1 files changed, 139 insertions, 0 deletions
diff --git a/compiler/rustc_borrowck/src/type_check/liveness/mod.rs b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs
new file mode 100644
index 000000000..d5c401ae1
--- /dev/null
+++ b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs
@@ -0,0 +1,139 @@
+use itertools::{Either, Itertools};
+use rustc_data_structures::fx::FxHashSet;
+use rustc_middle::mir::{Body, Local};
+use rustc_middle::ty::{RegionVid, TyCtxt};
+use rustc_mir_dataflow::impls::MaybeInitializedPlaces;
+use rustc_mir_dataflow::move_paths::MoveData;
+use rustc_mir_dataflow::ResultsCursor;
+use std::rc::Rc;
+
+use crate::{
+    constraints::OutlivesConstraintSet,
+    facts::{AllFacts, AllFactsExt},
+    location::LocationTable,
+    nll::ToRegionVid,
+    region_infer::values::RegionValueElements,
+    universal_regions::UniversalRegions,
+};
+
+use super::TypeChecker;
+
+mod local_use_map;
+mod polonius;
+mod trace;
+
+/// 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
+/// that indicate which types must be live at which point in the CFG.
+/// This vector is consumed by `constraint_generation`.
+///
+/// N.B., this computation requires normalization; therefore, it must be
+/// performed before
+pub(super) fn generate<'mir, 'tcx>(
+    typeck: &mut TypeChecker<'_, 'tcx>,
+    body: &Body<'tcx>,
+    elements: &Rc<RegionValueElements>,
+    flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>,
+    move_data: &MoveData<'tcx>,
+    location_table: &LocationTable,
+    use_polonius: bool,
+) {
+    debug!("liveness::generate");
+
+    let free_regions = regions_that_outlive_free_regions(
+        typeck.infcx.num_region_vars(),
+        &typeck.borrowck_context.universal_regions,
+        &typeck.borrowck_context.constraints.outlives_constraints,
+    );
+    let (relevant_live_locals, boring_locals) =
+        compute_relevant_live_locals(typeck.tcx(), &free_regions, &body);
+    let facts_enabled = use_polonius || AllFacts::enabled(typeck.tcx());
+
+    let polonius_drop_used = if facts_enabled {
+        let mut drop_used = Vec::new();
+        polonius::populate_access_facts(typeck, body, location_table, move_data, &mut drop_used);
+        Some(drop_used)
+    } else {
+        None
+    };
+
+    trace::trace(
+        typeck,
+        body,
+        elements,
+        flow_inits,
+        move_data,
+        relevant_live_locals,
+        boring_locals,
+        polonius_drop_used,
+    );
+}
+
+// The purpose of `compute_relevant_live_locals` 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).
+fn compute_relevant_live_locals<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    free_regions: &FxHashSet<RegionVid>,
+    body: &Body<'tcx>,
+) -> (Vec<Local>, Vec<Local>) {
+    let (boring_locals, relevant_live_locals): (Vec<_>, Vec<_>) =
+        body.local_decls.iter_enumerated().partition_map(|(local, local_decl)| {
+            if tcx.all_free_regions_meet(&local_decl.ty, |r| {
+                free_regions.contains(&r.to_region_vid())
+            }) {
+                Either::Left(local)
+            } else {
+                Either::Right(local)
+            }
+        });
+
+    debug!("{} total variables", body.local_decls.len());
+    debug!("{} variables need liveness", relevant_live_locals.len());
+    debug!("{} regions outlive free regions", free_regions.len());
+
+    (relevant_live_locals, boring_locals)
+}
+
+/// Computes 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<'tcx>(
+    num_region_vars: usize,
+    universal_regions: &UniversalRegions<'tcx>,
+    constraint_set: &OutlivesConstraintSet<'tcx>,
+) -> 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 fr_static = universal_regions.fr_static;
+    let rev_region_graph = rev_constraint_graph.region_graph(constraint_set, fr_static);
+
+    // Stack for the depth-first search. Start out with all the free regions.
+    let mut stack: Vec<_> = universal_regions.universal_regions().collect();
+
+    // 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
+}