Suppose that you want generate assembly code for complex expression trees using the fewest number of registers to store intermediate results. Suppose also that we have two-address instructions of the form
op Ri, Twhere op is an operation (add, sub, mult, etc), Ri is a register (R1, R2, R3, etc), and T is an address mode such as a memory reference, a register, indirect access, indexing etc. We also have a move instruction of the form:
load Ri, TFor example, for the expression
(A-B)+((C+D)+(E*F))
, which
corresponds to the AST:
+ / \ / \ - + / \ / \ A B + * / \ / \ C D E Fwe want to generate the following assembly code:
load R2, C add R2, D load R1, E mult R1, F add R2, R1 load R1, A sub R1, B add R1, R2That is, we used only two register.
There is an algorithm that generates code with the least number of
registers. It is called the Sethi-Ullman algorithm. It consists
of two phases: numbering and code generation. The
numbering phase assigns a number to each tree node that indicates how
many registers are needed to evaluate the subtree of this node.
Suppose that for a tree node T, we need l registers to evaluate
its left subtree and r registers to evaluate its right subtree.
Then if one of these numbers is larger, say l > r, then we can
evaluate the left subtree first and store its result into one of the
registers, say R_{k}. Now we can evaluate the right subtree using the
same registers we used for the left subtree, except of course R_{k}
since we want to remember the result of the left subtree. But this is
always possible since l > r. This means that we need l registers to
evaluate T too. The same happens if r > l but now we need to
evaluate the right subtree first and store the result to a register.
If l = r we need an extra register R_{l+1} to remember the result of
the left subtree. If T is a tree leaf, then the number of registers
to evaluate T is either 1 or 0 depending whether T is a left or a
right subtree (since an operation such as add R1, A
can handle
the right component A
directly without storing it into a
register). So the numbering algorithm starts from the tree leaves and
assigns 1 or 0 as explained. Then for each node whose children are
labeled l and r, if l = r then the node number is l + 1 otherwise
it is max(l, r). For example, we have the following numbering for the
previous example:
2 / \ / \ 1 2 / \ / \ 1 0 1 1 / \ / \ 1 0 1 0The code generation phase is as follows. We assume that for each node T has numbering regs(T). We use a stack of available registers which initially contains all the registers in order (with the lower register at the top).
generate(T) = | ||
if T is a leaf write ``load top(), T" | ||
if T is an internal node with children l and r then | ||
if regs(r) = 0 then { generate(l); write ``op top(), r" } | ||
if regs(l ) > = regs(r) | ||
then { | generate(l) | |
R := pop() | ||
generate(r) | ||
write ``op R, top()" | ||
push(R) } | ||
if regs(l ) < regs(r) | ||
then { | swap the top two elements of the stack | |
generate(r) | ||
R := pop() | ||
generate(l) | ||
write ``op top(), R" | ||
push(R) | ||
swap the top two elements of the stack } |
This assumes that the number of registers needed is no greater than the number of available registers. Otherwise, we need to spill the intermediate result of a node to memory. This algorithm also does not take advantage of the commutativity and associativity properties of operators to rearrange the expression tree.