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

rustc_mir_dataflow/impls/
liveness.rs
