Question

Common Data for this and the next 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;
}

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?

Accepted Answer

The correct answer is (B) 1. With code motion, move the computations of d=c*a and e=c+a into the else branch (right where they're used), so c only needs to stay live through the branch test, not through two separate eager computations beforehand. At the branch test itself we still need a (for the comparison and the if-branch), c (needed later inside the else branch), and x (freshly computed for the comparison) simultaneously live — an unavoidable peak of 3 live values, since x is derived from c and both a and c are still needed afterward. With only 2 registers available, handling this 3-way peak requires spilling exactly 1 of these 3 values to memory temporarily.

Explanation