Value numbering
a day ago
- SSA assigns each expression a unique name, enabling clearer distinction between textually similar but different computations.
- Value numbering identifies instructions that always produce the same value, allowing reuse (e.g., via hashing instructions).
- Local value numbering (LVN) works on linear block sequences, using a hash map to find and replace duplicate pure operations.
- Global value numbering (GVN) extends across blocks, leveraging dominator relationships to share value maps for expression deduplication.
- Impure operations (like field loads) require additional bookkeeping, such as load-store forwarding or type information tracking.
- Advanced techniques include unified hash tables, value partitioning, scoped hash maps, and handling phi-functions in loops.