VMimplementation

Register-Based Virtual Machines

Give the virtual machine numbered registers instead of an operand stack and `ADD r3, r1, r2` replaces three instructions with one — at the cost of a bigger instruction and a code generator that now has to decide which register everything lives in.

The question

What changes if my virtual machine has registers instead of an operand stack?

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

A program is still a linear instruction array, but the machine's data state is a flat array of numbered virtual registers per call frame rather than a stack plus slots. Operand *location* is now encoded in the instruction, which means an instruction can name three places at once — and the representation exists to answer "can one instruction do a whole three-address operation" with yes.

What this phase may assume or do

The generator may assign any register to any value provided that no register holds two values whose live ranges overlap, that every read is dominated by a write to the same register, and that the frame declares enough registers for the maximum simultaneously live count. Reusing a register whose previous value is still live is not slower code, it is wrong code — the same precondition that governs [[register-allocation]] in a native backend, applied to a machine with a much larger register file.

Key points

  • A register VM encodes operand locations in the instruction, so one instruction can express a full three-address operation.
  • Fewer instructions per unit of work means fewer dispatches, which is where the runtime win comes from.
  • Each instruction is larger, so the fetch and decode cost per instruction rises and part of the win is given back.
  • VM registers are frame slots, not hardware registers, and there are usually enough of them that allocation is bookkeeping rather than graph colouring.
  • The complexity moves from the interpreter to the compiler: the code generator now makes allocation decisions and must size the frame.
  • Lua 5 and Dalvik are the canonical examples, and both changed their instruction formats between versions — the format is an implementation detail there, not a contract.

The instruction names its operands

implementationThe ADD 2 0 1 spelling is Lua 5.x as printed by luac -l. The exact operand layout is not stable across Lua versions: 5.4 reworked the instruction format and introduced separate opcodes such as ADDK and ADDI for constant and immediate operands, so a 5.3 listing and a 5.4 listing of the same source differ in both opcode names and operand fields. Dalvik spells the same operation add-int v0, v1, v2, and ART compiles it ahead of time rather than interpreting it in the common case.

A register VM instruction carries operand fields. ADD r3, r1, r2 says: read registers 1 and 2, add, write register 3. It is the three-address form from [[three-address-code]] executed directly, with the virtual registers of the IR surviving all the way into the executable artifact rather than being flattened onto a stack.

The immediate effect is arithmetic on instruction counts. Our stack machine spends LOAD; LOAD; ADD; STORE — four dispatches — on c = a + b. A register machine spends one. Nothing about the addition changed; what changed is that the operand positions moved from the convention into the encoding.

The same statement c = a + b on both machines
Stack machine (ours, real output)
LOAD 0 ; a
LOAD 1 ; b
ADD
STORE 2 ; c
Register machine (Lua-style)
▸ADD 2 0 1   ; R[2] := R[0] + R[1]

Read it asFour instructions become one, and the one is wider. Read it as a compression question: the stack version encodes operand positions in *time* — the order the pushes happened — and the register version encodes them in *space*, in the operand fields. Neither is free; they simply spend different budgets.

Registers here are not hardware registers

The word "register" is doing double duty and the two meanings differ in the one dimension that matters: quantity. A CPU has sixteen or thirty-two architectural general-purpose registers, which is why [[spilling]] exists. A register VM has as many as the frame declares — Lua allows up to 255 per function, Dalvik encodes 4, 8 or 16 bit register numbers depending on the instruction form.

That abundance changes the allocation problem from "colour a graph under severe pressure" to "assign stack-frame slot numbers and try to reuse them". Lua's compiler treats registers as a stack of activation slots and frees them by moving a high-water mark back down; it is closer to bump allocation than to graph colouring. The hard version of the problem reappears only when the VM has a JIT and those virtual registers must be mapped onto real ones.

  • A VM register is a slot in the frame's value array. Access is an array index, not a hardware register read.
  • Register count per function is declared in the function header, so the frame can be allocated in one go on entry.
  • Because there are many, most values never need to be spilled or reloaded — the traffic that dominates a stack machine's trace simply does not occur.
  • The operand fields bound the register number. Dalvik has separate wide forms (move/16, move/from16) precisely because 4 bits does not always reach.
  • Instruction *size* becomes variable and encoding becomes a real design problem — the thing [[bytecode]] notes we get to skip entirely.

What the code generator has to do now

On a stack machine the generator is a post-order walk with no decisions. On a register machine it must choose a register for every intermediate value, know when that register becomes free, and keep the maximum count so the frame can be sized. For straight-line expressions this is easy — allocate upward, release on consume. Across branches and loops it is genuinely a [[live-ranges]] problem, because a value defined in one block and used in another must survive every path between them.

This is why the choice is not "register VMs are better". It is a transfer of complexity from the interpreter loop to the compiler, paid once per compilation instead of once per execution. If your bytecode is generated rarely and executed constantly, that is a good trade. If it is generated constantly — a REPL, a template engine, a configuration language evaluated once — it is a bad one.

Reusing a register after its value is dead
Before
ADD 2 0 1    ; R2 := R0 + R1
MUL 3 2 2    ; R3 := R2 * R2
PRINT 3
After
ADD 2 0 1    ; R2 := R0 + R1
MUL 2 2 2    ; R2 := R2 * R2   (R3 eliminated)
PRINT 2
Legal only when

Only if the value in R2 has no use after the multiply — that is, the multiply is the last read of R2 on every path from this point — and no other live value has been assigned to R2 in the meantime. Under that condition the frame needs one fewer register and no observable behavior changes.

Illegal when

If any later instruction, on any path including a back edge, reads R2 expecting the sum rather than the square. A loop body that computes t = a + b at the top and reads t again after the multiply is exactly this case: the rewrite is invisible on the first iteration and produces wrong values on every one after it.

Where the two designs actually stand

typicalComparisons between the two are usually made by rewriting one specific interpreter and measuring it, which controls for everything except the thing under test but generalizes badly: the result depends on the benchmark mix, on how aggressively the original stack interpreter was tuned, and on the host CPU's indirect-branch predictor. Treat "register VMs run fewer instructions" as reliable and any specific speedup percentage as belonging to the experiment it came from.

The honest summary is that register VMs execute fewer instructions and each instruction does more work and costs more to decode. Published measurements comparing a register rewrite of a stack interpreter against its original have reported meaningful reductions in executed instructions with a smaller reduction in running time, because part of the win is eaten by larger fetches and more decoding. The direction is consistent; the magnitude is workload-dependent and not a constant you can quote.

Which is to say: choose on the other axes. Portability, verifiability and ease of being targeted favour the stack machine. Interpreter throughput and a closer match to the IR you already have favour the register machine. Both camps contain enormously successful systems, which is the strongest available evidence that neither dominates.

How it works

The steps, in the order the compiler takes them.

  • The function header declares how many registers the frame needs; the VM allocates that many slots when the frame is pushed.
  • Arguments arrive in the lowest-numbered registers, so a call can copy them positionally without knowing the callee's body.
  • The code generator allocates registers upward as it walks an expression and releases them as their values are consumed, tracking a high-water mark for the frame size.
  • Each instruction decodes into an opcode and two or three operand fields, reads the named registers, computes, and writes the destination register.
  • Control flow still assigns to the instruction pointer; the register file is unaffected by a branch, which is why no depth-matching rule is needed at merges.
  • A call writes the callee's result into a register the caller named, so no stack juggling is required to move a return value into place.

How it breaks

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

  • A register is reused while its previous value is still live, and a variable silently takes on another variable's value partway through a function.
  • The declared register count is too small for a path the generator did not think about, and the VM reads past the frame — either a crash inside the interpreter with no user-level context, or, worse, a read of an adjacent frame.
  • An operand field overflows its bit width for a function with many locals, and the encoder silently truncates the register number, producing a program that reads the wrong register only in large functions.
  • A destination register aliases a source register in an instruction whose implementation writes the destination before reading the second source, so SUB 0 0 1 works and SUB 0 1 0 does not.
  • Bytecode produced by one version of the compiler is loaded by a VM with a different instruction format, and the operand fields are reinterpreted rather than rejected.

When it helps

  • Long-running interpreted workloads where dispatch is a measurable share of the time and the bytecode is compiled once.
  • An implementation whose IR is already three-address, since the mapping is almost the identity and no stack flattening is needed.
  • Embedded scripting where the interpreter loop must be small and fast and the compiler can be as clever as it likes.
  • A VM that will later gain a JIT: virtual registers are much closer to what a native backend wants than a stack is.

When it hurts

  • Bytecode that is generated far more often than it is executed — the extra generator work is never repaid.
  • A format meant to be targeted by other people's compilers, where the allocation burden is imposed on every producer.
  • Verification of untrusted code, which is harder than for a stack machine: register liveness and definite assignment must be proved rather than read off a depth counter.

What it costs

Every one of these is paid by something.

  • Named operands buy fewer executed instructions and pay in instruction width and decode work, so the measured win is smaller than the instruction-count win.
  • Moving allocation into the compiler buys a faster interpreter and pays in compile time and in code-generator complexity — a live-range analysis where a stack machine needed none.
  • A large register file buys the disappearance of spilling and pays in frame size: every frame allocates the maximum the function might need, on every call, whether or not the path taken uses them.
  • A close match to three-address IR buys an easy path to a JIT later and pays now, because the format is no longer trivially verifiable by a linear depth check.

What else you could do

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

  • A stack machine, which removes allocation from the generator entirely and pays for it in dispatches: [[stack-based-vm]].
  • A hybrid: a stack bytecode as the portable interface with an internal register form built at load time. This is what several production VMs effectively do, and it lets the shipped artifact stay verifiable while the executed form stays fast.
  • Skip the interpreter and compile ahead of time to native code, which is the route Android took when ART replaced Dalvik's interpretation as the common case: [[aot-compilation]].
  • Keep the stack machine and attack dispatch instead, with superinstructions and threading: [[interpreter-performance]].

See it for yourself

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

  • luac -l -l file.lua prints Lua's register instructions along with the register count and the constant table; the second -l adds the debug information.
  • For Android, dexdump -d classes.dex prints Dalvik instructions in add-int v0, v1, v2 form, with the register count per method in the header.
  • Compare directly: write the same three-line function in Lua and Python, then read luac -l beside python -m dis and count instructions for the same expression.
  • Our VM is a stack machine, so /compilers/vm shows the other side of this comparison — the LOAD/LOAD/ADD/STORE sequence a register machine collapses.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Register VMs use the CPU's registers." They use an array of frame slots. Mapping those onto hardware registers is a JIT's job and does not happen in the interpreter.
  • "Fewer instructions means proportionally faster." Part of the saving is returned as larger fetches and more decoding. The instruction-count reduction is the upper bound on the speedup, not the speedup.
  • "Register machines are the modern design and stack machines are legacy." WebAssembly is a stack machine and was designed in the last decade. The choice tracks what the format is *for*, not when it was made.
  • "Since there are hundreds of registers, allocation is free." It is cheap, not free, and it still has to be correct: a reused register whose value is live is a wrong-answer bug with no diagnostic.

Misconceptions

The claim, and what is actually true.

A register VM needs no register allocator because it has plenty of registers.
It needs assignment and liveness, just not under pressure. The correctness requirement — never reuse a register whose value is still live — is identical to a native allocator's; only the spilling disappears.
The stack machine wastes memory that the register machine saves.
Usually the reverse. A register frame is sized for the function's maximum simultaneous liveness and allocated on every call; a stack machine's operand area is typically shallow.

Go deeper

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

overview

Instead of pushing values onto a stack and letting instructions take whatever is on top, each instruction says which numbered slots to read and which to write. ADD r3, r1, r2 does in one step what a stack machine does in four. The instruction is bigger, and something now has to decide which slot each value belongs in.

practical

If you are writing a register VM by hand, the generator pattern is: keep a counter of the next free register, allocate upward for expression temporaries, reset the counter after each statement, and record the maximum reached as the frame size. Named locals get fixed low registers below the temporary area. That gets you almost all of the way; only values that cross a branch or a loop back edge need real liveness reasoning, and those are exactly the ones that produce the silent wrong-value bugs when you get them wrong.

advanced

The subtle argument for register bytecode is not the instruction count — it is what the format preserves. A stack machine destroys the dataflow graph and a JIT has to rebuild it by abstract-interpreting the stack effects before it can do anything useful. A register bytecode hands it over intact, which shortens the path from bytecode to a compilable IR. That is a strong reason to choose registers if a JIT is on the roadmap, and no reason at all if the format's job is to be verified and interpreted on hardware you do not control.

How much this depends on

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

implementationLua 5.x is register-based, and its instruction format changed between 5.1, 5.3 and 5.4 — 5.4 added constant- and immediate-operand arithmetic opcodes. Dalvik was register-based and interpreted; Android moved to ART, which compiles ahead of time and at install or first-run time. Statements about either are true of a named version and should be re-checked against the one in front of you.
typicalPublished register-versus-stack comparisons rewrite one interpreter and measure it. They consistently show fewer executed instructions and a smaller reduction in time, with the gap depending on benchmark mix and on how well the host predicts the interpreter's indirect branches. Do not carry a specific percentage from one such study to another VM.
simplifiedOur AtlasLang VM is a stack machine, so every register listing in this lesson is quoted from Lua or Dalvik rather than produced by our own toolchain. Nothing here can be reproduced at /compilers/vm; the stack side of every comparison can.

If you were asked this in an interview

  • Rewrite LOAD a; LOAD b; ADD; STORE c for a register machine and tell me what got bigger.
  • A register VM has 255 registers per frame. Does it still need a register allocator? Defend your answer.
  • Which design would you pick for a bytecode other people's compilers will target, and why is that a different question from which one runs faster?

Connections

Computer Architectureregistersinstruction-decodeinstruction-set-architecture
Domains that do not exist yet
  • Programming Languages & Runtime Internals — Frame allocation and the cost of sizing every activation record for its worst case
    A register VM allocates the maximum register count on every call, so frame layout becomes an allocation-rate question the runtime owns. The compiler only decides the number; what that number costs in practice depends on how the runtime allocates and reclaims frames.