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
  20 use super::MoveDataParamEnv;
  21 use util::elaborate_drops::DropFlagState;
  22
  23 use super::move_paths::{HasMoveData, MoveData, MovePathIndex};
  24 use super::{BitDenotation, BlockSets, DataflowOperator};
  25
  26 use super::drop_flag_effects_for_function_entry;
  27 use super::drop_flag_effects_for_location;
  28 use super::on_lookup_result_bits;
  29
  30 mod storage_liveness;
  31
  32 pub use self::storage_liveness::*;
  33
  34 #[allow(dead_code)]
  35 pub(super) mod borrows;
  36
  37 /// `MaybeInitializedLvals` tracks all l-values that might be
  38 /// initialized upon reaching a particular point in the control flow
  39 /// for a function.
  40 ///
  41 /// For example, in code like the following, we have corresponding
  42 /// dataflow information shown in the right-hand comments.
  43 ///
  44 /// ```rust
  45 /// struct S;
  46 /// fn foo(pred: bool) {                       // maybe-init:
  47 ///                                            // {}
  48 ///     let a = S; let b = S; let c; let d;    // {a, b}
  49 ///
  50 ///     if pred {
  51 ///         drop(a);                           // {   b}
  52 ///         b = S;                             // {   b}
  53 ///
  54 ///     } else {
  55 ///         drop(b);                           // {a}
  56 ///         d = S;                             // {a,       d}
  57 ///
  58 ///     }                                      // {a, b,    d}
  59 ///
  60 ///     c = S;                                 // {a, b, c, d}
  61 /// }
  62 /// ```
  63 ///
  64 /// To determine whether an l-value *must* be initialized at a
  65 /// particular control-flow point, one can take the set-difference
  66 /// between this data and the data from `MaybeUninitializedLvals` at the
  67 /// corresponding control-flow point.
  68 ///
  69 /// Similarly, at a given `drop` statement, the set-intersection
  70 /// between this data and `MaybeUninitializedLvals` yields the set of
  71 /// l-values that would require a dynamic drop-flag at that statement.
  72 pub struct MaybeInitializedLvals<'a, 'tcx: 'a> {
  73     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  74     mir: &'a Mir<'tcx>,
  75     mdpe: &'a MoveDataParamEnv<'tcx>,
  76 }
  77
  78 impl<'a, 'tcx: 'a> MaybeInitializedLvals<'a, 'tcx> {
  79     pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>,
  80                mir: &'a Mir<'tcx>,
  81                mdpe: &'a MoveDataParamEnv<'tcx>)
  82                -> Self
  83     {
  84         MaybeInitializedLvals { tcx: tcx, mir: mir, mdpe: mdpe }
  85     }
  86 }
  87
  88 impl<'a, 'tcx: 'a> HasMoveData<'tcx> for MaybeInitializedLvals<'a, 'tcx> {
  89     fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
  90 }
  91
  92 /// `MaybeUninitializedLvals` tracks all l-values that might be
  93 /// uninitialized upon reaching a particular point in the control flow
  94 /// for a function.
  95 ///
  96 /// For example, in code like the following, we have corresponding
  97 /// dataflow information shown in the right-hand comments.
  98 ///
  99 /// ```rust
 100 /// struct S;
 101 /// fn foo(pred: bool) {                       // maybe-uninit:
 102 ///                                            // {a, b, c, d}
 103 ///     let a = S; let b = S; let c; let d;    // {      c, d}
 104 ///
 105 ///     if pred {
 106 ///         drop(a);                           // {a,    c, d}
 107 ///         b = S;                             // {a,    c, d}
 108 ///
 109 ///     } else {
 110 ///         drop(b);                           // {   b, c, d}
 111 ///         d = S;                             // {   b, c   }
 112 ///
 113 ///     }                                      // {a, b, c, d}
 114 ///
 115 ///     c = S;                                 // {a, b,    d}
 116 /// }
 117 /// ```
 118 ///
 119 /// To determine whether an l-value *must* be uninitialized at a
 120 /// particular control-flow point, one can take the set-difference
 121 /// between this data and the data from `MaybeInitializedLvals` at the
 122 /// corresponding control-flow point.
 123 ///
 124 /// Similarly, at a given `drop` statement, the set-intersection
 125 /// between this data and `MaybeInitializedLvals` yields the set of
 126 /// l-values that would require a dynamic drop-flag at that statement.
 127 pub struct MaybeUninitializedLvals<'a, 'tcx: 'a> {
 128     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 129     mir: &'a Mir<'tcx>,
 130     mdpe: &'a MoveDataParamEnv<'tcx>,
 131 }
 132
 133 impl<'a, 'tcx: 'a> MaybeUninitializedLvals<'a, 'tcx> {
 134     pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 135                mir: &'a Mir<'tcx>,
 136                mdpe: &'a MoveDataParamEnv<'tcx>)
 137                -> Self
 138     {
 139         MaybeUninitializedLvals { tcx: tcx, mir: mir, mdpe: mdpe }
 140     }
 141 }
 142
 143 impl<'a, 'tcx: 'a> HasMoveData<'tcx> for MaybeUninitializedLvals<'a, 'tcx> {
 144     fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
 145 }
 146
 147 /// `DefinitelyInitializedLvals` tracks all l-values that are definitely
 148 /// initialized upon reaching a particular point in the control flow
 149 /// for a function.
 150 ///
 151 /// FIXME: Note that once flow-analysis is complete, this should be
 152 /// the set-complement of MaybeUninitializedLvals; thus we can get rid
 153 /// of one or the other of these two. I'm inclined to get rid of
 154 /// MaybeUninitializedLvals, simply because the sets will tend to be
 155 /// smaller in this analysis and thus easier for humans to process
 156 /// when debugging.
 157 ///
 158 /// For example, in code like the following, we have corresponding
 159 /// dataflow information shown in the right-hand comments.
 160 ///
 161 /// ```rust
 162 /// struct S;
 163 /// fn foo(pred: bool) {                       // definite-init:
 164 ///                                            // {          }
 165 ///     let a = S; let b = S; let c; let d;    // {a, b      }
 166 ///
 167 ///     if pred {
 168 ///         drop(a);                           // {   b,     }
 169 ///         b = S;                             // {   b,     }
 170 ///
 171 ///     } else {
 172 ///         drop(b);                           // {a,        }
 173 ///         d = S;                             // {a,       d}
 174 ///
 175 ///     }                                      // {          }
 176 ///
 177 ///     c = S;                                 // {       c  }
 178 /// }
 179 /// ```
 180 ///
 181 /// To determine whether an l-value *may* be uninitialized at a
 182 /// particular control-flow point, one can take the set-complement
 183 /// of this data.
 184 ///
 185 /// Similarly, at a given `drop` statement, the set-difference between
 186 /// this data and `MaybeInitializedLvals` yields the set of l-values
 187 /// that would require a dynamic drop-flag at that statement.
 188 pub struct DefinitelyInitializedLvals<'a, 'tcx: 'a> {
 189     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 190     mir: &'a Mir<'tcx>,
 191     mdpe: &'a MoveDataParamEnv<'tcx>,
 192 }
 193
 194 impl<'a, 'tcx: 'a> DefinitelyInitializedLvals<'a, 'tcx> {
 195     pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 196                mir: &'a Mir<'tcx>,
 197                mdpe: &'a MoveDataParamEnv<'tcx>)
 198                -> Self
 199     {
 200         DefinitelyInitializedLvals { tcx: tcx, mir: mir, mdpe: mdpe }
 201     }
 202 }
 203
 204 impl<'a, 'tcx: 'a> HasMoveData<'tcx> for DefinitelyInitializedLvals<'a, 'tcx> {
 205     fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
 206 }
 207
 208 impl<'a, 'tcx> MaybeInitializedLvals<'a, 'tcx> {
 209     fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex,
 210                    state: DropFlagState)
 211     {
 212         match state {
 213             DropFlagState::Absent => sets.kill(&path),
 214             DropFlagState::Present => sets.gen(&path),
 215         }
 216     }
 217 }
 218
 219 impl<'a, 'tcx> MaybeUninitializedLvals<'a, 'tcx> {
 220     fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex,
 221                    state: DropFlagState)
 222     {
 223         match state {
 224             DropFlagState::Absent => sets.gen(&path),
 225             DropFlagState::Present => sets.kill(&path),
 226         }
 227     }
 228 }
 229
 230 impl<'a, 'tcx> DefinitelyInitializedLvals<'a, 'tcx> {
 231     fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex,
 232                    state: DropFlagState)
 233     {
 234         match state {
 235             DropFlagState::Absent => sets.kill(&path),
 236             DropFlagState::Present => sets.gen(&path),
 237         }
 238     }
 239 }
 240
 241 impl<'a, 'tcx> BitDenotation for MaybeInitializedLvals<'a, 'tcx> {
 242     type Idx = MovePathIndex;
 243     fn name() -> &'static str { "maybe_init" }
 244     fn bits_per_block(&self) -> usize {
 245         self.move_data().move_paths.len()
 246     }
 247
 248     fn start_block_effect(&self, sets: &mut BlockSets<MovePathIndex>)
 249     {
 250         drop_flag_effects_for_function_entry(
 251             self.tcx, self.mir, self.mdpe,
 252             |path, s| {
 253                 assert!(s == DropFlagState::Present);
 254                 sets.on_entry.add(&path);
 255             });
 256     }
 257
 258     fn statement_effect(&self,
 259                         sets: &mut BlockSets<MovePathIndex>,
 260                         location: Location)
 261     {
 262         drop_flag_effects_for_location(
 263             self.tcx, self.mir, self.mdpe,
 264             location,
 265             |path, s| Self::update_bits(sets, path, s)
 266         )
 267     }
 268
 269     fn terminator_effect(&self,
 270                          sets: &mut BlockSets<MovePathIndex>,
 271                          location: Location)
 272     {
 273         drop_flag_effects_for_location(
 274             self.tcx, self.mir, self.mdpe,
 275             location,
 276             |path, s| Self::update_bits(sets, path, s)
 277         )
 278     }
 279
 280     fn propagate_call_return(&self,
 281                              in_out: &mut IdxSet<MovePathIndex>,
 282                              _call_bb: mir::BasicBlock,
 283                              _dest_bb: mir::BasicBlock,
 284                              dest_lval: &mir::Lvalue) {
 285         // when a call returns successfully, that means we need to set
 286         // the bits for that dest_lval to 1 (initialized).
 287         on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
 288                               self.move_data().rev_lookup.find(dest_lval),
 289                               |mpi| { in_out.add(&mpi); });
 290     }
 291 }
 292
 293 impl<'a, 'tcx> BitDenotation for MaybeUninitializedLvals<'a, 'tcx> {
 294     type Idx = MovePathIndex;
 295     fn name() -> &'static str { "maybe_uninit" }
 296     fn bits_per_block(&self) -> usize {
 297         self.move_data().move_paths.len()
 298     }
 299
 300     // sets on_entry bits for Arg lvalues
 301     fn start_block_effect(&self, sets: &mut BlockSets<MovePathIndex>) {
 302         // set all bits to 1 (uninit) before gathering counterevidence
 303         for e in sets.on_entry.words_mut() { *e = !0; }
 304
 305         drop_flag_effects_for_function_entry(
 306             self.tcx, self.mir, self.mdpe,
 307             |path, s| {
 308                 assert!(s == DropFlagState::Present);
 309                 sets.on_entry.remove(&path);
 310             });
 311     }
 312
 313     fn statement_effect(&self,
 314                         sets: &mut BlockSets<MovePathIndex>,
 315                         location: Location)
 316     {
 317         drop_flag_effects_for_location(
 318             self.tcx, self.mir, self.mdpe,
 319             location,
 320             |path, s| Self::update_bits(sets, path, s)
 321         )
 322     }
 323
 324     fn terminator_effect(&self,
 325                          sets: &mut BlockSets<MovePathIndex>,
 326                          location: Location)
 327     {
 328         drop_flag_effects_for_location(
 329             self.tcx, self.mir, self.mdpe,
 330             location,
 331             |path, s| Self::update_bits(sets, path, s)
 332         )
 333     }
 334
 335     fn propagate_call_return(&self,
 336                              in_out: &mut IdxSet<MovePathIndex>,
 337                              _call_bb: mir::BasicBlock,
 338                              _dest_bb: mir::BasicBlock,
 339                              dest_lval: &mir::Lvalue) {
 340         // when a call returns successfully, that means we need to set
 341         // the bits for that dest_lval to 0 (initialized).
 342         on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
 343                               self.move_data().rev_lookup.find(dest_lval),
 344                               |mpi| { in_out.remove(&mpi); });
 345     }
 346 }
 347
 348 impl<'a, 'tcx> BitDenotation for DefinitelyInitializedLvals<'a, 'tcx> {
 349     type Idx = MovePathIndex;
 350     fn name() -> &'static str { "definite_init" }
 351     fn bits_per_block(&self) -> usize {
 352         self.move_data().move_paths.len()
 353     }
 354
 355     // sets on_entry bits for Arg lvalues
 356     fn start_block_effect(&self, sets: &mut BlockSets<MovePathIndex>) {
 357         for e in sets.on_entry.words_mut() { *e = 0; }
 358
 359         drop_flag_effects_for_function_entry(
 360             self.tcx, self.mir, self.mdpe,
 361             |path, s| {
 362                 assert!(s == DropFlagState::Present);
 363                 sets.on_entry.add(&path);
 364             });
 365     }
 366
 367     fn statement_effect(&self,
 368                         sets: &mut BlockSets<MovePathIndex>,
 369                         location: Location)
 370     {
 371         drop_flag_effects_for_location(
 372             self.tcx, self.mir, self.mdpe,
 373             location,
 374             |path, s| Self::update_bits(sets, path, s)
 375         )
 376     }
 377
 378     fn terminator_effect(&self,
 379                          sets: &mut BlockSets<MovePathIndex>,
 380                          location: Location)
 381     {
 382         drop_flag_effects_for_location(
 383             self.tcx, self.mir, self.mdpe,
 384             location,
 385             |path, s| Self::update_bits(sets, path, s)
 386         )
 387     }
 388
 389     fn propagate_call_return(&self,
 390                              in_out: &mut IdxSet<MovePathIndex>,
 391                              _call_bb: mir::BasicBlock,
 392                              _dest_bb: mir::BasicBlock,
 393                              dest_lval: &mir::Lvalue) {
 394         // when a call returns successfully, that means we need to set
 395         // the bits for that dest_lval to 1 (initialized).
 396         on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
 397                               self.move_data().rev_lookup.find(dest_lval),
 398                               |mpi| { in_out.add(&mpi); });
 399     }
 400 }
 401
 402 impl<'a, 'tcx> BitwiseOperator for MaybeInitializedLvals<'a, 'tcx> {
 403     #[inline]
 404     fn join(&self, pred1: usize, pred2: usize) -> usize {
 405         pred1 | pred2 // "maybe" means we union effects of both preds
 406     }
 407 }
 408
 409 impl<'a, 'tcx> BitwiseOperator for MaybeUninitializedLvals<'a, 'tcx> {
 410     #[inline]
 411     fn join(&self, pred1: usize, pred2: usize) -> usize {
 412         pred1 | pred2 // "maybe" means we union effects of both preds
 413     }
 414 }
 415
 416 impl<'a, 'tcx> BitwiseOperator for DefinitelyInitializedLvals<'a, 'tcx> {
 417     #[inline]
 418     fn join(&self, pred1: usize, pred2: usize) -> usize {
 419         pred1 & pred2 // "definitely" means we intersect effects of both preds
 420     }
 421 }
 422
 423 // The way that dataflow fixed point iteration works, you want to
 424 // start at bottom and work your way to a fixed point. Control-flow
 425 // merges will apply the `join` operator to each block entry's current
 426 // state (which starts at that bottom value).
 427 //
 428 // This means, for propagation across the graph, that you either want
 429 // to start at all-zeroes and then use Union as your merge when
 430 // propagating, or you start at all-ones and then use Intersect as
 431 // your merge when propagating.
 432
 433 impl<'a, 'tcx> DataflowOperator for MaybeInitializedLvals<'a, 'tcx> {
 434     #[inline]
 435     fn bottom_value() -> bool {
 436         false // bottom = uninitialized
 437     }
 438 }
 439
 440 impl<'a, 'tcx> DataflowOperator for MaybeUninitializedLvals<'a, 'tcx> {
 441     #[inline]
 442     fn bottom_value() -> bool {
 443         false // bottom = initialized (start_block_effect counters this at outset)
 444     }
 445 }
 446
 447 impl<'a, 'tcx> DataflowOperator for DefinitelyInitializedLvals<'a, 'tcx> {
 448     #[inline]
 449     fn bottom_value() -> bool {
 450         true // bottom = initialized (start_block_effect counters this at outset)
 451     }
 452 }