[LLVMdev] Graph Coloring Regalloc

[Fernando Magno Quintao Pereira]

Hey, Anton,

     yes, I have an implementation of a register allocator for LLVM. I 
Don't build the interference graph though. I perform a linear scan on the 
dominator tree. The difference from my algorithm to LLVM's linear scan is 
that I perform register allocation before the SSA-elimination step. I have 
it working, but did not commit, because I did not implement it using 
LLVM's data structures. Instead, I dump the data, run my register 
allocator, and map it back into the VirtRegMap class, that will produce 
the executable code. Currently I can compile almost all the tests in the 
LLVM suite, and SPEC2000.
     I have a tech-report that I can send to you. Also, I can send the 
whole implementation. I am in the process of writing it on LLVM.

Fernando

> On 4/3/07, David Greene <greened at obbligato.org> wrote:
>> 
>> I'm just starting to dive into llvm, hoping to implement a
>> good graph coloring register allocator.  I gather that this
>> has been discussed before.
>> 
>> What is the RegAllocGraphColoring.cpp currently in the
>> sources?  It seems to be the Fred Chow algorithm but
>> it's not mentioned in the documentation anywhere.  Does
>> it work?
>
>
> Hi!
>
> I work on implementing of optimistic graph coloring algorithm (by Preston
> Briggs) for LLVM. I didn't mentioned it on this list directly though.
> Currently, my implementation is in the testing state. Probably I'll try
> commit it before the 2.0 release. However, my progress on this work is very
> unstable and the main goal of implementing the algorithm is my diploma.
>
> Register allocation via coloring of chordal graphs was also developed within
> LLVM by someone (Fernando Magno Quintao Pereira if I remember well), AFAIK,
> but I don't know whether he wants to commit his implementation. Probably,
> he'll answer you, too :)
>
> I've just downloaded llvm from cvs. And didn't find any
> RegAllocGraphColoring.cpp here. Could you give me a link to it as I'm
> interested in this, too?
>
> Best regards!
>
> Anton.
>