COALESCING

It is easy to eliminate redundant move instructions with an interference graph. If there is no edge in the interference graph between the source and destination of a move instruction, then the move can be eliminated. The source and destination nodes are coalesced into a new node whose edges are the union of those of the nodes being replaced. In principle, any pair of nodes not connected by an interference edge could be coalesced. This aggressive form of copy propagation is very successful at eliminating move instructions. Unfortunately, the node being introduced is more constrained than those being removed, as it contains a union of edges. Thus, it is quite possible that a graph, colorable with K colors before coalescing, may no longer be K -colorable after reckless coalescing. We wish to coalesce only where it is safe to do so, that is, where the coalescing will not render the graph uncolorable. Both of the following strategies are safe:

Briggs: Nodes a and b can be coalesced if the resulting node ab will have fewer than K neighbors of significant degree (i.e., having ≥ K edges). The coalescing is guaranteed not to turn a K -colorable graph into a non-K -colorable graph, because after the simplify phase has removed all the insignificantdegree nodes from the graph, the coalesced node will be adjacent only to those neighbors that were of significant degree. Since there are fewer than K of these, simplify can then remove the coalesced node from the graph. Thus if the original graph was colorable, the conservative coalescing strategy does not alter the colorability of the graph.
George: Nodes a and b can be coalesced if, for every neighbor t of a, either t already interferes with b or t is of insignificant degree. This coalescing is safe, by the following reasoning. Let S be the set of insignificant-degree neighbors of a in the original graph. If the coalescing were not done, simplify could remove all the nodes in S, leaving a reduced graph G₁. If the coalescing is done, then simplify can remove all the nodes in S, leaving a graph G₂. But G₂ is a subgraph of G₁ (the node ab in G₂ corresponds to the node b in G₁), and thus must be at least as easy to color.

These strategies are conservative, because there are still safe situations in which they will fail to coalesce. This means that the program may perform some unnecessary MOVE instructions - but this is better than spilling! Interleaving simplification steps with conservative coalescing eliminates most move instructions, while still guaranteeing not to introduce spills. The coalesce, simplify, and spill procedures should be alternated until the graph is empty, as shown in Image 11.4.
Image 11.4: Graph coloring with coalescing.

These are the phases of a register allocator with coalescing: Build: Construct the interference graph, and categorize each node as either move-related or non-move-related. A move-related node is one that is either the source or destination of a move instruction. Simplify: One at a time, remove non-move-related nodes of low (< K ) degree from the graph. Coalesce: Perform conservative coalescing on the reduced graph obtained in the simplification phase. Since the degrees of many nodes have been reduced by simplify, the conservative strategy is likely to find many more moves to coalesce than it would have in the initial interference graph. After two nodes have been coalesced (and the move instruction deleted), if the resulting node is no longer move-related, it will be available for the next round of simplification. Simplify and coalesce are repeated until only significant-degree or move-related nodes remain. Freeze: If neither simplify nor coalesce applies, we look for a move-related node of low degree. We freeze the moves in which this node is involved: That is, we give up hope of coalescing those moves. This causes the node (and perhaps other nodes related to the frozen moves) to be considered non-move-related, which should enable more simplification. Now, simplify and coalesce are resumed. Spill: If there are no low-degree nodes, we select a significant-degree node for potential spilling and push it on the stack. Select: Pop the entire stack, assigning colors. Consider Graph 11.1; nodes b, c, d, and j are the only move-related nodes. The initial work list used in the simplify phase must contain only non-moverelated nodes and consists of nodes g, h, and f. Once again, after removal of g, h, and k we obtain Graph 11.2. We could continue the simplification phase further; however, if we invoke a round of coalescing at this point, we discover that c and d are indeed coalesceable as the coalesced node has only two neighbors of significant degree: m and b. The resulting graph is shown in Graph 11.5a, with the coalesced node labeled as c&d.GRAPH 11.5: (a) after coalescing c and d; (b) after coalescing b and j.

From Graph 11.5a we see that it is possible to coalesce b and j as well. Nodes b and j are adjacent to two neighbors of significant degree, namely m and e. The result of coalescing b and j is shown in Graph 11.5b. After coalescing these two moves, there are no more move-related nodes, and therefore no more coalescing is possible. The simplify phase can be invoked one more time to remove all the remaining nodes. A possible assignment of colors is shown in Image 11.6.
Image 11.6: A coloring, with coalescing, for Graph 11.1.

Some moves are neither coalesced nor frozen. Instead, they are constrained. Consider the graph x, y, z, where (x, z) is the only interference edge and there are two moves x ← y and y ← z. Either move is a candidate for coalescing. But after x and y are coalesced, the remaining move xy ← z cannot be coalesced because of the interference edge (xy, z). We say this move is constrained, and we remove it from further consideration: It no longer causes nodes to be treated as move-related.

SPILLING

If spilling is necessary, build and simplify must be repeated on the whole program. The simplest version of the algorithm discards any coalescences found if build must be repeated. Then it is easy to see that coalescing does not increase the number of spills in any future round of build. A more efficient algorithm preserves any coalescences done before the first potential spill was discovered, but discards (uncoalesces) any coalescences done after that point. Coalescing of spills On a machine with many registers (> 20), there will usually be few spilled nodes. But on a six-register machine (such as the Intel Pentium), there will be many spills. The front end may have generated many temporaries, and transformations such as SSA (described in ) may split them into many more temporaries. If each spilled temporary lives in its own stack-frame location, then the frame may be quite large. Even worse, there may be many move instructions involving pairs of spilled nodes. But to implement a ← b when a and b are both spilled temporaries requires a fetch-store sequence, t ← M[b_loc]; M[a_loc] ← t. This is expensive, and also defines a temporary t that itself may cause other nodes to spill. But many of the spill pairs are never live simultaneously. Thus, they may be graph-colored, with coalescing! In fact, because there is no fixed limit to the number of stack-frame locations, we can coalesce aggressively, without worrying about how many high-degree neighbors the spill nodes have. The algorithm is thus:

Use liveness information to construct the interference graph for spilled nodes.
While there is any pair of noninterfering spilled nodes connected by a move instruction, coalesce them.
Use simplify and select to color the graph. There is no (further) spilling in this coloring; instead, simplify just picks the lowest-degree node, and select picks the first available color, without any predetermined limit on the number of colors.
The colors correspond to activation-record locations for the spilled variables.

This should be done before generating the spill instructions and regenerating the register-temporary interference graph, so as to avoid creating fetch-store sequences for coalesced moves of spilled nodes.