Expression

Given an expression, how do we transform that into Assembly code.

Learned in CS241E.

Technique 1: Using stack

def generateCode(e1, operator, e2): Code = {
	t1 = new Variable
	block(
		// evaluate e1
		// push Reg.result onto stack
		// evaluate e2
		// pop stack onto Reg.scratch
		// apply operator, which stores answer in Reg.result
	)
}

• GOOD: The technique is general in that it can generate correct code for expressions of arbitrary depth. The stack can hold an arbitrary number of results of subexpressions.
• BAD: The generated code contains many pushes and pops on the stack, and is thus not very efficient in terms of code size and execution speed.
• BAD: The use of the stack makes the generated code complicated and difficult to understand, not only for people, but especially for later passes in the compiler that might optimize or improve the code further.

def generateCode ( e1 , operator , e2 ): ( Code , Variable ) = {
	(c1 , v1 ) = // code / variable to evaluate subexpression e1
	(c2 , v2 ) = // code / variable to evaluate other subexpression e2
	v3 = new Variable
	code = c1 ++ c2 :+ // code to apply operator to v1 and v2
	// and store result in v3
	( code , v3 )
}
 

Technique 2: Using variables (Virtual Registers)

• GOOD: The generated code is simple and flexible, and easy for a compiler to improve and optimize further.
• BAD: Machine language arithmetic instructions operate on registers, not directly on variables, so we cannot directly express expressions such as a*b or v1 + v2 as a single machine language instruction.
• BAD: To further translate this code into efficient assembly language, we need a way to map variables to registers, rather than to stack locations, and to map a large number of variables to a limited number of registers.

A technique to alleviate these last two disadvantages is Register Allocation.

Technique 3: variables for temporary values, arithmetic operations on registers (Used in assignment)

def generateCode(e1, operator, e2): Code = {
	t1 = new Variable
	block(
	// evaluate e1
	// store Reg.result into variable t1
	// evaluate e2
	// read variable t1 into Reg.scratch
	// apply operator, which stores result into Reg.result
	)
}