analyssa 0.1.0

Target-agnostic SSA IR, analyses, and optimization pipeline
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

//! Loop analyzer for computing comprehensive loop information from SSA.
//!
//! This module provides the [`LoopAnalyzer`] which computes full
//! [`crate::analysis::loops::LoopInfo`] structures from an SSA function,
//! including preheaders, latches, exits, and loop type classification.
//!
//! # Architecture
//!
//! `LoopAnalyzer` is a thin convenience wrapper around the generic `detect_loops`
//! function from the `loops` module:
//!
//! 1. Constructs an `SsaCfg` from the SSA function
//! 2. Computes dominators using `algorithms::compute_dominators`
//! 3. Delegates to `detect_loops` for full loop analysis
//!
//! The separation between `LoopAnalyzer` and `detect_loops` allows the generic
//! loop detection to be used with non-SSA graph types (e.g., CIL CFGs, x86 CFGs)
//! while `LoopAnalyzer` provides a convenient SSA-specific interface.
//!
//! # Complexity
//!
//! Analysis: O(B^2) where B is the number of blocks (dominator computation
//! dominates the runtime). Loop detection is O(E * L) where E is edges and
//! L is the number of loops found.

use crate::{
    analysis::{
        cfg::SsaCfg,
        loops::{detect_loops, LoopForest},
    },
    graph::{algorithms, RootedGraph},
    ir::function::SsaFunction,
    target::Target,
};

/// Analyzes loops in an SSA function.
///
/// The analyzer computes:
/// - Natural loops using dominance-based back edge detection
/// - Preheader identification for each loop
/// - Latch (back edge source) identification
/// - Exit edge detection
/// - Loop type classification
/// - Loop nesting relationships
///
/// This is a thin wrapper around the generic `detect_loops` function,
/// providing a convenient SSA-specific interface.
pub struct LoopAnalyzer<'a, T: Target> {
    /// The SSA-based control flow graph used for dominance computation and loop detection.
    cfg: SsaCfg<'a, T>,
}

impl<'a, T: Target> LoopAnalyzer<'a, T> {
    /// Creates a new loop analyzer for the given SSA function.
    #[must_use]
    pub fn new(ssa: &'a SsaFunction<T>) -> Self {
        let cfg = SsaCfg::from_ssa(ssa);
        Self { cfg }
    }

    /// Analyzes all loops and returns a [`LoopForest`].
    ///
    /// Uses the shared `detect_loops` function which implements dominance-based
    /// back edge detection and computes preheaders, exits, loop types, and nesting.
    #[must_use]
    pub fn analyze(&self) -> LoopForest {
        let dominators = algorithms::compute_dominators(&self.cfg, self.cfg.entry());
        detect_loops(&self.cfg, &dominators)
    }
}

/// Extension trait for SSA functions to easily access loop analysis.
pub trait SsaLoopAnalysis {
    /// Analyzes loops in this function.
    fn analyze_loops(&self) -> LoopForest;
}

impl<T: Target> SsaLoopAnalysis for SsaFunction<T> {
    fn analyze_loops(&self) -> LoopForest {
        LoopAnalyzer::new(self).analyze()
    }
}