COS 320 - Assignment 10

Putting it all together

1. Nothing to unpack this time, you'll just be editing existing files.
2. In regalloc.sml, implement at least the simple version of spilling described below (you probably need to modify the last couple of lines of the code given in order to invoke the spill routine as necessary.
3. Now that all modules are available and you understand how everything works, revisit codegen.sml and (if necessary) correct the the use/def annotations of the jump instructions you generate. If necessary, modify the calculation of def-use in liveness.sml, too, but leave mips.sml unchanged.
4. Test your compiler for end-to-end correctness on several examples. The compilation of some test programs may abort because they require general spilling (see below). Convince yourself that the programs resulting from a successful run of your compiler don't fail when simulated in SPIM.
5. As time permits, implement general spilling.
6. Submit README and all source files necessary for successfully building your entire compiler (including the files provided by us), in gzipped form to dropbox here. Optionally, submit additional test programs as file mytests.gz - this should expand to a subdirectory "mystests" that contains source .fun programs. Use descriptive file names and add a description at the top of each file which specifies the intended behaviour. In the README, highlight which test cases of your test suite are successfully compiled. In case your compiler does not pass a test, include a problem description. Also indicate in README which files you actually modified (codegen, liveness,...) and why.
   

   Ideally, if all your modules are working properly, your regalloc.sml will be 100% compatible with the grader's reference version of the other modules. However, just in case there's some quirk in your code generator or register allocator that makes it incompatible, submit everything.

Spilling - simple version

In the simple version of spilling, you assume that any temporary that gets spilled appears only in Move instructions, never in any other instructions; and you assume that no Move has spilled temporaries for its source and destination. These assumptions don't always hold, but they hold often enough to compile a few Fun programs.

So here's what you have to do:

• In RegAlloc.alloc, count up the number n of spilled temporaries.
• At the beginning of the function's prolog, just before the first instruction of the first block, insert an instruction to subtract n*wordSize from the stack pointer.
• Assign offsets (0,1,2, etc.) to the spilled temporaries
• Traverse all the instructions of all the blocks of the function. For each instruction, if all its uses and defs have been assigned colors (have not spilled), use Mips.rename_regs to rewrite it to use the real registers specified by alloc.
• In this traversal, wherever there is a Move whose destination is a spilled temporary, convert it into a Sw instruction with the appropriate offset from the stack pointer. Wherever there is a Move whose source is a spilled temporary, convert it into a Lw instruction with the appropriate offset from the stack pointer.
• For any non-Move instruction whose uses and defs are not all mapped by the alloc function, simple spilling has failed. Call ErrorMsg.impossible.
• Just after function.epilog label, insert an instruction to add n*wordSize to the stack pointer.

General spilling

1. Take two registers [x,y] away from the palette that Color.color uses. Now, whenever you find a nonmove instruction that uses a spilled temporary, precede it with a load instruction that loads the spilled temporary into x or y. Whenever a nonmove instruction defs a spilled temporary, have it def x instead and follow it with a store instruction that stores x.
   

   You need two registers just in case you find an instruction that uses two spilled temporaries as its sources.

   Whenever you find a move instruction that moves one spilled temporary into another, replace it by load x, store x.

2. The other way to do it is this: Do not take any colors away from the palette. Either simple spilling works (in which case use it); or there are some nonsimple spills. Rewrite the program so that whenever there is an instruction such as c:=a+b that uses spilled temporaries, make up new temporaries ta,tb,tc and replace the instruction with ta:=a; tb:=b; tc:=ta+tb; c:=tc. Mark ta,tb,tc as must-not-spill by setting their spillCost to spillCostInfinity. (In this rewriting, do not rename any temporaries into real registers; just address the spills.) Then call the coloring algorithm again with the new register-allocation problem.

Optional: improved instruction selection

As you review the assembly code that comes out of your compiler, you may notice several respects in which the code looks suboptimal. The high-tech way to fix this is by appropriate back-end optimizations. For example, all the extra move instructions should be eliminated by register coalescing, and other kinds of optimizations should be done by algorithms described in Chapters 17 and 18 of the textbook. If your compiler doesn't have those optimization phases, a cheap substitute is to add extra patterns to your codegen module. Once you have general spilling working you may want to do this (or implement other optimizations), as time permits.