Re: Graph coloring for register allocation?

[Daniel Berlin <dberlin at redhat dot com>]

On Thu, 18 Jan 2001, Michael Matz wrote:

> Hi,
>
> On Wed, 17 Jan 2001, Daniel Berlin wrote:
> >
> > I've been working on, besides the SSA value numbering stuff (which works
> > nicely, I'm just putting the finishing touches on it before contributing.
> > Probably be a few weeks. ), an register allocator that also does live range
> > splitting. It's based on optimistic register coalescing
> > (http://citeseer.nj.nec.com/park98optimistic.html).
> > This is, from what I understand, pretty close to state of the art, if not
> > there already.
> >
> > I started this morning during first day of class classes, and finished and
> > tested the routine to build the interference graph.
> >
> > It'll probably be months for me to finish the register allocator, and it
> > would be nice to have some help.
>
> I too was planning to write a register allocator. And guess what, after
> reading probably all modern freely available papers on that topic I also
> wanted to take Park's approach (optimistic Coloring and Coalescing).

Great minds read the same papers, or something like that.
> While the algorithmic dimension is no problem, I was a little bit slowed
> down by gcc's RTL, and how to parse it correctly for conflicts (to not
> overconstrain the graph, but also to not forget conflicts),

This was actually the largest pain in the ass for generating the
interference graph. I stole two routines from combine.c and modified them
(they tell you whether a register is live after a certain insn).

I've verified the interference graph matches what the normal register
allocator believes as well.
>  and to  take
> the machine architecture into account.

This is something i was planning on worrying about after the the
implementation was far along. For the case ofinsns that will take up >1
register, it's already handled when building the interference graph.
 I  figured there are actually a billion
ways to handle the case of things like floating point calculations using
fp registers.  For instance, for some architectures (or maybe all
of them , it's hard to say), It might pay to just allocate the registers
in seperate passes (IE run the algorithm for the integer operations, then
the fp operations) . SML/NJ does this. It's not that particularly
difficult, since we know the modes of the instructions, and thus, what
kind of registers they need.
> Of  course it wasn't of much help,
> that I'm more a middle-end guy ;-)

Same here.
>
> To make it short, I would very much love to help with this.
>

Let me figure out the best way to do this (IE a branch on gcc cvs, or a
seperate cvs server, which i already have).
>
> Ciao,
> Michael.
>
>