GRAPH-COLORING IMPLEMENTATION

The graph-coloring algorithm needs to query the interference-graph data structure frequently. There are two kinds of queries:

Get all the nodes adjacent to node X; and
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 not query 1. Therefore, we need both data structures to (redundantly) represent the interference graph. 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're used in standard calling conventions, they interfere with any temporaries that happen to be live near any of the procedure-calls in the program. But we don't need to represent the adjacency 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 space and time, we do not explicitly represent the adjacency lists of the machine registers. We coalesce an ordinary node a with a machine register r using the George coalescing test, which needs the adjacency list of a but not of r. To test whether two ordinary (non-precolored) nodes can be coalesced, the algorithm shown here uses the Briggs coalescing test. Associated with each move-related node is a count of the moves it is involved in. This count is easy to maintain and is used to test if a node is no longer move-related. Associated with all nodes is a count of the number of neighbors currently in the graph. This is used to determine whether a node is of significant degree during coalescing, and whether a node can be removed from the graph during simplification. It is important to be able to quickly perform each simplify step (removing a low-degree non-move-related node), each coalesce step, and each freeze step. To do this, we maintain four work 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 STRUCTURES

The 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 disjoint and 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 is added 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 contain an enumeration value telling which set it is in. Since nodes must frequently be added to and removed 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 are nonempty. Move sets There are five sets of move instructions, and every move is in exactly one of these sets (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, with each move containing an enumeration value identifying which set it belongs to. When a node x changes from significant to low-degree, the moves associated with its neighbors must be added to the move work list. Moves that were blocked with too many significant 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 temporary u, 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 is initialized to the given color.

INVARIANTS

After Build, the following invariants always hold: Degree invariant Java ScreenShot

Simplify worklist invariant Either u has been selected for spilling, or Java ScreenShot

Freeze worklist invariant Java ScreenShot

Spill worklist invariant. Java ScreenShot

PROGRAM CODE

The algorithm is invoked using the procedure Main, which loops (via tail recursion) until no spills are generated.

procedure Main()
 LivenessAnalysis()
 Build() MakeWorklist()
 repeat if simplifyWorklist ≠ {} then Simplify()
 else if worklistMoves ≠ {} then Coalesce()
 else if freezeWorklist ≠ {} then Freeze()
 else if spillWorklist ≠ {} then SelectSpill()
 until simplifyWorklist = {} ∧ worklistMoves = {}
 ∧ freezeWorklist = {} ∧ spillWorklist = {}
 AssignColors()
 if spilledNodes ≠ {} then
 RewriteProgram(spilledNodes)
 Main()

If AssignColors spills, then RewriteProgram allocates memory locations for the spilled temporaries and inserts store and fetch instructions to access them. These stores and fetches are to newly created temporaries (with tiny live ranges), so the main loop must be performed on the altered graph.

procedure Build ()
 forall b ∈ blocks in program
 let live = liveOut(b)
 forall I ∈ instructions(b) in reverse order
 if isMoveInstruction(I) then
 live ← live/use(I
 forall n ∈ def(I) ∪ use(I)
 moveList[n] ← moveList[n] ∪ {I}
 worklistMoves ← worklistMoves ∪ {I}
 live ← live ∪ def(I)
 forall d ∈ def(I)
 forall l ∈ live
 AddEdge(l, d)
 live ← use(I) ∪ (live/def(I))

Procedure Build constructs the interference graph (and bit matrix) using the results of static liveness analysis, and also initializes the worklistMoves to contain all the moves in the program.

procedure AddEdge(u, v)
 if ((u, v) ∉ adjSet) ∧ (u ≠ v) then
 adjSet ← adjSet ∪[(u, v), (v, u)]
 if u ∉ precolored then
 adjList[u] ← adjList[u] ∪ {v}
 degree[u] ← degree[u] + 1
 if v ∉ precolored then
 adjList[v] ← adjList[v] ∪ {u}
 degree[v] ← degree[v] + 1
procedure MakeWorklist()
 forall n ∈ initial
 initial ← initial / {n}
 if degree[n] ≥ K then
 spillWorklist ← spillWorklist ∪ {n}
 else if MoveRelated(n) then
 freezeWorklist ← freezeWorklist ∪ {n}
 else
 simplifyWorklist ← 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 ∈ simplifyWorklist
 simplifyWorklist ← 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. If the degree of a neighbor is already less than K − 1, then the neighbor must be move-related, and is not added to the simplifyWorklist. When the degree of a neighbor transitions from K to K − 1, moves associated with its neighbors may be enabled.

procedure DecrementDegree(m)
 let d = degree[m]
 degree[m] ← d-1
 if d = K then
 EnableMoves({m} ∪ Adjacent(m))
 spillWorklist ← spillWorklist / {m}
 if MoveRelated(m) then
 freezeWorklist ← freezeWorklist ∪ {m}
 else
 simplifyWorklist ← simplifyWorklist ∪ {m}
procedure EnableMoves(nodes)
 forall n ∈ nodes
 forall m ∈ NodeMoves(n)
 if m ∈ activeMoves then
 activeMoves ← activeMoves / {m}
 worklistMoves worklistMoves ∪ {m}

Only moves in the worklistMoves are considered in the coalesce phase. When a move is coalesced, it may no longer be move-related and can be added to the simplify work list by the procedure AddWorkList. OK implements the heuristic used for coalescing a precolored register. Conservative implements the conservative coalescing heuristic.

procedure AddWorkList(u)
 if (u ≠ precolored ∧ not(MoveRelated(u)) ∧ degree[u] < K) then
 freezeWorklist ← freezeWorklist / {u}
 simplifyWorklist ← simplifyWorklist ∪ {u}
function OK(t, r)
 degree[t] < K ∩ t ∈ precolored ∩ (t, r) ∈ adjSet
function Conservative(nodes)
 let k = 0
 forall n ∈ nodes
 if degree[n] ≥ K then k ← k + 1
 return (k < K)
procedure Coalesce()
 let m=copy(x, y)) ∈ worklistMoves
 x ← GetAlias(x)
 y ← GetAlias(y)
 if y ∈ precolored then let (u, v) = (y, x)
 else let (u, v) = (x, y)
 worklistMoves ← worklistMoves / {m}
 if (u = v) then
 coalescedMoves ← coalescedMoves ∪ {m}
 AddWorkList(u)
 else if v ∈ precolored ∩ (u, v) ∈ adjSet then
 constrainedMoves ← constrainedMoves ∪ {m}
 AddWorkList(u)
 AddWorkList(v)
 else if u ∈ precolored ∧ (∀t ∈ Adjacent(v, OK(t, u/)
 ∩ u ∉ precolored ∧
 Conservative(Adjacent(u) ∪ Adjacent(v) then
 coalescedMoves ← coalescedMoves ∪ {m}
 Combine(u, v)
 AddWorkList(u)
 else
 activeMoves ← activeMoves ∪ {m}
procedure Combine(u, v)
 if v ∈ freezeWorklist then
 freezeWorklist freezeWorklist / {v}
 else
 spillWorklist ← spillWorklist / {v}
 coalescedNodes ← coalescedNodes ∪ {v}
 alias[v] ← u
 moveList[u] ← moveList[u] ∪ moveList[v]
 EnableMoves(v)
 forall t ∈ Adjacent(v)
 AddEdge(t,u)
 DecrementDegree(t)
 if degree[u] ≥ K ∧ u ∈ freezeWorkList
 freezeWorkList ← freezeWorkList / {u}
 spillWorkList ← spillWorkList ∪ {u}
function GetAlias (n)
 if n ∈ coalescedNodes then
 GetAlias(alias[n])
 else n
procedure Freeze()
 let u ∈ freezeWorklist
 freezeWorklist ← freezeWorklist / {u}
 simplifyWorklist ← simplifyWorklist ∪ {u}
 FreezeMoves(u)
procedure FreezeMoves(u)
 forall m_{(=copy(x, y))} ∈ NodeMoves(u)
 if GetAlias(y)=GetAlias(u) then
 v ← GetAlias(x)
 else
 v ← GetAlias(y)
 activeMoves ← activeMoves / {m}
 frozenMoves ← frozenMoves ∪ {m}
 if v ∈ freezeWorklist ∧ NodeMoves(v) = {} then
 freezeWorklist ← freezeWorklist / {v}
 simplifyWorklist simplifyWorklist ∪ {v}
procedure SelectSpill()
 let m ∈ spillWorklist selected using favorite heuristic Note: avoid choosing nodes that are the tiny live ranges resulting from the fetches of previously spilled registers
 spillWorklist ← spillWorklist / {m}
 simplifyWorklist ← simplifyWorklist ∪ {m}
 FreezeMoves(m)
procedure AssignColors()
 while SelectStack not empty
 let n = pop(SelectStack)
 okColors ← {0,...,K-1}
 forall w ∈ adjList[n]
 if GetAlias(w) ∈ (coloredNodes ∪ precolored) then
 okColors ← okColors / {color[GetAlias(w)]}
 if okColors Dfg then
 spilledNodes ← spilledNodes ∪ {n}
 else
 coloredNodes ← coloredNodes ∪ {n}
 let c ∈ okColors
 color[n] c
 forall n ∈ coalescedNodes
 color[n] ← color[GetAlias(n)]
procedure RewriteProgram()
 Allocate memory locations for each v ∈ spilledNodes,
 Create a new temporary v_i for each definition and each use,
 In the program (instructions), insert a store after each
 definition of a v_i, a fetch before each use of a v_i.
 Put all the v_i into a set newTemps.
 spilledNodes ← {}
 initial ← coloredNodes ∪ coalescedNodes ∪ newTemps
 coloredNodes ← {}
 coalescedNodes ← {}

We show a variant of the algorithm in which all coalesces are discarded if the program must be rewritten to incorporate spill fetches and stores. For a faster algorithm, keep all the coalesces found before the first call to SelectSpill and rewrite the program to eliminate the coalesced move instructions and temporaries.

In principle, a heuristic could be used to select the freeze node; the Freeze shown above picks an arbitrary node from the freeze work list. But freezes are not common, and a selection heuristic is unlikely to make a significant difference.