1 use rustc_index
::bit_set
::{BitSet, ChunkedBitSet}
;
2 use rustc_middle
::mir
::visit
::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor}
;
3 use rustc_middle
::mir
::{self, Local, Location, Place, StatementKind}
;
5 use crate::{Analysis, AnalysisDomain, Backward, CallReturnPlaces, GenKill, GenKillAnalysis}
;
7 /// A [live-variable dataflow analysis][liveness].
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
11 /// exist. See [this `mir-dataflow` test][flow-test] for an example. You almost never want to use
12 /// this analysis without also looking at the results of [`MaybeBorrowedLocals`].
14 /// ## Field-(in)sensitivity
16 /// As the name suggests, this analysis is field insensitive. If a projection of a variable `x` is
17 /// assigned to (e.g. `x.0 = 42`), it does not "define" `x` as far as liveness is concerned. In fact,
18 /// such an assignment is currently marked as a "use" of `x` in an attempt to be maximally
21 /// [`MaybeBorrowedLocals`]: super::MaybeBorrowedLocals
22 /// [flow-test]: https://github.com/rust-lang/rust/blob/a08c47310c7d49cbdc5d7afb38408ba519967ecd/src/test/ui/mir-dataflow/liveness-ptr.rs
23 /// [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis
24 pub struct MaybeLiveLocals
;
26 impl<'tcx
> AnalysisDomain
<'tcx
> for MaybeLiveLocals
{
27 type Domain
= ChunkedBitSet
<Local
>;
28 type Direction
= Backward
;
30 const NAME
: &'
static str = "liveness";
32 fn bottom_value(&self, body
: &mir
::Body
<'tcx
>) -> Self::Domain
{
34 ChunkedBitSet
::new_empty(body
.local_decls
.len())
37 fn initialize_start_block(&self, _
: &mir
::Body
<'tcx
>, _
: &mut Self::Domain
) {
38 // No variables are live until we observe a use
42 impl<'tcx
> GenKillAnalysis
<'tcx
> for MaybeLiveLocals
{
47 trans
: &mut impl GenKill
<Self::Idx
>,
48 statement
: &mir
::Statement
<'tcx
>,
51 TransferFunction(trans
).visit_statement(statement
, location
);
56 trans
: &mut impl GenKill
<Self::Idx
>,
57 terminator
: &mir
::Terminator
<'tcx
>,
60 TransferFunction(trans
).visit_terminator(terminator
, location
);
63 fn call_return_effect(
65 trans
: &mut impl GenKill
<Self::Idx
>,
66 _block
: mir
::BasicBlock
,
67 return_places
: CallReturnPlaces
<'_
, 'tcx
>,
69 return_places
.for_each(|place
| {
70 if let Some(local
) = place
.as_local() {
76 fn yield_resume_effect(
78 trans
: &mut impl GenKill
<Self::Idx
>,
79 _resume_block
: mir
::BasicBlock
,
80 resume_place
: mir
::Place
<'tcx
>,
82 YieldResumeEffect(trans
).visit_place(
84 PlaceContext
::MutatingUse(MutatingUseContext
::Yield
),
90 struct TransferFunction
<'a
, T
>(&'a
mut T
);
92 impl<'tcx
, T
> Visitor
<'tcx
> for TransferFunction
<'_
, T
>
96 fn visit_place(&mut self, place
: &mir
::Place
<'tcx
>, context
: PlaceContext
, location
: Location
) {
97 if let PlaceContext
::MutatingUse(MutatingUseContext
::Yield
) = context
{
98 // The resume place is evaluated and assigned to only after generator resumes, so its
99 // effect is handled separately in `yield_resume_effect`.
103 match DefUse
::for_place(*place
, context
) {
104 Some(DefUse
::Def
) => {
105 if let PlaceContext
::MutatingUse(
106 MutatingUseContext
::Call
| MutatingUseContext
::AsmOutput
,
109 // For the associated terminators, this is only a `Def` when the terminator returns
110 // "successfully." As such, we handle this case separately in `call_return_effect`
111 // above. However, if the place looks like `*_5`, this is still unconditionally a use of
114 self.0.kill(place
.local
);
117 Some(DefUse
::Use
) => self.0.gen(place
.local
),
121 self.visit_projection(place
.as_ref(), context
, location
);
124 fn visit_local(&mut self, local
: Local
, context
: PlaceContext
, _
: Location
) {
125 DefUse
::apply(self.0, local
.into(), context
);
129 struct YieldResumeEffect
<'a
, T
>(&'a
mut T
);
131 impl<'tcx
, T
> Visitor
<'tcx
> for YieldResumeEffect
<'_
, T
>
135 fn visit_place(&mut self, place
: &mir
::Place
<'tcx
>, context
: PlaceContext
, location
: Location
) {
136 DefUse
::apply(self.0, *place
, context
);
137 self.visit_projection(place
.as_ref(), context
, location
);
140 fn visit_local(&mut self, local
: Local
, context
: PlaceContext
, _
: Location
) {
141 DefUse
::apply(self.0, local
.into(), context
);
145 #[derive(Eq, PartialEq, Clone)]
152 fn apply
<'tcx
>(trans
: &mut impl GenKill
<Local
>, place
: Place
<'tcx
>, context
: PlaceContext
) {
153 match DefUse
::for_place(place
, context
) {
154 Some(DefUse
::Def
) => trans
.kill(place
.local
),
155 Some(DefUse
::Use
) => trans
.gen(place
.local
),
160 fn for_place
<'tcx
>(place
: Place
<'tcx
>, context
: PlaceContext
) -> Option
<DefUse
> {
162 PlaceContext
::NonUse(_
) => None
,
164 PlaceContext
::MutatingUse(
165 MutatingUseContext
::Call
166 | MutatingUseContext
::Yield
167 | MutatingUseContext
::AsmOutput
168 | MutatingUseContext
::Store
169 | MutatingUseContext
::Deinit
,
171 if place
.is_indirect() {
172 // Treat derefs as a use of the base local. `*p = 4` is not a def of `p` but a
175 } else if place
.projection
.is_empty() {
182 // Setting the discriminant is not a use because it does no reading, but it is also not
183 // a def because it does not overwrite the whole place
184 PlaceContext
::MutatingUse(MutatingUseContext
::SetDiscriminant
) => {
185 place
.is_indirect().then_some(DefUse
::Use
)
188 // All other contexts are uses...
189 PlaceContext
::MutatingUse(
190 MutatingUseContext
::AddressOf
191 | MutatingUseContext
::Borrow
192 | MutatingUseContext
::Drop
193 | MutatingUseContext
::Retag
,
195 | PlaceContext
::NonMutatingUse(
196 NonMutatingUseContext
::AddressOf
197 | NonMutatingUseContext
::Copy
198 | NonMutatingUseContext
::Inspect
199 | NonMutatingUseContext
::Move
200 | NonMutatingUseContext
::ShallowBorrow
201 | NonMutatingUseContext
::SharedBorrow
202 | NonMutatingUseContext
::UniqueBorrow
,
203 ) => Some(DefUse
::Use
),
205 PlaceContext
::MutatingUse(MutatingUseContext
::Projection
)
206 | PlaceContext
::NonMutatingUse(NonMutatingUseContext
::Projection
) => {
207 unreachable
!("A projection could be a def or a use and must be handled separately")
213 /// Like `MaybeLiveLocals`, but does not mark locals as live if they are used in a dead assignment.
215 /// This is basically written for dead store elimination and nothing else.
217 /// All of the caveats of `MaybeLiveLocals` apply.
218 pub struct MaybeTransitiveLiveLocals
<'a
> {
219 always_live
: &'a BitSet
<Local
>,
222 impl<'a
> MaybeTransitiveLiveLocals
<'a
> {
223 /// The `always_alive` set is the set of locals to which all stores should unconditionally be
226 /// This should include at least all locals that are ever borrowed.
227 pub fn new(always_live
: &'a BitSet
<Local
>) -> Self {
228 MaybeTransitiveLiveLocals { always_live }
232 impl<'a
, 'tcx
> AnalysisDomain
<'tcx
> for MaybeTransitiveLiveLocals
<'a
> {
233 type Domain
= ChunkedBitSet
<Local
>;
234 type Direction
= Backward
;
236 const NAME
: &'
static str = "transitive liveness";
238 fn bottom_value(&self, body
: &mir
::Body
<'tcx
>) -> Self::Domain
{
240 ChunkedBitSet
::new_empty(body
.local_decls
.len())
243 fn initialize_start_block(&self, _
: &mir
::Body
<'tcx
>, _
: &mut Self::Domain
) {
244 // No variables are live until we observe a use
248 impl<'a
, 'tcx
> Analysis
<'tcx
> for MaybeTransitiveLiveLocals
<'a
> {
249 fn apply_statement_effect(
251 trans
: &mut Self::Domain
,
252 statement
: &mir
::Statement
<'tcx
>,
255 // Compute the place that we are storing to, if any
256 let destination
= match &statement
.kind
{
257 StatementKind
::Assign(assign
) => {
258 if assign
.1.is_safe_to_remove
() {
264 StatementKind
::SetDiscriminant { place, .. }
| StatementKind
::Deinit(place
) => {
267 StatementKind
::FakeRead(_
)
268 | StatementKind
::StorageLive(_
)
269 | StatementKind
::StorageDead(_
)
270 | StatementKind
::Retag(..)
271 | StatementKind
::AscribeUserType(..)
272 | StatementKind
::Coverage(..)
273 | StatementKind
::Intrinsic(..)
274 | StatementKind
::Nop
=> None
,
276 if let Some(destination
) = destination
{
277 if !destination
.is_indirect()
278 && !trans
.contains(destination
.local
)
279 && !self.always_live
.contains(destination
.local
)
281 // This store is dead
285 TransferFunction(trans
).visit_statement(statement
, location
);
288 fn apply_terminator_effect(
290 trans
: &mut Self::Domain
,
291 terminator
: &mir
::Terminator
<'tcx
>,
294 TransferFunction(trans
).visit_terminator(terminator
, location
);
297 fn apply_call_return_effect(
299 trans
: &mut Self::Domain
,
300 _block
: mir
::BasicBlock
,
301 return_places
: CallReturnPlaces
<'_
, 'tcx
>,
303 return_places
.for_each(|place
| {
304 if let Some(local
) = place
.as_local() {
310 fn apply_yield_resume_effect(
312 trans
: &mut Self::Domain
,
313 _resume_block
: mir
::BasicBlock
,
314 resume_place
: mir
::Place
<'tcx
>,
316 YieldResumeEffect(trans
).visit_place(
318 PlaceContext
::MutatingUse(MutatingUseContext
::Yield
),