cairo_lang_lowering/borrow_check/
analysis.rs

1//! This module introduced 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::{
7    BlockId, FlatBlock, FlatBlockEnd, FlatLowered, MatchInfo, Statement, VarRemapping, VarUsage,
8};
9
10/// Location of a lowering statement inside a block.
11pub type StatementLocation = (BlockId, usize);
12
13/// Analyzer trait to implement for each specific analysis.
14#[allow(unused_variables)]
15pub trait Analyzer<'a> {
16    type Info: Clone;
17    fn visit_block_start(&mut self, info: &mut Self::Info, block_id: BlockId, block: &FlatBlock) {}
18    fn visit_stmt(
19        &mut self,
20        info: &mut Self::Info,
21        statement_location: StatementLocation,
22        stmt: &'a Statement,
23    ) {
24    }
25    fn visit_goto(
26        &mut self,
27        info: &mut Self::Info,
28        statement_location: StatementLocation,
29        target_block_id: BlockId,
30        remapping: &VarRemapping,
31    ) {
32    }
33    fn merge_match(
34        &mut self,
35        statement_location: StatementLocation,
36        match_info: &'a MatchInfo,
37        infos: impl Iterator<Item = Self::Info>,
38    ) -> Self::Info;
39    fn info_from_return(
40        &mut self,
41        statement_location: StatementLocation,
42        vars: &'a [VarUsage],
43    ) -> Self::Info;
44
45    /// Default `info_from_panic` implementation for post 'lower_panics' phases.
46    /// Earlier phases need to override this implementation.
47    fn info_from_panic(
48        &mut self,
49        statement_location: StatementLocation,
50        var: &VarUsage,
51    ) -> Self::Info {
52        unreachable!("Panics should have been stripped in the `lower_panics` phase.");
53    }
54}
55
56/// Main analysis type that allows traversing the flow backwards.
57pub struct BackAnalysis<'a, TAnalyzer: Analyzer<'a>> {
58    lowered: &'a FlatLowered,
59    pub analyzer: TAnalyzer,
60    block_info: HashMap<BlockId, TAnalyzer::Info>,
61}
62impl<'a, TAnalyzer: Analyzer<'a>> BackAnalysis<'a, TAnalyzer> {
63    /// Creates a new BackAnalysis instance.
64    pub fn new(lowered: &'a FlatLowered, analyzer: TAnalyzer) -> Self {
65        Self { lowered, analyzer, block_info: Default::default() }
66    }
67    /// Gets the analysis info for the entire function.
68    pub fn get_root_info(&mut self) -> TAnalyzer::Info {
69        let mut dfs_stack = vec![BlockId::root()];
70        while let Some(block_id) = dfs_stack.last() {
71            let end = &self.lowered.blocks[*block_id].end;
72            if !self.add_missing_dependency_blocks(&mut dfs_stack, end) {
73                self.calc_block_info(dfs_stack.pop().unwrap());
74            }
75        }
76        self.block_info.remove(&BlockId::root()).unwrap()
77    }
78
79    /// Gets the analysis info from the start of a block.
80    fn calc_block_info(&mut self, block_id: BlockId) {
81        let mut info = self.get_end_info(block_id);
82
83        // Go through statements backwards, and update info.
84        for (i, stmt) in self.lowered.blocks[block_id].statements.iter().enumerate().rev() {
85            let statement_location = (block_id, i);
86            self.analyzer.visit_stmt(&mut info, statement_location, stmt);
87        }
88
89        self.analyzer.visit_block_start(&mut info, block_id, &self.lowered.blocks[block_id]);
90
91        // Store result.
92        self.block_info.insert(block_id, info);
93    }
94
95    /// Adds to the DFS stack the dependent blocks that are not yet in cache - returns whether if
96    /// there are any such blocks.
97    fn add_missing_dependency_blocks(
98        &self,
99        dfs_stack: &mut Vec<BlockId>,
100        block_end: &'a FlatBlockEnd,
101    ) -> bool {
102        match block_end {
103            FlatBlockEnd::NotSet => unreachable!(),
104            FlatBlockEnd::Goto(target_block_id, _)
105                if !self.block_info.contains_key(target_block_id) =>
106            {
107                dfs_stack.push(*target_block_id);
108                true
109            }
110            FlatBlockEnd::Goto(_, _) | FlatBlockEnd::Return(..) | FlatBlockEnd::Panic(_) => false,
111            FlatBlockEnd::Match { info } => {
112                let mut missing_cache = false;
113                for arm in info.arms() {
114                    if !self.block_info.contains_key(&arm.block_id) {
115                        dfs_stack.push(arm.block_id);
116                        missing_cache = true;
117                    }
118                }
119                missing_cache
120            }
121        }
122    }
123
124    /// Gets the analysis info from the block's end onwards.
125    fn get_end_info(&mut self, block_id: BlockId) -> TAnalyzer::Info {
126        let block_end = &self.lowered.blocks[block_id].end;
127        let statement_location = (block_id, self.lowered.blocks[block_id].statements.len());
128        match block_end {
129            FlatBlockEnd::NotSet => unreachable!(),
130            FlatBlockEnd::Goto(target_block_id, remapping) => {
131                let mut info = self.block_info[target_block_id].clone();
132                self.analyzer.visit_goto(
133                    &mut info,
134                    statement_location,
135                    *target_block_id,
136                    remapping,
137                );
138                info
139            }
140            FlatBlockEnd::Return(vars, _location) => {
141                self.analyzer.info_from_return(statement_location, vars)
142            }
143            FlatBlockEnd::Panic(data) => self.analyzer.info_from_panic(statement_location, data),
144            FlatBlockEnd::Match { info } => {
145                // Can remove the block since match blocks do not merge.
146                let arm_infos =
147                    info.arms().iter().map(|arm| self.block_info.remove(&arm.block_id).unwrap());
148                self.analyzer.merge_match(statement_location, info, arm_infos)
149            }
150        }
151    }
152}
cairo_lang_lowering/borrow_check/analysis.rs

cairo_lang_lowering/borrow_check/
analysis.rs
