Bytecode compilation

Deep dive

How it works

In: parsed AST (see recursive-descent parsing, Pratt parsing) · Out: Vec<u8> code, constant pool, local-slot count, line table · State: the code buffer, the pool, the scope stack · Cost: O(n) time, one pass

1. Expressions: compile the children, then emit the operator (postfix). a + b becomes LOAD a; LOAD b; ADD.
2. Literals: deduplicated constant pool entry, CONST index.
3. Locals: a scope stack maps names to slots (name resolution, folded in); leaving a block truncates it so slots are reused. Compile the initializer before the name is visible.
4. if: compile the condition, emit JMPF <hole>, compile the then-branch, emit JMP <hole>, patch the first hole to here, compile the else-branch, patch the second hole.
5. while: remember top, compile the condition, JMPF <hole>, compile the body, JMP top (backward, target known), patch the exit hole.
6. Record (offset, line) when the line changes; finish with RET and the max slot count.

Stack vs register. A stack machine's instructions name no operands (ADD pops two, pushes one); a register machine names them (ADD dst a b). Lua 5.x is register-based, 32-bit instructions with a 7-bit opcode and 8-bit A/B/C fields (lopcodes.h); SQLite's VDBE is too (opcode.html). The JVM, EVM and CPython are stack machines (JVMS ch. 6, Solidity docs, dis). Register code needs register allocation in the compiler.

Encoding. Fixed width (Lua 4 bytes, CPython 3.6+ 2 bytes, BPF 8 bytes) decodes in one load; variable width (JVM) is denser. The JVM goto offset is signed 16-bit, goto_w 32-bit.

Backpatching. Lua chains pending jumps through their offset field (NO_JUMP ends the list, lcode.c), so one target serves many breaks.

Line table. Keep it out of the instruction stream: CPython co_lines() (PEP 626), JVM LineNumberTable (JVMS 4.7.12). Binary-search the offset on error; the happy path pays nothing.

Peephole and superinstructions. Scan a small window and rewrite (CONST 0; ADD removed, LOAD x; LOAD y fused); run it per basic block, since a jump into a pattern blocks the rewrite (peephole optimization, control-flow graph). CPython 3.13+ has LOAD_FAST_LOAD_FAST (dis): one dispatch instead of two.

Code

Compiles a small AST to Vec<u8> (u16 operands, absolute jump targets) and runs it; compiled and run, asserts pass.

enum Node {
    Num(i64), Var(&'static str), Add(Box<Node>, Box<Node>), Lt(Box<Node>, Box<Node>),
    Let(&'static str, Box<Node>), Assign(&'static str, Box<Node>),
    If(Box<Node>, Vec<Node>, Vec<Node>), While(Box<Node>, Vec<Node>),
}
use Node::*;
const CONST: u8 = 0; const LOAD: u8 = 1; const STORE: u8 = 2; const ADD: u8 = 3;
const LT: u8 = 4; const JMP: u8 = 5; const JMPF: u8 = 6; const RET: u8 = 7;
const HOLE: u16 = 0xFFFF; // jump placeholder, never a valid target
fn has_operand(op: u8) -> bool { matches!(op, CONST | LOAD | STORE | JMP | JMPF) }
#[derive(Default)]
struct Compiler {
    code: Vec<u8>, consts: Vec<i64>, nslots: u16,
    scope: Vec<(&'static str, u16)>, // innermost last; slot = depth at declaration
}
impl Compiler {
    fn emit(&mut self, op: u8, arg: Option<u16>) -> usize {
        let at = self.code.len(); // offset of the instruction: the patch site
        self.code.push(op);
        if let Some(a) = arg { self.code.extend_from_slice(&a.to_le_bytes()); }
        at
    }
    fn patch(&mut self, at: usize) { // point the jump at the current end of code
        let t = self.code.len() as u16;
        self.code[at + 1..at + 3].copy_from_slice(&t.to_le_bytes());
    }
    fn slot(&self, name: &str) -> u16 { self.scope.iter().rev().find(|(n, _)| *n == name).expect("unbound").1 }
    fn expr(&mut self, n: &Node) {
        match n {
            Num(v) => {
                let i = self.consts.iter().position(|c| c == v).unwrap_or_else(|| { self.consts.push(*v); self.consts.len() - 1 });
                self.emit(CONST, Some(i as u16));
            }
            Var(s) => { let k = self.slot(s); self.emit(LOAD, Some(k)); }
            Add(a, b) | Lt(a, b) => {
                self.expr(a); self.expr(b); self.emit(if matches!(n, Add(..)) { ADD } else { LT }, None);
            }
            _ => unreachable!(),
        }
    }
    fn block(&mut self, body: &[Node]) {
        let depth = self.scope.len();
        for s in body { self.stmt(s); }
        self.scope.truncate(depth); // slots above `depth` are free again
    }
    fn stmt(&mut self, n: &Node) {
        match n {
            Let(name, init) => {
                self.expr(init); // compile init BEFORE the name is visible
                let k = self.scope.len() as u16;
                self.scope.push((name, k)); self.nslots = self.nslots.max(k + 1);
                self.emit(STORE, Some(k));
            }
            Assign(name, v) => { self.expr(v); let k = self.slot(name); self.emit(STORE, Some(k)); }
            If(c, t, e) => {
                self.expr(c);
                let to_else = self.emit(JMPF, Some(HOLE));
                self.block(t);
                let to_end = self.emit(JMP, Some(HOLE));
                self.patch(to_else); self.block(e); self.patch(to_end);
            }
            While(c, body) => {
                let top = self.code.len() as u16;
                self.expr(c);
                let exit = self.emit(JMPF, Some(HOLE));
                self.block(body);
                self.emit(JMP, Some(top)); // backward: target known
                self.patch(exit);
            }
            _ => unreachable!(),
        }
    }
}
fn run(code: &[u8], consts: &[i64], nslots: usize) -> i64 {
    let (mut pc, mut st, mut loc) = (0usize, Vec::new(), vec![0i64; nslots]);
    let arg = |pc: usize| u16::from_le_bytes([code[pc + 1], code[pc + 2]]) as usize;
    loop {
        let op = code[pc];
        let next = pc + if has_operand(op) { 3 } else { 1 };
        match op {
            CONST => st.push(consts[arg(pc)]),
            LOAD => st.push(loc[arg(pc)]),
            STORE => loc[arg(pc)] = st.pop().unwrap(),
            ADD | LT => {
                let (b, a) = (st.pop().unwrap(), st.pop().unwrap());
                st.push(if op == ADD { a + b } else { (a < b) as i64 })
            }
            JMP => { pc = arg(pc); continue }
            JMPF => { if st.pop().unwrap() == 0 { pc = arg(pc); continue } }
            RET => return st.pop().unwrap(),
            _ => unreachable!(),
        }
        pc = next;
    }
}
#[allow(dead_code)]
enum Instr { Const(u16), Load(u16), Store(u16), Add, Lt, Jmp(u16), JmpF(u16), Ret }
fn main() {
    let b = |n| Box::new(n);
    let lt_i_11 = || Lt(b(Var("i")), b(Num(11)));
    let prog = vec![
        Let("sum", b(Num(0))), Let("i", b(Num(1))),
        While(b(lt_i_11()), vec![
            If(b(lt_i_11()), vec![Assign("sum", b(Add(b(Var("sum")), b(Var("i")))))],
                             vec![Assign("sum", b(Num(0)))]),
            Assign("i", b(Add(b(Var("i")), b(Num(1))))),
        ]),
    ];
    let mut c = Compiler::default();
    for s in &prog { c.stmt(s); }
    c.expr(&Var("sum")); c.emit(RET, None);
    assert_eq!(run(&c.code, &c.consts, c.nslots as usize), 55);
    let (mut pc, mut n) = (0, 0); // walk instruction boundaries
    while pc < c.code.len() {
        let op = c.code[pc];
        if matches!(op, JMP | JMPF) { assert_ne!(c.code[pc + 1..pc + 3], HOLE.to_le_bytes()); }
        pc += if has_operand(op) { 3 } else { 1 }; n += 1;
    }
    let enum_bytes = n * std::mem::size_of::<Instr>();
    println!("{n} instrs, bytecode {} B, Vec<Instr> {enum_bytes} B", c.code.len());
    assert!(c.code.len() < enum_bytes);
}

Output: 26 instrs, bytecode 68 B, Vec<Instr> 104 B (Instr = 4 B). The program is sum over i in 1..=10 with a redundant if to exercise both jump kinds.

Complexity and constants

• Compile: O(n), one pass; a patch is a 2-byte write.
• Size: 3 B for operand ops, 1 B otherwise; the demo averages 2.6 B per instruction vs 4 B for the enum.
• Run: one dispatch per instruction; branch mispredicts in the dispatch dominate.
• u16 targets cap a function at 64 KiB; real VMs add a wide form (JVM goto_w).

Efficiency

• Cost: compile is linear with one Vec<u8>; run cost is dispatch bound. The demo program is 68 B.
• Levers:
  • Constant pool dedupe — smaller code and cache files — repeated literals.
  • Superinstructions — fewer dispatches (CPython, above) — hot op pairs.
  • Slot reuse across scopes — smaller frames — nested blocks.
  • Serialised cache — skips parse and compile — scripts loaded often.
  • Metering only on back-edges (instruction metering) — untrusted code.
• Naive → standard → state of the art: tree walk · pointer chase per node → stack bytecode, fixed width · one dispatch per op → register bytecode with superinstructions, then a tiered JIT · fewer dispatches, then no dispatch.

Caching. CPython writes __pycache__/*.pyc: a magic number versioning the bytecode, flags, then source mtime and size or a SipHash of the source (PEP 3147, PEP 552). V8 embedders can persist compile results via kProduceCodeCache/kConsumeCodeCache (V8 blog). Key caches on the compiler version.

Implementation notes

• Emit with to_le_bytes, decode with from_le_bytes on a slice, not unaligned casts.
• Store the instruction offset as the patch site; the operand sits at +1.
• Verify before running: targets on instruction boundaries, slots in range, equal stack depth at joins.
• Compile let x = x + 1 initializers before declaring x; captured variables need upvalues.

Pitfalls

• A peephole pass after patching shifts offsets and breaks jumps: run it before patching, or relocate.
• as u16 truncates silently on big functions; check the length.

Variants and alternatives

In production

• Runtimes: Lua 5.x, CPython, the JVM.
• Databases: SQLite VDBE; EXPLAIN prints the program.
• Network: BPF filters are arrays of 8-byte struct sock_filter (code, jt, jf, k) (kernel docs).
• Smart contracts: Solidity compiles to EVM stack bytecode.
• Text search: the Rust regex crate compiles patterns to programs run by several engines.

Implementations

Sources

• Ierusalimschy, de Figueiredo, Celes, The Implementation of Lua 5.0, J. Univ. Comput. Sci. 2005. paper (title and venue from memory)
• Lindholm et al., The Java Virtual Machine Specification. spec
• Python docs, dis. doc · PEP 626, 3147, 552
• Linux kernel, Linux Socket Filtering aka BPF. doc