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

What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation.

  1. A.

    3

  2. B.

    4

  3. C.

    5

  4. D.

    6

Attempted by 53 students.

Show answer & explanation

Correct answer: B

Concept. The minimum number of registers a piece of straight-line/branching code needs (with no spilling) equals the register pressure: the maximum number of values that are simultaneously live at any single program point. A value is live from the instruction that defines it until its last use. That maximum live-count is a lower bound on the registers required; if a colouring of the interference graph using that many registers exists, it is also sufficient.

Application — liveness sweep (read the code backwards). Walk each statement and record the set of values that must be held simultaneously:

  1. c = a + b : needs a, b. After it, a is still used later, c is born. Live carries a, c.

  2. d = c * a : d is born and must survive to the else-branch. Live carries a, c, d.

  3. e = c + a : e is born and must also survive to the else-branch. Live carries a, c, d, e — four values at once.

  4. x = c * c : just before this, a, c, d, e are all live (size 4). x is born; c dies here. Live becomes a, x, d, e — still four.

  5. if (x > a) : the test reads x and a; d and e must still be preserved for the else path, so the live set entering the branch is a, x, d, e (size 4).

No program point ever holds more than four live values, so the register pressure is 4. Hence at least 4 registers are necessary.

Constructive allocation showing 4 is sufficient (registers R1–R4):

  1. R1 = a, R2 = b.

  2. c = a + b → R2 = R1 + R2 (R2 now holds c, R1 holds a; b is dead).

  3. d = c * a → R3 = R2 * R1 (R3 holds d).

  4. e = c + a → R4 = R2 + R1 (R4 holds e).

  5. x = c * c → R2 = R2 * R2 (c dies; R2 now holds x).

  6. Branch with R1 = a, R2 = x, R3 = d, R4 = e. If-path: y = a * a reuses any free register (d, e unused there). Else-path: d = d * d → R3 = R3 * R3, e = e * e → R4 = R4 * R4. No spill anywhere.

Cross-check. Lower bound (max live = 4) meets the achievable allocation (4 registers, no spill), so 4 is both necessary and sufficient. Three would fail precisely at the moment a, c, d, e are all live; anything above 4 leaves a register permanently idle.

Explore the full course: Gate Guidance By Sanchit Sir