Expressions

First, we parse it into a tree

1. Evaluate subexpression e1
2. Push result to stack
3. Evaluate subexpression e2
4. Pop top of stack into a scratch register
   Result register has value of e1, scratch register has value of e2
5. Apply operator to result and scratch registers, store result in result register

Pseudocode:

/**
 * Generate assembly language code to evaluate a binary
 * expression "e1 operator e2", where e1 and e2 are
 * subexpressions and operator is some arithmetic operator,
 * and place the resulting value in Reg.result.
 */
def generateCode(e1, operator, e2): Code = block(
    generateCode(e1.e1),
    push(Reg(3)),
    generateCode(e2.e1),
    pop(Reg(4)),
    Reg(3) := Reg(4) operator Reg(3)
)

• Upsides:
  • Can generate correct code for expressions of arbitrary depth
• Downsides:
  • Inefficient, many pushes and pops are slow
  • Hard to optimize for both compiler and human

1. Evaluate subexpression e1, store result in a variable
2. Evaluate subexpression e2, store result in a variable
3. Apply operator to the two variables, store result in a variable

Pseudocode:

/**
 * Generate assembly language code to evaluate a binary expression
 * e1 operator e2, where e1 and e2 are subexpressions and operator
 * is some arithmetic operator, and place the resulting value
 * in a variable .
 */
def generateCode(e1, operator, e2): (Code, Variable) = {
    (c1, v1) = generateCode(e1)
    (c2, v2) = generateCode(e2)
    v3 = new Variable()
    code = block(c1, c2, v3 = v1 operator v2)

    (code , v3)
}

• Upsides:
  • Generates code that's easier to optimize
• Downsides:
  • Machine language arithmetic operates on registers, not variables, so we need multiple instructions to express expressions such as a * b
  • We need a way to map variables to registers rather than stack locations, and to map a large number of variables to a limited number of registers (which we could alleviate with Register Allocation)

1. Evaluate subexpression 1
2. Write result to a variable, t1
3. Evaluate subexpression 2
4. Read variable t1 into scratch register
   Result register has value of e2, scratch register has value of e1
5. Apply operator to result and scratch registers, store result in result register

Pseudocode:

 /**
 * Generate assembly language code to evaluate a binary
 * expression "e1 operator e2", where e1 and e2 are
 * subexpressions and operator is some arithmetic operator,
 * and place the resulting value in Reg.result.
 */
def generateCode (e1, operator, e2): Code = {
    t1 = new Variable()
    
    block(
         generateCode(e1),
         write(t1, Reg(3)),
         generateCode(e2),
         read(Reg(4), t1),
         
         Reg(3) := Reg(4) op Reg(3)
    )
}