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