diff options
Diffstat (limited to 'compiler/rustc_mir/src/transform/coverage/counters.rs')
| -rw-r--r-- | compiler/rustc_mir/src/transform/coverage/counters.rs | 297 |
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 |