4.18.4 TC-9 Code to Write

src/regalloc/color.hh

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 Color can range from ugly and obfuscated to readable and very close to its specification.

src/regalloc/regallocator.cc

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

src/target/mips/epilogue.cc

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