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)]
  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 pub struct FunctionCoverage<'tcx> {
  32     instance: Instance<'tcx>,
  33     source_hash: u64,
  34     counters: IndexVec<CounterValueReference, Option<CodeRegion>>,
  35     expressions: IndexVec<InjectedExpressionIndex, Option<Expression>>,
  36     unreachable_regions: Vec<CodeRegion>,
  37 }
  38
  39 impl<'tcx> FunctionCoverage<'tcx> {
  40     pub fn new(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>) -> Self {
  41         let coverageinfo = tcx.coverageinfo(instance.def_id());
  42         debug!(
  43             "FunctionCoverage::new(instance={:?}) has coverageinfo={:?}",
  44             instance, coverageinfo
  45         );
  46         Self {
  47             instance,
  48             source_hash: 0, // will be set with the first `add_counter()`
  49             counters: IndexVec::from_elem_n(None, coverageinfo.num_counters as usize),
  50             expressions: IndexVec::from_elem_n(None, coverageinfo.num_expressions as usize),
  51             unreachable_regions: Vec::new(),
  52         }
  53     }
  54
  55     /// Sets the function source hash value. If called multiple times for the same function, all
  56     /// calls should have the same hash value.
  57     pub fn set_function_source_hash(&mut self, source_hash: u64) {
  58         if self.source_hash == 0 {
  59             self.source_hash = source_hash;
  60         } else {
  61             debug_assert_eq!(source_hash, self.source_hash);
  62         }
  63     }
  64
  65     /// Adds a code region to be counted by an injected counter intrinsic.
  66     pub fn add_counter(&mut self, id: CounterValueReference, region: CodeRegion) {
  67         self.counters[id].replace(region).expect_none("add_counter called with duplicate `id`");
  68     }
  69
  70     /// Both counters and "counter expressions" (or simply, "expressions") can be operands in other
  71     /// expressions. Expression IDs start from `u32::MAX` and go down, so the range of expression
  72     /// IDs will not overlap with the range of counter IDs. Counters and expressions can be added in
  73     /// any order, and expressions can still be assigned contiguous (though descending) IDs, without
  74     /// knowing what the last counter ID will be.
  75     ///
  76     /// When storing the expression data in the `expressions` vector in the `FunctionCoverage`
  77     /// struct, its vector index is computed, from the given expression ID, by subtracting from
  78     /// `u32::MAX`.
  79     ///
  80     /// Since the expression operands (`lhs` and `rhs`) can reference either counters or
  81     /// expressions, an operand that references an expression also uses its original ID, descending
  82     /// from `u32::MAX`. Theses operands are translated only during code generation, after all
  83     /// counters and expressions have been added.
  84     pub fn add_counter_expression(
  85         &mut self,
  86         expression_id: InjectedExpressionId,
  87         lhs: ExpressionOperandId,
  88         op: Op,
  89         rhs: ExpressionOperandId,
  90         region: Option<CodeRegion>,
  91     ) {
  92         debug!(
  93             "add_counter_expression({:?}, lhs={:?}, op={:?}, rhs={:?} at {:?}",
  94             expression_id, lhs, op, rhs, region
  95         );
  96         let expression_index = self.expression_index(u32::from(expression_id));
  97         self.expressions[expression_index]
  98             .replace(Expression { lhs, op, rhs, region })
  99             .expect_none("add_counter_expression called with duplicate `id_descending_from_max`");
 100     }
 101
 102     /// Add a region that will be marked as "unreachable", with a constant "zero counter".
 103     pub fn add_unreachable_region(&mut self, region: CodeRegion) {
 104         self.unreachable_regions.push(region)
 105     }
 106
 107     /// Return the source hash, generated from the HIR node structure, and used to indicate whether
 108     /// or not the source code structure changed between different compilations.
 109     pub fn source_hash(&self) -> u64 {
 110         self.source_hash
 111     }
 112
 113     /// Generate an array of CounterExpressions, and an iterator over all `Counter`s and their
 114     /// associated `Regions` (from which the LLVM-specific `CoverageMapGenerator` will create
 115     /// `CounterMappingRegion`s.
 116     pub fn get_expressions_and_counter_regions<'a>(
 117         &'a self,
 118     ) -> (Vec<CounterExpression>, impl Iterator<Item = (Counter, &'a CodeRegion)>) {
 119         assert!(
 120             self.source_hash != 0,
 121             "No counters provided the source_hash for function: {:?}",
 122             self.instance
 123         );
 124
 125         let counter_regions = self.counter_regions();
 126         let (counter_expressions, expression_regions) = self.expressions_with_regions();
 127         let unreachable_regions = self.unreachable_regions();
 128
 129         let counter_regions =
 130             counter_regions.chain(expression_regions.into_iter().chain(unreachable_regions));
 131         (counter_expressions, counter_regions)
 132     }
 133
 134     fn counter_regions<'a>(&'a self) -> impl Iterator<Item = (Counter, &'a CodeRegion)> {
 135         self.counters.iter_enumerated().filter_map(|(index, entry)| {
 136             // Option::map() will return None to filter out missing counters. This may happen
 137             // if, for example, a MIR-instrumented counter is removed during an optimization.
 138             entry.as_ref().map(|region| {
 139                 (Counter::counter_value_reference(index as CounterValueReference), region)
 140             })
 141         })
 142     }
 143
 144     fn expressions_with_regions(
 145         &'a self,
 146     ) -> (Vec<CounterExpression>, impl Iterator<Item = (Counter, &'a CodeRegion)>) {
 147         let mut counter_expressions = Vec::with_capacity(self.expressions.len());
 148         let mut expression_regions = Vec::with_capacity(self.expressions.len());
 149         let mut new_indexes = IndexVec::from_elem_n(None, self.expressions.len());
 150
 151         // This closure converts any `Expression` operand (`lhs` or `rhs` of the `Op::Add` or
 152         // `Op::Subtract` operation) into its native `llvm::coverage::Counter::CounterKind` type
 153         // and value. Operand ID value `0` maps to `CounterKind::Zero`; values in the known range
 154         // of injected LLVM counters map to `CounterKind::CounterValueReference` (and the value
 155         // matches the injected counter index); and any other value is converted into a
 156         // `CounterKind::Expression` with the expression's `new_index`.
 157         //
 158         // Expressions will be returned from this function in a sequential vector (array) of
 159         // `CounterExpression`, so the expression IDs must be mapped from their original,
 160         // potentially sparse set of indexes, originally in reverse order from `u32::MAX`.
 161         //
 162         // An `Expression` as an operand will have already been encountered as an `Expression` with
 163         // operands, so its new_index will already have been generated (as a 1-up index value).
 164         // (If an `Expression` as an operand does not have a corresponding new_index, it was
 165         // probably optimized out, after the expression was injected into the MIR, so it will
 166         // get a `CounterKind::Zero` instead.)
 167         //
 168         // In other words, an `Expression`s at any given index can include other expressions as
 169         // operands, but expression operands can only come from the subset of expressions having
 170         // `expression_index`s lower than the referencing `Expression`. Therefore, it is
 171         // reasonable to look up the new index of an expression operand while the `new_indexes`
 172         // vector is only complete up to the current `ExpressionIndex`.
 173         let id_to_counter =
 174             |new_indexes: &IndexVec<InjectedExpressionIndex, Option<MappedExpressionIndex>>,
 175              id: ExpressionOperandId| {
 176                 if id == ExpressionOperandId::ZERO {
 177                     Some(Counter::zero())
 178                 } else if id.index() < self.counters.len() {
 179                     // Note: Some codegen-injected Counters may be only referenced by `Expression`s,
 180                     // and may not have their own `CodeRegion`s,
 181                     let index = CounterValueReference::from(id.index());
 182                     Some(Counter::counter_value_reference(index))
 183                 } else {
 184                     let index = self.expression_index(u32::from(id));
 185                     self.expressions
 186                         .get(index)
 187                         .expect("expression id is out of range")
 188                         .as_ref()
 189                         // If an expression was optimized out, assume it would have produced a count
 190                         // of zero. This ensures that expressions dependent on optimized-out
 191                         // expressions are still valid.
 192                         .map_or(Some(Counter::zero()), |_| {
 193                             new_indexes[index].map(|new_index| Counter::expression(new_index))
 194                         })
 195                 }
 196             };
 197
 198         for (original_index, expression) in
 199             self.expressions.iter_enumerated().filter_map(|(original_index, entry)| {
 200                 // Option::map() will return None to filter out missing expressions. This may happen
 201                 // if, for example, a MIR-instrumented expression is removed during an optimization.
 202                 entry.as_ref().map(|expression| (original_index, expression))
 203             })
 204         {
 205             let optional_region = &expression.region;
 206             let Expression { lhs, op, rhs, .. } = *expression;
 207
 208             if let Some(Some((lhs_counter, rhs_counter))) =
 209                 id_to_counter(&new_indexes, lhs).map(|lhs_counter| {
 210                     id_to_counter(&new_indexes, rhs).map(|rhs_counter| (lhs_counter, rhs_counter))
 211                 })
 212             {
 213                 debug_assert!(
 214                     (lhs_counter.id as usize)
 215                         < usize::max(self.counters.len(), self.expressions.len())
 216                 );
 217                 debug_assert!(
 218                     (rhs_counter.id as usize)
 219                         < usize::max(self.counters.len(), self.expressions.len())
 220                 );
 221                 // Both operands exist. `Expression` operands exist in `self.expressions` and have
 222                 // been assigned a `new_index`.
 223                 let mapped_expression_index =
 224                     MappedExpressionIndex::from(counter_expressions.len());
 225                 let expression = CounterExpression::new(
 226                     lhs_counter,
 227                     match op {
 228                         Op::Add => ExprKind::Add,
 229                         Op::Subtract => ExprKind::Subtract,
 230                     },
 231                     rhs_counter,
 232                 );
 233                 debug!(
 234                     "Adding expression {:?} = {:?}, region: {:?}",
 235                     mapped_expression_index, expression, optional_region
 236                 );
 237                 counter_expressions.push(expression);
 238                 new_indexes[original_index] = Some(mapped_expression_index);
 239                 if let Some(region) = optional_region {
 240                     expression_regions.push((Counter::expression(mapped_expression_index), region));
 241                 }
 242             } else {
 243                 debug!(
 244                     "Ignoring expression with one or more missing operands: \
 245                     original_index={:?}, lhs={:?}, op={:?}, rhs={:?}, region={:?}",
 246                     original_index, lhs, op, rhs, optional_region,
 247                 )
 248             }
 249         }
 250         (counter_expressions, expression_regions.into_iter())
 251     }
 252
 253     fn unreachable_regions<'a>(&'a self) -> impl Iterator<Item = (Counter, &'a CodeRegion)> {
 254         self.unreachable_regions.iter().map(|region| (Counter::zero(), region))
 255     }
 256
 257     fn expression_index(&self, id_descending_from_max: u32) -> InjectedExpressionIndex {
 258         debug_assert!(id_descending_from_max >= self.counters.len() as u32);
 259         InjectedExpressionIndex::from(u32::MAX - id_descending_from_max)
 260     }
 261 }