rapx/graphs/
scc.rs

1//! Shared strongly-connected-component utilities.
2//!
3//! This module provides the small Tarjan SCC abstraction used by RAPx analyses
4//! and by the verification path extractor. The trait is intentionally graph
5//! agnostic: clients provide successor queries and receive each discovered SCC
6//! through `on_scc_found`.
7
8use crate::compat::{FxHashMap, FxHashSet};
9use rustc_middle::mir::BasicBlock;
10use std::cmp;
11
12/// An outgoing edge from an SCC body to a block outside the SCC.
13#[derive(Debug, Clone, Eq, Hash, PartialEq)]
14pub struct SccExit {
15    /// Legacy alias for `from` used by existing analyses.
16    pub exit: usize,
17    /// Source node inside the SCC body.
18    pub from: usize,
19    /// Destination node outside the SCC body.
20    pub to: usize,
21}
22
23impl SccExit {
24    /// Create an SCC exit edge from `from` to `to`.
25    pub fn new(from: usize, to: usize) -> Self {
26        SccExit {
27            exit: from,
28            from,
29            to,
30        }
31    }
32}
33
34/// Per-header SCC metadata used by loop-aware analyses.
35#[derive(Debug, Clone)]
36pub struct SccInfo {
37    /// SCC entry / representative block.
38    pub enter: usize,
39    /// SCC member set excluding `enter`.
40    pub nodes: FxHashSet<usize>,
41    /// Edges leaving the SCC.
42    pub exits: FxHashSet<SccExit>,
43    /// Edges inside the SCC region that go back to an earlier block or the representative.
44    pub backedges: Vec<(usize, usize)>,
45    /// Representative nodes of nested child SCCs.
46    pub child_sccs: Vec<usize>,
47}
48
49impl SccInfo {
50    /// Create empty SCC metadata for `enter`.
51    pub fn new(enter: usize) -> Self {
52        SccInfo {
53            enter,
54            nodes: FxHashSet::default(),
55            exits: FxHashSet::default(),
56            backedges: Vec::new(),
57            child_sccs: Vec::new(),
58        }
59    }
60
61    /// Returns `true` when this SCC contains only its representative and has no self-loop.
62    pub fn is_trivial(&self) -> bool {
63        self.nodes.is_empty() && self.backedges.is_empty()
64    }
65
66    /// Compatibility accessor for older callers.
67    pub fn enter(&self) -> usize {
68        self.enter
69    }
70}
71
72/// A cyclic SCC region specialized for MIR basic blocks.
73#[derive(Clone, Debug)]
74pub struct SccRegion {
75    /// Stable representative block used as the key for this SCC region.
76    pub representative: BasicBlock,
77    /// Blocks that belong to the SCC region.
78    pub blocks: Vec<BasicBlock>,
79    /// Edges that leave the SCC region.
80    pub exits: Vec<SccRegionExit>,
81    /// Edges inside the SCC region that go back to an earlier block or the representative.
82    pub backedges: Vec<(BasicBlock, BasicBlock)>,
83}
84
85/// An edge that leaves a detected MIR SCC region.
86#[derive(Clone, Debug)]
87pub struct SccRegionExit {
88    /// Source block inside the SCC region.
89    pub from: BasicBlock,
90    /// Destination block outside the SCC region.
91    pub to: BasicBlock,
92}
93
94/// Detect cyclic SCC regions in a MIR CFG successor graph.
95pub fn find_scc_regions(
96    successors: &[Vec<BasicBlock>],
97) -> (Vec<SccRegion>, FxHashMap<BasicBlock, BasicBlock>) {
98    let successors_usize: Vec<Vec<usize>> = successors
99        .iter()
100        .map(|nexts| nexts.iter().map(|bb| bb.as_usize()).collect())
101        .collect();
102    let components = collect_scc_components(&successors_usize);
103
104    let mut scc_regions = Vec::new();
105    let mut block_to_scc = FxHashMap::default();
106    for mut component in components {
107        component.sort_unstable();
108        let has_self_edge = component.len() == 1
109            && successors[component[0]]
110                .iter()
111                .any(|succ| succ.as_usize() == component[0]);
112        if component.len() <= 1 && !has_self_edge {
113            continue;
114        }
115
116        let representative = BasicBlock::from_usize(component[0]);
117        let block_set: FxHashSet<usize> = component.iter().copied().collect();
118        let mut exits = Vec::new();
119        let mut backedges = Vec::new();
120
121        for &block_idx in &component {
122            let block = BasicBlock::from_usize(block_idx);
123            for &succ in &successors[block_idx] {
124                let succ_idx = succ.as_usize();
125                if block_set.contains(&succ_idx) {
126                    if succ_idx <= block_idx || succ == representative {
127                        backedges.push((block, succ));
128                    }
129                } else {
130                    exits.push(SccRegionExit {
131                        from: block,
132                        to: succ,
133                    });
134                }
135            }
136        }
137
138        for &block_idx in &component {
139            block_to_scc.insert(BasicBlock::from_usize(block_idx), representative);
140        }
141
142        scc_regions.push(SccRegion {
143            representative,
144            blocks: component.into_iter().map(BasicBlock::from_usize).collect(),
145            exits,
146            backedges,
147        });
148    }
149
150    (scc_regions, block_to_scc)
151}
152
153/// Collect all SCC components from a successor graph.
154pub fn collect_scc_components(successors: &[Vec<usize>]) -> Vec<Vec<usize>> {
155    let mut collector = SccComponentCollector::new(successors.to_vec());
156    collector.find_scc();
157    collector.components
158}
159
160struct SccComponentCollector {
161    successors: Vec<Vec<usize>>,
162    components: Vec<Vec<usize>>,
163}
164
165impl SccComponentCollector {
166    fn new(successors: Vec<Vec<usize>>) -> Self {
167        Self {
168            successors,
169            components: Vec::new(),
170        }
171    }
172}
173
174/// Tarjan SCC callback trait.
175pub trait Scc {
176    /// Run SCC discovery from CFG entry block 0.
177    fn find_scc(&mut self) {
178        if self.get_size() == 0 {
179            return;
180        }
181        self.find_scc_from(0);
182    }
183
184    /// Run SCC discovery from a specific start node.
185    fn find_scc_from(&mut self, start: usize) {
186        if start >= self.get_size() {
187            return;
188        }
189        let mut stack = Vec::new();
190        let mut instack = FxHashSet::<usize>::default();
191        let mut dfn = vec![0; self.get_size()];
192        let mut low = vec![0; self.get_size()];
193        let mut time = 1;
194        self.tarjan(
195            start,
196            &mut stack,
197            &mut instack,
198            &mut dfn,
199            &mut low,
200            &mut time,
201        );
202    }
203
204    /// Callback invoked for each discovered SCC.
205    fn on_scc_found(&mut self, root: usize, scc_components: &[usize]);
206
207    /// Return outgoing successors of `root`.
208    fn get_next(&mut self, root: usize) -> FxHashSet<usize>;
209
210    /// Return the number of graph nodes.
211    fn get_size(&mut self) -> usize;
212
213    /// Recursive Tarjan traversal.
214    fn tarjan(
215        &mut self,
216        index: usize,
217        stack: &mut Vec<usize>,
218        instack: &mut FxHashSet<usize>,
219        dfn: &mut Vec<usize>,
220        low: &mut Vec<usize>,
221        time: &mut usize,
222    ) {
223        dfn[index] = *time;
224        low[index] = *time;
225        *time += 1;
226        stack.push(index);
227        instack.insert(index);
228
229        let size = self.get_size();
230        let nexts = self.get_next(index);
231        for next in nexts {
232            if next >= size {
233                continue;
234            }
235            if dfn[next] == 0 {
236                self.tarjan(next, stack, instack, dfn, low, time);
237                low[index] = cmp::min(low[index], low[next]);
238            } else if instack.contains(&next) {
239                low[index] = cmp::min(low[index], dfn[next]);
240            }
241        }
242
243        if dfn[index] == low[index] {
244            let mut component = vec![index];
245            while let Some(top) = stack.pop() {
246                instack.remove(&top);
247                if top == index {
248                    break;
249                }
250                component.push(top);
251            }
252            self.on_scc_found(index, &component);
253        }
254    }
255}
256
257impl Scc for SccComponentCollector {
258    fn on_scc_found(&mut self, _root: usize, scc_components: &[usize]) {
259        self.components.push(scc_components.to_vec());
260    }
261
262    fn get_next(&mut self, root: usize) -> FxHashSet<usize> {
263        self.successors
264            .get(root)
265            .into_iter()
266            .flat_map(|successors| successors.iter().copied())
267            .collect()
268    }
269
270    fn get_size(&mut self) -> usize {
271        self.successors.len()
272    }
273}
rapx/graphs/scc.rs

rapx/graphs/
scc.rs
