rustc_borrowck/type_check/liveness/
local_use_map.rs

1use rustc_index::IndexVec;
2use rustc_middle::mir::visit::{PlaceContext, Visitor};
3use rustc_middle::mir::{Body, Local, Location};
4use rustc_mir_dataflow::points::{DenseLocationMap, PointIndex};
5
6use crate::def_use::{self, DefUse};
7
8/// A map that cross references each local with the locations where it
9/// is defined (assigned), used, or dropped. Used during liveness
10/// computation.
11///
12/// We keep track only of `Local`s we'll do the liveness analysis later,
13/// this means that our internal `IndexVec`s will only be sparsely populated.
14/// In the time-memory trade-off between keeping compact vectors with new
15/// indexes (and needing to continuously map the `Local` index to its compact
16/// counterpart) and having `IndexVec`s that we only use a fraction of, time
17/// (and code simplicity) was favored. The rationale is that we only keep
18/// a small number of `IndexVec`s throughout the entire analysis while, in
19/// contrast, we're accessing each `Local` *many* times.
20pub(crate) struct LocalUseMap {
21    /// Head of a linked list of **definitions** of each variable --
22    /// definition in this context means assignment, e.g., `x` is
23    /// defined in `x = y` but not `y`; that first def is the head of
24    /// a linked list that lets you enumerate all places the variable
25    /// is assigned.
26    first_def_at: IndexVec<Local, Option<AppearanceIndex>>,
27
28    /// Head of a linked list of **uses** of each variable -- use in
29    /// this context means that the existing value of the variable is
30    /// read or modified. e.g., `y` is used in `x = y` but not `x`.
31    /// Note that `DROP(x)` terminators are excluded from this list.
32    first_use_at: IndexVec<Local, Option<AppearanceIndex>>,
33
34    /// Head of a linked list of **drops** of each variable -- these
35    /// are a special category of uses corresponding to the drop that
36    /// we add for each local variable.
37    first_drop_at: IndexVec<Local, Option<AppearanceIndex>>,
38
39    appearances: Appearances,
40}
41
42// The `Appearance::next` field effectively embeds a linked list within `Appearances`.
43type Appearances = IndexVec<AppearanceIndex, Appearance>;
44
45struct Appearance {
46    point_index: PointIndex,
47    next: Option<AppearanceIndex>,
48}
49
50rustc_index::newtype_index! {
51    pub struct AppearanceIndex {}
52}
53
54fn appearances_iter(
55    first: Option<AppearanceIndex>,
56    appearances: &Appearances,
57) -> impl Iterator<Item = AppearanceIndex> {
58    AppearancesIter { appearances, current: first }
59}
60
61// Iterates over `Appearances` by following `next` fields.
62struct AppearancesIter<'a> {
63    appearances: &'a Appearances,
64    current: Option<AppearanceIndex>,
65}
66
67impl<'a> Iterator for AppearancesIter<'a> {
68    type Item = AppearanceIndex;
69
70    fn next(&mut self) -> Option<AppearanceIndex> {
71        if let Some(c) = self.current {
72            self.current = self.appearances[c].next;
73            Some(c)
74        } else {
75            None
76        }
77    }
78}
79
80//-----------------------------------------------------------------------------
81
82impl LocalUseMap {
83    pub(crate) fn build(
84        live_locals: &[Local],
85        location_map: &DenseLocationMap,
86        body: &Body<'_>,
87    ) -> Self {
88        let nones = IndexVec::from_elem(None, &body.local_decls);
89        let mut local_use_map = LocalUseMap {
90            first_def_at: nones.clone(),
91            first_use_at: nones.clone(),
92            first_drop_at: nones,
93            appearances: IndexVec::new(),
94        };
95
96        if live_locals.is_empty() {
97            return local_use_map;
98        }
99
100        let mut locals_with_use_data: IndexVec<Local, bool> =
101            IndexVec::from_elem(false, &body.local_decls);
102        live_locals.iter().for_each(|&local| locals_with_use_data[local] = true);
103
104        LocalUseMapBuild { local_use_map: &mut local_use_map, location_map, locals_with_use_data }
105            .visit_body(body);
106
107        local_use_map
108    }
109
110    pub(crate) fn defs(&self, local: Local) -> impl Iterator<Item = PointIndex> {
111        appearances_iter(self.first_def_at[local], &self.appearances)
112            .map(move |aa| self.appearances[aa].point_index)
113    }
114
115    pub(crate) fn uses(&self, local: Local) -> impl Iterator<Item = PointIndex> {
116        appearances_iter(self.first_use_at[local], &self.appearances)
117            .map(move |aa| self.appearances[aa].point_index)
118    }
119
120    pub(crate) fn drops(&self, local: Local) -> impl Iterator<Item = PointIndex> {
121        appearances_iter(self.first_drop_at[local], &self.appearances)
122            .map(move |aa| self.appearances[aa].point_index)
123    }
124}
125
126struct LocalUseMapBuild<'me> {
127    local_use_map: &'me mut LocalUseMap,
128    location_map: &'me DenseLocationMap,
129
130    // Vector used in `visit_local` to signal which `Local`s do we need
131    // def/use/drop information on, constructed from `live_locals` (that
132    // contains the variables we'll do the liveness analysis for).
133    // This vector serves optimization purposes only: we could have
134    // obtained the same information from `live_locals` but we want to
135    // avoid repeatedly calling `Vec::contains()` (see `LocalUseMap` for
136    // the rationale on the time-memory trade-off we're favoring here).
137    locals_with_use_data: IndexVec<Local, bool>,
138}
139
140impl Visitor<'_> for LocalUseMapBuild<'_> {
141    fn visit_local(&mut self, local: Local, context: PlaceContext, location: Location) {
142        if self.locals_with_use_data[local]
143            && let Some(def_use) = def_use::categorize(context)
144        {
145            let first_appearance = match def_use {
146                DefUse::Def => &mut self.local_use_map.first_def_at[local],
147                DefUse::Use => &mut self.local_use_map.first_use_at[local],
148                DefUse::Drop => &mut self.local_use_map.first_drop_at[local],
149            };
150            let point_index = self.location_map.point_from_location(location);
151            let appearance_index = self
152                .local_use_map
153                .appearances
154                .push(Appearance { point_index, next: *first_appearance });
155            *first_appearance = Some(appearance_index);
156        }
157    }
158}
rustc_borrowck/type_check/liveness/local_use_map.rs

rustc_borrowck/type_check/liveness/
local_use_map.rs
