The Simplify and Select Loop of Chaitin-Style Coloring

Coloring an arbitrary graph with a fixed number of colors is NP-complete, and the interference graph of a real function is arbitrary enough that an exact algorithm is not affordable. The allocator therefore runs a heuristic that is greedy in one direction and provably safe in the other: it removes nodes it can certainly color, and when it cannot find any it removes a node it cannot color and marks it for spilling. The loop’s structure comes from a single observation about degrees.

Why a node of low degree can always be colored last

Consider a graph with K colors. Suppose a node v has fewer than K neighbors. If every other node in the graph can be colored with K colors, then v can be colored too: its neighbors use at most degree(v) distinct colors, which is at most K - 1, so at least one color remains for v. The argument is independent of how the rest of the graph was colored, which means it can be applied in reverse: strip v from the graph, color what remains, and put v back at the end with any free color.

That is the whole simplification step. Repeatedly find a node whose degree is below K, push it on a stack, and delete it from the graph. Deleting a node lowers the degrees of its neighbors, which may push more nodes below the threshold, so the process cascades. If it consumes the entire graph, the graph is K-colorable and the stack holds a coloring order: pop each node, look at the colors its (already restored) neighbors hold, and pick a color that is not among them.

Precolored nodes are never pushed. Their color is fixed, they remain in the graph throughout, and they count as neighbors for the degree test. A virtual register adjacent to two precolored registers effectively has two colors unavailable, but the degree test uses the full neighbor count, which is conservative in the right direction: it may refuse to simplify a node that could in fact be colored, but it never simplifies a node that cannot.

The cascade and its bound

The simplification cascade is where the algorithm’s efficiency comes from. Each removal costs time proportional to the node’s degree, and the total is the sum of degrees over all removed nodes, which is O(E) for a graph with E edges. Degree bookkeeping is a counter per node, decremented for each neighbor removed, so no rescan of the adjacency list is needed to test the threshold.

The cascade also explains why the algorithm is so effective in practice. Straight-line code has low register pressure almost everywhere: a value is live for a few instructions, interferes with a handful of others, and is trivially removable. The cascade eats those nodes immediately, and by the time it stalls, the remaining graph is small: the region of genuinely high pressure, usually a loop body or a call site. The size of the stalled graph is the measure of how hard the function is, not the size of the function.

The bound on the cascade’s length is the number of nodes, and each node’s removal touches its neighbors once, so a full simplification is linear in the graph size. That is the reason this family of allocators is affordable at all: the expensive part is the graph construction, not the coloring.

What happens when the cascade stalls

If every remaining node has degree at least K, the graph is not necessarily uncolorable, since the degree test is a sufficient condition and not a necessary one, but the algorithm has no node it can prove safe. Two responses are possible, and they distinguish the classic allocator from the improved one.

Chaitin’s original response is to pick a node, mark it as spilled, and remove it anyway. The node is pushed onto a separate list rather than the coloring stack, its neighbors’ degrees drop, and the cascade resumes. At the end, the spilled nodes are rewritten to live in memory, and the whole allocation is rerun on the modified program. This is pessimistic, not optimistic: the node chosen for spilling is not colored at all, the spill itself is what breaks the stall, and the rerun is mandatory. The choice of victim is therefore made by a cost heuristic, and the heuristic of spilling the node with the lowest cost-to-degree ratio is the subject of spill cost and victim selection.

Briggs’ improvement is to be optimistic for real. The stalled node is pushed onto the coloring stack like any other, and the coloring phase tries to color it. If it succeeds, no spill was needed and the choice was harmless. If it fails, because every one of the K colors is held by a neighbor at the moment of popping, the node is marked for spilling and the process continues. This is strictly better than Chaitin’s version: a node that happens to be colorable is colored instead of being spilled and rebuilt. In the worst case the same nodes fail, so nothing is lost; when the extra degree came from neighbors that were themselves removed later, the spill is avoided entirely. The optimistic variant is what makes Briggs’ graph-coloring allocator spill less than Chaitin’s while running the same simplify loop, and it is the setting in which conservative coalescing is formulated.

Coloring by popping

Selection walks the stack in reverse order of pushing. For each node, it collects the colors held by neighbors that are already colored (precolored nodes count as already colored from the start), and assigns the lowest-numbered free color. If no color is free, the node is uncolorable in this assignment.

The order matters, and the reverse order is the point. Nodes pushed early were removed when the graph was dense; nodes pushed late were removed when it was sparse. Popping reverses that, so the sparse-region nodes get colored first and the dense-region nodes are colored against a fully known neighborhood. A forward walk would color dense nodes with incomplete information and produce failures that the correct order avoids.

Color choice among the free ones is not arbitrary. Preferring a color that is already used by a move-related neighbor turns the move into a no-op for free, which is coalescing happening as a side effect of selection. Preferring low-numbered colors is a convention that keeps the chosen register stable across compilations, and it can shift how much spilling happens around calls, because on many targets the low-numbered registers are the caller-saved ones; the ABI-aware version of this preference is discussed in calling conventions as precolored nodes.

The loop as code

The following is the complete structure: simplification with an optimistic spill list, then selection with spill detection.

def color(adj, K, precolored):
    degree = {v: len(adj[v]) for v in adj}
    nbrs = {}                       # neighbor set saved at removal time
    stack, spilled = [], []

    def remove(v):
        nbrs[v] = adj.pop(v)        # keep the neighborhood for selection
        stack.append(v)
        for w in nbrs[v]:
            degree[w] -= 1

    while adj:
        # simplify: any node below the threshold is certainly colorable
        # (precolored nodes never appear in adj while this loop runs)
        low = next((v for v in adj if v not in precolored and degree[v] < K), None)
        if low is not None:
            remove(low)
            continue
        # optimistic: push a high-degree node anyway and see what happens
        v = max((x for x in adj if x not in precolored), key=lambda x: degree[x])
        remove(v)

    color_of = {p: p for p in precolored}
    for v in reversed(stack):
        taken = {color_of[w] for w in nbrs[v] if w in color_of}
        free = [c for c in range(K) if c not in taken]
        if free:
            color_of[v] = free[0]
        else:
            spilled.append(v)
    return color_of, spilled

The saved neighborhood in nbrs is what makes the degree counter meaningful: neighbors must be able to scan their own adjacency sets without encountering removed nodes, and selection must be able to scan the removed node’s neighbors. In an implementation that keeps a single graph and marks nodes as removed, both scans have to skip marked entries; either representation works, and the marked-node version is faster when adjacency sets are bitsets. The next(...) scan in the simplify loop is linear in the number of remaining nodes, which is fine for a concrete sketch and quadratic in the worst case for a real allocator; production versions keep a priority structure keyed by degree and update only the neighbors of the removed node.

Where the heuristic stops being enough

Three properties of this loop are worth stating plainly, two of them limits and one of them the reason the approach survives.

The result is not optimal. A graph that is K-colorable can be reported uncolorable by this heuristic, and the classic example is a graph where every node has degree at least K but a coloring exists; an induced cycle of length five with K = 2 is the smallest case, since every node there has degree exactly 2. The optimistic variant recovers some of these by trying, but a failure during selection still produces a spill that a smarter order would have avoided. The spills it reports are therefore an upper bound on what the program needs.

The loop is not confluent. The order in which low-degree nodes are simplified changes which node ends up uncolorable, because the optimistic choice at a stall is made on the current degrees. Two runs with different iteration orders over the node set can produce different spill sets for the same graph. Production allocators therefore pick nodes by a deterministic order, usually insertion order or a priority queue on spill cost, so that the result is reproducible, and accept that the choice is a heuristic rather than a search.

The third property is the one that justifies the whole design: the loop is fast. Simplification is linear in edges, selection is linear in the sum of the nodes’ neighbourhood sizes, and the entire pass runs in time comparable to the liveness analysis that fed it. The alternative of formulating coloring as an integer program or a SAT instance can find better colorings and costs orders of magnitude more, which is why it appears in research allocators and not in production compilers.