THE CSE compute (a+b) once, reuse it — when it is safe
When the same expression is computed more than once and its inputs have not changed between, a compiler can compute it once, store it in a temporary, and reuse the temporary — common-subexpression elimination. It is one of the oldest optimizations and it rides directly on available-expression analysis: reuse is legal exactly where the expression is available. The saving is real (fewer operations) but so is the cost: the value now lives in a temporary the programmer never wrote, and the ops that run no longer match the source.
THE TECHNIQUE k identical evaluations → 1 compute + (k−1) reuses
Set how many times a+b is used. Naively that is k evaluations; CSE computes it once and reuses, saving k−1: live demo
HISTORY & CREDIT John Cocke, 1970
“Writing a+b twice costs nothing; the compiler sees it.” — it costs a second evaluation unless a pass removes it, and removing it means introducing a value you never named. CSE is a genuine trade: fewer ops for a temporary and a source that no longer matches the run. cited
1969–70 · John Cocke & Jacob Schwartz — value numbering and common-subexpression elimination, foundational optimizing transforms. 1970 · John Cocke — “Global Common Subexpression Elimination”: systematic global CSE via available-expression analysis on the flow graph. now · local and global CSE (and GVN) in every optimizer; the canonical “compute once” win.
CSE is legal exactly where the expression is available, and worth it exactly where the temporary is cheaper than the recompute. Both are decisions the compiler makes on your behalf — usually invisibly. Cocke 1970
RECOMMEND FOR I-13 evaluations saved by reuse, computed
On the canonical compiler, computing a+b once (=12) and reusing it three times gives the same result with 2 evaluations saved:
$ i13 run cse.i13 # a+b computed once, reused 3x
t = 12
v = 36
saved = 2 -- 3 uses -> 1 evaluation + 2 reuses
Recommend:do NOT add automatic CSE to I-13 — and this is a design statement, not an oversight. i13's IVM lowers (a+b)*(a+b) to 8 ops that compute a+btwice, on purpose: the ops that run are the ops you wrote (EXECUTION ≠ COMMIT). CSE would insert a temporary you never named and a value you cannot see in the source — the opposite of a verifier's transparency. Offer it as a report (“this subexpression repeats”), never a silent rewrite.