GATE CSE 2013 | Question: 49

Question

The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have atmost two source operands and one destination operand. Assume that all variables are dead after this code segment.

c = a + b; 
d = c * a; 
e = c + a; 
x = c * c; 
if (x > a) { 
 y = a * a; 
} 
else { 
 d = d * d; 
 e = e * e; 
}

What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation.

• A. 3
• B. 4
• C. 5
• D. 6

Comments

this is still in syllabus asked in 2017

---

If there are not enough registers to hold all the variables, some variables may be moved to and from RAM. This process is called "spilling" the registers. Over the lifetime of a program, a variable can be both spilled and stored in registers: this variable is then considered as "split".

---

 

Answer 1

Here, we are told not to do code motion. So, we start with 3 registers

c = a + b; //a, c in register
d = c * a; //a, c, d in register
e = c + a; //a, c, e in register, d spilled. 

So, now we try with 4 registers

c = a + b; //a, c in register
d = c * a; //a, c, d in register
e = c + a; //a, c, d, e in register
x = c * c; //a, x, d, e in register
if (x > a) { 
 y = a * a; 
} 
else { 
 d = d * d; 
 e = e * e; 
} 

No spilling. So, 4 is the minimum number of registers needed for avoiding spilling. (If code motion was allowed, we need only 3 registers for avoiding spilling).

Comments

@Shaik Masthan sir please explain code motion?

Thanks

---

@halfcodeblood , the following wikipedia link might be of some help . 

codemotion 

---

@KartikGawande  Is it because :
 

if (x > a)    // x=x >a means a,x,d,e in registers

{

 y = a * a;   // y= a*a means y,x,d,e in registers 

} 

 else { 

 d = d * d;    // d=d*d means y,x,d,e in registers

 e = e * e;    // e=e*e means y,x,d,e in registers

 }

 So,in total 4 registers is enough.

Answer 2

Here 4 registers are needed

 

Answer 3

BOLD lines describe Live variable just before entering the next statement 

{ a,b }
c = a + b;

{ a,c }
d = c * a;

{ a,c,d }
e = c + a;

{ a,c,d,e }
x = c * c;

{ a,d,x,e }
if (x > a)

Either IF condition passes

{ a }
{ y = a * a; }

or when IF condition fails

{ d,e }
else 
{d = d * d;
e = e * e; }

So as we can see that at max only 4 variables are live, therefore we need 4 registers to avoid register spilling.

@Arjun sir, is this method correct?

Because everyone draws a graph and then finds its chromatic number, i don’t understand why do we need a graph?

For example, https://gateoverflow.in/78311/how-to-draw-register-allocation-interference-graph

Comments

Since it has not been used ahead, therefore dead.

---

most perfect answer after watching Deepak sir live ness analysis video.

---

x= c + constant; // constants like 1,2,3..

 

x= c + c ; 

 

does these statements need 2 registers or 1 register ?

 

 If we do liveliness analysis it was only 1 register. If we do it by hardware register it was 2. 

 

Some one please clarify @GO Classes @Shaik Masthan @Deepak Poonia @Arjun