Re: Graph coloring for register allocation?

[Daniel Berlin <dberlin at redhat dot com>]

On 1/17/01 8:48 PM, "dewar@gnat.com" <dewar@gnat.com> wrote:

> Well there is loads of work on register allocation and scheduling
> since the publication of the IBM algorithm, so I don't think anyone
> would use this unchanged. There are many variations on this theme
> which certainly are NOT patented (even a small variation on a patent
> tends to escape the patenting in the software field).
> 
> So rather than ask whether we want to use the IBM patented algorithn
> at this stage, I think the appropriate thing is to survey the current
> state of the art and ask whether we could be doing better using whatever
> algorithms and methods are available.
> 

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.

--Dan