]>
Commit | Line | Data |
---|---|---|
b7449926 | 1 | use rustc_data_structures::vec_linked_list as vll; |
dfeec247 | 2 | use rustc_index::vec::IndexVec; |
ba9703b0 | 3 | use rustc_middle::mir::visit::{PlaceContext, Visitor}; |
f9f354fc | 4 | use rustc_middle::mir::{Body, Local, Location}; |
60c5eb7d | 5 | |
f9f354fc | 6 | use crate::borrow_check::def_use::{self, DefUse}; |
60c5eb7d XL |
7 | use crate::borrow_check::region_infer::values::{PointIndex, RegionValueElements}; |
8 | ||
b7449926 XL |
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. | |
532ac7d7 XL |
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 { | |
b7449926 | 22 | /// Head of a linked list of **definitions** of each variable -- |
0731742a | 23 | /// definition in this context means assignment, e.g., `x` is |
b7449926 XL |
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. | |
532ac7d7 | 27 | first_def_at: IndexVec<Local, Option<AppearanceIndex>>, |
b7449926 XL |
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. | |
532ac7d7 | 33 | first_use_at: IndexVec<Local, Option<AppearanceIndex>>, |
b7449926 XL |
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. | |
532ac7d7 | 38 | first_drop_at: IndexVec<Local, Option<AppearanceIndex>>, |
b7449926 XL |
39 | |
40 | appearances: IndexVec<AppearanceIndex, Appearance>, | |
41 | } | |
42 | ||
43 | struct Appearance { | |
44 | point_index: PointIndex, | |
45 | next: Option<AppearanceIndex>, | |
46 | } | |
47 | ||
e74abb32 | 48 | rustc_index::newtype_index! { |
b7449926 XL |
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 | ||
532ac7d7 | 60 | impl LocalUseMap { |
b7449926 | 61 | crate fn build( |
532ac7d7 | 62 | live_locals: &Vec<Local>, |
b7449926 | 63 | elements: &RegionValueElements, |
f9f354fc | 64 | body: &Body<'_>, |
b7449926 | 65 | ) -> Self { |
dc9dc135 | 66 | let nones = IndexVec::from_elem_n(None, body.local_decls.len()); |
b7449926 | 67 | let mut local_use_map = LocalUseMap { |
b7449926 XL |
68 | first_def_at: nones.clone(), |
69 | first_use_at: nones.clone(), | |
70 | first_drop_at: nones, | |
71 | appearances: IndexVec::new(), | |
72 | }; | |
73 | ||
e74abb32 XL |
74 | if live_locals.is_empty() { |
75 | return local_use_map; | |
76 | } | |
77 | ||
532ac7d7 | 78 | let mut locals_with_use_data: IndexVec<Local, bool> = |
dc9dc135 | 79 | IndexVec::from_elem_n(false, body.local_decls.len()); |
e1599b0c XL |
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 } | |
ba9703b0 | 83 | .visit_body(&body); |
b7449926 XL |
84 | |
85 | local_use_map | |
86 | } | |
87 | ||
532ac7d7 | 88 | crate fn defs(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ { |
b7449926 XL |
89 | vll::iter(self.first_def_at[local], &self.appearances) |
90 | .map(move |aa| self.appearances[aa].point_index) | |
91 | } | |
92 | ||
532ac7d7 | 93 | crate fn uses(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ { |
b7449926 XL |
94 | vll::iter(self.first_use_at[local], &self.appearances) |
95 | .map(move |aa| self.appearances[aa].point_index) | |
96 | } | |
97 | ||
532ac7d7 | 98 | crate fn drops(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ { |
b7449926 XL |
99 | vll::iter(self.first_drop_at[local], &self.appearances) |
100 | .map(move |aa| self.appearances[aa].point_index) | |
101 | } | |
102 | } | |
103 | ||
532ac7d7 XL |
104 | struct LocalUseMapBuild<'me> { |
105 | local_use_map: &'me mut LocalUseMap, | |
b7449926 | 106 | elements: &'me RegionValueElements, |
532ac7d7 XL |
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>, | |
b7449926 XL |
116 | } |
117 | ||
532ac7d7 XL |
118 | impl LocalUseMapBuild<'_> { |
119 | fn insert_def(&mut self, local: Local, location: Location) { | |
b7449926 XL |
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 | ||
532ac7d7 | 128 | fn insert_use(&mut self, local: Local, location: Location) { |
b7449926 XL |
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 | ||
532ac7d7 | 137 | fn insert_drop(&mut self, local: Local, location: Location) { |
b7449926 XL |
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); | |
e1599b0c XL |
153 | let appearance_index = |
154 | appearances.push(Appearance { point_index, next: *first_appearance }); | |
b7449926 XL |
155 | *first_appearance = Some(appearance_index); |
156 | } | |
157 | } | |
158 | ||
532ac7d7 | 159 | impl Visitor<'tcx> for LocalUseMapBuild<'_> { |
48663c56 | 160 | fn visit_local(&mut self, &local: &Local, context: PlaceContext, location: Location) { |
532ac7d7 | 161 | if self.locals_with_use_data[local] { |
f9f354fc | 162 | match def_use::categorize(context) { |
532ac7d7 XL |
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), | |
b7449926 XL |
166 | _ => (), |
167 | } | |
168 | } | |
169 | } | |
170 | } |