1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use dataflow::move_paths::{HasMoveData, MoveData, MovePathIndex, LookupResult};
12 use dataflow::{MaybeInitializedPlaces, MaybeUninitializedPlaces};
13 use dataflow::{DataflowResults};
14 use dataflow::{on_all_children_bits, on_all_drop_children_bits};
15 use dataflow::{drop_flag_effects_for_location, on_lookup_result_bits};
16 use dataflow::MoveDataParamEnv;
17 use dataflow::{self, do_dataflow, DebugFormatted};
18 use rustc::ty::{self, TyCtxt};
20 use rustc::util::nodemap::FxHashMap;
21 use rustc_data_structures::bit_set::BitSet;
25 use transform::{MirPass, MirSource};
26 use util::patch::MirPatch;
27 use util::elaborate_drops::{DropFlagState, Unwind, elaborate_drop};
28 use util::elaborate_drops::{DropElaborator, DropStyle, DropFlagMode};
30 pub struct ElaborateDrops;
32 impl MirPass for ElaborateDrops {
33 fn run_pass<'a, 'tcx>(&self,
34 tcx: TyCtxt<'a, 'tcx, 'tcx>,
38 debug!("elaborate_drops({:?} @ {:?})", src, mir.span);
40 let id = tcx.hir.as_local_node_id(src.def_id).unwrap();
41 let param_env = tcx.param_env(src.def_id).with_reveal_all();
42 let move_data = match MoveData::gather_moves(mir, tcx) {
43 Ok(move_data) => move_data,
44 Err((move_data, _move_errors)) => {
45 // The only way we should be allowing any move_errors
46 // in here is if we are in the migration path for the
47 // NLL-based MIR-borrowck.
49 // If we are in the migration path, we have already
50 // reported these errors as warnings to the user. So
51 // we will just ignore them here.
52 assert!(tcx.migrate_borrowck());
56 let elaborate_patch = {
58 let env = MoveDataParamEnv {
62 let dead_unwinds = find_dead_unwinds(tcx, mir, id, &env);
64 do_dataflow(tcx, mir, id, &[], &dead_unwinds,
65 MaybeInitializedPlaces::new(tcx, mir, &env),
66 |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]));
68 do_dataflow(tcx, mir, id, &[], &dead_unwinds,
69 MaybeUninitializedPlaces::new(tcx, mir, &env),
70 |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]));
78 drop_flags: Default::default(),
79 patch: MirPatch::new(mir),
82 elaborate_patch.apply(mir);
86 /// Return the set of basic blocks whose unwind edges are known
87 /// to not be reachable, because they are `drop` terminators
88 /// that can't drop anything.
89 fn find_dead_unwinds<'a, 'tcx>(
90 tcx: TyCtxt<'a, 'tcx, 'tcx>,
93 env: &MoveDataParamEnv<'tcx, 'tcx>)
96 debug!("find_dead_unwinds({:?})", mir.span);
97 // We only need to do this pass once, because unwind edges can only
98 // reach cleanup blocks, which can't have unwind edges themselves.
99 let mut dead_unwinds = BitSet::new_empty(mir.basic_blocks().len());
101 do_dataflow(tcx, mir, id, &[], &dead_unwinds,
102 MaybeInitializedPlaces::new(tcx, mir, &env),
103 |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]));
104 for (bb, bb_data) in mir.basic_blocks().iter_enumerated() {
105 let location = match bb_data.terminator().kind {
106 TerminatorKind::Drop { ref location, unwind: Some(_), .. } |
107 TerminatorKind::DropAndReplace { ref location, unwind: Some(_), .. } => location,
111 let mut init_data = InitializationData {
112 live: flow_inits.sets().on_entry_set_for(bb.index()).to_owned(),
113 dead: BitSet::new_empty(env.move_data.move_paths.len()),
115 debug!("find_dead_unwinds @ {:?}: {:?}; init_data={:?}",
116 bb, bb_data, init_data.live);
117 for stmt in 0..bb_data.statements.len() {
118 let loc = Location { block: bb, statement_index: stmt };
119 init_data.apply_location(tcx, mir, env, loc);
122 let path = match env.move_data.rev_lookup.find(location) {
123 LookupResult::Exact(e) => e,
124 LookupResult::Parent(..) => {
125 debug!("find_dead_unwinds: has parent; skipping");
130 debug!("find_dead_unwinds @ {:?}: path({:?})={:?}", bb, location, path);
132 let mut maybe_live = false;
133 on_all_drop_children_bits(tcx, mir, &env, path, |child| {
134 let (child_maybe_live, _) = init_data.state(child);
135 maybe_live |= child_maybe_live;
138 debug!("find_dead_unwinds @ {:?}: maybe_live={}", bb, maybe_live);
140 dead_unwinds.insert(bb);
147 struct InitializationData {
148 live: BitSet<MovePathIndex>,
149 dead: BitSet<MovePathIndex>
152 impl InitializationData {
153 fn apply_location<'a,'tcx>(&mut self,
154 tcx: TyCtxt<'a, 'tcx, 'tcx>,
156 env: &MoveDataParamEnv<'tcx, 'tcx>,
159 drop_flag_effects_for_location(tcx, mir, env, loc, |path, df| {
160 debug!("at location {:?}: setting {:?} to {:?}",
163 DropFlagState::Present => {
164 self.live.insert(path);
165 self.dead.remove(path);
167 DropFlagState::Absent => {
168 self.dead.insert(path);
169 self.live.remove(path);
175 fn state(&self, path: MovePathIndex) -> (bool, bool) {
176 (self.live.contains(path), self.dead.contains(path))
180 struct Elaborator<'a, 'b: 'a, 'tcx: 'b> {
181 init_data: &'a InitializationData,
182 ctxt: &'a mut ElaborateDropsCtxt<'b, 'tcx>,
185 impl<'a, 'b, 'tcx> fmt::Debug for Elaborator<'a, 'b, 'tcx> {
186 fn fmt(&self, _f: &mut fmt::Formatter) -> fmt::Result {
191 impl<'a, 'b, 'tcx> DropElaborator<'a, 'tcx> for Elaborator<'a, 'b, 'tcx> {
192 type Path = MovePathIndex;
194 fn patch(&mut self) -> &mut MirPatch<'tcx> {
198 fn mir(&self) -> &'a Mir<'tcx> {
202 fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> {
206 fn param_env(&self) -> ty::ParamEnv<'tcx> {
207 self.ctxt.param_env()
210 fn drop_style(&self, path: Self::Path, mode: DropFlagMode) -> DropStyle {
211 let ((maybe_live, maybe_dead), multipart) = match mode {
212 DropFlagMode::Shallow => (self.init_data.state(path), false),
213 DropFlagMode::Deep => {
214 let mut some_live = false;
215 let mut some_dead = false;
216 let mut children_count = 0;
217 on_all_drop_children_bits(
218 self.tcx(), self.mir(), self.ctxt.env, path, |child| {
219 let (live, dead) = self.init_data.state(child);
220 debug!("elaborate_drop: state({:?}) = {:?}",
221 child, (live, dead));
226 ((some_live, some_dead), children_count != 1)
229 match (maybe_live, maybe_dead, multipart) {
230 (false, _, _) => DropStyle::Dead,
231 (true, false, _) => DropStyle::Static,
232 (true, true, false) => DropStyle::Conditional,
233 (true, true, true) => DropStyle::Open,
237 fn clear_drop_flag(&mut self, loc: Location, path: Self::Path, mode: DropFlagMode) {
239 DropFlagMode::Shallow => {
240 self.ctxt.set_drop_flag(loc, path, DropFlagState::Absent);
242 DropFlagMode::Deep => {
243 on_all_children_bits(
244 self.tcx(), self.mir(), self.ctxt.move_data(), path,
245 |child| self.ctxt.set_drop_flag(loc, child, DropFlagState::Absent)
251 fn field_subpath(&self, path: Self::Path, field: Field) -> Option<Self::Path> {
252 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
255 elem: ProjectionElem::Field(idx, _), ..
262 fn array_subpath(&self, path: Self::Path, index: u32, size: u32) -> Option<Self::Path> {
263 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
266 elem: ProjectionElem::ConstantIndex{offset, min_length: _, from_end: false}, ..
267 } => offset == index,
269 elem: ProjectionElem::ConstantIndex{offset, min_length: _, from_end: true}, ..
270 } => size - offset == index,
276 fn deref_subpath(&self, path: Self::Path) -> Option<Self::Path> {
277 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
279 &Projection { elem: ProjectionElem::Deref, .. } => true,
285 fn downcast_subpath(&self, path: Self::Path, variant: usize) -> Option<Self::Path> {
286 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
289 elem: ProjectionElem::Downcast(_, idx), ..
296 fn get_drop_flag(&mut self, path: Self::Path) -> Option<Operand<'tcx>> {
297 self.ctxt.drop_flag(path).map(Operand::Copy)
301 struct ElaborateDropsCtxt<'a, 'tcx: 'a> {
302 tcx: TyCtxt<'a, 'tcx, 'tcx>,
304 env: &'a MoveDataParamEnv<'tcx, 'tcx>,
305 flow_inits: DataflowResults<MaybeInitializedPlaces<'a, 'tcx, 'tcx>>,
306 flow_uninits: DataflowResults<MaybeUninitializedPlaces<'a, 'tcx, 'tcx>>,
307 drop_flags: FxHashMap<MovePathIndex, Local>,
308 patch: MirPatch<'tcx>,
311 impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
312 fn move_data(&self) -> &'b MoveData<'tcx> { &self.env.move_data }
314 fn param_env(&self) -> ty::ParamEnv<'tcx> {
318 fn initialization_data_at(&self, loc: Location) -> InitializationData {
319 let mut data = InitializationData {
320 live: self.flow_inits.sets().on_entry_set_for(loc.block.index())
322 dead: self.flow_uninits.sets().on_entry_set_for(loc.block.index())
325 for stmt in 0..loc.statement_index {
326 data.apply_location(self.tcx, self.mir, self.env,
327 Location { block: loc.block, statement_index: stmt });
332 fn create_drop_flag(&mut self, index: MovePathIndex, span: Span) {
334 let patch = &mut self.patch;
335 debug!("create_drop_flag({:?})", self.mir.span);
336 self.drop_flags.entry(index).or_insert_with(|| {
337 patch.new_internal(tcx.types.bool, span)
341 fn drop_flag(&mut self, index: MovePathIndex) -> Option<Place<'tcx>> {
342 self.drop_flags.get(&index).map(|t| Place::Local(*t))
345 /// create a patch that elaborates all drops in the input
347 fn elaborate(mut self) -> MirPatch<'tcx>
349 self.collect_drop_flags();
351 self.elaborate_drops();
353 self.drop_flags_on_init();
354 self.drop_flags_for_fn_rets();
355 self.drop_flags_for_args();
356 self.drop_flags_for_locs();
361 fn collect_drop_flags(&mut self)
363 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
364 let terminator = data.terminator();
365 let location = match terminator.kind {
366 TerminatorKind::Drop { ref location, .. } |
367 TerminatorKind::DropAndReplace { ref location, .. } => location,
371 let init_data = self.initialization_data_at(Location {
373 statement_index: data.statements.len()
376 let path = self.move_data().rev_lookup.find(location);
377 debug!("collect_drop_flags: {:?}, place {:?} ({:?})",
380 let path = match path {
381 LookupResult::Exact(e) => e,
382 LookupResult::Parent(None) => continue,
383 LookupResult::Parent(Some(parent)) => {
384 let (_maybe_live, maybe_dead) = init_data.state(parent);
386 span_bug!(terminator.source_info.span,
387 "drop of untracked, uninitialized value {:?}, place {:?} ({:?})",
394 on_all_drop_children_bits(self.tcx, self.mir, self.env, path, |child| {
395 let (maybe_live, maybe_dead) = init_data.state(child);
396 debug!("collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
397 child, location, path, (maybe_live, maybe_dead));
398 if maybe_live && maybe_dead {
399 self.create_drop_flag(child, terminator.source_info.span)
405 fn elaborate_drops(&mut self)
407 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
408 let loc = Location { block: bb, statement_index: data.statements.len() };
409 let terminator = data.terminator();
411 let resume_block = self.patch.resume_block();
412 match terminator.kind {
413 TerminatorKind::Drop { ref location, target, unwind } => {
414 let init_data = self.initialization_data_at(loc);
415 match self.move_data().rev_lookup.find(location) {
416 LookupResult::Exact(path) => {
419 init_data: &init_data,
422 terminator.source_info,
429 Unwind::To(Option::unwrap_or(unwind, resume_block))
433 LookupResult::Parent(..) => {
434 span_bug!(terminator.source_info.span,
435 "drop of untracked value {:?}", bb);
439 TerminatorKind::DropAndReplace { ref location, ref value,
442 assert!(!data.is_cleanup);
444 self.elaborate_replace(
455 /// Elaborate a MIR `replace` terminator. This instruction
456 /// is not directly handled by codegen, and therefore
457 /// must be desugared.
459 /// The desugaring drops the location if needed, and then writes
460 /// the value (including setting the drop flag) over it in *both* arms.
462 /// The `replace` terminator can also be called on places that
463 /// are not tracked by elaboration (for example,
464 /// `replace x[i] <- tmp0`). The borrow checker requires that
465 /// these locations are initialized before the assignment,
466 /// so we just generate an unconditional drop.
467 fn elaborate_replace(
470 location: &Place<'tcx>,
471 value: &Operand<'tcx>,
473 unwind: Option<BasicBlock>)
476 let data = &self.mir[bb];
477 let terminator = data.terminator();
478 assert!(!data.is_cleanup, "DropAndReplace in unwind path not supported");
480 let assign = Statement {
481 kind: StatementKind::Assign(location.clone(), box Rvalue::Use(value.clone())),
482 source_info: terminator.source_info
485 let unwind = unwind.unwrap_or_else(|| self.patch.resume_block());
486 let unwind = self.patch.new_block(BasicBlockData {
487 statements: vec![assign.clone()],
488 terminator: Some(Terminator {
489 kind: TerminatorKind::Goto { target: unwind },
495 let target = self.patch.new_block(BasicBlockData {
496 statements: vec![assign],
497 terminator: Some(Terminator {
498 kind: TerminatorKind::Goto { target: target },
504 match self.move_data().rev_lookup.find(location) {
505 LookupResult::Exact(path) => {
506 debug!("elaborate_drop_and_replace({:?}) - tracked {:?}", terminator, path);
507 let init_data = self.initialization_data_at(loc);
511 init_data: &init_data,
514 terminator.source_info,
520 on_all_children_bits(self.tcx, self.mir, self.move_data(), path, |child| {
521 self.set_drop_flag(Location { block: target, statement_index: 0 },
522 child, DropFlagState::Present);
523 self.set_drop_flag(Location { block: unwind, statement_index: 0 },
524 child, DropFlagState::Present);
527 LookupResult::Parent(parent) => {
528 // drop and replace behind a pointer/array/whatever. The location
529 // must be initialized.
530 debug!("elaborate_drop_and_replace({:?}) - untracked {:?}", terminator, parent);
531 self.patch.patch_terminator(bb, TerminatorKind::Drop {
532 location: location.clone(),
540 fn constant_bool(&self, span: Span, val: bool) -> Rvalue<'tcx> {
541 Rvalue::Use(Operand::Constant(Box::new(Constant {
543 ty: self.tcx.types.bool,
545 literal: ty::Const::from_bool(self.tcx, val),
549 fn set_drop_flag(&mut self, loc: Location, path: MovePathIndex, val: DropFlagState) {
550 if let Some(&flag) = self.drop_flags.get(&path) {
551 let span = self.patch.source_info_for_location(self.mir, loc).span;
552 let val = self.constant_bool(span, val.value());
553 self.patch.add_assign(loc, Place::Local(flag), val);
557 fn drop_flags_on_init(&mut self) {
558 let loc = Location::START;
559 let span = self.patch.source_info_for_location(self.mir, loc).span;
560 let false_ = self.constant_bool(span, false);
561 for flag in self.drop_flags.values() {
562 self.patch.add_assign(loc, Place::Local(*flag), false_.clone());
566 fn drop_flags_for_fn_rets(&mut self) {
567 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
568 if let TerminatorKind::Call {
569 destination: Some((ref place, tgt)), cleanup: Some(_), ..
570 } = data.terminator().kind {
571 assert!(!self.patch.is_patched(bb));
573 let loc = Location { block: tgt, statement_index: 0 };
574 let path = self.move_data().rev_lookup.find(place);
575 on_lookup_result_bits(
576 self.tcx, self.mir, self.move_data(), path,
577 |child| self.set_drop_flag(loc, child, DropFlagState::Present)
583 fn drop_flags_for_args(&mut self) {
584 let loc = Location::START;
585 dataflow::drop_flag_effects_for_function_entry(
586 self.tcx, self.mir, self.env, |path, ds| {
587 self.set_drop_flag(loc, path, ds);
592 fn drop_flags_for_locs(&mut self) {
593 // We intentionally iterate only over the *old* basic blocks.
595 // Basic blocks created by drop elaboration update their
596 // drop flags by themselves, to avoid the drop flags being
597 // clobbered before they are read.
599 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
600 debug!("drop_flags_for_locs({:?})", data);
601 for i in 0..(data.statements.len()+1) {
602 debug!("drop_flag_for_locs: stmt {}", i);
603 let mut allow_initializations = true;
604 if i == data.statements.len() {
605 match data.terminator().kind {
606 TerminatorKind::Drop { .. } => {
607 // drop elaboration should handle that by itself
610 TerminatorKind::DropAndReplace { .. } => {
611 // this contains the move of the source and
612 // the initialization of the destination. We
613 // only want the former - the latter is handled
614 // by the elaboration code and must be done
615 // *after* the destination is dropped.
616 assert!(self.patch.is_patched(bb));
617 allow_initializations = false;
619 TerminatorKind::Resume => {
620 // It is possible for `Resume` to be patched
621 // (in particular it can be patched to be replaced with
622 // a Goto; see `MirPatch::new`).
625 assert!(!self.patch.is_patched(bb));
629 let loc = Location { block: bb, statement_index: i };
630 dataflow::drop_flag_effects_for_location(
631 self.tcx, self.mir, self.env, loc, |path, ds| {
632 if ds == DropFlagState::Absent || allow_initializations {
633 self.set_drop_flag(loc, path, ds)
639 // There may be a critical edge after this call,
640 // so mark the return as initialized *before* the
642 if let TerminatorKind::Call {
643 destination: Some((ref place, _)), cleanup: None, ..
644 } = data.terminator().kind {
645 assert!(!self.patch.is_patched(bb));
647 let loc = Location { block: bb, statement_index: data.statements.len() };
648 let path = self.move_data().rev_lookup.find(place);
649 on_lookup_result_bits(
650 self.tcx, self.mir, self.move_data(), path,
651 |child| self.set_drop_flag(loc, child, DropFlagState::Present)