1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use errors
::DiagnosticBuilder
;
12 use rustc_data_structures
::stable_hasher
::{HashStable, StableHasher}
;
13 use rustc_data_structures
::fx
::{FxHashMap, FxHashSet}
;
14 use rustc_data_structures
::indexed_vec
::{Idx, IndexVec}
;
15 use rustc_data_structures
::sync
::{Lrc, RwLock, ReadGuard, Lock}
;
18 use ty
::{self, TyCtxt}
;
19 use util
::common
::{ProfileQueriesMsg, profq_msg}
;
21 use ich
::{StableHashingContext, StableHashingContextProvider, Fingerprint}
;
23 use super::debug
::EdgeFilter
;
24 use super::dep_node
::{DepNode, DepKind, WorkProductId}
;
25 use super::query
::DepGraphQuery
;
26 use super::safe
::DepGraphSafe
;
27 use super::serialized
::{SerializedDepGraph, SerializedDepNodeIndex}
;
28 use super::prev
::PreviousDepGraph
;
32 data
: Option
<Lrc
<DepGraphData
>>,
34 // A vector mapping depnodes from the current graph to their associated
35 // result value fingerprints. Do not rely on the length of this vector
36 // being the same as the number of nodes in the graph. The vector can
37 // contain an arbitrary number of zero-entries at the end.
38 fingerprints
: Lrc
<Lock
<IndexVec
<DepNodeIndex
, Fingerprint
>>>
42 newtype_index
!(DepNodeIndex
);
45 const INVALID
: DepNodeIndex
= DepNodeIndex(::std
::u32::MAX
);
48 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
49 pub enum DepNodeColor
{
55 pub fn is_green(self) -> bool
{
57 DepNodeColor
::Red
=> false,
58 DepNodeColor
::Green(_
) => true,
64 /// The new encoding of the dependency graph, optimized for red/green
65 /// tracking. The `current` field is the dependency graph of only the
66 /// current compilation session: We don't merge the previous dep-graph into
67 /// current one anymore.
68 current
: Lock
<CurrentDepGraph
>,
70 /// The dep-graph from the previous compilation session. It contains all
71 /// nodes and edges as well as all fingerprints of nodes that have them.
72 previous
: PreviousDepGraph
,
74 colors
: Lock
<DepNodeColorMap
>,
76 /// When we load, there may be `.o` files, cached mir, or other such
77 /// things available to us. If we find that they are not dirty, we
78 /// load the path to the file storing those work-products here into
79 /// this map. We can later look for and extract that data.
80 previous_work_products
: RwLock
<FxHashMap
<WorkProductId
, WorkProduct
>>,
82 /// Work-products that we generate in this run.
83 work_products
: RwLock
<FxHashMap
<WorkProductId
, WorkProduct
>>,
85 dep_node_debug
: Lock
<FxHashMap
<DepNode
, String
>>,
87 // Used for testing, only populated when -Zquery-dep-graph is specified.
88 loaded_from_cache
: Lock
<FxHashMap
<DepNodeIndex
, bool
>>,
93 pub fn new(prev_graph
: PreviousDepGraph
) -> DepGraph
{
94 // Pre-allocate the fingerprints array. We over-allocate a little so
95 // that we hopefully don't have to re-allocate during this compilation
97 let prev_graph_node_count
= prev_graph
.node_count();
99 let fingerprints
= IndexVec
::from_elem_n(Fingerprint
::ZERO
,
100 (prev_graph_node_count
* 115) / 100);
102 data
: Some(Lrc
::new(DepGraphData
{
103 previous_work_products
: RwLock
::new(FxHashMap()),
104 work_products
: RwLock
::new(FxHashMap()),
105 dep_node_debug
: Lock
::new(FxHashMap()),
106 current
: Lock
::new(CurrentDepGraph
::new()),
107 previous
: prev_graph
,
108 colors
: Lock
::new(DepNodeColorMap
::new(prev_graph_node_count
)),
109 loaded_from_cache
: Lock
::new(FxHashMap()),
111 fingerprints
: Lrc
::new(Lock
::new(fingerprints
)),
115 pub fn new_disabled() -> DepGraph
{
118 fingerprints
: Lrc
::new(Lock
::new(IndexVec
::new())),
122 /// True if we are actually building the full dep-graph.
124 pub fn is_fully_enabled(&self) -> bool
{
128 pub fn query(&self) -> DepGraphQuery
{
129 let current_dep_graph
= self.data
.as_ref().unwrap().current
.borrow();
130 let nodes
: Vec
<_
> = current_dep_graph
.nodes
.iter().cloned().collect();
131 let mut edges
= Vec
::new();
132 for (index
, edge_targets
) in current_dep_graph
.edges
.iter_enumerated() {
133 let from
= current_dep_graph
.nodes
[index
];
134 for &edge_target
in edge_targets
{
135 let to
= current_dep_graph
.nodes
[edge_target
];
136 edges
.push((from
, to
));
140 DepGraphQuery
::new(&nodes
[..], &edges
[..])
143 pub fn assert_ignored(&self)
145 if let Some(..) = self.data
{
146 ty
::tls
::with_context_opt(|icx
| {
147 let icx
= if let Some(icx
) = icx { icx }
else { return }
;
149 OpenTask
::Ignore
=> {
152 _
=> panic
!("expected an ignore context")
158 pub fn with_ignore
<OP
,R
>(&self, op
: OP
) -> R
159 where OP
: FnOnce() -> R
161 ty
::tls
::with_context(|icx
| {
162 let icx
= ty
::tls
::ImplicitCtxt
{
163 task
: &OpenTask
::Ignore
,
167 ty
::tls
::enter_context(&icx
, |_
| {
173 /// Starts a new dep-graph task. Dep-graph tasks are specified
174 /// using a free function (`task`) and **not** a closure -- this
175 /// is intentional because we want to exercise tight control over
176 /// what state they have access to. In particular, we want to
177 /// prevent implicit 'leaks' of tracked state into the task (which
178 /// could then be read without generating correct edges in the
179 /// dep-graph -- see the [rustc guide] for more details on
180 /// the dep-graph). To this end, the task function gets exactly two
181 /// pieces of state: the context `cx` and an argument `arg`. Both
182 /// of these bits of state must be of some type that implements
183 /// `DepGraphSafe` and hence does not leak.
185 /// The choice of two arguments is not fundamental. One argument
186 /// would work just as well, since multiple values can be
187 /// collected using tuples. However, using two arguments works out
188 /// to be quite convenient, since it is common to need a context
189 /// (`cx`) and some argument (e.g., a `DefId` identifying what
190 /// item to process).
192 /// For cases where you need some other number of arguments:
194 /// - If you only need one argument, just use `()` for the `arg`
196 /// - If you need 3+ arguments, use a tuple for the
199 /// [rustc guide]: https://rust-lang-nursery.github.io/rustc-guide/incremental-compilation.html
200 pub fn with_task
<'gcx
, C
, A
, R
>(&self,
206 where C
: DepGraphSafe
+ StableHashingContextProvider
<'gcx
>,
207 R
: HashStable
<StableHashingContext
<'gcx
>>,
209 self.with_task_impl(key
, cx
, arg
, false, task
,
210 |key
| OpenTask
::Regular(Lock
::new(RegularOpenTask
{
213 read_set
: FxHashSet(),
215 |data
, key
, task
| data
.borrow_mut().complete_task(key
, task
))
218 /// Creates a new dep-graph input with value `input`
219 pub fn input_task
<'gcx
, C
, R
>(&self,
224 where C
: DepGraphSafe
+ StableHashingContextProvider
<'gcx
>,
225 R
: HashStable
<StableHashingContext
<'gcx
>>,
227 fn identity_fn
<C
, A
>(_
: C
, arg
: A
) -> A
{
231 self.with_task_impl(key
, cx
, input
, true, identity_fn
,
232 |_
| OpenTask
::Ignore
,
233 |data
, key
, _
| data
.borrow_mut().alloc_node(key
, Vec
::new()))
236 fn with_task_impl
<'gcx
, C
, A
, R
>(
243 create_task
: fn(DepNode
) -> OpenTask
,
244 finish_task_and_alloc_depnode
: fn(&Lock
<CurrentDepGraph
>,
246 OpenTask
) -> DepNodeIndex
247 ) -> (R
, DepNodeIndex
)
249 C
: DepGraphSafe
+ StableHashingContextProvider
<'gcx
>,
250 R
: HashStable
<StableHashingContext
<'gcx
>>,
252 if let Some(ref data
) = self.data
{
253 let open_task
= create_task(key
);
255 // In incremental mode, hash the result of the task. We don't
256 // do anything with the hash yet, but we are computing it
258 // - we make sure that the infrastructure works and
259 // - we can get an idea of the runtime cost.
260 let mut hcx
= cx
.get_stable_hashing_context();
262 if cfg
!(debug_assertions
) {
263 profq_msg(hcx
.sess(), ProfileQueriesMsg
::TaskBegin(key
.clone()))
266 let result
= if no_tcx
{
269 ty
::tls
::with_context(|icx
| {
270 let icx
= ty
::tls
::ImplicitCtxt
{
275 ty
::tls
::enter_context(&icx
, |_
| {
281 if cfg
!(debug_assertions
) {
282 profq_msg(hcx
.sess(), ProfileQueriesMsg
::TaskEnd
)
285 let dep_node_index
= finish_task_and_alloc_depnode(&data
.current
, key
, open_task
);
287 let mut stable_hasher
= StableHasher
::new();
288 result
.hash_stable(&mut hcx
, &mut stable_hasher
);
290 let current_fingerprint
= stable_hasher
.finish();
292 // Store the current fingerprint
294 let mut fingerprints
= self.fingerprints
.borrow_mut();
296 if dep_node_index
.index() >= fingerprints
.len() {
297 fingerprints
.resize(dep_node_index
.index() + 1, Fingerprint
::ZERO
);
300 debug_assert
!(fingerprints
[dep_node_index
] == Fingerprint
::ZERO
,
301 "DepGraph::with_task() - Duplicate fingerprint \
302 insertion for {:?}", key
);
303 fingerprints
[dep_node_index
] = current_fingerprint
;
306 // Determine the color of the new DepNode.
307 if let Some(prev_index
) = data
.previous
.node_to_index_opt(&key
) {
308 let prev_fingerprint
= data
.previous
.fingerprint_by_index(prev_index
);
310 let color
= if current_fingerprint
== prev_fingerprint
{
311 DepNodeColor
::Green(dep_node_index
)
316 let mut colors
= data
.colors
.borrow_mut();
317 debug_assert
!(colors
.get(prev_index
).is_none(),
318 "DepGraph::with_task() - Duplicate DepNodeColor \
319 insertion for {:?}", key
);
321 colors
.insert(prev_index
, color
);
324 (result
, dep_node_index
)
326 if key
.kind
.fingerprint_needed_for_crate_hash() {
327 let mut hcx
= cx
.get_stable_hashing_context();
328 let result
= task(cx
, arg
);
329 let mut stable_hasher
= StableHasher
::new();
330 result
.hash_stable(&mut hcx
, &mut stable_hasher
);
331 let fingerprint
= stable_hasher
.finish();
333 let mut fingerprints
= self.fingerprints
.borrow_mut();
334 let dep_node_index
= DepNodeIndex
::new(fingerprints
.len());
335 fingerprints
.push(fingerprint
);
337 debug_assert
!(fingerprints
[dep_node_index
] == fingerprint
,
338 "DepGraph::with_task() - Assigned fingerprint to \
339 unexpected index for {:?}", key
);
341 (result
, dep_node_index
)
343 (task(cx
, arg
), DepNodeIndex
::INVALID
)
348 /// Execute something within an "anonymous" task, that is, a task the
349 /// DepNode of which is determined by the list of inputs it read from.
350 pub fn with_anon_task
<OP
,R
>(&self, dep_kind
: DepKind
, op
: OP
) -> (R
, DepNodeIndex
)
351 where OP
: FnOnce() -> R
353 if let Some(ref data
) = self.data
{
354 let (result
, open_task
) = ty
::tls
::with_context(|icx
| {
355 let task
= OpenTask
::Anon(Lock
::new(AnonOpenTask
{
357 read_set
: FxHashSet(),
361 let icx
= ty
::tls
::ImplicitCtxt
{
366 ty
::tls
::enter_context(&icx
, |_
| {
373 let dep_node_index
= data
.current
375 .pop_anon_task(dep_kind
, open_task
);
376 (result
, dep_node_index
)
378 (op(), DepNodeIndex
::INVALID
)
382 /// Execute something within an "eval-always" task which is a task
383 // that runs whenever anything changes.
384 pub fn with_eval_always_task
<'gcx
, C
, A
, R
>(&self,
390 where C
: DepGraphSafe
+ StableHashingContextProvider
<'gcx
>,
391 R
: HashStable
<StableHashingContext
<'gcx
>>,
393 self.with_task_impl(key
, cx
, arg
, false, task
,
394 |key
| OpenTask
::EvalAlways { node: key }
,
395 |data
, key
, task
| data
.borrow_mut().complete_eval_always_task(key
, task
))
399 pub fn read(&self, v
: DepNode
) {
400 if let Some(ref data
) = self.data
{
401 let mut current
= data
.current
.borrow_mut();
402 if let Some(&dep_node_index
) = current
.node_to_node_index
.get(&v
) {
403 current
.read_index(dep_node_index
);
405 bug
!("DepKind {:?} should be pre-allocated but isn't.", v
.kind
)
411 pub fn read_index(&self, dep_node_index
: DepNodeIndex
) {
412 if let Some(ref data
) = self.data
{
413 data
.current
.borrow_mut().read_index(dep_node_index
);
418 pub fn dep_node_index_of(&self, dep_node
: &DepNode
) -> DepNodeIndex
{
431 pub fn dep_node_exists(&self, dep_node
: &DepNode
) -> bool
{
432 if let Some(ref data
) = self.data
{
433 data
.current
.borrow_mut().node_to_node_index
.contains_key(dep_node
)
440 pub fn fingerprint_of(&self, dep_node_index
: DepNodeIndex
) -> Fingerprint
{
441 match self.fingerprints
.borrow().get(dep_node_index
) {
442 Some(&fingerprint
) => fingerprint
,
444 if let Some(ref data
) = self.data
{
445 let dep_node
= data
.current
.borrow().nodes
[dep_node_index
];
446 bug
!("Could not find current fingerprint for {:?}", dep_node
)
448 bug
!("Could not find current fingerprint for {:?}", dep_node_index
)
454 pub fn prev_fingerprint_of(&self, dep_node
: &DepNode
) -> Option
<Fingerprint
> {
455 self.data
.as_ref().unwrap().previous
.fingerprint_of(dep_node
)
459 pub fn prev_dep_node_index_of(&self, dep_node
: &DepNode
) -> SerializedDepNodeIndex
{
460 self.data
.as_ref().unwrap().previous
.node_to_index(dep_node
)
463 /// Indicates that a previous work product exists for `v`. This is
464 /// invoked during initial start-up based on what nodes are clean
465 /// (and what files exist in the incr. directory).
466 pub fn insert_previous_work_product(&self, v
: &WorkProductId
, data
: WorkProduct
) {
467 debug
!("insert_previous_work_product({:?}, {:?})", v
, data
);
471 .previous_work_products
473 .insert(v
.clone(), data
);
476 /// Indicates that we created the given work-product in this run
477 /// for `v`. This record will be preserved and loaded in the next
479 pub fn insert_work_product(&self, v
: &WorkProductId
, data
: WorkProduct
) {
480 debug
!("insert_work_product({:?}, {:?})", v
, data
);
486 .insert(v
.clone(), data
);
489 /// Check whether a previous work product exists for `v` and, if
490 /// so, return the path that leads to it. Used to skip doing work.
491 pub fn previous_work_product(&self, v
: &WorkProductId
) -> Option
<WorkProduct
> {
495 data
.previous_work_products
.borrow().get(v
).cloned()
499 /// Access the map of work-products created during this run. Only
500 /// used during saving of the dep-graph.
501 pub fn work_products(&self) -> ReadGuard
<FxHashMap
<WorkProductId
, WorkProduct
>> {
502 self.data
.as_ref().unwrap().work_products
.borrow()
505 /// Access the map of work-products created during the cached run. Only
506 /// used during saving of the dep-graph.
507 pub fn previous_work_products(&self) -> ReadGuard
<FxHashMap
<WorkProductId
, WorkProduct
>> {
508 self.data
.as_ref().unwrap().previous_work_products
.borrow()
512 pub fn register_dep_node_debug_str
<F
>(&self,
515 where F
: FnOnce() -> String
517 let dep_node_debug
= &self.data
.as_ref().unwrap().dep_node_debug
;
519 if dep_node_debug
.borrow().contains_key(&dep_node
) {
522 let debug_str
= debug_str_gen();
523 dep_node_debug
.borrow_mut().insert(dep_node
, debug_str
);
526 pub(super) fn dep_node_debug_str(&self, dep_node
: DepNode
) -> Option
<String
> {
527 self.data
.as_ref().and_then(|t
| t
.dep_node_debug
.borrow().get(&dep_node
).cloned())
530 pub fn edge_deduplication_data(&self) -> (u64, u64) {
531 let current_dep_graph
= self.data
.as_ref().unwrap().current
.borrow();
533 (current_dep_graph
.total_read_count
, current_dep_graph
.total_duplicate_read_count
)
536 pub fn serialize(&self) -> SerializedDepGraph
{
537 let mut fingerprints
= self.fingerprints
.borrow_mut();
538 let current_dep_graph
= self.data
.as_ref().unwrap().current
.borrow();
540 // Make sure we don't run out of bounds below.
541 if current_dep_graph
.nodes
.len() > fingerprints
.len() {
542 fingerprints
.resize(current_dep_graph
.nodes
.len(), Fingerprint
::ZERO
);
545 let fingerprints
= fingerprints
.clone().convert_index_type();
546 let nodes
= current_dep_graph
.nodes
.clone().convert_index_type();
548 let total_edge_count
: usize = current_dep_graph
.edges
.iter()
552 let mut edge_list_indices
= IndexVec
::with_capacity(nodes
.len());
553 let mut edge_list_data
= Vec
::with_capacity(total_edge_count
);
555 for (current_dep_node_index
, edges
) in current_dep_graph
.edges
.iter_enumerated() {
556 let start
= edge_list_data
.len() as u32;
557 // This should really just be a memcpy :/
558 edge_list_data
.extend(edges
.iter().map(|i
| SerializedDepNodeIndex
::new(i
.index())));
559 let end
= edge_list_data
.len() as u32;
561 debug_assert_eq
!(current_dep_node_index
.index(), edge_list_indices
.len());
562 edge_list_indices
.push((start
, end
));
565 debug_assert
!(edge_list_data
.len() <= ::std
::u32::MAX
as usize);
566 debug_assert_eq
!(edge_list_data
.len(), total_edge_count
);
576 pub fn node_color(&self, dep_node
: &DepNode
) -> Option
<DepNodeColor
> {
577 if let Some(ref data
) = self.data
{
578 if let Some(prev_index
) = data
.previous
.node_to_index_opt(dep_node
) {
579 return data
.colors
.borrow().get(prev_index
)
581 // This is a node that did not exist in the previous compilation
582 // session, so we consider it to be red.
583 return Some(DepNodeColor
::Red
)
590 pub fn try_mark_green
<'tcx
>(&self,
591 tcx
: TyCtxt
<'_
, 'tcx
, 'tcx
>,
593 -> Option
<DepNodeIndex
> {
594 debug
!("try_mark_green({:?}) - BEGIN", dep_node
);
595 let data
= self.data
.as_ref().unwrap();
597 #[cfg(not(parallel_queries))]
598 debug_assert
!(!data
.current
.borrow().node_to_node_index
.contains_key(dep_node
));
600 if dep_node
.kind
.is_input() {
601 // We should only hit try_mark_green() for inputs that do not exist
602 // anymore in the current compilation session. Existing inputs are
603 // eagerly marked as either red/green before any queries are
605 debug_assert
!(dep_node
.extract_def_id(tcx
).is_none());
606 debug
!("try_mark_green({:?}) - END - DepNode is deleted input", dep_node
);
610 let (prev_deps
, prev_dep_node_index
) = match data
.previous
.edges_from(dep_node
) {
612 // This DepNode and the corresponding query invocation existed
613 // in the previous compilation session too, so we can try to
614 // mark it as green by recursively marking all of its
615 // dependencies green.
619 // This DepNode did not exist in the previous compilation session,
620 // so we cannot mark it as green.
621 debug
!("try_mark_green({:?}) - END - DepNode does not exist in \
622 current compilation session anymore", dep_node
);
627 debug_assert
!(data
.colors
.borrow().get(prev_dep_node_index
).is_none());
629 let mut current_deps
= Vec
::new();
631 for &dep_dep_node_index
in prev_deps
{
632 let dep_dep_node_color
= data
.colors
.borrow().get(dep_dep_node_index
);
634 match dep_dep_node_color
{
635 Some(DepNodeColor
::Green(node_index
)) => {
636 // This dependency has been marked as green before, we are
637 // still fine and can continue with checking the other
639 debug
!("try_mark_green({:?}) --- found dependency {:?} to \
640 be immediately green",
642 data
.previous
.index_to_node(dep_dep_node_index
));
643 current_deps
.push(node_index
);
645 Some(DepNodeColor
::Red
) => {
646 // We found a dependency the value of which has changed
647 // compared to the previous compilation session. We cannot
648 // mark the DepNode as green and also don't need to bother
649 // with checking any of the other dependencies.
650 debug
!("try_mark_green({:?}) - END - dependency {:?} was \
653 data
.previous
.index_to_node(dep_dep_node_index
));
657 let dep_dep_node
= &data
.previous
.index_to_node(dep_dep_node_index
);
659 // We don't know the state of this dependency. If it isn't
660 // an input node, let's try to mark it green recursively.
661 if !dep_dep_node
.kind
.is_input() {
662 debug
!("try_mark_green({:?}) --- state of dependency {:?} \
663 is unknown, trying to mark it green", dep_node
,
666 if let Some(node_index
) = self.try_mark_green(tcx
, dep_dep_node
) {
667 debug
!("try_mark_green({:?}) --- managed to MARK \
668 dependency {:?} as green", dep_node
, dep_dep_node
);
669 current_deps
.push(node_index
);
673 match dep_dep_node
.kind
{
676 DepKind
::CrateMetadata
=> {
677 if dep_node
.extract_def_id(tcx
).is_none() {
678 // If the node does not exist anymore, we
679 // just fail to mark green.
682 // If the node does exist, it should have
683 // been pre-allocated.
684 bug
!("DepNode {:?} should have been \
685 pre-allocated but wasn't.",
690 // For other kinds of inputs it's OK to be
696 // We failed to mark it green, so we try to force the query.
697 debug
!("try_mark_green({:?}) --- trying to force \
698 dependency {:?}", dep_node
, dep_dep_node
);
699 if ::ty
::maps
::force_from_dep_node(tcx
, dep_dep_node
) {
700 let dep_dep_node_color
= data
.colors
.borrow().get(dep_dep_node_index
);
702 match dep_dep_node_color
{
703 Some(DepNodeColor
::Green(node_index
)) => {
704 debug
!("try_mark_green({:?}) --- managed to \
705 FORCE dependency {:?} to green",
706 dep_node
, dep_dep_node
);
707 current_deps
.push(node_index
);
709 Some(DepNodeColor
::Red
) => {
710 debug
!("try_mark_green({:?}) - END - \
711 dependency {:?} was red after forcing",
717 if !tcx
.sess
.has_errors() {
718 bug
!("try_mark_green() - Forcing the DepNode \
719 should have set its color")
721 // If the query we just forced has resulted
722 // in some kind of compilation error, we
723 // don't expect that the corresponding
724 // dep-node color has been updated.
729 // The DepNode could not be forced.
730 debug
!("try_mark_green({:?}) - END - dependency {:?} \
731 could not be forced", dep_node
, dep_dep_node
);
738 // If we got here without hitting a `return` that means that all
739 // dependencies of this DepNode could be marked as green. Therefore we
740 // can also mark this DepNode as green.
742 // There may be multiple threads trying to mark the same dep node green concurrently
744 let (dep_node_index
, did_allocation
) = {
745 let mut current
= data
.current
.borrow_mut();
747 if let Some(&dep_node_index
) = current
.node_to_node_index
.get(&dep_node
) {
748 // Someone else allocated it before us
749 (dep_node_index
, false)
751 // We allocating an entry for the node in the current dependency graph and
752 // adding all the appropriate edges imported from the previous graph
753 (current
.alloc_node(*dep_node
, current_deps
), true)
757 // ... copying the fingerprint from the previous graph too, so we don't
758 // have to recompute it ...
760 let fingerprint
= data
.previous
.fingerprint_by_index(prev_dep_node_index
);
761 let mut fingerprints
= self.fingerprints
.borrow_mut();
763 if dep_node_index
.index() >= fingerprints
.len() {
764 fingerprints
.resize(dep_node_index
.index() + 1, Fingerprint
::ZERO
);
767 // Multiple threads can all write the same fingerprint here
768 #[cfg(not(parallel_queries))]
769 debug_assert
!(fingerprints
[dep_node_index
] == Fingerprint
::ZERO
,
770 "DepGraph::try_mark_green() - Duplicate fingerprint \
771 insertion for {:?}", dep_node
);
773 fingerprints
[dep_node_index
] = fingerprint
;
776 // ... emitting any stored diagnostic ...
778 // Only the thread which did the allocation emits the error messages
780 // FIXME: Ensure that these are printed before returning for all threads.
781 // Currently threads where did_allocation = false can continue on
782 // and emit other diagnostics before these diagnostics are emitted.
783 // Such diagnostics should be emitted after these.
784 // See https://github.com/rust-lang/rust/issues/48685
785 let diagnostics
= tcx
.on_disk_query_result_cache
786 .load_diagnostics(tcx
, prev_dep_node_index
);
788 if diagnostics
.len() > 0 {
789 let handle
= tcx
.sess
.diagnostic();
791 // Promote the previous diagnostics to the current session.
792 tcx
.on_disk_query_result_cache
793 .store_diagnostics(dep_node_index
, diagnostics
.clone());
795 for diagnostic
in diagnostics
{
796 DiagnosticBuilder
::new_diagnostic(handle
, diagnostic
).emit();
801 // ... and finally storing a "Green" entry in the color map.
802 let mut colors
= data
.colors
.borrow_mut();
803 // Multiple threads can all write the same color here
804 #[cfg(not(parallel_queries))]
805 debug_assert
!(colors
.get(prev_dep_node_index
).is_none(),
806 "DepGraph::try_mark_green() - Duplicate DepNodeColor \
807 insertion for {:?}", dep_node
);
809 colors
.insert(prev_dep_node_index
, DepNodeColor
::Green(dep_node_index
));
811 debug
!("try_mark_green({:?}) - END - successfully marked as green", dep_node
);
815 // Returns true if the given node has been marked as green during the
816 // current compilation session. Used in various assertions
817 pub fn is_green(&self, dep_node
: &DepNode
) -> bool
{
818 self.node_color(dep_node
).map(|c
| c
.is_green()).unwrap_or(false)
821 // This method loads all on-disk cacheable query results into memory, so
822 // they can be written out to the new cache file again. Most query results
823 // will already be in memory but in the case where we marked something as
824 // green but then did not need the value, that value will never have been
827 // This method will only load queries that will end up in the disk cache.
828 // Other queries will not be executed.
829 pub fn exec_cache_promotions
<'a
, 'tcx
>(&self, tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>) {
830 let green_nodes
: Vec
<DepNode
> = {
831 let data
= self.data
.as_ref().unwrap();
832 let colors
= data
.colors
.borrow();
833 colors
.values
.indices().filter_map(|prev_index
| {
834 match colors
.get(prev_index
) {
835 Some(DepNodeColor
::Green(_
)) => {
836 let dep_node
= data
.previous
.index_to_node(prev_index
);
837 if dep_node
.cache_on_disk(tcx
) {
844 Some(DepNodeColor
::Red
) => {
845 // We can skip red nodes because a node can only be marked
846 // as red if the query result was recomputed and thus is
847 // already in memory.
854 for dep_node
in green_nodes
{
855 dep_node
.load_from_on_disk_cache(tcx
);
859 pub fn mark_loaded_from_cache(&self, dep_node_index
: DepNodeIndex
, state
: bool
) {
860 debug
!("mark_loaded_from_cache({:?}, {})",
861 self.data
.as_ref().unwrap().current
.borrow().nodes
[dep_node_index
],
869 .insert(dep_node_index
, state
);
872 pub fn was_loaded_from_cache(&self, dep_node
: &DepNode
) -> Option
<bool
> {
873 let data
= self.data
.as_ref().unwrap();
874 let dep_node_index
= data
.current
.borrow().node_to_node_index
[dep_node
];
875 data
.loaded_from_cache
.borrow().get(&dep_node_index
).cloned()
879 /// A "work product" is an intermediate result that we save into the
880 /// incremental directory for later re-use. The primary example are
881 /// the object files that we save for each partition at code
884 /// Each work product is associated with a dep-node, representing the
885 /// process that produced the work-product. If that dep-node is found
886 /// to be dirty when we load up, then we will delete the work-product
887 /// at load time. If the work-product is found to be clean, then we
888 /// will keep a record in the `previous_work_products` list.
890 /// In addition, work products have an associated hash. This hash is
891 /// an extra hash that can be used to decide if the work-product from
892 /// a previous compilation can be re-used (in addition to the dirty
895 /// As the primary example, consider the object files we generate for
896 /// each partition. In the first run, we create partitions based on
897 /// the symbols that need to be compiled. For each partition P, we
898 /// hash the symbols in P and create a `WorkProduct` record associated
899 /// with `DepNode::TransPartition(P)`; the hash is the set of symbols
902 /// The next time we compile, if the `DepNode::TransPartition(P)` is
903 /// judged to be clean (which means none of the things we read to
904 /// generate the partition were found to be dirty), it will be loaded
905 /// into previous work products. We will then regenerate the set of
906 /// symbols in the partition P and hash them (note that new symbols
907 /// may be added -- for example, new monomorphizations -- even if
908 /// nothing in P changed!). We will compare that hash against the
909 /// previous hash. If it matches up, we can reuse the object file.
910 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
911 pub struct WorkProduct
{
912 pub cgu_name
: String
,
913 /// Saved files associated with this CGU
914 pub saved_files
: Vec
<(WorkProductFileKind
, String
)>,
917 #[derive(Clone, Copy, Debug, RustcEncodable, RustcDecodable)]
918 pub enum WorkProductFileKind
{
924 pub(super) struct CurrentDepGraph
{
925 nodes
: IndexVec
<DepNodeIndex
, DepNode
>,
926 edges
: IndexVec
<DepNodeIndex
, Vec
<DepNodeIndex
>>,
927 node_to_node_index
: FxHashMap
<DepNode
, DepNodeIndex
>,
928 forbidden_edge
: Option
<EdgeFilter
>,
930 // Anonymous DepNodes are nodes the ID of which we compute from the list of
931 // their edges. This has the beneficial side-effect that multiple anonymous
932 // nodes can be coalesced into one without changing the semantics of the
933 // dependency graph. However, the merging of nodes can lead to a subtle
934 // problem during red-green marking: The color of an anonymous node from
935 // the current session might "shadow" the color of the node with the same
936 // ID from the previous session. In order to side-step this problem, we make
937 // sure that anon-node IDs allocated in different sessions don't overlap.
938 // This is implemented by mixing a session-key into the ID fingerprint of
939 // each anon node. The session-key is just a random number generated when
940 // the DepGraph is created.
941 anon_id_seed
: Fingerprint
,
943 total_read_count
: u64,
944 total_duplicate_read_count
: u64,
947 impl CurrentDepGraph
{
948 fn new() -> CurrentDepGraph
{
949 use std
::time
::{SystemTime, UNIX_EPOCH}
;
951 let duration
= SystemTime
::now().duration_since(UNIX_EPOCH
).unwrap();
952 let nanos
= duration
.as_secs() * 1_000_000_000 +
953 duration
.subsec_nanos() as u64;
954 let mut stable_hasher
= StableHasher
::new();
955 nanos
.hash(&mut stable_hasher
);
957 let forbidden_edge
= if cfg
!(debug_assertions
) {
958 match env
::var("RUST_FORBID_DEP_GRAPH_EDGE") {
960 match EdgeFilter
::new(&s
) {
962 Err(err
) => bug
!("RUST_FORBID_DEP_GRAPH_EDGE invalid: {}", err
),
972 nodes
: IndexVec
::new(),
973 edges
: IndexVec
::new(),
974 node_to_node_index
: FxHashMap(),
975 anon_id_seed
: stable_hasher
.finish(),
978 total_duplicate_read_count
: 0,
982 fn complete_task(&mut self, key
: DepNode
, task
: OpenTask
) -> DepNodeIndex
{
983 if let OpenTask
::Regular(task
) = task
{
984 let RegularOpenTask
{
988 } = task
.into_inner();
989 assert_eq
!(node
, key
);
991 // If this is an input node, we expect that it either has no
992 // dependencies, or that it just depends on DepKind::CrateMetadata
993 // or DepKind::Krate. This happens for some "thin wrapper queries"
994 // like `crate_disambiguator` which sometimes have zero deps (for
995 // when called for LOCAL_CRATE) or they depend on a CrateMetadata
997 if cfg
!(debug_assertions
) {
998 if node
.kind
.is_input() && reads
.len() > 0 &&
999 // FIXME(mw): Special case for DefSpan until Spans are handled
1000 // better in general.
1001 node
.kind
!= DepKind
::DefSpan
&&
1002 reads
.iter().any(|&i
| {
1003 !(self.nodes
[i
].kind
== DepKind
::CrateMetadata
||
1004 self.nodes
[i
].kind
== DepKind
::Krate
)
1007 bug
!("Input node {:?} with unexpected reads: {:?}",
1009 reads
.iter().map(|&i
| self.nodes
[i
]).collect
::<Vec
<_
>>())
1013 self.alloc_node(node
, reads
)
1015 bug
!("complete_task() - Expected regular task to be popped")
1019 fn pop_anon_task(&mut self, kind
: DepKind
, task
: OpenTask
) -> DepNodeIndex
{
1020 if let OpenTask
::Anon(task
) = task
{
1024 } = task
.into_inner();
1025 debug_assert
!(!kind
.is_input());
1027 let mut fingerprint
= self.anon_id_seed
;
1028 let mut hasher
= StableHasher
::new();
1030 for &read
in reads
.iter() {
1031 let read_dep_node
= self.nodes
[read
];
1033 ::std
::mem
::discriminant(&read_dep_node
.kind
).hash(&mut hasher
);
1035 // Fingerprint::combine() is faster than sending Fingerprint
1036 // through the StableHasher (at least as long as StableHasher
1038 fingerprint
= fingerprint
.combine(read_dep_node
.hash
);
1041 fingerprint
= fingerprint
.combine(hasher
.finish());
1043 let target_dep_node
= DepNode
{
1048 if let Some(&index
) = self.node_to_node_index
.get(&target_dep_node
) {
1051 self.alloc_node(target_dep_node
, reads
)
1054 bug
!("pop_anon_task() - Expected anonymous task to be popped")
1058 fn complete_eval_always_task(&mut self, key
: DepNode
, task
: OpenTask
) -> DepNodeIndex
{
1059 if let OpenTask
::EvalAlways
{
1062 debug_assert_eq
!(node
, key
);
1063 let krate_idx
= self.node_to_node_index
[&DepNode
::new_no_params(DepKind
::Krate
)];
1064 self.alloc_node(node
, vec
![krate_idx
])
1066 bug
!("complete_eval_always_task() - Expected eval always task to be popped");
1070 fn read_index(&mut self, source
: DepNodeIndex
) {
1071 ty
::tls
::with_context_opt(|icx
| {
1072 let icx
= if let Some(icx
) = icx { icx }
else { return }
;
1074 OpenTask
::Regular(ref task
) => {
1075 let mut task
= task
.lock();
1076 self.total_read_count
+= 1;
1077 if task
.read_set
.insert(source
) {
1078 task
.reads
.push(source
);
1080 if cfg
!(debug_assertions
) {
1081 if let Some(ref forbidden_edge
) = self.forbidden_edge
{
1082 let target
= &task
.node
;
1083 let source
= self.nodes
[source
];
1084 if forbidden_edge
.test(&source
, &target
) {
1085 bug
!("forbidden edge {:?} -> {:?} created",
1092 self.total_duplicate_read_count
+= 1;
1095 OpenTask
::Anon(ref task
) => {
1096 let mut task
= task
.lock();
1097 if task
.read_set
.insert(source
) {
1098 task
.reads
.push(source
);
1101 OpenTask
::Ignore
| OpenTask
::EvalAlways { .. }
=> {
1108 fn alloc_node(&mut self,
1110 edges
: Vec
<DepNodeIndex
>)
1112 debug_assert_eq
!(self.edges
.len(), self.nodes
.len());
1113 debug_assert_eq
!(self.node_to_node_index
.len(), self.nodes
.len());
1114 debug_assert
!(!self.node_to_node_index
.contains_key(&dep_node
));
1115 let dep_node_index
= DepNodeIndex
::new(self.nodes
.len());
1116 self.nodes
.push(dep_node
);
1117 self.node_to_node_index
.insert(dep_node
, dep_node_index
);
1118 self.edges
.push(edges
);
1123 pub struct RegularOpenTask
{
1125 reads
: Vec
<DepNodeIndex
>,
1126 read_set
: FxHashSet
<DepNodeIndex
>,
1129 pub struct AnonOpenTask
{
1130 reads
: Vec
<DepNodeIndex
>,
1131 read_set
: FxHashSet
<DepNodeIndex
>,
1135 Regular(Lock
<RegularOpenTask
>),
1136 Anon(Lock
<AnonOpenTask
>),
1143 // A data structure that stores Option<DepNodeColor> values as a contiguous
1144 // array, using one u32 per entry.
1145 struct DepNodeColorMap
{
1146 values
: IndexVec
<SerializedDepNodeIndex
, u32>,
1149 const COMPRESSED_NONE
: u32 = 0;
1150 const COMPRESSED_RED
: u32 = 1;
1151 const COMPRESSED_FIRST_GREEN
: u32 = 2;
1153 impl DepNodeColorMap
{
1154 fn new(size
: usize) -> DepNodeColorMap
{
1156 values
: IndexVec
::from_elem_n(COMPRESSED_NONE
, size
)
1160 fn get(&self, index
: SerializedDepNodeIndex
) -> Option
<DepNodeColor
> {
1161 match self.values
[index
] {
1162 COMPRESSED_NONE
=> None
,
1163 COMPRESSED_RED
=> Some(DepNodeColor
::Red
),
1164 value
=> Some(DepNodeColor
::Green(DepNodeIndex(value
- COMPRESSED_FIRST_GREEN
)))
1168 fn insert(&mut self, index
: SerializedDepNodeIndex
, color
: DepNodeColor
) {
1169 self.values
[index
] = match color
{
1170 DepNodeColor
::Red
=> COMPRESSED_RED
,
1171 DepNodeColor
::Green(index
) => index
.0 + COMPRESSED_FIRST_GREEN
,