diff options
Diffstat (limited to 'compiler/rustc_mir_transform/src')
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/counters.rs | 131 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/graph.rs | 161 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/tests.rs | 2 |
3 files changed, 130 insertions, 164 deletions
diff --git a/compiler/rustc_mir_transform/src/coverage/counters.rs b/compiler/rustc_mir_transform/src/coverage/counters.rs index 78845af0162..77e3dee1fef 100644 --- a/compiler/rustc_mir_transform/src/coverage/counters.rs +++ b/compiler/rustc_mir_transform/src/coverage/counters.rs @@ -245,13 +245,13 @@ impl<'a> MakeBcbCounters<'a> { // 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) { + 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(&mut traversal, bcb, branching_counter_operand)?; + self.make_branch_counters(&traversal, bcb, branching_counter_operand)?; } } else { debug!( @@ -274,7 +274,7 @@ impl<'a> MakeBcbCounters<'a> { fn make_branch_counters( &mut self, - traversal: &mut TraverseCoverageGraphWithLoops, + traversal: &TraverseCoverageGraphWithLoops<'_>, branching_bcb: BasicCoverageBlock, branching_counter_operand: Operand, ) -> Result<(), Error> { @@ -507,21 +507,14 @@ impl<'a> MakeBcbCounters<'a> { /// found, select any branch. fn choose_preferred_expression_branch( &self, - traversal: &TraverseCoverageGraphWithLoops, + traversal: &TraverseCoverageGraphWithLoops<'_>, branches: &[BcbBranch], ) -> BcbBranch { - let branch_needs_a_counter = |branch: &BcbBranch| self.branch_has_no_counter(branch); - - 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 + 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 } else { let &branch_without_counter = branches.iter().find(|&branch| self.branch_has_no_counter(branch)).expect( @@ -538,75 +531,52 @@ impl<'a> MakeBcbCounters<'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. - /// - /// 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( + /// Tries to find a branch that leads back to the top of a loop, and that + /// doesn't already have a counter. Such branches are good candidates to + /// be given an expression (instead of a physical counter), because they + /// will tend to be executed more times than a loop-exit branch. + fn find_good_reloop_branch( &self, - traversal: &TraverseCoverageGraphWithLoops, + traversal: &TraverseCoverageGraphWithLoops<'_>, branches: &[BcbBranch], ) -> Option<BcbBranch> { - let branch_needs_a_counter = |branch: &BcbBranch| self.branch_has_no_counter(branch); - - 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_dominates(branch.target_bcb, backedge_from_bcb) - }) { - if let Some(reloop_branch) = some_reloop_branch { - if self.branch_has_no_counter(&reloop_branch) { - // 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; + // 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 { + // 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) + }); + + if is_reloop_branch { + all_branches_exit_this_loop = false; + if self.branch_has_no_counter(&branch) { + // We found a good branch to be given an expression. + return Some(branch); } + // Keep looking for another reloop branch without a counter. + } else { + // This branch exits the loop. } - 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) } + + if !all_branches_exit_this_loop { + // We found one or more reloop branches, but all of them already + // have counters. Let the caller choose one of the exit branches. + debug!("All reloop branches had counters; skip checking the other loops"); + return None; + } + + // All of the branches exit this loop, so keep looking for a good + // reloop branch for one of the outer loops. } - some_reloop_branch + + None } #[inline] @@ -652,9 +622,4 @@ impl<'a> MakeBcbCounters<'a> { fn bcb_has_one_path_to_target(&self, bcb: BasicCoverageBlock) -> bool { self.bcb_predecessors(bcb).len() <= 1 } - - #[inline] - fn bcb_dominates(&self, dom: BasicCoverageBlock, node: BasicCoverageBlock) -> bool { - self.basic_coverage_blocks.dominates(dom, node) - } } diff --git a/compiler/rustc_mir_transform/src/coverage/graph.rs b/compiler/rustc_mir_transform/src/coverage/graph.rs index 39027d21f06..9a7adaada09 100644 --- a/compiler/rustc_mir_transform/src/coverage/graph.rs +++ b/compiler/rustc_mir_transform/src/coverage/graph.rs @@ -6,6 +6,7 @@ use rustc_index::{IndexSlice, IndexVec}; use rustc_middle::mir::{self, BasicBlock, TerminatorKind}; use std::cmp::Ordering; +use std::collections::VecDeque; use std::ops::{Index, IndexMut}; /// A coverage-specific simplification of the MIR control flow graph (CFG). The `CoverageGraph`s @@ -385,57 +386,72 @@ fn bcb_filtered_successors<'a, 'tcx>( /// ensures a loop is completely traversed before processing Blocks after the end of the loop. #[derive(Debug)] pub(super) struct TraversalContext { - /// From one or more backedges returning to a loop header. - pub loop_backedges: Option<(Vec<BasicCoverageBlock>, BasicCoverageBlock)>, - - /// worklist, to be traversed, of CoverageGraph in the loop with the given loop - /// backedges, such that the loop is the inner inner-most loop containing these - /// CoverageGraph - pub worklist: Vec<BasicCoverageBlock>, + /// BCB with one or more incoming loop backedges, indicating which loop + /// this context is for. + /// + /// If `None`, this is the non-loop context for the function as a whole. + loop_header: Option<BasicCoverageBlock>, + + /// Worklist of BCBs to be processed in this context. + worklist: VecDeque<BasicCoverageBlock>, } -pub(super) struct TraverseCoverageGraphWithLoops { - pub backedges: IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>>, - pub context_stack: Vec<TraversalContext>, +pub(super) struct TraverseCoverageGraphWithLoops<'a> { + basic_coverage_blocks: &'a CoverageGraph, + + backedges: IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>>, + context_stack: Vec<TraversalContext>, visited: BitSet<BasicCoverageBlock>, } -impl TraverseCoverageGraphWithLoops { - pub fn new(basic_coverage_blocks: &CoverageGraph) -> Self { - let start_bcb = basic_coverage_blocks.start_node(); +impl<'a> TraverseCoverageGraphWithLoops<'a> { + pub(super) fn new(basic_coverage_blocks: &'a CoverageGraph) -> Self { let backedges = find_loop_backedges(basic_coverage_blocks); - let context_stack = - vec![TraversalContext { loop_backedges: None, worklist: vec![start_bcb] }]; + + let worklist = VecDeque::from([basic_coverage_blocks.start_node()]); + let context_stack = vec![TraversalContext { loop_header: None, worklist }]; + // `context_stack` starts with a `TraversalContext` for the main function context (beginning // with the `start` BasicCoverageBlock of the function). New worklists are pushed to the top // of the stack as loops are entered, and popped off of the stack when a loop's worklist is // exhausted. let visited = BitSet::new_empty(basic_coverage_blocks.num_nodes()); - Self { backedges, context_stack, visited } + Self { basic_coverage_blocks, backedges, context_stack, visited } } - pub fn next(&mut self, basic_coverage_blocks: &CoverageGraph) -> Option<BasicCoverageBlock> { + /// For each loop on the loop context stack (top-down), yields a list of BCBs + /// within that loop that have an outgoing edge back to the loop header. + pub(super) fn reloop_bcbs_per_loop(&self) -> impl Iterator<Item = &[BasicCoverageBlock]> { + self.context_stack + .iter() + .rev() + .filter_map(|context| context.loop_header) + .map(|header_bcb| self.backedges[header_bcb].as_slice()) + } + + pub(super) fn next(&mut self) -> Option<BasicCoverageBlock> { debug!( "TraverseCoverageGraphWithLoops::next - context_stack: {:?}", self.context_stack.iter().rev().collect::<Vec<_>>() ); while let Some(context) = self.context_stack.last_mut() { - if let Some(next_bcb) = context.worklist.pop() { - if !self.visited.insert(next_bcb) { - debug!("Already visited: {:?}", next_bcb); + if let Some(bcb) = context.worklist.pop_front() { + if !self.visited.insert(bcb) { + debug!("Already visited: {bcb:?}"); continue; } - debug!("Visiting {:?}", next_bcb); - if self.backedges[next_bcb].len() > 0 { - debug!("{:?} is a loop header! Start a new TraversalContext...", next_bcb); + debug!("Visiting {bcb:?}"); + + if self.backedges[bcb].len() > 0 { + debug!("{bcb:?} is a loop header! Start a new TraversalContext..."); self.context_stack.push(TraversalContext { - loop_backedges: Some((self.backedges[next_bcb].clone(), next_bcb)), - worklist: Vec::new(), + loop_header: Some(bcb), + worklist: VecDeque::new(), }); } - self.extend_worklist(basic_coverage_blocks, next_bcb); - return Some(next_bcb); + self.add_successors_to_worklists(bcb); + return Some(bcb); } else { // Strip contexts with empty worklists from the top of the stack self.context_stack.pop(); @@ -445,13 +461,10 @@ impl TraverseCoverageGraphWithLoops { None } - pub fn extend_worklist( - &mut self, - basic_coverage_blocks: &CoverageGraph, - bcb: BasicCoverageBlock, - ) { - let successors = &basic_coverage_blocks.successors[bcb]; + pub fn add_successors_to_worklists(&mut self, bcb: BasicCoverageBlock) { + let successors = &self.basic_coverage_blocks.successors[bcb]; debug!("{:?} has {} successors:", bcb, successors.len()); + for &successor in successors { if successor == bcb { debug!( @@ -460,56 +473,44 @@ impl TraverseCoverageGraphWithLoops { bcb ); // Don't re-add this successor to the worklist. We are already processing it. + // FIXME: This claims to skip just the self-successor, but it actually skips + // all other successors as well. Does that matter? break; } - for context in self.context_stack.iter_mut().rev() { - // Add successors of the current BCB to the appropriate context. Successors that - // stay within a loop are added to the BCBs context worklist. Successors that - // exit the loop (they are not dominated by the loop header) must be reachable - // from other BCBs outside the loop, and they will be added to a different - // worklist. - // - // Branching blocks (with more than one successor) must be processed before - // blocks with only one successor, to prevent unnecessarily complicating - // `Expression`s by creating a Counter in a `BasicCoverageBlock` that the - // branching block would have given an `Expression` (or vice versa). - let (some_successor_to_add, some_loop_header) = - if let Some((_, loop_header)) = context.loop_backedges { - if basic_coverage_blocks.dominates(loop_header, successor) { - (Some(successor), Some(loop_header)) - } else { - (None, None) - } - } else { - (Some(successor), None) - }; - if let Some(successor_to_add) = some_successor_to_add { - if basic_coverage_blocks.successors[successor_to_add].len() > 1 { - debug!( - "{:?} successor is branching. Prioritize it at the beginning of \ - the {}", - successor_to_add, - if let Some(loop_header) = some_loop_header { - format!("worklist for the loop headed by {loop_header:?}") - } else { - String::from("non-loop worklist") - }, - ); - context.worklist.insert(0, successor_to_add); - } else { - debug!( - "{:?} successor is non-branching. Defer it to the end of the {}", - successor_to_add, - if let Some(loop_header) = some_loop_header { - format!("worklist for the loop headed by {loop_header:?}") - } else { - String::from("non-loop worklist") - }, - ); - context.worklist.push(successor_to_add); + + // Add successors of the current BCB to the appropriate context. Successors that + // stay within a loop are added to the BCBs context worklist. Successors that + // exit the loop (they are not dominated by the loop header) must be reachable + // from other BCBs outside the loop, and they will be added to a different + // worklist. + // + // Branching blocks (with more than one successor) must be processed before + // blocks with only one successor, to prevent unnecessarily complicating + // `Expression`s by creating a Counter in a `BasicCoverageBlock` that the + // branching block would have given an `Expression` (or vice versa). + + let context = self + .context_stack + .iter_mut() + .rev() + .find(|context| match context.loop_header { + Some(loop_header) => { + self.basic_coverage_blocks.dominates(loop_header, successor) } - break; - } + None => true, + }) + .unwrap_or_else(|| bug!("should always fall back to the root non-loop context")); + debug!("adding to worklist for {:?}", context.loop_header); + + // FIXME: The code below had debug messages claiming to add items to a + // particular end of the worklist, but was confused about which end was + // which. The existing behaviour has been preserved for now, but it's + // unclear what the intended behaviour was. + + if self.basic_coverage_blocks.successors[successor].len() > 1 { + context.worklist.push_back(successor); + } else { + context.worklist.push_front(successor); } } } diff --git a/compiler/rustc_mir_transform/src/coverage/tests.rs b/compiler/rustc_mir_transform/src/coverage/tests.rs index ee7cb791c81..487d2282364 100644 --- a/compiler/rustc_mir_transform/src/coverage/tests.rs +++ b/compiler/rustc_mir_transform/src/coverage/tests.rs @@ -628,7 +628,7 @@ fn test_traverse_coverage_with_loops() { let basic_coverage_blocks = graph::CoverageGraph::from_mir(&mir_body); let mut traversed_in_order = Vec::new(); let mut traversal = graph::TraverseCoverageGraphWithLoops::new(&basic_coverage_blocks); - while let Some(bcb) = traversal.next(&basic_coverage_blocks) { + while let Some(bcb) = traversal.next() { traversed_in_order.push(bcb); } |