Available Expressions
Has this expression already been computed on *every* path to here, with no operand changed since? A forward, must analysis with intersection at merges — and the precondition without which `[[common-subexpression-elimination]]` is a miscompilation.
When is it safe to reuse a value the program already computed, instead of computing it again?
The CFG annotated with, at every program point, the set of expressions whose value is already in hand — computed on every path reaching this point, and not invalidated since by an assignment to an operand. It exists to answer the precondition of redundancy elimination: *is this computation redundant here?* Note what a fact is: an expression, like a + b, not a value and not a variable.
Reusing a previously computed value is legal only if the expression is available on *every* path to this point — hence intersection at merges — and only if the expression is pure: no side effects, no dependence on memory that may have been written, and no possibility of trapping differently. Availability on some paths and not others is the specific error that miscompiles: the reused register holds a value computed on a path that was not taken, or holds nothing meaningful at all. The analysis is entitled to assume nothing about memory unless an alias analysis supplies it; a store to an unknown location invalidates every expression that reads memory.
Key points
- An expression is available if it is computed on every path to this point and no operand has changed since.
- It is a forward *must* analysis, so the meet is intersection and non-entry blocks initialise to the full set.
- The direction of unsafe error flips: claiming availability that does not hold is a miscompilation, not a lost optimization.
- Facts are expressions, not values, and an assignment to any operand kills every expression mentioning it.
- Memory is the hard half: without alias analysis, one store kills every memory-reading expression.
- Under SSA, dominance replaces the analysis for register expressions — the first computation dominating the second means it happened on every path.
- Eliminating a computation extends a live range, so it trades instructions for register pressure and is not unconditionally a win.
A must analysis, and why that changes everything
The three analyses before this one were all *may* analyses: something is true if it is true on some path, so the meet is union and the errors are over-approximations. Available expressions is the opposite. An expression is available only if it was computed on *every* path here, so the meet is intersection, the errors are under-approximations, and both the initialisation and the failure modes flip.
The consequence for initialisation is easy to get wrong and produces a silent, harmless-looking bug. Non-entry blocks must start with the *full* set of expressions, not the empty set, because the identity element for intersection is the universe. Start them empty and the first meet produces empty, the fixed point is reached in one round, and the analysis reports that nothing is ever available — which is sound, so nothing breaks, and CSE simply never fires again.
The consequence for correctness is the reverse of a may analysis. Claiming an expression is unavailable when it is available loses an optimization. Claiming it is available when it is not reuses a register that does not hold what you think it does, and the program computes with garbage.
1direction forward2meet intersection ("computed on EVERY path")3facts a set of expressions, e.g. { a+b, x*2 }4 5gen[B] expressions computed in B whose operands are not6 assigned later in B7kill[B] every expression mentioning a variable B assigns8in[B] intersection over predecessors P of out[P]9out[B] gen[B] union (in[B] minus kill[B])10 11boundary in[entry] = {} -- nothing computed yet12init in[B] = ALL -- identity for intersectionThe two initialisations differ, and that is not a detail. The entry block genuinely has nothing available; every other block starts optimistic and is cut down by the meet.
Kill is the interesting half
What makes an expression stop being available is an assignment to one of its operands. Compute a + b, then assign to a, and the stored value no longer corresponds to the expression — so a + b is killed. That is the whole kill rule for register operands, and it is why the analysis tracks expressions rather than values.
Memory is where this gets hard and where the honest limits are. If the expression reads memory — *p + 1, or a field load — then any store that may write that location kills it. Without alias analysis, "may write that location" means "any store at all", and a single store invalidates every memory-reading expression in the set. A call to an unknown function is worse: it may write anything, so it kills everything that touches memory.
This asymmetry is why CSE over registers is routine and CSE over memory is a research-grade problem. [[alias-analysis]] is precisely the input that makes the memory half tractable, and its absence is the reason a compiler will happily recompute a field load you can see is redundant.
- b0entryentry
t1 = a + b branch c ? b1 : b2
out = { a+b } - b1then
a = a + 1
assigning a kills a+b: out = {} - b2else
; nothing
out = { a+b } - b3join
t2 = a + b
in = {} intersect { a+b } = {} — recomputation is required
- b0→b1
- b0→b2
- b1→b3
- b2→b3
- b0idomb0(entry)
- b1idomb0
- b2idomb0
- b3idomb0
Read it asThis is the exact program that a union meet would miscompile. Under union, a + b would be reported available at b3 because it survived the b2 path, CSE would replace t2 with t1, and on the b1 path the answer would be computed from the old a. The intersection is not conservatism for its own sake — it is the difference between correct and wrong.
The transformation it licenses
With availability in hand, common subexpression elimination is mechanical: at each expression, if it is already available, replace the computation with a reference to the value that computed it. In practice the compiler has to have *kept* that value somewhere, which usually means CSE introduces a temporary at the earlier site and rewrites both.
Our own optimizer states the SSA version of the legality condition differently, and the difference is instructive: *two instructions compute the same pure operation on the same operands, and the first dominates the second. Dominance is what guarantees the earlier value is available on every path that reaches the later one.* Under SSA, dominance replaces the availability analysis for register expressions — if the first computation dominates the second, it happened on every path, which is exactly what availability was computing.
That is the same trade as reaching definitions: SSA absorbs the analysis for values and leaves it intact for memory. Global value numbering generalises further, treating expressions as equal when they are provably equal rather than syntactically identical, so a + b and b + a can be recognised as the same and a value copied through several names can be tracked. [[common-subexpression-elimination]] covers what to do with the result.
t1 = a + b ... t2 = a + b use t2
t1 = a + b ... use t1
The expression must be available at the second site: computed on every path reaching it, with no operand assigned in between on any path, and the value still held somewhere. The operation must be pure — no side effects, no observable memory access, and no possibility of trapping on operands that differ. In SSA the first two conditions collapse into "the first computation dominates the second", because operands cannot be reassigned.
An operand is assigned on any path between the two sites, so the expressions no longer denote the same value. Or the expression reads memory that a store or a call may have written in between — establishing that it did not requires alias analysis. Or the operation can trap: eliminating the second of two divisions is fine, but hoisting a division to a point where the divisor might be zero on some path introduces a fault the original program did not have.
What reuse actually costs
It is worth resisting the assumption that eliminating a computation is always an improvement. Reusing a value means keeping it alive from the first computation to the last reuse, which extends its live range — and a longer live range means more interference, which under pressure means a spill. A spill turns a register access into two memory accesses, which on a cheap operation is a straightforward loss.
This is a real and common trade, not a theoretical caveat. Recomputing an addition is often cheaper than keeping it in a register across a call, which is why [[coalescing-and-rematerialization]] exists and why some compilers deliberately re-materialise cheap values rather than spill them. The right mental model is that CSE trades instructions for register pressure, and the exchange rate depends on the target and on how many registers are already in use.
The related transformation worth knowing is partial redundancy elimination, which handles the case where an expression is available on *some* paths: it inserts a computation on the paths that lack it, making it fully available, and then eliminates the redundant one. That subsumes both CSE and loop-invariant code motion, and it needs availability plus a backward *anticipability* analysis — the pairing described in [[forward-vs-backward-analysis]].
How it works
The steps, in the order the compiler takes them.
- Enumerate the expressions in the function, and for each block compute
gen— expressions computed here whose operands are not reassigned later in the block — andkill— every expression mentioning a variable this block assigns. - Initialise the entry block's incoming set to empty, and every other block's to the full set of expressions.
- Iterate forward: the incoming set is the intersection over predecessors' outgoing sets; the outgoing set is
genplus the incoming set minuskill. - For memory-reading expressions, use alias analysis to decide which stores kill which expressions; conservatively, any store kills all of them.
- Stop at the fixed point, then walk the instructions: an expression already in the incoming set at its site is redundant.
- Introduce a temporary at the earlier computation if one does not already exist, and rewrite the redundant site to use it.
- Re-check register pressure: if the extended live range causes a spill, the elimination may be worse than the recomputation.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- The meet is union instead of intersection. An expression available on only one arm of a branch is reused on both, and the program computes with a value from a path it did not take — wrong on one branch only.
- Non-entry blocks are initialised empty. The analysis converges immediately to "nothing is available", CSE stops firing entirely, and the only symptom is code that is slower than the same compiler used to produce.
killmisses a call. An expression reading memory survives a call that wrote it, and the reused value is stale — correct until the callee actually writes, so it survives most testing.- An expression that can trap is treated as pure and reused after being hoisted. A division that could not have executed on this path now does, and a fault appears where the source had none.
- CSE fires aggressively under high register pressure and the extended live ranges force spills. The generated code has fewer arithmetic instructions and more memory traffic, and is measurably slower — a regression that looks like an improvement in an instruction count.
When it helps
- Code with repeated address computations and repeated arithmetic, especially array indexing lowered to explicit multiplication and addition, where the same subexpression appears many times per loop body.
- After inlining, which brings identical computations from caller and callee into one function where they can finally be seen as redundant — one of the main second-order benefits of
[[inlining]]. - As a component of partial redundancy elimination and loop-invariant code motion, where availability is one of the two analyses required.
When it hurts
- Under high register pressure, where keeping the value alive costs more than recomputing it. Cheap operations on a machine with few registers are the clearest case.
- On memory-heavy code without alias analysis, where the kill sets are so conservative that almost nothing stays available and the analysis pays for itself with nothing.
- For operations that may trap or have effects, where the purity precondition rules out most of the interesting candidates and the analysis finds only the easy ones.
What it costs
Every one of these is paid by something.
- Reuse buys fewer instructions; it pays register pressure directly, because the value must stay live between the two sites, and under pressure that converts into spill code that costs more than the instructions saved.
- Intersection buys correctness at merges; it pays every partially-redundant case, where the expression really was available on most paths and the analysis reports nothing — recovering those is PRE, which costs a second analysis and inserted computations.
- Tracking expressions syntactically buys a simple, cheap analysis; it pays every case where the same value is spelled differently —
a + bversusb + a, or a value copied through a temporary — which is what global value numbering costs more to catch. - Conservative memory kills buy soundness without alias analysis; they pay nearly all the availability in pointer-heavy code, which is why the analysis appears to do so little on real C++ compared with the textbook examples.
What else you could do
What a different compiler or language does instead, and when that is better.
- Global value numbering over SSA, which assigns a number to each value such that provably-equal values share a number. It catches commutativity and copy chains that syntactic availability misses, and is what most production compilers actually run.
- Partial redundancy elimination, which inserts computations on paths that lack them so that a partially-available expression becomes fully available. It subsumes CSE and loop-invariant code motion, and costs an extra backward analysis plus inserted code.
- Local CSE within a basic block only, using a hash table from expression to value. No data-flow analysis at all, catches the majority of easy cases, and is cheap enough for a fast compilation tier.
- Rematerialisation instead of reuse: deliberately recompute a cheap value at each use rather than keep it live. Under pressure this is the better trade, and a good allocator makes the decision with pressure information the middle-end did not have.
See it for yourself
The flag, dump or tool that shows you this directly.
opt -passes=gvn -S t.llruns global value numbering alone, which is the transformation this analysis licenses, in its modern form.opt -passes=early-cse -S t.llruns the cheap local version, so you can see how much is caught without any data-flow analysis at all.gcc -fdump-tree-preshows partial redundancy elimination, including the computations it inserted to make an expression fully available.- Compare
-fno-tree-preagainst the default on a loop with a repeated address computation, and read the assembly: the difference is exactly this analysis and its consumers.
Plausible wrong readings
Stated the way a confident engineer states them.
- "The expression appears twice, so the second one is redundant." Only if it is available — computed on every path, with no operand changed since, and the value still held.
- "Available means the value is in a register." It means the value has been computed. Keeping it somewhere is a separate obligation, and it is the obligation that costs register pressure.
- "CSE always makes the code faster." It removes instructions and adds pressure. Under a tight register budget the exchange can go the wrong way, and measuring is the only way to know.
- "SSA makes this analysis unnecessary." It replaces it for register expressions, where dominance gives availability. Memory still needs it, and memory is where most real redundancy lives.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
An expression is available at a point if the program has already computed it on every way of getting there, and nothing it depends on has changed since. That is the condition under which the earlier result can be reused instead of computing it again. Because it must hold on every path, merging two paths takes the intersection of what each had available.
practical
When a compiler fails to eliminate a redundancy you can see with your own eyes, the usual reasons are in this lesson. An operand was assigned on some path you did not think about. The expression reads memory and a store or a call in between could not be ruled out. Or the two spellings differ — a + b and b + a, or one goes through a temporary — and the compiler is matching syntax rather than value. Checking those three in order is faster than reading the optimizer.
advanced
The relationship between this analysis and its modern replacement is worth being precise about. Availability answers "is this expression already computed here"; dominance in SSA answers "did this instruction definitely execute before that one". They coincide for pure register expressions, which is why an SSA compiler can drop the analysis, and they come apart for memory, where executing earlier does not mean the value is still valid. That is the whole reason MemorySSA exists: it re-establishes the dominance shortcut for loads by giving memory versions and phis of its own, so that "this load is dominated by that one and the memory version is the same" becomes a legal substitute for an availability analysis. Partial redundancy elimination sits above all of this, combining availability with anticipability to place a computation at the earliest point where it is needed on every subsequent path and not yet available — which turns out to subsume loop-invariant code motion as a special case, since a loop-invariant expression is partially redundant on the second and later iterations.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
a + b and b + a are different facts. Real implementations canonicalise operand order first, and value numbering goes further by tracking equality rather than syntax.src/compilers/sim/optimize.ts is that the first instruction computes the same pure operation and dominates the second. It handles registers only; AtlasLang has no pointers, so the memory half of this lesson has no counterpart in our engine.If you were asked this in an interview
- Why is the meet for available expressions intersection rather than union? Give a program that breaks under union.
- What must non-entry blocks be initialised to, and what happens if you get it wrong?
- Under SSA, what replaces this analysis for register expressions, and why does the replacement not work for memory?
- Name a case where eliminating a redundant computation makes the program slower.
Connections
- Observability & Performance Engineering — Measuring whether an optimization actually helpedThis transformation trades instruction count against register pressure, and instruction count is the thing that is easy to see. Deciding which way the trade went on a real workload is a measurement problem owned there.