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}
;
6 use crate::def_use
::{self, DefUse}
;
7 use crate::region_infer
::values
::{PointIndex, RegionValueElements}
;
9 /// A map that cross references each local with the locations where it
10 /// is defined (assigned), used, or dropped. Used during liveness
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 pub(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
27 first_def_at
: IndexVec
<Local
, Option
<AppearanceIndex
>>,
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
>>,
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
>>,
40 appearances
: IndexVec
<AppearanceIndex
, Appearance
>,
44 point_index
: PointIndex
,
45 next
: Option
<AppearanceIndex
>,
48 rustc_index
::newtype_index
! {
49 pub struct AppearanceIndex { .. }
52 impl vll
::LinkElem
for Appearance
{
53 type LinkIndex
= AppearanceIndex
;
55 fn next(elem
: &Self) -> Option
<AppearanceIndex
> {
62 live_locals
: &[Local
],
63 elements
: &RegionValueElements
,
66 let nones
= IndexVec
::from_elem_n(None
, body
.local_decls
.len());
67 let mut local_use_map
= LocalUseMap
{
68 first_def_at
: nones
.clone(),
69 first_use_at
: nones
.clone(),
71 appearances
: IndexVec
::new(),
74 if live_locals
.is_empty() {
78 let mut locals_with_use_data
: IndexVec
<Local
, bool
> =
79 IndexVec
::from_elem_n(false, body
.local_decls
.len());
80 live_locals
.iter().for_each(|&local
| locals_with_use_data
[local
] = true);
82 LocalUseMapBuild { local_use_map: &mut local_use_map, elements, locals_with_use_data }
88 pub(crate) fn defs(&self, local
: Local
) -> impl Iterator
<Item
= PointIndex
> + '_
{
89 vll
::iter(self.first_def_at
[local
], &self.appearances
)
90 .map(move |aa
| self.appearances
[aa
].point_index
)
93 pub(crate) fn uses(&self, local
: Local
) -> impl Iterator
<Item
= PointIndex
> + '_
{
94 vll
::iter(self.first_use_at
[local
], &self.appearances
)
95 .map(move |aa
| self.appearances
[aa
].point_index
)
98 pub(crate) fn drops(&self, local
: Local
) -> impl Iterator
<Item
= PointIndex
> + '_
{
99 vll
::iter(self.first_drop_at
[local
], &self.appearances
)
100 .map(move |aa
| self.appearances
[aa
].point_index
)
104 struct LocalUseMapBuild
<'me
> {
105 local_use_map
: &'me
mut LocalUseMap
,
106 elements
: &'me RegionValueElements
,
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
>,
118 impl LocalUseMapBuild
<'_
> {
119 fn insert_def(&mut self, local
: Local
, location
: Location
) {
122 &mut self.local_use_map
.first_def_at
[local
],
123 &mut self.local_use_map
.appearances
,
128 fn insert_use(&mut self, local
: Local
, location
: Location
) {
131 &mut self.local_use_map
.first_use_at
[local
],
132 &mut self.local_use_map
.appearances
,
137 fn insert_drop(&mut self, local
: Local
, location
: Location
) {
140 &mut self.local_use_map
.first_drop_at
[local
],
141 &mut self.local_use_map
.appearances
,
147 elements
: &RegionValueElements
,
148 first_appearance
: &mut Option
<AppearanceIndex
>,
149 appearances
: &mut IndexVec
<AppearanceIndex
, Appearance
>,
152 let point_index
= elements
.point_from_location(location
);
153 let appearance_index
=
154 appearances
.push(Appearance { point_index, next: *first_appearance }
);
155 *first_appearance
= Some(appearance_index
);
159 impl Visitor
<'_
> for LocalUseMapBuild
<'_
> {
160 fn visit_local(&mut self, local
: Local
, context
: PlaceContext
, location
: Location
) {
161 if self.locals_with_use_data
[local
] {
162 match def_use
::categorize(context
) {
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
),