12.2 Common Subexpression Elimination

Common subexpression elimination (CSE) avoids recomputing a value that is already available. If %v1 = add %a, %b has executed and neither its operands nor relevant semantics have changed, a later identical add can reuse %v1.

%v1 = add %a, %b
%v2 = mul %v1, 4
%v3 = add %a, %b   ; replace with %v1
%v4 = sub %v3, 1   ; becomes sub %v1, 1

The phrase “same expression” hides the hard part. The compiler must prove that both instructions compute the same value on every path reaching the second instruction.

Expression keys and value numbering

Local CSE can scan a basic block while maintaining a table from expression keys to previous results. An integer add key might include opcode, type, flags, and operand value numbers:

key = (add, i32, no_signed_wrap=false, VN(a), VN(b))

For commutative operations, canonicalizing operand order lets a + b match b + a. Reassociation such as matching (a + b) + c with a + (b + c) needs stronger algebraic permission: signed overflow rules and floating-point rounding may make the two forms different.

Global value numbering (GVN) assigns the same value number to expressions proved equivalent across blocks. In SSA form, operands already identify definitions clearly, and dominance answers whether an earlier result is available: the defining instruction must dominate the replacement use. A computation in only one side of a branch cannot normally replace a computation after the merge.

Calls, traps, and semantic flags

Two calls to random() are not common subexpressions. Calls may read time, allocate objects, perform I/O, throw, or inspect mutable memory. A call marked pure may be eligible for reuse when its arguments match; a readonly call still depends on the memory state it reads.

Potential trapping also matters. Reusing a dominating division may be valid because its trap, if any, already occurred on every path to the use. Hoisting a division to create a common expression is different: it may introduce a trap on a path where the source never evaluated it.

Memory-aware CSE

Loads cannot be keyed only by address text. In this sequence, the second load may see a different value:

%v1 = load p
store 7, q
%v2 = load p

If p and q may alias, the store invalidates the available value for p. If alias analysis proves they cannot refer to overlapping memory, %v2 may reuse %v1. A call that may write memory creates a similar barrier. Volatile and atomic loads carry additional ordering semantics and must not be removed like ordinary reads.

Compilers model this with alias sets, memory dependence, Memory SSA, or explicit memory value numbers. Conceptually, a load key includes both its address and the memory version:

(load, p, memory-version M0) != (load, p, memory-version M1)

Correctness and profitability

CSE is usually profitable, but not automatically. Reusing a value can extend its live range and increase register pressure; avoiding a cheap instruction may cause an expensive spill. It can also retain a large object or pointer longer than expected in managed runtimes.

A production pass therefore separates legality from profitability. Legality asks whether the replacement preserves types, values, effects, exceptions, and dominance. Profitability estimates instruction cost, live-range growth, code size, and target behavior. Tests should include branch merges, commuted operands, calls with different effect attributes, aliasing stores, volatile memory, and trapping expressions.