Two instructions that apply the same pure operation to the same values compute the same value. The later one is redundant wherever the earlier one’s result is guaranteed to be available. Global value numbering finds those pairs, rewrites the later computation’s uses to read the earlier result, and lets the dead definition fall to the shared elimination round.

The whole question is what guaranteed to be available means. Mica answers it with dominance.

Dominance is the scope

The pass works over static single assignment form, where every name has exactly one definition. That turns “the same values” into a comparison of operand names and literals rather than a dataflow question, and it turns availability into a dominance question: an earlier computation whose block dominates a later identical one is available at it. This is hash-based value numbering in the Cooper–Simpson style, and it uses the same availability model as the load-to-load forwarding pass beside it.

The walk visits each function’s blocks in reverse postorder, keying every eligible instruction by its operation and its canonicalized operands. Operands resolve through the growing canonical map first, so a chain of redundant computations collapses to its root, and a commutative operation sorts its operand keys so a + b and b + a number together. A hit whose representative dominates the current block maps the redundant result onto the representative’s; a miss, or a representative that does not dominate, records the current instruction as the version later occurrences are checked against.

Dominance is a real restriction, not a formality: a computation on one arm of a conditional does not serve the other, because neither dominates the other, so arm-local repeats stay.

A checked operation may trap, but a redundant occurrence is dominated by its representative, which runs first on the same values: the later occurrence is reached only if the representative did not trap, so reuse cannot mask a fault.

Literals participate as values

The generator materializes every literal at its use site, so a naive numbering would see the same index expression written twice as two unrelated expressions over two different temporaries. Mica treats a literal copy as a constant in the value space instead: its result temporary keys by the literal’s type and value wherever it appears as an operand. Equal expressions therefore coincide whatever per-site copies fed them. That is the keystone of the scheme: without it, very little in a realistic program would number at all.

The copies themselves are not merged across blocks, and that is deliberate. Merging them manufactures a live range from the first occurrence to the last reuse, which the register allocator must then carry across everything in between; a per-site copy costs one register-width move and dies at its consumer. The one exception is a float literal within a single block, which loads from read-only data rather than moving an immediate, and whose reuse is local by construction.

for row := 0 to 63 do
    for col := 0 to 63 do
    begin
        a[row * 64 + col] := row + col;
        b[row * 64 + col] := row - col;
    end;

The second scaled index is computed under the first’s dominance, so the repeated multiply and the repeated add number onto the first occurrence. The literal operands do not number themselves — they key by value, which is what lets the two index expressions coincide, and the copy that fed the second falls dead once its consumer is gone. The program’s output is identical in every optimization mode.

The compiler reports what it did

Numbering is not a silent transform. On the optimizing path the compiler prints a static-single-assignment optimization block per compilation unit, in which Redundant computations numbered is a labeled counter beside the forwarding, folding, dead-code, and bounds-check counters. Those counters are recorded as minimum test expectations and checked for agreement across both backends, so a change that stops a known redundancy from collapsing surfaces as a test failure rather than as a benchmark surprise.

Value numbering runs after forwarding and constant folding, which expose the equalities, and before constant-branch resolution, whose conditions it can only sharpen.

See also