1 //! Dataflow analyses are built upon some interpretation of the
2 //! bitvectors attached to each basic block, represented via a
3 //! zero-sized structure.
5 use rustc_index::bit_set::BitSet;
6 use rustc_index::vec::Idx;
7 use rustc_middle::mir::{self, Body, Location};
8 use rustc_middle::ty::{self, TyCtxt};
9 use rustc_target::abi::VariantIdx;
11 use super::MoveDataParamEnv;
13 use crate::util::elaborate_drops::DropFlagState;
15 use super::move_paths::{HasMoveData, InitIndex, InitKind, LookupResult, MoveData, MovePathIndex};
16 use super::{AnalysisDomain, BottomValue, GenKill, GenKillAnalysis};
18 use super::drop_flag_effects_for_function_entry;
19 use super::drop_flag_effects_for_location;
20 use super::on_lookup_result_bits;
21 use crate::dataflow::drop_flag_effects;
24 pub(super) mod borrows;
29 pub use self::borrowed_locals::{MaybeBorrowedLocals, MaybeMutBorrowedLocals};
30 pub use self::borrows::Borrows;
31 pub use self::init_locals::MaybeInitializedLocals;
32 pub use self::liveness::MaybeLiveLocals;
33 pub use self::storage_liveness::MaybeStorageLive;
35 /// `MaybeInitializedPlaces` tracks all places that might be
36 /// initialized upon reaching a particular point in the control flow
39 /// For example, in code like the following, we have corresponding
40 /// dataflow information shown in the right-hand comments.
44 /// fn foo(pred: bool) { // maybe-init:
46 /// let a = S; let b = S; let c; let d; // {a, b}
58 /// c = S; // {a, b, c, d}
62 /// To determine whether a place *must* be initialized at a
63 /// particular control-flow point, one can take the set-difference
64 /// between this data and the data from `MaybeUninitializedPlaces` at the
65 /// corresponding control-flow point.
67 /// Similarly, at a given `drop` statement, the set-intersection
68 /// between this data and `MaybeUninitializedPlaces` yields the set of
69 /// places that would require a dynamic drop-flag at that statement.
70 pub struct MaybeInitializedPlaces<'a, 'tcx> {
73 mdpe: &'a MoveDataParamEnv<'tcx>,
76 impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> {
77 pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
78 MaybeInitializedPlaces { tcx, body, mdpe }
82 impl<'a, 'tcx> HasMoveData<'tcx> for MaybeInitializedPlaces<'a, 'tcx> {
83 fn move_data(&self) -> &MoveData<'tcx> {
88 /// `MaybeUninitializedPlaces` tracks all places that might be
89 /// uninitialized upon reaching a particular point in the control flow
92 /// For example, in code like the following, we have corresponding
93 /// dataflow information shown in the right-hand comments.
97 /// fn foo(pred: bool) { // maybe-uninit:
99 /// let a = S; let b = S; let c; let d; // { c, d}
102 /// drop(a); // {a, c, d}
103 /// b = S; // {a, c, d}
106 /// drop(b); // { b, c, d}
107 /// d = S; // { b, c }
109 /// } // {a, b, c, d}
111 /// c = S; // {a, b, d}
115 /// To determine whether a place *must* be uninitialized at a
116 /// particular control-flow point, one can take the set-difference
117 /// between this data and the data from `MaybeInitializedPlaces` at the
118 /// corresponding control-flow point.
120 /// Similarly, at a given `drop` statement, the set-intersection
121 /// between this data and `MaybeInitializedPlaces` yields the set of
122 /// places that would require a dynamic drop-flag at that statement.
123 pub struct MaybeUninitializedPlaces<'a, 'tcx> {
125 body: &'a Body<'tcx>,
126 mdpe: &'a MoveDataParamEnv<'tcx>,
129 impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> {
130 pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
131 MaybeUninitializedPlaces { tcx, body, mdpe }
135 impl<'a, 'tcx> HasMoveData<'tcx> for MaybeUninitializedPlaces<'a, 'tcx> {
136 fn move_data(&self) -> &MoveData<'tcx> {
141 /// `DefinitelyInitializedPlaces` tracks all places that are definitely
142 /// initialized upon reaching a particular point in the control flow
145 /// For example, in code like the following, we have corresponding
146 /// dataflow information shown in the right-hand comments.
150 /// fn foo(pred: bool) { // definite-init:
152 /// let a = S; let b = S; let c; let d; // {a, b }
155 /// drop(a); // { b, }
159 /// drop(b); // {a, }
168 /// To determine whether a place *may* be uninitialized at a
169 /// particular control-flow point, one can take the set-complement
172 /// Similarly, at a given `drop` statement, the set-difference between
173 /// this data and `MaybeInitializedPlaces` yields the set of places
174 /// that would require a dynamic drop-flag at that statement.
175 pub struct DefinitelyInitializedPlaces<'a, 'tcx> {
177 body: &'a Body<'tcx>,
178 mdpe: &'a MoveDataParamEnv<'tcx>,
181 impl<'a, 'tcx> DefinitelyInitializedPlaces<'a, 'tcx> {
182 pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
183 DefinitelyInitializedPlaces { tcx, body, mdpe }
187 impl<'a, 'tcx> HasMoveData<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> {
188 fn move_data(&self) -> &MoveData<'tcx> {
193 /// `EverInitializedPlaces` tracks all places that might have ever been
194 /// initialized upon reaching a particular point in the control flow
195 /// for a function, without an intervening `Storage Dead`.
197 /// This dataflow is used to determine if an immutable local variable may
200 /// For example, in code like the following, we have corresponding
201 /// dataflow information shown in the right-hand comments.
205 /// fn foo(pred: bool) { // ever-init:
207 /// let a = S; let b = S; let c; let d; // {a, b }
210 /// drop(a); // {a, b, }
211 /// b = S; // {a, b, }
214 /// drop(b); // {a, b, }
215 /// d = S; // {a, b, d }
219 /// c = S; // {a, b, c, d }
222 pub struct EverInitializedPlaces<'a, 'tcx> {
225 body: &'a Body<'tcx>,
226 mdpe: &'a MoveDataParamEnv<'tcx>,
229 impl<'a, 'tcx> EverInitializedPlaces<'a, 'tcx> {
230 pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
231 EverInitializedPlaces { tcx, body, mdpe }
235 impl<'a, 'tcx> HasMoveData<'tcx> for EverInitializedPlaces<'a, 'tcx> {
236 fn move_data(&self) -> &MoveData<'tcx> {
241 impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> {
243 trans: &mut impl GenKill<MovePathIndex>,
245 state: DropFlagState,
248 DropFlagState::Absent => trans.kill(path),
249 DropFlagState::Present => trans.gen(path),
254 impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> {
256 trans: &mut impl GenKill<MovePathIndex>,
258 state: DropFlagState,
261 DropFlagState::Absent => trans.gen(path),
262 DropFlagState::Present => trans.kill(path),
267 impl<'a, 'tcx> DefinitelyInitializedPlaces<'a, 'tcx> {
269 trans: &mut impl GenKill<MovePathIndex>,
271 state: DropFlagState,
274 DropFlagState::Absent => trans.kill(path),
275 DropFlagState::Present => trans.gen(path),
280 impl<'tcx> AnalysisDomain<'tcx> for MaybeInitializedPlaces<'_, 'tcx> {
281 type Idx = MovePathIndex;
283 const NAME: &'static str = "maybe_init";
285 fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize {
286 self.move_data().move_paths.len()
289 fn initialize_start_block(&self, _: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) {
290 drop_flag_effects_for_function_entry(self.tcx, self.body, self.mdpe, |path, s| {
291 assert!(s == DropFlagState::Present);
296 fn pretty_print_idx(&self, w: &mut impl std::io::Write, mpi: Self::Idx) -> std::io::Result<()> {
297 write!(w, "{}", self.move_data().move_paths[mpi])
301 impl<'tcx> GenKillAnalysis<'tcx> for MaybeInitializedPlaces<'_, 'tcx> {
304 trans: &mut impl GenKill<Self::Idx>,
305 _statement: &mir::Statement<'tcx>,
308 drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| {
309 Self::update_bits(trans, path, s)
313 fn terminator_effect(
315 trans: &mut impl GenKill<Self::Idx>,
316 _terminator: &mir::Terminator<'tcx>,
319 drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| {
320 Self::update_bits(trans, path, s)
324 fn call_return_effect(
326 trans: &mut impl GenKill<Self::Idx>,
327 _block: mir::BasicBlock,
328 _func: &mir::Operand<'tcx>,
329 _args: &[mir::Operand<'tcx>],
330 dest_place: mir::Place<'tcx>,
332 // when a call returns successfully, that means we need to set
333 // the bits for that dest_place to 1 (initialized).
334 on_lookup_result_bits(
338 self.move_data().rev_lookup.find(dest_place.as_ref()),
345 fn discriminant_switch_effect(
347 trans: &mut impl GenKill<Self::Idx>,
348 _block: mir::BasicBlock,
349 enum_place: mir::Place<'tcx>,
353 let enum_mpi = match self.move_data().rev_lookup.find(enum_place.as_ref()) {
354 LookupResult::Exact(mpi) => mpi,
355 LookupResult::Parent(_) => return,
358 // Kill all move paths that correspond to variants other than this one
359 let move_paths = &self.move_data().move_paths;
360 let enum_path = &move_paths[enum_mpi];
361 for (mpi, variant_path) in enum_path.children(move_paths) {
363 match variant_path.place.projection.last().unwrap() {
364 mir::ProjectionElem::Downcast(_, idx) if *idx == variant => continue,
365 _ => drop_flag_effects::on_all_children_bits(
370 |mpi| trans.kill(mpi),
377 impl<'tcx> AnalysisDomain<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> {
378 type Idx = MovePathIndex;
380 const NAME: &'static str = "maybe_uninit";
382 fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize {
383 self.move_data().move_paths.len()
386 // sets on_entry bits for Arg places
387 fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) {
388 // set all bits to 1 (uninit) before gathering counterevidence
389 assert!(self.bits_per_block(body) == state.domain_size());
392 drop_flag_effects_for_function_entry(self.tcx, self.body, self.mdpe, |path, s| {
393 assert!(s == DropFlagState::Present);
398 fn pretty_print_idx(&self, w: &mut impl std::io::Write, mpi: Self::Idx) -> std::io::Result<()> {
399 write!(w, "{}", self.move_data().move_paths[mpi])
403 impl<'tcx> GenKillAnalysis<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> {
406 trans: &mut impl GenKill<Self::Idx>,
407 _statement: &mir::Statement<'tcx>,
410 drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| {
411 Self::update_bits(trans, path, s)
415 fn terminator_effect(
417 trans: &mut impl GenKill<Self::Idx>,
418 _terminator: &mir::Terminator<'tcx>,
421 drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| {
422 Self::update_bits(trans, path, s)
426 fn call_return_effect(
428 trans: &mut impl GenKill<Self::Idx>,
429 _block: mir::BasicBlock,
430 _func: &mir::Operand<'tcx>,
431 _args: &[mir::Operand<'tcx>],
432 dest_place: mir::Place<'tcx>,
434 // when a call returns successfully, that means we need to set
435 // the bits for that dest_place to 0 (initialized).
436 on_lookup_result_bits(
440 self.move_data().rev_lookup.find(dest_place.as_ref()),
448 impl<'a, 'tcx> AnalysisDomain<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> {
449 type Idx = MovePathIndex;
451 const NAME: &'static str = "definite_init";
453 fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize {
454 self.move_data().move_paths.len()
457 // sets on_entry bits for Arg places
458 fn initialize_start_block(&self, _: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) {
461 drop_flag_effects_for_function_entry(self.tcx, self.body, self.mdpe, |path, s| {
462 assert!(s == DropFlagState::Present);
467 fn pretty_print_idx(&self, w: &mut impl std::io::Write, mpi: Self::Idx) -> std::io::Result<()> {
468 write!(w, "{}", self.move_data().move_paths[mpi])
472 impl<'tcx> GenKillAnalysis<'tcx> for DefinitelyInitializedPlaces<'_, 'tcx> {
475 trans: &mut impl GenKill<Self::Idx>,
476 _statement: &mir::Statement<'tcx>,
479 drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| {
480 Self::update_bits(trans, path, s)
484 fn terminator_effect(
486 trans: &mut impl GenKill<Self::Idx>,
487 _terminator: &mir::Terminator<'tcx>,
490 drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| {
491 Self::update_bits(trans, path, s)
495 fn call_return_effect(
497 trans: &mut impl GenKill<Self::Idx>,
498 _block: mir::BasicBlock,
499 _func: &mir::Operand<'tcx>,
500 _args: &[mir::Operand<'tcx>],
501 dest_place: mir::Place<'tcx>,
503 // when a call returns successfully, that means we need to set
504 // the bits for that dest_place to 1 (initialized).
505 on_lookup_result_bits(
509 self.move_data().rev_lookup.find(dest_place.as_ref()),
517 impl<'tcx> AnalysisDomain<'tcx> for EverInitializedPlaces<'_, 'tcx> {
518 type Idx = InitIndex;
520 const NAME: &'static str = "ever_init";
522 fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize {
523 self.move_data().inits.len()
526 fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) {
527 for arg_init in 0..body.arg_count {
528 state.insert(InitIndex::new(arg_init));
533 impl<'tcx> GenKillAnalysis<'tcx> for EverInitializedPlaces<'_, 'tcx> {
536 trans: &mut impl GenKill<Self::Idx>,
537 stmt: &mir::Statement<'tcx>,
540 let move_data = self.move_data();
541 let init_path_map = &move_data.init_path_map;
542 let init_loc_map = &move_data.init_loc_map;
543 let rev_lookup = &move_data.rev_lookup;
546 "statement {:?} at loc {:?} initializes move_indexes {:?}",
547 stmt, location, &init_loc_map[location]
549 trans.gen_all(init_loc_map[location].iter().copied());
551 if let mir::StatementKind::StorageDead(local) = stmt.kind {
552 // End inits for StorageDead, so that an immutable variable can
553 // be reinitialized on the next iteration of the loop.
554 let move_path_index = rev_lookup.find_local(local);
556 "stmt {:?} at loc {:?} clears the ever initialized status of {:?}",
557 stmt, location, &init_path_map[move_path_index]
559 trans.kill_all(init_path_map[move_path_index].iter().copied());
563 fn terminator_effect(
565 trans: &mut impl GenKill<Self::Idx>,
566 _terminator: &mir::Terminator<'tcx>,
569 let (body, move_data) = (self.body, self.move_data());
570 let term = body[location.block].terminator();
571 let init_loc_map = &move_data.init_loc_map;
573 "terminator {:?} at loc {:?} initializes move_indexes {:?}",
574 term, location, &init_loc_map[location]
577 init_loc_map[location]
579 .filter(|init_index| {
580 move_data.inits[**init_index].kind != InitKind::NonPanicPathOnly
586 fn call_return_effect(
588 trans: &mut impl GenKill<Self::Idx>,
589 block: mir::BasicBlock,
590 _func: &mir::Operand<'tcx>,
591 _args: &[mir::Operand<'tcx>],
592 _dest_place: mir::Place<'tcx>,
594 let move_data = self.move_data();
595 let init_loc_map = &move_data.init_loc_map;
597 let call_loc = self.body.terminator_loc(block);
598 for init_index in &init_loc_map[call_loc] {
599 trans.gen(*init_index);
604 impl<'a, 'tcx> BottomValue for MaybeInitializedPlaces<'a, 'tcx> {
605 /// bottom = uninitialized
606 const BOTTOM_VALUE: bool = false;
609 impl<'a, 'tcx> BottomValue for MaybeUninitializedPlaces<'a, 'tcx> {
610 /// bottom = initialized (start_block_effect counters this at outset)
611 const BOTTOM_VALUE: bool = false;
614 impl<'a, 'tcx> BottomValue for DefinitelyInitializedPlaces<'a, 'tcx> {
615 /// bottom = initialized (start_block_effect counters this at outset)
616 const BOTTOM_VALUE: bool = true;
619 impl<'a, 'tcx> BottomValue for EverInitializedPlaces<'a, 'tcx> {
620 /// bottom = no initialized variables by default
621 const BOTTOM_VALUE: bool = false;