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

[Roman Levenstein]

Hi Dave,

Coming back to your mail about the RegisterCoalescer and RegallocQuery
interfaces, I'd like to ask a few questions.

2009/1/12 David Greene <dag at cray.com>:
> 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.

I understand the overall approach. I even tried to define my own
coalescer by deriving it from the RegisterCoalescer.
This was OK. But then I got stuck, because I don't understand how I
can select this coalescer in the command-line of llc.
As far as I can tell, there is no registry for the coalescers (similar
to what exists for register allocators and which allow you to select a
register allocator by providing the --regalloc=register_allocator_name
command-line option ) and therefore there is no way to select a
specific register coalescer among all defined coalescers. Is my
understanding correct? If so, do we need to add such a registry for
this purpose?
Dave, how have you solved this in your source tree?

> 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 learned it by hart recently. My initial implementation uses my own
custom coalescer. But the problem is that it misses many opportunities
compared to the "simple" register coalescer. In particular, some
cases, where live intervals do not interfere even though their
live-ranges overlap. And this may happen e.g. for some live intervals
that were produced from phi-nodes. There are also some tricky cases
related to commuting operands and so on. Doing all that correctly
would probably end up with a code that is as "simple" as the
SimpleRegisterCoalescer ;-)

> 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 is also the direction that I'm thinking more and more about. I
think that if it would be possible to separate/extract an API that
would provide the possibility to check for possibility of coalescing
of two given intervals (a,b) and to perform the coalescing of two
particular intervals (a,b) then it would become much more reusable and
can serve as a basis for other coalescers. Those coalescers/register
allocators would then decide on their own about the candidates for
coalescing based on their own profitability analysis and internal
logic and then ask this common code if it is possible to coalesce
given intervals and to perform this coalescing and do dataflow
updates...

I think it is rather possible to extract it from the current
implementation, which currently covers too many things at once. For
example, it tries to do coalescing for all move-related intervals and
it does it based on its own metrics and its own logic. And in many
cases the code assumes that only these metrics are used. So the main
task is to separate the code that performs coalescing for a pair of
intervals from the code that decides which pairs and in which order
should be coalesced.

Is it more or less inline with your thinking? Is it what you managed to do?

> 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, BTW, I'd be very interested in having a look at it even of it is
not to be pushed back to LLVM by you in the near future.
May be I can work on it to make it more prepared for the inclusion
into mainline. Or may be it will provide me with a better insight
about how the "ideal" coalescer interface should look like in LLVM.
So, if you could provide me with the snippets of your coalescer
related code, especially the dissected SimpleRegisterCoalescer, I'd be
very grateful to you.

-Roman