Generating the coverage map

rustc now generates the coverage map and can support (limited)
coverage report generation, at the function level.

Example:

$ BUILD=$HOME/rust/build/x86_64-unknown-linux-gnu
$ $BUILD/stage1/bin/rustc -Zinstrument-coverage \
$HOME/rust/src/test/run-make-fulldeps/instrument-coverage/main.rs
$ LLVM_PROFILE_FILE="main.profraw" ./main
called
$ $BUILD/llvm/bin/llvm-profdata merge -sparse main.profraw -o main.profdata
$ $BUILD/llvm/bin/llvm-cov show --instr-profile=main.profdata main
    1|      1|pub fn will_be_called() {
    2|      1|    println!("called");
    3|      1|}
    4|       |
    5|      0|pub fn will_not_be_called() {
    6|      0|    println!("should not have been called");
    7|      0|}
    8|       |
    9|      1|fn main() {
   10|      1|    let less = 1;
   11|      1|    let more = 100;
   12|      1|
   13|      1|    if less < more {
   14|      1|        will_be_called();
   15|      1|    } else {
   16|      1|        will_not_be_called();
   17|      1|    }
   18|      1|}

5 files changed, 267 insertions, 37 deletions

diff --git a/src/librustc_codegen_ssa/back/link.rs b/src/librustc_codegen_ssa/back/link.rs
index 3adaa07db91..2d65282ce77 100644
--- a/src/librustc_codegen_ssa/back/link.rs
+++ b/src/librustc_codegen_ssa/back/link.rs
@@ -1659,7 +1659,7 @@ fn linker_with_args<'a, B: ArchiveBuilder<'a>>(
     // FIXME: Order dependent, applies to the following objects. Where should it be placed?
     // Try to strip as much out of the generated object by removing unused
     // sections if possible. See more comments in linker.rs
-    if !sess.opts.cg.link_dead_code {
+    if sess.opts.cg.link_dead_code != Some(true) {
         let keep_metadata = crate_type == CrateType::Dylib;
         cmd.gc_sections(keep_metadata);
     }
@@ -1695,7 +1695,7 @@ fn linker_with_args<'a, B: ArchiveBuilder<'a>>(
     );
 
     // OBJECT-FILES-NO, AUDIT-ORDER
-    if sess.opts.cg.profile_generate.enabled() {
+    if sess.opts.cg.profile_generate.enabled() || sess.opts.debugging_opts.instrument_coverage {
         cmd.pgo_gen();
     }
 
diff --git a/src/librustc_codegen_ssa/back/symbol_export.rs b/src/librustc_codegen_ssa/back/symbol_export.rs
index 3287e7b856a..7d742e7a7af 100644
--- a/src/librustc_codegen_ssa/back/symbol_export.rs
+++ b/src/librustc_codegen_ssa/back/symbol_export.rs
@@ -203,6 +203,17 @@ fn exported_symbols_provider_local(
         }));
     }
 
+    if tcx.sess.opts.debugging_opts.instrument_coverage {
+        // Similar to PGO profiling, preserve symbols used by LLVM InstrProf coverage profiling.
+        const COVERAGE_WEAK_SYMBOLS: [&str; 3] =
+            ["__llvm_profile_filename", "__llvm_coverage_mapping", "__llvm_covmap"];
+
+        symbols.extend(COVERAGE_WEAK_SYMBOLS.iter().map(|sym| {
+            let exported_symbol = ExportedSymbol::NoDefId(SymbolName::new(tcx, sym));
+            (exported_symbol, SymbolExportLevel::C)
+        }));
+    }
+
     if tcx.sess.opts.debugging_opts.sanitizer.contains(SanitizerSet::MEMORY) {
         // Similar to profiling, preserve weak msan symbol during LTO.
         const MSAN_WEAK_SYMBOLS: [&str; 2] = ["__msan_track_origins", "__msan_keep_going"];
diff --git a/src/librustc_codegen_ssa/coverageinfo/map.rs b/src/librustc_codegen_ssa/coverageinfo/map.rs
index 3bd262cf2b2..a8ffef8bc5b 100644
--- a/src/librustc_codegen_ssa/coverageinfo/map.rs
+++ b/src/librustc_codegen_ssa/coverageinfo/map.rs
@@ -1,32 +1,154 @@
-use rustc_data_structures::fx::FxHashMap;
-use std::collections::hash_map;
-use std::slice;
+use rustc_data_structures::sync::Lrc;
+use rustc_middle::mir;
+use rustc_span::source_map::{Pos, SourceFile, SourceMap};
+use rustc_span::{BytePos, FileName, 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 {
-    Add,
+    // 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,
 }
 
-pub struct CoverageSpan {
+#[derive(Clone, Debug)]
+pub struct CoverageRegion {
+    pub kind: CoverageKind,
     pub start_byte_pos: u32,
     pub end_byte_pos: u32,
 }
 
-pub struct CoverageRegion {
-    pub kind: CoverageKind,
-    pub coverage_span: CoverageSpan,
+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.
+        }
+    }
+}
+
+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,
+        }
+    }
+}
+
+/// 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,
+}
+
+impl Ord for CoverageLoc {
+    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,
+        ))
+    }
+}
+
+impl PartialOrd for CoverageLoc {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+impl fmt::Display for CoverageLoc {
+    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)
+    }
+}
+
+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);
+
+    // Use 1-based indexing.
+    let line = (found.line + 1) as u32;
+    let col = (byte_pos - line_pos).to_u32() + 1;
+
+    (file, line, col)
 }
 
 /// 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.
+/// 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
@@ -34,50 +156,134 @@ pub struct CoverageRegion {
 /// 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(Default)]
-pub struct FunctionCoverageRegions {
-    indexed: FxHashMap<u32, CoverageRegion>,
-    unreachable: Vec<CoverageSpan>,
+pub struct FunctionCoverage {
+    source_hash: u64,
+    counters: Vec<CoverageRegion>,
+    expressions: Vec<CoverageRegion>,
+    unreachable: Vec<CoverageRegion>,
+    translated: bool,
 }
 
-impl FunctionCoverageRegions {
-    pub fn add_counter(&mut self, index: u32, start_byte_pos: u32, end_byte_pos: u32) {
-        self.indexed.insert(
-            index,
-            CoverageRegion {
-                kind: CoverageKind::Counter,
-                coverage_span: CoverageSpan { start_byte_pos, end_byte_pos },
-            },
-        );
+impl FunctionCoverage {
+    pub fn with_coverageinfo<'tcx>(coverageinfo: &'tcx mir::CoverageInfo) -> Self {
+        Self {
+            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,
+        }
     }
 
-    pub fn add_counter_expression(
+    /// Adds a code region to be counted by an injected counter intrinsic. Return a counter ID
+    /// for the call.
+    pub fn add_counter(
         &mut self,
+        source_hash: u64,
         index: 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 };
+    }
+
+    pub fn add_counter_expression(
+        &mut self,
+        translated_index: u32,
         lhs: u32,
         op: CounterOp,
         rhs: u32,
         start_byte_pos: u32,
         end_byte_pos: u32,
     ) {
-        self.indexed.insert(
-            index,
-            CoverageRegion {
-                kind: CoverageKind::CounterExpression(lhs, op, rhs),
-                coverage_span: CoverageSpan { start_byte_pos, end_byte_pos },
-            },
-        );
+        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,
+        };
     }
 
     pub fn add_unreachable(&mut self, start_byte_pos: u32, end_byte_pos: u32) {
-        self.unreachable.push(CoverageSpan { start_byte_pos, end_byte_pos });
+        self.unreachable.push(CoverageRegion {
+            kind: CoverageKind::Unreachable,
+            start_byte_pos,
+            end_byte_pos,
+        });
+    }
+
+    pub fn source_hash(&self) -> u64 {
+        self.source_hash
+    }
+
+    fn regions(&'a mut self) -> impl Iterator<Item = &'a CoverageRegion> {
+        assert!(self.source_hash != 0);
+        self.ensure_expressions_translated();
+        self.counters.iter().chain(self.expressions.iter().chain(self.unreachable.iter()))
     }
 
-    pub fn indexed_regions(&self) -> hash_map::Iter<'_, u32, CoverageRegion> {
-        self.indexed.iter()
+    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
     }
 
-    pub fn unreachable_regions(&self) -> slice::Iter<'_, CoverageSpan> {
-        self.unreachable.iter()
+    /// 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 to_region_index(start: u32, index: u32) -> u32 {
+    if index < start { index } else { start + (u32::MAX - index) }
+}
diff --git a/src/librustc_codegen_ssa/traits/coverageinfo.rs b/src/librustc_codegen_ssa/traits/coverageinfo.rs
index d80f90fa4fa..1b9faa42484 100644
--- a/src/librustc_codegen_ssa/traits/coverageinfo.rs
+++ b/src/librustc_codegen_ssa/traits/coverageinfo.rs
@@ -10,6 +10,7 @@ pub trait CoverageInfoBuilderMethods<'tcx>: BackendTypes {
     fn add_counter_region(
         &mut self,
         instance: Instance<'tcx>,
+        function_source_hash: u64,
         index: u32,
         start_byte_pos: u32,
         end_byte_pos: u32,
diff --git a/src/librustc_codegen_ssa/traits/statics.rs b/src/librustc_codegen_ssa/traits/statics.rs
index a6462b35834..817fc02d166 100644
--- a/src/librustc_codegen_ssa/traits/statics.rs
+++ b/src/librustc_codegen_ssa/traits/statics.rs
@@ -5,6 +5,18 @@ use rustc_target::abi::Align;
 pub trait StaticMethods: BackendTypes {
     fn static_addr_of(&self, cv: Self::Value, align: Align, kind: Option<&str>) -> Self::Value;
     fn codegen_static(&self, def_id: DefId, is_mutable: bool);
+
+    /// Mark the given global value as "used", to prevent a backend from potentially removing a
+    /// static variable that may otherwise appear unused.
+    ///
+    /// Static variables in Rust can be annotated with the `#[used]` attribute to direct the `rustc`
+    /// compiler to mark the variable as a "used global".
+    ///
+    /// ```no_run
+    /// #[used]
+    /// static FOO: u32 = 0;
+    /// ```
+    fn add_used_global(&self, global: Self::Value);
 }
 
 pub trait StaticBuilderMethods: BackendTypes {