Graph coloring for register allocation?

[Michael Matz]

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

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

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

Yep, and probably much (though not all) of reload*.c. 


Ciao,
Michael.