cairo_lang_lowering/analysis/
backward.rs

1//! This module introduces the BackAnalysis utility that allows writing analyzers that go backwards
2//! in the flow of the program, on a Lowered representation.
3
4use crate::analysis::{Analyzer, DataflowAnalyzer, Direction, Edge, StatementLocation};
5use crate::{Block, BlockEnd, BlockId, Lowered, MatchInfo, Statement, VarRemapping, VarUsage};
6
7/// Main analysis type that allows traversing the flow backwards.
8pub struct BackAnalysis<'db, 'a, TAnalyzer: Analyzer<'db, 'a>> {
9    lowered: &'a Lowered<'db>,
10    pub analyzer: TAnalyzer,
11    block_info: Vec<Option<TAnalyzer::Info>>,
12}
13impl<'db, 'a, TAnalyzer: Analyzer<'db, 'a>> BackAnalysis<'db, 'a, TAnalyzer> {
14    /// Creates a new BackAnalysis instance.
15    pub fn new(lowered: &'a Lowered<'db>, analyzer: TAnalyzer) -> Self {
16        Self { lowered, analyzer, block_info: vec![None; lowered.blocks.len()] }
17    }
18    /// Gets the analysis info for the entire function.
19    pub fn get_root_info(&mut self) -> TAnalyzer::Info {
20        let mut dfs_stack = Vec::with_capacity(self.lowered.blocks.len());
21        dfs_stack.push(BlockId::root());
22        while let Some(block_id) = dfs_stack.last() {
23            let end = &self.lowered.blocks[*block_id].end;
24            if !self.add_missing_dependency_blocks(&mut dfs_stack, end) {
25                self.calc_block_info(dfs_stack.pop().unwrap());
26            }
27        }
28        self.block_info[BlockId::root().0].take().unwrap()
29    }
30
31    /// Gets the analysis info from the start of a block.
32    fn calc_block_info(&mut self, block_id: BlockId) {
33        let mut info = self.get_end_info(block_id);
34
35        // Go through statements backwards, and update info.
36        for (i, stmt) in self.lowered.blocks[block_id].statements.iter().enumerate().rev() {
37            let statement_location = (block_id, i);
38            self.analyzer.visit_stmt(&mut info, statement_location, stmt);
39        }
40
41        self.analyzer.visit_block_start(&mut info, block_id, &self.lowered.blocks[block_id]);
42
43        // Store result.
44        self.block_info[block_id.0] = Some(info);
45    }
46
47    /// Adds to the DFS stack the dependent blocks that are not yet in cache - returns whether
48    /// there are any such blocks.
49    fn add_missing_dependency_blocks(
50        &self,
51        dfs_stack: &mut Vec<BlockId>,
52        block_end: &'a BlockEnd<'_>,
53    ) -> bool {
54        match block_end {
55            BlockEnd::NotSet => unreachable!(),
56            BlockEnd::Goto(target_block_id, _) if self.block_info[target_block_id.0].is_none() => {
57                dfs_stack.push(*target_block_id);
58                true
59            }
60            BlockEnd::Goto(_, _) | BlockEnd::Return(..) | BlockEnd::Panic(_) => false,
61            BlockEnd::Match { info } => {
62                let mut missing_cache = false;
63                for arm in info.arms() {
64                    if self.block_info[arm.block_id.0].is_none() {
65                        dfs_stack.push(arm.block_id);
66                        missing_cache = true;
67                    }
68                }
69                missing_cache
70            }
71        }
72    }
73
74    /// Gets the analysis info from the block's end onwards.
75    fn get_end_info(&mut self, block_id: BlockId) -> TAnalyzer::Info {
76        let block_end = &self.lowered.blocks[block_id].end;
77        let statement_location = (block_id, self.lowered.blocks[block_id].statements.len());
78        match block_end {
79            BlockEnd::NotSet => unreachable!(),
80            BlockEnd::Goto(target_block_id, remapping) => {
81                let mut info = self.block_info[target_block_id.0].clone().unwrap();
82                self.analyzer.visit_goto(
83                    &mut info,
84                    statement_location,
85                    *target_block_id,
86                    remapping,
87                );
88                info
89            }
90            BlockEnd::Return(vars, _location) => {
91                self.analyzer.info_from_return(statement_location, vars)
92            }
93            BlockEnd::Panic(data) => self.analyzer.info_from_panic(statement_location, data),
94            BlockEnd::Match { info } => {
95                // Can remove the block since match blocks do not merge.
96                let arm_infos =
97                    info.arms().iter().map(|arm| self.block_info[arm.block_id.0].take().unwrap());
98                self.analyzer.merge_match(statement_location, info, arm_infos)
99            }
100        }
101    }
102}
103
104/// Backward analysis runner using `DataflowAnalyzer`.
105///
106/// This is an adapter that wraps `BackAnalysis` internally, translating
107/// between the new `DataflowAnalyzer` trait and the legacy `Analyzer` trait.
108/// Once all analyses are migrated, this can be simplified to inline the
109/// traversal logic directly.
110pub struct DataflowBackAnalysis<'db, 'a, TAnalyzer: DataflowAnalyzer<'db, 'a>> {
111    inner: BackAnalysis<'db, 'a, AnalyzerAdapter<'db, 'a, TAnalyzer>>,
112}
113
114impl<'db, 'a, TAnalyzer: DataflowAnalyzer<'db, 'a>> DataflowBackAnalysis<'db, 'a, TAnalyzer> {
115    /// Creates a new DataflowBackAnalysis instance.
116    pub fn new(lowered: &'a Lowered<'db>, analyzer: &'a mut TAnalyzer) -> Self {
117        assert!(
118            TAnalyzer::DIRECTION == Direction::Backward,
119            "DataflowBackAnalysis requires a backward analyzer"
120        );
121        let adapter = AnalyzerAdapter { analyzer, lowered };
122        Self { inner: BackAnalysis::new(lowered, adapter) }
123    }
124
125    /// Runs the analysis and returns the result.
126    ///
127    /// For backward analysis, returns the info at the start of each block.
128    pub fn run(mut self) -> TAnalyzer::Info {
129        self.inner.get_root_info()
130    }
131}
132
133/// Adapter that implements the legacy `Analyzer` trait by delegating to `DataflowAnalyzer`.
134pub struct AnalyzerAdapter<'db, 'a, TAnalyzer: DataflowAnalyzer<'db, 'a>> {
135    pub analyzer: &'a mut TAnalyzer,
136    lowered: &'a Lowered<'db>,
137}
138
139impl<'db, 'a, TAnalyzer: DataflowAnalyzer<'db, 'a>> Analyzer<'db, 'a>
140    for AnalyzerAdapter<'db, 'a, TAnalyzer>
141{
142    type Info = TAnalyzer::Info;
143
144    fn visit_block_start(&mut self, info: &mut Self::Info, block_id: BlockId, _block: &Block<'db>) {
145        // Get block from lowered with correct lifetime 'a.
146        let block = &self.lowered.blocks[block_id];
147        // First apply transfer_block (which processes statements in reverse for backward).
148        self.analyzer.transfer_block(info, block_id, block);
149        // Then call the block start hook.
150        self.analyzer.visit_block_start(info, block_id, block);
151    }
152
153    fn visit_stmt(
154        &mut self,
155        _info: &mut Self::Info,
156        _statement_location: StatementLocation,
157        _stmt: &'a Statement<'db>,
158    ) {
159        // Statements are handled by transfer_block in visit_block_start.
160        // This is intentionally empty.
161    }
162
163    fn visit_goto(
164        &mut self,
165        info: &mut Self::Info,
166        _statement_location: StatementLocation,
167        target_block_id: BlockId,
168        remapping: &'a VarRemapping<'db>,
169    ) {
170        let edge = Edge::Goto { target: target_block_id, remapping };
171        *info = self.analyzer.transfer_edge(info, &edge);
172    }
173
174    fn merge_match(
175        &mut self,
176        statement_location: StatementLocation,
177        match_info: &'a MatchInfo<'db>,
178        infos: impl Iterator<Item = Self::Info>,
179    ) -> Self::Info {
180        // Transfer each arm's info through its edge, then merge.
181        let mut iter = match_info.arms().iter().zip(infos);
182        let transformer = |analyzer: &mut TAnalyzer, info, arm| {
183            let edge = Edge::MatchArm { arm, match_info };
184            analyzer.transfer_edge(&info, &edge)
185        };
186        let Some(first) = iter.next().map(|(arm, info)| transformer(self.analyzer, info, arm))
187        else {
188            return self.analyzer.initial_info(
189                statement_location.0,
190                &self.lowered.blocks[statement_location.0].end,
191            );
192        };
193        iter.fold(first, |a, b| {
194            let b = transformer(self.analyzer, b.1, b.0);
195            self.analyzer.merge(self.lowered, statement_location, a, b)
196        })
197    }
198
199    fn info_from_return(
200        &mut self,
201        statement_location: StatementLocation,
202        vars: &'a [VarUsage<'db>],
203    ) -> Self::Info {
204        let block_end = &self.lowered.blocks[statement_location.0].end;
205        let BlockEnd::Return(_, location) = block_end else {
206            unreachable!("Unexpected block end type")
207        };
208        let location = *location;
209        let info = self.analyzer.initial_info(statement_location.0, block_end);
210        self.analyzer.transfer_edge(&info, &Edge::Return { vars, location })
211    }
212
213    fn info_from_panic(
214        &mut self,
215        statement_location: StatementLocation,
216        var: &VarUsage<'db>,
217    ) -> Self::Info {
218        let block_end = &self.lowered.blocks[statement_location.0].end;
219        let info = self.analyzer.initial_info(statement_location.0, block_end);
220        self.analyzer.transfer_edge(&info, &Edge::Panic { var: *var })
221    }
222}
cairo_lang_lowering/analysis/backward.rs

cairo_lang_lowering/analysis/
backward.rs
