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

The resulting graph is shown inGraph 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 areadjacent to two neighbors of significant degree, namely m and e. The result of coalescing band j is shown in Graph 11.5b.After coalescing these two moves, there are no more move-related nodes, and therefore nomore coalescing is possible.

The simplify phase can be invoked one more time to remove allthe remaining nodes. A possible assignment of colors is shown in Figure 11.6.192Figure 11.6: A coloring, with coalescing, for Graph 11.1.Some moves are neither coalesced nor frozen.

Instead, they are constrained. Consider thegraph 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 remainingmove xy ← z cannot be coalesced because of the interference edge (xy, z). We say this moveis constrained, and we remove it from further consideration: It no longer causes nodes to betreated as move-related.SPILLINGIf spilling is necessary, build and simplify must be repeated on the whole program.

Thesimplest 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 futureround of build. A more efficient algorithm preserves any coalescences done before the firstpotential spill was discovered, but discards (uncoalesces) any coalescences done after thatpoint.Coalescing of spills On a machine with many registers (> 20), there will usually be fewspilled nodes. But on a six-register machine (such as the Intel Pentium), there will be manyspills. The front end may have generated many temporaries, and transformations such as SSA(described in Chapter 19) may split them into many more temporaries. If each spilledtemporary 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 toimplement a ← b when a and b are both spilled temporaries requires a fetch-store sequence, t← M[bloc]; M[aloc] ← t. This is expensive, and also defines a temporary t that itself may causeother 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-framelocations, we can coalesce aggressively, without worrying about how many high-degreeneighbors the spill nodes have.

The algorithm is thus:1. Use liveness information to construct the interference graph for spilled nodes.2. While there is any pair of noninterfering spilled nodes connected by a moveinstruction, coalesce them.3. Use simplify and select to color the graph. There is no (further) spilling in thiscoloring; instead, simplify just picks the lowest-degree node, and select picks the firstavailable color, without any predetermined limit on the number of colors.4.

The colors correspond to activation-record locations for the spilled variables.193This should be done before generating the spill instructions and regenerating the registertemporary interference graph, so as to avoid creating fetch-store sequences for coalescedmoves of spilled nodes.11.3 PRECOLORED NODESSome temporaries are precolored - they represent machine registers. The front end generatesthese when interfacing to standard calling conventions across module boundaries, forexample. For each actual register that is used for some specific purpose, such as the framepointer, standard-argument-1-register, standard-argument-2-register, and so on, the Codegenor Frame module should use the particular temporary that is permanently bound to thatregister (see also page 251).

For any given color (that is, for any given machine register) thereshould be only one precolored node of that color.The select and coalesce operations can give an ordinary temporary the same color as aprecolored register, as long as they don't interfere, and in fact this is quite common. Thus, astandard calling-convention register can be reused inside a procedure as a temporary variable.Precolored nodes may be coalesced with other (non-precolored) nodes using conservativecoalescing.For a K-register machine, there will be K precolored nodes that all interfere with each other.Those of the precolored nodes that are not used explicitly (in a parameter-passing convention,for example) will not interfere with any ordinary (non-precolored) nodes; but a machineregister used explicitly will have a live range that interferes with any other variables thathappen to be live at the same time.We cannot simplify a precolored node - this would mean pulling it from the graph in the hopethat we can assign it a color later, but in fact we have no freedom about what color to assignit.

And we should not spill precolored nodes to memory, because the machine registers are bydefinition registers. Thus, we should treat them as having "infinite" degree.TEMPORARY COPIES OF MACHINE REGISTERSThe coloring algorithm works by calling simplify, coalesce, and spill until only the precolorednodes remain, and then the select phase can start adding the other nodes (and coloring them).Because precolored nodes do not spill, the front end must be careful to keep their live rangesshort. It can do this by generating MOVE instructions to move values to and from precolorednodes.

For example, suppose r7 is a callee-save register; it is "defined" at procedure entry and"used" at procedure exit. Instead of being kept in a precolored register throughout theprocedure (Figure 11.7a), it can be moved into a fresh temporary and then moved back(Figure 11.7b). If there is register pressure (a high demand for registers) in this function, t231will spill; otherwise t231 will be coalesced with r7 and the MOVE instructions will beeliminated.Figure 11.7: Moving a callee-save register to a fresh temporary.194CALLER-SAVE AND CALLEE-SAVE REGISTERSA local variable or compiler temporary that is not live across any procedure call shouldusually be allocated to a caller-save register, because in this case no saving and restoring ofthe register will be necessary at all. On the other hand, any variable that is live across severalprocedure calls should be kept in a callee-save register, since then only one save/restore willbe necessary (on entry/exit from the calling procedure).How can the register allocator allocate variables to registers using this criterion? Fortunately,a graph-coloring allocator can do this very naturally, as a byproduct of ordinary coalescingand spilling.

All the callee-save registers are considered live on entry to the procedure, and areused by the return instruction. The CALL instructions in the Assem language have beenannotated to define (interfere with) all the caller-save registers. If a variable is not live acrossa procedure call, it will tend to be allocated to a caller-save register.If a variable x is live across a procedure call, then it interferes with all the caller-save(precolored) registers, and it interferes with all the new temporaries (such as t231 in Figure11.7) created for callee-save registers. Thus, a spill will occur.

Using the common spill-costheuristic that spills a node with high degree but few uses, the node chosen for spilling will notbe x but t231. Since t231 is spilled, r7 will be available for coloring x (or some other variable).Essentially, the callee saves the callee-save register by spilling t231.EXAMPLE WITH PRECOLORED NODESA worked example will illustrate the issues of register allocation with precolored nodes,callee-save registers, and spilling.A C compiler is compiling Program 11.8a for a target machine with three registers; r1 and r2are caller-save, and r3 is callee-save.

The code generator has therefore made arrangements topreserve the value of r3 explicitly, by copying it into the temporary c and back again.PROGRAM 11.8: A C function and its translation into instructionsThe instruction-selection phase has produced the instruction list of Program 11.8b.

Theinterference graph for this function is shown at right.195The register allocation proceeds as follows (with K = 3):1. In this graph, there is no opportunity for simplify orfreeze (because all the non-precolored nodes have degree≥ K ). Any attempt to coalesce would produce acoalesced node adjacent to K or more significant-degreenodes. Therefore we must spill some node.

We calculatespill priorities as follows:Uses+Defsoutside loopNodeabcde(((((21221+ 10 ×+ 10 ×+ 10 ×+ 10 ×+ 10 ×Uses+DefsDegreewithin loop01023)/)/)/)/)/44643Spillpriority=====0.502.750.335.5010.332. Node c has the lowest priority - it interferes with manyother temporaries but is rarely used - so it should bespilled first. Spilling c, we obtain the graph at right.2. We can now coalesce a and e, since the resulting nodewill be adjacent to fewer than K significant-degree nodes(after coalescing, node d will be low-degree, though it issignificant-degree right now). No other simplify orcoalesce is possible now.3.