VMimplementation

Stack-Based Virtual Machines

Operands live on a stack, so instructions do not need to say where their inputs are. `PUSH 1; PUSH 2; ADD` leaves `3` where the next instruction will look for it, and the whole encoding shrinks because of it.

The question

How does a virtual machine execute 1 + 2 when the ADD instruction has no operands?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

A program is an instruction array; the machine's data state is a last-in-first-out operand stack plus an array of named local slots. Every instruction is a function from (stack, slots) to (stack, slots), and operand *location* is not encoded anywhere — it is a convention: inputs are the top of the stack, output goes back on top. That convention is exactly what this representation exists to buy.

What this phase may assume or do

The code generator may emit any instruction sequence whose net effect on the stack matches what the following instructions assume. Concretely: at every instruction the stack must already hold the operands that instruction pops, in the order it pops them, and at every control-flow merge every incoming path must arrive with the same stack depth. Violating either is not a slow program, it is a malformed one — which is why real stack VMs run a verifier before they run the code.

Key points

  • The operand stack is a location convention, and the convention is what lets most instructions have no operand fields at all.
  • The cost of that convention is instruction count: every operand needs its own instruction to get it onto the stack.
  • The operand stack and the local slot array are different things with different lifetimes; most confusion about stack VMs is a confusion between them.
  • Stack depth must match at every control-flow merge. This is a well-formedness property, and real VMs verify it before executing anything.
  • Code generation for a stack machine is a post-order tree walk with no allocation decisions, which is the main reason so many portable formats are stack machines.
  • Operand order matters and is arbitrary: document which side SUB pops first, because nothing in the instruction says.

The convention that removes the operand fields

A three-address instruction has to say three things: where the left operand is, where the right operand is, and where the result goes. A stack instruction says none of them. ADD pops two values, adds them, pushes one. The locations are fixed by convention, so the instruction is just an opcode — one byte, in a real encoding.

The price is visible in the same sentence. Because the operands must already be on the stack, something has to put them there, and that something is more instructions. PUSH 1; PUSH 2; ADD is three dispatches to do one addition. A register machine spends one. That is the entire content of [[stack-vs-register-vm]], and it is worth seeing on a real trace before arguing about it.

The three instructions everything else in this lesson is built from
1PUSH 1        ; stack: [1]
2PUSH 2        ; stack: [1, 2]
3ADD           ; stack: [3]

The stack is written with the top on the right, which is the convention the VM stepper uses too. ADD pops the right operand first and then the left, so SUB on [5, 3] yields 2 and not -2 — an ordering that is arbitrary, must be documented, and is a classic source of bugs in hand-written code generators.

A real trace, not a diagram

The trace below is what our VM produced for print(1 + 2);. Every row is one instruction retiring, and the stack column is the state *after* it. Steps 0 through 2 are the three instructions above, unchanged. Steps 3 and 4 are the seam described in [[bytecode]]: the addition's IR destination register %0 became a local slot, so the result is stored and immediately reloaded.

Step 5 is where the program becomes observable. PRINT pops one value and emits it, and that pop is the only reason the stack is empty afterwards. Everything before it was internal bookkeeping that no correct optimization is obliged to preserve — see [[observable-behaviour]].

AtlasLang print(1 + 2); — the actual instruction trace, stack top last
Bytecode
  1. 0PUSH 1
  2. 1PUSH 2
  3. 2ADD
  4. 3STORE 0 ; %0
  5. 4LOAD 0 ; %0
  6. 5PRINT
  7. 6PUSH 0
  8. 7RETURN
  9. 8HALT
Operand stack (top last)
1
1 / 7The literal is in the instruction, so no slot and no memory access are involved.

Read it asRead the stack column downward: it goes up by one, up by one, down to one, empty, one, empty. That rise and fall is the invariant a verifier checks — at the end of a statement the stack must be back where it started, or the generator has leaked. Note also what the trace does *not* contain: instruction 8, HALT, never executes, because RETURN in the outermost frame ends the run. HALT is a backstop for a function that falls off the end of its code, not the normal exit.

Locals are not the stack

simplifiedOurs has one operand stack shared by all frames, with stackBase recorded per frame and the stack truncated back to it on return. The JVM specifies a separate operand stack per frame with a maximum depth computed at compile time and checked by the verifier; CPython 3.11 and later interleaves frames in one contiguous "data stack" chunk for cheaper calls. All three are correct designs; only ours would let a malformed callee corrupt a caller if the truncation were removed.

A stack machine has two places to keep values and they do different jobs. The operand stack is scratch space for the expression currently being evaluated; it is deep during a nested expression and empty between statements. The local slots are the variables — an array per call frame, indexed by number, alive for the whole call.

Confusing the two is the most common way to misread a stack VM. LOAD 0 does not "pop a local"; it copies slot 0 onto the stack. STORE 0 does not "push"; it moves the top of the stack into slot 0 and shortens the stack. The slot array is what makes a variable readable twice; the stack is what makes an expression evaluable once.

  • Slots are numbered, not named. The names in our disassembly are comments the VM never reads — at runtime, a is 0.
  • Parameters occupy the first slots, in declaration order, so CALL can write arguments into them positionally without knowing anything about the callee's body.
  • A slot read before any write yields a default rather than a fault in our VM, which is a simplification a real verifier would reject: the JVM verifier proves every local is definitely assigned before use.
  • The stack is per-invocation in principle; ours is one shared array with a saved base per frame, restored on return so that a callee cannot leak stack into its caller.

Why so many real VMs chose this

implementationThe JVM, CPython, .NET IL and WebAssembly are stack machines as of their current specifications; Lua 5.x and Android's Dalvik/ART are register machines. Neither camp is drifting toward the other, but the individual implementations do specialize heavily inside their format — CPython 3.11 onward rewrites hot instructions into specialized variants at runtime, which blurs "one opcode, one meaning" without changing the format.

Stack machines dominate deployed bytecode formats — the JVM, CPython, .NET IL and WebAssembly are all stack machines — and the reason is not raw speed. It is that the code generator is trivial. Emitting for a stack machine is a post-order walk of an expression tree with no allocation decisions at all: visit the left child, visit the right child, emit the operator. There is no register allocator, no spilling, and no interaction between the shape of the expression and the number of names available.

That triviality matters most for the people who are not you. A stable stack bytecode is easy to *generate*, so other languages target it; it is easy to *verify*, because stack depth and type effects can be computed by a linear scan; and it is easy to *interpret*, so a new host platform gets a working implementation quickly. Those three properties are why a format like WebAssembly is a stack machine even though its consumers overwhelmingly compile it away — see [[wasm-model]].

How it works

The steps, in the order the compiler takes them.

  • The VM holds an instruction pointer, an operand stack and a stack of frames; each frame owns a slot map and remembers where to resume in its caller.
  • Each iteration fetches the instruction at ip, increments ip, and switches on the opcode.
  • PUSH appends its literal. LOAD n appends a copy of slot n. STORE n removes the top value and writes it to slot n.
  • A binary opcode pops the right operand, pops the left operand, computes, and pushes one result — so its net effect on depth is minus one.
  • JUMPF pops a value and assigns ip only if it is falsy; JUMP assigns ip unconditionally.
  • CALL pops the arity's worth of arguments, records the current stack depth as the new frame's base, and pushes a frame whose slots are those arguments.
  • RETURN pops the result, discards anything the callee left above its base, pushes the result, and resumes the caller at the recorded instruction.

How it breaks

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

  • The generator emits a value-producing expression as a statement and forgets to POP. The stack grows by one per iteration and a long-running loop dies with an out-of-memory that names nothing relevant.
  • Two branches of an if leave different stack depths, and the code after the merge reads whatever happened to be underneath. The symptom is a value that is correct when the condition is true and nonsense when it is false.
  • The operand order for a non-commutative opcode is implemented one way in the generator and the other way in the VM, so a - b computes b - a. Addition and multiplication tests all pass.
  • A slot index exceeds the frame's slot array; ours returns a default and keeps going, which turns a code-generation bug into a wrong answer instead of a crash.
  • A callee leaves values on the shared stack and the return path does not truncate, so the caller's subsequent pops read the callee's garbage — a corruption that only manifests after a call returns normally.

When it helps

  • You are writing the code generator by hand and want it to be a hundred lines rather than a thousand.
  • The bytecode is a public format that other compilers will target, and you want the barrier to entry low.
  • You need cheap verification: stack effects can be checked in a linear pass, which is what makes untrusted bytecode executable at all.
  • You are porting to a new host and want a working interpreter quickly, before any performance work.

When it hurts

  • Interpreter throughput is the binding constraint and you have already exhausted dispatch tricks — the extra instructions per operation are inherent, not incidental.
  • You want to reuse a classical register allocator or a peephole optimizer from a native backend; both are written against operands with names, and a stack has none.
  • Expression-heavy numeric code, where the ratio of stack shuffling to arithmetic is worst.

What it costs

Every one of these is paid by something.

  • Implicit operands buy a tiny encoding and a trivial code generator, and pay roughly two extra instructions per binary operation — each one a full fetch, decode and dispatch.
  • A shared operand stack buys cheap calls and pays in isolation: without an explicit truncation on return, a buggy callee corrupts its caller, and the bug surfaces after the call rather than inside it.
  • Cheap verifiability buys the ability to run untrusted code and pays by constraining the format: rules like "stack depth must agree at every merge" forbid instruction sequences that would otherwise be legal and faster.
  • Numbered slots buy fast local access and pay in debuggability — the name is gone unless you emitted a side table, so a stack trace shows slot 3 and not total.

What else you could do

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

  • A register VM names its operands, so one instruction does what three do here — fewer dispatches, larger instructions, and a code generator that needs allocation logic: [[register-based-vm]].
  • A closure-compiling interpreter avoids the format entirely by turning each node into a host-language closure, keeping the tree's structure while removing the per-node type switch.
  • Direct threading with a token-threaded instruction array replaces the opcode with the address of its handler, which changes the dispatch cost without changing the stack model: [[dispatch-loop]].
  • A "stack machine on the surface, registers underneath" design, which is what a JIT over a stack bytecode does: the front format stays easy to generate and verify, and the actual execution uses registers — see [[jit-compilation]].

See it for yourself

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

  • Step it yourself at /compilers/vm: the operand stack is rendered top-last and updates on every instruction, so the rise and fall in the trace above is directly visible.
  • python -m dis on any function; watch LOAD_FAST/BINARY_OP/STORE_FAST and count how many instructions each expression costs.
  • javap -c shows both the instructions and, in -v mode, the computed stack= and locals= maxima the verifier uses.
  • For WebAssembly, wasm2wat prints the stack-machine text form, and wasm-objdump -d prints the instruction stream with the stack effects annotated.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "The stack is where variables live." Variables live in slots. The stack holds intermediate values of the expression currently being evaluated, and is normally empty between statements.
  • "Stack machines are slower because stacks are slow." The stack is an array and its top is always in cache. The cost is the extra *instructions*, and therefore the extra dispatches, not the memory.
  • "ADD takes no operands, so it must be a pseudo-instruction." It is a real instruction; its operand locations are simply fixed by convention rather than encoded.
  • "If the code type-checked, the bytecode is well-formed." Type checking happened on the AST. Nothing about a well-typed program prevents a code generator from emitting an unbalanced stack, which is why the verifier is a separate stage.

Misconceptions

The claim, and what is actually true.

A stack VM needs no registers because it has no register allocation.
The *virtual* machine has no registers. The interpreter running on real hardware keeps the instruction pointer, the stack pointer and the current opcode in real registers, and how well it does that is most of an interpreter's performance story.
The operand stack and the call stack are the same stack.
They are separate concerns even when they share an array. One holds expression temporaries; the other holds frames with return addresses and slot arrays. Merging them is a design choice with consequences for security and for tail calls.

Go deeper

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

overview

Instructions take their inputs from the top of a stack and leave their results there. To compute 1 + 2, push 1, push 2, then say ADD — the addition does not need to be told where its numbers are, because there is only one place they could be. That is why a stack VM's instructions are so small.

practical

When you write the code generator, the rule is a post-order walk: emit the left subtree, emit the right subtree, emit the operator. Statements that produce a value you do not want need an explicit POP, and forgetting it is the single most common bug — it does not fail immediately, it leaks. Keep an assertion that the stack is empty at the end of every statement and you will catch it at the source instead of ten thousand iterations later.

advanced

The interesting engineering above a plain stack machine is stack caching: keeping the top one or two stack entries in host registers rather than in the array, with the interpreter tracking at compile time which "state" each instruction handler expects. It removes a large fraction of the memory traffic the naive design creates, at the cost of multiplying the number of handlers — one per opcode per cache state. It is the same trade as superinstructions in [[interpreter-performance]]: buy fewer memory operations and fewer dispatches with more generated interpreter code, and pay for it in instruction-cache pressure.

How much this depends on

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

implementationThe JVM, CPython, .NET IL and WebAssembly are stack machines; Lua 5.x and Dalvik/ART are register machines. Statements about "how bytecode works" that assume a stack are wrong for the latter group, and the difference shows up in the disassembly immediately.
simplifiedOur VM shares one operand stack across frames and restores a saved base on return, rather than giving each frame its own stack with a verified maximum depth as the JVM specification requires. It also tolerates reading an unwritten slot, which a real verifier rejects at load time.
typicalPop order for non-commutative operations — right operand first — is what our VM does and what the JVM and CPython do. It is a convention, not a law, and a VM that chose the other order would be equally correct and incompatible.

If you were asked this in an interview

  • Trace PUSH 1; PUSH 2; SUB and tell me what is on the stack. Now tell me what you had to assume.
  • Why do real stack VMs verify bytecode before running it, and what property are they checking?
  • You see the operand stack growing steadily in a long-running loop. What kind of bug is that, and where would you look?

Connections

DSAstack
Computer Architectureregistersinstruction-cache
Domains that do not exist yet
  • Programming Languages & Runtime Internals — How a running VM represents the values it pushes — tagging, boxing, and what the garbage collector must be able to find on the operand stack
    Our stack holds JavaScript numbers, so we never face the question a real VM faces on every push: is this slot a reference the collector must trace? Getting that wrong is how a VM collects a live object, and answering it is the runtime's job, not the code generator's.