oxilean_codegen/opt_cse/
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    AvailableSet, CSEAnalysisCache, CSEConstantFoldingHelper, CSEDepGraph, CSEDominatorTree,
10    CSEExtCache, CSEExtConstFolder, CSEExtDepGraph, CSEExtDomTree, CSEExtLiveness,
11    CSEExtPassConfig, CSEExtPassPhase, CSEExtPassRegistry, CSEExtPassStats, CSEExtWorklist,
12    CSELivenessInfo, CSEPass, CSEPassConfig, CSEPassPhase, CSEPassRegistry, CSEPassStats,
13    CSEWorklist, CSEX2Cache, CSEX2ConstFolder, CSEX2DepGraph, CSEX2DomTree, CSEX2Liveness,
14    CSEX2PassConfig, CSEX2PassPhase, CSEX2PassRegistry, CSEX2PassStats, CSEX2Worklist, CseConfig,
15    CseReport, DominatorTree, ExprKey, GvnTable,
16};
17
18/// Normalize a let-bound value into an `ExprKey`, or `None` if the value
19/// is not a candidate for CSE (e.g. impure, reset, reuse).
20pub fn let_value_to_key(value: &LcnfLetValue, pure_fns: &[String]) -> Option<ExprKey> {
21    match value {
22        LcnfLetValue::Lit(l) => Some(ExprKey::Lit(l.clone())),
23        LcnfLetValue::FVar(v) => Some(ExprKey::Var(*v)),
24        LcnfLetValue::Proj(name, idx, var) => Some(ExprKey::Proj(name.clone(), *idx, *var)),
25        LcnfLetValue::Ctor(name, tag, args) => {
26            Some(ExprKey::Ctor(name.clone(), *tag, args.clone()))
27        }
28        LcnfLetValue::App(func, args) => {
29            let is_pure = match func {
30                LcnfArg::Var(_) => false,
31                LcnfArg::Lit(_) => false,
32                LcnfArg::Erased => false,
33                LcnfArg::Type(_) => false,
34            };
35            let is_named_pure = pure_fns
36                .iter()
37                .any(|name| matches!(func, LcnfArg::Lit(LcnfLit::Str(s)) if s == name));
38            if is_pure || is_named_pure {
39                Some(ExprKey::App(func.clone(), args.clone()))
40            } else {
41                None
42            }
43        }
44        LcnfLetValue::Erased => None,
45        LcnfLetValue::Reset(_) => None,
46        LcnfLetValue::Reuse(_, _, _, _) => None,
47    }
48}
49/// Run CSE on a vector of function declarations with default configuration.
50pub fn optimize_cse(decls: &mut [LcnfFunDecl]) {
51    CSEPass::default().run(decls);
52}
53#[cfg(test)]
54mod tests {
55    use super::*;
56    pub(super) fn make_var(id: u64) -> LcnfVarId {
57        LcnfVarId(id)
58    }
59    pub(super) fn make_lit_nat(n: u64) -> LcnfLetValue {
60        LcnfLetValue::Lit(LcnfLit::Nat(n))
61    }
62    pub(super) fn make_fvar(id: u64) -> LcnfLetValue {
63        LcnfLetValue::FVar(make_var(id))
64    }
65    pub(super) fn make_proj(field: &str, idx: u32, var: u64) -> LcnfLetValue {
66        LcnfLetValue::Proj(field.to_string(), idx, make_var(var))
67    }
68    pub(super) fn make_ctor(name: &str, tag: u32, args: Vec<LcnfArg>) -> LcnfLetValue {
69        LcnfLetValue::Ctor(name.to_string(), tag, args)
70    }
71    pub(super) fn ret(v: u64) -> LcnfExpr {
72        LcnfExpr::Return(LcnfArg::Var(make_var(v)))
73    }
74    pub(super) fn let_binding(id: u64, value: LcnfLetValue, body: LcnfExpr) -> LcnfExpr {
75        LcnfExpr::Let {
76            id: make_var(id),
77            name: format!("x{}", id),
78            ty: LcnfType::Nat,
79            value,
80            body: Box::new(body),
81        }
82    }
83    #[test]
84    pub(super) fn test_key_lit() {
85        let v = make_lit_nat(42);
86        let key = let_value_to_key(&v, &[]);
87        assert_eq!(key, Some(ExprKey::Lit(LcnfLit::Nat(42))));
88    }
89    #[test]
90    pub(super) fn test_key_fvar() {
91        let v = make_fvar(7);
92        let key = let_value_to_key(&v, &[]);
93        assert_eq!(key, Some(ExprKey::Var(make_var(7))));
94    }
95    #[test]
96    pub(super) fn test_key_proj() {
97        let v = make_proj("foo", 1, 3);
98        let key = let_value_to_key(&v, &[]);
99        assert_eq!(key, Some(ExprKey::Proj("foo".into(), 1, make_var(3))));
100    }
101    #[test]
102    pub(super) fn test_key_ctor() {
103        let v = make_ctor("Pair", 0, vec![LcnfArg::Var(make_var(1))]);
104        let key = let_value_to_key(&v, &[]);
105        assert_eq!(
106            key,
107            Some(ExprKey::Ctor(
108                "Pair".into(),
109                0,
110                vec![LcnfArg::Var(make_var(1))]
111            ))
112        );
113    }
114    #[test]
115    pub(super) fn test_key_reset_is_none() {
116        let v = LcnfLetValue::Reset(make_var(5));
117        assert_eq!(let_value_to_key(&v, &[]), None);
118    }
119    #[test]
120    pub(super) fn test_key_erased_is_none() {
121        let v = LcnfLetValue::Erased;
122        assert_eq!(let_value_to_key(&v, &[]), None);
123    }
124    #[test]
125    pub(super) fn test_avail_insert_and_find() {
126        let mut avail = AvailableSet::new();
127        let key = ExprKey::Lit(LcnfLit::Nat(1));
128        avail.insert(key.clone(), make_var(10), "x10".into(), 0);
129        assert_eq!(avail.find(&key), Some(make_var(10)));
130    }
131    #[test]
132    pub(super) fn test_avail_miss() {
133        let avail = AvailableSet::new();
134        let key = ExprKey::Lit(LcnfLit::Nat(99));
135        assert_eq!(avail.find(&key), None);
136    }
137    #[test]
138    pub(super) fn test_avail_kill_above_depth() {
139        let mut avail = AvailableSet::new();
140        let k0 = ExprKey::Lit(LcnfLit::Nat(0));
141        let k1 = ExprKey::Lit(LcnfLit::Nat(1));
142        avail.insert(k0.clone(), make_var(1), "a".into(), 0);
143        avail.insert(k1.clone(), make_var(2), "b".into(), 3);
144        avail.kill_above_depth(2);
145        assert_eq!(avail.find(&k0), Some(make_var(1)));
146        assert_eq!(avail.find(&k1), None);
147    }
148    #[test]
149    pub(super) fn test_avail_len() {
150        let mut avail = AvailableSet::new();
151        assert_eq!(avail.len(), 0);
152        avail.insert(ExprKey::Lit(LcnfLit::Nat(1)), make_var(1), "a".into(), 0);
153        assert_eq!(avail.len(), 1);
154    }
155    #[test]
156    pub(super) fn test_gvn_insert_and_lookup() {
157        let mut gvn = GvnTable::new();
158        let key = ExprKey::Lit(LcnfLit::Nat(7));
159        let rep = gvn.insert(key.clone(), make_var(42));
160        assert_eq!(rep, make_var(42));
161        assert_eq!(gvn.lookup(&key), Some(make_var(42)));
162    }
163    #[test]
164    pub(super) fn test_gvn_duplicate_keeps_first() {
165        let mut gvn = GvnTable::new();
166        let key = ExprKey::Lit(LcnfLit::Nat(7));
167        gvn.insert(key.clone(), make_var(1));
168        let rep2 = gvn.insert(key.clone(), make_var(2));
169        assert_eq!(rep2, make_var(1));
170    }
171    #[test]
172    pub(super) fn test_dominator_tree() {
173        let mut dom = DominatorTree::new();
174        dom.insert(make_var(1), 0);
175        dom.insert(make_var(2), 2);
176        assert!(dom.dominates(make_var(1), make_var(2)));
177        assert!(!dom.dominates(make_var(2), make_var(1)));
178    }
179    #[test]
180    pub(super) fn test_local_cse_eliminates_duplicate_lit() {
181        let expr = let_binding(
182            1,
183            make_lit_nat(42),
184            let_binding(2, make_lit_nat(42), ret(2)),
185        );
186        let mut pass = CSEPass::default();
187        let result = pass.local_cse(&expr);
188        if let LcnfExpr::Let { body, .. } = &result {
189            if let LcnfExpr::Let { value, .. } = body.as_ref() {
190                assert_eq!(*value, LcnfLetValue::FVar(make_var(1)));
191            } else {
192                panic!("expected inner Let");
193            }
194        } else {
195            panic!("expected outer Let");
196        }
197        assert_eq!(pass.report().expressions_eliminated, 1);
198    }
199    #[test]
200    pub(super) fn test_local_cse_no_false_positive_different_lit() {
201        let expr = let_binding(1, make_lit_nat(1), let_binding(2, make_lit_nat(2), ret(2)));
202        let mut pass = CSEPass::default();
203        let result = pass.local_cse(&expr);
204        if let LcnfExpr::Let { body, .. } = &result {
205            if let LcnfExpr::Let { value, .. } = body.as_ref() {
206                assert_eq!(*value, make_lit_nat(2));
207            } else {
208                panic!("expected inner Let");
209            }
210        }
211        assert_eq!(pass.report().expressions_eliminated, 0);
212    }
213    #[test]
214    pub(super) fn test_local_cse_duplicate_proj() {
215        let proj = make_proj("record", 0, 5);
216        let expr = let_binding(10, proj.clone(), let_binding(11, proj.clone(), ret(11)));
217        let mut pass = CSEPass::default();
218        let result = pass.local_cse(&expr);
219        if let LcnfExpr::Let { body, .. } = &result {
220            if let LcnfExpr::Let { value, .. } = body.as_ref() {
221                assert_eq!(*value, LcnfLetValue::FVar(make_var(10)));
222            } else {
223                panic!("expected inner Let");
224            }
225        }
226        assert_eq!(pass.report().expressions_eliminated, 1);
227    }
228    #[test]
229    pub(super) fn test_local_cse_duplicate_ctor() {
230        let ctor = make_ctor("Some", 1, vec![LcnfArg::Var(make_var(3))]);
231        let expr = let_binding(20, ctor.clone(), let_binding(21, ctor.clone(), ret(21)));
232        let mut pass = CSEPass::default();
233        pass.local_cse(&expr);
234        assert_eq!(pass.report().expressions_eliminated, 1);
235    }
236    #[test]
237    pub(super) fn test_cse_return_unchanged() {
238        let expr = LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(0)));
239        let mut pass = CSEPass::default();
240        let result = pass.local_cse(&expr);
241        assert_eq!(result, expr);
242    }
243    #[test]
244    pub(super) fn test_cse_unreachable_unchanged() {
245        let expr = LcnfExpr::Unreachable;
246        let mut pass = CSEPass::default();
247        let result = pass.local_cse(&expr);
248        assert_eq!(result, expr);
249    }
250    #[test]
251    pub(super) fn test_cse_report_display() {
252        let r = CseReport {
253            expressions_found: 5,
254            expressions_eliminated: 3,
255            lets_hoisted: 1,
256        };
257        let s = format!("{}", r);
258        assert!(s.contains("found=5"));
259        assert!(s.contains("eliminated=3"));
260    }
261    #[test]
262    pub(super) fn test_cse_config_display() {
263        let c = CseConfig::default();
264        let s = format!("{}", c);
265        assert!(s.contains("max_expr_size=20"));
266    }
267    #[test]
268    pub(super) fn test_global_cse_run() {
269        let mut decls: Vec<LcnfFunDecl> = vec![];
270        CSEPass::default().run(&mut decls);
271    }
272    #[test]
273    pub(super) fn test_cse_triple_dup() {
274        let expr = let_binding(
275            1,
276            make_lit_nat(7),
277            let_binding(2, make_lit_nat(7), let_binding(3, make_lit_nat(7), ret(3))),
278        );
279        let mut pass = CSEPass::default();
280        pass.local_cse(&expr);
281        assert_eq!(pass.report().expressions_eliminated, 2);
282    }
283    #[test]
284    pub(super) fn test_cse_case_branches_independent() {
285        let inner_lit = make_lit_nat(99);
286        let alt_body = let_binding(
287            10,
288            inner_lit.clone(),
289            let_binding(11, inner_lit.clone(), ret(11)),
290        );
291        let case_expr = LcnfExpr::Case {
292            scrutinee: make_var(0),
293            scrutinee_ty: LcnfType::Nat,
294            alts: vec![LcnfAlt {
295                ctor_name: "Zero".into(),
296                ctor_tag: 0,
297                params: vec![],
298                body: alt_body,
299            }],
300            default: None,
301        };
302        let mut pass = CSEPass::default();
303        pass.local_cse(&case_expr);
304        assert_eq!(pass.report().expressions_eliminated, 1);
305    }
306    #[test]
307    pub(super) fn test_find_available() {
308        let pass = CSEPass::default();
309        let mut avail = AvailableSet::new();
310        let proj = make_proj("hd", 0, 1);
311        let key = let_value_to_key(&proj, &[]).expect("key key extraction should succeed");
312        avail.insert(key, make_var(5), "hd".into(), 0);
313        let result = pass.find_available(&avail, &proj);
314        assert_eq!(result, Some(make_var(5)));
315    }
316    #[test]
317    pub(super) fn test_hash_expr_is_commutative() {
318        let pass = CSEPass::default();
319        let va = LcnfArg::Lit(LcnfLit::Nat(1));
320        let vb = LcnfArg::Lit(LcnfLit::Nat(2));
321        let v1 = LcnfLetValue::App(
322            LcnfArg::Lit(LcnfLit::Str("add".into())),
323            vec![va.clone(), vb.clone()],
324        );
325        let v2 = LcnfLetValue::App(
326            LcnfArg::Lit(LcnfLit::Str("add".into())),
327            vec![vb.clone(), va.clone()],
328        );
329        let k1 = pass.hash_expr(&v1);
330        let k2 = pass.hash_expr(&v2);
331        assert_eq!(k1, k2);
332    }
333    #[test]
334    pub(super) fn test_optimize_cse_convenience() {
335        let mut decls: Vec<LcnfFunDecl> = vec![];
336        optimize_cse(&mut decls);
337    }
338}
339#[cfg(test)]
340mod CSE_infra_tests {
341    use super::*;
342    #[test]
343    pub(super) fn test_pass_config() {
344        let config = CSEPassConfig::new("test_pass", CSEPassPhase::Transformation);
345        assert!(config.enabled);
346        assert!(config.phase.is_modifying());
347        assert_eq!(config.phase.name(), "transformation");
348    }
349    #[test]
350    pub(super) fn test_pass_stats() {
351        let mut stats = CSEPassStats::new();
352        stats.record_run(10, 100, 3);
353        stats.record_run(20, 200, 5);
354        assert_eq!(stats.total_runs, 2);
355        assert!((stats.average_changes_per_run() - 15.0).abs() < 0.01);
356        assert!((stats.success_rate() - 1.0).abs() < 0.01);
357        let s = stats.format_summary();
358        assert!(s.contains("Runs: 2/2"));
359    }
360    #[test]
361    pub(super) fn test_pass_registry() {
362        let mut reg = CSEPassRegistry::new();
363        reg.register(CSEPassConfig::new("pass_a", CSEPassPhase::Analysis));
364        reg.register(CSEPassConfig::new("pass_b", CSEPassPhase::Transformation).disabled());
365        assert_eq!(reg.total_passes(), 2);
366        assert_eq!(reg.enabled_count(), 1);
367        reg.update_stats("pass_a", 5, 50, 2);
368        let stats = reg.get_stats("pass_a").expect("stats should exist");
369        assert_eq!(stats.total_changes, 5);
370    }
371    #[test]
372    pub(super) fn test_analysis_cache() {
373        let mut cache = CSEAnalysisCache::new(10);
374        cache.insert("key1".to_string(), vec![1, 2, 3]);
375        assert!(cache.get("key1").is_some());
376        assert!(cache.get("key2").is_none());
377        assert!((cache.hit_rate() - 0.5).abs() < 0.01);
378        cache.invalidate("key1");
379        assert!(!cache.entries["key1"].valid);
380        assert_eq!(cache.size(), 1);
381    }
382    #[test]
383    pub(super) fn test_worklist() {
384        let mut wl = CSEWorklist::new();
385        assert!(wl.push(1));
386        assert!(wl.push(2));
387        assert!(!wl.push(1));
388        assert_eq!(wl.len(), 2);
389        assert_eq!(wl.pop(), Some(1));
390        assert!(!wl.contains(1));
391        assert!(wl.contains(2));
392    }
393    #[test]
394    pub(super) fn test_dominator_tree() {
395        let mut dt = CSEDominatorTree::new(5);
396        dt.set_idom(1, 0);
397        dt.set_idom(2, 0);
398        dt.set_idom(3, 1);
399        assert!(dt.dominates(0, 3));
400        assert!(dt.dominates(1, 3));
401        assert!(!dt.dominates(2, 3));
402        assert!(dt.dominates(3, 3));
403    }
404    #[test]
405    pub(super) fn test_liveness() {
406        let mut liveness = CSELivenessInfo::new(3);
407        liveness.add_def(0, 1);
408        liveness.add_use(1, 1);
409        assert!(liveness.defs[0].contains(&1));
410        assert!(liveness.uses[1].contains(&1));
411    }
412    #[test]
413    pub(super) fn test_constant_folding() {
414        assert_eq!(CSEConstantFoldingHelper::fold_add_i64(3, 4), Some(7));
415        assert_eq!(CSEConstantFoldingHelper::fold_div_i64(10, 0), None);
416        assert_eq!(CSEConstantFoldingHelper::fold_div_i64(10, 2), Some(5));
417        assert_eq!(
418            CSEConstantFoldingHelper::fold_bitand_i64(0b1100, 0b1010),
419            0b1000
420        );
421        assert_eq!(CSEConstantFoldingHelper::fold_bitnot_i64(0), -1);
422    }
423    #[test]
424    pub(super) fn test_dep_graph() {
425        let mut g = CSEDepGraph::new();
426        g.add_dep(1, 2);
427        g.add_dep(2, 3);
428        g.add_dep(1, 3);
429        assert_eq!(g.dependencies_of(2), vec![1]);
430        let topo = g.topological_sort();
431        assert_eq!(topo.len(), 3);
432        assert!(!g.has_cycle());
433        let pos: std::collections::HashMap<u32, usize> =
434            topo.iter().enumerate().map(|(i, &n)| (n, i)).collect();
435        assert!(pos[&1] < pos[&2]);
436        assert!(pos[&1] < pos[&3]);
437        assert!(pos[&2] < pos[&3]);
438    }
439}
440#[cfg(test)]
441mod cseext_pass_tests {
442    use super::*;
443    #[test]
444    pub(super) fn test_cseext_phase_order() {
445        assert_eq!(CSEExtPassPhase::Early.order(), 0);
446        assert_eq!(CSEExtPassPhase::Middle.order(), 1);
447        assert_eq!(CSEExtPassPhase::Late.order(), 2);
448        assert_eq!(CSEExtPassPhase::Finalize.order(), 3);
449        assert!(CSEExtPassPhase::Early.is_early());
450        assert!(!CSEExtPassPhase::Early.is_late());
451    }
452    #[test]
453    pub(super) fn test_cseext_config_builder() {
454        let c = CSEExtPassConfig::new("p")
455            .with_phase(CSEExtPassPhase::Late)
456            .with_max_iter(50)
457            .with_debug(1);
458        assert_eq!(c.name, "p");
459        assert_eq!(c.max_iterations, 50);
460        assert!(c.is_debug_enabled());
461        assert!(c.enabled);
462        let c2 = c.disabled();
463        assert!(!c2.enabled);
464    }
465    #[test]
466    pub(super) fn test_cseext_stats() {
467        let mut s = CSEExtPassStats::new();
468        s.visit();
469        s.visit();
470        s.modify();
471        s.iterate();
472        assert_eq!(s.nodes_visited, 2);
473        assert_eq!(s.nodes_modified, 1);
474        assert!(s.changed);
475        assert_eq!(s.iterations, 1);
476        let e = s.efficiency();
477        assert!((e - 0.5).abs() < 1e-9);
478    }
479    #[test]
480    pub(super) fn test_cseext_registry() {
481        let mut r = CSEExtPassRegistry::new();
482        r.register(CSEExtPassConfig::new("a").with_phase(CSEExtPassPhase::Early));
483        r.register(CSEExtPassConfig::new("b").disabled());
484        assert_eq!(r.len(), 2);
485        assert_eq!(r.enabled_passes().len(), 1);
486        assert_eq!(r.passes_in_phase(&CSEExtPassPhase::Early).len(), 1);
487    }
488    #[test]
489    pub(super) fn test_cseext_cache() {
490        let mut c = CSEExtCache::new(4);
491        assert!(c.get(99).is_none());
492        c.put(99, vec![1, 2, 3]);
493        let v = c.get(99).expect("v should be present in map");
494        assert_eq!(v, &[1u8, 2, 3]);
495        assert!(c.hit_rate() > 0.0);
496        assert_eq!(c.live_count(), 1);
497    }
498    #[test]
499    pub(super) fn test_cseext_worklist() {
500        let mut w = CSEExtWorklist::new(10);
501        w.push(5);
502        w.push(3);
503        w.push(5);
504        assert_eq!(w.len(), 2);
505        assert!(w.contains(5));
506        let first = w.pop().expect("first should be available to pop");
507        assert!(!w.contains(first));
508    }
509    #[test]
510    pub(super) fn test_cseext_dom_tree() {
511        let mut dt = CSEExtDomTree::new(5);
512        dt.set_idom(1, 0);
513        dt.set_idom(2, 0);
514        dt.set_idom(3, 1);
515        dt.set_idom(4, 1);
516        assert!(dt.dominates(0, 3));
517        assert!(dt.dominates(1, 4));
518        assert!(!dt.dominates(2, 3));
519        assert_eq!(dt.depth_of(3), 2);
520    }
521    #[test]
522    pub(super) fn test_cseext_liveness() {
523        let mut lv = CSEExtLiveness::new(3);
524        lv.add_def(0, 1);
525        lv.add_use(1, 1);
526        assert!(lv.var_is_def_in_block(0, 1));
527        assert!(lv.var_is_used_in_block(1, 1));
528        assert!(!lv.var_is_def_in_block(1, 1));
529    }
530    #[test]
531    pub(super) fn test_cseext_const_folder() {
532        let mut cf = CSEExtConstFolder::new();
533        assert_eq!(cf.add_i64(3, 4), Some(7));
534        assert_eq!(cf.div_i64(10, 0), None);
535        assert_eq!(cf.mul_i64(6, 7), Some(42));
536        assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
537        assert_eq!(cf.fold_count(), 3);
538        assert_eq!(cf.failure_count(), 1);
539    }
540    #[test]
541    pub(super) fn test_cseext_dep_graph() {
542        let mut g = CSEExtDepGraph::new(4);
543        g.add_edge(0, 1);
544        g.add_edge(1, 2);
545        g.add_edge(2, 3);
546        assert!(!g.has_cycle());
547        assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
548        assert_eq!(g.reachable(0).len(), 4);
549        let sccs = g.scc();
550        assert_eq!(sccs.len(), 4);
551    }
552}
553#[cfg(test)]
554mod csex2_pass_tests {
555    use super::*;
556    #[test]
557    pub(super) fn test_csex2_phase_order() {
558        assert_eq!(CSEX2PassPhase::Early.order(), 0);
559        assert_eq!(CSEX2PassPhase::Middle.order(), 1);
560        assert_eq!(CSEX2PassPhase::Late.order(), 2);
561        assert_eq!(CSEX2PassPhase::Finalize.order(), 3);
562        assert!(CSEX2PassPhase::Early.is_early());
563        assert!(!CSEX2PassPhase::Early.is_late());
564    }
565    #[test]
566    pub(super) fn test_csex2_config_builder() {
567        let c = CSEX2PassConfig::new("p")
568            .with_phase(CSEX2PassPhase::Late)
569            .with_max_iter(50)
570            .with_debug(1);
571        assert_eq!(c.name, "p");
572        assert_eq!(c.max_iterations, 50);
573        assert!(c.is_debug_enabled());
574        assert!(c.enabled);
575        let c2 = c.disabled();
576        assert!(!c2.enabled);
577    }
578    #[test]
579    pub(super) fn test_csex2_stats() {
580        let mut s = CSEX2PassStats::new();
581        s.visit();
582        s.visit();
583        s.modify();
584        s.iterate();
585        assert_eq!(s.nodes_visited, 2);
586        assert_eq!(s.nodes_modified, 1);
587        assert!(s.changed);
588        assert_eq!(s.iterations, 1);
589        let e = s.efficiency();
590        assert!((e - 0.5).abs() < 1e-9);
591    }
592    #[test]
593    pub(super) fn test_csex2_registry() {
594        let mut r = CSEX2PassRegistry::new();
595        r.register(CSEX2PassConfig::new("a").with_phase(CSEX2PassPhase::Early));
596        r.register(CSEX2PassConfig::new("b").disabled());
597        assert_eq!(r.len(), 2);
598        assert_eq!(r.enabled_passes().len(), 1);
599        assert_eq!(r.passes_in_phase(&CSEX2PassPhase::Early).len(), 1);
600    }
601    #[test]
602    pub(super) fn test_csex2_cache() {
603        let mut c = CSEX2Cache::new(4);
604        assert!(c.get(99).is_none());
605        c.put(99, vec![1, 2, 3]);
606        let v = c.get(99).expect("v should be present in map");
607        assert_eq!(v, &[1u8, 2, 3]);
608        assert!(c.hit_rate() > 0.0);
609        assert_eq!(c.live_count(), 1);
610    }
611    #[test]
612    pub(super) fn test_csex2_worklist() {
613        let mut w = CSEX2Worklist::new(10);
614        w.push(5);
615        w.push(3);
616        w.push(5);
617        assert_eq!(w.len(), 2);
618        assert!(w.contains(5));
619        let first = w.pop().expect("first should be available to pop");
620        assert!(!w.contains(first));
621    }
622    #[test]
623    pub(super) fn test_csex2_dom_tree() {
624        let mut dt = CSEX2DomTree::new(5);
625        dt.set_idom(1, 0);
626        dt.set_idom(2, 0);
627        dt.set_idom(3, 1);
628        dt.set_idom(4, 1);
629        assert!(dt.dominates(0, 3));
630        assert!(dt.dominates(1, 4));
631        assert!(!dt.dominates(2, 3));
632        assert_eq!(dt.depth_of(3), 2);
633    }
634    #[test]
635    pub(super) fn test_csex2_liveness() {
636        let mut lv = CSEX2Liveness::new(3);
637        lv.add_def(0, 1);
638        lv.add_use(1, 1);
639        assert!(lv.var_is_def_in_block(0, 1));
640        assert!(lv.var_is_used_in_block(1, 1));
641        assert!(!lv.var_is_def_in_block(1, 1));
642    }
643    #[test]
644    pub(super) fn test_csex2_const_folder() {
645        let mut cf = CSEX2ConstFolder::new();
646        assert_eq!(cf.add_i64(3, 4), Some(7));
647        assert_eq!(cf.div_i64(10, 0), None);
648        assert_eq!(cf.mul_i64(6, 7), Some(42));
649        assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
650        assert_eq!(cf.fold_count(), 3);
651        assert_eq!(cf.failure_count(), 1);
652    }
653    #[test]
654    pub(super) fn test_csex2_dep_graph() {
655        let mut g = CSEX2DepGraph::new(4);
656        g.add_edge(0, 1);
657        g.add_edge(1, 2);
658        g.add_edge(2, 3);
659        assert!(!g.has_cycle());
660        assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
661        assert_eq!(g.reachable(0).len(), 4);
662        let sccs = g.scc();
663        assert_eq!(sccs.len(), 4);
664    }
665}
oxilean_codegen/opt_cse/functions.rs

oxilean_codegen/opt_cse/
functions.rs
