LLVM's GVN Pass: How Value Numbering Eliminates Redundant Computation and When to Trust It

The problem GVN solves

Frontends and earlier optimization passes generate redundant IR constantly. Inlining duplicates expressions, loop unrolling repeats address computations, and naive frontend output recomputes the same value in multiple basic blocks. Running opt -O2 on typical Clang output, a large fraction of early instructions are pure duplicates of values already available in dominating blocks. Global Value Numbering (GVN) is the mid-end pass that removes them.

The useful takeaway: GVN assigns each SSA value an equivalence number based on its expression structure, not its name. Two instructions with the same opcode, operands, and flags get the same number. If the leader (the first, dominating computation) is available where a duplicate appears, the duplicate is replaced and deleted. Understanding this model tells you both what GVN will catch and why it sometimes refuses to touch code that looks obviously redundant.

Requirements the design assumes

GVN operates on SSA-form IR and leans on two invariants:

• Dominance information is current. A replacement is only legal if the leader's definition dominates every use of the duplicate. GVN queries the dominator tree; passes that invalidate it before GVN runs will either force recomputation or suppress transformations.
• Memory state is modeled conservatively. Pure scalar expressions are trivially numberable. Loads and calls are not — a load's value depends on what memory looks like at that point. GVN uses MemorySSA (in modern LLVM, roughly 3.9 onward through current releases) to decide whether two loads can share a number.

The smallest suitable design

The core algorithm is a dominator-tree walk with a hash table:

1. Walk basic blocks in dominator-tree preorder, so leaders are always seen before the blocks they dominate.
2. For each instruction, compute a value number from its opcode, operand value numbers, and relevant flags (e.g., nsw on an add is part of the identity).
3. If the number already exists in the table and the leader dominates this block, replace all uses of the duplicate with the leader and erase it.
4. On leaving a block, remove numbers scoped to that block's subtree so siblings don't see each other's values.

Loads get a number derived from the pointer operand's number plus the current MemorySSA clobber. Two loads from the same pointer with no intervening clobber share a number; a store in between changes the clobber and therefore the number. This is the trust boundary: GVN's correctness for memory operations is entirely delegated to alias analysis and MemorySSA. If AA says two pointers don't alias when they actually do (for example, because TBAA metadata was emitted incorrectly by a frontend), GVN will happily fold loads it shouldn't.

Seeing it work

Consider this IR fragment, saved as demo.ll:

define i32 @f(i32 %a, i32 %b) {
entry:
  %x = mul i32 %a, %b
  %y = mul i32 %a, %b
  %s = add i32 %x, %y
  ret i32 %s
}

Run the pass standalone (no special permissions needed; this works anywhere LLVM's opt is installed):

opt -passes=gvn -S demo.ll -o demo.opt.ll
opt -passes=verify -disable-output demo.opt.ll

The expected result is that %y disappears and both operands of the add reference %x. The second command runs the IR verifier; it should exit silently with status 0. If the multiply had been inside two different blocks where neither dominates the other, GVN would leave both in place — that is correct behavior, not a missed optimization, because neither value is available at the other's point of use.

To check what GVN does inside the full pipeline rather than in isolation:

opt -passes='default<O3>' -print-after=gvn -S demo.ll -o /dev/null 2> gvn-after.txt

This dumps the IR each time GVN completes within the O3 pipeline. Note that default<O3> runs GVN more than once, because earlier passes (inlining, instcombine) create new redundancies after the first run.

Operational checks and failure modes

• Pass didn't run or did nothing: confirm execution with -debug-pass-manager (new PM) and check that the input is actually in a form GVN can reason about — partially promoted memory (stack slots not yet through mem2reg) hides scalar redundancy behind loads and stores.
• Redundancy survives across a store: usually correct. Check whether alias analysis can prove the store doesn't clobber the loaded pointer with opt -passes=aa-eval -print-all-alias-modref-info. If AA is too conservative, the fix is better pointer metadata or restrict qualifiers, not a different GVN flag.
• Exception-handling regions: value numbering across invoke/landingpad boundaries requires care because the exceptional edge has different available values. If you maintain an out-of-tree pass that mutates EH IR before GVN, verify with opt -passes=verify and test both normal and unwind paths; this is the area where hand-rolled IR most often breaks assumptions.
• Non-determinism concerns: GVN's results are deterministic for a given IR and pass pipeline, but results differ across LLVM versions as expression canonicalization (instcombine) changes what GVN sees. Pin the LLVM version when comparing pass statistics.

When the design would change

GVN alone does not handle partial redundancy — a computation available on only some paths. That is GVNHoist and GVNSink (separate passes, off by default in some configurations) or the classic PRE (partial redundancy elimination) functionality contained in GVN itself via enable-pre. If profiling shows redundant work along hot paths that GVN leaves behind, check whether the redundancy is partial before concluding the pass is broken. Conversely, if compile time matters more than the last few percent of eliminated instructions (fast debug builds, JIT tiers), GVN is one of the passes worth dropping first, since its dominator walk and MemorySSA queries are not cheap on large functions.

Limitations

GVN reasons about expression identity, not algebraic equivalence: a + b and b + a are only unified because instcombine canonicalizes operand order first. It will not prove (a * 2) equal to (a << 1). It also cannot see through calls unless they are marked readnone/readonly and the memory model permits it. Behavior described here reflects the stable core of the pass from roughly LLVM 3.9 through the 16/17-era releases; flag names and pass-manager syntax differ between the legacy and new pass managers, so check opt --help for your installed version.