Move the query system to rustc_query_impl.

7 files changed, 1632 insertions, 0 deletions

diff --git a/compiler/rustc_query_impl/src/README.md b/compiler/rustc_query_impl/src/README.md
new file mode 100644
index 00000000000..8ec07b9fdeb
--- /dev/null
+++ b/compiler/rustc_query_impl/src/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_impl/src/keys.rs b/compiler/rustc_query_impl/src/keys.rs
new file mode 100644
index 00000000000..1ae5bf12cab
--- /dev/null
+++ b/compiler/rustc_query_impl/src/keys.rs
@@ -0,0 +1,333 @@
+//! Defines the set of legal keys that can be used in queries.
+
+use rustc_hir::def_id::{CrateNum, DefId, LocalDefId, LOCAL_CRATE};
+use rustc_middle::infer::canonical::Canonical;
+use rustc_middle::mir;
+use rustc_middle::ty::fast_reject::SimplifiedType;
+use rustc_middle::ty::subst::{GenericArg, SubstsRef};
+use rustc_middle::ty::{self, Ty, TyCtxt};
+use rustc_span::symbol::{Ident, Symbol};
+use rustc_span::{Span, DUMMY_SP};
+
+/// The `Key` trait controls what types can legally be used as the key
+/// for a query.
+pub trait Key {
+    /// Given an instance of this key, what crate is it referring to?
+    /// This is used to find the provider.
+    fn query_crate(&self) -> CrateNum;
+
+    /// In the event that a cycle occurs, if no explicit span has been
+    /// given for a query with key `self`, what span should we use?
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span;
+}
+
+impl<'tcx> Key for ty::InstanceDef<'tcx> {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        tcx.def_span(self.def_id())
+    }
+}
+
+impl<'tcx> Key for ty::Instance<'tcx> {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        tcx.def_span(self.def_id())
+    }
+}
+
+impl<'tcx> Key for mir::interpret::GlobalId<'tcx> {
+    fn query_crate(&self) -> CrateNum {
+        self.instance.query_crate()
+    }
+
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.instance.default_span(tcx)
+    }
+}
+
+impl<'tcx> Key for mir::interpret::LitToConstInput<'tcx> {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+
+    fn default_span(&self, _tcx: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl Key for CrateNum {
+    fn query_crate(&self) -> CrateNum {
+        *self
+    }
+    fn default_span(&self, _: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl Key for LocalDefId {
+    fn query_crate(&self) -> CrateNum {
+        self.to_def_id().query_crate()
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.to_def_id().default_span(tcx)
+    }
+}
+
+impl Key for DefId {
+    fn query_crate(&self) -> CrateNum {
+        self.krate
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        tcx.def_span(*self)
+    }
+}
+
+impl Key for ty::WithOptConstParam<LocalDefId> {
+    fn query_crate(&self) -> CrateNum {
+        self.did.query_crate()
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.did.default_span(tcx)
+    }
+}
+
+impl Key for (DefId, DefId) {
+    fn query_crate(&self) -> CrateNum {
+        self.0.krate
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.1.default_span(tcx)
+    }
+}
+
+impl Key for (ty::Instance<'tcx>, LocalDefId) {
+    fn query_crate(&self) -> CrateNum {
+        self.0.query_crate()
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.0.default_span(tcx)
+    }
+}
+
+impl Key for (DefId, LocalDefId) {
+    fn query_crate(&self) -> CrateNum {
+        self.0.krate
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.1.default_span(tcx)
+    }
+}
+
+impl Key for (LocalDefId, DefId) {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.0.default_span(tcx)
+    }
+}
+
+impl Key for (DefId, Option<Ident>) {
+    fn query_crate(&self) -> CrateNum {
+        self.0.krate
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        tcx.def_span(self.0)
+    }
+}
+
+impl Key for (DefId, LocalDefId, Ident) {
+    fn query_crate(&self) -> CrateNum {
+        self.0.krate
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.1.default_span(tcx)
+    }
+}
+
+impl Key for (CrateNum, DefId) {
+    fn query_crate(&self) -> CrateNum {
+        self.0
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.1.default_span(tcx)
+    }
+}
+
+impl Key for (DefId, SimplifiedType) {
+    fn query_crate(&self) -> CrateNum {
+        self.0.krate
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.0.default_span(tcx)
+    }
+}
+
+impl<'tcx> Key for SubstsRef<'tcx> {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, _: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl<'tcx> Key for (DefId, SubstsRef<'tcx>) {
+    fn query_crate(&self) -> CrateNum {
+        self.0.krate
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.0.default_span(tcx)
+    }
+}
+
+impl<'tcx> Key
+    for (
+        (ty::WithOptConstParam<DefId>, SubstsRef<'tcx>),
+        (ty::WithOptConstParam<DefId>, SubstsRef<'tcx>),
+    )
+{
+    fn query_crate(&self) -> CrateNum {
+        (self.0).0.did.krate
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        (self.0).0.did.default_span(tcx)
+    }
+}
+
+impl<'tcx> Key for (LocalDefId, DefId, SubstsRef<'tcx>) {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.0.default_span(tcx)
+    }
+}
+
+impl<'tcx> Key for (ty::ParamEnv<'tcx>, ty::PolyTraitRef<'tcx>) {
+    fn query_crate(&self) -> CrateNum {
+        self.1.def_id().krate
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        tcx.def_span(self.1.def_id())
+    }
+}
+
+impl<'tcx> Key for (&'tcx ty::Const<'tcx>, mir::Field) {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, _: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl<'tcx> Key for ty::PolyTraitRef<'tcx> {
+    fn query_crate(&self) -> CrateNum {
+        self.def_id().krate
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        tcx.def_span(self.def_id())
+    }
+}
+
+impl<'tcx> Key for GenericArg<'tcx> {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, _: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl<'tcx> Key for &'tcx ty::Const<'tcx> {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, _: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl<'tcx> Key for Ty<'tcx> {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, _: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl<'tcx> Key for &'tcx ty::List<ty::Predicate<'tcx>> {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, _: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl<'tcx> Key for ty::ParamEnv<'tcx> {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, _: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl<'tcx, T: Key> Key for ty::ParamEnvAnd<'tcx, T> {
+    fn query_crate(&self) -> CrateNum {
+        self.value.query_crate()
+    }
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.value.default_span(tcx)
+    }
+}
+
+impl Key for Symbol {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, _tcx: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
+
+/// Canonical query goals correspond to abstract trait operations that
+/// are not tied to any crate in particular.
+impl<'tcx, T> Key for Canonical<'tcx, T> {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+
+    fn default_span(&self, _tcx: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl Key for (Symbol, u32, u32) {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+
+    fn default_span(&self, _tcx: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl<'tcx> Key for (DefId, Ty<'tcx>, SubstsRef<'tcx>, ty::ParamEnv<'tcx>) {
+    fn query_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+
+    fn default_span(&self, _tcx: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
diff --git a/compiler/rustc_query_impl/src/lib.rs b/compiler/rustc_query_impl/src/lib.rs
new file mode 100644
index 00000000000..43dfe6892b1
--- /dev/null
+++ b/compiler/rustc_query_impl/src/lib.rs
@@ -0,0 +1,65 @@
+//! Support for serializing the dep-graph and reloading it.
+
+#![doc(html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/")]
+#![feature(in_band_lifetimes)]
+#![feature(exhaustive_patterns)]
+#![feature(nll)]
+#![feature(min_specialization)]
+#![feature(crate_visibility_modifier)]
+#![feature(once_cell)]
+#![feature(rustc_attrs)]
+#![feature(never_type)]
+#![recursion_limit = "256"]
+
+#[macro_use]
+extern crate rustc_middle;
+#[macro_use]
+extern crate tracing;
+
+use rustc_data_structures::fingerprint::Fingerprint;
+use rustc_data_structures::fx::FxHashMap;
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
+use rustc_errors::{Diagnostic, Handler, Level};
+use rustc_hir::def_id::CrateNum;
+use rustc_index::vec::IndexVec;
+use rustc_middle::dep_graph;
+use rustc_middle::ich::StableHashingContext;
+use rustc_middle::ty::query::{query_keys, query_storage, query_stored, query_values};
+use rustc_middle::ty::query::{Providers, QueryEngine};
+use rustc_middle::ty::TyCtxt;
+use rustc_serialize::opaque;
+use rustc_span::{Span, DUMMY_SP};
+use std::mem;
+
+#[macro_use]
+mod plumbing;
+pub use plumbing::QueryCtxt;
+use plumbing::QueryStruct;
+use rustc_query_system::query::*;
+
+mod stats;
+pub use self::stats::print_stats;
+
+mod keys;
+use keys::Key;
+
+mod values;
+use self::values::Value;
+
+use rustc_query_system::query::QueryAccessors;
+pub use rustc_query_system::query::QueryConfig;
+pub(crate) use rustc_query_system::query::QueryDescription;
+
+use rustc_middle::ty::query::on_disk_cache;
+
+mod profiling_support;
+pub use self::profiling_support::alloc_self_profile_query_strings;
+
+rustc_query_append! { [define_queries!][<'tcx>] }
+
+impl<'tcx> Queries<'tcx> {
+    // Force codegen in the dyn-trait transformation in this crate.
+    pub fn as_dyn(&'tcx self) -> &'tcx dyn QueryEngine<'tcx> {
+        self
+    }
+}
diff --git a/compiler/rustc_query_impl/src/plumbing.rs b/compiler/rustc_query_impl/src/plumbing.rs
new file mode 100644
index 00000000000..466c1f79f48
--- /dev/null
+++ b/compiler/rustc_query_impl/src/plumbing.rs
@@ -0,0 +1,726 @@
+//! 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 super::{queries, Query};
+use rustc_middle::dep_graph::{DepKind, DepNode, DepNodeExt, DepNodeIndex, SerializedDepNodeIndex};
+use rustc_middle::ty::query::on_disk_cache;
+use rustc_middle::ty::tls::{self, ImplicitCtxt};
+use rustc_middle::ty::{self, TyCtxt};
+use rustc_query_system::dep_graph::HasDepContext;
+use rustc_query_system::query::{CycleError, QueryJobId, QueryJobInfo};
+use rustc_query_system::query::{QueryContext, QueryDescription};
+
+use rustc_data_structures::fx::FxHashMap;
+use rustc_data_structures::sync::Lock;
+use rustc_data_structures::thin_vec::ThinVec;
+use rustc_errors::{struct_span_err, Diagnostic, DiagnosticBuilder};
+use rustc_serialize::opaque;
+use rustc_span::def_id::{DefId, LocalDefId};
+use rustc_span::Span;
+
+#[derive(Copy, Clone)]
+pub struct QueryCtxt<'tcx> {
+    pub tcx: TyCtxt<'tcx>,
+    pub queries: &'tcx super::Queries<'tcx>,
+}
+
+impl<'tcx> std::ops::Deref for QueryCtxt<'tcx> {
+    type Target = TyCtxt<'tcx>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.tcx
+    }
+}
+
+impl HasDepContext for QueryCtxt<'tcx> {
+    type DepKind = rustc_middle::dep_graph::DepKind;
+    type StableHashingContext = rustc_middle::ich::StableHashingContext<'tcx>;
+    type DepContext = TyCtxt<'tcx>;
+
+    #[inline]
+    fn dep_context(&self) -> &Self::DepContext {
+        &self.tcx
+    }
+}
+
+impl QueryContext for QueryCtxt<'tcx> {
+    type Query = Query<'tcx>;
+
+    fn incremental_verify_ich(&self) -> bool {
+        self.sess.opts.debugging_opts.incremental_verify_ich
+    }
+    fn verbose(&self) -> bool {
+        self.sess.verbose()
+    }
+
+    fn def_path_str(&self, def_id: DefId) -> String {
+        self.tcx.def_path_str(def_id)
+    }
+
+    fn current_query_job(&self) -> Option<QueryJobId<Self::DepKind>> {
+        tls::with_related_context(**self, |icx| icx.query)
+    }
+
+    fn try_collect_active_jobs(
+        &self,
+    ) -> Option<FxHashMap<QueryJobId<Self::DepKind>, QueryJobInfo<Self::DepKind, Self::Query>>>
+    {
+        self.queries.try_collect_active_jobs()
+    }
+
+    fn try_load_from_on_disk_cache(&self, dep_node: &DepNode) {
+        let cb = &super::QUERY_CALLBACKS[dep_node.kind as usize];
+        (cb.try_load_from_on_disk_cache)(*self, dep_node)
+    }
+
+    fn try_force_from_dep_node(&self, dep_node: &DepNode) -> bool {
+        // FIXME: This match is just a workaround for incremental bugs and should
+        // be removed. https://github.com/rust-lang/rust/issues/62649 is one such
+        // bug that must be fixed before removing this.
+        match dep_node.kind {
+            DepKind::hir_owner | DepKind::hir_owner_nodes => {
+                if let Some(def_id) = dep_node.extract_def_id(**self) {
+                    let def_id = def_id.expect_local();
+                    let hir_id = self.tcx.hir().local_def_id_to_hir_id(def_id);
+                    if def_id != hir_id.owner {
+                        // This `DefPath` does not have a
+                        // corresponding `DepNode` (e.g. a
+                        // struct field), and the ` DefPath`
+                        // collided with the `DefPath` of a
+                        // proper item that existed in the
+                        // previous compilation session.
+                        //
+                        // Since the given `DefPath` does not
+                        // denote the item that previously
+                        // existed, we just fail to mark green.
+                        return false;
+                    }
+                } else {
+                    // If the node does not exist anymore, we
+                    // just fail to mark green.
+                    return false;
+                }
+            }
+            _ => {
+                // For other kinds of nodes it's OK to be
+                // forced.
+            }
+        }
+
+        debug!("try_force_from_dep_node({:?}) --- trying to force", dep_node);
+
+        // We must avoid ever having to call `force_from_dep_node()` for a
+        // `DepNode::codegen_unit`:
+        // Since we cannot reconstruct the query key of a `DepNode::codegen_unit`, we
+        // would always end up having to evaluate the first caller of the
+        // `codegen_unit` query that *is* reconstructible. This might very well be
+        // the `compile_codegen_unit` query, thus re-codegenning the whole CGU just
+        // to re-trigger calling the `codegen_unit` query with the right key. At
+        // that point we would already have re-done all the work we are trying to
+        // avoid doing in the first place.
+        // The solution is simple: Just explicitly call the `codegen_unit` query for
+        // each CGU, right after partitioning. This way `try_mark_green` will always
+        // hit the cache instead of having to go through `force_from_dep_node`.
+        // This assertion makes sure, we actually keep applying the solution above.
+        debug_assert!(
+            dep_node.kind != DepKind::codegen_unit,
+            "calling force_from_dep_node() on DepKind::codegen_unit"
+        );
+
+        let cb = &super::QUERY_CALLBACKS[dep_node.kind as usize];
+        (cb.force_from_dep_node)(*self, dep_node)
+    }
+
+    fn has_errors_or_delayed_span_bugs(&self) -> bool {
+        self.sess.has_errors_or_delayed_span_bugs()
+    }
+
+    fn diagnostic(&self) -> &rustc_errors::Handler {
+        self.sess.diagnostic()
+    }
+
+    // Interactions with on_disk_cache
+    fn load_diagnostics(&self, prev_dep_node_index: SerializedDepNodeIndex) -> Vec<Diagnostic> {
+        self.on_disk_cache
+            .as_ref()
+            .map(|c| c.load_diagnostics(**self, prev_dep_node_index))
+            .unwrap_or_default()
+    }
+
+    fn store_diagnostics(&self, dep_node_index: DepNodeIndex, diagnostics: ThinVec<Diagnostic>) {
+        if let Some(c) = self.on_disk_cache.as_ref() {
+            c.store_diagnostics(dep_node_index, diagnostics)
+        }
+    }
+
+    fn store_diagnostics_for_anon_node(
+        &self,
+        dep_node_index: DepNodeIndex,
+        diagnostics: ThinVec<Diagnostic>,
+    ) {
+        if let Some(c) = self.on_disk_cache.as_ref() {
+            c.store_diagnostics_for_anon_node(dep_node_index, diagnostics)
+        }
+    }
+
+    /// 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.
+    #[inline(always)]
+    fn start_query<R>(
+        &self,
+        token: QueryJobId<Self::DepKind>,
+        diagnostics: Option<&Lock<ThinVec<Diagnostic>>>,
+        compute: impl FnOnce() -> R,
+    ) -> R {
+        // The `TyCtxt` stored in TLS has the same global interner lifetime
+        // as `self`, so we use `with_related_context` to relate the 'tcx lifetimes
+        // when accessing the `ImplicitCtxt`.
+        tls::with_related_context(**self, move |current_icx| {
+            // Update the `ImplicitCtxt` to point to our new query job.
+            let new_icx = ImplicitCtxt {
+                tcx: **self,
+                query: Some(token),
+                diagnostics,
+                layout_depth: current_icx.layout_depth,
+                task_deps: current_icx.task_deps,
+            };
+
+            // Use the `ImplicitCtxt` while we execute the query.
+            tls::enter_context(&new_icx, |_| {
+                rustc_data_structures::stack::ensure_sufficient_stack(compute)
+            })
+        })
+    }
+}
+
+impl<'tcx> QueryCtxt<'tcx> {
+    #[inline(never)]
+    #[cold]
+    pub(super) fn report_cycle(
+        self,
+        CycleError { usage, cycle: stack }: CycleError<Query<'tcx>>,
+    ) -> DiagnosticBuilder<'tcx> {
+        assert!(!stack.is_empty());
+
+        let fix_span = |span: Span, query: &Query<'tcx>| {
+            self.sess.source_map().guess_head_span(query.default_span(*self, span))
+        };
+
+        // Disable naming impls with types in this path, since that
+        // sometimes cycles itself, leading to extra cycle errors.
+        // (And cycle errors around impls tend to occur during the
+        // collect/coherence phases anyhow.)
+        ty::print::with_forced_impl_filename_line(|| {
+            let span = fix_span(stack[1 % stack.len()].span, &stack[0].query);
+            let mut err = struct_span_err!(
+                self.sess,
+                span,
+                E0391,
+                "cycle detected when {}",
+                stack[0].query.describe(self)
+            );
+
+            for i in 1..stack.len() {
+                let query = &stack[i].query;
+                let span = fix_span(stack[(i + 1) % stack.len()].span, query);
+                err.span_note(span, &format!("...which requires {}...", query.describe(self)));
+            }
+
+            err.note(&format!(
+                "...which again requires {}, completing the cycle",
+                stack[0].query.describe(self)
+            ));
+
+            if let Some((span, query)) = usage {
+                err.span_note(
+                    fix_span(span, &query),
+                    &format!("cycle used when {}", query.describe(self)),
+                );
+            }
+
+            err
+        })
+    }
+
+    pub(super) fn encode_query_results(
+        self,
+        encoder: &mut on_disk_cache::CacheEncoder<'a, 'tcx, opaque::FileEncoder>,
+        query_result_index: &mut on_disk_cache::EncodedQueryResultIndex,
+    ) -> opaque::FileEncodeResult {
+        macro_rules! encode_queries {
+            ($($query:ident,)*) => {
+                $(
+                    on_disk_cache::encode_query_results::<_, super::queries::$query<'_>>(
+                        self,
+                        encoder,
+                        query_result_index
+                    )?;
+                )*
+            }
+        }
+
+        rustc_cached_queries!(encode_queries!);
+
+        Ok(())
+    }
+}
+
+/// This struct stores metadata about each Query.
+///
+/// Information is retrieved by indexing the `QUERIES` array using the integer value
+/// of the `DepKind`. Overall, this allows to implement `QueryContext` using this manual
+/// jump table instead of large matches.
+pub struct QueryStruct {
+    /// The red/green evaluation system will try to mark a specific DepNode in the
+    /// dependency graph as green by recursively trying to mark the dependencies of
+    /// that `DepNode` as green. While doing so, it will sometimes encounter a `DepNode`
+    /// where we don't know if it is red or green and we therefore actually have
+    /// to recompute its value in order to find out. Since the only piece of
+    /// information that we have at that point is the `DepNode` we are trying to
+    /// re-evaluate, we need some way to re-run a query from just that. This is what
+    /// `force_from_dep_node()` implements.
+    ///
+    /// In the general case, a `DepNode` consists of a `DepKind` and an opaque
+    /// GUID/fingerprint that will uniquely identify the node. This GUID/fingerprint
+    /// is usually constructed by computing a stable hash of the query-key that the
+    /// `DepNode` corresponds to. Consequently, it is not in general possible to go
+    /// back from hash to query-key (since hash functions are not reversible). For
+    /// this reason `force_from_dep_node()` is expected to fail from time to time
+    /// because we just cannot find out, from the `DepNode` alone, what the
+    /// corresponding query-key is and therefore cannot re-run the query.
+    ///
+    /// The system deals with this case letting `try_mark_green` fail which forces
+    /// the root query to be re-evaluated.
+    ///
+    /// Now, if `force_from_dep_node()` would always fail, it would be pretty useless.
+    /// Fortunately, we can use some contextual information that will allow us to
+    /// reconstruct query-keys for certain kinds of `DepNode`s. In particular, we
+    /// enforce by construction that the GUID/fingerprint of certain `DepNode`s is a
+    /// valid `DefPathHash`. Since we also always build a huge table that maps every
+    /// `DefPathHash` in the current codebase to the corresponding `DefId`, we have
+    /// everything we need to re-run the query.
+    ///
+    /// Take the `mir_promoted` query as an example. Like many other queries, it
+    /// just has a single parameter: the `DefId` of the item it will compute the
+    /// validated MIR for. Now, when we call `force_from_dep_node()` on a `DepNode`
+    /// with kind `MirValidated`, we know that the GUID/fingerprint of the `DepNode`
+    /// is actually a `DefPathHash`, and can therefore just look up the corresponding
+    /// `DefId` in `tcx.def_path_hash_to_def_id`.
+    ///
+    /// When you implement a new query, it will likely have a corresponding new
+    /// `DepKind`, and you'll have to support it here in `force_from_dep_node()`. As
+    /// a rule of thumb, if your query takes a `DefId` or `LocalDefId` as sole parameter,
+    /// then `force_from_dep_node()` should not fail for it. Otherwise, you can just
+    /// add it to the "We don't have enough information to reconstruct..." group in
+    /// the match below.
+    pub(crate) force_from_dep_node: fn(tcx: QueryCtxt<'_>, dep_node: &DepNode) -> bool,
+
+    /// Invoke a query to put the on-disk cached value in memory.
+    pub(crate) try_load_from_on_disk_cache: fn(QueryCtxt<'_>, &DepNode),
+}
+
+macro_rules! handle_cycle_error {
+    ([][$tcx: expr, $error:expr]) => {{
+        $tcx.report_cycle($error).emit();
+        Value::from_cycle_error($tcx)
+    }};
+    ([fatal_cycle $($rest:tt)*][$tcx:expr, $error:expr]) => {{
+        $tcx.report_cycle($error).emit();
+        $tcx.sess.abort_if_errors();
+        unreachable!()
+    }};
+    ([cycle_delay_bug $($rest:tt)*][$tcx:expr, $error:expr]) => {{
+        $tcx.report_cycle($error).delay_as_bug();
+        Value::from_cycle_error($tcx)
+    }};
+    ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*][$($args:tt)*]) => {
+        handle_cycle_error!([$($($modifiers)*)*][$($args)*])
+    };
+}
+
+macro_rules! is_anon {
+    ([]) => {{
+        false
+    }};
+    ([anon $($rest:tt)*]) => {{
+        true
+    }};
+    ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*]) => {
+        is_anon!([$($($modifiers)*)*])
+    };
+}
+
+macro_rules! is_eval_always {
+    ([]) => {{
+        false
+    }};
+    ([eval_always $($rest:tt)*]) => {{
+        true
+    }};
+    ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*]) => {
+        is_eval_always!([$($($modifiers)*)*])
+    };
+}
+
+macro_rules! hash_result {
+    ([][$hcx:expr, $result:expr]) => {{
+        dep_graph::hash_result($hcx, &$result)
+    }};
+    ([no_hash $($rest:tt)*][$hcx:expr, $result:expr]) => {{
+        None
+    }};
+    ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*][$($args:tt)*]) => {
+        hash_result!([$($($modifiers)*)*][$($args)*])
+    };
+}
+
+macro_rules! define_queries {
+    (<$tcx:tt>
+     $($(#[$attr:meta])*
+        [$($modifiers:tt)*] fn $name:ident($($K:tt)*) -> $V:ty,)*) => {
+
+        define_queries_struct! {
+            tcx: $tcx,
+            input: ($(([$($modifiers)*] [$($attr)*] [$name]))*)
+        }
+
+        #[allow(nonstandard_style)]
+        #[derive(Clone, Debug)]
+        pub enum Query<$tcx> {
+            $($(#[$attr])* $name(query_keys::$name<$tcx>)),*
+        }
+
+        impl<$tcx> Query<$tcx> {
+            pub fn name(&self) -> &'static str {
+                match *self {
+                    $(Query::$name(_) => stringify!($name),)*
+                }
+            }
+
+            pub(crate) fn describe(&self, tcx: QueryCtxt<$tcx>) -> String {
+                let (r, name) = match *self {
+                    $(Query::$name(key) => {
+                        (queries::$name::describe(tcx, key), stringify!($name))
+                    })*
+                };
+                if tcx.sess.verbose() {
+                    format!("{} [{}]", r, name)
+                } else {
+                    r
+                }
+            }
+
+            // FIXME(eddyb) Get more valid `Span`s on queries.
+            pub fn default_span(&self, tcx: TyCtxt<$tcx>, span: Span) -> Span {
+                if !span.is_dummy() {
+                    return span;
+                }
+                // The `def_span` query is used to calculate `default_span`,
+                // so exit to avoid infinite recursion.
+                if let Query::def_span(..) = *self {
+                    return span
+                }
+                match *self {
+                    $(Query::$name(key) => key.default_span(tcx),)*
+                }
+            }
+        }
+
+        impl<'a, $tcx> HashStable<StableHashingContext<'a>> for Query<$tcx> {
+            fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
+                mem::discriminant(self).hash_stable(hcx, hasher);
+                match *self {
+                    $(Query::$name(key) => key.hash_stable(hcx, hasher),)*
+                }
+            }
+        }
+
+        #[allow(nonstandard_style)]
+        pub mod queries {
+            use std::marker::PhantomData;
+
+            $(pub struct $name<$tcx> {
+                data: PhantomData<&$tcx ()>
+            })*
+        }
+
+        $(impl<$tcx> QueryConfig for queries::$name<$tcx> {
+            type Key = query_keys::$name<$tcx>;
+            type Value = query_values::$name<$tcx>;
+            type Stored = query_stored::$name<$tcx>;
+            const NAME: &'static str = stringify!($name);
+        }
+
+        impl<$tcx> QueryAccessors<QueryCtxt<$tcx>> for queries::$name<$tcx> {
+            const ANON: bool = is_anon!([$($modifiers)*]);
+            const EVAL_ALWAYS: bool = is_eval_always!([$($modifiers)*]);
+            const DEP_KIND: dep_graph::DepKind = dep_graph::DepKind::$name;
+
+            type Cache = query_storage::$name<$tcx>;
+
+            #[inline(always)]
+            fn query_state<'a>(tcx: QueryCtxt<$tcx>) -> &'a QueryState<crate::dep_graph::DepKind, Query<$tcx>, Self::Key> {
+                &tcx.queries.$name
+            }
+
+            #[inline(always)]
+            fn query_cache<'a>(tcx: QueryCtxt<$tcx>) -> &'a QueryCacheStore<Self::Cache>
+                where 'tcx:'a
+            {
+                &tcx.query_caches.$name
+            }
+
+            #[inline]
+            fn compute(tcx: QueryCtxt<'tcx>, key: Self::Key) -> Self::Value {
+                let provider = tcx.queries.providers.get(key.query_crate())
+                    // HACK(eddyb) it's possible crates may be loaded after
+                    // the query engine is created, and because crate loading
+                    // is not yet integrated with the query engine, such crates
+                    // would be missing appropriate entries in `providers`.
+                    .unwrap_or(&tcx.queries.fallback_extern_providers)
+                    .$name;
+                provider(*tcx, key)
+            }
+
+            fn hash_result(
+                _hcx: &mut StableHashingContext<'_>,
+                _result: &Self::Value
+            ) -> Option<Fingerprint> {
+                hash_result!([$($modifiers)*][_hcx, _result])
+            }
+
+            fn handle_cycle_error(
+                tcx: QueryCtxt<'tcx>,
+                error: CycleError<Query<'tcx>>
+            ) -> Self::Value {
+                handle_cycle_error!([$($modifiers)*][tcx, error])
+            }
+        })*
+
+        #[allow(non_upper_case_globals)]
+        pub mod query_callbacks {
+            use super::*;
+            use rustc_middle::dep_graph::DepNode;
+            use rustc_middle::ty::query::query_keys;
+            use rustc_query_system::dep_graph::DepNodeParams;
+            use rustc_query_system::query::{force_query, QueryDescription};
+
+            // We use this for most things when incr. comp. is turned off.
+            pub const Null: QueryStruct = QueryStruct {
+                force_from_dep_node: |_, dep_node| bug!("force_from_dep_node: encountered {:?}", dep_node),
+                try_load_from_on_disk_cache: |_, _| {},
+            };
+
+            pub const TraitSelect: QueryStruct = QueryStruct {
+                force_from_dep_node: |_, _| false,
+                try_load_from_on_disk_cache: |_, _| {},
+            };
+
+            pub const CompileCodegenUnit: QueryStruct = QueryStruct {
+                force_from_dep_node: |_, _| false,
+                try_load_from_on_disk_cache: |_, _| {},
+            };
+
+            $(pub const $name: QueryStruct = {
+                const is_anon: bool = is_anon!([$($modifiers)*]);
+
+                #[inline(always)]
+                fn can_reconstruct_query_key() -> bool {
+                    <query_keys::$name<'_> as DepNodeParams<TyCtxt<'_>>>
+                        ::can_reconstruct_query_key()
+                }
+
+                fn recover<'tcx>(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<query_keys::$name<'tcx>> {
+                    <query_keys::$name<'_> as DepNodeParams<TyCtxt<'_>>>::recover(tcx, dep_node)
+                }
+
+                fn force_from_dep_node(tcx: QueryCtxt<'_>, dep_node: &DepNode) -> bool {
+                    if is_anon {
+                        return false;
+                    }
+
+                    if !can_reconstruct_query_key() {
+                        return false;
+                    }
+
+                    if let Some(key) = recover(*tcx, dep_node) {
+                        force_query::<queries::$name<'_>, _>(tcx, key, DUMMY_SP, *dep_node);
+                        return true;
+                    }
+
+                    false
+                }
+
+                fn try_load_from_on_disk_cache(tcx: QueryCtxt<'_>, dep_node: &DepNode) {
+                    if is_anon {
+                        return
+                    }
+
+                    if !can_reconstruct_query_key() {
+                        return
+                    }
+
+                    debug_assert!(tcx.dep_graph
+                                     .node_color(dep_node)
+                                     .map(|c| c.is_green())
+                                     .unwrap_or(false));
+
+                    let key = recover(*tcx, dep_node).unwrap_or_else(|| panic!("Failed to recover key for {:?} with hash {}", dep_node, dep_node.hash));
+                    if queries::$name::cache_on_disk(tcx, &key, None) {
+                        let _ = tcx.$name(key);
+                    }
+                }
+
+                QueryStruct {
+                    force_from_dep_node,
+                    try_load_from_on_disk_cache,
+                }
+            };)*
+        }
+
+        static QUERY_CALLBACKS: &[QueryStruct] = &make_dep_kind_array!(query_callbacks);
+    }
+}
+
+// FIXME(eddyb) this macro (and others?) use `$tcx` and `'tcx` interchangeably.
+// We should either not take `$tcx` at all and use `'tcx` everywhere, or use
+// `$tcx` everywhere (even if that isn't necessary due to lack of hygiene).
+macro_rules! define_queries_struct {
+    (tcx: $tcx:tt,
+     input: ($(([$($modifiers:tt)*] [$($attr:tt)*] [$name:ident]))*)) => {
+        pub struct Queries<$tcx> {
+            providers: IndexVec<CrateNum, Providers>,
+            fallback_extern_providers: Box<Providers>,
+
+            $($(#[$attr])*  $name: QueryState<
+                crate::dep_graph::DepKind,
+                Query<$tcx>,
+                query_keys::$name<$tcx>,
+            >,)*
+        }
+
+        impl<$tcx> Queries<$tcx> {
+            pub fn new(
+                providers: IndexVec<CrateNum, Providers>,
+                fallback_extern_providers: Providers,
+            ) -> Self {
+                Queries {
+                    providers,
+                    fallback_extern_providers: Box::new(fallback_extern_providers),
+                    $($name: Default::default()),*
+                }
+            }
+
+            pub(crate) fn try_collect_active_jobs(
+                &self
+            ) -> Option<FxHashMap<QueryJobId<crate::dep_graph::DepKind>, QueryJobInfo<crate::dep_graph::DepKind, Query<$tcx>>>> {
+                let mut jobs = FxHashMap::default();
+
+                $(
+                    self.$name.try_collect_active_jobs(
+                        <queries::$name<'tcx> as QueryAccessors<QueryCtxt<'tcx>>>::DEP_KIND,
+                        Query::$name,
+                        &mut jobs,
+                    )?;
+                )*
+
+                Some(jobs)
+            }
+        }
+
+        impl QueryEngine<'tcx> for Queries<'tcx> {
+            #[cfg(parallel_compiler)]
+            unsafe fn deadlock(&'tcx self, tcx: TyCtxt<'tcx>, registry: &rustc_rayon_core::Registry) {
+                let tcx = QueryCtxt { tcx, queries: self };
+                rustc_query_system::query::deadlock(tcx, registry)
+            }
+
+            fn encode_query_results(
+                &'tcx self,
+                tcx: TyCtxt<'tcx>,
+                encoder: &mut on_disk_cache::CacheEncoder<'a, 'tcx, opaque::FileEncoder>,
+                query_result_index: &mut on_disk_cache::EncodedQueryResultIndex,
+            ) -> opaque::FileEncodeResult {
+                let tcx = QueryCtxt { tcx, queries: self };
+                tcx.encode_query_results(encoder, query_result_index)
+            }
+
+            fn exec_cache_promotions(&'tcx self, tcx: TyCtxt<'tcx>) {
+                let tcx = QueryCtxt { tcx, queries: self };
+                tcx.dep_graph.exec_cache_promotions(tcx)
+            }
+
+            fn try_mark_green(&'tcx self, tcx: TyCtxt<'tcx>, dep_node: &dep_graph::DepNode) -> bool {
+                let qcx = QueryCtxt { tcx, queries: self };
+                tcx.dep_graph.try_mark_green(qcx, dep_node).is_some()
+            }
+
+            fn try_print_query_stack(
+                &'tcx self,
+                tcx: TyCtxt<'tcx>,
+                query: Option<QueryJobId<dep_graph::DepKind>>,
+                handler: &Handler,
+                num_frames: Option<usize>,
+            ) -> usize {
+                let query_map = self.try_collect_active_jobs();
+
+                let mut current_query = query;
+                let mut i = 0;
+
+                while let Some(query) = current_query {
+                    if Some(i) == num_frames {
+                        break;
+                    }
+                    let query_info = if let Some(info) = query_map.as_ref().and_then(|map| map.get(&query))
+                    {
+                        info
+                    } else {
+                        break;
+                    };
+                    let mut diag = Diagnostic::new(
+                        Level::FailureNote,
+                        &format!(
+                            "#{} [{}] {}",
+                            i,
+                            query_info.info.query.name(),
+                            query_info.info.query.describe(QueryCtxt { tcx, queries: self })
+                        ),
+                    );
+                    diag.span = tcx.sess.source_map().guess_head_span(query_info.info.span).into();
+                    handler.force_print_diagnostic(diag);
+
+                    current_query = query_info.job.parent;
+                    i += 1;
+                }
+
+                i
+            }
+
+            $($(#[$attr])*
+            #[inline(always)]
+            fn $name(
+                &'tcx self,
+                tcx: TyCtxt<$tcx>,
+                span: Span,
+                key: query_keys::$name<$tcx>,
+                lookup: QueryLookup,
+                mode: QueryMode,
+            ) -> Option<query_stored::$name<$tcx>> {
+                let qcx = QueryCtxt { tcx, queries: self };
+                get_query::<queries::$name<$tcx>, _>(qcx, span, key, lookup, mode)
+            })*
+        }
+    };
+}
+
+fn describe_as_module(def_id: LocalDefId, tcx: TyCtxt<'_>) -> String {
+    if def_id.is_top_level_module() {
+        "top-level module".to_string()
+    } else {
+        format!("module `{}`", tcx.def_path_str(def_id.to_def_id()))
+    }
+}
+
+rustc_query_description! {}
diff --git a/compiler/rustc_query_impl/src/profiling_support.rs b/compiler/rustc_query_impl/src/profiling_support.rs
new file mode 100644
index 00000000000..24485889731
--- /dev/null
+++ b/compiler/rustc_query_impl/src/profiling_support.rs
@@ -0,0 +1,320 @@
+use measureme::{StringComponent, StringId};
+use rustc_data_structures::fx::FxHashMap;
+use rustc_data_structures::profiling::SelfProfiler;
+use rustc_hir::def_id::{CrateNum, DefId, DefIndex, LocalDefId, CRATE_DEF_INDEX, LOCAL_CRATE};
+use rustc_hir::definitions::DefPathData;
+use rustc_middle::ty::{TyCtxt, WithOptConstParam};
+use rustc_query_system::query::{QueryCache, QueryCacheStore};
+use std::fmt::Debug;
+use std::io::Write;
+
+struct QueryKeyStringCache {
+    def_id_cache: FxHashMap<DefId, StringId>,
+}
+
+impl QueryKeyStringCache {
+    fn new() -> QueryKeyStringCache {
+        QueryKeyStringCache { def_id_cache: Default::default() }
+    }
+}
+
+struct QueryKeyStringBuilder<'p, 'c, 'tcx> {
+    profiler: &'p SelfProfiler,
+    tcx: TyCtxt<'tcx>,
+    string_cache: &'c mut QueryKeyStringCache,
+}
+
+impl<'p, 'c, 'tcx> QueryKeyStringBuilder<'p, 'c, 'tcx> {
+    fn new(
+        profiler: &'p SelfProfiler,
+        tcx: TyCtxt<'tcx>,
+        string_cache: &'c mut QueryKeyStringCache,
+    ) -> QueryKeyStringBuilder<'p, 'c, 'tcx> {
+        QueryKeyStringBuilder { profiler, tcx, string_cache }
+    }
+
+    // The current implementation is rather crude. In the future it might be a
+    // good idea to base this on `ty::print` in order to get nicer and more
+    // efficient query keys.
+    fn def_id_to_string_id(&mut self, def_id: DefId) -> StringId {
+        if let Some(&string_id) = self.string_cache.def_id_cache.get(&def_id) {
+            return string_id;
+        }
+
+        let def_key = self.tcx.def_key(def_id);
+
+        let (parent_string_id, start_index) = match def_key.parent {
+            Some(parent_index) => {
+                let parent_def_id = DefId { index: parent_index, krate: def_id.krate };
+
+                (self.def_id_to_string_id(parent_def_id), 0)
+            }
+            None => (StringId::INVALID, 2),
+        };
+
+        let dis_buffer = &mut [0u8; 16];
+        let crate_name;
+        let other_name;
+        let name;
+        let dis;
+        let end_index;
+
+        match def_key.disambiguated_data.data {
+            DefPathData::CrateRoot => {
+                crate_name = self.tcx.original_crate_name(def_id.krate).as_str();
+                name = &*crate_name;
+                dis = "";
+                end_index = 3;
+            }
+            other => {
+                other_name = other.to_string();
+                name = other_name.as_str();
+                if def_key.disambiguated_data.disambiguator == 0 {
+                    dis = "";
+                    end_index = 3;
+                } else {
+                    write!(&mut dis_buffer[..], "[{}]", def_key.disambiguated_data.disambiguator)
+                        .unwrap();
+                    let end_of_dis = dis_buffer.iter().position(|&c| c == b']').unwrap();
+                    dis = std::str::from_utf8(&dis_buffer[..end_of_dis + 1]).unwrap();
+                    end_index = 4;
+                }
+            }
+        }
+
+        let components = [
+            StringComponent::Ref(parent_string_id),
+            StringComponent::Value("::"),
+            StringComponent::Value(name),
+            StringComponent::Value(dis),
+        ];
+
+        let string_id = self.profiler.alloc_string(&components[start_index..end_index]);
+
+        self.string_cache.def_id_cache.insert(def_id, string_id);
+
+        string_id
+    }
+}
+
+trait IntoSelfProfilingString {
+    fn to_self_profile_string(&self, builder: &mut QueryKeyStringBuilder<'_, '_, '_>) -> StringId;
+}
+
+// The default implementation of `IntoSelfProfilingString` just uses `Debug`
+// which is slow and causes lots of duplication of string data.
+// The specialized impls below take care of making the `DefId` case more
+// efficient.
+impl<T: Debug> IntoSelfProfilingString for T {
+    default fn to_self_profile_string(
+        &self,
+        builder: &mut QueryKeyStringBuilder<'_, '_, '_>,
+    ) -> StringId {
+        let s = format!("{:?}", self);
+        builder.profiler.alloc_string(&s[..])
+    }
+}
+
+impl<T: SpecIntoSelfProfilingString> IntoSelfProfilingString for T {
+    fn to_self_profile_string(&self, builder: &mut QueryKeyStringBuilder<'_, '_, '_>) -> StringId {
+        self.spec_to_self_profile_string(builder)
+    }
+}
+
+#[rustc_specialization_trait]
+trait SpecIntoSelfProfilingString: Debug {
+    fn spec_to_self_profile_string(
+        &self,
+        builder: &mut QueryKeyStringBuilder<'_, '_, '_>,
+    ) -> StringId;
+}
+
+impl SpecIntoSelfProfilingString for DefId {
+    fn spec_to_self_profile_string(
+        &self,
+        builder: &mut QueryKeyStringBuilder<'_, '_, '_>,
+    ) -> StringId {
+        builder.def_id_to_string_id(*self)
+    }
+}
+
+impl SpecIntoSelfProfilingString for CrateNum {
+    fn spec_to_self_profile_string(
+        &self,
+        builder: &mut QueryKeyStringBuilder<'_, '_, '_>,
+    ) -> StringId {
+        builder.def_id_to_string_id(DefId { krate: *self, index: CRATE_DEF_INDEX })
+    }
+}
+
+impl SpecIntoSelfProfilingString for DefIndex {
+    fn spec_to_self_profile_string(
+        &self,
+        builder: &mut QueryKeyStringBuilder<'_, '_, '_>,
+    ) -> StringId {
+        builder.def_id_to_string_id(DefId { krate: LOCAL_CRATE, index: *self })
+    }
+}
+
+impl SpecIntoSelfProfilingString for LocalDefId {
+    fn spec_to_self_profile_string(
+        &self,
+        builder: &mut QueryKeyStringBuilder<'_, '_, '_>,
+    ) -> StringId {
+        builder.def_id_to_string_id(DefId { krate: LOCAL_CRATE, index: self.local_def_index })
+    }
+}
+
+impl<T: SpecIntoSelfProfilingString> SpecIntoSelfProfilingString for WithOptConstParam<T> {
+    fn spec_to_self_profile_string(
+        &self,
+        builder: &mut QueryKeyStringBuilder<'_, '_, '_>,
+    ) -> StringId {
+        // We print `WithOptConstParam` values as tuples to make them shorter
+        // and more readable, without losing information:
+        //
+        // "WithOptConstParam { did: foo::bar, const_param_did: Some(foo::baz) }"
+        // becomes "(foo::bar, foo::baz)" and
+        // "WithOptConstParam { did: foo::bar, const_param_did: None }"
+        // becomes "(foo::bar, _)".
+
+        let did = StringComponent::Ref(self.did.to_self_profile_string(builder));
+
+        let const_param_did = if let Some(const_param_did) = self.const_param_did {
+            let const_param_did = builder.def_id_to_string_id(const_param_did);
+            StringComponent::Ref(const_param_did)
+        } else {
+            StringComponent::Value("_")
+        };
+
+        let components = [
+            StringComponent::Value("("),
+            did,
+            StringComponent::Value(", "),
+            const_param_did,
+            StringComponent::Value(")"),
+        ];
+
+        builder.profiler.alloc_string(&components[..])
+    }
+}
+
+impl<T0, T1> SpecIntoSelfProfilingString for (T0, T1)
+where
+    T0: SpecIntoSelfProfilingString,
+    T1: SpecIntoSelfProfilingString,
+{
+    fn spec_to_self_profile_string(
+        &self,
+        builder: &mut QueryKeyStringBuilder<'_, '_, '_>,
+    ) -> StringId {
+        let val0 = self.0.to_self_profile_string(builder);
+        let val1 = self.1.to_self_profile_string(builder);
+
+        let components = &[
+            StringComponent::Value("("),
+            StringComponent::Ref(val0),
+            StringComponent::Value(","),
+            StringComponent::Ref(val1),
+            StringComponent::Value(")"),
+        ];
+
+        builder.profiler.alloc_string(components)
+    }
+}
+
+/// Allocate the self-profiling query strings for a single query cache. This
+/// method is called from `alloc_self_profile_query_strings` which knows all
+/// the queries via macro magic.
+fn alloc_self_profile_query_strings_for_query_cache<'tcx, C>(
+    tcx: TyCtxt<'tcx>,
+    query_name: &'static str,
+    query_cache: &QueryCacheStore<C>,
+    string_cache: &mut QueryKeyStringCache,
+) where
+    C: QueryCache,
+    C::Key: Debug + Clone,
+{
+    tcx.prof.with_profiler(|profiler| {
+        let event_id_builder = profiler.event_id_builder();
+
+        // Walk the entire query cache and allocate the appropriate
+        // string representations. Each cache entry is uniquely
+        // identified by its dep_node_index.
+        if profiler.query_key_recording_enabled() {
+            let mut query_string_builder = QueryKeyStringBuilder::new(profiler, tcx, string_cache);
+
+            let query_name = profiler.get_or_alloc_cached_string(query_name);
+
+            // Since building the string representation of query keys might
+            // need to invoke queries itself, we cannot keep the query caches
+            // locked while doing so. Instead we copy out the
+            // `(query_key, dep_node_index)` pairs and release the lock again.
+            let query_keys_and_indices: Vec<_> = query_cache
+                .iter_results(|results| results.map(|(k, _, i)| (k.clone(), i)).collect());
+
+            // Now actually allocate the strings. If allocating the strings
+            // generates new entries in the query cache, we'll miss them but
+            // we don't actually care.
+            for (query_key, dep_node_index) in query_keys_and_indices {
+                // Translate the DepNodeIndex into a QueryInvocationId
+                let query_invocation_id = dep_node_index.into();
+
+                // Create the string version of the query-key
+                let query_key = query_key.to_self_profile_string(&mut query_string_builder);
+                let event_id = event_id_builder.from_label_and_arg(query_name, query_key);
+
+                // Doing this in bulk might be a good idea:
+                profiler.map_query_invocation_id_to_string(
+                    query_invocation_id,
+                    event_id.to_string_id(),
+                );
+            }
+        } else {
+            // In this branch we don't allocate query keys
+            let query_name = profiler.get_or_alloc_cached_string(query_name);
+            let event_id = event_id_builder.from_label(query_name).to_string_id();
+
+            query_cache.iter_results(|results| {
+                let query_invocation_ids: Vec<_> = results.map(|v| v.2.into()).collect();
+
+                profiler.bulk_map_query_invocation_id_to_single_string(
+                    query_invocation_ids.into_iter(),
+                    event_id,
+                );
+            });
+        }
+    });
+}
+
+/// All self-profiling events generated by the query engine use
+/// virtual `StringId`s for their `event_id`. This method makes all
+/// those virtual `StringId`s point to actual strings.
+///
+/// If we are recording only summary data, the ids will point to
+/// just the query names. If we are recording query keys too, we
+/// allocate the corresponding strings here.
+pub fn alloc_self_profile_query_strings(tcx: TyCtxt<'tcx>) {
+    if !tcx.prof.enabled() {
+        return;
+    }
+
+    let mut string_cache = QueryKeyStringCache::new();
+
+    macro_rules! alloc_once {
+        (<$tcx:tt>
+            $($(#[$attr:meta])* [$($modifiers:tt)*] fn $name:ident($K:ty) -> $V:ty,)*
+        ) => {
+            $({
+                alloc_self_profile_query_strings_for_query_cache(
+                    tcx,
+                    stringify!($name),
+                    &tcx.query_caches.$name,
+                    &mut string_cache,
+                );
+            })*
+        }
+    }
+
+    rustc_query_append! { [alloc_once!][<'tcx>] }
+}
diff --git a/compiler/rustc_query_impl/src/stats.rs b/compiler/rustc_query_impl/src/stats.rs
new file mode 100644
index 00000000000..4d52483c3b8
--- /dev/null
+++ b/compiler/rustc_query_impl/src/stats.rs
@@ -0,0 +1,140 @@
+use rustc_hir::def_id::{DefId, LOCAL_CRATE};
+use rustc_middle::ty::query::query_storage;
+use rustc_middle::ty::TyCtxt;
+use rustc_query_system::query::{QueryCache, QueryCacheStore};
+
+use std::any::type_name;
+use std::mem;
+#[cfg(debug_assertions)]
+use std::sync::atomic::Ordering;
+
+trait KeyStats {
+    fn key_stats(&self, stats: &mut QueryStats);
+}
+
+impl<T> KeyStats for T {
+    default fn key_stats(&self, _: &mut QueryStats) {}
+}
+
+impl KeyStats for DefId {
+    fn key_stats(&self, stats: &mut QueryStats) {
+        if self.krate == LOCAL_CRATE {
+            stats.local_def_id_keys = Some(stats.local_def_id_keys.unwrap_or(0) + 1);
+        }
+    }
+}
+
+#[derive(Clone)]
+struct QueryStats {
+    name: &'static str,
+    cache_hits: usize,
+    key_size: usize,
+    key_type: &'static str,
+    value_size: usize,
+    value_type: &'static str,
+    entry_count: usize,
+    local_def_id_keys: Option<usize>,
+}
+
+fn stats<C>(name: &'static str, map: &QueryCacheStore<C>) -> QueryStats
+where
+    C: QueryCache,
+{
+    let mut stats = QueryStats {
+        name,
+        #[cfg(debug_assertions)]
+        cache_hits: map.cache_hits.load(Ordering::Relaxed),
+        #[cfg(not(debug_assertions))]
+        cache_hits: 0,
+        key_size: mem::size_of::<C::Key>(),
+        key_type: type_name::<C::Key>(),
+        value_size: mem::size_of::<C::Value>(),
+        value_type: type_name::<C::Value>(),
+        entry_count: map.iter_results(|results| results.count()),
+        local_def_id_keys: None,
+    };
+    map.iter_results(|results| {
+        for (key, _, _) in results {
+            key.key_stats(&mut stats)
+        }
+    });
+    stats
+}
+
+pub fn print_stats(tcx: TyCtxt<'_>) {
+    let queries = query_stats(tcx);
+
+    if cfg!(debug_assertions) {
+        let hits: usize = queries.iter().map(|s| s.cache_hits).sum();
+        let results: usize = queries.iter().map(|s| s.entry_count).sum();
+        eprintln!("\nQuery cache hit rate: {}", hits as f64 / (hits + results) as f64);
+    }
+
+    let mut query_key_sizes = queries.clone();
+    query_key_sizes.sort_by_key(|q| q.key_size);
+    eprintln!("\nLarge query keys:");
+    for q in query_key_sizes.iter().rev().filter(|q| q.key_size > 8) {
+        eprintln!("   {} - {} x {} - {}", q.name, q.key_size, q.entry_count, q.key_type);
+    }
+
+    let mut query_value_sizes = queries.clone();
+    query_value_sizes.sort_by_key(|q| q.value_size);
+    eprintln!("\nLarge query values:");
+    for q in query_value_sizes.iter().rev().filter(|q| q.value_size > 8) {
+        eprintln!("   {} - {} x {} - {}", q.name, q.value_size, q.entry_count, q.value_type);
+    }
+
+    if cfg!(debug_assertions) {
+        let mut query_cache_hits = queries.clone();
+        query_cache_hits.sort_by_key(|q| q.cache_hits);
+        eprintln!("\nQuery cache hits:");
+        for q in query_cache_hits.iter().rev() {
+            eprintln!(
+                "   {} - {} ({}%)",
+                q.name,
+                q.cache_hits,
+                q.cache_hits as f64 / (q.cache_hits + q.entry_count) as f64
+            );
+        }
+    }
+
+    let mut query_value_count = queries.clone();
+    query_value_count.sort_by_key(|q| q.entry_count);
+    eprintln!("\nQuery value count:");
+    for q in query_value_count.iter().rev() {
+        eprintln!("   {} - {}", q.name, q.entry_count);
+    }
+
+    let mut def_id_density: Vec<_> =
+        queries.iter().filter(|q| q.local_def_id_keys.is_some()).collect();
+    def_id_density.sort_by_key(|q| q.local_def_id_keys.unwrap());
+    eprintln!("\nLocal DefId density:");
+    let total = tcx.hir().definitions().def_index_count() as f64;
+    for q in def_id_density.iter().rev() {
+        let local = q.local_def_id_keys.unwrap();
+        eprintln!("   {} - {} = ({}%)", q.name, local, (local as f64 * 100.0) / total);
+    }
+}
+
+macro_rules! print_stats {
+    (<$tcx:tt>
+        $($(#[$attr:meta])* [$($modifiers:tt)*] fn $name:ident($K:ty) -> $V:ty,)*
+    ) => {
+        fn query_stats(tcx: TyCtxt<'_>) -> Vec<QueryStats> {
+            let mut queries = Vec::new();
+
+            $(
+                queries.push(stats::<
+                    query_storage::$name<'_>,
+                >(
+                    stringify!($name),
+                    &tcx.query_caches.$name,
+                ));
+            )*
+
+            queries
+        }
+    }
+}
+
+rustc_query_append! { [print_stats!][<'tcx>] }
diff --git a/compiler/rustc_query_impl/src/values.rs b/compiler/rustc_query_impl/src/values.rs
new file mode 100644
index 00000000000..003867beeb7
--- /dev/null
+++ b/compiler/rustc_query_impl/src/values.rs
@@ -0,0 +1,45 @@
+use super::QueryCtxt;
+use rustc_middle::ty::{self, AdtSizedConstraint, Ty, TyS};
+
+pub(super) trait Value<'tcx>: Sized {
+    fn from_cycle_error(tcx: QueryCtxt<'tcx>) -> Self;
+}
+
+impl<'tcx, T> Value<'tcx> for T {
+    default fn from_cycle_error(tcx: QueryCtxt<'tcx>) -> T {
+        tcx.sess.abort_if_errors();
+        bug!("Value::from_cycle_error called without errors");
+    }
+}
+
+impl<'tcx> Value<'tcx> for &'_ TyS<'_> {
+    fn from_cycle_error(tcx: QueryCtxt<'tcx>) -> Self {
+        // SAFETY: This is never called when `Self` is not `Ty<'tcx>`.
+        // FIXME: Represent the above fact in the trait system somehow.
+        unsafe { std::mem::transmute::<Ty<'tcx>, Ty<'_>>(tcx.ty_error()) }
+    }
+}
+
+impl<'tcx> Value<'tcx> for ty::SymbolName<'_> {
+    fn from_cycle_error(tcx: QueryCtxt<'tcx>) -> Self {
+        // SAFETY: This is never called when `Self` is not `SymbolName<'tcx>`.
+        // FIXME: Represent the above fact in the trait system somehow.
+        unsafe {
+            std::mem::transmute::<ty::SymbolName<'tcx>, ty::SymbolName<'_>>(ty::SymbolName::new(
+                *tcx, "<error>",
+            ))
+        }
+    }
+}
+
+impl<'tcx> Value<'tcx> for AdtSizedConstraint<'_> {
+    fn from_cycle_error(tcx: QueryCtxt<'tcx>) -> Self {
+        // SAFETY: This is never called when `Self` is not `AdtSizedConstraint<'tcx>`.
+        // FIXME: Represent the above fact in the trait system somehow.
+        unsafe {
+            std::mem::transmute::<AdtSizedConstraint<'tcx>, AdtSizedConstraint<'_>>(
+                AdtSizedConstraint(tcx.intern_type_list(&[tcx.ty_error()])),
+            )
+        }
+    }
+}