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