Graph Coloring Regalloc

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Graph Coloring Regalloc

greened
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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

greened
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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

Anton Vayvod
In reply to this post by greened
On 4/3/07, David Greene <[hidden email]> 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.

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: 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 <[hidden email]> 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.
>
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

greened
Fernando Magno Quintao Pereira wrote:

>      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.

I'm interested in this algorithm as well.  When you get it ported to
LLVM's data structures, will you be adding it to the source tree?

                                 -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

Bill Wendling
In reply to this post by greened
On 4/3/07, David Greene <[hidden email]> 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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

Bill Wendling
On 4/3/07, Bill Wendling <[hidden email]> wrote:

> On 4/3/07, David Greene <[hidden email]> 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.
>
And, yes, I used Chow & Hennessey's algorithm. It's copyright free :-)

-bw
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

Leo Romanoff
In reply to this post by Anton Vayvod
Hi,


--- Anton Vayvod <[hidden email]> wrote:

> On 4/3/07, David Greene <[hidden email]> 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/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

greened
Roman Levenstein wrote:

> 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.

Are you saying the SUIF allocator implements the Smith/Ramsey/Holloway
algorithm, or something different?

                                  -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

Leo Romanoff

--- David Greene <[hidden email]> wrote:

> Roman Levenstein wrote:
> > 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.
>
> Are you saying the SUIF allocator implements the
> Smith/Ramsey/Holloway algorithm, or something different?

Yes, the SUIF allocator (or at least one of them) implements the
Smith/Ramsey/Holloway algorithm. This is what I understand by looking
at the coloring reggister allocator code in the SUIF distribution. The
SUIF code of this allocator is not very well commented, but I'm pretty
sure.

Roman


 
____________________________________________________________________________________
8:00? 8:25? 8:40? Find a flick in no time
with the Yahoo! Search movie showtime shortcut.
http://tools.search.yahoo.com/shortcuts/#news
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

greened
Roman Levenstein wrote:

> Yes, the SUIF allocator (or at least one of them) implements the
> Smith/Ramsey/Holloway algorithm. This is what I understand by looking
> at the coloring reggister allocator code in the SUIF distribution. The
> SUIF code of this allocator is not very well commented, but I'm pretty
> sure.

Do you have a pointer?  I'm interested in this algorithm as well.

                                 -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

Leo Romanoff
Hi Dave,

--- David Greene <[hidden email]> wrote:

> Roman Levenstein wrote:
>
> > Yes, the SUIF allocator (or at least one of them) implements the
> > Smith/Ramsey/Holloway algorithm. This is what I understand by
> looking
> > at the coloring reggister allocator code in the SUIF distribution.
> The
> > SUIF code of this allocator is not very well commented, but I'm
> pretty
> > sure.
>
> Do you have a pointer?  I'm interested in this algorithm as well.

I downloaded the MachSUIF sources from here:
http://www.eecs.harvard.edu/hube/software/software.html

More precisely, I took this version: 2.02.07.15

Have a look at the color.cpp in the raga subdirectory. This is the
implementation of Smith/Ramsey/Holloway algorithm, as far as I
understand.

-Roman




 
____________________________________________________________________________________
Never miss an email again!
Yahoo! Toolbar alerts you the instant new Mail arrives.
http://tools.search.yahoo.com/toolbar/features/mail/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

Lang Hames
Hi David,

I'm currently working on an implementation of the
Smith/Ramsey/Holloway algorithm for LLVM 1.9, to use for comparison
with a PBQP based allocator I'm also writing.

The allocator is almost complete, however it's a little messy (since
it was only for personal use) and only supports X86 at the moment. It
might me handy as a reference for you though.

Let me know if you want a copy of the code.

Cheers,
Lang.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

Domagoj Babic
Hi,

I'm not very familiar with the code generation, but this seems like a
good opportunity to ask...

Has anyone tried optimal graph coloring algorithms? Yeah, it's NP,
but the chances are that you are not looking at that many variables
at the same time. I'm wondering how much could one improve the
register allocation by using optimal algorithms, and how much impact
would that have on the speed of the produced native code?

Thx,
   Domagoj Babic
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Graph Coloring Regalloc

Chris Lattner
On Wed, 4 Apr 2007, Domagoj Babic wrote:
> Has anyone tried optimal graph coloring algorithms? Yeah, it's NP,
> but the chances are that you are not looking at that many variables
> at the same time. I'm wondering how much could one improve the
> register allocation by using optimal algorithms, and how much impact
> would that have on the speed of the produced native code?

<soapbox>

IMO, coloring the graph / assigning the registeres isn't the hard part.
The hard part of doing a decent job of register allocation is handling
things like: folding spill code into instructions, handling register
coallescing, splitting live ranges, doing rematerialization, doing shrink
wrapping, etc.

This opinion is largely "colored" (haha) by experience with ISAs that have
few registers.  If you are targeting itanium, you have a whole different
set of issues.

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev