Description
Construct an instruction generator for a subset of tiger that includes the following:
exp:
int
exp binop exp
id ( explist )
let declist in exp end
if test then exp else exp
binop:
+ - * /
test:
exp = exp
declist:
dec
dec declist
dec:
function id ( formals ) = exp
explist:
exp
explist , exp
formals:
formal
formal, formals
formal:
id
Your assignment is to implement (in semant.sml) a code generator for this subset of tiger. The full description of tiger is in the Appendix A of the book, and you can get a short description of Tiger. Remember, you don't have to implement the whole language, just what I describe above.
I made some simplifying assumptions in mine, you can use these as
well. My compiler only works if a let is at the outermost level of an
expression, and I have only one function in the let. The function can
only have one argument. You can build a quick and dirty code generator
using print statements in the type checker in semant.sml.
Quick and dirty instruction generation
Your code generator should implement a stack machine, like the one described in Alex Aiken's slides.
For example, the program:
123
should parse as an IntExp. In the translator for IntExp, we can
print assembly code to load 123 into a register:
| trexp (A.IntExp i) = {ty=Types.INT,
exp=(print ("li $a0, " ^ Int.toString i ^ "\n"))}
This code prints the MIPS assembly instruction to load an immediate
into register $a0, which we will use as the top of the stack. Since
print returns unit, this version of semant.sml has the same
types as last assignments.
To translate a more complicated expression like e1 + e2 we need to
translate e1 and save it to the stack, then translate e2, pop e1
to a temp register (we use $t0), and add them, leaving the result in
$a0. The stack pointer must end up at the same position as when we
started.
| trexp (A.OpExp{left, A.PlusOp, right, pos}) =
let
val e1 = trexp left
in
checkInt (e1, pos);
print "sw $a0, 0($sp)\n"; (* save e1 *)
print "addiu $sp, -4\n"; (* push stack *)
let
val e2 = trexp right
in
checkInt (e2, pos);
end;
{ty=Types.INT,
exp=(
print "lw $t1, 4($sp)\n"; (* copy e1 to tmp *)
print "add $a0, $t1, $a0\n"; (* add e1 and e2 *)
print "addiu $sp, 4\n" (* pop stack *)
)}
end
You may continue to expand on this, but you don't have to do any real type checking for this language, as we only have integer expressions.
Example code
Here's a small program 5 + 3 that should generate code.
- Semant.transProg (Parse.parse "sum.tig");
main:
li $a0, 5
sw $a0, 0($sp)
addiu $sp, $sp, -4
li $a0, 3
lw $t1, 4($sp)
add $a0, $t1, $a0
addiu $sp, $sp, 4
val it = () : unit
A recursive implementation of Fibonacci.
let
function fib(n) =
if n = 0 then 0 else
if n = 1 then 1 else
fib(n - 1) + fib(n - 2)
in
fib(10)
end
Should result in code like the following. You can load the code into the MARS MIPS simulator and run it.
main:
b start
fib:
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 true_branch1
false_branch1:
lw $a0, 4($fp)
sw $a0 0($sp)
addiu $sp $sp -4
li $a0, 1
lw $t1 4($sp)
addiu $sp $sp 4
beq $a0 $t1 true_branch2
false_branch2:
sw $fp 0($sp)
addiu $sp $sp -4
lw $a0, 4($fp)
sw $a0, 0($sp)
addiu $sp, $sp, -4
li $a0, 1
lw $t1, 4($sp)
sub $a0, $t1, $a0
addiu $sp, $sp, 4
sw $a0 0($sp)
addiu $sp $sp -4
jal fib
sw $a0, 0($sp)
addiu $sp, $sp, -4
sw $fp 0($sp)
addiu $sp $sp -4
lw $a0, 4($fp)
sw $a0, 0($sp)
addiu $sp, $sp, -4
li $a0, 2
lw $t1, 4($sp)
sub $a0, $t1, $a0
addiu $sp, $sp, 4
sw $a0 0($sp)
addiu $sp $sp -4
jal fib
lw $t1, 4($sp)
add $a0, $t1, $a0
addiu $sp, $sp, 4
b end_if2
true_branch2:
li $a0, 1
end_if2:
b end_if1
true_branch1:
li $a0, 0
end_if1:
lw $ra 4($sp)
addiu $sp $sp 12
lw $fp 0($sp)
jr $ra
start:
sw $fp 0($sp)
addiu $sp $sp -4
li $a0, 10
sw $a0 0($sp)
addiu $sp $sp -4
jal fib