1 use crate::ty::{self, TyCtxt};
2 use errors::Diagnostic;
3 use parking_lot::{Condvar, Mutex};
4 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
5 use rustc_data_structures::sharded::{self, Sharded};
6 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
7 use rustc_data_structures::sync::{AtomicU32, AtomicU64, Lock, Lrc, Ordering};
8 use rustc_index::vec::{Idx, IndexVec};
9 use smallvec::SmallVec;
10 use std::collections::hash_map::Entry;
14 use std::sync::atomic::Ordering::SeqCst;
16 use crate::ich::{Fingerprint, StableHashingContext, StableHashingContextProvider};
18 use super::debug::EdgeFilter;
19 use super::dep_node::{DepKind, DepNode, WorkProductId};
20 use super::prev::PreviousDepGraph;
21 use super::query::DepGraphQuery;
22 use super::safe::DepGraphSafe;
23 use super::serialized::{SerializedDepGraph, SerializedDepNodeIndex};
27 data: Option<Lrc<DepGraphData>>,
30 rustc_index::newtype_index! {
31 pub struct DepNodeIndex { .. }
35 pub const INVALID: DepNodeIndex = DepNodeIndex::MAX;
39 pub enum DepNodeColor {
45 pub fn is_green(self) -> bool {
47 DepNodeColor::Red => false,
48 DepNodeColor::Green(_) => true,
54 /// The new encoding of the dependency graph, optimized for red/green
55 /// tracking. The `current` field is the dependency graph of only the
56 /// current compilation session: We don't merge the previous dep-graph into
57 /// current one anymore.
58 current: CurrentDepGraph,
60 /// The dep-graph from the previous compilation session. It contains all
61 /// nodes and edges as well as all fingerprints of nodes that have them.
62 previous: PreviousDepGraph,
64 colors: DepNodeColorMap,
66 /// A set of loaded diagnostics that is in the progress of being emitted.
67 emitting_diagnostics: Mutex<FxHashSet<DepNodeIndex>>,
69 /// Used to wait for diagnostics to be emitted.
70 emitting_diagnostics_cond_var: Condvar,
72 /// When we load, there may be `.o` files, cached MIR, or other such
73 /// things available to us. If we find that they are not dirty, we
74 /// load the path to the file storing those work-products here into
75 /// this map. We can later look for and extract that data.
76 previous_work_products: FxHashMap<WorkProductId, WorkProduct>,
78 dep_node_debug: Lock<FxHashMap<DepNode, String>>,
81 pub fn hash_result<R>(hcx: &mut StableHashingContext<'_>, result: &R) -> Option<Fingerprint>
83 R: for<'a> HashStable<StableHashingContext<'a>>,
85 let mut stable_hasher = StableHasher::new();
86 result.hash_stable(hcx, &mut stable_hasher);
88 Some(stable_hasher.finish())
93 prev_graph: PreviousDepGraph,
94 prev_work_products: FxHashMap<WorkProductId, WorkProduct>,
96 let prev_graph_node_count = prev_graph.node_count();
99 data: Some(Lrc::new(DepGraphData {
100 previous_work_products: prev_work_products,
101 dep_node_debug: Default::default(),
102 current: CurrentDepGraph::new(prev_graph_node_count),
103 emitting_diagnostics: Default::default(),
104 emitting_diagnostics_cond_var: Condvar::new(),
105 previous: prev_graph,
106 colors: DepNodeColorMap::new(prev_graph_node_count),
111 pub fn new_disabled() -> DepGraph {
112 DepGraph { data: None }
115 /// Returns `true` if we are actually building the full dep-graph, and `false` otherwise.
117 pub fn is_fully_enabled(&self) -> bool {
121 pub fn query(&self) -> DepGraphQuery {
122 let data = self.data.as_ref().unwrap().current.data.lock();
123 let nodes: Vec<_> = data.iter().map(|n| n.node).collect();
124 let mut edges = Vec::new();
125 for (from, edge_targets) in data.iter().map(|d| (d.node, &d.edges)) {
126 for &edge_target in edge_targets.iter() {
127 let to = data[edge_target].node;
128 edges.push((from, to));
132 DepGraphQuery::new(&nodes[..], &edges[..])
135 pub fn assert_ignored(&self) {
136 if let Some(..) = self.data {
137 ty::tls::with_context_opt(|icx| {
138 let icx = if let Some(icx) = icx { icx } else { return };
139 assert!(icx.task_deps.is_none(), "expected no task dependency tracking");
144 pub fn with_ignore<OP, R>(&self, op: OP) -> R
148 ty::tls::with_context(|icx| {
149 let icx = ty::tls::ImplicitCtxt { task_deps: None, ..icx.clone() };
151 ty::tls::enter_context(&icx, |_| op())
155 /// Starts a new dep-graph task. Dep-graph tasks are specified
156 /// using a free function (`task`) and **not** a closure -- this
157 /// is intentional because we want to exercise tight control over
158 /// what state they have access to. In particular, we want to
159 /// prevent implicit 'leaks' of tracked state into the task (which
160 /// could then be read without generating correct edges in the
161 /// dep-graph -- see the [rustc guide] for more details on
162 /// the dep-graph). To this end, the task function gets exactly two
163 /// pieces of state: the context `cx` and an argument `arg`. Both
164 /// of these bits of state must be of some type that implements
165 /// `DepGraphSafe` and hence does not leak.
167 /// The choice of two arguments is not fundamental. One argument
168 /// would work just as well, since multiple values can be
169 /// collected using tuples. However, using two arguments works out
170 /// to be quite convenient, since it is common to need a context
171 /// (`cx`) and some argument (e.g., a `DefId` identifying what
172 /// item to process).
174 /// For cases where you need some other number of arguments:
176 /// - If you only need one argument, just use `()` for the `arg`
178 /// - If you need 3+ arguments, use a tuple for the
181 /// [rustc guide]: https://rust-lang.github.io/rustc-guide/incremental-compilation.html
182 pub fn with_task<'a, C, A, R>(
188 hash_result: impl FnOnce(&mut StableHashingContext<'_>, &R) -> Option<Fingerprint>,
189 ) -> (R, DepNodeIndex)
191 C: DepGraphSafe + StableHashingContextProvider<'a>,
201 #[cfg(debug_assertions)]
203 reads: SmallVec::new(),
204 read_set: Default::default(),
207 |data, key, fingerprint, task| data.complete_task(key, task.unwrap(), fingerprint),
212 /// Creates a new dep-graph input with value `input`
213 pub fn input_task<'a, C, R>(&self, key: DepNode, cx: C, input: R) -> (R, DepNodeIndex)
215 C: DepGraphSafe + StableHashingContextProvider<'a>,
216 R: for<'b> HashStable<StableHashingContext<'b>>,
218 fn identity_fn<C, A>(_: C, arg: A) -> A {
229 |data, key, fingerprint, _| data.alloc_node(key, SmallVec::new(), fingerprint),
234 fn with_task_impl<'a, C, A, R>(
241 create_task: fn(DepNode) -> Option<TaskDeps>,
242 finish_task_and_alloc_depnode: fn(
248 hash_result: impl FnOnce(&mut StableHashingContext<'_>, &R) -> Option<Fingerprint>,
249 ) -> (R, DepNodeIndex)
251 C: DepGraphSafe + StableHashingContextProvider<'a>,
253 if let Some(ref data) = self.data {
254 let task_deps = create_task(key).map(|deps| Lock::new(deps));
256 // In incremental mode, hash the result of the task. We don't
257 // do anything with the hash yet, but we are computing it
259 // - we make sure that the infrastructure works and
260 // - we can get an idea of the runtime cost.
261 let mut hcx = cx.get_stable_hashing_context();
263 let result = if no_tcx {
266 ty::tls::with_context(|icx| {
268 ty::tls::ImplicitCtxt { task_deps: task_deps.as_ref(), ..icx.clone() };
270 ty::tls::enter_context(&icx, |_| task(cx, arg))
274 let current_fingerprint = hash_result(&mut hcx, &result);
276 let dep_node_index = finish_task_and_alloc_depnode(
279 current_fingerprint.unwrap_or(Fingerprint::ZERO),
280 task_deps.map(|lock| lock.into_inner()),
283 let print_status = cfg!(debug_assertions) && hcx.sess().opts.debugging_opts.dep_tasks;
285 // Determine the color of the new DepNode.
286 if let Some(prev_index) = data.previous.node_to_index_opt(&key) {
287 let prev_fingerprint = data.previous.fingerprint_by_index(prev_index);
289 let color = if let Some(current_fingerprint) = current_fingerprint {
290 if current_fingerprint == prev_fingerprint {
292 eprintln!("[task::green] {:?}", key);
294 DepNodeColor::Green(dep_node_index)
297 eprintln!("[task::red] {:?}", key);
303 eprintln!("[task::unknown] {:?}", key);
305 // Mark the node as Red if we can't hash the result
310 data.colors.get(prev_index).is_none(),
311 "DepGraph::with_task() - Duplicate DepNodeColor \
316 data.colors.insert(prev_index, color);
319 eprintln!("[task::new] {:?}", key);
323 (result, dep_node_index)
325 (task(cx, arg), DepNodeIndex::INVALID)
329 /// Executes something within an "anonymous" task, that is, a task the
330 /// `DepNode` of which is determined by the list of inputs it read from.
331 pub fn with_anon_task<OP, R>(&self, dep_kind: DepKind, op: OP) -> (R, DepNodeIndex)
335 if let Some(ref data) = self.data {
336 let (result, task_deps) = ty::tls::with_context(|icx| {
337 let task_deps = Lock::new(TaskDeps {
338 #[cfg(debug_assertions)]
340 reads: SmallVec::new(),
341 read_set: Default::default(),
345 let icx = ty::tls::ImplicitCtxt { task_deps: Some(&task_deps), ..icx.clone() };
347 ty::tls::enter_context(&icx, |_| op())
350 (r, task_deps.into_inner())
352 let dep_node_index = data.current.complete_anon_task(dep_kind, task_deps);
353 (result, dep_node_index)
355 (op(), DepNodeIndex::INVALID)
359 /// Executes something within an "eval-always" task which is a task
360 /// that runs whenever anything changes.
361 pub fn with_eval_always_task<'a, C, A, R>(
367 hash_result: impl FnOnce(&mut StableHashingContext<'_>, &R) -> Option<Fingerprint>,
368 ) -> (R, DepNodeIndex)
370 C: DepGraphSafe + StableHashingContextProvider<'a>,
379 |data, key, fingerprint, _| data.alloc_node(key, smallvec![], fingerprint),
385 pub fn read(&self, v: DepNode) {
386 if let Some(ref data) = self.data {
387 let map = data.current.node_to_node_index.get_shard_by_value(&v).lock();
388 if let Some(dep_node_index) = map.get(&v).copied() {
390 data.read_index(dep_node_index);
392 bug!("DepKind {:?} should be pre-allocated but isn't.", v.kind)
398 pub fn read_index(&self, dep_node_index: DepNodeIndex) {
399 if let Some(ref data) = self.data {
400 data.read_index(dep_node_index);
405 pub fn dep_node_index_of(&self, dep_node: &DepNode) -> DepNodeIndex {
411 .get_shard_by_value(dep_node)
419 pub fn dep_node_exists(&self, dep_node: &DepNode) -> bool {
420 if let Some(ref data) = self.data {
423 .get_shard_by_value(&dep_node)
425 .contains_key(dep_node)
432 pub fn fingerprint_of(&self, dep_node_index: DepNodeIndex) -> Fingerprint {
433 let data = self.data.as_ref().expect("dep graph enabled").current.data.lock();
434 data[dep_node_index].fingerprint
437 pub fn prev_fingerprint_of(&self, dep_node: &DepNode) -> Option<Fingerprint> {
438 self.data.as_ref().unwrap().previous.fingerprint_of(dep_node)
442 pub fn prev_dep_node_index_of(&self, dep_node: &DepNode) -> SerializedDepNodeIndex {
443 self.data.as_ref().unwrap().previous.node_to_index(dep_node)
446 /// Checks whether a previous work product exists for `v` and, if
447 /// so, return the path that leads to it. Used to skip doing work.
448 pub fn previous_work_product(&self, v: &WorkProductId) -> Option<WorkProduct> {
449 self.data.as_ref().and_then(|data| data.previous_work_products.get(v).cloned())
452 /// Access the map of work-products created during the cached run. Only
453 /// used during saving of the dep-graph.
454 pub fn previous_work_products(&self) -> &FxHashMap<WorkProductId, WorkProduct> {
455 &self.data.as_ref().unwrap().previous_work_products
459 pub fn register_dep_node_debug_str<F>(&self, dep_node: DepNode, debug_str_gen: F)
461 F: FnOnce() -> String,
463 let dep_node_debug = &self.data.as_ref().unwrap().dep_node_debug;
465 if dep_node_debug.borrow().contains_key(&dep_node) {
468 let debug_str = debug_str_gen();
469 dep_node_debug.borrow_mut().insert(dep_node, debug_str);
472 pub(super) fn dep_node_debug_str(&self, dep_node: DepNode) -> Option<String> {
473 self.data.as_ref()?.dep_node_debug.borrow().get(&dep_node).cloned()
476 pub fn edge_deduplication_data(&self) -> Option<(u64, u64)> {
477 if cfg!(debug_assertions) {
478 let current_dep_graph = &self.data.as_ref().unwrap().current;
481 current_dep_graph.total_read_count.load(SeqCst),
482 current_dep_graph.total_duplicate_read_count.load(SeqCst),
489 pub fn serialize(&self) -> SerializedDepGraph {
490 let data = self.data.as_ref().unwrap().current.data.lock();
492 let fingerprints: IndexVec<SerializedDepNodeIndex, _> =
493 data.iter().map(|d| d.fingerprint).collect();
494 let nodes: IndexVec<SerializedDepNodeIndex, _> = data.iter().map(|d| d.node).collect();
496 let total_edge_count: usize = data.iter().map(|d| d.edges.len()).sum();
498 let mut edge_list_indices = IndexVec::with_capacity(nodes.len());
499 let mut edge_list_data = Vec::with_capacity(total_edge_count);
501 for (current_dep_node_index, edges) in data.iter_enumerated().map(|(i, d)| (i, &d.edges)) {
502 let start = edge_list_data.len() as u32;
503 // This should really just be a memcpy :/
504 edge_list_data.extend(edges.iter().map(|i| SerializedDepNodeIndex::new(i.index())));
505 let end = edge_list_data.len() as u32;
507 debug_assert_eq!(current_dep_node_index.index(), edge_list_indices.len());
508 edge_list_indices.push((start, end));
511 debug_assert!(edge_list_data.len() <= ::std::u32::MAX as usize);
512 debug_assert_eq!(edge_list_data.len(), total_edge_count);
514 SerializedDepGraph { nodes, fingerprints, edge_list_indices, edge_list_data }
517 pub fn node_color(&self, dep_node: &DepNode) -> Option<DepNodeColor> {
518 if let Some(ref data) = self.data {
519 if let Some(prev_index) = data.previous.node_to_index_opt(dep_node) {
520 return data.colors.get(prev_index);
522 // This is a node that did not exist in the previous compilation
523 // session, so we consider it to be red.
524 return Some(DepNodeColor::Red);
531 /// Try to read a node index for the node dep_node.
532 /// A node will have an index, when it's already been marked green, or when we can mark it
533 /// green. This function will mark the current task as a reader of the specified node, when
534 /// a node index can be found for that node.
535 pub fn try_mark_green_and_read(
539 ) -> Option<(SerializedDepNodeIndex, DepNodeIndex)> {
540 self.try_mark_green(tcx, dep_node).map(|(prev_index, dep_node_index)| {
541 debug_assert!(self.is_green(&dep_node));
542 self.read_index(dep_node_index);
543 (prev_index, dep_node_index)
547 pub fn try_mark_green(
551 ) -> Option<(SerializedDepNodeIndex, DepNodeIndex)> {
552 debug_assert!(!dep_node.kind.is_eval_always());
554 // Return None if the dep graph is disabled
555 let data = self.data.as_ref()?;
557 // Return None if the dep node didn't exist in the previous session
558 let prev_index = data.previous.node_to_index_opt(dep_node)?;
560 match data.colors.get(prev_index) {
561 Some(DepNodeColor::Green(dep_node_index)) => Some((prev_index, dep_node_index)),
562 Some(DepNodeColor::Red) => None,
564 // This DepNode and the corresponding query invocation existed
565 // in the previous compilation session too, so we can try to
566 // mark it as green by recursively marking all of its
567 // dependencies green.
568 self.try_mark_previous_green(tcx, data, prev_index, &dep_node)
569 .map(|dep_node_index| (prev_index, dep_node_index))
574 /// Try to mark a dep-node which existed in the previous compilation session as green.
575 fn try_mark_previous_green<'tcx>(
579 prev_dep_node_index: SerializedDepNodeIndex,
581 ) -> Option<DepNodeIndex> {
582 debug!("try_mark_previous_green({:?}) - BEGIN", dep_node);
584 #[cfg(not(parallel_compiler))]
590 .get_shard_by_value(dep_node)
592 .contains_key(dep_node)
594 debug_assert!(data.colors.get(prev_dep_node_index).is_none());
597 // We never try to mark eval_always nodes as green
598 debug_assert!(!dep_node.kind.is_eval_always());
600 debug_assert_eq!(data.previous.index_to_node(prev_dep_node_index), *dep_node);
602 let prev_deps = data.previous.edge_targets_from(prev_dep_node_index);
604 let mut current_deps = SmallVec::new();
606 for &dep_dep_node_index in prev_deps {
607 let dep_dep_node_color = data.colors.get(dep_dep_node_index);
609 match dep_dep_node_color {
610 Some(DepNodeColor::Green(node_index)) => {
611 // This dependency has been marked as green before, we are
612 // still fine and can continue with checking the other
615 "try_mark_previous_green({:?}) --- found dependency {:?} to \
616 be immediately green",
618 data.previous.index_to_node(dep_dep_node_index)
620 current_deps.push(node_index);
622 Some(DepNodeColor::Red) => {
623 // We found a dependency the value of which has changed
624 // compared to the previous compilation session. We cannot
625 // mark the DepNode as green and also don't need to bother
626 // with checking any of the other dependencies.
628 "try_mark_previous_green({:?}) - END - dependency {:?} was \
631 data.previous.index_to_node(dep_dep_node_index)
636 let dep_dep_node = &data.previous.index_to_node(dep_dep_node_index);
638 // We don't know the state of this dependency. If it isn't
639 // an eval_always node, let's try to mark it green recursively.
640 if !dep_dep_node.kind.is_eval_always() {
642 "try_mark_previous_green({:?}) --- state of dependency {:?} \
643 is unknown, trying to mark it green",
644 dep_node, dep_dep_node
647 let node_index = self.try_mark_previous_green(
653 if let Some(node_index) = node_index {
655 "try_mark_previous_green({:?}) --- managed to MARK \
656 dependency {:?} as green",
657 dep_node, dep_dep_node
659 current_deps.push(node_index);
663 match dep_dep_node.kind {
664 DepKind::Hir | DepKind::HirBody | DepKind::CrateMetadata => {
665 if dep_dep_node.extract_def_id(tcx).is_none() {
666 // If the node does not exist anymore, we
667 // just fail to mark green.
670 // If the node does exist, it should have
671 // been pre-allocated.
673 "DepNode {:?} should have been \
674 pre-allocated but wasn't.",
680 // For other kinds of nodes it's OK to be
686 // We failed to mark it green, so we try to force the query.
688 "try_mark_previous_green({:?}) --- trying to force \
690 dep_node, dep_dep_node
692 if crate::ty::query::force_from_dep_node(tcx, dep_dep_node) {
693 let dep_dep_node_color = data.colors.get(dep_dep_node_index);
695 match dep_dep_node_color {
696 Some(DepNodeColor::Green(node_index)) => {
698 "try_mark_previous_green({:?}) --- managed to \
699 FORCE dependency {:?} to green",
700 dep_node, dep_dep_node
702 current_deps.push(node_index);
704 Some(DepNodeColor::Red) => {
706 "try_mark_previous_green({:?}) - END - \
707 dependency {:?} was red after forcing",
708 dep_node, dep_dep_node
713 if !tcx.sess.has_errors_or_delayed_span_bugs() {
715 "try_mark_previous_green() - Forcing the DepNode \
716 should have set its color"
719 // If the query we just forced has resulted in
720 // some kind of compilation error, we cannot rely on
721 // the dep-node color having been properly updated.
722 // This means that the query system has reached an
723 // invalid state. We let the compiler continue (by
724 // returning `None`) so it can emit error messages
725 // and wind down, but rely on the fact that this
726 // invalid state will not be persisted to the
727 // incremental compilation cache because of
728 // compilation errors being present.
730 "try_mark_previous_green({:?}) - END - \
731 dependency {:?} resulted in compilation error",
732 dep_node, dep_dep_node
739 // The DepNode could not be forced.
741 "try_mark_previous_green({:?}) - END - dependency {:?} \
742 could not be forced",
743 dep_node, dep_dep_node
751 // If we got here without hitting a `return` that means that all
752 // dependencies of this DepNode could be marked as green. Therefore we
753 // can also mark this DepNode as green.
755 // There may be multiple threads trying to mark the same dep node green concurrently
757 let dep_node_index = {
758 // Copy the fingerprint from the previous graph,
759 // so we don't have to recompute it
760 let fingerprint = data.previous.fingerprint_by_index(prev_dep_node_index);
762 // We allocating an entry for the node in the current dependency graph and
763 // adding all the appropriate edges imported from the previous graph
764 data.current.intern_node(*dep_node, current_deps, fingerprint)
767 // ... emitting any stored diagnostic ...
769 // FIXME: Store the fact that a node has diagnostics in a bit in the dep graph somewhere
770 // Maybe store a list on disk and encode this fact in the DepNodeState
771 let diagnostics = tcx.queries.on_disk_cache.load_diagnostics(tcx, prev_dep_node_index);
773 #[cfg(not(parallel_compiler))]
775 data.colors.get(prev_dep_node_index).is_none(),
776 "DepGraph::try_mark_previous_green() - Duplicate DepNodeColor \
781 if unlikely!(diagnostics.len() > 0) {
782 self.emit_diagnostics(tcx, data, dep_node_index, prev_dep_node_index, diagnostics);
785 // ... and finally storing a "Green" entry in the color map.
786 // Multiple threads can all write the same color here
787 data.colors.insert(prev_dep_node_index, DepNodeColor::Green(dep_node_index));
789 debug!("try_mark_previous_green({:?}) - END - successfully marked as green", dep_node);
793 /// Atomically emits some loaded diagnostics.
794 /// This may be called concurrently on multiple threads for the same dep node.
797 fn emit_diagnostics<'tcx>(
801 dep_node_index: DepNodeIndex,
802 prev_dep_node_index: SerializedDepNodeIndex,
803 diagnostics: Vec<Diagnostic>,
805 let mut emitting = data.emitting_diagnostics.lock();
807 if data.colors.get(prev_dep_node_index) == Some(DepNodeColor::Green(dep_node_index)) {
808 // The node is already green so diagnostics must have been emitted already
812 if emitting.insert(dep_node_index) {
813 // We were the first to insert the node in the set so this thread
814 // must emit the diagnostics and signal other potentially waiting
818 // Promote the previous diagnostics to the current session.
819 tcx.queries.on_disk_cache.store_diagnostics(dep_node_index, diagnostics.clone().into());
821 let handle = tcx.sess.diagnostic();
823 for diagnostic in diagnostics {
824 handle.emit_diagnostic(&diagnostic);
827 // Mark the node as green now that diagnostics are emitted
828 data.colors.insert(prev_dep_node_index, DepNodeColor::Green(dep_node_index));
830 // Remove the node from the set
831 data.emitting_diagnostics.lock().remove(&dep_node_index);
834 data.emitting_diagnostics_cond_var.notify_all();
836 // We must wait for the other thread to finish emitting the diagnostic
839 data.emitting_diagnostics_cond_var.wait(&mut emitting);
840 if data.colors.get(prev_dep_node_index) == Some(DepNodeColor::Green(dep_node_index))
848 // Returns true if the given node has been marked as green during the
849 // current compilation session. Used in various assertions
850 pub fn is_green(&self, dep_node: &DepNode) -> bool {
851 self.node_color(dep_node).map(|c| c.is_green()).unwrap_or(false)
854 // This method loads all on-disk cacheable query results into memory, so
855 // they can be written out to the new cache file again. Most query results
856 // will already be in memory but in the case where we marked something as
857 // green but then did not need the value, that value will never have been
860 // This method will only load queries that will end up in the disk cache.
861 // Other queries will not be executed.
862 pub fn exec_cache_promotions(&self, tcx: TyCtxt<'_>) {
863 let _prof_timer = tcx.prof.generic_activity("incr_comp_query_cache_promotion");
865 let data = self.data.as_ref().unwrap();
866 for prev_index in data.colors.values.indices() {
867 match data.colors.get(prev_index) {
868 Some(DepNodeColor::Green(_)) => {
869 let dep_node = data.previous.index_to_node(prev_index);
870 dep_node.try_load_from_on_disk_cache(tcx);
872 None | Some(DepNodeColor::Red) => {
873 // We can skip red nodes because a node can only be marked
874 // as red if the query result was recomputed and thus is
875 // already in memory.
882 /// A "work product" is an intermediate result that we save into the
883 /// incremental directory for later re-use. The primary example are
884 /// the object files that we save for each partition at code
887 /// Each work product is associated with a dep-node, representing the
888 /// process that produced the work-product. If that dep-node is found
889 /// to be dirty when we load up, then we will delete the work-product
890 /// at load time. If the work-product is found to be clean, then we
891 /// will keep a record in the `previous_work_products` list.
893 /// In addition, work products have an associated hash. This hash is
894 /// an extra hash that can be used to decide if the work-product from
895 /// a previous compilation can be re-used (in addition to the dirty
898 /// As the primary example, consider the object files we generate for
899 /// each partition. In the first run, we create partitions based on
900 /// the symbols that need to be compiled. For each partition P, we
901 /// hash the symbols in P and create a `WorkProduct` record associated
902 /// with `DepNode::CodegenUnit(P)`; the hash is the set of symbols
905 /// The next time we compile, if the `DepNode::CodegenUnit(P)` is
906 /// judged to be clean (which means none of the things we read to
907 /// generate the partition were found to be dirty), it will be loaded
908 /// into previous work products. We will then regenerate the set of
909 /// symbols in the partition P and hash them (note that new symbols
910 /// may be added -- for example, new monomorphizations -- even if
911 /// nothing in P changed!). We will compare that hash against the
912 /// previous hash. If it matches up, we can reuse the object file.
913 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
914 pub struct WorkProduct {
915 pub cgu_name: String,
916 /// Saved files associated with this CGU.
917 pub saved_files: Vec<(WorkProductFileKind, String)>,
920 #[derive(Clone, Copy, Debug, RustcEncodable, RustcDecodable, PartialEq)]
921 pub enum WorkProductFileKind {
930 edges: SmallVec<[DepNodeIndex; 8]>,
931 fingerprint: Fingerprint,
934 /// `CurrentDepGraph` stores the dependency graph for the current session.
935 /// It will be populated as we run queries or tasks.
937 /// The nodes in it are identified by an index (`DepNodeIndex`).
938 /// The data for each node is stored in its `DepNodeData`, found in the `data` field.
940 /// We never remove nodes from the graph: they are only added.
942 /// This struct uses two locks internally. The `data` and `node_to_node_index` fields are
943 /// locked separately. Operations that take a `DepNodeIndex` typically just access
946 /// The only operation that must manipulate both locks is adding new nodes, in which case
947 /// we first acquire the `node_to_node_index` lock and then, once a new node is to be inserted,
948 /// acquire the lock on `data.`
949 pub(super) struct CurrentDepGraph {
950 data: Lock<IndexVec<DepNodeIndex, DepNodeData>>,
951 node_to_node_index: Sharded<FxHashMap<DepNode, DepNodeIndex>>,
953 /// Used to trap when a specific edge is added to the graph.
954 /// This is used for debug purposes and is only active with `debug_assertions`.
956 forbidden_edge: Option<EdgeFilter>,
958 /// Anonymous `DepNode`s are nodes whose IDs we compute from the list of
959 /// their edges. This has the beneficial side-effect that multiple anonymous
960 /// nodes can be coalesced into one without changing the semantics of the
961 /// dependency graph. However, the merging of nodes can lead to a subtle
962 /// problem during red-green marking: The color of an anonymous node from
963 /// the current session might "shadow" the color of the node with the same
964 /// ID from the previous session. In order to side-step this problem, we make
965 /// sure that anonymous `NodeId`s allocated in different sessions don't overlap.
966 /// This is implemented by mixing a session-key into the ID fingerprint of
967 /// each anon node. The session-key is just a random number generated when
968 /// the `DepGraph` is created.
969 anon_id_seed: Fingerprint,
971 /// These are simple counters that are for profiling and
972 /// debugging and only active with `debug_assertions`.
973 total_read_count: AtomicU64,
974 total_duplicate_read_count: AtomicU64,
977 impl CurrentDepGraph {
978 fn new(prev_graph_node_count: usize) -> CurrentDepGraph {
979 use std::time::{SystemTime, UNIX_EPOCH};
981 let duration = SystemTime::now().duration_since(UNIX_EPOCH).unwrap();
982 let nanos = duration.as_secs() * 1_000_000_000 + duration.subsec_nanos() as u64;
983 let mut stable_hasher = StableHasher::new();
984 nanos.hash(&mut stable_hasher);
986 let forbidden_edge = if cfg!(debug_assertions) {
987 match env::var("RUST_FORBID_DEP_GRAPH_EDGE") {
988 Ok(s) => match EdgeFilter::new(&s) {
990 Err(err) => bug!("RUST_FORBID_DEP_GRAPH_EDGE invalid: {}", err),
998 // Pre-allocate the dep node structures. We over-allocate a little so
999 // that we hopefully don't have to re-allocate during this compilation
1000 // session. The over-allocation is 2% plus a small constant to account
1001 // for the fact that in very small crates 2% might not be enough.
1002 let new_node_count_estimate = (prev_graph_node_count * 102) / 100 + 200;
1005 data: Lock::new(IndexVec::with_capacity(new_node_count_estimate)),
1006 node_to_node_index: Sharded::new(|| {
1007 FxHashMap::with_capacity_and_hasher(
1008 new_node_count_estimate / sharded::SHARDS,
1012 anon_id_seed: stable_hasher.finish(),
1014 total_read_count: AtomicU64::new(0),
1015 total_duplicate_read_count: AtomicU64::new(0),
1022 task_deps: TaskDeps,
1023 fingerprint: Fingerprint,
1025 self.alloc_node(node, task_deps.reads, fingerprint)
1028 fn complete_anon_task(&self, kind: DepKind, task_deps: TaskDeps) -> DepNodeIndex {
1029 debug_assert!(!kind.is_eval_always());
1031 let mut hasher = StableHasher::new();
1033 // The dep node indices are hashed here instead of hashing the dep nodes of the
1034 // dependencies. These indices may refer to different nodes per session, but this isn't
1035 // a problem here because we that ensure the final dep node hash is per session only by
1036 // combining it with the per session random number `anon_id_seed`. This hash only need
1037 // to map the dependencies to a single value on a per session basis.
1038 task_deps.reads.hash(&mut hasher);
1040 let target_dep_node = DepNode {
1043 // Fingerprint::combine() is faster than sending Fingerprint
1044 // through the StableHasher (at least as long as StableHasher
1046 hash: self.anon_id_seed.combine(hasher.finish()),
1049 self.intern_node(target_dep_node, task_deps.reads, Fingerprint::ZERO)
1055 edges: SmallVec<[DepNodeIndex; 8]>,
1056 fingerprint: Fingerprint,
1059 !self.node_to_node_index.get_shard_by_value(&dep_node).lock().contains_key(&dep_node)
1061 self.intern_node(dep_node, edges, fingerprint)
1067 edges: SmallVec<[DepNodeIndex; 8]>,
1068 fingerprint: Fingerprint,
1070 match self.node_to_node_index.get_shard_by_value(&dep_node).lock().entry(dep_node) {
1071 Entry::Occupied(entry) => *entry.get(),
1072 Entry::Vacant(entry) => {
1073 let mut data = self.data.lock();
1074 let dep_node_index = DepNodeIndex::new(data.len());
1075 data.push(DepNodeData { node: dep_node, edges, fingerprint });
1076 entry.insert(dep_node_index);
1084 fn read_index(&self, source: DepNodeIndex) {
1085 ty::tls::with_context_opt(|icx| {
1086 let icx = if let Some(icx) = icx { icx } else { return };
1087 if let Some(task_deps) = icx.task_deps {
1088 let mut task_deps = task_deps.lock();
1089 if cfg!(debug_assertions) {
1090 self.current.total_read_count.fetch_add(1, SeqCst);
1092 if task_deps.read_set.insert(source) {
1093 task_deps.reads.push(source);
1095 #[cfg(debug_assertions)]
1097 if let Some(target) = task_deps.node {
1098 let data = self.current.data.lock();
1099 if let Some(ref forbidden_edge) = self.current.forbidden_edge {
1100 let source = data[source].node;
1101 if forbidden_edge.test(&source, &target) {
1102 bug!("forbidden edge {:?} -> {:?} created", source, target)
1107 } else if cfg!(debug_assertions) {
1108 self.current.total_duplicate_read_count.fetch_add(1, SeqCst);
1115 pub struct TaskDeps {
1116 #[cfg(debug_assertions)]
1117 node: Option<DepNode>,
1118 reads: SmallVec<[DepNodeIndex; 8]>,
1119 read_set: FxHashSet<DepNodeIndex>,
1122 // A data structure that stores Option<DepNodeColor> values as a contiguous
1123 // array, using one u32 per entry.
1124 struct DepNodeColorMap {
1125 values: IndexVec<SerializedDepNodeIndex, AtomicU32>,
1128 const COMPRESSED_NONE: u32 = 0;
1129 const COMPRESSED_RED: u32 = 1;
1130 const COMPRESSED_FIRST_GREEN: u32 = 2;
1132 impl DepNodeColorMap {
1133 fn new(size: usize) -> DepNodeColorMap {
1134 DepNodeColorMap { values: (0..size).map(|_| AtomicU32::new(COMPRESSED_NONE)).collect() }
1137 fn get(&self, index: SerializedDepNodeIndex) -> Option<DepNodeColor> {
1138 match self.values[index].load(Ordering::Acquire) {
1139 COMPRESSED_NONE => None,
1140 COMPRESSED_RED => Some(DepNodeColor::Red),
1142 Some(DepNodeColor::Green(DepNodeIndex::from_u32(value - COMPRESSED_FIRST_GREEN)))
1147 fn insert(&self, index: SerializedDepNodeIndex, color: DepNodeColor) {
1148 self.values[index].store(
1150 DepNodeColor::Red => COMPRESSED_RED,
1151 DepNodeColor::Green(index) => index.as_u32() + COMPRESSED_FIRST_GREEN,