diff options
Diffstat (limited to 'compiler/rustc_query_system/src/query')
-rw-r--r-- | compiler/rustc_query_system/src/query/README.md | 3 | ||||
-rw-r--r-- | compiler/rustc_query_system/src/query/caches.rs | 226 | ||||
-rw-r--r-- | compiler/rustc_query_system/src/query/config.rs | 75 | ||||
-rw-r--r-- | compiler/rustc_query_system/src/query/job.rs | 612 | ||||
-rw-r--r-- | compiler/rustc_query_system/src/query/mod.rs | 125 | ||||
-rw-r--r-- | compiler/rustc_query_system/src/query/plumbing.rs | 742 |
6 files changed, 1783 insertions, 0 deletions
diff --git a/compiler/rustc_query_system/src/query/README.md b/compiler/rustc_query_system/src/query/README.md new file mode 100644 index 000000000..8ec07b9fd --- /dev/null +++ b/compiler/rustc_query_system/src/query/README.md @@ -0,0 +1,3 @@ +For more information about how the query system works, see the [rustc dev guide]. + +[rustc dev guide]: https://rustc-dev-guide.rust-lang.org/query.html diff --git a/compiler/rustc_query_system/src/query/caches.rs b/compiler/rustc_query_system/src/query/caches.rs new file mode 100644 index 000000000..85c5af72e --- /dev/null +++ b/compiler/rustc_query_system/src/query/caches.rs @@ -0,0 +1,226 @@ +use crate::dep_graph::DepNodeIndex; + +use rustc_arena::TypedArena; +use rustc_data_structures::fx::FxHashMap; +use rustc_data_structures::sharded; +#[cfg(parallel_compiler)] +use rustc_data_structures::sharded::Sharded; +#[cfg(not(parallel_compiler))] +use rustc_data_structures::sync::Lock; +use rustc_data_structures::sync::WorkerLocal; +use std::default::Default; +use std::fmt::Debug; +use std::hash::Hash; +use std::marker::PhantomData; + +pub trait CacheSelector<K, V> { + type Cache; +} + +pub trait QueryStorage { + type Value: Debug; + type Stored: Clone; + + /// Store a value without putting it in the cache. + /// This is meant to be used with cycle errors. + fn store_nocache(&self, value: Self::Value) -> Self::Stored; +} + +pub trait QueryCache: QueryStorage + Sized { + type Key: Hash + Eq + Clone + Debug; + + /// Checks if the query is already computed and in the cache. + /// It returns the shard index and a lock guard to the shard, + /// which will be used if the query is not in the cache and we need + /// to compute it. + fn lookup<R, OnHit>( + &self, + key: &Self::Key, + // `on_hit` can be called while holding a lock to the query state shard. + on_hit: OnHit, + ) -> Result<R, ()> + where + OnHit: FnOnce(&Self::Stored, DepNodeIndex) -> R; + + fn complete(&self, key: Self::Key, value: Self::Value, index: DepNodeIndex) -> Self::Stored; + + fn iter(&self, f: &mut dyn FnMut(&Self::Key, &Self::Value, DepNodeIndex)); +} + +pub struct DefaultCacheSelector; + +impl<K: Eq + Hash, V: Clone> CacheSelector<K, V> for DefaultCacheSelector { + type Cache = DefaultCache<K, V>; +} + +pub struct DefaultCache<K, V> { + #[cfg(parallel_compiler)] + cache: Sharded<FxHashMap<K, (V, DepNodeIndex)>>, + #[cfg(not(parallel_compiler))] + cache: Lock<FxHashMap<K, (V, DepNodeIndex)>>, +} + +impl<K, V> Default for DefaultCache<K, V> { + fn default() -> Self { + DefaultCache { cache: Default::default() } + } +} + +impl<K: Eq + Hash, V: Clone + Debug> QueryStorage for DefaultCache<K, V> { + type Value = V; + type Stored = V; + + #[inline] + fn store_nocache(&self, value: Self::Value) -> Self::Stored { + // We have no dedicated storage + value + } +} + +impl<K, V> QueryCache for DefaultCache<K, V> +where + K: Eq + Hash + Clone + Debug, + V: Clone + Debug, +{ + type Key = K; + + #[inline(always)] + fn lookup<R, OnHit>(&self, key: &K, on_hit: OnHit) -> Result<R, ()> + where + OnHit: FnOnce(&V, DepNodeIndex) -> R, + { + let key_hash = sharded::make_hash(key); + #[cfg(parallel_compiler)] + let lock = self.cache.get_shard_by_hash(key_hash).lock(); + #[cfg(not(parallel_compiler))] + let lock = self.cache.lock(); + let result = lock.raw_entry().from_key_hashed_nocheck(key_hash, key); + + if let Some((_, value)) = result { + let hit_result = on_hit(&value.0, value.1); + Ok(hit_result) + } else { + Err(()) + } + } + + #[inline] + fn complete(&self, key: K, value: V, index: DepNodeIndex) -> Self::Stored { + #[cfg(parallel_compiler)] + let mut lock = self.cache.get_shard_by_value(&key).lock(); + #[cfg(not(parallel_compiler))] + let mut lock = self.cache.lock(); + lock.insert(key, (value.clone(), index)); + value + } + + fn iter(&self, f: &mut dyn FnMut(&Self::Key, &Self::Value, DepNodeIndex)) { + #[cfg(parallel_compiler)] + { + let shards = self.cache.lock_shards(); + for shard in shards.iter() { + for (k, v) in shard.iter() { + f(k, &v.0, v.1); + } + } + } + #[cfg(not(parallel_compiler))] + { + let map = self.cache.lock(); + for (k, v) in map.iter() { + f(k, &v.0, v.1); + } + } + } +} + +pub struct ArenaCacheSelector<'tcx>(PhantomData<&'tcx ()>); + +impl<'tcx, K: Eq + Hash, V: 'tcx> CacheSelector<K, V> for ArenaCacheSelector<'tcx> { + type Cache = ArenaCache<'tcx, K, V>; +} + +pub struct ArenaCache<'tcx, K, V> { + arena: WorkerLocal<TypedArena<(V, DepNodeIndex)>>, + #[cfg(parallel_compiler)] + cache: Sharded<FxHashMap<K, &'tcx (V, DepNodeIndex)>>, + #[cfg(not(parallel_compiler))] + cache: Lock<FxHashMap<K, &'tcx (V, DepNodeIndex)>>, +} + +impl<'tcx, K, V> Default for ArenaCache<'tcx, K, V> { + fn default() -> Self { + ArenaCache { arena: WorkerLocal::new(|_| TypedArena::default()), cache: Default::default() } + } +} + +impl<'tcx, K: Eq + Hash, V: Debug + 'tcx> QueryStorage for ArenaCache<'tcx, K, V> { + type Value = V; + type Stored = &'tcx V; + + #[inline] + fn store_nocache(&self, value: Self::Value) -> Self::Stored { + let value = self.arena.alloc((value, DepNodeIndex::INVALID)); + let value = unsafe { &*(&value.0 as *const _) }; + &value + } +} + +impl<'tcx, K, V: 'tcx> QueryCache for ArenaCache<'tcx, K, V> +where + K: Eq + Hash + Clone + Debug, + V: Debug, +{ + type Key = K; + + #[inline(always)] + fn lookup<R, OnHit>(&self, key: &K, on_hit: OnHit) -> Result<R, ()> + where + OnHit: FnOnce(&&'tcx V, DepNodeIndex) -> R, + { + let key_hash = sharded::make_hash(key); + #[cfg(parallel_compiler)] + let lock = self.cache.get_shard_by_hash(key_hash).lock(); + #[cfg(not(parallel_compiler))] + let lock = self.cache.lock(); + let result = lock.raw_entry().from_key_hashed_nocheck(key_hash, key); + + if let Some((_, value)) = result { + let hit_result = on_hit(&&value.0, value.1); + Ok(hit_result) + } else { + Err(()) + } + } + + #[inline] + fn complete(&self, key: K, value: V, index: DepNodeIndex) -> Self::Stored { + let value = self.arena.alloc((value, index)); + let value = unsafe { &*(value as *const _) }; + #[cfg(parallel_compiler)] + let mut lock = self.cache.get_shard_by_value(&key).lock(); + #[cfg(not(parallel_compiler))] + let mut lock = self.cache.lock(); + lock.insert(key, value); + &value.0 + } + + fn iter(&self, f: &mut dyn FnMut(&Self::Key, &Self::Value, DepNodeIndex)) { + #[cfg(parallel_compiler)] + { + let shards = self.cache.lock_shards(); + for shard in shards.iter() { + for (k, v) in shard.iter() { + f(k, &v.0, v.1); + } + } + } + #[cfg(not(parallel_compiler))] + { + let map = self.cache.lock(); + for (k, v) in map.iter() { + f(k, &v.0, v.1); + } + } + } +} diff --git a/compiler/rustc_query_system/src/query/config.rs b/compiler/rustc_query_system/src/query/config.rs new file mode 100644 index 000000000..964914a13 --- /dev/null +++ b/compiler/rustc_query_system/src/query/config.rs @@ -0,0 +1,75 @@ +//! Query configuration and description traits. + +use crate::dep_graph::DepNode; +use crate::dep_graph::SerializedDepNodeIndex; +use crate::ich::StableHashingContext; +use crate::query::caches::QueryCache; +use crate::query::{QueryContext, QueryState}; + +use rustc_data_structures::fingerprint::Fingerprint; +use rustc_errors::{DiagnosticBuilder, ErrorGuaranteed}; +use std::fmt::Debug; +use std::hash::Hash; + +pub trait QueryConfig { + const NAME: &'static str; + + type Key: Eq + Hash + Clone + Debug; + type Value; + type Stored: Clone; +} + +pub struct QueryVTable<CTX: QueryContext, K, V> { + pub anon: bool, + pub dep_kind: CTX::DepKind, + pub eval_always: bool, + pub cache_on_disk: bool, + + pub compute: fn(CTX::DepContext, K) -> V, + pub hash_result: Option<fn(&mut StableHashingContext<'_>, &V) -> Fingerprint>, + pub handle_cycle_error: fn(CTX, DiagnosticBuilder<'_, ErrorGuaranteed>) -> V, + pub try_load_from_disk: Option<fn(CTX, SerializedDepNodeIndex) -> Option<V>>, +} + +impl<CTX: QueryContext, K, V> QueryVTable<CTX, K, V> { + pub(crate) fn to_dep_node(&self, tcx: CTX::DepContext, key: &K) -> DepNode<CTX::DepKind> + where + K: crate::dep_graph::DepNodeParams<CTX::DepContext>, + { + DepNode::construct(tcx, self.dep_kind, key) + } + + pub(crate) fn compute(&self, tcx: CTX::DepContext, key: K) -> V { + (self.compute)(tcx, key) + } + + pub(crate) fn try_load_from_disk(&self, tcx: CTX, index: SerializedDepNodeIndex) -> Option<V> { + self.try_load_from_disk + .expect("QueryDescription::load_from_disk() called for an unsupported query.")( + tcx, index, + ) + } +} + +pub trait QueryDescription<CTX: QueryContext>: QueryConfig { + const TRY_LOAD_FROM_DISK: Option<fn(CTX, SerializedDepNodeIndex) -> Option<Self::Value>>; + + type Cache: QueryCache<Key = Self::Key, Stored = Self::Stored, Value = Self::Value>; + + fn describe(tcx: CTX, key: Self::Key) -> String; + + // Don't use this method to access query results, instead use the methods on TyCtxt + fn query_state<'a>(tcx: CTX) -> &'a QueryState<Self::Key> + where + CTX: 'a; + + // Don't use this method to access query results, instead use the methods on TyCtxt + fn query_cache<'a>(tcx: CTX) -> &'a Self::Cache + where + CTX: 'a; + + // Don't use this method to compute query results, instead use the methods on TyCtxt + fn make_vtable(tcx: CTX, key: &Self::Key) -> QueryVTable<CTX, Self::Key, Self::Value>; + + fn cache_on_disk(tcx: CTX::DepContext, key: &Self::Key) -> bool; +} diff --git a/compiler/rustc_query_system/src/query/job.rs b/compiler/rustc_query_system/src/query/job.rs new file mode 100644 index 000000000..6d2aff381 --- /dev/null +++ b/compiler/rustc_query_system/src/query/job.rs @@ -0,0 +1,612 @@ +use crate::query::plumbing::CycleError; +use crate::query::{QueryContext, QueryStackFrame}; +use rustc_hir::def::DefKind; + +use rustc_data_structures::fx::FxHashMap; +use rustc_errors::{ + struct_span_err, Diagnostic, DiagnosticBuilder, ErrorGuaranteed, Handler, Level, +}; +use rustc_session::Session; +use rustc_span::Span; + +use std::hash::Hash; +use std::num::NonZeroU64; + +#[cfg(parallel_compiler)] +use { + parking_lot::{Condvar, Mutex}, + rustc_data_structures::fx::FxHashSet, + rustc_data_structures::sync::Lock, + rustc_data_structures::sync::Lrc, + rustc_data_structures::{jobserver, OnDrop}, + rustc_rayon_core as rayon_core, + rustc_span::DUMMY_SP, + std::iter::{self, FromIterator}, + std::{mem, process}, +}; + +/// Represents a span and a query key. +#[derive(Clone, Debug)] +pub struct QueryInfo { + /// The span corresponding to the reason for which this query was required. + pub span: Span, + pub query: QueryStackFrame, +} + +pub type QueryMap = FxHashMap<QueryJobId, QueryJobInfo>; + +/// A value uniquely identifying an active query job. +#[derive(Copy, Clone, Eq, PartialEq, Hash)] +pub struct QueryJobId(pub NonZeroU64); + +impl QueryJobId { + fn query(self, map: &QueryMap) -> QueryStackFrame { + map.get(&self).unwrap().query.clone() + } + + #[cfg(parallel_compiler)] + fn span(self, map: &QueryMap) -> Span { + map.get(&self).unwrap().job.span + } + + #[cfg(parallel_compiler)] + fn parent(self, map: &QueryMap) -> Option<QueryJobId> { + map.get(&self).unwrap().job.parent + } + + #[cfg(parallel_compiler)] + fn latch<'a>(self, map: &'a QueryMap) -> Option<&'a QueryLatch> { + map.get(&self).unwrap().job.latch.as_ref() + } +} + +pub struct QueryJobInfo { + pub query: QueryStackFrame, + pub job: QueryJob, +} + +/// Represents an active query job. +#[derive(Clone)] +pub struct QueryJob { + pub id: QueryJobId, + + /// The span corresponding to the reason for which this query was required. + pub span: Span, + + /// The parent query job which created this job and is implicitly waiting on it. + pub parent: Option<QueryJobId>, + + /// The latch that is used to wait on this job. + #[cfg(parallel_compiler)] + latch: Option<QueryLatch>, +} + +impl QueryJob { + /// Creates a new query job. + #[inline] + pub fn new(id: QueryJobId, span: Span, parent: Option<QueryJobId>) -> Self { + QueryJob { + id, + span, + parent, + #[cfg(parallel_compiler)] + latch: None, + } + } + + #[cfg(parallel_compiler)] + pub(super) fn latch(&mut self) -> QueryLatch { + if self.latch.is_none() { + self.latch = Some(QueryLatch::new()); + } + self.latch.as_ref().unwrap().clone() + } + + /// Signals to waiters that the query is complete. + /// + /// This does nothing for single threaded rustc, + /// as there are no concurrent jobs which could be waiting on us + #[inline] + pub fn signal_complete(self) { + #[cfg(parallel_compiler)] + { + if let Some(latch) = self.latch { + latch.set(); + } + } + } +} + +#[cfg(not(parallel_compiler))] +impl QueryJobId { + #[cold] + #[inline(never)] + pub(super) fn find_cycle_in_stack( + &self, + query_map: QueryMap, + current_job: &Option<QueryJobId>, + span: Span, + ) -> CycleError { + // Find the waitee amongst `current_job` parents + let mut cycle = Vec::new(); + let mut current_job = Option::clone(current_job); + + while let Some(job) = current_job { + let info = query_map.get(&job).unwrap(); + cycle.push(QueryInfo { span: info.job.span, query: info.query.clone() }); + + if job == *self { + cycle.reverse(); + + // This is the end of the cycle + // The span entry we included was for the usage + // of the cycle itself, and not part of the cycle + // Replace it with the span which caused the cycle to form + cycle[0].span = span; + // Find out why the cycle itself was used + let usage = info + .job + .parent + .as_ref() + .map(|parent| (info.job.span, parent.query(&query_map))); + return CycleError { usage, cycle }; + } + + current_job = info.job.parent; + } + + panic!("did not find a cycle") + } +} + +#[cfg(parallel_compiler)] +struct QueryWaiter { + query: Option<QueryJobId>, + condvar: Condvar, + span: Span, + cycle: Lock<Option<CycleError>>, +} + +#[cfg(parallel_compiler)] +impl QueryWaiter { + fn notify(&self, registry: &rayon_core::Registry) { + rayon_core::mark_unblocked(registry); + self.condvar.notify_one(); + } +} + +#[cfg(parallel_compiler)] +struct QueryLatchInfo { + complete: bool, + waiters: Vec<Lrc<QueryWaiter>>, +} + +#[cfg(parallel_compiler)] +#[derive(Clone)] +pub(super) struct QueryLatch { + info: Lrc<Mutex<QueryLatchInfo>>, +} + +#[cfg(parallel_compiler)] +impl QueryLatch { + fn new() -> Self { + QueryLatch { + info: Lrc::new(Mutex::new(QueryLatchInfo { complete: false, waiters: Vec::new() })), + } + } + + /// Awaits for the query job to complete. + pub(super) fn wait_on(&self, query: Option<QueryJobId>, span: Span) -> Result<(), CycleError> { + let waiter = + Lrc::new(QueryWaiter { query, span, cycle: Lock::new(None), condvar: Condvar::new() }); + self.wait_on_inner(&waiter); + // FIXME: Get rid of this lock. We have ownership of the QueryWaiter + // although another thread may still have a Lrc reference so we cannot + // use Lrc::get_mut + let mut cycle = waiter.cycle.lock(); + match cycle.take() { + None => Ok(()), + Some(cycle) => Err(cycle), + } + } + + /// Awaits the caller on this latch by blocking the current thread. + fn wait_on_inner(&self, waiter: &Lrc<QueryWaiter>) { + let mut info = self.info.lock(); + if !info.complete { + // We push the waiter on to the `waiters` list. It can be accessed inside + // the `wait` call below, by 1) the `set` method or 2) by deadlock detection. + // Both of these will remove it from the `waiters` list before resuming + // this thread. + info.waiters.push(waiter.clone()); + + // If this detects a deadlock and the deadlock handler wants to resume this thread + // we have to be in the `wait` call. This is ensured by the deadlock handler + // getting the self.info lock. + rayon_core::mark_blocked(); + jobserver::release_thread(); + waiter.condvar.wait(&mut info); + // Release the lock before we potentially block in `acquire_thread` + mem::drop(info); + jobserver::acquire_thread(); + } + } + + /// Sets the latch and resumes all waiters on it + fn set(&self) { + let mut info = self.info.lock(); + debug_assert!(!info.complete); + info.complete = true; + let registry = rayon_core::Registry::current(); + for waiter in info.waiters.drain(..) { + waiter.notify(®istry); + } + } + + /// Removes a single waiter from the list of waiters. + /// This is used to break query cycles. + fn extract_waiter(&self, waiter: usize) -> Lrc<QueryWaiter> { + let mut info = self.info.lock(); + debug_assert!(!info.complete); + // Remove the waiter from the list of waiters + info.waiters.remove(waiter) + } +} + +/// A resumable waiter of a query. The usize is the index into waiters in the query's latch +#[cfg(parallel_compiler)] +type Waiter = (QueryJobId, usize); + +/// Visits all the non-resumable and resumable waiters of a query. +/// Only waiters in a query are visited. +/// `visit` is called for every waiter and is passed a query waiting on `query_ref` +/// and a span indicating the reason the query waited on `query_ref`. +/// If `visit` returns Some, this function returns. +/// For visits of non-resumable waiters it returns the return value of `visit`. +/// For visits of resumable waiters it returns Some(Some(Waiter)) which has the +/// required information to resume the waiter. +/// If all `visit` calls returns None, this function also returns None. +#[cfg(parallel_compiler)] +fn visit_waiters<F>(query_map: &QueryMap, query: QueryJobId, mut visit: F) -> Option<Option<Waiter>> +where + F: FnMut(Span, QueryJobId) -> Option<Option<Waiter>>, +{ + // Visit the parent query which is a non-resumable waiter since it's on the same stack + if let Some(parent) = query.parent(query_map) { + if let Some(cycle) = visit(query.span(query_map), parent) { + return Some(cycle); + } + } + + // Visit the explicit waiters which use condvars and are resumable + if let Some(latch) = query.latch(query_map) { + for (i, waiter) in latch.info.lock().waiters.iter().enumerate() { + if let Some(waiter_query) = waiter.query { + if visit(waiter.span, waiter_query).is_some() { + // Return a value which indicates that this waiter can be resumed + return Some(Some((query, i))); + } + } + } + } + + None +} + +/// Look for query cycles by doing a depth first search starting at `query`. +/// `span` is the reason for the `query` to execute. This is initially DUMMY_SP. +/// If a cycle is detected, this initial value is replaced with the span causing +/// the cycle. +#[cfg(parallel_compiler)] +fn cycle_check( + query_map: &QueryMap, + query: QueryJobId, + span: Span, + stack: &mut Vec<(Span, QueryJobId)>, + visited: &mut FxHashSet<QueryJobId>, +) -> Option<Option<Waiter>> { + if !visited.insert(query) { + return if let Some(p) = stack.iter().position(|q| q.1 == query) { + // We detected a query cycle, fix up the initial span and return Some + + // Remove previous stack entries + stack.drain(0..p); + // Replace the span for the first query with the cycle cause + stack[0].0 = span; + Some(None) + } else { + None + }; + } + + // Query marked as visited is added it to the stack + stack.push((span, query)); + + // Visit all the waiters + let r = visit_waiters(query_map, query, |span, successor| { + cycle_check(query_map, successor, span, stack, visited) + }); + + // Remove the entry in our stack if we didn't find a cycle + if r.is_none() { + stack.pop(); + } + + r +} + +/// Finds out if there's a path to the compiler root (aka. code which isn't in a query) +/// from `query` without going through any of the queries in `visited`. +/// This is achieved with a depth first search. +#[cfg(parallel_compiler)] +fn connected_to_root( + query_map: &QueryMap, + query: QueryJobId, + visited: &mut FxHashSet<QueryJobId>, +) -> bool { + // We already visited this or we're deliberately ignoring it + if !visited.insert(query) { + return false; + } + + // This query is connected to the root (it has no query parent), return true + if query.parent(query_map).is_none() { + return true; + } + + visit_waiters(query_map, query, |_, successor| { + connected_to_root(query_map, successor, visited).then_some(None) + }) + .is_some() +} + +// Deterministically pick an query from a list +#[cfg(parallel_compiler)] +fn pick_query<'a, T, F>(query_map: &QueryMap, queries: &'a [T], f: F) -> &'a T +where + F: Fn(&T) -> (Span, QueryJobId), +{ + // Deterministically pick an entry point + // FIXME: Sort this instead + queries + .iter() + .min_by_key(|v| { + let (span, query) = f(v); + let hash = query.query(query_map).hash; + // Prefer entry points which have valid spans for nicer error messages + // We add an integer to the tuple ensuring that entry points + // with valid spans are picked first + let span_cmp = if span == DUMMY_SP { 1 } else { 0 }; + (span_cmp, hash) + }) + .unwrap() +} + +/// Looks for query cycles starting from the last query in `jobs`. +/// If a cycle is found, all queries in the cycle is removed from `jobs` and +/// the function return true. +/// If a cycle was not found, the starting query is removed from `jobs` and +/// the function returns false. +#[cfg(parallel_compiler)] +fn remove_cycle( + query_map: &QueryMap, + jobs: &mut Vec<QueryJobId>, + wakelist: &mut Vec<Lrc<QueryWaiter>>, +) -> bool { + let mut visited = FxHashSet::default(); + let mut stack = Vec::new(); + // Look for a cycle starting with the last query in `jobs` + if let Some(waiter) = + cycle_check(query_map, jobs.pop().unwrap(), DUMMY_SP, &mut stack, &mut visited) + { + // The stack is a vector of pairs of spans and queries; reverse it so that + // the earlier entries require later entries + let (mut spans, queries): (Vec<_>, Vec<_>) = stack.into_iter().rev().unzip(); + + // Shift the spans so that queries are matched with the span for their waitee + spans.rotate_right(1); + + // Zip them back together + let mut stack: Vec<_> = iter::zip(spans, queries).collect(); + + // Remove the queries in our cycle from the list of jobs to look at + for r in &stack { + if let Some(pos) = jobs.iter().position(|j| j == &r.1) { + jobs.remove(pos); + } + } + + // Find the queries in the cycle which are + // connected to queries outside the cycle + let entry_points = stack + .iter() + .filter_map(|&(span, query)| { + if query.parent(query_map).is_none() { + // This query is connected to the root (it has no query parent) + Some((span, query, None)) + } else { + let mut waiters = Vec::new(); + // Find all the direct waiters who lead to the root + visit_waiters(query_map, query, |span, waiter| { + // Mark all the other queries in the cycle as already visited + let mut visited = FxHashSet::from_iter(stack.iter().map(|q| q.1)); + + if connected_to_root(query_map, waiter, &mut visited) { + waiters.push((span, waiter)); + } + + None + }); + if waiters.is_empty() { + None + } else { + // Deterministically pick one of the waiters to show to the user + let waiter = *pick_query(query_map, &waiters, |s| *s); + Some((span, query, Some(waiter))) + } + } + }) + .collect::<Vec<(Span, QueryJobId, Option<(Span, QueryJobId)>)>>(); + + // Deterministically pick an entry point + let (_, entry_point, usage) = pick_query(query_map, &entry_points, |e| (e.0, e.1)); + + // Shift the stack so that our entry point is first + let entry_point_pos = stack.iter().position(|(_, query)| query == entry_point); + if let Some(pos) = entry_point_pos { + stack.rotate_left(pos); + } + + let usage = usage.as_ref().map(|(span, query)| (*span, query.query(query_map))); + + // Create the cycle error + let error = CycleError { + usage, + cycle: stack + .iter() + .map(|&(s, ref q)| QueryInfo { span: s, query: q.query(query_map) }) + .collect(), + }; + + // We unwrap `waiter` here since there must always be one + // edge which is resumable / waited using a query latch + let (waitee_query, waiter_idx) = waiter.unwrap(); + + // Extract the waiter we want to resume + let waiter = waitee_query.latch(query_map).unwrap().extract_waiter(waiter_idx); + + // Set the cycle error so it will be picked up when resumed + *waiter.cycle.lock() = Some(error); + + // Put the waiter on the list of things to resume + wakelist.push(waiter); + + true + } else { + false + } +} + +/// Detects query cycles by using depth first search over all active query jobs. +/// If a query cycle is found it will break the cycle by finding an edge which +/// uses a query latch and then resuming that waiter. +/// There may be multiple cycles involved in a deadlock, so this searches +/// all active queries for cycles before finally resuming all the waiters at once. +#[cfg(parallel_compiler)] +pub fn deadlock(query_map: QueryMap, registry: &rayon_core::Registry) { + let on_panic = OnDrop(|| { + eprintln!("deadlock handler panicked, aborting process"); + process::abort(); + }); + + let mut wakelist = Vec::new(); + let mut jobs: Vec<QueryJobId> = query_map.keys().cloned().collect(); + + let mut found_cycle = false; + + while jobs.len() > 0 { + if remove_cycle(&query_map, &mut jobs, &mut wakelist) { + found_cycle = true; + } + } + + // Check that a cycle was found. It is possible for a deadlock to occur without + // a query cycle if a query which can be waited on uses Rayon to do multithreading + // internally. Such a query (X) may be executing on 2 threads (A and B) and A may + // wait using Rayon on B. Rayon may then switch to executing another query (Y) + // which in turn will wait on X causing a deadlock. We have a false dependency from + // X to Y due to Rayon waiting and a true dependency from Y to X. The algorithm here + // only considers the true dependency and won't detect a cycle. + assert!(found_cycle); + + // FIXME: Ensure this won't cause a deadlock before we return + for waiter in wakelist.into_iter() { + waiter.notify(registry); + } + + on_panic.disable(); +} + +#[inline(never)] +#[cold] +pub(crate) fn report_cycle<'a>( + sess: &'a Session, + CycleError { usage, cycle: stack }: CycleError, +) -> DiagnosticBuilder<'a, ErrorGuaranteed> { + assert!(!stack.is_empty()); + + let span = stack[0].query.default_span(stack[1 % stack.len()].span); + let mut err = + struct_span_err!(sess, span, E0391, "cycle detected when {}", stack[0].query.description); + + for i in 1..stack.len() { + let query = &stack[i].query; + let span = query.default_span(stack[(i + 1) % stack.len()].span); + err.span_note(span, &format!("...which requires {}...", query.description)); + } + + if stack.len() == 1 { + err.note(&format!("...which immediately requires {} again", stack[0].query.description)); + } else { + err.note(&format!( + "...which again requires {}, completing the cycle", + stack[0].query.description + )); + } + + if stack.iter().all(|entry| { + entry + .query + .def_kind + .map_or(false, |def_kind| matches!(def_kind, DefKind::TyAlias | DefKind::TraitAlias)) + }) { + if stack.iter().all(|entry| { + entry.query.def_kind.map_or(false, |def_kind| matches!(def_kind, DefKind::TyAlias)) + }) { + err.note("type aliases cannot be recursive"); + err.help("consider using a struct, enum, or union instead to break the cycle"); + err.help("see <https://doc.rust-lang.org/reference/types.html#recursive-types> for more information"); + } else { + err.note("trait aliases cannot be recursive"); + } + } + + if let Some((span, query)) = usage { + err.span_note(query.default_span(span), &format!("cycle used when {}", query.description)); + } + + err +} + +pub fn print_query_stack<CTX: QueryContext>( + tcx: CTX, + mut current_query: Option<QueryJobId>, + handler: &Handler, + num_frames: Option<usize>, +) -> usize { + // Be careful relying on global state here: this code is called from + // a panic hook, which means that the global `Handler` may be in a weird + // state if it was responsible for triggering the panic. + let mut i = 0; + let query_map = tcx.try_collect_active_jobs(); + + while let Some(query) = current_query { + if Some(i) == num_frames { + break; + } + let Some(query_info) = query_map.as_ref().and_then(|map| map.get(&query)) else { + break; + }; + let mut diag = Diagnostic::new( + Level::FailureNote, + &format!("#{} [{}] {}", i, query_info.query.name, query_info.query.description), + ); + diag.span = query_info.job.span.into(); + handler.force_print_diagnostic(diag); + + current_query = query_info.job.parent; + i += 1; + } + + i +} diff --git a/compiler/rustc_query_system/src/query/mod.rs b/compiler/rustc_query_system/src/query/mod.rs new file mode 100644 index 000000000..fb2258434 --- /dev/null +++ b/compiler/rustc_query_system/src/query/mod.rs @@ -0,0 +1,125 @@ +mod plumbing; +pub use self::plumbing::*; + +mod job; +#[cfg(parallel_compiler)] +pub use self::job::deadlock; +pub use self::job::{print_query_stack, QueryInfo, QueryJob, QueryJobId, QueryJobInfo, QueryMap}; + +mod caches; +pub use self::caches::{ + ArenaCacheSelector, CacheSelector, DefaultCacheSelector, QueryCache, QueryStorage, +}; + +mod config; +pub use self::config::{QueryConfig, QueryDescription, QueryVTable}; + +use crate::dep_graph::{DepNodeIndex, HasDepContext, SerializedDepNodeIndex}; + +use rustc_data_structures::sync::Lock; +use rustc_data_structures::thin_vec::ThinVec; +use rustc_errors::Diagnostic; +use rustc_hir::def::DefKind; +use rustc_span::Span; + +/// Description of a frame in the query stack. +/// +/// This is mostly used in case of cycles for error reporting. +#[derive(Clone, Debug)] +pub struct QueryStackFrame { + pub name: &'static str, + pub description: String, + span: Option<Span>, + def_kind: Option<DefKind>, + /// This hash is used to deterministically pick + /// a query to remove cycles in the parallel compiler. + #[cfg(parallel_compiler)] + hash: u64, +} + +impl QueryStackFrame { + #[inline] + pub fn new( + name: &'static str, + description: String, + span: Option<Span>, + def_kind: Option<DefKind>, + _hash: impl FnOnce() -> u64, + ) -> Self { + Self { + name, + description, + span, + def_kind, + #[cfg(parallel_compiler)] + hash: _hash(), + } + } + + // FIXME(eddyb) Get more valid `Span`s on queries. + #[inline] + pub fn default_span(&self, span: Span) -> Span { + if !span.is_dummy() { + return span; + } + self.span.unwrap_or(span) + } +} + +/// Tracks 'side effects' for a particular query. +/// This struct is saved to disk along with the query result, +/// and loaded from disk if we mark the query as green. +/// This allows us to 'replay' changes to global state +/// that would otherwise only occur if we actually +/// executed the query method. +#[derive(Debug, Clone, Default, Encodable, Decodable)] +pub struct QuerySideEffects { + /// Stores any diagnostics emitted during query execution. + /// These diagnostics will be re-emitted if we mark + /// the query as green. + pub(super) diagnostics: ThinVec<Diagnostic>, +} + +impl QuerySideEffects { + #[inline] + pub fn is_empty(&self) -> bool { + let QuerySideEffects { diagnostics } = self; + diagnostics.is_empty() + } + pub fn append(&mut self, other: QuerySideEffects) { + let QuerySideEffects { diagnostics } = self; + diagnostics.extend(other.diagnostics); + } +} + +pub trait QueryContext: HasDepContext { + fn next_job_id(&self) -> QueryJobId; + + /// Get the query information from the TLS context. + fn current_query_job(&self) -> Option<QueryJobId>; + + fn try_collect_active_jobs(&self) -> Option<QueryMap>; + + /// Load side effects associated to the node in the previous session. + fn load_side_effects(&self, prev_dep_node_index: SerializedDepNodeIndex) -> QuerySideEffects; + + /// Register diagnostics for the given node, for use in next session. + fn store_side_effects(&self, dep_node_index: DepNodeIndex, side_effects: QuerySideEffects); + + /// Register diagnostics for the given node, for use in next session. + fn store_side_effects_for_anon_node( + &self, + dep_node_index: DepNodeIndex, + side_effects: QuerySideEffects, + ); + + /// Executes a job by changing the `ImplicitCtxt` to point to the + /// new query job while it executes. It returns the diagnostics + /// captured during execution and the actual result. + fn start_query<R>( + &self, + token: QueryJobId, + diagnostics: Option<&Lock<ThinVec<Diagnostic>>>, + compute: impl FnOnce() -> R, + ) -> R; +} diff --git a/compiler/rustc_query_system/src/query/plumbing.rs b/compiler/rustc_query_system/src/query/plumbing.rs new file mode 100644 index 000000000..5e8ea07d0 --- /dev/null +++ b/compiler/rustc_query_system/src/query/plumbing.rs @@ -0,0 +1,742 @@ +//! The implementation of the query system itself. This defines the macros that +//! generate the actual methods on tcx which find and execute the provider, +//! manage the caches, and so forth. + +use crate::dep_graph::{DepContext, DepNode, DepNodeIndex, DepNodeParams}; +use crate::query::caches::QueryCache; +use crate::query::config::{QueryDescription, QueryVTable}; +use crate::query::job::{report_cycle, QueryInfo, QueryJob, QueryJobId, QueryJobInfo}; +use crate::query::{QueryContext, QueryMap, QuerySideEffects, QueryStackFrame}; +use rustc_data_structures::fingerprint::Fingerprint; +use rustc_data_structures::fx::FxHashMap; +#[cfg(parallel_compiler)] +use rustc_data_structures::profiling::TimingGuard; +#[cfg(parallel_compiler)] +use rustc_data_structures::sharded::Sharded; +use rustc_data_structures::sync::Lock; +use rustc_data_structures::thin_vec::ThinVec; +use rustc_errors::{DiagnosticBuilder, ErrorGuaranteed, FatalError}; +use rustc_session::Session; +use rustc_span::{Span, DUMMY_SP}; +use std::cell::Cell; +use std::collections::hash_map::Entry; +use std::fmt::Debug; +use std::hash::Hash; +use std::mem; +use std::ptr; + +pub struct QueryState<K> { + #[cfg(parallel_compiler)] + active: Sharded<FxHashMap<K, QueryResult>>, + #[cfg(not(parallel_compiler))] + active: Lock<FxHashMap<K, QueryResult>>, +} + +/// Indicates the state of a query for a given key in a query map. +enum QueryResult { + /// An already executing query. The query job can be used to await for its completion. + Started(QueryJob), + + /// The query panicked. Queries trying to wait on this will raise a fatal error which will + /// silently panic. + Poisoned, +} + +impl<K> QueryState<K> +where + K: Eq + Hash + Clone + Debug, +{ + pub fn all_inactive(&self) -> bool { + #[cfg(parallel_compiler)] + { + let shards = self.active.lock_shards(); + shards.iter().all(|shard| shard.is_empty()) + } + #[cfg(not(parallel_compiler))] + { + self.active.lock().is_empty() + } + } + + pub fn try_collect_active_jobs<CTX: Copy>( + &self, + tcx: CTX, + make_query: fn(CTX, K) -> QueryStackFrame, + jobs: &mut QueryMap, + ) -> Option<()> { + #[cfg(parallel_compiler)] + { + // We use try_lock_shards here since we are called from the + // deadlock handler, and this shouldn't be locked. + let shards = self.active.try_lock_shards()?; + for shard in shards.iter() { + for (k, v) in shard.iter() { + if let QueryResult::Started(ref job) = *v { + let query = make_query(tcx, k.clone()); + jobs.insert(job.id, QueryJobInfo { query, job: job.clone() }); + } + } + } + } + #[cfg(not(parallel_compiler))] + { + // We use try_lock here since we are called from the + // deadlock handler, and this shouldn't be locked. + // (FIXME: Is this relevant for non-parallel compilers? It doesn't + // really hurt much.) + for (k, v) in self.active.try_lock()?.iter() { + if let QueryResult::Started(ref job) = *v { + let query = make_query(tcx, k.clone()); + jobs.insert(job.id, QueryJobInfo { query, job: job.clone() }); + } + } + } + + Some(()) + } +} + +impl<K> Default for QueryState<K> { + fn default() -> QueryState<K> { + QueryState { active: Default::default() } + } +} + +/// A type representing the responsibility to execute the job in the `job` field. +/// This will poison the relevant query if dropped. +struct JobOwner<'tcx, K> +where + K: Eq + Hash + Clone, +{ + state: &'tcx QueryState<K>, + key: K, + id: QueryJobId, +} + +#[cold] +#[inline(never)] +fn mk_cycle<CTX, V, R>( + tcx: CTX, + error: CycleError, + handle_cycle_error: fn(CTX, DiagnosticBuilder<'_, ErrorGuaranteed>) -> V, + cache: &dyn crate::query::QueryStorage<Value = V, Stored = R>, +) -> R +where + CTX: QueryContext, + V: std::fmt::Debug, + R: Clone, +{ + let error = report_cycle(tcx.dep_context().sess(), error); + let value = handle_cycle_error(tcx, error); + cache.store_nocache(value) +} + +impl<'tcx, K> JobOwner<'tcx, K> +where + K: Eq + Hash + Clone, +{ + /// Either gets a `JobOwner` corresponding the query, allowing us to + /// start executing the query, or returns with the result of the query. + /// This function assumes that `try_get_cached` is already called and returned `lookup`. + /// If the query is executing elsewhere, this will wait for it and return the result. + /// If the query panicked, this will silently panic. + /// + /// This function is inlined because that results in a noticeable speed-up + /// for some compile-time benchmarks. + #[inline(always)] + fn try_start<'b, CTX>( + tcx: &'b CTX, + state: &'b QueryState<K>, + span: Span, + key: K, + ) -> TryGetJob<'b, K> + where + CTX: QueryContext, + { + #[cfg(parallel_compiler)] + let mut state_lock = state.active.get_shard_by_value(&key).lock(); + #[cfg(not(parallel_compiler))] + let mut state_lock = state.active.lock(); + let lock = &mut *state_lock; + + match lock.entry(key) { + Entry::Vacant(entry) => { + let id = tcx.next_job_id(); + let job = tcx.current_query_job(); + let job = QueryJob::new(id, span, job); + + let key = entry.key().clone(); + entry.insert(QueryResult::Started(job)); + + let owner = JobOwner { state, id, key }; + return TryGetJob::NotYetStarted(owner); + } + Entry::Occupied(mut entry) => { + match entry.get_mut() { + #[cfg(not(parallel_compiler))] + QueryResult::Started(job) => { + let id = job.id; + drop(state_lock); + + // If we are single-threaded we know that we have cycle error, + // so we just return the error. + return TryGetJob::Cycle(id.find_cycle_in_stack( + tcx.try_collect_active_jobs().unwrap(), + &tcx.current_query_job(), + span, + )); + } + #[cfg(parallel_compiler)] + QueryResult::Started(job) => { + // For parallel queries, we'll block and wait until the query running + // in another thread has completed. Record how long we wait in the + // self-profiler. + let query_blocked_prof_timer = tcx.dep_context().profiler().query_blocked(); + + // Get the latch out + let latch = job.latch(); + + drop(state_lock); + + // With parallel queries we might just have to wait on some other + // thread. + let result = latch.wait_on(tcx.current_query_job(), span); + + match result { + Ok(()) => TryGetJob::JobCompleted(query_blocked_prof_timer), + Err(cycle) => TryGetJob::Cycle(cycle), + } + } + QueryResult::Poisoned => FatalError.raise(), + } + } + } + } + + /// Completes the query by updating the query cache with the `result`, + /// signals the waiter and forgets the JobOwner, so it won't poison the query + fn complete<C>(self, cache: &C, result: C::Value, dep_node_index: DepNodeIndex) -> C::Stored + where + C: QueryCache<Key = K>, + { + // We can move out of `self` here because we `mem::forget` it below + let key = unsafe { ptr::read(&self.key) }; + let state = self.state; + + // Forget ourself so our destructor won't poison the query + mem::forget(self); + + let (job, result) = { + let job = { + #[cfg(parallel_compiler)] + let mut lock = state.active.get_shard_by_value(&key).lock(); + #[cfg(not(parallel_compiler))] + let mut lock = state.active.lock(); + match lock.remove(&key).unwrap() { + QueryResult::Started(job) => job, + QueryResult::Poisoned => panic!(), + } + }; + let result = cache.complete(key, result, dep_node_index); + (job, result) + }; + + job.signal_complete(); + result + } +} + +impl<'tcx, K> Drop for JobOwner<'tcx, K> +where + K: Eq + Hash + Clone, +{ + #[inline(never)] + #[cold] + fn drop(&mut self) { + // Poison the query so jobs waiting on it panic. + let state = self.state; + let job = { + #[cfg(parallel_compiler)] + let mut shard = state.active.get_shard_by_value(&self.key).lock(); + #[cfg(not(parallel_compiler))] + let mut shard = state.active.lock(); + let job = match shard.remove(&self.key).unwrap() { + QueryResult::Started(job) => job, + QueryResult::Poisoned => panic!(), + }; + shard.insert(self.key.clone(), QueryResult::Poisoned); + job + }; + // Also signal the completion of the job, so waiters + // will continue execution. + job.signal_complete(); + } +} + +#[derive(Clone)] +pub(crate) struct CycleError { + /// The query and related span that uses the cycle. + pub usage: Option<(Span, QueryStackFrame)>, + pub cycle: Vec<QueryInfo>, +} + +/// The result of `try_start`. +enum TryGetJob<'tcx, K> +where + K: Eq + Hash + Clone, +{ + /// The query is not yet started. Contains a guard to the cache eventually used to start it. + NotYetStarted(JobOwner<'tcx, K>), + + /// The query was already completed. + /// Returns the result of the query and its dep-node index + /// if it succeeded or a cycle error if it failed. + #[cfg(parallel_compiler)] + JobCompleted(TimingGuard<'tcx>), + + /// Trying to execute the query resulted in a cycle. + Cycle(CycleError), +} + +/// Checks if the query is already computed and in the cache. +/// It returns the shard index and a lock guard to the shard, +/// which will be used if the query is not in the cache and we need +/// to compute it. +#[inline] +pub fn try_get_cached<'a, CTX, C, R, OnHit>( + tcx: CTX, + cache: &'a C, + key: &C::Key, + // `on_hit` can be called while holding a lock to the query cache + on_hit: OnHit, +) -> Result<R, ()> +where + C: QueryCache, + CTX: DepContext, + OnHit: FnOnce(&C::Stored) -> R, +{ + cache.lookup(&key, |value, index| { + if std::intrinsics::unlikely(tcx.profiler().enabled()) { + tcx.profiler().query_cache_hit(index.into()); + } + tcx.dep_graph().read_index(index); + on_hit(value) + }) +} + +fn try_execute_query<CTX, C>( + tcx: CTX, + state: &QueryState<C::Key>, + cache: &C, + span: Span, + key: C::Key, + dep_node: Option<DepNode<CTX::DepKind>>, + query: &QueryVTable<CTX, C::Key, C::Value>, +) -> (C::Stored, Option<DepNodeIndex>) +where + C: QueryCache, + C::Key: Clone + DepNodeParams<CTX::DepContext>, + CTX: QueryContext, +{ + match JobOwner::<'_, C::Key>::try_start(&tcx, state, span, key.clone()) { + TryGetJob::NotYetStarted(job) => { + let (result, dep_node_index) = execute_job(tcx, key, dep_node, query, job.id); + let result = job.complete(cache, result, dep_node_index); + (result, Some(dep_node_index)) + } + TryGetJob::Cycle(error) => { + let result = mk_cycle(tcx, error, query.handle_cycle_error, cache); + (result, None) + } + #[cfg(parallel_compiler)] + TryGetJob::JobCompleted(query_blocked_prof_timer) => { + let (v, index) = cache + .lookup(&key, |value, index| (value.clone(), index)) + .unwrap_or_else(|_| panic!("value must be in cache after waiting")); + + if std::intrinsics::unlikely(tcx.dep_context().profiler().enabled()) { + tcx.dep_context().profiler().query_cache_hit(index.into()); + } + query_blocked_prof_timer.finish_with_query_invocation_id(index.into()); + + (v, Some(index)) + } + } +} + +fn execute_job<CTX, K, V>( + tcx: CTX, + key: K, + mut dep_node_opt: Option<DepNode<CTX::DepKind>>, + query: &QueryVTable<CTX, K, V>, + job_id: QueryJobId, +) -> (V, DepNodeIndex) +where + K: Clone + DepNodeParams<CTX::DepContext>, + V: Debug, + CTX: QueryContext, +{ + let dep_graph = tcx.dep_context().dep_graph(); + + // Fast path for when incr. comp. is off. + if !dep_graph.is_fully_enabled() { + let prof_timer = tcx.dep_context().profiler().query_provider(); + let result = tcx.start_query(job_id, None, || query.compute(*tcx.dep_context(), key)); + let dep_node_index = dep_graph.next_virtual_depnode_index(); + prof_timer.finish_with_query_invocation_id(dep_node_index.into()); + return (result, dep_node_index); + } + + if !query.anon && !query.eval_always { + // `to_dep_node` is expensive for some `DepKind`s. + let dep_node = + dep_node_opt.get_or_insert_with(|| query.to_dep_node(*tcx.dep_context(), &key)); + + // The diagnostics for this query will be promoted to the current session during + // `try_mark_green()`, so we can ignore them here. + if let Some(ret) = tcx.start_query(job_id, None, || { + try_load_from_disk_and_cache_in_memory(tcx, &key, &dep_node, query) + }) { + return ret; + } + } + + let prof_timer = tcx.dep_context().profiler().query_provider(); + let diagnostics = Lock::new(ThinVec::new()); + + let (result, dep_node_index) = tcx.start_query(job_id, Some(&diagnostics), || { + if query.anon { + return dep_graph.with_anon_task(*tcx.dep_context(), query.dep_kind, || { + query.compute(*tcx.dep_context(), key) + }); + } + + // `to_dep_node` is expensive for some `DepKind`s. + let dep_node = dep_node_opt.unwrap_or_else(|| query.to_dep_node(*tcx.dep_context(), &key)); + + dep_graph.with_task(dep_node, *tcx.dep_context(), key, query.compute, query.hash_result) + }); + + prof_timer.finish_with_query_invocation_id(dep_node_index.into()); + + let diagnostics = diagnostics.into_inner(); + let side_effects = QuerySideEffects { diagnostics }; + + if std::intrinsics::unlikely(!side_effects.is_empty()) { + if query.anon { + tcx.store_side_effects_for_anon_node(dep_node_index, side_effects); + } else { + tcx.store_side_effects(dep_node_index, side_effects); + } + } + + (result, dep_node_index) +} + +fn try_load_from_disk_and_cache_in_memory<CTX, K, V>( + tcx: CTX, + key: &K, + dep_node: &DepNode<CTX::DepKind>, + query: &QueryVTable<CTX, K, V>, +) -> Option<(V, DepNodeIndex)> +where + K: Clone, + CTX: QueryContext, + V: Debug, +{ + // Note this function can be called concurrently from the same query + // We must ensure that this is handled correctly. + + let dep_graph = tcx.dep_context().dep_graph(); + let (prev_dep_node_index, dep_node_index) = dep_graph.try_mark_green(tcx, &dep_node)?; + + debug_assert!(dep_graph.is_green(dep_node)); + + // First we try to load the result from the on-disk cache. + // Some things are never cached on disk. + if query.cache_on_disk { + let prof_timer = tcx.dep_context().profiler().incr_cache_loading(); + + // The call to `with_query_deserialization` enforces that no new `DepNodes` + // are created during deserialization. See the docs of that method for more + // details. + let result = dep_graph + .with_query_deserialization(|| query.try_load_from_disk(tcx, prev_dep_node_index)); + + prof_timer.finish_with_query_invocation_id(dep_node_index.into()); + + if let Some(result) = result { + if std::intrinsics::unlikely( + tcx.dep_context().sess().opts.unstable_opts.query_dep_graph, + ) { + dep_graph.mark_debug_loaded_from_disk(*dep_node) + } + + let prev_fingerprint = tcx + .dep_context() + .dep_graph() + .prev_fingerprint_of(dep_node) + .unwrap_or(Fingerprint::ZERO); + // If `-Zincremental-verify-ich` is specified, re-hash results from + // the cache and make sure that they have the expected fingerprint. + // + // If not, we still seek to verify a subset of fingerprints loaded + // from disk. Re-hashing results is fairly expensive, so we can't + // currently afford to verify every hash. This subset should still + // give us some coverage of potential bugs though. + let try_verify = prev_fingerprint.as_value().1 % 32 == 0; + if std::intrinsics::unlikely( + try_verify || tcx.dep_context().sess().opts.unstable_opts.incremental_verify_ich, + ) { + incremental_verify_ich(*tcx.dep_context(), &result, dep_node, query); + } + + return Some((result, dep_node_index)); + } + + // We always expect to find a cached result for things that + // can be forced from `DepNode`. + debug_assert!( + !tcx.dep_context().fingerprint_style(dep_node.kind).reconstructible(), + "missing on-disk cache entry for {:?}", + dep_node + ); + } + + // We could not load a result from the on-disk cache, so + // recompute. + let prof_timer = tcx.dep_context().profiler().query_provider(); + + // The dep-graph for this computation is already in-place. + let result = dep_graph.with_ignore(|| query.compute(*tcx.dep_context(), key.clone())); + + prof_timer.finish_with_query_invocation_id(dep_node_index.into()); + + // Verify that re-running the query produced a result with the expected hash + // This catches bugs in query implementations, turning them into ICEs. + // For example, a query might sort its result by `DefId` - since `DefId`s are + // not stable across compilation sessions, the result could get up getting sorted + // in a different order when the query is re-run, even though all of the inputs + // (e.g. `DefPathHash` values) were green. + // + // See issue #82920 for an example of a miscompilation that would get turned into + // an ICE by this check + incremental_verify_ich(*tcx.dep_context(), &result, dep_node, query); + + Some((result, dep_node_index)) +} + +fn incremental_verify_ich<CTX, K, V: Debug>( + tcx: CTX::DepContext, + result: &V, + dep_node: &DepNode<CTX::DepKind>, + query: &QueryVTable<CTX, K, V>, +) where + CTX: QueryContext, +{ + assert!( + tcx.dep_graph().is_green(dep_node), + "fingerprint for green query instance not loaded from cache: {:?}", + dep_node, + ); + + debug!("BEGIN verify_ich({:?})", dep_node); + let new_hash = query.hash_result.map_or(Fingerprint::ZERO, |f| { + tcx.with_stable_hashing_context(|mut hcx| f(&mut hcx, result)) + }); + let old_hash = tcx.dep_graph().prev_fingerprint_of(dep_node); + debug!("END verify_ich({:?})", dep_node); + + if Some(new_hash) != old_hash { + incremental_verify_ich_cold(tcx.sess(), DebugArg::from(&dep_node), DebugArg::from(&result)); + } +} + +// This DebugArg business is largely a mirror of std::fmt::ArgumentV1, which is +// currently not exposed publicly. +// +// The PR which added this attempted to use `&dyn Debug` instead, but that +// showed statistically significant worse compiler performance. It's not +// actually clear what the cause there was -- the code should be cold. If this +// can be replaced with `&dyn Debug` with on perf impact, then it probably +// should be. +extern "C" { + type Opaque; +} + +struct DebugArg<'a> { + value: &'a Opaque, + fmt: fn(&Opaque, &mut std::fmt::Formatter<'_>) -> std::fmt::Result, +} + +impl<'a, T> From<&'a T> for DebugArg<'a> +where + T: std::fmt::Debug, +{ + fn from(value: &'a T) -> DebugArg<'a> { + DebugArg { + value: unsafe { std::mem::transmute(value) }, + fmt: unsafe { + std::mem::transmute(<T as std::fmt::Debug>::fmt as fn(_, _) -> std::fmt::Result) + }, + } + } +} + +impl std::fmt::Debug for DebugArg<'_> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + (self.fmt)(self.value, f) + } +} + +// Note that this is marked #[cold] and intentionally takes the equivalent of +// `dyn Debug` for its arguments, as we want to avoid generating a bunch of +// different implementations for LLVM to chew on (and filling up the final +// binary, too). +#[cold] +fn incremental_verify_ich_cold(sess: &Session, dep_node: DebugArg<'_>, result: DebugArg<'_>) { + let run_cmd = if let Some(crate_name) = &sess.opts.crate_name { + format!("`cargo clean -p {}` or `cargo clean`", crate_name) + } else { + "`cargo clean`".to_string() + }; + + // When we emit an error message and panic, we try to debug-print the `DepNode` + // and query result. Unfortunately, this can cause us to run additional queries, + // which may result in another fingerprint mismatch while we're in the middle + // of processing this one. To avoid a double-panic (which kills the process + // before we can print out the query static), we print out a terse + // but 'safe' message if we detect a re-entrant call to this method. + thread_local! { + static INSIDE_VERIFY_PANIC: Cell<bool> = const { Cell::new(false) }; + }; + + let old_in_panic = INSIDE_VERIFY_PANIC.with(|in_panic| in_panic.replace(true)); + + if old_in_panic { + sess.struct_err( + "internal compiler error: re-entrant incremental verify failure, suppressing message", + ) + .emit(); + } else { + sess.struct_err(&format!("internal compiler error: encountered incremental compilation error with {:?}", dep_node)) + .help(&format!("This is a known issue with the compiler. Run {} to allow your project to compile", run_cmd)) + .note("Please follow the instructions below to create a bug report with the provided information") + .note("See <https://github.com/rust-lang/rust/issues/84970> for more information") + .emit(); + panic!("Found unstable fingerprints for {:?}: {:?}", dep_node, result); + } + + INSIDE_VERIFY_PANIC.with(|in_panic| in_panic.set(old_in_panic)); +} + +/// Ensure that either this query has all green inputs or been executed. +/// Executing `query::ensure(D)` is considered a read of the dep-node `D`. +/// Returns true if the query should still run. +/// +/// This function is particularly useful when executing passes for their +/// side-effects -- e.g., in order to report errors for erroneous programs. +/// +/// Note: The optimization is only available during incr. comp. +#[inline(never)] +fn ensure_must_run<CTX, K, V>( + tcx: CTX, + key: &K, + query: &QueryVTable<CTX, K, V>, +) -> (bool, Option<DepNode<CTX::DepKind>>) +where + K: crate::dep_graph::DepNodeParams<CTX::DepContext>, + CTX: QueryContext, +{ + if query.eval_always { + return (true, None); + } + + // Ensuring an anonymous query makes no sense + assert!(!query.anon); + + let dep_node = query.to_dep_node(*tcx.dep_context(), key); + + let dep_graph = tcx.dep_context().dep_graph(); + match dep_graph.try_mark_green(tcx, &dep_node) { + None => { + // A None return from `try_mark_green` means that this is either + // a new dep node or that the dep node has already been marked red. + // Either way, we can't call `dep_graph.read()` as we don't have the + // DepNodeIndex. We must invoke the query itself. The performance cost + // this introduces should be negligible as we'll immediately hit the + // in-memory cache, or another query down the line will. + (true, Some(dep_node)) + } + Some((_, dep_node_index)) => { + dep_graph.read_index(dep_node_index); + tcx.dep_context().profiler().query_cache_hit(dep_node_index.into()); + (false, None) + } + } +} + +#[derive(Debug)] +pub enum QueryMode { + Get, + Ensure, +} + +pub fn get_query<Q, CTX>(tcx: CTX, span: Span, key: Q::Key, mode: QueryMode) -> Option<Q::Stored> +where + Q: QueryDescription<CTX>, + Q::Key: DepNodeParams<CTX::DepContext>, + CTX: QueryContext, +{ + let query = Q::make_vtable(tcx, &key); + let dep_node = if let QueryMode::Ensure = mode { + let (must_run, dep_node) = ensure_must_run(tcx, &key, &query); + if !must_run { + return None; + } + dep_node + } else { + None + }; + + let (result, dep_node_index) = try_execute_query( + tcx, + Q::query_state(tcx), + Q::query_cache(tcx), + span, + key, + dep_node, + &query, + ); + if let Some(dep_node_index) = dep_node_index { + tcx.dep_context().dep_graph().read_index(dep_node_index) + } + Some(result) +} + +pub fn force_query<Q, CTX>(tcx: CTX, key: Q::Key, dep_node: DepNode<CTX::DepKind>) +where + Q: QueryDescription<CTX>, + Q::Key: DepNodeParams<CTX::DepContext>, + CTX: QueryContext, +{ + // We may be concurrently trying both execute and force a query. + // Ensure that only one of them runs the query. + let cache = Q::query_cache(tcx); + let cached = cache.lookup(&key, |_, index| { + if std::intrinsics::unlikely(tcx.dep_context().profiler().enabled()) { + tcx.dep_context().profiler().query_cache_hit(index.into()); + } + }); + + match cached { + Ok(()) => return, + Err(()) => {} + } + + let query = Q::make_vtable(tcx, &key); + let state = Q::query_state(tcx); + debug_assert!(!query.anon); + + try_execute_query(tcx, state, cache, DUMMY_SP, key, Some(dep_node), &query); +} |