Re: Graph coloring for register allocation?

[Daniel Berlin <dberlin at redhat dot com>]

On Sun, 21 Jan 2001, Michael Matz wrote:

> Hi,
>
> On Sat, 20 Jan 2001, Michael Hayes wrote:
> >  > 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 posted some generic dataflow routines that I posted to this list a
> > few weeks ago that could help with this.  As well as liveness info,
> > they generate def-use and use-def
>
> 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.

As for the handiness, Yes, definitely.

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.

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?


 > > > info from which you can generate webs from.
>
> Ahh, a Muchnick reader?  ;-) I found nowhere else (IIRC) the term "web"
> for what is called everywhere else live range. Although I also like more
> the former one ;)
>
>
> Ciao,
> Michael.
>
>