ToolSphere

Simple Code Generator

Computer science

Generate register-machine code from scalar TAC, with getReg choices, next-use information, spills, register/address descriptors and instruction costs.

Type scalar assignments to see register code and allocation steps.

13 target instructions; abstract cost 22

Generated register-machine code

13 instructions · abstract cost 22

Copy target code
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
#InstructionCost
1LD R0, a2
2LD R1, b2
3SUB R0, R0, R11
4LD R1, a2
5ST t, R02
6LD R0, c2
7SUB R0, R1, R01
8LD R1, t2
9ADD R1, R1, R01
10ST u, R02
11ADD R0, R1, R01
12ST v, R12
13ST d, R02

Generation steps

t = a - b

  • getReg → R0: empty register
  • getReg → R1: empty register
  • getReg → R0: no live register-only value
LD R0, a
LD R1, b
SUB R0, R0, R1

Register descriptors after this step

A descriptor records which current values are in each register.

RegisterCurrent equal-value names
R0t
R1b

Address descriptors after this step

Each name lists the memory/register locations holding its current value.

NameCurrent locations
tR0
amemory:a
bmemory:b, R1
uno current location — not needed or not yet defined
cmemory:c
vno current location — not needed or not yet defined
dno current location — not needed or not yet defined

Next uses after this step

Next use is the next instruction that reads the current value. A spill saves a needed register value to memory.

NameLive?Next use
tyes3
ayes2
bnonone
unonone
cyes2
vnonone
dnonone

Target model and cost

  • Integer register-machine model with ordinary nonvolatile scalar memory and initialized inputs.
  • Empty live-out list preserves every assigned scalar; otherwise only the named live-out values require current memory on exit.
  • Cost is one per instruction plus one per memory or immediate operand. It is an abstract addressing cost, not CPU cycles.
  • The allocation heuristic is local and is not claimed globally optimal.

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Simple Code Generator

  1. 1Edit the loaded straight-line scalar TAC block, or keep the register-allocation example.
  2. 2Choose a register budget and state the values needed after the block; blank preserves every assigned scalar.
  3. 3Read the generated instructions and the explicitly defined abstract cost total.
  4. 4Move through generation steps to inspect getReg choices, emitted loads/stores and descriptor updates.
  5. 5Compare next-use information with register reuse and spills, then copy the target code.

About Simple Code Generator

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.

Frequently asked questions

What does this simple code generator accept?

One straight-line scalar block in the documented integer TAC syntax. Arrays, branches, floating-point operations and exponentiation are outside this target model.

What is getReg choosing?

It chooses a register based on current locations, protected operands and future needs. The step list shows whether an empty register, safely reusable register or spill candidate was selected.

What is a register descriptor?

It records names whose current equal values are resident in a register. Copies can share a register until a later definition separates their values.

What is an address descriptor?

It lists the current locations of a variable’s value. Memory is omitted when its copy is stale; a register-only live value may need a spill or final store.

Why are some copies missing from the instruction listing?

A copy can make its destination another name for the same resident value. The descriptors still change even when no physical register move is needed.

Why is a value stored and loaded again?

A limited register budget can require spilling a live register-only value. It is stored before overwrite and reloaded when needed later.

Which live-out values should I list?

List the scalar names whose final values are needed after the block. Blank keeps every assigned scalar; an explicit smaller contract can change which values require stores.

Does the cost mean processor cycles?

No. It is one base unit per instruction plus charges for memory and immediate operands. Real timing and instruction sizes depend on an architecture that this page does not model.

Is the generated code optimal?

No global optimality claim is made. The generator uses a transparent local allocation heuristic so its register choices and spill decisions can be studied.

How is the target code tested?

Tests interpret the original TAC and generated register code on randomized integer inputs. They also verify descriptor snapshots, alias handling, next uses and explicit exit stores.

Have a suggestion for Simple Code Generator?Share your feedback ↗