rustc_mir_dataflow/impls/
liveness.rs

1use rustc_index::bit_set::DenseBitSet;
2use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
3use rustc_middle::mir::{
4    self, CallReturnPlaces, Local, Location, Place, StatementKind, TerminatorEdges,
5};
6
7use crate::{Analysis, Backward, GenKill};
8
9/// A [live-variable dataflow analysis][liveness].
10///
11/// This analysis considers references as being used only at the point of the
12/// borrow. In other words, this analysis does not track uses because of references that already
13/// exist. See [this `mir-dataflow` test][flow-test] for an example. You almost never want to use
14/// this analysis without also looking at the results of [`MaybeBorrowedLocals`].
15///
16/// ## Field-(in)sensitivity
17///
18/// As the name suggests, this analysis is field insensitive. If a projection of a variable `x` is
19/// assigned to (e.g. `x.0 = 42`), it does not "define" `x` as far as liveness is concerned. In fact,
20/// such an assignment is currently marked as a "use" of `x` in an attempt to be maximally
21/// conservative.
22///
23/// [`MaybeBorrowedLocals`]: super::MaybeBorrowedLocals
24/// [flow-test]: https://github.com/rust-lang/rust/blob/a08c47310c7d49cbdc5d7afb38408ba519967ecd/src/test/ui/mir-dataflow/liveness-ptr.rs
25/// [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis
26pub struct MaybeLiveLocals;
27
28impl MaybeLiveLocals {
29    pub fn transfer_function<I>(state: &mut I) -> TransferFunction<'_, I> {
30        TransferFunction(state)
31    }
32}
33
34impl<'tcx> Analysis<'tcx> for MaybeLiveLocals {
35    type Domain = DenseBitSet<Local>;
36    type Direction = Backward;
37
38    const NAME: &'static str = "liveness";
39
40    fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
41        // bottom = not live
42        DenseBitSet::new_empty(body.local_decls.len())
43    }
44
45    fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
46        // No variables are live until we observe a use
47    }
48
49    fn apply_primary_statement_effect(
50        &self,
51        state: &mut Self::Domain,
52        statement: &mir::Statement<'tcx>,
53        location: Location,
54    ) {
55        TransferFunction(state).visit_statement(statement, location);
56    }
57
58    fn apply_primary_terminator_effect<'mir>(
59        &self,
60        state: &mut Self::Domain,
61        terminator: &'mir mir::Terminator<'tcx>,
62        location: Location,
63    ) -> TerminatorEdges<'mir, 'tcx> {
64        TransferFunction(state).visit_terminator(terminator, location);
65        terminator.edges()
66    }
67
68    fn apply_call_return_effect(
69        &self,
70        state: &mut Self::Domain,
71        _block: mir::BasicBlock,
72        return_places: CallReturnPlaces<'_, 'tcx>,
73    ) {
74        if let CallReturnPlaces::Yield(resume_place) = return_places {
75            YieldResumeEffect(state).visit_place(
76                &resume_place,
77                PlaceContext::MutatingUse(MutatingUseContext::Yield),
78                Location::START,
79            )
80        } else {
81            return_places.for_each(|place| {
82                if let Some(local) = place.as_local() {
83                    state.kill(local);
84                }
85            });
86        }
87    }
88}
89
90pub struct TransferFunction<'a, I>(pub &'a mut I);
91
92impl<'tcx, I> Visitor<'tcx> for TransferFunction<'_, I>
93where
94    I: GenKill<Local>,
95{
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 coroutine resumes, so its
99            // effect is handled separately in `call_resume_effect`.
100            return;
101        }
102
103        match DefUse::for_place(*place, context) {
104            DefUse::Def => {
105                if let PlaceContext::MutatingUse(
106                    MutatingUseContext::Call | MutatingUseContext::AsmOutput,
107                ) = context
108                {
109                    // For the associated terminators, this is only a `Def` when the terminator
110                    // returns "successfully." As such, we handle this case separately in
111                    // `call_return_effect` above. However, if the place looks like `*_5`, this is
112                    // still unconditionally a use of `_5`.
113                } else {
114                    self.0.kill(place.local);
115                }
116            }
117            DefUse::Use => self.0.gen_(place.local),
118            DefUse::PartialWrite | DefUse::NonUse => {}
119        }
120
121        self.visit_projection(place.as_ref(), context, location);
122    }
123
124    fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) {
125        DefUse::apply(self.0, local.into(), context);
126    }
127}
128
129struct YieldResumeEffect<'a>(&'a mut DenseBitSet<Local>);
130
131impl<'tcx> Visitor<'tcx> for YieldResumeEffect<'_> {
132    fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
133        DefUse::apply(self.0, *place, context);
134        self.visit_projection(place.as_ref(), context, location);
135    }
136
137    fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) {
138        DefUse::apply(self.0, local.into(), context);
139    }
140}
141
142#[derive(#[automatically_derived]
impl ::core::cmp::Eq for DefUse {
    #[inline]
    #[doc(hidden)]
    #[coverage(off)]
    fn assert_fields_are_eq(&self) {}
}Eq, #[automatically_derived]
impl ::core::cmp::PartialEq for DefUse {
    #[inline]
    fn eq(&self, other: &DefUse) -> bool {
        let __self_discr = ::core::intrinsics::discriminant_value(self);
        let __arg1_discr = ::core::intrinsics::discriminant_value(other);
        __self_discr == __arg1_discr
    }
}PartialEq, #[automatically_derived]
impl ::core::clone::Clone for DefUse {
    #[inline]
    fn clone(&self) -> DefUse {
        match self {
            DefUse::Def => DefUse::Def,
            DefUse::Use => DefUse::Use,
            DefUse::PartialWrite => DefUse::PartialWrite,
            DefUse::NonUse => DefUse::NonUse,
        }
    }
}Clone)]
143pub enum DefUse {
144    /// Full write to the local.
145    Def,
146    /// Read of any part of the local.
147    Use,
148    /// Partial write to the local.
149    PartialWrite,
150    /// Non-use, like debuginfo.
151    NonUse,
152}
153
154impl DefUse {
155    fn apply(state: &mut impl GenKill<Local>, place: Place<'_>, context: PlaceContext) {
156        match DefUse::for_place(place, context) {
157            DefUse::Def => state.kill(place.local),
158            DefUse::Use => state.gen_(place.local),
159            DefUse::PartialWrite | DefUse::NonUse => {}
160        }
161    }
162
163    pub fn for_place(place: Place<'_>, context: PlaceContext) -> DefUse {
164        match context {
165            PlaceContext::NonUse(_) => DefUse::NonUse,
166
167            PlaceContext::MutatingUse(
168                MutatingUseContext::Call
169                | MutatingUseContext::Yield
170                | MutatingUseContext::AsmOutput
171                | MutatingUseContext::Store,
172            ) => {
173                // Treat derefs as a use of the base local. `*p = 4` is not a def of `p` but a use.
174                if place.is_indirect() {
175                    DefUse::Use
176                } else if place.projection.is_empty() {
177                    DefUse::Def
178                } else {
179                    DefUse::PartialWrite
180                }
181            }
182
183            // Setting the discriminant is not a use because it does no reading, but it is also not
184            // a def because it does not overwrite the whole place
185            PlaceContext::MutatingUse(MutatingUseContext::SetDiscriminant) => {
186                if place.is_indirect() { DefUse::Use } else { DefUse::PartialWrite }
187            }
188
189            // All other contexts are uses...
190            PlaceContext::MutatingUse(
191                MutatingUseContext::RawBorrow
192                | MutatingUseContext::Borrow
193                | MutatingUseContext::Drop
194                | MutatingUseContext::Retag,
195            )
196            | PlaceContext::NonMutatingUse(
197                NonMutatingUseContext::RawBorrow
198                | NonMutatingUseContext::Copy
199                | NonMutatingUseContext::Inspect
200                | NonMutatingUseContext::Move
201                | NonMutatingUseContext::PlaceMention
202                | NonMutatingUseContext::FakeBorrow
203                | NonMutatingUseContext::SharedBorrow,
204            ) => DefUse::Use,
205
206            PlaceContext::MutatingUse(MutatingUseContext::Projection)
207            | PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) => {
208                {
    ::core::panicking::panic_fmt(format_args!("internal error: entered unreachable code: {0}",
            format_args!("A projection could be a def or a use and must be handled separately")));
}unreachable!("A projection could be a def or a use and must be handled separately")
209            }
210        }
211    }
212}
213
214/// Like `MaybeLiveLocals`, but does not mark locals as live if they are used in a dead assignment.
215///
216/// This is basically written for dead store elimination and nothing else.
217///
218/// All of the caveats of `MaybeLiveLocals` apply.
219pub struct MaybeTransitiveLiveLocals<'a> {
220    always_live: &'a DenseBitSet<Local>,
221    debuginfo_locals: &'a DenseBitSet<Local>,
222}
223
224impl<'a> MaybeTransitiveLiveLocals<'a> {
225    /// The `always_alive` set is the set of locals to which all stores should unconditionally be
226    /// considered live.
227    ///
228    /// This should include at least all locals that are ever borrowed.
229    pub fn new(
230        always_live: &'a DenseBitSet<Local>,
231        debuginfo_locals: &'a DenseBitSet<Local>,
232    ) -> Self {
233        MaybeTransitiveLiveLocals { always_live, debuginfo_locals }
234    }
235
236    pub fn can_be_removed_if_dead<'tcx>(
237        stmt_kind: &StatementKind<'tcx>,
238        always_live: &DenseBitSet<Local>,
239        debuginfo_locals: &'a DenseBitSet<Local>,
240    ) -> Option<Place<'tcx>> {
241        // Compute the place that we are storing to, if any
242        let destination = match stmt_kind {
243            StatementKind::Assign((place, rvalue)) => (rvalue.is_safe_to_remove()
244                // FIXME: We are not sure how we should represent this debugging information for some statements,
245                // keep it for now.
246                && (!debuginfo_locals.contains(place.local)
247                    || (place.as_local().is_some() && stmt_kind.as_debuginfo().is_some())))
248            .then_some(*place),
249            StatementKind::SetDiscriminant { place, .. } => {
250                (!debuginfo_locals.contains(place.local)).then_some(**place)
251            }
252            StatementKind::FakeRead(_)
253            | StatementKind::StorageLive(_)
254            | StatementKind::StorageDead(_)
255            | StatementKind::AscribeUserType(..)
256            | StatementKind::PlaceMention(..)
257            | StatementKind::Coverage(..)
258            | StatementKind::Intrinsic(..)
259            | StatementKind::ConstEvalCounter
260            | StatementKind::BackwardIncompatibleDropHint { .. }
261            | StatementKind::Nop => None,
262        };
263        if let Some(destination) = destination
264            && !destination.is_indirect()
265            && !always_live.contains(destination.local)
266        {
267            return Some(destination);
268        }
269        None
270    }
271}
272
273impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a> {
274    type Domain = DenseBitSet<Local>;
275    type Direction = Backward;
276
277    const NAME: &'static str = "transitive liveness";
278
279    fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
280        // bottom = not live
281        DenseBitSet::new_empty(body.local_decls.len())
282    }
283
284    fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
285        // No variables are live until we observe a use
286    }
287
288    fn apply_primary_statement_effect(
289        &self,
290        state: &mut Self::Domain,
291        statement: &mir::Statement<'tcx>,
292        location: Location,
293    ) {
294        if let Some(destination) =
295            Self::can_be_removed_if_dead(&statement.kind, &self.always_live, &self.debuginfo_locals)
296            && !state.contains(destination.local)
297        {
298            // This store is dead
299            return;
300        }
301        TransferFunction(state).visit_statement(statement, location);
302    }
303
304    fn apply_primary_terminator_effect<'mir>(
305        &self,
306        state: &mut Self::Domain,
307        terminator: &'mir mir::Terminator<'tcx>,
308        location: Location,
309    ) -> TerminatorEdges<'mir, 'tcx> {
310        TransferFunction(state).visit_terminator(terminator, location);
311        terminator.edges()
312    }
313
314    fn apply_call_return_effect(
315        &self,
316        state: &mut Self::Domain,
317        _block: mir::BasicBlock,
318        return_places: CallReturnPlaces<'_, 'tcx>,
319    ) {
320        if let CallReturnPlaces::Yield(resume_place) = return_places {
321            YieldResumeEffect(state).visit_place(
322                &resume_place,
323                PlaceContext::MutatingUse(MutatingUseContext::Yield),
324                Location::START,
325            )
326        } else {
327            return_places.for_each(|place| {
328                if let Some(local) = place.as_local() {
329                    state.remove(local);
330                }
331            });
332        }
333    }
334}
rustc_mir_dataflow/impls/liveness.rs

rustc_mir_dataflow/impls/
liveness.rs
