rustc_mir_transform/coverage/
graph.rs1use 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#[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 dominator_order_rank: IndexVec<BasicCoverageBlock, u32>,
28 is_loop_header: DenseBitSet<BasicCoverageBlock>,
30 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 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 .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 this.dominators = Some(graph::dominators::dominators(&this));
81
82 let dominator_order = graph::iterate::reverse_post_order(&this, this.start_node());
85 assert_eq!(dominator_order.len(), this.num_nodes());
87 for (rank, bcb) in (0u32..).zip(dominator_order) {
88 this.dominator_order_rank[bcb] = rank;
90
91 if this.reloop_predecessors(bcb).next().is_some() {
93 this.is_loop_header.insert(bcb);
94 }
95
96 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 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 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 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 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 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 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#[derive(Debug, Clone)]
299pub(crate) struct BasicCoverageBlockData {
300 pub(crate) basic_blocks: Vec<BasicBlock>,
301
302 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#[derive(Clone, Copy, Debug)]
326struct CoverageSuccessors<'a> {
327 targets: &'a [BasicBlock],
330 is_yield: bool,
333}
334
335impl CoverageSuccessors<'_> {
336 fn is_out_chainable(&self) -> bool {
339 self.is_out_summable() && self.targets.len() == 1
342 }
343
344 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
360fn 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 SwitchInt { targets, .. } => targets.all_targets(),
370
371 Yield { resume, .. } => {
374 is_yield = true;
375 slice::from_ref(resume)
376 }
377
378 Assert { target, .. }
381 | Drop { target, .. }
382 | FalseEdge { real_target: target, .. }
383 | FalseUnwind { real_target: target, .. }
384 | Goto { target } => slice::from_ref(target),
385
386 Call { target: maybe_target, .. } => maybe_target.as_slice(),
389
390 InlineAsm { targets, .. } => &targets,
393
394 CoroutineDrop
396 | Return
397 | TailCall { .. }
398 | Unreachable
399 | UnwindResume
400 | UnwindTerminate(_) => &[],
401 };
402
403 CoverageSuccessors { targets, is_yield }
404}
405
406#[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}