Register Bytecode and Windowed Register Allocation in Lua

A stack machine names no operands, which makes its instructions short and its code generation easy. A register machine names operands explicitly, which makes each instruction do more. Lua’s virtual machine takes the second route with a specific twist: registers are not global, they are a window into a per-call stack frame, and the window’s base moves with every call. The design is a study in how a small instruction encoding can buy back most of the cost of naming operands.

Why naming operands saves instructions

Take a single statement, x = a + b, with the three values held in registers. A register-based encoding emits one instruction: add the contents of register b to register a and place the result in register x. The stack encoding needed four. The ratio is not constant, but for straight-line arithmetic and local variable traffic it is the dominant difference between the two families, and it is why Lua’s VM executes fewer instructions per source operation than a stack VM doing the same work.

The encoding cost is operands. A three-address instruction needs three register numbers. Lua packs each instruction into a single 32-bit word: an opcode field of six or seven bits depending on the version, and then fields that are interpreted according to the opcode’s format. The common formats are A, B, C, and k, where A is usually the destination, B and C are either register numbers or small immediate values, and k selects whether C is a constant-table index. With 8 bits for A and 8 or 9 bits for the operands, the reachable register set per instruction is under 256, and the constant table index is bounded similarly.

That bound is the central constraint. A function cannot address more registers than the operand fields allow, so the compiler must map an unbounded number of source-level variables onto a bounded window. The mapping is register allocation, and in Lua’s case it is deliberately simple: locals get fixed registers for the duration of their scope, and expression temporaries are allocated above them by a stack discipline that mirrors the shape of the expression.

The window and the moving base

Each function call gets a new frame on the VM’s value stack. The frame’s first slot is the base, and register R(i) means the slot at base + i. The calling convention places the function’s arguments in consecutive registers starting at the base, so a call instruction does not copy arguments: it reserves a region above the current temporaries, writes the callee and the arguments into it, and executes a call opcode naming that region.

/* Simplified: a call reserves a region and the new frame base lands on the callee slot. */
int base = frame->base + frame->freereg;   /* start of the argument region */
stack[base]     = callee;
stack[base + 1] = arg1;
stack[base + 2] = arg2;
int nresults = call(&stack[base], 2);       /* new frame's base is &stack[base] */

Two properties follow. First, arguments are passed in registers without a separate argument array, so a call is not a bulk copy of the argument list. Second, the callee’s register file is a different window over the same underlying array, which means the callee can address its own locals with small indices regardless of how deep the call stack is. Without the base, a callee’s locals would need indices proportional to the total stack depth, which would not fit in the operand fields.

The windowed design has a cost: the compiler must know, at each instruction, how many registers are live. A call’s argument region must not overlap the caller’s live temporaries, so the compiler tracks a “free register” pointer that advances as temporaries are allocated and retreats as they are consumed. The maximum value of that pointer is the function’s frame size, and it is computed by the same pass that emits code. The Lua compiler records it as the function prototype’s maxstacksize, which is exactly the frame’s register count.

Fitting a program into 255 registers

The compiler’s job is to keep maxstacksize small. Locals are assigned registers in declaration order and keep them for the whole scope, so a function with many locals has a high base for its temporaries. Temporaries are short-lived and are reused aggressively: after an expression’s value is consumed by its parent, its register becomes free again.

Nested expressions are where this gets tight. A call used as an argument to another call needs its own region, and that region sits above the outer call’s arguments. The depth of the deepest call chain determines the peak. Lua’s compiler emits code in a single pass over the syntax tree, allocating registers as it descends and freeing them as it ascends, which is why it does not need a separate liveness analysis. The price is that it cannot do global register allocation; a variable that is live across a loop keeps its register even if it is not used inside the loop.

Constants are the escape hatch. When a value is a literal or a compile-time constant, the instruction can name the constant table instead of a register, so R1 := R0 + 1 uses the immediate form rather than materializing 1 in a register. The constant table is per-function, one entry per distinct constant used by that function, and its index must fit in the operand field. This is the same idea as an immediate operand in a hardware ISA, applied to a bytecode whose operands are otherwise all registers.

When the program genuinely needs more than the field width allows, the compiler does not fail. It generates code that moves values through a smaller set of registers, or it splits the expression so that fewer values are live simultaneously. The consequence is extra instructions, and the cost is paid only by functions that are large enough to need it.

Upvalues and the values that cannot live in the window

A local that a nested function captures cannot stay in the window, because the frame it lives in disappears when the enclosing call returns. Lua’s answer is the upvalue: a small heap object holding a pointer to the value’s storage, shared between the closure and the frame. The compiler emits instructions that load and store through the upvalue rather than addressing the register directly, so a captured variable costs an indirection per access.

There are two upvalue flavors in the implementation, and the difference matters. An open upvalue points into the live stack frame and is shared by every closure created in that frame that captures the same variable; when the frame exits, the upvalue is closed, its value is copied to the heap, and the pointer is retargeted. A closed upvalue points to its own storage. The transition happens at scope exit, which is why the compiler must know which registers are captured: it emits a close instruction at the point where the scope ends, naming the first captured register.

This is the same problem that closure conversion solves in compiled languages, with the same three options: copy the value into the closure at creation time, box it on the heap and share the box, or keep a pointer into the frame and fix it up when the frame dies. Lua chooses the third and pays the fixup.

What the register design costs elsewhere

The verifier story is weaker than the stack machine’s. A stack VM’s operand types are implicit in the stack order, so a verifier can reconstruct them from a single walk. A register VM’s instruction says which register to use but not what type is in it, so a verifier needs a type per register at every program point, and merging types at control-flow joins is a dataflow problem rather than a compositional check. Lua’s reference implementation does not verify at all: it trusts the bytecode it produced, and the bytecode is not designed as an interchange format for untrusted input. Systems that do accept untrusted register bytecode need a separate verifier and a type discipline the encoding does not carry.

Code generation is harder in the other direction. Because a register instruction can name any of the operands, the compiler must decide which values get registers and when to reuse them, and the single-pass scheme Lua uses is a deliberate simplification that trades code quality for compile speed. A compiler that wanted optimal register usage would need liveness analysis over the whole function, and the resulting improvement is bounded by the fact that most temporaries are already short-lived.

The debugger’s view also degrades. A register number is not a source name, so the implementation must keep a table mapping registers to variable names and to the instruction ranges where each mapping holds. Lua’s stripped chunks discard this; the unstripped ones carry it as debug information, and the debug library exposes it through the local-variable introspection functions. The stack VM’s equivalent table maps stack slots, which are even less stable, since the depth at a given point depends on the instruction.

Finally, the two designs differ in how they fail. A stack VM that runs out of operand stack space has a bug in the compiler or the verifier, because the maximum depth was static. A register VM that runs out of registers has a compiler that failed to fit the program, and the failure mode is a compile-time diagnostic rather than a runtime fault, unless the implementation chose to grow the window dynamically. Lua’s maxstacksize is a hard bound; a function whose needs exceed it cannot be compiled, which is why the compiler’s register allocation heuristics matter for what source programs are accepted at all.