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

cairo_lang_lowering/analysis/
backward.rs
