cp-09 — SSA Construction & Optimisation Passes

Status: ✅ Built (41/41 checks)

This lab takes the Three-Address Code from cp-08 and adds the middle-end: an IR interpreter that can execute TAC directly, a small pass pipeline (constant folding + propagation, dead-code elimination, CFG simplification), and a fix-point driver. The conceptual material covers full SSA — phi nodes, dominance, mem2reg — even though the implementation stops at a simpler whole-function constant-propagation scheme. The progression to real SSA happens when we hand off to LLVM in cp-10/11.

Layout

File	Purpose
`src/ir.{hpp,cpp}`	TAC IR types (unchanged from cp-08).
`src/ir_builder.{hpp,cpp}`	AST → TAC lowering. Fixed dangling-reference bug from cp-08 (`newBlock` returns a vector reference invalidated by subsequent inserts; capture `.id` immediately).
`src/ir_printer.{hpp,cpp}`	Module pretty-printer.
`src/passes.{hpp,cpp}`	`constFold`, `dce`, `simplifyCFG`, `runAll`.
`src/ir_interp.{hpp,cpp}`	Direct interpreter for the IR — semantics oracle.
`src/main.cpp`	`mlopt` driver: prints before/after IR, then runs.
`tests/test_passes.cpp`	11 tests / 41 checks.

Pipeline

source → tokens → AST → resolver → typechecker → IR (TAC) →
   [print "before"] → constFold → dce → simplifyCFG → [fixpoint] →
   [print "after"]  → IR interpreter → stdout

Build & run

cd src/cpp
cmake -S . -B build && cmake --build build
ctest --test-dir build --output-on-failure

CLI:

./build/mlopt examples/loop.ml          # print before/after IR + run
./build/mlopt --quiet  examples/loop.ml # just run
./build/mlopt --no-run examples/loop.ml # IR only

What each pass does

constFold — substitute single-def tN = <const> chains, fold binary/unary on constant operands into Move, collapse cjmp on a constant condition into jmp.
dce — drop pure value-producing instructions whose temp dst is never used. print, stg, call, and terminators are always preserved (no effect-purity analysis in this lab).
simplifyCFG — flood-fill reachability from bb0, drop unreachable blocks. After a cjmp is rewritten to a jmp, this is what actually deletes the abandoned branch.

The driver alternates them until a full sweep changes nothing.

Conceptual highlights (see `steps/`)

SSA as the universal IR shape used by LLVM, V8 Sparkplug, HotSpot, GraalVM, JavaScriptCore, and Cranelift — and why every modern compiler bottoms out in dominance/dominance-frontier algorithms.
mem2reg as the canonical SSA-construction algorithm: every named local becomes a series of versioned values, joined by phi nodes at dominance frontiers.
Why we stopped short of mem2reg here: classical SSA construction requires dominator computation, dominance-frontier sets, iterated insertion, and renaming. The book-keeping is well-documented (Cytron et al. 1991) and worth implementing — but at the cost of much more code than is needed for our optimisation set. The constant-propagation scheme we use here gets ~80% of the practical wins.

Test coverage

Constant folding of arithmetic and comparisons.
DCE preserves side effects (print, call, stg).
simplifyCFG drops unreachable: blocks emitted after return.
Branches on constants collapse to a single arm.
Interpreter executes loops, function calls, mutual recursion, short-circuit operators.
Round-trip property: running the interpreter before and after the pass pipeline produces identical output.

Compilers & Parser Engineer