GATE CS 2013 Q48 — Runtime Environments

Using the only allowed optimization, code motion, we can move the computations of d and e into the else block because they are only used there and their operands a and c are not modified before the branch. This minimizes their live ranges.

The optimized code becomes:

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

Let us allocate the two available registers, $R_1$ and $R_2$:

1. Load $a$ into $R_1$ and $b$ into $R_2$.
2. Compute $c = a + b$ and store it in $R_2$ (since $b$ is now dead). Currently: $R_1 = a$, $R_2 = c$.
3. To evaluate the condition x > a, both $x$ and $a$ must reside in registers. Thus, we must compute $x = c * c$ and store $x$ in $R_2$.
4. Since $c$ is still needed in the else block, we must spill $c$ to memory before overwriting $R_2$. This counts as 1 spill.
5. Now, $R_1 = a$ and $R_2 = x$. We perform the comparison x > a.
6. If the else branch is taken, we reload $c$ from memory into $R_2$ (as $x$ is now dead) and complete the remaining calculations without any further spills.

Thus, the minimum number of spills to memory is 1.