diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve/search_graph/mod.rs')
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/search_graph/mod.rs | 149 |
1 files changed, 94 insertions, 55 deletions
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 c7eb8de65..050269fa9 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs @@ -1,15 +1,19 @@ mod cache; mod overflow; +pub(super) use overflow::OverflowHandler; + 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}; +use super::SolverMode; + rustc_index::newtype_index! { pub struct StackDepth {} } @@ -20,6 +24,7 @@ struct StackElem<'tcx> { } pub(super) struct SearchGraph<'tcx> { + mode: SolverMode, /// The stack of goals currently being computed. /// /// An element is *deeper* in the stack if its index is *lower*. @@ -29,24 +34,43 @@ pub(super) struct SearchGraph<'tcx> { } impl<'tcx> SearchGraph<'tcx> { - pub(super) fn new(tcx: TyCtxt<'tcx>) -> SearchGraph<'tcx> { + pub(super) fn new(tcx: TyCtxt<'tcx>, mode: SolverMode) -> SearchGraph<'tcx> { Self { + mode, stack: Default::default(), overflow_data: OverflowData::new(tcx), provisional_cache: ProvisionalCache::empty(), } } + pub(super) fn solver_mode(&self) -> SolverMode { + self.mode + } + + /// We do not use the global cache during coherence. + /// + /// The trait solver behavior is different for coherence + /// so we would have to add the solver mode to the cache key. + /// This is probably not worth it as trait solving during + /// coherence tends to already be incredibly fast. + /// + /// 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 { + match self.mode { + SolverMode::Normal => true, + SolverMode::Coherence => false, + } + } + pub(super) fn is_empty(&self) -> bool { - self.stack.is_empty() - && self.provisional_cache.is_empty() - && !self.overflow_data.did_overflow() + self.stack.is_empty() && self.provisional_cache.is_empty() } /// Whether we're currently in a cycle. This should only be used /// for debug assertions. pub(super) fn in_cycle(&self) -> bool { - if let Some(stack_depth) = self.stack.last() { + if let Some(stack_depth) = self.stack.last_index() { // Either the current goal on the stack is the root of a cycle... if self.stack[stack_depth].has_been_used { return true; @@ -70,8 +94,6 @@ impl<'tcx> SearchGraph<'tcx> { tcx: TyCtxt<'tcx>, goal: CanonicalGoal<'tcx>, ) -> Result<(), QueryResult<'tcx>> { - // FIXME: start by checking the global cache - // Look at the provisional cache to check for cycles. let cache = &mut self.provisional_cache; match cache.lookup_table.entry(goal) { @@ -131,7 +153,7 @@ impl<'tcx> SearchGraph<'tcx> { /// coinductive cycles. /// /// When we encounter a coinductive cycle, we have to prove the final result of that cycle - /// while we are still computing that result. Because of this we continously recompute the + /// while we are still computing that result. Because of this we continuously recompute the /// cycle until the result of the previous iteration is equal to the final result, at which /// point we are done. /// @@ -139,10 +161,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 +197,90 @@ 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 self.should_use_global_cache() { + if let Some(result) = tcx.new_solver_evaluation_cache.get(&canonical_goal, tcx) { + debug!(?canonical_goal, ?result, "cache hit"); + 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(¤t_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 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.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 } } |