next up previous contents
Next: 12.2 Code Generation for Up: 12 Register Allocation Previous: 12 Register Allocation   Contents

12.1 Register Allocation Using the Interference Graph

The interference graph is used for assigning registers to temporary variables. If two variables do not interfere (ie, there is no edge between these two variables in the interference graph) then we can use the same register for both of them, thus reducing the number of registers needed. On the other hand, if there is a graph edge between two variables, then we should not assign the same register to them since this register needs to hold the values of both variable at one point of time (because the lives of these variables overlap at one point of time - this is what interference means).

Suppose that we have n available registers: r1, r2,..., rn. If we view each register as a different color, then the register allocation problem for the interference graph is equivalent to the graph coloring problem where we try to assign one of the n different colors to graph nodes so that no two adjacent nodes have the same color. This algorithm is used in map drawing where we have countries or states on the map and we want to color them using a small fixed number of colors so that states that have a common border are not painted with the same color. The graph in this case has one node for each state and an edge between two states if they have common borders.

The register allocation algorithm uses a stack of graph nodes to insert all nodes of the interference graph one at a time. Each time it selects a node that has fewer than n neighbors (adjacent nodes). The idea is that if we can color the graph after we remove this node, then of course we can color the original graph (with the node included) because the neighbors of this node can have n - 1 different colors in the worst case; so we can just assign the available nth color to the node. This is called simplification of the graph. Each selected node is pushed in the stack. Sometimes though we cannot simplify any further because all nodes have n or more neighbors. In that case we select one node (ie. variable) to be spilled into memory instead of assigning a register to it. This is called spilling and the spilled victim can be selected based on priorities (eg. which variable is used less frequently, is it outside a loop, etc). The spilled node is also pushed on the stack. When the graph is completely reduced (and all nodes have been pushed in the stack), we pop the stack one node at a time, we rebuild the interference graph and at the same time we assign a color to the popped-out node so that its color is different from the colors of its neighbors. This is called the selection phase. If we can't assign a color to a node, we spill out the node into memory (a node selected to be spilled out during the spill phase does not necessarily mean that it will actually spilled into memory at the end). If there are spilled nodes, we use a memory access for each spilled variable (eg. we use the frame location $fp-24 to store the spilled temporary variable and we replace all occurrences of this variable in the program with M[$fp-24]). Then we restart the whole process (the building of the interference graph, simplification, etc) from the beginning. Figures 11.1-11.3 in Section 11.1 in the textbook give an example of this method.

Consider the following interference graph from the previous section:


The nodes are pushed in the stack in the order of xvuzyw. Then, at the selection phase, xyzwuv variables are assigned the registers R0R2R1R0R1R0.

If there is a move instruction in a program (ie. an assignment of the form a:=b) and there is no conflict between a and b, then it is a good idea to use the same register for both a and b so that you can remove the move instruction entirely from the program. In fact you can just merge the graph nodes for a and b in the graph into one node. That way nodes are now labeled by sets of variables, instead of just one variable. This is called coalescing. This is a good thing to do since it reduces the number of registers needed and it removes the move instructions, but it may be bad since it increases the number of neighbors of the merged nodes, which may lead to an irreducible graph and a potential spilling. To do this, we add another phase to the register allocation algorithm, called coalescing, that coalesces move related nodes. If we derive an irreducible graph at some point of time, there is another phase, called freezing, that de-coalesces one node (into two nodes) and continues the simplification.

A common criterion for coalescing is that we coalesce two nodes if the merged node has fewer than n neighbors of degree greater than or equal to n (where n is the number of available registers). This is called the Briggs criterion. A slight variation of this is the George criterion where we coalesce nodes if all the neighbors of one of the nodes with degree greater than or equal to n already interfere with the other node.

Coalescing is very useful when handling callee-save registers in a program. Recall that callee-save registers need to be saved by the callee procedure to maintain their values upon the exit of the procedure. Suppose that r3 is a callee-save register. The procedure needs to save this register into a temporary variable at the beginning of the procedure (eg. a := r3) and to restore it at the end of the procedure (ie. r3 := a). That way, if r3 is not used at all during the procedure body, it will be coalesced with a and the move instructions will be removed. But coalescing can happen in many other different situations as long as there is no interference, which makes this technique very general. Note that registers in a program are handled as temporary variables with a preassigned color (precolored nodes). This means that precolored nodes can only be coalesced with other nodes (they cannot be simplified or spilled). See the example in Section 11.3 in the textbook for a program with precolored nodes.

next up previous contents
Next: 12.2 Code Generation for Up: 12 Register Allocation Previous: 12 Register Allocation   Contents
fegaras 2012-01-10