VMimplementation

Compiling to Bytecode

AST to IR to bytecode to VM. The translation rule fits in one line — a three-address `%d = a op b` becomes push a, push b, op — and the interesting parts are what the operand stack replaces and why we emit from pre-SSA IR.

The question

How do I turn a syntax tree into bytecode my VM can execute?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

The input is pre-SSA three-address IR: a list of basic blocks, each a sequence of instructions over virtual registers with an explicit terminator. The output is a flat instruction array with absolute jump targets and a slot table. The generator's job is to erase two things — block structure, which becomes instruction indices, and virtual registers, which become either stack positions or slots.

What this phase may assume or do

The emitted sequence must produce the same observable behavior as the IR under the VM's semantics. Three preconditions make that hold: instructions are emitted in the IR's existing evaluation order, so no side effect moves; every virtual register is stored before it is loaded on every path, so no value is read undefined; and every jump target is patched to the first instruction of the block it names, so no branch lands mid-instruction-sequence. Emitting from a form containing phi nodes violates the first of these, because a phi has no execution semantics at all.

Key points

The core translation is one line: %d = a op b becomes push a, push b, op, store d — the operand stack stands in for the destination register.
Emitting from IR rather than from the tree means the evaluation order was already decided, so the code generator makes no semantic decisions.
Bytecode is generated from pre-SSA form, or from SSA after phi destruction, because a phi node has no execution semantics.
Flattening a block graph into an array requires a patch pass for forward jumps — the same two-pass shape as an assembler and a linker.
Slot allocation for virtual registers is the stack machine's stand-in for register allocation, and it is much easier because slots are plentiful.
Peepholes at the bytecode level are local and cheap; anything needing dataflow belongs earlier, on the IR.

The translation rule

Every three-address instruction has the shape "destination, operator, operands". Every stack-machine sequence has the shape "get the operands, apply the operator, put the result somewhere". The mapping between them is direct: push each operand, emit the operator, store into the destination. The operand stack is playing the part of the destination register, temporarily, between the operator and the store.

That is the whole code generator for arithmetic, and it is why having an IR pays for itself here rather than in the optimizer. The IR already fixed an evaluation order and already named every intermediate. Emitting bytecode straight from the tree is possible and is what many small implementations do, but then the code generator has to make the ordering decisions too, and those decisions are language semantics leaking into the backend — the argument of [[why-ir-exists]].

The rule, applied to let a = 1; let b = 2; print(a + b); — real compiler output

Pre-SSA IR

store a, 1
store b, 2
%0 = load a
%1 = load b
%2 = %0 + %1
print %2

Bytecode

▸  0  PUSH 1
▸  1  STORE 0 ; a
▸  2  PUSH 2
▸  3  STORE 1 ; b
▸  4  LOAD 0 ; a
▸  5  STORE 2 ; %0
▸  6  LOAD 1 ; b
▸  7  STORE 3 ; %1
▸  8  LOAD 2 ; %0
▸  9  LOAD 3 ; %1
▸ 10  ADD
▸ 11  STORE 4 ; %2
▸ 12  LOAD 4 ; %2
▸ 13  PRINT
▸ 14  PUSH 0
▸ 15  RETURN
▸ 16  HALT

Read it asThe highlighted four instructions are the rule itself: push the left operand, push the right operand, apply, store. Everything around them is the cost of taking virtual registers literally — %0 and %1 each get a slot, so each IR load becomes a LOAD and a STORE. A generator that treated a register with one use as "leave it on the stack" would emit six instructions here instead of thirteen, which is exactly the peephole a production backend runs and ours deliberately does not, so that the IR-to-bytecode mapping stays one-to-one and readable.

Why we emit from pre-SSA IR

implementationThat AtlasLang can read the pre-SSA IR is a property of our pipeline, not a general technique: we keep both forms alive because the pipeline explorer renders them side by side. A production compiler runs its optimizations on SSA and would be discarding the optimized program if it generated code from the pre-SSA form, so it must destruct phis into copies instead. LLVM and GCC both do exactly that, in a pass that runs immediately before instruction selection.

SSA is the form the optimizer wants: one definition per name, so every use points at exactly one definition. But a phi node is not an instruction. It says "this value is whichever of these it was, depending on which edge we arrived on", and no machine and no VM can execute that — there is no opcode for "look at how you got here". Bytecode generation therefore happens after SSA has been left, which is the entire point of [[out-of-ssa]].

In our compiler, leaving SSA is free, because the pre-SSA form is still available: it has load and store against named slots, and a stack machine's locals *are* named slots. So the code generator reads the pre-SSA IR directly. A native backend cannot take that shortcut — it has to run the optimizer on SSA and then destruct the phis into copies on the incoming edges, and placing those copies correctly on critical edges is one of the genuinely fiddly parts of a backend.

What a phi would mean if it reached the code generator

1block merge:
2  %5 = phi [%3, from then], [%4, from else]
3  print %5
4 
5; there is no PHI opcode. The VM would have to know
6; which edge it arrived on, and an instruction pointer
7; does not carry that information.

Our code generator has an explicit phi case that emits a poisoned constant with the comment "phi reached codegen — out-of-SSA did not run". That is deliberate: a silently-emit-nothing case would produce a program that runs and returns wrong values, which is the worst possible failure. Failing loudly at the seam is worth an unreachable branch.

Blocks become indices, and jumps need patching

The IR is a graph of blocks; the bytecode is an array. Flattening means choosing an order for the blocks and recording where each one starts. A branch to a block that has not been emitted yet cannot know its target, so the generator emits a placeholder and records a patch — "instruction 12 needs the address of block merge" — and resolves every patch after the last block is laid down.

This is the same two-pass shape as an assembler resolving forward labels, and as a linker resolving relocations. It recurs at every level for the same reason: you cannot write down an address you have not yet chosen. Recognizing the pattern is worth more than the details — see [[relocations]].

Three blocks, and the instruction indices they became

entryentryentry↺ loop header
```
%0 = load n
%1 = %0 < 3
branch %1 -> body, exit
```
Emitted first, at index 5. The branch is emitted with two placeholder targets.
bodybodylatch
```
%2 = load s
...
store n, %6
jump entry
```
Starts at index 14. Its terminating jump goes backwards, so its target is already known and needs no patch.
exitexit
```
%7 = load s
print %7
return
```
Starts at index 33 — which is the value patched into the JUMPF back in the entry block.

Edges

entry→bodyn < 3
entry→exitotherwise
body→entryloop

Read it asThe forward edge to exit is the one that needs patching: when the generator emitted JUMPF it did not yet know that exit would start at 33. The back edge to entry needs none, because entry was emitted first and its index was already recorded. That asymmetry is why the patch list exists at all — and it is exactly why an assembler makes two passes over a file with forward labels.

What a real backend does here that we skip

Our generator is deliberately naive in one specific way: it materializes every virtual register into a slot, even when the value is produced and consumed by adjacent instructions. A production bytecode compiler tracks whether a value is already on the stack and skips the store-load pair, which is a local peephole with a clear legality condition — the value must have exactly one use, that use must be the next consumer, and nothing between them may touch the stack.

It also does not do constant folding at the bytecode level, choosing instead to fold on the IR where the analysis is easier. That is the right split: [[constant-folding]] wants a representation with named values and a dataflow lattice, and the bytecode has neither. The general rule is that optimizations belong at the level where the information they need is cheapest to obtain — which is [[phase-ordering]] restated for a backend.

The store-load elision our generator does not perform

Before

ADD
STORE 4 ; %2
LOAD 4 ; %2
PRINT

After

ADD
PRINT

Legal only when

Only if slot 4 has exactly one use — this LOAD — no other instruction reads or writes it afterwards, no branch target lands between the STORE and the LOAD, and no debugger contract requires the intermediate to be inspectable at that point. Under those conditions the value never needs to exist anywhere but the stack.

Illegal when

If %2 is read again later, if a jump target lands between the pair — in which case an arriving branch would find the stack one shallower than it expects — or if the slot corresponds to a user variable a debugger is entitled to display. The middle case is the subtle one: the transformation is locally correct and globally wrong, and it fails only on the path that enters through the label.

How it works

The steps, in the order the compiler takes them.

Allocate slots: parameters first in declaration order, then declared locals, then one synthetic slot per virtual register the IR mentions.
Walk the blocks in order, recording the current code length as each block's start index.
For each IR instruction, emit the fixed sequence its opcode maps to: operands pushed left to right, then the operation, then a store to the destination slot.
For each block terminator, emit a jump, a conditional jump plus a jump, or a value push plus RETURN, adding an entry to the patch list for every target whose address is not yet known.
After the last block, rewrite each recorded patch site with the start index of the block it named.
Append HALT so that control falling off the end of the code array stops rather than reading past it.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A patch is applied to the wrong instruction index and a branch lands in the middle of another block's sequence, so the VM executes a suffix of instructions with a stack that does not match — usually a stack underflow far from the branch.
A block is emitted but never has its start recorded, so its label patches to the end of the code and every branch to it silently becomes a halt.
A value-producing instruction is emitted for a statement whose result is discarded and no POP follows, leaking one stack entry per execution and killing long-running loops with an out-of-memory that names nothing useful.
Two virtual registers are mapped to the same slot because the slot table keyed on the wrong name, and a value is overwritten between its definition and its use — a wrong answer with no diagnostic.
An IR form containing phis reaches the generator and the phi case emits nothing, producing a program that runs and returns a plausible wrong number on exactly the paths that merge.

When it helps

You already have an IR and want an executable artifact without writing a native backend.
You want a stable, inspectable output to test the frontend against: bytecode diffs are a good golden-test target because they change only when the frontend's meaning changes.
You are building toward a JIT and need a bottom tier plus a place to attach profiling counters.
You need the same frontend to target several environments, and the bytecode is the portable middle — the argument of [[multiple-frontends-one-backend]] run in the other direction.

When it hurts

Very small programs compiled once and run once, where generation costs more than the interpretation it saves.
When the IR is not actually in a fixed evaluation order — generating from an unordered or partially ordered form pushes semantic decisions into the backend, which is where they are hardest to review.
When the target is a register VM: the mapping is closer to the IR, but slot reuse now needs real liveness information, and a naive generator will produce correct-looking code with live-range bugs.

What it costs

Every one of these is paid by something.

Generating from IR rather than from the AST buys a backend with no semantic decisions in it and pays for the IR itself — a lowering pass, a printer and a verifier that a tree-to-bytecode generator does not need.
A one-to-one IR-instruction-to-bytecode mapping buys readable output and easy debugging of the generator, and pays roughly a factor of two in emitted instructions against a generator that keeps values on the stack.
A patch list buys single-pass emission over an arbitrary block order and pays in a mutable code array plus a correctness obligation that every patch is applied — an unapplied patch is a silent wrong jump.
Materializing every virtual register into a slot buys a trivially correct generator and pays in frame size and in memory traffic on every instruction.

What else you could do

What a different compiler or language does instead, and when that is better.

Emit bytecode directly from the AST in a post-order walk, skipping the IR. Much less machinery, and the evaluation-order decisions move into the backend where they are easy to get subtly wrong.
Emit from SSA after destructing phis into copies on the incoming edges. Required if the optimizer runs on SSA and its output is what you intend to execute — [[out-of-ssa]].
Emit native code instead and skip the VM, which replaces slot allocation with real register allocation and a much larger backend — [[code-generation]].
Emit someone else's bytecode — JVM class files or WebAssembly — and inherit their verifier, JIT and tooling at the cost of fitting your semantics to their machine — [[webassembly]].

See it for yourself

The flag, dump or tool that shows you this directly.

Type any program at /compilers/pipeline and read the Bytecode panel beside the IR panel: every bytecode instruction is annotated with the IR block it came from.
Step the result at /compilers/vm to confirm the generated program actually does what the source says — the cheapest possible end-to-end check of a code generator.
CPython: dis.dis on a function with an if and a loop, and look for the jump targets; compare co_code offsets against the dis listing to see the patching that already happened.
For a real phi destruction, compile with clang -S -emit-llvm -O1 and then llc -print-after-all, and find the pass that removes the phis before instruction selection.

Plausible wrong readings

Stated the way a confident engineer states them.

"Bytecode generation is where the optimizations happen." Optimization happens on the IR, where values have names and dataflow analysis is cheap. What happens here is a local rewrite plus, at most, peepholes.
"The stack replaces the registers, so slots are unnecessary." The stack replaces the destination register only for the instant between the operator and its consumer. Anything that must survive that instant — a named variable, a value with several uses — needs a slot.
"Phi nodes are just moves, so the generator can emit them as copies." That is true and it is precisely what out-of-SSA does, on the incoming edges rather than at the phi's position. Emitting a copy where the phi sits is wrong, because it would run on every path rather than on the path it belongs to.
"Forward jumps need a two-pass compiler." They need a patch list, which a single pass over the blocks can maintain. Two passes is one way to implement it, not a requirement.

Misconceptions

The claim, and what is actually true.

The code generator decides evaluation order.

Lowering to IR decided it. If the generator is making that decision, the language's semantics are being defined in the backend, which is where nobody reviews them.

You need SSA to generate good code.

You need SSA to *analyze* code cheaply. You must leave it before generating, because phi nodes are not executable. SSA earns its keep in the middle-end and is an obstacle in the backend.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Take each IR instruction in turn and write out the bytecode that performs it: push the inputs, apply the operation, store the result. Keep a note of where each block of code starts, and when you are finished, go back and fill in the jump targets you did not know yet. That is a bytecode compiler.

practical

Three things will bite you. Forward jumps need a patch list, and an unapplied patch is a silent wrong branch — assert the list is empty at the end. Statements whose value is discarded need an explicit POP, and forgetting it leaks the stack. And the slot table must be keyed so that two distinct virtual registers can never collide; a Map from register name to index, populated on first use, is the whole solution and getting it wrong produces wrong answers with no error.

advanced

The design question worth arguing about is how much of the stack machine the generator should model. A generator that tracks stack residency — knowing that the result of the last instruction is already on top and need not be stored and reloaded — roughly halves the instruction count and turns the generator into a small abstract interpreter of its own output. That abstract state has to be reconciled at every control-flow merge, because a block reached from two places must be entered with the same stack shape from both, which is the same constraint the verifier enforces. In other words: the moment your generator gets clever about the stack, it acquires the verifier's obligations, and the honest way to hold them is to run the verifier on your own output in debug builds.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationOur generator reads pre-SSA IR because our pipeline keeps that form alive for the explorer. A compiler that optimizes on SSA cannot do this — it must destruct phis into edge copies first, or it would be executing the unoptimized program. LLVM and GCC both run phi elimination immediately before instruction selection for exactly this reason.

simplifiedWe materialize every virtual register into a slot and emit a STORE/LOAD pair around it. A production bytecode compiler tracks stack residency and elides most of those, roughly halving the instruction count. We keep them so that the bytecode panel and the IR panel line up instruction for instruction.

typicalThe two-pass "emit placeholders, then patch" structure is what assemblers, linkers and most bytecode generators do for forward references. Some generators instead pre-compute block addresses in a first pass and emit final targets in a second; the result is identical and the choice is about whether you would rather mutate the array or walk it twice.

If you were asked this in an interview

Give me the bytecode for c = a * b + 1 on a stack machine, and tell me where each operand came from.
Why can a code generator not emit a phi node, and what does a real compiler do about it?
You emit a forward branch to a block you have not generated yet. How do you write the target?

Connections

DSAstack dag

Computer Architectureinstruction-decode

Domains that do not exist yet

Programming Languages & Runtime Internals — The metadata the generator must emit alongside the instructions — line tables, stack maps, exception ranges
The instructions alone are not a usable artifact. A debugger needs instruction-to-span mappings, a collector needs to know which slots hold references at each safepoint, and an exception mechanism needs handler ranges. The compiler emits all three and the runtime consumes them, so getting the format right is a joint decision across the boundary.