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};
16 use rustc_target::abi::VariantIdx;
19 pub struct ElaborateDrops;
21 impl<'tcx> MirPass<'tcx> for ElaborateDrops {
22 fn phase_change(&self) -> Option<MirPhase> {
23 Some(MirPhase::DropLowering)
26 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
27 debug!("elaborate_drops({:?} @ {:?})", body.source, body.span);
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(
36 "No `move_errors` should be allowed in MIR borrowck",
41 let elaborate_patch = {
43 let env = MoveDataParamEnv { move_data, param_env };
44 let dead_unwinds = find_dead_unwinds(tcx, body, &env);
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);
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);
65 init_data: InitializationData { inits, uninits },
66 drop_flags: Default::default(),
67 patch: MirPatch::new(body),
71 elaborate_patch.apply(body);
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>(
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,
99 debug!("find_dead_unwinds @ {:?}: {:?}", bb, bb_data);
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");
109 flow_inits.seek_before_primary_effect(body.terminator_loc(bb));
111 "find_dead_unwinds @ {:?}: path({:?})={:?}; init_data={:?}",
118 let mut maybe_live = false;
119 on_all_drop_children_bits(tcx, body, &env, path, |child| {
120 maybe_live |= flow_inits.contains(child);
123 debug!("find_dead_unwinds @ {:?}: maybe_live={}", bb, maybe_live);
125 dead_unwinds.insert(bb);
132 struct InitializationData<'mir, 'tcx> {
133 inits: ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>,
134 uninits: ResultsCursor<'mir, 'tcx, MaybeUninitializedPlaces<'mir, 'tcx>>,
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);
143 fn maybe_live_dead(&self, path: MovePathIndex) -> (bool, bool) {
144 (self.inits.contains(path), self.uninits.contains(path))
148 struct Elaborator<'a, 'b, 'tcx> {
149 ctxt: &'a mut ElaborateDropsCtxt<'b, 'tcx>,
152 impl fmt::Debug for Elaborator<'_, '_, '_> {
153 fn fmt(&self, _f: &mut fmt::Formatter<'_>) -> fmt::Result {
158 impl<'a, 'tcx> DropElaborator<'a, 'tcx> for Elaborator<'a, '_, 'tcx> {
159 type Path = MovePathIndex;
161 fn patch(&mut self) -> &mut MirPatch<'tcx> {
165 fn body(&self) -> &'a Body<'tcx> {
169 fn tcx(&self) -> TyCtxt<'tcx> {
173 fn param_env(&self) -> ty::ParamEnv<'tcx> {
174 self.ctxt.param_env()
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));
191 ((some_live, some_dead), children_count != 1)
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,
202 fn clear_drop_flag(&mut self, loc: Location, path: Self::Path, mode: DropFlagMode) {
204 DropFlagMode::Shallow => {
205 self.ctxt.set_drop_flag(loc, path, DropFlagState::Absent);
207 DropFlagMode::Deep => {
208 on_all_children_bits(
211 self.ctxt.move_data(),
213 |child| self.ctxt.set_drop_flag(loc, child, DropFlagState::Absent),
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,
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");
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
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,
250 fn get_drop_flag(&mut self, path: Self::Path) -> Option<Operand<'tcx>> {
251 self.ctxt.drop_flag(path).map(Operand::Copy)
255 struct ElaborateDropsCtxt<'a, '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>,
264 impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
265 fn move_data(&self) -> &'b MoveData<'tcx> {
269 fn param_env(&self) -> ty::ParamEnv<'tcx> {
273 fn create_drop_flag(&mut self, index: MovePathIndex, span: Span) {
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));
280 fn drop_flag(&mut self, index: MovePathIndex) -> Option<Place<'tcx>> {
281 self.drop_flags.get(&index).map(|t| Place::from(*t))
284 /// create a patch that elaborates all drops in the input
286 fn elaborate(mut self) -> MirPatch<'tcx> {
287 self.collect_drop_flags();
289 self.elaborate_drops();
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();
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,
308 self.init_data.seek_before(self.body.terminator_loc(bb));
310 let path = self.move_data().rev_lookup.find(place.as_ref());
311 debug!("collect_drop_flags: {:?}, place {:?} ({:?})", bb, place, path);
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);
319 self.tcx.sess.delay_span_bug(
320 terminator.source_info.span,
322 "drop of untracked, uninitialized value {:?}, place {:?} ({:?})",
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);
334 "collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
338 (maybe_live, maybe_dead)
340 if maybe_live && maybe_dead {
341 self.create_drop_flag(child, terminator.source_info.span)
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();
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,
366 Unwind::To(Option::unwrap_or(unwind, resume_block))
370 LookupResult::Parent(..) => {
371 self.tcx.sess.delay_span_bug(
372 terminator.source_info.span,
373 &format!("drop of untracked value {:?}", bb),
378 TerminatorKind::DropAndReplace { place, ref value, target, unwind } => {
379 assert!(!data.is_cleanup);
381 self.elaborate_replace(loc, place, value, target, unwind);
388 /// Elaborate a MIR `replace` terminator. This instruction
389 /// is not directly handled by codegen, and therefore
390 /// must be desugared.
392 /// The desugaring drops the location if needed, and then writes
393 /// the value (including setting the drop flag) over it in *both* arms.
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(
404 value: &Operand<'tcx>,
406 unwind: Option<BasicBlock>,
409 let data = &self.body[bb];
410 let terminator = data.terminator();
411 assert!(!data.is_cleanup, "DropAndReplace in unwind path not supported");
413 let assign = Statement {
414 kind: StatementKind::Assign(Box::new((place, Rvalue::Use(value.clone())))),
415 source_info: terminator.source_info,
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 },
428 let target = self.patch.new_block(BasicBlockData {
429 statements: vec![assign],
430 terminator: Some(Terminator { kind: TerminatorKind::Goto { target }, ..*terminator }),
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);
439 &mut Elaborator { ctxt: self },
440 terminator.source_info,
447 on_all_children_bits(self.tcx, self.body, self.move_data(), path, |child| {
449 Location { block: target, statement_index: 0 },
451 DropFlagState::Present,
454 Location { block: unwind, statement_index: 0 },
456 DropFlagState::Present,
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(
466 TerminatorKind::Drop { place, target, unwind: Some(unwind) },
472 fn constant_bool(&self, span: Span, val: bool) -> Rvalue<'tcx> {
473 Rvalue::Use(Operand::Constant(Box::new(Constant {
476 literal: ty::Const::from_bool(self.tcx, val).into(),
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);
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());
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)),
503 } = data.terminator().kind
505 assert!(!self.patch.is_patched(bb));
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)
516 fn drop_flags_for_args(&mut self) {
517 let loc = Location::START;
518 rustc_mir_dataflow::drop_flag_effects_for_function_entry(
523 self.set_drop_flag(loc, path, ds);
528 fn drop_flags_for_locs(&mut self) {
529 // We intentionally iterate only over the *old* basic blocks.
531 // Basic blocks created by drop elaboration update their
532 // drop flags by themselves, to avoid the drop flags being
533 // clobbered before they are read.
535 for (bb, data) in self.body.basic_blocks().iter_enumerated() {
536 debug!("drop_flags_for_locs({:?})", data);
537 for i in 0..(data.statements.len() + 1) {
538 debug!("drop_flag_for_locs: stmt {}", i);
539 let mut allow_initializations = true;
540 if i == data.statements.len() {
541 match data.terminator().kind {
542 TerminatorKind::Drop { .. } => {
543 // drop elaboration should handle that by itself
546 TerminatorKind::DropAndReplace { .. } => {
547 // this contains the move of the source and
548 // the initialization of the destination. We
549 // only want the former - the latter is handled
550 // by the elaboration code and must be done
551 // *after* the destination is dropped.
552 assert!(self.patch.is_patched(bb));
553 allow_initializations = false;
555 TerminatorKind::Resume => {
556 // It is possible for `Resume` to be patched
557 // (in particular it can be patched to be replaced with
558 // a Goto; see `MirPatch::new`).
561 assert!(!self.patch.is_patched(bb));
565 let loc = Location { block: bb, statement_index: i };
566 rustc_mir_dataflow::drop_flag_effects_for_location(
572 if ds == DropFlagState::Absent || allow_initializations {
573 self.set_drop_flag(loc, path, ds)
579 // There may be a critical edge after this call,
580 // so mark the return as initialized *before* the
582 if let TerminatorKind::Call {
583 destination: Some((ref place, _)), cleanup: None, ..
584 } = data.terminator().kind
586 assert!(!self.patch.is_patched(bb));
588 let loc = Location { block: bb, statement_index: data.statements.len() };
589 let path = self.move_data().rev_lookup.find(place.as_ref());
590 on_lookup_result_bits(self.tcx, self.body, self.move_data(), path, |child| {
591 self.set_drop_flag(loc, child, DropFlagState::Present)