COS 320, Spring 2000. Programming Assignment

Programming Assignment 8: Register Allocation

Note: For this project, you must run sml and gcc on the sparc machines such as arizona.  This isn't as bad as it sounds. Map your OIT account space as a drive on your home computer (see You can now edit OIT files on your home computer as if they were local.


1) Copy /u/cos320/proj8/* into a new directory proj8.

2) Untar CM.tar into the directory proj8.


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 "..." holes in color.sml.  You only have to implement the simplify and coloring stages of register allocation.

Extra Credit:  Implement move coalescing.

Extra, Extra Credit:  Implement spilling.


You will have to devise testing mechanisms for register allocation yourself.

To test the completed project:

1) Run Main.compile "filename.tig";  This will generate a "filename.tig.s" assembly file.

2) Run "gcc runtime.c filename.tig.s" on arizona;  This will generate an "a.out" binary file.

3) Run the a.out binary file.


You must submit the file "canon.sml" and a brief README explaining any unusual assumptions or decisions you have made.

Please test your code with at least queens.tig, merge.tig, and merge-sort.tig.