llvm dev - Jul 2007 - [LLVMdev] Pluggable Register Coalescers

Hi all,

Tanya and Reid's ideas are very good. I think we want to go towards  
pluggable register coalescers. That said, I don't think the longer  
term plan to stop short term progress. To me, it's totally acceptable  
for the allocator to directly call the coalescers at this point. I  
would love to see a smarter coalescer. That's something we can use  
today! :-)

Thanks,

Evan

On Jul 11, 2007, at 10:41 AM, Tanya M. Lattner wrote:
>
>>> Ok, that sounds like a good plan.  I'll brush up on how alias  
>>> analysis
>>> works and work from there.
>>
>> I've been looking at this and it's become clear to me that we
need
>> some kind
>> of abstract coalescing interface similar to what the AliasAnalysis  
>> class
>> provides.  I think we need the same thing for register allocators.
>>
>> LLVM's existing coalescer is very simple.  It just goes and  
>> replaces every
>> copy it can.  In general, a coalescer will want to query the register
>> allocator about which copies it should remove.  For example,
Briggs'
>> conservative coalescer will not remove copies that could  
>> potentially cause
>> spills.  Only the register allocator has the information to make that
>> decision.
>> A coalescing interface needs to provide hooks for the register  
>> allocator to
>> invoke it potentially multiple times with a potentially restricted  
>> scope.  The
>> register allocator needs to provide an interface for the coalescer  
>> to ask
>> questions like, "is this copy here to split live ranges?"
and, "will
>> coalescing this copy potentially cause a spill?"
>>
>> AI think all this will require is new RegisterCoalescer and  
>> RegisterAllocator
>> interface classes that can be multiply-inherited (with   
>> MachineFunctionPass)
>> by the various implementations.
>>
>> It's not totally clear to me whether coalescers should even  
>> inherit from
>> MachineFunctionPass as they are really invoked by the register  
>> allocator,
>> not PassManager.  But then again, I can imagine some coalescers  
>> (like the
>> existing one) being independent enough to run on their own at any  
>> time.
>> Opinions on this are welcome.
>
> I think the coalescer should be flexible enough to be run  
> independent of
> the register allocator. For example, you may want to expose the copies
> induced by transforming out of SSA to the scheduler. If the  
> scheduler is
> run before register allocation, then you would want the coalescing to
> happen before as well.
>
> -Tanya
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

>> Ok, that sounds like a good plan.  I'll brush up on how alias
analysis
>> works and work from there.
>
> I've been looking at this and it's become clear to me that we need
some kind
> of abstract coalescing interface similar to what the AliasAnalysis class
> provides.  I think we need the same thing for register allocators.
>
> LLVM's existing coalescer is very simple.  It just goes and replaces
every
> copy it can.  In general, a coalescer will want to query the register
> allocator about which copies it should remove.  For example, Briggs'
> conservative coalescer will not remove copies that could potentially cause
> spills.  Only the register allocator has the information to make that
> decision.
> A coalescing interface needs to provide hooks for the register allocator to
> invoke it potentially multiple times with a potentially restricted scope. 
The
> register allocator needs to provide an interface for the coalescer to ask
> questions like, "is this copy here to split live ranges?" and,
"will
> coalescing this copy potentially cause a spill?"
>
> AI think all this will require is new RegisterCoalescer and
RegisterAllocator
> interface classes that can be multiply-inherited (with 
MachineFunctionPass)
> by the various implementations.
>
> It's not totally clear to me whether coalescers should even inherit
from
> MachineFunctionPass as they are really invoked by the register allocator,
> not PassManager.  But then again, I can imagine some coalescers (like the
> existing one) being independent enough to run on their own at any time.
> Opinions on this are welcome.
I think the coalescer should be flexible enough to be run independent of 
the register allocator. For example, you may want to expose the copies 
induced by transforming out of SSA to the scheduler. If the scheduler is 
run before register allocation, then you would want the coalescing to 
happen before as well.

-Tanya

On Wednesday 11 July 2007 12:41, Tanya M. Lattner wrote:
> I think the coalescer should be flexible enough to be run independent of
> the register allocator. For example, you may want to expose the copies
> induced by transforming out of SSA to the scheduler. If the scheduler is
> run before register allocation, then you would want the coalescing to
> happen before as well.
I agree that we want to allow for this possibility, but there are some
coalescers that cannot run independent of the register allocator.
So how do we handle both?  If I as a user ask for a regalloc-dependent
coalescer, what should it do if someone tries to run it as an independent
pass?

It could provide a fallback, perhaps invoking the existing coalescer,
but that would cause coalescing the user might not want.

It could do nothing and count on the register allocator to run it at some
point, but not all register allocators will necessarily run a coalescing pass.

I agree with Evan that we don't want to strangle short-term gain, but these
are the kinds of questions we should keep in mind as we design interfaces.
Interfaces can always change later, of course, but it's good to get them as
right as possible initially.

                                                  -Dave

On Jul 11, 2007, at 11:39 AM, David Greene wrote:
> On Wednesday 11 July 2007 12:41, Tanya M. Lattner wrote:
>
>> I think the coalescer should be flexible enough to be run  
>> independent of
>> the register allocator. For example, you may want to expose the  
>> copies
>> induced by transforming out of SSA to the scheduler. If the  
>> scheduler is
>> run before register allocation, then you would want the coalescing to
>> happen before as well.
>
> I agree that we want to allow for this possibility, but there are some
> coalescers that cannot run independent of the register allocator.
> So how do we handle both?  If I as a user ask for a regalloc-dependent
> coalescer, what should it do if someone tries to run it as an  
> independent
> pass?
Could it be possible for there to be a harness type interface that  
would allow coalescers that support both modes to be hooked into the  
pass registration, and those that depend on the allocator not be  
registered as passes?

--
Christopher Lamb



-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20070711/a431ebe3/attachment.html>