Common Subexpression Elimination
Compute `a * b` once and reuse it — but only when the earlier computation dominates the later one, so the value is guaranteed available on every path that reaches the reuse. Over registers this is easy; over memory it needs alias analysis, which is why the two are different problems.
The same expression appears twice. Why does the compiler sometimes reuse the first result and sometimes not?
SSA over a control-flow graph, with a dominator tree computed alongside. The CFG is what makes "is this value available here?" a graph question rather than a textual one, and dominance is the specific graph property that answers it. Without the dominator tree the pass cannot be written correctly, which is why [[dominators]] is a prerequisite and not a detail.
Two instructions compute the same pure operation on the same operands, and the first dominates the second. Dominance is the guarantee: every path from the entry to the later instruction passes through the earlier one, so the earlier value has definitely been computed. AtlasLang additionally refuses any instruction where mayTrap is true, because reusing a division means the second division no longer executes, and if the first one faulted the program never got there anyway — but if the *second* would have faulted on different operands, they were not the same expression.
Key points
- The precondition is dominance, not textual identity: the earlier computation must be on every path to the later one.
- In SSA the operands cannot have changed, which is most of why CSE over registers is easy and why SSA exists —
[[why-ssa-helps]]. - CSE over memory is a different problem, gated entirely on alias analysis, and is the single most common place a compiler leaves obvious-looking work on the table.
- Commutative operands must be normalised or half the redundancies are missed.
- CSE only rewrites uses; deleting the now-userless instruction is dead code elimination's job, and separating them keeps both passes simple.
Textual identity is not the condition; dominance is
The naive statement of CSE is "if you see the same expression twice, keep the first result". That is wrong in a way that a straight-line example can never show, because in straight-line code the earlier instruction always dominates the later one. Control flow is where it breaks.
The value from an earlier block is usable at a later block only if control cannot arrive at the later block without having passed through the earlier one. That is precisely the definition of dominance, and it is why every real CSE implementation carries a dominator tree — AtlasLang computes one with computeDominance and walks blocks in reverse post-order so that a dominating definition is always seen before its dominated uses.
The CFG below is the case that matters. %1 and %2 compute the same thing on the same operands, and %3 computes it a third time at the merge. Neither %1 nor %2 dominates %3 — control can reach b3 through either arm — so neither is available there, and CSE must leave %3 alone.
%3 cannot reuse %1 or %2, even though all three are the same expression- b0entryentry
%a = param 0 %b = param 1 branch %c ? b1 : b2
- b1then
%1 = int %a * %b
Computed only on this path. - b2else
%2 = int %a * %b
Computed only on that path. - b3merge
%3 = int %a * %b print %3
Reachable from both. Neither %1 nor %2 is available on every incoming path.
- b0→b1
- b0→b2
- b1→b3
- b2→b3
- b1idomb0
- b2idomb0
- b3idomb0
Read it asThe immediate dominator of b3 is b0, not b1 or b2 — that single fact is the whole answer. A CSE that reused %1 in b3 would read an undefined register whenever control took the else arm, which register allocation would then turn into whatever happened to be in that physical register. The correct fix is not CSE at all: hoist the expression into b0, which is what partial redundancy elimination and [[loop-invariant-code-motion]] do, and then b3's copy really is redundant.
When it does apply, the rewrite is trivial
Once dominance holds, the transformation is a substitution: every use of the later result is rewritten to the earlier register, and the later instruction is deleted for having no users — which is [[dead-code-elimination]]'s job, not CSE's. AtlasLang splits it exactly that way: CSE records a replacement map and rewrites uses, then filters out the instructions whose destinations it replaced.
One detail that is easy to get wrong: commutative operators need their operands normalised, or a + b and b + a hash to different keys and the redundancy is missed. AtlasLang normalises +, *, == and != by sorting the two operand keys. That is a cheap trick with a real payoff, and forgetting it is the usual reason a CSE implementation finds less than expected.
%1 = int %a * %b %2 = int %1 + 1 %3 = int %b * %a %4 = int %3 + 2 print %4
%1 = int %a * %b %2 = int %1 + 1 %4 = int %1 + 2 print %4
Both multiplications are pure, cannot trap, and have the same operands after commutative normalisation; %1 dominates %3 trivially because they are in the same block with %1 first, and neither %a nor %b can have changed, because in SSA nothing is ever reassigned.
The operands may have changed between the two computations, or the operation reads memory. %1 = load @p followed by a store to something that might be @p and then %3 = load @p is not a common subexpression — the second load may see a different value. Establishing that it cannot is [[alias-analysis]], which is why CSE over memory is a different and much harder pass than CSE over registers.
Registers are easy; memory is the whole problem
CSE over values in registers is close to free, because SSA guarantees that a register's definition is unique and immutable. The moment the expression reads memory, none of that holds. p->x + p->x looks like an obvious redundancy and is not one if anything between the two reads might have written to p->x — another thread, a call, a store through a pointer the compiler cannot rule out as aliasing.
This is the reason a C compiler often reloads a field inside a loop that visibly cannot change it, and the reason restrict exists. It is also why the same code in Rust optimizes better without any annotation: the borrow checker has already proved the aliasing property that the C compiler is forced to assume the worst about — [[ownership-types]].
Value numbering generalises CSE by giving every value a number such that provably-equal values share a number, which finds redundancies that operand-by-operand matching misses: a + b and b + a after normalisation, but also x where x = y and y + 0. Global value numbering does it across the whole function using the dominator tree; it is strictly stronger and strictly more expensive.
| Situation | Eliminated? | What has to be true |
|---|---|---|
a * b twice, same block, SSA registers | Yes | Dominance is trivial and SSA guarantees the operands are unchanged. |
Same expression in two arms of an if | No, as written | Neither dominates the merge. Hoisting into the predecessor first makes it redundant — a different transformation. |
p->x twice with a call in between | Usually not | The call may write through p. Needs the callee proved not to touch that memory — [[interprocedural-analysis]]. |
p->x twice with a store to q->y in betweenspec | Only with alias information | p and q must be proved not to alias. restrict, type-based rules or Rust's ownership all supply this differently — [[alias-analysis]]. |
How it works
The steps, in the order the compiler takes them.
- Compute the dominator tree and a reverse post-order over the blocks, so every block is visited after all the blocks that dominate it.
- Maintain a map from an expression key — operator plus operand identities, with commutative operands sorted — to the block and register that first computed it.
- For each pure, non-trapping instruction, look up its key. If a prior entry exists and its block dominates the current block, record a replacement from this destination to the prior register.
- If no dominating prior entry exists, insert this instruction as the available definition for that key.
- After the walk, rewrite every use through the replacement map and drop the instructions whose destinations were replaced.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- A value is reused on a path where it was never computed, and the program reads whatever the register happened to hold. The symptom is a wrong answer that changes when unrelated code changes, because it depends on the register allocator's choices.
- A memory load is reused across a write that did alias, and a program reads a stale value — the classic strict-aliasing miscompilation, which typically shows up only at
-O2and only in one function. - CSE finds far less than expected because commutative operands were not normalised, and the engineer concludes the compiler is weak when the implementation has a one-line gap.
- Reuse extends a value's live range across a large region, register pressure rises, and the allocator spills. The generated code has fewer multiplies and more memory traffic, and is slower — visible as a benchmark that regresses when an optimization is added.
When it helps
- Address computations: indexing expressions like
base + i * striderecur constantly after lowering and are the largest single source of eliminable redundancy in real code. - Code produced by inlining and macro expansion, where the same subexpression is written repeatedly by different pieces of source that did not know about each other.
- Anything where the expression is genuinely expensive — a division, a call to a function proved pure — and computing it twice is a measurable cost.
When it hurts
- When the eliminated expression was cheaper than keeping its result alive. A recomputed integer add costs one cycle; a spilled value costs a store and a load. This is exactly the trade that
[[coalescing-and-rematerialization]]runs in the opposite direction. - In loops where the reuse spans an iteration boundary and forces a value to live across the back edge, increasing pressure at the point where pressure hurts most.
What it costs
Every one of these is paid by something.
- CSE buys removed computation and pays in register pressure: every reused value must stay live from its definition to its last reuse, and the allocator may spill it — trading arithmetic for memory traffic, which on a modern core is usually a bad trade.
- Global value numbering finds strictly more redundancy than dominance-based CSE and costs substantially more compile time and implementation complexity — the reason LLVM ships both EarlyCSE and GVN and runs the cheap one more often.
- Extending CSE to memory buys the redundancies that actually matter in pointer-heavy code and costs a whole alias analysis, whose precision is itself a compile-time-versus-quality dial.
What else you could do
What a different compiler or language does instead, and when that is better.
- Global value numbering assigns numbers to provably-equal values rather than matching expressions syntactically, catching equivalences CSE misses, at higher cost.
- Partial redundancy elimination handles the case CSE cannot: an expression computed on some paths but not all, which PRE fixes by inserting a computation on the missing paths and then reusing everywhere. It subsumes both CSE and loop-invariant hoisting and is considerably harder to implement.
- Rematerialization goes the other way — recompute a cheap value instead of keeping it in a register — and is the right answer whenever the value is cheaper than a spill slot.
- Do it in the source. Hoisting a repeated subexpression into a local is free, portable across compilers, and does not depend on the optimizer proving anything — at the cost of source that reads less directly.
See it for yourself
The flag, dump or tool that shows you this directly.
- Toggle common-subexpression elimination alone at
/compilers/passesand watch the replacement map take effect while the dominator tree stays visible in the CFG panel. - LLVM:
opt -passes=early-cse -Sversusopt -passes=gvn -Son the same IR shows the difference between the cheap and the strong version directly. - GCC:
-fdump-tree-fre-details(full redundancy elimination) and-fdump-tree-pre-detailsprint what each proved. clang -O2 -Son a function that reads the same struct field twice with a call in between, then again with the call removed, is the fastest demonstration that this pass is gated on aliasing.- Compile the same code in Rust and in C with equivalent pointers and diff the assembly: the redundant reloads that survive in C usually do not survive in Rust.
Plausible wrong readings
Stated the way a confident engineer states them.
- "The compiler will not compute the same thing twice." It will, whenever it cannot prove the operands are unchanged — which for anything reading memory is most of the time.
- "CSE always makes the code faster." It converts computation into a live value. If that value spills, the trade is arithmetic for memory traffic and the code is slower.
- "The same expression in both arms of an if will be shared." Neither arm dominates the merge, so nothing is shared without first hoisting the expression above the branch — a different transformation with a different legality condition.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
If the compiler has already worked out a * b, it can use that answer again instead of multiplying twice. The condition is that the first multiplication definitely happened before it gets to the second one — on every possible route through the function, not just the one you are looking at.
practical
When you see a redundant-looking reload survive optimization, the question is almost never "is my compiler bad" and almost always "what could have written to that memory in between". A call it cannot see into, a store through a pointer it cannot rule out, or a shared variable another thread might touch will all block it. restrict, const, and hoisting the value into a local yourself are the three practical answers.
advanced
CSE, loop-invariant hoisting and partial redundancy elimination are the same problem at three strengths. PRE is the general formulation: an expression is partially redundant if it is available on some paths, and the fix is to insert it on the paths where it is not, converting partial redundancy into full redundancy which is then eliminable. Lazy code motion is the classic formulation, computed as four data-flow analyses over [[available-expressions]] and anticipability, and it places every computation at the earliest point that does not lengthen any live range unnecessarily — which is why it subsumes hoisting as a special case rather than being a separate pass.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
restrict in C, type-based aliasing rules in C and C++, ownership in Rust, and the absence of pointer arithmetic in Java. Carrying an expectation across languages is the usual mistake.If you were asked this in an interview
- What has to be true about two identical expressions before a compiler can keep only the first result?
- Why is eliminating a redundant load much harder than eliminating a redundant multiply?
- Give me a case where common subexpression elimination makes the generated code slower.