1 //! The implementation of the query system itself. This defines the macros that
2 //! generate the actual methods on tcx which find and execute the provider,
3 //! manage the caches, and so forth.
5 use crate::dep_graph::{DepContext, DepKind, DepNode, DepNodeIndex};
6 use crate::ich::StableHashingContext;
7 use crate::query::caches::QueryCache;
8 use crate::query::job::{report_cycle, QueryInfo, QueryJob, QueryJobId, QueryJobInfo};
9 use crate::query::{QueryContext, QueryMap, QuerySideEffects, QueryStackFrame};
10 use crate::values::Value;
11 use crate::HandleCycleError;
12 use rustc_data_structures::fingerprint::Fingerprint;
13 use rustc_data_structures::fx::FxHashMap;
14 #[cfg(parallel_compiler)]
15 use rustc_data_structures::profiling::TimingGuard;
16 #[cfg(parallel_compiler)]
17 use rustc_data_structures::sharded::Sharded;
18 use rustc_data_structures::sync::Lock;
19 use rustc_errors::{DiagnosticBuilder, ErrorGuaranteed, FatalError};
20 use rustc_session::Session;
21 use rustc_span::{Span, DUMMY_SP};
22 use std::borrow::Borrow;
24 use std::collections::hash_map::Entry;
29 use thin_vec::ThinVec;
31 use super::QueryConfig;
33 pub struct QueryState<K, D: DepKind> {
34 #[cfg(parallel_compiler)]
35 active: Sharded<FxHashMap<K, QueryResult<D>>>,
36 #[cfg(not(parallel_compiler))]
37 active: Lock<FxHashMap<K, QueryResult<D>>>,
40 /// Indicates the state of a query for a given key in a query map.
41 enum QueryResult<D: DepKind> {
42 /// An already executing query. The query job can be used to await for its completion.
45 /// The query panicked. Queries trying to wait on this will raise a fatal error which will
50 impl<K, D> QueryState<K, D>
52 K: Eq + Hash + Clone + Debug,
55 pub fn all_inactive(&self) -> bool {
56 #[cfg(parallel_compiler)]
58 let shards = self.active.lock_shards();
59 shards.iter().all(|shard| shard.is_empty())
61 #[cfg(not(parallel_compiler))]
63 self.active.lock().is_empty()
67 pub fn try_collect_active_jobs<Qcx: Copy>(
70 make_query: fn(Qcx, K) -> QueryStackFrame<D>,
71 jobs: &mut QueryMap<D>,
73 #[cfg(parallel_compiler)]
75 // We use try_lock_shards here since we are called from the
76 // deadlock handler, and this shouldn't be locked.
77 let shards = self.active.try_lock_shards()?;
78 for shard in shards.iter() {
79 for (k, v) in shard.iter() {
80 if let QueryResult::Started(ref job) = *v {
81 let query = make_query(qcx, k.clone());
82 jobs.insert(job.id, QueryJobInfo { query, job: job.clone() });
87 #[cfg(not(parallel_compiler))]
89 // We use try_lock here since we are called from the
90 // deadlock handler, and this shouldn't be locked.
91 // (FIXME: Is this relevant for non-parallel compilers? It doesn't
93 for (k, v) in self.active.try_lock()?.iter() {
94 if let QueryResult::Started(ref job) = *v {
95 let query = make_query(qcx, k.clone());
96 jobs.insert(job.id, QueryJobInfo { query, job: job.clone() });
105 impl<K, D: DepKind> Default for QueryState<K, D> {
106 fn default() -> QueryState<K, D> {
107 QueryState { active: Default::default() }
111 /// A type representing the responsibility to execute the job in the `job` field.
112 /// This will poison the relevant query if dropped.
113 struct JobOwner<'tcx, K, D: DepKind>
115 K: Eq + Hash + Clone,
117 state: &'tcx QueryState<K, D>,
124 fn mk_cycle<Qcx, V, R, D: DepKind>(
126 cycle_error: CycleError<D>,
127 handler: HandleCycleError,
128 cache: &dyn crate::query::QueryStorage<Value = V, Stored = R>,
131 Qcx: QueryContext + crate::query::HasDepContext<DepKind = D>,
132 V: std::fmt::Debug + Value<Qcx::DepContext, Qcx::DepKind>,
135 let error = report_cycle(qcx.dep_context().sess(), &cycle_error);
136 let value = handle_cycle_error(*qcx.dep_context(), &cycle_error, error, handler);
137 cache.store_nocache(value)
140 fn handle_cycle_error<Tcx, V>(
142 cycle_error: &CycleError<Tcx::DepKind>,
143 mut error: DiagnosticBuilder<'_, ErrorGuaranteed>,
144 handler: HandleCycleError,
148 V: Value<Tcx, Tcx::DepKind>,
150 use HandleCycleError::*;
154 Value::from_cycle_error(tcx, &cycle_error.cycle)
158 tcx.sess().abort_if_errors();
162 error.delay_as_bug();
163 Value::from_cycle_error(tcx, &cycle_error.cycle)
168 impl<'tcx, K, D: DepKind> JobOwner<'tcx, K, D>
170 K: Eq + Hash + Clone,
172 /// Either gets a `JobOwner` corresponding the query, allowing us to
173 /// start executing the query, or returns with the result of the query.
174 /// This function assumes that `try_get_cached` is already called and returned `lookup`.
175 /// If the query is executing elsewhere, this will wait for it and return the result.
176 /// If the query panicked, this will silently panic.
178 /// This function is inlined because that results in a noticeable speed-up
179 /// for some compile-time benchmarks.
181 fn try_start<'b, Qcx>(
183 state: &'b QueryState<K, Qcx::DepKind>,
186 ) -> TryGetJob<'b, K, D>
188 Qcx: QueryContext + crate::query::HasDepContext<DepKind = D>,
190 #[cfg(parallel_compiler)]
191 let mut state_lock = state.active.get_shard_by_value(&key).lock();
192 #[cfg(not(parallel_compiler))]
193 let mut state_lock = state.active.lock();
194 let lock = &mut *state_lock;
196 match lock.entry(key) {
197 Entry::Vacant(entry) => {
198 let id = qcx.next_job_id();
199 let job = qcx.current_query_job();
200 let job = QueryJob::new(id, span, job);
202 let key = entry.key().clone();
203 entry.insert(QueryResult::Started(job));
205 let owner = JobOwner { state, id, key };
206 return TryGetJob::NotYetStarted(owner);
208 Entry::Occupied(mut entry) => {
209 match entry.get_mut() {
210 #[cfg(not(parallel_compiler))]
211 QueryResult::Started(job) => {
215 // If we are single-threaded we know that we have cycle error,
216 // so we just return the error.
217 return TryGetJob::Cycle(id.find_cycle_in_stack(
218 qcx.try_collect_active_jobs().unwrap(),
219 &qcx.current_query_job(),
223 #[cfg(parallel_compiler)]
224 QueryResult::Started(job) => {
225 // For parallel queries, we'll block and wait until the query running
226 // in another thread has completed. Record how long we wait in the
228 let query_blocked_prof_timer = qcx.dep_context().profiler().query_blocked();
231 let latch = job.latch();
235 // With parallel queries we might just have to wait on some other
237 let result = latch.wait_on(qcx.current_query_job(), span);
240 Ok(()) => TryGetJob::JobCompleted(query_blocked_prof_timer),
241 Err(cycle) => TryGetJob::Cycle(cycle),
244 QueryResult::Poisoned => FatalError.raise(),
250 /// Completes the query by updating the query cache with the `result`,
251 /// signals the waiter and forgets the JobOwner, so it won't poison the query
252 fn complete<C>(self, cache: &C, result: C::Value, dep_node_index: DepNodeIndex) -> C::Stored
254 C: QueryCache<Key = K>,
256 // We can move out of `self` here because we `mem::forget` it below
257 let key = unsafe { ptr::read(&self.key) };
258 let state = self.state;
260 // Forget ourself so our destructor won't poison the query
263 let (job, result) = {
265 #[cfg(parallel_compiler)]
266 let mut lock = state.active.get_shard_by_value(&key).lock();
267 #[cfg(not(parallel_compiler))]
268 let mut lock = state.active.lock();
269 match lock.remove(&key).unwrap() {
270 QueryResult::Started(job) => job,
271 QueryResult::Poisoned => panic!(),
274 let result = cache.complete(key, result, dep_node_index);
278 job.signal_complete();
283 impl<'tcx, K, D> Drop for JobOwner<'tcx, K, D>
285 K: Eq + Hash + Clone,
291 // Poison the query so jobs waiting on it panic.
292 let state = self.state;
294 #[cfg(parallel_compiler)]
295 let mut shard = state.active.get_shard_by_value(&self.key).lock();
296 #[cfg(not(parallel_compiler))]
297 let mut shard = state.active.lock();
298 let job = match shard.remove(&self.key).unwrap() {
299 QueryResult::Started(job) => job,
300 QueryResult::Poisoned => panic!(),
302 shard.insert(self.key.clone(), QueryResult::Poisoned);
305 // Also signal the completion of the job, so waiters
306 // will continue execution.
307 job.signal_complete();
312 pub(crate) struct CycleError<D: DepKind> {
313 /// The query and related span that uses the cycle.
314 pub usage: Option<(Span, QueryStackFrame<D>)>,
315 pub cycle: Vec<QueryInfo<D>>,
318 /// The result of `try_start`.
319 enum TryGetJob<'tcx, K, D>
321 K: Eq + Hash + Clone,
324 /// The query is not yet started. Contains a guard to the cache eventually used to start it.
325 NotYetStarted(JobOwner<'tcx, K, D>),
327 /// The query was already completed.
328 /// Returns the result of the query and its dep-node index
329 /// if it succeeded or a cycle error if it failed.
330 #[cfg(parallel_compiler)]
331 JobCompleted(TimingGuard<'tcx>),
333 /// Trying to execute the query resulted in a cycle.
334 Cycle(CycleError<D>),
337 /// Checks if the query is already computed and in the cache.
338 /// It returns the shard index and a lock guard to the shard,
339 /// which will be used if the query is not in the cache and we need
342 pub fn try_get_cached<Tcx, C>(tcx: Tcx, cache: &C, key: &C::Key) -> Option<C::Stored>
347 match cache.lookup(&key) {
348 Some((value, index)) => {
349 if std::intrinsics::unlikely(tcx.profiler().enabled()) {
350 tcx.profiler().query_cache_hit(index.into());
352 tcx.dep_graph().read_index(index);
359 fn try_execute_query<Q, Qcx>(
361 state: &QueryState<Q::Key, Qcx::DepKind>,
365 dep_node: Option<DepNode<Qcx::DepKind>>,
366 ) -> (Q::Stored, Option<DepNodeIndex>)
371 match JobOwner::<'_, Q::Key, Qcx::DepKind>::try_start(&qcx, state, span, key.clone()) {
372 TryGetJob::NotYetStarted(job) => {
373 let (result, dep_node_index) =
374 execute_job::<Q, Qcx>(qcx, key.clone(), dep_node, job.id);
376 // We may have put a value inside the cache from inside the execution.
377 // Verify that it has the same hash as what we have now, to ensure consistency.
378 if let Some((cached_result, _)) = cache.lookup(&key) {
379 let hasher = Q::HASH_RESULT.expect("feedable forbids no_hash");
381 let old_hash = qcx.dep_context().with_stable_hashing_context(|mut hcx| {
382 hasher(&mut hcx, cached_result.borrow())
386 .with_stable_hashing_context(|mut hcx| hasher(&mut hcx, &result));
390 "Computed query value for {:?}({:?}) is inconsistent with fed value,\ncomputed={:#?}\nfed={:#?}",
398 let result = job.complete(cache, result, dep_node_index);
399 (result, Some(dep_node_index))
401 TryGetJob::Cycle(error) => {
402 let result = mk_cycle(qcx, error, Q::HANDLE_CYCLE_ERROR, cache);
405 #[cfg(parallel_compiler)]
406 TryGetJob::JobCompleted(query_blocked_prof_timer) => {
407 let Some((v, index)) = cache.lookup(&key) else {
408 panic!("value must be in cache after waiting")
411 if std::intrinsics::unlikely(qcx.dep_context().profiler().enabled()) {
412 qcx.dep_context().profiler().query_cache_hit(index.into());
414 query_blocked_prof_timer.finish_with_query_invocation_id(index.into());
421 fn execute_job<Q, Qcx>(
424 mut dep_node_opt: Option<DepNode<Qcx::DepKind>>,
426 ) -> (Q::Value, DepNodeIndex)
431 let dep_graph = qcx.dep_context().dep_graph();
433 // Fast path for when incr. comp. is off.
434 if !dep_graph.is_fully_enabled() {
435 let prof_timer = qcx.dep_context().profiler().query_provider();
436 let result = qcx.start_query(job_id, Q::DEPTH_LIMIT, None, || {
437 Q::compute(qcx, &key)(*qcx.dep_context(), key)
439 let dep_node_index = dep_graph.next_virtual_depnode_index();
440 prof_timer.finish_with_query_invocation_id(dep_node_index.into());
441 return (result, dep_node_index);
444 if !Q::ANON && !Q::EVAL_ALWAYS {
445 // `to_dep_node` is expensive for some `DepKind`s.
447 dep_node_opt.get_or_insert_with(|| Q::construct_dep_node(*qcx.dep_context(), &key));
449 // The diagnostics for this query will be promoted to the current session during
450 // `try_mark_green()`, so we can ignore them here.
451 if let Some(ret) = qcx.start_query(job_id, false, None, || {
452 try_load_from_disk_and_cache_in_memory::<Q, Qcx>(qcx, &key, &dep_node)
458 let prof_timer = qcx.dep_context().profiler().query_provider();
459 let diagnostics = Lock::new(ThinVec::new());
461 let (result, dep_node_index) =
462 qcx.start_query(job_id, Q::DEPTH_LIMIT, Some(&diagnostics), || {
464 return dep_graph.with_anon_task(*qcx.dep_context(), Q::DEP_KIND, || {
465 Q::compute(qcx, &key)(*qcx.dep_context(), key)
469 // `to_dep_node` is expensive for some `DepKind`s.
471 dep_node_opt.unwrap_or_else(|| Q::construct_dep_node(*qcx.dep_context(), &key));
473 let task = Q::compute(qcx, &key);
474 dep_graph.with_task(dep_node, *qcx.dep_context(), key, task, Q::HASH_RESULT)
477 prof_timer.finish_with_query_invocation_id(dep_node_index.into());
479 let diagnostics = diagnostics.into_inner();
480 let side_effects = QuerySideEffects { diagnostics };
482 if std::intrinsics::unlikely(!side_effects.is_empty()) {
484 qcx.store_side_effects_for_anon_node(dep_node_index, side_effects);
486 qcx.store_side_effects(dep_node_index, side_effects);
490 (result, dep_node_index)
493 fn try_load_from_disk_and_cache_in_memory<Q, Qcx>(
496 dep_node: &DepNode<Qcx::DepKind>,
497 ) -> Option<(Q::Value, DepNodeIndex)>
502 // Note this function can be called concurrently from the same query
503 // We must ensure that this is handled correctly.
505 let dep_graph = qcx.dep_context().dep_graph();
506 let (prev_dep_node_index, dep_node_index) = dep_graph.try_mark_green(qcx, &dep_node)?;
508 debug_assert!(dep_graph.is_green(dep_node));
510 // First we try to load the result from the on-disk cache.
511 // Some things are never cached on disk.
512 if let Some(try_load_from_disk) = Q::try_load_from_disk(qcx, &key) {
513 let prof_timer = qcx.dep_context().profiler().incr_cache_loading();
515 // The call to `with_query_deserialization` enforces that no new `DepNodes`
516 // are created during deserialization. See the docs of that method for more
519 dep_graph.with_query_deserialization(|| try_load_from_disk(qcx, prev_dep_node_index));
521 prof_timer.finish_with_query_invocation_id(dep_node_index.into());
523 if let Some(result) = result {
524 if std::intrinsics::unlikely(
525 qcx.dep_context().sess().opts.unstable_opts.query_dep_graph,
527 dep_graph.mark_debug_loaded_from_disk(*dep_node)
530 let prev_fingerprint = qcx
533 .prev_fingerprint_of(dep_node)
534 .unwrap_or(Fingerprint::ZERO);
535 // If `-Zincremental-verify-ich` is specified, re-hash results from
536 // the cache and make sure that they have the expected fingerprint.
538 // If not, we still seek to verify a subset of fingerprints loaded
539 // from disk. Re-hashing results is fairly expensive, so we can't
540 // currently afford to verify every hash. This subset should still
541 // give us some coverage of potential bugs though.
542 let try_verify = prev_fingerprint.as_value().1 % 32 == 0;
543 if std::intrinsics::unlikely(
544 try_verify || qcx.dep_context().sess().opts.unstable_opts.incremental_verify_ich,
546 incremental_verify_ich(*qcx.dep_context(), &result, dep_node, Q::HASH_RESULT);
549 return Some((result, dep_node_index));
552 // We always expect to find a cached result for things that
553 // can be forced from `DepNode`.
555 !qcx.dep_context().fingerprint_style(dep_node.kind).reconstructible(),
556 "missing on-disk cache entry for {dep_node:?}"
560 // We could not load a result from the on-disk cache, so
562 let prof_timer = qcx.dep_context().profiler().query_provider();
564 // The dep-graph for this computation is already in-place.
565 let result = dep_graph.with_ignore(|| Q::compute(qcx, key)(*qcx.dep_context(), key.clone()));
567 prof_timer.finish_with_query_invocation_id(dep_node_index.into());
569 // Verify that re-running the query produced a result with the expected hash
570 // This catches bugs in query implementations, turning them into ICEs.
571 // For example, a query might sort its result by `DefId` - since `DefId`s are
572 // not stable across compilation sessions, the result could get up getting sorted
573 // in a different order when the query is re-run, even though all of the inputs
574 // (e.g. `DefPathHash` values) were green.
576 // See issue #82920 for an example of a miscompilation that would get turned into
577 // an ICE by this check
578 incremental_verify_ich(*qcx.dep_context(), &result, dep_node, Q::HASH_RESULT);
580 Some((result, dep_node_index))
583 #[instrument(skip(tcx, result, hash_result), level = "debug")]
584 pub(crate) fn incremental_verify_ich<Tcx, V: Debug>(
587 dep_node: &DepNode<Tcx::DepKind>,
588 hash_result: Option<fn(&mut StableHashingContext<'_>, &V) -> Fingerprint>,
594 tcx.dep_graph().is_green(dep_node),
595 "fingerprint for green query instance not loaded from cache: {dep_node:?}",
598 let new_hash = hash_result.map_or(Fingerprint::ZERO, |f| {
599 tcx.with_stable_hashing_context(|mut hcx| f(&mut hcx, result))
602 let old_hash = tcx.dep_graph().prev_fingerprint_of(dep_node);
604 if Some(new_hash) != old_hash {
605 incremental_verify_ich_failed(
607 DebugArg::from(&dep_node),
608 DebugArg::from(&result),
615 // This DebugArg business is largely a mirror of std::fmt::ArgumentV1, which is
616 // currently not exposed publicly.
618 // The PR which added this attempted to use `&dyn Debug` instead, but that
619 // showed statistically significant worse compiler performance. It's not
620 // actually clear what the cause there was -- the code should be cold. If this
621 // can be replaced with `&dyn Debug` with on perf impact, then it probably
627 struct DebugArg<'a> {
629 fmt: fn(&Opaque, &mut std::fmt::Formatter<'_>) -> std::fmt::Result,
632 impl<'a, T> From<&'a T> for DebugArg<'a>
636 fn from(value: &'a T) -> DebugArg<'a> {
638 value: unsafe { std::mem::transmute(value) },
640 std::mem::transmute(<T as std::fmt::Debug>::fmt as fn(_, _) -> std::fmt::Result)
646 impl std::fmt::Debug for DebugArg<'_> {
647 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
648 (self.fmt)(self.value, f)
652 // Note that this is marked #[cold] and intentionally takes the equivalent of
653 // `dyn Debug` for its arguments, as we want to avoid generating a bunch of
654 // different implementations for LLVM to chew on (and filling up the final
657 fn incremental_verify_ich_failed(sess: &Session, dep_node: DebugArg<'_>, result: DebugArg<'_>) {
658 // When we emit an error message and panic, we try to debug-print the `DepNode`
659 // and query result. Unfortunately, this can cause us to run additional queries,
660 // which may result in another fingerprint mismatch while we're in the middle
661 // of processing this one. To avoid a double-panic (which kills the process
662 // before we can print out the query static), we print out a terse
663 // but 'safe' message if we detect a re-entrant call to this method.
665 static INSIDE_VERIFY_PANIC: Cell<bool> = const { Cell::new(false) };
668 let old_in_panic = INSIDE_VERIFY_PANIC.with(|in_panic| in_panic.replace(true));
671 sess.emit_err(crate::error::Reentrant);
673 let run_cmd = if let Some(crate_name) = &sess.opts.crate_name {
674 format!("`cargo clean -p {crate_name}` or `cargo clean`")
676 "`cargo clean`".to_string()
679 sess.emit_err(crate::error::IncrementCompilation {
681 dep_node: format!("{dep_node:?}"),
683 panic!("Found unstable fingerprints for {dep_node:?}: {result:?}");
686 INSIDE_VERIFY_PANIC.with(|in_panic| in_panic.set(old_in_panic));
689 /// Ensure that either this query has all green inputs or been executed.
690 /// Executing `query::ensure(D)` is considered a read of the dep-node `D`.
691 /// Returns true if the query should still run.
693 /// This function is particularly useful when executing passes for their
694 /// side-effects -- e.g., in order to report errors for erroneous programs.
696 /// Note: The optimization is only available during incr. comp.
698 fn ensure_must_run<Q, Qcx>(qcx: Qcx, key: &Q::Key) -> (bool, Option<DepNode<Qcx::DepKind>>)
707 // Ensuring an anonymous query makes no sense
710 let dep_node = Q::construct_dep_node(*qcx.dep_context(), key);
712 let dep_graph = qcx.dep_context().dep_graph();
713 match dep_graph.try_mark_green(qcx, &dep_node) {
715 // A None return from `try_mark_green` means that this is either
716 // a new dep node or that the dep node has already been marked red.
717 // Either way, we can't call `dep_graph.read()` as we don't have the
718 // DepNodeIndex. We must invoke the query itself. The performance cost
719 // this introduces should be negligible as we'll immediately hit the
720 // in-memory cache, or another query down the line will.
721 (true, Some(dep_node))
723 Some((_, dep_node_index)) => {
724 dep_graph.read_index(dep_node_index);
725 qcx.dep_context().profiler().query_cache_hit(dep_node_index.into());
737 pub fn get_query<Q, Qcx, D>(qcx: Qcx, span: Span, key: Q::Key, mode: QueryMode) -> Option<Q::Stored>
741 Q::Value: Value<Qcx::DepContext, D>,
744 let dep_node = if let QueryMode::Ensure = mode {
745 let (must_run, dep_node) = ensure_must_run::<Q, _>(qcx, &key);
754 let (result, dep_node_index) = try_execute_query::<Q, Qcx>(
762 if let Some(dep_node_index) = dep_node_index {
763 qcx.dep_context().dep_graph().read_index(dep_node_index)
768 pub fn force_query<Q, Qcx, D>(qcx: Qcx, key: Q::Key, dep_node: DepNode<Qcx::DepKind>)
772 Q::Value: Value<Qcx::DepContext, D>,
775 // We may be concurrently trying both execute and force a query.
776 // Ensure that only one of them runs the query.
777 let cache = Q::query_cache(qcx);
778 if let Some((_, index)) = cache.lookup(&key) {
779 if std::intrinsics::unlikely(qcx.dep_context().profiler().enabled()) {
780 qcx.dep_context().profiler().query_cache_hit(index.into());
785 let state = Q::query_state(qcx);
786 debug_assert!(!Q::ANON);
788 try_execute_query::<Q, _>(qcx, state, cache, DUMMY_SP, key, Some(dep_node));