Instruction selection and register allocation must satisfy the target machine, not just preserve an abstract expression tree.
By the end: Read live ranges, explain spills, and separate an allocation model from a complete machine-code generator.
Target instructions impose constraints
A backend chooses machine instructions that implement IR operations. One target may have a useful memory operand or fused operation that another lacks. Instructions can restrict register classes, operand placement, immediate sizes, and which inputs are overwritten. An abstract multiplication does not specify all these details.
The application binary interface, or ABI, defines conventions such as argument placement, return values, stack alignment, and which registers a callee must preserve. Locally correct arithmetic can still fail if generated code violates the ABI when it calls another function.
Translate an operation under an explicit target contract
An intermediate operation specifies a required computation, but a target instruction specifies how a particular machine can perform it. Consider a hypothetical integer addition whose destination must be the same register as its first input. To implement a new result while keeping that input available, the backend may first copy the input to another register and then add into the copy. If the original input has no later use, the result can overwrite its register. The same abstract addition can therefore require different instruction sequences depending on later uses.
Use a concrete example with a equal to four and b equal to seven. Suppose registers R1 and R2 initially contain those values, and the target permits R1 = R1 + R2. If a is dead afterward, the instruction leaves eleven in R1 and no required value is lost. If a must be returned separately later, overwriting R1 destroys four. With a free R3, first copy R1 into R3, then perform R3 = R3 + R2. The arithmetic agrees in both cases, but the preservation obligation differs.
An overwritten input may need a copy
Hypothetical target sequence
a has no later use
a is needed later
Initial values
R1 = 4; R2 = 7
R1 = 4; R2 = 7; R3 free
Preserve input if necessary
No copy required.
Copy R1 into R3: R3 = 4.
Addition overwrites its first input
R1 = R1 + R2: R1 = 11.
R3 = R3 + R2: R3 = 11.
Required values afterward
Result 11 is available in R1.
Original a = 4 in R1; result 11 in R3.
This is an exact value trace for a hypothetical destructive two-address addition. It is not SmallExpr bytecode or an encoding for a named CPU.
An immediate operand is a constant encoded within an instruction rather than fetched from a register. Encoding space can limit which constants fit. Suppose a hypothetical target has an unsigned eight-bit immediate field. Five fits directly, while three hundred does not because the greatest encodable value is 255. The backend needs another permitted sequence, perhaps materializing three hundred in a register before addition. This is a target constraint, not a claim that the source language forbids three hundred or that SmallExpr's bytecode PUSH uses such a field.
A memory operand introduces another target choice. A machine might allow addition to read one input directly from an addressed location, while another requires both inputs in registers. That difference can change the reload instructions needed for a spilled value. The abstract IR can hide these details while they are irrelevant, but the backend eventually must account for address formation and legal operand combinations. A register count that omits addressing is a storage illustration, not sufficient evidence that an instruction sequence can execute on a real processor.
Calls add obligations defined by the ABI. Suppose a hypothetical convention allows a callee to overwrite R1 and R2 but requires it to preserve R3. A caller whose value must survive the call cannot assume R1 remains unchanged. It might save that value to a stack slot or arrange to keep it in R3 while respecting the convention. Using R3 can create saving work in the function that promises to preserve it for its own caller. Register choice therefore depends on boundaries between compiled functions as well as local arithmetic.
Different constraints require different evidence
Hypothetical rule
Fits or preserves
Does not follow
Unsigned eight-bit immediate
5 fits because 0 ≤ 5 ≤ 255.
300 does not fit that field; the source value is still valid.
One memory input permitted
An instruction may read a spilled operand directly.
Every instruction or target accepts memory inputs.
Callee may overwrite R1 and R2
Caller protects values needed after a call.
R1 retains its old value merely because it held it before the call.
Callee must preserve R3
The callee restores the caller-visible R3 value.
Using R3 in the callee is always free of save/restore cost.
These are stated teaching assumptions, not universal register names, ABI rules, or immediate-field widths. The target contract determines legal native sequences.
When reading generated instructions, annotate both the value computation and the constraint each extra operation satisfies. A copy may preserve a still-needed input. A load may recover a spilled value. A save may satisfy a calling convention. These operations can be necessary despite lacking matching source operators. Other backends need not emit them. Another target or a different live range can remove the need. Ask for the target's operand and calling rules before judging a translation by its instruction count.
Keep values while future uses need them
A value is live at a point if some relevant future path can use its current value before it is replaced. In the lab, t1 and t2 are both live before multiplication. After the multiplication consumes them, only t3 remains. Textual variable count is not the same as peak simultaneous live storage.
Values whose live ranges overlap can interfere with sharing a register. Register allocation chooses storage while respecting interference and target constraints. If available registers cannot hold all required values, a compiler can spill some to memory, recompute values, or change the code. Each choice has costs.
Derive live values backward from their uses
A value needs storage because an upcoming operation may read it, not because its name still appears somewhere in the file. In the separate straight-line fragment, t1 is a plus b, t2 is c plus d, t3 is t1 times t2, and the fragment returns t3. Restrict attention to the computed temporaries t1, t2, and t3. The incoming operands have storage requirements too, but this model omits them. At a boundary, count only temporary values that have been defined and still have a future use.
Start immediately after the return. No temporary in this fragment has a remaining use, so the live set is empty. Immediately before the return, t3 is needed. Moving backward across t3 = t1 * t2 removes t3 because its definition supplies the new value, and adds t1 and t2 because the multiplication reads them. Thus both inputs must be available immediately before multiplication. The instruction reads its inputs before their old storage can be reused. Counting only the output would miss this necessary coexistence.
Continue backward across t2 = c + d. Remove t2 from the temporary live set because this instruction defines it. Its inputs c and d are outside the chosen temporary set, so only t1 remains in the restricted set before that instruction. Moving backward across the definition of t1 removes t1 as well. Reversing the resulting boundaries gives the displayed forward sequence: t1, then t1 and t2, then t3, then none. These are sets of retained values after instructions, not cumulative counts of definitions.
Where temporary values must remain available
The horizontal axis is instruction-boundary order, not elapsed time. Filled dots mark live values after an instruction. Bars connect those boundaries; an arrow into the multiplication marks its final reads. Input operands and target constraints are omitted.
For a conventional assignment, the backward rule keeps values needed later except the value newly defined here, then adds the instruction's uses. This explains why a definition can end one requirement while introducing others. A live value is a particular computed result, not necessarily a source variable or a fixed register. Reassigning a source variable creates a new value that can have a different live range. An optimizer may also eliminate that source variable's independent representation while retaining an equivalent result somewhere else.
The straight-line calculation generalizes to branches by considering successor paths. Suppose one successor reads t1 and another reads t2. Before choosing the branch, either value may be needed, so a conservative live set contains both. Taking one observed path does not justify discarding the other value in code that must handle both. Loops require propagating requirements around the back edge until the sets stop changing. This is a static analysis over the graph, unlike the SmallExpr VM trace that records actual operand-stack contents during one execution.
Derive the restricted temporary sets backward
Cross instruction backward
Temporary live set after
Temporary live set before
return t3
Empty
{t3}
t3 = t1 * t2
{t3}
{t1, t2}
t2 = c + d
{t1, t2}
{t1}
t1 = a + b
{t1}
Empty
Rows follow backward analysis order. Only t1, t2, and t3 are tracked; omitting a, b, c, and d does not mean their values need no storage in a real implementation.
Check the derivation by proposing an early overwrite. After defining t2 but before multiplication, overwrite t1's storage with an unrelated value. The multiplication can no longer obtain its required input unless another location or a valid recomputation supplies it. After multiplication, overwriting t1's former storage is harmless for this fragment because it has no remaining use. This contrast explains interference: t1 and t2 cannot share the only copy of one location while both are needed, but a later value may reuse storage once the earlier requirement ends.
Work through the mechanism
Which temporary values must coexist?
t1 = a + b
t2 = c + d
t3 = t1 * t2
return t3
Only t1, t2, and t3 are counted. Incoming operands and machine constraints are omitted.
Peak live temporaries: 2. Budget: 2. Both values fit at the peak in this abstract model.
Each box is one live temporary, not a time-scaled interval. Solid-outline blue boxes fit in the selected budget. A dashed gold box exceeds it. The particular excess value is illustrative, not an allocator’s chosen spill. Changing the budget leaves the live sets unchanged.
Boundary
Live temporary values
After t1 definition
t1
After t2 definition
t1, t2
After multiplication
t3
After return
None for this fragment
The incoming values a, b, c, d and target instruction constraints are outside this small storage diagram.
Change the budget without changing the live sets
Begin with the two-register preset and inspect the boundary after the second definition. Two temporary values coexist there, so two unconstrained temporary locations can retain them. A possible assignment places t1 in R1 and t2 in R2. When multiplication has read both, t3 can occupy R1 and R2 becomes free. This assignment assumes the result may reuse a consumed input's storage. It is a witness for the abstract storage problem, not a complete target program with loads, instruction encodings, and calling conventions.
Select the one-register preset without changing the fragment. The diagram's live sets remain the same because future uses have not changed. What changes is whether the selected budget can retain every live temporary in a register at the peak. One of the two values must exist elsewhere, be recomputed later, or be handled by a different legal instruction sequence. The dashed excess value does not identify an allocator's chosen victim. It marks a shortfall between the model's demand and its chosen resident-register budget.
Two locations fit the peak; one leaves a shortfall
Each cell is one hypothetical temporary register, not bytes or a scaled live interval. Both columns describe the same fragment and live sets. The right-hand question marks are deliberately not an executable allocation.
Work a spill example on paper rather than expecting generated native code from the control. Suppose R1 initially retains t1 and a memory slot S is available. Store t1 into S before using R1 to compute t2. With t2 in R1 and t1 in S, both required values still exist. A hypothetical multiplication that accepts one memory input can read S and R1 and leave t3 in R1. This sequence satisfies a one-register temporary budget only under that target assumption, and it introduces a store plus a memory read.
Change the assumed target so multiplication requires two register inputs. The previous one-register sequence is no longer an executable solution. Reloading t1 into R1 would overwrite t2, while retaining t2 in R1 leaves no second register for the reload. A second usable register, a suitable alternative instruction sequence, or another representation is necessary. A spill does not repeal operand constraints. This is why the widget reports that a value cannot remain resident rather than claiming to have built a working one-register backend for arbitrary targets.
A spill plan still has to satisfy the multiplication rule
Paper sequence
Memory-input multiplication allowed
Two register inputs required
Save t1 from R1 into slot S.
t1 remains available in memory.
t1 remains available in memory.
Compute t2 into R1.
R1 holds t2; S holds t1.
R1 holds t2; S holds t1.
Multiply S by R1 into R1.
Legal under the stated memory-input rule.
Not legal under this target rule.
Try reloading S into R1 first.
Not needed for this sequence.
Overwrites t2; a second register or another legal sequence is needed.
A storage witness becomes an executable plan only after target rules are supplied. The widget does not choose spills or emit either sequence.
Compare spilling with recomputation under explicit conditions. If t1 came from a cheap, pure operation whose inputs remain available, recalculating it later might avoid retaining it for a long interval. If those inputs require reloads too, recomputation may offer no saving. If t1 came from a call with output or a load whose memory can change, repeating it can change behavior. The abstract fragment does not provide enough facts to choose among these strategies. It only identifies the boundary where a register-only retention plan fails.
Finish by predicting the effect of a third register before looking for a control that is not present. In this restricted storage problem, the peak remains two, so an extra register does not change the live sets or establish a further reduction in work. Likewise, changing animation speed elsewhere cannot alter liveness. Explain both preset states using the same future-use argument, then state the extra target assumption needed by your paper spill sequence. This tests whether you can separate demand, resource budget, and the legality of a proposed implementation.
State what the liveness diagram leaves out
The diagram tracks three already computed temporaries at instruction boundaries in straight-line pseudocode. It assumes a value can reuse storage after its final read. Two registers suffice to retain these temporaries in this abstract storage model; one cannot keep both t1 and t2 resident at the highlighted boundary.
This is not an executable one-register or two-register backend. Loading inputs, addressing memory, constrained instructions, calls, and flags may require more resources or a different allocation. A full allocator also handles branches and loops, where liveness is a data-flow property over possible paths.
Connect storage choices to scheduling and evidence
Instruction order can change live overlap without changing a pure expression's value. In separate straight-line pseudocode, compute u from a plus b and later multiply u by two to produce r. Independently compute v from c plus d and multiply v by three to produce s. Finally add r and s. Computing u and v first retains both intermediate sums together. Completing the u calculation before starting v can release u earlier. Such scheduling needs dependency and effect checks; the liveness widget does not reorder the fixed fragment.
Count the temporaries for two proposed schedules. In the order u, v, r, s, result, the boundary after r retains v and r, and the boundary after v retains u and v. The peak is two. In the order u, r, v, s, result, the boundary after v retains r and v, so the peak is also two. Shortening u's lifetime did not lower this example's peak. This attempt shows why a scheduling claim needs a boundary calculation, not an impression that related operations are closer together.
A different rearrangement can lower a peak. Compute three independent sums u, v, and w, then form r = u * v and finally result = r + w. The original order u, v, w, r, result retains three values after w. If effects and dependencies permit the order u, v, r, w, result, the largest retained set has two values. The multiplication no longer waits while w is already retained. This is a separate example with a different dependency graph, not a newly discovered third temporary in the original four-instruction fragment.
Move the independent sum after the multiplication
Separate pure pseudocode: u = a + b; v = c + d; w = e + f; r = u * v; result = r + w. Each dot is one live computed value after the named definition. Horizontal position is schedule order, not duration. The final result remains available for return; incoming operands are omitted.
A reduced peak can make allocation easier, but it does not alone predict speed. A processor may execute independent work concurrently, and postponing it might reduce that overlap. Spills can hit a nearby cache or require more expensive access; register classes may prevent using an otherwise free register. An allocator can also split a live range, keeping a value in different locations at different points. Peak temporary count describes storage demand, but these target and workload considerations also affect runtime cost.
Debug information has to describe changing locations rather than promise one permanent slot per source variable. A value may begin in a register, move to a spill slot, and later return to a register. Another source variable may share its location after its final use. A folded constant may have no stored copy at all. These outcomes can make optimized debugging less direct without implying that lexical bindings changed. Binding determines which declaration a use means; allocation determines how the required value is represented at a particular program point.
When evaluating a backend claim, request a concrete allocation or instruction sequence as well as a live-set summary. Check each use against the location holding its value, then check operand constraints and call preservation. Only after that should you count added stores, reloads, or copies and consider measurement. For the lesson's model, the defensible conclusion is that two temporary values must coexist before multiplication, and their storage can be reused afterward. Native correctness, total register demand including inputs, and elapsed performance each require evidence beyond that bounded conclusion.
Check a value at every required use
Program point in a hypothetical spill plan
Location holding the required value
Audit question
After computing t1
R1 holds t1.
Will later operations overwrite R1?
After saving t1
R1 and slot S both hold t1.
Does the store preserve the full required value?
After computing t2
R1 holds t2; S holds t1.
Does the target permit multiplication from these locations?
After a permitted multiplication
R1 holds t3; old t1 and t2 are dead.
Can their former locations be reused now? Yes, in this fragment.
At a call in some larger program
Location depends on the convention and allocation.
Will a clobber destroy a still-live value?
Locations are program-point facts, not permanent identities for source variables. This audit needs operand and ABI information beyond the bounded live-temporary diagram.
Exercises
Count simultaneous storage
The fragment defines t1, t2, and t3. Must all three occupy separate registers throughout?
Hint
Inspect the final uses before considering reuse.
Worked answer
Phase
Needed temporary storage
Before multiply
t1 and t2
After multiply
t3 only
Possible reuse
A former t1 or t2 location
Definitions in the source are not permanent reservations of physical registers.
No. Before multiplication, t1 and t2 coexist. After it reads them, their storage can be reused for t3 under this abstract model. Peak live temporary count is two, not three. Actual target operand rules can add constraints, so this is not a complete machine-code proof.
Explain a spill
A compiler stores a temporary to a stack slot and reloads it later. Does this prove the source program explicitly used a stack variable there?
Hint
The storage may have been introduced by allocation.
Worked answer
Observation
Possible cause
Store and later reload
Register spill
Changing variable location
Allocation and scheduling
No persistent source slot
Value held in a register or eliminated
Machine storage reflects implementation choices as well as source semantics.
No. The compiler may have spilled a live value because registers were constrained. Source variables and generated storage locations do not map one-to-one. Debug information can describe the mapping at particular program points, but optimized values may move, merge, or disappear.
Sources and further reading
The explanations, examples, and worked answers are complete without these optional links. The sources describe specific implementations and language contracts, not one universal compiler pipeline. SmallExpr and the later pseudocode models are constructed teaching examples. Source notes identify the selected material reviewed; this is not an exhaustive compiler survey, production conformance test, or independent specialist review.
Selected overview and register-allocation material describing instruction selection, target constraints, liveness, and native-code generation. The storage lab is not an implementation of LLVM’s allocator. The reviewed register-allocation example has inconsistent def/use prose; the lesson follows explicit assignment direction instead.
Selected material on IR structure, SSA, phi semantics, integer operations, and semantic constraints. A production IR reference, not a specification of SmallExpr or a claim that every compiler uses LLVM.