| use crate::borrow_check::location::LocationTable; |
| use crate::borrow_check::nll::constraints::OutlivesConstraintSet; |
| use crate::borrow_check::nll::facts::{AllFacts, AllFactsExt}; |
| use crate::borrow_check::nll::region_infer::values::RegionValueElements; |
| use crate::borrow_check::nll::universal_regions::UniversalRegions; |
| use crate::borrow_check::nll::ToRegionVid; |
| use crate::dataflow::move_paths::MoveData; |
| use crate::dataflow::FlowAtLocation; |
| use crate::dataflow::MaybeInitializedPlaces; |
| use rustc::mir::{Body, Local}; |
| use rustc::ty::{RegionVid, TyCtxt}; |
| use rustc_data_structures::fx::FxHashSet; |
| use std::rc::Rc; |
| |
| 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<'tcx>( |
| typeck: &mut TypeChecker<'_, 'tcx>, |
| body: &Body<'tcx>, |
| elements: &Rc<RegionValueElements>, |
| flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'tcx>>, |
| move_data: &MoveData<'tcx>, |
| location_table: &LocationTable, |
| ) { |
| debug!("liveness::generate"); |
| |
| let live_locals: Vec<Local> = if AllFacts::enabled(typeck.tcx()) { |
| // If "dump facts from NLL analysis" was requested perform |
| // the liveness analysis for all `Local`s. This case opens |
| // the possibility of the variables being analyzed in `trace` |
| // to be *any* `Local`, not just the "live" ones, so we can't |
| // make any assumptions past this point as to the characteristics |
| // of the `live_locals`. |
| // FIXME: Review "live" terminology past this point, we should |
| // not be naming the `Local`s as live. |
| body.local_decls.indices().collect() |
| } else { |
| let free_regions = { |
| regions_that_outlive_free_regions( |
| typeck.infcx.num_region_vars(), |
| &typeck.borrowck_context.universal_regions, |
| &typeck.borrowck_context.constraints.outlives_constraints, |
| ) |
| }; |
| compute_live_locals(typeck.tcx(), &free_regions, body) |
| }; |
| |
| if !live_locals.is_empty() { |
| trace::trace(typeck, body, elements, flow_inits, move_data, live_locals); |
| |
| polonius::populate_access_facts(typeck, body, location_table, move_data); |
| } |
| } |
| |
| // The purpose of `compute_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_live_locals( |
| tcx: TyCtxt<'tcx>, |
| free_regions: &FxHashSet<RegionVid>, |
| body: &Body<'tcx>, |
| ) -> Vec<Local> { |
| let live_locals: Vec<Local> = body |
| .local_decls |
| .iter_enumerated() |
| .filter_map(|(local, local_decl)| { |
| if tcx.all_free_regions_meet(&local_decl.ty, |r| { |
| free_regions.contains(&r.to_region_vid()) |
| }) { |
| None |
| } else { |
| Some(local) |
| } |
| }) |
| .collect(); |
| |
| debug!("{} total variables", body.local_decls.len()); |
| debug!("{} variables need liveness", live_locals.len()); |
| debug!("{} regions outlive free regions", free_regions.len()); |
| |
| live_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( |
| num_region_vars: usize, |
| universal_regions: &UniversalRegions<'tcx>, |
| constraint_set: &OutlivesConstraintSet, |
| ) -> 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 |
| } |