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

Ok, I'm at a point now where I can implement plyggable register coalescers
as
we originally wanted when I started the refactoring work.

I'm in the midst of finishing up an implementation following the model of
how
register allocators are selected.  Thgere may be some more refactoring/code
sharing work to be done with this, but I want to get it working first.

createRegisterAllocator() is called by addPassesToEmit.* to instantiate the
register allocator.

Coalescing is a bit different.  Typically, the register allocator is the 
client of the coalescer.  My original thought was to have each register
allocator implementation call createRegisterCoalescer directly.  I then
thought it might be better to have allocators just declare they want a 
coalescer run and let someone else decide how to do it, similarly to
how the alias analysis group works.

But that's not quite right either, because it isn't possible in general
to
state that coalescing should run "before" register allocation.  Often
you
want to run it in the middle of the algorithm, and maybe more than once.

So now I'm back to the original thought of just having the allocators
call createRegisterCoalescer directly.  Does this sound like the right
solution?  Are there other ideas?

Are there times one might run register coalescing completely outside of
register allocation?  Again, in general, not all coalescers will be able to do
that (the classic case being a coalescer that works off an interference 
graph).

                                            -Dave

Hi David,

On Mon, 2007-07-09 at 16:32 -0500, David Greene wrote:
> Ok, I'm at a point now where I can implement plyggable register
coalescers as
> we originally wanted when I started the refactoring work.
> 
> I'm in the midst of finishing up an implementation following the model
of how
> register allocators are selected.  Thgere may be some more refactoring/code
> sharing work to be done with this, but I want to get it working first.
> 
> createRegisterAllocator() is called by addPassesToEmit.* to instantiate the
> register allocator.
> 
> Coalescing is a bit different.  Typically, the register allocator is the 
> client of the coalescer.  My original thought was to have each register
> allocator implementation call createRegisterCoalescer directly.  I then
> thought it might be better to have allocators just declare they want a 
> coalescer run and let someone else decide how to do it, similarly to
> how the alias analysis group works.
> 
> But that's not quite right either, because it isn't possible in
general to
> state that coalescing should run "before" register allocation. 
Often you
> want to run it in the middle of the algorithm, and maybe more than once.
> 
> So now I'm back to the original thought of just having the allocators
> call createRegisterCoalescer directly.  Does this sound like the right
> solution?  Are there other ideas?
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.
> Are there times one might run register coalescing completely outside of
> register allocation?  Again, in general, not all coalescers will be able to
do
> that (the classic case being a coalescer that works off an interference 
> graph).
> 
>                                             -Dave
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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.

                                            -Dave