1 use rustc_data_structures::fingerprint::Fingerprint;
2 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
3 use rustc_data_structures::profiling::QueryInvocationId;
4 use rustc_data_structures::sharded::{self, Sharded};
5 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
6 use rustc_data_structures::sync::{AtomicU32, AtomicU64, Lock, LockGuard, Lrc, Ordering};
7 use rustc_data_structures::unlikely;
8 use rustc_errors::Diagnostic;
9 use rustc_index::vec::{Idx, IndexVec};
10 use rustc_serialize::{Encodable, Encoder};
12 use parking_lot::{Condvar, Mutex};
13 use smallvec::{smallvec, SmallVec};
14 use std::collections::hash_map::Entry;
17 use std::marker::PhantomData;
20 use std::sync::atomic::Ordering::Relaxed;
22 use super::debug::EdgeFilter;
23 use super::prev::PreviousDepGraph;
24 use super::query::DepGraphQuery;
25 use super::serialized::SerializedDepNodeIndex;
26 use super::{DepContext, DepKind, DepNode, WorkProductId};
29 pub struct DepGraph<K: DepKind> {
30 data: Option<Lrc<DepGraphData<K>>>,
32 /// This field is used for assigning DepNodeIndices when running in
33 /// non-incremental mode. Even in non-incremental mode we make sure that
34 /// each task has a `DepNodeIndex` that uniquely identifies it. This unique
35 /// ID is used for self-profiling.
36 virtual_dep_node_index: Lrc<AtomicU32>,
39 rustc_index::newtype_index! {
40 pub struct DepNodeIndex { .. }
44 pub const INVALID: DepNodeIndex = DepNodeIndex::MAX;
47 impl std::convert::From<DepNodeIndex> for QueryInvocationId {
49 fn from(dep_node_index: DepNodeIndex) -> Self {
50 QueryInvocationId(dep_node_index.as_u32())
55 pub enum DepNodeColor {
61 pub fn is_green(self) -> bool {
63 DepNodeColor::Red => false,
64 DepNodeColor::Green(_) => true,
69 struct DepGraphData<K: DepKind> {
70 /// The new encoding of the dependency graph, optimized for red/green
71 /// tracking. The `current` field is the dependency graph of only the
72 /// current compilation session: We don't merge the previous dep-graph into
73 /// current one anymore, but we do reference shared data to save space.
74 current: CurrentDepGraph<K>,
76 /// The dep-graph from the previous compilation session. It contains all
77 /// nodes and edges as well as all fingerprints of nodes that have them.
78 previous: PreviousDepGraph<K>,
80 colors: DepNodeColorMap,
82 /// A set of loaded diagnostics that is in the progress of being emitted.
83 emitting_diagnostics: Mutex<FxHashSet<DepNodeIndex>>,
85 /// Used to wait for diagnostics to be emitted.
86 emitting_diagnostics_cond_var: Condvar,
88 /// When we load, there may be `.o` files, cached MIR, or other such
89 /// things available to us. If we find that they are not dirty, we
90 /// load the path to the file storing those work-products here into
91 /// this map. We can later look for and extract that data.
92 previous_work_products: FxHashMap<WorkProductId, WorkProduct>,
94 dep_node_debug: Lock<FxHashMap<DepNode<K>, String>>,
97 pub fn hash_result<HashCtxt, R>(hcx: &mut HashCtxt, result: &R) -> Option<Fingerprint>
99 R: HashStable<HashCtxt>,
101 let mut stable_hasher = StableHasher::new();
102 result.hash_stable(hcx, &mut stable_hasher);
104 Some(stable_hasher.finish())
107 impl<K: DepKind> DepGraph<K> {
109 prev_graph: PreviousDepGraph<K>,
110 prev_work_products: FxHashMap<WorkProductId, WorkProduct>,
112 let prev_graph_node_count = prev_graph.node_count();
115 data: Some(Lrc::new(DepGraphData {
116 previous_work_products: prev_work_products,
117 dep_node_debug: Default::default(),
118 current: CurrentDepGraph::new(prev_graph_node_count),
119 emitting_diagnostics: Default::default(),
120 emitting_diagnostics_cond_var: Condvar::new(),
121 previous: prev_graph,
122 colors: DepNodeColorMap::new(prev_graph_node_count),
124 virtual_dep_node_index: Lrc::new(AtomicU32::new(0)),
128 pub fn new_disabled() -> DepGraph<K> {
129 DepGraph { data: None, virtual_dep_node_index: Lrc::new(AtomicU32::new(0)) }
132 /// Returns `true` if we are actually building the full dep-graph, and `false` otherwise.
134 pub fn is_fully_enabled(&self) -> bool {
138 pub fn query(&self) -> DepGraphQuery<K> {
139 let data = self.data.as_ref().unwrap();
140 let previous = &data.previous;
142 // Note locking order: `prev_index_to_index`, then `data`.
143 let prev_index_to_index = data.current.prev_index_to_index.lock();
144 let data = data.current.data.lock();
145 let node_count = data.hybrid_indices.len();
146 let edge_count = self.edge_count(&data);
148 let mut nodes = Vec::with_capacity(node_count);
149 let mut edge_list_indices = Vec::with_capacity(node_count);
150 let mut edge_list_data = Vec::with_capacity(edge_count);
152 // See `DepGraph`'s `Encodable` implementation for notes on the approach used here.
154 edge_list_data.extend(data.unshared_edges.iter().map(|i| i.index()));
156 for &hybrid_index in data.hybrid_indices.iter() {
157 match hybrid_index.into() {
158 HybridIndex::New(new_index) => {
159 nodes.push(data.new.nodes[new_index]);
160 let edges = &data.new.edges[new_index];
161 edge_list_indices.push((edges.start.index(), edges.end.index()));
163 HybridIndex::Red(red_index) => {
164 nodes.push(previous.index_to_node(data.red.node_indices[red_index]));
165 let edges = &data.red.edges[red_index];
166 edge_list_indices.push((edges.start.index(), edges.end.index()));
168 HybridIndex::LightGreen(lg_index) => {
169 nodes.push(previous.index_to_node(data.light_green.node_indices[lg_index]));
170 let edges = &data.light_green.edges[lg_index];
171 edge_list_indices.push((edges.start.index(), edges.end.index()));
173 HybridIndex::DarkGreen(prev_index) => {
174 nodes.push(previous.index_to_node(prev_index));
176 let edges_iter = previous
177 .edge_targets_from(prev_index)
179 .map(|&dst| prev_index_to_index[dst].unwrap().index());
181 let start = edge_list_data.len();
182 edge_list_data.extend(edges_iter);
183 let end = edge_list_data.len();
184 edge_list_indices.push((start, end));
189 debug_assert_eq!(nodes.len(), node_count);
190 debug_assert_eq!(edge_list_indices.len(), node_count);
191 debug_assert_eq!(edge_list_data.len(), edge_count);
193 DepGraphQuery::new(&nodes[..], &edge_list_indices[..], &edge_list_data[..])
196 pub fn assert_ignored(&self) {
197 if let Some(..) = self.data {
198 K::read_deps(|task_deps| {
199 assert!(task_deps.is_none(), "expected no task dependency tracking");
204 pub fn with_ignore<OP, R>(&self, op: OP) -> R
208 K::with_deps(None, op)
211 /// Starts a new dep-graph task. Dep-graph tasks are specified
212 /// using a free function (`task`) and **not** a closure -- this
213 /// is intentional because we want to exercise tight control over
214 /// what state they have access to. In particular, we want to
215 /// prevent implicit 'leaks' of tracked state into the task (which
216 /// could then be read without generating correct edges in the
217 /// dep-graph -- see the [rustc dev guide] for more details on
218 /// the dep-graph). To this end, the task function gets exactly two
219 /// pieces of state: the context `cx` and an argument `arg`. Both
220 /// of these bits of state must be of some type that implements
221 /// `DepGraphSafe` and hence does not leak.
223 /// The choice of two arguments is not fundamental. One argument
224 /// would work just as well, since multiple values can be
225 /// collected using tuples. However, using two arguments works out
226 /// to be quite convenient, since it is common to need a context
227 /// (`cx`) and some argument (e.g., a `DefId` identifying what
228 /// item to process).
230 /// For cases where you need some other number of arguments:
232 /// - If you only need one argument, just use `()` for the `arg`
234 /// - If you need 3+ arguments, use a tuple for the
237 /// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/incremental-compilation.html
238 pub fn with_task<Ctxt: DepContext<DepKind = K>, A, R>(
243 task: fn(Ctxt, A) -> R,
244 hash_result: impl FnOnce(&mut Ctxt::StableHashingContext, &R) -> Option<Fingerprint>,
245 ) -> (R, DepNodeIndex) {
253 #[cfg(debug_assertions)]
255 reads: SmallVec::new(),
256 read_set: Default::default(),
257 phantom_data: PhantomData,
264 fn with_task_impl<Ctxt: DepContext<DepKind = K>, A, R>(
269 task: fn(Ctxt, A) -> R,
270 create_task: fn(DepNode<K>) -> Option<TaskDeps<K>>,
271 hash_result: impl FnOnce(&mut Ctxt::StableHashingContext, &R) -> Option<Fingerprint>,
272 ) -> (R, DepNodeIndex) {
273 if let Some(ref data) = self.data {
274 let task_deps = create_task(key).map(Lock::new);
275 let result = K::with_deps(task_deps.as_ref(), || task(cx, arg));
276 let edges = task_deps.map_or_else(|| smallvec![], |lock| lock.into_inner().reads);
278 let mut hcx = cx.create_stable_hashing_context();
279 let current_fingerprint = hash_result(&mut hcx, &result);
281 let print_status = cfg!(debug_assertions) && cx.debug_dep_tasks();
283 // Intern the new `DepNode`.
284 let dep_node_index = if let Some(prev_index) = data.previous.node_to_index_opt(&key) {
285 // Determine the color and index of the new `DepNode`.
286 let (color, dep_node_index) = if let Some(current_fingerprint) = current_fingerprint
288 if current_fingerprint == data.previous.fingerprint_by_index(prev_index) {
290 eprintln!("[task::green] {:?}", key);
293 // This is a light green node: it existed in the previous compilation,
294 // its query was re-executed, and it has the same result as before.
296 data.current.intern_light_green_node(&data.previous, prev_index, edges);
298 (DepNodeColor::Green(dep_node_index), dep_node_index)
301 eprintln!("[task::red] {:?}", key);
304 // This is a red node: it existed in the previous compilation, its query
305 // was re-executed, but it has a different result from before.
306 let dep_node_index = data.current.intern_red_node(
313 (DepNodeColor::Red, dep_node_index)
317 eprintln!("[task::unknown] {:?}", key);
320 // This is a red node, effectively: it existed in the previous compilation
321 // session, its query was re-executed, but it doesn't compute a result hash
322 // (i.e. it represents a `no_hash` query), so we have no way of determining
323 // whether or not the result was the same as before.
324 let dep_node_index = data.current.intern_red_node(
331 (DepNodeColor::Red, dep_node_index)
335 data.colors.get(prev_index).is_none(),
336 "DepGraph::with_task() - Duplicate DepNodeColor \
341 data.colors.insert(prev_index, color);
345 eprintln!("[task::new] {:?}", key);
348 // This is a new node: it didn't exist in the previous compilation session.
349 data.current.intern_new_node(
353 current_fingerprint.unwrap_or(Fingerprint::ZERO),
357 (result, dep_node_index)
359 // Incremental compilation is turned off. We just execute the task
360 // without tracking. We still provide a dep-node index that uniquely
361 // identifies the task so that we have a cheap way of referring to
362 // the query for self-profiling.
363 (task(cx, arg), self.next_virtual_depnode_index())
367 /// Executes something within an "anonymous" task, that is, a task the
368 /// `DepNode` of which is determined by the list of inputs it read from.
369 pub fn with_anon_task<OP, R>(&self, dep_kind: K, op: OP) -> (R, DepNodeIndex)
373 debug_assert!(!dep_kind.is_eval_always());
375 if let Some(ref data) = self.data {
376 let task_deps = Lock::new(TaskDeps::default());
377 let result = K::with_deps(Some(&task_deps), op);
378 let task_deps = task_deps.into_inner();
380 // The dep node indices are hashed here instead of hashing the dep nodes of the
381 // dependencies. These indices may refer to different nodes per session, but this isn't
382 // a problem here because we that ensure the final dep node hash is per session only by
383 // combining it with the per session random number `anon_id_seed`. This hash only need
384 // to map the dependencies to a single value on a per session basis.
385 let mut hasher = StableHasher::new();
386 task_deps.reads.hash(&mut hasher);
388 let target_dep_node = DepNode {
390 // Fingerprint::combine() is faster than sending Fingerprint
391 // through the StableHasher (at least as long as StableHasher
393 hash: data.current.anon_id_seed.combine(hasher.finish()).into(),
396 let dep_node_index = data.current.intern_new_node(
403 (result, dep_node_index)
405 (op(), self.next_virtual_depnode_index())
409 /// Executes something within an "eval-always" task which is a task
410 /// that runs whenever anything changes.
411 pub fn with_eval_always_task<Ctxt: DepContext<DepKind = K>, A, R>(
416 task: fn(Ctxt, A) -> R,
417 hash_result: impl FnOnce(&mut Ctxt::StableHashingContext, &R) -> Option<Fingerprint>,
418 ) -> (R, DepNodeIndex) {
419 self.with_task_impl(key, cx, arg, task, |_| None, hash_result)
423 pub fn read_index(&self, dep_node_index: DepNodeIndex) {
424 if let Some(ref data) = self.data {
425 K::read_deps(|task_deps| {
426 if let Some(task_deps) = task_deps {
427 let mut task_deps = task_deps.lock();
428 let task_deps = &mut *task_deps;
429 if cfg!(debug_assertions) {
430 data.current.total_read_count.fetch_add(1, Relaxed);
433 // As long as we only have a low number of reads we can avoid doing a hash
434 // insert and potentially allocating/reallocating the hashmap
435 let new_read = if task_deps.reads.len() < TASK_DEPS_READS_CAP {
436 task_deps.reads.iter().all(|other| *other != dep_node_index)
438 task_deps.read_set.insert(dep_node_index)
441 task_deps.reads.push(dep_node_index);
442 if task_deps.reads.len() == TASK_DEPS_READS_CAP {
443 // Fill `read_set` with what we have so far so we can use the hashset
445 task_deps.read_set.extend(task_deps.reads.iter().copied());
448 #[cfg(debug_assertions)]
450 if let Some(target) = task_deps.node {
451 if let Some(ref forbidden_edge) = data.current.forbidden_edge {
452 let src = self.dep_node_of(dep_node_index);
453 if forbidden_edge.test(&src, &target) {
454 panic!("forbidden edge {:?} -> {:?} created", src, target)
459 } else if cfg!(debug_assertions) {
460 data.current.total_duplicate_read_count.fetch_add(1, Relaxed);
468 pub fn dep_node_index_of(&self, dep_node: &DepNode<K>) -> DepNodeIndex {
469 self.dep_node_index_of_opt(dep_node).unwrap()
473 pub fn dep_node_index_of_opt(&self, dep_node: &DepNode<K>) -> Option<DepNodeIndex> {
474 let data = self.data.as_ref().unwrap();
475 let current = &data.current;
477 if let Some(prev_index) = data.previous.node_to_index_opt(dep_node) {
478 current.prev_index_to_index.lock()[prev_index]
480 current.new_node_to_index.get_shard_by_value(dep_node).lock().get(dep_node).copied()
485 pub fn dep_node_exists(&self, dep_node: &DepNode<K>) -> bool {
486 self.data.is_some() && self.dep_node_index_of_opt(dep_node).is_some()
490 pub fn dep_node_of(&self, dep_node_index: DepNodeIndex) -> DepNode<K> {
491 let data = self.data.as_ref().unwrap();
492 let previous = &data.previous;
493 let data = data.current.data.lock();
495 match data.hybrid_indices[dep_node_index].into() {
496 HybridIndex::New(new_index) => data.new.nodes[new_index],
497 HybridIndex::Red(red_index) => previous.index_to_node(data.red.node_indices[red_index]),
498 HybridIndex::LightGreen(light_green_index) => {
499 previous.index_to_node(data.light_green.node_indices[light_green_index])
501 HybridIndex::DarkGreen(prev_index) => previous.index_to_node(prev_index),
506 pub fn fingerprint_of(&self, dep_node_index: DepNodeIndex) -> Fingerprint {
507 let data = self.data.as_ref().unwrap();
508 let previous = &data.previous;
509 let data = data.current.data.lock();
511 match data.hybrid_indices[dep_node_index].into() {
512 HybridIndex::New(new_index) => data.new.fingerprints[new_index],
513 HybridIndex::Red(red_index) => data.red.fingerprints[red_index],
514 HybridIndex::LightGreen(light_green_index) => {
515 previous.fingerprint_by_index(data.light_green.node_indices[light_green_index])
517 HybridIndex::DarkGreen(prev_index) => previous.fingerprint_by_index(prev_index),
521 pub fn prev_fingerprint_of(&self, dep_node: &DepNode<K>) -> Option<Fingerprint> {
522 self.data.as_ref().unwrap().previous.fingerprint_of(dep_node)
525 /// Checks whether a previous work product exists for `v` and, if
526 /// so, return the path that leads to it. Used to skip doing work.
527 pub fn previous_work_product(&self, v: &WorkProductId) -> Option<WorkProduct> {
528 self.data.as_ref().and_then(|data| data.previous_work_products.get(v).cloned())
531 /// Access the map of work-products created during the cached run. Only
532 /// used during saving of the dep-graph.
533 pub fn previous_work_products(&self) -> &FxHashMap<WorkProductId, WorkProduct> {
534 &self.data.as_ref().unwrap().previous_work_products
538 pub fn register_dep_node_debug_str<F>(&self, dep_node: DepNode<K>, debug_str_gen: F)
540 F: FnOnce() -> String,
542 let dep_node_debug = &self.data.as_ref().unwrap().dep_node_debug;
544 if dep_node_debug.borrow().contains_key(&dep_node) {
547 let debug_str = debug_str_gen();
548 dep_node_debug.borrow_mut().insert(dep_node, debug_str);
551 pub fn dep_node_debug_str(&self, dep_node: DepNode<K>) -> Option<String> {
552 self.data.as_ref()?.dep_node_debug.borrow().get(&dep_node).cloned()
555 fn edge_count(&self, node_data: &LockGuard<'_, DepNodeData<K>>) -> usize {
556 let data = self.data.as_ref().unwrap();
557 let previous = &data.previous;
559 let mut edge_count = node_data.unshared_edges.len();
561 for &hybrid_index in node_data.hybrid_indices.iter() {
562 if let HybridIndex::DarkGreen(prev_index) = hybrid_index.into() {
563 edge_count += previous.edge_targets_from(prev_index).len()
570 pub fn node_color(&self, dep_node: &DepNode<K>) -> Option<DepNodeColor> {
571 if let Some(ref data) = self.data {
572 if let Some(prev_index) = data.previous.node_to_index_opt(dep_node) {
573 return data.colors.get(prev_index);
575 // This is a node that did not exist in the previous compilation
576 // session, so we consider it to be red.
577 return Some(DepNodeColor::Red);
584 /// Try to read a node index for the node dep_node.
585 /// A node will have an index, when it's already been marked green, or when we can mark it
586 /// green. This function will mark the current task as a reader of the specified node, when
587 /// a node index can be found for that node.
588 pub fn try_mark_green_and_read<Ctxt: DepContext<DepKind = K>>(
591 dep_node: &DepNode<K>,
592 ) -> Option<(SerializedDepNodeIndex, DepNodeIndex)> {
593 self.try_mark_green(tcx, dep_node).map(|(prev_index, dep_node_index)| {
594 debug_assert!(self.is_green(&dep_node));
595 self.read_index(dep_node_index);
596 (prev_index, dep_node_index)
600 pub fn try_mark_green<Ctxt: DepContext<DepKind = K>>(
603 dep_node: &DepNode<K>,
604 ) -> Option<(SerializedDepNodeIndex, DepNodeIndex)> {
605 debug_assert!(!dep_node.kind.is_eval_always());
607 // Return None if the dep graph is disabled
608 let data = self.data.as_ref()?;
610 // Return None if the dep node didn't exist in the previous session
611 let prev_index = data.previous.node_to_index_opt(dep_node)?;
613 match data.colors.get(prev_index) {
614 Some(DepNodeColor::Green(dep_node_index)) => Some((prev_index, dep_node_index)),
615 Some(DepNodeColor::Red) => None,
617 // This DepNode and the corresponding query invocation existed
618 // in the previous compilation session too, so we can try to
619 // mark it as green by recursively marking all of its
620 // dependencies green.
621 self.try_mark_previous_green(tcx, data, prev_index, &dep_node)
622 .map(|dep_node_index| (prev_index, dep_node_index))
627 /// Try to mark a dep-node which existed in the previous compilation session as green.
628 fn try_mark_previous_green<Ctxt: DepContext<DepKind = K>>(
631 data: &DepGraphData<K>,
632 prev_dep_node_index: SerializedDepNodeIndex,
633 dep_node: &DepNode<K>,
634 ) -> Option<DepNodeIndex> {
635 debug!("try_mark_previous_green({:?}) - BEGIN", dep_node);
637 #[cfg(not(parallel_compiler))]
639 debug_assert!(!self.dep_node_exists(dep_node));
640 debug_assert!(data.colors.get(prev_dep_node_index).is_none());
643 // We never try to mark eval_always nodes as green
644 debug_assert!(!dep_node.kind.is_eval_always());
646 debug_assert_eq!(data.previous.index_to_node(prev_dep_node_index), *dep_node);
648 let prev_deps = data.previous.edge_targets_from(prev_dep_node_index);
650 for &dep_dep_node_index in prev_deps {
651 let dep_dep_node_color = data.colors.get(dep_dep_node_index);
653 match dep_dep_node_color {
654 Some(DepNodeColor::Green(_)) => {
655 // This dependency has been marked as green before, we are
656 // still fine and can continue with checking the other
659 "try_mark_previous_green({:?}) --- found dependency {:?} to \
660 be immediately green",
662 data.previous.index_to_node(dep_dep_node_index)
665 Some(DepNodeColor::Red) => {
666 // We found a dependency the value of which has changed
667 // compared to the previous compilation session. We cannot
668 // mark the DepNode as green and also don't need to bother
669 // with checking any of the other dependencies.
671 "try_mark_previous_green({:?}) - END - dependency {:?} was \
674 data.previous.index_to_node(dep_dep_node_index)
679 let dep_dep_node = &data.previous.index_to_node(dep_dep_node_index);
681 // We don't know the state of this dependency. If it isn't
682 // an eval_always node, let's try to mark it green recursively.
683 if !dep_dep_node.kind.is_eval_always() {
685 "try_mark_previous_green({:?}) --- state of dependency {:?} ({}) \
686 is unknown, trying to mark it green",
687 dep_node, dep_dep_node, dep_dep_node.hash,
690 let node_index = self.try_mark_previous_green(
696 if node_index.is_some() {
698 "try_mark_previous_green({:?}) --- managed to MARK \
699 dependency {:?} as green",
700 dep_node, dep_dep_node
706 // We failed to mark it green, so we try to force the query.
708 "try_mark_previous_green({:?}) --- trying to force \
710 dep_node, dep_dep_node
712 if tcx.try_force_from_dep_node(dep_dep_node) {
713 let dep_dep_node_color = data.colors.get(dep_dep_node_index);
715 match dep_dep_node_color {
716 Some(DepNodeColor::Green(_)) => {
718 "try_mark_previous_green({:?}) --- managed to \
719 FORCE dependency {:?} to green",
720 dep_node, dep_dep_node
723 Some(DepNodeColor::Red) => {
725 "try_mark_previous_green({:?}) - END - \
726 dependency {:?} was red after forcing",
727 dep_node, dep_dep_node
732 if !tcx.has_errors_or_delayed_span_bugs() {
734 "try_mark_previous_green() - Forcing the DepNode \
735 should have set its color"
738 // If the query we just forced has resulted in
739 // some kind of compilation error, we cannot rely on
740 // the dep-node color having been properly updated.
741 // This means that the query system has reached an
742 // invalid state. We let the compiler continue (by
743 // returning `None`) so it can emit error messages
744 // and wind down, but rely on the fact that this
745 // invalid state will not be persisted to the
746 // incremental compilation cache because of
747 // compilation errors being present.
749 "try_mark_previous_green({:?}) - END - \
750 dependency {:?} resulted in compilation error",
751 dep_node, dep_dep_node
758 // The DepNode could not be forced.
760 "try_mark_previous_green({:?}) - END - dependency {:?} \
761 could not be forced",
762 dep_node, dep_dep_node
770 // If we got here without hitting a `return` that means that all
771 // dependencies of this DepNode could be marked as green. Therefore we
772 // can also mark this DepNode as green.
774 // There may be multiple threads trying to mark the same dep node green concurrently
776 let dep_node_index = {
777 // We allocating an entry for the node in the current dependency graph and
778 // adding all the appropriate edges imported from the previous graph
779 data.current.intern_dark_green_node(&data.previous, prev_dep_node_index)
782 // ... emitting any stored diagnostic ...
784 // FIXME: Store the fact that a node has diagnostics in a bit in the dep graph somewhere
785 // Maybe store a list on disk and encode this fact in the DepNodeState
786 let diagnostics = tcx.load_diagnostics(prev_dep_node_index);
788 #[cfg(not(parallel_compiler))]
790 data.colors.get(prev_dep_node_index).is_none(),
791 "DepGraph::try_mark_previous_green() - Duplicate DepNodeColor \
796 if unlikely!(!diagnostics.is_empty()) {
797 self.emit_diagnostics(tcx, data, dep_node_index, prev_dep_node_index, diagnostics);
800 // ... and finally storing a "Green" entry in the color map.
801 // Multiple threads can all write the same color here
802 data.colors.insert(prev_dep_node_index, DepNodeColor::Green(dep_node_index));
804 debug!("try_mark_previous_green({:?}) - END - successfully marked as green", dep_node);
808 /// Atomically emits some loaded diagnostics.
809 /// This may be called concurrently on multiple threads for the same dep node.
812 fn emit_diagnostics<Ctxt: DepContext<DepKind = K>>(
815 data: &DepGraphData<K>,
816 dep_node_index: DepNodeIndex,
817 prev_dep_node_index: SerializedDepNodeIndex,
818 diagnostics: Vec<Diagnostic>,
820 let mut emitting = data.emitting_diagnostics.lock();
822 if data.colors.get(prev_dep_node_index) == Some(DepNodeColor::Green(dep_node_index)) {
823 // The node is already green so diagnostics must have been emitted already
827 if emitting.insert(dep_node_index) {
828 // We were the first to insert the node in the set so this thread
829 // must emit the diagnostics and signal other potentially waiting
833 // Promote the previous diagnostics to the current session.
834 tcx.store_diagnostics(dep_node_index, diagnostics.clone().into());
836 let handle = tcx.diagnostic();
838 for diagnostic in diagnostics {
839 handle.emit_diagnostic(&diagnostic);
842 // Mark the node as green now that diagnostics are emitted
843 data.colors.insert(prev_dep_node_index, DepNodeColor::Green(dep_node_index));
845 // Remove the node from the set
846 data.emitting_diagnostics.lock().remove(&dep_node_index);
849 data.emitting_diagnostics_cond_var.notify_all();
851 // We must wait for the other thread to finish emitting the diagnostic
854 data.emitting_diagnostics_cond_var.wait(&mut emitting);
855 if data.colors.get(prev_dep_node_index) == Some(DepNodeColor::Green(dep_node_index))
863 // Returns true if the given node has been marked as green during the
864 // current compilation session. Used in various assertions
865 pub fn is_green(&self, dep_node: &DepNode<K>) -> bool {
866 self.node_color(dep_node).map_or(false, |c| c.is_green())
869 // This method loads all on-disk cacheable query results into memory, so
870 // they can be written out to the new cache file again. Most query results
871 // will already be in memory but in the case where we marked something as
872 // green but then did not need the value, that value will never have been
875 // This method will only load queries that will end up in the disk cache.
876 // Other queries will not be executed.
877 pub fn exec_cache_promotions<Ctxt: DepContext<DepKind = K>>(&self, tcx: Ctxt) {
878 let _prof_timer = tcx.profiler().generic_activity("incr_comp_query_cache_promotion");
880 let data = self.data.as_ref().unwrap();
881 for prev_index in data.colors.values.indices() {
882 match data.colors.get(prev_index) {
883 Some(DepNodeColor::Green(_)) => {
884 let dep_node = data.previous.index_to_node(prev_index);
885 tcx.try_load_from_on_disk_cache(&dep_node);
887 None | Some(DepNodeColor::Red) => {
888 // We can skip red nodes because a node can only be marked
889 // as red if the query result was recomputed and thus is
890 // already in memory.
896 // Register reused dep nodes (i.e. nodes we've marked red or green) with the context.
897 pub fn register_reused_dep_nodes<Ctxt: DepContext<DepKind = K>>(&self, tcx: Ctxt) {
898 let data = self.data.as_ref().unwrap();
899 for prev_index in data.colors.values.indices() {
900 match data.colors.get(prev_index) {
901 Some(DepNodeColor::Red) | Some(DepNodeColor::Green(_)) => {
902 let dep_node = data.previous.index_to_node(prev_index);
903 tcx.register_reused_dep_node(&dep_node);
910 pub fn print_incremental_info(&self) {
912 struct Stat<Kind: DepKind> {
918 let data = self.data.as_ref().unwrap();
919 let prev = &data.previous;
920 let current = &data.current;
921 let data = current.data.lock();
923 let mut stats: FxHashMap<_, Stat<K>> = FxHashMap::with_hasher(Default::default());
925 for &hybrid_index in data.hybrid_indices.iter() {
926 let (kind, edge_count) = match hybrid_index.into() {
927 HybridIndex::New(new_index) => {
928 let kind = data.new.nodes[new_index].kind;
929 let edge_range = &data.new.edges[new_index];
930 (kind, edge_range.end.as_usize() - edge_range.start.as_usize())
932 HybridIndex::Red(red_index) => {
933 let kind = prev.index_to_node(data.red.node_indices[red_index]).kind;
934 let edge_range = &data.red.edges[red_index];
935 (kind, edge_range.end.as_usize() - edge_range.start.as_usize())
937 HybridIndex::LightGreen(lg_index) => {
938 let kind = prev.index_to_node(data.light_green.node_indices[lg_index]).kind;
939 let edge_range = &data.light_green.edges[lg_index];
940 (kind, edge_range.end.as_usize() - edge_range.start.as_usize())
942 HybridIndex::DarkGreen(prev_index) => {
943 let kind = prev.index_to_node(prev_index).kind;
944 let edge_count = prev.edge_targets_from(prev_index).len();
949 let stat = stats.entry(kind).or_insert(Stat { kind, node_counter: 0, edge_counter: 0 });
950 stat.node_counter += 1;
951 stat.edge_counter += edge_count as u64;
954 let total_node_count = data.hybrid_indices.len();
955 let total_edge_count = self.edge_count(&data);
957 // Drop the lock guard.
958 std::mem::drop(data);
960 let mut stats: Vec<_> = stats.values().cloned().collect();
961 stats.sort_by_key(|s| -(s.node_counter as i64));
963 const SEPARATOR: &str = "[incremental] --------------------------------\
964 ----------------------------------------------\
967 println!("[incremental]");
968 println!("[incremental] DepGraph Statistics");
969 println!("{}", SEPARATOR);
970 println!("[incremental]");
971 println!("[incremental] Total Node Count: {}", total_node_count);
972 println!("[incremental] Total Edge Count: {}", total_edge_count);
974 if cfg!(debug_assertions) {
975 let total_edge_reads = current.total_read_count.load(Relaxed);
976 let total_duplicate_edge_reads = current.total_duplicate_read_count.load(Relaxed);
978 println!("[incremental] Total Edge Reads: {}", total_edge_reads);
979 println!("[incremental] Total Duplicate Edge Reads: {}", total_duplicate_edge_reads);
982 println!("[incremental]");
985 "[incremental] {:<36}| {:<17}| {:<12}| {:<17}|",
986 "Node Kind", "Node Frequency", "Node Count", "Avg. Edge Count"
990 "[incremental] -------------------------------------\
993 |------------------|"
997 let node_kind_ratio = (100.0 * (stat.node_counter as f64)) / (total_node_count as f64);
998 let node_kind_avg_edges = (stat.edge_counter as f64) / (stat.node_counter as f64);
1001 "[incremental] {:<36}|{:>16.1}% |{:>12} |{:>17.1} |",
1002 format!("{:?}", stat.kind),
1005 node_kind_avg_edges,
1009 println!("{}", SEPARATOR);
1010 println!("[incremental]");
1013 fn next_virtual_depnode_index(&self) -> DepNodeIndex {
1014 let index = self.virtual_dep_node_index.fetch_add(1, Relaxed);
1015 DepNodeIndex::from_u32(index)
1019 impl<E: Encoder, K: DepKind + Encodable<E>> Encodable<E> for DepGraph<K> {
1020 fn encode(&self, e: &mut E) -> Result<(), E::Error> {
1021 // We used to serialize the dep graph by creating and serializing a `SerializedDepGraph`
1022 // using data copied from the `DepGraph`. But copying created a large memory spike, so we
1023 // now serialize directly from the `DepGraph` as if it's a `SerializedDepGraph`. Because we
1024 // deserialize that data into a `SerializedDepGraph` in the next compilation session, we
1025 // need `DepGraph`'s `Encodable` and `SerializedDepGraph`'s `Decodable` implementations to
1026 // be in sync. If you update this encoding, be sure to update the decoding, and vice-versa.
1028 let data = self.data.as_ref().unwrap();
1029 let prev = &data.previous;
1031 // Note locking order: `prev_index_to_index`, then `data`.
1032 let prev_index_to_index = data.current.prev_index_to_index.lock();
1033 let data = data.current.data.lock();
1034 let new = &data.new;
1035 let red = &data.red;
1036 let lg = &data.light_green;
1038 let node_count = data.hybrid_indices.len();
1039 let edge_count = self.edge_count(&data);
1041 // `rustc_middle::ty::query::OnDiskCache` expects nodes to be encoded in `DepNodeIndex`
1042 // order. The edges in `edge_list_data` don't need to be in a particular order, as long as
1043 // each node references its edges as a contiguous range within it. Therefore, we can encode
1044 // `edge_list_data` directly from `unshared_edges`. It meets the above requirements, as
1045 // each non-dark-green node already knows the range of edges to reference within it, which
1046 // they'll encode in `edge_list_indices`. Dark green nodes, however, don't have their edges
1047 // in `unshared_edges`, so need to add them to `edge_list_data`.
1051 // Encoded values (nodes, etc.) are explicitly typed below to avoid inadvertently
1052 // serializing data in the wrong format (i.e. one incompatible with `SerializedDepGraph`).
1053 e.emit_struct("SerializedDepGraph", 4, |e| {
1054 e.emit_struct_field("nodes", 0, |e| {
1055 // `SerializedDepGraph` expects this to be encoded as a sequence of `DepNode`s.
1056 e.emit_seq(node_count, |e| {
1057 for (seq_index, &hybrid_index) in data.hybrid_indices.iter().enumerate() {
1058 let node: DepNode<K> = match hybrid_index.into() {
1059 New(i) => new.nodes[i],
1060 Red(i) => prev.index_to_node(red.node_indices[i]),
1061 LightGreen(i) => prev.index_to_node(lg.node_indices[i]),
1062 DarkGreen(prev_index) => prev.index_to_node(prev_index),
1065 e.emit_seq_elt(seq_index, |e| node.encode(e))?;
1072 e.emit_struct_field("fingerprints", 1, |e| {
1073 // `SerializedDepGraph` expects this to be encoded as a sequence of `Fingerprints`s.
1074 e.emit_seq(node_count, |e| {
1075 for (seq_index, &hybrid_index) in data.hybrid_indices.iter().enumerate() {
1076 let fingerprint: Fingerprint = match hybrid_index.into() {
1077 New(i) => new.fingerprints[i],
1078 Red(i) => red.fingerprints[i],
1079 LightGreen(i) => prev.fingerprint_by_index(lg.node_indices[i]),
1080 DarkGreen(prev_index) => prev.fingerprint_by_index(prev_index),
1083 e.emit_seq_elt(seq_index, |e| fingerprint.encode(e))?;
1090 e.emit_struct_field("edge_list_indices", 2, |e| {
1091 // `SerializedDepGraph` expects this to be encoded as a sequence of `(u32, u32)`s.
1092 e.emit_seq(node_count, |e| {
1093 // Dark green node edges start after the unshared (all other nodes') edges.
1094 let mut dark_green_edge_index = data.unshared_edges.len();
1096 for (seq_index, &hybrid_index) in data.hybrid_indices.iter().enumerate() {
1097 let edge_indices: (u32, u32) = match hybrid_index.into() {
1098 New(i) => (new.edges[i].start.as_u32(), new.edges[i].end.as_u32()),
1099 Red(i) => (red.edges[i].start.as_u32(), red.edges[i].end.as_u32()),
1100 LightGreen(i) => (lg.edges[i].start.as_u32(), lg.edges[i].end.as_u32()),
1101 DarkGreen(prev_index) => {
1102 let edge_count = prev.edge_targets_from(prev_index).len();
1103 let start = dark_green_edge_index as u32;
1104 dark_green_edge_index += edge_count;
1105 let end = dark_green_edge_index as u32;
1110 e.emit_seq_elt(seq_index, |e| edge_indices.encode(e))?;
1113 assert_eq!(dark_green_edge_index, edge_count);
1119 e.emit_struct_field("edge_list_data", 3, |e| {
1120 // `SerializedDepGraph` expects this to be encoded as a sequence of
1121 // `SerializedDepNodeIndex`.
1122 e.emit_seq(edge_count, |e| {
1123 for (seq_index, &edge) in data.unshared_edges.iter().enumerate() {
1124 let serialized_edge = SerializedDepNodeIndex::new(edge.index());
1125 e.emit_seq_elt(seq_index, |e| serialized_edge.encode(e))?;
1128 let mut seq_index = data.unshared_edges.len();
1130 for &hybrid_index in data.hybrid_indices.iter() {
1131 if let DarkGreen(prev_index) = hybrid_index.into() {
1132 for &edge in prev.edge_targets_from(prev_index) {
1133 // Dark green node edges are stored in the previous graph
1134 // and must be converted to edges in the current graph,
1135 // and then serialized as `SerializedDepNodeIndex`.
1136 let serialized_edge = SerializedDepNodeIndex::new(
1137 prev_index_to_index[edge].as_ref().unwrap().index(),
1140 e.emit_seq_elt(seq_index, |e| serialized_edge.encode(e))?;
1146 assert_eq!(seq_index, edge_count);
1155 /// A "work product" is an intermediate result that we save into the
1156 /// incremental directory for later re-use. The primary example are
1157 /// the object files that we save for each partition at code
1158 /// generation time.
1160 /// Each work product is associated with a dep-node, representing the
1161 /// process that produced the work-product. If that dep-node is found
1162 /// to be dirty when we load up, then we will delete the work-product
1163 /// at load time. If the work-product is found to be clean, then we
1164 /// will keep a record in the `previous_work_products` list.
1166 /// In addition, work products have an associated hash. This hash is
1167 /// an extra hash that can be used to decide if the work-product from
1168 /// a previous compilation can be re-used (in addition to the dirty
1171 /// As the primary example, consider the object files we generate for
1172 /// each partition. In the first run, we create partitions based on
1173 /// the symbols that need to be compiled. For each partition P, we
1174 /// hash the symbols in P and create a `WorkProduct` record associated
1175 /// with `DepNode::CodegenUnit(P)`; the hash is the set of symbols
1178 /// The next time we compile, if the `DepNode::CodegenUnit(P)` is
1179 /// judged to be clean (which means none of the things we read to
1180 /// generate the partition were found to be dirty), it will be loaded
1181 /// into previous work products. We will then regenerate the set of
1182 /// symbols in the partition P and hash them (note that new symbols
1183 /// may be added -- for example, new monomorphizations -- even if
1184 /// nothing in P changed!). We will compare that hash against the
1185 /// previous hash. If it matches up, we can reuse the object file.
1186 #[derive(Clone, Debug, Encodable, Decodable)]
1187 pub struct WorkProduct {
1188 pub cgu_name: String,
1189 /// Saved file associated with this CGU.
1190 pub saved_file: Option<String>,
1193 // The maximum value of the follow index types leaves the upper two bits unused
1194 // so that we can store multiple index types in `CompressedHybridIndex`, and use
1195 // those bits to encode which index type it contains.
1197 // Index type for `NewDepNodeData`.
1198 rustc_index::newtype_index! {
1199 struct NewDepNodeIndex {
1204 // Index type for `RedDepNodeData`.
1205 rustc_index::newtype_index! {
1206 struct RedDepNodeIndex {
1211 // Index type for `LightGreenDepNodeData`.
1212 rustc_index::newtype_index! {
1213 struct LightGreenDepNodeIndex {
1218 /// Compressed representation of `HybridIndex` enum. Bits unused by the
1219 /// contained index types are used to encode which index type it contains.
1220 #[derive(Copy, Clone)]
1221 struct CompressedHybridIndex(u32);
1223 impl CompressedHybridIndex {
1224 const NEW_TAG: u32 = 0b0000_0000_0000_0000_0000_0000_0000_0000;
1225 const RED_TAG: u32 = 0b0100_0000_0000_0000_0000_0000_0000_0000;
1226 const LIGHT_GREEN_TAG: u32 = 0b1000_0000_0000_0000_0000_0000_0000_0000;
1227 const DARK_GREEN_TAG: u32 = 0b1100_0000_0000_0000_0000_0000_0000_0000;
1229 const TAG_MASK: u32 = 0b1100_0000_0000_0000_0000_0000_0000_0000;
1230 const INDEX_MASK: u32 = !Self::TAG_MASK;
1233 impl From<NewDepNodeIndex> for CompressedHybridIndex {
1235 fn from(index: NewDepNodeIndex) -> Self {
1236 CompressedHybridIndex(Self::NEW_TAG | index.as_u32())
1240 impl From<RedDepNodeIndex> for CompressedHybridIndex {
1242 fn from(index: RedDepNodeIndex) -> Self {
1243 CompressedHybridIndex(Self::RED_TAG | index.as_u32())
1247 impl From<LightGreenDepNodeIndex> for CompressedHybridIndex {
1249 fn from(index: LightGreenDepNodeIndex) -> Self {
1250 CompressedHybridIndex(Self::LIGHT_GREEN_TAG | index.as_u32())
1254 impl From<SerializedDepNodeIndex> for CompressedHybridIndex {
1256 fn from(index: SerializedDepNodeIndex) -> Self {
1257 CompressedHybridIndex(Self::DARK_GREEN_TAG | index.as_u32())
1261 /// Contains an index into one of several node data collections. Elsewhere, we
1262 /// store `CompressedHyridIndex` instead of this to save space, but convert to
1263 /// this type during processing to take advantage of the enum match ergonomics.
1265 New(NewDepNodeIndex),
1266 Red(RedDepNodeIndex),
1267 LightGreen(LightGreenDepNodeIndex),
1268 DarkGreen(SerializedDepNodeIndex),
1271 impl From<CompressedHybridIndex> for HybridIndex {
1273 fn from(hybrid_index: CompressedHybridIndex) -> Self {
1274 let index = hybrid_index.0 & CompressedHybridIndex::INDEX_MASK;
1276 match hybrid_index.0 & CompressedHybridIndex::TAG_MASK {
1277 CompressedHybridIndex::NEW_TAG => HybridIndex::New(NewDepNodeIndex::from_u32(index)),
1278 CompressedHybridIndex::RED_TAG => HybridIndex::Red(RedDepNodeIndex::from_u32(index)),
1279 CompressedHybridIndex::LIGHT_GREEN_TAG => {
1280 HybridIndex::LightGreen(LightGreenDepNodeIndex::from_u32(index))
1282 CompressedHybridIndex::DARK_GREEN_TAG => {
1283 HybridIndex::DarkGreen(SerializedDepNodeIndex::from_u32(index))
1285 _ => unreachable!(),
1290 // Index type for `DepNodeData`'s edges.
1291 rustc_index::newtype_index! {
1292 struct EdgeIndex { .. }
1295 /// Data for nodes in the current graph, divided into different collections
1296 /// based on their presence in the previous graph, and if present, their color.
1297 /// We divide nodes this way because different types of nodes are able to share
1298 /// more or less data with the previous graph.
1300 /// To enable more sharing, we distinguish between two kinds of green nodes.
1301 /// Light green nodes are nodes in the previous graph that have been marked
1302 /// green because we re-executed their queries and the results were the same as
1303 /// in the previous session. Dark green nodes are nodes in the previous graph
1304 /// that have been marked green because we were able to mark all of their
1305 /// dependencies green.
1307 /// Both light and dark green nodes can share the dep node and fingerprint with
1308 /// the previous graph, but for light green nodes, we can't be sure that the
1309 /// edges may be shared without comparing them against the previous edges, so we
1310 /// store them directly (an approach in which we compare edges with the previous
1311 /// edges to see if they can be shared was evaluated, but was not found to be
1312 /// very profitable).
1314 /// For dark green nodes, we can share everything with the previous graph, which
1315 /// is why the `HybridIndex::DarkGreen` enum variant contains the index of the
1316 /// node in the previous graph, and why we don't have a separate collection for
1317 /// dark green node data--the collection is the `PreviousDepGraph` itself.
1319 /// (Note that for dark green nodes, the edges in the previous graph
1320 /// (`SerializedDepNodeIndex`s) must be converted to edges in the current graph
1321 /// (`DepNodeIndex`s). `CurrentDepGraph` contains `prev_index_to_index`, which
1322 /// can perform this conversion. It should always be possible, as by definition,
1323 /// a dark green node is one whose dependencies from the previous session have
1324 /// all been marked green--which means `prev_index_to_index` contains them.)
1326 /// Node data is stored in parallel vectors to eliminate the padding between
1327 /// elements that would be needed to satisfy alignment requirements of the
1328 /// structure that would contain all of a node's data. We could group tightly
1329 /// packing subsets of node data together and use fewer vectors, but for
1330 /// consistency's sake, we use separate vectors for each piece of data.
1331 struct DepNodeData<K> {
1332 /// Data for nodes not in previous graph.
1333 new: NewDepNodeData<K>,
1335 /// Data for nodes in previous graph that have been marked red.
1336 red: RedDepNodeData,
1338 /// Data for nodes in previous graph that have been marked light green.
1339 light_green: LightGreenDepNodeData,
1341 // Edges for all nodes other than dark-green ones. Edges for each node
1342 // occupy a contiguous region of this collection, which a node can reference
1343 // using two indices. Storing edges this way rather than using an `EdgesVec`
1344 // for each node reduces memory consumption by a not insignificant amount
1345 // when compiling large crates. The downside is that we have to copy into
1346 // this collection the edges from the `EdgesVec`s that are built up during
1347 // query execution. But this is mostly balanced out by the more efficient
1348 // implementation of `DepGraph::serialize` enabled by this representation.
1349 unshared_edges: IndexVec<EdgeIndex, DepNodeIndex>,
1351 /// Mapping from `DepNodeIndex` to an index into a collection above.
1352 /// Indicates which of the above collections contains a node's data.
1354 /// This collection is wasteful in time and space during incr-full builds,
1355 /// because for those, all nodes are new. However, the waste is relatively
1356 /// small, and the maintenance cost of avoiding using this for incr-full
1357 /// builds is somewhat high and prone to bugginess. It does not seem worth
1358 /// it at the time of this writing, but we may want to revisit the idea.
1359 hybrid_indices: IndexVec<DepNodeIndex, CompressedHybridIndex>,
1362 /// Data for nodes not in previous graph. Since we cannot share any data with
1363 /// the previous graph, so we must store all of such a node's data here.
1364 struct NewDepNodeData<K> {
1365 nodes: IndexVec<NewDepNodeIndex, DepNode<K>>,
1366 edges: IndexVec<NewDepNodeIndex, Range<EdgeIndex>>,
1367 fingerprints: IndexVec<NewDepNodeIndex, Fingerprint>,
1370 /// Data for nodes in previous graph that have been marked red. We can share the
1371 /// dep node with the previous graph, but the edges may be different, and the
1372 /// fingerprint is known to be different, so we store the latter two directly.
1373 struct RedDepNodeData {
1374 node_indices: IndexVec<RedDepNodeIndex, SerializedDepNodeIndex>,
1375 edges: IndexVec<RedDepNodeIndex, Range<EdgeIndex>>,
1376 fingerprints: IndexVec<RedDepNodeIndex, Fingerprint>,
1379 /// Data for nodes in previous graph that have been marked green because we
1380 /// re-executed their queries and the results were the same as in the previous
1381 /// session. We can share the dep node and the fingerprint with the previous
1382 /// graph, but the edges may be different, so we store them directly.
1383 struct LightGreenDepNodeData {
1384 node_indices: IndexVec<LightGreenDepNodeIndex, SerializedDepNodeIndex>,
1385 edges: IndexVec<LightGreenDepNodeIndex, Range<EdgeIndex>>,
1388 /// `CurrentDepGraph` stores the dependency graph for the current session. It
1389 /// will be populated as we run queries or tasks. We never remove nodes from the
1390 /// graph: they are only added.
1392 /// The nodes in it are identified by a `DepNodeIndex`. Internally, this maps to
1393 /// a `HybridIndex`, which identifies which collection in the `data` field
1394 /// contains a node's data. Which collection is used for a node depends on
1395 /// whether the node was present in the `PreviousDepGraph`, and if so, the color
1396 /// of the node. Each type of node can share more or less data with the previous
1397 /// graph. When possible, we can store just the index of the node in the
1398 /// previous graph, rather than duplicating its data in our own collections.
1399 /// This is important, because these graph structures are some of the largest in
1402 /// For the same reason, we also avoid storing `DepNode`s more than once as map
1403 /// keys. The `new_node_to_index` map only contains nodes not in the previous
1404 /// graph, and we map nodes in the previous graph to indices via a two-step
1405 /// mapping. `PreviousDepGraph` maps from `DepNode` to `SerializedDepNodeIndex`,
1406 /// and the `prev_index_to_index` vector (which is more compact and faster than
1407 /// using a map) maps from `SerializedDepNodeIndex` to `DepNodeIndex`.
1409 /// This struct uses three locks internally. The `data`, `new_node_to_index`,
1410 /// and `prev_index_to_index` fields are locked separately. Operations that take
1411 /// a `DepNodeIndex` typically just access the `data` field.
1413 /// We only need to manipulate at most two locks simultaneously:
1414 /// `new_node_to_index` and `data`, or `prev_index_to_index` and `data`. When
1415 /// manipulating both, we acquire `new_node_to_index` or `prev_index_to_index`
1416 /// first, and `data` second.
1417 pub(super) struct CurrentDepGraph<K> {
1418 data: Lock<DepNodeData<K>>,
1419 new_node_to_index: Sharded<FxHashMap<DepNode<K>, DepNodeIndex>>,
1420 prev_index_to_index: Lock<IndexVec<SerializedDepNodeIndex, Option<DepNodeIndex>>>,
1422 /// Used to trap when a specific edge is added to the graph.
1423 /// This is used for debug purposes and is only active with `debug_assertions`.
1425 forbidden_edge: Option<EdgeFilter>,
1427 /// Anonymous `DepNode`s are nodes whose IDs we compute from the list of
1428 /// their edges. This has the beneficial side-effect that multiple anonymous
1429 /// nodes can be coalesced into one without changing the semantics of the
1430 /// dependency graph. However, the merging of nodes can lead to a subtle
1431 /// problem during red-green marking: The color of an anonymous node from
1432 /// the current session might "shadow" the color of the node with the same
1433 /// ID from the previous session. In order to side-step this problem, we make
1434 /// sure that anonymous `NodeId`s allocated in different sessions don't overlap.
1435 /// This is implemented by mixing a session-key into the ID fingerprint of
1436 /// each anon node. The session-key is just a random number generated when
1437 /// the `DepGraph` is created.
1438 anon_id_seed: Fingerprint,
1440 /// These are simple counters that are for profiling and
1441 /// debugging and only active with `debug_assertions`.
1442 total_read_count: AtomicU64,
1443 total_duplicate_read_count: AtomicU64,
1446 impl<K: DepKind> CurrentDepGraph<K> {
1447 fn new(prev_graph_node_count: usize) -> CurrentDepGraph<K> {
1448 use std::time::{SystemTime, UNIX_EPOCH};
1450 let duration = SystemTime::now().duration_since(UNIX_EPOCH).unwrap();
1451 let nanos = duration.as_secs() * 1_000_000_000 + duration.subsec_nanos() as u64;
1452 let mut stable_hasher = StableHasher::new();
1453 nanos.hash(&mut stable_hasher);
1455 let forbidden_edge = if cfg!(debug_assertions) {
1456 match env::var("RUST_FORBID_DEP_GRAPH_EDGE") {
1457 Ok(s) => match EdgeFilter::new(&s) {
1459 Err(err) => panic!("RUST_FORBID_DEP_GRAPH_EDGE invalid: {}", err),
1467 // Pre-allocate the dep node structures. We over-allocate a little so
1468 // that we hopefully don't have to re-allocate during this compilation
1469 // session. The over-allocation for new nodes is 2% plus a small
1470 // constant to account for the fact that in very small crates 2% might
1471 // not be enough. The allocation for red and green node data doesn't
1472 // include a constant, as we don't want to allocate anything for these
1473 // structures during full incremental builds, where they aren't used.
1475 // These estimates are based on the distribution of node and edge counts
1476 // seen in rustc-perf benchmarks, adjusted somewhat to account for the
1477 // fact that these benchmarks aren't perfectly representative.
1479 // FIXME Use a collection type that doesn't copy node and edge data and
1480 // grow multiplicatively on reallocation. Without such a collection or
1481 // solution having the same effect, there is a performance hazard here
1482 // in both time and space, as growing these collections means copying a
1483 // large amount of data and doubling already large buffer capacities. A
1484 // solution for this will also mean that it's less important to get
1485 // these estimates right.
1486 let new_node_count_estimate = (prev_graph_node_count * 2) / 100 + 200;
1487 let red_node_count_estimate = (prev_graph_node_count * 3) / 100;
1488 let light_green_node_count_estimate = (prev_graph_node_count * 25) / 100;
1489 let total_node_count_estimate = prev_graph_node_count + new_node_count_estimate;
1491 let average_edges_per_node_estimate = 6;
1492 let unshared_edge_count_estimate = average_edges_per_node_estimate
1493 * (new_node_count_estimate + red_node_count_estimate + light_green_node_count_estimate);
1495 // We store a large collection of these in `prev_index_to_index` during
1496 // non-full incremental builds, and want to ensure that the element size
1497 // doesn't inadvertently increase.
1498 static_assert_size!(Option<DepNodeIndex>, 4);
1501 data: Lock::new(DepNodeData {
1502 new: NewDepNodeData {
1503 nodes: IndexVec::with_capacity(new_node_count_estimate),
1504 edges: IndexVec::with_capacity(new_node_count_estimate),
1505 fingerprints: IndexVec::with_capacity(new_node_count_estimate),
1507 red: RedDepNodeData {
1508 node_indices: IndexVec::with_capacity(red_node_count_estimate),
1509 edges: IndexVec::with_capacity(red_node_count_estimate),
1510 fingerprints: IndexVec::with_capacity(red_node_count_estimate),
1512 light_green: LightGreenDepNodeData {
1513 node_indices: IndexVec::with_capacity(light_green_node_count_estimate),
1514 edges: IndexVec::with_capacity(light_green_node_count_estimate),
1516 unshared_edges: IndexVec::with_capacity(unshared_edge_count_estimate),
1517 hybrid_indices: IndexVec::with_capacity(total_node_count_estimate),
1519 new_node_to_index: Sharded::new(|| {
1520 FxHashMap::with_capacity_and_hasher(
1521 new_node_count_estimate / sharded::SHARDS,
1525 prev_index_to_index: Lock::new(IndexVec::from_elem_n(None, prev_graph_node_count)),
1526 anon_id_seed: stable_hasher.finish(),
1528 total_read_count: AtomicU64::new(0),
1529 total_duplicate_read_count: AtomicU64::new(0),
1535 prev_graph: &PreviousDepGraph<K>,
1536 dep_node: DepNode<K>,
1538 fingerprint: Fingerprint,
1541 prev_graph.node_to_index_opt(&dep_node).is_none(),
1542 "node in previous graph should be interned using one \
1543 of `intern_red_node`, `intern_light_green_node`, etc."
1546 match self.new_node_to_index.get_shard_by_value(&dep_node).lock().entry(dep_node) {
1547 Entry::Occupied(entry) => *entry.get(),
1548 Entry::Vacant(entry) => {
1549 let data = &mut *self.data.lock();
1550 let new_index = data.new.nodes.push(dep_node);
1551 add_edges(&mut data.unshared_edges, &mut data.new.edges, edges);
1552 data.new.fingerprints.push(fingerprint);
1553 let dep_node_index = data.hybrid_indices.push(new_index.into());
1554 entry.insert(dep_node_index);
1562 prev_graph: &PreviousDepGraph<K>,
1563 prev_index: SerializedDepNodeIndex,
1565 fingerprint: Fingerprint,
1567 self.debug_assert_not_in_new_nodes(prev_graph, prev_index);
1569 let mut prev_index_to_index = self.prev_index_to_index.lock();
1571 match prev_index_to_index[prev_index] {
1572 Some(dep_node_index) => dep_node_index,
1574 let data = &mut *self.data.lock();
1575 let red_index = data.red.node_indices.push(prev_index);
1576 add_edges(&mut data.unshared_edges, &mut data.red.edges, edges);
1577 data.red.fingerprints.push(fingerprint);
1578 let dep_node_index = data.hybrid_indices.push(red_index.into());
1579 prev_index_to_index[prev_index] = Some(dep_node_index);
1585 fn intern_light_green_node(
1587 prev_graph: &PreviousDepGraph<K>,
1588 prev_index: SerializedDepNodeIndex,
1591 self.debug_assert_not_in_new_nodes(prev_graph, prev_index);
1593 let mut prev_index_to_index = self.prev_index_to_index.lock();
1595 match prev_index_to_index[prev_index] {
1596 Some(dep_node_index) => dep_node_index,
1598 let data = &mut *self.data.lock();
1599 let light_green_index = data.light_green.node_indices.push(prev_index);
1600 add_edges(&mut data.unshared_edges, &mut data.light_green.edges, edges);
1601 let dep_node_index = data.hybrid_indices.push(light_green_index.into());
1602 prev_index_to_index[prev_index] = Some(dep_node_index);
1608 fn intern_dark_green_node(
1610 prev_graph: &PreviousDepGraph<K>,
1611 prev_index: SerializedDepNodeIndex,
1613 self.debug_assert_not_in_new_nodes(prev_graph, prev_index);
1615 let mut prev_index_to_index = self.prev_index_to_index.lock();
1617 match prev_index_to_index[prev_index] {
1618 Some(dep_node_index) => dep_node_index,
1620 let mut data = self.data.lock();
1621 let dep_node_index = data.hybrid_indices.push(prev_index.into());
1622 prev_index_to_index[prev_index] = Some(dep_node_index);
1629 fn debug_assert_not_in_new_nodes(
1631 prev_graph: &PreviousDepGraph<K>,
1632 prev_index: SerializedDepNodeIndex,
1634 let node = &prev_graph.index_to_node(prev_index);
1636 !self.new_node_to_index.get_shard_by_value(node).lock().contains_key(node),
1637 "node from previous graph present in new node collection"
1643 fn add_edges<I: Idx>(
1644 edges: &mut IndexVec<EdgeIndex, DepNodeIndex>,
1645 edge_indices: &mut IndexVec<I, Range<EdgeIndex>>,
1646 new_edges: EdgesVec,
1648 let start = edges.next_index();
1649 edges.extend(new_edges);
1650 let end = edges.next_index();
1651 edge_indices.push(start..end);
1654 /// The capacity of the `reads` field `SmallVec`
1655 const TASK_DEPS_READS_CAP: usize = 8;
1656 type EdgesVec = SmallVec<[DepNodeIndex; TASK_DEPS_READS_CAP]>;
1658 pub struct TaskDeps<K> {
1659 #[cfg(debug_assertions)]
1660 node: Option<DepNode<K>>,
1662 read_set: FxHashSet<DepNodeIndex>,
1663 phantom_data: PhantomData<DepNode<K>>,
1666 impl<K> Default for TaskDeps<K> {
1667 fn default() -> Self {
1669 #[cfg(debug_assertions)]
1671 reads: EdgesVec::new(),
1672 read_set: FxHashSet::default(),
1673 phantom_data: PhantomData,
1678 // A data structure that stores Option<DepNodeColor> values as a contiguous
1679 // array, using one u32 per entry.
1680 struct DepNodeColorMap {
1681 values: IndexVec<SerializedDepNodeIndex, AtomicU32>,
1684 const COMPRESSED_NONE: u32 = 0;
1685 const COMPRESSED_RED: u32 = 1;
1686 const COMPRESSED_FIRST_GREEN: u32 = 2;
1688 impl DepNodeColorMap {
1689 fn new(size: usize) -> DepNodeColorMap {
1690 DepNodeColorMap { values: (0..size).map(|_| AtomicU32::new(COMPRESSED_NONE)).collect() }
1694 fn get(&self, index: SerializedDepNodeIndex) -> Option<DepNodeColor> {
1695 match self.values[index].load(Ordering::Acquire) {
1696 COMPRESSED_NONE => None,
1697 COMPRESSED_RED => Some(DepNodeColor::Red),
1699 Some(DepNodeColor::Green(DepNodeIndex::from_u32(value - COMPRESSED_FIRST_GREEN)))
1704 fn insert(&self, index: SerializedDepNodeIndex, color: DepNodeColor) {
1705 self.values[index].store(
1707 DepNodeColor::Red => COMPRESSED_RED,
1708 DepNodeColor::Green(index) => index.as_u32() + COMPRESSED_FIRST_GREEN,