[LLVMdev] Pluggable Register Coalescers

[David Greene]

On Monday 09 July 2007 17:07, David Greene wrote:
> On Monday 09 July 2007 16:49, Reid Spencer wrote:
> > The only thing that comes to mind is that creating and running the
> > coalescer are separate operations so you might want to do the creation
> > of it in alias analysis style. Then, the allocator can a) determine if a
> > coalescer was created, b) obtain the coalescer that was created, if any,
> > and c) run it at the right time for the allocator's algorithm, or even
> > not at all.
>
> 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.

Does this sound like a reasonable plan?  I want to keep the infrastructure as
flexible as possible, to allow multiple implementations that can be chosen at
run-time.  But the interfaces need to be specific enough to be useful for more
powerful algorithms.

Discuss away!

                                                  -Dave