package cd.backend.codegen;

import cd.Config;
import cd.backend.ExitCode;
import cd.backend.codegen.RegisterManager.Register;
import cd.ir.Ast.*;
import cd.ir.Ast.BinaryOp.BOp;
import cd.ir.Ast.UnaryOp.UOp;
import cd.ir.CompileTimeEvaluator;
import cd.ir.ExprVisitor;
import cd.ir.Symbol.*;
import cd.transform.analysis.MaybeC;
import cd.util.Pair;
import cd.util.debug.AstOneLine;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Optional;

import static cd.Config.FALSE;
import static cd.Config.TRUE;
import static cd.backend.codegen.AssemblyEmitter.constant;
import static cd.backend.codegen.AssemblyEmitter.labelAddress;
import static cd.backend.codegen.RegisterManager.BASE_REG;

/**
 * Generates code to evaluate expressions. After emitting the code, returns a
 * String which indicates the register where the result can be found.
 */
class ExprGenerator extends ExprVisitor<Register, Void> {
	protected final AstCodeGenerator cg;

	ExprGenerator(AstCodeGenerator astCodeGenerator) {
		cg = astCodeGenerator;
	}

	public Register gen(Expr ast) {
		return visit(ast, null);
	}

	@Override
	public Register visit(Expr ast, Void arg) {
		try {
			cg.emit.increaseIndent("Emitting " + AstOneLine.toString(ast));
			return super.visit(ast, null);
		} finally {
			cg.emit.decreaseIndent();
		}

	}

	@Override
	public Register intConst(IntConst ast, Void arg) {
		{
			Register reg = cg.rm.getRegister();
			cg.emit.emit("movl", ast.value, reg);
			return reg;
		}
	}

	@Override
	public Register unaryOp(UnaryOp ast, Void arg) {
		{
			Register argReg = gen(ast.arg());
			switch (ast.operator) {
				case U_PLUS:
					break;

				case U_MINUS:
					cg.emit.emit("negl", argReg);
					break;

				case U_BOOL_NOT:
					cg.emit.emit("xor", 1, argReg);
					break;
			}
			return argReg;
		}
	}
}

/*
 * This is the subclass of ExprGenerator containing the reference solution
 */
class ExprGeneratorRef extends ExprGenerator {

	/* cg and cgRef are the same instance. cgRef simply
	 * provides a wider interface */
	protected final AstCodeGeneratorRef cgRef;

	ExprGeneratorRef(AstCodeGeneratorRef astCodeGenerator) {
		super(astCodeGenerator);
		this.cgRef = astCodeGenerator;
	}

	/**
	 * This routine handles register shortages. It generates a value for
	 * {@code right}, while keeping the value in {@code leftReg} live. However,
	 * if there are insufficient registers, it may temporarily store the value
	 * in {@code leftReg} to the stack. In this case, it will be restored into
	 * another register once {@code right} has been evaluated, but the register
	 * may not be the same as {@code leftReg}. Therefore, this function returns
	 * a pair of registers, the first of which stores the left value, and the
	 * second of which stores the right value.
	 */
	public Pair<Register> genPushing(Register leftReg, Expr right) {
		Register newLeftReg = leftReg;
		boolean pop = false;

		if (cgRef.rnv.calc(right) > cgRef.rm.availableRegisters()) {
			cgRef.push(newLeftReg.repr);
			cgRef.rm.releaseRegister(newLeftReg);
			pop = true;
		}

		Register rightReg = gen(right);

		if (pop) {
			newLeftReg = cgRef.rm.getRegister();
			cgRef.pop(newLeftReg.repr);
		}

		return new Pair<Register>(newLeftReg, rightReg);

	}

	@Override
	public Register binaryOp(BinaryOp ast, Void arg) {
		Register leftReg = null;
		Register rightReg = null;

		{

			leftReg = gen(ast.left());
			Pair<Register> regs = genPushing(leftReg, ast.right());
			leftReg = regs.a;
			rightReg = regs.b;

		}

		assert leftReg != null && rightReg != null;

		new OperandsDispatcher() {

			@Override
			public void booleanOp(Register leftReg, BOp op, Register rightReg) {
				integerOp(leftReg, op, rightReg);
			}

			@Override
			public void integerOp(Register leftReg, BOp op, Register rightReg) {

				switch (op) {
					case B_TIMES:
						cgRef.emit.emit("imull", rightReg, leftReg);
						break;
					case B_PLUS:
						cgRef.emit.emit("addl", rightReg, leftReg);
						break;
					case B_MINUS:
						cgRef.emit.emit("subl", rightReg, leftReg);
						break;
					case B_DIV:
						emitDivMod(Register.EAX, leftReg, rightReg);
						break;
					case B_MOD:
						emitDivMod(Register.EDX, leftReg, rightReg);
						break;
					case B_AND:
						cgRef.emit.emit("andl", rightReg, leftReg);
						break;
					case B_OR:
						cgRef.emit.emit("orl", rightReg, leftReg);
						break;
					case B_EQUAL:
						emitCmp("sete", leftReg, rightReg);
						break;
					case B_NOT_EQUAL:
						emitCmp("setne", leftReg, rightReg);
						break;
					case B_LESS_THAN:
						emitCmp("setl", leftReg, rightReg);
						break;
					case B_LESS_OR_EQUAL:
						emitCmp("setle", leftReg, rightReg);
						break;
					case B_GREATER_THAN:
						emitCmp("setg", leftReg, rightReg);
						break;
					case B_GREATER_OR_EQUAL:
						emitCmp("setge", leftReg, rightReg);
						break;
					default:
						throw new AssemblyFailedException(
								"Invalid binary operator for "
										+ PrimitiveTypeSymbol.intType + " or "
										+ PrimitiveTypeSymbol.booleanType);
				}

			}

		}.binaryOp(ast, leftReg, rightReg);

		cgRef.rm.releaseRegister(rightReg);

		return leftReg;
	}

	private void emitCmp(String opname, Register leftReg, Register rightReg) {

		cgRef.emit.emit("cmpl", rightReg, leftReg);

		if (leftReg.hasLowByteVersion()) {
			cgRef.emit.emit("movl", "$0", leftReg);
			cgRef.emit.emit(opname, leftReg.lowByteVersion().repr);
		} else {
			cgRef.push(Register.EAX.repr);
			cgRef.emit.emit("movl", "$0", Register.EAX);
			cgRef.emit.emit(opname, "%al");
			cgRef.emit.emit("movl", Register.EAX, leftReg);
			cgRef.pop(Register.EAX.repr);
		}

	}

	private void emitDivMod(Register whichResultReg, Register leftReg,
							Register rightReg) {

		// Compare right reg for 0
		int padding = cgRef.emitCallPrefix(null, 1);
		cgRef.push(rightReg.repr);
		cgRef.emit.emit("call", AstCodeGeneratorRef.CHECK_NON_ZERO);
		cgRef.emitCallSuffix(null, 1, padding);

		// Save EAX, EBX, and EDX to the stack if they are not used
		// in this subtree (but are used elsewhere). We will be
		// changing them.
		List<Register> dontBother = Arrays.asList(rightReg, leftReg);
		Register[] affected = {Register.EAX, Register.EBX, Register.EDX};
		for (Register s : affected)
			if (!dontBother.contains(s) && cgRef.rm.isInUse(s))
				cgRef.emit.emit("pushl", s);

		// Move the LHS (numerator) into eax
		// Move the RHS (denominator) into ebx
		cgRef.emit.emit("pushl", rightReg);
		cgRef.emit.emit("pushl", leftReg);
		cgRef.emit.emit("popl", Register.EAX);
		cgRef.emit.emit("popl", "%ebx");
		cgRef.emit.emitRaw("cltd"); // sign-extend %eax into %edx
		cgRef.emit.emit("idivl", "%ebx"); // division, result into edx:eax

		// Move the result into the LHS, and pop off anything we saved
		cgRef.emit.emit("movl", whichResultReg, leftReg);
		for (int i = affected.length - 1; i >= 0; i--) {
			Register s = affected[i];
			if (!dontBother.contains(s) && cgRef.rm.isInUse(s))
				cgRef.emit.emit("popl", s);
		}
	}

	@Override
	public Register booleanConst(BooleanConst ast, Void arg) {
		Register reg = cgRef.rm.getRegister();
		cgRef.emit.emit("movl", ast.value ? TRUE : FALSE, reg);
		return reg;
	}

	@Override
	public Register builtInRead(BuiltInRead ast, Void arg) {
		Register reg = cgRef.rm.getRegister();
		int padding = cgRef.emitCallPrefix(reg, 0);
		cgRef.emit.emit("call", AstCodeGeneratorRef.READ_INTEGER);
		cgRef.emitCallSuffix(reg, 0, padding);
		return reg;
	}

	@Override
	public Register cast(Cast ast, Void arg) {
		// Invoke the helper function. If it does not exit,
		// the cast succeeded!
		Register objReg = gen(ast.arg());
		int padding = cgRef.emitCallPrefix(null, 2);
		cgRef.push(objReg.repr);
		cgRef.push(AssemblyEmitter.labelAddress(cgRef.vtable(ast.type)));
		cgRef.emit.emit("call", AstCodeGeneratorRef.CHECK_CAST);
		cgRef.emitCallSuffix(null, 2, padding);
		return objReg;
	}

	@Override
	public Register index(Index ast, Void arg) {
		Register arr = gen(ast.left());
		int padding = cgRef.emitCallPrefix(null, 1);
		cgRef.push(arr.repr);
		cgRef.emit.emit("call", AstCodeGeneratorRef.CHECK_NULL);
		cgRef.emitCallSuffix(null, 1, padding);
		Pair<Register> pair = genPushing(arr, ast.right());
		arr = pair.a;
		Register idx = pair.b;

		// Check array bounds
		padding = cgRef.emitCallPrefix(null, 2);
		cgRef.push(idx.repr);
		cgRef.push(arr.repr);
		cgRef.emit.emit("call", AstCodeGeneratorRef.CHECK_ARRAY_BOUNDS);
		cgRef.emitCallSuffix(null, 2, padding);

		cgRef.emit.emitMove(AssemblyEmitter.arrayAddress(arr, idx), idx);
		cgRef.rm.releaseRegister(arr);
		return idx;
	}

	@Override
	public Register field(Field ast, Void arg) {
		Register reg = gen(ast.arg());
		int padding = cgRef.emitCallPrefix(null, 1);
		cgRef.push(reg.repr);
		cgRef.emit.emit("call", AstCodeGeneratorRef.CHECK_NULL);
		cgRef.emitCallSuffix(null, 1, padding);
		assert ast.sym.offset != -1;
		cgRef.emit.emitLoad(ast.sym.offset, reg, reg);
		return reg;
	}

	@Override
	public Register newArray(NewArray ast, Void arg) {
		// Size of the array = 4 + 4 + elemsize * num elem.
		// Compute that into reg, store it into the stack as
		// an argument to Javali$Alloc(), and then use it to store final
		// result.
		ArrayTypeSymbol arrsym = (ArrayTypeSymbol) ast.type;
		Register reg = gen(ast.arg());

		// Check for negative array sizes
		int padding = cgRef.emitCallPrefix(null, 1);
		cgRef.push(reg.repr);
		cgRef.emit.emit("call", AstCodeGeneratorRef.CHECK_ARRAY_SIZE);
		cgRef.emitCallSuffix(null, 1, padding);

		Register lenReg = cgRef.rm.getRegister();
		cgRef.emit.emit("movl", reg, lenReg); // save length

		cgRef.emit.emit("imul", Config.SIZEOF_PTR, reg);
		cgRef.emit.emit("addl", 2 * Config.SIZEOF_PTR, reg);

		int allocPadding = cgRef.emitCallPrefix(reg, 1);
		cgRef.push(reg.repr);
		cgRef.emit.emit("call", AstCodeGeneratorRef.ALLOC);
		cgRef.emitCallSuffix(reg, 1, allocPadding);

		// store vtable ptr and array length
		cgRef.emit.emitStore(AssemblyEmitter.labelAddress(cgRef.vtable(arrsym)), 0, reg);
		cgRef.emit.emitStore(lenReg, Config.SIZEOF_PTR, reg);
		cgRef.rm.releaseRegister(lenReg);

		return reg;
	}

	@Override
	public Register newObject(NewObject ast, Void arg) {
		ClassSymbol clssym = (ClassSymbol) ast.type;
		Register reg = cgRef.rm.getRegister();
		int allocPadding = cgRef.emitCallPrefix(reg, 1);
		cgRef.push(constant(clssym.sizeof));
		cgRef.emit.emit("call", AstCodeGeneratorRef.ALLOC);
		cgRef.emitCallSuffix(reg, 1, allocPadding);
		cgRef.emit.emitStore(labelAddress(cgRef.vtable(clssym)), 0, reg);
		return reg;
	}

	@Override
	public Register nullConst(NullConst ast, Void arg) {
		Register reg = cgRef.rm.getRegister();
		cgRef.emit.emit("movl", "$0", reg);
		return reg;
	}

	@Override
	public Register thisRef(ThisRef ast, Void arg) {
		Register reg = cgRef.rm.getRegister();
		cgRef.emit.emitLoad(cgRef.THIS_OFFSET, BASE_REG, reg);
		return reg;
	}

	@Override
	public Register methodCall(MethodCallExpr ast, Void arg) {
		return cgRef.sg.methodCall(ast.sym, ast.allArguments());
	}

	@Override
	public Register var(Var ast, Void arg) {
		Register reg = cgRef.rm.getRegister();
		switch (ast.sym.kind) {
			case LOCAL:
			case PARAM:
				assert ast.sym.offset != -1;
				cgRef.emit.emitLoad(ast.sym.offset, BASE_REG, reg);
				break;
			case FIELD:
				// These are removed by the ExprRewriter added to the
				// end of semantic analysis.
				throw new RuntimeException("Should not happen");
		}
		return reg;
	}

	@Override
	public Register unaryOp(UnaryOp ast, Void arg) {
		if (ast.operator == UOp.U_MINUS) {
			Register argReg = gen(ast.arg());
			cgRef.emit.emit("negl", argReg);
			return argReg;
		} else {
			return super.unaryOp(ast, arg);
		}
	}
}

class ExprGeneratorNop90 extends ExprGeneratorRef {
	protected final CfgCodeGenerator cfgCg;
	protected CompileTimeEvaluator cte;

	ExprGeneratorNop90(AstCodeGeneratorNop90 cg, CfgCodeGenerator cfgCodeGenerator) {
		super(cg);
		this.cfgCg = cfgCodeGenerator;
		cte = new CompileTimeEvaluator();
	}


	@Override
	public Register field(Field ast, Void arg) {
		Register reg = gen(ast.arg());
		// only emit runtime Null check if the field is not known to be non null
		if (!cfgCg.check.isNotNull(ast)) {
			int padding = cgRef.emitCallPrefix(null, 1);
			cgRef.push(reg.repr);
			cgRef.emit.emit("call", AstCodeGeneratorRef.CHECK_NULL);
			cgRef.emitCallSuffix(null, 1, padding);
		}
		assert ast.sym.offset != -1;
		cgRef.emit.emitLoad(ast.sym.offset, reg, reg);
		return reg;
	}

	@Override
	public Register index(Index ast, Void arg) {
		boolean emitBoundCheck = cfgCg.check.checkArrayBound(ast);
		boolean skipNullCheck = !cfgCg.check.isNotNull(ast.left());
		int padding;

		Register arr = gen(ast.left());
		if (skipNullCheck) {
			padding = cgRef.emitCallPrefix(null, 1);
			cgRef.push(arr.repr);
			cgRef.emit.emit("call", AstCodeGeneratorRef.CHECK_NULL);
			cgRef.emitCallSuffix(null, 1, padding);
		}
		Pair<Register> pair = genPushing(arr, ast.right());
		arr = pair.a;
		Register idx = pair.b;

		// Check array bounds
		if (emitBoundCheck) {
			padding = cgRef.emitCallPrefix(null, 2);
			cgRef.push(idx.repr);
			cgRef.push(arr.repr);
			cgRef.emit.emit("call", AstCodeGeneratorRef.CHECK_ARRAY_BOUNDS);
			cgRef.emitCallSuffix(null, 2, padding);
		}
		cgRef.emit.emitMove(AssemblyEmitter.arrayAddress(arr, idx), idx);
		cgRef.rm.releaseRegister(arr);
		return idx;
	}

	@Override
	public Register newArray(NewArray ast, Void arg) {
		// Size of the array = 4 + 4 + elemsize * num elem.
		// Compute that into reg, store it into the stack as
		// an argument to Javali$Alloc(), and then use it to store final
		// result.
		boolean checkArraySize = cfgCg.check.checkArraySize(ast);
		ArrayTypeSymbol arrsym = (ArrayTypeSymbol) ast.type;
		int size;
		Register reg = cgRef.rm.getRegister();
		Register lenReg = cgRef.rm.getRegister();
		Optional<Integer> sizeOptional = cte.calc(ast.arg());
		if (!sizeOptional.isPresent()) {
			reg = gen(ast.arg());}
		
		// Check for negative array sizes    
		if (checkArraySize) {
			int padding = cgRef.emitCallPrefix(null, 1);
			cgRef.push(reg.repr);
			cgRef.emit.emit("call", AstCodeGeneratorRef.CHECK_ARRAY_SIZE);
			cgRef.emitCallSuffix(null, 1, padding);
		}

		if (!sizeOptional.isPresent()) {
			cgRef.emit.emit("movl", reg, lenReg);} // save length}
		else {
			size = sizeOptional.get();
			cgRef.emit.emit("movl", size, lenReg);	
		}
		
		if (!sizeOptional.isPresent()) {
			cgRef.emit.emit("imul", Config.SIZEOF_PTR, reg);
			cgRef.emit.emit("addl", 2 * Config.SIZEOF_PTR, reg);}
		else {
			size = sizeOptional.get();
			size = (size * Config.SIZEOF_PTR) + (2*Config.SIZEOF_PTR);
			cgRef.emit.emit("pushl", size);
		}

		int allocPadding = cgRef.emitCallPrefix(reg, 1);
		if (!sizeOptional.isPresent()) {
			cgRef.push(reg.repr);}
		cgRef.emit.emit("call", AstCodeGeneratorRef.ALLOC);
		cgRef.emitCallSuffix(reg, 1, allocPadding);

		// store vtable ptr and array length
		cgRef.emit.emitStore(AssemblyEmitter.labelAddress(cgRef.vtable(arrsym)), 0, reg);
		cgRef.emit.emitStore(lenReg, Config.SIZEOF_PTR, reg);
		cgRef.rm.releaseRegister(lenReg);

		return reg;
	}
	
	
	@Override
	public Register unaryOp(UnaryOp ast, Void arg) {
			Optional<Integer> optinalvalue = cte.calc(ast.arg());
			Register argReg;
			if (optinalvalue.isPresent()) {
				int value = optinalvalue.get();
				argReg = cgRef.rm.getRegister();
				switch (ast.operator) {
				case U_PLUS:
					break;

				case U_MINUS:
					value = value * -1;
					cgRef.emit.emit("movl",value, argReg);
					break;
				case U_BOOL_NOT:
					if (value==1) {
						cgRef.emit.emit("movl",0, argReg);
					}
					else {
						cgRef.emit.emit("movl",1, argReg);
					}
					break;
			}
			return argReg;
			}
			
			argReg = gen(ast.arg());
			switch (ast.operator) {
				case U_PLUS:
					break;

				case U_MINUS:
					cgRef.emit.emit("negl", argReg);
					break;

				case U_BOOL_NOT:
					cgRef.emit.emit("xor", 1, argReg);
					break;
			}
			return argReg;
	}
	


	@Override
	public Register binaryOp(BinaryOp ast, Void arg) {
		Register leftReg;
		Register rightReg = null;
		Optional<Integer> leftVal = cte.calc(ast.left());
		Optional<Integer> rightVal = cte.calc(ast.right());

		if (leftVal.isPresent() && ast.operator.isCommutative()) {
			// Switch sides of operation so that rightVal has the value
			Expr auxExpr = ast.left();
			ast.setLeft(ast.right());
			ast.setRight(auxExpr);
			rightVal = leftVal;
		}

		leftReg = gen(ast.left());

		if (!rightVal.isPresent()) {
			switch (ast.operator) {
				case B_OR:
				case B_AND:
					shortCircuitedBinaryOp(leftReg, ast.operator, ast.right());
					return leftReg;
				default:
					Pair<Register> regs = genPushing(leftReg, ast.right());
					leftReg = regs.a;
					rightReg = regs.b;
			}
		}

		assert leftReg != null && (rightReg != null || rightVal.isPresent());

		ImmediateOperandsDispatcher dispatcher = new ImmediateOperandsDispatcher() {

			@Override
			public void booleanOp(Register leftReg, BOp op, Register rightReg) {
				integerOp(leftReg, op, rightReg);
			}

			@Override
			public void booleanOp(Register leftReg, BOp op, int rightVal) {
				integerOp(leftReg, op, rightVal);
			}

			@Override
			public void integerOp(Register leftReg, BOp op, int rightVal) {
				switch(op) {
					case B_TIMES:
						cgRef.emit.emit("imull", rightVal, leftReg);
						break;
					case B_PLUS:
						cgRef.emit.emit("addl", rightVal, leftReg);
						break;
					case B_MINUS:
						cgRef.emit.emit("subl", rightVal, leftReg);
						break;
					case B_DIV:
						emitDivMod(Register.EAX, leftReg, rightVal);
						break;
					case B_MOD:
						emitDivMod(Register.EDX, leftReg, rightVal);
						break;
					case B_AND:
						cgRef.emit.emit("andl", rightVal, leftReg);
						break;
					case B_OR:
						cgRef.emit.emit("orl", rightVal, leftReg);
						break;
					case B_EQUAL:
						emitCmp("sete", leftReg, rightVal);
						break;
					case B_NOT_EQUAL:
						emitCmp("setne", leftReg, rightVal);
						break;
					case B_LESS_THAN:
						emitCmp("setl", leftReg, rightVal);
						break;
					case B_LESS_OR_EQUAL:
						emitCmp("setle", leftReg, rightVal);
						break;
					case B_GREATER_THAN:
						emitCmp("setg", leftReg, rightVal);
						break;
					case B_GREATER_OR_EQUAL:
						emitCmp("setge", leftReg, rightVal);
						break;
					default:
						throw new AssemblyFailedException(
								"Invalid binary operator for "
										+ PrimitiveTypeSymbol.intType + " or "
										+ PrimitiveTypeSymbol.booleanType);
				}
			}

			@Override
			public void integerOp(Register leftReg, BOp op, Register rightReg) {

				switch (op) {
					case B_TIMES:
						cgRef.emit.emit("imull", rightReg, leftReg);
						break;
					case B_PLUS:
						cgRef.emit.emit("addl", rightReg, leftReg);
						break;
					case B_MINUS:
						cgRef.emit.emit("subl", rightReg, leftReg);
						break;
					case B_DIV:
						emitDivMod(Register.EAX, leftReg, rightReg);
						break;
					case B_MOD:
						emitDivMod(Register.EDX, leftReg, rightReg);
						break;
					case B_AND:
						cgRef.emit.emit("andl", rightReg, leftReg);
						break;
					case B_OR:
						cgRef.emit.emit("orl", rightReg, leftReg);
						break;
					case B_EQUAL:
						emitCmp("sete", leftReg, rightReg);
						break;
					case B_NOT_EQUAL:
						emitCmp("setne", leftReg, rightReg);
						break;
					case B_LESS_THAN:
						emitCmp("setl", leftReg, rightReg);
						break;
					case B_LESS_OR_EQUAL:
						emitCmp("setle", leftReg, rightReg);
						break;
					case B_GREATER_THAN:
						emitCmp("setg", leftReg, rightReg);
						break;
					case B_GREATER_OR_EQUAL:
						emitCmp("setge", leftReg, rightReg);
						break;
					default:
						throw new AssemblyFailedException(
								"Invalid binary operator for "
										+ PrimitiveTypeSymbol.intType + " or "
										+ PrimitiveTypeSymbol.booleanType);
				}
			}
		};

		if (rightVal.isPresent()) {
			dispatcher.binaryOp(ast, leftReg, rightVal.get());
		} else {
			dispatcher.binaryOp(ast, leftReg, rightReg);
			cgRef.rm.releaseRegister(rightReg);
		}
		return leftReg;
	}

	private void shortCircuitedBinaryOp(Register left, BOp op, Expr right) {
		int definitiveValue;
		String opStr;
		switch (op) {
			case B_AND:
				definitiveValue = FALSE;
				opStr = "andl";
				break;
			case B_OR:
				definitiveValue = TRUE;
				opStr = "orl";
				break;
			default:
				throw new AssemblyFailedException("Unimplemented operator " + op);
		}
		String skipRightLabel = cgRef.emit.uniqueLabel();
		// Skip if value is unchangeable by operation
		cgRef.emit.emit("cmp", definitiveValue, left);
		cgRef.emit.emit("je", skipRightLabel);
		// Generate right side
		Pair<Register> regs = genPushing(left, right);
		left = regs.a;
		Register rightReg = regs.b;
		// Compare
		cgRef.emit.emit(opStr, rightReg, left);
		// Skip label
		cgRef.emit.emitLabel(skipRightLabel);
	}

	private void emitDivMod(Register whichResultReg, Register leftReg, int rightImm) {
		if (rightImm == 0) {
			cgRef.emit.emit("pushl", ExitCode.DIVISION_BY_ZERO.value);
			cgRef.emit.emit("call", Config.EXIT);
			return;
		}

		// Save EAX, EBX, and EDX to the stack if they are not used
		// in this subtree (but are used elsewhere). We will be
		// changing them.
		List<Register> dontBother = Collections.singletonList(leftReg);
		Register[] affected = {Register.EAX, Register.EBX, Register.EDX};
		for (Register s : affected)
			if (!dontBother.contains(s) && cgRef.rm.isInUse(s))
				cgRef.emit.emit("pushl", s);

		// Move the LHS (numerator) into eax
		// Move the RHS (denominator) into ebx
		cgRef.emit.emit("movl", leftReg, Register.EAX);
		cgRef.emit.emit("movl", rightImm, Register.EBX);
		cgRef.emit.emitRaw("cltd"); // sign-extend %eax into %edx
		cgRef.emit.emit("idivl", Register.EBX); // division, result into edx:eax

		// Move the result into the LHS, and pop off anything we saved
		cgRef.emit.emit("movl", whichResultReg, leftReg);
		for (int i = affected.length - 1; i >= 0; i--) {
			Register s = affected[i];
			if (!dontBother.contains(s) && cgRef.rm.isInUse(s))
				cgRef.emit.emit("popl", s);
		}
	}

	private void emitDivMod(Register whichResultReg, Register leftReg, Register rightReg) {
		// Compare right reg for 0 if value of rightReg is not known at compiletime
		int padding = cgRef.emitCallPrefix(null, 1);
		cgRef.push(rightReg.repr);
		cgRef.emit.emit("call", AstCodeGeneratorRef.CHECK_NON_ZERO);
		cgRef.emitCallSuffix(null, 1, padding);

		// Save EAX, EBX, and EDX to the stack if they are not used
		// in this subtree (but are used elsewhere). We will be
		// changing them.
		List<Register> dontBother = Arrays.asList(rightReg, leftReg);
		Register[] affected = {Register.EAX, Register.EBX, Register.EDX};
		for (Register s : affected)
			if (!dontBother.contains(s) && cgRef.rm.isInUse(s))
				cgRef.emit.emit("pushl", s);

		// Move the LHS (numerator) into eax
		// Move the RHS (denominator) into ebx
		cgRef.emit.emit("pushl", rightReg);
		cgRef.emit.emit("pushl", leftReg);
		cgRef.emit.emit("popl", Register.EAX);
		cgRef.emit.emit("popl", "%ebx");
		cgRef.emit.emitRaw("cltd"); // sign-extend %eax into %edx
		cgRef.emit.emit("idivl", "%ebx"); // division, result into edx:eax

		// Move the result into the LHS, and pop off anything we saved
		cgRef.emit.emit("movl", whichResultReg, leftReg);
		for (int i = affected.length - 1; i >= 0; i--) {
			Register s = affected[i];
			if (!dontBother.contains(s) && cgRef.rm.isInUse(s))
				cgRef.emit.emit("popl", s);
		}
	}

	// Comparison emission split into 3 to allow immediate values

	private void emitCmp(String opname, Register leftReg, Register rightReg) {
		cgRef.emit.emit("cmpl", rightReg, leftReg);
		emitCmp(opname, leftReg);
	}

	private void emitCmp(String opname, Register leftReg, int rightImm) {
		cgRef.emit.emit("cmpl", rightImm, leftReg);
		emitCmp(opname, leftReg);
	}

	private void emitCmp(String opname, Register register) {
		if (register.hasLowByteVersion()) {
			cgRef.emit.emit("movl", "$0", register);
			cgRef.emit.emit(opname, register.lowByteVersion().repr);
		} else {
			if (cgRef.rm.isInUse(Register.EAX))
				cgRef.push(Register.EAX.repr);
			cgRef.emit.emit("movl", "$0", Register.EAX);
			cgRef.emit.emit(opname, "%al");
			cgRef.emit.emit("movl", Register.EAX, register);
			if (cgRef.rm.isInUse(Register.EAX))
				cgRef.pop(Register.EAX.repr);
		}
	}


	@Override
	public Register cast(Cast ast, Void arg) {
		Register objReg = gen(ast.arg());
		// Skip error checking if up-cast or dynamic type is known
		if (isUpCast(ast) || dynamicTypeKnown(ast))
			return objReg;

		int padding = cgRef.emitCallPrefix(null, 2);
		cgRef.push(objReg.repr);
		cgRef.push(AssemblyEmitter.labelAddress(cgRef.vtable(ast.type)));
		cgRef.emit.emit("call", AstCodeGeneratorRef.CHECK_CAST);
		cgRef.emitCallSuffix(null, 2, padding);
		return objReg;
	}

	private boolean isUpCast(Cast cast) {
		return isUpCast(cast.type, cast.arg().type);
	}


	private boolean isUpCast(TypeSymbol to, TypeSymbol from) {
		if (from instanceof ClassSymbol) {
			// Search upwards to find a matching type
			ClassSymbol sym = (ClassSymbol) from;
			while (sym != ClassSymbol.objectType) {
				if (sym == to)
					return true;
				sym = sym.superClass;
			}
		} else {
			assert from instanceof ArrayTypeSymbol;
			// Nothing to do, as only superType is Object
		}
		// Casts to Object and to the same declared type always succeed
		return to == from || to == ClassSymbol.objectType;
	}

	private boolean dynamicTypeKnown(Cast cast) {
		assert cfgCg.dynamicTypeState != null;
		if (cast.arg() instanceof Var) {
			VariableSymbol symbol = ((Var) cast.arg()).sym;
			MaybeC<TypeSymbol> dynamicType = cfgCg.dynamicTypeState.get(symbol);
			if (dynamicType != null && dynamicType.isConstant())
				return isUpCast(cast.type, dynamicType.getValue());
		}
		return false;
	}
}

/* Dispatches BinaryOp based on the types of the operands
 */
abstract class OperandsDispatcher {

	public abstract void integerOp(Register leftReg, BOp op,
								   Register rightReg);

	public abstract void booleanOp(Register leftReg, BOp op,
								   Register rightReg);

	public void binaryOp(BinaryOp ast, Register leftReg, Register rightReg) {

		assert ast.type != null;

		if (ast.type == PrimitiveTypeSymbol.intType) {
			integerOp(leftReg, ast.operator, rightReg);
		} else if (ast.type == PrimitiveTypeSymbol.booleanType) {

			final TypeSymbol opType = ast.left().type;

			if (opType == PrimitiveTypeSymbol.intType) {
				integerOp(leftReg, ast.operator, rightReg);
			} else if (opType == PrimitiveTypeSymbol.booleanType) {
				booleanOp(leftReg, ast.operator, rightReg);
			} else {
				integerOp(leftReg, ast.operator, rightReg);
			}
		}
	}
}

abstract class ImmediateOperandsDispatcher extends OperandsDispatcher {

	public abstract void integerOp(Register leftReg, BOp op, int rightVal);

	public abstract void booleanOp(Register leftReg, BOp op, int rightVal);

	public void binaryOp(BinaryOp ast, Register leftReg, int rightVal) {
		assert ast.type != null;

		if (ast.type == PrimitiveTypeSymbol.intType) {
			integerOp(leftReg, ast.operator, rightVal);
		} else if (ast.type == PrimitiveTypeSymbol.booleanType) {
			final TypeSymbol opType = ast.left().type;
			if (opType == PrimitiveTypeSymbol.intType) {
				integerOp(leftReg, ast.operator, rightVal);
			} else if (opType == PrimitiveTypeSymbol.booleanType) {
				booleanOp(leftReg, ast.operator, rightVal);
			} else {
				booleanOp(leftReg, ast.operator, rightVal);
			}
		}
	}
}
