Auto merge of #134108 - fmease:rollup-tbtwm6j, r=fmease

Rollup of 10 pull requests

Successful merges:

 - #131558 (Lint on combining `#[no_mangle]` and `#[export_name]`)
 - #133184 (wasi/fs: Improve stopping condition for <ReadDir as Iterator>::next)
 - #133456 (Add licenses + Run `cargo update`)
 - #133472 (Run TLS destructors for wasm32-wasip1-threads)
 - #133853 (use vendor sources by default on dist tarballs)
 - #133946 (coverage: Prefer to visit nodes whose predecessors have been visited)
 - #134010 (fix ICE on type error in promoted)
 - #134029 (coverage: Use a query to find counters/expressions that must be zero)
 - #134071 (Configure renovatebot)
 - #134102 (Miscellaneous fixes for nix-dev-shell)

r? `@ghost`
`@rustbot` modify labels: rollup

3 files changed, 227 insertions, 151 deletions

diff --git a/compiler/rustc_mir_transform/src/coverage/counters.rs b/compiler/rustc_mir_transform/src/coverage/counters.rs
index 46efdd16ee8..9e80f1f1c4a 100644
--- a/compiler/rustc_mir_transform/src/coverage/counters.rs
+++ b/compiler/rustc_mir_transform/src/coverage/counters.rs
@@ -9,7 +9,7 @@ use rustc_index::bit_set::BitSet;
 use rustc_middle::mir::coverage::{CounterId, CovTerm, Expression, ExpressionId, Op};
 use tracing::{debug, debug_span, instrument};
 
-use crate::coverage::graph::{BasicCoverageBlock, CoverageGraph, TraverseCoverageGraphWithLoops};
+use crate::coverage::graph::{BasicCoverageBlock, CoverageGraph, ReadyFirstTraversal};
 
 #[cfg(test)]
 mod tests;
@@ -236,23 +236,12 @@ impl<'a> CountersBuilder<'a> {
 
         // Traverse the coverage graph, ensuring that every node that needs a
         // coverage counter has one.
-        //
-        // 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.
-        let mut traversal = TraverseCoverageGraphWithLoops::new(self.graph);
-        while let Some(bcb) = traversal.next() {
+        for bcb in ReadyFirstTraversal::new(self.graph) {
             let _span = debug_span!("traversal", ?bcb).entered();
             if self.bcb_needs_counter.contains(bcb) {
                 self.make_node_counter_and_out_edge_counters(bcb);
             }
         }
-
-        assert!(
-            traversal.is_complete(),
-            "`TraverseCoverageGraphWithLoops` missed some `BasicCoverageBlock`s: {:?}",
-            traversal.unvisited(),
-        );
     }
 
     /// Make sure the given node has a node counter, and then make sure each of
diff --git a/compiler/rustc_mir_transform/src/coverage/graph.rs b/compiler/rustc_mir_transform/src/coverage/graph.rs
index 092bce1de2c..ad6774fccd6 100644
--- a/compiler/rustc_mir_transform/src/coverage/graph.rs
+++ b/compiler/rustc_mir_transform/src/coverage/graph.rs
@@ -9,7 +9,6 @@ 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;
-use rustc_middle::bug;
 use rustc_middle::mir::{self, BasicBlock, Terminator, TerminatorKind};
 use tracing::debug;
 
@@ -462,138 +461,6 @@ fn bcb_filtered_successors<'a, 'tcx>(terminator: &'a Terminator<'tcx>) -> Covera
     CoverageSuccessors { targets, is_yield }
 }
 
-/// Maintains separate worklists for each loop in the BasicCoverageBlock CFG, plus one for the
-/// CoverageGraph outside all loops. This supports traversing the BCB CFG in a way that
-/// ensures a loop is completely traversed before processing Blocks after the end of the loop.
-#[derive(Debug)]
-struct TraversalContext {
-    /// 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(crate) struct TraverseCoverageGraphWithLoops<'a> {
-    basic_coverage_blocks: &'a CoverageGraph,
-
-    context_stack: Vec<TraversalContext>,
-    visited: BitSet<BasicCoverageBlock>,
-}
-
-impl<'a> TraverseCoverageGraphWithLoops<'a> {
-    pub(crate) fn new(basic_coverage_blocks: &'a CoverageGraph) -> Self {
-        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 { basic_coverage_blocks, context_stack, visited }
-    }
-
-    pub(crate) 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() {
-            let Some(bcb) = context.worklist.pop_front() else {
-                // This stack level is exhausted; pop it and try the next one.
-                self.context_stack.pop();
-                continue;
-            };
-
-            if !self.visited.insert(bcb) {
-                debug!("Already visited: {bcb:?}");
-                continue;
-            }
-            debug!("Visiting {bcb:?}");
-
-            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() });
-            }
-            self.add_successors_to_worklists(bcb);
-            return Some(bcb);
-        }
-
-        None
-    }
-
-    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!(
-                    "{:?} has itself as its own successor. (Note, the compiled code will \
-                    generate an infinite loop.)",
-                    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;
-            }
-
-            // 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)
-                    }
-                    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);
-            }
-        }
-    }
-
-    pub(crate) fn is_complete(&self) -> bool {
-        self.visited.count() == self.visited.domain_size()
-    }
-
-    pub(crate) fn unvisited(&self) -> Vec<BasicCoverageBlock> {
-        let mut unvisited_set: BitSet<BasicCoverageBlock> =
-            BitSet::new_filled(self.visited.domain_size());
-        unvisited_set.subtract(&self.visited);
-        unvisited_set.iter().collect::<Vec<_>>()
-    }
-}
-
 /// Wrapper around a [`mir::BasicBlocks`] graph that restricts each node's
 /// successors to only the ones considered "relevant" when building a coverage
 /// graph.
@@ -622,3 +489,126 @@ impl<'a, 'tcx> graph::Successors for CoverageRelevantSubgraph<'a, 'tcx> {
         self.coverage_successors(bb).into_iter()
     }
 }
+
+/// State of a node in the coverage graph during ready-first traversal.
+#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
+enum ReadyState {
+    /// This node has not yet been added to the fallback queue or ready queue.
+    Unqueued,
+    /// This node is currently in the fallback queue.
+    InFallbackQueue,
+    /// This node's predecessors have all been visited, so it is in the ready queue.
+    /// (It might also have a stale entry in the fallback queue.)
+    InReadyQueue,
+    /// This node has been visited.
+    /// (It might also have a stale entry in the fallback queue.)
+    Visited,
+}
+
+/// Iterator that visits nodes in the coverage graph, in an order that always
+/// prefers "ready" nodes whose predecessors have already been visited.
+pub(crate) struct ReadyFirstTraversal<'a> {
+    graph: &'a CoverageGraph,
+
+    /// For each node, the number of its predecessor nodes that haven't been visited yet.
+    n_unvisited_preds: IndexVec<BasicCoverageBlock, u32>,
+    /// Indicates whether a node has been visited, or which queue it is in.
+    state: IndexVec<BasicCoverageBlock, ReadyState>,
+
+    /// Holds unvisited nodes whose predecessors have all been visited.
+    ready_queue: VecDeque<BasicCoverageBlock>,
+    /// Holds unvisited nodes with some unvisited predecessors.
+    /// Also contains stale entries for nodes that were upgraded to ready.
+    fallback_queue: VecDeque<BasicCoverageBlock>,
+}
+
+impl<'a> ReadyFirstTraversal<'a> {
+    pub(crate) fn new(graph: &'a CoverageGraph) -> Self {
+        let num_nodes = graph.num_nodes();
+
+        let n_unvisited_preds =
+            IndexVec::from_fn_n(|node| graph.predecessors[node].len() as u32, num_nodes);
+        let mut state = IndexVec::from_elem_n(ReadyState::Unqueued, num_nodes);
+
+        // We know from coverage graph construction that the start node is the
+        // only node with no predecessors.
+        debug_assert!(
+            n_unvisited_preds.iter_enumerated().all(|(node, &n)| (node == START_BCB) == (n == 0))
+        );
+        let ready_queue = VecDeque::from(vec![START_BCB]);
+        state[START_BCB] = ReadyState::InReadyQueue;
+
+        Self { graph, state, n_unvisited_preds, ready_queue, fallback_queue: VecDeque::new() }
+    }
+
+    /// Returns the next node from the ready queue, or else the next unvisited
+    /// node from the fallback queue.
+    fn next_inner(&mut self) -> Option<BasicCoverageBlock> {
+        // Always prefer to yield a ready node if possible.
+        if let Some(node) = self.ready_queue.pop_front() {
+            assert_eq!(self.state[node], ReadyState::InReadyQueue);
+            return Some(node);
+        }
+
+        while let Some(node) = self.fallback_queue.pop_front() {
+            match self.state[node] {
+                // This entry in the fallback queue is not stale, so yield it.
+                ReadyState::InFallbackQueue => return Some(node),
+                // This node was added to the fallback queue, but later became
+                // ready and was visited via the ready queue. Ignore it here.
+                ReadyState::Visited => {}
+                // Unqueued nodes can't be in the fallback queue, by definition.
+                // We know that the ready queue is empty at this point.
+                ReadyState::Unqueued | ReadyState::InReadyQueue => unreachable!(
+                    "unexpected state for {node:?} in the fallback queue: {:?}",
+                    self.state[node]
+                ),
+            }
+        }
+
+        None
+    }
+
+    fn mark_visited_and_enqueue_successors(&mut self, node: BasicCoverageBlock) {
+        assert!(self.state[node] < ReadyState::Visited);
+        self.state[node] = ReadyState::Visited;
+
+        // For each of this node's successors, decrease the successor's
+        // "unvisited predecessors" count, and enqueue it if appropriate.
+        for &succ in &self.graph.successors[node] {
+            let is_unqueued = match self.state[succ] {
+                ReadyState::Unqueued => true,
+                ReadyState::InFallbackQueue => false,
+                ReadyState::InReadyQueue => {
+                    unreachable!("nodes in the ready queue have no unvisited predecessors")
+                }
+                // The successor was already visited via one of its other predecessors.
+                ReadyState::Visited => continue,
+            };
+
+            self.n_unvisited_preds[succ] -= 1;
+            if self.n_unvisited_preds[succ] == 0 {
+                // This node's predecessors have all been visited, so add it to
+                // the ready queue. If it's already in the fallback queue, that
+                // fallback entry will be ignored later.
+                self.state[succ] = ReadyState::InReadyQueue;
+                self.ready_queue.push_back(succ);
+            } else if is_unqueued {
+                // This node has unvisited predecessors, so add it to the
+                // fallback queue in case we run out of ready nodes later.
+                self.state[succ] = ReadyState::InFallbackQueue;
+                self.fallback_queue.push_back(succ);
+            }
+        }
+    }
+}
+
+impl<'a> Iterator for ReadyFirstTraversal<'a> {
+    type Item = BasicCoverageBlock;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let node = self.next_inner()?;
+        self.mark_visited_and_enqueue_successors(node);
+        Some(node)
+    }
+}
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),
+    }
+}