[LLVMdev] Live range splitting with Ising models

[Jakob Stoklund Olesen]

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