oxilean_codegen/opt_gvn/
functions.rs

1//! Auto-generated module
2//!
3//! 🤖 Generated with [SplitRS](https://github.com/cool-japan/splitrs)
4
5use crate::lcnf::*;
6use std::collections::HashMap;
7
8use super::types::{
9    AlgebraicSimplifier, AnticipationSet, CCPState, CongruenceClosure, DomTree, ExprCanonicaliser,
10    FixpointGVN, GVNAnalysisCache, GVNConfig, GVNConstantFoldingHelper, GVNDepGraph,
11    GVNDominatorTree, GVNFact, GVNFunctionSummary, GVNLivenessInfo, GVNPass, GVNPassConfig,
12    GVNPassPhase, GVNPassRegistry, GVNPassStats, GVNPipeline, GVNPrePass, GVNReport, GVNStatistics,
13    GVNWorklist, HashConsingTable, InterproceduralGVN, LeaderFinder, LoadEliminatorGVN, NormArg,
14    NormExpr, PhiNode, PhiNodeSet, PhiOperand, PredicateGVN, RedundancyCollector,
15    ScopedValueContext, ValueTable,
16};
17
18/// A unique identifier for a value equivalence class.
19pub type ValueNumber = u32;
20pub(super) fn norm_expr_from_value_conservative(value: &LcnfLetValue) -> NormExpr {
21    match value {
22        LcnfLetValue::Lit(LcnfLit::Nat(n)) => NormExpr::Lit(*n),
23        LcnfLetValue::Lit(LcnfLit::Str(s)) => NormExpr::LitStr(s.clone()),
24        LcnfLetValue::Erased => NormExpr::Erased,
25        LcnfLetValue::FVar(v) => NormExpr::FVar(v.0 as ValueNumber),
26        _ => NormExpr::Unknown,
27    }
28}
29pub(super) fn gvn_norm_value(value: &LcnfLetValue, fact: &GVNFact) -> NormExpr {
30    match value {
31        LcnfLetValue::Lit(LcnfLit::Nat(n)) => NormExpr::Lit(*n),
32        LcnfLetValue::Lit(LcnfLit::Str(s)) => NormExpr::LitStr(s.clone()),
33        LcnfLetValue::Erased => NormExpr::Erased,
34        LcnfLetValue::FVar(v) => {
35            let vn = fact.get(v).unwrap_or(v.0 as ValueNumber + 1_000_000);
36            NormExpr::FVar(vn)
37        }
38        LcnfLetValue::Proj(name, idx, v) => {
39            let vn = fact.get(v).unwrap_or(v.0 as ValueNumber + 1_000_000);
40            NormExpr::Proj(name.clone(), *idx, vn)
41        }
42        _ => NormExpr::Unknown,
43    }
44}
45pub(super) fn var(n: u64) -> LcnfVarId {
46    LcnfVarId(n)
47}
48pub(super) fn lit_val(n: u64) -> LcnfLetValue {
49    LcnfLetValue::Lit(LcnfLit::Nat(n))
50}
51pub(super) fn fvar_val(n: u64) -> LcnfLetValue {
52    LcnfLetValue::FVar(LcnfVarId(n))
53}
54pub(super) fn arg_lit(n: u64) -> LcnfArg {
55    LcnfArg::Lit(LcnfLit::Nat(n))
56}
57pub(super) fn make_decl(name: &str, body: LcnfExpr) -> LcnfFunDecl {
58    LcnfFunDecl {
59        name: name.to_string(),
60        params: vec![],
61        ret_type: LcnfType::Nat,
62        original_name: None,
63        is_recursive: false,
64        is_lifted: false,
65        inline_cost: 0,
66        body,
67    }
68}
69#[cfg(test)]
70mod tests {
71    use super::*;
72    pub(super) fn let_expr(id: u64, val: LcnfLetValue, body: LcnfExpr) -> LcnfExpr {
73        LcnfExpr::Let {
74            id: var(id),
75            name: format!("x{}", var(id).0),
76            ty: LcnfType::Nat,
77            value: val,
78            body: Box::new(body),
79        }
80    }
81    #[test]
82    pub(super) fn test_gvn_default_config() {
83        let cfg = GVNConfig::default();
84        assert!(cfg.do_phi_translation);
85        assert_eq!(cfg.max_depth, 100);
86    }
87    #[test]
88    pub(super) fn test_value_table_empty() {
89        let t = ValueTable::new();
90        assert!(t.is_empty());
91        assert_eq!(t.len(), 0);
92    }
93    #[test]
94    pub(super) fn test_value_table_insert_lookup() {
95        let mut t = ValueTable::new();
96        let key = NormExpr::Lit(42);
97        let vn = t.insert(key.clone(), lit_val(42), var(1));
98        assert_eq!(t.lookup(&key), Some(vn));
99        assert_eq!(t.len(), 1);
100    }
101    #[test]
102    pub(super) fn test_value_table_canonical_var() {
103        let mut t = ValueTable::new();
104        let key = NormExpr::Lit(7);
105        let vn = t.insert(key, lit_val(7), var(5));
106        assert_eq!(t.canonical_var(vn), Some(var(5)));
107    }
108    #[test]
109    pub(super) fn test_gvn_fact_insert_get() {
110        let mut f = GVNFact::new();
111        f.insert(var(1), 42);
112        assert_eq!(f.get(&var(1)), Some(42));
113        assert_eq!(f.get(&var(99)), None);
114    }
115    #[test]
116    pub(super) fn test_hash_consing_intern() {
117        let mut hct = HashConsingTable::new();
118        let key = NormExpr::Lit(5);
119        hct.intern(key.clone(), lit_val(5));
120        assert_eq!(hct.len(), 1);
121        hct.intern(key, lit_val(5));
122        assert_eq!(hct.len(), 1);
123    }
124    #[test]
125    pub(super) fn test_congruence_closure_union_find() {
126        let mut cc = CongruenceClosure::new();
127        cc.union(1, 2);
128        assert!(cc.are_equal(1, 2));
129        assert!(!cc.are_equal(1, 3));
130    }
131    #[test]
132    pub(super) fn test_congruence_closure_transitivity() {
133        let mut cc = CongruenceClosure::new();
134        cc.union(1, 2);
135        cc.union(2, 3);
136        assert!(cc.are_equal(1, 3));
137    }
138    #[test]
139    pub(super) fn test_gvn_report_default() {
140        let r = GVNReport::default();
141        assert_eq!(r.expressions_numbered, 0);
142        assert_eq!(r.redundancies_eliminated, 0);
143    }
144    #[test]
145    pub(super) fn test_gvn_report_merge() {
146        let mut r1 = GVNReport {
147            expressions_numbered: 3,
148            redundancies_eliminated: 1,
149            phi_translations: 2,
150        };
151        let r2 = GVNReport {
152            expressions_numbered: 2,
153            redundancies_eliminated: 4,
154            phi_translations: 1,
155        };
156        r1.merge(&r2);
157        assert_eq!(r1.expressions_numbered, 5);
158        assert_eq!(r1.redundancies_eliminated, 5);
159        assert_eq!(r1.phi_translations, 3);
160    }
161    #[test]
162    pub(super) fn test_gvn_run_no_redundancy() {
163        let body = let_expr(
164            1,
165            lit_val(1),
166            let_expr(2, lit_val(2), LcnfExpr::Return(arg_lit(0))),
167        );
168        let mut decls = vec![make_decl("f", body)];
169        let mut pass = GVNPass::default();
170        pass.run(&mut decls);
171        assert_eq!(pass.report().redundancies_eliminated, 0);
172    }
173    #[test]
174    pub(super) fn test_gvn_run_redundant_literal() {
175        let body = let_expr(
176            1,
177            lit_val(42),
178            let_expr(2, lit_val(42), LcnfExpr::Return(arg_lit(0))),
179        );
180        let mut decls = vec![make_decl("f", body)];
181        let mut pass = GVNPass::default();
182        pass.run(&mut decls);
183        assert!(pass.report().redundancies_eliminated >= 1);
184    }
185    #[test]
186    pub(super) fn test_gvn_assigns_value_numbers() {
187        let body = let_expr(1, lit_val(10), LcnfExpr::Return(arg_lit(10)));
188        let mut decls = vec![make_decl("f", body)];
189        let mut pass = GVNPass::default();
190        pass.run(&mut decls);
191        assert!(pass.report().expressions_numbered >= 1);
192    }
193    #[test]
194    pub(super) fn test_gvn_copy_binding_rewritten() {
195        let mut decls = vec![make_decl(
196            "f",
197            let_expr(
198                10,
199                lit_val(7),
200                let_expr(
201                    11,
202                    lit_val(7),
203                    LcnfExpr::Return(LcnfArg::Var(LcnfVarId(11))),
204                ),
205            ),
206        )];
207        let mut pass = GVNPass::default();
208        pass.run(&mut decls);
209        if let LcnfExpr::Let { body, .. } = &decls[0].body {
210            if let LcnfExpr::Let { value, .. } = body.as_ref() {
211                assert!(matches!(value, LcnfLetValue::FVar(v) if * v == LcnfVarId(10)));
212            }
213        }
214    }
215    #[test]
216    pub(super) fn test_gvn_run_multiple_decls() {
217        let mut decls = vec![
218            make_decl("a", let_expr(1, lit_val(1), LcnfExpr::Return(arg_lit(0)))),
219            make_decl("b", let_expr(2, lit_val(2), LcnfExpr::Return(arg_lit(0)))),
220        ];
221        let mut pass = GVNPass::default();
222        pass.run(&mut decls);
223        assert!(pass.report().expressions_numbered >= 2);
224    }
225    #[test]
226    pub(super) fn test_gvn_depth_limit() {
227        let mut cfg = GVNConfig::default();
228        cfg.max_depth = 1;
229        let body = let_expr(
230            1,
231            lit_val(5),
232            let_expr(2, lit_val(5), LcnfExpr::Return(arg_lit(0))),
233        );
234        let mut decls = vec![make_decl("f", body)];
235        let mut pass = GVNPass::new(cfg);
236        pass.run(&mut decls);
237    }
238    #[test]
239    pub(super) fn test_norm_expr_equality() {
240        let a = NormExpr::Lit(42);
241        let b = NormExpr::Lit(42);
242        assert_eq!(a, b);
243        let c = NormExpr::Lit(43);
244        assert_ne!(a, c);
245    }
246    #[test]
247    pub(super) fn test_norm_arg_equality() {
248        assert_eq!(NormArg::LitNat(5), NormArg::LitNat(5));
249        assert_ne!(NormArg::LitNat(5), NormArg::LitNat(6));
250    }
251    #[test]
252    pub(super) fn test_dom_tree_build() {
253        let body = let_expr(1, lit_val(5), LcnfExpr::Return(arg_lit(0)));
254        let decl = make_decl("f", body);
255        let dt = DomTree::build_from_decl(&decl);
256        assert_eq!(dt.num_nodes(), 1);
257        assert!(dt.roots.contains(&var(1)));
258    }
259    #[test]
260    pub(super) fn test_dom_tree_dominates_self() {
261        let body = let_expr(1, lit_val(5), LcnfExpr::Return(arg_lit(0)));
262        let decl = make_decl("f", body);
263        let dt = DomTree::build_from_decl(&decl);
264        assert!(dt.dominates(var(1), var(1)));
265    }
266    #[test]
267    pub(super) fn test_dom_tree_nested() {
268        let body = let_expr(
269            1,
270            lit_val(1),
271            let_expr(2, lit_val(2), LcnfExpr::Return(arg_lit(0))),
272        );
273        let decl = make_decl("f", body);
274        let dt = DomTree::build_from_decl(&decl);
275        assert!(dt.dominates(var(1), var(2)));
276    }
277    #[test]
278    pub(super) fn test_anticipation_set_basic() {
279        let mut a = AnticipationSet::new();
280        a.add(NormExpr::Lit(5));
281        assert!(a.contains(&NormExpr::Lit(5)));
282        assert!(!a.contains(&NormExpr::Lit(6)));
283    }
284    #[test]
285    pub(super) fn test_anticipation_set_meet() {
286        let mut a = AnticipationSet::new();
287        a.add(NormExpr::Lit(1));
288        a.add(NormExpr::Lit(2));
289        let mut b = AnticipationSet::new();
290        b.add(NormExpr::Lit(2));
291        b.add(NormExpr::Lit(3));
292        let meet = a.meet(&b);
293        assert!(meet.contains(&NormExpr::Lit(2)));
294        assert!(!meet.contains(&NormExpr::Lit(1)));
295        assert!(!meet.contains(&NormExpr::Lit(3)));
296    }
297    #[test]
298    pub(super) fn test_gvn_pre_compute_anticipation() {
299        let body = let_expr(1, lit_val(7), LcnfExpr::Return(arg_lit(0)));
300        let decl = make_decl("f", body);
301        let mut pre = GVNPrePass::new();
302        pre.compute_anticipation(&decl);
303        assert!(pre.anticipation.contains_key(&var(1)));
304    }
305    #[test]
306    pub(super) fn test_phi_node_trivial() {
307        let phi = PhiNode::new(
308            var(1),
309            vec![
310                PhiOperand {
311                    branch_idx: 0,
312                    vn: 5,
313                },
314                PhiOperand {
315                    branch_idx: 1,
316                    vn: 5,
317                },
318            ],
319            42,
320        );
321        assert!(phi.is_trivial());
322        assert_eq!(phi.trivial_vn(), Some(5));
323    }
324    #[test]
325    pub(super) fn test_phi_node_non_trivial() {
326        let phi = PhiNode::new(
327            var(1),
328            vec![
329                PhiOperand {
330                    branch_idx: 0,
331                    vn: 3,
332                },
333                PhiOperand {
334                    branch_idx: 1,
335                    vn: 7,
336                },
337            ],
338            42,
339        );
340        assert!(!phi.is_trivial());
341        assert_eq!(phi.trivial_vn(), None);
342    }
343    #[test]
344    pub(super) fn test_phi_node_set_add_remove_trivial() {
345        let mut pns = PhiNodeSet::new(100);
346        pns.add_phi(
347            var(1),
348            vec![
349                PhiOperand {
350                    branch_idx: 0,
351                    vn: 5,
352                },
353                PhiOperand {
354                    branch_idx: 1,
355                    vn: 5,
356                },
357            ],
358        );
359        pns.add_phi(
360            var(2),
361            vec![
362                PhiOperand {
363                    branch_idx: 0,
364                    vn: 3,
365                },
366                PhiOperand {
367                    branch_idx: 1,
368                    vn: 7,
369                },
370            ],
371        );
372        assert_eq!(pns.num_phis(), 2);
373        let removed = pns.remove_trivial();
374        assert_eq!(removed, 1);
375        assert_eq!(pns.num_phis(), 1);
376    }
377    #[test]
378    pub(super) fn test_leader_finder_basic() {
379        let mut lf = LeaderFinder::new();
380        lf.record(42, var(1));
381        lf.record(42, var(2));
382        assert_eq!(lf.leader(42), Some(var(1)));
383        assert_eq!(lf.members(42).len(), 2);
384        assert_eq!(lf.num_redundancies(), 1);
385    }
386    #[test]
387    pub(super) fn test_load_eliminator_basic() {
388        let body = LcnfExpr::Let {
389            id: var(1),
390            name: "c".to_string(),
391            ty: LcnfType::Nat,
392            value: LcnfLetValue::Ctor("Pair".to_string(), 0, vec![arg_lit(10), arg_lit(20)]),
393            body: Box::new(LcnfExpr::Let {
394                id: var(2),
395                name: "p1".to_string(),
396                ty: LcnfType::Nat,
397                value: LcnfLetValue::Proj("Pair".to_string(), 0, var(1)),
398                body: Box::new(LcnfExpr::Let {
399                    id: var(3),
400                    name: "p2".to_string(),
401                    ty: LcnfType::Nat,
402                    value: LcnfLetValue::Proj("Pair".to_string(), 0, var(1)),
403                    body: Box::new(LcnfExpr::Return(LcnfArg::Var(var(3)))),
404                }),
405            }),
406        };
407        let mut decl = make_decl("f", body);
408        let mut le = LoadEliminatorGVN::new();
409        le.run(&mut decl);
410        assert_eq!(le.eliminated, 1);
411    }
412    #[test]
413    pub(super) fn test_algebraic_simplifier_default_rules() {
414        let s = AlgebraicSimplifier::new();
415        assert!(!s.rules.is_empty());
416    }
417    #[test]
418    pub(super) fn test_ccp_state_constant_folding() {
419        let body = LcnfExpr::Let {
420            id: var(1),
421            name: "x".to_string(),
422            ty: LcnfType::Nat,
423            value: LcnfLetValue::Lit(LcnfLit::Nat(0)),
424            body: Box::new(LcnfExpr::Case {
425                scrutinee: var(1),
426                scrutinee_ty: LcnfType::Nat,
427                alts: vec![LcnfAlt {
428                    ctor_name: "zero".to_string(),
429                    ctor_tag: 0,
430                    params: vec![],
431                    body: LcnfExpr::Return(arg_lit(42)),
432                }],
433                default: None,
434            }),
435        };
436        let mut decl = make_decl("f", body);
437        let mut ccp = CCPState::new();
438        ccp.run(&mut decl);
439        assert!(ccp.folded >= 1);
440    }
441    #[test]
442    pub(super) fn test_predicate_gvn_enter_exit_branch() {
443        let mut pgvn = PredicateGVN::new();
444        pgvn.enter_branch(var(1), 0);
445        assert!(pgvn.knows_eq_lit(var(1), &LcnfLit::Nat(0)));
446        pgvn.exit_branch();
447        assert!(!pgvn.knows_eq_lit(var(1), &LcnfLit::Nat(0)));
448    }
449    #[test]
450    pub(super) fn test_fixpoint_gvn_converges() {
451        let body = let_expr(
452            1,
453            lit_val(5),
454            let_expr(2, lit_val(5), LcnfExpr::Return(arg_lit(0))),
455        );
456        let mut decl = make_decl("f", body);
457        let mut fp = FixpointGVN::new(10);
458        fp.run(&mut decl);
459        assert!(fp.iterations <= 10);
460    }
461    #[test]
462    pub(super) fn test_gvn_statistics_total_redundancies() {
463        let mut stats = GVNStatistics::new();
464        stats.lit_redundancies = 3;
465        stats.proj_redundancies = 2;
466        assert_eq!(stats.total_redundancies(), 5);
467    }
468    #[test]
469    pub(super) fn test_scoped_value_context_push_pop() {
470        let mut ctx = ScopedValueContext::new();
471        ctx.bind(var(1), 100);
472        assert_eq!(ctx.lookup(&var(1)), Some(100));
473        ctx.push_scope();
474        ctx.bind(var(2), 200);
475        assert_eq!(ctx.lookup(&var(2)), Some(200));
476        ctx.pop_scope();
477        assert_eq!(ctx.lookup(&var(2)), None);
478        assert_eq!(ctx.lookup(&var(1)), Some(100));
479    }
480    #[test]
481    pub(super) fn test_scoped_value_context_depth() {
482        let mut ctx = ScopedValueContext::new();
483        assert_eq!(ctx.scope_depth(), 1);
484        ctx.push_scope();
485        assert_eq!(ctx.scope_depth(), 2);
486        ctx.pop_scope();
487        assert_eq!(ctx.scope_depth(), 1);
488    }
489    #[test]
490    pub(super) fn test_expr_canonicaliser_sorts_commutative() {
491        let mut ec = ExprCanonicaliser::new();
492        let expr = NormExpr::App(NormArg::Vn(0), vec![NormArg::Vn(5), NormArg::Vn(3)]);
493        let canon = ec.canonicalise(expr);
494        if let NormExpr::App(_, args) = &canon {
495            assert_eq!(args[0], NormArg::Vn(3));
496            assert_eq!(args[1], NormArg::Vn(5));
497        }
498        assert_eq!(ec.canonicalisations, 1);
499    }
500    #[test]
501    pub(super) fn test_gvn_function_summary_pure() {
502        let mut s = GVNFunctionSummary::new();
503        s.mark_pure();
504        assert!(s.is_pure_fn);
505    }
506    #[test]
507    pub(super) fn test_interprocedural_gvn_pure_query() {
508        let mut igvn = InterproceduralGVN::new();
509        let mut s = GVNFunctionSummary::new();
510        s.mark_pure();
511        igvn.add_summary("pure_fn".to_string(), s);
512        assert!(igvn.calls_are_equal("pure_fn"));
513        assert!(!igvn.calls_are_equal("impure"));
514    }
515    #[test]
516    pub(super) fn test_redundancy_collector_basic() {
517        let body = let_expr(
518            1,
519            lit_val(42),
520            let_expr(2, lit_val(42), LcnfExpr::Return(arg_lit(0))),
521        );
522        let decl = make_decl("f", body);
523        let mut rc = RedundancyCollector::new();
524        rc.collect(&decl);
525        assert!(rc.num_redundancies() >= 1);
526    }
527    #[test]
528    pub(super) fn test_gvn_pipeline_default() {
529        let body = let_expr(
530            1,
531            lit_val(7),
532            let_expr(2, lit_val(7), LcnfExpr::Return(arg_lit(0))),
533        );
534        let mut decls = vec![make_decl("f", body)];
535        let mut pipeline = GVNPipeline::new();
536        pipeline.run(&mut decls);
537        assert!(pipeline.stats.total_vns >= 1);
538    }
539    #[test]
540    pub(super) fn test_gvn_fact_meet() {
541        let mut f1 = GVNFact::new();
542        f1.insert(var(1), 10);
543        f1.insert(var(2), 20);
544        let mut f2 = GVNFact::new();
545        f2.insert(var(1), 10);
546        f2.insert(var(2), 99);
547        let meet = f1.meet(&f2);
548        assert_eq!(meet.get(&var(1)), Some(10));
549        assert_eq!(meet.get(&var(2)), None);
550    }
551    #[test]
552    pub(super) fn test_value_table_try_merge_compatible() {
553        let mut t1 = ValueTable::new();
554        let vn1 = t1.insert(NormExpr::Lit(1), lit_val(1), var(1));
555        let mut t2 = ValueTable::new();
556        t2.insert(NormExpr::Lit(2), lit_val(2), var(2));
557        let ok = t1.try_merge(&t2);
558        assert!(ok);
559        let _ = vn1;
560    }
561    #[test]
562    pub(super) fn test_gvn_pipeline_with_load_elim() {
563        let body = LcnfExpr::Let {
564            id: var(1),
565            name: "c".to_string(),
566            ty: LcnfType::Nat,
567            value: LcnfLetValue::Ctor("Pair".to_string(), 0, vec![arg_lit(5)]),
568            body: Box::new(LcnfExpr::Let {
569                id: var(2),
570                name: "p".to_string(),
571                ty: LcnfType::Nat,
572                value: LcnfLetValue::Proj("Pair".to_string(), 0, var(1)),
573                body: Box::new(LcnfExpr::Let {
574                    id: var(3),
575                    name: "p2".to_string(),
576                    ty: LcnfType::Nat,
577                    value: LcnfLetValue::Proj("Pair".to_string(), 0, var(1)),
578                    body: Box::new(LcnfExpr::Return(LcnfArg::Var(var(3)))),
579                }),
580            }),
581        };
582        let mut decls = vec![make_decl("f", body)];
583        let mut pipeline = GVNPipeline {
584            do_load_elim: true,
585            do_base_gvn: false,
586            ..GVNPipeline::default()
587        };
588        pipeline.run(&mut decls);
589        assert!(pipeline.stats.proj_redundancies >= 1);
590    }
591    #[test]
592    pub(super) fn test_congruence_closure_idempotent_union() {
593        let mut cc = CongruenceClosure::new();
594        cc.union(1, 1);
595        assert!(cc.are_equal(1, 1));
596    }
597    #[test]
598    pub(super) fn test_fixpoint_gvn_max_iter_respected() {
599        let body = LcnfExpr::Return(arg_lit(0));
600        let mut decl = make_decl("f", body);
601        let mut fp = FixpointGVN::new(3);
602        fp.run(&mut decl);
603        assert!(fp.iterations <= 3);
604    }
605    #[test]
606    pub(super) fn test_norm_expr_proj_hash() {
607        use std::collections::HashSet;
608        let mut s: HashSet<NormExpr> = HashSet::new();
609        s.insert(NormExpr::Proj("Foo".to_string(), 0, 5));
610        s.insert(NormExpr::Proj("Foo".to_string(), 0, 5));
611        assert_eq!(s.len(), 1);
612        s.insert(NormExpr::Proj("Foo".to_string(), 1, 5));
613        assert_eq!(s.len(), 2);
614    }
615}
616#[cfg(test)]
617mod GVN_infra_tests {
618    use super::*;
619    #[test]
620    pub(super) fn test_pass_config() {
621        let config = GVNPassConfig::new("test_pass", GVNPassPhase::Transformation);
622        assert!(config.enabled);
623        assert!(config.phase.is_modifying());
624        assert_eq!(config.phase.name(), "transformation");
625    }
626    #[test]
627    pub(super) fn test_pass_stats() {
628        let mut stats = GVNPassStats::new();
629        stats.record_run(10, 100, 3);
630        stats.record_run(20, 200, 5);
631        assert_eq!(stats.total_runs, 2);
632        assert!((stats.average_changes_per_run() - 15.0).abs() < 0.01);
633        assert!((stats.success_rate() - 1.0).abs() < 0.01);
634        let s = stats.format_summary();
635        assert!(s.contains("Runs: 2/2"));
636    }
637    #[test]
638    pub(super) fn test_pass_registry() {
639        let mut reg = GVNPassRegistry::new();
640        reg.register(GVNPassConfig::new("pass_a", GVNPassPhase::Analysis));
641        reg.register(GVNPassConfig::new("pass_b", GVNPassPhase::Transformation).disabled());
642        assert_eq!(reg.total_passes(), 2);
643        assert_eq!(reg.enabled_count(), 1);
644        reg.update_stats("pass_a", 5, 50, 2);
645        let stats = reg.get_stats("pass_a").expect("stats should exist");
646        assert_eq!(stats.total_changes, 5);
647    }
648    #[test]
649    pub(super) fn test_analysis_cache() {
650        let mut cache = GVNAnalysisCache::new(10);
651        cache.insert("key1".to_string(), vec![1, 2, 3]);
652        assert!(cache.get("key1").is_some());
653        assert!(cache.get("key2").is_none());
654        assert!((cache.hit_rate() - 0.5).abs() < 0.01);
655        cache.invalidate("key1");
656        assert!(!cache.entries["key1"].valid);
657        assert_eq!(cache.size(), 1);
658    }
659    #[test]
660    pub(super) fn test_worklist() {
661        let mut wl = GVNWorklist::new();
662        assert!(wl.push(1));
663        assert!(wl.push(2));
664        assert!(!wl.push(1));
665        assert_eq!(wl.len(), 2);
666        assert_eq!(wl.pop(), Some(1));
667        assert!(!wl.contains(1));
668        assert!(wl.contains(2));
669    }
670    #[test]
671    pub(super) fn test_dominator_tree() {
672        let mut dt = GVNDominatorTree::new(5);
673        dt.set_idom(1, 0);
674        dt.set_idom(2, 0);
675        dt.set_idom(3, 1);
676        assert!(dt.dominates(0, 3));
677        assert!(dt.dominates(1, 3));
678        assert!(!dt.dominates(2, 3));
679        assert!(dt.dominates(3, 3));
680    }
681    #[test]
682    pub(super) fn test_liveness() {
683        let mut liveness = GVNLivenessInfo::new(3);
684        liveness.add_def(0, 1);
685        liveness.add_use(1, 1);
686        assert!(liveness.defs[0].contains(&1));
687        assert!(liveness.uses[1].contains(&1));
688    }
689    #[test]
690    pub(super) fn test_constant_folding() {
691        assert_eq!(GVNConstantFoldingHelper::fold_add_i64(3, 4), Some(7));
692        assert_eq!(GVNConstantFoldingHelper::fold_div_i64(10, 0), None);
693        assert_eq!(GVNConstantFoldingHelper::fold_div_i64(10, 2), Some(5));
694        assert_eq!(
695            GVNConstantFoldingHelper::fold_bitand_i64(0b1100, 0b1010),
696            0b1000
697        );
698        assert_eq!(GVNConstantFoldingHelper::fold_bitnot_i64(0), -1);
699    }
700    #[test]
701    pub(super) fn test_dep_graph() {
702        let mut g = GVNDepGraph::new();
703        g.add_dep(1, 2);
704        g.add_dep(2, 3);
705        g.add_dep(1, 3);
706        assert_eq!(g.dependencies_of(2), vec![1]);
707        let topo = g.topological_sort();
708        assert_eq!(topo.len(), 3);
709        assert!(!g.has_cycle());
710        let pos: std::collections::HashMap<u32, usize> =
711            topo.iter().enumerate().map(|(i, &n)| (n, i)).collect();
712        assert!(pos[&1] < pos[&2]);
713        assert!(pos[&1] < pos[&3]);
714        assert!(pos[&2] < pos[&3]);
715    }
716}
oxilean_codegen/opt_gvn/functions.rs

oxilean_codegen/opt_gvn/
functions.rs
