Part 6 · 1 chapters · ~8 min

Code Generation

Stack-machine code generation by post-order traversal, control flow with jumps and backpatching, short-circuit evaluation for && and ||, functions, frames and calling conventions, register machines and register allocation (linear scan, graph colouring), instruction selection, and targeting WebAssembly or LLVM instead of writing a back end.

7

From tree to instructions

code
// codegen for if/else with backpatching (the BYO approach, simplified)
case 'if': {
  genExpr(s.cond);
  const jz = emit(['JZ', -1]);                 // placeholder target
  for (const t of s.then) genStmt(t);
  const jmp = emit(['JMP', -1]);
  code[jz][1] = code.length;                   // patch: false branch lands here
  for (const t of s.else) genStmt(t);
  code[jmp][1] = code.length;                  // patch: then-branch skips the else
  break;
}
// short-circuit a && b: evaluate a; if false, skip b entirely (JZ over it) and push 0
code
;; the same function compiled to WebAssembly text: a stack machine too
(func $fib (param $n i32) (result i32)
  (if (result i32) (i32.lt_s (local.get $n) (i32.const 2))
    (then (local.get $n))
    (else (i32.add (call $fib (i32.sub (local.get $n) (i32.const 1)))
                   (call $fib (i32.sub (local.get $n) (i32.const 2)))))))

Do not write a native back end for a new language unless that is the point: emit LLVM IR (Rust, Swift, Zig historically), Cranelift (fast compile times), WebAssembly, or C, and reuse decades of optimisation and register allocation work.

CODE GENERATION FOR `if (n < 2) { return n; }`
a tree becomes flat instructions with jumps
codegencode arraygen(cond): LOAD 0, PUSH 2, LT
swipe the figure sideways, or tap expand for full screen
1/4
expressions
An expression on a stack machine is a post-order walk: emit the left operand, the right operand, then the operator. n < 2 becomes LOAD 0, PUSH 2, LT.
post-order walkoperands, then operator