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

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