THE AVAILABLE EXPRESSIONS already computed on every path — do not compute twice
An expression like a+b is available at a point if it has been computed on every path to that point and none of its inputs changed since. Where an expression is available, recomputing it is waste — you can reuse the earlier value. It is a forward, must dataflow analysis: like reaching definitions but joined by intersection (available on ALL paths, not some), and a redefinition of any input kills every expression that used it. Available expressions is exactly the precondition that makes common-subexpression elimination legal.
THE TECHNIQUE available on ALL paths (intersection) → safe to reuse
Two expressions are computed; toggle whether an input is later redefined (which kills the expressions using it). The demo tracks the available set to the exit: live demo
HISTORY & CREDIT Cocke 1970 · Kildall 1973
“Compute it when you need it.” — if you already computed it on every path and nothing changed, needing it again is an illusion; the value is sitting there. Available-expression analysis is the compiler noticing the déjà vu precisely enough to act on it. cited
1970 · John Cocke — common-subexpression elimination via availability, on the flow graph. 1973 · Gary Kildall — casts it as a forward must dataflow problem: the same lattice framework, joined by intersection. now · the enabling analysis for CSE and partial-redundancy elimination in every optimizer.
Reaching definitions joins by union (reaches on some path); available expressions joins by intersection (safe on all paths). Same lattice, opposite meet — the framework's economy. Kildall 1973
RECOMMEND FOR I-13 available set at exit as a bitmask, computed
On the canonical compiler, with two expressions computed and no input redefined, both stay available — the set is {0,1} = bitmask 3:
$ i13 run avail.i13 # forward availability, no kill
a = 3 -- bits {0,1}: both a+b and a*c available at exit (CSE is legal for both)
Recommend:hold this pass back — it is the enabler for CSE, and CSE is exactly the kind of invisible rewrite i13's creed refuses (EXECUTION ≠ COMMIT). The value of availability to i13 is diagnostic, not transformational: it could warn “you computed a+b twice” (a waste-ledger note) without silently reusing it. Show the redundancy; let the author decide. The analysis is welcome; the automatic rewrite is not.