[LLVMdev] [PATCH] Re: Pluggable Register Coalescers

[David A. Greene]

On Tuesday 17 July 2007 14:21, David Greene wrote:

> > I don't care for a MachineFunctionPass that can be directly called. I
> > think it's a very good idea to keep the coalescers independent from
> > the allocators. If that's desired, we should enhance passmanager so
> > each allocator can run some sub-passes as part of the allocation
> > pass.
>
> I agree that this is a good long-term goal.  Unfortunately, I don't have
> the time resources to implement it right now.  If someone else can take up
> this as a sub-project, that would be great!  I agree that several other
> passes could make use of it.

I've got something in the works that provides an interface for the coalescer
to query an interference object.  So the RegisterAllocator class no longer
exists and coalescers don't directly depend on register allocators.  As a
bonus, the interference interface doesn't make any assumptions about
the underlying representation but has the interfaces necessary to make
equivalent queries to what a coalescer might ask an interference graph.

As a proof of concept, I have an example of what the linear scan algorithm
might provide.  It's very inefficient and in practice linear scan probably 
won't ever interact with a coalescer that partners with the allocator but
it serves to show that the interface can be met by something that doesn't
use a graph.

I've also implemented a graph-based realization using what I currently have,
but as I said in another message, I'm not at liberty to release that publicly.
It's pretty straightforward code, though.

The RegisterCoalescer interface still exists because register allocators need
to be able to invoke the coalescer, sometimes repeatedly.  PassManager can't 
do that.  The current SimpleRegisterCoalescer (which should really be named 
AggressiveRegisterCoalescer -- another patch on the way) inherits from both 
MachineFunctionPass and RegisterCoalescer.  The former because it is run and 
managed by PassManager and the latter because it needs to belong to the 
RegisterAllocator AnalysisGroup, similar to how alias analysis works.  We need 
a way for register allocators to ask PassManager for the coalescer object 
(even if the coalescer doesn't inherit from MachineFunctionPass) and this is 
the only way I know how to do it until someone takes on revamping how 
PassManager works and providing the capability of constructing hierarchies
of PassManagers.

I'm still working out getting things to build, etc. and will post a patch when
I've got through all that.  But does this sound like something closer to what
we want?

                                                -Dave