COS 320 - Assignment 9

Compiling Techniques, Spring 2012, Princeton University.      Due date: Monday 23 April.

Graph-Coloring Register Allocation

Implement the coloring part of a graph-coloring register allocator, using the Kempe / Chaitin algorithm.
  1. Make a new directory as9, copy all your files from as8, and unpack as9.zip. The new files are regalloc.sml, color.sig, and color.sml.
  2. In color.sml, implement verify.
  3. In color.sml, implement color.
  4. Debug by running Compile.compile "whatever.fun". The output file whatever.fun.s will be not-quite-working MIPS code; many of the temporaries will have been allocated to real registers, but the spilled temporaries will still be "$x" pseudoregisters.
  5. Submit README and color.sml to dropbox here.

Verification

Your verify function should check that the coloring satisfies all the constraints:
  1. alloc(t) is always in the "palette" of colors permitted.
  2. Every virtual (nonprecolored) register mentioned in the func is either in the alloc or in the spills.
  3. No precolored register is in the alloc or in the spills.
  4. No two registers that interfere (whether they are precolored or virtual) have the same color. The "color" (if any) of a virtual register is its alloc. The "color" of a precolored register is itself.
  5. No spilled register has spillCost >= spillCostInfinity.
The way to do this is to define a "mention" function and an "interfere" function, then call upon Liveness.analyze. That will call your "mention" and "interfere" which can check all the properties listed.

If you find a violation, just call ErrorMsg.impossible with an appropriately informative string. The more informative the better, because this will help you debug your coloring algorithm!

Coloring

Implement graph coloring without coalescing. You will completely ignore the moves parameter of the color function.

The use of the RegSet module makes it very easy to deal with sets of registers. This means you can have an elegant and natural implementation of the algorithm described in Section 11.1 of the textbook.

The heart of your algorithm can be a function like this, 

fun f (lowdegs: RS.set, highdegs: RS.set) : coloring
where lowdegs is the set of nonprecolored registers still in the interference graph that have degree <K, and highdegs is the set of nonprecolored registers still in the interference graph that have degree ≥K. (K is the number of colors in the palette.)

If lowdegs is not empty, apply the Simplify heuristic described on page 229 of the textbook. Instead of "push on a stack", just do a recursive call to the function f. (By the way, choose a better name than f!)

If lowdegs is empty and highdegs is not empty, apply the Spill heuristic described on page 229 of the textbook. Spill the node with the lowest spill cost. Again, instead of "push on a stack" just do a recursive call.

Take into account that Simplify and Spill both modify the degree of existing nodes when making the recursive call.

If both are empty, then return from f and, on the way back out of the deep recursion, colors will be assigned.

DO NOT implement coalescing heuristics. That's another (optional) programming assignment entirely; save your ingenuity for that one.

Back to COS 320 front page