1 //! Dataflow analyses are built upon some interpretation of the
2 //! bitvectors attached to each basic block, represented via a
3 //! zero-sized structure.
6 use rustc::mir::{self, Mir, Location};
7 use rustc_data_structures::bit_set::{BitSet, BitSetOperator};
8 use rustc_data_structures::indexed_vec::Idx;
10 use super::MoveDataParamEnv;
12 use crate::util::elaborate_drops::DropFlagState;
14 use super::move_paths::{HasMoveData, MoveData, MovePathIndex, InitIndex, InitKind};
15 use super::{BitDenotation, BlockSets, InitialFlow};
17 use super::drop_flag_effects_for_function_entry;
18 use super::drop_flag_effects_for_location;
19 use super::on_lookup_result_bits;
23 pub use self::storage_liveness::*;
27 pub use self::borrowed_locals::*;
29 pub(super) mod borrows;
31 /// `MaybeInitializedPlaces` tracks all places that might be
32 /// initialized upon reaching a particular point in the control flow
35 /// For example, in code like the following, we have corresponding
36 /// dataflow information shown in the right-hand comments.
40 /// fn foo(pred: bool) { // maybe-init:
42 /// let a = S; let b = S; let c; let d; // {a, b}
54 /// c = S; // {a, b, c, d}
58 /// To determine whether a place *must* be initialized at a
59 /// particular control-flow point, one can take the set-difference
60 /// between this data and the data from `MaybeUninitializedPlaces` at the
61 /// corresponding control-flow point.
63 /// Similarly, at a given `drop` statement, the set-intersection
64 /// between this data and `MaybeUninitializedPlaces` yields the set of
65 /// places that would require a dynamic drop-flag at that statement.
66 pub struct MaybeInitializedPlaces<'a, 'gcx: 'tcx, 'tcx: 'a> {
67 tcx: TyCtxt<'a, 'gcx, 'tcx>,
69 mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>,
72 impl<'a, 'gcx: 'tcx, 'tcx> MaybeInitializedPlaces<'a, 'gcx, 'tcx> {
73 pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
75 mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>)
78 MaybeInitializedPlaces { tcx: tcx, mir: mir, mdpe: mdpe }
82 impl<'a, 'gcx, 'tcx> HasMoveData<'tcx> for MaybeInitializedPlaces<'a, 'gcx, 'tcx> {
83 fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
86 /// `MaybeUninitializedPlaces` tracks all places that might be
87 /// uninitialized upon reaching a particular point in the control flow
90 /// For example, in code like the following, we have corresponding
91 /// dataflow information shown in the right-hand comments.
95 /// fn foo(pred: bool) { // maybe-uninit:
97 /// let a = S; let b = S; let c; let d; // { c, d}
100 /// drop(a); // {a, c, d}
101 /// b = S; // {a, c, d}
104 /// drop(b); // { b, c, d}
105 /// d = S; // { b, c }
107 /// } // {a, b, c, d}
109 /// c = S; // {a, b, d}
113 /// To determine whether a place *must* be uninitialized at a
114 /// particular control-flow point, one can take the set-difference
115 /// between this data and the data from `MaybeInitializedPlaces` at the
116 /// corresponding control-flow point.
118 /// Similarly, at a given `drop` statement, the set-intersection
119 /// between this data and `MaybeInitializedPlaces` yields the set of
120 /// places that would require a dynamic drop-flag at that statement.
121 pub struct MaybeUninitializedPlaces<'a, 'gcx: 'tcx, 'tcx: 'a> {
122 tcx: TyCtxt<'a, 'gcx, 'tcx>,
124 mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>,
127 impl<'a, 'gcx, 'tcx> MaybeUninitializedPlaces<'a, 'gcx, 'tcx> {
128 pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
130 mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>)
133 MaybeUninitializedPlaces { tcx: tcx, mir: mir, mdpe: mdpe }
137 impl<'a, 'gcx, 'tcx> HasMoveData<'tcx> for MaybeUninitializedPlaces<'a, 'gcx, 'tcx> {
138 fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
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, 'gcx: 'tcx, 'tcx: 'a> {
176 tcx: TyCtxt<'a, 'gcx, 'tcx>,
178 mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>,
181 impl<'a, 'gcx, 'tcx: 'a> DefinitelyInitializedPlaces<'a, 'gcx, 'tcx> {
182 pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
184 mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>)
187 DefinitelyInitializedPlaces { tcx: tcx, mir: mir, mdpe: mdpe }
191 impl<'a, 'gcx, 'tcx: 'a> HasMoveData<'tcx> for DefinitelyInitializedPlaces<'a, 'gcx, 'tcx> {
192 fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
195 /// `EverInitializedPlaces` tracks all places that might have ever been
196 /// initialized upon reaching a particular point in the control flow
197 /// for a function, without an intervening `Storage Dead`.
199 /// This dataflow is used to determine if an immutable local variable may
202 /// For example, in code like the following, we have corresponding
203 /// dataflow information shown in the right-hand comments.
207 /// fn foo(pred: bool) { // ever-init:
209 /// let a = S; let b = S; let c; let d; // {a, b }
212 /// drop(a); // {a, b, }
213 /// b = S; // {a, b, }
216 /// drop(b); // {a, b, }
217 /// d = S; // {a, b, d }
221 /// c = S; // {a, b, c, d }
224 pub struct EverInitializedPlaces<'a, 'gcx: 'tcx, 'tcx: 'a> {
225 tcx: TyCtxt<'a, 'gcx, 'tcx>,
227 mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>,
230 impl<'a, 'gcx: 'tcx, 'tcx: 'a> EverInitializedPlaces<'a, 'gcx, 'tcx> {
231 pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
233 mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>)
236 EverInitializedPlaces { tcx: tcx, mir: mir, mdpe: mdpe }
240 impl<'a, 'gcx, 'tcx> HasMoveData<'tcx> for EverInitializedPlaces<'a, 'gcx, 'tcx> {
241 fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
245 impl<'a, 'gcx, 'tcx> MaybeInitializedPlaces<'a, 'gcx, 'tcx> {
246 fn update_bits(sets: &mut BlockSets<'_, MovePathIndex>, path: MovePathIndex,
247 state: DropFlagState)
250 DropFlagState::Absent => sets.kill(path),
251 DropFlagState::Present => sets.gen(path),
256 impl<'a, 'gcx, 'tcx> MaybeUninitializedPlaces<'a, 'gcx, 'tcx> {
257 fn update_bits(sets: &mut BlockSets<'_, MovePathIndex>, path: MovePathIndex,
258 state: DropFlagState)
261 DropFlagState::Absent => sets.gen(path),
262 DropFlagState::Present => sets.kill(path),
267 impl<'a, 'gcx, 'tcx> DefinitelyInitializedPlaces<'a, 'gcx, 'tcx> {
268 fn update_bits(sets: &mut BlockSets<'_, MovePathIndex>, path: MovePathIndex,
269 state: DropFlagState)
272 DropFlagState::Absent => sets.kill(path),
273 DropFlagState::Present => sets.gen(path),
278 impl<'a, 'gcx, 'tcx> BitDenotation<'tcx> for MaybeInitializedPlaces<'a, 'gcx, 'tcx> {
279 type Idx = MovePathIndex;
280 fn name() -> &'static str { "maybe_init" }
281 fn bits_per_block(&self) -> usize {
282 self.move_data().move_paths.len()
285 fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) {
286 drop_flag_effects_for_function_entry(
287 self.tcx, self.mir, self.mdpe,
289 assert!(s == DropFlagState::Present);
290 entry_set.insert(path);
294 fn statement_effect(&self,
295 sets: &mut BlockSets<'_, MovePathIndex>,
298 drop_flag_effects_for_location(
299 self.tcx, self.mir, self.mdpe,
301 |path, s| Self::update_bits(sets, path, s)
305 fn terminator_effect(&self,
306 sets: &mut BlockSets<'_, MovePathIndex>,
309 drop_flag_effects_for_location(
310 self.tcx, self.mir, self.mdpe,
312 |path, s| Self::update_bits(sets, path, s)
316 fn propagate_call_return(
318 in_out: &mut BitSet<MovePathIndex>,
319 _call_bb: mir::BasicBlock,
320 _dest_bb: mir::BasicBlock,
321 dest_place: &mir::Place<'tcx>,
323 // when a call returns successfully, that means we need to set
324 // the bits for that dest_place to 1 (initialized).
325 on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
326 self.move_data().rev_lookup.find(dest_place),
327 |mpi| { in_out.insert(mpi); });
331 impl<'a, 'gcx, 'tcx> BitDenotation<'tcx> for MaybeUninitializedPlaces<'a, 'gcx, 'tcx> {
332 type Idx = MovePathIndex;
333 fn name() -> &'static str { "maybe_uninit" }
334 fn bits_per_block(&self) -> usize {
335 self.move_data().move_paths.len()
338 // sets on_entry bits for Arg places
339 fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) {
340 // set all bits to 1 (uninit) before gathering counterevidence
341 assert!(self.bits_per_block() == entry_set.domain_size());
342 entry_set.insert_all();
344 drop_flag_effects_for_function_entry(
345 self.tcx, self.mir, self.mdpe,
347 assert!(s == DropFlagState::Present);
348 entry_set.remove(path);
352 fn statement_effect(&self,
353 sets: &mut BlockSets<'_, MovePathIndex>,
356 drop_flag_effects_for_location(
357 self.tcx, self.mir, self.mdpe,
359 |path, s| Self::update_bits(sets, path, s)
363 fn terminator_effect(&self,
364 sets: &mut BlockSets<'_, MovePathIndex>,
367 drop_flag_effects_for_location(
368 self.tcx, self.mir, self.mdpe,
370 |path, s| Self::update_bits(sets, path, s)
374 fn propagate_call_return(
376 in_out: &mut BitSet<MovePathIndex>,
377 _call_bb: mir::BasicBlock,
378 _dest_bb: mir::BasicBlock,
379 dest_place: &mir::Place<'tcx>,
381 // when a call returns successfully, that means we need to set
382 // the bits for that dest_place to 0 (initialized).
383 on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
384 self.move_data().rev_lookup.find(dest_place),
385 |mpi| { in_out.remove(mpi); });
389 impl<'a, 'gcx, 'tcx> BitDenotation<'tcx> for DefinitelyInitializedPlaces<'a, 'gcx, 'tcx> {
390 type Idx = MovePathIndex;
391 fn name() -> &'static str { "definite_init" }
392 fn bits_per_block(&self) -> usize {
393 self.move_data().move_paths.len()
396 // sets on_entry bits for Arg places
397 fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) {
400 drop_flag_effects_for_function_entry(
401 self.tcx, self.mir, self.mdpe,
403 assert!(s == DropFlagState::Present);
404 entry_set.insert(path);
408 fn statement_effect(&self,
409 sets: &mut BlockSets<'_, MovePathIndex>,
412 drop_flag_effects_for_location(
413 self.tcx, self.mir, self.mdpe,
415 |path, s| Self::update_bits(sets, path, s)
419 fn terminator_effect(&self,
420 sets: &mut BlockSets<'_, MovePathIndex>,
423 drop_flag_effects_for_location(
424 self.tcx, self.mir, self.mdpe,
426 |path, s| Self::update_bits(sets, path, s)
430 fn propagate_call_return(
432 in_out: &mut BitSet<MovePathIndex>,
433 _call_bb: mir::BasicBlock,
434 _dest_bb: mir::BasicBlock,
435 dest_place: &mir::Place<'tcx>,
437 // when a call returns successfully, that means we need to set
438 // the bits for that dest_place to 1 (initialized).
439 on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
440 self.move_data().rev_lookup.find(dest_place),
441 |mpi| { in_out.insert(mpi); });
445 impl<'a, 'gcx, 'tcx> BitDenotation<'tcx> for EverInitializedPlaces<'a, 'gcx, 'tcx> {
446 type Idx = InitIndex;
447 fn name() -> &'static str { "ever_init" }
448 fn bits_per_block(&self) -> usize {
449 self.move_data().inits.len()
452 fn start_block_effect(&self, entry_set: &mut BitSet<InitIndex>) {
453 for arg_init in 0..self.mir.arg_count {
454 entry_set.insert(InitIndex::new(arg_init));
458 fn statement_effect(&self,
459 sets: &mut BlockSets<'_, InitIndex>,
460 location: Location) {
461 let (_, mir, move_data) = (self.tcx, self.mir, self.move_data());
462 let stmt = &mir[location.block].statements[location.statement_index];
463 let init_path_map = &move_data.init_path_map;
464 let init_loc_map = &move_data.init_loc_map;
465 let rev_lookup = &move_data.rev_lookup;
467 debug!("statement {:?} at loc {:?} initializes move_indexes {:?}",
468 stmt, location, &init_loc_map[location]);
469 sets.gen_all(&init_loc_map[location]);
472 mir::StatementKind::StorageDead(local) => {
473 // End inits for StorageDead, so that an immutable variable can
474 // be reinitialized on the next iteration of the loop.
475 let move_path_index = rev_lookup.find_local(local);
476 debug!("stmt {:?} at loc {:?} clears the ever initialized status of {:?}",
477 stmt, location, &init_path_map[move_path_index]);
478 sets.kill_all(&init_path_map[move_path_index]);
484 fn terminator_effect(&self,
485 sets: &mut BlockSets<'_, InitIndex>,
488 let (mir, move_data) = (self.mir, self.move_data());
489 let term = mir[location.block].terminator();
490 let init_loc_map = &move_data.init_loc_map;
491 debug!("terminator {:?} at loc {:?} initializes move_indexes {:?}",
492 term, location, &init_loc_map[location]);
494 init_loc_map[location].iter().filter(|init_index| {
495 move_data.inits[**init_index].kind != InitKind::NonPanicPathOnly
500 fn propagate_call_return(
502 in_out: &mut BitSet<InitIndex>,
503 call_bb: mir::BasicBlock,
504 _dest_bb: mir::BasicBlock,
505 _dest_place: &mir::Place<'tcx>,
507 let move_data = self.move_data();
508 let bits_per_block = self.bits_per_block();
509 let init_loc_map = &move_data.init_loc_map;
511 let call_loc = Location {
513 statement_index: self.mir[call_bb].statements.len(),
515 for init_index in &init_loc_map[call_loc] {
516 assert!(init_index.index() < bits_per_block);
517 in_out.insert(*init_index);
522 impl<'a, 'gcx, 'tcx> BitSetOperator for MaybeInitializedPlaces<'a, 'gcx, 'tcx> {
524 fn join<T: Idx>(&self, inout_set: &mut BitSet<T>, in_set: &BitSet<T>) -> bool {
525 inout_set.union(in_set) // "maybe" means we union effects of both preds
529 impl<'a, 'gcx, 'tcx> BitSetOperator for MaybeUninitializedPlaces<'a, 'gcx, 'tcx> {
531 fn join<T: Idx>(&self, inout_set: &mut BitSet<T>, in_set: &BitSet<T>) -> bool {
532 inout_set.union(in_set) // "maybe" means we union effects of both preds
536 impl<'a, 'gcx, 'tcx> BitSetOperator for DefinitelyInitializedPlaces<'a, 'gcx, 'tcx> {
538 fn join<T: Idx>(&self, inout_set: &mut BitSet<T>, in_set: &BitSet<T>) -> bool {
539 inout_set.intersect(in_set) // "definitely" means we intersect effects of both preds
543 impl<'a, 'gcx, 'tcx> BitSetOperator for EverInitializedPlaces<'a, 'gcx, 'tcx> {
545 fn join<T: Idx>(&self, inout_set: &mut BitSet<T>, in_set: &BitSet<T>) -> bool {
546 inout_set.union(in_set) // inits from both preds are in scope
550 // The way that dataflow fixed point iteration works, you want to
551 // start at bottom and work your way to a fixed point. Control-flow
552 // merges will apply the `join` operator to each block entry's current
553 // state (which starts at that bottom value).
555 // This means, for propagation across the graph, that you either want
556 // to start at all-zeroes and then use Union as your merge when
557 // propagating, or you start at all-ones and then use Intersect as
558 // your merge when propagating.
560 impl<'a, 'gcx, 'tcx> InitialFlow for MaybeInitializedPlaces<'a, 'gcx, 'tcx> {
562 fn bottom_value() -> bool {
563 false // bottom = uninitialized
567 impl<'a, 'gcx, 'tcx> InitialFlow for MaybeUninitializedPlaces<'a, 'gcx, 'tcx> {
569 fn bottom_value() -> bool {
570 false // bottom = initialized (start_block_effect counters this at outset)
574 impl<'a, 'gcx, 'tcx> InitialFlow for DefinitelyInitializedPlaces<'a, 'gcx, 'tcx> {
576 fn bottom_value() -> bool {
577 true // bottom = initialized (start_block_effect counters this at outset)
581 impl<'a, 'gcx, 'tcx> InitialFlow for EverInitializedPlaces<'a, 'gcx, 'tcx> {
583 fn bottom_value() -> bool {
584 false // bottom = no initialized variables by default