Auto merge of #79589 - tgnottingham:shared_dep_graph, r=michaelwoerister

rustc_query_system: reduce dependency graph memory usage

This change implements, at a high level, two space optimizations to the dependency graph.

The first optimization is sharing graph data with the previous dependency graph. Whenever we intern a node, we know whether that node is new (not in the previous graph) or not, and if not, the color of the node in the previous graph.

Red and green nodes have their `DepNode` present in the previous graph, so for that piece of node data, we can just store the index of the node in the previous graph rather than duplicate the `DepNode`. Green nodes additionally have the the same result `Fingerprint`, so we can avoid duplicating that too. Finally, we distinguish between "light" and "dark" green nodes, where the latter are nodes that were marked green because all of their dependencies were marked green. These nodes can additionally share edges with the previous graph, because we know that their set of dependencies is the same (technically, light green and red nodes can have the same dependencies too, but we don't try to figure out whether or not that's the case).

Also, some effort is made to pack data tightly, and to avoid storing `DepNode`s as map keys more than once.

The second optimization is storing edges in a more compact representation, as in the `SerializedDepGraph`, that is, in a single vector, rather than one `EdgesVec` per node. An `EdgesVec` is a `SmallVec` with an inline buffer for 8 elements. Each `EdgesVec` is, at minimum, 40 bytes, and has a per-node overhead of up to 40 bytes. In the ideal case of exactly 8 edges, then 32 bytes are used for edges, and the overhead is 8 bytes. But most of the time, the overhead is higher.

In contrast, using a single vector to store all edges, and having each node specify its start and end elements as 4 byte indices into the vector has a constant overhead of 8 bytes--the best case scenario for the per-node `EdgesVec` approach.

The downside of this approach is that `EdgesVec`s built up during query execution have to be copied into the vector, whereas before, we could just take ownership over them. However, we mostly make up for this because the single vector representation enables a more efficient implementation of `DepGraph::serialize`.

3 files changed, 686 insertions, 246 deletions

diff --git a/compiler/rustc_query_system/src/dep_graph/graph.rs b/compiler/rustc_query_system/src/dep_graph/graph.rs
index d2f0e39ea6b..605d7ae4af6 100644
--- a/compiler/rustc_query_system/src/dep_graph/graph.rs
+++ b/compiler/rustc_query_system/src/dep_graph/graph.rs
@@ -3,7 +3,7 @@ use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use rustc_data_structures::profiling::QueryInvocationId;
 use rustc_data_structures::sharded::{self, Sharded};
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
-use rustc_data_structures::sync::{AtomicU32, AtomicU64, Lock, Lrc, Ordering};
+use rustc_data_structures::sync::{AtomicU32, AtomicU64, Lock, LockGuard, Lrc, Ordering};
 use rustc_data_structures::unlikely;
 use rustc_errors::Diagnostic;
 use rustc_index::vec::{Idx, IndexVec};
@@ -15,6 +15,7 @@ use std::env;
 use std::hash::Hash;
 use std::marker::PhantomData;
 use std::mem;
+use std::ops::Range;
 use std::sync::atomic::Ordering::Relaxed;
 
 use super::debug::EdgeFilter;
@@ -68,7 +69,7 @@ struct DepGraphData<K: DepKind> {
     /// 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.
+    /// current one anymore, but we do reference shared data to save space.
     current: CurrentDepGraph<K>,
 
     /// The dep-graph from the previous compilation session. It contains all
@@ -134,17 +135,61 @@ impl<K: DepKind> DepGraph<K> {
     }
 
     pub fn query(&self) -> DepGraphQuery<K> {
-        let data = self.data.as_ref().unwrap().current.data.lock();
-        let nodes: Vec<_> = data.iter().map(|n| n.node).collect();
-        let mut edges = Vec::new();
-        for (from, edge_targets) in data.iter().map(|d| (d.node, &d.edges)) {
-            for &edge_target in edge_targets.iter() {
-                let to = data[edge_target].node;
-                edges.push((from, to));
+        let data = self.data.as_ref().unwrap();
+        let previous = &data.previous;
+
+        // Note locking order: `prev_index_to_index`, then `data`.
+        let prev_index_to_index = data.current.prev_index_to_index.lock();
+        let data = data.current.data.lock();
+        let node_count = data.hybrid_indices.len();
+        let edge_count = self.edge_count(&data);
+
+        let mut nodes = Vec::with_capacity(node_count);
+        let mut edge_list_indices = Vec::with_capacity(node_count);
+        let mut edge_list_data = Vec::with_capacity(edge_count);
+
+        // See `serialize` for notes on the approach used here.
+
+        edge_list_data.extend(data.unshared_edges.iter().map(|i| i.index()));
+
+        for &hybrid_index in data.hybrid_indices.iter() {
+            match hybrid_index.into() {
+                HybridIndex::New(new_index) => {
+                    nodes.push(data.new.nodes[new_index]);
+                    let edges = &data.new.edges[new_index];
+                    edge_list_indices.push((edges.start.index(), edges.end.index()));
+                }
+                HybridIndex::Red(red_index) => {
+                    nodes.push(previous.index_to_node(data.red.node_indices[red_index]));
+                    let edges = &data.red.edges[red_index];
+                    edge_list_indices.push((edges.start.index(), edges.end.index()));
+                }
+                HybridIndex::LightGreen(lg_index) => {
+                    nodes.push(previous.index_to_node(data.light_green.node_indices[lg_index]));
+                    let edges = &data.light_green.edges[lg_index];
+                    edge_list_indices.push((edges.start.index(), edges.end.index()));
+                }
+                HybridIndex::DarkGreen(prev_index) => {
+                    nodes.push(previous.index_to_node(prev_index));
+
+                    let edges_iter = previous
+                        .edge_targets_from(prev_index)
+                        .iter()
+                        .map(|&dst| prev_index_to_index[dst].unwrap().index());
+
+                    let start = edge_list_data.len();
+                    edge_list_data.extend(edges_iter);
+                    let end = edge_list_data.len();
+                    edge_list_indices.push((start, end));
+                }
             }
         }
 
-        DepGraphQuery::new(&nodes[..], &edges[..])
+        debug_assert_eq!(nodes.len(), node_count);
+        debug_assert_eq!(edge_list_indices.len(), node_count);
+        debug_assert_eq!(edge_list_data.len(), edge_count);
+
+        DepGraphQuery::new(&nodes[..], &edge_list_indices[..], &edge_list_data[..])
     }
 
     pub fn assert_ignored(&self) {
@@ -201,7 +246,6 @@ impl<K: DepKind> DepGraph<K> {
             key,
             cx,
             arg,
-            false,
             task,
             |_key| {
                 Some(TaskDeps {
@@ -212,7 +256,6 @@ impl<K: DepKind> DepGraph<K> {
                     phantom_data: PhantomData,
                 })
             },
-            |data, key, fingerprint, task| data.complete_task(key, task.unwrap(), fingerprint),
             hash_result,
         )
     }
@@ -222,66 +265,69 @@ impl<K: DepKind> DepGraph<K> {
         key: DepNode<K>,
         cx: Ctxt,
         arg: A,
-        no_tcx: bool,
         task: fn(Ctxt, A) -> R,
         create_task: fn(DepNode<K>) -> Option<TaskDeps<K>>,
-        finish_task_and_alloc_depnode: fn(
-            &CurrentDepGraph<K>,
-            DepNode<K>,
-            Fingerprint,
-            Option<TaskDeps<K>>,
-        ) -> DepNodeIndex,
         hash_result: impl FnOnce(&mut Ctxt::StableHashingContext, &R) -> Option<Fingerprint>,
     ) -> (R, DepNodeIndex) {
         if let Some(ref data) = self.data {
             let task_deps = create_task(key).map(Lock::new);
+            let result = K::with_deps(task_deps.as_ref(), || task(cx, arg));
+            let edges = task_deps.map_or_else(|| smallvec![], |lock| lock.into_inner().reads);
 
-            // In incremental mode, hash the result of the task. We don't
-            // do anything with the hash yet, but we are computing it
-            // anyway so that
-            //  - we make sure that the infrastructure works and
-            //  - we can get an idea of the runtime cost.
             let mut hcx = cx.create_stable_hashing_context();
-
-            let result = if no_tcx {
-                task(cx, arg)
-            } else {
-                K::with_deps(task_deps.as_ref(), || task(cx, arg))
-            };
-
             let current_fingerprint = hash_result(&mut hcx, &result);
 
-            let dep_node_index = finish_task_and_alloc_depnode(
-                &data.current,
-                key,
-                current_fingerprint.unwrap_or(Fingerprint::ZERO),
-                task_deps.map(|lock| lock.into_inner()),
-            );
-
             let print_status = cfg!(debug_assertions) && cx.debug_dep_tasks();
 
-            // Determine the color of the new DepNode.
-            if let Some(prev_index) = data.previous.node_to_index_opt(&key) {
-                let prev_fingerprint = data.previous.fingerprint_by_index(prev_index);
-
-                let color = if let Some(current_fingerprint) = current_fingerprint {
-                    if current_fingerprint == prev_fingerprint {
+            // Intern the new `DepNode`.
+            let dep_node_index = if let Some(prev_index) = data.previous.node_to_index_opt(&key) {
+                // Determine the color and index of the new `DepNode`.
+                let (color, dep_node_index) = if let Some(current_fingerprint) = current_fingerprint
+                {
+                    if current_fingerprint == data.previous.fingerprint_by_index(prev_index) {
                         if print_status {
                             eprintln!("[task::green] {:?}", key);
                         }
-                        DepNodeColor::Green(dep_node_index)
+
+                        // This is a light green node: it existed in the previous compilation,
+                        // its query was re-executed, and it has the same result as before.
+                        let dep_node_index =
+                            data.current.intern_light_green_node(&data.previous, prev_index, edges);
+
+                        (DepNodeColor::Green(dep_node_index), dep_node_index)
                     } else {
                         if print_status {
                             eprintln!("[task::red] {:?}", key);
                         }
-                        DepNodeColor::Red
+
+                        // This is a red node: it existed in the previous compilation, its query
+                        // was re-executed, but it has a different result from before.
+                        let dep_node_index = data.current.intern_red_node(
+                            &data.previous,
+                            prev_index,
+                            edges,
+                            current_fingerprint,
+                        );
+
+                        (DepNodeColor::Red, dep_node_index)
                     }
                 } else {
                     if print_status {
                         eprintln!("[task::unknown] {:?}", key);
                     }
-                    // Mark the node as Red if we can't hash the result
-                    DepNodeColor::Red
+
+                    // 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.
+                    let dep_node_index = data.current.intern_red_node(
+                        &data.previous,
+                        prev_index,
+                        edges,
+                        Fingerprint::ZERO,
+                    );
+
+                    (DepNodeColor::Red, dep_node_index)
                 };
 
                 debug_assert!(
@@ -292,12 +338,27 @@ impl<K: DepKind> DepGraph<K> {
                 );
 
                 data.colors.insert(prev_index, color);
-            } else if print_status {
-                eprintln!("[task::new] {:?}", key);
-            }
+                dep_node_index
+            } else {
+                if print_status {
+                    eprintln!("[task::new] {:?}", key);
+                }
+
+                // This is a new node: it didn't exist in the previous compilation session.
+                data.current.intern_new_node(
+                    &data.previous,
+                    key,
+                    edges,
+                    current_fingerprint.unwrap_or(Fingerprint::ZERO),
+                )
+            };
 
             (result, dep_node_index)
         } 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.
             (task(cx, arg), self.next_virtual_depnode_index())
         }
     }
@@ -308,13 +369,36 @@ impl<K: DepKind> DepGraph<K> {
     where
         OP: FnOnce() -> R,
     {
+        debug_assert!(!dep_kind.is_eval_always());
+
         if let Some(ref data) = self.data {
             let task_deps = Lock::new(TaskDeps::default());
-
             let result = K::with_deps(Some(&task_deps), op);
             let task_deps = task_deps.into_inner();
 
-            let dep_node_index = data.current.complete_anon_task(dep_kind, task_deps);
+            // 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();
+            task_deps.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).
+                hash: data.current.anon_id_seed.combine(hasher.finish()).into(),
+            };
+
+            let dep_node_index = data.current.intern_new_node(
+                &data.previous,
+                target_dep_node,
+                task_deps.reads,
+                Fingerprint::ZERO,
+            );
+
             (result, dep_node_index)
         } else {
             (op(), self.next_virtual_depnode_index())
@@ -331,69 +415,106 @@ impl<K: DepKind> DepGraph<K> {
         task: fn(Ctxt, A) -> R,
         hash_result: impl FnOnce(&mut Ctxt::StableHashingContext, &R) -> Option<Fingerprint>,
     ) -> (R, DepNodeIndex) {
-        self.with_task_impl(
-            key,
-            cx,
-            arg,
-            false,
-            task,
-            |_| None,
-            |data, key, fingerprint, _| data.alloc_node(key, smallvec![], fingerprint),
-            hash_result,
-        )
+        self.with_task_impl(key, cx, arg, task, |_| None, hash_result)
     }
 
     #[inline]
-    pub fn read(&self, v: DepNode<K>) {
+    pub fn read_index(&self, dep_node_index: DepNodeIndex) {
         if let Some(ref data) = self.data {
-            let map = data.current.node_to_node_index.get_shard_by_value(&v).lock();
-            if let Some(dep_node_index) = map.get(&v).copied() {
-                std::mem::drop(map);
-                data.read_index(dep_node_index);
-            } else {
-                panic!("DepKind {:?} should be pre-allocated but isn't.", v.kind)
-            }
+            K::read_deps(|task_deps| {
+                if let Some(task_deps) = task_deps {
+                    let mut task_deps = task_deps.lock();
+                    let task_deps = &mut *task_deps;
+                    if cfg!(debug_assertions) {
+                        data.current.total_read_count.fetch_add(1, Relaxed);
+                    }
+
+                    // As long as we only have a low number of reads we can avoid doing a hash
+                    // insert and potentially allocating/reallocating the hashmap
+                    let new_read = if task_deps.reads.len() < TASK_DEPS_READS_CAP {
+                        task_deps.reads.iter().all(|other| *other != 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() == TASK_DEPS_READS_CAP {
+                            // Fill `read_set` with what we have so far so we can use the hashset
+                            // next time
+                            task_deps.read_set.extend(task_deps.reads.iter().copied());
+                        }
+
+                        #[cfg(debug_assertions)]
+                        {
+                            if let Some(target) = task_deps.node {
+                                if let Some(ref forbidden_edge) = data.current.forbidden_edge {
+                                    let src = self.dep_node_of(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, Relaxed);
+                    }
+                }
+            })
         }
     }
 
     #[inline]
-    pub fn read_index(&self, dep_node_index: DepNodeIndex) {
-        if let Some(ref data) = self.data {
-            data.read_index(dep_node_index);
-        }
+    pub fn dep_node_index_of(&self, dep_node: &DepNode<K>) -> DepNodeIndex {
+        self.dep_node_index_of_opt(dep_node).unwrap()
     }
 
     #[inline]
-    pub fn dep_node_index_of(&self, dep_node: &DepNode<K>) -> DepNodeIndex {
-        self.data
-            .as_ref()
-            .unwrap()
-            .current
-            .node_to_node_index
-            .get_shard_by_value(dep_node)
-            .lock()
-            .get(dep_node)
-            .cloned()
-            .unwrap()
+    pub fn dep_node_index_of_opt(&self, dep_node: &DepNode<K>) -> Option<DepNodeIndex> {
+        let data = self.data.as_ref().unwrap();
+        let current = &data.current;
+
+        if let Some(prev_index) = data.previous.node_to_index_opt(dep_node) {
+            current.prev_index_to_index.lock()[prev_index]
+        } else {
+            current.new_node_to_index.get_shard_by_value(dep_node).lock().get(dep_node).copied()
+        }
     }
 
     #[inline]
     pub fn dep_node_exists(&self, dep_node: &DepNode<K>) -> bool {
-        if let Some(ref data) = self.data {
-            data.current
-                .node_to_node_index
-                .get_shard_by_value(&dep_node)
-                .lock()
-                .contains_key(dep_node)
-        } else {
-            false
+        self.data.is_some() && self.dep_node_index_of_opt(dep_node).is_some()
+    }
+
+    #[inline]
+    pub fn dep_node_of(&self, dep_node_index: DepNodeIndex) -> DepNode<K> {
+        let data = self.data.as_ref().unwrap();
+        let previous = &data.previous;
+        let data = data.current.data.lock();
+
+        match data.hybrid_indices[dep_node_index].into() {
+            HybridIndex::New(new_index) => data.new.nodes[new_index],
+            HybridIndex::Red(red_index) => previous.index_to_node(data.red.node_indices[red_index]),
+            HybridIndex::LightGreen(light_green_index) => {
+                previous.index_to_node(data.light_green.node_indices[light_green_index])
+            }
+            HybridIndex::DarkGreen(prev_index) => previous.index_to_node(prev_index),
         }
     }
 
     #[inline]
     pub fn fingerprint_of(&self, dep_node_index: DepNodeIndex) -> Fingerprint {
-        let data = self.data.as_ref().expect("dep graph enabled").current.data.lock();
-        data[dep_node_index].fingerprint
+        let data = self.data.as_ref().unwrap();
+        let previous = &data.previous;
+        let data = data.current.data.lock();
+
+        match data.hybrid_indices[dep_node_index].into() {
+            HybridIndex::New(new_index) => data.new.fingerprints[new_index],
+            HybridIndex::Red(red_index) => data.red.fingerprints[red_index],
+            HybridIndex::LightGreen(light_green_index) => {
+                previous.fingerprint_by_index(data.light_green.node_indices[light_green_index])
+            }
+            HybridIndex::DarkGreen(prev_index) => previous.fingerprint_by_index(prev_index),
+        }
     }
 
     pub fn prev_fingerprint_of(&self, dep_node: &DepNode<K>) -> Option<Fingerprint> {
@@ -443,30 +564,95 @@ impl<K: DepKind> DepGraph<K> {
         }
     }
 
-    pub fn serialize(&self) -> SerializedDepGraph<K> {
-        let data = self.data.as_ref().unwrap().current.data.lock();
+    fn edge_count(&self, node_data: &LockGuard<'_, DepNodeData<K>>) -> usize {
+        let data = self.data.as_ref().unwrap();
+        let previous = &data.previous;
 
-        let fingerprints: IndexVec<SerializedDepNodeIndex, _> =
-            data.iter().map(|d| d.fingerprint).collect();
-        let nodes: IndexVec<SerializedDepNodeIndex, _> = data.iter().map(|d| d.node).collect();
+        let mut edge_count = node_data.unshared_edges.len();
 
-        let total_edge_count: usize = data.iter().map(|d| d.edges.len()).sum();
+        for &hybrid_index in node_data.hybrid_indices.iter() {
+            if let HybridIndex::DarkGreen(prev_index) = hybrid_index.into() {
+                edge_count += previous.edge_targets_from(prev_index).len()
+            }
+        }
 
-        let mut edge_list_indices = IndexVec::with_capacity(nodes.len());
-        let mut edge_list_data = Vec::with_capacity(total_edge_count);
+        edge_count
+    }
 
-        for (current_dep_node_index, edges) in data.iter_enumerated().map(|(i, d)| (i, &d.edges)) {
-            let start = edge_list_data.len() as u32;
-            // This should really just be a memcpy :/
-            edge_list_data.extend(edges.iter().map(|i| SerializedDepNodeIndex::new(i.index())));
-            let end = edge_list_data.len() as u32;
+    pub fn serialize(&self) -> SerializedDepGraph<K> {
+        type SDNI = SerializedDepNodeIndex;
 
-            debug_assert_eq!(current_dep_node_index.index(), edge_list_indices.len());
-            edge_list_indices.push((start, end));
+        let data = self.data.as_ref().unwrap();
+        let previous = &data.previous;
+
+        // Note locking order: `prev_index_to_index`, then `data`.
+        let prev_index_to_index = data.current.prev_index_to_index.lock();
+        let data = data.current.data.lock();
+        let node_count = data.hybrid_indices.len();
+        let edge_count = self.edge_count(&data);
+
+        let mut nodes = IndexVec::with_capacity(node_count);
+        let mut fingerprints = IndexVec::with_capacity(node_count);
+        let mut edge_list_indices = IndexVec::with_capacity(node_count);
+        let mut edge_list_data = Vec::with_capacity(edge_count);
+
+        // `rustc_middle::ty::query::OnDiskCache` expects nodes to be in
+        // `DepNodeIndex` order. The edges in `edge_list_data`, on the other
+        // hand, don't need to be in a particular order, as long as each node
+        // can reference its edges as a contiguous range within it. This is why
+        // we're able to copy `unshared_edges` directly into `edge_list_data`.
+        // It meets the above requirements, and each non-dark-green node already
+        // knows the range of edges to reference within it, which they'll push
+        // onto `edge_list_indices`. Dark green nodes, however, don't have their
+        // edges in `unshared_edges`, so need to add them to `edge_list_data`.
+
+        edge_list_data.extend(data.unshared_edges.iter().map(|i| SDNI::new(i.index())));
+
+        for &hybrid_index in data.hybrid_indices.iter() {
+            match hybrid_index.into() {
+                HybridIndex::New(i) => {
+                    let new = &data.new;
+                    nodes.push(new.nodes[i]);
+                    fingerprints.push(new.fingerprints[i]);
+                    let edges = &new.edges[i];
+                    edge_list_indices.push((edges.start.as_u32(), edges.end.as_u32()));
+                }
+                HybridIndex::Red(i) => {
+                    let red = &data.red;
+                    nodes.push(previous.index_to_node(red.node_indices[i]));
+                    fingerprints.push(red.fingerprints[i]);
+                    let edges = &red.edges[i];
+                    edge_list_indices.push((edges.start.as_u32(), edges.end.as_u32()));
+                }
+                HybridIndex::LightGreen(i) => {
+                    let lg = &data.light_green;
+                    nodes.push(previous.index_to_node(lg.node_indices[i]));
+                    fingerprints.push(previous.fingerprint_by_index(lg.node_indices[i]));
+                    let edges = &lg.edges[i];
+                    edge_list_indices.push((edges.start.as_u32(), edges.end.as_u32()));
+                }
+                HybridIndex::DarkGreen(prev_index) => {
+                    nodes.push(previous.index_to_node(prev_index));
+                    fingerprints.push(previous.fingerprint_by_index(prev_index));
+
+                    let edges_iter = previous
+                        .edge_targets_from(prev_index)
+                        .iter()
+                        .map(|&dst| prev_index_to_index[dst].as_ref().unwrap());
+
+                    let start = edge_list_data.len() as u32;
+                    edge_list_data.extend(edges_iter.map(|i| SDNI::new(i.index())));
+                    let end = edge_list_data.len() as u32;
+                    edge_list_indices.push((start, end));
+                }
+            }
         }
 
+        debug_assert_eq!(nodes.len(), node_count);
+        debug_assert_eq!(fingerprints.len(), node_count);
+        debug_assert_eq!(edge_list_indices.len(), node_count);
+        debug_assert_eq!(edge_list_data.len(), edge_count);
         debug_assert!(edge_list_data.len() <= u32::MAX as usize);
-        debug_assert_eq!(edge_list_data.len(), total_edge_count);
 
         SerializedDepGraph { nodes, fingerprints, edge_list_indices, edge_list_data }
     }
@@ -540,14 +726,7 @@ impl<K: DepKind> DepGraph<K> {
 
         #[cfg(not(parallel_compiler))]
         {
-            debug_assert!(
-                !data
-                    .current
-                    .node_to_node_index
-                    .get_shard_by_value(dep_node)
-                    .lock()
-                    .contains_key(dep_node)
-            );
+            debug_assert!(!self.dep_node_exists(dep_node));
             debug_assert!(data.colors.get(prev_dep_node_index).is_none());
         }
 
@@ -558,13 +737,11 @@ impl<K: DepKind> DepGraph<K> {
 
         let prev_deps = data.previous.edge_targets_from(prev_dep_node_index);
 
-        let mut current_deps = SmallVec::new();
-
         for &dep_dep_node_index in prev_deps {
             let dep_dep_node_color = data.colors.get(dep_dep_node_index);
 
             match dep_dep_node_color {
-                Some(DepNodeColor::Green(node_index)) => {
+                Some(DepNodeColor::Green(_)) => {
                     // This dependency has been marked as green before, we are
                     // still fine and can continue with checking the other
                     // dependencies.
@@ -574,7 +751,6 @@ impl<K: DepKind> DepGraph<K> {
                         dep_node,
                         data.previous.index_to_node(dep_dep_node_index)
                     );
-                    current_deps.push(node_index);
                 }
                 Some(DepNodeColor::Red) => {
                     // We found a dependency the value of which has changed
@@ -607,13 +783,12 @@ impl<K: DepKind> DepGraph<K> {
                             dep_dep_node_index,
                             dep_dep_node,
                         );
-                        if let Some(node_index) = node_index {
+                        if node_index.is_some() {
                             debug!(
                                 "try_mark_previous_green({:?}) --- managed to MARK \
                                     dependency {:?} as green",
                                 dep_node, dep_dep_node
                             );
-                            current_deps.push(node_index);
                             continue;
                         }
                     }
@@ -628,13 +803,12 @@ impl<K: DepKind> DepGraph<K> {
                         let dep_dep_node_color = data.colors.get(dep_dep_node_index);
 
                         match dep_dep_node_color {
-                            Some(DepNodeColor::Green(node_index)) => {
+                            Some(DepNodeColor::Green(_)) => {
                                 debug!(
                                     "try_mark_previous_green({:?}) --- managed to \
                                         FORCE dependency {:?} to green",
                                     dep_node, dep_dep_node
                                 );
-                                current_deps.push(node_index);
                             }
                             Some(DepNodeColor::Red) => {
                                 debug!(
@@ -690,13 +864,9 @@ impl<K: DepKind> DepGraph<K> {
         // There may be multiple threads trying to mark the same dep node green concurrently
 
         let dep_node_index = {
-            // Copy the fingerprint from the previous graph,
-            // so we don't have to recompute it
-            let fingerprint = data.previous.fingerprint_by_index(prev_dep_node_index);
-
             // We allocating an entry for the node in the current dependency graph and
             // adding all the appropriate edges imported from the previous graph
-            data.current.intern_node(*dep_node, current_deps, fingerprint)
+            data.current.intern_dark_green_node(&data.previous, prev_dep_node_index)
         };
 
         // ... emitting any stored diagnostic ...
@@ -871,31 +1041,234 @@ pub struct WorkProduct {
     pub saved_file: Option<String>,
 }
 
-#[derive(Clone)]
+// The maximum value of the follow index types leaves the upper two bits unused
+// so that we can store multiple index types in `CompressedHybridIndex`, and use
+// those bits to encode which index type it contains.
+
+// Index type for `NewDepNodeData`.
+rustc_index::newtype_index! {
+    struct NewDepNodeIndex {
+        MAX = 0x7FFF_FFFF
+    }
+}
+
+// Index type for `RedDepNodeData`.
+rustc_index::newtype_index! {
+    struct RedDepNodeIndex {
+        MAX = 0x7FFF_FFFF
+    }
+}
+
+// Index type for `LightGreenDepNodeData`.
+rustc_index::newtype_index! {
+    struct LightGreenDepNodeIndex {
+        MAX = 0x7FFF_FFFF
+    }
+}
+
+/// Compressed representation of `HybridIndex` enum. Bits unused by the
+/// contained index types are used to encode which index type it contains.
+#[derive(Copy, Clone)]
+struct CompressedHybridIndex(u32);
+
+impl CompressedHybridIndex {
+    const NEW_TAG: u32 = 0b0000_0000_0000_0000_0000_0000_0000_0000;
+    const RED_TAG: u32 = 0b0100_0000_0000_0000_0000_0000_0000_0000;
+    const LIGHT_GREEN_TAG: u32 = 0b1000_0000_0000_0000_0000_0000_0000_0000;
+    const DARK_GREEN_TAG: u32 = 0b1100_0000_0000_0000_0000_0000_0000_0000;
+
+    const TAG_MASK: u32 = 0b1100_0000_0000_0000_0000_0000_0000_0000;
+    const INDEX_MASK: u32 = !Self::TAG_MASK;
+}
+
+impl From<NewDepNodeIndex> for CompressedHybridIndex {
+    #[inline]
+    fn from(index: NewDepNodeIndex) -> Self {
+        CompressedHybridIndex(Self::NEW_TAG | index.as_u32())
+    }
+}
+
+impl From<RedDepNodeIndex> for CompressedHybridIndex {
+    #[inline]
+    fn from(index: RedDepNodeIndex) -> Self {
+        CompressedHybridIndex(Self::RED_TAG | index.as_u32())
+    }
+}
+
+impl From<LightGreenDepNodeIndex> for CompressedHybridIndex {
+    #[inline]
+    fn from(index: LightGreenDepNodeIndex) -> Self {
+        CompressedHybridIndex(Self::LIGHT_GREEN_TAG | index.as_u32())
+    }
+}
+
+impl From<SerializedDepNodeIndex> for CompressedHybridIndex {
+    #[inline]
+    fn from(index: SerializedDepNodeIndex) -> Self {
+        CompressedHybridIndex(Self::DARK_GREEN_TAG | index.as_u32())
+    }
+}
+
+/// Contains an index into one of several node data collections. Elsewhere, we
+/// store `CompressedHyridIndex` instead of this to save space, but convert to
+/// this type during processing to take advantage of the enum match ergonomics.
+enum HybridIndex {
+    New(NewDepNodeIndex),
+    Red(RedDepNodeIndex),
+    LightGreen(LightGreenDepNodeIndex),
+    DarkGreen(SerializedDepNodeIndex),
+}
+
+impl From<CompressedHybridIndex> for HybridIndex {
+    #[inline]
+    fn from(hybrid_index: CompressedHybridIndex) -> Self {
+        let index = hybrid_index.0 & CompressedHybridIndex::INDEX_MASK;
+
+        match hybrid_index.0 & CompressedHybridIndex::TAG_MASK {
+            CompressedHybridIndex::NEW_TAG => HybridIndex::New(NewDepNodeIndex::from_u32(index)),
+            CompressedHybridIndex::RED_TAG => HybridIndex::Red(RedDepNodeIndex::from_u32(index)),
+            CompressedHybridIndex::LIGHT_GREEN_TAG => {
+                HybridIndex::LightGreen(LightGreenDepNodeIndex::from_u32(index))
+            }
+            CompressedHybridIndex::DARK_GREEN_TAG => {
+                HybridIndex::DarkGreen(SerializedDepNodeIndex::from_u32(index))
+            }
+            _ => unreachable!(),
+        }
+    }
+}
+
+// Index type for `DepNodeData`'s edges.
+rustc_index::newtype_index! {
+    struct EdgeIndex { .. }
+}
+
+/// Data for nodes in the current graph, divided into different collections
+/// based on their presence in the previous graph, and if present, their color.
+/// We divide nodes this way because different types of nodes are able to share
+/// more or less data with the previous graph.
+///
+/// To enable more sharing, we distinguish between two kinds of green nodes.
+/// Light green nodes are nodes in the previous graph that have been marked
+/// green because we re-executed their queries and the results were the same as
+/// in the previous session. Dark green nodes are nodes in the previous graph
+/// that have been marked green because we were able to mark all of their
+/// dependencies green.
+///
+/// Both light and dark green nodes can share the dep node and fingerprint with
+/// the previous graph, but for light green nodes, we can't be sure that the
+/// edges may be shared without comparing them against the previous edges, so we
+/// store them directly (an approach in which we compare edges with the previous
+/// edges to see if they can be shared was evaluated, but was not found to be
+/// very profitable).
+///
+/// For dark green nodes, we can share everything with the previous graph, which
+/// is why the `HybridIndex::DarkGreen` enum variant contains the index of the
+/// node in the previous graph, and why we don't have a separate collection for
+/// dark green node data--the collection is the `PreviousDepGraph` itself.
+///
+/// (Note that for dark green nodes, the edges in the previous graph
+/// (`SerializedDepNodeIndex`s) must be converted to edges in the current graph
+/// (`DepNodeIndex`s). `CurrentDepGraph` contains `prev_index_to_index`, which
+/// can perform this conversion. It should always be possible, as by definition,
+/// a dark green node is one whose dependencies from the previous session have
+/// all been marked green--which means `prev_index_to_index` contains them.)
+///
+/// Node data is stored in parallel vectors to eliminate the padding between
+/// elements that would be needed to satisfy alignment requirements of the
+/// structure that would contain all of a node's data. We could group tightly
+/// packing subsets of node data together and use fewer vectors, but for
+/// consistency's sake, we use separate vectors for each piece of data.
 struct DepNodeData<K> {
-    node: DepNode<K>,
-    edges: EdgesVec,
-    fingerprint: Fingerprint,
+    /// Data for nodes not in previous graph.
+    new: NewDepNodeData<K>,
+
+    /// Data for nodes in previous graph that have been marked red.
+    red: RedDepNodeData,
+
+    /// Data for nodes in previous graph that have been marked light green.
+    light_green: LightGreenDepNodeData,
+
+    // Edges for all nodes other than dark-green ones. Edges for each node
+    // occupy a contiguous region of this collection, which a node can reference
+    // using two indices. Storing edges this way rather than using an `EdgesVec`
+    // for each node reduces memory consumption by a not insignificant amount
+    // when compiling large crates. The downside is that we have to copy into
+    // this collection the edges from the `EdgesVec`s that are built up during
+    // query execution. But this is mostly balanced out by the more efficient
+    // implementation of `DepGraph::serialize` enabled by this representation.
+    unshared_edges: IndexVec<EdgeIndex, DepNodeIndex>,
+
+    /// Mapping from `DepNodeIndex` to an index into a collection above.
+    /// Indicates which of the above collections contains a node's data.
+    ///
+    /// This collection is wasteful in time and space during incr-full builds,
+    /// because for those, all nodes are new. However, the waste is relatively
+    /// small, and the maintenance cost of avoiding using this for incr-full
+    /// builds is somewhat high and prone to bugginess. It does not seem worth
+    /// it at the time of this writing, but we may want to revisit the idea.
+    hybrid_indices: IndexVec<DepNodeIndex, CompressedHybridIndex>,
+}
+
+/// Data for nodes not in previous graph. Since we cannot share any data with
+/// the previous graph, so we must store all of such a node's data here.
+struct NewDepNodeData<K> {
+    nodes: IndexVec<NewDepNodeIndex, DepNode<K>>,
+    edges: IndexVec<NewDepNodeIndex, Range<EdgeIndex>>,
+    fingerprints: IndexVec<NewDepNodeIndex, Fingerprint>,
+}
+
+/// Data for nodes in previous graph that have been marked red. We can share the
+/// dep node with the previous graph, but the edges may be different, and the
+/// fingerprint is known to be different, so we store the latter two directly.
+struct RedDepNodeData {
+    node_indices: IndexVec<RedDepNodeIndex, SerializedDepNodeIndex>,
+    edges: IndexVec<RedDepNodeIndex, Range<EdgeIndex>>,
+    fingerprints: IndexVec<RedDepNodeIndex, Fingerprint>,
 }
 
-/// `CurrentDepGraph` stores the dependency graph for the current session.
-/// It will be populated as we run queries or tasks.
+/// Data for nodes in previous graph that have been marked green because we
+/// re-executed their queries and the results were the same as in the previous
+/// session. We can share the dep node and the fingerprint with the previous
+/// graph, but the edges may be different, so we store them directly.
+struct LightGreenDepNodeData {
+    node_indices: IndexVec<LightGreenDepNodeIndex, SerializedDepNodeIndex>,
+    edges: IndexVec<LightGreenDepNodeIndex, Range<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 an index (`DepNodeIndex`).
-/// The data for each node is stored in its `DepNodeData`, found in the `data` field.
+/// The nodes in it are identified by a `DepNodeIndex`. Internally, this maps to
+/// a `HybridIndex`, which identifies which collection in the `data` field
+/// contains a node's data. Which collection is used for a node depends on
+/// whether the node was present in the `PreviousDepGraph`, and if so, the color
+/// of the node. Each type of node can share more or less data with the previous
+/// graph. When possible, we can store just the index of the node in the
+/// previous graph, rather than duplicating its data in our own collections.
+/// This is important, because these graph structures are some of the largest in
+/// the compiler.
 ///
-/// We never remove nodes from the graph: they are only added.
+/// For the same reason, we also avoid storing `DepNode`s more than once as map
+/// keys. The `new_node_to_index` map only contains nodes not in the previous
+/// graph, and we map nodes in the previous graph to indices via a two-step
+/// mapping. `PreviousDepGraph` 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 two locks internally. The `data` and `node_to_node_index` fields are
-/// locked separately. Operations that take a `DepNodeIndex` typically just access
-/// the data field.
+/// This struct uses three locks internally. The `data`, `new_node_to_index`,
+/// and `prev_index_to_index` fields are locked separately. Operations that take
+/// a `DepNodeIndex` typically just access the `data` field.
 ///
-/// The only operation that must manipulate both locks is adding new nodes, in which case
-/// we first acquire the `node_to_node_index` lock and then, once a new node is to be inserted,
-/// acquire the lock on `data.`
+/// We only need to manipulate at most two locks simultaneously:
+/// `new_node_to_index` and `data`, or `prev_index_to_index` and `data`. When
+/// manipulating both, we acquire `new_node_to_index` or `prev_index_to_index`
+/// first, and `data` second.
 pub(super) struct CurrentDepGraph<K> {
-    data: Lock<IndexVec<DepNodeIndex, DepNodeData<K>>>,
-    node_to_node_index: Sharded<FxHashMap<DepNode<K>, DepNodeIndex>>,
+    data: Lock<DepNodeData<K>>,
+    new_node_to_index: Sharded<FxHashMap<DepNode<K>, DepNodeIndex>>,
+    prev_index_to_index: Lock<IndexVec<SerializedDepNodeIndex, Option<DepNodeIndex>>>,
 
     /// 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`.
@@ -944,18 +1317,63 @@ impl<K: DepKind> CurrentDepGraph<K> {
 
         // Pre-allocate the dep node structures. We over-allocate a little so
         // that we hopefully don't have to re-allocate during this compilation
-        // session. The over-allocation is 2% plus a small constant to account
-        // for the fact that in very small crates 2% might not be enough.
-        let new_node_count_estimate = (prev_graph_node_count * 102) / 100 + 200;
+        // session. The over-allocation for new nodes is 2% plus a small
+        // constant to account for the fact that in very small crates 2% might
+        // not be enough. The allocation for red and green node data doesn't
+        // include a constant, as we don't want to allocate anything for these
+        // structures during full incremental builds, where they aren't used.
+        //
+        // These estimates are based on the distribution of node and edge counts
+        // seen in rustc-perf benchmarks, adjusted somewhat to account for the
+        // fact that these benchmarks aren't perfectly representative.
+        //
+        // FIXME Use a collection type that doesn't copy node and edge data and
+        // grow multiplicatively on reallocation. Without such a collection or
+        // solution having the same effect, there is a performance hazard here
+        // in both time and space, as growing these collections means copying a
+        // large amount of data and doubling already large buffer capacities. A
+        // solution for this will also mean that it's less important to get
+        // these estimates right.
+        let new_node_count_estimate = (prev_graph_node_count * 2) / 100 + 200;
+        let red_node_count_estimate = (prev_graph_node_count * 3) / 100;
+        let light_green_node_count_estimate = (prev_graph_node_count * 25) / 100;
+        let total_node_count_estimate = prev_graph_node_count + new_node_count_estimate;
+
+        let average_edges_per_node_estimate = 6;
+        let unshared_edge_count_estimate = average_edges_per_node_estimate
+            * (new_node_count_estimate + red_node_count_estimate + light_green_node_count_estimate);
+
+        // 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.
+        static_assert_size!(Option<DepNodeIndex>, 4);
 
         CurrentDepGraph {
-            data: Lock::new(IndexVec::with_capacity(new_node_count_estimate)),
-            node_to_node_index: Sharded::new(|| {
+            data: Lock::new(DepNodeData {
+                new: NewDepNodeData {
+                    nodes: IndexVec::with_capacity(new_node_count_estimate),
+                    edges: IndexVec::with_capacity(new_node_count_estimate),
+                    fingerprints: IndexVec::with_capacity(new_node_count_estimate),
+                },
+                red: RedDepNodeData {
+                    node_indices: IndexVec::with_capacity(red_node_count_estimate),
+                    edges: IndexVec::with_capacity(red_node_count_estimate),
+                    fingerprints: IndexVec::with_capacity(red_node_count_estimate),
+                },
+                light_green: LightGreenDepNodeData {
+                    node_indices: IndexVec::with_capacity(light_green_node_count_estimate),
+                    edges: IndexVec::with_capacity(light_green_node_count_estimate),
+                },
+                unshared_edges: IndexVec::with_capacity(unshared_edge_count_estimate),
+                hybrid_indices: IndexVec::with_capacity(total_node_count_estimate),
+            }),
+            new_node_to_index: Sharded::new(|| {
                 FxHashMap::with_capacity_and_hasher(
                     new_node_count_estimate / sharded::SHARDS,
                     Default::default(),
                 )
             }),
+            prev_index_to_index: Lock::new(IndexVec::from_elem_n(None, prev_graph_node_count)),
             anon_id_seed: stable_hasher.finish(),
             forbidden_edge,
             total_read_count: AtomicU64::new(0),
@@ -963,114 +1381,125 @@ impl<K: DepKind> CurrentDepGraph<K> {
         }
     }
 
-    fn complete_task(
+    fn intern_new_node(
         &self,
-        node: DepNode<K>,
-        task_deps: TaskDeps<K>,
+        prev_graph: &PreviousDepGraph<K>,
+        dep_node: DepNode<K>,
+        edges: EdgesVec,
         fingerprint: Fingerprint,
     ) -> DepNodeIndex {
-        self.alloc_node(node, task_deps.reads, fingerprint)
-    }
-
-    fn complete_anon_task(&self, kind: K, task_deps: TaskDeps<K>) -> DepNodeIndex {
-        debug_assert!(!kind.is_eval_always());
-
-        let mut hasher = StableHasher::new();
-
-        // 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.
-        task_deps.reads.hash(&mut hasher);
-
-        let target_dep_node = DepNode {
-            kind,
-
-            // Fingerprint::combine() is faster than sending Fingerprint
-            // through the StableHasher (at least as long as StableHasher
-            // is so slow).
-            hash: self.anon_id_seed.combine(hasher.finish()).into(),
-        };
+        debug_assert!(
+            prev_graph.node_to_index_opt(&dep_node).is_none(),
+            "node in previous graph should be interned using one \
+            of `intern_red_node`, `intern_light_green_node`, etc."
+        );
 
-        self.intern_node(target_dep_node, task_deps.reads, Fingerprint::ZERO)
+        match self.new_node_to_index.get_shard_by_value(&dep_node).lock().entry(dep_node) {
+            Entry::Occupied(entry) => *entry.get(),
+            Entry::Vacant(entry) => {
+                let data = &mut *self.data.lock();
+                let new_index = data.new.nodes.push(dep_node);
+                add_edges(&mut data.unshared_edges, &mut data.new.edges, edges);
+                data.new.fingerprints.push(fingerprint);
+                let dep_node_index = data.hybrid_indices.push(new_index.into());
+                entry.insert(dep_node_index);
+                dep_node_index
+            }
+        }
     }
 
-    fn alloc_node(
+    fn intern_red_node(
         &self,
-        dep_node: DepNode<K>,
+        prev_graph: &PreviousDepGraph<K>,
+        prev_index: SerializedDepNodeIndex,
         edges: EdgesVec,
         fingerprint: Fingerprint,
     ) -> DepNodeIndex {
-        debug_assert!(
-            !self.node_to_node_index.get_shard_by_value(&dep_node).lock().contains_key(&dep_node)
-        );
-        self.intern_node(dep_node, edges, fingerprint)
+        self.debug_assert_not_in_new_nodes(prev_graph, prev_index);
+
+        let mut prev_index_to_index = self.prev_index_to_index.lock();
+
+        match prev_index_to_index[prev_index] {
+            Some(dep_node_index) => dep_node_index,
+            None => {
+                let data = &mut *self.data.lock();
+                let red_index = data.red.node_indices.push(prev_index);
+                add_edges(&mut data.unshared_edges, &mut data.red.edges, edges);
+                data.red.fingerprints.push(fingerprint);
+                let dep_node_index = data.hybrid_indices.push(red_index.into());
+                prev_index_to_index[prev_index] = Some(dep_node_index);
+                dep_node_index
+            }
+        }
     }
 
-    fn intern_node(
+    fn intern_light_green_node(
         &self,
-        dep_node: DepNode<K>,
+        prev_graph: &PreviousDepGraph<K>,
+        prev_index: SerializedDepNodeIndex,
         edges: EdgesVec,
-        fingerprint: Fingerprint,
     ) -> DepNodeIndex {
-        match self.node_to_node_index.get_shard_by_value(&dep_node).lock().entry(dep_node) {
-            Entry::Occupied(entry) => *entry.get(),
-            Entry::Vacant(entry) => {
-                let mut data = self.data.lock();
-                let dep_node_index = DepNodeIndex::new(data.len());
-                data.push(DepNodeData { node: dep_node, edges, fingerprint });
-                entry.insert(dep_node_index);
+        self.debug_assert_not_in_new_nodes(prev_graph, prev_index);
+
+        let mut prev_index_to_index = self.prev_index_to_index.lock();
+
+        match prev_index_to_index[prev_index] {
+            Some(dep_node_index) => dep_node_index,
+            None => {
+                let data = &mut *self.data.lock();
+                let light_green_index = data.light_green.node_indices.push(prev_index);
+                add_edges(&mut data.unshared_edges, &mut data.light_green.edges, edges);
+                let dep_node_index = data.hybrid_indices.push(light_green_index.into());
+                prev_index_to_index[prev_index] = Some(dep_node_index);
                 dep_node_index
             }
         }
     }
-}
 
-impl<K: DepKind> DepGraphData<K> {
-    #[inline(never)]
-    fn read_index(&self, source: DepNodeIndex) {
-        K::read_deps(|task_deps| {
-            if let Some(task_deps) = task_deps {
-                let mut task_deps = task_deps.lock();
-                let task_deps = &mut *task_deps;
-                if cfg!(debug_assertions) {
-                    self.current.total_read_count.fetch_add(1, Relaxed);
-                }
+    fn intern_dark_green_node(
+        &self,
+        prev_graph: &PreviousDepGraph<K>,
+        prev_index: SerializedDepNodeIndex,
+    ) -> DepNodeIndex {
+        self.debug_assert_not_in_new_nodes(prev_graph, prev_index);
 
-                // As long as we only have a low number of reads we can avoid doing a hash
-                // insert and potentially allocating/reallocating the hashmap
-                let new_read = if task_deps.reads.len() < TASK_DEPS_READS_CAP {
-                    task_deps.reads.iter().all(|other| *other != source)
-                } else {
-                    task_deps.read_set.insert(source)
-                };
-                if new_read {
-                    task_deps.reads.push(source);
-                    if task_deps.reads.len() == TASK_DEPS_READS_CAP {
-                        // Fill `read_set` with what we have so far so we can use the hashset next
-                        // time
-                        task_deps.read_set.extend(task_deps.reads.iter().copied());
-                    }
+        let mut prev_index_to_index = self.prev_index_to_index.lock();
 
-                    #[cfg(debug_assertions)]
-                    {
-                        if let Some(target) = task_deps.node {
-                            let data = self.current.data.lock();
-                            if let Some(ref forbidden_edge) = self.current.forbidden_edge {
-                                let source = data[source].node;
-                                if forbidden_edge.test(&source, &target) {
-                                    panic!("forbidden edge {:?} -> {:?} created", source, target)
-                                }
-                            }
-                        }
-                    }
-                } else if cfg!(debug_assertions) {
-                    self.current.total_duplicate_read_count.fetch_add(1, Relaxed);
-                }
+        match prev_index_to_index[prev_index] {
+            Some(dep_node_index) => dep_node_index,
+            None => {
+                let mut data = self.data.lock();
+                let dep_node_index = data.hybrid_indices.push(prev_index.into());
+                prev_index_to_index[prev_index] = Some(dep_node_index);
+                dep_node_index
             }
-        })
+        }
     }
+
+    #[inline]
+    fn debug_assert_not_in_new_nodes(
+        &self,
+        prev_graph: &PreviousDepGraph<K>,
+        prev_index: SerializedDepNodeIndex,
+    ) {
+        let node = &prev_graph.index_to_node(prev_index);
+        debug_assert!(
+            !self.new_node_to_index.get_shard_by_value(node).lock().contains_key(node),
+            "node from previous graph present in new node collection"
+        );
+    }
+}
+
+#[inline]
+fn add_edges<I: Idx>(
+    edges: &mut IndexVec<EdgeIndex, DepNodeIndex>,
+    edge_indices: &mut IndexVec<I, Range<EdgeIndex>>,
+    new_edges: EdgesVec,
+) {
+    let start = edges.next_index();
+    edges.extend(new_edges);
+    let end = edges.next_index();
+    edge_indices.push(start..end);
 }
 
 /// The capacity of the `reads` field `SmallVec`
diff --git a/compiler/rustc_query_system/src/dep_graph/query.rs b/compiler/rustc_query_system/src/dep_graph/query.rs
index a27b716b95a..cc25d08cb54 100644
--- a/compiler/rustc_query_system/src/dep_graph/query.rs
+++ b/compiler/rustc_query_system/src/dep_graph/query.rs
@@ -9,17 +9,23 @@ pub struct DepGraphQuery<K> {
 }
 
 impl<K: DepKind> DepGraphQuery<K> {
-    pub fn new(nodes: &[DepNode<K>], edges: &[(DepNode<K>, DepNode<K>)]) -> DepGraphQuery<K> {
-        let mut graph = Graph::with_capacity(nodes.len(), edges.len());
+    pub fn new(
+        nodes: &[DepNode<K>],
+        edge_list_indices: &[(usize, usize)],
+        edge_list_data: &[usize],
+    ) -> DepGraphQuery<K> {
+        let mut graph = Graph::with_capacity(nodes.len(), edge_list_data.len());
         let mut indices = FxHashMap::default();
         for node in nodes {
             indices.insert(*node, graph.add_node(*node));
         }
 
-        for &(ref source, ref target) in edges {
-            let source = indices[source];
-            let target = indices[target];
-            graph.add_edge(source, target, ());
+        for (source, &(start, end)) in edge_list_indices.iter().enumerate() {
+            for &target in &edge_list_data[start..end] {
+                let source = indices[&nodes[source]];
+                let target = indices[&nodes[target]];
+                graph.add_edge(source, target, ());
+            }
         }
 
         DepGraphQuery { graph, indices }
diff --git a/compiler/rustc_query_system/src/dep_graph/serialized.rs b/compiler/rustc_query_system/src/dep_graph/serialized.rs
index 932c6d2a2f1..28e07406918 100644
--- a/compiler/rustc_query_system/src/dep_graph/serialized.rs
+++ b/compiler/rustc_query_system/src/dep_graph/serialized.rs
@@ -4,8 +4,13 @@ use super::{DepKind, DepNode};
 use rustc_data_structures::fingerprint::Fingerprint;
 use rustc_index::vec::IndexVec;
 
+// The maximum value of `SerializedDepNodeIndex` leaves the upper two bits
+// unused so that we can store multiple index types in `CompressedHybridIndex`,
+// and use those bits to encode which index type it contains.
 rustc_index::newtype_index! {
-    pub struct SerializedDepNodeIndex { .. }
+    pub struct SerializedDepNodeIndex {
+        MAX = 0x7FFF_FFFF
+    }
 }
 
 /// Data for use when recompiling the **current crate**.