in Compiler Design edited by
14,744 views
49 votes
49 votes

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?

  1. $2$
  2. $9$
  3. $5$
  4. $3$
in Compiler Design edited by
14.7k views

4 Comments

Expression tree is evaluated in any order not necessary left to right.
2
2
edited by

here we can see that max require 3 register.

follow bottom-up manner.

9
9

7 Answers

84 votes
84 votes
Best answer

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

edited by

12 Comments

edited by
sachin sir, why you started with c+d, if the expression is (a-b)*(e-(c+d))

can we do it any way to get the minimal number?
0
0

just adding for explanation purpose

    Register 1 Register 2 Register 3
c    
c d  
c+d d  
c+d e  
c+d e-(c+d)  
a e-(c+d) b (here we need new register to load b)
a-b e-(c+d) b
(a-b)+(e-(c+d)) e-(c+d) b

 

2
2
sethi-ullman algorithm can be used to get the answer fast and correctly.
1
1

@Ayush Upadhyaya sethi Ullman algo gives answer 2(not 3).

 

can you please explain when to use sethi Ullman algo?

0
0

@soumayan bandhu-No.Sethi Ullman Algorithm also gives the answer as 3.

If you have any doubt, then try writing code and check whether you missed any value or not.

 

0
0

Oh,yes.

 This algorithm gives answer 2.

@Ayush Upadhyaya but I found some other previous questions where this algorithm is not worked, actually gives less number of registers.

0
0
Okay, just paste the link of that question in which you are having problem and we shall discuss that algorithm on it.So, it should be clear. :)
1
1

It is the same labelling algorithm. (Sethi-Ullman algorithm)

But because of the below statement given in question, every variable will need one register. Hence we will need 3 registers and not just 2.

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

10
10
I think that statement is there only to convey RISC architecture.In my opinion, the reason for choosing 3 reg over 2 is to maintain the precedence relation since the expression is (a-b)+(e-(c+d)).
0
0
Why to start execution from left subtree? Or we can start from any side?
0
0

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

1
1

@VYAN_jy you cannot solve this question using two registers.

0
0
29 votes
29 votes
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

4 Comments

 sid1221 

yes correct.

1
1

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.

1
1

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
2
2
5 votes
5 votes

$(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$

3 votes
3 votes
answer - D

using dependency graph coloring algorithm

3 Comments

@ankltrokdeonsns

Can u Draw it.? If u can then plzz draw it..it will be helpful for us
1
1
can u explain this algorithm?
1
1
why graph coloring method is giving the wrong answer to this problem. where we can’t apply that method?
1
1
Answer:

Related questions