cairo_lang_lowering/analysis/
mod.rs

1//! Dataflow analysis utilities for the lowering IR.
2//!
3//! This module provides generic analysis frameworks that can be used by various
4//! optimization passes and semantic checks.
5
6pub mod backward;
7pub mod def_site;
8pub use backward::{BackAnalysis, DataflowBackAnalysis};
9
10pub mod core;
11pub use core::{DataflowAnalyzer, Direction, Edge, StatementLocation};
12
13pub mod dominator;
14pub mod equality_analysis;
15pub mod forward;
16pub mod use_sites;
17pub use forward::ForwardDataflowAnalysis;
18pub mod topological_order;
19
20#[cfg(test)]
21mod equality_analysis_test;
22#[cfg(test)]
23mod test;
24
25use crate::{Block, BlockId, MatchInfo, Statement, VarRemapping, VarUsage};
26
27/// Where a variable is defined.
28#[derive(Clone, Copy, PartialEq, Eq, Hash)]
29pub enum DefLocation {
30    /// Defined by a statement at the given location.
31    Statement(StatementLocation),
32    /// Defined at block entry (parameter, goto remapping, or match arm binding).
33    BlockEntry(BlockId),
34}
35
36impl DefLocation {
37    /// Returns the [`BlockId`] of the block in which the variable is defined.
38    pub fn block(&self) -> BlockId {
39        match *self {
40            DefLocation::Statement((b, _)) => b,
41            DefLocation::BlockEntry(b) => b,
42        }
43    }
44}
45
46impl std::fmt::Debug for DefLocation {
47    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
48        match self {
49            DefLocation::Statement((block, stmt_idx)) => write!(f, "stmt({block:?}, {stmt_idx})"),
50            DefLocation::BlockEntry(block) => write!(f, "entry({block:?})"),
51        }
52    }
53}
54
55/// Where a variable is used.
56#[derive(Clone, Copy, PartialEq, Eq, Hash)]
57pub enum UseLocation {
58    /// Used as input to a statement.
59    Statement(StatementLocation),
60    /// Used at block end (return, panic, goto, or match).
61    BlockEnd(BlockId),
62}
63
64impl UseLocation {
65    /// Returns the [`BlockId`] of the block in which the variable is used.
66    pub fn block(&self) -> BlockId {
67        match *self {
68            UseLocation::Statement((b, _)) => b,
69            UseLocation::BlockEnd(b) => b,
70        }
71    }
72}
73
74impl std::fmt::Debug for UseLocation {
75    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
76        match self {
77            UseLocation::Statement((block, stmt_idx)) => write!(f, "stmt({block:?}, {stmt_idx})"),
78            UseLocation::BlockEnd(block) => write!(f, "end({block:?})"),
79        }
80    }
81}
82
83/// Analyzer trait to implement for each specific analysis.
84#[allow(unused_variables)]
85pub trait Analyzer<'db, 'a> {
86    type Info: Clone;
87    fn visit_block_start(&mut self, info: &mut Self::Info, block_id: BlockId, block: &Block<'db>) {}
88    fn visit_stmt(
89        &mut self,
90        info: &mut Self::Info,
91        statement_location: StatementLocation,
92        stmt: &'a Statement<'db>,
93    ) {
94    }
95    fn visit_goto(
96        &mut self,
97        info: &mut Self::Info,
98        statement_location: StatementLocation,
99        target_block_id: BlockId,
100        remapping: &'a VarRemapping<'db>,
101    ) {
102    }
103    fn merge_match(
104        &mut self,
105        statement_location: StatementLocation,
106        match_info: &'a MatchInfo<'db>,
107        infos: impl Iterator<Item = Self::Info>,
108    ) -> Self::Info;
109    fn info_from_return(
110        &mut self,
111        statement_location: StatementLocation,
112        vars: &'a [VarUsage<'db>],
113    ) -> Self::Info;
114
115    /// Default `info_from_panic` implementation for post 'lower_panics' phases.
116    /// Earlier phases need to override this implementation.
117    fn info_from_panic(
118        &mut self,
119        statement_location: StatementLocation,
120        var: &VarUsage<'db>,
121    ) -> Self::Info {
122        unreachable!("Panics should have been stripped in the `lower_panics` phase.");
123    }
124}
cairo_lang_lowering/analysis/mod.rs

cairo_lang_lowering/analysis/
mod.rs
