Optimization

Optimisation is a misnomer — it is really code improvement. This deck builds the theory (data-flow analysis) and then applies it: the classic transformations, loop and SSA-based passes, and how real compilers sequence them.

An optimiser rewrites code to improve some objective — but it may only do so if the rewrite is semantics-preserving. This is the “as-if” rule: the program must behave as if every step of the abstract machine ran, even if the compiler actually did something cheaper.

A “faster” program that computes a different answer is not an optimisation — it is a miscompilation. Correctness first, always.

Optimisations are classified by the scope they reason over. Wider scope sees more opportunities but costs more analysis — and crosses harder boundaries (function calls, translation units, the whole program).

Almost every global optimisation rests on data-flow analysis (DFA): a general method for computing, at every program point, a conservative summary of what must or may hold there. The framework has four parts — pick them, turn the crank, get a sound answer.

in[B]  = MEET over predecessors P of out[P]   (forward)
out[B] = transfer_B( in[B] )
         = gen[B] ∪ ( in[B] − kill[B] )

# backward analyses swap in/out and use successors:
out[B] = MEET over successors S of in[S]
in[B]  = transfer_B( out[B] )

The meet operator combines facts arriving along different paths. Its choice (∪ vs ∩) is exactly what makes an analysis may or must.

The domain of facts forms a lattice: a partially-ordered set where every pair of elements has a greatest lower bound (meet, ∧) and a least upper bound (join, ∨). ⊤ (top) is “no information yet / everything possible”; ⊥ (bottom) is “over-defined / conflicting”. Iteration moves facts monotonically down.

To solve the equations we iterate to a fixed point. Initialise every block to ⊤, then repeatedly recompute blocks whose inputs changed until nothing changes. The worklist keeps us from rescanning stable blocks.

worklist ← all blocks
out[B]   ← ⊤   for all B   (∅ for a union analysis)
out[entry] ← boundary condition

while worklist not empty:
    B ← pop(worklist)
    in[B]  ← MEET over preds P of out[P]
    new    ← gen[B] ∪ (in[B] − kill[B])
    if new ≠ out[B]:
        out[B] ← new
        worklist ← worklist ∪ successors(B)

Reaching definitions (forward, may): which assignments could reach a point unkilled? At the join block B4, in is the union of both predecessors' out — so d2 and d3 both reach.

gen[B2]  = { d2 }
kill[B2] = { d1, d3 }   # other defs of x
out[B2]  = gen ∪ (in − kill)
         = { d2 }

Every data-flow analysis sits in one of four boxes, fixed by two independent choices: which direction information flows, and whether facts are may (union) or must (intersection).

The complete classification. Memorise the four-corner pattern and you can derive any of them from first principles.

The bread-and-butter scalar transforms. Each is cheap, enabling, and synergistic — one creates opportunities for the next, which is why optimisers run them repeatedly.

int s = 60 * 60 * 24;
// folds to:
int s = 86400;

x = 4;
y = x + 2;   // → y = 4 + 2
             // → y = 6 (then folds)

x = y;
z = x + 1;   // → z = y + 1
// x now possibly dead → DCE removes it

Loops are where programs spend their time, so they get the most attention. Loop-Invariant Code Motion hoists computations that produce the same value every iteration out to the pre-header — computed once instead of N times.

Modern CPUs offer SIMD units (SSE/AVX/AVX-512 on x86, NEON/SVE on ARM, V on RISC-V) that apply one operation to a vector of lanes. The vectoriser rewrites a scalar loop to process several elements per iteration.

// scalar: 1 add per iteration
for (i = 0; i < n; i++)
    c[i] = a[i] + b[i];

// vectorised (width 4): 4 adds per iteration
for (i = 0; i + 4 <= n; i += 4)
    c[i:i+4] = a[i:i+4] + b[i:i+4];  // one VADD
// + a scalar remainder/peel loop for the tail

In SSA form (Part 06) each variable is assigned exactly once, so a use points directly at its single definition — def-use chains are explicit and free. Many analyses that needed full data-flow now become a sparse graph walk.

No single optimisation is dramatic; the cascade is. Watch a snippet shrink as const-prop, folding, CSE, strength-reduction and DCE fire in sequence.

Each pass is simple; together they fold the whole function to return 64;. The art is in ordering and repeating them.

Two pointers alias if they may refer to the same storage. Almost every memory optimisation hinges on the question “can this store affect that load?” — and a conservative “maybe” kills the optimisation. Alias analysis is the silent ceiling on what a compiler can do.

*p = 1;
x = *q;        // is x == 1 ? only if p,q alias
*p = 2;        // can we drop the *p=1 store?
               // only if nothing reads through
               // an alias in between

Optimisations interact: one pass creates opportunities for another — or destroys them. There is no universally best order, and the search space is enormous. This is the phase-ordering problem, and it has no clean solution.

The pragmatic answer: a good enough, robust order that works across most programs, with cheap normalising passes interleaved to keep each heavy pass fed with clean IR.

LLVM and GCC organise optimisation as a sequence of passes driven by a pass manager. The -O level selects which passes run and how aggressively.

clang -O2 -mllvm -print-pipeline-passes
opt -passes='default<O2>' -print-after-all
gcc -O2 -fdump-tree-all -fdump-rtl-all

C and C++ declare some constructs undefined behaviour (UB): the standard imposes no requirements. The optimiser is then free to assume UB never happens — and to rewrite code on that assumption. This is a powerful, and famously controversial, source of speed.

// signed overflow is UB → compiler assumes
// it never happens → this loop terminates:
for (int i = 0; i <= n; i++) { ... }
// i+1 can't wrap, so i<=n is bounded → may
// use a wider IV, vectorise, hoist checks

int v = *p;       // deref → p assumed non-null
if (p) { ... }    // → branch can be deleted!