23,112 views

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

What is spilling?
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 .

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.

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

by

@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

“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.
thanks sir
                r1=a   r2=b
c = a + b;      r1=a   r2=c
x = c * c;         a      x     c spilled memory
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

why you moved two statements inside both if and else ? How its optimising ?
well we could think of it as the compiler worked on the code and optimized the code using code motion

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

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?