Rollup merge of #108071 - compiler-errors:new-solver-caching, r=lcnr

Implement goal caching with the new solver

Maybe it's wrong, idk. Opening mostly for first impressions before I go to sleep.

r? ``@lcnr,`` cc ``@cjgillot``

11 files changed, 183 insertions, 173 deletions

diff --git a/compiler/rustc_infer/src/traits/mod.rs b/compiler/rustc_infer/src/traits/mod.rs
index 3a82899660b..77c67c14ecc 100644
--- a/compiler/rustc_infer/src/traits/mod.rs
+++ b/compiler/rustc_infer/src/traits/mod.rs
@@ -53,6 +53,12 @@ pub struct Obligation<'tcx, T> {
     pub recursion_depth: usize,
 }
 
+impl<'tcx, P> From<Obligation<'tcx, P>> for solve::Goal<'tcx, P> {
+    fn from(value: Obligation<'tcx, P>) -> Self {
+        solve::Goal { param_env: value.param_env, predicate: value.predicate }
+    }
+}
+
 pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>;
 pub type TraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitPredicate<'tcx>>;
 
diff --git a/compiler/rustc_middle/src/traits/solve.rs b/compiler/rustc_middle/src/traits/solve.rs
index bd43867a3da..92d3e73e683 100644
--- a/compiler/rustc_middle/src/traits/solve.rs
+++ b/compiler/rustc_middle/src/traits/solve.rs
@@ -1,12 +1,104 @@
 use std::ops::ControlFlow;
 
 use rustc_data_structures::intern::Interned;
+use rustc_query_system::cache::Cache;
 
-use crate::infer::canonical::QueryRegionConstraints;
+use crate::infer::canonical::{CanonicalVarValues, QueryRegionConstraints};
+use crate::traits::query::NoSolution;
+use crate::traits::Canonical;
 use crate::ty::{
-    FallibleTypeFolder, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeVisitable, TypeVisitor,
+    self, FallibleTypeFolder, ToPredicate, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeVisitable,
+    TypeVisitor,
 };
 
+pub type EvaluationCache<'tcx> = Cache<CanonicalGoal<'tcx>, QueryResult<'tcx>>;
+
+/// A goal is a statement, i.e. `predicate`, we want to prove
+/// given some assumptions, i.e. `param_env`.
+///
+/// Most of the time the `param_env` contains the `where`-bounds of the function
+/// we're currently typechecking while the `predicate` is some trait bound.
+#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
+pub struct Goal<'tcx, P> {
+    pub param_env: ty::ParamEnv<'tcx>,
+    pub predicate: P,
+}
+
+impl<'tcx, P> Goal<'tcx, P> {
+    pub fn new(
+        tcx: TyCtxt<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+        predicate: impl ToPredicate<'tcx, P>,
+    ) -> Goal<'tcx, P> {
+        Goal { param_env, predicate: predicate.to_predicate(tcx) }
+    }
+
+    /// Updates the goal to one with a different `predicate` but the same `param_env`.
+    pub fn with<Q>(self, tcx: TyCtxt<'tcx>, predicate: impl ToPredicate<'tcx, Q>) -> Goal<'tcx, Q> {
+        Goal { param_env: self.param_env, predicate: predicate.to_predicate(tcx) }
+    }
+}
+
+#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
+pub struct Response<'tcx> {
+    pub var_values: CanonicalVarValues<'tcx>,
+    /// Additional constraints returned by this query.
+    pub external_constraints: ExternalConstraints<'tcx>,
+    pub certainty: Certainty,
+}
+
+#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
+pub enum Certainty {
+    Yes,
+    Maybe(MaybeCause),
+}
+
+impl Certainty {
+    pub const AMBIGUOUS: Certainty = Certainty::Maybe(MaybeCause::Ambiguity);
+
+    /// When proving multiple goals using **AND**, e.g. nested obligations for an impl,
+    /// use this function to unify the certainty of these goals
+    pub fn unify_and(self, other: Certainty) -> Certainty {
+        match (self, other) {
+            (Certainty::Yes, Certainty::Yes) => Certainty::Yes,
+            (Certainty::Yes, Certainty::Maybe(_)) => other,
+            (Certainty::Maybe(_), Certainty::Yes) => self,
+            (Certainty::Maybe(MaybeCause::Overflow), Certainty::Maybe(MaybeCause::Overflow)) => {
+                Certainty::Maybe(MaybeCause::Overflow)
+            }
+            // If at least one of the goals is ambiguous, hide the overflow as the ambiguous goal
+            // may still result in failure.
+            (Certainty::Maybe(MaybeCause::Ambiguity), Certainty::Maybe(_))
+            | (Certainty::Maybe(_), Certainty::Maybe(MaybeCause::Ambiguity)) => {
+                Certainty::Maybe(MaybeCause::Ambiguity)
+            }
+        }
+    }
+}
+
+/// Why we failed to evaluate a goal.
+#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
+pub enum MaybeCause {
+    /// We failed due to ambiguity. This ambiguity can either
+    /// be a true ambiguity, i.e. there are multiple different answers,
+    /// or we hit a case where we just don't bother, e.g. `?x: Trait` goals.
+    Ambiguity,
+    /// We gave up due to an overflow, most often by hitting the recursion limit.
+    Overflow,
+}
+
+pub type CanonicalGoal<'tcx, T = ty::Predicate<'tcx>> = Canonical<'tcx, Goal<'tcx, T>>;
+
+pub type CanonicalResponse<'tcx> = Canonical<'tcx, Response<'tcx>>;
+
+/// The result of evaluating a canonical query.
+///
+/// FIXME: We use a different type than the existing canonical queries. This is because
+/// we need to add a `Certainty` for `overflow` and may want to restructure this code without
+/// having to worry about changes to currently used code. Once we've made progress on this
+/// solver, merge the two responses again.
+pub type QueryResult<'tcx> = Result<CanonicalResponse<'tcx>, NoSolution>;
+
 #[derive(Debug, PartialEq, Eq, Copy, Clone, Hash)]
 pub struct ExternalConstraints<'tcx>(pub(crate) Interned<'tcx, ExternalConstraintsData<'tcx>>);
 
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index 82da846ea68..e95f6f91357 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -17,6 +17,7 @@ use crate::mir::{
 };
 use crate::thir::Thir;
 use crate::traits;
+use crate::traits::solve;
 use crate::traits::solve::{ExternalConstraints, ExternalConstraintsData};
 use crate::ty::query::{self, TyCtxtAt};
 use crate::ty::{
@@ -537,6 +538,9 @@ pub struct GlobalCtxt<'tcx> {
     /// Merge this with `selection_cache`?
     pub evaluation_cache: traits::EvaluationCache<'tcx>,
 
+    /// Caches the results of goal evaluation in the new solver.
+    pub new_solver_evaluation_cache: solve::EvaluationCache<'tcx>,
+
     /// Data layout specification for the current target.
     pub data_layout: TargetDataLayout,
 
@@ -712,6 +716,7 @@ impl<'tcx> TyCtxt<'tcx> {
             pred_rcache: Default::default(),
             selection_cache: Default::default(),
             evaluation_cache: Default::default(),
+            new_solver_evaluation_cache: Default::default(),
             data_layout,
             alloc_map: Lock::new(interpret::AllocMap::new()),
         }
diff --git a/compiler/rustc_trait_selection/src/solve/assembly.rs b/compiler/rustc_trait_selection/src/solve/assembly.rs
index dec9f8016b0..b092503a007 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly.rs
@@ -2,11 +2,12 @@
 
 #[cfg(doc)]
 use super::trait_goals::structural_traits::*;
-use super::{CanonicalResponse, Certainty, EvalCtxt, Goal, MaybeCause, QueryResult};
+use super::EvalCtxt;
 use itertools::Itertools;
 use rustc_hir::def_id::DefId;
 use rustc_infer::traits::query::NoSolution;
 use rustc_infer::traits::util::elaborate_predicates;
+use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, MaybeCause, QueryResult};
 use rustc_middle::ty::TypeFoldable;
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use std::fmt::Debug;
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index 43fd415e871..55d361b1204 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -21,11 +21,13 @@ use rustc_hir::def_id::DefId;
 use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues};
 use rustc_infer::infer::{InferCtxt, InferOk, TyCtxtInferExt};
 use rustc_infer::traits::query::NoSolution;
-use rustc_infer::traits::Obligation;
-use rustc_middle::traits::solve::{ExternalConstraints, ExternalConstraintsData};
+use rustc_middle::traits::solve::{
+    CanonicalGoal, CanonicalResponse, Certainty, ExternalConstraints, ExternalConstraintsData,
+    Goal, MaybeCause, QueryResult, Response,
+};
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use rustc_middle::ty::{
-    CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, ToPredicate, TypeOutlivesPredicate,
+    CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, TypeOutlivesPredicate,
 };
 use rustc_span::DUMMY_SP;
 
@@ -43,45 +45,6 @@ mod trait_goals;
 pub use eval_ctxt::EvalCtxt;
 pub use fulfill::FulfillmentCtxt;
 
-/// A goal is a statement, i.e. `predicate`, we want to prove
-/// given some assumptions, i.e. `param_env`.
-///
-/// Most of the time the `param_env` contains the `where`-bounds of the function
-/// we're currently typechecking while the `predicate` is some trait bound.
-#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
-pub struct Goal<'tcx, P> {
-    param_env: ty::ParamEnv<'tcx>,
-    predicate: P,
-}
-
-impl<'tcx, P> Goal<'tcx, P> {
-    pub fn new(
-        tcx: TyCtxt<'tcx>,
-        param_env: ty::ParamEnv<'tcx>,
-        predicate: impl ToPredicate<'tcx, P>,
-    ) -> Goal<'tcx, P> {
-        Goal { param_env, predicate: predicate.to_predicate(tcx) }
-    }
-
-    /// Updates the goal to one with a different `predicate` but the same `param_env`.
-    fn with<Q>(self, tcx: TyCtxt<'tcx>, predicate: impl ToPredicate<'tcx, Q>) -> Goal<'tcx, Q> {
-        Goal { param_env: self.param_env, predicate: predicate.to_predicate(tcx) }
-    }
-}
-
-impl<'tcx, P> From<Obligation<'tcx, P>> for Goal<'tcx, P> {
-    fn from(obligation: Obligation<'tcx, P>) -> Goal<'tcx, P> {
-        Goal { param_env: obligation.param_env, predicate: obligation.predicate }
-    }
-}
-#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
-pub struct Response<'tcx> {
-    pub var_values: CanonicalVarValues<'tcx>,
-    /// Additional constraints returned by this query.
-    pub external_constraints: ExternalConstraints<'tcx>,
-    pub certainty: Certainty,
-}
-
 trait CanonicalResponseExt {
     fn has_no_inference_or_external_constraints(&self) -> bool;
 }
@@ -94,56 +57,6 @@ impl<'tcx> CanonicalResponseExt for Canonical<'tcx, Response<'tcx>> {
     }
 }
 
-#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
-pub enum Certainty {
-    Yes,
-    Maybe(MaybeCause),
-}
-
-impl Certainty {
-    pub const AMBIGUOUS: Certainty = Certainty::Maybe(MaybeCause::Ambiguity);
-
-    /// When proving multiple goals using **AND**, e.g. nested obligations for an impl,
-    /// use this function to unify the certainty of these goals
-    pub fn unify_and(self, other: Certainty) -> Certainty {
-        match (self, other) {
-            (Certainty::Yes, Certainty::Yes) => Certainty::Yes,
-            (Certainty::Yes, Certainty::Maybe(_)) => other,
-            (Certainty::Maybe(_), Certainty::Yes) => self,
-            (Certainty::Maybe(MaybeCause::Overflow), Certainty::Maybe(MaybeCause::Overflow)) => {
-                Certainty::Maybe(MaybeCause::Overflow)
-            }
-            // If at least one of the goals is ambiguous, hide the overflow as the ambiguous goal
-            // may still result in failure.
-            (Certainty::Maybe(MaybeCause::Ambiguity), Certainty::Maybe(_))
-            | (Certainty::Maybe(_), Certainty::Maybe(MaybeCause::Ambiguity)) => {
-                Certainty::Maybe(MaybeCause::Ambiguity)
-            }
-        }
-    }
-}
-
-/// Why we failed to evaluate a goal.
-#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
-pub enum MaybeCause {
-    /// We failed due to ambiguity. This ambiguity can either
-    /// be a true ambiguity, i.e. there are multiple different answers,
-    /// or we hit a case where we just don't bother, e.g. `?x: Trait` goals.
-    Ambiguity,
-    /// We gave up due to an overflow, most often by hitting the recursion limit.
-    Overflow,
-}
-
-type CanonicalGoal<'tcx, T = ty::Predicate<'tcx>> = Canonical<'tcx, Goal<'tcx, T>>;
-type CanonicalResponse<'tcx> = Canonical<'tcx, Response<'tcx>>;
-/// The result of evaluating a canonical query.
-///
-/// FIXME: We use a different type than the existing canonical queries. This is because
-/// we need to add a `Certainty` for `overflow` and may want to restructure this code without
-/// having to worry about changes to currently used code. Once we've made progress on this
-/// solver, merge the two responses again.
-pub type QueryResult<'tcx> = Result<CanonicalResponse<'tcx>, NoSolution>;
-
 pub trait InferCtxtEvalExt<'tcx> {
     /// Evaluates a goal from **outside** of the trait solver.
     ///
diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs
index 33c66d072e9..e206658b4b9 100644
--- a/compiler/rustc_trait_selection/src/solve/project_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs
@@ -2,7 +2,7 @@ use crate::traits::{specialization_graph, translate_substs};
 
 use super::assembly;
 use super::trait_goals::structural_traits;
-use super::{Certainty, EvalCtxt, Goal, QueryResult};
+use super::EvalCtxt;
 use rustc_errors::ErrorGuaranteed;
 use rustc_hir::def::DefKind;
 use rustc_hir::def_id::DefId;
@@ -11,6 +11,7 @@ use rustc_infer::infer::InferCtxt;
 use rustc_infer::traits::query::NoSolution;
 use rustc_infer::traits::specialization_graph::LeafDef;
 use rustc_infer::traits::Reveal;
+use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult};
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
 use rustc_middle::ty::ProjectionPredicate;
 use rustc_middle::ty::{self, Ty, TyCtxt};
@@ -512,7 +513,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
     fn consider_builtin_dyn_upcast_candidates(
         _ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
-    ) -> Vec<super::CanonicalResponse<'tcx>> {
+    ) -> Vec<CanonicalResponse<'tcx>> {
         bug!("`Unsize` does not have an associated type: {:?}", goal);
     }
 
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
index 86b13c05f76..d1b4fa554c5 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
@@ -8,12 +8,10 @@
 //!
 //! FIXME(@lcnr): Write that section, feel free to ping me if you need help here
 //! before then or if I still haven't done that before January 2023.
-use super::overflow::OverflowData;
 use super::StackDepth;
-use crate::solve::{CanonicalGoal, QueryResult};
 use rustc_data_structures::fx::FxHashMap;
 use rustc_index::vec::IndexVec;
-use rustc_middle::ty::TyCtxt;
+use rustc_middle::traits::solve::{CanonicalGoal, QueryResult};
 
 rustc_index::newtype_index! {
     pub struct EntryIndex {}
@@ -98,26 +96,3 @@ impl<'tcx> ProvisionalCache<'tcx> {
         self.entries[entry_index].response
     }
 }
-
-pub(super) fn try_move_finished_goal_to_global_cache<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    overflow_data: &mut OverflowData,
-    stack: &IndexVec<super::StackDepth, super::StackElem<'tcx>>,
-    goal: CanonicalGoal<'tcx>,
-    response: QueryResult<'tcx>,
-) {
-    // We move goals to the global cache if we either did not hit an overflow or if it's
-    // the root goal as that will now always hit the same overflow limit.
-    //
-    // NOTE: We cannot move any non-root goals to the global cache even if their final result
-    // isn't impacted by the overflow as that goal still has unstable query dependencies
-    // because it didn't go its full depth.
-    //
-    // FIXME(@lcnr): We could still cache subtrees which are not impacted by overflow though.
-    // Tracking that info correctly isn't trivial, so I haven't implemented it for now.
-    let should_cache_globally = !overflow_data.did_overflow() || stack.is_empty();
-    if should_cache_globally {
-        // FIXME: move the provisional entry to the global cache.
-        let _ = (tcx, goal, response);
-    }
-}
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
index c7eb8de6521..f1b840aac55 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
@@ -2,11 +2,12 @@ mod cache;
 mod overflow;
 
 use self::cache::ProvisionalEntry;
-use super::{CanonicalGoal, Certainty, MaybeCause, QueryResult};
 pub(super) use crate::solve::search_graph::overflow::OverflowHandler;
 use cache::ProvisionalCache;
 use overflow::OverflowData;
 use rustc_index::vec::IndexVec;
+use rustc_middle::dep_graph::DepKind;
+use rustc_middle::traits::solve::{CanonicalGoal, Certainty, MaybeCause, QueryResult};
 use rustc_middle::ty::TyCtxt;
 use std::{collections::hash_map::Entry, mem};
 
@@ -139,10 +140,9 @@ impl<'tcx> SearchGraph<'tcx> {
     /// updated the provisional cache and we have to recompute the current goal.
     ///
     /// FIXME: Refer to the rustc-dev-guide entry once it exists.
-    #[instrument(level = "debug", skip(self, tcx, actual_goal), ret)]
+    #[instrument(level = "debug", skip(self, actual_goal), ret)]
     fn try_finalize_goal(
         &mut self,
-        tcx: TyCtxt<'tcx>,
         actual_goal: CanonicalGoal<'tcx>,
         response: QueryResult<'tcx>,
     ) -> bool {
@@ -176,72 +176,87 @@ impl<'tcx> SearchGraph<'tcx> {
             self.stack.push(StackElem { goal, has_been_used: false });
             false
         } else {
-            self.try_move_finished_goal_to_global_cache(tcx, stack_elem);
             true
         }
     }
 
-    fn try_move_finished_goal_to_global_cache(
+    pub(super) fn with_new_goal(
         &mut self,
         tcx: TyCtxt<'tcx>,
-        stack_elem: StackElem<'tcx>,
-    ) {
-        let StackElem { goal, .. } = stack_elem;
+        canonical_goal: CanonicalGoal<'tcx>,
+        mut loop_body: impl FnMut(&mut Self) -> QueryResult<'tcx>,
+    ) -> QueryResult<'tcx> {
+        if let Some(result) = tcx.new_solver_evaluation_cache.get(&canonical_goal, tcx) {
+            return result;
+        }
+
+        match self.try_push_stack(tcx, canonical_goal) {
+            Ok(()) => {}
+            // Our goal is already on the stack, eager return.
+            Err(response) => return response,
+        }
+
+        // This is for global caching, so we properly track query dependencies.
+        // Everything that affects the `Result` should be performed within this
+        // `with_anon_task` closure.
+        let (result, dep_node) = tcx.dep_graph.with_anon_task(tcx, DepKind::TraitSelect, || {
+            self.repeat_while_none(
+                |this| {
+                    let result = this.deal_with_overflow(tcx, canonical_goal);
+                    let _ = this.stack.pop().unwrap();
+                    result
+                },
+                |this| {
+                    let result = loop_body(this);
+                    this.try_finalize_goal(canonical_goal, result).then(|| result)
+                },
+            )
+        });
+
         let cache = &mut self.provisional_cache;
-        let provisional_entry_index = *cache.lookup_table.get(&goal).unwrap();
+        let provisional_entry_index = *cache.lookup_table.get(&canonical_goal).unwrap();
         let provisional_entry = &mut cache.entries[provisional_entry_index];
         let depth = provisional_entry.depth;
 
         // If not, we're done with this goal.
         //
         // Check whether that this goal doesn't depend on a goal deeper on the stack
-        // and if so, move it and all nested goals to the global cache.
+        // and if so, move it to the global cache.
         //
         // Note that if any nested goal were to depend on something deeper on the stack,
         // this would have also updated the depth of the current goal.
         if depth == self.stack.next_index() {
-            for (i, entry) in cache.entries.drain_enumerated(provisional_entry_index.index()..) {
+            // If the current goal is the head of a cycle, we drop all other
+            // cycle participants without moving them to the global cache.
+            let other_cycle_participants = provisional_entry_index.index() + 1;
+            for (i, entry) in cache.entries.drain_enumerated(other_cycle_participants..) {
                 let actual_index = cache.lookup_table.remove(&entry.goal);
                 debug_assert_eq!(Some(i), actual_index);
                 debug_assert!(entry.depth == depth);
-                cache::try_move_finished_goal_to_global_cache(
-                    tcx,
-                    &mut self.overflow_data,
-                    &self.stack,
-                    entry.goal,
-                    entry.response,
-                );
             }
-        }
-    }
 
-    pub(super) fn with_new_goal(
-        &mut self,
-        tcx: TyCtxt<'tcx>,
-        canonical_goal: CanonicalGoal<'tcx>,
-        mut loop_body: impl FnMut(&mut Self) -> QueryResult<'tcx>,
-    ) -> QueryResult<'tcx> {
-        match self.try_push_stack(tcx, canonical_goal) {
-            Ok(()) => {}
-            // Our goal is already on the stack, eager return.
-            Err(response) => return response,
+            let current_goal = cache.entries.pop().unwrap();
+            let actual_index = cache.lookup_table.remove(&current_goal.goal);
+            debug_assert_eq!(Some(provisional_entry_index), actual_index);
+            debug_assert!(current_goal.depth == depth);
+
+            // We move the root goal to the global cache if we either did not hit an overflow or if it's
+            // the root goal as that will now always hit the same overflow limit.
+            //
+            // NOTE: We cannot move any non-root goals to the global cache. When replaying the root goal's
+            // dependencies, our non-root goal may no longer appear as child of the root goal.
+            //
+            // See https://github.com/rust-lang/rust/pull/108071 for some additional context.
+            let should_cache_globally = !self.overflow_data.did_overflow() || self.stack.is_empty();
+            if should_cache_globally {
+                tcx.new_solver_evaluation_cache.insert(
+                    current_goal.goal,
+                    dep_node,
+                    current_goal.response,
+                );
+            }
         }
 
-        self.repeat_while_none(
-            |this| {
-                let result = this.deal_with_overflow(tcx, canonical_goal);
-                let stack_elem = this.stack.pop().unwrap();
-                this.try_move_finished_goal_to_global_cache(tcx, stack_elem);
-                result
-            },
-            |this| {
-                let result = loop_body(this);
-                if this.try_finalize_goal(tcx, canonical_goal, result) {
-                    Some(result)
-                } else {
-                    None
-                }
-            },
-        )
+        result
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs
index 56409b0602b..7c9e63f529b 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs
@@ -1,10 +1,11 @@
 use rustc_infer::infer::canonical::Canonical;
 use rustc_infer::traits::query::NoSolution;
+use rustc_middle::traits::solve::{Certainty, MaybeCause, QueryResult};
 use rustc_middle::ty::TyCtxt;
 use rustc_session::Limit;
 
 use super::SearchGraph;
-use crate::solve::{response_no_constraints, Certainty, EvalCtxt, MaybeCause, QueryResult};
+use crate::solve::{response_no_constraints, EvalCtxt};
 
 /// When detecting a solver overflow, we return ambiguity. Overflow can be
 /// *hidden* by either a fatal error in an **AND** or a trivial success in an **OR**.
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index 5c499c36e9b..0669975d638 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -2,12 +2,12 @@
 
 use std::iter;
 
-use super::assembly;
-use super::{CanonicalResponse, Certainty, EvalCtxt, Goal, QueryResult};
+use super::{assembly, EvalCtxt};
 use rustc_hir::def_id::DefId;
 use rustc_hir::LangItem;
 use rustc_infer::traits::query::NoSolution;
 use rustc_infer::traits::util::supertraits;
+use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult};
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
 use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt};
 use rustc_middle::ty::{TraitPredicate, TypeVisitableExt};
diff --git a/compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs b/compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs
index f183248f2d0..1420c25c922 100644
--- a/compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs
@@ -1,9 +1,10 @@
+use rustc_middle::traits::solve::{Certainty, Goal, MaybeCause};
 use rustc_middle::ty;
 use rustc_session::config::TraitSolver;
 
 use crate::infer::canonical::OriginalQueryValues;
 use crate::infer::InferCtxt;
-use crate::solve::{Certainty, Goal, InferCtxtEvalExt, MaybeCause};
+use crate::solve::InferCtxtEvalExt;
 use crate::traits::{EvaluationResult, OverflowError, PredicateObligation, SelectionContext};
 
 pub trait InferCtxtExt<'tcx> {