compiler/rustc_codegen_ssa/src/coverageinfo/map.rs

   1 pub use super::ffi::*;
   2
   3 use rustc_index::vec::IndexVec;
   4 use rustc_middle::mir::coverage::{
   5     CodeRegion, CounterValueReference, ExpressionOperandId, InjectedExpressionId,
   6     InjectedExpressionIndex, MappedExpressionIndex, Op,
   7 };
   8 use rustc_middle::ty::Instance;
   9 use rustc_middle::ty::TyCtxt;
  10
  11 #[derive(Clone, Debug, PartialEq)]
  12 pub struct Expression {
  13     lhs: ExpressionOperandId,
  14     op: Op,
  15     rhs: ExpressionOperandId,
  16     region: Option<CodeRegion>,
  17 }
  18
  19 /// Collects all of the coverage regions associated with (a) injected counters, (b) counter
  20 /// expressions (additions or subtraction), and (c) unreachable regions (always counted as zero),
  21 /// for a given Function. Counters and counter expressions have non-overlapping `id`s because they
  22 /// can both be operands in an expression. This struct also stores the `function_source_hash`,
  23 /// computed during instrumentation, and forwarded with counters.
  24 ///
  25 /// Note, it may be important to understand LLVM's definitions of `unreachable` regions versus "gap
  26 /// regions" (or "gap areas"). A gap region is a code region within a counted region (either counter
  27 /// or expression), but the line or lines in the gap region are not executable (such as lines with
  28 /// only whitespace or comments). According to LLVM Code Coverage Mapping documentation, "A count
  29 /// for a gap area is only used as the line execution count if there are no other regions on a
  30 /// line."
  31 #[derive(Debug)]
  32 pub struct FunctionCoverage<'tcx> {
  33     instance: Instance<'tcx>,
  34     source_hash: u64,
  35     is_used: bool,
  36     counters: IndexVec<CounterValueReference, Option<CodeRegion>>,
  37     expressions: IndexVec<InjectedExpressionIndex, Option<Expression>>,
  38     unreachable_regions: Vec<CodeRegion>,
  39 }
  40
  41 impl<'tcx> FunctionCoverage<'tcx> {
  42     /// Creates a new set of coverage data for a used (called) function.
  43     pub fn new(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>) -> Self {
  44         Self::create(tcx, instance, true)
  45     }
  46
  47     /// Creates a new set of coverage data for an unused (never called) function.
  48     pub fn unused(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>) -> Self {
  49         Self::create(tcx, instance, false)
  50     }
  51
  52     fn create(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>, is_used: bool) -> Self {
  53         let coverageinfo = tcx.coverageinfo(instance.def);
  54         debug!(
  55             "FunctionCoverage::create(instance={:?}) has coverageinfo={:?}. is_used={}",
  56             instance, coverageinfo, is_used
  57         );
  58         Self {
  59             instance,
  60             source_hash: 0, // will be set with the first `add_counter()`
  61             is_used,
  62             counters: IndexVec::from_elem_n(None, coverageinfo.num_counters as usize),
  63             expressions: IndexVec::from_elem_n(None, coverageinfo.num_expressions as usize),
  64             unreachable_regions: Vec::new(),
  65         }
  66     }
  67
  68     /// Returns true for a used (called) function, and false for an unused function.
  69     pub fn is_used(&self) -> bool {
  70         self.is_used
  71     }
  72
  73     /// Sets the function source hash value. If called multiple times for the same function, all
  74     /// calls should have the same hash value.
  75     pub fn set_function_source_hash(&mut self, source_hash: u64) {
  76         if self.source_hash == 0 {
  77             self.source_hash = source_hash;
  78         } else {
  79             debug_assert_eq!(source_hash, self.source_hash);
  80         }
  81     }
  82
  83     /// Adds a code region to be counted by an injected counter intrinsic.
  84     pub fn add_counter(&mut self, id: CounterValueReference, region: CodeRegion) {
  85         if let Some(previous_region) = self.counters[id].replace(region.clone()) {
  86             assert_eq!(previous_region, region, "add_counter: code region for id changed");
  87         }
  88     }
  89
  90     /// Both counters and "counter expressions" (or simply, "expressions") can be operands in other
  91     /// expressions. Expression IDs start from `u32::MAX` and go down, so the range of expression
  92     /// IDs will not overlap with the range of counter IDs. Counters and expressions can be added in
  93     /// any order, and expressions can still be assigned contiguous (though descending) IDs, without
  94     /// knowing what the last counter ID will be.
  95     ///
  96     /// When storing the expression data in the `expressions` vector in the `FunctionCoverage`
  97     /// struct, its vector index is computed, from the given expression ID, by subtracting from
  98     /// `u32::MAX`.
  99     ///
 100     /// Since the expression operands (`lhs` and `rhs`) can reference either counters or
 101     /// expressions, an operand that references an expression also uses its original ID, descending
 102     /// from `u32::MAX`. Theses operands are translated only during code generation, after all
 103     /// counters and expressions have been added.
 104     pub fn add_counter_expression(
 105         &mut self,
 106         expression_id: InjectedExpressionId,
 107         lhs: ExpressionOperandId,
 108         op: Op,
 109         rhs: ExpressionOperandId,
 110         region: Option<CodeRegion>,
 111     ) {
 112         debug!(
 113             "add_counter_expression({:?}, lhs={:?}, op={:?}, rhs={:?} at {:?}",
 114             expression_id, lhs, op, rhs, region
 115         );
 116         let expression_index = self.expression_index(u32::from(expression_id));
 117         debug_assert!(
 118             expression_index.as_usize() < self.expressions.len(),
 119             "expression_index {} is out of range for expressions.len() = {}
 120             for {:?}",
 121             expression_index.as_usize(),
 122             self.expressions.len(),
 123             self,
 124         );
 125         if let Some(previous_expression) = self.expressions[expression_index].replace(Expression {
 126             lhs,
 127             op,
 128             rhs,
 129             region: region.clone(),
 130         }) {
 131             assert_eq!(
 132                 previous_expression,
 133                 Expression { lhs, op, rhs, region },
 134                 "add_counter_expression: expression for id changed"
 135             );
 136         }
 137     }
 138
 139     /// Add a region that will be marked as "unreachable", with a constant "zero counter".
 140     pub fn add_unreachable_region(&mut self, region: CodeRegion) {
 141         self.unreachable_regions.push(region)
 142     }
 143
 144     /// Return the source hash, generated from the HIR node structure, and used to indicate whether
 145     /// or not the source code structure changed between different compilations.
 146     pub fn source_hash(&self) -> u64 {
 147         self.source_hash
 148     }
 149
 150     /// Generate an array of CounterExpressions, and an iterator over all `Counter`s and their
 151     /// associated `Regions` (from which the LLVM-specific `CoverageMapGenerator` will create
 152     /// `CounterMappingRegion`s.
 153     pub fn get_expressions_and_counter_regions(
 154         &self,
 155     ) -> (Vec<CounterExpression>, impl Iterator<Item = (Counter, &CodeRegion)>) {
 156         assert!(
 157             self.source_hash != 0 || !self.is_used,
 158             "No counters provided the source_hash for used function: {:?}",
 159             self.instance
 160         );
 161
 162         let counter_regions = self.counter_regions();
 163         let (counter_expressions, expression_regions) = self.expressions_with_regions();
 164         let unreachable_regions = self.unreachable_regions();
 165
 166         let counter_regions =
 167             counter_regions.chain(expression_regions.into_iter().chain(unreachable_regions));
 168         (counter_expressions, counter_regions)
 169     }
 170
 171     fn counter_regions(&self) -> impl Iterator<Item = (Counter, &CodeRegion)> {
 172         self.counters.iter_enumerated().filter_map(|(index, entry)| {
 173             // Option::map() will return None to filter out missing counters. This may happen
 174             // if, for example, a MIR-instrumented counter is removed during an optimization.
 175             entry.as_ref().map(|region| (Counter::counter_value_reference(index), region))
 176         })
 177     }
 178
 179     fn expressions_with_regions(
 180         &self,
 181     ) -> (Vec<CounterExpression>, impl Iterator<Item = (Counter, &CodeRegion)>) {
 182         let mut counter_expressions = Vec::with_capacity(self.expressions.len());
 183         let mut expression_regions = Vec::with_capacity(self.expressions.len());
 184         let mut new_indexes = IndexVec::from_elem_n(None, self.expressions.len());
 185
 186         // This closure converts any `Expression` operand (`lhs` or `rhs` of the `Op::Add` or
 187         // `Op::Subtract` operation) into its native `llvm::coverage::Counter::CounterKind` type
 188         // and value. Operand ID value `0` maps to `CounterKind::Zero`; values in the known range
 189         // of injected LLVM counters map to `CounterKind::CounterValueReference` (and the value
 190         // matches the injected counter index); and any other value is converted into a
 191         // `CounterKind::Expression` with the expression's `new_index`.
 192         //
 193         // Expressions will be returned from this function in a sequential vector (array) of
 194         // `CounterExpression`, so the expression IDs must be mapped from their original,
 195         // potentially sparse set of indexes, originally in reverse order from `u32::MAX`.
 196         //
 197         // An `Expression` as an operand will have already been encountered as an `Expression` with
 198         // operands, so its new_index will already have been generated (as a 1-up index value).
 199         // (If an `Expression` as an operand does not have a corresponding new_index, it was
 200         // probably optimized out, after the expression was injected into the MIR, so it will
 201         // get a `CounterKind::Zero` instead.)
 202         //
 203         // In other words, an `Expression`s at any given index can include other expressions as
 204         // operands, but expression operands can only come from the subset of expressions having
 205         // `expression_index`s lower than the referencing `Expression`. Therefore, it is
 206         // reasonable to look up the new index of an expression operand while the `new_indexes`
 207         // vector is only complete up to the current `ExpressionIndex`.
 208         let id_to_counter = |new_indexes: &IndexVec<
 209             InjectedExpressionIndex,
 210             Option<MappedExpressionIndex>,
 211         >,
 212                              id: ExpressionOperandId| {
 213             if id == ExpressionOperandId::ZERO {
 214                 Some(Counter::zero())
 215             } else if id.index() < self.counters.len() {
 216                 debug_assert!(
 217                     id.index() > 0,
 218                     "ExpressionOperandId indexes for counters are 1-based, but this id={}",
 219                     id.index()
 220                 );
 221                 // Note: Some codegen-injected Counters may be only referenced by `Expression`s,
 222                 // and may not have their own `CodeRegion`s,
 223                 let index = CounterValueReference::from(id.index());
 224                 // Note, the conversion to LLVM `Counter` adjusts the index to be zero-based.
 225                 Some(Counter::counter_value_reference(index))
 226             } else {
 227                 let index = self.expression_index(u32::from(id));
 228                 self.expressions
 229                     .get(index)
 230                     .expect("expression id is out of range")
 231                     .as_ref()
 232                     // If an expression was optimized out, assume it would have produced a count
 233                     // of zero. This ensures that expressions dependent on optimized-out
 234                     // expressions are still valid.
 235                     .map_or(Some(Counter::zero()), |_| new_indexes[index].map(Counter::expression))
 236             }
 237         };
 238
 239         for (original_index, expression) in
 240             self.expressions.iter_enumerated().filter_map(|(original_index, entry)| {
 241                 // Option::map() will return None to filter out missing expressions. This may happen
 242                 // if, for example, a MIR-instrumented expression is removed during an optimization.
 243                 entry.as_ref().map(|expression| (original_index, expression))
 244             })
 245         {
 246             let optional_region = &expression.region;
 247             let Expression { lhs, op, rhs, .. } = *expression;
 248
 249             if let Some(Some((lhs_counter, mut rhs_counter))) = id_to_counter(&new_indexes, lhs)
 250                 .map(|lhs_counter| {
 251                     id_to_counter(&new_indexes, rhs).map(|rhs_counter| (lhs_counter, rhs_counter))
 252                 })
 253             {
 254                 if lhs_counter.is_zero() && op.is_subtract() {
 255                     // The left side of a subtraction was probably optimized out. As an example,
 256                     // a branch condition might be evaluated as a constant expression, and the
 257                     // branch could be removed, dropping unused counters in the process.
 258                     //
 259                     // Since counters are unsigned, we must assume the result of the expression
 260                     // can be no more and no less than zero. An expression known to evaluate to zero
 261                     // does not need to be added to the coverage map.
 262                     //
 263                     // Coverage test `loops_branches.rs` includes multiple variations of branches
 264                     // based on constant conditional (literal `true` or `false`), and demonstrates
 265                     // that the expected counts are still correct.
 266                     debug!(
 267                         "Expression subtracts from zero (assume unreachable): \
 268                         original_index={:?}, lhs={:?}, op={:?}, rhs={:?}, region={:?}",
 269                         original_index, lhs, op, rhs, optional_region,
 270                     );
 271                     rhs_counter = Counter::zero();
 272                 }
 273                 debug_assert!(
 274                     lhs_counter.is_zero()
 275                         // Note: with `as usize` the ID _could_ overflow/wrap if `usize = u16`
 276                         || ((lhs_counter.zero_based_id() as usize)
 277                             <= usize::max(self.counters.len(), self.expressions.len())),
 278                     "lhs id={} > both counters.len()={} and expressions.len()={}
 279                     ({:?} {:?} {:?})",
 280                     lhs_counter.zero_based_id(),
 281                     self.counters.len(),
 282                     self.expressions.len(),
 283                     lhs_counter,
 284                     op,
 285                     rhs_counter,
 286                 );
 287
 288                 debug_assert!(
 289                     rhs_counter.is_zero()
 290                         // Note: with `as usize` the ID _could_ overflow/wrap if `usize = u16`
 291                         || ((rhs_counter.zero_based_id() as usize)
 292                             <= usize::max(self.counters.len(), self.expressions.len())),
 293                     "rhs id={} > both counters.len()={} and expressions.len()={}
 294                     ({:?} {:?} {:?})",
 295                     rhs_counter.zero_based_id(),
 296                     self.counters.len(),
 297                     self.expressions.len(),
 298                     lhs_counter,
 299                     op,
 300                     rhs_counter,
 301                 );
 302
 303                 // Both operands exist. `Expression` operands exist in `self.expressions` and have
 304                 // been assigned a `new_index`.
 305                 let mapped_expression_index =
 306                     MappedExpressionIndex::from(counter_expressions.len());
 307                 let expression = CounterExpression::new(
 308                     lhs_counter,
 309                     match op {
 310                         Op::Add => ExprKind::Add,
 311                         Op::Subtract => ExprKind::Subtract,
 312                     },
 313                     rhs_counter,
 314                 );
 315                 debug!(
 316                     "Adding expression {:?} = {:?}, region: {:?}",
 317                     mapped_expression_index, expression, optional_region
 318                 );
 319                 counter_expressions.push(expression);
 320                 new_indexes[original_index] = Some(mapped_expression_index);
 321                 if let Some(region) = optional_region {
 322                     expression_regions.push((Counter::expression(mapped_expression_index), region));
 323                 }
 324             } else {
 325                 bug!(
 326                     "expression has one or more missing operands \
 327                       original_index={:?}, lhs={:?}, op={:?}, rhs={:?}, region={:?}",
 328                     original_index,
 329                     lhs,
 330                     op,
 331                     rhs,
 332                     optional_region,
 333                 );
 334             }
 335         }
 336         (counter_expressions, expression_regions.into_iter())
 337     }
 338
 339     fn unreachable_regions(&self) -> impl Iterator<Item = (Counter, &CodeRegion)> {
 340         self.unreachable_regions.iter().map(|region| (Counter::zero(), region))
 341     }
 342
 343     fn expression_index(&self, id_descending_from_max: u32) -> InjectedExpressionIndex {
 344         debug_assert!(id_descending_from_max >= self.counters.len() as u32);
 345         InjectedExpressionIndex::from(u32::MAX - id_descending_from_max)
 346     }
 347 }