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

   1 use crate::borrow_check::nll::region_infer::values::{PointIndex, RegionValueElements};
   2 use crate::util::liveness::{categorize, DefUse};
   3 use rustc::mir::visit::{PlaceContext, Visitor};
   4 use rustc::mir::{Local, Location, Body};
   5 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
   6 use rustc_data_structures::vec_linked_list as vll;
   7
   8 /// A map that cross references each local with the locations where it
   9 /// is defined (assigned), used, or dropped. Used during liveness
  10 /// computation.
  11 ///
  12 /// We keep track only of `Local`s we'll do the liveness analysis later,
  13 /// this means that our internal `IndexVec`s will only be sparsely populated.
  14 /// In the time-memory trade-off between keeping compact vectors with new
  15 /// indexes (and needing to continuously map the `Local` index to its compact
  16 /// counterpart) and having `IndexVec`s that we only use a fraction of, time
  17 /// (and code simplicity) was favored. The rationale is that we only keep
  18 /// a small number of `IndexVec`s throughout the entire analysis while, in
  19 /// contrast, we're accessing each `Local` *many* times.
  20 crate struct LocalUseMap {
  21     /// Head of a linked list of **definitions** of each variable --
  22     /// definition in this context means assignment, e.g., `x` is
  23     /// defined in `x = y` but not `y`; that first def is the head of
  24     /// a linked list that lets you enumerate all places the variable
  25     /// is assigned.
  26     first_def_at: IndexVec<Local, Option<AppearanceIndex>>,
  27
  28     /// Head of a linked list of **uses** of each variable -- use in
  29     /// this context means that the existing value of the variable is
  30     /// read or modified. e.g., `y` is used in `x = y` but not `x`.
  31     /// Note that `DROP(x)` terminators are excluded from this list.
  32     first_use_at: IndexVec<Local, Option<AppearanceIndex>>,
  33
  34     /// Head of a linked list of **drops** of each variable -- these
  35     /// are a special category of uses corresponding to the drop that
  36     /// we add for each local variable.
  37     first_drop_at: IndexVec<Local, Option<AppearanceIndex>>,
  38
  39     appearances: IndexVec<AppearanceIndex, Appearance>,
  40 }
  41
  42 struct Appearance {
  43     point_index: PointIndex,
  44     next: Option<AppearanceIndex>,
  45 }
  46
  47 newtype_index! {
  48     pub struct AppearanceIndex { .. }
  49 }
  50
  51 impl vll::LinkElem for Appearance {
  52     type LinkIndex = AppearanceIndex;
  53
  54     fn next(elem: &Self) -> Option<AppearanceIndex> {
  55         elem.next
  56     }
  57 }
  58
  59 impl LocalUseMap {
  60     crate fn build(
  61         live_locals: &Vec<Local>,
  62         elements: &RegionValueElements,
  63         mir: &Body<'_>,
  64     ) -> Self {
  65         let nones = IndexVec::from_elem_n(None, mir.local_decls.len());
  66         let mut local_use_map = LocalUseMap {
  67             first_def_at: nones.clone(),
  68             first_use_at: nones.clone(),
  69             first_drop_at: nones,
  70             appearances: IndexVec::new(),
  71         };
  72
  73         let mut locals_with_use_data: IndexVec<Local, bool> =
  74             IndexVec::from_elem_n(false, mir.local_decls.len());
  75         live_locals
  76             .iter()
  77             .for_each(|&local| locals_with_use_data[local] = true);
  78
  79         LocalUseMapBuild {
  80             local_use_map: &mut local_use_map,
  81             elements,
  82             locals_with_use_data,
  83         }
  84         .visit_body(mir);
  85
  86         local_use_map
  87     }
  88
  89     crate fn defs(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ {
  90         vll::iter(self.first_def_at[local], &self.appearances)
  91             .map(move |aa| self.appearances[aa].point_index)
  92     }
  93
  94     crate fn uses(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ {
  95         vll::iter(self.first_use_at[local], &self.appearances)
  96             .map(move |aa| self.appearances[aa].point_index)
  97     }
  98
  99     crate fn drops(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ {
 100         vll::iter(self.first_drop_at[local], &self.appearances)
 101             .map(move |aa| self.appearances[aa].point_index)
 102     }
 103 }
 104
 105 struct LocalUseMapBuild<'me> {
 106     local_use_map: &'me mut LocalUseMap,
 107     elements: &'me RegionValueElements,
 108
 109     // Vector used in `visit_local` to signal which `Local`s do we need
 110     // def/use/drop information on, constructed from `live_locals` (that
 111     // contains the variables we'll do the liveness analysis for).
 112     // This vector serves optimization purposes only: we could have
 113     // obtained the same information from `live_locals` but we want to
 114     // avoid repeatedly calling `Vec::contains()` (see `LocalUseMap` for
 115     // the rationale on the time-memory trade-off we're favoring here).
 116     locals_with_use_data: IndexVec<Local, bool>,
 117 }
 118
 119 impl LocalUseMapBuild<'_> {
 120     fn insert_def(&mut self, local: Local, location: Location) {
 121         Self::insert(
 122             self.elements,
 123             &mut self.local_use_map.first_def_at[local],
 124             &mut self.local_use_map.appearances,
 125             location,
 126         );
 127     }
 128
 129     fn insert_use(&mut self, local: Local, location: Location) {
 130         Self::insert(
 131             self.elements,
 132             &mut self.local_use_map.first_use_at[local],
 133             &mut self.local_use_map.appearances,
 134             location,
 135         );
 136     }
 137
 138     fn insert_drop(&mut self, local: Local, location: Location) {
 139         Self::insert(
 140             self.elements,
 141             &mut self.local_use_map.first_drop_at[local],
 142             &mut self.local_use_map.appearances,
 143             location,
 144         );
 145     }
 146
 147     fn insert(
 148         elements: &RegionValueElements,
 149         first_appearance: &mut Option<AppearanceIndex>,
 150         appearances: &mut IndexVec<AppearanceIndex, Appearance>,
 151         location: Location,
 152     ) {
 153         let point_index = elements.point_from_location(location);
 154         let appearance_index = appearances.push(Appearance {
 155             point_index,
 156             next: *first_appearance,
 157         });
 158         *first_appearance = Some(appearance_index);
 159     }
 160 }
 161
 162 impl Visitor<'tcx> for LocalUseMapBuild<'_> {
 163     fn visit_local(&mut self, &local: &Local, context: PlaceContext, location: Location) {
 164         if self.locals_with_use_data[local] {
 165             match categorize(context) {
 166                 Some(DefUse::Def) => self.insert_def(local, location),
 167                 Some(DefUse::Use) => self.insert_use(local, location),
 168                 Some(DefUse::Drop) => self.insert_drop(local, location),
 169                 _ => (),
 170             }
 171         }
 172     }
 173 }