Tech Report CS-92-13

Register Allocation Using Control Trees

Kathleen Knobe and Kenneth Zadeck

March 1992

Abstract:

Register allocation is like trying to fit blocks in a box. There are two distinct problems: first, the volume of the blocks may be too large for the box, and second, the shapes of the blocks may make the box difficult to pack. No matter how good your packing technique is, you cannot succeed if the volume of blocks is too large. On the other hand, that the volume of blocks is acceptable does not guarantee that the box can be packed.

In the analogy to register allocation, each live range associated with a candidate (object to be allocated) is a block. Other algorithms view blocks as having uniform density. Our blocks have {\em holes}, regions in which the candidate's live range is reference-free. We prune portions of the program where the number of live candidates is greater than the number of registers (the {\em register pressure} is too high) by storing the value in memory on entry to the region and reloading it on exit. It is always possible to prune enough that the volume of the candidates does not exceed the volume of the box.

In theory, once the volume problem is solved, packing is easy if one has a chainsaw: when something doesn't fit, cut it in two and try again. In practice, the problem is difficult to solve well because splitting has a cost: {\tt move} instructions must be inserted between the split regions. It is important to select not only the proper candidate to split but also the proper location of the split to facilitate packing the remaining blocks and also to minimize the costs of the {\tt move} instructions.

Both the pruning and the splitting use the {\em control tree} to take into account the program structure in determining costs. Since the algorithm uses the control tree to guide the pruning and splitting decisions, the algorithm is called {\em control-tree register allocation} algorithm.

(complete text in pdf)