oxilean_codegen/opt_dce/
types.rs

1//! Auto-generated module
2//!
3//! 🤖 Generated with [SplitRS](https://github.com/cool-japan/splitrs)
4
5use crate::lcnf::*;
6use std::collections::{HashMap, HashSet, VecDeque};
7
8#[allow(dead_code)]
9#[derive(Debug, Clone, PartialEq)]
10pub enum DCEPassPhase {
11    Analysis,
12    Transformation,
13    Verification,
14    Cleanup,
15}
16impl DCEPassPhase {
17    #[allow(dead_code)]
18    pub fn name(&self) -> &str {
19        match self {
20            DCEPassPhase::Analysis => "analysis",
21            DCEPassPhase::Transformation => "transformation",
22            DCEPassPhase::Verification => "verification",
23            DCEPassPhase::Cleanup => "cleanup",
24        }
25    }
26    #[allow(dead_code)]
27    pub fn is_modifying(&self) -> bool {
28        matches!(self, DCEPassPhase::Transformation | DCEPassPhase::Cleanup)
29    }
30}
31/// Per-variable usage information collected by occurrence analysis.
32#[derive(Debug, Clone, Default)]
33pub struct UsageInfo {
34    /// How many times the variable is referenced.
35    pub use_count: usize,
36    /// Whether the variable escapes into a closure, constructor field,
37    /// or any context where its lifetime is not locally bounded.
38    pub is_escaping: bool,
39    /// Whether any use of the variable occurs inside a syntactic loop
40    /// (i.e., inside a recursive function body or after a back-edge).
41    pub is_in_loop: bool,
42}
43impl UsageInfo {
44    /// Create a fresh usage info with zero uses and no flags set.
45    pub(super) fn new() -> Self {
46        UsageInfo {
47            use_count: 0,
48            is_escaping: false,
49            is_in_loop: false,
50        }
51    }
52    /// Record one additional use of the variable.
53    pub(super) fn add_use(&mut self) {
54        self.use_count += 1;
55    }
56    /// Mark the variable as escaping.
57    pub(super) fn mark_escaping(&mut self) {
58        self.is_escaping = true;
59    }
60    /// Mark the variable as used inside a loop.
61    pub(super) fn mark_in_loop(&mut self) {
62        self.is_in_loop = true;
63    }
64    /// Returns `true` if the variable is dead (zero uses).
65    pub fn is_dead(&self) -> bool {
66        self.use_count == 0
67    }
68    /// Returns `true` if the variable is used exactly once.
69    pub fn is_once(&self) -> bool {
70        self.use_count == 1
71    }
72}
73#[allow(dead_code)]
74#[derive(Debug, Clone)]
75pub struct DCEPassConfig {
76    pub phase: DCEPassPhase,
77    pub enabled: bool,
78    pub max_iterations: u32,
79    pub debug_output: bool,
80    pub pass_name: String,
81}
82impl DCEPassConfig {
83    #[allow(dead_code)]
84    pub fn new(name: impl Into<String>, phase: DCEPassPhase) -> Self {
85        DCEPassConfig {
86            phase,
87            enabled: true,
88            max_iterations: 10,
89            debug_output: false,
90            pass_name: name.into(),
91        }
92    }
93    #[allow(dead_code)]
94    pub fn disabled(mut self) -> Self {
95        self.enabled = false;
96        self
97    }
98    #[allow(dead_code)]
99    pub fn with_debug(mut self) -> Self {
100        self.debug_output = true;
101        self
102    }
103    #[allow(dead_code)]
104    pub fn max_iter(mut self, n: u32) -> Self {
105        self.max_iterations = n;
106        self
107    }
108}
109#[allow(dead_code)]
110pub struct DCEPassRegistry {
111    pub(super) configs: Vec<DCEPassConfig>,
112    pub(super) stats: std::collections::HashMap<String, DCEPassStats>,
113}
114impl DCEPassRegistry {
115    #[allow(dead_code)]
116    pub fn new() -> Self {
117        DCEPassRegistry {
118            configs: Vec::new(),
119            stats: std::collections::HashMap::new(),
120        }
121    }
122    #[allow(dead_code)]
123    pub fn register(&mut self, config: DCEPassConfig) {
124        self.stats
125            .insert(config.pass_name.clone(), DCEPassStats::new());
126        self.configs.push(config);
127    }
128    #[allow(dead_code)]
129    pub fn enabled_passes(&self) -> Vec<&DCEPassConfig> {
130        self.configs.iter().filter(|c| c.enabled).collect()
131    }
132    #[allow(dead_code)]
133    pub fn get_stats(&self, name: &str) -> Option<&DCEPassStats> {
134        self.stats.get(name)
135    }
136    #[allow(dead_code)]
137    pub fn total_passes(&self) -> usize {
138        self.configs.len()
139    }
140    #[allow(dead_code)]
141    pub fn enabled_count(&self) -> usize {
142        self.enabled_passes().len()
143    }
144    #[allow(dead_code)]
145    pub fn update_stats(&mut self, name: &str, changes: u64, time_ms: u64, iter: u32) {
146        if let Some(stats) = self.stats.get_mut(name) {
147            stats.record_run(changes, time_ms, iter);
148        }
149    }
150}
151#[allow(dead_code)]
152#[derive(Debug, Clone)]
153pub struct DCECacheEntry {
154    pub key: String,
155    pub data: Vec<u8>,
156    pub timestamp: u64,
157    pub valid: bool,
158}
159#[allow(dead_code)]
160#[derive(Debug, Clone, Default)]
161pub struct DCEPassStats {
162    pub total_runs: u32,
163    pub successful_runs: u32,
164    pub total_changes: u64,
165    pub time_ms: u64,
166    pub iterations_used: u32,
167}
168impl DCEPassStats {
169    #[allow(dead_code)]
170    pub fn new() -> Self {
171        Self::default()
172    }
173    #[allow(dead_code)]
174    pub fn record_run(&mut self, changes: u64, time_ms: u64, iterations: u32) {
175        self.total_runs += 1;
176        self.successful_runs += 1;
177        self.total_changes += changes;
178        self.time_ms += time_ms;
179        self.iterations_used = iterations;
180    }
181    #[allow(dead_code)]
182    pub fn average_changes_per_run(&self) -> f64 {
183        if self.total_runs == 0 {
184            return 0.0;
185        }
186        self.total_changes as f64 / self.total_runs as f64
187    }
188    #[allow(dead_code)]
189    pub fn success_rate(&self) -> f64 {
190        if self.total_runs == 0 {
191            return 0.0;
192        }
193        self.successful_runs as f64 / self.total_runs as f64
194    }
195    #[allow(dead_code)]
196    pub fn format_summary(&self) -> String {
197        format!(
198            "Runs: {}/{}, Changes: {}, Time: {}ms",
199            self.successful_runs, self.total_runs, self.total_changes, self.time_ms
200        )
201    }
202}
203#[allow(dead_code)]
204#[derive(Debug, Clone)]
205pub struct DCEDominatorTree {
206    pub idom: Vec<Option<u32>>,
207    pub dom_children: Vec<Vec<u32>>,
208    pub dom_depth: Vec<u32>,
209}
210impl DCEDominatorTree {
211    #[allow(dead_code)]
212    pub fn new(size: usize) -> Self {
213        DCEDominatorTree {
214            idom: vec![None; size],
215            dom_children: vec![Vec::new(); size],
216            dom_depth: vec![0; size],
217        }
218    }
219    #[allow(dead_code)]
220    pub fn set_idom(&mut self, node: usize, idom: u32) {
221        self.idom[node] = Some(idom);
222    }
223    #[allow(dead_code)]
224    pub fn dominates(&self, a: usize, b: usize) -> bool {
225        if a == b {
226            return true;
227        }
228        let mut cur = b;
229        loop {
230            match self.idom[cur] {
231                Some(parent) if parent as usize == a => return true,
232                Some(parent) if parent as usize == cur => return false,
233                Some(parent) => cur = parent as usize,
234                None => return false,
235            }
236        }
237    }
238    #[allow(dead_code)]
239    pub fn depth(&self, node: usize) -> u32 {
240        self.dom_depth.get(node).copied().unwrap_or(0)
241    }
242}
243#[allow(dead_code)]
244#[derive(Debug, Clone)]
245pub struct DCEWorklist {
246    pub(super) items: std::collections::VecDeque<u32>,
247    pub(super) in_worklist: std::collections::HashSet<u32>,
248}
249impl DCEWorklist {
250    #[allow(dead_code)]
251    pub fn new() -> Self {
252        DCEWorklist {
253            items: std::collections::VecDeque::new(),
254            in_worklist: std::collections::HashSet::new(),
255        }
256    }
257    #[allow(dead_code)]
258    pub fn push(&mut self, item: u32) -> bool {
259        if self.in_worklist.insert(item) {
260            self.items.push_back(item);
261            true
262        } else {
263            false
264        }
265    }
266    #[allow(dead_code)]
267    pub fn pop(&mut self) -> Option<u32> {
268        let item = self.items.pop_front()?;
269        self.in_worklist.remove(&item);
270        Some(item)
271    }
272    #[allow(dead_code)]
273    pub fn is_empty(&self) -> bool {
274        self.items.is_empty()
275    }
276    #[allow(dead_code)]
277    pub fn len(&self) -> usize {
278        self.items.len()
279    }
280    #[allow(dead_code)]
281    pub fn contains(&self, item: u32) -> bool {
282        self.in_worklist.contains(&item)
283    }
284}
285/// Accumulated statistics for a DCE run.
286#[derive(Debug, Clone, Default)]
287pub struct DceStats {
288    /// Number of dead let-bindings removed.
289    pub lets_eliminated: usize,
290    /// Number of unreachable case alternatives removed.
291    pub alts_eliminated: usize,
292    /// Number of constant values propagated (and let removed).
293    pub constants_propagated: usize,
294    /// Number of copy bindings propagated (and let removed).
295    pub copies_propagated: usize,
296    /// Number of unreachable function declarations removed.
297    pub functions_eliminated: usize,
298    /// Total number of fixed-point iterations executed.
299    pub iterations: usize,
300}
301impl DceStats {
302    /// Total number of transformations applied.
303    pub fn total_changes(&self) -> usize {
304        self.lets_eliminated
305            + self.alts_eliminated
306            + self.constants_propagated
307            + self.copies_propagated
308            + self.functions_eliminated
309    }
310    /// Merge the statistics from `other` into `self`.
311    pub(super) fn merge(&mut self, other: &DceStats) {
312        self.lets_eliminated += other.lets_eliminated;
313        self.alts_eliminated += other.alts_eliminated;
314        self.constants_propagated += other.constants_propagated;
315        self.copies_propagated += other.copies_propagated;
316        self.functions_eliminated += other.functions_eliminated;
317    }
318}
319#[allow(dead_code)]
320#[derive(Debug, Clone)]
321pub struct DCELivenessInfo {
322    pub live_in: Vec<std::collections::HashSet<u32>>,
323    pub live_out: Vec<std::collections::HashSet<u32>>,
324    pub defs: Vec<std::collections::HashSet<u32>>,
325    pub uses: Vec<std::collections::HashSet<u32>>,
326}
327impl DCELivenessInfo {
328    #[allow(dead_code)]
329    pub fn new(block_count: usize) -> Self {
330        DCELivenessInfo {
331            live_in: vec![std::collections::HashSet::new(); block_count],
332            live_out: vec![std::collections::HashSet::new(); block_count],
333            defs: vec![std::collections::HashSet::new(); block_count],
334            uses: vec![std::collections::HashSet::new(); block_count],
335        }
336    }
337    #[allow(dead_code)]
338    pub fn add_def(&mut self, block: usize, var: u32) {
339        if block < self.defs.len() {
340            self.defs[block].insert(var);
341        }
342    }
343    #[allow(dead_code)]
344    pub fn add_use(&mut self, block: usize, var: u32) {
345        if block < self.uses.len() {
346            self.uses[block].insert(var);
347        }
348    }
349    #[allow(dead_code)]
350    pub fn is_live_in(&self, block: usize, var: u32) -> bool {
351        self.live_in
352            .get(block)
353            .map(|s| s.contains(&var))
354            .unwrap_or(false)
355    }
356    #[allow(dead_code)]
357    pub fn is_live_out(&self, block: usize, var: u32) -> bool {
358        self.live_out
359            .get(block)
360            .map(|s| s.contains(&var))
361            .unwrap_or(false)
362    }
363}
364/// A known constant value discovered during analysis.
365///
366/// This forms a simple two-level lattice:
367///   Unknown  (top -- we know nothing)
368///      |
369///   Lit / Ctor  (known concrete value)
370#[derive(Debug, Clone, PartialEq, Eq)]
371pub enum ConstValue {
372    /// A literal constant (nat or string).
373    Lit(LcnfLit),
374    /// A fully applied constructor with known tag and arguments.
375    Ctor(String, u32, Vec<LcnfArg>),
376    /// Value is not statically known.
377    Unknown,
378}
379impl ConstValue {
380    /// Returns `true` if the value is statically known (not Unknown).
381    pub fn is_known(&self) -> bool {
382        !matches!(self, ConstValue::Unknown)
383    }
384    /// Attempt to extract a literal from the const value.
385    pub fn as_lit(&self) -> Option<&LcnfLit> {
386        match self {
387            ConstValue::Lit(l) => Some(l),
388            _ => None,
389        }
390    }
391    /// Attempt to extract constructor info from the const value.
392    pub fn as_ctor(&self) -> Option<(&str, u32, &[LcnfArg])> {
393        match self {
394            ConstValue::Ctor(name, tag, args) => Some((name.as_str(), *tag, args.as_slice())),
395            _ => None,
396        }
397    }
398}
399#[allow(dead_code)]
400#[derive(Debug, Clone)]
401pub struct DCEAnalysisCache {
402    pub(super) entries: std::collections::HashMap<String, DCECacheEntry>,
403    pub(super) max_size: usize,
404    pub(super) hits: u64,
405    pub(super) misses: u64,
406}
407impl DCEAnalysisCache {
408    #[allow(dead_code)]
409    pub fn new(max_size: usize) -> Self {
410        DCEAnalysisCache {
411            entries: std::collections::HashMap::new(),
412            max_size,
413            hits: 0,
414            misses: 0,
415        }
416    }
417    #[allow(dead_code)]
418    pub fn get(&mut self, key: &str) -> Option<&DCECacheEntry> {
419        if self.entries.contains_key(key) {
420            self.hits += 1;
421            self.entries.get(key)
422        } else {
423            self.misses += 1;
424            None
425        }
426    }
427    #[allow(dead_code)]
428    pub fn insert(&mut self, key: String, data: Vec<u8>) {
429        if self.entries.len() >= self.max_size {
430            if let Some(oldest) = self.entries.keys().next().cloned() {
431                self.entries.remove(&oldest);
432            }
433        }
434        self.entries.insert(
435            key.clone(),
436            DCECacheEntry {
437                key,
438                data,
439                timestamp: 0,
440                valid: true,
441            },
442        );
443    }
444    #[allow(dead_code)]
445    pub fn invalidate(&mut self, key: &str) {
446        if let Some(entry) = self.entries.get_mut(key) {
447            entry.valid = false;
448        }
449    }
450    #[allow(dead_code)]
451    pub fn clear(&mut self) {
452        self.entries.clear();
453    }
454    #[allow(dead_code)]
455    pub fn hit_rate(&self) -> f64 {
456        let total = self.hits + self.misses;
457        if total == 0 {
458            return 0.0;
459        }
460        self.hits as f64 / total as f64
461    }
462    #[allow(dead_code)]
463    pub fn size(&self) -> usize {
464        self.entries.len()
465    }
466}
467/// Configuration knobs for the DCE pipeline.
468#[derive(Debug, Clone)]
469pub struct DceConfig {
470    /// Eliminate unused let-bindings.
471    pub eliminate_unused_lets: bool,
472    /// Eliminate case alternatives that are statically unreachable.
473    pub eliminate_unreachable_alts: bool,
474    /// Propagate literal constants through let-bindings.
475    pub propagate_constants: bool,
476    /// Propagate copies (`let x = y`) by substituting `y` for `x`.
477    pub propagate_copies: bool,
478    /// Fold case expressions whose scrutinee is a known constructor.
479    pub fold_known_calls: bool,
480    /// Maximum number of fixed-point iterations.
481    pub max_iterations: usize,
482}
483#[allow(dead_code)]
484#[derive(Debug, Clone)]
485pub struct DCEDepGraph {
486    pub(super) nodes: Vec<u32>,
487    pub(super) edges: Vec<(u32, u32)>,
488}
489impl DCEDepGraph {
490    #[allow(dead_code)]
491    pub fn new() -> Self {
492        DCEDepGraph {
493            nodes: Vec::new(),
494            edges: Vec::new(),
495        }
496    }
497    #[allow(dead_code)]
498    pub fn add_node(&mut self, id: u32) {
499        if !self.nodes.contains(&id) {
500            self.nodes.push(id);
501        }
502    }
503    #[allow(dead_code)]
504    pub fn add_dep(&mut self, dep: u32, dependent: u32) {
505        self.add_node(dep);
506        self.add_node(dependent);
507        self.edges.push((dep, dependent));
508    }
509    #[allow(dead_code)]
510    pub fn dependents_of(&self, node: u32) -> Vec<u32> {
511        self.edges
512            .iter()
513            .filter(|(d, _)| *d == node)
514            .map(|(_, dep)| *dep)
515            .collect()
516    }
517    #[allow(dead_code)]
518    pub fn dependencies_of(&self, node: u32) -> Vec<u32> {
519        self.edges
520            .iter()
521            .filter(|(_, dep)| *dep == node)
522            .map(|(d, _)| *d)
523            .collect()
524    }
525    #[allow(dead_code)]
526    pub fn topological_sort(&self) -> Vec<u32> {
527        let mut in_degree: std::collections::HashMap<u32, u32> = std::collections::HashMap::new();
528        for &n in &self.nodes {
529            in_degree.insert(n, 0);
530        }
531        for (_, dep) in &self.edges {
532            *in_degree.entry(*dep).or_insert(0) += 1;
533        }
534        let mut queue: std::collections::VecDeque<u32> = self
535            .nodes
536            .iter()
537            .filter(|&&n| in_degree[&n] == 0)
538            .copied()
539            .collect();
540        let mut result = Vec::new();
541        while let Some(node) = queue.pop_front() {
542            result.push(node);
543            for dep in self.dependents_of(node) {
544                let cnt = in_degree.entry(dep).or_insert(0);
545                *cnt = cnt.saturating_sub(1);
546                if *cnt == 0 {
547                    queue.push_back(dep);
548                }
549            }
550        }
551        result
552    }
553    #[allow(dead_code)]
554    pub fn has_cycle(&self) -> bool {
555        self.topological_sort().len() < self.nodes.len()
556    }
557}
558#[allow(dead_code)]
559pub struct DCEConstantFoldingHelper;
560impl DCEConstantFoldingHelper {
561    #[allow(dead_code)]
562    pub fn fold_add_i64(a: i64, b: i64) -> Option<i64> {
563        a.checked_add(b)
564    }
565    #[allow(dead_code)]
566    pub fn fold_sub_i64(a: i64, b: i64) -> Option<i64> {
567        a.checked_sub(b)
568    }
569    #[allow(dead_code)]
570    pub fn fold_mul_i64(a: i64, b: i64) -> Option<i64> {
571        a.checked_mul(b)
572    }
573    #[allow(dead_code)]
574    pub fn fold_div_i64(a: i64, b: i64) -> Option<i64> {
575        if b == 0 {
576            None
577        } else {
578            a.checked_div(b)
579        }
580    }
581    #[allow(dead_code)]
582    pub fn fold_add_f64(a: f64, b: f64) -> f64 {
583        a + b
584    }
585    #[allow(dead_code)]
586    pub fn fold_mul_f64(a: f64, b: f64) -> f64 {
587        a * b
588    }
589    #[allow(dead_code)]
590    pub fn fold_neg_i64(a: i64) -> Option<i64> {
591        a.checked_neg()
592    }
593    #[allow(dead_code)]
594    pub fn fold_not_bool(a: bool) -> bool {
595        !a
596    }
597    #[allow(dead_code)]
598    pub fn fold_and_bool(a: bool, b: bool) -> bool {
599        a && b
600    }
601    #[allow(dead_code)]
602    pub fn fold_or_bool(a: bool, b: bool) -> bool {
603        a || b
604    }
605    #[allow(dead_code)]
606    pub fn fold_shl_i64(a: i64, b: u32) -> Option<i64> {
607        a.checked_shl(b)
608    }
609    #[allow(dead_code)]
610    pub fn fold_shr_i64(a: i64, b: u32) -> Option<i64> {
611        a.checked_shr(b)
612    }
613    #[allow(dead_code)]
614    pub fn fold_rem_i64(a: i64, b: i64) -> Option<i64> {
615        if b == 0 {
616            None
617        } else {
618            Some(a % b)
619        }
620    }
621    #[allow(dead_code)]
622    pub fn fold_bitand_i64(a: i64, b: i64) -> i64 {
623        a & b
624    }
625    #[allow(dead_code)]
626    pub fn fold_bitor_i64(a: i64, b: i64) -> i64 {
627        a | b
628    }
629    #[allow(dead_code)]
630    pub fn fold_bitxor_i64(a: i64, b: i64) -> i64 {
631        a ^ b
632    }
633    #[allow(dead_code)]
634    pub fn fold_bitnot_i64(a: i64) -> i64 {
635        !a
636    }
637}
oxilean_codegen/opt_dce/types.rs

oxilean_codegen/opt_dce/
types.rs
