oxilean_codegen/opt_dse/
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    DSEAnalysisCache, DSEConstantFoldingHelper, DSEDepGraph, DSEDominatorTree, DSEExtCache,
10    DSEExtConstFolder, DSEExtDepGraph, DSEExtDomTree, DSEExtLiveness, DSEExtPassConfig,
11    DSEExtPassPhase, DSEExtPassRegistry, DSEExtPassStats, DSEExtWorklist, DSELivenessInfo, DSEPass,
12    DSEPassConfig, DSEPassPhase, DSEPassRegistry, DSEPassStats, DSEReport, DSEWorklist, DSEX2Cache,
13    DSEX2ConstFolder, DSEX2DepGraph, DSEX2DomTree, DSEX2Liveness, DSEX2PassConfig, DSEX2PassPhase,
14    DSEX2PassRegistry, DSEX2PassStats, DSEX2Worklist, DeadStoreConfig, LiveVariableInfo, StoreInfo,
15    UseDefChain,
16};
17
18/// Alias for `LiveVariableInfo` (used as the return type of `compute_liveness`).
19pub type LivenessInfo = LiveVariableInfo;
20/// Collect the set of all variables *defined* (introduced by let) in `expr`.
21pub(super) fn collect_defs_uses(
22    expr: &LcnfExpr,
23    defs: &mut HashSet<LcnfVarId>,
24    uses: &mut HashSet<LcnfVarId>,
25) {
26    match expr {
27        LcnfExpr::Let {
28            id, value, body, ..
29        } => {
30            defs.insert(*id);
31            collect_used_in_let_value_into(value, uses);
32            collect_defs_uses(body, defs, uses);
33        }
34        LcnfExpr::Case {
35            scrutinee,
36            alts,
37            default,
38            ..
39        } => {
40            uses.insert(*scrutinee);
41            for alt in alts {
42                collect_defs_uses(&alt.body, defs, uses);
43            }
44            if let Some(d) = default {
45                collect_defs_uses(d, defs, uses);
46            }
47        }
48        LcnfExpr::Return(arg) => collect_used_in_arg_into(arg, uses),
49        LcnfExpr::TailCall(f, args) => {
50            collect_used_in_arg_into(f, uses);
51            for a in args {
52                collect_used_in_arg_into(a, uses);
53            }
54        }
55        LcnfExpr::Unreachable => {}
56    }
57}
58pub(super) fn collect_used_in_arg_into(arg: &LcnfArg, out: &mut HashSet<LcnfVarId>) {
59    if let LcnfArg::Var(v) = arg {
60        out.insert(*v);
61    }
62}
63pub(super) fn collect_used_in_let_value_into(val: &LcnfLetValue, out: &mut HashSet<LcnfVarId>) {
64    match val {
65        LcnfLetValue::App(f, args) => {
66            collect_used_in_arg_into(f, out);
67            for a in args {
68                collect_used_in_arg_into(a, out);
69            }
70        }
71        LcnfLetValue::Proj(_, _, v) => {
72            out.insert(*v);
73        }
74        LcnfLetValue::Ctor(_, _, args) => {
75            for a in args {
76                collect_used_in_arg_into(a, out);
77            }
78        }
79        LcnfLetValue::FVar(v) => {
80            out.insert(*v);
81        }
82        LcnfLetValue::Reset(v) => {
83            out.insert(*v);
84        }
85        LcnfLetValue::Reuse(slot, _, _, args) => {
86            out.insert(*slot);
87            for a in args {
88                collect_used_in_arg_into(a, out);
89            }
90        }
91        LcnfLetValue::Lit(_) | LcnfLetValue::Erased => {}
92    }
93}
94/// Collect all variables *used* (read) in `expr`.
95pub(super) fn collect_used_in_expr(expr: &LcnfExpr, out: &mut HashSet<LcnfVarId>) {
96    match expr {
97        LcnfExpr::Let { value, body, .. } => {
98            collect_used_in_let_value_into(value, out);
99            collect_used_in_expr(body, out);
100        }
101        LcnfExpr::Case {
102            scrutinee,
103            alts,
104            default,
105            ..
106        } => {
107            out.insert(*scrutinee);
108            for alt in alts {
109                collect_used_in_expr(&alt.body, out);
110            }
111            if let Some(d) = default {
112                collect_used_in_expr(d, out);
113            }
114        }
115        LcnfExpr::Return(arg) => collect_used_in_arg_into(arg, out),
116        LcnfExpr::TailCall(f, args) => {
117            collect_used_in_arg_into(f, out);
118            for a in args {
119                collect_used_in_arg_into(a, out);
120            }
121        }
122        LcnfExpr::Unreachable => {}
123    }
124}
125/// Backward liveness pass: walk `expr` from bottom to top, maintaining
126/// `live` as the set of variables live *below* the current point.
127/// Records `live_after[x]` for each let-binding `x`.
128pub(super) fn backward_liveness(
129    expr: &LcnfExpr,
130    live: &mut HashSet<LcnfVarId>,
131    info: &mut LiveVariableInfo,
132) {
133    match expr {
134        LcnfExpr::Let {
135            id, value, body, ..
136        } => {
137            backward_liveness(body, live, info);
138            info.live_after.insert(*id, live.clone());
139            live.remove(id);
140            collect_used_in_let_value_into(value, live);
141        }
142        LcnfExpr::Case {
143            scrutinee,
144            alts,
145            default,
146            ..
147        } => {
148            let mut branch_live: HashSet<LcnfVarId> = HashSet::new();
149            for alt in alts {
150                let mut bl = live.clone();
151                backward_liveness(&alt.body, &mut bl, info);
152                branch_live.extend(bl);
153            }
154            if let Some(d) = default {
155                let mut bl = live.clone();
156                backward_liveness(d, &mut bl, info);
157                branch_live.extend(bl);
158            }
159            *live = branch_live;
160            live.insert(*scrutinee);
161        }
162        LcnfExpr::Return(arg) => {
163            collect_used_in_arg_into(arg, live);
164        }
165        LcnfExpr::TailCall(f, args) => {
166            collect_used_in_arg_into(f, live);
167            for a in args {
168                collect_used_in_arg_into(a, live);
169            }
170        }
171        LcnfExpr::Unreachable => {}
172    }
173}
174/// Check if a `LcnfLetValue` is "side-effect free" (no allocation or call).
175pub(super) fn is_pure(val: &LcnfLetValue, aggressive: bool) -> bool {
176    match val {
177        LcnfLetValue::Lit(_) | LcnfLetValue::Erased | LcnfLetValue::FVar(_) => true,
178        LcnfLetValue::Proj(..) => true,
179        LcnfLetValue::Ctor(..) => aggressive,
180        LcnfLetValue::App(..) | LcnfLetValue::Reset(..) | LcnfLetValue::Reuse(..) => false,
181    }
182}
183/// Recursively remove dead let-bindings from `expr`.
184pub(super) fn remove_dead_lets(
185    expr: &mut LcnfExpr,
186    dead: &HashSet<LcnfVarId>,
187    cfg: &DeadStoreConfig,
188) {
189    loop {
190        match expr {
191            LcnfExpr::Let {
192                id, value, body, ..
193            } if dead.contains(id) && is_pure(value, cfg.aggressive) => {
194                let new_expr = std::mem::replace(body.as_mut(), LcnfExpr::Unreachable);
195                *expr = new_expr;
196            }
197            LcnfExpr::Let { body, .. } => {
198                remove_dead_lets(body, dead, cfg);
199                break;
200            }
201            LcnfExpr::Case { alts, default, .. } => {
202                for alt in alts.iter_mut() {
203                    remove_dead_lets(&mut alt.body, dead, cfg);
204                }
205                if let Some(d) = default {
206                    remove_dead_lets(d, dead, cfg);
207                }
208                break;
209            }
210            LcnfExpr::Return(_) | LcnfExpr::Unreachable | LcnfExpr::TailCall(..) => break,
211        }
212    }
213}
214pub(super) fn var(n: u64) -> LcnfVarId {
215    LcnfVarId(n)
216}
217pub(super) fn lit_val(n: u64) -> LcnfLetValue {
218    LcnfLetValue::Lit(LcnfLit::Nat(n))
219}
220pub(super) fn arg_var(n: u64) -> LcnfArg {
221    LcnfArg::Var(LcnfVarId(n))
222}
223pub(super) fn arg_lit(n: u64) -> LcnfArg {
224    LcnfArg::Lit(LcnfLit::Nat(n))
225}
226pub(super) fn make_decl(name: &str, body: LcnfExpr) -> LcnfFunDecl {
227    LcnfFunDecl {
228        name: name.to_string(),
229        params: vec![],
230        ret_type: LcnfType::Nat,
231        original_name: None,
232        is_recursive: false,
233        is_lifted: false,
234        inline_cost: 0,
235        body,
236    }
237}
238#[cfg(test)]
239mod tests {
240    use super::*;
241    pub(super) fn let_nat(id: u64, n: u64, body: LcnfExpr) -> LcnfExpr {
242        LcnfExpr::Let {
243            id: var(id),
244            name: format!("x{}", var(id).0),
245            ty: LcnfType::Nat,
246            value: lit_val(n),
247            body: Box::new(body),
248        }
249    }
250    pub(super) fn let_fvar(id: u64, src: u64, body: LcnfExpr) -> LcnfExpr {
251        LcnfExpr::Let {
252            id: var(id),
253            name: format!("x{}", var(id).0),
254            ty: LcnfType::Nat,
255            value: LcnfLetValue::FVar(var(src)),
256            body: Box::new(body),
257        }
258    }
259    #[test]
260    pub(super) fn test_dse_default_config() {
261        let cfg = DeadStoreConfig::default();
262        assert!(!cfg.check_aliasing);
263        assert!(!cfg.aggressive);
264    }
265    #[test]
266    pub(super) fn test_dse_report_default() {
267        let r = DSEReport::default();
268        assert_eq!(r.stores_analyzed, 0);
269        assert_eq!(r.dead_stores_eliminated, 0);
270        assert_eq!(r.bytes_saved, 0);
271    }
272    #[test]
273    pub(super) fn test_dse_report_merge() {
274        let mut r1 = DSEReport {
275            stores_analyzed: 4,
276            dead_stores_eliminated: 2,
277            bytes_saved: 128,
278        };
279        let r2 = DSEReport {
280            stores_analyzed: 3,
281            dead_stores_eliminated: 1,
282            bytes_saved: 64,
283        };
284        r1.merge(&r2);
285        assert_eq!(r1.stores_analyzed, 7);
286        assert_eq!(r1.dead_stores_eliminated, 3);
287        assert_eq!(r1.bytes_saved, 192);
288    }
289    #[test]
290    pub(super) fn test_usedefchain_add_use() {
291        let mut udc = UseDefChain::new();
292        udc.add_use(var(1), var(2));
293        assert!(udc.has_uses(&var(1)));
294        assert!(!udc.has_uses(&var(99)));
295    }
296    #[test]
297    pub(super) fn test_usedefchain_add_def() {
298        let mut udc = UseDefChain::new();
299        udc.add_def(var(5), lit_val(42));
300        assert!(udc.defs.contains_key(&var(5)));
301    }
302    #[test]
303    pub(super) fn test_store_info_construction() {
304        let si = StoreInfo {
305            var: var(3),
306            value: lit_val(7),
307            overwritten_before_read: false,
308        };
309        assert_eq!(si.var, var(3));
310        assert!(!si.overwritten_before_read);
311    }
312    #[test]
313    pub(super) fn test_live_variable_info_default() {
314        let lvi = LiveVariableInfo::new();
315        assert!(lvi.live_at_entry.is_empty());
316    }
317    #[test]
318    pub(super) fn test_compute_liveness_return_only() {
319        let decl = make_decl("f", LcnfExpr::Return(arg_var(5)));
320        let pass = DSEPass::default();
321        let liveness = pass.compute_liveness(&decl);
322        assert!(liveness.live_at_entry.contains(&var(5)));
323    }
324    #[test]
325    pub(super) fn test_find_dead_stores_unused_lit() {
326        let body = let_nat(1, 42, LcnfExpr::Return(arg_lit(0)));
327        let decl = make_decl("f", body);
328        let mut pass = DSEPass::default();
329        let liveness = pass.compute_liveness(&decl);
330        let dead = pass.find_dead_stores(&decl, &liveness);
331        assert!(dead.contains(&var(1)));
332    }
333    #[test]
334    pub(super) fn test_find_dead_stores_used_var() {
335        let body = let_nat(1, 42, LcnfExpr::Return(arg_var(1)));
336        let decl = make_decl("f", body);
337        let mut pass = DSEPass::default();
338        let liveness = pass.compute_liveness(&decl);
339        let dead = pass.find_dead_stores(&decl, &liveness);
340        assert!(!dead.contains(&var(1)));
341    }
342    #[test]
343    pub(super) fn test_eliminate_dead_stores_removes_unused_let() {
344        let body = let_nat(1, 42, LcnfExpr::Return(arg_lit(0)));
345        let mut decl = make_decl("f", body);
346        let mut pass = DSEPass::default();
347        let liveness = pass.compute_liveness(&decl);
348        let dead = pass.find_dead_stores(&decl, &liveness);
349        pass.eliminate_dead_stores(&mut decl, &dead);
350        assert!(matches!(decl.body, LcnfExpr::Return(_)));
351    }
352    #[test]
353    pub(super) fn test_run_removes_dead_stores() {
354        let body = let_nat(1, 42, LcnfExpr::Return(arg_lit(0)));
355        let mut decls = vec![make_decl("f", body)];
356        let mut pass = DSEPass::default();
357        pass.run(&mut decls);
358        assert!(pass.report().dead_stores_eliminated >= 1);
359        assert!(matches!(decls[0].body, LcnfExpr::Return(_)));
360    }
361    #[test]
362    pub(super) fn test_run_keeps_live_stores() {
363        let body = let_nat(1, 42, LcnfExpr::Return(arg_var(1)));
364        let mut decls = vec![make_decl("f", body)];
365        let mut pass = DSEPass::default();
366        pass.run(&mut decls);
367        assert_eq!(pass.report().dead_stores_eliminated, 0);
368        assert!(matches!(decls[0].body, LcnfExpr::Let { .. }));
369    }
370    #[test]
371    pub(super) fn test_run_chain_of_dead_stores() {
372        let body = let_nat(1, 1, let_nat(2, 2, LcnfExpr::Return(arg_lit(0))));
373        let mut decls = vec![make_decl("f", body)];
374        let mut pass = DSEPass::default();
375        pass.run(&mut decls);
376        assert!(pass.report().dead_stores_eliminated >= 2);
377    }
378    #[test]
379    pub(super) fn test_run_fvar_dead() {
380        let body = let_nat(1, 10, let_fvar(2, 1, LcnfExpr::Return(arg_var(1))));
381        let mut decls = vec![make_decl("f", body)];
382        let mut pass = DSEPass::default();
383        pass.run(&mut decls);
384        assert!(pass.report().dead_stores_eliminated >= 1);
385    }
386    #[test]
387    pub(super) fn test_is_pure_lit() {
388        assert!(is_pure(&lit_val(0), false));
389    }
390    #[test]
391    pub(super) fn test_is_pure_app_not_pure() {
392        let val = LcnfLetValue::App(LcnfArg::Lit(LcnfLit::Nat(0)), vec![]);
393        assert!(!is_pure(&val, false));
394        assert!(!is_pure(&val, true));
395    }
396    #[test]
397    pub(super) fn test_is_pure_ctor_aggressive() {
398        let val = LcnfLetValue::Ctor("Foo".to_string(), 0, vec![]);
399        assert!(!is_pure(&val, false));
400        assert!(is_pure(&val, true));
401    }
402    #[test]
403    pub(super) fn test_run_multiple_decls() {
404        let mut decls = vec![
405            make_decl("a", let_nat(1, 5, LcnfExpr::Return(arg_lit(0)))),
406            make_decl("b", let_nat(2, 6, LcnfExpr::Return(arg_lit(0)))),
407        ];
408        let mut pass = DSEPass::default();
409        pass.run(&mut decls);
410        assert!(pass.report().dead_stores_eliminated >= 2);
411    }
412    #[test]
413    pub(super) fn test_bytes_saved_proportional() {
414        let body = let_nat(1, 1, LcnfExpr::Return(arg_lit(0)));
415        let mut decls = vec![make_decl("f", body)];
416        let mut pass = DSEPass::default();
417        pass.run(&mut decls);
418        let r = pass.report();
419        assert_eq!(r.bytes_saved, r.dead_stores_eliminated * 64);
420    }
421}
422#[cfg(test)]
423mod DSE_infra_tests {
424    use super::*;
425    #[test]
426    pub(super) fn test_pass_config() {
427        let config = DSEPassConfig::new("test_pass", DSEPassPhase::Transformation);
428        assert!(config.enabled);
429        assert!(config.phase.is_modifying());
430        assert_eq!(config.phase.name(), "transformation");
431    }
432    #[test]
433    pub(super) fn test_pass_stats() {
434        let mut stats = DSEPassStats::new();
435        stats.record_run(10, 100, 3);
436        stats.record_run(20, 200, 5);
437        assert_eq!(stats.total_runs, 2);
438        assert!((stats.average_changes_per_run() - 15.0).abs() < 0.01);
439        assert!((stats.success_rate() - 1.0).abs() < 0.01);
440        let s = stats.format_summary();
441        assert!(s.contains("Runs: 2/2"));
442    }
443    #[test]
444    pub(super) fn test_pass_registry() {
445        let mut reg = DSEPassRegistry::new();
446        reg.register(DSEPassConfig::new("pass_a", DSEPassPhase::Analysis));
447        reg.register(DSEPassConfig::new("pass_b", DSEPassPhase::Transformation).disabled());
448        assert_eq!(reg.total_passes(), 2);
449        assert_eq!(reg.enabled_count(), 1);
450        reg.update_stats("pass_a", 5, 50, 2);
451        let stats = reg.get_stats("pass_a").expect("stats should exist");
452        assert_eq!(stats.total_changes, 5);
453    }
454    #[test]
455    pub(super) fn test_analysis_cache() {
456        let mut cache = DSEAnalysisCache::new(10);
457        cache.insert("key1".to_string(), vec![1, 2, 3]);
458        assert!(cache.get("key1").is_some());
459        assert!(cache.get("key2").is_none());
460        assert!((cache.hit_rate() - 0.5).abs() < 0.01);
461        cache.invalidate("key1");
462        assert!(!cache.entries["key1"].valid);
463        assert_eq!(cache.size(), 1);
464    }
465    #[test]
466    pub(super) fn test_worklist() {
467        let mut wl = DSEWorklist::new();
468        assert!(wl.push(1));
469        assert!(wl.push(2));
470        assert!(!wl.push(1));
471        assert_eq!(wl.len(), 2);
472        assert_eq!(wl.pop(), Some(1));
473        assert!(!wl.contains(1));
474        assert!(wl.contains(2));
475    }
476    #[test]
477    pub(super) fn test_dominator_tree() {
478        let mut dt = DSEDominatorTree::new(5);
479        dt.set_idom(1, 0);
480        dt.set_idom(2, 0);
481        dt.set_idom(3, 1);
482        assert!(dt.dominates(0, 3));
483        assert!(dt.dominates(1, 3));
484        assert!(!dt.dominates(2, 3));
485        assert!(dt.dominates(3, 3));
486    }
487    #[test]
488    pub(super) fn test_liveness() {
489        let mut liveness = DSELivenessInfo::new(3);
490        liveness.add_def(0, 1);
491        liveness.add_use(1, 1);
492        assert!(liveness.defs[0].contains(&1));
493        assert!(liveness.uses[1].contains(&1));
494    }
495    #[test]
496    pub(super) fn test_constant_folding() {
497        assert_eq!(DSEConstantFoldingHelper::fold_add_i64(3, 4), Some(7));
498        assert_eq!(DSEConstantFoldingHelper::fold_div_i64(10, 0), None);
499        assert_eq!(DSEConstantFoldingHelper::fold_div_i64(10, 2), Some(5));
500        assert_eq!(
501            DSEConstantFoldingHelper::fold_bitand_i64(0b1100, 0b1010),
502            0b1000
503        );
504        assert_eq!(DSEConstantFoldingHelper::fold_bitnot_i64(0), -1);
505    }
506    #[test]
507    pub(super) fn test_dep_graph() {
508        let mut g = DSEDepGraph::new();
509        g.add_dep(1, 2);
510        g.add_dep(2, 3);
511        g.add_dep(1, 3);
512        assert_eq!(g.dependencies_of(2), vec![1]);
513        let topo = g.topological_sort();
514        assert_eq!(topo.len(), 3);
515        assert!(!g.has_cycle());
516        let pos: std::collections::HashMap<u32, usize> =
517            topo.iter().enumerate().map(|(i, &n)| (n, i)).collect();
518        assert!(pos[&1] < pos[&2]);
519        assert!(pos[&1] < pos[&3]);
520        assert!(pos[&2] < pos[&3]);
521    }
522}
523#[cfg(test)]
524mod dseext_pass_tests {
525    use super::*;
526    #[test]
527    pub(super) fn test_dseext_phase_order() {
528        assert_eq!(DSEExtPassPhase::Early.order(), 0);
529        assert_eq!(DSEExtPassPhase::Middle.order(), 1);
530        assert_eq!(DSEExtPassPhase::Late.order(), 2);
531        assert_eq!(DSEExtPassPhase::Finalize.order(), 3);
532        assert!(DSEExtPassPhase::Early.is_early());
533        assert!(!DSEExtPassPhase::Early.is_late());
534    }
535    #[test]
536    pub(super) fn test_dseext_config_builder() {
537        let c = DSEExtPassConfig::new("p")
538            .with_phase(DSEExtPassPhase::Late)
539            .with_max_iter(50)
540            .with_debug(1);
541        assert_eq!(c.name, "p");
542        assert_eq!(c.max_iterations, 50);
543        assert!(c.is_debug_enabled());
544        assert!(c.enabled);
545        let c2 = c.disabled();
546        assert!(!c2.enabled);
547    }
548    #[test]
549    pub(super) fn test_dseext_stats() {
550        let mut s = DSEExtPassStats::new();
551        s.visit();
552        s.visit();
553        s.modify();
554        s.iterate();
555        assert_eq!(s.nodes_visited, 2);
556        assert_eq!(s.nodes_modified, 1);
557        assert!(s.changed);
558        assert_eq!(s.iterations, 1);
559        let e = s.efficiency();
560        assert!((e - 0.5).abs() < 1e-9);
561    }
562    #[test]
563    pub(super) fn test_dseext_registry() {
564        let mut r = DSEExtPassRegistry::new();
565        r.register(DSEExtPassConfig::new("a").with_phase(DSEExtPassPhase::Early));
566        r.register(DSEExtPassConfig::new("b").disabled());
567        assert_eq!(r.len(), 2);
568        assert_eq!(r.enabled_passes().len(), 1);
569        assert_eq!(r.passes_in_phase(&DSEExtPassPhase::Early).len(), 1);
570    }
571    #[test]
572    pub(super) fn test_dseext_cache() {
573        let mut c = DSEExtCache::new(4);
574        assert!(c.get(99).is_none());
575        c.put(99, vec![1, 2, 3]);
576        let v = c.get(99).expect("v should be present in map");
577        assert_eq!(v, &[1u8, 2, 3]);
578        assert!(c.hit_rate() > 0.0);
579        assert_eq!(c.live_count(), 1);
580    }
581    #[test]
582    pub(super) fn test_dseext_worklist() {
583        let mut w = DSEExtWorklist::new(10);
584        w.push(5);
585        w.push(3);
586        w.push(5);
587        assert_eq!(w.len(), 2);
588        assert!(w.contains(5));
589        let first = w.pop().expect("first should be available to pop");
590        assert!(!w.contains(first));
591    }
592    #[test]
593    pub(super) fn test_dseext_dom_tree() {
594        let mut dt = DSEExtDomTree::new(5);
595        dt.set_idom(1, 0);
596        dt.set_idom(2, 0);
597        dt.set_idom(3, 1);
598        dt.set_idom(4, 1);
599        assert!(dt.dominates(0, 3));
600        assert!(dt.dominates(1, 4));
601        assert!(!dt.dominates(2, 3));
602        assert_eq!(dt.depth_of(3), 2);
603    }
604    #[test]
605    pub(super) fn test_dseext_liveness() {
606        let mut lv = DSEExtLiveness::new(3);
607        lv.add_def(0, 1);
608        lv.add_use(1, 1);
609        assert!(lv.var_is_def_in_block(0, 1));
610        assert!(lv.var_is_used_in_block(1, 1));
611        assert!(!lv.var_is_def_in_block(1, 1));
612    }
613    #[test]
614    pub(super) fn test_dseext_const_folder() {
615        let mut cf = DSEExtConstFolder::new();
616        assert_eq!(cf.add_i64(3, 4), Some(7));
617        assert_eq!(cf.div_i64(10, 0), None);
618        assert_eq!(cf.mul_i64(6, 7), Some(42));
619        assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
620        assert_eq!(cf.fold_count(), 3);
621        assert_eq!(cf.failure_count(), 1);
622    }
623    #[test]
624    pub(super) fn test_dseext_dep_graph() {
625        let mut g = DSEExtDepGraph::new(4);
626        g.add_edge(0, 1);
627        g.add_edge(1, 2);
628        g.add_edge(2, 3);
629        assert!(!g.has_cycle());
630        assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
631        assert_eq!(g.reachable(0).len(), 4);
632        let sccs = g.scc();
633        assert_eq!(sccs.len(), 4);
634    }
635}
636#[cfg(test)]
637mod dsex2_pass_tests {
638    use super::*;
639    #[test]
640    pub(super) fn test_dsex2_phase_order() {
641        assert_eq!(DSEX2PassPhase::Early.order(), 0);
642        assert_eq!(DSEX2PassPhase::Middle.order(), 1);
643        assert_eq!(DSEX2PassPhase::Late.order(), 2);
644        assert_eq!(DSEX2PassPhase::Finalize.order(), 3);
645        assert!(DSEX2PassPhase::Early.is_early());
646        assert!(!DSEX2PassPhase::Early.is_late());
647    }
648    #[test]
649    pub(super) fn test_dsex2_config_builder() {
650        let c = DSEX2PassConfig::new("p")
651            .with_phase(DSEX2PassPhase::Late)
652            .with_max_iter(50)
653            .with_debug(1);
654        assert_eq!(c.name, "p");
655        assert_eq!(c.max_iterations, 50);
656        assert!(c.is_debug_enabled());
657        assert!(c.enabled);
658        let c2 = c.disabled();
659        assert!(!c2.enabled);
660    }
661    #[test]
662    pub(super) fn test_dsex2_stats() {
663        let mut s = DSEX2PassStats::new();
664        s.visit();
665        s.visit();
666        s.modify();
667        s.iterate();
668        assert_eq!(s.nodes_visited, 2);
669        assert_eq!(s.nodes_modified, 1);
670        assert!(s.changed);
671        assert_eq!(s.iterations, 1);
672        let e = s.efficiency();
673        assert!((e - 0.5).abs() < 1e-9);
674    }
675    #[test]
676    pub(super) fn test_dsex2_registry() {
677        let mut r = DSEX2PassRegistry::new();
678        r.register(DSEX2PassConfig::new("a").with_phase(DSEX2PassPhase::Early));
679        r.register(DSEX2PassConfig::new("b").disabled());
680        assert_eq!(r.len(), 2);
681        assert_eq!(r.enabled_passes().len(), 1);
682        assert_eq!(r.passes_in_phase(&DSEX2PassPhase::Early).len(), 1);
683    }
684    #[test]
685    pub(super) fn test_dsex2_cache() {
686        let mut c = DSEX2Cache::new(4);
687        assert!(c.get(99).is_none());
688        c.put(99, vec![1, 2, 3]);
689        let v = c.get(99).expect("v should be present in map");
690        assert_eq!(v, &[1u8, 2, 3]);
691        assert!(c.hit_rate() > 0.0);
692        assert_eq!(c.live_count(), 1);
693    }
694    #[test]
695    pub(super) fn test_dsex2_worklist() {
696        let mut w = DSEX2Worklist::new(10);
697        w.push(5);
698        w.push(3);
699        w.push(5);
700        assert_eq!(w.len(), 2);
701        assert!(w.contains(5));
702        let first = w.pop().expect("first should be available to pop");
703        assert!(!w.contains(first));
704    }
705    #[test]
706    pub(super) fn test_dsex2_dom_tree() {
707        let mut dt = DSEX2DomTree::new(5);
708        dt.set_idom(1, 0);
709        dt.set_idom(2, 0);
710        dt.set_idom(3, 1);
711        dt.set_idom(4, 1);
712        assert!(dt.dominates(0, 3));
713        assert!(dt.dominates(1, 4));
714        assert!(!dt.dominates(2, 3));
715        assert_eq!(dt.depth_of(3), 2);
716    }
717    #[test]
718    pub(super) fn test_dsex2_liveness() {
719        let mut lv = DSEX2Liveness::new(3);
720        lv.add_def(0, 1);
721        lv.add_use(1, 1);
722        assert!(lv.var_is_def_in_block(0, 1));
723        assert!(lv.var_is_used_in_block(1, 1));
724        assert!(!lv.var_is_def_in_block(1, 1));
725    }
726    #[test]
727    pub(super) fn test_dsex2_const_folder() {
728        let mut cf = DSEX2ConstFolder::new();
729        assert_eq!(cf.add_i64(3, 4), Some(7));
730        assert_eq!(cf.div_i64(10, 0), None);
731        assert_eq!(cf.mul_i64(6, 7), Some(42));
732        assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
733        assert_eq!(cf.fold_count(), 3);
734        assert_eq!(cf.failure_count(), 1);
735    }
736    #[test]
737    pub(super) fn test_dsex2_dep_graph() {
738        let mut g = DSEX2DepGraph::new(4);
739        g.add_edge(0, 1);
740        g.add_edge(1, 2);
741        g.add_edge(2, 3);
742        assert!(!g.has_cycle());
743        assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
744        assert_eq!(g.reachable(0).len(), 4);
745        let sccs = g.scc();
746        assert_eq!(sccs.len(), 4);
747    }
748}
oxilean_codegen/opt_dse/functions.rs

oxilean_codegen/opt_dse/
functions.rs
