cairo_lang_lowering/analysis/
forward.rs

1//! Forward dataflow analysis runner.
2//!
3//! This module provides `FwdAnalysis`, which traverses the control flow graph in forward
4//! (topological) order, computing dataflow information from function entry to exits.
5use itertools::Itertools;
6
7use crate::analysis::core::{DataflowAnalyzer, Direction, Edge};
8use crate::{BlockEnd, BlockId, Lowered};
9
10/// Forward analysis runner.
11///
12/// Traverses the CFG in topological order (from entry towards exits), processing
13/// statements in forward order within each block.
14///
15/// The runner automatically handles:
16/// - Block/statement traversal via `transfer_block`
17/// - Variable remapping at gotos (via `transfer_edge`)
18/// - State distribution to match arms (via `transfer_edge`)
19/// - State joining at convergence points (via `merge`)
20pub struct ForwardDataflowAnalysis<'db, 'a, TAnalyzer: DataflowAnalyzer<'db, 'a>> {
21    lowered: &'a Lowered<'db>,
22    pub analyzer: TAnalyzer,
23    /// Number of predecessors for each block (pre-computed).
24    predecessor_counts: Vec<usize>,
25    /// Incoming edges: (source_block_id, info). Cleared when block is processed.
26    incoming: Vec<Option<TAnalyzer::Info>>,
27}
28
29impl<'db, 'a, TAnalyzer: DataflowAnalyzer<'db, 'a>> ForwardDataflowAnalysis<'db, 'a, TAnalyzer> {
30    /// Creates a new FwdAnalysis instance.
31    pub fn new(lowered: &'a Lowered<'db>, analyzer: TAnalyzer) -> Self {
32        debug_assert!(
33            TAnalyzer::DIRECTION == Direction::Forward,
34            "FwdAnalysis requires an analyzer with DIRECTION == Forward"
35        );
36        let predecessor_counts = compute_predecessor_counts(lowered);
37        let incoming = vec![None; lowered.blocks.len()];
38        Self { lowered, analyzer, predecessor_counts, incoming }
39    }
40
41    /// Runs the forward analysis and returns the exit info for each block.
42    ///
43    /// For acyclic CFGs, this processes blocks in topological order.
44    /// Returns the exit info Vec indexed by BlockId.
45    pub fn run(&mut self) -> Vec<Option<TAnalyzer::Info>> {
46        let n_blocks = self.lowered.blocks.len();
47        let mut block_info: Vec<Option<TAnalyzer::Info>> = vec![None; n_blocks];
48
49        // Root block has 0 predecessors, so it's immediately ready.
50        let root_id = BlockId::root();
51        let mut ready =
52            vec![(root_id, self.analyzer.initial_info(root_id, &self.lowered.blocks[root_id].end))];
53
54        while let Some((block_id, mut info)) = ready.pop() {
55            let block = &self.lowered.blocks[block_id];
56
57            // Process block.
58            self.analyzer.visit_block_start(&mut info, block_id, block);
59            self.analyzer.transfer_block(&mut info, block_id, block);
60
61            // Transfer to successors and check readiness.
62            self.propagate_to_successors(block_id, &info, &mut ready);
63            block_info[block_id.0] = Some(info);
64        }
65        assert!(
66            self.incoming.iter().all(Option::is_none),
67            "Post run, there should be no-incoming. Actual: {:?}",
68            self.incoming.iter().map(Option::is_some).zip(&self.predecessor_counts).collect_vec()
69        );
70        block_info
71    }
72
73    /// Propagate info to all successors and mark them ready if all predecessors are done.
74    fn propagate_to_successors(
75        &mut self,
76        block_id: BlockId,
77        info: &TAnalyzer::Info,
78        ready: &mut Vec<(BlockId, TAnalyzer::Info)>,
79    ) {
80        let block = &self.lowered.blocks[block_id];
81        match &block.end {
82            BlockEnd::Goto(target, remapping) => {
83                let edge = Edge::Goto { target: *target, remapping };
84                let target_info = self.analyzer.transfer_edge(info, &edge);
85                self.add_and_maybe_ready(*target, target_info, ready);
86            }
87            BlockEnd::Match { info: match_info } => {
88                for arm in match_info.arms() {
89                    let edge = Edge::MatchArm { arm, match_info };
90                    let arm_info = self.analyzer.transfer_edge(info, &edge);
91                    self.add_and_maybe_ready(arm.block_id, arm_info, ready);
92                }
93            }
94            BlockEnd::Return(..) | BlockEnd::Panic(_) => {
95                // Terminal blocks, no successors.
96            }
97            BlockEnd::NotSet => unreachable!("Block end not set"),
98        }
99    }
100
101    /// Add incoming info and mark target ready if all predecessors have contributed.
102    ///
103    /// When multiple predecessors contribute to a block, their info is merged.
104    fn add_and_maybe_ready(
105        &mut self,
106        target: BlockId,
107        info: TAnalyzer::Info,
108        ready: &mut Vec<(BlockId, TAnalyzer::Info)>,
109    ) {
110        let merged_info = match self.incoming[target.0].take() {
111            Some(existing) => self.analyzer.merge(self.lowered, (target, 0), existing, info),
112            None => info,
113        };
114
115        self.predecessor_counts[target.0] -= 1;
116        if self.predecessor_counts[target.0] == 0 {
117            ready.push((target, merged_info));
118        } else {
119            self.incoming[target.0] = Some(merged_info);
120        }
121    }
122}
123
124/// Computes the number of predecessors for each block.
125fn compute_predecessor_counts(lowered: &Lowered<'_>) -> Vec<usize> {
126    let n_blocks = lowered.blocks.len();
127    let mut counts = vec![0usize; n_blocks];
128
129    let mut stack = vec![BlockId::root()];
130    while let Some(b) = stack.pop() {
131        let mut handle_target = |target: BlockId| {
132            if counts[target.0] == 0 {
133                stack.push(target);
134            }
135            counts[target.0] += 1;
136        };
137        match &lowered.blocks[b].end {
138            BlockEnd::Goto(target, _) => handle_target(*target),
139            BlockEnd::Match { info } => {
140                info.arms().iter().for_each(|arm| handle_target(arm.block_id));
141            }
142            BlockEnd::Return(..) | BlockEnd::Panic(_) | BlockEnd::NotSet => {}
143        }
144    }
145
146    counts
147}
cairo_lang_lowering/analysis/forward.rs

cairo_lang_lowering/analysis/
forward.rs
