cairo_lang_lowering/analysis/
def_site.rs

1//! Def-site analysis for lowered IR.
2//!
3//! Records where each variable is first defined as a `DefLocation`:
4//! either `BlockEntry` (parameters, goto remappings, match arm bindings)
5//! or `Statement` (output of a statement). Uses the forward analysis framework
6//! and all results are accumulated in the analyzer's global `def_sites` vector.
7
8use std::fmt;
9
10use crate::analysis::DefLocation;
11use crate::analysis::core::{DataflowAnalyzer, Direction, Edge, StatementLocation};
12use crate::analysis::forward::ForwardDataflowAnalysis;
13use crate::{BlockEnd, BlockId, Lowered, Statement};
14
15/// Result of def-site analysis: the def location for each variable, indexed by arena index.
16///
17/// Each entry is `Some(loc)` when the variable's defining block is reachable from the function
18/// entry, and `None` when it is unreachable (and therefore never visited by the analysis).
19pub struct DefSites(pub Vec<Option<DefLocation>>);
20
21impl std::ops::Deref for DefSites {
22    type Target = [Option<DefLocation>];
23    fn deref(&self) -> &Self::Target {
24        &self.0
25    }
26}
27
28impl fmt::Debug for DefSites {
29    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
30        let mut list = f.debug_list();
31        for (idx, def) in self.0.iter().enumerate() {
32            match def {
33                Some(loc) => list.entry(&format_args!("v{idx}: {loc:?}")),
34                None => list.entry(&format_args!("v{idx}: undefined")),
35            };
36        }
37        list.finish()
38    }
39}
40
41/// Forward analysis that records where each variable first becomes available.
42pub struct DefSiteAnalysis<'db, 'a> {
43    lowered: &'a Lowered<'db>,
44    /// First-available location for each variable, indexed by variable arena index.
45    /// Slots stay `None` until the traversal reaches them; slots that remain `None` correspond
46    /// to variables in unreachable blocks.
47    def_sites: Vec<Option<DefLocation>>,
48}
49
50impl DefSiteAnalysis<'_, '_> {
51    /// Runs def-site analysis on a lowered function.
52    ///
53    /// Returns a vector indexed by variable arena index, mapping each variable to the
54    /// `DefLocation` where it first becomes available:
55    /// - `BlockEntry(block)`: available at block entry (parameters, goto remappings, match arm
56    ///   bindings).
57    /// - `Statement((block, i))`: available after statement `i` in `block`.
58    /// - `None`: the variable's defining block is unreachable from the function entry.
59    pub fn analyze(lowered: &Lowered<'_>) -> DefSites {
60        let analyzer = DefSiteAnalysis { lowered, def_sites: vec![None; lowered.variables.len()] };
61        let mut fwd = ForwardDataflowAnalysis::new(lowered, analyzer);
62        fwd.run();
63        DefSites(fwd.analyzer.def_sites)
64    }
65}
66
67impl<'db, 'a> DataflowAnalyzer<'db, 'a> for DefSiteAnalysis<'db, 'a> {
68    type Info = ();
69    const DIRECTION: Direction = Direction::Forward;
70
71    fn initial_info(&mut self, _block_id: BlockId, _block_end: &'a BlockEnd<'db>) -> Self::Info {
72        for &param in &self.lowered.parameters {
73            self.def_sites[param.index()] = Some(DefLocation::BlockEntry(BlockId::root()));
74        }
75    }
76
77    fn merge(
78        &mut self,
79        _lowered: &Lowered<'db>,
80        _statement_location: StatementLocation,
81        _info1: Self::Info,
82        _info2: Self::Info,
83    ) -> Self::Info {
84    }
85
86    fn transfer_stmt(
87        &mut self,
88        _info: &mut Self::Info,
89        statement_location: StatementLocation,
90        stmt: &'a Statement<'db>,
91    ) {
92        for &output in stmt.outputs() {
93            self.def_sites[output.index()] = Some(DefLocation::Statement(statement_location));
94        }
95    }
96
97    fn transfer_edge(&mut self, _info: &Self::Info, edge: &Edge<'db, 'a>) -> Self::Info {
98        match edge {
99            Edge::Goto { target, remapping } => {
100                for (&dst, _) in remapping.iter() {
101                    self.def_sites[dst.index()] = Some(DefLocation::BlockEntry(*target));
102                }
103            }
104            Edge::MatchArm { arm, .. } => {
105                for &var in &arm.var_ids {
106                    self.def_sites[var.index()] = Some(DefLocation::BlockEntry(arm.block_id));
107                }
108            }
109            Edge::Return { .. } | Edge::Panic { .. } => {}
110        }
111    }
112}
cairo_lang_lowering/analysis/def_site.rs

cairo_lang_lowering/analysis/
def_site.rs
