[LLVMdev] Live range splitting with Ising models

[Jakob Stoklund Olesen]

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