diff options
Diffstat (limited to 'compiler/rustc_mir_transform')
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/counters.rs | 309 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/graph.rs | 66 |
2 files changed, 170 insertions, 205 deletions
diff --git a/compiler/rustc_mir_transform/src/coverage/counters.rs b/compiler/rustc_mir_transform/src/coverage/counters.rs index 1e11d8d09b6..604589e5b96 100644 --- a/compiler/rustc_mir_transform/src/coverage/counters.rs +++ b/compiler/rustc_mir_transform/src/coverage/counters.rs @@ -1,18 +1,16 @@ -use super::graph; - -use graph::{BasicCoverageBlock, BcbBranch, CoverageGraph, TraverseCoverageGraphWithLoops}; - use rustc_data_structures::fx::FxHashMap; use rustc_data_structures::graph::WithNumNodes; use rustc_index::bit_set::BitSet; use rustc_index::IndexVec; use rustc_middle::mir::coverage::*; +use super::graph::{BasicCoverageBlock, CoverageGraph, TraverseCoverageGraphWithLoops}; + use std::fmt::{self, Debug}; /// The coverage counter or counter expression associated with a particular /// BCB node or BCB edge. -#[derive(Clone)] +#[derive(Clone, Copy)] pub(super) enum BcbCounter { Counter { id: CounterId }, Expression { id: ExpressionId }, @@ -88,11 +86,20 @@ impl CoverageCounters { BcbCounter::Counter { id } } - fn make_expression(&mut self, lhs: CovTerm, op: Op, rhs: CovTerm) -> BcbCounter { - let id = self.expressions.push(Expression { lhs, op, rhs }); + fn make_expression(&mut self, lhs: BcbCounter, op: Op, rhs: BcbCounter) -> BcbCounter { + let expression = Expression { lhs: lhs.as_term(), op, rhs: rhs.as_term() }; + let id = self.expressions.push(expression); BcbCounter::Expression { id } } + /// Variant of `make_expression` that makes `lhs` optional and assumes [`Op::Add`]. + /// + /// This is useful when using [`Iterator::fold`] to build an arbitrary-length sum. + fn make_sum_expression(&mut self, lhs: Option<BcbCounter>, rhs: BcbCounter) -> BcbCounter { + let Some(lhs) = lhs else { return rhs }; + self.make_expression(lhs, Op::Add, rhs) + } + /// Counter IDs start from one and go up. fn next_counter(&mut self) -> CounterId { let next = self.next_counter_id; @@ -109,7 +116,7 @@ impl CoverageCounters { self.expressions.len() } - fn set_bcb_counter(&mut self, bcb: BasicCoverageBlock, counter_kind: BcbCounter) -> CovTerm { + fn set_bcb_counter(&mut self, bcb: BasicCoverageBlock, counter_kind: BcbCounter) -> BcbCounter { assert!( // If the BCB has an edge counter (to be injected into a new `BasicBlock`), it can also // have an expression (to be injected into an existing `BasicBlock` represented by this @@ -118,14 +125,13 @@ impl CoverageCounters { "attempt to add a `Counter` to a BCB target with existing incoming edge counters" ); - let term = counter_kind.as_term(); if let Some(replaced) = self.bcb_counters[bcb].replace(counter_kind) { bug!( "attempt to set a BasicCoverageBlock coverage counter more than once; \ {bcb:?} already had counter {replaced:?}", ); } else { - term + counter_kind } } @@ -134,7 +140,7 @@ impl CoverageCounters { from_bcb: BasicCoverageBlock, to_bcb: BasicCoverageBlock, counter_kind: BcbCounter, - ) -> CovTerm { + ) -> BcbCounter { // If the BCB has an edge counter (to be injected into a new `BasicBlock`), it can also // have an expression (to be injected into an existing `BasicBlock` represented by this // `BasicCoverageBlock`). @@ -148,19 +154,18 @@ impl CoverageCounters { } self.bcb_has_incoming_edge_counters.insert(to_bcb); - let term = counter_kind.as_term(); if let Some(replaced) = self.bcb_edge_counters.insert((from_bcb, to_bcb), counter_kind) { bug!( "attempt to set an edge counter more than once; from_bcb: \ {from_bcb:?} already had counter {replaced:?}", ); } else { - term + counter_kind } } - pub(super) fn bcb_counter(&self, bcb: BasicCoverageBlock) -> Option<&BcbCounter> { - self.bcb_counters[bcb].as_ref() + pub(super) fn bcb_counter(&self, bcb: BasicCoverageBlock) -> Option<BcbCounter> { + self.bcb_counters[bcb] } pub(super) fn bcb_node_counters( @@ -226,11 +231,7 @@ impl<'a> MakeBcbCounters<'a> { while let Some(bcb) = traversal.next() { if bcb_has_coverage_spans(bcb) { debug!("{:?} has at least one coverage span. Get or make its counter", bcb); - let branching_counter_operand = self.get_or_make_counter_operand(bcb); - - if self.bcb_needs_branch_counters(bcb) { - self.make_branch_counters(&traversal, bcb, branching_counter_operand); - } + self.make_node_and_branch_counters(&traversal, bcb); } else { debug!( "{:?} does not have any coverage spans. A counter will only be added if \ @@ -247,100 +248,93 @@ impl<'a> MakeBcbCounters<'a> { ); } - fn make_branch_counters( + fn make_node_and_branch_counters( &mut self, traversal: &TraverseCoverageGraphWithLoops<'_>, - branching_bcb: BasicCoverageBlock, - branching_counter_operand: CovTerm, + from_bcb: BasicCoverageBlock, ) { - let branches = self.bcb_branches(branching_bcb); + // First, ensure that this node has a counter of some kind. + // We might also use its term later to compute one of the branch counters. + let from_bcb_operand = self.get_or_make_counter_operand(from_bcb); + + let branch_target_bcbs = self.basic_coverage_blocks.successors[from_bcb].as_slice(); + + // If this node doesn't have multiple out-edges, or all of its out-edges + // already have counters, then we don't need to create edge counters. + let needs_branch_counters = branch_target_bcbs.len() > 1 + && branch_target_bcbs + .iter() + .any(|&to_bcb| self.branch_has_no_counter(from_bcb, to_bcb)); + if !needs_branch_counters { + return; + } + debug!( - "{:?} has some branch(es) without counters:\n {}", - branching_bcb, - branches + "{from_bcb:?} has some branch(es) without counters:\n {}", + branch_target_bcbs .iter() - .map(|branch| { format!("{:?}: {:?}", branch, self.branch_counter(branch)) }) + .map(|&to_bcb| { + format!("{from_bcb:?}->{to_bcb:?}: {:?}", self.branch_counter(from_bcb, to_bcb)) + }) .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) - } else { - debug!(" {:?} has multiple incoming edges, so adding an edge counter", branch); - self.get_or_make_edge_counter_operand(branching_bcb, branch.target_bcb) - }; - 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, - ); - debug!(" [new intermediate expression: {:?}]", intermediate_expression); - let intermediate_expression_operand = intermediate_expression.as_term(); - some_sumup_counter_operand.replace(intermediate_expression_operand); - } - } - } + // Of the branch edges that don't have counters yet, one can be given an expression + // (computed from the other edges) instead of a dedicated counter. + let expression_to_bcb = self.choose_preferred_expression_branch(traversal, from_bcb); - // 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"); + // For each branch arm other than the one that was chosen to get an expression, + // ensure that it has a counter (existing counter/expression or a new counter), + // and accumulate the corresponding terms into a single sum term. + let sum_of_all_other_branches: BcbCounter = { + let _span = debug_span!("sum_of_all_other_branches", ?expression_to_bcb).entered(); + branch_target_bcbs + .iter() + .copied() + // Skip the chosen branch, since we'll calculate it from the other branches. + .filter(|&to_bcb| to_bcb != expression_to_bcb) + .fold(None, |accum, to_bcb| { + let _span = debug_span!("to_bcb", ?accum, ?to_bcb).entered(); + let branch_counter = self.get_or_make_edge_counter_operand(from_bcb, to_bcb); + Some(self.coverage_counters.make_sum_expression(accum, branch_counter)) + }) + .expect("there must be at least one other branch") + }; + + // For the branch that was chosen to get an expression, create that expression + // by taking the count of the node we're branching from, and subtracting the + // sum of all the other branches. debug!( - "Making an expression for the selected expression_branch: {:?} \ - (expression_branch predecessors: {:?})", - expression_branch, - self.bcb_predecessors(expression_branch.target_bcb), + "Making an expression for the selected expression_branch: \ + {expression_to_bcb:?} (expression_branch predecessors: {:?})", + self.bcb_predecessors(expression_to_bcb), ); let expression = self.coverage_counters.make_expression( - branching_counter_operand, + from_bcb_operand, Op::Subtract, - sumup_counter_operand, + sum_of_all_other_branches, ); - debug!("{:?} gets an expression: {:?}", expression_branch, expression); - let bcb = expression_branch.target_bcb; - if expression_branch.is_only_path_to_target() { - self.coverage_counters.set_bcb_counter(bcb, expression); + debug!("{expression_to_bcb:?} gets an expression: {expression:?}"); + if self.basic_coverage_blocks.bcb_has_multiple_in_edges(expression_to_bcb) { + self.coverage_counters.set_bcb_edge_counter(from_bcb, expression_to_bcb, expression); } else { - self.coverage_counters.set_bcb_edge_counter(branching_bcb, bcb, expression); + self.coverage_counters.set_bcb_counter(expression_to_bcb, expression); } } #[instrument(level = "debug", skip(self))] - fn get_or_make_counter_operand(&mut self, bcb: BasicCoverageBlock) -> CovTerm { + fn get_or_make_counter_operand(&mut self, bcb: BasicCoverageBlock) -> BcbCounter { // If the BCB already has a counter, return it. - if let Some(counter_kind) = &self.coverage_counters.bcb_counters[bcb] { + if let Some(counter_kind) = self.coverage_counters.bcb_counters[bcb] { debug!("{bcb:?} already has a counter: {counter_kind:?}"); - return counter_kind.as_term(); + return counter_kind; } // 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); + let one_path_to_target = !self.basic_coverage_blocks.bcb_has_multiple_in_edges(bcb); if one_path_to_target || self.bcb_predecessors(bcb).contains(&bcb) { let counter_kind = self.coverage_counters.make_counter(); if one_path_to_target { @@ -355,40 +349,25 @@ impl<'a> MakeBcbCounters<'a> { return self.coverage_counters.set_bcb_counter(bcb, 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 _sumup_debug_span = debug_span!("(preparing sum-up expression)").entered(); - - let mut predecessors = self.bcb_predecessors(bcb).to_owned().into_iter(); - let first_edge_counter_operand = - self.get_or_make_edge_counter_operand(predecessors.next().unwrap(), bcb); - let mut some_sumup_edge_counter_operand = None; - for predecessor in predecessors { - let edge_counter_operand = self.get_or_make_edge_counter_operand(predecessor, bcb); - 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, - ); - debug!("new intermediate expression: {intermediate_expression:?}"); - let intermediate_expression_operand = intermediate_expression.as_term(); - 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(), - ); - drop(_sumup_debug_span); - - debug!("{bcb:?} gets a new counter (sum of predecessor counters): {counter_kind:?}"); - self.coverage_counters.set_bcb_counter(bcb, counter_kind) + // A BCB with multiple incoming edges can compute its count by ensuring that counters + // exist for each of those edges, and then adding them up to get a total count. + let sum_of_in_edges: BcbCounter = { + let _span = debug_span!("sum_of_in_edges", ?bcb).entered(); + // We avoid calling `self.bcb_predecessors` here so that we can + // call methods on `&mut self` inside the fold. + self.basic_coverage_blocks.predecessors[bcb] + .iter() + .copied() + .fold(None, |accum, from_bcb| { + let _span = debug_span!("from_bcb", ?accum, ?from_bcb).entered(); + let edge_counter = self.get_or_make_edge_counter_operand(from_bcb, bcb); + Some(self.coverage_counters.make_sum_expression(accum, edge_counter)) + }) + .expect("there must be at least one in-edge") + }; + + debug!("{bcb:?} gets a new counter (sum of predecessor counters): {sum_of_in_edges:?}"); + self.coverage_counters.set_bcb_counter(bcb, sum_of_in_edges) } #[instrument(level = "debug", skip(self))] @@ -396,20 +375,26 @@ impl<'a> MakeBcbCounters<'a> { &mut self, from_bcb: BasicCoverageBlock, to_bcb: BasicCoverageBlock, - ) -> CovTerm { + ) -> BcbCounter { + // If the target BCB has only one in-edge (i.e. this one), then create + // a node counter instead, since it will have the same value. + if !self.basic_coverage_blocks.bcb_has_multiple_in_edges(to_bcb) { + assert_eq!([from_bcb].as_slice(), self.basic_coverage_blocks.predecessors[to_bcb]); + return self.get_or_make_counter_operand(to_bcb); + } + // 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 { + if self.bcb_successors(from_bcb).len() == 1 { return self.get_or_make_counter_operand(from_bcb); } // If the edge already has a counter, return it. - if let Some(counter_kind) = + if let Some(&counter_kind) = self.coverage_counters.bcb_edge_counters.get(&(from_bcb, to_bcb)) { debug!("Edge {from_bcb:?}->{to_bcb:?} already has a counter: {counter_kind:?}"); - return counter_kind.as_term(); + return counter_kind; } // Make a new counter to count this edge. @@ -423,16 +408,19 @@ impl<'a> MakeBcbCounters<'a> { fn choose_preferred_expression_branch( &self, traversal: &TraverseCoverageGraphWithLoops<'_>, - branches: &[BcbBranch], - ) -> BcbBranch { - let good_reloop_branch = self.find_good_reloop_branch(traversal, branches); - if let Some(reloop_branch) = good_reloop_branch { - assert!(self.branch_has_no_counter(&reloop_branch)); - debug!("Selecting reloop branch {reloop_branch:?} to get an expression"); - reloop_branch + from_bcb: BasicCoverageBlock, + ) -> BasicCoverageBlock { + let good_reloop_branch = self.find_good_reloop_branch(traversal, from_bcb); + if let Some(reloop_target) = good_reloop_branch { + assert!(self.branch_has_no_counter(from_bcb, reloop_target)); + debug!("Selecting reloop target {reloop_target:?} to get an expression"); + reloop_target } else { - let &branch_without_counter = - branches.iter().find(|&branch| self.branch_has_no_counter(branch)).expect( + let &branch_without_counter = self + .bcb_successors(from_bcb) + .iter() + .find(|&&to_bcb| self.branch_has_no_counter(from_bcb, to_bcb)) + .expect( "needs_branch_counters was `true` so there should be at least one \ branch", ); @@ -453,26 +441,28 @@ impl<'a> MakeBcbCounters<'a> { fn find_good_reloop_branch( &self, traversal: &TraverseCoverageGraphWithLoops<'_>, - branches: &[BcbBranch], - ) -> Option<BcbBranch> { + from_bcb: BasicCoverageBlock, + ) -> Option<BasicCoverageBlock> { + let branch_target_bcbs = self.bcb_successors(from_bcb); + // Consider each loop on the current traversal context stack, top-down. for reloop_bcbs in traversal.reloop_bcbs_per_loop() { let mut all_branches_exit_this_loop = true; // Try to find a branch that doesn't exit this loop and doesn't // already have a counter. - for &branch in branches { + for &branch_target_bcb in branch_target_bcbs { // A branch is a reloop branch if it dominates any BCB that has // an edge back to the loop header. (Other branches are exits.) let is_reloop_branch = reloop_bcbs.iter().any(|&reloop_bcb| { - self.basic_coverage_blocks.dominates(branch.target_bcb, reloop_bcb) + self.basic_coverage_blocks.dominates(branch_target_bcb, reloop_bcb) }); if is_reloop_branch { all_branches_exit_this_loop = false; - if self.branch_has_no_counter(&branch) { + if self.branch_has_no_counter(from_bcb, branch_target_bcb) { // We found a good branch to be given an expression. - return Some(branch); + return Some(branch_target_bcb); } // Keep looking for another reloop branch without a counter. } else { @@ -505,36 +495,23 @@ impl<'a> MakeBcbCounters<'a> { } #[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| self.branch_has_no_counter(branch); - let branches = self.bcb_branches(bcb); - branches.len() > 1 && branches.iter().any(branch_needs_a_counter) - } - - fn branch_has_no_counter(&self, branch: &BcbBranch) -> bool { - self.branch_counter(branch).is_none() + fn branch_has_no_counter( + &self, + from_bcb: BasicCoverageBlock, + to_bcb: BasicCoverageBlock, + ) -> bool { + self.branch_counter(from_bcb, to_bcb).is_none() } - fn branch_counter(&self, branch: &BcbBranch) -> Option<&BcbCounter> { - let to_bcb = branch.target_bcb; - if let Some(from_bcb) = branch.edge_from_bcb { + fn branch_counter( + &self, + from_bcb: BasicCoverageBlock, + to_bcb: BasicCoverageBlock, + ) -> Option<&BcbCounter> { + if self.basic_coverage_blocks.bcb_has_multiple_in_edges(to_bcb) { self.coverage_counters.bcb_edge_counters.get(&(from_bcb, to_bcb)) } else { self.coverage_counters.bcb_counters[to_bcb].as_ref() } } - - /// 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 - } } diff --git a/compiler/rustc_mir_transform/src/coverage/graph.rs b/compiler/rustc_mir_transform/src/coverage/graph.rs index 0d807db404c..263bfdaaaba 100644 --- a/compiler/rustc_mir_transform/src/coverage/graph.rs +++ b/compiler/rustc_mir_transform/src/coverage/graph.rs @@ -62,6 +62,14 @@ impl CoverageGraph { Self { bcbs, bb_to_bcb, successors, predecessors, dominators: None }; let dominators = dominators::dominators(&basic_coverage_blocks); basic_coverage_blocks.dominators = Some(dominators); + + // The coverage graph's entry-point node (bcb0) always starts with bb0, + // which never has predecessors. Any other blocks merged into bcb0 can't + // have multiple (coverage-relevant) predecessors, so bcb0 always has + // zero in-edges. + assert!(basic_coverage_blocks[START_BCB].leader_bb() == mir::START_BLOCK); + assert!(basic_coverage_blocks.predecessors[START_BCB].is_empty()); + basic_coverage_blocks } @@ -199,6 +207,25 @@ impl CoverageGraph { pub fn cmp_in_dominator_order(&self, a: BasicCoverageBlock, b: BasicCoverageBlock) -> Ordering { self.dominators.as_ref().unwrap().cmp_in_dominator_order(a, b) } + + /// Returns true if the given node has 2 or more in-edges, i.e. 2 or more + /// predecessors. + /// + /// This property is interesting to code that assigns counters to nodes and + /// edges, because if a node _doesn't_ have multiple in-edges, then there's + /// no benefit in having a separate counter for its in-edge, because it + /// would have the same value as the node's own counter. + /// + /// FIXME: That assumption might not be true for [`TerminatorKind::Yield`]? + #[inline(always)] + pub(super) fn bcb_has_multiple_in_edges(&self, bcb: BasicCoverageBlock) -> bool { + // Even though bcb0 conceptually has an extra virtual in-edge due to + // being the entry point, we've already asserted that it has no _other_ + // in-edges, so there's no possibility of it having _multiple_ in-edges. + // (And since its virtual in-edge doesn't exist in the graph, that edge + // can't have a separate counter anyway.) + self.predecessors[bcb].len() > 1 + } } impl Index<BasicCoverageBlock> for CoverageGraph { @@ -319,45 +346,6 @@ impl BasicCoverageBlockData { } } -/// Represents a successor from a branching BasicCoverageBlock (such as the arms of a `SwitchInt`) -/// as either the successor BCB itself, if it has only one incoming edge, or the successor _plus_ -/// the specific branching BCB, representing the edge between the two. The latter case -/// distinguishes this incoming edge from other incoming edges to the same `target_bcb`. -#[derive(Clone, Copy, PartialEq, Eq)] -pub(super) struct BcbBranch { - pub edge_from_bcb: Option<BasicCoverageBlock>, - pub target_bcb: BasicCoverageBlock, -} - -impl BcbBranch { - pub fn from_to( - from_bcb: BasicCoverageBlock, - to_bcb: BasicCoverageBlock, - basic_coverage_blocks: &CoverageGraph, - ) -> Self { - let edge_from_bcb = if basic_coverage_blocks.predecessors[to_bcb].len() > 1 { - Some(from_bcb) - } else { - None - }; - Self { edge_from_bcb, target_bcb: to_bcb } - } - - pub fn is_only_path_to_target(&self) -> bool { - self.edge_from_bcb.is_none() - } -} - -impl std::fmt::Debug for BcbBranch { - fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - if let Some(from_bcb) = self.edge_from_bcb { - write!(fmt, "{:?}->{:?}", from_bcb, self.target_bcb) - } else { - write!(fmt, "{:?}", self.target_bcb) - } - } -} - // Returns the subset of a block's successors that are relevant to the coverage // graph, i.e. those that do not represent unwinds or unreachable branches. // FIXME(#78544): MIR InstrumentCoverage: Improve coverage of `#[should_panic]` tests and |