◄ WORLD V · SONNY 5DART 152 · a helldive at the net

GLOBAL VALUE NUMBERING same number, same value; compute it once

Give every expression a value number so that two expressions get the same number exactly when they are provably equal — not textually equal, congruent. Then a second a+b, or a d+b where d is a copy of a, is recognised as already computed and reused. It catches redundancy that textual matching cannot.

THE TECHNIQUE congruence, not text: hash by (op, vn, vn)

Hash each expression by its operator and the value numbers of its operands. Equal hash → equal value number → redundant. Watch a+b, a second a+b, and d+b (with d=a) all collapse to one number: live demo







  
HISTORY & CREDIT Balke/Cocke-Schwartz 1970; global form 1988

  
“GVN is just CSE.” — related but not equal. Common-subexpression elimination matches expressions by an available-expressions dataflow (roughly textual); GVN partitions by congruence of value numbers, so it sees equalities through copies and φs that textual CSE misses. cited

  
1970 · local value numbering — invented by Balke (late 1960s), described by Cocke & Schwartz (Courant notes, 1970). Cocke’s own ~1970 contribution is global common-subexpression elimination, not value numbering.
1988 · Alpern, Wegman & Zadeck — “Detecting Equality of Variables in Programs” (POPL): the global, partition-refinement congruence algorithm over SSA.
1997 · Cliff Click / Briggs-Cooper-Simpson — hash-based GVN and the RPO/dominator-scoped variants used in real compilers.

  
Congruence is a fixed point: two φs are congruent if their operands are pairwise congruent — a mutual recursion resolved by partition refinement (optimistic) rather than pessimistic worklist. Alpern-Wegman-Zadeck, 1988






  
RECOMMEND FOR I-13 redundant compute collapses

  
The equalities GVN must prove — the second a+b, and d+b through the copy d=a — hold on the canonical compiler:

  
$ i13 run gvn.i13   # a+b computed three ways, one value number
a = 6   b = 7   d = 6   (d <- a)
t1 = 13   -- a + b
t2 = 13   -- a + b   (congruent to t1 -> redundant)
t3 = 13   -- d + b   (d congruent a -> congruent to t1)

  
Recommend: GVN is LIT and a genuine win on I-13 — verified t1=t2=t3=13, so t2 and t3 are redundant computations a value-number pass can delete and replace with t1. The copy case (d=a makes d+b congruent to a+b) is exactly what textual CSE would miss, so GVN is the stronger choice; it wants SSA (150) and feeds copy-propagation (153).