rustc_borrowck/type_check/liveness/
local_use_map.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
use rustc_index::IndexVec;
use rustc_middle::mir::visit::{PlaceContext, Visitor};
use rustc_middle::mir::{Body, Local, Location};
use rustc_mir_dataflow::points::{DenseLocationMap, PointIndex};

use crate::def_use::{self, DefUse};

/// A map that cross references each local with the locations where it
/// is defined (assigned), used, or dropped. Used during liveness
/// computation.
///
/// We keep track only of `Local`s we'll do the liveness analysis later,
/// this means that our internal `IndexVec`s will only be sparsely populated.
/// In the time-memory trade-off between keeping compact vectors with new
/// indexes (and needing to continuously map the `Local` index to its compact
/// counterpart) and having `IndexVec`s that we only use a fraction of, time
/// (and code simplicity) was favored. The rationale is that we only keep
/// a small number of `IndexVec`s throughout the entire analysis while, in
/// contrast, we're accessing each `Local` *many* times.
pub(crate) struct LocalUseMap {
    /// Head of a linked list of **definitions** of each variable --
    /// definition in this context means assignment, e.g., `x` is
    /// defined in `x = y` but not `y`; that first def is the head of
    /// a linked list that lets you enumerate all places the variable
    /// is assigned.
    first_def_at: IndexVec<Local, Option<AppearanceIndex>>,

    /// Head of a linked list of **uses** of each variable -- use in
    /// this context means that the existing value of the variable is
    /// read or modified. e.g., `y` is used in `x = y` but not `x`.
    /// Note that `DROP(x)` terminators are excluded from this list.
    first_use_at: IndexVec<Local, Option<AppearanceIndex>>,

    /// Head of a linked list of **drops** of each variable -- these
    /// are a special category of uses corresponding to the drop that
    /// we add for each local variable.
    first_drop_at: IndexVec<Local, Option<AppearanceIndex>>,

    appearances: Appearances,
}

// The `Appearance::next` field effectively embeds a linked list within `Appearances`.
type Appearances = IndexVec<AppearanceIndex, Appearance>;

struct Appearance {
    point_index: PointIndex,
    next: Option<AppearanceIndex>,
}

rustc_index::newtype_index! {
    pub struct AppearanceIndex {}
}

fn appearances_iter(
    first: Option<AppearanceIndex>,
    appearances: &Appearances,
) -> impl Iterator<Item = AppearanceIndex> + '_ {
    AppearancesIter { appearances, current: first }
}

// Iterates over `Appearances` by following `next` fields.
struct AppearancesIter<'a> {
    appearances: &'a Appearances,
    current: Option<AppearanceIndex>,
}

impl<'a> Iterator for AppearancesIter<'a> {
    type Item = AppearanceIndex;

    fn next(&mut self) -> Option<AppearanceIndex> {
        if let Some(c) = self.current {
            self.current = self.appearances[c].next;
            Some(c)
        } else {
            None
        }
    }
}

//-----------------------------------------------------------------------------

impl LocalUseMap {
    pub(crate) fn build(
        live_locals: &[Local],
        elements: &DenseLocationMap,
        body: &Body<'_>,
    ) -> Self {
        let nones = IndexVec::from_elem(None, &body.local_decls);
        let mut local_use_map = LocalUseMap {
            first_def_at: nones.clone(),
            first_use_at: nones.clone(),
            first_drop_at: nones,
            appearances: IndexVec::new(),
        };

        if live_locals.is_empty() {
            return local_use_map;
        }

        let mut locals_with_use_data: IndexVec<Local, bool> =
            IndexVec::from_elem(false, &body.local_decls);
        live_locals.iter().for_each(|&local| locals_with_use_data[local] = true);

        LocalUseMapBuild { local_use_map: &mut local_use_map, elements, locals_with_use_data }
            .visit_body(body);

        local_use_map
    }

    pub(crate) fn defs(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ {
        appearances_iter(self.first_def_at[local], &self.appearances)
            .map(move |aa| self.appearances[aa].point_index)
    }

    pub(crate) fn uses(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ {
        appearances_iter(self.first_use_at[local], &self.appearances)
            .map(move |aa| self.appearances[aa].point_index)
    }

    pub(crate) fn drops(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ {
        appearances_iter(self.first_drop_at[local], &self.appearances)
            .map(move |aa| self.appearances[aa].point_index)
    }
}

struct LocalUseMapBuild<'me> {
    local_use_map: &'me mut LocalUseMap,
    elements: &'me DenseLocationMap,

    // Vector used in `visit_local` to signal which `Local`s do we need
    // def/use/drop information on, constructed from `live_locals` (that
    // contains the variables we'll do the liveness analysis for).
    // This vector serves optimization purposes only: we could have
    // obtained the same information from `live_locals` but we want to
    // avoid repeatedly calling `Vec::contains()` (see `LocalUseMap` for
    // the rationale on the time-memory trade-off we're favoring here).
    locals_with_use_data: IndexVec<Local, bool>,
}

impl Visitor<'_> for LocalUseMapBuild<'_> {
    fn visit_local(&mut self, local: Local, context: PlaceContext, location: Location) {
        if self.locals_with_use_data[local]
            && let Some(def_use) = def_use::categorize(context)
        {
            let first_appearance = match def_use {
                DefUse::Def => &mut self.local_use_map.first_def_at[local],
                DefUse::Use => &mut self.local_use_map.first_use_at[local],
                DefUse::Drop => &mut self.local_use_map.first_drop_at[local],
            };
            let point_index = self.elements.point_from_location(location);
            let appearance_index = self
                .local_use_map
                .appearances
                .push(Appearance { point_index, next: *first_appearance });
            *first_appearance = Some(appearance_index);
        }
    }
}