Skip useless recursion in freshening and late-bound-region substitutio

Before:
581.72user 4.75system 7:42.74elapsed 126%CPU (0avgtext+0avgdata 1176224maxresident)k
llvm took 359.183

After:
550.63user 5.09system 7:20.28elapsed 126%CPU (0avgtext+0avgdata 1165516maxresident)k
llvm took 354.801

6 files changed, 129 insertions, 76 deletions

diff --git a/src/librustc/middle/infer/freshen.rs b/src/librustc/middle/infer/freshen.rs
index 111cf68726c..8783577945c 100644
--- a/src/librustc/middle/infer/freshen.rs
+++ b/src/librustc/middle/infer/freshen.rs
@@ -104,6 +104,10 @@ impl<'a, 'tcx> TypeFolder<'tcx> for TypeFreshener<'a, 'tcx> {
     }
 
     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
+        if !ty::type_needs_infer(t) && !ty::type_has_erasable_regions(t) {
+            return t;
+        }
+
         let tcx = self.infcx.tcx;
 
         match t.sty {
diff --git a/src/librustc/middle/infer/higher_ranked/mod.rs b/src/librustc/middle/infer/higher_ranked/mod.rs
index b0940aa7ec0..7fd4a14b25b 100644
--- a/src/librustc/middle/infer/higher_ranked/mod.rs
+++ b/src/librustc/middle/infer/higher_ranked/mod.rs
@@ -530,7 +530,7 @@ pub fn skolemize_late_bound_regions<'a,'tcx,T>(infcx: &InferCtxt<'a,'tcx>,
      * details.
      */
 
-    let (result, map) = ty::replace_late_bound_regions(infcx.tcx, binder, |br| {
+    let (result, map) = ty_fold::replace_late_bound_regions(infcx.tcx, binder, |br| {
         infcx.region_vars.new_skolemized(br, &snapshot.region_vars_snapshot)
     });
 
diff --git a/src/librustc/middle/infer/mod.rs b/src/librustc/middle/infer/mod.rs
index b802f46e285..b3c4dd68dba 100644
--- a/src/librustc/middle/infer/mod.rs
+++ b/src/librustc/middle/infer/mod.rs
@@ -26,9 +26,8 @@ use middle::free_region::FreeRegionMap;
 use middle::subst;
 use middle::subst::Substs;
 use middle::ty::{TyVid, IntVid, FloatVid, RegionVid, UnconstrainedNumeric};
-use middle::ty::replace_late_bound_regions;
 use middle::ty::{self, Ty};
-use middle::ty_fold::{TypeFolder, TypeFoldable};
+use middle::ty_fold::{self, TypeFolder, TypeFoldable};
 use middle::ty_relate::{Relate, RelateResult, TypeRelation};
 use rustc_data_structures::unify::{self, UnificationTable};
 use std::cell::{RefCell};
@@ -1038,7 +1037,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         -> (T, FnvHashMap<ty::BoundRegion,ty::Region>)
         where T : TypeFoldable<'tcx> + Repr<'tcx>
     {
-        ty::replace_late_bound_regions(
+        ty_fold::replace_late_bound_regions(
             self.tcx,
             value,
             |br| self.next_region_var(LateBoundRegion(span, br, lbrct)))
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 0b014c9e6a2..b5ef06f9a9e 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -806,29 +806,31 @@ impl<'tcx> ctxt<'tcx> {
 // recursing over the type itself.
 bitflags! {
     flags TypeFlags: u32 {
-        const HAS_PARAMS        = 1 << 0,
-        const HAS_SELF          = 1 << 1,
-        const HAS_TY_INFER      = 1 << 2,
-        const HAS_RE_INFER      = 1 << 3,
-        const HAS_RE_LATE_BOUND = 1 << 4,
-        const HAS_REGIONS       = 1 << 5,
-        const HAS_TY_ERR        = 1 << 6,
-        const HAS_PROJECTION    = 1 << 7,
-        const HAS_TY_CLOSURE    = 1 << 8,
-        const NEEDS_SUBST       = TypeFlags::HAS_PARAMS.bits |
-                                  TypeFlags::HAS_SELF.bits |
-                                  TypeFlags::HAS_REGIONS.bits,
+        const HAS_PARAMS         = 1 << 0,
+        const HAS_SELF           = 1 << 1,
+        const HAS_TY_INFER       = 1 << 2,
+        const HAS_RE_INFER       = 1 << 3,
+        const HAS_RE_EARLY_BOUND = 1 << 4,
+        const HAS_FREE_REGIONS   = 1 << 5,
+        const HAS_TY_ERR         = 1 << 6,
+        const HAS_PROJECTION     = 1 << 7,
+        const HAS_TY_CLOSURE     = 1 << 8,
+        const NEEDS_SUBST        = TypeFlags::HAS_PARAMS.bits |
+                                   TypeFlags::HAS_SELF.bits |
+                                   TypeFlags::HAS_RE_EARLY_BOUND.bits,
 
         // Flags representing the nominal content of a type,
-        // computed by FlagsComputetion
+        // computed by FlagsComputation. If you add a new nominal
+        // flag, it should be added here too.
         const NOMINAL_FLAGS     = TypeFlags::HAS_PARAMS.bits |
                                   TypeFlags::HAS_SELF.bits |
                                   TypeFlags::HAS_TY_INFER.bits |
                                   TypeFlags::HAS_RE_INFER.bits |
-                                  TypeFlags::HAS_RE_LATE_BOUND.bits |
-                                  TypeFlags::HAS_REGIONS.bits |
+                                  TypeFlags::HAS_RE_EARLY_BOUND.bits |
+                                  TypeFlags::HAS_FREE_REGIONS.bits |
                                   TypeFlags::HAS_TY_ERR.bits |
-                                  TypeFlags::HAS_PROJECTION.bits,
+                                  TypeFlags::HAS_PROJECTION.bits |
+                                  TypeFlags::HAS_TY_CLOSURE.bits,
 
         // Caches for type_is_sized, type_moves_by_default
         const SIZEDNESS_CACHED  = 1 << 16,
@@ -990,8 +992,10 @@ pub fn type_has_ty_closure(ty: Ty) -> bool {
     ty.flags.get().intersects(TypeFlags::HAS_TY_CLOSURE)
 }
 
-pub fn type_has_late_bound_regions(ty: Ty) -> bool {
-    ty.flags.get().intersects(TypeFlags::HAS_RE_LATE_BOUND)
+pub fn type_has_erasable_regions(ty: Ty) -> bool {
+    ty.flags.get().intersects(TypeFlags::HAS_RE_EARLY_BOUND |
+                              TypeFlags::HAS_RE_INFER |
+                              TypeFlags::HAS_FREE_REGIONS)
 }
 
 /// An "escaping region" is a bound region whose binder is not part of `t`.
@@ -2987,7 +2991,7 @@ impl FlagComputation {
                 for projection_bound in &bounds.projection_bounds {
                     let mut proj_computation = FlagComputation::new();
                     proj_computation.add_projection_predicate(&projection_bound.0);
-                    computation.add_bound_computation(&proj_computation);
+                    self.add_bound_computation(&proj_computation);
                 }
                 self.add_bound_computation(&computation);
 
@@ -3041,14 +3045,12 @@ impl FlagComputation {
     }
 
     fn add_region(&mut self, r: Region) {
-        self.add_flags(TypeFlags::HAS_REGIONS);
         match r {
             ty::ReInfer(_) => { self.add_flags(TypeFlags::HAS_RE_INFER); }
-            ty::ReLateBound(debruijn, _) => {
-                self.add_flags(TypeFlags::HAS_RE_LATE_BOUND);
-                self.add_depth(debruijn.depth);
-            }
-            _ => { }
+            ty::ReLateBound(debruijn, _) => { self.add_depth(debruijn.depth); }
+            ty::ReEarlyBound(..) => { self.add_flags(TypeFlags::HAS_RE_EARLY_BOUND); }
+            ty::ReStatic => {}
+            _ => { self.add_flags(TypeFlags::HAS_FREE_REGIONS); }
         }
     }
 
@@ -6994,7 +6996,7 @@ pub fn liberate_late_bound_regions<'tcx, T>(
     -> T
     where T : TypeFoldable<'tcx> + Repr<'tcx>
 {
-    replace_late_bound_regions(
+    ty_fold::replace_late_bound_regions(
         tcx, value,
         |br| ty::ReFree(ty::FreeRegion{scope: all_outlive_scope, bound_region: br})).0
 }
@@ -7005,7 +7007,7 @@ pub fn count_late_bound_regions<'tcx, T>(
     -> usize
     where T : TypeFoldable<'tcx> + Repr<'tcx>
 {
-    let (_, skol_map) = replace_late_bound_regions(tcx, value, |_| ty::ReStatic);
+    let (_, skol_map) = ty_fold::replace_late_bound_regions(tcx, value, |_| ty::ReStatic);
     skol_map.len()
 }
 
@@ -7063,7 +7065,7 @@ pub fn erase_late_bound_regions<'tcx, T>(
     -> T
     where T : TypeFoldable<'tcx> + Repr<'tcx>
 {
-    replace_late_bound_regions(tcx, value, |_| ty::ReStatic).0
+    ty_fold::replace_late_bound_regions(tcx, value, |_| ty::ReStatic).0
 }
 
 /// Rewrite any late-bound regions so that they are anonymous.  Region numbers are
@@ -7081,53 +7083,12 @@ pub fn anonymize_late_bound_regions<'tcx, T>(
     where T : TypeFoldable<'tcx> + Repr<'tcx>,
 {
     let mut counter = 0;
-    ty::Binder(replace_late_bound_regions(tcx, sig, |_| {
+    ty::Binder(ty_fold::replace_late_bound_regions(tcx, sig, |_| {
         counter += 1;
         ReLateBound(ty::DebruijnIndex::new(1), BrAnon(counter))
     }).0)
 }
 
-/// Replaces the late-bound-regions in `value` that are bound by `value`.
-pub fn replace_late_bound_regions<'tcx, T, F>(
-    tcx: &ty::ctxt<'tcx>,
-    binder: &Binder<T>,
-    mut mapf: F)
-    -> (T, FnvHashMap<ty::BoundRegion,ty::Region>)
-    where T : TypeFoldable<'tcx> + Repr<'tcx>,
-          F : FnMut(BoundRegion) -> ty::Region,
-{
-    debug!("replace_late_bound_regions({})", binder.repr(tcx));
-
-    let mut map = FnvHashMap();
-
-    // Note: fold the field `0`, not the binder, so that late-bound
-    // regions bound by `binder` are considered free.
-    let value = ty_fold::fold_regions(tcx, &binder.0, |region, current_depth| {
-        debug!("region={}", region.repr(tcx));
-        match region {
-            ty::ReLateBound(debruijn, br) if debruijn.depth == current_depth => {
-                let region = *map.entry(br).or_insert_with(|| mapf(br));
-
-                if let ty::ReLateBound(debruijn1, br) = region {
-                    // If the callback returns a late-bound region,
-                    // that region should always use depth 1. Then we
-                    // adjust it to the correct depth.
-                    assert_eq!(debruijn1.depth, 1);
-                    ty::ReLateBound(debruijn, br)
-                } else {
-                    region
-                }
-            }
-            _ => {
-                region
-            }
-        }
-    });
-
-    debug!("resulting map: {:?} value: {:?}", map, value.repr(tcx));
-    (value, map)
-}
-
 impl DebruijnIndex {
     pub fn new(depth: u32) -> DebruijnIndex {
         assert!(depth > 0);
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
index 6f098a53238..884fc9571ce 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -42,6 +42,7 @@ use std::rc::Rc;
 use syntax::abi;
 use syntax::ast;
 use syntax::owned_slice::OwnedSlice;
+use util::nodemap::FnvHashMap;
 use util::ppaux::Repr;
 
 ///////////////////////////////////////////////////////////////////////////
@@ -842,6 +843,86 @@ impl<'a, 'tcx> TypeFolder<'tcx> for RegionFolder<'a, 'tcx>
 }
 
 ///////////////////////////////////////////////////////////////////////////
+// Late-bound region replacer
+
+// Replaces the escaping regions in a type.
+
+struct RegionReplacer<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
+    current_depth: u32,
+    fld_r: &'a mut (FnMut(ty::BoundRegion) -> ty::Region + 'a),
+    map: FnvHashMap<ty::BoundRegion, ty::Region>
+}
+
+impl<'a, 'tcx> RegionReplacer<'a, 'tcx> {
+    fn new<F>(tcx: &'a ty::ctxt<'tcx>, fld_r: &'a mut F) -> RegionReplacer<'a, 'tcx>
+        where F : FnMut(ty::BoundRegion) -> ty::Region
+    {
+        RegionReplacer {
+            tcx: tcx,
+            current_depth: 1,
+            fld_r: fld_r,
+            map: FnvHashMap()
+        }
+    }
+}
+
+pub fn replace_late_bound_regions<'tcx,T,F>(tcx: &ty::ctxt<'tcx>,
+                                            value: &ty::Binder<T>,
+                                            mut f: F)
+                                            -> (T, FnvHashMap<ty::BoundRegion, ty::Region>)
+    where F : FnMut(ty::BoundRegion) -> ty::Region,
+          T : TypeFoldable<'tcx> + Repr<'tcx>,
+{
+    debug!("replace_late_bound_regions({})", value.repr(tcx));
+    let mut replacer = RegionReplacer::new(tcx, &mut f);
+    let result = value.skip_binder().fold_with(&mut replacer);
+    (result, replacer.map)
+}
+
+impl<'a, 'tcx> TypeFolder<'tcx> for RegionReplacer<'a, 'tcx>
+{
+    fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx }
+
+    fn enter_region_binder(&mut self) {
+        self.current_depth += 1;
+    }
+
+    fn exit_region_binder(&mut self) {
+        self.current_depth -= 1;
+    }
+
+    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
+        if !ty::type_escapes_depth(t, self.current_depth-1) {
+            return t;
+        }
+
+        super_fold_ty(self, t)
+    }
+
+    fn fold_region(&mut self, r: ty::Region) -> ty::Region {
+        match r {
+            ty::ReLateBound(debruijn, br) if debruijn.depth == self.current_depth => {
+                debug!("RegionReplacer.fold_region({}) folding region (current_depth={})",
+                       r.repr(self.tcx()), self.current_depth);
+                let fld_r = &mut self.fld_r;
+                let region = *self.map.entry(br).or_insert_with(|| fld_r(br));
+                if let ty::ReLateBound(debruijn1, br) = region {
+                    // If the callback returns a late-bound region,
+                    // that region should always use depth 1. Then we
+                    // adjust it to the correct depth.
+                    assert_eq!(debruijn1.depth, 1);
+                    ty::ReLateBound(debruijn, br)
+                } else {
+                    region
+                }
+            }
+            r => r
+        }
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
 // Region eraser
 //
 // Replaces all free regions with 'static. Useful in contexts, such as
@@ -861,6 +942,14 @@ pub fn erase_regions<'tcx, T: TypeFoldable<'tcx>>(tcx: &ty::ctxt<'tcx>, t: T) ->
 impl<'a, 'tcx> TypeFolder<'tcx> for RegionEraser<'a, 'tcx> {
     fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx }
 
+    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
+        if !ty::type_has_erasable_regions(t) {
+            return t;
+        }
+
+        super_fold_ty(self, t)
+    }
+
     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
         // because whether or not a region is bound affects subtyping,
         // we can't erase the bound/free distinction, but we can
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index acbd09f671b..3532bcdb279 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -24,7 +24,7 @@ use middle::ty::{ty_param, ty_ptr, ty_rptr, ty_tup};
 use middle::ty::ty_closure;
 use middle::ty::{ty_uniq, ty_trait, ty_int, ty_uint, ty_infer};
 use middle::ty;
-use middle::ty_fold::TypeFoldable;
+use middle::ty_fold::{self, TypeFoldable};
 
 use std::collections::HashMap;
 use std::collections::hash_state::HashState;
@@ -1301,7 +1301,7 @@ impl<'tcx, T> UserString<'tcx> for ty::Binder<T>
         // the output. We'll probably want to tweak this over time to
         // decide just how much information to give.
         let mut names = Vec::new();
-        let (unbound_value, _) = ty::replace_late_bound_regions(tcx, self, |br| {
+        let (unbound_value, _) = ty_fold::replace_late_bound_regions(tcx, self, |br| {
             ty::ReLateBound(ty::DebruijnIndex::new(1), match br {
                 ty::BrNamed(_, name) => {
                     names.push(token::get_name(name));