import std.stdio;

enum Type {
    number,
    id,
    add,
    sub,
    mul,
    div,
    push,
    pop,
    none
}

enum Reg {
    none,
    r0,
    r1
}

class AST {
    AST left;
    AST right;
    Type type;
    Reg reg;
    int n;

    this(AST l, AST r, Type t) {
        left = l;
        right = r;
        type = t;
        n = 0;
    }
}

class BinExpression : AST {
    this(AST l, AST r, Type t) {
        super(l, r, t);
    }
}

class Identifier : AST {
    string name;

    this(string nm) {
        super(null, null, Type.id);
        name = nm;
    }
}

class Number : AST {
    int number;

    this(int n) {
        super(null, null, Type.number);
        number = n;
    }
}


Reg[] regs = [ Reg.r0, Reg.r1 ];
const int regs_num = regs.sizeof / int.sizeof;
int C = 0;

void main() {
    // ((2 + 2) + (2 + 2)) + ((2 + 2) + (2 + 2))
    // t1 = 2 + 2
    // t2 = 2 + 2
    // t3 = t1 + t2
    // t4 = 2 + 2
    // t5 = 2 + 2
    // t6 = t4 + t5
    // t7 = t3 + t6
    Number a = new Number(2);
    Number b = new Number(2);

    Number c = new Number(2);
    Number d = new Number(2);

    Number e = new Number(2);
    Number f = new Number(2);

    Number g = new Number(2);
    Number h = new Number(2);


    // t1 = 2 + 2
    BinExpression t1 = new BinExpression(a, b, Type.add);
    // t2 = 2 + 2
    BinExpression t2 = new BinExpression(c, d, Type.add);
    // t3 = t1 + t2
    BinExpression t3 = new BinExpression(t1, t2, Type.add);
    // t4 = 2 + 2
    BinExpression t4 = new BinExpression(e, f, Type.add);
    // t5 = 2 + 2
    BinExpression t5 = new BinExpression(g, h, Type.add);
    // t5 = t3 + t4
    BinExpression t6 = new BinExpression(t4, t5,Type.add);
    BinExpression t7 = new BinExpression(t3, t6, Type.add);
    label(t7);
    gen(t7);
}

Reg get_reg() {
    if(C == regs.sizeof / int.sizeof) {
        //writeln("out of registers!");
        C = 0;
    }

    return regs[C++];
}

void gen(AST ast) {
    if(ast.left !is null && ast.right !is null) {
        int l = ast.left.n;
        int r = ast.right.n;

        if(l >= regs_num && r >= regs_num) {
            gen(ast.right);
            ast.n -= 1;
            //Reg r2 = ast.right.reg;
            emit_operation(Type.push, ast.right.reg);
            gen(ast.left);
            ast.reg = get_reg();
            emit_operation(Type.pop, ast.right.reg);
            //push_reg(r2);
        } else if(l >= r) {
            gen(ast.left);
            gen(ast.right);
            ast.n -= 1;
        } else if(l < r) {
            gen(ast.right);
            gen(ast.left);
            ast.n -= 1;
        }

        ast.reg = get_reg();
        Reg r1 = ast.left.reg;
        Reg r2 = ast.right.reg;
        emit_operation(ast.type, r1, r2);
        // result is in r1, so free r2.
        //push_reg(r2);
    } else if(ast.type == Type.id || ast.type == Type.number) {
        ast.n += 1;
        ast.reg = get_reg();
        emit_load(ast);
    } else {
        writeln("gen() error");
        // error
    }
}

void label(AST ast) {
    if(ast is null)
        return;

    label(ast.left);
    label(ast.right);

    if(ast.type == Type.id || ast.type == Type.number)
        ast.n = 1;
    // ast has two childrens
    else if(ast.left !is null && ast.right !is null) {
        int l = ast.left.n;
        int r = ast.right.n;

        if(l == r)
            ast.n = 1 + l;
        else
            ast.n = max(1, l, r);
    }
    // ast has one child
    else if(ast.left !is null && ast.right is null)
        ast.n = ast.left.n;
    else
        writeln("label() error!");
}

int max(int x, int y, int z) {
    return max(x, max(y, z));
}

int max(int a, int b) {
    return a > b ? a : b;
}

void emit_operation(Type op, Reg r1, Reg r2)
{
    writefln("\t%s %s,%s",
                     op_as_string(op),
                     reg_as_string(r1),
                     reg_as_string(r2));
}

void emit_load(AST ast) {
    switch(ast.type) {
        case Type.id:
            writefln("\t LOAD %s,[%s]", reg_as_string(ast.reg), (cast(Identifier)ast).name);
            break;
        case Type.number:
            writefln("\t LOAD %s,%d", reg_as_string(ast.reg), (cast(Number)ast).number);
            break;
        default:
            writeln("emitLoad() error!");
    }
}

void emit_operation(Type op, Reg r)
{
    writefln("\t%s %s",
                     op_as_string(op),
                     reg_as_string(r));
}

string reg_as_string(Reg r) {
    switch(r) {
        case Reg.r0:   return "R0";
        case Reg.r1:   return "R1";
        case Reg.none: return "NONE";
        default:     return "UNKNOW";
    }
}

string op_as_string(Type t) {
    switch(t) {
        case Type.add: return "ADD";
        case Type.sub: return "SUB";
        case Type.mul: return "MUL";
        case Type.div: return "DIV";
        case Type.push: return "push";
        case Type.pop: return "pop";
        default:     return "UNKNOW";
    }
}