12.2 Code Generation for Trees

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, T

where 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, T

For example, for the expression (A-B)+((C+D)+(E*F)), which corresponds to the AST:

          +
        /   \
       /      \
      -        +
     / \     /   \
    A   B   +     *
           / \   / \
          C   D E   F

we 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, R2

That 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   0

The 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.