in Compiler Design retagged by
23,112 views
35 votes
35 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
in Compiler Design retagged by
by
23.1k views

4 Comments

What is spilling?
0
0
In simple words spilling is that you have to store intermediate results also in registers , you can’t move intermediate results into memory to save some registers .
0
0

Mitali gupta

I think it is something different then what you said.

spilling means intermediate result stored into a temporary memory location. when no of registers are not  enough to keep intermediate operands.

1
1

3 Answers

34 votes
34 votes
Best answer
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
by

4 Comments

@Deepak Poonia sir the tag mentioned here says it’s out of syllabus so can i assume that spilling is not a part of gate syllabus now ? as i have seen questions regarding spilling in some test series that’s why i am asking

0
0
“Target code generation” is indeed removed from GATE CSE syllabus last time the syllabus was updated. But this is a topic which is still relevant and can be asked in GATE – like token ring, vector space etc which have been asked even when they were not in “official syllabus”. I would say the probability of this being asked is very less but not 0. I have removed the “out of syllabus” tag.
1
1
thanks sir
0
0
41 votes
41 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

4 Comments

why you moved two statements inside both if and else ? How its optimising ?
0
0
0
0
well we could think of it as the compiler worked on the code and optimized the code using code motion
0
0
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 

2 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
2
2

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

0
0
Answer:

Related questions