Stack Machines and Register Machines as Bytecode Targets

A bytecode format has to answer one question before any other: where do an instruction’s inputs live? Two answers dominate. In a stack machine the operands are implicit, taken from the top of an evaluation stack, and the instruction names only the operation. In a register machine each operand is named by a slot index carried in the instruction word. The choice determines how wide instructions are, how many of them a compiler emits for a given expression, how much type state the verifier has to track, and how much work the interpreter does per source-level operation. It also determines which kinds of code are cheap to represent and which are awkward.

Implicit operands and the cost of a stack discipline

A stack machine instruction such as iadd in the Java Virtual Machine carries no operand fields at all. It pops two values, adds them, and pushes the result. A compiler for such a target emits code by walking the expression tree in post-order: push the left operand, push the right operand, emit the operator. No register allocation happens at the bytecode level, because there are no registers to allocate. The compiler only has to track the maximum depth the stack reaches, which it records as a single number in the method header.

The JVM stores that number as max_stack, an unsigned 16-bit field, so a method’s operand stack is capped at 65,535 slots. A slot is nominally 32 bits; long and double values occupy two consecutive slots, which is why a method that manipulates doubles reaches the limit twice as fast. The same encoding applies to max_locals, also a u2, which bounds the local variable array rather than the stack.

The benefit is density. Most JVM opcodes are a single byte, and the ones that name a local variable or a constant pool entry take one or two extra bytes. Because operands are implied, the same iadd serves every addition regardless of where the values came from. Decoding is trivial: read a byte, index a table, jump.

The cost is instruction count. Every intermediate value must be explicitly produced and consumed, so a stack machine executes roughly one dispatch per node of the expression tree. Storing a value to a local and reading it back costs two instructions where a register machine would use one move, and often no instruction at all if the allocator can keep the value in place. Deeply nested expressions produce long runs of push and pop instructions whose only purpose is to shuffle values into position.

Fixed-width words and the register alternative

A register machine names its operands. Lua’s bytecode is the clearest example of the compact form: every instruction is exactly one 32-bit word, partitioned into an opcode field and several register or constant fields. An addition looks like ADD A B C, meaning the value in register B is added to the value in register C and stored in register A.

Fixed width buys cheap decoding. The interpreter reads a word, extracts the opcode with a shift and a mask, and extracts the operand fields the same way, with no variable-length parsing and no bounds checks on the instruction stream. It also buys predictable instruction addresses: the instruction pointer advances by four bytes, so a jump target can be stored as a word offset rather than a byte offset.

It costs encoding space. The three-operand form has to fit inside the word, so the fields are narrow. In Lua 5.3 and later the destination register field is eight bits wide, and the virtual machine caps a function at 255 registers because that field cannot address more. A function that needs more locals has to spill some of them into a table or restructure. The same narrowness applies to constants: an instruction that loads a constant by index can only reach as many constants as its field can address, which is why such formats usually provide a wider load form alongside the narrow one.

The instruction count falls. An expression that a stack machine compiles to nine instructions costs a register machine fewer, because intermediate results stay in named slots instead of being pushed and popped and immediately read back. Whether the total work falls with it depends on what dominates: dispatch overhead, or the bytes moved per instruction.

What the verifier sees

Type checking is the second forcing function. A stack machine has a natural abstract state: a stack of types plus an array of local types. Each instruction has a fixed effect on that state, so verification is a linear scan over the code with a merge at each branch target. When two paths reach the same instruction, the verifier checks that both arrived with the same stack shape and compatible local types, and rejects the method if they did not. Because the operand stack is the only place temporaries can live, the verifier never has to reason about unnamed dead values.

A register machine has to track a type per register, including registers that are dead on some paths and live on others. Merging is a per-slot lattice join rather than a stack comparison, and the verifier must handle slots that hold a reference on one path and an integer on another, which is legal as long as neither is read before being overwritten. That is more state per program point and more work per instruction.

The same asymmetry appears at garbage collection boundaries. A collector walking a suspended frame needs to know which slots hold references. In a stack machine the operand stack slots above the current depth are dead by construction, so the live set is the stack prefix plus the live locals. In a register machine the live set has to be computed from liveness information, because a register may hold a stale reference that will never be read again. Interpreters for register formats therefore carry per-instruction liveness maps or accept conservative retention.

Where each model hits its limits

The stack model degrades when the encoding runs out of operand bits. The JVM indexes locals with 16 bits, but most local instructions carry a single-byte index, so any local index above 255 requires the wide prefix, which replaces the one-byte index with a two-byte one and so lengthens the instruction. Constant pool entries are capped at 65,535 by the u2 index, and the ldc instruction takes a single-byte index, so it can only reach the first 256 entries; the three-byte ldc_w exists precisely to cover the rest. These are not incidental details, they are the shape of the format showing through.

The register model degrades when a function needs more slots than the fields can address. Spilling into an auxiliary array is possible, but it reintroduces the load and store instructions the register design was meant to avoid. Fixed-width formats also waste bits on instructions that use fewer operands: a jump needs one target, not three fields.

Both models have to decide how to represent control flow. The JVM allows arbitrary jumps by byte offset, which forces the verifier to reconstruct stack shapes at every target. WebAssembly keeps a stack machine but restricts control flow to structured blocks, loops, and branches to labels. Because the stack height at the start and end of every block is statically determined by the block’s type, validation can be done in a single pass without stack maps, and the same property makes the format compilable to native code without a separate analysis phase.

What actually decides the choice

The choice tracks the compiler, not the hardware. A stack format lets a simple front end emit code without a register allocator, which is why teaching compilers and small language implementations favor it. A register format moves the allocation problem into the bytecode compiler, where it can share machinery with the source language’s own optimizer, and pays for it with wider instructions and a harder verifier.

Transport favors the stack. Bytecode that travels over a network or is embedded in a page is dominated by code size, and a one-byte opcode with implicit operands is hard to beat for simple operations. Long-running execution favors registers, where fewer dispatches per operation matter more than bytes. The measurement literature on the two designs, notably the comparison by Shi, Gregg, Beatty and Ertl, found that register code executes fewer instructions and fewer dispatches while occupying more bytes, with the balance shifting by workload. Neither wins unconditionally, which is why both remain in widely deployed formats: the JVM and WebAssembly on one side, Lua and Dalvik on the other.

A third option exists and is common in practice: a stack machine with a local variable array, as in the JVM and CPython. Locals are named by index, so values that live across statements avoid the push and pop churn, while temporaries stay implicit. The result is a hybrid whose encoding is small for expression evaluation and whose locals behave like registers. Recognizing which parts of a given format are stack-like and which are register-like is usually more useful than classifying the format as one or the other.

How that instruction stream is then dispatched, one instruction at a time through a table of handler addresses, is a separate design problem with its own costs, covered in computed goto and direct threading. Where the operands a register machine names actually live at run time is the frame layout question covered in interpreter stack frame layout.