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, Body, Location};
7 use rustc_data_structures::bit_set::BitSet;
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, BottomValue, GenKillSet};
17 use super::drop_flag_effects_for_function_entry;
18 use super::drop_flag_effects_for_location;
19 use super::on_lookup_result_bits;
22 mod indirect_mutation;
25 pub use self::borrowed_locals::*;
26 pub use self::indirect_mutation::IndirectlyMutableLocals;
27 pub use self::storage_liveness::*;
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, 'tcx> {
69 mdpe: &'a MoveDataParamEnv<'tcx>,
72 impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> {
73 pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
74 MaybeInitializedPlaces { tcx: tcx, body: body, mdpe: mdpe }
78 impl<'a, 'tcx> HasMoveData<'tcx> for MaybeInitializedPlaces<'a, 'tcx> {
79 fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
82 /// `MaybeUninitializedPlaces` tracks all places that might be
83 /// uninitialized upon reaching a particular point in the control flow
86 /// For example, in code like the following, we have corresponding
87 /// dataflow information shown in the right-hand comments.
91 /// fn foo(pred: bool) { // maybe-uninit:
93 /// let a = S; let b = S; let c; let d; // { c, d}
96 /// drop(a); // {a, c, d}
97 /// b = S; // {a, c, d}
100 /// drop(b); // { b, c, d}
101 /// d = S; // { b, c }
103 /// } // {a, b, c, d}
105 /// c = S; // {a, b, d}
109 /// To determine whether a place *must* be uninitialized at a
110 /// particular control-flow point, one can take the set-difference
111 /// between this data and the data from `MaybeInitializedPlaces` at the
112 /// corresponding control-flow point.
114 /// Similarly, at a given `drop` statement, the set-intersection
115 /// between this data and `MaybeInitializedPlaces` yields the set of
116 /// places that would require a dynamic drop-flag at that statement.
117 pub struct MaybeUninitializedPlaces<'a, 'tcx> {
119 body: &'a Body<'tcx>,
120 mdpe: &'a MoveDataParamEnv<'tcx>,
123 impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> {
124 pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
125 MaybeUninitializedPlaces { tcx: tcx, body: body, mdpe: mdpe }
129 impl<'a, 'tcx> HasMoveData<'tcx> for MaybeUninitializedPlaces<'a, 'tcx> {
130 fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
133 /// `DefinitelyInitializedPlaces` tracks all places that are definitely
134 /// initialized upon reaching a particular point in the control flow
137 /// For example, in code like the following, we have corresponding
138 /// dataflow information shown in the right-hand comments.
142 /// fn foo(pred: bool) { // definite-init:
144 /// let a = S; let b = S; let c; let d; // {a, b }
147 /// drop(a); // { b, }
151 /// drop(b); // {a, }
160 /// To determine whether a place *may* be uninitialized at a
161 /// particular control-flow point, one can take the set-complement
164 /// Similarly, at a given `drop` statement, the set-difference between
165 /// this data and `MaybeInitializedPlaces` yields the set of places
166 /// that would require a dynamic drop-flag at that statement.
167 pub struct DefinitelyInitializedPlaces<'a, 'tcx> {
169 body: &'a Body<'tcx>,
170 mdpe: &'a MoveDataParamEnv<'tcx>,
173 impl<'a, 'tcx> DefinitelyInitializedPlaces<'a, 'tcx> {
174 pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
175 DefinitelyInitializedPlaces { tcx: tcx, body: body, mdpe: mdpe }
179 impl<'a, 'tcx> HasMoveData<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> {
180 fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
183 /// `EverInitializedPlaces` tracks all places that might have ever been
184 /// initialized upon reaching a particular point in the control flow
185 /// for a function, without an intervening `Storage Dead`.
187 /// This dataflow is used to determine if an immutable local variable may
190 /// For example, in code like the following, we have corresponding
191 /// dataflow information shown in the right-hand comments.
195 /// fn foo(pred: bool) { // ever-init:
197 /// let a = S; let b = S; let c; let d; // {a, b }
200 /// drop(a); // {a, b, }
201 /// b = S; // {a, b, }
204 /// drop(b); // {a, b, }
205 /// d = S; // {a, b, d }
209 /// c = S; // {a, b, c, d }
212 pub struct EverInitializedPlaces<'a, 'tcx> {
214 body: &'a Body<'tcx>,
215 mdpe: &'a MoveDataParamEnv<'tcx>,
218 impl<'a, 'tcx> EverInitializedPlaces<'a, 'tcx> {
219 pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
220 EverInitializedPlaces { tcx: tcx, body: body, mdpe: mdpe }
224 impl<'a, 'tcx> HasMoveData<'tcx> for EverInitializedPlaces<'a, 'tcx> {
225 fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
228 impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> {
229 fn update_bits(trans: &mut GenKillSet<MovePathIndex>,
231 state: DropFlagState)
234 DropFlagState::Absent => trans.kill(path),
235 DropFlagState::Present => trans.gen(path),
240 impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> {
241 fn update_bits(trans: &mut GenKillSet<MovePathIndex>,
243 state: DropFlagState)
246 DropFlagState::Absent => trans.gen(path),
247 DropFlagState::Present => trans.kill(path),
252 impl<'a, 'tcx> DefinitelyInitializedPlaces<'a, 'tcx> {
253 fn update_bits(trans: &mut GenKillSet<MovePathIndex>,
255 state: DropFlagState)
258 DropFlagState::Absent => trans.kill(path),
259 DropFlagState::Present => trans.gen(path),
264 impl<'a, 'tcx> BitDenotation<'tcx> for MaybeInitializedPlaces<'a, 'tcx> {
265 type Idx = MovePathIndex;
266 fn name() -> &'static str { "maybe_init" }
267 fn bits_per_block(&self) -> usize {
268 self.move_data().move_paths.len()
271 fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) {
272 drop_flag_effects_for_function_entry(
273 self.tcx, self.body, self.mdpe,
275 assert!(s == DropFlagState::Present);
276 entry_set.insert(path);
280 fn statement_effect(&self,
281 trans: &mut GenKillSet<Self::Idx>,
284 drop_flag_effects_for_location(
285 self.tcx, self.body, self.mdpe,
287 |path, s| Self::update_bits(trans, path, s)
291 fn terminator_effect(&self,
292 trans: &mut GenKillSet<Self::Idx>,
295 drop_flag_effects_for_location(
296 self.tcx, self.body, self.mdpe,
298 |path, s| Self::update_bits(trans, path, s)
302 fn propagate_call_return(
304 in_out: &mut BitSet<MovePathIndex>,
305 _call_bb: mir::BasicBlock,
306 _dest_bb: mir::BasicBlock,
307 dest_place: &mir::Place<'tcx>,
309 // when a call returns successfully, that means we need to set
310 // the bits for that dest_place to 1 (initialized).
311 on_lookup_result_bits(self.tcx, self.body, self.move_data(),
312 self.move_data().rev_lookup.find(dest_place.as_ref()),
313 |mpi| { in_out.insert(mpi); });
317 impl<'a, 'tcx> BitDenotation<'tcx> for MaybeUninitializedPlaces<'a, 'tcx> {
318 type Idx = MovePathIndex;
319 fn name() -> &'static str { "maybe_uninit" }
320 fn bits_per_block(&self) -> usize {
321 self.move_data().move_paths.len()
324 // sets on_entry bits for Arg places
325 fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) {
326 // set all bits to 1 (uninit) before gathering counterevidence
327 assert!(self.bits_per_block() == entry_set.domain_size());
328 entry_set.insert_all();
330 drop_flag_effects_for_function_entry(
331 self.tcx, self.body, self.mdpe,
333 assert!(s == DropFlagState::Present);
334 entry_set.remove(path);
338 fn statement_effect(&self,
339 trans: &mut GenKillSet<Self::Idx>,
342 drop_flag_effects_for_location(
343 self.tcx, self.body, self.mdpe,
345 |path, s| Self::update_bits(trans, path, s)
349 fn terminator_effect(&self,
350 trans: &mut GenKillSet<Self::Idx>,
353 drop_flag_effects_for_location(
354 self.tcx, self.body, self.mdpe,
356 |path, s| Self::update_bits(trans, path, s)
360 fn propagate_call_return(
362 in_out: &mut BitSet<MovePathIndex>,
363 _call_bb: mir::BasicBlock,
364 _dest_bb: mir::BasicBlock,
365 dest_place: &mir::Place<'tcx>,
367 // when a call returns successfully, that means we need to set
368 // the bits for that dest_place to 0 (initialized).
369 on_lookup_result_bits(self.tcx, self.body, self.move_data(),
370 self.move_data().rev_lookup.find(dest_place.as_ref()),
371 |mpi| { in_out.remove(mpi); });
375 impl<'a, 'tcx> BitDenotation<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> {
376 type Idx = MovePathIndex;
377 fn name() -> &'static str { "definite_init" }
378 fn bits_per_block(&self) -> usize {
379 self.move_data().move_paths.len()
382 // sets on_entry bits for Arg places
383 fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) {
386 drop_flag_effects_for_function_entry(
387 self.tcx, self.body, self.mdpe,
389 assert!(s == DropFlagState::Present);
390 entry_set.insert(path);
394 fn statement_effect(&self,
395 trans: &mut GenKillSet<Self::Idx>,
398 drop_flag_effects_for_location(
399 self.tcx, self.body, self.mdpe,
401 |path, s| Self::update_bits(trans, path, s)
405 fn terminator_effect(&self,
406 trans: &mut GenKillSet<Self::Idx>,
409 drop_flag_effects_for_location(
410 self.tcx, self.body, self.mdpe,
412 |path, s| Self::update_bits(trans, path, s)
416 fn propagate_call_return(
418 in_out: &mut BitSet<MovePathIndex>,
419 _call_bb: mir::BasicBlock,
420 _dest_bb: mir::BasicBlock,
421 dest_place: &mir::Place<'tcx>,
423 // when a call returns successfully, that means we need to set
424 // the bits for that dest_place to 1 (initialized).
425 on_lookup_result_bits(self.tcx, self.body, self.move_data(),
426 self.move_data().rev_lookup.find(dest_place.as_ref()),
427 |mpi| { in_out.insert(mpi); });
431 impl<'a, 'tcx> BitDenotation<'tcx> for EverInitializedPlaces<'a, 'tcx> {
432 type Idx = InitIndex;
433 fn name() -> &'static str { "ever_init" }
434 fn bits_per_block(&self) -> usize {
435 self.move_data().inits.len()
438 fn start_block_effect(&self, entry_set: &mut BitSet<InitIndex>) {
439 for arg_init in 0..self.body.arg_count {
440 entry_set.insert(InitIndex::new(arg_init));
444 fn statement_effect(&self,
445 trans: &mut GenKillSet<Self::Idx>,
446 location: Location) {
447 let (_, body, move_data) = (self.tcx, self.body, self.move_data());
448 let stmt = &body[location.block].statements[location.statement_index];
449 let init_path_map = &move_data.init_path_map;
450 let init_loc_map = &move_data.init_loc_map;
451 let rev_lookup = &move_data.rev_lookup;
453 debug!("statement {:?} at loc {:?} initializes move_indexes {:?}",
454 stmt, location, &init_loc_map[location]);
455 trans.gen_all(&init_loc_map[location]);
458 mir::StatementKind::StorageDead(local) => {
459 // End inits for StorageDead, so that an immutable variable can
460 // be reinitialized on the next iteration of the loop.
461 let move_path_index = rev_lookup.find_local(local);
462 debug!("stmt {:?} at loc {:?} clears the ever initialized status of {:?}",
463 stmt, location, &init_path_map[move_path_index]);
464 trans.kill_all(&init_path_map[move_path_index]);
470 fn terminator_effect(&self,
471 trans: &mut GenKillSet<Self::Idx>,
474 let (body, move_data) = (self.body, self.move_data());
475 let term = body[location.block].terminator();
476 let init_loc_map = &move_data.init_loc_map;
477 debug!("terminator {:?} at loc {:?} initializes move_indexes {:?}",
478 term, location, &init_loc_map[location]);
480 init_loc_map[location].iter().filter(|init_index| {
481 move_data.inits[**init_index].kind != InitKind::NonPanicPathOnly
486 fn propagate_call_return(
488 in_out: &mut BitSet<InitIndex>,
489 call_bb: mir::BasicBlock,
490 _dest_bb: mir::BasicBlock,
491 _dest_place: &mir::Place<'tcx>,
493 let move_data = self.move_data();
494 let bits_per_block = self.bits_per_block();
495 let init_loc_map = &move_data.init_loc_map;
497 let call_loc = Location {
499 statement_index: self.body[call_bb].statements.len(),
501 for init_index in &init_loc_map[call_loc] {
502 assert!(init_index.index() < bits_per_block);
503 in_out.insert(*init_index);
508 impl<'a, 'tcx> BottomValue for MaybeInitializedPlaces<'a, 'tcx> {
509 /// bottom = uninitialized
510 const BOTTOM_VALUE: bool = false;
513 impl<'a, 'tcx> BottomValue for MaybeUninitializedPlaces<'a, 'tcx> {
514 /// bottom = initialized (start_block_effect counters this at outset)
515 const BOTTOM_VALUE: bool = false;
518 impl<'a, 'tcx> BottomValue for DefinitelyInitializedPlaces<'a, 'tcx> {
519 /// bottom = initialized (start_block_effect counters this at outset)
520 const BOTTOM_VALUE: bool = true;
523 impl<'a, 'tcx> BottomValue for EverInitializedPlaces<'a, 'tcx> {
524 /// bottom = no initialized variables by default
525 const BOTTOM_VALUE: bool = false;