[LLVMdev] Graph Coloring Regalloc

[Roman Levenstein]

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/