Part 5 · 1 chapters · ~8 min

Optimisation Passes

Correctness first (optimisations must preserve observable behaviour), constant folding as implemented in the BYO compiler, propagation, dead code elimination, common subexpression elimination, inlining, loop optimisations, peephole optimisation on the BYO bytecode, pass ordering, undefined behaviour as an optimiser's licence, and checking optimisers with differential testing.

Folding, and waste in real output

code

// from src/fold.ts
case '/': if (b !== 0) return { k: 'num', value: Math.trunc(a / b), ...pos }; break;   // never fold x / 0

// node src/index.ts examples/fib.mini --asm  (real output, excerpt)
fib:
   15  LOAD 0
   16  PUSH 2
   17  LT
   18  JZ 22
   19  LOAD 0
   20  RET
   21  JMP 22        ← unreachable (after RET) and jumps to the next instruction anyway
   22  LOAD 0
   …
   31  RET
   32  PUSH 0        ← implicit "return 0" after an explicit return: unreachable
   33  RET

Differential testing: run every test program with and without the optimiser and compare outputs; any difference is an optimiser bug. Csmith-style random program generators found hundreds of bugs in GCC and LLVM this way.

OPTIMISATION PASSES

each rewrites code to something faster with the same behaviour

swipe the figure sideways, or tap expand for full screen

1/4

folding

The BYO folder evaluates sub-expressions whose operands are literals at compile time, but leaves division by a literal zero alone so the runtime reports the error at the right position.

compute at compile timekeep runtime errors honest