GATE CSE 2013 | Question: 48

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

Q.48 Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code?

• A. 0
• B. 1
• C. 2
• D. 3

Comments

What an explaination @Kshitij Sharma, thank you!

---

Deepak Sir Explanation: Link

---

@Kshitij Sharma But bro tell me 
in else part where we have 
d=c+a
d=d*d
e=c+a 
e=e*e
before entering the else part we have a and x is reg R1 and R2 
now we bring c in r2 because we need to do c+a but now the result will be store in d and d we have to use in next line but we have a and c in reg and we cant overwrite c,a bcoz we have to use it in future i.e in e=c+a so we hae to store any one in memory and bring d in register cant it results in 1 more spilll
please correct me if i m wrong 

Answer 1

We can do code motion as follows:

c = a + b; //a and b in register and b replaced by the result c after the instruction
x = c * c; //x replaces c in register and c is spilled (moved to memory)
if (x > a) { //x and a in registers
 y = a * a; 
 d = c * a; //spilled c taken from memory and replaces x in register. 
 e = c + a; 
} 
else { 
 d = c * a; //spilled c taken from memory and replaces x in register. d replaces a in register
 d = d * d; //c and d in register
 e = c + a; //a  taken from memory and e replaces c in register (a taken from memory is not a spill, it is a fill. The reason is a is not modified till this point.)
 e = e * e; 
} 

So, we need minimum 1 spill in the compiled code.

https://en.wikipedia.org/wiki/Register_allocation 

Comments

But how to find what code should be moved....wasnt it very difficult to find out?

---

@Deepak Poonia sir how in the if(x>a) both x and a are in memory 

---

Arjun Sir is the legend !!. Short precise answers and the amount of clarity their answers are carrying, just a glance and you get where you were going wrong.

Answer 2

                r1=a   r2=b
c = a + b;      r1=a   r2=c
x = c * c;         a      x     c spilled memory 
if (x > a) {                                   //jump to either block 
 d = c * a;        a      d     c
 e = c + a;        a      e     c
 y = a * a;        y      e     c
}                                         
else { 
 d = c * a;        a      d     c        
 e = c + a;        e      d     c
 d = d * d;               d
 e = e * e;        e
} 

Only c needs to be in memory and spilling (register to memory) is done only once so answer would be 1

Comments

why you moved two statements inside both if and else ? How its optimising ?

---

example https://gateoverflow.in/275026/made-easy-test-series

---

well we could think of it as the compiler worked on the code and optimized the code using code motion

Answer 3

Only one memory spill is required to store x. because when else part to be executed we need to store c after replacing x in register R2 

Comments

See

What u all are doing, that d and e under if block and else block.

but how do u know that only d and e should come under if block and else block.

 

if block doesnot contain any d or e

---

@Abhrajyoti00   bhai is question ko samjha de kse hoga ye….spilling?

Answer 4

To minimize spills to memory in the compiled code, we need to consider the limited number of registers available in the instruction set architecture. In this case, the processor has only two registers.

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

The limited register constraint may lead to spills to memory when there are more than two live variables at the same time.

• Before c = a + b;, a and b are live.
• Before d = c * a;, a, b, and c are live.
• Before e = c + a;, a, b, and c are live.
• Before x = c * c;, a, b, and c are live.
• Before the if statement, a, b, and c are live.
• Inside the if branch, a and y are live.
• Inside the else branch, a, b, c, d, and e are live.

Now, let's consider the limited registers (R1 and R2). We can observe that at most three variables (a, b, and c) are live simultaneously before the if statement. Therefore, we may need to spill one variable to memory.

The minimum number of spills to memory is:

1

Answer 5

Spill: Move data from a Register to Memory.

Fill: Move data from Memory to a Register.
Although, I couldn't find actual definition of fill, taking it from Arjun sir's answer.

---

Since question mentions

Assume that all variables are dead after this code segment

d & e needs to be calculated only in the else block, so we move it there.
 

ignoring obvious loads

c = a + b; // R2{c} <- R1{a} + R2{b}
x = c * c; // Need 'a' next, so spill c in memory. And then R2{x} <- R2{c} * R2 {c}
// above if you spill 'a' to memory, you need to spill c to memory again later (to load x), so to minimize spill c into memory
// also, a is never modifed in the program, so we can 'fill' it anytime.
if (x > a) { // CMP R2{x}, R1{a}
  y = a * a;  // R2{} <- R1{a}*R1{a}
}
else {
//since question says minimum spill to memory, c can be read (or fill'ed) multiple times
  d = c * a; // load R2,c; R2{d} <- R2{c}*R1{a}
  d = d * d; // R2{d} <- R2{d} * R2{d}
  e = c + a; // load R2,c; R2{e} <- R2{c} + R1{a}
  e = e * e; // R2{e} <- R2{e} * R2 {e}
}

Answer 6

We can do code motion as follows:

c = a + b; //a and b in register and b replaced by the result c after the instruction
x = c * c; //x replaces c in register and c is spilled (moved to memory)
if (x > a) { //x and a in memory
y = a * a;
d = c * a; //spilled c taken from memory and replaces x in register.
e = c + a;
}
else {
d = c * a; //spilled c taken from memory and replaces x in register. d replaces a in register
d = d * d; //c and d in register
e = c + a; //a  taken from memory and e replaces c in register (a taken from memory is not a spill, it is a fill)
e = e * e;
} ..

Comments

@Ray Tomlinson, Can you explain the code motion process? Why did we move it inside the if block?

---

@cormen Refer this : https://gateoverflow.in/1556/gate-cse-2013-question-48?show=123445#c123445

Note: Code motion helps us move or rearrange instructions in such a way that we reduce the number of spills and optimize register usage.

---

Just a copy of the best answer by Arjun Sir! What's the point of copying and pasting if there isn't anything new!