incr.comp.: Hash more pieces of crate metadata to detect changes there.

32 files changed, 1477 insertions, 828 deletions

diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index 12e0d4d3ea2..af425a95fb1 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -51,6 +51,9 @@ pub enum DepNode<D: Clone + Debug> {
     // in an extern crate.
     MetaData(D),
 
+    // Represents some piece of metadata global to its crate.
+    GlobalMetaData(D, GlobalMetaDataKind),
+
     // Represents some artifact that we save to disk. Note that these
     // do not have a def-id as part of their identifier.
     WorkProduct(Arc<WorkProductId>),
@@ -79,7 +82,6 @@ pub enum DepNode<D: Clone + Debug> {
     MirKeys,
     LateLintCheck,
     TransCrateItem(D),
-    TransInlinedItem(D),
     TransWriteMetadata,
     CrateVariances,
 
@@ -157,6 +159,7 @@ pub enum DepNode<D: Clone + Debug> {
     DefSpan(D),
     Stability(D),
     Deprecation(D),
+    FileMap(D, Arc<String>),
 }
 
 impl<D: Clone + Debug> DepNode<D> {
@@ -234,7 +237,6 @@ impl<D: Clone + Debug> DepNode<D> {
             RegionMaps(ref d) => op(d).map(RegionMaps),
             RvalueCheck(ref d) => op(d).map(RvalueCheck),
             TransCrateItem(ref d) => op(d).map(TransCrateItem),
-            TransInlinedItem(ref d) => op(d).map(TransInlinedItem),
             AssociatedItems(ref d) => op(d).map(AssociatedItems),
             ItemSignature(ref d) => op(d).map(ItemSignature),
             ItemVariances(ref d) => op(d).map(ItemVariances),
@@ -271,6 +273,8 @@ impl<D: Clone + Debug> DepNode<D> {
             DefSpan(ref d) => op(d).map(DefSpan),
             Stability(ref d) => op(d).map(Stability),
             Deprecation(ref d) => op(d).map(Deprecation),
+            GlobalMetaData(ref d, kind) => op(d).map(|d| GlobalMetaData(d, kind)),
+            FileMap(ref d, ref file_name) => op(d).map(|d| FileMap(d, file_name.clone())),
         }
     }
 }
@@ -282,3 +286,16 @@ impl<D: Clone + Debug> DepNode<D> {
 /// them even in the absence of a tcx.)
 #[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
 pub struct WorkProductId(pub String);
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
+pub enum GlobalMetaDataKind {
+    Krate,
+    CrateDeps,
+    DylibDependencyFormats,
+    LangItems,
+    LangItemsMissing,
+    NativeLibraries,
+    CodeMap,
+    Impls,
+    ExportedSymbols,
+}
diff --git a/src/librustc/dep_graph/mod.rs b/src/librustc/dep_graph/mod.rs
index 809bed939f5..822b61df7a4 100644
--- a/src/librustc/dep_graph/mod.rs
+++ b/src/librustc/dep_graph/mod.rs
@@ -22,6 +22,7 @@ mod thread;
 pub use self::dep_tracking_map::{DepTrackingMap, DepTrackingMapConfig};
 pub use self::dep_node::DepNode;
 pub use self::dep_node::WorkProductId;
+pub use self::dep_node::GlobalMetaDataKind;
 pub use self::graph::DepGraph;
 pub use self::graph::WorkProduct;
 pub use self::query::DepGraphQuery;
diff --git a/src/librustc/hir/svh.rs b/src/librustc/hir/svh.rs
index ae1f9d3028c..a6cfcb710ed 100644
--- a/src/librustc/hir/svh.rs
+++ b/src/librustc/hir/svh.rs
@@ -66,3 +66,7 @@ impl Decodable for Svh {
          .map(Svh::new)
     }
 }
+
+impl_stable_hash_for!(struct Svh {
+    hash
+});
diff --git a/src/librustc/ich/caching_codemap_view.rs b/src/librustc/ich/caching_codemap_view.rs
index 1278d9f5171..b21c3a2b216 100644
--- a/src/librustc/ich/caching_codemap_view.rs
+++ b/src/librustc/ich/caching_codemap_view.rs
@@ -8,10 +8,14 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use ty::TyCtxt;
+use dep_graph::{DepGraph, DepNode};
+use hir::def_id::{DefId, CrateNum, CRATE_DEF_INDEX};
+use rustc_data_structures::bitvec::BitVector;
 use std::rc::Rc;
+use std::sync::Arc;
 use syntax::codemap::CodeMap;
 use syntax_pos::{BytePos, FileMap};
+use ty::TyCtxt;
 
 #[derive(Clone)]
 struct CacheEntry {
@@ -20,30 +24,37 @@ struct CacheEntry {
     line_start: BytePos,
     line_end: BytePos,
     file: Rc<FileMap>,
+    file_index: usize,
 }
 
 pub struct CachingCodemapView<'tcx> {
     codemap: &'tcx CodeMap,
     line_cache: [CacheEntry; 3],
     time_stamp: usize,
+    dep_graph: DepGraph,
+    dep_tracking_reads: BitVector,
 }
 
 impl<'tcx> CachingCodemapView<'tcx> {
     pub fn new<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> CachingCodemapView<'tcx> {
         let codemap = tcx.sess.codemap();
-        let first_file = codemap.files.borrow()[0].clone();
+        let files = codemap.files_untracked();
+        let first_file = files[0].clone();
         let entry = CacheEntry {
             time_stamp: 0,
             line_number: 0,
             line_start: BytePos(0),
             line_end: BytePos(0),
             file: first_file,
+            file_index: 0,
         };
 
         CachingCodemapView {
+            dep_graph: tcx.dep_graph.clone(),
             codemap: codemap,
             line_cache: [entry.clone(), entry.clone(), entry.clone()],
             time_stamp: 0,
+            dep_tracking_reads: BitVector::new(files.len()),
         }
     }
 
@@ -56,6 +67,10 @@ impl<'tcx> CachingCodemapView<'tcx> {
         for cache_entry in self.line_cache.iter_mut() {
             if pos >= cache_entry.line_start && pos < cache_entry.line_end {
                 cache_entry.time_stamp = self.time_stamp;
+                if self.dep_tracking_reads.insert(cache_entry.file_index) {
+                    self.dep_graph.read(dep_node(cache_entry));
+                }
+
                 return Some((cache_entry.file.clone(),
                              cache_entry.line_number,
                              pos - cache_entry.line_start));
@@ -75,7 +90,7 @@ impl<'tcx> CachingCodemapView<'tcx> {
         // If the entry doesn't point to the correct file, fix it up
         if pos < cache_entry.file.start_pos || pos >= cache_entry.file.end_pos {
             let file_valid;
-            let files = self.codemap.files.borrow();
+            let files = self.codemap.files_untracked();
 
             if files.len() > 0 {
                 let file_index = self.codemap.lookup_filemap_idx(pos);
@@ -83,6 +98,7 @@ impl<'tcx> CachingCodemapView<'tcx> {
 
                 if pos >= file.start_pos && pos < file.end_pos {
                     cache_entry.file = file;
+                    cache_entry.file_index = file_index;
                     file_valid = true;
                 } else {
                     file_valid = false;
@@ -104,8 +120,21 @@ impl<'tcx> CachingCodemapView<'tcx> {
         cache_entry.line_end = line_bounds.1;
         cache_entry.time_stamp = self.time_stamp;
 
+        if self.dep_tracking_reads.insert(cache_entry.file_index) {
+            self.dep_graph.read(dep_node(cache_entry));
+        }
+
         return Some((cache_entry.file.clone(),
                      cache_entry.line_number,
                      pos - cache_entry.line_start));
     }
 }
+
+fn dep_node(cache_entry: &CacheEntry) -> DepNode<DefId> {
+    let def_id = DefId {
+        krate: CrateNum::from_u32(cache_entry.file.crate_of_origin),
+        index: CRATE_DEF_INDEX,
+    };
+    let name = Arc::new(cache_entry.file.name.clone());
+    DepNode::FileMap(def_id, name)
+}
diff --git a/src/librustc/ich/impls_cstore.rs b/src/librustc/ich/impls_cstore.rs
new file mode 100644
index 00000000000..e95dbdd15c5
--- /dev/null
+++ b/src/librustc/ich/impls_cstore.rs
@@ -0,0 +1,40 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! This module contains `HashStable` implementations for various data types
+//! from rustc::middle::cstore in no particular order.
+
+use middle;
+
+impl_stable_hash_for!(enum middle::cstore::DepKind {
+    UnexportedMacrosOnly,
+    MacrosOnly,
+    Implicit,
+    Explicit
+});
+
+impl_stable_hash_for!(enum middle::cstore::NativeLibraryKind {
+    NativeStatic,
+    NativeStaticNobundle,
+    NativeFramework,
+    NativeUnknown
+});
+
+impl_stable_hash_for!(struct middle::cstore::NativeLibrary {
+    kind,
+    name,
+    cfg,
+    foreign_items
+});
+
+impl_stable_hash_for!(enum middle::cstore::LinkagePreference {
+    RequireDynamic,
+    RequireStatic
+});
diff --git a/src/librustc/ich/impls_hir.rs b/src/librustc/ich/impls_hir.rs
index 3aeee1c1b98..abc51601b6e 100644
--- a/src/librustc/ich/impls_hir.rs
+++ b/src/librustc/ich/impls_hir.rs
@@ -1120,3 +1120,11 @@ impl_stable_hash_for!(struct hir::def::Export {
     def,
     span
 });
+
+impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ::middle::lang_items::LangItem {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          _: &mut StableHashingContext<'a, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        ::std::hash::Hash::hash(self, hasher);
+    }
+}
diff --git a/src/librustc/ich/impls_syntax.rs b/src/librustc/ich/impls_syntax.rs
index 26734500001..7138db01339 100644
--- a/src/librustc/ich/impls_syntax.rs
+++ b/src/librustc/ich/impls_syntax.rs
@@ -19,7 +19,9 @@ use std::mem;
 use syntax::ast;
 use syntax::parse::token;
 use syntax::tokenstream;
-use syntax_pos::Span;
+use syntax_pos::{Span, FileMap};
+
+use hir::def_id::{DefId, CrateNum, CRATE_DEF_INDEX};
 
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
                                            StableHasherResult};
@@ -299,3 +301,79 @@ fn hash_token<'a, 'tcx, W: StableHasherResult>(token: &token::Token,
         token::Token::Shebang(val) => val.hash_stable(hcx, hasher),
     }
 }
+
+impl_stable_hash_for_spanned!(::syntax::ast::NestedMetaItemKind);
+
+impl_stable_hash_for!(enum ::syntax::ast::NestedMetaItemKind {
+    MetaItem(meta_item),
+    Literal(lit)
+});
+
+impl_stable_hash_for!(struct ::syntax::ast::MetaItem {
+    name,
+    node,
+    span
+});
+
+impl_stable_hash_for!(enum ::syntax::ast::MetaItemKind {
+    Word,
+    List(nested_items),
+    NameValue(lit)
+});
+
+impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for FileMap {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let FileMap {
+            ref name,
+            name_was_remapped,
+            crate_of_origin,
+            // Do not hash the source as it is not encoded
+            src: _,
+            start_pos,
+            end_pos: _,
+            ref lines,
+            ref multibyte_chars,
+        } = *self;
+
+        name.hash_stable(hcx, hasher);
+        name_was_remapped.hash_stable(hcx, hasher);
+
+        DefId {
+            krate: CrateNum::from_u32(crate_of_origin),
+            index: CRATE_DEF_INDEX,
+        }.hash_stable(hcx, hasher);
+
+        // We only hash the relative position within this filemap
+        let lines = lines.borrow();
+        lines.len().hash_stable(hcx, hasher);
+        for &line in lines.iter() {
+            stable_byte_pos(line, start_pos).hash_stable(hcx, hasher);
+        }
+
+        // We only hash the relative position within this filemap
+        let multibyte_chars = multibyte_chars.borrow();
+        multibyte_chars.len().hash_stable(hcx, hasher);
+        for &char_pos in multibyte_chars.iter() {
+            stable_multibyte_char(char_pos, start_pos).hash_stable(hcx, hasher);
+        }
+    }
+}
+
+fn stable_byte_pos(pos: ::syntax_pos::BytePos,
+                   filemap_start: ::syntax_pos::BytePos)
+                   -> u32 {
+    pos.0 - filemap_start.0
+}
+
+fn stable_multibyte_char(mbc: ::syntax_pos::MultiByteChar,
+                         filemap_start: ::syntax_pos::BytePos)
+                         -> (u32, u32) {
+    let ::syntax_pos::MultiByteChar {
+        pos,
+        bytes,
+    } = mbc;
+
+    (pos.0 - filemap_start.0, bytes as u32)
+}
diff --git a/src/librustc/ich/mod.rs b/src/librustc/ich/mod.rs
index d70ed051ac4..d881a1cc45a 100644
--- a/src/librustc/ich/mod.rs
+++ b/src/librustc/ich/mod.rs
@@ -19,6 +19,7 @@ mod caching_codemap_view;
 mod hcx;
 
 mod impls_const_math;
+mod impls_cstore;
 mod impls_hir;
 mod impls_mir;
 mod impls_ty;
diff --git a/src/librustc/middle/cstore.rs b/src/librustc/middle/cstore.rs
index 303c5059e7c..16b3fcd2f8c 100644
--- a/src/librustc/middle/cstore.rs
+++ b/src/librustc/middle/cstore.rs
@@ -23,6 +23,7 @@
 // probably get a better home if someone can find one.
 
 use hir::def;
+use dep_graph::DepNode;
 use hir::def_id::{CrateNum, DefId, DefIndex};
 use hir::map as hir_map;
 use hir::map::definitions::{Definitions, DefKey, DisambiguatedDefPathData};
@@ -161,7 +162,16 @@ pub struct ExternCrate {
 
 pub struct EncodedMetadata {
     pub raw_data: Vec<u8>,
-    pub hashes: Vec<EncodedMetadataHash>,
+    pub hashes: EncodedMetadataHashes,
+}
+
+impl EncodedMetadata {
+    pub fn new() -> EncodedMetadata {
+        EncodedMetadata {
+            raw_data: Vec::new(),
+            hashes: EncodedMetadataHashes::new(),
+        }
+    }
 }
 
 /// The hash for some metadata that (when saving) will be exported
@@ -173,6 +183,24 @@ pub struct EncodedMetadataHash {
     pub hash: ich::Fingerprint,
 }
 
+/// The hash for some metadata that (when saving) will be exported
+/// from this crate, or which (when importing) was exported by an
+/// upstream crate.
+#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
+pub struct EncodedMetadataHashes {
+    pub entry_hashes: Vec<EncodedMetadataHash>,
+    pub global_hashes: Vec<(DepNode<()>, ich::Fingerprint)>,
+}
+
+impl EncodedMetadataHashes {
+    pub fn new() -> EncodedMetadataHashes {
+        EncodedMetadataHashes {
+            entry_hashes: Vec::new(),
+            global_hashes: Vec::new(),
+        }
+    }
+}
+
 /// A store of Rust crates, through with their metadata
 /// can be accessed.
 pub trait CrateStore {
diff --git a/src/librustc/session/mod.rs b/src/librustc/session/mod.rs
index ec3eaa124c3..2e2d5a6bd4d 100644
--- a/src/librustc/session/mod.rs
+++ b/src/librustc/session/mod.rs
@@ -11,8 +11,8 @@
 pub use self::code_stats::{CodeStats, DataTypeKind, FieldInfo};
 pub use self::code_stats::{SizeKind, TypeSizeInfo, VariantInfo};
 
-use dep_graph::DepGraph;
-use hir::def_id::{CrateNum, DefIndex};
+use dep_graph::{DepGraph, DepNode};
+use hir::def_id::{DefId, CrateNum, DefIndex, CRATE_DEF_INDEX};
 use lint;
 use middle::cstore::CrateStore;
 use middle::dependency_format;
@@ -32,7 +32,7 @@ use syntax::parse::ParseSess;
 use syntax::symbol::Symbol;
 use syntax::{ast, codemap};
 use syntax::feature_gate::AttributeType;
-use syntax_pos::{Span, MultiSpan};
+use syntax_pos::{Span, MultiSpan, FileMap};
 
 use rustc_back::{LinkerFlavor, PanicStrategy};
 use rustc_back::target::Target;
@@ -48,6 +48,7 @@ use std::io::Write;
 use std::rc::Rc;
 use std::fmt;
 use std::time::Duration;
+use std::sync::Arc;
 use libc::c_int;
 
 mod code_stats;
@@ -627,6 +628,22 @@ pub fn build_session_(sopts: config::Options,
         }
     };
     let target_cfg = config::build_target_config(&sopts, &span_diagnostic);
+
+    // Hook up the codemap with a callback that allows it to register FileMap
+    // accesses with the dependency graph.
+    let cm_depgraph = dep_graph.clone();
+    let codemap_dep_tracking_callback = Box::new(move |filemap: &FileMap| {
+        let def_id = DefId {
+            krate: CrateNum::from_u32(filemap.crate_of_origin),
+            index: CRATE_DEF_INDEX,
+        };
+        let name = Arc::new(filemap.name.clone());
+        let dep_node = DepNode::FileMap(def_id, name);
+
+        cm_depgraph.read(dep_node);
+    });
+    codemap.set_dep_tracking_callback(codemap_dep_tracking_callback);
+
     let p_s = parse::ParseSess::with_span_handler(span_diagnostic, codemap);
     let default_sysroot = match sopts.maybe_sysroot {
         Some(_) => None,
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
index 95f063976d4..635b95d861d 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -283,6 +283,16 @@ impl<CTX> HashStable<CTX> for str {
     }
 }
 
+
+impl<CTX> HashStable<CTX> for String {
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        (&self[..]).hash_stable(hcx, hasher);
+    }
+}
+
 impl<CTX> HashStable<CTX> for bool {
     #[inline]
     fn hash_stable<W: StableHasherResult>(&self,
diff --git a/src/librustc_driver/driver.rs b/src/librustc_driver/driver.rs
index 9f0f567b6ce..5f14890665c 100644
--- a/src/librustc_driver/driver.rs
+++ b/src/librustc_driver/driver.rs
@@ -1155,8 +1155,7 @@ fn write_out_deps(sess: &Session, outputs: &OutputFilenames, crate_name: &str) {
             // Build a list of files used to compile the output and
             // write Makefile-compatible dependency rules
             let files: Vec<String> = sess.codemap()
-                                         .files
-                                         .borrow()
+                                         .files()
                                          .iter()
                                          .filter(|fmap| fmap.is_real_file())
                                          .filter(|fmap| !fmap.is_imported())
diff --git a/src/librustc_incremental/calculate_svh/mod.rs b/src/librustc_incremental/calculate_svh/mod.rs
index c67866971e1..6f5cc1f3f45 100644
--- a/src/librustc_incremental/calculate_svh/mod.rs
+++ b/src/librustc_incremental/calculate_svh/mod.rs
@@ -29,9 +29,10 @@
 
 use std::cell::RefCell;
 use std::hash::Hash;
+use std::sync::Arc;
 use rustc::dep_graph::DepNode;
 use rustc::hir;
-use rustc::hir::def_id::{CRATE_DEF_INDEX, DefId};
+use rustc::hir::def_id::{LOCAL_CRATE, CRATE_DEF_INDEX, DefId};
 use rustc::hir::itemlikevisit::ItemLikeVisitor;
 use rustc::ich::{Fingerprint, StableHashingContext};
 use rustc::ty::TyCtxt;
@@ -60,6 +61,10 @@ impl IncrementalHashesMap {
         }
     }
 
+    pub fn get(&self, k: &DepNode<DefId>) -> Option<&Fingerprint> {
+        self.hashes.get(k)
+    }
+
     pub fn insert(&mut self, k: DepNode<DefId>, v: Fingerprint) -> Option<Fingerprint> {
         self.hashes.insert(k, v)
     }
@@ -140,14 +145,34 @@ impl<'a, 'tcx: 'a> ComputeItemHashesVisitor<'a, 'tcx> {
             let hcx = &mut self.hcx;
             let mut item_hashes: Vec<_> =
                 self.hashes.iter()
-                           .map(|(item_dep_node, &item_hash)| {
-                               // convert from a DepNode<DefId> tp 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();
-                               (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(_) => {
+                                        // We want to incoporate these into the
+                                        // SVH.
+                                    }
+                                    DepNode::FileMap(..) => {
+                                        // These don't make a semantic
+                                        // difference, filter them out.
+                                        return None
+                                    }
+                                    ref other => {
+                                        bug!("Found unexpected DepNode 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();
             item_hashes.sort_unstable(); // avoid artificial dependencies on item ordering
@@ -229,6 +254,24 @@ pub fn compute_incremental_hashes_map<'a, 'tcx: 'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>)
             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);
         }
+
+        for filemap in tcx.sess
+                          .codemap()
+                          .files_untracked()
+                          .iter()
+                          .filter(|fm| !fm.is_imported()) {
+            assert_eq!(LOCAL_CRATE.as_u32(), filemap.crate_of_origin);
+            let def_id = DefId {
+                krate: LOCAL_CRATE,
+                index: CRATE_DEF_INDEX,
+            };
+            let name = Arc::new(filemap.name.clone());
+            let dep_node = DepNode::FileMap(def_id, name);
+            let mut hasher = IchHasher::new();
+            filemap.hash_stable(&mut visitor.hcx, &mut hasher);
+            let fingerprint = hasher.finish();
+            visitor.hashes.insert(dep_node, fingerprint);
+        }
     });
 
     tcx.sess.perf_stats.incr_comp_hashes_count.set(visitor.hashes.len() as u64);
diff --git a/src/librustc_incremental/persist/data.rs b/src/librustc_incremental/persist/data.rs
index 8a1af5dd08d..b016ff34bc5 100644
--- a/src/librustc_incremental/persist/data.rs
+++ b/src/librustc_incremental/persist/data.rs
@@ -99,7 +99,11 @@ pub struct SerializedMetadataHashes {
     /// where `X` refers to some item in this crate. That `X` will be
     /// a `DefPathIndex` that gets retracted to the current `DefId`
     /// (matching the one found in this structure).
-    pub hashes: Vec<EncodedMetadataHash>,
+    pub entry_hashes: Vec<EncodedMetadataHash>,
+
+    /// This map contains fingerprints that are not specific to some DefId but
+    /// describe something global to the whole crate.
+    pub global_hashes: Vec<(DepNode<()>, Fingerprint)>,
 
     /// For each DefIndex (as it occurs in SerializedMetadataHash), this
     /// map stores the DefPathIndex (as it occurs in DefIdDirectory), so
diff --git a/src/librustc_incremental/persist/hash.rs b/src/librustc_incremental/persist/hash.rs
index 9d8ff57e03b..5bc442deafa 100644
--- a/src/librustc_incremental/persist/hash.rs
+++ b/src/librustc_incremental/persist/hash.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 use rustc::dep_graph::DepNode;
-use rustc::hir::def_id::{CrateNum, DefId};
+use rustc::hir::def_id::{CrateNum, DefId, LOCAL_CRATE, CRATE_DEF_INDEX};
 use rustc::hir::svh::Svh;
 use rustc::ich::Fingerprint;
 use rustc::ty::TyCtxt;
@@ -23,11 +23,15 @@ use super::data::*;
 use super::fs::*;
 use super::file_format;
 
+use std::hash::Hash;
+use std::fmt::Debug;
+
 pub struct HashContext<'a, 'tcx: 'a> {
     pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
     incremental_hashes_map: &'a IncrementalHashesMap,
     item_metadata_hashes: FxHashMap<DefId, Fingerprint>,
     crate_hashes: FxHashMap<CrateNum, Svh>,
+    global_metadata_hashes: FxHashMap<DepNode<DefId>, Fingerprint>,
 }
 
 impl<'a, 'tcx> HashContext<'a, 'tcx> {
@@ -39,6 +43,7 @@ impl<'a, 'tcx> HashContext<'a, 'tcx> {
             incremental_hashes_map: incremental_hashes_map,
             item_metadata_hashes: FxHashMap(),
             crate_hashes: FxHashMap(),
+            global_metadata_hashes: FxHashMap(),
         }
     }
 
@@ -46,9 +51,11 @@ impl<'a, 'tcx> HashContext<'a, 'tcx> {
         match *dep_node {
             DepNode::Krate |
             DepNode::Hir(_) |
-            DepNode::HirBody(_) =>
+            DepNode::HirBody(_) |
+            DepNode::FileMap(..) =>
                 true,
-            DepNode::MetaData(def_id) => !def_id.is_local(),
+            DepNode::MetaData(def_id) |
+            DepNode::GlobalMetaData(def_id, _) => !def_id.is_local(),
             _ => false,
         }
     }
@@ -60,7 +67,8 @@ impl<'a, 'tcx> HashContext<'a, 'tcx> {
             }
 
             // HIR nodes (which always come from our crate) are an input:
-            DepNode::Hir(def_id) | DepNode::HirBody(def_id) => {
+            DepNode::Hir(def_id) |
+            DepNode::HirBody(def_id) => {
                 assert!(def_id.is_local(),
                         "cannot hash HIR for non-local def-id {:?} => {:?}",
                         def_id,
@@ -69,12 +77,30 @@ impl<'a, 'tcx> HashContext<'a, 'tcx> {
                 Some(self.incremental_hashes_map[dep_node])
             }
 
+            DepNode::FileMap(def_id, ref name) => {
+                if def_id.is_local() {
+                    Some(self.incremental_hashes_map[dep_node])
+                } else {
+                    Some(self.metadata_hash(DepNode::FileMap(def_id, name.clone()),
+                                            def_id.krate,
+                                            |this| &mut this.global_metadata_hashes))
+                }
+            }
+
             // MetaData from other crates is an *input* to us.
             // 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))
+                Some(self.metadata_hash(def_id,
+                                        def_id.krate,
+                                        |this| &mut this.item_metadata_hashes))
+            }
+
+            DepNode::GlobalMetaData(def_id, kind) => {
+                Some(self.metadata_hash(DepNode::GlobalMetaData(def_id, kind),
+                                        def_id.krate,
+                                        |this| &mut this.global_metadata_hashes))
             }
 
             _ => {
@@ -87,33 +113,37 @@ impl<'a, 'tcx> HashContext<'a, 'tcx> {
         }
     }
 
-    fn metadata_hash(&mut self, def_id: DefId) -> Fingerprint {
-        debug!("metadata_hash(def_id={:?})", def_id);
+    fn metadata_hash<K, C>(&mut self,
+                           key: K,
+                           cnum: CrateNum,
+                           cache: C)
+                           -> Fingerprint
+        where K: Hash + Eq + Debug,
+              C: Fn(&mut Self) -> &mut FxHashMap<K, Fingerprint>,
+    {
+        debug!("metadata_hash(key={:?})", key);
 
-        assert!(!def_id.is_local());
+        debug_assert!(cnum != LOCAL_CRATE);
         loop {
             // check whether we have a result cached for this def-id
-            if let Some(&hash) = self.item_metadata_hashes.get(&def_id) {
-                debug!("metadata_hash: def_id={:?} hash={:?}", def_id, hash);
+            if let Some(&hash) = cache(self).get(&key) {
                 return hash;
             }
 
             // check whether we did not find detailed metadata for this
             // krate; in that case, we just use the krate's overall hash
-            if let Some(&svh) = self.crate_hashes.get(&def_id.krate) {
-                debug!("metadata_hash: def_id={:?} crate_hash={:?}", def_id, svh);
-
+            if let Some(&svh) = self.crate_hashes.get(&cnum) {
                 // micro-"optimization": avoid a cache miss if we ask
                 // for metadata from this particular def-id again.
                 let fingerprint = svh_to_fingerprint(svh);
-                self.item_metadata_hashes.insert(def_id, fingerprint);
+                cache(self).insert(key, fingerprint);
 
                 return fingerprint;
             }
 
             // otherwise, load the data and repeat.
-            self.load_data(def_id.krate);
-            assert!(self.crate_hashes.contains_key(&def_id.krate));
+            self.load_data(cnum);
+            assert!(self.crate_hashes.contains_key(&cnum));
         }
     }
 
@@ -191,7 +221,7 @@ impl<'a, 'tcx> HashContext<'a, 'tcx> {
         }
 
         let serialized_hashes = SerializedMetadataHashes::decode(&mut decoder)?;
-        for serialized_hash in serialized_hashes.hashes {
+        for serialized_hash in serialized_hashes.entry_hashes {
             // the hashes are stored with just a def-index, which is
             // always relative to the old crate; convert that to use
             // our internal crate number
@@ -202,6 +232,24 @@ impl<'a, 'tcx> HashContext<'a, 'tcx> {
             debug!("load_from_data: def_id={:?} hash={}", def_id, serialized_hash.hash);
             assert!(old.is_none(), "already have hash for {:?}", def_id);
         }
+
+        for (dep_node, fingerprint) in serialized_hashes.global_hashes {
+            // Here we need to remap the CrateNum in the DepNode.
+            let def_id = DefId { krate: cnum, index: CRATE_DEF_INDEX };
+            let dep_node = match dep_node {
+                DepNode::GlobalMetaData(_, kind) => DepNode::GlobalMetaData(def_id, kind),
+                DepNode::FileMap(_, name) => DepNode::FileMap(def_id, name),
+                other => {
+                    bug!("unexpected DepNode variant: {:?}", other)
+                }
+            };
+
+            // record the hash for this dep-node
+            debug!("load_from_data: def_node={:?} hash={}", dep_node, fingerprint);
+            let old = self.global_metadata_hashes.insert(dep_node.clone(), fingerprint);
+            assert!(old.is_none(), "already have hash for {:?}", dep_node);
+        }
+
         Ok(())
     }
 }
diff --git a/src/librustc_incremental/persist/load.rs b/src/librustc_incremental/persist/load.rs
index ed2e2e72ee7..7fad600d105 100644
--- a/src/librustc_incremental/persist/load.rs
+++ b/src/librustc_incremental/persist/load.rs
@@ -240,35 +240,40 @@ fn initial_dirty_nodes<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     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 hash in serialized_hashes {
         if let Some(dep_node) = retraced.map(&hash.dep_node) {
-            let current_hash = hcx.hash(&dep_node).unwrap();
-            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(),
-                   current_hash);
-                continue;
-            }
+            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(),
+                       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);
-            }
+                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);
+                }
 
-            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 {
-            if tcx.sess.opts.debugging_opts.incremental_dump_hash {
-                println!("node {:?} is dirty as it was removed",
-                         hash.dep_node);
+                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);
             }
-
-            debug!("initial_dirty_nodes: {:?} is dirty as it was removed",
-                   hash.dep_node);
+        } else {
+            print_removed_message(&hash.dep_node);
         }
 
         dirty_nodes.insert(hash.dep_node.clone(), hash.dep_node.clone());
@@ -382,8 +387,8 @@ fn load_prev_metadata_hashes(tcx: TyCtxt,
 
     debug!("load_prev_metadata_hashes() - Mapping DefIds");
 
-    assert_eq!(serialized_hashes.index_map.len(), serialized_hashes.hashes.len());
-    for serialized_hash in serialized_hashes.hashes {
+    assert_eq!(serialized_hashes.index_map.len(), serialized_hashes.entry_hashes.len());
+    for serialized_hash in serialized_hashes.entry_hashes {
         let def_path_index = serialized_hashes.index_map[&serialized_hash.def_index];
         if let Some(def_id) = retraced.def_id(def_path_index) {
             let old = output.insert(def_id, serialized_hash.hash);
diff --git a/src/librustc_incremental/persist/save.rs b/src/librustc_incremental/persist/save.rs
index 1864009fbdf..06e49e9d37c 100644
--- a/src/librustc_incremental/persist/save.rs
+++ b/src/librustc_incremental/persist/save.rs
@@ -12,7 +12,7 @@ use rustc::dep_graph::DepNode;
 use rustc::hir::def_id::DefId;
 use rustc::hir::svh::Svh;
 use rustc::ich::Fingerprint;
-use rustc::middle::cstore::EncodedMetadataHash;
+use rustc::middle::cstore::EncodedMetadataHashes;
 use rustc::session::Session;
 use rustc::ty::TyCtxt;
 use rustc_data_structures::fx::FxHashMap;
@@ -34,7 +34,7 @@ use super::work_product;
 
 pub fn save_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                 incremental_hashes_map: &IncrementalHashesMap,
-                                metadata_hashes: &[EncodedMetadataHash],
+                                metadata_hashes: &EncodedMetadataHashes,
                                 svh: Svh) {
     debug!("save_dep_graph()");
     let _ignore = tcx.dep_graph.in_ignore();
@@ -240,18 +240,19 @@ pub fn encode_dep_graph(preds: &Predecessors,
 
 pub fn encode_metadata_hashes(tcx: TyCtxt,
                               svh: Svh,
-                              metadata_hashes: &[EncodedMetadataHash],
+                              metadata_hashes: &EncodedMetadataHashes,
                               builder: &mut DefIdDirectoryBuilder,
                               current_metadata_hashes: &mut FxHashMap<DefId, Fingerprint>,
                               encoder: &mut Encoder)
                               -> io::Result<()> {
     let mut serialized_hashes = SerializedMetadataHashes {
-        hashes: metadata_hashes.to_vec(),
+        entry_hashes: metadata_hashes.entry_hashes.to_vec(),
+        global_hashes: metadata_hashes.global_hashes.to_vec(),
         index_map: FxHashMap()
     };
 
     if tcx.sess.opts.debugging_opts.query_dep_graph {
-        for serialized_hash in &serialized_hashes.hashes {
+        for serialized_hash in &serialized_hashes.entry_hashes {
             let def_id = DefId::local(serialized_hash.def_index);
 
             // Store entry in the index_map
diff --git a/src/librustc_metadata/astencode.rs b/src/librustc_metadata/astencode.rs
index d9008ce555c..6c02ac7eafe 100644
--- a/src/librustc_metadata/astencode.rs
+++ b/src/librustc_metadata/astencode.rs
@@ -10,7 +10,7 @@
 
 use rustc::hir::intravisit::{Visitor, NestedVisitorMap};
 
-use index_builder::EntryBuilder;
+use isolated_encoder::IsolatedEncoder;
 use schema::*;
 
 use rustc::hir;
@@ -31,7 +31,7 @@ impl_stable_hash_for!(struct Ast<'tcx> {
     rvalue_promotable_to_static
 });
 
-impl<'a, 'b, 'tcx> EntryBuilder<'a, 'b, 'tcx> {
+impl<'a, 'b, 'tcx> IsolatedEncoder<'a, 'b, 'tcx> {
     pub fn encode_body(&mut self, body_id: hir::BodyId) -> Lazy<Ast<'tcx>> {
         let body = self.tcx.hir.body(body_id);
         let lazy_body = self.lazy(body);
diff --git a/src/librustc_metadata/creader.rs b/src/librustc_metadata/creader.rs
index 966e814e337..58c2d3b2c12 100644
--- a/src/librustc_metadata/creader.rs
+++ b/src/librustc_metadata/creader.rs
@@ -12,9 +12,10 @@
 
 use cstore::{self, CStore, CrateSource, MetadataBlob};
 use locator::{self, CratePaths};
-use schema::CrateRoot;
+use schema::{CrateRoot, Tracked};
 
-use rustc::hir::def_id::{CrateNum, DefIndex};
+use rustc::dep_graph::{DepNode, GlobalMetaDataKind};
+use rustc::hir::def_id::{DefId, CrateNum, DefIndex, CRATE_DEF_INDEX};
 use rustc::hir::svh::Svh;
 use rustc::middle::cstore::DepKind;
 use rustc::session::Session;
@@ -311,7 +312,8 @@ impl<'a> CrateLoader<'a> {
             crate_root.def_path_table.decode(&metadata)
         });
 
-        let exported_symbols = crate_root.exported_symbols.decode(&metadata).collect();
+        let exported_symbols = crate_root.exported_symbols
+                                         .map(|x| x.decode(&metadata).collect());
 
         let mut cmeta = cstore::CrateMetadata {
             name: name,
@@ -333,16 +335,27 @@ impl<'a> CrateLoader<'a> {
                 rlib: rlib,
                 rmeta: rmeta,
             },
-            dllimport_foreign_items: FxHashSet(),
+            // Initialize this with an empty set. The field is populated below
+            // after we were able to deserialize its contents.
+            dllimport_foreign_items: Tracked::new(FxHashSet()),
         };
 
-        let dllimports: Vec<_> = cmeta.get_native_libraries().iter()
-                            .filter(|lib| relevant_lib(self.sess, lib) &&
-                                          lib.kind == cstore::NativeLibraryKind::NativeUnknown)
-                            .flat_map(|lib| &lib.foreign_items)
-                            .map(|id| *id)
-                            .collect();
-        cmeta.dllimport_foreign_items.extend(dllimports);
+        let dllimports: Tracked<FxHashSet<_>> = cmeta
+            .root
+            .native_libraries
+            .map(|native_libraries| {
+                let native_libraries: Vec<_> = native_libraries.decode(&cmeta)
+                                                               .collect();
+                native_libraries
+                    .iter()
+                    .filter(|lib| relevant_lib(self.sess, lib) &&
+                                  lib.kind == cstore::NativeLibraryKind::NativeUnknown)
+                    .flat_map(|lib| lib.foreign_items.iter())
+                    .map(|id| *id)
+                    .collect()
+            });
+
+        cmeta.dllimport_foreign_items = dllimports;
 
         let cmeta = Rc::new(cmeta);
         self.cstore.set_crate_data(cnum, cmeta.clone());
@@ -493,10 +506,16 @@ impl<'a> CrateLoader<'a> {
             return cstore::CrateNumMap::new();
         }
 
+        let dep_node = DepNode::GlobalMetaData(DefId { krate, index: CRATE_DEF_INDEX },
+                                               GlobalMetaDataKind::CrateDeps);
+
         // The map from crate numbers in the crate we're resolving to local crate numbers.
         // We map 0 and all other holes in the map to our parent crate. The "additional"
         // self-dependencies should be harmless.
-        ::std::iter::once(krate).chain(crate_root.crate_deps.decode(metadata).map(|dep| {
+        ::std::iter::once(krate).chain(crate_root.crate_deps
+                                                 .get(&self.sess.dep_graph, dep_node)
+                                                 .decode(metadata)
+                                                 .map(|dep| {
             debug!("resolving dep crate {} hash: `{}`", dep.name, dep.hash);
             if dep.kind == DepKind::UnexportedMacrosOnly {
                 return krate;
@@ -654,7 +673,9 @@ impl<'a> CrateLoader<'a> {
 
     /// Look for a plugin registrar. Returns library path, crate
     /// SVH and DefIndex of the registrar function.
-    pub fn find_plugin_registrar(&mut self, span: Span, name: &str)
+    pub fn find_plugin_registrar(&mut self,
+                                 span: Span,
+                                 name: &str)
                                  -> Option<(PathBuf, Symbol, DefIndex)> {
         let ekrate = self.read_extension_crate(span, &ExternCrateInfo {
              name: Symbol::intern(name),
@@ -740,13 +761,17 @@ impl<'a> CrateLoader<'a> {
         let mut runtime_found = false;
         let mut needs_panic_runtime = attr::contains_name(&krate.attrs,
                                                           "needs_panic_runtime");
+
+        let dep_graph = &self.sess.dep_graph;
+
         self.cstore.iter_crate_data(|cnum, data| {
-            needs_panic_runtime = needs_panic_runtime || data.needs_panic_runtime();
-            if data.is_panic_runtime() {
+            needs_panic_runtime = needs_panic_runtime ||
+                                  data.needs_panic_runtime(dep_graph);
+            if data.is_panic_runtime(dep_graph) {
                 // Inject a dependency from all #![needs_panic_runtime] to this
                 // #![panic_runtime] crate.
                 self.inject_dependency_if(cnum, "a panic runtime",
-                                          &|data| data.needs_panic_runtime());
+                                          &|data| data.needs_panic_runtime(dep_graph));
                 runtime_found = runtime_found || data.dep_kind.get() == DepKind::Explicit;
             }
         });
@@ -782,11 +807,11 @@ impl<'a> CrateLoader<'a> {
 
         // Sanity check the loaded crate to ensure it is indeed a panic runtime
         // and the panic strategy is indeed what we thought it was.
-        if !data.is_panic_runtime() {
+        if !data.is_panic_runtime(dep_graph) {
             self.sess.err(&format!("the crate `{}` is not a panic runtime",
                                    name));
         }
-        if data.panic_strategy() != desired_strategy {
+        if data.panic_strategy(dep_graph) != desired_strategy {
             self.sess.err(&format!("the crate `{}` does not have the panic \
                                     strategy `{}`",
                                    name, desired_strategy.desc()));
@@ -794,7 +819,7 @@ impl<'a> CrateLoader<'a> {
 
         self.sess.injected_panic_runtime.set(Some(cnum));
         self.inject_dependency_if(cnum, "a panic runtime",
-                                  &|data| data.needs_panic_runtime());
+                                  &|data| data.needs_panic_runtime(dep_graph));
     }
 
     fn inject_sanitizer_runtime(&mut self) {
@@ -862,7 +887,7 @@ impl<'a> CrateLoader<'a> {
                                        PathKind::Crate, dep_kind);
 
                 // Sanity check the loaded crate to ensure it is indeed a sanitizer runtime
-                if !data.is_sanitizer_runtime() {
+                if !data.is_sanitizer_runtime(&self.sess.dep_graph) {
                     self.sess.err(&format!("the crate `{}` is not a sanitizer runtime",
                                            name));
                 }
@@ -878,12 +903,13 @@ impl<'a> CrateLoader<'a> {
         // also bail out as we don't need to implicitly inject one.
         let mut needs_allocator = false;
         let mut found_required_allocator = false;
+        let dep_graph = &self.sess.dep_graph;
         self.cstore.iter_crate_data(|cnum, data| {
-            needs_allocator = needs_allocator || data.needs_allocator();
-            if data.is_allocator() {
+            needs_allocator = needs_allocator || data.needs_allocator(dep_graph);
+            if data.is_allocator(dep_graph) {
                 info!("{} required by rlib and is an allocator", data.name());
                 self.inject_dependency_if(cnum, "an allocator",
-                                          &|data| data.needs_allocator());
+                                          &|data| data.needs_allocator(dep_graph));
                 found_required_allocator = found_required_allocator ||
                     data.dep_kind.get() == DepKind::Explicit;
             }
@@ -937,14 +963,14 @@ impl<'a> CrateLoader<'a> {
 
         // Sanity check the crate we loaded to ensure that it is indeed an
         // allocator.
-        if !data.is_allocator() {
+        if !data.is_allocator(dep_graph) {
             self.sess.err(&format!("the allocator crate `{}` is not tagged \
                                     with #![allocator]", data.name()));
         }
 
         self.sess.injected_allocator.set(Some(cnum));
         self.inject_dependency_if(cnum, "an allocator",
-                                  &|data| data.needs_allocator());
+                                  &|data| data.needs_allocator(dep_graph));
     }
 
     fn inject_dependency_if(&self,
diff --git a/src/librustc_metadata/cstore.rs b/src/librustc_metadata/cstore.rs
index 72ad1d75a56..8d53e7d49ee 100644
--- a/src/librustc_metadata/cstore.rs
+++ b/src/librustc_metadata/cstore.rs
@@ -12,9 +12,9 @@
 // crates and libraries
 
 use locator;
-use schema;
+use schema::{self, Tracked};
 
-use rustc::dep_graph::DepGraph;
+use rustc::dep_graph::{DepGraph, DepNode, GlobalMetaDataKind};
 use rustc::hir::def_id::{CRATE_DEF_INDEX, LOCAL_CRATE, CrateNum, DefIndex, DefId};
 use rustc::hir::map::definitions::DefPathTable;
 use rustc::hir::svh::Svh;
@@ -83,14 +83,14 @@ pub struct CrateMetadata {
     /// compilation support.
     pub def_path_table: DefPathTable,
 
-    pub exported_symbols: FxHashSet<DefIndex>,
+    pub exported_symbols: Tracked<FxHashSet<DefIndex>>,
 
     pub dep_kind: Cell<DepKind>,
     pub source: CrateSource,
 
     pub proc_macros: Option<Vec<(ast::Name, Rc<SyntaxExtension>)>>,
     // Foreign items imported from a dylib (Windows only)
-    pub dllimport_foreign_items: FxHashSet<DefIndex>,
+    pub dllimport_foreign_items: Tracked<FxHashSet<DefIndex>>,
 }
 
 pub struct CStore {
@@ -269,8 +269,8 @@ impl CrateMetadata {
         self.root.disambiguator
     }
 
-    pub fn is_staged_api(&self) -> bool {
-        for attr in self.get_item_attrs(CRATE_DEF_INDEX).iter() {
+    pub fn is_staged_api(&self, dep_graph: &DepGraph) -> bool {
+        for attr in self.get_item_attrs(CRATE_DEF_INDEX, dep_graph).iter() {
             if attr.path == "stable" || attr.path == "unstable" {
                 return true;
             }
@@ -278,42 +278,51 @@ impl CrateMetadata {
         false
     }
 
-    pub fn is_allocator(&self) -> bool {
-        let attrs = self.get_item_attrs(CRATE_DEF_INDEX);
+    pub fn is_allocator(&self, dep_graph: &DepGraph) -> bool {
+        let attrs = self.get_item_attrs(CRATE_DEF_INDEX, dep_graph);
         attr::contains_name(&attrs, "allocator")
     }
 
-    pub fn needs_allocator(&self) -> bool {
-        let attrs = self.get_item_attrs(CRATE_DEF_INDEX);
+    pub fn needs_allocator(&self, dep_graph: &DepGraph) -> bool {
+        let attrs = self.get_item_attrs(CRATE_DEF_INDEX, dep_graph);
         attr::contains_name(&attrs, "needs_allocator")
     }
 
-    pub fn is_panic_runtime(&self) -> bool {
-        let attrs = self.get_item_attrs(CRATE_DEF_INDEX);
+    pub fn is_panic_runtime(&self, dep_graph: &DepGraph) -> bool {
+        let attrs = self.get_item_attrs(CRATE_DEF_INDEX, dep_graph);
         attr::contains_name(&attrs, "panic_runtime")
     }
 
-    pub fn needs_panic_runtime(&self) -> bool {
-        let attrs = self.get_item_attrs(CRATE_DEF_INDEX);
+    pub fn needs_panic_runtime(&self, dep_graph: &DepGraph) -> bool {
+        let attrs = self.get_item_attrs(CRATE_DEF_INDEX, dep_graph);
         attr::contains_name(&attrs, "needs_panic_runtime")
     }
 
-    pub fn is_compiler_builtins(&self) -> bool {
-        let attrs = self.get_item_attrs(CRATE_DEF_INDEX);
+    pub fn is_compiler_builtins(&self, dep_graph: &DepGraph) -> bool {
+        let attrs = self.get_item_attrs(CRATE_DEF_INDEX, dep_graph);
         attr::contains_name(&attrs, "compiler_builtins")
     }
 
-    pub fn is_sanitizer_runtime(&self) -> bool {
-        let attrs = self.get_item_attrs(CRATE_DEF_INDEX);
+    pub fn is_sanitizer_runtime(&self, dep_graph: &DepGraph) -> bool {
+        let attrs = self.get_item_attrs(CRATE_DEF_INDEX, dep_graph);
         attr::contains_name(&attrs, "sanitizer_runtime")
     }
 
-    pub fn is_no_builtins(&self) -> bool {
-        let attrs = self.get_item_attrs(CRATE_DEF_INDEX);
+    pub fn is_no_builtins(&self, dep_graph: &DepGraph) -> bool {
+        let attrs = self.get_item_attrs(CRATE_DEF_INDEX, dep_graph);
         attr::contains_name(&attrs, "no_builtins")
     }
 
-    pub fn panic_strategy(&self) -> PanicStrategy {
-        self.root.panic_strategy.clone()
+    pub fn panic_strategy(&self, dep_graph: &DepGraph) -> PanicStrategy {
+        let def_id = DefId {
+            krate: self.cnum,
+            index: CRATE_DEF_INDEX,
+        };
+        let dep_node = DepNode::GlobalMetaData(def_id, GlobalMetaDataKind::Krate);
+
+        self.root
+            .panic_strategy
+            .get(dep_graph, dep_node)
+            .clone()
     }
 }
diff --git a/src/librustc_metadata/cstore_impl.rs b/src/librustc_metadata/cstore_impl.rs
index a1794ec2d82..6fa6a868605 100644
--- a/src/librustc_metadata/cstore_impl.rs
+++ b/src/librustc_metadata/cstore_impl.rs
@@ -24,7 +24,7 @@ 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::dep_graph::{DepNode, GlobalMetaDataKind};
 use rustc::hir::map::{DefKey, DefPath, DisambiguatedDefPathData};
 use rustc::util::nodemap::{NodeSet, DefIdMap};
 use rustc_back::PanicStrategy;
@@ -147,8 +147,8 @@ impl CrateStore for cstore::CStore {
 
     fn item_attrs(&self, def_id: DefId) -> Rc<[ast::Attribute]>
     {
-        self.dep_graph.read(DepNode::MetaData(def_id));
-        self.get_crate_data(def_id.krate).get_item_attrs(def_id.index)
+        self.get_crate_data(def_id.krate)
+            .get_item_attrs(def_id.index, &self.dep_graph)
     }
 
     fn fn_arg_names(&self, did: DefId) -> Vec<ast::Name>
@@ -168,7 +168,7 @@ impl CrateStore for cstore::CStore {
         }
         let mut result = vec![];
         self.iter_crate_data(|_, cdata| {
-            cdata.get_implementations_for_trait(filter, &mut result)
+            cdata.get_implementations_for_trait(filter, &self.dep_graph, &mut result)
         });
         result
     }
@@ -216,70 +216,82 @@ impl CrateStore for cstore::CStore {
     }
 
     fn is_exported_symbol(&self, def_id: DefId) -> bool {
-        self.get_crate_data(def_id.krate).exported_symbols.contains(&def_id.index)
+        let data = self.get_crate_data(def_id.krate);
+        let dep_node = data.metadata_dep_node(GlobalMetaDataKind::ExportedSymbols);
+        data.exported_symbols
+            .get(&self.dep_graph, dep_node)
+            .contains(&def_id.index)
     }
 
     fn is_dllimport_foreign_item(&self, def_id: DefId) -> bool {
         if def_id.krate == LOCAL_CRATE {
             self.dllimport_foreign_items.borrow().contains(&def_id.index)
         } else {
-            self.get_crate_data(def_id.krate).is_dllimport_foreign_item(def_id.index)
+            self.get_crate_data(def_id.krate)
+                .is_dllimport_foreign_item(def_id.index, &self.dep_graph)
         }
     }
 
     fn dylib_dependency_formats(&self, cnum: CrateNum)
                                 -> Vec<(CrateNum, LinkagePreference)>
     {
-        self.get_crate_data(cnum).get_dylib_dependency_formats()
+        self.get_crate_data(cnum).get_dylib_dependency_formats(&self.dep_graph)
     }
 
     fn dep_kind(&self, cnum: CrateNum) -> DepKind
     {
-        self.get_crate_data(cnum).dep_kind.get()
+        let data = self.get_crate_data(cnum);
+        let dep_node = data.metadata_dep_node(GlobalMetaDataKind::CrateDeps);
+        self.dep_graph.read(dep_node);
+        data.dep_kind.get()
     }
 
     fn export_macros(&self, cnum: CrateNum) {
-        if self.get_crate_data(cnum).dep_kind.get() == DepKind::UnexportedMacrosOnly {
-            self.get_crate_data(cnum).dep_kind.set(DepKind::MacrosOnly)
+        let data = self.get_crate_data(cnum);
+        let dep_node = data.metadata_dep_node(GlobalMetaDataKind::CrateDeps);
+
+        self.dep_graph.read(dep_node);
+        if data.dep_kind.get() == DepKind::UnexportedMacrosOnly {
+            data.dep_kind.set(DepKind::MacrosOnly)
         }
     }
 
     fn lang_items(&self, cnum: CrateNum) -> Vec<(DefIndex, usize)>
     {
-        self.get_crate_data(cnum).get_lang_items()
+        self.get_crate_data(cnum).get_lang_items(&self.dep_graph)
     }
 
     fn missing_lang_items(&self, cnum: CrateNum)
                           -> Vec<lang_items::LangItem>
     {
-        self.get_crate_data(cnum).get_missing_lang_items()
+        self.get_crate_data(cnum).get_missing_lang_items(&self.dep_graph)
     }
 
     fn is_staged_api(&self, cnum: CrateNum) -> bool
     {
-        self.get_crate_data(cnum).is_staged_api()
+        self.get_crate_data(cnum).is_staged_api(&self.dep_graph)
     }
 
     fn is_allocator(&self, cnum: CrateNum) -> bool
     {
-        self.get_crate_data(cnum).is_allocator()
+        self.get_crate_data(cnum).is_allocator(&self.dep_graph)
     }
 
     fn is_panic_runtime(&self, cnum: CrateNum) -> bool
     {
-        self.get_crate_data(cnum).is_panic_runtime()
+        self.get_crate_data(cnum).is_panic_runtime(&self.dep_graph)
     }
 
     fn is_compiler_builtins(&self, cnum: CrateNum) -> bool {
-        self.get_crate_data(cnum).is_compiler_builtins()
+        self.get_crate_data(cnum).is_compiler_builtins(&self.dep_graph)
     }
 
     fn is_sanitizer_runtime(&self, cnum: CrateNum) -> bool {
-        self.get_crate_data(cnum).is_sanitizer_runtime()
+        self.get_crate_data(cnum).is_sanitizer_runtime(&self.dep_graph)
     }
 
     fn panic_strategy(&self, cnum: CrateNum) -> PanicStrategy {
-        self.get_crate_data(cnum).panic_strategy()
+        self.get_crate_data(cnum).panic_strategy(&self.dep_graph)
     }
 
     fn crate_name(&self, cnum: CrateNum) -> Symbol
@@ -325,16 +337,16 @@ impl CrateStore for cstore::CStore {
 
     fn native_libraries(&self, cnum: CrateNum) -> Vec<NativeLibrary>
     {
-        self.get_crate_data(cnum).get_native_libraries()
+        self.get_crate_data(cnum).get_native_libraries(&self.dep_graph)
     }
 
     fn exported_symbols(&self, cnum: CrateNum) -> Vec<DefId>
     {
-        self.get_crate_data(cnum).get_exported_symbols()
+        self.get_crate_data(cnum).get_exported_symbols(&self.dep_graph)
     }
 
     fn is_no_builtins(&self, cnum: CrateNum) -> bool {
-        self.get_crate_data(cnum).is_no_builtins()
+        self.get_crate_data(cnum).is_no_builtins(&self.dep_graph)
     }
 
     fn retrace_path(&self,
@@ -401,7 +413,7 @@ impl CrateStore for cstore::CStore {
         let body = filemap_to_stream(&sess.parse_sess, filemap);
 
         // Mark the attrs as used
-        let attrs = data.get_item_attrs(id.index);
+        let attrs = data.get_item_attrs(id.index, &self.dep_graph);
         for attr in attrs.iter() {
             attr::mark_used(attr);
         }
@@ -483,7 +495,7 @@ impl CrateStore for cstore::CStore {
                                  reachable: &NodeSet)
                                  -> EncodedMetadata
     {
-        encoder::encode_metadata(tcx, self, link_meta, reachable)
+        encoder::encode_metadata(tcx, link_meta, reachable)
     }
 
     fn metadata_encoding_version(&self) -> &[u8]
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index ae755adcf5f..820b5a68bcc 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -13,6 +13,7 @@
 use cstore::{self, CrateMetadata, MetadataBlob, NativeLibrary};
 use schema::*;
 
+use rustc::dep_graph::{DepGraph, DepNode, GlobalMetaDataKind};
 use rustc::hir::map::{DefKey, DefPath, DefPathData};
 use rustc::hir;
 
@@ -404,10 +405,14 @@ impl<'a, 'tcx> MetadataBlob {
         Lazy::with_position(pos).decode(self)
     }
 
-    pub fn list_crate_metadata(&self, out: &mut io::Write) -> io::Result<()> {
+    pub fn list_crate_metadata(&self,
+                               out: &mut io::Write) -> io::Result<()> {
         write!(out, "=External Dependencies=\n")?;
         let root = self.get_root();
-        for (i, dep) in root.crate_deps.decode(self).enumerate() {
+        for (i, dep) in root.crate_deps
+                            .get_untracked()
+                            .decode(self)
+                            .enumerate() {
             write!(out, "{} {}-{}\n", i + 1, dep.name, dep.hash)?;
         }
         write!(out, "\n")?;
@@ -653,8 +658,13 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     /// Iterates over the language items in the given crate.
-    pub fn get_lang_items(&self) -> Vec<(DefIndex, usize)> {
-        self.root.lang_items.decode(self).collect()
+    pub fn get_lang_items(&self, dep_graph: &DepGraph) -> Vec<(DefIndex, usize)> {
+        let dep_node = self.metadata_dep_node(GlobalMetaDataKind::LangItems);
+        self.root
+            .lang_items
+            .get(dep_graph, dep_node)
+            .decode(self)
+            .collect()
     }
 
     /// Iterates over each child of the given item.
@@ -853,13 +863,17 @@ impl<'a, 'tcx> CrateMetadata {
         }
     }
 
-    pub fn get_item_attrs(&self, node_id: DefIndex) -> Rc<[ast::Attribute]> {
+    pub fn get_item_attrs(&self,
+                          node_id: DefIndex,
+                          dep_graph: &DepGraph) -> Rc<[ast::Attribute]> {
         let (node_as, node_index) =
             (node_id.address_space().index(), node_id.as_array_index());
         if self.is_proc_macro(node_id) {
             return Rc::new([]);
         }
 
+        dep_graph.read(DepNode::MetaData(self.local_def_id(node_id)));
+
         if let Some(&Some(ref val)) =
             self.attribute_cache.borrow()[node_as].get(node_index) {
             return val.clone();
@@ -924,7 +938,10 @@ impl<'a, 'tcx> CrateMetadata {
             .collect()
     }
 
-    pub fn get_implementations_for_trait(&self, filter: Option<DefId>, result: &mut Vec<DefId>) {
+    pub fn get_implementations_for_trait(&self,
+                                         filter: Option<DefId>,
+                                         dep_graph: &DepGraph,
+                                         result: &mut Vec<DefId>) {
         // Do a reverse lookup beforehand to avoid touching the crate_num
         // hash map in the loop below.
         let filter = match filter.map(|def_id| self.reverse_translate_def_id(def_id)) {
@@ -935,7 +952,8 @@ impl<'a, 'tcx> CrateMetadata {
         };
 
         // FIXME(eddyb) Make this O(1) instead of O(n).
-        for trait_impls in self.root.impls.decode(self) {
+        let dep_node = self.metadata_dep_node(GlobalMetaDataKind::Impls);
+        for trait_impls in self.root.impls.get(dep_graph, dep_node).decode(self) {
             if filter.is_some() && filter != Some(trait_impls.trait_id) {
                 continue;
             }
@@ -958,13 +976,29 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
 
-    pub fn get_native_libraries(&self) -> Vec<NativeLibrary> {
-        self.root.native_libraries.decode(self).collect()
+    pub fn get_native_libraries(&self,
+                                dep_graph: &DepGraph)
+                                -> Vec<NativeLibrary> {
+        let dep_node = self.metadata_dep_node(GlobalMetaDataKind::NativeLibraries);
+        self.root
+            .native_libraries
+            .get(dep_graph, dep_node)
+            .decode(self)
+            .collect()
     }
 
-    pub fn get_dylib_dependency_formats(&self) -> Vec<(CrateNum, LinkagePreference)> {
+    pub fn get_dylib_dependency_formats(&self,
+                                        dep_graph: &DepGraph)
+                                        -> Vec<(CrateNum, LinkagePreference)> {
+        let def_id = DefId {
+            krate: self.cnum,
+            index: CRATE_DEF_INDEX,
+        };
+        let dep_node = DepNode::GlobalMetaData(def_id,
+                                               GlobalMetaDataKind::DylibDependencyFormats);
         self.root
             .dylib_dependency_formats
+            .get(dep_graph, dep_node)
             .decode(self)
             .enumerate()
             .flat_map(|(i, link)| {
@@ -974,8 +1008,13 @@ impl<'a, 'tcx> CrateMetadata {
             .collect()
     }
 
-    pub fn get_missing_lang_items(&self) -> Vec<lang_items::LangItem> {
-        self.root.lang_items_missing.decode(self).collect()
+    pub fn get_missing_lang_items(&self, dep_graph: &DepGraph) -> Vec<lang_items::LangItem> {
+        let dep_node = self.metadata_dep_node(GlobalMetaDataKind::LangItemsMissing);
+        self.root
+            .lang_items_missing
+            .get(dep_graph, dep_node)
+            .decode(self)
+            .collect()
     }
 
     pub fn get_fn_arg_names(&self, id: DefIndex) -> Vec<ast::Name> {
@@ -988,8 +1027,13 @@ impl<'a, 'tcx> CrateMetadata {
         arg_names.decode(self).collect()
     }
 
-    pub fn get_exported_symbols(&self) -> Vec<DefId> {
-        self.exported_symbols.iter().map(|&index| self.local_def_id(index)).collect()
+    pub fn get_exported_symbols(&self, dep_graph: &DepGraph) -> Vec<DefId> {
+        let dep_node = self.metadata_dep_node(GlobalMetaDataKind::ExportedSymbols);
+        self.exported_symbols
+            .get(dep_graph, dep_node)
+            .iter()
+            .map(|&index| self.local_def_id(index))
+            .collect()
     }
 
     pub fn get_macro(&self, id: DefIndex) -> (ast::Name, MacroDef) {
@@ -1018,8 +1062,11 @@ impl<'a, 'tcx> CrateMetadata {
         }
     }
 
-    pub fn is_dllimport_foreign_item(&self, id: DefIndex) -> bool {
-        self.dllimport_foreign_items.contains(&id)
+    pub fn is_dllimport_foreign_item(&self, id: DefIndex, dep_graph: &DepGraph) -> bool {
+        let dep_node = self.metadata_dep_node(GlobalMetaDataKind::NativeLibraries);
+        self.dllimport_foreign_items
+            .get(dep_graph, dep_node)
+            .contains(&id)
     }
 
     pub fn is_default_impl(&self, impl_id: DefIndex) -> bool {
@@ -1097,121 +1144,62 @@ impl<'a, 'tcx> CrateMetadata {
         let external_codemap = self.root.codemap.decode(self);
 
         let imported_filemaps = external_codemap.map(|filemap_to_import| {
-                // Try to find an existing FileMap that can be reused for the filemap to
-                // be imported. A FileMap is reusable if it is exactly the same, just
-                // positioned at a different offset within the codemap.
-                let reusable_filemap = {
-                    local_codemap.files
-                        .borrow()
-                        .iter()
-                        .find(|fm| are_equal_modulo_startpos(&fm, &filemap_to_import))
-                        .map(|rc| rc.clone())
-                };
-
-                match reusable_filemap {
-                    Some(fm) => {
-
-                        debug!("CrateMetaData::imported_filemaps reuse \
-                                filemap {:?} original (start_pos {:?} end_pos {:?}) \
-                                translated (start_pos {:?} end_pos {:?})",
-                               filemap_to_import.name,
-                               filemap_to_import.start_pos, filemap_to_import.end_pos,
-                               fm.start_pos, fm.end_pos);
-
-                        cstore::ImportedFileMap {
-                            original_start_pos: filemap_to_import.start_pos,
-                            original_end_pos: filemap_to_import.end_pos,
-                            translated_filemap: fm,
-                        }
-                    }
-                    None => {
-                        // We can't reuse an existing FileMap, so allocate a new one
-                        // containing the information we need.
-                        let syntax_pos::FileMap { name,
-                                                  name_was_remapped,
-                                                  start_pos,
-                                                  end_pos,
-                                                  lines,
-                                                  multibyte_chars,
-                                                  .. } = filemap_to_import;
-
-                        let source_length = (end_pos - start_pos).to_usize();
-
-                        // Translate line-start positions and multibyte character
-                        // position into frame of reference local to file.
-                        // `CodeMap::new_imported_filemap()` will then translate those
-                        // coordinates to their new global frame of reference when the
-                        // offset of the FileMap is known.
-                        let mut lines = lines.into_inner();
-                        for pos in &mut lines {
-                            *pos = *pos - start_pos;
-                        }
-                        let mut multibyte_chars = multibyte_chars.into_inner();
-                        for mbc in &mut multibyte_chars {
-                            mbc.pos = mbc.pos - start_pos;
-                        }
+            // We can't reuse an existing FileMap, so allocate a new one
+            // containing the information we need.
+            let syntax_pos::FileMap { name,
+                                      name_was_remapped,
+                                      start_pos,
+                                      end_pos,
+                                      lines,
+                                      multibyte_chars,
+                                      .. } = filemap_to_import;
+
+            let source_length = (end_pos - start_pos).to_usize();
+
+            // Translate line-start positions and multibyte character
+            // position into frame of reference local to file.
+            // `CodeMap::new_imported_filemap()` will then translate those
+            // coordinates to their new global frame of reference when the
+            // offset of the FileMap is known.
+            let mut lines = lines.into_inner();
+            for pos in &mut lines {
+                *pos = *pos - start_pos;
+            }
+            let mut multibyte_chars = multibyte_chars.into_inner();
+            for mbc in &mut multibyte_chars {
+                mbc.pos = mbc.pos - start_pos;
+            }
 
-                        let local_version = local_codemap.new_imported_filemap(name,
-                                                                               name_was_remapped,
-                                                                               source_length,
-                                                                               lines,
-                                                                               multibyte_chars);
-                        debug!("CrateMetaData::imported_filemaps alloc \
-                                filemap {:?} original (start_pos {:?} end_pos {:?}) \
-                                translated (start_pos {:?} end_pos {:?})",
-                               local_version.name, start_pos, end_pos,
-                               local_version.start_pos, local_version.end_pos);
-
-                        cstore::ImportedFileMap {
-                            original_start_pos: start_pos,
-                            original_end_pos: end_pos,
-                            translated_filemap: local_version,
-                        }
-                    }
-                }
-            })
-            .collect();
+            let local_version = local_codemap.new_imported_filemap(name,
+                                                                   name_was_remapped,
+                                                                   self.cnum.as_u32(),
+                                                                   source_length,
+                                                                   lines,
+                                                                   multibyte_chars);
+            debug!("CrateMetaData::imported_filemaps alloc \
+                    filemap {:?} original (start_pos {:?} end_pos {:?}) \
+                    translated (start_pos {:?} end_pos {:?})",
+                   local_version.name, start_pos, end_pos,
+                   local_version.start_pos, local_version.end_pos);
+
+            cstore::ImportedFileMap {
+                original_start_pos: start_pos,
+                original_end_pos: end_pos,
+                translated_filemap: local_version,
+            }
+        }).collect();
 
         // This shouldn't borrow twice, but there is no way to downgrade RefMut to Ref.
         *self.codemap_import_info.borrow_mut() = imported_filemaps;
         self.codemap_import_info.borrow()
     }
-}
-
-fn are_equal_modulo_startpos(fm1: &syntax_pos::FileMap, fm2: &syntax_pos::FileMap) -> bool {
-    if fm1.byte_length() != fm2.byte_length() {
-        return false;
-    }
-
-    if fm1.name != fm2.name {
-        return false;
-    }
-
-    let lines1 = fm1.lines.borrow();
-    let lines2 = fm2.lines.borrow();
-
-    if lines1.len() != lines2.len() {
-        return false;
-    }
-
-    for (&line1, &line2) in lines1.iter().zip(lines2.iter()) {
-        if (line1 - fm1.start_pos) != (line2 - fm2.start_pos) {
-            return false;
-        }
-    }
-
-    let multibytes1 = fm1.multibyte_chars.borrow();
-    let multibytes2 = fm2.multibyte_chars.borrow();
 
-    if multibytes1.len() != multibytes2.len() {
-        return false;
-    }
+    pub fn metadata_dep_node(&self, kind: GlobalMetaDataKind) -> DepNode<DefId> {
+        let def_id = DefId {
+            krate: self.cnum,
+            index: CRATE_DEF_INDEX,
+        };
 
-    for (mb1, mb2) in multibytes1.iter().zip(multibytes2.iter()) {
-        if (mb1.bytes != mb2.bytes) || ((mb1.pos - fm1.start_pos) != (mb2.pos - fm2.start_pos)) {
-            return false;
-        }
+        DepNode::GlobalMetaData(def_id, kind)
     }
-
-    true
 }
diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs
index 796cb8c4d65..fa4ebed1618 100644
--- a/src/librustc_metadata/encoder.rs
+++ b/src/librustc_metadata/encoder.rs
@@ -8,14 +8,17 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use cstore;
 use index::Index;
+use index_builder::{FromId, IndexBuilder, Untracked};
+use isolated_encoder::IsolatedEncoder;
 use schema::*;
 
 use rustc::middle::cstore::{LinkMeta, LinkagePreference, NativeLibrary,
-                            EncodedMetadata, EncodedMetadataHash};
+                            EncodedMetadata, EncodedMetadataHashes};
 use rustc::hir::def_id::{CrateNum, CRATE_DEF_INDEX, DefIndex, DefId, LOCAL_CRATE};
 use rustc::hir::map::definitions::DefPathTable;
+use rustc::dep_graph::{DepNode, GlobalMetaDataKind};
+use rustc::ich::{StableHashingContext, Fingerprint};
 use rustc::middle::dependency_format::Linkage;
 use rustc::middle::lang_items;
 use rustc::mir;
@@ -26,12 +29,15 @@ use rustc::session::config::{self, CrateTypeProcMacro};
 use rustc::util::nodemap::{FxHashMap, NodeSet};
 
 use rustc_serialize::{Encodable, Encoder, SpecializedEncoder, opaque};
+use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
+
 use std::hash::Hash;
 use std::intrinsics;
 use std::io::prelude::*;
 use std::io::Cursor;
 use std::path::Path;
 use std::rc::Rc;
+use std::sync::Arc;
 use std::u32;
 use syntax::ast::{self, CRATE_NODE_ID};
 use syntax::codemap::Spanned;
@@ -44,20 +50,18 @@ use rustc::hir::itemlikevisit::ItemLikeVisitor;
 use rustc::hir::intravisit::{Visitor, NestedVisitorMap};
 use rustc::hir::intravisit;
 
-use super::index_builder::{FromId, IndexBuilder, Untracked, EntryBuilder};
-
 pub struct EncodeContext<'a, 'tcx: 'a> {
     opaque: opaque::Encoder<'a>,
     pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
     link_meta: &'a LinkMeta,
-    cstore: &'a cstore::CStore,
     exported_symbols: &'a NodeSet,
 
     lazy_state: LazyState,
     type_shorthands: FxHashMap<Ty<'tcx>, usize>,
     predicate_shorthands: FxHashMap<ty::Predicate<'tcx>, usize>,
 
-    pub metadata_hashes: Vec<EncodedMetadataHash>,
+    pub metadata_hashes: EncodedMetadataHashes,
+    pub compute_ich: bool,
 }
 
 macro_rules! encoder_methods {
@@ -134,6 +138,7 @@ impl<'a, 'tcx> SpecializedEncoder<ty::GenericPredicates<'tcx>> for EncodeContext
 }
 
 impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
+
     pub fn position(&self) -> usize {
         self.opaque.position()
     }
@@ -237,11 +242,240 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
 
         Ok(())
     }
+
+    // Encodes something that corresponds to a single DepNode::GlobalMetaData
+    // and registers the Fingerprint in the `metadata_hashes` map.
+    pub fn tracked<'x, DATA, R>(&'x mut self,
+                                dep_node: DepNode<()>,
+                                op: fn(&mut IsolatedEncoder<'x, 'a, 'tcx>, DATA) -> R,
+                                data: DATA)
+                                -> Tracked<R> {
+        let mut entry_builder = IsolatedEncoder::new(self);
+        let ret = op(&mut entry_builder, data);
+        let (fingerprint, this) = entry_builder.finish();
+
+        if let Some(fingerprint) = fingerprint {
+            this.metadata_hashes.global_hashes.push((dep_node, fingerprint));
+        }
+
+        Tracked::new(ret)
+    }
+
+    fn encode_info_for_items(&mut self) -> Index {
+        let krate = self.tcx.hir.krate();
+        let mut index = IndexBuilder::new(self);
+        index.record(DefId::local(CRATE_DEF_INDEX),
+                     IsolatedEncoder::encode_info_for_mod,
+                     FromId(CRATE_NODE_ID, (&krate.module, &krate.attrs, &hir::Public)));
+        let mut visitor = EncodeVisitor { index: index };
+        krate.visit_all_item_likes(&mut visitor.as_deep_visitor());
+        for macro_def in &krate.exported_macros {
+            visitor.visit_macro_def(macro_def);
+        }
+        visitor.index.into_items()
+    }
+
+    fn encode_def_path_table(&mut self) -> Lazy<DefPathTable> {
+        let definitions = self.tcx.hir.definitions();
+        self.lazy(definitions.def_path_table())
+    }
+
+    fn encode_codemap(&mut self) -> LazySeq<syntax_pos::FileMap> {
+        let codemap = self.tcx.sess.codemap();
+        let all_filemaps = codemap.files();
+
+        let hcx = &mut StableHashingContext::new(self.tcx);
+        let (working_dir, working_dir_was_remapped) = self.tcx.sess.working_dir.clone();
+
+        let adapted = all_filemaps.iter()
+            .filter(|filemap| {
+                // No need to re-export imported filemaps, as any downstream
+                // crate will import them from their original source.
+                !filemap.is_imported()
+            })
+            .map(|filemap| {
+                // When exporting FileMaps, we expand all paths to absolute
+                // paths because any relative paths are potentially relative to
+                // a wrong directory.
+                // However, if a path has been modified via
+                // `-Zremap-path-prefix` we assume the user has already set
+                // things up the way they want and don't touch the path values
+                // anymore.
+                let name = Path::new(&filemap.name);
+                if filemap.name_was_remapped ||
+                   (name.is_relative() && working_dir_was_remapped) {
+                    // This path of this FileMap has been modified by
+                    // path-remapping, so we use it verbatim (and avoid cloning
+                    // the whole map in the process).
+                    filemap.clone()
+                } else {
+                    let mut adapted = (**filemap).clone();
+                    let abs_path = Path::new(&working_dir).join(name)
+                                                         .to_string_lossy()
+                                                         .into_owned();
+                    adapted.name = abs_path;
+                    Rc::new(adapted)
+                }
+            });
+
+        let filemaps: Vec<_> = if self.compute_ich {
+            adapted.inspect(|filemap| {
+                let mut hasher = StableHasher::new();
+                filemap.hash_stable(hcx, &mut hasher);
+                let fingerprint = hasher.finish();
+                let dep_node = DepNode::FileMap((), Arc::new(filemap.name.clone()));
+                self.metadata_hashes.global_hashes.push((dep_node, fingerprint));
+            }).collect()
+        } else {
+            adapted.collect()
+        };
+
+        self.lazy_seq_ref(filemaps.iter().map(|fm| &**fm))
+    }
+
+    fn encode_crate_root(&mut self) -> Lazy<CrateRoot> {
+        let mut i = self.position();
+
+        let crate_deps = self.tracked(
+            DepNode::GlobalMetaData((), GlobalMetaDataKind::CrateDeps),
+            IsolatedEncoder::encode_crate_deps,
+            ());
+        let dylib_dependency_formats = self.tracked(
+            DepNode::GlobalMetaData((), GlobalMetaDataKind::DylibDependencyFormats),
+            IsolatedEncoder::encode_dylib_dependency_formats,
+            ());
+        let dep_bytes = self.position() - i;
+
+        // Encode the language items.
+        i = self.position();
+        let lang_items = self.tracked(
+            DepNode::GlobalMetaData((), GlobalMetaDataKind::LangItems),
+            IsolatedEncoder::encode_lang_items,
+            ());
+
+        let lang_items_missing = self.tracked(
+            DepNode::GlobalMetaData((), GlobalMetaDataKind::LangItemsMissing),
+            IsolatedEncoder::encode_lang_items_missing,
+            ());
+        let lang_item_bytes = self.position() - i;
+
+        // Encode the native libraries used
+        i = self.position();
+        let native_libraries = self.tracked(
+            DepNode::GlobalMetaData((), GlobalMetaDataKind::NativeLibraries),
+            IsolatedEncoder::encode_native_libraries,
+            ());
+        let native_lib_bytes = self.position() - i;
+
+        // Encode codemap
+        i = self.position();
+        let codemap = self.encode_codemap();
+        let codemap_bytes = self.position() - i;
+
+        // Encode DefPathTable
+        i = self.position();
+        let def_path_table = self.encode_def_path_table();
+        let def_path_table_bytes = self.position() - i;
+
+        // Encode the def IDs of impls, for coherence checking.
+        i = self.position();
+        let impls = self.tracked(
+            DepNode::GlobalMetaData((), GlobalMetaDataKind::Impls),
+            IsolatedEncoder::encode_impls,
+            ());
+        let impl_bytes = self.position() - i;
+
+        // Encode exported symbols info.
+        i = self.position();
+        let exported_symbols = self.tracked(
+            DepNode::GlobalMetaData((), GlobalMetaDataKind::ExportedSymbols),
+            IsolatedEncoder::encode_exported_symbols,
+            self.exported_symbols);
+        let exported_symbols_bytes = self.position() - i;
+
+        // Encode and index the items.
+        i = self.position();
+        let items = self.encode_info_for_items();
+        let item_bytes = self.position() - i;
+
+        i = self.position();
+        let index = items.write_index(&mut self.opaque.cursor);
+        let index_bytes = self.position() - i;
+
+        let tcx = self.tcx;
+        let link_meta = self.link_meta;
+        let is_proc_macro = tcx.sess.crate_types.borrow().contains(&CrateTypeProcMacro);
+        let root = self.lazy(&CrateRoot {
+            name: tcx.crate_name(LOCAL_CRATE),
+            triple: tcx.sess.opts.target_triple.clone(),
+            hash: link_meta.crate_hash,
+            disambiguator: tcx.sess.local_crate_disambiguator(),
+            panic_strategy: Tracked::new(tcx.sess.panic_strategy()),
+            plugin_registrar_fn: tcx.sess
+                .plugin_registrar_fn
+                .get()
+                .map(|id| tcx.hir.local_def_id(id).index),
+            macro_derive_registrar: if is_proc_macro {
+                let id = tcx.sess.derive_registrar_fn.get().unwrap();
+                Some(tcx.hir.local_def_id(id).index)
+            } else {
+                None
+            },
+
+            crate_deps: crate_deps,
+            dylib_dependency_formats: dylib_dependency_formats,
+            lang_items: lang_items,
+            lang_items_missing: lang_items_missing,
+            native_libraries: native_libraries,
+            codemap: codemap,
+            def_path_table: def_path_table,
+            impls: impls,
+            exported_symbols: exported_symbols,
+            index: index,
+        });
+
+        let total_bytes = self.position();
+
+        self.metadata_hashes.global_hashes.push((
+            DepNode::GlobalMetaData((), GlobalMetaDataKind::Krate),
+            Fingerprint::from_smaller_hash(link_meta.crate_hash.as_u64())
+        ));
+
+        if self.tcx.sess.meta_stats() {
+            let mut zero_bytes = 0;
+            for e in self.opaque.cursor.get_ref() {
+                if *e == 0 {
+                    zero_bytes += 1;
+                }
+            }
+
+            println!("metadata stats:");
+            println!("             dep bytes: {}", dep_bytes);
+            println!("       lang item bytes: {}", lang_item_bytes);
+            println!("          native bytes: {}", native_lib_bytes);
+            println!("         codemap bytes: {}", codemap_bytes);
+            println!("            impl bytes: {}", impl_bytes);
+            println!("    exp. symbols bytes: {}", exported_symbols_bytes);
+            println!("  def-path table bytes: {}", def_path_table_bytes);
+            println!("            item bytes: {}", item_bytes);
+            println!("           index bytes: {}", index_bytes);
+            println!("            zero bytes: {}", zero_bytes);
+            println!("           total bytes: {}", total_bytes);
+        }
+
+        root
+    }
 }
 
-impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
+// These are methods for encoding various things. They are meant to be used with
+// IndexBuilder::record() and EncodeContext::tracked(). They actually
+// would not have to be methods of IsolatedEncoder (free standing functions
+// taking IsolatedEncoder as first argument would be just fine) but by making
+// them methods we don't have to repeat the lengthy `<'a, 'b: 'a, 'tcx: 'b>`
+// clause again and again.
+impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> {
     fn encode_variances_of(&mut self, def_id: DefId) -> LazySeq<ty::Variance> {
-        debug!("EntryBuilder::encode_variances_of({:?})", def_id);
+        debug!("IsolatedEncoder::encode_variances_of({:?})", def_id);
         let tcx = self.tcx;
         self.lazy_seq_from_slice(&tcx.variances_of(def_id))
     }
@@ -249,7 +483,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     fn encode_item_type(&mut self, def_id: DefId) -> Lazy<Ty<'tcx>> {
         let tcx = self.tcx;
         let ty = tcx.type_of(def_id);
-        debug!("EntryBuilder::encode_item_type({:?}) => {:?}", def_id, ty);
+        debug!("IsolatedEncoder::encode_item_type({:?}) => {:?}", def_id, ty);
         self.lazy(&ty)
     }
 
@@ -265,7 +499,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
         let def = tcx.adt_def(enum_did);
         let variant = &def.variants[index];
         let def_id = variant.did;
-        debug!("EntryBuilder::encode_enum_variant_info({:?})", def_id);
+        debug!("IsolatedEncoder::encode_enum_variant_info({:?})", def_id);
 
         let data = VariantData {
             ctor_kind: variant.ctor_kind,
@@ -306,7 +540,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
                            -> Entry<'tcx> {
         let tcx = self.tcx;
         let def_id = tcx.hir.local_def_id(id);
-        debug!("EntryBuilder::encode_info_for_mod({:?})", def_id);
+        debug!("IsolatedEncoder::encode_info_for_mod({:?})", def_id);
 
         let data = ModData {
             reexports: match tcx.export_map.get(&id) {
@@ -338,22 +572,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
             mir: None
         }
     }
-}
-
-impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
-    fn encode_fields(&mut self, adt_def_id: DefId) {
-        let def = self.tcx.adt_def(adt_def_id);
-        for (variant_index, variant) in def.variants.iter().enumerate() {
-            for (field_index, field) in variant.fields.iter().enumerate() {
-                self.record(field.did,
-                            EntryBuilder::encode_field,
-                            (adt_def_id, Untracked((variant_index, field_index))));
-            }
-        }
-    }
-}
 
-impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     /// Encode data for the given field of the given variant of the
     /// given ADT. The indices of the variant/field are untracked:
     /// this is ok because we will have to lookup the adt-def by its
@@ -370,7 +589,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
         let field = &variant.fields[field_index];
 
         let def_id = field.did;
-        debug!("EntryBuilder::encode_field({:?})", def_id);
+        debug!("IsolatedEncoder::encode_field({:?})", def_id);
 
         let variant_id = tcx.hir.as_local_node_id(variant.did).unwrap();
         let variant_data = tcx.hir.expect_variant_data(variant_id);
@@ -396,7 +615,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     }
 
     fn encode_struct_ctor(&mut self, (adt_def_id, def_id): (DefId, DefId)) -> Entry<'tcx> {
-        debug!("EntryBuilder::encode_struct_ctor({:?})", def_id);
+        debug!("IsolatedEncoder::encode_struct_ctor({:?})", def_id);
         let tcx = self.tcx;
         let variant = tcx.adt_def(adt_def_id).struct_variant();
 
@@ -438,19 +657,19 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     }
 
     fn encode_generics(&mut self, def_id: DefId) -> Lazy<ty::Generics> {
-        debug!("EntryBuilder::encode_generics({:?})", def_id);
+        debug!("IsolatedEncoder::encode_generics({:?})", def_id);
         let tcx = self.tcx;
         self.lazy(tcx.generics_of(def_id))
     }
 
     fn encode_predicates(&mut self, def_id: DefId) -> Lazy<ty::GenericPredicates<'tcx>> {
-        debug!("EntryBuilder::encode_predicates({:?})", def_id);
+        debug!("IsolatedEncoder::encode_predicates({:?})", def_id);
         let tcx = self.tcx;
         self.lazy(&tcx.predicates_of(def_id))
     }
 
     fn encode_info_for_trait_item(&mut self, def_id: DefId) -> Entry<'tcx> {
-        debug!("EntryBuilder::encode_info_for_trait_item({:?})", def_id);
+        debug!("IsolatedEncoder::encode_info_for_trait_item({:?})", def_id);
         let tcx = self.tcx;
 
         let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
@@ -533,7 +752,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     }
 
     fn encode_info_for_impl_item(&mut self, def_id: DefId) -> Entry<'tcx> {
-        debug!("EntryBuilder::encode_info_for_impl_item({:?})", def_id);
+        debug!("IsolatedEncoder::encode_info_for_impl_item({:?})", def_id);
         let node_id = self.tcx.hir.as_local_node_id(def_id).unwrap();
         let ast_item = self.tcx.hir.expect_impl_item(node_id);
         let impl_item = self.tcx.associated_item(def_id);
@@ -631,7 +850,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
 
     // Encodes the inherent implementations of a structure, enumeration, or trait.
     fn encode_inherent_implementations(&mut self, def_id: DefId) -> LazySeq<DefIndex> {
-        debug!("EntryBuilder::encode_inherent_implementations({:?})", def_id);
+        debug!("IsolatedEncoder::encode_inherent_implementations({:?})", def_id);
         let implementations = self.tcx.inherent_impls(def_id);
         if implementations.is_empty() {
             LazySeq::empty()
@@ -644,19 +863,19 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     }
 
     fn encode_stability(&mut self, def_id: DefId) -> Option<Lazy<attr::Stability>> {
-        debug!("EntryBuilder::encode_stability({:?})", def_id);
+        debug!("IsolatedEncoder::encode_stability({:?})", def_id);
         self.tcx.lookup_stability(def_id).map(|stab| self.lazy(stab))
     }
 
     fn encode_deprecation(&mut self, def_id: DefId) -> Option<Lazy<attr::Deprecation>> {
-        debug!("EntryBuilder::encode_deprecation({:?})", def_id);
+        debug!("IsolatedEncoder::encode_deprecation({:?})", def_id);
         self.tcx.lookup_deprecation(def_id).map(|depr| self.lazy(&depr))
     }
 
     fn encode_info_for_item(&mut self, (def_id, item): (DefId, &'tcx hir::Item)) -> Entry<'tcx> {
         let tcx = self.tcx;
 
-        debug!("EntryBuilder::encode_info_for_item({:?})", def_id);
+        debug!("IsolatedEncoder::encode_info_for_item({:?})", def_id);
 
         let kind = match item.node {
             hir::ItemStatic(_, hir::MutMutable, _) => EntryKind::MutStatic,
@@ -902,197 +1121,11 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
             mir: None,
         }
     }
-}
 
-impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
-    /// In some cases, along with the item itself, we also
-    /// encode some sub-items. Usually we want some info from the item
-    /// so it's easier to do that here then to wait until we would encounter
-    /// normally in the visitor walk.
-    fn encode_addl_info_for_item(&mut self, item: &hir::Item) {
-        let def_id = self.tcx.hir.local_def_id(item.id);
-        match item.node {
-            hir::ItemStatic(..) |
-            hir::ItemConst(..) |
-            hir::ItemFn(..) |
-            hir::ItemMod(..) |
-            hir::ItemForeignMod(..) |
-            hir::ItemGlobalAsm(..) |
-            hir::ItemExternCrate(..) |
-            hir::ItemUse(..) |
-            hir::ItemDefaultImpl(..) |
-            hir::ItemTy(..) => {
-                // no sub-item recording needed in these cases
-            }
-            hir::ItemEnum(..) => {
-                self.encode_fields(def_id);
-
-                let def = self.tcx.adt_def(def_id);
-                for (i, variant) in def.variants.iter().enumerate() {
-                    self.record(variant.did,
-                                EntryBuilder::encode_enum_variant_info,
-                                (def_id, Untracked(i)));
-                }
-            }
-            hir::ItemStruct(ref struct_def, _) => {
-                self.encode_fields(def_id);
-
-                // If the struct has a constructor, encode it.
-                if !struct_def.is_struct() {
-                    let ctor_def_id = self.tcx.hir.local_def_id(struct_def.id());
-                    self.record(ctor_def_id,
-                                EntryBuilder::encode_struct_ctor,
-                                (def_id, ctor_def_id));
-                }
-            }
-            hir::ItemUnion(..) => {
-                self.encode_fields(def_id);
-            }
-            hir::ItemImpl(..) => {
-                for &trait_item_def_id in self.tcx.associated_item_def_ids(def_id).iter() {
-                    self.record(trait_item_def_id,
-                                EntryBuilder::encode_info_for_impl_item,
-                                trait_item_def_id);
-                }
-            }
-            hir::ItemTrait(..) => {
-                for &item_def_id in self.tcx.associated_item_def_ids(def_id).iter() {
-                    self.record(item_def_id,
-                                EntryBuilder::encode_info_for_trait_item,
-                                item_def_id);
-                }
-            }
-        }
-    }
-}
-
-impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
-    fn encode_info_for_foreign_item(&mut self,
-                                    (def_id, nitem): (DefId, &hir::ForeignItem))
-                                    -> Entry<'tcx> {
-        let tcx = self.tcx;
-
-        debug!("EntryBuilder::encode_info_for_foreign_item({:?})", def_id);
-
-        let kind = match nitem.node {
-            hir::ForeignItemFn(_, ref names, _) => {
-                let data = FnData {
-                    constness: hir::Constness::NotConst,
-                    arg_names: self.encode_fn_arg_names(names),
-                };
-                EntryKind::ForeignFn(self.lazy(&data))
-            }
-            hir::ForeignItemStatic(_, true) => EntryKind::ForeignMutStatic,
-            hir::ForeignItemStatic(_, false) => EntryKind::ForeignImmStatic,
-        };
-
-        Entry {
-            kind: kind,
-            visibility: self.lazy(&ty::Visibility::from_hir(&nitem.vis, nitem.id, tcx)),
-            span: self.lazy(&nitem.span),
-            attributes: self.encode_attributes(&nitem.attrs),
-            children: LazySeq::empty(),
-            stability: self.encode_stability(def_id),
-            deprecation: self.encode_deprecation(def_id),
-
-            ty: Some(self.encode_item_type(def_id)),
-            inherent_impls: LazySeq::empty(),
-            variances: LazySeq::empty(),
-            generics: Some(self.encode_generics(def_id)),
-            predicates: Some(self.encode_predicates(def_id)),
-
-            ast: None,
-            mir: None,
-        }
-    }
-}
-
-struct EncodeVisitor<'a, 'b: 'a, 'tcx: 'b> {
-    index: IndexBuilder<'a, 'b, 'tcx>,
-}
-
-impl<'a, 'b, 'tcx> Visitor<'tcx> for EncodeVisitor<'a, 'b, 'tcx> {
-    fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
-        NestedVisitorMap::OnlyBodies(&self.index.tcx.hir)
-    }
-    fn visit_expr(&mut self, ex: &'tcx hir::Expr) {
-        intravisit::walk_expr(self, ex);
-        self.index.encode_info_for_expr(ex);
-    }
-    fn visit_item(&mut self, item: &'tcx hir::Item) {
-        intravisit::walk_item(self, item);
-        let def_id = self.index.tcx.hir.local_def_id(item.id);
-        match item.node {
-            hir::ItemExternCrate(_) |
-            hir::ItemUse(..) => (), // ignore these
-            _ => self.index.record(def_id, EntryBuilder::encode_info_for_item, (def_id, item)),
-        }
-        self.index.encode_addl_info_for_item(item);
-    }
-    fn visit_foreign_item(&mut self, ni: &'tcx hir::ForeignItem) {
-        intravisit::walk_foreign_item(self, ni);
-        let def_id = self.index.tcx.hir.local_def_id(ni.id);
-        self.index.record(def_id,
-                          EntryBuilder::encode_info_for_foreign_item,
-                          (def_id, ni));
-    }
-    fn visit_variant(&mut self,
-                     v: &'tcx hir::Variant,
-                     g: &'tcx hir::Generics,
-                     id: ast::NodeId) {
-        intravisit::walk_variant(self, v, g, id);
-
-        if let Some(discr) = v.node.disr_expr {
-            let def_id = self.index.tcx.hir.body_owner_def_id(discr);
-            self.index.record(def_id, EntryBuilder::encode_info_for_embedded_const, def_id);
-        }
-    }
-    fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
-        intravisit::walk_generics(self, generics);
-        self.index.encode_info_for_generics(generics);
-    }
-    fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
-        intravisit::walk_ty(self, ty);
-        self.index.encode_info_for_ty(ty);
-    }
-    fn visit_macro_def(&mut self, macro_def: &'tcx hir::MacroDef) {
-        let def_id = self.index.tcx.hir.local_def_id(macro_def.id);
-        self.index.record(def_id, EntryBuilder::encode_info_for_macro_def, macro_def);
-    }
-}
-
-impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
-    fn encode_info_for_generics(&mut self, generics: &hir::Generics) {
-        for ty_param in &generics.ty_params {
-            let def_id = self.tcx.hir.local_def_id(ty_param.id);
-            let has_default = Untracked(ty_param.default.is_some());
-            self.record(def_id, EntryBuilder::encode_info_for_ty_param, (def_id, has_default));
-        }
-    }
-
-    fn encode_info_for_ty(&mut self, ty: &hir::Ty) {
-        if let hir::TyImplTrait(_) = ty.node {
-            let def_id = self.tcx.hir.local_def_id(ty.id);
-            self.record(def_id, EntryBuilder::encode_info_for_anon_ty, def_id);
-        }
-    }
-
-    fn encode_info_for_expr(&mut self, expr: &hir::Expr) {
-        match expr.node {
-            hir::ExprClosure(..) => {
-                let def_id = self.tcx.hir.local_def_id(expr.id);
-                self.record(def_id, EntryBuilder::encode_info_for_closure, def_id);
-            }
-            _ => {}
-        }
-    }
-}
-
-impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     fn encode_info_for_ty_param(&mut self,
                                 (def_id, Untracked(has_default)): (DefId, Untracked<bool>))
                                 -> Entry<'tcx> {
-        debug!("EntryBuilder::encode_info_for_ty_param({:?})", def_id);
+        debug!("IsolatedEncoder::encode_info_for_ty_param({:?})", def_id);
         let tcx = self.tcx;
         Entry {
             kind: EntryKind::Type,
@@ -1119,7 +1152,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     }
 
     fn encode_info_for_anon_ty(&mut self, def_id: DefId) -> Entry<'tcx> {
-        debug!("EntryBuilder::encode_info_for_anon_ty({:?})", def_id);
+        debug!("IsolatedEncoder::encode_info_for_anon_ty({:?})", def_id);
         let tcx = self.tcx;
         Entry {
             kind: EntryKind::Type,
@@ -1142,7 +1175,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     }
 
     fn encode_info_for_closure(&mut self, def_id: DefId) -> Entry<'tcx> {
-        debug!("EntryBuilder::encode_info_for_closure({:?})", def_id);
+        debug!("IsolatedEncoder::encode_info_for_closure({:?})", def_id);
         let tcx = self.tcx;
 
         let data = ClosureData {
@@ -1171,7 +1204,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     }
 
     fn encode_info_for_embedded_const(&mut self, def_id: DefId) -> Entry<'tcx> {
-        debug!("EntryBuilder::encode_info_for_embedded_const({:?})", def_id);
+        debug!("IsolatedEncoder::encode_info_for_embedded_const({:?})", def_id);
         let tcx = self.tcx;
         let id = tcx.hir.as_local_node_id(def_id).unwrap();
         let body = tcx.hir.body_owned_by(id);
@@ -1198,154 +1231,70 @@ impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
 
     fn encode_attributes(&mut self, attrs: &[ast::Attribute]) -> LazySeq<ast::Attribute> {
         // NOTE: This must use lazy_seq_from_slice(), not lazy_seq() because
-        //       we really on the HashStable specialization for [Attribute]
+        //       we rely on the HashStable specialization for [Attribute]
         //       to properly filter things out.
         self.lazy_seq_from_slice(attrs)
     }
-}
 
-impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
-    fn encode_info_for_items(&mut self) -> Index {
-        let krate = self.tcx.hir.krate();
-        let mut index = IndexBuilder::new(self);
-        index.record(DefId::local(CRATE_DEF_INDEX),
-                     EntryBuilder::encode_info_for_mod,
-                     FromId(CRATE_NODE_ID, (&krate.module, &krate.attrs, &hir::Public)));
-        let mut visitor = EncodeVisitor { index: index };
-        krate.visit_all_item_likes(&mut visitor.as_deep_visitor());
-        for macro_def in &krate.exported_macros {
-            visitor.visit_macro_def(macro_def);
-        }
-        visitor.index.into_items()
+    fn encode_native_libraries(&mut self, _: ()) -> LazySeq<NativeLibrary> {
+        let used_libraries = self.tcx.sess.cstore.used_libraries();
+        self.lazy_seq(used_libraries)
     }
 
-    fn encode_crate_deps(&mut self) -> LazySeq<CrateDep> {
-        fn get_ordered_deps(cstore: &cstore::CStore) -> Vec<(CrateNum, Rc<cstore::CrateMetadata>)> {
-            // Pull the cnums and name,vers,hash out of cstore
-            let mut deps = Vec::new();
-            cstore.iter_crate_data(|cnum, val| {
-                deps.push((cnum, val.clone()));
-            });
+    fn encode_crate_deps(&mut self, _: ()) -> LazySeq<CrateDep> {
+        let cstore = &*self.tcx.sess.cstore;
+        let crates = cstore.crates();
 
-            // Sort by cnum
-            deps.sort_by(|kv1, kv2| kv1.0.cmp(&kv2.0));
+        let mut deps = crates
+            .iter()
+            .map(|&cnum| {
+                let dep = CrateDep {
+                    name: cstore.original_crate_name(cnum),
+                    hash: cstore.crate_hash(cnum),
+                    kind: cstore.dep_kind(cnum),
+                };
+                (cnum, dep)
+            })
+            .collect::<Vec<_>>();
+
+        deps.sort_by_key(|&(cnum, _)| cnum);
 
+        {
             // Sanity-check the crate numbers
             let mut expected_cnum = 1;
             for &(n, _) in &deps {
                 assert_eq!(n, CrateNum::new(expected_cnum));
                 expected_cnum += 1;
             }
-
-            deps
         }
 
         // We're just going to write a list of crate 'name-hash-version's, with
         // the assumption that they are numbered 1 to n.
         // FIXME (#2166): This is not nearly enough to support correct versioning
         // but is enough to get transitive crate dependencies working.
-        let deps = get_ordered_deps(self.cstore);
-        self.lazy_seq(deps.iter().map(|&(_, ref dep)| {
-            CrateDep {
-                name: dep.name(),
-                hash: dep.hash(),
-                kind: dep.dep_kind.get(),
-            }
-        }))
+        self.lazy_seq_ref(deps.iter().map(|&(_, ref dep)| dep))
     }
 
-    fn encode_lang_items(&mut self) -> (LazySeq<(DefIndex, usize)>, LazySeq<lang_items::LangItem>) {
+    fn encode_lang_items(&mut self, _: ()) -> LazySeq<(DefIndex, usize)> {
         let tcx = self.tcx;
         let lang_items = tcx.lang_items.items().iter();
-        (self.lazy_seq(lang_items.enumerate().filter_map(|(i, &opt_def_id)| {
+        self.lazy_seq(lang_items.enumerate().filter_map(|(i, &opt_def_id)| {
             if let Some(def_id) = opt_def_id {
                 if def_id.is_local() {
                     return Some((def_id.index, i));
                 }
             }
             None
-        })),
-         self.lazy_seq_ref(&tcx.lang_items.missing))
-    }
-
-    fn encode_native_libraries(&mut self) -> LazySeq<NativeLibrary> {
-        let used_libraries = self.tcx.sess.cstore.used_libraries();
-        self.lazy_seq(used_libraries)
-    }
-
-    fn encode_codemap(&mut self) -> LazySeq<syntax_pos::FileMap> {
-        let codemap = self.tcx.sess.codemap();
-        let all_filemaps = codemap.files.borrow();
-        let adapted = all_filemaps.iter()
-            .filter(|filemap| {
-                // No need to re-export imported filemaps, as any downstream
-                // crate will import them from their original source.
-                !filemap.is_imported()
-            })
-            .map(|filemap| {
-                // When exporting FileMaps, we expand all paths to absolute
-                // paths because any relative paths are potentially relative to
-                // a wrong directory.
-                // However, if a path has been modified via
-                // `-Zremap-path-prefix` we assume the user has already set
-                // things up the way they want and don't touch the path values
-                // anymore.
-                let name = Path::new(&filemap.name);
-                let (ref working_dir, working_dir_was_remapped) = self.tcx.sess.working_dir;
-                if filemap.name_was_remapped ||
-                   (name.is_relative() && working_dir_was_remapped) {
-                    // This path of this FileMap has been modified by
-                    // path-remapping, so we use it verbatim (and avoid cloning
-                    // the whole map in the process).
-                    filemap.clone()
-                } else {
-                    let mut adapted = (**filemap).clone();
-                    let abs_path = Path::new(working_dir).join(name)
-                                                         .to_string_lossy()
-                                                         .into_owned();
-                    adapted.name = abs_path;
-                    Rc::new(adapted)
-                }
-            })
-            .collect::<Vec<_>>();
-
-        self.lazy_seq_ref(adapted.iter().map(|fm| &**fm))
-    }
-
-    fn encode_def_path_table(&mut self) -> Lazy<DefPathTable> {
-        let definitions = self.tcx.hir.definitions();
-        self.lazy(definitions.def_path_table())
-    }
-}
-
-struct ImplVisitor<'a, 'tcx: 'a> {
-    tcx: TyCtxt<'a, 'tcx, 'tcx>,
-    impls: FxHashMap<DefId, Vec<DefIndex>>,
-}
-
-impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ImplVisitor<'a, 'tcx> {
-    fn visit_item(&mut self, item: &hir::Item) {
-        if let hir::ItemImpl(..) = item.node {
-            let impl_id = self.tcx.hir.local_def_id(item.id);
-            if let Some(trait_ref) = self.tcx.impl_trait_ref(impl_id) {
-                self.impls
-                    .entry(trait_ref.def_id)
-                    .or_insert(vec![])
-                    .push(impl_id.index);
-            }
-        }
+        }))
     }
 
-    fn visit_trait_item(&mut self, _trait_item: &'v hir::TraitItem) {}
-
-    fn visit_impl_item(&mut self, _impl_item: &'v hir::ImplItem) {
-        // handled in `visit_item` above
+    fn encode_lang_items_missing(&mut self, _: ()) -> LazySeq<lang_items::LangItem> {
+        let tcx = self.tcx;
+        self.lazy_seq_ref(&tcx.lang_items.missing)
     }
-}
 
-impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
     /// Encodes an index, mapping each trait to its (local) implementations.
-    fn encode_impls(&mut self) -> LazySeq<TraitImpls> {
+    fn encode_impls(&mut self, _: ()) -> LazySeq<TraitImpls> {
         let mut visitor = ImplVisitor {
             tcx: self.tcx,
             impls: FxHashMap(),
@@ -1371,13 +1320,12 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
     // middle::reachable module but filters out items that either don't have a
     // symbol associated with them (they weren't translated) or if they're an FFI
     // definition (as that's not defined in this crate).
-    fn encode_exported_symbols(&mut self) -> LazySeq<DefIndex> {
-        let exported_symbols = self.exported_symbols;
+    fn encode_exported_symbols(&mut self, exported_symbols: &NodeSet) -> LazySeq<DefIndex> {
         let tcx = self.tcx;
         self.lazy_seq(exported_symbols.iter().map(|&id| tcx.hir.local_def_id(id).index))
     }
 
-    fn encode_dylib_dependency_formats(&mut self) -> LazySeq<Option<LinkagePreference>> {
+    fn encode_dylib_dependency_formats(&mut self, _: ()) -> LazySeq<Option<LinkagePreference>> {
         match self.tcx.sess.dependency_formats.borrow().get(&config::CrateTypeDylib) {
             Some(arr) => {
                 self.lazy_seq(arr.iter().map(|slot| {
@@ -1393,111 +1341,221 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
             None => LazySeq::empty(),
         }
     }
-}
 
-impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
-    fn encode_crate_root(&mut self) -> Lazy<CrateRoot> {
-        let mut i = self.position();
-        let crate_deps = self.encode_crate_deps();
-        let dylib_dependency_formats = self.encode_dylib_dependency_formats();
-        let dep_bytes = self.position() - i;
+    fn encode_info_for_foreign_item(&mut self,
+                                    (def_id, nitem): (DefId, &hir::ForeignItem))
+                                    -> Entry<'tcx> {
+        let tcx = self.tcx;
 
-        // Encode the language items.
-        i = self.position();
-        let (lang_items, lang_items_missing) = self.encode_lang_items();
-        let lang_item_bytes = self.position() - i;
+        debug!("IsolatedEncoder::encode_info_for_foreign_item({:?})", def_id);
 
-        // Encode the native libraries used
-        i = self.position();
-        let native_libraries = self.encode_native_libraries();
-        let native_lib_bytes = self.position() - i;
+        let kind = match nitem.node {
+            hir::ForeignItemFn(_, ref names, _) => {
+                let data = FnData {
+                    constness: hir::Constness::NotConst,
+                    arg_names: self.encode_fn_arg_names(names),
+                };
+                EntryKind::ForeignFn(self.lazy(&data))
+            }
+            hir::ForeignItemStatic(_, true) => EntryKind::ForeignMutStatic,
+            hir::ForeignItemStatic(_, false) => EntryKind::ForeignImmStatic,
+        };
 
-        // Encode codemap
-        i = self.position();
-        let codemap = self.encode_codemap();
-        let codemap_bytes = self.position() - i;
+        Entry {
+            kind: kind,
+            visibility: self.lazy(&ty::Visibility::from_hir(&nitem.vis, nitem.id, tcx)),
+            span: self.lazy(&nitem.span),
+            attributes: self.encode_attributes(&nitem.attrs),
+            children: LazySeq::empty(),
+            stability: self.encode_stability(def_id),
+            deprecation: self.encode_deprecation(def_id),
 
-        // Encode DefPathTable
-        i = self.position();
-        let def_path_table = self.encode_def_path_table();
-        let def_path_table_bytes = self.position() - i;
+            ty: Some(self.encode_item_type(def_id)),
+            inherent_impls: LazySeq::empty(),
+            variances: LazySeq::empty(),
+            generics: Some(self.encode_generics(def_id)),
+            predicates: Some(self.encode_predicates(def_id)),
 
-        // Encode the def IDs of impls, for coherence checking.
-        i = self.position();
-        let impls = self.encode_impls();
-        let impl_bytes = self.position() - i;
+            ast: None,
+            mir: None,
+        }
+    }
+}
 
-        // Encode exported symbols info.
-        i = self.position();
-        let exported_symbols = self.encode_exported_symbols();
-        let exported_symbols_bytes = self.position() - i;
+struct EncodeVisitor<'a, 'b: 'a, 'tcx: 'b> {
+    index: IndexBuilder<'a, 'b, 'tcx>,
+}
 
-        // Encode and index the items.
-        i = self.position();
-        let items = self.encode_info_for_items();
-        let item_bytes = self.position() - i;
+impl<'a, 'b, 'tcx> Visitor<'tcx> for EncodeVisitor<'a, 'b, 'tcx> {
+    fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
+        NestedVisitorMap::OnlyBodies(&self.index.tcx.hir)
+    }
+    fn visit_expr(&mut self, ex: &'tcx hir::Expr) {
+        intravisit::walk_expr(self, ex);
+        self.index.encode_info_for_expr(ex);
+    }
+    fn visit_item(&mut self, item: &'tcx hir::Item) {
+        intravisit::walk_item(self, item);
+        let def_id = self.index.tcx.hir.local_def_id(item.id);
+        match item.node {
+            hir::ItemExternCrate(_) |
+            hir::ItemUse(..) => (), // ignore these
+            _ => self.index.record(def_id, IsolatedEncoder::encode_info_for_item, (def_id, item)),
+        }
+        self.index.encode_addl_info_for_item(item);
+    }
+    fn visit_foreign_item(&mut self, ni: &'tcx hir::ForeignItem) {
+        intravisit::walk_foreign_item(self, ni);
+        let def_id = self.index.tcx.hir.local_def_id(ni.id);
+        self.index.record(def_id,
+                          IsolatedEncoder::encode_info_for_foreign_item,
+                          (def_id, ni));
+    }
+    fn visit_variant(&mut self,
+                     v: &'tcx hir::Variant,
+                     g: &'tcx hir::Generics,
+                     id: ast::NodeId) {
+        intravisit::walk_variant(self, v, g, id);
 
-        i = self.position();
-        let index = items.write_index(&mut self.opaque.cursor);
-        let index_bytes = self.position() - i;
+        if let Some(discr) = v.node.disr_expr {
+            let def_id = self.index.tcx.hir.body_owner_def_id(discr);
+            self.index.record(def_id, IsolatedEncoder::encode_info_for_embedded_const, def_id);
+        }
+    }
+    fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
+        intravisit::walk_generics(self, generics);
+        self.index.encode_info_for_generics(generics);
+    }
+    fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
+        intravisit::walk_ty(self, ty);
+        self.index.encode_info_for_ty(ty);
+    }
+    fn visit_macro_def(&mut self, macro_def: &'tcx hir::MacroDef) {
+        let def_id = self.index.tcx.hir.local_def_id(macro_def.id);
+        self.index.record(def_id, IsolatedEncoder::encode_info_for_macro_def, macro_def);
+    }
+}
 
-        let tcx = self.tcx;
-        let link_meta = self.link_meta;
-        let is_proc_macro = tcx.sess.crate_types.borrow().contains(&CrateTypeProcMacro);
-        let root = self.lazy(&CrateRoot {
-            name: tcx.crate_name(LOCAL_CRATE),
-            triple: tcx.sess.opts.target_triple.clone(),
-            hash: link_meta.crate_hash,
-            disambiguator: tcx.sess.local_crate_disambiguator(),
-            panic_strategy: tcx.sess.panic_strategy(),
-            plugin_registrar_fn: tcx.sess
-                .plugin_registrar_fn
-                .get()
-                .map(|id| tcx.hir.local_def_id(id).index),
-            macro_derive_registrar: if is_proc_macro {
-                let id = tcx.sess.derive_registrar_fn.get().unwrap();
-                Some(tcx.hir.local_def_id(id).index)
-            } else {
-                None
-            },
+impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
+    fn encode_fields(&mut self, adt_def_id: DefId) {
+        let def = self.tcx.adt_def(adt_def_id);
+        for (variant_index, variant) in def.variants.iter().enumerate() {
+            for (field_index, field) in variant.fields.iter().enumerate() {
+                self.record(field.did,
+                            IsolatedEncoder::encode_field,
+                            (adt_def_id, Untracked((variant_index, field_index))));
+            }
+        }
+    }
 
-            crate_deps: crate_deps,
-            dylib_dependency_formats: dylib_dependency_formats,
-            lang_items: lang_items,
-            lang_items_missing: lang_items_missing,
-            native_libraries: native_libraries,
-            codemap: codemap,
-            def_path_table: def_path_table,
-            impls: impls,
-            exported_symbols: exported_symbols,
-            index: index,
-        });
+    fn encode_info_for_generics(&mut self, generics: &hir::Generics) {
+        for ty_param in &generics.ty_params {
+            let def_id = self.tcx.hir.local_def_id(ty_param.id);
+            let has_default = Untracked(ty_param.default.is_some());
+            self.record(def_id, IsolatedEncoder::encode_info_for_ty_param, (def_id, has_default));
+        }
+    }
 
-        let total_bytes = self.position();
+    fn encode_info_for_ty(&mut self, ty: &hir::Ty) {
+        if let hir::TyImplTrait(_) = ty.node {
+            let def_id = self.tcx.hir.local_def_id(ty.id);
+            self.record(def_id, IsolatedEncoder::encode_info_for_anon_ty, def_id);
+        }
+    }
 
-        if self.tcx.sess.meta_stats() {
-            let mut zero_bytes = 0;
-            for e in self.opaque.cursor.get_ref() {
-                if *e == 0 {
-                    zero_bytes += 1;
+    fn encode_info_for_expr(&mut self, expr: &hir::Expr) {
+        match expr.node {
+            hir::ExprClosure(..) => {
+                let def_id = self.tcx.hir.local_def_id(expr.id);
+                self.record(def_id, IsolatedEncoder::encode_info_for_closure, def_id);
+            }
+            _ => {}
+        }
+    }
+
+    /// In some cases, along with the item itself, we also
+    /// encode some sub-items. Usually we want some info from the item
+    /// so it's easier to do that here then to wait until we would encounter
+    /// normally in the visitor walk.
+    fn encode_addl_info_for_item(&mut self, item: &hir::Item) {
+        let def_id = self.tcx.hir.local_def_id(item.id);
+        match item.node {
+            hir::ItemStatic(..) |
+            hir::ItemConst(..) |
+            hir::ItemFn(..) |
+            hir::ItemMod(..) |
+            hir::ItemForeignMod(..) |
+            hir::ItemGlobalAsm(..) |
+            hir::ItemExternCrate(..) |
+            hir::ItemUse(..) |
+            hir::ItemDefaultImpl(..) |
+            hir::ItemTy(..) => {
+                // no sub-item recording needed in these cases
+            }
+            hir::ItemEnum(..) => {
+                self.encode_fields(def_id);
+
+                let def = self.tcx.adt_def(def_id);
+                for (i, variant) in def.variants.iter().enumerate() {
+                    self.record(variant.did,
+                                IsolatedEncoder::encode_enum_variant_info,
+                                (def_id, Untracked(i)));
                 }
             }
+            hir::ItemStruct(ref struct_def, _) => {
+                self.encode_fields(def_id);
 
-            println!("metadata stats:");
-            println!("             dep bytes: {}", dep_bytes);
-            println!("       lang item bytes: {}", lang_item_bytes);
-            println!("          native bytes: {}", native_lib_bytes);
-            println!("         codemap bytes: {}", codemap_bytes);
-            println!("            impl bytes: {}", impl_bytes);
-            println!("    exp. symbols bytes: {}", exported_symbols_bytes);
-            println!("  def-path table bytes: {}", def_path_table_bytes);
-            println!("            item bytes: {}", item_bytes);
-            println!("           index bytes: {}", index_bytes);
-            println!("            zero bytes: {}", zero_bytes);
-            println!("           total bytes: {}", total_bytes);
+                // If the struct has a constructor, encode it.
+                if !struct_def.is_struct() {
+                    let ctor_def_id = self.tcx.hir.local_def_id(struct_def.id());
+                    self.record(ctor_def_id,
+                                IsolatedEncoder::encode_struct_ctor,
+                                (def_id, ctor_def_id));
+                }
+            }
+            hir::ItemUnion(..) => {
+                self.encode_fields(def_id);
+            }
+            hir::ItemImpl(..) => {
+                for &trait_item_def_id in self.tcx.associated_item_def_ids(def_id).iter() {
+                    self.record(trait_item_def_id,
+                                IsolatedEncoder::encode_info_for_impl_item,
+                                trait_item_def_id);
+                }
+            }
+            hir::ItemTrait(..) => {
+                for &item_def_id in self.tcx.associated_item_def_ids(def_id).iter() {
+                    self.record(item_def_id,
+                                IsolatedEncoder::encode_info_for_trait_item,
+                                item_def_id);
+                }
+            }
         }
+    }
+}
 
-        root
+struct ImplVisitor<'a, 'tcx: 'a> {
+    tcx: TyCtxt<'a, 'tcx, 'tcx>,
+    impls: FxHashMap<DefId, Vec<DefIndex>>,
+}
+
+impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ImplVisitor<'a, 'tcx> {
+    fn visit_item(&mut self, item: &hir::Item) {
+        if let hir::ItemImpl(..) = item.node {
+            let impl_id = self.tcx.hir.local_def_id(item.id);
+            if let Some(trait_ref) = self.tcx.impl_trait_ref(impl_id) {
+                self.impls
+                    .entry(trait_ref.def_id)
+                    .or_insert(vec![])
+                    .push(impl_id.index);
+            }
+        }
+    }
+
+    fn visit_trait_item(&mut self, _trait_item: &'v hir::TraitItem) {}
+
+    fn visit_impl_item(&mut self, _impl_item: &'v hir::ImplItem) {
+        // handled in `visit_item` above
     }
 }
 
@@ -1525,7 +1583,6 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
 // generated regardless of trailing bytes that end up in it.
 
 pub fn encode_metadata<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
-                                 cstore: &cstore::CStore,
                                  link_meta: &LinkMeta,
                                  exported_symbols: &NodeSet)
                                  -> EncodedMetadata
@@ -1533,20 +1590,24 @@ pub fn encode_metadata<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     let mut cursor = Cursor::new(vec![]);
     cursor.write_all(METADATA_HEADER).unwrap();
 
-    // Will be filed with the root position after encoding everything.
+    // Will be filled with the root position after encoding everything.
     cursor.write_all(&[0, 0, 0, 0]).unwrap();
 
+     let compute_ich = (tcx.sess.opts.debugging_opts.query_dep_graph ||
+                        tcx.sess.opts.debugging_opts.incremental_cc) &&
+                        tcx.sess.opts.build_dep_graph();
+
     let (root, metadata_hashes) = {
         let mut ecx = EncodeContext {
             opaque: opaque::Encoder::new(&mut cursor),
             tcx: tcx,
             link_meta: link_meta,
-            cstore: cstore,
             exported_symbols: exported_symbols,
             lazy_state: LazyState::NoNode,
             type_shorthands: Default::default(),
             predicate_shorthands: Default::default(),
-            metadata_hashes: Vec::new(),
+            metadata_hashes: EncodedMetadataHashes::new(),
+            compute_ich: compute_ich,
         };
 
         // Encode the rustc version string in a predictable location.
diff --git a/src/librustc_metadata/index_builder.rs b/src/librustc_metadata/index_builder.rs
index 01f948866b8..478202aeba4 100644
--- a/src/librustc_metadata/index_builder.rs
+++ b/src/librustc_metadata/index_builder.rs
@@ -58,20 +58,16 @@
 use encoder::EncodeContext;
 use index::Index;
 use schema::*;
+use isolated_encoder::IsolatedEncoder;
 
 use rustc::hir;
 use rustc::hir::def_id::DefId;
-use rustc::ich::{StableHashingContext, Fingerprint};
 use rustc::middle::cstore::EncodedMetadataHash;
 use rustc::ty::TyCtxt;
 use syntax::ast;
 
 use std::ops::{Deref, DerefMut};
 
-use rustc_data_structures::accumulate_vec::AccumulateVec;
-use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
-use rustc_serialize::Encodable;
-
 /// Builder that can encode new items, adding them into the index.
 /// Item encoding cannot be nested.
 pub struct IndexBuilder<'a, 'b: 'a, 'tcx: 'b> {
@@ -119,7 +115,7 @@ impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
     /// content system.
     pub fn record<'x, DATA>(&'x mut self,
                             id: DefId,
-                            op: fn(&mut EntryBuilder<'x, 'b, 'tcx>, DATA) -> Entry<'tcx>,
+                            op: fn(&mut IsolatedEncoder<'x, 'b, 'tcx>, DATA) -> Entry<'tcx>,
                             data: DATA)
         where DATA: DepGraphRead
     {
@@ -132,29 +128,19 @@ impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
         // unclear whether that would be a win since hashing is cheap enough.
         let _task = tcx.dep_graph.in_ignore();
 
-        let compute_ich = (tcx.sess.opts.debugging_opts.query_dep_graph ||
-                           tcx.sess.opts.debugging_opts.incremental_cc) &&
-                           tcx.sess.opts.build_dep_graph();
-
         let ecx: &'x mut EncodeContext<'b, 'tcx> = &mut *self.ecx;
-        let mut entry_builder = EntryBuilder {
-            tcx: tcx,
-            ecx: ecx,
-            hcx: if compute_ich {
-                Some((StableHashingContext::new(tcx), StableHasher::new()))
-            } else {
-                None
-            }
-        };
-
+        let mut entry_builder = IsolatedEncoder::new(ecx);
         let entry = op(&mut entry_builder, data);
+        let entry = entry_builder.lazy(&entry);
 
-        if let Some((ref mut hcx, ref mut hasher)) = entry_builder.hcx {
-            entry.hash_stable(hcx, hasher);
+        let (fingerprint, ecx) = entry_builder.finish();
+        if let Some(hash) = fingerprint {
+            ecx.metadata_hashes.entry_hashes.push(EncodedMetadataHash {
+                def_index: id.index,
+                hash: hash,
+            });
         }
 
-        let entry = entry_builder.ecx.lazy(&entry);
-        entry_builder.finish(id);
         self.items.record(id, entry);
     }
 
@@ -257,91 +243,3 @@ impl<T> DepGraphRead for FromId<T> {
         tcx.hir.read(self.0);
     }
 }
-
-pub struct EntryBuilder<'a, 'b: 'a, 'tcx: 'b> {
-    pub tcx: TyCtxt<'b, 'tcx, 'tcx>,
-    ecx: &'a mut EncodeContext<'b, 'tcx>,
-    hcx: Option<(StableHashingContext<'b, 'tcx>, StableHasher<Fingerprint>)>,
-}
-
-impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
-
-    pub fn finish(self, def_id: DefId) {
-        if let Some((_, hasher)) = self.hcx {
-            let hash = hasher.finish();
-            self.ecx.metadata_hashes.push(EncodedMetadataHash {
-                def_index: def_id.index,
-                hash: hash,
-            });
-        }
-    }
-
-    pub fn lazy<T>(&mut self, value: &T) -> Lazy<T>
-        where T: Encodable + HashStable<StableHashingContext<'b, 'tcx>>
-    {
-        if let Some((ref mut hcx, ref mut hasher)) = self.hcx {
-            value.hash_stable(hcx, hasher);
-            debug!("metadata-hash: {:?}", hasher);
-        }
-        self.ecx.lazy(value)
-    }
-
-    pub fn lazy_seq<I, T>(&mut self, iter: I) -> LazySeq<T>
-        where I: IntoIterator<Item = T>,
-              T: Encodable + HashStable<StableHashingContext<'b, 'tcx>>
-    {
-        if let Some((ref mut hcx, ref mut hasher)) = self.hcx {
-            let iter = iter.into_iter();
-            let (lower_bound, upper_bound) = iter.size_hint();
-
-            if upper_bound == Some(lower_bound) {
-                lower_bound.hash_stable(hcx, hasher);
-                let mut num_items_hashed = 0;
-                let ret = self.ecx.lazy_seq(iter.inspect(|item| {
-                    item.hash_stable(hcx, hasher);
-                    num_items_hashed += 1;
-                }));
-
-                // Sometimes items in a sequence are filtered out without being
-                // hashed (e.g. for &[ast::Attribute]) and this code path cannot
-                // handle that correctly, so we want to make sure we didn't hit
-                // it by accident.
-                if lower_bound != num_items_hashed {
-                    bug!("Hashed a different number of items ({}) than expected ({})",
-                         num_items_hashed,
-                         lower_bound);
-                }
-                debug!("metadata-hash: {:?}", hasher);
-                ret
-            } else {
-                // Collect into a vec so we know the length of the sequence
-                let items: AccumulateVec<[T; 32]> = iter.collect();
-                items.hash_stable(hcx, hasher);
-                debug!("metadata-hash: {:?}", hasher);
-                self.ecx.lazy_seq(items)
-            }
-        } else {
-            self.ecx.lazy_seq(iter)
-        }
-    }
-
-    pub fn lazy_seq_from_slice<T>(&mut self, slice: &[T]) -> LazySeq<T>
-        where T: Encodable + HashStable<StableHashingContext<'b, 'tcx>>
-    {
-        if let Some((ref mut hcx, ref mut hasher)) = self.hcx {
-            slice.hash_stable(hcx, hasher);
-            debug!("metadata-hash: {:?}", hasher);
-        }
-        self.ecx.lazy_seq_ref(slice.iter())
-    }
-
-    pub fn lazy_seq_ref_from_slice<T>(&mut self, slice: &[&T]) -> LazySeq<T>
-        where T: Encodable + HashStable<StableHashingContext<'b, 'tcx>>
-    {
-        if let Some((ref mut hcx, ref mut hasher)) = self.hcx {
-            slice.hash_stable(hcx, hasher);
-            debug!("metadata-hash: {:?}", hasher);
-        }
-        self.ecx.lazy_seq_ref(slice.iter().map(|x| *x))
-    }
-}
diff --git a/src/librustc_metadata/isolated_encoder.rs b/src/librustc_metadata/isolated_encoder.rs
new file mode 100644
index 00000000000..7722a7b10c9
--- /dev/null
+++ b/src/librustc_metadata/isolated_encoder.rs
@@ -0,0 +1,160 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use encoder::EncodeContext;
+use schema::{Lazy, LazySeq};
+
+use rustc::ich::{StableHashingContext, Fingerprint};
+use rustc::ty::TyCtxt;
+
+use rustc_data_structures::accumulate_vec::AccumulateVec;
+use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
+use rustc_serialize::Encodable;
+
+/// The IsolatedEncoder provides facilities to write to crate metadata while
+/// making sure that anything going through it is also feed into an ICH hasher.
+pub struct IsolatedEncoder<'a, 'b: 'a, 'tcx: 'b> {
+    pub tcx: TyCtxt<'b, 'tcx, 'tcx>,
+    ecx: &'a mut EncodeContext<'b, 'tcx>,
+    hcx: Option<(StableHashingContext<'b, 'tcx>, StableHasher<Fingerprint>)>,
+}
+
+impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> {
+
+    pub fn new(ecx: &'a mut EncodeContext<'b, 'tcx>) -> Self {
+        let tcx = ecx.tcx;
+        let compute_ich = ecx.compute_ich;
+        IsolatedEncoder {
+            tcx: tcx,
+            ecx: ecx,
+            hcx: if compute_ich {
+                Some((StableHashingContext::new(tcx), StableHasher::new()))
+            } else {
+                None
+            }
+        }
+    }
+
+    pub fn finish(self) -> (Option<Fingerprint>, &'a mut EncodeContext<'b, 'tcx>) {
+        if let Some((_, hasher)) = self.hcx {
+            (Some(hasher.finish()), self.ecx)
+        } else {
+            (None, self.ecx)
+        }
+    }
+
+    pub fn lazy<T>(&mut self, value: &T) -> Lazy<T>
+        where T: Encodable + HashStable<StableHashingContext<'b, 'tcx>>
+    {
+        if let Some((ref mut hcx, ref mut hasher)) = self.hcx {
+            value.hash_stable(hcx, hasher);
+            debug!("metadata-hash: {:?}", hasher);
+        }
+        self.ecx.lazy(value)
+    }
+
+    pub fn lazy_seq<I, T>(&mut self, iter: I) -> LazySeq<T>
+        where I: IntoIterator<Item = T>,
+              T: Encodable + HashStable<StableHashingContext<'b, 'tcx>>
+    {
+        if let Some((ref mut hcx, ref mut hasher)) = self.hcx {
+            let iter = iter.into_iter();
+            let (lower_bound, upper_bound) = iter.size_hint();
+
+            if upper_bound == Some(lower_bound) {
+                lower_bound.hash_stable(hcx, hasher);
+                let mut num_items_hashed = 0;
+                let ret = self.ecx.lazy_seq(iter.inspect(|item| {
+                    item.hash_stable(hcx, hasher);
+                    num_items_hashed += 1;
+                }));
+
+                // Sometimes items in a sequence are filtered out without being
+                // hashed (e.g. for &[ast::Attribute]) and this code path cannot
+                // handle that correctly, so we want to make sure we didn't hit
+                // it by accident.
+                if lower_bound != num_items_hashed {
+                    bug!("Hashed a different number of items ({}) than expected ({})",
+                         num_items_hashed,
+                         lower_bound);
+                }
+                debug!("metadata-hash: {:?}", hasher);
+                ret
+            } else {
+                // Collect into a vec so we know the length of the sequence
+                let items: AccumulateVec<[T; 32]> = iter.collect();
+                items.hash_stable(hcx, hasher);
+                debug!("metadata-hash: {:?}", hasher);
+                self.ecx.lazy_seq(items)
+            }
+        } else {
+            self.ecx.lazy_seq(iter)
+        }
+    }
+
+    pub fn lazy_seq_ref<'x, I, T>(&mut self, iter: I) -> LazySeq<T>
+        where I: IntoIterator<Item = &'x T>,
+              T: 'x + Encodable + HashStable<StableHashingContext<'b, 'tcx>>
+    {
+        if let Some((ref mut hcx, ref mut hasher)) = self.hcx {
+            let iter = iter.into_iter();
+            let (lower_bound, upper_bound) = iter.size_hint();
+
+            if upper_bound == Some(lower_bound) {
+                lower_bound.hash_stable(hcx, hasher);
+                let mut num_items_hashed = 0;
+                let ret = self.ecx.lazy_seq_ref(iter.inspect(|item| {
+                    item.hash_stable(hcx, hasher);
+                    num_items_hashed += 1;
+                }));
+
+                // Sometimes items in a sequence are filtered out without being
+                // hashed (e.g. for &[ast::Attribute]) and this code path cannot
+                // handle that correctly, so we want to make sure we didn't hit
+                // it by accident.
+                if lower_bound != num_items_hashed {
+                    bug!("Hashed a different number of items ({}) than expected ({})",
+                         num_items_hashed,
+                         lower_bound);
+                }
+                debug!("metadata-hash: {:?}", hasher);
+                ret
+            } else {
+                // Collect into a vec so we know the length of the sequence
+                let items: AccumulateVec<[&'x T; 32]> = iter.collect();
+                items.hash_stable(hcx, hasher);
+                debug!("metadata-hash: {:?}", hasher);
+                self.ecx.lazy_seq_ref(items.iter().map(|x| *x))
+            }
+        } else {
+            self.ecx.lazy_seq_ref(iter)
+        }
+    }
+
+    pub fn lazy_seq_from_slice<T>(&mut self, slice: &[T]) -> LazySeq<T>
+        where T: Encodable + HashStable<StableHashingContext<'b, 'tcx>>
+    {
+        if let Some((ref mut hcx, ref mut hasher)) = self.hcx {
+            slice.hash_stable(hcx, hasher);
+            debug!("metadata-hash: {:?}", hasher);
+        }
+        self.ecx.lazy_seq_ref(slice.iter())
+    }
+
+    pub fn lazy_seq_ref_from_slice<T>(&mut self, slice: &[&T]) -> LazySeq<T>
+        where T: Encodable + HashStable<StableHashingContext<'b, 'tcx>>
+    {
+        if let Some((ref mut hcx, ref mut hasher)) = self.hcx {
+            slice.hash_stable(hcx, hasher);
+            debug!("metadata-hash: {:?}", hasher);
+        }
+        self.ecx.lazy_seq_ref(slice.iter().map(|x| *x))
+    }
+}
diff --git a/src/librustc_metadata/lib.rs b/src/librustc_metadata/lib.rs
index b9e142ac650..90eb2bc0f6a 100644
--- a/src/librustc_metadata/lib.rs
+++ b/src/librustc_metadata/lib.rs
@@ -57,6 +57,7 @@ mod index;
 mod encoder;
 mod decoder;
 mod cstore_impl;
+mod isolated_encoder;
 mod schema;
 
 pub mod creader;
diff --git a/src/librustc_metadata/schema.rs b/src/librustc_metadata/schema.rs
index 5870903e771..5abe1adfb6f 100644
--- a/src/librustc_metadata/schema.rs
+++ b/src/librustc_metadata/schema.rs
@@ -13,7 +13,7 @@ use index;
 
 use rustc::hir;
 use rustc::hir::def::{self, CtorKind};
-use rustc::hir::def_id::{DefIndex, DefId};
+use rustc::hir::def_id::{DefIndex, DefId, CrateNum};
 use rustc::ich::StableHashingContext;
 use rustc::middle::cstore::{DepKind, LinkagePreference, NativeLibrary};
 use rustc::middle::lang_items;
@@ -32,6 +32,8 @@ use std::mem;
 use rustc_data_structures::stable_hasher::{StableHasher, HashStable,
                                            StableHasherResult};
 
+use rustc::dep_graph::{DepGraph, DepNode};
+
 pub fn rustc_version() -> String {
     format!("rustc {}",
             option_env!("CFG_VERSION").unwrap_or("unknown version"))
@@ -186,25 +188,59 @@ pub enum LazyState {
     Previous(usize),
 }
 
+/// A `Tracked<T>` wraps a value so that one can only access it when specifying
+/// the `DepNode` for that value. This makes it harder to forget registering
+/// reads.
+#[derive(RustcEncodable, RustcDecodable)]
+pub struct Tracked<T> {
+    state: T,
+}
+
+impl<T> Tracked<T> {
+    pub fn new(state: T) -> Tracked<T> {
+        Tracked {
+            state: state,
+        }
+    }
+
+    pub fn get(&self, dep_graph: &DepGraph, dep_node: DepNode<DefId>) -> &T {
+        dep_graph.read(dep_node);
+        &self.state
+    }
+
+    pub fn get_untracked(&self) -> &T {
+        &self.state
+    }
+
+    pub fn map<F, R>(&self, f: F) -> Tracked<R>
+        where F: FnOnce(&T) -> R
+    {
+        Tracked {
+            state: f(&self.state),
+        }
+    }
+}
+
+
 #[derive(RustcEncodable, RustcDecodable)]
 pub struct CrateRoot {
     pub name: Symbol,
     pub triple: String,
     pub hash: hir::svh::Svh,
     pub disambiguator: Symbol,
-    pub panic_strategy: PanicStrategy,
+    pub panic_strategy: Tracked<PanicStrategy>,
     pub plugin_registrar_fn: Option<DefIndex>,
     pub macro_derive_registrar: Option<DefIndex>,
 
-    pub crate_deps: LazySeq<CrateDep>,
-    pub dylib_dependency_formats: LazySeq<Option<LinkagePreference>>,
-    pub lang_items: LazySeq<(DefIndex, usize)>,
-    pub lang_items_missing: LazySeq<lang_items::LangItem>,
-    pub native_libraries: LazySeq<NativeLibrary>,
+    pub crate_deps: Tracked<LazySeq<CrateDep>>,
+    pub dylib_dependency_formats: Tracked<LazySeq<Option<LinkagePreference>>>,
+    pub lang_items: Tracked<LazySeq<(DefIndex, usize)>>,
+    pub lang_items_missing: Tracked<LazySeq<lang_items::LangItem>>,
+    pub native_libraries: Tracked<LazySeq<NativeLibrary>>,
     pub codemap: LazySeq<syntax_pos::FileMap>,
     pub def_path_table: Lazy<hir::map::definitions::DefPathTable>,
-    pub impls: LazySeq<TraitImpls>,
-    pub exported_symbols: LazySeq<DefIndex>,
+    pub impls: Tracked<LazySeq<TraitImpls>>,
+    pub exported_symbols: Tracked<LazySeq<DefIndex>>,
     pub index: LazySeq<index::Index>,
 }
 
@@ -215,12 +251,35 @@ pub struct CrateDep {
     pub kind: DepKind,
 }
 
+impl_stable_hash_for!(struct CrateDep {
+    name,
+    hash,
+    kind
+});
+
 #[derive(RustcEncodable, RustcDecodable)]
 pub struct TraitImpls {
     pub trait_id: (u32, DefIndex),
     pub impls: LazySeq<DefIndex>,
 }
 
+impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for TraitImpls {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let TraitImpls {
+            trait_id: (krate, def_index),
+            ref impls,
+        } = *self;
+
+        DefId {
+            krate: CrateNum::from_u32(krate),
+            index: def_index
+        }.hash_stable(hcx, hasher);
+        impls.hash_stable(hcx, hasher);
+    }
+}
+
 #[derive(RustcEncodable, RustcDecodable)]
 pub struct Entry<'tcx> {
     pub kind: EntryKind<'tcx>,
diff --git a/src/librustc_trans/base.rs b/src/librustc_trans/base.rs
index 56ff5ebb069..8689e176f7a 100644
--- a/src/librustc_trans/base.rs
+++ b/src/librustc_trans/base.rs
@@ -754,10 +754,7 @@ fn write_metadata<'a, 'gcx>(tcx: TyCtxt<'a, 'gcx, 'gcx>,
     }).max().unwrap();
 
     if kind == MetadataKind::None {
-        return (metadata_llcx, metadata_llmod, EncodedMetadata {
-            raw_data: vec![],
-            hashes: vec![],
-        });
+        return (metadata_llcx, metadata_llmod, EncodedMetadata::new());
     }
 
     let cstore = &tcx.sess.cstore;
diff --git a/src/libsyntax/codemap.rs b/src/libsyntax/codemap.rs
index 8a88ec3a672..0c8be1d4f24 100644
--- a/src/libsyntax/codemap.rs
+++ b/src/libsyntax/codemap.rs
@@ -21,8 +21,8 @@ pub use syntax_pos::*;
 pub use syntax_pos::hygiene::{ExpnFormat, ExpnInfo, NameAndSpan};
 pub use self::ExpnFormat::*;
 
-use std::cell::RefCell;
-use std::path::{Path,PathBuf};
+use std::cell::{RefCell, Ref};
+use std::path::{Path, PathBuf};
 use std::rc::Rc;
 
 use std::env;
@@ -103,11 +103,18 @@ impl FileLoader for RealFileLoader {
 //
 
 pub struct CodeMap {
-    pub files: RefCell<Vec<Rc<FileMap>>>,
+    // The `files` field should not be visible outside of libsyntax so that we
+    // can do proper dependency tracking.
+    pub(super) files: RefCell<Vec<Rc<FileMap>>>,
     file_loader: Box<FileLoader>,
     // This is used to apply the file path remapping as specified via
     // -Zremap-path-prefix to all FileMaps allocated within this CodeMap.
     path_mapping: FilePathMapping,
+    // The CodeMap will invoke this callback whenever a specific FileMap is
+    // accessed. The callback starts out as a no-op but when the dependency
+    // graph becomes available later during the compilation process, it is
+    // be replaced with something that notifies the dep-tracking system.
+    dep_tracking_callback: RefCell<Box<Fn(&FileMap)>>,
 }
 
 impl CodeMap {
@@ -116,6 +123,7 @@ impl CodeMap {
             files: RefCell::new(Vec::new()),
             file_loader: Box::new(RealFileLoader),
             path_mapping: path_mapping,
+            dep_tracking_callback: RefCell::new(Box::new(|_| {})),
         }
     }
 
@@ -126,6 +134,7 @@ impl CodeMap {
             files: RefCell::new(Vec::new()),
             file_loader: file_loader,
             path_mapping: path_mapping,
+            dep_tracking_callback: RefCell::new(Box::new(|_| {})),
         }
     }
 
@@ -133,6 +142,10 @@ impl CodeMap {
         &self.path_mapping
     }
 
+    pub fn set_dep_tracking_callback(&self, cb: Box<Fn(&FileMap)>) {
+        *self.dep_tracking_callback.borrow_mut() = cb;
+    }
+
     pub fn file_exists(&self, path: &Path) -> bool {
         self.file_loader.file_exists(path)
     }
@@ -142,6 +155,19 @@ impl CodeMap {
         Ok(self.new_filemap(path.to_str().unwrap().to_string(), src))
     }
 
+    pub fn files(&self) -> Ref<Vec<Rc<FileMap>>> {
+        let files = self.files.borrow();
+        for file in files.iter() {
+            (self.dep_tracking_callback.borrow())(file);
+        }
+        files
+    }
+
+    /// Only use this if you do your own dependency tracking!
+    pub fn files_untracked(&self) -> Ref<Vec<Rc<FileMap>>> {
+        self.files.borrow()
+    }
+
     fn next_start_pos(&self) -> usize {
         let files = self.files.borrow();
         match files.last() {
@@ -170,6 +196,7 @@ impl CodeMap {
         let filemap = Rc::new(FileMap {
             name: filename,
             name_was_remapped: was_remapped,
+            crate_of_origin: 0,
             src: Some(Rc::new(src)),
             start_pos: Pos::from_usize(start_pos),
             end_pos: Pos::from_usize(end_pos),
@@ -204,6 +231,7 @@ impl CodeMap {
     pub fn new_imported_filemap(&self,
                                 filename: FileName,
                                 name_was_remapped: bool,
+                                crate_of_origin: u32,
                                 source_len: usize,
                                 mut file_local_lines: Vec<BytePos>,
                                 mut file_local_multibyte_chars: Vec<MultiByteChar>)
@@ -225,6 +253,7 @@ impl CodeMap {
         let filemap = Rc::new(FileMap {
             name: filename,
             name_was_remapped: name_was_remapped,
+            crate_of_origin: crate_of_origin,
             src: None,
             start_pos: start_pos,
             end_pos: end_pos,
@@ -282,6 +311,8 @@ impl CodeMap {
         let files = self.files.borrow();
         let f = (*files)[idx].clone();
 
+        (self.dep_tracking_callback.borrow())(&f);
+
         match f.lookup_line(pos) {
             Some(line) => Ok(FileMapAndLine { fm: f, line: line }),
             None => Err(f)
@@ -471,6 +502,7 @@ impl CodeMap {
     pub fn get_filemap(&self, filename: &str) -> Option<Rc<FileMap>> {
         for fm in self.files.borrow().iter() {
             if filename == fm.name {
+               (self.dep_tracking_callback.borrow())(&fm);
                 return Some(fm.clone());
             }
         }
@@ -481,6 +513,7 @@ impl CodeMap {
     pub fn lookup_byte_offset(&self, bpos: BytePos) -> FileMapAndBytePos {
         let idx = self.lookup_filemap_idx(bpos);
         let fm = (*self.files.borrow())[idx].clone();
+        (self.dep_tracking_callback.borrow())(&fm);
         let offset = bpos - fm.start_pos;
         FileMapAndBytePos {fm: fm, pos: offset}
     }
@@ -491,6 +524,8 @@ impl CodeMap {
         let files = self.files.borrow();
         let map = &(*files)[idx];
 
+        (self.dep_tracking_callback.borrow())(map);
+
         // The number of extra bytes due to multibyte chars in the FileMap
         let mut total_extra_bytes = 0;
 
@@ -536,7 +571,7 @@ impl CodeMap {
     }
 
     pub fn count_lines(&self) -> usize {
-        self.files.borrow().iter().fold(0, |a, f| a + f.count_lines())
+        self.files().iter().fold(0, |a, f| a + f.count_lines())
     }
 }
 
diff --git a/src/libsyntax_pos/lib.rs b/src/libsyntax_pos/lib.rs
index f46b4fcb715..ec56098aa97 100644
--- a/src/libsyntax_pos/lib.rs
+++ b/src/libsyntax_pos/lib.rs
@@ -377,6 +377,8 @@ pub struct FileMap {
     pub name: FileName,
     /// True if the `name` field above has been modified by -Zremap-path-prefix
     pub name_was_remapped: bool,
+    /// Indicates which crate this FileMap was imported from.
+    pub crate_of_origin: u32,
     /// The complete source code
     pub src: Option<Rc<String>>,
     /// The start position of this source in the CodeMap
@@ -491,6 +493,8 @@ impl Decodable for FileMap {
             Ok(FileMap {
                 name: name,
                 name_was_remapped: name_was_remapped,
+                // `crate_of_origin` has to be set by the importer.
+                crate_of_origin: 0xEFFF_FFFF,
                 start_pos: start_pos,
                 end_pos: end_pos,
                 src: None,
diff --git a/src/test/incremental/remapped_paths_cc/auxiliary/extern_crate.rs b/src/test/incremental/remapped_paths_cc/auxiliary/extern_crate.rs
new file mode 100644
index 00000000000..09db90d618b
--- /dev/null
+++ b/src/test/incremental/remapped_paths_cc/auxiliary/extern_crate.rs
@@ -0,0 +1,24 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// ignore-tidy-linelength
+
+// aux-build:extern_crate.rs
+//[rpass1] compile-flags: -g
+//[rpass2] compile-flags: -g
+//[rpass3] compile-flags: -g -Zremap-path-prefix-from={{src-base}} -Zremap-path-prefix-to=/the/src
+
+#![feature(rustc_attrs)]
+#![crate_type="rlib"]
+
+#[inline(always)]
+pub fn inline_fn() {
+    println!("test");
+}
diff --git a/src/test/incremental/remapped_paths_cc/main.rs b/src/test/incremental/remapped_paths_cc/main.rs
new file mode 100644
index 00000000000..8a8c658accc
--- /dev/null
+++ b/src/test/incremental/remapped_paths_cc/main.rs
@@ -0,0 +1,42 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// revisions:rpass1 rpass2 rpass3
+// compile-flags: -Z query-dep-graph -g
+// aux-build:extern_crate.rs
+
+
+// This test case makes sure that we detect if paths emitted into debuginfo
+// are changed, even when the change happens in an external crate.
+
+#![feature(rustc_attrs)]
+
+#![rustc_partition_reused(module="main", cfg="rpass2")]
+#![rustc_partition_reused(module="main-some_mod", cfg="rpass2")]
+#![rustc_partition_reused(module="main", cfg="rpass3")]
+#![rustc_partition_translated(module="main-some_mod", cfg="rpass3")]
+
+extern crate extern_crate;
+
+#[rustc_clean(label="TransCrateItem", cfg="rpass2")]
+#[rustc_clean(label="TransCrateItem", cfg="rpass3")]
+fn main() {
+    some_mod::some_fn();
+}
+
+mod some_mod {
+    use extern_crate;
+
+    #[rustc_clean(label="TransCrateItem", cfg="rpass2")]
+    #[rustc_dirty(label="TransCrateItem", cfg="rpass3")]
+    pub fn some_fn() {
+        extern_crate::inline_fn();
+    }
+}