Part 9 · 1 chapters · ~8 min

Capstone: Extend the BYO Compiler

Four extensions to the 471-line BYO compiler, each test-first: a peephole optimiser that removes the jumps and dead code visible in its own output, a string type through every stage, for loops by desugaring, and arrays on a mark-sweep heap, with step-count measurements before and after.

Four extensions

code

cd modules/byo/repos/compiler
npm test                                    # baseline: pass 6, fail 0
node src/index.ts examples/fib.mini --asm   # baseline listing: 34 instructions (0-33)

// test first: the peephole pass must shrink code without changing output
test('peephole removes jump-to-next and code after RET', () => {
  const before = compile(fibSrc), after = peephole(before);
  assert.ok(after.code.length < before.code.length);
  assert.deepEqual(run(after).output, run(before).output);         // same behaviour
  assert.ok(!after.code.some((op, i) => op[0] === 'JMP' && op[1] === i + 1));
});

// for loops by desugaring, in the parser:
//   for (let i: int = 0; i < n; i = i + 1) { body }
//   →  { let i: int = 0; while (i < n) { body; i = i + 1; } }

CAPSTONE: EXTEND THE BYO COMPILER

four changes, each with tests first

swipe the figure sideways, or tap expand for full screen

1/4

peephole first

Add a pass over the bytecode that deletes a JMP whose target is the next instruction and any instructions after a RET that nothing jumps to; fix up jump targets. Test that fib.mini output is unchanged and shorter.

smaller code, same outputtargets must be renumbered