diff options
Diffstat (limited to 'compiler/rustc_query_system/src/dep_graph/graph.rs')
| -rw-r--r-- | compiler/rustc_query_system/src/dep_graph/graph.rs | 1288 |
1 files changed, 1288 insertions, 0 deletions
diff --git a/compiler/rustc_query_system/src/dep_graph/graph.rs b/compiler/rustc_query_system/src/dep_graph/graph.rs new file mode 100644 index 000000000..8ff561327 --- /dev/null +++ b/compiler/rustc_query_system/src/dep_graph/graph.rs @@ -0,0 +1,1288 @@ +use parking_lot::Mutex; +use rustc_data_structures::fingerprint::Fingerprint; +use rustc_data_structures::fx::{FxHashMap, FxHashSet}; +use rustc_data_structures::profiling::{EventId, QueryInvocationId, SelfProfilerRef}; +use rustc_data_structures::sharded::{self, Sharded}; +use rustc_data_structures::stable_hasher::{HashStable, StableHasher}; +use rustc_data_structures::steal::Steal; +use rustc_data_structures::sync::{AtomicU32, AtomicU64, Lock, Lrc, Ordering}; +use rustc_index::vec::IndexVec; +use rustc_serialize::opaque::{FileEncodeResult, FileEncoder}; +use smallvec::{smallvec, SmallVec}; +use std::assert_matches::assert_matches; +use std::collections::hash_map::Entry; +use std::fmt::Debug; +use std::hash::Hash; +use std::marker::PhantomData; +use std::sync::atomic::Ordering::Relaxed; + +use super::query::DepGraphQuery; +use super::serialized::{GraphEncoder, SerializedDepGraph, SerializedDepNodeIndex}; +use super::{DepContext, DepKind, DepNode, HasDepContext, WorkProductId}; +use crate::ich::StableHashingContext; +use crate::query::{QueryContext, QuerySideEffects}; + +#[cfg(debug_assertions)] +use {super::debug::EdgeFilter, std::env}; + +#[derive(Clone)] +pub struct DepGraph<K: DepKind> { + data: Option<Lrc<DepGraphData<K>>>, + + /// This field is used for assigning DepNodeIndices when running in + /// non-incremental mode. Even in non-incremental mode we make sure that + /// each task has a `DepNodeIndex` that uniquely identifies it. This unique + /// ID is used for self-profiling. + virtual_dep_node_index: Lrc<AtomicU32>, +} + +rustc_index::newtype_index! { + pub struct DepNodeIndex { .. } +} + +impl DepNodeIndex { + pub const INVALID: DepNodeIndex = DepNodeIndex::MAX; + pub const SINGLETON_DEPENDENCYLESS_ANON_NODE: DepNodeIndex = DepNodeIndex::from_u32(0); + pub const FOREVER_RED_NODE: DepNodeIndex = DepNodeIndex::from_u32(1); +} + +impl std::convert::From<DepNodeIndex> for QueryInvocationId { + #[inline] + fn from(dep_node_index: DepNodeIndex) -> Self { + QueryInvocationId(dep_node_index.as_u32()) + } +} + +#[derive(PartialEq)] +pub enum DepNodeColor { + Red, + Green(DepNodeIndex), +} + +impl DepNodeColor { + #[inline] + pub fn is_green(self) -> bool { + match self { + DepNodeColor::Red => false, + DepNodeColor::Green(_) => true, + } + } +} + +struct DepGraphData<K: DepKind> { + /// The new encoding of the dependency graph, optimized for red/green + /// tracking. The `current` field is the dependency graph of only the + /// current compilation session: We don't merge the previous dep-graph into + /// current one anymore, but we do reference shared data to save space. + current: CurrentDepGraph<K>, + + /// The dep-graph from the previous compilation session. It contains all + /// nodes and edges as well as all fingerprints of nodes that have them. + previous: SerializedDepGraph<K>, + + colors: DepNodeColorMap, + + processed_side_effects: Mutex<FxHashSet<DepNodeIndex>>, + + /// When we load, there may be `.o` files, cached MIR, or other such + /// things available to us. If we find that they are not dirty, we + /// load the path to the file storing those work-products here into + /// this map. We can later look for and extract that data. + previous_work_products: FxHashMap<WorkProductId, WorkProduct>, + + dep_node_debug: Lock<FxHashMap<DepNode<K>, String>>, + + /// Used by incremental compilation tests to assert that + /// a particular query result was decoded from disk + /// (not just marked green) + debug_loaded_from_disk: Lock<FxHashSet<DepNode<K>>>, +} + +pub fn hash_result<R>(hcx: &mut StableHashingContext<'_>, result: &R) -> Fingerprint +where + R: for<'a> HashStable<StableHashingContext<'a>>, +{ + let mut stable_hasher = StableHasher::new(); + result.hash_stable(hcx, &mut stable_hasher); + stable_hasher.finish() +} + +impl<K: DepKind> DepGraph<K> { + pub fn new( + profiler: &SelfProfilerRef, + prev_graph: SerializedDepGraph<K>, + prev_work_products: FxHashMap<WorkProductId, WorkProduct>, + encoder: FileEncoder, + record_graph: bool, + record_stats: bool, + ) -> DepGraph<K> { + let prev_graph_node_count = prev_graph.node_count(); + + let current = CurrentDepGraph::new( + profiler, + prev_graph_node_count, + encoder, + record_graph, + record_stats, + ); + + let colors = DepNodeColorMap::new(prev_graph_node_count); + + // Instantiate a dependy-less node only once for anonymous queries. + let _green_node_index = current.intern_new_node( + profiler, + DepNode { kind: DepKind::NULL, hash: current.anon_id_seed.into() }, + smallvec![], + Fingerprint::ZERO, + ); + assert_eq!(_green_node_index, DepNodeIndex::SINGLETON_DEPENDENCYLESS_ANON_NODE); + + // Instantiate a dependy-less red node only once for anonymous queries. + let (_red_node_index, _prev_and_index) = current.intern_node( + profiler, + &prev_graph, + DepNode { kind: DepKind::RED, hash: Fingerprint::ZERO.into() }, + smallvec![], + None, + false, + ); + assert_eq!(_red_node_index, DepNodeIndex::FOREVER_RED_NODE); + assert!(matches!(_prev_and_index, None | Some((_, DepNodeColor::Red)))); + + DepGraph { + data: Some(Lrc::new(DepGraphData { + previous_work_products: prev_work_products, + dep_node_debug: Default::default(), + current, + processed_side_effects: Default::default(), + previous: prev_graph, + colors, + debug_loaded_from_disk: Default::default(), + })), + virtual_dep_node_index: Lrc::new(AtomicU32::new(0)), + } + } + + pub fn new_disabled() -> DepGraph<K> { + DepGraph { data: None, virtual_dep_node_index: Lrc::new(AtomicU32::new(0)) } + } + + /// Returns `true` if we are actually building the full dep-graph, and `false` otherwise. + #[inline] + pub fn is_fully_enabled(&self) -> bool { + self.data.is_some() + } + + pub fn with_query(&self, f: impl Fn(&DepGraphQuery<K>)) { + if let Some(data) = &self.data { + data.current.encoder.borrow().with_query(f) + } + } + + pub fn assert_ignored(&self) { + if let Some(..) = self.data { + K::read_deps(|task_deps| { + assert_matches!( + task_deps, + TaskDepsRef::Ignore, + "expected no task dependency tracking" + ); + }) + } + } + + pub fn with_ignore<OP, R>(&self, op: OP) -> R + where + OP: FnOnce() -> R, + { + K::with_deps(TaskDepsRef::Ignore, op) + } + + /// Used to wrap the deserialization of a query result from disk, + /// This method enforces that no new `DepNodes` are created during + /// query result deserialization. + /// + /// Enforcing this makes the query dep graph simpler - all nodes + /// must be created during the query execution, and should be + /// created from inside the 'body' of a query (the implementation + /// provided by a particular compiler crate). + /// + /// Consider the case of three queries `A`, `B`, and `C`, where + /// `A` invokes `B` and `B` invokes `C`: + /// + /// `A -> B -> C` + /// + /// Suppose that decoding the result of query `B` required re-computing + /// the query `C`. If we did not create a fresh `TaskDeps` when + /// decoding `B`, we would still be using the `TaskDeps` for query `A` + /// (if we needed to re-execute `A`). This would cause us to create + /// a new edge `A -> C`. If this edge did not previously + /// exist in the `DepGraph`, then we could end up with a different + /// `DepGraph` at the end of compilation, even if there were no + /// meaningful changes to the overall program (e.g. a newline was added). + /// In addition, this edge might cause a subsequent compilation run + /// to try to force `C` before marking other necessary nodes green. If + /// `C` did not exist in the new compilation session, then we could + /// get an ICE. Normally, we would have tried (and failed) to mark + /// some other query green (e.g. `item_children`) which was used + /// to obtain `C`, which would prevent us from ever trying to force + /// a non-existent `D`. + /// + /// It might be possible to enforce that all `DepNode`s read during + /// deserialization already exist in the previous `DepGraph`. In + /// the above example, we would invoke `D` during the deserialization + /// of `B`. Since we correctly create a new `TaskDeps` from the decoding + /// of `B`, this would result in an edge `B -> D`. If that edge already + /// existed (with the same `DepPathHash`es), then it should be correct + /// to allow the invocation of the query to proceed during deserialization + /// of a query result. We would merely assert that the dep-graph fragment + /// that would have been added by invoking `C` while decoding `B` + /// is equivalent to the dep-graph fragment that we already instantiated for B + /// (at the point where we successfully marked B as green). + /// + /// However, this would require additional complexity + /// in the query infrastructure, and is not currently needed by the + /// decoding of any query results. Should the need arise in the future, + /// we should consider extending the query system with this functionality. + pub fn with_query_deserialization<OP, R>(&self, op: OP) -> R + where + OP: FnOnce() -> R, + { + K::with_deps(TaskDepsRef::Forbid, op) + } + + /// Starts a new dep-graph task. Dep-graph tasks are specified + /// using a free function (`task`) and **not** a closure -- this + /// is intentional because we want to exercise tight control over + /// what state they have access to. In particular, we want to + /// prevent implicit 'leaks' of tracked state into the task (which + /// could then be read without generating correct edges in the + /// dep-graph -- see the [rustc dev guide] for more details on + /// the dep-graph). To this end, the task function gets exactly two + /// pieces of state: the context `cx` and an argument `arg`. Both + /// of these bits of state must be of some type that implements + /// `DepGraphSafe` and hence does not leak. + /// + /// The choice of two arguments is not fundamental. One argument + /// would work just as well, since multiple values can be + /// collected using tuples. However, using two arguments works out + /// to be quite convenient, since it is common to need a context + /// (`cx`) and some argument (e.g., a `DefId` identifying what + /// item to process). + /// + /// For cases where you need some other number of arguments: + /// + /// - If you only need one argument, just use `()` for the `arg` + /// parameter. + /// - If you need 3+ arguments, use a tuple for the + /// `arg` parameter. + /// + /// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/incremental-compilation.html + pub fn with_task<Ctxt: HasDepContext<DepKind = K>, A: Debug, R>( + &self, + key: DepNode<K>, + cx: Ctxt, + arg: A, + task: fn(Ctxt, A) -> R, + hash_result: Option<fn(&mut StableHashingContext<'_>, &R) -> Fingerprint>, + ) -> (R, DepNodeIndex) { + if self.is_fully_enabled() { + self.with_task_impl(key, cx, arg, task, hash_result) + } else { + // Incremental compilation is turned off. We just execute the task + // without tracking. We still provide a dep-node index that uniquely + // identifies the task so that we have a cheap way of referring to + // the query for self-profiling. + (task(cx, arg), self.next_virtual_depnode_index()) + } + } + + fn with_task_impl<Ctxt: HasDepContext<DepKind = K>, A: Debug, R>( + &self, + key: DepNode<K>, + cx: Ctxt, + arg: A, + task: fn(Ctxt, A) -> R, + hash_result: Option<fn(&mut StableHashingContext<'_>, &R) -> Fingerprint>, + ) -> (R, DepNodeIndex) { + // This function is only called when the graph is enabled. + let data = self.data.as_ref().unwrap(); + + // If the following assertion triggers, it can have two reasons: + // 1. Something is wrong with DepNode creation, either here or + // in `DepGraph::try_mark_green()`. + // 2. Two distinct query keys get mapped to the same `DepNode` + // (see for example #48923). + assert!( + !self.dep_node_exists(&key), + "forcing query with already existing `DepNode`\n\ + - query-key: {:?}\n\ + - dep-node: {:?}", + arg, + key + ); + + let task_deps = if cx.dep_context().is_eval_always(key.kind) { + None + } else { + Some(Lock::new(TaskDeps { + #[cfg(debug_assertions)] + node: Some(key), + reads: SmallVec::new(), + read_set: Default::default(), + phantom_data: PhantomData, + })) + }; + + let task_deps_ref = match &task_deps { + Some(deps) => TaskDepsRef::Allow(deps), + None => TaskDepsRef::Ignore, + }; + + let result = K::with_deps(task_deps_ref, || task(cx, arg)); + let edges = task_deps.map_or_else(|| smallvec![], |lock| lock.into_inner().reads); + + let dcx = cx.dep_context(); + let hashing_timer = dcx.profiler().incr_result_hashing(); + let current_fingerprint = + hash_result.map(|f| dcx.with_stable_hashing_context(|mut hcx| f(&mut hcx, &result))); + + let print_status = cfg!(debug_assertions) && dcx.sess().opts.unstable_opts.dep_tasks; + + // Intern the new `DepNode`. + let (dep_node_index, prev_and_color) = data.current.intern_node( + dcx.profiler(), + &data.previous, + key, + edges, + current_fingerprint, + print_status, + ); + + hashing_timer.finish_with_query_invocation_id(dep_node_index.into()); + + if let Some((prev_index, color)) = prev_and_color { + debug_assert!( + data.colors.get(prev_index).is_none(), + "DepGraph::with_task() - Duplicate DepNodeColor \ + insertion for {:?}", + key + ); + + data.colors.insert(prev_index, color); + } + + (result, dep_node_index) + } + + /// Executes something within an "anonymous" task, that is, a task the + /// `DepNode` of which is determined by the list of inputs it read from. + pub fn with_anon_task<Ctxt: DepContext<DepKind = K>, OP, R>( + &self, + cx: Ctxt, + dep_kind: K, + op: OP, + ) -> (R, DepNodeIndex) + where + OP: FnOnce() -> R, + { + debug_assert!(!cx.is_eval_always(dep_kind)); + + if let Some(ref data) = self.data { + let task_deps = Lock::new(TaskDeps::default()); + let result = K::with_deps(TaskDepsRef::Allow(&task_deps), op); + let task_deps = task_deps.into_inner(); + let task_deps = task_deps.reads; + + let dep_node_index = match task_deps.len() { + 0 => { + // Because the dep-node id of anon nodes is computed from the sets of its + // dependencies we already know what the ID of this dependency-less node is + // going to be (i.e. equal to the precomputed + // `SINGLETON_DEPENDENCYLESS_ANON_NODE`). As a consequence we can skip creating + // a `StableHasher` and sending the node through interning. + DepNodeIndex::SINGLETON_DEPENDENCYLESS_ANON_NODE + } + 1 => { + // When there is only one dependency, don't bother creating a node. + task_deps[0] + } + _ => { + // The dep node indices are hashed here instead of hashing the dep nodes of the + // dependencies. These indices may refer to different nodes per session, but this isn't + // a problem here because we that ensure the final dep node hash is per session only by + // combining it with the per session random number `anon_id_seed`. This hash only need + // to map the dependencies to a single value on a per session basis. + let mut hasher = StableHasher::new(); + task_deps.hash(&mut hasher); + + let target_dep_node = DepNode { + kind: dep_kind, + // Fingerprint::combine() is faster than sending Fingerprint + // through the StableHasher (at least as long as StableHasher + // is so slow). + hash: data.current.anon_id_seed.combine(hasher.finish()).into(), + }; + + data.current.intern_new_node( + cx.profiler(), + target_dep_node, + task_deps, + Fingerprint::ZERO, + ) + } + }; + + (result, dep_node_index) + } else { + (op(), self.next_virtual_depnode_index()) + } + } + + #[inline] + pub fn read_index(&self, dep_node_index: DepNodeIndex) { + if let Some(ref data) = self.data { + K::read_deps(|task_deps| { + let mut task_deps = match task_deps { + TaskDepsRef::Allow(deps) => deps.lock(), + TaskDepsRef::Ignore => return, + TaskDepsRef::Forbid => { + panic!("Illegal read of: {:?}", dep_node_index) + } + }; + let task_deps = &mut *task_deps; + + if cfg!(debug_assertions) { + data.current.total_read_count.fetch_add(1, Relaxed); + } + + // As long as we only have a low number of reads we can avoid doing a hash + // insert and potentially allocating/reallocating the hashmap + let new_read = if task_deps.reads.len() < TASK_DEPS_READS_CAP { + task_deps.reads.iter().all(|other| *other != dep_node_index) + } else { + task_deps.read_set.insert(dep_node_index) + }; + if new_read { + task_deps.reads.push(dep_node_index); + if task_deps.reads.len() == TASK_DEPS_READS_CAP { + // Fill `read_set` with what we have so far so we can use the hashset + // next time + task_deps.read_set.extend(task_deps.reads.iter().copied()); + } + + #[cfg(debug_assertions)] + { + if let Some(target) = task_deps.node { + if let Some(ref forbidden_edge) = data.current.forbidden_edge { + let src = forbidden_edge.index_to_node.lock()[&dep_node_index]; + if forbidden_edge.test(&src, &target) { + panic!("forbidden edge {:?} -> {:?} created", src, target) + } + } + } + } + } else if cfg!(debug_assertions) { + data.current.total_duplicate_read_count.fetch_add(1, Relaxed); + } + }) + } + } + + #[inline] + pub fn dep_node_index_of(&self, dep_node: &DepNode<K>) -> DepNodeIndex { + self.dep_node_index_of_opt(dep_node).unwrap() + } + + #[inline] + pub fn dep_node_index_of_opt(&self, dep_node: &DepNode<K>) -> Option<DepNodeIndex> { + let data = self.data.as_ref().unwrap(); + let current = &data.current; + + if let Some(prev_index) = data.previous.node_to_index_opt(dep_node) { + current.prev_index_to_index.lock()[prev_index] + } else { + current.new_node_to_index.get_shard_by_value(dep_node).lock().get(dep_node).copied() + } + } + + #[inline] + pub fn dep_node_exists(&self, dep_node: &DepNode<K>) -> bool { + self.data.is_some() && self.dep_node_index_of_opt(dep_node).is_some() + } + + pub fn prev_fingerprint_of(&self, dep_node: &DepNode<K>) -> Option<Fingerprint> { + self.data.as_ref().unwrap().previous.fingerprint_of(dep_node) + } + + /// Checks whether a previous work product exists for `v` and, if + /// so, return the path that leads to it. Used to skip doing work. + pub fn previous_work_product(&self, v: &WorkProductId) -> Option<WorkProduct> { + self.data.as_ref().and_then(|data| data.previous_work_products.get(v).cloned()) + } + + /// Access the map of work-products created during the cached run. Only + /// used during saving of the dep-graph. + pub fn previous_work_products(&self) -> &FxHashMap<WorkProductId, WorkProduct> { + &self.data.as_ref().unwrap().previous_work_products + } + + pub fn mark_debug_loaded_from_disk(&self, dep_node: DepNode<K>) { + self.data.as_ref().unwrap().debug_loaded_from_disk.lock().insert(dep_node); + } + + pub fn debug_was_loaded_from_disk(&self, dep_node: DepNode<K>) -> bool { + self.data.as_ref().unwrap().debug_loaded_from_disk.lock().contains(&dep_node) + } + + #[inline(always)] + pub fn register_dep_node_debug_str<F>(&self, dep_node: DepNode<K>, debug_str_gen: F) + where + F: FnOnce() -> String, + { + let dep_node_debug = &self.data.as_ref().unwrap().dep_node_debug; + + if dep_node_debug.borrow().contains_key(&dep_node) { + return; + } + let debug_str = debug_str_gen(); + dep_node_debug.borrow_mut().insert(dep_node, debug_str); + } + + pub fn dep_node_debug_str(&self, dep_node: DepNode<K>) -> Option<String> { + self.data.as_ref()?.dep_node_debug.borrow().get(&dep_node).cloned() + } + + fn node_color(&self, dep_node: &DepNode<K>) -> Option<DepNodeColor> { + if let Some(ref data) = self.data { + if let Some(prev_index) = data.previous.node_to_index_opt(dep_node) { + return data.colors.get(prev_index); + } else { + // This is a node that did not exist in the previous compilation session. + return None; + } + } + + None + } + + /// Try to mark a node index for the node dep_node. + /// + /// A node will have an index, when it's already been marked green, or when we can mark it + /// green. This function will mark the current task as a reader of the specified node, when + /// a node index can be found for that node. + pub fn try_mark_green<Ctxt: QueryContext<DepKind = K>>( + &self, + tcx: Ctxt, + dep_node: &DepNode<K>, + ) -> Option<(SerializedDepNodeIndex, DepNodeIndex)> { + debug_assert!(!tcx.dep_context().is_eval_always(dep_node.kind)); + + // Return None if the dep graph is disabled + let data = self.data.as_ref()?; + + // Return None if the dep node didn't exist in the previous session + let prev_index = data.previous.node_to_index_opt(dep_node)?; + + match data.colors.get(prev_index) { + Some(DepNodeColor::Green(dep_node_index)) => Some((prev_index, dep_node_index)), + Some(DepNodeColor::Red) => None, + None => { + // This DepNode and the corresponding query invocation existed + // in the previous compilation session too, so we can try to + // mark it as green by recursively marking all of its + // dependencies green. + self.try_mark_previous_green(tcx, data, prev_index, &dep_node) + .map(|dep_node_index| (prev_index, dep_node_index)) + } + } + } + + fn try_mark_parent_green<Ctxt: QueryContext<DepKind = K>>( + &self, + tcx: Ctxt, + data: &DepGraphData<K>, + parent_dep_node_index: SerializedDepNodeIndex, + dep_node: &DepNode<K>, + ) -> Option<()> { + let dep_dep_node_color = data.colors.get(parent_dep_node_index); + let dep_dep_node = &data.previous.index_to_node(parent_dep_node_index); + + match dep_dep_node_color { + Some(DepNodeColor::Green(_)) => { + // This dependency has been marked as green before, we are + // still fine and can continue with checking the other + // dependencies. + debug!( + "try_mark_previous_green({:?}) --- found dependency {:?} to \ + be immediately green", + dep_node, dep_dep_node, + ); + return Some(()); + } + Some(DepNodeColor::Red) => { + // We found a dependency the value of which has changed + // compared to the previous compilation session. We cannot + // mark the DepNode as green and also don't need to bother + // with checking any of the other dependencies. + debug!( + "try_mark_previous_green({:?}) - END - dependency {:?} was immediately red", + dep_node, dep_dep_node, + ); + return None; + } + None => {} + } + + // We don't know the state of this dependency. If it isn't + // an eval_always node, let's try to mark it green recursively. + if !tcx.dep_context().is_eval_always(dep_dep_node.kind) { + debug!( + "try_mark_previous_green({:?}) --- state of dependency {:?} ({}) \ + is unknown, trying to mark it green", + dep_node, dep_dep_node, dep_dep_node.hash, + ); + + let node_index = + self.try_mark_previous_green(tcx, data, parent_dep_node_index, dep_dep_node); + if node_index.is_some() { + debug!( + "try_mark_previous_green({:?}) --- managed to MARK dependency {:?} as green", + dep_node, dep_dep_node + ); + return Some(()); + } + } + + // We failed to mark it green, so we try to force the query. + debug!( + "try_mark_previous_green({:?}) --- trying to force dependency {:?}", + dep_node, dep_dep_node + ); + if !tcx.dep_context().try_force_from_dep_node(*dep_dep_node) { + // The DepNode could not be forced. + debug!( + "try_mark_previous_green({:?}) - END - dependency {:?} could not be forced", + dep_node, dep_dep_node + ); + return None; + } + + let dep_dep_node_color = data.colors.get(parent_dep_node_index); + + match dep_dep_node_color { + Some(DepNodeColor::Green(_)) => { + debug!( + "try_mark_previous_green({:?}) --- managed to FORCE dependency {:?} to green", + dep_node, dep_dep_node + ); + return Some(()); + } + Some(DepNodeColor::Red) => { + debug!( + "try_mark_previous_green({:?}) - END - dependency {:?} was red after forcing", + dep_node, dep_dep_node + ); + return None; + } + None => {} + } + + if !tcx.dep_context().sess().has_errors_or_delayed_span_bugs() { + panic!("try_mark_previous_green() - Forcing the DepNode should have set its color") + } + + // If the query we just forced has resulted in + // some kind of compilation error, we cannot rely on + // the dep-node color having been properly updated. + // This means that the query system has reached an + // invalid state. We let the compiler continue (by + // returning `None`) so it can emit error messages + // and wind down, but rely on the fact that this + // invalid state will not be persisted to the + // incremental compilation cache because of + // compilation errors being present. + debug!( + "try_mark_previous_green({:?}) - END - dependency {:?} resulted in compilation error", + dep_node, dep_dep_node + ); + return None; + } + + /// Try to mark a dep-node which existed in the previous compilation session as green. + fn try_mark_previous_green<Ctxt: QueryContext<DepKind = K>>( + &self, + tcx: Ctxt, + data: &DepGraphData<K>, + prev_dep_node_index: SerializedDepNodeIndex, + dep_node: &DepNode<K>, + ) -> Option<DepNodeIndex> { + debug!("try_mark_previous_green({:?}) - BEGIN", dep_node); + + #[cfg(not(parallel_compiler))] + { + debug_assert!(!self.dep_node_exists(dep_node)); + debug_assert!(data.colors.get(prev_dep_node_index).is_none()); + } + + // We never try to mark eval_always nodes as green + debug_assert!(!tcx.dep_context().is_eval_always(dep_node.kind)); + + debug_assert_eq!(data.previous.index_to_node(prev_dep_node_index), *dep_node); + + let prev_deps = data.previous.edge_targets_from(prev_dep_node_index); + + for &dep_dep_node_index in prev_deps { + self.try_mark_parent_green(tcx, data, dep_dep_node_index, dep_node)? + } + + // If we got here without hitting a `return` that means that all + // dependencies of this DepNode could be marked as green. Therefore we + // can also mark this DepNode as green. + + // There may be multiple threads trying to mark the same dep node green concurrently + + // We allocating an entry for the node in the current dependency graph and + // adding all the appropriate edges imported from the previous graph + let dep_node_index = data.current.promote_node_and_deps_to_current( + tcx.dep_context().profiler(), + &data.previous, + prev_dep_node_index, + ); + + // ... emitting any stored diagnostic ... + + // FIXME: Store the fact that a node has diagnostics in a bit in the dep graph somewhere + // Maybe store a list on disk and encode this fact in the DepNodeState + let side_effects = tcx.load_side_effects(prev_dep_node_index); + + #[cfg(not(parallel_compiler))] + debug_assert!( + data.colors.get(prev_dep_node_index).is_none(), + "DepGraph::try_mark_previous_green() - Duplicate DepNodeColor \ + insertion for {:?}", + dep_node + ); + + if !side_effects.is_empty() { + self.emit_side_effects(tcx, data, dep_node_index, side_effects); + } + + // ... and finally storing a "Green" entry in the color map. + // Multiple threads can all write the same color here + data.colors.insert(prev_dep_node_index, DepNodeColor::Green(dep_node_index)); + + debug!("try_mark_previous_green({:?}) - END - successfully marked as green", dep_node); + Some(dep_node_index) + } + + /// Atomically emits some loaded diagnostics. + /// This may be called concurrently on multiple threads for the same dep node. + #[cold] + #[inline(never)] + fn emit_side_effects<Ctxt: QueryContext<DepKind = K>>( + &self, + tcx: Ctxt, + data: &DepGraphData<K>, + dep_node_index: DepNodeIndex, + side_effects: QuerySideEffects, + ) { + let mut processed = data.processed_side_effects.lock(); + + if processed.insert(dep_node_index) { + // We were the first to insert the node in the set so this thread + // must process side effects + + // Promote the previous diagnostics to the current session. + tcx.store_side_effects(dep_node_index, side_effects.clone()); + + let handle = tcx.dep_context().sess().diagnostic(); + + for mut diagnostic in side_effects.diagnostics { + handle.emit_diagnostic(&mut diagnostic); + } + } + } + + // Returns true if the given node has been marked as red during the + // current compilation session. Used in various assertions + pub fn is_red(&self, dep_node: &DepNode<K>) -> bool { + self.node_color(dep_node) == Some(DepNodeColor::Red) + } + + // Returns true if the given node has been marked as green during the + // current compilation session. Used in various assertions + pub fn is_green(&self, dep_node: &DepNode<K>) -> bool { + self.node_color(dep_node).map_or(false, |c| c.is_green()) + } + + // This method loads all on-disk cacheable query results into memory, so + // they can be written out to the new cache file again. Most query results + // will already be in memory but in the case where we marked something as + // green but then did not need the value, that value will never have been + // loaded from disk. + // + // This method will only load queries that will end up in the disk cache. + // Other queries will not be executed. + pub fn exec_cache_promotions<Ctxt: DepContext<DepKind = K>>(&self, tcx: Ctxt) { + let _prof_timer = tcx.profiler().generic_activity("incr_comp_query_cache_promotion"); + + let data = self.data.as_ref().unwrap(); + for prev_index in data.colors.values.indices() { + match data.colors.get(prev_index) { + Some(DepNodeColor::Green(_)) => { + let dep_node = data.previous.index_to_node(prev_index); + tcx.try_load_from_on_disk_cache(dep_node); + } + None | Some(DepNodeColor::Red) => { + // We can skip red nodes because a node can only be marked + // as red if the query result was recomputed and thus is + // already in memory. + } + } + } + } + + pub fn print_incremental_info(&self) { + if let Some(data) = &self.data { + data.current.encoder.borrow().print_incremental_info( + data.current.total_read_count.load(Relaxed), + data.current.total_duplicate_read_count.load(Relaxed), + ) + } + } + + pub fn encode(&self, profiler: &SelfProfilerRef) -> FileEncodeResult { + if let Some(data) = &self.data { + data.current.encoder.steal().finish(profiler) + } else { + Ok(0) + } + } + + pub(crate) fn next_virtual_depnode_index(&self) -> DepNodeIndex { + let index = self.virtual_dep_node_index.fetch_add(1, Relaxed); + DepNodeIndex::from_u32(index) + } +} + +/// A "work product" is an intermediate result that we save into the +/// incremental directory for later re-use. The primary example are +/// the object files that we save for each partition at code +/// generation time. +/// +/// Each work product is associated with a dep-node, representing the +/// process that produced the work-product. If that dep-node is found +/// to be dirty when we load up, then we will delete the work-product +/// at load time. If the work-product is found to be clean, then we +/// will keep a record in the `previous_work_products` list. +/// +/// In addition, work products have an associated hash. This hash is +/// an extra hash that can be used to decide if the work-product from +/// a previous compilation can be re-used (in addition to the dirty +/// edges check). +/// +/// As the primary example, consider the object files we generate for +/// each partition. In the first run, we create partitions based on +/// the symbols that need to be compiled. For each partition P, we +/// hash the symbols in P and create a `WorkProduct` record associated +/// with `DepNode::CodegenUnit(P)`; the hash is the set of symbols +/// in P. +/// +/// The next time we compile, if the `DepNode::CodegenUnit(P)` is +/// judged to be clean (which means none of the things we read to +/// generate the partition were found to be dirty), it will be loaded +/// into previous work products. We will then regenerate the set of +/// symbols in the partition P and hash them (note that new symbols +/// may be added -- for example, new monomorphizations -- even if +/// nothing in P changed!). We will compare that hash against the +/// previous hash. If it matches up, we can reuse the object file. +#[derive(Clone, Debug, Encodable, Decodable)] +pub struct WorkProduct { + pub cgu_name: String, + /// Saved files associated with this CGU. In each key/value pair, the value is the path to the + /// saved file and the key is some identifier for the type of file being saved. + /// + /// By convention, file extensions are currently used as identifiers, i.e. the key "o" maps to + /// the object file's path, and "dwo" to the dwarf object file's path. + pub saved_files: FxHashMap<String, String>, +} + +// Index type for `DepNodeData`'s edges. +rustc_index::newtype_index! { + struct EdgeIndex { .. } +} + +/// `CurrentDepGraph` stores the dependency graph for the current session. It +/// will be populated as we run queries or tasks. We never remove nodes from the +/// graph: they are only added. +/// +/// The nodes in it are identified by a `DepNodeIndex`. We avoid keeping the nodes +/// in memory. This is important, because these graph structures are some of the +/// largest in the compiler. +/// +/// For this reason, we avoid storing `DepNode`s more than once as map +/// keys. The `new_node_to_index` map only contains nodes not in the previous +/// graph, and we map nodes in the previous graph to indices via a two-step +/// mapping. `SerializedDepGraph` maps from `DepNode` to `SerializedDepNodeIndex`, +/// and the `prev_index_to_index` vector (which is more compact and faster than +/// using a map) maps from `SerializedDepNodeIndex` to `DepNodeIndex`. +/// +/// This struct uses three locks internally. The `data`, `new_node_to_index`, +/// and `prev_index_to_index` fields are locked separately. Operations that take +/// a `DepNodeIndex` typically just access the `data` field. +/// +/// We only need to manipulate at most two locks simultaneously: +/// `new_node_to_index` and `data`, or `prev_index_to_index` and `data`. When +/// manipulating both, we acquire `new_node_to_index` or `prev_index_to_index` +/// first, and `data` second. +pub(super) struct CurrentDepGraph<K: DepKind> { + encoder: Steal<GraphEncoder<K>>, + new_node_to_index: Sharded<FxHashMap<DepNode<K>, DepNodeIndex>>, + prev_index_to_index: Lock<IndexVec<SerializedDepNodeIndex, Option<DepNodeIndex>>>, + + /// Used to trap when a specific edge is added to the graph. + /// This is used for debug purposes and is only active with `debug_assertions`. + #[cfg(debug_assertions)] + forbidden_edge: Option<EdgeFilter<K>>, + + /// Anonymous `DepNode`s are nodes whose IDs we compute from the list of + /// their edges. This has the beneficial side-effect that multiple anonymous + /// nodes can be coalesced into one without changing the semantics of the + /// dependency graph. However, the merging of nodes can lead to a subtle + /// problem during red-green marking: The color of an anonymous node from + /// the current session might "shadow" the color of the node with the same + /// ID from the previous session. In order to side-step this problem, we make + /// sure that anonymous `NodeId`s allocated in different sessions don't overlap. + /// This is implemented by mixing a session-key into the ID fingerprint of + /// each anon node. The session-key is just a random number generated when + /// the `DepGraph` is created. + anon_id_seed: Fingerprint, + + /// These are simple counters that are for profiling and + /// debugging and only active with `debug_assertions`. + total_read_count: AtomicU64, + total_duplicate_read_count: AtomicU64, + + /// The cached event id for profiling node interning. This saves us + /// from having to look up the event id every time we intern a node + /// which may incur too much overhead. + /// This will be None if self-profiling is disabled. + node_intern_event_id: Option<EventId>, +} + +impl<K: DepKind> CurrentDepGraph<K> { + fn new( + profiler: &SelfProfilerRef, + prev_graph_node_count: usize, + encoder: FileEncoder, + record_graph: bool, + record_stats: bool, + ) -> CurrentDepGraph<K> { + use std::time::{SystemTime, UNIX_EPOCH}; + + let duration = SystemTime::now().duration_since(UNIX_EPOCH).unwrap(); + let nanos = duration.as_secs() * 1_000_000_000 + duration.subsec_nanos() as u64; + let mut stable_hasher = StableHasher::new(); + nanos.hash(&mut stable_hasher); + let anon_id_seed = stable_hasher.finish(); + + #[cfg(debug_assertions)] + let forbidden_edge = match env::var("RUST_FORBID_DEP_GRAPH_EDGE") { + Ok(s) => match EdgeFilter::new(&s) { + Ok(f) => Some(f), + Err(err) => panic!("RUST_FORBID_DEP_GRAPH_EDGE invalid: {}", err), + }, + Err(_) => None, + }; + + // We store a large collection of these in `prev_index_to_index` during + // non-full incremental builds, and want to ensure that the element size + // doesn't inadvertently increase. + static_assert_size!(Option<DepNodeIndex>, 4); + + let new_node_count_estimate = 102 * prev_graph_node_count / 100 + 200; + + let node_intern_event_id = profiler + .get_or_alloc_cached_string("incr_comp_intern_dep_graph_node") + .map(EventId::from_label); + + CurrentDepGraph { + encoder: Steal::new(GraphEncoder::new( + encoder, + prev_graph_node_count, + record_graph, + record_stats, + )), + new_node_to_index: Sharded::new(|| { + FxHashMap::with_capacity_and_hasher( + new_node_count_estimate / sharded::SHARDS, + Default::default(), + ) + }), + prev_index_to_index: Lock::new(IndexVec::from_elem_n(None, prev_graph_node_count)), + anon_id_seed, + #[cfg(debug_assertions)] + forbidden_edge, + total_read_count: AtomicU64::new(0), + total_duplicate_read_count: AtomicU64::new(0), + node_intern_event_id, + } + } + + #[cfg(debug_assertions)] + fn record_edge(&self, dep_node_index: DepNodeIndex, key: DepNode<K>) { + if let Some(forbidden_edge) = &self.forbidden_edge { + forbidden_edge.index_to_node.lock().insert(dep_node_index, key); + } + } + + /// Writes the node to the current dep-graph and allocates a `DepNodeIndex` for it. + /// Assumes that this is a node that has no equivalent in the previous dep-graph. + fn intern_new_node( + &self, + profiler: &SelfProfilerRef, + key: DepNode<K>, + edges: EdgesVec, + current_fingerprint: Fingerprint, + ) -> DepNodeIndex { + match self.new_node_to_index.get_shard_by_value(&key).lock().entry(key) { + Entry::Occupied(entry) => *entry.get(), + Entry::Vacant(entry) => { + let dep_node_index = + self.encoder.borrow().send(profiler, key, current_fingerprint, edges); + entry.insert(dep_node_index); + #[cfg(debug_assertions)] + self.record_edge(dep_node_index, key); + dep_node_index + } + } + } + + fn intern_node( + &self, + profiler: &SelfProfilerRef, + prev_graph: &SerializedDepGraph<K>, + key: DepNode<K>, + edges: EdgesVec, + fingerprint: Option<Fingerprint>, + print_status: bool, + ) -> (DepNodeIndex, Option<(SerializedDepNodeIndex, DepNodeColor)>) { + let print_status = cfg!(debug_assertions) && print_status; + + // Get timer for profiling `DepNode` interning + let _node_intern_timer = + self.node_intern_event_id.map(|eid| profiler.generic_activity_with_event_id(eid)); + + if let Some(prev_index) = prev_graph.node_to_index_opt(&key) { + // Determine the color and index of the new `DepNode`. + if let Some(fingerprint) = fingerprint { + if fingerprint == prev_graph.fingerprint_by_index(prev_index) { + if print_status { + eprintln!("[task::green] {:?}", key); + } + + // This is a green node: it existed in the previous compilation, + // its query was re-executed, and it has the same result as before. + let mut prev_index_to_index = self.prev_index_to_index.lock(); + + let dep_node_index = match prev_index_to_index[prev_index] { + Some(dep_node_index) => dep_node_index, + None => { + let dep_node_index = + self.encoder.borrow().send(profiler, key, fingerprint, edges); + prev_index_to_index[prev_index] = Some(dep_node_index); + dep_node_index + } + }; + + #[cfg(debug_assertions)] + self.record_edge(dep_node_index, key); + (dep_node_index, Some((prev_index, DepNodeColor::Green(dep_node_index)))) + } else { + if print_status { + eprintln!("[task::red] {:?}", key); + } + + // This is a red node: it existed in the previous compilation, its query + // was re-executed, but it has a different result from before. + let mut prev_index_to_index = self.prev_index_to_index.lock(); + + let dep_node_index = match prev_index_to_index[prev_index] { + Some(dep_node_index) => dep_node_index, + None => { + let dep_node_index = + self.encoder.borrow().send(profiler, key, fingerprint, edges); + prev_index_to_index[prev_index] = Some(dep_node_index); + dep_node_index + } + }; + + #[cfg(debug_assertions)] + self.record_edge(dep_node_index, key); + (dep_node_index, Some((prev_index, DepNodeColor::Red))) + } + } else { + if print_status { + eprintln!("[task::unknown] {:?}", key); + } + + // This is a red node, effectively: it existed in the previous compilation + // session, its query was re-executed, but it doesn't compute a result hash + // (i.e. it represents a `no_hash` query), so we have no way of determining + // whether or not the result was the same as before. + let mut prev_index_to_index = self.prev_index_to_index.lock(); + + let dep_node_index = match prev_index_to_index[prev_index] { + Some(dep_node_index) => dep_node_index, + None => { + let dep_node_index = + self.encoder.borrow().send(profiler, key, Fingerprint::ZERO, edges); + prev_index_to_index[prev_index] = Some(dep_node_index); + dep_node_index + } + }; + + #[cfg(debug_assertions)] + self.record_edge(dep_node_index, key); + (dep_node_index, Some((prev_index, DepNodeColor::Red))) + } + } else { + if print_status { + eprintln!("[task::new] {:?}", key); + } + + let fingerprint = fingerprint.unwrap_or(Fingerprint::ZERO); + + // This is a new node: it didn't exist in the previous compilation session. + let dep_node_index = self.intern_new_node(profiler, key, edges, fingerprint); + + (dep_node_index, None) + } + } + + fn promote_node_and_deps_to_current( + &self, + profiler: &SelfProfilerRef, + prev_graph: &SerializedDepGraph<K>, + prev_index: SerializedDepNodeIndex, + ) -> DepNodeIndex { + self.debug_assert_not_in_new_nodes(prev_graph, prev_index); + + let mut prev_index_to_index = self.prev_index_to_index.lock(); + + match prev_index_to_index[prev_index] { + Some(dep_node_index) => dep_node_index, + None => { + let key = prev_graph.index_to_node(prev_index); + let dep_node_index = self.encoder.borrow().send( + profiler, + key, + prev_graph.fingerprint_by_index(prev_index), + prev_graph + .edge_targets_from(prev_index) + .iter() + .map(|i| prev_index_to_index[*i].unwrap()) + .collect(), + ); + prev_index_to_index[prev_index] = Some(dep_node_index); + #[cfg(debug_assertions)] + self.record_edge(dep_node_index, key); + dep_node_index + } + } + } + + #[inline] + fn debug_assert_not_in_new_nodes( + &self, + prev_graph: &SerializedDepGraph<K>, + prev_index: SerializedDepNodeIndex, + ) { + let node = &prev_graph.index_to_node(prev_index); + debug_assert!( + !self.new_node_to_index.get_shard_by_value(node).lock().contains_key(node), + "node from previous graph present in new node collection" + ); + } +} + +/// The capacity of the `reads` field `SmallVec` +const TASK_DEPS_READS_CAP: usize = 8; +type EdgesVec = SmallVec<[DepNodeIndex; TASK_DEPS_READS_CAP]>; + +#[derive(Debug, Clone, Copy)] +pub enum TaskDepsRef<'a, K: DepKind> { + /// New dependencies can be added to the + /// `TaskDeps`. This is used when executing a 'normal' query + /// (no `eval_always` modifier) + Allow(&'a Lock<TaskDeps<K>>), + /// New dependencies are ignored. This is used when + /// executing an `eval_always` query, since there's no + /// need to track dependencies for a query that's always + /// re-executed. This is also used for `dep_graph.with_ignore` + Ignore, + /// Any attempt to add new dependencies will cause a panic. + /// This is used when decoding a query result from disk, + /// to ensure that the decoding process doesn't itself + /// require the execution of any queries. + Forbid, +} + +#[derive(Debug)] +pub struct TaskDeps<K: DepKind> { + #[cfg(debug_assertions)] + node: Option<DepNode<K>>, + reads: EdgesVec, + read_set: FxHashSet<DepNodeIndex>, + phantom_data: PhantomData<DepNode<K>>, +} + +impl<K: DepKind> Default for TaskDeps<K> { + fn default() -> Self { + Self { + #[cfg(debug_assertions)] + node: None, + reads: EdgesVec::new(), + read_set: FxHashSet::default(), + phantom_data: PhantomData, + } + } +} + +// A data structure that stores Option<DepNodeColor> values as a contiguous +// array, using one u32 per entry. +struct DepNodeColorMap { + values: IndexVec<SerializedDepNodeIndex, AtomicU32>, +} + +const COMPRESSED_NONE: u32 = 0; +const COMPRESSED_RED: u32 = 1; +const COMPRESSED_FIRST_GREEN: u32 = 2; + +impl DepNodeColorMap { + fn new(size: usize) -> DepNodeColorMap { + DepNodeColorMap { values: (0..size).map(|_| AtomicU32::new(COMPRESSED_NONE)).collect() } + } + + #[inline] + fn get(&self, index: SerializedDepNodeIndex) -> Option<DepNodeColor> { + match self.values[index].load(Ordering::Acquire) { + COMPRESSED_NONE => None, + COMPRESSED_RED => Some(DepNodeColor::Red), + value => { + Some(DepNodeColor::Green(DepNodeIndex::from_u32(value - COMPRESSED_FIRST_GREEN))) + } + } + } + + fn insert(&self, index: SerializedDepNodeIndex, color: DepNodeColor) { + self.values[index].store( + match color { + DepNodeColor::Red => COMPRESSED_RED, + DepNodeColor::Green(index) => index.as_u32() + COMPRESSED_FIRST_GREEN, + }, + Ordering::Release, + ) + } +} |