TC-9 Code to Write


Implement the graph coloring. The skeleton we provided is an exact copy of the implementation of the code suggested by Andrew Appel in the section 11.4 “Graph Coloring Implementation” of his book. A lot of comments that are verbatim copies of his comments are left in the code. Unfortunately, the books have several nasty mistakes in the algorithms, they are reported on his web page (Errata: Modern Compiler Implementation in ML); be sure to fix your books. For additionnal information about the books and some mistakes that were forgotten on his web page, be sure to check Modern Compiler Implementation.

Pay attention to misc::set: there is a lot of syntactic sugar provided to implement set operations. The code of Color can range from ugly and obfuscated to readable and very close to its specification.


Run the register allocation on each code fragment. Remove the useless moves.


If your compiler supports spills, implement Codegen::rewrite_program.