Lesson 17.6 — Partial redundancy elimination: Morel–Renvoise, lazy code motion, SSAPRE, GVN-PRE, load PRE¶
Techniques: Morel–Renvoise bidirectional PRE (1979); lazy code motion (Knoop–Rüthing–Steffen 1992/94) in the edge form of Drechsler–Stadel (1993), with computational and lifetime optimality; SSAPRE (Chow et al. 1997; Kennedy et al. 1999); GVN-PRE (VanDrunen–Hosking 2004); LLVM GVN's load PRE · Pebble implements: ★ lazy code motion on Chapter 8's TAC in
labs/ch17-lcm, checked against the Python oracle; the drilllcm-sets· Prerequisites: available and very busy (anticipable) expressions (Lesson 14.3); Lesson 17.4 · Time: 7–9 hours
1. Problem and motivation¶
Lessons 17.4 and 17.5 delete full redundancies: computations whose value is available on every path. Most redundancy in real code is partial: available on some paths only. The running example of this lesson is the smallest one, the diamond (as a Ch 14 three-address program; if only uses its operands):
flowchart TD
A([A: if p < q]) -->|T| B["B: x = a + b"]
A -->|F| C[C]
B --> D["D: y = a + b<br/>ret y"]
C --> DOn the path through B, a + b in D recomputes a known value; through C it does not. Partial-redundancy elimination (PRE) inserts a + b on the path through C — making the evaluation in D fully redundant — and deletes it from D. Every path now evaluates a + b exactly once. PRE subsumes global common-subexpression elimination (full redundancy) and loop-invariant code motion (an invariant expression in a loop body is partially redundant with itself along the back edge), which is why it has been a centerpiece of optimizing compilers since the 1980s.
Morel–Renvoise¶
Morel and Renvoise gave the first PRE algorithm: one system of bit-vector equations over "placement possible" sets, solved in both directions at once [MR79]. It placed insertions at block ends, could not insert on critical edges (Drechsler and Stadel exhibited the resulting misses [DS88]), was not computationally optimal and could move computations further than needed, stretching register lifetimes.
Lazy code motion¶
Knoop, Rüthing and Steffen split PRE into unidirectional analyses: down-safety (anticipability: the value would be computed anyway on every path), earliestness (the first down-safe point not already covered), then delay as long as possible (latest), and skip insertions used only by themselves (isolated) [KRS92, KRS94]. The result is computationally optimal (no program obtainable by safe insertions evaluates fewer computations on any path) and lifetime optimal (among those, the temporaries live shortest). Drechsler and Stadel reformulated it on basic blocks with insertions on edges [DS93]: the EARLIEST/LATER/INSERT/DELETE equations taught in [EaC3, Ch. 10], implemented by GCC's lcm.cc [GCC-LCM], the drill lcm-sets and the ★ lab.
SSAPRE¶
Bit-vector PRE works on lexically identical expressions over variables. Chow, Chan, Kennedy, Liu, Lo and Tu redid PRE on SSA, one expression at a time, with a sparse "factored redundancy graph": Φ-functions for expressions placed at iterated dominance frontiers, renamed like variables, then six steps decide where to insert and what to reload [CCK+97, KCL+99]. It was the PRE of SGI's and later Open64's optimizer [Open64-SSAPRE], and the reference treatment of the SSA book [SSAB, Ch. 11].
GVN-PRE¶
Lexical PRE misses redundancies whose operands have different names but equal values (t = a + b and u = c + b with c a copy of a). VanDrunen and Hosking combined PRE with value numbering: anticipation and availability are computed over value numbers, and expressions are translated through phis when moved to predecessors [VH04]. GCC's tree PRE is GVN-PRE on top of its RPO value numbering [GCC-PRE].
LLVM's load PRE¶
LLVM's gvn does not implement general PRE (its performScalarPRE handles only the diamond-shaped case). Its most important PRE is for loads: when a load is available (loaded or stored) in some predecessors, GVN inserts the load in the others and merges the values with a phi, subject to safety and profitability checks [LLVM-GVN].
2. Definitions and algorithms¶
Throughout, \(\mathcal{E}\) is the set of candidate expressions and each block \(n\) has the local sets of Lesson 14.3 in the notation of [EaC3]: \(\mathrm{UEEXPR}(n)\) (evaluated in \(n\) before any operand is redefined), \(\mathrm{DEEXPR}(n)\) (evaluated in \(n\) and no operand redefined afterwards), \(\mathrm{EXPRKILL}(n)\) (an operand is redefined in \(n\)) and \(\mathrm{TRANSP}(n) = \mathcal{E} \setminus \mathrm{EXPRKILL}(n)\).
Definition 17.6.1 (Availability, anticipability, partial availability)
With \(n_0\) the entry and every block reachable: \(\mathrm{AVIN}(n_0) = \emptyset\), \(\mathrm{AVIN}(n) = \bigcap_{p} \mathrm{AVOUT}(p)\), \(\mathrm{AVOUT}(n) = \mathrm{DEEXPR}(n) \cup (\mathrm{AVIN}(n) \setminus \mathrm{EXPRKILL}(n))\) (greatest solution); \(\mathrm{ANTOUT}(n) = \bigcap_{s} \mathrm{ANTIN}(s)\) (\(\emptyset\) at exits), \(\mathrm{ANTIN}(n) = \mathrm{UEEXPR}(n) \cup (\mathrm{ANTOUT}(n) \setminus \mathrm{EXPRKILL}(n))\) (greatest); partial availability \(\mathrm{PAVIN}\), \(\mathrm{PAVOUT}\): the same as availability with \(\bigcup\) and the least solution. \(e \in \mathrm{ANTIN}(n)\) means \(e\) is down-safe (anticipable) at the start of \(n\): every path from there evaluates \(e\) before an operand changes.
Definition 17.6.2 (PRE transformation; safety; optimality)
A PRE transformation of the program chooses, for each expression \(e\), a set of insertion points (block
ends, or edges) where h_e ← e is evaluated, and a set of blocks whose upward-exposed evaluation of \(e\) is
replaced by h_e; every other evaluation x ← e becomes h_e ← e; x ← h_e. It is correct if every
replaced evaluation finds h_e holding \(e\)'s current value on every path; safe if every insertion
point is down-safe for \(e\) (no path gains an evaluation it did not have — so no new exception or trap);
computationally optimal if among correct safe transformations it evaluates \(e\) at most as often on every
path as any other; lifetime optimal if among computationally optimal ones the ranges where h_e is live
are minimal (by inclusion).
Algorithm 17.6.3 (Morel–Renvoise PRE, with partial availability)
- Input: a CFG with the local sets; \(\mathrm{AVOUT}\), \(\mathrm{ANTIN}\), \(\mathrm{PAVIN}\) of Definition 17.6.1.
- Output: \(\mathrm{INSERT}(n)\) (at the end of block \(n\)) and \(\mathrm{DELETE}(n)\) for each block.
- Precondition: every block reachable; one entry without predecessors.
- Postcondition: correct and safe (Proposition 17.6.15); not computationally optimal in general (ibid.).
- Invariant: \(\mathrm{PPIN}\), \(\mathrm{PPOUT}\) only shrink from the universe.
function MorelRenvoise(G):
PPIN[n0] ← ∅; PPIN[n], PPOUT[n] ← 𝓔 for all other n # greatest solution
repeat until no change, for n in RPO:
PPOUT[n] ← (n is an exit) ? ∅ : ∩ over successors s of PPIN[s]
PPIN[n] ← PAVIN[n] ∩ ANTIN[n] ∩ (UEEXPR[n] ∪ (TRANSP[n] ∩ PPOUT[n]))
∩ ∩ over predecessors p of (AVOUT[p] ∪ PPOUT[p]) # the backward part: bidirectional
INSERT[n] ← PPOUT[n] − AVOUT[n] − (PPIN[n] ∩ TRANSP[n])
DELETE[n] ← UEEXPR[n] ∩ PPIN[n]
Definition 17.6.4 (Earliest, delayed, latest, isolated — Knoop, Rüthing, Steffen)
Consider program points (block entries and exits). A down-safe point \(p\) is earliest for \(e\) if no predecessor point is both down-safe and able to carry \(e\) to \(p\) unchanged, and \(e\) is not already available at \(p\). \(e\) is delayed at \(p\) if every path from the entry to \(p\) passes an earliest point for \(e\) with no evaluation of \(e\) in between. \(p\) is latest if \(e\) is delayed at \(p\) and either \(p\) evaluates \(e\) or some successor point is not delayed. A latest insertion is isolated if the value would reach no use other than the evaluation at the same point. LCM inserts at latest, non-isolated points and replaces the original evaluations that the insertions cover.
Definition 17.6.5 (Lazy code motion on edges, Drechsler–Stadel)
For every edge \((i, j)\) and block \(n\):
(\(\overline{X}\) is the complement in \(\mathcal{E}\); LATER/LATERIN is the greatest solution.) \(e \in \mathrm{LATER}(i, j)\) means the insertion of \(e\) may be delayed past the edge; an insertion is made on an edge where it can be delayed no further.
Algorithm 17.6.6 (Lazy code motion, edge form)
- Input: a CFG with local sets; \(\mathrm{AVOUT}\), \(\mathrm{ANTIN}\), \(\mathrm{ANTOUT}\) (Definition 17.6.1).
- Output: \(\mathrm{INSERT}(i, j)\) per edge, \(\mathrm{DELETE}(k)\) per block, and the rewritten program.
- Precondition: one entry \(n_0\) without predecessors; every block reachable.
- Postcondition: the rewritten program is correct and safe (Lemma 17.6.12), computationally optimal (Theorem 17.6.13) and lifetime optimal (Theorem 17.6.14, for the block-level placement).
- Invariant: LATER and LATERIN only shrink from the universe during the round-robin solve.
function LCM(G):
compute AVIN/AVOUT (forward, ∩) and ANTIN/ANTOUT (backward, ∩), greatest solutions
for each edge (i, j): compute EARLIEST(i, j) # Definition 17.6.5
LATERIN[n0] ← ∅; LATERIN[n], LATER[i, j] ← 𝓔 elsewhere
repeat until no change, for n in RPO:
for each successor s of n: LATER[n, s] ← EARLIEST[n, s] ∪ (LATERIN[n] − UEEXPR[n])
if n ≠ n0: LATERIN[n] ← ∩ over predecessors p of LATER[p, n]
INSERT[i, j] ← LATER[i, j] − LATERIN[j]; DELETE[k] ← UEEXPR[k] − LATERIN[k]
Rewrite:
for each e moved: pick a fresh temporary h_e
for each evaluation `x ← e` in block k:
if it is k's first upward-exposed evaluation and e ∈ DELETE[k]: replace by `x ← h_e`
else: replace by `h_e ← e; x ← h_e`
for each edge (i, j) with INSERT[i, j] ≠ ∅: put `h_e ← e` for its expressions
at the start of j if j has one predecessor, else at the end of i if i has one successor,
else in a new block on the edge (a critical edge)
scalaropt.lcm_sets is this algorithm, the drill lcm-sets prints its sets, and labs/ch17-lcm asks you to implement it on TAC (ch17-lcm --sets must equal lcm_oracle.py sets).
Definition 17.6.7 (Expression SSA: Φ, versions, factored redundancy graph)
For one expression \(E\) (e.g. \(a + b\) over variables \(a\), \(b\)) SSAPRE treats every evaluation of \(E\) as a real occurrence and inserts expression-Φ's \(h = \Phi(h_1, \dots, h_k)\) at the iterated dominance frontier of the blocks with real occurrences and of the definitions of \(E\)'s operands (a changed operand begins a new value). Renaming walks the dominator tree with a stack and gives two occurrences the same version iff they compute the same value (no operand redefined in between); a Φ operand from a predecessor where \(E\) is not available gets version \(\bot\). The occurrences, Φ's and their def-use edges form the factored redundancy graph (FRG).
Algorithm 17.6.8 (SSAPRE, per expression)
- Input: an SSA program; one lexical expression \(E\) at a time.
- Output: insertions at Φ operands, reloads replacing redundant real occurrences, a temporary \(t\) in SSA form.
- Precondition: strict SSA; critical edges split (Φ operand insertions happen at the end of predecessors).
- Postcondition: correct, safe and computationally optimal for \(E\) (Theorem 17.6.16).
- Invariant: after step 2, each version has one defining occurrence (a real occurrence or a Φ) that dominates its uses.
function SSAPRE(E):
1. Φ-Insertion: place Φ's for E at DF+(blocks with occurrences of E ∪ blocks defining E's operands)
2. Rename: dominator-tree walk with a version stack; a real occurrence whose operands are unchanged
since the version on top of the stack reuses that version; otherwise a new version.
Φ operands take the version on top at the end of the predecessor, or ⊥.
3. DownSafety: a Φ is down-safe unless some path from it reaches an exit without a real occurrence
of its version; propagate "not down-safe" backwards through Φ operands without real uses.
4. WillBeAvail: can_be_avail(Φ) = down-safe, or all operands are non-⊥ and can_be_avail;
later(Φ) = can_be_avail and no operand has a real use (propagate forward);
will_be_avail(Φ) = can_be_avail and not later.
5. Finalize: for each Φ with will_be_avail, insert E at the end of each predecessor whose operand
is ⊥ (or not will_be_avail); decide for each real occurrence whether to compute (save) or reload.
6. CodeMotion: introduce t: saved occurrences become `t ← E`, reloaded ones use t,
will_be_avail Φ's become phis of t.
Definition 17.6.9 (Value expressions, phi-translation, ANTIC)
Let every value have a number (Lesson 17.4). A value expression is \(\mathit{op}(v_1, v_2)\) over value
numbers. For a block \(b\): \(\mathrm{EXP\_GEN}(b)\) is the set of value expressions computed in \(b\) whose operands
are not defined in \(b\) before them; \(\mathrm{TMP\_GEN}(b)\) the values defined in \(b\); \(\mathrm{AVAIL\_OUT}(b)\) the
values available at the end of \(b\) (with a leader: a dominating value that computes them). Phi-translation
\(\mathrm{phi\_trans}(S, b, s)\) rewrites each value expression anticipated at the start of \(s\) by replacing
every operand defined by a phi of \(s\) with the phi's operand from \(b\), and re-numbers the result.
\(\mathrm{ANTIC\_IN}(b)\) is the greatest solution of
\(\mathrm{ANTIC\_OUT}(b) = \mathrm{phi\_trans}(\mathrm{ANTIC\_IN}(s), b, s)\) if \(b\) has one successor \(s\), and
\(\bigcap_s \mathrm{ANTIC\_IN}(s)\) otherwise; \(\mathrm{ANTIC\_IN}(b) = \mathrm{clean}(\mathrm{ANTIC\_OUT}(b) \cup
\mathrm{EXP\_GEN}(b) \setminus \mathrm{TMP\_GEN}(b))\), where clean drops expressions whose operands are not
themselves anticipated.
Algorithm 17.6.10 (GVN-PRE, VanDrunen–Hosking)
- Input: an SSA program with value numbers.
- Output: insertions and phis that make partially redundant values fully redundant; eliminations.
- Precondition: critical edges split; value numbering sound.
- Postcondition: every value computed in a block is replaced by a leader if one is available (Theorem 17.6.17).
- Invariant: \(\mathrm{ANTIC\_IN}\) only shrinks during its solve; insertions only add available values.
function GVNPRE(F):
BuildSets: AVAIL_OUT top-down in the dominator tree; EXP_GEN, TMP_GEN per block;
ANTIC_IN by the backward greatest fixed point of Definition 17.6.9
Insert: repeat until nothing new:
for each block b with ≥ 2 predecessors, in dominator-tree order:
for each value expression e in ANTIC_IN(b):
for each predecessor p: e_p ← phi_trans(e, p, b); avail_p ← leader of e_p in AVAIL_OUT(p)
if some avail_p exists and some does not (partially redundant):
insert `t_p ← e_p` at the end of each p without one; create `v ← phi(avail_p…)` in b;
add v to AVAIL_OUT of b and the blocks it dominates
Eliminate: replace every computation whose value has a different leader in AVAIL_OUT by that leader
Algorithm 17.6.11 (Load PRE in LLVM's GVN, simplified)
- Input: a load \(L\) of address \(p\) in block \(B\); memory dependence information for each predecessor path.
- Output: \(L\) replaced by a phi of available values, with loads inserted in the predecessors that lack one.
- Precondition: \(p\) is available (phi-translated) in the predecessors where a load is inserted; the load is safe to execute there (the address is dereferenceable on that path, or the load was anticipated on every path from there).
- Postcondition: every path evaluates at most one load of \(p\) where it evaluated one before, and \(L\)'s value is unchanged (Theorem 17.6.18).
- Invariant: the values collected per predecessor are each equal to what \(L\) would read when reached from that predecessor.
function LoadPRE(L at B):
for each predecessor P of B: find, through memory dependence, a value V_P equal to *p at the end of P
(an earlier load or store of p that nothing clobbers), or ⊥
Unavail ← { P : V_P = ⊥ }
if Unavail = ∅: replace L by phi(V_P …); done # fully redundant
if |Unavail| > 1 or the insertion is unsafe or unprofitable: give up
insert `V_P ← load p'` at the end of the one P ∈ Unavail (p' = p translated into P)
replace L by phi(V_P …) in B
3. Worked example¶
Morel–Renvoise¶
Algorithm 17.6.3 on the diamond (scalaropt.morel_renvoise; \(\mathcal{E} = \{a{+}b\}\), so sets are \(\{\}\) or \(\{a{+}b\}\)):
| block | UEEXPR | AVOUT | ANTIN | PAVIN | PPIN (pass 1) | PPOUT (pass 1) | pass 2 | INSERT | DELETE |
|---|---|---|---|---|---|---|---|---|---|
| A | {} | {} | {a+b} | {} | {} (entry) | {} | unchanged | {} | {} |
| B | {a+b} | {a+b} | {a+b} | {} | {} (PAVIN = {}) | {a+b} | unchanged | {} | {} |
| C | {} | {} | {a+b} | {} | {} (PAVIN = {}) | {a+b} | unchanged | {a+b} | {} |
| D | {a+b} | {a+b} | {a+b} | {a+b} | {a+b} | {} (exit) | unchanged | {} | {a+b} |
PPIN(D): \(a{+}b\) is partially available (through B), anticipated, upward exposed, and every predecessor either has it available (B) or can receive it (PPOUT(C) = {a+b}): placement possible.INSERT(C)= PPOUT(C) − AVOUT(C) − (PPIN(C) ∩ TRANSP(C)) = {a+b}; nothing in B (already available).DELETE(D)= {a+b}.
On the diamond, MR and LCM agree. On the critical-edge variant A: if p < q -> B, D; B: x = a + b -> D; D: y = a + b (the edge A→D is critical), MR finds nothing: inserting at the end of A would evaluate \(a{+}b\) on the path through B twice, so PPIN(D) needs PPOUT(A), which is empty because A's other successor B does not need it. LCM inserts on the edge A→D and deletes in D (scalaropt computes both; this is Drechsler and Stadel's 1988 observation [DS88]).
Lazy code motion¶
Algorithm 17.6.6 on the diamond (scalaropt.lcm; the unit test LazyCodeMotion.test_classic_partial_redundancy asserts these sets):
| edge | EARLIEST | LATER | INSERT |
|---|---|---|---|
| A→B | {a+b} | {a+b} | {} |
| A→C | {a+b} | {a+b} | {} |
| B→D | {} | {} | {} |
| C→D | {} | {a+b} | {a+b} |
| block | AVOUT | ANTIN | ANTOUT | LATERIN | DELETE |
|---|---|---|---|---|---|
| A | {} | {a+b} | {a+b} | {} (entry) | {} |
| B | {a+b} | {a+b} | {a+b} | {a+b} | {} |
| C | {} | {a+b} | {a+b} | {a+b} | {} |
| D | {a+b} | {a+b} | {} | {} | {a+b} |
- EARLIEST(A, B) and (A, C): \(a{+}b\) is anticipated at B and C, not available at the end of A, and A is the entry, so the earliest down-safe points are the edges out of A. (Inserting there would be safe but not lazy.)
- LATERIN(B) = LATER(A, B) = {a+b}: the insertion can be delayed into B; B evaluates \(a{+}b\) itself, so LATER(B, D) = EARLIEST(B, D) ∪ (LATERIN(B) − UEEXPR(B)) = {}: the delay stops at B's own evaluation (it becomes the "insertion").
- LATER(C, D) = {} ∪ (LATERIN(C) − {}) = {a+b}; LATERIN(D) = LATER(B, D) ∩ LATER(C, D) = {}: so INSERT(C, D) = {a+b} and DELETE(D) = {a+b} − {} = {a+b}.
Rewritten (with the temporary h): B: h = a + b; x = h, a new h = a + b on the edge C→D (C has one successor: at the end of C), D: y = h. The round-robin pass counts, each including the final unchanged pass (passes in the result of scalaropt.lcm): availability 2, anticipability 1 (the initial universe is already the answer), LATER 2. The lab's inputs/diamond.tac is this program in TAC; ch17-lcm --transform saves one evaluation (lcm_oracle.py check reports candidate evaluations 3 -> 2).
Try it
./course drill lcm-sets --seed 2 --difficulty hard --solution computes every set of Definition 17.6.5 on
a random 7-block program; the lab's running.tac is Lesson 14.3's running example (7 of 24 candidate
evaluations saved).
SSAPRE¶
SSAPRE for \(E = a + b\) on the diamond (in SSA; \(a\) and \(b\) are parameters, never redefined):
| step | result |
|---|---|
| 1 Φ-Insertion | real occurrences in B and D; \(\mathrm{DF}^{+}(\{B, D\}) = \{D\}\): insert \(h_? = \Phi(\,\cdot_B, \cdot_C)\) at the start of D |
| 2 Rename | dominator-tree preorder A, B, C, D: B's occurrence gets \(h_1\) (new); at the end of B, Φ operand from B ← \(h_1\); at the end of C nothing is on the stack: operand ← \(\bot\); Φ result gets \(h_2\); D's occurrence: operands unchanged since the Φ, so it reuses \(h_2\) |
| 3 DownSafety | the Φ (\(h_2\)) has a real use (D's occurrence) on every path to the exit: down-safe |
| 4 WillBeAvail | can_be_avail = true (down-safe); later: the operand \(h_1\) has a real use (B), so later = false; will_be_avail = true |
| 5 Finalize | Φ operand \(\bot\) from C: insert \(a + b\) at the end of C as \(h_3\); B's occurrence: save; D's occurrence: reload from \(h_2\) |
| 6 CodeMotion | B: t1 = a + b; x = t1, C: t3 = a + b, D: t2 = phi(t1, t3); y = t2 |
The same placement as LCM, obtained sparsely: SSAPRE touched two occurrences and one Φ, not a bit vector per block.
GVN-PRE¶
The function pre of the §7 box: x = 0; if (c) x = a + b; return x + (a + b);. In SSA: block 2 (entry, if c), block 3 (x_6 = a + b), block 5 (the empty else edge, split), block 4 (x_2 = phi(0 from 5, x_6 from 3), _1 = a + b, _7 = _1 + x_2). Value numbers: \(v_5\) = a+b (for x_6 and _1), \(v_6\) = _1 + x_2.
| block | EXP_GEN | ANTIC_IN |
|---|---|---|
| 4 | \(v_5\) = {a+b}, \(v_6\) = | {a, b, v5, x_2, v5 + x_2} |
| 3 | \(v_5\) | phi_trans from 4 with x_2 ↦ x_6: |
| 5 | {} | phi_trans with x_2 ↦ 0: v5 + 0 simplifies to v5: |
| 2 | {} | ANTIC_IN(3) ∩ ANTIC_IN(5) plus c: |
Insert at block 4: \(v_5\) is available at the end of 3 (x_6) but not of 5: insert _9 = a + b in 5 and prephitmp_10 = phi(_9, x_6). The value \(v_5 + x_2\) translates to \(v_5 + 0 = v_5\) (available in 5 as _9) and to \(v_5 + x_6 = x_6 \cdot 2\) in 3 (not available): insert _11 = x_6 * 2 in 3 and prephitmp_12 = phi(_9, _11). Both _1 and _7 in block 4 become fully redundant. (GCC then also hoists \(v_5\) into block 2, which makes _9 and x_6 redundant: §7 box.)
LLVM's load PRE¶
In partial of the §7 box, the load of *p in if.end has an available value on the edge from if.then (the load %0) but none on the edge from entry. Exactly one predecessor lacks it, p is available there, and the load is anticipated (every path from entry loads *p at if.end), so inserting %.pre = load p at the end of entry is safe. GVN inserts it, and then the load in if.then is fully redundant with it (%.pre dominates): both loads in the body are replaced by %.pre.
4. Invariants and correctness¶
Lemma 17.6.12 (LCM is correct and safe)
In the program rewritten by Algorithm 17.6.6: (a) every insertion of \(e\) on edge \((i, j)\) is down-safe
(\(e \in \mathrm{ANTIN}(j)\)) and \(e\) is not available there; (b) whenever a block \(k\) uses h_e in place of a
deleted evaluation, h_e holds the current value of \(e\) on every path; hence the rewritten program computes
the same values.
Proof sketch (full proof: [KRS94, §3–4]; for the edge form [DS93])
Fix \(e\) and drop it from the notation. (a) Show by induction on the length of a path from the entry that
\(\mathrm{LATERIN}(j) \subseteq \mathrm{ANTIN}(j)\) and \(\mathrm{LATER}(i, j) \subseteq \mathrm{ANTIN}(j)\) for
the greatest solution: characterize \(e \in \mathrm{LATERIN}(j)\) as "every path from \(n_0\) to \(j\) contains an
edge in EARLIEST after which no block evaluates \(e\) upward-exposed" (the greatest solution of a forward
\(\cap\)-system over paths starting at \(\mathrm{LATERIN}(n_0) = \emptyset\) is this all-paths property, as for
availability). EARLIEST edges satisfy \(e \in \mathrm{ANTIN}\) at their targets; walking forward from one
along blocks \(i\) with \(e \notin \mathrm{UEEXPR}(i)\), anticipation propagates: \(e \in \mathrm{ANTIN}(i)
\setminus \mathrm{UEEXPR}(i)\) forces \(e \in \mathrm{ANTOUT}(i) \setminus \mathrm{EXPRKILL}(i)\), so
\(e \in \mathrm{ANTIN}(s)\) for every successor \(s\). Insertions are LATER edges, hence down-safe; they are not
available because an EARLIEST edge requires \(e \notin \mathrm{AVOUT}(i)\) and delaying never crosses an
evaluation. (b) If \(e \in \mathrm{DELETE}(k)\) then \(e \notin \mathrm{LATERIN}(k)\), so on some incoming edge
\(e \notin \mathrm{LATER}\); by the all-paths characterization, on every path to \(k\) the delay chain that
began at an EARLIEST edge was ended — by an insertion (INSERT on an edge where LATER holds but LATERIN of
the target does not) or by an evaluation (which now writes h_e) — after which no operand of \(e\) changed
(down-safety of the chain) and no other evaluation intervened. Hence h_e holds \(e\)'s value at \(k\).
Theorem 17.6.13 (LCM is computationally optimal)
No correct and safe PRE transformation evaluates \(e\) fewer times than LCM on any path from the entry to an exit. In particular LCM never evaluates \(e\) more often than the original program on any path.
Proof sketch (full proof: [KRS94, Theorem 3.9])
Split every path into segments between consecutive original evaluations of \(e\) or definitions of its
operands. A safe transformation may evaluate \(e\) only at down-safe points; on a segment that ends in an
original evaluation, at least one evaluation is needed unless \(e\) is already available on entry to the
segment along this path. LCM evaluates exactly once per segment in which the original evaluates \(e\) and
\(e\) is not available on every path into the segment's start — the earliest points are the first down-safe
points on every path, and a single insertion (or kept evaluation) per delay chain covers every deletion
it reaches (Lemma 17.6.12 (b)). So on every path LCM's count is the number of segments needing an
evaluation, which is a lower bound for every correct safe transformation. The second claim follows since the
original program is itself a correct safe transformation. The unit test test_never_more_evaluations checks it
on random paths of 150 random programs, and lcm_oracle.py check on the lab's inputs.
Theorem 17.6.14 (LCM is lifetime optimal)
Among computationally optimal placements, LCM's temporaries h_e are live on a set of program points
contained in the live range of any other computationally optimal placement's temporaries.
Proof sketch (full proof: [KRS94, Theorem 3.13]; isolated insertions per Definition 17.6.4)
Every computationally optimal placement inserts exactly one evaluation per delay chain, somewhere between
the earliest point and the first use, because moving it outside that interval either adds evaluations (too
late: past a branch) or loses safety (too early: before down-safety). Delaying to the latest such point
makes the live range of h_e start as late as possible on every path while it still ends at the same uses,
so it is contained in every other optimal placement's live range. The node-based KRS algorithm also avoids
isolated insertions (a temporary used only at its own evaluation); in the edge form, an insertion whose
only use would be at the same place does not arise, because DELETE and INSERT at the same point cancel
(\(\mathrm{INSERT}(i, j) \cap \mathrm{LATERIN}(j) = \emptyset\)), and the kept evaluation writes h_e directly.
Proposition 17.6.15 (Morel–Renvoise: correct and safe, not optimal)
Algorithm 17.6.3's insertions are down-safe and its deletions correct; but there are programs where it misses a partial redundancy that LCM removes, and programs where it moves evaluations further up than necessary.
Proof
Safety: \(\mathrm{INSERT}(n) \subseteq \mathrm{PPOUT}(n) = \bigcap_s \mathrm{PPIN}(s) \subseteq \bigcap_s \mathrm{ANTIN}(s) = \mathrm{ANTOUT}(n)\), so every insertion at the end of \(n\) is anticipated. Correctness: if \(e \in \mathrm{DELETE}(k) \subseteq \mathrm{PPIN}(k)\), the last conjunct of PPIN says every predecessor \(p\) has \(e \in \mathrm{AVOUT}(p)\) or \(e \in \mathrm{PPOUT}(p)\); in the latter case either \(p\) inserts \(e\) at its end or \(e \in \mathrm{PPIN}(p) \cap \mathrm{TRANSP}(p)\) and the argument repeats upward; it ends at an availability or an insertion on every path because \(\mathrm{PPIN}(n_0) = \emptyset\) and PPIN is a greatest fixed point bounded by PAVIN (partial availability means the chain reaches an evaluation). Not optimal: the critical-edge variant of §3 — MR must insert at a block end, the only candidate A is not allowed (inserting there adds an evaluation on the path through B, and PPIN(D) requires PPOUT(A)), so MR removes nothing while LCM saves one evaluation per execution through A→D. For the second claim, MR places insertions as early as PPOUT allows (the "earliest" end), which lengthens live ranges on examples such as a loop-invariant expression used only after an inner test [KRS92, §1].
Theorem 17.6.16 (SSAPRE is correct, safe and computationally optimal)
For each expression, SSAPRE's insertions are at down-safe Φ operands, its reloads read the value of the expression, and the number of evaluations on every path is minimal among safe placements at Φ operands.
Proof sketch (full proof: [KCL+99, §4–5])
Φ-insertion at \(\mathrm{DF}^{+}\) of occurrences and operand definitions puts a Φ at every point where two
different values of \(E\) can merge (the argument of SSA construction, Ch 16), so versions correctly identify
equal values (renaming invariant). DownSafety computes, sparsely on the FRG, exactly the anticipability of
Definition 17.6.1 at Φ's; WillBeAvail's can_be_avail is "down-safe, or available on all incoming paths",
and later marks Φ's whose insertion can be postponed because no real occurrence needs them — the
FRG-level counterpart of LCM's delay. Insertions happen only at operands of will_be_avail Φ's, which are
down-safe or fully available: safe. Kennedy et al. prove that the result coincides with LCM's
computational optimality for each expression, and with lifetime optimality when a later pass sinks the
remaining insertions (their "optimal" variant).
Theorem 17.6.17 (GVN-PRE is sound)
Every insertion made by Algorithm 17.6.10 computes a value anticipated at the end of its block, and every elimination replaces a computation by a leader with the same value that dominates it.
Proof sketch (full proof: [VH04, §4])
By construction, \(\mathrm{ANTIC\_IN}\) is the greatest solution of a backward \(\cap\)-system whose facts are
value expressions translated through phis; a translated expression computes, on the edge from \(p\), the same
value the untranslated one computes at the start of the successor (phi-translation replaces exactly the
values the phis select on that edge). An insertion in \(p\) adds t_p ← e_p for an expression anticipated at
\(b\), whose operands are available in \(p\) (clean keeps only expressions with anticipated operands, and
insertion requires leaders for them), and the new phi merges, per predecessor, values equal to \(e\)'s value
on that edge: the phi's value is \(e\)'s value at \(b\). Elimination uses dominating leaders of equal value
numbers, which is sound by Theorem 17.4.6.
Theorem 17.6.18 (Load PRE preserves loaded values and adds no load on any path)
Under the preconditions of Algorithm 17.6.11, the new phi has, on every path, the value the original load read, and every path executes at most as many loads of \(p\) as before.
Proof
For each predecessor \(P\) with \(V_P \neq \bot\), memory dependence guarantees that nothing between \(V_P\)'s
definition and the end of \(P\) clobbers \(*p\) (translated), so \(*p\) at the end of \(P\) equals \(V_P\); for the one
inserted load, it reads \(*p\) at the end of \(P\) directly. Entering \(B\) from \(P\), the phi selects \(V_P\), which
equals what \(L\) reads, since nothing between the end of \(P\) and \(L\) in \(B\) clobbers \(p\) (the dependence query
started at \(L\)). A path through the inserted load's predecessor continues to \(L\) (the anticipation
precondition) and now executes the inserted load instead of \(L\); paths through other predecessors execute
no new load. Safety of executing the load earlier is the explicit precondition (a load may trap on an
invalid address, so LLVM requires p to be dereferenceable there or the load to be anticipated).
Which precondition breaks it. Without critical-edge splitting (or edge insertion), block-level PRE misses redundancies (Proposition 17.6.15); without down-safety, PRE can introduce a division by zero or a null load on a path that never executed it; with speculation (Lesson 17.6 §6) safety must be re-established by other means.
5. Complexity¶
\(n\) blocks, \(e_G\) edges, \(k = \lvert\mathcal{E}\rvert\) candidate expressions, \(w\) the machine word size, \(d\) the loop connectedness; \(N\) SSA values, \(V\) value numbers.
| Technique | Time (worst) | Time (typical) | Space | Justification |
|---|---|---|---|---|
| Morel–Renvoise | \(O(n^2 \cdot k / w)\) word operations: bidirectional systems need not converge in \(d + 2\) passes | several passes | \(O((n + e_G) k / w)\) | a bidirectional system is not rapid (Dhamdhere, Khedker) |
| LCM (edge form) | 4 unidirectional bit-vector problems: \(O((d + 2)(n + e_G) \cdot k / w)\) | \(\approx 3\) passes each | \(O(e_G \cdot k / w)\) | each system is a rapid gen/kill problem (Ch 14, Theorem 14.4.6) |
| SSAPRE | \(O(\sum_E (\lvert\text{occ}(E)\rvert + \lvert\mathrm{DF}^{+}\rvert))\) per expression, sparse | near-linear in the program | per expression | each step is a pass over the FRG |
| GVN-PRE | \(O(n \cdot V)\) per ANTIC pass, with \(O(d)\)-ish passes; insertion iterates | acceptable (GCC's PRE is on at -O2) |
\(O(n \cdot V)\) sets | set operations over value sets per block |
| Load PRE (LLVM) | per load: memory dependence queries across predecessors, capped | cheap per load, many loads | \(O(1)\) extra per load | MemDep limits (-memdep-block-scan-limit) |
Pathological family for bidirectional MR. A loop with \(m\) nested diamonds, where placement possibility must propagate backward across each diamond and forward again: the PPIN/PPOUT round-robin needs a pass per diamond, \(\Theta(m)\) passes of \(\Theta(n)\) blocks, while LCM's four unidirectional systems each converge in a constant number of RPO passes on the same reducible graph. At scale: the lab's running.tac (Lesson 14.3's running example with a loop) needs 2, 3 and 5 round-robin passes for availability, anticipability and LATER (scalaropt.lcm_tac(...)["passes"]; the drill lcm-sets prints the counts for its programs).
6. Variants and refinements¶
- Edge placement vs critical-edge splitting — Drechsler–Stadel insert on edges [DS93]; SSAPRE and GVN-PRE split critical edges first. Trade-off: more blocks vs simpler placement.
- Speculative PRE — insert at points that are not down-safe when profiling says it pays off (Horspool–Ho; the SSAPRE paper's speculation; GCC's
-ftree-loop-imfor invariants). Trade-off: may add work on cold paths; needs safe operations. - Isolation and register pressure — LCM's lifetime optimality ignores the number of simultaneously live temporaries; ALCM/pressure-aware PRE limit motion. Trade-off: fewer redundancies removed.
- Assignment motion and partial dead code — the dual problems: sink assignments to where they are used (Knoop–Rüthing–Steffen's partial dead code elimination), move assignments rather than expressions.
- Strength reduction with PRE — SSAPRE extends to induction-variable strength reduction (Kennedy et al., "Strength reduction via SSAPRE"); Ch 18.
- Load/store PRE — PRE of loads (LLVM GVN, below), and store sinking (MergedLoadStoreMotion, GVN-sink).
- Value-based PRE — GVN-PRE [VH04], Briggs–Cooper's reassociation + PRE [BC94], and GCC's PRE with code hoisting.
7. In real compilers¶
Morel–Renvoise¶
No production compiler solves the bidirectional MR system today; GCC's RTL PRE began as MR and was rewritten to lazy code motion, and its source still lists the lineage.
GCC's RTL PRE: from Morel–Renvoise to lazy code motion
Reproduce (gcc 15.1.0 source; curl from GitHub):
curl -sSfL https://raw.githubusercontent.com/gcc-mirror/gcc/releases/gcc-15.1.0/gcc/gcse.cc |
sed -n '/^ This is based on the original Morel-Renvoise/,/Compiler Design and Implementation/p'
Output:
This is based on the original Morel-Renvoise paper Fred Chow's thesis, and
lazy code motion from Knoop, Ruthing and Steffen as described in Advanced
Compiler Design and Implementation.
What to notice: the comment above GCC's RTL PRE driver in gcse.cc [GCC-GCSE] names the three
stages of this lesson's history; the header of the same file lists Morel–Renvoise, Drechsler–Stadel (both
papers) and Knoop–Rüthing–Steffen, and the placement itself calls pre_edge_lcm from lcm.cc — the
MR equations survive only as the problem LCM solves optimally.
Lazy code motion¶
GCC: gcc/lcm.cc — pre_edge_lcm with compute_antinout_edge, compute_earliest, compute_laterin, used by RTL PRE (gcse.cc) and other placement problems (mode switching) [GCC-LCM]. LLVM has no LCM pass; its PRE lives in GVN (below). The ★ lab and the drill implement Algorithm 17.6.6.
GCC's RTL PRE inserts on an edge and deletes the redundancy
Reproduce (gcc 14.2.0):
cat > pre.c <<'EOF'
int pre(int a, int b, int c) {
int x = 0;
if (c)
x = a + b; // a + b on one path only
return x + (a + b); // partially redundant: PRE inserts a + b on the other path
}
EOF
gcc-14 -O2 -fno-tree-pre -fno-code-hoisting -fno-tree-fre -fdump-rtl-pre-details -S pre.c -o /dev/null
grep -E '^PRE' pre.c.*r.pre
Output:
PRE: redundant insn 14 (expression 0) in bb 5, reaching reg is 105
PRE: edge (2,5), copy expression 0
PRE: bb 4, insn 28, copy expression 0 in insn 11 to reg 105
PRE GCSE of pre, 6 basic blocks, 2344 bytes needed, 1 substs, 2 insns created
What to notice: with the tree-level PRE and FRE disabled, RTL PRE sees the diamond of §3: the
evaluation of a + b (expression 0) in the join block 5 is redundant after an insertion on the edge
(2,5) — the INSERT on an edge of Definition 17.6.5 — and the kept evaluation in bb 4 copies its result into
the shared register 105 (h_e of Algorithm 17.6.6).
SSAPRE¶
Open64 (the open-source descendant of SGI's MIPSpro compilers, by the SSAPRE authors' group): osprey/be/opt/opt_eant.cxx (steps 3–4: down-safety and liveness of Φ's), opt_eavail.cxx (WillBeAvail), opt_efinalize.cxx (Finalize), opt_essa.cxx (Φ-insertion and renaming) [Open64-SSAPRE].
Open64's SSAPRE: the DownSafety step in the source
Reproduce (git 2.x; Open64 at commit 590bdf3d58944cb93aafd89480a5590a863ded60, the repository's HEAD when this lesson was written; it has no release tags):
git clone -q --filter=blob:none --sparse https://github.com/open64-compiler/open64 o64
git -C o64 checkout -q 590bdf3d58944cb93aafd89480a5590a863ded60
git -C o64 sparse-checkout set --no-cone '/osprey/be/opt/opt_eant.cxx'
sed -n '/^\/\/ SSA\/PRE Step 4 (Not down safe)/,/^\/\/ SSA\/PRE Step 4.5/p' o64/osprey/be/opt/opt_eant.cxx
Output:
// SSA/PRE Step 4 (Not down safe) and
// AGGCM (speculate safe ops out of while-do loop)
//
// (AGGCM) If an phi result is not fully anticipated, but the phi node
// has an edge that is a back edge, and the operation is proper for
// speculation, mark the phi result to be fully anticipated.
//
// Propagate not down safe (not fully anticipated) phi-assignments
// upward. I.e., if x5 = phi(x3,x4) is not down-safe, if x3 is also a
// phi-assignment and there is no real occurrence of x3, then the x3
// phi-assignment is also not down-safe. Note this happens only when
// x5 and x3 are not marked as down-safe by AGGCM.
//
//
// SSA/PRE Step 4.5 (dead phi elimination):
What to notice: step 3 of Algorithm 17.6.8 exactly (the file numbers the steps differently): "not
down-safe" propagates backwards through Φ operands without real occurrences. The AGGCM part is the
speculation variant of §6, applied to loop-invariant expressions in while loops.
GVN-PRE¶
GCC: gcc/tree-ssa-pre.cc — compute_antic (ANTIC_IN/ANTIC_OUT with phi-translation), do_pre_regular_insertion, and the code-hoisting mode that uses the same sets [GCC-PRE]; its value numbers come from tree-ssa-sccvn.cc (Lesson 17.5).
GCC tree PRE: value-based anticipation and phi-translation
Reproduce (gcc 14.2.0; pre.c from the previous box):
gcc-14 -O2 -fdump-tree-pre-details -S pre.c -o /dev/null
grep -E '^\[changed\] ANTIC_IN\[(4|3|5|2)\]|^Found partial|^Inserted|^Created phi|^Inserting expression|^Replaced redundant PHI' pre.c.*t.pre
Output:
[changed] ANTIC_IN[4] := { a_4(D) (0003), b_5(D) (0004), {plus_expr,a_4(D),b_5(D)} (0005), x_2 (0001), {plus_expr,_1,x_2} (0006) }
[changed] ANTIC_IN[3] := { a_4(D) (0003), b_5(D) (0004), {plus_expr,a_4(D),b_5(D)} (0005), {plus_expr,_1,x_6} (0008) }
[changed] ANTIC_IN[5] := { a_4(D) (0003), b_5(D) (0004), {plus_expr,a_4(D),b_5(D)} (0005) }
[changed] ANTIC_IN[2] := { c_3(D) (0002), a_4(D) (0003), b_5(D) (0004), {plus_expr,a_4(D),b_5(D)} (0005) }
Found partial redundancy for expression {plus_expr,a_4(D),b_5(D)} (0005)
Inserted _9 = a_4(D) + b_5(D);
Created phi prephitmp_10 = PHI <_9(5), x_6(3)>
Found partial redundancy for expression {plus_expr,_1,x_2} (0006)
Inserted _11 = x_6 * 2;
Created phi prephitmp_12 = PHI <_9(5), _11(3)>
Inserting expression in block 2 for code hoisting: {plus_expr,a_4(D),b_5(D)} (0005)
Inserted _13 = a_4(D) + b_5(D);
Replaced redundant PHI node defining prephitmp_10 with _13
What to notice: the GVN-PRE table of §3: sets of value numbers (in parentheses), _1 + x_2
phi-translated to _1 + x_6 in block 3 (value 0008) and simplified to value 0005 in block 5 (where
x_2 = 0). The insertion _11 = x_6 * 2 is (a + b) + x_6 after value numbering knows x_6 = a + b: an
expression that appears nowhere in the source, which lexical PRE could never insert. Code hoisting then
moves a + b into block 2.
LLVM's load PRE¶
LLVM: llvm/lib/Transforms/Scalar/GVN.cpp — GVNPass::processNonLocalLoad collects the per-predecessor availability, GVNPass::PerformLoadPRE checks safety and inserts, eliminatePartiallyRedundantLoad builds the phi; performScalarPRE is its limited scalar PRE [LLVM-GVN].
GVN's load PRE
Reproduce (clang 23.1.2, opt 23.1.2):
cat > lpre.c <<'EOF'
int partial(int *p, int c, int d) {
int s = 0;
if (c)
s = *p; // load on one path only
if (d)
s += 3;
return s + *p; // partially redundant: GVN inserts a load on the other path
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm lpre.c -o lpre.O0.ll
opt -passes='mem2reg,simplifycfg' -S lpre.O0.ll -o lpre.ll
opt -passes=gvn -S lpre.ll | sed -n '/^define/,/^}/p'
Output:
define dso_local i32 @partial(ptr noundef %p, i32 noundef %c, i32 noundef %d) #0 {
entry:
%tobool = icmp ne i32 %c, 0
%.pre = load i32, ptr %p, align 4
br i1 %tobool, label %if.then, label %if.end
if.then: ; preds = %entry
br label %if.end
if.end: ; preds = %if.then, %entry
%s.0 = phi i32 [ %.pre, %if.then ], [ 0, %entry ]
%tobool1 = icmp ne i32 %d, 0
%add = add nsw i32 %s.0, 3
%spec.select = select i1 %tobool1, i32 %add, i32 %s.0
%add4 = add nsw i32 %spec.select, %.pre
ret i32 %add4
}
What to notice: the load at the join was available from if.then only; GVN inserted %.pre at the
end of the other predecessor, entry, which is safe because every path from entry reaches the original
load. Since %.pre now dominates if.then, the load there became fully redundant too: two loads became one
on the c ≠ 0 path, and the c = 0 path still performs exactly one (Theorem 17.6.18).
Find where LLVM does it. In llvm/lib/Transforms/Scalar/GVN.cpp, which member function decides whether a partially redundant load can be made fully redundant by inserting loads in predecessors? (Quiz llvm-where-load-pre.)
8. Comparison¶
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Morel–Renvoise | Correct and safe; misses critical-edge cases; not optimal (Proposition 17.6.15) | bidirectional bit vectors · slow to converge | Block-end insertions | Medium | Historical; the problem statement |
| Lazy code motion | Computationally and lifetime optimal among safe placements (Theorems 17.6.13–17.6.14); lexical | 4 rapid bit-vector problems · fast | Edge insertions, deletions, temporaries | Medium | GCC RTL PRE (lcm.cc), textbooks, the ★ lab |
| SSAPRE | Same optimality per expression, on SSA; sparse | per expression, near-linear | Φ-based placement, SSA temporaries | High (six steps) | SGI/Open64; the SSA book |
| GVN-PRE | Value-based: finds redundancies with different names, via phi-translation | set operations per block over value numbers | Insertions of new expressions (e.g. x_6 * 2) |
High | GCC tree PRE |
| LLVM load PRE | Loads only; single missing predecessor; safety checks | per load, memdep-bound | Hoisted loads + phis | Medium (inside GVN) | LLVM gvn |
Choose LCM when you want provably optimal, safe PRE on a bit-vector framework you already have. Choose SSAPRE when your IR is SSA and you want sparseness per expression. Choose GVN-PRE when value numbering is available and lexical PRE misses too much (copies, reassociation, phis). Choose load PRE when memory operations dominate: it is the part of PRE LLVM ships.
9. Assessment¶
- Quiz:
mr-critical-edge,mr-bidirectional(tagmorel-renvoise);lcm-insert,lcm-delete,lcm-optimal(taglcm);ssapre-steps,ssapre-phi(tagssapre);gvnpre-phitrans,gvnpre-vs-lexical(taggvn-pre);load-pre-safety,llvm-where-load-pre(tagload-pre). - Drill:
./course drill lcm-sets(EARLIEST/LATER/INSERT/DELETE; its availability and anticipability sets are MR's inputs too). SSAPRE, GVN-PRE and load PRE have no drill: their steps are per-expression graph walks whose traces are shown above and asked in the quiz on concrete code. - Flashcards: tags
morel-renvoise,lcm,ssapre,gvn-pre,load-pre. - Exercises: ★
labs/ch17-lcm/SPEC.md.
References¶
See the chapter references.