Conservative Coalescing and the Conditions That Make It Safe

A move instruction that survives allocation is pure overhead. It transfers a value between two registers that the allocator could have made the same register, and if it had, the instruction would disappear. Removing moves is therefore worth real work: a move costs a cycle and a pipeline slot, and in a loop it costs that per iteration. Coalescing is the mechanism, and the naive version of it, which merges every move-related pair and then colors, is a trap, because merging two nodes merges their neighbor sets, and the merged node can have a degree that no coloring can satisfy.

The merge operation and why it hurts

Coalescing a and b, where the program contains b <- a, replaces both with a single node whose neighbors are the union of a’s and b’s. The move becomes a no-op and is deleted. The cost is that the merged node’s degree can be as large as the sum of the two degrees, and the constraint “this node needs a color different from all its neighbors” is now harder to satisfy than either of the original constraints.

An example makes it concrete. With K = 2 colors, take a and b move-related, each adjacent to the same single node c, and no edge between a and b. The graph is a path a - c - b and is 2-colorable: a and b get color 1, c gets color 2, and the move between a and b is free. Merge a and b and the result is a single node adjacent to c, which is trivially 2-colorable and the move disappears, which is a good merge.

Now take a and b each adjacent to c and d, with c and d adjacent to each other, and a and b not adjacent. The original graph is a diamond and is 2-colorable. Merging a and b yields a node adjacent to both c and d, which are adjacent to each other and therefore hold two different colors; the merged node has no color left, and the graph becomes uncolorable. Coalescing destroyed a valid coloring, and the allocator will now spill a value that did not need spilling.

Chaitin’s original allocator handled this by refusing to coalesce any pair whose merged degree reached K. The test is safe, because a merged node whose degree is below K is simplifiable and cannot be the cause of a failure, but it is far too strict. It rejects merges where a and b share most of their neighbors, because the merged degree is then close to either original degree and can still reach K.

Briggs: count the neighbors that matter

Briggs’ test asks a different question: after the merge, does the graph still have enough low-degree nodes to simplify? The precise condition is that the merged node has fewer than K neighbors of degree at least K. The reasoning is that a node can always be simplified if its degree is below K, and the merged node’s high-degree neighbors are the only ones that can prevent that: the low-degree neighbors will be removed before the merged node is considered, dropping its degree as they go.

Stated as a rule: coalesce a and b if the number of distinct neighbors of the merged node whose post-merge degree is >= K is less than K. The test is conservative in the technical sense: it never accepts a merge that would turn a graph colorable by the simplify/select procedure into one that runs out of colors for a reason the merge itself introduced. It accepts many merges that Chaitin’s degree test rejects. In the diamond example above, the merged node has two neighbors, both of degree at least 2, and K = 2, so the count is 2 and the merge is rejected; correctly, since the merge was fatal.

The test is also cheap. Computing the merged neighbor set is a union of two adjacency sets, and counting the high-degree members is a single pass. With bitset adjacency the union is N/64 word operations for N vertices, which is what makes the test affordable to run for every move in the program.

George: a test that avoids building the union

George and Appel’s test is stated per-neighbor rather than on the merged set, which makes it usable when one of the two nodes is precolored and when the union is expensive to materialize. Coalesce a into b if, for every neighbor t of a, either degree(t) < K or t is already adjacent to b. The intuition: the only new constraints the merge creates are edges from b to a’s neighbors that b did not already have, and those new edges only matter if t is high-degree, because a low-degree t will be simplified away before b is colored.

The test is asymmetric, since a into b is not the same as b into a, which is a feature rather than a bug. Coalescing a virtual register into a precolored register (the case of a value that must end up in a specific argument register) is exactly the situation where one direction is legal and the other is not, since the precolored node cannot be renamed. Running the test with the precolored node as b asks whether the virtual node can adopt that fixed color, which is the question the calling convention poses.

Both tests are sufficient, not necessary. A merge they reject may still be safe, and a more expensive check that attempts the merge and re-runs the coloring would find those cases. Production allocators accept the loss because the alternative costs substantially more per move, and the test they do run is the one described in the simplify and select loop, where the merged node must eventually be colored like any other.

The order of merges is the algorithm

Coalescing is not a single decision but a sequence, and the sequence changes the outcome. Merging a and b changes the degrees that later tests see, so a pair that would have passed may fail after an unrelated merge, and vice versa. Three orderings are common.

The first is to process moves in order of profitability, where profitability is estimated from the static loop nesting depth of the move, so moves inside loops come first. This is the ordering that matters most, because the benefit of eliminating a move scales with how often the move runs.

The second is to process all moves that are trivially safe first — those where one node’s neighborhood is already contained in the other’s — and only then run the conservative tests. Such merges add no new edges at all, so they cannot make a later test fail, and doing them first lets the later tests see the smaller graph they produce.

The third is to interleave coalescing with simplification, which is what the standard implementation does. Whenever a node’s degree drops below K, it is removed; after each removal, the move-related pairs involving its neighbors are retested. This is the “coalesce while simplifying” loop, and it is more effective than either phase alone because simplification lowers degrees, which makes more merges pass, which lowers degrees further.

Bias and the move graph

Each coalescing decision has a direction: merge a into b or b into a. When both are uncolored virtual registers the direction only affects later tests, but when one is precolored the direction is forced. A common refinement is to attach a bias to each move, recording which operand should be the survivor, derived from the instruction: a copy into an argument register biases toward the argument register, a copy out of a return register biases toward the virtual register.

Bias also resolves conflicts between coalescing and other constraints. If a is move-related to both b and c, and b and c interfere with each other, at most one of the two moves can be eliminated: merging a with b leaves the move to c in place, and the merged node now interferes with c. The allocator must pick, and the choice should be the move that executes more often. Tracking this requires per-pair move weights rather than a single move graph, which is why implementations store a list of moves per node rather than an edge set.

What coalescing does not fix

Coalescing removes moves that the allocator created or that the front end left behind, but it cannot remove a move whose two operands must differ. When a parallel copy contains a cycle — two values that must end up in each other’s registers — the cycle has to be broken by one instruction that writes a temporary, and no assignment of registers can remove it. The scheduling of such copies is treated under calling conventions; the allocator’s part is to break the cycle with the fewest temporaries, which for a swap and for a longer cycle is still one, a rotate through a scratch register.

Coalescing also interacts badly with spilling. A merged node that is spilled takes both original values to memory, and the move it was meant to eliminate is replaced by a load and a store, so a merge that turns out to spill is worse than no merge at all. Some allocators therefore weight coalescing decisions by a static estimate of how likely the merged node is to spill. The heuristic is approximate and the interaction is real; the standard resolution is to coalesce before spilling and to avoid re-coalescing after a spill round, so that the spill decision sees the merged graph and the merge decision does not see the spill.

A test in code

The following implements the Briggs test over bitset adjacency, which is the form that keeps the cost low.

def briggs_ok(a, b, adj, degree, K, precolored):
    if b in precolored:
        return george_ok(a, b, adj, degree, K)
    # neighbors that would still have degree >= K after the merge
    high = 0
    for t in adj[a] | adj[b]:
        if t in precolored:
            high += 1                      # precolored nodes never simplify away
        elif degree[t] - (t in adj[a]) - (t in adj[b]) >= K:
            high += 1
    return high < K

def george_ok(a, b, adj, degree, K):
    for t in adj[a]:
        if degree[t] < K or t in adj[b]:
            continue
        return False
    return True

The degree adjustment in the first test is the subtle part. After merging a and b, each shared neighbor loses two neighbors rather than one, and a neighbor adjacent to only one of them loses one. Computing the post-merge degree exactly is what makes the test tight; using the pre-merge degrees overestimates the number of high-degree neighbors and rejects merges that would have been safe. Precolored nodes are excluded from simplification, so their degree never drops and they always count as high.

The accounting

Move elimination is usually reported as a fraction of the moves in the input, and that fraction depends mostly on where the moves came from: code produced by naive instruction selection, where every operand goes through a temporary, gives the pass far more candidates than a backend that already assigns operands to fixed registers.