In this assignment you will compile the Fun intermediate language into MIPS
assembly with virtual registers. We will provide code to do register
allocation for you. The final compiler output can be run using the SPIM
simulator. In order to complete this assignment, you will have to use the
SPIM simulator and understand the MIPS assembly language:
This is an excellent document describing the MIPS assembly
language, calling conventions, and using the SPIM simulator.
See, in particular, chapter A.9 for a description of the MIPS
instructions you will use. spim and xspim have been installed
on the Linux OIT machines (eg: boater). In addition, Guilherme
added a symbolic link to spim and xspim in the ml directory that
you should already have in your PATH, so that if you invoke spim or
xspim on the command line from a Solaris machine (eg: arizona) it
should work fine. If you have difficulties with spim, please send e-mail
to the cos320 list.
If you would like to install SPIM on your own machine, source
code and binaries can be downloaded from this site. You can
get PCspim for your PC here. Documentation on PCSpim is
the factorial function in fun. Here is some
commented output assembly.
Caution, documentation bug!
The first operand of jalr is the register where to put the return
address (you must use $ra, which is what gencode_func,
described below expects), and the second one is the register containing the
address of the function to be executed. NOTE: the order of the jalr
operands is the OPPOSITE of what appears on the SPIM documentation.
[We have notified the implementor of SPIM.]
Copy /u/cos320/chap6/* and /u/cos320/chap6/tests/* into a new directory
If you have your own working copies of the
parser, lexer, etc from assignments 2, 3 and 4 you may use them for this
assignment. If you don't have
working versions, then use the ones we provide.
Your main job is to compile Fun language expressions into assembly language
with virtual registers. This involves understanding the mips.sig
interface, which describes the subset of the MIPS architecture you will be
compiling to, and gencode.sml, which you will need to understand and
modify. In gencode.sml, you will fill in the function gc_exp (a
part of gencode_exp) to
generate code for expressions. You will have to figure out how to compile
most of the expressions yourself. However, here are some hints:
gencode_exp has three arguments:
fenv : maps function identifiers to labels (and their code)
to find the label corresponding to a function identifier f
in fenv, call get_func_label fenv f
venv : maps local variables to the virtual register that
to find a virtual register that corresponds to local variable
id in venv, call Env.find (venv, id)
to extend venv so that it maps a new local variable x
to a new register r, call Env.insert (venv, x, r)
exp : the expression to be compiled
gc_exp is nested inside gencode_exp. It inherits fenv from
gencode_exp and has its own venv and expression to
gc_exp (and gencode_exp) both return the register where is
the expression result will be found. This should be some new virtual
register generated specifically for returning this result (unless you are
returning 0, in which case you may use the $zero register). Do
not reuse virtual registers. The register allocator takes care of
making efficient use of registers.
You should use the function emit provided in gencode.sml
to "emit" (ie: construct/generate/produce) each instruction or label.
emit (Instr i) (* emits Mips instruction i at the
current point in the code generation stream *)
emit (Lab l) (* emits Mips label l
beginning a new block of instructions *)
To create a new label for code when you do not care about the name of
the label (for example, when compiling if expressions or while
expressions), use the function Mips.freshlab.
Each time you need to store a new temporary result, you should store it
in a virtual register. To get a new virtual register that has not been
used before use the function Mips.newReg. Do not store any
temporaries in real registers or on the stack. The register allocator
that we have written for you will figure out how to use real registers and
the stack effectively. One exception is that if you need a register
containing 0, you may use the register $zero. Another exception
is when emitting code for a function call, as explained below.
When generating code for a function call, you should follow the MIPS calling convention. This calling convention requires that you put
the function argument in register $a0 and return value in $v0.
You should only move an argument to $a0immediately before
calling the function and upon return from the function, you should immediately move the result from
$v0 to a new virtual register.
This might create seemingly unnecessary move instructions, but the register
allocator will be able to optimize unnecessary moves away. If there
are virtual registers containing objects that are needed after the function
call, you do not need to save the contents of these virtual registers to the
stack before the call and restore them afterwards. The register
allocator will take care of saving and restoring registers containing values
that persist across calls.
To convert a string such as "$a0" or "$v0" or "$zero" to a Mips register
(ie: to an ML value with type Mips.reg), use the function Mips.reg.
Similarly, to convert an integer such as 3 to a Mips immediate value use the
If the expression has type <>, you can
simply return register $zero.
The code generator always generates two new functions in the code, init and
alloc. The function init is used to obtain heap space the
program can use from the operating system when the program starts up (you
will not need to call init in your code). The function alloc takes a
single integer argument i (in register $a0 as the MIPS calling
convention specifies), allocates space for an object with size i and
returns a pointer to the beginning of the freshly allocated space in
register $v0. You may store the first value in the tuple or ref
at address 0($v0). When compiling the tuple and ref creation
operations, you can use the function emit_alloc_call in gencode.sml
to emit a sequence of instructions that invokes alloc.
We have not implemented a garbage collector so a program can run out of
To test your code generator on <file>.fun, use Compile.compile
<file>.fun. This command will generate two files. The first is
<file>.fun.noregalloc.s. It contains the code that you generated.
Since this code contains virtual registers, you cannot run it on the spim
simulator. The second file, called <file>.fun.s
contains the final assembly output. Note that the code in this
second file will not be identical
to the code that you generated because the register allocator has eliminated
virtual registers and replaced them with real registers. It also loads and
stores values to and from the stack. It can be executed using spim. We are providing
you with the binaries for the register allocator and liveness analysis (in the
CM directory) -- writing your own version of these will be part of your
To test execution of your code, invoke spim in the most abstract mode (with no load/branch delay slots).
This is the default mode in spim and xspim. To check the
mode, go to simulator -> settings, make sure that the only checked boxes under
execution are "Allow pseudo instructions" and "Load exception file"
On a linux machine, type in xspim <Ret> and a graphic interface
will be brought up. Click on the "load" button to load a file. Click on
"Run" to run the program. Click on "step" button to single step
through the program. Docs for xspim can be found
On a PC using PCspim, double click the PCspim icon.
Click on "File-> Open" button to load a .s file. Click on the "run" button
to run the program. A console window will pop up when the program finish
executing. Docs for PCspim are
The code we are providing already handles a couple of expression patterns,
enough to generate code for tests/test0.fun. You may want to compile this
program and check its output (tests/test0.fun.s).