A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 40

This leads naturally to a stack-based (or recursive)algorithm for coloring: We repeatedly remove (and push on a stack) nodes of degree less thanK. Each such simplification will decrease the degrees of other nodes, leading to moreopportunity for simplification.188Spill: Suppose at some point during simplification the graph G has nodes only of significantdegree, that is, nodes of degree ≥ K . Then the simplify heuristic fails, and we mark somenode for spilling. That is, we choose some node in the graph (standing for a temporaryvariable in the program) and decide to represent it in memory, not registers, during programexecution. An optimistic approximation to the effect of spilling is that the spilled node doesnot interfere with any of the other nodes remaining in the graph.

It can therefore be removedand pushed on the stack, and the simplify process continued.Select: We assign colors to nodes in the graph. Starting with the empty graph, we rebuild theoriginal graph by repeatedly adding a node from the top of the stack. When we add a node tothe graph, there must be a color for it, as the premise for removing it in the simplify phase wasthat it could always be assigned a color provided the remaining nodes in the graph could besuccessfully colored.When potential spill node n that was pushed using the Spill heuristic is popped, there is noguarantee that it will be colorable: Its neighbors in the graph may be colored with K differentcolors already.

In this case, we have an actual spill. We do not assign any color, but wecontinue the Select phase to identify other actual spills.But perhaps some of the neighbors are the same color, so that among them there are fewerthan K colors. Then we can color n, and it does not become an actual spill. This technique isknown as optimistic coloring.Start over: If the Select phase is unable to find a color for some node(s), then the programmust be rewritten to fetch them from memory just before each use, and store them back aftereach definition. Thus, a spilled temporary will turn into several new temporaries with tiny liveranges. These will interfere with other temporaries in the graph.

So the algorithm is repeatedon this rewritten program. This process iterates until simplify succeeds with no spills; inpractice, one or two iterations almost always suffice.EXAMPLEGraph 11.1 shows the interferences for a simple program. The nodes are labeled with thetemporaries they represent, and there is an edge between two nodes if they are simultaneouslylive. For example, nodes d, k, and j are all connected since they are live simultaneously at theend of the block.

Assuming that there are four registers available on the machine, then thesimplify phase can start with the nodes g, h, c, and f in its working set, since they have lessthan four neighbors each. A color can always be found for them if the remaining graph can besuccessfully colored. If the algorithm starts by removing h and g and all their edges, then nodek becomes a candidate for removal and can be added to the work list.

Graph 11.2 remainsafter nodes g, h, and k have been removed. Continuing in this fashion a possible order inwhich nodes are removed is represented by the stack shown in Figure 11.3a, where the stackgrows upward.GRAPH 11.1: Interference graph for a program. Dotted lines are not interference edges butindicate move instructions.189GRAPH 11.2: After removal of h, g, k.Figure 11.3: Simplification stack, and a possible coloring.The nodes are now popped off the stack and the original graph reconstructed and coloredsimultaneously.

Starting with m, a color is chosen arbitrarily since the graph at this pointconsists of a singleton node. The next node to be put into the graph is c. The only constraint isthat it be given a color different from m, since there is an edge from m to c. A possibleassignment of colors for the reconstructed original graph is shown in Figure 11.3b.19011.2 COALESCINGIt is easy to eliminate redundant move instructions with an interference graph. If there is noedge in the interference graph between the source and destination of a move instruction, thenthe move can be eliminated. The source and destination nodes are coalesced into a new nodewhose 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. Thisaggressive form of copy propagation is very successful at eliminating move instructions.Unfortunately, the node being introduced is more constrained than those being removed, as itcontains a union of edges.

Thus, it is quite possible that a graph, colorable with K colorsbefore coalescing, may no longer be K -colorable after reckless coalescing. We wish tocoalesce only where it is safe to do so, that is, where the coalescing will not render the graphuncolorable. Both of the following strategies are safe:Briggs: Nodes a and b can be coalesced if the resulting node ab will have fewer than Kneighbors of significant degree (i.e., having ≥ K edges). The coalescing is guaranteed not toturn a K -colorable graph into a non-K -colorable graph, because after the simplify phase hasremoved all the insignificantdegree nodes from the graph, the coalesced node will be adjacentonly 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 wascolorable, 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 alreadyinterferes with b or t is of insignificant degree. This coalescing is safe, by the followingreasoning. Let S be the set of insignificant-degree neighbors of a in the original graph. If thecoalescing were not done, simplify could remove all the nodes in S, leaving a reduced graphG1.

If the coalescing is done, then simplify can remove all the nodes in S, leaving a graph G2.But G2 is a subgraph of G1 (the node ab in G2 corresponds to the node b in G1), and thus mustbe at least as easy to color.These strategies are conservative, because there are still safe situations in which they will failto 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 moveinstructions, while still guaranteeing not to introduce spills.

The coalesce, simplify, and spillprocedures should be alternated until the graph is empty, as shown in Figure 11.4.Figure 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 ornon-move-related. A move-related node is one that is either the source or destination of amove instruction.191Simplify: One at a time, remove non-move-related nodes of low (< K ) degree from thegraph.Coalesce: Perform conservative coalescing on the reduced graph obtained in thesimplification phase. Since the degrees of many nodes have been reduced by simplify, theconservative strategy is likely to find many more moves to coalesce than it would have in theinitial interference graph. After two nodes have been coalesced (and the move instructiondeleted), if the resulting node is no longer move-related, it will be available for the next roundof simplification.

Simplify and coalesce are repeated until only significant-degree or moverelated nodes remain.Freeze: If neither simplify nor coalesce applies, we look for a move-related node of lowdegree. We freeze the moves in which this node is involved: That is, we give up hope ofcoalescing those moves. This causes the node (and perhaps other nodes related to the frozenmoves) 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 potentialspilling 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 worklist used in the simplify phase must contain only non-moverelated nodes and consists of nodesg, 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 ofcoalescing at this point, we discover that c and d are indeed coalesceable as the coalescednode has only two neighbors of significant degree: m and b.