GATE CSE 2010 | Question: 37

Question

The program below uses six temporary variables $a, b, c, d, e, f$.

a = 1 
b = 10
c = 20 
d = a + b
e = c + d 
f = c + e 
b = c + e 
e = b + f 
d = 5 + e
return d + f 

Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?

• A. $2$
• B. $3$
• C. $4$
• D. $6$

Comments

Not even in the real world applications.If gate asks minimum number of registers giving a control flow graph. Then it will be the only algorithm will give us minimum registers.

---

Bro their are 3 Numeric integer values 1, 10,20 so for these you need 3 Registers (atleast) first . So thats why your thought process is very good but first it will require 3 Registers first then later on it will be decided acc to other operations .

---

.

Answer 1

Here in these types of compiler questions, idea is "map/assign multiple temporaries to one registers."

here $a, b,$ and $c$ all are having $3$ different values so i need atleast $3$ registers $r1$, $r2$ and $r3$.
$a$ is mapped to $r1$, $b$ to $r2$ and $c$ to $r3$.

$d = a + b$, after this line if u notice '$a$' is never present on right hand side, so I can map (register of $a$ which is $r1$ ) $d$ to $r1$.
$e = c + d$, after this line '$d$' is never present on rhs, so I can map (register of $d$ which is $r1$ ) $e$ to $r1$.

at this time mapping is
$r1 --- e$
$r2 --- b$
$r3 --- c$

(at this moment I have registers for $e, b$ and $c$. if I introduce new variable then I may need different register)
now at this point if u see
$f = c + e$
$b = c + e$
these two are essentially doing same thing, after these two line '$b$' and '$f$' are same so I can skip computing '$f$'. and whereever $f$ is present I will replace it with '$b$'. (because neither of '$f$' and '$b$' are changing after these two lines, so value of these will be '$c+e$' forever)

(seems like I introduced one more variable $f$, and register is needed for that, but actually I did not really introduce '$f$'. I am skipping computation of '$f$')
now at second last line "$d = 5 + e$"
here I introduced '$d$', I can map it to any of the register $r1$ or $r3$, because after this line neither of '$e$' or '$c$' is required. (value of '$b$' is required because I need to return '$d+f$', and '$f$' is essentially equal to '$b$')

finally code becomes

$r1 = 1$
$r2 = 10$
$r3 = 20$
$r1 = r1 + r2$
$r1 = r3 + r1$

(skipping '$f$' computation)
$r2 = r3 + r1$
$r2 = r3 + r1$
$r1 = r2 + r2$
$r3 = 5 + r1$
return $r3 + r2$

Therefore minimum $3$ registers needed.

Correct Answer: $B$

Comments

IS IT POSSIBLE TO TAKE HIGHEST NO OF VARIABLE LIVE IN ANY PERTICULAR TIME BY ( JUST LIVE VARIABLE ANALYSIS)

---

@Vineeth_Babu

i don't think that's gonna work
consider a scenario :
1. a=5
2. b=6

3. c=7

4. d=8

5. e=a+b+c+d
6. return a;

in this scenario, only a is required and rest is garbage but max live count at any place in the sequence is 4 ( just before stmt 5)
live variable will give 4 as answer but 1 is the real answer

---

for Those who are asking can we use live variable analysis then answr is YES 
application of live variable analysis are 1. dead code elimination and register allocation . 

for Register Allocation 
1. Liveness --> 2. RIG --> 3.coloring ( and yes you are done ) 
after solving you will get you req 3 Regi. 
credit @GO Classes @Sachin Mittal 1 @Deepaksir 

Answer 2

All of the given expressions use at-most 3 variables, so we never nee more than 3 registers.

See  http://en.wikipedia.org/wiki/Register_allocation

It requires minimum 3 registers.

Principle of Register Allocation : If a variable needs to be allocated to a register, the system checks for any free register available, if it finds one, it allocates. If there is no free register, then it checks for a register that contains a dead variable ( a variable whose value is not going to be used in future ), and if it finds one then it allocates. Otherwise it goes for Spilling ( it checks for a register whose value is needed after the longest time, saves its value into the memory, and then use that register for current allocation, later when the old value of the register is needed, the system gets it from the memory where it was saved and allocate it in any register which is available ).

But here we should not apply spilling as directed in the question.

Let’s allocate the registers for the variables.

a = 1 ( let’s say register R1 is allocated for variable ‘a’ )

b = 10 ( R2 for ‘b’ , because value of ‘a’ is going to be used in the future, hence can not replace variable of ‘a’ by that of ‘b’ in R1)

c = 20 ( R3 for ‘c’, because values of ‘a’ and ‘b’ are going to be used in the future, hence can not replace variable ‘a’ or ‘b’ by ‘c’ in R1 or R2 respectively)

d = a+b ( now, ‘d’ can be assigned to R1 because R1 contains dead variable which is ‘a’ and it is so called because it is not going to be used in future, i.e. no subsequent expression uses the value of variable ‘a’)

e = c+d ( ‘e’ can be assigned to R1, because currently R1 contains value of varibale ‘d’ which is not going to be used in the subsequent expression.)

Note: an already calculated value of a variable is used only by READ operation ( not WRITE), hence we have to see only on the RHS side of the subsequent expressions that whether the variable is going to be used or not.

f = c+e ( ‘ f ‘ can be assigned to R2, because vaule of ‘b’ in register R2 is not going to be used in subsequent expressions, hence R2 can be used to allocate for ‘ f ‘ replacing ‘b’ )

b = c+e ( ‘ b ‘ can be assigned to R3, because value of ‘c’ in R3 is not being used later )

e = b+f ( here ‘e’ is already in R1, so no allocation here, direct assignment )

d = 5+e ( ‘d’ can be assigned to either R1 or R3, because values in both are not used further, let’s assign in R1 )

return d+f ( no allocation here, simply contents of registers R1 and R2 are added and returned)

hence we need only 3 registers, R1 R2 and R3.

ref-http://quiz.geeksforgeeks.org/gate-gate-cs-2010-question-37/

Comments

simple and clear,great job....

Answer 3

After making the interference graph it can be colored with 3 different colors. Therefore minimum number of color needed to execute the program without spilling would be 3 (B).

Comments

with interfacing(DAG) diagram also it will take only 2 registers

---

See this:  https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/17/Slides17.pdf

---

Thanks Nirmal that was helpful.

Answer 4

3 registers.

here,

d = a + b
e = c + (a+b) 
f = c + (c+ (a+b)) 
b = c + (c+ (a+b) = f 
e = b + (c+(c+(a+b))) 
d = 5 + (b+(c+(c+(a+b))))
return d + f 

first evaluate b using two registers and then store its value in f because f and b are equal.

now evaluate d with two registers. then return d+f

hence 3 registers.

Comments

thanx @ jayendra

---

In the step d=5+e 5 should be in a register as it is given in the question that all operations take their operands from registers

---

@ Aishwarya Gujrathi 1
Operands should be in Memory not constant values its like immediate adressing mode right?

Answer 5

2 Registers

a = 1        ===>>   R1=a;
b = 10       ===>>   R2=b;
c = 20       ===>>   
d = a + b    ===>>   R1{D}=R1{A}+R2{B};
e = c + d    ===>>   R2=c;   R1{E}=R1{D}+R2{C};
f = c + e    ===>>   R1{F}=R2{C}+R1{E};
b = c + e    ===>>   R2{B}=R1{F};
e = b + f    ===>>   R2{E}=R2{B}+R1{F};
d = 5 + e    ===>>   R2{D}=5{CONST}+R2{E};
return d + f ===>>   RETURN R2{D}+R1{F};

Answer 6

I will re-write code based on versions of variable. The initial version of a variable $v$ shall be $v_0$

$a_0=1\\ b_0=10\\ c_0=20\\ d_0=a_0+b_0\\ e_0=c_0+d_0=c_0+a_0+b_0\\ f_0=c_0+e_0=c_0+c_0+a_0+b_0\\ b_1=c_0+e_0=f_0\\ e_1=b_1+f_0=f_0+f_0=b_1+b_1\\ d_1=5+e_1=5+f_0+f_0\\$

$return\,\,d_1+f_0=5+f_0+f_0+f_0\\$

(1)$Load\,R_1,a_0$

(2)$Load\,R_2,b_0$

(3)$Add\,R_1,R_2$(R1 now contains $d_0=a_0+b_0$)

(4)$Load\,R_2,c_0$

(5)$Add\,R_1,R_2$(R1 contains $e_0=c_0+a_0+b_0$)

(6)$Add \,R_1,R_2$(R1 now contains $f_0=c_0+e_0=c_0+c_0+a_0+b_0$)

(7) Now I know that the return value is $5+e_1=5+f_0+f_0+f_0$ and R1 contains $f_0$, I need to add $f_0$ two times more to the register R1, Load Register R2 with 5, Add it to the the register R1 and return contents of the Register $R_1$. And since, variables a,b,c,d,e,f are temporaries, means after execution of the code the values of a,b,c,d,e,f won't be required further and hence I don't need to store them in memory.

So, minimum registers required should be 2.

Comments

@Ayush Upadhyaya

 

how you got 7th line

---

I just tried subsituting what values variables are getting and what is being returned.