Annotate the compiler with information about what it is doing when.

29 files changed, 171 insertions, 50 deletions

diff --git a/src/librustc/lint/context.rs b/src/librustc/lint/context.rs
index 464f29a3393..0ac5160c29e 100644
--- a/src/librustc/lint/context.rs
+++ b/src/librustc/lint/context.rs
@@ -25,6 +25,7 @@
 //! for all lint attributes.
 use self::TargetLint::*;
 
+use dep_graph::DepNode;
 use middle::privacy::AccessLevels;
 use middle::ty;
 use session::{early_error, Session};
@@ -1071,6 +1072,8 @@ impl LateLintPass for GatherNodeLevels {
 ///
 /// Consumes the `lint_store` field of the `Session`.
 pub fn check_crate(tcx: &ty::ctxt, access_levels: &AccessLevels) {
+    let _task = tcx.dep_graph.in_task(DepNode::LateLintCheck);
+
     let krate = tcx.map.krate();
     let mut cx = LateContext::new(tcx, krate, access_levels);
 
diff --git a/src/librustc/middle/check_const.rs b/src/librustc/middle/check_const.rs
index c2acd0e4795..a9b3043e090 100644
--- a/src/librustc/middle/check_const.rs
+++ b/src/librustc/middle/check_const.rs
@@ -24,6 +24,7 @@
 // - It's not possible to take the address of a static item with unsafe interior. This is enforced
 // by borrowck::gather_loans
 
+use dep_graph::DepNode;
 use middle::ty::cast::{CastKind};
 use middle::const_eval::{self, ConstEvalErr};
 use middle::const_eval::ErrKind::IndexOpFeatureGated;
@@ -842,13 +843,12 @@ fn check_adjustments<'a, 'tcx>(v: &mut CheckCrateVisitor<'a, 'tcx>, e: &hir::Exp
 }
 
 pub fn check_crate(tcx: &ty::ctxt) {
-    tcx.map.krate().visit_all_items(&mut CheckCrateVisitor {
+    tcx.visit_all_items_in_krate(DepNode::CheckConst, &mut CheckCrateVisitor {
         tcx: tcx,
         mode: Mode::Var,
         qualif: ConstQualif::NOT_CONST,
         rvalue_borrows: NodeMap()
     });
-
     tcx.sess.abort_if_errors();
 }
 
diff --git a/src/librustc/middle/check_match.rs b/src/librustc/middle/check_match.rs
index 8439b439d76..972f9e2c64d 100644
--- a/src/librustc/middle/check_match.rs
+++ b/src/librustc/middle/check_match.rs
@@ -12,6 +12,7 @@ pub use self::Constructor::*;
 use self::Usefulness::*;
 use self::WitnessPreference::*;
 
+use dep_graph::DepNode;
 use middle::const_eval::{compare_const_vals, ConstVal};
 use middle::const_eval::{eval_const_expr, eval_const_expr_partial};
 use middle::const_eval::{const_expr_to_pat, lookup_const_by_id};
@@ -155,7 +156,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for MatchCheckCtxt<'a, 'tcx> {
 }
 
 pub fn check_crate(tcx: &ty::ctxt) {
-    tcx.map.krate().visit_all_items(&mut MatchCheckCtxt {
+    tcx.visit_all_items_in_krate(DepNode::MatchCheck, &mut MatchCheckCtxt {
         tcx: tcx,
         param_env: tcx.empty_parameter_environment(),
     });
diff --git a/src/librustc/middle/check_rvalues.rs b/src/librustc/middle/check_rvalues.rs
index 35adeae3e61..8a3e039ac6e 100644
--- a/src/librustc/middle/check_rvalues.rs
+++ b/src/librustc/middle/check_rvalues.rs
@@ -11,21 +11,21 @@
 // Checks that all rvalues in a crate have statically known size. check_crate
 // is the public starting point.
 
+use dep_graph::DepNode;
 use middle::expr_use_visitor as euv;
 use middle::infer;
 use middle::mem_categorization as mc;
 use middle::ty::ParameterEnvironment;
 use middle::ty;
 
-use syntax::ast;
 use rustc_front::hir;
-use syntax::codemap::Span;
 use rustc_front::intravisit;
+use syntax::ast;
+use syntax::codemap::Span;
 
-pub fn check_crate(tcx: &ty::ctxt,
-                   krate: &hir::Crate) {
+pub fn check_crate(tcx: &ty::ctxt) {
     let mut rvcx = RvalueContext { tcx: tcx };
-    krate.visit_all_items(&mut rvcx);
+    tcx.visit_all_items_in_krate(DepNode::RvalueCheck, &mut rvcx);
 }
 
 struct RvalueContext<'a, 'tcx: 'a> {
diff --git a/src/librustc/middle/dead.rs b/src/librustc/middle/dead.rs
index ec1b447d711..1386ef91c70 100644
--- a/src/librustc/middle/dead.rs
+++ b/src/librustc/middle/dead.rs
@@ -12,6 +12,7 @@
 // closely. The idea is that all reachable symbols are live, codes called
 // from live codes are live, and everything else is dead.
 
+use dep_graph::DepNode;
 use front::map as ast_map;
 use rustc_front::hir;
 use rustc_front::intravisit::{self, Visitor};
@@ -590,6 +591,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for DeadVisitor<'a, 'tcx> {
 }
 
 pub fn check_crate(tcx: &ty::ctxt, access_levels: &privacy::AccessLevels) {
+    let _task = tcx.dep_graph.in_task(DepNode::DeadCheck);
     let krate = tcx.map.krate();
     let live_symbols = find_live(tcx, access_levels, krate);
     let mut visitor = DeadVisitor { tcx: tcx, live_symbols: live_symbols };
diff --git a/src/librustc/middle/intrinsicck.rs b/src/librustc/middle/intrinsicck.rs
index 48d7f44063e..f1eed256dd1 100644
--- a/src/librustc/middle/intrinsicck.rs
+++ b/src/librustc/middle/intrinsicck.rs
@@ -8,6 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use dep_graph::DepNode;
 use middle::def::DefFn;
 use middle::def_id::DefId;
 use middle::subst::{Subst, Substs, EnumeratedItems};
@@ -29,7 +30,7 @@ pub fn check_crate(tcx: &ctxt) {
         dummy_sized_ty: tcx.types.isize,
         dummy_unsized_ty: tcx.mk_slice(tcx.types.isize),
     };
-    tcx.map.krate().visit_all_items(&mut visitor);
+    tcx.visit_all_items_in_krate(DepNode::IntrinsicCheck, &mut visitor);
 }
 
 struct IntrinsicCheckingVisitor<'a, 'tcx: 'a> {
diff --git a/src/librustc/middle/reachable.rs b/src/librustc/middle/reachable.rs
index d146ad2d800..738440adf41 100644
--- a/src/librustc/middle/reachable.rs
+++ b/src/librustc/middle/reachable.rs
@@ -15,6 +15,7 @@
 // makes all other generics or inline functions that it references
 // reachable as well.
 
+use dep_graph::DepNode;
 use front::map as ast_map;
 use middle::def;
 use middle::def_id::DefId;
@@ -349,6 +350,7 @@ impl<'a, 'v> Visitor<'v> for CollectPrivateImplItemsVisitor<'a> {
 pub fn find_reachable(tcx: &ty::ctxt,
                       access_levels: &privacy::AccessLevels)
                       -> NodeSet {
+    let _task = tcx.dep_graph.in_task(DepNode::Reachability);
 
     let mut reachable_context = ReachableContext::new(tcx);
 
diff --git a/src/librustc/middle/stability.rs b/src/librustc/middle/stability.rs
index f6af680d441..8d5c0c98885 100644
--- a/src/librustc/middle/stability.rs
+++ b/src/librustc/middle/stability.rs
@@ -13,6 +13,7 @@
 
 pub use self::StabilityLevel::*;
 
+use dep_graph::DepNode;
 use session::Session;
 use lint;
 use middle::cstore::{CrateStore, LOCAL_CRATE};
@@ -328,6 +329,7 @@ impl<'tcx> Index<'tcx> {
 /// features used.
 pub fn check_unstable_api_usage(tcx: &ty::ctxt)
                                 -> FnvHashMap<InternedString, StabilityLevel> {
+    let _task = tcx.dep_graph.in_task(DepNode::StabilityCheck);
     let ref active_lib_features = tcx.sess.features.borrow().declared_lib_features;
 
     // Put the active features into a map for quick lookup
@@ -341,8 +343,7 @@ pub fn check_unstable_api_usage(tcx: &ty::ctxt)
     };
     intravisit::walk_crate(&mut checker, tcx.map.krate());
 
-    let used_features = checker.used_features;
-    return used_features;
+    checker.used_features
 }
 
 struct Checker<'a, 'tcx: 'a> {
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index 255680465ca..dddd6f8bc85 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -15,10 +15,12 @@ pub use self::FulfillmentErrorCode::*;
 pub use self::Vtable::*;
 pub use self::ObligationCauseCode::*;
 
+use dep_graph::DepNode;
 use middle::def_id::DefId;
 use middle::free_region::FreeRegionMap;
 use middle::subst;
 use middle::ty::{self, HasTypeFlags, Ty};
+use middle::ty::fast_reject;
 use middle::ty::fold::TypeFoldable;
 use middle::infer::{self, fixup_err_to_string, InferCtxt};
 
@@ -599,6 +601,18 @@ impl<'tcx> FulfillmentError<'tcx> {
 }
 
 impl<'tcx> TraitObligation<'tcx> {
+    /// Creates the dep-node for selecting/evaluating this trait reference.
+    fn dep_node(&self, tcx: &ty::ctxt<'tcx>) -> DepNode {
+        let simplified_ty =
+            fast_reject::simplify_type(tcx,
+                                       self.predicate.skip_binder().self_ty(), // (*)
+                                       true);
+
+        // (*) skip_binder is ok because `simplify_type` doesn't care about regions
+
+        DepNode::TraitSelect(self.predicate.def_id(), simplified_ty)
+    }
+
     fn self_ty(&self) -> ty::Binder<Ty<'tcx>> {
         ty::Binder(self.predicate.skip_binder().self_ty())
     }
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index b0215675fca..bd92f974866 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -310,6 +310,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         debug!("select({:?})", obligation);
         assert!(!obligation.predicate.has_escaping_regions());
 
+        let dep_node = obligation.dep_node(self.tcx());
+        let _task = self.tcx().dep_graph.in_task(dep_node);
+
         let stack = self.push_stack(TraitObligationStackList::empty(), obligation);
         match try!(self.candidate_from_obligation(&stack)) {
             None => {
@@ -411,7 +414,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     /// accurate if inference variables are involved.
     pub fn evaluate_obligation_conservatively(&mut self,
                                               obligation: &PredicateObligation<'tcx>)
-                               -> bool
+                                              -> bool
     {
         debug!("evaluate_obligation_conservatively({:?})",
                obligation);
diff --git a/src/librustc/middle/ty/mod.rs b/src/librustc/middle/ty/mod.rs
index 5daa9bcd0d1..f9d18e99297 100644
--- a/src/librustc/middle/ty/mod.rs
+++ b/src/librustc/middle/ty/mod.rs
@@ -51,6 +51,7 @@ use syntax::parse::token::{InternedString, special_idents};
 
 use rustc_front::hir;
 use rustc_front::hir::{ItemImpl, ItemTrait};
+use rustc_front::intravisit::Visitor;
 
 pub use self::sty::{Binder, DebruijnIndex};
 pub use self::sty::{BuiltinBound, BuiltinBounds, ExistentialBounds};
@@ -1946,7 +1947,14 @@ fn lookup_locally_or_in_crate_store<V, F>(descr: &str,
         panic!("No def'n found for {:?} in tcx.{}", def_id, descr);
     }
     let v = load_external();
-    map.borrow_mut().insert(def_id, v.clone());
+
+    // Don't consider this a write from the current task, since we are
+    // loading from another crate. (Note that the current task will
+    // already have registered a read in the call to `get` above.)
+    dep_graph.with_ignore(|| {
+        map.borrow_mut().insert(def_id, v.clone());
+    });
+
     v
 }
 
@@ -2458,6 +2466,10 @@ impl<'tcx> ctxt<'tcx> {
             return
         }
 
+        // The primitive is not local, hence we are reading this out
+        // of metadata.
+        let _ignore = self.dep_graph.in_ignore();
+
         if self.populated_external_primitive_impls.borrow().contains(&primitive_def_id) {
             return
         }
@@ -2480,6 +2492,10 @@ impl<'tcx> ctxt<'tcx> {
             return
         }
 
+        // The type is not local, hence we are reading this out of
+        // metadata and don't need to track edges.
+        let _ignore = self.dep_graph.in_ignore();
+
         if self.populated_external_types.borrow().contains(&type_id) {
             return
         }
@@ -2505,6 +2521,10 @@ impl<'tcx> ctxt<'tcx> {
             return
         }
 
+        // The type is not local, hence we are reading this out of
+        // metadata and don't need to track edges.
+        let _ignore = self.dep_graph.in_ignore();
+
         let def = self.lookup_trait_def(trait_id);
         if def.flags.get().intersects(TraitFlags::IMPLS_VALID) {
             return;
@@ -2727,6 +2747,15 @@ impl<'tcx> ctxt<'tcx> {
     pub fn upvar_capture(&self, upvar_id: ty::UpvarId) -> Option<ty::UpvarCapture> {
         Some(self.tables.borrow().upvar_capture_map.get(&upvar_id).unwrap().clone())
     }
+
+
+    pub fn visit_all_items_in_krate<V,F>(&self,
+                                         dep_node_fn: F,
+                                         visitor: &mut V)
+        where F: FnMut(DefId) -> DepNode, V: Visitor<'tcx>
+    {
+        dep_graph::visit_all_items_in_krate(self, dep_node_fn, visitor);
+    }
 }
 
 /// The category of explicit self.
diff --git a/src/librustc/session/config.rs b/src/librustc/session/config.rs
index 745be426676..0134bcdf175 100644
--- a/src/librustc/session/config.rs
+++ b/src/librustc/session/config.rs
@@ -125,6 +125,8 @@ pub struct Options {
     pub parse_only: bool,
     pub no_trans: bool,
     pub treat_err_as_bug: bool,
+    pub incremental_compilation: bool,
+    pub dump_dep_graph: bool,
     pub no_analysis: bool,
     pub debugging_opts: DebuggingOptions,
     pub prints: Vec<PrintRequest>,
@@ -234,6 +236,8 @@ pub fn basic_options() -> Options {
         parse_only: false,
         no_trans: false,
         treat_err_as_bug: false,
+        incremental_compilation: false,
+        dump_dep_graph: false,
         no_analysis: false,
         debugging_opts: basic_debugging_options(),
         prints: Vec::new(),
@@ -606,6 +610,10 @@ options! {DebuggingOptions, DebuggingSetter, basic_debugging_options,
           "run all passes except translation; no output"),
     treat_err_as_bug: bool = (false, parse_bool,
           "treat all errors that occur as bugs"),
+    incr_comp: bool = (false, parse_bool,
+          "enable incremental compilation (experimental)"),
+    dump_dep_graph: bool = (false, parse_bool,
+          "dump the dependency graph to $RUST_DEP_GRAPH (default: /tmp/dep_graph.gv)"),
     no_analysis: bool = (false, parse_bool,
           "parse and expand the source, but run no analysis"),
     extra_plugins: Vec<String> = (Vec::new(), parse_list,
@@ -932,6 +940,8 @@ pub fn build_session_options(matches: &getopts::Matches) -> Options {
     let parse_only = debugging_opts.parse_only;
     let no_trans = debugging_opts.no_trans;
     let treat_err_as_bug = debugging_opts.treat_err_as_bug;
+    let incremental_compilation = debugging_opts.incr_comp;
+    let dump_dep_graph = debugging_opts.dump_dep_graph;
     let no_analysis = debugging_opts.no_analysis;
 
     if debugging_opts.debug_llvm {
@@ -1106,6 +1116,8 @@ 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,
+        dump_dep_graph: dump_dep_graph,
         no_analysis: no_analysis,
         debugging_opts: debugging_opts,
         prints: prints,
diff --git a/src/librustc_borrowck/borrowck/mod.rs b/src/librustc_borrowck/borrowck/mod.rs
index 0a2586755ce..631149e69d7 100644
--- a/src/librustc_borrowck/borrowck/mod.rs
+++ b/src/librustc_borrowck/borrowck/mod.rs
@@ -20,6 +20,7 @@ pub use self::MovedValueUseKind::*;
 
 use self::InteriorKind::*;
 
+use rustc::dep_graph::DepNode;
 use rustc::front::map as hir_map;
 use rustc::front::map::blocks::FnParts;
 use rustc::middle::cfg;
@@ -109,7 +110,7 @@ pub fn check_crate(tcx: &ty::ctxt) {
         }
     };
 
-    tcx.map.krate().visit_all_items(&mut bccx);
+    tcx.visit_all_items_in_krate(DepNode::BorrowCheck, &mut bccx);
 
     if tcx.sess.borrowck_stats() {
         println!("--- borrowck stats ---");
diff --git a/src/librustc_driver/driver.rs b/src/librustc_driver/driver.rs
index 27740b8fc5c..d172bfb4413 100644
--- a/src/librustc_driver/driver.rs
+++ b/src/librustc_driver/driver.rs
@@ -801,7 +801,7 @@ pub fn phase_3_run_analysis_passes<'tcx, F, R>(sess: &'tcx Session,
 
                                    time(time_passes,
                                         "rvalue checking",
-                                        || middle::check_rvalues::check_crate(tcx, krate));
+                                        || middle::check_rvalues::check_crate(tcx));
 
                                    // Avoid overwhelming user with errors if type checking failed.
                                    // I'm not sure how helpful this is, to be honest, but it avoids
diff --git a/src/librustc_driver/pretty.rs b/src/librustc_driver/pretty.rs
index 47b89e3be5d..ba5ecc22e74 100644
--- a/src/librustc_driver/pretty.rs
+++ b/src/librustc_driver/pretty.rs
@@ -204,6 +204,7 @@ impl PpSourceMode {
                                                         let annotation = TypedAnnotation {
                                                             tcx: tcx,
                                                         };
+                                                        let _ignore = tcx.dep_graph.in_ignore();
                                                         f(&annotation,
                                                           payload,
                                                           &ast_map.forest.krate)
diff --git a/src/librustc_mir/mir_map.rs b/src/librustc_mir/mir_map.rs
index 5c9399ebdad..08174272a9b 100644
--- a/src/librustc_mir/mir_map.rs
+++ b/src/librustc_mir/mir_map.rs
@@ -23,6 +23,7 @@ extern crate rustc_front;
 use build;
 use graphviz;
 use transform::*;
+use rustc::dep_graph::DepNode;
 use rustc::mir::repr::Mir;
 use hair::cx::Cx;
 use std::fs::File;
@@ -47,7 +48,7 @@ pub fn build_mir_for_crate<'tcx>(tcx: &ty::ctxt<'tcx>) -> MirMap<'tcx> {
             tcx: tcx,
             map: &mut map,
         };
-        tcx.map.krate().visit_all_items(&mut dump);
+        tcx.visit_all_items_in_krate(DepNode::MirMapConstruction, &mut dump);
     }
     map
 }
diff --git a/src/librustc_privacy/lib.rs b/src/librustc_privacy/lib.rs
index 1cc2482a39e..955e68be0b0 100644
--- a/src/librustc_privacy/lib.rs
+++ b/src/librustc_privacy/lib.rs
@@ -35,6 +35,7 @@ use std::mem::replace;
 use rustc_front::hir;
 use rustc_front::intravisit::{self, Visitor};
 
+use rustc::dep_graph::DepNode;
 use rustc::lint;
 use rustc::middle::def;
 use rustc::middle::def_id::DefId;
@@ -1674,6 +1675,8 @@ pub fn check_crate(tcx: &ty::ctxt,
                    export_map: &def::ExportMap,
                    external_exports: ExternalExports)
                    -> AccessLevels {
+    let _task = tcx.dep_graph.in_task(DepNode::Privacy);
+
     let krate = tcx.map.krate();
 
     // Sanity check to make sure that all privacy usage and controls are
diff --git a/src/librustc_trans/back/link.rs b/src/librustc_trans/back/link.rs
index 8446db65a4c..e1edbf4a127 100644
--- a/src/librustc_trans/back/link.rs
+++ b/src/librustc_trans/back/link.rs
@@ -182,8 +182,10 @@ pub fn find_crate_name(sess: Option<&Session>,
     "rust_out".to_string()
 }
 
-pub fn build_link_meta(sess: &Session, krate: &hir::Crate,
-                       name: &str) -> LinkMeta {
+pub fn build_link_meta(sess: &Session,
+                       krate: &hir::Crate,
+                       name: &str)
+                       -> LinkMeta {
     let r = LinkMeta {
         crate_name: name.to_owned(),
         crate_hash: Svh::calculate(&sess.opts.cg.metadata, krate),
diff --git a/src/librustc_trans/save/mod.rs b/src/librustc_trans/save/mod.rs
index 501ab566f1c..e1343c73acf 100644
--- a/src/librustc_trans/save/mod.rs
+++ b/src/librustc_trans/save/mod.rs
@@ -716,6 +716,8 @@ pub fn process_crate<'l, 'tcx>(tcx: &'l ty::ctxt<'tcx>,
                                analysis: &ty::CrateAnalysis,
                                cratename: &str,
                                odir: Option<&Path>) {
+    let _ignore = tcx.dep_graph.in_ignore();
+
     if generated_code(krate.span) {
         return;
     }
diff --git a/src/librustc_trans/trans/base.rs b/src/librustc_trans/trans/base.rs
index 4197f80cb5e..6dffdf74140 100644
--- a/src/librustc_trans/trans/base.rs
+++ b/src/librustc_trans/trans/base.rs
@@ -43,6 +43,7 @@ use middle::weak_lang_items;
 use middle::pat_util::simple_name;
 use middle::subst::Substs;
 use middle::ty::{self, Ty, HasTypeFlags};
+use rustc::dep_graph::DepNode;
 use rustc::front::map as hir_map;
 use rustc::util::common::time;
 use rustc_mir::mir_map::MirMap;
@@ -2978,9 +2979,16 @@ pub fn trans_crate<'tcx>(tcx: &ty::ctxt<'tcx>,
                          mir_map: &MirMap<'tcx>,
                          analysis: ty::CrateAnalysis)
                          -> CrateTranslation {
-    let ty::CrateAnalysis { export_map, reachable, name, .. } = analysis;
+    let _task = tcx.dep_graph.in_task(DepNode::TransCrate);
+
+    // Be careful with this krate: obviously it gives access to the
+    // entire contents of the krate. So if you push any subtasks of
+    // `TransCrate`, you need to be careful to register "reads" of the
+    // particular items that will be processed.
     let krate = tcx.map.krate();
 
+    let ty::CrateAnalysis { export_map, reachable, name, .. } = analysis;
+
     let check_overflow = if let Some(v) = tcx.sess.opts.debugging_opts.force_overflow_checks {
         v
     } else {
@@ -3186,7 +3194,16 @@ impl<'a, 'tcx, 'v> Visitor<'v> for TransItemsWithinModVisitor<'a, 'tcx> {
                 // skip modules, they will be uncovered by the TransModVisitor
             }
             _ => {
-                trans_item(self.ccx, i);
+                let def_id = self.ccx.tcx().map.local_def_id(i.id);
+                let tcx = self.ccx.tcx();
+
+                // Create a subtask for trans'ing a particular item. We are
+                // giving `trans_item` access to this item, so also record a read.
+                tcx.dep_graph.with_task(DepNode::TransCrateItem(def_id), || {
+                    tcx.dep_graph.read(DepNode::Hir(def_id));
+                    trans_item(self.ccx, i);
+                });
+
                 intravisit::walk_item(self, i);
             }
         }
diff --git a/src/librustc_trans/trans/inline.rs b/src/librustc_trans/trans/inline.rs
index 29965755eac..89399043c96 100644
--- a/src/librustc_trans/trans/inline.rs
+++ b/src/librustc_trans/trans/inline.rs
@@ -15,12 +15,13 @@ use middle::subst::Substs;
 use trans::base::{push_ctxt, trans_item, get_item_val, trans_fn};
 use trans::common::*;
 
+use rustc::dep_graph::DepNode;
 use rustc_front::hir;
 
-fn instantiate_inline(ccx: &CrateContext, fn_id: DefId)
-    -> Option<DefId> {
+fn instantiate_inline(ccx: &CrateContext, fn_id: DefId) -> Option<DefId> {
     debug!("instantiate_inline({:?})", fn_id);
     let _icx = push_ctxt("instantiate_inline");
+    let _task = ccx.tcx().dep_graph.in_task(DepNode::TransInlinedItem(fn_id));
 
     match ccx.external().borrow().get(&fn_id) {
         Some(&Some(node_id)) => {
diff --git a/src/librustc_trans/trans/intrinsic.rs b/src/librustc_trans/trans/intrinsic.rs
index 66f53deffa9..d8a3cc50ff4 100644
--- a/src/librustc_trans/trans/intrinsic.rs
+++ b/src/librustc_trans/trans/intrinsic.rs
@@ -37,6 +37,7 @@ use trans::machine;
 use trans::type_::Type;
 use middle::ty::{self, Ty, HasTypeFlags};
 use middle::subst::Substs;
+use rustc::dep_graph::DepNode;
 use rustc_front::hir;
 use syntax::abi::{self, RustIntrinsic};
 use syntax::ast;
@@ -101,6 +102,7 @@ pub fn span_transmute_size_error(a: &Session, b: Span, msg: &str) {
 /// Performs late verification that intrinsics are used correctly. At present,
 /// the only intrinsic that needs such verification is `transmute`.
 pub fn check_intrinsics(ccx: &CrateContext) {
+    let _task = ccx.tcx().dep_graph.in_task(DepNode::IntrinsicUseCheck);
     let mut last_failing_id = None;
     for transmute_restriction in ccx.tcx().transmute_restrictions.borrow().iter() {
         // Sometimes, a single call to transmute will push multiple
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index ca2db8c3def..14adc84f701 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -82,6 +82,7 @@ use self::TupleArgumentsFlag::*;
 
 use astconv::{self, ast_region_to_region, ast_ty_to_ty, AstConv, PathParamMode};
 use check::_match::pat_ctxt;
+use dep_graph::DepNode;
 use fmt_macros::{Parser, Piece, Position};
 use middle::astconv_util::prohibit_type_params;
 use middle::cstore::LOCAL_CRATE;
@@ -384,34 +385,33 @@ impl<'a, 'tcx> Visitor<'tcx> for CheckItemBodiesVisitor<'a, 'tcx> {
 
 pub fn check_wf_new(ccx: &CrateCtxt) {
     ccx.tcx.sess.abort_if_new_errors(|| {
-        let krate = ccx.tcx.map.krate();
         let mut visit = wfcheck::CheckTypeWellFormedVisitor::new(ccx);
-        krate.visit_all_items(&mut visit);
+        ccx.tcx.visit_all_items_in_krate(DepNode::WfCheck, &mut visit);
     });
 }
 
 pub fn check_item_types(ccx: &CrateCtxt) {
     ccx.tcx.sess.abort_if_new_errors(|| {
-        let krate = ccx.tcx.map.krate();
         let mut visit = CheckItemTypesVisitor { ccx: ccx };
-        krate.visit_all_items(&mut visit);
+        ccx.tcx.visit_all_items_in_krate(DepNode::TypeckItemType, &mut visit);
     });
 }
 
 pub fn check_item_bodies(ccx: &CrateCtxt) {
     ccx.tcx.sess.abort_if_new_errors(|| {
-        let krate = ccx.tcx.map.krate();
         let mut visit = CheckItemBodiesVisitor { ccx: ccx };
-        krate.visit_all_items(&mut visit);
+        ccx.tcx.visit_all_items_in_krate(DepNode::TypeckItemBody, &mut visit);
     });
 }
 
 pub fn check_drop_impls(ccx: &CrateCtxt) {
     ccx.tcx.sess.abort_if_new_errors(|| {
+        let _task = ccx.tcx.dep_graph.in_task(DepNode::Dropck);
         let drop_trait = match ccx.tcx.lang_items.drop_trait() {
             Some(id) => ccx.tcx.lookup_trait_def(id), None => { return }
         };
         drop_trait.for_each_impl(ccx.tcx, |drop_impl_did| {
+            let _task = ccx.tcx.dep_graph.in_task(DepNode::DropckImpl(drop_impl_did));
             if drop_impl_did.is_local() {
                 match dropck::check_drop_impl(ccx.tcx, drop_impl_did) {
                     Ok(()) => {}
diff --git a/src/librustc_typeck/coherence/mod.rs b/src/librustc_typeck/coherence/mod.rs
index 02be74a5906..07c920829d9 100644
--- a/src/librustc_typeck/coherence/mod.rs
+++ b/src/librustc_typeck/coherence/mod.rs
@@ -39,9 +39,10 @@ use std::rc::Rc;
 use syntax::codemap::Span;
 use syntax::parse::token;
 use util::nodemap::{DefIdMap, FnvHashMap};
+use rustc::dep_graph::DepNode;
 use rustc::front::map as hir_map;
 use rustc_front::intravisit;
-use rustc_front::hir::{Item, ItemImpl,Crate};
+use rustc_front::hir::{Item, ItemImpl};
 use rustc_front::hir;
 
 mod orphan;
@@ -104,11 +105,13 @@ impl<'a, 'tcx, 'v> intravisit::Visitor<'v> for CoherenceCheckVisitor<'a, 'tcx> {
 }
 
 impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
-    fn check(&self, krate: &Crate) {
+    fn check(&self) {
         // Check implementations and traits. This populates the tables
         // containing the inherent methods and extension methods. It also
         // builds up the trait inheritance table.
-        krate.visit_all_items(&mut CoherenceCheckVisitor { cc: self });
+        self.crate_context.tcx.visit_all_items_in_krate(
+            DepNode::CoherenceCheckImpl,
+            &mut CoherenceCheckVisitor { cc: self });
 
         // Copy over the inherent impls we gathered up during the walk into
         // the tcx.
@@ -513,11 +516,13 @@ fn enforce_trait_manually_implementable(tcx: &ty::ctxt, sp: Span, trait_def_id:
 }
 
 pub fn check_coherence(crate_context: &CrateCtxt) {
+    let _task = crate_context.tcx.dep_graph.in_task(DepNode::Coherence);
+    let infcx = new_infer_ctxt(crate_context.tcx, &crate_context.tcx.tables, None, true);
     CoherenceChecker {
         crate_context: crate_context,
-        inference_context: new_infer_ctxt(crate_context.tcx, &crate_context.tcx.tables, None, true),
+        inference_context: infcx,
         inherent_impls: RefCell::new(FnvHashMap()),
-    }.check(crate_context.tcx.map.krate());
+    }.check();
     unsafety::check(crate_context.tcx);
     orphan::check(crate_context.tcx);
     overlap::check(crate_context.tcx);
diff --git a/src/librustc_typeck/coherence/orphan.rs b/src/librustc_typeck/coherence/orphan.rs
index 76be04bb174..69eb7f51f37 100644
--- a/src/librustc_typeck/coherence/orphan.rs
+++ b/src/librustc_typeck/coherence/orphan.rs
@@ -17,12 +17,13 @@ use middle::traits;
 use middle::ty;
 use syntax::ast;
 use syntax::codemap::Span;
+use rustc::dep_graph::DepNode;
 use rustc_front::intravisit;
 use rustc_front::hir;
 
 pub fn check(tcx: &ty::ctxt) {
     let mut orphan = OrphanChecker { tcx: tcx };
-    tcx.map.krate().visit_all_items(&mut orphan);
+    tcx.visit_all_items_in_krate(DepNode::CoherenceOrphanCheck, &mut orphan);
 }
 
 struct OrphanChecker<'cx, 'tcx:'cx> {
@@ -234,10 +235,10 @@ impl<'cx, 'tcx> OrphanChecker<'cx, 'tcx> {
                     }
                     Err(traits::OrphanCheckErr::UncoveredTy(param_ty)) => {
                         span_err!(self.tcx.sess, item.span, E0210,
-                                "type parameter `{}` must be used as the type parameter for \
-                                 some local type (e.g. `MyStruct<T>`); only traits defined in \
-                                 the current crate can be implemented for a type parameter",
-                                param_ty);
+                                  "type parameter `{}` must be used as the type parameter for \
+                                   some local type (e.g. `MyStruct<T>`); only traits defined in \
+                                   the current crate can be implemented for a type parameter",
+                                  param_ty);
                         return;
                     }
                 }
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index eaaa2c77379..6135cf1d32a 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -79,6 +79,7 @@ use middle::ty::{VariantKind};
 use middle::ty::fold::{TypeFolder};
 use middle::ty::util::IntTypeExt;
 use rscope::*;
+use rustc::dep_graph::DepNode;
 use rustc::front::map as hir_map;
 use util::common::{ErrorReported, memoized};
 use util::nodemap::{FnvHashMap, FnvHashSet};
@@ -174,13 +175,11 @@ struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
 }
 
 impl<'a, 'tcx, 'v> intravisit::Visitor<'v> for CollectItemTypesVisitor<'a, 'tcx> {
-    fn visit_item(&mut self, i: &hir::Item) {
-        convert_item(self.ccx, i);
-        intravisit::walk_item(self, i);
-    }
-    fn visit_foreign_item(&mut self, i: &hir::ForeignItem) {
-        convert_foreign_item(self.ccx, i);
-        intravisit::walk_foreign_item(self, i);
+    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);
     }
 }
 
@@ -703,8 +702,12 @@ fn convert_item(ccx: &CrateCtxt, it: &hir::Item) {
     debug!("convert: item {} with id {}", it.name, it.id);
     match it.node {
         // These don't define types.
-        hir::ItemExternCrate(_) | hir::ItemUse(_) |
-        hir::ItemForeignMod(_) | hir::ItemMod(_) => {
+        hir::ItemExternCrate(_) | hir::ItemUse(_) | hir::ItemMod(_) => {
+        }
+        hir::ItemForeignMod(ref foreign_mod) => {
+            for item in &foreign_mod.items {
+                convert_foreign_item(ccx, item);
+            }
         }
         hir::ItemEnum(ref enum_definition, _) => {
             let (scheme, predicates) = convert_typed_item(ccx, it);
@@ -1455,6 +1458,11 @@ fn type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
                                 it: &hir::Item)
                                 -> ty::TypeScheme<'tcx>
 {
+    // Computing the type scheme of an item is a discrete task:
+    let item_def_id = ccx.tcx.map.local_def_id(it.id);
+    let _task = ccx.tcx.dep_graph.in_task(DepNode::TypeScheme(item_def_id));
+    ccx.tcx.dep_graph.read(DepNode::Hir(item_def_id)); // we have access to `it`
+
     memoized(&ccx.tcx.tcache,
              ccx.tcx.map.local_def_id(it.id),
              |_| compute_type_scheme_of_item(ccx, it))
@@ -1571,13 +1579,18 @@ fn convert_typed_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 
 fn type_scheme_of_foreign_item<'a, 'tcx>(
     ccx: &CrateCtxt<'a, 'tcx>,
-    it: &hir::ForeignItem,
+    item: &hir::ForeignItem,
     abi: abi::Abi)
     -> ty::TypeScheme<'tcx>
 {
+    // Computing the type scheme of a foreign item is a discrete task:
+    let item_def_id = ccx.tcx.map.local_def_id(item.id);
+    let _task = ccx.tcx.dep_graph.in_task(DepNode::TypeScheme(item_def_id));
+    ccx.tcx.dep_graph.read(DepNode::Hir(item_def_id)); // we have access to `item`
+
     memoized(&ccx.tcx.tcache,
-             ccx.tcx.map.local_def_id(it.id),
-             |_| compute_type_scheme_of_foreign_item(ccx, it, abi))
+             ccx.tcx.map.local_def_id(item.id),
+             |_| compute_type_scheme_of_foreign_item(ccx, item, abi))
 }
 
 fn compute_type_scheme_of_foreign_item<'a, 'tcx>(
diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs
index bf890f3e507..580d200eb73 100644
--- a/src/librustc_typeck/lib.rs
+++ b/src/librustc_typeck/lib.rs
@@ -92,6 +92,7 @@ extern crate rustc_platform_intrinsics as intrinsics;
 extern crate rustc_front;
 extern crate rustc_back;
 
+pub use rustc::dep_graph;
 pub use rustc::front;
 pub use rustc::lint;
 pub use rustc::middle;
diff --git a/src/librustc_typeck/variance.rs b/src/librustc_typeck/variance.rs
index 8c7967c7078..ce0e9e14035 100644
--- a/src/librustc_typeck/variance.rs
+++ b/src/librustc_typeck/variance.rs
@@ -266,6 +266,7 @@ use self::ParamKind::*;
 
 use arena;
 use arena::TypedArena;
+use dep_graph::DepNode;
 use middle::def_id::DefId;
 use middle::resolve_lifetime as rl;
 use middle::subst;
@@ -280,6 +281,7 @@ use rustc_front::intravisit::Visitor;
 use util::nodemap::NodeMap;
 
 pub fn infer_variance(tcx: &ty::ctxt) {
+    let _task = tcx.dep_graph.in_task(DepNode::Variance);
     let krate = tcx.map.krate();
     let mut arena = arena::TypedArena::new();
     let terms_cx = determine_parameters_to_be_inferred(tcx, &mut arena, krate);
diff --git a/src/librustdoc/core.rs b/src/librustdoc/core.rs
index d7190a4bea9..d57d1bcd92d 100644
--- a/src/librustdoc/core.rs
+++ b/src/librustdoc/core.rs
@@ -154,6 +154,7 @@ pub fn run_core(search_paths: SearchPaths, cfgs: Vec<String>, externs: Externs,
                                         &name,
                                         resolve::MakeGlobMap::No,
                                         |tcx, _, analysis| {
+        let _ignore = tcx.dep_graph.in_ignore();
         let ty::CrateAnalysis { access_levels, .. } = analysis;
 
         // Convert from a NodeId set to a DefId set since we don't always have easy access