cairo_lang_lowering/analysis/
dominator.rs

1//! Block dominator analysis for lowered IR.
2//!
3//! Computes the set of blocks that dominate each block using the forward
4//! dataflow framework. A block A dominates block B if every path from the
5//! entry block to B passes through A.
6
7use std::fmt;
8
9use cairo_lang_utils::ordered_hash_set::OrderedHashSet;
10use itertools::Itertools;
11
12use crate::analysis::core::{DataflowAnalyzer, Direction, StatementLocation};
13use crate::analysis::forward::ForwardDataflowAnalysis;
14use crate::{Block, BlockEnd, BlockId, Lowered};
15
16/// Result of dominator analysis, providing efficient dominator queries.
17pub struct Dominators {
18    /// Set of blocks that dominate `block_id` indexed by block ID.
19    per_block: Vec<OrderedHashSet<BlockId>>,
20}
21
22impl Dominators {
23    /// Runs dominator analysis on a lowered function.
24    pub fn analyze(lowered: &Lowered<'_>) -> Self {
25        let mut fwd = ForwardDataflowAnalysis::new(lowered, DominatorAnalyzer);
26        let per_block = fwd.run().into_iter().map(|opt| opt.unwrap_or_default()).collect();
27        Dominators { per_block }
28    }
29
30    /// Returns true if block `a` dominates block `b`.
31    pub fn dominates(&self, a: BlockId, b: BlockId) -> bool {
32        self.per_block[b.0].contains(&a)
33    }
34
35    /// Returns the set of dominators for the given block.
36    pub fn dominators_of(&self, block: BlockId) -> &OrderedHashSet<BlockId> {
37        &self.per_block[block.0]
38    }
39}
40
41impl fmt::Debug for Dominators {
42    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
43        let mut list = f.debug_list();
44        for (i, doms) in self.per_block.iter().enumerate() {
45            if doms.is_empty() {
46                list.entry(&format_args!("blk{i}: unreachable"));
47            } else {
48                let names = doms
49                    .iter()
50                    .map(|b| b.0)
51                    .sorted()
52                    .format_with(", ", |d, f| f(&format_args!("blk{d}")));
53                list.entry(&format_args!("blk{i}: {{{names}}}"));
54            }
55        }
56        list.finish()
57    }
58}
59
60/// Internal forward analyzer that computes dominator sets.
61struct DominatorAnalyzer;
62
63impl<'db, 'a> DataflowAnalyzer<'db, 'a> for DominatorAnalyzer {
64    type Info = OrderedHashSet<BlockId>;
65    const DIRECTION: Direction = Direction::Forward;
66
67    fn initial_info(&mut self, _block_id: BlockId, _block_end: &'a BlockEnd<'db>) -> Self::Info {
68        OrderedHashSet::default()
69    }
70
71    fn merge(
72        &mut self,
73        _lowered: &Lowered<'db>,
74        _statement_location: StatementLocation,
75        info1: Self::Info,
76        info2: Self::Info,
77    ) -> Self::Info {
78        // Dominator merge is set intersection:
79        // a block dominates B only if it dominates ALL predecessors of B.
80        let mut info1 = info1;
81        info1.retain(|id| info2.contains(id));
82        info1
83    }
84
85    fn transfer_block(&mut self, info: &mut Self::Info, block_id: BlockId, _block: &'a Block<'db>) {
86        // Every block dominates itself.
87        info.insert(block_id);
88    }
89}
90
91#[cfg(test)]
92#[path = "dominator_test.rs"]
93mod dominator_test;
cairo_lang_lowering/analysis/dominator.rs

cairo_lang_lowering/analysis/
dominator.rs
