compiler/rustc_mir/src/transform/elaborate_drops.rs

   1 use crate::dataflow;
   2 use crate::dataflow::impls::{MaybeInitializedPlaces, MaybeUninitializedPlaces};
   3 use crate::dataflow::move_paths::{LookupResult, MoveData, MovePathIndex};
   4 use crate::dataflow::on_lookup_result_bits;
   5 use crate::dataflow::MoveDataParamEnv;
   6 use crate::dataflow::{on_all_children_bits, on_all_drop_children_bits};
   7 use crate::dataflow::{Analysis, ResultsCursor};
   8 use crate::transform::{MirPass, MirSource};
   9 use crate::util::elaborate_drops::{elaborate_drop, DropFlagState, Unwind};
  10 use crate::util::elaborate_drops::{DropElaborator, DropFlagMode, DropStyle};
  11 use crate::util::patch::MirPatch;
  12 use rustc_data_structures::fx::FxHashMap;
  13 use rustc_hir as hir;
  14 use rustc_index::bit_set::BitSet;
  15 use rustc_middle::mir::*;
  16 use rustc_middle::ty::{self, TyCtxt};
  17 use rustc_span::Span;
  18 use rustc_target::abi::VariantIdx;
  19 use std::fmt;
  20
  21 pub struct ElaborateDrops;
  22
  23 impl<'tcx> MirPass<'tcx> for ElaborateDrops {
  24     fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut Body<'tcx>) {
  25         debug!("elaborate_drops({:?} @ {:?})", src, body.span);
  26
  27         let def_id = src.def_id();
  28         let param_env = tcx.param_env_reveal_all_normalized(src.def_id());
  29         let move_data = match MoveData::gather_moves(body, tcx, param_env) {
  30             Ok(move_data) => move_data,
  31             Err((move_data, _)) => {
  32                 tcx.sess.delay_span_bug(
  33                     body.span,
  34                     "No `move_errors` should be allowed in MIR borrowck",
  35                 );
  36                 move_data
  37             }
  38         };
  39         let elaborate_patch = {
  40             let body = &*body;
  41             let env = MoveDataParamEnv { move_data, param_env };
  42             let dead_unwinds = find_dead_unwinds(tcx, body, def_id, &env);
  43
  44             let inits = MaybeInitializedPlaces::new(tcx, body, &env)
  45                 .into_engine(tcx, body, def_id)
  46                 .dead_unwinds(&dead_unwinds)
  47                 .pass_name("elaborate_drops")
  48                 .iterate_to_fixpoint()
  49                 .into_results_cursor(body);
  50
  51             let uninits = MaybeUninitializedPlaces::new(tcx, body, &env)
  52                 .mark_inactive_variants_as_uninit()
  53                 .into_engine(tcx, body, def_id)
  54                 .dead_unwinds(&dead_unwinds)
  55                 .pass_name("elaborate_drops")
  56                 .iterate_to_fixpoint()
  57                 .into_results_cursor(body);
  58
  59             ElaborateDropsCtxt {
  60                 tcx,
  61                 body,
  62                 env: &env,
  63                 init_data: InitializationData { inits, uninits },
  64                 drop_flags: Default::default(),
  65                 patch: MirPatch::new(body),
  66             }
  67             .elaborate()
  68         };
  69         elaborate_patch.apply(body);
  70     }
  71 }
  72
  73 /// Returns the set of basic blocks whose unwind edges are known
  74 /// to not be reachable, because they are `drop` terminators
  75 /// that can't drop anything.
  76 fn find_dead_unwinds<'tcx>(
  77     tcx: TyCtxt<'tcx>,
  78     body: &Body<'tcx>,
  79     def_id: hir::def_id::DefId,
  80     env: &MoveDataParamEnv<'tcx>,
  81 ) -> BitSet<BasicBlock> {
  82     debug!("find_dead_unwinds({:?})", body.span);
  83     // We only need to do this pass once, because unwind edges can only
  84     // reach cleanup blocks, which can't have unwind edges themselves.
  85     let mut dead_unwinds = BitSet::new_empty(body.basic_blocks().len());
  86     let mut flow_inits = MaybeInitializedPlaces::new(tcx, body, &env)
  87         .into_engine(tcx, body, def_id)
  88         .pass_name("find_dead_unwinds")
  89         .iterate_to_fixpoint()
  90         .into_results_cursor(body);
  91     for (bb, bb_data) in body.basic_blocks().iter_enumerated() {
  92         let place = match bb_data.terminator().kind {
  93             TerminatorKind::Drop { ref place, unwind: Some(_), .. }
  94             | TerminatorKind::DropAndReplace { ref place, unwind: Some(_), .. } => place,
  95             _ => continue,
  96         };
  97
  98         debug!("find_dead_unwinds @ {:?}: {:?}", bb, bb_data);
  99
 100         let path = match env.move_data.rev_lookup.find(place.as_ref()) {
 101             LookupResult::Exact(e) => e,
 102             LookupResult::Parent(..) => {
 103                 debug!("find_dead_unwinds: has parent; skipping");
 104                 continue;
 105             }
 106         };
 107
 108         flow_inits.seek_before_primary_effect(body.terminator_loc(bb));
 109         debug!(
 110             "find_dead_unwinds @ {:?}: path({:?})={:?}; init_data={:?}",
 111             bb,
 112             place,
 113             path,
 114             flow_inits.get()
 115         );
 116
 117         let mut maybe_live = false;
 118         on_all_drop_children_bits(tcx, body, &env, path, |child| {
 119             maybe_live |= flow_inits.contains(child);
 120         });
 121
 122         debug!("find_dead_unwinds @ {:?}: maybe_live={}", bb, maybe_live);
 123         if !maybe_live {
 124             dead_unwinds.insert(bb);
 125         }
 126     }
 127
 128     dead_unwinds
 129 }
 130
 131 struct InitializationData<'mir, 'tcx> {
 132     inits: ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>,
 133     uninits: ResultsCursor<'mir, 'tcx, MaybeUninitializedPlaces<'mir, 'tcx>>,
 134 }
 135
 136 impl InitializationData<'_, '_> {
 137     fn seek_before(&mut self, loc: Location) {
 138         self.inits.seek_before_primary_effect(loc);
 139         self.uninits.seek_before_primary_effect(loc);
 140     }
 141
 142     fn maybe_live_dead(&self, path: MovePathIndex) -> (bool, bool) {
 143         (self.inits.contains(path), self.uninits.contains(path))
 144     }
 145 }
 146
 147 struct Elaborator<'a, 'b, 'tcx> {
 148     ctxt: &'a mut ElaborateDropsCtxt<'b, 'tcx>,
 149 }
 150
 151 impl<'a, 'b, 'tcx> fmt::Debug for Elaborator<'a, 'b, 'tcx> {
 152     fn fmt(&self, _f: &mut fmt::Formatter<'_>) -> fmt::Result {
 153         Ok(())
 154     }
 155 }
 156
 157 impl<'a, 'b, 'tcx> DropElaborator<'a, 'tcx> for Elaborator<'a, 'b, 'tcx> {
 158     type Path = MovePathIndex;
 159
 160     fn patch(&mut self) -> &mut MirPatch<'tcx> {
 161         &mut self.ctxt.patch
 162     }
 163
 164     fn body(&self) -> &'a Body<'tcx> {
 165         self.ctxt.body
 166     }
 167
 168     fn tcx(&self) -> TyCtxt<'tcx> {
 169         self.ctxt.tcx
 170     }
 171
 172     fn param_env(&self) -> ty::ParamEnv<'tcx> {
 173         self.ctxt.param_env()
 174     }
 175
 176     fn drop_style(&self, path: Self::Path, mode: DropFlagMode) -> DropStyle {
 177         let ((maybe_live, maybe_dead), multipart) = match mode {
 178             DropFlagMode::Shallow => (self.ctxt.init_data.maybe_live_dead(path), false),
 179             DropFlagMode::Deep => {
 180                 let mut some_live = false;
 181                 let mut some_dead = false;
 182                 let mut children_count = 0;
 183                 on_all_drop_children_bits(self.tcx(), self.body(), self.ctxt.env, path, |child| {
 184                     let (live, dead) = self.ctxt.init_data.maybe_live_dead(child);
 185                     debug!("elaborate_drop: state({:?}) = {:?}", child, (live, dead));
 186                     some_live |= live;
 187                     some_dead |= dead;
 188                     children_count += 1;
 189                 });
 190                 ((some_live, some_dead), children_count != 1)
 191             }
 192         };
 193         match (maybe_live, maybe_dead, multipart) {
 194             (false, _, _) => DropStyle::Dead,
 195             (true, false, _) => DropStyle::Static,
 196             (true, true, false) => DropStyle::Conditional,
 197             (true, true, true) => DropStyle::Open,
 198         }
 199     }
 200
 201     fn clear_drop_flag(&mut self, loc: Location, path: Self::Path, mode: DropFlagMode) {
 202         match mode {
 203             DropFlagMode::Shallow => {
 204                 self.ctxt.set_drop_flag(loc, path, DropFlagState::Absent);
 205             }
 206             DropFlagMode::Deep => {
 207                 on_all_children_bits(
 208                     self.tcx(),
 209                     self.body(),
 210                     self.ctxt.move_data(),
 211                     path,
 212                     |child| self.ctxt.set_drop_flag(loc, child, DropFlagState::Absent),
 213                 );
 214             }
 215         }
 216     }
 217
 218     fn field_subpath(&self, path: Self::Path, field: Field) -> Option<Self::Path> {
 219         dataflow::move_path_children_matching(self.ctxt.move_data(), path, |e| match e {
 220             ProjectionElem::Field(idx, _) => idx == field,
 221             _ => false,
 222         })
 223     }
 224
 225     fn array_subpath(&self, path: Self::Path, index: u64, size: u64) -> Option<Self::Path> {
 226         dataflow::move_path_children_matching(self.ctxt.move_data(), path, |e| match e {
 227             ProjectionElem::ConstantIndex { offset, min_length, from_end } => {
 228                 debug_assert!(size == min_length, "min_length should be exact for arrays");
 229                 assert!(!from_end, "from_end should not be used for array element ConstantIndex");
 230                 offset == index
 231             }
 232             _ => false,
 233         })
 234     }
 235
 236     fn deref_subpath(&self, path: Self::Path) -> Option<Self::Path> {
 237         dataflow::move_path_children_matching(self.ctxt.move_data(), path, |e| {
 238             e == ProjectionElem::Deref
 239         })
 240     }
 241
 242     fn downcast_subpath(&self, path: Self::Path, variant: VariantIdx) -> Option<Self::Path> {
 243         dataflow::move_path_children_matching(self.ctxt.move_data(), path, |e| match e {
 244             ProjectionElem::Downcast(_, idx) => idx == variant,
 245             _ => false,
 246         })
 247     }
 248
 249     fn get_drop_flag(&mut self, path: Self::Path) -> Option<Operand<'tcx>> {
 250         self.ctxt.drop_flag(path).map(Operand::Copy)
 251     }
 252 }
 253
 254 struct ElaborateDropsCtxt<'a, 'tcx> {
 255     tcx: TyCtxt<'tcx>,
 256     body: &'a Body<'tcx>,
 257     env: &'a MoveDataParamEnv<'tcx>,
 258     init_data: InitializationData<'a, 'tcx>,
 259     drop_flags: FxHashMap<MovePathIndex, Local>,
 260     patch: MirPatch<'tcx>,
 261 }
 262
 263 impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
 264     fn move_data(&self) -> &'b MoveData<'tcx> {
 265         &self.env.move_data
 266     }
 267
 268     fn param_env(&self) -> ty::ParamEnv<'tcx> {
 269         self.env.param_env
 270     }
 271
 272     fn create_drop_flag(&mut self, index: MovePathIndex, span: Span) {
 273         let tcx = self.tcx;
 274         let patch = &mut self.patch;
 275         debug!("create_drop_flag({:?})", self.body.span);
 276         self.drop_flags.entry(index).or_insert_with(|| patch.new_internal(tcx.types.bool, span));
 277     }
 278
 279     fn drop_flag(&mut self, index: MovePathIndex) -> Option<Place<'tcx>> {
 280         self.drop_flags.get(&index).map(|t| Place::from(*t))
 281     }
 282
 283     /// create a patch that elaborates all drops in the input
 284     /// MIR.
 285     fn elaborate(mut self) -> MirPatch<'tcx> {
 286         self.collect_drop_flags();
 287
 288         self.elaborate_drops();
 289
 290         self.drop_flags_on_init();
 291         self.drop_flags_for_fn_rets();
 292         self.drop_flags_for_args();
 293         self.drop_flags_for_locs();
 294
 295         self.patch
 296     }
 297
 298     fn collect_drop_flags(&mut self) {
 299         for (bb, data) in self.body.basic_blocks().iter_enumerated() {
 300             let terminator = data.terminator();
 301             let place = match terminator.kind {
 302                 TerminatorKind::Drop { ref place, .. }
 303                 | TerminatorKind::DropAndReplace { ref place, .. } => place,
 304                 _ => continue,
 305             };
 306
 307             self.init_data.seek_before(self.body.terminator_loc(bb));
 308
 309             let path = self.move_data().rev_lookup.find(place.as_ref());
 310             debug!("collect_drop_flags: {:?}, place {:?} ({:?})", bb, place, path);
 311
 312             let path = match path {
 313                 LookupResult::Exact(e) => e,
 314                 LookupResult::Parent(None) => continue,
 315                 LookupResult::Parent(Some(parent)) => {
 316                     let (_maybe_live, maybe_dead) = self.init_data.maybe_live_dead(parent);
 317                     if maybe_dead {
 318                         span_bug!(
 319                             terminator.source_info.span,
 320                             "drop of untracked, uninitialized value {:?}, place {:?} ({:?})",
 321                             bb,
 322                             place,
 323                             path
 324                         );
 325                     }
 326                     continue;
 327                 }
 328             };
 329
 330             on_all_drop_children_bits(self.tcx, self.body, self.env, path, |child| {
 331                 let (maybe_live, maybe_dead) = self.init_data.maybe_live_dead(child);
 332                 debug!(
 333                     "collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
 334                     child,
 335                     place,
 336                     path,
 337                     (maybe_live, maybe_dead)
 338                 );
 339                 if maybe_live && maybe_dead {
 340                     self.create_drop_flag(child, terminator.source_info.span)
 341                 }
 342             });
 343         }
 344     }
 345
 346     fn elaborate_drops(&mut self) {
 347         for (bb, data) in self.body.basic_blocks().iter_enumerated() {
 348             let loc = Location { block: bb, statement_index: data.statements.len() };
 349             let terminator = data.terminator();
 350
 351             let resume_block = self.patch.resume_block();
 352             match terminator.kind {
 353                 TerminatorKind::Drop { place, target, unwind } => {
 354                     self.init_data.seek_before(loc);
 355                     match self.move_data().rev_lookup.find(place.as_ref()) {
 356                         LookupResult::Exact(path) => elaborate_drop(
 357                             &mut Elaborator { ctxt: self },
 358                             terminator.source_info,
 359                             place,
 360                             path,
 361                             target,
 362                             if data.is_cleanup {
 363                                 Unwind::InCleanup
 364                             } else {
 365                                 Unwind::To(Option::unwrap_or(unwind, resume_block))
 366                             },
 367                             bb,
 368                         ),
 369                         LookupResult::Parent(..) => {
 370                             span_bug!(
 371                                 terminator.source_info.span,
 372                                 "drop of untracked value {:?}",
 373                                 bb
 374                             );
 375                         }
 376                     }
 377                 }
 378                 TerminatorKind::DropAndReplace { place, ref value, target, unwind } => {
 379                     assert!(!data.is_cleanup);
 380
 381                     self.elaborate_replace(loc, place, value, target, unwind);
 382                 }
 383                 _ => continue,
 384             }
 385         }
 386     }
 387
 388     /// Elaborate a MIR `replace` terminator. This instruction
 389     /// is not directly handled by codegen, and therefore
 390     /// must be desugared.
 391     ///
 392     /// The desugaring drops the location if needed, and then writes
 393     /// the value (including setting the drop flag) over it in *both* arms.
 394     ///
 395     /// The `replace` terminator can also be called on places that
 396     /// are not tracked by elaboration (for example,
 397     /// `replace x[i] <- tmp0`). The borrow checker requires that
 398     /// these locations are initialized before the assignment,
 399     /// so we just generate an unconditional drop.
 400     fn elaborate_replace(
 401         &mut self,
 402         loc: Location,
 403         place: Place<'tcx>,
 404         value: &Operand<'tcx>,
 405         target: BasicBlock,
 406         unwind: Option<BasicBlock>,
 407     ) {
 408         let bb = loc.block;
 409         let data = &self.body[bb];
 410         let terminator = data.terminator();
 411         assert!(!data.is_cleanup, "DropAndReplace in unwind path not supported");
 412
 413         let assign = Statement {
 414             kind: StatementKind::Assign(box (place, Rvalue::Use(value.clone()))),
 415             source_info: terminator.source_info,
 416         };
 417
 418         let unwind = unwind.unwrap_or_else(|| self.patch.resume_block());
 419         let unwind = self.patch.new_block(BasicBlockData {
 420             statements: vec![assign.clone()],
 421             terminator: Some(Terminator {
 422                 kind: TerminatorKind::Goto { target: unwind },
 423                 ..*terminator
 424             }),
 425             is_cleanup: true,
 426         });
 427
 428         let target = self.patch.new_block(BasicBlockData {
 429             statements: vec![assign],
 430             terminator: Some(Terminator { kind: TerminatorKind::Goto { target }, ..*terminator }),
 431             is_cleanup: false,
 432         });
 433
 434         match self.move_data().rev_lookup.find(place.as_ref()) {
 435             LookupResult::Exact(path) => {
 436                 debug!("elaborate_drop_and_replace({:?}) - tracked {:?}", terminator, path);
 437                 self.init_data.seek_before(loc);
 438                 elaborate_drop(
 439                     &mut Elaborator { ctxt: self },
 440                     terminator.source_info,
 441                     place,
 442                     path,
 443                     target,
 444                     Unwind::To(unwind),
 445                     bb,
 446                 );
 447                 on_all_children_bits(self.tcx, self.body, self.move_data(), path, |child| {
 448                     self.set_drop_flag(
 449                         Location { block: target, statement_index: 0 },
 450                         child,
 451                         DropFlagState::Present,
 452                     );
 453                     self.set_drop_flag(
 454                         Location { block: unwind, statement_index: 0 },
 455                         child,
 456                         DropFlagState::Present,
 457                     );
 458                 });
 459             }
 460             LookupResult::Parent(parent) => {
 461                 // drop and replace behind a pointer/array/whatever. The location
 462                 // must be initialized.
 463                 debug!("elaborate_drop_and_replace({:?}) - untracked {:?}", terminator, parent);
 464                 self.patch.patch_terminator(
 465                     bb,
 466                     TerminatorKind::Drop { place, target, unwind: Some(unwind) },
 467                 );
 468             }
 469         }
 470     }
 471
 472     fn constant_bool(&self, span: Span, val: bool) -> Rvalue<'tcx> {
 473         Rvalue::Use(Operand::Constant(Box::new(Constant {
 474             span,
 475             user_ty: None,
 476             literal: ty::Const::from_bool(self.tcx, val),
 477         })))
 478     }
 479
 480     fn set_drop_flag(&mut self, loc: Location, path: MovePathIndex, val: DropFlagState) {
 481         if let Some(&flag) = self.drop_flags.get(&path) {
 482             let span = self.patch.source_info_for_location(self.body, loc).span;
 483             let val = self.constant_bool(span, val.value());
 484             self.patch.add_assign(loc, Place::from(flag), val);
 485         }
 486     }
 487
 488     fn drop_flags_on_init(&mut self) {
 489         let loc = Location::START;
 490         let span = self.patch.source_info_for_location(self.body, loc).span;
 491         let false_ = self.constant_bool(span, false);
 492         for flag in self.drop_flags.values() {
 493             self.patch.add_assign(loc, Place::from(*flag), false_.clone());
 494         }
 495     }
 496
 497     fn drop_flags_for_fn_rets(&mut self) {
 498         for (bb, data) in self.body.basic_blocks().iter_enumerated() {
 499             if let TerminatorKind::Call {
 500                 destination: Some((ref place, tgt)),
 501                 cleanup: Some(_),
 502                 ..
 503             } = data.terminator().kind
 504             {
 505                 assert!(!self.patch.is_patched(bb));
 506
 507                 let loc = Location { block: tgt, statement_index: 0 };
 508                 let path = self.move_data().rev_lookup.find(place.as_ref());
 509                 on_lookup_result_bits(self.tcx, self.body, self.move_data(), path, |child| {
 510                     self.set_drop_flag(loc, child, DropFlagState::Present)
 511                 });
 512             }
 513         }
 514     }
 515
 516     fn drop_flags_for_args(&mut self) {
 517         let loc = Location::START;
 518         dataflow::drop_flag_effects_for_function_entry(self.tcx, self.body, self.env, |path, ds| {
 519             self.set_drop_flag(loc, path, ds);
 520         })
 521     }
 522
 523     fn drop_flags_for_locs(&mut self) {
 524         // We intentionally iterate only over the *old* basic blocks.
 525         //
 526         // Basic blocks created by drop elaboration update their
 527         // drop flags by themselves, to avoid the drop flags being
 528         // clobbered before they are read.
 529
 530         for (bb, data) in self.body.basic_blocks().iter_enumerated() {
 531             debug!("drop_flags_for_locs({:?})", data);
 532             for i in 0..(data.statements.len() + 1) {
 533                 debug!("drop_flag_for_locs: stmt {}", i);
 534                 let mut allow_initializations = true;
 535                 if i == data.statements.len() {
 536                     match data.terminator().kind {
 537                         TerminatorKind::Drop { .. } => {
 538                             // drop elaboration should handle that by itself
 539                             continue;
 540                         }
 541                         TerminatorKind::DropAndReplace { .. } => {
 542                             // this contains the move of the source and
 543                             // the initialization of the destination. We
 544                             // only want the former - the latter is handled
 545                             // by the elaboration code and must be done
 546                             // *after* the destination is dropped.
 547                             assert!(self.patch.is_patched(bb));
 548                             allow_initializations = false;
 549                         }
 550                         TerminatorKind::Resume => {
 551                             // It is possible for `Resume` to be patched
 552                             // (in particular it can be patched to be replaced with
 553                             // a Goto; see `MirPatch::new`).
 554                         }
 555                         _ => {
 556                             assert!(!self.patch.is_patched(bb));
 557                         }
 558                     }
 559                 }
 560                 let loc = Location { block: bb, statement_index: i };
 561                 dataflow::drop_flag_effects_for_location(
 562                     self.tcx,
 563                     self.body,
 564                     self.env,
 565                     loc,
 566                     |path, ds| {
 567                         if ds == DropFlagState::Absent || allow_initializations {
 568                             self.set_drop_flag(loc, path, ds)
 569                         }
 570                     },
 571                 )
 572             }
 573
 574             // There may be a critical edge after this call,
 575             // so mark the return as initialized *before* the
 576             // call.
 577             if let TerminatorKind::Call {
 578                 destination: Some((ref place, _)), cleanup: None, ..
 579             } = data.terminator().kind
 580             {
 581                 assert!(!self.patch.is_patched(bb));
 582
 583                 let loc = Location { block: bb, statement_index: data.statements.len() };
 584                 let path = self.move_data().rev_lookup.find(place.as_ref());
 585                 on_lookup_result_bits(self.tcx, self.body, self.move_data(), path, |child| {
 586                     self.set_drop_flag(loc, child, DropFlagState::Present)
 587                 });
 588             }
 589         }
 590     }
 591 }