The Gateway to Computer Science Excellence
+39 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 by Veteran
edited by | 5.6k views
is it in syllabus??
no sushmita
Thanx sir.
yes , it is in syllabus
gate 2017 asked almost same question .
yeah i wish they had not officially removed it from syllabus and then ask question.
Expression tree is evaluated in any order not necessary left to right.

here we can see that max require 3 register.

follow bottom-up manner.

5 Answers

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

by Boss
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?

just adding for explanation purpose

    Register 1 Register 2 Register 3
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


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

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


can you please explain when to use sethi Ullman algo?


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




 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.

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

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.

+28 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
by Active
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?
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.
@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.

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




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

slide number 19



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.


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


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


yes correct.


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

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
by Loyal

Can u Draw it.? If u can then plzz draw will be helpful for us
can u explain this algorithm?
+1 vote


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

by Loyal
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.

Related questions

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
52,215 questions
60,009 answers
94,696 users