oxilean_codegen/opt_licm/
types.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::functions::*;
9use std::collections::{HashMap, VecDeque};
10
11/// Loop level (nesting depth)
12#[allow(dead_code)]
13#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
14pub struct LoopLevelId(pub u32);
15/// Recognizes structural patterns in let-values that are always loop-invariant.
16#[allow(dead_code)]
17#[derive(Debug, Clone)]
18pub enum InvariantPattern {
19    /// A literal constant.
20    Literal,
21    /// An erased value (always invariant).
22    Erased,
23    /// A free-variable reference that is not defined inside the loop.
24    ExternalFVar,
25    /// A projection of an external variable.
26    ExternalProj,
27    /// A constructor whose all args are invariant.
28    InvariantCtor,
29}
30/// The main Loop Invariant Code Motion pass.
31pub struct LICMPass {
32    pub(super) config: LICMConfig,
33    pub(super) report: LICMReport,
34}
35impl LICMPass {
36    /// Create a new LICM pass with the given configuration.
37    pub fn new(config: LICMConfig) -> Self {
38        LICMPass {
39            config,
40            report: LICMReport::default(),
41        }
42    }
43    /// Run the LICM pass over all function declarations, mutating them
44    /// in-place to hoist loop-invariant bindings.
45    pub fn run(&mut self, decls: &mut [LcnfFunDecl]) {
46        for decl in decls.iter_mut() {
47            let loops = self.find_loops(decl);
48            self.report.loops_analyzed += loops.len();
49            for lp in &loops {
50                self.hoist_invariants(decl, lp);
51            }
52        }
53    }
54    /// Identify all loops in a function declaration by scanning for
55    /// recursive `Let` bindings (self-referencing variables).
56    pub fn find_loops(&self, decl: &LcnfFunDecl) -> Vec<LoopStructure> {
57        let mut loops = Vec::new();
58        let mut depth = 0u32;
59        Self::find_loops_in_expr(&decl.body, &mut depth, &mut loops);
60        loops
61    }
62    /// Check whether a `LcnfLetValue` is loop-invariant with respect to
63    /// the given loop structure (i.e., none of its free variables are
64    /// defined inside the loop body).
65    pub fn is_loop_invariant(&self, value: &LcnfLetValue, lp: &LoopStructure) -> bool {
66        let free = free_vars_of_let_value(value);
67        if let LcnfLetValue::App(LcnfArg::Var(f), _) = value {
68            if f == &lp.header {
69                return false;
70            }
71        }
72        if !self.config.hoist_function_calls {
73            if let LcnfLetValue::App(..) = value {
74                return false;
75            }
76        }
77        free.iter().all(|v| !lp.body_vars.contains(v))
78    }
79    /// Hoist all loop-invariant bindings from `lp` into a preheader and
80    /// update `decl.body` accordingly.
81    pub fn hoist_invariants(&mut self, decl: &mut LcnfFunDecl, lp: &LoopStructure) {
82        let mut candidates: Vec<HoistCandidate> = Vec::new();
83        Self::collect_invariant_candidates(&decl.body, lp, &self.config, &mut candidates);
84        let threshold = self.config.min_savings_threshold;
85        candidates.retain(|c| c.savings_estimate >= threshold);
86        if candidates.is_empty() {
87            return;
88        }
89        let hoisted_vars: HashSet<LcnfVarId> = candidates.iter().map(|c| c.expr.var).collect();
90        self.report.expressions_hoisted += hoisted_vars.len();
91        self.report.estimated_savings += candidates
92            .iter()
93            .map(|c| c.savings_estimate as u64)
94            .sum::<u64>();
95        let mut new_body = decl.body.clone();
96        remove_hoisted_bindings(&mut new_body, &hoisted_vars);
97        for c in candidates.iter().rev() {
98            new_body = LcnfExpr::Let {
99                id: c.expr.var,
100                name: format!("{}", c.expr.var),
101                ty: c.expr.ty.clone(),
102                value: c.expr.value.clone(),
103                body: Box::new(new_body),
104            };
105        }
106        decl.body = new_body;
107    }
108    /// Return a copy of the accumulated statistics report.
109    pub fn report(&self) -> LICMReport {
110        self.report.clone()
111    }
112    /// Recursively walk `expr` looking for recursive `Let` bindings.
113    pub(super) fn find_loops_in_expr(
114        expr: &LcnfExpr,
115        depth: &mut u32,
116        loops: &mut Vec<LoopStructure>,
117    ) {
118        match expr {
119            LcnfExpr::Let { id, body, .. } => {
120                let mut call_targets = HashSet::new();
121                collect_call_targets(body, &mut call_targets);
122                if call_targets.contains(id) {
123                    let mut body_vars = HashSet::new();
124                    collect_defined_vars(body, &mut body_vars);
125                    let exit_vars = {
126                        let mut ev = HashSet::new();
127                        collect_used_vars(body, &mut ev);
128                        ev.retain(|v| !body_vars.contains(v));
129                        ev
130                    };
131                    loops.push(LoopStructure {
132                        header: *id,
133                        body_vars,
134                        exit_vars,
135                        nest_depth: *depth,
136                    });
137                    *depth += 1;
138                    Self::find_loops_in_expr(body, depth, loops);
139                    *depth -= 1;
140                } else {
141                    Self::find_loops_in_expr(body, depth, loops);
142                }
143            }
144            LcnfExpr::Case { alts, default, .. } => {
145                for alt in alts {
146                    Self::find_loops_in_expr(&alt.body, depth, loops);
147                }
148                if let Some(d) = default {
149                    Self::find_loops_in_expr(d, depth, loops);
150                }
151            }
152            LcnfExpr::Return(_) | LcnfExpr::Unreachable | LcnfExpr::TailCall(..) => {}
153        }
154    }
155    /// Collect `HoistCandidate`s from inside the loop body.
156    pub(super) fn collect_invariant_candidates(
157        expr: &LcnfExpr,
158        lp: &LoopStructure,
159        config: &LICMConfig,
160        out: &mut Vec<HoistCandidate>,
161    ) {
162        match expr {
163            LcnfExpr::Let {
164                id,
165                name: _,
166                ty,
167                value,
168                body,
169            } => {
170                if lp.body_vars.contains(id) {
171                    let free = free_vars_of_let_value(value);
172                    let all_outside = free.iter().all(|v| !lp.body_vars.contains(v));
173                    let is_call = matches!(value, LcnfLetValue::App(..));
174                    let ok_call = !is_call || config.hoist_function_calls;
175                    let is_self_call = matches!(
176                        value, LcnfLetValue::App(LcnfArg::Var(f), ..) if f == & lp.header
177                    );
178                    if all_outside && ok_call && !is_self_call {
179                        out.push(HoistCandidate {
180                            expr: LoopInvariantExpr {
181                                var: *id,
182                                value: value.clone(),
183                                ty: ty.clone(),
184                                loop_depth: lp.nest_depth,
185                            },
186                            target_loop_header: lp.header,
187                            savings_estimate: 10,
188                        });
189                    }
190                }
191                Self::collect_invariant_candidates(body, lp, config, out);
192            }
193            LcnfExpr::Case { alts, default, .. } => {
194                for alt in alts {
195                    Self::collect_invariant_candidates(&alt.body, lp, config, out);
196                }
197                if let Some(d) = default {
198                    Self::collect_invariant_candidates(d, lp, config, out);
199                }
200            }
201            LcnfExpr::Return(_) | LcnfExpr::Unreachable | LcnfExpr::TailCall(..) => {}
202        }
203    }
204}
205/// LICM pass config (extended)
206#[allow(dead_code)]
207#[derive(Debug, Clone)]
208pub struct LicmConfigExt {
209    pub enable_hoist: bool,
210    pub enable_sink: bool,
211    pub enable_speculative_hoist: bool,
212    pub max_hoist_cost: i32,
213    pub min_trip_count: u64,
214    pub hoist_stores: bool,
215    pub hoist_calls: bool,
216    pub max_loop_depth: u32,
217}
218/// LICM profiler
219#[allow(dead_code)]
220#[derive(Debug, Default)]
221pub struct LicmExtProfiler {
222    pub timings: Vec<(String, u64)>,
223}
224#[allow(dead_code)]
225impl LicmExtProfiler {
226    pub fn new() -> Self {
227        Self::default()
228    }
229    pub fn record(&mut self, pass: &str, us: u64) {
230        self.timings.push((pass.to_string(), us));
231    }
232    pub fn total_us(&self) -> u64 {
233        self.timings.iter().map(|(_, t)| *t).sum()
234    }
235}
236/// LICM loop analysis result
237#[allow(dead_code)]
238#[derive(Debug, Default)]
239pub struct LicmLoopAnalysis {
240    pub loop_tree: LoopTree,
241    pub preheaders: LicmPreheaderMap,
242    pub invariant_vars: std::collections::HashMap<u32, LoopLevelId>,
243}
244#[allow(dead_code)]
245impl LicmLoopAnalysis {
246    pub fn new() -> Self {
247        Self::default()
248    }
249    pub fn add_invariant(&mut self, var: u32, loop_id: LoopLevelId) {
250        self.invariant_vars.insert(var, loop_id);
251    }
252    pub fn is_invariant(&self, var: u32) -> bool {
253        self.invariant_vars.contains_key(&var)
254    }
255    pub fn invariant_count(&self) -> usize {
256        self.invariant_vars.len()
257    }
258}
259/// LICM preheader builder
260#[allow(dead_code)]
261#[derive(Debug, Default)]
262pub struct LicmPreheaderBuilder {
263    pub created: Vec<LoopPreheader>,
264    pub next_block_id: u32,
265}
266#[allow(dead_code)]
267impl LicmPreheaderBuilder {
268    pub fn new(start_id: u32) -> Self {
269        Self {
270            created: Vec::new(),
271            next_block_id: start_id,
272        }
273    }
274    pub fn create_preheader(&mut self, loop_id: LoopLevelId) -> LoopPreheader {
275        let ph = LoopPreheader {
276            loop_id,
277            preheader_block: self.next_block_id,
278            inserted_insts: Vec::new(),
279        };
280        self.next_block_id += 1;
281        self.created.push(ph.clone());
282        ph
283    }
284    pub fn count(&self) -> usize {
285        self.created.len()
286    }
287}
288/// LICM id generator
289#[allow(dead_code)]
290#[derive(Debug, Default)]
291pub struct LicmExtIdGen {
292    pub(super) counter: u32,
293}
294#[allow(dead_code)]
295impl LicmExtIdGen {
296    pub fn new() -> Self {
297        Self::default()
298    }
299    pub fn next(&mut self) -> u32 {
300        let id = self.counter;
301        self.counter += 1;
302        id
303    }
304}
305/// LICM scheduler (ordering of hoisted instructions)
306#[allow(dead_code)]
307#[derive(Debug, Default)]
308pub struct LicmScheduler {
309    pub order: Vec<u32>,
310    pub scheduled: std::collections::HashSet<u32>,
311}
312#[allow(dead_code)]
313impl LicmScheduler {
314    pub fn new() -> Self {
315        Self::default()
316    }
317    pub fn schedule(&mut self, inst: u32) {
318        if self.scheduled.insert(inst) {
319            self.order.push(inst);
320        }
321    }
322    pub fn is_scheduled(&self, inst: u32) -> bool {
323        self.scheduled.contains(&inst)
324    }
325    pub fn scheduled_count(&self) -> usize {
326        self.order.len()
327    }
328}
329/// LICM hoistable expression
330#[allow(dead_code)]
331#[derive(Debug, Clone)]
332pub struct LicmHoistCandidate {
333    pub inst_id: u32,
334    pub loop_id: LoopLevelId,
335    pub cost: i32,
336    pub is_side_effect_free: bool,
337    pub operands: Vec<u32>,
338    pub def_uses: usize,
339}
340/// Measures the "complexity" of a loop body to guide hoisting aggressiveness.
341#[allow(dead_code)]
342#[derive(Debug, Clone, Default)]
343pub struct LoopBodyComplexity {
344    /// Total number of let-bindings in the body.
345    pub let_count: usize,
346    /// Number of function application let-values.
347    pub app_count: usize,
348    /// Number of constructor let-values.
349    pub ctor_count: usize,
350    /// Number of case expressions in the body.
351    pub case_count: usize,
352    /// Maximum depth of nested case expressions.
353    pub max_case_depth: usize,
354}
355impl LoopBodyComplexity {
356    /// Compute the complexity of an expression.
357    #[allow(dead_code)]
358    pub fn compute(expr: &LcnfExpr) -> Self {
359        let mut c = LoopBodyComplexity::default();
360        c.visit(expr, 0);
361        c
362    }
363    pub(super) fn visit(&mut self, expr: &LcnfExpr, case_depth: usize) {
364        match expr {
365            LcnfExpr::Let { value, body, .. } => {
366                self.let_count += 1;
367                match value {
368                    LcnfLetValue::App(..) => self.app_count += 1,
369                    LcnfLetValue::Ctor(..) => self.ctor_count += 1,
370                    _ => {}
371                }
372                self.visit(body, case_depth);
373            }
374            LcnfExpr::Case { alts, default, .. } => {
375                self.case_count += 1;
376                if case_depth + 1 > self.max_case_depth {
377                    self.max_case_depth = case_depth + 1;
378                }
379                for alt in alts {
380                    self.visit(&alt.body, case_depth + 1);
381                }
382                if let Some(d) = default {
383                    self.visit(d, case_depth + 1);
384                }
385            }
386            LcnfExpr::Return(_) | LcnfExpr::Unreachable | LcnfExpr::TailCall(..) => {}
387        }
388    }
389    /// Return a scalar complexity score.
390    #[allow(dead_code)]
391    pub fn score(&self) -> usize {
392        self.let_count + self.app_count * 2 + self.ctor_count + self.case_count * 3
393    }
394}
395/// LICM pass statistics (extended)
396#[allow(dead_code)]
397#[derive(Debug, Default, Clone)]
398pub struct LicmStatsExt {
399    pub loops_analyzed: usize,
400    pub candidates_found: usize,
401    pub hoisted: usize,
402    pub sunk: usize,
403    pub rejected: usize,
404    pub speculative_hoists: usize,
405}
406/// LICM candidate registry
407#[allow(dead_code)]
408#[derive(Debug, Default)]
409pub struct LicmCandidateRegistry {
410    pub hoists: Vec<LicmHoistCandidate>,
411    pub sinks: Vec<LicmSinkCandidate>,
412}
413#[allow(dead_code)]
414impl LicmCandidateRegistry {
415    pub fn new() -> Self {
416        Self::default()
417    }
418    pub fn add_hoist(&mut self, c: LicmHoistCandidate) {
419        self.hoists.push(c);
420    }
421    pub fn add_sink(&mut self, c: LicmSinkCandidate) {
422        self.sinks.push(c);
423    }
424    pub fn hoist_count(&self) -> usize {
425        self.hoists.len()
426    }
427    pub fn sink_count(&self) -> usize {
428        self.sinks.len()
429    }
430    pub fn pure_hoists(&self) -> Vec<&LicmHoistCandidate> {
431        self.hoists
432            .iter()
433            .filter(|c| c.is_side_effect_free)
434            .collect()
435    }
436}
437/// LICM pass builder
438#[allow(dead_code)]
439#[derive(Debug, Default)]
440pub struct LicmPassBuilder {
441    pub config: LicmConfigExt,
442    pub loop_tree: LoopTree,
443    pub candidates: LicmCandidateRegistry,
444    pub stats: LicmStatsExt,
445    pub diags: LicmDiagSink,
446}
447#[allow(dead_code)]
448impl LicmPassBuilder {
449    pub fn new() -> Self {
450        Self::default()
451    }
452    pub fn with_config(mut self, cfg: LicmConfigExt) -> Self {
453        self.config = cfg;
454        self
455    }
456    pub fn report(&self) -> String {
457        format!("{}", self.stats)
458    }
459}
460#[allow(dead_code)]
461#[derive(Debug, Clone)]
462pub struct LICMCacheEntry {
463    pub key: String,
464    pub data: Vec<u8>,
465    pub timestamp: u64,
466    pub valid: bool,
467}
468#[allow(dead_code)]
469#[derive(Debug, Default)]
470pub struct LicmDiagSink {
471    pub diags: Vec<(LicmDiagLevel, String)>,
472}
473#[allow(dead_code)]
474impl LicmDiagSink {
475    pub fn new() -> Self {
476        Self::default()
477    }
478    pub fn push(&mut self, level: LicmDiagLevel, msg: &str) {
479        self.diags.push((level, msg.to_string()));
480    }
481    pub fn has_errors(&self) -> bool {
482        self.diags.iter().any(|(l, _)| *l == LicmDiagLevel::Error)
483    }
484}
485/// LICM loop info summary
486#[allow(dead_code)]
487#[derive(Debug, Clone, Default)]
488pub struct LoopInfoSummary {
489    pub total_loops: usize,
490    pub inner_loops: usize,
491    pub countable_loops: usize,
492    pub avg_depth: f64,
493    pub max_depth: u32,
494}
495/// Profiling data used to guide LICM decisions.
496#[allow(dead_code)]
497#[derive(Debug, Clone, Default)]
498pub struct LICMProfileData {
499    /// Execution counts for each loop (by header var id).
500    pub loop_counts: std::collections::HashMap<LcnfVarId, u64>,
501    /// Execution counts for each let-binding (by var id).
502    pub binding_counts: std::collections::HashMap<LcnfVarId, u64>,
503}
504impl LICMProfileData {
505    /// Create a new empty profile.
506    #[allow(dead_code)]
507    pub fn new() -> Self {
508        LICMProfileData::default()
509    }
510    /// Record an execution count for a loop.
511    #[allow(dead_code)]
512    pub fn record_loop(&mut self, header: LcnfVarId, count: u64) {
513        self.loop_counts.insert(header, count);
514    }
515    /// Get the execution count for a loop (default 1 if unknown).
516    #[allow(dead_code)]
517    pub fn loop_count(&self, header: LcnfVarId) -> u64 {
518        self.loop_counts.get(&header).copied().unwrap_or(1)
519    }
520    /// Record an execution count for a binding.
521    #[allow(dead_code)]
522    pub fn record_binding(&mut self, var: LcnfVarId, count: u64) {
523        self.binding_counts.insert(var, count);
524    }
525    /// Compute the dynamic savings for a hoist candidate given profile data.
526    #[allow(dead_code)]
527    pub fn dynamic_savings(&self, candidate: &HoistCandidate) -> u64 {
528        let loop_exec = self.loop_count(candidate.target_loop_header);
529        (candidate.savings_estimate as u64).saturating_mul(loop_exec)
530    }
531}
532/// Represents a versioned loop: an if-then-else where each branch has a
533/// specialized loop copy optimized for a specific condition.
534#[allow(dead_code)]
535#[derive(Debug, Clone)]
536pub struct LoopVersion {
537    /// The discriminating condition variable.
538    pub cond_var: LcnfVarId,
539    /// Header of the "true" branch (optimized version).
540    pub fast_path_header: LcnfVarId,
541    /// Header of the "false" branch (generic version).
542    pub slow_path_header: LcnfVarId,
543}
544#[allow(dead_code)]
545#[derive(Debug, Clone)]
546pub struct LICMLivenessInfo {
547    pub live_in: Vec<std::collections::HashSet<u32>>,
548    pub live_out: Vec<std::collections::HashSet<u32>>,
549    pub defs: Vec<std::collections::HashSet<u32>>,
550    pub uses: Vec<std::collections::HashSet<u32>>,
551}
552impl LICMLivenessInfo {
553    #[allow(dead_code)]
554    pub fn new(block_count: usize) -> Self {
555        LICMLivenessInfo {
556            live_in: vec![std::collections::HashSet::new(); block_count],
557            live_out: vec![std::collections::HashSet::new(); block_count],
558            defs: vec![std::collections::HashSet::new(); block_count],
559            uses: vec![std::collections::HashSet::new(); block_count],
560        }
561    }
562    #[allow(dead_code)]
563    pub fn add_def(&mut self, block: usize, var: u32) {
564        if block < self.defs.len() {
565            self.defs[block].insert(var);
566        }
567    }
568    #[allow(dead_code)]
569    pub fn add_use(&mut self, block: usize, var: u32) {
570        if block < self.uses.len() {
571            self.uses[block].insert(var);
572        }
573    }
574    #[allow(dead_code)]
575    pub fn is_live_in(&self, block: usize, var: u32) -> bool {
576        self.live_in
577            .get(block)
578            .map(|s| s.contains(&var))
579            .unwrap_or(false)
580    }
581    #[allow(dead_code)]
582    pub fn is_live_out(&self, block: usize, var: u32) -> bool {
583        self.live_out
584            .get(block)
585            .map(|s| s.contains(&var))
586            .unwrap_or(false)
587    }
588}
589/// LICM code stats
590#[allow(dead_code)]
591#[derive(Debug, Default, Clone)]
592pub struct LicmCodeStats {
593    pub loops_analyzed: usize,
594    pub invariant_exprs: usize,
595    pub hoisted: usize,
596    pub sunk: usize,
597    pub speculative: usize,
598    pub rejected: usize,
599}
600#[allow(dead_code)]
601#[derive(Debug, Clone)]
602pub struct LICMDepGraph {
603    pub(super) nodes: Vec<u32>,
604    pub(super) edges: Vec<(u32, u32)>,
605}
606impl LICMDepGraph {
607    #[allow(dead_code)]
608    pub fn new() -> Self {
609        LICMDepGraph {
610            nodes: Vec::new(),
611            edges: Vec::new(),
612        }
613    }
614    #[allow(dead_code)]
615    pub fn add_node(&mut self, id: u32) {
616        if !self.nodes.contains(&id) {
617            self.nodes.push(id);
618        }
619    }
620    #[allow(dead_code)]
621    pub fn add_dep(&mut self, dep: u32, dependent: u32) {
622        self.add_node(dep);
623        self.add_node(dependent);
624        self.edges.push((dep, dependent));
625    }
626    #[allow(dead_code)]
627    pub fn dependents_of(&self, node: u32) -> Vec<u32> {
628        self.edges
629            .iter()
630            .filter(|(d, _)| *d == node)
631            .map(|(_, dep)| *dep)
632            .collect()
633    }
634    #[allow(dead_code)]
635    pub fn dependencies_of(&self, node: u32) -> Vec<u32> {
636        self.edges
637            .iter()
638            .filter(|(_, dep)| *dep == node)
639            .map(|(d, _)| *d)
640            .collect()
641    }
642    #[allow(dead_code)]
643    pub fn topological_sort(&self) -> Vec<u32> {
644        let mut in_degree: std::collections::HashMap<u32, u32> = std::collections::HashMap::new();
645        for &n in &self.nodes {
646            in_degree.insert(n, 0);
647        }
648        for (_, dep) in &self.edges {
649            *in_degree.entry(*dep).or_insert(0) += 1;
650        }
651        let mut queue: std::collections::VecDeque<u32> = self
652            .nodes
653            .iter()
654            .filter(|&&n| in_degree[&n] == 0)
655            .copied()
656            .collect();
657        let mut result = Vec::new();
658        while let Some(node) = queue.pop_front() {
659            result.push(node);
660            for dep in self.dependents_of(node) {
661                let cnt = in_degree.entry(dep).or_insert(0);
662                *cnt = cnt.saturating_sub(1);
663                if *cnt == 0 {
664                    queue.push_back(dep);
665                }
666            }
667        }
668        result
669    }
670    #[allow(dead_code)]
671    pub fn has_cycle(&self) -> bool {
672        self.topological_sort().len() < self.nodes.len()
673    }
674}
675/// Configuration knobs for the LICM pass.
676#[derive(Debug, Clone, Default)]
677pub struct LICMConfig {
678    /// Minimum estimated savings to justify hoisting an expression.
679    /// Defaults to 0 (hoist everything that is safe).
680    pub min_savings_threshold: u32,
681    /// Whether to hoist calls to named functions.
682    /// Defaults to `false` because side-effecting calls must stay in place.
683    pub hoist_function_calls: bool,
684}
685/// Loop preheader (block before loop)
686#[allow(dead_code)]
687#[derive(Debug, Clone)]
688pub struct LoopPreheader {
689    pub loop_id: LoopLevelId,
690    pub preheader_block: u32,
691    pub inserted_insts: Vec<u32>,
692}
693/// Loop tree node
694#[allow(dead_code)]
695#[derive(Debug, Clone)]
696pub struct LoopNode {
697    pub id: LoopLevelId,
698    pub header: u32,
699    pub body_blocks: Vec<u32>,
700    pub parent: Option<LoopLevelId>,
701    pub children: Vec<LoopLevelId>,
702    pub depth: u32,
703    pub is_inner_most: bool,
704    pub trip_count: Option<u64>,
705    pub is_countable: bool,
706}
707#[allow(dead_code)]
708#[derive(Debug, Clone, PartialEq)]
709pub enum LICMPassPhase {
710    Analysis,
711    Transformation,
712    Verification,
713    Cleanup,
714}
715impl LICMPassPhase {
716    #[allow(dead_code)]
717    pub fn name(&self) -> &str {
718        match self {
719            LICMPassPhase::Analysis => "analysis",
720            LICMPassPhase::Transformation => "transformation",
721            LICMPassPhase::Verification => "verification",
722            LICMPassPhase::Cleanup => "cleanup",
723        }
724    }
725    #[allow(dead_code)]
726    pub fn is_modifying(&self) -> bool {
727        matches!(self, LICMPassPhase::Transformation | LICMPassPhase::Cleanup)
728    }
729}
730#[allow(dead_code)]
731#[derive(Debug, Clone)]
732pub struct LICMPassConfig {
733    pub phase: LICMPassPhase,
734    pub enabled: bool,
735    pub max_iterations: u32,
736    pub debug_output: bool,
737    pub pass_name: String,
738}
739impl LICMPassConfig {
740    #[allow(dead_code)]
741    pub fn new(name: impl Into<String>, phase: LICMPassPhase) -> Self {
742        LICMPassConfig {
743            phase,
744            enabled: true,
745            max_iterations: 10,
746            debug_output: false,
747            pass_name: name.into(),
748        }
749    }
750    #[allow(dead_code)]
751    pub fn disabled(mut self) -> Self {
752        self.enabled = false;
753        self
754    }
755    #[allow(dead_code)]
756    pub fn with_debug(mut self) -> Self {
757        self.debug_output = true;
758        self
759    }
760    #[allow(dead_code)]
761    pub fn max_iter(mut self, n: u32) -> Self {
762        self.max_iterations = n;
763        self
764    }
765}
766/// A synthetic block that is prepended before a loop to receive hoisted code.
767///
768/// After LICM the `preheader_lets` bindings appear sequentially before the
769/// loop entry in the output LCNF.
770#[derive(Debug, Clone)]
771pub struct PreheaderBlock {
772    /// The loop this preheader guards.
773    pub loop_header: LcnfVarId,
774    /// Bindings to materialise in the preheader, in hoisting order.
775    pub preheader_lets: Vec<LoopInvariantExpr>,
776}
777#[allow(dead_code)]
778#[derive(Debug, Clone)]
779pub struct LICMDominatorTree {
780    pub idom: Vec<Option<u32>>,
781    pub dom_children: Vec<Vec<u32>>,
782    pub dom_depth: Vec<u32>,
783}
784impl LICMDominatorTree {
785    #[allow(dead_code)]
786    pub fn new(size: usize) -> Self {
787        LICMDominatorTree {
788            idom: vec![None; size],
789            dom_children: vec![Vec::new(); size],
790            dom_depth: vec![0; size],
791        }
792    }
793    #[allow(dead_code)]
794    pub fn set_idom(&mut self, node: usize, idom: u32) {
795        self.idom[node] = Some(idom);
796    }
797    #[allow(dead_code)]
798    pub fn dominates(&self, a: usize, b: usize) -> bool {
799        if a == b {
800            return true;
801        }
802        let mut cur = b;
803        loop {
804            match self.idom[cur] {
805                Some(parent) if parent as usize == a => return true,
806                Some(parent) if parent as usize == cur => return false,
807                Some(parent) => cur = parent as usize,
808                None => return false,
809            }
810        }
811    }
812    #[allow(dead_code)]
813    pub fn depth(&self, node: usize) -> u32 {
814        self.dom_depth.get(node).copied().unwrap_or(0)
815    }
816}
817/// Identifies load-like operations (projections, field reads) that are redundant
818/// because the same value has already been loaded earlier in the same scope.
819#[allow(dead_code)]
820#[derive(Debug, Clone, Default)]
821pub struct RedundantLoadInfo {
822    /// Maps (base_var, field_index) -> binding_var that holds the loaded value.
823    pub available_loads: std::collections::HashMap<(LcnfVarId, u32), LcnfVarId>,
824    /// Number of redundant loads detected.
825    pub redundant_count: usize,
826}
827impl RedundantLoadInfo {
828    /// Create a new empty `RedundantLoadInfo`.
829    #[allow(dead_code)]
830    pub fn new() -> Self {
831        RedundantLoadInfo::default()
832    }
833    /// Register a load: reading field `field_idx` of `base` into `dest`.
834    #[allow(dead_code)]
835    pub fn register_load(&mut self, base: LcnfVarId, field_idx: u32, dest: LcnfVarId) {
836        self.available_loads.insert((base, field_idx), dest);
837    }
838    /// Check if a load is redundant. Returns the earlier binding var if so.
839    #[allow(dead_code)]
840    pub fn lookup_load(&self, base: LcnfVarId, field_idx: u32) -> Option<LcnfVarId> {
841        self.available_loads.get(&(base, field_idx)).copied()
842    }
843    /// Scan an expression for redundant projections.
844    #[allow(dead_code)]
845    pub fn analyze(&mut self, expr: &LcnfExpr) {
846        match expr {
847            LcnfExpr::Let {
848                id,
849                value: LcnfLetValue::Proj(_field_name, ctor_tag, base),
850                body,
851                ..
852            } => {
853                if self.lookup_load(*base, *ctor_tag).is_some() {
854                    self.redundant_count += 1;
855                } else {
856                    self.register_load(*base, *ctor_tag, *id);
857                }
858                self.analyze(body);
859            }
860            LcnfExpr::Let { body, .. } => self.analyze(body),
861            LcnfExpr::Case { alts, default, .. } => {
862                for alt in alts {
863                    self.analyze(&alt.body);
864                }
865                if let Some(d) = default {
866                    self.analyze(d);
867                }
868            }
869            LcnfExpr::Return(_) | LcnfExpr::Unreachable | LcnfExpr::TailCall(..) => {}
870        }
871    }
872}
873/// Configuration for loop versioning.
874#[allow(dead_code)]
875#[derive(Debug, Clone, Default)]
876pub struct LoopVersioningConfig {
877    /// Maximum number of loop versions to create.
878    pub max_versions: usize,
879    /// Minimum estimated speedup (as a ratio) to justify versioning.
880    pub min_speedup_ratio: f32,
881}
882impl LoopVersioningConfig {
883    /// Create a conservative configuration.
884    #[allow(dead_code)]
885    pub fn conservative() -> Self {
886        LoopVersioningConfig {
887            max_versions: 2,
888            min_speedup_ratio: 1.5,
889        }
890    }
891}
892/// Statistics produced by a single LICM run.
893#[derive(Debug, Clone, Default)]
894pub struct LICMReport {
895    /// Total number of loops analysed.
896    pub loops_analyzed: usize,
897    /// Number of expressions hoisted out of loops.
898    pub expressions_hoisted: usize,
899    /// Total estimated dynamic evaluations saved.
900    pub estimated_savings: u64,
901}
902impl LICMReport {
903    /// Merge another report into `self`.
904    pub fn merge(&mut self, other: &LICMReport) {
905        self.loops_analyzed += other.loops_analyzed;
906        self.expressions_hoisted += other.expressions_hoisted;
907        self.estimated_savings += other.estimated_savings;
908    }
909}
910/// A candidate expression ready to be hoisted to a preheader.
911#[derive(Debug, Clone)]
912pub struct HoistCandidate {
913    /// The invariant binding to hoist.
914    pub expr: LoopInvariantExpr,
915    /// The id of the loop this candidate should be hoisted out of.
916    pub target_loop_header: LcnfVarId,
917    /// Estimated number of redundant evaluations saved (loop trip count
918    /// heuristic; we use 10 as a conservative default).
919    pub savings_estimate: u32,
920}
921/// LICM loop nest (for perfectly nested loops)
922#[allow(dead_code)]
923#[derive(Debug, Clone)]
924pub struct LoopNest {
925    pub loops: Vec<LoopLevelId>,
926    pub depth: u32,
927    pub is_perfect: bool,
928}
929/// LICM emit stats
930#[allow(dead_code)]
931#[derive(Debug, Default, Clone)]
932pub struct LicmExtEmitStats {
933    pub bytes_written: usize,
934    pub items_emitted: usize,
935    pub errors: usize,
936    pub warnings: usize,
937}
938/// A let-binding inside a loop whose value is loop-invariant.
939#[derive(Debug, Clone)]
940pub struct LoopInvariantExpr {
941    /// The variable introduced by this binding.
942    pub var: LcnfVarId,
943    /// The right-hand side value (invariant computation).
944    pub value: LcnfLetValue,
945    /// The type of the variable.
946    pub ty: LcnfType,
947    /// Nesting depth of the loop this expression was found in.
948    pub loop_depth: u32,
949}
950/// LICM result map
951#[allow(dead_code)]
952#[derive(Debug, Default)]
953pub struct LicmResultMap {
954    pub hoisted: std::collections::HashMap<u32, LoopLevelId>,
955    pub sunk: std::collections::HashMap<u32, u32>,
956    pub versioned: Vec<LicmVersion>,
957}
958#[allow(dead_code)]
959impl LicmResultMap {
960    pub fn new() -> Self {
961        Self::default()
962    }
963    pub fn mark_hoisted(&mut self, inst: u32, loop_id: LoopLevelId) {
964        self.hoisted.insert(inst, loop_id);
965    }
966    pub fn mark_sunk(&mut self, inst: u32, block: u32) {
967        self.sunk.insert(inst, block);
968    }
969    pub fn add_version(&mut self, v: LicmVersion) {
970        self.versioned.push(v);
971    }
972    pub fn hoist_count(&self) -> usize {
973        self.hoisted.len()
974    }
975    pub fn sink_count(&self) -> usize {
976        self.sunk.len()
977    }
978}
979/// LICM preheader map
980#[allow(dead_code)]
981#[derive(Debug, Default)]
982pub struct LicmPreheaderMap {
983    pub map: std::collections::HashMap<LoopLevelId, LoopPreheader>,
984}
985#[allow(dead_code)]
986impl LicmPreheaderMap {
987    pub fn new() -> Self {
988        Self::default()
989    }
990    pub fn insert(&mut self, ph: LoopPreheader) {
991        self.map.insert(ph.loop_id.clone(), ph);
992    }
993    pub fn get(&self, id: &LoopLevelId) -> Option<&LoopPreheader> {
994        self.map.get(id)
995    }
996    pub fn count(&self) -> usize {
997        self.map.len()
998    }
999}
1000#[allow(dead_code)]
1001#[derive(Debug, Clone, Default)]
1002pub struct LICMPassStats {
1003    pub total_runs: u32,
1004    pub successful_runs: u32,
1005    pub total_changes: u64,
1006    pub time_ms: u64,
1007    pub iterations_used: u32,
1008}
1009impl LICMPassStats {
1010    #[allow(dead_code)]
1011    pub fn new() -> Self {
1012        Self::default()
1013    }
1014    #[allow(dead_code)]
1015    pub fn record_run(&mut self, changes: u64, time_ms: u64, iterations: u32) {
1016        self.total_runs += 1;
1017        self.successful_runs += 1;
1018        self.total_changes += changes;
1019        self.time_ms += time_ms;
1020        self.iterations_used = iterations;
1021    }
1022    #[allow(dead_code)]
1023    pub fn average_changes_per_run(&self) -> f64 {
1024        if self.total_runs == 0 {
1025            return 0.0;
1026        }
1027        self.total_changes as f64 / self.total_runs as f64
1028    }
1029    #[allow(dead_code)]
1030    pub fn success_rate(&self) -> f64 {
1031        if self.total_runs == 0 {
1032            return 0.0;
1033        }
1034        self.successful_runs as f64 / self.total_runs as f64
1035    }
1036    #[allow(dead_code)]
1037    pub fn format_summary(&self) -> String {
1038        format!(
1039            "Runs: {}/{}, Changes: {}, Time: {}ms",
1040            self.successful_runs, self.total_runs, self.total_changes, self.time_ms
1041        )
1042    }
1043}
1044/// LICM source buffer
1045#[allow(dead_code)]
1046#[derive(Debug, Default)]
1047pub struct LicmExtSourceBuffer {
1048    pub content: String,
1049}
1050#[allow(dead_code)]
1051impl LicmExtSourceBuffer {
1052    pub fn new() -> Self {
1053        Self::default()
1054    }
1055    pub fn write(&mut self, s: &str) {
1056        self.content.push_str(s);
1057    }
1058    pub fn writeln(&mut self, s: &str) {
1059        self.content.push_str(s);
1060        self.content.push('\n');
1061    }
1062    pub fn finish(self) -> String {
1063        self.content
1064    }
1065}
1066#[allow(dead_code)]
1067#[derive(Debug, Clone)]
1068pub struct LICMAnalysisCache {
1069    pub(super) entries: std::collections::HashMap<String, LICMCacheEntry>,
1070    pub(super) max_size: usize,
1071    pub(super) hits: u64,
1072    pub(super) misses: u64,
1073}
1074impl LICMAnalysisCache {
1075    #[allow(dead_code)]
1076    pub fn new(max_size: usize) -> Self {
1077        LICMAnalysisCache {
1078            entries: std::collections::HashMap::new(),
1079            max_size,
1080            hits: 0,
1081            misses: 0,
1082        }
1083    }
1084    #[allow(dead_code)]
1085    pub fn get(&mut self, key: &str) -> Option<&LICMCacheEntry> {
1086        if self.entries.contains_key(key) {
1087            self.hits += 1;
1088            self.entries.get(key)
1089        } else {
1090            self.misses += 1;
1091            None
1092        }
1093    }
1094    #[allow(dead_code)]
1095    pub fn insert(&mut self, key: String, data: Vec<u8>) {
1096        if self.entries.len() >= self.max_size {
1097            if let Some(oldest) = self.entries.keys().next().cloned() {
1098                self.entries.remove(&oldest);
1099            }
1100        }
1101        self.entries.insert(
1102            key.clone(),
1103            LICMCacheEntry {
1104                key,
1105                data,
1106                timestamp: 0,
1107                valid: true,
1108            },
1109        );
1110    }
1111    #[allow(dead_code)]
1112    pub fn invalidate(&mut self, key: &str) {
1113        if let Some(entry) = self.entries.get_mut(key) {
1114            entry.valid = false;
1115        }
1116    }
1117    #[allow(dead_code)]
1118    pub fn clear(&mut self) {
1119        self.entries.clear();
1120    }
1121    #[allow(dead_code)]
1122    pub fn hit_rate(&self) -> f64 {
1123        let total = self.hits + self.misses;
1124        if total == 0 {
1125            return 0.0;
1126        }
1127        self.hits as f64 / total as f64
1128    }
1129    #[allow(dead_code)]
1130    pub fn size(&self) -> usize {
1131        self.entries.len()
1132    }
1133}
1134#[allow(dead_code)]
1135#[derive(Debug, Clone)]
1136pub struct LICMWorklist {
1137    pub(super) items: std::collections::VecDeque<u32>,
1138    pub(super) in_worklist: std::collections::HashSet<u32>,
1139}
1140impl LICMWorklist {
1141    #[allow(dead_code)]
1142    pub fn new() -> Self {
1143        LICMWorklist {
1144            items: std::collections::VecDeque::new(),
1145            in_worklist: std::collections::HashSet::new(),
1146        }
1147    }
1148    #[allow(dead_code)]
1149    pub fn push(&mut self, item: u32) -> bool {
1150        if self.in_worklist.insert(item) {
1151            self.items.push_back(item);
1152            true
1153        } else {
1154            false
1155        }
1156    }
1157    #[allow(dead_code)]
1158    pub fn pop(&mut self) -> Option<u32> {
1159        let item = self.items.pop_front()?;
1160        self.in_worklist.remove(&item);
1161        Some(item)
1162    }
1163    #[allow(dead_code)]
1164    pub fn is_empty(&self) -> bool {
1165        self.items.is_empty()
1166    }
1167    #[allow(dead_code)]
1168    pub fn len(&self) -> usize {
1169        self.items.len()
1170    }
1171    #[allow(dead_code)]
1172    pub fn contains(&self, item: u32) -> bool {
1173        self.in_worklist.contains(&item)
1174    }
1175}
1176/// LICM feature flags
1177#[allow(dead_code)]
1178#[derive(Debug, Clone, Default)]
1179pub struct LicmFeatureFlags {
1180    pub speculative: bool,
1181    pub sink_enabled: bool,
1182    pub hoist_loads: bool,
1183    pub hoist_pure_calls: bool,
1184}
1185#[allow(dead_code)]
1186pub struct LICMConstantFoldingHelper;
1187impl LICMConstantFoldingHelper {
1188    #[allow(dead_code)]
1189    pub fn fold_add_i64(a: i64, b: i64) -> Option<i64> {
1190        a.checked_add(b)
1191    }
1192    #[allow(dead_code)]
1193    pub fn fold_sub_i64(a: i64, b: i64) -> Option<i64> {
1194        a.checked_sub(b)
1195    }
1196    #[allow(dead_code)]
1197    pub fn fold_mul_i64(a: i64, b: i64) -> Option<i64> {
1198        a.checked_mul(b)
1199    }
1200    #[allow(dead_code)]
1201    pub fn fold_div_i64(a: i64, b: i64) -> Option<i64> {
1202        if b == 0 {
1203            None
1204        } else {
1205            a.checked_div(b)
1206        }
1207    }
1208    #[allow(dead_code)]
1209    pub fn fold_add_f64(a: f64, b: f64) -> f64 {
1210        a + b
1211    }
1212    #[allow(dead_code)]
1213    pub fn fold_mul_f64(a: f64, b: f64) -> f64 {
1214        a * b
1215    }
1216    #[allow(dead_code)]
1217    pub fn fold_neg_i64(a: i64) -> Option<i64> {
1218        a.checked_neg()
1219    }
1220    #[allow(dead_code)]
1221    pub fn fold_not_bool(a: bool) -> bool {
1222        !a
1223    }
1224    #[allow(dead_code)]
1225    pub fn fold_and_bool(a: bool, b: bool) -> bool {
1226        a && b
1227    }
1228    #[allow(dead_code)]
1229    pub fn fold_or_bool(a: bool, b: bool) -> bool {
1230        a || b
1231    }
1232    #[allow(dead_code)]
1233    pub fn fold_shl_i64(a: i64, b: u32) -> Option<i64> {
1234        a.checked_shl(b)
1235    }
1236    #[allow(dead_code)]
1237    pub fn fold_shr_i64(a: i64, b: u32) -> Option<i64> {
1238        a.checked_shr(b)
1239    }
1240    #[allow(dead_code)]
1241    pub fn fold_rem_i64(a: i64, b: i64) -> Option<i64> {
1242        if b == 0 {
1243            None
1244        } else {
1245            Some(a % b)
1246        }
1247    }
1248    #[allow(dead_code)]
1249    pub fn fold_bitand_i64(a: i64, b: i64) -> i64 {
1250        a & b
1251    }
1252    #[allow(dead_code)]
1253    pub fn fold_bitor_i64(a: i64, b: i64) -> i64 {
1254        a | b
1255    }
1256    #[allow(dead_code)]
1257    pub fn fold_bitxor_i64(a: i64, b: i64) -> i64 {
1258        a ^ b
1259    }
1260    #[allow(dead_code)]
1261    pub fn fold_bitnot_i64(a: i64) -> i64 {
1262        !a
1263    }
1264}
1265/// LICM versioning (for speculative hoisting)
1266#[allow(dead_code)]
1267#[derive(Debug, Clone)]
1268pub struct LicmVersion {
1269    pub original: u32,
1270    pub versioned: u32,
1271    pub guard_cond: String,
1272}
1273#[allow(dead_code)]
1274pub struct LICMPassRegistry {
1275    pub(super) configs: Vec<LICMPassConfig>,
1276    pub(super) stats: std::collections::HashMap<String, LICMPassStats>,
1277}
1278impl LICMPassRegistry {
1279    #[allow(dead_code)]
1280    pub fn new() -> Self {
1281        LICMPassRegistry {
1282            configs: Vec::new(),
1283            stats: std::collections::HashMap::new(),
1284        }
1285    }
1286    #[allow(dead_code)]
1287    pub fn register(&mut self, config: LICMPassConfig) {
1288        self.stats
1289            .insert(config.pass_name.clone(), LICMPassStats::new());
1290        self.configs.push(config);
1291    }
1292    #[allow(dead_code)]
1293    pub fn enabled_passes(&self) -> Vec<&LICMPassConfig> {
1294        self.configs.iter().filter(|c| c.enabled).collect()
1295    }
1296    #[allow(dead_code)]
1297    pub fn get_stats(&self, name: &str) -> Option<&LICMPassStats> {
1298        self.stats.get(name)
1299    }
1300    #[allow(dead_code)]
1301    pub fn total_passes(&self) -> usize {
1302        self.configs.len()
1303    }
1304    #[allow(dead_code)]
1305    pub fn enabled_count(&self) -> usize {
1306        self.enabled_passes().len()
1307    }
1308    #[allow(dead_code)]
1309    pub fn update_stats(&mut self, name: &str, changes: u64, time_ms: u64, iter: u32) {
1310        if let Some(stats) = self.stats.get_mut(name) {
1311            stats.record_run(changes, time_ms, iter);
1312        }
1313    }
1314}
1315/// LICM loop body analysis result
1316#[allow(dead_code)]
1317#[derive(Debug, Clone, Default)]
1318pub struct LoopBodyAnalysis {
1319    pub loop_id: u32,
1320    pub def_vars: std::collections::HashSet<u32>,
1321    pub use_vars: std::collections::HashSet<u32>,
1322    pub load_insts: Vec<u32>,
1323    pub store_insts: Vec<u32>,
1324    pub call_insts: Vec<u32>,
1325    pub has_volatile: bool,
1326    pub has_exception: bool,
1327}
1328#[allow(dead_code)]
1329impl LoopBodyAnalysis {
1330    pub fn new(loop_id: u32) -> Self {
1331        Self {
1332            loop_id,
1333            ..Default::default()
1334        }
1335    }
1336    pub fn add_def(&mut self, var: u32) {
1337        self.def_vars.insert(var);
1338    }
1339    pub fn add_use(&mut self, var: u32) {
1340        self.use_vars.insert(var);
1341    }
1342    pub fn is_def(&self, var: u32) -> bool {
1343        self.def_vars.contains(&var)
1344    }
1345    pub fn is_invariant(&self, var: u32) -> bool {
1346        !self.def_vars.contains(&var)
1347    }
1348    pub fn num_memory_ops(&self) -> usize {
1349        self.load_insts.len() + self.store_insts.len()
1350    }
1351}
1352/// LICM loop info builder
1353#[allow(dead_code)]
1354#[derive(Debug, Default)]
1355pub struct LoopInfoBuilder {
1356    pub loops: Vec<LoopNode>,
1357}
1358#[allow(dead_code)]
1359impl LoopInfoBuilder {
1360    pub fn new() -> Self {
1361        Self::default()
1362    }
1363    pub fn add_loop(&mut self, n: LoopNode) {
1364        self.loops.push(n);
1365    }
1366    pub fn build_tree(self) -> LoopTree {
1367        let mut tree = LoopTree::new();
1368        for n in self.loops {
1369            tree.add(n);
1370        }
1371        tree
1372    }
1373    pub fn summarize(&self) -> LoopInfoSummary {
1374        let total = self.loops.len();
1375        let inner = self.loops.iter().filter(|n| n.is_inner_most).count();
1376        let countable = self.loops.iter().filter(|n| n.is_countable).count();
1377        let depths: Vec<u32> = self.loops.iter().map(|n| n.depth).collect();
1378        let max_depth = depths.iter().copied().max().unwrap_or(0);
1379        let avg_depth = if total > 0 {
1380            depths.iter().sum::<u32>() as f64 / total as f64
1381        } else {
1382            0.0
1383        };
1384        LoopInfoSummary {
1385            total_loops: total,
1386            inner_loops: inner,
1387            countable_loops: countable,
1388            avg_depth,
1389            max_depth,
1390        }
1391    }
1392}
1393/// Identifies a loop in the LCNF control-flow graph.
1394///
1395/// In ANF / LCNF, loops manifest as (mutually) recursive function bindings.
1396/// The "header" is the function id that forms the back-edge target.
1397#[derive(Debug, Clone)]
1398pub struct LoopStructure {
1399    /// The variable id of the loop header (recursive entry point).
1400    pub header: LcnfVarId,
1401    /// All variables defined inside the loop body.
1402    pub body_vars: HashSet<LcnfVarId>,
1403    /// Variables that are live on loop exit (used outside the loop).
1404    pub exit_vars: HashSet<LcnfVarId>,
1405    /// Nesting depth (0 = outermost loop).
1406    pub nest_depth: u32,
1407}
1408/// LICM pass summary
1409#[allow(dead_code)]
1410#[derive(Debug, Default, Clone)]
1411pub struct LicmPassSummary {
1412    pub pass_name: String,
1413    pub functions_processed: usize,
1414    pub hoisted: usize,
1415    pub sunk: usize,
1416    pub duration_us: u64,
1417}
1418/// LICM sink candidate (for loop exit sinking)
1419#[allow(dead_code)]
1420#[derive(Debug, Clone)]
1421pub struct LicmSinkCandidate {
1422    pub inst_id: u32,
1423    pub loop_id: LoopLevelId,
1424    pub sink_to_block: u32,
1425    pub benefit: i32,
1426}
1427/// Loop tree
1428#[allow(dead_code)]
1429#[derive(Debug, Default)]
1430pub struct LoopTree {
1431    pub loops: std::collections::HashMap<LoopLevelId, LoopNode>,
1432    pub top_level: Vec<LoopLevelId>,
1433}
1434#[allow(dead_code)]
1435impl LoopTree {
1436    pub fn new() -> Self {
1437        Self::default()
1438    }
1439    pub fn add(&mut self, node: LoopNode) {
1440        if node.parent.is_none() {
1441            self.top_level.push(node.id.clone());
1442        }
1443        self.loops.insert(node.id.clone(), node);
1444    }
1445    pub fn get(&self, id: &LoopLevelId) -> Option<&LoopNode> {
1446        self.loops.get(id)
1447    }
1448    pub fn num_loops(&self) -> usize {
1449        self.loops.len()
1450    }
1451    pub fn inner_loops(&self) -> Vec<&LoopNode> {
1452        self.loops.values().filter(|n| n.is_inner_most).collect()
1453    }
1454}
1455/// LICM diagnostic
1456#[allow(dead_code)]
1457#[derive(Debug, Clone, PartialEq, Eq)]
1458pub enum LicmDiagLevel {
1459    Info,
1460    Warning,
1461    Error,
1462}
1463/// A named phase in a LICM-centric optimization pipeline.
1464#[allow(dead_code)]
1465#[derive(Debug, Clone, PartialEq, Eq)]
1466pub enum LICMPhase {
1467    /// Run LICM before CSE.
1468    LICMBeforeCSE,
1469    /// Run LICM after CSE.
1470    LICMAfterCSE,
1471    /// Run LICM in a loop until no more changes.
1472    LICMIterative,
1473    /// Run LICM once and stop.
1474    LICMOnce,
1475}
1476/// Loop nest information aggregated from a set of loop structures.
1477#[allow(dead_code)]
1478#[derive(Debug, Clone)]
1479pub struct LoopNestInfo {
1480    /// Maximum nesting depth among all loops.
1481    pub max_depth: u32,
1482    /// Total number of body variables across all loops.
1483    pub total_body_vars: usize,
1484    /// The loop structures.
1485    pub loops: Vec<LoopStructure>,
1486}
1487impl LoopNestInfo {
1488    /// Build loop nest info from a vector of loop structures.
1489    #[allow(dead_code)]
1490    pub fn from_loops(loops: Vec<LoopStructure>) -> Self {
1491        let max_depth = loops.iter().map(|l| l.nest_depth).max().unwrap_or(0);
1492        let total_body_vars: usize = loops.iter().map(|l| l.body_vars.len()).sum();
1493        LoopNestInfo {
1494            max_depth,
1495            total_body_vars,
1496            loops,
1497        }
1498    }
1499}
1500/// LICM heuristics configuration for LICMPassV2.
1501#[allow(dead_code)]
1502#[derive(Debug, Clone)]
1503pub struct LICMHeuristics {
1504    /// Maximum cost of an expression to consider for hoisting.
1505    pub max_hoist_cost: u32,
1506    /// Minimum savings estimate to justify hoisting.
1507    pub min_savings: u32,
1508}
1509impl Default for LICMHeuristics {
1510    fn default() -> Self {
1511        LICMHeuristics {
1512            max_hoist_cost: 100,
1513            min_savings: 0,
1514        }
1515    }
1516}
1517/// Version 2 of the LICM pass with heuristic control.
1518#[allow(dead_code)]
1519pub struct LICMPassV2 {
1520    /// Heuristics for deciding what to hoist.
1521    pub heuristics: LICMHeuristics,
1522    /// The inner LICM pass.
1523    inner: LICMPass,
1524}
1525#[allow(dead_code)]
1526impl LICMPassV2 {
1527    /// Create a new LICM v2 pass with default heuristics.
1528    pub fn new() -> Self {
1529        LICMPassV2 {
1530            heuristics: LICMHeuristics::default(),
1531            inner: LICMPass::new(LICMConfig {
1532                min_savings_threshold: 0,
1533                hoist_function_calls: false,
1534            }),
1535        }
1536    }
1537    /// Run the LICM v2 pass over function declarations.
1538    pub fn run(&mut self, decls: &mut [LcnfFunDecl]) {
1539        self.inner.config.min_savings_threshold = self.heuristics.min_savings;
1540        self.inner.run(decls);
1541    }
1542    /// Get the report from the inner pass.
1543    pub fn report(&self) -> &LICMReport {
1544        &self.inner.report
1545    }
1546}
1547/// Materialize a preheader block by wrapping an inner expression with
1548/// the let bindings from the preheader.
1549#[allow(dead_code)]
1550pub fn materialize_preheader(pb: &PreheaderBlock, inner: LcnfExpr) -> LcnfExpr {
1551    let mut result = inner;
1552    for inv in pb.preheader_lets.iter().rev() {
1553        result = LcnfExpr::Let {
1554            id: inv.var,
1555            name: format!("_pre_{}", inv.var.0),
1556            ty: inv.ty.clone(),
1557            value: inv.value.clone(),
1558            body: Box::new(result),
1559        };
1560    }
1561    result
1562}
1563/// Topologically sort hoist candidates so that producers come before
1564/// consumers (i.e., if candidate B uses the variable defined by A,
1565/// A must appear first).
1566#[allow(dead_code)]
1567pub fn topo_sort_candidates(candidates: &[HoistCandidate]) -> Vec<HoistCandidate> {
1568    let defined: HashSet<LcnfVarId> = candidates.iter().map(|c| c.expr.var).collect();
1569    // Build dependency map: deps[v] = variables that v depends on
1570    let mut deps: HashMap<LcnfVarId, Vec<LcnfVarId>> = HashMap::new();
1571    for c in candidates {
1572        let mut c_deps = Vec::new();
1573        match &c.expr.value {
1574            LcnfLetValue::FVar(v) if defined.contains(v) => {
1575                c_deps.push(*v);
1576            }
1577            LcnfLetValue::App(f, args) => {
1578                if let LcnfArg::Var(v) = f {
1579                    if defined.contains(v) {
1580                        c_deps.push(*v);
1581                    }
1582                }
1583                for a in args {
1584                    if let LcnfArg::Var(v) = a {
1585                        if defined.contains(v) {
1586                            c_deps.push(*v);
1587                        }
1588                    }
1589                }
1590            }
1591            LcnfLetValue::Proj(_, _, v) if defined.contains(v) => {
1592                c_deps.push(*v);
1593            }
1594            _ => {}
1595        }
1596        deps.insert(c.expr.var, c_deps);
1597    }
1598    // Build adjacency list and in-degree for Kahn's algorithm
1599    // Edge dep -> v means dep must come before v
1600    let mut adj: HashMap<LcnfVarId, Vec<LcnfVarId>> = HashMap::new();
1601    let mut in_degree: HashMap<LcnfVarId, usize> =
1602        candidates.iter().map(|c| (c.expr.var, 0)).collect();
1603    for (v, d) in &deps {
1604        for dep in d {
1605            adj.entry(*dep).or_default().push(*v);
1606            *in_degree.entry(*v).or_default() += 1;
1607        }
1608    }
1609    let mut queue: VecDeque<LcnfVarId> = in_degree
1610        .iter()
1611        .filter(|(_, &d)| d == 0)
1612        .map(|(v, _)| *v)
1613        .collect();
1614    let by_var: HashMap<LcnfVarId, &HoistCandidate> =
1615        candidates.iter().map(|c| (c.expr.var, c)).collect();
1616    let mut result = Vec::new();
1617    while let Some(v) = queue.pop_front() {
1618        if let Some(c) = by_var.get(&v) {
1619            result.push((*c).clone());
1620        }
1621        if let Some(neighbors) = adj.get(&v) {
1622            for n in neighbors {
1623                if let Some(d) = in_degree.get_mut(n) {
1624                    *d -= 1;
1625                    if *d == 0 {
1626                        queue.push_back(*n);
1627                    }
1628                }
1629            }
1630        }
1631    }
1632    result
1633}
oxilean_codegen/opt_licm/types.rs

oxilean_codegen/opt_licm/
types.rs
