Previous    Next

COLORING BY SIMPLIFICATION

Register allocation is an NP-complete problem (except in special cases, such as expression trees); graph coloring is also NP-complete. Fortunately there is a linear-time approximation algorithm that gives good results; its principal phases are Build, Simplify, Spill, and Select. Build: Construct the interference graph. We use dataflow analysis to compute the set of temporaries that are simultaneously live at each program point, and we add an edge to the graph for each pair of temporaries in the set. We repeat this for all program points. Simplify: We color the graph using a simple heuristic. Suppose the graph G contains a node m with fewer than K neighbors, where K is the number of registers on the machine. Let G′ be the graph G − {m} obtained by removing m. If G′ can be colored, then so can G, for when m is added to the colored graph G′, the neighbors of m have at most K − 1 colors among them, so a free color can always be found for m. This leads naturally to a stack-based (or recursive) algorithm for coloring: We repeatedly remove (and push on a stack) nodes of degree less than K. Each such simplification will decrease the degrees of other nodes, leading to more opportunity for simplification. Spill: Suppose at some point during simplification the graph G has nodes only of significant degree, that is, nodes of degree ≥ K . Then the simplify heuristic fails, and we mark some node for spilling. That is, we choose some node in the graph (standing for a temporary variable in the program) and decide to represent it in memory, not registers, during program execution. An optimistic approximation to the effect of spilling is that the spilled node does not interfere with any of the other nodes remaining in the graph. It can therefore be removed and 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 the original graph by repeatedly adding a node from the top of the stack. When we add a node to the graph, there must be a color for it, as the premise for removing it in the simplify phase was that it could always be assigned a color provided the remaining nodes in the graph could be successfully colored. When potential spill node n that was pushed using the Spill heuristic is popped, there is no guarantee that it will be colorable: Its neighbors in the graph may be colored with K different colors already. In this case, we have an actual spill. We do not assign any color, but we continue the Select phase to identify other actual spills. But perhaps some of the neighbors are the same color, so that among them there are fewer than K colors. Then we can color n, and it does not become an actual spill. This technique is known as optimistic coloring. Start over: If the Select phase is unable to find a color for some node(s), then the program must be rewritten to fetch them from memory just before each use, and store them back after each definition. Thus, a spilled temporary will turn into several new temporaries with tiny live ranges. These will interfere with other temporaries in the graph. So the algorithm is repeated on this rewritten program. This process iterates until simplify succeeds with no spills; in practice, one or two iterations almost always suffice.

EXAMPLE

Graph 11.1 shows the interferences for a simple program. The nodes are labeled with the temporaries they represent, and there is an edge between two nodes if they are simultaneously live. For example, nodes d, k, and j are all connected since they are live simultaneously at the end of the block. Assuming that there are four registers available on the machine, then the simplify phase can start with the nodes g, h, c, and f in its working set, since they have less than four neighbors each. A color can always be found for them if the remaining graph can be successfully colored. If the algorithm starts by removing h and g and all their edges, then node k becomes a candidate for removal and can be added to the work list. Graph 11.2 remains after nodes g, h, and k have been removed. Continuing in this fashion a possible order in which nodes are removed is represented by the stack shown in Image 11.3a, where the stack grows upward.

GRAPH 11.1: Interference graph for a program. Dotted lines are not interference edges but indicate move instructions.
Java Click To expand
Java End example
GRAPH 11.2: After removal of h, g, k.
Java Click To expand
Java End example
Java Click To expand
Image 11.3: Simplification stack, and a possible coloring.

The nodes are now popped off the stack and the original graph reconstructed and colored simultaneously. Starting with m, a color is chosen arbitrarily since the graph at this point consists of a singleton node. The next node to be put into the graph is c. The only constraint is that it be given a color different from m, since there is an edge from m to c. A possible assignment of colors for the reconstructed original graph is shown in Image 11.3b.


JaVaScreenshot Previous    Next
Comments