add spans to injected coverage counters

added regions with counter expressions and counters.

Added codegen_llvm/coverageinfo mod for upcoming coverage map

Move coverage region collection to CodegenCx finalization

Moved from `query coverageinfo` (renamed from `query coverage_data`),
as discussed in the PR at:

https://github.com/rust-lang/rust/pull/73684#issuecomment-649882503

Address merge conflict in MIR instrument_coverage test

The MIR test output format changed for int types.

moved debug messages out of block.rs

This makes the block.rs calls to add coverage mapping data to the
CodegenCx much more concise and readable.

move coverage intrinsic handling into llvm impl

I realized that having half of the coverage intrinsic handling in
`rustc_codegen_ssa` and half in `rustc_codegen_llvm` meant that any
non-llvm backend would be bound to the same decisions about how the
coverage-related MIR terminators should be handled.

To fix this, I moved the non-codegen portion of coverage intrinsic
handling into its own trait, and implemented it in `rustc_codegen_llvm`
alongside `codegen_intrinsic_call`.

I also added the (required?) stubs for the new intrinsics to
`IntrepretCx::emulate_intrinsic()`, to ensure calls to this function do
not fail if called with these new but known intrinsics.

address PR Feedback on 28 June 2020 2:48pm PDT

8 files changed, 152 insertions, 1 deletions

diff --git a/src/librustc_codegen_ssa/coverageinfo/map.rs b/src/librustc_codegen_ssa/coverageinfo/map.rs
new file mode 100644
index 00000000000..3bd262cf2b2
--- /dev/null
+++ b/src/librustc_codegen_ssa/coverageinfo/map.rs
@@ -0,0 +1,83 @@
+use rustc_data_structures::fx::FxHashMap;
+use std::collections::hash_map;
+use std::slice;
+
+#[derive(Copy, Clone, Debug)]
+pub enum CounterOp {
+    Add,
+    Subtract,
+}
+
+pub enum CoverageKind {
+    Counter,
+    CounterExpression(u32, CounterOp, u32),
+}
+
+pub struct CoverageSpan {
+    pub start_byte_pos: u32,
+    pub end_byte_pos: u32,
+}
+
+pub struct CoverageRegion {
+    pub kind: CoverageKind,
+    pub coverage_span: CoverageSpan,
+}
+
+/// 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.
+///
+/// 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."
+#[derive(Default)]
+pub struct FunctionCoverageRegions {
+    indexed: FxHashMap<u32, CoverageRegion>,
+    unreachable: Vec<CoverageSpan>,
+}
+
+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 },
+            },
+        );
+    }
+
+    pub fn add_counter_expression(
+        &mut self,
+        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 },
+            },
+        );
+    }
+
+    pub fn add_unreachable(&mut self, start_byte_pos: u32, end_byte_pos: u32) {
+        self.unreachable.push(CoverageSpan { start_byte_pos, end_byte_pos });
+    }
+
+    pub fn indexed_regions(&self) -> hash_map::Iter<'_, u32, CoverageRegion> {
+        self.indexed.iter()
+    }
+
+    pub fn unreachable_regions(&self) -> slice::Iter<'_, CoverageSpan> {
+        self.unreachable.iter()
+    }
+}
diff --git a/src/librustc_codegen_ssa/coverageinfo/mod.rs b/src/librustc_codegen_ssa/coverageinfo/mod.rs
new file mode 100644
index 00000000000..304f8e19da4
--- /dev/null
+++ b/src/librustc_codegen_ssa/coverageinfo/mod.rs
@@ -0,0 +1,3 @@
+pub mod map;
+
+pub use map::CounterOp;
diff --git a/src/librustc_codegen_ssa/lib.rs b/src/librustc_codegen_ssa/lib.rs
index bd3721850f3..618df15f5bc 100644
--- a/src/librustc_codegen_ssa/lib.rs
+++ b/src/librustc_codegen_ssa/lib.rs
@@ -34,6 +34,7 @@ use std::path::{Path, PathBuf};
 pub mod back;
 pub mod base;
 pub mod common;
+pub mod coverageinfo;
 pub mod debuginfo;
 pub mod glue;
 pub mod meth;
diff --git a/src/librustc_codegen_ssa/mir/block.rs b/src/librustc_codegen_ssa/mir/block.rs
index 480f9a50320..7514eb8e889 100644
--- a/src/librustc_codegen_ssa/mir/block.rs
+++ b/src/librustc_codegen_ssa/mir/block.rs
@@ -651,6 +651,18 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
         }
 
         if intrinsic.is_some() && intrinsic != Some("drop_in_place") {
+            let intrinsic = intrinsic.unwrap();
+
+            // `is_codegen_intrinsic()` allows the backend implementation to perform compile-time
+            // operations before converting the `args` to backend values.
+            if !bx.is_codegen_intrinsic(intrinsic, &args, self.instance) {
+                // If the intrinsic call was fully addressed by the `is_codegen_intrinsic()` call
+                // (as a compile-time operation), return immediately. This avoids the need to
+                // convert the arguments, the call to `codegen_intrinsic_call()`, and the return
+                // value handling.
+                return;
+            }
+
             let dest = match ret_dest {
                 _ if fn_abi.ret.is_indirect() => llargs[0],
                 ReturnDest::Nothing => {
@@ -670,7 +682,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
                     // third argument must be constant. This is
                     // checked by const-qualification, which also
                     // promotes any complex rvalues to constants.
-                    if i == 2 && intrinsic.unwrap().starts_with("simd_shuffle") {
+                    if i == 2 && intrinsic.starts_with("simd_shuffle") {
                         if let mir::Operand::Constant(constant) = arg {
                             let c = self.eval_mir_constant(constant);
                             let (llval, ty) = self.simd_shuffle_indices(
diff --git a/src/librustc_codegen_ssa/traits/builder.rs b/src/librustc_codegen_ssa/traits/builder.rs
index 7ffc9f15bff..994d8e0395d 100644
--- a/src/librustc_codegen_ssa/traits/builder.rs
+++ b/src/librustc_codegen_ssa/traits/builder.rs
@@ -1,5 +1,6 @@
 use super::abi::AbiBuilderMethods;
 use super::asm::AsmBuilderMethods;
+use super::coverageinfo::CoverageInfoBuilderMethods;
 use super::debuginfo::DebugInfoBuilderMethods;
 use super::intrinsic::IntrinsicCallMethods;
 use super::type_::ArgAbiMethods;
@@ -29,6 +30,7 @@ pub enum OverflowOp {
 
 pub trait BuilderMethods<'a, 'tcx>:
     HasCodegen<'tcx>
+    + CoverageInfoBuilderMethods<'tcx>
     + DebugInfoBuilderMethods
     + ArgAbiMethods<'tcx>
     + AbiBuilderMethods<'tcx>
diff --git a/src/librustc_codegen_ssa/traits/coverageinfo.rs b/src/librustc_codegen_ssa/traits/coverageinfo.rs
new file mode 100644
index 00000000000..d80f90fa4fa
--- /dev/null
+++ b/src/librustc_codegen_ssa/traits/coverageinfo.rs
@@ -0,0 +1,35 @@
+use super::BackendTypes;
+use crate::coverageinfo::CounterOp;
+use rustc_middle::ty::Instance;
+
+pub trait CoverageInfoMethods: BackendTypes {
+    fn coverageinfo_finalize(&self);
+}
+
+pub trait CoverageInfoBuilderMethods<'tcx>: BackendTypes {
+    fn add_counter_region(
+        &mut self,
+        instance: Instance<'tcx>,
+        index: u32,
+        start_byte_pos: u32,
+        end_byte_pos: u32,
+    );
+
+    fn add_counter_expression_region(
+        &mut self,
+        instance: Instance<'tcx>,
+        index: u32,
+        lhs: u32,
+        op: CounterOp,
+        rhs: u32,
+        start_byte_pos: u32,
+        end_byte_pos: u32,
+    );
+
+    fn add_unreachable_region(
+        &mut self,
+        instance: Instance<'tcx>,
+        start_byte_pos: u32,
+        end_byte_pos: u32,
+    );
+}
diff --git a/src/librustc_codegen_ssa/traits/intrinsic.rs b/src/librustc_codegen_ssa/traits/intrinsic.rs
index f6201949851..e713cc948c1 100644
--- a/src/librustc_codegen_ssa/traits/intrinsic.rs
+++ b/src/librustc_codegen_ssa/traits/intrinsic.rs
@@ -1,5 +1,6 @@
 use super::BackendTypes;
 use crate::mir::operand::OperandRef;
+use rustc_middle::mir::Operand;
 use rustc_middle::ty::{self, Ty};
 use rustc_span::Span;
 use rustc_target::abi::call::FnAbi;
@@ -18,6 +19,16 @@ pub trait IntrinsicCallMethods<'tcx>: BackendTypes {
         caller_instance: ty::Instance<'tcx>,
     );
 
+    /// Intrinsic-specific pre-codegen processing, if any is required. Some intrinsics are handled
+    /// at compile time and do not generate code. Returns true if codegen is required or false if
+    /// the intrinsic does not need code generation.
+    fn is_codegen_intrinsic(
+        &mut self,
+        intrinsic: &str,
+        args: &Vec<Operand<'tcx>>,
+        caller_instance: ty::Instance<'tcx>,
+    ) -> bool;
+
     fn abort(&mut self);
     fn assume(&mut self, val: Self::Value);
     fn expect(&mut self, cond: Self::Value, expected: bool) -> Self::Value;
diff --git a/src/librustc_codegen_ssa/traits/mod.rs b/src/librustc_codegen_ssa/traits/mod.rs
index 6b782731d53..0ac519dd0b1 100644
--- a/src/librustc_codegen_ssa/traits/mod.rs
+++ b/src/librustc_codegen_ssa/traits/mod.rs
@@ -19,6 +19,7 @@ mod asm;
 mod backend;
 mod builder;
 mod consts;
+mod coverageinfo;
 mod debuginfo;
 mod declare;
 mod intrinsic;
@@ -32,6 +33,7 @@ pub use self::asm::{AsmBuilderMethods, AsmMethods, InlineAsmOperandRef};
 pub use self::backend::{Backend, BackendTypes, CodegenBackend, ExtraBackendMethods};
 pub use self::builder::{BuilderMethods, OverflowOp};
 pub use self::consts::ConstMethods;
+pub use self::coverageinfo::{CoverageInfoBuilderMethods, CoverageInfoMethods};
 pub use self::debuginfo::{DebugInfoBuilderMethods, DebugInfoMethods};
 pub use self::declare::{DeclareMethods, PreDefineMethods};
 pub use self::intrinsic::IntrinsicCallMethods;
@@ -56,6 +58,7 @@ pub trait CodegenMethods<'tcx>:
     + MiscMethods<'tcx>
     + ConstMethods<'tcx>
     + StaticMethods
+    + CoverageInfoMethods
     + DebugInfoMethods<'tcx>
     + DeclareMethods<'tcx>
     + AsmMethods
@@ -72,6 +75,7 @@ impl<'tcx, T> CodegenMethods<'tcx> for T where
         + MiscMethods<'tcx>
         + ConstMethods<'tcx>
         + StaticMethods
+        + CoverageInfoMethods
         + DebugInfoMethods<'tcx>
         + DeclareMethods<'tcx>
         + AsmMethods