Injecting expressions in place of counters where helpful

Implementing the Graph traits for the BasicCoverageBlock
graph.

optimized replacement of counters with expressions plus new BCB graphviz

* Avoid adding coverage to unreachable blocks.
* Special case for Goto at the end of the body. Make it non-reportable.

Improved debugging and formatting options (from env)

Don't automatically add counters to BCBs without CoverageSpans. They may
still get counters but only if there are dependencies from
other BCBs that have spans, I think.

Make CodeRegions optional for Counters too. It is
possible to inject counters (`llvm.instrprof.increment` intrinsic calls
without corresponding code regions in the coverage map. An expression
can still uses these counter values.

Refactored instrument_coverage.rs -> instrument_coverage/mod.rs, and
then broke up the mod into multiple files.

Compiling with coverage, with the expression optimization, works on
the json5format crate and its dependencies.

Refactored debug features from mod.rs to debug.rs

1 files changed, 521 insertions, 3 deletions

diff --git a/compiler/rustc_mir/src/transform/coverage/counters.rs b/compiler/rustc_mir/src/transform/coverage/counters.rs
index c31f401780e..a3ae3021524 100644
--- a/compiler/rustc_mir/src/transform/coverage/counters.rs
+++ b/compiler/rustc_mir/src/transform/coverage/counters.rs
@@ -1,7 +1,15 @@
+use super::Error;
+
 use super::debug;
+use super::graph;
+use super::spans;
 
-use debug::DebugCounters;
+use debug::{DebugCounters, NESTED_INDENT};
+use graph::{BasicCoverageBlock, BcbBranch, CoverageGraph, TraverseCoverageGraphWithLoops};
+use spans::CoverageSpan;
 
+use rustc_data_structures::graph::WithNumNodes;
+use rustc_index::bit_set::BitSet;
 use rustc_middle::mir::coverage::*;
 
 /// Manages the counter and expression indexes/IDs to generate `CoverageKind` components for MIR
@@ -29,7 +37,19 @@ impl CoverageCounters {
         self.debug_counters.enable();
     }
 
-    pub fn make_counter<F>(&mut self, debug_block_label_fn: F) -> CoverageKind
+    /// Makes `CoverageKind` `Counter`s and `Expressions` for the `BasicCoverageBlocks` directly or
+    /// indirectly associated with `CoverageSpans`, and returns additional `Expression`s
+    /// representing intermediate values.
+    pub fn make_bcb_counters(
+        &mut self,
+        basic_coverage_blocks: &mut CoverageGraph,
+        coverage_spans: &Vec<CoverageSpan>,
+    ) -> Result<Vec<CoverageKind>, Error> {
+        let mut bcb_counters = BcbCounters::new(self, basic_coverage_blocks);
+        bcb_counters.make_bcb_counters(coverage_spans)
+    }
+
+    fn make_counter<F>(&mut self, debug_block_label_fn: F) -> CoverageKind
     where
         F: Fn() -> Option<String>,
     {
@@ -43,7 +63,7 @@ impl CoverageCounters {
         counter
     }
 
-    pub fn make_expression<F>(
+    fn make_expression<F>(
         &mut self,
         lhs: ExpressionOperandId,
         op: Op,
@@ -61,6 +81,17 @@ impl CoverageCounters {
         expression
     }
 
+    pub fn make_identity_counter(&mut self, counter_operand: ExpressionOperandId) -> CoverageKind {
+        let some_debug_block_label = if self.debug_counters.is_enabled() {
+            self.debug_counters.some_block_label(counter_operand).cloned()
+        } else {
+            None
+        };
+        self.make_expression(counter_operand, Op::Add, ExpressionOperandId::ZERO, || {
+            some_debug_block_label.clone()
+        })
+    }
+
     /// Counter IDs start from one and go up.
     fn next_counter(&mut self) -> CounterValueReference {
         assert!(self.next_counter_id < u32::MAX - self.num_expressions);
@@ -79,3 +110,490 @@ impl CoverageCounters {
         InjectedExpressionId::from(next)
     }
 }
+
+/// Traverse the `CoverageGraph` and add either a `Counter` or `Expression` to every BCB, to be
+/// injected with `CoverageSpan`s. `Expressions` have no runtime overhead, so if a viable expression
+/// (adding or subtracting two other counters or expressions) can compute the same result as an
+/// embedded counter, an `Expression` should be used.
+struct BcbCounters<'a> {
+    coverage_counters: &'a mut CoverageCounters,
+    basic_coverage_blocks: &'a mut CoverageGraph,
+}
+
+impl<'a> BcbCounters<'a> {
+    fn new(
+        coverage_counters: &'a mut CoverageCounters,
+        basic_coverage_blocks: &'a mut CoverageGraph,
+    ) -> Self {
+        Self { coverage_counters, basic_coverage_blocks }
+    }
+
+    /// If two `CoverageGraph` branch from another `BasicCoverageBlock`, one of the branches
+    /// can be counted by `Expression` by subtracting the other branch from the branching
+    /// block. Otherwise, the `BasicCoverageBlock` executed the least should have the `Counter`.
+    /// One way to predict which branch executes the least is by considering loops. A loop is exited
+    /// at a branch, so the branch that jumps to a `BasicCoverageBlock` outside the loop is almost
+    /// always executed less than the branch that does not exit the loop.
+    ///
+    /// Returns any non-code-span expressions created to represent intermediate values (such as to
+    /// add two counters so the result can be subtracted from another counter), or an Error with
+    /// message for subsequent debugging.
+    fn make_bcb_counters(
+        &mut self,
+        coverage_spans: &Vec<CoverageSpan>,
+    ) -> Result<Vec<CoverageKind>, Error> {
+        debug!("make_bcb_counters(): adding a counter or expression to each BasicCoverageBlock");
+        let num_bcbs = self.basic_coverage_blocks.num_nodes();
+        let mut collect_intermediate_expressions = Vec::with_capacity(num_bcbs);
+
+        let mut bcbs_with_coverage = BitSet::new_empty(num_bcbs);
+        for covspan in coverage_spans {
+            bcbs_with_coverage.insert(covspan.bcb);
+        }
+
+        // FIXME(richkadel): Add more comments to explain the logic here and in the rest of this
+        // function, and refactor this function to break it up into smaller functions that are
+        // easier to understand.
+
+        let mut traversal = TraverseCoverageGraphWithLoops::new(&self.basic_coverage_blocks);
+        while let Some(bcb) = traversal.next(self.basic_coverage_blocks) {
+            if bcbs_with_coverage.contains(bcb) {
+                debug!("{:?} has at least one `CoverageSpan`. Get or make its counter", bcb);
+                let branching_counter_operand =
+                    self.get_or_make_counter_operand(bcb, &mut collect_intermediate_expressions)?;
+
+                if self.bcb_needs_branch_counters(bcb) {
+                    self.make_branch_counters(
+                        &mut traversal,
+                        bcb,
+                        branching_counter_operand,
+                        &mut collect_intermediate_expressions,
+                    )?;
+                }
+            } else {
+                debug!(
+                    "{:?} does not have any `CoverageSpan`s. A counter will only be added if \
+                    and when a covered BCB has an expression dependency.",
+                    bcb,
+                );
+            }
+        }
+
+        if traversal.is_complete() {
+            Ok(collect_intermediate_expressions)
+        } else {
+            Error::from_string(format!(
+                "`TraverseCoverageGraphWithLoops` missed some `BasicCoverageBlock`s: {:?}",
+                traversal.unvisited(),
+            ))
+        }
+    }
+
+    fn make_branch_counters(
+        &mut self,
+        traversal: &mut TraverseCoverageGraphWithLoops,
+        branching_bcb: BasicCoverageBlock,
+        branching_counter_operand: ExpressionOperandId,
+        collect_intermediate_expressions: &mut Vec<CoverageKind>,
+    ) -> Result<(), Error> {
+        let branches = self.bcb_branches(branching_bcb);
+        debug!(
+            "{:?} has some branch(es) without counters:\n  {}",
+            branching_bcb,
+            branches
+                .iter()
+                .map(|branch| {
+                    format!("{:?}: {:?}", branch, branch.counter(&self.basic_coverage_blocks))
+                })
+                .collect::<Vec<_>>()
+                .join("\n  "),
+        );
+
+        let expression_branch = self.choose_preferred_expression_branch(traversal, &branches);
+        // Assign a Counter or Expression to each branch, plus additional
+        // `Expression`s, as needed, to sum up intermediate results.
+        let mut some_sumup_counter_operand = None;
+        for branch in branches {
+            if branch != expression_branch {
+                let branch_counter_operand = if branch.is_only_path_to_target() {
+                    debug!(
+                        "  {:?} has only one incoming edge (from {:?}), so adding a \
+                        counter",
+                        branch, branching_bcb
+                    );
+                    self.get_or_make_counter_operand(
+                        branch.target_bcb,
+                        collect_intermediate_expressions,
+                    )?
+                } else {
+                    debug!("  {:?} has multiple incoming edges, so adding an edge counter", branch);
+                    self.get_or_make_edge_counter_operand(
+                        branching_bcb,
+                        branch.target_bcb,
+                        collect_intermediate_expressions,
+                    )?
+                };
+                if let Some(sumup_counter_operand) =
+                    some_sumup_counter_operand.replace(branch_counter_operand)
+                {
+                    let intermediate_expression = self.coverage_counters.make_expression(
+                        branch_counter_operand,
+                        Op::Add,
+                        sumup_counter_operand,
+                        || None,
+                    );
+                    debug!(
+                        "  [new intermediate expression: {}]",
+                        self.format_counter(&intermediate_expression)
+                    );
+                    let intermediate_expression_operand = intermediate_expression.as_operand_id();
+                    collect_intermediate_expressions.push(intermediate_expression);
+                    some_sumup_counter_operand.replace(intermediate_expression_operand);
+                }
+            }
+        }
+        let sumup_counter_operand =
+            some_sumup_counter_operand.expect("sumup_counter_operand should have a value");
+        debug!(
+            "Making an expression for the selected expression_branch: {:?} \
+            (expression_branch predecessors: {:?})",
+            expression_branch,
+            self.bcb_predecessors(expression_branch.target_bcb),
+        );
+        let expression = self.coverage_counters.make_expression(
+            branching_counter_operand,
+            Op::Subtract,
+            sumup_counter_operand,
+            || Some(format!("{:?}", expression_branch)),
+        );
+        debug!("{:?} gets an expression: {}", expression_branch, self.format_counter(&expression));
+        let bcb = expression_branch.target_bcb;
+        if expression_branch.is_only_path_to_target() {
+            self.basic_coverage_blocks[bcb].set_counter(expression)?;
+        } else {
+            self.basic_coverage_blocks[bcb].set_edge_counter_from(branching_bcb, expression)?;
+        }
+        Ok(())
+    }
+
+    fn get_or_make_counter_operand(
+        &mut self,
+        bcb: BasicCoverageBlock,
+        collect_intermediate_expressions: &mut Vec<CoverageKind>,
+    ) -> Result<ExpressionOperandId, Error> {
+        self.recursive_get_or_make_counter_operand(bcb, collect_intermediate_expressions, 1)
+    }
+
+    fn recursive_get_or_make_counter_operand(
+        &mut self,
+        bcb: BasicCoverageBlock,
+        collect_intermediate_expressions: &mut Vec<CoverageKind>,
+        debug_indent_level: usize,
+    ) -> Result<ExpressionOperandId, Error> {
+        Ok({
+            if let Some(counter_kind) = self.basic_coverage_blocks[bcb].counter() {
+                debug!(
+                    "{}{:?} already has a counter: {}",
+                    NESTED_INDENT.repeat(debug_indent_level),
+                    bcb,
+                    self.format_counter(counter_kind),
+                );
+                counter_kind.as_operand_id()
+            } else {
+                let one_path_to_target = self.bcb_has_one_path_to_target(bcb);
+                if one_path_to_target || self.bcb_predecessors(bcb).contains(&bcb) {
+                    let counter_kind =
+                        self.coverage_counters.make_counter(|| Some(format!("{:?}", bcb)));
+                    if one_path_to_target {
+                        debug!(
+                            "{}{:?} gets a new counter: {}",
+                            NESTED_INDENT.repeat(debug_indent_level),
+                            bcb,
+                            self.format_counter(&counter_kind),
+                        );
+                    } else {
+                        debug!(
+                            "{}{:?} has itself as its own predecessor. It can't be part of its own \
+                            Expression sum, so it will get its own new counter: {}. (Note, the \
+                            compiled code will generate an infinite loop.)",
+                            NESTED_INDENT.repeat(debug_indent_level),
+                            bcb,
+                            self.format_counter(&counter_kind),
+                        );
+                    }
+                    self.basic_coverage_blocks[bcb].set_counter(counter_kind)?
+                } else {
+                    let mut predecessors = self.bcb_predecessors(bcb).clone().into_iter();
+                    debug!(
+                        "{}{:?} has multiple incoming edges and will get an expression that sums \
+                        them up...",
+                        NESTED_INDENT.repeat(debug_indent_level),
+                        bcb,
+                    );
+                    let first_edge_counter_operand = self
+                        .recursive_get_or_make_edge_counter_operand(
+                            predecessors.next().unwrap(),
+                            bcb,
+                            collect_intermediate_expressions,
+                            debug_indent_level + 1,
+                        )?;
+                    let mut some_sumup_edge_counter_operand = None;
+                    for predecessor in predecessors {
+                        let edge_counter_operand = self
+                            .recursive_get_or_make_edge_counter_operand(
+                                predecessor,
+                                bcb,
+                                collect_intermediate_expressions,
+                                debug_indent_level + 1,
+                            )?;
+                        if let Some(sumup_edge_counter_operand) =
+                            some_sumup_edge_counter_operand.replace(edge_counter_operand)
+                        {
+                            let intermediate_expression = self.coverage_counters.make_expression(
+                                sumup_edge_counter_operand,
+                                Op::Add,
+                                edge_counter_operand,
+                                || None,
+                            );
+                            debug!(
+                                "{}new intermediate expression: {}",
+                                NESTED_INDENT.repeat(debug_indent_level),
+                                self.format_counter(&intermediate_expression)
+                            );
+                            let intermediate_expression_operand =
+                                intermediate_expression.as_operand_id();
+                            collect_intermediate_expressions.push(intermediate_expression);
+                            some_sumup_edge_counter_operand
+                                .replace(intermediate_expression_operand);
+                        }
+                    }
+                    let counter_kind = self.coverage_counters.make_expression(
+                        first_edge_counter_operand,
+                        Op::Add,
+                        some_sumup_edge_counter_operand.unwrap(),
+                        || Some(format!("{:?}", bcb)),
+                    );
+                    debug!(
+                        "{}{:?} gets a new counter (sum of predecessor counters): {}",
+                        NESTED_INDENT.repeat(debug_indent_level),
+                        bcb,
+                        self.format_counter(&counter_kind)
+                    );
+                    self.basic_coverage_blocks[bcb].set_counter(counter_kind)?
+                }
+            }
+        })
+    }
+
+    fn get_or_make_edge_counter_operand(
+        &mut self,
+        from_bcb: BasicCoverageBlock,
+        to_bcb: BasicCoverageBlock,
+        collect_intermediate_expressions: &mut Vec<CoverageKind>,
+    ) -> Result<ExpressionOperandId, Error> {
+        self.recursive_get_or_make_edge_counter_operand(
+            from_bcb,
+            to_bcb,
+            collect_intermediate_expressions,
+            1,
+        )
+    }
+
+    fn recursive_get_or_make_edge_counter_operand(
+        &mut self,
+        from_bcb: BasicCoverageBlock,
+        to_bcb: BasicCoverageBlock,
+        collect_intermediate_expressions: &mut Vec<CoverageKind>,
+        debug_indent_level: usize,
+    ) -> Result<ExpressionOperandId, Error> {
+        Ok({
+            let successors = self.bcb_successors(from_bcb).iter();
+            if successors.len() > 1 {
+                if let Some(counter_kind) =
+                    self.basic_coverage_blocks[to_bcb].edge_counter_from(from_bcb)
+                {
+                    debug!(
+                        "{}Edge {:?}->{:?} already has a counter: {}",
+                        NESTED_INDENT.repeat(debug_indent_level),
+                        from_bcb,
+                        to_bcb,
+                        self.format_counter(counter_kind)
+                    );
+                    counter_kind.as_operand_id()
+                } else {
+                    let counter_kind = self
+                        .coverage_counters
+                        .make_counter(|| Some(format!("{:?}->{:?}", from_bcb, to_bcb)));
+                    debug!(
+                        "{}Edge {:?}->{:?} gets a new counter: {}",
+                        NESTED_INDENT.repeat(debug_indent_level),
+                        from_bcb,
+                        to_bcb,
+                        self.format_counter(&counter_kind)
+                    );
+                    self.basic_coverage_blocks[to_bcb]
+                        .set_edge_counter_from(from_bcb, counter_kind)?
+                }
+            } else {
+                self.recursive_get_or_make_counter_operand(
+                    from_bcb,
+                    collect_intermediate_expressions,
+                    debug_indent_level + 1,
+                )?
+            }
+        })
+    }
+
+    /// Select a branch for the expression, either the recommended `reloop_branch`, or
+    /// if none was found, select any branch.
+    fn choose_preferred_expression_branch(
+        &self,
+        traversal: &TraverseCoverageGraphWithLoops,
+        branches: &Vec<BcbBranch>,
+    ) -> BcbBranch {
+        let branch_needs_a_counter =
+            |branch: &BcbBranch| branch.counter(&self.basic_coverage_blocks).is_none();
+
+        let some_reloop_branch = self.find_some_reloop_branch(traversal, &branches);
+        if let Some(reloop_branch_without_counter) =
+            some_reloop_branch.filter(branch_needs_a_counter)
+        {
+            debug!(
+                "Selecting reloop_branch={:?} that still needs a counter, to get the \
+                `Expression`",
+                reloop_branch_without_counter
+            );
+            reloop_branch_without_counter
+        } else {
+            let &branch_without_counter = branches
+                .iter()
+                .find(|&&branch| branch.counter(&self.basic_coverage_blocks).is_none())
+                .expect(
+                    "needs_branch_counters was `true` so there should be at least one \
+                    branch",
+                );
+            debug!(
+                "Selecting any branch={:?} that still needs a counter, to get the \
+                `Expression` because there was no `reloop_branch`, or it already had a \
+                counter",
+                branch_without_counter
+            );
+            branch_without_counter
+        }
+    }
+
+    /// At most one of the branches (or its edge, from the branching_bcb,
+    /// if the branch has multiple incoming edges) can have a counter computed by
+    /// expression.
+    ///
+    /// If at least one of the branches leads outside of a loop (`found_loop_exit` is
+    /// true), and at least one other branch does not exit the loop (the first of which
+    /// is captured in `some_reloop_branch`), it's likely any reloop branch will be
+    /// executed far more often than loop exit branch, making the reloop branch a better
+    /// candidate for an expression.
+    fn find_some_reloop_branch(
+        &self,
+        traversal: &TraverseCoverageGraphWithLoops,
+        branches: &Vec<BcbBranch>,
+    ) -> Option<BcbBranch> {
+        let branch_needs_a_counter =
+            |branch: &BcbBranch| branch.counter(&self.basic_coverage_blocks).is_none();
+
+        let mut some_reloop_branch: Option<BcbBranch> = None;
+        for context in traversal.context_stack.iter().rev() {
+            if let Some((backedge_from_bcbs, _)) = &context.loop_backedges {
+                let mut found_loop_exit = false;
+                for &branch in branches.iter() {
+                    if backedge_from_bcbs.iter().any(|&backedge_from_bcb| {
+                        self.bcb_is_dominated_by(backedge_from_bcb, branch.target_bcb)
+                    }) {
+                        if let Some(reloop_branch) = some_reloop_branch {
+                            if reloop_branch.counter(&self.basic_coverage_blocks).is_none() {
+                                // we already found a candidate reloop_branch that still
+                                // needs a counter
+                                continue;
+                            }
+                        }
+                        // The path from branch leads back to the top of the loop. Set this
+                        // branch as the `reloop_branch`. If this branch already has a
+                        // counter, and we find another reloop branch that doesn't have a
+                        // counter yet, that branch will be selected as the `reloop_branch`
+                        // instead.
+                        some_reloop_branch = Some(branch);
+                    } else {
+                        // The path from branch leads outside this loop
+                        found_loop_exit = true;
+                    }
+                    if found_loop_exit
+                        && some_reloop_branch.filter(branch_needs_a_counter).is_some()
+                    {
+                        // Found both a branch that exits the loop and a branch that returns
+                        // to the top of the loop (`reloop_branch`), and the `reloop_branch`
+                        // doesn't already have a counter.
+                        break;
+                    }
+                }
+                if !found_loop_exit {
+                    debug!(
+                        "No branches exit the loop, so any branch without an existing \
+                        counter can have the `Expression`."
+                    );
+                    break;
+                }
+                if some_reloop_branch.is_some() {
+                    debug!(
+                        "Found a branch that exits the loop and a branch the loops back to \
+                        the top of the loop (`reloop_branch`). The `reloop_branch` will \
+                        get the `Expression`, as long as it still needs a counter."
+                    );
+                    break;
+                }
+                // else all branches exited this loop context, so run the same checks with
+                // the outer loop(s)
+            }
+        }
+        some_reloop_branch
+    }
+
+    #[inline]
+    fn bcb_predecessors(&self, bcb: BasicCoverageBlock) -> &Vec<BasicCoverageBlock> {
+        &self.basic_coverage_blocks.predecessors[bcb]
+    }
+
+    #[inline]
+    fn bcb_successors(&self, bcb: BasicCoverageBlock) -> &Vec<BasicCoverageBlock> {
+        &self.basic_coverage_blocks.successors[bcb]
+    }
+
+    #[inline]
+    fn bcb_branches(&self, from_bcb: BasicCoverageBlock) -> Vec<BcbBranch> {
+        self.bcb_successors(from_bcb)
+            .iter()
+            .map(|&to_bcb| BcbBranch::from_to(from_bcb, to_bcb, &self.basic_coverage_blocks))
+            .collect::<Vec<_>>()
+    }
+
+    fn bcb_needs_branch_counters(&self, bcb: BasicCoverageBlock) -> bool {
+        let branch_needs_a_counter =
+            |branch: &BcbBranch| branch.counter(&self.basic_coverage_blocks).is_none();
+        let branches = self.bcb_branches(bcb);
+        branches.len() > 1 && branches.iter().any(branch_needs_a_counter)
+    }
+
+    /// Returns true if the BasicCoverageBlock has zero or one incoming edge. (If zero, it should be
+    /// the entry point for the function.)
+    #[inline]
+    fn bcb_has_one_path_to_target(&self, bcb: BasicCoverageBlock) -> bool {
+        self.bcb_predecessors(bcb).len() <= 1
+    }
+
+    #[inline]
+    fn bcb_is_dominated_by(&self, node: BasicCoverageBlock, dom: BasicCoverageBlock) -> bool {
+        self.basic_coverage_blocks.is_dominated_by(node, dom)
+    }
+
+    #[inline]
+    fn format_counter(&self, counter_kind: &CoverageKind) -> String {
+        self.coverage_counters.debug_counters.format_counter(counter_kind)
+    }
+}