Stack Bytecode: Fixed Stack Effects and the Dispatch Loop

A stack machine has no register operands. An addition instruction names nothing: it pops two values from an operand stack, adds them, and pushes the result. Each instruction is therefore shorter than a register encoding of the same operation, and the encoding of an operation is a single opcode byte. The price is that operands move through memory, and the design question for the whole family of stack VMs is how much of that traffic the implementation can keep in registers anyway.

Operands that cost no bytes

Consider x = a + b where a, b, and x are locals. In a stack encoding the sequence is: push local 0, push local 1, add, store local 2. Each of those four instructions carries one operand byte, the local index, and the opcodes themselves are one byte. No instruction needs to encode three register numbers.

That compactness has a structural consequence. Because operands come from a stack that the instruction stream manipulates in order, the position of a value is determined by the instructions executed before it. A verifier can therefore compute the stack depth at every instruction offset without running the program, by walking the control flow graph and applying each opcode’s fixed stack effect. The Java Virtual Machine Specification defines this in its type-checking verifier: each instruction has a known effect on the depth and types of the operand stack, and a program that reaches an instruction with an incompatible depth is rejected at load time rather than failing later. WebAssembly goes further and makes validation a static property of the module: every instruction has a declared input and output type sequence, and the validator checks them compositionally.

Static stack depth is what makes a fast interpreter possible. If the maximum depth of the operand stack is known at compile time, the frame can be allocated as one contiguous block with the locals, and the stack pointer is a register pointing into that block rather than a heap-allocated object. The compiler computes the maximum depth by the same walk the verifier performs, and emits it as part of the code object’s metadata.

The frame is one array with two regions

A typical frame layout places the operand stack above the locals in a single allocation:

        higher addresses
        +--------------------------+
        | operand stack (grows up) |
        +--------------------------+
        | locals                   |
        +--------------------------+
        | frame header / metadata  |
        +--------------------------+
        lower addresses

Locals are addressed by index from the frame base, and the operand stack by offset from a stack pointer that starts just above the locals. Push decrements the address or increments an index depending on growth direction; the choice is arbitrary but must be consistent, and real implementations differ. CPython’s frame object holds a pointer to its value stack and a stack pointer; the locals of a function are addressed by slot numbers that the compiler assigned, rather than by name.

Because both regions are in one array, a push is a store through the stack pointer and an increment. A pop is a decrement. Neither touches the allocator. The expensive operations are the ones that move values between the stack and memory that is not the frame: loading a local that lives in a cell because a closure captured it, loading a global, or calling a function.

The dispatch loop and its two shapes

The interpreter’s main loop reads an opcode, jumps to the code for that opcode, and repeats. Two implementations dominate.

A switch-based loop keeps the instruction pointer in a local variable and uses a switch on the opcode. Compilers translate this to a jump table, so the dispatch is one indirect branch, but the loop has a single back edge and the branch predictor sees one target per opcode value. A computed-goto loop, available as a GNU C extension, places a label at the top of each opcode’s code and dispatches with a table of label addresses. Each opcode ends with its own indirect jump, which gives the predictor a separate history per opcode and, in practice, is usually found to predict better than the shared switch back edge. The technique appears in the interpreters of CPython, Ruby’s YARV, and many others.

static uint8_t read_u8(const uint8_t **ip) { return *(*ip)++; }
static int32_t read_i32(const uint8_t **ip) {
    uint32_t v = (uint32_t)(*ip)[0] | (uint32_t)(*ip)[1] << 8 |
                 (uint32_t)(*ip)[2] << 16 | (uint32_t)(*ip)[3] << 24;
    *ip += 4;
    return (int32_t)v;
}

static void run(Frame *f) {
    const uint8_t *ip = f->code;
    Value *sp = f->stack;
    static void *dispatch[] = { &&op_const, &&op_add, &&op_load, &&op_store };
    goto *dispatch[*ip++];
op_const: sp->i = read_i32(&ip); sp++;              goto *dispatch[*ip++];
op_add:   sp -= 2; sp->i = sp[0].i + sp[1].i; sp++;  goto *dispatch[*ip++];
op_load:  *sp++ = f->locals[read_u8(&ip)];           goto *dispatch[*ip++];
op_store: f->locals[read_u8(&ip)] = *--sp;           goto *dispatch[*ip++];
}

The loop above is deliberately naive: it assumes integers, has no bounds checks, and would need a tag check per arithmetic operation to be correct for a dynamically typed language. Each of those additions is a real cost. A tag check per add is a load, a compare, and a branch, so a dynamically typed stack VM spends roughly as much on checking types as on doing arithmetic, unless the compiler specializes. That specialization is what a just-in-time compiler provides, and the inline cache article covers how the check becomes cheaper than a branch.

Why stack machines are easy to generate code for

The reason so many language implementations use a stack VM is not speed. It is that code generation becomes a post-order traversal. For an expression node, emit code for the left child, emit code for the right child, emit the operator. Nothing has to be allocated to hold a temporary, because the stack holds it, and no register allocation pass is needed. A compiler for a stack target can be very small; a compiler for a register target needs liveness analysis and allocation before it can emit anything correct.

The same property makes stack code easy to generate from a tree at run time, which is how a tree-walker can gain a bytecode tier without rewriting its front end. The tree-walking interpreter article describes the per-node cost that this compilation removes.

The cost of that convenience is instruction count. A stack encoding executes more instructions per source operation than a register encoding, because every operand must be pushed and popped explicitly. On a machine where dispatch costs several cycles, instruction count is close to a direct multiplier on run time. This is the trade that register bytecode reverses: fewer instructions, harder code generation.

Verification as a load-time obligation

Static stack typing is not only an optimization; for some languages it is a security boundary. The JVM’s verifier exists because bytecode can arrive from an untrusted source, and the virtual machine must not execute code whose stack discipline is wrong, since a mismatch would let a value of one type be interpreted as another. The verifier reconstructs the type of every stack slot and local at every program point, merges types at control-flow joins, and rejects the method if a merge produces an inconsistent type. The merge rule is a least upper bound in the type lattice; two branches that leave an integer and a float respectively at the same depth do not merge, and the method is invalid.

WebAssembly’s validation is structurally simpler because the instruction set is typed. Each instruction declares its operand types, blocks declare their result types, and validation is a single pass over the instruction sequence maintaining a stack of types. A br to an outer block requires the stack to match that block’s label arity. Because types are declared rather than inferred from usage, there is no fixpoint computation and no merge.

Both designs share a consequence for implementers: the operand stack’s maximum depth is a static constant, so a frame can be allocated once at function entry. That eliminates the need for a stack overflow check per push, provided the frame allocation itself checks the total. The check moves from the hot path to the prologue.

The edge cases that bite

Values wider than a slot. The JVM treats long and double as occupying two stack slots, and the specification requires that the two halves not be split across a boundary in ways that would let them be addressed individually. Implementations that store 64-bit values in a single slot must still model the two-slot accounting in the verifier, and the mismatch between the model and the representation is a classic source of bugs in the dup2 family of instructions, which exist precisely to duplicate one or two slots depending on what is on top.

Operand stack overflow in recursive code. Because frames are allocated on entry and their depth is static, deep recursion exhausts the VM’s stack space, not the host’s. The JVM throws StackOverflowError when the thread’s stack cannot accommodate another frame; the check is on frame allocation, and the size of the frame is known, so the check is a comparison against a limit rather than a per-push test.

Exceptions leaving the stack dirty. When an exception unwinds a frame, the operand stack may hold arbitrary partially computed values. The handler entry point must reset the stack pointer to the depth the verifier recorded for that handler, not to whatever depth the faulting instruction left. Implementations that record exception table entries as (start offset, end offset, handler offset, stack depth) get this right; implementations that record only the handler offset have to reconstruct the depth.

Debugging information that must survive compilation. Because instructions no longer correspond to source expressions, every offset needs a mapping back. The JVM emits a LineNumberTable attribute per method, and the LocalVariableTable maps slot indices to names and ranges. Without them, a stack trace has offsets and no lines, and a debugger cannot show local values. The tables cost bytes in the class file, and stripping them is a standard size optimization for deployed code.