src/librustc_mir/dataflow/impls/mod.rs

   1 //! Dataflow analyses are built upon some interpretation of the
   2 //! bitvectors attached to each basic block, represented via a
   3 //! zero-sized structure.
   4
   5 use rustc::ty::TyCtxt;
   6 use rustc::mir::{self, Body, Location};
   7 use rustc_data_structures::bit_set::BitSet;
   8 use rustc_data_structures::indexed_vec::Idx;
   9
  10 use super::MoveDataParamEnv;
  11
  12 use crate::util::elaborate_drops::DropFlagState;
  13
  14 use super::move_paths::{HasMoveData, MoveData, MovePathIndex, InitIndex, InitKind};
  15 use super::{BitDenotation, BottomValue, GenKillSet};
  16
  17 use super::drop_flag_effects_for_function_entry;
  18 use super::drop_flag_effects_for_location;
  19 use super::on_lookup_result_bits;
  20
  21 mod storage_liveness;
  22
  23 pub use self::storage_liveness::*;
  24
  25 mod borrowed_locals;
  26
  27 pub use self::borrowed_locals::*;
  28
  29 pub(super) mod borrows;
  30
  31 /// `MaybeInitializedPlaces` tracks all places that might be
  32 /// initialized upon reaching a particular point in the control flow
  33 /// for a function.
  34 ///
  35 /// For example, in code like the following, we have corresponding
  36 /// dataflow information shown in the right-hand comments.
  37 ///
  38 /// ```rust
  39 /// struct S;
  40 /// fn foo(pred: bool) {                       // maybe-init:
  41 ///                                            // {}
  42 ///     let a = S; let b = S; let c; let d;    // {a, b}
  43 ///
  44 ///     if pred {
  45 ///         drop(a);                           // {   b}
  46 ///         b = S;                             // {   b}
  47 ///
  48 ///     } else {
  49 ///         drop(b);                           // {a}
  50 ///         d = S;                             // {a,       d}
  51 ///
  52 ///     }                                      // {a, b,    d}
  53 ///
  54 ///     c = S;                                 // {a, b, c, d}
  55 /// }
  56 /// ```
  57 ///
  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.
  62 ///
  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> {
  67     tcx: TyCtxt<'tcx>,
  68     body: &'a Body<'tcx>,
  69     mdpe: &'a MoveDataParamEnv<'tcx>,
  70 }
  71
  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 }
  75     }
  76 }
  77
  78 impl<'a, 'tcx> HasMoveData<'tcx> for MaybeInitializedPlaces<'a, 'tcx> {
  79     fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
  80 }
  81
  82 /// `MaybeUninitializedPlaces` tracks all places that might be
  83 /// uninitialized upon reaching a particular point in the control flow
  84 /// for a function.
  85 ///
  86 /// For example, in code like the following, we have corresponding
  87 /// dataflow information shown in the right-hand comments.
  88 ///
  89 /// ```rust
  90 /// struct S;
  91 /// fn foo(pred: bool) {                       // maybe-uninit:
  92 ///                                            // {a, b, c, d}
  93 ///     let a = S; let b = S; let c; let d;    // {      c, d}
  94 ///
  95 ///     if pred {
  96 ///         drop(a);                           // {a,    c, d}
  97 ///         b = S;                             // {a,    c, d}
  98 ///
  99 ///     } else {
 100 ///         drop(b);                           // {   b, c, d}
 101 ///         d = S;                             // {   b, c   }
 102 ///
 103 ///     }                                      // {a, b, c, d}
 104 ///
 105 ///     c = S;                                 // {a, b,    d}
 106 /// }
 107 /// ```
 108 ///
 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.
 113 ///
 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> {
 118     tcx: TyCtxt<'tcx>,
 119     body: &'a Body<'tcx>,
 120     mdpe: &'a MoveDataParamEnv<'tcx>,
 121 }
 122
 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 }
 126     }
 127 }
 128
 129 impl<'a, 'tcx> HasMoveData<'tcx> for MaybeUninitializedPlaces<'a, 'tcx> {
 130     fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
 131 }
 132
 133 /// `DefinitelyInitializedPlaces` tracks all places that are definitely
 134 /// initialized upon reaching a particular point in the control flow
 135 /// for a function.
 136 ///
 137 /// For example, in code like the following, we have corresponding
 138 /// dataflow information shown in the right-hand comments.
 139 ///
 140 /// ```rust
 141 /// struct S;
 142 /// fn foo(pred: bool) {                       // definite-init:
 143 ///                                            // {          }
 144 ///     let a = S; let b = S; let c; let d;    // {a, b      }
 145 ///
 146 ///     if pred {
 147 ///         drop(a);                           // {   b,     }
 148 ///         b = S;                             // {   b,     }
 149 ///
 150 ///     } else {
 151 ///         drop(b);                           // {a,        }
 152 ///         d = S;                             // {a,       d}
 153 ///
 154 ///     }                                      // {          }
 155 ///
 156 ///     c = S;                                 // {       c  }
 157 /// }
 158 /// ```
 159 ///
 160 /// To determine whether a place *may* be uninitialized at a
 161 /// particular control-flow point, one can take the set-complement
 162 /// of this data.
 163 ///
 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> {
 168     tcx: TyCtxt<'tcx>,
 169     body: &'a Body<'tcx>,
 170     mdpe: &'a MoveDataParamEnv<'tcx>,
 171 }
 172
 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 }
 176     }
 177 }
 178
 179 impl<'a, 'tcx> HasMoveData<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> {
 180     fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
 181 }
 182
 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`.
 186 ///
 187 /// This dataflow is used to determine if an immutable local variable may
 188 /// be assigned to.
 189 ///
 190 /// For example, in code like the following, we have corresponding
 191 /// dataflow information shown in the right-hand comments.
 192 ///
 193 /// ```rust
 194 /// struct S;
 195 /// fn foo(pred: bool) {                       // ever-init:
 196 ///                                            // {          }
 197 ///     let a = S; let b = S; let c; let d;    // {a, b      }
 198 ///
 199 ///     if pred {
 200 ///         drop(a);                           // {a, b,     }
 201 ///         b = S;                             // {a, b,     }
 202 ///
 203 ///     } else {
 204 ///         drop(b);                           // {a, b,      }
 205 ///         d = S;                             // {a, b,    d }
 206 ///
 207 ///     }                                      // {a, b,    d }
 208 ///
 209 ///     c = S;                                 // {a, b, c, d }
 210 /// }
 211 /// ```
 212 pub struct EverInitializedPlaces<'a, 'tcx> {
 213     tcx: TyCtxt<'tcx>,
 214     body: &'a Body<'tcx>,
 215     mdpe: &'a MoveDataParamEnv<'tcx>,
 216 }
 217
 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 }
 221     }
 222 }
 223
 224 impl<'a, 'tcx> HasMoveData<'tcx> for EverInitializedPlaces<'a, 'tcx> {
 225     fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
 226 }
 227
 228 impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> {
 229     fn update_bits(trans: &mut GenKillSet<MovePathIndex>,
 230                    path: MovePathIndex,
 231                    state: DropFlagState)
 232     {
 233         match state {
 234             DropFlagState::Absent => trans.kill(path),
 235             DropFlagState::Present => trans.gen(path),
 236         }
 237     }
 238 }
 239
 240 impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> {
 241     fn update_bits(trans: &mut GenKillSet<MovePathIndex>,
 242                    path: MovePathIndex,
 243                    state: DropFlagState)
 244     {
 245         match state {
 246             DropFlagState::Absent => trans.gen(path),
 247             DropFlagState::Present => trans.kill(path),
 248         }
 249     }
 250 }
 251
 252 impl<'a, 'tcx> DefinitelyInitializedPlaces<'a, 'tcx> {
 253     fn update_bits(trans: &mut GenKillSet<MovePathIndex>,
 254                    path: MovePathIndex,
 255                    state: DropFlagState)
 256     {
 257         match state {
 258             DropFlagState::Absent => trans.kill(path),
 259             DropFlagState::Present => trans.gen(path),
 260         }
 261     }
 262 }
 263
 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()
 269     }
 270
 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,
 274             |path, s| {
 275                 assert!(s == DropFlagState::Present);
 276                 entry_set.insert(path);
 277             });
 278     }
 279
 280     fn statement_effect(&self,
 281                         trans: &mut GenKillSet<Self::Idx>,
 282                         location: Location)
 283     {
 284         drop_flag_effects_for_location(
 285             self.tcx, self.body, self.mdpe,
 286             location,
 287             |path, s| Self::update_bits(trans, path, s)
 288         )
 289     }
 290
 291     fn terminator_effect(&self,
 292                          trans: &mut GenKillSet<Self::Idx>,
 293                          location: Location)
 294     {
 295         drop_flag_effects_for_location(
 296             self.tcx, self.body, self.mdpe,
 297             location,
 298             |path, s| Self::update_bits(trans, path, s)
 299         )
 300     }
 301
 302     fn propagate_call_return(
 303         &self,
 304         in_out: &mut BitSet<MovePathIndex>,
 305         _call_bb: mir::BasicBlock,
 306         _dest_bb: mir::BasicBlock,
 307         dest_place: &mir::Place<'tcx>,
 308     ) {
 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); });
 314     }
 315 }
 316
 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()
 322     }
 323
 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();
 329
 330         drop_flag_effects_for_function_entry(
 331             self.tcx, self.body, self.mdpe,
 332             |path, s| {
 333                 assert!(s == DropFlagState::Present);
 334                 entry_set.remove(path);
 335             });
 336     }
 337
 338     fn statement_effect(&self,
 339                         trans: &mut GenKillSet<Self::Idx>,
 340                         location: Location)
 341     {
 342         drop_flag_effects_for_location(
 343             self.tcx, self.body, self.mdpe,
 344             location,
 345             |path, s| Self::update_bits(trans, path, s)
 346         )
 347     }
 348
 349     fn terminator_effect(&self,
 350                          trans: &mut GenKillSet<Self::Idx>,
 351                          location: Location)
 352     {
 353         drop_flag_effects_for_location(
 354             self.tcx, self.body, self.mdpe,
 355             location,
 356             |path, s| Self::update_bits(trans, path, s)
 357         )
 358     }
 359
 360     fn propagate_call_return(
 361         &self,
 362         in_out: &mut BitSet<MovePathIndex>,
 363         _call_bb: mir::BasicBlock,
 364         _dest_bb: mir::BasicBlock,
 365         dest_place: &mir::Place<'tcx>,
 366     ) {
 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); });
 372     }
 373 }
 374
 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()
 380     }
 381
 382     // sets on_entry bits for Arg places
 383     fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) {
 384         entry_set.clear();
 385
 386         drop_flag_effects_for_function_entry(
 387             self.tcx, self.body, self.mdpe,
 388             |path, s| {
 389                 assert!(s == DropFlagState::Present);
 390                 entry_set.insert(path);
 391             });
 392     }
 393
 394     fn statement_effect(&self,
 395                         trans: &mut GenKillSet<Self::Idx>,
 396                         location: Location)
 397     {
 398         drop_flag_effects_for_location(
 399             self.tcx, self.body, self.mdpe,
 400             location,
 401             |path, s| Self::update_bits(trans, path, s)
 402         )
 403     }
 404
 405     fn terminator_effect(&self,
 406                          trans: &mut GenKillSet<Self::Idx>,
 407                          location: Location)
 408     {
 409         drop_flag_effects_for_location(
 410             self.tcx, self.body, self.mdpe,
 411             location,
 412             |path, s| Self::update_bits(trans, path, s)
 413         )
 414     }
 415
 416     fn propagate_call_return(
 417         &self,
 418         in_out: &mut BitSet<MovePathIndex>,
 419         _call_bb: mir::BasicBlock,
 420         _dest_bb: mir::BasicBlock,
 421         dest_place: &mir::Place<'tcx>,
 422     ) {
 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); });
 428     }
 429 }
 430
 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()
 436     }
 437
 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));
 441         }
 442     }
 443
 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;
 452
 453         debug!("statement {:?} at loc {:?} initializes move_indexes {:?}",
 454                stmt, location, &init_loc_map[location]);
 455         trans.gen_all(&init_loc_map[location]);
 456
 457         match stmt.kind {
 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]);
 465             }
 466             _ => {}
 467         }
 468     }
 469
 470     fn terminator_effect(&self,
 471                          trans: &mut GenKillSet<Self::Idx>,
 472                          location: Location)
 473     {
 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]);
 479         trans.gen_all(
 480             init_loc_map[location].iter().filter(|init_index| {
 481                 move_data.inits[**init_index].kind != InitKind::NonPanicPathOnly
 482             })
 483         );
 484     }
 485
 486     fn propagate_call_return(
 487         &self,
 488         in_out: &mut BitSet<InitIndex>,
 489         call_bb: mir::BasicBlock,
 490         _dest_bb: mir::BasicBlock,
 491         _dest_place: &mir::Place<'tcx>,
 492     ) {
 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;
 496
 497         let call_loc = Location {
 498             block: call_bb,
 499             statement_index: self.body[call_bb].statements.len(),
 500         };
 501         for init_index in &init_loc_map[call_loc] {
 502             assert!(init_index.index() < bits_per_block);
 503             in_out.insert(*init_index);
 504         }
 505     }
 506 }
 507
 508 impl<'a, 'tcx> BottomValue for MaybeInitializedPlaces<'a, 'tcx> {
 509     /// bottom = uninitialized
 510     const BOTTOM_VALUE: bool = false;
 511 }
 512
 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;
 516 }
 517
 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;
 521 }
 522
 523 impl<'a, 'tcx> BottomValue for EverInitializedPlaces<'a, 'tcx> {
 524     /// bottom = no initialized variables by default
 525     const BOTTOM_VALUE: bool = false;
 526 }