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 super::gather_moves::{HasMoveData, MoveData, MovePathIndex, LookupResult};
12 use super::dataflow::{MaybeInitializedLvals, MaybeUninitializedLvals};
13 use super::dataflow::{DataflowResults};
14 use super::{on_all_children_bits, on_all_drop_children_bits};
15 use super::{drop_flag_effects_for_location, on_lookup_result_bits};
16 use super::MoveDataParamEnv;
17 use rustc::ty::{self, TyCtxt};
19 use rustc::mir::transform::{MirPass, MirSource};
20 use rustc::middle::const_val::ConstVal;
21 use rustc::util::nodemap::FxHashMap;
22 use rustc_data_structures::indexed_set::IdxSetBuf;
23 use rustc_data_structures::indexed_vec::Idx;
24 use rustc_mir::util::patch::MirPatch;
25 use rustc_mir::util::elaborate_drops::{DropFlagState, elaborate_drop};
26 use rustc_mir::util::elaborate_drops::{DropElaborator, DropStyle, DropFlagMode};
33 pub struct ElaborateDrops;
35 impl MirPass for ElaborateDrops {
36 fn run_pass<'a, 'tcx>(&self,
37 tcx: TyCtxt<'a, 'tcx, 'tcx>,
41 debug!("elaborate_drops({:?} @ {:?})", src, mir.span);
43 MirSource::Fn(..) => {},
46 let id = src.item_id();
47 let param_env = tcx.parameter_environment(tcx.hir.local_def_id(id));
48 let move_data = MoveData::gather_moves(mir, tcx, ¶m_env);
49 let elaborate_patch = {
51 let env = MoveDataParamEnv {
55 let dead_unwinds = find_dead_unwinds(tcx, mir, id, &env);
57 super::do_dataflow(tcx, mir, id, &[], &dead_unwinds,
58 MaybeInitializedLvals::new(tcx, mir, &env),
59 |bd, p| &bd.move_data().move_paths[p]);
61 super::do_dataflow(tcx, mir, id, &[], &dead_unwinds,
62 MaybeUninitializedLvals::new(tcx, mir, &env),
63 |bd, p| &bd.move_data().move_paths[p]);
69 flow_inits: flow_inits,
70 flow_uninits: flow_uninits,
71 drop_flags: FxHashMap(),
72 patch: MirPatch::new(mir),
75 elaborate_patch.apply(mir);
79 /// Return the set of basic blocks whose unwind edges are known
80 /// to not be reachable, because they are `drop` terminators
81 /// that can't drop anything.
82 fn find_dead_unwinds<'a, 'tcx>(
83 tcx: TyCtxt<'a, 'tcx, 'tcx>,
86 env: &MoveDataParamEnv<'tcx>)
87 -> IdxSetBuf<BasicBlock>
89 debug!("find_dead_unwinds({:?})", mir.span);
90 // We only need to do this pass once, because unwind edges can only
91 // reach cleanup blocks, which can't have unwind edges themselves.
92 let mut dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len());
94 super::do_dataflow(tcx, mir, id, &[], &dead_unwinds,
95 MaybeInitializedLvals::new(tcx, mir, &env),
96 |bd, p| &bd.move_data().move_paths[p]);
97 for (bb, bb_data) in mir.basic_blocks().iter_enumerated() {
98 match bb_data.terminator().kind {
99 TerminatorKind::Drop { ref location, unwind: Some(_), .. } |
100 TerminatorKind::DropAndReplace { ref location, unwind: Some(_), .. } => {
101 let mut init_data = InitializationData {
102 live: flow_inits.sets().on_entry_set_for(bb.index()).to_owned(),
103 dead: IdxSetBuf::new_empty(env.move_data.move_paths.len()),
105 debug!("find_dead_unwinds @ {:?}: {:?}; init_data={:?}",
106 bb, bb_data, init_data.live);
107 for stmt in 0..bb_data.statements.len() {
108 let loc = Location { block: bb, statement_index: stmt };
109 init_data.apply_location(tcx, mir, env, loc);
112 let path = match env.move_data.rev_lookup.find(location) {
113 LookupResult::Exact(e) => e,
114 LookupResult::Parent(..) => {
115 debug!("find_dead_unwinds: has parent; skipping");
120 debug!("find_dead_unwinds @ {:?}: path({:?})={:?}", bb, location, path);
122 let mut maybe_live = false;
123 on_all_drop_children_bits(tcx, mir, &env, path, |child| {
124 let (child_maybe_live, _) = init_data.state(child);
125 maybe_live |= child_maybe_live;
128 debug!("find_dead_unwinds @ {:?}: maybe_live={}", bb, maybe_live);
130 dead_unwinds.add(&bb);
140 struct InitializationData {
141 live: IdxSetBuf<MovePathIndex>,
142 dead: IdxSetBuf<MovePathIndex>
145 impl InitializationData {
146 fn apply_location<'a,'tcx>(&mut self,
147 tcx: TyCtxt<'a, 'tcx, 'tcx>,
149 env: &MoveDataParamEnv<'tcx>,
152 drop_flag_effects_for_location(tcx, mir, env, loc, |path, df| {
153 debug!("at location {:?}: setting {:?} to {:?}",
156 DropFlagState::Present => {
157 self.live.add(&path);
158 self.dead.remove(&path);
160 DropFlagState::Absent => {
161 self.dead.add(&path);
162 self.live.remove(&path);
168 fn state(&self, path: MovePathIndex) -> (bool, bool) {
169 (self.live.contains(&path), self.dead.contains(&path))
173 struct Elaborator<'a, 'b: 'a, 'tcx: 'b> {
174 init_data: &'a InitializationData,
175 ctxt: &'a mut ElaborateDropsCtxt<'b, 'tcx>,
178 impl<'a, 'b, 'tcx> fmt::Debug for Elaborator<'a, 'b, 'tcx> {
179 fn fmt(&self, _f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
184 impl<'a, 'b, 'tcx> DropElaborator<'a, 'tcx> for Elaborator<'a, 'b, 'tcx> {
185 type Path = MovePathIndex;
187 fn patch(&mut self) -> &mut MirPatch<'tcx> {
191 fn mir(&self) -> &'a Mir<'tcx> {
195 fn tcx(&self) -> ty::TyCtxt<'a, 'tcx, 'tcx> {
199 fn param_env(&self) -> &'a ty::ParameterEnvironment<'tcx> {
200 self.ctxt.param_env()
203 fn drop_style(&self, path: Self::Path, mode: DropFlagMode) -> DropStyle {
204 let ((maybe_live, maybe_dead), multipart) = match mode {
205 DropFlagMode::Shallow => (self.init_data.state(path), false),
206 DropFlagMode::Deep => {
207 let mut some_live = false;
208 let mut some_dead = false;
209 let mut children_count = 0;
210 on_all_drop_children_bits(
211 self.tcx(), self.mir(), self.ctxt.env, path, |child| {
212 let (live, dead) = self.init_data.state(child);
213 debug!("elaborate_drop: state({:?}) = {:?}",
214 child, (live, dead));
219 ((some_live, some_dead), children_count != 1)
222 match (maybe_live, maybe_dead, multipart) {
223 (false, _, _) => DropStyle::Dead,
224 (true, false, _) => DropStyle::Static,
225 (true, true, false) => DropStyle::Conditional,
226 (true, true, true) => DropStyle::Open,
230 fn clear_drop_flag(&mut self, loc: Location, path: Self::Path, mode: DropFlagMode) {
232 DropFlagMode::Shallow => {
233 self.ctxt.set_drop_flag(loc, path, DropFlagState::Absent);
235 DropFlagMode::Deep => {
236 on_all_children_bits(
237 self.tcx(), self.mir(), self.ctxt.move_data(), path,
238 |child| self.ctxt.set_drop_flag(loc, child, DropFlagState::Absent)
244 fn field_subpath(&self, path: Self::Path, field: Field) -> Option<Self::Path> {
245 super::move_path_children_matching(self.ctxt.move_data(), path, |p| {
248 elem: ProjectionElem::Field(idx, _), ..
255 fn deref_subpath(&self, path: Self::Path) -> Option<Self::Path> {
256 super::move_path_children_matching(self.ctxt.move_data(), path, |p| {
258 &Projection { elem: ProjectionElem::Deref, .. } => true,
264 fn downcast_subpath(&self, path: Self::Path, variant: usize) -> Option<Self::Path> {
265 super::move_path_children_matching(self.ctxt.move_data(), path, |p| {
268 elem: ProjectionElem::Downcast(_, idx), ..
275 fn get_drop_flag(&mut self, path: Self::Path) -> Option<Operand<'tcx>> {
276 self.ctxt.drop_flag(path).map(Operand::Consume)
280 struct ElaborateDropsCtxt<'a, 'tcx: 'a> {
281 tcx: TyCtxt<'a, 'tcx, 'tcx>,
283 env: &'a MoveDataParamEnv<'tcx>,
284 flow_inits: DataflowResults<MaybeInitializedLvals<'a, 'tcx>>,
285 flow_uninits: DataflowResults<MaybeUninitializedLvals<'a, 'tcx>>,
286 drop_flags: FxHashMap<MovePathIndex, Local>,
287 patch: MirPatch<'tcx>,
290 impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
291 fn move_data(&self) -> &'b MoveData<'tcx> { &self.env.move_data }
292 fn param_env(&self) -> &'b ty::ParameterEnvironment<'tcx> {
296 fn initialization_data_at(&self, loc: Location) -> InitializationData {
297 let mut data = InitializationData {
298 live: self.flow_inits.sets().on_entry_set_for(loc.block.index())
300 dead: self.flow_uninits.sets().on_entry_set_for(loc.block.index())
303 for stmt in 0..loc.statement_index {
304 data.apply_location(self.tcx, self.mir, self.env,
305 Location { block: loc.block, statement_index: stmt });
310 fn create_drop_flag(&mut self, index: MovePathIndex, span: Span) {
312 let patch = &mut self.patch;
313 debug!("create_drop_flag({:?})", self.mir.span);
314 self.drop_flags.entry(index).or_insert_with(|| {
315 patch.new_temp(tcx.types.bool, span)
319 fn drop_flag(&mut self, index: MovePathIndex) -> Option<Lvalue<'tcx>> {
320 self.drop_flags.get(&index).map(|t| Lvalue::Local(*t))
323 /// create a patch that elaborates all drops in the input
325 fn elaborate(mut self) -> MirPatch<'tcx>
327 self.collect_drop_flags();
329 self.elaborate_drops();
331 self.drop_flags_on_init();
332 self.drop_flags_for_fn_rets();
333 self.drop_flags_for_args();
334 self.drop_flags_for_locs();
339 fn collect_drop_flags(&mut self)
341 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
342 let terminator = data.terminator();
343 let location = match terminator.kind {
344 TerminatorKind::Drop { ref location, .. } |
345 TerminatorKind::DropAndReplace { ref location, .. } => location,
349 let init_data = self.initialization_data_at(Location {
351 statement_index: data.statements.len()
354 let path = self.move_data().rev_lookup.find(location);
355 debug!("collect_drop_flags: {:?}, lv {:?} ({:?})",
358 let path = match path {
359 LookupResult::Exact(e) => e,
360 LookupResult::Parent(None) => continue,
361 LookupResult::Parent(Some(parent)) => {
362 let (_maybe_live, maybe_dead) = init_data.state(parent);
364 span_bug!(terminator.source_info.span,
365 "drop of untracked, uninitialized value {:?}, lv {:?} ({:?})",
372 on_all_drop_children_bits(self.tcx, self.mir, self.env, path, |child| {
373 let (maybe_live, maybe_dead) = init_data.state(child);
374 debug!("collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
375 child, location, path, (maybe_live, maybe_dead));
376 if maybe_live && maybe_dead {
377 self.create_drop_flag(child, terminator.source_info.span)
383 fn elaborate_drops(&mut self)
385 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
386 let loc = Location { block: bb, statement_index: data.statements.len() };
387 let terminator = data.terminator();
389 let resume_block = self.patch.resume_block();
390 match terminator.kind {
391 TerminatorKind::Drop { ref location, target, unwind } => {
392 let init_data = self.initialization_data_at(loc);
393 match self.move_data().rev_lookup.find(location) {
394 LookupResult::Exact(path) => {
397 init_data: &init_data,
400 terminator.source_info,
408 Some(Option::unwrap_or(unwind, resume_block))
412 LookupResult::Parent(..) => {
413 span_bug!(terminator.source_info.span,
414 "drop of untracked value {:?}", bb);
418 TerminatorKind::DropAndReplace { ref location, ref value,
421 assert!(!data.is_cleanup);
423 self.elaborate_replace(
434 /// Elaborate a MIR `replace` terminator. This instruction
435 /// is not directly handled by translation, and therefore
436 /// must be desugared.
438 /// The desugaring drops the location if needed, and then writes
439 /// the value (including setting the drop flag) over it in *both* arms.
441 /// The `replace` terminator can also be called on lvalues that
442 /// are not tracked by elaboration (for example,
443 /// `replace x[i] <- tmp0`). The borrow checker requires that
444 /// these locations are initialized before the assignment,
445 /// so we just generate an unconditional drop.
446 fn elaborate_replace(
449 location: &Lvalue<'tcx>,
450 value: &Operand<'tcx>,
452 unwind: Option<BasicBlock>)
455 let data = &self.mir[bb];
456 let terminator = data.terminator();
458 let assign = Statement {
459 kind: StatementKind::Assign(location.clone(), Rvalue::Use(value.clone())),
460 source_info: terminator.source_info
463 let unwind = unwind.unwrap_or(self.patch.resume_block());
464 let unwind = self.patch.new_block(BasicBlockData {
465 statements: vec![assign.clone()],
466 terminator: Some(Terminator {
467 kind: TerminatorKind::Goto { target: unwind },
473 let target = self.patch.new_block(BasicBlockData {
474 statements: vec![assign],
475 terminator: Some(Terminator {
476 kind: TerminatorKind::Goto { target: target },
479 is_cleanup: data.is_cleanup,
482 match self.move_data().rev_lookup.find(location) {
483 LookupResult::Exact(path) => {
484 debug!("elaborate_drop_and_replace({:?}) - tracked {:?}", terminator, path);
485 let init_data = self.initialization_data_at(loc);
489 init_data: &init_data,
492 terminator.source_info,
499 on_all_children_bits(self.tcx, self.mir, self.move_data(), path, |child| {
500 self.set_drop_flag(Location { block: target, statement_index: 0 },
501 child, DropFlagState::Present);
502 self.set_drop_flag(Location { block: unwind, statement_index: 0 },
503 child, DropFlagState::Present);
506 LookupResult::Parent(parent) => {
507 // drop and replace behind a pointer/array/whatever. The location
508 // must be initialized.
509 debug!("elaborate_drop_and_replace({:?}) - untracked {:?}", terminator, parent);
510 self.patch.patch_terminator(bb, TerminatorKind::Drop {
511 location: location.clone(),
519 fn constant_bool(&self, span: Span, val: bool) -> Rvalue<'tcx> {
520 Rvalue::Use(Operand::Constant(Box::new(Constant {
522 ty: self.tcx.types.bool,
523 literal: Literal::Value { value: ConstVal::Bool(val) }
527 fn set_drop_flag(&mut self, loc: Location, path: MovePathIndex, val: DropFlagState) {
528 if let Some(&flag) = self.drop_flags.get(&path) {
529 let span = self.patch.source_info_for_location(self.mir, loc).span;
530 let val = self.constant_bool(span, val.value());
531 self.patch.add_assign(loc, Lvalue::Local(flag), val);
535 fn drop_flags_on_init(&mut self) {
536 let loc = Location { block: START_BLOCK, statement_index: 0 };
537 let span = self.patch.source_info_for_location(self.mir, loc).span;
538 let false_ = self.constant_bool(span, false);
539 for flag in self.drop_flags.values() {
540 self.patch.add_assign(loc, Lvalue::Local(*flag), false_.clone());
544 fn drop_flags_for_fn_rets(&mut self) {
545 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
546 if let TerminatorKind::Call {
547 destination: Some((ref lv, tgt)), cleanup: Some(_), ..
548 } = data.terminator().kind {
549 assert!(!self.patch.is_patched(bb));
551 let loc = Location { block: tgt, statement_index: 0 };
552 let path = self.move_data().rev_lookup.find(lv);
553 on_lookup_result_bits(
554 self.tcx, self.mir, self.move_data(), path,
555 |child| self.set_drop_flag(loc, child, DropFlagState::Present)
561 fn drop_flags_for_args(&mut self) {
562 let loc = Location { block: START_BLOCK, statement_index: 0 };
563 super::drop_flag_effects_for_function_entry(
564 self.tcx, self.mir, self.env, |path, ds| {
565 self.set_drop_flag(loc, path, ds);
570 fn drop_flags_for_locs(&mut self) {
571 // We intentionally iterate only over the *old* basic blocks.
573 // Basic blocks created by drop elaboration update their
574 // drop flags by themselves, to avoid the drop flags being
575 // clobbered before they are read.
577 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
578 debug!("drop_flags_for_locs({:?})", data);
579 for i in 0..(data.statements.len()+1) {
580 debug!("drop_flag_for_locs: stmt {}", i);
581 let mut allow_initializations = true;
582 if i == data.statements.len() {
583 match data.terminator().kind {
584 TerminatorKind::Drop { .. } => {
585 // drop elaboration should handle that by itself
588 TerminatorKind::DropAndReplace { .. } => {
589 // this contains the move of the source and
590 // the initialization of the destination. We
591 // only want the former - the latter is handled
592 // by the elaboration code and must be done
593 // *after* the destination is dropped.
594 assert!(self.patch.is_patched(bb));
595 allow_initializations = false;
598 assert!(!self.patch.is_patched(bb));
602 let loc = Location { block: bb, statement_index: i };
603 super::drop_flag_effects_for_location(
604 self.tcx, self.mir, self.env, loc, |path, ds| {
605 if ds == DropFlagState::Absent || allow_initializations {
606 self.set_drop_flag(loc, path, ds)
612 // There may be a critical edge after this call,
613 // so mark the return as initialized *before* the
615 if let TerminatorKind::Call {
616 destination: Some((ref lv, _)), cleanup: None, ..
617 } = data.terminator().kind {
618 assert!(!self.patch.is_patched(bb));
620 let loc = Location { block: bb, statement_index: data.statements.len() };
621 let path = self.move_data().rev_lookup.find(lv);
622 on_lookup_result_bits(
623 self.tcx, self.mir, self.move_data(), path,
624 |child| self.set_drop_flag(loc, child, DropFlagState::Present)