COS 320, Spring 2005. Programming Assignment 8

Programming Assignment 8: Register Allocation


1) Copy /u/cos320/chap8/* into a new directory as7 using the command:

cp -r /u/cos320/chap8/* SOMEWHERE-IN-YOUR-HOME/as7


This assignment is based on chapter 11 pages 253-254 of your textbook. Please read chapter 11 before starting.  The objective of this assignment is to fill in the color function in color.sml.  You only have to implement the simplify and coloring stages of register allocation as described in chapter 11.1.

The color function returns the allocation (a table that maps temporaries to real registers), the list of spilled temporaries (a list of virtual registers that could not be assigned a real register and must be spilled), and the list of MIPS callee saved registers that you needed to use (the complete set of callee saved registers is contained in Mips.calleeSaved, found in mips.sig). The list of callee saved regs are needed so that the RegAlloc module can generate correct code to save and restore callee saved regs for functions. During register allocation, DO NOT use special purpose registers $zero, $at, $gp, $sp, Mips.spillReg1, Mips.spillReg2, and Mips.heapReg during register allocation. Mips.heapReg is reserved for heap allocation; Mips.spillReg1 and Mips.spillReg2 are reserved for load and store spilled temporaries from the memory.


To submit, go to and type

submit 8 color.sml README

The README should list your collaborators and explain any unusual assumptions or decisions you have made.