- Author
- Max Bernstein
- Published
- 4 April 2026
- Kind
- Personal blog post, compiler tutorial with Java excerpts
- Original
- bernsteinbear.com/blog/value-numbering/
- Subject
- Programming languages and types
What it is
Max Bernstein writes a blog about compilers. This post explains value numbering after a short primer on SSA. It builds the idea in steps, from straight-line code to dominator-based global numbering.
What it says
- Value numbering finds SSA instructions that always compute the same value.
- Compilers usually find them by hashing each instruction and comparing hash-equal ones.
- Local value numbering needs only a hash map and a union-find, as real compilers do.
- Global value numbering visits blocks in reverse post order, copying the dominator's value map.
- Siblings and join blocks cannot share maps, because the path taken is unknown.
- Impure instructions such as field loads can join if the pass tracks killing writes.
- The post sketches variants: unified hash tables, value partitioning, worklist dataflow, and scoped hash maps.
What evidence it gives
The post shows pseudocode and short edited excerpts from the Maxine VM. It uses small IR examples and a Java bytecode listing. It quotes a paper by Briggs on phi functions. It runs no benchmarks.
Interests and limits
The post is a tutorial from one author's reading of a few implementations. It admits not understanding some approaches yet. The final section is a list of unfinished notes and links. Nothing was measured.