[LLVMdev] [PATCH] Re: Pluggable Register Coalescers

[Evan Cheng]

On Jul 17, 2007, at 8:40 AM, David Greene wrote:

> On Monday 16 July 2007 18:19, Evan Cheng wrote:
>
>> Sorry I should have replied earlier. I really don't like this dual
>> interface approach. To me, this muddles things without offering any
>> real useful new functionalities.
>
> Ok.  See below for the rationale.
>
>> IMHO, if a register coalescer is tied to a particular allocator. Then
>> either it should simply belong to that allocator or that we have to
>> allow the allocator to act as a pass manager itself, i.e. it can
>> control what passes to run as part the allocating process. I don't
>> know if the pass manager allows that functionality. If not, then
>> that's something we should add because there are other passes that
>> can benefit from it.
>
> I'm not sure I fully understand what you're proposing.  The reason I
> went with the AliasAnalysis-like construct is that I envisioned a
> "-coalescer=<type>" user option, similar to how alias analysis and
> register allocation works.  Somehow we have to make that option
> work with independent register coalescers (those derived from
> MachineFunctionPass or equivalents that can run through the
> PassManager) and those that are tied to some abstract register
> allocation algorithm.  A coalescer that runs in conjunction with an
> allocator need not be tied to a particular implementation of register
> allocation.  For example, George and Appel's Iterated Register
> Coalescing can work with any concrete implementation of graph
> coloring (and there are lots of variations out there) and can probably
> work with other algorithms as well.  So if we can avoid it, I'd  
> rather not
> be limited to hard-coding these things.

Ok.

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

>
> If we decide that we don't need this flexibility, that's fine with  
> me.  I was
> working based on the needs expressed by Tanya and Reid and the
> implementation suggested by Christopher Lamb.  I'm not wedded to it.
>
> To me, the most important thing is a simple user interface.  We  
> want one
> command-line option that picks a coalescer and the user should not  
> have
> to worry about whether the coalescer is implemented as a separate pass
> or works as part of the register allocator.  The user should not  
> have to worry
> about whether the coalescer and register allocator he or she specifies
> are compatable in the sense that the register allocator knows the  
> guts of
> the coalescer and vice-versa.  That seems to drive the need for  
> abstract
> interfaces for both.

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


>
>> Also, on this particular file below. Seems to me these queries do not
>> belong to the register allocator. Perhaps a utility class that tracks
>> interference information that can be accessed by both the allocator
>> and the coalescer? Also, why is coalesceThisCopy() needed? Shouldn't
>> the coalescer be responsible for making the decision?
>
> 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.

>
> A utility class is an interesting idea.  In fact I've been thinking  
> about how
> one might go about separating the essentials of, say, a graph coloring
> allocator and the particular heuristics it uses to make decisions.   
> A graph
> is a graph and could certainly be factored out into a separate  
> utility class,
> which could provide interfaces for queries.  A policy-based design  
> is one
> possibility, where a generic graph coloring algorithm is written as  
> a template
> and the developer passes policy types that it uses to configure  
> itself with
> heuristics.
>
> 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.  It seems hard to me.  I'm not even sure a
> coalescer that wants to work with an allocator can work with every  
> register
> allocation algorithm.  For example, can the linear-scan algorithm  
> satisfy
> the queries asked by a coalescer that expects a graph coloring  
> algorithm?
> I don't know.  It would be nice if it could, to ease the burden on  
> the user as
> explained above.  I think it can if the queries are not too fine- 
> grained.  The
> interface in the patch is pretty much the coarsest grain that I  
> could think
> of.  It would be bad, for example, to add interfaces like "does  
> this graph
> node have neighbors of degree > N?" because not every allocator could
> answer it.

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

>
> The coalesceThisCopy interface is there for similar reasons.  Some  
> coalescing
> algorithms (Briggs' conservative coalescing is a good example)  
> examine the
> interference graph and apply heuristics based on the degree of the  
> neighbors
> of nodes being coalesced.  Your utility class could provide  
> interfaces to make
> more fine-grained queries, but as noted above, it seems a bit  
> harder as
> various register allocators may use very difference  
> representations.  So
> coalesceThisCopy is certainly a compromise.  It does move  some of the
> decision-making for coalescing into the register allocator.  You  
> raise a good
> point and I'll think about how we can improve this.

Ok.

>
> Do you have suggestions for how to move forward based on the  
> above?  I have
> some critical work to do here and it's going to require that we get  
> pluggable
> ]coalescers working at some level.  We can of course evolve the  
> interface as
> we learn.

Assuming the interference graph is available, does the coalescer need  
any information from the allocator to make decisions? Are you  
designing the coalescer so it always run before allocation? If so,  
please keep it simple. :-) Make it operate on existing live interval  
information (perhaps enhanced if needed) and the new interference  
graph class (again, if needed). I think as a first step, the  
coalescer should be as aggressive as possible (i.e. no concerns for  
what the allocator would do).

Evan


>
>                                                  -Dave
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev