rustc_mir_dataflow/impls/
initialized.rs

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

rustc_mir_dataflow/impls/
initialized.rs
