diff options
Diffstat (limited to 'compiler/rustc_mir_transform/src/coverage/counters.rs')
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/counters.rs | 374 |
1 files changed, 230 insertions, 144 deletions
diff --git a/compiler/rustc_mir_transform/src/coverage/counters.rs b/compiler/rustc_mir_transform/src/coverage/counters.rs index cf9f6981c5a..46efdd16ee8 100644 --- a/compiler/rustc_mir_transform/src/coverage/counters.rs +++ b/compiler/rustc_mir_transform/src/coverage/counters.rs @@ -1,3 +1,4 @@ +use std::cmp::Ordering; use std::fmt::{self, Debug}; use rustc_data_structures::captures::Captures; @@ -10,9 +11,12 @@ use tracing::{debug, debug_span, instrument}; use crate::coverage::graph::{BasicCoverageBlock, CoverageGraph, TraverseCoverageGraphWithLoops}; +#[cfg(test)] +mod tests; + /// The coverage counter or counter expression associated with a particular /// BCB node or BCB edge. -#[derive(Clone, Copy, PartialEq, Eq, Hash)] +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] enum BcbCounter { Counter { id: CounterId }, Expression { id: ExpressionId }, @@ -43,8 +47,9 @@ struct BcbExpression { rhs: BcbCounter, } -#[derive(Debug)] -pub(super) enum CounterIncrementSite { +/// Enum representing either a node or an edge in the coverage graph. +#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub(super) enum Site { Node { bcb: BasicCoverageBlock }, Edge { from_bcb: BasicCoverageBlock, to_bcb: BasicCoverageBlock }, } @@ -54,16 +59,10 @@ pub(super) enum CounterIncrementSite { pub(super) struct CoverageCounters { /// List of places where a counter-increment statement should be injected /// into MIR, each with its corresponding counter ID. - counter_increment_sites: IndexVec<CounterId, CounterIncrementSite>, + counter_increment_sites: IndexVec<CounterId, Site>, /// Coverage counters/expressions that are associated with individual BCBs. 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. - edge_counters: FxHashMap<(BasicCoverageBlock, BasicCoverageBlock), BcbCounter>, /// Table of expression data, associating each expression ID with its /// corresponding operator (+ or -) and its LHS/RHS operands. @@ -83,93 +82,30 @@ impl CoverageCounters { let mut builder = CountersBuilder::new(graph, bcb_needs_counter); builder.make_bcb_counters(); - builder.counters + builder.into_coverage_counters() } fn with_num_bcbs(num_bcbs: usize) -> Self { Self { counter_increment_sites: IndexVec::new(), node_counters: IndexVec::from_elem_n(None, num_bcbs), - edge_counters: FxHashMap::default(), expressions: IndexVec::new(), expressions_memo: FxHashMap::default(), } } - /// Shared helper used by [`Self::make_phys_node_counter`] and - /// [`Self::make_phys_edge_counter`]. Don't call this directly. - fn make_counter_inner(&mut self, site: CounterIncrementSite) -> BcbCounter { + /// Creates a new physical counter for a BCB node or edge. + fn make_phys_counter(&mut self, site: Site) -> BcbCounter { let id = self.counter_increment_sites.push(site); BcbCounter::Counter { id } } - /// Creates a new physical counter for a BCB node. - fn make_phys_node_counter(&mut self, bcb: BasicCoverageBlock) -> BcbCounter { - self.make_counter_inner(CounterIncrementSite::Node { bcb }) - } - - /// Creates a new physical counter for a BCB edge. - fn make_phys_edge_counter( - &mut self, - from_bcb: BasicCoverageBlock, - to_bcb: BasicCoverageBlock, - ) -> BcbCounter { - self.make_counter_inner(CounterIncrementSite::Edge { from_bcb, to_bcb }) - } - fn make_expression(&mut self, lhs: BcbCounter, op: Op, rhs: BcbCounter) -> BcbCounter { let new_expr = BcbExpression { lhs, op, rhs }; - *self - .expressions_memo - .entry(new_expr) - .or_insert_with(|| Self::make_expression_inner(&mut self.expressions, new_expr)) - } - - /// This is an associated function so that we can call it while borrowing - /// `&mut self.expressions_memo`. - fn make_expression_inner( - expressions: &mut IndexVec<ExpressionId, BcbExpression>, - new_expr: BcbExpression, - ) -> BcbCounter { - // Simplify expressions using basic algebra. - // - // Some of these cases might not actually occur in practice, depending - // on the details of how the instrumentor builds expressions. - let BcbExpression { lhs, op, rhs } = new_expr; - - if let BcbCounter::Expression { id } = lhs { - let lhs_expr = &expressions[id]; - - // Simplify `(a - b) + b` to `a`. - if lhs_expr.op == Op::Subtract && op == Op::Add && lhs_expr.rhs == rhs { - return lhs_expr.lhs; - } - // Simplify `(a + b) - b` to `a`. - if lhs_expr.op == Op::Add && op == Op::Subtract && lhs_expr.rhs == rhs { - return lhs_expr.lhs; - } - // Simplify `(a + b) - a` to `b`. - if lhs_expr.op == Op::Add && op == Op::Subtract && lhs_expr.lhs == rhs { - return lhs_expr.rhs; - } - } - - if let BcbCounter::Expression { id } = rhs { - let rhs_expr = &expressions[id]; - - // Simplify `a + (b - a)` to `b`. - if op == Op::Add && rhs_expr.op == Op::Subtract && lhs == rhs_expr.rhs { - return rhs_expr.lhs; - } - // Simplify `a - (a - b)` to `b`. - if op == Op::Subtract && rhs_expr.op == Op::Subtract && lhs == rhs_expr.lhs { - return rhs_expr.rhs; - } - } - - // Simplification failed, so actually create the new expression. - let id = expressions.push(new_expr); - BcbCounter::Expression { id } + *self.expressions_memo.entry(new_expr).or_insert_with(|| { + let id = self.expressions.push(new_expr); + BcbCounter::Expression { id } + }) } /// Creates a counter that is the sum of the given counters. @@ -182,6 +118,12 @@ impl CoverageCounters { .reduce(|accum, counter| self.make_expression(accum, Op::Add, counter)) } + /// Creates a counter whose value is `lhs - SUM(rhs)`. + fn make_subtracted_sum(&mut self, lhs: BcbCounter, rhs: &[BcbCounter]) -> BcbCounter { + let Some(rhs_sum) = self.make_sum(rhs) else { return lhs }; + self.make_expression(lhs, Op::Subtract, rhs_sum) + } + pub(super) fn num_counters(&self) -> usize { self.counter_increment_sites.len() } @@ -195,20 +137,6 @@ impl CoverageCounters { counter } - fn set_edge_counter( - &mut self, - from_bcb: BasicCoverageBlock, - to_bcb: BasicCoverageBlock, - counter: BcbCounter, - ) -> BcbCounter { - 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.node_counters[bcb].map(|counter| counter.as_term()) } @@ -218,8 +146,8 @@ impl CoverageCounters { /// each site's corresponding counter ID. pub(super) fn counter_increment_sites( &self, - ) -> impl Iterator<Item = (CounterId, &CounterIncrementSite)> { - self.counter_increment_sites.iter_enumerated() + ) -> impl Iterator<Item = (CounterId, Site)> + Captures<'_> { + self.counter_increment_sites.iter_enumerated().map(|(id, &site)| (id, site)) } /// Returns an iterator over the subset of BCB nodes that have been associated @@ -254,22 +182,53 @@ impl CoverageCounters { } } +/// Symbolic representation of the coverage counter to be used for a particular +/// node or edge in the coverage graph. The same site counter can be used for +/// multiple sites, if they have been determined to have the same count. +#[derive(Clone, Copy, Debug)] +enum SiteCounter { + /// A physical counter at some node/edge. + Phys { site: Site }, + /// A counter expression for a node that takes the sum of all its in-edge + /// counters. + NodeSumExpr { bcb: BasicCoverageBlock }, + /// A counter expression for an edge that takes the counter of its source + /// node, and subtracts the counters of all its sibling out-edges. + EdgeDiffExpr { from_bcb: BasicCoverageBlock, to_bcb: BasicCoverageBlock }, +} + +/// Yields the graph successors of `from_bcb` that aren't `to_bcb`. This is +/// used when creating a counter expression for [`SiteCounter::EdgeDiffExpr`]. +/// +/// For example, in this diagram the sibling out-edge targets of edge `AC` are +/// the nodes `B` and `D`. +/// +/// ```text +/// A +/// / | \ +/// B C D +/// ``` +fn sibling_out_edge_targets( + graph: &CoverageGraph, + from_bcb: BasicCoverageBlock, + to_bcb: BasicCoverageBlock, +) -> impl Iterator<Item = BasicCoverageBlock> + Captures<'_> { + graph.successors[from_bcb].iter().copied().filter(move |&t| t != to_bcb) +} + /// 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>, + + site_counters: FxHashMap<Site, SiteCounter>, } 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 { - counters: CoverageCounters::with_num_bcbs(graph.num_nodes()), - graph, - bcb_needs_counter, - } + Self { graph, bcb_needs_counter, site_counters: FxHashMap::default() } } fn make_bcb_counters(&mut self) { @@ -302,9 +261,7 @@ impl<'a> CountersBuilder<'a> { 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.graph.successors[from_bcb].as_slice(); + self.get_or_make_node_counter(from_bcb); // If this node's out-edges won't sum to the node's counter, // then there's no reason to create edge counters here. @@ -315,11 +272,11 @@ impl<'a> CountersBuilder<'a> { // 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)) { + if self.site_counters.contains_key(&Site::Edge { from_bcb, to_bcb }) { return true; } self.graph.sole_predecessor(to_bcb) == Some(from_bcb) - && self.counters.node_counters[to_bcb].is_some() + && self.site_counters.contains_key(&Site::Node { bcb: to_bcb }) }; // Determine the set of out-edges that could benefit from being given an expression. @@ -332,51 +289,41 @@ impl<'a> CountersBuilder<'a> { // 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(target_bcb) = self.choose_out_edge_for_expression(from_bcb, &candidate_successors) + let Some(to_bcb) = self.choose_out_edge_for_expression(from_bcb, &candidate_successors) else { return; }; // For each out-edge 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 counters into a single sum expression. - let other_out_edge_counters = successors - .iter() - .copied() - // Skip the chosen edge, since we'll calculate its count from this sum. - .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.counters.make_sum(&other_out_edge_counters) - else { - return; - }; + // ensure that it has a counter (existing counter/expression or a new counter). + for target in sibling_out_edge_targets(self.graph, from_bcb, to_bcb) { + self.get_or_make_edge_counter(from_bcb, target); + } // 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.counters.make_expression(node_counter, Op::Subtract, sum_of_all_other_out_edges); - - debug!("{target_bcb:?} gets an expression: {expression:?}"); - self.counters.set_edge_counter(from_bcb, target_bcb, expression); + let counter = SiteCounter::EdgeDiffExpr { from_bcb, to_bcb }; + self.site_counters.insert(Site::Edge { from_bcb, to_bcb }, counter); } #[instrument(level = "debug", skip(self))] - fn get_or_make_node_counter(&mut self, bcb: BasicCoverageBlock) -> BcbCounter { + fn get_or_make_node_counter(&mut self, bcb: BasicCoverageBlock) -> SiteCounter { // If the BCB already has a counter, return it. - if let Some(counter) = self.counters.node_counters[bcb] { + if let Some(&counter) = self.site_counters.get(&Site::Node { 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) + self.site_counters.insert(Site::Node { bcb }, counter); + counter } - fn make_node_counter_inner(&mut self, bcb: BasicCoverageBlock) -> BcbCounter { + fn make_node_counter_inner(&mut self, bcb: BasicCoverageBlock) -> SiteCounter { // 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)) + && let Some(&edge_counter) = + self.site_counters.get(&Site::Edge { from_bcb: sole_pred, to_bcb: bcb }) { return edge_counter; } @@ -390,20 +337,17 @@ impl<'a> CountersBuilder<'a> { // leading to infinite recursion. if predecessors.len() <= 1 || predecessors.contains(&bcb) { debug!(?bcb, ?predecessors, "node has <=1 predecessors or is its own predecessor"); - let counter = self.counters.make_phys_node_counter(bcb); + let counter = SiteCounter::Phys { site: Site::Node { 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 // exist for each of those edges, and then adding them up to get a total count. - let in_edge_counters = predecessors - .iter() - .copied() - .map(|from_bcb| self.get_or_make_edge_counter(from_bcb, bcb)) - .collect::<Vec<_>>(); - let sum_of_in_edges: BcbCounter = - self.counters.make_sum(&in_edge_counters).expect("there must be at least one in-edge"); + for &from_bcb in predecessors { + self.get_or_make_edge_counter(from_bcb, bcb); + } + let sum_of_in_edges = SiteCounter::NodeSumExpr { bcb }; debug!("{bcb:?} gets a new counter (sum of predecessor counters): {sum_of_in_edges:?}"); sum_of_in_edges @@ -414,22 +358,23 @@ impl<'a> CountersBuilder<'a> { &mut self, from_bcb: BasicCoverageBlock, to_bcb: BasicCoverageBlock, - ) -> BcbCounter { + ) -> SiteCounter { // If the edge already has a counter, return it. - if let Some(&counter) = self.counters.edge_counters.get(&(from_bcb, to_bcb)) { + if let Some(&counter) = self.site_counters.get(&Site::Edge { 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) + self.site_counters.insert(Site::Edge { from_bcb, to_bcb }, counter); + counter } fn make_edge_counter_inner( &mut self, from_bcb: BasicCoverageBlock, to_bcb: BasicCoverageBlock, - ) -> BcbCounter { + ) -> SiteCounter { // 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.graph.sole_predecessor(to_bcb) { @@ -447,7 +392,7 @@ impl<'a> CountersBuilder<'a> { } // Make a new counter to count this edge. - let counter = self.counters.make_phys_edge_counter(from_bcb, to_bcb); + let counter = SiteCounter::Phys { site: Site::Edge { from_bcb, to_bcb } }; debug!(?from_bcb, ?to_bcb, ?counter, "edge gets a physical counter"); counter } @@ -510,4 +455,145 @@ impl<'a> CountersBuilder<'a> { None } + + fn into_coverage_counters(self) -> CoverageCounters { + Transcriber::new(&self).transcribe_counters() + } +} + +/// Helper struct for converting `CountersBuilder` into a final `CoverageCounters`. +struct Transcriber<'a> { + old: &'a CountersBuilder<'a>, + new: CoverageCounters, + phys_counter_for_site: FxHashMap<Site, BcbCounter>, +} + +impl<'a> Transcriber<'a> { + fn new(old: &'a CountersBuilder<'a>) -> Self { + Self { + old, + new: CoverageCounters::with_num_bcbs(old.graph.num_nodes()), + phys_counter_for_site: FxHashMap::default(), + } + } + + fn transcribe_counters(mut self) -> CoverageCounters { + for bcb in self.old.bcb_needs_counter.iter() { + let site = Site::Node { bcb }; + let site_counter = self.site_counter(site); + + // Resolve the site counter into flat lists of nodes/edges whose + // physical counts contribute to the counter for this node. + // Distinguish between counts that will be added vs subtracted. + let mut pos = vec![]; + let mut neg = vec![]; + self.push_resolved_sites(site_counter, &mut pos, &mut neg); + + // Simplify by cancelling out sites that appear on both sides. + let (mut pos, mut neg) = sort_and_cancel(pos, neg); + + if pos.is_empty() { + // If we somehow end up with no positive terms after cancellation, + // fall back to creating a physical counter. There's no known way + // for this to happen, but it's hard to confidently rule it out. + debug_assert!(false, "{site:?} has no positive counter terms"); + pos = vec![Some(site)]; + neg = vec![]; + } + + let mut new_counters_for_sites = |sites: Vec<Option<Site>>| { + sites + .into_iter() + .filter_map(|id| try { self.ensure_phys_counter(id?) }) + .collect::<Vec<_>>() + }; + let mut pos = new_counters_for_sites(pos); + let mut neg = new_counters_for_sites(neg); + + pos.sort(); + neg.sort(); + + let pos_counter = self.new.make_sum(&pos).expect("`pos` should not be empty"); + let new_counter = self.new.make_subtracted_sum(pos_counter, &neg); + self.new.set_node_counter(bcb, new_counter); + } + + self.new + } + + fn site_counter(&self, site: Site) -> SiteCounter { + self.old.site_counters.get(&site).copied().unwrap_or_else(|| { + // We should have already created all necessary site counters. + // But if we somehow didn't, avoid crashing in release builds, + // and just use an extra physical counter instead. + debug_assert!(false, "{site:?} should have a counter"); + SiteCounter::Phys { site } + }) + } + + fn ensure_phys_counter(&mut self, site: Site) -> BcbCounter { + *self.phys_counter_for_site.entry(site).or_insert_with(|| self.new.make_phys_counter(site)) + } + + /// Resolves the given counter into flat lists of nodes/edges, whose counters + /// will then be added and subtracted to form a counter expression. + fn push_resolved_sites(&self, counter: SiteCounter, pos: &mut Vec<Site>, neg: &mut Vec<Site>) { + match counter { + SiteCounter::Phys { site } => pos.push(site), + SiteCounter::NodeSumExpr { bcb } => { + for &from_bcb in &self.old.graph.predecessors[bcb] { + let edge_counter = self.site_counter(Site::Edge { from_bcb, to_bcb: bcb }); + self.push_resolved_sites(edge_counter, pos, neg); + } + } + SiteCounter::EdgeDiffExpr { from_bcb, to_bcb } => { + // First, add the count for `from_bcb`. + let node_counter = self.site_counter(Site::Node { bcb: from_bcb }); + self.push_resolved_sites(node_counter, pos, neg); + + // Then subtract the counts for the other out-edges. + for target in sibling_out_edge_targets(self.old.graph, from_bcb, to_bcb) { + let edge_counter = self.site_counter(Site::Edge { from_bcb, to_bcb: target }); + // Swap `neg` and `pos` so that the counter is subtracted. + self.push_resolved_sites(edge_counter, neg, pos); + } + } + } + } +} + +/// Given two lists: +/// - Sorts each list. +/// - Converts each list to `Vec<Option<T>>`. +/// - Scans for values that appear in both lists, and cancels them out by +/// replacing matching pairs of values with `None`. +fn sort_and_cancel<T: Ord>(mut pos: Vec<T>, mut neg: Vec<T>) -> (Vec<Option<T>>, Vec<Option<T>>) { + pos.sort(); + neg.sort(); + + // Convert to `Vec<Option<T>>`. If `T` has a niche, this should be zero-cost. + let mut pos = pos.into_iter().map(Some).collect::<Vec<_>>(); + let mut neg = neg.into_iter().map(Some).collect::<Vec<_>>(); + + // Scan through the lists using two cursors. When either cursor reaches the + // end of its list, there can be no more equal pairs, so stop. + let mut p = 0; + let mut n = 0; + while p < pos.len() && n < neg.len() { + // If the values are equal, remove them and advance both cursors. + // Otherwise, advance whichever cursor points to the lesser value. + // (Choosing which cursor to advance relies on both lists being sorted.) + match pos[p].cmp(&neg[n]) { + Ordering::Less => p += 1, + Ordering::Equal => { + pos[p] = None; + neg[n] = None; + p += 1; + n += 1; + } + Ordering::Greater => n += 1, + } + } + + (pos, neg) } |