Auto merge of #44501 - nikomatsakis:issue-44137-non-query-data-in-tcx, r=eddyb

remove or encapsulate the remaining non-query data in tcx

I wound up removing the existing cache around inhabitedness since it didn't seem to be adding much value. I reworked const rvalue promotion, but not that much (i.e., I did not split the computation into bits, as @eddyb had tossed out as a suggestion). But it's now demand driven, at least.

cc @michaelwoerister -- see the `forbid_reads` change in last commit

r? @eddyb -- since the trickiest of this PR is the work on const rvalue promotion

cc #44137

25 files changed, 438 insertions, 241 deletions

diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index a86742d7bd4..d67a74f681e 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -360,8 +360,10 @@ git add path/to/submodule
 
 outside the submodule.
 
-It can also be more convenient during development to set `submodules = false`
-in the `config.toml` to prevent `x.py` from resetting to the original branch.
+In order to prepare your PR, you can run the build locally by doing
+`./x.py build src/tools/TOOL`. If you will be editing the sources
+there, you may wish to set `submodules = false` in the `config.toml`
+to prevent `x.py` from resetting to the original branch.
 
 ## Writing Documentation
 [writing-documentation]: #writing-documentation
diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index 92bbb745bb2..f9e902b9105 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -554,6 +554,7 @@ define_dep_nodes!( <'tcx>
     [] LookupDeprecationEntry(DefId),
     [] ItemBodyNestedBodies(DefId),
     [] ConstIsRvaluePromotableToStatic(DefId),
+    [] RvaluePromotableMap(DefId),
     [] ImplParent(DefId),
     [] TraitOfItem(DefId),
     [] IsExportedSymbol(DefId),
@@ -609,6 +610,7 @@ define_dep_nodes!( <'tcx>
     [] PostorderCnums,
     [] HasCloneClosures(CrateNum),
     [] HasCopyClosures(CrateNum),
+    [] EraseRegionsTy { ty: Ty<'tcx> },
 
     [] Freevars(DefId),
     [] MaybeUnusedTraitImport(DefId),
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index ed440849b48..64fe4626d6e 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -60,7 +60,7 @@
 #![cfg_attr(stage0, feature(const_fn))]
 #![cfg_attr(not(stage0), feature(const_atomic_bool_new))]
 
-#![recursion_limit="256"]
+#![recursion_limit="512"]
 
 extern crate arena;
 #[macro_use] extern crate bitflags;
diff --git a/src/librustc/middle/expr_use_visitor.rs b/src/librustc/middle/expr_use_visitor.rs
index b036b145a96..e62cc2a658a 100644
--- a/src/librustc/middle/expr_use_visitor.rs
+++ b/src/librustc/middle/expr_use_visitor.rs
@@ -27,10 +27,11 @@ use middle::region;
 use ty::{self, TyCtxt, adjustment};
 
 use hir::{self, PatKind};
-
+use std::rc::Rc;
 use syntax::ast;
 use syntax::ptr::P;
 use syntax_pos::Span;
+use util::nodemap::ItemLocalMap;
 
 ///////////////////////////////////////////////////////////////////////////
 // The Delegate trait
@@ -262,15 +263,30 @@ macro_rules! return_if_err {
 }
 
 impl<'a, 'tcx> ExprUseVisitor<'a, 'tcx, 'tcx> {
+    /// Creates the ExprUseVisitor, configuring it with the various options provided:
+    ///
+    /// - `delegate` -- who receives the callbacks
+    /// - `param_env` --- parameter environment for trait lookups (esp. pertaining to `Copy`)
+    /// - `region_scope_tree` --- region scope tree for the code being analyzed
+    /// - `tables` --- typeck results for the code being analyzed
+    /// - `rvalue_promotable_map` --- if you care about rvalue promotion, then provide
+    ///   the map here (it can be computed with `tcx.rvalue_promotable_map(def_id)`).
+    ///   `None` means that rvalues will be given more conservative lifetimes.
+    ///
+    /// See also `with_infer`, which is used *during* typeck.
     pub fn new(delegate: &'a mut (Delegate<'tcx>+'a),
                tcx: TyCtxt<'a, 'tcx, 'tcx>,
                param_env: ty::ParamEnv<'tcx>,
                region_scope_tree: &'a region::ScopeTree,
-               tables: &'a ty::TypeckTables<'tcx>)
+               tables: &'a ty::TypeckTables<'tcx>,
+               rvalue_promotable_map: Option<Rc<ItemLocalMap<bool>>>)
                -> Self
     {
         ExprUseVisitor {
-            mc: mc::MemCategorizationContext::new(tcx, region_scope_tree, tables),
+            mc: mc::MemCategorizationContext::new(tcx,
+                                                  region_scope_tree,
+                                                  tables,
+                                                  rvalue_promotable_map),
             delegate,
             param_env,
         }
diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index 8754316ca84..e0e30f88316 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -86,6 +86,7 @@ use syntax_pos::Span;
 
 use std::fmt;
 use std::rc::Rc;
+use util::nodemap::ItemLocalMap;
 
 #[derive(Clone, PartialEq)]
 pub enum Categorization<'tcx> {
@@ -285,6 +286,7 @@ pub struct MemCategorizationContext<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     pub tcx: TyCtxt<'a, 'gcx, 'tcx>,
     pub region_scope_tree: &'a region::ScopeTree,
     pub tables: &'a ty::TypeckTables<'tcx>,
+    rvalue_promotable_map: Option<Rc<ItemLocalMap<bool>>>,
     infcx: Option<&'a InferCtxt<'a, 'gcx, 'tcx>>,
 }
 
@@ -392,21 +394,46 @@ impl MutabilityCategory {
 impl<'a, 'tcx> MemCategorizationContext<'a, 'tcx, 'tcx> {
     pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                region_scope_tree: &'a region::ScopeTree,
-               tables: &'a ty::TypeckTables<'tcx>)
+               tables: &'a ty::TypeckTables<'tcx>,
+               rvalue_promotable_map: Option<Rc<ItemLocalMap<bool>>>)
                -> MemCategorizationContext<'a, 'tcx, 'tcx> {
-        MemCategorizationContext { tcx, region_scope_tree, tables, infcx: None }
+        MemCategorizationContext {
+            tcx,
+            region_scope_tree,
+            tables,
+            rvalue_promotable_map,
+            infcx: None
+        }
     }
 }
 
 impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
+    /// Creates a `MemCategorizationContext` during type inference.
+    /// This is used during upvar analysis and a few other places.
+    /// Because the typeck tables are not yet complete, the results
+    /// from the analysis must be used with caution:
+    ///
+    /// - rvalue promotions are not known, so the lifetimes of
+    ///   temporaries may be overly conservative;
+    /// - similarly, as the results of upvar analysis are not yet
+    ///   known, the results around upvar accesses may be incorrect.
     pub fn with_infer(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
                       region_scope_tree: &'a region::ScopeTree,
                       tables: &'a ty::TypeckTables<'tcx>)
                       -> MemCategorizationContext<'a, 'gcx, 'tcx> {
+        let tcx = infcx.tcx;
+
+        // Subtle: we can't do rvalue promotion analysis until the
+        // typeck phase is complete, which means that you can't trust
+        // the rvalue lifetimes that result, but that's ok, since we
+        // don't need to know those during type inference.
+        let rvalue_promotable_map = None;
+
         MemCategorizationContext {
-            tcx: infcx.tcx,
+            tcx,
             region_scope_tree,
             tables,
+            rvalue_promotable_map,
             infcx: Some(infcx),
         }
     }
@@ -869,8 +896,9 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                            span: Span,
                            expr_ty: Ty<'tcx>)
                            -> cmt<'tcx> {
-        let promotable = self.tcx.rvalue_promotable_to_static.borrow().get(&id).cloned()
-                                   .unwrap_or(false);
+        let hir_id = self.tcx.hir.node_to_hir_id(id);
+        let promotable = self.rvalue_promotable_map.as_ref().map(|m| m[&hir_id.local_id])
+                                                            .unwrap_or(false);
 
         // Always promote `[T; 0]` (even when e.g. borrowed mutably).
         let promotable = match expr_ty.sty {
@@ -885,7 +913,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
         let re = if promotable {
             self.tcx.types.re_static
         } else {
-            self.temporary_scope(self.tcx.hir.node_to_hir_id(id).local_id)
+            self.temporary_scope(hir_id.local_id)
         };
         let ret = self.cat_rvalue(id, span, re, expr_ty);
         debug!("cat_rvalue_node ret {:?}", ret);
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 24ba38cf147..3d5e8ea583c 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -43,7 +43,6 @@ use ty::RegionKind;
 use ty::{TyVar, TyVid, IntVar, IntVid, FloatVar, FloatVid};
 use ty::TypeVariants::*;
 use ty::layout::{Layout, TargetDataLayout};
-use ty::inhabitedness::DefIdForest;
 use ty::maps;
 use ty::steal::Steal;
 use ty::BindingMode;
@@ -893,11 +892,6 @@ pub struct GlobalCtxt<'tcx> {
     // Internal cache for metadata decoding. No need to track deps on this.
     pub rcache: RefCell<FxHashMap<ty::CReaderCacheKey, Ty<'tcx>>>,
 
-    // FIXME dep tracking -- should be harmless enough
-    pub normalized_cache: RefCell<FxHashMap<Ty<'tcx>, Ty<'tcx>>>,
-
-    pub inhabitedness_cache: RefCell<FxHashMap<Ty<'tcx>, DefIdForest>>,
-
     /// Caches the results of trait selection. This cache is used
     /// for things that do not have to do with the parameters in scope.
     pub selection_cache: traits::SelectionCache<'tcx>,
@@ -907,9 +901,6 @@ pub struct GlobalCtxt<'tcx> {
     /// Merge this with `selection_cache`?
     pub evaluation_cache: traits::EvaluationCache<'tcx>,
 
-    /// Maps Expr NodeId's to `true` iff `&expr` can have 'static lifetime.
-    pub rvalue_promotable_to_static: RefCell<NodeMap<bool>>,
-
     /// The definite name of the current crate after taking into account
     /// attributes, commandline parameters, etc.
     pub crate_name: Symbol,
@@ -1178,11 +1169,8 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             maps: maps::Maps::new(providers),
             mir_passes,
             rcache: RefCell::new(FxHashMap()),
-            normalized_cache: RefCell::new(FxHashMap()),
-            inhabitedness_cache: RefCell::new(FxHashMap()),
             selection_cache: traits::SelectionCache::new(),
             evaluation_cache: traits::EvaluationCache::new(),
-            rvalue_promotable_to_static: RefCell::new(NodeMap()),
             crate_name: Symbol::intern(crate_name),
             data_layout,
             layout_interner: RefCell::new(FxHashSet()),
diff --git a/src/librustc/ty/erase_regions.rs b/src/librustc/ty/erase_regions.rs
new file mode 100644
index 00000000000..4f8fca67949
--- /dev/null
+++ b/src/librustc/ty/erase_regions.rs
@@ -0,0 +1,79 @@
+// 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 ty::{self, Ty, TyCtxt};
+use ty::fold::{TypeFolder, TypeFoldable};
+
+pub(super) fn provide(providers: &mut ty::maps::Providers) {
+    *providers = ty::maps::Providers {
+        erase_regions_ty,
+        ..*providers
+    };
+}
+
+fn erase_regions_ty<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
+    // NB: use `super_fold_with` here. If we used `fold_with`, it
+    // could invoke the `erase_regions_ty` query recursively.
+    ty.super_fold_with(&mut RegionEraserVisitor { tcx })
+}
+
+impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
+    /// Returns an equivalent value with all free regions removed (note
+    /// that late-bound regions remain, because they are important for
+    /// subtyping, but they are anonymized and normalized as well)..
+    pub fn erase_regions<T>(self, value: &T) -> T
+        where T : TypeFoldable<'tcx>
+    {
+        let value1 = value.fold_with(&mut RegionEraserVisitor { tcx: self });
+        debug!("erase_regions({:?}) = {:?}", value, value1);
+        value1
+    }
+}
+
+struct RegionEraserVisitor<'a, 'gcx: 'tcx, 'tcx: 'a> {
+    tcx: TyCtxt<'a, 'gcx, 'tcx>,
+}
+
+impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionEraserVisitor<'a, 'gcx, 'tcx> {
+    fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
+        self.tcx
+    }
+
+    fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
+        if let Some(ty_lifted) = self.tcx.lift_to_global(&ty) {
+            self.tcx.erase_regions_ty(ty_lifted)
+        } else {
+            ty.super_fold_with(self)
+        }
+    }
+
+    fn fold_binder<T>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T>
+        where T : TypeFoldable<'tcx>
+    {
+        let u = self.tcx.anonymize_late_bound_regions(t);
+        u.super_fold_with(self)
+    }
+
+    fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
+        // because late-bound regions affect subtyping, we can't
+        // erase the bound/free distinction, but we can replace
+        // all free regions with 'erased.
+        //
+        // Note that we *CAN* replace early-bound regions -- the
+        // type system never "sees" those, they get substituted
+        // away. In trans, they will always be erased to 'erased
+        // whenever a substitution occurs.
+        match *r {
+            ty::ReLateBound(..) => r,
+            _ => self.tcx.types.re_erased
+        }
+    }
+}
+
diff --git a/src/librustc/ty/fold.rs b/src/librustc/ty/fold.rs
index 543e8f3e2f0..edd4329fa41 100644
--- a/src/librustc/ty/fold.rs
+++ b/src/librustc/ty/fold.rs
@@ -445,67 +445,6 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionReplacer<'a, 'gcx, 'tcx> {
 }
 
 ///////////////////////////////////////////////////////////////////////////
-// Region eraser
-
-impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
-    /// Returns an equivalent value with all free regions removed (note
-    /// that late-bound regions remain, because they are important for
-    /// subtyping, but they are anonymized and normalized as well)..
-    pub fn erase_regions<T>(self, value: &T) -> T
-        where T : TypeFoldable<'tcx>
-    {
-        let value1 = value.fold_with(&mut RegionEraser(self));
-        debug!("erase_regions({:?}) = {:?}",
-               value, value1);
-        return value1;
-
-        struct RegionEraser<'a, 'gcx: 'a+'tcx, 'tcx: 'a>(TyCtxt<'a, 'gcx, 'tcx>);
-
-        impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionEraser<'a, 'gcx, 'tcx> {
-            fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.0 }
-
-            fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
-                if let Some(u) = self.tcx().normalized_cache.borrow().get(&ty).cloned() {
-                    return u;
-                }
-
-                // FIXME(eddyb) should local contexts have a cache too?
-                if let Some(ty_lifted) = self.tcx().lift_to_global(&ty) {
-                    let tcx = self.tcx().global_tcx();
-                    let t_norm = ty_lifted.super_fold_with(&mut RegionEraser(tcx));
-                    tcx.normalized_cache.borrow_mut().insert(ty_lifted, t_norm);
-                    t_norm
-                } else {
-                    ty.super_fold_with(self)
-                }
-            }
-
-            fn fold_binder<T>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T>
-                where T : TypeFoldable<'tcx>
-            {
-                let u = self.tcx().anonymize_late_bound_regions(t);
-                u.super_fold_with(self)
-            }
-
-            fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
-                // because late-bound regions affect subtyping, we can't
-                // erase the bound/free distinction, but we can replace
-                // all free regions with 'erased.
-                //
-                // Note that we *CAN* replace early-bound regions -- the
-                // type system never "sees" those, they get substituted
-                // away. In trans, they will always be erased to 'erased
-                // whenever a substitution occurs.
-                match *r {
-                    ty::ReLateBound(..) => r,
-                    _ => self.tcx().types.re_erased
-                }
-            }
-        }
-    }
-}
-
-///////////////////////////////////////////////////////////////////////////
 // Region shifter
 //
 // Shifts the De Bruijn indices on all escaping bound regions by a
diff --git a/src/librustc/ty/inhabitedness/mod.rs b/src/librustc/ty/inhabitedness/mod.rs
index a829814e090..0072512464a 100644
--- a/src/librustc/ty/inhabitedness/mod.rs
+++ b/src/librustc/ty/inhabitedness/mod.rs
@@ -10,7 +10,7 @@
 
 use util::nodemap::{FxHashMap, FxHashSet};
 use ty::context::TyCtxt;
-use ty::{AdtDef, VariantDef, FieldDef, TyS};
+use ty::{AdtDef, VariantDef, FieldDef, Ty, TyS};
 use ty::{DefId, Substs};
 use ty::{AdtKind, Visibility};
 use ty::TypeVariants::*;
@@ -62,13 +62,95 @@ mod def_id_forest;
 // This code should only compile in modules where the uninhabitedness of Foo is
 // visible.
 
+impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
+    /// Checks whether a type is visibly uninhabited from a particular module.
+    /// # Example
+    /// ```rust
+    /// enum Void {}
+    /// mod a {
+    ///     pub mod b {
+    ///         pub struct SecretlyUninhabited {
+    ///             _priv: !,
+    ///         }
+    ///     }
+    /// }
+    ///
+    /// mod c {
+    ///     pub struct AlsoSecretlyUninhabited {
+    ///         _priv: Void,
+    ///     }
+    ///     mod d {
+    ///     }
+    /// }
+    ///
+    /// struct Foo {
+    ///     x: a::b::SecretlyUninhabited,
+    ///     y: c::AlsoSecretlyUninhabited,
+    /// }
+    /// ```
+    /// In this code, the type `Foo` will only be visibly uninhabited inside the
+    /// modules b, c and d. This effects pattern-matching on `Foo` or types that
+    /// contain `Foo`.
+    ///
+    /// # Example
+    /// ```rust
+    /// let foo_result: Result<T, Foo> = ... ;
+    /// let Ok(t) = foo_result;
+    /// ```
+    /// This code should only compile in modules where the uninhabitedness of Foo is
+    /// visible.
+    pub fn is_ty_uninhabited_from(self, module: DefId, ty: Ty<'tcx>) -> bool {
+        // To check whether this type is uninhabited at all (not just from the
+        // given node) you could check whether the forest is empty.
+        // ```
+        // forest.is_empty()
+        // ```
+        self.ty_inhabitedness_forest(ty).contains(self, module)
+    }
+
+    pub fn is_ty_uninhabited_from_all_modules(self, ty: Ty<'tcx>) -> bool {
+        !self.ty_inhabitedness_forest(ty).is_empty()
+    }
+
+    fn ty_inhabitedness_forest(self, ty: Ty<'tcx>) -> DefIdForest {
+        ty.uninhabited_from(&mut FxHashMap(), self)
+    }
+
+    pub fn is_enum_variant_uninhabited_from(self,
+                                            module: DefId,
+                                            variant: &'tcx VariantDef,
+                                            substs: &'tcx Substs<'tcx>)
+                                            -> bool
+    {
+        self.variant_inhabitedness_forest(variant, substs).contains(self, module)
+    }
+
+    pub fn is_variant_uninhabited_from_all_modules(self,
+                                                   variant: &'tcx VariantDef,
+                                                   substs: &'tcx Substs<'tcx>)
+                                                   -> bool
+    {
+        !self.variant_inhabitedness_forest(variant, substs).is_empty()
+    }
+
+    fn variant_inhabitedness_forest(self, variant: &'tcx VariantDef, substs: &'tcx Substs<'tcx>)
+                                    -> DefIdForest {
+        // Determine the ADT kind:
+        let adt_def_id = self.adt_def_id_of_variant(variant);
+        let adt_kind = self.adt_def(adt_def_id).adt_kind();
+
+        // Compute inhabitedness forest:
+        variant.uninhabited_from(&mut FxHashMap(), self, substs, adt_kind)
+    }
+}
+
 impl<'a, 'gcx, 'tcx> AdtDef {
     /// Calculate the forest of DefIds from which this adt is visibly uninhabited.
-    pub fn uninhabited_from(
-                &self,
-                visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
-                tcx: TyCtxt<'a, 'gcx, 'tcx>,
-                substs: &'tcx Substs<'tcx>) -> DefIdForest
+    fn uninhabited_from(
+        &self,
+        visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
+        tcx: TyCtxt<'a, 'gcx, 'tcx>,
+        substs: &'tcx Substs<'tcx>) -> DefIdForest
     {
         DefIdForest::intersection(tcx, self.variants.iter().map(|v| {
             v.uninhabited_from(visited, tcx, substs, self.adt_kind())
@@ -78,12 +160,12 @@ impl<'a, 'gcx, 'tcx> AdtDef {
 
 impl<'a, 'gcx, 'tcx> VariantDef {
     /// Calculate the forest of DefIds from which this variant is visibly uninhabited.
-    pub fn uninhabited_from(
-                &self,
-                visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
-                tcx: TyCtxt<'a, 'gcx, 'tcx>,
-                substs: &'tcx Substs<'tcx>,
-                adt_kind: AdtKind) -> DefIdForest
+    fn uninhabited_from(
+        &self,
+        visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
+        tcx: TyCtxt<'a, 'gcx, 'tcx>,
+        substs: &'tcx Substs<'tcx>,
+        adt_kind: AdtKind) -> DefIdForest
     {
         match adt_kind {
             AdtKind::Union => {
@@ -107,12 +189,12 @@ impl<'a, 'gcx, 'tcx> VariantDef {
 
 impl<'a, 'gcx, 'tcx> FieldDef {
     /// Calculate the forest of DefIds from which this field is visibly uninhabited.
-    pub fn uninhabited_from(
-                &self,
-                visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
-                tcx: TyCtxt<'a, 'gcx, 'tcx>,
-                substs: &'tcx Substs<'tcx>,
-                is_enum: bool) -> DefIdForest
+    fn uninhabited_from(
+        &self,
+        visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
+        tcx: TyCtxt<'a, 'gcx, 'tcx>,
+        substs: &'tcx Substs<'tcx>,
+        is_enum: bool) -> DefIdForest
     {
         let mut data_uninhabitedness = move || {
             self.ty(tcx, substs).uninhabited_from(visited, tcx)
@@ -138,35 +220,10 @@ impl<'a, 'gcx, 'tcx> FieldDef {
 
 impl<'a, 'gcx, 'tcx> TyS<'tcx> {
     /// Calculate the forest of DefIds from which this type is visibly uninhabited.
-    pub fn uninhabited_from(
-                &self,
-                visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
-                tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest
-    {
-        match tcx.lift_to_global(&self) {
-            Some(global_ty) => {
-                {
-                    let cache = tcx.inhabitedness_cache.borrow();
-                    if let Some(forest) = cache.get(&global_ty) {
-                        return forest.clone();
-                    }
-                }
-                let forest = global_ty.uninhabited_from_inner(visited, tcx);
-                let mut cache = tcx.inhabitedness_cache.borrow_mut();
-                cache.insert(global_ty, forest.clone());
-                forest
-            },
-            None => {
-                let forest = self.uninhabited_from_inner(visited, tcx);
-                forest
-            },
-        }
-    }
-
-    fn uninhabited_from_inner(
-                &self,
-                visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
-                tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest
+    fn uninhabited_from(
+        &self,
+        visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
+        tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest
     {
         match self.sty {
             TyAdt(def, substs) => {
diff --git a/src/librustc/ty/maps/config.rs b/src/librustc/ty/maps/config.rs
index 137039598a5..8f8cda0e0f1 100644
--- a/src/librustc/ty/maps/config.rs
+++ b/src/librustc/ty/maps/config.rs
@@ -29,7 +29,12 @@ pub(super) trait QueryDescription: QueryConfig {
 
 impl<M: QueryConfig<Key=DefId>> QueryDescription for M {
     default fn describe(tcx: TyCtxt, def_id: DefId) -> String {
-        format!("processing `{}`", tcx.item_path_str(def_id))
+        if !tcx.sess.verbose() {
+            format!("processing `{}`", tcx.item_path_str(def_id))
+        } else {
+            let name = unsafe { ::std::intrinsics::type_name::<M>() };
+            format!("processing `{}` applied to `{:?}`", name, def_id)
+        }
     }
 }
 
@@ -70,6 +75,12 @@ impl<'tcx> QueryDescription for queries::super_predicates_of<'tcx> {
     }
 }
 
+impl<'tcx> QueryDescription for queries::erase_regions_ty<'tcx> {
+    fn describe(_tcx: TyCtxt, ty: Ty<'tcx>) -> String {
+        format!("erasing regions from `{:?}`", ty)
+    }
+}
+
 impl<'tcx> QueryDescription for queries::type_param_predicates<'tcx> {
     fn describe(tcx: TyCtxt, (_, def_id): (DefId, DefId)) -> String {
         let id = tcx.hir.as_local_node_id(def_id).unwrap();
@@ -214,6 +225,13 @@ impl<'tcx> QueryDescription for queries::const_is_rvalue_promotable_to_static<'t
     }
 }
 
+impl<'tcx> QueryDescription for queries::rvalue_promotable_map<'tcx> {
+    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
+        format!("checking which parts of `{}` are promotable to static",
+                tcx.item_path_str(def_id))
+    }
+}
+
 impl<'tcx> QueryDescription for queries::is_mir_available<'tcx> {
     fn describe(tcx: TyCtxt, def_id: DefId) -> String {
         format!("checking if item is mir available: `{}`",
diff --git a/src/librustc/ty/maps/mod.rs b/src/librustc/ty/maps/mod.rs
index f54391ebb07..839042bf229 100644
--- a/src/librustc/ty/maps/mod.rs
+++ b/src/librustc/ty/maps/mod.rs
@@ -37,7 +37,7 @@ use ty::{self, CrateInherentImpls, Ty, TyCtxt};
 use ty::layout::{Layout, LayoutError};
 use ty::steal::Steal;
 use ty::subst::Substs;
-use util::nodemap::{DefIdSet, DefIdMap};
+use util::nodemap::{DefIdSet, DefIdMap, ItemLocalMap};
 use util::common::{profq_msg, ProfileQueriesMsg};
 
 use rustc_data_structures::indexed_set::IdxSetBuf;
@@ -231,6 +231,7 @@ define_maps! { <'tcx>
     [] fn is_exported_symbol: IsExportedSymbol(DefId) -> bool,
     [] fn item_body_nested_bodies: ItemBodyNestedBodies(DefId) -> ExternBodyNestedBodies,
     [] fn const_is_rvalue_promotable_to_static: ConstIsRvaluePromotableToStatic(DefId) -> bool,
+    [] fn rvalue_promotable_map: RvaluePromotableMap(DefId) -> Rc<ItemLocalMap<bool>>,
     [] fn is_mir_available: IsMirAvailable(DefId) -> bool,
     [] fn vtable_methods: vtable_methods_node(ty::PolyTraitRef<'tcx>)
                           -> Rc<Vec<Option<(DefId, &'tcx Substs<'tcx>)>>>,
@@ -343,12 +344,21 @@ define_maps! { <'tcx>
 
     [] fn has_copy_closures: HasCopyClosures(CrateNum) -> bool,
     [] fn has_clone_closures: HasCloneClosures(CrateNum) -> bool,
+
+    // Erases regions from `ty` to yield a new type.
+    // Normally you would just use `tcx.erase_regions(&value)`,
+    // however, which uses this query as a kind of cache.
+    [] fn erase_regions_ty: erase_regions_ty(Ty<'tcx>) -> Ty<'tcx>,
 }
 
 //////////////////////////////////////////////////////////////////////
 // These functions are little shims used to find the dep-node for a
 // given query when there is not a *direct* mapping:
 
+fn erase_regions_ty<'tcx>(ty: Ty<'tcx>) -> DepConstructor<'tcx> {
+    DepConstructor::EraseRegionsTy { ty }
+}
+
 fn type_param_predicates<'tcx>((item_id, param_id): (DefId, DefId)) -> DepConstructor<'tcx> {
     DepConstructor::TypeParamPredicates {
         item_id,
diff --git a/src/librustc/ty/maps/plumbing.rs b/src/librustc/ty/maps/plumbing.rs
index 4e301342ee0..343ac049ea2 100644
--- a/src/librustc/ty/maps/plumbing.rs
+++ b/src/librustc/ty/maps/plumbing.rs
@@ -701,6 +701,7 @@ pub fn force_from_dep_node<'a, 'gcx, 'lcx>(tcx: TyCtxt<'a, 'gcx, 'lcx>,
         DepKind::CompileCodegenUnit |
         DepKind::FulfillObligation |
         DepKind::VtableMethods |
+        DepKind::EraseRegionsTy |
 
         // These are just odd
         DepKind::Null |
@@ -774,6 +775,7 @@ pub fn force_from_dep_node<'a, 'gcx, 'lcx>(tcx: TyCtxt<'a, 'gcx, 'lcx>,
         DepKind::ConstIsRvaluePromotableToStatic => {
             force!(const_is_rvalue_promotable_to_static, def_id!());
         }
+        DepKind::RvaluePromotableMap => { force!(rvalue_promotable_map, def_id!()); }
         DepKind::ImplParent => { force!(impl_parent, def_id!()); }
         DepKind::TraitOfItem => { force!(trait_of_item, def_id!()); }
         DepKind::IsExportedSymbol => { force!(is_exported_symbol, def_id!()); }
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index c4f526d8014..129c81c5cd6 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -18,6 +18,7 @@ pub use self::fold::TypeFoldable;
 use hir::{map as hir_map, FreevarMap, TraitMap};
 use hir::def::{Def, CtorKind, ExportMap};
 use hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX, LOCAL_CRATE};
+use hir::map::DefPathData;
 use ich::StableHashingContext;
 use middle::const_val::ConstVal;
 use middle::lang_items::{FnTraitLangItem, FnMutTraitLangItem, FnOnceTraitLangItem};
@@ -89,6 +90,7 @@ pub mod adjustment;
 pub mod binding;
 pub mod cast;
 pub mod error;
+mod erase_regions;
 pub mod fast_reject;
 pub mod fold;
 pub mod inhabitedness;
@@ -2232,6 +2234,20 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         }
     }
 
+    /// Given a `VariantDef`, returns the def-id of the `AdtDef` of which it is a part.
+    pub fn adt_def_id_of_variant(self, variant_def: &'tcx VariantDef) -> DefId {
+        let def_key = self.def_key(variant_def.did);
+        match def_key.disambiguated_data.data {
+            // for enum variants and tuple structs, the def-id of the ADT itself
+            // is the *parent* of the variant
+            DefPathData::EnumVariant(..) | DefPathData::StructCtor =>
+                DefId { krate: variant_def.did.krate, index: def_key.parent.unwrap() },
+
+            // otherwise, for structs and unions, they share a def-id
+            _ => variant_def.did,
+        }
+    }
+
     pub fn item_name(self, id: DefId) -> InternedString {
         if let Some(id) = self.hir.as_local_node_id(id) {
             self.hir.name(id).as_str()
@@ -2560,6 +2576,7 @@ fn original_crate_name<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 pub fn provide(providers: &mut ty::maps::Providers) {
     util::provide(providers);
     context::provide(providers);
+    erase_regions::provide(providers);
     *providers = ty::maps::Providers {
         associated_item,
         associated_item_def_ids,
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 10e1286465d..064627c21bf 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -24,7 +24,6 @@ use std::cmp::Ordering;
 use syntax::abi;
 use syntax::ast::{self, Name};
 use syntax::symbol::keywords;
-use util::nodemap::FxHashMap;
 
 use serialize;
 
@@ -1070,54 +1069,6 @@ impl<'a, 'gcx, 'tcx> TyS<'tcx> {
         }
     }
 
-    /// Checks whether a type is visibly uninhabited from a particular module.
-    /// # Example
-    /// ```rust
-    /// enum Void {}
-    /// mod a {
-    ///     pub mod b {
-    ///         pub struct SecretlyUninhabited {
-    ///             _priv: !,
-    ///         }
-    ///     }
-    /// }
-    ///
-    /// mod c {
-    ///     pub struct AlsoSecretlyUninhabited {
-    ///         _priv: Void,
-    ///     }
-    ///     mod d {
-    ///     }
-    /// }
-    ///
-    /// struct Foo {
-    ///     x: a::b::SecretlyUninhabited,
-    ///     y: c::AlsoSecretlyUninhabited,
-    /// }
-    /// ```
-    /// In this code, the type `Foo` will only be visibly uninhabited inside the
-    /// modules b, c and d. This effects pattern-matching on `Foo` or types that
-    /// contain `Foo`.
-    ///
-    /// # Example
-    /// ```rust
-    /// let foo_result: Result<T, Foo> = ... ;
-    /// let Ok(t) = foo_result;
-    /// ```
-    /// This code should only compile in modules where the uninhabitedness of Foo is
-    /// visible.
-    pub fn is_uninhabited_from(&self, module: DefId, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> bool {
-        let mut visited = FxHashMap::default();
-        let forest = self.uninhabited_from(&mut visited, tcx);
-
-        // To check whether this type is uninhabited at all (not just from the
-        // given node) you could check whether the forest is empty.
-        // ```
-        // forest.is_empty()
-        // ```
-        forest.contains(tcx, module)
-    }
-
     pub fn is_primitive(&self) -> bool {
         match self.sty {
             TyBool | TyChar | TyInt(_) | TyUint(_) | TyFloat(_) => true,
diff --git a/src/librustc_borrowck/borrowck/check_loans.rs b/src/librustc_borrowck/borrowck/check_loans.rs
index 0e9fb583407..6fd9ff4012e 100644
--- a/src/librustc_borrowck/borrowck/check_loans.rs
+++ b/src/librustc_borrowck/borrowck/check_loans.rs
@@ -206,7 +206,13 @@ pub fn check_loans<'a, 'b, 'c, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
         all_loans,
         param_env,
     };
-    euv::ExprUseVisitor::new(&mut clcx, bccx.tcx, param_env, &bccx.region_scope_tree, bccx.tables)
+    let rvalue_promotable_map = bccx.tcx.rvalue_promotable_map(def_id);
+    euv::ExprUseVisitor::new(&mut clcx,
+                             bccx.tcx,
+                             param_env,
+                             &bccx.region_scope_tree,
+                             bccx.tables,
+                             Some(rvalue_promotable_map))
         .consume_body(body);
 }
 
diff --git a/src/librustc_borrowck/borrowck/gather_loans/mod.rs b/src/librustc_borrowck/borrowck/gather_loans/mod.rs
index bb39e8ad2e6..8654f2a50e4 100644
--- a/src/librustc_borrowck/borrowck/gather_loans/mod.rs
+++ b/src/librustc_borrowck/borrowck/gather_loans/mod.rs
@@ -48,7 +48,13 @@ pub fn gather_loans_in_fn<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
         move_error_collector: move_error::MoveErrorCollector::new(),
     };
 
-    euv::ExprUseVisitor::new(&mut glcx, bccx.tcx, param_env, &bccx.region_scope_tree, bccx.tables)
+    let rvalue_promotable_map = bccx.tcx.rvalue_promotable_map(def_id);
+    euv::ExprUseVisitor::new(&mut glcx,
+                             bccx.tcx,
+                             param_env,
+                             &bccx.region_scope_tree,
+                             bccx.tables,
+                             Some(rvalue_promotable_map))
         .consume_body(bccx.body);
 
     glcx.report_potential_errors();
diff --git a/src/librustc_const_eval/_match.rs b/src/librustc_const_eval/_match.rs
index b836b71e74b..08f3b0a4c5f 100644
--- a/src/librustc_const_eval/_match.rs
+++ b/src/librustc_const_eval/_match.rs
@@ -25,7 +25,7 @@ use pattern::{PatternFoldable, PatternFolder};
 
 use rustc::hir::def_id::DefId;
 use rustc::hir::RangeEnd;
-use rustc::ty::{self, AdtKind, Ty, TyCtxt, TypeFoldable};
+use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
 
 use rustc::mir::Field;
 use rustc::util::common::ErrorReported;
@@ -202,7 +202,7 @@ impl<'a, 'tcx> MatchCheckCtxt<'a, 'tcx> {
 
     fn is_uninhabited(&self, ty: Ty<'tcx>) -> bool {
         if self.tcx.sess.features.borrow().never_type {
-            ty.is_uninhabited_from(self.module, self.tcx)
+            self.tcx.is_ty_uninhabited_from(self.module, ty)
         } else {
             false
         }
@@ -210,13 +210,11 @@ impl<'a, 'tcx> MatchCheckCtxt<'a, 'tcx> {
 
     fn is_variant_uninhabited(&self,
                               variant: &'tcx ty::VariantDef,
-                              substs: &'tcx ty::subst::Substs<'tcx>) -> bool
+                              substs: &'tcx ty::subst::Substs<'tcx>)
+                              -> bool
     {
         if self.tcx.sess.features.borrow().never_type {
-            let forest = variant.uninhabited_from(
-                &mut FxHashMap::default(), self.tcx, substs, AdtKind::Enum
-            );
-            forest.contains(self.tcx, self.module)
+            self.tcx.is_enum_variant_uninhabited_from(self.module, variant, substs)
         } else {
             false
         }
diff --git a/src/librustc_const_eval/check_match.rs b/src/librustc_const_eval/check_match.rs
index 0339969f2b4..e6a04c9c57a 100644
--- a/src/librustc_const_eval/check_match.rs
+++ b/src/librustc_const_eval/check_match.rs
@@ -192,7 +192,7 @@ impl<'a, 'tcx> MatchVisitor<'a, 'tcx> {
             let module = self.tcx.hir.get_module_parent(scrut.id);
             if inlined_arms.is_empty() {
                 let scrutinee_is_uninhabited = if self.tcx.sess.features.borrow().never_type {
-                    pat_ty.is_uninhabited_from(module, self.tcx)
+                    self.tcx.is_ty_uninhabited_from(module, pat_ty)
                 } else {
                     self.conservative_is_uninhabited(pat_ty)
                 };
@@ -526,7 +526,7 @@ fn check_for_mutation_in_guard(cx: &MatchVisitor, guard: &hir::Expr) {
     let mut checker = MutationChecker {
         cx,
     };
-    ExprUseVisitor::new(&mut checker, cx.tcx, cx.param_env, cx.region_scope_tree, cx.tables)
+    ExprUseVisitor::new(&mut checker, cx.tcx, cx.param_env, cx.region_scope_tree, cx.tables, None)
         .walk_expr(guard);
 }
 
diff --git a/src/librustc_driver/driver.rs b/src/librustc_driver/driver.rs
index ad6f7fbf111..7dbf93da385 100644
--- a/src/librustc_driver/driver.rs
+++ b/src/librustc_driver/driver.rs
@@ -38,7 +38,7 @@ use rustc_typeck as typeck;
 use rustc_privacy;
 use rustc_plugin::registry::Registry;
 use rustc_plugin as plugin;
-use rustc_passes::{ast_validation, no_asm, loops, consts, static_recursion, hir_stats};
+use rustc_passes::{self, ast_validation, no_asm, loops, consts, static_recursion, hir_stats};
 use rustc_const_eval::{self, check_match};
 use super::Compilation;
 use ::DefaultTransCrate;
@@ -973,6 +973,7 @@ pub fn phase_3_run_analysis_passes<'tcx, F, R>(sess: &'tcx Session,
     traits::provide(&mut local_providers);
     reachable::provide(&mut local_providers);
     rustc_const_eval::provide(&mut local_providers);
+    rustc_passes::provide(&mut local_providers);
     middle::region::provide(&mut local_providers);
     cstore::provide_local(&mut local_providers);
     lint::provide(&mut local_providers);
diff --git a/src/librustc_metadata/astencode.rs b/src/librustc_metadata/astencode.rs
index d9ab2562eff..722d0cad238 100644
--- a/src/librustc_metadata/astencode.rs
+++ b/src/librustc_metadata/astencode.rs
@@ -56,7 +56,8 @@ impl<'a, 'b, 'tcx> IsolatedEncoder<'a, 'b, 'tcx> {
         };
 
         let lazy_body = self.lazy(body);
-        let tables = self.tcx.body_tables(body_id);
+        let body_owner_def_id = self.tcx.hir.body_owner_def_id(body_id);
+        let tables = self.tcx.typeck_tables_of(body_owner_def_id);
         let lazy_tables = self.lazy(tables);
 
         let mut visitor = NestedBodyCollector {
@@ -67,7 +68,7 @@ impl<'a, 'b, 'tcx> IsolatedEncoder<'a, 'b, 'tcx> {
         let lazy_nested_bodies = self.lazy_seq_ref_from_slice(&visitor.bodies_found);
 
         let rvalue_promotable_to_static =
-            self.tcx.rvalue_promotable_to_static.borrow()[&body.value.id];
+            self.tcx.const_is_rvalue_promotable_to_static(body_owner_def_id);
 
         self.lazy(&Ast {
             body: lazy_body,
diff --git a/src/librustc_mir/build/matches/simplify.rs b/src/librustc_mir/build/matches/simplify.rs
index 6e3eef57352..9b3f16f1ab4 100644
--- a/src/librustc_mir/build/matches/simplify.rs
+++ b/src/librustc_mir/build/matches/simplify.rs
@@ -26,7 +26,6 @@ use build::{BlockAnd, BlockAndExtension, Builder};
 use build::matches::{Binding, MatchPair, Candidate};
 use hair::*;
 use rustc::mir::*;
-use rustc_data_structures::fx::FxHashMap;
 
 use std::mem;
 
@@ -102,12 +101,7 @@ impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> {
                 if self.hir.tcx().sess.features.borrow().never_type {
                     let irrefutable = adt_def.variants.iter().enumerate().all(|(i, v)| {
                         i == variant_index || {
-                            let mut visited = FxHashMap::default();
-                            let node_set = v.uninhabited_from(&mut visited,
-                                                              self.hir.tcx(),
-                                                              substs,
-                                                              adt_def.adt_kind());
-                            !node_set.is_empty()
+                            self.hir.tcx().is_variant_uninhabited_from_all_modules(v, substs)
                         }
                     });
                     if irrefutable {
diff --git a/src/librustc_passes/consts.rs b/src/librustc_passes/consts.rs
index 547d63fc3d4..d3202ba4ab5 100644
--- a/src/librustc_passes/consts.rs
+++ b/src/librustc_passes/consts.rs
@@ -39,20 +39,79 @@ use rustc::middle::mem_categorization as mc;
 use rustc::middle::mem_categorization::Categorization;
 use rustc::mir::transform::MirSource;
 use rustc::ty::{self, Ty, TyCtxt};
+use rustc::ty::maps::{queries, Providers};
 use rustc::ty::subst::Substs;
 use rustc::traits::Reveal;
 use rustc::util::common::ErrorReported;
-use rustc::util::nodemap::NodeSet;
+use rustc::util::nodemap::{ItemLocalMap, NodeSet};
 use rustc::lint::builtin::CONST_ERR;
-
 use rustc::hir::{self, PatKind, RangeEnd};
+use std::rc::Rc;
 use syntax::ast;
 use syntax_pos::{Span, DUMMY_SP};
 use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
 
-use std::collections::hash_map::Entry;
 use std::cmp::Ordering;
 
+pub fn provide(providers: &mut Providers) {
+    *providers = Providers {
+        rvalue_promotable_map,
+        const_is_rvalue_promotable_to_static,
+        ..*providers
+    };
+}
+
+pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
+    for &body_id in &tcx.hir.krate().body_ids {
+        let def_id = tcx.hir.body_owner_def_id(body_id);
+        tcx.const_is_rvalue_promotable_to_static(def_id);
+    }
+    tcx.sess.abort_if_errors();
+}
+
+fn const_is_rvalue_promotable_to_static<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
+                                                  def_id: DefId)
+                                                  -> bool
+{
+    assert!(def_id.is_local());
+
+    let node_id = tcx.hir.as_local_node_id(def_id)
+                     .expect("rvalue_promotable_map invoked with non-local def-id");
+    let body_id = tcx.hir.body_owned_by(node_id);
+    let body_hir_id = tcx.hir.node_to_hir_id(body_id.node_id);
+    tcx.rvalue_promotable_map(def_id).contains_key(&body_hir_id.local_id)
+}
+
+fn rvalue_promotable_map<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
+                                   def_id: DefId)
+                                   -> Rc<ItemLocalMap<bool>>
+{
+    let outer_def_id = tcx.closure_base_def_id(def_id);
+    if outer_def_id != def_id {
+        return tcx.rvalue_promotable_map(outer_def_id);
+    }
+
+    let mut visitor = CheckCrateVisitor {
+        tcx,
+        tables: &ty::TypeckTables::empty(None),
+        in_fn: false,
+        in_static: false,
+        promotable: false,
+        mut_rvalue_borrows: NodeSet(),
+        param_env: ty::ParamEnv::empty(Reveal::UserFacing),
+        identity_substs: Substs::empty(),
+        result_map: ItemLocalMap(),
+    };
+
+    // `def_id` should be a `Body` owner
+    let node_id = tcx.hir.as_local_node_id(def_id)
+                     .expect("rvalue_promotable_map invoked with non-local def-id");
+    let body_id = tcx.hir.body_owned_by(node_id);
+    visitor.visit_nested_body(body_id);
+
+    Rc::new(visitor.result_map)
+}
+
 struct CheckCrateVisitor<'a, 'tcx: 'a> {
     tcx: TyCtxt<'a, 'tcx, 'tcx>,
     in_fn: bool,
@@ -62,6 +121,7 @@ struct CheckCrateVisitor<'a, 'tcx: 'a> {
     param_env: ty::ParamEnv<'tcx>,
     identity_substs: &'tcx Substs<'tcx>,
     tables: &'a ty::TypeckTables<'tcx>,
+    result_map: ItemLocalMap<bool>,
 }
 
 impl<'a, 'gcx> CheckCrateVisitor<'a, 'gcx> {
@@ -109,18 +169,11 @@ impl<'a, 'gcx> CheckCrateVisitor<'a, 'gcx> {
 
 impl<'a, 'tcx> Visitor<'tcx> for CheckCrateVisitor<'a, 'tcx> {
     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
+        // note that we *do* visit nested bodies, because we override `visit_nested_body` below
         NestedVisitorMap::None
     }
 
     fn visit_nested_body(&mut self, body_id: hir::BodyId) {
-        match self.tcx.rvalue_promotable_to_static.borrow_mut().entry(body_id.node_id) {
-            Entry::Occupied(_) => return,
-            Entry::Vacant(entry) => {
-                // Prevent infinite recursion on re-entry.
-                entry.insert(false);
-            }
-        }
-
         let item_id = self.tcx.hir.body_owner(body_id);
         let item_def_id = self.tcx.hir.local_def_id(item_id);
 
@@ -151,7 +204,7 @@ impl<'a, 'tcx> Visitor<'tcx> for CheckCrateVisitor<'a, 'tcx> {
         let tcx = self.tcx;
         let param_env = self.param_env;
         let region_scope_tree = self.tcx.region_scope_tree(item_def_id);
-        euv::ExprUseVisitor::new(self, tcx, param_env, &region_scope_tree, self.tables)
+        euv::ExprUseVisitor::new(self, tcx, param_env, &region_scope_tree, self.tables, None)
             .consume_body(body);
 
         self.visit_body(body);
@@ -270,7 +323,7 @@ impl<'a, 'tcx> Visitor<'tcx> for CheckCrateVisitor<'a, 'tcx> {
             }
         }
 
-        self.tcx.rvalue_promotable_to_static.borrow_mut().insert(ex.id, self.promotable);
+        self.result_map.insert(ex.hir_id.local_id, self.promotable);
         self.promotable &= outer;
     }
 }
@@ -371,16 +424,17 @@ fn check_expr<'a, 'tcx>(v: &mut CheckCrateVisitor<'a, 'tcx>, e: &hir::Expr, node
                     let promotable = if v.tcx.trait_of_item(did).is_some() {
                         // Don't peek inside trait associated constants.
                         false
-                    } else if let Some(node_id) = v.tcx.hir.as_local_node_id(did) {
-                        match v.tcx.hir.maybe_body_owned_by(node_id) {
-                            Some(body) => {
-                                v.visit_nested_body(body);
-                                v.tcx.rvalue_promotable_to_static.borrow()[&body.node_id]
-                            }
-                            None => false
-                        }
                     } else {
-                        v.tcx.const_is_rvalue_promotable_to_static(did)
+                        queries::const_is_rvalue_promotable_to_static::try_get(v.tcx, e.span, did)
+                            .unwrap_or_else(|mut err| {
+                                // A cycle between constants ought to be reported elsewhere.
+                                err.cancel();
+                                v.tcx.sess.delay_span_bug(
+                                    e.span,
+                                    &format!("cycle encountered during const qualification: {:?}",
+                                             did));
+                                false
+                            })
                     };
 
                     // Just in case the type is more specific than the definition,
@@ -513,20 +567,6 @@ fn check_adjustments<'a, 'tcx>(v: &mut CheckCrateVisitor<'a, 'tcx>, e: &hir::Exp
     }
 }
 
-pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
-    tcx.hir.krate().visit_all_item_likes(&mut CheckCrateVisitor {
-        tcx,
-        tables: &ty::TypeckTables::empty(None),
-        in_fn: false,
-        in_static: false,
-        promotable: false,
-        mut_rvalue_borrows: NodeSet(),
-        param_env: ty::ParamEnv::empty(Reveal::UserFacing),
-        identity_substs: Substs::empty(),
-    }.as_deep_visitor());
-    tcx.sess.abort_if_errors();
-}
-
 impl<'a, 'gcx, 'tcx> euv::Delegate<'tcx> for CheckCrateVisitor<'a, 'gcx> {
     fn consume(&mut self,
                _consume_id: ast::NodeId,
diff --git a/src/librustc_passes/lib.rs b/src/librustc_passes/lib.rs
index 28b99e1185b..9a150abea66 100644
--- a/src/librustc_passes/lib.rs
+++ b/src/librustc_passes/lib.rs
@@ -33,6 +33,8 @@ extern crate syntax;
 extern crate syntax_pos;
 extern crate rustc_errors as errors;
 
+use rustc::ty::maps::Providers;
+
 mod diagnostics;
 
 pub mod ast_validation;
@@ -44,3 +46,7 @@ pub mod no_asm;
 pub mod static_recursion;
 
 __build_diagnostic_array! { librustc_passes, DIAGNOSTICS }
+
+pub fn provide(providers: &mut Providers) {
+    consts::provide(providers);
+}
diff --git a/src/test/run-pass/issue-44402.rs b/src/test/run-pass/issue-44402.rs
new file mode 100644
index 00000000000..244aa65a3d5
--- /dev/null
+++ b/src/test/run-pass/issue-44402.rs
@@ -0,0 +1,36 @@
+// Copyright 2016 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.
+
+#![feature(never_type)]
+
+// Regression test for inhabitedness check. The old
+// cache used to cause us to incorrectly decide
+// that `test_b` was invalid.
+
+struct Foo {
+    field1: !,
+    field2: Option<&'static Bar>,
+}
+
+struct Bar {
+    field1: &'static Foo
+}
+
+fn test_a() {
+    let x: Option<Foo> = None;
+    match x { None => () }
+}
+
+fn test_b() {
+    let x: Option<Bar> = None;
+    match x { None => () }
+}
+
+fn main() { }
diff --git a/src/tools/toolstate.toml b/src/tools/toolstate.toml
index e62597c5216..f1684f4c5ac 100644
--- a/src/tools/toolstate.toml
+++ b/src/tools/toolstate.toml
@@ -26,7 +26,7 @@
 miri = "Broken"
 
 # ping @Manishearth @llogiq @mcarton @oli-obk
-clippy = "Compiling"
+clippy = "Broken"
 
 # ping @nrc
 rls = "Testing"