[LLVMdev] Is it possible to use the SimpleRegisterCoalescing pass in an iterative way?

[David Greene]

On Friday 09 January 2009 03:36, Roman Levenstein wrote:
> Hi,
>
> I'm implementing some variations of graph-coloring register allocators for
> LLVM. Many of them perform their phases (e.g. coalescing, graph
> simplification, spilling,  color selection) in an iterative way. Since
> LLVM provides an implementation of the coalescing in the
> SimpleRegisterCoalescing class already, I would like to reuse it (even
> though I could of course create my own coalescing implementation). But
> this class is a MachineFunctionPass.
>
> I'm wondering, if it is possible to use this pass from another pass
> (i.e. regalloc) in an iterative way:
> I need to invoke it multiple times for the same MachineFunction at
> certain places in my regalloc pass implementation.
> May be some sort of analysis update can be performed? Or is it
> designed to be used just once per MachineFunction?

Hi Roman,

I did this a while back when implementing iterative register coalescing.  My 
guess is you're trying to do the same with the Generaslized Graph Coloring 
algorithm,.

It's not easy to accomplish within the LLVM framework.  I've made a number of 
structural changes to our code here and it's in a bit of a state of bitrot due 
to upstream changes we haven't merged in yet.

I got some of this work merged upstream in the RegisterCoalescer and 
RegallocQuery interfaces.  RegallocQuery is supposed to be an opaque 
communication conduit between register allocators and coalescers such that 
the allocator can update the coalescer when it makes changes and vice versa.

When I did the full implementation I found I had to make more changes to 
RegallocQuery.  I have not pushed those upstream for various reasons, 
including that at the time the register coalescing code was in a great state 
of flux and it was difficult to track.  It will be a bit of work to get it all 
up-to-date for merging.

Evan is right that coalesceFunction is the primary interface to invoke the 
coalescer.  The iterative coalescer I wrote implements that function.  The 
iterative coalescer is also a FunctionPass which does nothing.  It's simply 
there to fulfill the requirement that the register allocator depends on a 
coalescer.  This way I could use the SimpleRegisterCoalescer or the new 
iterative coalescer in a pluggable manner.  The generalized graph coloring 
allocator holds a reference to the coalescer.  SimpleRegisterCoalescing does 
nothing in its implementation of coalesceFunction.

This is all very far from ideal.  What we really need is a PassManager that 
knows about multually dependent, iterative algorithms.  I thought about this a 
bit back in the day and came up with the idea of a hierarchy of PassManagers.  
A set of iterative passes could live in a PassManager under the top-level 
PassManager and the child PassManager could specify dependencies for all of 
the passes it manages.  I didn't get very far with this so I don't know it 
it's a viable solution.

The iterative coalescer does its own correctness and profitability analysis 
but reuses the code from SimpleRegisterCoalescing to do the actual LLVM IR and 
dataflow updates.  That's non-trivial work.  The code to do this in 
SimpleRegisterCoalescing is a bit...well...convoluted.  :)  I did a 
significant amount of work to separate that code out from the dataflow and 
profitability analysis that determines when to coalesce copies.

This I think is very valuable work and I'd like to push it back.  It's always 
good to separate analyses and updates as much as possible so that things can 
be reused.

But I can't promise that I'll be able to merge all of the work I've  done.  We 
have quite a bit going on here right now and I've been moved to other bits of 
work.  I'll see if I can get some things accomplished out-of-band.

                                                       -Dave