GATE CSE 2011 | Question: 36

Question

Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables $a, b, c, d,$ and $e$ are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?

• A. $2$
• B. $9$
• C. $5$
• D. $3$

Comments

PLEASE TELL ME THE ALGORITHM TO DO THSI

---

@Sherlock_Holmes There is no particular algorithm to do this. We just have to take minimum number of registers first, then if not sufficient add another register and see whether we can get our desired result or not . 

                       OR

We can use Live Variable Analysis in case of  blocks

---

@Sherlock_Holmes

• put leaf nodes = 1
• do recursively till you reach root of the tree
• if $m==n$:
      then $root$ = ($m+1) or (n+1)$
• if $m \ne n$:
      then $root$ = $max(m,n$
• value of root of the tree is the min no. of registers required w/o spilling

Answer 1

Given is Load Store Architecture, that means we can access memory using Load and Store Instructions.

Key Idea:- Pick new register only when it is required.

We want to add c and d, and initially both are in memory, therefore copy these into registers.

• load $R1, c$    $(R1 \leftarrow c)$
• load $R2, d$   $(R2 \leftarrow d)$

(here no compensation can be done, we need two registers)

• add $R1, R1, R2 \ (  R1 \leftarrow R1 + R2)$

(at this point $R1$ is holding $\mathbf{c+d}$ and $R2$ is holding $\mathbf{d}$, i.e. $R1 \leftarrow \mathbf{c+d}$  and $R2 \leftarrow \mathbf{d})$
Now, $\mathbf{e}$ comes into picture and my question is, Can i make use of $R1$ or $R2$ to store $\mathbf{e}$?
I can not use R1 to store e as its value will be needed later but I can use R2.

• load $R2, e$

(currently $R1 \leftarrow  \mathbf{c+d}$  and $R2 \leftarrow \mathbf{e})$

• Sub $R1, R2, R1$  $(R1 \leftarrow R2 - R1)$

Doing this all gives, final value of right sub-tree is stored in $R1$, and $R2$ stores $\mathbf{e}$.
Now, coming to left subtree, to perform "$a-b$" we need to copy both variables in registers.
We can copy one of the variable in $R2$, but we can not obviously copy in $R1$ as value of $R1$ will be required later.

• Load $R2, a$
• Load $R3, b$ (here comes extra register, and we can not avoid using it.)

Current mapping is $R2 \leftarrow a$, $R3 \leftarrow b$ and $R1$ contains final value of Right subtree.

• SUB $R2, R2, R3 (R2 \leftarrow R2 - R3)$
• ADD $R1, R1 , R2$

Hence answer is $3$  i.e. D

Comments

@gleise_21

See Pg 15 of this  pdf
Link: https://www.cse.iitb.ac.in/~uday/courses/cs324-08/code-generation.pdf
It has been done to minimize the number of registers.

---

@VYAN_jy you cannot solve this question using two registers.

---

from either side you start you will get 3 registers..

Answer 2

R1<- -c,  R2<- -d,  R2<- -R1+R2,  R1<- -e,  R2<- -R1-R2

To calculate the rest of the expression we must load a and b into the registers but we need the content of R2 later.  So we must use another register. R1<- -a,  R3<- -b,  R1<- -R1-R3,  R1<- -R1+R2

Ans D

Comments

So, we can use Labelling Algorithm with some modification. Instead of labeling right leaf node=0, need to label it with 1. After applying the algorithm, we get 3 register.

Please comment if my understanding is correct.

---

Why you assigned 0 to b and d.

In Sethi ullman algo,we have to assign 1 to every variable.

see below

https://en.wikipedia.org/wiki/Sethi%E2%80%93Ullman_algorithm

Traverse the abstract syntax tree in pre- or postorder

1. For every non-constant leaf node, assign a 1 (i.e. 1 register is needed to hold the variable/field/etc.). For every constant leaf node (RHS of an operation – literals, values), assign a 0.
2. For every non-leaf node n, assign the number of registers needed to evaluate the respective subtrees of n. If the number of registers needed in the left subtree (l) are not equal to the number of registers needed in the right subtree (r), the number of registers needed for the current node n is max(l, r). If l == r, then the number of registers needed for the current node is r + 1

---

@jatin saini your statement 

In Sethi ullman algo,we have to assign 1 to every variable.

Is wrong , as 0 will be assigned to b and d its correct please read the algo that you have mentioned !. ie point 1 .

 By going through algo we will get the answer as 2 . But here its given in the question that 

The binary operators used in this expression tree can be evaluated by the machine only when operands are in registers

we have to do some slight modification as we cannot  assign 0 to b and d  as they required to be in register before calculation so we give 1 register to both b and d. And now we apply the algo as it is . and we will get answer as 3

Answer 3

$(a-b)+(e-(c+d))$

$Load\ R0\leftarrow a$

$Load\ R1\leftarrow b$

$Sub\ R0\leftarrow R0-R1$

$Load\ R1\leftarrow c$

$Load\ R2\leftarrow d$

$add\ R1\leftarrow R1+R2$

$Load\ R2\leftarrow e$

$Sub\ R2\leftarrow R2-R1$

$add\ R0\leftarrow R0+R2$

---

$Ans: 3$

Answer 4

answer - D

using dependency graph coloring algorithm

Comments

@ankltrokdeonsns

Can u Draw it.? If u can then plzz draw it..it will be helpful for us

---

can u explain this algorithm?

---

why graph coloring method is giving the wrong answer to this problem. where we can’t apply that method?

---

@Mohib we can not apply graph coloring or Live Variable Analysis here as it is used for register allocation only. Either use Ulman-Sethi algorithm or do it by taking two registers first and then expanding if required. We can use the concept of a Live Variable to make things simple here.

Answer 5

The answer should be 2.
r1 = c
r2 = d
r1 = r1 + r2 (r1 = c + d)
r2 = e
r1 = r2 - r1 (r1 = e - (c + d))
r2 = a
r1 = r1 + r2 (r1 = a + (e - (c + d)))
r2 = b
r1 = r1 - r2 (r1 = (a + (e - (c + d))) - b)

Now, the above expression is equivalent to (a-b) + (e - (c+d)) as "addition" and "subtraction" are both commutative and associative.

Please correct me if I'm wrong.

Answer 6

For more information you can refer this, https://www.cse.iitb.ac.in/~uday/courses/cs324-08/code-generation.pdf