in Compiler Design edited by
14,743 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

4 Comments

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

12 Comments

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?
0
0
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.
2
2
@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.
0
0

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 

3
3

@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

1
1

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

3
3

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

 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