Auto merge of #125069 - amandasystems:scc-refactor, r=nikomatsakis

Extend SCC construction to enable extra functionality

Do YOU feel like your SCC construction doesn't do enough? Then I have a patch for you! SCCs can now do *everything*! Well, almost.

This patch has been extracted from #123720. It specifically enhances
`Sccs` to allow tracking arbitrary commutative properties (think min/max mappings on nodes vs arbitrary closures) of strongly connected components, 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 reasonably straightforward "find max/min" operation during SCC construction. This is also included in this patch.

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. It may or may not have gotten easier to read for someone else.

I believe this logic can also be used in leak check, but haven't checked. Ha. ha. Ha.

5 files changed, 670 insertions, 337 deletions

diff --git a/compiler/rustc_borrowck/src/constraints/mod.rs b/compiler/rustc_borrowck/src/constraints/mod.rs
index 97408fa20d7..b54e05b2b34 100644
--- a/compiler/rustc_borrowck/src/constraints/mod.rs
+++ b/compiler/rustc_borrowck/src/constraints/mod.rs
@@ -1,4 +1,4 @@
-use rustc_data_structures::graph::scc::Sccs;
+use crate::type_check::Locations;
 use rustc_index::{IndexSlice, IndexVec};
 use rustc_middle::mir::ConstraintCategory;
 use rustc_middle::ty::{RegionVid, TyCtxt, VarianceDiagInfo};
@@ -6,8 +6,6 @@ use rustc_span::Span;
 use std::fmt;
 use std::ops::Index;
 
-use crate::type_check::Locations;
-
 pub(crate) mod graph;
 
 /// A set of NLL region constraints. These include "outlives"
@@ -45,18 +43,6 @@ impl<'tcx> OutlivesConstraintSet<'tcx> {
         graph::ConstraintGraph::new(graph::Reverse, self, num_region_vars)
     }
 
-    /// Computes cycles (SCCs) in the graph of regions. In particular,
-    /// find all regions R1, R2 such that R1: R2 and R2: R1 and group
-    /// them into an SCC, and find the relationships between SCCs.
-    pub(crate) fn compute_sccs(
-        &self,
-        constraint_graph: &graph::NormalConstraintGraph,
-        static_region: RegionVid,
-    ) -> Sccs<RegionVid, ConstraintSccIndex> {
-        let region_graph = &constraint_graph.region_graph(self, static_region);
-        Sccs::new(region_graph)
-    }
-
     pub(crate) fn outlives(
         &self,
     ) -> &IndexSlice<OutlivesConstraintIndex, OutlivesConstraint<'tcx>> {
diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs
index 0e3140ca98b..40b58500598 100644
--- a/compiler/rustc_borrowck/src/region_infer/mod.rs
+++ b/compiler/rustc_borrowck/src/region_infer/mod.rs
@@ -4,10 +4,10 @@ use std::rc::Rc;
 use rustc_data_structures::binary_search_util;
 use rustc_data_structures::frozen::Frozen;
 use rustc_data_structures::fx::{FxIndexMap, FxIndexSet};
-use rustc_data_structures::graph::scc::Sccs;
+use rustc_data_structures::graph::scc::{self, Sccs};
 use rustc_errors::Diag;
 use rustc_hir::def_id::CRATE_DEF_ID;
-use rustc_index::{IndexSlice, IndexVec};
+use rustc_index::IndexVec;
 use rustc_infer::infer::outlives::test_type_match;
 use rustc_infer::infer::region_constraints::{GenericKind, VarInfos, VerifyBound, VerifyIfEq};
 use rustc_infer::infer::{InferCtxt, NllRegionVariableOrigin, RegionVariableOrigin};
@@ -19,7 +19,7 @@ use rustc_middle::mir::{
 };
 use rustc_middle::traits::ObligationCause;
 use rustc_middle::traits::ObligationCauseCode;
-use rustc_middle::ty::{self, RegionVid, Ty, TyCtxt, TypeFoldable};
+use rustc_middle::ty::{self, RegionVid, Ty, TyCtxt, TypeFoldable, UniverseIndex};
 use rustc_mir_dataflow::points::DenseLocationMap;
 use rustc_span::Span;
 
@@ -46,6 +46,97 @@ mod reverse_sccs;
 
 pub mod values;
 
+pub type ConstraintSccs = Sccs<RegionVid, ConstraintSccIndex, RegionTracker>;
+
+/// An annotation for region graph SCCs that tracks
+/// the values of its elements.
+#[derive(Copy, Debug, Clone)]
+pub struct RegionTracker {
+    /// The largest universe of a placeholder reached from this SCC.
+    /// This includes placeholders within this SCC.
+    max_placeholder_universe_reached: UniverseIndex,
+
+    /// The smallest universe index reachable form the nodes of this SCC.
+    min_reachable_universe: UniverseIndex,
+
+    /// The representative Region Variable Id for this SCC. We prefer
+    /// placeholders over existentially quantified variables, otherwise
+    ///  it's the one with the smallest Region Variable ID.
+    representative: RegionVid,
+
+    /// Is the current representative a placeholder?
+    representative_is_placeholder: bool,
+
+    /// Is the current representative existentially quantified?
+    representative_is_existential: bool,
+}
+
+impl scc::Annotation for RegionTracker {
+    fn merge_scc(mut self, mut other: Self) -> Self {
+        // Prefer any placeholder over any existential
+        if other.representative_is_placeholder && self.representative_is_existential {
+            other.merge_min_max_seen(&self);
+            return other;
+        }
+
+        if self.representative_is_placeholder && other.representative_is_existential
+            || (self.representative <= other.representative)
+        {
+            self.merge_min_max_seen(&other);
+            return self;
+        }
+        other.merge_min_max_seen(&self);
+        other
+    }
+
+    fn merge_reached(mut self, other: Self) -> Self {
+        // No update to in-component values, only add seen values.
+        self.merge_min_max_seen(&other);
+        self
+    }
+}
+
+impl RegionTracker {
+    fn new(rvid: RegionVid, definition: &RegionDefinition<'_>) -> Self {
+        let (representative_is_placeholder, representative_is_existential) = match definition.origin
+        {
+            rustc_infer::infer::NllRegionVariableOrigin::FreeRegion => (false, false),
+            rustc_infer::infer::NllRegionVariableOrigin::Placeholder(_) => (true, false),
+            rustc_infer::infer::NllRegionVariableOrigin::Existential { .. } => (false, true),
+        };
+
+        let placeholder_universe =
+            if representative_is_placeholder { definition.universe } else { UniverseIndex::ROOT };
+
+        Self {
+            max_placeholder_universe_reached: placeholder_universe,
+            min_reachable_universe: definition.universe,
+            representative: rvid,
+            representative_is_placeholder,
+            representative_is_existential,
+        }
+    }
+    fn universe(self) -> UniverseIndex {
+        self.min_reachable_universe
+    }
+
+    fn merge_min_max_seen(&mut self, other: &Self) {
+        self.max_placeholder_universe_reached = std::cmp::max(
+            self.max_placeholder_universe_reached,
+            other.max_placeholder_universe_reached,
+        );
+
+        self.min_reachable_universe =
+            std::cmp::min(self.min_reachable_universe, other.min_reachable_universe);
+    }
+
+    /// Returns `true` if during the annotated SCC reaches a placeholder
+    /// with a universe larger than the smallest reachable one, `false` otherwise.
+    pub fn has_incompatible_universes(&self) -> bool {
+        self.universe().cannot_name(self.max_placeholder_universe_reached)
+    }
+}
+
 pub struct RegionInferenceContext<'tcx> {
     pub var_infos: VarInfos,
 
@@ -72,7 +163,7 @@ pub struct RegionInferenceContext<'tcx> {
     /// The SCC computed from `constraints` and the constraint
     /// graph. We have an edge from SCC A to SCC B if `A: B`. Used to
     /// compute the values of each region.
-    constraint_sccs: Rc<Sccs<RegionVid, ConstraintSccIndex>>,
+    constraint_sccs: Rc<ConstraintSccs>,
 
     /// Reverse of the SCC constraint graph --  i.e., an edge `A -> B` exists if
     /// `B: A`. This is used to compute the universal regions that are required
@@ -91,22 +182,6 @@ pub struct RegionInferenceContext<'tcx> {
     /// Map universe indexes to information on why we created it.
     universe_causes: FxIndexMap<ty::UniverseIndex, UniverseInfo<'tcx>>,
 
-    /// Contains the minimum universe of any variable within the same
-    /// SCC. We will ensure that no SCC contains values that are not
-    /// visible from this index.
-    scc_universes: IndexVec<ConstraintSccIndex, ty::UniverseIndex>,
-
-    /// Contains the "representative" region of each SCC.
-    /// It is defined as the one with the minimal RegionVid, favoring
-    /// free regions, then placeholders, then existential regions.
-    ///
-    /// It is a hacky way to manage checking regions for equality,
-    /// since we can 'canonicalize' each region to the representative
-    /// of its SCC and be sure that -- if they have the same repr --
-    /// they *must* be equal (though not having the same repr does not
-    /// mean they are unequal).
-    scc_representatives: IndexVec<ConstraintSccIndex, ty::RegionVid>,
-
     /// The final inferred values of the region variables; we compute
     /// one value per SCC. To get the value for any given *region*,
     /// you first find which scc it is a part of.
@@ -151,7 +226,7 @@ pub(crate) struct AppliedMemberConstraint {
 }
 
 #[derive(Debug)]
-pub(crate) struct RegionDefinition<'tcx> {
+pub struct RegionDefinition<'tcx> {
     /// What kind of variable is this -- a free region? existential
     /// variable? etc. (See the `NllRegionVariableOrigin` for more
     /// info.)
@@ -250,7 +325,7 @@ pub enum ExtraConstraintInfo {
 }
 
 #[instrument(skip(infcx, sccs), level = "debug")]
-fn sccs_info<'tcx>(infcx: &BorrowckInferCtxt<'tcx>, sccs: Rc<Sccs<RegionVid, ConstraintSccIndex>>) {
+fn sccs_info<'tcx>(infcx: &BorrowckInferCtxt<'tcx>, sccs: &ConstraintSccs) {
     use crate::renumber::RegionCtxt;
 
     let var_to_origin = infcx.reg_var_to_origin.borrow();
@@ -264,7 +339,7 @@ fn sccs_info<'tcx>(infcx: &BorrowckInferCtxt<'tcx>, sccs: Rc<Sccs<RegionVid, Con
     }
     debug!("{}", reg_vars_to_origins_str);
 
-    let num_components = sccs.scc_data().ranges().len();
+    let num_components = sccs.num_sccs();
     let mut components = vec![FxIndexSet::default(); num_components];
 
     for (reg_var_idx, scc_idx) in sccs.scc_indices().iter().enumerate() {
@@ -301,10 +376,11 @@ fn sccs_info<'tcx>(infcx: &BorrowckInferCtxt<'tcx>, sccs: Rc<Sccs<RegionVid, Con
 
     let mut scc_node_to_edges = FxIndexMap::default();
     for (scc_idx, repr) in components_representatives.iter() {
-        let edges_range = sccs.scc_data().ranges()[*scc_idx].clone();
-        let edges = &sccs.scc_data().all_successors()[edges_range];
-        let edge_representatives =
-            edges.iter().map(|scc_idx| components_representatives[scc_idx]).collect::<Vec<_>>();
+        let edge_representatives = sccs
+            .successors(*scc_idx)
+            .iter()
+            .map(|scc_idx| components_representatives[scc_idx])
+            .collect::<Vec<_>>();
         scc_node_to_edges.insert((scc_idx, repr), edge_representatives);
     }
 
@@ -320,7 +396,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     /// The `outlives_constraints` and `type_tests` are an initial set
     /// of constraints produced by the MIR type check.
     pub(crate) fn new(
-        _infcx: &BorrowckInferCtxt<'tcx>,
+        infcx: &BorrowckInferCtxt<'tcx>,
         var_infos: VarInfos,
         universal_regions: Rc<UniversalRegions<'tcx>>,
         placeholder_indices: Rc<PlaceholderIndices>,
@@ -343,13 +419,20 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             .map(|info| RegionDefinition::new(info.universe, info.origin))
             .collect();
 
+        let fr_static = universal_regions.fr_static;
         let constraints = Frozen::freeze(outlives_constraints);
         let constraint_graph = Frozen::freeze(constraints.graph(definitions.len()));
-        let fr_static = universal_regions.fr_static;
-        let constraint_sccs = Rc::new(constraints.compute_sccs(&constraint_graph, fr_static));
+        let constraint_sccs = {
+            let constraint_graph = constraints.graph(definitions.len());
+            let region_graph = &constraint_graph.region_graph(&constraints, fr_static);
+            let sccs = ConstraintSccs::new_with_annotation(&region_graph, |r| {
+                RegionTracker::new(r, &definitions[r])
+            });
+            Rc::new(sccs)
+        };
 
         if cfg!(debug_assertions) {
-            sccs_info(_infcx, constraint_sccs.clone());
+            sccs_info(infcx, &constraint_sccs);
         }
 
         let mut scc_values =
@@ -360,10 +443,6 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             scc_values.merge_liveness(scc, region, &liveness_constraints);
         }
 
-        let scc_universes = Self::compute_scc_universes(&constraint_sccs, &definitions);
-
-        let scc_representatives = Self::compute_scc_representatives(&constraint_sccs, &definitions);
-
         let member_constraints =
             Rc::new(member_constraints_in.into_mapped(|r| constraint_sccs.scc(r)));
 
@@ -378,8 +457,6 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             member_constraints,
             member_constraints_applied: Vec::new(),
             universe_causes,
-            scc_universes,
-            scc_representatives,
             scc_values,
             type_tests,
             universal_regions,
@@ -391,123 +468,6 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         result
     }
 
-    /// Each SCC is the combination of many region variables which
-    /// have been equated. Therefore, we can associate a universe with
-    /// each SCC which is minimum of all the universes of its
-    /// constituent regions -- this is because whatever value the SCC
-    /// takes on must be a value that each of the regions within the
-    /// SCC could have as well. This implies that the SCC must have
-    /// the minimum, or narrowest, universe.
-    fn compute_scc_universes(
-        constraint_sccs: &Sccs<RegionVid, ConstraintSccIndex>,
-        definitions: &IndexSlice<RegionVid, RegionDefinition<'tcx>>,
-    ) -> IndexVec<ConstraintSccIndex, ty::UniverseIndex> {
-        let num_sccs = constraint_sccs.num_sccs();
-        let mut scc_universes = IndexVec::from_elem_n(ty::UniverseIndex::MAX, num_sccs);
-
-        debug!("compute_scc_universes()");
-
-        // For each region R in universe U, ensure that the universe for the SCC
-        // that contains R is "no bigger" than U. This effectively sets the universe
-        // for each SCC to be the minimum of the regions within.
-        for (region_vid, region_definition) in definitions.iter_enumerated() {
-            let scc = constraint_sccs.scc(region_vid);
-            let scc_universe = &mut scc_universes[scc];
-            let scc_min = std::cmp::min(region_definition.universe, *scc_universe);
-            if scc_min != *scc_universe {
-                *scc_universe = scc_min;
-                debug!(
-                    "compute_scc_universes: lowered universe of {scc:?} to {scc_min:?} \
-                    because it contains {region_vid:?} in {region_universe:?}",
-                    scc = scc,
-                    scc_min = scc_min,
-                    region_vid = region_vid,
-                    region_universe = region_definition.universe,
-                );
-            }
-        }
-
-        // Walk each SCC `A` and `B` such that `A: B`
-        // and ensure that universe(A) can see universe(B).
-        //
-        // This serves to enforce the 'empty/placeholder' hierarchy
-        // (described in more detail on `RegionKind`):
-        //
-        // ```
-        // static -----+
-        //   |         |
-        // empty(U0) placeholder(U1)
-        //   |      /
-        // empty(U1)
-        // ```
-        //
-        // In particular, imagine we have variables R0 in U0 and R1
-        // created in U1, and constraints like this;
-        //
-        // ```
-        // R1: !1 // R1 outlives the placeholder in U1
-        // R1: R0 // R1 outlives R0
-        // ```
-        //
-        // Here, we wish for R1 to be `'static`, because it
-        // cannot outlive `placeholder(U1)` and `empty(U0)` any other way.
-        //
-        // Thanks to this loop, what happens is that the `R1: R0`
-        // constraint lowers the universe of `R1` to `U0`, which in turn
-        // means that the `R1: !1` constraint will (later) cause
-        // `R1` to become `'static`.
-        for scc_a in constraint_sccs.all_sccs() {
-            for &scc_b in constraint_sccs.successors(scc_a) {
-                let scc_universe_a = scc_universes[scc_a];
-                let scc_universe_b = scc_universes[scc_b];
-                let scc_universe_min = std::cmp::min(scc_universe_a, scc_universe_b);
-                if scc_universe_a != scc_universe_min {
-                    scc_universes[scc_a] = scc_universe_min;
-
-                    debug!(
-                        "compute_scc_universes: lowered universe of {scc_a:?} to {scc_universe_min:?} \
-                        because {scc_a:?}: {scc_b:?} and {scc_b:?} is in universe {scc_universe_b:?}",
-                        scc_a = scc_a,
-                        scc_b = scc_b,
-                        scc_universe_min = scc_universe_min,
-                        scc_universe_b = scc_universe_b
-                    );
-                }
-            }
-        }
-
-        debug!("compute_scc_universes: scc_universe = {:#?}", scc_universes);
-
-        scc_universes
-    }
-
-    /// For each SCC, we compute a unique `RegionVid`. See the
-    /// `scc_representatives` field of `RegionInferenceContext` for
-    /// more details.
-    fn compute_scc_representatives(
-        constraints_scc: &Sccs<RegionVid, ConstraintSccIndex>,
-        definitions: &IndexSlice<RegionVid, RegionDefinition<'tcx>>,
-    ) -> IndexVec<ConstraintSccIndex, ty::RegionVid> {
-        let num_sccs = constraints_scc.num_sccs();
-        let mut scc_representatives = IndexVec::from_elem_n(RegionVid::MAX, num_sccs);
-
-        // Iterate over all RegionVids *in-order* and pick the least RegionVid as the
-        // representative of its SCC. This naturally prefers free regions over others.
-        for (vid, def) in definitions.iter_enumerated() {
-            let repr = &mut scc_representatives[constraints_scc.scc(vid)];
-            if *repr == ty::RegionVid::MAX {
-                *repr = vid;
-            } else if matches!(def.origin, NllRegionVariableOrigin::Placeholder(_))
-                && matches!(definitions[*repr].origin, NllRegionVariableOrigin::Existential { .. })
-            {
-                // Pick placeholders over existentials even if they have a greater RegionVid.
-                *repr = vid;
-            }
-        }
-
-        scc_representatives
-    }
-
     /// Initializes the region variables for each universally
     /// quantified region (lifetime parameter). The first N variables
     /// always correspond to the regions appearing in the function
@@ -528,12 +488,45 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     /// and (b) any universally quantified regions that it outlives,
     /// which in this case is just itself. R1 (`'b`) in contrast also
     /// outlives `'a` and hence contains R0 and R1.
+    ///
+    /// This bit of logic also handles invalid universe relations
+    /// for higher-kinded types.
+    ///
+    /// We Walk each SCC `A` and `B` such that `A: B`
+    /// and ensure that universe(A) can see universe(B).
+    ///
+    /// This serves to enforce the 'empty/placeholder' hierarchy
+    /// (described in more detail on `RegionKind`):
+    ///
+    /// ```ignore (illustrative)
+    /// static -----+
+    ///   |         |
+    /// empty(U0) placeholder(U1)
+    ///   |      /
+    /// empty(U1)
+    /// ```
+    ///
+    /// In particular, imagine we have variables R0 in U0 and R1
+    /// created in U1, and constraints like this;
+    ///
+    /// ```ignore (illustrative)
+    /// R1: !1 // R1 outlives the placeholder in U1
+    /// R1: R0 // R1 outlives R0
+    /// ```
+    ///
+    /// Here, we wish for R1 to be `'static`, because it
+    /// cannot outlive `placeholder(U1)` and `empty(U0)` any other way.
+    ///
+    /// Thanks to this loop, what happens is that the `R1: R0`
+    /// constraint has lowered the universe of `R1` to `U0`, which in turn
+    /// means that the `R1: !1` constraint here will cause
+    /// `R1` to become `'static`.
     fn init_free_and_bound_regions(&mut self) {
         // Update the names (if any)
         // This iterator has unstable order but we collect it all into an IndexVec
         for (external_name, variable) in self.universal_regions.named_universal_regions() {
             debug!(
-                "init_universal_regions: region {:?} has external name {:?}",
+                "init_free_and_bound_regions: region {:?} has external name {:?}",
                 variable, external_name
             );
             self.definitions[variable].external_name = Some(external_name);
@@ -559,7 +552,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
                     // its universe `ui` and its extensions. So we
                     // can't just add it into `scc` unless the
                     // universe of the scc can name this region.
-                    let scc_universe = self.scc_universes[scc];
+                    let scc_universe = self.scc_universe(scc);
                     if scc_universe.can_name(placeholder.universe) {
                         self.scc_values.add_element(scc, placeholder);
                     } else {
@@ -640,8 +633,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
 
     /// Returns access to the value of `r` for debugging purposes.
     pub(crate) fn region_universe(&self, r: RegionVid) -> ty::UniverseIndex {
-        let scc = self.constraint_sccs.scc(r);
-        self.scc_universes[scc]
+        self.scc_universe(self.constraint_sccs.scc(r))
     }
 
     /// Once region solving has completed, this function will return the member constraints that
@@ -737,8 +729,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         // SCC. For each SCC, we visit its successors and compute
         // their values, then we union all those values to get our
         // own.
-        let constraint_sccs = self.constraint_sccs.clone();
-        for scc in constraint_sccs.all_sccs() {
+        for scc in self.constraint_sccs.all_sccs() {
             self.compute_value_for_scc(scc);
         }
 
@@ -817,20 +808,15 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         // if one exists.
         for c_r in &mut choice_regions {
             let scc = self.constraint_sccs.scc(*c_r);
-            *c_r = self.scc_representatives[scc];
+            *c_r = self.scc_representative(scc);
         }
 
         // If the member region lives in a higher universe, we currently choose
         // the most conservative option by leaving it unchanged.
-        if self.scc_universes[scc] != ty::UniverseIndex::ROOT {
+
+        if !self.constraint_sccs().annotation(scc).universe().is_root() {
             return;
         }
-        debug_assert!(
-            self.scc_values.placeholders_contained_in(scc).next().is_none(),
-            "scc {:?} in a member constraint has placeholder value: {:?}",
-            scc,
-            self.scc_values.region_value_str(scc),
-        );
 
         // The existing value for `scc` is a lower-bound. This will
         // consist of some set `{P} + {LB}` of points `{P}` and
@@ -900,12 +886,13 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     /// in `scc_a`. Used during constraint propagation, and only once
     /// the value of `scc_b` has been computed.
     fn universe_compatible(&self, scc_b: ConstraintSccIndex, scc_a: ConstraintSccIndex) -> bool {
-        let universe_a = self.scc_universes[scc_a];
+        let universe_a = self.constraint_sccs().annotation(scc_a).universe();
+        let universe_b = self.constraint_sccs().annotation(scc_b).universe();
 
         // Quick check: if scc_b's declared universe is a subset of
         // scc_a's declared universe (typically, both are ROOT), then
         // it cannot contain any problematic universe elements.
-        if universe_a.can_name(self.scc_universes[scc_b]) {
+        if universe_a.can_name(universe_b) {
             return true;
         }
 
@@ -1033,7 +1020,9 @@ impl<'tcx> RegionInferenceContext<'tcx> {
 
         debug!(
             "lower_bound = {:?} r_scc={:?} universe={:?}",
-            lower_bound, r_scc, self.scc_universes[r_scc]
+            lower_bound,
+            r_scc,
+            self.constraint_sccs.annotation(r_scc).universe()
         );
 
         // If the type test requires that `T: 'a` where `'a` is a
@@ -1321,7 +1310,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         tcx.fold_regions(value, |r, _db| {
             let vid = self.to_region_vid(r);
             let scc = self.constraint_sccs.scc(vid);
-            let repr = self.scc_representatives[scc];
+            let repr = self.scc_representative(scc);
             ty::Region::new_var(tcx, repr)
         })
     }
@@ -1547,6 +1536,11 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         }
     }
 
+    /// The minimum universe of any variable reachable from this
+    /// SCC, inside or outside of it.
+    fn scc_universe(&self, scc: ConstraintSccIndex) -> UniverseIndex {
+        self.constraint_sccs().annotation(scc).universe()
+    }
     /// Checks the final value for the free region `fr` to see if it
     /// grew too large. In particular, examine what `end(X)` points
     /// wound up in `fr`'s final value; for each `end(X)` where `X !=
@@ -1566,8 +1560,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
 
         // Because this free region must be in the ROOT universe, we
         // know it cannot contain any bound universes.
-        assert!(self.scc_universes[longer_fr_scc].is_root());
-        debug_assert!(self.scc_values.placeholders_contained_in(longer_fr_scc).next().is_none());
+        assert!(self.scc_universe(longer_fr_scc).is_root());
 
         // Only check all of the relations for the main representative of each
         // SCC, otherwise just check that we outlive said representative. This
@@ -1575,7 +1568,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         // closures.
         // Note that the representative will be a universal region if there is
         // one in this SCC, so we will always check the representative here.
-        let representative = self.scc_representatives[longer_fr_scc];
+        let representative = self.scc_representative(longer_fr_scc);
         if representative != longer_fr {
             if let RegionRelationCheckResult::Error = self.check_universal_region_relation(
                 longer_fr,
@@ -1796,16 +1789,14 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     /// `true` if `r1` cannot name that placeholder in its
     /// value; otherwise, returns `false`.
     pub(crate) fn cannot_name_placeholder(&self, r1: RegionVid, r2: RegionVid) -> bool {
-        debug!("cannot_name_value_of(r1={:?}, r2={:?})", r1, r2);
-
         match self.definitions[r2].origin {
             NllRegionVariableOrigin::Placeholder(placeholder) => {
-                let universe1 = self.definitions[r1].universe;
+                let r1_universe = self.definitions[r1].universe;
                 debug!(
-                    "cannot_name_value_of: universe1={:?} placeholder={:?}",
-                    universe1, placeholder
+                    "cannot_name_value_of: universe1={r1_universe:?} placeholder={:?}",
+                    placeholder
                 );
-                universe1.cannot_name(placeholder.universe)
+                r1_universe.cannot_name(placeholder.universe)
             }
 
             NllRegionVariableOrigin::FreeRegion | NllRegionVariableOrigin::Existential { .. } => {
@@ -1835,6 +1826,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     ///
     /// Returns: a series of constraints as well as the region `R`
     /// that passed the target test.
+    #[instrument(skip(self, target_test), ret)]
     pub(crate) fn find_constraint_paths_between_regions(
         &self,
         from_region: RegionVid,
@@ -1932,7 +1924,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     #[instrument(skip(self), level = "trace", ret)]
     pub(crate) fn find_sub_region_live_at(&self, fr1: RegionVid, location: Location) -> RegionVid {
         trace!(scc = ?self.constraint_sccs.scc(fr1));
-        trace!(universe = ?self.scc_universes[self.constraint_sccs.scc(fr1)]);
+        trace!(universe = ?self.region_universe(fr1));
         self.find_constraint_paths_between_regions(fr1, |r| {
             // First look for some `r` such that `fr1: r` and `r` is live at `location`
             trace!(?r, liveness_constraints=?self.liveness_constraints.pretty_print_live_points(r));
@@ -2252,8 +2244,8 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     /// This can be used to quickly under-approximate the regions which are equal to each other
     /// and their relative orderings.
     // This is `pub` because it's used by unstable external borrowck data users, see `consumers.rs`.
-    pub fn constraint_sccs(&self) -> &Sccs<RegionVid, ConstraintSccIndex> {
-        self.constraint_sccs.as_ref()
+    pub fn constraint_sccs(&self) -> &ConstraintSccs {
+        &self.constraint_sccs
     }
 
     /// Access to the region graph, built from the outlives constraints.
@@ -2282,6 +2274,18 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         let point = self.liveness_constraints.point_from_location(location);
         self.liveness_constraints.is_loan_live_at(loan_idx, point)
     }
+
+    /// Returns the representative `RegionVid` for a given SCC.
+    /// See `RegionTracker` for how a region variable ID is chosen.
+    ///
+    /// It is a hacky way to manage checking regions for equality,
+    /// since we can 'canonicalize' each region to the representative
+    /// of its SCC and be sure that -- if they have the same repr --
+    /// they *must* be equal (though not having the same repr does not
+    /// mean they are unequal).
+    fn scc_representative(&self, scc: ConstraintSccIndex) -> RegionVid {
+        self.constraint_sccs.annotation(scc).representative
+    }
 }
 
 impl<'tcx> RegionDefinition<'tcx> {
diff --git a/compiler/rustc_borrowck/src/region_infer/opaque_types.rs b/compiler/rustc_borrowck/src/region_infer/opaque_types.rs
index 06adb686ed4..51c3648d730 100644
--- a/compiler/rustc_borrowck/src/region_infer/opaque_types.rs
+++ b/compiler/rustc_borrowck/src/region_infer/opaque_types.rs
@@ -85,7 +85,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
                     // Use the SCC representative instead of directly using `region`.
                     // See [rustc-dev-guide chapter] § "Strict lifetime equality".
                     let scc = self.constraint_sccs.scc(region.as_var());
-                    let vid = self.scc_representatives[scc];
+                    let vid = self.scc_representative(scc);
                     let named = match self.definitions[vid].origin {
                         // Iterate over all universal regions in a consistent order and find the
                         // *first* equal region. This makes sure that equal lifetimes will have
@@ -213,7 +213,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
                 let scc = self.constraint_sccs.scc(vid);
 
                 // Special handling of higher-ranked regions.
-                if !self.scc_universes[scc].is_root() {
+                if !self.scc_universe(scc).is_root() {
                     match self.scc_values.placeholders_contained_in(scc).enumerate().last() {
                         // If the region contains a single placeholder then they're equal.
                         Some((0, placeholder)) => {
diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs
index 7f36e4ca16d..8b96b36a851 100644
--- a/compiler/rustc_data_structures/src/graph/scc/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs
@@ -4,52 +4,119 @@
 //! 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,
+/// the max/min element of the SCC, or all of the above.
+///
+/// Concretely, the both merge operations must commute, e.g. where `merge`
+/// is `merge_scc` and `merge_reached`: `a.merge(b) == b.merge(a)`
+///
+/// In general, what you want is probably always min/max according
+/// to some ordering, potentially with side constraints (min x such
+/// that P holds).
+pub trait Annotation: Debug + Copy {
+    /// Merge two existing annotations into one during
+    /// path compression.o
+    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 scc_data(&self) -> &SccData<S> {
-        &self.scc_data
+    pub fn annotation(&self, scc: S) -> A {
+        self.scc_data.annotation(scc)
+    }
+
+    pub fn scc_indices(&self) -> &IndexSlice<N, S> {
+        &self.scc_indices
     }
 
     /// Returns the number of SCCs in the graph.
@@ -90,7 +157,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 +165,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 +199,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 +244,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 its current annotation is
+    /// `annotation`.
     ///
     /// 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 merged annotation is `annotation`.
+    /// Note that an SCC can have several cycles, so its final annotation
+    /// is the merged value of all its member annotations.
+    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 +281,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 +314,10 @@ 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 current annotation of the SCC.
+    ///
     /// [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 +325,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 +343,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 +359,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 +382,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 +398,40 @@ 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!
+        // Note that there are two different states being assigned: the root state, and
+        // a potentially derived version of the root state for non-root nodes in the chain.
+        let (root_state, assigned_state) = {
+            loop {
+                debug!("find_state(r = {node:?} in state {:?})", self.node_states[node]);
+                match self.node_states[node] {
+                    // This must have been the first and only state since it is unexplored*;
+                    // no update needed! * Unless there is a bug :')
+                    s @ NodeState::NotVisited => return s,
+                    // We are in a completely discovered SCC; every node on our path is in that SCC:
+                    s @ NodeState::InCycle { .. } => break (s, s),
+                    // The Interesting Third Base Case: we are a path back to a root node
+                    // still being explored. Now we need that node to keep its state and
+                    // every other node to be recorded as being in whatever component that
+                    // ends up in.
+                    s @ NodeState::BeingVisited { depth, .. } => {
+                        break (s, NodeState::InCycleWith { parent: self.node_stack[depth] });
+                    }
+                    // We are not at the head of a path; keep compressing it!
+                    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;
+                    }
                 }
             }
         };
@@ -365,10 +473,14 @@ where
         // Move backwards until we found the node where we started. We
         // will know when we hit the state where previous_node == node.
         loop {
-            // Back at the beginning, we can return.
+            // Back at the beginning, we can return. Note that we return the root state.
+            // This is becuse for components being explored, we would otherwise get a
+            // `node_state[n] = InCycleWith{ parent: n }` and that's wrong.
             if previous_node == node {
-                return node_state;
+                return root_state;
             }
+            debug!("Compressing {node:?} down to {previous_node:?} with state {assigned_state:?}");
+
             // Update to previous node in the link.
             match self.node_states[previous_node] {
                 NodeState::InCycleWith { parent: previous } => {
@@ -376,34 +488,14 @@ where
                     previous_node = previous;
                 }
                 // Only InCycleWith nodes were added to the reverse linked list.
-                other => panic!("Invalid previous link while compressing cycle: {other:?}"),
+                other => unreachable!("Invalid previous link while compressing cycle: {other:?}"),
             }
 
-            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
-                // at that depth.
-                NodeState::BeingVisited { depth } => {
-                    self.node_states[node] =
-                        NodeState::InCycleWith { parent: self.node_stack[depth] };
-                }
-                // 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:?}")
-                }
-            }
+            // Update the node state to the (potentially derived) state.
+            // If the root is still being explored, this is
+            // `InCycleWith{ parent: <root node>}`, otherwise
+            // `assigned_state == root_state`.
+            self.node_states[node] = assigned_state;
         }
     }
 
@@ -413,30 +505,36 @@ 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,
+            current_component_annotation: (self.to_annotation)(initial),
         }];
 
         let mut return_value = None;
@@ -445,18 +543,26 @@ 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.
+            if node != initial {
+                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 +570,10 @@ 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: *current_component_annotation,
+                    };
                     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);
+}