Rollup merge of #113887 - lcnr:cache-coherence, r=compiler-errors

new solver: add a separate cache for coherence

based on #113835

`typenum` now compiles with `-Ztrait-solver=next-coherence`. Because we disable caching once we encounter the recursion limit it is still really slow, but at least it passes and I will deal with overflow handling afterwards.

`typenum` previously hanged. The top 10 goals were
```rust
1749948 counts
(  1)   601056 (34.3%, 34.3%): Canonical { value: QueryInput { goal: Goal { predicate: Binder { value: ProjectionPredicate(AliasTy { args: [^1_0], def_id: DefId(0:1196 ~ typenum[0ab6]::type_operators::Len::Output) }, Term::Ty(^1_1)), bound_vars: [] }, param_env: ParamEnv { caller_bounds: [], reveal: UserFacing, constness: NotConst } }, anchor: Bubble, predefined_opaques_in_body: PredefinedOpaques(PredefinedOpaquesData { opaque_types: [] }) }, max_universe: U0, variables: [CanonicalVarInfo { kind: Ty(General(U0)) }, CanonicalVarInfo { kind: Ty(General(U0)) }] }
(  2)   240422 (13.7%, 48.1%): Canonical { value: QueryInput { goal: Goal { predicate: Binder { value: ProjectionPredicate(AliasTy { args: [<^1_0 as type_operators::Len>::Output, bit::B1], def_id: DefId(1:2752 ~ core[a405]::ops::arith::Add::Output) }, Term::Ty(^1_1)), bound_vars: [] }, param_env: ParamEnv { caller_bounds: [], reveal: UserFacing, constness: NotConst } }, anchor: Bubble, predefined_opaques_in_body: PredefinedOpaques(PredefinedOpaquesData { opaque_types: [] }) }, max_universe: U0, variables: [CanonicalVarInfo { kind: Ty(General(U0)) }, CanonicalVarInfo { kind: Ty(General(U0)) }] }
(  3)   198367 (11.3%, 59.4%): Canonical { value: QueryInput { goal: Goal { predicate: Binder { value: TraitPredicate(<^1_0 as core::marker::Sized>, polarity:Positive), bound_vars: [] }, param_env: ParamEnv { caller_bounds: [], reveal: UserFacing, constness: NotConst } }, anchor: Bubble, predefined_opaques_in_body: PredefinedOpaques(PredefinedOpaquesData { opaque_types: [] }) }, max_universe: U0, variables: [CanonicalVarInfo { kind: Ty(General(U0)) }] }
(  4)    96168 ( 5.5%, 64.9%): Canonical { value: QueryInput { goal: Goal { predicate: Binder { value: ProjectionPredicate(AliasTy { args: [<^1_0 as type_operators::Len>::Output, bit::B1], def_id: DefId(1:2752 ~ core[a405]::ops::arith::Add::Output) }, Term::Ty(<<^1_0 as type_operators::Len>::Output as core::ops::Add<bit::B1>>::Output)), bound_vars: [] }, param_env: ParamEnv { caller_bounds: [], reveal: UserFacing, constness: NotConst } }, anchor: Bubble, predefined_opaques_in_body: PredefinedOpaques(PredefinedOpaquesData { opaque_types: [] }) }, max_universe: U0, variables: [CanonicalVarInfo { kind: Ty(General(U0)) }] }
(  5)    78155 ( 4.5%, 69.4%): Canonical { value: QueryInput { goal: Goal { predicate: Binder { value: TraitPredicate(<^1_0 as marker_traits::Unsigned>, polarity:Positive), bound_vars: [] }, param_env: ParamEnv { caller_bounds: [], reveal: UserFacing, constness: NotConst } }, anchor: Bubble, predefined_opaques_in_body: PredefinedOpaques(PredefinedOpaquesData { opaque_types: [] }) }, max_universe: U0, variables: [CanonicalVarInfo { kind: Ty(General(U0)) }] }
(  6)    72140 ( 4.1%, 73.5%): Canonical { value: QueryInput { goal: Goal { predicate: Binder { value: TraitPredicate(<^1_0 as marker_traits::Bit>, polarity:Positive), bound_vars: [] }, param_env: ParamEnv { caller_bounds: [], reveal: UserFacing, constness: NotConst } }, anchor: Bubble, predefined_opaques_in_body: PredefinedOpaques(PredefinedOpaquesData { opaque_types: [] }) }, max_universe: U0, variables: [CanonicalVarInfo { kind: Ty(General(U0)) }] }
(  7)    60107 ( 3.4%, 76.9%): Canonical { value: QueryInput { goal: Goal { predicate: Binder { value: TraitPredicate(<^1_0 as type_operators::Len>, polarity:Positive), bound_vars: [] }, param_env: ParamEnv { caller_bounds: [], reveal: UserFacing, constness: NotConst } }, anchor: Bubble, predefined_opaques_in_body: PredefinedOpaques(PredefinedOpaquesData { opaque_types: [] }) }, max_universe: U0, variables: [CanonicalVarInfo { kind: Ty(General(U0)) }] }
(  8)    60106 ( 3.4%, 80.4%): Canonical { value: QueryInput { goal: Goal { predicate: Binder { value: ProjectionPredicate(AliasTy { args: [uint::UInt<^1_0, ^1_1>], def_id: DefId(0:1196 ~ typenum[0ab6]::type_operators::Len::Output) }, Term::Ty(^1_2)), bound_vars: [] }, param_env: ParamEnv { caller_bounds: [], reveal: UserFacing, constness: NotConst } }, anchor: Bubble, predefined_opaques_in_body: PredefinedOpaques(PredefinedOpaquesData { opaque_types: [] }) }, max_universe: U0, variables: [CanonicalVarInfo { kind: Ty(General(U0)) }, CanonicalVarInfo { kind: Ty(General(U0)) }, CanonicalVarInfo { kind: Ty(General(U0)) }] }
(  9)    60106 ( 3.4%, 83.8%): Canonical { value: QueryInput { goal: Goal { predicate: Binder { value: TraitPredicate(<<<^1_0 as type_operators::Len>::Output as core::ops::Add<bit::B1>>::Output as marker_traits::Unsigned>, polarity:Positive), bound_vars: [] }, param_env: ParamEnv { caller_bounds: [], reveal: UserFacing, constness: NotConst } }, anchor: Bubble, predefined_opaques_in_body: PredefinedOpaques(PredefinedOpaquesData { opaque_types: [] }) }, max_universe: U0, variables: [CanonicalVarInfo { kind: Ty(General(U0)) }] }
( 10)    60106 ( 3.4%, 87.2%): Canonical { value: QueryInput { goal: Goal { predicate: Binder { value: TraitPredicate(<<^1_0 as type_operators::Len>::Output as core::ops::Add<bit::B1>>, polarity:Positive), bound_vars: [] }, param_env: ParamEnv { caller_bounds: [], reveal: UserFacing, constness: NotConst } }, anchor: Bubble, predefined_opaques_in_body: PredefinedOpaques(PredefinedOpaquesData { opaque_types: [] }) }, max_universe: U0, variables: [CanonicalVarInfo { kind: Ty(General(U0)) }] }
```

r? ``@compiler-errors``

2 files changed, 20 insertions, 17 deletions

diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index 1a23fa80210..aa1f8e48b1b 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -569,6 +569,7 @@ pub struct GlobalCtxt<'tcx> {
 
     /// Caches the results of goal evaluation in the new solver.
     pub new_solver_evaluation_cache: solve::EvaluationCache<'tcx>,
+    pub new_solver_coherence_evaluation_cache: solve::EvaluationCache<'tcx>,
 
     /// Data layout specification for the current target.
     pub data_layout: TargetDataLayout,
@@ -680,10 +681,12 @@ impl<'tcx> TyCtxt<'tcx> {
         value.lift_to_tcx(self)
     }
 
-    /// Creates a type context and call the closure with a `TyCtxt` reference
-    /// to the context. The closure enforces that the type context and any interned
-    /// value (types, args, etc.) can only be used while `ty::tls` has a valid
-    /// reference to the context, to allow formatting values that need it.
+    /// Creates a type context. To use the context call `fn enter` which
+    /// provides a `TyCtxt`.
+    ///
+    /// By only providing the `TyCtxt` inside of the closure we enforce that the type
+    /// context and any interned alue (types, args, etc.) can only be used while `ty::tls`
+    /// has a valid reference to the context, to allow formatting values that need it.
     pub fn create_global_ctxt(
         s: &'tcx Session,
         lint_store: Lrc<dyn Any + sync::DynSend + sync::DynSync>,
@@ -721,6 +724,7 @@ impl<'tcx> TyCtxt<'tcx> {
             selection_cache: Default::default(),
             evaluation_cache: Default::default(),
             new_solver_evaluation_cache: Default::default(),
+            new_solver_coherence_evaluation_cache: Default::default(),
             data_layout,
             alloc_map: Lock::new(interpret::AllocMap::new()),
         }
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 f00456e26df..98c8a74752c 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
@@ -9,7 +9,9 @@ use cache::ProvisionalCache;
 use overflow::OverflowData;
 use rustc_index::IndexVec;
 use rustc_middle::dep_graph::DepKind;
-use rustc_middle::traits::solve::{CanonicalInput, Certainty, MaybeCause, QueryResult};
+use rustc_middle::traits::solve::{
+    CanonicalInput, Certainty, EvaluationCache, MaybeCause, QueryResult,
+};
 use rustc_middle::ty::TyCtxt;
 use std::{collections::hash_map::Entry, mem};
 
@@ -58,10 +60,10 @@ impl<'tcx> SearchGraph<'tcx> {
     ///
     /// We could add another global cache for coherence instead,
     /// but that's effort so let's only do it if necessary.
-    pub(super) fn should_use_global_cache(&self) -> bool {
+    pub(super) fn global_cache(&self, tcx: TyCtxt<'tcx>) -> &'tcx EvaluationCache<'tcx> {
         match self.mode {
-            SolverMode::Normal => true,
-            SolverMode::Coherence => false,
+            SolverMode::Normal => &tcx.new_solver_evaluation_cache,
+            SolverMode::Coherence => &tcx.new_solver_coherence_evaluation_cache,
         }
     }
 
@@ -213,8 +215,8 @@ impl<'tcx> SearchGraph<'tcx> {
         inspect: &mut ProofTreeBuilder<'tcx>,
         mut loop_body: impl FnMut(&mut Self, &mut ProofTreeBuilder<'tcx>) -> QueryResult<'tcx>,
     ) -> QueryResult<'tcx> {
-        if self.should_use_global_cache() && inspect.use_global_cache() {
-            if let Some(result) = tcx.new_solver_evaluation_cache.get(&canonical_input, tcx) {
+        if inspect.use_global_cache() {
+            if let Some(result) = self.global_cache(tcx).get(&canonical_input, tcx) {
                 debug!(?canonical_input, ?result, "cache hit");
                 inspect.cache_hit(CacheHit::Global);
                 return result;
@@ -278,13 +280,10 @@ impl<'tcx> SearchGraph<'tcx> {
             // 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 can_cache = !self.overflow_data.did_overflow() || self.stack.is_empty();
-            if self.should_use_global_cache() && can_cache {
-                tcx.new_solver_evaluation_cache.insert(
-                    current_goal.input,
-                    dep_node,
-                    current_goal.response,
-                );
+            let can_cache = inspect.use_global_cache()
+                && (!self.overflow_data.did_overflow() || self.stack.is_empty());
+            if can_cache {
+                self.global_cache(tcx).insert(current_goal.input, dep_node, current_goal.response)
             }
         }