How do I calculate the number of temporaries for a given expression(s)?

Question

I'm struggling to understand what I am doing wrong on an online compilers course, and there aren't many resources online to help me figure out my error.

Here is the question:

The following two expressions are evaluated using the simple code generation technique described in the video lectures: E1=e1+e2+e3+e4+e5 E2=e1+(e2+(e3+(e4+e5))) Identify the correct conclusions about the number of temporaries(NT) needed in the evaluation of E1 and E2.

Select all that apply:

• [ ] For any choice of e1, e2, e3, e4, and e5, NT(E1) NT(E2).

• [ ] For any choice of e1, e2, e3, e4, and e5, NT(E1) NT(E2).

• [ ] For any choice of e1, e2, e3, e4, and e5, NT(E1) = NT(E2).

• [ ] For different choices of e1, e2, e3, e4, and e5, the predicates NT(E1) NT(E2), NT(E1) = NT(E2), and NT(E1) NT(E2) can all be true.

• [ ] If all of e1, e2, e3, e4, and e5 are integer literals, NT(E1) NT(E2).

• [ ] If all of e1, e2, e3, e4, and e5 are integer literals, NT(E1) = NT(E2).

• [ ] If all of e1, e2, e3, e4, and e5 are integer literals, NT(E1) NT(E2).

It seems that E1 and E2 require the same number of temporaries. I've gotten all of the other questions right regarding this topic, so I'm genuinely at a loss.

Answer 1

If the naïve code generation choice is to materialize left operand into a register during the initial walk of the tree, then the right operand, and then perform arithmetic, like addition, the first expression will require 2 temporaries, so for E1=e1+e2+e3+e4+e5:

load t1, e1
load t2, e2
add t1,t1,t2 
load t2, e3
add t1, t1, t2
load t2, e4 
add t1, t1, t2
load t2, e5
add t1, t1, t2
store t1, E1

The point here being that the registers for the operands are released immediately after doing the addition, so t1 & t2 are both released.  So, though t1 is reclaimed for the result, t2 available for the next materialization.

While for E2=e1+(e2+(e3+(e4+e5))) we will have:

load t1, e1
load t2, e2
load t3, e3
load t4, e4
load t5, e5
add t4, t4, t5
add t3, t3, t4
add t2, t2, t3
add t1, t1, t2
store t1, E2

If the code generation is this naïve as described above.  Because the registers cannot be released until the addition is performed, yet the tree is traversed once with all actions necessary taken directly.

Code generation for a stack machine would be similar, replacing loads with push, while add will have no operands, so for the first expression, push, push, add, push, add, push add, while for the second, push, push, push, push, add, add.

Obviously, improvements in the code generation can be made so as to delay materializing the expressions into registers as follows: evaluate the left operand but leave it in memory if it is simple (e.g. variable or immediate), evaluate the right operand similarly, then revisit the left operand and load it into a register if it isn't already, then revisit the right operand similarly, and finally perform the addition, releasing both registers for left & right operand, while also claiming a register for the result.