rustc_mir_dataflow/impls/
initialized.rs

Help
1use std::assert_matches::assert_matches;
2
3use rustc_abi::VariantIdx;
4use rustc_index::Idx;
5use rustc_index::bit_set::{DenseBitSet, MixedBitSet};
6use rustc_middle::bug;
7use rustc_middle::mir::{self, Body, CallReturnPlaces, Location, TerminatorEdges};
8use rustc_middle::ty::util::Discr;
9use rustc_middle::ty::{self, TyCtxt};
10use tracing::{debug, instrument};
11
12use crate::drop_flag_effects::DropFlagState;
13use crate::framework::SwitchIntTarget;
14use crate::move_paths::{HasMoveData, InitIndex, InitKind, LookupResult, MoveData, MovePathIndex};
15use crate::{
16    Analysis, GenKill, MaybeReachable, drop_flag_effects, drop_flag_effects_for_function_entry,
17    drop_flag_effects_for_location, on_all_children_bits, on_lookup_result_bits,
18};
19
20// Used by both `MaybeInitializedPlaces` and `MaybeUninitializedPlaces`.
21pub struct MaybePlacesSwitchIntData<'tcx> {
22    enum_place: mir::Place<'tcx>,
23    discriminants: Vec<(VariantIdx, Discr<'tcx>)>,
24    index: usize,
25}
26
27impl<'tcx> MaybePlacesSwitchIntData<'tcx> {
28    // The discriminant order in the `SwitchInt` targets should match the order yielded by
29    // `AdtDef::discriminants`. We rely on this to match each discriminant in the targets to its
30    // corresponding variant in linear time.
31    fn next_discr(&mut self, value: u128) -> VariantIdx {
32        // An out-of-bounds abort will occur if the discriminant ordering isn't as described above.
33        loop {
34            let (variant, discr) = self.discriminants[self.index];
35            self.index += 1;
36            if discr.val == value {
37                return variant;
38            }
39        }
40    }
41}
42
43impl<'tcx> MaybePlacesSwitchIntData<'tcx> {
44    fn new(
45        tcx: TyCtxt<'tcx>,
46        body: &Body<'tcx>,
47        block: mir::BasicBlock,
48        discr: &mir::Operand<'tcx>,
49    ) -> Option<Self> {
50        let Some(discr) = discr.place() else { return None };
51
52        // Inspect a `SwitchInt`-terminated basic block to see if the condition of that `SwitchInt`
53        // is an enum discriminant.
54        //
55        // We expect such blocks to have a call to `discriminant` as their last statement like so:
56        // ```text
57        // ...
58        // _42 = discriminant(_1)
59        // SwitchInt(_42, ..)
60        // ```
61        // If the basic block matches this pattern, this function gathers the place corresponding
62        // to the enum (`_1` in the example above) as well as the discriminants.
63        let block_data = &body[block];
64        for statement in block_data.statements.iter().rev() {
65            match statement.kind {
66                mir::StatementKind::Assign(box (lhs, mir::Rvalue::Discriminant(enum_place)))
67                    if lhs == discr =>
68                {
69                    match enum_place.ty(body, tcx).ty.kind() {
70                        ty::Adt(enum_def, _) => {
71                            return Some(MaybePlacesSwitchIntData {
72                                enum_place,
73                                discriminants: enum_def.discriminants(tcx).collect(),
74                                index: 0,
75                            });
76                        }
77
78                        // `Rvalue::Discriminant` is also used to get the active yield point for a
79                        // coroutine, but we do not need edge-specific effects in that case. This
80                        // may change in the future.
81                        ty::Coroutine(..) => break,
82
83                        t => bug!("`discriminant` called on unexpected type {:?}", t),
84                    }
85                }
86                mir::StatementKind::Coverage(_) => continue,
87                _ => break,
88            }
89        }
90        None
91    }
92}
93
94/// `MaybeInitializedPlaces` tracks all places that might be
95/// initialized upon reaching a particular point in the control flow
96/// for a function.
97///
98/// For example, in code like the following, we have corresponding
99/// dataflow information shown in the right-hand comments.
100///
101/// ```rust
102/// struct S;
103/// fn foo(pred: bool) {                        // maybe-init:
104///                                             // {}
105///     let a = S; let mut b = S; let c; let d; // {a, b}
106///
107///     if pred {
108///         drop(a);                            // {   b}
109///         b = S;                              // {   b}
110///
111///     } else {
112///         drop(b);                            // {a}
113///         d = S;                              // {a,       d}
114///
115///     }                                       // {a, b,    d}
116///
117///     c = S;                                  // {a, b, c, d}
118/// }
119/// ```
120///
121/// To determine whether a place is *definitely* initialized at a
122/// particular control-flow point, one can take the set-complement
123/// of the data from `MaybeUninitializedPlaces` at the corresponding
124/// control-flow point.
125///
126/// Similarly, at a given `drop` statement, the set-intersection
127/// between this data and `MaybeUninitializedPlaces` yields the set of
128/// places that would require a dynamic drop-flag at that statement.
129pub struct MaybeInitializedPlaces<'a, 'tcx> {
130    tcx: TyCtxt<'tcx>,
131    body: &'a Body<'tcx>,
132    move_data: &'a MoveData<'tcx>,
133    skip_unreachable_unwind: bool,
134}
135
136impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> {
137    pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, move_data: &'a MoveData<'tcx>) -> Self {
138        MaybeInitializedPlaces { tcx, body, move_data, skip_unreachable_unwind: false }
139    }
140
141    pub fn skipping_unreachable_unwind(mut self) -> Self {
142        self.skip_unreachable_unwind = true;
143        self
144    }
145
146    pub fn is_unwind_dead(
147        &self,
148        place: mir::Place<'tcx>,
149        state: &<Self as Analysis<'tcx>>::Domain,
150    ) -> bool {
151        if let LookupResult::Exact(path) = self.move_data().rev_lookup.find(place.as_ref()) {
152            let mut maybe_live = false;
153            on_all_children_bits(self.move_data(), path, |child| {
154                maybe_live |= state.contains(child);
155            });
156            !maybe_live
157        } else {
158            false
159        }
160    }
161}
162
163impl<'a, 'tcx> HasMoveData<'tcx> for MaybeInitializedPlaces<'a, 'tcx> {
164    fn move_data(&self) -> &MoveData<'tcx> {
165        self.move_data
166    }
167}
168
169/// `MaybeUninitializedPlaces` tracks all places that might be
170/// uninitialized upon reaching a particular point in the control flow
171/// for a function.
172///
173/// For example, in code like the following, we have corresponding
174/// dataflow information shown in the right-hand comments.
175///
176/// ```rust
177/// struct S;
178/// fn foo(pred: bool) {                        // maybe-uninit:
179///                                             // {a, b, c, d}
180///     let a = S; let mut b = S; let c; let d; // {      c, d}
181///
182///     if pred {
183///         drop(a);                            // {a,    c, d}
184///         b = S;                              // {a,    c, d}
185///
186///     } else {
187///         drop(b);                            // {   b, c, d}
188///         d = S;                              // {   b, c   }
189///
190///     }                                       // {a, b, c, d}
191///
192///     c = S;                                  // {a, b,    d}
193/// }
194/// ```
195///
196/// To determine whether a place is *definitely* uninitialized at a
197/// particular control-flow point, one can take the set-complement
198/// of the data from `MaybeInitializedPlaces` at the corresponding
199/// control-flow point.
200///
201/// Similarly, at a given `drop` statement, the set-intersection
202/// between this data and `MaybeInitializedPlaces` yields the set of
203/// places that would require a dynamic drop-flag at that statement.
204pub struct MaybeUninitializedPlaces<'a, 'tcx> {
205    tcx: TyCtxt<'tcx>,
206    body: &'a Body<'tcx>,
207    move_data: &'a MoveData<'tcx>,
208
209    mark_inactive_variants_as_uninit: bool,
210    skip_unreachable_unwind: DenseBitSet<mir::BasicBlock>,
211}
212
213impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> {
214    pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, move_data: &'a MoveData<'tcx>) -> Self {
215        MaybeUninitializedPlaces {
216            tcx,
217            body,
218            move_data,
219            mark_inactive_variants_as_uninit: false,
220            skip_unreachable_unwind: DenseBitSet::new_empty(body.basic_blocks.len()),
221        }
222    }
223
224    /// Causes inactive enum variants to be marked as "maybe uninitialized" after a switch on an
225    /// enum discriminant.
226    ///
227    /// This is correct in a vacuum but is not the default because it causes problems in the borrow
228    /// checker, where this information gets propagated along `FakeEdge`s.
229    pub fn mark_inactive_variants_as_uninit(mut self) -> Self {
230        self.mark_inactive_variants_as_uninit = true;
231        self
232    }
233
234    pub fn skipping_unreachable_unwind(
235        mut self,
236        unreachable_unwind: DenseBitSet<mir::BasicBlock>,
237    ) -> Self {
238        self.skip_unreachable_unwind = unreachable_unwind;
239        self
240    }
241}
242
243impl<'tcx> HasMoveData<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> {
244    fn move_data(&self) -> &MoveData<'tcx> {
245        self.move_data
246    }
247}
248
249/// `EverInitializedPlaces` tracks all places that might have ever been
250/// initialized upon reaching a particular point in the control flow
251/// for a function, without an intervening `StorageDead`.
252///
253/// This dataflow is used to determine if an immutable local variable may
254/// be assigned to.
255///
256/// For example, in code like the following, we have corresponding
257/// dataflow information shown in the right-hand comments.
258///
259/// ```rust
260/// struct S;
261/// fn foo(pred: bool) {                        // ever-init:
262///                                             // {          }
263///     let a = S; let mut b = S; let c; let d; // {a, b      }
264///
265///     if pred {
266///         drop(a);                            // {a, b,     }
267///         b = S;                              // {a, b,     }
268///
269///     } else {
270///         drop(b);                            // {a, b,      }
271///         d = S;                              // {a, b,    d }
272///
273///     }                                       // {a, b,    d }
274///
275///     c = S;                                  // {a, b, c, d }
276/// }
277/// ```
278pub struct EverInitializedPlaces<'a, 'tcx> {
279    body: &'a Body<'tcx>,
280    move_data: &'a MoveData<'tcx>,
281}
282
283impl<'a, 'tcx> EverInitializedPlaces<'a, 'tcx> {
284    pub fn new(body: &'a Body<'tcx>, move_data: &'a MoveData<'tcx>) -> Self {
285        EverInitializedPlaces { body, move_data }
286    }
287}
288
289impl<'tcx> HasMoveData<'tcx> for EverInitializedPlaces<'_, 'tcx> {
290    fn move_data(&self) -> &MoveData<'tcx> {
291        self.move_data
292    }
293}
294
295impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> {
296    fn update_bits(
297        state: &mut <Self as Analysis<'tcx>>::Domain,
298        path: MovePathIndex,
299        dfstate: DropFlagState,
300    ) {
301        match dfstate {
302            DropFlagState::Absent => state.kill(path),
303            DropFlagState::Present => state.gen_(path),
304        }
305    }
306}
307
308impl<'tcx> MaybeUninitializedPlaces<'_, 'tcx> {
309    fn update_bits(
310        state: &mut <Self as Analysis<'tcx>>::Domain,
311        path: MovePathIndex,
312        dfstate: DropFlagState,
313    ) {
314        match dfstate {
315            DropFlagState::Absent => state.gen_(path),
316            DropFlagState::Present => state.kill(path),
317        }
318    }
319}
320
321impl<'tcx> Analysis<'tcx> for MaybeInitializedPlaces<'_, 'tcx> {
322    /// There can be many more `MovePathIndex` than there are locals in a MIR body.
323    /// We use a mixed bitset to avoid paying too high a memory footprint.
324    type Domain = MaybeReachable<MixedBitSet<MovePathIndex>>;
325
326    type SwitchIntData = MaybePlacesSwitchIntData<'tcx>;
327
328    const NAME: &'static str = "maybe_init";
329
330    fn bottom_value(&self, _: &mir::Body<'tcx>) -> Self::Domain {
331        // bottom = uninitialized
332        MaybeReachable::Unreachable
333    }
334
335    fn initialize_start_block(&self, _: &mir::Body<'tcx>, state: &mut Self::Domain) {
336        *state =
337            MaybeReachable::Reachable(MixedBitSet::new_empty(self.move_data().move_paths.len()));
338        drop_flag_effects_for_function_entry(self.body, self.move_data, |path, s| {
339            assert!(s == DropFlagState::Present);
340            state.gen_(path);
341        });
342    }
343
344    fn apply_primary_statement_effect(
345        &mut self,
346        state: &mut Self::Domain,
347        statement: &mir::Statement<'tcx>,
348        location: Location,
349    ) {
350        drop_flag_effects_for_location(self.body, self.move_data, location, |path, s| {
351            Self::update_bits(state, path, s)
352        });
353
354        // Mark all places as "maybe init" if they are mutably borrowed. See #90752.
355        if self.tcx.sess.opts.unstable_opts.precise_enum_drop_elaboration
356            && let Some((_, rvalue)) = statement.kind.as_assign()
357            && let mir::Rvalue::Ref(_, mir::BorrowKind::Mut { .. }, place)
358                // FIXME: Does `&raw const foo` allow mutation? See #90413.
359                | mir::Rvalue::RawPtr(_, place) = rvalue
360            && let LookupResult::Exact(mpi) = self.move_data().rev_lookup.find(place.as_ref())
361        {
362            on_all_children_bits(self.move_data(), mpi, |child| {
363                state.gen_(child);
364            })
365        }
366    }
367
368    fn apply_primary_terminator_effect<'mir>(
369        &mut self,
370        state: &mut Self::Domain,
371        terminator: &'mir mir::Terminator<'tcx>,
372        location: Location,
373    ) -> TerminatorEdges<'mir, 'tcx> {
374        // Note: `edges` must be computed first because `drop_flag_effects_for_location` can change
375        // the result of `is_unwind_dead`.
376        let mut edges = terminator.edges();
377        if self.skip_unreachable_unwind
378            && let mir::TerminatorKind::Drop { target, unwind, place, replace: _ } = terminator.kind
379            && matches!(unwind, mir::UnwindAction::Cleanup(_))
380            && self.is_unwind_dead(place, state)
381        {
382            edges = TerminatorEdges::Single(target);
383        }
384        drop_flag_effects_for_location(self.body, self.move_data, location, |path, s| {
385            Self::update_bits(state, path, s)
386        });
387        edges
388    }
389
390    fn apply_call_return_effect(
391        &mut self,
392        state: &mut Self::Domain,
393        _block: mir::BasicBlock,
394        return_places: CallReturnPlaces<'_, 'tcx>,
395    ) {
396        return_places.for_each(|place| {
397            // when a call returns successfully, that means we need to set
398            // the bits for that dest_place to 1 (initialized).
399            on_lookup_result_bits(
400                self.move_data(),
401                self.move_data().rev_lookup.find(place.as_ref()),
402                |mpi| {
403                    state.gen_(mpi);
404                },
405            );
406        });
407    }
408
409    fn get_switch_int_data(
410        &mut self,
411        block: mir::BasicBlock,
412        discr: &mir::Operand<'tcx>,
413    ) -> Option<Self::SwitchIntData> {
414        if !self.tcx.sess.opts.unstable_opts.precise_enum_drop_elaboration {
415            return None;
416        }
417
418        MaybePlacesSwitchIntData::new(self.tcx, self.body, block, discr)
419    }
420
421    fn apply_switch_int_edge_effect(
422        &mut self,
423        data: &mut Self::SwitchIntData,
424        state: &mut Self::Domain,
425        edge: SwitchIntTarget,
426    ) {
427        if let Some(value) = edge.value {
428            // Kill all move paths that correspond to variants we know to be inactive along this
429            // particular outgoing edge of a `SwitchInt`.
430            drop_flag_effects::on_all_inactive_variants(
431                self.move_data,
432                data.enum_place,
433                data.next_discr(value),
434                |mpi| state.kill(mpi),
435            );
436        }
437    }
438}
439
440/// There can be many more `MovePathIndex` than there are locals in a MIR body.
441/// We use a mixed bitset to avoid paying too high a memory footprint.
442pub type MaybeUninitializedPlacesDomain = MixedBitSet<MovePathIndex>;
443
444impl<'tcx> Analysis<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> {
445    type Domain = MaybeUninitializedPlacesDomain;
446
447    type SwitchIntData = MaybePlacesSwitchIntData<'tcx>;
448
449    const NAME: &'static str = "maybe_uninit";
450
451    fn bottom_value(&self, _: &mir::Body<'tcx>) -> Self::Domain {
452        // bottom = initialized (`initialize_start_block` overwrites this on first entry)
453        MixedBitSet::new_empty(self.move_data().move_paths.len())
454    }
455
456    // sets state bits for Arg places
457    fn initialize_start_block(&self, _: &mir::Body<'tcx>, state: &mut Self::Domain) {
458        // set all bits to 1 (uninit) before gathering counter-evidence
459        state.insert_all();
460
461        drop_flag_effects_for_function_entry(self.body, self.move_data, |path, s| {
462            assert!(s == DropFlagState::Present);
463            state.remove(path);
464        });
465    }
466
467    fn apply_primary_statement_effect(
468        &mut self,
469        state: &mut Self::Domain,
470        _statement: &mir::Statement<'tcx>,
471        location: Location,
472    ) {
473        drop_flag_effects_for_location(self.body, self.move_data, location, |path, s| {
474            Self::update_bits(state, path, s)
475        });
476
477        // Unlike in `MaybeInitializedPlaces` above, we don't need to change the state when a
478        // mutable borrow occurs. Places cannot become uninitialized through a mutable reference.
479    }
480
481    fn apply_primary_terminator_effect<'mir>(
482        &mut self,
483        state: &mut Self::Domain,
484        terminator: &'mir mir::Terminator<'tcx>,
485        location: Location,
486    ) -> TerminatorEdges<'mir, 'tcx> {
487        drop_flag_effects_for_location(self.body, self.move_data, location, |path, s| {
488            Self::update_bits(state, path, s)
489        });
490        if self.skip_unreachable_unwind.contains(location.block) {
491            let mir::TerminatorKind::Drop { target, unwind, .. } = terminator.kind else { bug!() };
492            assert_matches!(unwind, mir::UnwindAction::Cleanup(_));
493            TerminatorEdges::Single(target)
494        } else {
495            terminator.edges()
496        }
497    }
498
499    fn apply_call_return_effect(
500        &mut self,
501        state: &mut Self::Domain,
502        _block: mir::BasicBlock,
503        return_places: CallReturnPlaces<'_, 'tcx>,
504    ) {
505        return_places.for_each(|place| {
506            // when a call returns successfully, that means we need to set
507            // the bits for that dest_place to 0 (initialized).
508            on_lookup_result_bits(
509                self.move_data(),
510                self.move_data().rev_lookup.find(place.as_ref()),
511                |mpi| {
512                    state.kill(mpi);
513                },
514            );
515        });
516    }
517
518    fn get_switch_int_data(
519        &mut self,
520        block: mir::BasicBlock,
521        discr: &mir::Operand<'tcx>,
522    ) -> Option<Self::SwitchIntData> {
523        if !self.tcx.sess.opts.unstable_opts.precise_enum_drop_elaboration {
524            return None;
525        }
526
527        if !self.mark_inactive_variants_as_uninit {
528            return None;
529        }
530
531        MaybePlacesSwitchIntData::new(self.tcx, self.body, block, discr)
532    }
533
534    fn apply_switch_int_edge_effect(
535        &mut self,
536        data: &mut Self::SwitchIntData,
537        state: &mut Self::Domain,
538        edge: SwitchIntTarget,
539    ) {
540        if let Some(value) = edge.value {
541            // Mark all move paths that correspond to variants other than this one as maybe
542            // uninitialized (in reality, they are *definitely* uninitialized).
543            drop_flag_effects::on_all_inactive_variants(
544                self.move_data,
545                data.enum_place,
546                data.next_discr(value),
547                |mpi| state.gen_(mpi),
548            );
549        }
550    }
551}
552
553/// There can be many more `InitIndex` than there are locals in a MIR body.
554/// We use a mixed bitset to avoid paying too high a memory footprint.
555pub type EverInitializedPlacesDomain = MixedBitSet<InitIndex>;
556
557impl<'tcx> Analysis<'tcx> for EverInitializedPlaces<'_, 'tcx> {
558    type Domain = EverInitializedPlacesDomain;
559
560    const NAME: &'static str = "ever_init";
561
562    fn bottom_value(&self, _: &mir::Body<'tcx>) -> Self::Domain {
563        // bottom = no initialized variables by default
564        MixedBitSet::new_empty(self.move_data().inits.len())
565    }
566
567    fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut Self::Domain) {
568        for arg_init in 0..body.arg_count {
569            state.insert(InitIndex::new(arg_init));
570        }
571    }
572
573    #[instrument(skip(self, state), level = "debug")]
574    fn apply_primary_statement_effect(
575        &mut self,
576        state: &mut Self::Domain,
577        stmt: &mir::Statement<'tcx>,
578        location: Location,
579    ) {
580        let move_data = self.move_data();
581        let init_path_map = &move_data.init_path_map;
582        let init_loc_map = &move_data.init_loc_map;
583        let rev_lookup = &move_data.rev_lookup;
584
585        debug!("initializes move_indexes {:?}", init_loc_map[location]);
586        state.gen_all(init_loc_map[location].iter().copied());
587
588        if let mir::StatementKind::StorageDead(local) = stmt.kind {
589            // End inits for StorageDead, so that an immutable variable can
590            // be reinitialized on the next iteration of the loop.
591            if let Some(move_path_index) = rev_lookup.find_local(local) {
592                debug!(
593                    "clears the ever initialized status of {:?}",
594                    init_path_map[move_path_index]
595                );
596                state.kill_all(init_path_map[move_path_index].iter().copied());
597            }
598        }
599    }
600
601    #[instrument(skip(self, state, terminator), level = "debug")]
602    fn apply_primary_terminator_effect<'mir>(
603        &mut self,
604        state: &mut Self::Domain,
605        terminator: &'mir mir::Terminator<'tcx>,
606        location: Location,
607    ) -> TerminatorEdges<'mir, 'tcx> {
608        let (body, move_data) = (self.body, self.move_data());
609        let term = body[location.block].terminator();
610        let init_loc_map = &move_data.init_loc_map;
611        debug!(?term);
612        debug!("initializes move_indexes {:?}", init_loc_map[location]);
613        state.gen_all(
614            init_loc_map[location]
615                .iter()
616                .filter(|init_index| {
617                    move_data.inits[**init_index].kind != InitKind::NonPanicPathOnly
618                })
619                .copied(),
620        );
621        terminator.edges()
622    }
623
624    fn apply_call_return_effect(
625        &mut self,
626        state: &mut Self::Domain,
627        block: mir::BasicBlock,
628        _return_places: CallReturnPlaces<'_, 'tcx>,
629    ) {
630        let move_data = self.move_data();
631        let init_loc_map = &move_data.init_loc_map;
632
633        let call_loc = self.body.terminator_loc(block);
634        for init_index in &init_loc_map[call_loc] {
635            state.gen_(*init_index);
636        }
637    }
638}
rustc_mir_dataflow/impls/initialized.rs

rustc_mir_dataflow/impls/
initialized.rs
