REGISTER ALLOCATION FOR TREES

Register allocation for expression trees is much simpler than for arbitrary flow graphs. We do not need global dataflow analysis or interference graphs. Suppose we have a tiled tree such as in Image 9.2a. This tree has two trivial tiles, the TEMP nodes fp and i, which we assume are already in registers r_fp and r_i . We wish to label the roots of the nontrivial tiles (the ones corresponding to instructions, i.e., 2, 4, 5, 6, 8) with registers from the list r₁, r₂,…, r_k. Algorithm 11.9 traverses the tree in postorder, assigning a register to the root of each tile. With n initialized to zero, this algorithm applied to the root (tile 9) produces the allocation {tile2 ↦ r₁, tile4 ↦ r₂, tile5 ↦ r₂, tile6 ↦ r₁, tile8 ↦ r₂, tile9 ↦ r₁}. The algorithm can be combined with Maximal Munch, since both algorithms are doing the same bottom-up traversal.ALGORITHM 11.9: Simple register allocation on trees.

function SimpleAlloc(t)
 for each nontrivial tile u that is a child of t
 SimpleAlloc(u)
 for each nontrivial tile u that is a child of t
 n ← n - 1
 n ← n + 1
 assign rn to hold the value at the root of t

But this algorithm will not always lead to an optimal allocation. Consider the following tree, where each tile is shown as a single node:

The SimpleAlloc function will use three registers for this expression (as shown at left on the next page), but by reordering the instructions we can do the computation using only two registers (as shown at right):

Using dynamic programming, we can find the optimal ordering for the instructions. The idea is to label each tile with the number of registers it needs during its evaluation. Suppose a tile t has two nontrivial children u_left and u_right that require n and m registers, respectively, for their evaluation. If we evaluate u_left first, and hold its result in one register while we evaluate u_right, then we have needed max(n, 1 + m) registers for the whole expression rooted at t. Conversely, if we evaluate u_right first, then we need max(1 + n, m) registers. Clearly, if n > m, we should evaluate u_left first, and if n < m, we should evaluate u_right first. If n = m, we will need n + 1 registers no matter which subexpression is evaluated first. Algorithm 11.10 labels each tile t with need[t], the number of registers needed to evaluate the subtree rooted at t. It can be generalized to handle tiles with more than two children. Maximal Munch should identify - but not emit - the tiles, simultaneously with the labeling of Algorithm 11.10. The next pass emits Assem instructions for the tiles; wherever a tile has more than one child, the subtrees must be emitted in decreasing order of register need.ALGORITHM 11.10: Sethi-Ullman labeling algorithm.

function Label(t)
 for each tile u that is a child of t
 Label(u)
 if t is trivial
 then need[t] ← 0
 else if t has two children, uleft and uright
 then if need[uleft] = need[uright]
 then need[t] ← 1 + need[uleft]
 else need[t] ← max(1, need[uleft], need[uright])
 else if t has one child, u
 then need[t] ← max(1, need[u]
 else if t has no children
 then need[t] ← 1

Algorithm 11.10 can profitably be used in a compiler that uses graph-coloring register allocation. Emitting the subtrees in decreasing order of need will minimize the number of simultaneously live temporaries and reduce the number of spills. In a compiler without graph-coloring register allocation, Algorithm 11.10 is used as a pre-pass to Algorithm 11.11, which assigns registers as the trees are emitted and also handles spilling cleanly. This takes care of register allocation for the internal nodes of expression trees; allocating registers for explicit TEMPsofthe Tree language would have to be done in some other way. In general, such a compiler would keep almost all program variables in the stack frame, so there would not be many of these explicit TEMPs to allocate.ALGORITHM 11.11: Sethi-Ullman register allocation for trees.

function SethiUllman(t, n)
 if t has two children, uleft and uright
 if need[uleft] ≥ K ∧ need[uright] ≥ K
 SethiUllman(uright, 0)
 n ← n - 1
 spill: emit instruction to store reg[uright]
 SethiUllman(uleft, 0)
 unspill: reg[uright] ← "r1"; emit instruction to fetch reg[uright]
 else if need[uleft] ≥ need[uright]
 SethiUllman(uleft, n)
 SethiUllman(uright, n + 1)
 else need[uleft] < need[uright]
 SethiUllman(uright, n)
 SethiUllman(uleft, n)
 reg[t] ← "rn"
 emit OPER(instruction[t], reg[t], [ reg[uleft], reg[uright]])
 else if t has one child, u
 SethiUllman(u, n)
 reg[t] ← "rn"
 emit OPER(instruction[t], reg[t], [reg[u]])
 else if t is nontrivial but has no children
 reg[t] ← "rn"
 emit OPER(instruction[t], reg[t], [])
 else if t is a trivial node TEMP(ri)
 reg[t] ← "ri"