[LLVMdev] Regalloc Refactoring

[David Greene]

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.

On, say, the x86 machines, the cost of a spill is really not much
different from the cost of a copy so it's probably close to a wash in
the end.  But there are many machines where the cost of each operation
is vastly different.  Aggressive coalescing is not always good.  Often
you'd rather copy than spill.

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

This is one of the reasons I want to separate all of these concerns.
We shouldn't force developers to always coalesce or always use some
generic measure of spill cost.

                                -Dave