compiler/rustc_mir_transform/src/elaborate_drops.rs

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