COS320, Spring 2016: Compiling Techniques

MIPS and SPIM

The recursive Fibonacci function is,

fibrec ( n ) = if n<2 then r=1 else (d=fibrec(n-2); e=fibrec(n-1); r=d+e); return r 

fibiter ( n ) = a=1; b=1; while (n!=0) do (n=n-1; c=a; a=b; b=c+b); return a; 

1. Read Larus's introduction to MIPS and SPIM (which is Appendix A of Patterson & Hennessy's Computer Organization and Design). Note the following two mistakes in the document: on page A-23, the marginal notes on caller/callee-saved registers are the wrong way around. (The descriptions in the full text are correct). On page A-64, the order of arguments of the Jalr instruction is incorrect; the Spim simulator is correct: the first argument is the return-address register; the second argument is the address of the function being called.
   
2. Download the SPIM simulator appropriate for your OS from here, install it, and familarize yourself with it; additional documentation is available here.
3. Unpack as5.zip. The files errormsg.sml, table.sig, table.sml, symbol.sml are exactly as in previous assignments.
4. Modify the file fib.s by adding definitions for the _fibrec and _fibiter functions, as follows:
   
   • _fibrec should allocate 3 words of stack space, then save $ra and one callee-save register into the stack frame. The callee-save register should be used to hold the variable n, so it doesn't need to be saved and restored across the recursive call. The variable d should be kept in a caller-save register, and saved/restored just before/after the call to fibrec(n-1). (This is suboptimal; in this case it would be optimal to use caller-save registers only, but do it the suboptimal way just to learn how everything works.)
   • _fibiter should not touch the stack pointer at all, because it can use caller-save registers for all its local variables
   • Do not use the frame pointer at all; you don't need it.
5. Use Spim to run your fib.s. The result should be,

   3 3 

6. Read and understand mips.sig and mips.sml. Note particularly that Mips.RegSet is an instantiation of the ORD_SET module from the SML/NJ Library; see this page for reference.
   
7. Compile fibx.sml (by the usual CM.make "sources.cm";) and run Fibx.go(); This generates a file fibx.s, which is similar to fib.s.
8. Write the function bodies in fibx.sml for emit_fibrec_func and emit_fibiter_func in a style similar to emit_main_func.
9. Make sure that your generated fibx.s works correctly in Spim.
10. Submit README, fib.s, and fibx.sml to dropbox here. There may not be much to say in the README besides the usual "who I discussed this with, who I helped, who I got help from."