How register allocation preserves live values with spills and target constraints

A computation can create hundreds of intermediate values even when the machine offers only a small usable register set. Most of those values are needed at different times. register allocation follows those requirements so that a register can hold a new value after its previous occupant's last required use. When too many required values overlap, the compiler preserves some in memory and inserts the transfers that bring them back for later instructions.

At each instruction, the allocator must determine which value may be overwritten. Counting source variables gives little help: one variable can represent several successive values, and values from different paths can have different lifetimes. An allocation needs control-flow information, instruction constraints, and an account of every use. A storage assignment can preserve the program perfectly while making a frequently executed path expensive.

Follow definitions and uses across a bounded branch

Consider a stipulated machine with two general-purpose registers, R0 and R1. It can add two register operands and overwrite either input with the result. Loads and stores move values between a register and a private stack slot. The branch condition comes from a separate control input, so it consumes neither of these two registers in this example. These assumptions define the model; a real instruction set may impose additional constraints.

The entry block computes a = 10, b = 20, and c = a + b. It then branches. The left block computes dL = a + c, while the right block computes dR = b + c. Each branch transfers its result to a common return location. The required answers are 40 on the left and 50 on the right. Neither branch changes the inputs or has additional side effects.

A value is live at a point when an execution continuing from that point may use its current value before replacing it with another definition. Immediately before the left addition, a and c are live. Immediately before the right addition, b and c are live. Before the branch decision, the compiler must preserve a, b, and c because either successor can still be selected.

At block boundaries, a conventional backward analysis computes live-out as the union of successor live-in sets. Live-in is the block's used-before-defined values together with live-out values that the block does not define. These equations are applied until the sets stop changing. For this small acyclic graph, the left live-in set is {a, c}, the right set is {b, c}, and entry live-out is {a, b, c}. Neither constant input needs to be live before its entry definition.

The union is conservative about the branch's possible futures. Although a and b are never both operands of a branch-local addition, both must survive until the branch chooses which is needed. Reusing their storage before that decision would destroy one possible outcome. Once execution enters the left block, b can be discarded; on the right, a can be discarded. Those changes allow different reuse decisions within the successors.

Construct live-range interference from required storage

Walk backward through the entry instructions to expose live-range interference. After c is defined, a and b must remain available for the branch, so c conflicts with each. After b is defined, a is still needed to form c and may be used on the left, so b conflicts with a. The interference graph for these three values is a triangle: every pair needs distinct storage at a relevant point in this model.

A triangle cannot be assigned only two register colors if each whole live range must occupy one register. That establishes the failure of this restricted all-register assignment. It does not establish that the program cannot run. Splitting a range, placing part of it in memory, or changing legal code placement can create a feasible execution. The allocator must account for the transfers introduced by those choices.

A useful starting point for live-range interference is giving each computed definition its own identity. The linked SSA guide explains those identities and the lowering of path-dependent selections into transfers. Here, the analysis continues to finite storage assignment after the values and their branch uses are clear. Correct merge transfers still have to survive whatever physical registers are chosen.

Even a colorable graph is only part of a target-specific feasibility check. Some operations accept a subset of registers, some results must use a particular register, and register classes can differ by value type. Calls can clobber locations. A two-input instruction may require a destination to share an input location. These restrictions belong to the instruction contract; they cannot be inferred from pairwise liveness alone.

Trace register spilling without losing a future use

Choose b for memory storage at the crowded point. Put a in R0 and b in R1, then store R1 into stack slot S_b. The slot now contains 20. Compute c by adding R0 and R1 with the result in R1. R0 still contains a = 10; R1 now contains c = 30. Overwriting the register copy of b is safe because the required b value survives in S_b.

On the left, compute the result into R0 from R0 + R1. The inputs are 10 and 30, so R0 becomes 40. Both input values have reached their last use on that path. On the right, load S_b into R0. This overwrites a, which has no right-path use. R0 becomes 20 while R1 remains 30; their sum produces 50 in R0. Both branches therefore return through the same physical register.

The trace checks the value-preservation obligation of register spilling. Every operand read must find the intended definition, and every memory reload must refer to the slot holding that definition's preserved value. The store must occur before the register is reused. A compiler cannot repair an overwritten value by placing a store after the overwrite; the original bits would already be gone.

The stack slot also has a lifetime. Another spilled value can share it only when their required stored contents do not overlap. A reload on one path cannot rely on a store performed only on another path. Here the entry store dominates both successors, so every execution reaching the right-path reload has already initialized S_b. Private spill storage must also respect the target's alignment, size, and calling-convention requirements.

When checking code after register spilling, keep the checking model explicit. The linked bytecode-verification guide propagates conservative execution-state descriptions and explains what its admission checks leave unproven. Such a check is useful for the invariants it actually represents. Passing a bytecode verifier does not independently prove a later machine-code allocator placed every store and reload correctly.

Charge transfers where execution actually repeats

Suppose this entire branch computation runs 100 times, with 99 left outcomes and one right outcome. The chosen b allocation performs 100 stores and one reload. Spilling a instead, while retaining c and b in registers, would need 100 stores and 99 reloads if the same entry and branch placement were used. This stipulated frequency comparison favors preserving a in a register through the branch.

Those counts are not measured time. A reload's effect depends on instruction placement, memory behavior, available execution resources, and dependencies. The counts do identify where extra operations enter the model. A compiler may use profile information or estimated frequencies to avoid placing transfers on a common path, provided every possible path still receives the right value.

A loop gives a different placement problem. Stipulate an invariant value x that is computed before a loop and used only after it. Each loop body needs both registers for temporary arithmetic, and the body executes 100 times. An allocation that insists on keeping x in a register at every loop boundary could save x before each body and reload it afterward, producing 100 store/reload pairs.

Split x's range around the whole loop instead: store it once before entry, let its stack slot retain the value throughout the repetitions, and reload once after the exit. That produces one pair. The transformation requires x to stay unchanged, its spill slot to remain intact, and every relevant exit needing x to execute an appropriate reload. An inner use of x would require an additional transfer or a different split. Hoisting a store is justified by those facts, not simply by spotting a loop.

Revise the allocation for a fixed-register result

Now change one instruction contract in the original branch example: the addition producing c must write R0. Keep the initial assignment a in R0 and b in R1. The earlier plan stored b and wrote c into R1, so it violates this new contract. Writing c directly into R0 would destroy a, which the left successor still needs.

A feasible revision stores a from R0 into S_a before computing c. Then compute c into R0, leaving b = 20 in R1. On the left, reload S_a into R1; b is dead there, so the overwrite is allowed. Add c and a to obtain 40 in R0. On the right, add c and b directly to obtain 50 in R0. The fixed-register result and both branch results now satisfy the stipulated contracts.

The revision is correct but changes the transfer count under the earlier 99-to-one branch frequencies: it requires 100 stores and 99 reloads. Other legal assignments or additional moves may offer another cost. Finding one feasible plan does not certify it as optimal. register allocation must satisfy the concrete target first, then compare the cost of admissible alternatives without treating a graph coloring result as the whole machine model.

Use a concrete machine without inventing performance evidence

For a laptop on which to inspect generated assembly, the catalogue offers the Lenovo IdeaPad 15.6-inch FHD touch laptop with an i5-1334U, 16GB DDR4, and 512GB SSD. Those listing facts describe the purchasable system. They do not show which compiler, calling convention, optimization settings, or allocation decisions a particular program will use.

The ASUS Vivobook 14-inch FHD laptop is another listed machine, with a Core 5 120U and 16GB DDR4. Comparing compiler outputs on either machine requires preserving the source, target options, and generated instructions. A product specification cannot substantiate a claim that one spill placement runs faster.

A useful inspection records each value's required uses, the location containing it before every instruction, and the permitted operand/result locations. For the examples here, the expected checks are concrete: both branch answers remain 40 and 50, each reload has a preceding valid store, and the constrained c result appears in R0. Transfer counts belong beside those correctness checks, with their stipulated frequencies identified. Performance claims require additional evidence from the actual program and execution environment.