Implement Global Value Numbering (GVN) optimization

Start by locating the existing CSE, SCCP, DCE, dominator-tree, and basic-block implementations in the compiler. Use the three supplied test cases to examine cross-block, commutative, and chained-expression behavior. Done means redundant expressions are eliminated without semantic changes, side effects remain correct, and compilation time does not increase by more than 10%.

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