src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs

   1 use crate::borrow_check::location::LocationTable;
   2 use crate::borrow_check::nll::constraints::ConstraintSet;
   3 use crate::borrow_check::nll::facts::{AllFacts, AllFactsExt};
   4 use crate::borrow_check::nll::region_infer::values::RegionValueElements;
   5 use crate::borrow_check::nll::universal_regions::UniversalRegions;
   6 use crate::borrow_check::nll::ToRegionVid;
   7 use crate::dataflow::move_paths::MoveData;
   8 use crate::dataflow::FlowAtLocation;
   9 use crate::dataflow::MaybeInitializedPlaces;
  10 use rustc::mir::{Local, Body};
  11 use rustc::ty::{RegionVid, TyCtxt};
  12 use rustc_data_structures::fx::FxHashSet;
  13 use std::rc::Rc;
  14
  15 use super::TypeChecker;
  16
  17 mod local_use_map;
  18 mod trace;
  19
  20 /// Combines liveness analysis with initialization analysis to
  21 /// determine which variables are live at which points, both due to
  22 /// ordinary uses and drops. Returns a set of (ty, location) pairs
  23 /// that indicate which types must be live at which point in the CFG.
  24 /// This vector is consumed by `constraint_generation`.
  25 ///
  26 /// N.B., this computation requires normalization; therefore, it must be
  27 /// performed before
  28 pub(super) fn generate<'gcx, 'tcx>(
  29     typeck: &mut TypeChecker<'_, 'gcx, 'tcx>,
  30     mir: &Body<'tcx>,
  31     elements: &Rc<RegionValueElements>,
  32     flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'gcx, 'tcx>>,
  33     move_data: &MoveData<'tcx>,
  34     location_table: &LocationTable,
  35 ) {
  36     debug!("liveness::generate");
  37
  38     let live_locals: Vec<Local> = if AllFacts::enabled(typeck.tcx()) {
  39         // If "dump facts from NLL analysis" was requested perform
  40         // the liveness analysis for all `Local`s. This case opens
  41         // the possibility of the variables being analyzed in `trace`
  42         // to be *any* `Local`, not just the "live" ones, so we can't
  43         // make any assumptions past this point as to the characteristics
  44         // of the `live_locals`.
  45         // FIXME: Review "live" terminology past this point, we should
  46         // not be naming the `Local`s as live.
  47         mir.local_decls.indices().collect()
  48     } else {
  49         let free_regions = {
  50             regions_that_outlive_free_regions(
  51                 typeck.infcx.num_region_vars(),
  52                 &typeck.borrowck_context.universal_regions,
  53                 &typeck.borrowck_context.constraints.outlives_constraints,
  54             )
  55         };
  56         compute_live_locals(typeck.tcx(), &free_regions, mir)
  57     };
  58
  59     if !live_locals.is_empty() {
  60         trace::trace(
  61             typeck,
  62             mir,
  63             elements,
  64             flow_inits,
  65             move_data,
  66             live_locals,
  67             location_table,
  68         );
  69     }
  70 }
  71
  72 // The purpose of `compute_live_locals` is to define the subset of `Local`
  73 // variables for which we need to do a liveness computation. We only need
  74 // to compute whether a variable `X` is live if that variable contains
  75 // some region `R` in its type where `R` is not known to outlive a free
  76 // region (i.e., where `R` may be valid for just a subset of the fn body).
  77 fn compute_live_locals(
  78     tcx: TyCtxt<'_, '_, 'tcx>,
  79     free_regions: &FxHashSet<RegionVid>,
  80     mir: &Body<'tcx>,
  81 ) -> Vec<Local> {
  82     let live_locals: Vec<Local> = mir
  83         .local_decls
  84         .iter_enumerated()
  85         .filter_map(|(local, local_decl)| {
  86             if tcx.all_free_regions_meet(&local_decl.ty, |r| {
  87                 free_regions.contains(&r.to_region_vid())
  88             }) {
  89                 None
  90             } else {
  91                 Some(local)
  92             }
  93         })
  94         .collect();
  95
  96     debug!("{} total variables", mir.local_decls.len());
  97     debug!("{} variables need liveness", live_locals.len());
  98     debug!("{} regions outlive free regions", free_regions.len());
  99
 100     live_locals
 101 }
 102
 103 /// Computes all regions that are (currently) known to outlive free
 104 /// regions. For these regions, we do not need to compute
 105 /// liveness, since the outlives constraints will ensure that they
 106 /// are live over the whole fn body anyhow.
 107 fn regions_that_outlive_free_regions(
 108     num_region_vars: usize,
 109     universal_regions: &UniversalRegions<'tcx>,
 110     constraint_set: &ConstraintSet,
 111 ) -> FxHashSet<RegionVid> {
 112     // Build a graph of the outlives constraints thus far. This is
 113     // a reverse graph, so for each constraint `R1: R2` we have an
 114     // edge `R2 -> R1`. Therefore, if we find all regions
 115     // reachable from each free region, we will have all the
 116     // regions that are forced to outlive some free region.
 117     let rev_constraint_graph = constraint_set.reverse_graph(num_region_vars);
 118     let fr_static = universal_regions.fr_static;
 119     let rev_region_graph = rev_constraint_graph.region_graph(constraint_set, fr_static);
 120
 121     // Stack for the depth-first search. Start out with all the free regions.
 122     let mut stack: Vec<_> = universal_regions.universal_regions().collect();
 123
 124     // Set of all free regions, plus anything that outlives them. Initially
 125     // just contains the free regions.
 126     let mut outlives_free_region: FxHashSet<_> = stack.iter().cloned().collect();
 127
 128     // Do the DFS -- for each thing in the stack, find all things
 129     // that outlive it and add them to the set. If they are not,
 130     // push them onto the stack for later.
 131     while let Some(sub_region) = stack.pop() {
 132         stack.extend(
 133             rev_region_graph
 134                 .outgoing_regions(sub_region)
 135                 .filter(|&r| outlives_free_region.insert(r)),
 136         );
 137     }
 138
 139     // Return the final set of things we visited.
 140     outlives_free_region
 141 }