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::{self, CallReturnPlaces, Local, Location, Place, StatementKind};
4
5use crate::{Analysis, Backward, GenKill};
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
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`].
13///
14/// ## Field-(in)sensitivity
15///
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
19/// conservative.
20///
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
24pub struct MaybeLiveLocals;
25
26impl<'tcx> Analysis<'tcx> for MaybeLiveLocals {
27    type Domain = DenseBitSet<Local>;
28    type Direction = Backward;
29
30    const NAME: &'static str = "liveness";
31
32    fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
33        // bottom = not live
34        DenseBitSet::new_empty(body.local_decls.len())
35    }
36
37    fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
38        // No variables are live until we observe a use
39    }
40
41    fn apply_primary_statement_effect(
42        &self,
43        state: &mut Self::Domain,
44        statement: &mir::Statement<'tcx>,
45        location: Location,
46    ) {
47        LivenessTransferFunction(state).visit_statement(statement, location);
48    }
49
50    fn apply_primary_terminator_effect(
51        &self,
52        state: &mut Self::Domain,
53        terminator: &mir::Terminator<'tcx>,
54        location: Location,
55    ) {
56        LivenessTransferFunction(state).visit_terminator(terminator, location);
57    }
58
59    fn apply_call_return_effect(
60        &self,
61        state: &mut Self::Domain,
62        _block: mir::BasicBlock,
63        return_places: CallReturnPlaces<'_, 'tcx>,
64    ) {
65        if let CallReturnPlaces::Yield(resume_place) = return_places {
66            YieldResumeEffect(state).visit_place(
67                &resume_place,
68                PlaceContext::MutatingUse(MutatingUseContext::Yield),
69                Location::START,
70            )
71        } else {
72            return_places.for_each(|place| {
73                if let Some(local) = place.as_local() {
74                    state.kill(local);
75                }
76            });
77        }
78    }
79}
80
81pub struct LivenessTransferFunction<'a, I>(pub &'a mut I);
82
83impl<'tcx, I> Visitor<'tcx> for LivenessTransferFunction<'_, I>
84where
85    I: GenKill<Local>,
86{
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
133pub enum DefUse {
134    /// Full write to the local.
135    Def,
136    /// Read of any part of the local.
137    Use,
138    /// Partial write to the local.
139    PartialWrite,
140    /// Non-use, like debuginfo.
141    NonUse,
142}
143
144impl DefUse {
145    fn apply(state: &mut impl GenKill<Local>, place: Place<'_>, context: PlaceContext) {
146        match DefUse::for_place(place, context) {
147            DefUse::Def => state.kill(place.local),
148            DefUse::Use => state.gen_(place.local),
149            DefUse::PartialWrite | DefUse::NonUse => {}
150        }
151    }
152
153    pub fn for_place(place: Place<'_>, context: PlaceContext) -> DefUse {
154        match context {
155            PlaceContext::NonUse(_) => DefUse::NonUse,
156
157            PlaceContext::MutatingUse(
158                MutatingUseContext::Call
159                | MutatingUseContext::Yield
160                | MutatingUseContext::AsmOutput
161                | MutatingUseContext::Store,
162            ) => {
163                // Treat derefs as a use of the base local. `*p = 4` is not a def of `p` but a use.
164                if place.is_indirect() {
165                    DefUse::Use
166                } else if place.projection.is_empty() {
167                    DefUse::Def
168                } else {
169                    DefUse::PartialWrite
170                }
171            }
172
173            // Setting the discriminant is not a use because it does no reading, but it is also not
174            // a def because it does not overwrite the whole place
175            PlaceContext::MutatingUse(MutatingUseContext::SetDiscriminant) => {
176                if place.is_indirect() { DefUse::Use } else { DefUse::PartialWrite }
177            }
178
179            // All other contexts are uses...
180            PlaceContext::MutatingUse(
181                MutatingUseContext::RawBorrow
182                | MutatingUseContext::Borrow
183                | MutatingUseContext::Drop,
184            )
185            | PlaceContext::NonMutatingUse(
186                NonMutatingUseContext::RawBorrow
187                | NonMutatingUseContext::Copy
188                | NonMutatingUseContext::Inspect
189                | NonMutatingUseContext::Move
190                | NonMutatingUseContext::PlaceMention
191                | NonMutatingUseContext::FakeBorrow
192                | NonMutatingUseContext::SharedBorrow,
193            ) => DefUse::Use,
194
195            PlaceContext::MutatingUse(MutatingUseContext::Projection)
196            | PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) => {
197                {
    ::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")
198            }
199        }
200    }
201}
202
203/// Like `MaybeLiveLocals` (and layered on top of `MaybeLiveLocals`), but does not mark locals as
204/// live if they are used in a dead assignment.
205///
206/// This is basically written for dead store elimination and nothing else.
207///
208/// All of the caveats of `MaybeLiveLocals` apply.
209pub struct MaybeTransitiveLiveLocals<'a> {
210    always_live: &'a DenseBitSet<Local>,
211    debuginfo_locals: &'a DenseBitSet<Local>,
212}
213
214impl<'a> MaybeTransitiveLiveLocals<'a> {
215    /// The `always_live` set is the set of locals to which all stores should unconditionally be
216    /// considered live.
217    ///
218    /// This should include at least all locals that are ever borrowed.
219    pub fn new(
220        always_live: &'a DenseBitSet<Local>,
221        debuginfo_locals: &'a DenseBitSet<Local>,
222    ) -> Self {
223        MaybeTransitiveLiveLocals { always_live, debuginfo_locals }
224    }
225
226    pub fn can_be_removed_if_dead<'tcx>(
227        stmt_kind: &StatementKind<'tcx>,
228        always_live: &DenseBitSet<Local>,
229        debuginfo_locals: &DenseBitSet<Local>,
230    ) -> Option<Place<'tcx>> {
231        // Compute the place that we are storing to, if any
232        let destination = match stmt_kind {
233            StatementKind::Assign((place, rvalue)) => (rvalue.is_safe_to_remove()
234                // FIXME: We are not sure how we should represent this debugging information for some statements,
235                // keep it for now.
236                && (!debuginfo_locals.contains(place.local)
237                    || (place.as_local().is_some() && stmt_kind.as_debuginfo().is_some())))
238            .then_some(*place),
239            StatementKind::SetDiscriminant { place, .. } => {
240                (!debuginfo_locals.contains(place.local)).then_some(**place)
241            }
242            StatementKind::FakeRead(_)
243            | StatementKind::StorageLive(_)
244            | StatementKind::StorageDead(_)
245            | StatementKind::AscribeUserType(..)
246            | StatementKind::PlaceMention(..)
247            | StatementKind::Coverage(..)
248            | StatementKind::Intrinsic(..)
249            | StatementKind::ConstEvalCounter
250            | StatementKind::BackwardIncompatibleDropHint { .. }
251            | StatementKind::Nop => None,
252        };
253        if let Some(destination) = destination
254            && !destination.is_indirect()
255            && !always_live.contains(destination.local)
256        {
257            return Some(destination);
258        }
259        None
260    }
261}
262
263impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a> {
264    type Domain = DenseBitSet<Local>;
265    type Direction = Backward;
266
267    const NAME: &'static str = "transitive liveness";
268
269    fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
270        MaybeLiveLocals.bottom_value(body)
271    }
272
273    fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut Self::Domain) {
274        MaybeLiveLocals.initialize_start_block(body, state)
275    }
276
277    fn apply_primary_statement_effect(
278        &self,
279        state: &mut Self::Domain,
280        statement: &mir::Statement<'tcx>,
281        location: Location,
282    ) {
283        // This is the one part of `MaybeTransitiveLiveLocals` that differs from `MaybeLiveLocals`.
284        if let Some(destination) =
285            Self::can_be_removed_if_dead(&statement.kind, self.always_live, self.debuginfo_locals)
286            && !state.contains(destination.local)
287        {
288            // This store is dead
289            return;
290        }
291
292        MaybeLiveLocals.apply_primary_statement_effect(state, statement, location);
293    }
294
295    fn apply_primary_terminator_effect(
296        &self,
297        state: &mut Self::Domain,
298        terminator: &mir::Terminator<'tcx>,
299        location: Location,
300    ) {
301        MaybeLiveLocals.apply_primary_terminator_effect(state, terminator, location)
302    }
303
304    fn apply_call_return_effect(
305        &self,
306        state: &mut Self::Domain,
307        block: mir::BasicBlock,
308        return_places: CallReturnPlaces<'_, 'tcx>,
309    ) {
310        MaybeLiveLocals.apply_call_return_effect(state, block, return_places);
311    }
312}
rustc_mir_dataflow/impls/liveness.rs

rustc_mir_dataflow/impls/
liveness.rs
