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:
e
in $a0
$sp
and the contents of the stack
We define a code-generation function cgen(e)
whose result is the code generated for e
cgen(i) =
li $a0 i
RED
: compile time
BLUE
: run time
cgen(e1+e2) = cgen(e1)
sw $a0 0($sp) addiu $sp $sp-4
cgen(e2)
lw $t1 r($sp) add $a0 $t1 $a0 addiu $sp $sp 4
cgen(e1+e2) =
cgen(e1)
print "sw $a0 0($sp)"
print "addiu $sp $sp-4"
cgen(e2)
print "lw $t1 r($sp)"
print "add $a0 $t1 $a0"
print "addiu $sp $sp 4"
This latter syntax is a bit more verbose, so we will largely stick to the short-hand notation.
e1
directly in $t1
Is this code correct? Why not? Consider ifcgen(e1+e2) = cgen(e1)
move $t1 $a0
cgen(e2)
add $a0 $t1 $a0
e2=e3+e4
+
is a template with "holes" for code for evaluating e1
and e2
.
e1+e2
is code for e1
and e2
glued together
cgen(e1-e2) = cgen(e1)
sw $a0 0($sp) addiu $sp $sp-4
cgen(e2)
lw $t1 r($sp) sub $a0 $t1 $a0 addiu $sp $sp 4
Dealing with if-then-else constructs:
beq reg1 reg2 label
reg1=reg2
b label
cgen(if e1=e2 then e3 else e4) = cgen(e1)
sw $a0 0($sp) addiu $sp $sp -4
cgen(e2)
lw $t1 4($sp) addiu $sp $sp 4 beq $a0 $t1 true_branch ... false_branch:
cgen(e4)
b end_if true_branch:
cgen(e3)
end_if:
Code for function calls and function definitions depends on the layout of the AR
A very simple AR suffices for this language:
f(x1,...,xn)
push x1,...,xn
on the stack
$sp
is the same as it was on function entry
$fp
(frame pointer)
f(x,y)
, the AR is:
FP: old fp | y } AR of f x | SP-> RA
jal label
$ra
jr reg
cgen(f(e1,e2,...,en)) =
sw $fp 0($sp) addiu $sp $sp -4
cgen(en)
sw $a0 0($sp) addiu $sp $sp - 4 ...
cgen(e1)
sw $a0 0($sp) addiu $sp $sp - 4 jal f_entry
$ra
4*n+8
bytes long
cgen(def f(x1,x2,...,xn) = e) =
f_entry: move $fp $sp sw $ra 0($sp) addiu $sp $sp -4
cgen(e)
lw $ra 4($sp) addiu $sp $sp z lw $fp 0($sp) jr $ra
FP --> SP -->
FP --> old fp y x SP--> (this is where the return address will go)
FP --> old fp y x FP--> ra SP-->
FP --> SP -->
Variable references are the last construct
$sp
xi
be the ith (i=1..n) formal parameter of the function for which code is being generated
cgen(xi) = lw $a0 z($fp) [z = 4*i]e.g.,
x
at $fp+4
and y
at $fp+8
$sp
vis-a-vis the value of $sp
at function entry, and thus appropriately adjust the addresses of all variables. Pro: one less register (no frame pointer needed now)! Con: much harder to read and debug the code now. Also not possible with VLAs (variable length arrays).
Summary
def sumto(x) = if x = 0 then 0 else x + sumto(x-1)
sumto_entry: move $fp $sp sw $ra 0($sp) addiu $sp $sp -4 lw $a0 4($fp) sw $a0 0($sp) addiu $sp $sp -4 li $a0 0 lw $t1 4($sp) addiu $sp $sp 4 beq $a0 $t1 true1 false1: lw $a0 4($fp) sw $a0 0($sp) addiu $sp $sp -4 sw $fp 0($sp) addiu $sp $sp -4 lw $a0 4($fp) # x sw $a0 0($sp) addiu $sp $sp -4 li $a0 1 lw $t1 4($sp) sub $a0 $t1 $a0 # x - 1 addiu $sp $sp 4 sw $a0 0($sp) addiu $sp $sp -4 jal sumto_entry lw $t1 4($sp) add $a0 $t1 $a0 addiu $sp $sp 4 b endif1 true1: li $a0 0 endif1: lw $r1 4(esp) addiu $sp $sp 12 lw $fp 0($sp) jr $ra
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.
x=1
x=2
fib
x-1
x-2
Let NT(e)
be the number of temps needed to evaluate e
NT(e1+e2)
NT(e1)
NT(e2) + 1
e1
e1
can be reused for temporaries in e2
NT(e1+e2) = max(NT(e1), 1+NT(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
cgen(e1+e2) = cgen(e1) sw $a0 0($sp) addiu $sp $sp -4 cgen(e2) lw $t1 4($sp) add $a0 $t1 $a0 addiu $sp $sp 4
cgen(e1+e2, nt) = cgen(e1, nt) sw $a0 nt($sp) cgen(e2, nt+4) lw $t1 nt($fp) add $a0 $t1 $a0