resolved conflict with upstream commit

63 files changed, 1644 insertions, 1284 deletions

diff --git a/src/librustc/Cargo.toml b/src/librustc/Cargo.toml
index 357ebb89fb6..af108188ce0 100644
--- a/src/librustc/Cargo.toml
+++ b/src/librustc/Cargo.toml
@@ -19,7 +19,6 @@ log = { version = "0.4", features = ["release_max_level_info", "std"] }
 proc_macro = { path = "../libproc_macro" }
 rustc_apfloat = { path = "../librustc_apfloat" }
 rustc_target = { path = "../librustc_target" }
-rustc_const_math = { path = "../librustc_const_math" }
 rustc_data_structures = { path = "../librustc_data_structures" }
 rustc_errors = { path = "../librustc_errors" }
 serialize = { path = "../libserialize" }
diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index 18bf54297af..e4f432e7caf 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -70,7 +70,8 @@ use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
 use std::fmt;
 use std::hash::Hash;
 use syntax_pos::symbol::InternedString;
-use traits::query::{CanonicalProjectionGoal, CanonicalTyGoal};
+use traits::query::{CanonicalProjectionGoal,
+                    CanonicalTyGoal, CanonicalPredicateGoal};
 use ty::{TyCtxt, Instance, InstanceDef, ParamEnv, ParamEnvAnd, PolyTraitRef, Ty};
 use ty::subst::Substs;
 
@@ -643,6 +644,7 @@ define_dep_nodes!( <'tcx>
     [] NormalizeProjectionTy(CanonicalProjectionGoal<'tcx>),
     [] NormalizeTyAfterErasingRegions(ParamEnvAnd<'tcx, Ty<'tcx>>),
     [] DropckOutlives(CanonicalTyGoal<'tcx>),
+    [] EvaluateObligation(CanonicalPredicateGoal<'tcx>),
 
     [] SubstituteNormalizeAndTestPredicates { key: (DefId, &'tcx Substs<'tcx>) },
 
diff --git a/src/librustc/hir/check_attr.rs b/src/librustc/hir/check_attr.rs
index 956cd17f38f..24a1256c9d3 100644
--- a/src/librustc/hir/check_attr.rs
+++ b/src/librustc/hir/check_attr.rs
@@ -30,6 +30,8 @@ enum Target {
     ForeignMod,
     Expression,
     Statement,
+    Closure,
+    Static,
     Other,
 }
 
@@ -42,6 +44,7 @@ impl Target {
             hir::ItemEnum(..) => Target::Enum,
             hir::ItemConst(..) => Target::Const,
             hir::ItemForeignMod(..) => Target::ForeignMod,
+            hir::ItemStatic(..) => Target::Static,
             _ => Target::Other,
         }
     }
@@ -101,16 +104,17 @@ impl<'a, 'tcx> CheckAttrVisitor<'a, 'tcx> {
         }
 
         self.check_repr(item, target);
+        self.check_used(item, target);
     }
 
-    /// Check if an `#[inline]` is applied to a function.
+    /// Check if an `#[inline]` is applied to a function or a closure.
     fn check_inline(&self, attr: &hir::Attribute, span: &Span, target: Target) {
-        if target != Target::Fn {
+        if target != Target::Fn && target != Target::Closure {
             struct_span_err!(self.tcx.sess,
                              attr.span,
                              E0518,
-                             "attribute should be applied to function")
-                .span_label(*span, "not a function")
+                             "attribute should be applied to function or closure")
+                .span_label(*span, "not a function or closure")
                 .emit();
         }
     }
@@ -149,10 +153,7 @@ impl<'a, 'tcx> CheckAttrVisitor<'a, 'tcx> {
         // ```
         let hints: Vec<_> = item.attrs
             .iter()
-            .filter(|attr| match attr.name() {
-                Some(name) => name == "repr",
-                None => false,
-            })
+            .filter(|attr| attr.name() == "repr")
             .filter_map(|attr| attr.meta_item_list())
             .flat_map(|hints| hints)
             .collect();
@@ -286,9 +287,13 @@ impl<'a, 'tcx> CheckAttrVisitor<'a, 'tcx> {
     }
 
     fn check_expr_attributes(&self, expr: &hir::Expr) {
+        let target = match expr.node {
+            hir::ExprClosure(..) => Target::Closure,
+            _ => Target::Expression,
+        };
         for attr in expr.attrs.iter() {
             if attr.check_name("inline") {
-                self.check_inline(attr, &expr.span, Target::Expression);
+                self.check_inline(attr, &expr.span, target);
             }
             if attr.check_name("repr") {
                 self.emit_repr_error(
@@ -300,6 +305,15 @@ impl<'a, 'tcx> CheckAttrVisitor<'a, 'tcx> {
             }
         }
     }
+
+    fn check_used(&self, item: &hir::Item, target: Target) {
+        for attr in &item.attrs {
+            if attr.name() == "used" && target != Target::Static {
+                self.tcx.sess
+                    .span_err(attr.span, "attribute must be applied to a `static` variable");
+            }
+        }
+    }
 }
 
 impl<'a, 'tcx> Visitor<'tcx> for CheckAttrVisitor<'a, 'tcx> {
diff --git a/src/librustc/hir/intravisit.rs b/src/librustc/hir/intravisit.rs
index 62f3f9f4486..3e5dcee113a 100644
--- a/src/librustc/hir/intravisit.rs
+++ b/src/librustc/hir/intravisit.rs
@@ -404,7 +404,7 @@ pub fn walk_local<'v, V: Visitor<'v>>(visitor: &mut V, local: &'v Local) {
     // Intentionally visiting the expr first - the initialization expr
     // dominates the local's definition.
     walk_list!(visitor, visit_expr, &local.init);
-
+    walk_list!(visitor, visit_attribute, local.attrs.iter());
     visitor.visit_id(local.id);
     visitor.visit_pat(&local.pat);
     walk_list!(visitor, visit_ty, &local.ty);
@@ -731,6 +731,7 @@ pub fn walk_generic_param<'v, V: Visitor<'v>>(visitor: &mut V, param: &'v Generi
             visitor.visit_name(ty_param.span, ty_param.name);
             walk_list!(visitor, visit_ty_param_bound, &ty_param.bounds);
             walk_list!(visitor, visit_ty, &ty_param.default);
+            walk_list!(visitor, visit_attribute, ty_param.attrs.iter());
         }
     }
 }
diff --git a/src/librustc/hir/lowering.rs b/src/librustc/hir/lowering.rs
index 4023521147e..51f0c1d7047 100644
--- a/src/librustc/hir/lowering.rs
+++ b/src/librustc/hir/lowering.rs
@@ -655,7 +655,7 @@ impl<'a> LoweringContext<'a> {
                 self.resolver.definitions().create_def_with_parent(
                     parent_id.index,
                     def_node_id,
-                    DefPathData::LifetimeDef(str_name),
+                    DefPathData::LifetimeDef(str_name.as_interned_str()),
                     DefIndexAddressSpace::High,
                     Mark::root(),
                     span,
@@ -1302,7 +1302,7 @@ impl<'a> LoweringContext<'a> {
                     self.context.resolver.definitions().create_def_with_parent(
                         self.parent,
                         def_node_id,
-                        DefPathData::LifetimeDef(name.name().as_str()),
+                        DefPathData::LifetimeDef(name.name().as_interned_str()),
                         DefIndexAddressSpace::High,
                         Mark::root(),
                         lifetime.span,
@@ -3119,6 +3119,20 @@ impl<'a> LoweringContext<'a> {
             ExprKind::Index(ref el, ref er) => {
                 hir::ExprIndex(P(self.lower_expr(el)), P(self.lower_expr(er)))
             }
+            // Desugar `<start>..=<end>` to `std::ops::RangeInclusive::new(<start>, <end>)`
+            ExprKind::Range(Some(ref e1), Some(ref e2), RangeLimits::Closed) => {
+                // FIXME: Use e.span directly after RangeInclusive::new() is stabilized in stage0.
+                let span = self.allow_internal_unstable(CompilerDesugaringKind::DotFill, e.span);
+                let id = self.next_id();
+                let e1 = self.lower_expr(e1);
+                let e2 = self.lower_expr(e2);
+                let ty_path = P(self.std_path(span, &["ops", "RangeInclusive"], false));
+                let ty = self.ty_path(id, span, hir::QPath::Resolved(None, ty_path));
+                let new_seg = P(hir::PathSegment::from_name(Symbol::intern("new")));
+                let new_path = hir::QPath::TypeRelative(ty, new_seg);
+                let new = P(self.expr(span, hir::ExprPath(new_path), ThinVec::new()));
+                hir::ExprCall(new, hir_vec![e1, e2])
+            }
             ExprKind::Range(ref e1, ref e2, lims) => {
                 use syntax::ast::RangeLimits::*;
 
@@ -3128,7 +3142,7 @@ impl<'a> LoweringContext<'a> {
                     (&None, &Some(..), HalfOpen) => "RangeTo",
                     (&Some(..), &Some(..), HalfOpen) => "Range",
                     (&None, &Some(..), Closed) => "RangeToInclusive",
-                    (&Some(..), &Some(..), Closed) => "RangeInclusive",
+                    (&Some(..), &Some(..), Closed) => unreachable!(),
                     (_, &None, Closed) => self.diagnostic()
                         .span_fatal(e.span, "inclusive range with no end")
                         .raise(),
@@ -4107,15 +4121,13 @@ impl<'a> LoweringContext<'a> {
     }
 
     fn maybe_lint_bare_trait(&self, span: Span, id: NodeId, is_global: bool) {
-        if self.sess.features_untracked().dyn_trait {
-            self.sess.buffer_lint_with_diagnostic(
-                builtin::BARE_TRAIT_OBJECT,
-                id,
-                span,
-                "trait objects without an explicit `dyn` are deprecated",
-                builtin::BuiltinLintDiagnostics::BareTraitObject(span, is_global),
-            )
-        }
+        self.sess.buffer_lint_with_diagnostic(
+            builtin::BARE_TRAIT_OBJECT,
+            id,
+            span,
+            "trait objects without an explicit `dyn` are deprecated",
+            builtin::BuiltinLintDiagnostics::BareTraitObject(span, is_global),
+        )
     }
 
     fn wrap_in_try_constructor(
diff --git a/src/librustc/hir/map/def_collector.rs b/src/librustc/hir/map/def_collector.rs
index bfe21549e45..ebd8e623582 100644
--- a/src/librustc/hir/map/def_collector.rs
+++ b/src/librustc/hir/map/def_collector.rs
@@ -107,18 +107,18 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
         // information we encapsulate into
         let def_data = match i.node {
             ItemKind::Impl(..) => DefPathData::Impl,
-            ItemKind::Trait(..) => DefPathData::Trait(i.ident.name.as_str()),
+            ItemKind::Trait(..) => DefPathData::Trait(i.ident.name.as_interned_str()),
             ItemKind::Enum(..) | ItemKind::Struct(..) | ItemKind::Union(..) |
             ItemKind::TraitAlias(..) |
             ItemKind::ExternCrate(..) | ItemKind::ForeignMod(..) | ItemKind::Ty(..) =>
-                DefPathData::TypeNs(i.ident.name.as_str()),
+                DefPathData::TypeNs(i.ident.name.as_interned_str()),
             ItemKind::Mod(..) if i.ident == keywords::Invalid.ident() => {
                 return visit::walk_item(self, i);
             }
-            ItemKind::Mod(..) => DefPathData::Module(i.ident.name.as_str()),
+            ItemKind::Mod(..) => DefPathData::Module(i.ident.name.as_interned_str()),
             ItemKind::Static(..) | ItemKind::Const(..) | ItemKind::Fn(..) =>
-                DefPathData::ValueNs(i.ident.name.as_str()),
-            ItemKind::MacroDef(..) => DefPathData::MacroDef(i.ident.name.as_str()),
+                DefPathData::ValueNs(i.ident.name.as_interned_str()),
+            ItemKind::MacroDef(..) => DefPathData::MacroDef(i.ident.name.as_interned_str()),
             ItemKind::Mac(..) => return self.visit_macro_invoc(i.id, false),
             ItemKind::GlobalAsm(..) => DefPathData::Misc,
             ItemKind::Use(..) => {
@@ -133,7 +133,8 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
                     for v in &enum_definition.variants {
                         let variant_def_index =
                             this.create_def(v.node.data.id(),
-                                            DefPathData::EnumVariant(v.node.ident.name.as_str()),
+                                            DefPathData::EnumVariant(v.node.ident
+                                                                      .name.as_interned_str()),
                                             REGULAR_SPACE,
                                             v.span);
                         this.with_parent(variant_def_index, |this| {
@@ -141,7 +142,7 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
                                 let name = field.ident.map(|ident| ident.name)
                                     .unwrap_or_else(|| Symbol::intern(&index.to_string()));
                                 this.create_def(field.id,
-                                                DefPathData::Field(name.as_str()),
+                                                DefPathData::Field(name.as_interned_str()),
                                                 REGULAR_SPACE,
                                                 field.span);
                             }
@@ -165,7 +166,7 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
                         let name = field.ident.map(|ident| ident.name)
                             .unwrap_or_else(|| Symbol::intern(&index.to_string()));
                         this.create_def(field.id,
-                                        DefPathData::Field(name.as_str()),
+                                        DefPathData::Field(name.as_interned_str()),
                                         REGULAR_SPACE,
                                         field.span);
                     }
@@ -187,7 +188,7 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
         }
 
         let def = self.create_def(foreign_item.id,
-                                  DefPathData::ValueNs(foreign_item.ident.name.as_str()),
+                                  DefPathData::ValueNs(foreign_item.ident.name.as_interned_str()),
                                   REGULAR_SPACE,
                                   foreign_item.span);
 
@@ -201,7 +202,7 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
             GenericParam::Lifetime(ref lifetime_def) => {
                 self.create_def(
                     lifetime_def.lifetime.id,
-                    DefPathData::LifetimeDef(lifetime_def.lifetime.ident.name.as_str()),
+                    DefPathData::LifetimeDef(lifetime_def.lifetime.ident.name.as_interned_str()),
                     REGULAR_SPACE,
                     lifetime_def.lifetime.ident.span
                 );
@@ -209,7 +210,7 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
             GenericParam::Type(ref ty_param) => {
                 self.create_def(
                     ty_param.id,
-                    DefPathData::TypeParam(ty_param.ident.name.as_str()),
+                    DefPathData::TypeParam(ty_param.ident.name.as_interned_str()),
                     REGULAR_SPACE,
                     ty_param.ident.span
                 );
@@ -222,8 +223,10 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
     fn visit_trait_item(&mut self, ti: &'a TraitItem) {
         let def_data = match ti.node {
             TraitItemKind::Method(..) | TraitItemKind::Const(..) =>
-                DefPathData::ValueNs(ti.ident.name.as_str()),
-            TraitItemKind::Type(..) => DefPathData::AssocTypeInTrait(ti.ident.name.as_str()),
+                DefPathData::ValueNs(ti.ident.name.as_interned_str()),
+            TraitItemKind::Type(..) => {
+                DefPathData::AssocTypeInTrait(ti.ident.name.as_interned_str())
+            },
             TraitItemKind::Macro(..) => return self.visit_macro_invoc(ti.id, false),
         };
 
@@ -240,8 +243,8 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
     fn visit_impl_item(&mut self, ii: &'a ImplItem) {
         let def_data = match ii.node {
             ImplItemKind::Method(..) | ImplItemKind::Const(..) =>
-                DefPathData::ValueNs(ii.ident.name.as_str()),
-            ImplItemKind::Type(..) => DefPathData::AssocTypeInImpl(ii.ident.name.as_str()),
+                DefPathData::ValueNs(ii.ident.name.as_interned_str()),
+            ImplItemKind::Type(..) => DefPathData::AssocTypeInImpl(ii.ident.name.as_interned_str()),
             ImplItemKind::Macro(..) => return self.visit_macro_invoc(ii.id, false),
         };
 
diff --git a/src/librustc/hir/map/definitions.rs b/src/librustc/hir/map/definitions.rs
index 12f146ef491..616dc22486d 100644
--- a/src/librustc/hir/map/definitions.rs
+++ b/src/librustc/hir/map/definitions.rs
@@ -701,7 +701,7 @@ impl DefPathData {
             Typeof => "{{typeof}}",
         };
 
-        Symbol::intern(s).as_str()
+        Symbol::intern(s).as_interned_str()
     }
 
     pub fn to_string(&self) -> String {
@@ -731,7 +731,7 @@ macro_rules! define_global_metadata_kind {
                     definitions.create_def_with_parent(
                         CRATE_DEF_INDEX,
                         ast::DUMMY_NODE_ID,
-                        DefPathData::GlobalMetaData(instance.name().as_str()),
+                        DefPathData::GlobalMetaData(instance.name().as_interned_str()),
                         GLOBAL_MD_ADDRESS_SPACE,
                         Mark::root(),
                         DUMMY_SP
@@ -746,7 +746,7 @@ macro_rules! define_global_metadata_kind {
                 let def_key = DefKey {
                     parent: Some(CRATE_DEF_INDEX),
                     disambiguated_data: DisambiguatedDefPathData {
-                        data: DefPathData::GlobalMetaData(self.name().as_str()),
+                        data: DefPathData::GlobalMetaData(self.name().as_interned_str()),
                         disambiguator: 0,
                     }
                 };
diff --git a/src/librustc/ich/impls_const_math.rs b/src/librustc/ich/impls_const_math.rs
deleted file mode 100644
index 5f3ff461c0c..00000000000
--- a/src/librustc/ich/impls_const_math.rs
+++ /dev/null
@@ -1,44 +0,0 @@
-// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-//! This module contains `HashStable` implementations for various data types
-//! from `rustc_const_math` in no particular order.
-
-impl_stable_hash_for!(struct ::rustc_const_math::ConstFloat {
-    ty,
-    bits
-});
-
-impl_stable_hash_for!(enum ::rustc_const_math::ConstMathErr {
-    NotInRange,
-    CmpBetweenUnequalTypes,
-    UnequalTypes(op),
-    Overflow(op),
-    ShiftNegative,
-    DivisionByZero,
-    RemainderByZero,
-    UnsignedNegation,
-    ULitOutOfRange(int_ty),
-    LitOutOfRange(int_ty)
-});
-
-impl_stable_hash_for!(enum ::rustc_const_math::Op {
-    Add,
-    Sub,
-    Mul,
-    Div,
-    Rem,
-    Shr,
-    Shl,
-    Neg,
-    BitAnd,
-    BitOr,
-    BitXor
-});
diff --git a/src/librustc/ich/impls_mir.rs b/src/librustc/ich/impls_mir.rs
index c73f171806e..33f43e53394 100644
--- a/src/librustc/ich/impls_mir.rs
+++ b/src/librustc/ich/impls_mir.rs
@@ -227,27 +227,6 @@ for mir::TerminatorKind<'gcx> {
     }
 }
 
-impl<'a, 'gcx> HashStable<StableHashingContext<'a>>
-for mir::AssertMessage<'gcx> {
-    fn hash_stable<W: StableHasherResult>(&self,
-                                          hcx: &mut StableHashingContext<'a>,
-                                          hasher: &mut StableHasher<W>) {
-        mem::discriminant(self).hash_stable(hcx, hasher);
-
-        match *self {
-            mir::AssertMessage::BoundsCheck { ref len, ref index } => {
-                len.hash_stable(hcx, hasher);
-                index.hash_stable(hcx, hasher);
-            }
-            mir::AssertMessage::Math(ref const_math_err) => {
-                const_math_err.hash_stable(hcx, hasher);
-            }
-            mir::AssertMessage::GeneratorResumedAfterReturn => (),
-            mir::AssertMessage::GeneratorResumedAfterPanic => (),
-        }
-    }
-}
-
 impl_stable_hash_for!(struct mir::Statement<'tcx> { source_info, kind });
 
 impl<'a, 'gcx> HashStable<StableHashingContext<'a>>
@@ -563,6 +542,11 @@ impl<'a, 'gcx> HashStable<StableHashingContext<'a>> for mir::Literal<'gcx> {
 
 impl_stable_hash_for!(struct mir::Location { block, statement_index });
 
+impl_stable_hash_for!(struct mir::BorrowCheckResult<'tcx> {
+    closure_requirements,
+    used_mut_upvars
+});
+
 impl_stable_hash_for!(struct mir::ClosureRegionRequirements<'tcx> {
     num_external_vids,
     outlives_requirements
diff --git a/src/librustc/ich/impls_syntax.rs b/src/librustc/ich/impls_syntax.rs
index d7e16ab3620..1cf9b7bf478 100644
--- a/src/librustc/ich/impls_syntax.rs
+++ b/src/librustc/ich/impls_syntax.rs
@@ -19,7 +19,7 @@ use std::mem;
 use syntax::ast;
 use syntax::feature_gate;
 use syntax::parse::token;
-use syntax::symbol::InternedString;
+use syntax::symbol::{InternedString, LocalInternedString};
 use syntax::tokenstream;
 use syntax_pos::FileMap;
 
@@ -34,8 +34,7 @@ impl<'a> HashStable<StableHashingContext<'a>> for InternedString {
     fn hash_stable<W: StableHasherResult>(&self,
                                           hcx: &mut StableHashingContext<'a>,
                                           hasher: &mut StableHasher<W>) {
-        let s: &str = &**self;
-        s.hash_stable(hcx, hasher);
+        self.with(|s| s.hash_stable(hcx, hasher))
     }
 }
 
@@ -50,6 +49,27 @@ impl<'a> ToStableHashKey<StableHashingContext<'a>> for InternedString {
     }
 }
 
+impl<'a> HashStable<StableHashingContext<'a>> for LocalInternedString {
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a>,
+                                          hasher: &mut StableHasher<W>) {
+        let s: &str = &**self;
+        s.hash_stable(hcx, hasher);
+    }
+}
+
+impl<'a> ToStableHashKey<StableHashingContext<'a>> for LocalInternedString {
+    type KeyType = LocalInternedString;
+
+    #[inline]
+    fn to_stable_hash_key(&self,
+                          _: &StableHashingContext<'a>)
+                          -> LocalInternedString {
+        self.clone()
+    }
+}
+
 impl<'a> HashStable<StableHashingContext<'a>> for ast::Name {
     #[inline]
     fn hash_stable<W: StableHasherResult>(&self,
@@ -66,7 +86,7 @@ impl<'a> ToStableHashKey<StableHashingContext<'a>> for ast::Name {
     fn to_stable_hash_key(&self,
                           _: &StableHashingContext<'a>)
                           -> InternedString {
-        self.as_str()
+        self.as_interned_str()
     }
 }
 
@@ -179,8 +199,7 @@ impl<'a> HashStable<StableHashingContext<'a>> for [ast::Attribute] {
         let filtered: AccumulateVec<[&ast::Attribute; 8]> = self
             .iter()
             .filter(|attr| {
-                !attr.is_sugared_doc &&
-                attr.name().map(|name| !hcx.is_ignored_attr(name)).unwrap_or(true)
+                !attr.is_sugared_doc && !hcx.is_ignored_attr(attr.name())
             })
             .collect();
 
@@ -191,12 +210,23 @@ impl<'a> HashStable<StableHashingContext<'a>> for [ast::Attribute] {
     }
 }
 
+impl<'a> HashStable<StableHashingContext<'a>> for ast::Path {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a>,
+                                          hasher: &mut StableHasher<W>) {
+        self.segments.len().hash_stable(hcx, hasher);
+        for segment in &self.segments {
+            segment.ident.name.hash_stable(hcx, hasher);
+        }
+    }
+}
+
 impl<'a> HashStable<StableHashingContext<'a>> for ast::Attribute {
     fn hash_stable<W: StableHasherResult>(&self,
                                           hcx: &mut StableHashingContext<'a>,
                                           hasher: &mut StableHasher<W>) {
         // Make sure that these have been filtered out.
-        debug_assert!(self.name().map(|name| !hcx.is_ignored_attr(name)).unwrap_or(true));
+        debug_assert!(!hcx.is_ignored_attr(self.name()));
         debug_assert!(!self.is_sugared_doc);
 
         let ast::Attribute {
@@ -209,10 +239,7 @@ impl<'a> HashStable<StableHashingContext<'a>> for ast::Attribute {
         } = *self;
 
         style.hash_stable(hcx, hasher);
-        path.segments.len().hash_stable(hcx, hasher);
-        for segment in &path.segments {
-            segment.ident.name.hash_stable(hcx, hasher);
-        }
+        path.hash_stable(hcx, hasher);
         for tt in tokens.trees() {
             tt.hash_stable(hcx, hasher);
         }
diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index 5ab8d6eb7b3..a40d8e09277 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -505,9 +505,6 @@ for ::middle::const_val::ErrKind<'gcx> {
                 len.hash_stable(hcx, hasher);
                 index.hash_stable(hcx, hasher);
             }
-            Math(ref const_math_err) => {
-                const_math_err.hash_stable(hcx, hasher);
-            }
             LayoutError(ref layout_error) => {
                 layout_error.hash_stable(hcx, hasher);
             }
@@ -528,16 +525,26 @@ impl_stable_hash_for!(struct ty::GenericPredicates<'tcx> {
     predicates
 });
 
+
 impl<'a, 'gcx> HashStable<StableHashingContext<'a>>
 for ::mir::interpret::EvalError<'gcx> {
     fn hash_stable<W: StableHasherResult>(&self,
                                           hcx: &mut StableHashingContext<'a>,
                                           hasher: &mut StableHasher<W>) {
+        self.kind.hash_stable(hcx, hasher)
+    }
+}
+
+impl<'a, 'gcx, O: HashStable<StableHashingContext<'a>>> HashStable<StableHashingContext<'a>>
+for ::mir::interpret::EvalErrorKind<'gcx, O> {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a>,
+                                          hasher: &mut StableHasher<W>) {
         use mir::interpret::EvalErrorKind::*;
 
-        mem::discriminant(&self.kind).hash_stable(hcx, hasher);
+        mem::discriminant(&self).hash_stable(hcx, hasher);
 
-        match self.kind {
+        match *self {
             DanglingPointerDeref |
             DoubleFree |
             InvalidMemoryAccess |
@@ -568,8 +575,12 @@ for ::mir::interpret::EvalError<'gcx> {
             TypeckError |
             DerefFunctionPointer |
             ExecuteMemory |
-            ReferencedConstant |
-            OverflowingMath => {}
+            OverflowNeg |
+            RemainderByZero |
+            DivisionByZero |
+            GeneratorResumedAfterReturn |
+            GeneratorResumedAfterPanic |
+            ReferencedConstant => {}
             MachineError(ref err) => err.hash_stable(hcx, hasher),
             FunctionPointerTyMismatch(a, b) => {
                 a.hash_stable(hcx, hasher);
@@ -588,14 +599,9 @@ for ::mir::interpret::EvalError<'gcx> {
             },
             InvalidBoolOp(bop) => bop.hash_stable(hcx, hasher),
             Unimplemented(ref s) => s.hash_stable(hcx, hasher),
-            ArrayIndexOutOfBounds(sp, a, b) => {
-                sp.hash_stable(hcx, hasher);
-                a.hash_stable(hcx, hasher);
-                b.hash_stable(hcx, hasher)
-            },
-            Math(sp, ref err) => {
-                sp.hash_stable(hcx, hasher);
-                err.hash_stable(hcx, hasher)
+            BoundsCheck { ref len, ref index } => {
+                len.hash_stable(hcx, hasher);
+                index.hash_stable(hcx, hasher)
             },
             Intrinsic(ref s) => s.hash_stable(hcx, hasher),
             InvalidChar(c) => c.hash_stable(hcx, hasher),
@@ -668,6 +674,7 @@ for ::mir::interpret::EvalError<'gcx> {
             Layout(lay) => lay.hash_stable(hcx, hasher),
             HeapAllocNonPowerOfTwoAlignment(n) => n.hash_stable(hcx, hasher),
             PathNotFound(ref v) => v.hash_stable(hcx, hasher),
+            Overflow(op) => op.hash_stable(hcx, hasher),
         }
     }
 }
diff --git a/src/librustc/ich/mod.rs b/src/librustc/ich/mod.rs
index 1b77a2e7c82..a0c6bbbb239 100644
--- a/src/librustc/ich/mod.rs
+++ b/src/librustc/ich/mod.rs
@@ -18,7 +18,6 @@ mod fingerprint;
 mod caching_codemap_view;
 mod hcx;
 
-mod impls_const_math;
 mod impls_cstore;
 mod impls_hir;
 mod impls_mir;
diff --git a/src/librustc/infer/combine.rs b/src/librustc/infer/combine.rs
index 096aed85f55..ccba5a09cf6 100644
--- a/src/librustc/infer/combine.rs
+++ b/src/librustc/infer/combine.rs
@@ -407,7 +407,7 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
                             drop(variables);
                             self.relate(&u, &u)
                         }
-                        TypeVariableValue::Unknown { .. } => {
+                        TypeVariableValue::Unknown { universe } => {
                             match self.ambient_variance {
                                 // Invariant: no need to make a fresh type variable.
                                 ty::Invariant => return Ok(t),
@@ -424,7 +424,7 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
                             }
 
                             let origin = *variables.var_origin(vid);
-                            let new_var_id = variables.new_var(false, origin);
+                            let new_var_id = variables.new_var(universe, false, origin);
                             let u = self.tcx().mk_var(new_var_id);
                             debug!("generalize: replacing original vid={:?} with new={:?}",
                                    vid, u);
diff --git a/src/librustc/infer/higher_ranked/mod.rs b/src/librustc/infer/higher_ranked/mod.rs
index c23836071ff..b8437e39ddc 100644
--- a/src/librustc/infer/higher_ranked/mod.rs
+++ b/src/librustc/infer/higher_ranked/mod.rs
@@ -19,7 +19,7 @@ use super::{CombinedSnapshot,
 use super::combine::CombineFields;
 use super::region_constraints::{TaintDirections};
 
-use std::collections::BTreeMap;
+use rustc_data_structures::lazy_btree_map::LazyBTreeMap;
 use ty::{self, TyCtxt, Binder, TypeFoldable};
 use ty::error::TypeError;
 use ty::relate::{Relate, RelateResult, TypeRelation};
@@ -62,7 +62,7 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
             // Second, we instantiate each bound region in the supertype with a
             // fresh concrete region.
             let (b_prime, skol_map) =
-                self.infcx.skolemize_late_bound_regions(b, snapshot);
+                self.infcx.skolemize_late_bound_regions(b);
 
             debug!("a_prime={:?}", a_prime);
             debug!("b_prime={:?}", b_prime);
@@ -114,7 +114,7 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
             // First, we instantiate each bound region in the matcher
             // with a skolemized region.
             let ((a_match, a_value), skol_map) =
-                self.infcx.skolemize_late_bound_regions(a_pair, snapshot);
+                self.infcx.skolemize_late_bound_regions(a_pair);
 
             debug!("higher_ranked_match: a_match={:?}", a_match);
             debug!("higher_ranked_match: skol_map={:?}", skol_map);
@@ -247,7 +247,8 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
                                              snapshot: &CombinedSnapshot<'a, 'tcx>,
                                              debruijn: ty::DebruijnIndex,
                                              new_vars: &[ty::RegionVid],
-                                             a_map: &BTreeMap<ty::BoundRegion, ty::Region<'tcx>>,
+                                             a_map: &LazyBTreeMap<ty::BoundRegion,
+                                                                  ty::Region<'tcx>>,
                                              r0: ty::Region<'tcx>)
                                              -> ty::Region<'tcx> {
             // Regions that pre-dated the LUB computation stay as they are.
@@ -343,7 +344,8 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
                                              snapshot: &CombinedSnapshot<'a, 'tcx>,
                                              debruijn: ty::DebruijnIndex,
                                              new_vars: &[ty::RegionVid],
-                                             a_map: &BTreeMap<ty::BoundRegion, ty::Region<'tcx>>,
+                                             a_map: &LazyBTreeMap<ty::BoundRegion,
+                                                                  ty::Region<'tcx>>,
                                              a_vars: &[ty::RegionVid],
                                              b_vars: &[ty::RegionVid],
                                              r0: ty::Region<'tcx>)
@@ -412,7 +414,7 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
 
         fn rev_lookup<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
                                       span: Span,
-                                      a_map: &BTreeMap<ty::BoundRegion, ty::Region<'tcx>>,
+                                      a_map: &LazyBTreeMap<ty::BoundRegion, ty::Region<'tcx>>,
                                       r: ty::Region<'tcx>) -> ty::Region<'tcx>
         {
             for (a_br, a_r) in a_map {
@@ -435,7 +437,7 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
 }
 
 fn var_ids<'a, 'gcx, 'tcx>(fields: &CombineFields<'a, 'gcx, 'tcx>,
-                           map: &BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
+                           map: &LazyBTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
                            -> Vec<ty::RegionVid> {
     map.iter()
        .map(|(_, &r)| match *r {
@@ -585,14 +587,13 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     ///
     /// [rustc guide]: https://rust-lang-nursery.github.io/rustc-guide/trait-hrtb.html
     pub fn skolemize_late_bound_regions<T>(&self,
-                                           binder: &ty::Binder<T>,
-                                           snapshot: &CombinedSnapshot<'a, 'tcx>)
+                                           binder: &ty::Binder<T>)
                                            -> (T, SkolemizationMap<'tcx>)
         where T : TypeFoldable<'tcx>
     {
         let (result, map) = self.tcx.replace_late_bound_regions(binder, |br| {
-            self.borrow_region_constraints()
-                .push_skolemized(self.tcx, br, &snapshot.region_constraints_snapshot)
+            self.universe.set(self.universe().subuniverse());
+            self.tcx.mk_region(ty::ReSkolemized(self.universe(), br))
         });
 
         debug!("skolemize_bound_regions(binder={:?}, result={:?}, map={:?})",
@@ -777,7 +778,8 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         debug!("pop_skolemized({:?})", skol_map);
         let skol_regions: FxHashSet<_> = skol_map.values().cloned().collect();
         self.borrow_region_constraints()
-            .pop_skolemized(self.tcx, &skol_regions, &snapshot.region_constraints_snapshot);
+            .pop_skolemized(self.universe(), &skol_regions, &snapshot.region_constraints_snapshot);
+        self.universe.set(snapshot.universe);
         if !skol_map.is_empty() {
             self.projection_cache.borrow_mut().rollback_skolemized(
                 &snapshot.projection_cache_snapshot);
diff --git a/src/librustc/infer/lexical_region_resolve/mod.rs b/src/librustc/infer/lexical_region_resolve/mod.rs
index 00b2ac7449f..5984a831e6f 100644
--- a/src/librustc/infer/lexical_region_resolve/mod.rs
+++ b/src/librustc/infer/lexical_region_resolve/mod.rs
@@ -15,7 +15,7 @@ use infer::RegionVariableOrigin;
 use infer::region_constraints::Constraint;
 use infer::region_constraints::GenericKind;
 use infer::region_constraints::RegionConstraintData;
-use infer::region_constraints::VarOrigins;
+use infer::region_constraints::VarInfos;
 use infer::region_constraints::VerifyBound;
 use middle::free_region::RegionRelations;
 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
@@ -37,7 +37,7 @@ mod graphviz;
 /// all the variables as well as a set of errors that must be reported.
 pub fn resolve<'tcx>(
     region_rels: &RegionRelations<'_, '_, 'tcx>,
-    var_origins: VarOrigins,
+    var_infos: VarInfos,
     data: RegionConstraintData<'tcx>,
 ) -> (
     LexicalRegionResolutions<'tcx>,
@@ -47,7 +47,7 @@ pub fn resolve<'tcx>(
     let mut errors = vec![];
     let mut resolver = LexicalResolver {
         region_rels,
-        var_origins,
+        var_infos,
         data,
     };
     let values = resolver.infer_variable_values(&mut errors);
@@ -103,7 +103,7 @@ type RegionGraph<'tcx> = graph::Graph<(), Constraint<'tcx>>;
 
 struct LexicalResolver<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
     region_rels: &'cx RegionRelations<'cx, 'gcx, 'tcx>,
-    var_origins: VarOrigins,
+    var_infos: VarInfos,
     data: RegionConstraintData<'tcx>,
 }
 
@@ -132,7 +132,7 @@ impl<'cx, 'gcx, 'tcx> LexicalResolver<'cx, 'gcx, 'tcx> {
     }
 
     fn num_vars(&self) -> usize {
-        self.var_origins.len()
+        self.var_infos.len()
     }
 
     /// Initially, the value for all variables is set to `'empty`, the
@@ -279,7 +279,7 @@ impl<'cx, 'gcx, 'tcx> LexicalResolver<'cx, 'gcx, 'tcx> {
 
             (&ReVar(v_id), _) | (_, &ReVar(v_id)) => {
                 span_bug!(
-                    self.var_origins[v_id].span(),
+                    self.var_infos[v_id].origin.span(),
                     "lub_concrete_regions invoked with non-concrete \
                      regions: {:?}, {:?}",
                     a,
@@ -576,7 +576,7 @@ impl<'cx, 'gcx, 'tcx> LexicalResolver<'cx, 'gcx, 'tcx> {
                 if !self.region_rels
                     .is_subregion_of(lower_bound.region, upper_bound.region)
                 {
-                    let origin = self.var_origins[node_idx].clone();
+                    let origin = self.var_infos[node_idx].origin.clone();
                     debug!(
                         "region inference error at {:?} for {:?}: SubSupConflict sub: {:?} \
                          sup: {:?}",
@@ -598,7 +598,7 @@ impl<'cx, 'gcx, 'tcx> LexicalResolver<'cx, 'gcx, 'tcx> {
         }
 
         span_bug!(
-            self.var_origins[node_idx].span(),
+            self.var_infos[node_idx].origin.span(),
             "collect_error_for_expanding_node() could not find \
              error for var {:?}, lower_bounds={:?}, \
              upper_bounds={:?}",
diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index 40cc43c3ca6..c62e7f8d9b6 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -28,9 +28,9 @@ use ty::error::{ExpectedFound, TypeError, UnconstrainedNumeric};
 use ty::fold::TypeFoldable;
 use ty::relate::RelateResult;
 use traits::{self, ObligationCause, PredicateObligations};
+use rustc_data_structures::lazy_btree_map::LazyBTreeMap;
 use rustc_data_structures::unify as ut;
 use std::cell::{Cell, RefCell, Ref, RefMut};
-use std::collections::BTreeMap;
 use std::fmt;
 use syntax::ast;
 use errors::DiagnosticBuilder;
@@ -42,7 +42,7 @@ use arena::SyncDroplessArena;
 use self::combine::CombineFields;
 use self::higher_ranked::HrMatchResult;
 use self::region_constraints::{RegionConstraintCollector, RegionSnapshot};
-use self::region_constraints::{GenericKind, VerifyBound, RegionConstraintData, VarOrigins};
+use self::region_constraints::{GenericKind, VerifyBound, RegionConstraintData, VarInfos};
 use self::lexical_region_resolve::LexicalRegionResolutions;
 use self::outlives::env::OutlivesEnvironment;
 use self::type_variable::TypeVariableOrigin;
@@ -183,11 +183,22 @@ pub struct InferCtxt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     // obligations within. This is expected to be done 'late enough'
     // that all type inference variables have been bound and so forth.
     pub region_obligations: RefCell<Vec<(ast::NodeId, RegionObligation<'tcx>)>>,
+
+    /// What is the innermost universe we have created? Starts out as
+    /// `UniverseIndex::root()` but grows from there as we enter
+    /// universal quantifiers.
+    ///
+    /// NB: At present, we exclude the universal quantifiers on the
+    /// item we are type-checking, and just consider those names as
+    /// part of the root universe. So this would only get incremented
+    /// when we enter into a higher-ranked (`for<..>`) type or trait
+    /// bound.
+    universe: Cell<ty::UniverseIndex>,
 }
 
 /// A map returned by `skolemize_late_bound_regions()` indicating the skolemized
 /// region that each late-bound region was replaced with.
-pub type SkolemizationMap<'tcx> = BTreeMap<ty::BoundRegion, ty::Region<'tcx>>;
+pub type SkolemizationMap<'tcx> = LazyBTreeMap<ty::BoundRegion, ty::Region<'tcx>>;
 
 /// See `error_reporting` module for more details
 #[derive(Clone, Debug)]
@@ -455,6 +466,7 @@ impl<'a, 'gcx, 'tcx> InferCtxtBuilder<'a, 'gcx, 'tcx> {
             err_count_on_creation: tcx.sess.err_count(),
             in_snapshot: Cell::new(false),
             region_obligations: RefCell::new(vec![]),
+            universe: Cell::new(ty::UniverseIndex::ROOT),
         }))
     }
 }
@@ -489,6 +501,7 @@ pub struct CombinedSnapshot<'a, 'tcx:'a> {
     float_snapshot: ut::Snapshot<ut::InPlace<ty::FloatVid>>,
     region_constraints_snapshot: RegionSnapshot,
     region_obligations_snapshot: usize,
+    universe: ty::UniverseIndex,
     was_in_snapshot: bool,
     _in_progress_tables: Option<Ref<'a, ty::TypeckTables<'tcx>>>,
 }
@@ -618,6 +631,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
             float_snapshot: self.float_unification_table.borrow_mut().snapshot(),
             region_constraints_snapshot: self.borrow_region_constraints().start_snapshot(),
             region_obligations_snapshot: self.region_obligations.borrow().len(),
+            universe: self.universe(),
             was_in_snapshot: in_snapshot,
             // Borrow tables "in progress" (i.e. during typeck)
             // to ban writes from within a snapshot to them.
@@ -635,10 +649,12 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                                float_snapshot,
                                region_constraints_snapshot,
                                region_obligations_snapshot,
+                               universe,
                                was_in_snapshot,
                                _in_progress_tables } = snapshot;
 
         self.in_snapshot.set(was_in_snapshot);
+        self.universe.set(universe);
 
         self.projection_cache
             .borrow_mut()
@@ -667,6 +683,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                                float_snapshot,
                                region_constraints_snapshot,
                                region_obligations_snapshot: _,
+                               universe: _,
                                was_in_snapshot,
                                _in_progress_tables } = snapshot;
 
@@ -811,7 +828,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
 
         Some(self.commit_if_ok(|snapshot| {
             let (ty::SubtypePredicate { a_is_expected, a, b}, skol_map) =
-                self.skolemize_late_bound_regions(predicate, snapshot);
+                self.skolemize_late_bound_regions(predicate);
 
             let cause_span = cause.span;
             let ok = self.at(cause, param_env).sub_exp(a_is_expected, a, b)?;
@@ -828,7 +845,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     {
         self.commit_if_ok(|snapshot| {
             let (ty::OutlivesPredicate(r_a, r_b), skol_map) =
-                self.skolemize_late_bound_regions(predicate, snapshot);
+                self.skolemize_late_bound_regions(predicate);
             let origin =
                 SubregionOrigin::from_obligation_cause(cause,
                                                        || RelateRegionParamBound(cause.span));
@@ -841,7 +858,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     pub fn next_ty_var_id(&self, diverging: bool, origin: TypeVariableOrigin) -> TyVid {
         self.type_variables
             .borrow_mut()
-            .new_var(diverging, origin)
+            .new_var(self.universe(), diverging, origin)
     }
 
     pub fn next_ty_var(&self, origin: TypeVariableOrigin) -> Ty<'tcx> {
@@ -872,12 +889,14 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     ///   during diagnostics / error-reporting.
     pub fn next_region_var(&self, origin: RegionVariableOrigin)
                            -> ty::Region<'tcx> {
-        self.tcx.mk_region(ty::ReVar(self.borrow_region_constraints().new_region_var(origin)))
+        let region_var = self.borrow_region_constraints()
+            .new_region_var(self.universe(), origin);
+        self.tcx.mk_region(ty::ReVar(region_var))
     }
 
     /// Number of region variables created so far.
     pub fn num_region_vars(&self) -> usize {
-        self.borrow_region_constraints().var_origins().len()
+        self.borrow_region_constraints().num_region_vars()
     }
 
     /// Just a convenient wrapper of `next_region_var` for using during NLL.
@@ -909,7 +928,8 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                             -> Ty<'tcx> {
         let ty_var_id = self.type_variables
                             .borrow_mut()
-                            .new_var(false,
+                            .new_var(self.universe(),
+                                     false,
                                      TypeVariableOrigin::TypeParameterDefinition(span, def.name));
 
         self.tcx.mk_var(ty_var_id)
@@ -1004,12 +1024,12 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                                                 region_context,
                                                 region_map,
                                                 outlives_env.free_region_map());
-        let (var_origins, data) = self.region_constraints.borrow_mut()
+        let (var_infos, data) = self.region_constraints.borrow_mut()
                                                          .take()
                                                          .expect("regions already resolved")
-                                                         .into_origins_and_data();
+                                                         .into_infos_and_data();
         let (lexical_region_resolutions, errors) =
-            lexical_region_resolve::resolve(region_rels, var_origins, data);
+            lexical_region_resolve::resolve(region_rels, var_infos, data);
 
         let old_value = self.lexical_region_resolutions.replace(Some(lexical_region_resolutions));
         assert!(old_value.is_none());
@@ -1057,13 +1077,13 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     /// hence that `resolve_regions_and_report_errors` can never be
     /// called. This is used only during NLL processing to "hand off" ownership
     /// of the set of region vairables into the NLL region context.
-    pub fn take_region_var_origins(&self) -> VarOrigins {
-        let (var_origins, data) = self.region_constraints.borrow_mut()
+    pub fn take_region_var_origins(&self) -> VarInfos {
+        let (var_infos, data) = self.region_constraints.borrow_mut()
                                                          .take()
                                                          .expect("regions already resolved")
-                                                         .into_origins_and_data();
+                                                         .into_infos_and_data();
         assert!(data.is_empty());
-        var_origins
+        var_infos
     }
 
     pub fn ty_to_string(&self, t: Ty<'tcx>) -> String {
@@ -1216,7 +1236,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         span: Span,
         lbrct: LateBoundRegionConversionTime,
         value: &ty::Binder<T>)
-        -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
+        -> (T, LazyBTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
         where T : TypeFoldable<'tcx>
     {
         self.tcx.replace_late_bound_regions(
@@ -1356,6 +1376,10 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         self.evaluation_cache.clear();
         self.projection_cache.borrow_mut().clear();
     }
+
+    fn universe(&self) -> ty::UniverseIndex {
+        self.universe.get()
+    }
 }
 
 impl<'a, 'gcx, 'tcx> TypeTrace<'tcx> {
diff --git a/src/librustc/infer/region_constraints/mod.rs b/src/librustc/infer/region_constraints/mod.rs
index 4113a2dd417..c388fa21371 100644
--- a/src/librustc/infer/region_constraints/mod.rs
+++ b/src/librustc/infer/region_constraints/mod.rs
@@ -22,18 +22,16 @@ use rustc_data_structures::unify as ut;
 use ty::{self, Ty, TyCtxt};
 use ty::{Region, RegionVid};
 use ty::ReStatic;
-use ty::{BrFresh, ReLateBound, ReSkolemized, ReVar};
+use ty::{BrFresh, ReLateBound, ReVar};
 
 use std::collections::BTreeMap;
-use std::fmt;
-use std::mem;
-use std::u32;
+use std::{cmp, fmt, mem, u32};
 
 mod taint;
 
 pub struct RegionConstraintCollector<'tcx> {
     /// For each `RegionVid`, the corresponding `RegionVariableOrigin`.
-    var_origins: IndexVec<RegionVid, RegionVariableOrigin>,
+    var_infos: IndexVec<RegionVid, RegionVariableInfo>,
 
     data: RegionConstraintData<'tcx>,
 
@@ -47,9 +45,6 @@ pub struct RegionConstraintCollector<'tcx> {
     /// exist). This prevents us from making many such regions.
     glbs: CombineMap<'tcx>,
 
-    /// Number of skolemized variables currently active.
-    skolemization_count: u32,
-
     /// Global counter used during the GLB algorithm to create unique
     /// names for fresh bound regions
     bound_count: u32,
@@ -76,7 +71,7 @@ pub struct RegionConstraintCollector<'tcx> {
     unification_table: ut::UnificationTable<ut::InPlace<ty::RegionVid>>,
 }
 
-pub type VarOrigins = IndexVec<RegionVid, RegionVariableOrigin>;
+pub type VarInfos = IndexVec<RegionVid, RegionVariableInfo>;
 
 /// The full set of region constraints gathered up by the collector.
 /// Describes constraints between the region variables and other
@@ -230,10 +225,15 @@ enum CombineMapType {
 
 type CombineMap<'tcx> = FxHashMap<TwoRegions<'tcx>, RegionVid>;
 
+#[derive(Debug, Clone, Copy)]
+pub struct RegionVariableInfo {
+    pub origin: RegionVariableOrigin,
+    pub universe: ty::UniverseIndex,
+}
+
 pub struct RegionSnapshot {
     length: usize,
     region_snapshot: ut::Snapshot<ut::InPlace<ty::RegionVid>>,
-    skolemization_count: u32,
 }
 
 /// When working with skolemized regions, we often wish to find all of
@@ -273,19 +273,18 @@ impl TaintDirections {
 impl<'tcx> RegionConstraintCollector<'tcx> {
     pub fn new() -> RegionConstraintCollector<'tcx> {
         RegionConstraintCollector {
-            var_origins: VarOrigins::default(),
+            var_infos: VarInfos::default(),
             data: RegionConstraintData::default(),
             lubs: FxHashMap(),
             glbs: FxHashMap(),
-            skolemization_count: 0,
             bound_count: 0,
             undo_log: Vec::new(),
             unification_table: ut::UnificationTable::new(),
         }
     }
 
-    pub fn var_origins(&self) -> &VarOrigins {
-        &self.var_origins
+    pub fn num_region_vars(&self) -> usize {
+        self.var_infos.len()
     }
 
     pub fn region_constraint_data(&self) -> &RegionConstraintData<'tcx> {
@@ -295,9 +294,9 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
     /// Once all the constraints have been gathered, extract out the final data.
     ///
     /// Not legal during a snapshot.
-    pub fn into_origins_and_data(self) -> (VarOrigins, RegionConstraintData<'tcx>) {
+    pub fn into_infos_and_data(self) -> (VarInfos, RegionConstraintData<'tcx>) {
         assert!(!self.in_snapshot());
-        (self.var_origins, self.data)
+        (self.var_infos, self.data)
     }
 
     /// Takes (and clears) the current set of constraints. Note that
@@ -319,18 +318,15 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         // should think carefully about whether it needs to be cleared
         // or updated in some way.
         let RegionConstraintCollector {
-            var_origins,
+            var_infos,
             data,
             lubs,
             glbs,
-            skolemization_count,
             bound_count: _,
             undo_log: _,
             unification_table,
         } = self;
 
-        assert_eq!(*skolemization_count, 0);
-
         // Clear the tables of (lubs, glbs), so that we will create
         // fresh regions if we do a LUB operation. As it happens,
         // LUB/GLB are not performed by the MIR type-checker, which is
@@ -343,7 +339,7 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         // also insert `a <= b` and a `b <= a` edges, so the
         // `RegionConstraintData` contains the relationship here.
         *unification_table = ut::UnificationTable::new();
-        for vid in var_origins.indices() {
+        for vid in var_infos.indices() {
             unification_table.new_key(unify_key::RegionVidKey { min_vid: vid });
         }
 
@@ -365,7 +361,6 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         RegionSnapshot {
             length,
             region_snapshot: self.unification_table.snapshot(),
-            skolemization_count: self.skolemization_count,
         }
     }
 
@@ -373,12 +368,6 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         debug!("RegionConstraintCollector: commit({})", snapshot.length);
         assert!(self.undo_log.len() > snapshot.length);
         assert!(self.undo_log[snapshot.length] == OpenSnapshot);
-        assert!(
-            self.skolemization_count == snapshot.skolemization_count,
-            "failed to pop skolemized regions: {} now vs {} at start",
-            self.skolemization_count,
-            snapshot.skolemization_count
-        );
 
         if snapshot.length == 0 {
             self.undo_log.truncate(0);
@@ -398,7 +387,6 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         }
         let c = self.undo_log.pop().unwrap();
         assert!(c == OpenSnapshot);
-        self.skolemization_count = snapshot.skolemization_count;
         self.unification_table.rollback_to(snapshot.region_snapshot);
     }
 
@@ -411,8 +399,8 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
                 // nothing to do here
             }
             AddVar(vid) => {
-                self.var_origins.pop().unwrap();
-                assert_eq!(self.var_origins.len(), vid.index() as usize);
+                self.var_infos.pop().unwrap();
+                assert_eq!(self.var_infos.len(), vid.index() as usize);
             }
             AddConstraint(ref constraint) => {
                 self.data.constraints.remove(constraint);
@@ -433,8 +421,13 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         }
     }
 
-    pub fn new_region_var(&mut self, origin: RegionVariableOrigin) -> RegionVid {
-        let vid = self.var_origins.push(origin.clone());
+    pub fn new_region_var(&mut self,
+                          universe: ty::UniverseIndex,
+                          origin: RegionVariableOrigin) -> RegionVid {
+        let vid = self.var_infos.push(RegionVariableInfo {
+            origin,
+            universe,
+        });
 
         let u_vid = self.unification_table
             .new_key(unify_key::RegionVidKey { min_vid: vid });
@@ -450,44 +443,14 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         return vid;
     }
 
-    /// Returns the origin for the given variable.
-    pub fn var_origin(&self, vid: RegionVid) -> RegionVariableOrigin {
-        self.var_origins[vid].clone()
+    /// Returns the universe for the given variable.
+    pub fn var_universe(&self, vid: RegionVid) -> ty::UniverseIndex {
+        self.var_infos[vid].universe
     }
 
-    /// Creates a new skolemized region. Skolemized regions are fresh
-    /// regions used when performing higher-ranked computations. They
-    /// must be used in a very particular way and are never supposed
-    /// to "escape" out into error messages or the code at large.
-    ///
-    /// The idea is to always create a snapshot. Skolemized regions
-    /// can be created in the context of this snapshot, but before the
-    /// snapshot is committed or rolled back, they must be popped
-    /// (using `pop_skolemized_regions`), so that their numbers can be
-    /// recycled. Normally you don't have to think about this: you use
-    /// the APIs in `higher_ranked/mod.rs`, such as
-    /// `skolemize_late_bound_regions` and `plug_leaks`, which will
-    /// guide you on this path (ensure that the `SkolemizationMap` is
-    /// consumed and you are good). For more info on how skolemization
-    /// for HRTBs works, see the [rustc guide].
-    ///
-    /// [rustc guide]: https://rust-lang-nursery.github.io/rustc-guide/trait-hrtb.html
-    ///
-    /// The `snapshot` argument to this function is not really used;
-    /// it's just there to make it explicit which snapshot bounds the
-    /// skolemized region that results. It should always be the top-most snapshot.
-    pub fn push_skolemized(
-        &mut self,
-        tcx: TyCtxt<'_, '_, 'tcx>,
-        br: ty::BoundRegion,
-        snapshot: &RegionSnapshot,
-    ) -> Region<'tcx> {
-        assert!(self.in_snapshot());
-        assert!(self.undo_log[snapshot.length] == OpenSnapshot);
-
-        let sc = self.skolemization_count;
-        self.skolemization_count = sc + 1;
-        tcx.mk_region(ReSkolemized(ty::SkolemizedRegionVid { index: sc }, br))
+    /// Returns the origin for the given variable.
+    pub fn var_origin(&self, vid: RegionVid) -> RegionVariableOrigin {
+        self.var_infos[vid].origin
     }
 
     /// Removes all the edges to/from the skolemized regions that are
@@ -496,7 +459,7 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
     /// created in that time.
     pub fn pop_skolemized(
         &mut self,
-        _tcx: TyCtxt<'_, '_, 'tcx>,
+        skolemization_count: ty::UniverseIndex,
         skols: &FxHashSet<ty::Region<'tcx>>,
         snapshot: &RegionSnapshot,
     ) {
@@ -505,36 +468,28 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         assert!(self.in_snapshot());
         assert!(self.undo_log[snapshot.length] == OpenSnapshot);
         assert!(
-            self.skolemization_count as usize >= skols.len(),
+            skolemization_count.as_usize() >= skols.len(),
             "popping more skolemized variables than actually exist, \
-             sc now = {}, skols.len = {}",
-            self.skolemization_count,
+             sc now = {:?}, skols.len = {:?}",
+            skolemization_count,
             skols.len()
         );
 
-        let last_to_pop = self.skolemization_count;
-        let first_to_pop = last_to_pop - (skols.len() as u32);
+        let last_to_pop = skolemization_count.subuniverse();
+        let first_to_pop = ty::UniverseIndex::from(last_to_pop.as_u32() - skols.len() as u32);
 
-        assert!(
-            first_to_pop >= snapshot.skolemization_count,
-            "popping more regions than snapshot contains, \
-             sc now = {}, sc then = {}, skols.len = {}",
-            self.skolemization_count,
-            snapshot.skolemization_count,
-            skols.len()
-        );
         debug_assert! {
             skols.iter()
                  .all(|&k| match *k {
-                     ty::ReSkolemized(index, _) =>
-                         index.index >= first_to_pop &&
-                         index.index < last_to_pop,
+                     ty::ReSkolemized(universe, _) =>
+                         universe >= first_to_pop &&
+                         universe < last_to_pop,
                      _ =>
                          false
                  }),
-            "invalid skolemization keys or keys out of range ({}..{}): {:?}",
-            snapshot.skolemization_count,
-            self.skolemization_count,
+            "invalid skolemization keys or keys out of range ({:?}..{:?}): {:?}",
+            first_to_pop,
+            last_to_pop,
             skols
         }
 
@@ -551,7 +506,6 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
             self.rollback_undo_entry(undo_entry);
         }
 
-        self.skolemization_count = snapshot.skolemization_count;
         return;
 
         fn kill_constraint<'tcx>(
@@ -805,7 +759,10 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         if let Some(&c) = self.combine_map(t).get(&vars) {
             return tcx.mk_region(ReVar(c));
         }
-        let c = self.new_region_var(MiscVariable(origin.span()));
+        let a_universe = self.universe(a);
+        let b_universe = self.universe(b);
+        let c_universe = cmp::max(a_universe, b_universe);
+        let c = self.new_region_var(c_universe, MiscVariable(origin.span()));
         self.combine_map(t).insert(vars, c);
         if self.in_snapshot() {
             self.undo_log.push(AddCombination(t, vars));
@@ -821,6 +778,24 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         new_r
     }
 
+    fn universe(&self, region: Region<'tcx>) -> ty::UniverseIndex {
+        match *region {
+            ty::ReScope(..) |
+            ty::ReStatic |
+            ty::ReEmpty |
+            ty::ReErased |
+            ty::ReFree(..) |
+            ty::ReEarlyBound(..) => ty::UniverseIndex::ROOT,
+            ty::ReSkolemized(universe, _) => universe,
+            ty::ReClosureBound(vid) |
+            ty::ReVar(vid) => self.var_universe(vid),
+            ty::ReLateBound(..) =>
+                bug!("universe(): encountered bound region {:?}", region),
+            ty::ReCanonical(..) =>
+                bug!("region_universe(): encountered canonical region {:?}", region),
+        }
+    }
+
     pub fn vars_created_since_snapshot(&self, mark: &RegionSnapshot) -> Vec<RegionVid> {
         self.undo_log[mark.length..]
             .iter()
@@ -865,12 +840,7 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
 
 impl fmt::Debug for RegionSnapshot {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(
-            f,
-            "RegionSnapshot(length={},skolemization={})",
-            self.length,
-            self.skolemization_count
-        )
+        write!(f, "RegionSnapshot(length={})", self.length)
     }
 }
 
diff --git a/src/librustc/infer/type_variable.rs b/src/librustc/infer/type_variable.rs
index 5e96f4eb576..d40e1b3760f 100644
--- a/src/librustc/infer/type_variable.rs
+++ b/src/librustc/infer/type_variable.rs
@@ -78,10 +78,12 @@ struct TypeVariableData {
 #[derive(Copy, Clone, Debug)]
 pub enum TypeVariableValue<'tcx> {
     Known { value: Ty<'tcx> },
-    Unknown,
+    Unknown { universe: ty::UniverseIndex },
 }
 
 impl<'tcx> TypeVariableValue<'tcx> {
+    /// If this value is known, returns the type it is known to be.
+    /// Otherwise, `None`.
     pub fn known(&self) -> Option<Ty<'tcx>> {
         match *self {
             TypeVariableValue::Unknown { .. } => None,
@@ -181,10 +183,11 @@ impl<'tcx> TypeVariableTable<'tcx> {
     ///   The code in this module doesn't care, but it can be useful
     ///   for improving error messages.
     pub fn new_var(&mut self,
+                   universe: ty::UniverseIndex,
                    diverging: bool,
                    origin: TypeVariableOrigin)
                    -> ty::TyVid {
-        let eq_key = self.eq_relations.new_key(TypeVariableValue::Unknown);
+        let eq_key = self.eq_relations.new_key(TypeVariableValue::Unknown { universe });
 
         let sub_key = self.sub_relations.new_key(());
         assert_eq!(eq_key.vid, sub_key);
@@ -437,7 +440,16 @@ impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> {
             (&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2),
 
             // If both sides are *unknown*, it hardly matters, does it?
-            (&TypeVariableValue::Unknown, &TypeVariableValue::Unknown) => Ok(*value1),
+            (&TypeVariableValue::Unknown { universe: universe1 },
+             &TypeVariableValue::Unknown { universe: universe2 }) =>  {
+                // If we unify two unbound variables, ?T and ?U, then whatever
+                // value they wind up taking (which must be the same value) must
+                // be nameable by both universes. Therefore, the resulting
+                // universe is the minimum of the two universes, because that is
+                // the one which contains the fewest names in scope.
+                let universe = cmp::min(universe1, universe2);
+                Ok(TypeVariableValue::Unknown { universe })
+            }
         }
     }
 }
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index f85d0a9bf0c..879d38c4894 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -45,8 +45,8 @@
 #![feature(const_fn)]
 #![feature(core_intrinsics)]
 #![feature(drain_filter)]
-#![feature(dyn_trait)]
 #![feature(entry_or_default)]
+#![cfg_attr(stage0, feature(dyn_trait))]
 #![feature(from_ref)]
 #![feature(fs_read_write)]
 #![cfg_attr(windows, feature(libc))]
@@ -58,6 +58,7 @@
 #![feature(nonzero)]
 #![feature(proc_macro_internals)]
 #![feature(quote)]
+#![feature(optin_builtin_traits)]
 #![feature(refcell_replace_swap)]
 #![feature(rustc_diagnostic_macros)]
 #![feature(slice_patterns)]
@@ -68,7 +69,7 @@
 #![feature(trusted_len)]
 #![feature(catch_expr)]
 #![feature(test)]
-#![feature(inclusive_range_fields)]
+#![feature(inclusive_range_methods)]
 
 #![recursion_limit="512"]
 
@@ -84,7 +85,6 @@ extern crate libc;
 extern crate rustc_target;
 #[macro_use] extern crate rustc_data_structures;
 extern crate serialize;
-extern crate rustc_const_math;
 extern crate rustc_errors as errors;
 #[macro_use] extern crate log;
 #[macro_use] extern crate syntax;
diff --git a/src/librustc/lint/levels.rs b/src/librustc/lint/levels.rs
index e8b536d5267..d158f52c643 100644
--- a/src/librustc/lint/levels.rs
+++ b/src/librustc/lint/levels.rs
@@ -198,7 +198,7 @@ impl<'a> LintLevelsBuilder<'a> {
                       "malformed lint attribute");
         };
         for attr in attrs {
-            let level = match attr.name().and_then(|name| Level::from_str(&name.as_str())) {
+            let level = match Level::from_str(&attr.name().as_str()) {
                 None => continue,
                 Some(lvl) => lvl,
             };
@@ -221,7 +221,7 @@ impl<'a> LintLevelsBuilder<'a> {
                         continue
                     }
                 };
-                let name = word.ident.name;
+                let name = word.name();
                 match store.check_lint_name(&name.as_str()) {
                     CheckLintNameResult::Ok(ids) => {
                         let src = LintSource::Node(name, li.span);
@@ -260,7 +260,7 @@ impl<'a> LintLevelsBuilder<'a> {
                                                 Some(li.span.into()),
                                                 &msg);
                         if name.as_str().chars().any(|c| c.is_uppercase()) {
-                            let name_lower = name.as_str().to_lowercase();
+                            let name_lower = name.as_str().to_lowercase().to_string();
                             if let CheckLintNameResult::NoLint =
                                     store.check_lint_name(&name_lower) {
                                 db.emit();
diff --git a/src/librustc/lint/mod.rs b/src/librustc/lint/mod.rs
index 0d4fd99995f..d6c6f9dc0f6 100644
--- a/src/librustc/lint/mod.rs
+++ b/src/librustc/lint/mod.rs
@@ -507,7 +507,7 @@ pub fn struct_lint_level<'a>(sess: &'a Session,
 
         let explanation = if lint_id == LintId::of(::lint::builtin::UNSTABLE_NAME_COLLISION) {
             "once this method is added to the standard library, \
-             there will be ambiguity here, which will cause a hard error!"
+             the ambiguity may cause an error or change in behavior!"
                 .to_owned()
         } else if let Some(edition) = future_incompatible.edition {
             format!("{} in the {} edition!", STANDARD_MESSAGE, edition)
diff --git a/src/librustc/middle/const_val.rs b/src/librustc/middle/const_val.rs
index 19a7576b7ce..0ecab50dda2 100644
--- a/src/librustc/middle/const_val.rs
+++ b/src/librustc/middle/const_val.rs
@@ -11,7 +11,6 @@
 use hir::def_id::DefId;
 use ty::{self, TyCtxt, layout};
 use ty::subst::Substs;
-use rustc_const_math::*;
 use mir::interpret::{Value, PrimVal};
 use errors::DiagnosticBuilder;
 
@@ -62,7 +61,6 @@ pub enum ErrKind<'tcx> {
     UnimplementedConstVal(&'static str),
     IndexOutOfBounds { len: u64, index: u64 },
 
-    Math(ConstMathErr),
     LayoutError(layout::LayoutError<'tcx>),
 
     TypeckError,
@@ -76,15 +74,6 @@ pub struct FrameInfo {
     pub location: String,
 }
 
-impl<'tcx> From<ConstMathErr> for ErrKind<'tcx> {
-    fn from(err: ConstMathErr) -> ErrKind<'tcx> {
-        match err {
-            ConstMathErr::UnsignedNegation => ErrKind::TypeckError,
-            _ => ErrKind::Math(err)
-        }
-    }
-}
-
 #[derive(Clone, Debug)]
 pub enum ConstEvalErrDescription<'a, 'tcx: 'a> {
     Simple(Cow<'a, str>),
@@ -122,7 +111,6 @@ impl<'a, 'gcx, 'tcx> ConstEvalErr<'tcx> {
                         len, index)
             }
 
-            Math(ref err) => Simple(err.description().into_cow()),
             LayoutError(ref err) => Simple(err.to_string().into_cow()),
 
             TypeckError => simple!("type-checking failed"),
diff --git a/src/librustc/middle/expr_use_visitor.rs b/src/librustc/middle/expr_use_visitor.rs
index 2cc5a4a8fe6..725fcf1e646 100644
--- a/src/librustc/middle/expr_use_visitor.rs
+++ b/src/librustc/middle/expr_use_visitor.rs
@@ -28,6 +28,7 @@ use ty::{self, TyCtxt, adjustment};
 
 use hir::{self, PatKind};
 use rustc_data_structures::sync::Lrc;
+use std::rc::Rc;
 use syntax::ast;
 use syntax::ptr::P;
 use syntax_pos::Span;
@@ -44,7 +45,7 @@ pub trait Delegate<'tcx> {
     fn consume(&mut self,
                consume_id: ast::NodeId,
                consume_span: Span,
-               cmt: mc::cmt<'tcx>,
+               cmt: &mc::cmt_<'tcx>,
                mode: ConsumeMode);
 
     // The value found at `cmt` has been determined to match the
@@ -61,14 +62,14 @@ pub trait Delegate<'tcx> {
     // called on a subpart of an input passed to `matched_pat).
     fn matched_pat(&mut self,
                    matched_pat: &hir::Pat,
-                   cmt: mc::cmt<'tcx>,
+                   cmt: &mc::cmt_<'tcx>,
                    mode: MatchMode);
 
     // The value found at `cmt` is either copied or moved via the
     // pattern binding `consume_pat`, depending on mode.
     fn consume_pat(&mut self,
                    consume_pat: &hir::Pat,
-                   cmt: mc::cmt<'tcx>,
+                   cmt: &mc::cmt_<'tcx>,
                    mode: ConsumeMode);
 
     // The value found at `borrow` is being borrowed at the point
@@ -76,7 +77,7 @@ pub trait Delegate<'tcx> {
     fn borrow(&mut self,
               borrow_id: ast::NodeId,
               borrow_span: Span,
-              cmt: mc::cmt<'tcx>,
+              cmt: &mc::cmt_<'tcx>,
               loan_region: ty::Region<'tcx>,
               bk: ty::BorrowKind,
               loan_cause: LoanCause);
@@ -90,7 +91,7 @@ pub trait Delegate<'tcx> {
     fn mutate(&mut self,
               assignment_id: ast::NodeId,
               assignment_span: Span,
-              assignee_cmt: mc::cmt<'tcx>,
+              assignee_cmt: &mc::cmt_<'tcx>,
               mode: MutateMode);
 }
 
@@ -316,11 +317,11 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
 
             let fn_body_scope_r =
                 self.tcx().mk_region(ty::ReScope(region::Scope::Node(body.value.hir_id.local_id)));
-            let arg_cmt = self.mc.cat_rvalue(
+            let arg_cmt = Rc::new(self.mc.cat_rvalue(
                 arg.id,
                 arg.pat.span,
                 fn_body_scope_r, // Args live only as long as the fn body.
-                arg_ty);
+                arg_ty));
 
             self.walk_irrefutable_pat(arg_cmt, &arg.pat);
         }
@@ -335,11 +336,11 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
     fn delegate_consume(&mut self,
                         consume_id: ast::NodeId,
                         consume_span: Span,
-                        cmt: mc::cmt<'tcx>) {
+                        cmt: &mc::cmt_<'tcx>) {
         debug!("delegate_consume(consume_id={}, cmt={:?})",
                consume_id, cmt);
 
-        let mode = copy_or_move(&self.mc, self.param_env, &cmt, DirectRefMove);
+        let mode = copy_or_move(&self.mc, self.param_env, cmt, DirectRefMove);
         self.delegate.consume(consume_id, consume_span, cmt, mode);
     }
 
@@ -353,7 +354,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
         debug!("consume_expr(expr={:?})", expr);
 
         let cmt = return_if_err!(self.mc.cat_expr(expr));
-        self.delegate_consume(expr.id, expr.span, cmt);
+        self.delegate_consume(expr.id, expr.span, &cmt);
         self.walk_expr(expr);
     }
 
@@ -362,7 +363,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
                    expr: &hir::Expr,
                    mode: MutateMode) {
         let cmt = return_if_err!(self.mc.cat_expr(expr));
-        self.delegate.mutate(assignment_expr.id, assignment_expr.span, cmt, mode);
+        self.delegate.mutate(assignment_expr.id, assignment_expr.span, &cmt, mode);
         self.walk_expr(expr);
     }
 
@@ -375,7 +376,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
                expr, r, bk);
 
         let cmt = return_if_err!(self.mc.cat_expr(expr));
-        self.delegate.borrow(expr.id, expr.span, cmt, r, bk, cause);
+        self.delegate.borrow(expr.id, expr.span, &cmt, r, bk, cause);
 
         self.walk_expr(expr)
     }
@@ -435,7 +436,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
             }
 
             hir::ExprMatch(ref discr, ref arms, _) => {
-                let discr_cmt = return_if_err!(self.mc.cat_expr(&discr));
+                let discr_cmt = Rc::new(return_if_err!(self.mc.cat_expr(&discr)));
                 let r = self.tcx().types.re_empty;
                 self.borrow_expr(&discr, r, ty::ImmBorrow, MatchDiscriminant);
 
@@ -619,7 +620,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
                 // "assigns", which is handled by
                 // `walk_pat`:
                 self.walk_expr(&expr);
-                let init_cmt = return_if_err!(self.mc.cat_expr(&expr));
+                let init_cmt = Rc::new(return_if_err!(self.mc.cat_expr(&expr)));
                 self.walk_irrefutable_pat(init_cmt, &local.pat);
             }
         }
@@ -652,7 +653,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
             None => { return; }
         };
 
-        let with_cmt = return_if_err!(self.mc.cat_expr(&with_expr));
+        let with_cmt = Rc::new(return_if_err!(self.mc.cat_expr(&with_expr)));
 
         // Select just those fields of the `with`
         // expression that will actually be used
@@ -671,7 +672,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
                             with_field.name,
                             with_field.ty(self.tcx(), substs)
                         );
-                        self.delegate_consume(with_expr.id, with_expr.span, cmt_field);
+                        self.delegate_consume(with_expr.id, with_expr.span, &cmt_field);
                     }
                 }
             }
@@ -710,7 +711,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
                 adjustment::Adjust::Unsize => {
                     // Creating a closure/fn-pointer or unsizing consumes
                     // the input and stores it into the resulting rvalue.
-                    self.delegate_consume(expr.id, expr.span, cmt.clone());
+                    self.delegate_consume(expr.id, expr.span, &cmt);
                 }
 
                 adjustment::Adjust::Deref(None) => {}
@@ -722,12 +723,11 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
                 // this is an autoref of `x`.
                 adjustment::Adjust::Deref(Some(ref deref)) => {
                     let bk = ty::BorrowKind::from_mutbl(deref.mutbl);
-                    self.delegate.borrow(expr.id, expr.span, cmt.clone(),
-                                         deref.region, bk, AutoRef);
+                    self.delegate.borrow(expr.id, expr.span, &cmt, deref.region, bk, AutoRef);
                 }
 
                 adjustment::Adjust::Borrow(ref autoref) => {
-                    self.walk_autoref(expr, cmt.clone(), autoref);
+                    self.walk_autoref(expr, &cmt, autoref);
                 }
             }
             cmt = return_if_err!(self.mc.cat_expr_adjusted(expr, cmt, &adjustment));
@@ -739,7 +739,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
     /// after all relevant autoderefs have occurred.
     fn walk_autoref(&mut self,
                     expr: &hir::Expr,
-                    cmt_base: mc::cmt<'tcx>,
+                    cmt_base: &mc::cmt_<'tcx>,
                     autoref: &adjustment::AutoBorrow<'tcx>) {
         debug!("walk_autoref(expr.id={} cmt_base={:?} autoref={:?})",
                expr.id,
@@ -852,7 +852,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
                 // Each match binding is effectively an assignment to the
                 // binding being produced.
                 let def = Def::Local(canonical_id);
-                if let Ok(binding_cmt) = mc.cat_def(pat.id, pat.span, pat_ty, def) {
+                if let Ok(ref binding_cmt) = mc.cat_def(pat.id, pat.span, pat_ty, def) {
                     delegate.mutate(pat.id, pat.span, binding_cmt, MutateMode::Init);
                 }
 
@@ -861,13 +861,13 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
                     ty::BindByReference(m) => {
                         if let ty::TyRef(r, _) = pat_ty.sty {
                             let bk = ty::BorrowKind::from_mutbl(m);
-                            delegate.borrow(pat.id, pat.span, cmt_pat, r, bk, RefBinding);
+                            delegate.borrow(pat.id, pat.span, &cmt_pat, r, bk, RefBinding);
                         }
                     }
                     ty::BindByValue(..) => {
                         let mode = copy_or_move(mc, param_env, &cmt_pat, PatBindingMove);
                         debug!("walk_pat binding consuming pat");
-                        delegate.consume_pat(pat, cmt_pat, mode);
+                        delegate.consume_pat(pat, &cmt_pat, mode);
                     }
                 }
             }
@@ -891,12 +891,12 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
                     let downcast_cmt = mc.cat_downcast_if_needed(pat, cmt_pat, variant_did);
 
                     debug!("variant downcast_cmt={:?} pat={:?}", downcast_cmt, pat);
-                    delegate.matched_pat(pat, downcast_cmt, match_mode);
+                    delegate.matched_pat(pat, &downcast_cmt, match_mode);
                 }
                 Def::Struct(..) | Def::StructCtor(..) | Def::Union(..) |
                 Def::TyAlias(..) | Def::AssociatedTy(..) | Def::SelfTy(..) => {
                     debug!("struct cmt_pat={:?} pat={:?}", cmt_pat, pat);
-                    delegate.matched_pat(pat, cmt_pat, match_mode);
+                    delegate.matched_pat(pat, &cmt_pat, match_mode);
                 }
                 _ => {}
             }
@@ -924,12 +924,12 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
                                                 self.param_env,
                                                 &cmt_var,
                                                 CaptureMove);
-                        self.delegate.consume(closure_expr.id, freevar.span, cmt_var, mode);
+                        self.delegate.consume(closure_expr.id, freevar.span, &cmt_var, mode);
                     }
                     ty::UpvarCapture::ByRef(upvar_borrow) => {
                         self.delegate.borrow(closure_expr.id,
                                              fn_decl_span,
-                                             cmt_var,
+                                             &cmt_var,
                                              upvar_borrow.region,
                                              upvar_borrow.kind,
                                              ClosureCapture(freevar.span));
@@ -943,7 +943,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
                         closure_id: ast::NodeId,
                         closure_span: Span,
                         upvar: &hir::Freevar)
-                        -> mc::McResult<mc::cmt<'tcx>> {
+                        -> mc::McResult<mc::cmt_<'tcx>> {
         // Create the cmt for the variable being borrowed, from the
         // caller's perspective
         let var_hir_id = self.tcx().hir.node_to_hir_id(upvar.var_id());
@@ -954,7 +954,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
 
 fn copy_or_move<'a, 'gcx, 'tcx>(mc: &mc::MemCategorizationContext<'a, 'gcx, 'tcx>,
                                 param_env: ty::ParamEnv<'tcx>,
-                                cmt: &mc::cmt<'tcx>,
+                                cmt: &mc::cmt_<'tcx>,
                                 move_reason: MoveReason)
                                 -> ConsumeMode
 {
diff --git a/src/librustc/middle/liveness.rs b/src/librustc/middle/liveness.rs
index 17c114bc3b3..d1a46f5f155 100644
--- a/src/librustc/middle/liveness.rs
+++ b/src/librustc/middle/liveness.rs
@@ -111,6 +111,7 @@ use ty::{self, TyCtxt};
 use lint;
 use util::nodemap::{NodeMap, NodeSet};
 
+use std::collections::VecDeque;
 use std::{fmt, usize};
 use std::io::prelude::*;
 use std::io;
@@ -412,18 +413,43 @@ fn visit_local<'a, 'tcx>(ir: &mut IrMaps<'a, 'tcx>, local: &'tcx hir::Local) {
 }
 
 fn visit_arm<'a, 'tcx>(ir: &mut IrMaps<'a, 'tcx>, arm: &'tcx hir::Arm) {
-    for pat in &arm.pats {
-        // for struct patterns, take note of which fields used shorthand (`x` rather than `x: x`)
+    for mut pat in &arm.pats {
+        // For struct patterns, take note of which fields used shorthand
+        // (`x` rather than `x: x`).
         //
-        // FIXME: according to the rust-lang-nursery/rustc-guide book, `NodeId`s are to be phased
-        // out in favor of `HirId`s; however, we need to match the signature of `each_binding`,
-        // which uses `NodeIds`.
+        // FIXME: according to the rust-lang-nursery/rustc-guide book, `NodeId`s are to be
+        // phased out in favor of `HirId`s; however, we need to match the signature of
+        // `each_binding`, which uses `NodeIds`.
         let mut shorthand_field_ids = NodeSet();
-        if let hir::PatKind::Struct(_, ref fields, _) = pat.node {
-            for field in fields {
-                if field.node.is_shorthand {
-                    shorthand_field_ids.insert(field.node.pat.id);
+        let mut pats = VecDeque::new();
+        pats.push_back(pat);
+        while let Some(pat) = pats.pop_front() {
+            use hir::PatKind::*;
+            match pat.node {
+                Binding(_, _, _, ref inner_pat) => {
+                    pats.extend(inner_pat.iter());
                 }
+                Struct(_, ref fields, _) => {
+                    for field in fields {
+                        if field.node.is_shorthand {
+                            shorthand_field_ids.insert(field.node.pat.id);
+                        }
+                    }
+                }
+                Ref(ref inner_pat, _) |
+                Box(ref inner_pat) => {
+                    pats.push_back(inner_pat);
+                }
+                TupleStruct(_, ref inner_pats, _) |
+                Tuple(ref inner_pats, _) => {
+                    pats.extend(inner_pats.iter());
+                }
+                Slice(ref pre_pats, ref inner_pat, ref post_pats) => {
+                    pats.extend(pre_pats.iter());
+                    pats.extend(inner_pat.iter());
+                    pats.extend(post_pats.iter());
+                }
+                _ => {}
             }
         }
 
diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index 6f41f07dce8..f40a41cd299 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -572,13 +572,13 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
         Ok(ret_ty)
     }
 
-    pub fn cat_expr(&self, expr: &hir::Expr) -> McResult<cmt<'tcx>> {
+    pub fn cat_expr(&self, expr: &hir::Expr) -> McResult<cmt_<'tcx>> {
         // This recursion helper avoids going through *too many*
         // adjustments, since *only* non-overloaded deref recurses.
         fn helper<'a, 'gcx, 'tcx>(mc: &MemCategorizationContext<'a, 'gcx, 'tcx>,
                                   expr: &hir::Expr,
                                   adjustments: &[adjustment::Adjustment<'tcx>])
-                                   -> McResult<cmt<'tcx>> {
+                                   -> McResult<cmt_<'tcx>> {
             match adjustments.split_last() {
                 None => mc.cat_expr_unadjusted(expr),
                 Some((adjustment, previous)) => {
@@ -591,24 +591,24 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
     }
 
     pub fn cat_expr_adjusted(&self, expr: &hir::Expr,
-                             previous: cmt<'tcx>,
+                             previous: cmt_<'tcx>,
                              adjustment: &adjustment::Adjustment<'tcx>)
-                             -> McResult<cmt<'tcx>> {
+                             -> McResult<cmt_<'tcx>> {
         self.cat_expr_adjusted_with(expr, || Ok(previous), adjustment)
     }
 
     fn cat_expr_adjusted_with<F>(&self, expr: &hir::Expr,
                                  previous: F,
                                  adjustment: &adjustment::Adjustment<'tcx>)
-                                 -> McResult<cmt<'tcx>>
-        where F: FnOnce() -> McResult<cmt<'tcx>>
+                                 -> McResult<cmt_<'tcx>>
+        where F: FnOnce() -> McResult<cmt_<'tcx>>
     {
         debug!("cat_expr_adjusted_with({:?}): {:?}", adjustment, expr);
         let target = self.resolve_type_vars_if_possible(&adjustment.target);
         match adjustment.kind {
             adjustment::Adjust::Deref(overloaded) => {
                 // Equivalent to *expr or something similar.
-                let base = if let Some(deref) = overloaded {
+                let base = Rc::new(if let Some(deref) = overloaded {
                     let ref_ty = self.tcx.mk_ref(deref.region, ty::TypeAndMut {
                         ty: target,
                         mutbl: deref.mutbl,
@@ -616,7 +616,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                     self.cat_rvalue_node(expr.id, expr.span, ref_ty)
                 } else {
                     previous()?
-                };
+                });
                 self.cat_deref(expr, base, false)
             }
 
@@ -633,7 +633,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
         }
     }
 
-    pub fn cat_expr_unadjusted(&self, expr: &hir::Expr) -> McResult<cmt<'tcx>> {
+    pub fn cat_expr_unadjusted(&self, expr: &hir::Expr) -> McResult<cmt_<'tcx>> {
         debug!("cat_expr: id={} expr={:?}", expr.id, expr);
 
         let expr_ty = self.expr_ty(expr)?;
@@ -642,13 +642,13 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
             if self.tables.is_method_call(expr) {
                 self.cat_overloaded_place(expr, e_base, false)
             } else {
-                let base_cmt = self.cat_expr(&e_base)?;
+                let base_cmt = Rc::new(self.cat_expr(&e_base)?);
                 self.cat_deref(expr, base_cmt, false)
             }
           }
 
           hir::ExprField(ref base, f_name) => {
-            let base_cmt = self.cat_expr(&base)?;
+            let base_cmt = Rc::new(self.cat_expr(&base)?);
             debug!("cat_expr(cat_field): id={} expr={:?} base={:?}",
                    expr.id,
                    expr,
@@ -666,7 +666,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                 // dereferencing.
                 self.cat_overloaded_place(expr, base, true)
             } else {
-                let base_cmt = self.cat_expr(&base)?;
+                let base_cmt = Rc::new(self.cat_expr(&base)?);
                 self.cat_index(expr, base_cmt, expr_ty, InteriorOffsetKind::Index)
             }
           }
@@ -701,7 +701,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                    span: Span,
                    expr_ty: Ty<'tcx>,
                    def: Def)
-                   -> McResult<cmt<'tcx>> {
+                   -> McResult<cmt_<'tcx>> {
         debug!("cat_def: id={} expr={:?} def={:?}",
                id, expr_ty, def);
 
@@ -718,14 +718,14 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                     return Ok(self.cat_rvalue_node(id, span, expr_ty));
                 }
             }
-              Ok(Rc::new(cmt_ {
+              Ok(cmt_ {
                   id:id,
                   span:span,
                   cat:Categorization::StaticItem,
                   mutbl: if mutbl { McDeclared } else { McImmutable},
                   ty:expr_ty,
                   note: NoteNone
-              }))
+              })
           }
 
           Def::Upvar(var_id, _, fn_node_id) => {
@@ -733,14 +733,14 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
           }
 
           Def::Local(vid) => {
-            Ok(Rc::new(cmt_ {
+            Ok(cmt_ {
                 id,
                 span,
                 cat: Categorization::Local(vid),
                 mutbl: MutabilityCategory::from_local(self.tcx, self.tables, vid),
                 ty: expr_ty,
                 note: NoteNone
-            }))
+            })
           }
 
           def => span_bug!(span, "unexpected definition in memory categorization: {:?}", def)
@@ -754,7 +754,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                  span: Span,
                  var_id: ast::NodeId,
                  fn_node_id: ast::NodeId)
-                 -> McResult<cmt<'tcx>>
+                 -> McResult<cmt_<'tcx>>
     {
         let fn_hir_id = self.tcx.hir.node_to_hir_id(fn_node_id);
 
@@ -861,7 +861,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
             }
         };
 
-        let ret = Rc::new(cmt_result);
+        let ret = cmt_result;
         debug!("cat_upvar ret={:?}", ret);
         Ok(ret)
     }
@@ -938,7 +938,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                            id: ast::NodeId,
                            span: Span,
                            expr_ty: Ty<'tcx>)
-                           -> cmt<'tcx> {
+                           -> cmt_<'tcx> {
         let hir_id = self.tcx.hir.node_to_hir_id(id);
         let promotable = self.rvalue_promotable_map.as_ref().map(|m| m.contains(&hir_id.local_id))
                                                             .unwrap_or(false);
@@ -966,15 +966,15 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                       cmt_id: ast::NodeId,
                       span: Span,
                       temp_scope: ty::Region<'tcx>,
-                      expr_ty: Ty<'tcx>) -> cmt<'tcx> {
-        let ret = Rc::new(cmt_ {
+                      expr_ty: Ty<'tcx>) -> cmt_<'tcx> {
+        let ret = cmt_ {
             id:cmt_id,
             span:span,
             cat:Categorization::Rvalue(temp_scope),
             mutbl:McDeclared,
             ty:expr_ty,
             note: NoteNone
-        });
+        };
         debug!("cat_rvalue ret {:?}", ret);
         ret
     }
@@ -985,15 +985,15 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                                  f_index: usize,
                                  f_name: Name,
                                  f_ty: Ty<'tcx>)
-                                 -> cmt<'tcx> {
-        let ret = Rc::new(cmt_ {
+                                 -> cmt_<'tcx> {
+        let ret = cmt_ {
             id: node.id(),
             span: node.span(),
             mutbl: base_cmt.mutbl.inherit(),
             cat: Categorization::Interior(base_cmt, InteriorField(FieldIndex(f_index, f_name))),
             ty: f_ty,
             note: NoteNone
-        });
+        };
         debug!("cat_field ret {:?}", ret);
         ret
     }
@@ -1002,7 +1002,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                              expr: &hir::Expr,
                              base: &hir::Expr,
                              implicit: bool)
-                             -> McResult<cmt<'tcx>> {
+                             -> McResult<cmt_<'tcx>> {
         debug!("cat_overloaded_place: implicit={}", implicit);
 
         // Reconstruct the output assuming it's a reference with the
@@ -1022,7 +1022,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
             mutbl,
         });
 
-        let base_cmt = self.cat_rvalue_node(expr.id, expr.span, ref_ty);
+        let base_cmt = Rc::new(self.cat_rvalue_node(expr.id, expr.span, ref_ty));
         self.cat_deref(expr, base_cmt, implicit)
     }
 
@@ -1030,7 +1030,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                                  node: &N,
                                  base_cmt: cmt<'tcx>,
                                  implicit: bool)
-                                 -> McResult<cmt<'tcx>> {
+                                 -> McResult<cmt_<'tcx>> {
         debug!("cat_deref: base_cmt={:?}", base_cmt);
 
         let base_cmt_ty = base_cmt.ty;
@@ -1052,7 +1052,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
             }
             ref ty => bug!("unexpected type in cat_deref: {:?}", ty)
         };
-        let ret = Rc::new(cmt_ {
+        let ret = cmt_ {
             id: node.id(),
             span: node.span(),
             // For unique ptrs, we inherit mutability from the owning reference.
@@ -1060,7 +1060,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
             cat: Categorization::Deref(base_cmt, ptr),
             ty: deref_ty,
             note: NoteNone
-        });
+        };
         debug!("cat_deref ret {:?}", ret);
         Ok(ret)
     }
@@ -1070,7 +1070,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                              base_cmt: cmt<'tcx>,
                              element_ty: Ty<'tcx>,
                              context: InteriorOffsetKind)
-                             -> McResult<cmt<'tcx>> {
+                             -> McResult<cmt_<'tcx>> {
         //! Creates a cmt for an indexing operation (`[]`).
         //!
         //! One subtle aspect of indexing that may not be
@@ -1089,8 +1089,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
         //! - `base_cmt`: the cmt of `elt`
 
         let interior_elem = InteriorElement(context);
-        let ret =
-            self.cat_imm_interior(elt, base_cmt, element_ty, interior_elem);
+        let ret = self.cat_imm_interior(elt, base_cmt, element_ty, interior_elem);
         debug!("cat_index ret {:?}", ret);
         return Ok(ret);
     }
@@ -1100,15 +1099,15 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                                         base_cmt: cmt<'tcx>,
                                         interior_ty: Ty<'tcx>,
                                         interior: InteriorKind)
-                                        -> cmt<'tcx> {
-        let ret = Rc::new(cmt_ {
+                                        -> cmt_<'tcx> {
+        let ret = cmt_ {
             id: node.id(),
             span: node.span(),
             mutbl: base_cmt.mutbl.inherit(),
             cat: Categorization::Interior(base_cmt, interior),
             ty: interior_ty,
             note: NoteNone
-        });
+        };
         debug!("cat_imm_interior ret={:?}", ret);
         ret
     }
@@ -1232,7 +1231,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                         .get(pat.hir_id)
                         .map(|v| v.len())
                         .unwrap_or(0) {
-            cmt = self.cat_deref(pat, cmt, true /* implicit */)?;
+            cmt = Rc::new(self.cat_deref(pat, cmt, true /* implicit */)?);
         }
         let cmt = cmt; // lose mutability
 
@@ -1279,7 +1278,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
             for (i, subpat) in subpats.iter().enumerate_and_adjust(expected_len, ddpos) {
                 let subpat_ty = self.pat_ty(&subpat)?; // see (*2)
                 let interior = InteriorField(FieldIndex(i, Name::intern(&i.to_string())));
-                let subcmt = self.cat_imm_interior(pat, cmt.clone(), subpat_ty, interior);
+                let subcmt = Rc::new(self.cat_imm_interior(pat, cmt.clone(), subpat_ty, interior));
                 self.cat_pattern_(subcmt, &subpat, op)?;
             }
           }
@@ -1302,7 +1301,8 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
             for fp in field_pats {
                 let field_ty = self.pat_ty(&fp.node.pat)?; // see (*2)
                 let f_index = self.tcx.field_index(fp.node.id, self.tables);
-                let cmt_field = self.cat_field(pat, cmt.clone(), f_index, fp.node.name, field_ty);
+                let cmt_field =
+                    Rc::new(self.cat_field(pat, cmt.clone(), f_index, fp.node.name, field_ty));
                 self.cat_pattern_(cmt_field, &fp.node.pat, op)?;
             }
           }
@@ -1320,7 +1320,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
             for (i, subpat) in subpats.iter().enumerate_and_adjust(expected_len, ddpos) {
                 let subpat_ty = self.pat_ty(&subpat)?; // see (*2)
                 let interior = InteriorField(FieldIndex(i, Name::intern(&i.to_string())));
-                let subcmt = self.cat_imm_interior(pat, cmt.clone(), subpat_ty, interior);
+                let subcmt = Rc::new(self.cat_imm_interior(pat, cmt.clone(), subpat_ty, interior));
                 self.cat_pattern_(subcmt, &subpat, op)?;
             }
           }
@@ -1329,7 +1329,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
             // box p1, &p1, &mut p1.  we can ignore the mutability of
             // PatKind::Ref since that information is already contained
             // in the type.
-            let subcmt = self.cat_deref(pat, cmt, false)?;
+            let subcmt = Rc::new(self.cat_deref(pat, cmt, false)?);
             self.cat_pattern_(subcmt, &subpat, op)?;
           }
 
@@ -1342,7 +1342,7 @@ impl<'a, 'gcx, 'tcx> MemCategorizationContext<'a, 'gcx, 'tcx> {
                 }
             };
             let context = InteriorOffsetKind::Pattern;
-            let elt_cmt = self.cat_index(pat, cmt, element_ty, context)?;
+            let elt_cmt = Rc::new(self.cat_index(pat, cmt, element_ty, context)?);
             for before_pat in before {
                 self.cat_pattern_(elt_cmt.clone(), &before_pat, op)?;
             }
@@ -1379,7 +1379,7 @@ pub enum AliasableReason {
 }
 
 impl<'tcx> cmt_<'tcx> {
-    pub fn guarantor(&self) -> cmt<'tcx> {
+    pub fn guarantor(&self) -> cmt_<'tcx> {
         //! Returns `self` after stripping away any derefs or
         //! interior content. The return value is basically the `cmt` which
         //! determines how long the value in `self` remains live.
@@ -1392,7 +1392,7 @@ impl<'tcx> cmt_<'tcx> {
             Categorization::Deref(_, BorrowedPtr(..)) |
             Categorization::Deref(_, Implicit(..)) |
             Categorization::Upvar(..) => {
-                Rc::new((*self).clone())
+                (*self).clone()
             }
             Categorization::Downcast(ref b, _) |
             Categorization::Interior(ref b, _) |
@@ -1442,16 +1442,17 @@ impl<'tcx> cmt_<'tcx> {
         }
     }
 
-    // Digs down through one or two layers of deref and grabs the cmt
-    // for the upvar if a note indicates there is one.
-    pub fn upvar(&self) -> Option<cmt<'tcx>> {
+    // Digs down through one or two layers of deref and grabs the
+    // Categorization of the cmt for the upvar if a note indicates there is
+    // one.
+    pub fn upvar_cat(&self) -> Option<&Categorization<'tcx>> {
         match self.note {
             NoteClosureEnv(..) | NoteUpvarRef(..) => {
                 Some(match self.cat {
                     Categorization::Deref(ref inner, _) => {
                         match inner.cat {
-                            Categorization::Deref(ref inner, _) => inner.clone(),
-                            Categorization::Upvar(..) => inner.clone(),
+                            Categorization::Deref(ref inner, _) => &inner.cat,
+                            Categorization::Upvar(..) => &inner.cat,
                             _ => bug!()
                         }
                     }
@@ -1462,7 +1463,6 @@ impl<'tcx> cmt_<'tcx> {
         }
     }
 
-
     pub fn descriptive_string(&self, tcx: TyCtxt) -> String {
         match self.cat {
             Categorization::StaticItem => {
@@ -1479,8 +1479,7 @@ impl<'tcx> cmt_<'tcx> {
                 }
             }
             Categorization::Deref(_, pk) => {
-                let upvar = self.upvar();
-                match upvar.as_ref().map(|i| &i.cat) {
+                match self.upvar_cat() {
                     Some(&Categorization::Upvar(ref var)) => {
                         var.to_string()
                     }
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index 5f4efbeeaa8..bfc9ff6660d 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -690,21 +690,22 @@ impl<'tcx> ScopeTree {
         // the start. So this algorithm is faster.
         let mut ma = Some(scope_a);
         let mut mb = Some(scope_b);
-        let mut seen: SmallVec<[Scope; 32]> = SmallVec::new();
+        let mut seen_a: SmallVec<[Scope; 32]> = SmallVec::new();
+        let mut seen_b: SmallVec<[Scope; 32]> = SmallVec::new();
         loop {
             if let Some(a) = ma {
-                if seen.iter().position(|s| *s == a).is_some() {
+                if seen_b.iter().position(|s| *s == a).is_some() {
                     return a;
                 }
-                seen.push(a);
+                seen_a.push(a);
                 ma = self.parent_map.get(&a).map(|s| *s);
             }
 
             if let Some(b) = mb {
-                if seen.iter().position(|s| *s == b).is_some() {
+                if seen_a.iter().position(|s| *s == b).is_some() {
                     return b;
                 }
-                seen.push(b);
+                seen_b.push(b);
                 mb = self.parent_map.get(&b).map(|s| *s);
             }
 
diff --git a/src/librustc/middle/stability.rs b/src/librustc/middle/stability.rs
index 328b2db2b58..279908d2b67 100644
--- a/src/librustc/middle/stability.rs
+++ b/src/librustc/middle/stability.rs
@@ -205,7 +205,7 @@ impl<'a, 'tcx: 'a> Annotator<'a, 'tcx> {
         } else {
             // Emit errors for non-staged-api crates.
             for attr in attrs {
-                let tag = unwrap_or!(attr.name(), continue);
+                let tag = attr.name();
                 if tag == "unstable" || tag == "stable" || tag == "rustc_deprecated" {
                     attr::mark_used(attr);
                     self.tcx.sess.span_err(attr.span(), "stability attributes may not be used \
diff --git a/src/librustc/mir/cache.rs b/src/librustc/mir/cache.rs
index 1ed5a22257c..41ba526b73f 100644
--- a/src/librustc/mir/cache.rs
+++ b/src/librustc/mir/cache.rs
@@ -68,7 +68,7 @@ fn calculate_predecessors(mir: &Mir) -> IndexVec<BasicBlock, Vec<BasicBlock>> {
     let mut result = IndexVec::from_elem(vec![], mir.basic_blocks());
     for (bb, data) in mir.basic_blocks().iter_enumerated() {
         if let Some(ref term) = data.terminator {
-            for &tgt in term.successors().iter() {
+            for &tgt in term.successors() {
                 result[tgt].push(bb);
             }
         }
diff --git a/src/librustc/mir/interpret/error.rs b/src/librustc/mir/interpret/error.rs
index b919f4d15a8..1e1d50c3fc0 100644
--- a/src/librustc/mir/interpret/error.rs
+++ b/src/librustc/mir/interpret/error.rs
@@ -1,4 +1,3 @@
-use std::error::Error;
 use std::{fmt, env};
 
 use mir;
@@ -8,18 +7,16 @@ use super::{
     MemoryPointer, Lock, AccessKind
 };
 
-use rustc_const_math::ConstMathErr;
-use syntax::codemap::Span;
 use backtrace::Backtrace;
 
 #[derive(Debug, Clone)]
 pub struct EvalError<'tcx> {
-    pub kind: EvalErrorKind<'tcx>,
+    pub kind: EvalErrorKind<'tcx, u64>,
     pub backtrace: Option<Backtrace>,
 }
 
-impl<'tcx> From<EvalErrorKind<'tcx>> for EvalError<'tcx> {
-    fn from(kind: EvalErrorKind<'tcx>) -> Self {
+impl<'tcx> From<EvalErrorKind<'tcx, u64>> for EvalError<'tcx> {
+    fn from(kind: EvalErrorKind<'tcx, u64>) -> Self {
         let backtrace = match env::var("MIRI_BACKTRACE") {
             Ok(ref val) if !val.is_empty() => Some(Backtrace::new_unresolved()),
             _ => None
@@ -31,8 +28,10 @@ impl<'tcx> From<EvalErrorKind<'tcx>> for EvalError<'tcx> {
     }
 }
 
-#[derive(Debug, Clone)]
-pub enum EvalErrorKind<'tcx> {
+pub type AssertMessage<'tcx> = EvalErrorKind<'tcx, mir::Operand<'tcx>>;
+
+#[derive(Clone, RustcEncodable, RustcDecodable)]
+pub enum EvalErrorKind<'tcx, O> {
     /// This variant is used by machines to signal their own errors that do not
     /// match an existing variant
     MachineError(String),
@@ -60,10 +59,12 @@ pub enum EvalErrorKind<'tcx> {
     Unimplemented(String),
     DerefFunctionPointer,
     ExecuteMemory,
-    ArrayIndexOutOfBounds(Span, u64, u64),
-    Math(Span, ConstMathErr),
+    BoundsCheck { len: O, index: O },
+    Overflow(mir::BinOp),
+    OverflowNeg,
+    DivisionByZero,
+    RemainderByZero,
     Intrinsic(String),
-    OverflowingMath,
     InvalidChar(u128),
     StackFrameLimitReached,
     OutOfTls,
@@ -121,14 +122,16 @@ pub enum EvalErrorKind<'tcx> {
     /// Cannot compute this constant because it depends on another one
     /// which already produced an error
     ReferencedConstant,
+    GeneratorResumedAfterReturn,
+    GeneratorResumedAfterPanic,
 }
 
 pub type EvalResult<'tcx, T = ()> = Result<T, EvalError<'tcx>>;
 
-impl<'tcx> Error for EvalError<'tcx> {
-    fn description(&self) -> &str {
+impl<'tcx, O> EvalErrorKind<'tcx, O> {
+    pub fn description(&self) -> &str {
         use self::EvalErrorKind::*;
-        match self.kind {
+        match *self {
             MachineError(ref inner) => inner,
             FunctionPointerTyMismatch(..) =>
                 "tried to call a function through a function pointer of a different type",
@@ -175,14 +178,10 @@ impl<'tcx> Error for EvalError<'tcx> {
                 "tried to dereference a function pointer",
             ExecuteMemory =>
                 "tried to treat a memory pointer as a function pointer",
-            ArrayIndexOutOfBounds(..) =>
+            BoundsCheck{..} =>
                 "array index out of bounds",
-            Math(..) =>
-                "mathematical operation failed",
             Intrinsic(..) =>
                 "intrinsic failed",
-            OverflowingMath =>
-                "attempted to do overflowing math",
             NoMirFor(..) =>
                 "mir not found",
             InvalidChar(..) =>
@@ -232,7 +231,7 @@ impl<'tcx> Error for EvalError<'tcx> {
                 "the evaluated program panicked",
             ReadFromReturnPointer =>
                 "tried to read from the return pointer",
-            EvalErrorKind::PathNotFound(_) =>
+            PathNotFound(_) =>
                 "a path could not be resolved, maybe the crate is not loaded",
             UnimplementedTraitSelection =>
                 "there were unresolved type arguments during trait selection",
@@ -240,14 +239,33 @@ impl<'tcx> Error for EvalError<'tcx> {
                 "encountered constants with type errors, stopping evaluation",
             ReferencedConstant =>
                 "referenced constant has errors",
+            Overflow(mir::BinOp::Add) => "attempt to add with overflow",
+            Overflow(mir::BinOp::Sub) => "attempt to subtract with overflow",
+            Overflow(mir::BinOp::Mul) => "attempt to multiply with overflow",
+            Overflow(mir::BinOp::Div) => "attempt to divide with overflow",
+            Overflow(mir::BinOp::Rem) => "attempt to calculate the remainder with overflow",
+            OverflowNeg => "attempt to negate with overflow",
+            Overflow(mir::BinOp::Shr) => "attempt to shift right with overflow",
+            Overflow(mir::BinOp::Shl) => "attempt to shift left with overflow",
+            Overflow(op) => bug!("{:?} cannot overflow", op),
+            DivisionByZero => "attempt to divide by zero",
+            RemainderByZero => "attempt to calculate the remainder with a divisor of zero",
+            GeneratorResumedAfterReturn => "generator resumed after completion",
+            GeneratorResumedAfterPanic => "generator resumed after panicking",
         }
     }
 }
 
 impl<'tcx> fmt::Display for EvalError<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{:?}", self.kind)
+    }
+}
+
+impl<'tcx, O: fmt::Debug> fmt::Debug for EvalErrorKind<'tcx, O> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         use self::EvalErrorKind::*;
-        match self.kind {
+        match *self {
             PointerOutOfBounds { ptr, access, allocation_size } => {
                 write!(f, "{} at offset {}, outside bounds of allocation {} which has size {}",
                        if access { "memory access" } else { "pointer computed" },
@@ -275,14 +293,12 @@ impl<'tcx> fmt::Display for EvalError<'tcx> {
             NoMirFor(ref func) => write!(f, "no mir for `{}`", func),
             FunctionPointerTyMismatch(sig, got) =>
                 write!(f, "tried to call a function with sig {} through a function pointer of type {}", sig, got),
-            ArrayIndexOutOfBounds(span, len, index) =>
-                write!(f, "index out of bounds: the len is {} but the index is {} at {:?}", len, index, span),
+            BoundsCheck { ref len, ref index } =>
+                write!(f, "index out of bounds: the len is {:?} but the index is {:?}", len, index),
             ReallocatedWrongMemoryKind(ref old, ref new) =>
                 write!(f, "tried to reallocate memory from {} to {}", old, new),
             DeallocatedWrongMemoryKind(ref old, ref new) =>
                 write!(f, "tried to deallocate {} memory but gave {} as the kind", old, new),
-            Math(_, ref err) =>
-                write!(f, "{}", err.description()),
             Intrinsic(ref err) =>
                 write!(f, "{}", err),
             InvalidChar(c) =>
diff --git a/src/librustc/mir/interpret/mod.rs b/src/librustc/mir/interpret/mod.rs
index c9eed0e4a28..546c7a920d5 100644
--- a/src/librustc/mir/interpret/mod.rs
+++ b/src/librustc/mir/interpret/mod.rs
@@ -8,7 +8,7 @@ macro_rules! err {
 mod error;
 mod value;
 
-pub use self::error::{EvalError, EvalResult, EvalErrorKind};
+pub use self::error::{EvalError, EvalResult, EvalErrorKind, AssertMessage};
 
 pub use self::value::{PrimVal, PrimValKind, Value, Pointer};
 
@@ -23,7 +23,7 @@ use std::iter;
 use syntax::ast::Mutability;
 use rustc_serialize::{Encoder, Decoder, Decodable, Encodable};
 
-#[derive(Clone, Debug, PartialEq)]
+#[derive(Clone, Debug, PartialEq, RustcEncodable, RustcDecodable)]
 pub enum Lock {
     NoLock,
     WriteLock(DynamicLifetime),
@@ -31,13 +31,13 @@ pub enum Lock {
     ReadLock(Vec<DynamicLifetime>),
 }
 
-#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 pub struct DynamicLifetime {
     pub frame: usize,
     pub region: Option<region::Scope>, // "None" indicates "until the function ends"
 }
 
-#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+#[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 pub enum AccessKind {
     Read,
     Write,
@@ -88,12 +88,12 @@ pub trait PointerArithmetic: layout::HasDataLayout {
 
     fn signed_offset<'tcx>(self, val: u64, i: i64) -> EvalResult<'tcx, u64> {
         let (res, over) = self.overflowing_signed_offset(val, i as i128);
-        if over { err!(OverflowingMath) } else { Ok(res) }
+        if over { err!(Overflow(mir::BinOp::Add)) } else { Ok(res) }
     }
 
     fn offset<'tcx>(self, val: u64, i: u64) -> EvalResult<'tcx, u64> {
         let (res, over) = self.overflowing_offset(val, i);
-        if over { err!(OverflowingMath) } else { Ok(res) }
+        if over { err!(Overflow(mir::BinOp::Add)) } else { Ok(res) }
     }
 
     fn wrapping_signed_offset(self, val: u64, i: i64) -> u64 {
diff --git a/src/librustc/mir/mod.rs b/src/librustc/mir/mod.rs
index c525c4ed651..37f6d47ff84 100644
--- a/src/librustc/mir/mod.rs
+++ b/src/librustc/mir/mod.rs
@@ -15,17 +15,17 @@
 use graphviz::IntoCow;
 use middle::const_val::ConstVal;
 use middle::region;
-use rustc_const_math::ConstMathErr;
 use rustc_data_structures::sync::{Lrc};
 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
 use rustc_data_structures::control_flow_graph::dominators::{Dominators, dominators};
 use rustc_data_structures::control_flow_graph::{GraphPredecessors, GraphSuccessors};
 use rustc_data_structures::control_flow_graph::ControlFlowGraph;
+use rustc_data_structures::small_vec::SmallVec;
 use rustc_serialize as serialize;
 use hir::def::CtorKind;
 use hir::def_id::DefId;
 use mir::visit::MirVisitable;
-use mir::interpret::{Value, PrimVal};
+use mir::interpret::{Value, PrimVal, EvalErrorKind};
 use ty::subst::{Subst, Substs};
 use ty::{self, AdtDef, CanonicalTy, ClosureSubsts, Region, Ty, TyCtxt, GeneratorInterior};
 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
@@ -36,12 +36,16 @@ use hir::{self, InlineAsm};
 use std::borrow::{Cow};
 use rustc_data_structures::sync::ReadGuard;
 use std::fmt::{self, Debug, Formatter, Write};
-use std::{iter, mem, u32};
+use std::{iter, mem, option, u32};
 use std::ops::{Index, IndexMut};
 use std::vec::IntoIter;
 use syntax::ast::{self, Name};
 use syntax::symbol::InternedString;
 use syntax_pos::{Span, DUMMY_SP};
+use rustc_apfloat::ieee::{Single, Double};
+use rustc_apfloat::Float;
+
+pub use mir::interpret::AssertMessage;
 
 mod cache;
 pub mod tcx;
@@ -247,6 +251,22 @@ impl<'tcx> Mir<'tcx> {
         })
     }
 
+    /// Returns an iterator over all user-declared mutable arguments and locals.
+    #[inline]
+    pub fn mut_vars_and_args_iter<'a>(&'a self) -> impl Iterator<Item=Local> + 'a {
+        (1..self.local_decls.len()).filter_map(move |index| {
+            let local = Local::new(index);
+            let decl = &self.local_decls[local];
+            if (decl.is_user_variable || index < self.arg_count + 1)
+               && decl.mutability == Mutability::Mut
+            {
+                Some(local)
+            } else {
+                None
+            }
+        })
+    }
+
     /// Returns an iterator over all function arguments.
     #[inline]
     pub fn args_iter(&self) -> impl Iterator<Item=Local> {
@@ -842,12 +862,17 @@ pub enum TerminatorKind<'tcx> {
     },
 }
 
+pub type Successors<'a> =
+    iter::Chain<option::IntoIter<&'a BasicBlock>, slice::Iter<'a, BasicBlock>>;
+pub type SuccessorsMut<'a> =
+    iter::Chain<option::IntoIter<&'a mut BasicBlock>, slice::IterMut<'a, BasicBlock>>;
+
 impl<'tcx> Terminator<'tcx> {
-    pub fn successors(&self) -> Cow<[BasicBlock]> {
+    pub fn successors(&self) -> Successors {
         self.kind.successors()
     }
 
-    pub fn successors_mut(&mut self) -> Vec<&mut BasicBlock> {
+    pub fn successors_mut(&mut self) -> SuccessorsMut {
         self.kind.successors_mut()
     }
 
@@ -868,72 +893,71 @@ impl<'tcx> TerminatorKind<'tcx> {
         }
     }
 
-    pub fn successors(&self) -> Cow<[BasicBlock]> {
+    pub fn successors(&self) -> Successors {
         use self::TerminatorKind::*;
         match *self {
-            Goto { target: ref b } => slice::from_ref(b).into_cow(),
-            SwitchInt { targets: ref b, .. } => b[..].into_cow(),
-            Resume | Abort | GeneratorDrop => (&[]).into_cow(),
-            Return => (&[]).into_cow(),
-            Unreachable => (&[]).into_cow(),
-            Call { destination: Some((_, t)), cleanup: Some(c), .. } => vec![t, c].into_cow(),
-            Call { destination: Some((_, ref t)), cleanup: None, .. } =>
-                slice::from_ref(t).into_cow(),
-            Call { destination: None, cleanup: Some(ref c), .. } => slice::from_ref(c).into_cow(),
-            Call { destination: None, cleanup: None, .. } => (&[]).into_cow(),
-            Yield { resume: t, drop: Some(c), .. } => vec![t, c].into_cow(),
-            Yield { resume: ref t, drop: None, .. } => slice::from_ref(t).into_cow(),
-            DropAndReplace { target, unwind: Some(unwind), .. } |
-            Drop { target, unwind: Some(unwind), .. } => {
-                vec![target, unwind].into_cow()
+            Resume | Abort | GeneratorDrop | Return | Unreachable |
+            Call { destination: None, cleanup: None, .. } => {
+                None.into_iter().chain(&[])
+            }
+            Goto { target: ref t } |
+            Call { destination: None, cleanup: Some(ref t), .. } |
+            Call { destination: Some((_, ref t)), cleanup: None, .. } |
+            Yield { resume: ref t, drop: None, .. } |
+            DropAndReplace { target: ref t, unwind: None, .. } |
+            Drop { target: ref t, unwind: None, .. } |
+            Assert { target: ref t, cleanup: None, .. } |
+            FalseUnwind { real_target: ref t, unwind: None } => {
+                Some(t).into_iter().chain(&[])
+            }
+            Call { destination: Some((_, ref t)), cleanup: Some(ref u), .. } |
+            Yield { resume: ref t, drop: Some(ref u), .. } |
+            DropAndReplace { target: ref t, unwind: Some(ref u), .. } |
+            Drop { target: ref t, unwind: Some(ref u), .. } |
+            Assert { target: ref t, cleanup: Some(ref u), .. } |
+            FalseUnwind { real_target: ref t, unwind: Some(ref u) } => {
+                Some(t).into_iter().chain(slice::from_ref(u))
             }
-            DropAndReplace { ref target, unwind: None, .. } |
-            Drop { ref target, unwind: None, .. } => {
-                slice::from_ref(target).into_cow()
+            SwitchInt { ref targets, .. } => {
+                None.into_iter().chain(&targets[..])
             }
-            Assert { target, cleanup: Some(unwind), .. } => vec![target, unwind].into_cow(),
-            Assert { ref target, .. } => slice::from_ref(target).into_cow(),
             FalseEdges { ref real_target, ref imaginary_targets } => {
-                let mut s = vec![*real_target];
-                s.extend_from_slice(imaginary_targets);
-                s.into_cow()
+                Some(real_target).into_iter().chain(&imaginary_targets[..])
             }
-            FalseUnwind { real_target: t, unwind: Some(u) } => vec![t, u].into_cow(),
-            FalseUnwind { real_target: ref t, unwind: None } => slice::from_ref(t).into_cow(),
         }
     }
 
-    // FIXME: no mootable cow. I’m honestly not sure what a “cow” between `&mut [BasicBlock]` and
-    // `Vec<&mut BasicBlock>` would look like in the first place.
-    pub fn successors_mut(&mut self) -> Vec<&mut BasicBlock> {
+    pub fn successors_mut(&mut self) -> SuccessorsMut {
         use self::TerminatorKind::*;
         match *self {
-            Goto { target: ref mut b } => vec![b],
-            SwitchInt { targets: ref mut b, .. } => b.iter_mut().collect(),
-            Resume | Abort | GeneratorDrop => Vec::new(),
-            Return => Vec::new(),
-            Unreachable => Vec::new(),
-            Call { destination: Some((_, ref mut t)), cleanup: Some(ref mut c), .. } => vec![t, c],
-            Call { destination: Some((_, ref mut t)), cleanup: None, .. } => vec![t],
-            Call { destination: None, cleanup: Some(ref mut c), .. } => vec![c],
-            Call { destination: None, cleanup: None, .. } => vec![],
-            Yield { resume: ref mut t, drop: Some(ref mut c), .. } => vec![t, c],
-            Yield { resume: ref mut t, drop: None, .. } => vec![t],
-            DropAndReplace { ref mut target, unwind: Some(ref mut unwind), .. } |
-            Drop { ref mut target, unwind: Some(ref mut unwind), .. } => vec![target, unwind],
-            DropAndReplace { ref mut target, unwind: None, .. } |
-            Drop { ref mut target, unwind: None, .. } => {
-                vec![target]
+            Resume | Abort | GeneratorDrop | Return | Unreachable |
+            Call { destination: None, cleanup: None, .. } => {
+                None.into_iter().chain(&mut [])
+            }
+            Goto { target: ref mut t } |
+            Call { destination: None, cleanup: Some(ref mut t), .. } |
+            Call { destination: Some((_, ref mut t)), cleanup: None, .. } |
+            Yield { resume: ref mut t, drop: None, .. } |
+            DropAndReplace { target: ref mut t, unwind: None, .. } |
+            Drop { target: ref mut t, unwind: None, .. } |
+            Assert { target: ref mut t, cleanup: None, .. } |
+            FalseUnwind { real_target: ref mut t, unwind: None } => {
+                Some(t).into_iter().chain(&mut [])
+            }
+            Call { destination: Some((_, ref mut t)), cleanup: Some(ref mut u), .. } |
+            Yield { resume: ref mut t, drop: Some(ref mut u), .. } |
+            DropAndReplace { target: ref mut t, unwind: Some(ref mut u), .. } |
+            Drop { target: ref mut t, unwind: Some(ref mut u), .. } |
+            Assert { target: ref mut t, cleanup: Some(ref mut u), .. } |
+            FalseUnwind { real_target: ref mut t, unwind: Some(ref mut u) } => {
+                Some(t).into_iter().chain(slice::from_ref_mut(u))
+            }
+            SwitchInt { ref mut targets, .. } => {
+                None.into_iter().chain(&mut targets[..])
             }
-            Assert { ref mut target, cleanup: Some(ref mut unwind), .. } => vec![target, unwind],
-            Assert { ref mut target, .. } => vec![target],
             FalseEdges { ref mut real_target, ref mut imaginary_targets } => {
-                let mut s = vec![real_target];
-                s.extend(imaginary_targets.iter_mut());
-                s
+                Some(real_target).into_iter().chain(&mut imaginary_targets[..])
             }
-            FalseUnwind { real_target: ref mut t, unwind: Some(ref mut u) } => vec![t, u],
-            FalseUnwind { ref mut real_target, unwind: None } => vec![real_target],
         }
     }
 
@@ -1053,18 +1077,18 @@ impl<'tcx> BasicBlockData<'tcx> {
 impl<'tcx> Debug for TerminatorKind<'tcx> {
     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
         self.fmt_head(fmt)?;
-        let successors = self.successors();
+        let successor_count = self.successors().count();
         let labels = self.fmt_successor_labels();
-        assert_eq!(successors.len(), labels.len());
+        assert_eq!(successor_count, labels.len());
 
-        match successors.len() {
+        match successor_count {
             0 => Ok(()),
 
-            1 => write!(fmt, " -> {:?}", successors[0]),
+            1 => write!(fmt, " -> {:?}", self.successors().nth(0).unwrap()),
 
             _ => {
                 write!(fmt, " -> [")?;
-                for (i, target) in successors.iter().enumerate() {
+                for (i, target) in self.successors().enumerate() {
                     if i > 0 {
                         write!(fmt, ", ")?;
                     }
@@ -1113,26 +1137,7 @@ impl<'tcx> TerminatorKind<'tcx> {
                 if !expected {
                     write!(fmt, "!")?;
                 }
-                write!(fmt, "{:?}, ", cond)?;
-
-                match *msg {
-                    AssertMessage::BoundsCheck { ref len, ref index } => {
-                        write!(fmt, "{:?}, {:?}, {:?}",
-                               "index out of bounds: the len is {} but the index is {}",
-                               len, index)?;
-                    }
-                    AssertMessage::Math(ref err) => {
-                        write!(fmt, "{:?}", err.description())?;
-                    }
-                    AssertMessage::GeneratorResumedAfterReturn => {
-                        write!(fmt, "{:?}", "generator resumed after completion")?;
-                    }
-                    AssertMessage::GeneratorResumedAfterPanic => {
-                        write!(fmt, "{:?}", "generator resumed after panicking")?;
-                    }
-                }
-
-                write!(fmt, ")")
+                write!(fmt, "{:?}, \"{:?}\")", cond, msg)
             },
             FalseEdges { .. } => write!(fmt, "falseEdges"),
             FalseUnwind { .. } => write!(fmt, "falseUnwind"),
@@ -1187,17 +1192,6 @@ impl<'tcx> TerminatorKind<'tcx> {
     }
 }
 
-#[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
-pub enum AssertMessage<'tcx> {
-    BoundsCheck {
-        len: Operand<'tcx>,
-        index: Operand<'tcx>
-    },
-    Math(ConstMathErr),
-    GeneratorResumedAfterReturn,
-    GeneratorResumedAfterPanic,
-}
-
 ///////////////////////////////////////////////////////////////////////////
 // Statements
 
@@ -1898,12 +1892,13 @@ fn fmt_const_val<W: Write>(fmt: &mut W, const_val: &ty::Const) -> fmt::Result {
 
 pub fn print_miri_value<W: Write>(value: Value, ty: Ty, f: &mut W) -> fmt::Result {
     use ty::TypeVariants::*;
-    use rustc_const_math::ConstFloat;
     match (value, &ty.sty) {
         (Value::ByVal(PrimVal::Bytes(0)), &TyBool) => write!(f, "false"),
         (Value::ByVal(PrimVal::Bytes(1)), &TyBool) => write!(f, "true"),
-        (Value::ByVal(PrimVal::Bytes(bits)), &TyFloat(fty)) =>
-            write!(f, "{}", ConstFloat { bits, ty: fty }),
+        (Value::ByVal(PrimVal::Bytes(bits)), &TyFloat(ast::FloatTy::F32)) =>
+            write!(f, "{}f32", Single::from_bits(bits)),
+        (Value::ByVal(PrimVal::Bytes(bits)), &TyFloat(ast::FloatTy::F64)) =>
+            write!(f, "{}f64", Double::from_bits(bits)),
         (Value::ByVal(PrimVal::Bytes(n)), &TyUint(ui)) => write!(f, "{:?}{}", n, ui),
         (Value::ByVal(PrimVal::Bytes(n)), &TyInt(i)) => write!(f, "{:?}{}", n as i128, i),
         (Value::ByVal(PrimVal::Bytes(n)), &TyChar) =>
@@ -1952,7 +1947,7 @@ impl<'tcx> ControlFlowGraph for Mir<'tcx> {
     fn successors<'graph>(&'graph self, node: Self::Node)
                           -> <Self as GraphSuccessors<'graph>>::Iter
     {
-        self.basic_blocks[node].terminator().successors().into_owned().into_iter()
+        self.basic_blocks[node].terminator().successors().cloned()
     }
 }
 
@@ -1963,7 +1958,7 @@ impl<'a, 'b> GraphPredecessors<'b> for Mir<'a> {
 
 impl<'a, 'b>  GraphSuccessors<'b> for Mir<'a> {
     type Item = BasicBlock;
-    type Iter = IntoIter<BasicBlock>;
+    type Iter = iter::Cloned<Successors<'b>>;
 }
 
 #[derive(Copy, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
@@ -1983,6 +1978,11 @@ impl fmt::Debug for Location {
 }
 
 impl Location {
+    pub const START: Location = Location {
+        block: START_BLOCK,
+        statement_index: 0,
+    };
+
     /// Returns the location immediately after this one within the enclosing block.
     ///
     /// Note that if this location represents a terminator, then the
@@ -2029,6 +2029,12 @@ pub struct GeneratorLayout<'tcx> {
     pub fields: Vec<LocalDecl<'tcx>>,
 }
 
+#[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
+pub struct BorrowCheckResult<'gcx> {
+    pub closure_requirements: Option<ClosureRegionRequirements<'gcx>>,
+    pub used_mut_upvars: SmallVec<[Field; 8]>,
+}
+
 /// After we borrow check a closure, we are left with various
 /// requirements that we have inferred between the free regions that
 /// appear in the closure's signature or on its field types.  These
@@ -2256,8 +2262,8 @@ impl<'tcx> TypeFoldable<'tcx> for Terminator<'tcx> {
                 }
             },
             Assert { ref cond, expected, ref msg, target, cleanup } => {
-                let msg = if let AssertMessage::BoundsCheck { ref len, ref index } = *msg {
-                    AssertMessage::BoundsCheck {
+                let msg = if let EvalErrorKind::BoundsCheck { ref len, ref index } = *msg {
+                    EvalErrorKind::BoundsCheck {
                         len: len.fold_with(folder),
                         index: index.fold_with(folder),
                     }
@@ -2306,7 +2312,7 @@ impl<'tcx> TypeFoldable<'tcx> for Terminator<'tcx> {
             },
             Assert { ref cond, ref msg, .. } => {
                 if cond.visit_with(visitor) {
-                    if let AssertMessage::BoundsCheck { ref len, ref index } = *msg {
+                    if let EvalErrorKind::BoundsCheck { ref len, ref index } = *msg {
                         len.visit_with(visitor) || index.visit_with(visitor)
                     } else {
                         false
diff --git a/src/librustc/mir/traversal.rs b/src/librustc/mir/traversal.rs
index 666ca5eabe8..92888ed99e4 100644
--- a/src/librustc/mir/traversal.rs
+++ b/src/librustc/mir/traversal.rs
@@ -8,8 +8,6 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::vec;
-
 use rustc_data_structures::bitvec::BitVector;
 use rustc_data_structures::indexed_vec::Idx;
 
@@ -67,7 +65,7 @@ impl<'a, 'tcx> Iterator for Preorder<'a, 'tcx> {
             let data = &self.mir[idx];
 
             if let Some(ref term) = data.terminator {
-                for &succ in term.successors().iter() {
+                for &succ in term.successors() {
                     self.worklist.push(succ);
                 }
             }
@@ -110,7 +108,7 @@ impl<'a, 'tcx> ExactSizeIterator for Preorder<'a, 'tcx> {}
 pub struct Postorder<'a, 'tcx: 'a> {
     mir: &'a Mir<'tcx>,
     visited: BitVector,
-    visit_stack: Vec<(BasicBlock, vec::IntoIter<BasicBlock>)>
+    visit_stack: Vec<(BasicBlock, Successors<'a>)>
 }
 
 impl<'a, 'tcx> Postorder<'a, 'tcx> {
@@ -126,10 +124,7 @@ impl<'a, 'tcx> Postorder<'a, 'tcx> {
 
         if let Some(ref term) = data.terminator {
             po.visited.insert(root.index());
-
-            let succs = term.successors().into_owned().into_iter();
-
-            po.visit_stack.push((root, succs));
+            po.visit_stack.push((root, term.successors()));
             po.traverse_successor();
         }
 
@@ -186,7 +181,7 @@ impl<'a, 'tcx> Postorder<'a, 'tcx> {
         // two iterations yield `C` and finally `A` for a final traversal of [E, D, B, C, A]
         loop {
             let bb = if let Some(&mut (_, ref mut iter)) = self.visit_stack.last_mut() {
-                if let Some(bb) = iter.next() {
+                if let Some(&bb) = iter.next() {
                     bb
                 } else {
                     break;
@@ -197,8 +192,7 @@ impl<'a, 'tcx> Postorder<'a, 'tcx> {
 
             if self.visited.insert(bb.index()) {
                 if let Some(ref term) = self.mir[bb].terminator {
-                    let succs = term.successors().into_owned().into_iter();
-                    self.visit_stack.push((bb, succs));
+                    self.visit_stack.push((bb, term.successors()));
                 }
             }
         }
diff --git a/src/librustc/mir/visit.rs b/src/librustc/mir/visit.rs
index a3fdb6f73ab..59b6f369754 100644
--- a/src/librustc/mir/visit.rs
+++ b/src/librustc/mir/visit.rs
@@ -511,17 +511,13 @@ macro_rules! make_mir_visitor {
             fn super_assert_message(&mut self,
                                     msg: & $($mutability)* AssertMessage<'tcx>,
                                     location: Location) {
-                match *msg {
-                    AssertMessage::BoundsCheck {
+                use mir::interpret::EvalErrorKind::*;
+                if let BoundsCheck {
                         ref $($mutability)* len,
                         ref $($mutability)* index
-                    } => {
-                        self.visit_operand(len, location);
-                        self.visit_operand(index, location);
-                    }
-                    AssertMessage::Math(_) => {},
-                    AssertMessage::GeneratorResumedAfterReturn => {},
-                    AssertMessage::GeneratorResumedAfterPanic => {},
+                    } = *msg {
+                    self.visit_operand(len, location);
+                    self.visit_operand(index, location);
                 }
             }
 
diff --git a/src/librustc/session/config.rs b/src/librustc/session/config.rs
index ab703d423c6..0beda679e69 100644
--- a/src/librustc/session/config.rs
+++ b/src/librustc/session/config.rs
@@ -1053,6 +1053,8 @@ options! {CodegenOptions, CodegenSetter, basic_codegen_options,
          2 = full debug info with variable and type information"),
     opt_level: Option<String> = (None, parse_opt_string, [TRACKED],
         "optimize with possible levels 0-3, s, or z"),
+    force_frame_pointers: Option<bool> = (None, parse_opt_bool, [TRACKED],
+        "force use of the frame pointers"),
     debug_assertions: Option<bool> = (None, parse_opt_bool, [TRACKED],
         "explicitly enable the cfg(debug_assertions) directive"),
     inline_threshold: Option<usize> = (None, parse_opt_uint, [TRACKED],
@@ -1248,6 +1250,8 @@ options! {DebuggingOptions, DebuggingSetter, basic_debugging_options,
         "choose which RELRO level to use"),
     nll_subminimal_causes: bool = (false, parse_bool, [UNTRACKED],
         "when tracking region error causes, accept subminimal results for faster execution."),
+    nll_facts: bool = (false, parse_bool, [UNTRACKED],
+                       "dump facts from NLL analysis into side files"),
     disable_nll_user_type_assert: bool = (false, parse_bool, [UNTRACKED],
         "disable user provided type assertion in NLL"),
     trans_time_graph: bool = (false, parse_bool, [UNTRACKED],
@@ -1270,7 +1274,7 @@ options! {DebuggingOptions, DebuggingSetter, basic_debugging_options,
     dep_info_omit_d_target: bool = (false, parse_bool, [TRACKED],
         "in dep-info output, omit targets for tracking dependencies of the dep-info files \
          themselves"),
-    approximate_suggestions: bool = (false, parse_bool, [UNTRACKED],
+    suggestion_applicability: bool = (false, parse_bool, [UNTRACKED],
         "include machine-applicability of suggestions in JSON output"),
     unpretty: Option<String> = (None, parse_unpretty, [UNTRACKED],
         "Present the input source, unstable (and less-pretty) variants;
@@ -1681,7 +1685,7 @@ pub fn parse_cfgspecs(cfgspecs: Vec<String>) -> ast::CrateConfig {
                 early_error(ErrorOutputType::default(), &msg)
             }
 
-            (meta_item.ident.name, meta_item.value_str())
+            (meta_item.name(), meta_item.value_str())
         })
         .collect::<ast::CrateConfig>()
 }
@@ -2966,6 +2970,10 @@ mod tests {
         assert!(reference.dep_tracking_hash() != opts.dep_tracking_hash());
 
         opts = reference.clone();
+        opts.cg.force_frame_pointers = Some(false);
+        assert!(reference.dep_tracking_hash() != opts.dep_tracking_hash());
+
+        opts = reference.clone();
         opts.cg.debug_assertions = Some(true);
         assert!(reference.dep_tracking_hash() != opts.dep_tracking_hash());
 
diff --git a/src/librustc/session/mod.rs b/src/librustc/session/mod.rs
index a0f11443425..2ab72ba20bf 100644
--- a/src/librustc/session/mod.rs
+++ b/src/librustc/session/mod.rs
@@ -20,7 +20,7 @@ use lint::builtin::BuiltinLintDiagnostics;
 use middle::allocator::AllocatorKind;
 use middle::dependency_format;
 use session::search_paths::PathKind;
-use session::config::{DebugInfoLevel, OutputType};
+use session::config::{OutputType};
 use ty::tls;
 use util::nodemap::{FxHashSet};
 use util::common::{duration_to_secs_str, ErrorReported};
@@ -658,8 +658,11 @@ impl Session {
     }
 
     pub fn must_not_eliminate_frame_pointers(&self) -> bool {
-        self.opts.debuginfo != DebugInfoLevel::NoDebugInfo
-            || !self.target.target.options.eliminate_frame_pointer
+        if let Some(x) = self.opts.cg.force_frame_pointers {
+            x
+        } else {
+            !self.target.target.options.eliminate_frame_pointer
+        }
     }
 
     /// Returns the symbol name for the registrar function,
@@ -1002,7 +1005,7 @@ pub fn build_session_with_codemap(
                     Some(registry),
                     codemap.clone(),
                     pretty,
-                    sopts.debugging_opts.approximate_suggestions,
+                    sopts.debugging_opts.suggestion_applicability,
                 ).ui_testing(sopts.debugging_opts.ui_testing),
             ),
             (config::ErrorOutputType::Json(pretty), Some(dst)) => Box::new(
@@ -1011,7 +1014,7 @@ pub fn build_session_with_codemap(
                     Some(registry),
                     codemap.clone(),
                     pretty,
-                    sopts.debugging_opts.approximate_suggestions,
+                    sopts.debugging_opts.suggestion_applicability,
                 ).ui_testing(sopts.debugging_opts.ui_testing),
             ),
             (config::ErrorOutputType::Short(color_config), None) => Box::new(
diff --git a/src/librustc/traits/coherence.rs b/src/librustc/traits/coherence.rs
index 31f8af1f968..5a626e7b82c 100644
--- a/src/librustc/traits/coherence.rs
+++ b/src/librustc/traits/coherence.rs
@@ -154,7 +154,10 @@ fn overlap<'cx, 'gcx, 'tcx>(selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
                                            recursion_depth: 0,
                                            predicate: p })
                      .chain(obligations)
-                     .find(|o| !selcx.evaluate_obligation(o));
+                     .find(|o| !selcx.predicate_may_hold_fatal(o));
+    // FIXME: the call to `selcx.predicate_may_hold_fatal` above should be ported
+    // to the canonical trait query form, `infcx.predicate_may_hold`, once
+    // the new system supports intercrate mode (which coherence needs).
 
     if let Some(failing_obligation) = opt_failing_obligation {
         debug!("overlap: obligation unsatisfiable {:?}", failing_obligation);
diff --git a/src/librustc/traits/error_reporting.rs b/src/librustc/traits/error_reporting.rs
index 33abc0c7e15..047d4bb8930 100644
--- a/src/librustc/traits/error_reporting.rs
+++ b/src/librustc/traits/error_reporting.rs
@@ -24,6 +24,7 @@ use super::{
     SelectionContext,
     SelectionError,
     ObjectSafetyViolation,
+    Overflow,
 };
 
 use errors::DiagnosticBuilder;
@@ -659,8 +660,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                                 predicate: ty::Predicate::Trait(predicate),
                                 .. obligation.clone()
                             };
-                            let mut selcx = SelectionContext::new(self);
-                            if selcx.evaluate_obligation(&unit_obligation) {
+                            if self.predicate_may_hold(&unit_obligation) {
                                 err.note("the trait is implemented for `()`. \
                                          Possibly this error has been caused by changes to \
                                          Rust's type-inference algorithm \
@@ -830,6 +830,10 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                 }
                 err.struct_error(self.tcx, span, "constant expression")
             }
+
+            Overflow => {
+                bug!("overflow should be handled before the `report_selection_error` path");
+            }
         };
         self.note_obligation_cause(&mut err, obligation);
         err.emit();
@@ -872,7 +876,6 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                 .count();
 
             let mut trait_type = trait_ref.self_ty();
-            let mut selcx = SelectionContext::new(self);
 
             for refs_remaining in 0..refs_number {
                 if let ty::TypeVariants::TyRef(_, ty::TypeAndMut{ ty: t_type, mutbl: _ }) =
@@ -886,7 +889,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                                                          obligation.param_env,
                                                          new_trait_ref.to_predicate());
 
-                    if selcx.evaluate_obligation(&new_obligation) {
+                    if self.predicate_may_hold(&new_obligation) {
                         let sp = self.tcx.sess.codemap()
                             .span_take_while(span, |c| c.is_whitespace() || *c == '&');
 
@@ -976,6 +979,12 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                      ArgKind::Arg(format!("{}", field.name), "_".to_string())
                  }).collect::<Vec<_>>())
             }
+            hir::map::NodeStructCtor(ref variant_data) => {
+                (self.tcx.sess.codemap().def_span(self.tcx.hir.span(variant_data.id())),
+                 variant_data.fields()
+                    .iter().map(|_| ArgKind::Arg("_".to_owned(), "_".to_owned()))
+                    .collect())
+            }
             _ => panic!("non-FnLike node found: {:?}", node),
         }
     }
@@ -1322,7 +1331,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                 cleaned_pred.to_predicate()
             );
 
-            selcx.evaluate_obligation(&obligation)
+            self.predicate_may_hold(&obligation)
         })
     }
 
diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index 1c091d68a2e..6e201507181 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -112,7 +112,7 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
                 selcx,
                 register_region_obligations: self.register_region_obligations
             });
-            debug!("select: outcome={:?}", outcome);
+            debug!("select: outcome={:#?}", outcome);
 
             // FIXME: if we kept the original cache key, we could mark projection
             // obligations as complete for the projection cache here.
@@ -333,7 +333,7 @@ fn process_predicate<'a, 'gcx, 'tcx>(
             if data.is_global() {
                 // no type variables present, can use evaluation for better caching.
                 // FIXME: consider caching errors too.
-                if selcx.evaluate_obligation_conservatively(&obligation) {
+                if selcx.infcx().predicate_must_hold(&obligation) {
                     debug!("selecting trait `{:?}` at depth {} evaluated to holds",
                            data, obligation.recursion_depth);
                     return Ok(Some(vec![]))
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index 728d9f1a027..dd5208e908e 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -41,7 +41,7 @@ pub use self::object_safety::ObjectSafetyViolation;
 pub use self::object_safety::MethodViolationCode;
 pub use self::on_unimplemented::{OnUnimplementedDirective, OnUnimplementedNote};
 pub use self::select::{EvaluationCache, SelectionContext, SelectionCache};
-pub use self::select::IntercrateAmbiguityCause;
+pub use self::select::{EvaluationResult, IntercrateAmbiguityCause, OverflowError};
 pub use self::specialize::{OverlapError, specialization_graph, translate_substs};
 pub use self::specialize::{SpecializesCache, find_associated_item};
 pub use self::engine::TraitEngine;
@@ -74,6 +74,19 @@ pub enum IntercrateMode {
     Fixed
 }
 
+// The mode that trait queries run in
+#[derive(Copy, Clone, PartialEq, Eq, Debug)]
+pub enum TraitQueryMode {
+    // Standard/un-canonicalized queries get accurate
+    // spans etc. passed in and hence can do reasonable
+    // error reporting on their own.
+    Standard,
+    // Canonicalized queries get dummy spans and hence
+    // must generally propagate errors to
+    // pre-canonicalization callsites.
+    Canonical,
+}
+
 /// An `Obligation` represents some trait reference (e.g. `int:Eq`) for
 /// which the vtable must be found.  The process of finding a vtable is
 /// called "resolving" the `Obligation`. This process consists of
@@ -349,6 +362,7 @@ pub enum SelectionError<'tcx> {
                                 ty::error::TypeError<'tcx>),
     TraitNotObjectSafe(DefId),
     ConstEvalFailure(ConstEvalErr<'tcx>),
+    Overflow,
 }
 
 pub struct FulfillmentError<'tcx> {
@@ -550,8 +564,7 @@ pub fn type_known_to_meet_bound<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx
         predicate: trait_ref.to_predicate(),
     };
 
-    let result = SelectionContext::new(infcx)
-        .evaluate_obligation_conservatively(&obligation);
+    let result = infcx.predicate_must_hold(&obligation);
     debug!("type_known_to_meet_ty={:?} bound={} => {:?}",
            ty, infcx.tcx.item_path_str(def_id), result);
 
diff --git a/src/librustc/traits/on_unimplemented.rs b/src/librustc/traits/on_unimplemented.rs
index 405dafdff2b..3cf7af30b3d 100644
--- a/src/librustc/traits/on_unimplemented.rs
+++ b/src/librustc/traits/on_unimplemented.rs
@@ -18,10 +18,10 @@ use util::nodemap::FxHashMap;
 use syntax::ast::{MetaItem, NestedMetaItem};
 use syntax::attr;
 use syntax_pos::Span;
-use syntax_pos::symbol::InternedString;
+use syntax_pos::symbol::LocalInternedString;
 
 #[derive(Clone, Debug)]
-pub struct OnUnimplementedFormatString(InternedString);
+pub struct OnUnimplementedFormatString(LocalInternedString);
 
 #[derive(Debug)]
 pub struct OnUnimplementedDirective {
@@ -190,7 +190,7 @@ impl<'a, 'gcx, 'tcx> OnUnimplementedDirective {
         for command in self.subcommands.iter().chain(Some(self)).rev() {
             if let Some(ref condition) = command.condition {
                 if !attr::eval_condition(condition, &tcx.sess.parse_sess, &mut |c| {
-                    options.contains(&(c.ident.name.as_str().to_string(),
+                    options.contains(&(c.name().as_str().to_string(),
                                       match c.value_str().map(|s| s.as_str().to_string()) {
                                           Some(s) => Some(s),
                                           None => None
@@ -225,7 +225,7 @@ impl<'a, 'gcx, 'tcx> OnUnimplementedDirective {
 impl<'a, 'gcx, 'tcx> OnUnimplementedFormatString {
     pub fn try_parse(tcx: TyCtxt<'a, 'gcx, 'tcx>,
                      trait_def_id: DefId,
-                     from: InternedString,
+                     from: LocalInternedString,
                      err_sp: Span)
                      -> Result<Self, ErrorReported>
     {
diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs
index 1c7942139e9..45fa588bbf5 100644
--- a/src/librustc/traits/project.rs
+++ b/src/librustc/traits/project.rs
@@ -188,7 +188,7 @@ pub fn poly_project_and_unify_type<'cx, 'gcx, 'tcx>(
     let infcx = selcx.infcx();
     infcx.commit_if_ok(|snapshot| {
         let (skol_predicate, skol_map) =
-            infcx.skolemize_late_bound_regions(&obligation.predicate, snapshot);
+            infcx.skolemize_late_bound_regions(&obligation.predicate);
 
         let skol_obligation = obligation.with(skol_predicate);
         let r = match project_and_unify_type(selcx, &skol_obligation) {
@@ -196,7 +196,10 @@ pub fn poly_project_and_unify_type<'cx, 'gcx, 'tcx>(
                 let span = obligation.cause.span;
                 match infcx.leak_check(false, span, &skol_map, snapshot) {
                     Ok(()) => Ok(infcx.plug_leaks(skol_map, snapshot, result)),
-                    Err(e) => Err(MismatchedProjectionTypes { err: e }),
+                    Err(e) => {
+                        debug!("poly_project_and_unify_type: leak check encountered error {:?}", e);
+                        Err(MismatchedProjectionTypes { err: e })
+                    }
                 }
             }
             Err(e) => {
@@ -243,7 +246,10 @@ fn project_and_unify_type<'cx, 'gcx, 'tcx>(
             obligations.extend(inferred_obligations);
             Ok(Some(obligations))
         },
-        Err(err) => Err(MismatchedProjectionTypes { err: err }),
+        Err(err) => {
+            debug!("project_and_unify_type: equating types encountered error {:?}", err);
+            Err(MismatchedProjectionTypes { err: err })
+        }
     }
 }
 
@@ -403,7 +409,7 @@ impl<'a, 'b, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for AssociatedTypeNormalizer<'a,
         if let ConstVal::Unevaluated(def_id, substs) = constant.val {
             let tcx = self.selcx.tcx().global_tcx();
             if let Some(param_env) = self.tcx().lift_to_global(&self.param_env) {
-                if substs.needs_infer() {
+                if substs.needs_infer() || substs.has_skol() {
                     let identity_substs = Substs::identity_for_item(tcx, def_id);
                     let instance = ty::Instance::resolve(tcx, param_env, def_id, identity_substs);
                     if let Some(instance) = instance {
diff --git a/src/librustc/traits/query/evaluate_obligation.rs b/src/librustc/traits/query/evaluate_obligation.rs
new file mode 100644
index 00000000000..4e028cac49a
--- /dev/null
+++ b/src/librustc/traits/query/evaluate_obligation.rs
@@ -0,0 +1,70 @@
+// Copyright 2018 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 infer::InferCtxt;
+use infer::canonical::{Canonical, Canonicalize};
+use traits::{EvaluationResult, PredicateObligation, SelectionContext,
+             TraitQueryMode, OverflowError};
+use traits::query::CanonicalPredicateGoal;
+use ty::{ParamEnvAnd, Predicate, TyCtxt};
+
+impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
+    /// Evaluates whether the predicate can be satisfied (by any means)
+    /// in the given `ParamEnv`.
+    pub fn predicate_may_hold(
+        &self,
+        obligation: &PredicateObligation<'tcx>,
+    ) -> bool {
+        self.evaluate_obligation(obligation).may_apply()
+    }
+
+    /// Evaluates whether the predicate can be satisfied in the given
+    /// `ParamEnv`, and returns `false` if not certain. However, this is
+    /// not entirely accurate if inference variables are involved.
+    pub fn predicate_must_hold(
+        &self,
+        obligation: &PredicateObligation<'tcx>,
+    ) -> bool {
+        self.evaluate_obligation(obligation) == EvaluationResult::EvaluatedToOk
+    }
+
+    // Helper function that canonicalizes and runs the query, as well as handles
+    // overflow.
+    fn evaluate_obligation(
+        &self,
+        obligation: &PredicateObligation<'tcx>,
+    ) -> EvaluationResult {
+        let (c_pred, _) =
+            self.canonicalize_query(&obligation.param_env.and(obligation.predicate));
+        // Run canonical query. If overflow occurs, rerun from scratch but this time
+        // in standard trait query mode so that overflow is handled appropriately
+        // within `SelectionContext`.
+        match self.tcx.global_tcx().evaluate_obligation(c_pred) {
+            Ok(result) => result,
+            Err(OverflowError) => {
+                let mut selcx =
+                    SelectionContext::with_query_mode(&self, TraitQueryMode::Standard);
+                selcx.evaluate_obligation_recursively(obligation)
+                     .expect("Overflow should be caught earlier in standard query mode")
+            }
+        }
+    }
+}
+
+impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for ParamEnvAnd<'tcx, Predicate<'tcx>> {
+    type Canonicalized = CanonicalPredicateGoal<'gcx>;
+
+    fn intern(
+        _gcx: TyCtxt<'_, 'gcx, 'gcx>,
+        value: Canonical<'gcx, Self::Lifted>,
+    ) -> Self::Canonicalized {
+        value
+    }
+}
diff --git a/src/librustc/traits/query/mod.rs b/src/librustc/traits/query/mod.rs
index f1f9256f825..096633ddab2 100644
--- a/src/librustc/traits/query/mod.rs
+++ b/src/librustc/traits/query/mod.rs
@@ -19,6 +19,7 @@ use infer::canonical::Canonical;
 use ty::{self, Ty};
 
 pub mod dropck_outlives;
+pub mod evaluate_obligation;
 pub mod normalize;
 pub mod normalize_erasing_regions;
 
@@ -27,6 +28,9 @@ pub type CanonicalProjectionGoal<'tcx> =
 
 pub type CanonicalTyGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, Ty<'tcx>>>;
 
+pub type CanonicalPredicateGoal<'tcx> =
+    Canonical<'tcx, ty::ParamEnvAnd<'tcx, ty::Predicate<'tcx>>>;
+
 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
 pub struct NoSolution;
 
diff --git a/src/librustc/traits/query/normalize.rs b/src/librustc/traits/query/normalize.rs
index 5e0a4ca3305..f074e061653 100644
--- a/src/librustc/traits/query/normalize.rs
+++ b/src/librustc/traits/query/normalize.rs
@@ -196,7 +196,7 @@ impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for QueryNormalizer<'cx, 'gcx, 'tcx
         if let ConstVal::Unevaluated(def_id, substs) = constant.val {
             let tcx = self.infcx.tcx.global_tcx();
             if let Some(param_env) = self.tcx().lift_to_global(&self.param_env) {
-                if substs.needs_infer() {
+                if substs.needs_infer() || substs.has_skol() {
                     let identity_substs = Substs::identity_for_item(tcx, def_id);
                     let instance = ty::Instance::resolve(tcx, param_env, def_id, identity_substs);
                     if let Some(instance) = instance {
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index f43f5cf3e3f..54b2cf28082 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -17,12 +17,12 @@ use self::EvaluationResult::*;
 
 use super::coherence::{self, Conflict};
 use super::DerivedObligationCause;
-use super::IntercrateMode;
+use super::{IntercrateMode, TraitQueryMode};
 use super::project;
 use super::project::{normalize_with_depth, Normalized, ProjectionCacheKey};
 use super::{PredicateObligation, TraitObligation, ObligationCause};
 use super::{ObligationCauseCode, BuiltinDerivedObligation, ImplDerivedObligation};
-use super::{SelectionError, Unimplemented, OutputTypeParameterMismatch};
+use super::{SelectionError, Unimplemented, OutputTypeParameterMismatch, Overflow};
 use super::{ObjectCastObligation, Obligation};
 use super::TraitNotObjectSafe;
 use super::Selection;
@@ -87,7 +87,12 @@ pub struct SelectionContext<'cx, 'gcx: 'cx+'tcx, 'tcx: 'cx> {
     /// Controls whether or not to filter out negative impls when selecting.
     /// This is used in librustdoc to distinguish between the lack of an impl
     /// and a negative impl
-    allow_negative_impls: bool
+    allow_negative_impls: bool,
+
+    /// The mode that trait queries run in, which informs our error handling
+    /// policy. In essence, canonicalized queries need their errors propagated
+    /// rather than immediately reported because we do not have accurate spans.
+    query_mode: TraitQueryMode,
 }
 
 #[derive(Clone, Debug)]
@@ -319,7 +324,7 @@ enum BuiltinImplConditions<'tcx> {
 ///     all the "potential success" candidates can potentially succeed,
 ///     so they are no-ops when unioned with a definite error, and within
 ///     the categories it's easy to see that the unions are correct.
-enum EvaluationResult {
+pub enum EvaluationResult {
     /// Evaluation successful
     EvaluatedToOk,
     /// Evaluation is known to be ambiguous - it *might* hold for some
@@ -385,7 +390,7 @@ enum EvaluationResult {
 }
 
 impl EvaluationResult {
-    fn may_apply(self) -> bool {
+    pub fn may_apply(self) -> bool {
         match self {
             EvaluatedToOk |
             EvaluatedToAmbig |
@@ -408,6 +413,26 @@ impl EvaluationResult {
     }
 }
 
+impl_stable_hash_for!(enum self::EvaluationResult {
+    EvaluatedToOk,
+    EvaluatedToAmbig,
+    EvaluatedToUnknown,
+    EvaluatedToRecur,
+    EvaluatedToErr
+});
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+/// Indicates that trait evaluation caused overflow.
+pub struct OverflowError;
+
+impl_stable_hash_for!(struct OverflowError { });
+
+impl<'tcx> From<OverflowError> for SelectionError<'tcx> {
+    fn from(OverflowError: OverflowError) -> SelectionError<'tcx> {
+        SelectionError::Overflow
+    }
+}
+
 #[derive(Clone)]
 pub struct EvaluationCache<'tcx> {
     hashmap: RefCell<FxHashMap<ty::PolyTraitRef<'tcx>, WithDepNode<EvaluationResult>>>
@@ -421,6 +446,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             intercrate: None,
             intercrate_ambiguity_causes: None,
             allow_negative_impls: false,
+            query_mode: TraitQueryMode::Standard,
         }
     }
 
@@ -433,6 +459,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             intercrate: Some(mode),
             intercrate_ambiguity_causes: None,
             allow_negative_impls: false,
+            query_mode: TraitQueryMode::Standard,
         }
     }
 
@@ -445,6 +472,20 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             intercrate: None,
             intercrate_ambiguity_causes: None,
             allow_negative_impls,
+            query_mode: TraitQueryMode::Standard,
+        }
+    }
+
+    pub fn with_query_mode(infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>,
+                           query_mode: TraitQueryMode) -> SelectionContext<'cx, 'gcx, 'tcx> {
+        debug!("with_query_mode({:?})", query_mode);
+        SelectionContext {
+            infcx,
+            freshener: infcx.freshener(),
+            intercrate: None,
+            intercrate_ambiguity_causes: None,
+            allow_negative_impls: false,
+            query_mode,
         }
     }
 
@@ -528,12 +569,27 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         assert!(!obligation.predicate.has_escaping_regions());
 
         let stack = self.push_stack(TraitObligationStackList::empty(), obligation);
-        let ret = match self.candidate_from_obligation(&stack)? {
-            None => None,
-            Some(candidate) => Some(self.confirm_candidate(obligation, candidate)?)
+
+        let candidate = match self.candidate_from_obligation(&stack) {
+            Err(SelectionError::Overflow) => {
+                // In standard mode, overflow must have been caught and reported
+                // earlier.
+                assert!(self.query_mode == TraitQueryMode::Canonical);
+                return Err(SelectionError::Overflow);
+            },
+            Err(e) => { return Err(e); },
+            Ok(None) => { return Ok(None); },
+            Ok(Some(candidate)) => candidate
         };
 
-        Ok(ret)
+        match self.confirm_candidate(obligation, candidate) {
+            Err(SelectionError::Overflow) => {
+                assert!(self.query_mode == TraitQueryMode::Canonical);
+                return Err(SelectionError::Overflow);
+            },
+            Err(e) => Err(e),
+            Ok(candidate) => Ok(Some(candidate))
+        }
     }
 
     ///////////////////////////////////////////////////////////////////////////
@@ -547,32 +603,30 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     // we can be sure it does not.
 
     /// Evaluates whether the obligation `obligation` can be satisfied (by any means).
-    pub fn evaluate_obligation(&mut self,
-                               obligation: &PredicateObligation<'tcx>)
-                               -> bool
+    pub fn predicate_may_hold_fatal(&mut self,
+                                    obligation: &PredicateObligation<'tcx>)
+                                    -> bool
     {
-        debug!("evaluate_obligation({:?})",
+        debug!("predicate_may_hold_fatal({:?})",
                obligation);
 
-        self.probe(|this, _| {
-            this.evaluate_predicate_recursively(TraitObligationStackList::empty(), obligation)
-                .may_apply()
-        })
+        // This fatal query is a stopgap that should only be used in standard mode,
+        // where we do not expect overflow to be propagated.
+        assert!(self.query_mode == TraitQueryMode::Standard);
+
+        self.evaluate_obligation_recursively(obligation)
+            .expect("Overflow should be caught earlier in standard query mode")
+            .may_apply()
     }
 
-    /// Evaluates whether the obligation `obligation` can be satisfied,
-    /// and returns `false` if not certain. However, this is not entirely
-    /// accurate if inference variables are involved.
-    pub fn evaluate_obligation_conservatively(&mut self,
-                                              obligation: &PredicateObligation<'tcx>)
-                                              -> bool
+    /// Evaluates whether the obligation `obligation` can be satisfied and returns
+    /// an `EvaluationResult`.
+    pub fn evaluate_obligation_recursively(&mut self,
+                                           obligation: &PredicateObligation<'tcx>)
+                                           -> Result<EvaluationResult, OverflowError>
     {
-        debug!("evaluate_obligation_conservatively({:?})",
-               obligation);
-
         self.probe(|this, _| {
             this.evaluate_predicate_recursively(TraitObligationStackList::empty(), obligation)
-                == EvaluatedToOk
         })
     }
 
@@ -582,29 +636,29 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     fn evaluate_predicates_recursively<'a,'o,I>(&mut self,
                                                 stack: TraitObligationStackList<'o, 'tcx>,
                                                 predicates: I)
-                                                -> EvaluationResult
+                                                -> Result<EvaluationResult, OverflowError>
         where I : IntoIterator<Item=&'a PredicateObligation<'tcx>>, 'tcx:'a
     {
         let mut result = EvaluatedToOk;
         for obligation in predicates {
-            let eval = self.evaluate_predicate_recursively(stack, obligation);
+            let eval = self.evaluate_predicate_recursively(stack, obligation)?;
             debug!("evaluate_predicate_recursively({:?}) = {:?}",
                    obligation, eval);
             if let EvaluatedToErr = eval {
                 // fast-path - EvaluatedToErr is the top of the lattice,
                 // so we don't need to look on the other predicates.
-                return EvaluatedToErr;
+                return Ok(EvaluatedToErr);
             } else {
                 result = cmp::max(result, eval);
             }
         }
-        result
+        Ok(result)
     }
 
     fn evaluate_predicate_recursively<'o>(&mut self,
                                           previous_stack: TraitObligationStackList<'o, 'tcx>,
                                           obligation: &PredicateObligation<'tcx>)
-                                           -> EvaluationResult
+                                           -> Result<EvaluationResult, OverflowError>
     {
         debug!("evaluate_predicate_recursively({:?})",
                obligation);
@@ -620,11 +674,10 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 // does this code ever run?
                 match self.infcx.subtype_predicate(&obligation.cause, obligation.param_env, p) {
                     Some(Ok(InferOk { obligations, .. })) => {
-                        self.evaluate_predicates_recursively(previous_stack, &obligations);
-                        EvaluatedToOk
+                        self.evaluate_predicates_recursively(previous_stack, &obligations)
                     },
-                    Some(Err(_)) => EvaluatedToErr,
-                    None => EvaluatedToAmbig,
+                    Some(Err(_)) => Ok(EvaluatedToErr),
+                    None => Ok(EvaluatedToAmbig),
                 }
             }
 
@@ -636,21 +689,21 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                     Some(obligations) =>
                         self.evaluate_predicates_recursively(previous_stack, obligations.iter()),
                     None =>
-                        EvaluatedToAmbig,
+                        Ok(EvaluatedToAmbig),
                 }
             }
 
             ty::Predicate::TypeOutlives(..) | ty::Predicate::RegionOutlives(..) => {
                 // we do not consider region relationships when
                 // evaluating trait matches
-                EvaluatedToOk
+                Ok(EvaluatedToOk)
             }
 
             ty::Predicate::ObjectSafe(trait_def_id) => {
                 if self.tcx().is_object_safe(trait_def_id) {
-                    EvaluatedToOk
+                    Ok(EvaluatedToOk)
                 } else {
-                    EvaluatedToErr
+                    Ok(EvaluatedToErr)
                 }
             }
 
@@ -668,10 +721,10 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                         result
                     }
                     Ok(None) => {
-                        EvaluatedToAmbig
+                        Ok(EvaluatedToAmbig)
                     }
                     Err(_) => {
-                        EvaluatedToErr
+                        Ok(EvaluatedToErr)
                     }
                 }
             }
@@ -680,13 +733,13 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 match self.infcx.closure_kind(closure_def_id, closure_substs) {
                     Some(closure_kind) => {
                         if closure_kind.extends(kind) {
-                            EvaluatedToOk
+                            Ok(EvaluatedToOk)
                         } else {
-                            EvaluatedToErr
+                            Ok(EvaluatedToErr)
                         }
                     }
                     None => {
-                        EvaluatedToAmbig
+                        Ok(EvaluatedToAmbig)
                     }
                 }
             }
@@ -707,16 +760,16 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                                 promoted: None
                             };
                             match self.tcx().const_eval(param_env.and(cid)) {
-                                Ok(_) => EvaluatedToOk,
-                                Err(_) => EvaluatedToErr
+                                Ok(_) => Ok(EvaluatedToOk),
+                                Err(_) => Ok(EvaluatedToErr)
                             }
                         } else {
-                            EvaluatedToErr
+                            Ok(EvaluatedToErr)
                         }
                     }
                     None => {
                         // Inference variables still left in param_env or substs.
-                        EvaluatedToAmbig
+                        Ok(EvaluatedToAmbig)
                     }
                 }
             }
@@ -726,7 +779,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     fn evaluate_trait_predicate_recursively<'o>(&mut self,
                                                 previous_stack: TraitObligationStackList<'o, 'tcx>,
                                                 mut obligation: TraitObligation<'tcx>)
-                                                -> EvaluationResult
+                                                -> Result<EvaluationResult, OverflowError>
     {
         debug!("evaluate_trait_predicate_recursively({:?})",
                obligation);
@@ -745,22 +798,23 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             debug!("CACHE HIT: EVAL({:?})={:?}",
                    fresh_trait_ref,
                    result);
-            return result;
+            return Ok(result);
         }
 
         let (result, dep_node) = self.in_task(|this| this.evaluate_stack(&stack));
+        let result = result?;
 
         debug!("CACHE MISS: EVAL({:?})={:?}",
                fresh_trait_ref,
                result);
         self.insert_evaluation_cache(obligation.param_env, fresh_trait_ref, dep_node, result);
 
-        result
+        Ok(result)
     }
 
     fn evaluate_stack<'o>(&mut self,
                           stack: &TraitObligationStack<'o, 'tcx>)
-                          -> EvaluationResult
+                          -> Result<EvaluationResult, OverflowError>
     {
         // In intercrate mode, whenever any of the types are unbound,
         // there can always be an impl. Even if there are no impls in
@@ -815,7 +869,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                     }
                 }
             }
-            return EvaluatedToAmbig;
+            return Ok(EvaluatedToAmbig);
         }
         if unbound_input_types &&
               stack.iter().skip(1).any(
@@ -825,7 +879,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         {
             debug!("evaluate_stack({:?}) --> unbound argument, recursive --> giving up",
                    stack.fresh_trait_ref);
-            return EvaluatedToUnknown;
+            return Ok(EvaluatedToUnknown);
         }
 
         // If there is any previous entry on the stack that precisely
@@ -860,18 +914,19 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             if self.coinductive_match(cycle) {
                 debug!("evaluate_stack({:?}) --> recursive, coinductive",
                        stack.fresh_trait_ref);
-                return EvaluatedToOk;
+                return Ok(EvaluatedToOk);
             } else {
                 debug!("evaluate_stack({:?}) --> recursive, inductive",
                        stack.fresh_trait_ref);
-                return EvaluatedToRecur;
+                return Ok(EvaluatedToRecur);
             }
         }
 
         match self.candidate_from_obligation(stack) {
             Ok(Some(c)) => self.evaluate_candidate(stack, &c),
-            Ok(None) => EvaluatedToAmbig,
-            Err(..) => EvaluatedToErr
+            Ok(None) => Ok(EvaluatedToAmbig),
+            Err(Overflow) => Err(OverflowError),
+            Err(..) => Ok(EvaluatedToErr)
         }
     }
 
@@ -909,7 +964,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     fn evaluate_candidate<'o>(&mut self,
                               stack: &TraitObligationStack<'o, 'tcx>,
                               candidate: &SelectionCandidate<'tcx>)
-                              -> EvaluationResult
+                              -> Result<EvaluationResult, OverflowError>
     {
         debug!("evaluate_candidate: depth={} candidate={:?}",
                stack.obligation.recursion_depth, candidate);
@@ -921,12 +976,12 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                         stack.list(),
                         selection.nested_obligations().iter())
                 }
-                Err(..) => EvaluatedToErr
+                Err(..) => Ok(EvaluatedToErr)
             }
-        });
+        })?;
         debug!("evaluate_candidate: depth={} result={:?}",
                stack.obligation.recursion_depth, result);
-        result
+        Ok(result)
     }
 
     fn check_evaluation_cache(&self,
@@ -1000,7 +1055,14 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         // not update) the cache.
         let recursion_limit = *self.infcx.tcx.sess.recursion_limit.get();
         if stack.obligation.recursion_depth >= recursion_limit {
-            self.infcx().report_overflow_error(&stack.obligation, true);
+            match self.query_mode {
+                TraitQueryMode::Standard => {
+                    self.infcx().report_overflow_error(&stack.obligation, true);
+                },
+                TraitQueryMode::Canonical => {
+                    return Err(Overflow);
+                },
+            }
         }
 
         // Check the cache. Note that we skolemize the trait-ref
@@ -1081,9 +1143,15 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                     debug!("evaluate_stack: intercrate_ambiguity_causes is some");
                     // Heuristics: show the diagnostics when there are no candidates in crate.
                     if let Ok(candidate_set) = self.assemble_candidates(stack) {
-                        if !candidate_set.ambiguous && candidate_set.vec.iter().all(|c| {
-                            !self.evaluate_candidate(stack, &c).may_apply()
-                        }) {
+                        let no_candidates_apply =
+                            candidate_set
+                            .vec
+                            .iter()
+                            .map(|c| self.evaluate_candidate(stack, &c))
+                            .collect::<Result<Vec<_>, OverflowError>>()?
+                            .iter()
+                            .all(|r| !r.may_apply());
+                        if !candidate_set.ambiguous && no_candidates_apply {
                             let trait_ref = stack.obligation.predicate.skip_binder().trait_ref;
                             let self_ty = trait_ref.self_ty();
                             let trait_desc = trait_ref.to_string();
@@ -1151,18 +1219,21 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         }
 
         // Winnow, but record the exact outcome of evaluation, which
-        // is needed for specialization.
-        let mut candidates: Vec<_> = candidates.into_iter().filter_map(|c| {
-            let eval = self.evaluate_candidate(stack, &c);
-            if eval.may_apply() {
-                Some(EvaluatedCandidate {
+        // is needed for specialization. Propagate overflow if it occurs.
+        let candidates: Result<Vec<Option<EvaluatedCandidate>>, _> = candidates
+            .into_iter()
+            .map(|c| match self.evaluate_candidate(stack, &c) {
+                Ok(eval) if eval.may_apply() => Ok(Some(EvaluatedCandidate {
                     candidate: c,
                     evaluation: eval,
-                })
-            } else {
-                None
-            }
-        }).collect();
+                })),
+                Ok(_) => Ok(None),
+                Err(OverflowError) => Err(Overflow),
+            })
+            .collect();
+
+        let mut candidates: Vec<EvaluatedCandidate> =
+            candidates?.into_iter().filter_map(|c| c).collect();
 
         // If there are STILL multiple candidate, we can further
         // reduce the list by dropping duplicates -- including
@@ -1438,7 +1509,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         let poly_trait_predicate =
             self.infcx().resolve_type_vars_if_possible(&obligation.predicate);
         let (skol_trait_predicate, skol_map) =
-            self.infcx().skolemize_late_bound_regions(&poly_trait_predicate, snapshot);
+            self.infcx().skolemize_late_bound_regions(&poly_trait_predicate);
         debug!("match_projection_obligation_against_definition_bounds: \
                 skol_trait_predicate={:?} skol_map={:?}",
                skol_trait_predicate,
@@ -1537,12 +1608,14 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         let matching_bounds =
             all_bounds.filter(|p| p.def_id() == stack.obligation.predicate.def_id());
 
-        let matching_bounds =
-            matching_bounds.filter(
-                |bound| self.evaluate_where_clause(stack, bound.clone()).may_apply());
-
-        let param_candidates =
-            matching_bounds.map(|bound| ParamCandidate(bound));
+        // keep only those bounds which may apply, and propagate overflow if it occurs
+        let mut param_candidates = vec![];
+        for bound in matching_bounds {
+            let wc = self.evaluate_where_clause(stack, bound.clone())?;
+            if wc.may_apply() {
+                param_candidates.push(ParamCandidate(bound));
+            }
+        }
 
         candidates.vec.extend(param_candidates);
 
@@ -1552,14 +1625,14 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     fn evaluate_where_clause<'o>(&mut self,
                                  stack: &TraitObligationStack<'o, 'tcx>,
                                  where_clause_trait_ref: ty::PolyTraitRef<'tcx>)
-                                 -> EvaluationResult
+                                 -> Result<EvaluationResult, OverflowError>
     {
         self.probe(move |this, _| {
             match this.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) {
                 Ok(obligations) => {
                     this.evaluate_predicates_recursively(stack.list(), obligations.iter())
                 }
-                Err(()) => EvaluatedToErr
+                Err(()) => Ok(EvaluatedToErr)
             }
         })
     }
@@ -2265,7 +2338,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
 
             self.in_snapshot(|this, snapshot| {
                 let (skol_ty, skol_map) =
-                    this.infcx().skolemize_late_bound_regions(&ty, snapshot);
+                    this.infcx().skolemize_late_bound_regions(&ty);
                 let Normalized { value: normalized_ty, mut obligations } =
                     project::normalize_with_depth(this,
                                                   param_env,
@@ -2486,7 +2559,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         let trait_obligations = self.in_snapshot(|this, snapshot| {
             let poly_trait_ref = obligation.predicate.to_poly_trait_ref();
             let (trait_ref, skol_map) =
-                this.infcx().skolemize_late_bound_regions(&poly_trait_ref, snapshot);
+                this.infcx().skolemize_late_bound_regions(&poly_trait_ref);
             let cause = obligation.derived_cause(ImplDerivedObligation);
             this.impl_or_trait_obligations(cause,
                                            obligation.recursion_depth + 1,
@@ -3069,8 +3142,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         }
 
         let (skol_obligation, skol_map) = self.infcx().skolemize_late_bound_regions(
-            &obligation.predicate,
-            snapshot);
+            &obligation.predicate);
         let skol_obligation_trait_ref = skol_obligation.trait_ref;
 
         let impl_substs = self.infcx.fresh_substs_for_item(obligation.cause.span,
diff --git a/src/librustc/traits/structural_impls.rs b/src/librustc/traits/structural_impls.rs
index 1e3e4160de1..d7e42655bbb 100644
--- a/src/librustc/traits/structural_impls.rs
+++ b/src/librustc/traits/structural_impls.rs
@@ -177,6 +177,7 @@ impl<'a, 'tcx> Lift<'tcx> for traits::SelectionError<'a> {
             super::ConstEvalFailure(ref err) => {
                 tcx.lift(err).map(super::ConstEvalFailure)
             }
+            super::Overflow => bug!() // FIXME: ape ConstEvalFailure?
         }
     }
 }
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 4f49b159ad3..3d154e43a9a 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -34,7 +34,7 @@ use middle::resolve_lifetime::{self, ObjectLifetimeDefault};
 use middle::stability;
 use mir::{self, Mir, interpret};
 use mir::interpret::{Value, PrimVal};
-use ty::subst::{Kind, Substs};
+use ty::subst::{Kind, Substs, Subst};
 use ty::ReprOptions;
 use ty::Instance;
 use traits;
@@ -1467,6 +1467,14 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         self.borrowck_mode().use_mir()
     }
 
+    /// If true, pattern variables for use in guards on match arms
+    /// will be bound as references to the data, and occurrences of
+    /// those variables in the guard expression will implicitly
+    /// dereference those bindings. (See rust-lang/rust#27282.)
+    pub fn all_pat_vars_are_implicit_refs_within_guards(self) -> bool {
+        self.borrowck_mode().use_mir()
+    }
+
     /// If true, we should enable two-phase borrows checks. This is
     /// done with either `-Ztwo-phase-borrows` or with
     /// `#![feature(nll)]`.
@@ -2119,7 +2127,7 @@ macro_rules! intern_method {
                                             $alloc_method:ident,
                                             $alloc_to_key:expr,
                                             $alloc_to_ret:expr,
-                                            $needs_infer:expr) -> $ty:ty) => {
+                                            $keep_in_local_tcx:expr) -> $ty:ty) => {
         impl<'a, 'gcx, $lt_tcx> TyCtxt<'a, 'gcx, $lt_tcx> {
             pub fn $method(self, v: $alloc) -> &$lt_tcx $ty {
                 {
@@ -2137,7 +2145,7 @@ macro_rules! intern_method {
                 // HACK(eddyb) Depend on flags being accurate to
                 // determine that all contents are in the global tcx.
                 // See comments on Lift for why we can't use that.
-                if !($needs_infer)(&v) {
+                if !($keep_in_local_tcx)(&v) {
                     if !self.is_global() {
                         let v = unsafe {
                             mem::transmute(v)
@@ -2165,7 +2173,7 @@ macro_rules! intern_method {
 }
 
 macro_rules! direct_interners {
-    ($lt_tcx:tt, $($name:ident: $method:ident($needs_infer:expr) -> $ty:ty),+) => {
+    ($lt_tcx:tt, $($name:ident: $method:ident($keep_in_local_tcx:expr) -> $ty:ty),+) => {
         $(impl<$lt_tcx> PartialEq for Interned<$lt_tcx, $ty> {
             fn eq(&self, other: &Self) -> bool {
                 self.0 == other.0
@@ -2180,7 +2188,10 @@ macro_rules! direct_interners {
             }
         }
 
-        intern_method!($lt_tcx, $name: $method($ty, alloc, |x| x, |x| x, $needs_infer) -> $ty);)+
+        intern_method!(
+            $lt_tcx,
+            $name: $method($ty, alloc, |x| x, |x| x, $keep_in_local_tcx) -> $ty
+        );)+
     }
 }
 
@@ -2189,12 +2200,7 @@ pub fn keep_local<'tcx, T: ty::TypeFoldable<'tcx>>(x: &T) -> bool {
 }
 
 direct_interners!('tcx,
-    region: mk_region(|r| {
-        match r {
-            &ty::ReVar(_) | &ty::ReSkolemized(..) => true,
-            _ => false
-        }
-    }) -> RegionKind,
+    region: mk_region(|r: &RegionKind| r.keep_in_local_tcx()) -> RegionKind,
     const_: mk_const(|c: &Const| keep_local(&c.ty) || keep_local(&c.val)) -> Const<'tcx>
 );
 
@@ -2328,7 +2334,15 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     pub fn mk_box(self, ty: Ty<'tcx>) -> Ty<'tcx> {
         let def_id = self.require_lang_item(lang_items::OwnedBoxLangItem);
         let adt_def = self.adt_def(def_id);
-        let substs = self.mk_substs(iter::once(Kind::from(ty)));
+        let generics = self.generics_of(def_id);
+        let mut substs = vec![Kind::from(ty)];
+        // Add defaults for other generic params if there are some.
+        for def in generics.types.iter().skip(1) {
+            assert!(def.has_default);
+            let ty = self.type_of(def.def_id).subst(self, &substs);
+            substs.push(ty.into());
+        }
+        let substs = self.mk_substs(substs.into_iter());
         self.mk_ty(TyAdt(adt_def, substs))
     }
 
@@ -2471,7 +2485,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     }
 
     pub fn mk_self_type(self) -> Ty<'tcx> {
-        self.mk_param(0, keywords::SelfType.name().as_str())
+        self.mk_param(0, keywords::SelfType.name().as_interned_str())
     }
 
     pub fn mk_param_from_def(self, def: &ty::TypeParameterDef) -> Ty<'tcx> {
diff --git a/src/librustc/ty/fold.rs b/src/librustc/ty/fold.rs
index eb06852c65d..1793b5e1edb 100644
--- a/src/librustc/ty/fold.rs
+++ b/src/librustc/ty/fold.rs
@@ -43,8 +43,8 @@ use middle::const_val::ConstVal;
 use hir::def_id::DefId;
 use ty::{self, Binder, Ty, TyCtxt, TypeFlags};
 
+use rustc_data_structures::lazy_btree_map::LazyBTreeMap;
 use std::fmt;
-use std::collections::BTreeMap;
 use util::nodemap::FxHashSet;
 
 /// The TypeFoldable trait is implemented for every type that can be folded.
@@ -91,6 +91,9 @@ pub trait TypeFoldable<'tcx>: fmt::Debug + Clone {
     fn needs_infer(&self) -> bool {
         self.has_type_flags(TypeFlags::HAS_TY_INFER | TypeFlags::HAS_RE_INFER)
     }
+    fn has_skol(&self) -> bool {
+        self.has_type_flags(TypeFlags::HAS_RE_SKOL)
+    }
     fn needs_subst(&self) -> bool {
         self.has_type_flags(TypeFlags::NEEDS_SUBST)
     }
@@ -111,15 +114,6 @@ pub trait TypeFoldable<'tcx>: fmt::Debug + Clone {
         self.has_type_flags(TypeFlags::HAS_FREE_REGIONS)
     }
 
-    fn is_normalized_for_trans(&self) -> bool {
-        !self.has_type_flags(TypeFlags::HAS_RE_INFER |
-                             TypeFlags::HAS_FREE_REGIONS |
-                             TypeFlags::HAS_TY_INFER |
-                             TypeFlags::HAS_PARAMS |
-                             TypeFlags::HAS_NORMALIZABLE_PROJECTION |
-                             TypeFlags::HAS_TY_ERR |
-                             TypeFlags::HAS_SELF)
-    }
     /// Indicates whether this value references only 'global'
     /// types/lifetimes that are the same regardless of what fn we are
     /// in. This is used for caching. Errs on the side of returning
@@ -334,7 +328,7 @@ struct RegionReplacer<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     tcx: TyCtxt<'a, 'gcx, 'tcx>,
     current_depth: u32,
     fld_r: &'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a),
-    map: BTreeMap<ty::BoundRegion, ty::Region<'tcx>>
+    map: LazyBTreeMap<ty::BoundRegion, ty::Region<'tcx>>
 }
 
 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
@@ -349,7 +343,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     pub fn replace_late_bound_regions<T,F>(self,
         value: &Binder<T>,
         mut f: F)
-        -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
+        -> (T, LazyBTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
         where F : FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
               T : TypeFoldable<'tcx>,
     {
@@ -462,7 +456,7 @@ impl<'a, 'gcx, 'tcx> RegionReplacer<'a, 'gcx, 'tcx> {
             tcx,
             current_depth: 1,
             fld_r,
-            map: BTreeMap::default()
+            map: LazyBTreeMap::default()
         }
     }
 }
diff --git a/src/librustc/ty/item_path.rs b/src/librustc/ty/item_path.rs
index 2819141c81b..752b7f69a6a 100644
--- a/src/librustc/ty/item_path.rs
+++ b/src/librustc/ty/item_path.rs
@@ -14,7 +14,7 @@ use ty::{self, Ty, TyCtxt};
 use middle::cstore::{ExternCrate, ExternCrateSource};
 use syntax::ast;
 use syntax::symbol::Symbol;
-use syntax::symbol::InternedString;
+use syntax::symbol::LocalInternedString;
 
 use std::cell::Cell;
 
@@ -131,7 +131,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     {
         let visible_parent_map = self.visible_parent_map(LOCAL_CRATE);
 
-        let (mut cur_def, mut cur_path) = (external_def_id, Vec::<InternedString>::new());
+        let (mut cur_def, mut cur_path) = (external_def_id, Vec::<LocalInternedString>::new());
         loop {
             // If `cur_def` is a direct or injected extern crate, push the path to the crate
             // followed by the path to the item within the crate and return.
@@ -168,8 +168,9 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             }
 
             let data = cur_def_key.disambiguated_data.data;
-            let symbol =
-                data.get_opt_name().unwrap_or_else(|| Symbol::intern("<unnamed>").as_str());
+            let symbol = data.get_opt_name().map(|n| n.as_str()).unwrap_or_else(|| {
+                Symbol::intern("<unnamed>").as_str()
+            });
             cur_path.push(symbol);
 
             match visible_parent_map.get(&cur_def) {
@@ -221,7 +222,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             data @ DefPathData::GlobalMetaData(..) => {
                 let parent_def_id = self.parent_def_id(def_id).unwrap();
                 self.push_item_path(buffer, parent_def_id);
-                buffer.push(&data.as_interned_str());
+                buffer.push(&data.as_interned_str().as_symbol().as_str());
             }
             DefPathData::StructCtor => { // present `X` instead of `X::{{constructor}}`
                 let parent_def_id = self.parent_def_id(def_id).unwrap();
diff --git a/src/librustc/ty/layout.rs b/src/librustc/ty/layout.rs
index ef2a4246628..a319b341ebb 100644
--- a/src/librustc/ty/layout.rs
+++ b/src/librustc/ty/layout.rs
@@ -19,7 +19,6 @@ use std::cmp;
 use std::fmt;
 use std::i128;
 use std::mem;
-use std::ops::RangeInclusive;
 
 use ich::StableHashingContext;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
@@ -149,7 +148,7 @@ pub const FAT_PTR_ADDR: usize = 0;
 /// - For a slice, this is the length.
 pub const FAT_PTR_EXTRA: usize = 1;
 
-#[derive(Copy, Clone, Debug)]
+#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
 pub enum LayoutError<'tcx> {
     Unknown(Ty<'tcx>),
     SizeOverflow(Ty<'tcx>)
@@ -492,7 +491,7 @@ impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
             ty::TyFloat(FloatTy::F64) => scalar(F64),
             ty::TyFnPtr(_) => {
                 let mut ptr = scalar_unit(Pointer);
-                ptr.valid_range.start = 1;
+                ptr.valid_range = 1..=*ptr.valid_range.end();
                 tcx.intern_layout(LayoutDetails::scalar(self, ptr))
             }
 
@@ -506,7 +505,7 @@ impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
             ty::TyRawPtr(ty::TypeAndMut { ty: pointee, .. }) => {
                 let mut data_ptr = scalar_unit(Pointer);
                 if !ty.is_unsafe_ptr() {
-                    data_ptr.valid_range.start = 1;
+                    data_ptr.valid_range = 1..=*data_ptr.valid_range.end();
                 }
 
                 let pointee = tcx.normalize_erasing_regions(param_env, pointee);
@@ -524,7 +523,7 @@ impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
                     }
                     ty::TyDynamic(..) => {
                         let mut vtable = scalar_unit(Pointer);
-                        vtable.valid_range.start = 1;
+                        vtable.valid_range = 1..=*vtable.valid_range.end();
                         vtable
                     }
                     _ => return Err(LayoutError::Unknown(unsized_part))
@@ -751,8 +750,8 @@ impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
                         match st.abi {
                             Abi::Scalar(ref mut scalar) |
                             Abi::ScalarPair(ref mut scalar, _) => {
-                                if scalar.valid_range.start == 0 {
-                                    scalar.valid_range.start = 1;
+                                if *scalar.valid_range.start() == 0 {
+                                    scalar.valid_range = 1..=*scalar.valid_range.end();
                                 }
                             }
                             _ => {}
@@ -788,18 +787,15 @@ impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
                                 }
                             }
                         }
-                        if niche_variants.start > v {
-                            niche_variants.start = v;
-                        }
-                        niche_variants.end = v;
+                        niche_variants = *niche_variants.start().min(&v)..=v;
                     }
 
-                    if niche_variants.start > niche_variants.end {
+                    if niche_variants.start() > niche_variants.end() {
                         dataful_variant = None;
                     }
 
                     if let Some(i) = dataful_variant {
-                        let count = (niche_variants.end - niche_variants.start + 1) as u128;
+                        let count = (niche_variants.end() - niche_variants.start() + 1) as u128;
                         for (field_index, &field) in variants[i].iter().enumerate() {
                             let (offset, niche, niche_start) =
                                 match self.find_niche(field, count)? {
@@ -897,7 +893,7 @@ impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
                 }
 
                 // Create the set of structs that represent each variant.
-                let mut variants = variants.into_iter().enumerate().map(|(i, field_layouts)| {
+                let mut layout_variants = variants.iter().enumerate().map(|(i, field_layouts)| {
                     let mut st = univariant_uninterned(&field_layouts,
                         &def.repr, StructKind::Prefixed(min_ity.size(), prefix_align))?;
                     st.variants = Variants::Single { index: i };
@@ -944,11 +940,15 @@ impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
                 // We increase the size of the discriminant to avoid LLVM copying
                 // padding when it doesn't need to. This normally causes unaligned
                 // load/stores and excessive memcpy/memset operations. By using a
-                // bigger integer size, LLVM can be sure about it's contents and
+                // bigger integer size, LLVM can be sure about its contents and
                 // won't be so conservative.
 
                 // Use the initial field alignment
-                let mut ity = Integer::for_abi_align(dl, start_align).unwrap_or(min_ity);
+                let mut ity = if def.repr.c() || def.repr.int.is_some() {
+                    min_ity
+                } else {
+                    Integer::for_abi_align(dl, start_align).unwrap_or(min_ity)
+                };
 
                 // If the alignment is not larger than the chosen discriminant size,
                 // don't use the alignment as the final size.
@@ -958,7 +958,7 @@ impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
                     // Patch up the variants' first few fields.
                     let old_ity_size = min_ity.size();
                     let new_ity_size = ity.size();
-                    for variant in &mut variants {
+                    for variant in &mut layout_variants {
                         if variant.abi == Abi::Uninhabited {
                             continue;
                         }
@@ -985,15 +985,80 @@ impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
                     value: Int(ity, signed),
                     valid_range: (min as u128 & tag_mask)..=(max as u128 & tag_mask),
                 };
-                let abi = if tag.value.size(dl) == size {
-                    Abi::Scalar(tag.clone())
-                } else {
-                    Abi::Aggregate { sized: true }
-                };
+                let mut abi = Abi::Aggregate { sized: true };
+                if tag.value.size(dl) == size {
+                    abi = Abi::Scalar(tag.clone());
+                } else if !tag.is_bool() {
+                    // HACK(nox): Blindly using ScalarPair for all tagged enums
+                    // where applicable leads to Option<u8> being handled as {i1, i8},
+                    // which later confuses SROA and some loop optimisations,
+                    // ultimately leading to the repeat-trusted-len test
+                    // failing. We make the trade-off of using ScalarPair only
+                    // for types where the tag isn't a boolean.
+                    let mut common_prim = None;
+                    for (field_layouts, layout_variant) in variants.iter().zip(&layout_variants) {
+                        let offsets = match layout_variant.fields {
+                            FieldPlacement::Arbitrary { ref offsets, .. } => offsets,
+                            _ => bug!(),
+                        };
+                        let mut fields = field_layouts
+                            .iter()
+                            .zip(offsets)
+                            .filter(|p| !p.0.is_zst());
+                        let (field, offset) = match (fields.next(), fields.next()) {
+                            (None, None) => continue,
+                            (Some(pair), None) => pair,
+                            _ => {
+                                common_prim = None;
+                                break;
+                            }
+                        };
+                        let prim = match field.details.abi {
+                            Abi::Scalar(ref scalar) => scalar.value,
+                            _ => {
+                                common_prim = None;
+                                break;
+                            }
+                        };
+                        if let Some(pair) = common_prim {
+                            // This is pretty conservative. We could go fancier
+                            // by conflating things like i32 and u32, or even
+                            // realising that (u8, u8) could just cohabit with
+                            // u16 or even u32.
+                            if pair != (prim, offset) {
+                                common_prim = None;
+                                break;
+                            }
+                        } else {
+                            common_prim = Some((prim, offset));
+                        }
+                    }
+                    if let Some((prim, offset)) = common_prim {
+                        let pair = scalar_pair(tag.clone(), scalar_unit(prim));
+                        let pair_offsets = match pair.fields {
+                            FieldPlacement::Arbitrary {
+                                ref offsets,
+                                ref memory_index
+                            } => {
+                                assert_eq!(memory_index, &[0, 1]);
+                                offsets
+                            }
+                            _ => bug!()
+                        };
+                        if pair_offsets[0] == Size::from_bytes(0) &&
+                            pair_offsets[1] == *offset &&
+                            align == pair.align &&
+                            size == pair.size {
+                            // We can use `ScalarPair` only when it matches our
+                            // already computed layout (including `#[repr(C)]`).
+                            abi = pair.abi;
+                        }
+                    }
+                }
                 tcx.intern_layout(LayoutDetails {
                     variants: Variants::Tagged {
                         discr: tag,
-                        variants
+                        variants: layout_variants,
                     },
                     fields: FieldPlacement::Arbitrary {
                         offsets: vec![Size::from_bytes(0)],
@@ -1594,10 +1659,10 @@ impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
             let max_value = !0u128 >> (128 - bits);
 
             // Find out how many values are outside the valid range.
-            let niches = if v.start <= v.end {
-                v.start + (max_value - v.end)
+            let niches = if v.start() <= v.end() {
+                v.start() + (max_value - v.end())
             } else {
-                v.start - v.end - 1
+                v.start() - v.end() - 1
             };
 
             // Give up if we can't fit `count` consecutive niches.
@@ -1605,11 +1670,11 @@ impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
                 return None;
             }
 
-            let niche_start = v.end.wrapping_add(1) & max_value;
-            let niche_end = v.end.wrapping_add(count) & max_value;
+            let niche_start = v.end().wrapping_add(1) & max_value;
+            let niche_end = v.end().wrapping_add(count) & max_value;
             Some((offset, Scalar {
                 value,
-                valid_range: v.start..=niche_end
+                valid_range: *v.start()..=niche_end
             }, niche_start))
         };
 
@@ -1679,14 +1744,14 @@ impl<'a> HashStable<StableHashingContext<'a>> for Variants {
             }
             NicheFilling {
                 dataful_variant,
-                niche_variants: RangeInclusive { start, end },
+                ref niche_variants,
                 ref niche,
                 niche_start,
                 ref variants,
             } => {
                 dataful_variant.hash_stable(hcx, hasher);
-                start.hash_stable(hcx, hasher);
-                end.hash_stable(hcx, hasher);
+                niche_variants.start().hash_stable(hcx, hasher);
+                niche_variants.end().hash_stable(hcx, hasher);
                 niche.hash_stable(hcx, hasher);
                 niche_start.hash_stable(hcx, hasher);
                 variants.hash_stable(hcx, hasher);
@@ -1749,10 +1814,10 @@ impl<'a> HashStable<StableHashingContext<'a>> for Scalar {
     fn hash_stable<W: StableHasherResult>(&self,
                                           hcx: &mut StableHashingContext<'a>,
                                           hasher: &mut StableHasher<W>) {
-        let Scalar { value, valid_range: RangeInclusive { start, end } } = *self;
+        let Scalar { value, ref valid_range } = *self;
         value.hash_stable(hcx, hasher);
-        start.hash_stable(hcx, hasher);
-        end.hash_stable(hcx, hasher);
+        valid_range.start().hash_stable(hcx, hasher);
+        valid_range.end().hash_stable(hcx, hasher);
     }
 }
 
diff --git a/src/librustc/ty/maps/config.rs b/src/librustc/ty/maps/config.rs
index 735fe06560f..57c8c4f34e7 100644
--- a/src/librustc/ty/maps/config.rs
+++ b/src/librustc/ty/maps/config.rs
@@ -9,24 +9,45 @@
 // except according to those terms.
 
 use dep_graph::SerializedDepNodeIndex;
+use dep_graph::DepNode;
 use hir::def_id::{CrateNum, DefId, DefIndex};
 use mir::interpret::{GlobalId};
-use traits::query::{CanonicalProjectionGoal, CanonicalTyGoal};
+use traits::query::{CanonicalPredicateGoal, CanonicalProjectionGoal, CanonicalTyGoal};
 use ty::{self, ParamEnvAnd, Ty, TyCtxt};
 use ty::subst::Substs;
 use ty::maps::queries;
+use ty::maps::Query;
+use ty::maps::QueryMap;
 
 use std::hash::Hash;
+use std::fmt::Debug;
 use syntax_pos::symbol::InternedString;
+use rustc_data_structures::sync::Lock;
+use rustc_data_structures::stable_hasher::HashStable;
+use ich::StableHashingContext;
 
 /// Query configuration and description traits.
 
-pub trait QueryConfig {
-    type Key: Eq + Hash + Clone;
-    type Value;
+pub trait QueryConfig<'tcx> {
+    const NAME: &'static str;
+
+    type Key: Eq + Hash + Clone + Debug;
+    type Value: Clone + for<'a> HashStable<StableHashingContext<'a>>;
+
+    fn query(key: Self::Key) -> Query<'tcx>;
+
+    // Don't use this method to access query results, instead use the methods on TyCtxt
+    fn query_map<'a>(tcx: TyCtxt<'a, 'tcx, '_>) -> &'a Lock<QueryMap<'tcx, Self>>;
+
+    fn to_dep_node(tcx: TyCtxt<'_, 'tcx, '_>, key: &Self::Key) -> DepNode;
+
+    // Don't use this method to compute query results, instead use the methods on TyCtxt
+    fn compute(tcx: TyCtxt<'_, 'tcx, '_>, key: Self::Key) -> Self::Value;
+
+    fn handle_cycle_error(tcx: TyCtxt<'_, 'tcx, '_>) -> Self::Value;
 }
 
-pub(super) trait QueryDescription<'tcx>: QueryConfig {
+pub trait QueryDescription<'tcx>: QueryConfig<'tcx> {
     fn describe(tcx: TyCtxt, key: Self::Key) -> String;
 
     #[inline]
@@ -41,7 +62,7 @@ pub(super) trait QueryDescription<'tcx>: QueryConfig {
     }
 }
 
-impl<'tcx, M: QueryConfig<Key=DefId>> QueryDescription<'tcx> for M {
+impl<'tcx, M: QueryConfig<'tcx, Key=DefId>> QueryDescription<'tcx> for M {
     default fn describe(tcx: TyCtxt, def_id: DefId) -> String {
         if !tcx.sess.verbose() {
             format!("processing `{}`", tcx.item_path_str(def_id))
@@ -73,6 +94,12 @@ impl<'tcx> QueryDescription<'tcx> for queries::normalize_ty_after_erasing_region
     }
 }
 
+impl<'tcx> QueryDescription<'tcx> for queries::evaluate_obligation<'tcx> {
+    fn describe(_tcx: TyCtxt, goal: CanonicalPredicateGoal<'tcx>) -> String {
+        format!("evaluating trait selection obligation `{}`", goal.value.value)
+    }
+}
+
 impl<'tcx> QueryDescription<'tcx> for queries::is_copy_raw<'tcx> {
     fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
         format!("computing whether `{}` is `Copy`", env.value)
diff --git a/src/librustc/ty/maps/job.rs b/src/librustc/ty/maps/job.rs
index 374406158c1..3b6af018d6b 100644
--- a/src/librustc/ty/maps/job.rs
+++ b/src/librustc/ty/maps/job.rs
@@ -17,13 +17,10 @@ use ty::context::TyCtxt;
 use errors::Diagnostic;
 
 /// Indicates the state of a query for a given key in a query map
-pub(super) enum QueryResult<'tcx, T> {
+pub(super) enum QueryResult<'tcx> {
     /// An already executing query. The query job can be used to await for its completion
     Started(Lrc<QueryJob<'tcx>>),
 
-    /// The query is complete and produced `T`
-    Complete(T),
-
     /// The query panicked. Queries trying to wait on this will raise a fatal error / silently panic
     Poisoned,
 }
diff --git a/src/librustc/ty/maps/keys.rs b/src/librustc/ty/maps/keys.rs
index 72f2cb49abc..da29f23589e 100644
--- a/src/librustc/ty/maps/keys.rs
+++ b/src/librustc/ty/maps/keys.rs
@@ -11,7 +11,7 @@
 //! Defines the set of legal keys that can be used in queries.
 
 use hir::def_id::{CrateNum, DefId, LOCAL_CRATE, DefIndex};
-use traits::query::{CanonicalProjectionGoal, CanonicalTyGoal};
+use traits::query::{CanonicalPredicateGoal, CanonicalProjectionGoal, CanonicalTyGoal};
 use ty::{self, Ty, TyCtxt};
 use ty::subst::Substs;
 use ty::fast_reject::SimplifiedType;
@@ -200,3 +200,13 @@ impl<'tcx> Key for CanonicalTyGoal<'tcx> {
         DUMMY_SP
     }
 }
+
+impl<'tcx> Key for CanonicalPredicateGoal<'tcx> {
+    fn map_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+
+    fn default_span(&self, _tcx: TyCtxt) -> Span {
+        DUMMY_SP
+    }
+}
diff --git a/src/librustc/ty/maps/mod.rs b/src/librustc/ty/maps/mod.rs
index f5cb3643de8..d89846a75ef 100644
--- a/src/librustc/ty/maps/mod.rs
+++ b/src/librustc/ty/maps/mod.rs
@@ -9,7 +9,6 @@
 // except according to those terms.
 
 use dep_graph::{DepConstructor, DepNode};
-use errors::DiagnosticBuilder;
 use hir::def_id::{CrateNum, DefId, DefIndex};
 use hir::def::{Def, Export};
 use hir::{self, TraitCandidate, ItemLocalId, TransFnAttrs};
@@ -32,8 +31,9 @@ use mir;
 use mir::interpret::{GlobalId};
 use session::{CompileResult, CrateDisambiguator};
 use session::config::OutputFilenames;
-use traits::Vtable;
-use traits::query::{CanonicalProjectionGoal, CanonicalTyGoal, NoSolution};
+use traits::{self, Vtable};
+use traits::query::{CanonicalPredicateGoal, CanonicalProjectionGoal,
+                    CanonicalTyGoal, NoSolution};
 use traits::query::dropck_outlives::{DtorckConstraint, DropckOutlivesResult};
 use traits::query::normalize::NormalizationResult;
 use traits::specialization_graph;
@@ -42,7 +42,7 @@ use ty::{self, CrateInherentImpls, ParamEnvAnd, Ty, TyCtxt};
 use ty::steal::Steal;
 use ty::subst::Substs;
 use util::nodemap::{DefIdSet, DefIdMap, ItemLocalSet};
-use util::common::{profq_msg, ErrorReported, ProfileQueriesMsg};
+use util::common::{ErrorReported};
 
 use rustc_data_structures::indexed_set::IdxSetBuf;
 use rustc_target::spec::PanicStrategy;
@@ -67,7 +67,6 @@ pub use self::plumbing::force_from_dep_node;
 
 mod job;
 pub use self::job::{QueryJob, QueryInfo};
-use self::job::QueryResult;
 
 mod keys;
 pub use self::keys::Key;
@@ -212,7 +211,7 @@ define_maps! { <'tcx>
 
     /// Borrow checks the function body. If this is a closure, returns
     /// additional requirements that the closure's creator must verify.
-    [] fn mir_borrowck: MirBorrowCheck(DefId) -> Option<mir::ClosureRegionRequirements<'tcx>>,
+    [] fn mir_borrowck: MirBorrowCheck(DefId) -> mir::BorrowCheckResult<'tcx>,
 
     /// Gets a complete map from all types to their inherent impls.
     /// Not meant to be used directly outside of coherence.
@@ -433,6 +432,12 @@ define_maps! { <'tcx>
         NoSolution,
     >,
 
+    /// Do not call this query directly: invoke `infcx.predicate_may_hold()` or
+    /// `infcx.predicate_must_hold()` instead.
+    [] fn evaluate_obligation: EvaluateObligation(
+        CanonicalPredicateGoal<'tcx>
+    ) -> Result<traits::EvaluationResult, traits::OverflowError>,
+
     [] fn substitute_normalize_and_test_predicates:
         substitute_normalize_and_test_predicates_node((DefId, &'tcx Substs<'tcx>)) -> bool,
 
diff --git a/src/librustc/ty/maps/on_disk_cache.rs b/src/librustc/ty/maps/on_disk_cache.rs
index f88e33c708e..cea2a03fd53 100644
--- a/src/librustc/ty/maps/on_disk_cache.rs
+++ b/src/librustc/ty/maps/on_disk_cache.rs
@@ -30,7 +30,6 @@ use syntax::codemap::{CodeMap, StableFilemapId};
 use syntax_pos::{BytePos, Span, DUMMY_SP, FileMap};
 use syntax_pos::hygiene::{Mark, SyntaxContext, ExpnInfo};
 use ty;
-use ty::maps::job::QueryResult;
 use ty::codec::{self as ty_codec, TyDecoder, TyEncoder};
 use ty::context::TyCtxt;
 use util::common::time;
@@ -239,14 +238,12 @@ impl<'sess> OnDiskCache<'sess> {
                 encode_query_results::<specialization_graph_of, _>(tcx, enc, qri)?;
 
                 // const eval is special, it only encodes successfully evaluated constants
-                use ty::maps::plumbing::GetCacheInternal;
-                for (key, entry) in const_eval::get_cache_internal(tcx).map.iter() {
+                use ty::maps::QueryConfig;
+                let map = const_eval::query_map(tcx).borrow();
+                assert!(map.active.is_empty());
+                for (key, entry) in map.results.iter() {
                     use ty::maps::config::QueryDescription;
                     if const_eval::cache_on_disk(key.clone()) {
-                        let entry = match *entry {
-                            QueryResult::Complete(ref v) => v,
-                            _ => panic!("incomplete query"),
-                        };
                         if let Ok(ref value) = entry.value {
                             let dep_node = SerializedDepNodeIndex::new(entry.index.index());
 
@@ -1124,7 +1121,7 @@ fn encode_query_results<'enc, 'a, 'tcx, Q, E>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                               encoder: &mut CacheEncoder<'enc, 'a, 'tcx, E>,
                                               query_result_index: &mut EncodedQueryResultIndex)
                                               -> Result<(), E::Error>
-    where Q: super::plumbing::GetCacheInternal<'tcx>,
+    where Q: super::config::QueryDescription<'tcx>,
           E: 'enc + TyEncoder,
           Q::Value: Encodable,
 {
@@ -1133,12 +1130,10 @@ fn encode_query_results<'enc, 'a, 'tcx, Q, E>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     time(tcx.sess, desc, || {
 
-    for (key, entry) in Q::get_cache_internal(tcx).map.iter() {
+    let map = Q::query_map(tcx).borrow();
+    assert!(map.active.is_empty());
+    for (key, entry) in map.results.iter() {
         if Q::cache_on_disk(key.clone()) {
-            let entry = match *entry {
-                QueryResult::Complete(ref v) => v,
-                _ => panic!("incomplete query"),
-            };
             let dep_node = SerializedDepNodeIndex::new(entry.index.index());
 
             // Record position of the cache entry
diff --git a/src/librustc/ty/maps/plumbing.rs b/src/librustc/ty/maps/plumbing.rs
index 61a4eb58531..37950463f74 100644
--- a/src/librustc/ty/maps/plumbing.rs
+++ b/src/librustc/ty/maps/plumbing.rs
@@ -15,21 +15,29 @@
 use dep_graph::{DepNodeIndex, DepNode, DepKind, DepNodeColor};
 use errors::DiagnosticBuilder;
 use errors::Level;
+use errors::Diagnostic;
+use errors::FatalError;
 use ty::tls;
 use ty::{TyCtxt};
 use ty::maps::Query;
+use ty::maps::config::QueryConfig;
 use ty::maps::config::QueryDescription;
-use ty::maps::job::{QueryResult, QueryInfo};
+use ty::maps::job::{QueryJob, QueryResult, QueryInfo};
 use ty::item_path;
 
+use util::common::{profq_msg, ProfileQueriesMsg, QueryMsg};
+
 use rustc_data_structures::fx::{FxHashMap};
-use rustc_data_structures::sync::LockGuard;
-use std::marker::PhantomData;
+use rustc_data_structures::sync::{Lrc, Lock};
+use std::mem;
+use std::ptr;
+use std::collections::hash_map::Entry;
 use syntax_pos::Span;
+use syntax::codemap::DUMMY_SP;
 
-pub(super) struct QueryMap<'tcx, D: QueryDescription<'tcx>> {
-    phantom: PhantomData<(D, &'tcx ())>,
-    pub(super) map: FxHashMap<D::Key, QueryResult<'tcx, QueryValue<D::Value>>>,
+pub struct QueryMap<'tcx, D: QueryConfig<'tcx> + ?Sized> {
+    pub(super) results: FxHashMap<D::Key, QueryValue<D::Value>>,
+    pub(super) active: FxHashMap<D::Key, QueryResult<'tcx>>,
 }
 
 pub(super) struct QueryValue<T> {
@@ -48,18 +56,166 @@ impl<T> QueryValue<T> {
     }
 }
 
-impl<'tcx, M: QueryDescription<'tcx>> QueryMap<'tcx, M> {
+impl<'tcx, M: QueryConfig<'tcx>> QueryMap<'tcx, M> {
     pub(super) fn new() -> QueryMap<'tcx, M> {
         QueryMap {
-            phantom: PhantomData,
-            map: FxHashMap(),
+            results: FxHashMap(),
+            active: FxHashMap(),
+        }
+    }
+}
+
+// If enabled, send a message to the profile-queries thread
+macro_rules! profq_msg {
+    ($tcx:expr, $msg:expr) => {
+        if cfg!(debug_assertions) {
+            if $tcx.sess.profile_queries() {
+                profq_msg($tcx.sess, $msg)
+            }
+        }
+    }
+}
+
+// If enabled, format a key using its debug string, which can be
+// expensive to compute (in terms of time).
+macro_rules! profq_query_msg {
+    ($query:expr, $tcx:expr, $key:expr) => {{
+        let msg = if cfg!(debug_assertions) {
+            if $tcx.sess.profile_queries_and_keys() {
+                Some(format!("{:?}", $key))
+            } else { None }
+        } else { None };
+        QueryMsg {
+            query: $query,
+            msg,
+        }
+    }}
+}
+
+/// A type representing the responsibility to execute the job in the `job` field.
+/// This will poison the relevant query if dropped.
+pub(super) struct JobOwner<'a, 'tcx: 'a, Q: QueryDescription<'tcx> + 'a> {
+    map: &'a Lock<QueryMap<'tcx, Q>>,
+    key: Q::Key,
+    job: Lrc<QueryJob<'tcx>>,
+}
+
+impl<'a, 'tcx, Q: QueryDescription<'tcx>> JobOwner<'a, 'tcx, Q> {
+    /// Either gets a JobOwner corresponding the the query, allowing us to
+    /// start executing the query, or it returns with the result of the query.
+    /// If the query is executing elsewhere, this will wait for it.
+    /// If the query panicked, this will silently panic.
+    pub(super) fn try_get(
+        tcx: TyCtxt<'a, 'tcx, '_>,
+        span: Span,
+        key: &Q::Key,
+    ) -> TryGetJob<'a, 'tcx, Q> {
+        let map = Q::query_map(tcx);
+        loop {
+            let mut lock = map.borrow_mut();
+            if let Some(value) = lock.results.get(key) {
+                profq_msg!(tcx, ProfileQueriesMsg::CacheHit);
+                let result = Ok((value.value.clone(), value.index));
+                return TryGetJob::JobCompleted(result);
+            }
+            let job = match lock.active.entry((*key).clone()) {
+                Entry::Occupied(entry) => {
+                    match *entry.get() {
+                        QueryResult::Started(ref job) => job.clone(),
+                        QueryResult::Poisoned => FatalError.raise(),
+                    }
+                }
+                Entry::Vacant(entry) => {
+                    // No job entry for this query. Return a new one to be started later
+                    return tls::with_related_context(tcx, |icx| {
+                        let info = QueryInfo {
+                            span,
+                            query: Q::query(key.clone()),
+                        };
+                        let job = Lrc::new(QueryJob::new(info, icx.query.clone()));
+                        let owner = JobOwner {
+                            map,
+                            job: job.clone(),
+                            key: (*key).clone(),
+                        };
+                        entry.insert(QueryResult::Started(job));
+                        TryGetJob::NotYetStarted(owner)
+                    })
+                }
+            };
+            mem::drop(lock);
+
+            if let Err(cycle) = job.await(tcx, span) {
+                return TryGetJob::JobCompleted(Err(cycle));
+            }
+        }
+    }
+
+    /// Completes the query by updating the query map with the `result`,
+    /// signals the waiter and forgets the JobOwner, so it won't poison the query
+    pub(super) fn complete(self, result: &Q::Value, dep_node_index: DepNodeIndex) {
+        // We can move out of `self` here because we `mem::forget` it below
+        let key = unsafe { ptr::read(&self.key) };
+        let job = unsafe { ptr::read(&self.job) };
+        let map = self.map;
+
+        // Forget ourself so our destructor won't poison the query
+        mem::forget(self);
+
+        let value = QueryValue::new(result.clone(), dep_node_index);
+        {
+            let mut lock = map.borrow_mut();
+            lock.active.remove(&key);
+            lock.results.insert(key, value);
         }
+
+        job.signal_complete();
+    }
+
+    /// Executes a job by changing the ImplicitCtxt to point to the
+    /// new query job while it executes. It returns the diagnostics
+    /// captured during execution and the actual result.
+    pub(super) fn start<'lcx, F, R>(
+        &self,
+        tcx: TyCtxt<'_, 'tcx, 'lcx>,
+        compute: F)
+    -> (R, Vec<Diagnostic>)
+    where
+        F: for<'b> FnOnce(TyCtxt<'b, 'tcx, 'lcx>) -> R
+    {
+        // The TyCtxt stored in TLS has the same global interner lifetime
+        // as `tcx`, so we use `with_related_context` to relate the 'gcx lifetimes
+        // when accessing the ImplicitCtxt
+        let r = tls::with_related_context(tcx, move |current_icx| {
+            // Update the ImplicitCtxt to point to our new query job
+            let new_icx = tls::ImplicitCtxt {
+                tcx,
+                query: Some(self.job.clone()),
+                layout_depth: current_icx.layout_depth,
+                task: current_icx.task,
+            };
+
+            // Use the ImplicitCtxt while we execute the query
+            tls::enter_context(&new_icx, |_| {
+                compute(tcx)
+            })
+        });
+
+        // Extract the diagnostic from the job
+        let diagnostics = mem::replace(&mut *self.job.diagnostics.lock(), Vec::new());
+
+        (r, diagnostics)
     }
 }
 
-pub(super) trait GetCacheInternal<'tcx>: QueryDescription<'tcx> + Sized {
-    fn get_cache_internal<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>)
-                              -> LockGuard<'a, QueryMap<'tcx, Self>>;
+impl<'a, 'tcx, Q: QueryDescription<'tcx>> Drop for JobOwner<'a, 'tcx, Q> {
+    fn drop(&mut self) {
+        // Poison the query so jobs waiting on it panic
+        self.map.borrow_mut().active.insert(self.key.clone(), QueryResult::Poisoned);
+        // Also signal the completion of the job, so waiters
+        // will continue execution
+        self.job.signal_complete();
+    }
 }
 
 #[derive(Clone)]
@@ -70,14 +226,14 @@ pub(super) struct CycleError<'tcx> {
 }
 
 /// The result of `try_get_lock`
-pub(super) enum TryGetLock<'a, 'tcx: 'a, T, D: QueryDescription<'tcx> + 'a> {
+pub(super) enum TryGetJob<'a, 'tcx: 'a, D: QueryDescription<'tcx> + 'a> {
     /// The query is not yet started. Contains a guard to the map eventually used to start it.
-    NotYetStarted(LockGuard<'a, QueryMap<'tcx, D>>),
+    NotYetStarted(JobOwner<'a, 'tcx, D>),
 
     /// The query was already completed.
     /// Returns the result of the query and its dep node index
     /// if it succeeded or a cycle error if it failed
-    JobCompleted(Result<(T, DepNodeIndex), CycleError<'tcx>>),
+    JobCompleted(Result<(D::Value, DepNodeIndex), CycleError<'tcx>>),
 }
 
 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
@@ -180,28 +336,277 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             }
         }
     }
-}
 
-// If enabled, send a message to the profile-queries thread
-macro_rules! profq_msg {
-    ($tcx:expr, $msg:expr) => {
-        if cfg!(debug_assertions) {
-            if $tcx.sess.profile_queries() {
-                profq_msg($tcx.sess, $msg)
+    fn try_get_with<Q: QueryDescription<'gcx>>(
+        self,
+        span: Span,
+        key: Q::Key)
+    -> Result<Q::Value, CycleError<'gcx>>
+    {
+        debug!("ty::queries::{}::try_get_with(key={:?}, span={:?})",
+               Q::NAME,
+               key,
+               span);
+
+        profq_msg!(self,
+            ProfileQueriesMsg::QueryBegin(
+                span.data(),
+                profq_query_msg!(Q::NAME, self, key),
+            )
+        );
+
+        let job = match JobOwner::try_get(self, span, &key) {
+            TryGetJob::NotYetStarted(job) => job,
+            TryGetJob::JobCompleted(result) => {
+                return result.map(|(v, index)| {
+                    self.dep_graph.read_index(index);
+                    v
+                })
             }
+        };
+
+        // Fast path for when incr. comp. is off. `to_dep_node` is
+        // expensive for some DepKinds.
+        if !self.dep_graph.is_fully_enabled() {
+            let null_dep_node = DepNode::new_no_params(::dep_graph::DepKind::Null);
+            return self.force_query_with_job::<Q>(key, job, null_dep_node).map(|(v, _)| v);
+        }
+
+        let dep_node = Q::to_dep_node(self, &key);
+
+        if dep_node.kind.is_anon() {
+            profq_msg!(self, ProfileQueriesMsg::ProviderBegin);
+
+            let res = job.start(self, |tcx| {
+                tcx.dep_graph.with_anon_task(dep_node.kind, || {
+                    Q::compute(tcx.global_tcx(), key)
+                })
+            });
+
+            profq_msg!(self, ProfileQueriesMsg::ProviderEnd);
+            let ((result, dep_node_index), diagnostics) = res;
+
+            self.dep_graph.read_index(dep_node_index);
+
+            self.on_disk_query_result_cache
+                .store_diagnostics_for_anon_node(dep_node_index, diagnostics);
+
+            job.complete(&result, dep_node_index);
+
+            return Ok(result);
+        }
+
+        if !dep_node.kind.is_input() {
+            if let Some(dep_node_index) = self.try_mark_green_and_read(&dep_node) {
+                profq_msg!(self, ProfileQueriesMsg::CacheHit);
+                return self.load_from_disk_and_cache_in_memory::<Q>(key,
+                                                                    job,
+                                                                    dep_node_index,
+                                                                    &dep_node)
+            }
+        }
+
+        match self.force_query_with_job::<Q>(key, job, dep_node) {
+            Ok((result, dep_node_index)) => {
+                self.dep_graph.read_index(dep_node_index);
+                Ok(result)
+            }
+            Err(e) => Err(e)
         }
     }
-}
 
-// If enabled, format a key using its debug string, which can be
-// expensive to compute (in terms of time).
-macro_rules! profq_key {
-    ($tcx:expr, $key:expr) => {
-        if cfg!(debug_assertions) {
-            if $tcx.sess.profile_queries_and_keys() {
-                Some(format!("{:?}", $key))
-            } else { None }
-        } else { None }
+    fn load_from_disk_and_cache_in_memory<Q: QueryDescription<'gcx>>(
+        self,
+        key: Q::Key,
+        job: JobOwner<'a, 'gcx, Q>,
+        dep_node_index: DepNodeIndex,
+        dep_node: &DepNode
+    ) -> Result<Q::Value, CycleError<'gcx>>
+    {
+        // Note this function can be called concurrently from the same query
+        // We must ensure that this is handled correctly
+
+        debug_assert!(self.dep_graph.is_green(dep_node));
+
+        // First we try to load the result from the on-disk cache
+        let result = if Q::cache_on_disk(key.clone()) &&
+                        self.sess.opts.debugging_opts.incremental_queries {
+            let prev_dep_node_index =
+                self.dep_graph.prev_dep_node_index_of(dep_node);
+            let result = Q::try_load_from_disk(self.global_tcx(),
+                                                    prev_dep_node_index);
+
+            // We always expect to find a cached result for things that
+            // can be forced from DepNode.
+            debug_assert!(!dep_node.kind.can_reconstruct_query_key() ||
+                            result.is_some(),
+                            "Missing on-disk cache entry for {:?}",
+                            dep_node);
+            result
+        } else {
+            // Some things are never cached on disk.
+            None
+        };
+
+        let result = if let Some(result) = result {
+            result
+        } else {
+            // We could not load a result from the on-disk cache, so
+            // recompute.
+
+            // The diagnostics for this query have already been
+            // promoted to the current session during
+            // try_mark_green(), so we can ignore them here.
+            let (result, _) = job.start(self, |tcx| {
+                // The dep-graph for this computation is already in
+                // place
+                tcx.dep_graph.with_ignore(|| {
+                    Q::compute(tcx, key)
+                })
+            });
+            result
+        };
+
+        // If -Zincremental-verify-ich is specified, re-hash results from
+        // the cache and make sure that they have the expected fingerprint.
+        if self.sess.opts.debugging_opts.incremental_verify_ich {
+            use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
+            use ich::Fingerprint;
+
+            assert!(Some(self.dep_graph.fingerprint_of(dep_node_index)) ==
+                    self.dep_graph.prev_fingerprint_of(dep_node),
+                    "Fingerprint for green query instance not loaded \
+                        from cache: {:?}", dep_node);
+
+            debug!("BEGIN verify_ich({:?})", dep_node);
+            let mut hcx = self.create_stable_hashing_context();
+            let mut hasher = StableHasher::new();
+
+            result.hash_stable(&mut hcx, &mut hasher);
+
+            let new_hash: Fingerprint = hasher.finish();
+            debug!("END verify_ich({:?})", dep_node);
+
+            let old_hash = self.dep_graph.fingerprint_of(dep_node_index);
+
+            assert!(new_hash == old_hash, "Found unstable fingerprints \
+                for {:?}", dep_node);
+        }
+
+        if self.sess.opts.debugging_opts.query_dep_graph {
+            self.dep_graph.mark_loaded_from_cache(dep_node_index, true);
+        }
+
+        job.complete(&result, dep_node_index);
+
+        Ok(result)
+    }
+
+    fn force_query_with_job<Q: QueryDescription<'gcx>>(
+        self,
+        key: Q::Key,
+        job: JobOwner<'_, 'gcx, Q>,
+        dep_node: DepNode)
+    -> Result<(Q::Value, DepNodeIndex), CycleError<'gcx>> {
+        // If the following assertion triggers, it can have two reasons:
+        // 1. Something is wrong with DepNode creation, either here or
+        //    in DepGraph::try_mark_green()
+        // 2. Two distinct query keys get mapped to the same DepNode
+        //    (see for example #48923)
+        assert!(!self.dep_graph.dep_node_exists(&dep_node),
+                "Forcing query with already existing DepNode.\n\
+                    - query-key: {:?}\n\
+                    - dep-node: {:?}",
+                key, dep_node);
+
+        profq_msg!(self, ProfileQueriesMsg::ProviderBegin);
+        let res = job.start(self, |tcx| {
+            if dep_node.kind.is_eval_always() {
+                tcx.dep_graph.with_eval_always_task(dep_node,
+                                                    tcx,
+                                                    key,
+                                                    Q::compute)
+            } else {
+                tcx.dep_graph.with_task(dep_node,
+                                        tcx,
+                                        key,
+                                        Q::compute)
+            }
+        });
+        profq_msg!(self, ProfileQueriesMsg::ProviderEnd);
+
+        let ((result, dep_node_index), diagnostics) = res;
+
+        if self.sess.opts.debugging_opts.query_dep_graph {
+            self.dep_graph.mark_loaded_from_cache(dep_node_index, false);
+        }
+
+        if dep_node.kind != ::dep_graph::DepKind::Null {
+            self.on_disk_query_result_cache
+                .store_diagnostics(dep_node_index, diagnostics);
+        }
+
+        job.complete(&result, dep_node_index);
+
+        Ok((result, dep_node_index))
+    }
+
+    /// Ensure that either this query has all green inputs or been executed.
+    /// Executing query::ensure(D) is considered a read of the dep-node D.
+    ///
+    /// This function is particularly useful when executing passes for their
+    /// side-effects -- e.g., in order to report errors for erroneous programs.
+    ///
+    /// Note: The optimization is only available during incr. comp.
+    pub fn ensure_query<Q: QueryDescription<'gcx>>(self, key: Q::Key) -> () {
+        let dep_node = Q::to_dep_node(self, &key);
+
+        // Ensuring an "input" or anonymous query makes no sense
+        assert!(!dep_node.kind.is_anon());
+        assert!(!dep_node.kind.is_input());
+        if self.try_mark_green_and_read(&dep_node).is_none() {
+            // A None return from `try_mark_green_and_read` means that this is either
+            // a new dep node or that the dep node has already been marked red.
+            // Either way, we can't call `dep_graph.read()` as we don't have the
+            // DepNodeIndex. We must invoke the query itself. The performance cost
+            // this introduces should be negligible as we'll immediately hit the
+            // in-memory cache, or another query down the line will.
+            let _ = self.get_query::<Q>(DUMMY_SP, key);
+        }
+    }
+
+    #[allow(dead_code)]
+    fn force_query<Q: QueryDescription<'gcx>>(
+        self,
+        key: Q::Key,
+        span: Span,
+        dep_node: DepNode
+    ) -> Result<(Q::Value, DepNodeIndex), CycleError<'gcx>> {
+        // We may be concurrently trying both execute and force a query
+        // Ensure that only one of them runs the query
+        let job = match JobOwner::try_get(self, span, &key) {
+            TryGetJob::NotYetStarted(job) => job,
+            TryGetJob::JobCompleted(result) => return result,
+        };
+        self.force_query_with_job::<Q>(key, job, dep_node)
+    }
+
+    pub fn try_get_query<Q: QueryDescription<'gcx>>(
+        self,
+        span: Span,
+        key: Q::Key
+    ) -> Result<Q::Value, DiagnosticBuilder<'a>> {
+        match self.try_get_with::<Q>(span, key) {
+            Ok(e) => Ok(e),
+            Err(e) => Err(self.report_cycle(e)),
+        }
+    }
+
+    pub fn get_query<Q: QueryDescription<'gcx>>(self, span: Span, key: Q::Key) -> Q::Value {
+        self.try_get_query::<Q>(span, key).unwrap_or_else(|mut e| {
+            e.emit();
+            Q::handle_cycle_error(self)
+        })
     }
 }
 
@@ -210,7 +615,7 @@ macro_rules! handle_cycle_error {
         Value::from_cycle_error($this.global_tcx())
     }};
     ([fatal_cycle$(, $modifiers:ident)*][$this:expr]) => {{
-        $this.tcx.sess.abort_if_errors();
+        $this.sess.abort_if_errors();
         unreachable!();
     }};
     ([$other:ident$(, $modifiers:ident)*][$($args:tt)*]) => {
@@ -223,12 +628,7 @@ macro_rules! define_maps {
      $($(#[$attr:meta])*
        [$($modifiers:tt)*] fn $name:ident: $node:ident($K:ty) -> $V:ty,)*) => {
 
-        use dep_graph::DepNodeIndex;
-        use std::mem;
-        use errors::Diagnostic;
-        use errors::FatalError;
-        use rustc_data_structures::sync::{Lock, LockGuard};
-        use rustc_data_structures::OnDrop;
+        use rustc_data_structures::sync::Lock;
 
         define_map_struct! {
             tcx: $tcx,
@@ -251,12 +651,6 @@ macro_rules! define_maps {
             $($(#[$attr])* $name($K)),*
         }
 
-        #[allow(bad_style)]
-        #[derive(Clone, Debug, PartialEq, Eq)]
-        pub enum QueryMsg {
-            $($name(Option<String>)),*
-        }
-
         impl<$tcx> Query<$tcx> {
             pub fn name(&self) -> &'static str {
                 match *self {
@@ -303,162 +697,38 @@ macro_rules! define_maps {
             })*
         }
 
-        $(impl<$tcx> QueryConfig for queries::$name<$tcx> {
+        $(impl<$tcx> QueryConfig<$tcx> for queries::$name<$tcx> {
             type Key = $K;
             type Value = $V;
-        }
 
-        impl<$tcx> GetCacheInternal<$tcx> for queries::$name<$tcx> {
-            fn get_cache_internal<'a>(tcx: TyCtxt<'a, $tcx, $tcx>)
-                                      -> LockGuard<'a, QueryMap<$tcx, Self>> {
-                tcx.maps.$name.borrow()
+            const NAME: &'static str = stringify!($name);
+
+            fn query(key: Self::Key) -> Query<'tcx> {
+                Query::$name(key)
             }
-        }
 
-        impl<'a, $tcx, 'lcx> queries::$name<$tcx> {
+            fn query_map<'a>(tcx: TyCtxt<'a, $tcx, '_>) -> &'a Lock<QueryMap<$tcx, Self>> {
+                &tcx.maps.$name
+            }
 
             #[allow(unused)]
-            fn to_dep_node(tcx: TyCtxt<'a, $tcx, 'lcx>, key: &$K) -> DepNode {
+            fn to_dep_node(tcx: TyCtxt<'_, $tcx, '_>, key: &Self::Key) -> DepNode {
                 use dep_graph::DepConstructor::*;
 
                 DepNode::new(tcx, $node(*key))
             }
 
-            /// Either get the lock of the query map, allowing us to
-            /// start executing the query, or it returns with the result of the query.
-            /// If the query already executed and panicked, this will fatal error / silently panic
-            fn try_get_lock(
-                tcx: TyCtxt<'a, $tcx, 'lcx>,
-                span: Span,
-                key: &$K
-            ) -> TryGetLock<'a, $tcx, $V, Self>
-            {
-                loop {
-                    let lock = tcx.maps.$name.borrow_mut();
-                    let job = if let Some(value) = lock.map.get(key) {
-                        match *value {
-                            QueryResult::Started(ref job) => Some(job.clone()),
-                            QueryResult::Complete(ref value) => {
-                                profq_msg!(tcx, ProfileQueriesMsg::CacheHit);
-                                let result = Ok(((&value.value).clone(), value.index));
-                                return TryGetLock::JobCompleted(result);
-                            },
-                            QueryResult::Poisoned => FatalError.raise(),
-                        }
-                    } else {
-                        None
-                    };
-                    let job = if let Some(job) = job {
-                        job
-                    } else {
-                        return TryGetLock::NotYetStarted(lock);
-                    };
-                    mem::drop(lock);
-
-                    if let Err(cycle) = job.await(tcx, span) {
-                        return TryGetLock::JobCompleted(Err(cycle));
-                    }
-                }
+            fn compute(tcx: TyCtxt<'_, 'tcx, '_>, key: Self::Key) -> Self::Value {
+                let provider = tcx.maps.providers[key.map_crate()].$name;
+                provider(tcx.global_tcx(), key)
             }
 
-            fn try_get_with(tcx: TyCtxt<'a, $tcx, 'lcx>,
-                            span: Span,
-                            key: $K)
-                            -> Result<$V, CycleError<$tcx>>
-            {
-                debug!("ty::queries::{}::try_get_with(key={:?}, span={:?})",
-                       stringify!($name),
-                       key,
-                       span);
-
-                profq_msg!(tcx,
-                    ProfileQueriesMsg::QueryBegin(
-                        span.data(),
-                        QueryMsg::$name(profq_key!(tcx, key))
-                    )
-                );
-
-                /// Get the lock used to start the query or
-                /// return the result of the completed query
-                macro_rules! get_lock_or_return {
-                    () => {{
-                        match Self::try_get_lock(tcx, span, &key) {
-                            TryGetLock::NotYetStarted(lock) => lock,
-                            TryGetLock::JobCompleted(result) => {
-                                return result.map(|(v, index)| {
-                                    tcx.dep_graph.read_index(index);
-                                    v
-                                })
-                            }
-                        }
-                    }}
-                }
-
-                let mut lock = get_lock_or_return!();
-
-                // Fast path for when incr. comp. is off. `to_dep_node` is
-                // expensive for some DepKinds.
-                if !tcx.dep_graph.is_fully_enabled() {
-                    let null_dep_node = DepNode::new_no_params(::dep_graph::DepKind::Null);
-                    return Self::force_with_lock(tcx, key, span, lock, null_dep_node)
-                                .map(|(v, _)| v);
-                }
-
-                let dep_node = Self::to_dep_node(tcx, &key);
-
-                if dep_node.kind.is_anon() {
-                    profq_msg!(tcx, ProfileQueriesMsg::ProviderBegin);
-
-                    let res = Self::start_job(tcx, span, key, lock, |tcx| {
-                        tcx.dep_graph.with_anon_task(dep_node.kind, || {
-                            Self::compute_result(tcx.global_tcx(), key)
-                        })
-                    })?;
-
-                    profq_msg!(tcx, ProfileQueriesMsg::ProviderEnd);
-                    let (((result, dep_node_index), diagnostics), job) = res;
-
-                    tcx.dep_graph.read_index(dep_node_index);
-
-                    tcx.on_disk_query_result_cache
-                       .store_diagnostics_for_anon_node(dep_node_index, diagnostics);
-
-                    let value = QueryValue::new(Clone::clone(&result), dep_node_index);
-
-                    tcx.maps
-                       .$name
-                       .borrow_mut()
-                       .map
-                       .insert(key, QueryResult::Complete(value));
-
-                    job.signal_complete();
-
-                    return Ok(result);
-                }
-
-                if !dep_node.kind.is_input() {
-                    // try_mark_green_and_read may force queries. So we must drop our lock here
-                    mem::drop(lock);
-                    if let Some(dep_node_index) = tcx.try_mark_green_and_read(&dep_node) {
-                        profq_msg!(tcx, ProfileQueriesMsg::CacheHit);
-                        return Self::load_from_disk_and_cache_in_memory(tcx,
-                                                                        key,
-                                                                        span,
-                                                                        dep_node_index,
-                                                                        &dep_node)
-                    }
-                    lock = get_lock_or_return!();
-                }
-
-                match Self::force_with_lock(tcx, key, span, lock, dep_node) {
-                    Ok((result, dep_node_index)) => {
-                        tcx.dep_graph.read_index(dep_node_index);
-                        Ok(result)
-                    }
-                    Err(e) => Err(e)
-                }
+            fn handle_cycle_error(tcx: TyCtxt<'_, 'tcx, '_>) -> Self::Value {
+                handle_cycle_error!([$($modifiers)*][tcx])
             }
+        }
 
+        impl<'a, $tcx, 'lcx> queries::$name<$tcx> {
             /// Ensure that either this query has all green inputs or been executed.
             /// Executing query::ensure(D) is considered a read of the dep-node D.
             ///
@@ -467,282 +737,7 @@ macro_rules! define_maps {
             ///
             /// Note: The optimization is only available during incr. comp.
             pub fn ensure(tcx: TyCtxt<'a, $tcx, 'lcx>, key: $K) -> () {
-                let dep_node = Self::to_dep_node(tcx, &key);
-
-                // Ensuring an "input" or anonymous query makes no sense
-                assert!(!dep_node.kind.is_anon());
-                assert!(!dep_node.kind.is_input());
-                if tcx.try_mark_green_and_read(&dep_node).is_none() {
-                    // A None return from `try_mark_green_and_read` means that this is either
-                    // a new dep node or that the dep node has already been marked red.
-                    // Either way, we can't call `dep_graph.read()` as we don't have the
-                    // DepNodeIndex. We must invoke the query itself. The performance cost
-                    // this introduces should be negligible as we'll immediately hit the
-                    // in-memory cache, or another query down the line will.
-                    let _ = tcx.$name(key);
-                }
-            }
-
-            /// Creates a job for the query and updates the query map indicating that it started.
-            /// Then it changes ImplicitCtxt to point to the new query job while it executes.
-            /// If the query panics, this updates the query map to indicate so.
-            fn start_job<F, R>(tcx: TyCtxt<'_, $tcx, 'lcx>,
-                               span: Span,
-                               key: $K,
-                               mut map: LockGuard<'_, QueryMap<$tcx, Self>>,
-                               compute: F)
-                -> Result<((R, Vec<Diagnostic>), Lrc<QueryJob<$tcx>>), CycleError<$tcx>>
-                where F: for<'b> FnOnce(TyCtxt<'b, $tcx, 'lcx>) -> R
-            {
-                let query = Query::$name(Clone::clone(&key));
-
-                let entry = QueryInfo {
-                    span,
-                    query,
-                };
-
-                // The TyCtxt stored in TLS has the same global interner lifetime
-                // as `tcx`, so we use `with_related_context` to relate the 'gcx lifetimes
-                // when accessing the ImplicitCtxt
-                let (r, job) = ty::tls::with_related_context(tcx, move |icx| {
-                    let job = Lrc::new(QueryJob::new(entry, icx.query.clone()));
-
-                    // Store the job in the query map and drop the lock to allow
-                    // others to wait it
-                    map.map.entry(key).or_insert(QueryResult::Started(job.clone()));
-                    mem::drop(map);
-
-                    let r = {
-                        let on_drop = OnDrop(|| {
-                            // Poison the query so jobs waiting on it panic
-                            tcx.maps
-                            .$name
-                            .borrow_mut()
-                            .map
-                            .insert(key, QueryResult::Poisoned);
-                            // Also signal the completion of the job, so waiters
-                            // will continue execution
-                            job.signal_complete();
-                        });
-
-                        // Update the ImplicitCtxt to point to our new query job
-                        let icx = ty::tls::ImplicitCtxt {
-                            tcx,
-                            query: Some(job.clone()),
-                            layout_depth: icx.layout_depth,
-                            task: icx.task,
-                        };
-
-                        // Use the ImplicitCtxt while we execute the query
-                        let r = ty::tls::enter_context(&icx, |icx| {
-                            compute(icx.tcx)
-                        });
-
-                        mem::forget(on_drop);
-
-                        r
-                    };
-
-                    (r, job)
-                });
-
-                // Extract the diagnostic from the job
-                let diagnostics: Vec<_> = mem::replace(&mut *job.diagnostics.lock(), Vec::new());
-
-                Ok(((r, diagnostics), job))
-            }
-
-            fn compute_result(tcx: TyCtxt<'a, $tcx, 'lcx>, key: $K) -> $V {
-                let provider = tcx.maps.providers[key.map_crate()].$name;
-                provider(tcx.global_tcx(), key)
-            }
-
-            fn load_from_disk_and_cache_in_memory(tcx: TyCtxt<'a, $tcx, 'lcx>,
-                                                  key: $K,
-                                                  span: Span,
-                                                  dep_node_index: DepNodeIndex,
-                                                  dep_node: &DepNode)
-                                                  -> Result<$V, CycleError<$tcx>>
-            {
-                // Note this function can be called concurrently from the same query
-                // We must ensure that this is handled correctly
-
-                debug_assert!(tcx.dep_graph.is_green(dep_node));
-
-                // First we try to load the result from the on-disk cache
-                let result = if Self::cache_on_disk(key) &&
-                                tcx.sess.opts.debugging_opts.incremental_queries {
-                    let prev_dep_node_index =
-                        tcx.dep_graph.prev_dep_node_index_of(dep_node);
-                    let result = Self::try_load_from_disk(tcx.global_tcx(),
-                                                          prev_dep_node_index);
-
-                    // We always expect to find a cached result for things that
-                    // can be forced from DepNode.
-                    debug_assert!(!dep_node.kind.can_reconstruct_query_key() ||
-                                  result.is_some(),
-                                  "Missing on-disk cache entry for {:?}",
-                                  dep_node);
-                    result
-                } else {
-                    // Some things are never cached on disk.
-                    None
-                };
-
-                let (result, job) = if let Some(result) = result {
-                    (result, None)
-                } else {
-                    // We could not load a result from the on-disk cache, so
-                    // recompute.
-
-                    // The diagnostics for this query have already been
-                    // promoted to the current session during
-                    // try_mark_green(), so we can ignore them here.
-                    let ((result, _), job) = Self::start_job(tcx,
-                                                             span,
-                                                             key,
-                                                             tcx.maps.$name.borrow_mut(),
-                                                             |tcx| {
-                        // The dep-graph for this computation is already in
-                        // place
-                        tcx.dep_graph.with_ignore(|| {
-                            Self::compute_result(tcx, key)
-                        })
-                    })?;
-                    (result, Some(job))
-                };
-
-                // If -Zincremental-verify-ich is specified, re-hash results from
-                // the cache and make sure that they have the expected fingerprint.
-                if tcx.sess.opts.debugging_opts.incremental_verify_ich {
-                    use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
-                    use ich::Fingerprint;
-
-                    assert!(Some(tcx.dep_graph.fingerprint_of(dep_node_index)) ==
-                            tcx.dep_graph.prev_fingerprint_of(dep_node),
-                            "Fingerprint for green query instance not loaded \
-                             from cache: {:?}", dep_node);
-
-                    debug!("BEGIN verify_ich({:?})", dep_node);
-                    let mut hcx = tcx.create_stable_hashing_context();
-                    let mut hasher = StableHasher::new();
-
-                    result.hash_stable(&mut hcx, &mut hasher);
-
-                    let new_hash: Fingerprint = hasher.finish();
-                    debug!("END verify_ich({:?})", dep_node);
-
-                    let old_hash = tcx.dep_graph.fingerprint_of(dep_node_index);
-
-                    assert!(new_hash == old_hash, "Found unstable fingerprints \
-                        for {:?}", dep_node);
-                }
-
-                if tcx.sess.opts.debugging_opts.query_dep_graph {
-                    tcx.dep_graph.mark_loaded_from_cache(dep_node_index, true);
-                }
-
-                let value = QueryValue::new(Clone::clone(&result), dep_node_index);
-
-                tcx.maps
-                   .$name
-                   .borrow_mut()
-                   .map
-                   .insert(key, QueryResult::Complete(value));
-
-                job.map(|j| j.signal_complete());
-
-                Ok(result)
-            }
-
-            #[allow(dead_code)]
-            fn force(tcx: TyCtxt<'a, $tcx, 'lcx>,
-                     key: $K,
-                     span: Span,
-                     dep_node: DepNode)
-                     -> Result<($V, DepNodeIndex), CycleError<$tcx>> {
-                // We may be concurrently trying both execute and force a query
-                // Ensure that only one of them runs the query
-                let lock = match Self::try_get_lock(tcx, span, &key) {
-                    TryGetLock::NotYetStarted(lock) => lock,
-                    TryGetLock::JobCompleted(result) => return result,
-                };
-                Self::force_with_lock(tcx,
-                                      key,
-                                      span,
-                                      lock,
-                                      dep_node)
-            }
-
-            fn force_with_lock(tcx: TyCtxt<'a, $tcx, 'lcx>,
-                               key: $K,
-                               span: Span,
-                               map: LockGuard<'_, QueryMap<$tcx, Self>>,
-                               dep_node: DepNode)
-                               -> Result<($V, DepNodeIndex), CycleError<$tcx>> {
-                // If the following assertion triggers, it can have two reasons:
-                // 1. Something is wrong with DepNode creation, either here or
-                //    in DepGraph::try_mark_green()
-                // 2. Two distinct query keys get mapped to the same DepNode
-                //    (see for example #48923)
-                assert!(!tcx.dep_graph.dep_node_exists(&dep_node),
-                        "Forcing query with already existing DepNode.\n\
-                          - query-key: {:?}\n\
-                          - dep-node: {:?}",
-                        key, dep_node);
-
-                profq_msg!(tcx, ProfileQueriesMsg::ProviderBegin);
-                let res = Self::start_job(tcx,
-                                          span,
-                                          key,
-                                          map,
-                                          |tcx| {
-                    if dep_node.kind.is_eval_always() {
-                        tcx.dep_graph.with_eval_always_task(dep_node,
-                                                            tcx,
-                                                            key,
-                                                            Self::compute_result)
-                    } else {
-                        tcx.dep_graph.with_task(dep_node,
-                                                tcx,
-                                                key,
-                                                Self::compute_result)
-                    }
-                })?;
-                profq_msg!(tcx, ProfileQueriesMsg::ProviderEnd);
-
-                let (((result, dep_node_index), diagnostics), job) = res;
-
-                if tcx.sess.opts.debugging_opts.query_dep_graph {
-                    tcx.dep_graph.mark_loaded_from_cache(dep_node_index, false);
-                }
-
-                if dep_node.kind != ::dep_graph::DepKind::Null {
-                    tcx.on_disk_query_result_cache
-                       .store_diagnostics(dep_node_index, diagnostics);
-                }
-
-                let value = QueryValue::new(Clone::clone(&result), dep_node_index);
-
-                tcx.maps
-                   .$name
-                   .borrow_mut()
-                   .map
-                   .insert(key, QueryResult::Complete(value));
-
-                let job: Lrc<QueryJob> = job;
-
-                job.signal_complete();
-
-                Ok((result, dep_node_index))
-            }
-
-            pub fn try_get(tcx: TyCtxt<'a, $tcx, 'lcx>, span: Span, key: $K)
-                           -> Result<$V, DiagnosticBuilder<'a>> {
-                match Self::try_get_with(tcx, span, key) {
-                    Ok(e) => Ok(e),
-                    Err(e) => Err(tcx.report_cycle(e)),
-                }
+                tcx.ensure_query::<queries::$name>(key);
             }
         })*
 
@@ -778,10 +773,7 @@ macro_rules! define_maps {
         impl<'a, $tcx, 'lcx> TyCtxtAt<'a, $tcx, 'lcx> {
             $($(#[$attr])*
             pub fn $name(self, key: $K) -> $V {
-                queries::$name::try_get(self.tcx, self.span, key).unwrap_or_else(|mut e| {
-                    e.emit();
-                    handle_cycle_error!([$($modifiers)*][self])
-                })
+                self.tcx.get_query::<queries::$name>(self.span, key)
             })*
         }
 
@@ -872,7 +864,6 @@ macro_rules! define_provider_struct {
 pub fn force_from_dep_node<'a, 'gcx, 'lcx>(tcx: TyCtxt<'a, 'gcx, 'lcx>,
                                            dep_node: &DepNode)
                                            -> bool {
-    use ty::maps::keys::Key;
     use hir::def_id::LOCAL_CRATE;
 
     // We must avoid ever having to call force_from_dep_node() for a
@@ -915,23 +906,14 @@ pub fn force_from_dep_node<'a, 'gcx, 'lcx>(tcx: TyCtxt<'a, 'gcx, 'lcx>,
             {
                 use $crate::util::common::{ProfileQueriesMsg, profq_msg};
 
-                // FIXME(eddyb) Get more valid Span's on queries.
-                // def_span guard is necessary to prevent a recursive loop,
-                // default_span calls def_span query internally.
-                let span = if stringify!($query) != "def_span" {
-                    $key.default_span(tcx)
-                } else {
-                    ::syntax_pos::DUMMY_SP
-                };
-
                 profq_msg!(tcx,
                     ProfileQueriesMsg::QueryBegin(
-                        span.data(),
-                        ::ty::maps::QueryMsg::$query(profq_key!(tcx, $key))
+                        DUMMY_SP.data(),
+                        profq_query_msg!(::ty::maps::queries::$query::NAME, tcx, $key),
                     )
                 );
 
-                match ::ty::maps::queries::$query::force(tcx, $key, span, *dep_node) {
+                match tcx.force_query::<::ty::maps::queries::$query>($key, DUMMY_SP, *dep_node) {
                     Ok(_) => {},
                     Err(e) => {
                         tcx.report_cycle(e).emit();
@@ -977,6 +959,7 @@ pub fn force_from_dep_node<'a, 'gcx, 'lcx>(tcx: TyCtxt<'a, 'gcx, 'lcx>,
         DepKind::NormalizeProjectionTy |
         DepKind::NormalizeTyAfterErasingRegions |
         DepKind::DropckOutlives |
+        DepKind::EvaluateObligation |
         DepKind::SubstituteNormalizeAndTestPredicates |
         DepKind::InstanceDefSizeEstimate |
         DepKind::ProgramClausesForEnv |
diff --git a/src/librustc/ty/maps/values.rs b/src/librustc/ty/maps/values.rs
index 8d38d7dbbbb..d3d06248792 100644
--- a/src/librustc/ty/maps/values.rs
+++ b/src/librustc/ty/maps/values.rs
@@ -37,7 +37,7 @@ impl<'tcx> Value<'tcx> for Ty<'tcx> {
 
 impl<'tcx> Value<'tcx> for ty::SymbolName {
     fn from_cycle_error<'a>(_: TyCtxt<'a, 'tcx, 'tcx>) -> Self {
-        ty::SymbolName { name: Symbol::intern("<error>").as_str() }
+        ty::SymbolName { name: Symbol::intern("<error>").as_interned_str() }
     }
 }
 
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index de043668410..c4fe112a9e9 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -51,7 +51,7 @@ use std::mem;
 use syntax::ast::{self, DUMMY_NODE_ID, Name, Ident, NodeId};
 use syntax::attr;
 use syntax::ext::hygiene::Mark;
-use syntax::symbol::{Symbol, InternedString};
+use syntax::symbol::{Symbol, LocalInternedString, InternedString};
 use syntax_pos::{DUMMY_SP, Span};
 
 use rustc_data_structures::accumulate_vec::IntoIter as AccIntoIter;
@@ -69,7 +69,7 @@ pub use self::sty::{ExistentialTraitRef, PolyExistentialTraitRef};
 pub use self::sty::{ExistentialProjection, PolyExistentialProjection, Const};
 pub use self::sty::{BoundRegion, EarlyBoundRegion, FreeRegion, Region};
 pub use self::sty::RegionKind;
-pub use self::sty::{TyVid, IntVid, FloatVid, RegionVid, SkolemizedRegionVid};
+pub use self::sty::{TyVid, IntVid, FloatVid, RegionVid};
 pub use self::sty::BoundRegion::*;
 pub use self::sty::InferTy::*;
 pub use self::sty::RegionKind::*;
@@ -1370,15 +1370,13 @@ impl<'tcx> InstantiatedPredicates<'tcx> {
 /// type name in a non-zero universe is a skolemized type -- an
 /// idealized representative of "types in general" that we use for
 /// checking generic functions.
-#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
+#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
 pub struct UniverseIndex(u32);
 
 impl UniverseIndex {
     /// The root universe, where things that the user defined are
     /// visible.
-    pub fn root() -> UniverseIndex {
-        UniverseIndex(0)
-    }
+    pub const ROOT: Self = UniverseIndex(0);
 
     /// A "subuniverse" corresponds to being inside a `forall` quantifier.
     /// So, for example, suppose we have this type in universe `U`:
@@ -1392,7 +1390,21 @@ impl UniverseIndex {
     /// region `'a`, but that region was not nameable from `U` because
     /// it was not in scope there.
     pub fn subuniverse(self) -> UniverseIndex {
-        UniverseIndex(self.0 + 1)
+        UniverseIndex(self.0.checked_add(1).unwrap())
+    }
+
+    pub fn as_u32(&self) -> u32 {
+        self.0
+    }
+
+    pub fn as_usize(&self) -> usize {
+        self.0 as usize
+    }
+}
+
+impl From<u32> for UniverseIndex {
+    fn from(index: u32) -> Self {
+        UniverseIndex(index)
     }
 }
 
@@ -1476,7 +1488,11 @@ impl<'tcx> ParamEnv<'tcx> {
             }
 
             Reveal::All => {
-                if value.needs_infer() || value.has_param_types() || value.has_self_ty() {
+                if value.has_skol()
+                    || value.needs_infer()
+                    || value.has_param_types()
+                    || value.has_self_ty()
+                {
                     ParamEnvAnd {
                         param_env: self,
                         value,
@@ -2031,7 +2047,7 @@ impl<'a, 'gcx, 'tcx> AdtDef {
     /// Due to normalization being eager, this applies even if
     /// the associated type is behind a pointer, e.g. issue #31299.
     pub fn sized_constraint(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> &'tcx [Ty<'tcx>] {
-        match queries::adt_sized_constraint::try_get(tcx, DUMMY_SP, self.did) {
+        match tcx.try_get_query::<queries::adt_sized_constraint>(DUMMY_SP, self.did) {
             Ok(tys) => tys,
             Err(mut bug) => {
                 debug!("adt_sized_constraint: {:?} is recursive", self);
@@ -2463,7 +2479,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 
     pub fn item_name(self, id: DefId) -> InternedString {
         if id.index == CRATE_DEF_INDEX {
-            self.original_crate_name(id.krate).as_str()
+            self.original_crate_name(id.krate).as_interned_str()
         } else {
             let def_key = self.def_key(id);
             // The name of a StructCtor is that of its struct parent.
@@ -2820,15 +2836,13 @@ impl_stable_hash_for!(struct self::SymbolName {
 impl SymbolName {
     pub fn new(name: &str) -> SymbolName {
         SymbolName {
-            name: Symbol::intern(name).as_str()
+            name: Symbol::intern(name).as_interned_str()
         }
     }
-}
 
-impl Deref for SymbolName {
-    type Target = str;
-
-    fn deref(&self) -> &str { &self.name }
+    pub fn as_str(&self) -> LocalInternedString {
+        self.name.as_str()
+    }
 }
 
 impl fmt::Display for SymbolName {
diff --git a/src/librustc/ty/structural_impls.rs b/src/librustc/ty/structural_impls.rs
index 9b20fce6673..d4ed6c60e0e 100644
--- a/src/librustc/ty/structural_impls.rs
+++ b/src/librustc/ty/structural_impls.rs
@@ -474,8 +474,18 @@ impl<'a, 'tcx> Lift<'tcx> for ConstEvalErr<'a> {
 impl<'a, 'tcx> Lift<'tcx> for interpret::EvalError<'a> {
     type Lifted = interpret::EvalError<'tcx>;
     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        Some(interpret::EvalError {
+            kind: tcx.lift(&self.kind)?,
+            backtrace: self.backtrace.clone(),
+        })
+    }
+}
+
+impl<'a, 'tcx, O: Lift<'tcx>> Lift<'tcx> for interpret::EvalErrorKind<'a, O> {
+    type Lifted = interpret::EvalErrorKind<'tcx, <O as Lift<'tcx>>::Lifted>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
         use ::mir::interpret::EvalErrorKind::*;
-        let kind = match self.kind {
+        Some(match *self {
             MachineError(ref err) => MachineError(err.clone()),
             FunctionPointerTyMismatch(a, b) => FunctionPointerTyMismatch(
                 tcx.lift(&a)?,
@@ -504,10 +514,11 @@ impl<'a, 'tcx> Lift<'tcx> for interpret::EvalError<'a> {
             Unimplemented(ref s) => Unimplemented(s.clone()),
             DerefFunctionPointer => DerefFunctionPointer,
             ExecuteMemory => ExecuteMemory,
-            ArrayIndexOutOfBounds(sp, a, b) => ArrayIndexOutOfBounds(sp, a, b),
-            Math(sp, ref err) => Math(sp, err.clone()),
+            BoundsCheck { ref len, ref index } => BoundsCheck {
+                len: tcx.lift(len)?,
+                index: tcx.lift(index)?,
+            },
             Intrinsic(ref s) => Intrinsic(s.clone()),
-            OverflowingMath => OverflowingMath,
             InvalidChar(c) => InvalidChar(c),
             StackFrameLimitReached => StackFrameLimitReached,
             OutOfTls => OutOfTls,
@@ -568,10 +579,12 @@ impl<'a, 'tcx> Lift<'tcx> for interpret::EvalError<'a> {
             UnimplementedTraitSelection => UnimplementedTraitSelection,
             TypeckError => TypeckError,
             ReferencedConstant => ReferencedConstant,
-        };
-        Some(interpret::EvalError {
-            kind: kind,
-            backtrace: self.backtrace.clone(),
+            OverflowNeg => OverflowNeg,
+            Overflow(op) => Overflow(op),
+            DivisionByZero => DivisionByZero,
+            RemainderByZero => RemainderByZero,
+            GeneratorResumedAfterReturn => GeneratorResumedAfterReturn,
+            GeneratorResumedAfterPanic => GeneratorResumedAfterPanic,
         })
     }
 }
@@ -585,7 +598,6 @@ impl<'a, 'tcx> Lift<'tcx> for const_val::ErrKind<'a> {
             NonConstPath => NonConstPath,
             UnimplementedConstVal(s) => UnimplementedConstVal(s),
             IndexOutOfBounds { len, index } => IndexOutOfBounds { len, index },
-            Math(ref e) => Math(e.clone()),
 
             LayoutError(ref e) => {
                 return tcx.lift(e).map(LayoutError)
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 0dfae13cc75..382db571b52 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -864,7 +864,7 @@ impl<'a, 'gcx, 'tcx> ParamTy {
     }
 
     pub fn for_self() -> ParamTy {
-        ParamTy::new(0, keywords::SelfType.name().as_str())
+        ParamTy::new(0, keywords::SelfType.name().as_interned_str())
     }
 
     pub fn for_def(def: &ty::TypeParameterDef) -> ParamTy {
@@ -876,8 +876,10 @@ impl<'a, 'gcx, 'tcx> ParamTy {
     }
 
     pub fn is_self(&self) -> bool {
-        if self.name == keywords::SelfType.name().as_str() {
-            assert_eq!(self.idx, 0);
+        // FIXME(#50125): Ignoring `Self` with `idx != 0` might lead to weird behavior elsewhere,
+        // but this should only be possible when using `-Z continue-parse-after-error` like
+        // `compile-fail/issue-36638.rs`.
+        if self.name == keywords::SelfType.name().as_str() && self.idx == 0 {
             true
         } else {
             false
@@ -1019,7 +1021,7 @@ pub enum RegionKind {
 
     /// A skolemized region - basically the higher-ranked version of ReFree.
     /// Should not exist after typeck.
-    ReSkolemized(SkolemizedRegionVid, BoundRegion),
+    ReSkolemized(ty::UniverseIndex, BoundRegion),
 
     /// Empty lifetime is for data that is never accessed.
     /// Bottom in the region lattice. We treat ReEmpty somewhat
@@ -1073,11 +1075,6 @@ newtype_index!(RegionVid
         DEBUG_FORMAT = custom,
     });
 
-#[derive(Clone, Copy, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, PartialOrd, Ord)]
-pub struct SkolemizedRegionVid {
-    pub index: u32,
-}
-
 #[derive(Clone, Copy, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 pub enum InferTy {
     TyVar(TyVid),
@@ -1169,13 +1166,6 @@ impl RegionKind {
         }
     }
 
-    pub fn needs_infer(&self) -> bool {
-        match *self {
-            ty::ReVar(..) | ty::ReSkolemized(..) => true,
-            _ => false
-        }
-    }
-
     pub fn escapes_depth(&self, depth: u32) -> bool {
         match *self {
             ty::ReLateBound(debruijn, _) => debruijn.depth > depth,
@@ -1193,20 +1183,29 @@ impl RegionKind {
         }
     }
 
+    pub fn keep_in_local_tcx(&self) -> bool {
+        if let ty::ReVar(..) = self {
+            true
+        } else {
+            false
+        }
+    }
+
     pub fn type_flags(&self) -> TypeFlags {
         let mut flags = TypeFlags::empty();
 
+        if self.keep_in_local_tcx() {
+            flags = flags | TypeFlags::KEEP_IN_LOCAL_TCX;
+        }
+
         match *self {
             ty::ReVar(..) => {
                 flags = flags | TypeFlags::HAS_FREE_REGIONS;
                 flags = flags | TypeFlags::HAS_RE_INFER;
-                flags = flags | TypeFlags::KEEP_IN_LOCAL_TCX;
             }
             ty::ReSkolemized(..) => {
                 flags = flags | TypeFlags::HAS_FREE_REGIONS;
-                flags = flags | TypeFlags::HAS_RE_INFER;
                 flags = flags | TypeFlags::HAS_RE_SKOL;
-                flags = flags | TypeFlags::KEEP_IN_LOCAL_TCX;
             }
             ty::ReLateBound(..) => { }
             ty::ReEarlyBound(..) => {
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index a10ca132472..4aa70e1f7e0 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -1024,7 +1024,7 @@ fn needs_drop_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     let (param_env, ty) = query.into_parts();
 
     let needs_drop = |ty: Ty<'tcx>| -> bool {
-        match ty::queries::needs_drop_raw::try_get(tcx, DUMMY_SP, param_env.and(ty)) {
+        match tcx.try_get_query::<ty::queries::needs_drop_raw>(DUMMY_SP, param_env.and(ty)) {
             Ok(v) => v,
             Err(mut bug) => {
                 // Cycles should be reported as an error by `check_representable`.
diff --git a/src/librustc/util/common.rs b/src/librustc/util/common.rs
index bb6aa654c29..85533caffce 100644
--- a/src/librustc/util/common.rs
+++ b/src/librustc/util/common.rs
@@ -25,7 +25,6 @@ use std::time::{Duration, Instant};
 
 use std::sync::mpsc::{Sender};
 use syntax_pos::{SpanData};
-use ty::maps::{QueryMsg};
 use ty::TyCtxt;
 use dep_graph::{DepNode};
 use proc_macro;
@@ -59,6 +58,17 @@ fn panic_hook(info: &panic::PanicInfo) {
         if backtrace {
             TyCtxt::try_print_query_stack();
         }
+
+        #[cfg(windows)]
+        unsafe {
+            if env::var("RUSTC_BREAK_ON_ICE").is_ok() {
+                extern "system" {
+                    fn DebugBreak();
+                }
+                // Trigger a debugger if we crashed during bootstrap
+                DebugBreak();
+            }
+        }
     }
 }
 
@@ -77,6 +87,13 @@ pub struct ProfQDumpParams {
     pub dump_profq_msg_log:bool,
 }
 
+#[allow(bad_style)]
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct QueryMsg {
+    pub query: &'static str,
+    pub msg: Option<String>,
+}
+
 /// A sequence of these messages induce a trace of query-based incremental compilation.
 /// FIXME(matthewhammer): Determine whether we should include cycle detection here or not.
 #[derive(Clone,Debug)]
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 905776373bd..894a18b79cc 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -462,7 +462,7 @@ impl PrintContext {
                 0 => Symbol::intern("'r"),
                 1 => Symbol::intern("'s"),
                 i => Symbol::intern(&format!("'t{}", i-2)),
-            }.as_str()
+            }.as_interned_str()
         }
 
         // Replace any anonymous late-bound regions with named
@@ -808,8 +808,8 @@ define_print! {
                     write!(f, "'?{}", c.index())
                 }
 
-                ty::ReSkolemized(id, ref bound_region) => {
-                    write!(f, "ReSkolemized({}, {:?})", id.index, bound_region)
+                ty::ReSkolemized(universe, ref bound_region) => {
+                    write!(f, "ReSkolemized({:?}, {:?})", universe, bound_region)
                 }
 
                 ty::ReEmpty => write!(f, "ReEmpty"),