The Principal Sources of Optimization

A correct compiler that emits naïve code is only half a compiler. The front end has faithfully translated the source into basic blocks and a flow graph, but that intermediate code is full of avoidable work: the same address computed three times in a row, a variable copied only to be read once, an expression whose value never changes recomputed on every trip round a loop. The optimizer is the middle end whose job is to make the program do less while computing exactly the same answer. This page is the catalogue — the "principal sources of optimization" from Chapter 9 of the Dragon Book — a menu of machine-independent transformations that pay off on essentially every target.

"Machine-independent" is the key phrase. These transformations reason about the program's meaning, not about how many registers your chip has or how deep its pipeline is. That comes later, in the back end. Here we ask only: is this computation redundant, dead, or movable? — and answer in a way that would help an ARM, an x86 and a RISC-V equally.

The two questions every optimization must pass

Before we list the transformations, internalise the framing that governs all of them. An optimization is a rewrite of the program, and every rewrite must clear two hurdles, in order:

Safety (semantics preservation). The rewritten program must compute the same observable result as the original on every input and every control-flow path. This is a hard constraint — a "faster" program that is sometimes wrong is not an optimization, it is a bug.
Profitability. Given that it is safe, the rewrite should actually make the program better — fewer instructions, fewer cycles, less memory traffic. Profitability is a heuristic, often target-dependent, and occasionally a transformation is safe but not worth doing.

Safety is where the dataflow analyses earn their keep: they are the proofs that a rewrite is legal. Profitability is where cost models and heuristics live. Keep the two separate in your mind — conflating them is the classic student mistake, and the subject of this page's "Watch out!" below.

The catalogue

Here are the workhorse transformations. Each is defined by a local pattern it matches and a rewrite it applies; several depend on a supporting analysis to prove safety.

Transformation	What it does	Before → after
Common-subexpression elimination (CSE)	Reuse a value already computed instead of recomputing it.	`t1=b+c; … t2=b+c` → `t1=b+c; … t2=t1`
Copy propagation	After `x=y`, replace later uses of `x` with `y`.	`x=y; z=x+1` → `x=y; z=y+1`
Constant folding	Evaluate a constant expression at compile time.	`t=3*4` → `t=12`
Constant propagation	Substitute a variable known to hold a constant.	`x=5; y=x+2` → `x=5; y=7`
Dead-code elimination (DCE)	Delete a computation whose result is never used.	`x=y+z; // x unused` → (removed)
Code motion (loop-invariant)	Hoist a computation that does not change inside a loop to just before it.	`while(…){ t=ab; … }` → `t=ab; while(…){ … }`
Strength reduction	Replace an expensive operation with a cheaper equivalent.	`i*4` in a loop → running add `t=t+4`
Induction-variable elimination	Remove a loop variable derived from another by keeping only one counter.	drop `j=i*4`, iterate the address directly

These do not act in isolation — they feed one another. Constant propagation exposes constant folding; folding and copy propagation expose more dead code; removing dead code frees a register that lets another value live. This is why real optimizers run passes to a fixed point, cycling until nothing more changes.

Three scopes: local, global, and loop

The same transformation costs different amounts of analysis depending on how far you look:

Local — within a single basic block. No control flow to worry about; a straight line of instructions. CSE, copy propagation and DCE inside one block need nothing more than a walk over the block, and are elegantly captured by the DAG of a basic block.
Global — across the whole flow graph of a procedure. Now a value defined in one block may or may not reach a use in another, depending on the paths between them. Proving safety requires dataflow analysis — reaching definitions, available expressions, live variables.
Loop — the special, high-value case of global optimization that focuses on cycles in the flow graph. Loop-invariant code motion, strength reduction and induction-variable elimination all live here.

Why loops get all the attention: the 90/10 rule

Optimizers pour a disproportionate effort into loops, and the justification is empirical and blunt: a program typically spends about 90% of its running time in about 10% of its code, and that hot 10% is almost always inside loops. A statement in the body of a doubly-nested loop that runs n times each may execute n^2 times per call; shaving one operation off it is worth far more than removing a hundred operations from straight-line setup code that runs once.

\text{payoff} \;\approx\; (\text{ops saved per execution}) \times (\text{execution frequency}).

The frequency factor is enormous inside loops and tiny outside them, so the arithmetic settles the priorities. Hoisting one loop-invariant multiply out of a loop that runs a million times removes a million multiplies; folding a constant in start-up code removes one. Both are safe; only the first is seriously profitable. This is the profitability half of our framing made concrete.

Worked example: cleaning up a basic block

Take a short block and apply the local transformations by hand, then let the code do the same. Start with this three-address code:

a = 3 b = 4 t1 = a * b // both operands constant c = t1 t2 = c + a // c is a copy of t1 d = t2

Constant propagation + folding: a=3, b=4 so t1 = 3*4 = 12. Copy propagation: c is just t1, so t2 = t1 + a = 12 + 3 = 15, and d = 15. If a, b, c, t1, t2 turn out to be unused afterwards, dead-code elimination deletes them, leaving only what the block's live outputs need. The runnable version below performs constant folding and copy propagation on exactly this style of block:

// A tiny three-address instruction: dst = a op b, or a plain copy dst = a. type Instr = { dst: string; a: string; op?: "+" | "*"; b?: string }; function isConst(s: string): boolean { return /^-?\d+$/.test(s); } // Apply constant folding + constant/copy propagation over a straight-line block. function optimize(block: Instr[]): Instr[] { const known = new Map<string, string>(); // var -> constant literal OR the var it copies const out: Instr[] = []; const resolve = (s: string): string => { // Follow copy/constant chains until we hit a literal or an unknown var. let seen = new Set<string>(); while (known.has(s) && !seen.has(s)) { seen.add(s); s = known.get(s)!; } return s; }; for (const ins of block) { const a = resolve(ins.a); if (ins.op === undefined) { // copy: dst = a known.set(ins.dst, a); out.push({ dst: ins.dst, a }); continue; } const b = resolve(ins.b!); if (isConst(a) && isConst(b)) { // constant folding const v = ins.op === "+" ? +a + +b : +a * +b; known.set(ins.dst, String(v)); out.push({ dst: ins.dst, a: String(v) }); } else { known.delete(ins.dst); out.push({ dst: ins.dst, a, op: ins.op, b }); } } return out; } const block: Instr[] = [ { dst: "a", a: "3" }, { dst: "b", a: "4" }, { dst: "t1", a: "a", op: "*", b: "b" }, { dst: "c", a: "t1" }, { dst: "t2", a: "c", op: "+", b: "a" }, { dst: "d", a: "t2" }, ]; for (const ins of optimize(block)) { const rhs = ins.op ? `${ins.a} ${ins.op} ${ins.b}` : ins.a; console.log(`${ins.dst} = ${rhs}`); }

Every right-hand side collapses to a literal: the optimizer has folded and propagated its way to d = 15 without ever running the program. A following dead-code pass would then sweep away any of these assignments whose targets are not live on exit.

Not blindly. Optimizations that are perfectly safe under the language's abstract semantics can still surprise you. Floating-point arithmetic is not associative, so reordering (a+b)+c to a+(b+c) — tempting for a scheduler — can change the last bit of a result; compilers keep this behind a -ffast-math-style flag for exactly this reason. Aggressive elimination of a "dead" store to a security-sensitive buffer can leave a password in memory. And heavy inlining trades speed for code size, which can hurt if it blows the instruction cache. The catalogue tells you what is legal; judgement and cost models tell you what is wise.

The single most dangerous habit is to spot a "faster" rewrite and apply it because it looks like a win, without first proving it preserves meaning. Consider hoisting t = a[i] out of a loop because it looks invariant — but if the loop writes to a or to a pointer that might alias a, the load is not invariant and hoisting it changes the answer. Profitability can never buy back a lost correctness: an optimization that is 10× faster and occasionally wrong has negative value. Always run the analysis that establishes safety before you reach for the cost model. Every transformation in the catalogue has a matching safety condition; know it before you apply the rewrite.