The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+30 votes
3.1k views

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$
asked in Compiler Design by Veteran (106k points)
edited by | 3.1k views
+1
is it in syllabus??
0
no sushmita
+1
Thanx sir.
+3
yes , it is in syllabus
gate 2017 asked almost same question .
+4
+2
yeah i wish they had not officially removed it from syllabus and then ask question.

4 Answers

+43 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

answered by Boss (16.6k points)
edited by
0
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

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

 

0
sethi-ullman algorithm can be used to get the answer fast and correctly.
+26 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
answered by Loyal (6.2k points)
0
cant it be evaluated like this? First, evaluate the right sub-tree of the root as stated. Then add 'a' to one of the registers and then load 'b' in other register. By this, we have already met the condition that both the operands must be in register.

So, ANS = 2 , right?
+2
In load-store architecture i.e. RISC architecture, you cannot directly add contents of a memory location i.e. a to contents of a register. You first have to bring the content into a processor register.
0
@bleed red.

As Keith has stated, evaluate the contents of right subtree in R2.

Now, R1 is free.

Now, expressions to be evaluated is a-b+R2.

So, load 'a' in R1, then add R2 to it and then subtract 'b'.

It seems logical but I dont know if its valid for the parser.
+2

I know that my answer is wrong according to official key.I have applied labelling algorithm for this problem by which i am getting 2 registers.why we cant apply labelling algorithm(Complier design).when to apply and when not to..please clear the idea

@Bikram Ballav

@Sushant Gokhale

@Keith 

0

@amit

almost same example is given, just differ in - and + symbol in the tree

slide number 19 

http://people.cs.vt.edu/ryder/415/lectures/codeGeneration.pdf

+2

@amit

This question , answer is 3 registers 

As in qstn say no intermediate result store in memory only register can be use

to add "b" and R1, we first have to copy "b" to some register R2

because "b" is in memory

and we can not access memory using "add", as it is Load-Store architecture, and memory can be accessed using load and store instructions only . I mean for Load and Store purpose only .

as we copy b to another extra register

that's why 3 register require [ after applying Sethi-Ullman algorithm] .

The instructions produce result only in a register. If no intermediate results can be stored in memory, 

Because of this line we need to use one extra Register.

+1

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

I think because of this line we are getting the result as 3 because in slide 19 of the above pdf they are direclty doing arthmetic operation without even coping both operands to register for e.g add b,R1(Line No 2)

+1
@akb1115

In load-store architecture we cannot directly add contents of a memory location  to contents of a register.  We  first have to bring the content into a processor register . That's why 1 extra register needed .
+1
one more thing , we can say or as given above pdf , we cant use same destination register as oprand ... in labelling algo , so we should consider this one also to solving this ... so here we need extra 1 register ..rt?
+1

 sid1221 

yes correct.

0

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.

0

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
+3 votes
answer - D

using dependency graph coloring algorithm
answered by Loyal (9.1k points)
+1
@ankltrokdeonsns

Can u Draw it.? If u can then plzz draw it..it will be helpful for us
+1
can u explain this algorithm?
0 votes
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.
answered by (133 points)
Answer:

Related questions

+7 votes
1 answer
4


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,599 questions
48,600 answers
155,672 comments
63,739 users