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, ReadOnlyBodyCache};
   5 use rustc_index::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 rustc_index::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         body: ReadOnlyBodyCache<'_, '_>,
  64     ) -> Self {
  65         let nones = IndexVec::from_elem_n(None, body.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         if live_locals.is_empty() {
  74             return local_use_map;
  75         }
  76
  77         let mut locals_with_use_data: IndexVec<Local, bool> =
  78             IndexVec::from_elem_n(false, body.local_decls.len());
  79         live_locals.iter().for_each(|&local| locals_with_use_data[local] = true);
  80
  81         LocalUseMapBuild { local_use_map: &mut local_use_map, elements, locals_with_use_data }
  82             .visit_body(body);
  83
  84         local_use_map
  85     }
  86
  87     crate fn defs(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ {
  88         vll::iter(self.first_def_at[local], &self.appearances)
  89             .map(move |aa| self.appearances[aa].point_index)
  90     }
  91
  92     crate fn uses(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ {
  93         vll::iter(self.first_use_at[local], &self.appearances)
  94             .map(move |aa| self.appearances[aa].point_index)
  95     }
  96
  97     crate fn drops(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ {
  98         vll::iter(self.first_drop_at[local], &self.appearances)
  99             .map(move |aa| self.appearances[aa].point_index)
 100     }
 101 }
 102
 103 struct LocalUseMapBuild<'me> {
 104     local_use_map: &'me mut LocalUseMap,
 105     elements: &'me RegionValueElements,
 106
 107     // Vector used in `visit_local` to signal which `Local`s do we need
 108     // def/use/drop information on, constructed from `live_locals` (that
 109     // contains the variables we'll do the liveness analysis for).
 110     // This vector serves optimization purposes only: we could have
 111     // obtained the same information from `live_locals` but we want to
 112     // avoid repeatedly calling `Vec::contains()` (see `LocalUseMap` for
 113     // the rationale on the time-memory trade-off we're favoring here).
 114     locals_with_use_data: IndexVec<Local, bool>,
 115 }
 116
 117 impl LocalUseMapBuild<'_> {
 118     fn insert_def(&mut self, local: Local, location: Location) {
 119         Self::insert(
 120             self.elements,
 121             &mut self.local_use_map.first_def_at[local],
 122             &mut self.local_use_map.appearances,
 123             location,
 124         );
 125     }
 126
 127     fn insert_use(&mut self, local: Local, location: Location) {
 128         Self::insert(
 129             self.elements,
 130             &mut self.local_use_map.first_use_at[local],
 131             &mut self.local_use_map.appearances,
 132             location,
 133         );
 134     }
 135
 136     fn insert_drop(&mut self, local: Local, location: Location) {
 137         Self::insert(
 138             self.elements,
 139             &mut self.local_use_map.first_drop_at[local],
 140             &mut self.local_use_map.appearances,
 141             location,
 142         );
 143     }
 144
 145     fn insert(
 146         elements: &RegionValueElements,
 147         first_appearance: &mut Option<AppearanceIndex>,
 148         appearances: &mut IndexVec<AppearanceIndex, Appearance>,
 149         location: Location,
 150     ) {
 151         let point_index = elements.point_from_location(location);
 152         let appearance_index =
 153             appearances.push(Appearance { point_index, next: *first_appearance });
 154         *first_appearance = Some(appearance_index);
 155     }
 156 }
 157
 158 impl Visitor<'tcx> for LocalUseMapBuild<'_> {
 159     fn visit_local(&mut self, &local: &Local, context: PlaceContext, location: Location) {
 160         if self.locals_with_use_data[local] {
 161             match categorize(context) {
 162                 Some(DefUse::Def) => self.insert_def(local, location),
 163                 Some(DefUse::Use) => self.insert_use(local, location),
 164                 Some(DefUse::Drop) => self.insert_drop(local, location),
 165                 _ => (),
 166             }
 167         }
 168     }
 169 }