edited by
21,514 views
64 votes
64 votes

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?

  1. $2$
  2. $3$
  3. $4$
  4. $6$
edited by

7 Answers

5 votes
5 votes

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};
4 votes
4 votes

Following registers are live from top statement to bottom statement: 

  1. $\{a\}$
  2. $\{a,b\}$
  3. $\{a,b,c\}$
  4. $\{c,d\}$
  5. $\{c,e\}$
  6. $\{c,e,f\}$
  7. $\{b,f\}$
  8. $\{e\}$
  9. $\{d,e\}$

After making a graph with variables as vertices & edges between two nodes iff they lie in same block (within braces), the graph happened to be $3$ colorable hence 3 registers are required.

edited by
3 votes
3 votes

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.

Answer:

Related questions

40 votes
40 votes
2 answers
2
go_editor asked Sep 30, 2014
12,726 views
The grammar $ S \to aSa \mid bS \mid c$ is LL(1) but not LR(1)LR(1) but not LL(1)Both LL(1) and LR(1)Neither LL(1) nor LR(1)