Rollup merge of #134029 - Zalathar:zero, r=oli-obk

coverage: Use a query to find counters/expressions that must be zero

As of #133446, this query (`coverage_ids_info`) determines which counter/expression IDs are unused. So with only a little extra work, we can take the code that was using that information to determine which coverage counters/expressions must be zero, and move that inside the query as well.

There should be no change in compiler output.

7 files changed, 169 insertions, 223 deletions

diff --git a/compiler/rustc_codegen_llvm/src/coverageinfo/map_data.rs b/compiler/rustc_codegen_llvm/src/coverageinfo/map_data.rs
index 0752c718c70..c5d1ebdfe7c 100644
--- a/compiler/rustc_codegen_llvm/src/coverageinfo/map_data.rs
+++ b/compiler/rustc_codegen_llvm/src/coverageinfo/map_data.rs
@@ -1,159 +1,38 @@
 use rustc_data_structures::captures::Captures;
-use rustc_data_structures::fx::FxIndexSet;
-use rustc_index::bit_set::BitSet;
-use rustc_middle::mir::CoverageIdsInfo;
 use rustc_middle::mir::coverage::{
-    CounterId, CovTerm, Expression, ExpressionId, FunctionCoverageInfo, Mapping, MappingKind, Op,
+    CovTerm, CoverageIdsInfo, Expression, FunctionCoverageInfo, Mapping, MappingKind, Op,
     SourceRegion,
 };
-use rustc_middle::ty::Instance;
-use tracing::debug;
 
 use crate::coverageinfo::ffi::{Counter, CounterExpression, ExprKind};
 
-/// Holds all of the coverage mapping data associated with a function instance,
-/// collected during traversal of `Coverage` statements in the function's MIR.
-#[derive(Debug)]
-pub(crate) struct FunctionCoverageCollector<'tcx> {
-    /// Coverage info that was attached to this function by the instrumentor.
-    function_coverage_info: &'tcx FunctionCoverageInfo,
-    ids_info: &'tcx CoverageIdsInfo,
-    is_used: bool,
+pub(crate) struct FunctionCoverage<'tcx> {
+    pub(crate) function_coverage_info: &'tcx FunctionCoverageInfo,
+    /// If `None`, the corresponding function is unused.
+    ids_info: Option<&'tcx CoverageIdsInfo>,
 }
 
-impl<'tcx> FunctionCoverageCollector<'tcx> {
-    /// Creates a new set of coverage data for a used (called) function.
-    pub(crate) fn new(
-        instance: Instance<'tcx>,
-        function_coverage_info: &'tcx FunctionCoverageInfo,
-        ids_info: &'tcx CoverageIdsInfo,
-    ) -> Self {
-        Self::create(instance, function_coverage_info, ids_info, true)
-    }
-
-    /// Creates a new set of coverage data for an unused (never called) function.
-    pub(crate) fn unused(
-        instance: Instance<'tcx>,
-        function_coverage_info: &'tcx FunctionCoverageInfo,
-        ids_info: &'tcx CoverageIdsInfo,
-    ) -> Self {
-        Self::create(instance, function_coverage_info, ids_info, false)
-    }
-
-    fn create(
-        instance: Instance<'tcx>,
+impl<'tcx> FunctionCoverage<'tcx> {
+    pub(crate) fn new_used(
         function_coverage_info: &'tcx FunctionCoverageInfo,
         ids_info: &'tcx CoverageIdsInfo,
-        is_used: bool,
     ) -> Self {
-        let num_counters = function_coverage_info.num_counters;
-        let num_expressions = function_coverage_info.expressions.len();
-        debug!(
-            "FunctionCoverage::create(instance={instance:?}) has \
-            num_counters={num_counters}, num_expressions={num_expressions}, is_used={is_used}"
-        );
-
-        Self { function_coverage_info, ids_info, is_used }
-    }
-
-    /// Identify expressions that will always have a value of zero, and note
-    /// their IDs in [`ZeroExpressions`]. Mappings that refer to a zero expression
-    /// can instead become mappings to a constant zero value.
-    ///
-    /// This method 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(&self) -> ZeroExpressions {
-        // 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 = ZeroExpressions::default();
-
-        // 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 self.function_coverage_info.expressions.iter_enumerated() {
-            if !self.is_used || !self.ids_info.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(&self.ids_info.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
+        Self { function_coverage_info, ids_info: Some(ids_info) }
     }
 
-    pub(crate) fn into_finished(self) -> FunctionCoverage<'tcx> {
-        let zero_expressions = self.identify_zero_expressions();
-        let FunctionCoverageCollector { function_coverage_info, ids_info, is_used, .. } = self;
-
-        FunctionCoverage { function_coverage_info, ids_info, is_used, zero_expressions }
+    pub(crate) fn new_unused(function_coverage_info: &'tcx FunctionCoverageInfo) -> Self {
+        Self { function_coverage_info, ids_info: None }
     }
-}
-
-pub(crate) struct FunctionCoverage<'tcx> {
-    pub(crate) function_coverage_info: &'tcx FunctionCoverageInfo,
-    ids_info: &'tcx CoverageIdsInfo,
-    is_used: bool,
-
-    zero_expressions: ZeroExpressions,
-}
 
-impl<'tcx> FunctionCoverage<'tcx> {
     /// Returns true for a used (called) function, and false for an unused function.
     pub(crate) fn is_used(&self) -> bool {
-        self.is_used
+        self.ids_info.is_some()
     }
 
     /// Return the source hash, generated from the HIR node structure, and used to indicate whether
     /// or not the source code structure changed between different compilations.
     pub(crate) fn source_hash(&self) -> u64 {
-        if self.is_used { self.function_coverage_info.function_source_hash } else { 0 }
+        if self.is_used() { self.function_coverage_info.function_source_hash } else { 0 }
     }
 
     /// Convert this function's coverage expression data into a form that can be
@@ -196,37 +75,10 @@ impl<'tcx> FunctionCoverage<'tcx> {
     }
 
     fn is_zero_term(&self, term: CovTerm) -> bool {
-        !self.is_used || is_zero_term(&self.ids_info.counters_seen, &self.zero_expressions, term)
-    }
-}
-
-/// Set of expression IDs that are known to always evaluate to zero.
-/// Any mapping or expression operand that refers to these expressions can have
-/// that reference replaced with a constant zero value.
-#[derive(Default)]
-struct ZeroExpressions(FxIndexSet<ExpressionId>);
-
-impl ZeroExpressions {
-    fn insert(&mut self, id: ExpressionId) {
-        self.0.insert(id);
-    }
-
-    fn contains(&self, id: ExpressionId) -> bool {
-        self.0.contains(&id)
-    }
-}
-
-/// 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: &BitSet<CounterId>,
-    zero_expressions: &ZeroExpressions,
-    term: CovTerm,
-) -> bool {
-    match term {
-        CovTerm::Zero => true,
-        CovTerm::Counter(id) => !counters_seen.contains(id),
-        CovTerm::Expression(id) => zero_expressions.contains(id),
+        match self.ids_info {
+            Some(ids_info) => ids_info.is_zero_term(term),
+            // This function is unused, so all coverage counters/expressions are zero.
+            None => true,
+        }
     }
 }
diff --git a/compiler/rustc_codegen_llvm/src/coverageinfo/mapgen.rs b/compiler/rustc_codegen_llvm/src/coverageinfo/mapgen.rs
index 8c24579fa7c..a6c3caf9e2b 100644
--- a/compiler/rustc_codegen_llvm/src/coverageinfo/mapgen.rs
+++ b/compiler/rustc_codegen_llvm/src/coverageinfo/mapgen.rs
@@ -20,7 +20,7 @@ use rustc_target::spec::HasTargetSpec;
 use tracing::debug;
 
 use crate::common::CodegenCx;
-use crate::coverageinfo::map_data::{FunctionCoverage, FunctionCoverageCollector};
+use crate::coverageinfo::map_data::FunctionCoverage;
 use crate::coverageinfo::{ffi, llvm_cov};
 use crate::llvm;
 
@@ -63,16 +63,11 @@ pub(crate) fn finalize(cx: &CodegenCx<'_, '_>) {
         None => return,
     };
     if function_coverage_map.is_empty() {
-        // This module has no functions with coverage instrumentation
+        // This CGU has no functions with coverage instrumentation.
         return;
     }
 
-    let function_coverage_entries = function_coverage_map
-        .into_iter()
-        .map(|(instance, function_coverage)| (instance, function_coverage.into_finished()))
-        .collect::<Vec<_>>();
-
-    let all_file_names = function_coverage_entries
+    let all_file_names = function_coverage_map
         .iter()
         .map(|(_, fn_cov)| fn_cov.function_coverage_info.body_span)
         .map(|span| span_file_name(tcx, span));
@@ -92,7 +87,7 @@ pub(crate) fn finalize(cx: &CodegenCx<'_, '_>) {
     let mut unused_function_names = Vec::new();
 
     // Encode coverage mappings and generate function records
-    for (instance, function_coverage) in function_coverage_entries {
+    for (instance, function_coverage) in function_coverage_map {
         debug!("Generate function coverage for {}, {:?}", cx.codegen_unit.name(), instance);
 
         let mangled_function_name = tcx.symbol_name(instance).name;
@@ -536,11 +531,6 @@ fn add_unused_function_coverage<'tcx>(
     );
 
     // An unused function's mappings will all be rewritten to map to zero.
-    let function_coverage = FunctionCoverageCollector::unused(
-        instance,
-        function_coverage_info,
-        tcx.coverage_ids_info(instance.def),
-    );
-
+    let function_coverage = FunctionCoverage::new_unused(function_coverage_info);
     cx.coverage_cx().function_coverage_map.borrow_mut().insert(instance, function_coverage);
 }
diff --git a/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs b/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
index c2fcb33f98b..82b6677e203 100644
--- a/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
+++ b/compiler/rustc_codegen_llvm/src/coverageinfo/mod.rs
@@ -13,7 +13,7 @@ use tracing::{debug, instrument};
 
 use crate::builder::Builder;
 use crate::common::CodegenCx;
-use crate::coverageinfo::map_data::FunctionCoverageCollector;
+use crate::coverageinfo::map_data::FunctionCoverage;
 use crate::llvm;
 
 pub(crate) mod ffi;
@@ -24,8 +24,7 @@ mod mapgen;
 /// Extra per-CGU context/state needed for coverage instrumentation.
 pub(crate) struct CguCoverageContext<'ll, 'tcx> {
     /// Coverage data for each instrumented function identified by DefId.
-    pub(crate) function_coverage_map:
-        RefCell<FxIndexMap<Instance<'tcx>, FunctionCoverageCollector<'tcx>>>,
+    pub(crate) function_coverage_map: RefCell<FxIndexMap<Instance<'tcx>, FunctionCoverage<'tcx>>>,
     pub(crate) pgo_func_name_var_map: RefCell<FxHashMap<Instance<'tcx>, &'ll llvm::Value>>,
     pub(crate) mcdc_condition_bitmap_map: RefCell<FxHashMap<Instance<'tcx>, Vec<&'ll llvm::Value>>>,
 
@@ -42,9 +41,7 @@ impl<'ll, 'tcx> CguCoverageContext<'ll, 'tcx> {
         }
     }
 
-    fn take_function_coverage_map(
-        &self,
-    ) -> FxIndexMap<Instance<'tcx>, FunctionCoverageCollector<'tcx>> {
+    fn take_function_coverage_map(&self) -> FxIndexMap<Instance<'tcx>, FunctionCoverage<'tcx>> {
         self.function_coverage_map.replace(FxIndexMap::default())
     }
 
@@ -161,8 +158,7 @@ impl<'tcx> CoverageInfoBuilderMethods<'tcx> for Builder<'_, '_, 'tcx> {
         // This includes functions that were not partitioned into this CGU,
         // but were MIR-inlined into one of this CGU's functions.
         coverage_cx.function_coverage_map.borrow_mut().entry(instance).or_insert_with(|| {
-            FunctionCoverageCollector::new(
-                instance,
+            FunctionCoverage::new_used(
                 function_coverage_info,
                 bx.tcx.coverage_ids_info(instance.def),
             )
diff --git a/compiler/rustc_middle/src/mir/coverage.rs b/compiler/rustc_middle/src/mir/coverage.rs
index b7410ca5f18..962176290df 100644
--- a/compiler/rustc_middle/src/mir/coverage.rs
+++ b/compiler/rustc_middle/src/mir/coverage.rs
@@ -3,6 +3,7 @@
 use std::fmt::{self, Debug, Formatter};
 
 use rustc_index::IndexVec;
+use rustc_index::bit_set::BitSet;
 use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable};
 use rustc_span::Span;
 
@@ -310,3 +311,41 @@ pub struct MCDCDecisionSpan {
     pub decision_depth: u16,
     pub num_conditions: usize,
 }
+
+/// Summarizes coverage IDs inserted by the `InstrumentCoverage` MIR pass
+/// (for compiler option `-Cinstrument-coverage`), after MIR optimizations
+/// have had a chance to potentially remove some of them.
+///
+/// Used by the `coverage_ids_info` query.
+#[derive(Clone, TyEncodable, TyDecodable, Debug, HashStable)]
+pub struct CoverageIdsInfo {
+    pub counters_seen: BitSet<CounterId>,
+    pub zero_expressions: BitSet<ExpressionId>,
+}
+
+impl CoverageIdsInfo {
+    /// Coverage codegen needs to know how many coverage counters are ever
+    /// incremented within a function, so that it can set the `num-counters`
+    /// argument of the `llvm.instrprof.increment` intrinsic.
+    ///
+    /// This may be less than the highest counter ID emitted by the
+    /// InstrumentCoverage MIR pass, if the highest-numbered counter increments
+    /// were removed by MIR optimizations.
+    pub fn num_counters_after_mir_opts(&self) -> u32 {
+        // FIXME(Zalathar): Currently this treats an unused counter as "used"
+        // if its ID is less than that of the highest counter that really is
+        // used. Fixing this would require adding a renumbering step somewhere.
+        self.counters_seen.last_set_in(..).map_or(0, |max| max.as_u32() + 1)
+    }
+
+    /// 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.
+    pub fn is_zero_term(&self, term: CovTerm) -> bool {
+        match term {
+            CovTerm::Zero => true,
+            CovTerm::Counter(id) => !self.counters_seen.contains(id),
+            CovTerm::Expression(id) => self.zero_expressions.contains(id),
+        }
+    }
+}
diff --git a/compiler/rustc_middle/src/mir/query.rs b/compiler/rustc_middle/src/mir/query.rs
index 80dfcbf2e69..f690359e012 100644
--- a/compiler/rustc_middle/src/mir/query.rs
+++ b/compiler/rustc_middle/src/mir/query.rs
@@ -8,7 +8,7 @@ use rustc_abi::{FieldIdx, VariantIdx};
 use rustc_data_structures::fx::FxIndexMap;
 use rustc_errors::ErrorGuaranteed;
 use rustc_hir::def_id::LocalDefId;
-use rustc_index::bit_set::{BitMatrix, BitSet};
+use rustc_index::bit_set::BitMatrix;
 use rustc_index::{Idx, IndexVec};
 use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable};
 use rustc_span::Span;
@@ -16,7 +16,6 @@ use rustc_span::symbol::Symbol;
 use smallvec::SmallVec;
 
 use super::{ConstValue, SourceInfo};
-use crate::mir;
 use crate::ty::fold::fold_regions;
 use crate::ty::{self, CoroutineArgsExt, OpaqueHiddenType, Ty, TyCtxt};
 
@@ -351,30 +350,3 @@ pub struct DestructuredConstant<'tcx> {
     pub variant: Option<VariantIdx>,
     pub fields: &'tcx [(ConstValue<'tcx>, Ty<'tcx>)],
 }
-
-/// Summarizes coverage IDs inserted by the `InstrumentCoverage` MIR pass
-/// (for compiler option `-Cinstrument-coverage`), after MIR optimizations
-/// have had a chance to potentially remove some of them.
-///
-/// Used by the `coverage_ids_info` query.
-#[derive(Clone, TyEncodable, TyDecodable, Debug, HashStable)]
-pub struct CoverageIdsInfo {
-    pub counters_seen: BitSet<mir::coverage::CounterId>,
-    pub expressions_seen: BitSet<mir::coverage::ExpressionId>,
-}
-
-impl CoverageIdsInfo {
-    /// Coverage codegen needs to know how many coverage counters are ever
-    /// incremented within a function, so that it can set the `num-counters`
-    /// argument of the `llvm.instrprof.increment` intrinsic.
-    ///
-    /// This may be less than the highest counter ID emitted by the
-    /// InstrumentCoverage MIR pass, if the highest-numbered counter increments
-    /// were removed by MIR optimizations.
-    pub fn num_counters_after_mir_opts(&self) -> u32 {
-        // FIXME(Zalathar): Currently this treats an unused counter as "used"
-        // if its ID is less than that of the highest counter that really is
-        // used. Fixing this would require adding a renumbering step somewhere.
-        self.counters_seen.last_set_in(..).map_or(0, |max| max.as_u32() + 1)
-    }
-}
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index a3976c3dda1..fc3d690a8a9 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -581,7 +581,7 @@ rustc_queries! {
     /// Summarizes coverage IDs inserted by the `InstrumentCoverage` MIR pass
     /// (for compiler option `-Cinstrument-coverage`), after MIR optimizations
     /// have had a chance to potentially remove some of them.
-    query coverage_ids_info(key: ty::InstanceKind<'tcx>) -> &'tcx mir::CoverageIdsInfo {
+    query coverage_ids_info(key: ty::InstanceKind<'tcx>) -> &'tcx mir::coverage::CoverageIdsInfo {
         desc { |tcx| "retrieving coverage IDs info from MIR for `{}`", tcx.def_path_str(key.def_id()) }
         arena_cache
     }
diff --git a/compiler/rustc_mir_transform/src/coverage/query.rs b/compiler/rustc_mir_transform/src/coverage/query.rs
index 0090f6f3040..edaec3c7965 100644
--- a/compiler/rustc_mir_transform/src/coverage/query.rs
+++ b/compiler/rustc_mir_transform/src/coverage/query.rs
@@ -1,8 +1,11 @@
 use rustc_data_structures::captures::Captures;
 use rustc_index::bit_set::BitSet;
 use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrFlags;
-use rustc_middle::mir::coverage::{CovTerm, CoverageKind, MappingKind};
-use rustc_middle::mir::{Body, CoverageIdsInfo, Statement, StatementKind};
+use rustc_middle::mir::coverage::{
+    CounterId, CovTerm, CoverageIdsInfo, CoverageKind, Expression, ExpressionId,
+    FunctionCoverageInfo, MappingKind, Op,
+};
+use rustc_middle::mir::{Body, Statement, StatementKind};
 use rustc_middle::query::TyCtxtAt;
 use rustc_middle::ty::{self, TyCtxt};
 use rustc_middle::util::Providers;
@@ -87,10 +90,10 @@ fn coverage_ids_info<'tcx>(
 ) -> CoverageIdsInfo {
     let mir_body = tcx.instance_mir(instance_def);
 
-    let Some(fn_cov_info) = mir_body.function_coverage_info.as_ref() else {
+    let Some(fn_cov_info) = mir_body.function_coverage_info.as_deref() else {
         return CoverageIdsInfo {
             counters_seen: BitSet::new_empty(0),
-            expressions_seen: BitSet::new_empty(0),
+            zero_expressions: BitSet::new_empty(0),
         };
     };
 
@@ -123,7 +126,10 @@ fn coverage_ids_info<'tcx>(
         }
     }
 
-    CoverageIdsInfo { counters_seen, expressions_seen }
+    let zero_expressions =
+        identify_zero_expressions(fn_cov_info, &counters_seen, &expressions_seen);
+
+    CoverageIdsInfo { counters_seen, zero_expressions }
 }
 
 fn all_coverage_in_mir_body<'a, 'tcx>(
@@ -141,3 +147,94 @@ 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 `BitSet`. 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: &BitSet<CounterId>,
+    expressions_seen: &BitSet<ExpressionId>,
+) -> BitSet<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 = BitSet::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: &BitSet<CounterId>,
+    zero_expressions: &BitSet<ExpressionId>,
+    term: CovTerm,
+) -> bool {
+    match term {
+        CovTerm::Zero => true,
+        CovTerm::Counter(id) => !counters_seen.contains(id),
+        CovTerm::Expression(id) => zero_expressions.contains(id),
+    }
+}