intermediateRegisters
What happens when there are more live values than registers?
Whether the candidate knows what a spill is and can reason about which value to spill. Anyone can say "it uses memory"; the discriminator is the choice function and the fact that spilling changes the problem it was solving.
What a strong answer covers
- Something spills. The allocator picks a value, stores it to a stack slot at its definition, and reloads it before each use — so an operation that was a register access becomes a store plus one or more loads, and the function grows a larger frame.
- Which value it picks is the interesting part. The usual heuristics are: prefer values with long live ranges and few uses, because they occupy a register for a long time and pay little for it; strongly prefer values that are not used inside a loop, because a reload in a loop body is paid every iteration; and prefer values that can be *rematerialized* — a constant, an address computation, a load from an unchanging location can simply be recomputed at the use, which costs one instruction and no stack slot at all.
- Spilling also changes the problem. The reload is itself a value that needs a register, so a spill can create new pressure at the reload point, and allocators either reserve registers for this or iterate: colour, spill, rebuild the interference graph, colour again.
- The framing depends on the allocator. Graph colouring builds an interference graph and spills when a node cannot be given a colour with fewer than K neighbours, iterating to a fixed point. Linear scan walks the intervals in order and evicts the one that ends last, which is worse code and far faster to compute, which is why JITs at low tiers use it.
✓ Green flags
- Uses the word spill and describes the store/reload pair concretely.
- Names a spill heuristic and justifies it — loop depth, use count, live-range length.
- Knows rematerialization exists and when it beats a stack slot.
- Notes that spilling can create new pressure and that the allocator iterates.
- Distinguishes graph colouring from linear scan by what each is optimizing for.
✗ Red flags
- "The compiler errors out — it cannot allocate." It never errors; a spill always exists as a fallback because the stack is unbounded.
- "It uses the stack, so it is about twice as slow." Spill slots are the hottest addresses in the frame and usually sit in L1; the cost is real but it is not a memory-latency cost.
- "You should rewrite the source to use fewer variables." Source variables and machine values are not in correspondence — SSA and copy propagation have long since rearranged them.
- "Just spill the value you needed least recently." That is a cache policy, not an allocation policy; the allocator knows the whole live range in advance and should use it.
Follow-up
You reduce the register budget from 8 to 3 and the code gets slower by 5x rather than a little. What is probably in the loop body?
Implementation challenge
What to ask them to write or trace on a whiteboard.
Given six values with stated live ranges and three registers, produce an assignment. Say which value you spilled, why that one, and whether you would rematerialize it instead.