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?
-Dave
David Greene wrote:> 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?Ah, ok. One of our folks here grabbed it off the mailing list and put it in our local repository. Still, what's the status of this thing? -Dave
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. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070403/355a7c67/attachment.html>
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.
>
On 4/3/07, David Greene <greened at obbligato.org> wrote:> David Greene wrote: > > > 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? > > Ah, ok. One of our folks here grabbed it off the mailing > list and put it in our local repository. > > Still, what's the status of this thing? >The status is currently in limbo. I got some feedback from Evan on it and am in the middle of converting it to use better data structures. But haven't really had time to work on it. If you want to, please take it and see what you can do with it. It should work for the testsuite at least. -bw
Hi, --- Anton Vayvod <avayvod at gmail.com> wrote:> 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?The graph-coloring allocator was commited by Bill Wendling in this message on the llvm-commit mailing list: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20061113/039959.html The allocator does not handle register aliases and register classes correctly, which makes it rather unusable for most architectures. One idea that can be used for improving handling of irregular architectures is described in the "A Generalized Algorithm for Graph-Coloring Register Allocation" by Michael D. Smith, Norman Ramsey and Glenn Holloway: http://www.eecs.harvard.edu/~nr/pubs/gcra-abstract.html There exists also an implementation of the algorithm described in the paper for the SUIF compiler suite. I was planning to port it to LLVM, but a bit later. At the moment I'm working on the implementation of a linear scan register allocator based on the Wimmer's paper "Linear Scan Register Allocation for the Java HotSpot Client Compiler": http://www.ssw.uni-linz.ac.at/Research/Papers/Wimmer04Master/ This is a rather optimized version of a linear scan which is really used in Sun's HotSpot JVM. The difference of this version of the linear scan from the LLVM's linear scan implementation is that Wimmer's algorithm uses live interval splitting to achieve better allocation. Currently, I have a working version that e.g. compiles many tests for X86 target without errors. But proper testing is required of course. It is also not quite clear yet if it bring any measurable performance improvements. I'm going to contribute the code to LLVM rather soon, once I have cleaned up the code. Best regards, Roman ____________________________________________________________________________________ Looking for earth-friendly autos? Browse Top Cars by "Green Rating" at Yahoo! Autos' Green Center. http://autos.yahoo.com/green_center/