[LLVMdev] Live range splitting with Ising models

[David Tweed]

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