Chordal Interference Graphs and Optimal Coloring in SSA Form

Coloring an arbitrary graph is NP-complete, so every production allocator is a heuristic with no guarantee in general. There is one large and practically important class of programs where the guarantee comes back: programs in SSA form, whose interference graphs are chordal. On a chordal graph the greedy coloring produced by a perfect elimination ordering uses the minimum possible number of colors, and the ordering can be found in time linear in the graph size. The result is not a curiosity; it is the basis of a family of allocators that are both fast and optimal, and understanding why it holds shows which transformations destroy the property.

What chordality rules out

A graph is chordal when every cycle of length four or more has a chord: an edge between two vertices that are not adjacent in the cycle. A square with no diagonals is the smallest obstruction, and any graph containing one as an induced subgraph is not chordal. Trees are chordal, complete graphs are chordal, and interval graphs are chordal. General interference graphs are not. A concrete example needs four values whose live ranges overlap only in a cycle: give each of four blocks b1 through b4 one of the values, and make each value live in exactly two adjacent blocks — value a live in b1 and b2, b in b2 and b3, c in b3 and b4, and d in b4 and b1. Each value interferes with the two values it meets in a shared block, so the interference graph is the cycle a–b–c–d–a with no other edges, which is the induced square and therefore not chordal.

The structural characterization that matters is the simplicial vertex. A vertex is simplicial when its neighbors form a clique, meaning every pair of its neighbors is adjacent. Every chordal graph with at least one vertex has a simplicial vertex, and removing a simplicial vertex from a chordal graph leaves a chordal graph. Repeating the removal yields an ordering of all vertices, the perfect elimination ordering, in which each vertex’s later neighbors form a clique.

That property is exactly what the greedy coloring needs. Colour the vertices in reverse elimination order: when a vertex is coloured, all of its later neighbours, which are the only neighbours already coloured, form a clique, so they hold distinct colours, and the vertex needs at most one more colour than that clique contains. The number of colours the procedure uses is therefore one more than the largest later-neighbourhood, which for a chordal graph is the size of its largest clique. No order decision can make the greedy choice fail, because the neighbours already placed are mutually adjacent and their colours are all distinct.

Why SSA produces chordal graphs

The argument rests on the shape of a live range in SSA. Each value has exactly one definition, in one basic block. In a reducible program, which SSA construction typically assumes, the blocks in which the value is live lie within the blocks dominated by its definition, and the value is dead on any path where a redefinition would shadow it. The set of blocks dominated by a single block forms a subtree of the dominator tree, and the live ranges of all values therefore form a laminar family: two live ranges are either nested or disjoint in the dominator tree, never partially overlapping.

Laminar families produce chordal interference graphs. The classical construction is the intersection graph of a laminar family of subtrees of a tree, which is chordal; the interference graph of an SSA program is an induced subgraph of such an intersection graph, and induced subgraphs of chordal graphs are chordal. The proof is not needed to use the result, but the consequence is: the graph has no induced square, and a perfect elimination ordering exists.

Phi functions complicate the picture without breaking it. A phi at a join reads one value per predecessor, and the phi’s own live range begins at the join. The values flowing into the phi are live up to the end of their respective predecessor blocks, and the phi’s destination is live from the join onward. The live ranges remain laminar under the standard SSA liveness definition, and the chordality theorem covers programs with phi functions, which is what makes it applicable before SSA destruction rather than after.

Finding the ordering

Two linear-time algorithms find a perfect elimination ordering. Maximum cardinality search visits vertices in an arbitrary order and, at each step, selects the unvisited vertex with the largest number of already-visited neighbors. For a chordal graph the resulting ordering, reversed, is a perfect elimination ordering. Lexicographic breadth-first search does the same with a stronger invariant: each vertex carries a label that is a sequence of numbers, and vertices are selected by the lexicographic maximum of their labels.

Both algorithms are linear in the size of the graph with the right data structures: an array of buckets indexed by score for maximum cardinality search, a partition refinement for lexicographic search. For a function with 20,000 virtual registers and 200,000 edges, the ordering costs a single pass over the graph, which is cheaper than one iteration of the heuristic simplification loop it replaces.

The optimality claim is conditional on chordality, and checking chordality is itself linear: run maximum cardinality search, then verify that each vertex’s later neighbours form a clique. A graph that fails the check is not chordal, and the allocator must fall back to the heuristic loop. The check is worth doing because an incorrect assumption of chordality — from a graph built after a transformation that breaks the property — yields a colouring that is neither optimal nor guaranteed, and it may use more colours than K, which then appears as a spill.

Coloring in the elimination order

The coloring itself is the same greedy selection as in the simplify and select loop, with the ordering supplied rather than discovered. Process vertices in reverse perfect elimination order; for each, collect the colors held by its already-colored neighbors and take a free one.

def peo_color(adj, peo, K, precolored):
    # peo: perfect elimination ordering, simplicial vertices first
    color_of = {p: p for p in precolored}
    for v in reversed(peo):
        taken = {color_of[w] for w in adj[v] if w in color_of}
        free = next((c for c in range(K) if c not in taken), None)
        if free is None:
            return None                    # needs more than K colors
        color_of[v] = free
    return color_of

Because the later neighbors of each vertex form a clique, taken contains exactly degree_later(v) distinct colors and nothing else; no backtracking, no spill list, no stack. If the maximum clique size in the graph is at most K, the loop never fails. That maximum clique is a lower bound on the colors required and, for chordal graphs, exactly the number required, since the chromatic number equals the clique number, which is the property that fails for general graphs and is the reason heuristics exist.

Where the property is lost

Three transformations destroy chordality, and each is a normal part of compilation.

Coalescing merges two vertices into one whose neighborhood is the union of both. A union of two subtrees in a laminar family is not necessarily a subtree, so the merged live range can partially overlap a third range, and a partially overlapping pair of subtrees can form an induced square with a fourth. The practical consequence is that a coalescer running before coloring can turn a chordal graph into a general one, and the optimality proof no longer applies. The conservative tests of Briggs and George limit the damage by rejecting merges that would make the graph uncolorable, but they do not restore chordality.

SSA destruction is the second. Eliminating phi functions inserts copies at the join points, and each copy is a new value with a live range that spans from the copy to the uses. Those ranges are not part of the original laminar family, and the resulting graph is the one that general-purpose allocators see. This is why SSA-based allocators run the optimal coloring before destroying SSA: the guarantee exists only on the pre-destruction graph.

Spilling is the third, and it is the one that matters for the failure case. A spilled value is replaced by loads and stores, which create short-lived values at each use; those values are new vertices, and their live ranges are not laminar with the rest. Re-running the optimal coloring on the post-spill graph gives no guarantee, and implementations fall back to the heuristic loop for the second and later rounds.

The spill problem remains

Optimality in the coloring sense does not solve the allocation problem, because a function may need more colors than the machine has. The chordal machinery tells the allocator the exact minimum, which is the clique number, and identifies a minimum coloring, but when that minimum exceeds K, something must be spilled, and choosing what to spill is the same NP-hard problem as before. What the chordal result buys is a clean decision: the allocator knows the exact chromatic number, so it knows whether a spill is genuinely forced or whether the heuristic simply failed. A coloring that uses K + 1 colors on a chordal graph is proof that no K-coloring exists, which removes the guesswork from the spill loop.

The spill decision itself can use the elimination order as a guide. Vertices that appear late in the perfect elimination ordering have large cliques among their later neighbors, and those cliques are the pressure points. Spilling a vertex that is not in the maximum clique does not reduce the clique number, so the minimum color count is unchanged and the spill is wasted; spilling a vertex in the clique lowers the clique number by one. That gives a principled spill heuristic, and it is closer to a proof than the cost-to-degree ratio of the earlier model.

What the guarantee is worth

The practical value is speed and predictability. The heuristic loop’s result depends on the order in which nodes are visited, and a bad order produces spills that a better order would avoid; a perfect elimination ordering fixes that order up to ties between simplicial vertices, so the colouring does not depend on the arbitrary visit order the way the heuristic’s does. For a compiler that must be deterministic and fast, that is worth more than the marginal quality difference on functions where the heuristic happens to do well.

The limitation is scope. The theorem applies to reducible programs in SSA form with a live-range definition tied to dominance. Irreducible control flow, which arises from computed gotos, from some hand-written assembly, and from certain loop transformations, has no dominator-tree structure of the required kind, and the graph need not be chordal. Programs that mix SSA and non-SSA regions, which is common in compilers that construct SSA only for promotable variables, fall outside the guarantee as well. For those, the graph is a general one and the heuristic loop remains the only affordable option, which is why both algorithms coexist in the same compiler rather than one replacing the other.