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