Move placeholder handling to a proper preprocessing step

This commit breaks out the logic of placheolder rewriting
into its own preprocessing step.

The only functional change from this is that the preprocessing
step (where extra `r: 'static` constraints are added) is
performed upstream of Polonius legacy, finally affecting
Polonius. That is mostly a by-product, though.

6 files changed, 414 insertions, 299 deletions

diff --git a/compiler/rustc_borrowck/src/constraints/mod.rs b/compiler/rustc_borrowck/src/constraints/mod.rs
index 514bbfe359b..99ddccabd15 100644
--- a/compiler/rustc_borrowck/src/constraints/mod.rs
+++ b/compiler/rustc_borrowck/src/constraints/mod.rs
@@ -5,11 +5,9 @@ use rustc_index::{IndexSlice, IndexVec};
 use rustc_middle::mir::ConstraintCategory;
 use rustc_middle::ty::{RegionVid, TyCtxt, VarianceDiagInfo};
 use rustc_span::Span;
-use tracing::{debug, instrument};
+use tracing::debug;
 
-use crate::region_infer::{AnnotatedSccs, ConstraintSccs, RegionDefinition, SccAnnotations};
 use crate::type_check::Locations;
-use crate::universal_regions::UniversalRegions;
 
 pub(crate) mod graph;
 
@@ -53,112 +51,6 @@ impl<'tcx> OutlivesConstraintSet<'tcx> {
     ) -> &IndexSlice<OutlivesConstraintIndex, OutlivesConstraint<'tcx>> {
         &self.outlives
     }
-
-    /// 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,
-        static_region: RegionVid,
-        definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>,
-    ) -> AnnotatedSccs {
-        let constraint_graph = self.graph(definitions.len());
-        let region_graph = &constraint_graph.region_graph(self, static_region);
-        let mut annotation_visitor = SccAnnotations::new(definitions);
-        (
-            ConstraintSccs::new_with_annotation(&region_graph, &mut annotation_visitor),
-            annotation_visitor.scc_to_annotation,
-        )
-    }
-
-    /// This method handles Universe errors by rewriting the constraint
-    /// graph. For each strongly connected component in the constraint
-    /// graph such that there is a series of constraints
-    ///    A: B: C: ... : X  where
-    /// A's universe is smaller than X's and A is a placeholder,
-    /// add a constraint that A: 'static. This is a safe upper bound
-    /// in the face of borrow checker/trait solver limitations that will
-    /// eventually go away.
-    ///
-    /// For a more precise definition, see the documentation for
-    /// [`crate::region_infer::RegionTracker`].
-    ///
-    /// This edge case used to be handled during constraint propagation
-    /// by iterating over the strongly connected components in the constraint
-    /// graph while maintaining a set of bookkeeping mappings similar
-    /// to what is stored in `RegionTracker` and manually adding 'static as
-    /// needed.
-    ///
-    /// It was rewritten as part of the Polonius project with the goal of moving
-    /// higher-kindedness concerns out of the path of the borrow checker,
-    /// for two reasons:
-    ///
-    /// 1. Implementing Polonius is difficult enough without also
-    ///     handling them.
-    /// 2. The long-term goal is to handle higher-kinded concerns
-    ///     in the trait solver, where they belong. This avoids
-    ///     logic duplication and allows future trait solvers
-    ///     to compute better bounds than for example our
-    ///     "must outlive 'static" here.
-    ///
-    /// This code is a stop-gap measure in preparation for the future trait solver.
-    ///
-    /// Every constraint added by this method is an
-    /// internal `IllegalUniverse` constraint.
-    #[instrument(skip(self, universal_regions, definitions))]
-    pub(crate) fn add_outlives_static(
-        &mut self,
-        universal_regions: &UniversalRegions<'tcx>,
-        definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>,
-    ) -> AnnotatedSccs {
-        let fr_static = universal_regions.fr_static;
-        let (sccs, annotations) = self.compute_sccs(fr_static, definitions);
-
-        // Changed to `true` if we added any constraints to `self` and need to
-        // recompute SCCs.
-        let mut added_constraints = false;
-
-        for scc in sccs.all_sccs() {
-            // No point in adding 'static: 'static!
-            // This micro-optimisation makes somewhat sense
-            // because static outlives *everything*.
-            if scc == sccs.scc(fr_static) {
-                continue;
-            }
-
-            let annotation = annotations[scc];
-
-            // If this SCC participates in a universe violation,
-            // e.g. if it reaches a region with a universe smaller than
-            // the largest region reached, add a requirement that it must
-            // outlive `'static`.
-            if annotation.has_incompatible_universes() {
-                // Optimisation opportunity: this will add more constraints than
-                // needed for correctness, since an SCC upstream of another with
-                // a universe violation will "infect" its downstream SCCs to also
-                // outlive static.
-                added_constraints = true;
-                let scc_representative_outlives_static = OutlivesConstraint {
-                    sup: annotation.representative,
-                    sub: fr_static,
-                    category: ConstraintCategory::IllegalUniverse,
-                    locations: Locations::All(rustc_span::DUMMY_SP),
-                    span: rustc_span::DUMMY_SP,
-                    variance_info: VarianceDiagInfo::None,
-                    from_closure: false,
-                };
-                self.push(scc_representative_outlives_static);
-            }
-        }
-
-        if added_constraints {
-            // We changed the constraint set and so must recompute SCCs.
-            self.compute_sccs(fr_static, definitions)
-        } else {
-            // If we didn't add any back-edges; no more work needs doing
-            (sccs, annotations)
-        }
-    }
 }
 
 impl<'tcx> Index<OutlivesConstraintIndex> for OutlivesConstraintSet<'tcx> {
diff --git a/compiler/rustc_borrowck/src/eliminate_placeholders.rs b/compiler/rustc_borrowck/src/eliminate_placeholders.rs
new file mode 100644
index 00000000000..e8e1acbd7a5
--- /dev/null
+++ b/compiler/rustc_borrowck/src/eliminate_placeholders.rs
@@ -0,0 +1,371 @@
+//! Logic for lowering higher-kinded outlives constraints
+//! (with placeholders and universes) and turn them into regular
+//! outlives constraints.
+//!
+//! This logic is provisional and should be removed once the trait
+//! solver can handle this kind of constraint.
+use rustc_data_structures::frozen::Frozen;
+use rustc_data_structures::fx::{FxHashSet, FxIndexMap};
+use rustc_data_structures::graph::scc;
+use rustc_data_structures::graph::scc::Sccs;
+use rustc_index::IndexVec;
+use rustc_middle::mir::ConstraintCategory;
+use rustc_middle::ty::{RegionVid, UniverseIndex};
+use tracing::debug;
+
+use crate::constraints::{ConstraintSccIndex, OutlivesConstraintSet};
+use crate::consumers::OutlivesConstraint;
+use crate::diagnostics::UniverseInfo;
+use crate::member_constraints::MemberConstraintSet;
+use crate::region_infer::values::{LivenessValues, PlaceholderIndices};
+use crate::region_infer::{ConstraintSccs, RegionDefinition, TypeTest};
+use crate::ty::VarianceDiagInfo;
+use crate::type_check::free_region_relations::UniversalRegionRelations;
+use crate::type_check::{Locations, MirTypeckRegionConstraints};
+use crate::universal_regions::UniversalRegions;
+use crate::{BorrowckInferCtxt, NllRegionVariableOrigin};
+
+/// A set of outlives constraints after rewriting to remove
+/// higher-kinded constraints.
+pub(crate) struct LoweredConstraints<'tcx> {
+    pub(crate) constraint_sccs: Sccs<RegionVid, ConstraintSccIndex>,
+    pub(crate) definitions: Frozen<IndexVec<RegionVid, RegionDefinition<'tcx>>>,
+    pub(crate) scc_annotations: IndexVec<ConstraintSccIndex, RegionTracker>,
+    pub(crate) member_constraints: MemberConstraintSet<'tcx, RegionVid>,
+    pub(crate) outlives_constraints: OutlivesConstraintSet<'tcx>,
+    pub(crate) type_tests: Vec<TypeTest<'tcx>>,
+    pub(crate) liveness_constraints: LivenessValues,
+    pub(crate) universe_causes: FxIndexMap<UniverseIndex, UniverseInfo<'tcx>>,
+    pub(crate) placeholder_indices: PlaceholderIndices,
+}
+
+impl<'d, 'tcx, A: scc::Annotation> SccAnnotations<'d, 'tcx, A> {
+    pub(crate) fn init(definitions: &'d IndexVec<RegionVid, RegionDefinition<'tcx>>) -> Self {
+        Self { scc_to_annotation: IndexVec::new(), definitions }
+    }
+}
+
+/// A Visitor for SCC annotation construction.
+pub(crate) struct SccAnnotations<'d, 'tcx, A: scc::Annotation> {
+    pub(crate) scc_to_annotation: IndexVec<ConstraintSccIndex, A>,
+    definitions: &'d IndexVec<RegionVid, RegionDefinition<'tcx>>,
+}
+
+impl scc::Annotations<RegionVid> for SccAnnotations<'_, '_, RegionTracker> {
+    fn new(&self, element: RegionVid) -> RegionTracker {
+        RegionTracker::new(element, &self.definitions[element])
+    }
+
+    fn annotate_scc(&mut self, scc: ConstraintSccIndex, annotation: RegionTracker) {
+        let idx = self.scc_to_annotation.push(annotation);
+        assert!(idx == scc);
+    }
+
+    type Ann = RegionTracker;
+    type SccIdx = ConstraintSccIndex;
+}
+
+/// An annotation for region graph SCCs that tracks
+/// the values of its elements. This annotates a single SCC.
+#[derive(Copy, Debug, Clone)]
+pub(crate) 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.
+    pub(crate) representative: RegionVid,
+
+    /// Is the current representative a placeholder?
+    representative_is_placeholder: bool,
+
+    /// Is the current representative existentially quantified?
+    representative_is_existential: bool,
+}
+
+impl RegionTracker {
+    pub(crate) fn new(rvid: RegionVid, definition: &RegionDefinition<'_>) -> Self {
+        let (representative_is_placeholder, representative_is_existential) = match definition.origin
+        {
+            NllRegionVariableOrigin::FreeRegion => (false, false),
+            NllRegionVariableOrigin::Placeholder(_) => (true, false),
+            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,
+        }
+    }
+
+    /// The smallest-indexed universe reachable from and/or in this SCC.
+    pub(crate) fn min_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(crate) fn has_incompatible_universes(&self) -> bool {
+        self.min_universe().cannot_name(self.max_placeholder_universe_reached)
+    }
+
+    /// Determine if the tracked universes of the two SCCs
+    /// are compatible.
+    pub(crate) fn universe_compatible_with(&self, other: Self) -> bool {
+        self.min_universe().can_name(other.min_universe())
+            || self.min_universe().can_name(other.max_placeholder_universe_reached)
+    }
+}
+
+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
+    }
+}
+
+/// Determines if the region variable definitions contain
+/// placeholers, and compute them for later use.
+fn region_definitions<'tcx>(
+    universal_regions: &UniversalRegions<'tcx>,
+    infcx: &BorrowckInferCtxt<'tcx>,
+) -> (Frozen<IndexVec<RegionVid, RegionDefinition<'tcx>>>, bool) {
+    let var_infos = infcx.get_region_var_infos();
+    // Create a RegionDefinition for each inference variable. This happens here because
+    // it allows us to sneak in a cheap check for placeholders. Otherwise, its proper home
+    // is in `RegionInferenceContext::new()`, probably.
+    let mut definitions = IndexVec::with_capacity(var_infos.len());
+    let mut has_placeholders = false;
+
+    for info in var_infos.iter() {
+        let definition = RegionDefinition::new(info);
+        has_placeholders |= matches!(definition.origin, NllRegionVariableOrigin::Placeholder(_));
+        definitions.push(definition);
+    }
+
+    // Add external names from universal regions in fun function definitions.
+    for (external_name, variable) in universal_regions.named_universal_regions_iter() {
+        debug!("region {:?} has external name {:?}", variable, external_name);
+        definitions[variable].external_name = Some(external_name);
+    }
+    (Frozen::freeze(definitions), has_placeholders)
+}
+
+/// This method handles Universe errors by rewriting the constraint
+/// graph. For each strongly connected component in the constraint
+/// graph such that there is a series of constraints
+///    A: B: C: ... : X  where
+/// A's universe is smaller than X's and A is a placeholder,
+/// add a constraint that A: 'static. This is a safe upper bound
+/// in the face of borrow checker/trait solver limitations that will
+/// eventually go away.
+///
+/// For a more precise definition, see the documentation for
+/// [`RegionTracker`] and its methods!.
+///
+/// Since universes can also be involved in errors (if one placeholder
+/// transitively outlives another), this function also flags those.
+///
+/// Additionally, it similarly rewrites type-tests.
+///
+/// This edge case used to be handled during constraint propagation
+/// by iterating over the strongly connected components in the constraint
+/// graph while maintaining a set of bookkeeping mappings similar
+/// to what is stored in `RegionTracker` and manually adding 'sttaic as
+/// needed.
+///
+/// It was rewritten as part of the Polonius project with the goal of moving
+/// higher-kindedness concerns out of the path of the borrow checker,
+/// for two reasons:
+///
+/// 1. Implementing Polonius is difficult enough without also
+///     handling them.
+/// 2. The long-term goal is to handle higher-kinded concerns
+///     in the trait solver, where they belong. This avoids
+///     logic duplication and allows future trait solvers
+///     to compute better bounds than for example our
+///     "must outlive 'static" here.
+///
+/// This code is a stop-gap measure in preparation for the future trait solver.
+///
+/// Every constraint added by this method is an internal `IllegalUniverse` constraint.
+pub(crate) fn rewrite_higher_kinded_outlives_as_constraints<'tcx>(
+    constraints: MirTypeckRegionConstraints<'tcx>,
+    universal_region_relations: &Frozen<UniversalRegionRelations<'tcx>>,
+    infcx: &BorrowckInferCtxt<'tcx>,
+) -> LoweredConstraints<'tcx> {
+    let universal_regions = &universal_region_relations.universal_regions;
+    let (definitions, has_placeholders) = region_definitions(universal_regions, infcx);
+
+    let MirTypeckRegionConstraints {
+        placeholder_indices,
+        placeholder_index_to_region: _,
+        liveness_constraints,
+        mut outlives_constraints,
+        mut member_constraints,
+        universe_causes,
+        type_tests,
+    } = constraints;
+
+    if let Some(guar) = universal_regions.tainted_by_errors() {
+        debug!("Universal regions tainted by errors; removing constraints!");
+        // Suppress unhelpful extra errors in `infer_opaque_types` by clearing out all
+        // outlives bounds that we may end up checking.
+        outlives_constraints = Default::default();
+        member_constraints = Default::default();
+
+        // Also taint the entire scope.
+        infcx.set_tainted_by_errors(guar);
+    }
+
+    let fr_static = universal_regions.fr_static;
+    let compute_sccs =
+        |constraints: &OutlivesConstraintSet<'tcx>,
+         annotations: &mut SccAnnotations<'_, 'tcx, RegionTracker>| {
+            ConstraintSccs::new_with_annotation(
+                &constraints.graph(definitions.len()).region_graph(constraints, fr_static),
+                annotations,
+            )
+        };
+
+    // This code structure is a bit convoluted because it allows for a planned
+    // future change where the early return here has a different type of annotation
+    // that does much less work.
+    if !has_placeholders {
+        debug!("No placeholder regions found; skipping rewriting logic!");
+        let mut scc_annotations = SccAnnotations::init(&definitions);
+        let constraint_sccs = compute_sccs(&outlives_constraints, &mut scc_annotations);
+
+        return LoweredConstraints {
+            type_tests,
+            member_constraints,
+            constraint_sccs,
+            scc_annotations: scc_annotations.scc_to_annotation,
+            definitions,
+            outlives_constraints,
+            liveness_constraints,
+            universe_causes,
+            placeholder_indices,
+        };
+    }
+    debug!("Placeholders present; activating placeholder handling logic!");
+
+    let mut annotations = SccAnnotations::init(&definitions);
+    let sccs = compute_sccs(&outlives_constraints, &mut annotations);
+
+    let outlives_static =
+        rewrite_outlives(&sccs, &annotations, fr_static, &mut outlives_constraints);
+
+    let (sccs, scc_annotations) = if !outlives_static.is_empty() {
+        debug!("The following SCCs had :'static constraints added: {:?}", outlives_static);
+        let mut annotations = SccAnnotations::init(&definitions);
+
+        // We changed the constraint set and so must recompute SCCs.
+        // Optimisation opportunity: if we can add them incrementally (and that's
+        // possible because edges to 'static always only merge SCCs into 'static),
+        // we would potentially save a lot of work here.
+        (compute_sccs(&outlives_constraints, &mut annotations), annotations.scc_to_annotation)
+    } else {
+        // If we didn't add any back-edges; no more work needs doing
+        debug!("No constraints rewritten!");
+        (sccs, annotations.scc_to_annotation)
+    };
+
+    LoweredConstraints {
+        constraint_sccs: sccs,
+        definitions,
+        scc_annotations,
+        member_constraints,
+        outlives_constraints,
+        type_tests,
+        liveness_constraints,
+        universe_causes,
+        placeholder_indices,
+    }
+}
+
+fn rewrite_outlives<'tcx>(
+    sccs: &Sccs<RegionVid, ConstraintSccIndex>,
+    annotations: &SccAnnotations<'_, '_, RegionTracker>,
+    fr_static: RegionVid,
+    outlives_constraints: &mut OutlivesConstraintSet<'tcx>,
+) -> FxHashSet<ConstraintSccIndex> {
+    // Changed to `true` if we added any constraints to `self` and need to
+    // recompute SCCs.
+    let mut outlives_static = FxHashSet::default();
+
+    let annotations = &annotations.scc_to_annotation;
+
+    for scc in sccs.all_sccs() {
+        // No point in adding 'static: 'static!
+        // This micro-optimisation makes somewhat sense
+        // because static outlives *everything*.
+        if scc == sccs.scc(fr_static) {
+            continue;
+        }
+
+        let annotation = annotations[scc];
+
+        // If this SCC participates in a universe violation,
+        // e.g. if it reaches a region with a universe smaller than
+        // the largest region reached, add a requirement that it must
+        // outlive `'static`.
+        if annotation.has_incompatible_universes() {
+            // Optimisation opportunity: this will add more constraints than
+            // needed for correctness, since an SCC upstream of another with
+            // a universe violation will "infect" its downstream SCCs to also
+            // outlive static.
+            outlives_static.insert(scc);
+            let scc_representative_outlives_static = OutlivesConstraint {
+                sup: annotation.representative,
+                sub: fr_static,
+                category: ConstraintCategory::IllegalUniverse,
+                locations: Locations::All(rustc_span::DUMMY_SP),
+                span: rustc_span::DUMMY_SP,
+                variance_info: VarianceDiagInfo::None,
+                from_closure: false,
+            };
+            outlives_constraints.push(scc_representative_outlives_static);
+        }
+    }
+    outlives_static
+}
diff --git a/compiler/rustc_borrowck/src/lib.rs b/compiler/rustc_borrowck/src/lib.rs
index 44af1b76539..edf5494e886 100644
--- a/compiler/rustc_borrowck/src/lib.rs
+++ b/compiler/rustc_borrowck/src/lib.rs
@@ -75,6 +75,7 @@ mod constraints;
 mod dataflow;
 mod def_use;
 mod diagnostics;
+mod eliminate_placeholders;
 mod member_constraints;
 mod nll;
 mod path_utils;
diff --git a/compiler/rustc_borrowck/src/nll.rs b/compiler/rustc_borrowck/src/nll.rs
index fe899bb054f..9b1a5df8d06 100644
--- a/compiler/rustc_borrowck/src/nll.rs
+++ b/compiler/rustc_borrowck/src/nll.rs
@@ -22,6 +22,7 @@ use tracing::{debug, instrument};
 use crate::borrow_set::BorrowSet;
 use crate::consumers::ConsumerOptions;
 use crate::diagnostics::RegionErrors;
+use crate::eliminate_placeholders::rewrite_higher_kinded_outlives_as_constraints;
 use crate::polonius::PoloniusDiagnosticsContext;
 use crate::polonius::legacy::{
     PoloniusFacts, PoloniusFactsExt, PoloniusLocationTable, PoloniusOutput,
@@ -117,6 +118,12 @@ pub(crate) fn compute_regions<'a, 'tcx>(
         Rc::clone(&location_map),
     );
 
+    let lowered_constraints = rewrite_higher_kinded_outlives_as_constraints(
+        constraints,
+        &universal_region_relations,
+        infcx,
+    );
+
     // If requested, emit legacy polonius facts.
     polonius::legacy::emit_facts(
         &mut polonius_facts,
@@ -126,11 +133,15 @@ pub(crate) fn compute_regions<'a, 'tcx>(
         borrow_set,
         move_data,
         &universal_region_relations,
-        &constraints,
+        &lowered_constraints,
     );
 
-    let mut regioncx =
-        RegionInferenceContext::new(infcx, constraints, universal_region_relations, location_map);
+    let mut regioncx = RegionInferenceContext::new(
+        infcx,
+        lowered_constraints,
+        universal_region_relations,
+        location_map,
+    );
 
     // If requested for `-Zpolonius=next`, convert NLL constraints to localized outlives constraints
     // and use them to compute loan liveness.
diff --git a/compiler/rustc_borrowck/src/polonius/legacy/mod.rs b/compiler/rustc_borrowck/src/polonius/legacy/mod.rs
index 95820c07a02..67da43ca578 100644
--- a/compiler/rustc_borrowck/src/polonius/legacy/mod.rs
+++ b/compiler/rustc_borrowck/src/polonius/legacy/mod.rs
@@ -13,7 +13,7 @@ use tracing::debug;
 
 use crate::borrow_set::BorrowSet;
 use crate::constraints::OutlivesConstraint;
-use crate::type_check::MirTypeckRegionConstraints;
+use crate::eliminate_placeholders::LoweredConstraints;
 use crate::type_check::free_region_relations::UniversalRegionRelations;
 use crate::universal_regions::UniversalRegions;
 
@@ -43,7 +43,7 @@ pub(crate) fn emit_facts<'tcx>(
     borrow_set: &BorrowSet<'tcx>,
     move_data: &MoveData<'tcx>,
     universal_region_relations: &UniversalRegionRelations<'tcx>,
-    constraints: &MirTypeckRegionConstraints<'tcx>,
+    constraints: &LoweredConstraints<'tcx>,
 ) {
     let Some(facts) = facts else {
         // We don't do anything if there are no facts to fill.
@@ -203,7 +203,7 @@ pub(crate) fn emit_drop_facts<'tcx>(
 fn emit_outlives_facts<'tcx>(
     facts: &mut PoloniusFacts,
     location_table: &PoloniusLocationTable,
-    constraints: &MirTypeckRegionConstraints<'tcx>,
+    constraints: &LoweredConstraints<'tcx>,
 ) {
     facts.subset_base.extend(constraints.outlives_constraints.outlives().iter().flat_map(
         |constraint: &OutlivesConstraint<'_>| {
diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs
index b4ff3d66f3d..cfad071460b 100644
--- a/compiler/rustc_borrowck/src/region_infer/mod.rs
+++ b/compiler/rustc_borrowck/src/region_infer/mod.rs
@@ -4,12 +4,14 @@ 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::{self, Sccs};
+use rustc_data_structures::graph::scc::Sccs;
 use rustc_errors::Diag;
 use rustc_hir::def_id::CRATE_DEF_ID;
 use rustc_index::IndexVec;
 use rustc_infer::infer::outlives::test_type_match;
-use rustc_infer::infer::region_constraints::{GenericKind, VerifyBound, VerifyIfEq};
+use rustc_infer::infer::region_constraints::{
+    GenericKind, RegionVariableInfo, VerifyBound, VerifyIfEq,
+};
 use rustc_infer::infer::{InferCtxt, NllRegionVariableOrigin, RegionVariableOrigin};
 use rustc_middle::bug;
 use rustc_middle::mir::{
@@ -27,13 +29,14 @@ use crate::constraints::graph::{self, NormalConstraintGraph, RegionGraph};
 use crate::constraints::{ConstraintSccIndex, OutlivesConstraint, OutlivesConstraintSet};
 use crate::dataflow::BorrowIndex;
 use crate::diagnostics::{RegionErrorKind, RegionErrors, UniverseInfo};
+use crate::eliminate_placeholders::{LoweredConstraints, RegionTracker};
 use crate::member_constraints::{MemberConstraintSet, NllMemberConstraintIndex};
 use crate::polonius::LiveLoans;
 use crate::polonius::legacy::PoloniusOutput;
 use crate::region_infer::reverse_sccs::ReverseSccGraph;
 use crate::region_infer::values::{LivenessValues, RegionElement, RegionValues, ToElementIndex};
+use crate::type_check::Locations;
 use crate::type_check::free_region_relations::UniversalRegionRelations;
-use crate::type_check::{Locations, MirTypeckRegionConstraints};
 use crate::universal_regions::UniversalRegions;
 use crate::{
     BorrowckInferCtxt, ClosureOutlivesRequirement, ClosureOutlivesSubject,
@@ -48,124 +51,6 @@ mod reverse_sccs;
 pub(crate) mod values;
 
 pub(crate) type ConstraintSccs = Sccs<RegionVid, ConstraintSccIndex>;
-pub(crate) type AnnotatedSccs = (ConstraintSccs, IndexVec<ConstraintSccIndex, RegionTracker>);
-
-/// An annotation for region graph SCCs that tracks
-/// the values of its elements. This annotates a single SCC.
-#[derive(Copy, Debug, Clone)]
-pub(crate) 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.
-    pub(crate) 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
-    }
-}
-
-/// A Visitor for SCC annotation construction.
-pub(crate) struct SccAnnotations<'d, 'tcx, A: scc::Annotation> {
-    pub(crate) scc_to_annotation: IndexVec<ConstraintSccIndex, A>,
-    definitions: &'d IndexVec<RegionVid, RegionDefinition<'tcx>>,
-}
-
-impl<'d, 'tcx, A: scc::Annotation> SccAnnotations<'d, 'tcx, A> {
-    pub(crate) fn new(definitions: &'d IndexVec<RegionVid, RegionDefinition<'tcx>>) -> Self {
-        Self { scc_to_annotation: IndexVec::new(), definitions }
-    }
-}
-
-impl scc::Annotations<RegionVid> for SccAnnotations<'_, '_, RegionTracker> {
-    fn new(&self, element: RegionVid) -> RegionTracker {
-        RegionTracker::new(element, &self.definitions[element])
-    }
-
-    fn annotate_scc(&mut self, scc: ConstraintSccIndex, annotation: RegionTracker) {
-        let idx = self.scc_to_annotation.push(annotation);
-        assert!(idx == scc);
-    }
-
-    type Ann = RegionTracker;
-    type SccIdx = ConstraintSccIndex;
-}
-
-impl RegionTracker {
-    pub(crate) fn new(rvid: RegionVid, definition: &RegionDefinition<'_>) -> Self {
-        let (representative_is_placeholder, representative_is_existential) = match definition.origin
-        {
-            NllRegionVariableOrigin::FreeRegion => (false, false),
-            NllRegionVariableOrigin::Placeholder(_) => (true, false),
-            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,
-        }
-    }
-
-    /// The smallest-indexed universe reachable from and/or in this SCC.
-    fn min_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(crate) fn has_incompatible_universes(&self) -> bool {
-        self.min_universe().cannot_name(self.max_placeholder_universe_reached)
-    }
-}
 
 pub struct RegionInferenceContext<'tcx> {
     /// Contains the definition for every region variable. Region
@@ -413,26 +298,6 @@ fn sccs_info<'tcx>(infcx: &BorrowckInferCtxt<'tcx>, sccs: &ConstraintSccs) {
     debug!("SCC edges {:#?}", scc_node_to_edges);
 }
 
-fn create_definitions<'tcx>(
-    infcx: &BorrowckInferCtxt<'tcx>,
-    universal_regions: &UniversalRegions<'tcx>,
-) -> Frozen<IndexVec<RegionVid, RegionDefinition<'tcx>>> {
-    // Create a RegionDefinition for each inference variable.
-    let mut definitions: IndexVec<_, _> = infcx
-        .get_region_var_infos()
-        .iter()
-        .map(|info| RegionDefinition::new(info.universe, info.origin))
-        .collect();
-
-    // Add the external name for all universal regions.
-    for (external_name, variable) in universal_regions.named_universal_regions_iter() {
-        debug!("region {variable:?} has external name {external_name:?}");
-        definitions[variable].external_name = Some(external_name);
-    }
-
-    Frozen::freeze(definitions)
-}
-
 impl<'tcx> RegionInferenceContext<'tcx> {
     /// Creates a new region inference context with a total of
     /// `num_region_variables` valid inference variables; the first N
@@ -443,42 +308,30 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     /// of constraints produced by the MIR type check.
     pub(crate) fn new(
         infcx: &BorrowckInferCtxt<'tcx>,
-        constraints: MirTypeckRegionConstraints<'tcx>,
+        lowered_constraints: LoweredConstraints<'tcx>,
         universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>,
         location_map: Rc<DenseLocationMap>,
     ) -> Self {
         let universal_regions = &universal_region_relations.universal_regions;
-        let MirTypeckRegionConstraints {
-            placeholder_indices,
-            placeholder_index_to_region: _,
+
+        let LoweredConstraints {
+            constraint_sccs,
+            definitions,
+            outlives_constraints,
+            scc_annotations,
+            type_tests,
             liveness_constraints,
-            mut outlives_constraints,
-            mut member_constraints,
             universe_causes,
-            type_tests,
-        } = constraints;
+            placeholder_indices,
+            member_constraints,
+        } = lowered_constraints;
 
         debug!("universal_regions: {:#?}", universal_region_relations.universal_regions);
         debug!("outlives constraints: {:#?}", outlives_constraints);
         debug!("placeholder_indices: {:#?}", placeholder_indices);
         debug!("type tests: {:#?}", type_tests);
 
-        if let Some(guar) = universal_region_relations.universal_regions.tainted_by_errors() {
-            // Suppress unhelpful extra errors in `infer_opaque_types` by clearing out all
-            // outlives bounds that we may end up checking.
-            outlives_constraints = Default::default();
-            member_constraints = Default::default();
-
-            // Also taint the entire scope.
-            infcx.set_tainted_by_errors(guar);
-        }
-
-        let definitions = create_definitions(infcx, &universal_regions);
-
-        let (constraint_sccs, scc_annotations) =
-            outlives_constraints.add_outlives_static(&universal_regions, &definitions);
-        let constraints = Frozen::freeze(outlives_constraints);
-        let constraint_graph = Frozen::freeze(constraints.graph(definitions.len()));
+        let constraint_graph = Frozen::freeze(outlives_constraints.graph(definitions.len()));
 
         if cfg!(debug_assertions) {
             sccs_info(infcx, &constraint_sccs);
@@ -498,7 +351,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         let mut result = Self {
             definitions,
             liveness_constraints,
-            constraints,
+            constraints: Frozen::freeze(outlives_constraints),
             constraint_graph,
             constraint_sccs,
             scc_annotations,
@@ -904,20 +757,7 @@ 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 a_annotation = self.scc_annotations[scc_a];
-        let b_annotation = self.scc_annotations[scc_b];
-        let a_universe = a_annotation.min_universe();
-
-        // 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 a_universe.can_name(b_annotation.min_universe()) {
-            return true;
-        }
-
-        // Otherwise, there can be no placeholder in `b` with a too high
-        // universe index to name from `a`.
-        a_universe.can_name(b_annotation.max_placeholder_universe_reached)
+        self.scc_annotations[scc_a].universe_compatible_with(self.scc_annotations[scc_b])
     }
 
     /// Once regions have been propagated, this method is used to see
@@ -2269,17 +2109,17 @@ impl<'tcx> RegionInferenceContext<'tcx> {
 }
 
 impl<'tcx> RegionDefinition<'tcx> {
-    fn new(universe: ty::UniverseIndex, rv_origin: RegionVariableOrigin) -> Self {
+    pub(crate) fn new(rv_info: &RegionVariableInfo) -> Self {
         // Create a new region definition. Note that, for free
         // regions, the `external_name` field gets updated later in
-        // `init_free_and_bound_regions`.
+        // [[crate::eliminate_placeholders]].
 
-        let origin = match rv_origin {
+        let origin = match rv_info.origin {
             RegionVariableOrigin::Nll(origin) => origin,
             _ => NllRegionVariableOrigin::Existential { from_forall: false },
         };
 
-        Self { origin, universe, external_name: None }
+        Self { origin, universe: rv_info.universe, external_name: None }
     }
 }