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

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