Value numbering

What it is

Value numbering is a small miracle of compiler housekeeping. SSA gives each computation a fresh name so you stop confusing different x + 1s. Value numbering asks the next question: when do those names actually compute the same runtime value so we can reuse the result and skip work? It’s about turning “textually identical” into “semantically identical,” and that little shift can shave cycles off hot code paths.

How it works

Optimizers usually compute a canonical representation for each instruction — often a hash — and then merge equal entries (hash-consing). It has been reported that JavaScriptCore and a couple of other compilers use a destructive union-find style for this, leaving behind tiny Identity/Assign breadcrumbs until a cleanup pass collapses them. The Maxine VM’s valueNumber/valueEqual examples are a neat, readable illustration of the approach: if two binary ops have the same opcode and operands, they’re the same value and one can point at the other. Sweet, tidy, effective.

The catch: purity and exceptions

Not every operation is eligible. Why wouldn’t you dedupe everything? Because some instructions aren’t pure — loads, I/O, or anything that touches memory or the outside world depend on state and might raise exceptions. Allegedly, changing the source location of an exception is a fast way to break language contracts and developer expectations. So compilers generally restrict value numbering to side-effect-free operations, at least to start.

Why it matters

This is classic compiler thrift: reuse what you can, avoid recomputing, and keep the runtime lean. Local value numbering (LVN) applies this to straight-line code and is the low-hanging fruit; extending it across control-flow and impure ops is where things get interesting, and messy. Want a neat thought? The “aha” moment isn’t in the hash function — it’s when you realize that two previously redundant instructions are the same thing in spirit. That small victory ripples through code generation and JITs, and in performance-sensitive systems, every little victory counts.

Sources: bernsteinbear.com, Lobsters