[LLVMdev] [PATCH] Re: Pluggable Register Coalescers

[David Greene]

On Tuesday 17 July 2007 13:06, Evan Cheng wrote:

> > These two requirements led to the abstract RegisterCoalescer
> > interface in the patch.  This is the interface that register
> > allocators
> > know about.  Likewise, coalescers need an abstract interface to
> > register allocators to ask questions and do other things.
>
> If the two modules need to share information. I think you want a
> third module to encapsulate it.

Yes, that makes sense to me.

> 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.

> For now, I think we leave it as it is. If the user picked a 
> coalescer that doesn't work with the register allocator of choice, we
> can output an error (or a warning and override the choice).

Ok.

> > Register allocators know information about interference, for example,
> > the interference graph in a coloring allocator.  The classic
> > coalescing
> > algorithm examines the interference graph and looks for copies between
> > allocation units whose corresponding nodes do not have an edge between
> > them in the graph.  That's why that interface is there.
>
> Right, then perhaps the interference graph should not be part of
> allocator. Both the allocator and coalescer can be clients. It's
> weird to me for the coalescer to directly query the allocator
> especially since the goal is to keep the coalescer independent from
> the allocator.

Good point.

> > The larger question is whether a good abstract interface for the
> > utility class can be found that can support difference representations 
> > such as graphs, the linear-scan stuff, etc.

> I don't think we need that level of abstraction right now. :-)

True enough.  But I need some kind of abstraction, because for various reasons
I don't have an interference graph implementation I can check in.  But yet I
want to check something in that others can use. 

> Assuming the interference graph is available, does the coalescer need
> any information from the allocator to make decisions? 

Not that I'm aware of.  And in the future if something more is needed, then
we can do another round of factoring.

> Are you designing the coalescer so it always run before allocation? If so,
> please keep it simple. :-)

Believe me, I'm trying to keep it as simple as possible.  The coalescer I'm
working on doesn't run "before" allocation.  It runs in conjunction with it.
Decisions have to be made here as to whether it gets pushed out into the
public repository and because of the way it's designed, the general llvm
community might not be interested in it anyway.  It's more complex due to
some additional requirements on this end that don't have any relevance 
to the llvm community.

> Make it operate on existing live interval  information (perhaps enhanced if 
> needed)

Yep, it does.  Hence the factoring effort on the current coalescer.

> and the new interference graph class (again, if needed). 

As stated above, I'd like to make this an abstract interface to an 
interference graph, due to complexity of my implementation that the llvm
community doesn't care about.

> I think as a first step, the coalescer should be as aggressive as possible 
> (i.e. no concerns for what the allocator would do).

Well, that's the current coalescer, and the whole reason I'm writing a new one
is that we don't want it to be so aggressive.

In the end, what I am able to contribute back at this point is the
infrastructure to make it easy to implement new coalescers.  Due to
legal and other issues, I can't contribute any concrete implementations
right now, and it's not likely I'll be able to do so any time soon.  But I do
want to make sure that the infrastructure works for everyone.

This is very good feedback.  I'll take it and rework the patch.

                                                    -Dave