Auto merge of #53177 - nikomatsakis:nll-redundant-borrows-and-escaping-values, r=pnkfelix

optimize redundant borrows and escaping paths in NLL

This builds on https://github.com/rust-lang/rust/pull/53168 and adds a commit that addresses https://github.com/rust-lang/rust/issues/53176 -- or at least I think it does. I marked this as WIP because I want to see the test results (and measure the performance). I also want to double check we're not adding in any unsoundness here.

15 files changed, 388 insertions, 202 deletions

diff --git a/src/librustc_mir/borrow_check/borrow_set.rs b/src/librustc_mir/borrow_check/borrow_set.rs
index fe33dc0a58a..2e0cbf4326b 100644
--- a/src/librustc_mir/borrow_check/borrow_set.rs
+++ b/src/librustc_mir/borrow_check/borrow_set.rs
@@ -159,7 +159,7 @@ impl<'a, 'gcx, 'tcx> Visitor<'tcx> for GatherBorrows<'a, 'gcx, 'tcx> {
         location: mir::Location,
     ) {
         if let mir::Rvalue::Ref(region, kind, ref borrowed_place) = *rvalue {
-            if borrowed_place.is_unsafe_place(self.tcx, self.mir) {
+            if borrowed_place.ignore_borrow(self.tcx, self.mir) {
                 return;
             }
 
diff --git a/src/librustc_mir/borrow_check/nll/constraints/graph.rs b/src/librustc_mir/borrow_check/nll/constraints/graph.rs
index 5f05ae8ade5..1a1094b570b 100644
--- a/src/librustc_mir/borrow_check/nll/constraints/graph.rs
+++ b/src/librustc_mir/borrow_check/nll/constraints/graph.rs
@@ -8,27 +8,80 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use borrow_check::nll::constraints::{ConstraintIndex, ConstraintSet};
+use borrow_check::nll::constraints::{ConstraintIndex, ConstraintSet, OutlivesConstraint};
 use rustc::ty::RegionVid;
 use rustc_data_structures::graph;
 use rustc_data_structures::indexed_vec::IndexVec;
 
-crate struct ConstraintGraph {
+/// The construct graph organizes the constraints by their end-points.
+/// It can be used to view a `R1: R2` constraint as either an edge `R1
+/// -> R2` or `R2 -> R1` depending on the direction type `D`.
+crate struct ConstraintGraph<D: ConstraintGraphDirecton> {
+    _direction: D,
     first_constraints: IndexVec<RegionVid, Option<ConstraintIndex>>,
     next_constraints: IndexVec<ConstraintIndex, Option<ConstraintIndex>>,
 }
 
-impl ConstraintGraph {
+crate type NormalConstraintGraph = ConstraintGraph<Normal>;
+
+crate type ReverseConstraintGraph = ConstraintGraph<Reverse>;
+
+/// Marker trait that controls whether a `R1: R2` constraint
+/// represents an edge `R1 -> R2` or `R2 -> R1`.
+crate trait ConstraintGraphDirecton: Copy + 'static {
+    fn start_region(c: &OutlivesConstraint) -> RegionVid;
+    fn end_region(c: &OutlivesConstraint) -> RegionVid;
+}
+
+/// In normal mode, a `R1: R2` constraint results in an edge `R1 ->
+/// R2`. This is what we use when constructing the SCCs for
+/// inference. This is because we compute the value of R1 by union'ing
+/// all the things that it relies on.
+#[derive(Copy, Clone, Debug)]
+crate struct Normal;
+
+impl ConstraintGraphDirecton for Normal {
+    fn start_region(c: &OutlivesConstraint) -> RegionVid {
+        c.sup
+    }
+
+    fn end_region(c: &OutlivesConstraint) -> RegionVid {
+        c.sub
+    }
+}
+
+/// In reverse mode, a `R1: R2` constraint results in an edge `R2 ->
+/// R1`. We use this for optimizing liveness computation, because then
+/// we wish to iterate from a region (e.g., R2) to all the regions
+/// that will outlive it (e.g., R1).
+#[derive(Copy, Clone, Debug)]
+crate struct Reverse;
+
+impl ConstraintGraphDirecton for Reverse {
+    fn start_region(c: &OutlivesConstraint) -> RegionVid {
+        c.sub
+    }
+
+    fn end_region(c: &OutlivesConstraint) -> RegionVid {
+        c.sup
+    }
+}
+
+impl<D: ConstraintGraphDirecton> ConstraintGraph<D> {
     /// Create a "dependency graph" where each region constraint `R1:
     /// R2` is treated as an edge `R1 -> R2`. We use this graph to
     /// construct SCCs for region inference but also for error
     /// reporting.
-    crate fn new(set: &ConstraintSet, num_region_vars: usize) -> Self {
+    crate fn new(
+        direction: D,
+        set: &ConstraintSet,
+        num_region_vars: usize,
+    ) -> Self {
         let mut first_constraints = IndexVec::from_elem_n(None, num_region_vars);
         let mut next_constraints = IndexVec::from_elem(None, &set.constraints);
 
         for (idx, constraint) in set.constraints.iter_enumerated().rev() {
-            let head = &mut first_constraints[constraint.sup];
+            let head = &mut first_constraints[D::start_region(constraint)];
             let next = &mut next_constraints[idx];
             debug_assert!(next.is_none());
             *next = *head;
@@ -36,13 +89,21 @@ impl ConstraintGraph {
         }
 
         Self {
+            _direction: direction,
             first_constraints,
             next_constraints,
         }
     }
 
+    /// Given the constraint set from which this graph was built
+    /// creates a region graph so that you can iterate over *regions*
+    /// and not constraints.
+    crate fn region_graph<'rg>(&'rg self, set: &'rg ConstraintSet) -> RegionGraph<'rg, D> {
+        RegionGraph::new(set, self)
+    }
+
     /// Given a region `R`, iterate over all constraints `R: R1`.
-    crate fn outgoing_edges(&self, region_sup: RegionVid) -> Edges<'_> {
+    crate fn outgoing_edges(&self, region_sup: RegionVid) -> Edges<'_, D> {
         let first = self.first_constraints[region_sup];
         Edges {
             graph: self,
@@ -51,12 +112,12 @@ impl ConstraintGraph {
     }
 }
 
-crate struct Edges<'s> {
-    graph: &'s ConstraintGraph,
+crate struct Edges<'s, D: ConstraintGraphDirecton> {
+    graph: &'s ConstraintGraph<D>,
     pointer: Option<ConstraintIndex>,
 }
 
-impl<'s> Iterator for Edges<'s> {
+impl<'s, D: ConstraintGraphDirecton> Iterator for Edges<'s, D> {
     type Item = ConstraintIndex;
 
     fn next(&mut self) -> Option<Self::Item> {
@@ -69,17 +130,20 @@ impl<'s> Iterator for Edges<'s> {
     }
 }
 
-crate struct RegionGraph<'s> {
+/// This struct brings together a constraint set and a (normal, not
+/// reverse) constraint graph. It implements the graph traits and is
+/// usd for doing the SCC computation.
+crate struct RegionGraph<'s, D: ConstraintGraphDirecton> {
     set: &'s ConstraintSet,
-    constraint_graph: &'s ConstraintGraph,
+    constraint_graph: &'s ConstraintGraph<D>,
 }
 
-impl<'s> RegionGraph<'s> {
+impl<'s, D: ConstraintGraphDirecton> RegionGraph<'s, D> {
     /// Create a "dependency graph" where each region constraint `R1:
     /// R2` is treated as an edge `R1 -> R2`. We use this graph to
     /// construct SCCs for region inference but also for error
     /// reporting.
-    crate fn new(set: &'s ConstraintSet, constraint_graph: &'s ConstraintGraph) -> Self {
+    crate fn new(set: &'s ConstraintSet, constraint_graph: &'s ConstraintGraph<D>) -> Self {
         Self {
             set,
             constraint_graph,
@@ -88,7 +152,7 @@ impl<'s> RegionGraph<'s> {
 
     /// Given a region `R`, iterate over all regions `R1` such that
     /// there exists a constraint `R: R1`.
-    crate fn sub_regions(&self, region_sup: RegionVid) -> Successors<'_> {
+    crate fn outgoing_regions(&self, region_sup: RegionVid) -> Successors<'_, D> {
         Successors {
             set: self.set,
             edges: self.constraint_graph.outgoing_edges(region_sup),
@@ -96,39 +160,39 @@ impl<'s> RegionGraph<'s> {
     }
 }
 
-crate struct Successors<'s> {
+crate struct Successors<'s, D: ConstraintGraphDirecton> {
     set: &'s ConstraintSet,
-    edges: Edges<'s>,
+    edges: Edges<'s, D>,
 }
 
-impl<'s> Iterator for Successors<'s> {
+impl<'s, D: ConstraintGraphDirecton> Iterator for Successors<'s, D> {
     type Item = RegionVid;
 
     fn next(&mut self) -> Option<Self::Item> {
-        self.edges.next().map(|c| self.set[c].sub)
+        self.edges.next().map(|c| D::end_region(&self.set[c]))
     }
 }
 
-impl<'s> graph::DirectedGraph for RegionGraph<'s> {
+impl<'s, D: ConstraintGraphDirecton> graph::DirectedGraph for RegionGraph<'s, D> {
     type Node = RegionVid;
 }
 
-impl<'s> graph::WithNumNodes for RegionGraph<'s> {
+impl<'s, D: ConstraintGraphDirecton> graph::WithNumNodes for RegionGraph<'s, D> {
     fn num_nodes(&self) -> usize {
         self.constraint_graph.first_constraints.len()
     }
 }
 
-impl<'s> graph::WithSuccessors for RegionGraph<'s> {
+impl<'s, D: ConstraintGraphDirecton> graph::WithSuccessors for RegionGraph<'s, D> {
     fn successors<'graph>(
         &'graph self,
         node: Self::Node,
     ) -> <Self as graph::GraphSuccessors<'graph>>::Iter {
-        self.sub_regions(node)
+        self.outgoing_regions(node)
     }
 }
 
-impl<'s, 'graph> graph::GraphSuccessors<'graph> for RegionGraph<'s> {
+impl<'s, 'graph, D: ConstraintGraphDirecton> graph::GraphSuccessors<'graph> for RegionGraph<'s, D> {
     type Item = RegionVid;
-    type Iter = Successors<'graph>;
+    type Iter = Successors<'graph, D>;
 }
diff --git a/src/librustc_mir/borrow_check/nll/constraints/mod.rs b/src/librustc_mir/borrow_check/nll/constraints/mod.rs
index 597241234cd..4cb92262ff0 100644
--- a/src/librustc_mir/borrow_check/nll/constraints/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/constraints/mod.rs
@@ -36,12 +36,20 @@ impl ConstraintSet {
         self.constraints.push(constraint);
     }
 
-    /// Constructs a graph from the constraint set; the graph makes it
-    /// easy to find the constraints affecting a particular region
-    /// (you should not mutate the set once this graph is
-    /// constructed).
-    crate fn graph(&self, num_region_vars: usize) -> graph::ConstraintGraph {
-        graph::ConstraintGraph::new(self, num_region_vars)
+    /// Constructs a "normal" graph from the constraint set; the graph makes it
+    /// easy to find the constraints affecting a particular region.
+    ///
+    /// NB: This graph contains a "frozen" view of the current
+    /// constraints.  any new constraints added to the `ConstraintSet`
+    /// after the graph is built will not be present in the graph.
+    crate fn graph(&self, num_region_vars: usize) -> graph::NormalConstraintGraph {
+        graph::ConstraintGraph::new(graph::Normal, self, num_region_vars)
+    }
+
+    /// Like `graph`, but constraints a reverse graph where `R1: R2`
+    /// represents an edge `R2 -> R1`.
+    crate fn reverse_graph(&self, num_region_vars: usize) -> graph::ReverseConstraintGraph {
+        graph::ConstraintGraph::new(graph::Reverse, self, num_region_vars)
     }
 
     /// Compute cycles (SCCs) in the graph of regions. In particular,
@@ -49,9 +57,9 @@ impl ConstraintSet {
     /// them into an SCC, and find the relationships between SCCs.
     crate fn compute_sccs(
         &self,
-        constraint_graph: &graph::ConstraintGraph,
+        constraint_graph: &graph::NormalConstraintGraph,
     ) -> Sccs<RegionVid, ConstraintSccIndex> {
-        let region_graph = &graph::RegionGraph::new(self, constraint_graph);
+        let region_graph = &constraint_graph.region_graph(self);
         Sccs::new(region_graph)
     }
 }
diff --git a/src/librustc_mir/borrow_check/nll/liveness_map.rs b/src/librustc_mir/borrow_check/nll/liveness_map.rs
deleted file mode 100644
index cbd9c9a4e1a..00000000000
--- a/src/librustc_mir/borrow_check/nll/liveness_map.rs
+++ /dev/null
@@ -1,77 +0,0 @@
-// 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.
-
-//! For the NLL computation, we need to compute liveness, but only for those
-//! local variables whose types contain regions. The others are not of interest
-//! to us. This file defines a new index type (LocalWithRegion) that indexes into
-//! a list of "variables whose type contain regions". It also defines a map from
-//! Local to LocalWithRegion and vice versa -- this map can be given to the
-//! liveness code so that it only operates over variables with regions in their
-//! types, instead of all variables.
-
-use rustc::ty::TypeFoldable;
-use rustc_data_structures::indexed_vec::IndexVec;
-use rustc::mir::{Mir, Local};
-use util::liveness::LiveVariableMap;
-
-use rustc_data_structures::indexed_vec::Idx;
-
-/// Map between Local and LocalWithRegion indices: this map is supplied to the
-/// liveness code so that it will only analyze those variables whose types
-/// contain regions.
-crate struct NllLivenessMap {
-    /// For each local variable, contains either None (if the type has no regions)
-    /// or Some(i) with a suitable index.
-    pub from_local: IndexVec<Local, Option<LocalWithRegion>>,
-    /// For each LocalWithRegion, maps back to the original Local index.
-    pub to_local: IndexVec<LocalWithRegion, Local>,
-
-}
-
-impl LiveVariableMap for NllLivenessMap {
-
-    fn from_local(&self, local: Local) -> Option<Self::LiveVar> {
-        self.from_local[local]
-    }
-
-    type LiveVar = LocalWithRegion;
-
-    fn from_live_var(&self, local: Self::LiveVar) -> Local {
-        self.to_local[local]
-    }
-
-    fn num_variables(&self) -> usize {
-        self.to_local.len()
-    }
-}
-
-impl NllLivenessMap {
-    /// Iterates over the variables in Mir and assigns each Local whose type contains
-    /// regions a LocalWithRegion index. Returns a map for converting back and forth.
-    pub fn compute(mir: &Mir) -> Self {
-        let mut to_local = IndexVec::default();
-        let from_local: IndexVec<Local,Option<_>> = mir
-            .local_decls
-            .iter_enumerated()
-            .map(|(local, local_decl)| {
-                if local_decl.ty.has_free_regions() {
-                    Some(to_local.push(local))
-                }
-                    else {
-                        None
-                    }
-            }).collect();
-
-        Self { from_local, to_local }
-    }
-}
-
-/// Index given to each local variable whose type contains a region.
-newtype_index!(LocalWithRegion);
diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs
index 973568a67f0..f54d80d5f4f 100644
--- a/src/librustc_mir/borrow_check/nll/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/mod.rs
@@ -11,9 +11,9 @@
 use borrow_check::borrow_set::BorrowSet;
 use borrow_check::location::{LocationIndex, LocationTable};
 use borrow_check::nll::facts::AllFactsExt;
-use borrow_check::nll::type_check::MirTypeckRegionConstraints;
+use borrow_check::nll::type_check::{MirTypeckResults, MirTypeckRegionConstraints};
+use borrow_check::nll::type_check::liveness::liveness_map::{NllLivenessMap, LocalWithRegion};
 use borrow_check::nll::region_infer::values::RegionValueElements;
-use borrow_check::nll::liveness_map::{NllLivenessMap, LocalWithRegion};
 use dataflow::indexes::BorrowIndex;
 use dataflow::move_paths::MoveData;
 use dataflow::FlowAtLocation;
@@ -47,7 +47,6 @@ crate mod region_infer;
 mod renumber;
 crate mod type_check;
 mod universal_regions;
-crate mod liveness_map;
 
 mod constraints;
 
@@ -109,9 +108,12 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
     let elements = &Rc::new(RegionValueElements::new(mir));
 
     // Run the MIR type-checker.
-    let liveness_map = NllLivenessMap::compute(&mir);
-    let liveness = LivenessResults::compute(mir, &liveness_map);
-    let (constraint_sets, universal_region_relations) = type_check::type_check(
+    let MirTypeckResults {
+        constraints,
+        universal_region_relations,
+        liveness,
+        liveness_map,
+    } = type_check::type_check(
         infcx,
         param_env,
         mir,
@@ -119,7 +121,6 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
         &universal_regions,
         location_table,
         borrow_set,
-        &liveness,
         &mut all_facts,
         flow_inits,
         move_data,
@@ -141,7 +142,7 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
         mut liveness_constraints,
         outlives_constraints,
         type_tests,
-    } = constraint_sets;
+    } = constraints;
 
     constraint_generation::generate_constraints(
         infcx,
@@ -205,6 +206,7 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
     dump_mir_results(
         infcx,
         &liveness,
+        &liveness_map,
         MirSource::item(def_id),
         &mir,
         &regioncx,
@@ -221,6 +223,7 @@ 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,
@@ -230,8 +233,6 @@ fn dump_mir_results<'a, 'gcx, 'tcx>(
         return;
     }
 
-    let map = &NllLivenessMap::compute(mir);
-
     let regular_liveness_per_location: FxHashMap<_, _> = mir
         .basic_blocks()
         .indices()
@@ -239,7 +240,7 @@ fn dump_mir_results<'a, 'gcx, 'tcx>(
             let mut results = vec![];
             liveness
                 .regular
-                .simulate_block(&mir, bb, map, |location, local_set| {
+                .simulate_block(&mir, bb, liveness_map, |location, local_set| {
                     results.push((location, local_set.clone()));
                 });
             results
@@ -253,7 +254,7 @@ fn dump_mir_results<'a, 'gcx, 'tcx>(
             let mut results = vec![];
             liveness
                 .drop
-                .simulate_block(&mir, bb, map, |location, local_set| {
+                .simulate_block(&mir, bb, liveness_map, |location, local_set| {
                     results.push((location, local_set.clone()));
                 });
             results
diff --git a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
index 0798a45b3be..f7dfa5a7ae5 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 use super::universal_regions::UniversalRegions;
-use borrow_check::nll::constraints::graph::ConstraintGraph;
+use borrow_check::nll::constraints::graph::NormalConstraintGraph;
 use borrow_check::nll::constraints::{
     ConstraintIndex, ConstraintSccIndex, ConstraintSet, OutlivesConstraint,
 };
@@ -61,7 +61,7 @@ pub struct RegionInferenceContext<'tcx> {
     /// The constraint-set, but in graph form, making it easy to traverse
     /// the constraints adjacent to a particular region. Used to construct
     /// the SCC (see `constraint_sccs`) and for error reporting.
-    constraint_graph: Rc<ConstraintGraph>,
+    constraint_graph: Rc<NormalConstraintGraph>,
 
     /// The SCC computed from `constraints` and the constraint graph. Used to compute the values
     /// of each region.
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/liveness_map.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/liveness_map.rs
new file mode 100644
index 00000000000..89e8c76b22f
--- /dev/null
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/liveness_map.rs
@@ -0,0 +1,97 @@
+// 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.
+
+//! For the NLL computation, we need to compute liveness, but only for those
+//! local variables whose types contain regions. The others are not of interest
+//! to us. This file defines a new index type (LocalWithRegion) that indexes into
+//! a list of "variables whose type contain regions". It also defines a map from
+//! Local to LocalWithRegion and vice versa -- this map can be given to the
+//! liveness code so that it only operates over variables with regions in their
+//! types, instead of all variables.
+
+use borrow_check::nll::ToRegionVid;
+use rustc::mir::{Local, Mir};
+use rustc::ty::{RegionVid, TyCtxt};
+use rustc_data_structures::fx::FxHashSet;
+use rustc_data_structures::indexed_vec::{Idx, IndexVec};
+use util::liveness::LiveVariableMap;
+
+/// Map between Local and LocalWithRegion indices: the purpose of this
+/// map is to define the subset of local variables for which we need
+/// to do a liveness computation. We only need to compute whether a
+/// variable `X` is live if that variable contains some region `R` in
+/// its type where `R` is not known to outlive a free region (i.e.,
+/// where `R` may be valid for just a subset of the fn body).
+crate struct NllLivenessMap {
+    /// For each local variable, contains `Some(i)` if liveness is
+    /// needed for this variable.
+    pub from_local: IndexVec<Local, Option<LocalWithRegion>>,
+
+    /// For each `LocalWithRegion`, maps back to the original `Local` index.
+    pub to_local: IndexVec<LocalWithRegion, Local>,
+}
+
+impl LiveVariableMap for NllLivenessMap {
+    fn from_local(&self, local: Local) -> Option<Self::LiveVar> {
+        self.from_local[local]
+    }
+
+    type LiveVar = LocalWithRegion;
+
+    fn from_live_var(&self, local: Self::LiveVar) -> Local {
+        self.to_local[local]
+    }
+
+    fn num_variables(&self) -> usize {
+        self.to_local.len()
+    }
+}
+
+impl NllLivenessMap {
+    crate fn compute(
+        tcx: TyCtxt<'_, '_, 'tcx>,
+        free_regions: &FxHashSet<RegionVid>,
+        mir: &Mir<'tcx>,
+    ) -> Self {
+        let mut to_local = IndexVec::default();
+        let from_local: IndexVec<Local, Option<_>> = mir.local_decls
+            .iter_enumerated()
+            .map(|(local, local_decl)| {
+                if tcx.all_free_regions_meet(&local_decl.ty, |r| {
+                    free_regions.contains(&r.to_region_vid())
+                }) {
+                    // If all the regions in the type are free regions
+                    // (or there are no regions), then we don't need
+                    // to track liveness for this variable.
+                    None
+                } else {
+                    Some(to_local.push(local))
+                }
+            })
+            .collect();
+
+        debug!("{} total variables", mir.local_decls.len());
+        debug!("{} variables need liveness", to_local.len());
+        debug!("{} regions outlive free regions", free_regions.len());
+
+        Self {
+            from_local,
+            to_local,
+        }
+    }
+
+    /// True if there are no local variables that need liveness computation.
+    crate fn is_empty(&self) -> bool {
+        self.to_local.is_empty()
+    }
+}
+
+/// Index given to each local variable whose type contains a region.
+newtype_index!(LocalWithRegion);
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs
index 2b9307db59a..a9b69cfe761 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/liveness.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs
@@ -8,8 +8,10 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use borrow_check::nll::{NllLivenessMap, LocalWithRegion};
+use borrow_check::nll::constraints::ConstraintSet;
 use borrow_check::nll::type_check::AtLocation;
+use borrow_check::nll::{LocalWithRegion, NllLivenessMap};
+use borrow_check::nll::universal_regions::UniversalRegions;
 use dataflow::move_paths::{HasMoveData, MoveData};
 use dataflow::MaybeInitializedPlaces;
 use dataflow::{FlowAtLocation, FlowsAtLocation};
@@ -18,13 +20,15 @@ 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::{Ty, TypeFoldable};
-use rustc_data_structures::fx::FxHashMap;
+use rustc::ty::{RegionVid, Ty, TypeFoldable};
+use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use std::rc::Rc;
-use util::liveness::{LivenessResults, LiveVariableMap };
+use util::liveness::{LiveVariableMap, LivenessResults};
 
 use super::TypeChecker;
 
+crate mod liveness_map;
+
 /// Combines liveness analysis with initialization analysis to
 /// determine which variables are live at which points, both due to
 /// ordinary uses and drops. Returns a set of (ty, location) pairs
@@ -36,23 +40,77 @@ use super::TypeChecker;
 pub(super) fn generate<'gcx, 'tcx>(
     cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
     mir: &Mir<'tcx>,
-    liveness: &LivenessResults<LocalWithRegion>,
     flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>,
     move_data: &MoveData<'tcx>,
-) {
-    let mut generator = TypeLivenessGenerator {
-        cx,
-        mir,
-        liveness,
-        flow_inits,
-        move_data,
-        drop_data: FxHashMap(),
-        map: &NllLivenessMap::compute(mir),
+) -> (LivenessResults<LocalWithRegion>, NllLivenessMap) {
+    let free_regions = {
+        let borrowck_context = cx.borrowck_context.as_ref().unwrap();
+        regions_that_outlive_free_regions(
+            cx.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)
+}
+
+/// Compute all regions that are (currently) known to outlive free
+/// regions. For these regions, we do not need to compute
+/// liveness, since the outlives constraints will ensure that they
+/// are live over the whole fn body anyhow.
+fn regions_that_outlive_free_regions(
+    num_region_vars: usize,
+    universal_regions: &UniversalRegions<'tcx>,
+    constraint_set: &ConstraintSet,
+) -> FxHashSet<RegionVid> {
+    // Build a graph of the outlives constraints thus far. This is
+    // a reverse graph, so for each constraint `R1: R2` we have an
+    // edge `R2 -> R1`. Therefore, if we find all regions
+    // reachable from each free region, we will have all the
+    // regions that are forced to outlive some free region.
+    let rev_constraint_graph = constraint_set.reverse_graph(num_region_vars);
+    let rev_region_graph = rev_constraint_graph.region_graph(constraint_set);
+
+    // Stack for the depth-first search. Start out with all the free regions.
+    let mut stack: Vec<_> = universal_regions.universal_regions().collect();
 
-    for bb in mir.basic_blocks().indices() {
-        generator.add_liveness_constraints(bb);
+    // Set of all free regions, plus anything that outlives them. Initially
+    // just contains the free regions.
+    let mut outlives_free_region: FxHashSet<_> = stack.iter().cloned().collect();
+
+    // Do the DFS -- for each thing in the stack, find all things
+    // that outlive it and add them to the set. If they are not,
+    // push them onto the stack for later.
+    while let Some(sub_region) = stack.pop() {
+        stack.extend(
+            rev_region_graph
+                .outgoing_regions(sub_region)
+                .filter(|&r| outlives_free_region.insert(r)),
+        );
     }
+
+    // Return the final set of things we visited.
+    outlives_free_region
 }
 
 struct TypeLivenessGenerator<'gen, 'typeck, 'flow, 'gcx, 'tcx>
@@ -174,8 +232,13 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
 
         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);
+                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);
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 a18e2368bf7..eb689f0a9c6 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
@@ -18,6 +18,7 @@ use borrow_check::nll::facts::AllFacts;
 use borrow_check::nll::region_infer::values::{RegionValueElements, LivenessValues};
 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;
@@ -74,7 +75,7 @@ macro_rules! span_mirbug_and_err {
 mod constraint_conversion;
 pub mod free_region_relations;
 mod input_output;
-mod liveness;
+crate mod liveness;
 mod relate_tys;
 
 /// Type checks the given `mir` in the context of the inference
@@ -115,16 +116,12 @@ pub(crate) fn type_check<'gcx, 'tcx>(
     universal_regions: &Rc<UniversalRegions<'tcx>>,
     location_table: &LocationTable,
     borrow_set: &BorrowSet<'tcx>,
-    liveness: &LivenessResults<LocalWithRegion>,
     all_facts: &mut Option<AllFacts>,
     flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>,
     move_data: &MoveData<'tcx>,
     elements: &Rc<RegionValueElements>,
     errors_buffer: &mut Vec<Diagnostic>,
-) -> (
-    MirTypeckRegionConstraints<'tcx>,
-    Rc<UniversalRegionRelations<'tcx>>,
-) {
+) -> MirTypeckResults<'tcx> {
     let implicit_region_bound = infcx.tcx.mk_region(ty::ReVar(universal_regions.fr_fn_body));
     let mut constraints = MirTypeckRegionConstraints {
         liveness_constraints: LivenessValues::new(elements),
@@ -147,7 +144,7 @@ pub(crate) fn type_check<'gcx, 'tcx>(
         all_facts,
     );
 
-    {
+    let (liveness, liveness_map) = {
         let mut borrowck_context = BorrowCheckContext {
             universal_regions,
             location_table,
@@ -166,7 +163,6 @@ pub(crate) fn type_check<'gcx, 'tcx>(
             Some(&mut borrowck_context),
             Some(errors_buffer),
             |cx| {
-                liveness::generate(cx, mir, liveness, flow_inits, move_data);
                 cx.equate_inputs_and_outputs(
                     mir,
                     mir_def_id,
@@ -174,14 +170,20 @@ pub(crate) fn type_check<'gcx, 'tcx>(
                     &universal_region_relations,
                     &normalized_inputs_and_output,
                 );
+                liveness::generate(cx, mir, flow_inits, move_data)
             },
-        );
-    }
+        )
+    };
 
-    (constraints, universal_region_relations)
+    MirTypeckResults {
+        constraints,
+        universal_region_relations,
+        liveness,
+        liveness_map,
+    }
 }
 
-fn type_check_internal<'a, 'gcx, 'tcx, F>(
+fn type_check_internal<'a, 'gcx, 'tcx, R>(
     infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
     mir_def_id: DefId,
     param_env: ty::ParamEnv<'gcx>,
@@ -190,10 +192,8 @@ fn type_check_internal<'a, 'gcx, 'tcx, F>(
     implicit_region_bound: Option<ty::Region<'tcx>>,
     borrowck_context: Option<&'a mut BorrowCheckContext<'a, 'tcx>>,
     errors_buffer: Option<&mut Vec<Diagnostic>>,
-    mut extra: F,
-) where
-    F: FnMut(&mut TypeChecker<'a, 'gcx, 'tcx>),
-{
+    mut extra: impl FnMut(&mut TypeChecker<'a, 'gcx, 'tcx>) -> R,
+) -> R where {
     let mut checker = TypeChecker::new(
         infcx,
         mir,
@@ -214,7 +214,7 @@ fn type_check_internal<'a, 'gcx, 'tcx, F>(
         checker.typeck_mir(mir, errors_buffer);
     }
 
-    extra(&mut checker);
+    extra(&mut checker)
 }
 
 fn mirbug(tcx: TyCtxt, span: Span, msg: &str) {
@@ -655,6 +655,13 @@ struct BorrowCheckContext<'a, 'tcx: 'a> {
     constraints: &'a mut MirTypeckRegionConstraints<'tcx>,
 }
 
+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
 /// program to be considered well-typed.
 crate struct MirTypeckRegionConstraints<'tcx> {
diff --git a/src/librustc_mir/borrow_check/place_ext.rs b/src/librustc_mir/borrow_check/place_ext.rs
index b0517c5e61f..be0091068c2 100644
--- a/src/librustc_mir/borrow_check/place_ext.rs
+++ b/src/librustc_mir/borrow_check/place_ext.rs
@@ -15,8 +15,11 @@ use rustc::ty::{self, TyCtxt};
 
 /// Extension methods for the `Place` type.
 crate trait PlaceExt<'tcx> {
-    /// True if this is a deref of a raw pointer.
-    fn is_unsafe_place(&self, tcx: TyCtxt<'_, '_, 'tcx>, mir: &Mir<'tcx>) -> bool;
+    /// Returns true if we can safely ignore borrows of this place.
+    /// This is true whenever there is no action that the user can do
+    /// to the place `self` that would invalidate the borrow. This is true
+    /// for borrows of raw pointer dereferents as well as shared references.
+    fn ignore_borrow(&self, tcx: TyCtxt<'_, '_, 'tcx>, mir: &Mir<'tcx>) -> bool;
 
     /// If this is a place like `x.f.g`, returns the local
     /// `x`. Returns `None` if this is based in a static.
@@ -24,7 +27,7 @@ crate trait PlaceExt<'tcx> {
 }
 
 impl<'tcx> PlaceExt<'tcx> for Place<'tcx> {
-    fn is_unsafe_place(&self, tcx: TyCtxt<'_, '_, 'tcx>, mir: &Mir<'tcx>) -> bool {
+    fn ignore_borrow(&self, tcx: TyCtxt<'_, '_, 'tcx>, mir: &Mir<'tcx>) -> bool {
         match self {
             Place::Promoted(_) |
             Place::Local(_) => false,
@@ -36,12 +39,23 @@ impl<'tcx> PlaceExt<'tcx> for Place<'tcx> {
                 | ProjectionElem::Downcast(..)
                 | ProjectionElem::Subslice { .. }
                 | ProjectionElem::ConstantIndex { .. }
-                | ProjectionElem::Index(_) => proj.base.is_unsafe_place(tcx, mir),
+                | ProjectionElem::Index(_) => proj.base.ignore_borrow(tcx, mir),
+
                 ProjectionElem::Deref => {
                     let ty = proj.base.ty(mir, tcx).to_ty(tcx);
                     match ty.sty {
-                        ty::TyRawPtr(..) => true,
-                        _ => proj.base.is_unsafe_place(tcx, mir),
+                        // For both derefs of raw pointers and `&T`
+                        // references, the original path is `Copy` and
+                        // therefore not significant.  In particular,
+                        // there is nothing the user can do to the
+                        // original path that would invalidate the
+                        // newly created reference -- and if there
+                        // were, then the user could have copied the
+                        // original path into a new variable and
+                        // borrowed *that* one, leaving the original
+                        // path unborrowed.
+                        ty::TyRawPtr(..) | ty::TyRef(_, _, hir::MutImmutable) => true,
+                        _ => proj.base.ignore_borrow(tcx, mir),
                     }
                 }
             },
diff --git a/src/librustc_mir/dataflow/impls/borrows.rs b/src/librustc_mir/dataflow/impls/borrows.rs
index ea59e42fd47..b0c4d37814e 100644
--- a/src/librustc_mir/dataflow/impls/borrows.rs
+++ b/src/librustc_mir/dataflow/impls/borrows.rs
@@ -233,7 +233,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for Borrows<'a, 'gcx, 'tcx> {
                 // propagate_call_return method.
 
                 if let mir::Rvalue::Ref(region, _, ref place) = *rhs {
-                    if place.is_unsafe_place(self.tcx, self.mir) { return; }
+                    if place.ignore_borrow(self.tcx, self.mir) { return; }
                     let index = self.borrow_set.location_map.get(&location).unwrap_or_else(|| {
                         panic!("could not find BorrowIndex for location {:?}", location);
                     });
diff --git a/src/test/ui/borrowck/promote-ref-mut-in-let-issue-46557.nll.stderr b/src/test/ui/borrowck/promote-ref-mut-in-let-issue-46557.nll.stderr
index 95acdab3e80..52f1547bce6 100644
--- a/src/test/ui/borrowck/promote-ref-mut-in-let-issue-46557.nll.stderr
+++ b/src/test/ui/borrowck/promote-ref-mut-in-let-issue-46557.nll.stderr
@@ -1,30 +1,24 @@
 error[E0597]: borrowed value does not live long enough
   --> $DIR/promote-ref-mut-in-let-issue-46557.rs:15:21
    |
-LL |   fn gimme_static_mut_let() -> &'static mut u32 {
-   |  _______________________________________________-
-LL | |     let ref mut x = 1234543; //~ ERROR
-   | |                     ^^^^^^^ temporary value does not live long enough
-LL | |     x
-LL | | }
-   | | -
-   | | |
-   | |_temporary value only lives until here
-   |   borrow later used here
+LL |     let ref mut x = 1234543; //~ ERROR
+   |                     ^^^^^^^ temporary value does not live long enough
+LL |     x
+LL | }
+   | - temporary value only lives until here
+   |
+   = note: borrowed value must be valid for the static lifetime...
 
 error[E0597]: borrowed value does not live long enough
   --> $DIR/promote-ref-mut-in-let-issue-46557.rs:20:25
    |
-LL |   fn gimme_static_mut_let_nested() -> &'static mut u32 {
-   |  ______________________________________________________-
-LL | |     let (ref mut x, ) = (1234543, ); //~ ERROR
-   | |                         ^^^^^^^^^^^ temporary value does not live long enough
-LL | |     x
-LL | | }
-   | | -
-   | | |
-   | |_temporary value only lives until here
-   |   borrow later used here
+LL |     let (ref mut x, ) = (1234543, ); //~ ERROR
+   |                         ^^^^^^^^^^^ temporary value does not live long enough
+LL |     x
+LL | }
+   | - temporary value only lives until here
+   |
+   = note: borrowed value must be valid for the static lifetime...
 
 error[E0597]: borrowed value does not live long enough
   --> $DIR/promote-ref-mut-in-let-issue-46557.rs:25:11
diff --git a/src/test/ui/nll/get_default.nll.stderr b/src/test/ui/nll/get_default.nll.stderr
index b955a51e38d..580dce3c0fe 100644
--- a/src/test/ui/nll/get_default.nll.stderr
+++ b/src/test/ui/nll/get_default.nll.stderr
@@ -63,9 +63,18 @@ LL |         match map.get() {
 LL |             Some(v) => {
 LL |                 map.set(String::new()); // Both AST and MIR error here
    |                 ^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
-...
-LL |                 return v;
-   |                        - borrow later used here
+   |
+note: borrowed value must be valid for the anonymous lifetime #1 defined on the function body at 41:1...
+  --> $DIR/get_default.rs:41:1
+   |
+LL | / fn err(map: &mut Map) -> &String {
+LL | |     loop {
+LL | |         match map.get() {
+LL | |             Some(v) => {
+...  |
+LL | |     }
+LL | | }
+   | |_^
 
 error[E0502]: cannot borrow `*map` as mutable because it is also borrowed as immutable (Mir)
   --> $DIR/get_default.rs:51:17
diff --git a/src/test/ui/nll/get_default.stderr b/src/test/ui/nll/get_default.stderr
index 75194bf55bc..2f8eab907c7 100644
--- a/src/test/ui/nll/get_default.stderr
+++ b/src/test/ui/nll/get_default.stderr
@@ -63,9 +63,18 @@ LL |         match map.get() {
 LL |             Some(v) => {
 LL |                 map.set(String::new()); // Both AST and MIR error here
    |                 ^^^ mutable borrow occurs here
-...
-LL |                 return v;
-   |                        - borrow later used here
+   |
+note: borrowed value must be valid for the anonymous lifetime #1 defined on the function body at 41:1...
+  --> $DIR/get_default.rs:41:1
+   |
+LL | / fn err(map: &mut Map) -> &String {
+LL | |     loop {
+LL | |         match map.get() {
+LL | |             Some(v) => {
+...  |
+LL | |     }
+LL | | }
+   | |_^
 
 error[E0502]: cannot borrow `*map` as mutable because it is also borrowed as immutable (Mir)
   --> $DIR/get_default.rs:51:17
diff --git a/src/test/ui/nll/return-ref-mut-issue-46557.stderr b/src/test/ui/nll/return-ref-mut-issue-46557.stderr
index f40e38c63f5..f441085f242 100644
--- a/src/test/ui/nll/return-ref-mut-issue-46557.stderr
+++ b/src/test/ui/nll/return-ref-mut-issue-46557.stderr
@@ -1,16 +1,13 @@
 error[E0597]: borrowed value does not live long enough
   --> $DIR/return-ref-mut-issue-46557.rs:17:21
    |
-LL |   fn gimme_static_mut() -> &'static mut u32 {
-   |  ___________________________________________-
-LL | |     let ref mut x = 1234543; //~ ERROR borrowed value does not live long enough [E0597]
-   | |                     ^^^^^^^ temporary value does not live long enough
-LL | |     x
-LL | | }
-   | | -
-   | | |
-   | |_temporary value only lives until here
-   |   borrow later used here
+LL |     let ref mut x = 1234543; //~ ERROR borrowed value does not live long enough [E0597]
+   |                     ^^^^^^^ temporary value does not live long enough
+LL |     x
+LL | }
+   | - temporary value only lives until here
+   |
+   = note: borrowed value must be valid for the static lifetime...
 
 error: aborting due to previous error