compute union-find of locals flowing into the output of statics

Co-authored-by: lqd <remy.rakic+github@gmail.com>
Co-authored-by: nikomatsakis <niko@alum.mit.edu>

5 files changed, 203 insertions, 24 deletions

diff --git a/src/librustc_mir/borrow_check/nll/escaping_locals.rs b/src/librustc_mir/borrow_check/nll/escaping_locals.rs
new file mode 100644
index 00000000000..da9cc10853e
--- /dev/null
+++ b/src/librustc_mir/borrow_check/nll/escaping_locals.rs
@@ -0,0 +1,161 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! A MIR walk gathering a union-crfind of assigned locals, for the purpose of locating the ones
+//! escaping into the output.
+
+use rustc::mir::visit::Visitor;
+use rustc::mir::*;
+
+use rustc_data_structures::indexed_vec::Idx;
+use rustc_data_structures::unify as ut;
+
+crate struct EscapingLocals {
+    unification_table: ut::UnificationTable<ut::InPlace<AssignedLocal>>,
+}
+
+impl EscapingLocals {
+    crate fn compute(mir: &Mir<'_>) -> Self {
+        let mut visitor = GatherAssignedLocalsVisitor::new();
+        visitor.visit_mir(mir);
+
+        EscapingLocals { unification_table: visitor.unification_table }
+    }
+
+    /// True if `local` is known to escape into static
+    /// memory.
+    crate fn escapes_into_return(&mut self, local: Local) -> bool {
+        let return_place = AssignedLocal::from(RETURN_PLACE);
+        let other_place = AssignedLocal::from(local);
+        self.unification_table.unioned(return_place, other_place)
+    }
+}
+
+/// The MIR visitor gathering the union-find of the locals used in
+/// assignments.
+struct GatherAssignedLocalsVisitor {
+    unification_table: ut::UnificationTable<ut::InPlace<AssignedLocal>>,
+}
+
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
+struct AssignedLocal(u32);
+
+impl ut::UnifyKey for AssignedLocal {
+    type Value = ();
+
+    fn index(&self) -> u32 {
+        self.0
+    }
+
+    fn from_index(i: u32) -> AssignedLocal {
+        AssignedLocal(i)
+    }
+
+    fn tag() -> &'static str {
+        "AssignedLocal"
+    }
+}
+
+impl From<Local> for AssignedLocal {
+    fn from(item: Local) -> Self {
+        // newtype_indexes use usize but are u32s.
+        assert!(item.index() < ::std::u32::MAX as usize);
+        AssignedLocal(item.index() as u32)
+    }
+}
+
+impl GatherAssignedLocalsVisitor {
+    fn new() -> Self {
+        Self {
+            unification_table: ut::UnificationTable::new(),
+        }
+    }
+
+    fn union_locals_if_needed(&mut self, lvalue: Option<Local>, rvalue: Option<Local>) {
+        if let Some(lvalue) = lvalue {
+            if let Some(rvalue) = rvalue {
+                if lvalue != rvalue {
+                    self.unification_table
+                        .union(AssignedLocal::from(lvalue), AssignedLocal::from(rvalue));
+                }
+            }
+        }
+    }
+}
+
+// Returns the potential `Local` associated to this `Place` or `PlaceProjection`
+fn find_local_in_place(place: &Place) -> Option<Local> {
+    match place {
+        Place::Local(local) => Some(*local),
+
+        // If you do e.g. `x = a.f` then only *part* of the type of
+        // `a` escapes into `x` (the part contained in `f`); if `a`'s
+        // type has regions that don't appear in `f`, those might not
+        // escape.
+        Place::Projection(..) => None,
+
+        Place::Static { .. } | Place::Promoted { .. } => None,
+    }
+}
+
+// Returns the potential `Local` in this `Operand`.
+fn find_local_in_operand(op: &Operand) -> Option<Local> {
+    // Conservatively check a subset of `Operand`s we know our
+    // benchmarks track, for example `html5ever`.
+    match op {
+        Operand::Copy(place) | Operand::Move(place) => find_local_in_place(place),
+        Operand::Constant(_) => None,
+    }
+}
+
+impl<'tcx> Visitor<'tcx> for GatherAssignedLocalsVisitor {
+    fn visit_mir(&mut self, mir: &Mir<'tcx>) {
+        // We need as many union-find keys as there are locals
+        for _ in 0..mir.local_decls.len() {
+            self.unification_table.new_key(());
+        }
+
+        self.super_mir(mir);
+    }
+
+    fn visit_assign(
+        &mut self,
+        block: BasicBlock,
+        place: &Place<'tcx>,
+        rvalue: &Rvalue<'tcx>,
+        location: Location,
+    ) {
+        let local = find_local_in_place(place);
+
+        // Conservatively check a subset of `Rvalue`s we know our
+        // benchmarks track, for example `html5ever`.
+        match rvalue {
+            Rvalue::Use(op) => self.union_locals_if_needed(local, find_local_in_operand(op)),
+            Rvalue::Ref(_, _, place) => {
+                self.union_locals_if_needed(local, find_local_in_place(place))
+            }
+
+            Rvalue::Cast(kind, op, _) => match kind {
+                CastKind::Unsize => self.union_locals_if_needed(local, find_local_in_operand(op)),
+                _ => (),
+            },
+
+            Rvalue::Aggregate(_, ops) => {
+                for rvalue in ops.iter().map(find_local_in_operand) {
+                    self.union_locals_if_needed(local, rvalue);
+                }
+            }
+
+            _ => (),
+        };
+
+        self.super_assign(block, place, rvalue, location);
+    }
+}
diff --git a/src/librustc_mir/borrow_check/nll/liveness_map.rs b/src/librustc_mir/borrow_check/nll/liveness_map.rs
index cbd9c9a4e1a..be29744ab13 100644
--- a/src/librustc_mir/borrow_check/nll/liveness_map.rs
+++ b/src/librustc_mir/borrow_check/nll/liveness_map.rs
@@ -16,9 +16,10 @@
 //! liveness code so that it only operates over variables with regions in their
 //! types, instead of all variables.
 
+use borrow_check::nll::escaping_locals::EscapingLocals;
+use rustc::mir::{Local, Mir};
 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;
@@ -29,14 +30,13 @@ use rustc_data_structures::indexed_vec::Idx;
 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>,
+    from_local: IndexVec<Local, Option<LocalWithRegion>>,
 
+    /// For each LocalWithRegion, maps back to the original Local index.
+    to_local: IndexVec<LocalWithRegion, Local>,
 }
 
 impl LiveVariableMap for NllLivenessMap {
-
     fn from_local(&self, local: Local) -> Option<Self::LiveVar> {
         self.from_local[local]
     }
@@ -55,21 +55,33 @@ impl LiveVariableMap for NllLivenessMap {
 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 {
+    crate fn compute(mir: &Mir<'_>) -> Self {
+        let mut escaping_locals = EscapingLocals::compute(mir);
+
         let mut to_local = IndexVec::default();
-        let from_local: IndexVec<Local,Option<_>> = mir
+        let from_local: IndexVec<Local, Option<_>> = mir
             .local_decls
             .iter_enumerated()
             .map(|(local, local_decl)| {
-                if local_decl.ty.has_free_regions() {
+                if escaping_locals.escapes_into_return(local) {
+                    // If the local escapes into the return value,
+                    // then the return value will force all of the
+                    // regions in its type to outlive free regions
+                    // (e.g., `'static`) and hence liveness is not
+                    // needed. This is particularly important for big
+                    // statics.
+                    None
+                } else if local_decl.ty.has_free_regions() {
                     Some(to_local.push(local))
+                } else {
+                    None
                 }
-                    else {
-                        None
-                    }
             }).collect();
 
-        Self { from_local, to_local }
+        Self {
+            from_local,
+            to_local,
+        }
     }
 }
 
diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs
index 973568a67f0..d991908b699 100644
--- a/src/librustc_mir/borrow_check/nll/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/mod.rs
@@ -39,7 +39,9 @@ use polonius_engine::{Algorithm, Output};
 use util as mir_util;
 use util::pretty::{self, ALIGN};
 
+mod constraints;
 mod constraint_generation;
+mod escaping_locals;
 pub mod explain_borrow;
 mod facts;
 mod invalidation;
@@ -49,8 +51,6 @@ crate mod type_check;
 mod universal_regions;
 crate mod liveness_map;
 
-mod constraints;
-
 use self::facts::AllFacts;
 use self::region_infer::RegionInferenceContext;
 use self::universal_regions::UniversalRegions;
@@ -120,6 +120,7 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
         location_table,
         borrow_set,
         &liveness,
+        &liveness_map,
         &mut all_facts,
         flow_inits,
         move_data,
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness.rs
index 2b9307db59a..d02f54dc4b8 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/liveness.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness.rs
@@ -37,6 +37,7 @@ pub(super) fn generate<'gcx, 'tcx>(
     cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
     mir: &Mir<'tcx>,
     liveness: &LivenessResults<LocalWithRegion>,
+    liveness_map: &NllLivenessMap,
     flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>,
     move_data: &MoveData<'tcx>,
 ) {
@@ -44,10 +45,10 @@ pub(super) fn generate<'gcx, 'tcx>(
         cx,
         mir,
         liveness,
+        liveness_map,
         flow_inits,
         move_data,
         drop_data: FxHashMap(),
-        map: &NllLivenessMap::compute(mir),
     };
 
     for bb in mir.basic_blocks().indices() {
@@ -65,10 +66,10 @@ where
     cx: &'gen mut TypeChecker<'typeck, 'gcx, 'tcx>,
     mir: &'gen Mir<'tcx>,
     liveness: &'gen LivenessResults<LocalWithRegion>,
+    liveness_map: &'gen NllLivenessMap,
     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> {
@@ -86,9 +87,9 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
 
         self.liveness
             .regular
-            .simulate_block(self.mir, bb, self.map, |location, live_locals| {
+            .simulate_block(self.mir, bb, self.liveness_map, |location, live_locals| {
                 for live_local in live_locals.iter() {
-                    let local = self.map.from_live_var(live_local);
+                    let local = self.liveness_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);
                 }
@@ -97,7 +98,7 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
         let mut all_live_locals: Vec<(Location, Vec<LocalWithRegion>)> = vec![];
         self.liveness
             .drop
-            .simulate_block(self.mir, bb, self.map, |location, live_locals| {
+            .simulate_block(self.mir, bb, self.liveness_map, |location, live_locals| {
                 all_live_locals.push((location, live_locals.iter().collect()));
             });
         debug!(
@@ -124,7 +125,7 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
                     });
                 }
 
-                let local = self.map.from_live_var(live_local);
+                let local = self.liveness_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!(
@@ -133,7 +134,7 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
                         self.move_data.move_paths[initialized_child]
                     );
 
-                    let local = self.map.from_live_var(live_local);
+                    let local = self.liveness_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);
                 }
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..15afc6c52bf 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
@@ -15,9 +15,12 @@ use borrow_check::borrow_set::BorrowSet;
 use borrow_check::location::LocationTable;
 use borrow_check::nll::constraints::{ConstraintSet, OutlivesConstraint};
 use borrow_check::nll::facts::AllFacts;
-use borrow_check::nll::region_infer::values::{RegionValueElements, LivenessValues};
+use borrow_check::nll::liveness_map::NllLivenessMap;
+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::free_region_relations::{
+    CreateResult, UniversalRegionRelations,
+};
 use borrow_check::nll::universal_regions::UniversalRegions;
 use borrow_check::nll::LocalWithRegion;
 use borrow_check::nll::ToRegionVid;
@@ -116,6 +119,7 @@ pub(crate) fn type_check<'gcx, 'tcx>(
     location_table: &LocationTable,
     borrow_set: &BorrowSet<'tcx>,
     liveness: &LivenessResults<LocalWithRegion>,
+    liveness_map: &NllLivenessMap,
     all_facts: &mut Option<AllFacts>,
     flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>,
     move_data: &MoveData<'tcx>,
@@ -166,7 +170,7 @@ pub(crate) fn type_check<'gcx, 'tcx>(
             Some(&mut borrowck_context),
             Some(errors_buffer),
             |cx| {
-                liveness::generate(cx, mir, liveness, flow_inits, move_data);
+                liveness::generate(cx, mir, liveness, liveness_map, flow_inits, move_data);
                 cx.equate_inputs_and_outputs(
                     mir,
                     mir_def_id,