Register Allocation by Graph Coloring

Dear all,
I was looking for to compile some benchmarks and generate code using
different register allocation algorithms. As i can see, the built in
options for register allocation in llvm are
1. Simple
2. Local
3. Linear Scan

I want to compare the generating code also with a graph coloring based
register allocation approach. Is this also built in by default by
llvm. Are there some other projects, whose code i can borrow for this

To summarize: I want to compare the generated code of various
benchmarks (generated using linear scan based reg allocation vs graph
based register allocation).

Any suggestions would be helpful.


There have been several people working on projects like this, including me.
Unfortunately, I am not able to contribute my code. But Bill Wendling posted
an (incomplete) implementation of priority-based graph coloring some time
ago. You can check the list archives (Google is your friend here).

If you are doing this as part of a research project leading to publication, be
very careful about how you specify things. Every single register allocation
paper I've ever read is woefully incomplete when it comes to specifying
exactly what the allocator does. Even the papers by Briggs and Chaiten
contradict themselves when you examine the text of the paper vs. the
pseudocode provided.

There are lots of variables and heuristics. Be very skeptical about any
performance data you come across. I have seen swings of 20% or more
in performance based on assumptions about heuristics and various
enhancements to the algorithms.


Hi, Prabhat,

     I have the implementation of a register allocator at Register Allocation by Puzzle Solving
     It is not graph-based, but if you want to use it, I would be happy to help you to install. It is working for LLVM 2.1.