Optimization Passes

Imagine hiring a tireless editor for your code. You write it however feels natural — a spare variable here, a repeated calculation there, a line that turns out to do nothing. The editor reads every line and quietly rewrites it to run faster and take up less space, while guaranteeing one thing above all: the rewritten program computes the exact same answer for every possible input. That editor is the compiler's optimizer, and each individual rewrite it applies is an optimization pass.

The optimizer does not touch your source text. It works on the intermediate representation (IR) — the tidy, low-level form the compiler builds after parsing. On that IR it runs pass after pass, each a small, focused transformation: fold a constant, delete a dead line, reuse a value already computed. Run enough of these and clumsy code becomes tight code, without you ever knowing.

The golden rule: preserve the meaning

Every optimization pass lives under one iron law: it must be semantics-preserving. The transformed program must produce identical observable behaviour — same outputs, same return values, same visible side effects — as the original, for all inputs. An optimization is allowed to remove work; it is never allowed to remove meaning.

This is what makes optimization respectable rather than reckless. A pass that made your program slightly wrong to make it faster would be worthless — nobody wants a quick wrong answer. So every pass carries preconditions: conditions that must hold before it is safe to fire. Only when the compiler can prove the rewrite changes nothing observable does it apply it.

An optimization may change how a program computes its result — the instructions, their number, their order.
It must never change what result the program produces, for any input — the observable behaviour is fixed.
Every pass therefore has preconditions; it fires only when it can prove the rewrite is safe.

Constant folding: do the arithmetic now

If two operands are known at compile time, why wait until run time to combine them? Constant folding evaluates constant expressions during compilation and replaces them with their result. The classic case: 3 * 4 is not left as a multiply for the CPU to perform a billion times in a loop — the compiler computes 12 once, right now, and bakes it in.

Before After ------------------- ------------------- t1 = 3 * 4 t1 = 12 area = t1 * height area = t1 * height

The multiply 3 * 4 vanishes — the machine never runs it. Folding also handles 3600 * 24, string lengths, and anything else the compiler can evaluate without knowing the program's input.

Constant propagation: spread the known values

Constant folding gets far more powerful with a partner. Constant propagation notices that a variable holds a known constant and substitutes that constant wherever the variable is used. Once propagated, fresh constant expressions appear — which folding then collapses. The two passes feed each other, so compilers run them together, over and over, until nothing changes.

Before Propagate x=5 Then fold ------------ ------------------ ------------ x = 5 x = 5 x = 5 y = x * 2 y = 5 * 2 y = 10 z = y + 1 z = y + 1 z = 11

Propagate x = 5 into y = x * 2, fold to y = 10, propagate that into z, fold again — the whole chain becomes constants. A later dead-code elimination pass may then delete x and y entirely if nothing else reads them.

Common subexpression elimination: compute it once

If the program computes the very same expression twice, and nothing in between could have changed its operands, the second computation is wasted. Common subexpression elimination (CSE) computes the value once into a temporary and reuses it.

Before After ------------------- ------------------- t1 = a + b t0 = a + b x = t1 * 2 x = t0 * 2 t2 = a + b y = t0 - 1 y = t2 - 1

Both a + b subexpressions become a single temporary t0, saving one addition. The precondition matters: CSE is only safe if neither a nor b is reassigned between the two uses — otherwise the second a + b could be a different value, and reusing the old one would change the meaning.

Dead-code elimination: delete work that no one reads

Some computations produce a result that is never used, and some code can never even be reached. Dead-code elimination (DCE) removes both. If a variable is assigned and then never read before being overwritten or before the program ends, the assignment is dead — cut it. If control can never flow to a block (code after an unconditional return, or a branch whose condition is a known-false constant), it is unreachable — cut it too.

Before After ------------------- ------------------- x = 5 x = 5 y = expensive() return x + 1 return x + 1 z = x * y <- dead

Here y is computed but never used (the function returns before z), and the line assigning z is after the return, so it is unreachable. Both go. Note the care needed: if expensive() had an observable side effect (printing, writing a file), the compiler could not delete it — the result is unused, but the effect is observable, and deleting it would break the golden rule.

Build your own optimizer: constant folding on an AST

Constant folding is short enough to write in full. We model an arithmetic expression as a tiny tree: a num leaf or a bin binary operation. The folder walks the tree bottom-up; whenever both children of an operation have folded down to numeric literals, it replaces the operation node with a single literal holding the computed value. A mixed tree like 3 * 4 + x folds its constant part (3 * 4 → 12) but keeps the x. Press Run:

// An expression is a number literal, a variable (unknown until run time), // or a binary op with two sub-expressions. type Expr = | { kind: "num"; value: number } | { kind: "var"; name: string } | { kind: "bin"; op: "+" | "-" | "*"; left: Expr; right: Expr }; // Pretty-print a tree back to source-like text, so we can SEE the change. function render(e: Expr): string { if (e.kind === "num") return String(e.value); if (e.kind === "var") return e.name; return "(" + render(e.left) + " " + e.op + " " + render(e.right) + ")"; } // Count the operations still left in a tree (our "cost" measure). function ops(e: Expr): number { return e.kind === "bin" ? 1 + ops(e.left) + ops(e.right) : 0; } function apply(op: string, a: number, b: number): number { if (op === "+") return a + b; if (op === "-") return a - b; return a * b; } // The pass: fold children first (bottom-up); if BOTH are literals, collapse to one literal. function fold(e: Expr): Expr { if (e.kind !== "bin") return e; // a leaf (num or var) cannot fold further const left = fold(e.left); // fold the subtrees FIRST const right = fold(e.right); if (left.kind === "num" && right.kind === "num") { return { kind: "num", value: apply(e.op, left.value, right.value) }; } return { kind: "bin", op: e.op, left, right }; // operand still unknown: keep the op } const num = (value: number): Expr => ({ kind: "num", value }); const bin = (op: "+" | "-" | "*", left: Expr, right: Expr): Expr => ({ kind: "bin", op, left, right }); // Tree 1: 3 * 4 -> a single constant const t1 = bin("*", num(3), num(4)); console.log("all-constant:", render(t1), "->", render(fold(t1)), " ops", ops(t1), "->", ops(fold(t1))); // Tree 2: (3 * 4) + (x - 1) -- x is a runtime value, so that half cannot fold. const x: Expr = { kind: "var", name: "x" }; // an unknown, un-foldable leaf const t2 = bin("+", bin("*", num(3), num(4)), bin("-", x, num(1))); console.log("mixed tree: ", render(t2), "->", render(fold(t2)), " ops", ops(t2), "->", ops(fold(t2)));

The first tree collapses entirely to 12 — zero operations remain. The second folds its constant corner while leaving the parts that depend on real values intact, and its operation count drops accordingly. That is a genuine optimization pass, in about a dozen lines.

The control-flow graph: where global passes live

Folding a single expression is a local optimization — it looks only within one small piece. Bigger wins come from global passes that reason across a whole function: is this value still needed later? does this variable hold a constant on every path that reaches here? To answer such questions the compiler needs a map of how control can move through the code. That map is the control-flow graph (CFG), a kind of graph.

The CFG's nodes are basic blocks: maximal straight-line runs of IR with no branches in except at the top and no branches out except at the bottom. Once you enter a basic block you execute every instruction in it, in order, to the end. The CFG's edges are the possible jumps between blocks — a conditional branch splits into two edges (then/else), and separate paths merge back at a join block.

Many powerful passes are dataflow analyses run over this graph. Liveness analysis flows backward through the edges to discover which variables are still needed, powering dead-code elimination. Reaching-definitions flows forward to see which assignment supplies each use, powering constant propagation. The CFG is the shared stage on which global optimization and analysis perform.

A few more from the toolbox

The optimizer has dozens of passes; here are three more classics worth recognising:

Copy propagation. After y = x, replace later uses of y with x directly, so the copy may become dead and get deleted.
Strength reduction. Replace an expensive operation with a cheaper one that computes the same thing: x * 2 becomes x + x or a shift x << 1; a multiply inside a loop becomes a running addition.
Loop-invariant code motion. If a computation inside a loop gives the same result on every iteration, hoist it out of the loop so it runs once instead of a thousand times.

Every one of them is still bound by the same contract: fire only when the result is provably unchanged. Different work, identical meaning.

Yes — if it fires when its preconditions do not actually hold, it becomes a bug, and a nasty one. Reorder two statements that share a side effect (say, two writes to the same file) and the observable output changes. Assume signed integer arithmetic never overflows and "simplify" (x + 1) > x to true — correct in real numbers, but on a 32-bit int at the maximum value the addition wraps around and the inequality is false. This is exactly why real compilers are so fussy about the rules of their language: an optimization is only as safe as the assumptions it is allowed to make. Get those wrong and the "faster" program quietly computes the wrong answer.

Optimization removes work, not meaning. A pass may never change what the program does that is observable — only how much effort it spends getting there. If a rewrite can change any output for any input, it is not an optimization; it is a bug.
"Dead code" is not code you dislike. Dead-code elimination does not remove code that looks ugly or redundant to a human. It removes code whose result provably cannot affect any observable output. A computation whose value is unused but which prints, writes, or throws is not dead — its side effect is observable, so it stays.
CSE and propagation have preconditions. Reusing an earlier a + b is only safe if a and b were not reassigned in between. Skip that check and you reuse a stale value. "Same expression" is not enough — it must be the same value.