Google Git Google Git
Sign in
rust/rust/fc5a7077ca43894de1ea0d3f9f56ac627ceef5c7/./compiler/rustc_middle/src/dep_graph/graph.rs
blob: 444d02521148c371ea887d2ef56b2f826429207d [file]
use std::assert_matches;
use std::fmt::Debug;
use std::hash::Hash;
use std::sync::Arc;
use std::sync::atomic::{AtomicU32, Ordering};
use rustc_data_structures::fingerprint::{Fingerprint, PackedFingerprint};
use rustc_data_structures::fx::{FxHashMap, FxHashSet};
use rustc_data_structures::outline;
use rustc_data_structures::profiling::QueryInvocationId;
use rustc_data_structures::sharded::{self, ShardedHashMap};
use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
use rustc_data_structures::sync::{AtomicU64, Lock, is_dyn_thread_safe};
use rustc_data_structures::unord::UnordMap;
use rustc_errors::DiagInner;
use rustc_index::IndexVec;
use rustc_macros::{Decodable, Encodable};
use rustc_serialize::opaque::{FileEncodeResult, FileEncoder};
use rustc_session::Session;
use rustc_span::Symbol;
use tracing::{debug, instrument};
#[cfg(debug_assertions)]
use {super::debug::EdgeFilter, std::env};
use super::retained::RetainedDepGraph;
use super::serialized::{GraphEncoder, SerializedDepGraph, SerializedDepNodeIndex};
use super::{DepKind, DepNode, WorkProductId, read_deps, with_deps};
use crate::dep_graph::edges::EdgesVec;
use crate::ich::StableHashingContext;
use crate::ty::TyCtxt;
use crate::verify_ich::incremental_verify_ich;
/// Tracks 'side effects' for a particular query.
/// This struct is saved to disk along with the query result,
/// and loaded from disk if we mark the query as green.
/// This allows us to 'replay' changes to global state
/// that would otherwise only occur if we actually
/// executed the query method.
///
/// Each side effect gets an unique dep node index which is added
/// as a dependency of the query which had the effect.
#[derive(Debug, Encodable, Decodable)]
pub enum QuerySideEffect {
/// Stores a diagnostic emitted during query execution.
/// This diagnostic will be re-emitted if we mark
/// the query as green, as that query will have the side
/// effect dep node as a dependency.
Diagnostic(DiagInner),
/// Records the feature used during query execution.
/// This feature will be inserted into `sess.used_features`
/// if we mark the query as green, as that query will have
/// the side effect dep node as a dependency.
CheckFeature { symbol: Symbol },
}
#[derive(Clone)]
pub struct DepGraph {
data: Option<Arc<DepGraphData>>,
/// This field is used for assigning DepNodeIndices when running in
/// non-incremental mode. Even in non-incremental mode we make sure that
/// each task has a `DepNodeIndex` that uniquely identifies it. This unique
/// ID is used for self-profiling.
virtual_dep_node_index: Arc<AtomicU32>,
}
rustc_index::newtype_index! {
pub struct DepNodeIndex {}
}
// We store a large collection of these in `prev_index_to_index` during
// non-full incremental builds, and want to ensure that the element size
// doesn't inadvertently increase.
rustc_data_structures::static_assert_size!(Option<DepNodeIndex>, 4);
impl DepNodeIndex {
const SINGLETON_ZERO_DEPS_ANON_NODE: DepNodeIndex = DepNodeIndex::ZERO;
pub const FOREVER_RED_NODE: DepNodeIndex = DepNodeIndex::from_u32(1);
}
impl From<DepNodeIndex> for QueryInvocationId {
#[inline(always)]
fn from(dep_node_index: DepNodeIndex) -> Self {
QueryInvocationId(dep_node_index.as_u32())
}
}
pub(crate) struct MarkFrame<'a> {
index: SerializedDepNodeIndex,
parent: Option<&'a MarkFrame<'a>>,
}
#[derive(Debug)]
pub(super) enum DepNodeColor {
Green(DepNodeIndex),
Red,
Unknown,
}
pub struct DepGraphData {
/// The new encoding of the dependency graph, optimized for red/green
/// tracking. The `current` field is the dependency graph of only the
/// current compilation session: We don't merge the previous dep-graph into
/// current one anymore, but we do reference shared data to save space.
current: CurrentDepGraph,
/// The dep-graph from the previous compilation session. It contains all
/// nodes and edges as well as all fingerprints of nodes that have them.
previous: Arc<SerializedDepGraph>,
colors: DepNodeColorMap,
/// When we load, there may be `.o` files, cached MIR, or other such
/// things available to us. If we find that they are not dirty, we
/// load the path to the file storing those work-products here into
/// this map. We can later look for and extract that data.
previous_work_products: WorkProductMap,
dep_node_debug: Lock<FxHashMap<DepNode, String>>,
/// Used by incremental compilation tests to assert that
/// a particular query result was decoded from disk
/// (not just marked green)
debug_loaded_from_disk: Lock<FxHashSet<DepNode>>,
}
pub fn hash_result<R>(hcx: &mut StableHashingContext<'_>, result: &R) -> Fingerprint
where
R: for<'a> HashStable<StableHashingContext<'a>>,
{
let mut stable_hasher = StableHasher::new();
result.hash_stable(hcx, &mut stable_hasher);
stable_hasher.finish()
}
impl DepGraph {
pub fn new(
session: &Session,
prev_graph: Arc<SerializedDepGraph>,
prev_work_products: WorkProductMap,
encoder: FileEncoder,
) -> DepGraph {
let prev_graph_node_count = prev_graph.node_count();
let current =
CurrentDepGraph::new(session, prev_graph_node_count, encoder, Arc::clone(&prev_graph));
let colors = DepNodeColorMap::new(prev_graph_node_count);
// Instantiate a node with zero dependencies only once for anonymous queries.
let _green_node_index = current.alloc_new_node(
DepNode { kind: DepKind::AnonZeroDeps, key_fingerprint: current.anon_id_seed.into() },
EdgesVec::new(),
Fingerprint::ZERO,
);
assert_eq!(_green_node_index, DepNodeIndex::SINGLETON_ZERO_DEPS_ANON_NODE);
// Create a single always-red node, with no dependencies of its own.
// Other nodes can use the always-red node as a fake dependency, to
// ensure that their dependency list will never be all-green.
let red_node_index = current.alloc_new_node(
DepNode { kind: DepKind::Red, key_fingerprint: Fingerprint::ZERO.into() },
EdgesVec::new(),
Fingerprint::ZERO,
);
assert_eq!(red_node_index, DepNodeIndex::FOREVER_RED_NODE);
if prev_graph_node_count > 0 {
let prev_index =
const { SerializedDepNodeIndex::from_u32(DepNodeIndex::FOREVER_RED_NODE.as_u32()) };
let result = colors.try_set_color(prev_index, DesiredColor::Red);
assert_matches!(result, TrySetColorResult::Success);
}
DepGraph {
data: Some(Arc::new(DepGraphData {
previous_work_products: prev_work_products,
dep_node_debug: Default::default(),
current,
previous: prev_graph,
colors,
debug_loaded_from_disk: Default::default(),
})),
virtual_dep_node_index: Arc::new(AtomicU32::new(0)),
}
}
pub fn new_disabled() -> DepGraph {
DepGraph { data: None, virtual_dep_node_index: Arc::new(AtomicU32::new(0)) }
}
#[inline]
pub fn data(&self) -> Option<&DepGraphData> {
self.data.as_deref()
}
/// Returns `true` if we are actually building the full dep-graph, and `false` otherwise.
#[inline]
pub fn is_fully_enabled(&self) -> bool {
self.data.is_some()
}
pub fn with_retained_dep_graph(&self, f: impl Fn(&RetainedDepGraph)) {
if let Some(data) = &self.data {
data.current.encoder.with_retained_dep_graph(f)
}
}
pub fn assert_ignored(&self) {
if let Some(..) = self.data {
read_deps(|task_deps| {
assert_matches!(
task_deps,
TaskDepsRef::Ignore,
"expected no task dependency tracking"
);
})
}
}
pub fn with_ignore<OP, R>(&self, op: OP) -> R
where
OP: FnOnce() -> R,
{
with_deps(TaskDepsRef::Ignore, op)
}
/// Used to wrap the deserialization of a query result from disk,
/// This method enforces that no new `DepNodes` are created during
/// query result deserialization.
///
/// Enforcing this makes the query dep graph simpler - all nodes
/// must be created during the query execution, and should be
/// created from inside the 'body' of a query (the implementation
/// provided by a particular compiler crate).
///
/// Consider the case of three queries `A`, `B`, and `C`, where
/// `A` invokes `B` and `B` invokes `C`:
///
/// `A -> B -> C`
///
/// Suppose that decoding the result of query `B` required re-computing
/// the query `C`. If we did not create a fresh `TaskDeps` when
/// decoding `B`, we would still be using the `TaskDeps` for query `A`
/// (if we needed to re-execute `A`). This would cause us to create
/// a new edge `A -> C`. If this edge did not previously
/// exist in the `DepGraph`, then we could end up with a different
/// `DepGraph` at the end of compilation, even if there were no
/// meaningful changes to the overall program (e.g. a newline was added).
/// In addition, this edge might cause a subsequent compilation run
/// to try to force `C` before marking other necessary nodes green. If
/// `C` did not exist in the new compilation session, then we could
/// get an ICE. Normally, we would have tried (and failed) to mark
/// some other query green (e.g. `item_children`) which was used
/// to obtain `C`, which would prevent us from ever trying to force
/// a nonexistent `D`.
///
/// It might be possible to enforce that all `DepNode`s read during
/// deserialization already exist in the previous `DepGraph`. In
/// the above example, we would invoke `D` during the deserialization
/// of `B`. Since we correctly create a new `TaskDeps` from the decoding
/// of `B`, this would result in an edge `B -> D`. If that edge already
/// existed (with the same `DepPathHash`es), then it should be correct
/// to allow the invocation of the query to proceed during deserialization
/// of a query result. We would merely assert that the dep-graph fragment
/// that would have been added by invoking `C` while decoding `B`
/// is equivalent to the dep-graph fragment that we already instantiated for B
/// (at the point where we successfully marked B as green).
///
/// However, this would require additional complexity
/// in the query infrastructure, and is not currently needed by the
/// decoding of any query results. Should the need arise in the future,
/// we should consider extending the query system with this functionality.
pub fn with_query_deserialization<OP, R>(&self, op: OP) -> R
where
OP: FnOnce() -> R,
{
with_deps(TaskDepsRef::Forbid, op)
}
#[inline(always)]
pub fn with_task<'tcx, A: Debug, R>(
&self,
dep_node: DepNode,
tcx: TyCtxt<'tcx>,
task_arg: A,
task_fn: fn(tcx: TyCtxt<'tcx>, task_arg: A) -> R,
hash_result: Option<fn(&mut StableHashingContext<'_>, &R) -> Fingerprint>,
) -> (R, DepNodeIndex) {
match self.data() {
Some(data) => data.with_task(dep_node, tcx, task_arg, task_fn, hash_result),
None => (task_fn(tcx, task_arg), self.next_virtual_depnode_index()),
}
}
pub fn with_anon_task<'tcx, OP, R>(
&self,
tcx: TyCtxt<'tcx>,
dep_kind: DepKind,
op: OP,
) -> (R, DepNodeIndex)
where
OP: FnOnce() -> R,
{
match self.data() {
Some(data) => {
let (result, index) = data.with_anon_task_inner(tcx, dep_kind, op);
self.read_index(index);
(result, index)
}
None => (op(), self.next_virtual_depnode_index()),
}
}
}
impl DepGraphData {
/// Starts a new dep-graph task. Dep-graph tasks are specified
/// using a free function (`task`) and **not** a closure -- this
/// is intentional because we want to exercise tight control over
/// what state they have access to. In particular, we want to
/// prevent implicit 'leaks' of tracked state into the task (which
/// could then be read without generating correct edges in the
/// dep-graph -- see the [rustc dev guide] for more details on
/// the dep-graph).
///
/// Therefore, the task function takes a `TyCtxt`, plus exactly one
/// additional argument, `task_arg`. The additional argument type can be
/// `()` if no argument is needed, or a tuple if multiple arguments are
/// needed.
///
/// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/queries/incremental-compilation.html
#[inline(always)]
pub fn with_task<'tcx, A: Debug, R>(
&self,
dep_node: DepNode,
tcx: TyCtxt<'tcx>,
task_arg: A,
task_fn: fn(tcx: TyCtxt<'tcx>, task_arg: A) -> R,
hash_result: Option<fn(&mut StableHashingContext<'_>, &R) -> Fingerprint>,
) -> (R, DepNodeIndex) {
// If the following assertion triggers, it can have two reasons:
// 1. Something is wrong with DepNode creation, either here or
// in `DepGraph::try_mark_green()`.
// 2. Two distinct query keys get mapped to the same `DepNode`
// (see for example #48923).
self.assert_dep_node_not_yet_allocated_in_current_session(tcx.sess, &dep_node, || {
format!(
"forcing query with already existing `DepNode`\n\
- query-key: {task_arg:?}\n\
- dep-node: {dep_node:?}"
)
});
let with_deps = |task_deps| with_deps(task_deps, || task_fn(tcx, task_arg));
let (result, edges) = if tcx.is_eval_always(dep_node.kind) {
(with_deps(TaskDepsRef::EvalAlways), EdgesVec::new())
} else {
let task_deps = Lock::new(TaskDeps::new(
#[cfg(debug_assertions)]
Some(dep_node),
0,
));
(with_deps(TaskDepsRef::Allow(&task_deps)), task_deps.into_inner().reads)
};
let dep_node_index =
self.hash_result_and_alloc_node(tcx, dep_node, edges, &result, hash_result);
(result, dep_node_index)
}
/// Executes something within an "anonymous" task, that is, a task the
/// `DepNode` of which is determined by the list of inputs it read from.
///
/// NOTE: this does not actually count as a read of the DepNode here.
/// Using the result of this task without reading the DepNode will result
/// in untracked dependencies which may lead to ICEs as nodes are
/// incorrectly marked green.
///
/// FIXME: This could perhaps return a `WithDepNode` to ensure that the
/// user of this function actually performs the read.
fn with_anon_task_inner<'tcx, OP, R>(
&self,
tcx: TyCtxt<'tcx>,
dep_kind: DepKind,
op: OP,
) -> (R, DepNodeIndex)
where
OP: FnOnce() -> R,
{
debug_assert!(!tcx.is_eval_always(dep_kind));
// Large numbers of reads are common enough here that pre-sizing `read_set`
// to 128 actually helps perf on some benchmarks.
let task_deps = Lock::new(TaskDeps::new(
#[cfg(debug_assertions)]
None,
128,
));
let result = with_deps(TaskDepsRef::Allow(&task_deps), op);
let task_deps = task_deps.into_inner();
let reads = task_deps.reads;
let dep_node_index = match reads.len() {
0 => {
// Because the dep-node id of anon nodes is computed from the sets of its
// dependencies we already know what the ID of this dependency-less node is
// going to be (i.e. equal to the precomputed
// `SINGLETON_DEPENDENCYLESS_ANON_NODE`). As a consequence we can skip creating
// a `StableHasher` and sending the node through interning.
DepNodeIndex::SINGLETON_ZERO_DEPS_ANON_NODE
}
1 => {
// When there is only one dependency, don't bother creating a node.
reads[0]
}
_ => {
// The dep node indices are hashed here instead of hashing the dep nodes of the
// dependencies. These indices may refer to different nodes per session, but this isn't
// a problem here because we that ensure the final dep node hash is per session only by
// combining it with the per session random number `anon_id_seed`. This hash only need
// to map the dependencies to a single value on a per session basis.
let mut hasher = StableHasher::new();
reads.hash(&mut hasher);
let target_dep_node = DepNode {
kind: dep_kind,
// Fingerprint::combine() is faster than sending Fingerprint
// through the StableHasher (at least as long as StableHasher
// is so slow).
key_fingerprint: self.current.anon_id_seed.combine(hasher.finish()).into(),
};
// The DepNodes generated by the process above are not unique. 2 queries could
// have exactly the same dependencies. However, deserialization does not handle
// duplicated nodes, so we do the deduplication here directly.
//
// As anonymous nodes are a small quantity compared to the full dep-graph, the
// memory impact of this `anon_node_to_index` map remains tolerable, and helps
// us avoid useless growth of the graph with almost-equivalent nodes.
self.current.anon_node_to_index.get_or_insert_with(target_dep_node, || {
self.current.alloc_new_node(target_dep_node, reads, Fingerprint::ZERO)
})
}
};
(result, dep_node_index)
}
/// Intern the new `DepNode` with the dependencies up-to-now.
fn hash_result_and_alloc_node<'tcx, R>(
&self,
tcx: TyCtxt<'tcx>,
node: DepNode,
edges: EdgesVec,
result: &R,
hash_result: Option<fn(&mut StableHashingContext<'_>, &R) -> Fingerprint>,
) -> DepNodeIndex {
let hashing_timer = tcx.prof.incr_result_hashing();
let current_fingerprint = hash_result.map(|hash_result| {
tcx.with_stable_hashing_context(|mut hcx| hash_result(&mut hcx, result))
});
let dep_node_index = self.alloc_and_color_node(node, edges, current_fingerprint);
hashing_timer.finish_with_query_invocation_id(dep_node_index.into());
dep_node_index
}
}
impl DepGraph {
#[inline]
pub fn read_index(&self, dep_node_index: DepNodeIndex) {
if let Some(ref data) = self.data {
read_deps(|task_deps| {
let mut task_deps = match task_deps {
TaskDepsRef::Allow(deps) => deps.lock(),
TaskDepsRef::EvalAlways => {
// We don't need to record dependencies of eval_always
// queries. They are re-evaluated unconditionally anyway.
return;
}
TaskDepsRef::Ignore => return,
TaskDepsRef::Forbid => {
// Reading is forbidden in this context. ICE with a useful error message.
panic_on_forbidden_read(data, dep_node_index)
}
};
let task_deps = &mut *task_deps;
if cfg!(debug_assertions) {
data.current.total_read_count.fetch_add(1, Ordering::Relaxed);
}
// Has `dep_node_index` been seen before? Use either a linear scan or a hashset
// lookup to determine this. See `TaskDeps::read_set` for details.
let new_read = if task_deps.reads.len() <= TaskDeps::LINEAR_SCAN_MAX {
!task_deps.reads.contains(&dep_node_index)
} else {
task_deps.read_set.insert(dep_node_index)
};
if new_read {
task_deps.reads.push(dep_node_index);
if task_deps.reads.len() == TaskDeps::LINEAR_SCAN_MAX + 1 {
// Fill `read_set` with what we have so far. Future lookups will use it.
task_deps.read_set.extend(task_deps.reads.iter().copied());
}
#[cfg(debug_assertions)]
{
if let Some(target) = task_deps.node
&& let Some(ref forbidden_edge) = data.current.forbidden_edge
{
let src = forbidden_edge.index_to_node.lock()[&dep_node_index];
if forbidden_edge.test(&src, &target) {
panic!("forbidden edge {:?} -> {:?} created", src, target)
}
}
}
} else if cfg!(debug_assertions) {
data.current.total_duplicate_read_count.fetch_add(1, Ordering::Relaxed);
}
})
}
}
/// This encodes a side effect by creating a node with an unique index and associating
/// it with the node, for use in the next session.
#[inline]
pub fn record_diagnostic<'tcx>(&self, tcx: TyCtxt<'tcx>, diagnostic: &DiagInner) {
if let Some(ref data) = self.data {
read_deps(|task_deps| match task_deps {
TaskDepsRef::EvalAlways | TaskDepsRef::Ignore => return,
TaskDepsRef::Forbid | TaskDepsRef::Allow(..) => {
let dep_node_index = data
.encode_side_effect(tcx, QuerySideEffect::Diagnostic(diagnostic.clone()));
self.read_index(dep_node_index);
}
})
}
}
/// This forces a side effect node green by running its side effect. `prev_index` would
/// refer to a node created used `encode_side_effect` in the previous session.
#[inline]
pub fn force_side_effect<'tcx>(&self, tcx: TyCtxt<'tcx>, prev_index: SerializedDepNodeIndex) {
if let Some(ref data) = self.data {
data.force_side_effect(tcx, prev_index);
}
}
#[inline]
pub fn encode_side_effect<'tcx>(
&self,
tcx: TyCtxt<'tcx>,
side_effect: QuerySideEffect,
) -> DepNodeIndex {
if let Some(ref data) = self.data {
data.encode_side_effect(tcx, side_effect)
} else {
self.next_virtual_depnode_index()
}
}
/// Create a node when we force-feed a value into the query cache.
/// This is used to remove cycles during type-checking const generic parameters.
///
/// As usual in the query system, we consider the current state of the calling query
/// only depends on the list of dependencies up to now. As a consequence, the value
/// that this query gives us can only depend on those dependencies too. Therefore,
/// it is sound to use the current dependency set for the created node.
///
/// During replay, the order of the nodes is relevant in the dependency graph.
/// So the unchanged replay will mark the caller query before trying to mark this one.
/// If there is a change to report, the caller query will be re-executed before this one.
///
/// FIXME: If the code is changed enough for this node to be marked before requiring the
/// caller's node, we suppose that those changes will be enough to mark this node red and
/// force a recomputation using the "normal" way.
pub fn with_feed_task<'tcx, R>(
&self,
node: DepNode,
tcx: TyCtxt<'tcx>,
result: &R,
hash_result: Option<fn(&mut StableHashingContext<'_>, &R) -> Fingerprint>,
format_value_fn: fn(&R) -> String,
) -> DepNodeIndex {
if let Some(data) = self.data.as_ref() {
// The caller query has more dependencies than the node we are creating. We may
// encounter a case where this created node is marked as green, but the caller query is
// subsequently marked as red or recomputed. In this case, we will end up feeding a
// value to an existing node.
//
// For sanity, we still check that the loaded stable hash and the new one match.
if let Some(prev_index) = data.previous.node_to_index_opt(&node) {
let dep_node_index = data.colors.current(prev_index);
if let Some(dep_node_index) = dep_node_index {
incremental_verify_ich(
tcx,
data,
result,
prev_index,
hash_result,
format_value_fn,
);
#[cfg(debug_assertions)]
if hash_result.is_some() {
data.current.record_edge(
dep_node_index,
node,
data.prev_value_fingerprint_of(prev_index),
);
}
return dep_node_index;
}
}
let mut edges = EdgesVec::new();
read_deps(|task_deps| match task_deps {
TaskDepsRef::Allow(deps) => edges.extend(deps.lock().reads.iter().copied()),
TaskDepsRef::EvalAlways => {
edges.push(DepNodeIndex::FOREVER_RED_NODE);
}
TaskDepsRef::Ignore => {}
TaskDepsRef::Forbid => {
panic!("Cannot summarize when dependencies are not recorded.")
}
});
data.hash_result_and_alloc_node(tcx, node, edges, result, hash_result)
} else {
// Incremental compilation is turned off. We just execute the task
// without tracking. We still provide a dep-node index that uniquely
// identifies the task so that we have a cheap way of referring to
// the query for self-profiling.
self.next_virtual_depnode_index()
}
}
}
impl DepGraphData {
fn assert_dep_node_not_yet_allocated_in_current_session<S: std::fmt::Display>(
&self,
sess: &Session,
dep_node: &DepNode,
msg: impl FnOnce() -> S,
) {
if let Some(prev_index) = self.previous.node_to_index_opt(dep_node) {
let color = self.colors.get(prev_index);
let ok = match color {
DepNodeColor::Unknown => true,
DepNodeColor::Red => false,
DepNodeColor::Green(..) => sess.threads() > 1, // Other threads may mark this green
};
if !ok {
panic!("{}", msg())
}
} else if let Some(nodes_in_current_session) = &self.current.nodes_in_current_session {
outline(|| {
let seen = nodes_in_current_session.lock().contains_key(dep_node);
assert!(!seen, "{}", msg());
});
}
}
fn node_color(&self, dep_node: &DepNode) -> DepNodeColor {
if let Some(prev_index) = self.previous.node_to_index_opt(dep_node) {
self.colors.get(prev_index)
} else {
// This is a node that did not exist in the previous compilation session.
DepNodeColor::Unknown
}
}
/// Returns true if the given node has been marked as green during the
/// current compilation session. Used in various assertions
#[inline]
pub fn is_index_green(&self, prev_index: SerializedDepNodeIndex) -> bool {
matches!(self.colors.get(prev_index), DepNodeColor::Green(_))
}
#[inline]
pub fn prev_value_fingerprint_of(&self, prev_index: SerializedDepNodeIndex) -> Fingerprint {
self.previous.value_fingerprint_for_index(prev_index)
}
#[inline]
pub(crate) fn prev_node_of(&self, prev_index: SerializedDepNodeIndex) -> &DepNode {
self.previous.index_to_node(prev_index)
}
pub fn mark_debug_loaded_from_disk(&self, dep_node: DepNode) {
self.debug_loaded_from_disk.lock().insert(dep_node);
}
/// This encodes a side effect by creating a node with an unique index and associating
/// it with the node, for use in the next session.
#[inline]
fn encode_side_effect<'tcx>(
&self,
tcx: TyCtxt<'tcx>,
side_effect: QuerySideEffect,
) -> DepNodeIndex {
// Use `send_new` so we get an unique index, even though the dep node is not.
let dep_node_index = self.current.encoder.send_new(
DepNode {
kind: DepKind::SideEffect,
key_fingerprint: PackedFingerprint::from(Fingerprint::ZERO),
},
Fingerprint::ZERO,
// We want the side effect node to always be red so it will be forced and run the
// side effect.
std::iter::once(DepNodeIndex::FOREVER_RED_NODE).collect(),
);
tcx.query_system.side_effects.borrow_mut().insert(dep_node_index, side_effect);
dep_node_index
}
/// This forces a side effect node green by running its side effect. `prev_index` would
/// refer to a node created used `encode_side_effect` in the previous session.
#[inline]
fn force_side_effect<'tcx>(&self, tcx: TyCtxt<'tcx>, prev_index: SerializedDepNodeIndex) {
with_deps(TaskDepsRef::Ignore, || {
let side_effect = tcx
.query_system
.on_disk_cache
.as_ref()
.unwrap()
.load_side_effect(tcx, prev_index)
.unwrap();
// Use `send_and_color` as `promote_node_and_deps_to_current` expects all
// green dependencies. `send_and_color` will also prevent multiple nodes
// being encoded for concurrent calls.
let dep_node_index = self.current.encoder.send_and_color(
prev_index,
&self.colors,
DepNode {
kind: DepKind::SideEffect,
key_fingerprint: PackedFingerprint::from(Fingerprint::ZERO),
},
Fingerprint::ZERO,
std::iter::once(DepNodeIndex::FOREVER_RED_NODE).collect(),
true,
);
match &side_effect {
QuerySideEffect::Diagnostic(diagnostic) => {
tcx.dcx().emit_diagnostic(diagnostic.clone());
}
QuerySideEffect::CheckFeature { symbol } => {
tcx.sess.used_features.lock().insert(*symbol, dep_node_index.as_u32());
}
}
// This will just overwrite the same value for concurrent calls.
tcx.query_system.side_effects.borrow_mut().insert(dep_node_index, side_effect);
})
}
fn alloc_and_color_node(
&self,
key: DepNode,
edges: EdgesVec,
value_fingerprint: Option<Fingerprint>,
) -> DepNodeIndex {
if let Some(prev_index) = self.previous.node_to_index_opt(&key) {
// Determine the color and index of the new `DepNode`.
let is_green = if let Some(value_fingerprint) = value_fingerprint {
if value_fingerprint == self.previous.value_fingerprint_for_index(prev_index) {
// This is a green node: it existed in the previous compilation,
// its query was re-executed, and it has the same result as before.
true
} else {
// This is a red node: it existed in the previous compilation, its query
// was re-executed, but it has a different result from before.
false
}
} else {
// This is a red node, effectively: it existed in the previous compilation
// session, its query was re-executed, but it doesn't compute a result hash
// (i.e. it represents a `no_hash` query), so we have no way of determining
// whether or not the result was the same as before.
false
};
let value_fingerprint = value_fingerprint.unwrap_or(Fingerprint::ZERO);
let dep_node_index = self.current.encoder.send_and_color(
prev_index,
&self.colors,
key,
value_fingerprint,
edges,
is_green,
);
self.current.record_node(dep_node_index, key, value_fingerprint);
dep_node_index
} else {
self.current.alloc_new_node(key, edges, value_fingerprint.unwrap_or(Fingerprint::ZERO))
}
}
fn promote_node_and_deps_to_current(
&self,
prev_index: SerializedDepNodeIndex,
) -> Option<DepNodeIndex> {
self.current.debug_assert_not_in_new_nodes(&self.previous, prev_index);
let dep_node_index = self.current.encoder.send_promoted(prev_index, &self.colors);
#[cfg(debug_assertions)]
if let Some(dep_node_index) = dep_node_index {
self.current.record_edge(
dep_node_index,
*self.previous.index_to_node(prev_index),
self.previous.value_fingerprint_for_index(prev_index),
);
}
dep_node_index
}
}
impl DepGraph {
/// Checks whether a previous work product exists for `v` and, if
/// so, return the path that leads to it. Used to skip doing work.
pub fn previous_work_product(&self, v: &WorkProductId) -> Option<WorkProduct> {
self.data.as_ref().and_then(|data| data.previous_work_products.get(v).cloned())
}
/// Access the map of work-products created during the cached run. Only
/// used during saving of the dep-graph.
pub fn previous_work_products(&self) -> &WorkProductMap {
&self.data.as_ref().unwrap().previous_work_products
}
pub fn debug_was_loaded_from_disk(&self, dep_node: DepNode) -> bool {
self.data.as_ref().unwrap().debug_loaded_from_disk.lock().contains(&dep_node)
}
pub fn debug_dep_kind_was_loaded_from_disk(&self, dep_kind: DepKind) -> bool {
// We only check if we have a dep node corresponding to the given dep kind.
#[allow(rustc::potential_query_instability)]
self.data
.as_ref()
.unwrap()
.debug_loaded_from_disk
.lock()
.iter()
.any(|node| node.kind == dep_kind)
}
#[cfg(debug_assertions)]
#[inline(always)]
pub(crate) fn register_dep_node_debug_str<F>(&self, dep_node: DepNode, debug_str_gen: F)
where
F: FnOnce() -> String,
{
// Early queries (e.g., `-Z query-dep-graph` on empty crates) can reach here
// before the graph is initialized. Return early to prevent an ICE.
let data = match &self.data {
Some(d) => d,
None => return,
};
let dep_node_debug = &data.dep_node_debug;
if dep_node_debug.borrow().contains_key(&dep_node) {
return;
}
let debug_str = self.with_ignore(debug_str_gen);
dep_node_debug.borrow_mut().insert(dep_node, debug_str);
}
pub(crate) fn dep_node_debug_str(&self, dep_node: DepNode) -> Option<String> {
self.data.as_ref()?.dep_node_debug.borrow().get(&dep_node).cloned()
}
fn node_color(&self, dep_node: &DepNode) -> DepNodeColor {
if let Some(ref data) = self.data {
return data.node_color(dep_node);
}
DepNodeColor::Unknown
}
pub fn try_mark_green<'tcx>(
&self,
tcx: TyCtxt<'tcx>,
dep_node: &DepNode,
) -> Option<(SerializedDepNodeIndex, DepNodeIndex)> {
self.data()?.try_mark_green(tcx, dep_node)
}
}
impl DepGraphData {
/// Try to mark a node index for the node dep_node.
///
/// A node will have an index, when it's already been marked green, or when we can mark it
/// green. This function will mark the current task as a reader of the specified node, when
/// a node index can be found for that node.
pub fn try_mark_green<'tcx>(
&self,
tcx: TyCtxt<'tcx>,
dep_node: &DepNode,
) -> Option<(SerializedDepNodeIndex, DepNodeIndex)> {
debug_assert!(!tcx.is_eval_always(dep_node.kind));
// Return None if the dep node didn't exist in the previous session
let prev_index = self.previous.node_to_index_opt(dep_node)?;
debug_assert_eq!(self.previous.index_to_node(prev_index), dep_node);
match self.colors.get(prev_index) {
DepNodeColor::Green(dep_node_index) => Some((prev_index, dep_node_index)),
DepNodeColor::Red => None,
DepNodeColor::Unknown => {
// This DepNode and the corresponding query invocation existed
// in the previous compilation session too, so we can try to
// mark it as green by recursively marking all of its
// dependencies green.
self.try_mark_previous_green(tcx, prev_index, None)
.map(|dep_node_index| (prev_index, dep_node_index))
}
}
}
#[instrument(skip(self, tcx, parent_dep_node_index, frame), level = "debug")]
fn try_mark_parent_green<'tcx>(
&self,
tcx: TyCtxt<'tcx>,
parent_dep_node_index: SerializedDepNodeIndex,
frame: &MarkFrame<'_>,
) -> Option<()> {
let get_dep_dep_node = || self.previous.index_to_node(parent_dep_node_index);
match self.colors.get(parent_dep_node_index) {
DepNodeColor::Green(_) => {
// This dependency has been marked as green before, we are
// still fine and can continue with checking the other
// dependencies.
//
// This path is extremely hot. We don't want to get the
// `dep_dep_node` unless it's necessary. Hence the
// `get_dep_dep_node` closure.
debug!("dependency {:?} was immediately green", get_dep_dep_node());
return Some(());
}
DepNodeColor::Red => {
// We found a dependency the value of which has changed
// compared to the previous compilation session. We cannot
// mark the DepNode as green and also don't need to bother
// with checking any of the other dependencies.
debug!("dependency {:?} was immediately red", get_dep_dep_node());
return None;
}
DepNodeColor::Unknown => {}
}
let dep_dep_node = get_dep_dep_node();
// We don't know the state of this dependency. If it isn't
// an eval_always node, let's try to mark it green recursively.
if !tcx.is_eval_always(dep_dep_node.kind) {
debug!(
"state of dependency {:?} ({}) is unknown, trying to mark it green",
dep_dep_node, dep_dep_node.key_fingerprint,
);
let node_index = self.try_mark_previous_green(tcx, parent_dep_node_index, Some(frame));
if node_index.is_some() {
debug!("managed to MARK dependency {dep_dep_node:?} as green");
return Some(());
}
}
// We failed to mark it green, so we try to force the query.
debug!("trying to force dependency {dep_dep_node:?}");
if !tcx.try_force_from_dep_node(*dep_dep_node, parent_dep_node_index, frame) {
// The DepNode could not be forced.
debug!("dependency {dep_dep_node:?} could not be forced");
return None;
}
match self.colors.get(parent_dep_node_index) {
DepNodeColor::Green(_) => {
debug!("managed to FORCE dependency {dep_dep_node:?} to green");
return Some(());
}
DepNodeColor::Red => {
debug!("dependency {dep_dep_node:?} was red after forcing");
return None;
}
DepNodeColor::Unknown => {}
}
if let None = tcx.dcx().has_errors_or_delayed_bugs() {
panic!("try_mark_previous_green() - Forcing the DepNode should have set its color")
}
// If the query we just forced has resulted in
// some kind of compilation error, we cannot rely on
// the dep-node color having been properly updated.
// This means that the query system has reached an
// invalid state. We let the compiler continue (by
// returning `None`) so it can emit error messages
// and wind down, but rely on the fact that this
// invalid state will not be persisted to the
// incremental compilation cache because of
// compilation errors being present.
debug!("dependency {dep_dep_node:?} resulted in compilation error");
return None;
}
/// Try to mark a dep-node which existed in the previous compilation session as green.
#[instrument(skip(self, tcx, prev_dep_node_index, frame), level = "debug")]
fn try_mark_previous_green<'tcx>(
&self,
tcx: TyCtxt<'tcx>,
prev_dep_node_index: SerializedDepNodeIndex,
frame: Option<&MarkFrame<'_>>,
) -> Option<DepNodeIndex> {
let frame = MarkFrame { index: prev_dep_node_index, parent: frame };
// We never try to mark eval_always nodes as green
debug_assert!(!tcx.is_eval_always(self.previous.index_to_node(prev_dep_node_index).kind));
let prev_deps = self.previous.edge_targets_from(prev_dep_node_index);
for dep_dep_node_index in prev_deps {
self.try_mark_parent_green(tcx, dep_dep_node_index, &frame)?;
}
// If we got here without hitting a `return` that means that all
// dependencies of this DepNode could be marked as green. Therefore we
// can also mark this DepNode as green.
// There may be multiple threads trying to mark the same dep node green concurrently
// We allocating an entry for the node in the current dependency graph and
// adding all the appropriate edges imported from the previous graph.
//
// `no_hash` nodes may fail this promotion due to already being conservatively colored red.
let dep_node_index = self.promote_node_and_deps_to_current(prev_dep_node_index)?;
// ... and finally storing a "Green" entry in the color map.
// Multiple threads can all write the same color here
debug!(
"successfully marked {:?} as green",
self.previous.index_to_node(prev_dep_node_index)
);
Some(dep_node_index)
}
}
impl DepGraph {
/// Returns true if the given node has been marked as red during the
/// current compilation session. Used in various assertions
pub fn is_red(&self, dep_node: &DepNode) -> bool {
matches!(self.node_color(dep_node), DepNodeColor::Red)
}
/// Returns true if the given node has been marked as green during the
/// current compilation session. Used in various assertions
pub fn is_green(&self, dep_node: &DepNode) -> bool {
matches!(self.node_color(dep_node), DepNodeColor::Green(_))
}
pub fn assert_dep_node_not_yet_allocated_in_current_session<S: std::fmt::Display>(
&self,
sess: &Session,
dep_node: &DepNode,
msg: impl FnOnce() -> S,
) {
if let Some(data) = &self.data {
data.assert_dep_node_not_yet_allocated_in_current_session(sess, dep_node, msg)
}
}
/// This method loads all on-disk cacheable query results into memory, so
/// they can be written out to the new cache file again. Most query results
/// will already be in memory but in the case where we marked something as
/// green but then did not need the value, that value will never have been
/// loaded from disk.
///
/// This method will only load queries that will end up in the disk cache.
/// Other queries will not be executed.
pub fn exec_cache_promotions<'tcx>(&self, tcx: TyCtxt<'tcx>) {
let _prof_timer = tcx.prof.generic_activity("incr_comp_query_cache_promotion");
let data = self.data.as_ref().unwrap();
for prev_index in data.colors.values.indices() {
match data.colors.get(prev_index) {
DepNodeColor::Green(_) => {
let dep_node = data.previous.index_to_node(prev_index);
if let Some(promote_fn) =
tcx.dep_kind_vtable(dep_node.kind).promote_from_disk_fn
{
promote_fn(tcx, *dep_node)
};
}
DepNodeColor::Unknown | DepNodeColor::Red => {
// We can skip red nodes because a node can only be marked
// as red if the query result was recomputed and thus is
// already in memory.
}
}
}
}
pub(crate) fn finish_encoding(&self) -> FileEncodeResult {
if let Some(data) = &self.data { data.current.encoder.finish(&data.current) } else { Ok(0) }
}
pub fn next_virtual_depnode_index(&self) -> DepNodeIndex {
debug_assert!(self.data.is_none());
let index = self.virtual_dep_node_index.fetch_add(1, Ordering::Relaxed);
DepNodeIndex::from_u32(index)
}
}
/// A "work product" is an intermediate result that we save into the
/// incremental directory for later re-use. The primary example are
/// the object files that we save for each partition at code
/// generation time.
///
/// Each work product is associated with a dep-node, representing the
/// process that produced the work-product. If that dep-node is found
/// to be dirty when we load up, then we will delete the work-product
/// at load time. If the work-product is found to be clean, then we
/// will keep a record in the `previous_work_products` list.
///
/// In addition, work products have an associated hash. This hash is
/// an extra hash that can be used to decide if the work-product from
/// a previous compilation can be re-used (in addition to the dirty
/// edges check).
///
/// As the primary example, consider the object files we generate for
/// each partition. In the first run, we create partitions based on
/// the symbols that need to be compiled. For each partition P, we
/// hash the symbols in P and create a `WorkProduct` record associated
/// with `DepNode::CodegenUnit(P)`; the hash is the set of symbols
/// in P.
///
/// The next time we compile, if the `DepNode::CodegenUnit(P)` is
/// judged to be clean (which means none of the things we read to
/// generate the partition were found to be dirty), it will be loaded
/// into previous work products. We will then regenerate the set of
/// symbols in the partition P and hash them (note that new symbols
/// may be added -- for example, new monomorphizations -- even if
/// nothing in P changed!). We will compare that hash against the
/// previous hash. If it matches up, we can reuse the object file.
#[derive(Clone, Debug, Encodable, Decodable)]
pub struct WorkProduct {
pub cgu_name: String,
/// Saved files associated with this CGU. In each key/value pair, the value is the path to the
/// saved file and the key is some identifier for the type of file being saved.
///
/// By convention, file extensions are currently used as identifiers, i.e. the key "o" maps to
/// the object file's path, and "dwo" to the dwarf object file's path.
pub saved_files: UnordMap<String, String>,
}
pub type WorkProductMap = UnordMap<WorkProductId, WorkProduct>;
// Index type for `DepNodeData`'s edges.
rustc_index::newtype_index! {
struct EdgeIndex {}
}
/// `CurrentDepGraph` stores the dependency graph for the current session. It
/// will be populated as we run queries or tasks. We never remove nodes from the
/// graph: they are only added.
///
/// The nodes in it are identified by a `DepNodeIndex`. We avoid keeping the nodes
/// in memory. This is important, because these graph structures are some of the
/// largest in the compiler.
///
/// For this reason, we avoid storing `DepNode`s more than once as map
/// keys. The `anon_node_to_index` map only contains nodes of anonymous queries not in the previous
/// graph, and we map nodes in the previous graph to indices via a two-step
/// mapping. `SerializedDepGraph` maps from `DepNode` to `SerializedDepNodeIndex`,
/// and the `prev_index_to_index` vector (which is more compact and faster than
/// using a map) maps from `SerializedDepNodeIndex` to `DepNodeIndex`.
///
/// This struct uses three locks internally. The `data`, `anon_node_to_index`,
/// and `prev_index_to_index` fields are locked separately. Operations that take
/// a `DepNodeIndex` typically just access the `data` field.
///
/// We only need to manipulate at most two locks simultaneously:
/// `anon_node_to_index` and `data`, or `prev_index_to_index` and `data`. When
/// manipulating both, we acquire `anon_node_to_index` or `prev_index_to_index`
/// first, and `data` second.
pub(super) struct CurrentDepGraph {
encoder: GraphEncoder,
anon_node_to_index: ShardedHashMap<DepNode, DepNodeIndex>,
/// This is used to verify that value fingerprints do not change between the
/// creation of a node and its recomputation.
#[cfg(debug_assertions)]
value_fingerprints: Lock<IndexVec<DepNodeIndex, Option<Fingerprint>>>,
/// Used to trap when a specific edge is added to the graph.
/// This is used for debug purposes and is only active with `debug_assertions`.
#[cfg(debug_assertions)]
forbidden_edge: Option<EdgeFilter>,
/// Used to verify the absence of hash collisions among DepNodes.
/// This field is only `Some` if the `-Z incremental_verify_ich` option is present
/// or if `debug_assertions` are enabled.
///
/// The map contains all DepNodes that have been allocated in the current session so far.
nodes_in_current_session: Option<Lock<FxHashMap<DepNode, DepNodeIndex>>>,
/// Anonymous `DepNode`s are nodes whose IDs we compute from the list of
/// their edges. This has the beneficial side-effect that multiple anonymous
/// nodes can be coalesced into one without changing the semantics of the
/// dependency graph. However, the merging of nodes can lead to a subtle
/// problem during red-green marking: The color of an anonymous node from
/// the current session might "shadow" the color of the node with the same
/// ID from the previous session. In order to side-step this problem, we make
/// sure that anonymous `NodeId`s allocated in different sessions don't overlap.
/// This is implemented by mixing a session-key into the ID fingerprint of
/// each anon node. The session-key is a hash of the number of previous sessions.
anon_id_seed: Fingerprint,
/// These are simple counters that are for profiling and
/// debugging and only active with `debug_assertions`.
pub(super) total_read_count: AtomicU64,
pub(super) total_duplicate_read_count: AtomicU64,
}
impl CurrentDepGraph {
fn new(
session: &Session,
prev_graph_node_count: usize,
encoder: FileEncoder,
previous: Arc<SerializedDepGraph>,
) -> Self {
let mut stable_hasher = StableHasher::new();
previous.session_count().hash(&mut stable_hasher);
let anon_id_seed = stable_hasher.finish();
#[cfg(debug_assertions)]
let forbidden_edge = match env::var("RUST_FORBID_DEP_GRAPH_EDGE") {
Ok(s) => match EdgeFilter::new(&s) {
Ok(f) => Some(f),
Err(err) => panic!("RUST_FORBID_DEP_GRAPH_EDGE invalid: {}", err),
},
Err(_) => None,
};
let new_node_count_estimate = 102 * prev_graph_node_count / 100 + 200;
let new_node_dbg =
session.opts.unstable_opts.incremental_verify_ich || cfg!(debug_assertions);
CurrentDepGraph {
encoder: GraphEncoder::new(session, encoder, prev_graph_node_count, previous),
anon_node_to_index: ShardedHashMap::with_capacity(
// FIXME: The count estimate is off as anon nodes are only a portion of the nodes.
new_node_count_estimate / sharded::shards(),
),
anon_id_seed,
#[cfg(debug_assertions)]
forbidden_edge,
#[cfg(debug_assertions)]
value_fingerprints: Lock::new(IndexVec::from_elem_n(None, new_node_count_estimate)),
nodes_in_current_session: new_node_dbg.then(|| {
Lock::new(FxHashMap::with_capacity_and_hasher(
new_node_count_estimate,
Default::default(),
))
}),
total_read_count: AtomicU64::new(0),
total_duplicate_read_count: AtomicU64::new(0),
}
}
#[cfg(debug_assertions)]
fn record_edge(
&self,
dep_node_index: DepNodeIndex,
key: DepNode,
value_fingerprint: Fingerprint,
) {
if let Some(forbidden_edge) = &self.forbidden_edge {
forbidden_edge.index_to_node.lock().insert(dep_node_index, key);
}
let prior_value_fingerprint = *self
.value_fingerprints
.lock()
.get_or_insert_with(dep_node_index, || value_fingerprint);
assert_eq!(prior_value_fingerprint, value_fingerprint, "Unstable fingerprints for {key:?}");
}
#[inline(always)]
fn record_node(
&self,
dep_node_index: DepNodeIndex,
key: DepNode,
_value_fingerprint: Fingerprint,
) {
#[cfg(debug_assertions)]
self.record_edge(dep_node_index, key, _value_fingerprint);
if let Some(ref nodes_in_current_session) = self.nodes_in_current_session {
outline(|| {
if nodes_in_current_session.lock().insert(key, dep_node_index).is_some() {
panic!("Found duplicate dep-node {key:?}");
}
});
}
}
/// Writes the node to the current dep-graph and allocates a `DepNodeIndex` for it.
/// Assumes that this is a node that has no equivalent in the previous dep-graph.
#[inline(always)]
fn alloc_new_node(
&self,
key: DepNode,
edges: EdgesVec,
value_fingerprint: Fingerprint,
) -> DepNodeIndex {
let dep_node_index = self.encoder.send_new(key, value_fingerprint, edges);
self.record_node(dep_node_index, key, value_fingerprint);
dep_node_index
}
#[inline]
fn debug_assert_not_in_new_nodes(
&self,
prev_graph: &SerializedDepGraph,
prev_index: SerializedDepNodeIndex,
) {
if !is_dyn_thread_safe()
&& let Some(ref nodes_in_current_session) = self.nodes_in_current_session
{
debug_assert!(
!nodes_in_current_session
.lock()
.contains_key(&prev_graph.index_to_node(prev_index)),
"node from previous graph present in new node collection"
);
}
}
}
#[derive(Debug, Clone, Copy)]
pub enum TaskDepsRef<'a> {
/// New dependencies can be added to the
/// `TaskDeps`. This is used when executing a 'normal' query
/// (no `eval_always` modifier)
Allow(&'a Lock<TaskDeps>),
/// This is used when executing an `eval_always` query. We don't
/// need to track dependencies for a query that's always
/// re-executed -- but we need to know that this is an `eval_always`
/// query in order to emit dependencies to `DepNodeIndex::FOREVER_RED_NODE`
/// when directly feeding other queries.
EvalAlways,
/// New dependencies are ignored. This is also used for `dep_graph.with_ignore`.
Ignore,
/// Any attempt to add new dependencies will cause a panic.
/// This is used when decoding a query result from disk,
/// to ensure that the decoding process doesn't itself
/// require the execution of any queries.
Forbid,
}
#[derive(Debug)]
pub struct TaskDeps {
#[cfg(debug_assertions)]
node: Option<DepNode>,
/// A vector of `DepNodeIndex`, basically.
reads: EdgesVec,
/// When adding new edges to `reads` in `DepGraph::read_index` we need to determine if the edge
/// has been seen before. If the number of elements in `reads` is small, we just do a linear
/// scan. If the number is higher, a hashset has better perf. This field is that hashset. It's
/// only used if the number of elements in `reads` exceeds `LINEAR_SCAN_MAX`.
read_set: FxHashSet<DepNodeIndex>,
}
impl TaskDeps {
/// See `TaskDeps::read_set` above.
const LINEAR_SCAN_MAX: usize = 16;
#[inline]
fn new(#[cfg(debug_assertions)] node: Option<DepNode>, read_set_capacity: usize) -> Self {
TaskDeps {
#[cfg(debug_assertions)]
node,
reads: EdgesVec::new(),
read_set: FxHashSet::with_capacity_and_hasher(read_set_capacity, Default::default()),
}
}
}
// A data structure that stores Option<DepNodeColor> values as a contiguous
// array, using one u32 per entry.
pub(super) struct DepNodeColorMap {
values: IndexVec<SerializedDepNodeIndex, AtomicU32>,
}
// All values below `COMPRESSED_RED` are green.
const COMPRESSED_RED: u32 = u32::MAX - 1;
const COMPRESSED_UNKNOWN: u32 = u32::MAX;
impl DepNodeColorMap {
fn new(size: usize) -> DepNodeColorMap {
debug_assert!(COMPRESSED_RED > DepNodeIndex::MAX_AS_U32);
DepNodeColorMap { values: (0..size).map(|_| AtomicU32::new(COMPRESSED_UNKNOWN)).collect() }
}
#[inline]
pub(super) fn current(&self, index: SerializedDepNodeIndex) -> Option<DepNodeIndex> {
let value = self.values[index].load(Ordering::Relaxed);
if value <= DepNodeIndex::MAX_AS_U32 { Some(DepNodeIndex::from_u32(value)) } else { None }
}
/// Atomically sets the color of a previous-session dep node to either green
/// or red, if it has not already been colored.
///
/// If the node already has a color, the new color is ignored, and the
/// return value indicates the existing color.
#[inline(always)]
pub(super) fn try_set_color(
&self,
prev_index: SerializedDepNodeIndex,
color: DesiredColor,
) -> TrySetColorResult {
match self.values[prev_index].compare_exchange(
COMPRESSED_UNKNOWN,
match color {
DesiredColor::Red => COMPRESSED_RED,
DesiredColor::Green { index } => index.as_u32(),
},
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => TrySetColorResult::Success,
Err(COMPRESSED_RED) => TrySetColorResult::AlreadyRed,
Err(index) => TrySetColorResult::AlreadyGreen { index: DepNodeIndex::from_u32(index) },
}
}
#[inline]
pub(super) fn get(&self, index: SerializedDepNodeIndex) -> DepNodeColor {
let value = self.values[index].load(Ordering::Acquire);
// Green is by far the most common case. Check for that first so we can succeed with a
// single comparison.
if value < COMPRESSED_RED {
DepNodeColor::Green(DepNodeIndex::from_u32(value))
} else if value == COMPRESSED_RED {
DepNodeColor::Red
} else {
debug_assert_eq!(value, COMPRESSED_UNKNOWN);
DepNodeColor::Unknown
}
}
}
/// The color that [`DepNodeColorMap::try_set_color`] should try to apply to a node.
#[derive(Clone, Copy, Debug)]
pub(super) enum DesiredColor {
/// Try to mark the node red.
Red,
/// Try to mark the node green, associating it with a current-session node index.
Green { index: DepNodeIndex },
}
/// Return value of [`DepNodeColorMap::try_set_color`], indicating success or failure,
/// and (on failure) what the existing color is.
#[derive(Clone, Copy, Debug)]
pub(super) enum TrySetColorResult {
/// The [`DesiredColor`] was freshly applied to the node.
Success,
/// Coloring failed because the node was already marked red.
AlreadyRed,
/// Coloring failed because the node was already marked green,
/// and corresponds to node `index` in the current-session dep graph.
AlreadyGreen { index: DepNodeIndex },
}
#[inline(never)]
#[cold]
pub(crate) fn print_markframe_trace(graph: &DepGraph, frame: &MarkFrame<'_>) {
let data = graph.data.as_ref().unwrap();
eprintln!("there was a panic while trying to force a dep node");
eprintln!("try_mark_green dep node stack:");
let mut i = 0;
let mut current = Some(frame);
while let Some(frame) = current {
let node = data.previous.index_to_node(frame.index);
eprintln!("#{i} {node:?}");
current = frame.parent;
i += 1;
}
eprintln!("end of try_mark_green dep node stack");
}
#[cold]
#[inline(never)]
fn panic_on_forbidden_read(data: &DepGraphData, dep_node_index: DepNodeIndex) -> ! {
// We have to do an expensive reverse-lookup of the DepNode that
// corresponds to `dep_node_index`, but that's OK since we are about
// to ICE anyway.
let mut dep_node = None;
// First try to find the dep node among those that already existed in the
// previous session and has been marked green
for prev_index in data.colors.values.indices() {
if data.colors.current(prev_index) == Some(dep_node_index) {
dep_node = Some(*data.previous.index_to_node(prev_index));
break;
}
}
if dep_node.is_none()
&& let Some(nodes) = &data.current.nodes_in_current_session
{
// Try to find it among the nodes allocated so far in this session
// This is OK, there's only ever one node result possible so this is deterministic.
#[allow(rustc::potential_query_instability)]
if let Some((node, _)) = nodes.lock().iter().find(|&(_, index)| *index == dep_node_index) {
dep_node = Some(*node);
}
}
let dep_node = dep_node.map_or_else(
|| format!("with index {:?}", dep_node_index),
|dep_node| format!("`{:?}`", dep_node),
);
panic!(
"Error: trying to record dependency on DepNode {dep_node} in a \
context that does not allow it (e.g. during query deserialization). \
The most common case of recording a dependency on a DepNode `foo` is \
when the corresponding query `foo` is invoked. Invoking queries is not \
allowed as part of loading something from the incremental on-disk cache. \
See <https://github.com/rust-lang/rust/pull/91919>."
)
}
impl<'tcx> TyCtxt<'tcx> {
/// Return whether this kind always require evaluation.
#[inline(always)]
fn is_eval_always(self, kind: DepKind) -> bool {
self.dep_kind_vtable(kind).is_eval_always
}
}