src/librustc_mir/dataflow/impls/mod.rs

   1 // Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Dataflow analyses are built upon some interpretation of the
  12 //! bitvectors attached to each basic block, represented via a
  13 //! zero-sized structure.
  14
  15 use rustc::ty::TyCtxt;
  16 use rustc::mir::{self, Mir, Location};
  17 use rustc_data_structures::bitslice::{BitwiseOperator};
  18 use rustc_data_structures::indexed_set::{IdxSet};
  19 use rustc_data_structures::indexed_vec::Idx;
  20
  21 use super::MoveDataParamEnv;
  22 use util::elaborate_drops::DropFlagState;
  23
  24 use super::move_paths::{HasMoveData, MoveData, MoveOutIndex, MovePathIndex, InitIndex};
  25 use super::move_paths::{LookupResult, InitKind};
  26 use super::{BitDenotation, BlockSets, InitialFlow};
  27
  28 use super::drop_flag_effects_for_function_entry;
  29 use super::drop_flag_effects_for_location;
  30 use super::{on_lookup_result_bits, for_location_inits};
  31
  32 mod storage_liveness;
  33
  34 pub use self::storage_liveness::*;
  35
  36 #[allow(dead_code)]
  37 pub(super) mod borrows;
  38
  39 /// `MaybeInitializedLvals` tracks all l-values that might be
  40 /// initialized upon reaching a particular point in the control flow
  41 /// for a function.
  42 ///
  43 /// For example, in code like the following, we have corresponding
  44 /// dataflow information shown in the right-hand comments.
  45 ///
  46 /// ```rust
  47 /// struct S;
  48 /// fn foo(pred: bool) {                       // maybe-init:
  49 ///                                            // {}
  50 ///     let a = S; let b = S; let c; let d;    // {a, b}
  51 ///
  52 ///     if pred {
  53 ///         drop(a);                           // {   b}
  54 ///         b = S;                             // {   b}
  55 ///
  56 ///     } else {
  57 ///         drop(b);                           // {a}
  58 ///         d = S;                             // {a,       d}
  59 ///
  60 ///     }                                      // {a, b,    d}
  61 ///
  62 ///     c = S;                                 // {a, b, c, d}
  63 /// }
  64 /// ```
  65 ///
  66 /// To determine whether an l-value *must* be initialized at a
  67 /// particular control-flow point, one can take the set-difference
  68 /// between this data and the data from `MaybeUninitializedLvals` at the
  69 /// corresponding control-flow point.
  70 ///
  71 /// Similarly, at a given `drop` statement, the set-intersection
  72 /// between this data and `MaybeUninitializedLvals` yields the set of
  73 /// l-values that would require a dynamic drop-flag at that statement.
  74 pub struct MaybeInitializedLvals<'a, 'gcx: 'tcx, 'tcx: 'a> {
  75     tcx: TyCtxt<'a, 'gcx, 'tcx>,
  76     mir: &'a Mir<'tcx>,
  77     mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>,
  78 }
  79
  80 impl<'a, 'gcx: 'tcx, 'tcx> MaybeInitializedLvals<'a, 'gcx, 'tcx> {
  81     pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
  82                mir: &'a Mir<'tcx>,
  83                mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>)
  84                -> Self
  85     {
  86         MaybeInitializedLvals { tcx: tcx, mir: mir, mdpe: mdpe }
  87     }
  88 }
  89
  90 impl<'a, 'gcx, 'tcx> HasMoveData<'tcx> for MaybeInitializedLvals<'a, 'gcx, 'tcx> {
  91     fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
  92 }
  93
  94 /// `MaybeUninitializedLvals` tracks all l-values that might be
  95 /// uninitialized upon reaching a particular point in the control flow
  96 /// for a function.
  97 ///
  98 /// For example, in code like the following, we have corresponding
  99 /// dataflow information shown in the right-hand comments.
 100 ///
 101 /// ```rust
 102 /// struct S;
 103 /// fn foo(pred: bool) {                       // maybe-uninit:
 104 ///                                            // {a, b, c, d}
 105 ///     let a = S; let b = S; let c; let d;    // {      c, d}
 106 ///
 107 ///     if pred {
 108 ///         drop(a);                           // {a,    c, d}
 109 ///         b = S;                             // {a,    c, d}
 110 ///
 111 ///     } else {
 112 ///         drop(b);                           // {   b, c, d}
 113 ///         d = S;                             // {   b, c   }
 114 ///
 115 ///     }                                      // {a, b, c, d}
 116 ///
 117 ///     c = S;                                 // {a, b,    d}
 118 /// }
 119 /// ```
 120 ///
 121 /// To determine whether an l-value *must* be uninitialized at a
 122 /// particular control-flow point, one can take the set-difference
 123 /// between this data and the data from `MaybeInitializedLvals` at the
 124 /// corresponding control-flow point.
 125 ///
 126 /// Similarly, at a given `drop` statement, the set-intersection
 127 /// between this data and `MaybeInitializedLvals` yields the set of
 128 /// l-values that would require a dynamic drop-flag at that statement.
 129 pub struct MaybeUninitializedLvals<'a, 'gcx: 'tcx, 'tcx: 'a> {
 130     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 131     mir: &'a Mir<'tcx>,
 132     mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>,
 133 }
 134
 135 impl<'a, 'gcx, 'tcx> MaybeUninitializedLvals<'a, 'gcx, 'tcx> {
 136     pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 137                mir: &'a Mir<'tcx>,
 138                mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>)
 139                -> Self
 140     {
 141         MaybeUninitializedLvals { tcx: tcx, mir: mir, mdpe: mdpe }
 142     }
 143 }
 144
 145 impl<'a, 'gcx, 'tcx> HasMoveData<'tcx> for MaybeUninitializedLvals<'a, 'gcx, 'tcx> {
 146     fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
 147 }
 148
 149 /// `DefinitelyInitializedLvals` tracks all l-values that are definitely
 150 /// initialized upon reaching a particular point in the control flow
 151 /// for a function.
 152 ///
 153 /// FIXME: Note that once flow-analysis is complete, this should be
 154 /// the set-complement of MaybeUninitializedLvals; thus we can get rid
 155 /// of one or the other of these two. I'm inclined to get rid of
 156 /// MaybeUninitializedLvals, simply because the sets will tend to be
 157 /// smaller in this analysis and thus easier for humans to process
 158 /// when debugging.
 159 ///
 160 /// For example, in code like the following, we have corresponding
 161 /// dataflow information shown in the right-hand comments.
 162 ///
 163 /// ```rust
 164 /// struct S;
 165 /// fn foo(pred: bool) {                       // definite-init:
 166 ///                                            // {          }
 167 ///     let a = S; let b = S; let c; let d;    // {a, b      }
 168 ///
 169 ///     if pred {
 170 ///         drop(a);                           // {   b,     }
 171 ///         b = S;                             // {   b,     }
 172 ///
 173 ///     } else {
 174 ///         drop(b);                           // {a,        }
 175 ///         d = S;                             // {a,       d}
 176 ///
 177 ///     }                                      // {          }
 178 ///
 179 ///     c = S;                                 // {       c  }
 180 /// }
 181 /// ```
 182 ///
 183 /// To determine whether an l-value *may* be uninitialized at a
 184 /// particular control-flow point, one can take the set-complement
 185 /// of this data.
 186 ///
 187 /// Similarly, at a given `drop` statement, the set-difference between
 188 /// this data and `MaybeInitializedLvals` yields the set of l-values
 189 /// that would require a dynamic drop-flag at that statement.
 190 pub struct DefinitelyInitializedLvals<'a, 'gcx: 'tcx, 'tcx: 'a> {
 191     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 192     mir: &'a Mir<'tcx>,
 193     mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>,
 194 }
 195
 196 impl<'a, 'gcx, 'tcx: 'a> DefinitelyInitializedLvals<'a, 'gcx, 'tcx> {
 197     pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 198                mir: &'a Mir<'tcx>,
 199                mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>)
 200                -> Self
 201     {
 202         DefinitelyInitializedLvals { tcx: tcx, mir: mir, mdpe: mdpe }
 203     }
 204 }
 205
 206 impl<'a, 'gcx, 'tcx: 'a> HasMoveData<'tcx> for DefinitelyInitializedLvals<'a, 'gcx, 'tcx> {
 207     fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
 208 }
 209
 210 /// `MovingOutStatements` tracks the statements that perform moves out
 211 /// of particular l-values. More precisely, it tracks whether the
 212 /// *effect* of such moves (namely, the uninitialization of the
 213 /// l-value in question) can reach some point in the control-flow of
 214 /// the function, or if that effect is "killed" by some intervening
 215 /// operation reinitializing that l-value.
 216 ///
 217 /// The resulting dataflow is a more enriched version of
 218 /// `MaybeUninitializedLvals`. Both structures on their own only tell
 219 /// you if an l-value *might* be uninitialized at a given point in the
 220 /// control flow. But `MovingOutStatements` also includes the added
 221 /// data of *which* particular statement causing the deinitialization
 222 /// that the borrow checker's error message may need to report.
 223 #[allow(dead_code)]
 224 pub struct MovingOutStatements<'a, 'gcx: 'tcx, 'tcx: 'a> {
 225     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 226     mir: &'a Mir<'tcx>,
 227     mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>,
 228 }
 229
 230 impl<'a, 'gcx: 'tcx, 'tcx: 'a> MovingOutStatements<'a, 'gcx, 'tcx> {
 231     pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 232                mir: &'a Mir<'tcx>,
 233                mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>)
 234                -> Self
 235     {
 236         MovingOutStatements { tcx: tcx, mir: mir, mdpe: mdpe }
 237     }
 238 }
 239
 240 impl<'a, 'gcx, 'tcx> HasMoveData<'tcx> for MovingOutStatements<'a, 'gcx, 'tcx> {
 241     fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
 242 }
 243
 244 /// `EverInitializedLvals` tracks all l-values that might have ever been
 245 /// initialized upon reaching a particular point in the control flow
 246 /// for a function, without an intervening `Storage Dead`.
 247 ///
 248 /// This dataflow is used to determine if an immutable local variable may
 249 /// be assigned to.
 250 ///
 251 /// For example, in code like the following, we have corresponding
 252 /// dataflow information shown in the right-hand comments.
 253 ///
 254 /// ```rust
 255 /// struct S;
 256 /// fn foo(pred: bool) {                       // ever-init:
 257 ///                                            // {          }
 258 ///     let a = S; let b = S; let c; let d;    // {a, b      }
 259 ///
 260 ///     if pred {
 261 ///         drop(a);                           // {a, b,     }
 262 ///         b = S;                             // {a, b,     }
 263 ///
 264 ///     } else {
 265 ///         drop(b);                           // {a, b,      }
 266 ///         d = S;                             // {a, b,    d }
 267 ///
 268 ///     }                                      // {a, b,    d }
 269 ///
 270 ///     c = S;                                 // {a, b, c, d }
 271 /// }
 272 /// ```
 273 pub struct EverInitializedLvals<'a, 'gcx: 'tcx, 'tcx: 'a> {
 274     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 275     mir: &'a Mir<'tcx>,
 276     mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>,
 277 }
 278
 279 impl<'a, 'gcx: 'tcx, 'tcx: 'a> EverInitializedLvals<'a, 'gcx, 'tcx> {
 280     pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 281                mir: &'a Mir<'tcx>,
 282                mdpe: &'a MoveDataParamEnv<'gcx, 'tcx>)
 283                -> Self
 284     {
 285         EverInitializedLvals { tcx: tcx, mir: mir, mdpe: mdpe }
 286     }
 287 }
 288
 289 impl<'a, 'gcx, 'tcx> HasMoveData<'tcx> for EverInitializedLvals<'a, 'gcx, 'tcx> {
 290     fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
 291 }
 292
 293
 294 impl<'a, 'gcx, 'tcx> MaybeInitializedLvals<'a, 'gcx, 'tcx> {
 295     fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex,
 296                    state: DropFlagState)
 297     {
 298         match state {
 299             DropFlagState::Absent => sets.kill(&path),
 300             DropFlagState::Present => sets.gen(&path),
 301         }
 302     }
 303 }
 304
 305 impl<'a, 'gcx, 'tcx> MaybeUninitializedLvals<'a, 'gcx, 'tcx> {
 306     fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex,
 307                    state: DropFlagState)
 308     {
 309         match state {
 310             DropFlagState::Absent => sets.gen(&path),
 311             DropFlagState::Present => sets.kill(&path),
 312         }
 313     }
 314 }
 315
 316 impl<'a, 'gcx, 'tcx> DefinitelyInitializedLvals<'a, 'gcx, 'tcx> {
 317     fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex,
 318                    state: DropFlagState)
 319     {
 320         match state {
 321             DropFlagState::Absent => sets.kill(&path),
 322             DropFlagState::Present => sets.gen(&path),
 323         }
 324     }
 325 }
 326
 327 impl<'a, 'gcx, 'tcx> BitDenotation for MaybeInitializedLvals<'a, 'gcx, 'tcx> {
 328     type Idx = MovePathIndex;
 329     fn name() -> &'static str { "maybe_init" }
 330     fn bits_per_block(&self) -> usize {
 331         self.move_data().move_paths.len()
 332     }
 333
 334     fn start_block_effect(&self, entry_set: &mut IdxSet<MovePathIndex>) {
 335         drop_flag_effects_for_function_entry(
 336             self.tcx, self.mir, self.mdpe,
 337             |path, s| {
 338                 assert!(s == DropFlagState::Present);
 339                 entry_set.add(&path);
 340             });
 341     }
 342
 343     fn statement_effect(&self,
 344                         sets: &mut BlockSets<MovePathIndex>,
 345                         location: Location)
 346     {
 347         drop_flag_effects_for_location(
 348             self.tcx, self.mir, self.mdpe,
 349             location,
 350             |path, s| Self::update_bits(sets, path, s)
 351         )
 352     }
 353
 354     fn terminator_effect(&self,
 355                          sets: &mut BlockSets<MovePathIndex>,
 356                          location: Location)
 357     {
 358         drop_flag_effects_for_location(
 359             self.tcx, self.mir, self.mdpe,
 360             location,
 361             |path, s| Self::update_bits(sets, path, s)
 362         )
 363     }
 364
 365     fn propagate_call_return(&self,
 366                              in_out: &mut IdxSet<MovePathIndex>,
 367                              _call_bb: mir::BasicBlock,
 368                              _dest_bb: mir::BasicBlock,
 369                              dest_place: &mir::Place) {
 370         // when a call returns successfully, that means we need to set
 371         // the bits for that dest_place to 1 (initialized).
 372         on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
 373                               self.move_data().rev_lookup.find(dest_place),
 374                               |mpi| { in_out.add(&mpi); });
 375     }
 376 }
 377
 378 impl<'a, 'gcx, 'tcx> BitDenotation for MaybeUninitializedLvals<'a, 'gcx, 'tcx> {
 379     type Idx = MovePathIndex;
 380     fn name() -> &'static str { "maybe_uninit" }
 381     fn bits_per_block(&self) -> usize {
 382         self.move_data().move_paths.len()
 383     }
 384
 385     // sets on_entry bits for Arg places
 386     fn start_block_effect(&self, entry_set: &mut IdxSet<MovePathIndex>) {
 387         // set all bits to 1 (uninit) before gathering counterevidence
 388         for e in entry_set.words_mut() { *e = !0; }
 389
 390         drop_flag_effects_for_function_entry(
 391             self.tcx, self.mir, self.mdpe,
 392             |path, s| {
 393                 assert!(s == DropFlagState::Present);
 394                 entry_set.remove(&path);
 395             });
 396     }
 397
 398     fn statement_effect(&self,
 399                         sets: &mut BlockSets<MovePathIndex>,
 400                         location: Location)
 401     {
 402         drop_flag_effects_for_location(
 403             self.tcx, self.mir, self.mdpe,
 404             location,
 405             |path, s| Self::update_bits(sets, path, s)
 406         )
 407     }
 408
 409     fn terminator_effect(&self,
 410                          sets: &mut BlockSets<MovePathIndex>,
 411                          location: Location)
 412     {
 413         drop_flag_effects_for_location(
 414             self.tcx, self.mir, self.mdpe,
 415             location,
 416             |path, s| Self::update_bits(sets, path, s)
 417         )
 418     }
 419
 420     fn propagate_call_return(&self,
 421                              in_out: &mut IdxSet<MovePathIndex>,
 422                              _call_bb: mir::BasicBlock,
 423                              _dest_bb: mir::BasicBlock,
 424                              dest_place: &mir::Place) {
 425         // when a call returns successfully, that means we need to set
 426         // the bits for that dest_place to 0 (initialized).
 427         on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
 428                               self.move_data().rev_lookup.find(dest_place),
 429                               |mpi| { in_out.remove(&mpi); });
 430     }
 431 }
 432
 433 impl<'a, 'gcx, 'tcx> BitDenotation for DefinitelyInitializedLvals<'a, 'gcx, 'tcx> {
 434     type Idx = MovePathIndex;
 435     fn name() -> &'static str { "definite_init" }
 436     fn bits_per_block(&self) -> usize {
 437         self.move_data().move_paths.len()
 438     }
 439
 440     // sets on_entry bits for Arg places
 441     fn start_block_effect(&self, entry_set: &mut IdxSet<MovePathIndex>) {
 442         for e in entry_set.words_mut() { *e = 0; }
 443
 444         drop_flag_effects_for_function_entry(
 445             self.tcx, self.mir, self.mdpe,
 446             |path, s| {
 447                 assert!(s == DropFlagState::Present);
 448                 entry_set.add(&path);
 449             });
 450     }
 451
 452     fn statement_effect(&self,
 453                         sets: &mut BlockSets<MovePathIndex>,
 454                         location: Location)
 455     {
 456         drop_flag_effects_for_location(
 457             self.tcx, self.mir, self.mdpe,
 458             location,
 459             |path, s| Self::update_bits(sets, path, s)
 460         )
 461     }
 462
 463     fn terminator_effect(&self,
 464                          sets: &mut BlockSets<MovePathIndex>,
 465                          location: Location)
 466     {
 467         drop_flag_effects_for_location(
 468             self.tcx, self.mir, self.mdpe,
 469             location,
 470             |path, s| Self::update_bits(sets, path, s)
 471         )
 472     }
 473
 474     fn propagate_call_return(&self,
 475                              in_out: &mut IdxSet<MovePathIndex>,
 476                              _call_bb: mir::BasicBlock,
 477                              _dest_bb: mir::BasicBlock,
 478                              dest_place: &mir::Place) {
 479         // when a call returns successfully, that means we need to set
 480         // the bits for that dest_place to 1 (initialized).
 481         on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
 482                               self.move_data().rev_lookup.find(dest_place),
 483                               |mpi| { in_out.add(&mpi); });
 484     }
 485 }
 486
 487 impl<'a, 'gcx, 'tcx> BitDenotation for MovingOutStatements<'a, 'gcx, 'tcx> {
 488     type Idx = MoveOutIndex;
 489     fn name() -> &'static str { "moving_out" }
 490     fn bits_per_block(&self) -> usize {
 491         self.move_data().moves.len()
 492     }
 493
 494     fn start_block_effect(&self, _sets: &mut IdxSet<MoveOutIndex>) {
 495         // no move-statements have been executed prior to function
 496         // execution, so this method has no effect on `_sets`.
 497     }
 498
 499     fn statement_effect(&self,
 500                         sets: &mut BlockSets<MoveOutIndex>,
 501                         location: Location) {
 502         let (tcx, mir, move_data) = (self.tcx, self.mir, self.move_data());
 503         let stmt = &mir[location.block].statements[location.statement_index];
 504         let loc_map = &move_data.loc_map;
 505         let path_map = &move_data.path_map;
 506
 507         match stmt.kind {
 508             // this analysis only tries to find moves explicitly
 509             // written by the user, so we ignore the move-outs
 510             // created by `StorageDead` and at the beginning
 511             // of a function.
 512             mir::StatementKind::StorageDead(_) => {}
 513             _ => {
 514                 debug!("stmt {:?} at loc {:?} moves out of move_indexes {:?}",
 515                        stmt, location, &loc_map[location]);
 516                 // Every path deinitialized by a *particular move*
 517                 // has corresponding bit, "gen'ed" (i.e. set)
 518                 // here, in dataflow vector
 519                 sets.gen_all_and_assert_dead(&loc_map[location]);
 520             }
 521         }
 522
 523         for_location_inits(tcx, mir, move_data, location,
 524                            |mpi| sets.kill_all(&path_map[mpi]));
 525     }
 526
 527     fn terminator_effect(&self,
 528                          sets: &mut BlockSets<MoveOutIndex>,
 529                          location: Location)
 530     {
 531         let (tcx, mir, move_data) = (self.tcx, self.mir, self.move_data());
 532         let term = mir[location.block].terminator();
 533         let loc_map = &move_data.loc_map;
 534         let path_map = &move_data.path_map;
 535
 536         debug!("terminator {:?} at loc {:?} moves out of move_indexes {:?}",
 537                term, location, &loc_map[location]);
 538         sets.gen_all_and_assert_dead(&loc_map[location]);
 539
 540         for_location_inits(tcx, mir, move_data, location,
 541                            |mpi| sets.kill_all(&path_map[mpi]));
 542     }
 543
 544     fn propagate_call_return(&self,
 545                              in_out: &mut IdxSet<MoveOutIndex>,
 546                              _call_bb: mir::BasicBlock,
 547                              _dest_bb: mir::BasicBlock,
 548                              dest_place: &mir::Place) {
 549         let move_data = self.move_data();
 550         let bits_per_block = self.bits_per_block();
 551
 552         let path_map = &move_data.path_map;
 553         on_lookup_result_bits(self.tcx,
 554                               self.mir,
 555                               move_data,
 556                               move_data.rev_lookup.find(dest_place),
 557                               |mpi| for moi in &path_map[mpi] {
 558                                   assert!(moi.index() < bits_per_block);
 559                                   in_out.remove(&moi);
 560                               });
 561     }
 562 }
 563
 564 impl<'a, 'gcx, 'tcx> BitDenotation for EverInitializedLvals<'a, 'gcx, 'tcx> {
 565     type Idx = InitIndex;
 566     fn name() -> &'static str { "ever_init" }
 567     fn bits_per_block(&self) -> usize {
 568         self.move_data().inits.len()
 569     }
 570
 571     fn start_block_effect(&self, entry_set: &mut IdxSet<InitIndex>) {
 572         for arg_init in 0..self.mir.arg_count {
 573             entry_set.add(&InitIndex::new(arg_init));
 574         }
 575     }
 576
 577     fn statement_effect(&self,
 578                         sets: &mut BlockSets<InitIndex>,
 579                         location: Location) {
 580         let (_, mir, move_data) = (self.tcx, self.mir, self.move_data());
 581         let stmt = &mir[location.block].statements[location.statement_index];
 582         let init_path_map = &move_data.init_path_map;
 583         let init_loc_map = &move_data.init_loc_map;
 584         let rev_lookup = &move_data.rev_lookup;
 585
 586         debug!("statement {:?} at loc {:?} initializes move_indexes {:?}",
 587                stmt, location, &init_loc_map[location]);
 588         sets.gen_all(&init_loc_map[location]);
 589
 590         match stmt.kind {
 591             mir::StatementKind::StorageDead(local) |
 592             mir::StatementKind::StorageLive(local) => {
 593                 // End inits for StorageDead and StorageLive, so that an immutable
 594                 // variable can be reinitialized on the next iteration of the loop.
 595                 //
 596                 // FIXME(#46525): We *need* to do this for StorageLive as well as
 597                 // StorageDead, because lifetimes of match bindings with guards are
 598                 // weird - i.e. this code
 599                 //
 600                 // ```
 601                 //     fn main() {
 602                 //         match 0 {
 603                 //             a | a
 604                 //             if { println!("a={}", a); false } => {}
 605                 //             _ => {}
 606                 //         }
 607                 //     }
 608                 // ```
 609                 //
 610                 // runs the guard twice, using the same binding for `a`, and only
 611                 // storagedeads after everything ends, so if we don't regard the
 612                 // storagelive as killing storage, we would have a multiple assignment
 613                 // to immutable data error.
 614                 if let LookupResult::Exact(mpi) = rev_lookup.find(&mir::Place::Local(local)) {
 615                     debug!("stmt {:?} at loc {:?} clears the ever initialized status of {:?}",
 616                            stmt, location, &init_path_map[mpi]);
 617                     sets.kill_all(&init_path_map[mpi]);
 618                 }
 619             }
 620             _ => {}
 621         }
 622     }
 623
 624     fn terminator_effect(&self,
 625                          sets: &mut BlockSets<InitIndex>,
 626                          location: Location)
 627     {
 628         let (mir, move_data) = (self.mir, self.move_data());
 629         let term = mir[location.block].terminator();
 630         let init_loc_map = &move_data.init_loc_map;
 631         debug!("terminator {:?} at loc {:?} initializes move_indexes {:?}",
 632                term, location, &init_loc_map[location]);
 633         sets.gen_all(
 634             init_loc_map[location].iter().filter(|init_index| {
 635                 move_data.inits[**init_index].kind != InitKind::NonPanicPathOnly
 636             })
 637         );
 638     }
 639
 640     fn propagate_call_return(&self,
 641                              in_out: &mut IdxSet<InitIndex>,
 642                              call_bb: mir::BasicBlock,
 643                              _dest_bb: mir::BasicBlock,
 644                              _dest_place: &mir::Place) {
 645         let move_data = self.move_data();
 646         let bits_per_block = self.bits_per_block();
 647         let init_loc_map = &move_data.init_loc_map;
 648
 649         let call_loc = Location {
 650             block: call_bb,
 651             statement_index: self.mir[call_bb].statements.len(),
 652         };
 653         for init_index in &init_loc_map[call_loc] {
 654             assert!(init_index.index() < bits_per_block);
 655             in_out.add(init_index);
 656         }
 657     }
 658 }
 659
 660 impl<'a, 'gcx, 'tcx> BitwiseOperator for MaybeInitializedLvals<'a, 'gcx, 'tcx> {
 661     #[inline]
 662     fn join(&self, pred1: usize, pred2: usize) -> usize {
 663         pred1 | pred2 // "maybe" means we union effects of both preds
 664     }
 665 }
 666
 667 impl<'a, 'gcx, 'tcx> BitwiseOperator for MaybeUninitializedLvals<'a, 'gcx, 'tcx> {
 668     #[inline]
 669     fn join(&self, pred1: usize, pred2: usize) -> usize {
 670         pred1 | pred2 // "maybe" means we union effects of both preds
 671     }
 672 }
 673
 674 impl<'a, 'gcx, 'tcx> BitwiseOperator for DefinitelyInitializedLvals<'a, 'gcx, 'tcx> {
 675     #[inline]
 676     fn join(&self, pred1: usize, pred2: usize) -> usize {
 677         pred1 & pred2 // "definitely" means we intersect effects of both preds
 678     }
 679 }
 680
 681 impl<'a, 'gcx, 'tcx> BitwiseOperator for MovingOutStatements<'a, 'gcx, 'tcx> {
 682     #[inline]
 683     fn join(&self, pred1: usize, pred2: usize) -> usize {
 684         pred1 | pred2 // moves from both preds are in scope
 685     }
 686 }
 687
 688 impl<'a, 'gcx, 'tcx> BitwiseOperator for EverInitializedLvals<'a, 'gcx, 'tcx> {
 689     #[inline]
 690     fn join(&self, pred1: usize, pred2: usize) -> usize {
 691         pred1 | pred2 // inits from both preds are in scope
 692     }
 693 }
 694
 695 // The way that dataflow fixed point iteration works, you want to
 696 // start at bottom and work your way to a fixed point. Control-flow
 697 // merges will apply the `join` operator to each block entry's current
 698 // state (which starts at that bottom value).
 699 //
 700 // This means, for propagation across the graph, that you either want
 701 // to start at all-zeroes and then use Union as your merge when
 702 // propagating, or you start at all-ones and then use Intersect as
 703 // your merge when propagating.
 704
 705 impl<'a, 'gcx, 'tcx> InitialFlow for MaybeInitializedLvals<'a, 'gcx, 'tcx> {
 706     #[inline]
 707     fn bottom_value() -> bool {
 708         false // bottom = uninitialized
 709     }
 710 }
 711
 712 impl<'a, 'gcx, 'tcx> InitialFlow for MaybeUninitializedLvals<'a, 'gcx, 'tcx> {
 713     #[inline]
 714     fn bottom_value() -> bool {
 715         false // bottom = initialized (start_block_effect counters this at outset)
 716     }
 717 }
 718
 719 impl<'a, 'gcx, 'tcx> InitialFlow for DefinitelyInitializedLvals<'a, 'gcx, 'tcx> {
 720     #[inline]
 721     fn bottom_value() -> bool {
 722         true // bottom = initialized (start_block_effect counters this at outset)
 723     }
 724 }
 725
 726 impl<'a, 'gcx, 'tcx> InitialFlow for MovingOutStatements<'a, 'gcx, 'tcx> {
 727     #[inline]
 728     fn bottom_value() -> bool {
 729         false // bottom = no loans in scope by default
 730     }
 731 }
 732
 733 impl<'a, 'gcx, 'tcx> InitialFlow for EverInitializedLvals<'a, 'gcx, 'tcx> {
 734     #[inline]
 735     fn bottom_value() -> bool {
 736         false // bottom = no initialized variables by default
 737     }
 738 }