Optimal Coalescing Challenge

Andrew Appel and Lal George

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.

Description of the problem

Given an undirected graph of N nodes of degree less than K, and a set of triples of the form (i,j,w), where i and j are nodes and w is a weight; find a K-coloring of the graph that minimizes the sum of the weights of triples (i,j,w) such that color[i] != color[j].

Sample inputs

We provide 474 sample inputs. We also have several different solution sets, found by different algorithms:
  1. suboptimal solutions found by iterated register coalescing from Lal George
  2. better (but not optimal) solutions found by optimistic coalescing from Lal George
  3. solutions from a better greedy algorithm from Hai Fang of Yale University
  4. solutions from a heuristic algorithm from Hai Fang
  5. Optimal solutions from an integer linear program by Daniel Grund and Sebastian Hack.
Problems and solutions are described in this input format. We also provide a solution checker that verifies and evaluates any solution to an instance.

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.

Background reading

The following technical report describes the context of the coalescing problem.

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).

Iterated register coalescing

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.