[LLVMdev] Regalloc Refactoring

[Evan Cheng]

On Apr 16, 2007, at 1:17 PM, David Greene 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.
>
> 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.

These are "implementation details". They don't necessarily make good  
paper material. :-)

Obviously, smart heuristics can make a big difference here (estimated  
register pressures, etc.) But the more important thing is how the  
passes down stream can recover from the earlier mistakes. By this, we  
mean live range splitting and re-materialization. Unfortunately,  
neither of these are feasible given the current infrastructure. Chris  
and I have been discussing a rewrite informally, but no formal plan  
has been materialized.

Evan

>
>                                 -Dave
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev