Register Allocation Interview Questions: Compute Liveness, Interference, and Spill Costs

Register allocation interview questions become easier when you keep three decisions separate: which values must survive, which values cannot share a register, and which value is cheapest to move through memory. Compute liveness first, build interference from that result, then justify a spill with execution frequency and a correct rewritten program. Graph coloring alone does not explain the spill cost.

This article uses primary compiler references and an original two-register exercise. The Python checker executed the finite dataflow calculation and compared rewritten results on 242 inputs; it did not run LLVM's allocator or benchmark generated machine code. Use the compiler pipeline question on PracHub to practice locating allocation within a backend before working through the trace.

Start by stating the machine contract

Official background: LLVM's code generator documentation distinguishes virtual registers from physical registers and describes allocation within a target-dependent backend. Real targets add register classes, calling conventions and instruction restrictions. The exercise below deliberately removes those details so you can check the central reasoning.

Assume two interchangeable integer registers, R0 and R1. Inputs can be loaded from their parameter locations. Arithmetic may overwrite a source register after its last required use. There are no calls, exceptions, aliases, fixed-register instructions or arithmetic overflow in this model. The branch condition is available separately and consumes neither register. State those assumptions before drawing a graph; otherwise the interviewer may be reasoning about a different machine.

The original program has four basic blocks:

B0:
    a = input_x
    b = input_y
    c = a + b
    if left: goto L
    else:    goto R
L:
    t = a + c
    goto J
R:
    t = b + c
    goto J
J:
    u = t + c
    return u

Both branches define t before the join. Treat this as ordinary three-address code with reaching definitions, rather than silently applying SSA phi rules. A use of t in J is satisfied by the definition on the taken path. If the interviewer changes the representation to SSA, rename those definitions and account for edge uses explicitly.

For x = 2 and y = 5, c is 7. The left path returns 16; the right path returns 19. Keep both expected returns beside the graph. They will expose a plausible but incorrect spill rewrite later.

Compute live sets backward across the branch

The CMU register allocation recitation gives the standard backward equations: live-out is the union of successors' live-in sets, and live-in is use union live-out minus definitions. “Use” at block level means a value read before being defined within that block.

OUT[B] = union(IN[S] for S in successors(B))
IN[B]  = USE[B] union (OUT[B] - DEF[B])

Initialize sets to empty and repeatedly apply the equations until nothing changes. This graph is acyclic, so a suitable reverse traversal propagates the information in one sweep; the saved implementation performs a second sweep to confirm stability. Do not interpret its two loop iterations as a property of every liveness analysis.

The union at B0 is the important step. Although L does not use b and R does not use a, either successor might execute. Before the condition resolves, the allocation must preserve all values needed by either path. Choosing the left successor's set because it is more common would change program semantics on the right path.

At J, u has no live-out requirement because the return consumes its value inside the block. That does not mean the return requires no storage; it means u need not survive beyond the block. A target return register would introduce another constraint absent from this model.

If you struggle with a block summary, expand the instructions. Immediately before c = a + b, a and b are inputs to the addition. Immediately afterward, a, b and c must all survive to the branch. The difference between these two program points is precisely where register pressure becomes unavoidable.

Draw interference from definitions and live-out values

Work backward through each block. At a definition of v, connect v to every different value live after that instruction. Then remove v from the live set and add the instruction's uses. The resulting undirected edges are a–b, a–c, b–c and c–t. There is no t–u edge in this exercise because t dies when u is computed and the arithmetic permits destination reuse.

The a, b, c triangle requires three colors. With only two available registers, no ordering trick can color this graph without changing the program. The local checker enumerated all eight two-color assignments for that triangle and found a conflict in every assignment. This is a finite impossibility check for this graph, not a claim that general graph coloring is cheap.

Explain why interference is stronger than “these names appear in the same expression.” Values can interfere even if they never appear together in one instruction, because both must remain available across other operations. Conversely, a source and destination may share a register when the source dies and the instruction supports that overlap.

Moves deserve a separate discussion. A copy can create an opportunity to coalesce names, but merging their nodes may add constraints elsewhere. Fixed operands and overlapping physical register names can also invalidate an apparently legal color assignment. The Penn compiler lecture provides broader allocation and spilling context; the small graph here does not model those target restrictions.

Compare spill costs using the path frequencies

Suppose profiling for this fictional workload says the function runs 100 times: 99 left branches and one right branch. These are supplied exercise frequencies, not measured production data. Both a and b have interference degree two, so a degree-only rule cannot choose between them.

Under a simple rewrite that stores a spilled input once per invocation and reloads it before each use, the counts differ:

Spilling b saves 98 modeled memory accesses. The simple model explicitly reloads each spilled use; an optimizer could remove the initial redundant reload shown below, so these totals are not a claim of minimum traffic. The result follows from where the uses occur, rather than the variable's spelling or graph degree. A real cost model may weight loads and stores differently, incorporate loop depth, exploit rematerialization, or split live ranges. Therefore 201 is a teaching count under the stated rewrite, not a cycle estimate.

Ask what changes if the branch frequencies reverse. The preferred input spill reverses too. Ask what changes if x is a cheap constant. Recreating a may cost less than loading it, but only if recomputation preserves the original semantics and operands remain available. A heuristic is useful because it approximates such consequences; its formula is not a substitute for explaining them.

Rewrite b into a stack slot without losing a path

Here is one valid two-register rewrite. The slot holds b across the branch. On the left path, a remains in R0. On the right path, a is dead, so R0 can be reused for b's reload.

R0 = input_x                 # a
R1 = input_y                 # b
stack_b = R1
R1 = stack_b                  # explicit reload in the simple spill model
R1 = R0 + R1                 # c; b survives in stack_b
if left:
    R0 = R0 + R1             # t = a + c
else:
    R0 = stack_b             # a is dead on this edge
    R0 = R0 + R1             # t = b + c
R0 = R0 + R1                 # u = t + c
return R0

Track contents rather than variable names after every operation. R1 begins as b and later holds c. R0 begins as a, becomes t on either edge, then becomes u. Assigning one permanent register to each original name would obscure the point of the rewrite.

The tempting bug is omitting R0 = stack_b on R. With x = 2 and y = 5, the faulty right path computes a + 2c = 16 instead of b + 2c = 19. The left path still passes. A test suite that exercises only the common branch would give false confidence.

The executed checker compared the machine rewrite with the independent expression (x if left else y) + 2 * (x + y) for all x and y from −5 through 5 and both branch outcomes. All 242 cases matched. Removing the right-edge reload produced 110 failures. Equal x and y can hide that mutation, so choose unequal inputs when explaining a minimal counterexample.

Recompute after rewriting, then discuss what the model omits

Spilling changes the instruction stream and live ranges. Recompute or update liveness for the rewritten representation; do not assume that deleting one graph vertex is the complete allocator. Inserted loads have destinations, stores have uses, and additional temporaries can create new pressure. Our hand schedule shows that this particular program fits two registers after the rewrite.

If the interviewer adds a loop, make the back edge visible. A variable used on the next iteration can be live at the current iteration's end even when no later instruction in the printed block reads it. The fixed-point procedure handles this by circulating information until stable. One reverse textual pass does not establish that result.

If a call is inserted before J, ask which registers the calling convention preserves. If an instruction requires a specific register, represent that constraint explicitly. If integer overflow is observable, the independent oracle must use the same width and overflow behavior. These extensions change the correctness contract; they cannot be dismissed as implementation details.

Allocation also differs from CPU register renaming. The compiler chooses finite machine locations for program values before execution. A processor may later map architectural registers to physical registers dynamically to remove false dependencies. Both involve names and storage, but their lifetimes, recovery events and correctness checks differ.

Check a loop follow-up without recomputing from memory

If the interviewer adds a back edge from J to a block that uses b again, the right branch is no longer b's only later use. Mark the edge and rerun the equations before quoting the spill count. A value that looked dead at the return boundary may now be live around the loop. The old 201-access estimate belongs to the original terminating program, not this extension.

Also distinguish a value from a reused source-language name. If the loop redefines b before every use, the old b may be dead even though the same spelling appears in the next iteration. Trace reaching definitions or the actual IR representation instead of reasoning from names alone. This is especially important when moving between SSA and non-SSA examples.

During rehearsal, have a partner change just one successor edge or one use. Update the affected live sets, identify whether the triangle still exists, and say which reload schedule is no longer justified. This tests your dataflow understanding more directly than redrawing the original graph faster. Keep the original semantic oracle for the original program; create a new expected behavior before claiming the loop rewrite is correct.

Rehearse the explanation with five related questions

These verified PracHub records provide compiler context and follow-up practice. They are broader than this exact graph, and they are not a prediction of any company's question set. For each one, bring the liveness table or spill counterexample into the part of the answer it actually supports.

Before finishing, explain one complete chain aloud: the branch union makes a, b and c simultaneously live; the triangle prevents two-color allocation; path frequency favors spilling b; the right-edge reload preserves the uncommon outcome. Then change one assumption and say which calculation must be redone.

Practice the LLVM backend explanation with the two-register program beside it. Stop when you can defend the live sets, the chosen spill and the unequal-input failure without referring to a memorized allocator slogan.

Sources and Further Reading

• LLVM: The target-independent code generator
• CMU 15-411: Register allocation recitation, January 2024
• University of Pennsylvania: Register allocation lecture