20.
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have at most 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;
}
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 ?
Exam Year(s)
Tripura Public Service Commission - 2025,
Answer: B
The minimum number of spills is 1.
Two points settle it. First, a and b are never reassigned, so they can be reloaded from their memory locations whenever needed; only storing a value computed in the code counts as a spill. Second, code motion lets d = c * a and e = c + a move into the else branch, the only place their values are used.
At least one spill. At the test x > a, both x and a must be in the two registers, and c is still needed afterwards to compute d and e in the else branch. Three values need to survive with two registers, so c must be stored to memory once.
One is enough. R1 = a, R2 = b; R2 = a + b (c); store c (the spill); R2 = c * c (x); compare R2 with R1. In the if branch, y = a * a uses R1. In the else branch, reload c into R2, compute d = c * a into R1, then d = d * d; reload a into R1, compute e = c + a into R2, then e = e * e.
So 0 is impossible and 2 or 3 are more than needed.
