diff options
Diffstat (limited to 'compiler/rustc_borrowck/src/type_check/liveness/mod.rs')
-rw-r--r-- | compiler/rustc_borrowck/src/type_check/liveness/mod.rs | 139 |
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 +} |