]>
Commit | Line | Data |
---|---|---|
f9f354fc XL |
1 | use rustc_index::bit_set::BitSet; |
2 | use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor}; | |
3 | use rustc_middle::mir::{self, Local, Location}; | |
4 | ||
1b1a35ee | 5 | use crate::dataflow::{AnalysisDomain, Backward, GenKill, GenKillAnalysis}; |
f9f354fc XL |
6 | |
7 | /// A [live-variable dataflow analysis][liveness]. | |
8 | /// | |
9 | /// This analysis considers references as being used only at the point of the | |
10 | /// borrow. In other words, this analysis does not track uses because of references that already | |
29967ef6 | 11 | /// exist. See [this `mir-dataflow` test][flow-test] for an example. You almost never want to use |
f9f354fc XL |
12 | /// this analysis without also looking at the results of [`MaybeBorrowedLocals`]. |
13 | /// | |
fc512014 | 14 | /// [`MaybeBorrowedLocals`]: super::MaybeBorrowedLocals |
f9f354fc XL |
15 | /// [flow-test]: https://github.com/rust-lang/rust/blob/a08c47310c7d49cbdc5d7afb38408ba519967ecd/src/test/ui/mir-dataflow/liveness-ptr.rs |
16 | /// [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis | |
17 | pub struct MaybeLiveLocals; | |
18 | ||
19 | impl MaybeLiveLocals { | |
20 | fn transfer_function<T>(&self, trans: &'a mut T) -> TransferFunction<'a, T> { | |
21 | TransferFunction(trans) | |
22 | } | |
23 | } | |
24 | ||
f9f354fc | 25 | impl AnalysisDomain<'tcx> for MaybeLiveLocals { |
1b1a35ee | 26 | type Domain = BitSet<Local>; |
f9f354fc XL |
27 | type Direction = Backward; |
28 | ||
29 | const NAME: &'static str = "liveness"; | |
30 | ||
1b1a35ee XL |
31 | fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain { |
32 | // bottom = not live | |
33 | BitSet::new_empty(body.local_decls.len()) | |
f9f354fc XL |
34 | } |
35 | ||
1b1a35ee | 36 | fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) { |
f9f354fc XL |
37 | // No variables are live until we observe a use |
38 | } | |
39 | } | |
40 | ||
41 | impl GenKillAnalysis<'tcx> for MaybeLiveLocals { | |
1b1a35ee XL |
42 | type Idx = Local; |
43 | ||
f9f354fc XL |
44 | fn statement_effect( |
45 | &self, | |
46 | trans: &mut impl GenKill<Self::Idx>, | |
47 | statement: &mir::Statement<'tcx>, | |
48 | location: Location, | |
49 | ) { | |
50 | self.transfer_function(trans).visit_statement(statement, location); | |
51 | } | |
52 | ||
53 | fn terminator_effect( | |
54 | &self, | |
55 | trans: &mut impl GenKill<Self::Idx>, | |
56 | terminator: &mir::Terminator<'tcx>, | |
57 | location: Location, | |
58 | ) { | |
59 | self.transfer_function(trans).visit_terminator(terminator, location); | |
60 | } | |
61 | ||
62 | fn call_return_effect( | |
63 | &self, | |
64 | trans: &mut impl GenKill<Self::Idx>, | |
65 | _block: mir::BasicBlock, | |
66 | _func: &mir::Operand<'tcx>, | |
67 | _args: &[mir::Operand<'tcx>], | |
68 | dest_place: mir::Place<'tcx>, | |
69 | ) { | |
70 | if let Some(local) = dest_place.as_local() { | |
71 | trans.kill(local); | |
72 | } | |
73 | } | |
74 | ||
75 | fn yield_resume_effect( | |
76 | &self, | |
77 | trans: &mut impl GenKill<Self::Idx>, | |
78 | _resume_block: mir::BasicBlock, | |
79 | resume_place: mir::Place<'tcx>, | |
80 | ) { | |
81 | if let Some(local) = resume_place.as_local() { | |
82 | trans.kill(local); | |
83 | } | |
84 | } | |
85 | } | |
86 | ||
87 | struct TransferFunction<'a, T>(&'a mut T); | |
88 | ||
89 | impl<'tcx, T> Visitor<'tcx> for TransferFunction<'_, T> | |
90 | where | |
91 | T: GenKill<Local>, | |
92 | { | |
f035d41b XL |
93 | fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) { |
94 | let mir::Place { projection, local } = *place; | |
95 | ||
96 | // We purposefully do not call `super_place` here to avoid calling `visit_local` for this | |
97 | // place with one of the `Projection` variants of `PlaceContext`. | |
6a06907d | 98 | self.visit_projection(place.as_ref(), context, location); |
f035d41b XL |
99 | |
100 | match DefUse::for_place(context) { | |
101 | // Treat derefs as a use of the base local. `*p = 4` is not a def of `p` but a use. | |
102 | Some(_) if place.is_indirect() => self.0.gen(local), | |
103 | ||
104 | Some(DefUse::Def) if projection.is_empty() => self.0.kill(local), | |
105 | Some(DefUse::Use) => self.0.gen(local), | |
106 | _ => {} | |
107 | } | |
108 | } | |
109 | ||
f9f354fc | 110 | fn visit_local(&mut self, &local: &Local, context: PlaceContext, _: Location) { |
f035d41b XL |
111 | // Because we do not call `super_place` above, `visit_local` is only called for locals that |
112 | // do not appear as part of a `Place` in the MIR. This handles cases like the implicit use | |
113 | // of the return place in a `Return` terminator or the index in an `Index` projection. | |
f9f354fc XL |
114 | match DefUse::for_place(context) { |
115 | Some(DefUse::Def) => self.0.kill(local), | |
116 | Some(DefUse::Use) => self.0.gen(local), | |
117 | _ => {} | |
118 | } | |
119 | } | |
120 | } | |
121 | ||
122 | #[derive(Eq, PartialEq, Clone)] | |
123 | enum DefUse { | |
124 | Def, | |
125 | Use, | |
126 | } | |
127 | ||
128 | impl DefUse { | |
129 | fn for_place(context: PlaceContext) -> Option<DefUse> { | |
130 | match context { | |
131 | PlaceContext::NonUse(_) => None, | |
132 | ||
133 | PlaceContext::MutatingUse(MutatingUseContext::Store) => Some(DefUse::Def), | |
134 | ||
135 | // `MutatingUseContext::Call` and `MutatingUseContext::Yield` indicate that this is the | |
136 | // destination place for a `Call` return or `Yield` resume respectively. Since this is | |
29967ef6 | 137 | // only a `Def` when the function returns successfully, we handle this case separately |
f9f354fc XL |
138 | // in `call_return_effect` above. |
139 | PlaceContext::MutatingUse(MutatingUseContext::Call | MutatingUseContext::Yield) => None, | |
140 | ||
141 | // All other contexts are uses... | |
142 | PlaceContext::MutatingUse( | |
143 | MutatingUseContext::AddressOf | |
144 | | MutatingUseContext::AsmOutput | |
145 | | MutatingUseContext::Borrow | |
146 | | MutatingUseContext::Drop | |
f9f354fc XL |
147 | | MutatingUseContext::Retag, |
148 | ) | |
149 | | PlaceContext::NonMutatingUse( | |
150 | NonMutatingUseContext::AddressOf | |
151 | | NonMutatingUseContext::Copy | |
152 | | NonMutatingUseContext::Inspect | |
153 | | NonMutatingUseContext::Move | |
f9f354fc XL |
154 | | NonMutatingUseContext::ShallowBorrow |
155 | | NonMutatingUseContext::SharedBorrow | |
156 | | NonMutatingUseContext::UniqueBorrow, | |
157 | ) => Some(DefUse::Use), | |
f035d41b XL |
158 | |
159 | PlaceContext::MutatingUse(MutatingUseContext::Projection) | |
160 | | PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) => { | |
161 | unreachable!("A projection could be a def or a use and must be handled separately") | |
162 | } | |
f9f354fc XL |
163 | } |
164 | } | |
165 | } |