1 use errors::{Diagnostic, DiagnosticBuilder};
2 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
3 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
4 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
5 use smallvec::SmallVec;
6 use rustc_data_structures::sync::{Lrc, Lock, AtomicU32, Ordering};
9 use std::collections::hash_map::Entry;
10 use crate::ty::{self, TyCtxt};
11 use crate::util::common::{ProfileQueriesMsg, profq_msg};
12 use parking_lot::{Mutex, Condvar};
14 use crate::ich::{StableHashingContext, StableHashingContextProvider, Fingerprint};
16 use super::debug::EdgeFilter;
17 use super::dep_node::{DepNode, DepKind, WorkProductId};
18 use super::query::DepGraphQuery;
19 use super::safe::DepGraphSafe;
20 use super::serialized::{SerializedDepGraph, SerializedDepNodeIndex};
21 use super::prev::PreviousDepGraph;
25 data: Option<Lrc<DepGraphData>>,
29 pub struct DepNodeIndex { .. }
33 const INVALID: DepNodeIndex = DepNodeIndex::MAX;
36 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
37 pub enum DepNodeColor {
43 pub fn is_green(self) -> bool {
45 DepNodeColor::Red => false,
46 DepNodeColor::Green(_) => true,
52 /// The new encoding of the dependency graph, optimized for red/green
53 /// tracking. The `current` field is the dependency graph of only the
54 /// current compilation session: We don't merge the previous dep-graph into
55 /// current one anymore.
56 current: Lock<CurrentDepGraph>,
58 /// The dep-graph from the previous compilation session. It contains all
59 /// nodes and edges as well as all fingerprints of nodes that have them.
60 previous: PreviousDepGraph,
62 colors: DepNodeColorMap,
64 /// A set of loaded diagnostics that have been emitted.
65 emitted_diagnostics: Mutex<FxHashSet<DepNodeIndex>>,
67 /// Used to wait for diagnostics to be emitted.
68 emitted_diagnostics_cond_var: Condvar,
70 /// When we load, there may be `.o` files, cached MIR, or other such
71 /// things available to us. If we find that they are not dirty, we
72 /// load the path to the file storing those work-products here into
73 /// this map. We can later look for and extract that data.
74 previous_work_products: FxHashMap<WorkProductId, WorkProduct>,
76 dep_node_debug: Lock<FxHashMap<DepNode, String>>,
78 // Used for testing, only populated when -Zquery-dep-graph is specified.
79 loaded_from_cache: Lock<FxHashMap<DepNodeIndex, bool>>,
82 pub fn hash_result<R>(hcx: &mut StableHashingContext<'_>, result: &R) -> Option<Fingerprint>
84 R: for<'a> HashStable<StableHashingContext<'a>>,
86 let mut stable_hasher = StableHasher::new();
87 result.hash_stable(hcx, &mut stable_hasher);
89 Some(stable_hasher.finish())
94 pub fn new(prev_graph: PreviousDepGraph,
95 prev_work_products: FxHashMap<WorkProductId, WorkProduct>) -> DepGraph {
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: Lock::new(CurrentDepGraph::new(prev_graph_node_count)),
103 emitted_diagnostics: Default::default(),
104 emitted_diagnostics_cond_var: Condvar::new(),
105 previous: prev_graph,
106 colors: DepNodeColorMap::new(prev_graph_node_count),
107 loaded_from_cache: Default::default(),
112 pub fn new_disabled() -> DepGraph {
118 /// Returns `true` if we are actually building the full dep-graph, and `false` otherwise.
120 pub fn is_fully_enabled(&self) -> bool {
124 pub fn query(&self) -> DepGraphQuery {
125 let current_dep_graph = self.data.as_ref().unwrap().current.borrow();
126 let nodes: Vec<_> = current_dep_graph.data.iter().map(|n| n.node).collect();
127 let mut edges = Vec::new();
128 for (from, edge_targets) in current_dep_graph.data.iter()
129 .map(|d| (d.node, &d.edges)) {
130 for &edge_target in edge_targets.iter() {
131 let to = current_dep_graph.data[edge_target].node;
132 edges.push((from, to));
136 DepGraphQuery::new(&nodes[..], &edges[..])
139 pub fn assert_ignored(&self)
141 if let Some(..) = self.data {
142 ty::tls::with_context_opt(|icx| {
143 let icx = if let Some(icx) = icx { icx } else { return };
144 assert!(icx.task_deps.is_none(), "expected no task dependency tracking");
149 pub fn with_ignore<OP,R>(&self, op: OP) -> R
150 where OP: FnOnce() -> R
152 ty::tls::with_context(|icx| {
153 let icx = ty::tls::ImplicitCtxt {
158 ty::tls::enter_context(&icx, |_| {
164 /// Starts a new dep-graph task. Dep-graph tasks are specified
165 /// using a free function (`task`) and **not** a closure -- this
166 /// is intentional because we want to exercise tight control over
167 /// what state they have access to. In particular, we want to
168 /// prevent implicit 'leaks' of tracked state into the task (which
169 /// could then be read without generating correct edges in the
170 /// dep-graph -- see the [rustc guide] for more details on
171 /// the dep-graph). To this end, the task function gets exactly two
172 /// pieces of state: the context `cx` and an argument `arg`. Both
173 /// of these bits of state must be of some type that implements
174 /// `DepGraphSafe` and hence does not leak.
176 /// The choice of two arguments is not fundamental. One argument
177 /// would work just as well, since multiple values can be
178 /// collected using tuples. However, using two arguments works out
179 /// to be quite convenient, since it is common to need a context
180 /// (`cx`) and some argument (e.g., a `DefId` identifying what
181 /// item to process).
183 /// For cases where you need some other number of arguments:
185 /// - If you only need one argument, just use `()` for the `arg`
187 /// - If you need 3+ arguments, use a tuple for the
190 /// [rustc guide]: https://rust-lang.github.io/rustc-guide/incremental-compilation.html
191 pub fn with_task<'a, C, A, R>(
197 hash_result: impl FnOnce(&mut StableHashingContext<'_>, &R) -> Option<Fingerprint>,
198 ) -> (R, DepNodeIndex)
200 C: DepGraphSafe + StableHashingContextProvider<'a>,
202 self.with_task_impl(key, cx, arg, false, task,
203 |_key| Some(TaskDeps {
204 #[cfg(debug_assertions)]
206 reads: SmallVec::new(),
207 read_set: Default::default(),
209 |data, key, fingerprint, task| {
210 data.borrow_mut().complete_task(key, task.unwrap(), fingerprint)
215 /// Creates a new dep-graph input with value `input`
216 pub fn input_task<'a, C, R>(&self,
221 where C: DepGraphSafe + StableHashingContextProvider<'a>,
222 R: for<'b> HashStable<StableHashingContext<'b>>,
224 fn identity_fn<C, A>(_: C, arg: A) -> A {
228 self.with_task_impl(key, cx, input, true, identity_fn,
230 |data, key, fingerprint, _| {
231 data.borrow_mut().alloc_node(key, SmallVec::new(), fingerprint)
236 fn with_task_impl<'a, C, A, R>(
243 create_task: fn(DepNode) -> Option<TaskDeps>,
244 finish_task_and_alloc_depnode: fn(&Lock<CurrentDepGraph>,
247 Option<TaskDeps>) -> DepNodeIndex,
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 if cfg!(debug_assertions) {
264 profq_msg(hcx.sess(), ProfileQueriesMsg::TaskBegin(key.clone()))
267 let result = if no_tcx {
270 ty::tls::with_context(|icx| {
271 let icx = ty::tls::ImplicitCtxt {
272 task_deps: task_deps.as_ref(),
276 ty::tls::enter_context(&icx, |_| {
282 if cfg!(debug_assertions) {
283 profq_msg(hcx.sess(), ProfileQueriesMsg::TaskEnd)
286 let current_fingerprint = hash_result(&mut hcx, &result);
288 let dep_node_index = finish_task_and_alloc_depnode(
291 current_fingerprint.unwrap_or(Fingerprint::ZERO),
292 task_deps.map(|lock| lock.into_inner()),
295 let print_status = cfg!(debug_assertions) && hcx.sess().opts.debugging_opts.dep_tasks;
297 // Determine the color of the new DepNode.
298 if let Some(prev_index) = data.previous.node_to_index_opt(&key) {
299 let prev_fingerprint = data.previous.fingerprint_by_index(prev_index);
301 let color = if let Some(current_fingerprint) = current_fingerprint {
302 if current_fingerprint == prev_fingerprint {
304 eprintln!("[task::green] {:?}", key);
306 DepNodeColor::Green(dep_node_index)
309 eprintln!("[task::red] {:?}", key);
315 eprintln!("[task::unknown] {:?}", key);
317 // Mark the node as Red if we can't hash the result
321 debug_assert!(data.colors.get(prev_index).is_none(),
322 "DepGraph::with_task() - Duplicate DepNodeColor \
323 insertion for {:?}", key);
325 data.colors.insert(prev_index, color);
328 eprintln!("[task::new] {:?}", key);
332 (result, dep_node_index)
334 (task(cx, arg), DepNodeIndex::INVALID)
338 /// Executes something within an "anonymous" task, that is, a task the
339 /// `DepNode` of which is determined by the list of inputs it read from.
340 pub fn with_anon_task<OP,R>(&self, dep_kind: DepKind, op: OP) -> (R, DepNodeIndex)
341 where OP: FnOnce() -> R
343 if let Some(ref data) = self.data {
344 let (result, task_deps) = ty::tls::with_context(|icx| {
345 let task_deps = Lock::new(TaskDeps {
346 #[cfg(debug_assertions)]
348 reads: SmallVec::new(),
349 read_set: Default::default(),
353 let icx = ty::tls::ImplicitCtxt {
354 task_deps: Some(&task_deps),
358 ty::tls::enter_context(&icx, |_| {
363 (r, task_deps.into_inner())
365 let dep_node_index = data.current
367 .complete_anon_task(dep_kind, task_deps);
368 (result, dep_node_index)
370 (op(), DepNodeIndex::INVALID)
374 /// Executes something within an "eval-always" task which is a task
375 /// that runs whenever anything changes.
376 pub fn with_eval_always_task<'a, C, A, R>(
382 hash_result: impl FnOnce(&mut StableHashingContext<'_>, &R) -> Option<Fingerprint>,
383 ) -> (R, DepNodeIndex)
385 C: DepGraphSafe + StableHashingContextProvider<'a>,
387 self.with_task_impl(key, cx, arg, false, task,
389 |data, key, fingerprint, _| {
390 let mut current = data.borrow_mut();
391 let krate_idx = current.node_to_node_index[
392 &DepNode::new_no_params(DepKind::Krate)
394 current.alloc_node(key, smallvec![krate_idx], fingerprint)
400 pub fn read(&self, v: DepNode) {
401 if let Some(ref data) = self.data {
402 let current = data.current.borrow_mut();
403 if let Some(&dep_node_index) = current.node_to_node_index.get(&v) {
404 std::mem::drop(current);
405 data.read_index(dep_node_index);
407 bug!("DepKind {:?} should be pre-allocated but isn't.", v.kind)
413 pub fn read_index(&self, dep_node_index: DepNodeIndex) {
414 if let Some(ref data) = self.data {
415 data.read_index(dep_node_index);
420 pub fn dep_node_index_of(&self, dep_node: &DepNode) -> DepNodeIndex {
433 pub fn dep_node_exists(&self, dep_node: &DepNode) -> bool {
434 if let Some(ref data) = self.data {
435 data.current.borrow_mut().node_to_node_index.contains_key(dep_node)
442 pub fn fingerprint_of(&self, dep_node_index: DepNodeIndex) -> Fingerprint {
443 let current = self.data.as_ref().expect("dep graph enabled").current.borrow_mut();
444 current.data[dep_node_index].fingerprint
447 pub fn prev_fingerprint_of(&self, dep_node: &DepNode) -> Option<Fingerprint> {
448 self.data.as_ref().unwrap().previous.fingerprint_of(dep_node)
452 pub fn prev_dep_node_index_of(&self, dep_node: &DepNode) -> SerializedDepNodeIndex {
453 self.data.as_ref().unwrap().previous.node_to_index(dep_node)
456 /// Checks whether a previous work product exists for `v` and, if
457 /// so, return the path that leads to it. Used to skip doing work.
458 pub fn previous_work_product(&self, v: &WorkProductId) -> Option<WorkProduct> {
462 data.previous_work_products.get(v).cloned()
466 /// Access the map of work-products created during the cached run. Only
467 /// used during saving of the dep-graph.
468 pub fn previous_work_products(&self) -> &FxHashMap<WorkProductId, WorkProduct> {
469 &self.data.as_ref().unwrap().previous_work_products
473 pub fn register_dep_node_debug_str<F>(&self,
476 where F: FnOnce() -> String
478 let dep_node_debug = &self.data.as_ref().unwrap().dep_node_debug;
480 if dep_node_debug.borrow().contains_key(&dep_node) {
483 let debug_str = debug_str_gen();
484 dep_node_debug.borrow_mut().insert(dep_node, debug_str);
487 pub(super) fn dep_node_debug_str(&self, dep_node: DepNode) -> Option<String> {
496 pub fn edge_deduplication_data(&self) -> Option<(u64, u64)> {
497 if cfg!(debug_assertions) {
498 let current_dep_graph = self.data.as_ref().unwrap().current.borrow();
500 Some((current_dep_graph.total_read_count,
501 current_dep_graph.total_duplicate_read_count))
507 pub fn serialize(&self) -> SerializedDepGraph {
508 let current_dep_graph = self.data.as_ref().unwrap().current.borrow();
510 let fingerprints: IndexVec<SerializedDepNodeIndex, _> =
511 current_dep_graph.data.iter().map(|d| d.fingerprint).collect();
512 let nodes: IndexVec<SerializedDepNodeIndex, _> =
513 current_dep_graph.data.iter().map(|d| d.node).collect();
515 let total_edge_count: usize = current_dep_graph.data.iter()
516 .map(|d| d.edges.len())
519 let mut edge_list_indices = IndexVec::with_capacity(nodes.len());
520 let mut edge_list_data = Vec::with_capacity(total_edge_count);
522 for (current_dep_node_index, edges) in current_dep_graph.data.iter_enumerated()
523 .map(|(i, d)| (i, &d.edges)) {
524 let start = edge_list_data.len() as u32;
525 // This should really just be a memcpy :/
526 edge_list_data.extend(edges.iter().map(|i| SerializedDepNodeIndex::new(i.index())));
527 let end = edge_list_data.len() as u32;
529 debug_assert_eq!(current_dep_node_index.index(), edge_list_indices.len());
530 edge_list_indices.push((start, end));
533 debug_assert!(edge_list_data.len() <= ::std::u32::MAX as usize);
534 debug_assert_eq!(edge_list_data.len(), total_edge_count);
544 pub fn node_color(&self, dep_node: &DepNode) -> Option<DepNodeColor> {
545 if let Some(ref data) = self.data {
546 if let Some(prev_index) = data.previous.node_to_index_opt(dep_node) {
547 return data.colors.get(prev_index)
549 // This is a node that did not exist in the previous compilation
550 // session, so we consider it to be red.
551 return Some(DepNodeColor::Red)
558 /// Try to read a node index for the node dep_node.
559 /// A node will have an index, when it's already been marked green, or when we can mark it
560 /// green. This function will mark the current task as a reader of the specified node, when
561 /// a node index can be found for that node.
562 pub fn try_mark_green_and_read(
564 tcx: TyCtxt<'_, '_, '_>,
566 ) -> Option<(SerializedDepNodeIndex, DepNodeIndex)> {
567 self.try_mark_green(tcx, dep_node).map(|(prev_index, dep_node_index)| {
568 debug_assert!(self.is_green(&dep_node));
569 self.read_index(dep_node_index);
570 (prev_index, dep_node_index)
574 pub fn try_mark_green(
576 tcx: TyCtxt<'_, '_, '_>,
578 ) -> Option<(SerializedDepNodeIndex, DepNodeIndex)> {
579 debug_assert!(!dep_node.kind.is_input());
581 // Return None if the dep graph is disabled
582 let data = self.data.as_ref()?;
584 // Return None if the dep node didn't exist in the previous session
585 let prev_index = data.previous.node_to_index_opt(dep_node)?;
587 match data.colors.get(prev_index) {
588 Some(DepNodeColor::Green(dep_node_index)) => Some((prev_index, dep_node_index)),
589 Some(DepNodeColor::Red) => None,
591 // This DepNode and the corresponding query invocation existed
592 // in the previous compilation session too, so we can try to
593 // mark it as green by recursively marking all of its
594 // dependencies green.
595 self.try_mark_previous_green(
600 ).map(|dep_node_index| {
601 (prev_index, dep_node_index)
607 /// Try to mark a dep-node which existed in the previous compilation session as green.
608 fn try_mark_previous_green<'tcx>(
610 tcx: TyCtxt<'_, 'tcx, 'tcx>,
612 prev_dep_node_index: SerializedDepNodeIndex,
614 ) -> Option<DepNodeIndex> {
615 debug!("try_mark_previous_green({:?}) - BEGIN", dep_node);
617 #[cfg(not(parallel_compiler))]
619 debug_assert!(!data.current.borrow().node_to_node_index.contains_key(dep_node));
620 debug_assert!(data.colors.get(prev_dep_node_index).is_none());
623 // We never try to mark inputs as green
624 debug_assert!(!dep_node.kind.is_input());
626 debug_assert_eq!(data.previous.index_to_node(prev_dep_node_index), *dep_node);
628 let prev_deps = data.previous.edge_targets_from(prev_dep_node_index);
630 let mut current_deps = SmallVec::new();
632 for &dep_dep_node_index in prev_deps {
633 let dep_dep_node_color = data.colors.get(dep_dep_node_index);
635 match dep_dep_node_color {
636 Some(DepNodeColor::Green(node_index)) => {
637 // This dependency has been marked as green before, we are
638 // still fine and can continue with checking the other
640 debug!("try_mark_previous_green({:?}) --- found dependency {:?} to \
641 be immediately green",
643 data.previous.index_to_node(dep_dep_node_index));
644 current_deps.push(node_index);
646 Some(DepNodeColor::Red) => {
647 // We found a dependency the value of which has changed
648 // compared to the previous compilation session. We cannot
649 // mark the DepNode as green and also don't need to bother
650 // with checking any of the other dependencies.
651 debug!("try_mark_previous_green({:?}) - END - dependency {:?} was \
654 data.previous.index_to_node(dep_dep_node_index));
658 let dep_dep_node = &data.previous.index_to_node(dep_dep_node_index);
660 // We don't know the state of this dependency. If it isn't
661 // an input node, let's try to mark it green recursively.
662 if !dep_dep_node.kind.is_input() {
663 debug!("try_mark_previous_green({:?}) --- state of dependency {:?} \
664 is unknown, trying to mark it green", dep_node,
667 let node_index = self.try_mark_previous_green(
673 if let Some(node_index) = node_index {
674 debug!("try_mark_previous_green({:?}) --- managed to MARK \
675 dependency {:?} as green", dep_node, dep_dep_node);
676 current_deps.push(node_index);
680 match dep_dep_node.kind {
683 DepKind::CrateMetadata => {
684 if dep_dep_node.extract_def_id(tcx).is_none() {
685 // If the node does not exist anymore, we
686 // just fail to mark green.
689 // If the node does exist, it should have
690 // been pre-allocated.
691 bug!("DepNode {:?} should have been \
692 pre-allocated but wasn't.",
697 // For other kinds of inputs it's OK to be
703 // We failed to mark it green, so we try to force the query.
704 debug!("try_mark_previous_green({:?}) --- trying to force \
705 dependency {:?}", dep_node, dep_dep_node);
706 if crate::ty::query::force_from_dep_node(tcx, dep_dep_node) {
707 let dep_dep_node_color = data.colors.get(dep_dep_node_index);
709 match dep_dep_node_color {
710 Some(DepNodeColor::Green(node_index)) => {
711 debug!("try_mark_previous_green({:?}) --- managed to \
712 FORCE dependency {:?} to green",
713 dep_node, dep_dep_node);
714 current_deps.push(node_index);
716 Some(DepNodeColor::Red) => {
717 debug!("try_mark_previous_green({:?}) - END - \
718 dependency {:?} was red after forcing",
724 if !tcx.sess.has_errors() {
725 bug!("try_mark_previous_green() - Forcing the DepNode \
726 should have set its color")
728 // If the query we just forced has resulted
729 // in some kind of compilation error, we
730 // don't expect that the corresponding
731 // dep-node color has been updated.
736 // The DepNode could not be forced.
737 debug!("try_mark_previous_green({:?}) - END - dependency {:?} \
738 could not be forced", dep_node, dep_dep_node);
745 // If we got here without hitting a `return` that means that all
746 // dependencies of this DepNode could be marked as green. Therefore we
747 // can also mark this DepNode as green.
749 // There may be multiple threads trying to mark the same dep node green concurrently
751 let (dep_node_index, did_allocation) = {
752 let mut current = data.current.borrow_mut();
754 // Copy the fingerprint from the previous graph,
755 // so we don't have to recompute it
756 let fingerprint = data.previous.fingerprint_by_index(prev_dep_node_index);
758 // We allocating an entry for the node in the current dependency graph and
759 // adding all the appropriate edges imported from the previous graph
760 current.intern_node(*dep_node, current_deps, fingerprint)
763 // ... emitting any stored diagnostic ...
765 let diagnostics = tcx.queries.on_disk_cache
766 .load_diagnostics(tcx, prev_dep_node_index);
768 if unlikely!(diagnostics.len() > 0) {
769 self.emit_diagnostics(
778 // ... and finally storing a "Green" entry in the color map.
779 // Multiple threads can all write the same color here
780 #[cfg(not(parallel_compiler))]
781 debug_assert!(data.colors.get(prev_dep_node_index).is_none(),
782 "DepGraph::try_mark_previous_green() - Duplicate DepNodeColor \
783 insertion for {:?}", dep_node);
785 data.colors.insert(prev_dep_node_index, DepNodeColor::Green(dep_node_index));
787 debug!("try_mark_previous_green({:?}) - END - successfully marked as green", dep_node);
791 /// Atomically emits some loaded diagnotics, assuming that this only gets called with
792 /// `did_allocation` set to `true` on a single thread.
795 fn emit_diagnostics<'tcx>(
797 tcx: TyCtxt<'_, 'tcx, 'tcx>,
799 dep_node_index: DepNodeIndex,
800 did_allocation: bool,
801 diagnostics: Vec<Diagnostic>,
803 if did_allocation || !cfg!(parallel_compiler) {
804 // Only the thread which did the allocation emits the error messages
805 let handle = tcx.sess.diagnostic();
807 // Promote the previous diagnostics to the current session.
808 tcx.queries.on_disk_cache
809 .store_diagnostics(dep_node_index, diagnostics.clone().into());
811 for diagnostic in diagnostics {
812 DiagnosticBuilder::new_diagnostic(handle, diagnostic).emit();
815 #[cfg(parallel_compiler)]
817 // Mark the diagnostics and emitted and wake up waiters
818 data.emitted_diagnostics.lock().insert(dep_node_index);
819 data.emitted_diagnostics_cond_var.notify_all();
822 // The other threads will wait for the diagnostics to be emitted
824 let mut emitted_diagnostics = data.emitted_diagnostics.lock();
826 if emitted_diagnostics.contains(&dep_node_index) {
829 data.emitted_diagnostics_cond_var.wait(&mut emitted_diagnostics);
834 // Returns true if the given node has been marked as green during the
835 // current compilation session. Used in various assertions
836 pub fn is_green(&self, dep_node: &DepNode) -> bool {
837 self.node_color(dep_node).map(|c| c.is_green()).unwrap_or(false)
840 // This method loads all on-disk cacheable query results into memory, so
841 // they can be written out to the new cache file again. Most query results
842 // will already be in memory but in the case where we marked something as
843 // green but then did not need the value, that value will never have been
846 // This method will only load queries that will end up in the disk cache.
847 // Other queries will not be executed.
848 pub fn exec_cache_promotions<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) {
849 let green_nodes: Vec<DepNode> = {
850 let data = self.data.as_ref().unwrap();
851 data.colors.values.indices().filter_map(|prev_index| {
852 match data.colors.get(prev_index) {
853 Some(DepNodeColor::Green(_)) => {
854 let dep_node = data.previous.index_to_node(prev_index);
855 if dep_node.cache_on_disk(tcx) {
862 Some(DepNodeColor::Red) => {
863 // We can skip red nodes because a node can only be marked
864 // as red if the query result was recomputed and thus is
865 // already in memory.
872 for dep_node in green_nodes {
873 dep_node.load_from_on_disk_cache(tcx);
877 pub fn mark_loaded_from_cache(&self, dep_node_index: DepNodeIndex, state: bool) {
878 debug!("mark_loaded_from_cache({:?}, {})",
879 self.data.as_ref().unwrap().current.borrow().data[dep_node_index].node,
887 .insert(dep_node_index, state);
890 pub fn was_loaded_from_cache(&self, dep_node: &DepNode) -> Option<bool> {
891 let data = self.data.as_ref().unwrap();
892 let dep_node_index = data.current.borrow().node_to_node_index[dep_node];
893 data.loaded_from_cache.borrow().get(&dep_node_index).cloned()
897 /// A "work product" is an intermediate result that we save into the
898 /// incremental directory for later re-use. The primary example are
899 /// the object files that we save for each partition at code
902 /// Each work product is associated with a dep-node, representing the
903 /// process that produced the work-product. If that dep-node is found
904 /// to be dirty when we load up, then we will delete the work-product
905 /// at load time. If the work-product is found to be clean, then we
906 /// will keep a record in the `previous_work_products` list.
908 /// In addition, work products have an associated hash. This hash is
909 /// an extra hash that can be used to decide if the work-product from
910 /// a previous compilation can be re-used (in addition to the dirty
913 /// As the primary example, consider the object files we generate for
914 /// each partition. In the first run, we create partitions based on
915 /// the symbols that need to be compiled. For each partition P, we
916 /// hash the symbols in P and create a `WorkProduct` record associated
917 /// with `DepNode::CodegenUnit(P)`; the hash is the set of symbols
920 /// The next time we compile, if the `DepNode::CodegenUnit(P)` is
921 /// judged to be clean (which means none of the things we read to
922 /// generate the partition were found to be dirty), it will be loaded
923 /// into previous work products. We will then regenerate the set of
924 /// symbols in the partition P and hash them (note that new symbols
925 /// may be added -- for example, new monomorphizations -- even if
926 /// nothing in P changed!). We will compare that hash against the
927 /// previous hash. If it matches up, we can reuse the object file.
928 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
929 pub struct WorkProduct {
930 pub cgu_name: String,
931 /// Saved files associated with this CGU.
932 pub saved_files: Vec<(WorkProductFileKind, String)>,
935 #[derive(Clone, Copy, Debug, RustcEncodable, RustcDecodable, PartialEq)]
936 pub enum WorkProductFileKind {
945 edges: SmallVec<[DepNodeIndex; 8]>,
946 fingerprint: Fingerprint,
949 pub(super) struct CurrentDepGraph {
950 data: IndexVec<DepNodeIndex, DepNodeData>,
951 node_to_node_index: FxHashMap<DepNode, DepNodeIndex>,
953 forbidden_edge: Option<EdgeFilter>,
955 /// Anonymous `DepNode`s are nodes whose IDs we compute from the list of
956 /// their edges. This has the beneficial side-effect that multiple anonymous
957 /// nodes can be coalesced into one without changing the semantics of the
958 /// dependency graph. However, the merging of nodes can lead to a subtle
959 /// problem during red-green marking: The color of an anonymous node from
960 /// the current session might "shadow" the color of the node with the same
961 /// ID from the previous session. In order to side-step this problem, we make
962 /// sure that anonymous `NodeId`s allocated in different sessions don't overlap.
963 /// This is implemented by mixing a session-key into the ID fingerprint of
964 /// each anon node. The session-key is just a random number generated when
965 /// the `DepGraph` is created.
966 anon_id_seed: Fingerprint,
968 total_read_count: u64,
969 total_duplicate_read_count: u64,
972 impl CurrentDepGraph {
973 fn new(prev_graph_node_count: usize) -> CurrentDepGraph {
974 use std::time::{SystemTime, UNIX_EPOCH};
976 let duration = SystemTime::now().duration_since(UNIX_EPOCH).unwrap();
977 let nanos = duration.as_secs() * 1_000_000_000 +
978 duration.subsec_nanos() as u64;
979 let mut stable_hasher = StableHasher::new();
980 nanos.hash(&mut stable_hasher);
982 let forbidden_edge = if cfg!(debug_assertions) {
983 match env::var("RUST_FORBID_DEP_GRAPH_EDGE") {
985 match EdgeFilter::new(&s) {
987 Err(err) => bug!("RUST_FORBID_DEP_GRAPH_EDGE invalid: {}", err),
996 // Pre-allocate the dep node structures. We over-allocate a little so
997 // that we hopefully don't have to re-allocate during this compilation
999 let new_node_count_estimate = (prev_graph_node_count * 115) / 100;
1002 data: IndexVec::with_capacity(new_node_count_estimate),
1003 node_to_node_index: FxHashMap::with_capacity_and_hasher(
1004 new_node_count_estimate,
1007 anon_id_seed: stable_hasher.finish(),
1009 total_read_count: 0,
1010 total_duplicate_read_count: 0,
1017 task_deps: TaskDeps,
1018 fingerprint: Fingerprint
1020 // If this is an input node, we expect that it either has no
1021 // dependencies, or that it just depends on DepKind::CrateMetadata
1022 // or DepKind::Krate. This happens for some "thin wrapper queries"
1023 // like `crate_disambiguator` which sometimes have zero deps (for
1024 // when called for LOCAL_CRATE) or they depend on a CrateMetadata
1026 if cfg!(debug_assertions) {
1027 if node.kind.is_input() && task_deps.reads.len() > 0 &&
1028 // FIXME(mw): Special case for DefSpan until Spans are handled
1029 // better in general.
1030 node.kind != DepKind::DefSpan &&
1031 task_deps.reads.iter().any(|&i| {
1032 !(self.data[i].node.kind == DepKind::CrateMetadata ||
1033 self.data[i].node.kind == DepKind::Krate)
1036 bug!("Input node {:?} with unexpected reads: {:?}",
1038 task_deps.reads.iter().map(|&i| self.data[i].node).collect::<Vec<_>>())
1042 self.alloc_node(node, task_deps.reads, fingerprint)
1045 fn complete_anon_task(&mut self, kind: DepKind, task_deps: TaskDeps) -> DepNodeIndex {
1046 debug_assert!(!kind.is_input());
1048 let mut fingerprint = self.anon_id_seed;
1049 let mut hasher = StableHasher::new();
1051 for &read in task_deps.reads.iter() {
1052 let read_dep_node = self.data[read].node;
1054 ::std::mem::discriminant(&read_dep_node.kind).hash(&mut hasher);
1056 // Fingerprint::combine() is faster than sending Fingerprint
1057 // through the StableHasher (at least as long as StableHasher
1059 fingerprint = fingerprint.combine(read_dep_node.hash);
1062 fingerprint = fingerprint.combine(hasher.finish());
1064 let target_dep_node = DepNode {
1069 self.intern_node(target_dep_node, task_deps.reads, Fingerprint::ZERO).0
1075 edges: SmallVec<[DepNodeIndex; 8]>,
1076 fingerprint: Fingerprint
1078 debug_assert!(!self.node_to_node_index.contains_key(&dep_node));
1079 self.intern_node(dep_node, edges, fingerprint).0
1085 edges: SmallVec<[DepNodeIndex; 8]>,
1086 fingerprint: Fingerprint
1087 ) -> (DepNodeIndex, bool) {
1088 debug_assert_eq!(self.node_to_node_index.len(), self.data.len());
1090 match self.node_to_node_index.entry(dep_node) {
1091 Entry::Occupied(entry) => (*entry.get(), false),
1092 Entry::Vacant(entry) => {
1093 let dep_node_index = DepNodeIndex::new(self.data.len());
1094 self.data.push(DepNodeData {
1099 entry.insert(dep_node_index);
1100 (dep_node_index, true)
1107 fn read_index(&self, source: DepNodeIndex) {
1108 ty::tls::with_context_opt(|icx| {
1109 let icx = if let Some(icx) = icx { icx } else { return };
1110 if let Some(task_deps) = icx.task_deps {
1111 let mut task_deps = task_deps.lock();
1112 if cfg!(debug_assertions) {
1113 self.current.lock().total_read_count += 1;
1115 if task_deps.read_set.insert(source) {
1116 task_deps.reads.push(source);
1118 #[cfg(debug_assertions)]
1120 if let Some(target) = task_deps.node {
1121 let graph = self.current.lock();
1122 if let Some(ref forbidden_edge) = graph.forbidden_edge {
1123 let source = graph.data[source].node;
1124 if forbidden_edge.test(&source, &target) {
1125 bug!("forbidden edge {:?} -> {:?} created",
1132 } else if cfg!(debug_assertions) {
1133 self.current.lock().total_duplicate_read_count += 1;
1140 pub struct TaskDeps {
1141 #[cfg(debug_assertions)]
1142 node: Option<DepNode>,
1143 reads: SmallVec<[DepNodeIndex; 8]>,
1144 read_set: FxHashSet<DepNodeIndex>,
1147 // A data structure that stores Option<DepNodeColor> values as a contiguous
1148 // array, using one u32 per entry.
1149 struct DepNodeColorMap {
1150 values: IndexVec<SerializedDepNodeIndex, AtomicU32>,
1153 const COMPRESSED_NONE: u32 = 0;
1154 const COMPRESSED_RED: u32 = 1;
1155 const COMPRESSED_FIRST_GREEN: u32 = 2;
1157 impl DepNodeColorMap {
1158 fn new(size: usize) -> DepNodeColorMap {
1160 values: (0..size).map(|_| AtomicU32::new(COMPRESSED_NONE)).collect(),
1164 fn get(&self, index: SerializedDepNodeIndex) -> Option<DepNodeColor> {
1165 match self.values[index].load(Ordering::Acquire) {
1166 COMPRESSED_NONE => None,
1167 COMPRESSED_RED => Some(DepNodeColor::Red),
1168 value => Some(DepNodeColor::Green(DepNodeIndex::from_u32(
1169 value - COMPRESSED_FIRST_GREEN
1174 fn insert(&self, index: SerializedDepNodeIndex, color: DepNodeColor) {
1175 self.values[index].store(match color {
1176 DepNodeColor::Red => COMPRESSED_RED,
1177 DepNodeColor::Green(index) => index.as_u32() + COMPRESSED_FIRST_GREEN,
1178 }, Ordering::Release)