Programming Assignment 6:  Code Generation

The SPIM Simulator.

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.

 

The SPIM Homepage.

 

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 here.

Sample Output.

        Here 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.]

Instructions

1. Copy /u/cos320/chap6/* and /u/cos320/chap6/tests/* into a new directory as6. 
2. 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.
3. 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 contains them
       • 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 compile.
   • 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 $a0 immediately 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 function Mips.immed.
   • 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 space.
      
4. To test your code generator on <file>.fun, use Compile.compile <file>.fun. This command will generate two files.  The first is called <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 future assignments.
5. 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 here.
   • 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 here.
6. 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).
7. Submit by running submit 6 gencode.sml.