Re: Graph coloring for register allocation?

[Michael Matz <matzmich at cs dot tu-berlin dot de>]

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).  
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), and to take
the machine architecture into account. Of course it wasn't of much help,
that I'm more a middle-end guy ;-)

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


Ciao,
Michael.