1 use crate::dataflow::move_paths::{HasMoveData, LookupResult, MoveData, MovePathIndex};
2 use crate::dataflow::DataflowResults;
3 use crate::dataflow::MoveDataParamEnv;
4 use crate::dataflow::{self, do_dataflow, DebugFormatted};
5 use crate::dataflow::{drop_flag_effects_for_location, on_lookup_result_bits};
6 use crate::dataflow::{on_all_children_bits, on_all_drop_children_bits};
7 use crate::dataflow::{MaybeInitializedPlaces, MaybeUninitializedPlaces};
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;
13 use rustc::ty::layout::VariantIdx;
14 use rustc::ty::{self, TyCtxt};
15 use rustc_data_structures::fx::FxHashMap;
17 use rustc_index::bit_set::BitSet;
21 pub struct ElaborateDrops;
23 impl<'tcx> MirPass<'tcx> for ElaborateDrops {
24 fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut BodyAndCache<'tcx>) {
25 debug!("elaborate_drops({:?} @ {:?})", src, body.span);
27 let def_id = src.def_id();
28 let param_env = tcx.param_env(src.def_id()).with_reveal_all();
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(
34 "No `move_errors` should be allowed in MIR borrowck",
39 let elaborate_patch = {
41 let env = MoveDataParamEnv { move_data, param_env };
42 let dead_unwinds = find_dead_unwinds(tcx, body, def_id, &env);
43 let flow_inits = do_dataflow(
49 MaybeInitializedPlaces::new(tcx, body, &env),
50 |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]),
52 let flow_uninits = do_dataflow(
58 MaybeUninitializedPlaces::new(tcx, body, &env),
59 |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]),
68 drop_flags: Default::default(),
69 patch: MirPatch::new(body),
73 elaborate_patch.apply(body);
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<'tcx>(
83 def_id: hir::def_id::DefId,
84 env: &MoveDataParamEnv<'tcx>,
85 ) -> BitSet<BasicBlock> {
86 debug!("find_dead_unwinds({:?})", body.span);
87 // We only need to do this pass once, because unwind edges can only
88 // reach cleanup blocks, which can't have unwind edges themselves.
89 let mut dead_unwinds = BitSet::new_empty(body.basic_blocks().len());
90 let flow_inits = do_dataflow(
96 MaybeInitializedPlaces::new(tcx, body, &env),
97 |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]),
99 for (bb, bb_data) in body.basic_blocks().iter_enumerated() {
100 let location = match bb_data.terminator().kind {
101 TerminatorKind::Drop { ref location, unwind: Some(_), .. }
102 | TerminatorKind::DropAndReplace { ref location, unwind: Some(_), .. } => location,
106 let mut init_data = InitializationData {
107 live: flow_inits.sets().entry_set_for(bb.index()).to_owned(),
108 dead: BitSet::new_empty(env.move_data.move_paths.len()),
110 debug!("find_dead_unwinds @ {:?}: {:?}; init_data={:?}", bb, bb_data, init_data.live);
111 for stmt in 0..bb_data.statements.len() {
112 let loc = Location { block: bb, statement_index: stmt };
113 init_data.apply_location(tcx, body, env, loc);
116 let path = match env.move_data.rev_lookup.find(location.as_ref()) {
117 LookupResult::Exact(e) => e,
118 LookupResult::Parent(..) => {
119 debug!("find_dead_unwinds: has parent; skipping");
124 debug!("find_dead_unwinds @ {:?}: path({:?})={:?}", bb, location, path);
126 let mut maybe_live = false;
127 on_all_drop_children_bits(tcx, body, &env, path, |child| {
128 let (child_maybe_live, _) = init_data.state(child);
129 maybe_live |= child_maybe_live;
132 debug!("find_dead_unwinds @ {:?}: maybe_live={}", bb, maybe_live);
134 dead_unwinds.insert(bb);
141 struct InitializationData {
142 live: BitSet<MovePathIndex>,
143 dead: BitSet<MovePathIndex>,
146 impl InitializationData {
147 fn apply_location<'tcx>(
151 env: &MoveDataParamEnv<'tcx>,
154 drop_flag_effects_for_location(tcx, body, env, loc, |path, df| {
155 debug!("at location {:?}: setting {:?} to {:?}", loc, path, df);
157 DropFlagState::Present => {
158 self.live.insert(path);
159 self.dead.remove(path);
161 DropFlagState::Absent => {
162 self.dead.insert(path);
163 self.live.remove(path);
169 fn state(&self, path: MovePathIndex) -> (bool, bool) {
170 (self.live.contains(path), self.dead.contains(path))
174 struct Elaborator<'a, 'b, 'tcx> {
175 init_data: &'a InitializationData,
176 ctxt: &'a mut ElaborateDropsCtxt<'b, 'tcx>,
179 impl<'a, 'b, 'tcx> fmt::Debug for Elaborator<'a, 'b, 'tcx> {
180 fn fmt(&self, _f: &mut fmt::Formatter<'_>) -> fmt::Result {
185 impl<'a, 'b, 'tcx> DropElaborator<'a, 'tcx> for Elaborator<'a, 'b, 'tcx> {
186 type Path = MovePathIndex;
188 fn patch(&mut self) -> &mut MirPatch<'tcx> {
192 fn body(&self) -> &'a Body<'tcx> {
196 fn tcx(&self) -> TyCtxt<'tcx> {
200 fn param_env(&self) -> ty::ParamEnv<'tcx> {
201 self.ctxt.param_env()
204 fn drop_style(&self, path: Self::Path, mode: DropFlagMode) -> DropStyle {
205 let ((maybe_live, maybe_dead), multipart) = match mode {
206 DropFlagMode::Shallow => (self.init_data.state(path), false),
207 DropFlagMode::Deep => {
208 let mut some_live = false;
209 let mut some_dead = false;
210 let mut children_count = 0;
211 on_all_drop_children_bits(self.tcx(), self.body(), self.ctxt.env, path, |child| {
212 let (live, dead) = self.init_data.state(child);
213 debug!("elaborate_drop: state({:?}) = {:?}", child, (live, dead));
218 ((some_live, some_dead), children_count != 1)
221 match (maybe_live, maybe_dead, multipart) {
222 (false, _, _) => DropStyle::Dead,
223 (true, false, _) => DropStyle::Static,
224 (true, true, false) => DropStyle::Conditional,
225 (true, true, true) => DropStyle::Open,
229 fn clear_drop_flag(&mut self, loc: Location, path: Self::Path, mode: DropFlagMode) {
231 DropFlagMode::Shallow => {
232 self.ctxt.set_drop_flag(loc, path, DropFlagState::Absent);
234 DropFlagMode::Deep => {
235 on_all_children_bits(
238 self.ctxt.move_data(),
240 |child| self.ctxt.set_drop_flag(loc, child, DropFlagState::Absent),
246 fn field_subpath(&self, path: Self::Path, field: Field) -> Option<Self::Path> {
247 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |e| match e {
248 ProjectionElem::Field(idx, _) => *idx == field,
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, |e| match e {
255 ProjectionElem::ConstantIndex { offset, min_length, from_end } => {
256 debug_assert!(size == *min_length, "min_length should be exact for arrays");
257 assert!(!from_end, "from_end should not be used for array element ConstantIndex");
264 fn deref_subpath(&self, path: Self::Path) -> Option<Self::Path> {
265 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |e| {
266 *e == ProjectionElem::Deref
270 fn downcast_subpath(&self, path: Self::Path, variant: VariantIdx) -> Option<Self::Path> {
271 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |e| match e {
272 ProjectionElem::Downcast(_, idx) => *idx == variant,
277 fn get_drop_flag(&mut self, path: Self::Path) -> Option<Operand<'tcx>> {
278 self.ctxt.drop_flag(path).map(Operand::Copy)
282 struct ElaborateDropsCtxt<'a, 'tcx> {
284 body: &'a Body<'tcx>,
285 env: &'a MoveDataParamEnv<'tcx>,
286 flow_inits: DataflowResults<'tcx, MaybeInitializedPlaces<'a, 'tcx>>,
287 flow_uninits: DataflowResults<'tcx, MaybeUninitializedPlaces<'a, 'tcx>>,
288 drop_flags: FxHashMap<MovePathIndex, Local>,
289 patch: MirPatch<'tcx>,
292 impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
293 fn move_data(&self) -> &'b MoveData<'tcx> {
297 fn param_env(&self) -> ty::ParamEnv<'tcx> {
301 fn initialization_data_at(&self, loc: Location) -> InitializationData {
302 let mut data = InitializationData {
303 live: self.flow_inits.sets().entry_set_for(loc.block.index()).to_owned(),
304 dead: self.flow_uninits.sets().entry_set_for(loc.block.index()).to_owned(),
306 for stmt in 0..loc.statement_index {
311 Location { block: loc.block, statement_index: stmt },
317 fn create_drop_flag(&mut self, index: MovePathIndex, span: Span) {
319 let patch = &mut self.patch;
320 debug!("create_drop_flag({:?})", self.body.span);
321 self.drop_flags.entry(index).or_insert_with(|| patch.new_internal(tcx.types.bool, span));
324 fn drop_flag(&mut self, index: MovePathIndex) -> Option<Place<'tcx>> {
325 self.drop_flags.get(&index).map(|t| Place::from(*t))
328 /// create a patch that elaborates all drops in the input
330 fn elaborate(mut self) -> MirPatch<'tcx> {
331 self.collect_drop_flags();
333 self.elaborate_drops();
335 self.drop_flags_on_init();
336 self.drop_flags_for_fn_rets();
337 self.drop_flags_for_args();
338 self.drop_flags_for_locs();
343 fn collect_drop_flags(&mut self) {
344 for (bb, data) in self.body.basic_blocks().iter_enumerated() {
345 let terminator = data.terminator();
346 let location = match terminator.kind {
347 TerminatorKind::Drop { ref location, .. }
348 | TerminatorKind::DropAndReplace { ref location, .. } => location,
352 let init_data = self.initialization_data_at(Location {
354 statement_index: data.statements.len(),
357 let path = self.move_data().rev_lookup.find(location.as_ref());
358 debug!("collect_drop_flags: {:?}, place {:?} ({:?})", bb, location, path);
360 let path = match path {
361 LookupResult::Exact(e) => e,
362 LookupResult::Parent(None) => continue,
363 LookupResult::Parent(Some(parent)) => {
364 let (_maybe_live, maybe_dead) = init_data.state(parent);
367 terminator.source_info.span,
368 "drop of untracked, uninitialized value {:?}, place {:?} ({:?})",
378 on_all_drop_children_bits(self.tcx, self.body, self.env, path, |child| {
379 let (maybe_live, maybe_dead) = init_data.state(child);
381 "collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
385 (maybe_live, maybe_dead)
387 if maybe_live && maybe_dead {
388 self.create_drop_flag(child, terminator.source_info.span)
394 fn elaborate_drops(&mut self) {
395 for (bb, data) in self.body.basic_blocks().iter_enumerated() {
396 let loc = Location { block: bb, statement_index: data.statements.len() };
397 let terminator = data.terminator();
399 let resume_block = self.patch.resume_block();
400 match terminator.kind {
401 TerminatorKind::Drop { ref location, target, unwind } => {
402 let init_data = self.initialization_data_at(loc);
403 match self.move_data().rev_lookup.find(location.as_ref()) {
404 LookupResult::Exact(path) => elaborate_drop(
405 &mut Elaborator { init_data: &init_data, ctxt: self },
406 terminator.source_info,
413 Unwind::To(Option::unwrap_or(unwind, resume_block))
417 LookupResult::Parent(..) => {
419 terminator.source_info.span,
420 "drop of untracked value {:?}",
426 TerminatorKind::DropAndReplace { ref location, ref value, target, unwind } => {
427 assert!(!data.is_cleanup);
429 self.elaborate_replace(loc, location, value, target, unwind);
436 /// Elaborate a MIR `replace` terminator. This instruction
437 /// is not directly handled by codegen, and therefore
438 /// must be desugared.
440 /// The desugaring drops the location if needed, and then writes
441 /// the value (including setting the drop flag) over it in *both* arms.
443 /// The `replace` terminator can also be called on places that
444 /// are not tracked by elaboration (for example,
445 /// `replace x[i] <- tmp0`). The borrow checker requires that
446 /// these locations are initialized before the assignment,
447 /// so we just generate an unconditional drop.
448 fn elaborate_replace(
451 location: &Place<'tcx>,
452 value: &Operand<'tcx>,
454 unwind: Option<BasicBlock>,
457 let data = &self.body[bb];
458 let terminator = data.terminator();
459 assert!(!data.is_cleanup, "DropAndReplace in unwind path not supported");
461 let assign = Statement {
462 kind: StatementKind::Assign(box (location.clone(), Rvalue::Use(value.clone()))),
463 source_info: terminator.source_info,
466 let unwind = unwind.unwrap_or_else(|| self.patch.resume_block());
467 let unwind = self.patch.new_block(BasicBlockData {
468 statements: vec![assign.clone()],
469 terminator: Some(Terminator {
470 kind: TerminatorKind::Goto { target: unwind },
476 let target = self.patch.new_block(BasicBlockData {
477 statements: vec![assign],
478 terminator: Some(Terminator { kind: TerminatorKind::Goto { target }, ..*terminator }),
482 match self.move_data().rev_lookup.find(location.as_ref()) {
483 LookupResult::Exact(path) => {
484 debug!("elaborate_drop_and_replace({:?}) - tracked {:?}", terminator, path);
485 let init_data = self.initialization_data_at(loc);
488 &mut Elaborator { init_data: &init_data, ctxt: self },
489 terminator.source_info,
496 on_all_children_bits(self.tcx, self.body, self.move_data(), path, |child| {
498 Location { block: target, statement_index: 0 },
500 DropFlagState::Present,
503 Location { block: unwind, statement_index: 0 },
505 DropFlagState::Present,
509 LookupResult::Parent(parent) => {
510 // drop and replace behind a pointer/array/whatever. The location
511 // must be initialized.
512 debug!("elaborate_drop_and_replace({:?}) - untracked {:?}", terminator, parent);
513 self.patch.patch_terminator(
515 TerminatorKind::Drop {
516 location: location.clone(),
518 unwind: Some(unwind),
525 fn constant_bool(&self, span: Span, val: bool) -> Rvalue<'tcx> {
526 Rvalue::Use(Operand::Constant(Box::new(Constant {
529 literal: ty::Const::from_bool(self.tcx, val),
533 fn set_drop_flag(&mut self, loc: Location, path: MovePathIndex, val: DropFlagState) {
534 if let Some(&flag) = self.drop_flags.get(&path) {
535 let span = self.patch.source_info_for_location(self.body, loc).span;
536 let val = self.constant_bool(span, val.value());
537 self.patch.add_assign(loc, Place::from(flag), val);
541 fn drop_flags_on_init(&mut self) {
542 let loc = Location::START;
543 let span = self.patch.source_info_for_location(self.body, loc).span;
544 let false_ = self.constant_bool(span, false);
545 for flag in self.drop_flags.values() {
546 self.patch.add_assign(loc, Place::from(*flag), false_.clone());
550 fn drop_flags_for_fn_rets(&mut self) {
551 for (bb, data) in self.body.basic_blocks().iter_enumerated() {
552 if let TerminatorKind::Call {
553 destination: Some((ref place, tgt)),
556 } = data.terminator().kind
558 assert!(!self.patch.is_patched(bb));
560 let loc = Location { block: tgt, statement_index: 0 };
561 let path = self.move_data().rev_lookup.find(place.as_ref());
562 on_lookup_result_bits(self.tcx, self.body, self.move_data(), path, |child| {
563 self.set_drop_flag(loc, child, DropFlagState::Present)
569 fn drop_flags_for_args(&mut self) {
570 let loc = Location::START;
571 dataflow::drop_flag_effects_for_function_entry(self.tcx, self.body, self.env, |path, ds| {
572 self.set_drop_flag(loc, path, ds);
576 fn drop_flags_for_locs(&mut self) {
577 // We intentionally iterate only over the *old* basic blocks.
579 // Basic blocks created by drop elaboration update their
580 // drop flags by themselves, to avoid the drop flags being
581 // clobbered before they are read.
583 for (bb, data) in self.body.basic_blocks().iter_enumerated() {
584 debug!("drop_flags_for_locs({:?})", data);
585 for i in 0..(data.statements.len() + 1) {
586 debug!("drop_flag_for_locs: stmt {}", i);
587 let mut allow_initializations = true;
588 if i == data.statements.len() {
589 match data.terminator().kind {
590 TerminatorKind::Drop { .. } => {
591 // drop elaboration should handle that by itself
594 TerminatorKind::DropAndReplace { .. } => {
595 // this contains the move of the source and
596 // the initialization of the destination. We
597 // only want the former - the latter is handled
598 // by the elaboration code and must be done
599 // *after* the destination is dropped.
600 assert!(self.patch.is_patched(bb));
601 allow_initializations = false;
603 TerminatorKind::Resume => {
604 // It is possible for `Resume` to be patched
605 // (in particular it can be patched to be replaced with
606 // a Goto; see `MirPatch::new`).
609 assert!(!self.patch.is_patched(bb));
613 let loc = Location { block: bb, statement_index: i };
614 dataflow::drop_flag_effects_for_location(
620 if ds == DropFlagState::Absent || allow_initializations {
621 self.set_drop_flag(loc, path, ds)
627 // There may be a critical edge after this call,
628 // so mark the return as initialized *before* the
630 if let TerminatorKind::Call {
631 destination: Some((ref place, _)), cleanup: None, ..
632 } = data.terminator().kind
634 assert!(!self.patch.is_patched(bb));
636 let loc = Location { block: bb, statement_index: data.statements.len() };
637 let path = self.move_data().rev_lookup.find(place.as_ref());
638 on_lookup_result_bits(self.tcx, self.body, self.move_data(), path, |child| {
639 self.set_drop_flag(loc, child, DropFlagState::Present)