Question 48

Consider the 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;
}

Notice that the variables d and e are only used inside the else branch. Since code motion is permitted, we can defer the computations of d and e until inside the else block:

c = a + b;
x = c * c;
if (x > a) {
    y = a * a;
}
else {
    d = c * a;
    d = d * d;
    e = c + a;
    e = e * e;
}

Let us evaluate register requirements with 2 registers $R_1, R_2$:

1. To compute c = a + b, registers hold $a$ and $b$, computing c.
2. To compute x = c * c, registers hold $c$, producing x.
3. In the condition if (x > a), we compare x and a. Both $x$ and $a$ must be in registers.
4. But notice: for the else branch, variable $c$ must be preserved across the comparison to compute d = c * a and e = c + a! At the point of x > a, the variables needed subsequently in the else branch are $a$ and $c$, plus $x$ is needed for the test. This requires 3 active values ($x, a, c$), while only 2 registers are available.
5. Therefore, at least one value (specifically $c$) must be spilled to memory before the branch and reloaded in the else branch.

Thus, the minimum number of spills to memory is 1, which corresponds to option (B).