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

Consider the expression $(a-1) * (((b+c)/3)+d)$. Let $X$ be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture, in which 

  1.  only load and store instructions can have memory operands and 
  2.  arithmetic instructions can have only register or immediate operands. The value of $X$ is _____________ .
in Compiler Design by Veteran (420k points)
edited by | 7.6k views
+9
+2
here i think the order of evaluation of the expression is done in such a way that the code generated is small and the number of registers is less hence evaluating (a-1) first will give the answer 3 and evaluating last gives the answer 2 but the answer is 2 as it is least with minimum number of registers
+2
0

https://gateoverflow.in/2138/gate2011-36

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

 (without any register spill) 

Does this statements means the same ??

 

0
What does mean without any register spill?
0
Bracket mismatch here.

2 Answers

+56 votes
Best answer
Load $R1,b$

Load $R2,c$

ADD $R1,R2$

Div $R1,3$

Load $R2,d$

Add $R1,R2$

Load $R2,a$

Sub $R2,1$

Mul $R2,R1$

hence minimum $2$ registers required
by Active (3.4k points)
edited by
+4

The correct answer would be 3. Because you have to calculate (a-1) first, which you have to keep upto the last. Hence 3 Register.

+7
but why...the question asks to do it efficiently in minimum number of possible register without spilling...
+1
What will be the correct answer for this?
+5
Correct answer would be 2
+14

by labelling algorithm we can get minimum 2 registers for the above question.

https://gateoverflow.in/2138/gate2011_36

my doubt is why we have not applied labelling algo in the gate 2011 question..please help

@Bikram Ballav Sir

@Arjun Sir

+9

@amit

Yes, The Labelling algorithm we can directly apply here .

It is actually Known as Sethi-Ullman Algorithm

https://en.wikipedia.org/wiki/Sethi–Ullman_algorithm

+10
and @amit

" If no intermediate results can be stored in memory, " this line is not given in this question , like it was given in 2011 question.

Hence here, in this question , we can store intermediate results into memory, no extra register require for that.

That's the only reason we can get minimum number of registers are 2 in this question but  minimum number of registers are  3 in 2011 question. Just because of this line .

Hope things get clear now.
+2

@Bikram  Sir 

How to solve this question using register interference graph(RIG) approach? 

My approach:- 

Three address code:-

----------------Live{a,b,c,d}

t1=a-1  

  -----------------Live{b,c,t1,d}

t2=b+c

------------------Live{t1,t2,d}

t3=t2+3

------------------Live{t3,t1,d} 

t4=t3+d

------------------Live{t1,t4}

t5=t1*t4

When I try to color the RIG for this I need more than 2 colors

What is the problem with this approach???

+7
but even without storing any result in memory, here only 2 registers are sufficient.
+17

@Bikram Sir,

"" If no intermediate results can be stored in memory, " this line is not given in this question , like it was given in 2011 question."

I think the above line in this question also is implied by the words "no spilling" ??

Here also in this question we cannot store intermediate results into memory.

The difference in answer of values as here(2) and that compared to 2011 question is because here we have some constant values in the expression of this question and the question clearly mentions that 

"arithmetic instructions can have only register or immediate operands"

That means we can save on one register while performing ALU computations with constants.

+1
the associativity of the multiplication operatoris Left to Right.Why are we not taking that here ? There must be a fixed associativyty followed right ?
0
i too have same doubt
0

@suchismith roy

Associativity of multiplication operator?

There is only one * operator so no point of associativity.

0

@Ayush+Upadhyaya

I agree with your statement 

0
This topic is related CAO...not code optimization
0

@Amit puri could you please explain the algorithm.

0
+18 votes

solution..

by Boss (41.6k points)
+1
correct answer will be 2
Answer:

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
50,309 questions
55,742 answers
192,220 comments
90,455 users