coverage. Adapt to mcdc mapping formats introduced by llvm 19

9 files changed, 382 insertions, 255 deletions

diff --git a/compiler/rustc_codegen_llvm/src/builder.rs b/compiler/rustc_codegen_llvm/src/builder.rs
index 3abebdf6ca1..30d7ba4421b 100644
--- a/compiler/rustc_codegen_llvm/src/builder.rs
+++ b/compiler/rustc_codegen_llvm/src/builder.rs
@@ -1679,9 +1679,9 @@ impl<'a, 'll, 'tcx> Builder<'a, 'll, 'tcx> {
         &mut self,
         fn_name: &'ll Value,
         hash: &'ll Value,
-        bitmap_bytes: &'ll Value,
+        bitmap_bits: &'ll Value,
     ) {
-        debug!("mcdc_parameters() with args ({:?}, {:?}, {:?})", fn_name, hash, bitmap_bytes);
+        debug!("mcdc_parameters() with args ({:?}, {:?}, {:?})", fn_name, hash, bitmap_bits);
 
         assert!(
             crate::llvm_util::get_version() >= (19, 0, 0),
@@ -1693,7 +1693,7 @@ impl<'a, 'll, 'tcx> Builder<'a, 'll, 'tcx> {
             &[self.cx.type_ptr(), self.cx.type_i64(), self.cx.type_i32()],
             self.cx.type_void(),
         );
-        let args = &[fn_name, hash, bitmap_bytes];
+        let args = &[fn_name, hash, bitmap_bits];
         let args = self.check_call("call", llty, llfn, args);
 
         unsafe {
@@ -1713,13 +1713,12 @@ impl<'a, 'll, 'tcx> Builder<'a, 'll, 'tcx> {
         &mut self,
         fn_name: &'ll Value,
         hash: &'ll Value,
-        bitmap_bytes: &'ll Value,
         bitmap_index: &'ll Value,
         mcdc_temp: &'ll Value,
     ) {
         debug!(
-            "mcdc_tvbitmap_update() with args ({:?}, {:?}, {:?}, {:?}, {:?})",
-            fn_name, hash, bitmap_bytes, bitmap_index, mcdc_temp
+            "mcdc_tvbitmap_update() with args ({:?}, {:?}, {:?}, {:?})",
+            fn_name, hash, bitmap_index, mcdc_temp
         );
         assert!(
             crate::llvm_util::get_version() >= (19, 0, 0),
@@ -1729,16 +1728,10 @@ impl<'a, 'll, 'tcx> Builder<'a, 'll, 'tcx> {
         let llfn =
             unsafe { llvm::LLVMRustGetInstrProfMCDCTVBitmapUpdateIntrinsic(self.cx().llmod) };
         let llty = self.cx.type_func(
-            &[
-                self.cx.type_ptr(),
-                self.cx.type_i64(),
-                self.cx.type_i32(),
-                self.cx.type_i32(),
-                self.cx.type_ptr(),
-            ],
+            &[self.cx.type_ptr(), self.cx.type_i64(), self.cx.type_i32(), self.cx.type_ptr()],
             self.cx.type_void(),
         );
-        let args = &[fn_name, hash, bitmap_bytes, bitmap_index, mcdc_temp];
+        let args = &[fn_name, hash, bitmap_index, mcdc_temp];
         let args = self.check_call("call", llty, llfn, args);
         unsafe {
             let _ = llvm::LLVMRustBuildCall(
@@ -1754,45 +1747,15 @@ impl<'a, 'll, 'tcx> Builder<'a, 'll, 'tcx> {
         self.store(self.const_i32(0), mcdc_temp, self.tcx.data_layout.i32_align.abi);
     }
 
-    pub(crate) fn mcdc_condbitmap_update(
-        &mut self,
-        fn_name: &'ll Value,
-        hash: &'ll Value,
-        cond_loc: &'ll Value,
-        mcdc_temp: &'ll Value,
-        bool_value: &'ll Value,
-    ) {
-        debug!(
-            "mcdc_condbitmap_update() with args ({:?}, {:?}, {:?}, {:?}, {:?})",
-            fn_name, hash, cond_loc, mcdc_temp, bool_value
-        );
+    pub(crate) fn mcdc_condbitmap_update(&mut self, cond_index: &'ll Value, mcdc_temp: &'ll Value) {
+        debug!("mcdc_condbitmap_update() with args ({:?}, {:?})", cond_index, mcdc_temp);
         assert!(
             crate::llvm_util::get_version() >= (19, 0, 0),
             "MCDC intrinsics require LLVM 19 or later"
         );
-        let llfn = unsafe { llvm::LLVMRustGetInstrProfMCDCCondBitmapIntrinsic(self.cx().llmod) };
-        let llty = self.cx.type_func(
-            &[
-                self.cx.type_ptr(),
-                self.cx.type_i64(),
-                self.cx.type_i32(),
-                self.cx.type_ptr(),
-                self.cx.type_i1(),
-            ],
-            self.cx.type_void(),
-        );
-        let args = &[fn_name, hash, cond_loc, mcdc_temp, bool_value];
-        self.check_call("call", llty, llfn, args);
-        unsafe {
-            let _ = llvm::LLVMRustBuildCall(
-                self.llbuilder,
-                llty,
-                llfn,
-                args.as_ptr() as *const &llvm::Value,
-                args.len() as c_uint,
-                [].as_ptr(),
-                0 as c_uint,
-            );
-        }
+        let align = self.tcx.data_layout.i32_align.abi;
+        let current_tv_index = self.load(self.cx.type_i32(), mcdc_temp, align);
+        let new_tv_index = self.add(current_tv_index, cond_index);
+        self.store(new_tv_index, mcdc_temp, align);
     }
 }
diff --git a/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs b/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
index 3a80d216f47..d7d29eebf85 100644
--- a/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
+++ b/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
@@ -98,14 +98,14 @@ impl<'tcx> CoverageInfoBuilderMethods<'tcx> for Builder<'_, '_, 'tcx> {
         };
 
         // If there are no MC/DC bitmaps to set up, return immediately.
-        if function_coverage_info.mcdc_bitmap_bytes == 0 {
+        if function_coverage_info.mcdc_bitmap_bits == 0 {
             return;
         }
 
         let fn_name = self.get_pgo_func_name_var(instance);
         let hash = self.const_u64(function_coverage_info.function_source_hash);
-        let bitmap_bytes = self.const_u32(function_coverage_info.mcdc_bitmap_bytes);
-        self.mcdc_parameters(fn_name, hash, bitmap_bytes);
+        let bitmap_bits = self.const_u32(function_coverage_info.mcdc_bitmap_bits as u32);
+        self.mcdc_parameters(fn_name, hash, bitmap_bits);
 
         // Create pointers named `mcdc.addr.{i}` to stack-allocated condition bitmaps.
         let mut cond_bitmaps = vec![];
@@ -185,35 +185,28 @@ impl<'tcx> CoverageInfoBuilderMethods<'tcx> for Builder<'_, '_, 'tcx> {
             CoverageKind::ExpressionUsed { id } => {
                 func_coverage.mark_expression_id_seen(id);
             }
-            CoverageKind::CondBitmapUpdate { id, value, decision_depth } => {
+            CoverageKind::CondBitmapUpdate { index, decision_depth } => {
                 drop(coverage_map);
-                assert_ne!(
-                    id.as_u32(),
-                    0,
-                    "ConditionId of evaluated conditions should never be zero"
-                );
                 let cond_bitmap = coverage_context
                     .try_get_mcdc_condition_bitmap(&instance, decision_depth)
                     .expect("mcdc cond bitmap should have been allocated for updating");
-                let cond_loc = bx.const_i32(id.as_u32() as i32 - 1);
-                let bool_value = bx.const_bool(value);
-                let fn_name = bx.get_pgo_func_name_var(instance);
-                let hash = bx.const_u64(function_coverage_info.function_source_hash);
-                bx.mcdc_condbitmap_update(fn_name, hash, cond_loc, cond_bitmap, bool_value);
+                let cond_index = bx.const_i32(index as i32);
+                bx.mcdc_condbitmap_update(cond_index, cond_bitmap);
             }
             CoverageKind::TestVectorBitmapUpdate { bitmap_idx, decision_depth } => {
                 drop(coverage_map);
                 let cond_bitmap = coverage_context
                                     .try_get_mcdc_condition_bitmap(&instance, decision_depth)
                                     .expect("mcdc cond bitmap should have been allocated for merging into the global bitmap");
-                let bitmap_bytes = function_coverage_info.mcdc_bitmap_bytes;
-                assert!(bitmap_idx < bitmap_bytes, "bitmap index of the decision out of range");
+                assert!(
+                    bitmap_idx as usize <= function_coverage_info.mcdc_bitmap_bits,
+                    "bitmap index of the decision out of range"
+                );
 
                 let fn_name = bx.get_pgo_func_name_var(instance);
                 let hash = bx.const_u64(function_coverage_info.function_source_hash);
-                let bitmap_bytes = bx.const_u32(bitmap_bytes);
                 let bitmap_index = bx.const_u32(bitmap_idx);
-                bx.mcdc_tvbitmap_update(fn_name, hash, bitmap_bytes, bitmap_index, cond_bitmap);
+                bx.mcdc_tvbitmap_update(fn_name, hash, bitmap_index, cond_bitmap);
             }
         }
     }
diff --git a/compiler/rustc_codegen_llvm/src/llvm/ffi.rs b/compiler/rustc_codegen_llvm/src/llvm/ffi.rs
index d3950df91fb..661debbb9f1 100644
--- a/compiler/rustc_codegen_llvm/src/llvm/ffi.rs
+++ b/compiler/rustc_codegen_llvm/src/llvm/ffi.rs
@@ -1614,7 +1614,6 @@ unsafe extern "C" {
     pub fn LLVMRustGetInstrProfIncrementIntrinsic(M: &Module) -> &Value;
     pub fn LLVMRustGetInstrProfMCDCParametersIntrinsic(M: &Module) -> &Value;
     pub fn LLVMRustGetInstrProfMCDCTVBitmapUpdateIntrinsic(M: &Module) -> &Value;
-    pub fn LLVMRustGetInstrProfMCDCCondBitmapIntrinsic(M: &Module) -> &Value;
 
     pub fn LLVMRustBuildCall<'a>(
         B: &Builder<'a>,
diff --git a/compiler/rustc_middle/src/mir/coverage.rs b/compiler/rustc_middle/src/mir/coverage.rs
index 9a0f5a65321..4a876dc1228 100644
--- a/compiler/rustc_middle/src/mir/coverage.rs
+++ b/compiler/rustc_middle/src/mir/coverage.rs
@@ -128,8 +128,8 @@ pub enum CoverageKind {
 
     /// Marks the point in MIR control flow represented by a evaluated condition.
     ///
-    /// This is eventually lowered to `llvm.instrprof.mcdc.condbitmap.update` in LLVM IR.
-    CondBitmapUpdate { id: ConditionId, value: bool, decision_depth: u16 },
+    /// This is eventually lowered to instruments updating mcdc temp variables.
+    CondBitmapUpdate { index: u32, decision_depth: u16 },
 
     /// Marks the point in MIR control flow represented by a evaluated decision.
     ///
@@ -145,14 +145,8 @@ impl Debug for CoverageKind {
             BlockMarker { id } => write!(fmt, "BlockMarker({:?})", id.index()),
             CounterIncrement { id } => write!(fmt, "CounterIncrement({:?})", id.index()),
             ExpressionUsed { id } => write!(fmt, "ExpressionUsed({:?})", id.index()),
-            CondBitmapUpdate { id, value, decision_depth } => {
-                write!(
-                    fmt,
-                    "CondBitmapUpdate({:?}, {:?}, depth={:?})",
-                    id.index(),
-                    value,
-                    decision_depth
-                )
+            CondBitmapUpdate { index, decision_depth } => {
+                write!(fmt, "CondBitmapUpdate(index={:?}, depth={:?})", index, decision_depth)
             }
             TestVectorBitmapUpdate { bitmap_idx, decision_depth } => {
                 write!(fmt, "TestVectorUpdate({:?}, depth={:?})", bitmap_idx, decision_depth)
@@ -253,7 +247,7 @@ pub struct Mapping {
 pub struct FunctionCoverageInfo {
     pub function_source_hash: u64,
     pub num_counters: usize,
-    pub mcdc_bitmap_bytes: u32,
+    pub mcdc_bitmap_bits: usize,
     pub expressions: IndexVec<ExpressionId, Expression>,
     pub mappings: Vec<Mapping>,
     /// The depth of the deepest decision is used to know how many
@@ -275,8 +269,10 @@ pub struct CoverageInfoHi {
     /// data structures without having to scan the entire body first.
     pub num_block_markers: usize,
     pub branch_spans: Vec<BranchSpan>,
-    pub mcdc_branch_spans: Vec<MCDCBranchSpan>,
-    pub mcdc_decision_spans: Vec<MCDCDecisionSpan>,
+    /// Branch spans generated by mcdc. Because of some limits mcdc builder give up generating
+    /// decisions including them so that they are handled as normal branch spans.
+    pub mcdc_degraded_branch_spans: Vec<MCDCBranchSpan>,
+    pub mcdc_spans: Vec<(MCDCDecisionSpan, Vec<MCDCBranchSpan>)>,
 }
 
 #[derive(Clone, Debug)]
@@ -299,12 +295,9 @@ pub struct ConditionInfo {
 #[derive(TyEncodable, TyDecodable, Hash, HashStable, TypeFoldable, TypeVisitable)]
 pub struct MCDCBranchSpan {
     pub span: Span,
-    /// If `None`, this actually represents a normal branch span inserted for
-    /// code that was too complex for MC/DC.
-    pub condition_info: Option<ConditionInfo>,
+    pub condition_info: ConditionInfo,
     pub true_marker: BlockMarkerId,
     pub false_marker: BlockMarkerId,
-    pub decision_depth: u16,
 }
 
 #[derive(Copy, Clone, Debug)]
@@ -318,7 +311,7 @@ pub struct DecisionInfo {
 #[derive(TyEncodable, TyDecodable, Hash, HashStable, TypeFoldable, TypeVisitable)]
 pub struct MCDCDecisionSpan {
     pub span: Span,
-    pub num_conditions: usize,
     pub end_markers: Vec<BlockMarkerId>,
     pub decision_depth: u16,
+    pub num_conditions: usize,
 }
diff --git a/compiler/rustc_middle/src/mir/pretty.rs b/compiler/rustc_middle/src/mir/pretty.rs
index 9cafe804a8e..2a3a070a6e7 100644
--- a/compiler/rustc_middle/src/mir/pretty.rs
+++ b/compiler/rustc_middle/src/mir/pretty.rs
@@ -538,8 +538,8 @@ fn write_coverage_info_hi(
     let coverage::CoverageInfoHi {
         num_block_markers: _,
         branch_spans,
-        mcdc_branch_spans,
-        mcdc_decision_spans,
+        mcdc_degraded_branch_spans,
+        mcdc_spans,
     } = coverage_info_hi;
 
     // Only add an extra trailing newline if we printed at least one thing.
@@ -553,29 +553,35 @@ fn write_coverage_info_hi(
         did_print = true;
     }
 
-    for coverage::MCDCBranchSpan {
-        span,
-        condition_info,
-        true_marker,
-        false_marker,
-        decision_depth,
-    } in mcdc_branch_spans
+    for coverage::MCDCBranchSpan { span, true_marker, false_marker, .. } in
+        mcdc_degraded_branch_spans
     {
         writeln!(
             w,
-            "{INDENT}coverage mcdc branch {{ condition_id: {:?}, true: {true_marker:?}, false: {false_marker:?}, depth: {decision_depth:?} }} => {span:?}",
-            condition_info.map(|info| info.condition_id)
+            "{INDENT}coverage branch {{ true: {true_marker:?}, false: {false_marker:?} }} => {span:?}",
         )?;
         did_print = true;
     }
 
-    for coverage::MCDCDecisionSpan { span, num_conditions, end_markers, decision_depth } in
-        mcdc_decision_spans
+    for (
+        coverage::MCDCDecisionSpan { span, end_markers, decision_depth, num_conditions: _ },
+        conditions,
+    ) in mcdc_spans
     {
+        let num_conditions = conditions.len();
         writeln!(
             w,
             "{INDENT}coverage mcdc decision {{ num_conditions: {num_conditions:?}, end: {end_markers:?}, depth: {decision_depth:?} }} => {span:?}"
         )?;
+        for coverage::MCDCBranchSpan { span, condition_info, true_marker, false_marker } in
+            conditions
+        {
+            writeln!(
+                w,
+                "{INDENT}coverage mcdc branch {{ condition_id: {:?}, true: {true_marker:?}, false: {false_marker:?} }} => {span:?}",
+                condition_info.condition_id
+            )?;
+        }
         did_print = true;
     }
 
diff --git a/compiler/rustc_mir_build/src/build/coverageinfo.rs b/compiler/rustc_mir_build/src/build/coverageinfo.rs
index 204ee45bfa2..52a4a4b4b51 100644
--- a/compiler/rustc_mir_build/src/build/coverageinfo.rs
+++ b/compiler/rustc_mir_build/src/build/coverageinfo.rs
@@ -175,7 +175,7 @@ impl CoverageInfoBuilder {
         let branch_spans =
             branch_info.map(|branch_info| branch_info.branch_spans).unwrap_or_default();
 
-        let (mcdc_decision_spans, mcdc_branch_spans) =
+        let (mcdc_spans, mcdc_degraded_branch_spans) =
             mcdc_info.map(MCDCInfoBuilder::into_done).unwrap_or_default();
 
         // For simplicity, always return an info struct (without Option), even
@@ -183,8 +183,8 @@ impl CoverageInfoBuilder {
         Box::new(CoverageInfoHi {
             num_block_markers,
             branch_spans,
-            mcdc_branch_spans,
-            mcdc_decision_spans,
+            mcdc_degraded_branch_spans,
+            mcdc_spans,
         })
     }
 }
diff --git a/compiler/rustc_mir_build/src/build/coverageinfo/mcdc.rs b/compiler/rustc_mir_build/src/build/coverageinfo/mcdc.rs
index 5c45a7a33a2..343d4000043 100644
--- a/compiler/rustc_mir_build/src/build/coverageinfo/mcdc.rs
+++ b/compiler/rustc_mir_build/src/build/coverageinfo/mcdc.rs
@@ -12,16 +12,16 @@ use rustc_span::Span;
 use crate::build::Builder;
 use crate::errors::MCDCExceedsConditionLimit;
 
-/// The MCDC bitmap scales exponentially (2^n) based on the number of conditions seen,
-/// So llvm sets a maximum value prevents the bitmap footprint from growing too large without the user's knowledge.
-/// This limit may be relaxed if the [upstream change](https://github.com/llvm/llvm-project/pull/82448) is merged.
-const MAX_CONDITIONS_IN_DECISION: usize = 6;
+/// LLVM uses `i16` to represent condition id. Hence `i16::MAX` is the hard limit for number of
+/// conditions in a decision.
+const MAX_CONDITIONS_IN_DECISION: usize = i16::MAX as usize;
 
 #[derive(Default)]
 struct MCDCDecisionCtx {
     /// To construct condition evaluation tree.
     decision_stack: VecDeque<ConditionInfo>,
     processing_decision: Option<MCDCDecisionSpan>,
+    conditions: Vec<MCDCBranchSpan>,
 }
 
 struct MCDCState {
@@ -155,16 +155,29 @@ impl MCDCState {
         decision_ctx.decision_stack.push_back(lhs);
     }
 
-    fn take_condition(
+    fn try_finish_decision(
         &mut self,
+        span: Span,
         true_marker: BlockMarkerId,
         false_marker: BlockMarkerId,
-    ) -> (Option<ConditionInfo>, Option<MCDCDecisionSpan>) {
+        degraded_branches: &mut Vec<MCDCBranchSpan>,
+    ) -> Option<(MCDCDecisionSpan, Vec<MCDCBranchSpan>)> {
         let Some(decision_ctx) = self.decision_ctx_stack.last_mut() else {
             bug!("Unexpected empty decision_ctx_stack")
         };
         let Some(condition_info) = decision_ctx.decision_stack.pop_back() else {
-            return (None, None);
+            let branch = MCDCBranchSpan {
+                span,
+                condition_info: ConditionInfo {
+                    condition_id: ConditionId::START,
+                    true_next_id: None,
+                    false_next_id: None,
+                },
+                true_marker,
+                false_marker,
+            };
+            degraded_branches.push(branch);
+            return None;
         };
         let Some(decision) = decision_ctx.processing_decision.as_mut() else {
             bug!("Processing decision should have been created before any conditions are taken");
@@ -175,24 +188,31 @@ impl MCDCState {
         if condition_info.false_next_id.is_none() {
             decision.end_markers.push(false_marker);
         }
+        decision_ctx.conditions.push(MCDCBranchSpan {
+            span,
+            condition_info,
+            true_marker,
+            false_marker,
+        });
 
         if decision_ctx.decision_stack.is_empty() {
-            (Some(condition_info), decision_ctx.processing_decision.take())
+            let conditions = std::mem::take(&mut decision_ctx.conditions);
+            decision_ctx.processing_decision.take().map(|decision| (decision, conditions))
         } else {
-            (Some(condition_info), None)
+            None
         }
     }
 }
 
 pub(crate) struct MCDCInfoBuilder {
-    branch_spans: Vec<MCDCBranchSpan>,
-    decision_spans: Vec<MCDCDecisionSpan>,
+    degraded_spans: Vec<MCDCBranchSpan>,
+    mcdc_spans: Vec<(MCDCDecisionSpan, Vec<MCDCBranchSpan>)>,
     state: MCDCState,
 }
 
 impl MCDCInfoBuilder {
     pub(crate) fn new() -> Self {
-        Self { branch_spans: vec![], decision_spans: vec![], state: MCDCState::new() }
+        Self { degraded_spans: vec![], mcdc_spans: vec![], state: MCDCState::new() }
     }
 
     pub(crate) fn visit_evaluated_condition(
@@ -206,50 +226,44 @@ impl MCDCInfoBuilder {
         let true_marker = inject_block_marker(source_info, true_block);
         let false_marker = inject_block_marker(source_info, false_block);
 
-        let decision_depth = self.state.decision_depth();
-        let (mut condition_info, decision_result) =
-            self.state.take_condition(true_marker, false_marker);
         // take_condition() returns Some for decision_result when the decision stack
         // is empty, i.e. when all the conditions of the decision were instrumented,
         // and the decision is "complete".
-        if let Some(decision) = decision_result {
-            match decision.num_conditions {
+        if let Some((decision, conditions)) = self.state.try_finish_decision(
+            source_info.span,
+            true_marker,
+            false_marker,
+            &mut self.degraded_spans,
+        ) {
+            let num_conditions = conditions.len();
+            assert_eq!(
+                num_conditions, decision.num_conditions,
+                "final number of conditions is not correct"
+            );
+            match num_conditions {
                 0 => {
                     unreachable!("Decision with no condition is not expected");
                 }
                 1..=MAX_CONDITIONS_IN_DECISION => {
-                    self.decision_spans.push(decision);
+                    self.mcdc_spans.push((decision, conditions));
                 }
                 _ => {
-                    // Do not generate mcdc mappings and statements for decisions with too many conditions.
-                    // Therefore, first erase the condition info of the (N-1) previous branch spans.
-                    let rebase_idx = self.branch_spans.len() - (decision.num_conditions - 1);
-                    for branch in &mut self.branch_spans[rebase_idx..] {
-                        branch.condition_info = None;
-                    }
-
-                    // Then, erase this last branch span's info too, for a total of N.
-                    condition_info = None;
+                    self.degraded_spans.extend(conditions);
 
                     tcx.dcx().emit_warn(MCDCExceedsConditionLimit {
                         span: decision.span,
-                        num_conditions: decision.num_conditions,
+                        num_conditions,
                         max_conditions: MAX_CONDITIONS_IN_DECISION,
                     });
                 }
             }
         }
-        self.branch_spans.push(MCDCBranchSpan {
-            span: source_info.span,
-            condition_info,
-            true_marker,
-            false_marker,
-            decision_depth,
-        });
     }
 
-    pub(crate) fn into_done(self) -> (Vec<MCDCDecisionSpan>, Vec<MCDCBranchSpan>) {
-        (self.decision_spans, self.branch_spans)
+    pub(crate) fn into_done(
+        self,
+    ) -> (Vec<(MCDCDecisionSpan, Vec<MCDCBranchSpan>)>, Vec<MCDCBranchSpan>) {
+        (self.mcdc_spans, self.degraded_spans)
     }
 }
 
diff --git a/compiler/rustc_mir_transform/src/coverage/mappings.rs b/compiler/rustc_mir_transform/src/coverage/mappings.rs
index ec5ba354805..c20f7a6f326 100644
--- a/compiler/rustc_mir_transform/src/coverage/mappings.rs
+++ b/compiler/rustc_mir_transform/src/coverage/mappings.rs
@@ -1,10 +1,11 @@
 use std::collections::BTreeSet;
 
+use rustc_data_structures::fx::FxIndexMap;
 use rustc_data_structures::graph::DirectedGraph;
 use rustc_index::IndexVec;
 use rustc_index::bit_set::BitSet;
 use rustc_middle::mir::coverage::{
-    BlockMarkerId, BranchSpan, ConditionInfo, CoverageInfoHi, CoverageKind,
+    BlockMarkerId, BranchSpan, ConditionId, ConditionInfo, CoverageInfoHi, CoverageKind,
 };
 use rustc_middle::mir::{self, BasicBlock, StatementKind};
 use rustc_middle::ty::TyCtxt;
@@ -38,10 +39,11 @@ pub(super) struct MCDCBranch {
     pub(super) span: Span,
     pub(super) true_bcb: BasicCoverageBlock,
     pub(super) false_bcb: BasicCoverageBlock,
-    /// If `None`, this actually represents a normal branch mapping inserted
-    /// for code that was too complex for MC/DC.
-    pub(super) condition_info: Option<ConditionInfo>,
-    pub(super) decision_depth: u16,
+    pub(super) condition_info: ConditionInfo,
+    // Offset added to test vector idx if this branch is evaluated to true.
+    pub(super) true_index: usize,
+    // Offset added to test vector idx if this branch is evaluated to false.
+    pub(super) false_index: usize,
 }
 
 /// Associates an MC/DC decision with its join BCBs.
@@ -49,11 +51,15 @@ pub(super) struct MCDCBranch {
 pub(super) struct MCDCDecision {
     pub(super) span: Span,
     pub(super) end_bcbs: BTreeSet<BasicCoverageBlock>,
-    pub(super) bitmap_idx: u32,
-    pub(super) num_conditions: u16,
+    pub(super) bitmap_idx: usize,
+    pub(super) num_test_vectors: usize,
     pub(super) decision_depth: u16,
 }
 
+// LLVM uses `i32` to index the bitmap. Thus `i32::MAX` is the hard limit for number of all test vectors
+// in a function.
+const MCDC_MAX_BITMAP_SIZE: usize = i32::MAX as usize;
+
 #[derive(Default)]
 pub(super) struct ExtractedMappings {
     /// Store our own copy of [`CoverageGraph::num_nodes`], so that we don't
@@ -62,9 +68,9 @@ pub(super) struct ExtractedMappings {
     pub(super) num_bcbs: usize,
     pub(super) code_mappings: Vec<CodeMapping>,
     pub(super) branch_pairs: Vec<BranchPair>,
-    pub(super) mcdc_bitmap_bytes: u32,
-    pub(super) mcdc_branches: Vec<MCDCBranch>,
-    pub(super) mcdc_decisions: Vec<MCDCDecision>,
+    pub(super) mcdc_bitmap_bits: usize,
+    pub(super) mcdc_degraded_branches: Vec<MCDCBranch>,
+    pub(super) mcdc_mappings: Vec<(MCDCDecision, Vec<MCDCBranch>)>,
 }
 
 /// Extracts coverage-relevant spans from MIR, and associates them with
@@ -77,9 +83,9 @@ pub(super) fn extract_all_mapping_info_from_mir<'tcx>(
 ) -> ExtractedMappings {
     let mut code_mappings = vec![];
     let mut branch_pairs = vec![];
-    let mut mcdc_bitmap_bytes = 0;
-    let mut mcdc_branches = vec![];
-    let mut mcdc_decisions = vec![];
+    let mut mcdc_bitmap_bits = 0;
+    let mut mcdc_degraded_branches = vec![];
+    let mut mcdc_mappings = vec![];
 
     if hir_info.is_async_fn || tcx.sess.coverage_no_mir_spans() {
         // An async function desugars into a function that returns a future,
@@ -104,18 +110,18 @@ pub(super) fn extract_all_mapping_info_from_mir<'tcx>(
         mir_body,
         hir_info.body_span,
         basic_coverage_blocks,
-        &mut mcdc_bitmap_bytes,
-        &mut mcdc_branches,
-        &mut mcdc_decisions,
+        &mut mcdc_bitmap_bits,
+        &mut mcdc_degraded_branches,
+        &mut mcdc_mappings,
     );
 
     ExtractedMappings {
         num_bcbs: basic_coverage_blocks.num_nodes(),
         code_mappings,
         branch_pairs,
-        mcdc_bitmap_bytes,
-        mcdc_branches,
-        mcdc_decisions,
+        mcdc_bitmap_bits,
+        mcdc_degraded_branches,
+        mcdc_mappings,
     }
 }
 
@@ -126,9 +132,9 @@ impl ExtractedMappings {
             num_bcbs,
             code_mappings,
             branch_pairs,
-            mcdc_bitmap_bytes: _,
-            mcdc_branches,
-            mcdc_decisions,
+            mcdc_bitmap_bits: _,
+            mcdc_degraded_branches,
+            mcdc_mappings,
         } = self;
 
         // Identify which BCBs have one or more mappings.
@@ -144,7 +150,10 @@ impl ExtractedMappings {
             insert(true_bcb);
             insert(false_bcb);
         }
-        for &MCDCBranch { true_bcb, false_bcb, .. } in mcdc_branches {
+        for &MCDCBranch { true_bcb, false_bcb, .. } in mcdc_degraded_branches
+            .iter()
+            .chain(mcdc_mappings.iter().map(|(_, branches)| branches.into_iter()).flatten())
+        {
             insert(true_bcb);
             insert(false_bcb);
         }
@@ -152,8 +161,8 @@ impl ExtractedMappings {
         // MC/DC decisions refer to BCBs, but don't require those BCBs to have counters.
         if bcbs_with_counter_mappings.is_empty() {
             debug_assert!(
-                mcdc_decisions.is_empty(),
-                "A function with no counter mappings shouldn't have any decisions: {mcdc_decisions:?}",
+                mcdc_mappings.is_empty(),
+                "A function with no counter mappings shouldn't have any decisions: {mcdc_mappings:?}",
             );
         }
 
@@ -232,9 +241,9 @@ pub(super) fn extract_mcdc_mappings(
     mir_body: &mir::Body<'_>,
     body_span: Span,
     basic_coverage_blocks: &CoverageGraph,
-    mcdc_bitmap_bytes: &mut u32,
-    mcdc_branches: &mut impl Extend<MCDCBranch>,
-    mcdc_decisions: &mut impl Extend<MCDCDecision>,
+    mcdc_bitmap_bits: &mut usize,
+    mcdc_degraded_branches: &mut impl Extend<MCDCBranch>,
+    mcdc_mappings: &mut impl Extend<(MCDCDecision, Vec<MCDCBranch>)>,
 ) {
     let Some(coverage_info_hi) = mir_body.coverage_info_hi.as_deref() else { return };
 
@@ -257,43 +266,143 @@ pub(super) fn extract_mcdc_mappings(
             Some((span, true_bcb, false_bcb))
         };
 
-    mcdc_branches.extend(coverage_info_hi.mcdc_branch_spans.iter().filter_map(
-        |&mir::coverage::MCDCBranchSpan {
-             span: raw_span,
-             condition_info,
-             true_marker,
-             false_marker,
-             decision_depth,
-         }| {
-            let (span, true_bcb, false_bcb) =
-                check_branch_bcb(raw_span, true_marker, false_marker)?;
-            Some(MCDCBranch { span, true_bcb, false_bcb, condition_info, decision_depth })
-        },
-    ));
-
-    mcdc_decisions.extend(coverage_info_hi.mcdc_decision_spans.iter().filter_map(
-        |decision: &mir::coverage::MCDCDecisionSpan| {
-            let span = unexpand_into_body_span(decision.span, body_span)?;
-
-            let end_bcbs = decision
-                .end_markers
-                .iter()
-                .map(|&marker| bcb_from_marker(marker))
-                .collect::<Option<_>>()?;
-
-            // Each decision containing N conditions needs 2^N bits of space in
-            // the bitmap, rounded up to a whole number of bytes.
-            // The decision's "bitmap index" points to its first byte in the bitmap.
-            let bitmap_idx = *mcdc_bitmap_bytes;
-            *mcdc_bitmap_bytes += (1_u32 << decision.num_conditions).div_ceil(8);
-
-            Some(MCDCDecision {
+    let to_mcdc_branch = |&mir::coverage::MCDCBranchSpan {
+                              span: raw_span,
+                              condition_info,
+                              true_marker,
+                              false_marker,
+                          }| {
+        let (span, true_bcb, false_bcb) = check_branch_bcb(raw_span, true_marker, false_marker)?;
+        Some(MCDCBranch {
+            span,
+            true_bcb,
+            false_bcb,
+            condition_info,
+            true_index: usize::MAX,
+            false_index: usize::MAX,
+        })
+    };
+
+    let mut get_bitmap_idx = |num_test_vectors: usize| -> Option<usize> {
+        let bitmap_idx = *mcdc_bitmap_bits;
+        let next_bitmap_bits = bitmap_idx.saturating_add(num_test_vectors);
+        (next_bitmap_bits <= MCDC_MAX_BITMAP_SIZE).then(|| {
+            *mcdc_bitmap_bits = next_bitmap_bits;
+            bitmap_idx
+        })
+    };
+    mcdc_degraded_branches
+        .extend(coverage_info_hi.mcdc_degraded_branch_spans.iter().filter_map(to_mcdc_branch));
+
+    mcdc_mappings.extend(coverage_info_hi.mcdc_spans.iter().filter_map(|(decision, branches)| {
+        if branches.len() == 0 {
+            return None;
+        }
+        let decision_span = unexpand_into_body_span(decision.span, body_span)?;
+
+        let end_bcbs = decision
+            .end_markers
+            .iter()
+            .map(|&marker| bcb_from_marker(marker))
+            .collect::<Option<_>>()?;
+        let mut branch_mappings: Vec<_> = branches.into_iter().filter_map(to_mcdc_branch).collect();
+        if branch_mappings.len() != branches.len() {
+            mcdc_degraded_branches.extend(branch_mappings);
+            return None;
+        }
+        let num_test_vectors = calc_test_vectors_index(&mut branch_mappings);
+        let Some(bitmap_idx) = get_bitmap_idx(num_test_vectors) else {
+            // TODO warn about bitmap
+            mcdc_degraded_branches.extend(branch_mappings);
+            return None;
+        };
+        // LLVM requires span of the decision contains all spans of its conditions.
+        // Usually the decision span meets the requirement well but in cases like macros it may not.
+        let span = branch_mappings
+            .iter()
+            .map(|branch| branch.span)
+            .reduce(|lhs, rhs| lhs.to(rhs))
+            .map(
+                |joint_span| {
+                    if decision_span.contains(joint_span) { decision_span } else { joint_span }
+                },
+            )
+            .expect("branch mappings are ensured to be non-empty as checked above");
+        Some((
+            MCDCDecision {
                 span,
                 end_bcbs,
                 bitmap_idx,
-                num_conditions: decision.num_conditions as u16,
+                num_test_vectors,
                 decision_depth: decision.decision_depth,
-            })
-        },
-    ));
+            },
+            branch_mappings,
+        ))
+    }));
+}
+
+// LLVM checks the executed test vector by accumulating indices of tested branches.
+// We calculate number of all possible test vectors of the decision and assign indices
+// to branches here.
+// See [the rfc](https://discourse.llvm.org/t/rfc-coverage-new-algorithm-and-file-format-for-mc-dc/76798/)
+// for more details about the algorithm.
+// This function is mostly like [`TVIdxBuilder::TvIdxBuilder`](https://github.com/llvm/llvm-project/blob/d594d9f7f4dc6eb748b3261917db689fdc348b96/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp#L226)
+fn calc_test_vectors_index(conditions: &mut Vec<MCDCBranch>) -> usize {
+    let mut indegree_stats = IndexVec::<ConditionId, usize>::from_elem_n(0, conditions.len());
+    // `num_paths` is `width` described at the llvm rfc, which indicates how many paths reaching the condition node.
+    let mut num_paths_stats = IndexVec::<ConditionId, usize>::from_elem_n(0, conditions.len());
+    let mut next_conditions = conditions
+        .iter_mut()
+        .map(|branch| {
+            let ConditionInfo { condition_id, true_next_id, false_next_id } = branch.condition_info;
+            [true_next_id, false_next_id]
+                .into_iter()
+                .filter_map(std::convert::identity)
+                .for_each(|next_id| indegree_stats[next_id] += 1);
+            (condition_id, branch)
+        })
+        .collect::<FxIndexMap<_, _>>();
+
+    let mut queue = std::collections::VecDeque::from_iter(
+        next_conditions.swap_remove(&ConditionId::START).into_iter(),
+    );
+    num_paths_stats[ConditionId::START] = 1;
+    let mut decision_end_nodes = Vec::new();
+    while let Some(branch) = queue.pop_front() {
+        let ConditionInfo { condition_id, true_next_id, false_next_id } = branch.condition_info;
+        let (false_index, true_index) = (&mut branch.false_index, &mut branch.true_index);
+        let this_paths_count = num_paths_stats[condition_id];
+        // Note. First check the false next to ensure conditions are touched in same order with llvm-cov.
+        for (next, index) in [(false_next_id, false_index), (true_next_id, true_index)] {
+            if let Some(next_id) = next {
+                let next_paths_count = &mut num_paths_stats[next_id];
+                *index = *next_paths_count;
+                *next_paths_count = next_paths_count.saturating_add(this_paths_count);
+                let next_indegree = &mut indegree_stats[next_id];
+                *next_indegree -= 1;
+                if *next_indegree == 0 {
+                    queue.push_back(next_conditions.swap_remove(&next_id).expect(
+                        "conditions with non-zero indegree before must be in next_conditions",
+                    ));
+                }
+            } else {
+                decision_end_nodes.push((this_paths_count, condition_id, index));
+            }
+        }
+    }
+    assert!(next_conditions.is_empty(), "the decision tree has untouched nodes");
+    let mut cur_idx = 0;
+    // LLVM hopes the end nodes are sorted in descending order by `num_paths` so that it can
+    // optimize bitmap size for decisions in tree form such as `a && b && c && d && ...`.
+    decision_end_nodes.sort_by_key(|(num_paths, _, _)| usize::MAX - *num_paths);
+    for (num_paths, condition_id, index) in decision_end_nodes {
+        assert_eq!(
+            num_paths, num_paths_stats[condition_id],
+            "end nodes should not be updated since they were visited"
+        );
+        assert_eq!(*index, usize::MAX, "end nodes should not be assigned index before");
+        *index = cur_idx;
+        cur_idx += num_paths;
+    }
+    cur_idx
 }
diff --git a/compiler/rustc_mir_transform/src/coverage/mod.rs b/compiler/rustc_mir_transform/src/coverage/mod.rs
index 79482ba3919..d0f30314e79 100644
--- a/compiler/rustc_mir_transform/src/coverage/mod.rs
+++ b/compiler/rustc_mir_transform/src/coverage/mod.rs
@@ -114,16 +114,16 @@ fn instrument_function_for_coverage<'tcx>(tcx: TyCtxt<'tcx>, mir_body: &mut mir:
     inject_mcdc_statements(mir_body, &basic_coverage_blocks, &extracted_mappings);
 
     let mcdc_num_condition_bitmaps = extracted_mappings
-        .mcdc_decisions
+        .mcdc_mappings
         .iter()
-        .map(|&mappings::MCDCDecision { decision_depth, .. }| decision_depth)
+        .map(|&(mappings::MCDCDecision { decision_depth, .. }, _)| decision_depth)
         .max()
         .map_or(0, |max| usize::from(max) + 1);
 
     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: extracted_mappings.mcdc_bitmap_bytes,
+        mcdc_bitmap_bits: extracted_mappings.mcdc_bitmap_bits,
         expressions: coverage_counters.into_expressions(),
         mappings,
         mcdc_num_condition_bitmaps,
@@ -161,9 +161,9 @@ fn create_mappings<'tcx>(
         num_bcbs: _,
         code_mappings,
         branch_pairs,
-        mcdc_bitmap_bytes: _,
-        mcdc_branches,
-        mcdc_decisions,
+        mcdc_bitmap_bits: _,
+        mcdc_degraded_branches,
+        mcdc_mappings,
     } = extracted_mappings;
     let mut mappings = Vec::new();
 
@@ -186,26 +186,79 @@ fn create_mappings<'tcx>(
         },
     ));
 
-    mappings.extend(mcdc_branches.iter().filter_map(
-        |&mappings::MCDCBranch { span, true_bcb, false_bcb, condition_info, decision_depth: _ }| {
+    let term_for_bcb =
+        |bcb| coverage_counters.term_for_bcb(bcb).expect("all BCBs with spans were given counters");
+
+    // MCDC branch mappings are appended with their decisions in case decisions were ignored.
+    mappings.extend(mcdc_degraded_branches.iter().filter_map(
+        |&mappings::MCDCBranch {
+             span,
+             true_bcb,
+             false_bcb,
+             condition_info: _,
+             true_index: _,
+             false_index: _,
+         }| {
             let source_region = region_for_span(span)?;
             let true_term = term_for_bcb(true_bcb);
             let false_term = term_for_bcb(false_bcb);
-            let kind = match condition_info {
-                Some(mcdc_params) => MappingKind::MCDCBranch { true_term, false_term, mcdc_params },
-                None => MappingKind::Branch { true_term, false_term },
-            };
-            Some(Mapping { kind, source_region })
+            Some(Mapping { kind: MappingKind::Branch { true_term, false_term }, source_region })
         },
     ));
 
-    mappings.extend(mcdc_decisions.iter().filter_map(
-        |&mappings::MCDCDecision { span, bitmap_idx, num_conditions, .. }| {
-            let source_region = region_for_span(span)?;
-            let kind = MappingKind::MCDCDecision(DecisionInfo { bitmap_idx, num_conditions });
-            Some(Mapping { kind, source_region })
-        },
-    ));
+    for (decision, branches) in mcdc_mappings {
+        let num_conditions = branches.len() as u16;
+        let conditions = branches
+            .into_iter()
+            .filter_map(
+                |&mappings::MCDCBranch {
+                     span,
+                     true_bcb,
+                     false_bcb,
+                     condition_info,
+                     true_index: _,
+                     false_index: _,
+                 }| {
+                    let source_region = region_for_span(span)?;
+                    let true_term = term_for_bcb(true_bcb);
+                    let false_term = term_for_bcb(false_bcb);
+                    Some(Mapping {
+                        kind: MappingKind::MCDCBranch {
+                            true_term,
+                            false_term,
+                            mcdc_params: condition_info,
+                        },
+                        source_region,
+                    })
+                },
+            )
+            .collect::<Vec<_>>();
+
+        if conditions.len() == num_conditions as usize
+            && let Some(source_region) = region_for_span(decision.span)
+        {
+            // LLVM requires end index for counter mapping regions.
+            let kind = MappingKind::MCDCDecision(DecisionInfo {
+                bitmap_idx: (decision.bitmap_idx + decision.num_test_vectors) as u32,
+                num_conditions,
+            });
+            mappings.extend(
+                std::iter::once(Mapping { kind, source_region }).chain(conditions.into_iter()),
+            );
+        } else {
+            mappings.extend(conditions.into_iter().map(|mapping| {
+                let MappingKind::MCDCBranch { true_term, false_term, mcdc_params: _ } =
+                    mapping.kind
+                else {
+                    unreachable!("all mappings here are MCDCBranch as shown above");
+                };
+                Mapping {
+                    kind: MappingKind::Branch { true_term, false_term },
+                    source_region: mapping.source_region,
+                }
+            }))
+        }
+    }
 
     mappings
 }
@@ -274,44 +327,41 @@ fn inject_mcdc_statements<'tcx>(
     basic_coverage_blocks: &CoverageGraph,
     extracted_mappings: &ExtractedMappings,
 ) {
-    // Inject test vector update first because `inject_statement` always insert new statement at
-    // head.
-    for &mappings::MCDCDecision {
-        span: _,
-        ref end_bcbs,
-        bitmap_idx,
-        num_conditions: _,
-        decision_depth,
-    } in &extracted_mappings.mcdc_decisions
-    {
-        for end in end_bcbs {
-            let end_bb = basic_coverage_blocks[*end].leader_bb();
+    for (decision, conditions) in &extracted_mappings.mcdc_mappings {
+        // Inject test vector update first because `inject_statement` always insert new statement at head.
+        for &end in &decision.end_bcbs {
+            let end_bb = basic_coverage_blocks[end].leader_bb();
             inject_statement(
                 mir_body,
-                CoverageKind::TestVectorBitmapUpdate { bitmap_idx, decision_depth },
+                CoverageKind::TestVectorBitmapUpdate {
+                    bitmap_idx: decision.bitmap_idx as u32,
+                    decision_depth: decision.decision_depth,
+                },
                 end_bb,
             );
         }
-    }
-
-    for &mappings::MCDCBranch { span: _, true_bcb, false_bcb, condition_info, decision_depth } in
-        &extracted_mappings.mcdc_branches
-    {
-        let Some(condition_info) = condition_info else { continue };
-        let id = condition_info.condition_id;
 
-        let true_bb = basic_coverage_blocks[true_bcb].leader_bb();
-        inject_statement(
-            mir_body,
-            CoverageKind::CondBitmapUpdate { id, value: true, decision_depth },
-            true_bb,
-        );
-        let false_bb = basic_coverage_blocks[false_bcb].leader_bb();
-        inject_statement(
-            mir_body,
-            CoverageKind::CondBitmapUpdate { id, value: false, decision_depth },
-            false_bb,
-        );
+        for &mappings::MCDCBranch {
+            span: _,
+            true_bcb,
+            false_bcb,
+            condition_info: _,
+            true_index,
+            false_index,
+        } in conditions
+        {
+            for (index, bcb) in [(false_index, false_bcb), (true_index, true_bcb)] {
+                let bb = basic_coverage_blocks[bcb].leader_bb();
+                inject_statement(
+                    mir_body,
+                    CoverageKind::CondBitmapUpdate {
+                        index: index as u32,
+                        decision_depth: decision.decision_depth,
+                    },
+                    bb,
+                );
+            }
+        }
     }
 }