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

Now we could coalesce ae&r1 or coalesce b&r2. Let usdo the latter.4. We can now coalesce either ae&r1 or coalesce d&r1. Letus do the former.5. We cannot now coalesce r1ae&d because the move isconstrained: The nodes r1ae and d interfere. We mustsimplify d.1966. Now we have reached a graph with only precolorednodes, so we pop nodes from the stack and assign colorsto them. First we pick d, which can be assigned color r3.Nodes a, b, and e have already been assigned colors bycoalescing.

But node c, which was a potential spill, turnsinto an actual spill when it is popped from the stack,since no color can be found for it.7. Since there was spilling in this round, we must rewritethe program to include spill instructions. For each use (ordefinition) of c, we make up a new temporary, and fetch(or store) it immediately beforehand (or afterward).8. Now we build a new interference graph:9. Graph-coloring proceeds as follows. We can immediatelycoalesce c1&r3 and then c2&r3.10.

Then, as before, we can coalesce a&e and then b&r2.11. As before, we can coalesce ae&r1 and then simplify d.12. Now we start popping from the stack: We select color r3 Node Colorfor d, and this was the only node on the stack - all other ar1nodes were coalesced or precolored. The coloring isr2bshown at right.r3cr3dr1e19713. Now we can rewrite the program using the registerassignment.14. Finally, we can delete any move instruction whosesource and destination are the same; these are the resultof coalescing.The final program has only one uncoalesced move instruction.11.4 GRAPH-COLORING IMPLEMENTATIONThe graph-coloring algorithm needs to query the interference-graph data structure frequently.There are two kinds of queries:1.

Get all the nodes adjacent to node X; and2. Tell if X and Y are adjacent.An adjacency list (per node) can answer query 1 quickly, but not query 2 if the lists are long.A two-dimensional bit matrix indexed by node numbers can answer query 2 quickly, but notquery 1. Therefore, we need both data structures to (redundantly) represent the interferencegraph. If the graph is very sparse, a hash table of integer pairs may be better than a bit matrix.The adjacency lists of machine registers (precolored nodes) can be very large; because they'reused in standard calling conventions, they interfere with any temporaries that happen to belive near any of the procedure-calls in the program. But we don't need to represent theadjacency list for a precolored node, because adjacency lists are used only in the select phase(which does not apply to precolored nodes) and in the Briggs coalescing test. To save spaceand time, we do not explicitly represent the adjacency lists of the machine registers.

Wecoalesce an ordinary node a with a machine register r using the George coalescing test, whichneeds the adjacency list of a but not of r.To test whether two ordinary (non-precolored) nodes can be coalesced, the algorithm shownhere uses the Briggs coalescing test.Associated with each move-related node is a count of the moves it is involved in. This countis easy to maintain and is used to test if a node is no longer move-related. Associated with allnodes is a count of the number of neighbors currently in the graph. This is used to determine198whether a node is of significant degree during coalescing, and whether a node can be removedfrom the graph during simplification.It is important to be able to quickly perform each simplify step (removing a low-degree nonmove-related node), each coalesce step, and each freeze step.

To do this, we maintain fourwork lists:••••Low-degree non-move-related nodes (simplifyWorklist);Move instructions that might be coalesceable (worklistMoves);Low-degree move-related nodes (freezeWorklist);High-degree nodes (spillWorklist).Using these work lists, we avoid quadratic time blowup in finding coalesceable nodes.DATA STRUCTURESThe algorithm maintains these data structures to keep track of graph nodes and move edges:Node work lists, sets, and stacks The following lists and sets are always mutually disjointand every node is always in exactly one of the sets or lists.••••••precolored: machine registers, preassigned a color.initial: temporary registers, not precolored and not yet processed.simplifyWorklist: list of low-degree non-move-related nodes.freezeWorklist: low-degree move-related nodes.spillWorklist: high-degree nodes.spilledNodes: nodes marked for spilling during this round; initially empty.•coalescedNodes: registers that have been coalesced; when u ← v is coalesced, v isadded to this set and u put back on some work list (or vice versa).coloredNodes: nodes successfully colored.selectStack: stack containing temporaries removed from the graph.••Since membership in these sets is often tested, the representation of each node should containan enumeration value telling which set it is in.

Since nodes must frequently be added to andremoved from these sets, each set can be represented by a doubly linked list of nodes. Initially(on entry to Main), and on exiting RewriteProgram, only the sets precolored and initial arenonempty.Move sets There are five sets of move instructions, and every move is in exactly one of thesesets (after Build through the end of Main).•••••coalescedMoves: moves that have been coalesced.constrainedMoves: moves whose source and target interfere.frozenMoves: moves that will no longer be considered for coalescing.worklistMoves: moves enabled for possible coalescing.activeMoves: moves not yet ready for coalescing.Like the node work lists, the move sets should be implemented as doubly linked lists, witheach move containing an enumeration value identifying which set it belongs to.199When a node x changes from significant to low-degree, the moves associated with itsneighbors must be added to the move work list.

Moves that were blocked with too manysignificant neighbors might now be enabled for coalescing.Other data structures.••••••adjSet: the set of interference edges (u, v) in the graph; if (u, v) 2 adjSet, then (v, u) ∈adjSet.adjList: adjacency list representation of the graph; for each non-precolored temporaryu, adjList[u] is the set of nodes that interfere with u.degree: an array containing the current degree of each node.moveList: a mapping from a node to the list of moves it is associated with.alias: when a move (u, v) has been coalesced, and v put in coalescedNodes, then alias(v) = u.color: the color chosen by the algorithm for a node; for precolored nodes this isinitialized to the given color.INVARIANTSAfter Build, the following invariants always hold:Degree invariantSimplify worklist invariant Either u has been selected for spilling, orFreeze worklist invariantSpill worklist invariant.PROGRAM CODEThe algorithm is invoked using the procedure Main, which loops (via tail recursion) until nospills are generated.procedure Main()LivenessAnalysis()Build() MakeWorklist()repeatif simplifyWorklist ≠ {} then Simplify()else if worklistMoves ≠ {} then Coalesce()200else if freezeWorklist ≠ {} then Freeze()else if spillWorklist ≠ {} then SelectSpill()until simplifyWorklist = {} ∧ worklistMoves = {}∧ freezeWorklist = {} ∧ spillWorklist = {}AssignColors()if spilledNodes ≠ {} thenRewriteProgram(spilledNodes)Main()If AssignColors spills, then RewriteProgram allocates memory locations for the spilledtemporaries and inserts store and fetch instructions to access them.

These stores and fetchesare to newly created temporaries (with tiny live ranges), so the main loop must be performedon the altered graph.procedure Build ()forall b ∈ blocks in programlet live = liveOut(b)forall I ∈ instructions(b) in reverse orderif isMoveInstruction(I) thenlive ← live/use(Iforall n ∈ def(I) ∪ use(I)moveList[n] ← moveList[n] ∪ {I}worklistMoves ← worklistMoves ∪ {I}live ← live ∪ def(I)forall d ∈ def(I)forall l ∈ liveAddEdge(l, d)live ← use(I) ∪ (live/def(I))Procedure Build constructs the interference graph (and bit matrix) using the results of staticliveness analysis, and also initializes the worklistMoves to contain all the moves in theprogram.procedure AddEdge(u, v)if ((u, v) ∉ adjSet) ∧ (u ≠ v) thenadjSet ← adjSet ∪[(u, v), (v, u)]if u ∉ precolored thenadjList[u] ← adjList[u] ∪ {v}degree[u] ← degree[u] + 1if v ∉ precolored thenadjList[v] ← adjList[v] ∪ {u}degree[v] ← degree[v] + 1procedure MakeWorklist()forall n ∈ initialinitial ← initial / {n}if degree[n] ≥ K thenspillWorklist ← spillWorklist ∪ {n}else if MoveRelated(n) thenfreezeWorklist ← freezeWorklist ∪ {n}else201simplifyWorklist ← simplifyWorklist ∪ {n}function Adjacent(n)adjList[n] / (selectStack ∪ coalescedNodes)function NodeMoves (n)moveList[n] ∩ (activeMoves ∪ worklistMoves)function MoveRelated(n)NodeMoves(n) ≠ {}procedure Simplify()let n ∈ simplifyWorklistsimplifyWorklist ← simplifyWorklist / {n}push(n, selectStack)forall m ∈ Adjacent(n)DecrementDegree(m)Removing a node from the graph involves decrementing the degree of its current neighbors.