diff options
Diffstat (limited to 'compiler/rustc_middle/src/dep_graph/dep_node.rs')
-rw-r--r-- | compiler/rustc_middle/src/dep_graph/dep_node.rs | 435 |
1 files changed, 435 insertions, 0 deletions
diff --git a/compiler/rustc_middle/src/dep_graph/dep_node.rs b/compiler/rustc_middle/src/dep_graph/dep_node.rs new file mode 100644 index 000000000..2d095438f --- /dev/null +++ b/compiler/rustc_middle/src/dep_graph/dep_node.rs @@ -0,0 +1,435 @@ +//! Nodes in the dependency graph. +//! +//! A node in the [dependency graph] is represented by a [`DepNode`]. +//! A `DepNode` consists of a [`DepKind`] (which +//! specifies the kind of thing it represents, like a piece of HIR, MIR, etc.) +//! and a [`Fingerprint`], a 128-bit hash value, the exact meaning of which +//! depends on the node's `DepKind`. Together, the kind and the fingerprint +//! fully identify a dependency node, even across multiple compilation sessions. +//! In other words, the value of the fingerprint does not depend on anything +//! that is specific to a given compilation session, like an unpredictable +//! interning key (e.g., `NodeId`, `DefId`, `Symbol`) or the numeric value of a +//! pointer. The concept behind this could be compared to how git commit hashes +//! uniquely identify a given commit. The fingerprinting approach has +//! a few advantages: +//! +//! * A `DepNode` can simply be serialized to disk and loaded in another session +//! without the need to do any "rebasing" (like we have to do for Spans and +//! NodeIds) or "retracing" (like we had to do for `DefId` in earlier +//! implementations of the dependency graph). +//! * A `Fingerprint` is just a bunch of bits, which allows `DepNode` to +//! implement `Copy`, `Sync`, `Send`, `Freeze`, etc. +//! * Since we just have a bit pattern, `DepNode` can be mapped from disk into +//! memory without any post-processing (e.g., "abomination-style" pointer +//! reconstruction). +//! * Because a `DepNode` is self-contained, we can instantiate `DepNodes` that +//! refer to things that do not exist anymore. In previous implementations +//! `DepNode` contained a `DefId`. A `DepNode` referring to something that +//! had been removed between the previous and the current compilation session +//! could not be instantiated because the current compilation session +//! contained no `DefId` for thing that had been removed. +//! +//! `DepNode` definition happens in the `define_dep_nodes!()` macro. This macro +//! defines the `DepKind` enum. Each `DepKind` has its own parameters that are +//! needed at runtime in order to construct a valid `DepNode` fingerprint. +//! However, only `CompileCodegenUnit` and `CompileMonoItem` are constructed +//! explicitly (with `make_compile_codegen_unit` cq `make_compile_mono_item`). +//! +//! Because the macro sees what parameters a given `DepKind` requires, it can +//! "infer" some properties for each kind of `DepNode`: +//! +//! * Whether a `DepNode` of a given kind has any parameters at all. Some +//! `DepNode`s could represent global concepts with only one value. +//! * Whether it is possible, in principle, to reconstruct a query key from a +//! given `DepNode`. Many `DepKind`s only require a single `DefId` parameter, +//! in which case it is possible to map the node's fingerprint back to the +//! `DefId` it was computed from. In other cases, too much information gets +//! lost during fingerprint computation. +//! +//! `make_compile_codegen_unit` and `make_compile_mono_items`, together with +//! `DepNode::new()`, ensures that only valid `DepNode` instances can be +//! constructed. For example, the API does not allow for constructing +//! parameterless `DepNode`s with anything other than a zeroed out fingerprint. +//! More generally speaking, it relieves the user of the `DepNode` API of +//! having to know how to compute the expected fingerprint for a given set of +//! node parameters. +//! +//! [dependency graph]: https://rustc-dev-guide.rust-lang.org/query.html + +use crate::mir::mono::MonoItem; +use crate::ty::TyCtxt; + +use rustc_data_structures::fingerprint::Fingerprint; +use rustc_hir::def_id::{CrateNum, DefId, LocalDefId}; +use rustc_hir::definitions::DefPathHash; +use rustc_hir::HirId; +use rustc_query_system::dep_graph::FingerprintStyle; +use rustc_span::symbol::Symbol; +use std::hash::Hash; + +pub use rustc_query_system::dep_graph::{DepContext, DepNodeParams}; + +/// This struct stores metadata about each DepKind. +/// +/// Information is retrieved by indexing the `DEP_KINDS` array using the integer value +/// of the `DepKind`. Overall, this allows to implement `DepContext` using this manual +/// jump table instead of large matches. +pub struct DepKindStruct { + /// Anonymous queries cannot be replayed from one compiler invocation to the next. + /// When their result is needed, it is recomputed. They are useful for fine-grained + /// dependency tracking, and caching within one compiler invocation. + pub is_anon: bool, + + /// Eval-always queries do not track their dependencies, and are always recomputed, even if + /// their inputs have not changed since the last compiler invocation. The result is still + /// cached within one compiler invocation. + pub is_eval_always: bool, + + /// Whether the query key can be recovered from the hashed fingerprint. + /// See [DepNodeParams] trait for the behaviour of each key type. + pub fingerprint_style: FingerprintStyle, + + /// 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`. + pub force_from_dep_node: Option<fn(tcx: TyCtxt<'_>, dep_node: DepNode) -> bool>, + + /// Invoke a query to put the on-disk cached value in memory. + pub try_load_from_on_disk_cache: Option<fn(TyCtxt<'_>, DepNode)>, +} + +impl DepKind { + #[inline(always)] + pub fn fingerprint_style(self, tcx: TyCtxt<'_>) -> FingerprintStyle { + // Only fetch the DepKindStruct once. + let data = tcx.query_kind(self); + if data.is_anon { + return FingerprintStyle::Opaque; + } + data.fingerprint_style + } +} + +macro_rules! define_dep_nodes { + (<$tcx:tt> + $( + [$($attrs:tt)*] + $variant:ident $(( $tuple_arg_ty:ty $(,)? ))* + ,)* + ) => ( + #[macro_export] + macro_rules! make_dep_kind_array { + ($mod:ident) => {[ $($mod::$variant()),* ]}; + } + + /// This enum serves as an index into arrays built by `make_dep_kind_array`. + #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Encodable, Decodable)] + #[allow(non_camel_case_types)] + pub enum DepKind { + $($variant),* + } + + fn dep_kind_from_label_string(label: &str) -> Result<DepKind, ()> { + match label { + $(stringify!($variant) => Ok(DepKind::$variant),)* + _ => Err(()), + } + } + + /// Contains variant => str representations for constructing + /// DepNode groups for tests. + #[allow(dead_code, non_upper_case_globals)] + pub mod label_strs { + $( + pub const $variant: &str = stringify!($variant); + )* + } + ); +} + +rustc_dep_node_append!([define_dep_nodes!][ <'tcx> + // We use this for most things when incr. comp. is turned off. + [] Null, + + // We use this to create a forever-red node. + [] Red, + + [anon] TraitSelect, + + // WARNING: if `Symbol` is changed, make sure you update `make_compile_codegen_unit` below. + [] CompileCodegenUnit(Symbol), + + // WARNING: if `MonoItem` is changed, make sure you update `make_compile_mono_item` below. + // Only used by rustc_codegen_cranelift + [] CompileMonoItem(MonoItem), +]); + +// WARNING: `construct` is generic and does not know that `CompileCodegenUnit` takes `Symbol`s as keys. +// Be very careful changing this type signature! +pub(crate) fn make_compile_codegen_unit(tcx: TyCtxt<'_>, name: Symbol) -> DepNode { + DepNode::construct(tcx, DepKind::CompileCodegenUnit, &name) +} + +// WARNING: `construct` is generic and does not know that `CompileMonoItem` takes `MonoItem`s as keys. +// Be very careful changing this type signature! +pub(crate) fn make_compile_mono_item<'tcx>( + tcx: TyCtxt<'tcx>, + mono_item: &MonoItem<'tcx>, +) -> DepNode { + DepNode::construct(tcx, DepKind::CompileMonoItem, mono_item) +} + +pub type DepNode = rustc_query_system::dep_graph::DepNode<DepKind>; + +// We keep a lot of `DepNode`s in memory during compilation. It's not +// required that their size stay the same, but we don't want to change +// it inadvertently. This assert just ensures we're aware of any change. +#[cfg(any(target_arch = "x86", target_arch = "x86_64"))] +static_assert_size!(DepNode, 18); + +#[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))] +static_assert_size!(DepNode, 24); + +pub trait DepNodeExt: Sized { + /// Construct a DepNode from the given DepKind and DefPathHash. This + /// method will assert that the given DepKind actually requires a + /// single DefId/DefPathHash parameter. + fn from_def_path_hash(tcx: TyCtxt<'_>, def_path_hash: DefPathHash, kind: DepKind) -> Self; + + /// Extracts the DefId corresponding to this DepNode. This will work + /// if two conditions are met: + /// + /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and + /// 2. the item that the DefPath refers to exists in the current tcx. + /// + /// Condition (1) is determined by the DepKind variant of the + /// DepNode. Condition (2) might not be fulfilled if a DepNode + /// refers to something from the previous compilation session that + /// has been removed. + fn extract_def_id(&self, tcx: TyCtxt<'_>) -> Option<DefId>; + + /// Used in testing + fn from_label_string( + tcx: TyCtxt<'_>, + label: &str, + def_path_hash: DefPathHash, + ) -> Result<Self, ()>; + + /// Used in testing + fn has_label_string(label: &str) -> bool; +} + +impl DepNodeExt for DepNode { + /// Construct a DepNode from the given DepKind and DefPathHash. This + /// method will assert that the given DepKind actually requires a + /// single DefId/DefPathHash parameter. + fn from_def_path_hash(tcx: TyCtxt<'_>, def_path_hash: DefPathHash, kind: DepKind) -> DepNode { + debug_assert!(kind.fingerprint_style(tcx) == FingerprintStyle::DefPathHash); + DepNode { kind, hash: def_path_hash.0.into() } + } + + /// Extracts the DefId corresponding to this DepNode. This will work + /// if two conditions are met: + /// + /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and + /// 2. the item that the DefPath refers to exists in the current tcx. + /// + /// Condition (1) is determined by the DepKind variant of the + /// DepNode. Condition (2) might not be fulfilled if a DepNode + /// refers to something from the previous compilation session that + /// has been removed. + fn extract_def_id<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Option<DefId> { + if self.kind.fingerprint_style(tcx) == FingerprintStyle::DefPathHash { + Some(tcx.def_path_hash_to_def_id(DefPathHash(self.hash.into()), &mut || { + panic!("Failed to extract DefId: {:?} {}", self.kind, self.hash) + })) + } else { + None + } + } + + /// Used in testing + fn from_label_string( + tcx: TyCtxt<'_>, + label: &str, + def_path_hash: DefPathHash, + ) -> Result<DepNode, ()> { + let kind = dep_kind_from_label_string(label)?; + + match kind.fingerprint_style(tcx) { + FingerprintStyle::Opaque => Err(()), + FingerprintStyle::Unit => Ok(DepNode::new_no_params(tcx, kind)), + FingerprintStyle::DefPathHash => { + Ok(DepNode::from_def_path_hash(tcx, def_path_hash, kind)) + } + } + } + + /// Used in testing + fn has_label_string(label: &str) -> bool { + dep_kind_from_label_string(label).is_ok() + } +} + +impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for () { + #[inline(always)] + fn fingerprint_style() -> FingerprintStyle { + FingerprintStyle::Unit + } + + #[inline(always)] + fn to_fingerprint(&self, _: TyCtxt<'tcx>) -> Fingerprint { + Fingerprint::ZERO + } + + #[inline(always)] + fn recover(_: TyCtxt<'tcx>, _: &DepNode) -> Option<Self> { + Some(()) + } +} + +impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for DefId { + #[inline(always)] + fn fingerprint_style() -> FingerprintStyle { + FingerprintStyle::DefPathHash + } + + #[inline(always)] + fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { + tcx.def_path_hash(*self).0 + } + + #[inline(always)] + fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { + tcx.def_path_str(*self) + } + + #[inline(always)] + fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> { + dep_node.extract_def_id(tcx) + } +} + +impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for LocalDefId { + #[inline(always)] + fn fingerprint_style() -> FingerprintStyle { + FingerprintStyle::DefPathHash + } + + #[inline(always)] + fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { + self.to_def_id().to_fingerprint(tcx) + } + + #[inline(always)] + fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { + self.to_def_id().to_debug_str(tcx) + } + + #[inline(always)] + fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> { + dep_node.extract_def_id(tcx).map(|id| id.expect_local()) + } +} + +impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for CrateNum { + #[inline(always)] + fn fingerprint_style() -> FingerprintStyle { + FingerprintStyle::DefPathHash + } + + #[inline(always)] + fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { + let def_id = self.as_def_id(); + def_id.to_fingerprint(tcx) + } + + #[inline(always)] + fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { + tcx.crate_name(*self).to_string() + } + + #[inline(always)] + fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> { + dep_node.extract_def_id(tcx).map(|id| id.krate) + } +} + +impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for (DefId, DefId) { + #[inline(always)] + fn fingerprint_style() -> FingerprintStyle { + FingerprintStyle::Opaque + } + + // We actually would not need to specialize the implementation of this + // method but it's faster to combine the hashes than to instantiate a full + // hashing context and stable-hashing state. + #[inline(always)] + fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { + let (def_id_0, def_id_1) = *self; + + let def_path_hash_0 = tcx.def_path_hash(def_id_0); + let def_path_hash_1 = tcx.def_path_hash(def_id_1); + + def_path_hash_0.0.combine(def_path_hash_1.0) + } + + #[inline(always)] + fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { + let (def_id_0, def_id_1) = *self; + + format!("({}, {})", tcx.def_path_debug_str(def_id_0), tcx.def_path_debug_str(def_id_1)) + } +} + +impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for HirId { + #[inline(always)] + fn fingerprint_style() -> FingerprintStyle { + FingerprintStyle::Opaque + } + + // We actually would not need to specialize the implementation of this + // method but it's faster to combine the hashes than to instantiate a full + // hashing context and stable-hashing state. + #[inline(always)] + fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { + let HirId { owner, local_id } = *self; + + let def_path_hash = tcx.def_path_hash(owner.to_def_id()); + let local_id = Fingerprint::from_smaller_hash(local_id.as_u32().into()); + + def_path_hash.0.combine(local_id) + } +} |