[LLVMdev] Graph Coloring Regalloc
Fernando Magno Quintao Pereira
fernando at CS.UCLA.EDU
Tue Apr 3 10:34:11 PDT 2007
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.
> 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?
> 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!
More information about the llvm-dev