rustc_mir_transform/coverage/
mappings.rs

Help
1use std::collections::BTreeSet;
2
3use rustc_data_structures::fx::FxIndexMap;
4use rustc_index::IndexVec;
5use rustc_middle::mir::coverage::{
6    BlockMarkerId, BranchSpan, ConditionId, ConditionInfo, CoverageInfoHi, CoverageKind,
7};
8use rustc_middle::mir::{self, BasicBlock, StatementKind};
9use rustc_middle::ty::TyCtxt;
10use rustc_span::Span;
11
12use crate::coverage::ExtractedHirInfo;
13use crate::coverage::graph::{BasicCoverageBlock, CoverageGraph, START_BCB};
14use crate::coverage::spans::extract_refined_covspans;
15use crate::coverage::unexpand::unexpand_into_body_span;
16use crate::errors::MCDCExceedsTestVectorLimit;
17
18/// Associates an ordinary executable code span with its corresponding BCB.
19#[derive(Debug)]
20pub(super) struct CodeMapping {
21    pub(super) span: Span,
22    pub(super) bcb: BasicCoverageBlock,
23}
24
25/// This is separate from [`MCDCBranch`] to help prepare for larger changes
26/// that will be needed for improved branch coverage in the future.
27/// (See <https://github.com/rust-lang/rust/pull/124217>.)
28#[derive(Debug)]
29pub(super) struct BranchPair {
30    pub(super) span: Span,
31    pub(super) true_bcb: BasicCoverageBlock,
32    pub(super) false_bcb: BasicCoverageBlock,
33}
34
35/// Associates an MC/DC branch span with condition info besides fields for normal branch.
36#[derive(Debug)]
37pub(super) struct MCDCBranch {
38    pub(super) span: Span,
39    pub(super) true_bcb: BasicCoverageBlock,
40    pub(super) false_bcb: BasicCoverageBlock,
41    pub(super) condition_info: ConditionInfo,
42    // Offset added to test vector idx if this branch is evaluated to true.
43    pub(super) true_index: usize,
44    // Offset added to test vector idx if this branch is evaluated to false.
45    pub(super) false_index: usize,
46}
47
48/// Associates an MC/DC decision with its join BCBs.
49#[derive(Debug)]
50pub(super) struct MCDCDecision {
51    pub(super) span: Span,
52    pub(super) end_bcbs: BTreeSet<BasicCoverageBlock>,
53    pub(super) bitmap_idx: usize,
54    pub(super) num_test_vectors: usize,
55    pub(super) decision_depth: u16,
56}
57
58// LLVM uses `i32` to index the bitmap. Thus `i32::MAX` is the hard limit for number of all test vectors
59// in a function.
60const MCDC_MAX_BITMAP_SIZE: usize = i32::MAX as usize;
61
62#[derive(Default)]
63pub(super) struct ExtractedMappings {
64    pub(super) code_mappings: Vec<CodeMapping>,
65    pub(super) branch_pairs: Vec<BranchPair>,
66    pub(super) mcdc_bitmap_bits: usize,
67    pub(super) mcdc_degraded_branches: Vec<MCDCBranch>,
68    pub(super) mcdc_mappings: Vec<(MCDCDecision, Vec<MCDCBranch>)>,
69}
70
71/// Extracts coverage-relevant spans from MIR, and associates them with
72/// their corresponding BCBs.
73pub(super) fn extract_all_mapping_info_from_mir<'tcx>(
74    tcx: TyCtxt<'tcx>,
75    mir_body: &mir::Body<'tcx>,
76    hir_info: &ExtractedHirInfo,
77    graph: &CoverageGraph,
78) -> ExtractedMappings {
79    let mut code_mappings = vec![];
80    let mut branch_pairs = vec![];
81    let mut mcdc_bitmap_bits = 0;
82    let mut mcdc_degraded_branches = vec![];
83    let mut mcdc_mappings = vec![];
84
85    if hir_info.is_async_fn || tcx.sess.coverage_no_mir_spans() {
86        // An async function desugars into a function that returns a future,
87        // with the user code wrapped in a closure. Any spans in the desugared
88        // outer function will be unhelpful, so just keep the signature span
89        // and ignore all of the spans in the MIR body.
90        //
91        // When debugging flag `-Zcoverage-options=no-mir-spans` is set, we need
92        // to give the same treatment to _all_ functions, because `llvm-cov`
93        // seems to ignore functions that don't have any ordinary code spans.
94        if let Some(span) = hir_info.fn_sig_span_extended {
95            code_mappings.push(CodeMapping { span, bcb: START_BCB });
96        }
97    } else {
98        // Extract coverage spans from MIR statements/terminators as normal.
99        extract_refined_covspans(mir_body, hir_info, graph, &mut code_mappings);
100    }
101
102    branch_pairs.extend(extract_branch_pairs(mir_body, hir_info, graph));
103
104    extract_mcdc_mappings(
105        mir_body,
106        tcx,
107        hir_info.body_span,
108        graph,
109        &mut mcdc_bitmap_bits,
110        &mut mcdc_degraded_branches,
111        &mut mcdc_mappings,
112    );
113
114    ExtractedMappings {
115        code_mappings,
116        branch_pairs,
117        mcdc_bitmap_bits,
118        mcdc_degraded_branches,
119        mcdc_mappings,
120    }
121}
122
123fn resolve_block_markers(
124    coverage_info_hi: &CoverageInfoHi,
125    mir_body: &mir::Body<'_>,
126) -> IndexVec<BlockMarkerId, Option<BasicBlock>> {
127    let mut block_markers = IndexVec::<BlockMarkerId, Option<BasicBlock>>::from_elem_n(
128        None,
129        coverage_info_hi.num_block_markers,
130    );
131
132    // Fill out the mapping from block marker IDs to their enclosing blocks.
133    for (bb, data) in mir_body.basic_blocks.iter_enumerated() {
134        for statement in &data.statements {
135            if let StatementKind::Coverage(CoverageKind::BlockMarker { id }) = statement.kind {
136                block_markers[id] = Some(bb);
137            }
138        }
139    }
140
141    block_markers
142}
143
144// FIXME: There is currently a lot of redundancy between
145// `extract_branch_pairs` and `extract_mcdc_mappings`. This is needed so
146// that they can each be modified without interfering with the other, but in
147// the long term we should try to bring them together again when branch coverage
148// and MC/DC coverage support are more mature.
149
150pub(super) fn extract_branch_pairs(
151    mir_body: &mir::Body<'_>,
152    hir_info: &ExtractedHirInfo,
153    graph: &CoverageGraph,
154) -> Vec<BranchPair> {
155    let Some(coverage_info_hi) = mir_body.coverage_info_hi.as_deref() else { return vec![] };
156
157    let block_markers = resolve_block_markers(coverage_info_hi, mir_body);
158
159    coverage_info_hi
160        .branch_spans
161        .iter()
162        .filter_map(|&BranchSpan { span: raw_span, true_marker, false_marker }| {
163            // For now, ignore any branch span that was introduced by
164            // expansion. This makes things like assert macros less noisy.
165            if !raw_span.ctxt().outer_expn_data().is_root() {
166                return None;
167            }
168            let span = unexpand_into_body_span(raw_span, hir_info.body_span)?;
169
170            let bcb_from_marker = |marker: BlockMarkerId| graph.bcb_from_bb(block_markers[marker]?);
171
172            let true_bcb = bcb_from_marker(true_marker)?;
173            let false_bcb = bcb_from_marker(false_marker)?;
174
175            Some(BranchPair { span, true_bcb, false_bcb })
176        })
177        .collect::<Vec<_>>()
178}
179
180pub(super) fn extract_mcdc_mappings(
181    mir_body: &mir::Body<'_>,
182    tcx: TyCtxt<'_>,
183    body_span: Span,
184    graph: &CoverageGraph,
185    mcdc_bitmap_bits: &mut usize,
186    mcdc_degraded_branches: &mut impl Extend<MCDCBranch>,
187    mcdc_mappings: &mut impl Extend<(MCDCDecision, Vec<MCDCBranch>)>,
188) {
189    let Some(coverage_info_hi) = mir_body.coverage_info_hi.as_deref() else { return };
190
191    let block_markers = resolve_block_markers(coverage_info_hi, mir_body);
192
193    let bcb_from_marker = |marker: BlockMarkerId| graph.bcb_from_bb(block_markers[marker]?);
194
195    let check_branch_bcb =
196        |raw_span: Span, true_marker: BlockMarkerId, false_marker: BlockMarkerId| {
197            // For now, ignore any branch span that was introduced by
198            // expansion. This makes things like assert macros less noisy.
199            if !raw_span.ctxt().outer_expn_data().is_root() {
200                return None;
201            }
202            let span = unexpand_into_body_span(raw_span, body_span)?;
203
204            let true_bcb = bcb_from_marker(true_marker)?;
205            let false_bcb = bcb_from_marker(false_marker)?;
206            Some((span, true_bcb, false_bcb))
207        };
208
209    let to_mcdc_branch = |&mir::coverage::MCDCBranchSpan {
210                              span: raw_span,
211                              condition_info,
212                              true_marker,
213                              false_marker,
214                          }| {
215        let (span, true_bcb, false_bcb) = check_branch_bcb(raw_span, true_marker, false_marker)?;
216        Some(MCDCBranch {
217            span,
218            true_bcb,
219            false_bcb,
220            condition_info,
221            true_index: usize::MAX,
222            false_index: usize::MAX,
223        })
224    };
225
226    let mut get_bitmap_idx = |num_test_vectors: usize| -> Option<usize> {
227        let bitmap_idx = *mcdc_bitmap_bits;
228        let next_bitmap_bits = bitmap_idx.saturating_add(num_test_vectors);
229        (next_bitmap_bits <= MCDC_MAX_BITMAP_SIZE).then(|| {
230            *mcdc_bitmap_bits = next_bitmap_bits;
231            bitmap_idx
232        })
233    };
234    mcdc_degraded_branches
235        .extend(coverage_info_hi.mcdc_degraded_branch_spans.iter().filter_map(to_mcdc_branch));
236
237    mcdc_mappings.extend(coverage_info_hi.mcdc_spans.iter().filter_map(|(decision, branches)| {
238        if branches.len() == 0 {
239            return None;
240        }
241        let decision_span = unexpand_into_body_span(decision.span, body_span)?;
242
243        let end_bcbs = decision
244            .end_markers
245            .iter()
246            .map(|&marker| bcb_from_marker(marker))
247            .collect::<Option<_>>()?;
248        let mut branch_mappings: Vec<_> = branches.into_iter().filter_map(to_mcdc_branch).collect();
249        if branch_mappings.len() != branches.len() {
250            mcdc_degraded_branches.extend(branch_mappings);
251            return None;
252        }
253        let num_test_vectors = calc_test_vectors_index(&mut branch_mappings);
254        let Some(bitmap_idx) = get_bitmap_idx(num_test_vectors) else {
255            tcx.dcx().emit_warn(MCDCExceedsTestVectorLimit {
256                span: decision_span,
257                max_num_test_vectors: MCDC_MAX_BITMAP_SIZE,
258            });
259            mcdc_degraded_branches.extend(branch_mappings);
260            return None;
261        };
262        // LLVM requires span of the decision contains all spans of its conditions.
263        // Usually the decision span meets the requirement well but in cases like macros it may not.
264        let span = branch_mappings
265            .iter()
266            .map(|branch| branch.span)
267            .reduce(|lhs, rhs| lhs.to(rhs))
268            .map(
269                |joint_span| {
270                    if decision_span.contains(joint_span) { decision_span } else { joint_span }
271                },
272            )
273            .expect("branch mappings are ensured to be non-empty as checked above");
274        Some((
275            MCDCDecision {
276                span,
277                end_bcbs,
278                bitmap_idx,
279                num_test_vectors,
280                decision_depth: decision.decision_depth,
281            },
282            branch_mappings,
283        ))
284    }));
285}
286
287// LLVM checks the executed test vector by accumulating indices of tested branches.
288// We calculate number of all possible test vectors of the decision and assign indices
289// to branches here.
290// See [the rfc](https://discourse.llvm.org/t/rfc-coverage-new-algorithm-and-file-format-for-mc-dc/76798/)
291// for more details about the algorithm.
292// This function is mostly like [`TVIdxBuilder::TvIdxBuilder`](https://github.com/llvm/llvm-project/blob/d594d9f7f4dc6eb748b3261917db689fdc348b96/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp#L226)
293fn calc_test_vectors_index(conditions: &mut Vec<MCDCBranch>) -> usize {
294    let mut indegree_stats = IndexVec::<ConditionId, usize>::from_elem_n(0, conditions.len());
295    // `num_paths` is `width` described at the llvm rfc, which indicates how many paths reaching the condition node.
296    let mut num_paths_stats = IndexVec::<ConditionId, usize>::from_elem_n(0, conditions.len());
297    let mut next_conditions = conditions
298        .iter_mut()
299        .map(|branch| {
300            let ConditionInfo { condition_id, true_next_id, false_next_id } = branch.condition_info;
301            [true_next_id, false_next_id]
302                .into_iter()
303                .flatten()
304                .for_each(|next_id| indegree_stats[next_id] += 1);
305            (condition_id, branch)
306        })
307        .collect::<FxIndexMap<_, _>>();
308
309    let mut queue =
310        std::collections::VecDeque::from_iter(next_conditions.swap_remove(&ConditionId::START));
311    num_paths_stats[ConditionId::START] = 1;
312    let mut decision_end_nodes = Vec::new();
313    while let Some(branch) = queue.pop_front() {
314        let ConditionInfo { condition_id, true_next_id, false_next_id } = branch.condition_info;
315        let (false_index, true_index) = (&mut branch.false_index, &mut branch.true_index);
316        let this_paths_count = num_paths_stats[condition_id];
317        // Note. First check the false next to ensure conditions are touched in same order with llvm-cov.
318        for (next, index) in [(false_next_id, false_index), (true_next_id, true_index)] {
319            if let Some(next_id) = next {
320                let next_paths_count = &mut num_paths_stats[next_id];
321                *index = *next_paths_count;
322                *next_paths_count = next_paths_count.saturating_add(this_paths_count);
323                let next_indegree = &mut indegree_stats[next_id];
324                *next_indegree -= 1;
325                if *next_indegree == 0 {
326                    queue.push_back(next_conditions.swap_remove(&next_id).expect(
327                        "conditions with non-zero indegree before must be in next_conditions",
328                    ));
329                }
330            } else {
331                decision_end_nodes.push((this_paths_count, condition_id, index));
332            }
333        }
334    }
335    assert!(next_conditions.is_empty(), "the decision tree has untouched nodes");
336    let mut cur_idx = 0;
337    // LLVM hopes the end nodes are sorted in descending order by `num_paths` so that it can
338    // optimize bitmap size for decisions in tree form such as `a && b && c && d && ...`.
339    decision_end_nodes.sort_by_key(|(num_paths, _, _)| usize::MAX - *num_paths);
340    for (num_paths, condition_id, index) in decision_end_nodes {
341        assert_eq!(
342            num_paths, num_paths_stats[condition_id],
343            "end nodes should not be updated since they were visited"
344        );
345        assert_eq!(*index, usize::MAX, "end nodes should not be assigned index before");
346        *index = cur_idx;
347        cur_idx += num_paths;
348    }
349    cur_idx
350}
rustc_mir_transform/coverage/mappings.rs

rustc_mir_transform/coverage/
mappings.rs
