Exercise 12        Name __________________        Score __/10

1. (5) ALGORITHM 11.10 labeled the subtrees with register need and ALGORITHM 11.11 rearranged subtrees to allocate registers first to the one having the greatest need, thereby reducing the total number of registers required for the instruction tree. The stack space requirements of our compiler could have been reduced by similar means.

• Explain what we would need to do differently.
• Give AMinusExp node code generation assuming a getNeed(node.getSubtree()) method returns the stack need of subtree (i.e. similar to getStack, getInt, etc. used in homeworks).

The basic problem is to determine which of the left or right subtrees should be generated first; the one having the greatest need.

The current compiler labels an AST with stack need but only calculates and retains in the symbol table total stack need of a method. Two separate passes for the method stack need computation and code generation. Both passes work from the bottom-up of the AST and cannot easily be performed simultaneously because stack need determines which subtree code should be generated.

One solution has two passes over the same AST, the first pass labeling the need of each subtree; the second pass using need to select the subtree order in which to generate code. The AMinusExp subtree is labeled by the following algorithm:

public void caseAMinusExp(AMinusExp node){   node.getL().apply(this);   node.getR().apply(this);   int need = getNeed(node.getL()) == getNeed(node.getR()) ?         getNeed(node.getL())+1 :         max(2, getNeed(node.getL()), getNeed(node.getR()));   setNeed(node, need); }

The algorithm for minus code generation would be:

public void caseAMinusExp(AMinusExp node) {   if (getNeed(node.getL()) >= getNeed(node.getR()) ) {       node.getL().apply(this);       node.getR().apply(this);   }   else {       node.getR().apply(this);       node.getL().apply(this);       emit("swap");               // swap top two stack operands   }   emit("isub"); }

2. (5) Analyze the scale of savings on stack space realized by rearranging the order of subtree code generation. Note that this is not practical in general due to the possible re-ordering of side-effects, for example:

1. class A {
2.     static int a=10;
3.     static int m1() { a = a - 1; return a; }
4.     static int m2() { a = a * 2; return a;}
5.     public static void main(String arg[]) {
6.         a = m1() + m2();
7.         System.out.println( a );
8.     }
9. }

           m1() + m2() ® 27

           m2() + m1() ® 39

 

Consider generating subtree code in the least need first versus the greatest need first order. For needs of subtrees need(a)<need(b), stack requirements for allocation in order of:

need(parent(a,b)) = b+1

need(parent(b,a))= b

The savings for a binary operation is at most 1 stack location. While it may appear that the savings is cumulative, that 1 stack location is be saved for every binary operation properly ordered, in fact the savings is 1, period.

Consider a method's need, which is the maximum of any subtree in the statement or return expression. For a method with subtrees:

                              method
                             /           \
                  statement      expression
                  |     |     |           /      \
                  a     b    c          d        e
                 /  \        
                f    g

the bottom-up needs for method results in:

need(method) = max(1, need(statement), need(expression))

need(statement) = max(1, need(a), need(b), need(c))

need(expression) = max(1, need(d),need(e))

need(a) = max(1, need(f),need(g))

or

need(method) = max(1, max(need(f),need(g)), need(b), need(c), max(need(d),need(e)))