coverage. Generate Mappings of decisions and conditions for MC/DC

3 files changed, 160 insertions, 22 deletions

diff --git a/compiler/rustc_mir_transform/src/coverage/mod.rs b/compiler/rustc_mir_transform/src/coverage/mod.rs
index d382d2c03c2..9e8648b0f93 100644
--- a/compiler/rustc_mir_transform/src/coverage/mod.rs
+++ b/compiler/rustc_mir_transform/src/coverage/mod.rs
@@ -100,9 +100,12 @@ fn instrument_function_for_coverage<'tcx>(tcx: TyCtxt<'tcx>, mir_body: &mut mir:
         &coverage_counters,
     );
 
+    inject_mcdc_statements(mir_body, &basic_coverage_blocks, &coverage_spans);
+
     mir_body.function_coverage_info = Some(Box::new(FunctionCoverageInfo {
         function_source_hash: hir_info.function_source_hash,
         num_counters: coverage_counters.num_counters(),
+        mcdc_bitmap_bytes: coverage_spans.test_vector_bitmap_bytes(),
         expressions: coverage_counters.into_expressions(),
         mappings,
     }));
@@ -136,20 +139,33 @@ fn create_mappings<'tcx>(
             .as_term()
     };
 
-    coverage_spans
-        .all_bcb_mappings()
-        .filter_map(|&BcbMapping { kind: bcb_mapping_kind, span }| {
-            let kind = match bcb_mapping_kind {
+    let mut mappings = Vec::new();
+
+    mappings.extend(coverage_spans.all_bcb_mappings().filter_map(
+        |BcbMapping { kind: bcb_mapping_kind, span }| {
+            let kind = match *bcb_mapping_kind {
                 BcbMappingKind::Code(bcb) => MappingKind::Code(term_for_bcb(bcb)),
                 BcbMappingKind::Branch { true_bcb, false_bcb } => MappingKind::Branch {
                     true_term: term_for_bcb(true_bcb),
                     false_term: term_for_bcb(false_bcb),
                 },
+                BcbMappingKind::MCDCBranch { true_bcb, false_bcb, condition_info } => {
+                    MappingKind::MCDCBranch {
+                        true_term: term_for_bcb(true_bcb),
+                        false_term: term_for_bcb(false_bcb),
+                        mcdc_params: condition_info,
+                    }
+                }
+                BcbMappingKind::MCDCDecision { bitmap_idx, conditions_num, .. } => {
+                    MappingKind::MCDCDecision(DecisionInfo { bitmap_idx, conditions_num })
+                }
             };
-            let code_region = make_code_region(source_map, file_name, span, body_span)?;
+            let code_region = make_code_region(source_map, file_name, *span, body_span)?;
             Some(Mapping { kind, code_region })
-        })
-        .collect::<Vec<_>>()
+        },
+    ));
+
+    mappings
 }
 
 /// For each BCB node or BCB edge that has an associated coverage counter,
@@ -204,6 +220,55 @@ fn inject_coverage_statements<'tcx>(
     }
 }
 
+/// For each conditions inject statements to update condition bitmap after it has been evaluated.
+/// For each decision inject statements to update test vector bitmap after it has been evaluated.
+fn inject_mcdc_statements<'tcx>(
+    mir_body: &mut mir::Body<'tcx>,
+    basic_coverage_blocks: &CoverageGraph,
+    coverage_spans: &CoverageSpans,
+) {
+    if coverage_spans.test_vector_bitmap_bytes() == 0 {
+        return;
+    }
+
+    // Inject test vector update first because `inject_statement` always insert new statement at head.
+    for (end_bcbs, bitmap_idx) in
+        coverage_spans.all_bcb_mappings().filter_map(|mapping| match &mapping.kind {
+            BcbMappingKind::MCDCDecision { end_bcbs, bitmap_idx, .. } => {
+                Some((end_bcbs, *bitmap_idx))
+            }
+            _ => None,
+        })
+    {
+        for end in end_bcbs {
+            let end_bb = basic_coverage_blocks[*end].leader_bb();
+            inject_statement(mir_body, CoverageKind::TestVectorBitmapUpdate { bitmap_idx }, end_bb);
+        }
+    }
+
+    for (true_bcb, false_bcb, condition_id) in
+        coverage_spans.all_bcb_mappings().filter_map(|mapping| match mapping.kind {
+            BcbMappingKind::MCDCBranch { true_bcb, false_bcb, condition_info } => {
+                Some((true_bcb, false_bcb, condition_info.condition_id))
+            }
+            _ => None,
+        })
+    {
+        let true_bb = basic_coverage_blocks[true_bcb].leader_bb();
+        inject_statement(
+            mir_body,
+            CoverageKind::CondBitmapUpdate { id: condition_id, value: true },
+            true_bb,
+        );
+        let false_bb = basic_coverage_blocks[false_bcb].leader_bb();
+        inject_statement(
+            mir_body,
+            CoverageKind::CondBitmapUpdate { id: condition_id, value: false },
+            false_bb,
+        );
+    }
+}
+
 /// Given two basic blocks that have a control-flow edge between them, creates
 /// and returns a new block that sits between those blocks.
 fn inject_edge_counter_basic_block(
diff --git a/compiler/rustc_mir_transform/src/coverage/spans.rs b/compiler/rustc_mir_transform/src/coverage/spans.rs
index 03ede886688..a4cd8a38c66 100644
--- a/compiler/rustc_mir_transform/src/coverage/spans.rs
+++ b/compiler/rustc_mir_transform/src/coverage/spans.rs
@@ -1,7 +1,9 @@
 use rustc_data_structures::graph::DirectedGraph;
 use rustc_index::bit_set::BitSet;
 use rustc_middle::mir;
+use rustc_middle::mir::coverage::ConditionInfo;
 use rustc_span::{BytePos, Span};
+use std::collections::BTreeSet;
 
 use crate::coverage::graph::{BasicCoverageBlock, CoverageGraph, START_BCB};
 use crate::coverage::spans::from_mir::SpanFromMir;
@@ -9,12 +11,20 @@ use crate::coverage::ExtractedHirInfo;
 
 mod from_mir;
 
-#[derive(Clone, Copy, Debug)]
+#[derive(Clone, Debug)]
 pub(super) enum BcbMappingKind {
     /// Associates an ordinary executable code span with its corresponding BCB.
     Code(BasicCoverageBlock),
     /// Associates a branch span with BCBs for its true and false arms.
     Branch { true_bcb: BasicCoverageBlock, false_bcb: BasicCoverageBlock },
+    /// Associates a mcdc branch span with condition info besides fields for normal branch.
+    MCDCBranch {
+        true_bcb: BasicCoverageBlock,
+        false_bcb: BasicCoverageBlock,
+        condition_info: ConditionInfo,
+    },
+    /// Associates a mcdc decision with its join BCB.
+    MCDCDecision { end_bcbs: BTreeSet<BasicCoverageBlock>, bitmap_idx: u32, conditions_num: u16 },
 }
 
 #[derive(Debug)]
@@ -26,6 +36,7 @@ pub(super) struct BcbMapping {
 pub(super) struct CoverageSpans {
     bcb_has_mappings: BitSet<BasicCoverageBlock>,
     mappings: Vec<BcbMapping>,
+    test_vector_bitmap_bytes: u32,
 }
 
 impl CoverageSpans {
@@ -36,6 +47,10 @@ impl CoverageSpans {
     pub(super) fn all_bcb_mappings(&self) -> impl Iterator<Item = &BcbMapping> {
         self.mappings.iter()
     }
+
+    pub(super) fn test_vector_bitmap_bytes(&self) -> u32 {
+        self.test_vector_bitmap_bytes
+    }
 }
 
 /// Extracts coverage-relevant spans from MIR, and associates them with
@@ -85,17 +100,26 @@ pub(super) fn generate_coverage_spans(
     let mut insert = |bcb| {
         bcb_has_mappings.insert(bcb);
     };
-    for &BcbMapping { kind, span: _ } in &mappings {
-        match kind {
+    let mut test_vector_bitmap_bytes = 0;
+    for BcbMapping { kind, span: _ } in &mappings {
+        match *kind {
             BcbMappingKind::Code(bcb) => insert(bcb),
-            BcbMappingKind::Branch { true_bcb, false_bcb } => {
+            BcbMappingKind::Branch { true_bcb, false_bcb }
+            | BcbMappingKind::MCDCBranch { true_bcb, false_bcb, .. } => {
                 insert(true_bcb);
                 insert(false_bcb);
             }
+            BcbMappingKind::MCDCDecision { bitmap_idx, conditions_num, .. } => {
+                // `bcb_has_mappings` is used for inject coverage counters
+                // but they are not needed for decision BCBs.
+                // While the length of test vector bitmap should be calculated here.
+                test_vector_bitmap_bytes = test_vector_bitmap_bytes
+                    .max(bitmap_idx + (1_u32 << conditions_num as u32).div_ceil(8));
+            }
         }
     }
 
-    Some(CoverageSpans { bcb_has_mappings, mappings })
+    Some(CoverageSpans { bcb_has_mappings, mappings, test_vector_bitmap_bytes })
 }
 
 #[derive(Debug)]
diff --git a/compiler/rustc_mir_transform/src/coverage/spans/from_mir.rs b/compiler/rustc_mir_transform/src/coverage/spans/from_mir.rs
index adb0c9f1929..b9919a2ae88 100644
--- a/compiler/rustc_mir_transform/src/coverage/spans/from_mir.rs
+++ b/compiler/rustc_mir_transform/src/coverage/spans/from_mir.rs
@@ -1,7 +1,9 @@
 use rustc_data_structures::captures::Captures;
 use rustc_data_structures::fx::FxHashSet;
 use rustc_index::IndexVec;
-use rustc_middle::mir::coverage::{BlockMarkerId, BranchSpan, CoverageKind};
+use rustc_middle::mir::coverage::{
+    BlockMarkerId, BranchSpan, CoverageKind, MCDCBranchSpan, MCDCDecisionSpan,
+};
 use rustc_middle::mir::{
     self, AggregateKind, BasicBlock, FakeReadCause, Rvalue, Statement, StatementKind, Terminator,
     TerminatorKind,
@@ -227,7 +229,10 @@ fn filtered_statement_span(statement: &Statement<'_>) -> Option<Span> {
 
         // These coverage statements should not exist prior to coverage instrumentation.
         StatementKind::Coverage(
-            CoverageKind::CounterIncrement { .. } | CoverageKind::ExpressionUsed { .. },
+            CoverageKind::CounterIncrement { .. }
+            | CoverageKind::ExpressionUsed { .. }
+            | CoverageKind::CondBitmapUpdate { .. }
+            | CoverageKind::TestVectorBitmapUpdate { .. },
         ) => bug!(
             "Unexpected coverage statement found during coverage instrumentation: {statement:?}"
         ),
@@ -384,10 +389,11 @@ pub(super) fn extract_branch_mappings(
         }
     }
 
-    branch_info
-        .branch_spans
-        .iter()
-        .filter_map(|&BranchSpan { span: raw_span, true_marker, false_marker }| {
+    let bcb_from_marker =
+        |marker: BlockMarkerId| basic_coverage_blocks.bcb_from_bb(block_markers[marker]?);
+
+    let check_branch_bcb =
+        |raw_span: Span, true_marker: BlockMarkerId, false_marker: BlockMarkerId| {
             // For now, ignore any branch span that was introduced by
             // expansion. This makes things like assert macros less noisy.
             if !raw_span.ctxt().outer_expn_data().is_root() {
@@ -395,13 +401,56 @@ pub(super) fn extract_branch_mappings(
             }
             let (span, _) = unexpand_into_body_span_with_visible_macro(raw_span, body_span)?;
 
-            let bcb_from_marker =
-                |marker: BlockMarkerId| basic_coverage_blocks.bcb_from_bb(block_markers[marker]?);
-
             let true_bcb = bcb_from_marker(true_marker)?;
             let false_bcb = bcb_from_marker(false_marker)?;
+            Some((span, true_bcb, false_bcb))
+        };
 
-            Some(BcbMapping { kind: BcbMappingKind::Branch { true_bcb, false_bcb }, span })
+    let branch_filter_map = |&BranchSpan { span: raw_span, true_marker, false_marker }| {
+        check_branch_bcb(raw_span, true_marker, false_marker).map(|(span, true_bcb, false_bcb)| {
+            BcbMapping { kind: BcbMappingKind::Branch { true_bcb, false_bcb }, span }
         })
+    };
+
+    let mcdc_branch_filter_map =
+        |&MCDCBranchSpan { span: raw_span, true_marker, false_marker, condition_info }| {
+            check_branch_bcb(raw_span, true_marker, false_marker).map(
+                |(span, true_bcb, false_bcb)| BcbMapping {
+                    kind: BcbMappingKind::MCDCBranch { true_bcb, false_bcb, condition_info },
+                    span,
+                },
+            )
+        };
+
+    let mut next_bitmap_idx = 0;
+
+    let decision_filter_map = |decision: &MCDCDecisionSpan| {
+        let (span, _) = unexpand_into_body_span_with_visible_macro(decision.span, body_span)?;
+
+        let end_bcbs = decision
+            .end_markers
+            .iter()
+            .map(|&marker| bcb_from_marker(marker))
+            .collect::<Option<_>>()?;
+
+        let bitmap_idx = next_bitmap_idx;
+        next_bitmap_idx += (1_u32 << decision.conditions_num).div_ceil(8);
+
+        Some(BcbMapping {
+            kind: BcbMappingKind::MCDCDecision {
+                end_bcbs,
+                bitmap_idx,
+                conditions_num: decision.conditions_num as u16,
+            },
+            span,
+        })
+    };
+
+    branch_info
+        .branch_spans
+        .iter()
+        .filter_map(branch_filter_map)
+        .chain(branch_info.mcdc_branch_spans.iter().filter_map(mcdc_branch_filter_map))
+        .chain(branch_info.mcdc_decision_spans.iter().filter_map(decision_filter_map))
         .collect::<Vec<_>>()
 }