COS 320 - Assignment 6

MIPS and SPIM

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).
2. Install Spim (get it from here). Note that the Spim documentation incorrectly describes the arguments of the Jalr instruction; the Spim simulator is correct: the first argument is the return-address register; the second argument is the address of the function being called.
   
3. Unpack as6.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."