[LLVMdev] Regalloc Refactoring

[Daniel Berlin]

On 4/16/07, David Greene <greened at obbligato.org> wrote:
> Chris Lattner wrote:
> > On Thu, 12 Apr 2007, Fernando Magno Quintao Pereira wrote:
> >>> I'm definitely interested in improving coalescing and it sounds like
> >>> this would fall under that work.  Do you have references to papers
> >>> that talk about the various algorithms?
> >> Some suggestions:
> >>
> >> @InProceedings{Budimlic02,
> >>   AUTHOR     = {Zoran Budimlic and Keith D. Cooper and Timothy J. Harvey
> >> and Ken Kennedy and Timothy S. Oberg and Steven W. Reeves},
> >>   YEAR       = "2002",
> >>   TITLE      = "Fast copy coalescing and live-range identification",
> >
> > Yep, this is the one I was thinking of.  It is available online here:
> > http://www.cs.rice.edu/~keith/LACSI/pldi02.pdf
>
> I was just looking at this today.  One thing that strikes me about
> all these papers I've read on the topic is that no one seems to
> consider the interaction of coalescing with spilling.
>   By definition
> coalescing increases lifetimes and can cause more interferences.
> Yet the papers all try to coalesce as many copies as possible.

Most papers I read these days try to coalesce anything that won't
cause spills.  Some of these apparoaches are to coalesce everything,
then undo as necessary to avoid spills, etc.

But certainly, I don't believe recent papers in the area of coalescing
ignore spill costs.

>
> Is anyone aware of publications addressing the interplay among
> coalescing, live range splitting, register allocation and spilling?

Yes, they are around, i'll dig them out of my pdfs :)