Evaluating Expressions with an Insufficient Supply of Registers
Introduction: When there are fewer registers available than the label of the root of the tree, we cannot apply Algorithm 8.24 directly. We need to introduce some store instructions that spill values of subtrees into memory, and we then need to load those values back into registers as needed. Here is the modified algorithm that takes into account a limitation on the number of registers.
Algorithm: Generating code from a labeled expression tree.
INPUT: A labeled tree with each operand appearing once (i.e., no common subexpressions) and a number of registers r > 2.
OUTPUT: An optimal sequence of machine instructions to evaluate the root into a register, using no more than r registers, which we assume are Ri, R2, •.. ,Rr-
METHOD: Apply the following recursive algorithm, starting at the root of the tree, with base 6 = 1. For a node JV with label r or less, the algorithm is exactly the same as Algorithm 8.24, and we shall not repeat those steps here. However, for interior nodes with a label k > r, we need to work on each side of the tree separately and store the result of the larger subtree. That result is brought back into memory just before node iV is evaluated, and the final step will take place in registers Rr-\ and Rr- The modifications to the basic algorithm are as follows:
1. Node N has at least one child with label r or greater. Pick the larger child (or either if their labels are the same) to be the "big" child and let the other child be the "little" child.
2. Recursively generate code for the big child, using base 6 = 1. The result of this evaluation will appear in register Rr.
3. Generate the machine instruction ST tk,Rr, where is a temporary variable used for temporary results used to help evaluate nodes with label k.
4. Generate code for the little child as follows. If the little child has label r or greater, pick base 6 = 1 . If the label of the little child is j < r, then pick 6 = r — j. Then recursively apply this algorithm to the little child; the result appears in Rr.
5. Generate the instruction LD Rr^i,tk-
6. If the big child is the right child of N, then generate the instruction
OP Rr, Rr, Rr-\. If the big child is the left child, generate OP Rr, Rr-i, Rr-
Example: Let us revisit the expression represented by Fig. 8.23, but now assume that r = 2; that is, only registers Rl and R2 are available to hold temporaries used in the evaluation of expressions. When we apply Algorithm 8.26 to Fig. 8.23, we see that the root, with label 3, has a label that is larger than r = 2. Thus, we need to identify one of the children as the "big" child. Since they have equal labels, either would do. Suppose we pick the right child as the big child.
Since the label of the big child of the root is 2, there are enough registers.
We thus apply Algorithm 8.24 to this subtree, with 6 = 1 and two registers. The result looks very much like the code we generated in Fig. 8.24, but with registers Rl and R2 in place of R2 and R3. This code is
LD R2, d
LD Rl, c
ADD R2, Rl, R2
LD Rl, e
MUL R2, Rl, R2
Now, since we need both registers for the left child of the root, we need to generate the instruction
ST t3, R2
Next, the left child of the root is handled. Again, the number of registers is sufficient for this child, and the code is
LD R2, b
LD Rl, a
SUB R2, Rl, R2
Finally, we reload the temporary that holds the right child of the root with the instruction
LD Rl, t3
and execute the operation at the root of the tree with the instruction
ADD R2, R2, Rl
The complete sequence of instructions is shown in Fig. 8.25.