Code Generation 1

A higher-level language
P --> D; P | D

D --> def id(ARGS) = E
ARGS --> id, ARGS | id
E --> int | id | if E1 = E2 then E3 else E4 | E1 + E2 | E1 - E2 | id(E1,...,En)

The first function definition f is the entry point

Program for computing the Fibonacci numbers:

def fib(x) = if x = 1 then 0 else
             if x = 2 then 1 else
             fib(x - 1) + fib(x - 2)

For each expression e we generate MIPS code that:

We define a code-generation function cgen(e) whose result is the code generated for e

Dealing with if-then-else constructs:

Code for function calls and function definitions depends on the layout of the AR

A very simple AR suffices for this language:

Variable references are the last construct

Summary

Example

def sumto(x) = if x = 0 then 0 else x + sumto(x-1)

Temporaries

Let's discuss a better way for compilers to manage temporary values. Idea: keep temporaries in the AR. The code generator must assign a fixed location in the AR for each temporary. (We will later discuss keeping temporaries in registers, which is even more efficient).
def fib(x) = if x = 1 then 0 else if x = 2 then 1 else fib(x-1) + fib(x-2)
If we first analyze the code to see how many temporaries we need, we can allocate space for that, instead of pushing and popping it from the stack each time. But many of these temporaries are only needed once and not needed after that. So some of the space can be re-used for the subsequent temporaries. In fact, we can evaluate the whole expression using only two temporaries.

Let NT(e) be the number of temps needed to evaluate e

NT(e1+e2)

Generalizing, we get a system of equations:

NT(e1+e2)	= max(NT(e1), 1+NT(e2))
NT(e1-e2)	= max(NT(e1), 1+NT(e2))
NT(if e1=e2 then e3 else e4) = max(NT(e1),1+NT(e2), NT(e3), NT(e4)) #once the branch is decided we do not need to hang on to e1/e2
NT(id(e1,...,en)) = max(NT(e1),...,NT(en))  #the space for the result for ei is saved in the new activation record that we are building and so we do not count them in the space required for the current activation record.
NT(int) = 0
NT(id) = 0

Looking at our fib example

def fib(x) = if (x[0] = 1[0])[1] then 0[0] else if (x[0] = 2[0])[1] then 1[0] else fib((x[0] - 1[0])[1])[1] + fib((x - 2)[1])[1 + 1]
Show that the entire expression evaluates to NT=2

Once we know the number of temporaries required, we can add that much space for the AR

AR layout

Old FP
xn
..
x1
RA
Temp NT(e)
Temp NT(e) - 1
..
Temp 1

Code generation must know how many temporaries are in use at each point