Graph coloring for register allocation?

[Daniel Berlin]

On Tue, 23 Jan 2001, Michael Matz wrote:

> Hi,
>
> On Sun, 21 Jan 2001, Daniel Berlin wrote:
> > > Yep, I have them, but not looked at them closely due to missing time.
> > > Also, meanwhile I was playing with the thought of building the
> > > interference graph incrementally (as proposed in one of the newer
> > > articles), and for that u/d-d/u-chains are not the best source. But at
> > > least for gathering the info your routines seem very handy.
> > What papers show how to build it incrementally?
> > I couldn't find any.
>
> Well, not incrementally, but sparse construction which can be more easily
> extended for incremental updates (it only needs all def/use site of a
> variable, no global information, and no incremental update of local
> liveness per basic block). It's from the MLRISC guys in their new register
> allocator: http://cm.bell-labs.com/cm/cs/what/smlnj/compiler-notes/new-ra.ps

Ahhh.
I constantly look at the MLRISC stuff, since they always seem to have the
latest optimizations and whatnot implemented.

>
> > Because there are so many implementations available, i've started with
> > Iterated Register Coalescing, and will convert it to optimistic when it's
> > done.
> > Works well so far.
>
> Cool. Any code, CVS branches or similar stuff?

I have code, and after classes today, i should be finished with another
phase of allocation.

I'll ask about a cvs branch then.

>
> > Just so we are all on the same page, everyone realizes that the new
> > register allocator will replace the regmove, the local-alloc, and the
> > global-alloc passes, right?
>

--Dan