Implement the graph coloring. The skeleton we provided is an exact copy of the implementation of the code suggest 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 on the algorithm, they reported on his web page (see Modern Compiler Implementation); be sure to fix your books.
Pay attention to
misc::set: there is a lot of syntactic sugar
provided to implement set operations. The code of
range from ugly and obfuscated to readable and very close to its
Run the register allocation on each code fragment. Remove the useless moves.
If your compiler supports spills, implement