Auto merge of #74733 - richkadel:llvm-coverage-map-gen-5, r=tmandry

Fixed coverage map issues; better aligned with LLVM APIs

Found some problems with the coverage map encoding when testing with more than one counter per function.

While debugging, I realized some better ways to structure the Rust implementation of the coverage mapping generator. I refactored somewhat, resulting in less code overall, expanded coverage of LLVM Coverage Map capabilities, and much closer alignment with LLVM data structures, APIs, and naming.

This should be easier to follow and easier to maintain.

r? @tmandry

Rust compiler MCP rust-lang/compiler-team#278
Relevant issue: #34701 - Implement support for LLVMs code coverage instrumentation

5 files changed, 355 insertions, 213 deletions

diff --git a/src/librustc_codegen_ssa/coverageinfo/ffi.rs b/src/librustc_codegen_ssa/coverageinfo/ffi.rs
new file mode 100644
index 00000000000..5b04f994994
--- /dev/null
+++ b/src/librustc_codegen_ssa/coverageinfo/ffi.rs
@@ -0,0 +1,67 @@
+use super::map::{CounterValueReference, MappedExpressionIndex};
+
+/// Aligns with [llvm::coverage::Counter::CounterKind](https://github.com/rust-lang/llvm-project/blob/rustc/10.0-2020-05-05/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h#L91)
+#[derive(Copy, Clone, Debug)]
+#[repr(C)]
+enum CounterKind {
+    Zero = 0,
+    CounterValueReference = 1,
+    Expression = 2,
+}
+
+/// A reference to an instance of an abstract "counter" that will yield a value in a coverage
+/// report. Note that `id` has different interpretations, depending on the `kind`:
+///   * For `CounterKind::Zero`, `id` is assumed to be `0`
+///   * For `CounterKind::CounterValueReference`,  `id` matches the `counter_id` of the injected
+///     instrumentation counter (the `index` argument to the LLVM intrinsic
+///     `instrprof.increment()`)
+///   * For `CounterKind::Expression`, `id` is the index into the coverage map's array of
+///     counter expressions.
+/// Aligns with [llvm::coverage::Counter](https://github.com/rust-lang/llvm-project/blob/rustc/10.0-2020-05-05/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h#L98-L99)
+/// Important: The Rust struct layout (order and types of fields) must match its C++ counterpart.
+#[derive(Copy, Clone, Debug)]
+#[repr(C)]
+pub struct Counter {
+    // Important: The layout (order and types of fields) must match its C++ counterpart.
+    kind: CounterKind,
+    id: u32,
+}
+
+impl Counter {
+    pub fn zero() -> Self {
+        Self { kind: CounterKind::Zero, id: 0 }
+    }
+
+    pub fn counter_value_reference(counter_id: CounterValueReference) -> Self {
+        Self { kind: CounterKind::CounterValueReference, id: counter_id.into() }
+    }
+
+    pub fn expression(mapped_expression_index: MappedExpressionIndex) -> Self {
+        Self { kind: CounterKind::Expression, id: mapped_expression_index.into() }
+    }
+}
+
+/// Aligns with [llvm::coverage::CounterExpression::ExprKind](https://github.com/rust-lang/llvm-project/blob/rustc/10.0-2020-05-05/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h#L146)
+#[derive(Copy, Clone, Debug)]
+#[repr(C)]
+pub enum ExprKind {
+    Subtract = 0,
+    Add = 1,
+}
+
+/// Aligns with [llvm::coverage::CounterExpression](https://github.com/rust-lang/llvm-project/blob/rustc/10.0-2020-05-05/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h#L147-L148)
+/// Important: The Rust struct layout (order and types of fields) must match its C++
+/// counterpart.
+#[derive(Copy, Clone, Debug)]
+#[repr(C)]
+pub struct CounterExpression {
+    kind: ExprKind,
+    lhs: Counter,
+    rhs: Counter,
+}
+
+impl CounterExpression {
+    pub fn new(lhs: Counter, kind: ExprKind, rhs: Counter) -> Self {
+        Self { kind, lhs, rhs }
+    }
+}
diff --git a/src/librustc_codegen_ssa/coverageinfo/map.rs b/src/librustc_codegen_ssa/coverageinfo/map.rs
index a8ffef8bc5b..1e36c90baaf 100644
--- a/src/librustc_codegen_ssa/coverageinfo/map.rs
+++ b/src/librustc_codegen_ssa/coverageinfo/map.rs
@@ -1,289 +1,360 @@
-use rustc_data_structures::sync::Lrc;
-use rustc_middle::mir;
-use rustc_span::source_map::{Pos, SourceFile, SourceMap};
-use rustc_span::{BytePos, FileName, RealFileName};
+pub use super::ffi::*;
+
+use rustc_index::vec::IndexVec;
+use rustc_middle::ty::Instance;
+use rustc_middle::ty::TyCtxt;
+use rustc_span::source_map::{Pos, SourceMap};
+use rustc_span::{BytePos, FileName, Loc, RealFileName};
 
 use std::cmp::{Ord, Ordering};
-use std::collections::BTreeMap;
 use std::fmt;
 use std::path::PathBuf;
 
-#[derive(Copy, Clone, Debug)]
-#[repr(C)]
-pub enum CounterOp {
-    // Note the order (and therefore the default values) is important. With the attribute
-    // `#[repr(C)]`, this enum matches the layout of the LLVM enum defined for the nested enum,
-    // `llvm::coverage::CounterExpression::ExprKind`, as shown in the following source snippet:
-    // https://github.com/rust-lang/llvm-project/blob/f208b70fbc4dee78067b3c5bd6cb92aa3ba58a1e/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h#L146
-    Subtract,
-    Add,
-}
-
-#[derive(Copy, Clone, Debug)]
-pub enum CoverageKind {
-    Counter,
-    CounterExpression(u32, CounterOp, u32),
-    Unreachable,
+rustc_index::newtype_index! {
+    pub struct ExpressionOperandId {
+        DEBUG_FORMAT = "ExpressionOperandId({})",
+        MAX = 0xFFFF_FFFF,
+    }
 }
 
-#[derive(Clone, Debug)]
-pub struct CoverageRegion {
-    pub kind: CoverageKind,
-    pub start_byte_pos: u32,
-    pub end_byte_pos: u32,
+rustc_index::newtype_index! {
+    pub struct CounterValueReference {
+        DEBUG_FORMAT = "CounterValueReference({})",
+        MAX = 0xFFFF_FFFF,
+    }
 }
 
-impl CoverageRegion {
-    pub fn source_loc(&self, source_map: &SourceMap) -> Option<(Lrc<SourceFile>, CoverageLoc)> {
-        let (start_file, start_line, start_col) =
-            lookup_file_line_col(source_map, BytePos::from_u32(self.start_byte_pos));
-        let (end_file, end_line, end_col) =
-            lookup_file_line_col(source_map, BytePos::from_u32(self.end_byte_pos));
-        let start_file_path = match &start_file.name {
-            FileName::Real(RealFileName::Named(path)) => path,
-            _ => {
-                bug!("start_file_path should be a RealFileName, but it was: {:?}", start_file.name)
-            }
-        };
-        let end_file_path = match &end_file.name {
-            FileName::Real(RealFileName::Named(path)) => path,
-            _ => bug!("end_file_path should be a RealFileName, but it was: {:?}", end_file.name),
-        };
-        if start_file_path == end_file_path {
-            Some((start_file, CoverageLoc { start_line, start_col, end_line, end_col }))
-        } else {
-            None
-            // FIXME(richkadel): There seems to be a problem computing the file location in
-            // some cases. I need to investigate this more. When I generate and show coverage
-            // for the example binary in the crates.io crate `json5format`, I had a couple of
-            // notable problems:
-            //
-            //   1. I saw a lot of coverage spans in `llvm-cov show` highlighting regions in
-            //      various comments (not corresponding to rustdoc code), indicating a possible
-            //      problem with the byte_pos-to-source-map implementation.
-            //
-            //   2. And (perhaps not related) when I build the aforementioned example binary with:
-            //      `RUST_FLAGS="-Zinstrument-coverage" cargo build --example formatjson5`
-            //      and then run that binary with
-            //      `LLVM_PROFILE_FILE="formatjson5.profraw" ./target/debug/examples/formatjson5 \
-            //      some.json5` for some reason the binary generates *TWO* `.profraw` files. One
-            //      named `default.profraw` and the other named `formatjson5.profraw` (the expected
-            //      name, in this case).
-            //
-            // If the byte range conversion is wrong, fix it. But if it
-            // is right, then it is possible for the start and end to be in different files.
-            // Can I do something other than ignore coverages that span multiple files?
-            //
-            // If I can resolve this, remove the "Option<>" result type wrapper
-            // `regions_in_file_order()` accordingly.
-        }
+rustc_index::newtype_index! {
+    pub struct InjectedExpressionIndex {
+        DEBUG_FORMAT = "InjectedExpressionIndex({})",
+        MAX = 0xFFFF_FFFF,
     }
 }
 
-impl Default for CoverageRegion {
-    fn default() -> Self {
-        Self {
-            // The default kind (Unreachable) is a placeholder that will be overwritten before
-            // backend codegen.
-            kind: CoverageKind::Unreachable,
-            start_byte_pos: 0,
-            end_byte_pos: 0,
-        }
+rustc_index::newtype_index! {
+    pub struct MappedExpressionIndex {
+        DEBUG_FORMAT = "MappedExpressionIndex({})",
+        MAX = 0xFFFF_FFFF,
     }
 }
 
-/// A source code region used with coverage information.
-#[derive(Debug, Eq, PartialEq)]
-pub struct CoverageLoc {
-    /// The (1-based) line number of the region start.
-    pub start_line: u32,
-    /// The (1-based) column number of the region start.
-    pub start_col: u32,
-    /// The (1-based) line number of the region end.
-    pub end_line: u32,
-    /// The (1-based) column number of the region end.
-    pub end_col: u32,
+#[derive(Clone, Debug)]
+pub struct Region {
+    start: Loc,
+    end: Loc,
 }
 
-impl Ord for CoverageLoc {
+impl Ord for Region {
     fn cmp(&self, other: &Self) -> Ordering {
-        (self.start_line, &self.start_col, &self.end_line, &self.end_col).cmp(&(
-            other.start_line,
-            &other.start_col,
-            &other.end_line,
-            &other.end_col,
-        ))
+        (&self.start.file.name, &self.start.line, &self.start.col, &self.end.line, &self.end.col)
+            .cmp(&(
+                &other.start.file.name,
+                &other.start.line,
+                &other.start.col,
+                &other.end.line,
+                &other.end.col,
+            ))
     }
 }
 
-impl PartialOrd for CoverageLoc {
+impl PartialOrd for Region {
     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
         Some(self.cmp(other))
     }
 }
 
-impl fmt::Display for CoverageLoc {
+impl PartialEq for Region {
+    fn eq(&self, other: &Self) -> bool {
+        self.start.file.name == other.start.file.name
+            && self.start.line == other.start.line
+            && self.start.col == other.start.col
+            && self.end.line == other.end.line
+            && self.end.col == other.end.col
+    }
+}
+
+impl Eq for Region {}
+
+impl fmt::Display for Region {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        // Customize debug format, and repeat the file name, so generated location strings are
-        // "clickable" in many IDEs.
-        write!(f, "{}:{} - {}:{}", self.start_line, self.start_col, self.end_line, self.end_col)
+        let (file_path, start_line, start_col, end_line, end_col) = self.file_start_and_end();
+        write!(f, "{:?}:{}:{} - {}:{}", file_path, start_line, start_col, end_line, end_col)
     }
 }
 
-fn lookup_file_line_col(source_map: &SourceMap, byte_pos: BytePos) -> (Lrc<SourceFile>, u32, u32) {
-    let found = source_map
-        .lookup_line(byte_pos)
-        .expect("should find coverage region byte position in source");
-    let file = found.sf;
-    let line_pos = file.line_begin_pos(byte_pos);
+impl Region {
+    pub fn new(source_map: &SourceMap, start_byte_pos: u32, end_byte_pos: u32) -> Self {
+        let start = source_map.lookup_char_pos(BytePos::from_u32(start_byte_pos));
+        let end = source_map.lookup_char_pos(BytePos::from_u32(end_byte_pos));
+        assert_eq!(start.file.name, end.file.name);
+        Self { start, end }
+    }
 
-    // Use 1-based indexing.
-    let line = (found.line + 1) as u32;
-    let col = (byte_pos - line_pos).to_u32() + 1;
+    pub fn file_start_and_end<'a>(&'a self) -> (&'a PathBuf, u32, u32, u32, u32) {
+        let start = &self.start;
+        let end = &self.end;
+        match &start.file.name {
+            FileName::Real(RealFileName::Named(path)) => (
+                path,
+                start.line as u32,
+                start.col.to_u32() + 1,
+                end.line as u32,
+                end.col.to_u32() + 1,
+            ),
+            _ => {
+                bug!("start.file.name should be a RealFileName, but it was: {:?}", start.file.name)
+            }
+        }
+    }
+}
 
-    (file, line, col)
+#[derive(Clone, Debug)]
+pub struct ExpressionRegion {
+    lhs: ExpressionOperandId,
+    op: ExprKind,
+    rhs: ExpressionOperandId,
+    region: Region,
 }
 
+// FIXME(richkadel): There seems to be a problem computing the file location in
+// some cases. I need to investigate this more. When I generate and show coverage
+// for the example binary in the crates.io crate `json5format`, I had a couple of
+// notable problems:
+//
+//   1. I saw a lot of coverage spans in `llvm-cov show` highlighting regions in
+//      various comments (not corresponding to rustdoc code), indicating a possible
+//      problem with the byte_pos-to-source-map implementation.
+//
+//   2. And (perhaps not related) when I build the aforementioned example binary with:
+//      `RUST_FLAGS="-Zinstrument-coverage" cargo build --example formatjson5`
+//      and then run that binary with
+//      `LLVM_PROFILE_FILE="formatjson5.profraw" ./target/debug/examples/formatjson5 \
+//      some.json5` for some reason the binary generates *TWO* `.profraw` files. One
+//      named `default.profraw` and the other named `formatjson5.profraw` (the expected
+//      name, in this case).
+//
+//   3. I think that if I eliminate regions within a function, their region_ids,
+//      referenced in expressions, will be wrong? I think the ids are implied by their
+//      array position in the final coverage map output (IIRC).
+//
+//   4. I suspect a problem (if not the only problem) is the SourceMap is wrong for some
+//      region start/end byte positions. Just like I couldn't get the function hash at
+//      intrinsic codegen time for external crate functions, I think the SourceMap I
+//      have here only applies to the local crate, and I know I have coverages that
+//      reference external crates.
+//
+//          I still don't know if I fixed the hash problem correctly. If external crates
+//          implement the function, can't I use the coverage counters already compiled
+//          into those external crates? (Maybe not for generics and/or maybe not for
+//          macros... not sure. But I need to understand this better.)
+//
+// If the byte range conversion is wrong, fix it. But if it
+// is right, then it is possible for the start and end to be in different files.
+// Can I do something other than ignore coverages that span multiple files?
+//
+// If I can resolve this, remove the "Option<>" result type wrapper
+// `regions_in_file_order()` accordingly.
+
 /// 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 are indexed because they can be operands
-/// in an expression. This struct also stores the `function_source_hash`, computed during
-/// instrumentation and forwarded with counters.
+/// 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's important to distinguish the `unreachable` region type from what LLVM's refers to as
-/// a "gap region" (or "gap area"). 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."
-pub struct FunctionCoverage {
+/// 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."
+pub struct FunctionCoverage<'a> {
+    source_map: &'a SourceMap,
     source_hash: u64,
-    counters: Vec<CoverageRegion>,
-    expressions: Vec<CoverageRegion>,
-    unreachable: Vec<CoverageRegion>,
-    translated: bool,
+    counters: IndexVec<CounterValueReference, Option<Region>>,
+    expressions: IndexVec<InjectedExpressionIndex, Option<ExpressionRegion>>,
+    unreachable_regions: Vec<Region>,
 }
 
-impl FunctionCoverage {
-    pub fn with_coverageinfo<'tcx>(coverageinfo: &'tcx mir::CoverageInfo) -> Self {
+impl<'a> FunctionCoverage<'a> {
+    pub fn new<'tcx: 'a>(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>) -> Self {
+        let coverageinfo = tcx.coverageinfo(instance.def_id());
         Self {
+            source_map: tcx.sess.source_map(),
             source_hash: 0, // will be set with the first `add_counter()`
-            counters: vec![CoverageRegion::default(); coverageinfo.num_counters as usize],
-            expressions: vec![CoverageRegion::default(); coverageinfo.num_expressions as usize],
-            unreachable: Vec::new(),
-            translated: false,
+            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(),
         }
     }
 
-    /// Adds a code region to be counted by an injected counter intrinsic. Return a counter ID
-    /// for the call.
+    /// Adds a code region to be counted by an injected counter intrinsic.
+    /// The source_hash (computed during coverage instrumentation) should also be provided, and
+    /// should be the same for all counters in a given function.
     pub fn add_counter(
         &mut self,
         source_hash: u64,
-        index: u32,
+        id: u32,
         start_byte_pos: u32,
         end_byte_pos: u32,
     ) {
-        self.source_hash = source_hash;
-        self.counters[index as usize] =
-            CoverageRegion { kind: CoverageKind::Counter, start_byte_pos, end_byte_pos };
+        if self.source_hash == 0 {
+            self.source_hash = source_hash;
+        } else {
+            debug_assert_eq!(source_hash, self.source_hash);
+        }
+        self.counters[CounterValueReference::from(id)]
+            .replace(Region::new(self.source_map, start_byte_pos, end_byte_pos))
+            .expect_none("add_counter called with duplicate `id`");
     }
 
+    /// 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,
-        translated_index: u32,
+        id_descending_from_max: u32,
         lhs: u32,
-        op: CounterOp,
+        op: ExprKind,
         rhs: u32,
         start_byte_pos: u32,
         end_byte_pos: u32,
     ) {
-        let index = u32::MAX - translated_index;
-        // Counter expressions start with "translated indexes", descending from `u32::MAX`, so
-        // the range of expression indexes is disjoint from the range of counter indexes. This way,
-        // both counters and expressions can be operands in other expressions.
-        //
-        // Once all counters have been added, the final "region index" for an expression is
-        // `counters.len() + expression_index` (where `expression_index` is its index in
-        // `self.expressions`), and the expression operands (`lhs` and `rhs`) can be converted to
-        // final "region index" references by the same conversion, after subtracting from
-        // `u32::MAX`.
-        self.expressions[index as usize] = CoverageRegion {
-            kind: CoverageKind::CounterExpression(lhs, op, rhs),
-            start_byte_pos,
-            end_byte_pos,
-        };
+        let expression_id = ExpressionOperandId::from(id_descending_from_max);
+        let lhs = ExpressionOperandId::from(lhs);
+        let rhs = ExpressionOperandId::from(rhs);
+
+        let expression_index = self.expression_index(expression_id);
+        self.expressions[expression_index]
+            .replace(ExpressionRegion {
+                lhs,
+                op,
+                rhs,
+                region: Region::new(self.source_map, start_byte_pos, end_byte_pos),
+            })
+            .expect_none("add_counter_expression called with duplicate `id_descending_from_max`");
     }
 
-    pub fn add_unreachable(&mut self, start_byte_pos: u32, end_byte_pos: u32) {
-        self.unreachable.push(CoverageRegion {
-            kind: CoverageKind::Unreachable,
-            start_byte_pos,
-            end_byte_pos,
-        });
+    /// Add a region that will be marked as "unreachable", with a constant "zero counter".
+    pub fn add_unreachable_region(&mut self, start_byte_pos: u32, end_byte_pos: u32) {
+        self.unreachable_regions.push(Region::new(self.source_map, start_byte_pos, end_byte_pos));
     }
 
+    /// 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
     }
 
-    fn regions(&'a mut self) -> impl Iterator<Item = &'a CoverageRegion> {
+    /// 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(
+        &'a self,
+    ) -> (Vec<CounterExpression>, impl Iterator<Item = (Counter, &'a Region)>) {
         assert!(self.source_hash != 0);
-        self.ensure_expressions_translated();
-        self.counters.iter().chain(self.expressions.iter().chain(self.unreachable.iter()))
+
+        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)
     }
 
-    pub fn regions_in_file_order(
-        &'a mut self,
-        source_map: &SourceMap,
-    ) -> BTreeMap<PathBuf, BTreeMap<CoverageLoc, (usize, CoverageKind)>> {
-        let mut regions_in_file_order = BTreeMap::new();
-        for (region_id, region) in self.regions().enumerate() {
-            if let Some((source_file, region_loc)) = region.source_loc(source_map) {
-                // FIXME(richkadel): `region.source_loc()` sometimes fails with two different
-                // filenames for the start and end byte position. This seems wrong, but for
-                // now, if encountered, the region is skipped. If resolved, convert the result
-                // to a non-option value so regions are never skipped.
-                let real_file_path = match &(*source_file).name {
-                    FileName::Real(RealFileName::Named(path)) => path.clone(),
-                    _ => bug!("coverage mapping expected only real, named files"),
-                };
-                let file_coverage_regions =
-                    regions_in_file_order.entry(real_file_path).or_insert_with(|| BTreeMap::new());
-                file_coverage_regions.insert(region_loc, (region_id, region.kind));
-            }
-        }
-        regions_in_file_order
+    fn counter_regions(&'a self) -> impl Iterator<Item = (Counter, &'a Region)> {
+        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 as CounterValueReference), region)
+            })
+        })
     }
 
-    /// A one-time translation of expression operands is needed, for any operands referencing
-    /// other CounterExpressions. CounterExpression operands get an initial operand ID that is
-    /// computed by the simple translation: `u32::max - expression_index` because, when created,
-    /// the total number of Counters is not yet known. This function recomputes region indexes
-    /// for expressions so they start with the next region index after the last counter index.
-    fn ensure_expressions_translated(&mut self) {
-        if !self.translated {
-            self.translated = true;
-            let start = self.counters.len() as u32;
-            assert!(
-                (start as u64 + self.expressions.len() as u64) < u32::MAX as u64,
-                "the number of counters and counter expressions in a single function exceeds {}",
-                u32::MAX
-            );
-            for region in self.expressions.iter_mut() {
-                match region.kind {
-                    CoverageKind::CounterExpression(lhs, op, rhs) => {
-                        let lhs = to_region_index(start, lhs);
-                        let rhs = to_region_index(start, rhs);
-                        region.kind = CoverageKind::CounterExpression(lhs, op, rhs);
-                    }
-                    _ => bug!("expressions must only contain CounterExpression kinds"),
+    fn expressions_with_regions(
+        &'a self,
+    ) -> (Vec<CounterExpression>, impl Iterator<Item = (Counter, &'a Region)>) {
+        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(MappedExpressionIndex::from(u32::MAX), self.expressions.len());
+        // Note, the initial value shouldn't matter since every index in use in `self.expressions`
+        // will be set, and after that, `new_indexes` will only be accessed using those same
+        // indexes.
+
+        // Note that an `ExpressionRegion`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 `ExpressionRegion`. 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, MappedExpressionIndex>,
+             id: ExpressionOperandId| {
+                if id.index() < self.counters.len() {
+                    let index = CounterValueReference::from(id.index());
+                    self.counters
+                        .get(index)
+                        .unwrap() // pre-validated
+                        .as_ref()
+                        .map(|_| Counter::counter_value_reference(index))
+                } else {
+                    let index = self.expression_index(id);
+                    self.expressions
+                        .get(index)
+                        .expect("expression id is out of range")
+                        .as_ref()
+                        .map(|_| Counter::expression(new_indexes[index]))
                 }
+            };
+
+        for (original_index, expression_region) 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(|region| (original_index, region))
+            })
+        {
+            let region = &expression_region.region;
+            let ExpressionRegion { lhs, op, rhs, .. } = *expression_region;
+
+            if let Some(Some((lhs_counter, rhs_counter))) =
+                id_to_counter(&new_indexes, lhs).map(|lhs_counter| {
+                    id_to_counter(&new_indexes, rhs).map(|rhs_counter| (lhs_counter, 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());
+                counter_expressions.push(CounterExpression::new(lhs_counter, op, rhs_counter));
+                new_indexes[original_index] = mapped_expression_index;
+                expression_regions.push((Counter::expression(mapped_expression_index), region));
             }
         }
+        (counter_expressions, expression_regions.into_iter())
+    }
+
+    fn unreachable_regions(&'a self) -> impl Iterator<Item = (Counter, &'a Region)> {
+        self.unreachable_regions.iter().map(|region| (Counter::zero(), region))
     }
-}
 
-fn to_region_index(start: u32, index: u32) -> u32 {
-    if index < start { index } else { start + (u32::MAX - index) }
+    fn expression_index(
+        &self,
+        id_descending_from_max: ExpressionOperandId,
+    ) -> InjectedExpressionIndex {
+        debug_assert!(id_descending_from_max.index() >= self.counters.len());
+        InjectedExpressionIndex::from(u32::MAX - u32::from(id_descending_from_max))
+    }
 }
diff --git a/src/librustc_codegen_ssa/coverageinfo/mod.rs b/src/librustc_codegen_ssa/coverageinfo/mod.rs
index 304f8e19da4..1f0ffd289b1 100644
--- a/src/librustc_codegen_ssa/coverageinfo/mod.rs
+++ b/src/librustc_codegen_ssa/coverageinfo/mod.rs
@@ -1,3 +1,4 @@
+pub mod ffi;
 pub mod map;
 
-pub use map::CounterOp;
+pub use map::ExprKind;
diff --git a/src/librustc_codegen_ssa/lib.rs b/src/librustc_codegen_ssa/lib.rs
index bdd73c08313..85260d30a3d 100644
--- a/src/librustc_codegen_ssa/lib.rs
+++ b/src/librustc_codegen_ssa/lib.rs
@@ -1,5 +1,6 @@
 #![doc(html_root_url = "https://doc.rust-lang.org/nightly/")]
 #![feature(bool_to_option)]
+#![feature(option_expect_none)]
 #![feature(box_patterns)]
 #![feature(try_blocks)]
 #![feature(in_band_lifetimes)]
@@ -7,6 +8,8 @@
 #![feature(or_patterns)]
 #![feature(trusted_len)]
 #![feature(associated_type_bounds)]
+#![feature(const_fn)] // for rustc_index::newtype_index
+#![feature(const_panic)] // for rustc_index::newtype_index
 #![recursion_limit = "256"]
 
 //! This crate contains codegen code that is used by all codegen backends (LLVM and others).
diff --git a/src/librustc_codegen_ssa/traits/coverageinfo.rs b/src/librustc_codegen_ssa/traits/coverageinfo.rs
index 1b9faa42484..db1d86c974e 100644
--- a/src/librustc_codegen_ssa/traits/coverageinfo.rs
+++ b/src/librustc_codegen_ssa/traits/coverageinfo.rs
@@ -1,5 +1,5 @@
 use super::BackendTypes;
-use crate::coverageinfo::CounterOp;
+use crate::coverageinfo::ExprKind;
 use rustc_middle::ty::Instance;
 
 pub trait CoverageInfoMethods: BackendTypes {
@@ -21,7 +21,7 @@ pub trait CoverageInfoBuilderMethods<'tcx>: BackendTypes {
         instance: Instance<'tcx>,
         index: u32,
         lhs: u32,
-        op: CounterOp,
+        op: ExprKind,
         rhs: u32,
         start_byte_pos: u32,
         end_byte_pos: u32,