llvm dev - Aug 2013 - [LLVMdev] Live range splitting with Ising models

With the D-Wave computer in the news recently, you may find it interesting that
LLVM’s register allocator is using Ising models to compute regions for live
range splitting.

The problem of finding a region for splitting a live range is mapped to an Ising
model with the help of the edge bundle graph, see EdgeBundles.h. A node in the
edge bundle graph represents a set of CFG edges that enter or leave the same
basic block, see also ‘llc -view-edge-bundles’.

A region for splitting a live range can be described as a coloring of the edge
bundle graph, such that ‘spin up’ means that the live range should go in a
register through this bundle, and ‘spin down’ means that the live range should
go on the stack. The connections between edge bundle nodes correspond to basic
blocks, and we give each connection a weight that is the expected execution
frequency of the corresponding basic block. This means that the ‘energy’ of a
solution is the same as the total expected execution frequency of the spill code
required to implement the live range split. The optimal split region is the
‘ground state’ of the Ising model.

As it turns out, the edge bundle graph is quite sparse compared to an
interesting Ising model, and that means we can get away with using a very fast,
very stupid algorithm (stolen from Hopfield networks) that simply converges on a
nearby local minimum. We don’t actually need to use simulated annealing or other
fancy optimization algorithms.

Stupid Ising model optimizer: lib/CodeGen/SpillPlacement.cpp
More on D-Wave:
http://arstechnica.com/science/2013/08/d-waves-black-box-starts-to-open-up/
More on Ising models and Hopfield networks:
http://www.inference.phy.cam.ac.uk/mackay/itila/

Thanks,
/jakob

On 7 August 2013 17:06, Jakob Stoklund Olesen <stoklund at 2pi.dk>
wrote:
> With the D-Wave computer in the news recently, you may find it interesting
that LLVM’s register allocator is using Ising models to compute regions for live
range splitting.
>
> The problem of finding a region for splitting a live range is mapped to an
Ising model with the help of the edge bundle graph, see EdgeBundles.h. A node in
the edge bundle graph represents a set of CFG edges that enter or leave the same
basic block, see also ‘llc -view-edge-bundles’.
>
> A region for splitting a live range can be described as a coloring of the
edge bundle graph, such that ‘spin up’ means that the live range should go in a
register through this bundle, and ‘spin down’ means that the live range should
go on the stack. The connections between edge bundle nodes correspond to basic
blocks, and we give each connection a weight that is the expected execution
frequency of the corresponding basic block. This means that the ‘energy’ of a
solution is the same as the total expected execution frequency of the spill code
required to implement the live range split. The optimal split region is the
‘ground state’ of the Ising model.
Thanks for the information. Is this done iteratively? I.E., we solve a
ising model every time we cannot assign a register to a range and want
to decide if we should split one of the already assigned ranges?

Cheers,
Rafael

On Aug 8, 2013, at 8:24 AM, Rafael Espíndola <rafael.espindola at
gmail.com> wrote:
> On 7 August 2013 17:06, Jakob Stoklund Olesen <stoklund at 2pi.dk>
wrote:
>> With the D-Wave computer in the news recently, you may find it
interesting that LLVM’s register allocator is using Ising models to compute
regions for live range splitting.
>> 
>> The problem of finding a region for splitting a live range is mapped to
an Ising model with the help of the edge bundle graph, see EdgeBundles.h. A node
in the edge bundle graph represents a set of CFG edges that enter or leave the
same basic block, see also ‘llc -view-edge-bundles’.
>> 
>> A region for splitting a live range can be described as a coloring of
the edge bundle graph, such that ‘spin up’ means that the live range should go
in a register through this bundle, and ‘spin down’ means that the live range
should go on the stack. The connections between edge bundle nodes correspond to
basic blocks, and we give each connection a weight that is the expected
execution frequency of the corresponding basic block. This means that the
‘energy’ of a solution is the same as the total expected execution frequency of
the spill code required to implement the live range split. The optimal split
region is the ‘ground state’ of the Ising model.
> 
> Thanks for the information. Is this done iteratively? I.E., we solve a
> ising model every time we cannot assign a register to a range and want
> to decide if we should split one of the already assigned ranges?
Not quite. If no register can be found for a live range, we first try to evict
an already assigned live range with a smaller spill weight. If none is found, we
move on to splitting the live range.

It can happen that a split range gets evicted by a third range with higher spill
weight. In that case, the range is split again, and this process can iterate as
long as the splitting is making progress. IIRC, 'progress' is defined as
reducing the number of basic blocks covered by the live range.

Thanks,
/jakob

On 7 August 2013 17:06, Jakob Stoklund Olesen <stoklund at 2pi.dk>
wrote:
> With the D-Wave computer in the news recently, you may find it interesting
that LLVM’s register allocator is using Ising models to compute regions for live
range splitting.
>
> The problem of finding a region for splitting a live range is mapped to an
Ising model with the help of the edge bundle graph, see EdgeBundles.h. A node in
the edge bundle graph represents a set of CFG edges that enter or leave the same
basic block, see also ‘llc -view-edge-bundles’.
>
> A region for splitting a live range can be described as a coloring of the
edge bundle graph, such that ‘spin up’ means that the live range should go in a
register through this bundle, and ‘spin down’ means that the live range should
go on the stack. The connections between edge bundle nodes correspond to basic
blocks, and we give each connection a weight that is the expected execution
frequency of the corresponding basic block. This means that the ‘energy’ of a
solution is the same as the total expected execution frequency of the spill code
required to implement the live range split. The optimal split region is the
‘ground state’ of the Ising model.
| Thanks for the information. Is this done iteratively? I.E., we solve a
| ising model every time we cannot assign a register to a range and want
| to decide if we should split one of the already assigned ranges?

Just as general comments not related to the specific implementation in LLVM:

I believe that 2-state Ising models can be reduced to max-flow/min-cut (eg,
Finding ground states in random-field Ising ferromagnets by F Barahona) , so
were a guaranteed polynomial time solution wanted that could be used although as
Jakob mentioned, with "easy" problems as simple iterative thing is
often quicker in practice. (That's assuming it is an exact Ising model: I
hadn't realized LLVM was using that and a quick skim of the file doesn't
make me fully confident I understand what model it's implementing.) One
interesting thing that can be done with max-flow solutions is to change the
problem data to a modified problem in a smart way, then restart the solver from
the existing solution and avoid redoing most of the work. (Certain Markov Random
Field models, of which Ising is an example, in computer vision have been using
max-flow to solve these problems for about a decade now, which is how I know
about it.)

Cheers,
Dave

On Aug 8, 2013, at 10:46 AM, David Tweed <david.tweed at arm.com> wrote:
> | I believe that 2-state Ising models can be reduced to max-flow/min-cut
(eg, Finding ground states in random-field Ising ferromagnets by F Barahona)
> 
> I hadn't been following D-Wave; upon looking I see that they're
using problem reductions to Ising models which aren't ferromagnet models
(sign is different), and those problems are known to be NP-hard. Haven't
thought about what kind of models LLVM is using.
I hadn’t noticed that either. Anyway, LLVM’s models are ferromagnetic, the
interactions are sums of expected basic block frequencies which are always
non-negative numbers.

Thanks,
/jakob

On Aug 8, 2013, at 9:01 AM, David Tweed <David.Tweed at arm.com> wrote:
> Just as general comments not related to the specific implementation in
LLVM:
> 
> I believe that 2-state Ising models can be reduced to max-flow/min-cut (eg,
Finding ground states in random-field Ising ferromagnets by F Barahona) , so
were a guaranteed polynomial time solution wanted that could be used although as
Jakob mentioned, with "easy" problems as simple iterative thing is
often quicker in practice. (That's assuming it is an exact Ising model: I
hadn't realized LLVM was using that and a quick skim of the file doesn't
make me fully confident I understand what model it's implementing.)
The cost function does map to the Hamiltonian of an Ising model (give or take a
couple of constants), and all interactions are non-negative, making it
ferromagnetic. There are a couple of cheats, though:

- The nodes are tri-state, {-1, 0, +1}, with the neutral state being used as the
starting point. This allows a small spin-up seed to grow into a domain of
unbiased nodes until it hits negatively biased nodes. The nearby local minima
found without this tweak tended to be too conservative.

- Initially, only positively biased nodes and their neighbors are added to the
model. As the Hopfield updates activate more nodes, their neighbors are added to
the model. This is purely a compile time optimization for large CFGs, but it
does affect the result by not allowing spin-down domains to form until they are
‘discovered’.

I think there is a lot of room for improvement here, and it would be interesting
to see how a proper solver would affect the generated code.
> One interesting thing that can be done with max-flow solutions is to change
the problem data to a modified problem in a smart way, then restart the solver
from the existing solution and avoid redoing most of the work. (Certain Markov
Random Field models, of which Ising is an example, in computer vision have been
using max-flow to solve these problems for about a decade now, which is how I
know about it.)
I would like to implement a couple of generalizations that may be related:

1. Currently, we optimize a 2-state Ising model for each candidate member of the
register class when splitting a live range. The Ising models are different
because the negative node bias comes from interference from other live ranges
that have already been assigned to the candidate register. The live range is
split according to the cheapest Ising solution, creating a number of live ranges
that can be assigned to the candidate register and a remainder that is likely to
spill.

I would like to do a multiway split instead, targeting multiple candidate
registers simultaneously. This could be done by somehow combining the 2-state
Ising solutions, but a more accurate model would be an n+1 state Ising model
with a state for each candidate register in the register class plus one
representing the stack. I don’t know how to optimize such a model.

2. When spilling, values can be available both on the stack and in a register,
but the Ising models assume a value can only be in one place and always add a
cost for moving values between register and stack. A tri-state model {stack,
reg, both} would compute a more accurate cost. This would mean that couplings
are no longer symmetric, the cost would depend on the direction of control flow.

Thanks,
/jakob