oxilean_codegen/opt_licm/
functions.rs

1//! Auto-generated module
2//!
3//! 🤖 Generated with [SplitRS](https://github.com/cool-japan/splitrs)
4
5use crate::lcnf::*;
6use std::collections::HashSet;
7
8use super::types::{
9    HoistCandidate, InvariantPattern, LICMAnalysisCache, LICMConfig, LICMConstantFoldingHelper,
10    LICMDepGraph, LICMDominatorTree, LICMLivenessInfo, LICMPass, LICMPassConfig, LICMPassPhase,
11    LICMPassRegistry, LICMPassStats, LICMPhase, LICMProfileData, LICMReport, LICMWorklist,
12    LicmConfigExt, LicmHoistCandidate, LoopBodyComplexity, LoopInvariantExpr, LoopNode,
13    LoopStructure, LoopVersion, LoopVersioningConfig, PreheaderBlock, RedundantLoadInfo,
14};
15
16/// Collect the set of variables *used* (read) inside `expr`.
17pub(super) fn collect_used_vars(expr: &LcnfExpr, out: &mut HashSet<LcnfVarId>) {
18    match expr {
19        LcnfExpr::Let { value, body, .. } => {
20            collect_used_in_let_value(value, out);
21            collect_used_vars(body, out);
22        }
23        LcnfExpr::Case {
24            scrutinee,
25            alts,
26            default,
27            ..
28        } => {
29            out.insert(*scrutinee);
30            for alt in alts {
31                collect_used_vars(&alt.body, out);
32            }
33            if let Some(d) = default {
34                collect_used_vars(d, out);
35            }
36        }
37        LcnfExpr::Return(arg) => collect_used_in_arg(arg, out),
38        LcnfExpr::TailCall(f, args) => {
39            collect_used_in_arg(f, out);
40            for a in args {
41                collect_used_in_arg(a, out);
42            }
43        }
44        LcnfExpr::Unreachable => {}
45    }
46}
47pub(super) fn collect_used_in_arg(arg: &LcnfArg, out: &mut HashSet<LcnfVarId>) {
48    if let LcnfArg::Var(v) = arg {
49        out.insert(*v);
50    }
51}
52pub(super) fn collect_used_in_let_value(val: &LcnfLetValue, out: &mut HashSet<LcnfVarId>) {
53    match val {
54        LcnfLetValue::App(f, args) => {
55            collect_used_in_arg(f, out);
56            for a in args {
57                collect_used_in_arg(a, out);
58            }
59        }
60        LcnfLetValue::Proj(_, _, v) => {
61            out.insert(*v);
62        }
63        LcnfLetValue::Ctor(_, _, args) => {
64            for a in args {
65                collect_used_in_arg(a, out);
66            }
67        }
68        LcnfLetValue::FVar(v) => {
69            out.insert(*v);
70        }
71        LcnfLetValue::Reset(v) => {
72            out.insert(*v);
73        }
74        LcnfLetValue::Reuse(slot, _, _, args) => {
75            out.insert(*slot);
76            for a in args {
77                collect_used_in_arg(a, out);
78            }
79        }
80        LcnfLetValue::Lit(_) | LcnfLetValue::Erased => {}
81    }
82}
83/// Collect the set of variables used as **call targets** (function position in
84/// `App` / `TailCall`) inside `expr`.  This is a stricter variant of
85/// `collect_used_vars` that only picks up variables that are *called*, not
86/// those merely passed as arguments or returned.
87pub(super) fn collect_call_targets(expr: &LcnfExpr, out: &mut HashSet<LcnfVarId>) {
88    match expr {
89        LcnfExpr::Let { value, body, .. } => {
90            if let LcnfLetValue::App(LcnfArg::Var(v), _) = value {
91                out.insert(*v);
92            }
93            collect_call_targets(body, out);
94        }
95        LcnfExpr::Case { alts, default, .. } => {
96            for alt in alts {
97                collect_call_targets(&alt.body, out);
98            }
99            if let Some(d) = default {
100                collect_call_targets(d, out);
101            }
102        }
103        LcnfExpr::TailCall(LcnfArg::Var(v), _) => {
104            out.insert(*v);
105        }
106        _ => {}
107    }
108}
109/// Collect the set of variables *defined* (written) inside `expr`.
110pub(super) fn collect_defined_vars(expr: &LcnfExpr, out: &mut HashSet<LcnfVarId>) {
111    match expr {
112        LcnfExpr::Let { id, body, .. } => {
113            out.insert(*id);
114            collect_defined_vars(body, out);
115        }
116        LcnfExpr::Case { alts, default, .. } => {
117            for alt in alts {
118                collect_defined_vars(&alt.body, out);
119            }
120            if let Some(d) = default {
121                collect_defined_vars(d, out);
122            }
123        }
124        LcnfExpr::Return(_) | LcnfExpr::Unreachable | LcnfExpr::TailCall(..) => {}
125    }
126}
127/// Collect the free variables of a `LcnfLetValue`.
128pub(super) fn free_vars_of_let_value(val: &LcnfLetValue) -> HashSet<LcnfVarId> {
129    let mut out = HashSet::new();
130    collect_used_in_let_value(val, &mut out);
131    out
132}
133/// Remove let-bindings whose `id` is in `hoisted` from `expr` in-place.
134/// The binding itself is deleted; the body continues unchanged.
135pub(super) fn remove_hoisted_bindings(expr: &mut LcnfExpr, hoisted: &HashSet<LcnfVarId>) {
136    loop {
137        match expr {
138            LcnfExpr::Let { id, body, .. } if hoisted.contains(id) => {
139                let new_expr = std::mem::replace(body.as_mut(), LcnfExpr::Unreachable);
140                *expr = new_expr;
141            }
142            LcnfExpr::Let { body, .. } => {
143                remove_hoisted_bindings(body, hoisted);
144                break;
145            }
146            LcnfExpr::Case { alts, default, .. } => {
147                for alt in alts.iter_mut() {
148                    remove_hoisted_bindings(&mut alt.body, hoisted);
149                }
150                if let Some(d) = default {
151                    remove_hoisted_bindings(d, hoisted);
152                }
153                break;
154            }
155            LcnfExpr::Return(_) | LcnfExpr::Unreachable | LcnfExpr::TailCall(..) => break,
156        }
157    }
158}
159pub(super) fn var(n: u64) -> LcnfVarId {
160    LcnfVarId(n)
161}
162pub(super) fn lit_nat(n: u64) -> LcnfLetValue {
163    LcnfLetValue::Lit(LcnfLit::Nat(n))
164}
165pub(super) fn arg_var(n: u64) -> LcnfArg {
166    LcnfArg::Var(LcnfVarId(n))
167}
168pub(super) fn arg_lit(n: u64) -> LcnfArg {
169    LcnfArg::Lit(LcnfLit::Nat(n))
170}
171pub(super) fn make_decl(name: &str, body: LcnfExpr) -> LcnfFunDecl {
172    LcnfFunDecl {
173        name: name.to_string(),
174        params: vec![],
175        ret_type: LcnfType::Nat,
176        original_name: None,
177        is_recursive: false,
178        is_lifted: false,
179        inline_cost: 0,
180        body,
181    }
182}
183#[cfg(test)]
184mod tests {
185    use super::*;
186    /// Build a simple self-recursive let that models a counted loop.
187    ///
188    /// ```text
189    /// let loop_fn = <invariant: lit 42>
190    ///               let inner = <loop body: lit 1>
191    ///               return inner
192    /// ```
193    /// The variable `loop_fn` is used in the body to simulate recursion.
194    pub(super) fn build_loop_with_invariant() -> LcnfFunDecl {
195        let inner_body = LcnfExpr::Let {
196            id: var(2),
197            name: format!("x{}", var(2).0),
198            ty: LcnfType::Nat,
199            value: LcnfLetValue::Lit(LcnfLit::Nat(1)),
200            body: Box::new(LcnfExpr::Let {
201                id: var(3),
202                name: format!("x{}", var(3).0),
203                ty: LcnfType::Nat,
204                value: LcnfLetValue::App(arg_var(0), vec![arg_var(2)]),
205                body: Box::new(LcnfExpr::Return(arg_var(3))),
206            }),
207        };
208        let body_with_inv = LcnfExpr::Let {
209            id: var(1),
210            name: format!("x{}", var(1).0),
211            ty: LcnfType::Nat,
212            value: LcnfLetValue::Lit(LcnfLit::Nat(42)),
213            body: Box::new(inner_body),
214        };
215        let body = LcnfExpr::Let {
216            id: var(0),
217            name: format!("x{}", var(0).0),
218            ty: LcnfType::Nat,
219            value: LcnfLetValue::Lit(LcnfLit::Nat(0)),
220            body: Box::new(body_with_inv),
221        };
222        make_decl("loop_test", body)
223    }
224    #[test]
225    pub(super) fn test_licm_default_config() {
226        let cfg = LICMConfig::default();
227        assert_eq!(cfg.min_savings_threshold, 0);
228        assert!(!cfg.hoist_function_calls);
229    }
230    #[test]
231    pub(super) fn test_licm_report_default() {
232        let r = LICMReport::default();
233        assert_eq!(r.loops_analyzed, 0);
234        assert_eq!(r.expressions_hoisted, 0);
235        assert_eq!(r.estimated_savings, 0);
236    }
237    #[test]
238    pub(super) fn test_licm_report_merge() {
239        let mut r1 = LICMReport {
240            loops_analyzed: 2,
241            expressions_hoisted: 3,
242            estimated_savings: 30,
243        };
244        let r2 = LICMReport {
245            loops_analyzed: 1,
246            expressions_hoisted: 2,
247            estimated_savings: 20,
248        };
249        r1.merge(&r2);
250        assert_eq!(r1.loops_analyzed, 3);
251        assert_eq!(r1.expressions_hoisted, 5);
252        assert_eq!(r1.estimated_savings, 50);
253    }
254    #[test]
255    pub(super) fn test_find_loops_empty_decl() {
256        let decl = make_decl("empty", LcnfExpr::Return(arg_lit(0)));
257        let pass = LICMPass::default();
258        let loops = pass.find_loops(&decl);
259        assert!(loops.is_empty());
260    }
261    #[test]
262    pub(super) fn test_find_loops_detects_self_recursive() {
263        let decl = build_loop_with_invariant();
264        let pass = LICMPass::default();
265        let loops = pass.find_loops(&decl);
266        assert!(!loops.is_empty());
267        assert_eq!(loops[0].header, var(0));
268    }
269    #[test]
270    pub(super) fn test_is_loop_invariant_literal() {
271        let pass = LICMPass::default();
272        let lp = LoopStructure {
273            header: var(0),
274            body_vars: vec![var(1), var(2)].into_iter().collect(),
275            exit_vars: HashSet::new(),
276            nest_depth: 0,
277        };
278        assert!(pass.is_loop_invariant(&LcnfLetValue::Lit(LcnfLit::Nat(7)), &lp));
279    }
280    #[test]
281    pub(super) fn test_is_loop_invariant_var_inside_loop() {
282        let pass = LICMPass::default();
283        let lp = LoopStructure {
284            header: var(0),
285            body_vars: vec![var(1)].into_iter().collect(),
286            exit_vars: HashSet::new(),
287            nest_depth: 0,
288        };
289        assert!(!pass.is_loop_invariant(&LcnfLetValue::FVar(var(1)), &lp));
290    }
291    #[test]
292    pub(super) fn test_is_loop_invariant_var_outside_loop() {
293        let pass = LICMPass::default();
294        let lp = LoopStructure {
295            header: var(0),
296            body_vars: vec![var(1)].into_iter().collect(),
297            exit_vars: HashSet::new(),
298            nest_depth: 0,
299        };
300        assert!(pass.is_loop_invariant(&LcnfLetValue::FVar(var(99)), &lp));
301    }
302    #[test]
303    pub(super) fn test_is_loop_invariant_call_blocked_by_config() {
304        let pass = LICMPass::default();
305        let lp = LoopStructure {
306            header: var(0),
307            body_vars: HashSet::new(),
308            exit_vars: HashSet::new(),
309            nest_depth: 0,
310        };
311        let val = LcnfLetValue::App(LcnfArg::Lit(LcnfLit::Nat(0)), vec![]);
312        assert!(!pass.is_loop_invariant(&val, &lp));
313    }
314    #[test]
315    pub(super) fn test_is_loop_invariant_call_allowed_by_config() {
316        let mut cfg = LICMConfig::default();
317        cfg.hoist_function_calls = true;
318        let pass = LICMPass::new(cfg);
319        let lp = LoopStructure {
320            header: var(0),
321            body_vars: HashSet::new(),
322            exit_vars: HashSet::new(),
323            nest_depth: 0,
324        };
325        let val = LcnfLetValue::App(LcnfArg::Lit(LcnfLit::Nat(0)), vec![]);
326        assert!(pass.is_loop_invariant(&val, &lp));
327    }
328    #[test]
329    pub(super) fn test_is_loop_invariant_recursive_call_never_hoisted() {
330        let mut cfg = LICMConfig::default();
331        cfg.hoist_function_calls = true;
332        let pass = LICMPass::new(cfg);
333        let lp = LoopStructure {
334            header: var(0),
335            body_vars: HashSet::new(),
336            exit_vars: HashSet::new(),
337            nest_depth: 0,
338        };
339        let val = LcnfLetValue::App(LcnfArg::Var(var(0)), vec![]);
340        assert!(!pass.is_loop_invariant(&val, &lp));
341    }
342    #[test]
343    pub(super) fn test_hoist_invariants_empty_loop() {
344        let mut decl = make_decl("empty", LcnfExpr::Return(arg_lit(0)));
345        let lp = LoopStructure {
346            header: var(0),
347            body_vars: HashSet::new(),
348            exit_vars: HashSet::new(),
349            nest_depth: 0,
350        };
351        let mut pass = LICMPass::default();
352        pass.hoist_invariants(&mut decl, &lp);
353        assert_eq!(pass.report().expressions_hoisted, 0);
354    }
355    #[test]
356    pub(super) fn test_run_no_loops() {
357        let mut decls = vec![make_decl("simple", LcnfExpr::Return(arg_lit(1)))];
358        let mut pass = LICMPass::default();
359        pass.run(&mut decls);
360        let r = pass.report();
361        assert_eq!(r.loops_analyzed, 0);
362        assert_eq!(r.expressions_hoisted, 0);
363    }
364    #[test]
365    pub(super) fn test_run_hoists_literal_from_loop() {
366        let mut decl = build_loop_with_invariant();
367        let pass_detect = LICMPass::default();
368        let loops = pass_detect.find_loops(&decl);
369        let mut pass = LICMPass::default();
370        for lp in &loops {
371            pass.hoist_invariants(&mut decl, lp);
372        }
373        let r = pass.report();
374        assert!(r.expressions_hoisted >= 1);
375    }
376    #[test]
377    pub(super) fn test_loop_structure_nest_depth() {
378        let decl = build_loop_with_invariant();
379        let pass = LICMPass::default();
380        let loops = pass.find_loops(&decl);
381        for lp in &loops {
382            assert_eq!(lp.nest_depth, 0);
383        }
384    }
385    #[test]
386    pub(super) fn test_hoist_candidate_savings_estimate() {
387        let candidate = HoistCandidate {
388            expr: LoopInvariantExpr {
389                var: var(5),
390                value: lit_nat(99),
391                ty: LcnfType::Nat,
392                loop_depth: 0,
393            },
394            target_loop_header: var(0),
395            savings_estimate: 10,
396        };
397        assert_eq!(candidate.savings_estimate, 10);
398    }
399    #[test]
400    pub(super) fn test_preheader_block_construction() {
401        let inv = LoopInvariantExpr {
402            var: var(5),
403            value: lit_nat(99),
404            ty: LcnfType::Nat,
405            loop_depth: 0,
406        };
407        let pb = PreheaderBlock {
408            loop_header: var(0),
409            preheader_lets: vec![inv.clone()],
410        };
411        assert_eq!(pb.preheader_lets.len(), 1);
412        assert_eq!(pb.loop_header, var(0));
413    }
414    #[test]
415    pub(super) fn test_collect_used_vars_return() {
416        let expr = LcnfExpr::Return(arg_var(7));
417        let mut used = HashSet::new();
418        collect_used_vars(&expr, &mut used);
419        assert!(used.contains(&var(7)));
420    }
421    #[test]
422    pub(super) fn test_collect_defined_vars_let() {
423        let expr = LcnfExpr::Let {
424            id: var(3),
425            name: format!("x{}", var(3).0),
426            ty: LcnfType::Nat,
427            value: lit_nat(0),
428            body: Box::new(LcnfExpr::Return(arg_lit(0))),
429        };
430        let mut defined = HashSet::new();
431        collect_defined_vars(&expr, &mut defined);
432        assert!(defined.contains(&var(3)));
433    }
434    #[test]
435    pub(super) fn test_remove_hoisted_bindings() {
436        let mut expr = LcnfExpr::Let {
437            id: var(1),
438            name: format!("x{}", var(1).0),
439            ty: LcnfType::Nat,
440            value: lit_nat(42),
441            body: Box::new(LcnfExpr::Return(arg_var(1))),
442        };
443        let mut hoisted = HashSet::new();
444        hoisted.insert(var(1));
445        remove_hoisted_bindings(&mut expr, &hoisted);
446        assert!(matches!(expr, LcnfExpr::Return(_)));
447    }
448    #[test]
449    pub(super) fn test_run_multiple_decls() {
450        let mut decls = vec![
451            make_decl("a", LcnfExpr::Return(arg_lit(0))),
452            make_decl("b", LcnfExpr::Return(arg_lit(1))),
453        ];
454        let mut pass = LICMPass::default();
455        pass.run(&mut decls);
456        assert_eq!(pass.report().loops_analyzed, 0);
457    }
458}
459/// Try to recognize the invariant pattern of a `LcnfLetValue`, given the
460/// set of variables defined inside the loop.
461#[allow(dead_code)]
462pub fn recognize_invariant_pattern(
463    val: &LcnfLetValue,
464    body_vars: &HashSet<LcnfVarId>,
465) -> Option<InvariantPattern> {
466    match val {
467        LcnfLetValue::Lit(_) => Some(InvariantPattern::Literal),
468        LcnfLetValue::Erased => Some(InvariantPattern::Erased),
469        LcnfLetValue::FVar(v) => {
470            if !body_vars.contains(v) {
471                Some(InvariantPattern::ExternalFVar)
472            } else {
473                None
474            }
475        }
476        LcnfLetValue::Proj(_, _, base) => {
477            if !body_vars.contains(base) {
478                Some(InvariantPattern::ExternalProj)
479            } else {
480                None
481            }
482        }
483        LcnfLetValue::Ctor(_, _, args) => {
484            let all_external = args.iter().all(|a| match a {
485                LcnfArg::Var(v) => !body_vars.contains(v),
486                LcnfArg::Lit(_) | LcnfArg::Erased | LcnfArg::Type(_) => true,
487            });
488            if all_external {
489                Some(InvariantPattern::InvariantCtor)
490            } else {
491                None
492            }
493        }
494        _ => None,
495    }
496}
497/// Summarise a `LICMReport` as a human-readable string.
498#[allow(dead_code)]
499pub fn format_licm_report(report: &LICMReport) -> String {
500    format!(
501        "LICM: {} loops analysed, {} expressions hoisted, {} estimated savings",
502        report.loops_analyzed, report.expressions_hoisted, report.estimated_savings
503    )
504}
505/// Returns `true` if the LICM report shows any improvement was made.
506#[allow(dead_code)]
507pub fn licm_made_changes(report: &LICMReport) -> bool {
508    report.expressions_hoisted > 0
509}
510#[cfg(test)]
511mod licm_utility_tests {
512    use super::*;
513    use crate::opt_licm::*;
514    #[test]
515    pub(super) fn test_redundant_load_info_new() {
516        let info = RedundantLoadInfo::new();
517        assert_eq!(info.redundant_count, 0);
518        assert!(info.available_loads.is_empty());
519    }
520    #[test]
521    pub(super) fn test_redundant_load_register_and_lookup() {
522        let mut info = RedundantLoadInfo::new();
523        info.register_load(LcnfVarId(1), 0, LcnfVarId(2));
524        assert_eq!(info.lookup_load(LcnfVarId(1), 0), Some(LcnfVarId(2)));
525        assert_eq!(info.lookup_load(LcnfVarId(1), 1), None);
526    }
527    #[test]
528    pub(super) fn test_redundant_load_analysis_proj() {
529        let mut info = RedundantLoadInfo::new();
530        let expr = LcnfExpr::Let {
531            id: LcnfVarId(2),
532            name: "p1".to_string(),
533            ty: LcnfType::Nat,
534            value: LcnfLetValue::Proj("0".to_string(), 0, LcnfVarId(1)),
535            body: Box::new(LcnfExpr::Let {
536                id: LcnfVarId(3),
537                name: "p2".to_string(),
538                ty: LcnfType::Nat,
539                value: LcnfLetValue::Proj("0".to_string(), 0, LcnfVarId(1)),
540                body: Box::new(LcnfExpr::Return(LcnfArg::Var(LcnfVarId(3)))),
541            }),
542        };
543        info.analyze(&expr);
544        assert_eq!(info.redundant_count, 1);
545    }
546    #[test]
547    pub(super) fn test_loop_body_complexity_empty_return() {
548        let expr = LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(0)));
549        let c = LoopBodyComplexity::compute(&expr);
550        assert_eq!(c.let_count, 0);
551        assert_eq!(c.case_count, 0);
552        assert_eq!(c.score(), 0);
553    }
554    #[test]
555    pub(super) fn test_loop_body_complexity_let_chain() {
556        let expr = LcnfExpr::Let {
557            id: LcnfVarId(1),
558            name: "a".to_string(),
559            ty: LcnfType::Nat,
560            value: LcnfLetValue::Lit(LcnfLit::Nat(1)),
561            body: Box::new(LcnfExpr::Let {
562                id: LcnfVarId(2),
563                name: "b".to_string(),
564                ty: LcnfType::Nat,
565                value: LcnfLetValue::App(
566                    LcnfArg::Var(LcnfVarId(1)),
567                    vec![LcnfArg::Var(LcnfVarId(1))],
568                ),
569                body: Box::new(LcnfExpr::Return(LcnfArg::Var(LcnfVarId(2)))),
570            }),
571        };
572        let c = LoopBodyComplexity::compute(&expr);
573        assert_eq!(c.let_count, 2);
574        assert_eq!(c.app_count, 1);
575        assert!(c.score() > 0);
576    }
577    #[test]
578    pub(super) fn test_loop_body_complexity_nested_case() {
579        let inner_case = LcnfExpr::Case {
580            scrutinee: LcnfVarId(1),
581            scrutinee_ty: LcnfType::Nat,
582            alts: vec![],
583            default: Some(Box::new(LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(0))))),
584        };
585        let outer = LcnfExpr::Case {
586            scrutinee: LcnfVarId(0),
587            scrutinee_ty: LcnfType::Nat,
588            alts: vec![crate::lcnf::LcnfAlt {
589                ctor_name: "A".to_string(),
590                ctor_tag: 0,
591                params: vec![],
592                body: inner_case,
593            }],
594            default: None,
595        };
596        let c = LoopBodyComplexity::compute(&outer);
597        assert_eq!(c.case_count, 2);
598        assert_eq!(c.max_case_depth, 2);
599    }
600    #[test]
601    pub(super) fn test_recognize_invariant_pattern_literal() {
602        let body_vars: HashSet<LcnfVarId> = HashSet::new();
603        let val = LcnfLetValue::Lit(LcnfLit::Nat(7));
604        assert!(matches!(
605            recognize_invariant_pattern(&val, &body_vars),
606            Some(InvariantPattern::Literal)
607        ));
608    }
609    #[test]
610    pub(super) fn test_recognize_invariant_pattern_erased() {
611        let body_vars: HashSet<LcnfVarId> = HashSet::new();
612        assert!(matches!(
613            recognize_invariant_pattern(&LcnfLetValue::Erased, &body_vars),
614            Some(InvariantPattern::Erased)
615        ));
616    }
617    #[test]
618    pub(super) fn test_recognize_invariant_pattern_external_fvar() {
619        let body_vars: HashSet<LcnfVarId> = vec![LcnfVarId(1)].into_iter().collect();
620        let val = LcnfLetValue::FVar(LcnfVarId(99));
621        assert!(matches!(
622            recognize_invariant_pattern(&val, &body_vars),
623            Some(InvariantPattern::ExternalFVar)
624        ));
625        let val2 = LcnfLetValue::FVar(LcnfVarId(1));
626        assert!(recognize_invariant_pattern(&val2, &body_vars).is_none());
627    }
628    #[test]
629    pub(super) fn test_recognize_invariant_pattern_external_proj() {
630        let body_vars: HashSet<LcnfVarId> = vec![LcnfVarId(1)].into_iter().collect();
631        let val = LcnfLetValue::Proj("0".to_string(), 0, LcnfVarId(50));
632        assert!(matches!(
633            recognize_invariant_pattern(&val, &body_vars),
634            Some(InvariantPattern::ExternalProj)
635        ));
636    }
637    #[test]
638    pub(super) fn test_recognize_invariant_pattern_ctor_all_external() {
639        let body_vars: HashSet<LcnfVarId> = HashSet::new();
640        let val = LcnfLetValue::Ctor(
641            "T".to_string(),
642            0,
643            vec![LcnfArg::Lit(LcnfLit::Nat(1)), LcnfArg::Lit(LcnfLit::Nat(2))],
644        );
645        assert!(matches!(
646            recognize_invariant_pattern(&val, &body_vars),
647            Some(InvariantPattern::InvariantCtor)
648        ));
649    }
650    #[test]
651    pub(super) fn test_recognize_invariant_pattern_ctor_internal_arg() {
652        let body_vars: HashSet<LcnfVarId> = vec![LcnfVarId(5)].into_iter().collect();
653        let val = LcnfLetValue::Ctor("T".to_string(), 0, vec![LcnfArg::Var(LcnfVarId(5))]);
654        assert!(recognize_invariant_pattern(&val, &body_vars).is_none());
655    }
656    #[test]
657    pub(super) fn test_format_licm_report() {
658        let r = LICMReport {
659            loops_analyzed: 3,
660            expressions_hoisted: 5,
661            estimated_savings: 50,
662        };
663        let s = format_licm_report(&r);
664        assert!(s.contains("3 loops"));
665        assert!(s.contains("5 expressions"));
666        assert!(s.contains("50 estimated"));
667    }
668    #[test]
669    pub(super) fn test_licm_made_changes_true() {
670        let r = LICMReport {
671            loops_analyzed: 1,
672            expressions_hoisted: 2,
673            estimated_savings: 20,
674        };
675        assert!(licm_made_changes(&r));
676    }
677    #[test]
678    pub(super) fn test_licm_made_changes_false() {
679        let r = LICMReport::default();
680        assert!(!licm_made_changes(&r));
681    }
682    #[test]
683    pub(super) fn test_preheader_block_empty() {
684        let pb = PreheaderBlock {
685            loop_header: LcnfVarId(0),
686            preheader_lets: vec![],
687        };
688        let inner = LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(42)));
689        let result = materialize_preheader(&pb, inner.clone());
690        assert_eq!(result, inner);
691    }
692    #[test]
693    pub(super) fn test_loop_nest_info_multiple_depths() {
694        let loops = vec![
695            LoopStructure {
696                header: LcnfVarId(0),
697                body_vars: HashSet::new(),
698                exit_vars: HashSet::new(),
699                nest_depth: 0,
700            },
701            LoopStructure {
702                header: LcnfVarId(1),
703                body_vars: vec![LcnfVarId(10)].into_iter().collect(),
704                exit_vars: HashSet::new(),
705                nest_depth: 1,
706            },
707            LoopStructure {
708                header: LcnfVarId(2),
709                body_vars: vec![LcnfVarId(20), LcnfVarId(21)].into_iter().collect(),
710                exit_vars: HashSet::new(),
711                nest_depth: 2,
712            },
713        ];
714        let info = LoopNestInfo::from_loops(loops);
715        assert_eq!(info.max_depth, 2);
716        assert_eq!(info.total_body_vars, 3);
717    }
718}
719#[cfg(test)]
720mod licm_phase_tests {
721    use super::*;
722    use crate::opt_licm::*;
723    #[test]
724    pub(super) fn test_loop_version_structure() {
725        let v = LoopVersion {
726            cond_var: LcnfVarId(10),
727            fast_path_header: LcnfVarId(20),
728            slow_path_header: LcnfVarId(30),
729        };
730        assert_eq!(v.cond_var, LcnfVarId(10));
731        assert_eq!(v.fast_path_header, LcnfVarId(20));
732        assert_eq!(v.slow_path_header, LcnfVarId(30));
733    }
734    #[test]
735    pub(super) fn test_loop_versioning_config_conservative() {
736        let cfg = LoopVersioningConfig::conservative();
737        assert_eq!(cfg.max_versions, 2);
738        assert!((cfg.min_speedup_ratio - 1.5).abs() < 0.001);
739    }
740    #[test]
741    pub(super) fn test_licm_profile_data_new() {
742        let pd = LICMProfileData::new();
743        assert!(pd.loop_counts.is_empty());
744        assert!(pd.binding_counts.is_empty());
745    }
746    #[test]
747    pub(super) fn test_licm_profile_data_record_and_query() {
748        let mut pd = LICMProfileData::new();
749        pd.record_loop(LcnfVarId(0), 1000);
750        assert_eq!(pd.loop_count(LcnfVarId(0)), 1000);
751        assert_eq!(pd.loop_count(LcnfVarId(99)), 1);
752    }
753    #[test]
754    pub(super) fn test_licm_profile_data_dynamic_savings() {
755        let mut pd = LICMProfileData::new();
756        pd.record_loop(LcnfVarId(0), 50);
757        let candidate = HoistCandidate {
758            expr: LoopInvariantExpr {
759                var: LcnfVarId(1),
760                value: LcnfLetValue::Erased,
761                ty: LcnfType::Nat,
762                loop_depth: 0,
763            },
764            target_loop_header: LcnfVarId(0),
765            savings_estimate: 10,
766        };
767        assert_eq!(pd.dynamic_savings(&candidate), 500);
768    }
769    #[test]
770    pub(super) fn test_licm_phase_display() {
771        assert_eq!(LICMPhase::LICMBeforeCSE.to_string(), "LICM-before-CSE");
772        assert_eq!(LICMPhase::LICMAfterCSE.to_string(), "LICM-after-CSE");
773        assert_eq!(LICMPhase::LICMIterative.to_string(), "LICM-iterative");
774        assert_eq!(LICMPhase::LICMOnce.to_string(), "LICM-once");
775    }
776    #[test]
777    pub(super) fn test_licm_phase_equality() {
778        assert_eq!(LICMPhase::LICMOnce, LICMPhase::LICMOnce);
779        assert_ne!(LICMPhase::LICMOnce, LICMPhase::LICMIterative);
780    }
781    #[test]
782    pub(super) fn test_loop_versioning_config_default() {
783        let cfg = LoopVersioningConfig::default();
784        assert_eq!(cfg.max_versions, 0);
785    }
786    #[test]
787    pub(super) fn test_licm_profile_data_record_binding() {
788        let mut pd = LICMProfileData::new();
789        pd.record_binding(LcnfVarId(5), 200);
790        assert_eq!(
791            *pd.binding_counts
792                .get(&LcnfVarId(5))
793                .expect("value should be present in map"),
794            200
795        );
796    }
797    #[test]
798    pub(super) fn test_redundant_load_multiple_fields() {
799        let mut info = RedundantLoadInfo::new();
800        info.register_load(LcnfVarId(1), 0, LcnfVarId(10));
801        info.register_load(LcnfVarId(1), 1, LcnfVarId(11));
802        info.register_load(LcnfVarId(2), 0, LcnfVarId(12));
803        assert_eq!(info.lookup_load(LcnfVarId(1), 0), Some(LcnfVarId(10)));
804        assert_eq!(info.lookup_load(LcnfVarId(1), 1), Some(LcnfVarId(11)));
805        assert_eq!(info.lookup_load(LcnfVarId(2), 0), Some(LcnfVarId(12)));
806        assert_eq!(info.lookup_load(LcnfVarId(2), 1), None);
807    }
808    #[test]
809    pub(super) fn test_loop_body_complexity_case_with_apps() {
810        let expr = LcnfExpr::Case {
811            scrutinee: LcnfVarId(0),
812            scrutinee_ty: LcnfType::Nat,
813            alts: vec![crate::lcnf::LcnfAlt {
814                ctor_name: "A".to_string(),
815                ctor_tag: 0,
816                params: vec![],
817                body: LcnfExpr::Let {
818                    id: LcnfVarId(1),
819                    name: "r".to_string(),
820                    ty: LcnfType::Nat,
821                    value: LcnfLetValue::App(LcnfArg::Lit(LcnfLit::Nat(0)), vec![]),
822                    body: Box::new(LcnfExpr::Return(LcnfArg::Var(LcnfVarId(1)))),
823                },
824            }],
825            default: None,
826        };
827        let c = LoopBodyComplexity::compute(&expr);
828        assert_eq!(c.case_count, 1);
829        assert_eq!(c.let_count, 1);
830        assert_eq!(c.app_count, 1);
831    }
832    #[test]
833    pub(super) fn test_topo_sort_two_independent() {
834        let c1 = HoistCandidate {
835            expr: LoopInvariantExpr {
836                var: LcnfVarId(1),
837                value: LcnfLetValue::Lit(LcnfLit::Nat(1)),
838                ty: LcnfType::Nat,
839                loop_depth: 0,
840            },
841            target_loop_header: LcnfVarId(0),
842            savings_estimate: 5,
843        };
844        let c2 = HoistCandidate {
845            expr: LoopInvariantExpr {
846                var: LcnfVarId(2),
847                value: LcnfLetValue::Lit(LcnfLit::Nat(2)),
848                ty: LcnfType::Nat,
849                loop_depth: 0,
850            },
851            target_loop_header: LcnfVarId(0),
852            savings_estimate: 5,
853        };
854        let sorted = topo_sort_candidates(&[c1, c2]);
855        assert_eq!(sorted.len(), 2);
856        let vars: Vec<LcnfVarId> = sorted.iter().map(|c| c.expr.var).collect();
857        assert!(vars.contains(&LcnfVarId(1)));
858        assert!(vars.contains(&LcnfVarId(2)));
859    }
860    #[test]
861    pub(super) fn test_topo_sort_dependent_pair() {
862        let c1 = HoistCandidate {
863            expr: LoopInvariantExpr {
864                var: LcnfVarId(1),
865                value: LcnfLetValue::Lit(LcnfLit::Nat(42)),
866                ty: LcnfType::Nat,
867                loop_depth: 0,
868            },
869            target_loop_header: LcnfVarId(0),
870            savings_estimate: 5,
871        };
872        let c2 = HoistCandidate {
873            expr: LoopInvariantExpr {
874                var: LcnfVarId(2),
875                value: LcnfLetValue::FVar(LcnfVarId(1)),
876                ty: LcnfType::Nat,
877                loop_depth: 0,
878            },
879            target_loop_header: LcnfVarId(0),
880            savings_estimate: 5,
881        };
882        let sorted = topo_sort_candidates(&[c1, c2]);
883        assert_eq!(sorted.len(), 2);
884        let pos1 = sorted
885            .iter()
886            .position(|c| c.expr.var == LcnfVarId(1))
887            .expect("operation should succeed");
888        let pos2 = sorted
889            .iter()
890            .position(|c| c.expr.var == LcnfVarId(2))
891            .expect("operation should succeed");
892        assert!(pos1 < pos2, "producer must precede consumer");
893    }
894    #[test]
895    pub(super) fn test_licm_pass_v2_with_heuristics() {
896        let mut pass = LICMPassV2::new();
897        pass.heuristics.max_hoist_cost = 0;
898        let mut decl = make_decl(
899            "heuristic_test",
900            LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(1))),
901        );
902        pass.run(std::slice::from_mut(&mut decl));
903        assert_eq!(pass.report().loops_analyzed, 0);
904    }
905    #[test]
906    pub(super) fn test_collect_used_vars_tailcall() {
907        let expr = LcnfExpr::TailCall(
908            LcnfArg::Var(LcnfVarId(1)),
909            vec![LcnfArg::Var(LcnfVarId(2)), LcnfArg::Lit(LcnfLit::Nat(0))],
910        );
911        let mut used = HashSet::new();
912        collect_used_vars(&expr, &mut used);
913        assert!(used.contains(&LcnfVarId(1)));
914        assert!(used.contains(&LcnfVarId(2)));
915    }
916    #[test]
917    pub(super) fn test_collect_defined_vars_case() {
918        let expr = LcnfExpr::Case {
919            scrutinee: LcnfVarId(0),
920            scrutinee_ty: LcnfType::Nat,
921            alts: vec![crate::lcnf::LcnfAlt {
922                ctor_name: "A".to_string(),
923                ctor_tag: 0,
924                params: vec![],
925                body: LcnfExpr::Let {
926                    id: LcnfVarId(10),
927                    name: "x".to_string(),
928                    ty: LcnfType::Nat,
929                    value: LcnfLetValue::Lit(LcnfLit::Nat(0)),
930                    body: Box::new(LcnfExpr::Return(LcnfArg::Var(LcnfVarId(10)))),
931                },
932            }],
933            default: None,
934        };
935        let mut defined = HashSet::new();
936        collect_defined_vars(&expr, &mut defined);
937        assert!(defined.contains(&LcnfVarId(10)));
938    }
939}
940/// LICM pass version
941#[allow(dead_code)]
942pub const LICM_PASS_VERSION: &str = "1.0.0";
943/// LICM loop invariant check helper
944#[allow(dead_code)]
945pub fn licm_is_loop_invariant_const(value: i64) -> bool {
946    let _ = value;
947    true
948}
949/// LICM hoist decision helper
950#[allow(dead_code)]
951pub fn licm_should_hoist(candidate: &LicmHoistCandidate, config: &LicmConfigExt) -> bool {
952    if !config.enable_hoist {
953        return false;
954    }
955    if !candidate.is_side_effect_free && !config.hoist_stores {
956        return false;
957    }
958    if candidate.cost > config.max_hoist_cost {
959        return false;
960    }
961    true
962}
963/// LICM trip count estimation
964#[allow(dead_code)]
965pub fn licm_estimate_trip_count(loop_node: &LoopNode) -> Option<u64> {
966    loop_node.trip_count
967}
968/// LICM benefit estimator
969#[allow(dead_code)]
970pub fn licm_hoist_benefit(candidate: &LicmHoistCandidate, trip_count: u64) -> i64 {
971    let savings_per_iter = candidate.cost as i64;
972    let total_savings = savings_per_iter * trip_count as i64;
973    total_savings - savings_per_iter
974}
975/// LICM version info
976#[allow(dead_code)]
977pub const LICM_VERSION_INFO: &str = "licm-pass-1.0.0";
978/// LICM default max hoist cost
979#[allow(dead_code)]
980pub const LICM_DEFAULT_MAX_HOIST_COST: i32 = 100;
981/// LICM min profitable trip count
982#[allow(dead_code)]
983pub const LICM_MIN_TRIP_COUNT: u64 = 2;
984/// LICM loop depth-1 invariant check
985#[allow(dead_code)]
986pub fn licm_is_trivially_invariant(var: u32, loop_defs: &std::collections::HashSet<u32>) -> bool {
987    !loop_defs.contains(&var)
988}
989/// LICM safe to hoist check
990#[allow(dead_code)]
991pub fn licm_is_safe_to_hoist(inst_id: u32, has_side_effects: bool, aliases_loop_mem: bool) -> bool {
992    let _ = inst_id;
993    !has_side_effects && !aliases_loop_mem
994}
995/// LICM loop-independent variable detection
996#[allow(dead_code)]
997pub fn licm_all_operands_invariant(
998    operands: &[u32],
999    invariants: &std::collections::HashSet<u32>,
1000) -> bool {
1001    operands.iter().all(|op| invariants.contains(op))
1002}
1003/// LICM loop exit block collector
1004#[allow(dead_code)]
1005pub fn licm_collect_loop_exits(
1006    loop_node: &LoopNode,
1007    cfg_succs: &std::collections::HashMap<u32, Vec<u32>>,
1008) -> Vec<u32> {
1009    let body: std::collections::HashSet<u32> = loop_node.body_blocks.iter().cloned().collect();
1010    let mut exits = Vec::new();
1011    for &blk in &loop_node.body_blocks {
1012        if let Some(succs) = cfg_succs.get(&blk) {
1013            for &s in succs {
1014                if !body.contains(&s) {
1015                    exits.push(s);
1016                }
1017            }
1018        }
1019    }
1020    exits
1021}
1022/// LICM dominated-by check (simplified)
1023#[allow(dead_code)]
1024pub fn licm_dominates(
1025    _dom: u32,
1026    _target: u32,
1027    _dom_tree: &std::collections::HashMap<u32, u32>,
1028) -> bool {
1029    true
1030}
1031/// LICM version
1032#[allow(dead_code)]
1033pub const LICM_BACKEND_VERSION: &str = "1.0.0";
1034#[cfg(test)]
1035mod LICM_infra_tests {
1036    use super::*;
1037    #[test]
1038    pub(super) fn test_pass_config() {
1039        let config = LICMPassConfig::new("test_pass", LICMPassPhase::Transformation);
1040        assert!(config.enabled);
1041        assert!(config.phase.is_modifying());
1042        assert_eq!(config.phase.name(), "transformation");
1043    }
1044    #[test]
1045    pub(super) fn test_pass_stats() {
1046        let mut stats = LICMPassStats::new();
1047        stats.record_run(10, 100, 3);
1048        stats.record_run(20, 200, 5);
1049        assert_eq!(stats.total_runs, 2);
1050        assert!((stats.average_changes_per_run() - 15.0).abs() < 0.01);
1051        assert!((stats.success_rate() - 1.0).abs() < 0.01);
1052        let s = stats.format_summary();
1053        assert!(s.contains("Runs: 2/2"));
1054    }
1055    #[test]
1056    pub(super) fn test_pass_registry() {
1057        let mut reg = LICMPassRegistry::new();
1058        reg.register(LICMPassConfig::new("pass_a", LICMPassPhase::Analysis));
1059        reg.register(LICMPassConfig::new("pass_b", LICMPassPhase::Transformation).disabled());
1060        assert_eq!(reg.total_passes(), 2);
1061        assert_eq!(reg.enabled_count(), 1);
1062        reg.update_stats("pass_a", 5, 50, 2);
1063        let stats = reg.get_stats("pass_a").expect("stats should exist");
1064        assert_eq!(stats.total_changes, 5);
1065    }
1066    #[test]
1067    pub(super) fn test_analysis_cache() {
1068        let mut cache = LICMAnalysisCache::new(10);
1069        cache.insert("key1".to_string(), vec![1, 2, 3]);
1070        assert!(cache.get("key1").is_some());
1071        assert!(cache.get("key2").is_none());
1072        assert!((cache.hit_rate() - 0.5).abs() < 0.01);
1073        cache.invalidate("key1");
1074        assert!(!cache.entries["key1"].valid);
1075        assert_eq!(cache.size(), 1);
1076    }
1077    #[test]
1078    pub(super) fn test_worklist() {
1079        let mut wl = LICMWorklist::new();
1080        assert!(wl.push(1));
1081        assert!(wl.push(2));
1082        assert!(!wl.push(1));
1083        assert_eq!(wl.len(), 2);
1084        assert_eq!(wl.pop(), Some(1));
1085        assert!(!wl.contains(1));
1086        assert!(wl.contains(2));
1087    }
1088    #[test]
1089    pub(super) fn test_dominator_tree() {
1090        let mut dt = LICMDominatorTree::new(5);
1091        dt.set_idom(1, 0);
1092        dt.set_idom(2, 0);
1093        dt.set_idom(3, 1);
1094        assert!(dt.dominates(0, 3));
1095        assert!(dt.dominates(1, 3));
1096        assert!(!dt.dominates(2, 3));
1097        assert!(dt.dominates(3, 3));
1098    }
1099    #[test]
1100    pub(super) fn test_liveness() {
1101        let mut liveness = LICMLivenessInfo::new(3);
1102        liveness.add_def(0, 1);
1103        liveness.add_use(1, 1);
1104        assert!(liveness.defs[0].contains(&1));
1105        assert!(liveness.uses[1].contains(&1));
1106    }
1107    #[test]
1108    pub(super) fn test_constant_folding() {
1109        assert_eq!(LICMConstantFoldingHelper::fold_add_i64(3, 4), Some(7));
1110        assert_eq!(LICMConstantFoldingHelper::fold_div_i64(10, 0), None);
1111        assert_eq!(LICMConstantFoldingHelper::fold_div_i64(10, 2), Some(5));
1112        assert_eq!(
1113            LICMConstantFoldingHelper::fold_bitand_i64(0b1100, 0b1010),
1114            0b1000
1115        );
1116        assert_eq!(LICMConstantFoldingHelper::fold_bitnot_i64(0), -1);
1117    }
1118    #[test]
1119    pub(super) fn test_dep_graph() {
1120        let mut g = LICMDepGraph::new();
1121        g.add_dep(1, 2);
1122        g.add_dep(2, 3);
1123        g.add_dep(1, 3);
1124        assert_eq!(g.dependencies_of(2), vec![1]);
1125        let topo = g.topological_sort();
1126        assert_eq!(topo.len(), 3);
1127        assert!(!g.has_cycle());
1128        let pos: std::collections::HashMap<u32, usize> =
1129            topo.iter().enumerate().map(|(i, &n)| (n, i)).collect();
1130        assert!(pos[&1] < pos[&2]);
1131        assert!(pos[&1] < pos[&3]);
1132        assert!(pos[&2] < pos[&3]);
1133    }
1134}
1135/// LICM code version
1136#[allow(dead_code)]
1137pub const LICM_CODE_VERSION: &str = "1.0.0";
oxilean_codegen/opt_licm/functions.rs

oxilean_codegen/opt_licm/
functions.rs
