]>
Commit | Line | Data |
---|---|---|
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::{Local, Location, ReadOnlyBodyAndCache}; | |
5 | ||
6 | use crate::util::liveness::{categorize, DefUse}; | |
7 | ||
8 | use crate::borrow_check::region_infer::values::{PointIndex, RegionValueElements}; | |
9 | ||
10 | /// A map that cross references each local with the locations where it | |
11 | /// is defined (assigned), used, or dropped. Used during liveness | |
12 | /// computation. | |
13 | /// | |
14 | /// We keep track only of `Local`s we'll do the liveness analysis later, | |
15 | /// this means that our internal `IndexVec`s will only be sparsely populated. | |
16 | /// In the time-memory trade-off between keeping compact vectors with new | |
17 | /// indexes (and needing to continuously map the `Local` index to its compact | |
18 | /// counterpart) and having `IndexVec`s that we only use a fraction of, time | |
19 | /// (and code simplicity) was favored. The rationale is that we only keep | |
20 | /// a small number of `IndexVec`s throughout the entire analysis while, in | |
21 | /// contrast, we're accessing each `Local` *many* times. | |
22 | crate struct LocalUseMap { | |
23 | /// Head of a linked list of **definitions** of each variable -- | |
24 | /// definition in this context means assignment, e.g., `x` is | |
25 | /// defined in `x = y` but not `y`; that first def is the head of | |
26 | /// a linked list that lets you enumerate all places the variable | |
27 | /// is assigned. | |
28 | first_def_at: IndexVec<Local, Option<AppearanceIndex>>, | |
29 | ||
30 | /// Head of a linked list of **uses** of each variable -- use in | |
31 | /// this context means that the existing value of the variable is | |
32 | /// read or modified. e.g., `y` is used in `x = y` but not `x`. | |
33 | /// Note that `DROP(x)` terminators are excluded from this list. | |
34 | first_use_at: IndexVec<Local, Option<AppearanceIndex>>, | |
35 | ||
36 | /// Head of a linked list of **drops** of each variable -- these | |
37 | /// are a special category of uses corresponding to the drop that | |
38 | /// we add for each local variable. | |
39 | first_drop_at: IndexVec<Local, Option<AppearanceIndex>>, | |
40 | ||
41 | appearances: IndexVec<AppearanceIndex, Appearance>, | |
42 | } | |
43 | ||
44 | struct Appearance { | |
45 | point_index: PointIndex, | |
46 | next: Option<AppearanceIndex>, | |
47 | } | |
48 | ||
49 | rustc_index::newtype_index! { | |
50 | pub struct AppearanceIndex { .. } | |
51 | } | |
52 | ||
53 | impl vll::LinkElem for Appearance { | |
54 | type LinkIndex = AppearanceIndex; | |
55 | ||
56 | fn next(elem: &Self) -> Option<AppearanceIndex> { | |
57 | elem.next | |
58 | } | |
59 | } | |
60 | ||
61 | impl LocalUseMap { | |
62 | crate fn build( | |
63 | live_locals: &Vec<Local>, | |
64 | elements: &RegionValueElements, | |
65 | body: ReadOnlyBodyAndCache<'_, '_>, | |
66 | ) -> Self { | |
67 | let nones = IndexVec::from_elem_n(None, body.local_decls.len()); | |
68 | let mut local_use_map = LocalUseMap { | |
69 | first_def_at: nones.clone(), | |
70 | first_use_at: nones.clone(), | |
71 | first_drop_at: nones, | |
72 | appearances: IndexVec::new(), | |
73 | }; | |
74 | ||
75 | if live_locals.is_empty() { | |
76 | return local_use_map; | |
77 | } | |
78 | ||
79 | let mut locals_with_use_data: IndexVec<Local, bool> = | |
80 | IndexVec::from_elem_n(false, body.local_decls.len()); | |
81 | live_locals.iter().for_each(|&local| locals_with_use_data[local] = true); | |
82 | ||
83 | LocalUseMapBuild { local_use_map: &mut local_use_map, elements, locals_with_use_data } | |
84 | .visit_body(&body); | |
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 = | |
155 | appearances.push(Appearance { point_index, next: *first_appearance }); | |
156 | *first_appearance = Some(appearance_index); | |
157 | } | |
158 | } | |
159 | ||
160 | impl Visitor<'tcx> for LocalUseMapBuild<'_> { | |
161 | fn visit_local(&mut self, &local: &Local, context: PlaceContext, location: Location) { | |
162 | if self.locals_with_use_data[local] { | |
163 | match categorize(context) { | |
164 | Some(DefUse::Def) => self.insert_def(local, location), | |
165 | Some(DefUse::Use) => self.insert_use(local, location), | |
166 | Some(DefUse::Drop) => self.insert_drop(local, location), | |
167 | _ => (), | |
168 | } | |
169 | } | |
170 | } | |
171 | } |