A deep dive into value numbering as a compiler optimization technique. Covers local value numbering (LVN) for basic blocks using hash-consing, then extends to global value numbering (GVN) across control flow using dominator trees. Uses Maxine VM's Java implementation as a reference. Explains why pure vs. impure instructions matter, how phi-functions complicate loop handling, and how load-store forwarding can be integrated into GVN. Also surveys alternative approaches including unified hash tables, value partitioning, scoped hash maps (Cranelift), and worklist dataflow methods.
Table of contents
Eliminating common subexpressionsPure vs impureLocal value numberingGlobal value numberingState management and invalidationOut in the worldWrapping up; bits and bobblesSort: