5.8k views

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 | 5.8k views
+2

This program can be executed with 2 registers. But b and both need c+e so  we need the value of c and e to be saved for

b= c+ e.

can we move the value of f to b directly as

r1=c ,r2=e,

so r1 <- r1+r2 (r1 as f r1->f )

Now for b= c+e =f

r2 <-r1 ( opr b <-f)

Next operations can be executed with 2 reg. Too

Is this correct approach??

If we can transfer the value of f'reg to b instead of adding c+e twice , this program need only 2 registers min.

0
is it in syllabus??
0
I don't think so. Anybody would confirm please?
0
DAG can also be used to solve this problem.
0
@chotu isn't the answer 2 here? Accepted answer says 3.Can't we use algabraic manipulation here?
0

@Chhotu Sir how to use DAG to solve this?

0
Simple and easy
0
What is DAG and how to apply it for this specific question?
0

great way......nice method pls provide more such solution.... It'll be helpful.

+1
r1 = 1
r2 = 10
r3 = 20
r1 = r1 + r2
r1 = r3 + r1
r2 = r3 + r1
r2 = r3 + r1
r1 = r2 + r2
r3 = 5 + r1
return r3 + r2
Therefore minimum 3 registers needed.

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$
by Boss (17.9k points)
edited
+1

@sachin

So, removing $f = c + e$ or  $b = c + e$ looks sensible here, as both are same.

So, if same lines come, we can safely remove in the exam and replacing that $f$ by $b$ or $b$ by $f$ in other lines also, right ?

+4

Depends.
Here value of b and f are not changing anywhere after that assignment and through out the program f and b are same. So i can supply value of b whenever some one requires value of f.
If these two values are changing later in the program, then u need to take extra precaution for that. U can use same register upto whereever these values are same, and u may need different register later.
I am not expert in this :D But this makes sense :)

+3
You are right and same precaution we take while drawing DAG. Anyway, this method suits here best :-)
+26
I just have a small doubt ::

Why are you assigning 3 different registers to a,b,and c initially.

In order to compute d=a+b we need only 'a' and 'b' and later in the program nowhere we are using the initial values of 'a' and 'b'.

My point is that , what we can do is assign 'a' and 'b' to 2 different registers initially.And instead of immediately assigning third register to 'c' . We can overwrite one of the registers used for 'a' or 'b'.

Later we may introduce a third register when it is absolutely needed.

Main idea is to avoid using new registers and reuse the old ones as long as possible.

Although even if we compute the way I am suggesting the ans would remain the same.But going the way i suggest will avoid us ending with more number of registers than absolutely necessary.
+1
Are the instructions required to be executed in sequential order? Doesn't the code Optimizer re-shuffle instructions in order to use less no of registers? Bcz if we do a bit re-shuffle it can be done using two registers.

Should we assume that in this type of questions code optimizer be there?

I did this assuming code being optimized:

a=1

b=10

b=a+b=11

a=20

b=a+b=31

a=a+b=51

b=a=51

b=a+b=102

b=5+b

return b+a

Where am i wrong?Is it the assumptions?
+1
here instead of using the same value of f for b we can temporarily use the register of b for f as the old value of b is not used again and then b value is over written by c+e and then we can put b in place of register c and then the live variables will be b,f,e and then onewards we can continue .. i dont think the compiler will think intelligently to reuse the same value of b instead of f so this should be right approach
+4

@VS please look into the below snippet:-

It says only we require 2 registers and it is quite logical. But my question is why we require 3 registers at all

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

Can you please look and elaborate it..

+1
someone please tell what is wrong in above approach by @vinil .Am getting same
+4
Yes. I think we only need 2 registers.
+3

@Vinil-

But you have changed order of instructions.

The instruction that loads c from memory is at step 3, but now you have moved to step 5.

The questions says we have to execute the given program, but here we are executing the "modified" version of program.

+2
But that really matter because  question is about minimum number of registers right ??
+8

Yes, Code motion is one of the compiler optimizations, we can use it !

Ref : https://gateoverflow.in/1556/gate2013-48

I think every body is doing the same mistake.

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

d = 5 + e    =>>   R2{D}=5{OPERAND}+R2{E}; We need Register R3 for Value 5 as it is an operand
return d + f ===>>   RETURN R2{D}+R1{F};
+1
Someone please show how to draw the  DAG for it
+1
So What is final answer 2 or 3?

Can someone please look at this
+1
how is it possible? when compiler will look  'c' and'e' for b=c+e ..then how we can tell to compiler to take b=f ?... instead allocating b's register to f and then same register to b may be an approach.  am i right?
0

what does "program without spilling" means?

+3
When a register content is saved to memory and then reloaded again it constitutes a spill. Basically reducing spills enhances the running speed of an application as register is faster than memory (including cache)
0

We need Register R3 for Value 5 as it is an operand

Isn't 5 an immediate value? How can we say it is an operand? I thought operand is anything which is a variable. @VS

0

When i traced back for "d+f," i got the return value as "6c+3a+3b+5"

can i use this expression to solve the problem..

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).
by Loyal (6.1k points)
+4
what will be the interference graph for it ?
+4
What will be the inference graph for this????
+1
with interfacing(DAG) diagram also it will take only 2 registers
0

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

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.

by Active (2.9k points)
0
simple and clear,great job....

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.

by Loyal (8.1k points)
+2
Could you please explain , what does spilling mean here ??
+14
spilling means storing content of register into memory location. if we have limited number of registers and we need more than available then at that time we can store the content of register into memory and again load it back whenever needed.
+2
thanx @ jayendra
+1
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
+1

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

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};
by (191 points)

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.

by Loyal (6.3k points)
edited by
0
Nice explaned

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.

by Boss (29k points)
0