Rollup merge of #123409 - ZhuUx:master, r=oli-obk

Implement Modified Condition/Decision  Coverage

This is an implementation based on llvm backend support (>= 18) by `@evodius96` and branch coverage support by `@Zalathar.`

### Major changes:

* Add -Zcoverage-options=mcdc as switch. Now coverage options accept either `no-branch`, `branch`, or `mcdc`. `mcdc` also enables `branch` because it is essential to work.
* Add coverage mapping for MCDCBranch and MCDCDecision. Note that MCDCParameter evolves from  llvm 18 to llvm 19. The mapping in rust side mainly references to 19 and is casted to 18 types in llvm wrapper.
* Add wrapper for mcdc instrinc functions from llvm. And inject associated statements to mir.
* Add BcbMappingKind::Decision, I'm not sure is it proper but can't find a better way temporarily.
* Let coverage-dump support parsing MCDCBranch and MCDCDecision from llvm ir.
* Add simple tests to check whether mcdc works.
* Same as clang, currently rustc does not generate instrument for decision with more than 6 condtions or only 1 condition due to considerations of resource.

### Implementation Details

1. To get information about conditions and decisions, `MCDCState` in `BranchInfoBuilder` is used during hir lowering to mir. For expressions with logical op we call `Builder::visit_coverage_branch_operation` to record its sub conditions, generate condition ids for them and save their spans (to construct the span of whole decision). This process mainly references to the implementation in clang and is described in comments over `MCDCState::record_conditions`. Also true marks and false marks introduced by branch coverage are used to detect where the decision evaluation ends: the next id  of the condition == 0.
2. Once the `MCDCState::decision_stack` popped all recorded conditions, we can ensure that the decision is checked over and push it into `decision_spans`. We do not manually insert decision span to avoid complexity from then_else_break in nested if scopes.
3. When constructing CoverageSpans, add condition info to BcbMappingKind::Branch and decision info to BcbMappingKind::Decision. If the branch mapping has non-zero condition id it will be transformed to MCDCBranch mapping and insert `CondBitmapUpdate` statements to its evaluated blocks. While decision bcb mapping will insert `TestVectorBitmapUpdate` in all its end blocks.

### Usage
```bash
 echo "[build]\nprofiler=true" >> config.toml
./x build --stage 1
./x test tests/coverage/mcdc_if.rs
```
to build the compiler and run tests.

```shell
export PATH=path/to/llvm-build:$PATH
rustup toolchain link mcdc build/host/stage1
cargo +mcdc rustc --bin foo -- -Cinstrument-coverage -Zcoverage-options=mcdc
cd target/debug
LLVM_PROFILE_FILE="foo.profraw" ./foo
llvm-profdata merge -sparse foo.profraw -o foo.profdata
llvm-cov show ./foo -instr-profile=foo.profdata --show-mcdc
```
to check "foo" code.

### Problems to solve

For now decision mapping will insert statements to its all end blocks, which may be optimized by inserting a final block of the decision. To do this we must also trace the evaluated value at each end of the decision and join them separately.

This implementation is not heavily tested so there should be some unrevealed issues. We are going to check our rust products in the next.  Please let me know if you had any suggestions or comments.

4 files changed, 355 insertions, 3 deletions

diff --git a/compiler/rustc_codegen_llvm/src/builder.rs b/compiler/rustc_codegen_llvm/src/builder.rs
index 160f361b9b5..4c2bdb2f5ec 100644
--- a/compiler/rustc_codegen_llvm/src/builder.rs
+++ b/compiler/rustc_codegen_llvm/src/builder.rs
@@ -17,7 +17,7 @@ use rustc_data_structures::small_c_str::SmallCStr;
 use rustc_hir::def_id::DefId;
 use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrs;
 use rustc_middle::ty::layout::{
-    FnAbiError, FnAbiOfHelpers, FnAbiRequest, LayoutError, LayoutOfHelpers, TyAndLayout,
+    FnAbiError, FnAbiOfHelpers, FnAbiRequest, HasTyCtxt, LayoutError, LayoutOfHelpers, TyAndLayout,
 };
 use rustc_middle::ty::{self, Instance, Ty, TyCtxt};
 use rustc_sanitizers::{cfi, kcfi};
@@ -1702,4 +1702,128 @@ impl<'a, 'll, 'tcx> Builder<'a, 'll, 'tcx> {
         };
         kcfi_bundle
     }
+
+    pub(crate) fn mcdc_parameters(
+        &mut self,
+        fn_name: &'ll Value,
+        hash: &'ll Value,
+        bitmap_bytes: &'ll Value,
+    ) -> &'ll Value {
+        debug!("mcdc_parameters() with args ({:?}, {:?}, {:?})", fn_name, hash, bitmap_bytes);
+
+        assert!(llvm_util::get_version() >= (18, 0, 0), "MCDC intrinsics require LLVM 18 or later");
+
+        let llfn = unsafe { llvm::LLVMRustGetInstrProfMCDCParametersIntrinsic(self.cx().llmod) };
+        let llty = self.cx.type_func(
+            &[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 = 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,
+            );
+            // Create condition bitmap named `mcdc.addr`.
+            let mut bx = Builder::with_cx(self.cx);
+            bx.position_at_start(llvm::LLVMGetFirstBasicBlock(self.llfn()));
+            let cond_bitmap = {
+                let alloca =
+                    llvm::LLVMBuildAlloca(bx.llbuilder, bx.cx.type_i32(), c"mcdc.addr".as_ptr());
+                llvm::LLVMSetAlignment(alloca, 4);
+                alloca
+            };
+            bx.store(self.const_i32(0), cond_bitmap, self.tcx().data_layout.i32_align.abi);
+            cond_bitmap
+        }
+    }
+
+    pub(crate) fn mcdc_tvbitmap_update(
+        &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
+        );
+        assert!(llvm_util::get_version() >= (18, 0, 0), "MCDC intrinsics require LLVM 18 or later");
+
+        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_void(),
+        );
+        let args = &[fn_name, hash, bitmap_bytes, bitmap_index, mcdc_temp];
+        let args = 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 i32_align = self.tcx().data_layout.i32_align.abi;
+        self.store(self.const_i32(0), mcdc_temp, i32_align);
+    }
+
+    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
+        );
+        assert!(llvm_util::get_version() >= (18, 0, 0), "MCDC intrinsics require LLVM 18 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,
+            );
+        }
+    }
 }
diff --git a/compiler/rustc_codegen_llvm/src/coverageinfo/ffi.rs b/compiler/rustc_codegen_llvm/src/coverageinfo/ffi.rs
index 2af28146a51..12a846a49ec 100644
--- a/compiler/rustc_codegen_llvm/src/coverageinfo/ffi.rs
+++ b/compiler/rustc_codegen_llvm/src/coverageinfo/ffi.rs
@@ -1,4 +1,6 @@
-use rustc_middle::mir::coverage::{CodeRegion, CounterId, CovTerm, ExpressionId, MappingKind};
+use rustc_middle::mir::coverage::{
+    CodeRegion, ConditionInfo, CounterId, CovTerm, DecisionInfo, ExpressionId, MappingKind,
+};
 
 /// Must match the layout of `LLVMRustCounterKind`.
 #[derive(Copy, Clone, Debug)]
@@ -99,6 +101,86 @@ pub enum RegionKind {
     /// associated with two counters, each representing the number of times the
     /// expression evaluates to true or false.
     BranchRegion = 4,
+
+    /// A DecisionRegion represents a top-level boolean expression and is
+    /// associated with a variable length bitmap index and condition number.
+    MCDCDecisionRegion = 5,
+
+    /// A Branch Region can be extended to include IDs to facilitate MC/DC.
+    MCDCBranchRegion = 6,
+}
+
+pub mod mcdc {
+    use rustc_middle::mir::coverage::{ConditionInfo, DecisionInfo};
+
+    /// Must match the layout of `LLVMRustMCDCDecisionParameters`.
+    #[repr(C)]
+    #[derive(Clone, Copy, Debug, Default)]
+    pub struct DecisionParameters {
+        bitmap_idx: u32,
+        conditions_num: u16,
+    }
+
+    // ConditionId in llvm is `unsigned int` at 18 while `int16_t` at [19](https://github.com/llvm/llvm-project/pull/81257)
+    type LLVMConditionId = i16;
+
+    /// Must match the layout of `LLVMRustMCDCBranchParameters`.
+    #[repr(C)]
+    #[derive(Clone, Copy, Debug, Default)]
+    pub struct BranchParameters {
+        condition_id: LLVMConditionId,
+        condition_ids: [LLVMConditionId; 2],
+    }
+
+    #[repr(C)]
+    #[derive(Clone, Copy, Debug)]
+    pub enum ParameterTag {
+        None = 0,
+        Decision = 1,
+        Branch = 2,
+    }
+    /// Same layout with `LLVMRustMCDCParameters`
+    #[repr(C)]
+    #[derive(Clone, Copy, Debug)]
+    pub struct Parameters {
+        tag: ParameterTag,
+        decision_params: DecisionParameters,
+        branch_params: BranchParameters,
+    }
+
+    impl Parameters {
+        pub fn none() -> Self {
+            Self {
+                tag: ParameterTag::None,
+                decision_params: Default::default(),
+                branch_params: Default::default(),
+            }
+        }
+        pub fn decision(decision_params: DecisionParameters) -> Self {
+            Self { tag: ParameterTag::Decision, decision_params, branch_params: Default::default() }
+        }
+        pub fn branch(branch_params: BranchParameters) -> Self {
+            Self { tag: ParameterTag::Branch, decision_params: Default::default(), branch_params }
+        }
+    }
+
+    impl From<ConditionInfo> for BranchParameters {
+        fn from(value: ConditionInfo) -> Self {
+            Self {
+                condition_id: value.condition_id.as_u32() as LLVMConditionId,
+                condition_ids: [
+                    value.false_next_id.as_u32() as LLVMConditionId,
+                    value.true_next_id.as_u32() as LLVMConditionId,
+                ],
+            }
+        }
+    }
+
+    impl From<DecisionInfo> for DecisionParameters {
+        fn from(value: DecisionInfo) -> Self {
+            Self { bitmap_idx: value.bitmap_idx, conditions_num: value.conditions_num }
+        }
+    }
 }
 
 /// This struct provides LLVM's representation of a "CoverageMappingRegion", encoded into the
@@ -122,6 +204,7 @@ pub struct CounterMappingRegion {
     /// for the false branch of the region.
     false_counter: Counter,
 
+    mcdc_params: mcdc::Parameters,
     /// An indirect reference to the source filename. In the LLVM Coverage Mapping Format, the
     /// file_id is an index into a function-specific `virtual_file_mapping` array of indexes
     /// that, in turn, are used to look up the filename for this region.
@@ -173,6 +256,26 @@ impl CounterMappingRegion {
                 end_line,
                 end_col,
             ),
+            MappingKind::MCDCBranch { true_term, false_term, mcdc_params } => {
+                Self::mcdc_branch_region(
+                    Counter::from_term(true_term),
+                    Counter::from_term(false_term),
+                    mcdc_params,
+                    local_file_id,
+                    start_line,
+                    start_col,
+                    end_line,
+                    end_col,
+                )
+            }
+            MappingKind::MCDCDecision(decision_info) => Self::decision_region(
+                decision_info,
+                local_file_id,
+                start_line,
+                start_col,
+                end_line,
+                end_col,
+            ),
         }
     }
 
@@ -187,6 +290,7 @@ impl CounterMappingRegion {
         Self {
             counter,
             false_counter: Counter::ZERO,
+            mcdc_params: mcdc::Parameters::none(),
             file_id,
             expanded_file_id: 0,
             start_line,
@@ -209,6 +313,7 @@ impl CounterMappingRegion {
         Self {
             counter,
             false_counter,
+            mcdc_params: mcdc::Parameters::none(),
             file_id,
             expanded_file_id: 0,
             start_line,
@@ -219,6 +324,54 @@ impl CounterMappingRegion {
         }
     }
 
+    pub(crate) fn mcdc_branch_region(
+        counter: Counter,
+        false_counter: Counter,
+        condition_info: ConditionInfo,
+        file_id: u32,
+        start_line: u32,
+        start_col: u32,
+        end_line: u32,
+        end_col: u32,
+    ) -> Self {
+        Self {
+            counter,
+            false_counter,
+            mcdc_params: mcdc::Parameters::branch(condition_info.into()),
+            file_id,
+            expanded_file_id: 0,
+            start_line,
+            start_col,
+            end_line,
+            end_col,
+            kind: RegionKind::MCDCBranchRegion,
+        }
+    }
+
+    pub(crate) fn decision_region(
+        decision_info: DecisionInfo,
+        file_id: u32,
+        start_line: u32,
+        start_col: u32,
+        end_line: u32,
+        end_col: u32,
+    ) -> Self {
+        let mcdc_params = mcdc::Parameters::decision(decision_info.into());
+
+        Self {
+            counter: Counter::ZERO,
+            false_counter: Counter::ZERO,
+            mcdc_params,
+            file_id,
+            expanded_file_id: 0,
+            start_line,
+            start_col,
+            end_line,
+            end_col,
+            kind: RegionKind::MCDCDecisionRegion,
+        }
+    }
+
     // This function might be used in the future; the LLVM API is still evolving, as is coverage
     // support.
     #[allow(dead_code)]
@@ -233,6 +386,7 @@ impl CounterMappingRegion {
         Self {
             counter: Counter::ZERO,
             false_counter: Counter::ZERO,
+            mcdc_params: mcdc::Parameters::none(),
             file_id,
             expanded_file_id,
             start_line,
@@ -256,6 +410,7 @@ impl CounterMappingRegion {
         Self {
             counter: Counter::ZERO,
             false_counter: Counter::ZERO,
+            mcdc_params: mcdc::Parameters::none(),
             file_id,
             expanded_file_id: 0,
             start_line,
@@ -280,6 +435,7 @@ impl CounterMappingRegion {
         Self {
             counter,
             false_counter: Counter::ZERO,
+            mcdc_params: mcdc::Parameters::none(),
             file_id,
             expanded_file_id: 0,
             start_line,
diff --git a/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs b/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
index 140566e8da9..085ce15d81f 100644
--- a/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
+++ b/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
@@ -13,7 +13,7 @@ use rustc_codegen_ssa::traits::{
 use rustc_data_structures::fx::{FxHashMap, FxIndexMap};
 use rustc_llvm::RustString;
 use rustc_middle::bug;
-use rustc_middle::mir::coverage::CoverageKind;
+use rustc_middle::mir::coverage::{CoverageKind, FunctionCoverageInfo};
 use rustc_middle::ty::layout::HasTyCtxt;
 use rustc_middle::ty::Instance;
 use rustc_target::abi::Align;
@@ -30,6 +30,7 @@ pub struct CrateCoverageContext<'ll, 'tcx> {
     pub(crate) function_coverage_map:
         RefCell<FxIndexMap<Instance<'tcx>, FunctionCoverageCollector<'tcx>>>,
     pub(crate) pgo_func_name_var_map: RefCell<FxHashMap<Instance<'tcx>, &'ll llvm::Value>>,
+    pub(crate) mcdc_condition_bitmap_map: RefCell<FxHashMap<Instance<'tcx>, &'ll llvm::Value>>,
 }
 
 impl<'ll, 'tcx> CrateCoverageContext<'ll, 'tcx> {
@@ -37,6 +38,7 @@ impl<'ll, 'tcx> CrateCoverageContext<'ll, 'tcx> {
         Self {
             function_coverage_map: Default::default(),
             pgo_func_name_var_map: Default::default(),
+            mcdc_condition_bitmap_map: Default::default(),
         }
     }
 
@@ -45,6 +47,12 @@ impl<'ll, 'tcx> CrateCoverageContext<'ll, 'tcx> {
     ) -> FxIndexMap<Instance<'tcx>, FunctionCoverageCollector<'tcx>> {
         self.function_coverage_map.replace(FxIndexMap::default())
     }
+
+    /// LLVM use a temp value to record evaluated mcdc test vector of each decision, which is called condition bitmap.
+    /// This value is named `mcdc.addr` (same as clang) and is a 32-bit integer.
+    fn try_get_mcdc_condition_bitmap(&self, instance: &Instance<'tcx>) -> Option<&'ll llvm::Value> {
+        self.mcdc_condition_bitmap_map.borrow().get(instance).copied()
+    }
 }
 
 // These methods used to be part of trait `CoverageInfoMethods`, which no longer
@@ -90,6 +98,10 @@ impl<'tcx> CoverageInfoBuilderMethods<'tcx> for Builder<'_, '_, 'tcx> {
             return;
         };
 
+        if function_coverage_info.mcdc_bitmap_bytes > 0 {
+            ensure_mcdc_parameters(bx, instance, function_coverage_info);
+        }
+
         let Some(coverage_context) = bx.coverage_context() else { return };
         let mut coverage_map = coverage_context.function_coverage_map.borrow_mut();
         let func_coverage = coverage_map
@@ -131,10 +143,66 @@ impl<'tcx> CoverageInfoBuilderMethods<'tcx> for Builder<'_, '_, 'tcx> {
             CoverageKind::ExpressionUsed { id } => {
                 func_coverage.mark_expression_id_seen(id);
             }
+            CoverageKind::CondBitmapUpdate { id, value, .. } => {
+                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)
+                    .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);
+            }
+            CoverageKind::TestVectorBitmapUpdate { bitmap_idx } => {
+                drop(coverage_map);
+                let cond_bitmap = coverage_context
+                                    .try_get_mcdc_condition_bitmap(&instance)
+                                    .expect("mcdc cond bitmap should have been allocated for merging into the global bitmap");
+                let bitmap_bytes = bx.tcx().coverage_ids_info(instance.def).mcdc_bitmap_bytes;
+                assert!(bitmap_idx < bitmap_bytes, "bitmap index of the decision out of range");
+                assert!(
+                    bitmap_bytes <= function_coverage_info.mcdc_bitmap_bytes,
+                    "bitmap length disagreement: query says {bitmap_bytes} but function info only has {}",
+                    function_coverage_info.mcdc_bitmap_bytes
+                );
+
+                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);
+            }
         }
     }
 }
 
+fn ensure_mcdc_parameters<'ll, 'tcx>(
+    bx: &mut Builder<'_, 'll, 'tcx>,
+    instance: Instance<'tcx>,
+    function_coverage_info: &FunctionCoverageInfo,
+) {
+    let Some(cx) = bx.coverage_context() else { return };
+    if cx.mcdc_condition_bitmap_map.borrow().contains_key(&instance) {
+        return;
+    }
+
+    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(function_coverage_info.mcdc_bitmap_bytes);
+    let cond_bitmap = bx.mcdc_parameters(fn_name, hash, bitmap_bytes);
+    bx.coverage_context()
+        .expect("already checked above")
+        .mcdc_condition_bitmap_map
+        .borrow_mut()
+        .insert(instance, cond_bitmap);
+}
+
 /// Calls llvm::createPGOFuncNameVar() with the given function instance's
 /// mangled function name. The LLVM API returns an llvm::GlobalVariable
 /// containing the function name, with the specific variable name and linkage
diff --git a/compiler/rustc_codegen_llvm/src/llvm/ffi.rs b/compiler/rustc_codegen_llvm/src/llvm/ffi.rs
index 83158f6f1d5..a10dc61967e 100644
--- a/compiler/rustc_codegen_llvm/src/llvm/ffi.rs
+++ b/compiler/rustc_codegen_llvm/src/llvm/ffi.rs
@@ -1631,6 +1631,10 @@ extern "C" {
 
     // Miscellaneous instructions
     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>,
         Ty: &'a Type,