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

cairo_lang_lowering/analysis/
forward.rs
