Auto merge of #124255 - RenjiSann:renji/mcdc-nested-expressions, r=Zalathar

MCDC coverage: support nested decision coverage

#123409 provided the initial MCDC coverage implementation.

As referenced in #124144, it does not currently support "nested" decisions, like the following example :

```rust
fn nested_if_in_condition(a: bool, b: bool, c: bool) {
    if a && if b || c { true } else { false } {
        say("yes");
    } else {
        say("no");
    }
}
```

Note that there is an if-expression (`if b || c ...`) embedded inside a boolean expression in the decision of an outer if-expression.

This PR proposes a workaround for this cases, by introducing a Decision context stack, and by handing several `temporary condition bitmaps` instead of just one.
When instrumenting boolean expressions, if the current node is a leaf condition (i.e. not a `||`/`&&` logical operator nor a `!` not operator), we insert a new decision context, such that if there are more boolean expressions inside the condition, they are handled as separate expressions.

On the codegen LLVM side, we allocate as many `temp_cond_bitmap`s as necessary to handle the maximum encountered decision depth.

2 files changed, 41 insertions, 20 deletions

diff --git a/compiler/rustc_codegen_llvm/src/builder.rs b/compiler/rustc_codegen_llvm/src/builder.rs
index f7546039540..5c8f358d03a 100644
--- a/compiler/rustc_codegen_llvm/src/builder.rs
+++ b/compiler/rustc_codegen_llvm/src/builder.rs
@@ -27,6 +27,7 @@ use rustc_target::abi::{self, call::FnAbi, Align, Size, WrappingRange};
 use rustc_target::spec::{HasTargetSpec, SanitizerSet, Target};
 use smallvec::SmallVec;
 use std::borrow::Cow;
+use std::ffi::CString;
 use std::iter;
 use std::ops::Deref;
 use std::ptr;
@@ -1709,7 +1710,8 @@ impl<'a, 'll, 'tcx> Builder<'a, 'll, 'tcx> {
         fn_name: &'ll Value,
         hash: &'ll Value,
         bitmap_bytes: &'ll Value,
-    ) -> &'ll Value {
+        max_decision_depth: u32,
+    ) -> Vec<&'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");
@@ -1722,6 +1724,8 @@ impl<'a, 'll, 'tcx> Builder<'a, 'll, 'tcx> {
         let args = &[fn_name, hash, bitmap_bytes];
         let args = self.check_call("call", llty, llfn, args);
 
+        let mut cond_bitmaps = vec![];
+
         unsafe {
             let _ = llvm::LLVMRustBuildCall(
                 self.llbuilder,
@@ -1733,17 +1737,22 @@ impl<'a, 'll, 'tcx> Builder<'a, 'll, 'tcx> {
                 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
+            for i in 0..=max_decision_depth {
+                let mut bx = Builder::with_cx(self.cx);
+                bx.position_at_start(llvm::LLVMGetFirstBasicBlock(self.llfn()));
+
+                let name = CString::new(format!("mcdc.addr.{i}")).unwrap();
+                let cond_bitmap = {
+                    let alloca =
+                        llvm::LLVMBuildAlloca(bx.llbuilder, bx.cx.type_i32(), name.as_ptr());
+                    llvm::LLVMSetAlignment(alloca, 4);
+                    alloca
+                };
+                bx.store(self.const_i32(0), cond_bitmap, self.tcx().data_layout.i32_align.abi);
+                cond_bitmaps.push(cond_bitmap);
+            }
         }
+        cond_bitmaps
     }
 
     pub(crate) fn mcdc_tvbitmap_update(
diff --git a/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs b/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
index 085ce15d81f..679c6e1a2ff 100644
--- a/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
+++ b/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
@@ -30,7 +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>>,
+    pub(crate) mcdc_condition_bitmap_map: RefCell<FxHashMap<Instance<'tcx>, Vec<&'ll llvm::Value>>>,
 }
 
 impl<'ll, 'tcx> CrateCoverageContext<'ll, 'tcx> {
@@ -49,9 +49,20 @@ impl<'ll, 'tcx> CrateCoverageContext<'ll, 'tcx> {
     }
 
     /// 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()
+    /// In order to handle nested decisions, several condition bitmaps can be
+    /// allocated for a function body.
+    /// These values are named `mcdc.addr.{i}` and are a 32-bit integers.
+    /// They respectively hold the condition bitmaps for decisions with a depth of `i`.
+    fn try_get_mcdc_condition_bitmap(
+        &self,
+        instance: &Instance<'tcx>,
+        decision_depth: u16,
+    ) -> Option<&'ll llvm::Value> {
+        self.mcdc_condition_bitmap_map
+            .borrow()
+            .get(instance)
+            .and_then(|bitmap_map| bitmap_map.get(decision_depth as usize))
+            .copied() // Dereference Option<&&Value> to Option<&Value>
     }
 }
 
@@ -143,7 +154,7 @@ impl<'tcx> CoverageInfoBuilderMethods<'tcx> for Builder<'_, '_, 'tcx> {
             CoverageKind::ExpressionUsed { id } => {
                 func_coverage.mark_expression_id_seen(id);
             }
-            CoverageKind::CondBitmapUpdate { id, value, .. } => {
+            CoverageKind::CondBitmapUpdate { id, value, decision_depth } => {
                 drop(coverage_map);
                 assert_ne!(
                     id.as_u32(),
@@ -151,7 +162,7 @@ impl<'tcx> CoverageInfoBuilderMethods<'tcx> for Builder<'_, '_, 'tcx> {
                     "ConditionId of evaluated conditions should never be zero"
                 );
                 let cond_bitmap = coverage_context
-                    .try_get_mcdc_condition_bitmap(&instance)
+                    .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);
@@ -159,10 +170,10 @@ impl<'tcx> CoverageInfoBuilderMethods<'tcx> for Builder<'_, '_, 'tcx> {
                 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 } => {
+            CoverageKind::TestVectorBitmapUpdate { bitmap_idx, decision_depth } => {
                 drop(coverage_map);
                 let cond_bitmap = coverage_context
-                                    .try_get_mcdc_condition_bitmap(&instance)
+                                    .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 = bx.tcx().coverage_ids_info(instance.def).mcdc_bitmap_bytes;
                 assert!(bitmap_idx < bitmap_bytes, "bitmap index of the decision out of range");
@@ -195,7 +206,8 @@ fn ensure_mcdc_parameters<'ll, 'tcx>(
     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);
+    let max_decision_depth = function_coverage_info.mcdc_max_decision_depth;
+    let cond_bitmap = bx.mcdc_parameters(fn_name, hash, bitmap_bytes, max_decision_depth as u32);
     bx.coverage_context()
         .expect("already checked above")
         .mcdc_condition_bitmap_map