Implement Global Value Numbering (GVN) optimization

Description

Global Value Numbering is a compiler optimization that eliminates redundant computations across basic blocks by assigning the same value number to expressions that compute the same value. This optimization can catch redundancies that CSE (Common Subexpression Elimination) misses due to control flow.

Current Limitation

The current CSE only works within basic blocks. Identical computations in different blocks are not detected:

if (condition) {
    x = a + b * c;  // Computation 1
} else {
    y = a + b * c;  // Same computation, different block
}
z = a + b * c;      // Redundant with both above

Implementation Details

1. Value Numbering Infrastructure

typedef struct {
    enum { VN_CONST, VN_VAR, VN_BINOP, VN_UNOP, VN_PHI } type;
    union {
        int const_val;
        var_t *var;
        struct {
            int op;
            int vn1, vn2;  // Value numbers of operands
        } binop;
    };
} value_expr_t;

typedef struct {
    hashmap_t *expr_to_vn;  // Expression → value number
    hashmap_t *vn_to_leader;  // Value number → representative variable
    int next_vn;
} gvn_state_t;

2. Algorithm Steps

void run_gvn(func_t *func) {
    // Phase 1: Build dominator tree
    build_dominator_tree(func);
    
    // Phase 2: Value numbering in dominator tree order
    gvn_state_t state = init_gvn_state();
    for (bb in reverse_postorder(func)) {
        process_block_gvn(bb, &state);
    }
    
    // Phase 3: Replace redundant computations
    replace_with_leaders(&state);
}

void process_block_gvn(basic_block_t *bb, gvn_state_t *state) {
    for (insn in bb->insns) {
        value_expr_t expr = build_expr(insn);
        int vn = lookup_or_add(state->expr_to_vn, expr);
        
        if (has_leader(state, vn)) {
            // Redundant - replace with existing value
            replace_insn(insn, get_leader(state, vn));
        } else {
            // New value - record as leader
            set_leader(state, vn, insn->rd);
        }
    }
}

3. Hash Function for Expressions

uint32_t hash_expr(value_expr_t *expr) {
    switch (expr->type) {
    case VN_CONST:
        return hash_int(expr->const_val);
    case VN_BINOP:
        // Commutative operators: sort operands
        if (is_commutative(expr->binop.op)) {
            int v1 = MIN(expr->binop.vn1, expr->binop.vn2);
            int v2 = MAX(expr->binop.vn1, expr->binop.vn2);
            return hash_combine(expr->binop.op, v1, v2);
        }
        return hash_combine(expr->binop.op, 
                          expr->binop.vn1, expr->binop.vn2);
    }
}

Test Cases

// Cross-block redundancy
int test_gvn_basic(int a, int b, int c) {
    int x;
    if (c > 0) {
        x = a + b;      // VN = 1
        use(x);
    } else {
        x = a + b;      // Same VN = 1, should reuse
        use(x);
    }
    int y = a + b;      // Same VN = 1, should reuse
    return x + y;
}

// Commutative operations
int test_gvn_commutative(int a, int b) {
    int x = a + b;      // VN = 1
    int y = b + a;      // Same VN = 1 (commutative)
    return x * y;       // Should optimize to x * x
}

// Complex expressions
int test_gvn_complex(int a, int b, int c) {
    int t1 = a * b;
    int t2 = t1 + c;
    // ... other code ...
    int t3 = a * b;     // Should reuse t1
    int t4 = t3 + c;    // Should reuse t2
    return t2 + t4;     // Should optimize to t2 * 2
}

Expected Benefits

10-20% reduction in redundant computations
Better than CSE for programs with complex control flow
Enables further constant propagation
Reduces register pressure

Integration

Run after SCCP (needs constant values)
Run before DCE (creates dead code)
Complements existing CSE pass

Success Metrics

Redundant expressions eliminated across blocks
No increase in compilation time > 10%
Correct handling of side effects
Preserves program semantics

I have a working prototype of this and would like to pick it up.

Rather than restate the plan, here is what building it turned up, since parts
of the description do not match the IR as it stands at 4d3b4c0.

What the pass has to beat

cse() compares operands by pointer and scans only from the head of the
current block, so it misses two different things. The obvious one is distance:

int r = a * b;
use(r);
if (c > 0) {
    int s = a * b;   /* another block, so cse() never sees it */
    return r + s;
}

The less obvious one is that pointer equality is not value equality. Given

t1 = a + b;   t2 = a + b;
t3 = t1 + c;  t4 = t2 + c;

cse() collapses the first pair but not the second, because t1 and t2 are
different var_t. Numbering values rather than comparing names makes the
second pair collapse for free, and that recursion is the reason to do this as
GVN rather than as a wider CSE.

Two things in the description I would do differently

"Phase 1: Build dominator tree." It is already built. ssa_build() runs
build_idom() and build_dom(), and nothing between there and optimize()
invalidates them: inline_calls() copies only branch-free callees
(func_is_inlinable() refuses a body with then_ or else_), so it adds
instructions but no edges. The three passes that do rewrite the CFG --
if_convert(), thread_const_branches() and strength_reduce() -- all run
after optimize(), which is why rebuild_dom() sits at main.c:243 rather
than earlier. So the pass can read bb->dom_next directly and does not need
its own rebuild_dom().

"for (bb in reverse_postorder(func))." This is the one substantive
correction. Reverse postorder cannot express the scoping: it has no point at
which to discard what a block contributed, so an if arm's values stay
visible while the else arm is numbered, and the else arm reuses a value its
path never computed. The walk has to go down the dominator tree, pushing on
the way down and popping on the way back up -- bb_solve_phi_params() already
walks the same tree the same way for the same reason and is a usable
template.

"Run after SCCP." Worth clarifying which pass is meant. opt-sccp.c
folds only the load_constant + trunc pattern -- the comment above its
include at ssa.c:13 already notes that despite the file name there is no
lattice -- and general constant folding lives in const_folding() inside
optimize()'s instruction walk.

"Run before DCE" is right and comes for free: dce_sweep() is at the end
of optimize(), so a pass placed at the top of it is already ahead.

Where it goes

Its own file, src/opt-gvn.c, alongside opt-sccp.c, called per function near
the top of optimize(). It does not belong inside that function's instruction
walk: the walk visits blocks in reverse postorder and one instruction at a
time, and this needs a different traversal order.

What I have

A pass that numbers binary operations, walks the dominator tree with a scoped
table, normalizes commutative operands, and refuses a global or address-taken
operand exactly as cse() does. On the first example above it takes the two
multiplications in dom() down to one; the suite passes on x64, arm, arm64
and riscv at both stages.

Two things I deliberately left out, since each needs its own decision:

Phi results are not numbered, so a value both arms agree on is not
recognized at the join. Doing that needs a fixed point over loops.
Memory is not numbered. OP_load and OP_read may return a different value
each time and there is no alias analysis here to prove otherwise.

Before sending anything I would like to know whether the dominator-tree
traversal is the shape you want, and whether you would rather cse()
eventually retire into this pass or stay as it is -- its array-access case
(add + read) is load elimination rather than value numbering, so it does
not fold in cleanly either way.

@alanhc

Closing as completed. Global value numbering is implemented in VIR as vir_gvn_with_stats() in src/vir.c. It runs at the default optimization level after SCCP, CFG simplification and local CSE (see the pass list in docs/vir.md).

Both cases from this issue, and the two from @alanhc's comment, now compile to one computation each. --dump-ir at 2cbc93f:

function gvn1                         function gvn2
b0(%d0:i32, %d2:i32, %d4:i32):        b0(%d0:i32, %d2:i32, %d4:i32):
  %d8 = mul.i32 %d0, %d2                %d8 = add.i32 %d0, %d2
  ...                                   %d16 = add.i32 %d8, %d4
b2:                                     %d24 = mul.i32 %d16, %d16
  %d28 = add.i32 %d8, %d8   <- a*b      return %d24
  return %d28                  reused

Values are numbered, not variable names, so t3 = t1 + c and t4 = t2 + c fold once t1 and t2 do. This is the recursive case that pointer-equality CSE missed.

A computation that is redundant on only some paths into a join (if (f) x = a + b; y = a + b;) is still recomputed. That is partial redundancy, and it stays open as #288. @alanhc, thank you for the analysis. The legacy cse() that your prototype targeted is gone, but if you want to continue in this area, #288 is the natural next step on VIR.

Navigation Menu

Repository navigation

Implement Global Value Numbering (GVN) optimization #287

Description

Current Limitation

Implementation Details

1. Value Numbering Infrastructure

2. Algorithm Steps

3. Hash Function for Expressions

Test Cases

Expected Benefits

Integration

Success Metrics

What the pass has to beat

Two things in the description I would do differently

Where it goes

What I have

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Implement Global Value Numbering (GVN) optimization #287

Description

Description

Current Limitation

Implementation Details

1. Value Numbering Infrastructure

2. Algorithm Steps

3. Hash Function for Expressions

Test Cases

Expected Benefits

Integration

Success Metrics

Activity

alanhc commented on Sep 10, 2026

What the pass has to beat

Two things in the description I would do differently

Where it goes

What I have

jserv commented on Oct 15, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions