Project 1: A Register VM

Take the measurement ADR-002 promised.

Port the compiler and the VM to a register machine, run both on the same corpus, and find out what the stack machine actually cost you — on your workload, on your machine, with your dispatch loop.

Effort: a long weekend. Value: it will change how you read every VM you encounter afterwards.

What You Build

A second backend, alongside the tree walker and the stack VM:

#![allow(unused)]
fn main() {
// A register instruction addresses its operands explicitly.
pub enum ROp {
    Move   { dst: u8, src: u8 },
    LoadK  { dst: u8, k: u16 },
    LoadI  { dst: u8, n: i32 },
    Add    { dst: u8, a: u8, b: u8 },      // R[dst] = R[a] + R[b]
    Lt     { dst: u8, a: u8, b: u8 },
    GetField { dst: u8, obj: u8, k: u16 },
    Call   { func: u8, argc: u8, nres: u8 },   // args are in R[func+1 ..]
    Return { first: u8, count: u8 },
    Jump   { target: u32 },
    // ...
}
}

And the part that is actually new work: a register allocator.

#![allow(unused)]
fn main() {
/// Lua's `freereg` is a watermark that moves like a stack pointer. Expressions
/// allocate at the top and release when consumed. Locals hold their registers
/// for their whole scope. This is about as simple as register allocation gets,
/// and it is still a chapter of invariants.
struct RegAlloc { freereg: u8, nactive: u8, max: u8 }
}

The Three Places It Gets Hard

1. compile_expr gains a destination. In the stack machine it left one value on top. Now it must answer "where do you want the result?", which propagates through every expression form and is the single largest diff.
2. Register reuse must be correct, not just tidy. Freeing a register still holding a live temporary produces code that runs and computes the wrong thing — the asymmetry the stack-vs-register chapter warned about.
3. Multiple returns and varargs. The stack machine let the stack top be the count. A register machine needs an explicit "results start at R[k]" convention, and Lua's LUA_MULTRET handling in luaD_poscall is worth reading before you write yours.

The Measurement

cargo bench -- --baseline v0.1

The instruction-count row is the one to trust, because it is exact and machine-independent. The published direction is: substantially fewer executed instructions, somewhat larger bytecode, and a net speedup that depends on your dispatch technique and your CPU.

Compute the upper bound first, before you build anything. From Lab 27's opcode profile, count how many executed instructions are pure operand shuffling (GET_LOCAL/SET_LOCAL feeding an operator). That fraction is the register machine's ceiling on your workload — and if it is 15%, you now know the answer before spending the weekend.

Deliverables

• A register instruction set, documented in the same shape as the opcode reference.
• A register allocator with a watermark and an invariant test (no live register is reused).
• The whole corpus compiles, validates, and runs.
• The differential test runs three backends and all three agree — and the harness needed no changes, because Lab 8 built it that way.
• The measurement table, including the predicted upper bound and how close you got.
• ADR-015, superseding ADR-002 or confirming it. Confirming it is a fine outcome and it is now backed by a number.
• An honest paragraph: was the compiler complexity worth the speedup?

Where to Read

git clone https://github.com/lua/lua && cd lua
rg -n 'freereg|luaK_reserveregs|luaK_exp2nextreg|luaK_exp2anyreg' lcode.c
rg -n 'OP_MOVE|OP_ADD|iABC' lopcodes.h lvm.c

• Lua's lcode.c — freereg and the exp2* family are the allocator, in about 200 lines. This is the primary source and it is readable.
• The Implementation of Lua 5.0, §7 — the rationale from the people who made this exact switch, with their measurements.
• Shi, Casey, Ertl & Gregg, Virtual Machine Showdown: Stack Versus Registers (VEE 2005) — a controlled comparison. Get the paper for the figures rather than trusting a remembered percentage.
• Dalvik's bytecode reference, for a second register design with different constraints (ARM, memory).

Validation / Self-check

1. What does compile_expr gain, and why is that the largest part of the diff?
2. What is a register allocator's watermark, and what invariant must hold?
3. What is the failure mode of freeing a live register, and why is it worse than a stack machine's equivalent bug?
4. How did you compute the upper bound before building, and how close was the result?
5. Which row of the measurement table is exact, and why?
6. Did the differential harness need changes? What does that say about Lab 8?
7. Was it worth it? Answer with your numbers, not with a preference.

Next: Project 2 — NaN Boxing.