Common Subexpression Elimination

An expression `e` (such as `a + b`) is said to be available at a program point `p` if every path from the entry of the program to `p` computes `e`, and after that computation none of `e`'s operands has been redefined before reaching `p`. Availability is a classic must analysis: a fact holds at `p` only if it holds along every incoming path, which makes it safe to use at any point where it's certain to hold, regardless of which path execution actually took. Common Subexpression Elimination transforms the program by replacing an occurrence of an available expression `e` with a reference to a temporary variable that already holds `e`'s value — inserted at the point where `e` was first computed. The optimization has two flavors. Local CSE operates within a single basic block, using a simple scan and a table of already-computed expressions, since a basic block has no branches and therefore only one incoming "path" to reason about. Global CSE operates across an entire control-flow graph, and requires the full machinery of iterative data-flow analysis to compute availability, because a block may be reached from multiple predecessors whose computed expressions must all agree. A crucial companion notion is the kill of an expression: an assignment `x = ...` kills every expression that reads `x` as an operand, because after the assignment the old value of `x` may no longer match what those expressions would recompute. Getting kill sets right — including for indirect stores through pointers or array writes that may alias an expression's operands — is the single largest source of unsoundness in real CSE implementations, and is treated at length below.

Local CSE. Within one basic block, walk the statements top to bottom, maintaining a table mapping expression signatures (operator + operand values, not variable names) to the temporary that currently holds that value. On each assignment `x = y op z`: 1. Look up `y op z` in the table. If present and still valid, replace the computation with `x = t` where `t` is the stored temporary. 2. Otherwise compute it normally and record `y op z ↦ x` (or a fresh temp) in the table. 3. Invalidate (remove) any table entry whose operands include `x`, since `x` has just changed.

Global CSE requires knowing, for every block entry, the set of expressions available on all paths reaching that block. This is computed with a forward, must, iterative data-flow analysis over the lattice of expression sets ordered by superset-is-"more available" (intersection is meet). For each basic block `B`, define two local sets computed by a single forward scan of `B`:

• `e_gen(B)`: expressions computed in `B` whose operands are not subsequently redefined within `B` (i.e., they reach the block's exit still valid).
• `e_kill(B)`: expressions not in `e_gen(B)` that are killed somewhere in `B` because one of their operands is reassigned.

The data-flow equations are: ``` AvailOut(ENTRY) = ∅ for all blocks B ≠ ENTRY: AvailIn(B) = ⋂ over all predecessors P of B of AvailOut(P) AvailOut(B) = e_gen(B) ∪ (AvailIn(B) − e_kill(B)) ``` The meet is intersection (an expression is available only if available on every incoming path), reflecting the must-analysis nature of the problem. This is solved to a fixed point with the standard worklist algorithm. ``` ALGORITHM ComputeAvailableExpressions(CFG) U ← set of all expressions appearing in any assignment (the "universe") for each block B: compute e_gen(B), e_kill(B) by a single forward pass over B's statements AvailOut(B) ← U // optimistic initialization (needed for correctness of meet-over-paths) AvailOut(ENTRY) ← ∅ changed ← true while changed: changed ← false for each block B in CFG, B ≠ ENTRY: AvailIn(B) ← INTERSECT( AvailOut(P) for each predecessor P of B ) new_out ← e_gen(B) ∪ (AvailIn(B) − e_kill(B)) if new_out ≠ AvailOut(B): AvailOut(B) ← new_out changed ← true return AvailIn, AvailOut for every block

ALGORITHM ApplyCSE(CFG, AvailIn) for each block B, in any order: avail ← AvailIn(B) // expressions available at entry to B table ← map from expression to holding-temp, seeded from avail's known temps for each statement s = "x = y op z" in B, in order: e ← canonical form of (y op z) if e is a pure expression (no side effects) and e ∈ avail (or was computed earlier in this scan of B and not yet killed): t ← temp already holding value of e replace s with "x = t" else: emit s unchanged record that e is now held by x (or a fresh temp introduced at s) avail ← avail ∪ {e} // kill: remove from avail any expression that reads x avail ← { f ∈ avail : x is not an operand of f } ``` Two engineering details matter. First, `AvailOut` must be initialized to the universal set `U` (not empty) for all non-entry blocks before iteration begins, because the analysis takes a meet (intersection); starting from `U` guarantees the iteration only shrinks sets monotonically toward the correct fixed point (see Complexity & Correctness). Second, expressions must be canonicalized (e.g., recognize `a+b` and `b+a` as the same expression for commutative operators) so that textually different but semantically identical computations are still caught.

Notice in the figure that even though `B3` still has `a+b` available, `B4`'s incoming intersection with `B2` (which killed it) forces `AvailIn(B4) = ∅`. This is precisely why availability is a must, all-paths property: one path that invalidates the expression is enough to forbid reuse at the merge point, and `B4` must recompute `a+b` rather than reuse `t1`.

Time complexity. Let `n` be the number of basic blocks, `E` be the number of edges (predecessor links) in the CFG, and `k` be the number of distinct expressions (the size of the universe `U`). Each block's `e_gen`/`e_kill` computation is a single linear pass over its statements, costing `O(|B|)` total, or `O(m)` summed over all blocks, where `m` is the number of statements in the whole program. The iterative fixed-point computation represents each `AvailOut(B)` as a bit vector of length `k`. Because the lattice is the powerset of `U` ordered by inclusion, has height `k` (each strict shrink removes at least one bit), and the transfer function is monotone, the number of iterations of the outer `while` loop is bounded by `O(n·k)` in the worst case (each block's set can shrink at most `k` times). Each pass over all blocks costs `O(E·k / w)` bit-vector operations where `w` is machine word size (bitset intersection/union in `O(k/w)`), giving total worst-case time ``` O(n · k · E · k / w) = O(n · E · k² / w) ``` In practice, for reducible flow graphs the algorithm converges in `O(d)` passes where `d` is the loop-nesting depth (typically a small constant, rarely more than 3–5 for real code), making the practical cost close to `O(E·k/w)` — linear in the size of the flow graph times the number of expressions, which is why CSE is considered a cheap, "free" optimization pass. Local CSE inside a single block is simpler: one linear scan with a hash-table lookup per statement, giving `O(|B|)` expected time per block and `O(m)` overall.

Correctness argument. The desired specification is the meet-over-all-paths (MOP) solution: expression `e` should be considered available at block entry `B` exactly when every control-flow path from `ENTRY` to `B` computes `e` and does not subsequently kill it before reaching `B`. Two facts establish that the iterative algorithm computes this correctly (for the case that matters in practice — no analysis of an unreachable path is needed since MOP is only meaningful over realizable paths, and the standard CSE correctness argument uses the all-paths superset, which is safe even though it may be conservative for infeasible paths): 1. Monotonicity and termination. The transfer function `f_B(X) = e_gen(B) ∪ (X − e_kill(B))` is monotone: if `X ⊆ Y` then `f_B(X) ⊆ f_B(Y)`. Since every `AvailOut(B)` starts at the top element `U` and each update can only shrink sets (never grow them, because `e_gen(B) ∪ (X − e_kill(B)) ⊆ X` whenever `X ⊇ e_gen(B)`, an invariant preserved by induction from the initial `U`), the sequence of iterates is a decreasing chain in a finite lattice of height `k`. A decreasing chain in a finite lattice must stabilize, so the `while changed` loop terminates, and by the Knaster–Tarski fixed-point theorem it terminates at the greatest fixed point — which for a must-analysis is exactly the safe, conservative answer we want (an expression is claimed available only when it truly is, on every actual path). 2. Safety of the transformation. Suppose `e ∈ AvailIn(B)` when the algorithm terminates. By construction this means `e` survives the intersection over every predecessor's `AvailOut`, and by induction on path length, every control-flow path reaching `B` computed `e` and did not kill its operands afterward. Therefore, at runtime, whichever path execution actually took, the value of `e` currently held in memory (in the temp introduced at its computation) equals the value `e` would recompute to at `B`. Replacing the recomputation with a read of that temp changes no observable value the program computes — assuming the expression is pure (no side effects, no dependency on memory that could be aliased and unaccounted for in the kill sets). The caveat about purity and aliasing is not a footnote — it is the crux of soundness. If `e` reads through a pointer (`p + q`), the kill set must include every assignment that could possibly write to the memory `p` or `q` might point to, as determined by a points-to or alias analysis; without this, CSE can silently reuse a stale value and produce wrong output. The dataflow algorithm itself is agnostic to this — it is only as sound as the `e_gen`/`e_kill` sets fed into it.

Space complexity. Storing `AvailIn`/`AvailOut` bit vectors for every block costs `O(n·k/w)` words. The expression table for local CSE costs `O(k)` per block scan.

Take the flow graph from the figure, with statements: ``` ENTRY: B1: t1 = a + b B2: c = t1 2 a = 5 B3: d = t1 - 1 B4: e = a + b f = c + d ``` Universe of expressions `U = { a+b, t12, a-... , t1-1, c+d }` (simplify to the ones that recur: `a+b` is the interesting one, appearing in `B1` and again textually in `B4`). Step through the fixed-point computation:

At `B4`, the compiler evaluates `AvailIn(B4) = AvailOut(B2) ∩ AvailOut(B3) = ∅ ∩ {a+b} = ∅`. Even though `B3` alone would have permitted reuse, the must semantics of availability correctly forbids replacing `e = a + b` in `B4` with a reference to `t1`, because the path through `B2` reassigned `a` before reaching `B4`, so `t1`'s stored value no longer equals the current `a + b`. The compiler must recompute `a + b` at `B4`, exactly as the algorithm dictates — reusing it there would produce a silently wrong value on the `ENTRY→B1→B2→B4` path. Contrast this with a local CSE pass inside `B4` alone (ignoring inter-block flow): a naive local-only implementation that didn't consult global availability and instead just remembered "I saw `a+b` computed in `B1`" would incorrectly rewrite `e = a + b` to `e = t1`, producing a bug that only manifests when control passes through `B2`. This is exactly why global CSE cannot be built by na\"ively gluing together per-block local tables without running the full data-flow fixed point — the merge-point intersection is doing indispensable work.

The theoretical scaffolding for CSE — data-flow analysis over lattices, with availability as a canonical must-analysis — was formalized in the 1970s alongside the broader development of dataflow frameworks for optimizing compilers, most influentially systematized by Gary Kildall's lattice-theoretic formulation of global program analysis and later refined by John Cocke, Ken Kennedy, and collaborators who classified analyses into the may/must, forward/backward taxonomy still taught today.

Every production optimizing compiler runs a form of CSE. GCC's tree-SSA pipeline includes a dedicated pass (`tree-cse`/PRE, partial redundancy elimination, a generalization of CSE that also handles partially-available expressions). LLVM's `EarlyCSE` and `GVN` (Global Value Numbering) passes implement local and global common subexpression elimination respectively, the latter subsuming classic CSE by reasoning about value equivalence rather than pure syntax. JIT compilers such as HotSpot's C2 and V8's TurboFan run CSE-like passes at runtime, where the cost of the analysis itself matters because it happens during program execution rather than ahead of time — reinforcing why the near-linear practical complexity of the iterative algorithm is essential, not just a theoretical nicety. CSE is also foundational preparation for Loop Optimizations and Loop-Invariant Code Motion, since recognizing that a loop body recomputes the same expression on every iteration is a direct generalization of the same availability reasoning applied across loop-carried control flow, and both rely on the same Data-Flow Analysis Framework machinery, sharing lattice-based fixed-point computation with related passes like Reaching Definitions Analysis.

Ask the tutor: How does Partial Redundancy Elimination generalize CSE to handle expressions available on only some paths?