diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:02:58 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:02:58 +0000 |
commit | 698f8c2f01ea549d77d7dc3338a12e04c11057b9 (patch) | |
tree | 173a775858bd501c378080a10dca74132f05bc50 /compiler/rustc_middle/src/dep_graph | |
parent | Initial commit. (diff) | |
download | rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.tar.xz rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.zip |
Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | compiler/rustc_middle/src/dep_graph/dep_node.rs | 435 | ||||
-rw-r--r-- | compiler/rustc_middle/src/dep_graph/mod.rs | 140 |
2 files changed, 575 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) + } +} diff --git a/compiler/rustc_middle/src/dep_graph/mod.rs b/compiler/rustc_middle/src/dep_graph/mod.rs new file mode 100644 index 000000000..c8b3b52b0 --- /dev/null +++ b/compiler/rustc_middle/src/dep_graph/mod.rs @@ -0,0 +1,140 @@ +use crate::ty::{self, TyCtxt}; +use rustc_data_structures::profiling::SelfProfilerRef; +use rustc_query_system::ich::StableHashingContext; +use rustc_session::Session; + +#[macro_use] +mod dep_node; + +pub use rustc_query_system::dep_graph::{ + debug::DepNodeFilter, hash_result, DepContext, DepNodeColor, DepNodeIndex, + SerializedDepNodeIndex, WorkProduct, WorkProductId, +}; + +pub use dep_node::{label_strs, DepKind, DepKindStruct, DepNode, DepNodeExt}; +pub(crate) use dep_node::{make_compile_codegen_unit, make_compile_mono_item}; + +pub type DepGraph = rustc_query_system::dep_graph::DepGraph<DepKind>; +pub type TaskDeps = rustc_query_system::dep_graph::TaskDeps<DepKind>; +pub type TaskDepsRef<'a> = rustc_query_system::dep_graph::TaskDepsRef<'a, DepKind>; +pub type DepGraphQuery = rustc_query_system::dep_graph::DepGraphQuery<DepKind>; +pub type SerializedDepGraph = rustc_query_system::dep_graph::SerializedDepGraph<DepKind>; +pub type EdgeFilter = rustc_query_system::dep_graph::debug::EdgeFilter<DepKind>; + +impl rustc_query_system::dep_graph::DepKind for DepKind { + const NULL: Self = DepKind::Null; + const RED: Self = DepKind::Red; + + fn debug_node(node: &DepNode, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{:?}(", node.kind)?; + + ty::tls::with_opt(|opt_tcx| { + if let Some(tcx) = opt_tcx { + if let Some(def_id) = node.extract_def_id(tcx) { + write!(f, "{}", tcx.def_path_debug_str(def_id))?; + } else if let Some(ref s) = tcx.dep_graph.dep_node_debug_str(*node) { + write!(f, "{}", s)?; + } else { + write!(f, "{}", node.hash)?; + } + } else { + write!(f, "{}", node.hash)?; + } + Ok(()) + })?; + + write!(f, ")") + } + + fn with_deps<OP, R>(task_deps: TaskDepsRef<'_>, op: OP) -> R + where + OP: FnOnce() -> R, + { + ty::tls::with_context(|icx| { + let icx = ty::tls::ImplicitCtxt { task_deps, ..icx.clone() }; + + ty::tls::enter_context(&icx, |_| op()) + }) + } + + fn read_deps<OP>(op: OP) + where + OP: for<'a> FnOnce(TaskDepsRef<'a>), + { + ty::tls::with_context_opt(|icx| { + let Some(icx) = icx else { return }; + op(icx.task_deps) + }) + } +} + +impl<'tcx> DepContext for TyCtxt<'tcx> { + type DepKind = DepKind; + + #[inline] + fn with_stable_hashing_context<R>(&self, f: impl FnOnce(StableHashingContext<'_>) -> R) -> R { + TyCtxt::with_stable_hashing_context(*self, f) + } + + #[inline] + fn dep_graph(&self) -> &DepGraph { + &self.dep_graph + } + + #[inline(always)] + fn profiler(&self) -> &SelfProfilerRef { + &self.prof + } + + #[inline(always)] + fn sess(&self) -> &Session { + self.sess + } + + #[inline(always)] + fn fingerprint_style(&self, kind: DepKind) -> rustc_query_system::dep_graph::FingerprintStyle { + kind.fingerprint_style(*self) + } + + #[inline(always)] + fn is_eval_always(&self, kind: DepKind) -> bool { + self.query_kind(kind).is_eval_always + } + + fn try_force_from_dep_node(&self, dep_node: DepNode) -> bool { + 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 = self.query_kind(dep_node.kind); + if let Some(f) = cb.force_from_dep_node { + f(*self, dep_node); + true + } else { + false + } + } + + fn try_load_from_on_disk_cache(&self, dep_node: DepNode) { + let cb = self.query_kind(dep_node.kind); + if let Some(f) = cb.try_load_from_on_disk_cache { + f(*self, dep_node) + } + } +} |