diff options
Diffstat (limited to 'compiler/rustc_mir_transform/src')
| -rw-r--r-- | compiler/rustc_mir_transform/src/coroutine.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/counters.rs | 247 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/graph.rs | 134 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/mappings.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/spans.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/gvn.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/inline.rs | 7 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/promote_consts.rs | 2 |
8 files changed, 213 insertions, 185 deletions
diff --git a/compiler/rustc_mir_transform/src/coroutine.rs b/compiler/rustc_mir_transform/src/coroutine.rs index 0a413d68020..cd291058977 100644 --- a/compiler/rustc_mir_transform/src/coroutine.rs +++ b/compiler/rustc_mir_transform/src/coroutine.rs @@ -1497,7 +1497,7 @@ fn check_field_tys_sized<'tcx>( ) { // No need to check if unsized_locals/unsized_fn_params is disabled, // since we will error during typeck. - if !tcx.features().unsized_locals && !tcx.features().unsized_fn_params { + if !tcx.features().unsized_locals() && !tcx.features().unsized_fn_params() { return; } diff --git a/compiler/rustc_mir_transform/src/coverage/counters.rs b/compiler/rustc_mir_transform/src/coverage/counters.rs index 94088156756..cf9f6981c5a 100644 --- a/compiler/rustc_mir_transform/src/coverage/counters.rs +++ b/compiler/rustc_mir_transform/src/coverage/counters.rs @@ -5,7 +5,6 @@ use rustc_data_structures::fx::FxHashMap; use rustc_data_structures::graph::DirectedGraph; use rustc_index::IndexVec; use rustc_index::bit_set::BitSet; -use rustc_middle::bug; use rustc_middle::mir::coverage::{CounterId, CovTerm, Expression, ExpressionId, Op}; use tracing::{debug, debug_span, instrument}; @@ -58,13 +57,13 @@ pub(super) struct CoverageCounters { counter_increment_sites: IndexVec<CounterId, CounterIncrementSite>, /// Coverage counters/expressions that are associated with individual BCBs. - bcb_counters: IndexVec<BasicCoverageBlock, Option<BcbCounter>>, + node_counters: IndexVec<BasicCoverageBlock, Option<BcbCounter>>, /// Coverage counters/expressions that are associated with the control-flow /// edge between two BCBs. /// /// We currently don't iterate over this map, but if we do in the future, /// switch it back to `FxIndexMap` to avoid query stability hazards. - bcb_edge_counters: FxHashMap<(BasicCoverageBlock, BasicCoverageBlock), BcbCounter>, + edge_counters: FxHashMap<(BasicCoverageBlock, BasicCoverageBlock), BcbCounter>, /// Table of expression data, associating each expression ID with its /// corresponding operator (+ or -) and its LHS/RHS operands. @@ -78,20 +77,20 @@ impl CoverageCounters { /// Ensures that each BCB node needing a counter has one, by creating physical /// counters or counter expressions for nodes and edges as required. pub(super) fn make_bcb_counters( - basic_coverage_blocks: &CoverageGraph, + graph: &CoverageGraph, bcb_needs_counter: &BitSet<BasicCoverageBlock>, ) -> Self { - let mut counters = MakeBcbCounters::new(basic_coverage_blocks, bcb_needs_counter); - counters.make_bcb_counters(); + let mut builder = CountersBuilder::new(graph, bcb_needs_counter); + builder.make_bcb_counters(); - counters.coverage_counters + builder.counters } fn with_num_bcbs(num_bcbs: usize) -> Self { Self { counter_increment_sites: IndexVec::new(), - bcb_counters: IndexVec::from_elem_n(None, num_bcbs), - bcb_edge_counters: FxHashMap::default(), + node_counters: IndexVec::from_elem_n(None, num_bcbs), + edge_counters: FxHashMap::default(), expressions: IndexVec::new(), expressions_memo: FxHashMap::default(), } @@ -104,24 +103,18 @@ impl CoverageCounters { BcbCounter::Counter { id } } - /// Creates a new physical counter attached a BCB node. - /// The node must not already have a counter. + /// Creates a new physical counter for a BCB node. fn make_phys_node_counter(&mut self, bcb: BasicCoverageBlock) -> BcbCounter { - let counter = self.make_counter_inner(CounterIncrementSite::Node { bcb }); - debug!(?bcb, ?counter, "node gets a physical counter"); - self.set_bcb_counter(bcb, counter) + self.make_counter_inner(CounterIncrementSite::Node { bcb }) } - /// Creates a new physical counter attached to a BCB edge. - /// The edge must not already have a counter. + /// Creates a new physical counter for a BCB edge. fn make_phys_edge_counter( &mut self, from_bcb: BasicCoverageBlock, to_bcb: BasicCoverageBlock, ) -> BcbCounter { - let counter = self.make_counter_inner(CounterIncrementSite::Edge { from_bcb, to_bcb }); - debug!(?from_bcb, ?to_bcb, ?counter, "edge gets a physical counter"); - self.set_bcb_edge_counter(from_bcb, to_bcb, counter) + self.make_counter_inner(CounterIncrementSite::Edge { from_bcb, to_bcb }) } fn make_expression(&mut self, lhs: BcbCounter, op: Op, rhs: BcbCounter) -> BcbCounter { @@ -193,35 +186,31 @@ impl CoverageCounters { self.counter_increment_sites.len() } - fn set_bcb_counter(&mut self, bcb: BasicCoverageBlock, counter_kind: BcbCounter) -> BcbCounter { - 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 { - counter_kind - } + fn set_node_counter(&mut self, bcb: BasicCoverageBlock, counter: BcbCounter) -> BcbCounter { + let existing = self.node_counters[bcb].replace(counter); + assert!( + existing.is_none(), + "node {bcb:?} already has a counter: {existing:?} => {counter:?}" + ); + counter } - fn set_bcb_edge_counter( + fn set_edge_counter( &mut self, from_bcb: BasicCoverageBlock, to_bcb: BasicCoverageBlock, - counter_kind: BcbCounter, + counter: BcbCounter, ) -> BcbCounter { - 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 { - counter_kind - } + let existing = self.edge_counters.insert((from_bcb, to_bcb), counter); + assert!( + existing.is_none(), + "edge ({from_bcb:?} -> {to_bcb:?}) already has a counter: {existing:?} => {counter:?}" + ); + counter } pub(super) fn term_for_bcb(&self, bcb: BasicCoverageBlock) -> Option<CovTerm> { - self.bcb_counters[bcb].map(|counter| counter.as_term()) + self.node_counters[bcb].map(|counter| counter.as_term()) } /// Returns an iterator over all the nodes/edges in the coverage graph that @@ -238,7 +227,7 @@ impl CoverageCounters { pub(super) fn bcb_nodes_with_coverage_expressions( &self, ) -> impl Iterator<Item = (BasicCoverageBlock, ExpressionId)> + Captures<'_> { - self.bcb_counters.iter_enumerated().filter_map(|(bcb, &counter_kind)| match counter_kind { + self.node_counters.iter_enumerated().filter_map(|(bcb, &counter)| match counter { // Yield the BCB along with its associated expression ID. Some(BcbCounter::Expression { id }) => Some((bcb, id)), // This BCB is associated with a counter or nothing, so skip it. @@ -265,22 +254,20 @@ impl CoverageCounters { } } -/// Helper struct that allows counter creation to inspect the BCB graph. -struct MakeBcbCounters<'a> { - coverage_counters: CoverageCounters, - basic_coverage_blocks: &'a CoverageGraph, +/// Helper struct that allows counter creation to inspect the BCB graph, and +/// the set of nodes that need counters. +struct CountersBuilder<'a> { + counters: CoverageCounters, + graph: &'a CoverageGraph, bcb_needs_counter: &'a BitSet<BasicCoverageBlock>, } -impl<'a> MakeBcbCounters<'a> { - fn new( - basic_coverage_blocks: &'a CoverageGraph, - bcb_needs_counter: &'a BitSet<BasicCoverageBlock>, - ) -> Self { - assert_eq!(basic_coverage_blocks.num_nodes(), bcb_needs_counter.domain_size()); +impl<'a> CountersBuilder<'a> { + fn new(graph: &'a CoverageGraph, bcb_needs_counter: &'a BitSet<BasicCoverageBlock>) -> Self { + assert_eq!(graph.num_nodes(), bcb_needs_counter.domain_size()); Self { - coverage_counters: CoverageCounters::with_num_bcbs(basic_coverage_blocks.num_nodes()), - basic_coverage_blocks, + counters: CoverageCounters::with_num_bcbs(graph.num_nodes()), + graph, bcb_needs_counter, } } @@ -293,13 +280,12 @@ impl<'a> MakeBcbCounters<'a> { // // The traversal tries to ensure that, when a loop is encountered, all // nodes within the loop are visited before visiting any nodes outside - // the loop. It also keeps track of which loop(s) the traversal is - // currently inside. - let mut traversal = TraverseCoverageGraphWithLoops::new(self.basic_coverage_blocks); + // the loop. + let mut traversal = TraverseCoverageGraphWithLoops::new(self.graph); while let Some(bcb) = traversal.next() { let _span = debug_span!("traversal", ?bcb).entered(); if self.bcb_needs_counter.contains(bcb) { - self.make_node_counter_and_out_edge_counters(&traversal, bcb); + self.make_node_counter_and_out_edge_counters(bcb); } } @@ -312,36 +298,41 @@ impl<'a> MakeBcbCounters<'a> { /// Make sure the given node has a node counter, and then make sure each of /// its out-edges has an edge counter (if appropriate). - #[instrument(level = "debug", skip(self, traversal))] - fn make_node_counter_and_out_edge_counters( - &mut self, - traversal: &TraverseCoverageGraphWithLoops<'_>, - from_bcb: BasicCoverageBlock, - ) { + #[instrument(level = "debug", skip(self))] + fn make_node_counter_and_out_edge_counters(&mut self, from_bcb: BasicCoverageBlock) { // First, ensure that this node has a counter of some kind. // We might also use that counter to compute one of the out-edge counters. let node_counter = self.get_or_make_node_counter(from_bcb); - let successors = self.basic_coverage_blocks.successors[from_bcb].as_slice(); + let successors = self.graph.successors[from_bcb].as_slice(); // If this node's out-edges won't sum to the node's counter, // then there's no reason to create edge counters here. - if !self.basic_coverage_blocks[from_bcb].is_out_summable { + if !self.graph[from_bcb].is_out_summable { return; } - // Determine the set of out-edges that don't yet have edge counters. - let candidate_successors = self.basic_coverage_blocks.successors[from_bcb] + // When choosing which out-edge should be given a counter expression, ignore edges that + // already have counters, or could use the existing counter of their target node. + let out_edge_has_counter = |to_bcb| { + if self.counters.edge_counters.contains_key(&(from_bcb, to_bcb)) { + return true; + } + self.graph.sole_predecessor(to_bcb) == Some(from_bcb) + && self.counters.node_counters[to_bcb].is_some() + }; + + // Determine the set of out-edges that could benefit from being given an expression. + let candidate_successors = self.graph.successors[from_bcb] .iter() .copied() - .filter(|&to_bcb| self.edge_has_no_counter(from_bcb, to_bcb)) + .filter(|&to_bcb| !out_edge_has_counter(to_bcb)) .collect::<Vec<_>>(); debug!(?candidate_successors); // If there are out-edges without counters, choose one to be given an expression // (computed from this node and the other out-edges) instead of a physical counter. - let Some(expression_to_bcb) = - self.choose_out_edge_for_expression(traversal, &candidate_successors) + let Some(target_bcb) = self.choose_out_edge_for_expression(from_bcb, &candidate_successors) else { return; }; @@ -353,43 +344,44 @@ impl<'a> MakeBcbCounters<'a> { .iter() .copied() // Skip the chosen edge, since we'll calculate its count from this sum. - .filter(|&to_bcb| to_bcb != expression_to_bcb) + .filter(|&edge_target_bcb| edge_target_bcb != target_bcb) .map(|to_bcb| self.get_or_make_edge_counter(from_bcb, to_bcb)) .collect::<Vec<_>>(); - let Some(sum_of_all_other_out_edges) = - self.coverage_counters.make_sum(&other_out_edge_counters) + let Some(sum_of_all_other_out_edges) = self.counters.make_sum(&other_out_edge_counters) else { return; }; // Now create an expression for the chosen edge, by taking the counter // for its source node and subtracting the sum of its sibling out-edges. - let expression = self.coverage_counters.make_expression( - node_counter, - Op::Subtract, - sum_of_all_other_out_edges, - ); + let expression = + self.counters.make_expression(node_counter, Op::Subtract, sum_of_all_other_out_edges); - debug!("{expression_to_bcb:?} gets an expression: {expression:?}"); - if let Some(sole_pred) = self.basic_coverage_blocks.sole_predecessor(expression_to_bcb) { - // This edge normally wouldn't get its own counter, so attach the expression - // to its target node instead, so that `edge_has_no_counter` can see it. - assert_eq!(sole_pred, from_bcb); - self.coverage_counters.set_bcb_counter(expression_to_bcb, expression); - } else { - self.coverage_counters.set_bcb_edge_counter(from_bcb, expression_to_bcb, expression); - } + debug!("{target_bcb:?} gets an expression: {expression:?}"); + self.counters.set_edge_counter(from_bcb, target_bcb, expression); } #[instrument(level = "debug", skip(self))] fn get_or_make_node_counter(&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] { - debug!("{bcb:?} already has a counter: {counter_kind:?}"); - return counter_kind; + if let Some(counter) = self.counters.node_counters[bcb] { + debug!("{bcb:?} already has a counter: {counter:?}"); + return counter; + } + + let counter = self.make_node_counter_inner(bcb); + self.counters.set_node_counter(bcb, counter) + } + + fn make_node_counter_inner(&mut self, bcb: BasicCoverageBlock) -> BcbCounter { + // If the node's sole in-edge already has a counter, use that. + if let Some(sole_pred) = self.graph.sole_predecessor(bcb) + && let Some(&edge_counter) = self.counters.edge_counters.get(&(sole_pred, bcb)) + { + return edge_counter; } - let predecessors = self.basic_coverage_blocks.predecessors[bcb].as_slice(); + let predecessors = self.graph.predecessors[bcb].as_slice(); // Handle cases where we can't compute a node's count from its in-edges: // - START_BCB has no in-edges, so taking the sum would panic (or be wrong). @@ -398,7 +390,9 @@ impl<'a> MakeBcbCounters<'a> { // leading to infinite recursion. if predecessors.len() <= 1 || predecessors.contains(&bcb) { debug!(?bcb, ?predecessors, "node has <=1 predecessors or is its own predecessor"); - return self.coverage_counters.make_phys_node_counter(bcb); + let counter = self.counters.make_phys_node_counter(bcb); + debug!(?bcb, ?counter, "node gets a physical counter"); + return counter; } // A BCB with multiple incoming edges can compute its count by ensuring that counters @@ -408,13 +402,11 @@ impl<'a> MakeBcbCounters<'a> { .copied() .map(|from_bcb| self.get_or_make_edge_counter(from_bcb, bcb)) .collect::<Vec<_>>(); - let sum_of_in_edges: BcbCounter = self - .coverage_counters - .make_sum(&in_edge_counters) - .expect("there must be at least one in-edge"); + let sum_of_in_edges: BcbCounter = + self.counters.make_sum(&in_edge_counters).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) + sum_of_in_edges } #[instrument(level = "debug", skip(self))] @@ -423,9 +415,24 @@ impl<'a> MakeBcbCounters<'a> { from_bcb: BasicCoverageBlock, to_bcb: BasicCoverageBlock, ) -> BcbCounter { + // If the edge already has a counter, return it. + if let Some(&counter) = self.counters.edge_counters.get(&(from_bcb, to_bcb)) { + debug!("Edge {from_bcb:?}->{to_bcb:?} already has a counter: {counter:?}"); + return counter; + } + + let counter = self.make_edge_counter_inner(from_bcb, to_bcb); + self.counters.set_edge_counter(from_bcb, to_bcb, counter) + } + + fn make_edge_counter_inner( + &mut self, + from_bcb: BasicCoverageBlock, + to_bcb: BasicCoverageBlock, + ) -> BcbCounter { // If the target node has exactly one in-edge (i.e. this one), then just // use the node's counter, since it will have the same value. - if let Some(sole_pred) = self.basic_coverage_blocks.sole_predecessor(to_bcb) { + if let Some(sole_pred) = self.graph.sole_predecessor(to_bcb) { assert_eq!(sole_pred, from_bcb); // This call must take care not to invoke `get_or_make_edge` for // this edge, since that would result in infinite recursion! @@ -434,33 +441,27 @@ impl<'a> MakeBcbCounters<'a> { // If the source node has exactly one out-edge (i.e. this one) and would have // the same execution count as that edge, then just use the node's counter. - if let Some(simple_succ) = self.basic_coverage_blocks.simple_successor(from_bcb) { + if let Some(simple_succ) = self.graph.simple_successor(from_bcb) { assert_eq!(simple_succ, to_bcb); return self.get_or_make_node_counter(from_bcb); } - // If the edge already has a counter, return it. - 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; - } - // Make a new counter to count this edge. - self.coverage_counters.make_phys_edge_counter(from_bcb, to_bcb) + let counter = self.counters.make_phys_edge_counter(from_bcb, to_bcb); + debug!(?from_bcb, ?to_bcb, ?counter, "edge gets a physical counter"); + counter } /// Given a set of candidate out-edges (represented by their successor node), /// choose one to be given a counter expression instead of a physical counter. fn choose_out_edge_for_expression( &self, - traversal: &TraverseCoverageGraphWithLoops<'_>, + from_bcb: BasicCoverageBlock, candidate_successors: &[BasicCoverageBlock], ) -> Option<BasicCoverageBlock> { // Try to find a candidate that leads back to the top of a loop, // because reloop edges tend to be executed more times than loop-exit edges. - if let Some(reloop_target) = self.find_good_reloop_edge(traversal, &candidate_successors) { + if let Some(reloop_target) = self.find_good_reloop_edge(from_bcb, &candidate_successors) { debug!("Selecting reloop target {reloop_target:?} to get an expression"); return Some(reloop_target); } @@ -479,7 +480,7 @@ impl<'a> MakeBcbCounters<'a> { /// for them to be able to avoid a physical counter increment. fn find_good_reloop_edge( &self, - traversal: &TraverseCoverageGraphWithLoops<'_>, + from_bcb: BasicCoverageBlock, candidate_successors: &[BasicCoverageBlock], ) -> Option<BasicCoverageBlock> { // If there are no candidates, avoid iterating over the loop stack. @@ -488,14 +489,15 @@ impl<'a> MakeBcbCounters<'a> { } // Consider each loop on the current traversal context stack, top-down. - for reloop_bcbs in traversal.reloop_bcbs_per_loop() { + for loop_header_node in self.graph.loop_headers_containing(from_bcb) { // Try to find a candidate edge that doesn't exit this loop. for &target_bcb in candidate_successors { // An edge is a reloop edge if its target dominates any BCB that has // an edge back to the loop header. (Otherwise it's an exit edge.) - let is_reloop_edge = reloop_bcbs.iter().any(|&reloop_bcb| { - self.basic_coverage_blocks.dominates(target_bcb, reloop_bcb) - }); + let is_reloop_edge = self + .graph + .reloop_predecessors(loop_header_node) + .any(|reloop_bcb| self.graph.dominates(target_bcb, reloop_bcb)); if is_reloop_edge { // We found a good out-edge to be given an expression. return Some(target_bcb); @@ -508,21 +510,4 @@ impl<'a> MakeBcbCounters<'a> { None } - - #[inline] - fn edge_has_no_counter( - &self, - from_bcb: BasicCoverageBlock, - to_bcb: BasicCoverageBlock, - ) -> bool { - let edge_counter = - if let Some(sole_pred) = self.basic_coverage_blocks.sole_predecessor(to_bcb) { - assert_eq!(sole_pred, from_bcb); - self.coverage_counters.bcb_counters[to_bcb] - } else { - self.coverage_counters.bcb_edge_counters.get(&(from_bcb, to_bcb)).copied() - }; - - edge_counter.is_none() - } } diff --git a/compiler/rustc_mir_transform/src/coverage/graph.rs b/compiler/rustc_mir_transform/src/coverage/graph.rs index d839f46cfbd..168262bf01c 100644 --- a/compiler/rustc_mir_transform/src/coverage/graph.rs +++ b/compiler/rustc_mir_transform/src/coverage/graph.rs @@ -1,10 +1,11 @@ use std::cmp::Ordering; use std::collections::VecDeque; +use std::iter; use std::ops::{Index, IndexMut}; use rustc_data_structures::captures::Captures; use rustc_data_structures::fx::FxHashSet; -use rustc_data_structures::graph::dominators::{self, Dominators}; +use rustc_data_structures::graph::dominators::Dominators; use rustc_data_structures::graph::{self, DirectedGraph, StartNode}; use rustc_index::IndexVec; use rustc_index::bit_set::BitSet; @@ -20,7 +21,17 @@ pub(crate) struct CoverageGraph { bb_to_bcb: IndexVec<BasicBlock, Option<BasicCoverageBlock>>, pub(crate) successors: IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>>, pub(crate) predecessors: IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>>, + dominators: Option<Dominators<BasicCoverageBlock>>, + /// Allows nodes to be compared in some total order such that _if_ + /// `a` dominates `b`, then `a < b`. If neither node dominates the other, + /// their relative order is consistent but arbitrary. + dominator_order_rank: IndexVec<BasicCoverageBlock, u32>, + /// A loop header is a node that dominates one or more of its predecessors. + is_loop_header: BitSet<BasicCoverageBlock>, + /// For each node, the loop header node of its nearest enclosing loop. + /// This forms a linked list that can be traversed to find all enclosing loops. + enclosing_loop_header: IndexVec<BasicCoverageBlock, Option<BasicCoverageBlock>>, } impl CoverageGraph { @@ -54,9 +65,47 @@ impl CoverageGraph { } } - let mut this = Self { bcbs, bb_to_bcb, successors, predecessors, dominators: None }; + let num_nodes = bcbs.len(); + let mut this = Self { + bcbs, + bb_to_bcb, + successors, + predecessors, + dominators: None, + dominator_order_rank: IndexVec::from_elem_n(0, num_nodes), + is_loop_header: BitSet::new_empty(num_nodes), + enclosing_loop_header: IndexVec::from_elem_n(None, num_nodes), + }; + assert_eq!(num_nodes, this.num_nodes()); + + // Set the dominators first, because later init steps rely on them. + this.dominators = Some(graph::dominators::dominators(&this)); + + // Iterate over all nodes, such that dominating nodes are visited before + // the nodes they dominate. Either preorder or reverse postorder is fine. + let dominator_order = graph::iterate::reverse_post_order(&this, this.start_node()); + // The coverage graph is created by traversal, so all nodes are reachable. + assert_eq!(dominator_order.len(), this.num_nodes()); + for (rank, bcb) in (0u32..).zip(dominator_order) { + // The dominator rank of each node is its index in a dominator-order traversal. + this.dominator_order_rank[bcb] = rank; + + // A node is a loop header if it dominates any of its predecessors. + if this.reloop_predecessors(bcb).next().is_some() { + this.is_loop_header.insert(bcb); + } - this.dominators = Some(dominators::dominators(&this)); + // If the immediate dominator is a loop header, that's our enclosing loop. + // Otherwise, inherit the immediate dominator's enclosing loop. + // (Dominator order ensures that we already processed the dominator.) + if let Some(dom) = this.dominators().immediate_dominator(bcb) { + this.enclosing_loop_header[bcb] = this + .is_loop_header + .contains(dom) + .then_some(dom) + .or_else(|| this.enclosing_loop_header[dom]); + } + } // The coverage graph's entry-point node (bcb0) always starts with bb0, // which never has predecessors. Any other blocks merged into bcb0 can't @@ -152,8 +201,13 @@ impl CoverageGraph { } #[inline(always)] + fn dominators(&self) -> &Dominators<BasicCoverageBlock> { + self.dominators.as_ref().unwrap() + } + + #[inline(always)] pub(crate) fn dominates(&self, dom: BasicCoverageBlock, node: BasicCoverageBlock) -> bool { - self.dominators.as_ref().unwrap().dominates(dom, node) + self.dominators().dominates(dom, node) } #[inline(always)] @@ -162,7 +216,7 @@ impl CoverageGraph { a: BasicCoverageBlock, b: BasicCoverageBlock, ) -> Ordering { - self.dominators.as_ref().unwrap().cmp_in_dominator_order(a, b) + self.dominator_order_rank[a].cmp(&self.dominator_order_rank[b]) } /// Returns the source of this node's sole in-edge, if it has exactly one. @@ -193,6 +247,36 @@ impl CoverageGraph { None } } + + /// For each loop that contains the given node, yields the "loop header" + /// node representing that loop, from innermost to outermost. If the given + /// node is itself a loop header, it is yielded first. + pub(crate) fn loop_headers_containing( + &self, + bcb: BasicCoverageBlock, + ) -> impl Iterator<Item = BasicCoverageBlock> + Captures<'_> { + let self_if_loop_header = self.is_loop_header.contains(bcb).then_some(bcb).into_iter(); + + let mut curr = Some(bcb); + let strictly_enclosing = iter::from_fn(move || { + let enclosing = self.enclosing_loop_header[curr?]; + curr = enclosing; + enclosing + }); + + self_if_loop_header.chain(strictly_enclosing) + } + + /// For the given node, yields the subset of its predecessor nodes that + /// it dominates. If that subset is non-empty, the node is a "loop header", + /// and each of those predecessors represents an in-edge that jumps back to + /// the top of its loop. + pub(crate) fn reloop_predecessors( + &self, + to_bcb: BasicCoverageBlock, + ) -> impl Iterator<Item = BasicCoverageBlock> + Captures<'_> { + self.predecessors[to_bcb].iter().copied().filter(move |&pred| self.dominates(to_bcb, pred)) + } } impl Index<BasicCoverageBlock> for CoverageGraph { @@ -418,15 +502,12 @@ struct TraversalContext { pub(crate) struct TraverseCoverageGraphWithLoops<'a> { basic_coverage_blocks: &'a CoverageGraph, - backedges: IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>>, context_stack: Vec<TraversalContext>, visited: BitSet<BasicCoverageBlock>, } impl<'a> TraverseCoverageGraphWithLoops<'a> { pub(crate) fn new(basic_coverage_blocks: &'a CoverageGraph) -> Self { - let backedges = find_loop_backedges(basic_coverage_blocks); - let worklist = VecDeque::from([basic_coverage_blocks.start_node()]); let context_stack = vec![TraversalContext { loop_header: None, worklist }]; @@ -435,17 +516,7 @@ impl<'a> TraverseCoverageGraphWithLoops<'a> { // 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 { basic_coverage_blocks, backedges, context_stack, visited } - } - - /// 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(crate) 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()) + Self { basic_coverage_blocks, context_stack, visited } } pub(crate) fn next(&mut self) -> Option<BasicCoverageBlock> { @@ -467,7 +538,7 @@ impl<'a> TraverseCoverageGraphWithLoops<'a> { } debug!("Visiting {bcb:?}"); - if self.backedges[bcb].len() > 0 { + if self.basic_coverage_blocks.is_loop_header.contains(bcb) { debug!("{bcb:?} is a loop header! Start a new TraversalContext..."); self.context_stack .push(TraversalContext { loop_header: Some(bcb), worklist: VecDeque::new() }); @@ -545,29 +616,6 @@ impl<'a> TraverseCoverageGraphWithLoops<'a> { } } -fn find_loop_backedges( - basic_coverage_blocks: &CoverageGraph, -) -> IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>> { - let num_bcbs = basic_coverage_blocks.num_nodes(); - let mut backedges = IndexVec::from_elem_n(Vec::<BasicCoverageBlock>::new(), num_bcbs); - - // Identify loops by their backedges. - for (bcb, _) in basic_coverage_blocks.iter_enumerated() { - for &successor in &basic_coverage_blocks.successors[bcb] { - if basic_coverage_blocks.dominates(successor, bcb) { - let loop_header = successor; - let backedge_from_bcb = bcb; - debug!( - "Found BCB backedge: {:?} -> loop_header: {:?}", - backedge_from_bcb, loop_header - ); - backedges[loop_header].push(backedge_from_bcb); - } - } - } - backedges -} - fn short_circuit_preorder<'a, 'tcx, F, Iter>( body: &'a mir::Body<'tcx>, filtered_successors: F, diff --git a/compiler/rustc_mir_transform/src/coverage/mappings.rs b/compiler/rustc_mir_transform/src/coverage/mappings.rs index bc86ae22a0d..2db7c6cf1d6 100644 --- a/compiler/rustc_mir_transform/src/coverage/mappings.rs +++ b/compiler/rustc_mir_transform/src/coverage/mappings.rs @@ -363,7 +363,7 @@ fn calc_test_vectors_index(conditions: &mut Vec<MCDCBranch>) -> usize { let ConditionInfo { condition_id, true_next_id, false_next_id } = branch.condition_info; [true_next_id, false_next_id] .into_iter() - .filter_map(std::convert::identity) + .flatten() .for_each(|next_id| indegree_stats[next_id] += 1); (condition_id, branch) }) diff --git a/compiler/rustc_mir_transform/src/coverage/spans.rs b/compiler/rustc_mir_transform/src/coverage/spans.rs index da7d20cf19a..085c738f1f9 100644 --- a/compiler/rustc_mir_transform/src/coverage/spans.rs +++ b/compiler/rustc_mir_transform/src/coverage/spans.rs @@ -87,7 +87,7 @@ fn remove_unwanted_expansion_spans(covspans: &mut Vec<SpanFromMir>) { covspans.retain(|covspan| { match covspan.expn_kind { // Retain only the first await-related or macro-expanded covspan with this span. - Some(ExpnKind::Desugaring(kind)) if kind == DesugaringKind::Await => { + Some(ExpnKind::Desugaring(DesugaringKind::Await)) => { deduplicated_spans.insert(covspan.span) } Some(ExpnKind::Macro(MacroKind::Bang, _)) => deduplicated_spans.insert(covspan.span), diff --git a/compiler/rustc_mir_transform/src/gvn.rs b/compiler/rustc_mir_transform/src/gvn.rs index daf868559bc..79c62372df0 100644 --- a/compiler/rustc_mir_transform/src/gvn.rs +++ b/compiler/rustc_mir_transform/src/gvn.rs @@ -288,7 +288,7 @@ impl<'body, 'tcx> VnState<'body, 'tcx> { values: FxIndexSet::with_capacity_and_hasher(num_values, Default::default()), evaluated: IndexVec::with_capacity(num_values), next_opaque: Some(1), - feature_unsized_locals: tcx.features().unsized_locals, + feature_unsized_locals: tcx.features().unsized_locals(), ssa, dominators, reused_locals: BitSet::new_empty(local_decls.len()), diff --git a/compiler/rustc_mir_transform/src/inline.rs b/compiler/rustc_mir_transform/src/inline.rs index c9f24764cc2..42d6bdf6cee 100644 --- a/compiler/rustc_mir_transform/src/inline.rs +++ b/compiler/rustc_mir_transform/src/inline.rs @@ -439,12 +439,7 @@ impl<'tcx> Inliner<'tcx> { // Reachability pass defines which functions are eligible for inlining. Generally inlining // other functions is incorrect because they could reference symbols that aren't exported. - let is_generic = callsite - .callee - .args - .non_erasable_generics(self.tcx, callsite.callee.def_id()) - .next() - .is_some(); + let is_generic = callsite.callee.args.non_erasable_generics().next().is_some(); if !is_generic && !cross_crate_inlinable { return Err("not exported"); } diff --git a/compiler/rustc_mir_transform/src/promote_consts.rs b/compiler/rustc_mir_transform/src/promote_consts.rs index 86c4b241a2b..fa9a6bfcf7c 100644 --- a/compiler/rustc_mir_transform/src/promote_consts.rs +++ b/compiler/rustc_mir_transform/src/promote_consts.rs @@ -673,7 +673,7 @@ impl<'tcx> Validator<'_, 'tcx> { } // Make sure the callee is a `const fn`. let is_const_fn = match *fn_ty.kind() { - ty::FnDef(def_id, _) => self.tcx.is_const_fn_raw(def_id), + ty::FnDef(def_id, _) => self.tcx.is_const_fn(def_id), _ => false, }; if !is_const_fn { |