rustc: treat ReEarlyBound as free without replacing it with ReFree.

35 files changed, 248 insertions, 332 deletions

diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index f822361198f..f9a86c2f010 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -54,7 +54,8 @@ impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ty::RegionKind<'tc
                 db.depth.hash_stable(hcx, hasher);
                 i.hash_stable(hcx, hasher);
             }
-            ty::ReEarlyBound(ty::EarlyBoundRegion { index, name }) => {
+            ty::ReEarlyBound(ty::EarlyBoundRegion { def_id, index, name }) => {
+                def_id.hash_stable(hcx, hasher);
                 index.hash_stable(hcx, hasher);
                 name.hash_stable(hcx, hasher);
             }
diff --git a/src/librustc/infer/combine.rs b/src/librustc/infer/combine.rs
index 82578f6aa61..18909a784d6 100644
--- a/src/librustc/infer/combine.rs
+++ b/src/librustc/infer/combine.rs
@@ -423,15 +423,6 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
                 return Ok(r);
             }
 
-            // Early-bound regions should really have been substituted away before
-            // we get to this point.
-            ty::ReEarlyBound(..) => {
-                span_bug!(
-                    self.span,
-                    "Encountered early bound region when generalizing: {:?}",
-                    r);
-            }
-
             // Always make a fresh region variable for skolemized regions;
             // the higher-ranked decision procedures rely on this.
             ty::ReSkolemized(..) => { }
@@ -442,6 +433,7 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
             ty::ReStatic |
             ty::ReScope(..) |
             ty::ReVar(..) |
+            ty::ReEarlyBound(..) |
             ty::ReFree(..) => {
                 match self.ambient_variance {
                     ty::Invariant => return Ok(r),
diff --git a/src/librustc/infer/error_reporting/mod.rs b/src/librustc/infer/error_reporting/mod.rs
index 389103e203e..da5ff6ff38a 100644
--- a/src/librustc/infer/error_reporting/mod.rs
+++ b/src/librustc/infer/error_reporting/mod.rs
@@ -172,19 +172,35 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
                 explain_span(self, scope_decorated_tag, span)
             }
 
-            ty::ReFree(ref fr) => {
-                let prefix = match fr.bound_region {
-                    ty::BrAnon(idx) => {
-                        format!("the anonymous lifetime #{} defined on", idx + 1)
+            ty::ReEarlyBound(_) |
+            ty::ReFree(_) => {
+                let scope = match *region {
+                    ty::ReEarlyBound(ref br) => {
+                        self.parent_def_id(br.def_id).unwrap()
                     }
-                    ty::BrFresh(_) => "an anonymous lifetime defined on".to_owned(),
-                    _ => {
-                        format!("the lifetime {} as defined on",
-                                fr.bound_region)
+                    ty::ReFree(ref fr) => fr.scope,
+                    _ => bug!()
+                };
+                let prefix = match *region {
+                    ty::ReEarlyBound(ref br) => {
+                        format!("the lifetime {} as defined on", br.name)
+                    }
+                    ty::ReFree(ref fr) => {
+                        match fr.bound_region {
+                            ty::BrAnon(idx) => {
+                                format!("the anonymous lifetime #{} defined on", idx + 1)
+                            }
+                            ty::BrFresh(_) => "an anonymous lifetime defined on".to_owned(),
+                            _ => {
+                                format!("the lifetime {} as defined on",
+                                        fr.bound_region)
+                            }
+                        }
                     }
+                    _ => bug!()
                 };
 
-                let node = self.hir.as_local_node_id(fr.scope)
+                let node = self.hir.as_local_node_id(scope)
                                    .unwrap_or(DUMMY_NODE_ID);
                 let unknown;
                 let tag = match self.hir.find(node) {
@@ -199,12 +215,12 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
                     Some(_) => {
                         unknown = format!("unexpected node ({}) for scope {:?}.  \
                                            Please report a bug.",
-                                          self.hir.node_to_string(node), fr.scope);
+                                          self.hir.node_to_string(node), scope);
                         &unknown
                     }
                     None => {
                         unknown = format!("unknown node for scope {:?}.  \
-                                           Please report a bug.", fr.scope);
+                                           Please report a bug.", scope);
                         &unknown
                     }
                 };
@@ -216,8 +232,6 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 
             ty::ReEmpty => ("the empty lifetime".to_owned(), None),
 
-            ty::ReEarlyBound(ref data) => (data.name.to_string(), None),
-
             // FIXME(#13998) ReSkolemized should probably print like
             // ReFree rather than dumping Debug output on the user.
             //
@@ -797,6 +811,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         }
 
         let mut err = match *sub {
+            ty::ReEarlyBound(_) |
             ty::ReFree(ty::FreeRegion {bound_region: ty::BrNamed(..), ..}) => {
                 // Does the required lifetime have a nice name we can print?
                 let mut err = struct_span_err!(self.tcx.sess,
diff --git a/src/librustc/infer/freshen.rs b/src/librustc/infer/freshen.rs
index ad67ef9a127..a0ef1f65f52 100644
--- a/src/librustc/infer/freshen.rs
+++ b/src/librustc/infer/freshen.rs
@@ -85,13 +85,13 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
 
     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
         match *r {
-            ty::ReEarlyBound(..) |
             ty::ReLateBound(..) => {
                 // leave bound regions alone
                 r
             }
 
             ty::ReStatic |
+            ty::ReEarlyBound(..) |
             ty::ReFree(_) |
             ty::ReScope(_) |
             ty::ReVar(_) |
diff --git a/src/librustc/infer/higher_ranked/mod.rs b/src/librustc/infer/higher_ranked/mod.rs
index 09f909ef399..dbbcc6cfbec 100644
--- a/src/librustc/infer/higher_ranked/mod.rs
+++ b/src/librustc/infer/higher_ranked/mod.rs
@@ -274,7 +274,7 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
                                              -> ty::Region<'tcx> {
             // Regions that pre-dated the LUB computation stay as they are.
             if !is_var_in_set(new_vars, r0) {
-                assert!(!r0.is_bound());
+                assert!(!r0.is_late_bound());
                 debug!("generalize_region(r0={:?}): not new variable", r0);
                 return r0;
             }
@@ -288,7 +288,7 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
                 debug!("generalize_region(r0={:?}): \
                         non-new-variables found in {:?}",
                        r0, tainted);
-                assert!(!r0.is_bound());
+                assert!(!r0.is_late_bound());
                 return r0;
             }
 
@@ -371,7 +371,7 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
                                              r0: ty::Region<'tcx>)
                                              -> ty::Region<'tcx> {
             if !is_var_in_set(new_vars, r0) {
-                assert!(!r0.is_bound());
+                assert!(!r0.is_late_bound());
                 return r0;
             }
 
@@ -424,7 +424,7 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
                 return rev_lookup(infcx, span, a_map, a_r.unwrap());
             } else if a_r.is_none() && b_r.is_none() {
                 // Not related to bound variables from either fn:
-                assert!(!r0.is_bound());
+                assert!(!r0.is_late_bound());
                 return r0;
             } else {
                 // Other:
diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index 23d720433c2..e42280124a1 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -1009,7 +1009,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     }
 
     pub fn add_given(&self,
-                     sub: ty::FreeRegion,
+                     sub: ty::Region<'tcx>,
                      sup: ty::RegionVid)
     {
         self.region_vars.add_given(sub, sup);
diff --git a/src/librustc/infer/region_inference/mod.rs b/src/librustc/infer/region_inference/mod.rs
index 4c82c3bfb85..2e3c2443544 100644
--- a/src/librustc/infer/region_inference/mod.rs
+++ b/src/librustc/infer/region_inference/mod.rs
@@ -29,7 +29,6 @@ use ty::{ReEmpty, ReStatic, ReFree, ReEarlyBound, ReErased};
 use ty::{ReLateBound, ReScope, ReVar, ReSkolemized, BrFresh};
 
 use std::cell::{Cell, RefCell};
-use std::cmp::Ordering::{self, Less, Greater, Equal};
 use std::fmt;
 use std::mem;
 use std::u32;
@@ -127,7 +126,7 @@ pub enum UndoLogEntry<'tcx> {
     AddVerify(usize),
 
     /// We added the given `given`
-    AddGiven(ty::FreeRegion, ty::RegionVid),
+    AddGiven(Region<'tcx>, ty::RegionVid),
 
     /// We added a GLB/LUB "combinaton variable"
     AddCombination(CombineMapType, TwoRegions<'tcx>),
@@ -213,7 +212,7 @@ pub struct RegionVarBindings<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     // record the fact that `'a <= 'b` is implied by the fn signature,
     // and then ignore the constraint when solving equations. This is
     // a bit of a hack but seems to work.
-    givens: RefCell<FxHashSet<(ty::FreeRegion, ty::RegionVid)>>,
+    givens: RefCell<FxHashSet<(Region<'tcx>, ty::RegionVid)>>,
 
     lubs: RefCell<CombineMap<'tcx>>,
     glbs: RefCell<CombineMap<'tcx>>,
@@ -309,8 +308,7 @@ impl<'a, 'gcx, 'tcx> TaintSet<'tcx> {
                         self.add_edge(a, b);
                     }
                     &AddGiven(a, b) => {
-                        self.add_edge(tcx.mk_region(ReFree(a)),
-                                      tcx.mk_region(ReVar(b)));
+                        self.add_edge(a, tcx.mk_region(ReVar(b)));
                     }
                     &AddVerify(i) => {
                         verifys[i].bound.for_each_region(&mut |b| {
@@ -661,7 +659,7 @@ impl<'a, 'gcx, 'tcx> RegionVarBindings<'a, 'gcx, 'tcx> {
         }
     }
 
-    pub fn add_given(&self, sub: ty::FreeRegion, sup: ty::RegionVid) {
+    pub fn add_given(&self, sub: Region<'tcx>, sup: ty::RegionVid) {
         // cannot add givens once regions are resolved
         assert!(self.values_are_none());
 
@@ -702,9 +700,7 @@ impl<'a, 'gcx, 'tcx> RegionVarBindings<'a, 'gcx, 'tcx> {
                origin);
 
         match (sub, sup) {
-            (&ReEarlyBound(..), _) |
             (&ReLateBound(..), _) |
-            (_, &ReEarlyBound(..)) |
             (_, &ReLateBound(..)) => {
                 span_bug!(origin.span(),
                           "cannot relate bound region: {:?} <= {:?}",
@@ -908,8 +904,6 @@ impl<'a, 'gcx, 'tcx> RegionVarBindings<'a, 'gcx, 'tcx> {
         match (a, b) {
             (&ReLateBound(..), _) |
             (_, &ReLateBound(..)) |
-            (&ReEarlyBound(..), _) |
-            (_, &ReEarlyBound(..)) |
             (&ReErased, _) |
             (_, &ReErased) => {
                 bug!("cannot relate region: LUB({:?}, {:?})", a, b);
@@ -931,18 +925,32 @@ impl<'a, 'gcx, 'tcx> RegionVarBindings<'a, 'gcx, 'tcx> {
                           b);
             }
 
-            (&ReFree(ref fr), &ReScope(s_id)) |
-            (&ReScope(s_id), &ReFree(ref fr)) => {
+            (&ReEarlyBound(_), &ReScope(s_id)) |
+            (&ReScope(s_id), &ReEarlyBound(_)) |
+            (&ReFree(_), &ReScope(s_id)) |
+            (&ReScope(s_id), &ReFree(_)) => {
                 // A "free" region can be interpreted as "some region
                 // at least as big as fr.scope".  So, we can
                 // reasonably compare free regions and scopes:
-                let fr_scope = region_rels.region_maps.free_extent(self.tcx, fr);
+                let fr_scope = match (a, b) {
+                    (&ReEarlyBound(ref br), _) | (_, &ReEarlyBound(ref br)) => {
+                        region_rels.region_maps.early_free_extent(self.tcx, br)
+                    }
+                    (&ReFree(ref fr), _) | (_, &ReFree(ref fr)) => {
+                        region_rels.region_maps.free_extent(self.tcx, fr)
+                    }
+                    _ => bug!()
+                };
                 let r_id = region_rels.region_maps.nearest_common_ancestor(fr_scope, s_id);
                 if r_id == fr_scope {
                     // if the free region's scope `fr.scope` is bigger than
                     // the scope region `s_id`, then the LUB is the free
                     // region itself:
-                    return self.tcx.mk_region(ReFree(*fr));
+                    match (a, b) {
+                        (_, &ReScope(_)) => return a,
+                        (&ReScope(_), _) => return b,
+                        _ => bug!()
+                    }
                 }
 
                 // otherwise, we don't know what the free region is,
@@ -958,6 +966,9 @@ impl<'a, 'gcx, 'tcx> RegionVarBindings<'a, 'gcx, 'tcx> {
                 self.tcx.mk_region(ReScope(lub))
             }
 
+            (&ReEarlyBound(_), &ReEarlyBound(_)) |
+            (&ReFree(_), &ReEarlyBound(_)) |
+            (&ReEarlyBound(_), &ReFree(_)) |
             (&ReFree(_), &ReFree(_)) => {
                 region_rels.lub_free_regions(a, b)
             }
@@ -1040,13 +1051,13 @@ impl<'a, 'gcx, 'tcx> RegionVarBindings<'a, 'gcx, 'tcx> {
 
         let mut givens = self.givens.borrow_mut();
         let seeds: Vec<_> = givens.iter().cloned().collect();
-        for (fr, vid) in seeds {
+        for (r, vid) in seeds {
             let seed_index = NodeIndex(vid.index as usize);
             for succ_index in graph.depth_traverse(seed_index, OUTGOING) {
                 let succ_index = succ_index.0 as u32;
                 if succ_index < self.num_vars() {
                     let succ_vid = RegionVid { index: succ_index };
-                    givens.insert((fr, succ_vid));
+                    givens.insert((r, succ_vid));
                 }
             }
         }
@@ -1095,8 +1106,9 @@ impl<'a, 'gcx, 'tcx> RegionVarBindings<'a, 'gcx, 'tcx> {
 
         // Check if this relationship is implied by a given.
         match *a_region {
-            ty::ReFree(fr) => {
-                if self.givens.borrow().contains(&(fr, b_vid)) {
+            ty::ReEarlyBound(_) |
+            ty::ReFree(_) => {
+                if self.givens.borrow().contains(&(a_region, b_vid)) {
                     debug!("given");
                     return false;
                 }
@@ -1332,16 +1344,15 @@ impl<'a, 'gcx, 'tcx> RegionVarBindings<'a, 'gcx, 'tcx> {
         // We place free regions first because we are special casing
         // SubSupConflict(ReFree, ReFree) when reporting error, and so
         // the user will more likely get a specific suggestion.
-        fn free_regions_first(a: &RegionAndOrigin, b: &RegionAndOrigin) -> Ordering {
-            match (a.region, b.region) {
-                (&ReFree(..), &ReFree(..)) => Equal,
-                (&ReFree(..), _) => Less,
-                (_, &ReFree(..)) => Greater,
-                (..) => Equal,
+        fn region_order_key(x: &RegionAndOrigin) -> u8 {
+            match *x.region {
+                ReEarlyBound(_) => 0,
+                ReFree(_) => 1,
+                _ => 2
             }
         }
-        lower_bounds.sort_by(|a, b| free_regions_first(a, b));
-        upper_bounds.sort_by(|a, b| free_regions_first(a, b));
+        lower_bounds.sort_by_key(region_order_key);
+        upper_bounds.sort_by_key(region_order_key);
 
         for lower_bound in &lower_bounds {
             for upper_bound in &upper_bounds {
diff --git a/src/librustc/middle/free_region.rs b/src/librustc/middle/free_region.rs
index e0d13878f14..8168837b1f5 100644
--- a/src/librustc/middle/free_region.rs
+++ b/src/librustc/middle/free_region.rs
@@ -71,23 +71,27 @@ impl<'a, 'gcx, 'tcx> RegionRelations<'a, 'gcx, 'tcx> {
                 (&ty::ReScope(sub_scope), &ty::ReScope(super_scope)) =>
                     self.region_maps.is_subscope_of(sub_scope, super_scope),
 
+                (&ty::ReScope(sub_scope), &ty::ReEarlyBound(ref br)) => {
+                    let fr_scope = self.region_maps.early_free_extent(self.tcx, br);
+                    self.region_maps.is_subscope_of(sub_scope, fr_scope)
+                }
+
                 (&ty::ReScope(sub_scope), &ty::ReFree(ref fr)) => {
                     let fr_scope = self.region_maps.free_extent(self.tcx, fr);
-                    self.region_maps.is_subscope_of(sub_scope, fr_scope) ||
-                        self.is_static(super_region)
+                    self.region_maps.is_subscope_of(sub_scope, fr_scope)
                 }
 
+                (&ty::ReEarlyBound(_), &ty::ReEarlyBound(_)) |
+                (&ty::ReFree(_), &ty::ReEarlyBound(_)) |
+                (&ty::ReEarlyBound(_), &ty::ReFree(_)) |
                 (&ty::ReFree(_), &ty::ReFree(_)) =>
-                    self.free_regions.relation.contains(&sub_region, &super_region) ||
-                        self.is_static(super_region),
-
-                (&ty::ReStatic, &ty::ReFree(_)) =>
-                    self.is_static(super_region),
+                    self.free_regions.relation.contains(&sub_region, &super_region),
 
                 _ =>
                     false,
             }
         };
+        let result = result || self.is_static(super_region);
         debug!("is_subregion_of(sub_region={:?}, super_region={:?}) = {:?}",
                sub_region, super_region, result);
         result
@@ -98,11 +102,11 @@ impl<'a, 'gcx, 'tcx> RegionRelations<'a, 'gcx, 'tcx> {
         debug!("is_static(super_region={:?})", super_region);
         match *super_region {
             ty::ReStatic => true,
-            ty::ReFree(_) => {
+            ty::ReEarlyBound(_) | ty::ReFree(_) => {
                 let re_static = self.tcx.mk_region(ty::ReStatic);
                 self.free_regions.relation.contains(&re_static, &super_region)
             }
-            _ => bug!("only free regions should be given to `is_static`")
+            _ => false
         }
     }
 
@@ -139,11 +143,9 @@ impl<'tcx> FreeRegionMap<'tcx> {
         for implied_bound in implied_bounds {
             debug!("implied bound: {:?}", implied_bound);
             match *implied_bound {
-                ImpliedBound::RegionSubRegion(a @ &ty::ReFree(_), b @ &ty::ReFree(_)) |
-                ImpliedBound::RegionSubRegion(a @ &ty::ReStatic, b @ &ty::ReFree(_)) => {
+                ImpliedBound::RegionSubRegion(a, b) => {
                     self.relate_regions(a, b);
                 }
-                ImpliedBound::RegionSubRegion(..) |
                 ImpliedBound::RegionSubParam(..) |
                 ImpliedBound::RegionSubProjection(..) => {
                 }
@@ -167,32 +169,18 @@ impl<'tcx> FreeRegionMap<'tcx> {
                     // No region bounds here
                 }
                 ty::Predicate::RegionOutlives(ty::Binder(ty::OutlivesPredicate(r_a, r_b))) => {
-                    match (r_a, r_b) {
-                        // `'static: 'x` is not notable
-                        (&ty::ReStatic, &ty::ReFree(_)) => {},
-
-                        (&ty::ReFree(_), &ty::ReStatic) |
-                        (&ty::ReFree(_), &ty::ReFree(_)) => {
-                            // Record that `'a:'b`. Or, put another way, `'b <= 'a`.
-                            self.relate_regions(r_b, r_a);
-                        }
-
-                        _ => {
-                            // All named regions are instantiated with free regions.
-                            bug!("record_region_bounds: non free region: {:?} / {:?}",
-                                 r_a,
-                                 r_b);
-                        }
-                    }
+                    self.relate_regions(r_b, r_a);
                 }
             }
         }
     }
 
+    // Record that `'sup:'sub`. Or, put another way, `'sub <= 'sup`.
+    // (with the exception that `'static: 'x` is not notable)
     fn relate_regions(&mut self, sub: Region<'tcx>, sup: Region<'tcx>) {
-        assert!(match *sub { ty::ReFree(_) | ty::ReStatic => true, _ => false });
-        assert!(match *sup { ty::ReFree(_) | ty::ReStatic => true, _ => false });
-        self.relation.add(sub, sup)
+        if (is_free(sub) || *sub == ty::ReStatic) && is_free(sup) {
+            self.relation.add(sub, sup)
+        }
     }
 
     pub fn lub_free_regions<'a, 'gcx>(&self,
@@ -200,8 +188,8 @@ impl<'tcx> FreeRegionMap<'tcx> {
                                       r_a: Region<'tcx>,
                                       r_b: Region<'tcx>)
                                       -> Region<'tcx> {
-        assert!(match *r_a { ty::ReFree(_) => true, _ => false });
-        assert!(match *r_b { ty::ReFree(_) => true, _ => false });
+        assert!(is_free(r_a));
+        assert!(is_free(r_b));
         let result = if r_a == r_b { r_a } else {
             match self.relation.postdom_upper_bound(&r_a, &r_b) {
                 None => tcx.mk_region(ty::ReStatic),
@@ -213,6 +201,13 @@ impl<'tcx> FreeRegionMap<'tcx> {
     }
 }
 
+fn is_free(r: Region) -> bool {
+    match *r {
+        ty::ReEarlyBound(_) | ty::ReFree(_) => true,
+        _ => false
+    }
+}
+
 impl_stable_hash_for!(struct FreeRegionMap<'tcx> {
     relation
 });
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index c6565b78f61..917b21c865a 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -608,6 +608,33 @@ impl<'tcx> RegionMaps<'tcx> {
 
     /// Assuming that the provided region was defined within this `RegionMaps`,
     /// returns the outermost `CodeExtent` that the region outlives.
+    pub fn early_free_extent<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
+                                       br: &ty::EarlyBoundRegion)
+                                       -> CodeExtent<'tcx> {
+        let param_owner = tcx.parent_def_id(br.def_id).unwrap();
+
+        let param_owner_id = tcx.hir.as_local_node_id(param_owner).unwrap();
+        let body_id = tcx.hir.maybe_body_owned_by(param_owner_id).unwrap_or_else(|| {
+            // The lifetime was defined on node that doesn't own a body,
+            // which in practice can only mean a trait or an impl, that
+            // is the parent of a method, and that is enforced below.
+            assert_eq!(Some(param_owner_id), self.root_parent,
+                       "free_extent: {:?} not recognized by the region maps for {:?}",
+                       param_owner,
+                       self.root_body.map(|body| tcx.hir.body_owner_def_id(body)));
+
+            // The trait/impl lifetime is in scope for the method's body.
+            self.root_body.unwrap()
+        });
+
+        tcx.intern_code_extent(CodeExtentData::CallSiteScope {
+            fn_id: tcx.hir.body_owner(body_id),
+            body_id: body_id.node_id
+        })
+    }
+
+    /// Assuming that the provided region was defined within this `RegionMaps`,
+    /// returns the outermost `CodeExtent` that the region outlives.
     pub fn free_extent<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, fr: &ty::FreeRegion)
                                  -> CodeExtent<'tcx> {
         let param_owner = match fr.bound_region {
@@ -617,27 +644,12 @@ impl<'tcx> RegionMaps<'tcx> {
             _ => fr.scope
         };
 
-        let param_owner_id = tcx.hir.as_local_node_id(param_owner).unwrap();
-        let body_id = tcx.hir.maybe_body_owned_by(param_owner_id)
-        .map(|body| {
-            assert_eq!(param_owner, fr.scope);
-            body
-        })
-        .unwrap_or_else(|| {
-            let root = tcx.hir.as_local_node_id(fr.scope).unwrap();
-
-            assert_eq!(Some(param_owner_id), self.root_parent,
-                       "free_extent: {:?} not recognized by the region maps for {:?}",
-                       param_owner, fr.scope);
-
-            let root_body = tcx.hir.body_owned_by(root);
+        // Ensure that the named late-bound lifetimes were defined
+        // on the same function that they ended up being freed in.
+        assert_eq!(param_owner, fr.scope);
 
-            assert!(Some(root_body) == self.root_body,
-                    "free_extent: {:?} not inside {:?}",
-                    param_owner, self.root_body.map(|body| tcx.hir.body_owner_def_id(body)));
-
-            root_body
-        });
+        let param_owner_id = tcx.hir.as_local_node_id(param_owner).unwrap();
+        let body_id = tcx.hir.body_owned_by(param_owner_id);
 
         tcx.intern_code_extent(CodeExtentData::CallSiteScope {
             fn_id: tcx.hir.body_owner(body_id),
diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index 55770efa9ad..7d7308d73bb 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -894,7 +894,9 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
         };
 
         if let Some(mut def) = result {
-            if let Some(body_id) = outermost_body {
+            if let Region::EarlyBound(..) = def {
+                // Do not free early-bound regions, only late-bound ones.
+            } else if let Some(body_id) = outermost_body {
                 let fn_id = self.hir_map.body_owner(body_id);
                 match self.hir_map.get(fn_id) {
                     hir::map::NodeItem(&hir::Item {
diff --git a/src/librustc/traits/object_safety.rs b/src/librustc/traits/object_safety.rs
index dbc1f070af8..66e8e503be4 100644
--- a/src/librustc/traits/object_safety.rs
+++ b/src/librustc/traits/object_safety.rs
@@ -206,9 +206,8 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         };
 
         // Search for a predicate like `Self : Sized` amongst the trait bounds.
-        let free_substs = self.construct_free_substs(def_id);
         let predicates = self.predicates_of(def_id);
-        let predicates = predicates.instantiate(self, free_substs).predicates;
+        let predicates = predicates.instantiate_identity(self).predicates;
         elaborate_predicates(self, predicates)
             .any(|predicate| {
                 match predicate {
diff --git a/src/librustc/traits/specialize/mod.rs b/src/librustc/traits/specialize/mod.rs
index f8d8f3962b8..3882e218241 100644
--- a/src/librustc/traits/specialize/mod.rs
+++ b/src/librustc/traits/specialize/mod.rs
@@ -180,9 +180,7 @@ pub fn specializes<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     // create a parameter environment corresponding to a (skolemized) instantiation of impl1
     let penv = tcx.parameter_environment(impl1_def_id);
-    let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id)
-                             .unwrap()
-                             .subst(tcx, &penv.free_substs);
+    let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id).unwrap();
 
     // Create a infcx, taking the predicates of impl1 as assumptions:
     let result = tcx.infer_ctxt(penv, Reveal::UserFacing).enter(|infcx| {
diff --git a/src/librustc/traits/util.rs b/src/librustc/traits/util.rs
index 1d10c3a9695..3f5cf7eca53 100644
--- a/src/librustc/traits/util.rs
+++ b/src/librustc/traits/util.rs
@@ -197,7 +197,7 @@ impl<'cx, 'gcx, 'tcx> Elaborator<'cx, 'gcx, 'tcx> {
                 // I want to be conservative. --nmatsakis
                 let ty_max = data.skip_binder().0;
                 let r_min = data.skip_binder().1;
-                if r_min.is_bound() {
+                if r_min.is_late_bound() {
                     return;
                 }
 
@@ -206,7 +206,7 @@ impl<'cx, 'gcx, 'tcx> Elaborator<'cx, 'gcx, 'tcx> {
                     tcx.outlives_components(ty_max)
                        .into_iter()
                        .filter_map(|component| match component {
-                           Component::Region(r) => if r.is_bound() {
+                           Component::Region(r) => if r.is_late_bound() {
                                None
                            } else {
                                Some(ty::Predicate::RegionOutlives(
diff --git a/src/librustc/ty/layout.rs b/src/librustc/ty/layout.rs
index c3208e1dbfe..bd38a6c3fd3 100644
--- a/src/librustc/ty/layout.rs
+++ b/src/librustc/ty/layout.rs
@@ -1271,7 +1271,7 @@ impl<'a, 'gcx, 'tcx> Layout {
                         let param_env = tcx.parameter_environment(def.did);
                         let fields = &def.variants[0].fields;
                         let last_field = &fields[fields.len()-1];
-                        let always_sized = last_field.ty(tcx, param_env.free_substs)
+                        let always_sized = tcx.type_of(last_field.did)
                           .is_sized(tcx, &param_env, DUMMY_SP);
                         if !always_sized { StructKind::MaybeUnsizedUnivariant }
                         else { StructKind::AlwaysSizedUnivariant }
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 8ccaf0622d7..51bd0b88bac 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -731,12 +731,19 @@ pub struct RegionParameterDef {
 impl RegionParameterDef {
     pub fn to_early_bound_region_data(&self) -> ty::EarlyBoundRegion {
         ty::EarlyBoundRegion {
+            def_id: self.def_id,
             index: self.index,
             name: self.name,
         }
     }
 
     pub fn to_bound_region(&self) -> ty::BoundRegion {
+        self.to_early_bound_region_data().to_bound_region()
+    }
+}
+
+impl ty::EarlyBoundRegion {
+    pub fn to_bound_region(&self) -> ty::BoundRegion {
         ty::BoundRegion::BrNamed(self.def_id, self.name)
     }
 }
@@ -815,6 +822,21 @@ impl<'a, 'gcx, 'tcx> GenericPredicates<'tcx> {
         instantiated.predicates.extend(self.predicates.iter().map(|p| p.subst(tcx, substs)))
     }
 
+    pub fn instantiate_identity(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>)
+                                -> InstantiatedPredicates<'tcx> {
+        let mut instantiated = InstantiatedPredicates::empty();
+        self.instantiate_identity_into(tcx, &mut instantiated);
+        instantiated
+    }
+
+    fn instantiate_identity_into(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
+                                 instantiated: &mut InstantiatedPredicates<'tcx>) {
+        if let Some(def_id) = self.parent {
+            tcx.predicates_of(def_id).instantiate_identity_into(tcx, instantiated);
+        }
+        instantiated.predicates.extend(&self.predicates)
+    }
+
     pub fn instantiate_supertrait(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
                                   poly_trait_ref: &ty::PolyTraitRef<'tcx>)
                                   -> InstantiatedPredicates<'tcx>
@@ -1240,9 +1262,6 @@ impl<'tcx> InstantiatedPredicates<'tcx> {
 /// more distinctions clearer.
 #[derive(Clone)]
 pub struct ParameterEnvironment<'tcx> {
-    /// See `construct_free_substs` for details.
-    pub free_substs: &'tcx Substs<'tcx>,
-
     /// Obligations that the caller must satisfy. This is basically
     /// the set of bounds on the in-scope type parameters, translated
     /// into Obligations, and elaborated and normalized.
@@ -1264,7 +1283,6 @@ impl<'a, 'tcx> ParameterEnvironment<'tcx> {
                               -> ParameterEnvironment<'tcx>
     {
         ParameterEnvironment {
-            free_substs: self.free_substs,
             caller_bounds: caller_bounds,
             is_copy_cache: RefCell::new(FxHashMap()),
             is_sized_cache: RefCell::new(FxHashMap()),
@@ -2372,7 +2390,6 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     /// are no free type/lifetime parameters in scope.
     pub fn empty_parameter_environment(self) -> ParameterEnvironment<'tcx> {
         ty::ParameterEnvironment {
-            free_substs: self.intern_substs(&[]),
             caller_bounds: Slice::empty(),
             is_copy_cache: RefCell::new(FxHashMap()),
             is_sized_cache: RefCell::new(FxHashMap()),
@@ -2380,43 +2397,14 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         }
     }
 
-    /// Constructs and returns a substitution that can be applied to move from
-    /// the "outer" view of a type or method to the "inner" view.
-    /// In general, this means converting from bound parameters to
-    /// free parameters. Since we currently represent bound/free type
-    /// parameters in the same way, this only has an effect on regions.
-    pub fn construct_free_substs(self, def_id: DefId) -> &'gcx Substs<'gcx> {
-        let scope = self.closure_base_def_id(def_id);
-        let substs = Substs::for_item(self.global_tcx(), def_id, |def, _| {
-            // map bound 'a => free 'a
-            self.global_tcx().mk_region(ReFree(FreeRegion {
-                scope,
-                bound_region: def.to_bound_region()
-            }))
-        }, |def, _| {
-            // map T => T
-            self.global_tcx().mk_param_from_def(def)
-        });
-
-        debug!("parameter_environment: {:?}", substs);
-        substs
-    }
-
     /// See `ParameterEnvironment` struct def'n for details.
     pub fn parameter_environment(self, def_id: DefId) -> ParameterEnvironment<'gcx> {
         //
-        // Construct the free substs.
-        //
-
-        let free_substs = self.construct_free_substs(def_id);
-
-        //
         // Compute the bounds on Self and the type parameters.
         //
 
         let tcx = self.global_tcx();
-        let generic_predicates = tcx.predicates_of(def_id);
-        let bounds = generic_predicates.instantiate(tcx, free_substs);
+        let bounds = tcx.predicates_of(def_id).instantiate_identity(tcx);
         let predicates = bounds.predicates;
 
         // Finally, we have to normalize the bounds in the environment, in
@@ -2433,7 +2421,6 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         //
 
         let unnormalized_env = ty::ParameterEnvironment {
-            free_substs,
             caller_bounds: tcx.intern_predicates(&predicates),
             is_copy_cache: RefCell::new(FxHashMap()),
             is_sized_cache: RefCell::new(FxHashMap()),
diff --git a/src/librustc/ty/outlives.rs b/src/librustc/ty/outlives.rs
index a544b2dd399..ab1b1b3857d 100644
--- a/src/librustc/ty/outlives.rs
+++ b/src/librustc/ty/outlives.rs
@@ -204,7 +204,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 
 fn push_region_constraints<'tcx>(out: &mut Vec<Component<'tcx>>, regions: Vec<ty::Region<'tcx>>) {
     for r in regions {
-        if !r.is_bound() {
+        if !r.is_late_bound() {
             out.push(Component::Region(r));
         }
     }
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 1b09baccadb..4faefc0fca9 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -790,6 +790,7 @@ impl<'tcx> serialize::UseSpecializedDecodable for Region<'tcx> {}
 
 #[derive(Copy, Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
 pub struct EarlyBoundRegion {
+    pub def_id: DefId,
     pub index: u32,
     pub name: Name,
 }
@@ -906,9 +907,8 @@ impl DebruijnIndex {
 
 /// Region utilities
 impl<'tcx> RegionKind<'tcx> {
-    pub fn is_bound(&self) -> bool {
+    pub fn is_late_bound(&self) -> bool {
         match *self {
-            ty::ReEarlyBound(..) => true,
             ty::ReLateBound(..) => true,
             _ => false,
         }
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index 06d09bd350a..c6c6a0e4700 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -688,9 +688,8 @@ impl<'a, 'gcx, 'tcx, W> TypeVisitor<'tcx> for TypeIdHasher<'a, 'gcx, 'tcx, W>
                 self.hash(db.depth);
                 self.hash(i);
             }
-            ty::ReEarlyBound(ty::EarlyBoundRegion { index, name }) => {
-                self.hash(index);
-                self.hash(name.as_str());
+            ty::ReEarlyBound(ty::EarlyBoundRegion { def_id, .. }) => {
+                self.def_id(def_id);
             }
             ty::ReLateBound(..) |
             ty::ReFree(..) |
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 307897c4eb4..27cc5faaf20 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -506,11 +506,7 @@ impl<'tcx> fmt::Debug for ty::ClosureUpvar<'tcx> {
 
 impl<'tcx> fmt::Debug for ty::ParameterEnvironment<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "ParameterEnvironment(\
-            free_substs={:?}, \
-            caller_bounds={:?})",
-            self.free_substs,
-            self.caller_bounds)
+        write!(f, "ParameterEnvironment({:?})", self.caller_bounds)
     }
 }
 
diff --git a/src/librustc_borrowck/borrowck/gather_loans/mod.rs b/src/librustc_borrowck/borrowck/gather_loans/mod.rs
index ca0e5dad65b..cbb6f7bce50 100644
--- a/src/librustc_borrowck/borrowck/gather_loans/mod.rs
+++ b/src/librustc_borrowck/borrowck/gather_loans/mod.rs
@@ -353,6 +353,10 @@ impl<'a, 'tcx> GatherLoanCtxt<'a, 'tcx> {
                 let loan_scope = match *loan_region {
                     ty::ReScope(scope) => scope,
 
+                    ty::ReEarlyBound(ref br) => {
+                        self.bccx.region_maps.early_free_extent(self.tcx(), br)
+                    }
+
                     ty::ReFree(ref fr) => {
                         self.bccx.region_maps.free_extent(self.tcx(), fr)
                     }
@@ -361,7 +365,6 @@ impl<'a, 'tcx> GatherLoanCtxt<'a, 'tcx> {
 
                     ty::ReEmpty |
                     ty::ReLateBound(..) |
-                    ty::ReEarlyBound(..) |
                     ty::ReVar(..) |
                     ty::ReSkolemized(..) |
                     ty::ReErased => {
diff --git a/src/librustc_borrowck/borrowck/mod.rs b/src/librustc_borrowck/borrowck/mod.rs
index 7eb73a87532..07fd966f570 100644
--- a/src/librustc_borrowck/borrowck/mod.rs
+++ b/src/librustc_borrowck/borrowck/mod.rs
@@ -513,6 +513,8 @@ impl<'a, 'tcx> BorrowckCtxt<'a, 'tcx> {
         match (&err.code, &err.cause) {
             (&err_out_of_scope(&ty::ReScope(_), &ty::ReStatic, _),
              &BorrowViolation(euv::ClosureCapture(span))) |
+            (&err_out_of_scope(&ty::ReScope(_), &ty::ReEarlyBound(..), _),
+             &BorrowViolation(euv::ClosureCapture(span))) |
             (&err_out_of_scope(&ty::ReScope(_), &ty::ReFree(..), _),
              &BorrowViolation(euv::ClosureCapture(span))) => {
                 return self.report_out_of_scope_escaping_closure_capture(&err, span);
diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index e8885626151..1de6749200f 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -296,8 +296,9 @@ impl<'a, 'gcx, 'tcx> Env<'a, 'gcx, 'tcx> {
     pub fn re_early_bound(&self, index: u32, name: &'static str) -> ty::Region<'tcx> {
         let name = Symbol::intern(name);
         self.infcx.tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
-            index: index,
-            name: name,
+            def_id: self.infcx.tcx.hir.local_def_id(ast::CRATE_NODE_ID),
+            index,
+            name,
         }))
     }
 
diff --git a/src/librustc_mir/shim.rs b/src/librustc_mir/shim.rs
index 587cc27f4b8..6f4480bf6dd 100644
--- a/src/librustc_mir/shim.rs
+++ b/src/librustc_mir/shim.rs
@@ -15,7 +15,7 @@ use rustc::middle::const_val::ConstVal;
 use rustc::mir::*;
 use rustc::mir::transform::MirSource;
 use rustc::ty::{self, Ty};
-use rustc::ty::subst::{Kind, Subst};
+use rustc::ty::subst::{Kind, Subst, Substs};
 use rustc::ty::maps::Providers;
 
 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
@@ -65,7 +65,6 @@ fn make_shim<'a, 'tcx>(tcx: ty::TyCtxt<'a, 'tcx, 'tcx>,
 
             build_call_shim(
                 tcx,
-                &param_env,
                 def_id,
                 adjustment,
                 CallKind::Indirect,
@@ -77,7 +76,6 @@ fn make_shim<'a, 'tcx>(tcx: ty::TyCtxt<'a, 'tcx, 'tcx>,
             // trans::mir knows to turn to an actual virtual call.
             build_call_shim(
                 tcx,
-                &param_env,
                 def_id,
                 Adjustment::Identity,
                 CallKind::Direct(def_id),
@@ -93,7 +91,6 @@ fn make_shim<'a, 'tcx>(tcx: ty::TyCtxt<'a, 'tcx, 'tcx>,
 
             build_call_shim(
                 tcx,
-                &param_env,
                 call_once,
                 Adjustment::RefMut,
                 CallKind::Direct(call_mut),
@@ -157,7 +154,7 @@ fn build_drop_shim<'a, 'tcx>(tcx: ty::TyCtxt<'a, 'tcx, 'tcx>,
     let substs = if let Some(ty) = ty {
         tcx.mk_substs(iter::once(Kind::from(ty)))
     } else {
-        param_env.free_substs
+        Substs::identity_for_item(tcx, def_id)
     };
     let fn_ty = tcx.type_of(def_id).subst(tcx, substs);
     let sig = tcx.erase_late_bound_regions(&fn_ty.fn_sig());
@@ -271,7 +268,6 @@ impl<'a, 'tcx> DropElaborator<'a, 'tcx> for DropShimElaborator<'a, 'tcx> {
 /// If `untuple_args` is a vec of types, the second argument of the
 /// function will be untupled as these types.
 fn build_call_shim<'a, 'tcx>(tcx: ty::TyCtxt<'a, 'tcx, 'tcx>,
-                             param_env: &ty::ParameterEnvironment<'tcx>,
                              def_id: DefId,
                              rcvr_adjustment: Adjustment,
                              call_kind: CallKind,
@@ -282,7 +278,7 @@ fn build_call_shim<'a, 'tcx>(tcx: ty::TyCtxt<'a, 'tcx, 'tcx>,
             call_kind={:?}, untuple_args={:?})",
            def_id, rcvr_adjustment, call_kind, untuple_args);
 
-    let fn_ty = tcx.type_of(def_id).subst(tcx, param_env.free_substs);
+    let fn_ty = tcx.type_of(def_id);
     let sig = tcx.erase_late_bound_regions(&fn_ty.fn_sig());
     let span = tcx.def_span(def_id);
 
@@ -324,9 +320,10 @@ fn build_call_shim<'a, 'tcx>(tcx: ty::TyCtxt<'a, 'tcx, 'tcx>,
         CallKind::Direct(def_id) => (
             Operand::Constant(box Constant {
                 span: span,
-                ty: tcx.type_of(def_id).subst(tcx, param_env.free_substs),
+                ty: tcx.type_of(def_id),
                 literal: Literal::Value {
-                    value: ConstVal::Function(def_id, param_env.free_substs),
+                    value: ConstVal::Function(def_id,
+                        Substs::identity_for_item(tcx, def_id)),
                 },
             }),
             vec![rcvr]
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index dfcc68bf390..9e8352fde80 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -41,12 +41,6 @@ pub trait AstConv<'gcx, 'tcx> {
     fn get_type_parameter_bounds(&self, span: Span, def_id: DefId)
                                  -> ty::GenericPredicates<'tcx>;
 
-    /// Return an (optional) substitution to convert bound type parameters that
-    /// are in scope into free ones. This function should only return Some
-    /// within a fn body.
-    /// See ParameterEnvironment::free_substs for more information.
-    fn get_free_substs(&self) -> Option<&Substs<'tcx>>;
-
     /// What lifetime should we use when a lifetime is omitted (and not elided)?
     fn re_infer(&self, span: Span, _def: Option<&ty::RegionParameterDef>)
                 -> Option<ty::Region<'tcx>>;
@@ -121,6 +115,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
             Some(&rl::Region::EarlyBound(index, id)) => {
                 let name = tcx.hir.name(id);
                 tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
+                    def_id: tcx.hir.local_def_id(id),
                     index: index,
                     name: name
                 }))
@@ -857,12 +852,6 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                     }
                 };
 
-                let trait_ref = if let Some(free_substs) = self.get_free_substs() {
-                    trait_ref.subst(tcx, free_substs)
-                } else {
-                    trait_ref
-                };
-
                 let candidates =
                     traits::supertraits(tcx, ty::Binder(trait_ref))
                     .filter(|r| self.trait_defines_associated_type_named(r.def_id(),
@@ -1020,12 +1009,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                 assert_eq!(opt_self_ty, None);
                 self.prohibit_type_params(&path.segments);
 
-                let ty = tcx.at(span).type_of(def_id);
-                if let Some(free_substs) = self.get_free_substs() {
-                    ty.subst(tcx, free_substs)
-                } else {
-                    ty
-                }
+                tcx.at(span).type_of(def_id)
             }
             Def::SelfTy(Some(_), None) => {
                 // Self in trait.
diff --git a/src/librustc_typeck/check/closure.rs b/src/librustc_typeck/check/closure.rs
index 9e4a7ed1ddc..4c3d5c8aaca 100644
--- a/src/librustc_typeck/check/closure.rs
+++ b/src/librustc_typeck/check/closure.rs
@@ -15,6 +15,7 @@ use super::{check_fn, Expectation, FnCtxt};
 use astconv::AstConv;
 use rustc::infer::type_variable::TypeVariableOrigin;
 use rustc::ty::{self, ToPolyTraitRef, Ty};
+use rustc::ty::subst::Substs;
 use std::cmp;
 use std::iter;
 use syntax::abi::Abi;
@@ -67,8 +68,10 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         // Create type variables (for now) to represent the transformed
         // types of upvars. These will be unified during the upvar
         // inference phase (`upvar.rs`).
+        let base_substs = Substs::identity_for_item(self.tcx,
+            self.tcx.closure_base_def_id(expr_def_id));
         let closure_type = self.tcx.mk_closure(expr_def_id,
-            self.parameter_environment.free_substs.extend_to(self.tcx, expr_def_id,
+            base_substs.extend_to(self.tcx, expr_def_id,
                 |_, _| span_bug!(expr.span, "closure has region param"),
                 |_, _| self.infcx.next_ty_var(TypeVariableOrigin::TransformedUpvar(expr.span))
             )
diff --git a/src/librustc_typeck/check/compare_method.rs b/src/librustc_typeck/check/compare_method.rs
index 7404222a4bd..d9f77e8f04f 100644
--- a/src/librustc_typeck/check/compare_method.rs
+++ b/src/librustc_typeck/check/compare_method.rs
@@ -170,13 +170,12 @@ fn compare_predicate_entailment<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     let impl_param_env = tcx.parameter_environment(impl_m.def_id);
 
     // Create mapping from impl to skolemized.
-    let impl_to_skol_substs = &impl_param_env.free_substs;
+    let impl_to_skol_substs = Substs::identity_for_item(tcx, impl_m.def_id);
 
     // Create mapping from trait to skolemized.
     let trait_to_skol_substs = impl_to_skol_substs.rebase_onto(tcx,
                                                                impl_m.container.id(),
-                                                               trait_to_impl_substs.subst(tcx,
-                                                                          impl_to_skol_substs));
+                                                               trait_to_impl_substs);
     debug!("compare_impl_method: trait_to_skol_substs={:?}",
            trait_to_skol_substs);
 
@@ -191,8 +190,7 @@ fn compare_predicate_entailment<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                        impl_m,
                                        &trait_m_generics,
                                        &impl_m_generics,
-                                       trait_to_skol_substs,
-                                       impl_to_skol_substs)?;
+                                       trait_to_skol_substs)?;
 
     // Create obligations for each predicate declared by the impl
     // definition in the context of the trait's parameter
@@ -200,7 +198,7 @@ fn compare_predicate_entailment<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     // however, because we want to replace all late-bound regions with
     // region variables.
     let impl_predicates = tcx.predicates_of(impl_m_predicates.parent.unwrap());
-    let mut hybrid_preds = impl_predicates.instantiate(tcx, impl_to_skol_substs);
+    let mut hybrid_preds = impl_predicates.instantiate_identity(tcx);
 
     debug!("compare_impl_method: impl_bounds={:?}", hybrid_preds);
 
@@ -274,8 +272,6 @@ fn compare_predicate_entailment<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                                             infer::HigherRankedType,
                                                             &m_sig(impl_m));
         let impl_sig =
-            impl_sig.subst(tcx, impl_to_skol_substs);
-        let impl_sig =
             inh.normalize_associated_types_in(impl_m_span,
                                               impl_m_node_id,
                                               &impl_sig);
@@ -370,8 +366,7 @@ fn check_region_bounds_on_impl_method<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                                 impl_m: &ty::AssociatedItem,
                                                 trait_generics: &ty::Generics,
                                                 impl_generics: &ty::Generics,
-                                                trait_to_skol_substs: &Substs<'tcx>,
-                                                impl_to_skol_substs: &Substs<'tcx>)
+                                                trait_to_skol_substs: &Substs<'tcx>)
                                                 -> Result<(), ErrorReported> {
     let trait_params = &trait_generics.regions[..];
     let impl_params = &impl_generics.regions[..];
@@ -379,12 +374,10 @@ fn check_region_bounds_on_impl_method<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     debug!("check_region_bounds_on_impl_method: \
             trait_generics={:?} \
             impl_generics={:?} \
-            trait_to_skol_substs={:?} \
-            impl_to_skol_substs={:?}",
+            trait_to_skol_substs={:?}",
            trait_generics,
            impl_generics,
-           trait_to_skol_substs,
-           impl_to_skol_substs);
+           trait_to_skol_substs);
 
     // Must have same number of early-bound lifetime parameters.
     // Unfortunately, if the user screws up the bounds, then this
@@ -739,22 +732,10 @@ pub fn compare_const_impl<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         // Create a parameter environment that represents the implementation's
         // method.
         let impl_c_node_id = tcx.hir.as_local_node_id(impl_c.def_id).unwrap();
-        let impl_param_env = tcx.parameter_environment(impl_c.def_id);
-
-        // Create mapping from impl to skolemized.
-        let impl_to_skol_substs = &impl_param_env.free_substs;
-
-        // Create mapping from trait to skolemized.
-        let trait_to_skol_substs = impl_to_skol_substs.rebase_onto(tcx,
-                                                                   impl_c.container.id(),
-                                                                   trait_to_impl_substs.subst(tcx,
-                                                                              impl_to_skol_substs));
-        debug!("compare_const_impl: trait_to_skol_substs={:?}",
-               trait_to_skol_substs);
 
         // Compute skolemized form of impl and trait const tys.
-        let impl_ty = tcx.type_of(impl_c.def_id).subst(tcx, impl_to_skol_substs);
-        let trait_ty = tcx.type_of(trait_c.def_id).subst(tcx, trait_to_skol_substs);
+        let impl_ty = tcx.type_of(impl_c.def_id);
+        let trait_ty = tcx.type_of(trait_c.def_id).subst(tcx, trait_to_impl_substs);
         let mut cause = ObligationCause::misc(impl_c_span, impl_c_node_id);
 
         // There is no "body" here, so just pass dummy id.
diff --git a/src/librustc_typeck/check/dropck.rs b/src/librustc_typeck/check/dropck.rs
index f6ffb3c0135..8e3329e2720 100644
--- a/src/librustc_typeck/check/dropck.rs
+++ b/src/librustc_typeck/check/dropck.rs
@@ -85,7 +85,6 @@ fn ensure_drop_params_and_item_params_correspond<'a, 'tcx>(
         let mut fulfillment_cx = traits::FulfillmentContext::new();
 
         let named_type = tcx.type_of(self_type_did);
-        let named_type = named_type.subst(tcx, &infcx.parameter_environment.free_substs);
 
         let drop_impl_span = tcx.def_span(drop_impl_did);
         let fresh_impl_substs =
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 201fc6ce7f2..3755dfd3f40 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -818,8 +818,6 @@ fn typeck_tables_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
             // Compute the fty from point of view of inside fn.
             let fn_sig =
-                fn_sig.subst(inh.tcx, &inh.parameter_environment.free_substs);
-            let fn_sig =
                 inh.liberate_late_bound_regions(def_id, &fn_sig);
             let fn_sig =
                 inh.normalize_associated_types_in(body.value.span, body_id.node_id, &fn_sig);
@@ -1555,10 +1553,6 @@ pub fn check_enum<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 impl<'a, 'gcx, 'tcx> AstConv<'gcx, 'tcx> for FnCtxt<'a, 'gcx, 'tcx> {
     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx }
 
-    fn get_free_substs(&self) -> Option<&Substs<'tcx>> {
-        Some(&self.parameter_environment.free_substs)
-    }
-
     fn get_type_parameter_bounds(&self, _: Span, def_id: DefId)
                                  -> ty::GenericPredicates<'tcx>
     {
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index bdaf3db8780..3da01764243 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -397,9 +397,11 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
             for implication in implied_bounds {
                 debug!("implication: {:?}", implication);
                 match implication {
-                    ImpliedBound::RegionSubRegion(&ty::ReFree(free_a),
+                    ImpliedBound::RegionSubRegion(r_a @ &ty::ReEarlyBound(_),
+                                                  &ty::ReVar(vid_b)) |
+                    ImpliedBound::RegionSubRegion(r_a @ &ty::ReFree(_),
                                                   &ty::ReVar(vid_b)) => {
-                        self.add_given(free_a, vid_b);
+                        self.add_given(r_a, vid_b);
                     }
                     ImpliedBound::RegionSubParam(r_a, param_b) => {
                         self.region_bound_pairs.push((r_a, GenericKind::Param(param_b)));
@@ -1664,7 +1666,7 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
         }
 
         let mut regions = ty.regions();
-        regions.retain(|r| !r.is_bound()); // ignore late-bound regions
+        regions.retain(|r| !r.is_late_bound()); // ignore late-bound regions
         bounds.push(VerifyBound::AllRegions(regions));
 
         // remove bounds that must hold, since they are not interesting
diff --git a/src/librustc_typeck/check/wfcheck.rs b/src/librustc_typeck/check/wfcheck.rs
index af7830a63a7..6895d738625 100644
--- a/src/librustc_typeck/check/wfcheck.rs
+++ b/src/librustc_typeck/check/wfcheck.rs
@@ -159,8 +159,6 @@ impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
                              sig_if_method: Option<&hir::MethodSig>) {
         let code = self.code.clone();
         self.for_id(item_id, span).with_fcx(|fcx, this| {
-            let free_substs = &fcx.parameter_environment.free_substs;
-
             let item = fcx.tcx.associated_item(fcx.tcx.hir.local_def_id(item_id));
 
             let (mut implied_bounds, self_ty) = match item.container {
@@ -172,14 +170,16 @@ impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
             match item.kind {
                 ty::AssociatedKind::Const => {
                     let ty = fcx.tcx.type_of(item.def_id);
-                    let ty = fcx.instantiate_type_scheme(span, free_substs, &ty);
+                    let ty = fcx.normalize_associated_types_in(span, &ty);
                     fcx.register_wf_obligation(ty, span, code.clone());
                 }
                 ty::AssociatedKind::Method => {
                     reject_shadowing_type_parameters(fcx.tcx, item.def_id);
                     let method_ty = fcx.tcx.type_of(item.def_id);
-                    let method_ty = fcx.instantiate_type_scheme(span, free_substs, &method_ty);
-                    let predicates = fcx.instantiate_bounds(span, item.def_id, free_substs);
+                    let method_ty = fcx.normalize_associated_types_in(span, &method_ty);
+                    let predicates = fcx.tcx.predicates_of(item.def_id)
+                        .instantiate_identity(fcx.tcx);
+                    let predicates = fcx.normalize_associated_types_in(span, &predicates);
                     let sig = method_ty.fn_sig();
                     this.check_fn_or_method(fcx, span, sig, &predicates,
                                             item.def_id, &mut implied_bounds);
@@ -189,7 +189,7 @@ impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
                 ty::AssociatedKind::Type => {
                     if item.defaultness.has_value() {
                         let ty = fcx.tcx.type_of(item.def_id);
-                        let ty = fcx.instantiate_type_scheme(span, free_substs, &ty);
+                        let ty = fcx.normalize_associated_types_in(span, &ty);
                         fcx.register_wf_obligation(ty, span, code.clone());
                     }
                 }
@@ -239,9 +239,9 @@ impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
                 }
             }
 
-            let free_substs = &fcx.parameter_environment.free_substs;
             let def_id = fcx.tcx.hir.local_def_id(item.id);
-            let predicates = fcx.instantiate_bounds(item.span, def_id, free_substs);
+            let predicates = fcx.tcx.predicates_of(def_id).instantiate_identity(fcx.tcx);
+            let predicates = fcx.normalize_associated_types_in(item.span, &predicates);
             this.check_where_clauses(fcx, item.span, &predicates);
 
             vec![] // no implied bounds in a struct def'n
@@ -317,8 +317,8 @@ impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
         }
 
         self.for_item(item).with_fcx(|fcx, this| {
-            let free_substs = &fcx.parameter_environment.free_substs;
-            let predicates = fcx.instantiate_bounds(item.span, trait_def_id, free_substs);
+            let predicates = fcx.tcx.predicates_of(trait_def_id).instantiate_identity(fcx.tcx);
+            let predicates = fcx.normalize_associated_types_in(item.span, &predicates);
             this.check_where_clauses(fcx, item.span, &predicates);
             vec![]
         });
@@ -326,13 +326,13 @@ impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
 
     fn check_item_fn(&mut self, item: &hir::Item) {
         self.for_item(item).with_fcx(|fcx, this| {
-            let free_substs = &fcx.parameter_environment.free_substs;
             let def_id = fcx.tcx.hir.local_def_id(item.id);
             let ty = fcx.tcx.type_of(def_id);
-            let item_ty = fcx.instantiate_type_scheme(item.span, free_substs, &ty);
+            let item_ty = fcx.normalize_associated_types_in(item.span, &ty);
             let sig = item_ty.fn_sig();
 
-            let predicates = fcx.instantiate_bounds(item.span, def_id, free_substs);
+            let predicates = fcx.tcx.predicates_of(def_id).instantiate_identity(fcx.tcx);
+            let predicates = fcx.normalize_associated_types_in(item.span, &predicates);
 
             let mut implied_bounds = vec![];
             this.check_fn_or_method(fcx, item.span, sig, &predicates,
@@ -348,10 +348,7 @@ impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
 
         self.for_item(item).with_fcx(|fcx, this| {
             let ty = fcx.tcx.type_of(fcx.tcx.hir.local_def_id(item.id));
-            let item_ty = fcx.instantiate_type_scheme(item.span,
-                                                      &fcx.parameter_environment
-                                                          .free_substs,
-                                                      &ty);
+            let item_ty = fcx.normalize_associated_types_in(item.span, &ty);
 
             fcx.register_wf_obligation(item_ty, item.span, this.code.clone());
 
@@ -367,15 +364,14 @@ impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
         debug!("check_impl: {:?}", item);
 
         self.for_item(item).with_fcx(|fcx, this| {
-            let free_substs = &fcx.parameter_environment.free_substs;
             let item_def_id = fcx.tcx.hir.local_def_id(item.id);
 
             match *ast_trait_ref {
                 Some(ref ast_trait_ref) => {
                     let trait_ref = fcx.tcx.impl_trait_ref(item_def_id).unwrap();
                     let trait_ref =
-                        fcx.instantiate_type_scheme(
-                            ast_trait_ref.path.span, free_substs, &trait_ref);
+                        fcx.normalize_associated_types_in(
+                            ast_trait_ref.path.span, &trait_ref);
                     let obligations =
                         ty::wf::trait_obligations(fcx,
                                                   fcx.body_id,
@@ -387,12 +383,13 @@ impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
                 }
                 None => {
                     let self_ty = fcx.tcx.type_of(item_def_id);
-                    let self_ty = fcx.instantiate_type_scheme(item.span, free_substs, &self_ty);
+                    let self_ty = fcx.normalize_associated_types_in(item.span, &self_ty);
                     fcx.register_wf_obligation(self_ty, ast_self_ty.span, this.code.clone());
                 }
             }
 
-            let predicates = fcx.instantiate_bounds(item.span, item_def_id, free_substs);
+            let predicates = fcx.tcx.predicates_of(item_def_id).instantiate_identity(fcx.tcx);
+            let predicates = fcx.normalize_associated_types_in(item.span, &predicates);
             this.check_where_clauses(fcx, item.span, &predicates);
 
             fcx.impl_implied_bounds(item_def_id, item.span)
@@ -425,8 +422,7 @@ impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
                                       def_id: DefId,
                                       implied_bounds: &mut Vec<Ty<'tcx>>)
     {
-        let free_substs = &fcx.parameter_environment.free_substs;
-        let sig = fcx.instantiate_type_scheme(span, free_substs, &sig);
+        let sig = fcx.normalize_associated_types_in(span, &sig);
         let sig = fcx.liberate_late_bound_regions(def_id, &sig);
 
         for input_ty in sig.inputs() {
@@ -459,9 +455,8 @@ impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
 
         let span = method_sig.decl.inputs[0].span;
 
-        let free_substs = &fcx.parameter_environment.free_substs;
         let method_ty = fcx.tcx.type_of(method.def_id);
-        let fty = fcx.instantiate_type_scheme(span, free_substs, &method_ty);
+        let fty = fcx.normalize_associated_types_in(span, &method_ty);
         let sig = fcx.liberate_late_bound_regions(method.def_id, &fty.fn_sig());
 
         debug!("check_method_receiver: sig={:?}", sig);
@@ -477,7 +472,7 @@ impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
             }
             ExplicitSelf::ByBox => fcx.tcx.mk_box(self_ty)
         };
-        let rcvr_ty = fcx.instantiate_type_scheme(span, free_substs, &rcvr_ty);
+        let rcvr_ty = fcx.normalize_associated_types_in(span, &rcvr_ty);
         let rcvr_ty = fcx.liberate_late_bound_regions(method.def_id,
                                                       &ty::Binder(rcvr_ty));
 
@@ -624,10 +619,8 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
             struct_def.fields().iter()
             .map(|field| {
                 let field_ty = self.tcx.type_of(self.tcx.hir.local_def_id(field.id));
-                let field_ty = self.instantiate_type_scheme(field.span,
-                                                            &self.parameter_environment
-                                                                 .free_substs,
-                                                            &field_ty);
+                let field_ty = self.normalize_associated_types_in(field.span,
+                                                                  &field_ty);
                 AdtField { ty: field_ty, span: field.span }
             })
             .collect();
@@ -641,19 +634,18 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
     }
 
     fn impl_implied_bounds(&self, impl_def_id: DefId, span: Span) -> Vec<Ty<'tcx>> {
-        let free_substs = &self.parameter_environment.free_substs;
         match self.tcx.impl_trait_ref(impl_def_id) {
             Some(ref trait_ref) => {
                 // Trait impl: take implied bounds from all types that
                 // appear in the trait reference.
-                let trait_ref = self.instantiate_type_scheme(span, free_substs, trait_ref);
+                let trait_ref = self.normalize_associated_types_in(span, trait_ref);
                 trait_ref.substs.types().collect()
             }
 
             None => {
                 // Inherent impl: take implied bounds from the self type.
                 let self_ty = self.tcx.type_of(impl_def_id);
-                let self_ty = self.instantiate_type_scheme(span, free_substs, &self_ty);
+                let self_ty = self.normalize_associated_types_in(span, &self_ty);
                 vec![self_ty]
             }
         }
diff --git a/src/librustc_typeck/check/writeback.rs b/src/librustc_typeck/check/writeback.rs
index 49440037af5..b43e2423757 100644
--- a/src/librustc_typeck/check/writeback.rs
+++ b/src/librustc_typeck/check/writeback.rs
@@ -19,7 +19,7 @@ use rustc::infer::{InferCtxt};
 use rustc::ty::{self, Ty, TyCtxt, MethodCall, MethodCallee};
 use rustc::ty::adjustment;
 use rustc::ty::fold::{TypeFolder,TypeFoldable};
-use rustc::util::nodemap::{DefIdMap, DefIdSet};
+use rustc::util::nodemap::DefIdSet;
 use syntax::ast;
 use syntax_pos::Span;
 use std::mem;
@@ -71,55 +71,17 @@ struct WritebackCx<'cx, 'gcx: 'cx+'tcx, 'tcx: 'cx> {
 
     tables: ty::TypeckTables<'gcx>,
 
-    // Mapping from free regions of the function to the
-    // early-bound versions of them, visible from the
-    // outside of the function. This is needed by, and
-    // only populated if there are any `impl Trait`.
-    free_to_bound_regions: DefIdMap<ty::Region<'gcx>>,
-
     body: &'gcx hir::Body,
 }
 
 impl<'cx, 'gcx, 'tcx> WritebackCx<'cx, 'gcx, 'tcx> {
     fn new(fcx: &'cx FnCtxt<'cx, 'gcx, 'tcx>, body: &'gcx hir::Body)
         -> WritebackCx<'cx, 'gcx, 'tcx> {
-        let mut wbcx = WritebackCx {
+        WritebackCx {
             fcx: fcx,
             tables: ty::TypeckTables::empty(),
-            free_to_bound_regions: DefIdMap(),
             body: body
-        };
-
-        // Only build the reverse mapping if `impl Trait` is used.
-        if fcx.anon_types.borrow().is_empty() {
-            return wbcx;
         }
-
-        let gcx = fcx.tcx.global_tcx();
-        let free_substs = fcx.parameter_environment.free_substs;
-        for (i, k) in free_substs.iter().enumerate() {
-            let r = if let Some(r) = k.as_region() {
-                r
-            } else {
-                continue;
-            };
-            match *r {
-                ty::ReFree(ty::FreeRegion {
-                    bound_region: ty::BoundRegion::BrNamed(def_id, name), ..
-                }) => {
-                    let bound_region = gcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
-                        index: i as u32,
-                        name: name,
-                    }));
-                    wbcx.free_to_bound_regions.insert(def_id, bound_region);
-                }
-                _ => {
-                    bug!("{:?} is not a free region for an early-bound lifetime", r);
-                }
-            }
-        }
-
-        wbcx
     }
 
     fn tcx(&self) -> TyCtxt<'cx, 'gcx, 'tcx> {
@@ -285,22 +247,16 @@ impl<'cx, 'gcx, 'tcx> WritebackCx<'cx, 'gcx, 'tcx> {
             let inside_ty = self.resolve(&concrete_ty, &node_id);
 
             // Convert the type from the function into a type valid outside
-            // the function, by replacing free regions with early-bound ones.
+            // the function, by replacing invalid regions with 'static,
+            // after producing an error for each of them.
             let outside_ty = gcx.fold_regions(&inside_ty, &mut false, |r, _| {
                 match *r {
-                    // 'static is valid everywhere.
-                    ty::ReStatic => gcx.types.re_static,
-                    ty::ReEmpty => gcx.types.re_empty,
-
-                    // Free regions that come from early-bound regions are valid.
-                    ty::ReFree(ty::FreeRegion {
-                        bound_region: ty::BoundRegion::BrNamed(def_id, ..), ..
-                    }) if self.free_to_bound_regions.contains_key(&def_id) => {
-                        self.free_to_bound_regions[&def_id]
-                    }
+                    // 'static and early-bound regions are valid.
+                    ty::ReStatic |
+                    ty::ReEarlyBound(_) |
+                    ty::ReEmpty => r,
 
                     ty::ReFree(_) |
-                    ty::ReEarlyBound(_) |
                     ty::ReLateBound(..) |
                     ty::ReScope(_) |
                     ty::ReSkolemized(..) => {
diff --git a/src/librustc_typeck/coherence/builtin.rs b/src/librustc_typeck/coherence/builtin.rs
index 47642798617..d40a68e6056 100644
--- a/src/librustc_typeck/coherence/builtin.rs
+++ b/src/librustc_typeck/coherence/builtin.rs
@@ -19,7 +19,6 @@ use rustc::traits::{self, ObligationCause, Reveal};
 use rustc::ty::{self, Ty, TyCtxt};
 use rustc::ty::TypeFoldable;
 use rustc::ty::adjustment::CoerceUnsizedInfo;
-use rustc::ty::subst::Subst;
 use rustc::ty::util::CopyImplementationError;
 use rustc::infer;
 
@@ -107,7 +106,6 @@ fn visit_implementation_of_copy<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     let span = tcx.hir.span(impl_node_id);
     let param_env = tcx.parameter_environment(impl_did);
-    let self_type = self_type.subst(tcx, &param_env.free_substs);
     assert!(!self_type.has_escaping_regions());
 
     debug!("visit_implementation_of_copy: self_type={:?} (free)",
@@ -202,8 +200,6 @@ pub fn coerce_unsized_info<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     let span = tcx.hir.span(impl_node_id);
     let param_env = tcx.parameter_environment(impl_did);
-    let source = source.subst(tcx, &param_env.free_substs);
-    let target = target.subst(tcx, &param_env.free_substs);
     assert!(!source.has_escaping_regions());
 
     let err_info = CoerceUnsizedInfo { custom_kind: None };
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index ec200241ee6..7c6c70024ce 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -205,10 +205,6 @@ impl<'a, 'tcx> AstConv<'tcx, 'tcx> for ItemCtxt<'a, 'tcx> {
         self.tcx.at(span).type_param_predicates((self.item_def_id, def_id))
     }
 
-    fn get_free_substs(&self) -> Option<&Substs<'tcx>> {
-        None
-    }
-
     fn re_infer(&self, _span: Span, _def: Option<&ty::RegionParameterDef>)
                 -> Option<ty::Region<'tcx>> {
         None
@@ -1299,6 +1295,7 @@ fn predicates_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     let mut index = parent_count + has_own_self as u32;
     for param in early_bound_lifetimes_from_generics(tcx, ast_generics) {
         let region = tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
+            def_id: tcx.hir.local_def_id(param.lifetime.id),
             index: index,
             name: param.lifetime.name
         }));
diff --git a/src/test/compile-fail/issue-27942.rs b/src/test/compile-fail/issue-27942.rs
index 595e4bfb0d7..22e7de3838d 100644
--- a/src/test/compile-fail/issue-27942.rs
+++ b/src/test/compile-fail/issue-27942.rs
@@ -11,17 +11,18 @@
 pub trait Resources<'a> {}
 
 pub trait Buffer<'a, R: Resources<'a>> {
+    //~^ NOTE the lifetime 'a as defined on the trait at 13:0...
+    //~| NOTE ...does not necessarily outlive the lifetime 'a as defined on the trait
+
     fn select(&self) -> BufferViewHandle<R>;
     //~^ ERROR mismatched types
     //~| lifetime mismatch
     //~| NOTE expected type `Resources<'_>`
-    //~| NOTE the lifetime 'a as defined on the method body at 14:4...
     //~| NOTE ...does not necessarily outlive the anonymous lifetime #1 defined on the method body
     //~| ERROR mismatched types
     //~| lifetime mismatch
     //~| NOTE expected type `Resources<'_>`
-    //~| NOTE the anonymous lifetime #1 defined on the method body at 14:4...
-    //~| NOTE ...does not necessarily outlive the lifetime 'a as defined on the method body
+    //~| NOTE the anonymous lifetime #1 defined on the method body at 17:4...
 }
 
 pub struct BufferViewHandle<'a, R: 'a+Resources<'a>>(&'a R);
diff --git a/src/test/compile-fail/issue-37884.rs b/src/test/compile-fail/issue-37884.rs
index 28ce79ab5aa..6313293bf2b 100644
--- a/src/test/compile-fail/issue-37884.rs
+++ b/src/test/compile-fail/issue-37884.rs
@@ -11,13 +11,14 @@
 struct RepeatMut<'a, T>(T, &'a ());
 
 impl<'a, T: 'a> Iterator for RepeatMut<'a, T> {
+    //~^ NOTE ...does not necessarily outlive the lifetime 'a as defined on the impl
+
     type Item = &'a mut T;
     fn next(&'a mut self) -> Option<Self::Item>
     //~^ ERROR method not compatible with trait
     //~| lifetime mismatch
     //~| NOTE expected type `fn(&mut RepeatMut<'a, T>) -> std::option::Option<&mut T>`
     //~| NOTE the anonymous lifetime #1 defined on the method body
-    //~| NOTE ...does not necessarily outlive the lifetime 'a as defined on the method body
     {
         Some(&mut self.0)
     }