retagged by
28,280 views
36 votes
36 votes

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?

  1. 0
  2. 1
  3. 2
  4. 3
retagged by

5 Answers

Best answer
36 votes
36 votes
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; 
} 

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

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

selected by
42 votes
42 votes
                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

3 votes
3 votes

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 

0 votes
0 votes

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:

Related questions

0 votes
0 votes
1 answer
3
1 votes
1 votes
1 answer
4