]>
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 | |
c295e0f8 XL |
6 | use crate::def_use::{self, DefUse}; |
7 | use crate::region_infer::values::{PointIndex, RegionValueElements}; | |
60c5eb7d | 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 { |
5869c6ff | 61 | crate fn build(live_locals: &[Local], elements: &RegionValueElements, body: &Body<'_>) -> Self { |
dc9dc135 | 62 | let nones = IndexVec::from_elem_n(None, body.local_decls.len()); |
b7449926 | 63 | let mut local_use_map = LocalUseMap { |
b7449926 XL |
64 | first_def_at: nones.clone(), |
65 | first_use_at: nones.clone(), | |
66 | first_drop_at: nones, | |
67 | appearances: IndexVec::new(), | |
68 | }; | |
69 | ||
e74abb32 XL |
70 | if live_locals.is_empty() { |
71 | return local_use_map; | |
72 | } | |
73 | ||
532ac7d7 | 74 | let mut locals_with_use_data: IndexVec<Local, bool> = |
dc9dc135 | 75 | IndexVec::from_elem_n(false, body.local_decls.len()); |
e1599b0c XL |
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 } | |
ba9703b0 | 79 | .visit_body(&body); |
b7449926 XL |
80 | |
81 | local_use_map | |
82 | } | |
83 | ||
532ac7d7 | 84 | crate fn defs(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ { |
b7449926 XL |
85 | vll::iter(self.first_def_at[local], &self.appearances) |
86 | .map(move |aa| self.appearances[aa].point_index) | |
87 | } | |
88 | ||
532ac7d7 | 89 | crate fn uses(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ { |
b7449926 XL |
90 | vll::iter(self.first_use_at[local], &self.appearances) |
91 | .map(move |aa| self.appearances[aa].point_index) | |
92 | } | |
93 | ||
532ac7d7 | 94 | crate fn drops(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ { |
b7449926 XL |
95 | vll::iter(self.first_drop_at[local], &self.appearances) |
96 | .map(move |aa| self.appearances[aa].point_index) | |
97 | } | |
98 | } | |
99 | ||
532ac7d7 XL |
100 | struct LocalUseMapBuild<'me> { |
101 | local_use_map: &'me mut LocalUseMap, | |
b7449926 | 102 | elements: &'me RegionValueElements, |
532ac7d7 XL |
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>, | |
b7449926 XL |
112 | } |
113 | ||
532ac7d7 XL |
114 | impl LocalUseMapBuild<'_> { |
115 | fn insert_def(&mut self, local: Local, location: Location) { | |
b7449926 XL |
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 | ||
532ac7d7 | 124 | fn insert_use(&mut self, local: Local, location: Location) { |
b7449926 XL |
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 | ||
532ac7d7 | 133 | fn insert_drop(&mut self, local: Local, location: Location) { |
b7449926 XL |
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 | ||
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); | |
e1599b0c XL |
149 | let appearance_index = |
150 | appearances.push(Appearance { point_index, next: *first_appearance }); | |
b7449926 XL |
151 | *first_appearance = Some(appearance_index); |
152 | } | |
153 | } | |
154 | ||
a2a8927a | 155 | impl Visitor<'_> for LocalUseMapBuild<'_> { |
48663c56 | 156 | fn visit_local(&mut self, &local: &Local, context: PlaceContext, location: Location) { |
532ac7d7 | 157 | if self.locals_with_use_data[local] { |
f9f354fc | 158 | match def_use::categorize(context) { |
532ac7d7 XL |
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), | |
b7449926 XL |
162 | _ => (), |
163 | } | |
164 | } | |
165 | } | |
166 | } |