Lesson 17.5 — Optimistic global value numbering: partitioning, SCC/RPO iteration, NewGVN, hoisting and sinking

Techniques: congruence partitioning (Alpern–Wegman–Zadeck 1988, with Hopcroft-style splitting); optimistic RPO / SCC-based value numbering (Simpson 1996, Click 1995); complete and predicated GVN (Gargi 2002; LLVM's NewGVN), including value inference from branch predicates; GVN-hoist and GVN-sink · Pebble implements: AWZ partitioning in the comparison lab (labs/ch17-scalar, Part B2), measured against the DVNT of Lesson 17.4 · Prerequisites: Lesson 17.4; DFA minimization and Hopcroft's algorithm (Ch 1) · Time: 6–8 hours

1. Problem and motivation

Hash-based value numbering (Lesson 17.4) is pessimistic: at a loop header it must number a phi before the values flowing around the back edge have numbers, so it assumes they are different. In the chapter's running example run (Lesson 17.1) the loop

while.cond:
  i.0 = phi [0, entry], [add, if.end]
  j.0 = phi [0, entry], [add2, if.end]
  ...
if.end:
  add = add i.0, 1
  add2 = add j.0, 1

keeps i.0 and j.0 equal forever, but DVNT and LLVM's GVN never find out: phi(0, add) and phi(0, add2) have different keys because add and add2 are unnumbered when the phis are hashed. An optimistic algorithm instead assumes values equal until proven otherwise and refines the assumption to a fixed point; it then proves i.0 ≡ j.0, hence mul ≡ mul3 and sub = mul − mul3 = 0. Together with SCCP's x = 1 that makes run return 1 (Lesson 17.8).

Congruence partitioning (Alpern–Wegman–Zadeck)

Alpern, Wegman and Zadeck, in one of the two 1988 papers that introduced SSA, put the question as a partition problem on the SSA value graph: start with all values of the same operator in one class and split classes whose members have operands in different classes, until nothing splits [AWZ88]. With Hopcroft's partition-refinement technique (the one that minimizes DFAs, Ch 1) this takes \(O(E \log N)\) time. The result is the coarsest stable partition, which equals the maximal congruence (Theorem 17.5.10). The lab implements it and checks that it contains every congruence DVNT finds.

Optimistic RPO and SCC-based value numbering

Simpson's thesis turned the partition idea back into hashing: iterate hash-based value numbering in reverse postorder, starting from the optimistic assumption, until the numbers stop changing; restricting the iteration to the strongly connected components of the value graph gives the SCC-based variant [Sim96, BCS97]. Click combined the same optimistic iteration with constant propagation and algebraic simplification ("combining analyses") [Cli95t, CC95]. Hashing lets these algorithms fold constants and identities during numbering, which partitioning cannot. GCC's FRE/PRE numbering is Simpson's algorithm [GCC-SCCVN].

NewGVN and predicated value numbering

Gargi's predicated GVN makes optimistic value numbering sparse (only instructions whose inputs changed are re-numbered: "touched" instructions), treats unreachable code optimistically as in SCCP, and infers values from branch predicates (inside if (a == b), b has a's value number) [Gar02]. LLVM's newgvn implements it with congruence classes, PredicateInfo for the predicates and MemorySSA for memory [LLVM-NewGVN]. Gulwani and Necula showed what complete value numbering would mean — equality of all Herbrand terms along all paths — and that it needs more than any of these algorithms [GN04].

GVN-hoist and GVN-sink

Value numbers also say when different instructions in different blocks compute the same value; moving them to one place removes code rather than computation. GVN-hoist moves computations that are equal in all successors of a block into that block (very busy expressions); GVN-sink merges equal-shaped instructions from all predecessors of a block into it, with phis for their differing operands [LLVM-GVNHoist, LLVM-GVNSink]. They reduce code size and are the value-numbering relatives of PRE (Lesson 17.6).

2. Definitions and algorithms

Definition 17.5.1 (Value graph, congruence)

The value graph of a strict SSA function has one node per value; a node is labeled with its operator (for a phi: phi and its block, and its operands ordered by incoming block), has an ordered edge to each operand, and literals and parameters are leaves labeled by themselves. A relation \(R\) on instruction values is a congruence if it is an equivalence and \(x \mathrel{R} y\) implies \(\mathrm{label}(x) = \mathrm{label}(y)\) and, for every position \(k\), the \(k\)-th operands \(a_k, b_k\) satisfy \(a_k \mathrel{R} b_k\) (instructions) or \(a_k = b_k\) (leaves). Two values are congruent if some congruence relates them. (This is the chapter's positional congruence: no commutativity, no folding.)

Congruence on run

\(\{(\text{i.0}, \text{j.0}), (\text{add}, \text{add2}), (\text{mul}, \text{mul3})\}\) with the identity is a congruence: i.0 and j.0 are both phi@while.cond with operands \((0, 0)\) equal and \((\text{add}, \text{add2})\) related; add and add2 are both add with operands related and \((1, 1)\) equal. x.0 is not congruent to i.0: its first operand is the literal 1, not 0.

Definition 17.5.2 (Stable partition)

A partition \(\Pi\) of the instruction values is label-respecting if each class has a single label, and stable if for any two values \(x, y\) in one class and every position \(k\) their \(k\)-th operands are in one class (or are the same leaf). Partitions are ordered by refinement: \(\Pi \preceq \Pi'\) if every class of \(\Pi\) lies inside a class of \(\Pi'\) ("\(\Pi'\) is coarser"). A stable label-respecting partition is exactly the set of classes of a congruence.

Algorithm 17.5.3 (Congruence partitioning, signature refinement)

• Input: the value graph of a strict SSA function.
• Output: the coarsest stable label-respecting partition \(\Pi^\ast\).
• Precondition: labels as in Definition 17.5.1.
• Postcondition: \(\Pi^\ast\) is stable, and every stable label-respecting partition refines it (Theorem 17.5.10).
• Invariant: the maximal congruence refines the current partition \(\Pi_r\) (no two congruent values are ever separated).

function Partition(F):
    Π0 ← group the instruction values by label           # round 0: optimistic
    r ← 0
    repeat:
        r ← r + 1
        for each value x: sig(x) ← (class of x in Π_{r−1}, class-or-leaf of each operand in order)
        Π_r ← group the values by sig
    until |Π_r| = |Π_{r−1}|                             # nothing split in round r
    return Π_r

scalaropt.awz is this algorithm (the drill vn-partition counts its rounds); scalaropt.awz_hopcroft is Algorithm 17.5.4, and both are checked against an independent greatest-fixed-point computation on pairs.

Algorithm 17.5.4 (Hopcroft-style splitting, as in Alpern–Wegman–Zadeck)

• Input: the value graph; for each node and operand position \(k\), the list of its users at position \(k\).
• Output: the same partition \(\Pi^\ast\) as Algorithm 17.5.3.
• Precondition: as Algorithm 17.5.3; leaves are singleton classes.
• Postcondition: \(\Pi^\ast\) (Theorem 17.5.10); \(O(E \log N)\) time (Lemma 17.5.13).
• Invariant: every class that might split some other class is on the worklist, or is the union of a class that was processed and one on the worklist.

function HopcroftPartition(F):
    classes ← values grouped by label, plus one singleton class per leaf
    W ← all classes
    while W ≠ ∅:
        S ← remove a class from W                          # the splitter
        for each operand position k:
            X ← { u : u uses some member of S at position k }
            for each class C with ∅ ≠ C ∩ X ≠ C:
                split C into C ∩ X and C \ X
                if C was in W: put both halves in W
                else: put the smaller half in W            # the log factor
    return the classes of instruction values

Definition 17.5.5 (Herbrand equivalence, completeness)

Interpret every operator as an uninterpreted function symbol. Two values \(x, y\) are Herbrand-equivalent at a program point \(p\) if on every path from the entry to \(p\) the symbolic terms they denote are equal. A value-numbering algorithm is complete for a class of programs if it finds all Herbrand equivalences. Congruence (Definition 17.5.1) implies Herbrand equivalence wherever both values are defined, but not conversely: in if (c) {x = a+b; y = a+b;} else {x = c+d; y = c+d;} the phis x, y are Herbrand-equivalent and congruent, while z = phi(a+b, c+d) and w = phi(a, c) + phi(b, d) are Herbrand-equivalent but not congruent (different labels) [GN04].

Algorithm 17.5.6 (Optimistic value numbering by iteration, Simpson's RPO algorithm)

• Input: a strict SSA function; its instructions in reverse postorder.
• Output: a number (a representative value) for every value.
• Precondition: as Algorithm 17.5.3.
• Postcondition: equal numbers ⇔ congruent (Theorem 17.5.14).
• Invariant: (Jacobi form) the partition \(Q_r\) induced by \(\mathit{VN}_r\) interleaves with the rounds of Algorithm 17.5.3: \(Q_{r+1} \preceq \Pi_r \preceq Q_r\) (Theorem 17.5.14).

function RPOValueNumbering(F):
    VN[v] ← ⊤ for every instruction value          # ⊤ matches ⊤: everything starts equal
    repeat:
        T ← empty hash table;  New ← copy of VN
        for each instruction v in RPO:
            ops ← for each operand a: (a is a literal or parameter) ? a : Cur(a)
            New[v] ← T.lookup-or-insert((label(v), ops), v)   # the first v with this key
        changed ← (New ≠ VN);  VN ← New
    until not changed
function Cur(a): return VN[a]           # Jacobi: previous iteration's number
                                        # Simpson's RPO/Gauss–Seidel form: New[a] if a was already visited

Definition 17.5.7 (Predicate and value inference)

For an edge \(e = (B, T)\) leaving br (icmp pred a, b), T, F, the edge predicate is \(a \mathbin{\mathit{pred}} b\) (and its negation on the edge to \(F\)). The predicate holds in every block dominated by \(e\) (reached only through \(e\)). Value inference uses an equality predicate \(a = b\) that holds at a use of \(b\) to give that use the value number of \(a\); predicate inference uses the predicates that hold at a block to fold comparisons inside it. NewGVN makes the per-edge copies of \(b\) explicit (PredicateInfo inserts ssa.copy intrinsics, e-SSA as in Ch 14 Lesson 14.6 §6), so a predicate is attached to a value, not to a region.

Algorithm 17.5.8 (Sparse optimistic GVN with reachability and predicates, Gargi / NewGVN, simplified)

• Input: a strict SSA function in e-SSA form (Definition 17.5.7).
• Output: congruence classes of values, reachable blocks and edges; a leader per class.
• Precondition: the symbolic evaluator Eval is monotone and sound (constant folding, simplification, predicates).
• Postcondition: a fixed point: every value's class is determined by its symbolic expression over the classes of its operands; values in unreachable blocks are in no class (Theorem 17.5.15).
• Invariant: every instruction whose operands' classes or whose block's reachability changed since its last evaluation is touched.

function NewGVN(F):
    every value starts in the class TOP; only the entry block is reachable
    Touched ← instructions of the entry block
    while Touched ≠ ∅:
        I ← the touched instruction first in RPO; untouch I
        if I is a branch or switch: mark reachable the successors its folded condition allows;
                                    touch the instructions of newly reachable blocks and their phis
        else:
            E ← Eval(I)                    # symbolic expression over leaders: a constant, another value,
                                           # a phi of reachable incoming values, or opcode(classes)
            C ← the class whose expression is E (create it if none)
            if C ≠ class(I): move I to C; touch the users of I   # also every member when a leader changes
    replace every value by the leader of its class (a constant, or a dominating member)

Algorithm 17.5.9 (GVN-hoist, simplified)

• Input: a function with value numbers; its dominator and post-dominator trees.
• Output: the function with each group of equal computations that all successors of a block perform replaced by one computation in that block.
• Precondition: value numbers are sound (equal numbers, equal values); the instructions moved are safe to execute earlier (no side effects, no traps unless all paths trap at the same point), and their operands are available at the hoisting point.
• Postcondition: every execution that performed one of the grouped computations performs the hoisted one instead; no execution performs more (Theorem 17.5.16).
• Invariant: a candidate group is a set of instructions with one value number, one in each successor region of the hoisting point.

function GVNHoist(F):
    for each value number n with ≥ 2 instructions I1..Ik:
        H ← the nearest common dominator of block(I1)..block(Ik)
        if every path from H to an exit meets exactly one of I1..Ik before any operand changes
           (the value is very busy at the end of H), and H's operands of n are available:
            move I1 to the end of H; replace I2..Ik by I1

GVN-sink is the mirror image: for a block \(J\) whose predecessors all end in instructions with the same shape, move one copy into \(J\) and turn each differing operand into a phi of \(J\).

3. Worked example

Congruence partitioning (Alpern–Wegman–Zadeck)

Algorithm 17.5.3 on run (scalaropt.awz; operands shown with their round-0 class):

round	classes with ≥ 2 members	what split, and why
0	{i.0, x.0, j.0} (phi@while.cond) · {add, add2, add4} (add) · {mul, mul3} (mul)	grouped by label; cmp, cmp1, x.1, sub alone
1	{i.0, j.0} · {add, add2} · {mul, mul3}	x.0's first operand is the literal 1, i.0's and j.0's is 0; add4 = add sub, x.0 has operands in classes {sub}, {x.0,…} while add has {i.0,…} and the literal 1
2	{i.0, j.0} · {add, add2} · {mul, mul3}	no class splits: i.0, j.0 have operands \((0, \text{add})\), \((0, \text{add2})\) in one class; add, add2 have \((\text{i.0}, 1)\), \((\text{j.0}, 1)\); mul, mul3 have \((\text{i.0}, 4)\), \((\text{j.0}, 4)\)

Round 2 splits nothing: stable, 9 classes. The three non-trivial classes are exactly what DVNT misses. With Algorithm 17.5.4 (positions counted from 0) the same partition appears after processing the leaf splitter \(\{1\}\): at position 0 it splits the phi class (only x.0 has the literal 1 there), and at position 1 it splits the add class (add and add2 have the literal 1 there, add4 has x.0); no later splitter changes anything.

Try it

./course drill vn-partition --seed 2 --difficulty medium --solution shows the rounds on a random function; hard adds the DVNT numbers for comparison.

Optimistic RPO and SCC-based value numbering

Algorithm 17.5.6 in Simpson's Gauss–Seidel form on run, blocks in RPO (entry, while.cond, while.end, while.body, if.end); numbers are named by their first value (scalaropt.rpo_vn):

iteration	while.cond	while.end	while.body / if.end	changed?
1	i.0 = phi(0, ⊤) → i.0; x.0 = phi(1, ⊤) → x.0; j.0 = phi(0, ⊤) → i.0; cmp → cmp	mul = mul(i.0, 4) → mul; mul3 = mul(i.0, 4) → mul; sub → sub; add4 → add4	cmp1 → cmp1; x.1 → x.1; add = add(i.0, 1) → add; add2 = add(i.0, 1) → add	yes (from ⊤)
2	j.0 = phi(0, add) = key of i.0 → i.0	as before	as before	no

Iteration 1 is optimistic exactly where DVNT is pessimistic: add and add2 are still ⊤, so i.0 and j.0 hash equal; iteration 2 confirms it with real numbers. Two iterations instead of AWZ's three rounds, because the Gauss–Seidel form uses numbers computed earlier in the same iteration. GCC's FRE does the same on run (the §7 box).

NewGVN and predicated value numbering

NewGVN on run does the work of SCCP and optimistic GVN in one fixed point: x.0 evaluates to phi(1, x.1) with x.1 in class TOP, so x.0 gets the constant class 1; cmp1 = ne x.0, 1 folds to false, so the edge to if.then is never marked reachable; x.1's only reachable operand is x.0: class 1. Meanwhile j.0 joins i.0's class as in the RPO trace, mul3 joins mul, sub = mul − mul simplifies to 0 and add4 = 0 + 1 to the constant 1: the whole function returns 1 (§7 box). On pred (Lesson 17.4), the predicate a == b of the edge into if.then gives the ssa.copy of b the class of a; mul b, c joins mul a, c, and sub is 0.

GVN-hoist and GVN-sink

In @hoist of the §7 box, %x = mul %a, %b (block l) and %y = mul %a, %b (block r) have one value number; the nearest common dominator of l and r is entry, the value is very busy at the end of entry (each successor computes it before any operand changes), and %a, %b are available there. GVN-hoist moves %x to entry and replaces %y by it: one multiplication instead of two copies. In @sink, both predecessors of j end with add %a, C; store …, %p with different constants; GVN-sink puts one add and one store into j and a phi [2, %r], [1, %l] for the constant.

4. Invariants and correctness

Theorem 17.5.10 (The coarsest stable partition is the maximal congruence, and Algorithm 17.5.3 computes it)

(a) There is a largest congruence \(\equiv^\ast\) (it contains every congruence), and its classes form the coarsest stable label-respecting partition. (b) Algorithm 17.5.3 returns it after at most \(N\) rounds, \(N\) the number of instruction values.

Proof

(a) The union of all congruences, closed transitively, is again a congruence: if \(x_0 R_1 x_1 R_2 \dots x_m\) with each \(R_i\) a congruence, all \(x_i\) share one label and their \(k\)-th operands form a chain in the same relations. So \(\equiv^\ast\) exists and contains every congruence; by Definition 17.5.2 its classes are stable and label-respecting, and any stable label-respecting partition is a congruence, hence refines them. (b) Invariant (\(\equiv^\ast\) refines \(\Pi_r\)): round 0 groups by label, and congruent values share one. If \(x \equiv^\ast y\) and \(\equiv^\ast\) refines \(\Pi_{r-1}\), then \(x, y\) are in one class of \(\Pi_{r-1}\) and their operands are pairwise congruent (congruence), hence pairwise in one class of \(\Pi_{r-1}\) (or equal leaves): \(\mathrm{sig}(x) = \mathrm{sig}(y)\), so they stay together in \(\Pi_r\). Refinement: \(\Pi_r\) refines \(\Pi_{r-1}\) because the signature contains the old class. Termination: each round that does not stop has strictly more classes, and there are at most \(N\): at most \(N\) rounds. At termination the numbers of classes are equal, and since \(\Pi_r\) refines \(\Pi_{r-1}\) they are equal partitions; for \(x, y\) in one class of \(\Pi_r = \Pi_{r-1}\) the signatures are equal, so operands are pairwise in one class: \(\Pi_r\) is stable, and label-respecting since it refines \(\Pi_0\). By (a) it is refined by nothing coarser that is stable, and by the invariant it is refined by \(\equiv^\ast\); so it is the classes of \(\equiv^\ast\).

Theorem 17.5.11 (Congruent values are equal)

If \(x \equiv^\ast y\) and the definitions of both dominate a program point \(p\), then on every execution reaching \(p\) the most recent values of \(x\) and \(y\) are equal.

Proof sketch (full proof: [AWZ88, §5])

Order the evaluations of an execution in time and prove, by induction on the time of the later of the two evaluations, the stronger claim: whenever \(x \equiv^\ast y\) and both have been evaluated at least once, their latest values are equal. For an operation \(x = \mathit{op}(a_1, a_2)\) just evaluated: \(y\) has the same operator and congruent operands \(b_k\); by strict SSA the latest \(a_k\), \(b_k\) were evaluated before, so by induction they are equal (or are the same leaf), and so are \(\mathit{op}\)'s results — provided \(y\)'s latest evaluation used the same operand values, which AWZ guarantee by requiring that the latest evaluations of congruent values be "in step" (their §5 uses the dominance of both definitions over \(p\) to exclude a stale \(y\) from an older loop iteration). For phis the same argument applies per incoming edge, using that congruent phis are in the same block and so take the operand of the same edge. The dominance hypothesis is essential: i.0 and j.0 of run are equal at every point both dominate, while a value computed in one loop iteration and a congruent one from the next need not be.

Check: ValueNumbering.test_congruent_values_equal_where_both_defined executes 150 random functions and compares the values of every congruent pair whose definitions dominate the returns.

Theorem 17.5.12 (Partitioning finds everything hash-based numbering finds)

Let \(\sim\) relate two values iff DVNT (Algorithm 17.4.5, positional keys, no meaningless-phi rule) gives them the same number. Then \(\sim \subseteq \equiv^\ast\), and the inclusion is strict on run.

Proof

\(\sim\) is an equivalence (equality of numbers). If \(x \sim y\) with \(x \neq y\), then \(y\) got \(x\)'s number by a table hit, so their keys are equal: the same label and, position by position, operands with the same number (the same leaf, or values related by \(\sim\)). Operands without a number count as themselves, so equal keys there mean identical operands. Hence \(\sim\) is a congruence and by Theorem 17.5.10 (a) it is contained in \(\equiv^\ast\). Strictness: i.0 \(\equiv^\ast\) j.0 (§3) but DVNT numbers them differently (Lesson 17.4, Theorem 17.4.7 (b)). The lab's unit test Compare.CorpusPrecisionOrderingAndSoundness asserts the inclusion on every corpus function, and ValueNumbering.test_dvnt_contained_in_awz on 250 random ones.

Lemma 17.5.13 (Hopcroft-style splitting)

Algorithm 17.5.4 returns \(\Pi^\ast\) in \(O(E \log N)\) time, where \(E\) is the number of value-graph edges and \(N\) the number of nodes.

Proof sketch (full proof: [AWZ88, §4], following Hopcroft's DFA minimization, Ch 1)

Correctness: every split separates values whose operands at some position lie in different classes, which the maximal congruence also separates (by the invariant of Theorem 17.5.10), so \(\equiv^\ast\) refines the result; at the end every class is stable with respect to every class that was ever a splitter, and the "process the smaller half" rule preserves this, because stability with respect to \(C\) and to one half implies stability with respect to the other half (for a fixed position, each user of \(C\) uses a member of exactly one half or of both). Time: scanning a splitter \(S\) costs its user edges; a node is in a processed splitter at most \(1 + \log_2 N\) times, since each time after the first its class is at most half of the class it was in the previous time. Summing user edges gives \(O(E \log N)\).

Theorem 17.5.14 (Optimistic iteration computes the maximal congruence)

In Jacobi form, let \(Q_r\) be the partition induced by \(\mathit{VN}_r\) after iteration \(r\) of Algorithm 17.5.6 (\(Q_0\) = one class). Then \(Q_{r+1} \preceq \Pi_r \preceq Q_r\) for every \(r \geq 0\), with \(\Pi_r\) the rounds of Algorithm 17.5.3, and the algorithm stops with the classes of \(\equiv^\ast\). (The two sequences are interleaved, not equal: \(Q_1\) already separates different leaf operands but not operands of different labels, \(\Pi_0\) does neither.)

Proof

Write \(Q_r\) for the partition induced by \(\mathit{VN}_r\) (\(Q_0\): one class, everything ⊤). In Jacobi form, \(x \mathrel{Q_r} y\) iff \(x\) and \(y\) have the same key, i.e. the same label and operands that are pairwise \(Q_{r-1}\)-related (or equal leaves). By induction, \(Q_{r}\) refines \(Q_{r-1}\) (for \(r = 1\) trivially; then, if \(Q_{r-1}\) refines \(Q_{r-2}\), operands related by \(Q_{r-1}\) are related by \(Q_{r-2}\)). Now compare with Algorithm 17.5.3's \(\Pi_r\) by induction on \(r\), proving \(\Pi_r \preceq Q_r\) and \(Q_{r+1} \preceq \Pi_r\). \(\Pi_r \preceq Q_r\): \(\Pi_0 \preceq Q_0\); if \(x \mathrel{\Pi_r} y\) then \(x, y\) are in one class of \(\Pi_{r-1} \preceq \Pi_0\) (same label) and their operands are pairwise \(\Pi_{r-1}\)-related, hence pairwise \(Q_{r-1}\)-related by the hypothesis: \(x \mathrel{Q_r} y\). \(Q_{r+1} \preceq \Pi_r\): for \(r = 0\), equal keys imply equal labels. If \(x \mathrel{Q_{r+1}} y\), then \(x \mathrel{Q_r} y\) (refinement), so \(x \mathrel{\Pi_{r-1}} y\) by the hypothesis; and their operands are pairwise \(Q_r\)-related, hence \(\Pi_{r-1}\)-related: equal signatures, \(x \mathrel{\Pi_r} y\). The two sequences are interleaved (\(Q_{r+1} \preceq \Pi_r \preceq Q_r\)). If \(Q_{r+1} = Q_r\) then \(\Pi_r = Q_r\); since \(Q_{r+1}\) is computed from \(Q_r\) alone, \(Q_{r+2} = Q_{r+1}\), so \(\Pi_{r+1} = Q_{r+1} = \Pi_r\): round \(r + 1\) of Algorithm 17.5.3 splits nothing and \(Q_r = \Pi_r\) is \(\equiv^\ast\) by Theorem 17.5.10. Conversely \(Q\) cannot keep refining after \(\Pi\) has stopped, since \(\Pi^\ast \preceq Q_r\) for all \(r\) (the first half of the induction). The representative numbers are the first member of each class in RPO, so \(\mathit{VN}\) stops changing exactly when the partition does. Simpson's Gauss–Seidel form uses fresher numbers and may converge in fewer iterations; its fixed point is stable (equal keys, pairwise related operands) and it never separates congruent values (the invariant of Theorem 17.5.10 holds for any order of updates), so it also ends at \(\equiv^\ast\) [Sim96, Ch. 3]; the course checks the equality on 400 random functions (scalaropt.rpo_vn vs scalaropt.awz).

Theorem 17.5.15 (NewGVN's fixed point is sound)

If Eval is sound (equal symbolic expressions over equal classes denote equal values; a folded constant is the value on every execution that reaches the instruction with operands in their classes; a predicate is used only where it holds), then at the fixed point of Algorithm 17.5.8 every value in a reachable block equals the leader of its class wherever the leader dominates it, and blocks marked unreachable never run.

Proof sketch (full proof: [Gar02, §4–5]; the combination of Theorems 17.1.13 and 17.5.11)

At the fixed point no instruction is touched, so every equation "class(I) = class of Eval(I)" holds and every branch's reachable successors are those its folded condition allows. Reachability is sound by the argument of Theorem 17.1.13 (an optimistic fixed point of a monotone system is a solution, and solutions over-approximate executions). Value equality follows the induction of Theorem 17.5.11, with Eval's soundness replacing "same operator"; a phi joins only reachable incoming values, as SCCP does. Predicates are attached to ssa.copy values defined on the edge, so the value inference is applied only in the region the edge dominates (Definition 17.5.7). The optimism is sound only at the fixed point: stopping early could leave two values in one class that a later touch would split, which is why NewGVN iterates until nothing is touched.

Theorem 17.5.16 (GVN-hoisting is safe and never adds computations)

Under the preconditions of Algorithm 17.5.9, the transformed program computes the same values, and on every path the number of evaluations of the hoisted value does not increase.

Proof

The hoisted value is very busy at the end of \(H\): every path from \(H\) evaluates one of \(I_1, \dots, I_k\) before any operand changes, so evaluating it at \(H\) instead yields the same value (equal value numbers; operands unchanged; operands available because they dominate \(H\)) and it is used only where one of the \(I_j\) was, all of which \(H\) dominates. Each path from \(H\) previously executed exactly one \(I_j\) before an operand change and now executes the hoisted copy once: the count is the same. The precondition on side effects and traps makes executing it earlier unobservable. Sinking is the mirror argument with "anticipated in every predecessor" and post-dominance.

Which precondition breaks it. Algebraic identities in hashing (x + 0 ≡ x) break the equivalence with AWZ, which only knows labels: the lab disables them for that reason; commutativity must be handled in both or neither. For hoisting: a udiv by a possibly-zero operand is not safe to hoist unless every path executes it before any side effect.

5. Complexity

\(N\) values, \(E\) value-graph edges (operand uses), \(n\) blocks, \(d\) loop nesting depth.

Technique	Time (worst)	Time (typical)	Space	Justification
AWZ, signature refinement (17.5.3)	\(O(N \cdot E)\): up to \(N\) rounds of \(O(E)\)	2–4 rounds	\(O(N + E)\)	Theorem 17.5.10 (b)
AWZ, Hopcroft (17.5.4)	\(O(E \log N)\)	near-linear	\(O(N + E)\)	Lemma 17.5.13
Optimistic RPO VN (17.5.6)	\(O(N \cdot E)\) in theory; \(d + 2\)-ish iterations on reducible code	2–3 iterations	\(O(N)\)	each iteration is linear; the number of iterations is bounded like round-robin dataflow (Ch 14, Theorem 14.4.6) — the SCC variant iterates only inside cycles
NewGVN / Gargi	\(O(N \cdot E)\) worst (re-touching)	touched instructions only; slower constant than GVN in practice	\(O(N + E)\) plus PredicateInfo copies	sparse iteration over touched instructions
GVN-hoist / GVN-sink	\(O(N \cdot n)\) candidate checks (dominance and very-busy queries per value number)	limited by heuristics (-gvn-hoist-max-* options)	\(O(N)\)	one candidate group per value number

Pathological family for signature refinement: a chain of \(N\) phis \(p_k = \phi(p_{k-1}, c)\) in one block, all with the same label, where only \(p_1\) differs in its leaf operand: round \(r\) separates exactly \(p_r\) from the rest, so \(N\) rounds of \(O(N)\) work: \(\Theta(N^2)\). Hopcroft's rule processes each split off singleton once: \(O(N \log N)\). At scale: the lab (ch17-compare --table --time) runs both VN algorithms over the corpus in about 0.1 ms each; NewGVN is not in LLVM's default pipeline (an option of PassBuilder, -enable-newgvn), mainly because it has had fewer years of tuning than GVN's load handling.

6. Variants and refinements

• Commutative and algebraic congruence — sort operands by class before comparing signatures, or apply identities before hashing (optimistic hashing can; pure partitioning cannot) [Cli95t, Sim96]. Trade-off: more equalities, weaker theory (identities make the relation depend on constants).
• Value-driven code motion — use the classes to move and merge computations (Simpson's value-driven redundancy elimination [Sim96], GVN-PRE in Lesson 17.6).
• Combining with constant propagation and reachability — Click's combined analysis [CC95] and NewGVN (§3) beat SCCP followed by GVN in either order (Lesson 17.8); the price is a more complex fixed point.
• Complete GVN — Gulwani and Necula's polynomial algorithm finds all Herbrand equivalences of bounded size [GN04]; not used in production compilers. Trade-off: completeness vs cost.
• Memory — NewGVN numbers MemorySSA definitions like values (memory phis get congruence classes too), so loads with congruent memory states and addresses merge [LLVM-NewGVN].
• Sinking vs hoisting heuristics — GVN-hoist is off by default in LLVM's -O2, GVN-sink runs only in some pipelines (code-size oriented); both trade code size against register pressure and scheduling freedom.

7. In real compilers

Congruence partitioning (Alpern–Wegman–Zadeck)

No production compiler runs Hopcroft partitioning on SSA today; the optimistic congruence it defines is what GCC's FRE and LLVM's NewGVN compute, by hashing. LLVM's pessimistic gvn misses it, which the following box shows on the running example.

The congruence i ≡ j: pessimistic GVN vs optimistic NewGVN

Reproduce (opt 23.1.2; run.ll from Lesson 17.1's SCCP box):

opt -passes=gvn -S run.ll | sed -n '/^while.end:/,/^}/p'
opt -passes=newgvn -S run.ll | sed -n '/^while.end:/,/^}/p'

Output:

while.end:                                        ; preds = %while.cond
  %mul = mul nsw i32 %i.0, 4
  %mul3 = mul nsw i32 %j.0, 4
  %sub = sub nsw i32 %mul, %mul3
  %add4 = add nsw i32 %sub, %x.0
  ret i32 %add4
}
while.end:                                        ; preds = %while.cond
  ret i32 1
}

What to notice: gvn hashes %j.0 = phi [0, %entry], [%add2, %if.end] before %add2 has a number, so %mul and %mul3 stay apart. NewGVN's optimistic classes (the §3 AWZ partition, plus SCCP's x = 1) make %sub = 0 and the result the constant 1.

Optimistic RPO and SCC-based value numbering

GCC: gcc/tree-ssa-sccvn.cc — do_rpo_vn iterates optimistic value numbering in RPO over the regions of a function, re-visiting loop headers until values stabilize; FRE and PRE are its clients [GCC-SCCVN].

GCC's FRE iterates a loop until i and j have one value number

Reproduce (gcc 14.2.0; run.c from Lesson 17.1):

gcc-14 -O2 -fdump-tree-fre1-details -S run.c -o /dev/null
grep -E 'Setting value number of (j_5|j_16|_14|_12)|^Iterating' run.c.*t.fre1

Output:

Setting value number of j_5 to 0 (changed)
Setting value number of j_16 to 1 (changed)
Iterating to 1 BB4
Setting value number of j_5 to i_4 (changed)
Setting value number of j_16 to i_15 (changed)
Iterating to 1 BB4
Setting value number of j_5 to i_4
Setting value number of j_16 to i_15
Setting value number of j_5 to i_4
Setting value number of _14 to 0 (changed)
Setting value number of _12 to 1 (changed)

What to notice: the first visit of the loop is optimistic (it only sees the entry values: j_5 is 0, j_16 is 1); after "Iterating to 1 BB4" the back edge is included and j_5 joins i_4, j_16 joins i_15 — the second row of the §3 RPO table. The next iteration changes nothing, and _14 = i − j gets the number 0, so run returns 1 (_12).

NewGVN and predicated value numbering

LLVM: llvm/lib/Transforms/Scalar/NewGVN.cpp — the file header cites Gargi and Simpson; NewGVN::iterateTouchedInstructions is the touched-instruction loop, performCongruenceFinding moves an instruction between CongruenceClasses, PredicateInfo provides the edge predicates [LLVM-NewGVN].

NewGVN: predicates and unreachable code

Reproduce (opt 23.1.2; pred.ll from Lesson 17.4's GVN box, run.ll from Lesson 17.1):

opt -passes=newgvn -S pred.ll | sed -n '/^if.then:/,/^}/p'
opt -passes=newgvn -S run.ll | sed -n '/^while.body:/,/^if.end:/p'

Output:

if.then:                                          ; preds = %entry
  br label %return

if.end:                                           ; preds = %entry
  br label %return

return:                                           ; preds = %if.end, %if.then
  ret i32 0
}
while.body:                                       ; preds = %while.cond
  br i1 false, label %if.then, label %if.end

if.then:                                          ; preds = %while.body
  store i8 poison, ptr null, align 1
  br label %if.end

if.end:                                           ; preds = %if.then, %while.body

What to notice: with the predicate %a == %b, both multiplications of pred joined one class and, unused, disappeared (GVN kept one, Lesson 17.4's box). In run, NewGVN proved if.then unreachable, as SCCP does, but does not delete blocks: it folds the branch condition to false and marks the dead block with store i8 poison, ptr null (undefined behavior, so a later SimplifyCFG deletes it).

GVN-hoist and GVN-sink

LLVM: llvm/lib/Transforms/Scalar/GVNHoist.cpp — GVNHoist::hoistExpressions [LLVM-GVNHoist]; llvm/lib/Transforms/Scalar/GVNSink.cpp — GVNSink::sinkBB [LLVM-GVNSink]. GCC's PRE pass has a code-hoisting mode that uses its ANTIC sets (Lesson 17.6's box, "Inserting expression in block 2 for code hoisting").

gvn-hoist and gvn-sink

Reproduce (opt 23.1.2):

cat > hoist.ll <<'EOF'
define i32 @hoist(i32 %a, i32 %b, i1 %c) {
entry:
  br i1 %c, label %l, label %r
l:
  %x = mul i32 %a, %b        ; the same computation in both arms:
  %x1 = add i32 %x, 1        ; very busy at the end of %entry
  br label %j
r:
  %y = mul i32 %a, %b
  %y1 = sub i32 %y, 1
  br label %j
j:
  %p = phi i32 [ %x1, %l ], [ %y1, %r ]
  ret i32 %p
}

define void @sink(ptr %p, i32 %a, i1 %c) {
entry:
  br i1 %c, label %l, label %r
l:
  %x = add i32 %a, 1
  store i32 %x, ptr %p       ; the same store (of different values) in both arms
  br label %j
r:
  %y = add i32 %a, 2
  store i32 %y, ptr %p
  br label %j
j:
  ret void
}
EOF
opt -passes=gvn-hoist -S hoist.ll | sed -n '/@hoist/,/^r:/p'
opt -passes=gvn-sink -S hoist.ll | sed -n '/@sink/,/^}/p'

Output:

define i32 @hoist(i32 %a, i32 %b, i1 %c) {
entry:
  %x = mul i32 %a, %b
  br i1 %c, label %l, label %r

l:                                                ; preds = %entry
  %x1 = add i32 %x, 1
  br label %j

r:                                                ; preds = %entry
define void @sink(ptr %p, i32 %a, i1 %c) {
entry:
  br i1 %c, label %l, label %r

l:                                                ; preds = %entry
  br label %j

r:                                                ; preds = %entry
  br label %j

j:                                                ; preds = %r, %l
  %.sink = phi i32 [ 2, %r ], [ 1, %l ]
  %y = add i32 %a, %.sink
  store i32 %y, ptr %p, align 4
  ret void
}

What to notice: GVN-hoist moved the mul to the common dominator (neither arm computes it any more); GVN-sink turned two stores and two adds into one each, with a phi for the only operand that differs. Plain gvn changes neither function: the two muls are siblings.

Find where LLVM does it. In llvm/lib/Transforms/Scalar/NewGVN.cpp, which function processes the worklist of touched instructions until it is empty? (Quiz llvm-where-newgvn.)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
AWZ partitioning	Maximal congruence (Theorem 17.5.10); ⊇ hash-based (17.5.12); no algebra, no constants	\(O(E \log N)\) Hopcroft; rounds × \(O(E)\) with signatures	Classes, not replacements (needs a leader choice)	Medium (partition refinement)	Theory, the lab; basis of optimistic VN
Optimistic RPO / SCC VN	Same partition, plus folding and identities during hashing	2–3 linear iterations · fast	Value numbers usable directly	Medium	GCC FRE/PRE (do_rpo_vn)
NewGVN (Gargi)	Optimistic congruence + constants + unreachable code + predicates + memory	sparse, touched instructions · slower than GVN	Replacements; unreachable blocks marked	High	LLVM newgvn (not default)
GVN-hoist / GVN-sink	Moves equal computations to a common dominator / successor; code size	per value number · cheap with limits	Fewer copies, same number of evaluations	Medium	LLVM gvn-hoist, gvn-sink; GCC code hoisting

Choose AWZ when you want the maximal congruence with a clean proof or a reference for testing (the lab uses it to check DVNT). Choose optimistic RPO/SCC VN when you need loop-carried congruences in production and want constant folding in the same pass. Choose NewGVN-style predicated GVN when reachability, constants and branch predicates should cooperate with value numbering in one fixed point. Choose hoisting and sinking when code size matters: they remove copies, not work.

9. Assessment

• Quiz: awz-rounds, awz-classes (tag awz); rpo-vn-iterations, herbrand-vs-congruence (tag optimistic-vn); newgvn-unreachable, llvm-where-newgvn (tag newgvn); gvn-hoist-busy, gvn-sink-phi (tag gvn-hoist-sink).
• Drill: ./course drill vn-partition (AWZ classes and rounds; DVNT for comparison). Optimistic RPO VN computes the same partition (Theorem 17.5.14), so the same drill practices it; NewGVN and hoisting/sinking are practiced through the quiz's concrete instances.
• Flashcards: tags awz, optimistic-vn, newgvn, gvn-hoist-sink.
• Exercises: lab Part B2 (labs/ch17-scalar/SPEC.md).

References

See the chapter references.