rustc_mir_transform/coverage/
graph.rs

1use std::cmp::Ordering;
2use std::ops::{Index, IndexMut};
3use std::{mem, slice};
4
5use rustc_data_structures::fx::FxHashSet;
6use rustc_data_structures::graph::dominators::Dominators;
7use rustc_data_structures::graph::{self, DirectedGraph, StartNode};
8use rustc_index::IndexVec;
9use rustc_index::bit_set::DenseBitSet;
10pub(crate) use rustc_middle::mir::coverage::{BasicCoverageBlock, START_BCB};
11use rustc_middle::mir::{self, BasicBlock, Terminator, TerminatorKind};
12use tracing::debug;
13
14/// A coverage-specific simplification of the MIR control flow graph (CFG). The `CoverageGraph`s
15/// nodes are `BasicCoverageBlock`s, which encompass one or more MIR `BasicBlock`s.
16#[derive(Debug)]
17pub(crate) struct CoverageGraph {
18    bcbs: IndexVec<BasicCoverageBlock, BasicCoverageBlockData>,
19    bb_to_bcb: IndexVec<BasicBlock, Option<BasicCoverageBlock>>,
20    pub(crate) successors: IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>>,
21    pub(crate) predecessors: IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>>,
22
23    dominators: Option<Dominators<BasicCoverageBlock>>,
24    /// Allows nodes to be compared in some total order such that _if_
25    /// `a` dominates `b`, then `a < b`. If neither node dominates the other,
26    /// their relative order is consistent but arbitrary.
27    dominator_order_rank: IndexVec<BasicCoverageBlock, u32>,
28    /// A loop header is a node that dominates one or more of its predecessors.
29    is_loop_header: DenseBitSet<BasicCoverageBlock>,
30    /// For each node, the loop header node of its nearest enclosing loop.
31    /// This forms a linked list that can be traversed to find all enclosing loops.
32    enclosing_loop_header: IndexVec<BasicCoverageBlock, Option<BasicCoverageBlock>>,
33}
34
35impl CoverageGraph {
36    pub(crate) fn from_mir(mir_body: &mir::Body<'_>) -> Self {
37        let (bcbs, bb_to_bcb) = Self::compute_basic_coverage_blocks(mir_body);
38
39        // Pre-transform MIR `BasicBlock` successors and predecessors into the BasicCoverageBlock
40        // equivalents. Note that since the BasicCoverageBlock graph has been fully simplified, the
41        // each predecessor of a BCB leader_bb should be in a unique BCB. It is possible for a
42        // `SwitchInt` to have multiple targets to the same destination `BasicBlock`, so
43        // de-duplication is required. This is done without reordering the successors.
44
45        let successors = IndexVec::<BasicCoverageBlock, _>::from_fn_n(
46            |bcb| {
47                let mut seen_bcbs = FxHashSet::default();
48                let terminator = mir_body[bcbs[bcb].last_bb()].terminator();
49                bcb_filtered_successors(terminator)
50                    .into_iter()
51                    .filter_map(|successor_bb| bb_to_bcb[successor_bb])
52                    // Remove duplicate successor BCBs, keeping only the first.
53                    .filter(|&successor_bcb| seen_bcbs.insert(successor_bcb))
54                    .collect::<Vec<_>>()
55            },
56            bcbs.len(),
57        );
58
59        let mut predecessors = IndexVec::from_elem(Vec::new(), &bcbs);
60        for (bcb, bcb_successors) in successors.iter_enumerated() {
61            for &successor in bcb_successors {
62                predecessors[successor].push(bcb);
63            }
64        }
65
66        let num_nodes = bcbs.len();
67        let mut this = Self {
68            bcbs,
69            bb_to_bcb,
70            successors,
71            predecessors,
72            dominators: None,
73            dominator_order_rank: IndexVec::from_elem_n(0, num_nodes),
74            is_loop_header: DenseBitSet::new_empty(num_nodes),
75            enclosing_loop_header: IndexVec::from_elem_n(None, num_nodes),
76        };
77        assert_eq!(num_nodes, this.num_nodes());
78
79        // Set the dominators first, because later init steps rely on them.
80        this.dominators = Some(graph::dominators::dominators(&this));
81
82        // Iterate over all nodes, such that dominating nodes are visited before
83        // the nodes they dominate. Either preorder or reverse postorder is fine.
84        let dominator_order = graph::iterate::reverse_post_order(&this, this.start_node());
85        // The coverage graph is created by traversal, so all nodes are reachable.
86        assert_eq!(dominator_order.len(), this.num_nodes());
87        for (rank, bcb) in (0u32..).zip(dominator_order) {
88            // The dominator rank of each node is its index in a dominator-order traversal.
89            this.dominator_order_rank[bcb] = rank;
90
91            // A node is a loop header if it dominates any of its predecessors.
92            if this.reloop_predecessors(bcb).next().is_some() {
93                this.is_loop_header.insert(bcb);
94            }
95
96            // If the immediate dominator is a loop header, that's our enclosing loop.
97            // Otherwise, inherit the immediate dominator's enclosing loop.
98            // (Dominator order ensures that we already processed the dominator.)
99            if let Some(dom) = this.dominators().immediate_dominator(bcb) {
100                this.enclosing_loop_header[bcb] = this
101                    .is_loop_header
102                    .contains(dom)
103                    .then_some(dom)
104                    .or_else(|| this.enclosing_loop_header[dom]);
105            }
106        }
107
108        // The coverage graph's entry-point node (bcb0) always starts with bb0,
109        // which never has predecessors. Any other blocks merged into bcb0 can't
110        // have multiple (coverage-relevant) predecessors, so bcb0 always has
111        // zero in-edges.
112        assert!(this[START_BCB].leader_bb() == mir::START_BLOCK);
113        assert!(this.predecessors[START_BCB].is_empty());
114
115        this
116    }
117
118    fn compute_basic_coverage_blocks(
119        mir_body: &mir::Body<'_>,
120    ) -> (
121        IndexVec<BasicCoverageBlock, BasicCoverageBlockData>,
122        IndexVec<BasicBlock, Option<BasicCoverageBlock>>,
123    ) {
124        let num_basic_blocks = mir_body.basic_blocks.len();
125        let mut bcbs = IndexVec::<BasicCoverageBlock, _>::with_capacity(num_basic_blocks);
126        let mut bb_to_bcb = IndexVec::from_elem_n(None, num_basic_blocks);
127
128        let mut flush_chain_into_new_bcb = |current_chain: &mut Vec<BasicBlock>| {
129            // Take the accumulated list of blocks, leaving the vector empty
130            // to be used by subsequent BCBs.
131            let basic_blocks = mem::take(current_chain);
132
133            let bcb = bcbs.next_index();
134            for &bb in basic_blocks.iter() {
135                bb_to_bcb[bb] = Some(bcb);
136            }
137
138            let is_out_summable = basic_blocks.last().is_some_and(|&bb| {
139                bcb_filtered_successors(mir_body[bb].terminator()).is_out_summable()
140            });
141            let bcb_data = BasicCoverageBlockData { basic_blocks, is_out_summable };
142            debug!("adding {bcb:?}: {bcb_data:?}");
143            bcbs.push(bcb_data);
144        };
145
146        // Traverse the MIR control-flow graph, accumulating chains of blocks
147        // that can be combined into a single node in the coverage graph.
148        // A depth-first search ensures that if two nodes can be chained
149        // together, they will be adjacent in the traversal order.
150
151        // Accumulates a chain of blocks that will be combined into one BCB.
152        let mut current_chain = vec![];
153
154        let subgraph = CoverageRelevantSubgraph::new(&mir_body.basic_blocks);
155        for bb in graph::depth_first_search(subgraph, mir::START_BLOCK)
156            .filter(|&bb| mir_body[bb].terminator().kind != TerminatorKind::Unreachable)
157        {
158            if let Some(&prev) = current_chain.last() {
159                // Adding a block to a non-empty chain is allowed if the
160                // previous block permits chaining, and the current block has
161                // `prev` as its sole predecessor.
162                let can_chain = subgraph.coverage_successors(prev).is_out_chainable()
163                    && mir_body.basic_blocks.predecessors()[bb].as_slice() == &[prev];
164                if !can_chain {
165                    // The current block can't be added to the existing chain, so
166                    // flush that chain into a new BCB, and start a new chain.
167                    flush_chain_into_new_bcb(&mut current_chain);
168                }
169            }
170
171            current_chain.push(bb);
172        }
173
174        if !current_chain.is_empty() {
175            debug!("flushing accumulated blocks into one last BCB");
176            flush_chain_into_new_bcb(&mut current_chain);
177        }
178
179        (bcbs, bb_to_bcb)
180    }
181
182    #[inline(always)]
183    pub(crate) fn iter_enumerated(
184        &self,
185    ) -> impl Iterator<Item = (BasicCoverageBlock, &BasicCoverageBlockData)> {
186        self.bcbs.iter_enumerated()
187    }
188
189    #[inline(always)]
190    pub(crate) fn bcb_from_bb(&self, bb: BasicBlock) -> Option<BasicCoverageBlock> {
191        if bb.index() < self.bb_to_bcb.len() { self.bb_to_bcb[bb] } else { None }
192    }
193
194    #[inline(always)]
195    fn dominators(&self) -> &Dominators<BasicCoverageBlock> {
196        self.dominators.as_ref().unwrap()
197    }
198
199    #[inline(always)]
200    pub(crate) fn dominates(&self, dom: BasicCoverageBlock, node: BasicCoverageBlock) -> bool {
201        self.dominators().dominates(dom, node)
202    }
203
204    #[inline(always)]
205    pub(crate) fn cmp_in_dominator_order(
206        &self,
207        a: BasicCoverageBlock,
208        b: BasicCoverageBlock,
209    ) -> Ordering {
210        self.dominator_order_rank[a].cmp(&self.dominator_order_rank[b])
211    }
212
213    /// For the given node, yields the subset of its predecessor nodes that
214    /// it dominates. If that subset is non-empty, the node is a "loop header",
215    /// and each of those predecessors represents an in-edge that jumps back to
216    /// the top of its loop.
217    pub(crate) fn reloop_predecessors(
218        &self,
219        to_bcb: BasicCoverageBlock,
220    ) -> impl Iterator<Item = BasicCoverageBlock> {
221        self.predecessors[to_bcb].iter().copied().filter(move |&pred| self.dominates(to_bcb, pred))
222    }
223}
224
225impl Index<BasicCoverageBlock> for CoverageGraph {
226    type Output = BasicCoverageBlockData;
227
228    #[inline]
229    fn index(&self, index: BasicCoverageBlock) -> &BasicCoverageBlockData {
230        &self.bcbs[index]
231    }
232}
233
234impl IndexMut<BasicCoverageBlock> for CoverageGraph {
235    #[inline]
236    fn index_mut(&mut self, index: BasicCoverageBlock) -> &mut BasicCoverageBlockData {
237        &mut self.bcbs[index]
238    }
239}
240
241impl graph::DirectedGraph for CoverageGraph {
242    type Node = BasicCoverageBlock;
243
244    #[inline]
245    fn num_nodes(&self) -> usize {
246        self.bcbs.len()
247    }
248}
249
250impl graph::StartNode for CoverageGraph {
251    #[inline]
252    fn start_node(&self) -> Self::Node {
253        self.bcb_from_bb(mir::START_BLOCK)
254            .expect("mir::START_BLOCK should be in a BasicCoverageBlock")
255    }
256}
257
258impl graph::Successors for CoverageGraph {
259    #[inline]
260    fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
261        self.successors[node].iter().copied()
262    }
263}
264
265impl graph::Predecessors for CoverageGraph {
266    #[inline]
267    fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
268        self.predecessors[node].iter().copied()
269    }
270}
271
272/// `BasicCoverageBlockData` holds the data indexed by a `BasicCoverageBlock`.
273///
274/// A `BasicCoverageBlock` (BCB) represents the maximal-length sequence of MIR `BasicBlock`s without
275/// conditional branches, and form a new, simplified, coverage-specific Control Flow Graph, without
276/// altering the original MIR CFG.
277///
278/// Note that running the MIR `SimplifyCfg` transform is not sufficient (and therefore not
279/// necessary). The BCB-based CFG is a more aggressive simplification. For example:
280///
281///   * The BCB CFG ignores (trims) branches not relevant to coverage, such as unwind-related code,
282///     that is injected by the Rust compiler but has no physical source code to count. This also
283///     means a BasicBlock with a `Call` terminator can be merged into its primary successor target
284///     block, in the same BCB. (But, note: Issue #78544: "MIR InstrumentCoverage: Improve coverage
285///     of `#[should_panic]` tests and `catch_unwind()` handlers")
286///   * Some BasicBlock terminators support Rust-specific concerns--like borrow-checking--that are
287///     not relevant to coverage analysis. `FalseUnwind`, for example, can be treated the same as
288///     a `Goto`, and merged with its successor into the same BCB.
289///
290/// Each BCB with at least one computed coverage span will have no more than one `Counter`.
291/// In some cases, a BCB's execution count can be computed by `Expression`. Additional
292/// disjoint coverage spans in a BCB can also be counted by `Expression` (by adding `ZERO`
293/// to the BCB's primary counter or expression).
294///
295/// The BCB CFG is critical to simplifying the coverage analysis by ensuring graph path-based
296/// queries (`dominates()`, `predecessors`, `successors`, etc.) have branch (control flow)
297/// significance.
298#[derive(Debug, Clone)]
299pub(crate) struct BasicCoverageBlockData {
300    pub(crate) basic_blocks: Vec<BasicBlock>,
301
302    /// If true, this node's execution count can be assumed to be the sum of the
303    /// execution counts of all of its **out-edges** (assuming no panics).
304    ///
305    /// Notably, this is false for a node ending with [`TerminatorKind::Yield`],
306    /// because the yielding coroutine might not be resumed.
307    pub(crate) is_out_summable: bool,
308}
309
310impl BasicCoverageBlockData {
311    #[inline(always)]
312    pub(crate) fn leader_bb(&self) -> BasicBlock {
313        self.basic_blocks[0]
314    }
315
316    #[inline(always)]
317    pub(crate) fn last_bb(&self) -> BasicBlock {
318        *self.basic_blocks.last().unwrap()
319    }
320}
321
322/// Holds the coverage-relevant successors of a basic block's terminator, and
323/// indicates whether that block can potentially be combined into the same BCB
324/// as its sole successor.
325#[derive(Clone, Copy, Debug)]
326struct CoverageSuccessors<'a> {
327    /// Coverage-relevant successors of the corresponding terminator.
328    /// There might be 0, 1, or multiple targets.
329    targets: &'a [BasicBlock],
330    /// `Yield` terminators are not chainable, because their sole out-edge is
331    /// only followed if/when the generator is resumed after the yield.
332    is_yield: bool,
333}
334
335impl CoverageSuccessors<'_> {
336    /// If `false`, this terminator cannot be chained into another block when
337    /// building the coverage graph.
338    fn is_out_chainable(&self) -> bool {
339        // If a terminator is out-summable and has exactly one out-edge, then
340        // it is eligible to be chained into its successor block.
341        self.is_out_summable() && self.targets.len() == 1
342    }
343
344    /// Returns true if the terminator itself is assumed to have the same
345    /// execution count as the sum of its out-edges (assuming no panics).
346    fn is_out_summable(&self) -> bool {
347        !self.is_yield && !self.targets.is_empty()
348    }
349}
350
351impl IntoIterator for CoverageSuccessors<'_> {
352    type Item = BasicBlock;
353    type IntoIter = impl DoubleEndedIterator<Item = Self::Item>;
354
355    fn into_iter(self) -> Self::IntoIter {
356        self.targets.iter().copied()
357    }
358}
359
360// Returns the subset of a block's successors that are relevant to the coverage
361// graph, i.e. those that do not represent unwinds or false edges.
362// FIXME(#78544): MIR InstrumentCoverage: Improve coverage of `#[should_panic]` tests and
363// `catch_unwind()` handlers.
364fn bcb_filtered_successors<'a, 'tcx>(terminator: &'a Terminator<'tcx>) -> CoverageSuccessors<'a> {
365    use TerminatorKind::*;
366    let mut is_yield = false;
367    let targets = match &terminator.kind {
368        // A switch terminator can have many coverage-relevant successors.
369        SwitchInt { targets, .. } => targets.all_targets(),
370
371        // A yield terminator has exactly 1 successor, but should not be chained,
372        // because its resume edge has a different execution count.
373        Yield { resume, .. } => {
374            is_yield = true;
375            slice::from_ref(resume)
376        }
377
378        // These terminators have exactly one coverage-relevant successor,
379        // and can be chained into it.
380        Assert { target, .. }
381        | Drop { target, .. }
382        | FalseEdge { real_target: target, .. }
383        | FalseUnwind { real_target: target, .. }
384        | Goto { target } => slice::from_ref(target),
385
386        // A call terminator can normally be chained, except when it has no
387        // successor because it is known to diverge.
388        Call { target: maybe_target, .. } => maybe_target.as_slice(),
389
390        // An inline asm terminator can normally be chained, except when it
391        // diverges or uses asm goto.
392        InlineAsm { targets, .. } => &targets,
393
394        // These terminators have no coverage-relevant successors.
395        CoroutineDrop
396        | Return
397        | TailCall { .. }
398        | Unreachable
399        | UnwindResume
400        | UnwindTerminate(_) => &[],
401    };
402
403    CoverageSuccessors { targets, is_yield }
404}
405
406/// Wrapper around a [`mir::BasicBlocks`] graph that restricts each node's
407/// successors to only the ones considered "relevant" when building a coverage
408/// graph.
409#[derive(Clone, Copy)]
410struct CoverageRelevantSubgraph<'a, 'tcx> {
411    basic_blocks: &'a mir::BasicBlocks<'tcx>,
412}
413impl<'a, 'tcx> CoverageRelevantSubgraph<'a, 'tcx> {
414    fn new(basic_blocks: &'a mir::BasicBlocks<'tcx>) -> Self {
415        Self { basic_blocks }
416    }
417
418    fn coverage_successors(&self, bb: BasicBlock) -> CoverageSuccessors<'_> {
419        bcb_filtered_successors(self.basic_blocks[bb].terminator())
420    }
421}
422impl<'a, 'tcx> graph::DirectedGraph for CoverageRelevantSubgraph<'a, 'tcx> {
423    type Node = BasicBlock;
424
425    fn num_nodes(&self) -> usize {
426        self.basic_blocks.num_nodes()
427    }
428}
429impl<'a, 'tcx> graph::Successors for CoverageRelevantSubgraph<'a, 'tcx> {
430    fn successors(&self, bb: Self::Node) -> impl Iterator<Item = Self::Node> {
431        self.coverage_successors(bb).into_iter()
432    }
433}