introduce liveness constraints into NLL code

And do a bunch of gratuitious refactoring that I did not bother to
separate into nice commits.

7 files changed, 395 insertions, 211 deletions

diff --git a/src/librustc_data_structures/indexed_set.rs b/src/librustc_data_structures/indexed_set.rs
index c790463e47a..c5ffb003399 100644
--- a/src/librustc_data_structures/indexed_set.rs
+++ b/src/librustc_data_structures/indexed_set.rs
@@ -53,11 +53,19 @@ pub struct IdxSet<T: Idx> {
 }
 
 impl<T: Idx> fmt::Debug for IdxSetBuf<T> {
-    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { self.bits.fmt(w) }
+    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
+        w.debug_list()
+         .entries(self.iter())
+         .finish()
+    }
 }
 
 impl<T: Idx> fmt::Debug for IdxSet<T> {
-    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { self.bits.fmt(w) }
+    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
+        w.debug_list()
+         .entries(self.iter())
+         .finish()
+    }
 }
 
 impl<T: Idx> IdxSetBuf<T> {
diff --git a/src/librustc_mir/lib.rs b/src/librustc_mir/lib.rs
index 7e4206e14c5..16753cee7e0 100644
--- a/src/librustc_mir/lib.rs
+++ b/src/librustc_mir/lib.rs
@@ -18,6 +18,7 @@ Rust MIR: a lowered representation of Rust. Also: an experiment!
 
 #![feature(box_patterns)]
 #![feature(box_syntax)]
+#![feature(conservative_impl_trait)]
 #![feature(const_fn)]
 #![feature(core_intrinsics)]
 #![feature(i128_type)]
diff --git a/src/librustc_mir/transform/nll/constraint_generation.rs b/src/librustc_mir/transform/nll/constraint_generation.rs
new file mode 100644
index 00000000000..1c0c3b6fc33
--- /dev/null
+++ b/src/librustc_mir/transform/nll/constraint_generation.rs
@@ -0,0 +1,64 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use rustc::mir::Mir;
+use rustc::infer::InferCtxt;
+use util::liveness::LivenessResult;
+
+use super::ToRegionIndex;
+use super::region_infer::RegionInferenceContext;
+
+pub fn generate_constraints<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+                                            regioncx: &mut RegionInferenceContext,
+                                            mir: &Mir<'tcx>,
+                                            liveness: &LivenessResult)
+{
+    ConstraintGeneration { infcx, regioncx, mir, liveness }.add_constraints();
+}
+
+struct ConstraintGeneration<'constrain, 'gcx: 'tcx, 'tcx: 'constrain> {
+    infcx: &'constrain InferCtxt<'constrain, 'gcx, 'tcx>,
+    regioncx: &'constrain mut RegionInferenceContext,
+    mir: &'constrain Mir<'tcx>,
+    liveness: &'constrain LivenessResult,
+}
+
+impl<'constrain, 'gcx, 'tcx> ConstraintGeneration<'constrain, 'gcx, 'tcx> {
+    fn add_constraints(&mut self) {
+        // To start, add the liveness constraints.
+        self.add_liveness_constraints();
+    }
+
+    /// Liveness constraints:
+    ///
+    /// > If a variable V is live at point P, then all regions R in the type of V
+    /// > must include the point P.
+    fn add_liveness_constraints(&mut self) {
+        let tcx = self.infcx.tcx;
+
+        debug!("add_liveness_constraints()");
+        for bb in self.mir.basic_blocks().indices() {
+            debug!("add_liveness_constraints: bb={:?}", bb);
+
+            self.liveness.simulate_block(self.mir, bb, |location, live_locals| {
+                debug!("add_liveness_constraints: location={:?} live_locals={:?}",
+                       location, live_locals);
+
+                for live_local in live_locals.iter() {
+                    let live_local_ty = self.mir.local_decls[live_local].ty;
+                    tcx.for_each_free_region(&live_local_ty, |live_region| {
+                        let vid = live_region.to_region_index();
+                        self.regioncx.add_live_point(vid, location);
+                    })
+                }
+            });
+        }
+    }
+}
diff --git a/src/librustc_mir/transform/nll/mod.rs b/src/librustc_mir/transform/nll/mod.rs
index fc42fd42b15..273972f6937 100644
--- a/src/librustc_mir/transform/nll/mod.rs
+++ b/src/librustc_mir/transform/nll/mod.rs
@@ -8,215 +8,115 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use self::infer::InferenceContext;
-use rustc::ty::TypeFoldable;
-use rustc::ty::subst::{Kind, Substs};
-use rustc::ty::{Ty, TyCtxt, ClosureSubsts, RegionVid, RegionKind};
-use rustc::mir::{Mir, Location, Rvalue, BasicBlock, Statement, StatementKind};
-use rustc::mir::visit::{MutVisitor, Lookup};
+use rustc::ty::{self, RegionKind, TyCtxt};
+use rustc::mir::{Location, Mir};
 use rustc::mir::transform::{MirPass, MirSource};
-use rustc::infer::{self as rustc_infer, InferCtxt};
-use rustc::util::nodemap::{FxHashMap, FxHashSet};
-use rustc_data_structures::indexed_vec::{IndexVec, Idx};
-use syntax_pos::DUMMY_SP;
-use std::collections::HashMap;
+use rustc::infer::InferCtxt;
+use rustc::util::nodemap::FxHashMap;
+use rustc_data_structures::indexed_vec::Idx;
+use std::collections::BTreeSet;
 use std::fmt;
-use util::liveness;
+use util::liveness::{self, LivenessResult};
 
 use util as mir_util;
 use self::mir_util::PassWhere;
 
-mod infer;
+mod constraint_generation;
 
-#[allow(dead_code)]
-struct NLLVisitor<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
-    lookup_map: HashMap<RegionVid, Lookup>,
-    regions: IndexVec<RegionIndex, Region>,
-    #[allow(dead_code)]
-    infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
-}
+mod region_infer;
+use self::region_infer::RegionInferenceContext;
 
-impl<'a, 'gcx, 'tcx> NLLVisitor<'a, 'gcx, 'tcx> {
-    pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>) -> Self {
-        NLLVisitor {
-            infcx,
-            lookup_map: HashMap::new(),
-            regions: IndexVec::new(),
-        }
-    }
+mod renumber;
 
-    pub fn into_results(self) -> (HashMap<RegionVid, Lookup>, IndexVec<RegionIndex, Region>) {
-        (self.lookup_map, self.regions)
-    }
-
-    fn renumber_regions<T>(&mut self, value: &T) -> T where T: TypeFoldable<'tcx> {
-        self.infcx.tcx.fold_regions(value, &mut false, |_region, _depth| {
-            self.regions.push(Region::default());
-            self.infcx.next_region_var(rustc_infer::MiscVariable(DUMMY_SP))
-        })
-    }
+// MIR Pass for non-lexical lifetimes
+pub struct NLL;
 
-    fn store_region(&mut self, region: &RegionKind, lookup: Lookup) {
-        if let RegionKind::ReVar(rid) = *region {
-            self.lookup_map.entry(rid).or_insert(lookup);
+impl MirPass for NLL {
+    fn run_pass<'a, 'tcx>(
+        &self,
+        tcx: TyCtxt<'a, 'tcx, 'tcx>,
+        source: MirSource,
+        input_mir: &mut Mir<'tcx>,
+    ) {
+        if !tcx.sess.opts.debugging_opts.nll {
+            return;
         }
-    }
 
-    fn store_ty_regions(&mut self, ty: &Ty<'tcx>, lookup: Lookup) {
-        for region in ty.regions() {
-            self.store_region(region, lookup);
-        }
-    }
+        tcx.infer_ctxt().enter(|ref infcx| {
+            // Clone mir so we can mutate it without disturbing the rest of the compiler
+            let mir = &mut input_mir.clone();
 
-    fn store_kind_regions(&mut self, kind: &'tcx Kind, lookup: Lookup) {
-        if let Some(ty) = kind.as_type() {
-            self.store_ty_regions(&ty, lookup);
-        } else if let Some(region) = kind.as_region() {
-            self.store_region(region, lookup);
-        }
-    }
-}
+            // Replace all regions with fresh inference variables.
+            let num_region_variables = renumber::renumber_mir(infcx, mir);
 
-impl<'a, 'gcx, 'tcx> MutVisitor<'tcx> for NLLVisitor<'a, 'gcx, 'tcx> {
-    fn visit_ty(&mut self, ty: &mut Ty<'tcx>, lookup: Lookup) {
-        let old_ty = *ty;
-        *ty = self.renumber_regions(&old_ty);
-        self.store_ty_regions(ty, lookup);
-    }
+            // Compute what is live where.
+            let liveness = &liveness::liveness_of_locals(mir);
 
-    fn visit_substs(&mut self, substs: &mut &'tcx Substs<'tcx>, location: Location) {
-        *substs = self.renumber_regions(&{*substs});
-        let lookup = Lookup::Loc(location);
-        for kind in *substs {
-            self.store_kind_regions(kind, lookup);
-        }
-    }
+            // Create the region inference context, generate the constraints,
+            // and then solve them.
+            let regioncx = &mut RegionInferenceContext::new(num_region_variables);
+            constraint_generation::generate_constraints(infcx, regioncx, mir, liveness);
+            regioncx.solve(infcx, mir);
 
-    fn visit_rvalue(&mut self, rvalue: &mut Rvalue<'tcx>, location: Location) {
-        match *rvalue {
-            Rvalue::Ref(ref mut r, _, _) => {
-                let old_r = *r;
-                *r = self.renumber_regions(&old_r);
-                let lookup = Lookup::Loc(location);
-                self.store_region(r, lookup);
-            }
-            Rvalue::Use(..) |
-            Rvalue::Repeat(..) |
-            Rvalue::Len(..) |
-            Rvalue::Cast(..) |
-            Rvalue::BinaryOp(..) |
-            Rvalue::CheckedBinaryOp(..) |
-            Rvalue::UnaryOp(..) |
-            Rvalue::Discriminant(..) |
-            Rvalue::NullaryOp(..) |
-            Rvalue::Aggregate(..) => {
-                // These variants don't contain regions.
-            }
-        }
-        self.super_rvalue(rvalue, location);
+            // Dump MIR results into a file, if that is enabled.
+            dump_mir_results(infcx, liveness, source, regioncx, mir);
+        })
     }
+}
 
-    fn visit_closure_substs(&mut self,
-                            substs: &mut ClosureSubsts<'tcx>,
-                            location: Location) {
-        *substs = self.renumber_regions(substs);
-        let lookup = Lookup::Loc(location);
-        for kind in substs.substs {
-            self.store_kind_regions(kind, lookup);
-        }
+fn dump_mir_results<'a, 'gcx, 'tcx>(
+    infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+    liveness: &LivenessResult,
+    source: MirSource,
+    regioncx: &RegionInferenceContext,
+    mir: &Mir<'tcx>,
+) {
+    if !mir_util::dump_enabled(infcx.tcx, "nll", source) {
+        return;
     }
 
-    fn visit_statement(&mut self,
-                       block: BasicBlock,
-                       statement: &mut Statement<'tcx>,
-                       location: Location) {
-        if let StatementKind::EndRegion(_) = statement.kind {
-            statement.kind = StatementKind::Nop;
-        }
-        self.super_statement(block, statement, location);
-    }
-}
+    let liveness_per_location: FxHashMap<_, _> = mir.basic_blocks()
+        .indices()
+        .flat_map(|bb| {
+            let mut results = vec![];
+            liveness.simulate_block(&mir, bb, |location, local_set| {
+                results.push((location, local_set.clone()));
+            });
+            results
+        })
+        .collect();
+
+    mir_util::dump_mir(infcx.tcx, None, "nll", &0, source, mir, |pass_where, out| {
+        match pass_where {
+            // Before the CFG, dump out the values for each region variable.
+            PassWhere::BeforeCFG => for region in regioncx.regions() {
+                writeln!(out, "| {:?}: {:?}", region, regioncx.region_value(region))?;
+            },
+
+            // Before each basic block, dump out the values
+            // that are live on entry to the basic block.
+            PassWhere::BeforeBlock(bb) => {
+                let local_set = &liveness.ins[bb];
+                writeln!(out, "    | Variables live on entry to the block {:?}:", bb)?;
+                for local in local_set.iter() {
+                    writeln!(out, "    | - {:?}", local)?;
+                }
+            }
 
-// MIR Pass for non-lexical lifetimes
-pub struct NLL;
+            PassWhere::InCFG(location) => {
+                let local_set = &liveness_per_location[&location];
+                writeln!(out, "        | Live variables here: {:?}", local_set)?;
+            }
 
-impl MirPass for NLL {
-    fn run_pass<'a, 'tcx>(&self,
-                          tcx: TyCtxt<'a, 'tcx, 'tcx>,
-                          source: MirSource,
-                          input_mir: &mut Mir<'tcx>) {
-        if !tcx.sess.opts.debugging_opts.nll {
-            return;
+            PassWhere::AfterCFG => {}
         }
-
-        tcx.infer_ctxt().enter(|infcx| {
-            // Clone mir so we can mutate it without disturbing the rest of the compiler
-            let mir = &mut input_mir.clone();
-
-            let mut visitor = NLLVisitor::new(&infcx);
-            visitor.visit_mir(mir);
-
-            let liveness = liveness::liveness_of_locals(mir);
-
-            let liveness_per_location: FxHashMap<_, _> =
-                mir
-                .basic_blocks()
-                .indices()
-                .flat_map(|bb| {
-                    let mut results = vec![];
-                    liveness.simulate_block(&mir, bb, |location, local_set| {
-                        results.push((location, local_set.clone()));
-                    });
-                    results
-                })
-                .collect();
-
-            mir_util::dump_mir(infcx.tcx, None, "nll", &0, source, mir, |pass_where, out| {
-                match pass_where {
-                    // Before the CFG, dump out the values for each region variable.
-                    PassWhere::BeforeCFG => {
-                        for (index, value) in visitor.regions.iter_enumerated() {
-                            writeln!(out, "| R{:03}: {:?}", index.0, value)?;
-                        }
-                    }
-
-                    // Before each basic block, dump out the values
-                    // that are live on entry to the basic block.
-                    PassWhere::BeforeBlock(bb) => {
-                        let local_set = &liveness.ins[bb];
-                        writeln!(out, "    | Variables live on entry to the block {:?}:", bb)?;
-                        for local in local_set.iter() {
-                            writeln!(out, "    | - {:?}", local)?;
-                        }
-                    }
-
-                    PassWhere::InCFG(location) => {
-                        let local_set = &liveness_per_location[&location];
-                        let mut string = String::new();
-                        for local in local_set.iter() {
-                            string.push_str(&format!(", {:?}", local));
-                        }
-                        if !string.is_empty() {
-                            writeln!(out, "        | Live variables here: [{}]", &string[2..])?;
-                        } else {
-                            writeln!(out, "        | Live variables here: []")?;
-                        }
-                    }
-
-                    PassWhere::AfterCFG => { }
-                }
-                Ok(())
-            });
-            let (_lookup_map, regions) = visitor.into_results();
-            let mut inference_context = InferenceContext::new(regions);
-            inference_context.solve(&infcx, mir);
-        })
-    }
+        Ok(())
+    });
 }
 
 #[derive(Clone, Default, PartialEq, Eq)]
 pub struct Region {
-    points: FxHashSet<Location>,
+    points: BTreeSet<Location>,
 }
 
 impl fmt::Debug for Region {
@@ -235,4 +135,25 @@ impl Region {
     }
 }
 
-newtype_index!(RegionIndex);
+newtype_index!(RegionIndex {
+    DEBUG_NAME = "R",
+});
+
+/// Right now, we piggy back on the `ReVar` to store our NLL inference
+/// regions. These are indexed with `RegionIndex`. This method will
+/// assert that the region is a `ReVar` and convert the internal index
+/// into a `RegionIndex`. This is reasonable because in our MIR we
+/// replace all free regions with inference variables.
+trait ToRegionIndex {
+    fn to_region_index(&self) -> RegionIndex;
+}
+
+impl ToRegionIndex for RegionKind {
+    fn to_region_index(&self) -> RegionIndex {
+        if let &ty::ReVar(vid) = self {
+            RegionIndex::new(vid.index as usize)
+        } else {
+            bug!("region is not an ReVar: {:?}", self)
+        }
+    }
+}
diff --git a/src/librustc_mir/transform/nll/infer.rs b/src/librustc_mir/transform/nll/region_infer.rs
index e6e00f295ca..75abd4d3ff5 100644
--- a/src/librustc_mir/transform/nll/infer.rs
+++ b/src/librustc_mir/transform/nll/region_infer.rs
@@ -15,7 +15,7 @@ use rustc::mir::{Location, Mir};
 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
 use rustc_data_structures::fx::FxHashSet;
 
-pub struct InferenceContext {
+pub struct RegionInferenceContext {
     definitions: IndexVec<RegionIndex, VarDefinition>,
     constraints: IndexVec<ConstraintIndex, Constraint>,
     errors: IndexVec<InferenceErrorIndex, InferenceError>,
@@ -28,22 +28,13 @@ pub struct InferenceError {
 
 newtype_index!(InferenceErrorIndex);
 
+#[derive(Default)]
 struct VarDefinition {
     name: (), // FIXME(nashenas88) RegionName
     value: Region,
     capped: bool,
 }
 
-impl VarDefinition {
-    pub fn new(value: Region) -> Self {
-        Self {
-            name: (),
-            value,
-            capped: false,
-        }
-    }
-}
-
 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
 pub struct Constraint {
     sub: RegionIndex,
@@ -53,10 +44,12 @@ pub struct Constraint {
 
 newtype_index!(ConstraintIndex);
 
-impl InferenceContext {
-    pub fn new(values: IndexVec<RegionIndex, Region>) -> Self {
+impl RegionInferenceContext {
+    pub fn new(num_region_variables: usize) -> Self {
         Self {
-            definitions: values.into_iter().map(VarDefinition::new).collect(),
+            definitions: (0..num_region_variables)
+                .map(|_| VarDefinition::default())
+                .collect(),
             constraints: IndexVec::new(),
             errors: IndexVec::new(),
         }
@@ -87,8 +80,14 @@ impl InferenceContext {
         self.constraints.push(Constraint { sup, sub, point });
     }
 
-    #[allow(dead_code)]
-    pub fn region(&self, v: RegionIndex) -> &Region {
+    /// Returns an iterator over all the region indices.
+    pub fn regions(&self) -> impl Iterator<Item = RegionIndex> {
+        self.definitions.indices()
+    }
+
+    /// Returns the current value for the region `v`. This is only
+    /// really meaningful after `solve` has executed.
+    pub fn region_value(&self, v: RegionIndex) -> &Region {
         &self.definitions[v].value
     }
 
@@ -144,8 +143,7 @@ impl InferenceContext {
 }
 
 struct Dfs<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> {
-    #[allow(dead_code)]
-    infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
+    #[allow(dead_code)] infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
     mir: &'a Mir<'tcx>,
 }
 
@@ -183,17 +181,22 @@ impl<'a, 'gcx: 'tcx, 'tcx: 'a> Dfs<'a, 'gcx, 'tcx> {
 
             let block_data = &self.mir[p.block];
             let successor_points = if p.statement_index < block_data.statements.len() {
-                vec![Location {
-                    statement_index: p.statement_index + 1,
-                    ..p
-                }]
+                vec![
+                    Location {
+                        statement_index: p.statement_index + 1,
+                        ..p
+                    },
+                ]
             } else {
-                block_data.terminator()
+                block_data
+                    .terminator()
                     .successors()
                     .iter()
-                    .map(|&basic_block| Location {
-                        statement_index: 0,
-                        block: basic_block,
+                    .map(|&basic_block| {
+                        Location {
+                            statement_index: 0,
+                            block: basic_block,
+                        }
                     })
                     .collect::<Vec<_>>()
             };
diff --git a/src/librustc_mir/transform/nll/renumber.rs b/src/librustc_mir/transform/nll/renumber.rs
new file mode 100644
index 00000000000..589179c2066
--- /dev/null
+++ b/src/librustc_mir/transform/nll/renumber.rs
@@ -0,0 +1,132 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use rustc::ty::TypeFoldable;
+use rustc::ty::subst::{Kind, Substs};
+use rustc::ty::{Ty, ClosureSubsts, RegionVid, RegionKind};
+use rustc::mir::{Mir, Location, Rvalue, BasicBlock, Statement, StatementKind};
+use rustc::mir::visit::{MutVisitor, Lookup};
+use rustc::infer::{self as rustc_infer, InferCtxt};
+use syntax_pos::DUMMY_SP;
+use std::collections::HashMap;
+
+/// Replaces all free regions appearing in the MIR with fresh
+/// inference variables, returning the number of variables created.
+pub fn renumber_mir<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+                                    mir: &mut Mir<'tcx>)
+                                    -> usize
+{
+    let mut visitor = NLLVisitor::new(infcx);
+    visitor.visit_mir(mir);
+    visitor.num_region_variables
+}
+
+struct NLLVisitor<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
+    lookup_map: HashMap<RegionVid, Lookup>,
+    num_region_variables: usize,
+    infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
+}
+
+impl<'a, 'gcx, 'tcx> NLLVisitor<'a, 'gcx, 'tcx> {
+    pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>) -> Self {
+        NLLVisitor {
+            infcx,
+            lookup_map: HashMap::new(),
+            num_region_variables: 0
+        }
+    }
+
+    fn renumber_regions<T>(&mut self, value: &T) -> T where T: TypeFoldable<'tcx> {
+        self.infcx.tcx.fold_regions(value, &mut false, |_region, _depth| {
+            self.num_region_variables += 1;
+            self.infcx.next_region_var(rustc_infer::MiscVariable(DUMMY_SP))
+        })
+    }
+
+    fn store_region(&mut self, region: &RegionKind, lookup: Lookup) {
+        if let RegionKind::ReVar(rid) = *region {
+            self.lookup_map.entry(rid).or_insert(lookup);
+        }
+    }
+
+    fn store_ty_regions(&mut self, ty: &Ty<'tcx>, lookup: Lookup) {
+        for region in ty.regions() {
+            self.store_region(region, lookup);
+        }
+    }
+
+    fn store_kind_regions(&mut self, kind: &'tcx Kind, lookup: Lookup) {
+        if let Some(ty) = kind.as_type() {
+            self.store_ty_regions(&ty, lookup);
+        } else if let Some(region) = kind.as_region() {
+            self.store_region(region, lookup);
+        }
+    }
+}
+
+impl<'a, 'gcx, 'tcx> MutVisitor<'tcx> for NLLVisitor<'a, 'gcx, 'tcx> {
+    fn visit_ty(&mut self, ty: &mut Ty<'tcx>, lookup: Lookup) {
+        let old_ty = *ty;
+        *ty = self.renumber_regions(&old_ty);
+        self.store_ty_regions(ty, lookup);
+    }
+
+    fn visit_substs(&mut self, substs: &mut &'tcx Substs<'tcx>, location: Location) {
+        *substs = self.renumber_regions(&{*substs});
+        let lookup = Lookup::Loc(location);
+        for kind in *substs {
+            self.store_kind_regions(kind, lookup);
+        }
+    }
+
+    fn visit_rvalue(&mut self, rvalue: &mut Rvalue<'tcx>, location: Location) {
+        match *rvalue {
+            Rvalue::Ref(ref mut r, _, _) => {
+                let old_r = *r;
+                *r = self.renumber_regions(&old_r);
+                let lookup = Lookup::Loc(location);
+                self.store_region(r, lookup);
+            }
+            Rvalue::Use(..) |
+            Rvalue::Repeat(..) |
+            Rvalue::Len(..) |
+            Rvalue::Cast(..) |
+            Rvalue::BinaryOp(..) |
+            Rvalue::CheckedBinaryOp(..) |
+            Rvalue::UnaryOp(..) |
+            Rvalue::Discriminant(..) |
+            Rvalue::NullaryOp(..) |
+            Rvalue::Aggregate(..) => {
+                // These variants don't contain regions.
+            }
+        }
+        self.super_rvalue(rvalue, location);
+    }
+
+    fn visit_closure_substs(&mut self,
+                            substs: &mut ClosureSubsts<'tcx>,
+                            location: Location) {
+        *substs = self.renumber_regions(substs);
+        let lookup = Lookup::Loc(location);
+        for kind in substs.substs {
+            self.store_kind_regions(kind, lookup);
+        }
+    }
+
+    fn visit_statement(&mut self,
+                       block: BasicBlock,
+                       statement: &mut Statement<'tcx>,
+                       location: Location) {
+        if let StatementKind::EndRegion(_) = statement.kind {
+            statement.kind = StatementKind::Nop;
+        }
+        self.super_statement(block, statement, location);
+    }
+}
diff --git a/src/test/mir-opt/nll/region-liveness-basic.rs b/src/test/mir-opt/nll/region-liveness-basic.rs
new file mode 100644
index 00000000000..d1ef08cf00d
--- /dev/null
+++ b/src/test/mir-opt/nll/region-liveness-basic.rs
@@ -0,0 +1,55 @@
+// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Basic test for liveness constraints: the region (`R1`) that appears
+// in the type of `p` includes the points after `&v[0]` up to (but not
+// including) the call to `use_x`. The `else` branch is not included.
+
+// compile-flags:-Znll -Zverbose
+//                     ^^^^^^^^^ force compiler to dump more region information
+
+#![allow(warnings)]
+
+fn use_x(_: usize) -> bool { true }
+
+fn main() {
+    let mut v = [1, 2, 3];
+    let p = &v[0];
+    if true {
+        use_x(*p);
+    } else {
+        use_x(22);
+    }
+}
+
+// END RUST SOURCE
+// START rustc.node12.nll.0.mir
+// | R1: {bb1[1], bb2[0], bb2[1]}
+// ...
+//             let _2: &'_#1r usize;
+// END rustc.node12.nll.0.mir
+// START rustc.node12.nll.0.mir
+//    bb1: {
+//        | Live variables here: [_1, _3]
+//        _2 = &'_#0r _1[_3];
+//        | Live variables here: [_2]
+//        switchInt(const true) -> [0u8: bb3, otherwise: bb2];
+//    }
+// END rustc.node12.nll.0.mir
+// START rustc.node12.nll.0.mir
+//    bb2: {
+//        | Live variables here: [_2]
+//        StorageLive(_7);
+//        | Live variables here: [_2]
+//        _7 = (*_2);
+//        | Live variables here: [_7]
+//        _6 = const use_x(_7) -> bb4;
+//    }
+// END rustc.node12.nll.0.mir