[LLVMdev] Register Allocation by Graph Coloring

[David Greene]

On Tuesday 04 March 2008 02:24, Prabhat Kumar Saraswat wrote:
> 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
> task.

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.

                                                  -Dave