rustc_mir_dataflow/impls/
storage_liveness.rs

1use std::borrow::Cow;
2
3use rustc_index::bit_set::DenseBitSet;
4use rustc_middle::mir::visit::{NonMutatingUseContext, PlaceContext, Visitor};
5use rustc_middle::mir::*;
6
7use super::MaybeBorrowedLocals;
8use crate::{Analysis, GenKill, ResultsCursor};
9
10/// The set of locals in a MIR body that do not have `StorageLive`/`StorageDead` annotations.
11///
12/// These locals have fixed storage for the duration of the body.
13pub fn always_storage_live_locals(body: &Body<'_>) -> DenseBitSet<Local> {
14    let mut always_live_locals = DenseBitSet::new_filled(body.local_decls.len());
15
16    for block in &*body.basic_blocks {
17        for statement in &block.statements {
18            if let StatementKind::StorageLive(l) | StatementKind::StorageDead(l) = statement.kind {
19                always_live_locals.remove(l);
20            }
21        }
22    }
23
24    always_live_locals
25}
26
27pub struct MaybeStorageLive<'a> {
28    always_live_locals: Cow<'a, DenseBitSet<Local>>,
29}
30
31impl<'a> MaybeStorageLive<'a> {
32    pub fn new(always_live_locals: Cow<'a, DenseBitSet<Local>>) -> Self {
33        MaybeStorageLive { always_live_locals }
34    }
35}
36
37impl<'a, 'tcx> Analysis<'tcx> for MaybeStorageLive<'a> {
38    type Domain = DenseBitSet<Local>;
39
40    const NAME: &'static str = "maybe_storage_live";
41
42    fn bottom_value(&self, body: &Body<'tcx>) -> Self::Domain {
43        // bottom = dead
44        DenseBitSet::new_empty(body.local_decls.len())
45    }
46
47    fn initialize_start_block(&self, body: &Body<'tcx>, state: &mut Self::Domain) {
48        state.union(&*self.always_live_locals);
49
50        for arg in body.args_iter() {
51            state.insert(arg);
52        }
53    }
54
55    fn apply_primary_statement_effect(
56        &mut self,
57        state: &mut Self::Domain,
58        stmt: &Statement<'tcx>,
59        _: Location,
60    ) {
61        match stmt.kind {
62            StatementKind::StorageLive(l) => state.gen_(l),
63            StatementKind::StorageDead(l) => state.kill(l),
64            _ => (),
65        }
66    }
67}
68
69pub struct MaybeStorageDead<'a> {
70    always_live_locals: Cow<'a, DenseBitSet<Local>>,
71}
72
73impl<'a> MaybeStorageDead<'a> {
74    pub fn new(always_live_locals: Cow<'a, DenseBitSet<Local>>) -> Self {
75        MaybeStorageDead { always_live_locals }
76    }
77}
78
79impl<'a, 'tcx> Analysis<'tcx> for MaybeStorageDead<'a> {
80    type Domain = DenseBitSet<Local>;
81
82    const NAME: &'static str = "maybe_storage_dead";
83
84    fn bottom_value(&self, body: &Body<'tcx>) -> Self::Domain {
85        // bottom = live
86        DenseBitSet::new_empty(body.local_decls.len())
87    }
88
89    fn initialize_start_block(&self, body: &Body<'tcx>, state: &mut Self::Domain) {
90        assert_eq!(body.local_decls.len(), self.always_live_locals.domain_size());
91        // Do not iterate on return place and args, as they are trivially always live.
92        for local in body.vars_and_temps_iter() {
93            if !self.always_live_locals.contains(local) {
94                state.insert(local);
95            }
96        }
97    }
98
99    fn apply_primary_statement_effect(
100        &mut self,
101        state: &mut Self::Domain,
102        stmt: &Statement<'tcx>,
103        _: Location,
104    ) {
105        match stmt.kind {
106            StatementKind::StorageLive(l) => state.kill(l),
107            StatementKind::StorageDead(l) => state.gen_(l),
108            _ => (),
109        }
110    }
111}
112
113type BorrowedLocalsResults<'mir, 'tcx> = ResultsCursor<'mir, 'tcx, MaybeBorrowedLocals>;
114
115/// Dataflow analysis that determines whether each local requires storage at a
116/// given location; i.e. whether its storage can go away without being observed.
117pub struct MaybeRequiresStorage<'mir, 'tcx> {
118    borrowed_locals: BorrowedLocalsResults<'mir, 'tcx>,
119}
120
121impl<'mir, 'tcx> MaybeRequiresStorage<'mir, 'tcx> {
122    pub fn new(borrowed_locals: BorrowedLocalsResults<'mir, 'tcx>) -> Self {
123        MaybeRequiresStorage { borrowed_locals }
124    }
125}
126
127impl<'tcx> Analysis<'tcx> for MaybeRequiresStorage<'_, 'tcx> {
128    type Domain = DenseBitSet<Local>;
129
130    const NAME: &'static str = "requires_storage";
131
132    fn bottom_value(&self, body: &Body<'tcx>) -> Self::Domain {
133        // bottom = dead
134        DenseBitSet::new_empty(body.local_decls.len())
135    }
136
137    fn initialize_start_block(&self, body: &Body<'tcx>, state: &mut Self::Domain) {
138        // The resume argument is live on function entry (we don't care about
139        // the `self` argument)
140        for arg in body.args_iter().skip(1) {
141            state.insert(arg);
142        }
143    }
144
145    fn apply_early_statement_effect(
146        &mut self,
147        state: &mut Self::Domain,
148        stmt: &Statement<'tcx>,
149        loc: Location,
150    ) {
151        // If a place is borrowed in a statement, it needs storage for that statement.
152        MaybeBorrowedLocals::transfer_function(state).visit_statement(stmt, loc);
153
154        match &stmt.kind {
155            StatementKind::StorageDead(l) => state.kill(*l),
156
157            // If a place is assigned to in a statement, it needs storage for that statement.
158            StatementKind::Assign(box (place, _))
159            | StatementKind::SetDiscriminant { box place, .. }
160            | StatementKind::Deinit(box place) => {
161                state.gen_(place.local);
162            }
163
164            // Nothing to do for these. Match exhaustively so this fails to compile when new
165            // variants are added.
166            StatementKind::AscribeUserType(..)
167            | StatementKind::PlaceMention(..)
168            | StatementKind::Coverage(..)
169            | StatementKind::FakeRead(..)
170            | StatementKind::ConstEvalCounter
171            | StatementKind::Nop
172            | StatementKind::Retag(..)
173            | StatementKind::Intrinsic(..)
174            | StatementKind::BackwardIncompatibleDropHint { .. }
175            | StatementKind::StorageLive(..) => {}
176        }
177    }
178
179    fn apply_primary_statement_effect(
180        &mut self,
181        state: &mut Self::Domain,
182        _: &Statement<'tcx>,
183        loc: Location,
184    ) {
185        // If we move from a place then it only stops needing storage *after*
186        // that statement.
187        self.check_for_move(state, loc);
188    }
189
190    fn apply_early_terminator_effect(
191        &mut self,
192        state: &mut Self::Domain,
193        terminator: &Terminator<'tcx>,
194        loc: Location,
195    ) {
196        // If a place is borrowed in a terminator, it needs storage for that terminator.
197        MaybeBorrowedLocals::transfer_function(state).visit_terminator(terminator, loc);
198
199        match &terminator.kind {
200            TerminatorKind::Call { destination, .. } => {
201                state.gen_(destination.local);
202            }
203
204            // Note that we do *not* gen the `resume_arg` of `Yield` terminators. The reason for
205            // that is that a `yield` will return from the function, and `resume_arg` is written
206            // only when the coroutine is later resumed. Unlike `Call`, this doesn't require the
207            // place to have storage *before* the yield, only after.
208            TerminatorKind::Yield { .. } => {}
209
210            TerminatorKind::InlineAsm { operands, .. } => {
211                for op in operands {
212                    match op {
213                        InlineAsmOperand::Out { place, .. }
214                        | InlineAsmOperand::InOut { out_place: place, .. } => {
215                            if let Some(place) = place {
216                                state.gen_(place.local);
217                            }
218                        }
219                        InlineAsmOperand::In { .. }
220                        | InlineAsmOperand::Const { .. }
221                        | InlineAsmOperand::SymFn { .. }
222                        | InlineAsmOperand::SymStatic { .. }
223                        | InlineAsmOperand::Label { .. } => {}
224                    }
225                }
226            }
227
228            // Nothing to do for these. Match exhaustively so this fails to compile when new
229            // variants are added.
230            TerminatorKind::UnwindTerminate(_)
231            | TerminatorKind::Assert { .. }
232            | TerminatorKind::Drop { .. }
233            | TerminatorKind::FalseEdge { .. }
234            | TerminatorKind::FalseUnwind { .. }
235            | TerminatorKind::CoroutineDrop
236            | TerminatorKind::Goto { .. }
237            | TerminatorKind::UnwindResume
238            | TerminatorKind::Return
239            | TerminatorKind::TailCall { .. }
240            | TerminatorKind::SwitchInt { .. }
241            | TerminatorKind::Unreachable => {}
242        }
243    }
244
245    fn apply_primary_terminator_effect<'t>(
246        &mut self,
247        state: &mut Self::Domain,
248        terminator: &'t Terminator<'tcx>,
249        loc: Location,
250    ) -> TerminatorEdges<'t, 'tcx> {
251        match terminator.kind {
252            // For call terminators the destination requires storage for the call
253            // and after the call returns successfully, but not after a panic.
254            // Since `propagate_call_unwind` doesn't exist, we have to kill the
255            // destination here, and then gen it again in `call_return_effect`.
256            TerminatorKind::Call { destination, .. } => {
257                state.kill(destination.local);
258            }
259
260            // The same applies to InlineAsm outputs.
261            TerminatorKind::InlineAsm { ref operands, .. } => {
262                CallReturnPlaces::InlineAsm(operands).for_each(|place| state.kill(place.local));
263            }
264
265            // Nothing to do for these. Match exhaustively so this fails to compile when new
266            // variants are added.
267            TerminatorKind::Yield { .. }
268            | TerminatorKind::UnwindTerminate(_)
269            | TerminatorKind::Assert { .. }
270            | TerminatorKind::Drop { .. }
271            | TerminatorKind::FalseEdge { .. }
272            | TerminatorKind::FalseUnwind { .. }
273            | TerminatorKind::CoroutineDrop
274            | TerminatorKind::Goto { .. }
275            | TerminatorKind::UnwindResume
276            | TerminatorKind::Return
277            | TerminatorKind::TailCall { .. }
278            | TerminatorKind::SwitchInt { .. }
279            | TerminatorKind::Unreachable => {}
280        }
281
282        self.check_for_move(state, loc);
283        terminator.edges()
284    }
285
286    fn apply_call_return_effect(
287        &mut self,
288        state: &mut Self::Domain,
289        _block: BasicBlock,
290        return_places: CallReturnPlaces<'_, 'tcx>,
291    ) {
292        return_places.for_each(|place| state.gen_(place.local));
293    }
294}
295
296impl<'tcx> MaybeRequiresStorage<'_, 'tcx> {
297    /// Kill locals that are fully moved and have not been borrowed.
298    fn check_for_move(&mut self, state: &mut <Self as Analysis<'tcx>>::Domain, loc: Location) {
299        let body = self.borrowed_locals.body();
300        let mut visitor = MoveVisitor { state, borrowed_locals: &mut self.borrowed_locals };
301        visitor.visit_location(body, loc);
302    }
303}
304
305struct MoveVisitor<'a, 'mir, 'tcx> {
306    borrowed_locals: &'a mut BorrowedLocalsResults<'mir, 'tcx>,
307    state: &'a mut DenseBitSet<Local>,
308}
309
310impl<'tcx> Visitor<'tcx> for MoveVisitor<'_, '_, 'tcx> {
311    fn visit_local(&mut self, local: Local, context: PlaceContext, loc: Location) {
312        if PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) == context {
313            self.borrowed_locals.seek_before_primary_effect(loc);
314            if !self.borrowed_locals.get().contains(local) {
315                self.state.kill(local);
316            }
317        }
318    }
319}