The following code segment is executed on a processor which allows only…

20252013

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?

  1. A.

    0

  2. B.

    1

  3. C.

    2

  4. D.

    3

Attempted by 23 students.

Show answer & explanation

Correct answer: B

Concept

Register allocation maps program variables to a limited set of CPU registers. A spill is forced at a program point whenever the number of values that are simultaneously live there (already computed and still needed later) exceeds the number of available registers: one live value is written out to memory to free a register, then reloaded when needed. The maximum of this simultaneous-live count over all program points is the register pressure. When the pressure peaks at a single point, that point forces (pressure - number of registers) writes; code motion reduces pressure by delaying a computation until just before its use, so a value is not born until it is actually needed.

Applying it to this code

There are 2 registers. First drop dead computations and apply code motion. The statements d = c * a and e = c + a feed only the else branch (which squares them), so code motion pushes them down into the else block; they no longer occupy registers during the condition test. Walking the resulting straight-line core step by step:

  1. c = a + b: load a and b into the two registers and compute c. b is dead afterward, so the live set is {a, c} - two values, which fit in two registers.

  2. x = c * c: this uses only c, and its result x is needed for the test x > a. At this point the live set is {a, c, x}: a is still needed for the comparison and c is still needed to recompute d and e in the else block. That is three live values with only two registers.

  3. The shortfall: one of the three live values must be written to memory to free a register for the multiply and the comparison; it is reloaded later in whichever branch consumes it. This is the single forced write.

  4. Branches: the if branch runs only y = a * a (needs a alone); the else branch runs d = d * d and e = e * e, each recomputed fresh from c and a via the moved statements. Taken on its own, neither branch ever holds three live values, so neither forces an additional write.

Cross-check

Scan the simultaneous-live count at every point after code motion: the only point that exceeds two is the c = a + b ... x = c * c / comparison region, where it reaches three. A single peak of three against two registers forces 3 - 2 = 1 write, and code motion has already flattened every other potential peak, so the minimum is exactly one.

Explore the full course: Niacl Ao It Specialist