rustc_query_system/dep_graph/graph.rs
1use std::assert_matches::assert_matches;
2use std::fmt::Debug;
3use std::hash::Hash;
4use std::marker::PhantomData;
5use std::sync::Arc;
6use std::sync::atomic::{AtomicU32, Ordering};
7
8use rustc_data_structures::fingerprint::{Fingerprint, PackedFingerprint};
9use rustc_data_structures::fx::{FxHashMap, FxHashSet};
10use rustc_data_structures::outline;
11use rustc_data_structures::profiling::QueryInvocationId;
12use rustc_data_structures::sharded::{self, ShardedHashMap};
13use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
14use rustc_data_structures::sync::{AtomicU64, Lock};
15use rustc_data_structures::unord::UnordMap;
16use rustc_errors::DiagInner;
17use rustc_index::IndexVec;
18use rustc_macros::{Decodable, Encodable};
19use rustc_serialize::opaque::{FileEncodeResult, FileEncoder};
20use rustc_session::Session;
21use tracing::{debug, instrument};
22#[cfg(debug_assertions)]
23use {super::debug::EdgeFilter, std::env};
24
25use super::query::DepGraphQuery;
26use super::serialized::{GraphEncoder, SerializedDepGraph, SerializedDepNodeIndex};
27use super::{DepContext, DepKind, DepNode, Deps, HasDepContext, WorkProductId};
28use crate::dep_graph::edges::EdgesVec;
29use crate::ich::StableHashingContext;
30use crate::query::{QueryContext, QuerySideEffect};
31
32#[derive(Clone)]
33pub struct DepGraph<D: Deps> {
34 data: Option<Arc<DepGraphData<D>>>,
35
36 /// This field is used for assigning DepNodeIndices when running in
37 /// non-incremental mode. Even in non-incremental mode we make sure that
38 /// each task has a `DepNodeIndex` that uniquely identifies it. This unique
39 /// ID is used for self-profiling.
40 virtual_dep_node_index: Arc<AtomicU32>,
41}
42
43rustc_index::newtype_index! {
44 pub struct DepNodeIndex {}
45}
46
47// We store a large collection of these in `prev_index_to_index` during
48// non-full incremental builds, and want to ensure that the element size
49// doesn't inadvertently increase.
50rustc_data_structures::static_assert_size!(Option<DepNodeIndex>, 4);
51
52impl DepNodeIndex {
53 const SINGLETON_ZERO_DEPS_ANON_NODE: DepNodeIndex = DepNodeIndex::ZERO;
54 pub const FOREVER_RED_NODE: DepNodeIndex = DepNodeIndex::from_u32(1);
55}
56
57impl From<DepNodeIndex> for QueryInvocationId {
58 #[inline(always)]
59 fn from(dep_node_index: DepNodeIndex) -> Self {
60 QueryInvocationId(dep_node_index.as_u32())
61 }
62}
63
64pub struct MarkFrame<'a> {
65 index: SerializedDepNodeIndex,
66 parent: Option<&'a MarkFrame<'a>>,
67}
68
69#[derive(Debug)]
70pub(super) enum DepNodeColor {
71 Red,
72 Green(DepNodeIndex),
73}
74
75impl DepNodeColor {
76 #[inline]
77 fn is_green(self) -> bool {
78 match self {
79 DepNodeColor::Red => false,
80 DepNodeColor::Green(_) => true,
81 }
82 }
83}
84
85pub(crate) struct DepGraphData<D: Deps> {
86 /// The new encoding of the dependency graph, optimized for red/green
87 /// tracking. The `current` field is the dependency graph of only the
88 /// current compilation session: We don't merge the previous dep-graph into
89 /// current one anymore, but we do reference shared data to save space.
90 current: CurrentDepGraph<D>,
91
92 /// The dep-graph from the previous compilation session. It contains all
93 /// nodes and edges as well as all fingerprints of nodes that have them.
94 previous: Arc<SerializedDepGraph>,
95
96 colors: DepNodeColorMap,
97
98 /// When we load, there may be `.o` files, cached MIR, or other such
99 /// things available to us. If we find that they are not dirty, we
100 /// load the path to the file storing those work-products here into
101 /// this map. We can later look for and extract that data.
102 previous_work_products: WorkProductMap,
103
104 dep_node_debug: Lock<FxHashMap<DepNode, String>>,
105
106 /// Used by incremental compilation tests to assert that
107 /// a particular query result was decoded from disk
108 /// (not just marked green)
109 debug_loaded_from_disk: Lock<FxHashSet<DepNode>>,
110}
111
112pub fn hash_result<R>(hcx: &mut StableHashingContext<'_>, result: &R) -> Fingerprint
113where
114 R: for<'a> HashStable<StableHashingContext<'a>>,
115{
116 let mut stable_hasher = StableHasher::new();
117 result.hash_stable(hcx, &mut stable_hasher);
118 stable_hasher.finish()
119}
120
121impl<D: Deps> DepGraph<D> {
122 pub fn new(
123 session: &Session,
124 prev_graph: Arc<SerializedDepGraph>,
125 prev_work_products: WorkProductMap,
126 encoder: FileEncoder,
127 record_graph: bool,
128 record_stats: bool,
129 ) -> DepGraph<D> {
130 let prev_graph_node_count = prev_graph.node_count();
131
132 let current = CurrentDepGraph::new(
133 session,
134 prev_graph_node_count,
135 encoder,
136 record_graph,
137 record_stats,
138 Arc::clone(&prev_graph),
139 );
140
141 let colors = DepNodeColorMap::new(prev_graph_node_count);
142
143 // Instantiate a node with zero dependencies only once for anonymous queries.
144 let _green_node_index = current.alloc_new_node(
145 DepNode { kind: D::DEP_KIND_ANON_ZERO_DEPS, hash: current.anon_id_seed.into() },
146 EdgesVec::new(),
147 Fingerprint::ZERO,
148 );
149 assert_eq!(_green_node_index, DepNodeIndex::SINGLETON_ZERO_DEPS_ANON_NODE);
150
151 // Instantiate a dependy-less red node only once for anonymous queries.
152 let red_node_index = current.alloc_new_node(
153 DepNode { kind: D::DEP_KIND_RED, hash: Fingerprint::ZERO.into() },
154 EdgesVec::new(),
155 Fingerprint::ZERO,
156 );
157 assert_eq!(red_node_index, DepNodeIndex::FOREVER_RED_NODE);
158 if prev_graph_node_count > 0 {
159 colors.insert(
160 SerializedDepNodeIndex::from_u32(DepNodeIndex::FOREVER_RED_NODE.as_u32()),
161 DepNodeColor::Red,
162 );
163 }
164
165 DepGraph {
166 data: Some(Arc::new(DepGraphData {
167 previous_work_products: prev_work_products,
168 dep_node_debug: Default::default(),
169 current,
170 previous: prev_graph,
171 colors,
172 debug_loaded_from_disk: Default::default(),
173 })),
174 virtual_dep_node_index: Arc::new(AtomicU32::new(0)),
175 }
176 }
177
178 pub fn new_disabled() -> DepGraph<D> {
179 DepGraph { data: None, virtual_dep_node_index: Arc::new(AtomicU32::new(0)) }
180 }
181
182 #[inline]
183 pub(crate) fn data(&self) -> Option<&DepGraphData<D>> {
184 self.data.as_deref()
185 }
186
187 /// Returns `true` if we are actually building the full dep-graph, and `false` otherwise.
188 #[inline]
189 pub fn is_fully_enabled(&self) -> bool {
190 self.data.is_some()
191 }
192
193 pub fn with_query(&self, f: impl Fn(&DepGraphQuery)) {
194 if let Some(data) = &self.data {
195 data.current.encoder.with_query(f)
196 }
197 }
198
199 pub fn assert_ignored(&self) {
200 if let Some(..) = self.data {
201 D::read_deps(|task_deps| {
202 assert_matches!(
203 task_deps,
204 TaskDepsRef::Ignore,
205 "expected no task dependency tracking"
206 );
207 })
208 }
209 }
210
211 pub fn with_ignore<OP, R>(&self, op: OP) -> R
212 where
213 OP: FnOnce() -> R,
214 {
215 D::with_deps(TaskDepsRef::Ignore, op)
216 }
217
218 /// Used to wrap the deserialization of a query result from disk,
219 /// This method enforces that no new `DepNodes` are created during
220 /// query result deserialization.
221 ///
222 /// Enforcing this makes the query dep graph simpler - all nodes
223 /// must be created during the query execution, and should be
224 /// created from inside the 'body' of a query (the implementation
225 /// provided by a particular compiler crate).
226 ///
227 /// Consider the case of three queries `A`, `B`, and `C`, where
228 /// `A` invokes `B` and `B` invokes `C`:
229 ///
230 /// `A -> B -> C`
231 ///
232 /// Suppose that decoding the result of query `B` required re-computing
233 /// the query `C`. If we did not create a fresh `TaskDeps` when
234 /// decoding `B`, we would still be using the `TaskDeps` for query `A`
235 /// (if we needed to re-execute `A`). This would cause us to create
236 /// a new edge `A -> C`. If this edge did not previously
237 /// exist in the `DepGraph`, then we could end up with a different
238 /// `DepGraph` at the end of compilation, even if there were no
239 /// meaningful changes to the overall program (e.g. a newline was added).
240 /// In addition, this edge might cause a subsequent compilation run
241 /// to try to force `C` before marking other necessary nodes green. If
242 /// `C` did not exist in the new compilation session, then we could
243 /// get an ICE. Normally, we would have tried (and failed) to mark
244 /// some other query green (e.g. `item_children`) which was used
245 /// to obtain `C`, which would prevent us from ever trying to force
246 /// a nonexistent `D`.
247 ///
248 /// It might be possible to enforce that all `DepNode`s read during
249 /// deserialization already exist in the previous `DepGraph`. In
250 /// the above example, we would invoke `D` during the deserialization
251 /// of `B`. Since we correctly create a new `TaskDeps` from the decoding
252 /// of `B`, this would result in an edge `B -> D`. If that edge already
253 /// existed (with the same `DepPathHash`es), then it should be correct
254 /// to allow the invocation of the query to proceed during deserialization
255 /// of a query result. We would merely assert that the dep-graph fragment
256 /// that would have been added by invoking `C` while decoding `B`
257 /// is equivalent to the dep-graph fragment that we already instantiated for B
258 /// (at the point where we successfully marked B as green).
259 ///
260 /// However, this would require additional complexity
261 /// in the query infrastructure, and is not currently needed by the
262 /// decoding of any query results. Should the need arise in the future,
263 /// we should consider extending the query system with this functionality.
264 pub fn with_query_deserialization<OP, R>(&self, op: OP) -> R
265 where
266 OP: FnOnce() -> R,
267 {
268 D::with_deps(TaskDepsRef::Forbid, op)
269 }
270
271 #[inline(always)]
272 pub fn with_task<Ctxt: HasDepContext<Deps = D>, A: Debug, R>(
273 &self,
274 key: DepNode,
275 cx: Ctxt,
276 arg: A,
277 task: fn(Ctxt, A) -> R,
278 hash_result: Option<fn(&mut StableHashingContext<'_>, &R) -> Fingerprint>,
279 ) -> (R, DepNodeIndex) {
280 match self.data() {
281 Some(data) => data.with_task(key, cx, arg, task, hash_result),
282 None => (task(cx, arg), self.next_virtual_depnode_index()),
283 }
284 }
285
286 pub fn with_anon_task<Tcx: DepContext<Deps = D>, OP, R>(
287 &self,
288 cx: Tcx,
289 dep_kind: DepKind,
290 op: OP,
291 ) -> (R, DepNodeIndex)
292 where
293 OP: FnOnce() -> R,
294 {
295 match self.data() {
296 Some(data) => {
297 let (result, index) = data.with_anon_task_inner(cx, dep_kind, op);
298 self.read_index(index);
299 (result, index)
300 }
301 None => (op(), self.next_virtual_depnode_index()),
302 }
303 }
304}
305
306impl<D: Deps> DepGraphData<D> {
307 /// Starts a new dep-graph task. Dep-graph tasks are specified
308 /// using a free function (`task`) and **not** a closure -- this
309 /// is intentional because we want to exercise tight control over
310 /// what state they have access to. In particular, we want to
311 /// prevent implicit 'leaks' of tracked state into the task (which
312 /// could then be read without generating correct edges in the
313 /// dep-graph -- see the [rustc dev guide] for more details on
314 /// the dep-graph). To this end, the task function gets exactly two
315 /// pieces of state: the context `cx` and an argument `arg`. Both
316 /// of these bits of state must be of some type that implements
317 /// `DepGraphSafe` and hence does not leak.
318 ///
319 /// The choice of two arguments is not fundamental. One argument
320 /// would work just as well, since multiple values can be
321 /// collected using tuples. However, using two arguments works out
322 /// to be quite convenient, since it is common to need a context
323 /// (`cx`) and some argument (e.g., a `DefId` identifying what
324 /// item to process).
325 ///
326 /// For cases where you need some other number of arguments:
327 ///
328 /// - If you only need one argument, just use `()` for the `arg`
329 /// parameter.
330 /// - If you need 3+ arguments, use a tuple for the
331 /// `arg` parameter.
332 ///
333 /// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/queries/incremental-compilation.html
334 #[inline(always)]
335 pub(crate) fn with_task<Ctxt: HasDepContext<Deps = D>, A: Debug, R>(
336 &self,
337 key: DepNode,
338 cx: Ctxt,
339 arg: A,
340 task: fn(Ctxt, A) -> R,
341 hash_result: Option<fn(&mut StableHashingContext<'_>, &R) -> Fingerprint>,
342 ) -> (R, DepNodeIndex) {
343 // If the following assertion triggers, it can have two reasons:
344 // 1. Something is wrong with DepNode creation, either here or
345 // in `DepGraph::try_mark_green()`.
346 // 2. Two distinct query keys get mapped to the same `DepNode`
347 // (see for example #48923).
348 self.assert_dep_node_not_yet_allocated_in_current_session(&key, || {
349 format!(
350 "forcing query with already existing `DepNode`\n\
351 - query-key: {arg:?}\n\
352 - dep-node: {key:?}"
353 )
354 });
355
356 let with_deps = |task_deps| D::with_deps(task_deps, || task(cx, arg));
357 let (result, edges) = if cx.dep_context().is_eval_always(key.kind) {
358 (with_deps(TaskDepsRef::EvalAlways), EdgesVec::new())
359 } else {
360 let task_deps = Lock::new(TaskDeps {
361 #[cfg(debug_assertions)]
362 node: Some(key),
363 reads: EdgesVec::new(),
364 read_set: Default::default(),
365 phantom_data: PhantomData,
366 });
367 (with_deps(TaskDepsRef::Allow(&task_deps)), task_deps.into_inner().reads)
368 };
369
370 let dcx = cx.dep_context();
371 let dep_node_index = self.hash_result_and_alloc_node(dcx, key, edges, &result, hash_result);
372
373 (result, dep_node_index)
374 }
375
376 /// Executes something within an "anonymous" task, that is, a task the
377 /// `DepNode` of which is determined by the list of inputs it read from.
378 ///
379 /// NOTE: this does not actually count as a read of the DepNode here.
380 /// Using the result of this task without reading the DepNode will result
381 /// in untracked dependencies which may lead to ICEs as nodes are
382 /// incorrectly marked green.
383 ///
384 /// FIXME: This could perhaps return a `WithDepNode` to ensure that the
385 /// user of this function actually performs the read; we'll have to see
386 /// how to make that work with `anon` in `execute_job_incr`, though.
387 pub(crate) fn with_anon_task_inner<Tcx: DepContext<Deps = D>, OP, R>(
388 &self,
389 cx: Tcx,
390 dep_kind: DepKind,
391 op: OP,
392 ) -> (R, DepNodeIndex)
393 where
394 OP: FnOnce() -> R,
395 {
396 debug_assert!(!cx.is_eval_always(dep_kind));
397
398 let task_deps = Lock::new(TaskDeps::default());
399 let result = D::with_deps(TaskDepsRef::Allow(&task_deps), op);
400 let task_deps = task_deps.into_inner();
401 let task_deps = task_deps.reads;
402
403 let dep_node_index = match task_deps.len() {
404 0 => {
405 // Because the dep-node id of anon nodes is computed from the sets of its
406 // dependencies we already know what the ID of this dependency-less node is
407 // going to be (i.e. equal to the precomputed
408 // `SINGLETON_DEPENDENCYLESS_ANON_NODE`). As a consequence we can skip creating
409 // a `StableHasher` and sending the node through interning.
410 DepNodeIndex::SINGLETON_ZERO_DEPS_ANON_NODE
411 }
412 1 => {
413 // When there is only one dependency, don't bother creating a node.
414 task_deps[0]
415 }
416 _ => {
417 // The dep node indices are hashed here instead of hashing the dep nodes of the
418 // dependencies. These indices may refer to different nodes per session, but this isn't
419 // a problem here because we that ensure the final dep node hash is per session only by
420 // combining it with the per session random number `anon_id_seed`. This hash only need
421 // to map the dependencies to a single value on a per session basis.
422 let mut hasher = StableHasher::new();
423 task_deps.hash(&mut hasher);
424
425 let target_dep_node = DepNode {
426 kind: dep_kind,
427 // Fingerprint::combine() is faster than sending Fingerprint
428 // through the StableHasher (at least as long as StableHasher
429 // is so slow).
430 hash: self.current.anon_id_seed.combine(hasher.finish()).into(),
431 };
432
433 // The DepNodes generated by the process above are not unique. 2 queries could
434 // have exactly the same dependencies. However, deserialization does not handle
435 // duplicated nodes, so we do the deduplication here directly.
436 //
437 // As anonymous nodes are a small quantity compared to the full dep-graph, the
438 // memory impact of this `anon_node_to_index` map remains tolerable, and helps
439 // us avoid useless growth of the graph with almost-equivalent nodes.
440 self.current.anon_node_to_index.get_or_insert_with(target_dep_node, || {
441 self.current.alloc_new_node(target_dep_node, task_deps, Fingerprint::ZERO)
442 })
443 }
444 };
445
446 (result, dep_node_index)
447 }
448
449 /// Intern the new `DepNode` with the dependencies up-to-now.
450 fn hash_result_and_alloc_node<Ctxt: DepContext<Deps = D>, R>(
451 &self,
452 cx: &Ctxt,
453 node: DepNode,
454 edges: EdgesVec,
455 result: &R,
456 hash_result: Option<fn(&mut StableHashingContext<'_>, &R) -> Fingerprint>,
457 ) -> DepNodeIndex {
458 let hashing_timer = cx.profiler().incr_result_hashing();
459 let current_fingerprint = hash_result.map(|hash_result| {
460 cx.with_stable_hashing_context(|mut hcx| hash_result(&mut hcx, result))
461 });
462 let dep_node_index = self.alloc_and_color_node(node, edges, current_fingerprint);
463 hashing_timer.finish_with_query_invocation_id(dep_node_index.into());
464 dep_node_index
465 }
466}
467
468impl<D: Deps> DepGraph<D> {
469 #[inline]
470 pub fn read_index(&self, dep_node_index: DepNodeIndex) {
471 if let Some(ref data) = self.data {
472 D::read_deps(|task_deps| {
473 let mut task_deps = match task_deps {
474 TaskDepsRef::Allow(deps) => deps.lock(),
475 TaskDepsRef::EvalAlways => {
476 // We don't need to record dependencies of eval_always
477 // queries. They are re-evaluated unconditionally anyway.
478 return;
479 }
480 TaskDepsRef::Ignore => return,
481 TaskDepsRef::Forbid => {
482 // Reading is forbidden in this context. ICE with a useful error message.
483 panic_on_forbidden_read(data, dep_node_index)
484 }
485 };
486 let task_deps = &mut *task_deps;
487
488 if cfg!(debug_assertions) {
489 data.current.total_read_count.fetch_add(1, Ordering::Relaxed);
490 }
491
492 // As long as we only have a low number of reads we can avoid doing a hash
493 // insert and potentially allocating/reallocating the hashmap
494 let new_read = if task_deps.reads.len() < EdgesVec::INLINE_CAPACITY {
495 task_deps.reads.iter().all(|other| *other != dep_node_index)
496 } else {
497 task_deps.read_set.insert(dep_node_index)
498 };
499 if new_read {
500 task_deps.reads.push(dep_node_index);
501 if task_deps.reads.len() == EdgesVec::INLINE_CAPACITY {
502 // Fill `read_set` with what we have so far so we can use the hashset
503 // next time
504 task_deps.read_set.extend(task_deps.reads.iter().copied());
505 }
506
507 #[cfg(debug_assertions)]
508 {
509 if let Some(target) = task_deps.node {
510 if let Some(ref forbidden_edge) = data.current.forbidden_edge {
511 let src = forbidden_edge.index_to_node.lock()[&dep_node_index];
512 if forbidden_edge.test(&src, &target) {
513 panic!("forbidden edge {:?} -> {:?} created", src, target)
514 }
515 }
516 }
517 }
518 } else if cfg!(debug_assertions) {
519 data.current.total_duplicate_read_count.fetch_add(1, Ordering::Relaxed);
520 }
521 })
522 }
523 }
524
525 /// This encodes a diagnostic by creating a node with an unique index and assoicating
526 /// `diagnostic` with it, for use in the next session.
527 #[inline]
528 pub fn record_diagnostic<Qcx: QueryContext>(&self, qcx: Qcx, diagnostic: &DiagInner) {
529 if let Some(ref data) = self.data {
530 D::read_deps(|task_deps| match task_deps {
531 TaskDepsRef::EvalAlways | TaskDepsRef::Ignore => return,
532 TaskDepsRef::Forbid | TaskDepsRef::Allow(..) => {
533 self.read_index(data.encode_diagnostic(qcx, diagnostic));
534 }
535 })
536 }
537 }
538 /// This forces a diagnostic node green by running its side effect. `prev_index` would
539 /// refer to a node created used `encode_diagnostic` in the previous session.
540 #[inline]
541 pub fn force_diagnostic_node<Qcx: QueryContext>(
542 &self,
543 qcx: Qcx,
544 prev_index: SerializedDepNodeIndex,
545 ) {
546 if let Some(ref data) = self.data {
547 data.force_diagnostic_node(qcx, prev_index);
548 }
549 }
550
551 /// Create a node when we force-feed a value into the query cache.
552 /// This is used to remove cycles during type-checking const generic parameters.
553 ///
554 /// As usual in the query system, we consider the current state of the calling query
555 /// only depends on the list of dependencies up to now. As a consequence, the value
556 /// that this query gives us can only depend on those dependencies too. Therefore,
557 /// it is sound to use the current dependency set for the created node.
558 ///
559 /// During replay, the order of the nodes is relevant in the dependency graph.
560 /// So the unchanged replay will mark the caller query before trying to mark this one.
561 /// If there is a change to report, the caller query will be re-executed before this one.
562 ///
563 /// FIXME: If the code is changed enough for this node to be marked before requiring the
564 /// caller's node, we suppose that those changes will be enough to mark this node red and
565 /// force a recomputation using the "normal" way.
566 pub fn with_feed_task<Ctxt: DepContext<Deps = D>, R: Debug>(
567 &self,
568 node: DepNode,
569 cx: Ctxt,
570 result: &R,
571 hash_result: Option<fn(&mut StableHashingContext<'_>, &R) -> Fingerprint>,
572 ) -> DepNodeIndex {
573 if let Some(data) = self.data.as_ref() {
574 // The caller query has more dependencies than the node we are creating. We may
575 // encounter a case where this created node is marked as green, but the caller query is
576 // subsequently marked as red or recomputed. In this case, we will end up feeding a
577 // value to an existing node.
578 //
579 // For sanity, we still check that the loaded stable hash and the new one match.
580 if let Some(prev_index) = data.previous.node_to_index_opt(&node) {
581 let dep_node_index = data.colors.current(prev_index);
582 if let Some(dep_node_index) = dep_node_index {
583 crate::query::incremental_verify_ich(
584 cx,
585 data,
586 result,
587 prev_index,
588 hash_result,
589 |value| format!("{value:?}"),
590 );
591
592 #[cfg(debug_assertions)]
593 if hash_result.is_some() {
594 data.current.record_edge(
595 dep_node_index,
596 node,
597 data.prev_fingerprint_of(prev_index),
598 );
599 }
600
601 return dep_node_index;
602 }
603 }
604
605 let mut edges = EdgesVec::new();
606 D::read_deps(|task_deps| match task_deps {
607 TaskDepsRef::Allow(deps) => edges.extend(deps.lock().reads.iter().copied()),
608 TaskDepsRef::EvalAlways => {
609 edges.push(DepNodeIndex::FOREVER_RED_NODE);
610 }
611 TaskDepsRef::Ignore => {}
612 TaskDepsRef::Forbid => {
613 panic!("Cannot summarize when dependencies are not recorded.")
614 }
615 });
616
617 data.hash_result_and_alloc_node(&cx, node, edges, result, hash_result)
618 } else {
619 // Incremental compilation is turned off. We just execute the task
620 // without tracking. We still provide a dep-node index that uniquely
621 // identifies the task so that we have a cheap way of referring to
622 // the query for self-profiling.
623 self.next_virtual_depnode_index()
624 }
625 }
626}
627
628impl<D: Deps> DepGraphData<D> {
629 fn assert_dep_node_not_yet_allocated_in_current_session<S: std::fmt::Display>(
630 &self,
631 dep_node: &DepNode,
632 msg: impl FnOnce() -> S,
633 ) {
634 if let Some(prev_index) = self.previous.node_to_index_opt(dep_node) {
635 let current = self.colors.get(prev_index);
636 assert!(current.is_none(), "{}", msg())
637 } else if let Some(nodes_in_current_session) = &self.current.nodes_in_current_session {
638 outline(|| {
639 let seen = nodes_in_current_session.lock().contains_key(dep_node);
640 assert!(!seen, "{}", msg());
641 });
642 }
643 }
644
645 fn node_color(&self, dep_node: &DepNode) -> Option<DepNodeColor> {
646 if let Some(prev_index) = self.previous.node_to_index_opt(dep_node) {
647 self.colors.get(prev_index)
648 } else {
649 // This is a node that did not exist in the previous compilation session.
650 None
651 }
652 }
653
654 /// Returns true if the given node has been marked as green during the
655 /// current compilation session. Used in various assertions
656 #[inline]
657 pub(crate) fn is_index_green(&self, prev_index: SerializedDepNodeIndex) -> bool {
658 self.colors.get(prev_index).is_some_and(|c| c.is_green())
659 }
660
661 #[inline]
662 pub(crate) fn prev_fingerprint_of(&self, prev_index: SerializedDepNodeIndex) -> Fingerprint {
663 self.previous.fingerprint_by_index(prev_index)
664 }
665
666 #[inline]
667 pub(crate) fn prev_node_of(&self, prev_index: SerializedDepNodeIndex) -> DepNode {
668 self.previous.index_to_node(prev_index)
669 }
670
671 pub(crate) fn mark_debug_loaded_from_disk(&self, dep_node: DepNode) {
672 self.debug_loaded_from_disk.lock().insert(dep_node);
673 }
674
675 /// This encodes a diagnostic by creating a node with an unique index and assoicating
676 /// `diagnostic` with it, for use in the next session.
677 #[inline]
678 fn encode_diagnostic<Qcx: QueryContext>(
679 &self,
680 qcx: Qcx,
681 diagnostic: &DiagInner,
682 ) -> DepNodeIndex {
683 // Use `send_new` so we get an unique index, even though the dep node is not.
684 let dep_node_index = self.current.encoder.send_new(
685 DepNode {
686 kind: D::DEP_KIND_SIDE_EFFECT,
687 hash: PackedFingerprint::from(Fingerprint::ZERO),
688 },
689 Fingerprint::ZERO,
690 // We want the side effect node to always be red so it will be forced and emit the
691 // diagnostic.
692 std::iter::once(DepNodeIndex::FOREVER_RED_NODE).collect(),
693 );
694 let side_effect = QuerySideEffect::Diagnostic(diagnostic.clone());
695 qcx.store_side_effect(dep_node_index, side_effect);
696 dep_node_index
697 }
698
699 /// This forces a diagnostic node green by running its side effect. `prev_index` would
700 /// refer to a node created used `encode_diagnostic` in the previous session.
701 #[inline]
702 fn force_diagnostic_node<Qcx: QueryContext>(
703 &self,
704 qcx: Qcx,
705 prev_index: SerializedDepNodeIndex,
706 ) {
707 D::with_deps(TaskDepsRef::Ignore, || {
708 let side_effect = qcx.load_side_effect(prev_index).unwrap();
709
710 match &side_effect {
711 QuerySideEffect::Diagnostic(diagnostic) => {
712 qcx.dep_context().sess().dcx().emit_diagnostic(diagnostic.clone());
713 }
714 }
715
716 // Use `send_and_color` as `promote_node_and_deps_to_current` expects all
717 // green dependencies. `send_and_color` will also prevent multiple nodes
718 // being encoded for concurrent calls.
719 let dep_node_index = self.current.encoder.send_and_color(
720 prev_index,
721 &self.colors,
722 DepNode {
723 kind: D::DEP_KIND_SIDE_EFFECT,
724 hash: PackedFingerprint::from(Fingerprint::ZERO),
725 },
726 Fingerprint::ZERO,
727 std::iter::once(DepNodeIndex::FOREVER_RED_NODE).collect(),
728 true,
729 );
730 // This will just overwrite the same value for concurrent calls.
731 qcx.store_side_effect(dep_node_index, side_effect);
732 })
733 }
734
735 fn alloc_and_color_node(
736 &self,
737 key: DepNode,
738 edges: EdgesVec,
739 fingerprint: Option<Fingerprint>,
740 ) -> DepNodeIndex {
741 if let Some(prev_index) = self.previous.node_to_index_opt(&key) {
742 // Determine the color and index of the new `DepNode`.
743 let is_green = if let Some(fingerprint) = fingerprint {
744 if fingerprint == self.previous.fingerprint_by_index(prev_index) {
745 // This is a green node: it existed in the previous compilation,
746 // its query was re-executed, and it has the same result as before.
747 true
748 } else {
749 // This is a red node: it existed in the previous compilation, its query
750 // was re-executed, but it has a different result from before.
751 false
752 }
753 } else {
754 // This is a red node, effectively: it existed in the previous compilation
755 // session, its query was re-executed, but it doesn't compute a result hash
756 // (i.e. it represents a `no_hash` query), so we have no way of determining
757 // whether or not the result was the same as before.
758 false
759 };
760
761 let fingerprint = fingerprint.unwrap_or(Fingerprint::ZERO);
762
763 let dep_node_index = self.current.encoder.send_and_color(
764 prev_index,
765 &self.colors,
766 key,
767 fingerprint,
768 edges,
769 is_green,
770 );
771
772 self.current.record_node(dep_node_index, key, fingerprint);
773
774 dep_node_index
775 } else {
776 self.current.alloc_new_node(key, edges, fingerprint.unwrap_or(Fingerprint::ZERO))
777 }
778 }
779
780 fn promote_node_and_deps_to_current(&self, prev_index: SerializedDepNodeIndex) -> DepNodeIndex {
781 self.current.debug_assert_not_in_new_nodes(&self.previous, prev_index);
782
783 let dep_node_index = self.current.encoder.send_promoted(prev_index, &self.colors);
784
785 #[cfg(debug_assertions)]
786 self.current.record_edge(
787 dep_node_index,
788 self.previous.index_to_node(prev_index),
789 self.previous.fingerprint_by_index(prev_index),
790 );
791
792 dep_node_index
793 }
794}
795
796impl<D: Deps> DepGraph<D> {
797 /// Checks whether a previous work product exists for `v` and, if
798 /// so, return the path that leads to it. Used to skip doing work.
799 pub fn previous_work_product(&self, v: &WorkProductId) -> Option<WorkProduct> {
800 self.data.as_ref().and_then(|data| data.previous_work_products.get(v).cloned())
801 }
802
803 /// Access the map of work-products created during the cached run. Only
804 /// used during saving of the dep-graph.
805 pub fn previous_work_products(&self) -> &WorkProductMap {
806 &self.data.as_ref().unwrap().previous_work_products
807 }
808
809 pub fn debug_was_loaded_from_disk(&self, dep_node: DepNode) -> bool {
810 self.data.as_ref().unwrap().debug_loaded_from_disk.lock().contains(&dep_node)
811 }
812
813 #[cfg(debug_assertions)]
814 #[inline(always)]
815 pub(crate) fn register_dep_node_debug_str<F>(&self, dep_node: DepNode, debug_str_gen: F)
816 where
817 F: FnOnce() -> String,
818 {
819 let dep_node_debug = &self.data.as_ref().unwrap().dep_node_debug;
820
821 if dep_node_debug.borrow().contains_key(&dep_node) {
822 return;
823 }
824 let debug_str = self.with_ignore(debug_str_gen);
825 dep_node_debug.borrow_mut().insert(dep_node, debug_str);
826 }
827
828 pub fn dep_node_debug_str(&self, dep_node: DepNode) -> Option<String> {
829 self.data.as_ref()?.dep_node_debug.borrow().get(&dep_node).cloned()
830 }
831
832 fn node_color(&self, dep_node: &DepNode) -> Option<DepNodeColor> {
833 if let Some(ref data) = self.data {
834 return data.node_color(dep_node);
835 }
836
837 None
838 }
839
840 pub fn try_mark_green<Qcx: QueryContext<Deps = D>>(
841 &self,
842 qcx: Qcx,
843 dep_node: &DepNode,
844 ) -> Option<(SerializedDepNodeIndex, DepNodeIndex)> {
845 self.data().and_then(|data| data.try_mark_green(qcx, dep_node))
846 }
847}
848
849impl<D: Deps> DepGraphData<D> {
850 /// Try to mark a node index for the node dep_node.
851 ///
852 /// A node will have an index, when it's already been marked green, or when we can mark it
853 /// green. This function will mark the current task as a reader of the specified node, when
854 /// a node index can be found for that node.
855 pub(crate) fn try_mark_green<Qcx: QueryContext<Deps = D>>(
856 &self,
857 qcx: Qcx,
858 dep_node: &DepNode,
859 ) -> Option<(SerializedDepNodeIndex, DepNodeIndex)> {
860 debug_assert!(!qcx.dep_context().is_eval_always(dep_node.kind));
861
862 // Return None if the dep node didn't exist in the previous session
863 let prev_index = self.previous.node_to_index_opt(dep_node)?;
864
865 match self.colors.get(prev_index) {
866 Some(DepNodeColor::Green(dep_node_index)) => Some((prev_index, dep_node_index)),
867 Some(DepNodeColor::Red) => None,
868 None => {
869 // This DepNode and the corresponding query invocation existed
870 // in the previous compilation session too, so we can try to
871 // mark it as green by recursively marking all of its
872 // dependencies green.
873 self.try_mark_previous_green(qcx, prev_index, dep_node, None)
874 .map(|dep_node_index| (prev_index, dep_node_index))
875 }
876 }
877 }
878
879 #[instrument(skip(self, qcx, parent_dep_node_index, frame), level = "debug")]
880 fn try_mark_parent_green<Qcx: QueryContext<Deps = D>>(
881 &self,
882 qcx: Qcx,
883 parent_dep_node_index: SerializedDepNodeIndex,
884 frame: Option<&MarkFrame<'_>>,
885 ) -> Option<()> {
886 let dep_dep_node_color = self.colors.get(parent_dep_node_index);
887 let dep_dep_node = &self.previous.index_to_node(parent_dep_node_index);
888
889 match dep_dep_node_color {
890 Some(DepNodeColor::Green(_)) => {
891 // This dependency has been marked as green before, we are
892 // still fine and can continue with checking the other
893 // dependencies.
894 debug!("dependency {dep_dep_node:?} was immediately green");
895 return Some(());
896 }
897 Some(DepNodeColor::Red) => {
898 // We found a dependency the value of which has changed
899 // compared to the previous compilation session. We cannot
900 // mark the DepNode as green and also don't need to bother
901 // with checking any of the other dependencies.
902 debug!("dependency {dep_dep_node:?} was immediately red");
903 return None;
904 }
905 None => {}
906 }
907
908 // We don't know the state of this dependency. If it isn't
909 // an eval_always node, let's try to mark it green recursively.
910 if !qcx.dep_context().is_eval_always(dep_dep_node.kind) {
911 debug!(
912 "state of dependency {:?} ({}) is unknown, trying to mark it green",
913 dep_dep_node, dep_dep_node.hash,
914 );
915
916 let node_index =
917 self.try_mark_previous_green(qcx, parent_dep_node_index, dep_dep_node, frame);
918
919 if node_index.is_some() {
920 debug!("managed to MARK dependency {dep_dep_node:?} as green");
921 return Some(());
922 }
923 }
924
925 // We failed to mark it green, so we try to force the query.
926 debug!("trying to force dependency {dep_dep_node:?}");
927 if !qcx.dep_context().try_force_from_dep_node(*dep_dep_node, parent_dep_node_index, frame) {
928 // The DepNode could not be forced.
929 debug!("dependency {dep_dep_node:?} could not be forced");
930 return None;
931 }
932
933 let dep_dep_node_color = self.colors.get(parent_dep_node_index);
934
935 match dep_dep_node_color {
936 Some(DepNodeColor::Green(_)) => {
937 debug!("managed to FORCE dependency {dep_dep_node:?} to green");
938 return Some(());
939 }
940 Some(DepNodeColor::Red) => {
941 debug!("dependency {dep_dep_node:?} was red after forcing");
942 return None;
943 }
944 None => {}
945 }
946
947 if let None = qcx.dep_context().sess().dcx().has_errors_or_delayed_bugs() {
948 panic!("try_mark_previous_green() - Forcing the DepNode should have set its color")
949 }
950
951 // If the query we just forced has resulted in
952 // some kind of compilation error, we cannot rely on
953 // the dep-node color having been properly updated.
954 // This means that the query system has reached an
955 // invalid state. We let the compiler continue (by
956 // returning `None`) so it can emit error messages
957 // and wind down, but rely on the fact that this
958 // invalid state will not be persisted to the
959 // incremental compilation cache because of
960 // compilation errors being present.
961 debug!("dependency {dep_dep_node:?} resulted in compilation error");
962 return None;
963 }
964
965 /// Try to mark a dep-node which existed in the previous compilation session as green.
966 #[instrument(skip(self, qcx, prev_dep_node_index, frame), level = "debug")]
967 fn try_mark_previous_green<Qcx: QueryContext<Deps = D>>(
968 &self,
969 qcx: Qcx,
970 prev_dep_node_index: SerializedDepNodeIndex,
971 dep_node: &DepNode,
972 frame: Option<&MarkFrame<'_>>,
973 ) -> Option<DepNodeIndex> {
974 let frame = MarkFrame { index: prev_dep_node_index, parent: frame };
975
976 // We never try to mark eval_always nodes as green
977 debug_assert!(!qcx.dep_context().is_eval_always(dep_node.kind));
978
979 debug_assert_eq!(self.previous.index_to_node(prev_dep_node_index), *dep_node);
980
981 let prev_deps = self.previous.edge_targets_from(prev_dep_node_index);
982
983 for dep_dep_node_index in prev_deps {
984 self.try_mark_parent_green(qcx, dep_dep_node_index, Some(&frame))?;
985 }
986
987 // If we got here without hitting a `return` that means that all
988 // dependencies of this DepNode could be marked as green. Therefore we
989 // can also mark this DepNode as green.
990
991 // There may be multiple threads trying to mark the same dep node green concurrently
992
993 // We allocating an entry for the node in the current dependency graph and
994 // adding all the appropriate edges imported from the previous graph
995 let dep_node_index = self.promote_node_and_deps_to_current(prev_dep_node_index);
996
997 // ... and finally storing a "Green" entry in the color map.
998 // Multiple threads can all write the same color here
999
1000 debug!("successfully marked {dep_node:?} as green");
1001 Some(dep_node_index)
1002 }
1003}
1004
1005impl<D: Deps> DepGraph<D> {
1006 /// Returns true if the given node has been marked as red during the
1007 /// current compilation session. Used in various assertions
1008 pub fn is_red(&self, dep_node: &DepNode) -> bool {
1009 matches!(self.node_color(dep_node), Some(DepNodeColor::Red))
1010 }
1011
1012 /// Returns true if the given node has been marked as green during the
1013 /// current compilation session. Used in various assertions
1014 pub fn is_green(&self, dep_node: &DepNode) -> bool {
1015 self.node_color(dep_node).is_some_and(|c| c.is_green())
1016 }
1017
1018 pub fn assert_dep_node_not_yet_allocated_in_current_session<S: std::fmt::Display>(
1019 &self,
1020 dep_node: &DepNode,
1021 msg: impl FnOnce() -> S,
1022 ) {
1023 if let Some(data) = &self.data {
1024 data.assert_dep_node_not_yet_allocated_in_current_session(dep_node, msg)
1025 }
1026 }
1027
1028 /// This method loads all on-disk cacheable query results into memory, so
1029 /// they can be written out to the new cache file again. Most query results
1030 /// will already be in memory but in the case where we marked something as
1031 /// green but then did not need the value, that value will never have been
1032 /// loaded from disk.
1033 ///
1034 /// This method will only load queries that will end up in the disk cache.
1035 /// Other queries will not be executed.
1036 pub fn exec_cache_promotions<Tcx: DepContext>(&self, tcx: Tcx) {
1037 let _prof_timer = tcx.profiler().generic_activity("incr_comp_query_cache_promotion");
1038
1039 let data = self.data.as_ref().unwrap();
1040 for prev_index in data.colors.values.indices() {
1041 match data.colors.get(prev_index) {
1042 Some(DepNodeColor::Green(_)) => {
1043 let dep_node = data.previous.index_to_node(prev_index);
1044 tcx.try_load_from_on_disk_cache(dep_node);
1045 }
1046 None | Some(DepNodeColor::Red) => {
1047 // We can skip red nodes because a node can only be marked
1048 // as red if the query result was recomputed and thus is
1049 // already in memory.
1050 }
1051 }
1052 }
1053 }
1054
1055 pub fn print_incremental_info(&self) {
1056 if let Some(data) = &self.data {
1057 data.current.encoder.print_incremental_info(
1058 data.current.total_read_count.load(Ordering::Relaxed),
1059 data.current.total_duplicate_read_count.load(Ordering::Relaxed),
1060 )
1061 }
1062 }
1063
1064 pub fn finish_encoding(&self) -> FileEncodeResult {
1065 if let Some(data) = &self.data { data.current.encoder.finish() } else { Ok(0) }
1066 }
1067
1068 pub(crate) fn next_virtual_depnode_index(&self) -> DepNodeIndex {
1069 debug_assert!(self.data.is_none());
1070 let index = self.virtual_dep_node_index.fetch_add(1, Ordering::Relaxed);
1071 DepNodeIndex::from_u32(index)
1072 }
1073}
1074
1075/// A "work product" is an intermediate result that we save into the
1076/// incremental directory for later re-use. The primary example are
1077/// the object files that we save for each partition at code
1078/// generation time.
1079///
1080/// Each work product is associated with a dep-node, representing the
1081/// process that produced the work-product. If that dep-node is found
1082/// to be dirty when we load up, then we will delete the work-product
1083/// at load time. If the work-product is found to be clean, then we
1084/// will keep a record in the `previous_work_products` list.
1085///
1086/// In addition, work products have an associated hash. This hash is
1087/// an extra hash that can be used to decide if the work-product from
1088/// a previous compilation can be re-used (in addition to the dirty
1089/// edges check).
1090///
1091/// As the primary example, consider the object files we generate for
1092/// each partition. In the first run, we create partitions based on
1093/// the symbols that need to be compiled. For each partition P, we
1094/// hash the symbols in P and create a `WorkProduct` record associated
1095/// with `DepNode::CodegenUnit(P)`; the hash is the set of symbols
1096/// in P.
1097///
1098/// The next time we compile, if the `DepNode::CodegenUnit(P)` is
1099/// judged to be clean (which means none of the things we read to
1100/// generate the partition were found to be dirty), it will be loaded
1101/// into previous work products. We will then regenerate the set of
1102/// symbols in the partition P and hash them (note that new symbols
1103/// may be added -- for example, new monomorphizations -- even if
1104/// nothing in P changed!). We will compare that hash against the
1105/// previous hash. If it matches up, we can reuse the object file.
1106#[derive(Clone, Debug, Encodable, Decodable)]
1107pub struct WorkProduct {
1108 pub cgu_name: String,
1109 /// Saved files associated with this CGU. In each key/value pair, the value is the path to the
1110 /// saved file and the key is some identifier for the type of file being saved.
1111 ///
1112 /// By convention, file extensions are currently used as identifiers, i.e. the key "o" maps to
1113 /// the object file's path, and "dwo" to the dwarf object file's path.
1114 pub saved_files: UnordMap<String, String>,
1115}
1116
1117pub type WorkProductMap = UnordMap<WorkProductId, WorkProduct>;
1118
1119// Index type for `DepNodeData`'s edges.
1120rustc_index::newtype_index! {
1121 struct EdgeIndex {}
1122}
1123
1124/// `CurrentDepGraph` stores the dependency graph for the current session. It
1125/// will be populated as we run queries or tasks. We never remove nodes from the
1126/// graph: they are only added.
1127///
1128/// The nodes in it are identified by a `DepNodeIndex`. We avoid keeping the nodes
1129/// in memory. This is important, because these graph structures are some of the
1130/// largest in the compiler.
1131///
1132/// For this reason, we avoid storing `DepNode`s more than once as map
1133/// keys. The `anon_node_to_index` map only contains nodes of anonymous queries not in the previous
1134/// graph, and we map nodes in the previous graph to indices via a two-step
1135/// mapping. `SerializedDepGraph` maps from `DepNode` to `SerializedDepNodeIndex`,
1136/// and the `prev_index_to_index` vector (which is more compact and faster than
1137/// using a map) maps from `SerializedDepNodeIndex` to `DepNodeIndex`.
1138///
1139/// This struct uses three locks internally. The `data`, `anon_node_to_index`,
1140/// and `prev_index_to_index` fields are locked separately. Operations that take
1141/// a `DepNodeIndex` typically just access the `data` field.
1142///
1143/// We only need to manipulate at most two locks simultaneously:
1144/// `anon_node_to_index` and `data`, or `prev_index_to_index` and `data`. When
1145/// manipulating both, we acquire `anon_node_to_index` or `prev_index_to_index`
1146/// first, and `data` second.
1147pub(super) struct CurrentDepGraph<D: Deps> {
1148 encoder: GraphEncoder<D>,
1149 anon_node_to_index: ShardedHashMap<DepNode, DepNodeIndex>,
1150
1151 /// This is used to verify that fingerprints do not change between the creation of a node
1152 /// and its recomputation.
1153 #[cfg(debug_assertions)]
1154 fingerprints: Lock<IndexVec<DepNodeIndex, Option<Fingerprint>>>,
1155
1156 /// Used to trap when a specific edge is added to the graph.
1157 /// This is used for debug purposes and is only active with `debug_assertions`.
1158 #[cfg(debug_assertions)]
1159 forbidden_edge: Option<EdgeFilter>,
1160
1161 /// Used to verify the absence of hash collisions among DepNodes.
1162 /// This field is only `Some` if the `-Z incremental_verify_ich` option is present
1163 /// or if `debug_assertions` are enabled.
1164 ///
1165 /// The map contains all DepNodes that have been allocated in the current session so far.
1166 nodes_in_current_session: Option<Lock<FxHashMap<DepNode, DepNodeIndex>>>,
1167
1168 /// Anonymous `DepNode`s are nodes whose IDs we compute from the list of
1169 /// their edges. This has the beneficial side-effect that multiple anonymous
1170 /// nodes can be coalesced into one without changing the semantics of the
1171 /// dependency graph. However, the merging of nodes can lead to a subtle
1172 /// problem during red-green marking: The color of an anonymous node from
1173 /// the current session might "shadow" the color of the node with the same
1174 /// ID from the previous session. In order to side-step this problem, we make
1175 /// sure that anonymous `NodeId`s allocated in different sessions don't overlap.
1176 /// This is implemented by mixing a session-key into the ID fingerprint of
1177 /// each anon node. The session-key is a hash of the number of previous sessions.
1178 anon_id_seed: Fingerprint,
1179
1180 /// These are simple counters that are for profiling and
1181 /// debugging and only active with `debug_assertions`.
1182 total_read_count: AtomicU64,
1183 total_duplicate_read_count: AtomicU64,
1184}
1185
1186impl<D: Deps> CurrentDepGraph<D> {
1187 fn new(
1188 session: &Session,
1189 prev_graph_node_count: usize,
1190 encoder: FileEncoder,
1191 record_graph: bool,
1192 record_stats: bool,
1193 previous: Arc<SerializedDepGraph>,
1194 ) -> Self {
1195 let mut stable_hasher = StableHasher::new();
1196 previous.session_count().hash(&mut stable_hasher);
1197 let anon_id_seed = stable_hasher.finish();
1198
1199 #[cfg(debug_assertions)]
1200 let forbidden_edge = match env::var("RUST_FORBID_DEP_GRAPH_EDGE") {
1201 Ok(s) => match EdgeFilter::new(&s) {
1202 Ok(f) => Some(f),
1203 Err(err) => panic!("RUST_FORBID_DEP_GRAPH_EDGE invalid: {}", err),
1204 },
1205 Err(_) => None,
1206 };
1207
1208 let new_node_count_estimate = 102 * prev_graph_node_count / 100 + 200;
1209
1210 let new_node_dbg =
1211 session.opts.unstable_opts.incremental_verify_ich || cfg!(debug_assertions);
1212
1213 CurrentDepGraph {
1214 encoder: GraphEncoder::new(
1215 encoder,
1216 prev_graph_node_count,
1217 record_graph,
1218 record_stats,
1219 &session.prof,
1220 previous,
1221 ),
1222 anon_node_to_index: ShardedHashMap::with_capacity(
1223 // FIXME: The count estimate is off as anon nodes are only a portion of the nodes.
1224 new_node_count_estimate / sharded::shards(),
1225 ),
1226 anon_id_seed,
1227 #[cfg(debug_assertions)]
1228 forbidden_edge,
1229 #[cfg(debug_assertions)]
1230 fingerprints: Lock::new(IndexVec::from_elem_n(None, new_node_count_estimate)),
1231 nodes_in_current_session: new_node_dbg.then(|| {
1232 Lock::new(FxHashMap::with_capacity_and_hasher(
1233 new_node_count_estimate,
1234 Default::default(),
1235 ))
1236 }),
1237 total_read_count: AtomicU64::new(0),
1238 total_duplicate_read_count: AtomicU64::new(0),
1239 }
1240 }
1241
1242 #[cfg(debug_assertions)]
1243 fn record_edge(&self, dep_node_index: DepNodeIndex, key: DepNode, fingerprint: Fingerprint) {
1244 if let Some(forbidden_edge) = &self.forbidden_edge {
1245 forbidden_edge.index_to_node.lock().insert(dep_node_index, key);
1246 }
1247 let previous = *self.fingerprints.lock().get_or_insert_with(dep_node_index, || fingerprint);
1248 assert_eq!(previous, fingerprint, "Unstable fingerprints for {:?}", key);
1249 }
1250
1251 #[inline(always)]
1252 fn record_node(
1253 &self,
1254 dep_node_index: DepNodeIndex,
1255 key: DepNode,
1256 _current_fingerprint: Fingerprint,
1257 ) {
1258 #[cfg(debug_assertions)]
1259 self.record_edge(dep_node_index, key, _current_fingerprint);
1260
1261 if let Some(ref nodes_in_current_session) = self.nodes_in_current_session {
1262 outline(|| {
1263 if nodes_in_current_session.lock().insert(key, dep_node_index).is_some() {
1264 panic!("Found duplicate dep-node {key:?}");
1265 }
1266 });
1267 }
1268 }
1269
1270 /// Writes the node to the current dep-graph and allocates a `DepNodeIndex` for it.
1271 /// Assumes that this is a node that has no equivalent in the previous dep-graph.
1272 #[inline(always)]
1273 fn alloc_new_node(
1274 &self,
1275 key: DepNode,
1276 edges: EdgesVec,
1277 current_fingerprint: Fingerprint,
1278 ) -> DepNodeIndex {
1279 let dep_node_index = self.encoder.send_new(key, current_fingerprint, edges);
1280
1281 self.record_node(dep_node_index, key, current_fingerprint);
1282
1283 dep_node_index
1284 }
1285
1286 #[inline]
1287 fn debug_assert_not_in_new_nodes(
1288 &self,
1289 prev_graph: &SerializedDepGraph,
1290 prev_index: SerializedDepNodeIndex,
1291 ) {
1292 if let Some(ref nodes_in_current_session) = self.nodes_in_current_session {
1293 debug_assert!(
1294 !nodes_in_current_session
1295 .lock()
1296 .contains_key(&prev_graph.index_to_node(prev_index)),
1297 "node from previous graph present in new node collection"
1298 );
1299 }
1300 }
1301}
1302
1303#[derive(Debug, Clone, Copy)]
1304pub enum TaskDepsRef<'a> {
1305 /// New dependencies can be added to the
1306 /// `TaskDeps`. This is used when executing a 'normal' query
1307 /// (no `eval_always` modifier)
1308 Allow(&'a Lock<TaskDeps>),
1309 /// This is used when executing an `eval_always` query. We don't
1310 /// need to track dependencies for a query that's always
1311 /// re-executed -- but we need to know that this is an `eval_always`
1312 /// query in order to emit dependencies to `DepNodeIndex::FOREVER_RED_NODE`
1313 /// when directly feeding other queries.
1314 EvalAlways,
1315 /// New dependencies are ignored. This is also used for `dep_graph.with_ignore`.
1316 Ignore,
1317 /// Any attempt to add new dependencies will cause a panic.
1318 /// This is used when decoding a query result from disk,
1319 /// to ensure that the decoding process doesn't itself
1320 /// require the execution of any queries.
1321 Forbid,
1322}
1323
1324#[derive(Debug)]
1325pub struct TaskDeps {
1326 #[cfg(debug_assertions)]
1327 node: Option<DepNode>,
1328 reads: EdgesVec,
1329 read_set: FxHashSet<DepNodeIndex>,
1330 phantom_data: PhantomData<DepNode>,
1331}
1332
1333impl Default for TaskDeps {
1334 fn default() -> Self {
1335 Self {
1336 #[cfg(debug_assertions)]
1337 node: None,
1338 reads: EdgesVec::new(),
1339 read_set: FxHashSet::with_capacity_and_hasher(128, Default::default()),
1340 phantom_data: PhantomData,
1341 }
1342 }
1343}
1344// A data structure that stores Option<DepNodeColor> values as a contiguous
1345// array, using one u32 per entry.
1346pub(super) struct DepNodeColorMap {
1347 values: IndexVec<SerializedDepNodeIndex, AtomicU32>,
1348}
1349
1350const COMPRESSED_NONE: u32 = u32::MAX;
1351const COMPRESSED_RED: u32 = u32::MAX - 1;
1352
1353impl DepNodeColorMap {
1354 fn new(size: usize) -> DepNodeColorMap {
1355 debug_assert!(COMPRESSED_RED > DepNodeIndex::MAX_AS_U32);
1356 DepNodeColorMap { values: (0..size).map(|_| AtomicU32::new(COMPRESSED_NONE)).collect() }
1357 }
1358
1359 #[inline]
1360 pub(super) fn current(&self, index: SerializedDepNodeIndex) -> Option<DepNodeIndex> {
1361 let value = self.values[index].load(Ordering::Relaxed);
1362 if value <= DepNodeIndex::MAX_AS_U32 { Some(DepNodeIndex::from_u32(value)) } else { None }
1363 }
1364
1365 #[inline]
1366 pub(super) fn get(&self, index: SerializedDepNodeIndex) -> Option<DepNodeColor> {
1367 match self.values[index].load(Ordering::Acquire) {
1368 COMPRESSED_NONE => None,
1369 COMPRESSED_RED => Some(DepNodeColor::Red),
1370 value => Some(DepNodeColor::Green(DepNodeIndex::from_u32(value))),
1371 }
1372 }
1373
1374 #[inline]
1375 pub(super) fn insert(&self, index: SerializedDepNodeIndex, color: DepNodeColor) {
1376 self.values[index].store(
1377 match color {
1378 DepNodeColor::Red => COMPRESSED_RED,
1379 DepNodeColor::Green(index) => index.as_u32(),
1380 },
1381 Ordering::Release,
1382 )
1383 }
1384}
1385
1386#[inline(never)]
1387#[cold]
1388pub(crate) fn print_markframe_trace<D: Deps>(graph: &DepGraph<D>, frame: Option<&MarkFrame<'_>>) {
1389 let data = graph.data.as_ref().unwrap();
1390
1391 eprintln!("there was a panic while trying to force a dep node");
1392 eprintln!("try_mark_green dep node stack:");
1393
1394 let mut i = 0;
1395 let mut current = frame;
1396 while let Some(frame) = current {
1397 let node = data.previous.index_to_node(frame.index);
1398 eprintln!("#{i} {node:?}");
1399 current = frame.parent;
1400 i += 1;
1401 }
1402
1403 eprintln!("end of try_mark_green dep node stack");
1404}
1405
1406#[cold]
1407#[inline(never)]
1408fn panic_on_forbidden_read<D: Deps>(data: &DepGraphData<D>, dep_node_index: DepNodeIndex) -> ! {
1409 // We have to do an expensive reverse-lookup of the DepNode that
1410 // corresponds to `dep_node_index`, but that's OK since we are about
1411 // to ICE anyway.
1412 let mut dep_node = None;
1413
1414 // First try to find the dep node among those that already existed in the
1415 // previous session and has been marked green
1416 for prev_index in data.colors.values.indices() {
1417 if data.colors.current(prev_index) == Some(dep_node_index) {
1418 dep_node = Some(data.previous.index_to_node(prev_index));
1419 break;
1420 }
1421 }
1422
1423 if dep_node.is_none()
1424 && let Some(nodes) = &data.current.nodes_in_current_session
1425 {
1426 // Try to find it among the nodes allocated so far in this session
1427 if let Some((node, _)) = nodes.lock().iter().find(|&(_, index)| *index == dep_node_index) {
1428 dep_node = Some(*node);
1429 }
1430 }
1431
1432 let dep_node = dep_node.map_or_else(
1433 || format!("with index {:?}", dep_node_index),
1434 |dep_node| format!("`{:?}`", dep_node),
1435 );
1436
1437 panic!(
1438 "Error: trying to record dependency on DepNode {dep_node} in a \
1439 context that does not allow it (e.g. during query deserialization). \
1440 The most common case of recording a dependency on a DepNode `foo` is \
1441 when the corresponding query `foo` is invoked. Invoking queries is not \
1442 allowed as part of loading something from the incremental on-disk cache. \
1443 See <https://github.com/rust-lang/rust/pull/91919>."
1444 )
1445}