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

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;

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); } } }

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); } }

// 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 }