Extend SCC construction to enable extra functionality

This patch has been extracted from #123720. It specifically enhances
`Sccs` to allow tracking arbitrary commutative properties of SCCs, including
- reachable values (max/min)
- SCC-internal values (max/min)

This helps with among other things universe computation: we can now identify
SCC universes as a straightforward "find max/min" operation during SCC construction.

It's also more or less zero-cost; don't use the new features, don't pay for them.

This commit also vastly extends the documentation of the SCCs module, which I had a very hard time following.

2 files changed, 472 insertions, 129 deletions

diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs
index 7f36e4ca16d..fb8d727d67e 100644
--- a/compiler/rustc_data_structures/src/graph/scc/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs
@@ -4,52 +4,109 @@
 //! node in the graph. This uses [Tarjan's algorithm](
 //! https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)
 //! that completes in *O*(*n*) time.
+//! Optionally, also annotate the SCC nodes with some commutative data.
+//! Typical examples would include: minimum element in SCC, maximum element
+//! reachable from it, etc.
 
 use crate::fx::FxHashSet;
 use crate::graph::vec_graph::VecGraph;
 use crate::graph::{DirectedGraph, NumEdges, Successors};
 use rustc_index::{Idx, IndexSlice, IndexVec};
+use std::fmt::Debug;
 use std::ops::Range;
 use tracing::{debug, instrument};
 
 #[cfg(test)]
 mod tests;
 
+/// An annotation for an SCC. This can be a representative,
+/// or the max/min element of the SCC, or all of the above.
+pub trait Annotation: Debug + Copy {
+    /// Merge two existing annotations into one during
+    /// path compression.
+    fn merge_scc(self, other: Self) -> Self;
+
+    /// Merge a successor into this annotation.
+    fn merge_reached(self, other: Self) -> Self;
+
+    fn update_scc(&mut self, other: Self) {
+        *self = self.merge_scc(other)
+    }
+
+    fn update_reachable(&mut self, other: Self) {
+        *self = self.merge_reached(other)
+    }
+}
+
+/// The empty annotation, which does nothing.
+impl Annotation for () {
+    fn merge_reached(self, _other: Self) -> Self {
+        ()
+    }
+    fn merge_scc(self, _other: Self) -> Self {
+        ()
+    }
+}
+
 /// Strongly connected components (SCC) of a graph. The type `N` is
 /// the index type for the graph nodes and `S` is the index type for
 /// the SCCs. We can map from each node to the SCC that it
 /// participates in, and we also have the successors of each SCC.
-pub struct Sccs<N: Idx, S: Idx> {
+pub struct Sccs<N: Idx, S: Idx, A: Annotation> {
     /// For each node, what is the SCC index of the SCC to which it
     /// belongs.
     scc_indices: IndexVec<N, S>,
 
-    /// Data about each SCC.
-    scc_data: SccData<S>,
+    /// Data about all the SCCs.
+    scc_data: SccData<S, A>,
 }
 
-pub struct SccData<S: Idx> {
-    /// For each SCC, the range of `all_successors` where its
+/// Information about an invidividual SCC node.
+struct SccDetails<A: Annotation> {
+    /// For this SCC, the range of `all_successors` where its
     /// successors can be found.
-    ranges: IndexVec<S, Range<usize>>,
+    range: Range<usize>,
+
+    /// User-specified metadata about the SCC.
+    annotation: A,
+}
+
+// The name of this struct should discourage you from making it public and leaking
+// its representation. This message was left here by one who came before you,
+//  who learnt the hard way that making even small changes in representation is difficult when it's publicly inspectable. Obey the law of Demeter!
+struct SccData<S: Idx, A: Annotation> {
+    /// Maps SCC indices to their metadata, including
+    /// offsets into `all_successors`.
+    scc_details: IndexVec<S, SccDetails<A>>,
 
     /// Contains the successors for all the Sccs, concatenated. The
     /// range of indices corresponding to a given SCC is found in its
-    /// SccData.
+    /// `scc_details.range`.
     all_successors: Vec<S>,
 }
 
-impl<N: Idx, S: Idx + Ord> Sccs<N, S> {
+impl<N: Idx, S: Idx + Ord> Sccs<N, S, ()> {
+    /// Compute SCCs without annotations.
     pub fn new(graph: &impl Successors<Node = N>) -> Self {
-        SccsConstruction::construct(graph)
+        Self::new_with_annotation(graph, |_| ())
     }
+}
 
-    pub fn scc_indices(&self) -> &IndexSlice<N, S> {
-        &self.scc_indices
+impl<N: Idx, S: Idx + Ord, A: Annotation> Sccs<N, S, A> {
+    /// Compute SCCs and annotate them with a user-supplied annotation
+    pub fn new_with_annotation<F: Fn(N) -> A>(
+        graph: &impl Successors<Node = N>,
+        to_annotation: F,
+    ) -> Self {
+        SccsConstruction::construct(graph, to_annotation)
+    }
+
+    pub fn annotation(&self, scc: S) -> A {
+        self.scc_data.annotation(scc)
     }
 
-    pub fn scc_data(&self) -> &SccData<S> {
-        &self.scc_data
+    pub fn scc_indices(&self) -> &IndexSlice<N, S> {
+        &self.scc_indices
     }
 
     /// Returns the number of SCCs in the graph.
@@ -90,7 +147,7 @@ impl<N: Idx, S: Idx + Ord> Sccs<N, S> {
     }
 }
 
-impl<N: Idx, S: Idx + Ord> DirectedGraph for Sccs<N, S> {
+impl<N: Idx, S: Idx + Ord, A: Annotation> DirectedGraph for Sccs<N, S, A> {
     type Node = S;
 
     fn num_nodes(&self) -> usize {
@@ -98,43 +155,33 @@ impl<N: Idx, S: Idx + Ord> DirectedGraph for Sccs<N, S> {
     }
 }
 
-impl<N: Idx, S: Idx + Ord> NumEdges for Sccs<N, S> {
+impl<N: Idx, S: Idx + Ord, A: Annotation> NumEdges for Sccs<N, S, A> {
     fn num_edges(&self) -> usize {
         self.scc_data.all_successors.len()
     }
 }
 
-impl<N: Idx, S: Idx + Ord> Successors for Sccs<N, S> {
+impl<N: Idx, S: Idx + Ord, A: Annotation> Successors for Sccs<N, S, A> {
     fn successors(&self, node: S) -> impl Iterator<Item = Self::Node> {
         self.successors(node).iter().cloned()
     }
 }
 
-impl<S: Idx> SccData<S> {
+impl<S: Idx, A: Annotation> SccData<S, A> {
     /// Number of SCCs,
     fn len(&self) -> usize {
-        self.ranges.len()
-    }
-
-    pub fn ranges(&self) -> &IndexSlice<S, Range<usize>> {
-        &self.ranges
-    }
-
-    pub fn all_successors(&self) -> &Vec<S> {
-        &self.all_successors
+        self.scc_details.len()
     }
 
     /// Returns the successors of the given SCC.
     fn successors(&self, scc: S) -> &[S] {
-        // Annoyingly, `range` does not implement `Copy`, so we have
-        // to do `range.start..range.end`:
-        let range = &self.ranges[scc];
-        &self.all_successors[range.start..range.end]
+        &self.all_successors[self.scc_details[scc].range.clone()]
     }
 
     /// Creates a new SCC with `successors` as its successors and
+    /// the maximum weight of its internal nodes `scc_max_weight` and
     /// returns the resulting index.
-    fn create_scc(&mut self, successors: impl IntoIterator<Item = S>) -> S {
+    fn create_scc(&mut self, successors: impl IntoIterator<Item = S>, annotation: A) -> S {
         // Store the successors on `scc_successors_vec`, remembering
         // the range of indices.
         let all_successors_start = self.all_successors.len();
@@ -142,22 +189,35 @@ impl<S: Idx> SccData<S> {
         let all_successors_end = self.all_successors.len();
 
         debug!(
-            "create_scc({:?}) successors={:?}",
-            self.ranges.len(),
+            "create_scc({:?}) successors={:?}, annotation={:?}",
+            self.len(),
             &self.all_successors[all_successors_start..all_successors_end],
+            annotation
         );
 
-        self.ranges.push(all_successors_start..all_successors_end)
+        let range = all_successors_start..all_successors_end;
+        let metadata = SccDetails { range, annotation };
+        self.scc_details.push(metadata)
+    }
+
+    fn annotation(&self, scc: S) -> A {
+        self.scc_details[scc].annotation
     }
 }
 
-struct SccsConstruction<'c, G: DirectedGraph + Successors, S: Idx> {
+struct SccsConstruction<'c, G, S, A, F>
+where
+    G: DirectedGraph + Successors,
+    S: Idx,
+    A: Annotation,
+    F: Fn(G::Node) -> A,
+{
     graph: &'c G,
 
     /// The state of each node; used during walk to record the stack
     /// and after walk to record what cycle each node ended up being
     /// in.
-    node_states: IndexVec<G::Node, NodeState<G::Node, S>>,
+    node_states: IndexVec<G::Node, NodeState<G::Node, S, A>>,
 
     /// The stack of nodes that we are visiting as part of the DFS.
     node_stack: Vec<G::Node>,
@@ -174,26 +234,34 @@ struct SccsConstruction<'c, G: DirectedGraph + Successors, S: Idx> {
     /// around between successors to amortize memory allocation costs.
     duplicate_set: FxHashSet<S>,
 
-    scc_data: SccData<S>,
+    scc_data: SccData<S, A>,
+
+    /// A function that constructs an initial SCC annotation
+    /// out of a single node.
+    to_annotation: F,
 }
 
 #[derive(Copy, Clone, Debug)]
-enum NodeState<N, S> {
+enum NodeState<N, S, A> {
     /// This node has not yet been visited as part of the DFS.
     ///
     /// After SCC construction is complete, this state ought to be
     /// impossible.
     NotVisited,
 
-    /// This node is currently being walk as part of our DFS. It is on
-    /// the stack at the depth `depth`.
+    /// This node is currently being walked as part of our DFS. It is on
+    /// the stack at the depth `depth` and the heaviest node on the way
+    /// there is `max_weigth_on_path`.
     ///
     /// After SCC construction is complete, this state ought to be
     /// impossible.
-    BeingVisited { depth: usize },
+    BeingVisited { depth: usize, annotation: A },
 
-    /// Indicates that this node is a member of the given cycle.
-    InCycle { scc_index: S },
+    /// Indicates that this node is a member of the given cycle where
+    /// the weight of the heaviest node is `cycle_max_weight`.
+    /// Note that an SCC can have several cycles, so the max
+    /// weight of an SCC is the max weight of all its cycles.
+    InCycle { scc_index: S, annotation: A },
 
     /// Indicates that this node is a member of whatever cycle
     /// `parent` is a member of. This state is transient: whenever we
@@ -203,16 +271,27 @@ enum NodeState<N, S> {
     InCycleWith { parent: N },
 }
 
+/// The state of walking a given node.
 #[derive(Copy, Clone, Debug)]
-enum WalkReturn<S> {
-    Cycle { min_depth: usize },
-    Complete { scc_index: S },
+enum WalkReturn<S, A> {
+    /// The walk found a cycle, but the entire component is not known to have
+    /// been fully walked yet. We only know the minimum depth of  this
+    /// component in a minimum spanning tree of the graph. This component
+    /// is tentatively represented by the state of the first node of this
+    /// cycle we met, which is at `min_depth`.
+    Cycle { min_depth: usize, annotation: A },
+    /// The SCC and everything reachable from it have been fully walked.
+    /// At this point we know what is inside the SCC as we have visited every
+    /// node reachable from it. The SCC can now be fully represented by its ID.
+    Complete { scc_index: S, annotation: A },
 }
 
-impl<'c, G, S> SccsConstruction<'c, G, S>
+impl<'c, G, S, A, F> SccsConstruction<'c, G, S, A, F>
 where
     G: DirectedGraph + Successors,
     S: Idx,
+    F: Fn(G::Node) -> A,
+    A: Annotation,
 {
     /// Identifies SCCs in the graph `G` and computes the resulting
     /// DAG. This uses a variant of [Tarjan's
@@ -225,8 +304,12 @@ where
     /// D' (i.e., D' < D), we know that N, N', and all nodes in
     /// between them on the stack are part of an SCC.
     ///
+    /// Additionally, we keep track of a representative of the SCC with the highest
+    /// reachable weight for all SCCs, for some arbitrary ordering function that assigns
+    /// a weight to nodes.
+    ///
     /// [wikipedia]: https://bit.ly/2EZIx84
-    fn construct(graph: &'c G) -> Sccs<G::Node, S> {
+    fn construct(graph: &'c G, to_annotation: F) -> Sccs<G::Node, S, A> {
         let num_nodes = graph.num_nodes();
 
         let mut this = Self {
@@ -234,15 +317,16 @@ where
             node_states: IndexVec::from_elem_n(NodeState::NotVisited, num_nodes),
             node_stack: Vec::with_capacity(num_nodes),
             successors_stack: Vec::new(),
-            scc_data: SccData { ranges: IndexVec::new(), all_successors: Vec::new() },
+            scc_data: SccData { scc_details: IndexVec::new(), all_successors: Vec::new() },
             duplicate_set: FxHashSet::default(),
+            to_annotation,
         };
 
         let scc_indices = (0..num_nodes)
             .map(G::Node::new)
             .map(|node| match this.start_walk_from(node) {
-                WalkReturn::Complete { scc_index } => scc_index,
-                WalkReturn::Cycle { min_depth } => {
+                WalkReturn::Complete { scc_index, .. } => scc_index,
+                WalkReturn::Cycle { min_depth, .. } => {
                     panic!("`start_walk_node({node:?})` returned cycle with depth {min_depth:?}")
                 }
             })
@@ -251,12 +335,8 @@ where
         Sccs { scc_indices, scc_data: this.scc_data }
     }
 
-    fn start_walk_from(&mut self, node: G::Node) -> WalkReturn<S> {
-        if let Some(result) = self.inspect_node(node) {
-            result
-        } else {
-            self.walk_unvisited_node(node)
-        }
+    fn start_walk_from(&mut self, node: G::Node) -> WalkReturn<S, A> {
+        self.inspect_node(node).unwrap_or_else(|| self.walk_unvisited_node(node))
     }
 
     /// Inspect a node during the DFS. We first examine its current
@@ -271,11 +351,15 @@ where
     /// Otherwise, we are looking at a node that has already been
     /// completely visited. We therefore return `WalkReturn::Complete`
     /// with its associated SCC index.
-    fn inspect_node(&mut self, node: G::Node) -> Option<WalkReturn<S>> {
+    fn inspect_node(&mut self, node: G::Node) -> Option<WalkReturn<S, A>> {
         Some(match self.find_state(node) {
-            NodeState::InCycle { scc_index } => WalkReturn::Complete { scc_index },
+            NodeState::InCycle { scc_index, annotation } => {
+                WalkReturn::Complete { scc_index, annotation }
+            }
 
-            NodeState::BeingVisited { depth: min_depth } => WalkReturn::Cycle { min_depth },
+            NodeState::BeingVisited { depth: min_depth, annotation } => {
+                WalkReturn::Cycle { min_depth, annotation }
+            }
 
             NodeState::NotVisited => return None,
 
@@ -290,7 +374,7 @@ where
     /// of `r2` (and updates `r` to reflect current result). This is
     /// basically the "find" part of a standard union-find algorithm
     /// (with path compression).
-    fn find_state(&mut self, mut node: G::Node) -> NodeState<G::Node, S> {
+    fn find_state(&mut self, mut node: G::Node) -> NodeState<G::Node, S, A> {
         // To avoid recursion we temporarily reuse the `parent` of each
         // InCycleWith link to encode a downwards link while compressing
         // the path. After we have found the root or deepest node being
@@ -306,24 +390,42 @@ where
         // found the initial self-loop.
         let mut previous_node = node;
 
-        // Ultimately assigned by the parent when following
+        // Ultimately propagated to all the transitive parents when following
         // `InCycleWith` upwards.
-        let node_state = loop {
-            debug!("find_state(r = {:?} in state {:?})", node, self.node_states[node]);
-            match self.node_states[node] {
-                NodeState::InCycle { scc_index } => break NodeState::InCycle { scc_index },
-                NodeState::BeingVisited { depth } => break NodeState::BeingVisited { depth },
-                NodeState::NotVisited => break NodeState::NotVisited,
-                NodeState::InCycleWith { parent } => {
-                    // We test this, to be extremely sure that we never
-                    // ever break our termination condition for the
-                    // reverse iteration loop.
-                    assert!(node != parent, "Node can not be in cycle with itself");
-                    // Store the previous node as an inverted list link
-                    self.node_states[node] = NodeState::InCycleWith { parent: previous_node };
-                    // Update to parent node.
-                    previous_node = node;
-                    node = parent;
+        // This loop performs the downward link encoding mentioned above. Details below!
+        let node_state = {
+            let mut annotation = (self.to_annotation)(node);
+
+            loop {
+                debug!("find_state(r = {node:?} in state {:?})", self.node_states[node]);
+                match self.node_states[node] {
+                    NodeState::NotVisited => break NodeState::NotVisited,
+                    NodeState::BeingVisited { depth, annotation: previous_annotation } => {
+                        break NodeState::BeingVisited {
+                            depth,
+                            annotation: previous_annotation.merge_scc(annotation),
+                        };
+                    }
+                    NodeState::InCycleWith { parent } => {
+                        // We test this, to be extremely sure that we never
+                        // ever break our termination condition for the
+                        // reverse iteration loop.
+                        assert!(node != parent, "Node can not be in cycle with itself");
+
+                        annotation = annotation.merge_scc((self.to_annotation)(node));
+
+                        // Store the previous node as an inverted list link
+                        self.node_states[node] = NodeState::InCycleWith { parent: previous_node };
+                        // Update to parent node.
+                        previous_node = node;
+                        node = parent;
+                    }
+                    NodeState::InCycle { scc_index, annotation: previous_annotation } => {
+                        break NodeState::InCycle {
+                            scc_index,
+                            annotation: previous_annotation.merge_scc(annotation),
+                        };
+                    }
                 }
             }
         };
@@ -369,6 +471,8 @@ where
             if previous_node == node {
                 return node_state;
             }
+            debug!("Compressing {node:?} down to {previous_node:?} with state {node_state:?}");
+
             // Update to previous node in the link.
             match self.node_states[previous_node] {
                 NodeState::InCycleWith { parent: previous } => {
@@ -381,29 +485,20 @@ where
 
             debug!("find_state: parent_state = {:?}", node_state);
 
-            // Update the node state from the parent state. The assigned
-            // state is actually a loop invariant but it will only be
-            // evaluated if there is at least one backlink to follow.
-            // Fully trusting llvm here to find this loop optimization.
-            match node_state {
-                // Path compression, make current node point to the same root.
-                NodeState::InCycle { .. } => {
-                    self.node_states[node] = node_state;
-                }
-                // Still visiting nodes, compress to cycle to the node
+            let new_state = match node_state {
+                // Still visiting nodes, compress the cycle to the root node
                 // at that depth.
-                NodeState::BeingVisited { depth } => {
-                    self.node_states[node] =
-                        NodeState::InCycleWith { parent: self.node_stack[depth] };
+                NodeState::BeingVisited { depth, .. } => {
+                    let parent = self.node_stack[depth];
+                    NodeState::InCycleWith { parent }
                 }
-                // These are never allowed as parent nodes. InCycleWith
-                // should have been followed to a real parent and
-                // NotVisited can not be part of a cycle since it should
-                // have instead gotten explored.
-                NodeState::NotVisited | NodeState::InCycleWith { .. } => {
-                    panic!("invalid parent state: {node_state:?}")
-                }
-            }
+                // Already fully visited; we just transfer the state of the parent.
+                s @ NodeState::InCycle { .. } => s,
+                // These cannot be the root nodes of a path being compressed
+                NodeState::NotVisited | NodeState::InCycleWith { .. } => unreachable!(),
+            };
+
+            self.node_states[node] = new_state;
         }
     }
 
@@ -413,30 +508,37 @@ where
     /// caller decide avoids mutual recursion between the two methods and allows
     /// us to maintain an allocated stack for nodes on the path between calls.
     #[instrument(skip(self, initial), level = "debug")]
-    fn walk_unvisited_node(&mut self, initial: G::Node) -> WalkReturn<S> {
-        struct VisitingNodeFrame<G: DirectedGraph, Successors> {
+    fn walk_unvisited_node(&mut self, initial: G::Node) -> WalkReturn<S, A> {
+        debug!("Walk unvisited node: {initial:?}");
+        struct VisitingNodeFrame<G: DirectedGraph, Successors, A> {
             node: G::Node,
-            iter: Option<Successors>,
+            successors: Option<Successors>,
             depth: usize,
             min_depth: usize,
             successors_len: usize,
             min_cycle_root: G::Node,
             successor_node: G::Node,
+            /// The annotation for the SCC starting in `node`. It may or may
+            /// not contain other nodes.
+            current_component_annotation: A,
         }
 
         // Move the stack to a local variable. We want to utilize the existing allocation and
         // mutably borrow it without borrowing self at the same time.
         let mut successors_stack = core::mem::take(&mut self.successors_stack);
+
         debug_assert_eq!(successors_stack.len(), 0);
 
-        let mut stack: Vec<VisitingNodeFrame<G, _>> = vec![VisitingNodeFrame {
+        let mut stack: Vec<VisitingNodeFrame<G, _, _>> = vec![VisitingNodeFrame {
             node: initial,
             depth: 0,
             min_depth: 0,
-            iter: None,
+            successors: None,
             successors_len: 0,
             min_cycle_root: initial,
             successor_node: initial,
+            // Strictly speaking not necessary, but assumed to be idempotent:
+            current_component_annotation: (self.to_annotation)(initial),
         }];
 
         let mut return_value = None;
@@ -445,18 +547,24 @@ where
             let VisitingNodeFrame {
                 node,
                 depth,
-                iter,
+                successors,
                 successors_len,
                 min_depth,
                 min_cycle_root,
                 successor_node,
+                current_component_annotation,
             } = frame;
-
             let node = *node;
             let depth = *depth;
 
-            let successors = match iter {
-                Some(iter) => iter,
+            // node is definitely in the current component, add it to the annotation.
+            current_component_annotation.update_scc((self.to_annotation)(node));
+            debug!(
+                "Visiting {node:?} at depth {depth:?}, annotation: {current_component_annotation:?}"
+            );
+
+            let successors = match successors {
+                Some(successors) => successors,
                 None => {
                     // This None marks that we still have the initialize this node's frame.
                     debug!(?depth, ?node);
@@ -464,7 +572,8 @@ where
                     debug_assert!(matches!(self.node_states[node], NodeState::NotVisited));
 
                     // Push `node` onto the stack.
-                    self.node_states[node] = NodeState::BeingVisited { depth };
+                    self.node_states[node] =
+                        NodeState::BeingVisited { depth, annotation: (self.to_annotation)(node) };
                     self.node_stack.push(node);
 
                     // Walk each successor of the node, looking to see if any of
@@ -472,11 +581,11 @@ where
                     // so, that means they can also reach us.
                     *successors_len = successors_stack.len();
                     // Set and return a reference, this is currently empty.
-                    iter.get_or_insert(self.graph.successors(node))
+                    successors.get_or_insert(self.graph.successors(node))
                 }
             };
 
-            // Now that iter is initialized, this is a constant for this frame.
+            // Now that the successors iterator is initialized, this is a constant for this frame.
             let successors_len = *successors_len;
 
             // Construct iterators for the nodes and walk results. There are two cases:
@@ -489,10 +598,17 @@ where
                 debug!(?node, ?successor_node);
                 (successor_node, self.inspect_node(successor_node))
             });
-
             for (successor_node, walk) in returned_walk.chain(successor_walk) {
                 match walk {
-                    Some(WalkReturn::Cycle { min_depth: successor_min_depth }) => {
+                    // The starting node `node` leads to a cycle whose earliest node,
+                    // `successor_node`, is at `min_depth`. There may be more cycles.
+                    Some(WalkReturn::Cycle {
+                        min_depth: successor_min_depth,
+                        annotation: successor_annotation,
+                    }) => {
+                        debug!(
+                            "Cycle found from {node:?}, minimum depth: {successor_min_depth:?}, annotation: {successor_annotation:?}"
+                        );
                         // Track the minimum depth we can reach.
                         assert!(successor_min_depth <= depth);
                         if successor_min_depth < *min_depth {
@@ -500,41 +616,56 @@ where
                             *min_depth = successor_min_depth;
                             *min_cycle_root = successor_node;
                         }
+                        current_component_annotation.update_scc(successor_annotation);
                     }
-
-                    Some(WalkReturn::Complete { scc_index: successor_scc_index }) => {
+                    // The starting node `node` is succeeded by a fully identified SCC
+                    // which is now added to the set under `scc_index`.
+                    Some(WalkReturn::Complete {
+                        scc_index: successor_scc_index,
+                        annotation: successor_annotation,
+                    }) => {
+                        debug!(
+                            "Complete; {node:?} is root of complete-visited SCC idx {successor_scc_index:?} with annotation {successor_annotation:?}"
+                        );
                         // Push the completed SCC indices onto
                         // the `successors_stack` for later.
                         debug!(?node, ?successor_scc_index);
                         successors_stack.push(successor_scc_index);
+                        current_component_annotation.update_reachable(successor_annotation);
                     }
-
+                    // `node` has no more (direct) successors; search recursively.
                     None => {
                         let depth = depth + 1;
+                        debug!("Recursing down into {successor_node:?} at depth {depth:?}");
                         debug!(?depth, ?successor_node);
                         // Remember which node the return value will come from.
                         frame.successor_node = successor_node;
-                        // Start a new stack frame the step into it.
+                        // Start a new stack frame, then step into it.
                         stack.push(VisitingNodeFrame {
                             node: successor_node,
                             depth,
-                            iter: None,
+                            successors: None,
                             successors_len: 0,
                             min_depth: depth,
                             min_cycle_root: successor_node,
                             successor_node,
+                            current_component_annotation: (self.to_annotation)(successor_node),
                         });
                         continue 'recurse;
                     }
                 }
             }
 
+            debug!("Finished walk from {node:?} with annotation: {current_component_annotation:?}");
+
             // Completed walk, remove `node` from the stack.
             let r = self.node_stack.pop();
             debug_assert_eq!(r, Some(node));
 
             // Remove the frame, it's done.
             let frame = stack.pop().unwrap();
+            let current_component_annotation = frame.current_component_annotation;
+            debug_assert_eq!(frame.node, node);
 
             // If `min_depth == depth`, then we are the root of the
             // cycle: we can't reach anyone further down the stack.
@@ -543,6 +674,8 @@ where
             // We return one frame at a time so there can't be another return value.
             debug_assert!(return_value.is_none());
             return_value = Some(if frame.min_depth == depth {
+                // We are at the head of the component.
+
                 // Note that successor stack may have duplicates, so we
                 // want to remove those:
                 let deduplicated_successors = {
@@ -552,15 +685,25 @@ where
                         .drain(successors_len..)
                         .filter(move |&i| duplicate_set.insert(i))
                 };
-                let scc_index = self.scc_data.create_scc(deduplicated_successors);
-                self.node_states[node] = NodeState::InCycle { scc_index };
-                WalkReturn::Complete { scc_index }
+
+                debug!("Creating SCC rooted in {node:?} with successor {:?}", frame.successor_node);
+
+                let scc_index =
+                    self.scc_data.create_scc(deduplicated_successors, current_component_annotation);
+
+                self.node_states[node] =
+                    NodeState::InCycle { scc_index, annotation: current_component_annotation };
+
+                WalkReturn::Complete { scc_index, annotation: current_component_annotation }
             } else {
                 // We are not the head of the cycle. Return back to our
                 // caller. They will take ownership of the
                 // `self.successors` data that we pushed.
                 self.node_states[node] = NodeState::InCycleWith { parent: frame.min_cycle_root };
-                WalkReturn::Cycle { min_depth: frame.min_depth }
+                WalkReturn::Cycle {
+                    min_depth: frame.min_depth,
+                    annotation: current_component_annotation,
+                }
             });
         }
 
diff --git a/compiler/rustc_data_structures/src/graph/scc/tests.rs b/compiler/rustc_data_structures/src/graph/scc/tests.rs
index 513df666d0d..373f87bfdbc 100644
--- a/compiler/rustc_data_structures/src/graph/scc/tests.rs
+++ b/compiler/rustc_data_structures/src/graph/scc/tests.rs
@@ -3,10 +3,53 @@ extern crate test;
 use super::*;
 use crate::graph::tests::TestGraph;
 
+#[derive(Copy, Clone, Debug)]
+struct MaxReached(usize);
+type UsizeSccs = Sccs<usize, usize, ()>;
+type MaxReachedSccs = Sccs<usize, usize, MaxReached>;
+
+impl Annotation for MaxReached {
+    fn merge_scc(self, other: Self) -> Self {
+        Self(std::cmp::max(other.0, self.0))
+    }
+
+    fn merge_reached(self, other: Self) -> Self {
+        self.merge_scc(other)
+    }
+}
+
+impl PartialEq<usize> for MaxReached {
+    fn eq(&self, other: &usize) -> bool {
+        &self.0 == other
+    }
+}
+
+impl MaxReached {
+    fn from_usize(nr: usize) -> Self {
+        Self(nr)
+    }
+}
+
+#[derive(Copy, Clone, Debug)]
+struct MinMaxIn {
+    min: usize,
+    max: usize,
+}
+
+impl Annotation for MinMaxIn {
+    fn merge_scc(self, other: Self) -> Self {
+        Self { min: std::cmp::min(self.min, other.min), max: std::cmp::max(self.max, other.max) }
+    }
+
+    fn merge_reached(self, _other: Self) -> Self {
+        self
+    }
+}
+
 #[test]
 fn diamond() {
     let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
-    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    let sccs: UsizeSccs = Sccs::new(&graph);
     assert_eq!(sccs.num_sccs(), 4);
     assert_eq!(sccs.num_sccs(), 4);
 }
@@ -34,7 +77,7 @@ fn test_big_scc() {
     +-- 2 <--+
          */
     let graph = TestGraph::new(0, &[(0, 1), (1, 2), (1, 3), (2, 0), (3, 2)]);
-    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    let sccs: UsizeSccs = Sccs::new(&graph);
     assert_eq!(sccs.num_sccs(), 1);
 }
 
@@ -50,7 +93,7 @@ fn test_three_sccs() {
     +-- 2 <--+
          */
     let graph = TestGraph::new(0, &[(0, 1), (1, 2), (2, 1), (3, 2)]);
-    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    let sccs: UsizeSccs = Sccs::new(&graph);
     assert_eq!(sccs.num_sccs(), 3);
     assert_eq!(sccs.scc(0), 1);
     assert_eq!(sccs.scc(1), 0);
@@ -106,7 +149,7 @@ fn test_find_state_2() {
     // 2 InCycleWith { 1 }
     // 3 InCycleWith { 0 }
 
-    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    let sccs: UsizeSccs = Sccs::new(&graph);
     assert_eq!(sccs.num_sccs(), 1);
     assert_eq!(sccs.scc(0), 0);
     assert_eq!(sccs.scc(1), 0);
@@ -130,7 +173,7 @@ fn test_find_state_3() {
          */
     let graph =
         TestGraph::new(0, &[(0, 1), (0, 4), (1, 2), (1, 3), (2, 1), (3, 0), (4, 2), (5, 2)]);
-    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    let sccs: UsizeSccs = Sccs::new(&graph);
     assert_eq!(sccs.num_sccs(), 2);
     assert_eq!(sccs.scc(0), 0);
     assert_eq!(sccs.scc(1), 0);
@@ -165,7 +208,7 @@ fn test_deep_linear() {
         nodes.push((i - 1, i));
     }
     let graph = TestGraph::new(0, nodes.as_slice());
-    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    let sccs: UsizeSccs = Sccs::new(&graph);
     assert_eq!(sccs.num_sccs(), NR_NODES);
     assert_eq!(sccs.scc(0), NR_NODES - 1);
     assert_eq!(sccs.scc(NR_NODES - 1), 0);
@@ -210,7 +253,164 @@ fn bench_sccc(b: &mut test::Bencher) {
     graph[21] = (7, 4);
     let graph = TestGraph::new(0, &graph[..]);
     b.iter(|| {
-        let sccs: Sccs<_, usize> = Sccs::new(&graph);
+        let sccs: UsizeSccs = Sccs::new(&graph);
         assert_eq!(sccs.num_sccs(), 3);
     });
 }
+
+#[test]
+fn test_max_self_loop() {
+    let graph = TestGraph::new(0, &[(0, 0)]);
+    let sccs: MaxReachedSccs =
+        Sccs::new_with_annotation(&graph, |n| if n == 0 { MaxReached(17) } else { MaxReached(0) });
+    assert_eq!(sccs.annotation(0), 17);
+}
+
+#[test]
+fn test_max_branch() {
+    let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 4)]);
+    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, MaxReached::from_usize);
+    assert_eq!(sccs.annotation(sccs.scc(0)), 4);
+    assert_eq!(sccs.annotation(sccs.scc(1)), 3);
+    assert_eq!(sccs.annotation(sccs.scc(2)), 4);
+}
+#[test]
+fn test_single_cycle_max() {
+    let graph = TestGraph::new(0, &[(0, 2), (2, 3), (2, 4), (4, 1), (1, 2)]);
+    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, MaxReached::from_usize);
+    assert_eq!(sccs.annotation(sccs.scc(2)), 4);
+    assert_eq!(sccs.annotation(sccs.scc(0)), 4);
+}
+
+#[test]
+fn test_simple_cycle_max() {
+    let graph = TestGraph::new(0, &[(0, 1), (1, 2), (2, 0)]);
+    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, MaxReached::from_usize);
+    assert_eq!(sccs.num_sccs(), 1);
+}
+
+#[test]
+fn test_double_cycle_max() {
+    let graph =
+        TestGraph::new(0, &[(0, 1), (1, 2), (1, 4), (2, 3), (2, 4), (3, 5), (4, 1), (5, 4)]);
+    let sccs: MaxReachedSccs =
+        Sccs::new_with_annotation(&graph, |n| if n == 5 { MaxReached(2) } else { MaxReached(1) });
+
+    assert_eq!(sccs.annotation(sccs.scc(0)).0, 2);
+}
+
+#[test]
+fn test_bug_minimised() {
+    let graph = TestGraph::new(0, &[(0, 3), (0, 1), (3, 2), (2, 3), (1, 4), (4, 5), (5, 4)]);
+    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, |n| match n {
+        3 => MaxReached(1),
+        _ => MaxReached(0),
+    });
+    assert_eq!(sccs.annotation(sccs.scc(2)), 1);
+    assert_eq!(sccs.annotation(sccs.scc(1)), 0);
+    assert_eq!(sccs.annotation(sccs.scc(4)), 0);
+}
+
+#[test]
+fn test_bug_max_leak_minimised() {
+    let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (3, 0), (3, 4), (4, 3)]);
+    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, |w| match w {
+        4 => MaxReached(1),
+        _ => MaxReached(0),
+    });
+
+    assert_eq!(sccs.annotation(sccs.scc(2)), 0);
+    assert_eq!(sccs.annotation(sccs.scc(3)), 1);
+    assert_eq!(sccs.annotation(sccs.scc(0)), 1);
+}
+
+#[test]
+fn test_bug_max_leak() {
+    let graph = TestGraph::new(
+        8,
+        &[
+            (0, 0),
+            (0, 18),
+            (0, 19),
+            (0, 1),
+            (0, 2),
+            (0, 7),
+            (0, 8),
+            (0, 23),
+            (18, 0),
+            (18, 12),
+            (19, 0),
+            (19, 25),
+            (12, 18),
+            (12, 3),
+            (12, 5),
+            (3, 12),
+            (3, 21),
+            (3, 22),
+            (5, 13),
+            (21, 3),
+            (22, 3),
+            (13, 5),
+            (13, 4),
+            (4, 13),
+            (4, 0),
+            (2, 11),
+            (7, 6),
+            (6, 20),
+            (20, 6),
+            (8, 17),
+            (17, 9),
+            (9, 16),
+            (16, 26),
+            (26, 15),
+            (15, 10),
+            (10, 14),
+            (14, 27),
+            (23, 24),
+        ],
+    );
+    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, |w| match w {
+        22 => MaxReached(1),
+        24 => MaxReached(2),
+        27 => MaxReached(2),
+        _ => MaxReached(0),
+    });
+
+    assert_eq!(sccs.annotation(sccs.scc(2)), 0);
+    assert_eq!(sccs.annotation(sccs.scc(7)), 0);
+    assert_eq!(sccs.annotation(sccs.scc(8)), 2);
+    assert_eq!(sccs.annotation(sccs.scc(23)), 2);
+    assert_eq!(sccs.annotation(sccs.scc(3)), 2);
+    assert_eq!(sccs.annotation(sccs.scc(0)), 2);
+}
+
+#[test]
+fn test_bug_max_zero_stick_shape() {
+    let graph = TestGraph::new(0, &[(0, 1), (1, 2), (2, 3), (3, 2), (3, 4)]);
+
+    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, |w| match w {
+        4 => MaxReached(1),
+        _ => MaxReached(0),
+    });
+
+    assert_eq!(sccs.annotation(sccs.scc(0)), 1);
+    assert_eq!(sccs.annotation(sccs.scc(1)), 1);
+    assert_eq!(sccs.annotation(sccs.scc(2)), 1);
+    assert_eq!(sccs.annotation(sccs.scc(3)), 1);
+    assert_eq!(sccs.annotation(sccs.scc(4)), 1);
+}
+
+#[test]
+fn test_min_max_in() {
+    let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (3, 0), (3, 4), (4, 3), (3, 5)]);
+    let sccs: Sccs<usize, usize, MinMaxIn> =
+        Sccs::new_with_annotation(&graph, |w| MinMaxIn { min: w, max: w });
+
+    assert_eq!(sccs.annotation(sccs.scc(2)).min, 2);
+    assert_eq!(sccs.annotation(sccs.scc(2)).max, 2);
+    assert_eq!(sccs.annotation(sccs.scc(0)).min, 0);
+    assert_eq!(sccs.annotation(sccs.scc(0)).max, 4);
+    assert_eq!(sccs.annotation(sccs.scc(3)).min, 0);
+    assert_eq!(sccs.annotation(sccs.scc(3)).max, 4);
+    assert_eq!(sccs.annotation(sccs.scc(5)).min, 5);
+}