compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs

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