solar_codegen/transform/
gvn.rs

1//! Congruence-class global value numbering.
2//!
3//! Unlike CSE, which keys expressions by operand `ValueId` and therefore only
4//! unifies expressions whose operands were already collapsed, this pass builds
5//! congruence classes first: two values are congruent when they compute the
6//! same pure expression over pairwise-congruent operands. That catches
7//! transitive congruence (`a = x + y; b = x + y; c = a * 2; d = b * 2` makes
8//! `d` congruent to `c`) and phi congruence (two phis in one block with
9//! pairwise-congruent incoming values).
10//!
11//! ## Algorithm
12//!
13//! Value numbering is pessimistic and iterated to a fixed point (Simpson's RPO
14//! algorithm). A value number is represented by its class representative
15//! `ValueId`:
16//! - Initially every value is its own class, except equal immediates (same payload, hence same
17//!   value and `MirType`) and function arguments with the same index, which share a class. Each
18//!   `Undef` stays unique.
19//! - Each sweep walks all instructions in reverse postorder and recomputes each result's class from
20//!   a per-sweep hash-consing table keyed by the instruction's expression over its operands'
21//!   current classes, plus the result `MirType` so differently-typed results never merge.
22//!   Commutative operands are sorted by class; `gt`/`sgt` key as the swapped `lt`/`slt`.
23//! - A phi keys as its block plus the per-predecessor incoming classes; a phi whose incoming values
24//!   all share one class joins that class directly.
25//! - Sweeps repeat until no class changes, with a hard cap. If the cap is hit before convergence
26//!   the numbering is discarded: only a converged fixed point has a self-consistent congruence
27//!   proof, and bailing only loses optimization.
28//!
29//! Only pure word expressions (and `calldataload`/`blockhash`/`blobhash`,
30//! which are pure within one execution) participate. Memory, storage, and
31//! account-environment reads, `gas`/`msize`/`returndatasize`, and calls never
32//! merge here; CSE keeps covering those with its clobber tracking.
33//!
34//! ## Replacement
35//!
36//! A dominator-tree preorder walk (over reachable blocks only) carries a
37//! scoped leader map from class to the first value of that class seen on the
38//! current tree path. An instruction whose class already has an in-scope
39//! leader is removed and its result redirected to the leader; otherwise it
40//! becomes the leader for its subtree. Sibling subtrees never see each other's
41//! leaders, so congruent values without a dominance relation are left alone.
42//! Classes represented by an immediate, argument, or undef are pre-seeded with
43//! that value, which folds phi-of-same over constants. Orphaned arena entries
44//! are left behind for DCE, matching the other passes.
45
46use crate::{
47    analysis::CfgInfo,
48    mir::{
49        BlockId, Function, Immediate, InstId, InstKind, MirType, Value, ValueId, utils as mir_utils,
50    },
51    pass::FunctionPass,
52};
53use solar_data_structures::map::{FxHashMap, FxHashSet};
54
55/// Hard cap on value-numbering sweeps per round.
56const MAX_VN_SWEEPS: usize = 10;
57/// Hard cap on whole-pass rounds (number, then replace) per function.
58const MAX_ROUNDS: usize = 4;
59
60/// A value number, named by its congruence-class representative.
61type ClassId = ValueId;
62
63/// Congruence-class global value numbering pass.
64#[derive(Debug, Default)]
65pub struct GlobalValueNumberer {
66    /// Number of instructions folded onto a congruent leader.
67    pub eliminated_count: usize,
68}
69
70/// Function pass for congruence-class global value numbering.
71pub struct GvnPass;
72
73impl FunctionPass for GvnPass {
74    fn name(&self) -> &str {
75        "gvn"
76    }
77
78    fn run_on_function(&mut self, func: &mut Function) -> bool {
79        GlobalValueNumberer::new().run(func) != 0
80    }
81}
82
83/// A hash-consing key for one instruction: its expression over operand
84/// classes plus the result type.
85#[derive(Clone, Debug, PartialEq, Eq, Hash)]
86struct ExprKey {
87    kind: ExprKind,
88    /// Result type; differently-typed results never merge.
89    ty: MirType,
90}
91
92/// An expression shape over operand congruence classes.
93#[derive(Clone, Debug, PartialEq, Eq, Hash)]
94enum ExprKind {
95    Add(ClassId, ClassId),
96    Sub(ClassId, ClassId),
97    Mul(ClassId, ClassId),
98    Div(ClassId, ClassId),
99    SDiv(ClassId, ClassId),
100    Mod(ClassId, ClassId),
101    SMod(ClassId, ClassId),
102    Exp(ClassId, ClassId),
103    AddMod(ClassId, ClassId, ClassId),
104    MulMod(ClassId, ClassId, ClassId),
105    And(ClassId, ClassId),
106    Or(ClassId, ClassId),
107    Xor(ClassId, ClassId),
108    Not(ClassId),
109    Shl(ClassId, ClassId),
110    Shr(ClassId, ClassId),
111    Sar(ClassId, ClassId),
112    Byte(ClassId, ClassId),
113    /// Also keys `Gt(a, b)`, normalized as `Lt(b, a)`.
114    Lt(ClassId, ClassId),
115    /// Also keys `SGt(a, b)`, normalized as `SLt(b, a)`.
116    SLt(ClassId, ClassId),
117    Eq(ClassId, ClassId),
118    IsZero(ClassId),
119    Select(ClassId, ClassId, ClassId),
120    SignExtend(ClassId, ClassId),
121    CalldataLoad(ClassId),
122    BlockHash(ClassId),
123    BlobHash(ClassId),
124    LoadImmutable(u32),
125    Phi(BlockId, Vec<(BlockId, ClassId)>),
126}
127
128struct ReplaceCtx<'a> {
129    vn: &'a [ClassId],
130    cfg: &'a CfgInfo,
131    inst_results: &'a FxHashMap<InstId, ValueId>,
132    replacements: &'a mut FxHashMap<ValueId, ValueId>,
133    dead: &'a mut FxHashSet<InstId>,
134}
135
136impl GlobalValueNumberer {
137    /// Creates a new GVN pass.
138    pub fn new() -> Self {
139        Self::default()
140    }
141
142    /// Runs GVN on a function to a fixed point of number-then-replace rounds.
143    /// Returns the number of instructions eliminated.
144    pub fn run(&mut self, func: &mut Function) -> usize {
145        self.eliminated_count = 0;
146        for _ in 0..MAX_ROUNDS {
147            if !self.run_round(func) {
148                break;
149            }
150        }
151        self.eliminated_count
152    }
153
154    /// Runs one numbering and replacement round. Returns true if MIR changed.
155    fn run_round(&mut self, func: &mut Function) -> bool {
156        let cfg = CfgInfo::new(func);
157        let inst_results = func.inst_results();
158        let Some(vn) = Self::compute_value_numbers(func, cfg.rpo(), &inst_results) else {
159            return false;
160        };
161
162        // Immediates, arguments, and undefs are available everywhere, so their
163        // classes start with a leader. This folds phi-of-same over constants.
164        let mut leaders: FxHashMap<ClassId, ValueId> = FxHashMap::default();
165        for (value_id, value) in func.values.iter_enumerated() {
166            if !matches!(value, Value::Inst(_)) && vn[value_id.index()] == value_id {
167                leaders.insert(value_id, value_id);
168            }
169        }
170
171        let mut replacements = FxHashMap::default();
172        let mut dead = FxHashSet::default();
173        let mut ctx = ReplaceCtx {
174            vn: &vn,
175            cfg: &cfg,
176            inst_results: &inst_results,
177            replacements: &mut replacements,
178            dead: &mut dead,
179        };
180        self.replace_in_block(func, func.entry_block, &mut leaders, &mut ctx);
181
182        if replacements.is_empty() {
183            return false;
184        }
185        Self::apply_replacements_to_all_blocks(func, &replacements);
186        for block in func.blocks.iter_mut() {
187            block.instructions.retain(|id| !dead.contains(id));
188        }
189        true
190    }
191
192    // ----- value numbering -----
193
194    /// Computes a converged congruence-class assignment, or `None` if the
195    /// sweep cap was hit first.
196    fn compute_value_numbers(
197        func: &Function,
198        rpo: &[BlockId],
199        inst_results: &FxHashMap<InstId, ValueId>,
200    ) -> Option<Vec<ClassId>> {
201        let mut vn: Vec<ClassId> = func.values.indices().collect();
202        let mut immediate_reps: FxHashMap<Immediate, ValueId> = FxHashMap::default();
203        let mut arg_reps: FxHashMap<u32, ValueId> = FxHashMap::default();
204        for (value_id, value) in func.values.iter_enumerated() {
205            match value {
206                Value::Immediate(imm) => {
207                    vn[value_id.index()] = *immediate_reps.entry(imm.clone()).or_insert(value_id);
208                }
209                Value::Arg { index, .. } => {
210                    vn[value_id.index()] = *arg_reps.entry(*index).or_insert(value_id);
211                }
212                Value::Inst(_) | Value::Undef(_) | Value::Error(_) => {}
213            }
214        }
215
216        for _ in 0..MAX_VN_SWEEPS {
217            let mut table: FxHashMap<ExprKey, ClassId> = FxHashMap::default();
218            let mut changed = false;
219            for &block_id in rpo {
220                for &inst_id in &func.blocks[block_id].instructions {
221                    let Some(&result) = inst_results.get(&inst_id) else { continue };
222                    let inst = &func.instructions[inst_id];
223                    let Some(ty) = inst.result_ty else { continue };
224                    let Some(class) =
225                        Self::instruction_class(block_id, &inst.kind, ty, result, &vn, &mut table)
226                    else {
227                        continue;
228                    };
229                    if vn[result.index()] != class {
230                        vn[result.index()] = class;
231                        changed = true;
232                    }
233                }
234            }
235            if !changed {
236                return Some(vn);
237            }
238        }
239        None
240    }
241
242    /// Returns the class for one instruction's result given the current
243    /// numbering, or `None` for instructions that never participate.
244    ///
245    /// Participating instructions always get a class (falling back to their
246    /// own result), so a stale merge from an earlier sweep cannot survive a
247    /// sweep that no longer justifies it.
248    fn instruction_class(
249        block_id: BlockId,
250        kind: &InstKind,
251        ty: MirType,
252        result: ValueId,
253        vn: &[ClassId],
254        table: &mut FxHashMap<ExprKey, ClassId>,
255    ) -> Option<ClassId> {
256        if let InstKind::Phi(incoming) = kind {
257            let Some((&(_, first), rest)) = incoming.split_first() else { return Some(result) };
258            // Phi-of-same: a phi over one class is that class.
259            if rest.iter().all(|&(_, value)| vn[value.index()] == vn[first.index()]) {
260                return Some(vn[first.index()]);
261            }
262            let Some(incoming) = Self::phi_key_incoming(incoming, vn) else { return Some(result) };
263            let key = ExprKey { kind: ExprKind::Phi(block_id, incoming), ty };
264            return Some(*table.entry(key).or_insert(result));
265        }
266        let kind = Self::expr_kind(kind, vn)?;
267        Some(*table.entry(ExprKey { kind, ty }).or_insert(result))
268    }
269
270    /// Normalizes a phi's incoming list for keying: per-predecessor classes,
271    /// sorted by predecessor with exact duplicates removed.
272    fn phi_key_incoming(
273        incoming: &[(BlockId, ValueId)],
274        vn: &[ClassId],
275    ) -> Option<Vec<(BlockId, ClassId)>> {
276        let mut entries: Vec<(BlockId, ClassId)> =
277            incoming.iter().map(|&(pred, value)| (pred, vn[value.index()])).collect();
278        entries.sort_by_key(|&(pred, class)| (pred.index(), class.index()));
279        entries.dedup();
280        // A predecessor listed with two distinct classes has no well-defined
281        // per-edge value; leave such phis unmerged.
282        if entries.windows(2).any(|pair| pair[0].0 == pair[1].0) {
283            return None;
284        }
285        Some(entries)
286    }
287
288    /// Builds the expression shape over operand classes for pure word ops.
289    /// Returns `None` for every other instruction.
290    fn expr_kind(kind: &InstKind, vn: &[ClassId]) -> Option<ExprKind> {
291        let class = |value: ValueId| vn[value.index()];
292        let sorted = |a: ValueId, b: ValueId| {
293            let (a, b) = (class(a), class(b));
294            if b.index() < a.index() { (b, a) } else { (a, b) }
295        };
296        Some(match *kind {
297            InstKind::Add(a, b) => {
298                let (a, b) = sorted(a, b);
299                ExprKind::Add(a, b)
300            }
301            InstKind::Mul(a, b) => {
302                let (a, b) = sorted(a, b);
303                ExprKind::Mul(a, b)
304            }
305            InstKind::And(a, b) => {
306                let (a, b) = sorted(a, b);
307                ExprKind::And(a, b)
308            }
309            InstKind::Or(a, b) => {
310                let (a, b) = sorted(a, b);
311                ExprKind::Or(a, b)
312            }
313            InstKind::Xor(a, b) => {
314                let (a, b) = sorted(a, b);
315                ExprKind::Xor(a, b)
316            }
317            InstKind::Eq(a, b) => {
318                let (a, b) = sorted(a, b);
319                ExprKind::Eq(a, b)
320            }
321            InstKind::AddMod(a, b, n) => {
322                let (a, b) = sorted(a, b);
323                ExprKind::AddMod(a, b, class(n))
324            }
325            InstKind::MulMod(a, b, n) => {
326                let (a, b) = sorted(a, b);
327                ExprKind::MulMod(a, b, class(n))
328            }
329            InstKind::Sub(a, b) => ExprKind::Sub(class(a), class(b)),
330            InstKind::Div(a, b) => ExprKind::Div(class(a), class(b)),
331            InstKind::SDiv(a, b) => ExprKind::SDiv(class(a), class(b)),
332            InstKind::Mod(a, b) => ExprKind::Mod(class(a), class(b)),
333            InstKind::SMod(a, b) => ExprKind::SMod(class(a), class(b)),
334            InstKind::Exp(a, b) => ExprKind::Exp(class(a), class(b)),
335            InstKind::Shl(a, b) => ExprKind::Shl(class(a), class(b)),
336            InstKind::Shr(a, b) => ExprKind::Shr(class(a), class(b)),
337            InstKind::Sar(a, b) => ExprKind::Sar(class(a), class(b)),
338            InstKind::Byte(a, b) => ExprKind::Byte(class(a), class(b)),
339            InstKind::SignExtend(a, b) => ExprKind::SignExtend(class(a), class(b)),
340            // Swapped comparisons - canonicalize `a > b` as `b < a` so they
341            // unify; the surviving instruction keeps its own opcode.
342            InstKind::Lt(a, b) => ExprKind::Lt(class(a), class(b)),
343            InstKind::Gt(a, b) => ExprKind::Lt(class(b), class(a)),
344            InstKind::SLt(a, b) => ExprKind::SLt(class(a), class(b)),
345            InstKind::SGt(a, b) => ExprKind::SLt(class(b), class(a)),
346            InstKind::IsZero(a) => ExprKind::IsZero(class(a)),
347            InstKind::Not(a) => ExprKind::Not(class(a)),
348            InstKind::Select(condition, then_value, else_value) => {
349                ExprKind::Select(class(condition), class(then_value), class(else_value))
350            }
351            InstKind::CalldataLoad(a) => ExprKind::CalldataLoad(class(a)),
352            InstKind::BlockHash(a) => ExprKind::BlockHash(class(a)),
353            InstKind::BlobHash(a) => ExprKind::BlobHash(class(a)),
354            // Immutable reads are constant once the runtime code is patched.
355            InstKind::LoadImmutable(offset) => ExprKind::LoadImmutable(offset),
356            // Everything else (memory, storage, environment reads, calls,
357            // gas/msize/returndatasize, keccak) never merges in this pass.
358            _ => return None,
359        })
360    }
361
362    // ----- replacement -----
363
364    /// Dominator-tree preorder walk with a scoped class-to-leader map.
365    fn replace_in_block(
366        &mut self,
367        func: &Function,
368        block_id: BlockId,
369        leaders: &mut FxHashMap<ClassId, ValueId>,
370        ctx: &mut ReplaceCtx<'_>,
371    ) {
372        for &inst_id in &func.blocks[block_id].instructions {
373            let Some(&result) = ctx.inst_results.get(&inst_id) else { continue };
374            let kind = &func.instructions[inst_id].kind;
375            if !matches!(kind, InstKind::Phi(_)) && Self::expr_kind(kind, ctx.vn).is_none() {
376                continue;
377            }
378            let class = ctx.vn[result.index()];
379            if let Some(&leader) = leaders.get(&class) {
380                if leader != result {
381                    ctx.replacements.insert(result, leader);
382                    ctx.dead.insert(inst_id);
383                    self.eliminated_count += 1;
384                }
385            } else {
386                leaders.insert(class, result);
387            }
388        }
389
390        for &child in ctx.cfg.dominators().children(block_id) {
391            let mut child_leaders = leaders.clone();
392            self.replace_in_block(func, child, &mut child_leaders, ctx);
393        }
394    }
395
396    // ----- CFG helpers -----
397
398    // ----- replacement application -----
399
400    fn apply_replacements_to_all_blocks(
401        func: &mut Function,
402        replacements: &FxHashMap<ValueId, ValueId>,
403    ) {
404        let block_ids: Vec<_> = func.blocks.indices().collect();
405        for block_id in block_ids {
406            Self::apply_replacements(func, block_id, replacements);
407        }
408    }
409
410    /// Applies value replacements to all instructions in a block.
411    fn apply_replacements(
412        func: &mut Function,
413        block_id: BlockId,
414        replacements: &FxHashMap<ValueId, ValueId>,
415    ) {
416        let inst_ids: Vec<InstId> = func.blocks[block_id].instructions.clone();
417        for inst_id in inst_ids {
418            let inst = &mut func.instructions[inst_id];
419            if mir_utils::replace_inst_uses_canonicalized(&mut inst.kind, replacements) != 0 {
420                if mir_utils::is_memory_inst(&inst.kind) {
421                    inst.metadata.set_memory_region(None);
422                }
423                if matches!(
424                    inst.kind,
425                    InstKind::SLoad(_)
426                        | InstKind::SStore(_, _)
427                        | InstKind::TLoad(_)
428                        | InstKind::TStore(_, _)
429                ) {
430                    inst.metadata.set_storage_alias(None);
431                }
432            }
433        }
434
435        if let Some(term) = &mut func.blocks[block_id].terminator {
436            mir_utils::replace_terminator_uses_canonicalized(term, replacements);
437        }
438    }
439}
solar_codegen/transform/gvn.rs

solar_codegen/transform/
gvn.rs
