movabs, push/pop, add, imul, idiv, neg, ret -- straight into a growable byte buffer;fn (i64) i64 -- argument in rdi, result in rax;mmap and mprotect (the W^X flip), tying the JIT thread from episode 140 to a real compiler;errdefer make a code generator hard to get subtly wrong;Learn Zig Series):For three episodes we did something very specific -- we turned a regex pattern into an automaton and ran it. That was code generation in miniature: a syntax tree in, an executable artifact out. Now I want to ask the general question that sits behind every compiler ever written: given any tree, how do you produce something the CPU runs directly? Not a bytecode you interpret in a loop (that was episode 136), and not the yes/no automaton of the regex arc -- actual native x86-64 machine code, bytes you write into memory and then jump into. In episode 140 we lit that fuse: we hand-assembled a few bytes, flipped a page executable, and called it. Today we build the missing middle: a real code generator that walks an AST and emits those bytes for us. By the end you will type "(x + 5) * 2" and get back a genuine Zig function pointer that runs at the speed of the silicon. Here we go!
Three exercises closed the regex trilogy -- non-greedy operators, word boundaries, and the back-reference that forced us out of the automata camp. All three build on episode 143's Pike VM and program compiler, so paste them alongside that code.
Exercise 1 -- Non-greedy operators. The task was to add *?, +? and ??, the lazy variants that match as little as possible. The change really is tiny: a repetition just needs to remember whether it is greedy, and its split is emitted with the two branches in the opposite order when it is not. I give each repetition node a greedy flag, and in compileNode the greedy branch is tried first (goes in x), the lazy one flips x and y:
const Rep = struct { inner: *const Node, greedy: bool = true };
// ...the star / plus / optional payloads in Node now hold a Rep instead of *const Node.
// In compileNode:
.star => |rep| {
const sp = try self.emit(.{ .op = .split });
const body = self.here();
try self.compileNode(rep.inner);
_ = try self.emit(.{ .op = .jmp, .x = sp });
const exit = self.here();
// Greedy prefers the body (x is tried first); lazy prefers the exit.
self.insts.items[sp].x = if (rep.greedy) body else exit;
self.insts.items[sp].y = if (rep.greedy) exit else body;
},
.plus => |rep| {
const l1 = self.here();
try self.compileNode(rep.inner);
const sp = try self.emit(.{ .op = .split });
const exit = self.here();
self.insts.items[sp].x = if (rep.greedy) l1 else exit;
self.insts.items[sp].y = if (rep.greedy) exit else l1;
},
.optional => |rep| {
const sp = try self.emit(.{ .op = .split });
const body = self.here();
try self.compileNode(rep.inner);
const exit = self.here();
self.insts.items[sp].x = if (rep.greedy) body else exit;
self.insts.items[sp].y = if (rep.greedy) exit else body;
},
The parser detects the trailing ? with a one-line helper and sets the flag:
fn eat(self: *Parser, c: u8) bool {
if (self.peek() == c) {
self.pos += 1;
return true;
}
return false;
}
// In parseRepeat, for each of '*', '+', '?':
'+' => {
self.pos += 1;
atom = try self.new(.{ .plus = .{ .inner = atom, .greedy = !self.eat('?') } });
},
And the proof -- greedy a+ swallows the whole run, lazy a+? stops at one character, purely because the thread priority flipped:
test "lazy operators match as little as possible" {
const gpa = std.testing.allocator;
var greedy = try Regex.compile(gpa, "a+");
defer greedy.deinit();
const g = (try greedy.find("aaa")).?;
try std.testing.expectEqual(@as(usize, 3), g.end); // all three
var lazy = try Regex.compile(gpa, "a+?");
defer lazy.deinit();
const l = (try lazy.find("aaa")).?;
try std.testing.expectEqual(@as(usize, 1), l.end); // just one
}
The lovely part is that greedy versus lazy is not a runtime decision at all -- it is baked into the order the two split targets sit in the program. The Pike VM's "higher priority added first" rule does the rest, unchanged.
Exercise 2 -- Word boundaries. \b is a zero-width assertion, but unlike ^ and $ it depends on both the byte before and the byte after the cursor: a boundary sits exactly where a word character meets a non-word one (the string edges count as non-word). I add one instruction and one helper, and wire the check straight into addThread where the other asserts live:
fn isWord(c: u8) bool {
return (c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z') or (c >= '0' and c <= '9') or c == '_';
}
// A new Op.assert_word_boundary, compiled from a `\b` in the parser. In addThread:
.assert_word_boundary => {
// The edges count as non-word, so \b can fire at the very ends too.
const before = sp > 0 and isWord(self.input[sp - 1]);
const after = sp < self.input.len and isWord(self.input[sp]);
if (before != after) try self.addThread(list, pc + 1, saves, sp);
},
Because the assertion consumes nothing and only gates whether the thread proceeds, it slots into the epsilon machinery for free -- no change to the main loop at all:
test "word boundaries anchor whole words" {
const gpa = std.testing.allocator;
var re = try Regex.compile(gpa, "\\bcat\\b");
defer re.deinit();
try std.testing.expect(try re.isMatch("the cat sat"));
try std.testing.expect(!try re.isMatch("category"));
}
\bcat\b matches inside the cat sat because spaces flank the word, but not inside category, where a letter follows cat and the trailing \b fails. The parser change is a single line in the escape handler: if (e == 'b') return self.new(.word_boundary);.
Exercise 3 -- Back-references. This is the one the automata camp gives up, and building it teaches you why in the most physical way possible. A back-reference like \1 means "match the exact text group 1 captured", so a thread's fate now depends on text it recorded earlier -- which breaks the "one thread per instruction" dedupe that made the Pike VM linear. So you cannot bolt it onto the Pike VM; you drop back to a recursive backtracking matcher that literally tries every path:
const Backtracker = struct {
insts: []const Inst,
input: []const u8,
slots: []?usize,
steps: usize = 0,
fn go(self: *Backtracker, pc: usize, sp: usize) bool {
self.steps += 1;
const inst = self.insts[pc];
switch (inst.op) {
.char => return sp < self.input.len and self.input[sp] == inst.c and self.go(pc + 1, sp + 1),
.any => return sp < self.input.len and self.go(pc + 1, sp + 1),
.class => return sp < self.input.len and inst.cls.has(self.input[sp]) and self.go(pc + 1, sp + 1),
.match => return true,
.jmp => return self.go(inst.x, sp),
.split => return self.go(inst.x, sp) or self.go(inst.y, sp),
.assert_start => return sp == 0 and self.go(pc + 1, sp),
.assert_end => return sp == self.input.len and self.go(pc + 1, sp),
.save => {
const old = self.slots[inst.x];
self.slots[inst.x] = sp;
if (self.go(pc + 1, sp)) return true;
self.slots[inst.x] = old; // undo on failure -- this IS the backtrack
return false;
},
.backref => {
const n = inst.x;
const s = self.slots[2 * n] orelse return self.go(pc + 1, sp);
const e = self.slots[2 * n + 1] orelse return self.go(pc + 1, sp);
const text = self.input[s..e];
if (sp + text.len <= self.input.len and
std.mem.eql(u8, self.input[sp .. sp + text.len], text))
return self.go(pc + 1, sp + text.len);
return false;
},
}
}
};
fn backtrackMatch(gpa: std.mem.Allocator, pattern: []const u8, input: []const u8, steps_out: *usize) !bool {
var prog = try compileProgram(gpa, pattern);
defer prog.deinit();
const slots = try gpa.alloc(?usize, 2 * (prog.ngroups + 1));
defer gpa.free(slots);
var start: usize = 0;
var total: usize = 0;
while (start <= input.len) : (start += 1) {
@memset(slots, null);
var bt = Backtracker{ .insts = prog.insts, .input = input, .slots = slots };
const ok = bt.go(0, start);
total += bt.steps;
if (ok) {
steps_out.* = total;
return true;
}
}
steps_out.* = total;
return false;
}
It matches correctly -- ^(a+)\1$ only accepts even-length runs, and (\w+) \1 catches a doubled word -- but the moment you feed a backtracker a pattern with nested repetition and a failing tail, the running time detonates:
test "back-references work, but backtracking can detonate" {
const gpa = std.testing.allocator;
var steps: usize = 0;
try std.testing.expect(try backtrackMatch(gpa, "^(a+)\\1$", "aaaa", &steps)); // 2+2
try std.testing.expect(!try backtrackMatch(gpa, "^(a+)\\1$", "aaaaa", &steps)); // odd: no
try std.testing.expect(try backtrackMatch(gpa, "(\\w+) \\1", "hello hello", &steps));
var s8: usize = 0;
var s16: usize = 0;
_ = try backtrackMatch(gpa, "^(a+)+b$", "aaaaaaaa", &s8); // no 'b' -> forced to fail
_ = try backtrackMatch(gpa, "^(a+)+b$", "aaaaaaaaaaaaaaaa", &s16);
// Doubling the input multiplies the work catastrophically -- this is ReDoS,
// the exact failure the Pike VM is immune to by construction.
try std.testing.expect(s16 > 100 * s8);
}
On my machine ^(a+)+b$ takes about 1,800 recursion steps for eight as and over 450,000 for sixteen -- more than a hundredfold for a doubling of the input. That is the ReDoS that takes down web servers, and it is precisely why RE2, Go and Rust refuse back-references: the feature and the linear-time guarantee cannot coexist. You have now proven the tradeoff with your own hands. Right -- on to today's real subject. ;-)
Strip away the mystique and a code generator is a tree walk that prints -- except it prints machine instructions instead of characters. For every node shape in the AST it emits a fixed recipe of instructions, and it composes those recipes the way the tree composes. The hard question a real compiler agonises over is instruction selection (which machine instructions best implement this node) and register allocation (where to keep the intermediate values). We are going to sidestep the second one almost entirely with a trick as old as compilers: treat the machine's own hardware stack as our scratch space. Every subexpression, once generated, leaves its single result value pushed on the stack. A binary operator pops its two operands, computes, and pushes the answer. That is a stack machine, and it is the simplest strategy that is always correct, because it never runs out of registers -- the stack is effectively unbounded.
The tradeoff is honesty: stack-machine code is not fast code. It shuffles values to and from memory constantly, where a good compiler would keep them in registers. But it is correct, it is tiny, and it lets us focus this episode on the mechanics of emitting real bytes. Making that same code register-efficient is a whole discipline of its own -- one we pick up next time. For now, correctness first, speed later, exactly the order I always argue for.
Our source language is integer arithmetic over a single variable x: numbers, + - * /, parentheses, and unary minus. Small enough to fit in your head, rich enough that precedence and associativity actually matter. The AST is a four-case tagged union -- the shape you have seen since episode 133:
const std = @import("std");
const BinOp = enum { add, sub, mul, div };
const Expr = union(enum) {
num: i64,
var_x,
neg: *const Expr,
bin: struct { op: BinOp, lhs: *const Expr, rhs: *const Expr },
};
var_x is the compiled function's one input. num carries a literal. neg and bin hold child pointers, so the whole expression is a tree of these. Nothing here is Zig-specific yet -- it is the same AST you would draw for a calculator in any language. What makes the rest pleasant is that a union(enum) forces every consumer to handle every case, so when we grow the language later the compiler tells us exactly which switch arms went stale.
We already know how to turn text into this tree -- it is the recursive-descent parser from episode 132, in its most classic three-level form. parseExpr handles the low-precedence + -, parseTerm the higher-precedence * /, and parseFactor the atoms and parentheses. Left-to-right loops give left associativity for free:
const ParseError = error{ UnexpectedEnd, UnexpectedChar, ExpectedParen, TrailingInput, OutOfMemory };
const Parser = struct {
src: []const u8,
pos: usize = 0,
arena: std.mem.Allocator,
fn make(self: *Parser, e: Expr) ParseError!*Expr {
const p = try self.arena.create(Expr);
p.* = e;
return p;
}
fn skipSpaces(self: *Parser) void {
while (self.pos < self.src.len and self.src[self.pos] == ' ') self.pos += 1;
}
fn peek(self: *Parser) ?u8 {
self.skipSpaces();
return if (self.pos < self.src.len) self.src[self.pos] else null;
}
fn parseExpr(self: *Parser) ParseError!*Expr {
var lhs = try self.parseTerm();
while (self.peek()) |c| {
if (c != '+' and c != '-') break;
self.pos += 1;
const rhs = try self.parseTerm();
lhs = try self.make(.{ .bin = .{ .op = if (c == '+') .add else .sub, .lhs = lhs, .rhs = rhs } });
}
return lhs;
}
fn parseTerm(self: *Parser) ParseError!*Expr {
var lhs = try self.parseFactor();
while (self.peek()) |c| {
if (c != '*' and c != '/') break;
self.pos += 1;
const rhs = try self.parseFactor();
lhs = try self.make(.{ .bin = .{ .op = if (c == '*') .mul else .div, .lhs = lhs, .rhs = rhs } });
}
return lhs;
}
fn parseFactor(self: *Parser) ParseError!*Expr {
const c = self.peek() orelse return error.UnexpectedEnd;
switch (c) {
'-' => {
self.pos += 1;
return self.make(.{ .neg = try self.parseFactor() });
},
'(' => {
self.pos += 1;
const inner = try self.parseExpr();
if (self.peek() != ')') return error.ExpectedParen;
self.pos += 1;
return inner;
},
'x' => {
self.pos += 1;
return self.make(.var_x);
},
'0'...'9' => {
var v: i64 = 0;
while (self.pos < self.src.len and self.src[self.pos] >= '0' and self.src[self.pos] <= '9') {
v = v * 10 + (self.src[self.pos] - '0');
self.pos += 1;
}
return self.make(.{ .num = v });
},
else => return error.UnexpectedChar,
}
}
};
fn parse(arena: std.mem.Allocator, src: []const u8) !*Expr {
var p = Parser{ .src = src, .arena = arena };
const e = try p.parseExpr();
if (p.peek() != null) return error.TrailingInput;
return e;
}
One Zig detail worth calling out (it bit us in the regex arc too): the three parse functions are mutually recursive, so their inferred error sets form a cycle the compiler cannot resolve. Writing an explicit ParseError set on each one breaks the loop. All the tree nodes come from an arena, so there is not a single per-node free to worry about -- the arena drops the whole tree at once when compilation is done.
Now the fun part. The emitter is nothing but a growable buffer of u8 with two conveniences: append a fixed sequence of opcode bytes, and append a 64-bit immediate in little-endian (x86 is a little-endian architecture, so the low byte goes first):
const CodeBuf = struct {
bytes: std.ArrayList(u8),
gpa: std.mem.Allocator,
fn init(gpa: std.mem.Allocator) CodeBuf {
return .{ .bytes = .empty, .gpa = gpa };
}
fn deinit(self: *CodeBuf) void {
self.bytes.deinit(self.gpa);
}
fn emit(self: *CodeBuf, comptime bs: []const u8) !void {
try self.bytes.appendSlice(self.gpa, bs);
}
fn emitImm64(self: *CodeBuf, v: i64) !void {
var buf: [8]u8 = undefined;
std.mem.writeInt(i64, &buf, v, .little);
try self.bytes.appendSlice(self.gpa, &buf);
}
};
That is genuinely all a machine-code assembler is at the bottom: a function that appends bytes. Everything above it -- mnemonics, operands, labels -- is convenience we build on top. std.mem.writeInt with an explicit .little endianness means the same code emits correct immediates even if you cross-compiled the generator itself on a big-endian host; the target byte order is what matters, and we state it outright.
Here is the heart of the episode. generate walks the tree and, for each node, emits the x86-64 recipe that leaves the node's value on top of the hardware stack. I have annotated every instruction with its assembly mnemonic so you can read the bytes:
// Convention: every subexpression leaves its value pushed on the hardware
// stack. A binary op pops both operands, computes, and pushes the result.
fn generate(cb: *CodeBuf, e: *const Expr) !void {
switch (e.*) {
.num => |v| {
try cb.emit(&.{ 0x48, 0xB8 }); // movabs rax, imm64
try cb.emitImm64(v);
try cb.emit(&.{0x50}); // push rax
},
.var_x => {
try cb.emit(&.{0x57}); // push rdi (first System V integer arg)
},
.neg => |inner| {
try generate(cb, inner);
try cb.emit(&.{0x58}); // pop rax
try cb.emit(&.{ 0x48, 0xF7, 0xD8 }); // neg rax
try cb.emit(&.{0x50}); // push rax
},
.bin => |b| {
try generate(cb, b.lhs);
try generate(cb, b.rhs);
try cb.emit(&.{0x59}); // pop rcx (rhs)
try cb.emit(&.{0x58}); // pop rax (lhs)
switch (b.op) {
.add => try cb.emit(&.{ 0x48, 0x01, 0xC8 }), // add rax, rcx
.sub => try cb.emit(&.{ 0x48, 0x29, 0xC8 }), // sub rax, rcx
.mul => try cb.emit(&.{ 0x48, 0x0F, 0xAF, 0xC1 }), // imul rax, rcx
.div => try cb.emit(&.{ 0x48, 0x99, 0x48, 0xF7, 0xF9 }), // cqo; idiv rcx
}
try cb.emit(&.{0x50}); // push rax
},
}
}
fn compileToBytes(cb: *CodeBuf, root: *const Expr) !void {
try generate(cb, root);
try cb.emit(&.{0x58}); // pop rax (final result into return register)
try cb.emit(&.{0xC3}); // ret
}
Let me decode the encodings, because this is where the episode earns its "advanced". The 0x48 prefix in front of almost everything is the REX.W byte -- it says "this operates on 64-bit registers". movabs rax, imm64 is 0x48 0xB8 followed by the eight-byte constant, the only x86-64 instruction that takes a full 64-bit immediate. push rax and pop rax are the one-byte 0x50 and 0x58; push rdi (our argument register) is 0x57. For the operators, both operands are popped -- right into rcx, left into rax -- then add rax, rcx is 0x48 0x01 0xC8, imul is the two-byte-opcode 0x48 0x0F 0xAF 0xC1, and division is the fiddly one: cqo (0x48 0x99) sign-extends rax into the rdx:rax pair, then idiv rcx (0x48 0xF7 0xF9) does a signed 128-by-64 divide, quotient landing in rax.
The two facts that make the whole thing callable are the System V AMD64 calling convention: the first integer argument arrives in rdi (that is why var_x is just push rdi), and the return value goes back in rax (that is why we finish with pop rax; ret). We never touch rdx except transiently in division, and our pushes and pops are perfectly balanced, so the stack is exactly where the CPU expects it at the ret. No prologue, no epilogue, no stack frame -- our function is a leaf that calls nothing, so it needs none.
We have a []u8 of perfectly good machine code sitting in a normal heap allocation -- and the CPU will refuse to execute it, because that memory is not marked executable. This is the JIT step from episode 140, done properly. We mmap a fresh page as readable-writable, copy our bytes in, then mprotect it to readable-executable. Note that we never leave it writable and executable at the same time: that W^X discipline (write XOR execute) is what modern kernels want, and flipping in two steps respects it:
const JitFn = *const fn (i64) callconv(.c) i64;
const Compiled = struct {
mem: []align(std.heap.page_size_min) u8,
fn call(self: Compiled, x: i64) i64 {
const f: JitFn = @ptrCast(self.mem.ptr);
return f(x);
}
fn deinit(self: Compiled) void {
std.posix.munmap(self.mem);
}
};
fn jit(code: []const u8) !Compiled {
const mem = try std.posix.mmap(
null,
code.len,
.{ .READ = true, .WRITE = true },
.{ .TYPE = .PRIVATE, .ANONYMOUS = true },
-1,
0,
);
errdefer std.posix.munmap(mem);
@memcpy(mem[0..code.len], code);
// Flip the page from writable to executable: W^X, never both at once.
const rc = std.os.linux.mprotect(mem.ptr, mem.len, .{ .READ = true, .EXEC = true });
if (rc != 0) return error.MprotectFailed;
return .{ .mem = mem };
}
// A one-call convenience: source text -> live function.
fn compile(gpa: std.mem.Allocator, source: []const u8) !Compiled {
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const ast = try parse(arena_state.allocator(), source);
var cb = CodeBuf.init(gpa);
defer cb.deinit();
try compileToBytes(&cb, ast);
return jit(cb.bytes.items);
}
The @ptrCast from a page of bytes to a typed function pointer is the exact moment data becomes code -- the single most magical line in any JIT, and Zig makes you spell it out so it is impossible to do by accident. The callconv(.c) on JitFn is essential: it tells Zig this pointer follows the C/System V ABI, which is precisely the convention our bytes were written for. And look at the ownership story, which is very Zig: Compiled holds a page-aligned slice and owns it, so it has a deinit that munmaps; the errdefer in jit unmaps the page if mprotect ever fails, so a failed compile leaks nothing. The compile wrapper ties source to a live function in one call -- arena for the throwaway AST, a CodeBuf for the bytes, and out comes something you can invoke.
Real compilers do not emit code straight from the parse tree -- they transform it first. The simplest and most universal transform is constant folding: any subtree with no variables in it has a value known now, at compile time, so we compute it once and replace the subtree with a literal. It is a bottom-up rewrite, and Zig's exhaustive switch makes it very hard to forget a case:
fn fold(arena: std.mem.Allocator, e: *const Expr) !*const Expr {
switch (e.*) {
.num, .var_x => return e,
.neg => |inner| {
const f = try fold(arena, inner);
if (f.* == .num) {
const p = try arena.create(Expr);
p.* = .{ .num = -f.num };
return p;
}
const p = try arena.create(Expr);
p.* = .{ .neg = f };
return p;
},
.bin => |b| {
const l = try fold(arena, b.lhs);
const r = try fold(arena, b.rhs);
if (l.* == .num and r.* == .num) {
const v = switch (b.op) {
.add => l.num + r.num,
.sub => l.num - r.num,
.mul => l.num * r.num,
.div => @divTrunc(l.num, r.num),
};
const p = try arena.create(Expr);
p.* = .{ .num = v };
return p;
}
const p = try arena.create(Expr);
p.* = .{ .bin = .{ .op = b.op, .lhs = l, .rhs = r } };
return p;
},
}
}
fn countNodes(e: *const Expr) usize {
return switch (e.*) {
.num, .var_x => 1,
.neg => |inner| 1 + countNodes(inner),
.bin => |b| 1 + countNodes(b.lhs) + countNodes(b.rhs),
};
}
Fold x + (2 * 3 + 4) and the (2 * 3 + 4) collapses to a single 10 before a byte of machine code is emitted -- fewer instructions, a smaller page, a faster function, and the runtime never does arithmetic the compiler could have done for it. That is the entire philosophy of an optimizing compiler in one pass: move work from run time to compile time whenever you provably can. Bigger optimizers stack dozens of these passes (dead-code elimination, common-subexpression elimination, strength reduction), but they are all variations on "rewrite the tree into a cheaper tree that computes the same thing".
A code generator is a machine for producing bugs that only show up as wrong numbers, so I lean hard on differential testing: compile an expression, then check the JIT's output against the same formula written directly in Zig, across a whole range of inputs. If native machine code and the Zig reference ever disagree, the test screams. I pair that with an exact-bytes test on a trivial program, so encoding mistakes are caught at the byte level, not just the result level:
test "generated code matches a Zig reference across many inputs" {
const gpa = std.testing.allocator;
var f = try compile(gpa, "(x * x + 7 * x) / 2 - 3");
defer f.deinit();
var x: i64 = -50;
while (x <= 50) : (x += 1) {
const expected = @divTrunc(x * x + 7 * x, 2) - 3;
try std.testing.expectEqual(expected, f.call(x));
}
}
test "the emitted bytes are exactly what we expect for a trivial program" {
const gpa = std.testing.allocator;
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const ast = try parse(arena_state.allocator(), "x");
var cb = CodeBuf.init(gpa);
defer cb.deinit();
try compileToBytes(&cb, ast);
// push rdi ; pop rax ; ret
try std.testing.expectEqualSlices(u8, &.{ 0x57, 0x58, 0xC3 }, cb.bytes.items);
}
The differential test is the one I trust most. It runs the actual JIT-compiled function for a hundred and one values of x and compares each to Zig's own arithmetic -- precedence, integer division truncation, unary minus, all of it, all agreeing. When that passes you are not hoping your byte encodings are right, you are watching them be right against an independent oracle. The exact-bytes test is the microscope for when they are not: if push rdi ever stops being 0x57, this test tells you the exact byte, not just "the answer was wrong". Together they cover the two failure modes of code generation -- wrong instruction selected, and right instruction wrongly encoded.
Everything here is the real architecture, just scaled down. A production compiler still parses to an AST (or something close), still lowers it toward the machine, still does instruction selection and emits bytes. What we skipped is the industrial-strength middle: an intermediate representation (usually SSA form) that optimizations chew on, and a real register allocator so values live in registers instead of bouncing on the stack. LLVM -- the backend behind Clang, and behind Rust's rustc -- is exactly that middle taken to its limit: dozens of passes over an IR, then a sophisticated instruction selector and register allocator per target. Zig itself ships its own backends alongside LLVM for the same reason. Go's compiler is famously LLVM-free: its own SSA backend and register allocator, tuned for fast compiles over maximal optimization -- a very deliberate tradeoff. And the JIT lineage from episode 140 lives here too: V8's TurboFan, LuaJIT and the JVM's HotSpot all do this same "tree in, native bytes out" at run time, guided by profiling, which is why they can sometimes beat an ahead-of-time compiler that never saw the real workload.
The honest gap in our version is register allocation -- the stack-machine strategy is what a real compiler does before it gets clever, and turning that shuffling into tight register code is a genuinely hard and beautiful problem. We take exactly that step next time, so hold the thought.
Add a modulo operator %. Division already emits cqo; idiv rcx, and idiv leaves the remainder in rdx while the quotient goes to rax. So % is nearly free: emit the same cqo; idiv rcx, but move rdx into rax before pushing (mov rax, rdx is 0x48 0x89 0xD0). Wire it through the lexer and parseTerm (same precedence as * and /), then differential-test x % 7 against Zig's @rem across many inputs. Mind the sign rules -- decide whether you want truncated or floored modulo and test the negative cases.
Add comparisons that yield 0 or 1. Extend the language with x > 5 and friends. This is real instruction selection: emit cmp rax, rcx (0x48 0x39 0xC8), then a setcc that writes a 0/1 byte into al (e.g. setg al is 0x0F 0x9F 0xC0), then zero-extend with movzx rax, al (0x48 0x0F 0xB6 0xC0). Support >, <, ==, !=, prove each against a Zig reference, and notice how "an expression is always an integer" keeps the stack-machine convention intact.
Write a peephole optimizer over the emitted bytes. Our stack discipline produces obvious waste -- a push rax (0x50) immediately followed by a pop rax (0x58) is a no-op that can simply be deleted. Write a pass that scans the byte buffer (or, more robustly, a list of emitted instructions before flattening) and removes such redundant pairs, then measure how many bytes you save on (x + 1) + (x + 1). For bonus credit, fold movabs rax, imm; push rax; pop rax back into keeping the value in a register -- and feel why doing this properly is really just register allocation knocking at the door.
That is a compiler you can read top to bottom: source text in, a parse tree, a constant-folding pass, an instruction-selecting tree walk, real x86-64 bytes, and a page you can jump into and call like any other Zig function. The one thing standing between our stack-shuffling output and code a real compiler would be proud of is where the values live -- and that is exactly the knot we untie next time. Thanks for your time, and happy compiling! ;-)
@scipio