Register-Based VMs and VM Design Trade-offs

A stack machine works like a calculator with a pile of numbers: push, push, add.

Learning Objectives

Compare stack and register machines: virtual registers, three-address instructions, instruction count versus complexity, operand encoding and size, dispatch overhead.

Explain register allocation in a VM compiler, temporaries and liveness, basic blocks, control-flow graphs, SSA and lowering, and translation between stack and register forms.

Weigh implementation complexity, optimisation potential and benchmark fairness when designing a VM.

Plain-Language Explanation

A stack machine works like a calculator with a pile of numbers: push, push, add. A register machine works like a calculator with numbered memory slots: "add slot 1 and slot 2 into slot 0". The register version needs fewer instructions, but each instruction is bigger and the compiler must decide which values go in which slots.

Precise Technical Explanation

Stack machine versus register machine Stack: operands implicit at the top of the stack; short instructions; more of them (every operand is moved by a push). Register: operands named explicitly; longer instructions; fewer of them; values stay in registers across instructions.

Numbered slots in the current frame (r0, r1…), usually unlimited per function up to an encoding limit (Lua: 250; Dalvik: 65,536), stored in memory — not CPU registers.

op dest, src1, src2 — e.g. ADD r0, r1, r2. Two-address forms (ADD r0, r1 meaning r0 += r1) and accumulator machines (V8's Ignition: an implicit accumulator plus registers) are intermediate designs.

Instruction count versus instruction complexity (a + b) * c is 5 stack instructions or 3 register instructions when a, b, c are already in registers. Each dispatch costs time; each decoded operand costs time too.

Operand encoding and bytecode size Register instructions carry 2–3 operands; fixed 32-bit encodings (Lua) decode fast but waste space; variable encodings save space.

Fewer instructions mean fewer dispatches, the main reason register VMs are often faster in interpreters (Shi et al. measured roughly a 47% reduction in executed instructions for a register version of the JVM, with a modest increase in code size).

Register allocation in a VM compiler The compiler maps locals and temporaries to virtual registers. Simple schemes: one register per local plus a stack-like allocator for temporaries (Lua's freereg); reuse a register once its value is dead.

Temporary values and liveness A value is live from its definition to its last use; registers holding dead values can be reused. MiniLang's comparison compiler reuses the left operand's register for the result.

Maximal straight-line instruction sequences with one entry (the first instruction, a leader) and one exit (the last instruction). Leaders: the first instruction, every jump target, and every instruction after a jump.

Nodes are basic blocks; edges are possible transfers (fall-through and jumps). Optimisers and JITs work on CFGs.

SSA form and lowering Converting register code to SSA renames every assignment uniquely and inserts φ-functions at merges, making data flow explicit for optimisation.

Simulate the stack at compile time: each push allocates a register, each pop names one — Dalvik's dx tool converted JVM stack bytecode to register bytecode this way.

Emit loads of source registers, the operation, and a store to the destination — easy, but loses the instruction-count advantage.

Interpreter implementation complexity Register VMs need operand decoding for every instruction and a register allocator in the compiler; stack VMs have a simpler compiler.

Examples of stack-based and register-based instruction formats

These formats are illustrative and not the exact encoding of a named production VM.

Benchmark design and fairness Compare VMs that differ only in instruction format (same value representation, same dispatch technique, same compiler optimisations), count instructions and measure time separately, and use realistic programs.

Design trade-offs for a custom VM Choose a stack VM for a simple compiler, small code and easy verification (WebAssembly, JVM); choose registers for interpreter speed (Lua, Dalvik); choose an accumulator design for a balance (V8's Ignition).

; Stack-style
LOAD_CONST 4
LOAD_CONST 5
MUL
STORE_LOCAL 0

; Register-style, illustrative
MUL r0, r1, r2     ; r0 = r1 * r2

Why It Matters in Real Systems

Android moved from JVM stack bytecode to Dalvik's register bytecode for interpreter speed on phones; V8 chose an accumulator-register design for Ignition; WebAssembly chose a stack machine for compact, quickly validated code.

Key Terms

Numbered frame slot named by instructions op dest, a, b Range during which a value may still be used

Straight-line code with one entry and one exit Graph of basic blocks and control transfers

Syntax or Instruction Format

Stack form (MiniLang-style): CONST k, LOAD name, ADD. Register form (illustrative): LOADK r, k, MOVE r, name, ADD rd, ra, rb.

Complete Example

The course's expression compiler generates both forms from the same AST and evaluates them (Node.js 24, MiniLang module):

Output (instruction counts are for this toy compiler, not universal performance evidence):

A real production register machine: V8's Ignition bytecode for (a + b) * c (Node.js 24.18 / V8; printed with --print-bytecode, memory addresses removed — this listing is engine- and version-specific):

Basic blocks found in real MiniLang bytecode with the leader algorithm (Node.js 24):

import { exprForms } from "file:///D:/Projects/EngineerHub/src/cs/tracks/runtimes/minilang/minilang.ts";

const env = { a: 2, b: 3, c: 4, d: 5 };
for (const src of ["(a + b) * c", "a * b + c * d", "a - b - c - d", "-(a + b) * (c - d) / 2"]) {
  const f = exprForms(src, env);
  console.log(`${src}  =  ${f.value}`);
  console.log(`  stack (${f.stack.length} instructions, max depth ${f.stackMax}): ${f.stack.join("; ")}`);
  const reg = f.register.filter((x) => !x.startsWith(";"));
  console.log(`  register (${reg.length} instructions, ${f.registersUsed} registers): ${reg.join("; ")}`);
}

(a + b) * c  =  20
  stack (5 instructions, max depth 2): LOAD a; LOAD b; ADD; LOAD c; MUL
  register (5 instructions, 2 registers): MOVE r0, a; MOVE r1, b; ADD r0, r0, r1; MOVE r1, c; MUL r0, r0, r1
a * b + c * d  =  26
  stack (7 instructions, max depth 3): LOAD a; LOAD b; MUL; LOAD c; LOAD d; MUL; ADD
  register (7 instructions, 3 registers): MOVE r0, a; MOVE r1, b; MUL r0, r0, r1; MOVE r1, c; MOVE r2, d; MUL r1, r1, r2; ADD r0, r0, r1
a - b - c - d  =  -10
  stack (7 instructions, max depth 2): LOAD a; LOAD b; SUB; LOAD c; SUB; LOAD d; SUB
  register (7 instructions, 2 registers): MOVE r0, a; MOVE r1, b; SUB r0, r0, r1; MOVE r1, c; SUB r0, r0, r1; MOVE r1, d; SUB r0, r0, r1
-(a + b) * (c - d) / 2  =  2.5
  stack (10 instructions, max depth 3): LOAD a; LOAD b; ADD; NEG; LOAD c; LOAD d; SUB; MUL; CONST 2; DIV
  register (10 instructions, 3 registers): MOVE r0, a; MOVE r1, b; ADD r0, r0, r1; NEG r0, r0; MOVE r1, c; MOVE r2, d; SUB r1, r1, r2; MUL r0, r0, r1; LOADK r1, 2; DIV r0, r0, r1

const { execFileSync } = require("node:child_process");
const { writeFileSync } = require("node:fs");

writeFileSync("calc_child.js", "function calc(a, b, c) { return (a + b) * c; }\nconsole.log(calc(2, 3, 4));\n");
const out = execFileSync(process.execPath, ["--print-bytecode", "--print-bytecode-filter=calc", "calc_child.js"], { encoding: "utf8" });
for (const line of out.split(/\r?\n/)) {
  if (/^\[generated|^Parameter count|^Register count/.test(line)) console.log(line.replace(/ \(0x[0-9a-f]+ .*\)/, ""));
  const m = line.match(/@\s+(\d+) : ([0-9a-f ]+?)\s{2,}(.+)$/);
  if (m) console.log(`  @${m[1].padStart(2)}  ${m[2].padEnd(10)}  ${m[3]}`);
  if (/^\d+$/.test(line.trim())) console.log("program output:", line.trim());
}

[generated bytecode for function: calc]
Parameter count 4
Register count 1
  @ 0  0b 04       Ldar a1
  @ 2  3f 03 01    Add a0, [1]
  @ 5  ce          Star0
  @ 6  0b 05       Ldar a2
  @ 8  41 f9 00    Mul r0, [0]
  @11  b3          Return
program output: 20

import { compile, disassemble } from "file:///D:/Projects/EngineerHub/src/cs/tracks/runtimes/minilang/minilang.ts";

const fn = compile("let n = 3; while (n > 0) { if (n == 2) print(\"two\"); n = n - 1; } print(\"done\");").script;
const ins = disassemble(fn);
const leaders = new Set([0]);
ins.forEach((d, i) => {
  if (d.target !== null) { leaders.add(d.target); if (ins[i + 1]) leaders.add(ins[i + 1].offset); }
});
let block = -1;
for (const d of ins) {
  if (leaders.has(d.offset)) console.log(`B${++block} (leader @${d.offset})`);
  console.log(`   ${String(d.offset).padStart(2, "0")}  ${d.op}${d.operands ? " " + d.operands : ""}${d.target !== null ? "  → " + d.target : ""}`);
}

B0 (leader @0)
   00  CONSTANT 0
   02  DEFINE_GLOBAL 0
B1 (leader @4)
   04  GET_GLOBAL 0
   06  CONSTANT 1
   08  GREATER
   09  JUMP_IF_FALSE 28  → 40
B2 (leader @12)
   12  POP
   13  GET_GLOBAL 0
   15  CONSTANT 2
   17  EQUAL
   18  JUMP_IF_FALSE 7  → 28
B3 (leader @21)
   21  POP
   22  CONSTANT 3
   24  PRINT
   25  JUMP 1  → 29
B4 (leader @28)
   28  POP
B5 (leader @29)
   29  GET_GLOBAL 0
   31  CONSTANT 4
   33  SUBTRACT
   34  SET_GLOBAL 0
   36  POP
   37  LOOP 36  → 4
B6 (leader @40)
   40  POP
   41  CONSTANT 5
   43  PRINT
   44  HALT

Line-by-Line Explanation

exprForms builds both forms from one AST. The stack form pushes every operand; the register form reuses r0 for the left operand and result, and frees temporaries after use.

Ignition: Ldar loads a register into the accumulator, Add a0, [1] adds argument register a0 to the accumulator (the [1] is a feedback-vector slot used for type feedback — Module 16), Star0 stores the accumulator into r0, Mul r0, [0] multiplies. V8 evaluates a + b as acc = b; acc = a + acc, preserving left-to-right semantics.

Leaders: offset 0, each jump target and each instruction after a jump; each leader starts a basic block.

Expected Output

As shown; the V8 listing is specific to this Node.js/V8 version.

Step-by-Step Runtime Behavior

(a + b) * c on the register form: r0 ← a (2), r1 ← b (3), r0 ← r0 + r1 (5), r1 ← c (4), r0 ← r0 × r1 (20).

Common Misconceptions

"Virtual registers are CPU registers." They are memory slots in the frame (a JIT may later map them to CPU registers).

"Register VMs are always faster." Fewer dispatches but bigger instructions; the net effect depends on the implementation.

"V8 bytecode is stable." It changes between V8 versions.

Common Bugs and Failure Modes

Reusing a register whose value is still live; operand-order mistakes in three-address code; register limits exceeded in large functions without a spill strategy.

Corrected or Safer Patterns

Track liveness; allocate temporaries stack-like (last allocated, first freed); verify register bounds like stack bounds.

Debugging and Inspection Techniques

Dump both forms; luac -l (Lua), node --print-bytecode (V8), dexdump -d (Android) show register bytecode.

Performance Considerations

Register forms reduce dispatches and memory traffic for operands; stack forms are smaller and simpler to validate and compile; JITs erase most differences for hot code.

Security Considerations

Portability and Version Caveats

Ignition's instruction set, register naming and feedback slots are V8-version specific.

Real-World Use Cases

Lua, Dalvik/ART, V8 Ignition, Parrot, Erlang BEAM (register machine) — versus JVM, CLR, CPython and WebAssembly (stack machines).

Best Practices

Choose by your constraints (compiler simplicity, code size, interpreter speed), and benchmark fairly.

Exercises

E1 · Beginner. Write stack and register code for a * b + c.

Answer: Stack: LOAD a; LOAD b; MUL; LOAD c; ADD (5). Register: MOVE r0, a; MOVE r1, b; MUL r0, r0, r1; MOVE r1, c; ADD r0, r0, r1 (5 here because operands are loaded; with a, b, c already in registers: MUL r3, r0, r1; ADD r3, r3, r2 — 2).

E2 · Intermediate. Identify the leaders in 0 CONST; 2 JUMP_IF_FALSE → 9; 5 PRINT; 6 JUMP → 10; 9 PRINT; 10 HALT.

Answer: 0 (first), 5 (after a jump), 9 (a target and after a jump), 10 (a target).

E3 · Advanced challenge. Sketch stack-to-register translation for LOAD a; LOAD b; ADD; LOAD c; MUL.

Answer: Keep a compile-time stack of register names: LOAD a → push r_a; LOAD b → push r_b; ADD → pop r_b, r_a, emit ADD t0, r_a, r_b, push t0; LOAD c → push r_c; MUL → pop r_c, t0, emit MUL t0, t0, r_c — two register instructions.

Quiz

? Why do register VMs often execute fewer instructions than stack VMs?
+ Operands are named directly, so values are not pushed and popped around each operation. :: Fewer dispatches.
- They have no constant pool. :: They do.
- They skip type checks. :: Unrelated.
- They run on real CPU registers. :: Virtual registers are memory slots.

? What is a basic block?
+ A straight-line sequence with one entry and one exit. :: Jumps only enter at the top and leave at the bottom.
- A block statement in source code. :: Unrelated to `{ }`.
- A memory page. :: No.
- A function. :: Functions contain many blocks.

? Which designs use stack-based bytecode? (select all that apply)
+ JVM :: Operand stack.
+ WebAssembly :: Structured stack machine.
- Lua 5 :: Register-based.
+ CPython :: Stack-based.

Summary and Key Takeaways

Stack VMs have compact code and simple compilers; register VMs execute fewer, larger instructions and need register allocation. Basic blocks and CFGs organise code for optimisation in either design; JITs convert both into SSA.