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_index::bit_set::BitSet;
   6 use rustc_index::vec::Idx;
   7 use rustc_middle::mir::{self, Body, Location};
   8 use rustc_middle::ty::{self, TyCtxt};
   9 use rustc_target::abi::VariantIdx;
  10
  11 use super::MoveDataParamEnv;
  12
  13 use crate::util::elaborate_drops::DropFlagState;
  14
  15 use super::move_paths::{HasMoveData, InitIndex, InitKind, LookupResult, MoveData, MovePathIndex};
  16 use super::{AnalysisDomain, BottomValue, GenKill, GenKillAnalysis};
  17
  18 use super::drop_flag_effects_for_function_entry;
  19 use super::drop_flag_effects_for_location;
  20 use super::on_lookup_result_bits;
  21 use crate::dataflow::drop_flag_effects;
  22
  23 mod borrowed_locals;
  24 mod storage_liveness;
  25
  26 pub use self::borrowed_locals::*;
  27 pub use self::storage_liveness::*;
  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, body, mdpe }
  75     }
  76 }
  77
  78 impl<'a, 'tcx> HasMoveData<'tcx> for MaybeInitializedPlaces<'a, 'tcx> {
  79     fn move_data(&self) -> &MoveData<'tcx> {
  80         &self.mdpe.move_data
  81     }
  82 }
  83
  84 /// `MaybeUninitializedPlaces` tracks all places that might be
  85 /// uninitialized upon reaching a particular point in the control flow
  86 /// for a function.
  87 ///
  88 /// For example, in code like the following, we have corresponding
  89 /// dataflow information shown in the right-hand comments.
  90 ///
  91 /// ```rust
  92 /// struct S;
  93 /// fn foo(pred: bool) {                       // maybe-uninit:
  94 ///                                            // {a, b, c, d}
  95 ///     let a = S; let b = S; let c; let d;    // {      c, d}
  96 ///
  97 ///     if pred {
  98 ///         drop(a);                           // {a,    c, d}
  99 ///         b = S;                             // {a,    c, d}
 100 ///
 101 ///     } else {
 102 ///         drop(b);                           // {   b, c, d}
 103 ///         d = S;                             // {   b, c   }
 104 ///
 105 ///     }                                      // {a, b, c, d}
 106 ///
 107 ///     c = S;                                 // {a, b,    d}
 108 /// }
 109 /// ```
 110 ///
 111 /// To determine whether a place *must* be uninitialized at a
 112 /// particular control-flow point, one can take the set-difference
 113 /// between this data and the data from `MaybeInitializedPlaces` at the
 114 /// corresponding control-flow point.
 115 ///
 116 /// Similarly, at a given `drop` statement, the set-intersection
 117 /// between this data and `MaybeInitializedPlaces` yields the set of
 118 /// places that would require a dynamic drop-flag at that statement.
 119 pub struct MaybeUninitializedPlaces<'a, 'tcx> {
 120     tcx: TyCtxt<'tcx>,
 121     body: &'a Body<'tcx>,
 122     mdpe: &'a MoveDataParamEnv<'tcx>,
 123 }
 124
 125 impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> {
 126     pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
 127         MaybeUninitializedPlaces { tcx, body, mdpe }
 128     }
 129 }
 130
 131 impl<'a, 'tcx> HasMoveData<'tcx> for MaybeUninitializedPlaces<'a, 'tcx> {
 132     fn move_data(&self) -> &MoveData<'tcx> {
 133         &self.mdpe.move_data
 134     }
 135 }
 136
 137 /// `DefinitelyInitializedPlaces` tracks all places that are definitely
 138 /// initialized upon reaching a particular point in the control flow
 139 /// for a function.
 140 ///
 141 /// For example, in code like the following, we have corresponding
 142 /// dataflow information shown in the right-hand comments.
 143 ///
 144 /// ```rust
 145 /// struct S;
 146 /// fn foo(pred: bool) {                       // definite-init:
 147 ///                                            // {          }
 148 ///     let a = S; let b = S; let c; let d;    // {a, b      }
 149 ///
 150 ///     if pred {
 151 ///         drop(a);                           // {   b,     }
 152 ///         b = S;                             // {   b,     }
 153 ///
 154 ///     } else {
 155 ///         drop(b);                           // {a,        }
 156 ///         d = S;                             // {a,       d}
 157 ///
 158 ///     }                                      // {          }
 159 ///
 160 ///     c = S;                                 // {       c  }
 161 /// }
 162 /// ```
 163 ///
 164 /// To determine whether a place *may* be uninitialized at a
 165 /// particular control-flow point, one can take the set-complement
 166 /// of this data.
 167 ///
 168 /// Similarly, at a given `drop` statement, the set-difference between
 169 /// this data and `MaybeInitializedPlaces` yields the set of places
 170 /// that would require a dynamic drop-flag at that statement.
 171 pub struct DefinitelyInitializedPlaces<'a, 'tcx> {
 172     tcx: TyCtxt<'tcx>,
 173     body: &'a Body<'tcx>,
 174     mdpe: &'a MoveDataParamEnv<'tcx>,
 175 }
 176
 177 impl<'a, 'tcx> DefinitelyInitializedPlaces<'a, 'tcx> {
 178     pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
 179         DefinitelyInitializedPlaces { tcx, body, mdpe }
 180     }
 181 }
 182
 183 impl<'a, 'tcx> HasMoveData<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> {
 184     fn move_data(&self) -> &MoveData<'tcx> {
 185         &self.mdpe.move_data
 186     }
 187 }
 188
 189 /// `EverInitializedPlaces` tracks all places that might have ever been
 190 /// initialized upon reaching a particular point in the control flow
 191 /// for a function, without an intervening `Storage Dead`.
 192 ///
 193 /// This dataflow is used to determine if an immutable local variable may
 194 /// be assigned to.
 195 ///
 196 /// For example, in code like the following, we have corresponding
 197 /// dataflow information shown in the right-hand comments.
 198 ///
 199 /// ```rust
 200 /// struct S;
 201 /// fn foo(pred: bool) {                       // ever-init:
 202 ///                                            // {          }
 203 ///     let a = S; let b = S; let c; let d;    // {a, b      }
 204 ///
 205 ///     if pred {
 206 ///         drop(a);                           // {a, b,     }
 207 ///         b = S;                             // {a, b,     }
 208 ///
 209 ///     } else {
 210 ///         drop(b);                           // {a, b,      }
 211 ///         d = S;                             // {a, b,    d }
 212 ///
 213 ///     }                                      // {a, b,    d }
 214 ///
 215 ///     c = S;                                 // {a, b, c, d }
 216 /// }
 217 /// ```
 218 pub struct EverInitializedPlaces<'a, 'tcx> {
 219     #[allow(dead_code)]
 220     tcx: TyCtxt<'tcx>,
 221     body: &'a Body<'tcx>,
 222     mdpe: &'a MoveDataParamEnv<'tcx>,
 223 }
 224
 225 impl<'a, 'tcx> EverInitializedPlaces<'a, 'tcx> {
 226     pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>) -> Self {
 227         EverInitializedPlaces { tcx, body, mdpe }
 228     }
 229 }
 230
 231 impl<'a, 'tcx> HasMoveData<'tcx> for EverInitializedPlaces<'a, 'tcx> {
 232     fn move_data(&self) -> &MoveData<'tcx> {
 233         &self.mdpe.move_data
 234     }
 235 }
 236
 237 impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> {
 238     fn update_bits(
 239         trans: &mut impl GenKill<MovePathIndex>,
 240         path: MovePathIndex,
 241         state: DropFlagState,
 242     ) {
 243         match state {
 244             DropFlagState::Absent => trans.kill(path),
 245             DropFlagState::Present => trans.gen(path),
 246         }
 247     }
 248 }
 249
 250 impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> {
 251     fn update_bits(
 252         trans: &mut impl GenKill<MovePathIndex>,
 253         path: MovePathIndex,
 254         state: DropFlagState,
 255     ) {
 256         match state {
 257             DropFlagState::Absent => trans.gen(path),
 258             DropFlagState::Present => trans.kill(path),
 259         }
 260     }
 261 }
 262
 263 impl<'a, 'tcx> DefinitelyInitializedPlaces<'a, 'tcx> {
 264     fn update_bits(
 265         trans: &mut impl GenKill<MovePathIndex>,
 266         path: MovePathIndex,
 267         state: DropFlagState,
 268     ) {
 269         match state {
 270             DropFlagState::Absent => trans.kill(path),
 271             DropFlagState::Present => trans.gen(path),
 272         }
 273     }
 274 }
 275
 276 impl<'tcx> AnalysisDomain<'tcx> for MaybeInitializedPlaces<'_, 'tcx> {
 277     type Idx = MovePathIndex;
 278
 279     const NAME: &'static str = "maybe_init";
 280
 281     fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize {
 282         self.move_data().move_paths.len()
 283     }
 284
 285     fn initialize_start_block(&self, _: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) {
 286         drop_flag_effects_for_function_entry(self.tcx, self.body, self.mdpe, |path, s| {
 287             assert!(s == DropFlagState::Present);
 288             state.insert(path);
 289         });
 290     }
 291
 292     fn pretty_print_idx(&self, w: &mut impl std::io::Write, mpi: Self::Idx) -> std::io::Result<()> {
 293         write!(w, "{}", self.move_data().move_paths[mpi])
 294     }
 295 }
 296
 297 impl<'tcx> GenKillAnalysis<'tcx> for MaybeInitializedPlaces<'_, 'tcx> {
 298     fn statement_effect(
 299         &self,
 300         trans: &mut impl GenKill<Self::Idx>,
 301         _statement: &mir::Statement<'tcx>,
 302         location: Location,
 303     ) {
 304         drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| {
 305             Self::update_bits(trans, path, s)
 306         })
 307     }
 308
 309     fn terminator_effect(
 310         &self,
 311         trans: &mut impl GenKill<Self::Idx>,
 312         _terminator: &mir::Terminator<'tcx>,
 313         location: Location,
 314     ) {
 315         drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| {
 316             Self::update_bits(trans, path, s)
 317         })
 318     }
 319
 320     fn call_return_effect(
 321         &self,
 322         trans: &mut impl GenKill<Self::Idx>,
 323         _block: mir::BasicBlock,
 324         _func: &mir::Operand<'tcx>,
 325         _args: &[mir::Operand<'tcx>],
 326         dest_place: mir::Place<'tcx>,
 327     ) {
 328         // when a call returns successfully, that means we need to set
 329         // the bits for that dest_place to 1 (initialized).
 330         on_lookup_result_bits(
 331             self.tcx,
 332             self.body,
 333             self.move_data(),
 334             self.move_data().rev_lookup.find(dest_place.as_ref()),
 335             |mpi| {
 336                 trans.gen(mpi);
 337             },
 338         );
 339     }
 340
 341     fn discriminant_switch_effect(
 342         &self,
 343         trans: &mut impl GenKill<Self::Idx>,
 344         _block: mir::BasicBlock,
 345         enum_place: mir::Place<'tcx>,
 346         _adt: &ty::AdtDef,
 347         variant: VariantIdx,
 348     ) {
 349         let enum_mpi = match self.move_data().rev_lookup.find(enum_place.as_ref()) {
 350             LookupResult::Exact(mpi) => mpi,
 351             LookupResult::Parent(_) => return,
 352         };
 353
 354         // Kill all move paths that correspond to variants other than this one
 355         let move_paths = &self.move_data().move_paths;
 356         let enum_path = &move_paths[enum_mpi];
 357         for (mpi, variant_path) in enum_path.children(move_paths) {
 358             trans.kill(mpi);
 359             match variant_path.place.projection.last().unwrap() {
 360                 mir::ProjectionElem::Downcast(_, idx) if *idx == variant => continue,
 361                 _ => drop_flag_effects::on_all_children_bits(
 362                     self.tcx,
 363                     self.body,
 364                     self.move_data(),
 365                     mpi,
 366                     |mpi| trans.kill(mpi),
 367                 ),
 368             }
 369         }
 370     }
 371 }
 372
 373 impl<'tcx> AnalysisDomain<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> {
 374     type Idx = MovePathIndex;
 375
 376     const NAME: &'static str = "maybe_uninit";
 377
 378     fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize {
 379         self.move_data().move_paths.len()
 380     }
 381
 382     // sets on_entry bits for Arg places
 383     fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) {
 384         // set all bits to 1 (uninit) before gathering counterevidence
 385         assert!(self.bits_per_block(body) == state.domain_size());
 386         state.insert_all();
 387
 388         drop_flag_effects_for_function_entry(self.tcx, self.body, self.mdpe, |path, s| {
 389             assert!(s == DropFlagState::Present);
 390             state.remove(path);
 391         });
 392     }
 393
 394     fn pretty_print_idx(&self, w: &mut impl std::io::Write, mpi: Self::Idx) -> std::io::Result<()> {
 395         write!(w, "{}", self.move_data().move_paths[mpi])
 396     }
 397 }
 398
 399 impl<'tcx> GenKillAnalysis<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> {
 400     fn statement_effect(
 401         &self,
 402         trans: &mut impl GenKill<Self::Idx>,
 403         _statement: &mir::Statement<'tcx>,
 404         location: Location,
 405     ) {
 406         drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| {
 407             Self::update_bits(trans, path, s)
 408         })
 409     }
 410
 411     fn terminator_effect(
 412         &self,
 413         trans: &mut impl GenKill<Self::Idx>,
 414         _terminator: &mir::Terminator<'tcx>,
 415         location: Location,
 416     ) {
 417         drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| {
 418             Self::update_bits(trans, path, s)
 419         })
 420     }
 421
 422     fn call_return_effect(
 423         &self,
 424         trans: &mut impl GenKill<Self::Idx>,
 425         _block: mir::BasicBlock,
 426         _func: &mir::Operand<'tcx>,
 427         _args: &[mir::Operand<'tcx>],
 428         dest_place: mir::Place<'tcx>,
 429     ) {
 430         // when a call returns successfully, that means we need to set
 431         // the bits for that dest_place to 0 (initialized).
 432         on_lookup_result_bits(
 433             self.tcx,
 434             self.body,
 435             self.move_data(),
 436             self.move_data().rev_lookup.find(dest_place.as_ref()),
 437             |mpi| {
 438                 trans.kill(mpi);
 439             },
 440         );
 441     }
 442 }
 443
 444 impl<'a, 'tcx> AnalysisDomain<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> {
 445     type Idx = MovePathIndex;
 446
 447     const NAME: &'static str = "definite_init";
 448
 449     fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize {
 450         self.move_data().move_paths.len()
 451     }
 452
 453     // sets on_entry bits for Arg places
 454     fn initialize_start_block(&self, _: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) {
 455         state.clear();
 456
 457         drop_flag_effects_for_function_entry(self.tcx, self.body, self.mdpe, |path, s| {
 458             assert!(s == DropFlagState::Present);
 459             state.insert(path);
 460         });
 461     }
 462
 463     fn pretty_print_idx(&self, w: &mut impl std::io::Write, mpi: Self::Idx) -> std::io::Result<()> {
 464         write!(w, "{}", self.move_data().move_paths[mpi])
 465     }
 466 }
 467
 468 impl<'tcx> GenKillAnalysis<'tcx> for DefinitelyInitializedPlaces<'_, 'tcx> {
 469     fn statement_effect(
 470         &self,
 471         trans: &mut impl GenKill<Self::Idx>,
 472         _statement: &mir::Statement<'tcx>,
 473         location: Location,
 474     ) {
 475         drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| {
 476             Self::update_bits(trans, path, s)
 477         })
 478     }
 479
 480     fn terminator_effect(
 481         &self,
 482         trans: &mut impl GenKill<Self::Idx>,
 483         _terminator: &mir::Terminator<'tcx>,
 484         location: Location,
 485     ) {
 486         drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| {
 487             Self::update_bits(trans, path, s)
 488         })
 489     }
 490
 491     fn call_return_effect(
 492         &self,
 493         trans: &mut impl GenKill<Self::Idx>,
 494         _block: mir::BasicBlock,
 495         _func: &mir::Operand<'tcx>,
 496         _args: &[mir::Operand<'tcx>],
 497         dest_place: mir::Place<'tcx>,
 498     ) {
 499         // when a call returns successfully, that means we need to set
 500         // the bits for that dest_place to 1 (initialized).
 501         on_lookup_result_bits(
 502             self.tcx,
 503             self.body,
 504             self.move_data(),
 505             self.move_data().rev_lookup.find(dest_place.as_ref()),
 506             |mpi| {
 507                 trans.gen(mpi);
 508             },
 509         );
 510     }
 511 }
 512
 513 impl<'tcx> AnalysisDomain<'tcx> for EverInitializedPlaces<'_, 'tcx> {
 514     type Idx = InitIndex;
 515
 516     const NAME: &'static str = "ever_init";
 517
 518     fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize {
 519         self.move_data().inits.len()
 520     }
 521
 522     fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) {
 523         for arg_init in 0..body.arg_count {
 524             state.insert(InitIndex::new(arg_init));
 525         }
 526     }
 527 }
 528
 529 impl<'tcx> GenKillAnalysis<'tcx> for EverInitializedPlaces<'_, 'tcx> {
 530     fn statement_effect(
 531         &self,
 532         trans: &mut impl GenKill<Self::Idx>,
 533         stmt: &mir::Statement<'tcx>,
 534         location: Location,
 535     ) {
 536         let move_data = self.move_data();
 537         let init_path_map = &move_data.init_path_map;
 538         let init_loc_map = &move_data.init_loc_map;
 539         let rev_lookup = &move_data.rev_lookup;
 540
 541         debug!(
 542             "statement {:?} at loc {:?} initializes move_indexes {:?}",
 543             stmt, location, &init_loc_map[location]
 544         );
 545         trans.gen_all(init_loc_map[location].iter().copied());
 546
 547         if let mir::StatementKind::StorageDead(local) = stmt.kind {
 548             // End inits for StorageDead, so that an immutable variable can
 549             // be reinitialized on the next iteration of the loop.
 550             let move_path_index = rev_lookup.find_local(local);
 551             debug!(
 552                 "stmt {:?} at loc {:?} clears the ever initialized status of {:?}",
 553                 stmt, location, &init_path_map[move_path_index]
 554             );
 555             trans.kill_all(init_path_map[move_path_index].iter().copied());
 556         }
 557     }
 558
 559     fn terminator_effect(
 560         &self,
 561         trans: &mut impl GenKill<Self::Idx>,
 562         _terminator: &mir::Terminator<'tcx>,
 563         location: Location,
 564     ) {
 565         let (body, move_data) = (self.body, self.move_data());
 566         let term = body[location.block].terminator();
 567         let init_loc_map = &move_data.init_loc_map;
 568         debug!(
 569             "terminator {:?} at loc {:?} initializes move_indexes {:?}",
 570             term, location, &init_loc_map[location]
 571         );
 572         trans.gen_all(
 573             init_loc_map[location]
 574                 .iter()
 575                 .filter(|init_index| {
 576                     move_data.inits[**init_index].kind != InitKind::NonPanicPathOnly
 577                 })
 578                 .copied(),
 579         );
 580     }
 581
 582     fn call_return_effect(
 583         &self,
 584         trans: &mut impl GenKill<Self::Idx>,
 585         block: mir::BasicBlock,
 586         _func: &mir::Operand<'tcx>,
 587         _args: &[mir::Operand<'tcx>],
 588         _dest_place: mir::Place<'tcx>,
 589     ) {
 590         let move_data = self.move_data();
 591         let init_loc_map = &move_data.init_loc_map;
 592
 593         let call_loc = self.body.terminator_loc(block);
 594         for init_index in &init_loc_map[call_loc] {
 595             trans.gen(*init_index);
 596         }
 597     }
 598 }
 599
 600 impl<'a, 'tcx> BottomValue for MaybeInitializedPlaces<'a, 'tcx> {
 601     /// bottom = uninitialized
 602     const BOTTOM_VALUE: bool = false;
 603 }
 604
 605 impl<'a, 'tcx> BottomValue for MaybeUninitializedPlaces<'a, 'tcx> {
 606     /// bottom = initialized (start_block_effect counters this at outset)
 607     const BOTTOM_VALUE: bool = false;
 608 }
 609
 610 impl<'a, 'tcx> BottomValue for DefinitelyInitializedPlaces<'a, 'tcx> {
 611     /// bottom = initialized (start_block_effect counters this at outset)
 612     const BOTTOM_VALUE: bool = true;
 613 }
 614
 615 impl<'a, 'tcx> BottomValue for EverInitializedPlaces<'a, 'tcx> {
 616     /// bottom = no initialized variables by default
 617     const BOTTOM_VALUE: bool = false;
 618 }