Rollup merge of #136053 - Zalathar:defer-counters, r=saethlin

coverage: Defer part of counter-creation until codegen

Follow-up to #135481 and #135873.

One of the pleasant properties of the new counter-assignment algorithm is that we can stop partway through the process, store the intermediate state in MIR, and then resume the rest of the algorithm during codegen. This lets it take into account which parts of the control-flow graph were eliminated by MIR opts, resulting in fewer physical counters and simpler counter expressions.

Those improvements end up completely obsoleting much larger chunks of code that were previously responsible for cleaning up the coverage metadata after MIR opts, while also doing a more thorough cleanup job.

(That change also unlocks some further simplifications that I've kept out of this PR to limit its scope.)

1 files changed, 47 insertions, 120 deletions

diff --git a/compiler/rustc_mir_transform/src/coverage/query.rs b/compiler/rustc_mir_transform/src/coverage/query.rs
index a849ed4c3e2..cd89fbe772d 100644
--- a/compiler/rustc_mir_transform/src/coverage/query.rs
+++ b/compiler/rustc_mir_transform/src/coverage/query.rs
@@ -1,10 +1,7 @@
 use rustc_data_structures::captures::Captures;
 use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrFlags;
-use rustc_middle::mir::coverage::{
-    CounterId, CovTerm, CoverageIdsInfo, CoverageKind, Expression, ExpressionId,
-    FunctionCoverageInfo, MappingKind, Op,
-};
+use rustc_middle::mir::coverage::{BasicCoverageBlock, CoverageIdsInfo, CoverageKind, MappingKind};
 use rustc_middle::mir::{Body, Statement, StatementKind};
 use rustc_middle::ty::{self, TyCtxt};
 use rustc_middle::util::Providers;
@@ -12,6 +9,9 @@ use rustc_span::def_id::LocalDefId;
 use rustc_span::sym;
 use tracing::trace;
 
+use crate::coverage::counters::node_flow::make_node_counters;
+use crate::coverage::counters::{CoverageCounters, transcribe_counters};
+
 /// Registers query/hook implementations related to coverage.
 pub(crate) fn provide(providers: &mut Providers) {
     providers.hooks.is_eligible_for_coverage = is_eligible_for_coverage;
@@ -89,39 +89,57 @@ fn coverage_ids_info<'tcx>(
     let mir_body = tcx.instance_mir(instance_def);
     let fn_cov_info = mir_body.function_coverage_info.as_deref()?;
 
-    let mut counters_seen = DenseBitSet::new_empty(fn_cov_info.num_counters);
-    let mut expressions_seen = DenseBitSet::new_filled(fn_cov_info.expressions.len());
-
-    // For each expression ID that is directly used by one or more mappings,
-    // mark it as not-yet-seen. This indicates that we expect to see a
-    // corresponding `ExpressionUsed` statement during MIR traversal.
-    for mapping in fn_cov_info.mappings.iter() {
-        // Currently we only worry about ordinary code mappings.
-        // For branch and MC/DC mappings, expressions might not correspond
-        // to any particular point in the control-flow graph.
-        // (Keep this in sync with the injection of `ExpressionUsed`
-        // statements in the `InstrumentCoverage` MIR pass.)
-        if let MappingKind::Code(CovTerm::Expression(id)) = mapping.kind {
-            expressions_seen.remove(id);
-        }
-    }
-
+    // Scan through the final MIR to see which BCBs survived MIR opts.
+    // Any BCB not in this set was optimized away.
+    let mut bcbs_seen = DenseBitSet::new_empty(fn_cov_info.priority_list.len());
     for kind in all_coverage_in_mir_body(mir_body) {
         match *kind {
-            CoverageKind::CounterIncrement { id } => {
-                counters_seen.insert(id);
-            }
-            CoverageKind::ExpressionUsed { id } => {
-                expressions_seen.insert(id);
+            CoverageKind::VirtualCounter { bcb } => {
+                bcbs_seen.insert(bcb);
             }
             _ => {}
         }
     }
 
-    let zero_expressions =
-        identify_zero_expressions(fn_cov_info, &counters_seen, &expressions_seen);
+    // Determine the set of BCBs that are referred to by mappings, and therefore
+    // need a counter. Any node not in this set will only get a counter if it
+    // is part of the counter expression for a node that is in the set.
+    let mut bcb_needs_counter =
+        DenseBitSet::<BasicCoverageBlock>::new_empty(fn_cov_info.priority_list.len());
+    for mapping in &fn_cov_info.mappings {
+        match mapping.kind {
+            MappingKind::Code { bcb } => {
+                bcb_needs_counter.insert(bcb);
+            }
+            MappingKind::Branch { true_bcb, false_bcb } => {
+                bcb_needs_counter.insert(true_bcb);
+                bcb_needs_counter.insert(false_bcb);
+            }
+            MappingKind::MCDCBranch { true_bcb, false_bcb, mcdc_params: _ } => {
+                bcb_needs_counter.insert(true_bcb);
+                bcb_needs_counter.insert(false_bcb);
+            }
+            MappingKind::MCDCDecision(_) => {}
+        }
+    }
 
-    Some(CoverageIdsInfo { counters_seen, zero_expressions })
+    // FIXME(Zalathar): It should be possible to sort `priority_list[1..]` by
+    // `!bcbs_seen.contains(bcb)` to simplify the mappings even further, at the
+    // expense of some churn in the tests. When doing so, also consider removing
+    // the sorts in `transcribe_counters`.
+    let node_counters = make_node_counters(&fn_cov_info.node_flow_data, &fn_cov_info.priority_list);
+    let coverage_counters = transcribe_counters(&node_counters, &bcb_needs_counter, &bcbs_seen);
+
+    let CoverageCounters {
+        phys_counter_for_node, next_counter_id, node_counters, expressions, ..
+    } = coverage_counters;
+
+    Some(CoverageIdsInfo {
+        num_counters: next_counter_id.as_u32(),
+        phys_counter_for_node,
+        term_for_bcb: node_counters,
+        expressions,
+    })
 }
 
 fn all_coverage_in_mir_body<'a, 'tcx>(
@@ -139,94 +157,3 @@ fn is_inlined(body: &Body<'_>, statement: &Statement<'_>) -> bool {
     let scope_data = &body.source_scopes[statement.source_info.scope];
     scope_data.inlined.is_some() || scope_data.inlined_parent_scope.is_some()
 }
-
-/// Identify expressions that will always have a value of zero, and note their
-/// IDs in a `DenseBitSet`. Mappings that refer to a zero expression can instead
-/// become mappings to a constant zero value.
-///
-/// This function mainly exists to preserve the simplifications that were
-/// already being performed by the Rust-side expression renumbering, so that
-/// the resulting coverage mappings don't get worse.
-fn identify_zero_expressions(
-    fn_cov_info: &FunctionCoverageInfo,
-    counters_seen: &DenseBitSet<CounterId>,
-    expressions_seen: &DenseBitSet<ExpressionId>,
-) -> DenseBitSet<ExpressionId> {
-    // The set of expressions that either were optimized out entirely, or
-    // have zero as both of their operands, and will therefore always have
-    // a value of zero. Other expressions that refer to these as operands
-    // can have those operands replaced with `CovTerm::Zero`.
-    let mut zero_expressions = DenseBitSet::new_empty(fn_cov_info.expressions.len());
-
-    // Simplify a copy of each expression based on lower-numbered expressions,
-    // and then update the set of always-zero expressions if necessary.
-    // (By construction, expressions can only refer to other expressions
-    // that have lower IDs, so one pass is sufficient.)
-    for (id, expression) in fn_cov_info.expressions.iter_enumerated() {
-        if !expressions_seen.contains(id) {
-            // If an expression was not seen, it must have been optimized away,
-            // so any operand that refers to it can be replaced with zero.
-            zero_expressions.insert(id);
-            continue;
-        }
-
-        // We don't need to simplify the actual expression data in the
-        // expressions list; we can just simplify a temporary copy and then
-        // use that to update the set of always-zero expressions.
-        let Expression { mut lhs, op, mut rhs } = *expression;
-
-        // If an expression has an operand that is also an expression, the
-        // operand's ID must be strictly lower. This is what lets us find
-        // all zero expressions in one pass.
-        let assert_operand_expression_is_lower = |operand_id: ExpressionId| {
-            assert!(
-                operand_id < id,
-                "Operand {operand_id:?} should be less than {id:?} in {expression:?}",
-            )
-        };
-
-        // If an operand refers to a counter or expression that is always
-        // zero, then that operand can be replaced with `CovTerm::Zero`.
-        let maybe_set_operand_to_zero = |operand: &mut CovTerm| {
-            if let CovTerm::Expression(id) = *operand {
-                assert_operand_expression_is_lower(id);
-            }
-
-            if is_zero_term(&counters_seen, &zero_expressions, *operand) {
-                *operand = CovTerm::Zero;
-            }
-        };
-        maybe_set_operand_to_zero(&mut lhs);
-        maybe_set_operand_to_zero(&mut rhs);
-
-        // Coverage counter values cannot be negative, so if an expression
-        // involves subtraction from zero, assume that its RHS must also be zero.
-        // (Do this after simplifications that could set the LHS to zero.)
-        if lhs == CovTerm::Zero && op == Op::Subtract {
-            rhs = CovTerm::Zero;
-        }
-
-        // After the above simplifications, if both operands are zero, then
-        // we know that this expression is always zero too.
-        if lhs == CovTerm::Zero && rhs == CovTerm::Zero {
-            zero_expressions.insert(id);
-        }
-    }
-
-    zero_expressions
-}
-
-/// Returns `true` if the given term is known to have a value of zero, taking
-/// into account knowledge of which counters are unused and which expressions
-/// are always zero.
-fn is_zero_term(
-    counters_seen: &DenseBitSet<CounterId>,
-    zero_expressions: &DenseBitSet<ExpressionId>,
-    term: CovTerm,
-) -> bool {
-    match term {
-        CovTerm::Zero => true,
-        CovTerm::Counter(id) => !counters_seen.contains(id),
-        CovTerm::Expression(id) => zero_expressions.contains(id),
-    }
-}