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

cairo_lang_lowering/analysis/
backward.rs
