Lesson 17.4 — Hash-based redundancy elimination: EarlyCSE, dominator-based value numbering, LLVM GVN¶

Techniques: dominator-scoped CSE with scoped hash tables and memory generations (LLVM EarlyCSE); hash-based global value numbering over the dominator tree, DVNT (Briggs–Cooper–Simpson 1997); LLVM's GVN (RPO value numbering with a leader table, equality propagation, load elimination) · Pebble implements: pebble-gvn, a DVNT pass (exercise E3), and the hash half of the comparison lab (labs/ch17-scalar, Part B) · Prerequisites: local value numbering (Ch 8, Lesson 8.3 and Ch 13); dominator trees (Lesson 15.1) · Time: 5–7 hours

1. Problem and motivation¶

Two computations are redundant if the second always recomputes the value of the first; replacing the second by the first saves the work. Local value numbering (Ch 8 and Ch 13) finds redundancies inside one block by hashing each expression's operator and operand value numbers. This lesson extends the same hash table beyond a block. The running example is diamond from the lab corpus (labs/ch17-scalar/corpus/redundancy.c):

int diamond(int a, int b, int c) {
  int x = a * b + c;
  int y;
  if (c > 0)
    y = a * b - c;
  else
    y = a * b + c;
  int z = (a * b + c) * 2;
  return x + y + z;
}

In SSA (clang-23 -O0 + mem2reg, value names kept; lt 0, c is icmp sgt c, 0):

fn diamond(a, b, c):
entry:
  mul = mul a, b
  add = add mul, c
  cmp = lt 0, c
  cbr cmp, if.then, if.else
if.then:
  mul1 = mul a, b
  sub = sub mul1, c
  br if.end
if.else:
  mul2 = mul a, b
  add3 = add mul2, c
  br if.end
if.end:
  y.0 = phi [sub, if.then], [add3, if.else]
  mul4 = mul a, b
  add5 = add mul4, c
  mul6 = mul add5, 2
  add7 = add add, y.0
  add8 = add add7, mul6
  ret add8

flowchart TD
  entry([entry]) -->|T| it[if.then]
  entry -->|F| ie[if.else]
  it --> j[if.end]
  ie --> j

mul in entry dominates the three later mul a, b, so all three are redundant; add dominates add3 and add5.

Dominator-scoped CSE (EarlyCSE)¶

The simplest global extension walks the dominator tree and keeps the hash table as a stack of scopes: entering a block pushes a scope, leaving it pops the entries the block added. An expression found in the table was computed in a dominator, hence on every path to the current point, and its value is still correct because SSA values never change. LLVM's EarlyCSE does this for pure expressions, and adds loads, calls and stores through memory generations: a counter that increases at every instruction that may write memory, so a load may reuse an earlier load only if no write intervened [LLVM-EarlyCSE]. It is cheap enough to run several times in the -O2 pipeline.

Dominator-based value numbering (DVNT)¶

Briggs, Cooper and Simpson studied value numbering at increasing scopes — local, superlocal (extended basic blocks) and dominator-based — and named the dominator version DVNT [BCS97]. It is EarlyCSE without memory and with two phi rules: a phi whose operands all have the same value number is meaningless (it gets that number), and two phis in the same block with the same operand numbers are redundant. Because it walks the dominator tree once, operands that arrive over back edges have no number yet: DVNT is pessimistic at loops, and it never finds a redundancy between siblings. pebble-gvn implements DVNT; the lab measures what it misses compared to partitioning (Lesson 17.5).

LLVM's GVN¶

LLVM's gvn pass is also hash-based, but its value numbers are global rather than scoped: it numbers every instruction in reverse postorder, keeps for each number a list of leaders (defining instructions, by block) and replaces an instruction only by a leader that dominates it [LLVM-GVN]. On top of this it propagates equalities from branch conditions (inside if (a == b), b is replaced by a), eliminates redundant loads with memory dependence analysis, and performs PRE of loads and scalars (Lesson 17.6).

2. Definitions and algorithms¶

Definition 17.4.1 (Expression key, value number)

Let \(\mathit{vn} : \mathit{Val} \rightharpoonup \mathbb{N}\) assign value numbers to some SSA values, and let \(\mathit{vn}(c) = c\) for literals and \(\mathit{vn}(v) = v\) (the value itself) for values without a number. The key of an instruction \(I = \mathit{op}(a_1, \dots, a_k)\) is \(\kappa(I) = (\mathit{label}(I), \mathit{vn}(a_1), \dots, \mathit{vn}(a_k))\), where the label is the opcode with its type and predicate (for a phi: phi and its block; operands keyed by incoming block). For commutative opcodes the operand numbers may be sorted first.

Definition 17.4.2 (Redundancy)

An instruction \(J\) is fully redundant with \(I\) if \(I\) dominates \(J\) and on every execution the value computed by \(J\) equals the most recent value computed by \(I\). Replacing all uses of \(J\) by \(I\) and deleting \(J\) is then correct (Theorem 17.4.6).

Definition 17.4.3 (Scoped hash table)

A scoped hash table is a map from keys to values together with a stack of scopes; push opens a scope, insert(k, v) adds a binding recorded in the current scope (shadowing any older binding of \(k\)), and pop removes the bindings of the innermost scope, restoring shadowed ones. lookup(k) returns the innermost binding.

Algorithm 17.4.4 (EarlyCSE: dominator-scoped CSE with memory generations)

Input: a function in SSA form, its dominator tree.
Output: the function with redundant pure instructions and redundant loads replaced.
Precondition: each instruction's memory effect (none / reads / may write) is known.
Postcondition: every replacement satisfies Definition 17.4.2 (Theorem 17.4.6).
Invariant: when block \(B\) is processed, Avail holds exactly the pure expressions computed in the dominators of \(B\) and earlier in \(B\); Loads maps pointers to (value, generation) pairs from the same instructions; Gen has increased at least once since any write to memory on any path from those instructions.

function EarlyCSE(F, DT):
    Avail ← scoped hash table (key → instruction);  Loads ← scoped (pointer → (value, gen))
    Gen ← 0
    Visit(root of DT)
function Visit(B):
    push a scope on Avail and on Loads
    if B has more than one predecessor: Gen ← Gen + 1         # a write may reach B along another path
    for each instruction I of B, in order:
        if I is pure:
            if Avail.lookup(κ(I)) = J: replace I by J; continue
            Avail.insert(κ(I), I)
        else if I is a non-volatile load from p:
            if Loads.lookup(p) = (v, Gen) and v has I's type: replace I by v; continue
            Loads.insert(p, (I, Gen))
        else if I may write memory:
            Gen ← Gen + 1
            if I is a non-volatile store of v to p: Loads.insert(p, (v, Gen))    # store-to-load forwarding
    for each child C of B in DT: Visit(C)
    pop the scopes of Avail and Loads

Algorithm 17.4.5 (Dominator-based value numbering, DVNT)

Input: a strict SSA function, its dominator tree \(\mathcal{D}\); children of each node visited in reverse postorder.
Output: a value number \(\mathit{VN}(v)\) for every value; a replacement for every redundant value.
Precondition: strict SSA.
Postcondition: \(\mathit{VN}(x) = \mathit{VN}(y)\) implies \(x\) and \(y\) are congruent (Definition 17.5.1) and the one visited first dominates the other; the induced partition is contained in the maximal congruence (Theorem 17.5.12).
Invariant: when a block is visited, the table holds exactly the keys of values defined in its dominators (and earlier in the block), each mapped to the value that defined it first.

function DVNT(F):
    T ← scoped hash table;  Walk(entry)
function Walk(B):
    push a scope on T
    for each phi p in B:
        if all operands of p have the same number n (ignoring p itself): VN[p] ← n; replace p   # meaningless
        else if T.lookup(κ(p)) = q: VN[p] ← VN[q]; replace p by q                          # redundant
        else: VN[p] ← p; T.insert(κ(p), p)
    for each other instruction I in B defining a value:
        if I has side effects or reads memory: VN[I] ← I; continue
        if T.lookup(κ(I)) = J: VN[I] ← VN[J]; replace I by J
        else: VN[I] ← I; T.insert(κ(I), I)
    for each child C of B in 𝒟, in reverse postorder: Walk(C)
    pop the scope of T

scalaropt.dvnt implements this with the chapter's positional congruence and without the meaningless-phi rule (so that its classes stay comparable with AWZ in the lab); pebble-gvn implements it with both phi rules, sorted commutative operands and flag intersection.

3. Worked example¶

Dominator-based value numbering (DVNT)¶

DVNT on diamond (scalaropt.dvnt, trace rows in the order the walk visits them; dominator-tree children of entry in RPO: if.else, if.then, if.end; value numbers are named by their first value):

block	value	key	hit?	value number
entry	`mul`	`mul(a, b)`	no	mul
entry	`add`	`add(mul, c)`	no	add
entry	`cmp`	`lt(0, c)`	no	cmp
if.else	`mul2`	`mul(a, b)`	yes	mul
if.else	`add3`	`add(mul, c)`	yes	add
if.then	`mul1`	`mul(a, b)`	yes	mul
if.then	`sub`	`sub(mul, c)`	no	sub
if.end	`y.0`	`phi@if.end(sub, add)`	no	y.0
if.end	`mul4`	`mul(a, b)`	yes	mul
if.end	`add5`	`add(mul, c)`	yes	add
if.end	`mul6`	`mul(add, 2)`	no	mul6
if.end	`add7`	`add(add, y.0)`	no	add7
if.end	`add8`	`add(add7, mul6)`	no	add8

Scopes: after if.else is finished its scope (holding nothing new: both hits) is popped before if.then; sub is inserted in if.then's scope and popped before if.end. Note add3 gets the number of add because mul2 got the number of mul: the key uses numbers, not names. Five redundancies: mul1, mul2, mul4 → mul; add3, add5 → add. The phi y.0 becomes phi [sub, if.then], [add, if.else]. Partitioning (Lesson 17.5) finds exactly the same classes here (scalaropt.awz); on the running example run it finds i.0 ≡ j.0, which DVNT misses (Lesson 17.5 §3).

Try it

./course drill vn-partition --seed 2 --difficulty hard --solution prints a DVNT trace in this format next to the AWZ partition.

Dominator-scoped CSE (EarlyCSE)¶

Algorithm 17.4.4 on one block of the §7 box, with p noalias (restrict), @g a global and touch an unknown call. Generations start at 0:

instruction	action	Gen	Avail / Loads after
`%mul = mul a, b`	insert	0	mul(a,b)→%mul
`%0 = load p`	insert	0	p→(%0, 0)
`%add = add %mul, %0`	insert	0	+ add(%mul,%0)→%add
`store 1, @g`	may write: Gen+1; forward	1	@g→(1, 1)
`%mul1 = mul a, b`	hit	1	replace by %mul
`%1 = load p`	p→(%0, 0), but Gen = 1 ≠ 0	1	miss: insert p→(%1, 1)
`call @touch()`	may write: Gen+1	2
`%2 = load p`	p→(%1, 1), Gen = 2	2	miss

Plain generations lose both loads, because any write bumps the counter. With MemorySSA (early-cse<memssa>), isSameMemGeneration asks whether the write in between actually clobbers p; noalias says no, so %1 and %2 both become %0 and the expressions add %mul1, %1, add %mul4, %2 hash to %add: the §7 box.

LLVM's GVN¶

On pred of the §7 box, GVN numbers %a, %b, %c, then %cmp = icmp eq %a, %b and the branch. Entering if.then over the true edge, propagateEquality records %b ≡ %a for the blocks dominated by that edge (the edge's target has a single predecessor), so %mul1 = mul %b, %c gets the key of %mul = mul %a, %c, finds a dominating leader and is replaced; %sub = sub %mul, %mul folds to 0 during value numbering, and the phi in return becomes phi [0, if.then], [0, if.end] = 0. DVNT and EarlyCSE know nothing about %a == %b and keep both multiplications.

4. Invariants and correctness¶

Theorem 17.4.6 (Dominating equal keys give full redundancies)

In a strict SSA function, let \(I\) dominate \(J\), and let \(\kappa(I) = \kappa(J)\) under value numbers such that equal numbers imply equal values at every point where both are defined. If \(I\) and \(J\) are pure (no memory access, no side effect, cannot trap or trapping is identical), then \(J\) is fully redundant with \(I\), and replacing \(J\) by \(I\) preserves behavior (after intersecting poison-generating flags).

Proof

Every execution that reaches \(J\) passed \(I\) first (dominance). The operands of \(J\) have the same value numbers as those of \(I\) position by position (equal keys; for sorted commutative keys, up to a permutation, which the opcode's commutativity makes irrelevant), so at \(J\) they hold the same values as \(I\)'s operands did — SSA values are never reassigned, so "the value of \(a\) at \(I\)" is "the value of \(a\)". A pure operation is a function of its operands and label, so \(J\) computes \(I\)'s value. Replacing \(J\)'s uses by \(I\) is legal because \(I\) dominates \(J\), hence all of \(J\)'s uses (strict SSA). Flags: if \(I\) carries nsw and \(J\) does not, \(I\) may produce poison where \(J\) produced a value; dropping the flags not present on both (andIRFlags) makes \(I\) refine both. A division by zero traps at \(I\) first, so reusing its value at \(J\) removes no trap.

Theorem 17.4.7 (DVNT is correct and pessimistic)

Algorithm 17.4.5 terminates in one walk. (a) If \(\mathit{VN}(x) = \mathit{VN}(y)\) then \(x\) and \(y\) have equal values whenever both are defined, and the first-visited dominates the second. (b) There are congruent pairs it misses: values in sibling subtrees, and values whose congruence depends on a back edge.

Proof

Termination: each block is walked once (the dominator tree is a tree). (a) By induction on the walk. The invariant of the algorithm box holds: a scope is pushed on entry to \(B\) and popped on exit, so at \(B\) the table holds exactly the entries from \(B\)'s ancestors, i.e. its dominators (Ch 15, Theorem 15.1.6). A new number is only ever the value itself. A hit for \(I\) returns a \(J\) inserted in a dominator (or earlier in \(B\)) with the same key, whose operands, by the induction hypothesis, have numbers that imply equal values; Theorem 17.4.6 gives equal values and dominance. Meaningless phis: all operands carry the same number, hence the same value on every incoming edge, so the phi equals that value. Redundant phis in one block: same incoming numbers per predecessor, hence the same value on every entry. (b) Witnesses: mul1 and mul2 in if.then/if.else of a diamond without the mul in entry (siblings; the lab's siblings function), and i.0/j.0 in run — when while.cond is walked, add and add2 have no numbers yet, so the keys phi(0, add) and phi(0, add2) differ.

Theorem 17.4.8 (Memory generations are sound)

In Algorithm 17.4.4, a load replaced by a value \(v\) recorded with generation \(g\) at a point dominating it reads the value \(v\) on every execution.

Proof

\(v\) was recorded at an instruction \(X\) (a load of \(p\), or a store of \(v\) to \(p\)) that dominates the load \(L\), with generation \(g = \mathit{Gen}\) at \(L\). The counter never decreases, and the walk visits every instruction on the dominator-tree path from \(X\) to \(L\) between visiting \(X\) and visiting \(L\); so equal generations mean that no instruction after \(X\) in its block, before \(L\) in its block, or in a block strictly between them on the tree path may write memory, and that every block \(C_1, \dots, C_k\) on the tree path after \(\mathrm{block}(X)\) has a single predecessor (entering a block with several predecessors increments the counter). A block with a single predecessor has that predecessor as its immediate dominator, so the only edge into \(C_{i}\) is \(C_{i-1} \to C_i\) (with \(C_0 = \mathrm{block}(X)\)). Now take an execution reaching \(L\) and the last execution of \(X\) before it (one exists: \(X\) dominates \(L\)). From there the run cannot re-enter \(\mathrm{block}(X)\) (it would execute \(X\) again), so it enters \(C_1\) from \(C_0\) directly, then each \(C_i\) from \(C_{i-1}\): it runs exactly the instructions after \(X\), the blocks \(C_1, \dots, C_{k-1}\) and the instructions before \(L\), none of which may write memory. Memory at \(p\) is unchanged, and \(L\) reads what that execution of \(X\) read or wrote.

Theorem 17.4.9 (LLVM GVN's leader replacement is sound)

If GVN's value table assigns equal numbers only to values that are equal wherever both are defined, and findLeader returns only leaders that dominate the query point, then every replacement preserves behavior. Equality propagation is sound: in blocks dominated by the true edge of br (icmp eq a, b), \(a = b\).

Proof sketch (full argument: [LLVM-GVN], GVNPass::propagateEquality and findLeader; [BCS97, §4])

The value table is a hash-based congruence like DVNT's (operands are numbered before their users in RPO, except over back edges, which get fresh numbers: pessimistic), so equal numbers imply equal values by the induction of Theorem 17.4.7 (a); dominance of the leader makes the replacement legal as in Theorem 17.4.6. For equalities: a block dominated by the edge \(e = (B, T)\) of br (icmp eq a, b) is reached only through \(e\) (that is what edge dominance means, and GVN requires \(T\) to have a single predecessor or checks edge dominance), and on \(e\) the comparison was true, so \(a = b\) holds there; SSA values do not change, so it holds in all such blocks. Replacing \(b\) by \(a\) there is the sound direction when \(a\) dominates.

Which precondition breaks it. Hashing loads or calls without a memory model (a load is not pure); scoping by blocks instead of the dominator tree (a sibling's value would leak); commutative sorting for non-commutative operators; reusing a value with stronger flags without intersecting them (poison).

5. Complexity¶

\(I\) instructions, \(U\) operand uses, \(n\) blocks; hashing is expected \(O(1)\) per key of length \(k\).

Technique	Time (worst)	Time (typical)	Space	Justification
EarlyCSE	\(O(I + U)\) expected, plus MemorySSA clobber queries capped by `-earlycse-mssa-optimization-cap`	linear, one walk	\(O(I)\)	each instruction hashed once; scopes add and remove each entry once
DVNT	\(O(I + U)\) expected	linear	\(O(I)\)	one dominator-tree walk; each key built from \(k\) operand numbers
LLVM GVN	\(O(I + U)\) for numbering per iteration, iterated until no change; plus memory dependence queries	1–2 iterations; memdep dominates the cost	\(O(I)\)	`iterateOnFunction` repeats while something changed

Pathological family. Hash-based numbering is linear on every input, but its results degrade: a chain of \(k\) loops each copying twin induction variables (i = i + 1; j = j + 1) leaves \(2k\) distinct phis where \(k\) classes exist; DVNT and GVN find 0 of the \(k\) congruences, AWZ all of them (Lesson 17.5). The table in the lab (ch17-compare --table) shows it on real code: on the corpus hash-based VN finds 15 redundant candidates and partitioning 26. At scale: EarlyCSE runs twice in LLVM 23's default<O2> pipeline (opt -passes='default<O2>' -print-pipeline-passes) [LLVM-Pipelines] because it is the cheapest cleanup after inlining and loop passes; GVN is one of the more expensive scalar passes, mainly because of load analysis.

Superlocal value numbering — hash across an extended basic block (a tree of single-predecessor blocks) with a stack of tables; the step between LVN and DVNT [BCS97, EaC3 Ch. 8]. Trade-off: no dominator tree needed, fewer redundancies.
Commutativity and simplification in the key — sort operands of commutative operators, fold constants and identities before hashing (EarlyCSE calls simplifyInstruction; GVN folds sub x, x). Trade-off: more hits; the lab disables it to compare with AWZ.
Memory-aware keys — memory generations (EarlyCSE), MemorySSA versions as operands (EarlyCSE <memssa>, NewGVN), memory dependence queries (GVN). Trade-off: precision vs query cost (Ch 19).
Predicate inference — GVN's propagateEquality, EarlyCSE's single-predecessor condition facts (the branch condition is known true in the taken successor). Trade-off: only equalities, only dominated regions.
Optimistic hash-based numbering — iterate RPO numbering, starting from "all values are equal" at back edges (Simpson's RPO/SCC VN [Sim96], GCC's do_rpo_vn [GCC-SCCVN]): finds loop congruences; Lesson 17.5 treats it with partitioning.
Value-based PRE — GVN's numbers also drive load PRE and scalar PRE (Lesson 17.6).

7. In real compilers¶

Dominator-scoped CSE (EarlyCSE)¶

LLVM: llvm/lib/Transforms/Scalar/EarlyCSE.cpp — EarlyCSE::run walks the dominator tree with an explicit stack of StackNodes, each holding scopes of the ScopedHashTables for simple values, loads (LoadValue with a generation), calls and GEPs; processNode bumps CurrentGeneration at blocks with several predecessors and at writes; isSameMemGeneration consults MemorySSA [LLVM-EarlyCSE].

EarlyCSE with and without MemorySSA

Reproduce (clang 23.1.2, opt 23.1.2):

cat > cse.c <<'EOF'
int g;
void touch(void);

int cse(int *restrict p, int a, int b) {
  int x = a * b + p[0];
  g = 1;                  // p is restrict: this store cannot change p[0]
  int y = a * b + p[0];
  touch();                // nor can this call: *p is only reachable through p
  int z = a * b + p[0];
  return x + y + z;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm cse.c -o cse.O0.ll
opt -passes=mem2reg -S cse.O0.ll -o cse.ll
opt -passes=early-cse -S cse.ll | sed -n '/^entry:/,/^}/p'
opt -passes='early-cse<memssa>' -S cse.ll | sed -n '/^entry:/,/^}/p'

Output:

entry:
  %mul = mul nsw i32 %a, %b
  %0 = load i32, ptr %p, align 4
  %add = add nsw i32 %mul, %0
  store i32 1, ptr @g, align 4
  %1 = load i32, ptr %p, align 4
  %add3 = add nsw i32 %mul, %1
  call void @touch()
  %2 = load i32, ptr %p, align 4
  %add6 = add nsw i32 %mul, %2
  %add7 = add nsw i32 %add, %add3
  %add8 = add nsw i32 %add7, %add6
  ret i32 %add8
}
entry:
  %mul = mul nsw i32 %a, %b
  %0 = load i32, ptr %p, align 4
  %add = add nsw i32 %mul, %0
  store i32 1, ptr @g, align 4
  call void @touch()
  %add7 = add nsw i32 %add, %add
  %add8 = add nsw i32 %add7, %add
  ret i32 %add8
}

What to notice: without MemorySSA the two mul a, b are gone but every load stays: the store and the call each bump the generation (the §3 table). With MemorySSA, noalias proves neither clobbers *p, so the loads merge and then the whole expression a * b + p[0] is found three times.

Dominator-based value numbering (DVNT)¶

GCC's dominator optimizer tree-ssa-dom.cc walks the dominator tree with a stack of available expressions (avail_exprs_stack) and replaces redundant expressions by dominating ones: DVNT plus jump threading and copy propagation. LLVM has no pass that is exactly DVNT (EarlyCSE is DVNT with memory, without the phi rules); pebble-gvn is.

GCC's dominator optimizer on the running example of this lesson

Reproduce (gcc 14.2.0; redundancy.c from labs/ch17-scalar/corpus/):

cp labs/ch17-scalar/corpus/redundancy.c .
gcc-14 -O2 -fno-tree-fre -fno-tree-pre -fno-code-hoisting -fdump-tree-dom2-details -S redundancy.c -o /dev/null
grep -m 5 'Replaced redundant' redundancy.c.*t.dom2

Output:

  Replaced redundant expr 'a_8(D) * b_9(D)' with '_1'
  Replaced redundant expr '_1 + c_10(D)' with 'x_11'
  Replaced redundant expr 'a_8(D) * b_9(D)' with '_1'
  Replaced redundant expr 'a_8(D) * b_9(D)' with '_1'
  Replaced redundant expr '_1 + c_10(D)' with 'x_11'

What to notice: with GCC's value-numbering passes (FRE, PRE) turned off, the dominator walk finds exactly the five redundancies of the §3 DVNT trace: three a * b and two a * b + c; the second replacement uses the value number _1, not the name _3, in the key. The sub in the other arm is not redundant with anything.

LLVM's GVN¶

LLVM: llvm/lib/Transforms/Scalar/GVN.cpp — GVNPass::ValueTable::lookupOrAdd (hash-based numbers), the LeaderMap and findLeader (dominating leaders), propagateEquality, processNonLocalLoad and PerformLoadPRE (Lesson 17.6), performScalarPRE [LLVM-GVN]. GCC's counterpart is FRE (tree-ssa-sccvn.cc, do_rpo_vn), optimistic rather than pessimistic [GCC-SCCVN].

GVN uses the branch condition; EarlyCSE does not

Reproduce (clang 23.1.2, opt 23.1.2):

cat > pred.c <<'EOF'
int pred(int a, int b, int c) {
  if (a == b) {
    int x = a * c;
    int y = b * c;      // a == b here, so y == x
    return x - y;
  }
  return 0;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm pred.c -o pred.O0.ll
opt -passes=mem2reg -S pred.O0.ll -o pred.ll
opt -passes=early-cse -S pred.ll | sed -n '/^if.then:/,/^if.end:/p'
opt -passes=gvn -S pred.ll | sed -n '/^if.then:/,/^}/p'

Output:

if.then:                                          ; preds = %entry
  %mul = mul nsw i32 %a, %c
  %mul1 = mul nsw i32 %b, %c
  %sub = sub nsw i32 %mul, %mul1
  br label %return

if.end:                                           ; preds = %entry
if.then:                                          ; preds = %entry
  %mul = mul nsw i32 %a, %c
  br label %return

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

return:                                           ; preds = %if.end, %if.then
  ret i32 0
}

What to notice: GVN learned %b = %a on the edge into if.then, so mul %b, %c got the number of mul %a, %c, the subtraction became sub x, x = 0 and the phi at return merged 0 with 0. EarlyCSE (and DVNT) hash %b and %a as different values. %mul itself is left for DCE.

Find where LLVM does it. In llvm/lib/Transforms/Scalar/EarlyCSE.cpp, find the counter that processNode increments when a block has more than one predecessor. What is it called, and what does a mismatch of its value between a load and an earlier load mean? (Quiz llvm-where-earlycse-generation.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
EarlyCSE	Dominated redundancies of pure ops, loads (generations or MemorySSA), calls; simplification	\(O(I + U)\) · the cheapest global CSE	Replaces with dominating values	Low–medium	Cleanup between LLVM passes (2× in `default<O2>`)
Dominator-based VN (DVNT)	Dominated redundancies + meaningless/redundant phis; pessimistic at back edges; misses siblings	\(O(I + U)\) · one walk	Value numbers + replacements	Low	`pebble-gvn`; GCC `dom`; teaching
LLVM GVN	DVNT-like numbering + equality propagation + load elimination + PRE	\(O(I + U)\) per iteration + memdep · the most expensive of the three	Replacements, PRE insertions	High	LLVM `gvn` at `-O2`

Choose EarlyCSE when you need a fast cleanup that also handles memory. Choose DVNT when you want the simplest global value numbering with a clean correctness argument, or when hash-based numbering is all you can afford. Choose GVN (hash-based with leaders and equalities) when loads and branch facts matter and you can pay for memory dependence; choose partition-based or optimistic VN (Lesson 17.5) when loop-carried congruences matter.

9. Assessment¶

Quiz: earlycse-generations, llvm-where-earlycse-generation (tag early-cse); dvnt-classes, dvnt-siblings (tag dvnt); gvn-equality, gvn-leaders (tag llvm-gvn).
Drill: ./course drill vn-partition --difficulty hard (the [dvnt] section is DVNT). EarlyCSE's generations and GVN's equalities have no drill of their own: they add one counter and one table to DVNT, and the quiz asks for them on concrete code.
Flashcards: tags early-cse, dvnt, llvm-gvn.
Exercises: E3 pebble-gvn; lab Part B1 (labs/ch17-scalar/SPEC.md).

References¶

See the chapter references.

Lesson 17.4 — Hash-based redundancy elimination: EarlyCSE, dominator-based value numbering, LLVM GVN¶

1. Problem and motivation¶

Dominator-scoped CSE (EarlyCSE)¶

Dominator-based value numbering (DVNT)¶

LLVM's GVN¶

2. Definitions and algorithms¶

3. Worked example¶

Dominator-based value numbering (DVNT)¶

Dominator-scoped CSE (EarlyCSE)¶

LLVM's GVN¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

7. In real compilers¶

Dominator-scoped CSE (EarlyCSE)¶

Dominator-based value numbering (DVNT)¶

LLVM's GVN¶

8. Comparison¶

9. Assessment¶

References¶