diff options
| -rw-r--r-- | compiler/rustc_codegen_llvm/src/coverageinfo/ffi.rs | 158 | ||||
| -rw-r--r-- | compiler/rustc_llvm/llvm-wrapper/CoverageMappingWrapper.cpp | 94 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/mir/coverage.rs | 104 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/mir/pretty.rs | 24 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/structural_impls.rs | 1 | ||||
| -rw-r--r-- | compiler/rustc_mir_build/src/build/coverageinfo.rs | 255 | ||||
| -rw-r--r-- | compiler/rustc_mir_build/src/build/matches/mod.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/mod.rs | 79 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/spans.rs | 34 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/spans/from_mir.rs | 69 |
10 files changed, 779 insertions, 41 deletions
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_llvm/llvm-wrapper/CoverageMappingWrapper.cpp b/compiler/rustc_llvm/llvm-wrapper/CoverageMappingWrapper.cpp index 0998b463a88..e842f47f48c 100644 --- a/compiler/rustc_llvm/llvm-wrapper/CoverageMappingWrapper.cpp +++ b/compiler/rustc_llvm/llvm-wrapper/CoverageMappingWrapper.cpp @@ -4,8 +4,6 @@ #include "llvm/ProfileData/Coverage/CoverageMappingWriter.h" #include "llvm/ProfileData/InstrProf.h" -#include <iostream> - using namespace llvm; // FFI equivalent of enum `llvm::coverage::Counter::CounterKind` @@ -43,6 +41,8 @@ enum class LLVMRustCounterMappingRegionKind { SkippedRegion = 2, GapRegion = 3, BranchRegion = 4, + MCDCDecisionRegion = 5, + MCDCBranchRegion = 6 }; static coverage::CounterMappingRegion::RegionKind @@ -58,15 +58,102 @@ fromRust(LLVMRustCounterMappingRegionKind Kind) { return coverage::CounterMappingRegion::GapRegion; case LLVMRustCounterMappingRegionKind::BranchRegion: return coverage::CounterMappingRegion::BranchRegion; +#if LLVM_VERSION_GE(18, 0) + case LLVMRustCounterMappingRegionKind::MCDCDecisionRegion: + return coverage::CounterMappingRegion::MCDCDecisionRegion; + case LLVMRustCounterMappingRegionKind::MCDCBranchRegion: + return coverage::CounterMappingRegion::MCDCBranchRegion; +#else + case LLVMRustCounterMappingRegionKind::MCDCDecisionRegion: + break; + case LLVMRustCounterMappingRegionKind::MCDCBranchRegion: + break; +#endif } report_fatal_error("Bad LLVMRustCounterMappingRegionKind!"); } +enum LLVMRustMCDCParametersTag { + None = 0, + Decision = 1, + Branch = 2, +}; + +struct LLVMRustMCDCDecisionParameters { + uint32_t BitmapIdx; + uint16_t NumConditions; +}; + +struct LLVMRustMCDCBranchParameters { + int16_t ConditionID; + int16_t ConditionIDs[2]; +}; + +struct LLVMRustMCDCParameters { + LLVMRustMCDCParametersTag Tag; + LLVMRustMCDCDecisionParameters DecisionParameters; + LLVMRustMCDCBranchParameters BranchParameters; +}; + +// LLVM representations for `MCDCParameters` evolved from LLVM 18 to 19. +// Look at representations in 18 +// https://github.com/rust-lang/llvm-project/blob/66a2881a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h#L253-L263 +// and representations in 19 +// https://github.com/llvm/llvm-project/blob/843cc474faefad1d639f4c44c1cf3ad7dbda76c8/llvm/include/llvm/ProfileData/Coverage/MCDCTypes.h +#if LLVM_VERSION_GE(18, 0) && LLVM_VERSION_LT(19, 0) +static coverage::CounterMappingRegion::MCDCParameters +fromRust(LLVMRustMCDCParameters Params) { + auto parameter = coverage::CounterMappingRegion::MCDCParameters{}; + switch (Params.Tag) { + case LLVMRustMCDCParametersTag::None: + return parameter; + case LLVMRustMCDCParametersTag::Decision: + parameter.BitmapIdx = + static_cast<unsigned>(Params.DecisionParameters.BitmapIdx), + parameter.NumConditions = + static_cast<unsigned>(Params.DecisionParameters.NumConditions); + return parameter; + case LLVMRustMCDCParametersTag::Branch: + parameter.ID = static_cast<coverage::CounterMappingRegion::MCDCConditionID>( + Params.BranchParameters.ConditionID), + parameter.FalseID = + static_cast<coverage::CounterMappingRegion::MCDCConditionID>( + Params.BranchParameters.ConditionIDs[0]), + parameter.TrueID = + static_cast<coverage::CounterMappingRegion::MCDCConditionID>( + Params.BranchParameters.ConditionIDs[1]); + return parameter; + } + report_fatal_error("Bad LLVMRustMCDCParametersTag!"); +} +#elif LLVM_VERSION_GE(19, 0) +static coverage::mcdc::Parameters fromRust(LLVMRustMCDCParameters Params) { + switch (Params.Tag) { + case LLVMRustMCDCParametersTag::None: + return std::monostate(); + case LLVMRustMCDCParametersTag::Decision: + return coverage::mcdc::DecisionParameters( + Params.DecisionParameters.BitmapIdx, + Params.DecisionParameters.NumConditions); + case LLVMRustMCDCParametersTag::Branch: + return coverage::mcdc::BranchParameters( + static_cast<coverage::mcdc::ConditionID>( + Params.BranchParameters.ConditionID), + {static_cast<coverage::mcdc::ConditionID>( + Params.BranchParameters.ConditionIDs[0]), + static_cast<coverage::mcdc::ConditionID>( + Params.BranchParameters.ConditionIDs[1])}); + } + report_fatal_error("Bad LLVMRustMCDCParametersTag!"); +} +#endif + // FFI equivalent of struct `llvm::coverage::CounterMappingRegion` // https://github.com/rust-lang/llvm-project/blob/ea6fa9c2/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h#L211-L304 struct LLVMRustCounterMappingRegion { LLVMRustCounter Count; LLVMRustCounter FalseCount; + LLVMRustMCDCParameters MCDCParameters; uint32_t FileID; uint32_t ExpandedFileID; uint32_t LineStart; @@ -135,7 +222,8 @@ extern "C" void LLVMRustCoverageWriteMappingToBuffer( MappingRegions.emplace_back( fromRust(Region.Count), fromRust(Region.FalseCount), #if LLVM_VERSION_GE(18, 0) && LLVM_VERSION_LT(19, 0) - coverage::CounterMappingRegion::MCDCParameters{}, + // LLVM 19 may move this argument to last. + fromRust(Region.MCDCParameters), #endif Region.FileID, Region.ExpandedFileID, // File IDs, then region info. Region.LineStart, Region.ColumnStart, Region.LineEnd, Region.ColumnEnd, diff --git a/compiler/rustc_middle/src/mir/coverage.rs b/compiler/rustc_middle/src/mir/coverage.rs index 582a1806688..b1d0c815ae0 100644 --- a/compiler/rustc_middle/src/mir/coverage.rs +++ b/compiler/rustc_middle/src/mir/coverage.rs @@ -51,6 +51,25 @@ rustc_index::newtype_index! { pub struct ExpressionId {} } +rustc_index::newtype_index! { + /// ID of a mcdc condition. Used by llvm to check mcdc coverage. + /// + /// Note for future: the max limit of 0xFFFF is probably too loose. Actually llvm does not + /// support decisions with too many conditions (7 and more at LLVM 18 while may be hundreds at 19) + /// and represents it with `int16_t`. This max value may be changed once we could + /// figure out an accurate limit. + #[derive(HashStable)] + #[encodable] + #[orderable] + #[max = 0xFFFF] + #[debug_format = "ConditionId({})"] + pub struct ConditionId {} +} + +impl ConditionId { + pub const NONE: Self = Self::from_u32(0); +} + /// Enum that can hold a constant zero value, the ID of an physical coverage /// counter, or the ID of a coverage-counter expression. /// @@ -106,6 +125,22 @@ pub enum CoverageKind { /// mappings. Intermediate expressions with no direct mappings are /// retained/zeroed based on whether they are transitively used.) ExpressionUsed { id: ExpressionId }, + + /// 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. + /// + /// If this statement does not survive MIR optimizations, the condition would never be + /// taken as evaluated. + CondBitmapUpdate { id: ConditionId, value: bool }, + + /// Marks the point in MIR control flow represented by a evaluated decision. + /// + /// This is eventually lowered to `llvm.instrprof.mcdc.tvbitmap.update` in LLVM IR. + /// + /// If this statement does not survive MIR optimizations, the decision would never be + /// taken as evaluated. + TestVectorBitmapUpdate { bitmap_idx: u32 }, } impl Debug for CoverageKind { @@ -116,6 +151,12 @@ 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 } => { + write!(fmt, "CondBitmapUpdate({:?}, {:?})", id.index(), value) + } + TestVectorBitmapUpdate { bitmap_idx } => { + write!(fmt, "TestVectorUpdate({:?})", bitmap_idx) + } } } } @@ -172,16 +213,23 @@ pub enum MappingKind { Code(CovTerm), /// Associates a branch region with separate counters for true and false. Branch { true_term: CovTerm, false_term: CovTerm }, + /// Associates a branch region with separate counters for true and false. + MCDCBranch { true_term: CovTerm, false_term: CovTerm, mcdc_params: ConditionInfo }, + /// Associates a decision region with a bitmap and number of conditions. + MCDCDecision(DecisionInfo), } impl MappingKind { /// Iterator over all coverage terms in this mapping kind. pub fn terms(&self) -> impl Iterator<Item = CovTerm> { - let one = |a| std::iter::once(a).chain(None); - let two = |a, b| std::iter::once(a).chain(Some(b)); + let zero = || None.into_iter().chain(None); + let one = |a| Some(a).into_iter().chain(None); + let two = |a, b| Some(a).into_iter().chain(Some(b)); match *self { Self::Code(term) => one(term), Self::Branch { true_term, false_term } => two(true_term, false_term), + Self::MCDCBranch { true_term, false_term, .. } => two(true_term, false_term), + Self::MCDCDecision(_) => zero(), } } @@ -193,6 +241,12 @@ impl MappingKind { Self::Branch { true_term, false_term } => { Self::Branch { true_term: map_fn(true_term), false_term: map_fn(false_term) } } + Self::MCDCBranch { true_term, false_term, mcdc_params } => Self::MCDCBranch { + true_term: map_fn(true_term), + false_term: map_fn(false_term), + mcdc_params, + }, + Self::MCDCDecision(param) => Self::MCDCDecision(param), } } } @@ -212,7 +266,7 @@ pub struct Mapping { pub struct FunctionCoverageInfo { pub function_source_hash: u64, pub num_counters: usize, - + pub mcdc_bitmap_bytes: u32, pub expressions: IndexVec<ExpressionId, Expression>, pub mappings: Vec<Mapping>, } @@ -226,6 +280,8 @@ pub struct BranchInfo { /// 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>, } #[derive(Clone, Debug)] @@ -235,3 +291,45 @@ pub struct BranchSpan { pub true_marker: BlockMarkerId, pub false_marker: BlockMarkerId, } + +#[derive(Copy, Clone, Debug)] +#[derive(TyEncodable, TyDecodable, Hash, HashStable, TypeFoldable, TypeVisitable)] +pub struct ConditionInfo { + pub condition_id: ConditionId, + pub true_next_id: ConditionId, + pub false_next_id: ConditionId, +} + +impl Default for ConditionInfo { + fn default() -> Self { + Self { + condition_id: ConditionId::NONE, + true_next_id: ConditionId::NONE, + false_next_id: ConditionId::NONE, + } + } +} + +#[derive(Clone, Debug)] +#[derive(TyEncodable, TyDecodable, Hash, HashStable, TypeFoldable, TypeVisitable)] +pub struct MCDCBranchSpan { + pub span: Span, + pub condition_info: ConditionInfo, + pub true_marker: BlockMarkerId, + pub false_marker: BlockMarkerId, +} + +#[derive(Copy, Clone, Debug)] +#[derive(TyEncodable, TyDecodable, Hash, HashStable, TypeFoldable, TypeVisitable)] +pub struct DecisionInfo { + pub bitmap_idx: u32, + pub conditions_num: u16, +} + +#[derive(Clone, Debug)] +#[derive(TyEncodable, TyDecodable, Hash, HashStable, TypeFoldable, TypeVisitable)] +pub struct MCDCDecisionSpan { + pub span: Span, + pub conditions_num: usize, + pub end_markers: Vec<BlockMarkerId>, +} diff --git a/compiler/rustc_middle/src/mir/pretty.rs b/compiler/rustc_middle/src/mir/pretty.rs index 15bd5c08965..a3cdcec9ec0 100644 --- a/compiler/rustc_middle/src/mir/pretty.rs +++ b/compiler/rustc_middle/src/mir/pretty.rs @@ -475,7 +475,8 @@ fn write_coverage_branch_info( branch_info: &coverage::BranchInfo, w: &mut dyn io::Write, ) -> io::Result<()> { - let coverage::BranchInfo { branch_spans, .. } = branch_info; + let coverage::BranchInfo { branch_spans, mcdc_branch_spans, mcdc_decision_spans, .. } = + branch_info; for coverage::BranchSpan { span, true_marker, false_marker } in branch_spans { writeln!( @@ -483,7 +484,26 @@ fn write_coverage_branch_info( "{INDENT}coverage branch {{ true: {true_marker:?}, false: {false_marker:?} }} => {span:?}", )?; } - if !branch_spans.is_empty() { + + for coverage::MCDCBranchSpan { span, condition_info, true_marker, false_marker } in + mcdc_branch_spans + { + writeln!( + w, + "{INDENT}coverage mcdc branch {{ condition_id: {:?}, true: {true_marker:?}, false: {false_marker:?} }} => {span:?}", + condition_info.condition_id + )?; + } + + for coverage::MCDCDecisionSpan { span, conditions_num, end_markers } in mcdc_decision_spans { + writeln!( + w, + "{INDENT}coverage mcdc decision {{ conditions_num: {conditions_num:?}, end: {end_markers:?} }} => {span:?}" + )?; + } + + if !branch_spans.is_empty() || !mcdc_branch_spans.is_empty() || !mcdc_decision_spans.is_empty() + { writeln!(w)?; } diff --git a/compiler/rustc_middle/src/ty/structural_impls.rs b/compiler/rustc_middle/src/ty/structural_impls.rs index 90c68e7ddfc..14a77d4b37e 100644 --- a/compiler/rustc_middle/src/ty/structural_impls.rs +++ b/compiler/rustc_middle/src/ty/structural_impls.rs @@ -427,6 +427,7 @@ TrivialTypeTraversalImpls! { crate::mir::coverage::BlockMarkerId, crate::mir::coverage::CounterId, crate::mir::coverage::ExpressionId, + crate::mir::coverage::ConditionId, crate::mir::Local, crate::mir::Promoted, crate::traits::Reveal, diff --git a/compiler/rustc_mir_build/src/build/coverageinfo.rs b/compiler/rustc_mir_build/src/build/coverageinfo.rs index ab0043906b1..57f809ef7cf 100644 --- a/compiler/rustc_mir_build/src/build/coverageinfo.rs +++ b/compiler/rustc_mir_build/src/build/coverageinfo.rs @@ -1,14 +1,20 @@ use std::assert_matches::assert_matches; use std::collections::hash_map::Entry; +use std::collections::VecDeque; use rustc_data_structures::fx::FxHashMap; -use rustc_middle::mir::coverage::{BlockMarkerId, BranchSpan, CoverageKind}; +use rustc_middle::mir::coverage::{ + BlockMarkerId, BranchSpan, ConditionId, ConditionInfo, CoverageKind, MCDCBranchSpan, + MCDCDecisionSpan, +}; use rustc_middle::mir::{self, BasicBlock, UnOp}; -use rustc_middle::thir::{ExprId, ExprKind, Thir}; +use rustc_middle::thir::{ExprId, ExprKind, LogicalOp, Thir}; use rustc_middle::ty::TyCtxt; use rustc_span::def_id::LocalDefId; +use rustc_span::Span; use crate::build::Builder; +use crate::errors::MCDCExceedsConditionNumLimit; pub(crate) struct BranchInfoBuilder { /// Maps condition expressions to their enclosing `!`, for better instrumentation. @@ -16,6 +22,9 @@ pub(crate) struct BranchInfoBuilder { num_block_markers: usize, branch_spans: Vec<BranchSpan>, + mcdc_branch_spans: Vec<MCDCBranchSpan>, + mcdc_decision_spans: Vec<MCDCDecisionSpan>, + mcdc_state: Option<MCDCState>, } #[derive(Clone, Copy)] @@ -33,7 +42,14 @@ impl BranchInfoBuilder { /// is enabled and `def_id` represents a function that is eligible for coverage. pub(crate) fn new_if_enabled(tcx: TyCtxt<'_>, def_id: LocalDefId) -> Option<Self> { if tcx.sess.instrument_coverage_branch() && tcx.is_eligible_for_coverage(def_id) { - Some(Self { nots: FxHashMap::default(), num_block_markers: 0, branch_spans: vec![] }) + Some(Self { + nots: FxHashMap::default(), + num_block_markers: 0, + branch_spans: vec![], + mcdc_branch_spans: vec![], + mcdc_decision_spans: vec![], + mcdc_state: MCDCState::new_if_enabled(tcx), + }) } else { None } @@ -79,6 +95,55 @@ impl BranchInfoBuilder { } } + fn record_conditions_operation(&mut self, logical_op: LogicalOp, span: Span) { + if let Some(mcdc_state) = self.mcdc_state.as_mut() { + mcdc_state.record_conditions(logical_op, span); + } + } + + fn fetch_condition_info( + &mut self, + tcx: TyCtxt<'_>, + true_marker: BlockMarkerId, + false_marker: BlockMarkerId, + ) -> Option<ConditionInfo> { + let mcdc_state = self.mcdc_state.as_mut()?; + let (mut condition_info, decision_result) = + mcdc_state.take_condition(true_marker, false_marker); + if let Some(decision) = decision_result { + match decision.conditions_num { + 0 => { + unreachable!("Decision with no condition is not expected"); + } + 1..=MAX_CONDITIONS_NUM_IN_DECISION => { + self.mcdc_decision_spans.push(decision); + } + _ => { + // Do not generate mcdc mappings and statements for decisions with too many conditions. + let rebase_idx = self.mcdc_branch_spans.len() - decision.conditions_num + 1; + let to_normal_branches = self.mcdc_branch_spans.split_off(rebase_idx); + self.branch_spans.extend(to_normal_branches.into_iter().map( + |MCDCBranchSpan { span, true_marker, false_marker, .. }| BranchSpan { + span, + true_marker, + false_marker, + }, + )); + + // ConditionInfo of this branch shall also be reset. + condition_info = None; + + tcx.dcx().emit_warn(MCDCExceedsConditionNumLimit { + span: decision.span, + conditions_num: decision.conditions_num, + max_conditions_num: MAX_CONDITIONS_NUM_IN_DECISION, + }); + } + } + } + condition_info + } + fn next_block_marker_id(&mut self) -> BlockMarkerId { let id = BlockMarkerId::from_usize(self.num_block_markers); self.num_block_markers += 1; @@ -86,14 +151,167 @@ impl BranchInfoBuilder { } pub(crate) fn into_done(self) -> Option<Box<mir::coverage::BranchInfo>> { - let Self { nots: _, num_block_markers, branch_spans } = self; + let Self { + nots: _, + num_block_markers, + branch_spans, + mcdc_branch_spans, + mcdc_decision_spans, + .. + } = self; if num_block_markers == 0 { assert!(branch_spans.is_empty()); return None; } - Some(Box::new(mir::coverage::BranchInfo { num_block_markers, branch_spans })) + Some(Box::new(mir::coverage::BranchInfo { + num_block_markers, + branch_spans, + mcdc_branch_spans, + mcdc_decision_spans, + })) + } +} + +/// 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_NUM_IN_DECISION: usize = 6; + +struct MCDCState { + /// To construct condition evaluation tree. + decision_stack: VecDeque<ConditionInfo>, + processing_decision: Option<MCDCDecisionSpan>, +} + +impl MCDCState { + fn new_if_enabled(tcx: TyCtxt<'_>) -> Option<Self> { + tcx.sess + .instrument_coverage_mcdc() + .then(|| Self { decision_stack: VecDeque::new(), processing_decision: None }) + } + + // At first we assign ConditionIds for each sub expression. + // If the sub expression is composite, re-assign its ConditionId to its LHS and generate a new ConditionId for its RHS. + // + // Example: "x = (A && B) || (C && D) || (D && F)" + // + // Visit Depth1: + // (A && B) || (C && D) || (D && F) + // ^-------LHS--------^ ^-RHS--^ + // ID=1 ID=2 + // + // Visit LHS-Depth2: + // (A && B) || (C && D) + // ^-LHS--^ ^-RHS--^ + // ID=1 ID=3 + // + // Visit LHS-Depth3: + // (A && B) + // LHS RHS + // ID=1 ID=4 + // + // Visit RHS-Depth3: + // (C && D) + // LHS RHS + // ID=3 ID=5 + // + // Visit RHS-Depth2: (D && F) + // LHS RHS + // ID=2 ID=6 + // + // Visit Depth1: + // (A && B) || (C && D) || (D && F) + // ID=1 ID=4 ID=3 ID=5 ID=2 ID=6 + // + // A node ID of '0' always means MC/DC isn't being tracked. + // + // If a "next" node ID is '0', it means it's the end of the test vector. + // + // As the compiler tracks expression in pre-order, we can ensure that condition info of parents are always properly assigned when their children are visited. + // - If the op is AND, the "false_next" of LHS and RHS should be the parent's "false_next". While "true_next" of the LHS is the RHS, the "true next" of RHS is the parent's "true_next". + // - If the op is OR, the "true_next" of LHS and RHS should be the parent's "true_next". While "false_next" of the LHS is the RHS, the "false next" of RHS is the parent's "false_next". + fn record_conditions(&mut self, op: LogicalOp, span: Span) { + let decision = match self.processing_decision.as_mut() { + Some(decision) => { + decision.span = decision.span.to(span); + decision + } + None => self.processing_decision.insert(MCDCDecisionSpan { + span, + conditions_num: 0, + end_markers: vec![], + }), + }; + + let parent_condition = self.decision_stack.pop_back().unwrap_or_default(); + let lhs_id = if parent_condition.condition_id == ConditionId::NONE { + decision.conditions_num += 1; + ConditionId::from(decision.conditions_num) + } else { + parent_condition.condition_id + }; + + decision.conditions_num += 1; + let rhs_condition_id = ConditionId::from(decision.conditions_num); + + let (lhs, rhs) = match op { + LogicalOp::And => { + let lhs = ConditionInfo { + condition_id: lhs_id, + true_next_id: rhs_condition_id, + false_next_id: parent_condition.false_next_id, + }; + let rhs = ConditionInfo { + condition_id: rhs_condition_id, + true_next_id: parent_condition.true_next_id, + false_next_id: parent_condition.false_next_id, + }; + (lhs, rhs) + } + LogicalOp::Or => { + let lhs = ConditionInfo { + condition_id: lhs_id, + true_next_id: parent_condition.true_next_id, + false_next_id: rhs_condition_id, + }; + let rhs = ConditionInfo { + condition_id: rhs_condition_id, + true_next_id: parent_condition.true_next_id, + false_next_id: parent_condition.false_next_id, + }; + (lhs, rhs) + } + }; + // We visit expressions tree in pre-order, so place the left-hand side on the top. + self.decision_stack.push_back(rhs); + self.decision_stack.push_back(lhs); + } + + fn take_condition( + &mut self, + true_marker: BlockMarkerId, + false_marker: BlockMarkerId, + ) -> (Option<ConditionInfo>, Option<MCDCDecisionSpan>) { + let Some(condition_info) = self.decision_stack.pop_back() else { + return (None, None); + }; + let Some(decision) = self.processing_decision.as_mut() else { + bug!("Processing decision should have been created before any conditions are taken"); + }; + if condition_info.true_next_id == ConditionId::NONE { + decision.end_markers.push(true_marker); + } + if condition_info.false_next_id == ConditionId::NONE { + decision.end_markers.push(false_marker); + } + + if self.decision_stack.is_empty() { + (Some(condition_info), self.processing_decision.take()) + } else { + (Some(condition_info), None) + } } } @@ -137,10 +355,27 @@ impl Builder<'_, '_> { let true_marker = inject_branch_marker(then_block); let false_marker = inject_branch_marker(else_block); - branch_info.branch_spans.push(BranchSpan { - span: source_info.span, - true_marker, - false_marker, - }); + if let Some(condition_info) = + branch_info.fetch_condition_info(self.tcx, true_marker, false_marker) + { + branch_info.mcdc_branch_spans.push(MCDCBranchSpan { + span: source_info.span, + condition_info, + true_marker, + false_marker, + }); + } else { + branch_info.branch_spans.push(BranchSpan { + span: source_info.span, + true_marker, + false_marker, + }); + } + } + + pub(crate) fn visit_coverage_branch_operation(&mut self, logical_op: LogicalOp, span: Span) { + if let Some(branch_info) = self.coverage_branch_info.as_mut() { + branch_info.record_conditions_operation(logical_op, span); + } } } diff --git a/compiler/rustc_mir_build/src/build/matches/mod.rs b/compiler/rustc_mir_build/src/build/matches/mod.rs index 9730473c428..f46dceeeedf 100644 --- a/compiler/rustc_mir_build/src/build/matches/mod.rs +++ b/compiler/rustc_mir_build/src/build/matches/mod.rs @@ -77,11 +77,13 @@ impl<'a, 'tcx> Builder<'a, 'tcx> { match expr.kind { ExprKind::LogicalOp { op: LogicalOp::And, lhs, rhs } => { + this.visit_coverage_branch_operation(LogicalOp::And, expr_span); let lhs_then_block = unpack!(this.then_else_break_inner(block, lhs, args)); let rhs_then_block = unpack!(this.then_else_break_inner(lhs_then_block, rhs, args)); rhs_then_block.unit() } ExprKind::LogicalOp { op: LogicalOp::Or, lhs, rhs } => { + this.visit_coverage_branch_operation(LogicalOp::Or, expr_span); let local_scope = this.local_scope(); let (lhs_success_block, failure_block) = this.in_if_then_scope(local_scope, expr_span, |this| { 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<_>>() } |