Auto merge of #31304 - nikomatsakis:incr-comp-read-from-hir-map, r=michaelwoerister

This change also modifies the dep graph infrastructure to keep track of the number of active tasks, so that even if we are not building the full dep-graph, we still get assertions when there is no active task and one does something that would add a read/write edge. This is particularly helpful since, if the assertions are *not* active, you wind up with the error happening in the message processing thread, which is too late to know the correct backtrace.

~~Before landing, I need to do some performance measurements. Those are underway.~~

See measurements below. No real effect on time.

r? @michaelwoerister

26 files changed, 289 insertions, 69 deletions

diff --git a/src/librustc/dep_graph/mod.rs b/src/librustc/dep_graph/mod.rs
index 3bb73ecca2c..faf97f5808e 100644
--- a/src/librustc/dep_graph/mod.rs
+++ b/src/librustc/dep_graph/mod.rs
@@ -40,8 +40,21 @@ pub enum DepNode {
     Hir(DefId),
 
     // Represents different phases in the compiler.
+    CrateReader,
+    CollectLanguageItems,
+    CheckStaticRecursion,
+    ResolveLifetimes,
+    RegionResolveCrate,
+    CheckLoops,
+    PluginRegistrar,
+    StabilityIndex,
     CollectItem(DefId),
     Coherence,
+    EffectCheck,
+    Liveness,
+    Resolve,
+    EntryPoint,
+    CheckEntryFn,
     CoherenceCheckImpl(DefId),
     CoherenceOverlapCheck(DefId),
     CoherenceOverlapCheckSpecial(DefId),
@@ -116,6 +129,13 @@ impl DepGraph {
         }
     }
 
+    /// True if we are actually building a dep-graph. If this returns false,
+    /// then the other methods on this `DepGraph` will have no net effect.
+    #[inline]
+    pub fn enabled(&self) -> bool {
+        self.data.enabled()
+    }
+
     pub fn query(&self) -> DepGraphQuery {
         self.data.query()
     }
diff --git a/src/librustc/dep_graph/thread.rs b/src/librustc/dep_graph/thread.rs
index dbc57605d71..c43b4b15b76 100644
--- a/src/librustc/dep_graph/thread.rs
+++ b/src/librustc/dep_graph/thread.rs
@@ -19,6 +19,7 @@
 //! allocated (and both have a fairly large capacity).
 
 use rustc_data_structures::veccell::VecCell;
+use std::cell::Cell;
 use std::sync::mpsc::{self, Sender, Receiver};
 use std::thread;
 
@@ -39,6 +40,13 @@ pub enum DepMessage {
 pub struct DepGraphThreadData {
     enabled: bool,
 
+    // Local counter that just tracks how many tasks are pushed onto the
+    // stack, so that we still get an error in the case where one is
+    // missing. If dep-graph construction is enabled, we'd get the same
+    // error when processing tasks later on, but that's annoying because
+    // it lacks precision about the source of the error.
+    tasks_pushed: Cell<usize>,
+
     // current buffer, where we accumulate messages
     messages: VecCell<DepMessage>,
 
@@ -59,11 +67,14 @@ impl DepGraphThreadData {
         let (tx1, rx1) = mpsc::channel();
         let (tx2, rx2) = mpsc::channel();
         let (txq, rxq) = mpsc::channel();
+
         if enabled {
             thread::spawn(move || main(rx1, tx2, txq));
         }
+
         DepGraphThreadData {
             enabled: enabled,
+            tasks_pushed: Cell::new(0),
             messages: VecCell::with_capacity(INITIAL_CAPACITY),
             swap_in: rx2,
             swap_out: tx1,
@@ -71,6 +82,11 @@ impl DepGraphThreadData {
         }
     }
 
+    #[inline]
+    pub fn enabled(&self) -> bool {
+        self.enabled
+    }
+
     /// Sends the current batch of messages to the thread. Installs a
     /// new vector of messages.
     fn swap(&self) {
@@ -100,13 +116,40 @@ impl DepGraphThreadData {
     /// the buffer is full, this may swap.)
     #[inline]
     pub fn enqueue(&self, message: DepMessage) {
+        // Regardless of whether dep graph construction is enabled, we
+        // still want to check that we always have a valid task on the
+        // stack when a read/write/etc event occurs.
+        match message {
+            DepMessage::Read(_) | DepMessage::Write(_) =>
+                if self.tasks_pushed.get() == 0 {
+                    self.invalid_message("read/write but no current task")
+                },
+            DepMessage::PushTask(_) | DepMessage::PushIgnore =>
+                self.tasks_pushed.set(self.tasks_pushed.get() + 1),
+            DepMessage::PopTask(_) | DepMessage::PopIgnore =>
+                self.tasks_pushed.set(self.tasks_pushed.get() - 1),
+            DepMessage::Query =>
+                (),
+        }
+
         if self.enabled {
-            let len = self.messages.push(message);
-            if len == INITIAL_CAPACITY {
-                self.swap();
-            }
+            self.enqueue_enabled(message);
         }
     }
+
+    // Outline this fn since I expect it may want to be inlined
+    // separately.
+    fn enqueue_enabled(&self, message: DepMessage) {
+        let len = self.messages.push(message);
+        if len == INITIAL_CAPACITY {
+            self.swap();
+        }
+    }
+
+    // Outline this too.
+    fn invalid_message(&self, string: &str) {
+        panic!("{}; see src/librustc/dep_graph/README.md for more information", string)
+    }
 }
 
 /// Definition of the depgraph thread.
diff --git a/src/librustc/front/map/collector.rs b/src/librustc/front/map/collector.rs
index e85b0ec77cb..8ffc343c8f4 100644
--- a/src/librustc/front/map/collector.rs
+++ b/src/librustc/front/map/collector.rs
@@ -79,6 +79,7 @@ impl<'ast> NodeCollector<'ast> {
 
     fn create_def(&mut self, node_id: NodeId, data: DefPathData) -> DefIndex {
         let parent_def = self.parent_def();
+        debug!("create_def(node_id={:?}, data={:?}, parent_def={:?})", node_id, data, parent_def);
         self.definitions.create_def_with_parent(parent_def, node_id, data)
     }
 
@@ -115,10 +116,13 @@ impl<'ast> Visitor<'ast> for NodeCollector<'ast> {
     /// deep walking so that we walk nested items in the context of
     /// their outer items.
     fn visit_nested_item(&mut self, item: ItemId) {
+        debug!("visit_nested_item: {:?}", item);
         self.visit_item(self.krate.item(item.id))
     }
 
     fn visit_item(&mut self, i: &'ast Item) {
+        debug!("visit_item: {:?}", i);
+
         // Pick the def data. This need not be unique, but the more
         // information we encapsulate into
         let def_data = match i.node {
diff --git a/src/librustc/front/map/mod.rs b/src/librustc/front/map/mod.rs
index 7de60995445..008229aca0b 100644
--- a/src/librustc/front/map/mod.rs
+++ b/src/librustc/front/map/mod.rs
@@ -14,6 +14,8 @@ use self::MapEntry::*;
 use self::collector::NodeCollector;
 pub use self::definitions::{Definitions, DefKey, DefPath, DefPathData, DisambiguatedDefPathData};
 
+use dep_graph::{DepGraph, DepNode};
+
 use middle::cstore::InlinedItem;
 use middle::cstore::InlinedItem as II;
 use middle::def_id::DefId;
@@ -228,19 +230,22 @@ impl<'ast> MapEntry<'ast> {
 
 /// Stores a crate and any number of inlined items from other crates.
 pub struct Forest {
-    pub krate: Crate,
+    krate: Crate,
+    pub dep_graph: DepGraph,
     inlined_items: TypedArena<InlinedParent>
 }
 
 impl Forest {
-    pub fn new(krate: Crate) -> Forest {
+    pub fn new(krate: Crate, dep_graph: DepGraph) -> Forest {
         Forest {
             krate: krate,
+            dep_graph: dep_graph,
             inlined_items: TypedArena::new()
         }
     }
 
     pub fn krate<'ast>(&'ast self) -> &'ast Crate {
+        self.dep_graph.read(DepNode::Krate);
         &self.krate
     }
 }
@@ -252,6 +257,10 @@ pub struct Map<'ast> {
     /// The backing storage for all the AST nodes.
     pub forest: &'ast Forest,
 
+    /// Same as the dep_graph in forest, just available with one fewer
+    /// deref. This is a gratuitious micro-optimization.
+    pub dep_graph: DepGraph,
+
     /// NodeIds are sequential integers from 0, so we can be
     /// super-compact by storing them in a vector. Not everything with
     /// a NodeId is in the map, but empirically the occupancy is about
@@ -267,6 +276,60 @@ pub struct Map<'ast> {
 }
 
 impl<'ast> Map<'ast> {
+    /// Registers a read in the dependency graph of the AST node with
+    /// the given `id`. This needs to be called each time a public
+    /// function returns the HIR for a node -- in other words, when it
+    /// "reveals" the content of a node to the caller (who might not
+    /// otherwise have had access to those contents, and hence needs a
+    /// read recorded). If the function just returns a DefId or
+    /// NodeId, no actual content was returned, so no read is needed.
+    fn read(&self, id: NodeId) {
+        self.dep_graph.read(self.dep_node(id));
+    }
+
+    fn dep_node(&self, id0: NodeId) -> DepNode {
+        let map = self.map.borrow();
+        let mut id = id0;
+        loop {
+            match map[id as usize] {
+                EntryItem(_, item) => {
+                    let def_id = self.local_def_id(item.id);
+                    // NB                          ^~~~~~~
+                    //
+                    // You would expect that `item.id == id`, but this
+                    // is not always the case. In particular, for a
+                    // ViewPath item like `use self::{mem, foo}`, we
+                    // map the ids for `mem` and `foo` to the
+                    // enclosing view path item. This seems mega super
+                    // ultra wrong, but then who am I to judge?
+                    // -nmatsakis
+                    return DepNode::Hir(def_id);
+                }
+
+                EntryForeignItem(p, _) |
+                EntryTraitItem(p, _) |
+                EntryImplItem(p, _) |
+                EntryVariant(p, _) |
+                EntryExpr(p, _) |
+                EntryStmt(p, _) |
+                EntryLocal(p, _) |
+                EntryPat(p, _) |
+                EntryBlock(p, _) |
+                EntryStructCtor(p, _) |
+                EntryLifetime(p, _) |
+                EntryTyParam(p, _) =>
+                    id = p,
+
+                RootCrate |
+                RootInlinedParent(_) => // FIXME(#2369) clarify story about cross-crate dep tracking
+                    return DepNode::Krate,
+
+                NotPresent =>
+                    panic!("Walking parents from `{}` led to `NotPresent` at `{}`", id0, id),
+            }
+        }
+    }
+
     pub fn num_local_def_ids(&self) -> usize {
         self.definitions.borrow().len()
     }
@@ -309,26 +372,30 @@ impl<'ast> Map<'ast> {
     }
 
     pub fn krate(&self) -> &'ast Crate {
-        &self.forest.krate
+        self.forest.krate()
     }
 
     /// Retrieve the Node corresponding to `id`, panicking if it cannot
     /// be found.
     pub fn get(&self, id: NodeId) -> Node<'ast> {
         match self.find(id) {
-            Some(node) => node,
+            Some(node) => node, // read recorded by `find`
             None => panic!("couldn't find node id {} in the AST map", id)
         }
     }
 
     pub fn get_if_local(&self, id: DefId) -> Option<Node<'ast>> {
-        self.as_local_node_id(id).map(|id| self.get(id))
+        self.as_local_node_id(id).map(|id| self.get(id)) // read recorded by `get`
     }
 
     /// Retrieve the Node corresponding to `id`, returning None if
     /// cannot be found.
     pub fn find(&self, id: NodeId) -> Option<Node<'ast>> {
-        self.find_entry(id).and_then(|x| x.to_node())
+        let result = self.find_entry(id).and_then(|x| x.to_node());
+        if result.is_some() {
+            self.read(id);
+        }
+        result
     }
 
     /// Similar to get_parent, returns the parent node id or id if there is no
@@ -459,22 +526,25 @@ impl<'ast> Map<'ast> {
             _ => None
         };
         match abi {
-            Some(abi) => abi,
+            Some(abi) => {
+                self.read(id); // reveals some of the content of a node
+                abi
+            }
             None => panic!("expected foreign mod or inlined parent, found {}",
                           self.node_to_string(parent))
         }
     }
 
     pub fn get_foreign_vis(&self, id: NodeId) -> Visibility {
-        let vis = self.expect_foreign_item(id).vis;
-        match self.find(self.get_parent(id)) {
+        let vis = self.expect_foreign_item(id).vis; // read recorded by `expect_foreign_item`
+        match self.find(self.get_parent(id)) { // read recorded by `find`
             Some(NodeItem(i)) => vis.inherit_from(i.vis),
             _ => vis
         }
     }
 
     pub fn expect_item(&self, id: NodeId) -> &'ast Item {
-        match self.find(id) {
+        match self.find(id) { // read recorded by `find`
             Some(NodeItem(item)) => item,
             _ => panic!("expected item, found {}", self.node_to_string(id))
         }
@@ -521,7 +591,7 @@ impl<'ast> Map<'ast> {
     }
 
     pub fn expect_expr(&self, id: NodeId) -> &'ast Expr {
-        match self.find(id) {
+        match self.find(id) { // read recorded by find
             Some(NodeExpr(expr)) => expr,
             _ => panic!("expected expr, found {}", self.node_to_string(id))
         }
@@ -571,6 +641,11 @@ impl<'ast> Map<'ast> {
     fn with_path_next<T, F>(&self, id: NodeId, next: LinkedPath, f: F) -> T where
         F: FnOnce(PathElems) -> T,
     {
+        // This function reveals the name of the item and hence is a
+        // kind of read. This is inefficient, since it walks ancestors
+        // and we are walking them anyhow, but whatever.
+        self.read(id);
+
         let parent = self.get_parent(id);
         let parent = match self.find_entry(id) {
             Some(EntryForeignItem(..)) => {
@@ -602,6 +677,7 @@ impl<'ast> Map<'ast> {
     /// Given a node ID, get a list of attributes associated with the AST
     /// corresponding to the Node ID
     pub fn attrs(&self, id: NodeId) -> &'ast [ast::Attribute] {
+        self.read(id); // reveals attributes on the node
         let attrs = match self.find(id) {
             Some(NodeItem(i)) => Some(&i.attrs[..]),
             Some(NodeForeignItem(fi)) => Some(&fi.attrs[..]),
@@ -655,6 +731,7 @@ impl<'ast> Map<'ast> {
     }
 
     pub fn span(&self, id: NodeId) -> Span {
+        self.read(id); // reveals span from node
         self.opt_span(id)
             .unwrap_or_else(|| panic!("AstMap.span: could not find span for id {:?}", id))
     }
@@ -833,6 +910,7 @@ pub fn map_crate<'ast>(forest: &'ast mut Forest) -> Map<'ast> {
 
     Map {
         forest: forest,
+        dep_graph: forest.dep_graph.clone(),
         map: RefCell::new(map),
         definitions: RefCell::new(definitions),
     }
diff --git a/src/librustc/middle/effect.rs b/src/librustc/middle/effect.rs
index 055beac5428..c27d029374a 100644
--- a/src/librustc/middle/effect.rs
+++ b/src/librustc/middle/effect.rs
@@ -12,6 +12,7 @@
 //! `unsafe`.
 use self::RootUnsafeContext::*;
 
+use dep_graph::DepNode;
 use middle::def::Def;
 use middle::ty::{self, Ty};
 use middle::ty::MethodCall;
@@ -182,6 +183,8 @@ impl<'a, 'tcx, 'v> Visitor<'v> for EffectCheckVisitor<'a, 'tcx> {
 }
 
 pub fn check_crate(tcx: &ty::ctxt) {
+    let _task = tcx.dep_graph.in_task(DepNode::EffectCheck);
+
     let mut visitor = EffectCheckVisitor {
         tcx: tcx,
         unsafe_context: UnsafeContext::new(SafeContext),
diff --git a/src/librustc/middle/entry.rs b/src/librustc/middle/entry.rs
index 2d096f66e09..67e96816abf 100644
--- a/src/librustc/middle/entry.rs
+++ b/src/librustc/middle/entry.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 
+use dep_graph::DepNode;
 use front::map as ast_map;
 use middle::def_id::{CRATE_DEF_INDEX};
 use session::{config, Session};
@@ -48,6 +49,8 @@ impl<'a, 'tcx> Visitor<'tcx> for EntryContext<'a, 'tcx> {
 }
 
 pub fn find_entry_point(session: &Session, ast_map: &ast_map::Map) {
+    let _task = ast_map.dep_graph.in_task(DepNode::EntryPoint);
+
     let any_exe = session.crate_types.borrow().iter().any(|ty| {
         *ty == config::CrateTypeExecutable
     });
diff --git a/src/librustc/middle/lang_items.rs b/src/librustc/middle/lang_items.rs
index 6e57d5dd1ba..f77ca10e88f 100644
--- a/src/librustc/middle/lang_items.rs
+++ b/src/librustc/middle/lang_items.rs
@@ -21,6 +21,7 @@
 
 pub use self::LangItem::*;
 
+use dep_graph::DepNode;
 use front::map as hir_map;
 use session::Session;
 use middle::cstore::CrateStore;
@@ -234,6 +235,7 @@ pub fn extract(attrs: &[ast::Attribute]) -> Option<InternedString> {
 pub fn collect_language_items(session: &Session,
                               map: &hir_map::Map)
                               -> LanguageItems {
+    let _task = map.dep_graph.in_task(DepNode::CollectLanguageItems);
     let krate: &hir::Crate = map.krate();
     let mut collector = LanguageItemCollector::new(session, map);
     collector.collect(krate);
diff --git a/src/librustc/middle/liveness.rs b/src/librustc/middle/liveness.rs
index 90fa148e008..5fa9d459345 100644
--- a/src/librustc/middle/liveness.rs
+++ b/src/librustc/middle/liveness.rs
@@ -109,6 +109,7 @@ use self::LoopKind::*;
 use self::LiveNodeKind::*;
 use self::VarKind::*;
 
+use dep_graph::DepNode;
 use middle::def::*;
 use middle::pat_util;
 use middle::ty;
@@ -192,6 +193,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for IrMaps<'a, 'tcx> {
 }
 
 pub fn check_crate(tcx: &ty::ctxt) {
+    let _task = tcx.dep_graph.in_task(DepNode::Liveness);
     tcx.map.krate().visit_all_items(&mut IrMaps::new(tcx));
     tcx.sess.abort_if_errors();
 }
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index 1361fac5b16..bf21b607b77 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -16,6 +16,7 @@
 //! Most of the documentation on regions can be found in
 //! `middle/infer/region_inference/README.md`
 
+use dep_graph::DepNode;
 use front::map as ast_map;
 use session::Session;
 use util::nodemap::{FnvHashMap, NodeMap, NodeSet};
@@ -1224,7 +1225,10 @@ impl<'a, 'v> Visitor<'v> for RegionResolutionVisitor<'a> {
     }
 }
 
-pub fn resolve_crate(sess: &Session, krate: &hir::Crate) -> RegionMaps {
+pub fn resolve_crate(sess: &Session, map: &ast_map::Map) -> RegionMaps {
+    let _task = map.dep_graph.in_task(DepNode::RegionResolveCrate);
+    let krate = map.krate();
+
     let maps = RegionMaps {
         code_extents: RefCell::new(vec![]),
         code_extent_interner: RefCell::new(FnvHashMap()),
diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index 48955bd9a15..4bdf716e637 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -18,6 +18,8 @@
 pub use self::DefRegion::*;
 use self::ScopeChain::*;
 
+use dep_graph::DepNode;
+use front::map::Map;
 use session::Session;
 use middle::def::{Def, DefMap};
 use middle::region;
@@ -94,9 +96,11 @@ type Scope<'a> = &'a ScopeChain<'a>;
 static ROOT_SCOPE: ScopeChain<'static> = RootScope;
 
 pub fn krate(sess: &Session,
-             krate: &hir::Crate,
+             hir_map: &Map,
              def_map: &DefMap)
              -> Result<NamedRegionMap, usize> {
+    let _task = hir_map.dep_graph.in_task(DepNode::ResolveLifetimes);
+    let krate = hir_map.krate();
     let mut named_region_map = NodeMap();
     try!(sess.track_errors(|| {
         krate.visit_all_items(&mut LifetimeContext {
diff --git a/src/librustc/middle/stability.rs b/src/librustc/middle/stability.rs
index e0d38f1c76f..7835f333f19 100644
--- a/src/librustc/middle/stability.rs
+++ b/src/librustc/middle/stability.rs
@@ -14,6 +14,7 @@
 pub use self::StabilityLevel::*;
 
 use dep_graph::DepNode;
+use front::map as hir_map;
 use session::Session;
 use lint;
 use middle::cstore::{CrateStore, LOCAL_CRATE};
@@ -30,7 +31,7 @@ use syntax::attr::{self, Stability, Deprecation, AttrMetaMethods};
 use util::nodemap::{DefIdMap, FnvHashSet, FnvHashMap};
 
 use rustc_front::hir;
-use rustc_front::hir::{Crate, Item, Generics, StructField, Variant};
+use rustc_front::hir::{Item, Generics, StructField, Variant};
 use rustc_front::intravisit::{self, Visitor};
 
 use std::mem::replace;
@@ -278,7 +279,9 @@ impl<'a, 'tcx, 'v> Visitor<'v> for Annotator<'a, 'tcx> {
 
 impl<'tcx> Index<'tcx> {
     /// Construct the stability index for a crate being compiled.
-    pub fn build(&mut self, tcx: &ty::ctxt<'tcx>, krate: &Crate, access_levels: &AccessLevels) {
+    pub fn build(&mut self, tcx: &ty::ctxt<'tcx>, access_levels: &AccessLevels) {
+        let _task = tcx.dep_graph.in_task(DepNode::StabilityIndex);
+        let krate = tcx.map.krate();
         let mut annotator = Annotator {
             tcx: tcx,
             index: self,
@@ -291,7 +294,10 @@ impl<'tcx> Index<'tcx> {
                            |v| intravisit::walk_crate(v, krate));
     }
 
-    pub fn new(krate: &Crate) -> Index<'tcx> {
+    pub fn new(hir_map: &hir_map::Map) -> Index<'tcx> {
+        let _task = hir_map.dep_graph.in_task(DepNode::StabilityIndex);
+        let krate = hir_map.krate();
+
         let mut is_staged_api = false;
         for attr in &krate.attrs {
             if attr.name() == "stable" || attr.name() == "unstable" {
diff --git a/src/librustc/middle/ty/context.rs b/src/librustc/middle/ty/context.rs
index 0fd6b933ed5..071cc0cbe3d 100644
--- a/src/librustc/middle/ty/context.rs
+++ b/src/librustc/middle/ty/context.rs
@@ -509,7 +509,7 @@ impl<'tcx> ctxt<'tcx> {
     {
         let interner = RefCell::new(FnvHashMap());
         let common_types = CommonTypes::new(&arenas.type_, &interner);
-        let dep_graph = DepGraph::new(s.opts.incremental_compilation);
+        let dep_graph = map.dep_graph.clone();
         let fulfilled_predicates = traits::GlobalFulfilledPredicates::new(dep_graph.clone());
         tls::enter(ctxt {
             arenas: arenas,
diff --git a/src/librustc/session/config.rs b/src/librustc/session/config.rs
index de128d839d9..68949863bfc 100644
--- a/src/librustc/session/config.rs
+++ b/src/librustc/session/config.rs
@@ -137,8 +137,13 @@ pub struct Options {
     pub no_trans: bool,
     pub error_format: ErrorOutputType,
     pub treat_err_as_bug: bool,
-    pub incremental_compilation: bool,
+
+    /// if true, build up the dep-graph
+    pub build_dep_graph: bool,
+
+    /// if true, -Z dump-dep-graph was passed to dump out the dep-graph
     pub dump_dep_graph: bool,
+
     pub no_analysis: bool,
     pub debugging_opts: DebuggingOptions,
     pub prints: Vec<PrintRequest>,
@@ -246,7 +251,7 @@ pub fn basic_options() -> Options {
         parse_only: false,
         no_trans: false,
         treat_err_as_bug: false,
-        incremental_compilation: false,
+        build_dep_graph: false,
         dump_dep_graph: false,
         no_analysis: false,
         debugging_opts: basic_debugging_options(),
@@ -1145,7 +1150,7 @@ pub fn build_session_options(matches: &getopts::Matches) -> Options {
         parse_only: parse_only,
         no_trans: no_trans,
         treat_err_as_bug: treat_err_as_bug,
-        incremental_compilation: incremental_compilation || dump_dep_graph,
+        build_dep_graph: incremental_compilation || dump_dep_graph,
         dump_dep_graph: dump_dep_graph,
         no_analysis: no_analysis,
         debugging_opts: debugging_opts,
diff --git a/src/librustc_driver/driver.rs b/src/librustc_driver/driver.rs
index c189df18a82..e5066399323 100644
--- a/src/librustc_driver/driver.rs
+++ b/src/librustc_driver/driver.rs
@@ -8,6 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use rustc::dep_graph::DepGraph;
 use rustc::front;
 use rustc::front::map as hir_map;
 use rustc_mir as mir;
@@ -115,9 +116,11 @@ pub fn compile_input(sess: &Session,
         let expanded_crate = assign_node_ids(sess, expanded_crate);
         // Lower ast -> hir.
         let lcx = LoweringContext::new(sess, Some(&expanded_crate));
+        let dep_graph = DepGraph::new(sess.opts.build_dep_graph);
         let mut hir_forest = time(sess.time_passes(),
                                   "lowering ast -> hir",
-                                  || hir_map::Forest::new(lower_crate(&lcx, &expanded_crate)));
+                                  || hir_map::Forest::new(lower_crate(&lcx, &expanded_crate),
+                                                          dep_graph));
 
         // Discard MTWT tables that aren't required past lowering to HIR.
         if !sess.opts.debugging_opts.keep_mtwt_tables &&
@@ -130,17 +133,20 @@ pub fn compile_input(sess: &Session,
 
         write_out_deps(sess, &outputs, &id);
 
-        controller_entry_point!(after_write_deps,
-                                sess,
-                                CompileState::state_after_write_deps(input,
-                                                                     sess,
-                                                                     outdir,
-                                                                     &hir_map,
-                                                                     &expanded_crate,
-                                                                     &hir_map.krate(),
-                                                                     &id[..],
-                                                                     &lcx),
-                                Ok(()));
+        {
+            let _ignore = hir_map.dep_graph.in_ignore();
+            controller_entry_point!(after_write_deps,
+                                    sess,
+                                    CompileState::state_after_write_deps(input,
+                                                                         sess,
+                                                                         outdir,
+                                                                         &hir_map,
+                                                                         &expanded_crate,
+                                                                         &hir_map.krate(),
+                                                                         &id[..],
+                                                                         &lcx),
+                                    Ok(()));
+        }
 
         time(sess.time_passes(), "attribute checking", || {
             front::check_attr::check_crate(sess, &expanded_crate);
@@ -166,6 +172,9 @@ pub fn compile_input(sess: &Session,
                                               control.make_glob_map,
                                               |tcx, mir_map, analysis, result| {
             {
+                // Eventually, we will want to track plugins.
+                let _ignore = tcx.dep_graph.in_ignore();
+
                 let state = CompileState::state_after_analysis(input,
                                                                &tcx.sess,
                                                                outdir,
@@ -735,11 +744,10 @@ pub fn phase_3_run_analysis_passes<'tcx, F, R>(sess: &'tcx Session,
     }
 
     let time_passes = sess.time_passes();
-    let krate = hir_map.krate();
 
     time(time_passes,
          "external crate/lib resolution",
-         || LocalCrateReader::new(sess, cstore, &hir_map).read_crates(krate));
+         || LocalCrateReader::new(sess, cstore, &hir_map).read_crates());
 
     let lang_items = try!(time(time_passes, "language item collection", || {
         sess.track_errors(|| {
@@ -769,7 +777,7 @@ pub fn phase_3_run_analysis_passes<'tcx, F, R>(sess: &'tcx Session,
     let named_region_map = try!(time(time_passes,
                                      "lifetime resolution",
                                      || middle::resolve_lifetime::krate(sess,
-                                                                        krate,
+                                                                        &hir_map,
                                                                         &def_map.borrow())));
 
     time(time_passes,
@@ -777,20 +785,22 @@ pub fn phase_3_run_analysis_passes<'tcx, F, R>(sess: &'tcx Session,
          || middle::entry::find_entry_point(sess, &hir_map));
 
     sess.plugin_registrar_fn.set(time(time_passes, "looking for plugin registrar", || {
-        plugin::build::find_plugin_registrar(sess.diagnostic(), krate)
+        plugin::build::find_plugin_registrar(sess.diagnostic(), &hir_map)
     }));
 
     let region_map = time(time_passes,
                           "region resolution",
-                          || middle::region::resolve_crate(sess, krate));
+                          || middle::region::resolve_crate(sess, &hir_map));
 
     time(time_passes,
          "loop checking",
-         || loops::check_crate(sess, krate));
+         || loops::check_crate(sess, &hir_map));
 
     try!(time(time_passes,
               "static item recursion checking",
-              || static_recursion::check_crate(sess, krate, &def_map.borrow(), &hir_map)));
+              || static_recursion::check_crate(sess, &def_map.borrow(), &hir_map)));
+
+    let index = stability::Index::new(&hir_map);
 
     ty::ctxt::create_and_enter(sess,
                                arenas,
@@ -800,7 +810,7 @@ pub fn phase_3_run_analysis_passes<'tcx, F, R>(sess: &'tcx Session,
                                freevars,
                                region_map,
                                lang_items,
-                               stability::Index::new(krate),
+                               index,
                                |tcx| {
         // passes are timed inside typeck
         try_with_f!(typeck::check_crate(tcx, trait_map), (tcx, None, analysis));
@@ -818,7 +828,7 @@ pub fn phase_3_run_analysis_passes<'tcx, F, R>(sess: &'tcx Session,
 
         // Do not move this check past lint
         time(time_passes, "stability index", || {
-            tcx.stability.borrow_mut().build(tcx, krate, &analysis.access_levels)
+            tcx.stability.borrow_mut().build(tcx, &analysis.access_levels)
         });
 
         time(time_passes,
diff --git a/src/librustc_driver/pretty.rs b/src/librustc_driver/pretty.rs
index 91af78a5bd4..58043f385fe 100644
--- a/src/librustc_driver/pretty.rs
+++ b/src/librustc_driver/pretty.rs
@@ -19,6 +19,7 @@ use rustc_trans::back::link;
 
 use {driver, abort_on_err};
 
+use rustc::dep_graph::DepGraph;
 use rustc::middle::ty;
 use rustc::middle::cfg;
 use rustc::middle::cfg::graphviz::LabelledCFG;
@@ -183,7 +184,7 @@ impl PpSourceMode {
                     sess: sess,
                     ast_map: Some(ast_map.clone()),
                 };
-                f(&annotation, payload, &ast_map.forest.krate)
+                f(&annotation, payload, ast_map.forest.krate())
             }
 
             PpmIdentified => {
@@ -191,7 +192,7 @@ impl PpSourceMode {
                     sess: sess,
                     ast_map: Some(ast_map.clone()),
                 };
-                f(&annotation, payload, &ast_map.forest.krate)
+                f(&annotation, payload, ast_map.forest.krate())
             }
             PpmTyped => {
                 abort_on_err(driver::phase_3_run_analysis_passes(sess,
@@ -207,7 +208,7 @@ impl PpSourceMode {
                     let _ignore = tcx.dep_graph.in_ignore();
                     f(&annotation,
                       payload,
-                      &ast_map.forest.krate)
+                      ast_map.forest.krate())
                 }), sess)
             }
             _ => panic!("Should use call_with_pp_support"),
@@ -706,8 +707,10 @@ pub fn pretty_print_input(sess: Session,
     let mut hir_forest;
     let lcx = LoweringContext::new(&sess, Some(&krate));
     let arenas = ty::CtxtArenas::new();
+    let dep_graph = DepGraph::new(false);
+    let _ignore = dep_graph.in_ignore();
     let ast_map = if compute_ast_map {
-        hir_forest = hir_map::Forest::new(lower_crate(&lcx, &krate));
+        hir_forest = hir_map::Forest::new(lower_crate(&lcx, &krate), dep_graph.clone());
         let map = driver::make_map(&sess, &mut hir_forest);
         Some(map)
     } else {
diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index 3389992ebb8..3736e045bd1 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -11,6 +11,7 @@
 //! # Standalone Tests for the Inference Module
 
 use driver;
+use rustc::dep_graph::DepGraph;
 use rustc_lint;
 use rustc_resolve as resolve;
 use rustc_typeck::middle::lang_items;
@@ -118,17 +119,19 @@ fn test_env<F>(source_string: &str,
 
     let krate = driver::assign_node_ids(&sess, krate);
     let lcx = LoweringContext::new(&sess, Some(&krate));
-    let mut hir_forest = hir_map::Forest::new(lower_crate(&lcx, &krate));
+    let dep_graph = DepGraph::new(false);
+    let _ignore = dep_graph.in_ignore();
+    let mut hir_forest = hir_map::Forest::new(lower_crate(&lcx, &krate), dep_graph.clone());
     let arenas = ty::CtxtArenas::new();
     let ast_map = driver::make_map(&sess, &mut hir_forest);
-    let krate = ast_map.krate();
 
     // run just enough stuff to build a tcx:
     let lang_items = lang_items::collect_language_items(&sess, &ast_map);
     let resolve::CrateMap { def_map, freevars, .. } =
         resolve::resolve_crate(&sess, &ast_map, resolve::MakeGlobMap::No);
-    let named_region_map = resolve_lifetime::krate(&sess, krate, &def_map.borrow());
-    let region_map = region::resolve_crate(&sess, krate);
+    let named_region_map = resolve_lifetime::krate(&sess, &ast_map, &def_map.borrow());
+    let region_map = region::resolve_crate(&sess, &ast_map);
+    let index = stability::Index::new(&ast_map);
     ty::ctxt::create_and_enter(&sess,
                                &arenas,
                                def_map,
@@ -137,7 +140,7 @@ fn test_env<F>(source_string: &str,
                                freevars,
                                region_map,
                                lang_items,
-                               stability::Index::new(krate),
+                               index,
                                |tcx| {
                                    let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None);
                                    body(Env { infcx: &infcx });
diff --git a/src/librustc_metadata/creader.rs b/src/librustc_metadata/creader.rs
index b569739c40c..7b094a5900a 100644
--- a/src/librustc_metadata/creader.rs
+++ b/src/librustc_metadata/creader.rs
@@ -18,6 +18,7 @@ use decoder;
 use loader::{self, CratePaths};
 
 use rustc::back::svh::Svh;
+use rustc::dep_graph::DepNode;
 use rustc::session::{config, Session};
 use rustc::session::search_paths::PathKind;
 use rustc::middle::cstore::{CrateStore, validate_crate_name};
@@ -723,7 +724,10 @@ impl<'a, 'b> LocalCrateReader<'a, 'b> {
     // Traverses an AST, reading all the information about use'd crates and
     // extern libraries necessary for later resolving, typechecking, linking,
     // etc.
-    pub fn read_crates(&mut self, krate: &hir::Crate) {
+    pub fn read_crates(&mut self) {
+        let _task = self.ast_map.dep_graph.in_task(DepNode::CrateReader);
+        let krate = self.ast_map.krate();
+
         self.process_crate(krate);
         krate.visit_all_items(self);
         self.creader.inject_allocator_crate();
diff --git a/src/librustc_passes/loops.rs b/src/librustc_passes/loops.rs
index eb2e445f9b0..bce18d3fe6e 100644
--- a/src/librustc_passes/loops.rs
+++ b/src/librustc_passes/loops.rs
@@ -11,9 +11,11 @@ use self::Context::*;
 
 use rustc::session::Session;
 
-use syntax::codemap::Span;
+use rustc::dep_graph::DepNode;
+use rustc::front::map::Map;
 use rustc_front::intravisit::{self, Visitor};
 use rustc_front::hir;
+use syntax::codemap::Span;
 
 #[derive(Clone, Copy, PartialEq)]
 enum Context {
@@ -26,7 +28,9 @@ struct CheckLoopVisitor<'a> {
     cx: Context
 }
 
-pub fn check_crate(sess: &Session, krate: &hir::Crate) {
+pub fn check_crate(sess: &Session, map: &Map) {
+    let _task = map.dep_graph.in_task(DepNode::CheckLoops);
+    let krate = map.krate();
     krate.visit_all_items(&mut CheckLoopVisitor { sess: sess, cx: Normal });
 }
 
diff --git a/src/librustc_passes/static_recursion.rs b/src/librustc_passes/static_recursion.rs
index 2d81354495d..329ce21edbe 100644
--- a/src/librustc_passes/static_recursion.rs
+++ b/src/librustc_passes/static_recursion.rs
@@ -11,6 +11,7 @@
 // This compiler pass detects constants that refer to themselves
 // recursively.
 
+use rustc::dep_graph::DepNode;
 use rustc::front::map as ast_map;
 use rustc::session::{Session, CompileResult};
 use rustc::middle::def::{Def, DefMap};
@@ -90,9 +91,11 @@ impl<'a, 'ast: 'a> Visitor<'ast> for CheckCrateVisitor<'a, 'ast> {
 }
 
 pub fn check_crate<'ast>(sess: &Session,
-                         krate: &'ast hir::Crate,
                          def_map: &DefMap,
-                         ast_map: &ast_map::Map<'ast>) -> CompileResult {
+                         ast_map: &ast_map::Map<'ast>)
+                         -> CompileResult {
+    let _task = ast_map.dep_graph.in_task(DepNode::CheckStaticRecursion);
+
     let mut visitor = CheckCrateVisitor {
         sess: sess,
         def_map: def_map,
@@ -100,7 +103,7 @@ pub fn check_crate<'ast>(sess: &Session,
         discriminant_map: RefCell::new(NodeMap()),
     };
     sess.track_errors(|| {
-        krate.visit_all_items(&mut visitor);
+        ast_map.krate().visit_all_items(&mut visitor);
     })
 }
 
diff --git a/src/librustc_plugin/build.rs b/src/librustc_plugin/build.rs
index 5adde4304f5..fe83b609334 100644
--- a/src/librustc_plugin/build.rs
+++ b/src/librustc_plugin/build.rs
@@ -14,6 +14,8 @@ use syntax::ast;
 use syntax::attr;
 use syntax::codemap::Span;
 use syntax::errors;
+use rustc::dep_graph::DepNode;
+use rustc::front::map::Map;
 use rustc_front::intravisit::Visitor;
 use rustc_front::hir;
 
@@ -34,8 +36,11 @@ impl<'v> Visitor<'v> for RegistrarFinder {
 
 /// Find the function marked with `#[plugin_registrar]`, if any.
 pub fn find_plugin_registrar(diagnostic: &errors::Handler,
-                             krate: &hir::Crate)
+                             hir_map: &Map)
                              -> Option<ast::NodeId> {
+    let _task = hir_map.dep_graph.in_task(DepNode::PluginRegistrar);
+    let krate = hir_map.krate();
+
     let mut finder = RegistrarFinder { registrars: Vec::new() };
     krate.visit_all_items(&mut finder);
 
diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index 64973bd7916..054aa1d5f55 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -47,6 +47,7 @@ use self::BareIdentifierPatternResolution::*;
 use self::ParentLink::*;
 use self::FallbackChecks::*;
 
+use rustc::dep_graph::DepNode;
 use rustc::front::map as hir_map;
 use rustc::session::Session;
 use rustc::lint;
@@ -3596,6 +3597,15 @@ pub fn resolve_crate<'a, 'tcx>(session: &'a Session,
                                ast_map: &'a hir_map::Map<'tcx>,
                                make_glob_map: MakeGlobMap)
                                -> CrateMap {
+    // Currently, we ignore the name resolution data structures for
+    // the purposes of dependency tracking. Instead we will run name
+    // resolution and include its output in the hash of each item,
+    // much like we do for macro expansion. In other words, the hash
+    // reflects not just its contents but the results of name
+    // resolution on those contents. Hopefully we'll push this back at
+    // some point.
+    let _task = ast_map.dep_graph.in_task(DepNode::Resolve);
+
     let krate = ast_map.krate();
     let arenas = Resolver::arenas();
     let mut resolver = create_resolver(session, ast_map, krate, make_glob_map, &arenas, None);
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index db4f8d3a70c..035be02b0c3 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -99,9 +99,8 @@ use rustc_front::print::pprust;
 
 pub fn collect_item_types(tcx: &ty::ctxt) {
     let ccx = &CrateCtxt { tcx: tcx, stack: RefCell::new(Vec::new()) };
-
     let mut visitor = CollectItemTypesVisitor{ ccx: ccx };
-    ccx.tcx.map.krate().visit_all_items(&mut visitor);
+    ccx.tcx.visit_all_items_in_krate(DepNode::CollectItem, &mut visitor);
 }
 
 ///////////////////////////////////////////////////////////////////////////
@@ -146,9 +145,6 @@ struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
 
 impl<'a, 'tcx, 'v> intravisit::Visitor<'v> for CollectItemTypesVisitor<'a, 'tcx> {
     fn visit_item(&mut self, item: &hir::Item) {
-        let tcx = self.ccx.tcx;
-        let item_def_id = tcx.map.local_def_id(item.id);
-        let _task = tcx.dep_graph.in_task(DepNode::CollectItem(item_def_id));
         convert_item(self.ccx, item);
     }
 }
diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs
index cb0b4d0902c..083eeff9f90 100644
--- a/src/librustc_typeck/lib.rs
+++ b/src/librustc_typeck/lib.rs
@@ -100,6 +100,7 @@ pub use rustc::middle;
 pub use rustc::session;
 pub use rustc::util;
 
+use dep_graph::DepNode;
 use front::map as hir_map;
 use middle::def::Def;
 use middle::infer::{self, TypeOrigin};
@@ -312,6 +313,7 @@ fn check_start_fn_ty(ccx: &CrateCtxt,
 
 fn check_for_entry_fn(ccx: &CrateCtxt) {
     let tcx = ccx.tcx;
+    let _task = tcx.dep_graph.in_task(DepNode::CheckEntryFn);
     match *tcx.sess.entry_fn.borrow() {
         Some((id, sp)) => match tcx.sess.entry_type.get() {
             Some(config::EntryMain) => check_main_fn_ty(ccx, id, sp),
diff --git a/src/librustdoc/core.rs b/src/librustdoc/core.rs
index 3e8457069d2..f0bd4dd83cb 100644
--- a/src/librustdoc/core.rs
+++ b/src/librustdoc/core.rs
@@ -11,6 +11,7 @@ pub use self::MaybeTyped::*;
 
 use rustc_lint;
 use rustc_driver::{driver, target_features, abort_on_err};
+use rustc::dep_graph::DepGraph;
 use rustc::session::{self, config};
 use rustc::middle::def_id::DefId;
 use rustc::middle::privacy::AccessLevels;
@@ -143,7 +144,7 @@ pub fn run_core(search_paths: SearchPaths, cfgs: Vec<String>, externs: Externs,
     let krate = driver::assign_node_ids(&sess, krate);
     // Lower ast -> hir.
     let lcx = LoweringContext::new(&sess, Some(&krate));
-    let mut hir_forest = hir_map::Forest::new(lower_crate(&lcx, &krate));
+    let mut hir_forest = hir_map::Forest::new(lower_crate(&lcx, &krate), DepGraph::new(false));
     let arenas = ty::CtxtArenas::new();
     let hir_map = driver::make_map(&sess, &mut hir_forest);
 
diff --git a/src/librustdoc/test.rs b/src/librustdoc/test.rs
index 81f984a5927..490e54f4e3d 100644
--- a/src/librustdoc/test.rs
+++ b/src/librustdoc/test.rs
@@ -25,6 +25,7 @@ use std::sync::{Arc, Mutex};
 
 use testing;
 use rustc_lint;
+use rustc::dep_graph::DepGraph;
 use rustc::front::map as hir_map;
 use rustc::session::{self, config};
 use rustc::session::config::{get_unstable_features_setting, OutputType};
@@ -99,7 +100,9 @@ pub fn run(input: &str,
 
     let opts = scrape_test_config(&krate);
 
-    let mut forest = hir_map::Forest::new(krate);
+    let dep_graph = DepGraph::new(false);
+    let _ignore = dep_graph.in_ignore();
+    let mut forest = hir_map::Forest::new(krate, dep_graph.clone());
     let map = hir_map::map_crate(&mut forest);
 
     let ctx = core::DocContext {
diff --git a/src/test/run-make/execution-engine/test.rs b/src/test/run-make/execution-engine/test.rs
index 3f9c81eac0b..13cbdfe24d6 100644
--- a/src/test/run-make/execution-engine/test.rs
+++ b/src/test/run-make/execution-engine/test.rs
@@ -26,6 +26,7 @@ use std::path::PathBuf;
 use std::rc::Rc;
 use std::thread::Builder;
 
+use rustc::dep_graph::DepGraph;
 use rustc::front::map as ast_map;
 use rustc::llvm;
 use rustc::middle::cstore::{CrateStore, LinkagePreference};
@@ -236,7 +237,8 @@ fn compile_program(input: &str, sysroot: PathBuf)
 
         let krate = driver::assign_node_ids(&sess, krate);
         let lcx = LoweringContext::new(&sess, Some(&krate));
-        let mut hir_forest = ast_map::Forest::new(lower_crate(&lcx, &krate));
+        let dep_graph = DepGraph::new(sess.opts.build_dep_graph);
+        let mut hir_forest = ast_map::Forest::new(lower_crate(&lcx, &krate), dep_graph);
         let arenas = ty::CtxtArenas::new();
         let ast_map = driver::make_map(&sess, &mut hir_forest);