diff options
| author | Camille GILLOT <gillot.camille@gmail.com> | 2021-01-01 01:53:25 +0100 |
|---|---|---|
| committer | Camille GILLOT <gillot.camille@gmail.com> | 2021-09-07 00:43:14 +0200 |
| commit | bba4be681d664a50ab307ec732f957c02255e067 (patch) | |
| tree | d56899ff2ba1bcf004901eac1e155b2656a5e4fd /compiler/rustc_mir/src/transform/coverage/counters.rs | |
| parent | 31a61ccc38201a13c2549b20772daf15ce0e0309 (diff) | |
| download | rust-bba4be681d664a50ab307ec732f957c02255e067.tar.gz rust-bba4be681d664a50ab307ec732f957c02255e067.zip | |
Move rustc_mir::transform to rustc_mir_transform.
Diffstat (limited to 'compiler/rustc_mir/src/transform/coverage/counters.rs')
| -rw-r--r-- | compiler/rustc_mir/src/transform/coverage/counters.rs | 614 |
1 files changed, 0 insertions, 614 deletions
diff --git a/compiler/rustc_mir/src/transform/coverage/counters.rs b/compiler/rustc_mir/src/transform/coverage/counters.rs deleted file mode 100644 index 6726b669ff2..00000000000 --- a/compiler/rustc_mir/src/transform/coverage/counters.rs +++ /dev/null @@ -1,614 +0,0 @@ -use super::Error; - -use super::debug; -use super::graph; -use super::spans; - -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 -/// `Coverage` statements. -pub(super) struct CoverageCounters { - function_source_hash: u64, - next_counter_id: u32, - num_expressions: u32, - pub debug_counters: DebugCounters, -} - -impl CoverageCounters { - pub fn new(function_source_hash: u64) -> Self { - Self { - function_source_hash, - next_counter_id: CounterValueReference::START.as_u32(), - num_expressions: 0, - debug_counters: DebugCounters::new(), - } - } - - /// Activate the `DebugCounters` data structures, to provide additional debug formatting - /// features when formatting `CoverageKind` (counter) values. - pub fn enable_debug(&mut self) { - self.debug_counters.enable(); - } - - /// Makes `CoverageKind` `Counter`s and `Expressions` for the `BasicCoverageBlock`s 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>, - { - let counter = CoverageKind::Counter { - function_source_hash: self.function_source_hash, - id: self.next_counter(), - }; - if self.debug_counters.is_enabled() { - self.debug_counters.add_counter(&counter, (debug_block_label_fn)()); - } - counter - } - - fn make_expression<F>( - &mut self, - lhs: ExpressionOperandId, - op: Op, - rhs: ExpressionOperandId, - debug_block_label_fn: F, - ) -> CoverageKind - where - F: Fn() -> Option<String>, - { - let id = self.next_expression(); - let expression = CoverageKind::Expression { id, lhs, op, rhs }; - if self.debug_counters.is_enabled() { - self.debug_counters.add_counter(&expression, (debug_block_label_fn)()); - } - 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); - let next = self.next_counter_id; - self.next_counter_id += 1; - CounterValueReference::from(next) - } - - /// Expression IDs start from u32::MAX and go down because an Expression can reference - /// (add or subtract counts) of both Counter regions and Expression regions. The counter - /// expression operand IDs must be unique across both types. - fn next_expression(&mut self) -> InjectedExpressionId { - assert!(self.next_counter_id < u32::MAX - self.num_expressions); - let next = u32::MAX - self.num_expressions; - self.num_expressions += 1; - 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 `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 - /// 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: &[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); - } - - // 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) { - 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 "), - ); - - // 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. - 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!( - " {:?} 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); - } - } - } - - // 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!( - "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> { - // 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!( - "{}{:?} 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), - ); - } - 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( - &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> { - // 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. - fn choose_preferred_expression_branch( - &self, - traversal: &TraverseCoverageGraphWithLoops, - branches: &[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: &[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) - } -} |
