The following code segment is executed on a processor which allows only…
20132013
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?
- A.
0
- B.
1
- C.
2
- D.
3
Attempted by 35 students.
Show answer & explanation
Correct answer: B
Concept
Register allocation maps simultaneously-live values onto a fixed set of registers. A spill is a store of a live value to memory because no register is free to hold it (a later reload is a load, not counted as a spill). The registers needed at any program point equal the number of values live there at once — the register pressure. The minimum spill count is squeezed between a lower bound from the peak register pressure (whenever live values outnumber registers, one of them must be stored) and an upper bound from the best legal schedule. Code motion only reorders statements while preserving correctness, so it can lower peak pressure but never manufactures an extra register.
Application
Two registers are available. Note first that d = c * a and e = c + a are used only inside the else-branch (d = d * d, e = e * e), and neither a nor c is modified before the branch, so code motion may legally relocate both statements into the else-branch. The straight-line prefix then reduces to: compute c, compute x = c * c, and test x > a — while c must survive into the else-branch (for the relocated d = c * a) and a must survive for the test. A concrete two-register schedule:
Compute c = a + b. b is now dead, so the two registers hold exactly a and c, with no free register left.
x = c * c still has to be computed and it needs a destination register, but both registers are occupied by the still-live a and c, and c is also needed later in the else-branch. Store c to memory here — this is the single spill — which frees one register.
Compute x = c * c into the freed register (c is read just before it is overwritten / from the value still in hand). The registers now hold a and x — exactly the two values the comparison needs.
Test x > a. In the then-branch compute y = a * a (a is already in a register; no further store). In the else-branch reload c from memory (a load, not a spill) and run d = c * a, e = c + a, then d = d * d, e = e * e; at every step there only two values are live, so they fit in the two registers.
Lower bound: at step 2 three values (a, c, and the soon-needed x) must all be accounted for with only two registers, so at least one store is unavoidable. Upper bound: the schedule performs exactly one store, of c. The bounds coincide.
Cross-check
Independent count of peak simultaneous live values: across computing and testing x we need a (for x > a), c (for the relocated else-branch work), and x (the comparison value) — three values against two registers — which forces exactly one store; no other point ever has more than two values live, because code motion confines d and e to the branch that consumes them. So one store-to-memory is both necessary and sufficient, giving a minimum of 1.