PARTIAL REDUNDANCY ELIMINATION redundant on some paths; hoist to make it redundant on all
An expression is fully redundant if it was already computed on every path to here, partially redundant if only on some. PRE inserts the computation on the paths that lack it — making it fully redundant — then removes it, so it runs exactly once on every path and never more than the original. One framework that subsumes common-subexpression elimination and loop-invariant code motion.
THE TECHNIQUE insert to complete the redundancy, then delete
Here a+b is computed twice on the then-path (fully redundant there) and once on the else-path. PRE hoists one copy before the branch so every path computes it once; the then-path drops from two to one, the else-path is unchanged. Count the evaluations: live demo
HISTORY & CREDIT Morel & Renvoise, CACM 1979
“PRE is just CSE.” — CSE only removes full redundancy. PRE’s move is insertion: it adds a computation where one is missing to complete a partial redundancy — which also captures loop-invariant code motion (the loop body is partially redundant with the pre-header). It strictly subsumes both. cited
1979 · Etienne Morel & Claude Renvoise — “Global Optimization by Suppression of Partial Redundancies” (CACM): the original bidirectional dataflow formulation. 1992 · Knoop, Rüthing & Steffen — “Lazy Code Motion” (PLDI): the optimal, unidirectional placement — computationally minimal and lifetime-minimal, no wasted register pressure. 1990s+ · SSA-based PRE (Chow, Kennedy et al.) — the form used in production compilers.
Optimal placement is a balance: hoist too far and you extend a value’s live range (register pressure); Lazy Code Motion hoists as late as possible while still killing the redundancy. Morel & Renvoise, 1979
RECOMMEND FOR I-13 one eval on every path
That the hoisted form computes the same result while evaluating a+b once per path holds on the canonical compiler:
$ i13 run pre.i13 # a+b twice on the then-path vs hoisted once
r_then = 26 h_then = 26 -- then-path: redundant(2 evals) == hoisted(1 eval)
r_else = 13 h_else = 13 -- else-path: unchanged, 1 eval each
Recommend: PRE is LIT in result and the strongest single redundancy pass for I-13 — verified the hoisted form matches the redundant form on both paths (26/26 then, 13/13 else) while cutting the then-path from two evaluations of a+b to one. Because one framework covers both CSE and loop-invariant motion, it is the pass to build after SSA (150) and GVN (152) rather than the two separately; use the Lazy-Code-Motion placement to avoid inflating live ranges.