diff options
Diffstat (limited to 'compiler/rustc_codegen_ssa/src/coverageinfo/map.rs')
| -rw-r--r-- | compiler/rustc_codegen_ssa/src/coverageinfo/map.rs | 347 |
1 files changed, 347 insertions, 0 deletions
diff --git a/compiler/rustc_codegen_ssa/src/coverageinfo/map.rs b/compiler/rustc_codegen_ssa/src/coverageinfo/map.rs new file mode 100644 index 000000000..1a6495cb1 --- /dev/null +++ b/compiler/rustc_codegen_ssa/src/coverageinfo/map.rs @@ -0,0 +1,347 @@ +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<CodeRegion>, +} + +/// 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<CounterValueReference, Option<CodeRegion>>, + expressions: IndexVec<InjectedExpressionIndex, Option<Expression>>, + unreachable_regions: Vec<CodeRegion>, +} + +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<CodeRegion>, + ) { + 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<CounterExpression>, impl Iterator<Item = (Counter, &CodeRegion)>) { + 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<Item = (Counter, &CodeRegion)> { + 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<CounterExpression>, impl Iterator<Item = (Counter, &CodeRegion)>) { + 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<MappedExpressionIndex>, + >, + 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<Item = (Counter, &CodeRegion)> { + 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) + } +} |