Responded to all feedback as of 2020-10-30

1 files changed, 151 insertions, 146 deletions

diff --git a/compiler/rustc_mir/src/transform/coverage/counters.rs b/compiler/rustc_mir/src/transform/coverage/counters.rs
index 7454ec2f438..d6c2f7f7aaf 100644
--- a/compiler/rustc_mir/src/transform/coverage/counters.rs
+++ b/compiler/rustc_mir/src/transform/coverage/counters.rs
@@ -12,16 +12,6 @@ use rustc_data_structures::graph::WithNumNodes;
 use rustc_index::bit_set::BitSet;
 use rustc_middle::mir::coverage::*;
 
-// When evaluating an expression operand to determine if it references a `Counter` or an
-// `Expression`, the range of counter or expression IDs must be known in order to answer the
-// question: "Does this ID fall inside the range of counters," for example. If "yes," the ID refers
-// to a counter, otherwise the ID refers to an expression.
-//
-// But in situations where the range is not currently known, the only fallback is to assume a
-// specific range limit. `MAX_COUNTER_GUARD` enforces a limit on the number of counters, and
-// therefore a limit on the range of counter IDs.
-pub(crate) const MAX_COUNTER_GUARD: u32 = (u32::MAX / 2) + 1;
-
 /// Manages the counter and expression indexes/IDs to generate `CoverageKind` components for MIR
 /// `Coverage` statements.
 pub(crate) struct CoverageCounters {
@@ -105,7 +95,6 @@ impl CoverageCounters {
     /// Counter IDs start from one and go up.
     fn next_counter(&mut self) -> CounterValueReference {
         assert!(self.next_counter_id < u32::MAX - self.num_expressions);
-        assert!(self.next_counter_id <= MAX_COUNTER_GUARD);
         let next = self.next_counter_id;
         self.next_counter_id += 1;
         CounterValueReference::from(next)
@@ -131,6 +120,7 @@ struct BcbCounters<'a> {
     basic_coverage_blocks: &'a mut CoverageGraph,
 }
 
+// FIXME(richkadel): Add unit tests for `BcbCounters` functions/algorithms.
 impl<'a> BcbCounters<'a> {
     fn new(
         coverage_counters: &'a mut CoverageCounters,
@@ -139,7 +129,7 @@ impl<'a> BcbCounters<'a> {
         Self { coverage_counters, basic_coverage_blocks }
     }
 
-    /// If two `CoverageGraph` branch from another `BasicCoverageBlock`, one of the branches
+    /// If two `BasicCoverageBlock`s 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
@@ -162,10 +152,16 @@ impl<'a> BcbCounters<'a> {
             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.
-
+        // Walk the `CoverageGraph`. For each `BasicCoverageBlock` node with an associated
+        // `CoverageSpan`, add a counter. If the `BasicCoverageBlock` branches, add a counter or
+        // expression to each branch `BasicCoverageBlock` (if the branch BCB has only one incoming
+        // edge) or edge from the branching BCB to the branch BCB (if the branch BCB has multiple
+        // incoming edges).
+        //
+        // The `TraverseCoverageGraphWithLoops` traversal ensures that, when a loop is encountered,
+        // all `BasicCoverageBlock` nodes in the loop are visited before visiting any node outside
+        // the loop. The `traversal` state includes a `context_stack`, providing a way to know if
+        // the current BCB is in one or more nested loops or not.
         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) {
@@ -220,11 +216,20 @@ impl<'a> BcbCounters<'a> {
                 .join("\n  "),
         );
 
+        // Use the `traversal` state to decide if a subset of the branches exit a loop, making it
+        // likely that branch is executed less than branches that do not exit the same loop. In this
+        // case, any branch that does not exit the loop (and has not already been assigned a
+        // counter) should be counted by expression, if possible. (If a preferred expression branch
+        // is not selected based on the loop context, select any branch without an existing
+        // counter.)
         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.
+
+        // 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 {
+            // Skip the selected `expression_branch`, if any. It's expression will be assigned after
+            // all others.
             if branch != expression_branch {
                 let branch_counter_operand = if branch.is_only_path_to_target() {
                     debug!(
@@ -263,6 +268,9 @@ impl<'a> BcbCounters<'a> {
                 }
             }
         }
+
+        // Assign the final expression to the `expression_branch` by subtracting the total of all
+        // other branches from the counter of the branching BCB.
         let sumup_counter_operand =
             some_sumup_counter_operand.expect("sumup_counter_operand should have a value");
         debug!(
@@ -301,99 +309,99 @@ impl<'a> BcbCounters<'a> {
         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() {
+        // If the BCB already has a counter, return it.
+        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),
+            );
+            return Ok(counter_kind.as_operand_id());
+        }
+
+        // A BCB with only one incoming edge gets a simple `Counter` (via `make_counter()`).
+        // Also, a BCB that loops back to itself gets a simple `Counter`. This may indicate the
+        // program results in a tight infinite loop, but it should still compile.
+        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!(
-                    "{}{:?} already has a counter: {}",
+                    "{}{:?} gets a new counter: {}",
                     NESTED_INDENT.repeat(debug_indent_level),
                     bcb,
-                    self.format_counter(counter_kind),
+                    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)?
-                }
+                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),
+                );
             }
-        })
+            return self.basic_coverage_blocks[bcb].set_counter(counter_kind);
+        }
+
+        // A BCB with multiple incoming edges can compute its count by `Expression`, summing up the
+        // counters and/or expressions of its incoming edges. This will recursively get or create
+        // counters for those incoming edges first, then call `make_expression()` to sum them up,
+        // with additional intermediate expressions as needed.
+        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(
@@ -417,46 +425,44 @@ impl<'a> BcbCounters<'a> {
         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,
-                )?
-            }
-        })
+        // If the source BCB has only one successor (assumed to be the given target), an edge
+        // counter is unnecessary. Just get or make a counter for the source BCB.
+        let successors = self.bcb_successors(from_bcb).iter();
+        if successors.len() == 1 {
+            return self.recursive_get_or_make_counter_operand(
+                from_bcb,
+                collect_intermediate_expressions,
+                debug_indent_level + 1,
+            );
+        }
+
+        // If the edge already has a counter, return it.
+        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)
+            );
+            return Ok(counter_kind.as_operand_id());
+        }
+
+        // Make a new counter to count this edge.
+        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)
     }
 
-    /// Select a branch for the expression, either the recommended `reloop_branch`, or
-    /// if none was found, select any branch.
+    /// 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,
@@ -493,9 +499,8 @@ impl<'a> BcbCounters<'a> {
         }
     }
 
-    /// 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.
+    /// 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