Code Generation

Three concepts: the compiler's three jobs, jump patching, and slot allocation.

The compiler is the second-largest file you write, and almost all of its difficulty is in two places: filling in a jump target you did not know yet, and deciding which stack slot a name lives in. Everything else is a post-order walk.

Concept 1: The Compiler's Three Jobs

1. Concept

A code generator turns a tree into a linear instruction sequence. In doing so it performs three resolutions, each of which converts something symbolic into something numeric:

   names       ──▶  slot numbers        (scope resolution)
   literals    ──▶  constant indices    (pooling)
   structure   ──▶  jump targets        (linearization)

2. Problem

The VM has no names, no nesting, and no literals. Everything it sees is an index. Somebody has to do the converting, and the AST is the last representation that still has the information.

3. Mental model

Compilation is the deletion of everything the machine does not need, and the numbering of everything that is left. After this pass, x is 3, "score" is constants[7], and "the else branch" is 0021.

Two invariants make the whole thing composable, and they are worth writing on a card:

   compile_expr(e)   leaves EXACTLY ONE value on the stack.      net effect: +1
   compile_stmt(s)   leaves the stack EXACTLY as it found it.    net effect:  0

Every bug in Lab 10 that is not a jump-patching bug is a violation of one of those two lines.

4. Implementation

#![allow(unused)]
fn main() {
pub struct Compiler {
    chunk: Chunk,
    locals: Vec<Local>,        // a STACK of live locals; index == slot number
    scope_depth: usize,
    breaks: Vec<Vec<usize>>,   // one pending-jump list per enclosing loop
    stack_depth: u16,          // current; used to compute max_stack
    max_stack: u16,
}

struct Local { name: String, depth: usize, span: Span, captured: bool /* Lab 14 */ }

impl Compiler {
    fn emit(&mut self, op: Op, span: Span) -> usize {
        self.track_stack_effect(op);       // keeps stack_depth and max_stack honest
        self.chunk.emit(op, span)
    }
}
}

locals is a stack, and its index is the slot number. That single sentence is the whole of scope resolution: declaring a local pushes; resolving a name searches backwards (so inner shadows outer); leaving a scope pops everything at that depth and emits one POP n.

#![allow(unused)]
fn main() {
fn resolve_local(&self, name: &str) -> Option<u8> {
    // BACKWARDS: the innermost declaration wins. This is shadowing, and it is
    // the same inward-out search the tree walker did — but it happens ONCE,
    // here, at compile time, instead of on every read at run time.
    self.locals.iter().rposition(|l| l.name == name).map(|i| i as u8)
}
}

Compare that with the tree walker's Env::get. Same algorithm. Different time. That is the entire performance story of Section 3 in one observation, and it is why Claim 3 says names are a compile-time concept.

5. Alternatives

6. Decision

A, with the resolver folded in.

The single pass works because Ember's grammar is such that everything a statement needs is known by the time you reach it — with exactly one exception, jumps, which is what backpatching is for.

Option C becomes attractive in Lab 14, where resolving a name may require walking enclosing function scopes to discover an upvalue. Ember handles that by giving each Compiler a parent pointer rather than adding a pass — note it as a place where the decision was close.

7. Tradeoffs

8. Production concerns

• Compile-time limits must be compile errors. More than 256 locals, more than 65,536 constants, a function nested more deeply than the compiler's own recursion guard — each must produce a diagnostic with a span, never a truncated operand. Test each with a generated file.
• The compiler recurses on the AST, so it inherits the parser's depth hazard. It is already bounded by MAX_PARSE_DEPTH, because no tree deeper than that can exist — but say so in a comment, because that reasoning is invisible and someone will raise the parse limit.
• max_stack must be an over-approximation, never an under-approximation. The VM reserves that much stack for the frame; too small means writes past the end of the frame's region. Compute it by tracking stack_depth at every emit and taking the maximum — and at a control-flow join, take the maximum of the incoming depths, not the last one.

Concept 2: Jump Patching

1. Concept

Backpatching is emitting a jump whose target you do not know yet, remembering where you put it, and filling in the target once you get there.

2. Problem

if cond then A else B end

The JUMP_IF_FALSE that skips A must target the first instruction of B. But B has not been compiled yet — you do not know its address until you have emitted all of A. And you cannot compile A after B, because the code must come out in source order.

3. Mental model

Emit the jump with a placeholder target, keep its index, and come back. A jump you have emitted but not yet patched is a debt, and the compiler must have paid all its debts before the chunk is done.

   compile `if c then A else B end`

   0000  <code for c>                    ────┐
   ....  JUMP_IF_FALSE  ????   ← debt #1     │  emit placeholder, remember index
   ....  <code for A>                        │
   ....  JUMP           ????   ← debt #2     │  emit placeholder, remember index
   0021: <code for B>          ← pay debt #1 ┘  patch: target = here
   0034: ...                   ← pay debt #2    patch: target = here

4. Implementation

#![allow(unused)]
fn main() {
/// Emit a jump with a placeholder target. Returns the index to patch.
fn emit_jump(&mut self, make: fn(u32) -> Op, span: Span) -> usize {
    self.emit(make(u32::MAX), span)          // u32::MAX is an OBVIOUSLY invalid target
}

/// Fill in a previously emitted jump to point at the NEXT instruction to be emitted.
fn patch_jump(&mut self, at: usize) {
    let target = self.chunk.code.len() as u32;
    match &mut self.chunk.code[at] {
        Op::Jump(t) | Op::JumpIfFalse(t)
        | Op::JumpIfFalseKeep(t) | Op::JumpIfTrueKeep(t) => {
            debug_assert_eq!(*t, u32::MAX, "double-patched jump at {at}");
            *t = target;
        }
        other => panic!("patch_jump on a non-jump: {other:?}"),
    }
}
}

Three details, each of which prevents a specific bug:

1. The placeholder is u32::MAX, not 0. A 0 placeholder that never gets patched is a valid jump to the start of the function: an infinite loop that runs. u32::MAX fails validation loudly. Choose placeholders that cannot be mistaken for real values — the same principle as a poison value in a memory allocator.
2. debug_assert_eq!(*t, u32::MAX) catches double-patching, which happens when a break list is patched by both the loop and an enclosing construct.
3. Targets are absolute, so patch_jump is code.len() and there is no "offset from where?" question. This is the encoding decision paying for itself: the classic backpatching off-by-one does not exist in Ember. With relative offsets you must decide whether the offset is from the jump instruction or the one after it, and then be consistent in two places. Note this in your journal as an example of a representation choice eliminating a bug class rather than mitigating it.

The four control-flow shapes, which between them cover the whole language:

#![allow(unused)]
fn main() {
// if / elseif / else — a chain of (skip-if-false) with (jump-to-end) between arms
fn compile_if(&mut self, arms: &[(Expr, Block)], else_: &Option<Block>) -> Result<()> {
    let mut ends = Vec::new();
    for (cond, body) in arms {
        self.compile_expr(cond)?;
        let next = self.emit_jump(Op::JumpIfFalse, cond.span());
        self.compile_block(body)?;
        ends.push(self.emit_jump(Op::Jump, body.span));
        self.patch_jump(next);                        // ← next arm starts HERE
    }
    if let Some(b) = else_ { self.compile_block(b)?; }
    for e in ends { self.patch_jump(e); }             // ← all arms converge HERE
    Ok(())
}

// while — the ONLY backwards jump, and its target is known before you need it
fn compile_while(&mut self, cond: &Expr, body: &Block) -> Result<()> {
    let top = self.chunk.code.len() as u32;           // ← remembered, not patched
    self.compile_expr(cond)?;
    let exit = self.emit_jump(Op::JumpIfFalse, cond.span());
    self.breaks.push(Vec::new());
    self.compile_block(body)?;
    self.emit(Op::Jump(top), body.span);              // the back-edge: a KNOWN target
    self.patch_jump(exit);
    for b in self.breaks.pop().unwrap() { self.patch_jump(b); }   // every `break` lands here
    Ok(())
}

// break — emit a debt, and hand it to the innermost loop
fn compile_break(&mut self, span: Span) -> Result<()> {
    let n = self.locals_declared_since_loop_start();
    if n > 0 { self.emit(Op::Pop(n), span); }         // ← discard the loop body's locals!
    let j = self.emit_jump(Op::Jump, span);
    self.breaks.last_mut().expect("parser rejects break outside a loop").push(j);
    Ok(())
}

// and / or — a conditional jump that KEEPS the operand
fn compile_and(&mut self, lhs: &Expr, rhs: &Expr) -> Result<()> {
    self.compile_expr(lhs)?;                          // +1
    let skip = self.emit_jump(Op::JumpIfFalseKeep, lhs.span());
    self.emit(Op::Pop(1), lhs.span());                // -1  (only on the fall-through)
    self.compile_expr(rhs)?;                          // +1
    self.patch_jump(skip);
    Ok(())                                            // net +1 on BOTH paths. Check it.
}
}

Warning: The Op::Pop(n) in compile_break is the step everyone forgets. A break from inside a block that declared locals must discard them, or the stack is left deeper than the compiler thinks it is — and every subsequent GET_LOCAL reads the wrong slot. It is silent, it only manifests when a loop body declares a local and contains a break, and it is exactly the kind of thing a golden test finds and a hand-written test does not. The same applies to return from inside nested blocks.

5–7. Alternatives, decision, tradeoffs

Decision: A. It is one pass and the debts are visible in the code. Option C is genuinely interesting and worth understanding: Wasm eliminated a whole category of malformed-bytecode attacks by making arbitrary jumps inexpressible. Ember cannot follow it without also giving up goto-shaped lowerings it may want later, and it gets the safety from validation instead.

8. Production concerns

• Every debt must be paid. Add a check at the end of compilation: no instruction in code may still contain u32::MAX. That is a two-line assertion and it catches an entire class of "the loop never exits" bugs at compile time rather than at run time.
• Do not debug jump patching by reading the compiler. Print the disassembly with absolute targets and read that. This is stated in the section index's mistakes table and it is the single most time-saving habit in Section 3.
• while with the condition at the top costs one extra jump per iteration. The alternative — jump to the condition, put the body first, condition at the bottom — is called loop rotation and every C compiler does it. It is a Section 7 challenge, and doing it now would make the disassembly harder to read for no measured benefit.

Concept 3: Slot Allocation

1–3. Concept, problem, mental model

Slots are allocated on a stack that mirrors lexical scope. Entering a block remembers the current watermark; leaving it pops back to the watermark and emits one POP n. Sibling blocks therefore reuse the same slots, which is both a memory win and a thing you can see in the disassembly.

   local a = 1        slot 0        locals: [a]
   do
     local b = 2      slot 1        locals: [a, b]
     local c = 3      slot 2        locals: [a, b, c]
   end                POP 2         locals: [a]              ← slots 1,2 released
   do
     local d = 4      slot 1        locals: [a, d]           ← REUSED
   end                POP 1

4. Implementation

#![allow(unused)]
fn main() {
fn begin_scope(&mut self) { self.scope_depth += 1; }

fn end_scope(&mut self, span: Span) {
    self.scope_depth -= 1;
    let mut n = 0u8;
    while let Some(l) = self.locals.last() {
        if l.depth <= self.scope_depth { break; }
        // Lab 14: if l.captured, emit CloseUpvals instead of counting it into POP.
        self.locals.pop();
        n += 1;
    }
    if n > 0 { self.emit(Op::Pop(n), span); }
}

fn declare_local(&mut self, name: &str, span: Span) -> Result<u8> {
    if self.locals.len() >= 256 {
        return Err(compile_error_at(span, "too many local variables in function"));
    }
    // NOTE: the caller has ALREADY compiled the initializer. That ordering is
    // what makes `local x = x` read the OUTER x — the same rule the tree walker
    // implements by evaluating before declaring. Two backends, one semantic,
    // enforced in two different places. This is exactly the kind of thing
    // differential testing exists to check.
    self.locals.push(Local { name: name.into(), depth: self.scope_depth, span, captured: false });
    Ok((self.locals.len() - 1) as u8)
}
}

5–8. Alternatives, decision, production concerns

Production concerns:

• The 256-slot limit is an encoding consequence (u8), not a language rule, and it must produce a clean error naming the function. Lua's limit is ~200 for the same reason. Generated code hits this; hand-written code essentially never does.
• A local is not live until its initializer has been compiled. Getting this backwards gives you JavaScript's temporal dead zone by accident, and gives local x = x the wrong meaning. It is one line, in two backends, and it is worth a golden test in both.
• captured (Lab 14) changes end_scope. A captured local cannot simply be popped; its upvalue must be closed first. Leaving the field in the struct now, unused, is cheaper than threading it through later.

9. References

rg -n 'freereg|luaK_reserveregs|luaK_exp2nextreg|removevars' lcode.c lparser.c
rg -n 'patchlist|luaK_patchtohere|luaK_concat|luaK_jumpto' lcode.c

• Lua's lcode.c — luaK_patchlist and friends are backpatching for a register machine, and patchlistaux shows how Lua patches a chain of jumps by threading the list through the jump instructions' own operand fields. That trick costs no extra memory and is worth seeing.
• Crafting Interpreters, chapters 22–23 — emitJump/patchJump in clox, essentially identical to Ember's with relative offsets.
• The WebAssembly spec's "Control Instructions" — option C, for contrast.

Things to Notice

• The compiler does the same name search the tree walker did, once, at compile time. That sentence is the whole performance argument for Section 3.
• Two invariants (expr = +1, stmt = 0) catch most bugs. Assert them, do not just believe them.
• Absolute jump targets delete the classic backpatching off-by-one. A representation choice eliminated a bug class instead of documenting it.
• u32::MAX as a placeholder fails loudly; 0 fails silently as a jump to the top. Choose poison values that cannot be valid.
• break must pop the locals declared since the loop started. Silent, rare, and exactly what a golden corpus catches.
• Slot reuse across sibling blocks is visible in the disassembly. Go look at it; it is the cheapest possible confirmation that your scope handling is right.

Validation / Self-check

1. Name the three resolutions a code generator performs and what each converts.
2. State the two stack invariants. Give a bug that violates each.
3. Why can the if jump not be emitted with its target already known? Describe backpatching in one sentence.
4. Why is u32::MAX a better placeholder than 0?
5. Why does Ember have no backpatching off-by-one, and what would reintroduce it?
6. Trace a and b through the compiler and show the stack depth is equal on both paths.
7. What must compile_break emit before its jump, and what is the symptom of forgetting it?
8. How are slots reused across sibling blocks, and how would you confirm it on your own machine?
9. Where is local x = x's ordering rule enforced in the compiler, and where in the tree walker? What checks that they agree?
10. Why must max_stack be an over-approximation, and what do you do at a control-flow join?

Next: Dispatch.