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
|
use rustc_index::bit_set::BitSet;
use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
use rustc_middle::mir::{self, Local, Location};
use crate::dataflow::{AnalysisDomain, Backward, BottomValue, GenKill, GenKillAnalysis};
/// A [live-variable dataflow analysis][liveness].
///
/// This analysis considers references as being used only at the point of the
/// borrow. In other words, this analysis does not track uses because of references that already
/// exist. See [this `mir-datalow` test][flow-test] for an example. You almost never want to use
/// this analysis without also looking at the results of [`MaybeBorrowedLocals`].
///
/// [`MaybeBorrowedLocals`]: ../struct.MaybeBorrowedLocals.html
/// [flow-test]: https://github.com/rust-lang/rust/blob/a08c47310c7d49cbdc5d7afb38408ba519967ecd/src/test/ui/mir-dataflow/liveness-ptr.rs
/// [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis
pub struct MaybeLiveLocals;
impl MaybeLiveLocals {
fn transfer_function<T>(&self, trans: &'a mut T) -> TransferFunction<'a, T> {
TransferFunction(trans)
}
}
impl BottomValue for MaybeLiveLocals {
// bottom = not live
const BOTTOM_VALUE: bool = false;
}
impl AnalysisDomain<'tcx> for MaybeLiveLocals {
type Idx = Local;
type Direction = Backward;
const NAME: &'static str = "liveness";
fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize {
body.local_decls.len()
}
fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut BitSet<Self::Idx>) {
// No variables are live until we observe a use
}
}
impl GenKillAnalysis<'tcx> for MaybeLiveLocals {
fn statement_effect(
&self,
trans: &mut impl GenKill<Self::Idx>,
statement: &mir::Statement<'tcx>,
location: Location,
) {
self.transfer_function(trans).visit_statement(statement, location);
}
fn terminator_effect(
&self,
trans: &mut impl GenKill<Self::Idx>,
terminator: &mir::Terminator<'tcx>,
location: Location,
) {
self.transfer_function(trans).visit_terminator(terminator, location);
}
fn call_return_effect(
&self,
trans: &mut impl GenKill<Self::Idx>,
_block: mir::BasicBlock,
_func: &mir::Operand<'tcx>,
_args: &[mir::Operand<'tcx>],
dest_place: mir::Place<'tcx>,
) {
if let Some(local) = dest_place.as_local() {
trans.kill(local);
}
}
fn yield_resume_effect(
&self,
trans: &mut impl GenKill<Self::Idx>,
_resume_block: mir::BasicBlock,
resume_place: mir::Place<'tcx>,
) {
if let Some(local) = resume_place.as_local() {
trans.kill(local);
}
}
}
struct TransferFunction<'a, T>(&'a mut T);
impl<'tcx, T> Visitor<'tcx> for TransferFunction<'_, T>
where
T: GenKill<Local>,
{
fn visit_local(&mut self, &local: &Local, context: PlaceContext, _: Location) {
match DefUse::for_place(context) {
Some(DefUse::Def) => self.0.kill(local),
Some(DefUse::Use) => self.0.gen(local),
_ => {}
}
}
}
#[derive(Eq, PartialEq, Clone)]
enum DefUse {
Def,
Use,
}
impl DefUse {
fn for_place(context: PlaceContext) -> Option<DefUse> {
match context {
PlaceContext::NonUse(_) => None,
PlaceContext::MutatingUse(MutatingUseContext::Store) => Some(DefUse::Def),
// `MutatingUseContext::Call` and `MutatingUseContext::Yield` indicate that this is the
// destination place for a `Call` return or `Yield` resume respectively. Since this is
// only a `Def` when the function returns succesfully, we handle this case separately
// in `call_return_effect` above.
PlaceContext::MutatingUse(MutatingUseContext::Call | MutatingUseContext::Yield) => None,
// All other contexts are uses...
PlaceContext::MutatingUse(
MutatingUseContext::AddressOf
| MutatingUseContext::AsmOutput
| MutatingUseContext::Borrow
| MutatingUseContext::Drop
| MutatingUseContext::Projection
| MutatingUseContext::Retag,
)
| PlaceContext::NonMutatingUse(
NonMutatingUseContext::AddressOf
| NonMutatingUseContext::Copy
| NonMutatingUseContext::Inspect
| NonMutatingUseContext::Move
| NonMutatingUseContext::Projection
| NonMutatingUseContext::ShallowBorrow
| NonMutatingUseContext::SharedBorrow
| NonMutatingUseContext::UniqueBorrow,
) => Some(DefUse::Use),
}
}
}
|
