0

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

enter image description here

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.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Juliana Hill
  • 400
  • 2
  • 15
  • 1
    What code-gen technique in what video lectures? No registers should be needed if the expressions were all integer *literals*, so they 0 = 0 for that case. A compiler can and should evaluate constant expressions at compile time. Also, both ways are a single chain of additions, so unless you evaluate earlier sub-expressions in a different order (because of some specific simplistic evaluation rule(?)), you need one temporary for the running total. And on a non-CISC, I guess another register for the actual integer value before adding it. – Peter Cordes Nov 20 '22 at 15:25
  • Perhaps your eval method is similar to the extremely naive one that we see an example of in [Why does the expression \`10 + 32\` not use the stack while \`10 + -32\` does?](https://stackoverflow.com/a/74410403)? – Peter Cordes Nov 20 '22 at 15:25
  • That was my initial thought, but I'm confused on the wording of the first 4 options. My previous attempt was just the 5th option, but that was not correct either. So, I selected those 2, and it's still wrong. – Juliana Hill Nov 20 '22 at 15:58
  • 1
    Okay, I re-submitted that, and it worked. Maybe it was just an error on the platform, and not my actual misunderstanding? – Juliana Hill Nov 20 '22 at 16:00

1 Answers1

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.

Erik Eidt
  • 23,049
  • 2
  • 29
  • 53