llvm dev - Mar 2008 - [LLVMdev] 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
task.

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.

Regards
Prabhat

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

Hi, Prabhat,

     I have the implementation of a register allocator at 
http://compilers.cs.ucla.edu/fernando/projects/puzzles
     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.

best,

Fernando
> 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.
>
> 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.
>
> Regards
> Prabhat
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>