Virtual Machines and Bytecode

A bytecode instruction set is a machine language for a machine that does not physically exist. Each instruction is a small, densely encoded operation — push a constant, add two values, invoke a method, branch — chosen so that a simple interpreter can execute it quickly and so that a compiler can emit it directly from an abstract syntax tree or an intermediate representation. Unlike source code, bytecode is already linearized, has resolved scoping into slot or register indices, and often carries auxiliary metadata (constant pools, type descriptors, exception tables) that the runtime needs but a human never sees. A virtual machine (VM) in this context is the runtime program that fetches, decodes, and executes bytecode instructions in a loop, exactly as a physical CPU fetches, decodes, and executes native instructions. Two design families dominate. A stack-based VM keeps operands on an implicit operand stack; an instruction like `iadd` takes no operands in its encoding — it simply pops two values off the stack and pushes their sum. A register-based VM instead gives every instruction explicit operand fields that name virtual registers (really, slots in the current activation record), so an add instruction looks like `add r3, r1, r2`. The stack design yields extremely compact, easy-to-generate code (a compiler never has to allocate registers); the register design yields fewer total instructions and less data shuffling, at the cost of larger instruction words and a real register-allocation problem for the compiler. Both families share the same runtime scaffolding familiar from Runtime Organization: The Call Stack and Activation Records: each method invocation creates a frame holding local variables/registers, a return address, and (in stack machines) its own operand stack; frames are pushed and popped on calls and returns exactly like native call frames, and the VM's garbage collector must be able to scan every live frame to find object references — which is precisely why bytecode formats are designed to make the location and lifetime of references statically determinable.

Compilation to bytecode. A front end parses source into an AST or a lower IR, then a code generator walks that structure emitting instructions. For a stack machine, expression compilation is a straightforward postorder traversal: compile the operands (which leaves their values on the stack), then emit the operator instruction (which consumes them and pushes the result). For a register machine, the compiler must additionally choose which registers hold each subexpression's result, either via a simple stack-like counter of "next free register" (simple, sometimes wasteful) or a real register allocator.

The interpreter loop. At its core, every bytecode VM runs the same fetch–decode–execute cycle: ``` function RUN(frame): pc := frame.entryPoint loop: opcode := frame.code[pc] pc := pc + 1 switch opcode: case PUSH_CONST: idx := frame.code[pc]; pc := pc + 1 frame.stack.push(frame.constPool[idx]) case ADD: b := frame.stack.pop() a := frame.stack.pop() frame.stack.push(a + b) case LOAD_LOCAL: slot := frame.code[pc]; pc := pc + 1 frame.stack.push(frame.locals[slot]) case STORE_LOCAL: slot := frame.code[pc]; pc := pc + 1 frame.locals[slot] := frame.stack.pop() case JUMP_IF_FALSE: target := frame.code[pc]; pc := pc + 1 cond := frame.stack.pop() if cond == false: pc := target case CALL: methodRef := frame.code[pc]; pc := pc + 1 argc := lookupArity(methodRef) args := frame.stack.popN(argc) callee := newFrame(methodRef, args) result := RUN(callee) // recursive call, or an explicit call stack frame.stack.push(result) case RETURN: return frame.stack.pop() default: trap("illegal opcode") ``` A register-based version replaces `stack.push`/`pop` with direct reads and writes to indexed registers, and the operand fields are embedded in the instruction word itself: ``` case ADD_R: dst := frame.code[pc]; pc := pc + 1 src1 := frame.code[pc]; pc := pc + 1 src2 := frame.code[pc]; pc := pc + 1 frame.regs[dst] := frame.regs[src1] + frame.regs[src2] ```

Dispatch mechanics. The `switch` shown above is the textbook implementation but is not the fastest one. Three standard dispatch strategies, in increasing order of typical speed: 1. Switch dispatch — a bounds-checked jump table generated by the compiler from a `switch` statement; simple, portable, but incurs a bounds check and sometimes poor branch prediction because one branch instruction serves every opcode. 2. Computed-goto (threaded) dispatch — each opcode handler ends by jumping directly to the address of the next opcode's handler (`goto dispatchTable[opcode]`), spreading the indirect branch across many call sites, which modern branch predictors handle far better since each site tends to see a more stable pattern of successor opcodes. 3. <strong>Direct/inline threading</strong> — the bytecode stream itself is rewritten (once, at load time) to store handler addresses instead of opcode numbers, eliminating the table lookup entirely. All three compute the same* sequence of operations; they differ only in dispatch overhead, which matters because dispatch is the one piece of work repeated for every single instruction executed.

Constant pools and symbolic references. Bytecode formats (notably the JVM's `.class` format) avoid embedding raw addresses because the program must be relocatable and safely loadable from an untrusted source. Instead, instructions reference an index into a constant pool holding class names, method signatures, and literal values as symbolic entries; the VM resolves these lazily on first use and caches the resolution, a technique called quickening or inline caching at the bytecode level.

Bytecode verification. Before running untrusted bytecode, a security-sensitive VM statically checks that the instruction stream cannot violate type safety or stack discipline — no popping an empty stack, no jumping into the middle of an instruction, no treating an integer as an object reference. This is done once, at load time, via a data-flow analysis called the verifier (conceptually an abstract interpretation over a lattice of stack/local types), so the interpreter's hot loop can omit these checks entirely and simply trust the invariant.

Time. Each executed bytecode instruction costs $O(1)$ amortized work in the interpreter: one fetch, one decode/dispatch, and a constant amount of stack/register manipulation, plus occasional $O(1)$-amortized constant-pool resolution (memoized after the first hit). If a program executes $n$ total instructions at runtime, the interpreter runs in $O(n)$ time. The constant hidden inside that $O(1)$ — the dispatch overhead — is exactly what separates switch dispatch from threaded dispatch; it does not change the asymptotic bound but easily accounts for a 2–3× difference in wall-clock throughput, which is why production VMs care about it.

Space. Each active frame uses $O(k)$ space for $k$ locals/registers plus $O(d)$ for the maximum operand-stack depth $d$ reached within that method — both are statically known at compile time from the method's bytecode, so the VM preallocates exactly the right frame size with no dynamic growth needed. Total space is $O(F \cdot (k+d))$ for $F$ live frames, i.e., proportional to call depth, matching the space behavior of native call stacks discussed under Runtime Organization: The Call Stack and Activation Records.

Correctness — the stack-depth invariant. The central correctness property of a stack-machine bytecode program is: > At every program point, the operand-stack depth reached is the same along every control-flow path that reaches that point, and every value's static type at that point is determined independent of path. This is provable by induction over the control-flow graph: the base case is the method entry (stack depth 0), and the inductive step checks, for each instruction, that its effect on stack depth (push/pop counts, which are fixed per opcode) is consistent regardless of which predecessor block was taken to reach it — exactly the analysis a bytecode verifier performs as an abstract interpretation, propagating an abstract stack-shape lattice until it reaches a fixed point (a standard forward data-flow analysis, terminating because the lattice has finite height and updates are monotone). Once verified, the interpreter can assume the stack never underflows and every pop's type matches the consuming instruction, which is what allows the hot loop pseudocode above to omit bounds and type checks entirely — the checks happened once, at load time, instead of on every one of the $n$ executed instructions.

Tradeoffs, honestly. Stack machines produce smaller bytecode (no operand fields to encode) and trivial code generation, but need more instructions overall — pushing and popping intermediate results that a register machine could keep put — and each of those extra instructions pays a dispatch cost. Register machines cut instruction count substantially (empirically, Lua's register VM executes roughly 40–50% fewer instructions than an equivalent stack VM for the same program) but instructions are wider (more bits for register fields), code generation needs a register allocator, and instructions can update several registers at once, complicating GC root-scanning at arbitrary points. Neither design is strictly better; the choice trades code density and compiler simplicity against instruction count and interpretation speed, and both remain slower than compiled native code by roughly one to two orders of magnitude for computation-heavy code — the gap Just-In-Time Compilation exists to close.

Compile and trace the expression `(x + 1) * y` with `x = 4`, `y = 3`, for a stack machine.

Bytecode (with a 2-slot local array `[x, y]`): ``` 0: LOAD_LOCAL 0 ; push x 2: PUSH_CONST 1 ; push 1 4: ADD 5: LOAD_LOCAL 1 ; push y 7: MUL 8: RETURN ```

Result: 15, matching `(4 + 1) 3`. Note the max stack depth reached is 2 — this is exactly the value the verifier and the frame allocator compute statically, so the VM can allocate a fixed 2-slot operand stack for this method with no runtime resizing. Now the <strong>register-machine</strong> version of the same expression, using registers `r0=x, r1=y`, `r2` scratch: ``` ADD_RI r2, r0, #1 ; r2 := x + 1 MUL_RR r2, r2, r1 ; r2 := r2 y RETURN r2 ```

Same result, 3 instructions instead of 6 — the register form eliminates the explicit push/pop traffic entirely, at the cost of each instruction now carrying three operand fields instead of zero.

The Java Virtual Machine executes `.class` bytecode for Java, Kotlin, Scala, and Clojure, using exactly the verifier-then-interpret-then-JIT pipeline this article describes. The CPython interpreter compiles Python source to a stack-based bytecode executed by a switch-dispatch loop, which is why CPython performance discussions center on dispatch overhead. WebAssembly ships a verifiable, portable stack-based bytecode as a compilation target for C, C++, Rust, and Go, letting browsers and edge runtimes sandbox near-native-speed code from untrusted sources. Android's ART/Dalvik runtime uses a register-based bytecode explicitly because register VMs execute fewer instructions per operation, an important tradeoff on battery-constrained mobile hardware. The .NET Common Language Runtime executes a stack-based Common Intermediate Language shared across C#, F#, and VB.NET. In every one of these systems, the bytecode-interpretation stage described here is the fallback and bootstrap layer beneath a tiered execution strategy that escalates to Just-In-Time Compilation for hot methods, blending the portability of bytecode with the speed of native code.

Ask the tutor: How would you redesign the interpreter loop to support a JIT compiler that promotes hot methods to native code mid-execution?