Translate a basic block with register state visible
This simple code generator translates a straight-line scalar TAC block into an abstract integer register machine. It shows the generated instructions, their addressing costs, each register-selection decision, register and address descriptors, and the next uses after each TAC instruction. The loaded example produces code immediately. Editing the block, register budget or live-out contract regenerates the complete walkthrough.
The method follows the local register-and-address-descriptor approach used in introductory compiler design. It is a teaching generator, not a backend for a real processor or an assembler. Its allocator uses a local heuristic and does not claim globally optimal code. The visible state is useful for explaining why a load can be avoided, why a current value must be spilled, or why a final store is required even after the arithmetic is complete.
Supply one scalar block and an observable-output contract
Input uses the site's scalar TAC assignments: copies, unary minus and supported binary integer arithmetic. Arrays, branches and complete control-flow programs are rejected on this page. Floating-point literals and exponentiation are outside this target model. The basic-block tool can help identify a suitable region, and the TAC generator explains how source expressions become intermediate operations.
The model assumes initialized integer inputs and ordinary nonvolatile scalar memory. The live-out field identifies final values that need to be available after the block. Leaving it blank conservatively preserves every assigned scalar. A smaller explicit list permits unneeded values to lose their current locations without a store. It does not permit omitting an arithmetic instruction that might matter through an error: this generator translates the supplied instructions rather than running a dead-code elimination pass.
Inspect the worked register-allocation example
The loaded block is:
t = a - b
u = a - c
v = t + u
d = v + u
With the default budget of 2 registers and every assigned scalar live on exit, the generator emits:
LD R0, a
LD R1, b
SUB R0, R0, R1
LD R1, a
ST t, R0
LD R0, c
SUB R0, R1, R0
LD R1, t
ADD R1, R1, R0
ST u, R0
ADD R0, R1, R0
ST v, R1
ST d, R0
For initialized inputs a = 12, b = 3 and c = 5, execution of that generated code gives:
| Live-out name | Value |
|---|---|
| t | 9 |
| u | 7 |
| v | 16 |
| d | 23 |
The reference TAC interpreter and target-machine interpreter agree on these results. The emitted sequence has 13 instructions and an abstract cost of 22 under the page's stated charging rule. Those figures come from the generator, not an assumed fixed textbook listing. Different register budgets or live-out choices can legitimately produce different code.
Read next-use information before choosing registers
A backward pass records whether each current value is needed later in the block and, if so, the next instruction that uses it. A value needed only at the boundary is marked live on exit instead of being assigned a fictitious next TAC instruction. A later definition ends the lifetime of the previous value under the same name.
The next-use table in a selected generation step describes the state after that instruction. It therefore refers to the new result value and the surviving operand values, not simply to every future appearance of the variable's spelling. Reassigning a name before its next read means the old value is not needed for that read. This distinction is central to safely reusing a register.
Follow getReg, loads and spills
Operand locations are consulted before emitting arithmetic. A name already resident in a register can be used without loading it again. Otherwise the generator selects an available register and loads the current memory value. Registers holding an operand needed by the current instruction are protected while the other operand is being brought in.
The selection heuristic prefers an empty register, then a register with no live value available only there. If spilling is necessary, it chooses using the farthest next need among the candidate register-only values. Current values that must survive are stored before their register is overwritten. Once all operands are available, the result can reuse an operand register because the abstract instruction reads its sources before writing its destination.
The decision list records getReg's chosen register and reason, followed by any spill stores. The current step's emitted code makes those effects inspectable. A later step may reload a spilled value when it is needed again. More registers can reduce some spills, but this local heuristic is not a guarantee that each budget produces a globally minimal sequence.
Distinguish register and address descriptors
A register descriptor lists names whose current values are equal and resident in that register. A copy can give another name to the same value without emitting a register move. Reassigning one alias removes that name from its old descriptor without destroying the other names' values.
An address descriptor lists current locations of one name: memory, registers, or both. A stale memory copy is not listed as current merely because the variable has a memory address. Names not needed yet or values discarded after their final use may have no current location. Incoming values needed at entry begin in memory; future local definitions do not receive fabricated initialized storage values.
Select a step to compare the emitted instruction with both descriptor tables. The regression tests also inspect these snapshots against interpreted TAC and target values. At block exit, every declared live-out whose current value exists only in a register is stored to memory. The final step shows that flushing process separately from the last arithmetic operation.
Interpret the abstract instruction cost
The cost is one unit per instruction plus one for each memory or immediate operand. A register-only arithmetic operation has only the base charge. A named memory operand is charged as memory even if its spelling resembles a register name, and an immediate operand has its own charge. The per-instruction table sums to the displayed total.
This is a model of addressing cost. It is not CPU cycles, elapsed time, bytes, energy or an architecture-specific performance estimate. The target has ordinary memory, integer arithmetic and the stated instruction forms; it does not model status flags, aliasing device registers, cache effects or instruction scheduling.
Verify the result within its stated model
Tests execute original TAC and generated target code on randomized initialized inputs under constrained register budgets. They compare the declared observable outputs and arithmetic errors. Targeted cases cover copy aliases, self-updates, signed arithmetic, spills, final stores, descriptor consistency and memory names that resemble registers.
Use the data-flow analyzer to study where live-out facts can come from across a graph, and the compiler lab for related exercises. Copy target code saves the current generated block. Keep its register budget, live-out assumptions and abstract cost rule with the listing when presenting a coursework answer.