[LLVMdev] [PATCH] Re: Pluggable Register Coalescers

[David Greene]

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.

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

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

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.

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.

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.

                                                 -Dave