1 use crate::dataflow::move_paths::{HasMoveData, MoveData, MovePathIndex, LookupResult};
2 use crate::dataflow::{MaybeInitializedPlaces, MaybeUninitializedPlaces};
3 use crate::dataflow::{DataflowResults};
4 use crate::dataflow::{on_all_children_bits, on_all_drop_children_bits};
5 use crate::dataflow::{drop_flag_effects_for_location, on_lookup_result_bits};
6 use crate::dataflow::MoveDataParamEnv;
7 use crate::dataflow::{self, do_dataflow, DebugFormatted};
8 use crate::transform::{MirPass, MirSource};
9 use crate::util::patch::MirPatch;
10 use crate::util::elaborate_drops::{DropFlagState, Unwind, elaborate_drop};
11 use crate::util::elaborate_drops::{DropElaborator, DropStyle, DropFlagMode};
12 use rustc::ty::{self, TyCtxt};
13 use rustc::ty::layout::VariantIdx;
16 use rustc::util::nodemap::FxHashMap;
17 use rustc_data_structures::bit_set::BitSet;
21 pub struct ElaborateDrops;
23 impl MirPass for ElaborateDrops {
24 fn run_pass<'a, 'tcx>(&self,
25 tcx: TyCtxt<'a, 'tcx, 'tcx>,
29 debug!("elaborate_drops({:?} @ {:?})", src, mir.span);
31 let def_id = src.def_id();
32 let param_env = tcx.param_env(src.def_id()).with_reveal_all();
33 let move_data = match MoveData::gather_moves(mir, tcx) {
34 Ok(move_data) => move_data,
35 Err((move_data, _move_errors)) => {
36 // The only way we should be allowing any move_errors
37 // in here is if we are in the migration path for the
38 // NLL-based MIR-borrowck.
40 // If we are in the migration path, we have already
41 // reported these errors as warnings to the user. So
42 // we will just ignore them here.
43 assert!(tcx.migrate_borrowck());
47 let elaborate_patch = {
49 let env = MoveDataParamEnv {
53 let dead_unwinds = find_dead_unwinds(tcx, mir, def_id, &env);
55 do_dataflow(tcx, mir, def_id, &[], &dead_unwinds,
56 MaybeInitializedPlaces::new(tcx, mir, &env),
57 |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]));
59 do_dataflow(tcx, mir, def_id, &[], &dead_unwinds,
60 MaybeUninitializedPlaces::new(tcx, mir, &env),
61 |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]));
69 drop_flags: Default::default(),
70 patch: MirPatch::new(mir),
73 elaborate_patch.apply(mir);
77 /// Returns the set of basic blocks whose unwind edges are known
78 /// to not be reachable, because they are `drop` terminators
79 /// that can't drop anything.
80 fn find_dead_unwinds<'a, 'tcx>(
81 tcx: TyCtxt<'a, 'tcx, 'tcx>,
83 def_id: hir::def_id::DefId,
84 env: &MoveDataParamEnv<'tcx, 'tcx>)
87 debug!("find_dead_unwinds({:?})", mir.span);
88 // We only need to do this pass once, because unwind edges can only
89 // reach cleanup blocks, which can't have unwind edges themselves.
90 let mut dead_unwinds = BitSet::new_empty(mir.basic_blocks().len());
92 do_dataflow(tcx, mir, def_id, &[], &dead_unwinds,
93 MaybeInitializedPlaces::new(tcx, mir, &env),
94 |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]));
95 for (bb, bb_data) in mir.basic_blocks().iter_enumerated() {
96 let location = match bb_data.terminator().kind {
97 TerminatorKind::Drop { ref location, unwind: Some(_), .. } |
98 TerminatorKind::DropAndReplace { ref location, unwind: Some(_), .. } => location,
102 let mut init_data = InitializationData {
103 live: flow_inits.sets().on_entry_set_for(bb.index()).to_owned(),
104 dead: BitSet::new_empty(env.move_data.move_paths.len()),
106 debug!("find_dead_unwinds @ {:?}: {:?}; init_data={:?}",
107 bb, bb_data, init_data.live);
108 for stmt in 0..bb_data.statements.len() {
109 let loc = Location { block: bb, statement_index: stmt };
110 init_data.apply_location(tcx, mir, env, loc);
113 let path = match env.move_data.rev_lookup.find(location) {
114 LookupResult::Exact(e) => e,
115 LookupResult::Parent(..) => {
116 debug!("find_dead_unwinds: has parent; skipping");
121 debug!("find_dead_unwinds @ {:?}: path({:?})={:?}", bb, location, path);
123 let mut maybe_live = false;
124 on_all_drop_children_bits(tcx, mir, &env, path, |child| {
125 let (child_maybe_live, _) = init_data.state(child);
126 maybe_live |= child_maybe_live;
129 debug!("find_dead_unwinds @ {:?}: maybe_live={}", bb, maybe_live);
131 dead_unwinds.insert(bb);
138 struct InitializationData {
139 live: BitSet<MovePathIndex>,
140 dead: BitSet<MovePathIndex>
143 impl InitializationData {
144 fn apply_location<'a,'tcx>(&mut self,
145 tcx: TyCtxt<'a, 'tcx, 'tcx>,
147 env: &MoveDataParamEnv<'tcx, 'tcx>,
150 drop_flag_effects_for_location(tcx, mir, env, loc, |path, df| {
151 debug!("at location {:?}: setting {:?} to {:?}",
154 DropFlagState::Present => {
155 self.live.insert(path);
156 self.dead.remove(path);
158 DropFlagState::Absent => {
159 self.dead.insert(path);
160 self.live.remove(path);
166 fn state(&self, path: MovePathIndex) -> (bool, bool) {
167 (self.live.contains(path), self.dead.contains(path))
171 struct Elaborator<'a, 'b: 'a, 'tcx: 'b> {
172 init_data: &'a InitializationData,
173 ctxt: &'a mut ElaborateDropsCtxt<'b, 'tcx>,
176 impl<'a, 'b, 'tcx> fmt::Debug for Elaborator<'a, 'b, 'tcx> {
177 fn fmt(&self, _f: &mut fmt::Formatter<'_>) -> fmt::Result {
182 impl<'a, 'b, 'tcx> DropElaborator<'a, 'tcx> for Elaborator<'a, 'b, 'tcx> {
183 type Path = MovePathIndex;
185 fn patch(&mut self) -> &mut MirPatch<'tcx> {
189 fn mir(&self) -> &'a Body<'tcx> {
193 fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> {
197 fn param_env(&self) -> ty::ParamEnv<'tcx> {
198 self.ctxt.param_env()
201 fn drop_style(&self, path: Self::Path, mode: DropFlagMode) -> DropStyle {
202 let ((maybe_live, maybe_dead), multipart) = match mode {
203 DropFlagMode::Shallow => (self.init_data.state(path), false),
204 DropFlagMode::Deep => {
205 let mut some_live = false;
206 let mut some_dead = false;
207 let mut children_count = 0;
208 on_all_drop_children_bits(
209 self.tcx(), self.mir(), self.ctxt.env, path, |child| {
210 let (live, dead) = self.init_data.state(child);
211 debug!("elaborate_drop: state({:?}) = {:?}",
212 child, (live, dead));
217 ((some_live, some_dead), children_count != 1)
220 match (maybe_live, maybe_dead, multipart) {
221 (false, _, _) => DropStyle::Dead,
222 (true, false, _) => DropStyle::Static,
223 (true, true, false) => DropStyle::Conditional,
224 (true, true, true) => DropStyle::Open,
228 fn clear_drop_flag(&mut self, loc: Location, path: Self::Path, mode: DropFlagMode) {
230 DropFlagMode::Shallow => {
231 self.ctxt.set_drop_flag(loc, path, DropFlagState::Absent);
233 DropFlagMode::Deep => {
234 on_all_children_bits(
235 self.tcx(), self.mir(), self.ctxt.move_data(), path,
236 |child| self.ctxt.set_drop_flag(loc, child, DropFlagState::Absent)
242 fn field_subpath(&self, path: Self::Path, field: Field) -> Option<Self::Path> {
243 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
246 elem: ProjectionElem::Field(idx, _), ..
253 fn array_subpath(&self, path: Self::Path, index: u32, size: u32) -> Option<Self::Path> {
254 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
257 elem: ProjectionElem::ConstantIndex{offset, min_length: _, from_end: false}, ..
258 } => offset == index,
260 elem: ProjectionElem::ConstantIndex{offset, min_length: _, from_end: true}, ..
261 } => size - offset == index,
267 fn deref_subpath(&self, path: Self::Path) -> Option<Self::Path> {
268 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
270 &Projection { elem: ProjectionElem::Deref, .. } => true,
276 fn downcast_subpath(&self, path: Self::Path, variant: VariantIdx) -> Option<Self::Path> {
277 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
280 elem: ProjectionElem::Downcast(_, idx), ..
287 fn get_drop_flag(&mut self, path: Self::Path) -> Option<Operand<'tcx>> {
288 self.ctxt.drop_flag(path).map(Operand::Copy)
292 struct ElaborateDropsCtxt<'a, 'tcx: 'a> {
293 tcx: TyCtxt<'a, 'tcx, 'tcx>,
295 env: &'a MoveDataParamEnv<'tcx, 'tcx>,
296 flow_inits: DataflowResults<'tcx, MaybeInitializedPlaces<'a, 'tcx, 'tcx>>,
297 flow_uninits: DataflowResults<'tcx, MaybeUninitializedPlaces<'a, 'tcx, 'tcx>>,
298 drop_flags: FxHashMap<MovePathIndex, Local>,
299 patch: MirPatch<'tcx>,
302 impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
303 fn move_data(&self) -> &'b MoveData<'tcx> { &self.env.move_data }
305 fn param_env(&self) -> ty::ParamEnv<'tcx> {
309 fn initialization_data_at(&self, loc: Location) -> InitializationData {
310 let mut data = InitializationData {
311 live: self.flow_inits.sets().on_entry_set_for(loc.block.index())
313 dead: self.flow_uninits.sets().on_entry_set_for(loc.block.index())
316 for stmt in 0..loc.statement_index {
317 data.apply_location(self.tcx, self.mir, self.env,
318 Location { block: loc.block, statement_index: stmt });
323 fn create_drop_flag(&mut self, index: MovePathIndex, span: Span) {
325 let patch = &mut self.patch;
326 debug!("create_drop_flag({:?})", self.mir.span);
327 self.drop_flags.entry(index).or_insert_with(|| {
328 patch.new_internal(tcx.types.bool, span)
332 fn drop_flag(&mut self, index: MovePathIndex) -> Option<Place<'tcx>> {
333 self.drop_flags.get(&index).map(|t| Place::Base(PlaceBase::Local(*t)))
336 /// create a patch that elaborates all drops in the input
338 fn elaborate(mut self) -> MirPatch<'tcx>
340 self.collect_drop_flags();
342 self.elaborate_drops();
344 self.drop_flags_on_init();
345 self.drop_flags_for_fn_rets();
346 self.drop_flags_for_args();
347 self.drop_flags_for_locs();
352 fn collect_drop_flags(&mut self)
354 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
355 let terminator = data.terminator();
356 let location = match terminator.kind {
357 TerminatorKind::Drop { ref location, .. } |
358 TerminatorKind::DropAndReplace { ref location, .. } => location,
362 let init_data = self.initialization_data_at(Location {
364 statement_index: data.statements.len()
367 let path = self.move_data().rev_lookup.find(location);
368 debug!("collect_drop_flags: {:?}, place {:?} ({:?})",
371 let path = match path {
372 LookupResult::Exact(e) => e,
373 LookupResult::Parent(None) => continue,
374 LookupResult::Parent(Some(parent)) => {
375 let (_maybe_live, maybe_dead) = init_data.state(parent);
377 span_bug!(terminator.source_info.span,
378 "drop of untracked, uninitialized value {:?}, place {:?} ({:?})",
385 on_all_drop_children_bits(self.tcx, self.mir, self.env, path, |child| {
386 let (maybe_live, maybe_dead) = init_data.state(child);
387 debug!("collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
388 child, location, path, (maybe_live, maybe_dead));
389 if maybe_live && maybe_dead {
390 self.create_drop_flag(child, terminator.source_info.span)
396 fn elaborate_drops(&mut self)
398 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
399 let loc = Location { block: bb, statement_index: data.statements.len() };
400 let terminator = data.terminator();
402 let resume_block = self.patch.resume_block();
403 match terminator.kind {
404 TerminatorKind::Drop { ref location, target, unwind } => {
405 let init_data = self.initialization_data_at(loc);
406 match self.move_data().rev_lookup.find(location) {
407 LookupResult::Exact(path) => {
410 init_data: &init_data,
413 terminator.source_info,
420 Unwind::To(Option::unwrap_or(unwind, resume_block))
424 LookupResult::Parent(..) => {
425 span_bug!(terminator.source_info.span,
426 "drop of untracked value {:?}", bb);
430 TerminatorKind::DropAndReplace { ref location, ref value,
433 assert!(!data.is_cleanup);
435 self.elaborate_replace(
446 /// Elaborate a MIR `replace` terminator. This instruction
447 /// is not directly handled by codegen, and therefore
448 /// must be desugared.
450 /// The desugaring drops the location if needed, and then writes
451 /// the value (including setting the drop flag) over it in *both* arms.
453 /// The `replace` terminator can also be called on places that
454 /// are not tracked by elaboration (for example,
455 /// `replace x[i] <- tmp0`). The borrow checker requires that
456 /// these locations are initialized before the assignment,
457 /// so we just generate an unconditional drop.
458 fn elaborate_replace(
461 location: &Place<'tcx>,
462 value: &Operand<'tcx>,
464 unwind: Option<BasicBlock>)
467 let data = &self.mir[bb];
468 let terminator = data.terminator();
469 assert!(!data.is_cleanup, "DropAndReplace in unwind path not supported");
471 let assign = Statement {
472 kind: StatementKind::Assign(location.clone(), box Rvalue::Use(value.clone())),
473 source_info: terminator.source_info
476 let unwind = unwind.unwrap_or_else(|| self.patch.resume_block());
477 let unwind = self.patch.new_block(BasicBlockData {
478 statements: vec![assign.clone()],
479 terminator: Some(Terminator {
480 kind: TerminatorKind::Goto { target: unwind },
486 let target = self.patch.new_block(BasicBlockData {
487 statements: vec![assign],
488 terminator: Some(Terminator {
489 kind: TerminatorKind::Goto { target },
495 match self.move_data().rev_lookup.find(location) {
496 LookupResult::Exact(path) => {
497 debug!("elaborate_drop_and_replace({:?}) - tracked {:?}", terminator, path);
498 let init_data = self.initialization_data_at(loc);
502 init_data: &init_data,
505 terminator.source_info,
511 on_all_children_bits(self.tcx, self.mir, self.move_data(), path, |child| {
512 self.set_drop_flag(Location { block: target, statement_index: 0 },
513 child, DropFlagState::Present);
514 self.set_drop_flag(Location { block: unwind, statement_index: 0 },
515 child, DropFlagState::Present);
518 LookupResult::Parent(parent) => {
519 // drop and replace behind a pointer/array/whatever. The location
520 // must be initialized.
521 debug!("elaborate_drop_and_replace({:?}) - untracked {:?}", terminator, parent);
522 self.patch.patch_terminator(bb, TerminatorKind::Drop {
523 location: location.clone(),
531 fn constant_bool(&self, span: Span, val: bool) -> Rvalue<'tcx> {
532 Rvalue::Use(Operand::Constant(Box::new(Constant {
534 ty: self.tcx.types.bool,
536 literal: ty::Const::from_bool(self.tcx, val),
540 fn set_drop_flag(&mut self, loc: Location, path: MovePathIndex, val: DropFlagState) {
541 if let Some(&flag) = self.drop_flags.get(&path) {
542 let span = self.patch.source_info_for_location(self.mir, loc).span;
543 let val = self.constant_bool(span, val.value());
544 self.patch.add_assign(loc, Place::Base(PlaceBase::Local(flag)), val);
548 fn drop_flags_on_init(&mut self) {
549 let loc = Location::START;
550 let span = self.patch.source_info_for_location(self.mir, loc).span;
551 let false_ = self.constant_bool(span, false);
552 for flag in self.drop_flags.values() {
553 self.patch.add_assign(loc, Place::Base(PlaceBase::Local(*flag)), false_.clone());
557 fn drop_flags_for_fn_rets(&mut self) {
558 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
559 if let TerminatorKind::Call {
560 destination: Some((ref place, tgt)), cleanup: Some(_), ..
561 } = data.terminator().kind {
562 assert!(!self.patch.is_patched(bb));
564 let loc = Location { block: tgt, statement_index: 0 };
565 let path = self.move_data().rev_lookup.find(place);
566 on_lookup_result_bits(
567 self.tcx, self.mir, self.move_data(), path,
568 |child| self.set_drop_flag(loc, child, DropFlagState::Present)
574 fn drop_flags_for_args(&mut self) {
575 let loc = Location::START;
576 dataflow::drop_flag_effects_for_function_entry(
577 self.tcx, self.mir, self.env, |path, ds| {
578 self.set_drop_flag(loc, path, ds);
583 fn drop_flags_for_locs(&mut self) {
584 // We intentionally iterate only over the *old* basic blocks.
586 // Basic blocks created by drop elaboration update their
587 // drop flags by themselves, to avoid the drop flags being
588 // clobbered before they are read.
590 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
591 debug!("drop_flags_for_locs({:?})", data);
592 for i in 0..(data.statements.len()+1) {
593 debug!("drop_flag_for_locs: stmt {}", i);
594 let mut allow_initializations = true;
595 if i == data.statements.len() {
596 match data.terminator().kind {
597 TerminatorKind::Drop { .. } => {
598 // drop elaboration should handle that by itself
601 TerminatorKind::DropAndReplace { .. } => {
602 // this contains the move of the source and
603 // the initialization of the destination. We
604 // only want the former - the latter is handled
605 // by the elaboration code and must be done
606 // *after* the destination is dropped.
607 assert!(self.patch.is_patched(bb));
608 allow_initializations = false;
610 TerminatorKind::Resume => {
611 // It is possible for `Resume` to be patched
612 // (in particular it can be patched to be replaced with
613 // a Goto; see `MirPatch::new`).
616 assert!(!self.patch.is_patched(bb));
620 let loc = Location { block: bb, statement_index: i };
621 dataflow::drop_flag_effects_for_location(
622 self.tcx, self.mir, self.env, loc, |path, ds| {
623 if ds == DropFlagState::Absent || allow_initializations {
624 self.set_drop_flag(loc, path, ds)
630 // There may be a critical edge after this call,
631 // so mark the return as initialized *before* the
633 if let TerminatorKind::Call {
634 destination: Some((ref place, _)), cleanup: None, ..
635 } = data.terminator().kind {
636 assert!(!self.patch.is_patched(bb));
638 let loc = Location { block: bb, statement_index: data.statements.len() };
639 let path = self.move_data().rev_lookup.find(place);
640 on_lookup_result_bits(
641 self.tcx, self.mir, self.move_data(), path,
642 |child| self.set_drop_flag(loc, child, DropFlagState::Present)