*
History: We originally posted this challenge
in August 2000. In December 2000 we found a satisfactory
heuristic, "optimistic coalescing," as described in our
technical report.
However, optimistic coalescing is in no way optimal, and an optimal
algorithm would still have practical application to real
compilers.
In October 2006, Daniel Grund and Sebastion Hack demonstrated
an optimal algorithm using integer linear programming (see below).
*

Register allocation can be done by graph coloring, and many computers
do register allocation this way. But register allocation is not
simply the *K*-coloring of an interference graph: often the
input graph is not *K*-colorable, and the allocator must
color some of the nodes and delete others.

We have a new *spilling*
algorithm for optimally deciding which nodes to delete,
thus reducing register allocation to a simpler coloring problem.
But coloring is NP-complete, and the greedy coloring algorithms
that worked well for the relatively unconstrained problems posed
by traditional algorithms do not work well for the coloring problems
that come out of our optimal spiller.

To be practically useful, our optimal spilling algorithm
requires a companion algorithm for
*K*-coloring with
optimal register coalescing. The challenge is
to find an optimal coalescing algorithm.

- suboptimal solutions found by iterated register coalescing from Lal George
- better (but not optimal) solutions found by optimistic coalescing from Lal George
- solutions from a better greedy algorithm from Hai Fang of Yale University
- solutions from a heuristic algorithm from Hai Fang
**Optimal**solutions from an integer linear program by Daniel Grund and Sebastian Hack.

These inputs were generated by compiling several of the standard SML/NJ benchmarks using a variant of SML/NJ that implements optimal register spilling. The solutions were generated by the iterated register coalescing algorithm.

Optimal Spilling for CISC Machines with Few Registers

(or, reducing register allocation to the unsolved problem
of optimal coalescing)

(Postscript)
(PDF)

Abstract.Register allocation based on graph coloring performs poorly for machines with few registers, if each temporary is held either in machine registers or memory over its entire lifetime. With the exception of short-lived temporaries, most temporaries must spill -- including long lived temporaries that are used within inner loops. Live-range splitting before or during register allocation helps to alleviate the problem but prior techniques are sometimes complex, make no guarantees about subsequent colorability and thus require further iterations of splitting, pay no attention to addressing modes, and make no claim to optimality. We formulate the register allocation problem for CISC architectures with few registers in two parts: an integer linear program that determines the optimal location to break up the implementation of a live range between registers and memory, and a register assignment phase that we guarantee to complete without further spill code insertion. Our linear programming model considers the various addressing modes available to an instruction and finds an optimal solution quickly. The second phase will complete without spilling, but at the expense of register-register copies remaining in the program. The task of coloring while leaving behind the minimum number of splits(optimal coalescing)is left as an open problem; we discuss two unsatisfactory solutions (one fast and suboptimal, the other optimal but far too slow).

The following paper describes our greedy algorithm for the coalescing problem. The paper actually describes a more general algorithm that also does spilling; for the "coalescing challenge" that part of the algorithm need not be implemented, and the multiple passes described in the paper would be unnecessary.

When applied to the inputs described in the paper (using 25 colors to allocate for 32-register RISC machines) the greedy algorithm performs well. To 6-color graphs resulting from optimal spilling, the greedy algorithm does not produce near-optimal results.

Iterated Register Coalescing. Lal George and Andrew
W. Appel.
*ACM Transactions on Programming Languages and Systems* 18(3) 300-324, May
1996.