implement liveness tracing, remove old liveness system

14 files changed, 963 insertions, 338 deletions

diff --git a/src/librustc/mir/mod.rs b/src/librustc/mir/mod.rs
index 86e521727c5..0840f333c87 100644
--- a/src/librustc/mir/mod.rs
+++ b/src/librustc/mir/mod.rs
@@ -194,12 +194,12 @@ impl<'tcx> Mir<'tcx> {
     }
 
     #[inline]
-    pub fn predecessors(&self) -> ReadGuard<IndexVec<BasicBlock, Vec<BasicBlock>>> {
+    pub fn predecessors(&self) -> ReadGuard<'_, IndexVec<BasicBlock, Vec<BasicBlock>>> {
         self.cache.predecessors(self)
     }
 
     #[inline]
-    pub fn predecessors_for(&self, bb: BasicBlock) -> ReadGuard<Vec<BasicBlock>> {
+    pub fn predecessors_for(&self, bb: BasicBlock) -> ReadGuard<'_, Vec<BasicBlock>> {
         ReadGuard::map(self.predecessors(), |p| &p[bb])
     }
 
@@ -328,6 +328,14 @@ impl<'tcx> Mir<'tcx> {
     pub fn return_ty(&self) -> Ty<'tcx> {
         self.local_decls[RETURN_PLACE].ty
     }
+
+    /// Get the location of the terminator for the given block
+    pub fn terminator_loc(&self, bb: BasicBlock) -> Location {
+        Location {
+            block: bb,
+            statement_index: self[bb].statements.len(),
+        }
+    }
 }
 
 #[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index 1eef7870c01..2e8d9725234 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -20,6 +20,7 @@
       html_favicon_url = "https://www.rust-lang.org/favicon.ico",
       html_root_url = "https://doc.rust-lang.org/nightly/")]
 
+#![feature(in_band_lifetimes)]
 #![feature(unboxed_closures)]
 #![feature(fn_traits)]
 #![feature(unsize)]
@@ -85,6 +86,7 @@ pub mod thin_vec;
 pub mod transitive_relation;
 pub mod tuple_slice;
 pub use ena::unify;
+pub mod vec_linked_list;
 pub mod work_queue;
 pub mod fingerprint;
 
diff --git a/src/librustc_data_structures/vec_linked_list.rs b/src/librustc_data_structures/vec_linked_list.rs
new file mode 100644
index 00000000000..390dca6b905
--- /dev/null
+++ b/src/librustc_data_structures/vec_linked_list.rs
@@ -0,0 +1,83 @@
+// Copyright 2014 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 indexed_vec::{Idx, IndexVec};
+
+pub fn iter<Ls>(
+    first: Option<Ls::LinkIndex>,
+    links: &'a Ls,
+) -> impl Iterator<Item = Ls::LinkIndex> + 'a
+where
+    Ls: Links,
+{
+    VecLinkedListIterator {
+        links: links,
+        current: first,
+    }
+}
+
+pub struct VecLinkedListIterator<Ls>
+where
+    Ls: Links,
+{
+    links: Ls,
+    current: Option<Ls::LinkIndex>,
+}
+
+impl<Ls> Iterator for VecLinkedListIterator<Ls>
+where
+    Ls: Links,
+{
+    type Item = Ls::LinkIndex;
+
+    fn next(&mut self) -> Option<Ls::LinkIndex> {
+        if let Some(c) = self.current {
+            self.current = <Ls as Links>::next(&self.links, c);
+            Some(c)
+        } else {
+            None
+        }
+    }
+}
+
+pub trait Links {
+    type LinkIndex: Copy;
+
+    fn next(links: &Self, index: Self::LinkIndex) -> Option<Self::LinkIndex>;
+}
+
+impl<Ls> Links for &Ls
+where
+    Ls: Links,
+{
+    type LinkIndex = Ls::LinkIndex;
+
+    fn next(links: &Self, index: Ls::LinkIndex) -> Option<Ls::LinkIndex> {
+        <Ls as Links>::next(links, index)
+    }
+}
+
+pub trait LinkElem {
+    type LinkIndex: Copy;
+
+    fn next(elem: &Self) -> Option<Self::LinkIndex>;
+}
+
+impl<L, E> Links for IndexVec<L, E>
+where
+    E: LinkElem<LinkIndex = L>,
+    L: Idx,
+{
+    type LinkIndex = L;
+
+    fn next(links: &Self, index: L) -> Option<L> {
+        <E as LinkElem>::next(&links[index])
+    }
+}
diff --git a/src/librustc_mir/borrow_check/flows.rs b/src/librustc_mir/borrow_check/flows.rs
index 90dc96cbd3c..192fa2b9eea 100644
--- a/src/librustc_mir/borrow_check/flows.rs
+++ b/src/librustc_mir/borrow_check/flows.rs
@@ -89,6 +89,10 @@ impl<'b, 'gcx, 'tcx> FlowsAtLocation for Flows<'b, 'gcx, 'tcx> {
         each_flow!(self, reset_to_entry_of(bb));
     }
 
+    fn reset_to_exit_of(&mut self, bb: BasicBlock) {
+        each_flow!(self, reset_to_exit_of(bb));
+    }
+
     fn reconstruct_statement_effect(&mut self, location: Location) {
         each_flow!(self, reconstruct_statement_effect(location));
     }
diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs
index 40df78d6bfd..b80f9784d6f 100644
--- a/src/librustc_mir/borrow_check/nll/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/mod.rs
@@ -12,7 +12,7 @@ use borrow_check::borrow_set::BorrowSet;
 use borrow_check::location::{LocationIndex, LocationTable};
 use borrow_check::nll::facts::AllFactsExt;
 use borrow_check::nll::type_check::{MirTypeckResults, MirTypeckRegionConstraints};
-use borrow_check::nll::type_check::liveness::liveness_map::{NllLivenessMap, LocalWithRegion};
+use borrow_check::nll::type_check::liveness::liveness_map::NllLivenessMap;
 use borrow_check::nll::region_infer::values::RegionValueElements;
 use dataflow::indexes::BorrowIndex;
 use dataflow::move_paths::MoveData;
@@ -22,9 +22,7 @@ use rustc::hir::def_id::DefId;
 use rustc::infer::InferCtxt;
 use rustc::mir::{ClosureOutlivesSubject, ClosureRegionRequirements, Mir};
 use rustc::ty::{self, RegionKind, RegionVid};
-use rustc::util::nodemap::FxHashMap;
 use rustc_errors::Diagnostic;
-use std::collections::BTreeSet;
 use std::fmt::Debug;
 use std::env;
 use std::io;
@@ -32,12 +30,11 @@ use std::path::PathBuf;
 use std::rc::Rc;
 use std::str::FromStr;
 use transform::MirSource;
-use util::liveness::{LivenessResults, LiveVarSet};
 
 use self::mir_util::PassWhere;
 use polonius_engine::{Algorithm, Output};
 use util as mir_util;
-use util::pretty::{self, ALIGN};
+use util::pretty;
 
 mod constraint_generation;
 pub mod explain_borrow;
@@ -111,8 +108,6 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
     let MirTypeckResults {
         constraints,
         universal_region_relations,
-        liveness,
-        liveness_map,
     } = type_check::type_check(
         infcx,
         param_env,
@@ -205,8 +200,6 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
     // write unit-tests, as well as helping with debugging.
     dump_mir_results(
         infcx,
-        &liveness,
-        &liveness_map,
         MirSource::item(def_id),
         &mir,
         &regioncx,
@@ -222,8 +215,6 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
 
 fn dump_mir_results<'a, 'gcx, 'tcx>(
     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
-    liveness: &LivenessResults<LocalWithRegion>,
-    liveness_map: &NllLivenessMap,
     source: MirSource,
     mir: &Mir<'tcx>,
     regioncx: &RegionInferenceContext,
@@ -233,34 +224,6 @@ fn dump_mir_results<'a, 'gcx, 'tcx>(
         return;
     }
 
-    let regular_liveness_per_location: FxHashMap<_, _> = mir
-        .basic_blocks()
-        .indices()
-        .flat_map(|bb| {
-            let mut results = vec![];
-            liveness
-                .regular
-                .simulate_block(&mir, bb, liveness_map, |location, local_set| {
-                    results.push((location, local_set.clone()));
-                });
-            results
-        })
-        .collect();
-
-    let drop_liveness_per_location: FxHashMap<_, _> = mir
-        .basic_blocks()
-        .indices()
-        .flat_map(|bb| {
-            let mut results = vec![];
-            liveness
-                .drop
-                .simulate_block(&mir, bb, liveness_map, |location, local_set| {
-                    results.push((location, local_set.clone()));
-                });
-            results
-        })
-        .collect();
-
     mir_util::dump_mir(
         infcx.tcx,
         None,
@@ -283,26 +246,10 @@ fn dump_mir_results<'a, 'gcx, 'tcx>(
                     }
                 }
 
-                PassWhere::BeforeLocation(location) => {
-                    let s = live_variable_set(
-                        &regular_liveness_per_location[&location],
-                        &drop_liveness_per_location[&location],
-                    );
-                    writeln!(
-                        out,
-                        "{:ALIGN$} | Live variables on entry to {:?}: {}",
-                        "",
-                        location,
-                        s,
-                        ALIGN = ALIGN
-                    )?;
+                PassWhere::BeforeLocation(_) => {
                 }
 
-                // After each basic block, dump out the values
-                // that are live on exit from the basic block.
-                PassWhere::AfterTerminator(bb) => {
-                    let s = live_variable_set(&liveness.regular.outs[bb], &liveness.drop.outs[bb]);
-                    writeln!(out, "    | Live variables on exit from {:?}: {}", bb, s)?;
+                PassWhere::AfterTerminator(_) => {
                 }
 
                 PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {}
@@ -420,33 +367,3 @@ impl ToRegionVid for RegionVid {
         self
     }
 }
-
-fn live_variable_set(
-    regular: &LiveVarSet<LocalWithRegion>,
-    drops: &LiveVarSet<LocalWithRegion>
-) -> String {
-    // sort and deduplicate:
-    let all_locals: BTreeSet<_> = regular.iter().chain(drops.iter()).collect();
-
-    // construct a string with each local, including `(drop)` if it is
-    // only dropped, versus a regular use.
-    let mut string = String::new();
-    for local in all_locals {
-        string.push_str(&format!("{:?}", local));
-
-        if !regular.contains(&local) {
-            assert!(drops.contains(&local));
-            string.push_str(" (drop)");
-        }
-
-        string.push_str(", ");
-    }
-
-    let len = if string.is_empty() {
-        0
-    } else {
-        string.len() - 2
-    };
-
-    format!("[{}]", &string[..len])
-}
diff --git a/src/librustc_mir/borrow_check/nll/region_infer/values.rs b/src/librustc_mir/borrow_check/nll/region_infer/values.rs
index 8db5809e53f..166281fd331 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/values.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/values.rs
@@ -10,7 +10,7 @@
 
 use rustc::mir::{BasicBlock, Location, Mir};
 use rustc::ty::{self, RegionVid};
-use rustc_data_structures::bitvec::SparseBitMatrix;
+use rustc_data_structures::bitvec::{BitArray, SparseBitMatrix};
 use rustc_data_structures::indexed_vec::Idx;
 use rustc_data_structures::indexed_vec::IndexVec;
 use std::fmt::Debug;
@@ -47,8 +47,13 @@ impl RegionValueElements {
         }
     }
 
+    /// Total number of point indices
+    crate fn num_points(&self) -> usize {
+        self.num_points
+    }
+
     /// Converts a `Location` into a `PointIndex`. O(1).
-    fn point_from_location(&self, location: Location) -> PointIndex {
+    crate fn point_from_location(&self, location: Location) -> PointIndex {
         let Location {
             block,
             statement_index,
@@ -57,6 +62,12 @@ impl RegionValueElements {
         PointIndex::new(start_index + statement_index)
     }
 
+    /// Converts a `Location` into a `PointIndex`. O(1).
+    crate fn entry_point(&self, block: BasicBlock) -> PointIndex {
+        let start_index = self.statements_before_block[block];
+        PointIndex::new(start_index)
+    }
+
     /// Converts a `PointIndex` back to a location. O(N) where N is
     /// the number of blocks; could be faster if we ever cared.
     crate fn to_location(&self, i: PointIndex) -> Location {
@@ -92,6 +103,15 @@ impl RegionValueElements {
             statement_index: point_index - first_index,
         }
     }
+
+    /// Returns an iterator of each basic block and the first point
+    /// index within the block; the point indices for all statements
+    /// within the block follow afterwards.
+    crate fn head_indices(&self) -> impl Iterator<Item = (BasicBlock, PointIndex)> + '_ {
+        self.statements_before_block
+            .iter_enumerated()
+            .map(move |(bb, &first_index)| (bb, PointIndex::new(first_index)))
+    }
 }
 
 /// A single integer representing a `Location` in the MIR control-flow
@@ -151,6 +171,13 @@ impl<N: Idx> LivenessValues<N> {
         self.points.add(row, index)
     }
 
+    /// Adds all the elements in the given bit array into the given
+    /// region. Returns true if any of them are newly added.
+    crate fn add_elements(&mut self, row: N, locations: &BitArray<PointIndex>) -> bool {
+        debug!("LivenessValues::add_elements(row={:?}, locations={:?})", row, locations);
+        self.points.merge_into(row, locations)
+    }
+
     /// Adds all the control-flow points to the values for `r`.
     crate fn add_all_points(&mut self, row: N) {
         self.points.add_all(row);
@@ -366,6 +393,18 @@ impl ToElementIndex for ty::UniverseIndex {
     }
 }
 
+crate fn location_set_str(
+    elements: &RegionValueElements,
+    points: impl IntoIterator<Item = PointIndex>,
+) -> String {
+    region_value_str(
+        points
+            .into_iter()
+            .map(|p| elements.to_location(p))
+            .map(RegionElement::Location),
+    )
+}
+
 fn region_value_str(elements: impl IntoIterator<Item = RegionElement>) -> String {
     let mut result = String::new();
     result.push_str("{");
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs
new file mode 100644
index 00000000000..b63c43d825b
--- /dev/null
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs
@@ -0,0 +1,158 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use borrow_check::nll::region_infer::values::{PointIndex, RegionValueElements};
+use borrow_check::nll::type_check::liveness::liveness_map::{LocalWithRegion, NllLivenessMap};
+use rustc::mir::visit::{PlaceContext, Visitor};
+use rustc::mir::{Local, Location, Mir};
+use rustc_data_structures::indexed_vec::{Idx, IndexVec};
+use rustc_data_structures::vec_linked_list as vll;
+use util::liveness::{categorize, DefUse, LiveVariableMap};
+
+/// A map that cross references each local with the locations where it
+/// is defined (assigned), used, or dropped. Used during liveness
+/// computation.
+crate struct LocalUseMap<'me> {
+    liveness_map: &'me NllLivenessMap,
+
+    /// Head of a linked list of **definitions** of each variable --
+    /// definition in this context means assignment, e.g. `x` is
+    /// defined in `x = y` but not `y`; that first def is the head of
+    /// a linked list that lets you enumerate all places the variable
+    /// is assigned.
+    first_def_at: IndexVec<LocalWithRegion, Option<AppearanceIndex>>,
+
+    /// Head of a linked list of **uses** of each variable -- use in
+    /// this context means that the existing value of the variable is
+    /// read or modified. e.g., `y` is used in `x = y` but not `x`.
+    first_use_at: IndexVec<LocalWithRegion, Option<AppearanceIndex>>,
+
+    /// Head of a linked list of **uses** of each variable -- use in
+    /// this context means that the existing value of the variable is
+    /// read or modified. e.g., `y` is used in `x = y` but not `x`.
+    first_drop_at: IndexVec<LocalWithRegion, Option<AppearanceIndex>>,
+
+    appearances: IndexVec<AppearanceIndex, Appearance>,
+}
+
+struct Appearance {
+    point_index: PointIndex,
+    next: Option<AppearanceIndex>,
+}
+
+newtype_index!(AppearanceIndex);
+
+impl vll::LinkElem for Appearance {
+    type LinkIndex = AppearanceIndex;
+
+    fn next(elem: &Self) -> Option<AppearanceIndex> {
+        elem.next
+    }
+}
+
+impl LocalUseMap<'me> {
+    crate fn build(
+        liveness_map: &'me NllLivenessMap,
+        elements: &RegionValueElements,
+        mir: &Mir<'_>,
+    ) -> Self {
+        let nones = IndexVec::from_elem_n(None, liveness_map.num_variables());
+        let mut local_use_map = LocalUseMap {
+            liveness_map,
+            first_def_at: nones.clone(),
+            first_use_at: nones.clone(),
+            first_drop_at: nones,
+            appearances: IndexVec::new(),
+        };
+
+        LocalUseMapBuild {
+            local_use_map: &mut local_use_map,
+            elements,
+        }.visit_mir(mir);
+
+        local_use_map
+    }
+
+    crate fn defs(&self, local: LocalWithRegion) -> impl Iterator<Item = PointIndex> + '_ {
+        vll::iter(self.first_def_at[local], &self.appearances)
+            .map(move |aa| self.appearances[aa].point_index)
+    }
+
+    crate fn uses(&self, local: LocalWithRegion) -> impl Iterator<Item = PointIndex> + '_ {
+        vll::iter(self.first_use_at[local], &self.appearances)
+            .map(move |aa| self.appearances[aa].point_index)
+    }
+
+    crate fn drops(&self, local: LocalWithRegion) -> impl Iterator<Item = PointIndex> + '_ {
+        vll::iter(self.first_drop_at[local], &self.appearances)
+            .map(move |aa| self.appearances[aa].point_index)
+    }
+}
+
+struct LocalUseMapBuild<'me, 'map> {
+    local_use_map: &'me mut LocalUseMap<'map>,
+    elements: &'me RegionValueElements,
+}
+
+impl LocalUseMapBuild<'_, '_> {
+    fn insert_def(&mut self, local: LocalWithRegion, location: Location) {
+        Self::insert(
+            self.elements,
+            &mut self.local_use_map.first_def_at[local],
+            &mut self.local_use_map.appearances,
+            location,
+        );
+    }
+
+    fn insert_use(&mut self, local: LocalWithRegion, location: Location) {
+        Self::insert(
+            self.elements,
+            &mut self.local_use_map.first_use_at[local],
+            &mut self.local_use_map.appearances,
+            location,
+        );
+    }
+
+    fn insert_drop(&mut self, local: LocalWithRegion, location: Location) {
+        Self::insert(
+            self.elements,
+            &mut self.local_use_map.first_drop_at[local],
+            &mut self.local_use_map.appearances,
+            location,
+        );
+    }
+
+    fn insert(
+        elements: &RegionValueElements,
+        first_appearance: &mut Option<AppearanceIndex>,
+        appearances: &mut IndexVec<AppearanceIndex, Appearance>,
+        location: Location,
+    ) {
+        let point_index = elements.point_from_location(location);
+        let appearance_index = appearances.push(Appearance {
+            point_index,
+            next: *first_appearance,
+        });
+        *first_appearance = Some(appearance_index);
+    }
+}
+
+impl Visitor<'tcx> for LocalUseMapBuild<'_, '_> {
+    fn visit_local(&mut self, &local: &Local, context: PlaceContext<'tcx>, location: Location) {
+        if let Some(local_with_region) = self.local_use_map.liveness_map.from_local(local) {
+            match categorize(context) {
+                Some(DefUse::Def) => self.insert_def(local_with_region, location),
+                Some(DefUse::Use) => self.insert_use(local_with_region, location),
+                Some(DefUse::Drop) => self.insert_drop(local_with_region, location),
+                _ => (),
+            }
+        }
+    }
+}
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs
index a9b69cfe761..d6fdd1c849c 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs
@@ -8,26 +8,24 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use borrow_check::nll::region_infer::values::RegionValueElements;
 use borrow_check::nll::constraints::ConstraintSet;
-use borrow_check::nll::type_check::AtLocation;
-use borrow_check::nll::{LocalWithRegion, NllLivenessMap};
+use borrow_check::nll::NllLivenessMap;
 use borrow_check::nll::universal_regions::UniversalRegions;
-use dataflow::move_paths::{HasMoveData, MoveData};
+use dataflow::move_paths::MoveData;
 use dataflow::MaybeInitializedPlaces;
-use dataflow::{FlowAtLocation, FlowsAtLocation};
-use rustc::infer::canonical::QueryRegionConstraint;
-use rustc::mir::{BasicBlock, Location, Mir};
-use rustc::traits::query::dropck_outlives::DropckOutlivesResult;
-use rustc::traits::query::type_op::outlives::DropckOutlives;
-use rustc::traits::query::type_op::TypeOp;
-use rustc::ty::{RegionVid, Ty, TypeFoldable};
-use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use dataflow::FlowAtLocation;
+use rustc::mir::Mir;
+use rustc::ty::RegionVid;
+use rustc_data_structures::fx::FxHashSet;
 use std::rc::Rc;
-use util::liveness::{LiveVariableMap, LivenessResults};
 
 use super::TypeChecker;
 
 crate mod liveness_map;
+mod local_use_map;
+mod point_index_map;
+mod trace;
 
 /// Combines liveness analysis with initialization analysis to
 /// determine which variables are live at which points, both due to
@@ -38,40 +36,23 @@ crate mod liveness_map;
 /// NB. This computation requires normalization; therefore, it must be
 /// performed before
 pub(super) fn generate<'gcx, 'tcx>(
-    cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
+    typeck: &mut TypeChecker<'_, 'gcx, 'tcx>,
     mir: &Mir<'tcx>,
+    elements: &Rc<RegionValueElements>,
     flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>,
     move_data: &MoveData<'tcx>,
-) -> (LivenessResults<LocalWithRegion>, NllLivenessMap) {
+) {
+    debug!("liveness::generate");
     let free_regions = {
-        let borrowck_context = cx.borrowck_context.as_ref().unwrap();
+        let borrowck_context = typeck.borrowck_context.as_ref().unwrap();
         regions_that_outlive_free_regions(
-            cx.infcx.num_region_vars(),
+            typeck.infcx.num_region_vars(),
             &borrowck_context.universal_regions,
             &borrowck_context.constraints.outlives_constraints,
         )
     };
-    let liveness_map = NllLivenessMap::compute(cx.tcx(), &free_regions, mir);
-    let liveness = LivenessResults::compute(mir, &liveness_map);
-
-    // For everything else, it is only live where it is actually used.
-    if !liveness_map.is_empty() {
-        let mut generator = TypeLivenessGenerator {
-            cx,
-            mir,
-            liveness: &liveness,
-            flow_inits,
-            move_data,
-            drop_data: FxHashMap(),
-            map: &liveness_map,
-        };
-
-        for bb in mir.basic_blocks().indices() {
-            generator.add_liveness_constraints(bb);
-        }
-    }
-
-    (liveness, liveness_map)
+    let liveness_map = NllLivenessMap::compute(typeck.tcx(), &free_regions, mir);
+    trace::trace(typeck, mir, elements, flow_inits, move_data, &liveness_map);
 }
 
 /// Compute all regions that are (currently) known to outlive free
@@ -112,198 +93,3 @@ fn regions_that_outlive_free_regions(
     // Return the final set of things we visited.
     outlives_free_region
 }
-
-struct TypeLivenessGenerator<'gen, 'typeck, 'flow, 'gcx, 'tcx>
-where
-    'typeck: 'gen,
-    'flow: 'gen,
-    'tcx: 'typeck + 'flow,
-    'gcx: 'tcx,
-{
-    cx: &'gen mut TypeChecker<'typeck, 'gcx, 'tcx>,
-    mir: &'gen Mir<'tcx>,
-    liveness: &'gen LivenessResults<LocalWithRegion>,
-    flow_inits: &'gen mut FlowAtLocation<MaybeInitializedPlaces<'flow, 'gcx, 'tcx>>,
-    move_data: &'gen MoveData<'tcx>,
-    drop_data: FxHashMap<Ty<'tcx>, DropData<'tcx>>,
-    map: &'gen NllLivenessMap,
-}
-
-struct DropData<'tcx> {
-    dropck_result: DropckOutlivesResult<'tcx>,
-    region_constraint_data: Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>,
-}
-
-impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flow, 'gcx, 'tcx> {
-    /// 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, bb: BasicBlock) {
-        debug!("add_liveness_constraints(bb={:?})", bb);
-
-        self.liveness
-            .regular
-            .simulate_block(self.mir, bb, self.map, |location, live_locals| {
-                for live_local in live_locals.iter() {
-                    let local = self.map.from_live_var(live_local);
-                    let live_local_ty = self.mir.local_decls[local].ty;
-                    Self::push_type_live_constraint(&mut self.cx, live_local_ty, location);
-                }
-            });
-
-        let mut all_live_locals: Vec<(Location, Vec<LocalWithRegion>)> = vec![];
-        self.liveness
-            .drop
-            .simulate_block(self.mir, bb, self.map, |location, live_locals| {
-                all_live_locals.push((location, live_locals.iter().collect()));
-            });
-        debug!(
-            "add_liveness_constraints: all_live_locals={:#?}",
-            all_live_locals
-        );
-
-        let terminator_index = self.mir.basic_blocks()[bb].statements.len();
-        self.flow_inits.reset_to_entry_of(bb);
-        while let Some((location, live_locals)) = all_live_locals.pop() {
-            for live_local in live_locals {
-                debug!(
-                    "add_liveness_constraints: location={:?} live_local={:?}",
-                    location, live_local
-                );
-
-                if log_enabled!(::log::Level::Debug) {
-                    self.flow_inits.each_state_bit(|mpi_init| {
-                        debug!(
-                            "add_liveness_constraints: location={:?} initialized={:?}",
-                            location,
-                            &self.flow_inits.operator().move_data().move_paths[mpi_init]
-                        );
-                    });
-                }
-
-                let local = self.map.from_live_var(live_local);
-                let mpi = self.move_data.rev_lookup.find_local(local);
-                if let Some(initialized_child) = self.flow_inits.has_any_child_of(mpi) {
-                    debug!(
-                        "add_liveness_constraints: mpi={:?} has initialized child {:?}",
-                        self.move_data.move_paths[mpi],
-                        self.move_data.move_paths[initialized_child]
-                    );
-
-                    let local = self.map.from_live_var(live_local);
-                    let live_local_ty = self.mir.local_decls[local].ty;
-                    self.add_drop_live_constraint(live_local, live_local_ty, location);
-                }
-            }
-
-            if location.statement_index == terminator_index {
-                debug!(
-                    "add_liveness_constraints: reconstruct_terminator_effect from {:#?}",
-                    location
-                );
-                self.flow_inits.reconstruct_terminator_effect(location);
-            } else {
-                debug!(
-                    "add_liveness_constraints: reconstruct_statement_effect from {:#?}",
-                    location
-                );
-                self.flow_inits.reconstruct_statement_effect(location);
-            }
-            self.flow_inits.apply_local_effect(location);
-        }
-    }
-
-    /// Some variable with type `live_ty` is "regular live" at
-    /// `location` -- i.e., it may be used later. This means that all
-    /// regions appearing in the type `live_ty` must be live at
-    /// `location`.
-    fn push_type_live_constraint<T>(
-        cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
-        value: T,
-        location: Location,
-    ) where
-        T: TypeFoldable<'tcx>,
-    {
-        debug!(
-            "push_type_live_constraint(live_ty={:?}, location={:?})",
-            value, location
-        );
-
-        cx.tcx().for_each_free_region(&value, |live_region| {
-            if let Some(ref mut borrowck_context) = cx.borrowck_context {
-                let region_vid = borrowck_context
-                    .universal_regions
-                    .to_region_vid(live_region);
-                borrowck_context
-                    .constraints
-                    .liveness_constraints
-                    .add_element(region_vid, location);
-
-                if let Some(all_facts) = borrowck_context.all_facts {
-                    let start_index = borrowck_context.location_table.start_index(location);
-                    all_facts.region_live_at.push((region_vid, start_index));
-
-                    let mid_index = borrowck_context.location_table.mid_index(location);
-                    all_facts.region_live_at.push((region_vid, mid_index));
-                }
-            }
-        });
-    }
-
-    /// Some variable with type `live_ty` is "drop live" at `location`
-    /// -- i.e., it may be dropped later. This means that *some* of
-    /// the regions in its type must be live at `location`. The
-    /// precise set will depend on the dropck constraints, and in
-    /// particular this takes `#[may_dangle]` into account.
-    fn add_drop_live_constraint(
-        &mut self,
-        dropped_local: LocalWithRegion,
-        dropped_ty: Ty<'tcx>,
-        location: Location,
-    ) {
-        debug!(
-            "add_drop_live_constraint(dropped_local={:?}, dropped_ty={:?}, location={:?})",
-            dropped_local, dropped_ty, location
-        );
-
-        let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({
-            let cx = &mut self.cx;
-            move || Self::compute_drop_data(cx, dropped_ty)
-        });
-
-        if let Some(data) = &drop_data.region_constraint_data {
-            self.cx.push_region_constraints(location.boring(), data);
-        }
-
-        drop_data.dropck_result.report_overflows(
-            self.cx.infcx.tcx,
-            self.mir.source_info(location).span,
-            dropped_ty,
-        );
-
-        // All things in the `outlives` array may be touched by
-        // the destructor and must be live at this point.
-        for &kind in &drop_data.dropck_result.kinds {
-            Self::push_type_live_constraint(&mut self.cx, kind, location);
-        }
-    }
-
-    fn compute_drop_data(
-        cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
-        dropped_ty: Ty<'tcx>,
-    ) -> DropData<'tcx> {
-        debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,);
-
-        let param_env = cx.param_env;
-        let (dropck_result, region_constraint_data) = param_env
-            .and(DropckOutlives::new(dropped_ty))
-            .fully_perform(cx.infcx)
-            .unwrap();
-
-        DropData {
-            dropck_result,
-            region_constraint_data,
-        }
-    }
-}
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/point_index_map.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/point_index_map.rs
new file mode 100644
index 00000000000..c2c21aa0d8d
--- /dev/null
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/point_index_map.rs
@@ -0,0 +1,78 @@
+// 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 borrow_check::nll::region_infer::values::PointIndex;
+use borrow_check::nll::region_infer::values::RegionValueElements;
+use rustc::mir::{BasicBlock, Location, Mir};
+use rustc_data_structures::indexed_vec::{Idx, IndexVec};
+use std::rc::Rc;
+
+/// A little data structure that makes it more efficient to find the
+/// predecessors of each point.
+crate struct PointIndexMap<'me, 'tcx> {
+    elements: &'me Rc<RegionValueElements>,
+    mir: &'me Mir<'tcx>,
+    basic_block_heads: IndexVec<PointIndex, Option<BasicBlock>>,
+}
+
+impl PointIndexMap<'m, 'tcx> {
+    crate fn new(elements: &'m Rc<RegionValueElements>, mir: &'m Mir<'tcx>) -> Self {
+        let mut basic_block_heads = IndexVec::from_elem_n(None, elements.num_points());
+
+        for (bb, first_point) in elements.head_indices() {
+            basic_block_heads[first_point] = Some(bb);
+        }
+
+        PointIndexMap {
+            elements,
+            mir,
+            basic_block_heads,
+        }
+    }
+
+    crate fn num_points(&self) -> usize {
+        self.elements.num_points()
+    }
+
+    crate fn location_of(&self, index: PointIndex) -> Location {
+        let mut statement_index = 0;
+
+        for &opt_bb in self.basic_block_heads.raw[..= index.index()].iter().rev() {
+            if let Some(block) = opt_bb {
+                return Location { block, statement_index };
+            }
+
+            statement_index += 1;
+        }
+
+        bug!("did not find basic block as expected for index = {:?}", index)
+    }
+
+    crate fn push_predecessors(&self, index: PointIndex, stack: &mut Vec<PointIndex>) {
+        match self.basic_block_heads[index] {
+            // If this is a basic block head, then the predecessors are
+            // the the terminators of other basic blocks
+            Some(bb_head) => {
+                stack.extend(
+                    self.mir
+                        .predecessors_for(bb_head)
+                        .iter()
+                        .map(|&pred_bb| self.mir.terminator_loc(pred_bb))
+                        .map(|pred_loc| self.elements.point_from_location(pred_loc)),
+                );
+            }
+
+            // Otherwise, the pred is just the previous statement
+            None => {
+                stack.push(PointIndex::new(index.index() - 1));
+            }
+        }
+    }
+}
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs
new file mode 100644
index 00000000000..e8d22827117
--- /dev/null
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs
@@ -0,0 +1,544 @@
+// 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 borrow_check::nll::region_infer::values::{self, PointIndex, RegionValueElements};
+use borrow_check::nll::type_check::liveness::liveness_map::{LocalWithRegion, NllLivenessMap};
+use borrow_check::nll::type_check::liveness::local_use_map::LocalUseMap;
+use borrow_check::nll::type_check::liveness::point_index_map::PointIndexMap;
+use borrow_check::nll::type_check::AtLocation;
+use borrow_check::nll::type_check::TypeChecker;
+use dataflow::move_paths::indexes::MovePathIndex;
+use dataflow::move_paths::MoveData;
+use dataflow::{FlowAtLocation, FlowsAtLocation, MaybeInitializedPlaces};
+use rustc::infer::canonical::QueryRegionConstraint;
+use rustc::mir::{BasicBlock, Local, Location, Mir};
+use rustc::traits::query::dropck_outlives::DropckOutlivesResult;
+use rustc::traits::query::type_op::outlives::DropckOutlives;
+use rustc::traits::query::type_op::TypeOp;
+use rustc::ty::{Ty, TypeFoldable};
+use rustc_data_structures::bitvec::BitArray;
+use rustc_data_structures::fx::FxHashMap;
+use std::rc::Rc;
+use util::liveness::LiveVariableMap;
+
+pub(super) fn trace(
+    typeck: &mut TypeChecker<'_, 'gcx, 'tcx>,
+    mir: &Mir<'tcx>,
+    elements: &Rc<RegionValueElements>,
+    flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>,
+    move_data: &MoveData<'tcx>,
+    liveness_map: &NllLivenessMap,
+) {
+    debug!("trace()");
+
+    if liveness_map.is_empty() {
+        return;
+    }
+
+    let local_use_map = &LocalUseMap::build(liveness_map, elements, mir);
+    let point_index_map = &PointIndexMap::new(elements, mir);
+
+    let cx = LivenessContext {
+        typeck,
+        mir,
+        flow_inits,
+        elements,
+        local_use_map,
+        move_data,
+        liveness_map,
+        point_index_map,
+        drop_data: FxHashMap::default(),
+    };
+
+    LivenessResults::new(cx).compute_for_all_locals();
+}
+
+/// Contextual state for the type-liveness generator.
+struct LivenessContext<'me, 'typeck, 'flow, 'gcx, 'tcx>
+where
+    'typeck: 'me,
+    'flow: 'me,
+    'tcx: 'typeck + 'flow,
+    'gcx: 'tcx,
+{
+    /// Current type-checker, giving us our inference context etc.
+    typeck: &'me mut TypeChecker<'typeck, 'gcx, 'tcx>,
+
+    /// Defines the `PointIndex` mapping
+    elements: &'me RegionValueElements,
+
+    /// MIR we are analyzing.
+    mir: &'me Mir<'tcx>,
+
+    /// Mapping to/from the various indices used for initialization tracking.
+    move_data: &'me MoveData<'tcx>,
+
+    /// Cache for the results of `dropck_outlives` query.
+    drop_data: FxHashMap<Ty<'tcx>, DropData<'tcx>>,
+
+    /// Results of dataflow tracking which variables (and paths) have been
+    /// initialized.
+    flow_inits: &'me mut FlowAtLocation<MaybeInitializedPlaces<'flow, 'gcx, 'tcx>>,
+
+    /// Index indicating where each variable is assigned, used, or
+    /// dropped.
+    local_use_map: &'me LocalUseMap<'me>,
+
+    point_index_map: &'me PointIndexMap<'me, 'tcx>,
+
+    /// Map tracking which variables need liveness computation.
+    liveness_map: &'me NllLivenessMap,
+}
+
+struct DropData<'tcx> {
+    dropck_result: DropckOutlivesResult<'tcx>,
+    region_constraint_data: Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>,
+}
+
+struct LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx>
+where
+    'typeck: 'me,
+    'flow: 'me,
+    'tcx: 'typeck + 'flow,
+    'gcx: 'tcx,
+{
+    cx: LivenessContext<'me, 'typeck, 'flow, 'gcx, 'tcx>,
+
+    /// Set of points that define the current local.
+    defs: BitArray<PointIndex>,
+
+    /// Points where the current variable is "use live" -- meaning
+    /// that there is a future "full use" that may use its value.
+    use_live_at: BitArray<PointIndex>,
+
+    /// Points where the current variable is "drop live" -- meaning
+    /// that there is no future "full use" that may use its value, but
+    /// there is a future drop.
+    drop_live_at: BitArray<PointIndex>,
+
+    /// Locations where drops may occur.
+    drop_locations: Vec<Location>,
+
+    /// Stack used when doing (reverse) DFS.
+    stack: Vec<PointIndex>,
+}
+
+impl LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> {
+    fn new(cx: LivenessContext<'me, 'typeck, 'flow, 'gcx, 'tcx>) -> Self {
+        let num_points = cx.point_index_map.num_points();
+        LivenessResults {
+            cx,
+            defs: BitArray::new(num_points),
+            use_live_at: BitArray::new(num_points),
+            drop_live_at: BitArray::new(num_points),
+            drop_locations: vec![],
+            stack: vec![],
+        }
+    }
+
+    fn compute_for_all_locals(&mut self) {
+        for live_local in self.cx.liveness_map.to_local.indices() {
+            let local = self.cx.liveness_map.from_live_var(live_local);
+            debug!("local={:?} live_local={:?}", local, live_local);
+
+            self.reset_local_state();
+            self.add_defs_for(live_local);
+            self.compute_use_live_points_for(live_local);
+            self.compute_drop_live_points_for(live_local);
+
+            let local_ty = self.cx.mir.local_decls[local].ty;
+
+            if !self.use_live_at.is_empty() {
+                self.cx.add_use_live_facts_for(local_ty, &self.use_live_at);
+            }
+
+            if !self.drop_live_at.is_empty() {
+                self.cx.add_drop_live_facts_for(
+                    local,
+                    local_ty,
+                    &self.drop_locations,
+                    &self.drop_live_at,
+                );
+            }
+        }
+    }
+
+    /// Clear the value of fields that are "per local variable".
+    fn reset_local_state(&mut self) {
+        self.defs.clear();
+        self.use_live_at.clear();
+        self.drop_live_at.clear();
+        self.drop_locations.clear();
+        assert!(self.stack.is_empty());
+    }
+
+    /// Adds the definitions of `local` into `self.defs`.
+    fn add_defs_for(&mut self, live_local: LocalWithRegion) {
+        for def in self.cx.local_use_map.defs(live_local) {
+            debug!("- defined at {:?}", def);
+            self.defs.insert(def);
+        }
+    }
+
+    /// Compute all points where local is "use live" -- meaning its
+    /// current value may be used later (except by a drop). This is
+    /// done by walking backwards from each use of `live_local` until we
+    /// find a `def` of local.
+    ///
+    /// Requires `add_defs_for(live_local)` to have been executed.
+    fn compute_use_live_points_for(&mut self, live_local: LocalWithRegion) {
+        debug!("compute_use_live_points_for(live_local={:?})", live_local);
+
+        self.stack.extend(self.cx.local_use_map.uses(live_local));
+        while let Some(p) = self.stack.pop() {
+            if self.defs.contains(p) {
+                continue;
+            }
+
+            if self.use_live_at.insert(p) {
+                self.cx
+                    .point_index_map
+                    .push_predecessors(p, &mut self.stack)
+            }
+        }
+    }
+
+    /// Compute all points where local is "drop live" -- meaning its
+    /// current value may be dropped later (but not used). This is
+    /// done by iterating over the drops of `local` where `local` (or
+    /// some subpart of `local`) is initialized. For each such drop,
+    /// we walk backwards until we find a point where `local` is
+    /// either defined or use-live.
+    ///
+    /// Requires `compute_use_live_points_for` and `add_defs_for` to
+    /// have been executed.
+    fn compute_drop_live_points_for(&mut self, live_local: LocalWithRegion) {
+        debug!("compute_drop_live_points_for(live_local={:?})", live_local);
+
+        let local = self.cx.liveness_map.from_live_var(live_local);
+        let mpi = self.cx.move_data.rev_lookup.find_local(local);
+        debug!("compute_drop_live_points_for: mpi = {:?}", mpi);
+
+        // Find the drops where `local` is initialized.
+        for drop_point in self.cx.local_use_map.drops(live_local) {
+            let location = self.cx.point_index_map.location_of(drop_point);
+            debug_assert_eq!(self.cx.mir.terminator_loc(location.block), location,);
+
+            if self.cx.initialized_at_terminator(location.block, mpi) {
+                if self.drop_live_at.insert(drop_point) {
+                    self.drop_locations.push(location);
+                    self.stack.push(drop_point);
+                }
+            }
+        }
+
+        debug!(
+            "compute_drop_live_points_for: drop_locations={:?}",
+            self.drop_locations
+        );
+
+        // Reverse DFS. But for drops, we do it a bit differently.
+        // The stack only ever stores *terminators of blocks*. Within
+        // a block, we walk back the statements in an inner loop.
+        'next_block: while let Some(term_point) = self.stack.pop() {
+            self.compute_drop_live_points_for_block(mpi, term_point);
+        }
+    }
+
+    /// Executes one iteration of the drop-live analysis loop.
+    ///
+    /// The parameter `mpi` is the `MovePathIndex` of the local variable
+    /// we are currently analyzing.
+    ///
+    /// The point `term_point` represents some terminator in the MIR,
+    /// where the local `mpi` is drop-live on entry to that terminator.
+    ///
+    /// This method adds all drop-live points within the block and --
+    /// where applicable -- pushes the terminators of preceding blocks
+    /// onto `self.stack`.
+    fn compute_drop_live_points_for_block(&mut self, mpi: MovePathIndex, term_point: PointIndex) {
+        debug!(
+            "compute_drop_live_points_for_block(mpi={:?}, term_point={:?})",
+            self.cx.move_data.move_paths[mpi].place,
+            self.cx.point_index_map.location_of(term_point),
+        );
+
+        // We are only invoked with terminators where `mpi` is
+        // drop-live on entry.
+        debug_assert!(self.drop_live_at.contains(term_point));
+
+        // Otherwise, scan backwards through the statements in the
+        // block.  One of them may be either a definition or use
+        // live point.
+        let term_location = self.cx.elements.to_location(term_point);
+        debug_assert_eq!(
+            self.cx.mir.terminator_loc(term_location.block),
+            term_location,
+        );
+        let block = term_location.block;
+        let entry_point = self.cx.elements.entry_point(term_location.block);
+        for p in (entry_point..term_point).rev() {
+            debug!(
+                "compute_drop_live_points_for_block: p = {:?}",
+                self.cx.point_index_map.location_of(p),
+            );
+
+            if self.defs.contains(p) {
+                debug!("compute_drop_live_points_for_block: def site");
+                return;
+            }
+
+            if self.use_live_at.contains(p) {
+                debug!("compute_drop_live_points_for_block: use-live at {:?}", p);
+                return;
+            }
+
+            if !self.drop_live_at.insert(p) {
+                debug!("compute_drop_live_points_for_block: already drop-live");
+                return;
+            }
+        }
+
+        for &pred_block in self.cx.mir.predecessors_for(block).iter() {
+            debug!(
+                "compute_drop_live_points_for_block: pred_block = {:?}",
+                pred_block,
+            );
+
+            // Check whether the variable is (at least partially)
+            // initialized at the exit of this predecessor. If so, we
+            // want to enqueue it on our list. If not, go check the
+            // next block.
+            //
+            // Note that we only need to check whether `live_local`
+            // became de-initialized at basic block boundaries. If it
+            // were to become de-initialized within the block, that
+            // would have been a "use-live" transition in the earlier
+            // loop, and we'd have returned already.
+            //
+            // NB. It's possible that the pred-block ends in a call
+            // which stores to the variable; in that case, the
+            // variable may be uninitialized "at exit" because this
+            // call only considers the *unconditional effects* of the
+            // terminator. *But*, in that case, the terminator is also
+            // a *definition* of the variable, in which case we want
+            // to stop the search anyhow. (But see Note 1 below.)
+            if !self.cx.initialized_at_exit(pred_block, mpi) {
+                debug!("compute_drop_live_points_for_block: not initialized");
+                continue;
+            }
+
+            let pred_term_loc = self.cx.mir.terminator_loc(pred_block);
+            let pred_term_point = self.cx.elements.point_from_location(pred_term_loc);
+
+            // If the terminator of this predecessor either *assigns*
+            // our value or is a "normal use", then stop.
+            if self.defs.contains(pred_term_point) {
+                debug!(
+                    "compute_drop_live_points_for_block: defined at {:?}",
+                    pred_term_loc
+                );
+                continue;
+            }
+
+            if self.use_live_at.contains(pred_term_point) {
+                debug!(
+                    "compute_drop_live_points_for_block: use-live at {:?}",
+                    pred_term_loc
+                );
+                continue;
+            }
+
+            // Otherwise, we are drop-live on entry to the terminator,
+            // so walk it.
+            if self.drop_live_at.insert(pred_term_point) {
+                debug!("compute_drop_live_points_for_block: pushed to stack");
+                self.stack.push(pred_term_point);
+            }
+        }
+
+        // Note 1. There is a weird scenario that you might imagine
+        // being problematic here, but which actually cannot happen.
+        // The problem would be if we had a variable that *is* initialized
+        // (but dead) on entry to the terminator, and where the current value
+        // will be dropped in the case of unwind. In that case, we ought to
+        // consider `X` to be drop-live in between the last use and call.
+        // Here is the example:
+        //
+        // ```
+        // BB0 {
+        //   X = ...
+        //   use(X); // last use
+        //   ...     // <-- X ought to be drop-live here
+        //   X = call() goto BB1 unwind BB2
+        // }
+        //
+        // BB1 {
+        //   DROP(X)
+        // }
+        //
+        // BB2 {
+        //   DROP(X)
+        // }
+        // ```
+        //
+        // However, the current code would, when walking back from BB2,
+        // simply stop and never explore BB0. This seems bad! But it turns
+        // out this code is flawed anyway -- note that the existing value of
+        // `X` would leak in the case where unwinding did *not* occur.
+        //
+        // What we *actually* generate is a store to a temporary
+        // for the call (`TMP = call()...`) and then a
+        // `DropAndReplace` to swap that with `X`
+        // (`DropAndReplace` has very particular semantics).
+    }
+}
+
+impl LivenessContext<'_, '_, '_, '_, 'tcx> {
+    /// True if the local variable (or some part of it) is initialized in
+    /// the terminator of `block`. We need to check this to determine if a
+    /// DROP of some local variable will have an effect -- note that
+    /// drops, as they may unwind, are always terminators.
+    fn initialized_at_terminator(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
+        // Compute the set of initialized paths at terminator of block
+        // by resetting to the start of the block and then applying
+        // the effects of all statements. This is the only way to get
+        // "just ahead" of a terminator.
+        self.flow_inits.reset_to_entry_of(block);
+        for statement_index in 0..self.mir[block].statements.len() {
+            let location = Location {
+                block,
+                statement_index,
+            };
+            self.flow_inits.reconstruct_statement_effect(location);
+            self.flow_inits.apply_local_effect(location);
+        }
+
+        self.flow_inits.has_any_child_of(mpi).is_some()
+    }
+
+    /// True if the path `mpi` (or some part of it) is initialized at
+    /// the exit of `block`.
+    ///
+    /// **Warning:** Does not account for the result of `Call`
+    /// instructions.
+    fn initialized_at_exit(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
+        self.flow_inits.reset_to_exit_of(block);
+        self.flow_inits.has_any_child_of(mpi).is_some()
+    }
+
+    /// Store the result that all regions in `value` are live for the
+    /// points `live_at`.
+    fn add_use_live_facts_for(
+        &mut self,
+        value: impl TypeFoldable<'tcx>,
+        live_at: &BitArray<PointIndex>,
+    ) {
+        debug!("add_use_live_facts_for(value={:?})", value);
+
+        Self::make_all_regions_live(self.elements, &mut self.typeck, value, live_at)
+    }
+
+    /// Some variable with type `live_ty` is "drop live" at `location`
+    /// -- i.e., it may be dropped later. This means that *some* of
+    /// the regions in its type must be live at `location`. The
+    /// precise set will depend on the dropck constraints, and in
+    /// particular this takes `#[may_dangle]` into account.
+    fn add_drop_live_facts_for(
+        &mut self,
+        dropped_local: Local,
+        dropped_ty: Ty<'tcx>,
+        drop_locations: &[Location],
+        live_at: &BitArray<PointIndex>,
+    ) {
+        debug!(
+            "add_drop_live_constraint(\
+             dropped_local={:?}, \
+             dropped_ty={:?}, \
+             drop_locations={:?}, \
+             live_at={:?})",
+            dropped_local,
+            dropped_ty,
+            drop_locations,
+            values::location_set_str(self.elements, live_at.iter()),
+        );
+
+        let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({
+            let typeck = &mut self.typeck;
+            move || Self::compute_drop_data(typeck, dropped_ty)
+        });
+
+        if let Some(data) = &drop_data.region_constraint_data {
+            for &drop_location in drop_locations {
+                self.typeck
+                    .push_region_constraints(drop_location.boring(), data);
+            }
+        }
+
+        drop_data.dropck_result.report_overflows(
+            self.typeck.infcx.tcx,
+            self.mir.source_info(*drop_locations.first().unwrap()).span,
+            dropped_ty,
+        );
+
+        // All things in the `outlives` array may be touched by
+        // the destructor and must be live at this point.
+        for &kind in &drop_data.dropck_result.kinds {
+            Self::make_all_regions_live(self.elements, &mut self.typeck, kind, live_at);
+        }
+    }
+
+    fn make_all_regions_live(
+        elements: &RegionValueElements,
+        typeck: &mut TypeChecker<'_, '_, 'tcx>,
+        value: impl TypeFoldable<'tcx>,
+        live_at: &BitArray<PointIndex>,
+    ) {
+        debug!("make_all_regions_live(value={:?})", value);
+        debug!(
+            "make_all_regions_live: live_at={}",
+            values::location_set_str(elements, live_at.iter()),
+        );
+
+        let tcx = typeck.tcx();
+        tcx.for_each_free_region(&value, |live_region| {
+            let borrowck_context = typeck.borrowck_context.as_mut().unwrap();
+            let live_region_vid = borrowck_context
+                .universal_regions
+                .to_region_vid(live_region);
+            borrowck_context
+                .constraints
+                .liveness_constraints
+                .add_elements(live_region_vid, live_at);
+
+            if let Some(_) = borrowck_context.all_facts {
+                bug!("polonius liveness facts not implemented yet")
+            }
+        });
+    }
+
+    fn compute_drop_data(
+        typeck: &mut TypeChecker<'_, 'gcx, 'tcx>,
+        dropped_ty: Ty<'tcx>,
+    ) -> DropData<'tcx> {
+        debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,);
+
+        let param_env = typeck.param_env;
+        let (dropck_result, region_constraint_data) = param_env
+            .and(DropckOutlives::new(dropped_ty))
+            .fully_perform(typeck.infcx)
+            .unwrap();
+
+        DropData {
+            dropck_result,
+            region_constraint_data,
+        }
+    }
+}
diff --git a/src/librustc_mir/borrow_check/nll/type_check/mod.rs b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
index 27417466c68..3a5857f775f 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
@@ -18,9 +18,7 @@ use borrow_check::nll::facts::AllFacts;
 use borrow_check::nll::region_infer::values::{LivenessValues, RegionValueElements};
 use borrow_check::nll::region_infer::{ClosureRegionRequirementsExt, TypeTest};
 use borrow_check::nll::type_check::free_region_relations::{CreateResult, UniversalRegionRelations};
-use borrow_check::nll::type_check::liveness::liveness_map::NllLivenessMap;
 use borrow_check::nll::universal_regions::UniversalRegions;
-use borrow_check::nll::LocalWithRegion;
 use borrow_check::nll::ToRegionVid;
 use dataflow::move_paths::MoveData;
 use dataflow::FlowAtLocation;
@@ -43,7 +41,6 @@ use std::fmt;
 use std::rc::Rc;
 use syntax_pos::{Span, DUMMY_SP};
 use transform::{MirPass, MirSource};
-use util::liveness::LivenessResults;
 
 use rustc_data_structures::fx::FxHashSet;
 use rustc_data_structures::indexed_vec::Idx;
@@ -143,7 +140,7 @@ pub(crate) fn type_check<'gcx, 'tcx>(
         all_facts,
     );
 
-    let (liveness, liveness_map) = {
+    {
         let mut borrowck_context = BorrowCheckContext {
             universal_regions,
             location_table,
@@ -169,16 +166,14 @@ pub(crate) fn type_check<'gcx, 'tcx>(
                     &universal_region_relations,
                     &normalized_inputs_and_output,
                 );
-                liveness::generate(cx, mir, flow_inits, move_data)
+                liveness::generate(cx, mir, elements, flow_inits, move_data);
             },
-        )
-    };
+        );
+    }
 
     MirTypeckResults {
         constraints,
         universal_region_relations,
-        liveness,
-        liveness_map,
     }
 }
 
@@ -672,8 +667,6 @@ struct BorrowCheckContext<'a, 'tcx: 'a> {
 crate struct MirTypeckResults<'tcx> {
     crate constraints: MirTypeckRegionConstraints<'tcx>,
     crate universal_region_relations: Rc<UniversalRegionRelations<'tcx>>,
-    crate liveness: LivenessResults<LocalWithRegion>,
-    crate liveness_map: NllLivenessMap,
 }
 
 /// A collection of region constraints that must be satisfied for the
diff --git a/src/librustc_mir/dataflow/at_location.rs b/src/librustc_mir/dataflow/at_location.rs
index 1f7faa21a12..d97c0c9b430 100644
--- a/src/librustc_mir/dataflow/at_location.rs
+++ b/src/librustc_mir/dataflow/at_location.rs
@@ -28,6 +28,15 @@ pub trait FlowsAtLocation {
     /// Reset the state bitvector to represent the entry to block `bb`.
     fn reset_to_entry_of(&mut self, bb: BasicBlock);
 
+    /// Reset the state bitvector to represent the exit of the
+    /// terminator of block `bb`.
+    ///
+    /// **Important:** In the case of a `Call` terminator, these
+    /// effects do *not* include the result of storing the destination
+    /// of the call, since that is edge-dependent (in other words, the
+    /// effects don't apply to the unwind edge).
+    fn reset_to_exit_of(&mut self, bb: BasicBlock);
+
     /// Build gen + kill sets for statement at `loc`.
     ///
     /// Note that invoking this method alone does not change the
@@ -142,6 +151,12 @@ impl<BD> FlowsAtLocation for FlowAtLocation<BD>
         self.curr_state.overwrite(self.base_results.sets().on_entry_set_for(bb.index()));
     }
 
+    fn reset_to_exit_of(&mut self, bb: BasicBlock) {
+        self.reset_to_entry_of(bb);
+        self.curr_state.union(self.base_results.sets().gen_set_for(bb.index()));
+        self.curr_state.subtract(self.base_results.sets().kill_set_for(bb.index()));
+    }
+
     fn reconstruct_statement_effect(&mut self, loc: Location) {
         self.stmt_gen.clear();
         self.stmt_kill.clear();
diff --git a/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.rs b/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.rs
index 5538eca3629..808114f3fa9 100644
--- a/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.rs
+++ b/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.rs
@@ -8,10 +8,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//compile-flags: -Z emit-end-regions -Zborrowck=mir
-
-
 #![allow(warnings)]
+#![feature(nll)]
 
 struct Wrap<'p> { p: &'p mut i32 }
 
diff --git a/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.stderr b/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.stderr
index 327454ee60e..6fc26d502d3 100644
--- a/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.stderr
+++ b/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.stderr
@@ -1,5 +1,5 @@
 error[E0506]: cannot assign to `x` because it is borrowed
-  --> $DIR/maybe-initialized-drop-implicit-fragment-drop.rs:32:5
+  --> $DIR/maybe-initialized-drop-implicit-fragment-drop.rs:30:5
    |
 LL |     let wrap = Wrap { p: &mut x };
    |                          ------ borrow of `x` occurs here