Auto merge of #42537 - michaelwoerister:tcx-for-dep-node, r=nikomatsakis

incr.comp.: Make DepNode `Copy` and valid across compilation sessions

This PR moves `DepNode` to a representation that does not need retracing and thus simplifies comparing dep-graphs from different compilation sessions. The code also gets a lot simpler in many places, since we don't need the generic parameter on `DepNode` anymore.  See https://github.com/rust-lang/rust/issues/42294 for details.

~~NOTE: Only the last commit of this is new, the rest is already reviewed in https://github.com/rust-lang/rust/pull/42504.~~

This PR is almost done but there are some things I still want to do:
- [x] Add some module-level documentation to `dep_node.rs`, explaining especially what the `define_dep_nodes!()` macro is about.
- [x] Do another pass over the dep-graph loading logic. I suspect that we can get rid of building the `edges` map and also use arrays instead of hash maps in some places.

cc @rust-lang/compiler
r? @nikomatsakis

39 files changed, 1007 insertions, 785 deletions

diff --git a/src/librustc/dep_graph/debug.rs b/src/librustc/dep_graph/debug.rs
index 5b15c5e6717..e22552008d5 100644
--- a/src/librustc/dep_graph/debug.rs
+++ b/src/librustc/dep_graph/debug.rs
@@ -12,7 +12,6 @@
 
 use super::dep_node::DepNode;
 use std::error::Error;
-use std::fmt::Debug;
 
 /// A dep-node filter goes from a user-defined string to a query over
 /// nodes. Right now the format is like this:
@@ -39,7 +38,7 @@ impl DepNodeFilter {
     }
 
     /// Tests whether `node` meets the filter, returning true if so.
-    pub fn test<D: Clone + Debug>(&self, node: &DepNode<D>) -> bool {
+    pub fn test(&self, node: &DepNode) -> bool {
         let debug_str = format!("{:?}", node);
         self.text.split("&")
                  .map(|s| s.trim())
@@ -67,10 +66,10 @@ impl EdgeFilter {
         }
     }
 
-    pub fn test<D: Clone + Debug>(&self,
-                                  source: &DepNode<D>,
-                                  target: &DepNode<D>)
-                                  -> bool {
+    pub fn test(&self,
+                source: &DepNode,
+                target: &DepNode)
+                -> bool {
         self.source.test(source) && self.target.test(target)
     }
 }
diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index 1571cf344ed..3b6a7f87c13 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -8,79 +8,332 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use hir::def_id::CrateNum;
+
+//! This module defines the `DepNode` type which the compiler uses to represent
+//! nodes in the dependency graph. A `DepNode` consists of a `DepKind` (which
+//! specifies the kind of thing it represents, like a piece of HIR, MIR, etc)
+//! and a `Fingerprint`, a 128 bit hash value the exact meaning of which
+//! depends on the node's `DepKind`. Together, the kind and the fingerprint
+//! fully identify a dependency node, even across multiple compilation sessions.
+//! In other words, the value of the fingerprint does not depend on anything
+//! that is specific to a given compilation session, like an unpredictable
+//! interning key (e.g. NodeId, DefId, Symbol) or the numeric value of a
+//! pointer. The concept behind this could be compared to how git commit hashes
+//! uniquely identify a given commit and has a few advantages:
+//!
+//! * A `DepNode` can simply be serialized to disk and loaded in another session
+//!   without the need to do any "rebasing (like we have to do for Spans and
+//!   NodeIds) or "retracing" like we had to do for `DefId` in earlier
+//!   implementations of the dependency graph.
+//! * A `Fingerprint` is just a bunch of bits, which allows `DepNode` to
+//!   implement `Copy`, `Sync`, `Send`, `Freeze`, etc.
+//! * Since we just have a bit pattern, `DepNode` can be mapped from disk into
+//!   memory without any post-processing (e.g. "abomination-style" pointer
+//!   reconstruction).
+//! * Because a `DepNode` is self-contained, we can instantiate `DepNodes` that
+//!   refer to things that do not exist anymore. In previous implementations
+//!   `DepNode` contained a `DefId`. A `DepNode` referring to something that
+//!   had been removed between the previous and the current compilation session
+//!   could not be instantiated because the current compilation session
+//!   contained no `DefId` for thing that had been removed.
+//!
+//! `DepNode` definition happens in the `define_dep_nodes!()` macro. This macro
+//! defines the `DepKind` enum and a corresponding `DepConstructor` enum. The
+//! `DepConstructor` enum links a `DepKind` to the parameters that are needed at
+//! runtime in order to construct a valid `DepNode` fingerprint.
+//!
+//! Because the macro sees what parameters a given `DepKind` requires, it can
+//! "infer" some properties for each kind of `DepNode`:
+//!
+//! * Whether a `DepNode` of a given kind has any parameters at all. Some
+//!   `DepNode`s, like `Krate`, represent global concepts with only one value.
+//! * Whether it is possible, in principle, to reconstruct a query key from a
+//!   given `DepNode`. Many `DepKind`s only require a single `DefId` parameter,
+//!   in which case it is possible to map the node's fingerprint back to the
+//!   `DefId` it was computed from. In other cases, too much information gets
+//!   lost during fingerprint computation.
+//!
+//! The `DepConstructor` enum, together with `DepNode::new()` ensures that only
+//! valid `DepNode` instances can be constructed. For example, the API does not
+//! allow for constructing parameterless `DepNode`s with anything other
+//! than a zeroed out fingerprint. More generally speaking, it relieves the
+//! user of the `DepNode` API of having to know how to compute the expected
+//! fingerprint for a given set of node parameters.
+
+use hir::def_id::{CrateNum, DefId};
+use hir::map::DefPathHash;
+
 use ich::Fingerprint;
-use rustc_data_structures::stable_hasher::StableHasher;
-use std::fmt::Debug;
+use ty::TyCtxt;
+use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
+use ich::StableHashingContext;
 use std::hash::Hash;
 
-macro_rules! try_opt {
-    ($e:expr) => (
-        match $e {
-            Some(r) => r,
-            None => return None,
+// erase!() just makes tokens go away. It's used to specify which macro argument
+// is repeated (i.e. which sub-expression of the macro we are in) but don't need
+// to actually use any of the arguments.
+macro_rules! erase {
+    ($x:tt) => ({})
+}
+
+macro_rules! define_dep_nodes {
+    ($(
+        $variant:ident $(( $($tuple_arg:tt),* ))*
+                       $({ $($struct_arg_name:ident : $struct_arg_ty:ty),* })*
+      ),*
+    ) => (
+        #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash,
+                 RustcEncodable, RustcDecodable)]
+        pub enum DepKind {
+            $($variant),*
+        }
+
+        impl DepKind {
+            #[allow(unreachable_code)]
+            #[inline]
+            pub fn can_reconstruct_query_key(&self) -> bool {
+                match *self {
+                    $(
+                        DepKind :: $variant => {
+                            // tuple args
+                            $({
+                                return <( $($tuple_arg,)* ) as DepNodeParams>
+                                    ::CAN_RECONSTRUCT_QUERY_KEY;
+                            })*
+
+                            // struct args
+                            $({
+                                return <( $($struct_arg_ty,)* ) as DepNodeParams>
+                                    ::CAN_RECONSTRUCT_QUERY_KEY;
+                            })*
+
+                            true
+                        }
+                    )*
+                }
+            }
+
+            #[allow(unreachable_code)]
+            #[inline]
+            pub fn has_params(&self) -> bool {
+                match *self {
+                    $(
+                        DepKind :: $variant => {
+                            // tuple args
+                            $({
+                                $(erase!($tuple_arg);)*
+                                return true;
+                            })*
+
+                            // struct args
+                            $({
+                                $(erase!($struct_arg_name);)*
+                                return true;
+                            })*
+
+                            false
+                        }
+                    )*
+                }
+            }
+        }
+
+        pub enum DepConstructor {
+            $(
+                $variant $(( $($tuple_arg),* ))*
+                         $({ $($struct_arg_name : $struct_arg_ty),* })*
+            ),*
+        }
+
+        #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash,
+                 RustcEncodable, RustcDecodable)]
+        pub struct DepNode {
+            pub kind: DepKind,
+            pub hash: Fingerprint,
+        }
+
+        impl DepNode {
+            #[allow(unreachable_code, non_snake_case)]
+            pub fn new(tcx: TyCtxt, dep: DepConstructor) -> DepNode {
+                match dep {
+                    $(
+                        DepConstructor :: $variant $(( $($tuple_arg),* ))*
+                                                   $({ $($struct_arg_name),* })*
+                            =>
+                        {
+                            // tuple args
+                            $({
+                                let tupled_args = ( $($tuple_arg,)* );
+                                let hash = DepNodeParams::to_fingerprint(&tupled_args,
+                                                                         tcx);
+                                return DepNode {
+                                    kind: DepKind::$variant,
+                                    hash
+                                };
+                            })*
+
+                            // struct args
+                            $({
+                                let tupled_args = ( $($struct_arg_name,)* );
+                                let hash = DepNodeParams::to_fingerprint(&tupled_args,
+                                                                         tcx);
+                                return DepNode {
+                                    kind: DepKind::$variant,
+                                    hash
+                                };
+                            })*
+
+                            DepNode {
+                                kind: DepKind::$variant,
+                                hash: Fingerprint::zero(),
+                            }
+                        }
+                    )*
+                }
+            }
+
+            /// Construct a DepNode from the given DepKind and DefPathHash. This
+            /// method will assert that the given DepKind actually requires a
+            /// single DefId/DefPathHash parameter.
+            #[inline]
+            pub fn from_def_path_hash(kind: DepKind,
+                                      def_path_hash: DefPathHash)
+                                      -> DepNode {
+                assert!(kind.can_reconstruct_query_key() && kind.has_params());
+                DepNode {
+                    kind,
+                    hash: def_path_hash.0,
+                }
+            }
+
+            /// Create a new, parameterless DepNode. This method will assert
+            /// that the DepNode corresponding to the given DepKind actually
+            /// does not require any parameters.
+            #[inline]
+            pub fn new_no_params(kind: DepKind) -> DepNode {
+                assert!(!kind.has_params());
+                DepNode {
+                    kind,
+                    hash: Fingerprint::zero(),
+                }
+            }
+
+            /// Extract the DefId corresponding to this DepNode. This will work
+            /// if two conditions are met:
+            ///
+            /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
+            /// 2. the item that the DefPath refers to exists in the current tcx.
+            ///
+            /// Condition (1) is determined by the DepKind variant of the
+            /// DepNode. Condition (2) might not be fulfilled if a DepNode
+            /// refers to something from the previous compilation session that
+            /// has been removed.
+            #[inline]
+            pub fn extract_def_id(&self, tcx: TyCtxt) -> Option<DefId> {
+                if self.kind.can_reconstruct_query_key() {
+                    let def_path_hash = DefPathHash(self.hash);
+                    tcx.def_path_hash_to_def_id
+                       .as_ref()
+                       .unwrap()
+                       .get(&def_path_hash)
+                       .cloned()
+                } else {
+                    None
+                }
+            }
+
+            /// Used in testing
+            pub fn from_label_string(label: &str,
+                                     def_path_hash: DefPathHash)
+                                     -> Result<DepNode, ()> {
+                let kind = match label {
+                    $(
+                        stringify!($variant) => DepKind::$variant,
+                    )*
+                    _ => return Err(()),
+                };
+
+                if !kind.can_reconstruct_query_key() {
+                    return Err(());
+                }
+
+                if kind.has_params() {
+                    Ok(def_path_hash.to_dep_node(kind))
+                } else {
+                    Ok(DepNode::new_no_params(kind))
+                }
+            }
         }
-    )
+    );
+}
+
+impl DefPathHash {
+    #[inline]
+    pub fn to_dep_node(self, kind: DepKind) -> DepNode {
+        DepNode::from_def_path_hash(kind, self)
+    }
 }
 
-#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
-pub enum DepNode<D: Clone + Debug> {
-    // The `D` type is "how definitions are identified".
-    // During compilation, it is always `DefId`, but when serializing
-    // it is mapped to `DefPath`.
-
-    /// Represents the `Krate` as a whole (the `hir::Krate` value) (as
-    /// distinct from the krate module). This is basically a hash of
-    /// the entire krate, so if you read from `Krate` (e.g., by calling
-    /// `tcx.hir.krate()`), we will have to assume that any change
-    /// means that you need to be recompiled. This is because the
-    /// `Krate` value gives you access to all other items. To avoid
-    /// this fate, do not call `tcx.hir.krate()`; instead, prefer
-    /// wrappers like `tcx.visit_all_items_in_krate()`.  If there is no
-    /// suitable wrapper, you can use `tcx.dep_graph.ignore()` to gain
-    /// access to the krate, but you must remember to add suitable
-    /// edges yourself for the individual items that you read.
+impl DefId {
+    #[inline]
+    pub fn to_dep_node(self, tcx: TyCtxt, kind: DepKind) -> DepNode {
+        DepNode::from_def_path_hash(kind, tcx.def_path_hash(self))
+    }
+}
+
+define_dep_nodes!(
+    // Represents the `Krate` as a whole (the `hir::Krate` value) (as
+    // distinct from the krate module). This is basically a hash of
+    // the entire krate, so if you read from `Krate` (e.g., by calling
+    // `tcx.hir.krate()`), we will have to assume that any change
+    // means that you need to be recompiled. This is because the
+    // `Krate` value gives you access to all other items. To avoid
+    // this fate, do not call `tcx.hir.krate()`; instead, prefer
+    // wrappers like `tcx.visit_all_items_in_krate()`.  If there is no
+    // suitable wrapper, you can use `tcx.dep_graph.ignore()` to gain
+    // access to the krate, but you must remember to add suitable
+    // edges yourself for the individual items that you read.
     Krate,
 
-    /// Represents the HIR node with the given node-id
-    Hir(D),
+    // Represents the HIR node with the given node-id
+    Hir(DefId),
 
-    /// Represents the body of a function or method. The def-id is that of the
-    /// function/method.
-    HirBody(D),
+    // Represents the body of a function or method. The def-id is that of the
+    // function/method.
+    HirBody(DefId),
 
-    /// Represents the metadata for a given HIR node, typically found
-    /// in an extern crate.
-    MetaData(D),
+    // Represents the metadata for a given HIR node, typically found
+    // in an extern crate.
+    MetaData(DefId),
 
-    /// Represents some artifact that we save to disk. Note that these
-    /// do not have a def-id as part of their identifier.
+    // Represents some artifact that we save to disk. Note that these
+    // do not have a def-id as part of their identifier.
     WorkProduct(WorkProductId),
 
     // Represents different phases in the compiler.
-    RegionMaps(D),
+    RegionMaps(DefId),
     Coherence,
     Resolve,
-    CoherenceCheckTrait(D),
-    CoherenceCheckImpl(D),
-    CoherenceOverlapCheck(D),
-    CoherenceOverlapCheckSpecial(D),
+    CoherenceCheckTrait(DefId),
+    CoherenceCheckImpl(DefId),
+    CoherenceOverlapCheck(DefId),
+    CoherenceOverlapCheckSpecial(DefId),
     Variance,
     PrivacyAccessLevels(CrateNum),
 
     // Represents the MIR for a fn; also used as the task node for
     // things read/modify that MIR.
     MirKrate,
-    Mir(D),
-    MirShim(Vec<D>),
+    Mir(DefId),
+    MirShim(DefIdList),
 
     BorrowCheckKrate,
-    BorrowCheck(D),
-    RvalueCheck(D),
+    BorrowCheck(DefId),
+    RvalueCheck(DefId),
     Reachability,
     MirKeys,
     LateLintCheck,
-    TransCrateItem(D),
+    TransCrateItem(DefId),
     TransWriteMetadata,
     CrateVariances,
 
@@ -89,38 +342,38 @@ pub enum DepNode<D: Clone + Debug> {
     // nodes. Often we map multiple tables to the same node if there
     // is no point in distinguishing them (e.g., both the type and
     // predicates for an item wind up in `ItemSignature`).
-    AssociatedItems(D),
-    ItemSignature(D),
-    ItemVarianceConstraints(D),
-    ItemVariances(D),
-    IsForeignItem(D),
-    TypeParamPredicates((D, D)),
-    SizedConstraint(D),
-    DtorckConstraint(D),
-    AdtDestructor(D),
-    AssociatedItemDefIds(D),
-    InherentImpls(D),
+    AssociatedItems(DefId),
+    ItemSignature(DefId),
+    ItemVarianceConstraints(DefId),
+    ItemVariances(DefId),
+    IsForeignItem(DefId),
+    TypeParamPredicates { item_id: DefId, param_id: DefId },
+    SizedConstraint(DefId),
+    DtorckConstraint(DefId),
+    AdtDestructor(DefId),
+    AssociatedItemDefIds(DefId),
+    InherentImpls(DefId),
     TypeckBodiesKrate,
-    TypeckTables(D),
-    UsedTraitImports(D),
-    ConstEval(D),
-    SymbolName(D),
-    SpecializationGraph(D),
-    ObjectSafety(D),
-    IsCopy(D),
-    IsSized(D),
-    IsFreeze(D),
-    NeedsDrop(D),
-    Layout(D),
-
-    /// The set of impls for a given trait. Ultimately, it would be
-    /// nice to get more fine-grained here (e.g., to include a
-    /// simplified type), but we can't do that until we restructure the
-    /// HIR to distinguish the *header* of an impl from its body.  This
-    /// is because changes to the header may change the self-type of
-    /// the impl and hence would require us to be more conservative
-    /// than changes in the impl body.
-    TraitImpls(D),
+    TypeckTables(DefId),
+    UsedTraitImports(DefId),
+    ConstEval(DefId),
+    SymbolName(DefId),
+    SpecializationGraph(DefId),
+    ObjectSafety(DefId),
+    IsCopy(DefId),
+    IsSized(DefId),
+    IsFreeze(DefId),
+    NeedsDrop(DefId),
+    Layout(DefId),
+
+    // The set of impls for a given trait. Ultimately, it would be
+    // nice to get more fine-grained here (e.g., to include a
+    // simplified type), but we can't do that until we restructure the
+    // HIR to distinguish the *header* of an impl from its body.  This
+    // is because changes to the header may change the self-type of
+    // the impl and hence would require us to be more conservative
+    // than changes in the impl body.
+    TraitImpls(DefId),
 
     AllLocalTraitImpls,
 
@@ -129,184 +382,80 @@ pub enum DepNode<D: Clone + Debug> {
     // Otherwise the write into the map would be incorrectly
     // attributed to the first task that happened to fill the cache,
     // which would yield an overly conservative dep-graph.
-    TraitItems(D),
-    ReprHints(D),
-
-    /// Trait selection cache is a little funny. Given a trait
-    /// reference like `Foo: SomeTrait<Bar>`, there could be
-    /// arbitrarily many def-ids to map on in there (e.g., `Foo`,
-    /// `SomeTrait`, `Bar`). We could have a vector of them, but it
-    /// requires heap-allocation, and trait sel in general can be a
-    /// surprisingly hot path. So instead we pick two def-ids: the
-    /// trait def-id, and the first def-id in the input types. If there
-    /// is no def-id in the input types, then we use the trait def-id
-    /// again. So for example:
-    ///
-    /// - `i32: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Clone }`
-    /// - `u32: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Clone }`
-    /// - `Clone: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Clone }`
-    /// - `Vec<i32>: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Vec }`
-    /// - `String: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: String }`
-    /// - `Foo: Trait<Bar>` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
-    /// - `Foo: Trait<i32>` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
-    /// - `(Foo, Bar): Trait` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
-    /// - `i32: Trait<Foo>` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
-    ///
-    /// You can see that we map many trait refs to the same
-    /// trait-select node.  This is not a problem, it just means
-    /// imprecision in our dep-graph tracking.  The important thing is
-    /// that for any given trait-ref, we always map to the **same**
-    /// trait-select node.
-    TraitSelect { trait_def_id: D, input_def_id: D },
-
-    /// For proj. cache, we just keep a list of all def-ids, since it is
-    /// not a hotspot.
-    ProjectionCache { def_ids: Vec<D> },
-
-    ParamEnv(D),
-    DescribeDef(D),
-    DefSpan(D),
-    Stability(D),
-    Deprecation(D),
-    ItemBodyNestedBodies(D),
-    ConstIsRvaluePromotableToStatic(D),
-    ImplParent(D),
-    TraitOfItem(D),
-    IsExportedSymbol(D),
-    IsMirAvailable(D),
-    ItemAttrs(D),
-    FnArgNames(D),
+    TraitItems(DefId),
+    ReprHints(DefId),
+
+    // Trait selection cache is a little funny. Given a trait
+    // reference like `Foo: SomeTrait<Bar>`, there could be
+    // arbitrarily many def-ids to map on in there (e.g., `Foo`,
+    // `SomeTrait`, `Bar`). We could have a vector of them, but it
+    // requires heap-allocation, and trait sel in general can be a
+    // surprisingly hot path. So instead we pick two def-ids: the
+    // trait def-id, and the first def-id in the input types. If there
+    // is no def-id in the input types, then we use the trait def-id
+    // again. So for example:
+    //
+    // - `i32: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Clone }`
+    // - `u32: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Clone }`
+    // - `Clone: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Clone }`
+    // - `Vec<i32>: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Vec }`
+    // - `String: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: String }`
+    // - `Foo: Trait<Bar>` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
+    // - `Foo: Trait<i32>` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
+    // - `(Foo, Bar): Trait` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
+    // - `i32: Trait<Foo>` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
+    //
+    // You can see that we map many trait refs to the same
+    // trait-select node.  This is not a problem, it just means
+    // imprecision in our dep-graph tracking.  The important thing is
+    // that for any given trait-ref, we always map to the **same**
+    // trait-select node.
+    TraitSelect { trait_def_id: DefId, input_def_id: DefId },
+
+    // For proj. cache, we just keep a list of all def-ids, since it is
+    // not a hotspot.
+    ProjectionCache { def_ids: DefIdList },
+
+    ParamEnv(DefId),
+    DescribeDef(DefId),
+    DefSpan(DefId),
+    Stability(DefId),
+    Deprecation(DefId),
+    ItemBodyNestedBodies(DefId),
+    ConstIsRvaluePromotableToStatic(DefId),
+    ImplParent(DefId),
+    TraitOfItem(DefId),
+    IsExportedSymbol(DefId),
+    IsMirAvailable(DefId),
+    ItemAttrs(DefId),
+    FnArgNames(DefId)
+);
+
+trait DepNodeParams<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> {
+    const CAN_RECONSTRUCT_QUERY_KEY: bool;
+    fn to_fingerprint(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Fingerprint;
 }
 
-impl<D: Clone + Debug> DepNode<D> {
-    /// Used in testing
-    pub fn from_label_string(label: &str, data: D) -> Result<DepNode<D>, ()> {
-        macro_rules! check {
-            ($($name:ident,)*) => {
-                match label {
-                    $(stringify!($name) => Ok(DepNode::$name(data)),)*
-                    _ => Err(())
-                }
-            }
-        }
+impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a, T> DepNodeParams<'a, 'gcx, 'tcx> for T
+    where T: HashStable<StableHashingContext<'a, 'gcx, 'tcx>>
+{
+    default const CAN_RECONSTRUCT_QUERY_KEY: bool = false;
 
-        if label == "Krate" {
-            // special case
-            return Ok(DepNode::Krate);
-        }
+    default fn to_fingerprint(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Fingerprint {
+        let mut hcx = StableHashingContext::new(tcx);
+        let mut hasher = StableHasher::new();
 
-        check! {
-            BorrowCheck,
-            Hir,
-            HirBody,
-            TransCrateItem,
-            AssociatedItems,
-            ItemSignature,
-            ItemVariances,
-            IsForeignItem,
-            AssociatedItemDefIds,
-            InherentImpls,
-            TypeckTables,
-            UsedTraitImports,
-            TraitImpls,
-            ReprHints,
-        }
+        self.hash_stable(&mut hcx, &mut hasher);
+
+        hasher.finish()
     }
+}
 
-    pub fn map_def<E, OP>(&self, mut op: OP) -> Option<DepNode<E>>
-        where OP: FnMut(&D) -> Option<E>, E: Clone + Debug
-    {
-        use self::DepNode::*;
-
-        match *self {
-            Krate => Some(Krate),
-            BorrowCheckKrate => Some(BorrowCheckKrate),
-            MirKrate => Some(MirKrate),
-            TypeckBodiesKrate => Some(TypeckBodiesKrate),
-            Coherence => Some(Coherence),
-            CrateVariances => Some(CrateVariances),
-            Resolve => Some(Resolve),
-            Variance => Some(Variance),
-            PrivacyAccessLevels(k) => Some(PrivacyAccessLevels(k)),
-            Reachability => Some(Reachability),
-            MirKeys => Some(MirKeys),
-            LateLintCheck => Some(LateLintCheck),
-            TransWriteMetadata => Some(TransWriteMetadata),
-
-            // work product names do not need to be mapped, because
-            // they are always absolute.
-            WorkProduct(ref id) => Some(WorkProduct(id.clone())),
-
-            IsCopy(ref d) => op(d).map(IsCopy),
-            IsSized(ref d) => op(d).map(IsSized),
-            IsFreeze(ref d) => op(d).map(IsFreeze),
-            NeedsDrop(ref d) => op(d).map(NeedsDrop),
-            Layout(ref d) => op(d).map(Layout),
-            Hir(ref d) => op(d).map(Hir),
-            HirBody(ref d) => op(d).map(HirBody),
-            MetaData(ref d) => op(d).map(MetaData),
-            CoherenceCheckTrait(ref d) => op(d).map(CoherenceCheckTrait),
-            CoherenceCheckImpl(ref d) => op(d).map(CoherenceCheckImpl),
-            CoherenceOverlapCheck(ref d) => op(d).map(CoherenceOverlapCheck),
-            CoherenceOverlapCheckSpecial(ref d) => op(d).map(CoherenceOverlapCheckSpecial),
-            Mir(ref d) => op(d).map(Mir),
-            MirShim(ref def_ids) => {
-                let def_ids: Option<Vec<E>> = def_ids.iter().map(op).collect();
-                def_ids.map(MirShim)
-            }
-            BorrowCheck(ref d) => op(d).map(BorrowCheck),
-            RegionMaps(ref d) => op(d).map(RegionMaps),
-            RvalueCheck(ref d) => op(d).map(RvalueCheck),
-            TransCrateItem(ref d) => op(d).map(TransCrateItem),
-            AssociatedItems(ref d) => op(d).map(AssociatedItems),
-            ItemSignature(ref d) => op(d).map(ItemSignature),
-            ItemVariances(ref d) => op(d).map(ItemVariances),
-            ItemVarianceConstraints(ref d) => op(d).map(ItemVarianceConstraints),
-            IsForeignItem(ref d) => op(d).map(IsForeignItem),
-            TypeParamPredicates((ref item, ref param)) => {
-                Some(TypeParamPredicates((try_opt!(op(item)), try_opt!(op(param)))))
-            }
-            SizedConstraint(ref d) => op(d).map(SizedConstraint),
-            DtorckConstraint(ref d) => op(d).map(DtorckConstraint),
-            AdtDestructor(ref d) => op(d).map(AdtDestructor),
-            AssociatedItemDefIds(ref d) => op(d).map(AssociatedItemDefIds),
-            InherentImpls(ref d) => op(d).map(InherentImpls),
-            TypeckTables(ref d) => op(d).map(TypeckTables),
-            UsedTraitImports(ref d) => op(d).map(UsedTraitImports),
-            ConstEval(ref d) => op(d).map(ConstEval),
-            SymbolName(ref d) => op(d).map(SymbolName),
-            SpecializationGraph(ref d) => op(d).map(SpecializationGraph),
-            ObjectSafety(ref d) => op(d).map(ObjectSafety),
-            TraitImpls(ref d) => op(d).map(TraitImpls),
-            AllLocalTraitImpls => Some(AllLocalTraitImpls),
-            TraitItems(ref d) => op(d).map(TraitItems),
-            ReprHints(ref d) => op(d).map(ReprHints),
-            TraitSelect { ref trait_def_id, ref input_def_id } => {
-                op(trait_def_id).and_then(|trait_def_id| {
-                    op(input_def_id).and_then(|input_def_id| {
-                        Some(TraitSelect { trait_def_id: trait_def_id,
-                                           input_def_id: input_def_id })
-                    })
-                })
-            }
-            ProjectionCache { ref def_ids } => {
-                let def_ids: Option<Vec<E>> = def_ids.iter().map(op).collect();
-                def_ids.map(|d| ProjectionCache { def_ids: d })
-            }
-            ParamEnv(ref d) => op(d).map(ParamEnv),
-            DescribeDef(ref d) => op(d).map(DescribeDef),
-            DefSpan(ref d) => op(d).map(DefSpan),
-            Stability(ref d) => op(d).map(Stability),
-            Deprecation(ref d) => op(d).map(Deprecation),
-            ItemAttrs(ref d) => op(d).map(ItemAttrs),
-            FnArgNames(ref d) => op(d).map(FnArgNames),
-            ImplParent(ref d) => op(d).map(ImplParent),
-            TraitOfItem(ref d) => op(d).map(TraitOfItem),
-            IsExportedSymbol(ref d) => op(d).map(IsExportedSymbol),
-            ItemBodyNestedBodies(ref d) => op(d).map(ItemBodyNestedBodies),
-            ConstIsRvaluePromotableToStatic(ref d) => op(d).map(ConstIsRvaluePromotableToStatic),
-            IsMirAvailable(ref d) => op(d).map(IsMirAvailable),
-        }
+impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> DepNodeParams<'a, 'gcx, 'tcx> for (DefId,) {
+    const CAN_RECONSTRUCT_QUERY_KEY: bool = true;
+
+    fn to_fingerprint(&self, tcx: TyCtxt) -> Fingerprint {
+        tcx.def_path_hash(self.0).0
     }
 }
 
@@ -315,14 +464,38 @@ impl<D: Clone + Debug> DepNode<D> {
 /// some independent path or string that persists between runs without
 /// the need to be mapped or unmapped. (This ensures we can serialize
 /// them even in the absence of a tcx.)
-#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
-pub struct WorkProductId(pub Fingerprint);
+#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash,
+         RustcEncodable, RustcDecodable)]
+pub struct WorkProductId {
+    hash: Fingerprint
+}
 
 impl WorkProductId {
     pub fn from_cgu_name(cgu_name: &str) -> WorkProductId {
         let mut hasher = StableHasher::new();
         cgu_name.len().hash(&mut hasher);
         cgu_name.hash(&mut hasher);
-        WorkProductId(hasher.finish())
+        WorkProductId {
+            hash: hasher.finish()
+        }
+    }
+
+    pub fn from_fingerprint(fingerprint: Fingerprint) -> WorkProductId {
+        WorkProductId {
+            hash: fingerprint
+        }
+    }
+
+    pub fn to_dep_node(self) -> DepNode {
+        DepNode {
+            kind: DepKind::WorkProduct,
+            hash: self.hash,
+        }
     }
 }
+
+impl_stable_hash_for!(struct ::dep_graph::WorkProductId {
+    hash
+});
+
+type DefIdList = Vec<DefId>;
diff --git a/src/librustc/dep_graph/dep_tracking_map.rs b/src/librustc/dep_graph/dep_tracking_map.rs
index 7a246c814d3..43f8d6b938d 100644
--- a/src/librustc/dep_graph/dep_tracking_map.rs
+++ b/src/librustc/dep_graph/dep_tracking_map.rs
@@ -8,12 +8,11 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use hir::def_id::DefId;
 use rustc_data_structures::fx::FxHashMap;
 use std::cell::RefCell;
-use std::ops::Index;
 use std::hash::Hash;
 use std::marker::PhantomData;
+use ty::TyCtxt;
 use util::common::MemoizationMap;
 
 use super::{DepNode, DepGraph};
@@ -30,7 +29,7 @@ pub struct DepTrackingMap<M: DepTrackingMapConfig> {
 pub trait DepTrackingMapConfig {
     type Key: Eq + Hash + Clone;
     type Value: Clone;
-    fn to_dep_node(key: &Self::Key) -> DepNode<DefId>;
+    fn to_dep_node(tcx: TyCtxt, key: &Self::Key) -> DepNode;
 }
 
 impl<M: DepTrackingMapConfig> DepTrackingMap<M> {
@@ -44,18 +43,18 @@ impl<M: DepTrackingMapConfig> DepTrackingMap<M> {
 
     /// Registers a (synthetic) read from the key `k`. Usually this
     /// is invoked automatically by `get`.
-    fn read(&self, k: &M::Key) {
-        let dep_node = M::to_dep_node(k);
+    fn read(&self, tcx: TyCtxt, k: &M::Key) {
+        let dep_node = M::to_dep_node(tcx, k);
         self.graph.read(dep_node);
     }
 
-    pub fn get(&self, k: &M::Key) -> Option<&M::Value> {
-        self.read(k);
+    pub fn get(&self, tcx: TyCtxt, k: &M::Key) -> Option<&M::Value> {
+        self.read(tcx, k);
         self.map.get(k)
     }
 
-    pub fn contains_key(&self, k: &M::Key) -> bool {
-        self.read(k);
+    pub fn contains_key(&self, tcx: TyCtxt, k: &M::Key) -> bool {
+        self.read(tcx, k);
         self.map.contains_key(k)
     }
 
@@ -99,32 +98,22 @@ impl<M: DepTrackingMapConfig> MemoizationMap for RefCell<DepTrackingMap<M>> {
     /// The key is the line marked `(*)`: the closure implicitly
     /// accesses the body of the item `item`, so we register a read
     /// from `Hir(item_def_id)`.
-    fn memoize<OP>(&self, key: M::Key, op: OP) -> M::Value
+    fn memoize<OP>(&self, tcx: TyCtxt, key: M::Key, op: OP) -> M::Value
         where OP: FnOnce() -> M::Value
     {
         let graph;
         {
             let this = self.borrow();
             if let Some(result) = this.map.get(&key) {
-                this.read(&key);
+                this.read(tcx, &key);
                 return result.clone();
             }
             graph = this.graph.clone();
         }
 
-        let _task = graph.in_task(M::to_dep_node(&key));
+        let _task = graph.in_task(M::to_dep_node(tcx, &key));
         let result = op();
         self.borrow_mut().map.insert(key, result.clone());
         result
     }
 }
-
-impl<'k, M: DepTrackingMapConfig> Index<&'k M::Key> for DepTrackingMap<M> {
-    type Output = M::Value;
-
-    #[inline]
-    fn index(&self, k: &'k M::Key) -> &M::Value {
-        self.get(k).unwrap()
-    }
-}
-
diff --git a/src/librustc/dep_graph/edges.rs b/src/librustc/dep_graph/edges.rs
index 5dbabcc9230..a323e44d0d4 100644
--- a/src/librustc/dep_graph/edges.rs
+++ b/src/librustc/dep_graph/edges.rs
@@ -9,13 +9,11 @@
 // except according to those terms.
 
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
-use std::fmt::Debug;
-use std::hash::Hash;
 use super::{DepGraphQuery, DepNode};
 
-pub struct DepGraphEdges<D: Clone + Debug + Eq + Hash> {
-    nodes: Vec<DepNode<D>>,
-    indices: FxHashMap<DepNode<D>, IdIndex>,
+pub struct DepGraphEdges {
+    nodes: Vec<DepNode>,
+    indices: FxHashMap<DepNode, IdIndex>,
     edges: FxHashSet<(IdIndex, IdIndex)>,
     open_nodes: Vec<OpenNode>,
 }
@@ -42,8 +40,8 @@ enum OpenNode {
     Ignore,
 }
 
-impl<D: Clone + Debug + Eq + Hash> DepGraphEdges<D> {
-    pub fn new() -> DepGraphEdges<D> {
+impl DepGraphEdges {
+    pub fn new() -> DepGraphEdges {
         DepGraphEdges {
             nodes: vec![],
             indices: FxHashMap(),
@@ -52,12 +50,12 @@ impl<D: Clone + Debug + Eq + Hash> DepGraphEdges<D> {
         }
     }
 
-    fn id(&self, index: IdIndex) -> DepNode<D> {
+    fn id(&self, index: IdIndex) -> DepNode {
         self.nodes[index.index()].clone()
     }
 
     /// Creates a node for `id` in the graph.
-    fn make_node(&mut self, id: DepNode<D>) -> IdIndex {
+    fn make_node(&mut self, id: DepNode) -> IdIndex {
         if let Some(&i) = self.indices.get(&id) {
             return i;
         }
@@ -82,7 +80,7 @@ impl<D: Clone + Debug + Eq + Hash> DepGraphEdges<D> {
         assert_eq!(popped_node, OpenNode::Ignore);
     }
 
-    pub fn push_task(&mut self, key: DepNode<D>) {
+    pub fn push_task(&mut self, key: DepNode) {
         let top_node = self.current_node();
 
         let new_node = self.make_node(key);
@@ -95,7 +93,7 @@ impl<D: Clone + Debug + Eq + Hash> DepGraphEdges<D> {
         }
     }
 
-    pub fn pop_task(&mut self, key: DepNode<D>) {
+    pub fn pop_task(&mut self, key: DepNode) {
         let popped_node = self.open_nodes.pop().unwrap();
         assert_eq!(OpenNode::Node(self.indices[&key]), popped_node);
     }
@@ -105,7 +103,7 @@ impl<D: Clone + Debug + Eq + Hash> DepGraphEdges<D> {
     /// effect. Note that *reading* from tracked state is harmless if
     /// you are not in a task; what is bad is *writing* to tracked
     /// state (and leaking data that you read into a tracked task).
-    pub fn read(&mut self, v: DepNode<D>) {
+    pub fn read(&mut self, v: DepNode) {
         if self.current_node().is_some() {
             let source = self.make_node(v);
             self.add_edge_from_current_node(|current| (source, current))
@@ -115,7 +113,7 @@ impl<D: Clone + Debug + Eq + Hash> DepGraphEdges<D> {
     /// Indicates that the current task `C` writes `v` by adding an
     /// edge from `C` to `v`. If there is no current task, panics. If
     /// you want to suppress this edge, use `ignore`.
-    pub fn write(&mut self, v: DepNode<D>) {
+    pub fn write(&mut self, v: DepNode) {
         let target = self.make_node(v);
         self.add_edge_from_current_node(|current| (current, target))
     }
@@ -159,7 +157,7 @@ impl<D: Clone + Debug + Eq + Hash> DepGraphEdges<D> {
         }
     }
 
-    pub fn query(&self) -> DepGraphQuery<D> {
+    pub fn query(&self) -> DepGraphQuery {
         let edges: Vec<_> = self.edges.iter()
                                       .map(|&(i, j)| (self.id(i), self.id(j)))
                                       .collect();
diff --git a/src/librustc/dep_graph/graph.rs b/src/librustc/dep_graph/graph.rs
index dc482b0d6ac..6afd31bfe92 100644
--- a/src/librustc/dep_graph/graph.rs
+++ b/src/librustc/dep_graph/graph.rs
@@ -8,7 +8,6 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use hir::def_id::DefId;
 use rustc_data_structures::fx::FxHashMap;
 use session::config::OutputType;
 use std::cell::{Ref, RefCell};
@@ -57,7 +56,7 @@ impl DepGraph {
         self.data.thread.is_fully_enabled()
     }
 
-    pub fn query(&self) -> DepGraphQuery<DefId> {
+    pub fn query(&self) -> DepGraphQuery {
         self.data.thread.query()
     }
 
@@ -65,7 +64,7 @@ impl DepGraph {
         raii::IgnoreTask::new(&self.data.thread)
     }
 
-    pub fn in_task<'graph>(&'graph self, key: DepNode<DefId>) -> Option<raii::DepTask<'graph>> {
+    pub fn in_task<'graph>(&'graph self, key: DepNode) -> Option<raii::DepTask<'graph>> {
         raii::DepTask::new(&self.data.thread, key)
     }
 
@@ -103,14 +102,14 @@ impl DepGraph {
     ///   `arg` parameter.
     ///
     /// [README]: README.md
-    pub fn with_task<C, A, R>(&self, key: DepNode<DefId>, cx: C, arg: A, task: fn(C, A) -> R) -> R
+    pub fn with_task<C, A, R>(&self, key: DepNode, cx: C, arg: A, task: fn(C, A) -> R) -> R
         where C: DepGraphSafe, A: DepGraphSafe
     {
         let _task = self.in_task(key);
         task(cx, arg)
     }
 
-    pub fn read(&self, v: DepNode<DefId>) {
+    pub fn read(&self, v: DepNode) {
         if self.data.thread.is_enqueue_enabled() {
             self.data.thread.enqueue(DepMessage::Read(v));
         }
diff --git a/src/librustc/dep_graph/mod.rs b/src/librustc/dep_graph/mod.rs
index 809bed939f5..92b05f6a655 100644
--- a/src/librustc/dep_graph/mod.rs
+++ b/src/librustc/dep_graph/mod.rs
@@ -28,3 +28,5 @@ pub use self::query::DepGraphQuery;
 pub use self::safe::AssertDepGraphSafe;
 pub use self::safe::DepGraphSafe;
 pub use self::raii::DepTask;
+
+pub use self::dep_node::{DepKind, DepConstructor};
diff --git a/src/librustc/dep_graph/query.rs b/src/librustc/dep_graph/query.rs
index 4c791f96553..116c527bf46 100644
--- a/src/librustc/dep_graph/query.rs
+++ b/src/librustc/dep_graph/query.rs
@@ -10,20 +10,18 @@
 
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::graph::{Direction, INCOMING, Graph, NodeIndex, OUTGOING};
-use std::fmt::Debug;
-use std::hash::Hash;
 
 use super::DepNode;
 
-pub struct DepGraphQuery<D: Clone + Debug + Hash + Eq> {
-    pub graph: Graph<DepNode<D>, ()>,
-    pub indices: FxHashMap<DepNode<D>, NodeIndex>,
+pub struct DepGraphQuery {
+    pub graph: Graph<DepNode, ()>,
+    pub indices: FxHashMap<DepNode, NodeIndex>,
 }
 
-impl<D: Clone + Debug + Hash + Eq> DepGraphQuery<D> {
-    pub fn new(nodes: &[DepNode<D>],
-               edges: &[(DepNode<D>, DepNode<D>)])
-               -> DepGraphQuery<D> {
+impl DepGraphQuery {
+    pub fn new(nodes: &[DepNode],
+               edges: &[(DepNode, DepNode)])
+               -> DepGraphQuery {
         let mut graph = Graph::new();
         let mut indices = FxHashMap();
         for node in nodes {
@@ -43,18 +41,18 @@ impl<D: Clone + Debug + Hash + Eq> DepGraphQuery<D> {
         }
     }
 
-    pub fn contains_node(&self, node: &DepNode<D>) -> bool {
+    pub fn contains_node(&self, node: &DepNode) -> bool {
         self.indices.contains_key(&node)
     }
 
-    pub fn nodes(&self) -> Vec<&DepNode<D>> {
+    pub fn nodes(&self) -> Vec<&DepNode> {
         self.graph.all_nodes()
                   .iter()
                   .map(|n| &n.data)
                   .collect()
     }
 
-    pub fn edges(&self) -> Vec<(&DepNode<D>,&DepNode<D>)> {
+    pub fn edges(&self) -> Vec<(&DepNode,&DepNode)> {
         self.graph.all_edges()
                   .iter()
                   .map(|edge| (edge.source(), edge.target()))
@@ -63,7 +61,7 @@ impl<D: Clone + Debug + Hash + Eq> DepGraphQuery<D> {
                   .collect()
     }
 
-    fn reachable_nodes(&self, node: &DepNode<D>, direction: Direction) -> Vec<&DepNode<D>> {
+    fn reachable_nodes(&self, node: &DepNode, direction: Direction) -> Vec<&DepNode> {
         if let Some(&index) = self.indices.get(node) {
             self.graph.depth_traverse(index, direction)
                       .map(|s| self.graph.node_data(s))
@@ -75,17 +73,17 @@ impl<D: Clone + Debug + Hash + Eq> DepGraphQuery<D> {
 
     /// All nodes reachable from `node`. In other words, things that
     /// will have to be recomputed if `node` changes.
-    pub fn transitive_successors(&self, node: &DepNode<D>) -> Vec<&DepNode<D>> {
+    pub fn transitive_successors(&self, node: &DepNode) -> Vec<&DepNode> {
         self.reachable_nodes(node, OUTGOING)
     }
 
     /// All nodes that can reach `node`.
-    pub fn transitive_predecessors(&self, node: &DepNode<D>) -> Vec<&DepNode<D>> {
+    pub fn transitive_predecessors(&self, node: &DepNode) -> Vec<&DepNode> {
         self.reachable_nodes(node, INCOMING)
     }
 
     /// Just the outgoing edges from `node`.
-    pub fn immediate_successors(&self, node: &DepNode<D>) -> Vec<&DepNode<D>> {
+    pub fn immediate_successors(&self, node: &DepNode) -> Vec<&DepNode> {
         if let Some(&index) = self.indices.get(&node) {
             self.graph.successor_nodes(index)
                       .map(|s| self.graph.node_data(s))
diff --git a/src/librustc/dep_graph/raii.rs b/src/librustc/dep_graph/raii.rs
index e39797599ac..b45f5de8027 100644
--- a/src/librustc/dep_graph/raii.rs
+++ b/src/librustc/dep_graph/raii.rs
@@ -8,17 +8,16 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use hir::def_id::DefId;
 use super::DepNode;
 use super::thread::{DepGraphThreadData, DepMessage};
 
 pub struct DepTask<'graph> {
     data: &'graph DepGraphThreadData,
-    key: Option<DepNode<DefId>>,
+    key: Option<DepNode>,
 }
 
 impl<'graph> DepTask<'graph> {
-    pub fn new(data: &'graph DepGraphThreadData, key: DepNode<DefId>)
+    pub fn new(data: &'graph DepGraphThreadData, key: DepNode)
                -> Option<DepTask<'graph>> {
         if data.is_enqueue_enabled() {
             data.enqueue(DepMessage::PushTask(key.clone()));
diff --git a/src/librustc/dep_graph/shadow.rs b/src/librustc/dep_graph/shadow.rs
index bedb6ff2771..8808ea5948d 100644
--- a/src/librustc/dep_graph/shadow.rs
+++ b/src/librustc/dep_graph/shadow.rs
@@ -26,7 +26,6 @@
 //! specify an edge filter to be applied to each edge as it is
 //! created.  See `./README.md` for details.
 
-use hir::def_id::DefId;
 use std::cell::RefCell;
 use std::env;
 
@@ -36,7 +35,7 @@ use super::debug::EdgeFilter;
 
 pub struct ShadowGraph {
     // if you push None onto the stack, that corresponds to an Ignore
-    stack: RefCell<Vec<Option<DepNode<DefId>>>>,
+    stack: RefCell<Vec<Option<DepNode>>>,
     forbidden_edge: Option<EdgeFilter>,
 }
 
@@ -114,8 +113,8 @@ impl ShadowGraph {
     }
 
     fn check_edge(&self,
-                  source: Option<Option<&DepNode<DefId>>>,
-                  target: Option<Option<&DepNode<DefId>>>) {
+                  source: Option<Option<&DepNode>>,
+                  target: Option<Option<&DepNode>>) {
         assert!(ENABLED);
         match (source, target) {
             // cannot happen, one side is always Some(Some(_))
@@ -141,9 +140,9 @@ impl ShadowGraph {
 
 // Do a little juggling: we get back a reference to an option at the
 // top of the stack, convert it to an optional reference.
-fn top<'s>(stack: &'s Vec<Option<DepNode<DefId>>>) -> Option<Option<&'s DepNode<DefId>>> {
+fn top<'s>(stack: &'s Vec<Option<DepNode>>) -> Option<Option<&'s DepNode>> {
     stack.last()
-        .map(|n: &'s Option<DepNode<DefId>>| -> Option<&'s DepNode<DefId>> {
+        .map(|n: &'s Option<DepNode>| -> Option<&'s DepNode> {
             // (*)
             // (*) type annotation just there to clarify what would
             // otherwise be some *really* obscure code
diff --git a/src/librustc/dep_graph/thread.rs b/src/librustc/dep_graph/thread.rs
index d3a940c811b..ad0abfe26f4 100644
--- a/src/librustc/dep_graph/thread.rs
+++ b/src/librustc/dep_graph/thread.rs
@@ -18,7 +18,6 @@
 //! to accumulate more messages. This way we only ever have two vectors
 //! allocated (and both have a fairly large capacity).
 
-use hir::def_id::DefId;
 use rustc_data_structures::veccell::VecCell;
 use std::sync::mpsc::{self, Sender, Receiver};
 use std::thread;
@@ -30,10 +29,10 @@ use super::shadow::ShadowGraph;
 
 #[derive(Debug)]
 pub enum DepMessage {
-    Read(DepNode<DefId>),
-    Write(DepNode<DefId>),
-    PushTask(DepNode<DefId>),
-    PopTask(DepNode<DefId>),
+    Read(DepNode),
+    Write(DepNode),
+    PushTask(DepNode),
+    PopTask(DepNode),
     PushIgnore,
     PopIgnore,
     Query,
@@ -63,7 +62,7 @@ pub struct DepGraphThreadData {
     swap_out: Sender<Vec<DepMessage>>,
 
     // where to receive query results
-    query_in: Receiver<DepGraphQuery<DefId>>,
+    query_in: Receiver<DepGraphQuery>,
 }
 
 const INITIAL_CAPACITY: usize = 2048;
@@ -120,7 +119,7 @@ impl DepGraphThreadData {
         self.swap_out.send(old_messages).unwrap();
     }
 
-    pub fn query(&self) -> DepGraphQuery<DefId> {
+    pub fn query(&self) -> DepGraphQuery {
         assert!(self.is_fully_enabled(), "should never query if not fully enabled");
         self.enqueue(DepMessage::Query);
         self.swap();
@@ -151,7 +150,7 @@ impl DepGraphThreadData {
 /// Definition of the depgraph thread.
 pub fn main(swap_in: Receiver<Vec<DepMessage>>,
             swap_out: Sender<Vec<DepMessage>>,
-            query_out: Sender<DepGraphQuery<DefId>>) {
+            query_out: Sender<DepGraphQuery>) {
     let mut edges = DepGraphEdges::new();
 
     // the compiler thread always expects a fresh buffer to be
diff --git a/src/librustc/hir/map/mod.rs b/src/librustc/hir/map/mod.rs
index 176760c255c..a1875cd46a0 100644
--- a/src/librustc/hir/map/mod.rs
+++ b/src/librustc/hir/map/mod.rs
@@ -15,7 +15,7 @@ pub use self::def_collector::{DefCollector, MacroInvocationData};
 pub use self::definitions::{Definitions, DefKey, DefPath, DefPathData,
                             DisambiguatedDefPathData, DefPathHash};
 
-use dep_graph::{DepGraph, DepNode};
+use dep_graph::{DepGraph, DepNode, DepKind};
 
 use hir::def_id::{CRATE_DEF_INDEX, DefId, DefIndex, DefIndexAddressSpace};
 
@@ -235,7 +235,7 @@ impl Forest {
     }
 
     pub fn krate<'hir>(&'hir self) -> &'hir Crate {
-        self.dep_graph.read(DepNode::Krate);
+        self.dep_graph.read(DepNode::new_no_params(DepKind::Krate));
         &self.krate
     }
 }
@@ -280,7 +280,7 @@ impl<'hir> Map<'hir> {
         self.dep_graph.read(self.dep_node(id));
     }
 
-    fn dep_node(&self, id0: NodeId) -> DepNode<DefId> {
+    fn dep_node(&self, id0: NodeId) -> DepNode {
         let mut id = id0;
         let mut last_expr = None;
         loop {
@@ -289,14 +289,16 @@ impl<'hir> Map<'hir> {
                 EntryItem(..) |
                 EntryTraitItem(..) |
                 EntryImplItem(..) => {
+                    let def_index = self.definitions.opt_def_index(id).unwrap();
+                    let def_path_hash = self.definitions.def_path_hash(def_index);
+
                     if let Some(last_id) = last_expr {
                         // The body may have a separate dep node
                         if entry.is_body_owner(last_id) {
-                            let def_id = self.local_def_id(id);
-                            return DepNode::HirBody(def_id);
+                            return def_path_hash.to_dep_node(DepKind::HirBody);
                         }
                     }
-                    return DepNode::Hir(self.local_def_id(id));
+                    return def_path_hash.to_dep_node(DepKind::Hir);
                 }
 
                 EntryVariant(p, v) => {
@@ -305,8 +307,9 @@ impl<'hir> Map<'hir> {
                     if last_expr.is_some() {
                         if v.node.disr_expr.map(|e| e.node_id) == last_expr {
                             // The enum parent holds both Hir and HirBody nodes.
-                            let def_id = self.local_def_id(id);
-                            return DepNode::HirBody(def_id);
+                            let def_index = self.definitions.opt_def_index(id).unwrap();
+                            let def_path_hash = self.definitions.def_path_hash(def_index);
+                            return def_path_hash.to_dep_node(DepKind::HirBody);
                         }
                     }
                 }
@@ -331,7 +334,8 @@ impl<'hir> Map<'hir> {
                 }
 
                 RootCrate => {
-                    return DepNode::Hir(DefId::local(CRATE_DEF_INDEX));
+                    let def_path_hash = self.definitions.def_path_hash(CRATE_DEF_INDEX);
+                    return def_path_hash.to_dep_node(DepKind::Hir);
                 }
 
                 NotPresent =>
@@ -339,8 +343,11 @@ impl<'hir> Map<'hir> {
                     // present in the map for whatever reason, but
                     // they *do* have def-ids. So if we encounter an
                     // empty hole, check for that case.
-                    return self.opt_local_def_id(id)
-                               .map(|def_id| DepNode::Hir(def_id))
+                    return self.definitions.opt_def_index(id)
+                               .map(|def_index| {
+                                    let def_path_hash = self.definitions.def_path_hash(def_index);
+                                    def_path_hash.to_dep_node(DepKind::Hir)
+                                })
                                .unwrap_or_else(|| {
                                    bug!("Walking parents from `{}` \
                                          led to `NotPresent` at `{}`",
@@ -497,7 +504,7 @@ impl<'hir> Map<'hir> {
     }
 
     pub fn trait_impls(&self, trait_did: DefId) -> &'hir [NodeId] {
-        self.dep_graph.read(DepNode::AllLocalTraitImpls);
+        self.dep_graph.read(DepNode::new_no_params(DepKind::AllLocalTraitImpls));
 
         // NB: intentionally bypass `self.forest.krate()` so that we
         // do not trigger a read of the whole krate here
@@ -505,7 +512,7 @@ impl<'hir> Map<'hir> {
     }
 
     pub fn trait_default_impl(&self, trait_did: DefId) -> Option<NodeId> {
-        self.dep_graph.read(DepNode::AllLocalTraitImpls);
+        self.dep_graph.read(DepNode::new_no_params(DepKind::AllLocalTraitImpls));
 
         // NB: intentionally bypass `self.forest.krate()` so that we
         // do not trigger a read of the whole krate here
@@ -520,8 +527,9 @@ impl<'hir> Map<'hir> {
     /// invoking `krate.attrs` because it registers a tighter
     /// dep-graph access.
     pub fn krate_attrs(&self) -> &'hir [ast::Attribute] {
-        let crate_root_def_id = DefId::local(CRATE_DEF_INDEX);
-        self.dep_graph.read(DepNode::Hir(crate_root_def_id));
+        let def_path_hash = self.definitions.def_path_hash(CRATE_DEF_INDEX);
+
+        self.dep_graph.read(def_path_hash.to_dep_node(DepKind::Hir));
         &self.forest.krate.attrs
     }
 
@@ -754,11 +762,8 @@ impl<'hir> Map<'hir> {
         }
     }
 
-    pub fn get_inlined_body(&self, def_id: DefId) -> Option<&'hir Body> {
-        self.inlined_bodies.borrow().get(&def_id).map(|&body| {
-            self.dep_graph.read(DepNode::MetaData(def_id));
-            body
-        })
+    pub fn get_inlined_body_untracked(&self, def_id: DefId) -> Option<&'hir Body> {
+        self.inlined_bodies.borrow().get(&def_id).cloned()
     }
 
     pub fn intern_inlined_body(&self, def_id: DefId, body: Body) -> &'hir Body {
diff --git a/src/librustc/lint/context.rs b/src/librustc/lint/context.rs
index 40734469718..aa7428e5910 100644
--- a/src/librustc/lint/context.rs
+++ b/src/librustc/lint/context.rs
@@ -25,7 +25,7 @@
 //! for all lint attributes.
 use self::TargetLint::*;
 
-use dep_graph::DepNode;
+use dep_graph::{DepNode, DepKind};
 use middle::privacy::AccessLevels;
 use traits::Reveal;
 use ty::{self, TyCtxt};
@@ -1341,7 +1341,7 @@ fn check_lint_name_cmdline(sess: &Session, lint_cx: &LintStore,
 ///
 /// Consumes the `lint_store` field of the `Session`.
 pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
-    let _task = tcx.dep_graph.in_task(DepNode::LateLintCheck);
+    let _task = tcx.dep_graph.in_task(DepNode::new_no_params(DepKind::LateLintCheck));
 
     let access_levels = &tcx.privacy_access_levels(LOCAL_CRATE);
 
diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index c2fe0453437..16ecc94b947 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -183,7 +183,9 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
 
         assert!(!infcx.is_in_snapshot());
 
-        if infcx.tcx.fulfilled_predicates.borrow().check_duplicate(&obligation.predicate) {
+        let tcx = infcx.tcx;
+
+        if tcx.fulfilled_predicates.borrow().check_duplicate(tcx, &obligation.predicate) {
             debug!("register_predicate_obligation: duplicate");
             return
         }
@@ -373,7 +375,8 @@ fn process_predicate<'a, 'gcx, 'tcx>(
 
     match obligation.predicate {
         ty::Predicate::Trait(ref data) => {
-            if selcx.tcx().fulfilled_predicates.borrow().check_duplicate_trait(data) {
+            let tcx = selcx.tcx();
+            if tcx.fulfilled_predicates.borrow().check_duplicate_trait(tcx, data) {
                 return Ok(Some(vec![]));
             }
 
@@ -607,22 +610,22 @@ impl<'a, 'gcx, 'tcx> GlobalFulfilledPredicates<'gcx> {
         }
     }
 
-    pub fn check_duplicate(&self, key: &ty::Predicate<'tcx>) -> bool {
+    pub fn check_duplicate(&self, tcx: TyCtxt, key: &ty::Predicate<'tcx>) -> bool {
         if let ty::Predicate::Trait(ref data) = *key {
-            self.check_duplicate_trait(data)
+            self.check_duplicate_trait(tcx, data)
         } else {
             false
         }
     }
 
-    pub fn check_duplicate_trait(&self, data: &ty::PolyTraitPredicate<'tcx>) -> bool {
+    pub fn check_duplicate_trait(&self, tcx: TyCtxt, data: &ty::PolyTraitPredicate<'tcx>) -> bool {
         // For the global predicate registry, when we find a match, it
         // may have been computed by some other task, so we want to
         // add a read from the node corresponding to the predicate
         // processing to make sure we get the transitive dependencies.
         if self.set.contains(data) {
             debug_assert!(data.is_global());
-            self.dep_graph.read(data.dep_node());
+            self.dep_graph.read(data.dep_node(tcx));
             debug!("check_duplicate: global predicate `{:?}` already proved elsewhere", data);
 
             true
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 998201ad8d9..10710d963a0 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -381,7 +381,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         assert!(!obligation.predicate.has_escaping_regions());
 
         let tcx = self.tcx();
-        let dep_node = obligation.predicate.dep_node();
+        let dep_node = obligation.predicate.dep_node(tcx);
         let _task = tcx.dep_graph.in_task(dep_node);
 
         let stack = self.push_stack(TraitObligationStackList::empty(), obligation);
@@ -514,11 +514,13 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         debug!("evaluate_predicate_recursively({:?})",
                obligation);
 
+        let tcx = self.tcx();
+
         // Check the cache from the tcx of predicates that we know
         // have been proven elsewhere. This cache only contains
         // predicates that are global in scope and hence unaffected by
         // the current environment.
-        if self.tcx().fulfilled_predicates.borrow().check_duplicate(&obligation.predicate) {
+        if tcx.fulfilled_predicates.borrow().check_duplicate(tcx, &obligation.predicate) {
             return EvaluatedToOk;
         }
 
diff --git a/src/librustc/traits/trans/mod.rs b/src/librustc/traits/trans/mod.rs
index 734ba2a2d39..40bd88d731d 100644
--- a/src/librustc/traits/trans/mod.rs
+++ b/src/librustc/traits/trans/mod.rs
@@ -13,7 +13,8 @@
 // seems likely that they should eventually be merged into more
 // general routines.
 
-use dep_graph::{DepGraph, DepNode, DepTrackingMap, DepTrackingMapConfig};
+use dep_graph::{DepGraph, DepNode, DepTrackingMap, DepTrackingMapConfig,
+                DepConstructor};
 use hir::def_id::DefId;
 use infer::TransNormalize;
 use std::cell::RefCell;
@@ -40,7 +41,7 @@ impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
         // Remove any references to regions; this helps improve caching.
         let trait_ref = self.erase_regions(&trait_ref);
 
-        self.trans_trait_caches.trait_cache.memoize(trait_ref, || {
+        self.trans_trait_caches.trait_cache.memoize(self, trait_ref, || {
             debug!("trans::fulfill_obligation(trait_ref={:?}, def_id={:?})",
                    trait_ref, trait_ref.def_id());
 
@@ -138,7 +139,7 @@ impl<'a, 'gcx> TypeFolder<'gcx, 'gcx> for AssociatedTypeNormalizer<'a, 'gcx> {
         if !ty.has_projection_types() {
             ty
         } else {
-            self.tcx.trans_trait_caches.project_cache.memoize(ty, || {
+            self.tcx.trans_trait_caches.project_cache.memoize(self.tcx, ty, || {
                 debug!("AssociatedTypeNormalizer: ty={:?}", ty);
                 self.tcx.normalize_associated_type(&ty)
             })
@@ -170,8 +171,8 @@ pub struct TraitSelectionCache<'tcx> {
 impl<'tcx> DepTrackingMapConfig for TraitSelectionCache<'tcx> {
     type Key = ty::PolyTraitRef<'tcx>;
     type Value = Vtable<'tcx, ()>;
-    fn to_dep_node(key: &ty::PolyTraitRef<'tcx>) -> DepNode<DefId> {
-        key.to_poly_trait_predicate().dep_node()
+    fn to_dep_node(tcx: TyCtxt, key: &ty::PolyTraitRef<'tcx>) -> DepNode {
+        key.to_poly_trait_predicate().dep_node(tcx)
     }
 }
 
@@ -184,7 +185,7 @@ pub struct ProjectionCache<'gcx> {
 impl<'gcx> DepTrackingMapConfig for ProjectionCache<'gcx> {
     type Key = Ty<'gcx>;
     type Value = Ty<'gcx>;
-    fn to_dep_node(key: &Self::Key) -> DepNode<DefId> {
+    fn to_dep_node(tcx: TyCtxt, key: &Self::Key) -> DepNode {
         // Ideally, we'd just put `key` into the dep-node, but we
         // can't put full types in there. So just collect up all the
         // def-ids of structs/enums as well as any traits that we
@@ -208,7 +209,7 @@ impl<'gcx> DepTrackingMapConfig for ProjectionCache<'gcx> {
                })
                .collect();
 
-        DepNode::ProjectionCache { def_ids: def_ids }
+        DepNode::new(tcx, DepConstructor::ProjectionCache { def_ids: def_ids })
     }
 }
 
diff --git a/src/librustc/ty/instance.rs b/src/librustc/ty/instance.rs
index 7dca28df9da..76103148ec3 100644
--- a/src/librustc/ty/instance.rs
+++ b/src/librustc/ty/instance.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use dep_graph::DepNode;
+use dep_graph::DepConstructor;
 use hir::def_id::DefId;
 use ty::{self, Ty, TypeFoldable, Substs};
 use util::ppaux;
@@ -60,7 +60,8 @@ impl<'tcx> InstanceDef<'tcx> {
         tcx.get_attrs(self.def_id())
     }
 
-    pub(crate) fn dep_node(&self) -> DepNode<DefId> {
+    pub //(crate)
+     fn dep_node(&self) -> DepConstructor {
         // HACK: def-id binning, project-style; someone replace this with
         // real on-demand.
         let ty = match self {
@@ -69,7 +70,7 @@ impl<'tcx> InstanceDef<'tcx> {
             _ => None
         }.into_iter();
 
-        DepNode::MirShim(
+        DepConstructor::MirShim(
             Some(self.def_id()).into_iter().chain(
                 ty.flat_map(|t| t.walk()).flat_map(|t| match t.sty {
                    ty::TyAdt(adt_def, _) => Some(adt_def.did),
diff --git a/src/librustc/ty/maps.rs b/src/librustc/ty/maps.rs
index b5adcc8ed75..162a734aa19 100644
--- a/src/librustc/ty/maps.rs
+++ b/src/librustc/ty/maps.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use dep_graph::{DepNode, DepTrackingMapConfig};
+use dep_graph::{DepConstructor, DepNode, DepTrackingMapConfig};
 use hir::def_id::{CrateNum, CRATE_DEF_INDEX, DefId, LOCAL_CRATE};
 use hir::def::Def;
 use hir;
@@ -524,10 +524,10 @@ macro_rules! define_maps {
             type Value = $V;
 
             #[allow(unused)]
-            fn to_dep_node(key: &$K) -> DepNode<DefId> {
-                use dep_graph::DepNode::*;
+            fn to_dep_node(tcx: TyCtxt, key: &$K) -> DepNode {
+                use dep_graph::DepConstructor::*;
 
-                $node(*key)
+                DepNode::new(tcx, $node(*key))
             }
         }
         impl<'a, $tcx, 'lcx> queries::$name<$tcx> {
@@ -554,7 +554,7 @@ macro_rules! define_maps {
                     span = key.default_span(tcx)
                 }
 
-                let _task = tcx.dep_graph.in_task(Self::to_dep_node(&key));
+                let _task = tcx.dep_graph.in_task(Self::to_dep_node(tcx, &key));
 
                 let result = tcx.cycle_check(span, Query::$name(key), || {
                     let provider = tcx.maps.providers[key.map_crate()].$name;
@@ -569,7 +569,7 @@ macro_rules! define_maps {
                 // We register the `read` here, but not in `force`, since
                 // `force` does not give access to the value produced (and thus
                 // we actually don't read it).
-                tcx.dep_graph.read(Self::to_dep_node(&key));
+                tcx.dep_graph.read(Self::to_dep_node(tcx, &key));
                 Self::try_get_with(tcx, span, key, Clone::clone)
             }
 
@@ -782,7 +782,7 @@ define_maps! { <'tcx>
 
     /// To avoid cycles within the predicates of a single item we compute
     /// per-type-parameter predicates for resolving `T::AssocTy`.
-    [] type_param_predicates: TypeParamPredicates((DefId, DefId))
+    [] type_param_predicates: type_param_predicates((DefId, DefId))
         -> ty::GenericPredicates<'tcx>,
 
     [] trait_def: ItemSignature(DefId) -> &'tcx ty::TraitDef,
@@ -931,74 +931,81 @@ define_maps! { <'tcx>
                                   -> Result<&'tcx Layout, LayoutError<'tcx>>,
 }
 
-fn coherent_trait_dep_node((_, def_id): (CrateNum, DefId)) -> DepNode<DefId> {
-    DepNode::CoherenceCheckTrait(def_id)
+fn type_param_predicates((item_id, param_id): (DefId, DefId)) -> DepConstructor {
+    DepConstructor::TypeParamPredicates {
+        item_id,
+        param_id
+    }
+}
+
+fn coherent_trait_dep_node((_, def_id): (CrateNum, DefId)) -> DepConstructor {
+    DepConstructor::CoherenceCheckTrait(def_id)
 }
 
-fn crate_inherent_impls_dep_node(_: CrateNum) -> DepNode<DefId> {
-    DepNode::Coherence
+fn crate_inherent_impls_dep_node(_: CrateNum) -> DepConstructor {
+    DepConstructor::Coherence
 }
 
-fn reachability_dep_node(_: CrateNum) -> DepNode<DefId> {
-    DepNode::Reachability
+fn reachability_dep_node(_: CrateNum) -> DepConstructor {
+    DepConstructor::Reachability
 }
 
-fn mir_shim_dep_node(instance: ty::InstanceDef) -> DepNode<DefId> {
+fn mir_shim_dep_node(instance: ty::InstanceDef) -> DepConstructor {
     instance.dep_node()
 }
 
-fn symbol_name_dep_node(instance: ty::Instance) -> DepNode<DefId> {
+fn symbol_name_dep_node(instance: ty::Instance) -> DepConstructor {
     // symbol_name uses the substs only to traverse them to find the
     // hash, and that does not create any new dep-nodes.
-    DepNode::SymbolName(instance.def.def_id())
+    DepConstructor::SymbolName(instance.def.def_id())
 }
 
-fn typeck_item_bodies_dep_node(_: CrateNum) -> DepNode<DefId> {
-    DepNode::TypeckBodiesKrate
+fn typeck_item_bodies_dep_node(_: CrateNum) -> DepConstructor {
+    DepConstructor::TypeckBodiesKrate
 }
 
-fn const_eval_dep_node((def_id, _): (DefId, &Substs)) -> DepNode<DefId> {
-    DepNode::ConstEval(def_id)
+fn const_eval_dep_node((def_id, _): (DefId, &Substs)) -> DepConstructor {
+    DepConstructor::ConstEval(def_id)
 }
 
-fn mir_keys(_: CrateNum) -> DepNode<DefId> {
-    DepNode::MirKeys
+fn mir_keys(_: CrateNum) -> DepConstructor {
+    DepConstructor::MirKeys
 }
 
-fn crate_variances(_: CrateNum) -> DepNode<DefId> {
-    DepNode::CrateVariances
+fn crate_variances(_: CrateNum) -> DepConstructor {
+    DepConstructor::CrateVariances
 }
 
-fn relevant_trait_impls_for((def_id, _): (DefId, SimplifiedType)) -> DepNode<DefId> {
-    DepNode::TraitImpls(def_id)
+fn relevant_trait_impls_for((def_id, _): (DefId, SimplifiedType)) -> DepConstructor {
+    DepConstructor::TraitImpls(def_id)
 }
 
-fn is_copy_dep_node<'tcx>(key: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepNode<DefId> {
+fn is_copy_dep_node<'tcx>(key: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepConstructor {
     let def_id = ty::item_path::characteristic_def_id_of_type(key.value)
         .unwrap_or(DefId::local(CRATE_DEF_INDEX));
-    DepNode::IsCopy(def_id)
+    DepConstructor::IsCopy(def_id)
 }
 
-fn is_sized_dep_node<'tcx>(key: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepNode<DefId> {
+fn is_sized_dep_node<'tcx>(key: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepConstructor {
     let def_id = ty::item_path::characteristic_def_id_of_type(key.value)
         .unwrap_or(DefId::local(CRATE_DEF_INDEX));
-    DepNode::IsSized(def_id)
+    DepConstructor::IsSized(def_id)
 }
 
-fn is_freeze_dep_node<'tcx>(key: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepNode<DefId> {
+fn is_freeze_dep_node<'tcx>(key: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepConstructor {
     let def_id = ty::item_path::characteristic_def_id_of_type(key.value)
         .unwrap_or(DefId::local(CRATE_DEF_INDEX));
-    DepNode::IsFreeze(def_id)
+    DepConstructor::IsFreeze(def_id)
 }
 
-fn needs_drop_dep_node<'tcx>(key: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepNode<DefId> {
+fn needs_drop_dep_node<'tcx>(key: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepConstructor {
     let def_id = ty::item_path::characteristic_def_id_of_type(key.value)
         .unwrap_or(DefId::local(CRATE_DEF_INDEX));
-    DepNode::NeedsDrop(def_id)
+    DepConstructor::NeedsDrop(def_id)
 }
 
-fn layout_dep_node<'tcx>(key: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepNode<DefId> {
+fn layout_dep_node<'tcx>(key: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepConstructor {
     let def_id = ty::item_path::characteristic_def_id_of_type(key.value)
         .unwrap_or(DefId::local(CRATE_DEF_INDEX));
-    DepNode::Layout(def_id)
+    DepConstructor::Layout(def_id)
 }
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index eea767cd868..d6b144ba59a 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -15,7 +15,7 @@ pub use self::IntVarValue::*;
 pub use self::LvaluePreference::*;
 pub use self::fold::TypeFoldable;
 
-use dep_graph::DepNode;
+use dep_graph::{DepNode, DepConstructor};
 use hir::{map as hir_map, FreevarMap, TraitMap};
 use hir::def::{Def, CtorKind, ExportMap};
 use hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX, LOCAL_CRATE};
@@ -936,7 +936,7 @@ impl<'tcx> TraitPredicate<'tcx> {
     }
 
     /// Creates the dep-node for selecting/evaluating this trait reference.
-    fn dep_node(&self) -> DepNode<DefId> {
+    fn dep_node(&self, tcx: TyCtxt) -> DepNode {
         // Extact the trait-def and first def-id from inputs.  See the
         // docs for `DepNode::TraitSelect` for more information.
         let trait_def_id = self.def_id();
@@ -949,10 +949,10 @@ impl<'tcx> TraitPredicate<'tcx> {
                 })
                 .next()
                 .unwrap_or(trait_def_id);
-        DepNode::TraitSelect {
+        DepNode::new(tcx, DepConstructor::TraitSelect {
             trait_def_id: trait_def_id,
             input_def_id: input_def_id
-        }
+        })
     }
 
     pub fn input_types<'a>(&'a self) -> impl DoubleEndedIterator<Item=Ty<'tcx>> + 'a {
@@ -970,9 +970,9 @@ impl<'tcx> PolyTraitPredicate<'tcx> {
         self.0.def_id()
     }
 
-    pub fn dep_node(&self) -> DepNode<DefId> {
+    pub fn dep_node(&self, tcx: TyCtxt) -> DepNode {
         // ok to skip binder since depnode does not care about regions
-        self.0.dep_node()
+        self.0.dep_node(tcx)
     }
 }
 
diff --git a/src/librustc/util/common.rs b/src/librustc/util/common.rs
index 17564671a1e..40ee3cd28f5 100644
--- a/src/librustc/util/common.rs
+++ b/src/librustc/util/common.rs
@@ -19,6 +19,8 @@ use std::iter::repeat;
 use std::path::Path;
 use std::time::{Duration, Instant};
 
+use ty::TyCtxt;
+
 // The name of the associated type for `Fn` return types
 pub const FN_OUTPUT_NAME: &'static str = "Output";
 
@@ -209,7 +211,7 @@ pub trait MemoizationMap {
     /// needed in the `op` to ensure that the correct edges are
     /// added into the dep graph. See the `DepTrackingMap` impl for
     /// more details!
-    fn memoize<OP>(&self, key: Self::Key, op: OP) -> Self::Value
+    fn memoize<OP>(&self, tcx: TyCtxt, key: Self::Key, op: OP) -> Self::Value
         where OP: FnOnce() -> Self::Value;
 }
 
@@ -219,7 +221,7 @@ impl<K, V, S> MemoizationMap for RefCell<HashMap<K,V,S>>
     type Key = K;
     type Value = V;
 
-    fn memoize<OP>(&self, key: K, op: OP) -> V
+    fn memoize<OP>(&self, _tcx: TyCtxt, key: K, op: OP) -> V
         where OP: FnOnce() -> V
     {
         let result = self.borrow().get(&key).cloned();
diff --git a/src/librustc_incremental/assert_dep_graph.rs b/src/librustc_incremental/assert_dep_graph.rs
index 39fe2188f68..04192c35ef3 100644
--- a/src/librustc_incremental/assert_dep_graph.rs
+++ b/src/librustc_incremental/assert_dep_graph.rs
@@ -44,7 +44,7 @@
 //! ```
 
 use graphviz as dot;
-use rustc::dep_graph::{DepGraphQuery, DepNode};
+use rustc::dep_graph::{DepGraphQuery, DepNode, DepKind};
 use rustc::dep_graph::debug::{DepNodeFilter, EdgeFilter};
 use rustc::hir::def_id::DefId;
 use rustc::ty::TyCtxt;
@@ -95,8 +95,8 @@ pub fn assert_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
     check_paths(tcx, &if_this_changed, &then_this_would_need);
 }
 
-type Sources = Vec<(Span, DefId, DepNode<DefId>)>;
-type Targets = Vec<(Span, ast::Name, ast::NodeId, DepNode<DefId>)>;
+type Sources = Vec<(Span, DefId, DepNode)>;
+type Targets = Vec<(Span, ast::Name, ast::NodeId, DepNode)>;
 
 struct IfThisChanged<'a, 'tcx:'a> {
     tcx: TyCtxt<'a, 'tcx, 'tcx>,
@@ -121,13 +121,14 @@ impl<'a, 'tcx> IfThisChanged<'a, 'tcx> {
 
     fn process_attrs(&mut self, node_id: ast::NodeId, attrs: &[ast::Attribute]) {
         let def_id = self.tcx.hir.local_def_id(node_id);
+        let def_path_hash = self.tcx.def_path_hash(def_id);
         for attr in attrs {
             if attr.check_name(ATTR_IF_THIS_CHANGED) {
                 let dep_node_interned = self.argument(attr);
                 let dep_node = match dep_node_interned {
-                    None => DepNode::Hir(def_id),
+                    None => def_path_hash.to_dep_node(DepKind::Hir),
                     Some(n) => {
-                        match DepNode::from_label_string(&n.as_str(), def_id) {
+                        match DepNode::from_label_string(&n.as_str(), def_path_hash) {
                             Ok(n) => n,
                             Err(()) => {
                                 self.tcx.sess.span_fatal(
@@ -142,7 +143,7 @@ impl<'a, 'tcx> IfThisChanged<'a, 'tcx> {
                 let dep_node_interned = self.argument(attr);
                 let dep_node = match dep_node_interned {
                     Some(n) => {
-                        match DepNode::from_label_string(&n.as_str(), def_id) {
+                        match DepNode::from_label_string(&n.as_str(), def_path_hash) {
                             Ok(n) => n,
                             Err(()) => {
                                 self.tcx.sess.span_fatal(
@@ -263,34 +264,34 @@ fn dump_graph(tcx: TyCtxt) {
     }
 }
 
-pub struct GraphvizDepGraph<'q>(FxHashSet<&'q DepNode<DefId>>,
-                                Vec<(&'q DepNode<DefId>, &'q DepNode<DefId>)>);
+pub struct GraphvizDepGraph<'q>(FxHashSet<&'q DepNode>,
+                                Vec<(&'q DepNode, &'q DepNode)>);
 
 impl<'a, 'tcx, 'q> dot::GraphWalk<'a> for GraphvizDepGraph<'q> {
-    type Node = &'q DepNode<DefId>;
-    type Edge = (&'q DepNode<DefId>, &'q DepNode<DefId>);
-    fn nodes(&self) -> dot::Nodes<&'q DepNode<DefId>> {
+    type Node = &'q DepNode;
+    type Edge = (&'q DepNode, &'q DepNode);
+    fn nodes(&self) -> dot::Nodes<&'q DepNode> {
         let nodes: Vec<_> = self.0.iter().cloned().collect();
         nodes.into_cow()
     }
-    fn edges(&self) -> dot::Edges<(&'q DepNode<DefId>, &'q DepNode<DefId>)> {
+    fn edges(&self) -> dot::Edges<(&'q DepNode, &'q DepNode)> {
         self.1[..].into_cow()
     }
-    fn source(&self, edge: &(&'q DepNode<DefId>, &'q DepNode<DefId>)) -> &'q DepNode<DefId> {
+    fn source(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode {
         edge.0
     }
-    fn target(&self, edge: &(&'q DepNode<DefId>, &'q DepNode<DefId>)) -> &'q DepNode<DefId> {
+    fn target(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode {
         edge.1
     }
 }
 
 impl<'a, 'tcx, 'q> dot::Labeller<'a> for GraphvizDepGraph<'q> {
-    type Node = &'q DepNode<DefId>;
-    type Edge = (&'q DepNode<DefId>, &'q DepNode<DefId>);
+    type Node = &'q DepNode;
+    type Edge = (&'q DepNode, &'q DepNode);
     fn graph_id(&self) -> dot::Id {
         dot::Id::new("DependencyGraph").unwrap()
     }
-    fn node_id(&self, n: &&'q DepNode<DefId>) -> dot::Id {
+    fn node_id(&self, n: &&'q DepNode) -> dot::Id {
         let s: String =
             format!("{:?}", n).chars()
                               .map(|c| if c == '_' || c.is_alphanumeric() { c } else { '_' })
@@ -298,7 +299,7 @@ impl<'a, 'tcx, 'q> dot::Labeller<'a> for GraphvizDepGraph<'q> {
         debug!("n={:?} s={:?}", n, s);
         dot::Id::new(s).unwrap()
     }
-    fn node_label(&self, n: &&'q DepNode<DefId>) -> dot::LabelText {
+    fn node_label(&self, n: &&'q DepNode) -> dot::LabelText {
         dot::LabelText::label(format!("{:?}", n))
     }
 }
@@ -306,8 +307,8 @@ impl<'a, 'tcx, 'q> dot::Labeller<'a> for GraphvizDepGraph<'q> {
 // Given an optional filter like `"x,y,z"`, returns either `None` (no
 // filter) or the set of nodes whose labels contain all of those
 // substrings.
-fn node_set<'q>(query: &'q DepGraphQuery<DefId>, filter: &DepNodeFilter)
-                -> Option<FxHashSet<&'q DepNode<DefId>>>
+fn node_set<'q>(query: &'q DepGraphQuery, filter: &DepNodeFilter)
+                -> Option<FxHashSet<&'q DepNode>>
 {
     debug!("node_set(filter={:?})", filter);
 
@@ -318,10 +319,10 @@ fn node_set<'q>(query: &'q DepGraphQuery<DefId>, filter: &DepNodeFilter)
     Some(query.nodes().into_iter().filter(|n| filter.test(n)).collect())
 }
 
-fn filter_nodes<'q>(query: &'q DepGraphQuery<DefId>,
-                    sources: &Option<FxHashSet<&'q DepNode<DefId>>>,
-                    targets: &Option<FxHashSet<&'q DepNode<DefId>>>)
-                    -> FxHashSet<&'q DepNode<DefId>>
+fn filter_nodes<'q>(query: &'q DepGraphQuery,
+                    sources: &Option<FxHashSet<&'q DepNode>>,
+                    targets: &Option<FxHashSet<&'q DepNode>>)
+                    -> FxHashSet<&'q DepNode>
 {
     if let &Some(ref sources) = sources {
         if let &Some(ref targets) = targets {
@@ -336,10 +337,10 @@ fn filter_nodes<'q>(query: &'q DepGraphQuery<DefId>,
     }
 }
 
-fn walk_nodes<'q>(query: &'q DepGraphQuery<DefId>,
-                  starts: &FxHashSet<&'q DepNode<DefId>>,
+fn walk_nodes<'q>(query: &'q DepGraphQuery,
+                  starts: &FxHashSet<&'q DepNode>,
                   direction: Direction)
-                  -> FxHashSet<&'q DepNode<DefId>>
+                  -> FxHashSet<&'q DepNode>
 {
     let mut set = FxHashSet();
     for &start in starts {
@@ -360,10 +361,10 @@ fn walk_nodes<'q>(query: &'q DepGraphQuery<DefId>,
     set
 }
 
-fn walk_between<'q>(query: &'q DepGraphQuery<DefId>,
-                    sources: &FxHashSet<&'q DepNode<DefId>>,
-                    targets: &FxHashSet<&'q DepNode<DefId>>)
-                    -> FxHashSet<&'q DepNode<DefId>>
+fn walk_between<'q>(query: &'q DepGraphQuery,
+                    sources: &FxHashSet<&'q DepNode>,
+                    targets: &FxHashSet<&'q DepNode>)
+                    -> FxHashSet<&'q DepNode>
 {
     // This is a bit tricky. We want to include a node only if it is:
     // (a) reachable from a source and (b) will reach a target. And we
@@ -391,7 +392,7 @@ fn walk_between<'q>(query: &'q DepGraphQuery<DefId>,
                 })
                 .collect();
 
-    fn recurse(query: &DepGraphQuery<DefId>,
+    fn recurse(query: &DepGraphQuery,
                node_states: &mut [State],
                node: NodeIndex)
                -> bool
@@ -428,9 +429,9 @@ fn walk_between<'q>(query: &'q DepGraphQuery<DefId>,
     }
 }
 
-fn filter_edges<'q>(query: &'q DepGraphQuery<DefId>,
-                    nodes: &FxHashSet<&'q DepNode<DefId>>)
-                    -> Vec<(&'q DepNode<DefId>, &'q DepNode<DefId>)>
+fn filter_edges<'q>(query: &'q DepGraphQuery,
+                    nodes: &FxHashSet<&'q DepNode>)
+                    -> Vec<(&'q DepNode, &'q DepNode)>
 {
     query.edges()
          .into_iter()
diff --git a/src/librustc_incremental/calculate_svh/mod.rs b/src/librustc_incremental/calculate_svh/mod.rs
index 7831ae3092f..f30a0f553b9 100644
--- a/src/librustc_incremental/calculate_svh/mod.rs
+++ b/src/librustc_incremental/calculate_svh/mod.rs
@@ -29,7 +29,7 @@
 
 use std::cell::RefCell;
 use std::hash::Hash;
-use rustc::dep_graph::DepNode;
+use rustc::dep_graph::{DepNode, DepKind};
 use rustc::hir;
 use rustc::hir::def_id::{CRATE_DEF_INDEX, DefId};
 use rustc::hir::map::DefPathHash;
@@ -44,7 +44,7 @@ use rustc_data_structures::accumulate_vec::AccumulateVec;
 pub type IchHasher = StableHasher<Fingerprint>;
 
 pub struct IncrementalHashesMap {
-    hashes: FxHashMap<DepNode<DefId>, Fingerprint>,
+    hashes: FxHashMap<DepNode, Fingerprint>,
 
     // These are the metadata hashes for the current crate as they were stored
     // during the last compilation session. They are only loaded if
@@ -62,16 +62,16 @@ impl IncrementalHashesMap {
         }
     }
 
-    pub fn get(&self, k: &DepNode<DefId>) -> Option<&Fingerprint> {
+    pub fn get(&self, k: &DepNode) -> Option<&Fingerprint> {
         self.hashes.get(k)
     }
 
-    pub fn insert(&mut self, k: DepNode<DefId>, v: Fingerprint) -> Option<Fingerprint> {
-        self.hashes.insert(k, v)
+    pub fn insert(&mut self, k: DepNode, v: Fingerprint) {
+        assert!(self.hashes.insert(k, v).is_none());
     }
 
     pub fn iter<'a>(&'a self)
-                    -> ::std::collections::hash_map::Iter<'a, DepNode<DefId>, Fingerprint> {
+                    -> ::std::collections::hash_map::Iter<'a, DepNode, Fingerprint> {
         self.hashes.iter()
     }
 
@@ -80,10 +80,10 @@ impl IncrementalHashesMap {
     }
 }
 
-impl<'a> ::std::ops::Index<&'a DepNode<DefId>> for IncrementalHashesMap {
+impl<'a> ::std::ops::Index<&'a DepNode> for IncrementalHashesMap {
     type Output = Fingerprint;
 
-    fn index(&self, index: &'a DepNode<DefId>) -> &Fingerprint {
+    fn index(&self, index: &'a DepNode) -> &Fingerprint {
         match self.hashes.get(index) {
             Some(fingerprint) => fingerprint,
             None => {
@@ -100,7 +100,7 @@ struct ComputeItemHashesVisitor<'a, 'tcx: 'a> {
 
 impl<'a, 'tcx: 'a> ComputeItemHashesVisitor<'a, 'tcx> {
     fn compute_and_store_ich_for_item_like<T>(&mut self,
-                                              dep_node: DepNode<DefId>,
+                                              dep_node: DepNode,
                                               hash_bodies: bool,
                                               item_like: T)
         where T: HashStable<StableHashingContext<'a, 'tcx, 'tcx>>
@@ -143,36 +143,29 @@ impl<'a, 'tcx: 'a> ComputeItemHashesVisitor<'a, 'tcx> {
         // add each item (in some deterministic order) to the overall
         // crate hash.
         {
-            let hcx = &mut self.hcx;
             let mut item_hashes: Vec<_> =
                 self.hashes.iter()
-                           .filter_map(|(item_dep_node, &item_hash)| {
+                           .filter_map(|(&item_dep_node, &item_hash)| {
                                 // This `match` determines what kinds of nodes
                                 // go into the SVH:
-                                match *item_dep_node {
-                                    DepNode::Hir(_) |
-                                    DepNode::HirBody(_) => {
+                                match item_dep_node.kind {
+                                    DepKind::Hir |
+                                    DepKind::HirBody => {
                                         // We want to incoporate these into the
                                         // SVH.
                                     }
-                                    DepNode::AllLocalTraitImpls => {
+                                    DepKind::AllLocalTraitImpls => {
                                         // These are already covered by hashing
                                         // the HIR.
                                         return None
                                     }
                                     ref other => {
-                                        bug!("Found unexpected DepNode during \
+                                        bug!("Found unexpected DepKind during \
                                               SVH computation: {:?}",
                                              other)
                                     }
                                 }
 
-                                // Convert from a DepNode<DefId> to a
-                                // DepNode<u64> where the u64 is the hash of
-                                // the def-id's def-path:
-                                let item_dep_node =
-                                    item_dep_node.map_def(|&did| Some(hcx.def_path_hash(did)))
-                                                 .unwrap();
                                 Some((item_dep_node, item_hash))
                            })
                            .collect();
@@ -183,7 +176,7 @@ impl<'a, 'tcx: 'a> ComputeItemHashesVisitor<'a, 'tcx> {
         krate.attrs.hash_stable(&mut self.hcx, &mut crate_state);
 
         let crate_hash = crate_state.finish();
-        self.hashes.insert(DepNode::Krate, crate_hash);
+        self.hashes.insert(DepNode::new_no_params(DepKind::Krate), crate_hash);
         debug!("calculate_crate_hash: crate_hash={:?}", crate_hash);
     }
 
@@ -206,11 +199,11 @@ impl<'a, 'tcx: 'a> ComputeItemHashesVisitor<'a, 'tcx> {
             body_ids: _,
         } = *krate;
 
-        let def_id = DefId::local(CRATE_DEF_INDEX);
-        self.compute_and_store_ich_for_item_like(DepNode::Hir(def_id),
+        let def_path_hash = self.hcx.tcx().hir.definitions().def_path_hash(CRATE_DEF_INDEX);
+        self.compute_and_store_ich_for_item_like(def_path_hash.to_dep_node(DepKind::Hir),
                                                  false,
                                                  (module, (span, attrs)));
-        self.compute_and_store_ich_for_item_like(DepNode::HirBody(def_id),
+        self.compute_and_store_ich_for_item_like(def_path_hash.to_dep_node(DepKind::HirBody),
                                                  true,
                                                  (module, (span, attrs)));
     }
@@ -255,27 +248,43 @@ impl<'a, 'tcx: 'a> ComputeItemHashesVisitor<'a, 'tcx> {
         let mut hasher = StableHasher::new();
         impls.hash_stable(&mut self.hcx, &mut hasher);
 
-        self.hashes.insert(DepNode::AllLocalTraitImpls, hasher.finish());
+        self.hashes.insert(DepNode::new_no_params(DepKind::AllLocalTraitImpls),
+                           hasher.finish());
     }
 }
 
 impl<'a, 'tcx: 'a> ItemLikeVisitor<'tcx> for ComputeItemHashesVisitor<'a, 'tcx> {
     fn visit_item(&mut self, item: &'tcx hir::Item) {
         let def_id = self.hcx.tcx().hir.local_def_id(item.id);
-        self.compute_and_store_ich_for_item_like(DepNode::Hir(def_id), false, item);
-        self.compute_and_store_ich_for_item_like(DepNode::HirBody(def_id), true, item);
+        let def_path_hash = self.hcx.tcx().def_path_hash(def_id);
+        self.compute_and_store_ich_for_item_like(def_path_hash.to_dep_node(DepKind::Hir),
+                                                 false,
+                                                 item);
+        self.compute_and_store_ich_for_item_like(def_path_hash.to_dep_node(DepKind::HirBody),
+                                                 true,
+                                                 item);
     }
 
     fn visit_trait_item(&mut self, item: &'tcx hir::TraitItem) {
         let def_id = self.hcx.tcx().hir.local_def_id(item.id);
-        self.compute_and_store_ich_for_item_like(DepNode::Hir(def_id), false, item);
-        self.compute_and_store_ich_for_item_like(DepNode::HirBody(def_id), true, item);
+        let def_path_hash = self.hcx.tcx().def_path_hash(def_id);
+        self.compute_and_store_ich_for_item_like(def_path_hash.to_dep_node(DepKind::Hir),
+                                                 false,
+                                                 item);
+        self.compute_and_store_ich_for_item_like(def_path_hash.to_dep_node(DepKind::HirBody),
+                                                 true,
+                                                 item);
     }
 
     fn visit_impl_item(&mut self, item: &'tcx hir::ImplItem) {
         let def_id = self.hcx.tcx().hir.local_def_id(item.id);
-        self.compute_and_store_ich_for_item_like(DepNode::Hir(def_id), false, item);
-        self.compute_and_store_ich_for_item_like(DepNode::HirBody(def_id), true, item);
+        let def_path_hash = self.hcx.tcx().def_path_hash(def_id);
+        self.compute_and_store_ich_for_item_like(def_path_hash.to_dep_node(DepKind::Hir),
+                                                 false,
+                                                 item);
+        self.compute_and_store_ich_for_item_like(def_path_hash.to_dep_node(DepKind::HirBody),
+                                                 true,
+                                                 item);
     }
 }
 
@@ -297,8 +306,13 @@ pub fn compute_incremental_hashes_map<'a, 'tcx: 'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>)
 
         for macro_def in krate.exported_macros.iter() {
             let def_id = tcx.hir.local_def_id(macro_def.id);
-            visitor.compute_and_store_ich_for_item_like(DepNode::Hir(def_id), false, macro_def);
-            visitor.compute_and_store_ich_for_item_like(DepNode::HirBody(def_id), true, macro_def);
+            let def_path_hash = tcx.def_path_hash(def_id);
+            visitor.compute_and_store_ich_for_item_like(def_path_hash.to_dep_node(DepKind::Hir),
+                                                        false,
+                                                        macro_def);
+            visitor.compute_and_store_ich_for_item_like(def_path_hash.to_dep_node(DepKind::HirBody),
+                                                        true,
+                                                        macro_def);
         }
 
         visitor.compute_and_store_ich_for_trait_impls(krate);
diff --git a/src/librustc_incremental/persist/data.rs b/src/librustc_incremental/persist/data.rs
index 96b7de94daf..06acfb5d778 100644
--- a/src/librustc_incremental/persist/data.rs
+++ b/src/librustc_incremental/persist/data.rs
@@ -22,11 +22,11 @@ use rustc_data_structures::indexed_vec::{IndexVec, Idx};
 #[derive(Debug, RustcEncodable, RustcDecodable)]
 pub struct SerializedDepGraph {
     /// The set of all DepNodes in the graph
-    pub nodes: IndexVec<DepNodeIndex, DepNode<DefPathHash>>,
+    pub nodes: IndexVec<DepNodeIndex, DepNode>,
     /// For each DepNode, stores the list of edges originating from that
     /// DepNode. Encoded as a [start, end) pair indexing into edge_list_data,
     /// which holds the actual DepNodeIndices of the target nodes.
-    pub edge_list_indices: Vec<(u32, u32)>,
+    pub edge_list_indices: IndexVec<DepNodeIndex, (u32, u32)>,
     /// A flattened list of all edge targets in the graph. Edge sources are
     /// implicit in edge_list_indices.
     pub edge_list_data: Vec<DepNodeIndex>,
@@ -34,7 +34,7 @@ pub struct SerializedDepGraph {
     /// These are output nodes that have no incoming edges. We track
     /// these separately so that when we reload all edges, we don't
     /// lose track of these nodes.
-    pub bootstrap_outputs: Vec<DepNode<DefPathHash>>,
+    pub bootstrap_outputs: Vec<DepNode>,
 
     /// These are hashes of two things:
     /// - the HIR nodes in this crate
@@ -55,7 +55,14 @@ pub struct SerializedDepGraph {
     /// will be different when we next compile) related to each node,
     /// but rather the `DefPathIndex`. This can then be retraced
     /// to find the current def-id.
-    pub hashes: Vec<SerializedHash>,
+    pub hashes: Vec<(DepNodeIndex, Fingerprint)>,
+}
+
+impl SerializedDepGraph {
+    pub fn edge_targets_from(&self, source: DepNodeIndex) -> &[DepNodeIndex] {
+        let targets = self.edge_list_indices[source];
+        &self.edge_list_data[targets.0 as usize .. targets.1 as usize]
+    }
 }
 
 /// The index of a DepNode in the SerializedDepGraph::nodes array.
@@ -85,16 +92,6 @@ impl Idx for DepNodeIndex {
 }
 
 #[derive(Debug, RustcEncodable, RustcDecodable)]
-pub struct SerializedHash {
-    /// def-id of thing being hashed
-    pub dep_node: DepNode<DefPathHash>,
-
-    /// the hash as of previous compilation, computed by code in
-    /// `hash` module
-    pub hash: Fingerprint,
-}
-
-#[derive(Debug, RustcEncodable, RustcDecodable)]
 pub struct SerializedWorkProduct {
     /// node that produced the work-product
     pub id: WorkProductId,
diff --git a/src/librustc_incremental/persist/dirty_clean.rs b/src/librustc_incremental/persist/dirty_clean.rs
index 3a428bd7b8f..3f3dc10365c 100644
--- a/src/librustc_incremental/persist/dirty_clean.rs
+++ b/src/librustc_incremental/persist/dirty_clean.rs
@@ -40,8 +40,9 @@
 //! previous revision to compare things to.
 //!
 
+use super::data::DepNodeIndex;
 use super::load::DirtyNodes;
-use rustc::dep_graph::{DepGraphQuery, DepNode};
+use rustc::dep_graph::{DepGraphQuery, DepNode, DepKind};
 use rustc::hir;
 use rustc::hir::def_id::DefId;
 use rustc::hir::itemlikevisit::ItemLikeVisitor;
@@ -50,6 +51,7 @@ use rustc::ich::{Fingerprint, ATTR_DIRTY, ATTR_CLEAN, ATTR_DIRTY_METADATA,
                  ATTR_CLEAN_METADATA};
 use syntax::ast::{self, Attribute, NestedMetaItem};
 use rustc_data_structures::fx::{FxHashSet, FxHashMap};
+use rustc_data_structures::indexed_vec::IndexVec;
 use syntax_pos::Span;
 use rustc::ty::TyCtxt;
 
@@ -57,6 +59,7 @@ const LABEL: &'static str = "label";
 const CFG: &'static str = "cfg";
 
 pub fn check_dirty_clean_annotations<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
+                                               nodes: &IndexVec<DepNodeIndex, DepNode>,
                                                dirty_inputs: &DirtyNodes) {
     // can't add `#[rustc_dirty]` etc without opting in to this feature
     if !tcx.sess.features.borrow().rustc_attrs {
@@ -64,13 +67,15 @@ pub fn check_dirty_clean_annotations<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     }
 
     let _ignore = tcx.dep_graph.in_ignore();
-    let def_path_hash_to_def_id = tcx.def_path_hash_to_def_id.as_ref().unwrap();
-    let dirty_inputs: FxHashSet<DepNode<DefId>> =
+    let dirty_inputs: FxHashSet<DepNode> =
         dirty_inputs.keys()
-                    .filter_map(|dep_node| {
-                        dep_node.map_def(|def_path_hash| {
-                            def_path_hash_to_def_id.get(def_path_hash).cloned()
-                        })
+                    .filter_map(|dep_node_index| {
+                        let dep_node = nodes[*dep_node_index];
+                        if dep_node.extract_def_id(tcx).is_some() {
+                            Some(dep_node)
+                        } else {
+                            None
+                        }
                     })
                     .collect();
 
@@ -100,18 +105,19 @@ pub fn check_dirty_clean_annotations<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
 pub struct DirtyCleanVisitor<'a, 'tcx:'a> {
     tcx: TyCtxt<'a, 'tcx, 'tcx>,
-    query: &'a DepGraphQuery<DefId>,
-    dirty_inputs: FxHashSet<DepNode<DefId>>,
+    query: &'a DepGraphQuery,
+    dirty_inputs: FxHashSet<DepNode>,
     checked_attrs: FxHashSet<ast::AttrId>,
 }
 
 impl<'a, 'tcx> DirtyCleanVisitor<'a, 'tcx> {
-    fn dep_node(&self, attr: &Attribute, def_id: DefId) -> DepNode<DefId> {
+    fn dep_node(&self, attr: &Attribute, def_id: DefId) -> DepNode {
+        let def_path_hash = self.tcx.def_path_hash(def_id);
         for item in attr.meta_item_list().unwrap_or_else(Vec::new) {
             if item.check_name(LABEL) {
                 let value = expect_associated_value(self.tcx, &item);
-                match DepNode::from_label_string(&value.as_str(), def_id) {
-                    Ok(def_id) => return def_id,
+                match DepNode::from_label_string(&value.as_str(), def_path_hash) {
+                    Ok(dep_node) => return dep_node,
                     Err(()) => {
                         self.tcx.sess.span_fatal(
                             item.span,
@@ -124,24 +130,30 @@ impl<'a, 'tcx> DirtyCleanVisitor<'a, 'tcx> {
         self.tcx.sess.span_fatal(attr.span, "no `label` found");
     }
 
-    fn dep_node_str(&self, dep_node: &DepNode<DefId>) -> DepNode<String> {
-        dep_node.map_def(|&def_id| Some(self.tcx.item_path_str(def_id))).unwrap()
+    fn dep_node_str(&self, dep_node: &DepNode) -> String {
+        if let Some(def_id) = dep_node.extract_def_id(self.tcx) {
+            format!("{:?}({})",
+                    dep_node.kind,
+                    self.tcx.item_path_str(def_id))
+        } else {
+            format!("{:?}({:?})", dep_node.kind, dep_node.hash)
+        }
     }
 
-    fn assert_dirty(&self, item_span: Span, dep_node: DepNode<DefId>) {
+    fn assert_dirty(&self, item_span: Span, dep_node: DepNode) {
         debug!("assert_dirty({:?})", dep_node);
 
-        match dep_node {
-            DepNode::Krate |
-            DepNode::Hir(_) |
-            DepNode::HirBody(_) => {
+        match dep_node.kind {
+            DepKind::Krate |
+            DepKind::Hir |
+            DepKind::HirBody => {
                 // HIR nodes are inputs, so if we are asserting that the HIR node is
                 // dirty, we check the dirty input set.
                 if !self.dirty_inputs.contains(&dep_node) {
                     let dep_node_str = self.dep_node_str(&dep_node);
                     self.tcx.sess.span_err(
                         item_span,
-                        &format!("`{:?}` not found in dirty set, but should be dirty",
+                        &format!("`{}` not found in dirty set, but should be dirty",
                                  dep_node_str));
                 }
             }
@@ -152,25 +164,25 @@ impl<'a, 'tcx> DirtyCleanVisitor<'a, 'tcx> {
                     let dep_node_str = self.dep_node_str(&dep_node);
                     self.tcx.sess.span_err(
                         item_span,
-                        &format!("`{:?}` found in dep graph, but should be dirty", dep_node_str));
+                        &format!("`{}` found in dep graph, but should be dirty", dep_node_str));
                 }
             }
         }
     }
 
-    fn assert_clean(&self, item_span: Span, dep_node: DepNode<DefId>) {
+    fn assert_clean(&self, item_span: Span, dep_node: DepNode) {
         debug!("assert_clean({:?})", dep_node);
 
-        match dep_node {
-            DepNode::Krate |
-            DepNode::Hir(_) |
-            DepNode::HirBody(_) => {
+        match dep_node.kind {
+            DepKind::Krate |
+            DepKind::Hir |
+            DepKind::HirBody => {
                 // For HIR nodes, check the inputs.
                 if self.dirty_inputs.contains(&dep_node) {
                     let dep_node_str = self.dep_node_str(&dep_node);
                     self.tcx.sess.span_err(
                         item_span,
-                        &format!("`{:?}` found in dirty-node set, but should be clean",
+                        &format!("`{}` found in dirty-node set, but should be clean",
                                  dep_node_str));
                 }
             }
@@ -180,7 +192,7 @@ impl<'a, 'tcx> DirtyCleanVisitor<'a, 'tcx> {
                     let dep_node_str = self.dep_node_str(&dep_node);
                     self.tcx.sess.span_err(
                         item_span,
-                        &format!("`{:?}` not found in dep graph, but should be clean",
+                        &format!("`{}` not found in dep graph, but should be clean",
                                  dep_node_str));
                 }
             }
diff --git a/src/librustc_incremental/persist/hash.rs b/src/librustc_incremental/persist/hash.rs
index 4a2dd274aae..0e8ffb9ee3c 100644
--- a/src/librustc_incremental/persist/hash.rs
+++ b/src/librustc_incremental/persist/hash.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use rustc::dep_graph::DepNode;
+use rustc::dep_graph::{DepNode, DepKind};
 use rustc::hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
 use rustc::hir::svh::Svh;
 use rustc::ich::Fingerprint;
@@ -45,31 +45,29 @@ impl<'a, 'tcx> HashContext<'a, 'tcx> {
         }
     }
 
-    pub fn is_hashable(dep_node: &DepNode<DefId>) -> bool {
-        match *dep_node {
-            DepNode::Krate |
-            DepNode::Hir(_) |
-            DepNode::HirBody(_) =>
+    pub fn is_hashable(tcx: TyCtxt, dep_node: &DepNode) -> bool {
+        match dep_node.kind {
+            DepKind::Krate |
+            DepKind::Hir |
+            DepKind::HirBody =>
                 true,
-            DepNode::MetaData(def_id) => !def_id.is_local(),
+            DepKind::MetaData => {
+                let def_id = dep_node.extract_def_id(tcx).unwrap();
+                !def_id.is_local()
+            }
             _ => false,
         }
     }
 
-    pub fn hash(&mut self, dep_node: &DepNode<DefId>) -> Option<Fingerprint> {
-        match *dep_node {
-            DepNode::Krate => {
+    pub fn hash(&mut self, dep_node: &DepNode) -> Option<Fingerprint> {
+        match dep_node.kind {
+            DepKind::Krate => {
                 Some(self.incremental_hashes_map[dep_node])
             }
 
             // HIR nodes (which always come from our crate) are an input:
-            DepNode::Hir(def_id) |
-            DepNode::HirBody(def_id) => {
-                assert!(def_id.is_local(),
-                        "cannot hash HIR for non-local def-id {:?} => {:?}",
-                        def_id,
-                        self.tcx.item_path_str(def_id));
-
+            DepKind::Hir |
+            DepKind::HirBody => {
                 Some(self.incremental_hashes_map[dep_node])
             }
 
@@ -77,10 +75,15 @@ impl<'a, 'tcx> HashContext<'a, 'tcx> {
             // MetaData nodes from *our* crates are an *output*; we
             // don't hash them, but we do compute a hash for them and
             // save it for others to use.
-            DepNode::MetaData(def_id) if !def_id.is_local() => {
-                Some(self.metadata_hash(def_id,
+            DepKind::MetaData => {
+                let def_id = dep_node.extract_def_id(self.tcx).unwrap();
+                if !def_id.is_local() {
+                    Some(self.metadata_hash(def_id,
                                         def_id.krate,
                                         |this| &mut this.metadata_hashes))
+                } else {
+                    None
+                }
             }
 
             _ => {
diff --git a/src/librustc_incremental/persist/load.rs b/src/librustc_incremental/persist/load.rs
index f2ecf4c74e7..28a00bf4aa6 100644
--- a/src/librustc_incremental/persist/load.rs
+++ b/src/librustc_incremental/persist/load.rs
@@ -10,17 +10,16 @@
 
 //! Code to save/load the dep-graph from files.
 
-use rustc::dep_graph::{DepNode, WorkProductId};
+use rustc::dep_graph::{DepNode, WorkProductId, DepKind};
 use rustc::hir::def_id::DefId;
-use rustc::hir::map::DefPathHash;
 use rustc::hir::svh::Svh;
 use rustc::ich::Fingerprint;
 use rustc::session::Session;
 use rustc::ty::TyCtxt;
 use rustc_data_structures::fx::{FxHashSet, FxHashMap};
+use rustc_data_structures::indexed_vec::IndexVec;
 use rustc_serialize::Decodable as RustcDecodable;
 use rustc_serialize::opaque::Decoder;
-use std::default::Default;
 use std::path::{Path};
 
 use IncrementalHashesMap;
@@ -33,7 +32,7 @@ use super::work_product;
 
 // The key is a dirty node. The value is **some** base-input that we
 // can blame it on.
-pub type DirtyNodes = FxHashMap<DepNode<DefPathHash>, DepNode<DefPathHash>>;
+pub type DirtyNodes = FxHashMap<DepNodeIndex, DepNodeIndex>;
 
 /// If we are in incremental mode, and a previous dep-graph exists,
 /// then load up those nodes/edges that are still valid into the
@@ -118,14 +117,20 @@ fn load_data(sess: &Session, path: &Path) -> Option<Vec<u8>> {
     None
 }
 
-/// Try to convert a DepNode from the old dep-graph into a DepNode in the
-/// current graph by mapping the DefPathHash to a valid DefId. This will fail
-/// if the DefPathHash refers to something that has been removed (because
-/// there is no DefId for that thing anymore).
-fn retrace(tcx: TyCtxt, dep_node: &DepNode<DefPathHash>) -> Option<DepNode<DefId>> {
-    dep_node.map_def(|def_path_hash| {
-        tcx.def_path_hash_to_def_id.as_ref().unwrap().get(def_path_hash).cloned()
-    })
+/// Check if a DepNode from the previous dep-graph refers to something that
+/// still exists in the current compilation session. Only works for DepNode
+/// variants that represent inputs (HIR and imported Metadata).
+fn does_still_exist(tcx: TyCtxt, dep_node: &DepNode) -> bool {
+    match dep_node.kind {
+        DepKind::Hir |
+        DepKind::HirBody |
+        DepKind::MetaData => {
+            dep_node.extract_def_id(tcx).is_some()
+        }
+        _ => {
+            bug!("unexpected Input DepNode: {:?}", dep_node)
+        }
+    }
 }
 
 /// Decode the dep graph and load the edges/nodes that are still clean
@@ -161,86 +166,55 @@ pub fn decode_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     let serialized_dep_graph = SerializedDepGraph::decode(&mut dep_graph_decoder)?;
 
-    let edge_map: FxHashMap<DepNode<DefPathHash>, Vec<DepNode<DefPathHash>>> = {
-        let capacity = serialized_dep_graph.edge_list_data.len();
-        let mut edge_map = FxHashMap::with_capacity_and_hasher(capacity, Default::default());
-
-        for (node_index, source) in serialized_dep_graph.nodes.iter().enumerate() {
-            let (start, end) = serialized_dep_graph.edge_list_indices[node_index];
-            let targets =
-                (&serialized_dep_graph.edge_list_data[start as usize .. end as usize])
-                .into_iter()
-                .map(|&node_index| serialized_dep_graph.nodes[node_index].clone())
-                .collect();
-
-            edge_map.insert(source.clone(), targets);
-        }
-
-        edge_map
-    };
-
     // Compute the set of nodes from the old graph where some input
-    // has changed or been removed. These are "raw" source nodes,
-    // which means that they still use the original `DefPathIndex`
-    // values from the encoding, rather than having been retraced to a
-    // `DefId`. The reason for this is that this way we can include
-    // nodes that have been removed (which no longer have a `DefId` in
-    // the current compilation).
+    // has changed or been removed.
     let dirty_raw_nodes = initial_dirty_nodes(tcx,
                                               incremental_hashes_map,
+                                              &serialized_dep_graph.nodes,
                                               &serialized_dep_graph.hashes);
-    let dirty_raw_nodes = transitive_dirty_nodes(&edge_map, dirty_raw_nodes);
+    let dirty_raw_nodes = transitive_dirty_nodes(&serialized_dep_graph,
+                                                 dirty_raw_nodes);
 
     // Recreate the edges in the graph that are still clean.
     let mut clean_work_products = FxHashSet();
     let mut dirty_work_products = FxHashSet(); // incomplete; just used to suppress debug output
-    let mut extra_edges = vec![];
-    for (source, targets) in &edge_map {
-        for target in targets {
-            process_edges(tcx, source, target, &edge_map, &dirty_raw_nodes,
-                          &mut clean_work_products, &mut dirty_work_products, &mut extra_edges);
+    for (source, targets) in serialized_dep_graph.edge_list_indices.iter_enumerated() {
+        let target_begin = targets.0 as usize;
+        let target_end = targets.1 as usize;
+
+        for &target in &serialized_dep_graph.edge_list_data[target_begin .. target_end] {
+            process_edge(tcx,
+                         source,
+                         target,
+                         &serialized_dep_graph.nodes,
+                         &dirty_raw_nodes,
+                         &mut clean_work_products,
+                         &mut dirty_work_products);
         }
     }
 
-    // Recreate bootstrap outputs, which are outputs that have no incoming edges (and hence cannot
-    // be dirty).
+    // Recreate bootstrap outputs, which are outputs that have no incoming edges
+    // (and hence cannot be dirty).
     for bootstrap_output in &serialized_dep_graph.bootstrap_outputs {
-        if let Some(n) = retrace(tcx, bootstrap_output) {
-            if let DepNode::WorkProduct(ref wp) = n {
-                clean_work_products.insert(wp.clone());
-            }
+        if let DepKind::WorkProduct = bootstrap_output.kind {
+            let wp_id = WorkProductId::from_fingerprint(bootstrap_output.hash);
+            clean_work_products.insert(wp_id);
+        }
 
-            tcx.dep_graph.with_task(n, (), (), create_node);
+        tcx.dep_graph.with_task(*bootstrap_output, (), (), create_node);
 
-            fn create_node((): (), (): ()) {
-                // just create the node with no inputs
-            }
+        fn create_node((): (), (): ()) {
+            // just create the node with no inputs
         }
     }
 
-    // Subtle. Sometimes we have intermediate nodes that we can't recreate in the new graph.
-    // This is pretty unusual but it arises in a scenario like this:
-    //
-    //     Hir(X) -> Foo(Y) -> Bar
-    //
-    // Note that the `Hir(Y)` is not an input to `Foo(Y)` -- this
-    // almost never happens, but can happen in some obscure
-    // scenarios. In that case, if `Y` is removed, then we can't
-    // recreate `Foo(Y)` (the def-id `Y` no longer exists); what we do
-    // then is to push the edge `Hir(X) -> Bar` onto `extra_edges`
-    // (along with any other targets of `Foo(Y)`). We will then add
-    // the edge from `Hir(X)` to `Bar` (or, if `Bar` itself cannot be
-    // recreated, to the targets of `Bar`).
-    while let Some((source, target)) = extra_edges.pop() {
-        process_edges(tcx, source, target, &edge_map, &dirty_raw_nodes,
-                      &mut clean_work_products, &mut dirty_work_products, &mut extra_edges);
-    }
-
     // Add in work-products that are still clean, and delete those that are
     // dirty.
     reconcile_work_products(tcx, work_products, &clean_work_products);
 
-    dirty_clean::check_dirty_clean_annotations(tcx, &dirty_raw_nodes);
+    dirty_clean::check_dirty_clean_annotations(tcx,
+                                               &serialized_dep_graph.nodes,
+                                               &dirty_raw_nodes);
 
     load_prev_metadata_hashes(tcx,
                               &mut *incremental_hashes_map.prev_metadata_hashes.borrow_mut());
@@ -251,70 +225,65 @@ pub fn decode_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 /// a bit vector where the index is the DefPathIndex.
 fn initial_dirty_nodes<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                  incremental_hashes_map: &IncrementalHashesMap,
-                                 serialized_hashes: &[SerializedHash])
+                                 nodes: &IndexVec<DepNodeIndex, DepNode>,
+                                 serialized_hashes: &[(DepNodeIndex, Fingerprint)])
                                  -> DirtyNodes {
     let mut hcx = HashContext::new(tcx, incremental_hashes_map);
     let mut dirty_nodes = FxHashMap();
 
-    let print_removed_message = |dep_node: &DepNode<_>| {
-        if tcx.sess.opts.debugging_opts.incremental_dump_hash {
-            println!("node {:?} is dirty as it was removed", dep_node);
-        }
-
-        debug!("initial_dirty_nodes: {:?} is dirty as it was removed", dep_node);
-    };
+    for &(dep_node_index, prev_hash) in serialized_hashes {
+        let dep_node = nodes[dep_node_index];
+        if does_still_exist(tcx, &dep_node) {
+            let current_hash = hcx.hash(&dep_node).unwrap_or_else(|| {
+                bug!("Cannot find current ICH for input that still exists?")
+            });
 
-    for hash in serialized_hashes {
-        if let Some(dep_node) = retrace(tcx, &hash.dep_node) {
-            if let Some(current_hash) = hcx.hash(&dep_node) {
-                if current_hash == hash.hash {
-                    debug!("initial_dirty_nodes: {:?} is clean (hash={:?})",
-                       dep_node.map_def(|&def_id| Some(tcx.def_path(def_id))).unwrap(),
+            if current_hash == prev_hash {
+                debug!("initial_dirty_nodes: {:?} is clean (hash={:?})",
+                       dep_node,
                        current_hash);
-                    continue;
-                }
-
-                if tcx.sess.opts.debugging_opts.incremental_dump_hash {
-                    println!("node {:?} is dirty as hash is {:?} was {:?}",
-                             dep_node.map_def(|&def_id| Some(tcx.def_path(def_id))).unwrap(),
-                             current_hash,
-                             hash.hash);
-                }
+                continue;
+            }
 
-                debug!("initial_dirty_nodes: {:?} is dirty as hash is {:?}, was {:?}",
-                       dep_node.map_def(|&def_id| Some(tcx.def_path(def_id))).unwrap(),
-                       current_hash,
-                       hash.hash);
-            } else {
-                print_removed_message(&hash.dep_node);
+            if tcx.sess.opts.debugging_opts.incremental_dump_hash {
+                println!("node {:?} is dirty as hash is {:?}, was {:?}",
+                         dep_node,
+                         current_hash,
+                         prev_hash);
             }
+
+            debug!("initial_dirty_nodes: {:?} is dirty as hash is {:?}, was {:?}",
+                   dep_node,
+                   current_hash,
+                   prev_hash);
         } else {
-            print_removed_message(&hash.dep_node);
-        }
+            if tcx.sess.opts.debugging_opts.incremental_dump_hash {
+                println!("node {:?} is dirty as it was removed", dep_node);
+            }
 
-        dirty_nodes.insert(hash.dep_node.clone(), hash.dep_node.clone());
+            debug!("initial_dirty_nodes: {:?} is dirty as it was removed", dep_node);
+        }
+        dirty_nodes.insert(dep_node_index, dep_node_index);
     }
 
     dirty_nodes
 }
 
-fn transitive_dirty_nodes(edge_map: &FxHashMap<DepNode<DefPathHash>, Vec<DepNode<DefPathHash>>>,
+fn transitive_dirty_nodes(serialized_dep_graph: &SerializedDepGraph,
                           mut dirty_nodes: DirtyNodes)
                           -> DirtyNodes
 {
-    let mut stack: Vec<(DepNode<DefPathHash>, DepNode<DefPathHash>)> = vec![];
-    stack.extend(dirty_nodes.iter().map(|(s, b)| (s.clone(), b.clone())));
+    let mut stack: Vec<(DepNodeIndex, DepNodeIndex)> = vec![];
+    stack.extend(dirty_nodes.iter().map(|(&s, &b)| (s, b)));
     while let Some((source, blame)) = stack.pop() {
         // we know the source is dirty (because of the node `blame`)...
-        assert!(dirty_nodes.contains_key(&source));
+        debug_assert!(dirty_nodes.contains_key(&source));
 
         // ...so we dirty all the targets (with the same blame)
-        if let Some(targets) = edge_map.get(&source) {
-            for target in targets {
-                if !dirty_nodes.contains_key(target) {
-                    dirty_nodes.insert(target.clone(), blame.clone());
-                    stack.push((target.clone(), blame.clone()));
-                }
+        for &target in serialized_dep_graph.edge_targets_from(source) {
+            if !dirty_nodes.contains_key(&target) {
+                dirty_nodes.insert(target, blame);
+                stack.push((target, blame));
             }
         }
     }
@@ -366,6 +335,7 @@ fn delete_dirty_work_product(tcx: TyCtxt,
 fn load_prev_metadata_hashes(tcx: TyCtxt,
                              output: &mut FxHashMap<DefId, Fingerprint>) {
     if !tcx.sess.opts.debugging_opts.query_dep_graph {
+        // Previous metadata hashes are only needed for testing.
         return
     }
 
@@ -417,71 +387,75 @@ fn load_prev_metadata_hashes(tcx: TyCtxt,
            serialized_hashes.index_map.len());
 }
 
-fn process_edges<'a, 'tcx, 'edges>(
+fn process_edge<'a, 'tcx, 'edges>(
     tcx: TyCtxt<'a, 'tcx, 'tcx>,
-    source: &'edges DepNode<DefPathHash>,
-    target: &'edges DepNode<DefPathHash>,
-    edges: &'edges FxHashMap<DepNode<DefPathHash>, Vec<DepNode<DefPathHash>>>,
+    source: DepNodeIndex,
+    target: DepNodeIndex,
+    nodes: &IndexVec<DepNodeIndex, DepNode>,
     dirty_raw_nodes: &DirtyNodes,
     clean_work_products: &mut FxHashSet<WorkProductId>,
-    dirty_work_products: &mut FxHashSet<WorkProductId>,
-    extra_edges: &mut Vec<(&'edges DepNode<DefPathHash>, &'edges DepNode<DefPathHash>)>)
+    dirty_work_products: &mut FxHashSet<WorkProductId>)
 {
     // If the target is dirty, skip the edge. If this is an edge
     // that targets a work-product, we can print the blame
     // information now.
-    if let Some(blame) = dirty_raw_nodes.get(target) {
-        if let DepNode::WorkProduct(ref wp) = *target {
+    if let Some(&blame) = dirty_raw_nodes.get(&target) {
+        let target = nodes[target];
+        if let DepKind::WorkProduct = target.kind {
             if tcx.sess.opts.debugging_opts.incremental_info {
-                if dirty_work_products.insert(wp.clone()) {
+                let wp_id = WorkProductId::from_fingerprint(target.hash);
+
+                if dirty_work_products.insert(wp_id) {
                     // Try to reconstruct the human-readable version of the
                     // DepNode. This cannot be done for things that where
                     // removed.
-                    let readable_blame = if let Some(dep_node) = retrace(tcx, blame) {
-                        dep_node.map_def(|&def_id| Some(tcx.def_path(def_id).to_string(tcx)))
-                                .unwrap()
+                    let blame = nodes[blame];
+                    let blame_str = if let Some(def_id) = blame.extract_def_id(tcx) {
+                        format!("{:?}({})",
+                                blame.kind,
+                                tcx.def_path(def_id).to_string(tcx))
                     } else {
-                        blame.map_def(|def_path_hash| Some(format!("{:?}", def_path_hash)))
-                             .unwrap()
+                        format!("{:?}", blame)
                     };
 
                     println!("incremental: module {:?} is dirty because {:?} \
                               changed or was removed",
-                             wp,
-                             readable_blame);
+                             wp_id,
+                             blame_str);
                 }
             }
         }
         return;
     }
 
-    // If the source is dirty, the target will be dirty.
-    assert!(!dirty_raw_nodes.contains_key(source));
-
-    // Retrace the source -> target edges to def-ids and then create
-    // an edge in the graph. Retracing may yield none if some of the
-    // data happens to have been removed.
-    if let Some(source_node) = retrace(tcx, source) {
-        if let Some(target_node) = retrace(tcx, target) {
-            let _task = tcx.dep_graph.in_task(target_node);
-            tcx.dep_graph.read(source_node);
-            if let DepNode::WorkProduct(ref wp) = *target {
-                clean_work_products.insert(wp.clone());
-            }
-        } else {
-            // As discussed in `decode_dep_graph` above, sometimes the
-            // target cannot be recreated again, in which case we add
-            // edges to go from `source` to the targets of `target`.
-            extra_edges.extend(
-                edges[target].iter().map(|t| (source, t)));
+    // At this point we have asserted that the target is clean -- otherwise, we
+    // would have hit the return above. We can do some further consistency
+    // checks based on this fact:
+
+    // We should never have an edge where the target is clean but the source
+    // was dirty. Otherwise something was wrong with the dirtying pass above:
+    debug_assert!(!dirty_raw_nodes.contains_key(&source));
+
+    // We also never should encounter an edge going from a removed input to a
+    // clean target because removing the input would have dirtied the input
+    // node and transitively dirtied the target.
+    debug_assert!(match nodes[source].kind {
+        DepKind::Hir | DepKind::HirBody | DepKind::MetaData => {
+            does_still_exist(tcx, &nodes[source])
+        }
+        _ => true,
+    });
+
+    if !dirty_raw_nodes.contains_key(&target) {
+        let target = nodes[target];
+        let source = nodes[source];
+        let _task = tcx.dep_graph.in_task(target);
+        tcx.dep_graph.read(source);
+
+        if let DepKind::WorkProduct = target.kind {
+            let wp_id = WorkProductId::from_fingerprint(target.hash);
+            clean_work_products.insert(wp_id);
         }
-    } else {
-        // It's also possible that the source can't be created! But we
-        // can ignore such cases, because (a) if `source` is a HIR
-        // node, it would be considered dirty; and (b) in other cases,
-        // there must be some input to this node that is clean, and so
-        // we'll re-create the edges over in the case where target is
-        // undefined.
     }
 }
 
diff --git a/src/librustc_incremental/persist/preds/mod.rs b/src/librustc_incremental/persist/preds/mod.rs
index e769641a4ca..0a259ad2685 100644
--- a/src/librustc_incremental/persist/preds/mod.rs
+++ b/src/librustc_incremental/persist/preds/mod.rs
@@ -8,8 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use rustc::dep_graph::{DepGraphQuery, DepNode};
-use rustc::hir::def_id::DefId;
+use rustc::dep_graph::{DepGraphQuery, DepNode, DepKind};
 use rustc::ich::Fingerprint;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::graph::{Graph, NodeIndex};
@@ -26,7 +25,7 @@ pub struct Predecessors<'query> {
     // nodes) and all of the "work-products" we may care about
     // later. Other nodes may be retained if it keeps the overall size
     // of the graph down.
-    pub reduced_graph: Graph<&'query DepNode<DefId>, ()>,
+    pub reduced_graph: Graph<&'query DepNode, ()>,
 
     // These are output nodes that have no incoming edges. We have to
     // track these specially because, when we load the data back up
@@ -34,32 +33,32 @@ pub struct Predecessors<'query> {
     // to recreate the nodes where all incoming edges are clean; but
     // since we ordinarily just serialize edges, we wind up just
     // forgetting that bootstrap outputs even exist in that case.)
-    pub bootstrap_outputs: Vec<&'query DepNode<DefId>>,
+    pub bootstrap_outputs: Vec<&'query DepNode>,
 
     // For the inputs (hir/foreign-metadata), we include hashes.
-    pub hashes: FxHashMap<&'query DepNode<DefId>, Fingerprint>,
+    pub hashes: FxHashMap<&'query DepNode, Fingerprint>,
 }
 
 impl<'q> Predecessors<'q> {
-    pub fn new(query: &'q DepGraphQuery<DefId>, hcx: &mut HashContext) -> Self {
+    pub fn new(query: &'q DepGraphQuery, hcx: &mut HashContext) -> Self {
         let tcx = hcx.tcx;
 
         // Find the set of "start nodes". These are nodes that we will
         // possibly query later.
-        let is_output = |node: &DepNode<DefId>| -> bool {
-            match *node {
-                DepNode::WorkProduct(_) => true,
-                DepNode::MetaData(ref def_id) => {
+        let is_output = |node: &DepNode| -> bool {
+            match node.kind {
+                DepKind::WorkProduct => true,
+                DepKind::MetaData => {
                     // We do *not* create dep-nodes for the current crate's
                     // metadata anymore, just for metadata that we import/read
                     // from other crates.
-                    debug_assert!(!def_id.is_local());
+                    debug_assert!(!node.extract_def_id(tcx).unwrap().is_local());
                     false
                 }
                 // if -Z query-dep-graph is passed, save more extended data
                 // to enable better unit testing
-                DepNode::TypeckTables(_) |
-                DepNode::TransCrateItem(_) => tcx.sess.opts.debugging_opts.query_dep_graph,
+                DepKind::TypeckTables |
+                DepKind::TransCrateItem => tcx.sess.opts.debugging_opts.query_dep_graph,
 
                 _ => false,
             }
@@ -67,7 +66,9 @@ impl<'q> Predecessors<'q> {
 
         // Reduce the graph to the most important nodes.
         let compress::Reduction { graph, input_nodes } =
-            compress::reduce_graph(&query.graph, HashContext::is_hashable, |n| is_output(n));
+            compress::reduce_graph(&query.graph,
+                                   |n| HashContext::is_hashable(tcx, n),
+                                   |n| is_output(n));
 
         let mut hashes = FxHashMap();
         for input_index in input_nodes {
@@ -81,8 +82,8 @@ impl<'q> Predecessors<'q> {
             // Not all inputs might have been reachable from an output node,
             // but we still want their hash for our unit tests.
             let hir_nodes = query.graph.all_nodes().iter().filter_map(|node| {
-                match node.data {
-                    DepNode::Hir(_) => Some(&node.data),
+                match node.data.kind {
+                    DepKind::Hir => Some(&node.data),
                     _ => None,
                 }
             });
@@ -93,7 +94,7 @@ impl<'q> Predecessors<'q> {
             }
         }
 
-        let bootstrap_outputs: Vec<&'q DepNode<DefId>> =
+        let bootstrap_outputs: Vec<&'q DepNode> =
             (0 .. graph.len_nodes())
             .map(NodeIndex)
             .filter(|&n| graph.incoming_edges(n).next().is_none())
diff --git a/src/librustc_incremental/persist/save.rs b/src/librustc_incremental/persist/save.rs
index 01db756f9de..867452d97e8 100644
--- a/src/librustc_incremental/persist/save.rs
+++ b/src/librustc_incremental/persist/save.rs
@@ -11,7 +11,6 @@
 use rustc::dep_graph::DepNode;
 use rustc::hir::def_id::DefId;
 use rustc::hir::svh::Svh;
-use rustc::hir::map::DefPathHash;
 use rustc::ich::Fingerprint;
 use rustc::middle::cstore::EncodedMetadataHashes;
 use rustc::session::Session;
@@ -174,19 +173,15 @@ pub fn encode_dep_graph(tcx: TyCtxt,
     // First encode the commandline arguments hash
     tcx.sess.opts.dep_tracking_hash().encode(encoder)?;
 
-    let to_hash_based_node = |dep_node: &DepNode<DefId>| {
-        dep_node.map_def(|&def_id| Some(tcx.def_path_hash(def_id))).unwrap()
-    };
-
     // NB: We rely on this Vec being indexable by reduced_graph's NodeIndex.
-    let nodes: IndexVec<DepNodeIndex, DepNode<DefPathHash>> = preds
+    let mut nodes: IndexVec<DepNodeIndex, DepNode> = preds
         .reduced_graph
         .all_nodes()
         .iter()
-        .map(|node| to_hash_based_node(node.data))
+        .map(|node| node.data.clone())
         .collect();
 
-    let mut edge_list_indices = Vec::with_capacity(nodes.len());
+    let mut edge_list_indices = IndexVec::with_capacity(nodes.len());
     let mut edge_list_data = Vec::with_capacity(preds.reduced_graph.len_edges());
 
     for node_index in 0 .. nodes.len() {
@@ -201,34 +196,62 @@ pub fn encode_dep_graph(tcx: TyCtxt,
         edge_list_indices.push((start, end));
     }
 
-    // Let's make we had no overflow there.
+    // Let's make sure we had no overflow there.
     assert!(edge_list_data.len() <= ::std::u32::MAX as usize);
     // Check that we have a consistent number of edges.
     assert_eq!(edge_list_data.len(), preds.reduced_graph.len_edges());
 
-    let bootstrap_outputs = preds
-        .bootstrap_outputs
-        .iter()
-        .map(|n| to_hash_based_node(n))
-        .collect();
+    let bootstrap_outputs = preds.bootstrap_outputs
+                                 .iter()
+                                 .map(|dep_node| (**dep_node).clone())
+                                 .collect();
+
+    // Next, build the map of content hashes. To this end, we need to transform
+    // the (DepNode -> Fingerprint) map that we have into a
+    // (DepNodeIndex -> Fingerprint) map. This may necessitate adding nodes back
+    // to the dep-graph that have been filtered out during reduction.
+    let content_hashes = {
+        // We have to build a (DepNode -> DepNodeIndex) map. We over-allocate a
+        // little because we expect some more nodes to be added.
+        let capacity = (nodes.len() * 120) / 100;
+        let mut node_to_index = FxHashMap::with_capacity_and_hasher(capacity,
+                                                                    Default::default());
+        // Add the nodes we already have in the graph.
+        node_to_index.extend(nodes.iter_enumerated()
+                                  .map(|(index, &node)| (node, index)));
+
+        let mut content_hashes = Vec::with_capacity(preds.hashes.len());
+
+        for (&&dep_node, &hash) in preds.hashes.iter() {
+            let dep_node_index = *node_to_index
+                .entry(dep_node)
+                .or_insert_with(|| {
+                    // There is no DepNodeIndex for this DepNode yet. This
+                    // happens when the DepNode got filtered out during graph
+                    // reduction. Since we have a content hash for the DepNode,
+                    // we add it back to the graph.
+                    let next_index = nodes.len();
+                    nodes.push(dep_node);
+
+                    debug_assert_eq!(next_index, edge_list_indices.len());
+                    // Push an empty list of edges
+                    edge_list_indices.push((0,0));
+
+                    DepNodeIndex::new(next_index)
+                });
+
+            content_hashes.push((dep_node_index, hash));
+        }
 
-    let hashes = preds
-        .hashes
-        .iter()
-        .map(|(&dep_node, &hash)| {
-            SerializedHash {
-                dep_node: to_hash_based_node(dep_node),
-                hash: hash,
-            }
-        })
-        .collect();
+        content_hashes
+    };
 
     let graph = SerializedDepGraph {
         nodes,
         edge_list_indices,
         edge_list_data,
         bootstrap_outputs,
-        hashes,
+        hashes: content_hashes,
     };
 
     // Encode the graph data.
diff --git a/src/librustc_metadata/cstore.rs b/src/librustc_metadata/cstore.rs
index ed67616e58f..e572be9ffe7 100644
--- a/src/librustc_metadata/cstore.rs
+++ b/src/librustc_metadata/cstore.rs
@@ -255,6 +255,13 @@ impl CStore {
     pub fn do_extern_mod_stmt_cnum(&self, emod_id: ast::NodeId) -> Option<CrateNum> {
         self.extern_mod_crate_map.borrow().get(&emod_id).cloned()
     }
+
+    pub fn read_dep_node(&self, def_id: DefId) {
+        use rustc::middle::cstore::CrateStore;
+        let def_path_hash = self.def_path_hash(def_id);
+        let dep_node = def_path_hash.to_dep_node(::rustc::dep_graph::DepKind::MetaData);
+        self.dep_graph.read(dep_node);
+    }
 }
 
 impl CrateMetadata {
diff --git a/src/librustc_metadata/cstore_impl.rs b/src/librustc_metadata/cstore_impl.rs
index 529f7613b05..4cbcfe15c0c 100644
--- a/src/librustc_metadata/cstore_impl.rs
+++ b/src/librustc_metadata/cstore_impl.rs
@@ -22,8 +22,6 @@ use rustc::session::Session;
 use rustc::ty::{self, TyCtxt};
 use rustc::ty::maps::Providers;
 use rustc::hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX, LOCAL_CRATE};
-
-use rustc::dep_graph::{DepNode};
 use rustc::hir::map::{DefKey, DefPath, DisambiguatedDefPathData, DefPathHash};
 use rustc::hir::map::definitions::{DefPathTable, GlobalMetaDataKind};
 use rustc::util::nodemap::{NodeSet, DefIdMap};
@@ -48,7 +46,10 @@ macro_rules! provide {
                                         DepTrackingMapConfig>::Value {
                 assert!(!$def_id.is_local());
 
-                $tcx.dep_graph.read(DepNode::MetaData($def_id));
+                let def_path_hash = $tcx.def_path_hash($def_id);
+                let dep_node = def_path_hash.to_dep_node(::rustc::dep_graph::DepKind::MetaData);
+
+                $tcx.dep_graph.read(dep_node);
 
                 let $cdata = $tcx.sess.cstore.crate_data_as_rc_any($def_id.krate);
                 let $cdata = $cdata.downcast_ref::<cstore::CrateMetadata>()
@@ -140,12 +141,12 @@ impl CrateStore for cstore::CStore {
     }
 
     fn visibility(&self, def: DefId) -> ty::Visibility {
-        self.dep_graph.read(DepNode::MetaData(def));
+        self.read_dep_node(def);
         self.get_crate_data(def.krate).get_visibility(def.index)
     }
 
     fn item_generics_cloned(&self, def: DefId) -> ty::Generics {
-        self.dep_graph.read(DepNode::MetaData(def));
+        self.read_dep_node(def);
         self.get_crate_data(def.krate).get_generics(def.index)
     }
 
@@ -161,19 +162,19 @@ impl CrateStore for cstore::CStore {
 
     fn impl_defaultness(&self, def: DefId) -> hir::Defaultness
     {
-        self.dep_graph.read(DepNode::MetaData(def));
+        self.read_dep_node(def);
         self.get_crate_data(def.krate).get_impl_defaultness(def.index)
     }
 
     fn associated_item_cloned(&self, def: DefId) -> ty::AssociatedItem
     {
-        self.dep_graph.read(DepNode::MetaData(def));
+        self.read_dep_node(def);
         self.get_crate_data(def.krate).get_associated_item(def.index)
     }
 
     fn is_const_fn(&self, did: DefId) -> bool
     {
-        self.dep_graph.read(DepNode::MetaData(did));
+        self.read_dep_node(did);
         self.get_crate_data(did.krate).is_const_fn(did.index)
     }
 
@@ -344,13 +345,13 @@ impl CrateStore for cstore::CStore {
 
     fn struct_field_names(&self, def: DefId) -> Vec<ast::Name>
     {
-        self.dep_graph.read(DepNode::MetaData(def));
+        self.read_dep_node(def);
         self.get_crate_data(def.krate).get_struct_field_names(def.index)
     }
 
     fn item_children(&self, def_id: DefId, sess: &Session) -> Vec<def::Export>
     {
-        self.dep_graph.read(DepNode::MetaData(def_id));
+        self.read_dep_node(def_id);
         let mut result = vec![];
         self.get_crate_data(def_id.krate)
             .each_child_of_item(def_id.index, |child| result.push(child), sess);
@@ -398,11 +399,12 @@ impl CrateStore for cstore::CStore {
                            tcx: TyCtxt<'a, 'tcx, 'tcx>,
                            def_id: DefId)
                            -> &'tcx hir::Body {
-        if let Some(cached) = tcx.hir.get_inlined_body(def_id) {
+        self.read_dep_node(def_id);
+
+        if let Some(cached) = tcx.hir.get_inlined_body_untracked(def_id) {
             return cached;
         }
 
-        self.dep_graph.read(DepNode::MetaData(def_id));
         debug!("item_body({:?}): inlining item", def_id);
 
         self.get_crate_data(def_id.krate).item_body(tcx, def_id.index)
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index d4baaa39d5d..92d9a800888 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -13,7 +13,7 @@
 use cstore::{self, CrateMetadata, MetadataBlob, NativeLibrary};
 use schema::*;
 
-use rustc::dep_graph::{DepGraph, DepNode};
+use rustc::dep_graph::{DepGraph, DepNode, DepKind};
 use rustc::hir::map::{DefKey, DefPath, DefPathData, DefPathHash};
 use rustc::hir::map::definitions::GlobalMetaDataKind;
 use rustc::hir;
@@ -876,7 +876,8 @@ impl<'a, 'tcx> CrateMetadata {
             return Rc::new([]);
         }
 
-        dep_graph.read(DepNode::MetaData(self.local_def_id(node_id)));
+        let dep_node = self.def_path_hash(node_id).to_dep_node(DepKind::MetaData);
+        dep_graph.read(dep_node);
 
         if let Some(&Some(ref val)) =
             self.attribute_cache.borrow()[node_as].get(node_index) {
@@ -1194,8 +1195,9 @@ impl<'a, 'tcx> CrateMetadata {
         self.codemap_import_info.borrow()
     }
 
-    pub fn metadata_dep_node(&self, kind: GlobalMetaDataKind) -> DepNode<DefId> {
+    pub fn metadata_dep_node(&self, kind: GlobalMetaDataKind) -> DepNode {
         let def_index = kind.def_index(&self.def_path_table);
-        DepNode::MetaData(self.local_def_id(def_index))
+        let def_path_hash = self.def_path_table.def_path_hash(def_index);
+        def_path_hash.to_dep_node(DepKind::MetaData)
     }
 }
diff --git a/src/librustc_metadata/schema.rs b/src/librustc_metadata/schema.rs
index 9180f9100ad..1337f90efa7 100644
--- a/src/librustc_metadata/schema.rs
+++ b/src/librustc_metadata/schema.rs
@@ -203,7 +203,7 @@ impl<T> Tracked<T> {
         }
     }
 
-    pub fn get(&self, dep_graph: &DepGraph, dep_node: DepNode<DefId>) -> &T {
+    pub fn get(&self, dep_graph: &DepGraph, dep_node: DepNode) -> &T {
         dep_graph.read(dep_node);
         &self.state
     }
diff --git a/src/librustc_trans/back/link.rs b/src/librustc_trans/back/link.rs
index e57cbb1c910..e4939db5759 100644
--- a/src/librustc_trans/back/link.rs
+++ b/src/librustc_trans/back/link.rs
@@ -23,7 +23,7 @@ use rustc::middle::dependency_format::Linkage;
 use CrateTranslation;
 use rustc::util::common::time;
 use rustc::util::fs::fix_windows_verbatim_for_gcc;
-use rustc::dep_graph::DepNode;
+use rustc::dep_graph::{DepKind, DepNode};
 use rustc::hir::def_id::CrateNum;
 use rustc::hir::svh::Svh;
 use rustc_back::tempdir::TempDir;
@@ -134,8 +134,9 @@ pub fn find_crate_name(sess: Option<&Session>,
 }
 
 pub fn build_link_meta(incremental_hashes_map: &IncrementalHashesMap) -> LinkMeta {
+    let krate_dep_node = &DepNode::new_no_params(DepKind::Krate);
     let r = LinkMeta {
-        crate_hash: Svh::new(incremental_hashes_map[&DepNode::Krate].to_smaller_hash()),
+        crate_hash: Svh::new(incremental_hashes_map[krate_dep_node].to_smaller_hash()),
     };
     info!("{:?}", r);
     return r;
diff --git a/src/librustc_trans/partitioning.rs b/src/librustc_trans/partitioning.rs
index df8984e6d24..ead442d3388 100644
--- a/src/librustc_trans/partitioning.rs
+++ b/src/librustc_trans/partitioning.rs
@@ -167,8 +167,8 @@ impl<'tcx> CodegenUnit<'tcx> {
         WorkProductId::from_cgu_name(self.name())
     }
 
-    pub fn work_product_dep_node(&self) -> DepNode<DefId> {
-        DepNode::WorkProduct(self.work_product_id())
+    pub fn work_product_dep_node(&self) -> DepNode {
+        self.work_product_id().to_dep_node()
     }
 
     pub fn compute_symbol_name_hash<'a>(&self,
diff --git a/src/librustc_trans/trans_item.rs b/src/librustc_trans/trans_item.rs
index 392ee71d52b..2a36ef9358e 100644
--- a/src/librustc_trans/trans_item.rs
+++ b/src/librustc_trans/trans_item.rs
@@ -23,7 +23,7 @@ use common;
 use declare;
 use llvm;
 use monomorphize::Instance;
-use rustc::dep_graph::DepNode;
+use rustc::dep_graph::DepKind;
 use rustc::hir;
 use rustc::hir::def_id::DefId;
 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
@@ -75,14 +75,16 @@ impl<'a, 'tcx> TransItem<'tcx> {
 
         match *self {
             TransItem::Static(node_id) => {
-                let def_id = ccx.tcx().hir.local_def_id(node_id);
-                let _task = ccx.tcx().dep_graph.in_task(DepNode::TransCrateItem(def_id)); // (*)
-                let item = ccx.tcx().hir.expect_item(node_id);
+                let tcx = ccx.tcx();
+                let def_id = tcx.hir.local_def_id(node_id);
+                let dep_node = def_id.to_dep_node(tcx, DepKind::TransCrateItem);
+                let _task = ccx.tcx().dep_graph.in_task(dep_node); // (*)
+                let item = tcx.hir.expect_item(node_id);
                 if let hir::ItemStatic(_, m, _) = item.node {
                     match consts::trans_static(&ccx, m, item.id, &item.attrs) {
                         Ok(_) => { /* Cool, everything's alright. */ },
                         Err(err) => {
-                            err.report(ccx.tcx(), item.span, "static");
+                            err.report(tcx, item.span, "static");
                         }
                     };
                 } else {
@@ -99,7 +101,8 @@ impl<'a, 'tcx> TransItem<'tcx> {
             }
             TransItem::Fn(instance) => {
                 let _task = ccx.tcx().dep_graph.in_task(
-                    DepNode::TransCrateItem(instance.def_id())); // (*)
+                    instance.def_id()
+                            .to_dep_node(ccx.tcx(), DepKind::TransCrateItem)); // (*)
 
                 base::trans_instance(&ccx, instance);
             }
diff --git a/src/librustc_typeck/coherence/inherent_impls.rs b/src/librustc_typeck/coherence/inherent_impls.rs
index f7ebc210442..e24d7660021 100644
--- a/src/librustc_typeck/coherence/inherent_impls.rs
+++ b/src/librustc_typeck/coherence/inherent_impls.rs
@@ -17,7 +17,7 @@
 //! `tcx.inherent_impls(def_id)`). That value, however,
 //! is computed by selecting an idea from this table.
 
-use rustc::dep_graph::DepNode;
+use rustc::dep_graph::DepKind;
 use rustc::hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
 use rustc::hir;
 use rustc::hir::itemlikevisit::ItemLikeVisitor;
@@ -79,7 +79,8 @@ pub fn inherent_impls<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     });
 
     for &impl_def_id in &result[..] {
-        tcx.dep_graph.read(DepNode::Hir(impl_def_id));
+        let def_path_hash = tcx.def_path_hash(impl_def_id);
+        tcx.dep_graph.read(def_path_hash.to_dep_node(DepKind::Hir));
     }
 
     result
diff --git a/src/librustc_typeck/coherence/overlap.rs b/src/librustc_typeck/coherence/overlap.rs
index ba1d7b18e8c..781e323dea3 100644
--- a/src/librustc_typeck/coherence/overlap.rs
+++ b/src/librustc_typeck/coherence/overlap.rs
@@ -15,7 +15,7 @@
 use rustc::traits;
 use rustc::ty::{self, TyCtxt, TypeFoldable};
 use syntax::ast;
-use rustc::dep_graph::DepNode;
+use rustc::dep_graph::DepKind;
 use rustc::hir;
 use rustc::hir::itemlikevisit::ItemLikeVisitor;
 
@@ -39,7 +39,8 @@ pub fn check_impl<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, node_id: ast::NodeId) {
     }
 
     let _task =
-        tcx.dep_graph.in_task(DepNode::CoherenceOverlapCheck(trait_def_id));
+      tcx.dep_graph.in_task(trait_def_id.to_dep_node(tcx,
+                                                     DepKind::CoherenceOverlapCheck));
 
     // Trigger building the specialization graph for the trait of this impl.
     // This will detect any overlap errors.
diff --git a/src/librustc_typeck/variance/constraints.rs b/src/librustc_typeck/variance/constraints.rs
index cb2ee7dd1bc..c434edb1c31 100644
--- a/src/librustc_typeck/variance/constraints.rs
+++ b/src/librustc_typeck/variance/constraints.rs
@@ -15,7 +15,7 @@
 
 use hir::def_id::DefId;
 use middle::resolve_lifetime as rl;
-use rustc::dep_graph::{AssertDepGraphSafe, DepNode};
+use rustc::dep_graph::{AssertDepGraphSafe, DepKind};
 use rustc::ty::subst::Substs;
 use rustc::ty::{self, Ty, TyCtxt};
 use rustc::hir::map as hir_map;
@@ -104,7 +104,8 @@ impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ConstraintContext<'a, 'tcx> {
             hir::ItemEnum(..) |
             hir::ItemStruct(..) |
             hir::ItemUnion(..) => {
-                tcx.dep_graph.with_task(DepNode::ItemVarianceConstraints(def_id),
+                let dep_node = def_id.to_dep_node(tcx, DepKind::ItemVarianceConstraints);
+                tcx.dep_graph.with_task(dep_node,
                                         AssertDepGraphSafe(self),
                                         def_id,
                                         visit_item_task);
diff --git a/src/librustc_typeck/variance/mod.rs b/src/librustc_typeck/variance/mod.rs
index 1afe2725ac8..8f9f40ca40b 100644
--- a/src/librustc_typeck/variance/mod.rs
+++ b/src/librustc_typeck/variance/mod.rs
@@ -12,7 +12,7 @@
 //! parameters. See README.md for details.
 
 use arena;
-use rustc::dep_graph::DepNode;
+use rustc::dep_graph::DepKind;
 use rustc::hir;
 use rustc::hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
 use rustc::ty::{self, CrateVariancesMap, TyCtxt};
@@ -72,12 +72,15 @@ fn variances_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, item_def_id: DefId)
             // Lacking red/green, we read the variances for all items here
             // but ignore the dependencies, then re-synthesize the ones we need.
             let crate_map = tcx.dep_graph.with_ignore(|| tcx.crate_variances(LOCAL_CRATE));
-            tcx.dep_graph.read(DepNode::ItemVarianceConstraints(item_def_id));
+            let dep_node = item_def_id.to_dep_node(tcx, DepKind::ItemVarianceConstraints);
+            tcx.dep_graph.read(dep_node);
             for &dep_def_id in crate_map.dependencies.less_than(&item_def_id) {
                 if dep_def_id.is_local() {
-                    tcx.dep_graph.read(DepNode::ItemVarianceConstraints(dep_def_id));
+                    let dep_node = dep_def_id.to_dep_node(tcx, DepKind::ItemVarianceConstraints);
+                    tcx.dep_graph.read(dep_node);
                 } else {
-                    tcx.dep_graph.read(DepNode::ItemVariances(dep_def_id));
+                    let dep_node = dep_def_id.to_dep_node(tcx, DepKind::ItemVariances);
+                    tcx.dep_graph.read(dep_node);
                 }
             }
 
diff --git a/src/test/incremental/dirty_clean.rs b/src/test/incremental/dirty_clean.rs
index 9f20128de4f..ce9865103dc 100644
--- a/src/test/incremental/dirty_clean.rs
+++ b/src/test/incremental/dirty_clean.rs
@@ -38,8 +38,8 @@ mod y {
     #[rustc_clean(label="TypeckTables", cfg="cfail2")]
     #[rustc_clean(label="TransCrateItem", cfg="cfail2")]
     pub fn y() {
-        //[cfail2]~^ ERROR `TypeckTables("y::y")` not found in dep graph, but should be clean
-        //[cfail2]~| ERROR `TransCrateItem("y::y")` not found in dep graph, but should be clean
+        //[cfail2]~^ ERROR `TypeckTables(y::y)` not found in dep graph, but should be clean
+        //[cfail2]~| ERROR `TransCrateItem(y::y)` not found in dep graph, but should be clean
         x::x();
     }
 }
@@ -48,7 +48,7 @@ mod z {
     #[rustc_dirty(label="TypeckTables", cfg="cfail2")]
     #[rustc_dirty(label="TransCrateItem", cfg="cfail2")]
     pub fn z() {
-        //[cfail2]~^ ERROR `TypeckTables("z::z")` found in dep graph, but should be dirty
-        //[cfail2]~| ERROR `TransCrateItem("z::z")` found in dep graph, but should be dirty
+        //[cfail2]~^ ERROR `TypeckTables(z::z)` found in dep graph, but should be dirty
+        //[cfail2]~| ERROR `TransCrateItem(z::z)` found in dep graph, but should be dirty
     }
 }