oxilean_codegen/opt_mem2reg/
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, HashSet};
7
8use super::types::{
9    BindingInfo, BindingKind, DominanceFrontier, M2RAnalysisCache, M2RConstantFoldingHelper,
10    M2RDepGraph, M2RDominatorTree, M2RExtCache, M2RExtConstFolder, M2RExtDepGraph, M2RExtDomTree,
11    M2RExtLiveness, M2RExtPassConfig, M2RExtPassPhase, M2RExtPassRegistry, M2RExtPassStats,
12    M2RExtWorklist, M2RLivenessInfo, M2RPassConfig, M2RPassPhase, M2RPassRegistry, M2RPassStats,
13    M2RWorklist, M2RX2Cache, M2RX2ConstFolder, M2RX2DepGraph, M2RX2DomTree, M2RX2Liveness,
14    M2RX2PassConfig, M2RX2PassPhase, M2RX2PassRegistry, M2RX2PassStats, M2RX2Worklist, Mem2Reg,
15    Mem2RegConfig,
16};
17
18/// Count how many times each variable is referenced in `expr`.
19pub(super) fn count_uses(expr: &LcnfExpr, counts: &mut HashMap<LcnfVarId, usize>) {
20    match expr {
21        LcnfExpr::Let {
22            id, value, body, ..
23        } => {
24            count_uses_in_value(value, counts);
25            count_uses(body, counts);
26            let _ = id;
27        }
28        LcnfExpr::Case {
29            scrutinee,
30            alts,
31            default,
32            ..
33        } => {
34            *counts.entry(*scrutinee).or_insert(0) += 1;
35            for alt in alts {
36                count_uses(&alt.body, counts);
37            }
38            if let Some(def) = default {
39                count_uses(def, counts);
40            }
41        }
42        LcnfExpr::Return(arg) => count_uses_in_arg(arg, counts),
43        LcnfExpr::TailCall(func, args) => {
44            count_uses_in_arg(func, counts);
45            for a in args {
46                count_uses_in_arg(a, counts);
47            }
48        }
49        LcnfExpr::Unreachable => {}
50    }
51}
52pub(super) fn count_uses_in_value(value: &LcnfLetValue, counts: &mut HashMap<LcnfVarId, usize>) {
53    match value {
54        LcnfLetValue::App(func, args) => {
55            count_uses_in_arg(func, counts);
56            for a in args {
57                count_uses_in_arg(a, counts);
58            }
59        }
60        LcnfLetValue::Proj(_, _, var) => {
61            *counts.entry(*var).or_insert(0) += 1;
62        }
63        LcnfLetValue::Ctor(_, _, args) => {
64            for a in args {
65                count_uses_in_arg(a, counts);
66            }
67        }
68        LcnfLetValue::Lit(_) => {}
69        LcnfLetValue::Erased => {}
70        LcnfLetValue::FVar(var) => {
71            *counts.entry(*var).or_insert(0) += 1;
72        }
73        LcnfLetValue::Reset(var) => {
74            *counts.entry(*var).or_insert(0) += 1;
75        }
76        LcnfLetValue::Reuse(slot, _, _, args) => {
77            *counts.entry(*slot).or_insert(0) += 1;
78            for a in args {
79                count_uses_in_arg(a, counts);
80            }
81        }
82    }
83}
84pub(super) fn count_uses_in_arg(arg: &LcnfArg, counts: &mut HashMap<LcnfVarId, usize>) {
85    if let LcnfArg::Var(id) = arg {
86        *counts.entry(*id).or_insert(0) += 1;
87    }
88}
89/// Collect all variables defined anywhere in an expression.
90pub(super) fn collect_defined(expr: &LcnfExpr, defined: &mut HashSet<LcnfVarId>) {
91    match expr {
92        LcnfExpr::Let {
93            id, value, body, ..
94        } => {
95            defined.insert(*id);
96            collect_defined_in_value(value, defined);
97            collect_defined(body, defined);
98        }
99        LcnfExpr::Case { alts, default, .. } => {
100            for alt in alts {
101                for p in &alt.params {
102                    defined.insert(p.id);
103                }
104                collect_defined(&alt.body, defined);
105            }
106            if let Some(def) = default {
107                collect_defined(def, defined);
108            }
109        }
110        LcnfExpr::Return(_) | LcnfExpr::Unreachable | LcnfExpr::TailCall(_, _) => {}
111    }
112}
113pub(super) fn collect_defined_in_value(value: &LcnfLetValue, defined: &mut HashSet<LcnfVarId>) {
114    let _ = (value, defined);
115}
116/// Compute dominance frontiers by finding variables that appear defined in
117/// some branches of a `Case` but also used outside the case.
118pub(super) fn compute_dominance_frontier(expr: &LcnfExpr) -> DominanceFrontier {
119    let mut frontier = DominanceFrontier::default();
120    compute_frontier_rec(expr, &mut frontier);
121    frontier
122}
123pub(super) fn compute_frontier_rec(expr: &LcnfExpr, frontier: &mut DominanceFrontier) {
124    match expr {
125        LcnfExpr::Let { value: _, body, .. } => {
126            compute_frontier_rec(body, frontier);
127        }
128        LcnfExpr::Case { alts, default, .. } => {
129            let mut branch_defs: Vec<HashSet<LcnfVarId>> = Vec::new();
130            for alt in alts {
131                let mut defs = HashSet::new();
132                for p in &alt.params {
133                    defs.insert(p.id);
134                }
135                collect_defined(&alt.body, &mut defs);
136                compute_frontier_rec(&alt.body, frontier);
137                branch_defs.push(defs);
138            }
139            if let Some(def) = default {
140                let mut defs = HashSet::new();
141                collect_defined(def, &mut defs);
142                compute_frontier_rec(def, frontier);
143                branch_defs.push(defs);
144            }
145            if branch_defs.len() > 1 {
146                let all_defs: HashSet<LcnfVarId> = branch_defs.iter().flatten().cloned().collect();
147                for var in all_defs {
148                    let defined_in_all = branch_defs.iter().all(|d| d.contains(&var));
149                    if !defined_in_all {
150                        frontier.join_vars.insert(var);
151                    }
152                }
153            }
154        }
155        LcnfExpr::Return(_) | LcnfExpr::Unreachable | LcnfExpr::TailCall(_, _) => {}
156    }
157}
158/// Substitute all occurrences of `from` with `to` in `expr`.
159pub(super) fn substitute_var(expr: LcnfExpr, from: LcnfVarId, to: LcnfArg) -> LcnfExpr {
160    match expr {
161        LcnfExpr::Let {
162            id,
163            name,
164            ty,
165            value,
166            body,
167        } => {
168            let value2 = subst_in_value(value, from, &to);
169            let body2 = substitute_var(*body, from, to);
170            LcnfExpr::Let {
171                id,
172                name,
173                ty,
174                value: value2,
175                body: Box::new(body2),
176            }
177        }
178        LcnfExpr::Case {
179            scrutinee,
180            scrutinee_ty,
181            alts,
182            default,
183        } => {
184            let scrutinee2 = if scrutinee == from {
185                match &to {
186                    LcnfArg::Var(v) => *v,
187                    _ => scrutinee,
188                }
189            } else {
190                scrutinee
191            };
192            let alts2 = alts
193                .into_iter()
194                .map(|alt| LcnfAlt {
195                    ctor_name: alt.ctor_name,
196                    ctor_tag: alt.ctor_tag,
197                    params: alt.params,
198                    body: substitute_var(alt.body, from, to.clone()),
199                })
200                .collect();
201            let default2 = default.map(|d| Box::new(substitute_var(*d, from, to)));
202            LcnfExpr::Case {
203                scrutinee: scrutinee2,
204                scrutinee_ty,
205                alts: alts2,
206                default: default2,
207            }
208        }
209        LcnfExpr::Return(arg) => LcnfExpr::Return(subst_in_arg(arg, from, &to)),
210        LcnfExpr::TailCall(func, args) => {
211            let func2 = subst_in_arg(func, from, &to);
212            let args2 = args
213                .into_iter()
214                .map(|a| subst_in_arg(a, from, &to))
215                .collect();
216            LcnfExpr::TailCall(func2, args2)
217        }
218        LcnfExpr::Unreachable => LcnfExpr::Unreachable,
219    }
220}
221pub(super) fn subst_in_arg(arg: LcnfArg, from: LcnfVarId, to: &LcnfArg) -> LcnfArg {
222    match &arg {
223        LcnfArg::Var(id) if *id == from => to.clone(),
224        _ => arg,
225    }
226}
227pub(super) fn subst_in_value(value: LcnfLetValue, from: LcnfVarId, to: &LcnfArg) -> LcnfLetValue {
228    match value {
229        LcnfLetValue::App(func, args) => {
230            let func2 = subst_in_arg(func, from, to);
231            let args2 = args
232                .into_iter()
233                .map(|a| subst_in_arg(a, from, to))
234                .collect();
235            LcnfLetValue::App(func2, args2)
236        }
237        LcnfLetValue::Proj(name, idx, var) => {
238            let var2 = if var == from {
239                match to {
240                    LcnfArg::Var(v) => *v,
241                    _ => var,
242                }
243            } else {
244                var
245            };
246            LcnfLetValue::Proj(name, idx, var2)
247        }
248        LcnfLetValue::Ctor(name, tag, args) => {
249            let args2 = args
250                .into_iter()
251                .map(|a| subst_in_arg(a, from, to))
252                .collect();
253            LcnfLetValue::Ctor(name, tag, args2)
254        }
255        LcnfLetValue::FVar(var) => {
256            if var == from {
257                match to {
258                    LcnfArg::Var(v) => LcnfLetValue::FVar(*v),
259                    _ => LcnfLetValue::FVar(var),
260                }
261            } else {
262                LcnfLetValue::FVar(var)
263            }
264        }
265        LcnfLetValue::Reset(var) => {
266            let var2 = if var == from {
267                match to {
268                    LcnfArg::Var(v) => *v,
269                    _ => var,
270                }
271            } else {
272                var
273            };
274            LcnfLetValue::Reset(var2)
275        }
276        LcnfLetValue::Reuse(slot, name, tag, args) => {
277            let slot2 = if slot == from {
278                match to {
279                    LcnfArg::Var(v) => *v,
280                    _ => slot,
281                }
282            } else {
283                slot
284            };
285            let args2 = args
286                .into_iter()
287                .map(|a| subst_in_arg(a, from, to))
288                .collect();
289            LcnfLetValue::Reuse(slot2, name, tag, args2)
290        }
291        other => other,
292    }
293}
294/// Returns `true` if a let-value is promotable (pure, no memory side effects).
295pub(super) fn is_promotable(value: &LcnfLetValue) -> bool {
296    match value {
297        LcnfLetValue::Lit(_) => true,
298        LcnfLetValue::FVar(_) => true,
299        LcnfLetValue::Erased => true,
300        LcnfLetValue::Ctor(_, _, _) => true,
301        LcnfLetValue::Proj(_, _, _) => true,
302        LcnfLetValue::App(_, _) => false,
303        LcnfLetValue::Reset(_) => false,
304        LcnfLetValue::Reuse(_, _, _, _) => false,
305    }
306}
307/// Returns `true` if the value is a "trivial" scalar (literal or single var
308/// alias), the cheapest class to inline at every use site.
309pub(super) fn is_trivial(value: &LcnfLetValue) -> bool {
310    matches!(
311        value,
312        LcnfLetValue::Lit(_) | LcnfLetValue::FVar(_) | LcnfLetValue::Erased
313    )
314}
315/// Convert a promotable `LcnfLetValue` into an `LcnfArg` for substitution,
316/// returning `None` for values that have no direct `LcnfArg` representation.
317pub(super) fn let_value_to_arg(value: &LcnfLetValue) -> Option<LcnfArg> {
318    match value {
319        LcnfLetValue::Lit(l) => Some(LcnfArg::Lit(l.clone())),
320        LcnfLetValue::FVar(v) => Some(LcnfArg::Var(*v)),
321        LcnfLetValue::Erased => Some(LcnfArg::Erased),
322        _ => None,
323    }
324}
325/// Collect binding information recursively.
326pub(super) fn collect_binding_info(
327    expr: &LcnfExpr,
328    bindings: &mut HashMap<LcnfVarId, BindingInfo>,
329    use_counts: &HashMap<LcnfVarId, usize>,
330    frontier: &DominanceFrontier,
331    depth: usize,
332) {
333    match expr {
334        LcnfExpr::Let {
335            id,
336            ty,
337            value,
338            body,
339            ..
340        } => {
341            let kind = if frontier.join_vars.contains(id) {
342                BindingKind::MayJoin
343            } else {
344                match value {
345                    LcnfLetValue::Reset(_) | LcnfLetValue::Reuse(_, _, _, _) => {
346                        BindingKind::MemoryOp
347                    }
348                    _ => BindingKind::Immutable,
349                }
350            };
351            let use_count = *use_counts.get(id).unwrap_or(&0);
352            bindings.insert(
353                *id,
354                BindingInfo {
355                    kind,
356                    value: value.clone(),
357                    ty: ty.clone(),
358                    use_count,
359                    depth,
360                },
361            );
362            collect_binding_info(body, bindings, use_counts, frontier, depth + 1);
363        }
364        LcnfExpr::Case { alts, default, .. } => {
365            for alt in alts {
366                collect_binding_info(&alt.body, bindings, use_counts, frontier, depth + 1);
367            }
368            if let Some(def) = default {
369                collect_binding_info(def, bindings, use_counts, frontier, depth + 1);
370            }
371        }
372        LcnfExpr::Return(_) | LcnfExpr::Unreachable | LcnfExpr::TailCall(_, _) => {}
373    }
374}
375#[cfg(test)]
376mod tests {
377    use super::*;
378    use crate::lcnf::{
379        LcnfExpr, LcnfFunDecl, LcnfLetValue, LcnfLit, LcnfParam, LcnfType, LcnfVarId,
380    };
381    pub(super) fn make_decl(body: LcnfExpr) -> LcnfFunDecl {
382        LcnfFunDecl {
383            name: "test_fn".to_string(),
384            original_name: None,
385            params: vec![],
386            ret_type: LcnfType::Nat,
387            body,
388            is_recursive: false,
389            is_lifted: false,
390            inline_cost: 1,
391        }
392    }
393    /// `let x = 42; return x`  →  `return 42`
394    #[test]
395    pub(super) fn test_promote_literal_binding() {
396        let body = LcnfExpr::Let {
397            id: LcnfVarId(0),
398            name: "x".to_string(),
399            ty: LcnfType::Nat,
400            value: LcnfLetValue::Lit(LcnfLit::Nat(42)),
401            body: Box::new(LcnfExpr::Return(LcnfArg::Var(LcnfVarId(0)))),
402        };
403        let mut decl = make_decl(body);
404        let mut pass = Mem2Reg::new(Mem2RegConfig::default());
405        pass.run(&mut decl);
406        assert_eq!(decl.body, LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(42))));
407        assert_eq!(pass.report().bindings_promoted, 1);
408    }
409    /// `let x = fvar(y); return x`  →  `return y`
410    #[test]
411    pub(super) fn test_promote_fvar_binding() {
412        let body = LcnfExpr::Let {
413            id: LcnfVarId(1),
414            name: "x".to_string(),
415            ty: LcnfType::Nat,
416            value: LcnfLetValue::FVar(LcnfVarId(0)),
417            body: Box::new(LcnfExpr::Return(LcnfArg::Var(LcnfVarId(1)))),
418        };
419        let mut decl = make_decl(body);
420        let mut pass = Mem2Reg::new(Mem2RegConfig::default());
421        pass.run(&mut decl);
422        assert_eq!(decl.body, LcnfExpr::Return(LcnfArg::Var(LcnfVarId(0))));
423        assert_eq!(pass.report().bindings_promoted, 1);
424    }
425    /// Memory ops (Reset) must NOT be promoted.
426    #[test]
427    pub(super) fn test_no_promote_memory_op() {
428        let body = LcnfExpr::Let {
429            id: LcnfVarId(1),
430            name: "slot".to_string(),
431            ty: LcnfType::Object,
432            value: LcnfLetValue::Reset(LcnfVarId(0)),
433            body: Box::new(LcnfExpr::Return(LcnfArg::Var(LcnfVarId(1)))),
434        };
435        let mut decl = make_decl(body);
436        let mut pass = Mem2Reg::new(Mem2RegConfig::default());
437        pass.run(&mut decl);
438        assert!(matches!(decl.body, LcnfExpr::Let { .. }));
439        assert_eq!(pass.report().bindings_promoted, 0);
440    }
441    /// App bindings are NOT promotable (may have side effects).
442    #[test]
443    pub(super) fn test_no_promote_app() {
444        let body = LcnfExpr::Let {
445            id: LcnfVarId(1),
446            name: "r".to_string(),
447            ty: LcnfType::Nat,
448            value: LcnfLetValue::App(LcnfArg::Var(LcnfVarId(0)), vec![]),
449            body: Box::new(LcnfExpr::Return(LcnfArg::Var(LcnfVarId(1)))),
450        };
451        let mut decl = make_decl(body);
452        let mut pass = Mem2Reg::new(Mem2RegConfig::default());
453        pass.run(&mut decl);
454        assert!(matches!(decl.body, LcnfExpr::Let { .. }));
455        assert_eq!(pass.report().bindings_promoted, 0);
456    }
457    /// Conservative mode: erased bindings are still trivial and should be promoted.
458    #[test]
459    pub(super) fn test_conservative_promotes_trivial() {
460        let body = LcnfExpr::Let {
461            id: LcnfVarId(0),
462            name: "e".to_string(),
463            ty: LcnfType::Erased,
464            value: LcnfLetValue::Erased,
465            body: Box::new(LcnfExpr::Return(LcnfArg::Var(LcnfVarId(0)))),
466        };
467        let mut decl = make_decl(body);
468        let mut pass = Mem2Reg::new(Mem2RegConfig {
469            conservative: true,
470            ..Default::default()
471        });
472        pass.run(&mut decl);
473        assert_eq!(decl.body, LcnfExpr::Return(LcnfArg::Erased));
474        assert_eq!(pass.report().bindings_promoted, 1);
475    }
476    /// Chain: `let x = 1; let y = x; return y`  →  `return 1`
477    #[test]
478    pub(super) fn test_promote_chain() {
479        let body = LcnfExpr::Let {
480            id: LcnfVarId(0),
481            name: "x".to_string(),
482            ty: LcnfType::Nat,
483            value: LcnfLetValue::Lit(LcnfLit::Nat(1)),
484            body: Box::new(LcnfExpr::Let {
485                id: LcnfVarId(1),
486                name: "y".to_string(),
487                ty: LcnfType::Nat,
488                value: LcnfLetValue::FVar(LcnfVarId(0)),
489                body: Box::new(LcnfExpr::Return(LcnfArg::Var(LcnfVarId(1)))),
490            }),
491        };
492        let mut decl = make_decl(body);
493        let mut pass = Mem2Reg::new(Mem2RegConfig::default());
494        pass.run(&mut decl);
495        assert_eq!(decl.body, LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(1))));
496        assert_eq!(pass.report().bindings_promoted, 2);
497    }
498    /// Dominance frontier computation: variables defined only in one branch
499    /// are reported as join candidates.
500    #[test]
501    pub(super) fn test_dominance_frontier() {
502        let case_expr = LcnfExpr::Case {
503            scrutinee: LcnfVarId(0),
504            scrutinee_ty: LcnfType::Object,
505            alts: vec![LcnfAlt {
506                ctor_name: "A".to_string(),
507                ctor_tag: 0,
508                params: vec![LcnfParam {
509                    id: LcnfVarId(1),
510                    name: "p".to_string(),
511                    ty: LcnfType::Nat,
512                    erased: false,
513                    borrowed: false,
514                }],
515                body: LcnfExpr::Return(LcnfArg::Var(LcnfVarId(1))),
516            }],
517            default: Some(Box::new(LcnfExpr::Return(LcnfArg::Var(LcnfVarId(0))))),
518        };
519        let frontier = compute_dominance_frontier(&case_expr);
520        assert!(frontier.join_vars.contains(&LcnfVarId(1)));
521    }
522    /// `Mem2Reg::default_pass()` constructor smoke test.
523    #[test]
524    pub(super) fn test_default_pass_smoke() {
525        let body = LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(0)));
526        let mut decl = make_decl(body);
527        let mut pass = Mem2Reg::default_pass();
528        pass.run(&mut decl);
529        assert_eq!(pass.report().bindings_promoted, 0);
530    }
531}
532#[cfg(test)]
533mod M2R_infra_tests {
534    use super::*;
535    #[test]
536    pub(super) fn test_pass_config() {
537        let config = M2RPassConfig::new("test_pass", M2RPassPhase::Transformation);
538        assert!(config.enabled);
539        assert!(config.phase.is_modifying());
540        assert_eq!(config.phase.name(), "transformation");
541    }
542    #[test]
543    pub(super) fn test_pass_stats() {
544        let mut stats = M2RPassStats::new();
545        stats.record_run(10, 100, 3);
546        stats.record_run(20, 200, 5);
547        assert_eq!(stats.total_runs, 2);
548        assert!((stats.average_changes_per_run() - 15.0).abs() < 0.01);
549        assert!((stats.success_rate() - 1.0).abs() < 0.01);
550        let s = stats.format_summary();
551        assert!(s.contains("Runs: 2/2"));
552    }
553    #[test]
554    pub(super) fn test_pass_registry() {
555        let mut reg = M2RPassRegistry::new();
556        reg.register(M2RPassConfig::new("pass_a", M2RPassPhase::Analysis));
557        reg.register(M2RPassConfig::new("pass_b", M2RPassPhase::Transformation).disabled());
558        assert_eq!(reg.total_passes(), 2);
559        assert_eq!(reg.enabled_count(), 1);
560        reg.update_stats("pass_a", 5, 50, 2);
561        let stats = reg.get_stats("pass_a").expect("stats should exist");
562        assert_eq!(stats.total_changes, 5);
563    }
564    #[test]
565    pub(super) fn test_analysis_cache() {
566        let mut cache = M2RAnalysisCache::new(10);
567        cache.insert("key1".to_string(), vec![1, 2, 3]);
568        assert!(cache.get("key1").is_some());
569        assert!(cache.get("key2").is_none());
570        assert!((cache.hit_rate() - 0.5).abs() < 0.01);
571        cache.invalidate("key1");
572        assert!(!cache.entries["key1"].valid);
573        assert_eq!(cache.size(), 1);
574    }
575    #[test]
576    pub(super) fn test_worklist() {
577        let mut wl = M2RWorklist::new();
578        assert!(wl.push(1));
579        assert!(wl.push(2));
580        assert!(!wl.push(1));
581        assert_eq!(wl.len(), 2);
582        assert_eq!(wl.pop(), Some(1));
583        assert!(!wl.contains(1));
584        assert!(wl.contains(2));
585    }
586    #[test]
587    pub(super) fn test_dominator_tree() {
588        let mut dt = M2RDominatorTree::new(5);
589        dt.set_idom(1, 0);
590        dt.set_idom(2, 0);
591        dt.set_idom(3, 1);
592        assert!(dt.dominates(0, 3));
593        assert!(dt.dominates(1, 3));
594        assert!(!dt.dominates(2, 3));
595        assert!(dt.dominates(3, 3));
596    }
597    #[test]
598    pub(super) fn test_liveness() {
599        let mut liveness = M2RLivenessInfo::new(3);
600        liveness.add_def(0, 1);
601        liveness.add_use(1, 1);
602        assert!(liveness.defs[0].contains(&1));
603        assert!(liveness.uses[1].contains(&1));
604    }
605    #[test]
606    pub(super) fn test_constant_folding() {
607        assert_eq!(M2RConstantFoldingHelper::fold_add_i64(3, 4), Some(7));
608        assert_eq!(M2RConstantFoldingHelper::fold_div_i64(10, 0), None);
609        assert_eq!(M2RConstantFoldingHelper::fold_div_i64(10, 2), Some(5));
610        assert_eq!(
611            M2RConstantFoldingHelper::fold_bitand_i64(0b1100, 0b1010),
612            0b1000
613        );
614        assert_eq!(M2RConstantFoldingHelper::fold_bitnot_i64(0), -1);
615    }
616    #[test]
617    pub(super) fn test_dep_graph() {
618        let mut g = M2RDepGraph::new();
619        g.add_dep(1, 2);
620        g.add_dep(2, 3);
621        g.add_dep(1, 3);
622        assert_eq!(g.dependencies_of(2), vec![1]);
623        let topo = g.topological_sort();
624        assert_eq!(topo.len(), 3);
625        assert!(!g.has_cycle());
626        let pos: std::collections::HashMap<u32, usize> =
627            topo.iter().enumerate().map(|(i, &n)| (n, i)).collect();
628        assert!(pos[&1] < pos[&2]);
629        assert!(pos[&1] < pos[&3]);
630        assert!(pos[&2] < pos[&3]);
631    }
632}
633#[cfg(test)]
634mod m2rext_pass_tests {
635    use super::*;
636    #[test]
637    pub(super) fn test_m2rext_phase_order() {
638        assert_eq!(M2RExtPassPhase::Early.order(), 0);
639        assert_eq!(M2RExtPassPhase::Middle.order(), 1);
640        assert_eq!(M2RExtPassPhase::Late.order(), 2);
641        assert_eq!(M2RExtPassPhase::Finalize.order(), 3);
642        assert!(M2RExtPassPhase::Early.is_early());
643        assert!(!M2RExtPassPhase::Early.is_late());
644    }
645    #[test]
646    pub(super) fn test_m2rext_config_builder() {
647        let c = M2RExtPassConfig::new("p")
648            .with_phase(M2RExtPassPhase::Late)
649            .with_max_iter(50)
650            .with_debug(1);
651        assert_eq!(c.name, "p");
652        assert_eq!(c.max_iterations, 50);
653        assert!(c.is_debug_enabled());
654        assert!(c.enabled);
655        let c2 = c.disabled();
656        assert!(!c2.enabled);
657    }
658    #[test]
659    pub(super) fn test_m2rext_stats() {
660        let mut s = M2RExtPassStats::new();
661        s.visit();
662        s.visit();
663        s.modify();
664        s.iterate();
665        assert_eq!(s.nodes_visited, 2);
666        assert_eq!(s.nodes_modified, 1);
667        assert!(s.changed);
668        assert_eq!(s.iterations, 1);
669        let e = s.efficiency();
670        assert!((e - 0.5).abs() < 1e-9);
671    }
672    #[test]
673    pub(super) fn test_m2rext_registry() {
674        let mut r = M2RExtPassRegistry::new();
675        r.register(M2RExtPassConfig::new("a").with_phase(M2RExtPassPhase::Early));
676        r.register(M2RExtPassConfig::new("b").disabled());
677        assert_eq!(r.len(), 2);
678        assert_eq!(r.enabled_passes().len(), 1);
679        assert_eq!(r.passes_in_phase(&M2RExtPassPhase::Early).len(), 1);
680    }
681    #[test]
682    pub(super) fn test_m2rext_cache() {
683        let mut c = M2RExtCache::new(4);
684        assert!(c.get(99).is_none());
685        c.put(99, vec![1, 2, 3]);
686        let v = c.get(99).expect("v should be present in map");
687        assert_eq!(v, &[1u8, 2, 3]);
688        assert!(c.hit_rate() > 0.0);
689        assert_eq!(c.live_count(), 1);
690    }
691    #[test]
692    pub(super) fn test_m2rext_worklist() {
693        let mut w = M2RExtWorklist::new(10);
694        w.push(5);
695        w.push(3);
696        w.push(5);
697        assert_eq!(w.len(), 2);
698        assert!(w.contains(5));
699        let first = w.pop().expect("first should be available to pop");
700        assert!(!w.contains(first));
701    }
702    #[test]
703    pub(super) fn test_m2rext_dom_tree() {
704        let mut dt = M2RExtDomTree::new(5);
705        dt.set_idom(1, 0);
706        dt.set_idom(2, 0);
707        dt.set_idom(3, 1);
708        dt.set_idom(4, 1);
709        assert!(dt.dominates(0, 3));
710        assert!(dt.dominates(1, 4));
711        assert!(!dt.dominates(2, 3));
712        assert_eq!(dt.depth_of(3), 2);
713    }
714    #[test]
715    pub(super) fn test_m2rext_liveness() {
716        let mut lv = M2RExtLiveness::new(3);
717        lv.add_def(0, 1);
718        lv.add_use(1, 1);
719        assert!(lv.var_is_def_in_block(0, 1));
720        assert!(lv.var_is_used_in_block(1, 1));
721        assert!(!lv.var_is_def_in_block(1, 1));
722    }
723    #[test]
724    pub(super) fn test_m2rext_const_folder() {
725        let mut cf = M2RExtConstFolder::new();
726        assert_eq!(cf.add_i64(3, 4), Some(7));
727        assert_eq!(cf.div_i64(10, 0), None);
728        assert_eq!(cf.mul_i64(6, 7), Some(42));
729        assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
730        assert_eq!(cf.fold_count(), 3);
731        assert_eq!(cf.failure_count(), 1);
732    }
733    #[test]
734    pub(super) fn test_m2rext_dep_graph() {
735        let mut g = M2RExtDepGraph::new(4);
736        g.add_edge(0, 1);
737        g.add_edge(1, 2);
738        g.add_edge(2, 3);
739        assert!(!g.has_cycle());
740        assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
741        assert_eq!(g.reachable(0).len(), 4);
742        let sccs = g.scc();
743        assert_eq!(sccs.len(), 4);
744    }
745}
746#[cfg(test)]
747mod m2rx2_pass_tests {
748    use super::*;
749    #[test]
750    pub(super) fn test_m2rx2_phase_order() {
751        assert_eq!(M2RX2PassPhase::Early.order(), 0);
752        assert_eq!(M2RX2PassPhase::Middle.order(), 1);
753        assert_eq!(M2RX2PassPhase::Late.order(), 2);
754        assert_eq!(M2RX2PassPhase::Finalize.order(), 3);
755        assert!(M2RX2PassPhase::Early.is_early());
756        assert!(!M2RX2PassPhase::Early.is_late());
757    }
758    #[test]
759    pub(super) fn test_m2rx2_config_builder() {
760        let c = M2RX2PassConfig::new("p")
761            .with_phase(M2RX2PassPhase::Late)
762            .with_max_iter(50)
763            .with_debug(1);
764        assert_eq!(c.name, "p");
765        assert_eq!(c.max_iterations, 50);
766        assert!(c.is_debug_enabled());
767        assert!(c.enabled);
768        let c2 = c.disabled();
769        assert!(!c2.enabled);
770    }
771    #[test]
772    pub(super) fn test_m2rx2_stats() {
773        let mut s = M2RX2PassStats::new();
774        s.visit();
775        s.visit();
776        s.modify();
777        s.iterate();
778        assert_eq!(s.nodes_visited, 2);
779        assert_eq!(s.nodes_modified, 1);
780        assert!(s.changed);
781        assert_eq!(s.iterations, 1);
782        let e = s.efficiency();
783        assert!((e - 0.5).abs() < 1e-9);
784    }
785    #[test]
786    pub(super) fn test_m2rx2_registry() {
787        let mut r = M2RX2PassRegistry::new();
788        r.register(M2RX2PassConfig::new("a").with_phase(M2RX2PassPhase::Early));
789        r.register(M2RX2PassConfig::new("b").disabled());
790        assert_eq!(r.len(), 2);
791        assert_eq!(r.enabled_passes().len(), 1);
792        assert_eq!(r.passes_in_phase(&M2RX2PassPhase::Early).len(), 1);
793    }
794    #[test]
795    pub(super) fn test_m2rx2_cache() {
796        let mut c = M2RX2Cache::new(4);
797        assert!(c.get(99).is_none());
798        c.put(99, vec![1, 2, 3]);
799        let v = c.get(99).expect("v should be present in map");
800        assert_eq!(v, &[1u8, 2, 3]);
801        assert!(c.hit_rate() > 0.0);
802        assert_eq!(c.live_count(), 1);
803    }
804    #[test]
805    pub(super) fn test_m2rx2_worklist() {
806        let mut w = M2RX2Worklist::new(10);
807        w.push(5);
808        w.push(3);
809        w.push(5);
810        assert_eq!(w.len(), 2);
811        assert!(w.contains(5));
812        let first = w.pop().expect("first should be available to pop");
813        assert!(!w.contains(first));
814    }
815    #[test]
816    pub(super) fn test_m2rx2_dom_tree() {
817        let mut dt = M2RX2DomTree::new(5);
818        dt.set_idom(1, 0);
819        dt.set_idom(2, 0);
820        dt.set_idom(3, 1);
821        dt.set_idom(4, 1);
822        assert!(dt.dominates(0, 3));
823        assert!(dt.dominates(1, 4));
824        assert!(!dt.dominates(2, 3));
825        assert_eq!(dt.depth_of(3), 2);
826    }
827    #[test]
828    pub(super) fn test_m2rx2_liveness() {
829        let mut lv = M2RX2Liveness::new(3);
830        lv.add_def(0, 1);
831        lv.add_use(1, 1);
832        assert!(lv.var_is_def_in_block(0, 1));
833        assert!(lv.var_is_used_in_block(1, 1));
834        assert!(!lv.var_is_def_in_block(1, 1));
835    }
836    #[test]
837    pub(super) fn test_m2rx2_const_folder() {
838        let mut cf = M2RX2ConstFolder::new();
839        assert_eq!(cf.add_i64(3, 4), Some(7));
840        assert_eq!(cf.div_i64(10, 0), None);
841        assert_eq!(cf.mul_i64(6, 7), Some(42));
842        assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
843        assert_eq!(cf.fold_count(), 3);
844        assert_eq!(cf.failure_count(), 1);
845    }
846    #[test]
847    pub(super) fn test_m2rx2_dep_graph() {
848        let mut g = M2RX2DepGraph::new(4);
849        g.add_edge(0, 1);
850        g.add_edge(1, 2);
851        g.add_edge(2, 3);
852        assert!(!g.has_cycle());
853        assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
854        assert_eq!(g.reachable(0).len(), 4);
855        let sccs = g.scc();
856        assert_eq!(sccs.len(), 4);
857    }
858}
oxilean_codegen/opt_mem2reg/functions.rs

oxilean_codegen/opt_mem2reg/
functions.rs
