Register Assignment for Outer Loops
Introduction: Having assigned registers and generated code for inner loops, we may apply the same idea to progressively larger enclosing loops. If an outer loop L\ contains an inner loop L2, the names allocated registers in L2 need not be allocated registers in L\ — L2. Similarly, if we choose to allocate x a register in L2 but not Li, we must load x on entrance to L2 and store x on exit from L2. We leave as an exercise the derivation of a criterion for selecting names to be allocated registers in an outer loop L, given that choices have already been made for all loops nested within L.
Register Allocation by Graph Coloring: When a register is needed for a computation but all available registers are inuse, the contents of one of the used registers must be stored (spilled) into amemory location in order to free up a register. Graph coloring is a simple,systematic technique for allocating registers and managing register spills.In the method, two passes are used. In the first, target-machine instructionsare selected as though there are an infinite number of symbolic registers;in effect, names used in the intermediate code become names of registers and the three-address instructions become machine-language instructions. If access to variables requires instructions that use stack pointers, display pointers, base registers, or other quantities that assist access, then we assume that these quantities are held in registers reserved for each purpose. Normally, their use is directly translatable into an access mode for an address mentioned in a machine instruction. If access is more complex, the access must be broken into several machine instructions, and a temporary symbolic register (or several) may need to be created.
Once the instructions have been selected, a second pass assigns physical registers to symbolic ones. The goal is to find an assignment that minimizes the cost of spills.
In the second pass, for each procedure a register-interference graph is constructed in which the nodes are symbolic registers and an edge connects two nodes if one is live at a point where the other is defined. For example, a register interference graph for Fig. 8.17 would have nodes for names a and d. In block By, a is live at the second statement, which defines d; therefore, in the graph there would be an edge between the nodes for a and d.
An attempt is made to color the register-interference graph using k colors, where k is the number of assignable registers. A graph is said to be colored if each node has been assigned a color in such a way that no two adjacent nodes have the same color. A color represents a register, and the color makes sure that no two symbolic registers that can interfere with each other are assigned the same physical register.
Although the problem of determining whether a graph is fc-colorable is NP complete in general, the following heuristic technique can usually be used to do the coloring quickly in practice. Suppose a node n in a graph G has fewer than k neighbors (nodes connected to n by an edge). Remove n and its edges from G to obtain a graph G'. A ^-coloring of G' can be extended to a fc-coloring of G by assigning n a color not assigned to any of its neighbors. By repeatedly eliminating nodes having fewer than k edges from the register interference graph, either we obtain the empty graph, in which case we can produce a ^-coloring for the original graph by coloring the nodes in the reverse order in which they were removed, or we obtain a graph in which each node has k or more adjacent nodes. In the latter case a ^-coloring is no longer possible. At this point a node is spilled by introducing code to store and reload the register. Chaitin has devised several heuristics for choosing the node to spill. A general rule is to avoid introducing spill code into inner loops.