Rollup merge of #117394 - lcnr:proof-tree-cache4, r=compiler-errors

use global cache when computing proof trees

we're writing the solver while relying on the existence of the global cache to avoid exponential blowup. By disabling the global cache when building proof trees, it is easy to get hangs, e.g. when computing intercrate ambiguity causes.

Removes the unstable `-Zdump_solver_proof_tree_use_cache` option, as we now always return a full proof tree.

r? `@compiler-errors`

11 files changed, 138 insertions, 126 deletions

diff --git a/compiler/rustc_middle/src/arena.rs b/compiler/rustc_middle/src/arena.rs
index 1d573a746b9..dd761b4e312 100644
--- a/compiler/rustc_middle/src/arena.rs
+++ b/compiler/rustc_middle/src/arena.rs
@@ -69,6 +69,7 @@ macro_rules! arena_types {
             [] dtorck_constraint: rustc_middle::traits::query::DropckConstraint<'tcx>,
             [] candidate_step: rustc_middle::traits::query::CandidateStep<'tcx>,
             [] autoderef_bad_ty: rustc_middle::traits::query::MethodAutoderefBadTy<'tcx>,
+            [] canonical_goal_evaluation: rustc_middle::traits::solve::inspect::GoalEvaluationStep<'tcx>,
             [] query_region_constraints: rustc_middle::infer::canonical::QueryRegionConstraints<'tcx>,
             [] type_op_subtype:
                 rustc_middle::infer::canonical::Canonical<'tcx,
diff --git a/compiler/rustc_middle/src/traits/solve/cache.rs b/compiler/rustc_middle/src/traits/solve/cache.rs
index 9898b0019bb..e9e9cc418a6 100644
--- a/compiler/rustc_middle/src/traits/solve/cache.rs
+++ b/compiler/rustc_middle/src/traits/solve/cache.rs
@@ -1,4 +1,4 @@
-use super::{CanonicalInput, QueryResult};
+use super::{inspect, CanonicalInput, QueryResult};
 use crate::ty::TyCtxt;
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use rustc_data_structures::sync::Lock;
@@ -14,8 +14,10 @@ pub struct EvaluationCache<'tcx> {
     map: Lock<FxHashMap<CanonicalInput<'tcx>, CacheEntry<'tcx>>>,
 }
 
+#[derive(PartialEq, Eq)]
 pub struct CacheData<'tcx> {
     pub result: QueryResult<'tcx>,
+    pub proof_tree: Option<&'tcx [inspect::GoalEvaluationStep<'tcx>]>,
     pub reached_depth: usize,
     pub encountered_overflow: bool,
 }
@@ -24,22 +26,33 @@ impl<'tcx> EvaluationCache<'tcx> {
     /// Insert a final result into the global cache.
     pub fn insert(
         &self,
+        tcx: TyCtxt<'tcx>,
         key: CanonicalInput<'tcx>,
+        proof_tree: Option<&'tcx [inspect::GoalEvaluationStep<'tcx>]>,
         reached_depth: usize,
-        did_overflow: bool,
+        encountered_overflow: bool,
         cycle_participants: FxHashSet<CanonicalInput<'tcx>>,
         dep_node: DepNodeIndex,
         result: QueryResult<'tcx>,
     ) {
         let mut map = self.map.borrow_mut();
         let entry = map.entry(key).or_default();
-        let data = WithDepNode::new(dep_node, result);
+        let data = WithDepNode::new(dep_node, QueryData { result, proof_tree });
         entry.cycle_participants.extend(cycle_participants);
-        if did_overflow {
+        if encountered_overflow {
             entry.with_overflow.insert(reached_depth, data);
         } else {
             entry.success = Some(Success { data, reached_depth });
         }
+
+        if cfg!(debug_assertions) {
+            drop(map);
+            if Some(CacheData { result, proof_tree, reached_depth, encountered_overflow })
+                != self.get(tcx, key, |_| false, Limit(reached_depth))
+            {
+                bug!("unable to retrieve inserted element from cache: {key:?}");
+            }
+        }
     }
 
     /// Try to fetch a cached result, checking the recursion limit
@@ -62,27 +75,39 @@ impl<'tcx> EvaluationCache<'tcx> {
 
         if let Some(ref success) = entry.success {
             if available_depth.value_within_limit(success.reached_depth) {
+                let QueryData { result, proof_tree } = success.data.get(tcx);
                 return Some(CacheData {
-                    result: success.data.get(tcx),
+                    result,
+                    proof_tree,
                     reached_depth: success.reached_depth,
                     encountered_overflow: false,
                 });
             }
         }
 
-        entry.with_overflow.get(&available_depth.0).map(|e| CacheData {
-            result: e.get(tcx),
-            reached_depth: available_depth.0,
-            encountered_overflow: true,
+        entry.with_overflow.get(&available_depth.0).map(|e| {
+            let QueryData { result, proof_tree } = e.get(tcx);
+            CacheData {
+                result,
+                proof_tree,
+                reached_depth: available_depth.0,
+                encountered_overflow: true,
+            }
         })
     }
 }
 
 struct Success<'tcx> {
-    data: WithDepNode<QueryResult<'tcx>>,
+    data: WithDepNode<QueryData<'tcx>>,
     reached_depth: usize,
 }
 
+#[derive(Clone, Copy)]
+pub struct QueryData<'tcx> {
+    pub result: QueryResult<'tcx>,
+    pub proof_tree: Option<&'tcx [inspect::GoalEvaluationStep<'tcx>]>,
+}
+
 /// The cache entry for a goal `CanonicalInput`.
 ///
 /// This contains results whose computation never hit the
@@ -96,5 +121,5 @@ struct CacheEntry<'tcx> {
     /// See the doc comment of `StackEntry::cycle_participants` for more
     /// details.
     cycle_participants: FxHashSet<CanonicalInput<'tcx>>,
-    with_overflow: FxHashMap<usize, WithDepNode<QueryResult<'tcx>>>,
+    with_overflow: FxHashMap<usize, WithDepNode<QueryData<'tcx>>>,
 }
diff --git a/compiler/rustc_middle/src/traits/solve/inspect.rs b/compiler/rustc_middle/src/traits/solve/inspect.rs
index e7e40bee6b9..a5916c4ab85 100644
--- a/compiler/rustc_middle/src/traits/solve/inspect.rs
+++ b/compiler/rustc_middle/src/traits/solve/inspect.rs
@@ -42,12 +42,6 @@ pub struct State<'tcx, T> {
 
 pub type CanonicalState<'tcx, T> = Canonical<'tcx, State<'tcx, T>>;
 
-#[derive(Debug, Eq, PartialEq)]
-pub enum CacheHit {
-    Provisional,
-    Global,
-}
-
 /// When evaluating the root goals we also store the
 /// original values for the `CanonicalVarValues` of the
 /// canonicalized goal. We use this to map any [CanonicalState]
@@ -78,8 +72,8 @@ pub struct CanonicalGoalEvaluation<'tcx> {
 #[derive(Eq, PartialEq)]
 pub enum CanonicalGoalEvaluationKind<'tcx> {
     Overflow,
-    CacheHit(CacheHit),
-    Uncached { revisions: Vec<GoalEvaluationStep<'tcx>> },
+    CycleInStack,
+    Evaluation { revisions: &'tcx [GoalEvaluationStep<'tcx>] },
 }
 impl Debug for GoalEvaluation<'_> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
diff --git a/compiler/rustc_middle/src/traits/solve/inspect/format.rs b/compiler/rustc_middle/src/traits/solve/inspect/format.rs
index 5733be00adf..4b73d8e41a1 100644
--- a/compiler/rustc_middle/src/traits/solve/inspect/format.rs
+++ b/compiler/rustc_middle/src/traits/solve/inspect/format.rs
@@ -74,13 +74,10 @@ impl<'a, 'b> ProofTreeFormatter<'a, 'b> {
             CanonicalGoalEvaluationKind::Overflow => {
                 writeln!(self.f, "OVERFLOW: {:?}", eval.result)
             }
-            CanonicalGoalEvaluationKind::CacheHit(CacheHit::Global) => {
-                writeln!(self.f, "GLOBAL CACHE HIT: {:?}", eval.result)
+            CanonicalGoalEvaluationKind::CycleInStack => {
+                writeln!(self.f, "CYCLE IN STACK: {:?}", eval.result)
             }
-            CanonicalGoalEvaluationKind::CacheHit(CacheHit::Provisional) => {
-                writeln!(self.f, "PROVISIONAL CACHE HIT: {:?}", eval.result)
-            }
-            CanonicalGoalEvaluationKind::Uncached { revisions } => {
+            CanonicalGoalEvaluationKind::Evaluation { revisions } => {
                 for (n, step) in revisions.iter().enumerate() {
                     writeln!(self.f, "REVISION {n}")?;
                     self.nested(|this| this.format_evaluation_step(step))?;
diff --git a/compiler/rustc_session/src/options.rs b/compiler/rustc_session/src/options.rs
index 30c8b9d6700..25a4547362c 100644
--- a/compiler/rustc_session/src/options.rs
+++ b/compiler/rustc_session/src/options.rs
@@ -1529,8 +1529,6 @@ options! {
     dump_solver_proof_tree: DumpSolverProofTree = (DumpSolverProofTree::Never, parse_dump_solver_proof_tree, [UNTRACKED],
         "dump a proof tree for every goal evaluated by the new trait solver. If the flag is specified without any options after it
         then it defaults to `always`. If the flag is not specified at all it defaults to `on-request`."),
-    dump_solver_proof_tree_use_cache: Option<bool> = (None, parse_opt_bool, [UNTRACKED],
-        "determines whether dumped proof trees use the global cache"),
     dwarf_version: Option<u32> = (None, parse_opt_number, [TRACKED],
         "version of DWARF debug information to emit (default: 2 or 4, depending on platform)"),
     dylib_lto: bool = (false, parse_bool, [UNTRACKED],
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
index 066129d8e47..70235b710e2 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
@@ -119,25 +119,11 @@ impl NestedGoals<'_> {
 
 #[derive(PartialEq, Eq, Debug, Hash, HashStable, Clone, Copy)]
 pub enum GenerateProofTree {
-    Yes(UseGlobalCache),
+    Yes,
     IfEnabled,
     Never,
 }
 
-#[derive(PartialEq, Eq, Debug, Hash, HashStable, Clone, Copy)]
-pub enum UseGlobalCache {
-    Yes,
-    No,
-}
-impl UseGlobalCache {
-    pub fn from_bool(use_cache: bool) -> Self {
-        match use_cache {
-            true => UseGlobalCache::Yes,
-            false => UseGlobalCache::No,
-        }
-    }
-}
-
 pub trait InferCtxtEvalExt<'tcx> {
     /// Evaluates a goal from **outside** of the trait solver.
     ///
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
index 15c8d9e5bcb..69bfdd4688c 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
@@ -17,7 +17,7 @@ use rustc_middle::traits::solve::{Certainty, Goal};
 use rustc_middle::ty;
 
 use crate::solve::inspect::ProofTreeBuilder;
-use crate::solve::{GenerateProofTree, InferCtxtEvalExt, UseGlobalCache};
+use crate::solve::{GenerateProofTree, InferCtxtEvalExt};
 
 pub struct InspectGoal<'a, 'tcx> {
     infcx: &'a InferCtxt<'tcx>,
@@ -82,8 +82,7 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> {
                 }
 
                 for &goal in &instantiated_goals {
-                    let (_, proof_tree) =
-                        infcx.evaluate_root_goal(goal, GenerateProofTree::Yes(UseGlobalCache::No));
+                    let (_, proof_tree) = infcx.evaluate_root_goal(goal, GenerateProofTree::Yes);
                     let proof_tree = proof_tree.unwrap();
                     visitor.visit_goal(&InspectGoal::new(
                         infcx,
@@ -169,11 +168,11 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
         let mut candidates = vec![];
         let last_eval_step = match self.evaluation.evaluation.kind {
             inspect::CanonicalGoalEvaluationKind::Overflow
-            | inspect::CanonicalGoalEvaluationKind::CacheHit(_) => {
+            | inspect::CanonicalGoalEvaluationKind::CycleInStack => {
                 warn!("unexpected root evaluation: {:?}", self.evaluation);
                 return vec![];
             }
-            inspect::CanonicalGoalEvaluationKind::Uncached { ref revisions } => {
+            inspect::CanonicalGoalEvaluationKind::Evaluation { ref revisions } => {
                 if let Some(last) = revisions.last() {
                     last
                 } else {
@@ -227,8 +226,7 @@ impl<'tcx> ProofTreeInferCtxtExt<'tcx> for InferCtxt<'tcx> {
         goal: Goal<'tcx, ty::Predicate<'tcx>>,
         visitor: &mut V,
     ) -> ControlFlow<V::BreakTy> {
-        let (_, proof_tree) =
-            self.evaluate_root_goal(goal, GenerateProofTree::Yes(UseGlobalCache::No));
+        let (_, proof_tree) = self.evaluate_root_goal(goal, GenerateProofTree::Yes);
         let proof_tree = proof_tree.unwrap();
         visitor.visit_goal(&InspectGoal::new(self, 0, &proof_tree))
     }
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/build.rs b/compiler/rustc_trait_selection/src/solve/inspect/build.rs
index 2eba98b02e9..088455b38cb 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/build.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect/build.rs
@@ -3,6 +3,8 @@
 //! This code is *a bit* of a mess and can hopefully be
 //! mostly ignored. For a general overview of how it works,
 //! see the comment on [ProofTreeBuilder].
+use std::mem;
+
 use rustc_middle::traits::query::NoSolution;
 use rustc_middle::traits::solve::{
     CanonicalInput, Certainty, Goal, IsNormalizesToHack, QueryInput, QueryResult,
@@ -10,7 +12,6 @@ use rustc_middle::traits::solve::{
 use rustc_middle::ty::{self, TyCtxt};
 use rustc_session::config::DumpSolverProofTree;
 
-use crate::solve::eval_ctxt::UseGlobalCache;
 use crate::solve::{self, inspect, EvalCtxt, GenerateProofTree};
 
 /// The core data structure when building proof trees.
@@ -34,12 +35,7 @@ use crate::solve::{self, inspect, EvalCtxt, GenerateProofTree};
 /// is called to recursively convert the whole structure to a
 /// finished proof tree.
 pub(in crate::solve) struct ProofTreeBuilder<'tcx> {
-    state: Option<Box<BuilderData<'tcx>>>,
-}
-
-struct BuilderData<'tcx> {
-    tree: DebugSolver<'tcx>,
-    use_global_cache: UseGlobalCache,
+    state: Option<Box<DebugSolver<'tcx>>>,
 }
 
 /// The current state of the proof tree builder, at most places
@@ -118,36 +114,46 @@ pub(in crate::solve) enum WipGoalEvaluationKind<'tcx> {
     Nested { is_normalizes_to_hack: IsNormalizesToHack },
 }
 
-#[derive(Eq, PartialEq, Debug)]
-pub(in crate::solve) enum WipCanonicalGoalEvaluationKind {
+#[derive(Eq, PartialEq)]
+pub(in crate::solve) enum WipCanonicalGoalEvaluationKind<'tcx> {
     Overflow,
-    CacheHit(inspect::CacheHit),
+    CycleInStack,
+    Interned { revisions: &'tcx [inspect::GoalEvaluationStep<'tcx>] },
+}
+
+impl std::fmt::Debug for WipCanonicalGoalEvaluationKind<'_> {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Self::Overflow => write!(f, "Overflow"),
+            Self::CycleInStack => write!(f, "CycleInStack"),
+            Self::Interned { revisions: _ } => f.debug_struct("Interned").finish_non_exhaustive(),
+        }
+    }
 }
 
 #[derive(Eq, PartialEq, Debug)]
 struct WipCanonicalGoalEvaluation<'tcx> {
     goal: CanonicalInput<'tcx>,
-    kind: Option<WipCanonicalGoalEvaluationKind>,
+    kind: Option<WipCanonicalGoalEvaluationKind<'tcx>>,
+    /// Only used for uncached goals. After we finished evaluating
+    /// the goal, this is interned and moved into `kind`.
     revisions: Vec<WipGoalEvaluationStep<'tcx>>,
     result: Option<QueryResult<'tcx>>,
 }
 
 impl<'tcx> WipCanonicalGoalEvaluation<'tcx> {
     fn finalize(self) -> inspect::CanonicalGoalEvaluation<'tcx> {
-        let kind = match self.kind {
-            Some(WipCanonicalGoalEvaluationKind::Overflow) => {
+        assert!(self.revisions.is_empty());
+        let kind = match self.kind.unwrap() {
+            WipCanonicalGoalEvaluationKind::Overflow => {
                 inspect::CanonicalGoalEvaluationKind::Overflow
             }
-            Some(WipCanonicalGoalEvaluationKind::CacheHit(hit)) => {
-                inspect::CanonicalGoalEvaluationKind::CacheHit(hit)
+            WipCanonicalGoalEvaluationKind::CycleInStack => {
+                inspect::CanonicalGoalEvaluationKind::CycleInStack
+            }
+            WipCanonicalGoalEvaluationKind::Interned { revisions } => {
+                inspect::CanonicalGoalEvaluationKind::Evaluation { revisions }
             }
-            None => inspect::CanonicalGoalEvaluationKind::Uncached {
-                revisions: self
-                    .revisions
-                    .into_iter()
-                    .map(WipGoalEvaluationStep::finalize)
-                    .collect(),
-            },
         };
 
         inspect::CanonicalGoalEvaluation { goal: self.goal, kind, result: self.result.unwrap() }
@@ -226,33 +232,20 @@ impl<'tcx> WipProbeStep<'tcx> {
 }
 
 impl<'tcx> ProofTreeBuilder<'tcx> {
-    fn new(
-        state: impl Into<DebugSolver<'tcx>>,
-        use_global_cache: UseGlobalCache,
-    ) -> ProofTreeBuilder<'tcx> {
-        ProofTreeBuilder {
-            state: Some(Box::new(BuilderData { tree: state.into(), use_global_cache })),
-        }
+    fn new(state: impl Into<DebugSolver<'tcx>>) -> ProofTreeBuilder<'tcx> {
+        ProofTreeBuilder { state: Some(Box::new(state.into())) }
     }
 
     fn nested<T: Into<DebugSolver<'tcx>>>(&self, state: impl FnOnce() -> T) -> Self {
-        match &self.state {
-            Some(prev_state) => Self {
-                state: Some(Box::new(BuilderData {
-                    tree: state().into(),
-                    use_global_cache: prev_state.use_global_cache,
-                })),
-            },
-            None => Self { state: None },
-        }
+        ProofTreeBuilder { state: self.state.as_ref().map(|_| Box::new(state().into())) }
     }
 
     fn as_mut(&mut self) -> Option<&mut DebugSolver<'tcx>> {
-        self.state.as_mut().map(|boxed| &mut boxed.tree)
+        self.state.as_deref_mut()
     }
 
     pub fn finalize(self) -> Option<inspect::GoalEvaluation<'tcx>> {
-        match self.state?.tree {
+        match *self.state? {
             DebugSolver::GoalEvaluation(wip_goal_evaluation) => {
                 Some(wip_goal_evaluation.finalize())
             }
@@ -260,13 +253,6 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
         }
     }
 
-    pub fn use_global_cache(&self) -> bool {
-        self.state
-            .as_ref()
-            .map(|state| matches!(state.use_global_cache, UseGlobalCache::Yes))
-            .unwrap_or(true)
-    }
-
     pub fn new_maybe_root(
         tcx: TyCtxt<'tcx>,
         generate_proof_tree: GenerateProofTree,
@@ -276,10 +262,7 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
             GenerateProofTree::IfEnabled => {
                 let opts = &tcx.sess.opts.unstable_opts;
                 match opts.dump_solver_proof_tree {
-                    DumpSolverProofTree::Always => {
-                        let use_cache = opts.dump_solver_proof_tree_use_cache.unwrap_or(true);
-                        ProofTreeBuilder::new_root(UseGlobalCache::from_bool(use_cache))
-                    }
+                    DumpSolverProofTree::Always => ProofTreeBuilder::new_root(),
                     // `OnError` is handled by reevaluating goals in error
                     // reporting with `GenerateProofTree::Yes`.
                     DumpSolverProofTree::OnError | DumpSolverProofTree::Never => {
@@ -287,12 +270,12 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
                     }
                 }
             }
-            GenerateProofTree::Yes(use_cache) => ProofTreeBuilder::new_root(use_cache),
+            GenerateProofTree::Yes => ProofTreeBuilder::new_root(),
         }
     }
 
-    pub fn new_root(use_global_cache: UseGlobalCache) -> ProofTreeBuilder<'tcx> {
-        ProofTreeBuilder::new(DebugSolver::Root, use_global_cache)
+    pub fn new_root() -> ProofTreeBuilder<'tcx> {
+        ProofTreeBuilder::new(DebugSolver::Root)
     }
 
     pub fn new_noop() -> ProofTreeBuilder<'tcx> {
@@ -336,9 +319,27 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
         })
     }
 
+    pub fn finalize_evaluation(
+        &mut self,
+        tcx: TyCtxt<'tcx>,
+    ) -> Option<&'tcx [inspect::GoalEvaluationStep<'tcx>]> {
+        self.as_mut().map(|this| match this {
+            DebugSolver::CanonicalGoalEvaluation(evaluation) => {
+                let revisions = mem::take(&mut evaluation.revisions)
+                    .into_iter()
+                    .map(WipGoalEvaluationStep::finalize);
+                let revisions = &*tcx.arena.alloc_from_iter(revisions);
+                let kind = WipCanonicalGoalEvaluationKind::Interned { revisions };
+                assert_eq!(evaluation.kind.replace(kind), None);
+                revisions
+            }
+            _ => unreachable!(),
+        })
+    }
+
     pub fn canonical_goal_evaluation(&mut self, canonical_goal_evaluation: ProofTreeBuilder<'tcx>) {
         if let Some(this) = self.as_mut() {
-            match (this, canonical_goal_evaluation.state.unwrap().tree) {
+            match (this, *canonical_goal_evaluation.state.unwrap()) {
                 (
                     DebugSolver::GoalEvaluation(goal_evaluation),
                     DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluation),
@@ -348,7 +349,7 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
         }
     }
 
-    pub fn goal_evaluation_kind(&mut self, kind: WipCanonicalGoalEvaluationKind) {
+    pub fn goal_evaluation_kind(&mut self, kind: WipCanonicalGoalEvaluationKind<'tcx>) {
         if let Some(this) = self.as_mut() {
             match this {
                 DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluation) => {
@@ -372,7 +373,7 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
     }
     pub fn goal_evaluation(&mut self, goal_evaluation: ProofTreeBuilder<'tcx>) {
         if let Some(this) = self.as_mut() {
-            match (this, goal_evaluation.state.unwrap().tree) {
+            match (this, *goal_evaluation.state.unwrap()) {
                 (
                     DebugSolver::AddedGoalsEvaluation(WipAddedGoalsEvaluation {
                         evaluations, ..
@@ -396,7 +397,7 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
     }
     pub fn goal_evaluation_step(&mut self, goal_evaluation_step: ProofTreeBuilder<'tcx>) {
         if let Some(this) = self.as_mut() {
-            match (this, goal_evaluation_step.state.unwrap().tree) {
+            match (this, *goal_evaluation_step.state.unwrap()) {
                 (
                     DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluations),
                     DebugSolver::GoalEvaluationStep(goal_evaluation_step),
@@ -444,7 +445,7 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
 
     pub fn finish_probe(&mut self, probe: ProofTreeBuilder<'tcx>) {
         if let Some(this) = self.as_mut() {
-            match (this, probe.state.unwrap().tree) {
+            match (this, *probe.state.unwrap()) {
                 (
                     DebugSolver::Probe(WipProbe { steps, .. })
                     | DebugSolver::GoalEvaluationStep(WipGoalEvaluationStep {
@@ -486,7 +487,7 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
 
     pub fn added_goals_evaluation(&mut self, added_goals_evaluation: ProofTreeBuilder<'tcx>) {
         if let Some(this) = self.as_mut() {
-            match (this, added_goals_evaluation.state.unwrap().tree) {
+            match (this, *added_goals_evaluation.state.unwrap()) {
                 (
                     DebugSolver::GoalEvaluationStep(WipGoalEvaluationStep {
                         evaluation: WipProbe { steps, .. },
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index d45fe102805..dba5369fa0f 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -38,9 +38,7 @@ mod project_goals;
 mod search_graph;
 mod trait_goals;
 
-pub use eval_ctxt::{
-    EvalCtxt, GenerateProofTree, InferCtxtEvalExt, InferCtxtSelectExt, UseGlobalCache,
-};
+pub use eval_ctxt::{EvalCtxt, GenerateProofTree, InferCtxtEvalExt, InferCtxtSelectExt};
 pub use fulfill::FulfillmentCtxt;
 pub(crate) use normalize::{deeply_normalize, deeply_normalize_with_skipped_universes};
 
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph.rs b/compiler/rustc_trait_selection/src/solve/search_graph.rs
index 33513f6bd43..7ffa1d7d319 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph.rs
@@ -6,7 +6,6 @@ use rustc_data_structures::fx::FxHashSet;
 use rustc_index::Idx;
 use rustc_index::IndexVec;
 use rustc_middle::dep_graph::dep_kinds;
-use rustc_middle::traits::solve::inspect::CacheHit;
 use rustc_middle::traits::solve::CacheData;
 use rustc_middle::traits::solve::{CanonicalInput, Certainty, EvaluationCache, QueryResult};
 use rustc_middle::ty::TyCtxt;
@@ -191,8 +190,8 @@ impl<'tcx> SearchGraph<'tcx> {
         };
 
         // Try to fetch the goal from the global cache.
-        if inspect.use_global_cache() {
-            if let Some(CacheData { result, reached_depth, encountered_overflow }) =
+        'global: {
+            let Some(CacheData { result, proof_tree, reached_depth, encountered_overflow }) =
                 self.global_cache(tcx).get(
                     tcx,
                     input,
@@ -201,13 +200,26 @@ impl<'tcx> SearchGraph<'tcx> {
                     },
                     available_depth,
                 )
-            {
-                inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::CacheHit(
-                    CacheHit::Global,
-                ));
-                self.on_cache_hit(reached_depth, encountered_overflow);
-                return result;
+            else {
+                break 'global;
+            };
+
+            // If we're building a proof tree and the current cache entry does not
+            // contain a proof tree, we do not use the entry but instead recompute
+            // the goal. We simply overwrite the existing entry once we're done,
+            // caching the proof tree.
+            if !inspect.is_noop() {
+                if let Some(revisions) = proof_tree {
+                    inspect.goal_evaluation_kind(
+                        inspect::WipCanonicalGoalEvaluationKind::Interned { revisions },
+                    );
+                } else {
+                    break 'global;
+                }
             }
+
+            self.on_cache_hit(reached_depth, encountered_overflow);
+            return result;
         }
 
         // Check whether we're in a cycle.
@@ -238,9 +250,7 @@ impl<'tcx> SearchGraph<'tcx> {
             // Finally we can return either the provisional response for that goal if we have a
             // coinductive cycle or an ambiguous result if the cycle is inductive.
             Entry::Occupied(entry) => {
-                inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::CacheHit(
-                    CacheHit::Provisional,
-                ));
+                inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::CycleInStack);
 
                 let stack_depth = *entry.get();
                 debug!("encountered cycle with depth {stack_depth:?}");
@@ -329,6 +339,8 @@ impl<'tcx> SearchGraph<'tcx> {
                 (current_entry, result)
             });
 
+        let proof_tree = inspect.finalize_evaluation(tcx);
+
         // We're now done with this goal. In case this goal is involved in a larger cycle
         // do not remove it from the provisional cache and update its provisional result.
         // We only add the root of cycles to the global cache.
@@ -346,7 +358,9 @@ impl<'tcx> SearchGraph<'tcx> {
             // more details.
             let reached_depth = final_entry.reached_depth.as_usize() - self.stack.len();
             self.global_cache(tcx).insert(
+                tcx,
                 input,
+                proof_tree,
                 reached_depth,
                 final_entry.encountered_overflow,
                 final_entry.cycle_participants,
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
index 79b09db2268..0796cb57d97 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
@@ -8,7 +8,7 @@ mod type_err_ctxt_ext;
 
 use super::{Obligation, ObligationCause, ObligationCauseCode, PredicateObligation};
 use crate::infer::InferCtxt;
-use crate::solve::{GenerateProofTree, InferCtxtEvalExt, UseGlobalCache};
+use crate::solve::{GenerateProofTree, InferCtxtEvalExt};
 use rustc_hir as hir;
 use rustc_hir::def_id::DefId;
 use rustc_hir::intravisit::Visitor;
@@ -173,7 +173,7 @@ pub fn dump_proof_tree<'tcx>(o: &Obligation<'tcx, ty::Predicate<'tcx>>, infcx: &
     infcx.probe(|_| {
         let goal = Goal { predicate: o.predicate, param_env: o.param_env };
         let tree = infcx
-            .evaluate_root_goal(goal, GenerateProofTree::Yes(UseGlobalCache::No))
+            .evaluate_root_goal(goal, GenerateProofTree::Yes)
             .1
             .expect("proof tree should have been generated");
         let mut lock = std::io::stdout().lock();