pub use super::ffi::*; use rustc_index::vec::IndexVec; use rustc_middle::mir::coverage::{ CodeRegion, CounterValueReference, ExpressionOperandId, InjectedExpressionId, InjectedExpressionIndex, MappedExpressionIndex, Op, }; use rustc_middle::ty::Instance; use rustc_middle::ty::TyCtxt; #[derive(Clone, Debug, PartialEq)] pub struct Expression { lhs: ExpressionOperandId, op: Op, rhs: ExpressionOperandId, region: Option, } /// Collects all of the coverage regions associated with (a) injected counters, (b) counter /// expressions (additions or subtraction), and (c) unreachable regions (always counted as zero), /// for a given Function. Counters and counter expressions have non-overlapping `id`s because they /// can both be operands in an expression. This struct also stores the `function_source_hash`, /// computed during instrumentation, and forwarded with counters. /// /// Note, it may be important to understand LLVM's definitions of `unreachable` regions versus "gap /// regions" (or "gap areas"). A gap region is a code region within a counted region (either counter /// or expression), but the line or lines in the gap region are not executable (such as lines with /// only whitespace or comments). According to LLVM Code Coverage Mapping documentation, "A count /// for a gap area is only used as the line execution count if there are no other regions on a /// line." #[derive(Debug)] pub struct FunctionCoverage<'tcx> { instance: Instance<'tcx>, source_hash: u64, is_used: bool, counters: IndexVec>, expressions: IndexVec>, unreachable_regions: Vec, } impl<'tcx> FunctionCoverage<'tcx> { /// Creates a new set of coverage data for a used (called) function. pub fn new(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>) -> Self { Self::create(tcx, instance, true) } /// Creates a new set of coverage data for an unused (never called) function. pub fn unused(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>) -> Self { Self::create(tcx, instance, false) } fn create(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>, is_used: bool) -> Self { let coverageinfo = tcx.coverageinfo(instance.def); debug!( "FunctionCoverage::create(instance={:?}) has coverageinfo={:?}. is_used={}", instance, coverageinfo, is_used ); Self { instance, source_hash: 0, // will be set with the first `add_counter()` is_used, counters: IndexVec::from_elem_n(None, coverageinfo.num_counters as usize), expressions: IndexVec::from_elem_n(None, coverageinfo.num_expressions as usize), unreachable_regions: Vec::new(), } } /// Returns true for a used (called) function, and false for an unused function. pub fn is_used(&self) -> bool { self.is_used } /// Sets the function source hash value. If called multiple times for the same function, all /// calls should have the same hash value. pub fn set_function_source_hash(&mut self, source_hash: u64) { if self.source_hash == 0 { self.source_hash = source_hash; } else { debug_assert_eq!(source_hash, self.source_hash); } } /// Adds a code region to be counted by an injected counter intrinsic. pub fn add_counter(&mut self, id: CounterValueReference, region: CodeRegion) { if let Some(previous_region) = self.counters[id].replace(region.clone()) { assert_eq!(previous_region, region, "add_counter: code region for id changed"); } } /// Both counters and "counter expressions" (or simply, "expressions") can be operands in other /// expressions. Expression IDs start from `u32::MAX` and go down, so the range of expression /// IDs will not overlap with the range of counter IDs. Counters and expressions can be added in /// any order, and expressions can still be assigned contiguous (though descending) IDs, without /// knowing what the last counter ID will be. /// /// When storing the expression data in the `expressions` vector in the `FunctionCoverage` /// struct, its vector index is computed, from the given expression ID, by subtracting from /// `u32::MAX`. /// /// Since the expression operands (`lhs` and `rhs`) can reference either counters or /// expressions, an operand that references an expression also uses its original ID, descending /// from `u32::MAX`. Theses operands are translated only during code generation, after all /// counters and expressions have been added. pub fn add_counter_expression( &mut self, expression_id: InjectedExpressionId, lhs: ExpressionOperandId, op: Op, rhs: ExpressionOperandId, region: Option, ) { debug!( "add_counter_expression({:?}, lhs={:?}, op={:?}, rhs={:?} at {:?}", expression_id, lhs, op, rhs, region ); let expression_index = self.expression_index(u32::from(expression_id)); debug_assert!( expression_index.as_usize() < self.expressions.len(), "expression_index {} is out of range for expressions.len() = {} for {:?}", expression_index.as_usize(), self.expressions.len(), self, ); if let Some(previous_expression) = self.expressions[expression_index].replace(Expression { lhs, op, rhs, region: region.clone(), }) { assert_eq!( previous_expression, Expression { lhs, op, rhs, region }, "add_counter_expression: expression for id changed" ); } } /// Add a region that will be marked as "unreachable", with a constant "zero counter". pub fn add_unreachable_region(&mut self, region: CodeRegion) { self.unreachable_regions.push(region) } /// Return the source hash, generated from the HIR node structure, and used to indicate whether /// or not the source code structure changed between different compilations. pub fn source_hash(&self) -> u64 { self.source_hash } /// Generate an array of CounterExpressions, and an iterator over all `Counter`s and their /// associated `Regions` (from which the LLVM-specific `CoverageMapGenerator` will create /// `CounterMappingRegion`s. pub fn get_expressions_and_counter_regions( &self, ) -> (Vec, impl Iterator) { assert!( self.source_hash != 0 || !self.is_used, "No counters provided the source_hash for used function: {:?}", self.instance ); let counter_regions = self.counter_regions(); let (counter_expressions, expression_regions) = self.expressions_with_regions(); let unreachable_regions = self.unreachable_regions(); let counter_regions = counter_regions.chain(expression_regions.into_iter().chain(unreachable_regions)); (counter_expressions, counter_regions) } fn counter_regions(&self) -> impl Iterator { self.counters.iter_enumerated().filter_map(|(index, entry)| { // Option::map() will return None to filter out missing counters. This may happen // if, for example, a MIR-instrumented counter is removed during an optimization. entry.as_ref().map(|region| (Counter::counter_value_reference(index), region)) }) } fn expressions_with_regions( &self, ) -> (Vec, impl Iterator) { let mut counter_expressions = Vec::with_capacity(self.expressions.len()); let mut expression_regions = Vec::with_capacity(self.expressions.len()); let mut new_indexes = IndexVec::from_elem_n(None, self.expressions.len()); // This closure converts any `Expression` operand (`lhs` or `rhs` of the `Op::Add` or // `Op::Subtract` operation) into its native `llvm::coverage::Counter::CounterKind` type // and value. Operand ID value `0` maps to `CounterKind::Zero`; values in the known range // of injected LLVM counters map to `CounterKind::CounterValueReference` (and the value // matches the injected counter index); and any other value is converted into a // `CounterKind::Expression` with the expression's `new_index`. // // Expressions will be returned from this function in a sequential vector (array) of // `CounterExpression`, so the expression IDs must be mapped from their original, // potentially sparse set of indexes, originally in reverse order from `u32::MAX`. // // An `Expression` as an operand will have already been encountered as an `Expression` with // operands, so its new_index will already have been generated (as a 1-up index value). // (If an `Expression` as an operand does not have a corresponding new_index, it was // probably optimized out, after the expression was injected into the MIR, so it will // get a `CounterKind::Zero` instead.) // // In other words, an `Expression`s at any given index can include other expressions as // operands, but expression operands can only come from the subset of expressions having // `expression_index`s lower than the referencing `Expression`. Therefore, it is // reasonable to look up the new index of an expression operand while the `new_indexes` // vector is only complete up to the current `ExpressionIndex`. let id_to_counter = |new_indexes: &IndexVec< InjectedExpressionIndex, Option, >, id: ExpressionOperandId| { if id == ExpressionOperandId::ZERO { Some(Counter::zero()) } else if id.index() < self.counters.len() { debug_assert!( id.index() > 0, "ExpressionOperandId indexes for counters are 1-based, but this id={}", id.index() ); // Note: Some codegen-injected Counters may be only referenced by `Expression`s, // and may not have their own `CodeRegion`s, let index = CounterValueReference::from(id.index()); // Note, the conversion to LLVM `Counter` adjusts the index to be zero-based. Some(Counter::counter_value_reference(index)) } else { let index = self.expression_index(u32::from(id)); self.expressions .get(index) .expect("expression id is out of range") .as_ref() // If an expression was optimized out, assume it would have produced a count // of zero. This ensures that expressions dependent on optimized-out // expressions are still valid. .map_or(Some(Counter::zero()), |_| new_indexes[index].map(Counter::expression)) } }; for (original_index, expression) in self.expressions.iter_enumerated().filter_map(|(original_index, entry)| { // Option::map() will return None to filter out missing expressions. This may happen // if, for example, a MIR-instrumented expression is removed during an optimization. entry.as_ref().map(|expression| (original_index, expression)) }) { let optional_region = &expression.region; let Expression { lhs, op, rhs, .. } = *expression; if let Some(Some((lhs_counter, mut rhs_counter))) = id_to_counter(&new_indexes, lhs) .map(|lhs_counter| { id_to_counter(&new_indexes, rhs).map(|rhs_counter| (lhs_counter, rhs_counter)) }) { if lhs_counter.is_zero() && op.is_subtract() { // The left side of a subtraction was probably optimized out. As an example, // a branch condition might be evaluated as a constant expression, and the // branch could be removed, dropping unused counters in the process. // // Since counters are unsigned, we must assume the result of the expression // can be no more and no less than zero. An expression known to evaluate to zero // does not need to be added to the coverage map. // // Coverage test `loops_branches.rs` includes multiple variations of branches // based on constant conditional (literal `true` or `false`), and demonstrates // that the expected counts are still correct. debug!( "Expression subtracts from zero (assume unreachable): \ original_index={:?}, lhs={:?}, op={:?}, rhs={:?}, region={:?}", original_index, lhs, op, rhs, optional_region, ); rhs_counter = Counter::zero(); } debug_assert!( lhs_counter.is_zero() // Note: with `as usize` the ID _could_ overflow/wrap if `usize = u16` || ((lhs_counter.zero_based_id() as usize) <= usize::max(self.counters.len(), self.expressions.len())), "lhs id={} > both counters.len()={} and expressions.len()={} ({:?} {:?} {:?})", lhs_counter.zero_based_id(), self.counters.len(), self.expressions.len(), lhs_counter, op, rhs_counter, ); debug_assert!( rhs_counter.is_zero() // Note: with `as usize` the ID _could_ overflow/wrap if `usize = u16` || ((rhs_counter.zero_based_id() as usize) <= usize::max(self.counters.len(), self.expressions.len())), "rhs id={} > both counters.len()={} and expressions.len()={} ({:?} {:?} {:?})", rhs_counter.zero_based_id(), self.counters.len(), self.expressions.len(), lhs_counter, op, rhs_counter, ); // Both operands exist. `Expression` operands exist in `self.expressions` and have // been assigned a `new_index`. let mapped_expression_index = MappedExpressionIndex::from(counter_expressions.len()); let expression = CounterExpression::new( lhs_counter, match op { Op::Add => ExprKind::Add, Op::Subtract => ExprKind::Subtract, }, rhs_counter, ); debug!( "Adding expression {:?} = {:?}, region: {:?}", mapped_expression_index, expression, optional_region ); counter_expressions.push(expression); new_indexes[original_index] = Some(mapped_expression_index); if let Some(region) = optional_region { expression_regions.push((Counter::expression(mapped_expression_index), region)); } } else { bug!( "expression has one or more missing operands \ original_index={:?}, lhs={:?}, op={:?}, rhs={:?}, region={:?}", original_index, lhs, op, rhs, optional_region, ); } } (counter_expressions, expression_regions.into_iter()) } fn unreachable_regions(&self) -> impl Iterator { self.unreachable_regions.iter().map(|region| (Counter::zero(), region)) } fn expression_index(&self, id_descending_from_max: u32) -> InjectedExpressionIndex { debug_assert!(id_descending_from_max >= self.counters.len() as u32); InjectedExpressionIndex::from(u32::MAX - id_descending_from_max) } }