GATE CSE 2004 | Question: 10

Question

Consider the grammar rule $E \rightarrow E1 – E2$ for arith­metic expressions. The code generated is targeted to a CPU having a single user register. The sub­traction operation requires the first operand to be in the register. If $E1$ and $E2$ do not have any com­mon sub expression, in order to get the shortest possible code

• A. $E1$ should be evaluated first
• B. $E2$ should be evaluated first
• C. Evaluation of $E1$ and $E2$ should necessarily be interleaved
• D. Order of evaluation of $E1$ and $E2$ is of no consequence

Comments

https://youtu.be/o2CLMvdC4Lo?si=7PZ1_aIZZIoDzWvk.  Best answer I found...

---

If E1 and E2 do not have any com­mon sub expression

What is the significance of this statement? If E1 and E2 have a common sub expression, what would be the answer in that case? 

---

For single register,

Addition, Multiplication → Either first

Subtraction, Division → Second operand first

Answer 1

$E2$ should be evaluated first

After evaluating $E2$ first and then $E1$, we will have $E1$ in the register and thus we can simply do SUB operation with $E2$ which will be in memory (as we have only a single register). If we do $E1$ first and then $E2$, we must move $E2$ to memory and $E1$ back to register before doing SUB, which will increase the code size.

for more expalianation see this discussion https://gateoverflow.in/4069/gate-cse-2004-question-10?show=100621#c100621

Comments

Thanks Arjun.

---

sir how evaluation took place with the help of register and memory? plz elaborate

---

single user register; provided is used by the user to store evaluated E2, the other register is with the CPU now containing E1,

so that now E1 - E2 can be done easily now without doing any swaps, and thus with the shortest code possible,

 

thus we did E2 evaluation first

---

@Nitin there is only one register..but u considered 2 one is user register and another is cpu register..

The correct thing should ...the evaluated E2 is stored inside Memory not in any User Register.

---

thanks noted.

---

@arjun sir

sir,what is meant by not having any common subexpression???

---

@ shefali1  not having any common sub expression means it does not contain any expression which is common between both or they dont share code.

@Arjun sir correct me if i am wrong.

Answer 2

Suppose that E1 is stored at memory location 1005 and E2 is stored at memory location 1010.

We want to perform E1 – E2.. and we have 1 Register named R1.

So for Substraction we first move E1 into ALU followed by E2.

Suppose we first evaluate E1.

1. Move E1 to R1
2. Assign value 5 to E1 =>> E1 = 5
3. Move E1 back at Memory location 1005.
4. Move E2 to R1.
5. Assign value 10 to E2 =>> E2=10
6. Move E2 back at memory location 1010.
7. Move E1=5 at R1 again.
8. Move R1 in to accumulator.(or in ALU)
9. Move E2=10 at R1 again.
10. Move R2 in to accumulator.(or in ALU)

Now we first evaluate E2.

1. Move E2 to R1.
2. Assign value 10 to E2 =>> E2=10
3. Move E2 back to Memory location 1010.
4. Move E1 to R1.
5. Assign value 5 to E1 =>> E1=5
6. Now move or load R1 in accumulator.(or in ALU)
7. Move E2=10 at R1 again.
8. Move R2 in to accumulator(or in ALU)

So evaluating E2 first takes less steps.

Comments

Good Answer

Answer 3

 E -> E1 - E2

Given that E1 and E2 don't share any sub expression, most optimized usage of single user register for evaluation of this production rule would come only when E2 is evaluated before E1.

This is because when we will have E1  evaluated in the register, E2 would have been already computed and stored at some memory location. Hence we could just use subtraction operation to take the user register as first operand, i.e. E1 and E2 value from its   memory location referenced using some index register or some other form according to the instruction. Hence correct answer should be (B) E2 should be evaluated first. 

Comments

Loved your answer

Answer 4

@arjun sir

If they said that spilling is not allowed and we have only one register then is this operation possible with any way of code

Is it necessary to move the E1 without moving to register

Answer 5

We need to do E1-E2, but E1,E2 are arithmetic expressions themselves, so we need to evaluate them before we do the subtraction. 
( ignoring load operation of the frst expressions)

What if we evaluate E1 first?
1. Evaluate E1 --> result ends up in register
2. Store E1 (since we also need to evaluate E2 using same reg.)
3. Load E2
4. Evaluate E2 ----> result in register
5. Store E2 ( since the operation requires the first operand to be in the register, we need to put E1 in register)
6. Load E1
7. SuB

now if we evaluate E2 first
1. Evaluate E2
2. Store E2
3. Load E1
4. Evaluate E1 ( First operand in register as intended)
5  Sub

               When we evaluate E1 first, we need extra operation for storing E1, one extra load operation after the E2 is evaluated and stored. 
So E2 evaluation should be done first. 

" E1 and E2 do not have any com­mon sub expression" - if they had common subexpressions, interleaved evaluation might have been an optimal choice(not necessarily by length of code), but we don't necessarily know the pattern of the common subexpression - so we can't really say anything about the length of code. Some codes might be smaller for interleaved evaluation, while others might be bigger.