]> git.proxmox.com Git - rustc.git/blob - src/librustc_mir/transform/elaborate_drops.rs
New upstream version 1.39.0+dfsg1
[rustc.git] / src / librustc_mir / transform / elaborate_drops.rs
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;
14 use rustc::hir;
15 use rustc::mir::*;
16 use rustc::util::nodemap::FxHashMap;
17 use rustc_data_structures::bit_set::BitSet;
18 use std::fmt;
19 use syntax_pos::Span;
20
21 pub struct ElaborateDrops;
22
23 impl<'tcx> MirPass<'tcx> for ElaborateDrops {
24 fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut Body<'tcx>) {
25 debug!("elaborate_drops({:?} @ {:?})", src, body.span);
26
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) {
30 Ok(move_data) => move_data,
31 Err((move_data, _move_errors)) => {
32 // The only way we should be allowing any move_errors
33 // in here is if we are in the migration path for the
34 // NLL-based MIR-borrowck.
35 //
36 // If we are in the migration path, we have already
37 // reported these errors as warnings to the user. So
38 // we will just ignore them here.
39 assert!(tcx.migrate_borrowck());
40 move_data
41 }
42 };
43 let elaborate_patch = {
44 let body = &*body;
45 let env = MoveDataParamEnv {
46 move_data,
47 param_env,
48 };
49 let dead_unwinds = find_dead_unwinds(tcx, body, def_id, &env);
50 let flow_inits =
51 do_dataflow(tcx, body, def_id, &[], &dead_unwinds,
52 MaybeInitializedPlaces::new(tcx, body, &env),
53 |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]));
54 let flow_uninits =
55 do_dataflow(tcx, body, def_id, &[], &dead_unwinds,
56 MaybeUninitializedPlaces::new(tcx, body, &env),
57 |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]));
58
59 ElaborateDropsCtxt {
60 tcx,
61 body,
62 env: &env,
63 flow_inits,
64 flow_uninits,
65 drop_flags: Default::default(),
66 patch: MirPatch::new(body),
67 }.elaborate()
68 };
69 elaborate_patch.apply(body);
70 }
71 }
72
73 /// Returns the set of basic blocks whose unwind edges are known
74 /// to not be reachable, because they are `drop` terminators
75 /// that can't drop anything.
76 fn find_dead_unwinds<'tcx>(
77 tcx: TyCtxt<'tcx>,
78 body: &Body<'tcx>,
79 def_id: hir::def_id::DefId,
80 env: &MoveDataParamEnv<'tcx>,
81 ) -> BitSet<BasicBlock> {
82 debug!("find_dead_unwinds({:?})", body.span);
83 // We only need to do this pass once, because unwind edges can only
84 // reach cleanup blocks, which can't have unwind edges themselves.
85 let mut dead_unwinds = BitSet::new_empty(body.basic_blocks().len());
86 let flow_inits =
87 do_dataflow(tcx, body, def_id, &[], &dead_unwinds,
88 MaybeInitializedPlaces::new(tcx, body, &env),
89 |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]));
90 for (bb, bb_data) in body.basic_blocks().iter_enumerated() {
91 let location = match bb_data.terminator().kind {
92 TerminatorKind::Drop { ref location, unwind: Some(_), .. } |
93 TerminatorKind::DropAndReplace { ref location, unwind: Some(_), .. } => location,
94 _ => continue,
95 };
96
97 let mut init_data = InitializationData {
98 live: flow_inits.sets().entry_set_for(bb.index()).to_owned(),
99 dead: BitSet::new_empty(env.move_data.move_paths.len()),
100 };
101 debug!("find_dead_unwinds @ {:?}: {:?}; init_data={:?}",
102 bb, bb_data, init_data.live);
103 for stmt in 0..bb_data.statements.len() {
104 let loc = Location { block: bb, statement_index: stmt };
105 init_data.apply_location(tcx, body, env, loc);
106 }
107
108 let path = match env.move_data.rev_lookup.find(location.as_ref()) {
109 LookupResult::Exact(e) => e,
110 LookupResult::Parent(..) => {
111 debug!("find_dead_unwinds: has parent; skipping");
112 continue
113 }
114 };
115
116 debug!("find_dead_unwinds @ {:?}: path({:?})={:?}", bb, location, path);
117
118 let mut maybe_live = false;
119 on_all_drop_children_bits(tcx, body, &env, path, |child| {
120 let (child_maybe_live, _) = init_data.state(child);
121 maybe_live |= child_maybe_live;
122 });
123
124 debug!("find_dead_unwinds @ {:?}: maybe_live={}", bb, maybe_live);
125 if !maybe_live {
126 dead_unwinds.insert(bb);
127 }
128 }
129
130 dead_unwinds
131 }
132
133 struct InitializationData {
134 live: BitSet<MovePathIndex>,
135 dead: BitSet<MovePathIndex>
136 }
137
138 impl InitializationData {
139 fn apply_location<'tcx>(
140 &mut self,
141 tcx: TyCtxt<'tcx>,
142 body: &Body<'tcx>,
143 env: &MoveDataParamEnv<'tcx>,
144 loc: Location,
145 ) {
146 drop_flag_effects_for_location(tcx, body, env, loc, |path, df| {
147 debug!("at location {:?}: setting {:?} to {:?}",
148 loc, path, df);
149 match df {
150 DropFlagState::Present => {
151 self.live.insert(path);
152 self.dead.remove(path);
153 }
154 DropFlagState::Absent => {
155 self.dead.insert(path);
156 self.live.remove(path);
157 }
158 }
159 });
160 }
161
162 fn state(&self, path: MovePathIndex) -> (bool, bool) {
163 (self.live.contains(path), self.dead.contains(path))
164 }
165 }
166
167 struct Elaborator<'a, 'b, 'tcx> {
168 init_data: &'a InitializationData,
169 ctxt: &'a mut ElaborateDropsCtxt<'b, 'tcx>,
170 }
171
172 impl<'a, 'b, 'tcx> fmt::Debug for Elaborator<'a, 'b, 'tcx> {
173 fn fmt(&self, _f: &mut fmt::Formatter<'_>) -> fmt::Result {
174 Ok(())
175 }
176 }
177
178 impl<'a, 'b, 'tcx> DropElaborator<'a, 'tcx> for Elaborator<'a, 'b, 'tcx> {
179 type Path = MovePathIndex;
180
181 fn patch(&mut self) -> &mut MirPatch<'tcx> {
182 &mut self.ctxt.patch
183 }
184
185 fn body(&self) -> &'a Body<'tcx> {
186 self.ctxt.body
187 }
188
189 fn tcx(&self) -> TyCtxt<'tcx> {
190 self.ctxt.tcx
191 }
192
193 fn param_env(&self) -> ty::ParamEnv<'tcx> {
194 self.ctxt.param_env()
195 }
196
197 fn drop_style(&self, path: Self::Path, mode: DropFlagMode) -> DropStyle {
198 let ((maybe_live, maybe_dead), multipart) = match mode {
199 DropFlagMode::Shallow => (self.init_data.state(path), false),
200 DropFlagMode::Deep => {
201 let mut some_live = false;
202 let mut some_dead = false;
203 let mut children_count = 0;
204 on_all_drop_children_bits(
205 self.tcx(), self.body(), self.ctxt.env, path, |child| {
206 let (live, dead) = self.init_data.state(child);
207 debug!("elaborate_drop: state({:?}) = {:?}",
208 child, (live, dead));
209 some_live |= live;
210 some_dead |= dead;
211 children_count += 1;
212 });
213 ((some_live, some_dead), children_count != 1)
214 }
215 };
216 match (maybe_live, maybe_dead, multipart) {
217 (false, _, _) => DropStyle::Dead,
218 (true, false, _) => DropStyle::Static,
219 (true, true, false) => DropStyle::Conditional,
220 (true, true, true) => DropStyle::Open,
221 }
222 }
223
224 fn clear_drop_flag(&mut self, loc: Location, path: Self::Path, mode: DropFlagMode) {
225 match mode {
226 DropFlagMode::Shallow => {
227 self.ctxt.set_drop_flag(loc, path, DropFlagState::Absent);
228 }
229 DropFlagMode::Deep => {
230 on_all_children_bits(
231 self.tcx(), self.body(), self.ctxt.move_data(), path,
232 |child| self.ctxt.set_drop_flag(loc, child, DropFlagState::Absent)
233 );
234 }
235 }
236 }
237
238 fn field_subpath(&self, path: Self::Path, field: Field) -> Option<Self::Path> {
239 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |e| match e {
240 ProjectionElem::Field(idx, _) => *idx == field,
241 _ => false,
242 })
243 }
244
245 fn array_subpath(&self, path: Self::Path, index: u32, size: u32) -> Option<Self::Path> {
246 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |e| match e {
247 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false } => {
248 *offset == index
249 }
250 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true } => {
251 size - offset == index
252 }
253 _ => false,
254 })
255 }
256
257 fn deref_subpath(&self, path: Self::Path) -> Option<Self::Path> {
258 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |e| {
259 *e == ProjectionElem::Deref
260 })
261 }
262
263 fn downcast_subpath(&self, path: Self::Path, variant: VariantIdx) -> Option<Self::Path> {
264 dataflow::move_path_children_matching(self.ctxt.move_data(), path, |e| match e {
265 ProjectionElem::Downcast(_, idx) => *idx == variant,
266 _ => false
267 })
268 }
269
270 fn get_drop_flag(&mut self, path: Self::Path) -> Option<Operand<'tcx>> {
271 self.ctxt.drop_flag(path).map(Operand::Copy)
272 }
273 }
274
275 struct ElaborateDropsCtxt<'a, 'tcx> {
276 tcx: TyCtxt<'tcx>,
277 body: &'a Body<'tcx>,
278 env: &'a MoveDataParamEnv<'tcx>,
279 flow_inits: DataflowResults<'tcx, MaybeInitializedPlaces<'a, 'tcx>>,
280 flow_uninits: DataflowResults<'tcx, MaybeUninitializedPlaces<'a, 'tcx>>,
281 drop_flags: FxHashMap<MovePathIndex, Local>,
282 patch: MirPatch<'tcx>,
283 }
284
285 impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
286 fn move_data(&self) -> &'b MoveData<'tcx> { &self.env.move_data }
287
288 fn param_env(&self) -> ty::ParamEnv<'tcx> {
289 self.env.param_env
290 }
291
292 fn initialization_data_at(&self, loc: Location) -> InitializationData {
293 let mut data = InitializationData {
294 live: self.flow_inits.sets().entry_set_for(loc.block.index())
295 .to_owned(),
296 dead: self.flow_uninits.sets().entry_set_for(loc.block.index())
297 .to_owned(),
298 };
299 for stmt in 0..loc.statement_index {
300 data.apply_location(self.tcx, self.body, self.env,
301 Location { block: loc.block, statement_index: stmt });
302 }
303 data
304 }
305
306 fn create_drop_flag(&mut self, index: MovePathIndex, span: Span) {
307 let tcx = self.tcx;
308 let patch = &mut self.patch;
309 debug!("create_drop_flag({:?})", self.body.span);
310 self.drop_flags.entry(index).or_insert_with(|| {
311 patch.new_internal(tcx.types.bool, span)
312 });
313 }
314
315 fn drop_flag(&mut self, index: MovePathIndex) -> Option<Place<'tcx>> {
316 self.drop_flags.get(&index).map(|t| Place::from(*t))
317 }
318
319 /// create a patch that elaborates all drops in the input
320 /// MIR.
321 fn elaborate(mut self) -> MirPatch<'tcx>
322 {
323 self.collect_drop_flags();
324
325 self.elaborate_drops();
326
327 self.drop_flags_on_init();
328 self.drop_flags_for_fn_rets();
329 self.drop_flags_for_args();
330 self.drop_flags_for_locs();
331
332 self.patch
333 }
334
335 fn collect_drop_flags(&mut self)
336 {
337 for (bb, data) in self.body.basic_blocks().iter_enumerated() {
338 let terminator = data.terminator();
339 let location = match terminator.kind {
340 TerminatorKind::Drop { ref location, .. } |
341 TerminatorKind::DropAndReplace { ref location, .. } => location,
342 _ => continue
343 };
344
345 let init_data = self.initialization_data_at(Location {
346 block: bb,
347 statement_index: data.statements.len()
348 });
349
350 let path = self.move_data().rev_lookup.find(location.as_ref());
351 debug!("collect_drop_flags: {:?}, place {:?} ({:?})",
352 bb, location, path);
353
354 let path = match path {
355 LookupResult::Exact(e) => e,
356 LookupResult::Parent(None) => continue,
357 LookupResult::Parent(Some(parent)) => {
358 let (_maybe_live, maybe_dead) = init_data.state(parent);
359 if maybe_dead {
360 span_bug!(terminator.source_info.span,
361 "drop of untracked, uninitialized value {:?}, place {:?} ({:?})",
362 bb, location, path);
363 }
364 continue
365 }
366 };
367
368 on_all_drop_children_bits(self.tcx, self.body, self.env, path, |child| {
369 let (maybe_live, maybe_dead) = init_data.state(child);
370 debug!("collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
371 child, location, path, (maybe_live, maybe_dead));
372 if maybe_live && maybe_dead {
373 self.create_drop_flag(child, terminator.source_info.span)
374 }
375 });
376 }
377 }
378
379 fn elaborate_drops(&mut self)
380 {
381 for (bb, data) in self.body.basic_blocks().iter_enumerated() {
382 let loc = Location { block: bb, statement_index: data.statements.len() };
383 let terminator = data.terminator();
384
385 let resume_block = self.patch.resume_block();
386 match terminator.kind {
387 TerminatorKind::Drop { ref location, target, unwind } => {
388 let init_data = self.initialization_data_at(loc);
389 match self.move_data().rev_lookup.find(location.as_ref()) {
390 LookupResult::Exact(path) => {
391 elaborate_drop(
392 &mut Elaborator {
393 init_data: &init_data,
394 ctxt: self
395 },
396 terminator.source_info,
397 location,
398 path,
399 target,
400 if data.is_cleanup {
401 Unwind::InCleanup
402 } else {
403 Unwind::To(Option::unwrap_or(unwind, resume_block))
404 },
405 bb)
406 }
407 LookupResult::Parent(..) => {
408 span_bug!(terminator.source_info.span,
409 "drop of untracked value {:?}", bb);
410 }
411 }
412 }
413 TerminatorKind::DropAndReplace { ref location, ref value,
414 target, unwind } =>
415 {
416 assert!(!data.is_cleanup);
417
418 self.elaborate_replace(
419 loc,
420 location, value,
421 target, unwind
422 );
423 }
424 _ => continue
425 }
426 }
427 }
428
429 /// Elaborate a MIR `replace` terminator. This instruction
430 /// is not directly handled by codegen, and therefore
431 /// must be desugared.
432 ///
433 /// The desugaring drops the location if needed, and then writes
434 /// the value (including setting the drop flag) over it in *both* arms.
435 ///
436 /// The `replace` terminator can also be called on places that
437 /// are not tracked by elaboration (for example,
438 /// `replace x[i] <- tmp0`). The borrow checker requires that
439 /// these locations are initialized before the assignment,
440 /// so we just generate an unconditional drop.
441 fn elaborate_replace(
442 &mut self,
443 loc: Location,
444 location: &Place<'tcx>,
445 value: &Operand<'tcx>,
446 target: BasicBlock,
447 unwind: Option<BasicBlock>)
448 {
449 let bb = loc.block;
450 let data = &self.body[bb];
451 let terminator = data.terminator();
452 assert!(!data.is_cleanup, "DropAndReplace in unwind path not supported");
453
454 let assign = Statement {
455 kind: StatementKind::Assign(box(location.clone(), Rvalue::Use(value.clone()))),
456 source_info: terminator.source_info
457 };
458
459 let unwind = unwind.unwrap_or_else(|| self.patch.resume_block());
460 let unwind = self.patch.new_block(BasicBlockData {
461 statements: vec![assign.clone()],
462 terminator: Some(Terminator {
463 kind: TerminatorKind::Goto { target: unwind },
464 ..*terminator
465 }),
466 is_cleanup: true
467 });
468
469 let target = self.patch.new_block(BasicBlockData {
470 statements: vec![assign],
471 terminator: Some(Terminator {
472 kind: TerminatorKind::Goto { target },
473 ..*terminator
474 }),
475 is_cleanup: false,
476 });
477
478 match self.move_data().rev_lookup.find(location.as_ref()) {
479 LookupResult::Exact(path) => {
480 debug!("elaborate_drop_and_replace({:?}) - tracked {:?}", terminator, path);
481 let init_data = self.initialization_data_at(loc);
482
483 elaborate_drop(
484 &mut Elaborator {
485 init_data: &init_data,
486 ctxt: self
487 },
488 terminator.source_info,
489 location,
490 path,
491 target,
492 Unwind::To(unwind),
493 bb);
494 on_all_children_bits(self.tcx, self.body, self.move_data(), path, |child| {
495 self.set_drop_flag(Location { block: target, statement_index: 0 },
496 child, DropFlagState::Present);
497 self.set_drop_flag(Location { block: unwind, statement_index: 0 },
498 child, DropFlagState::Present);
499 });
500 }
501 LookupResult::Parent(parent) => {
502 // drop and replace behind a pointer/array/whatever. The location
503 // must be initialized.
504 debug!("elaborate_drop_and_replace({:?}) - untracked {:?}", terminator, parent);
505 self.patch.patch_terminator(bb, TerminatorKind::Drop {
506 location: location.clone(),
507 target,
508 unwind: Some(unwind)
509 });
510 }
511 }
512 }
513
514 fn constant_bool(&self, span: Span, val: bool) -> Rvalue<'tcx> {
515 Rvalue::Use(Operand::Constant(Box::new(Constant {
516 span,
517 user_ty: None,
518 literal: ty::Const::from_bool(self.tcx, val),
519 })))
520 }
521
522 fn set_drop_flag(&mut self, loc: Location, path: MovePathIndex, val: DropFlagState) {
523 if let Some(&flag) = self.drop_flags.get(&path) {
524 let span = self.patch.source_info_for_location(self.body, loc).span;
525 let val = self.constant_bool(span, val.value());
526 self.patch.add_assign(loc, Place::from(flag), val);
527 }
528 }
529
530 fn drop_flags_on_init(&mut self) {
531 let loc = Location::START;
532 let span = self.patch.source_info_for_location(self.body, loc).span;
533 let false_ = self.constant_bool(span, false);
534 for flag in self.drop_flags.values() {
535 self.patch.add_assign(loc, Place::from(*flag), false_.clone());
536 }
537 }
538
539 fn drop_flags_for_fn_rets(&mut self) {
540 for (bb, data) in self.body.basic_blocks().iter_enumerated() {
541 if let TerminatorKind::Call {
542 destination: Some((ref place, tgt)), cleanup: Some(_), ..
543 } = data.terminator().kind {
544 assert!(!self.patch.is_patched(bb));
545
546 let loc = Location { block: tgt, statement_index: 0 };
547 let path = self.move_data().rev_lookup.find(place.as_ref());
548 on_lookup_result_bits(
549 self.tcx, self.body, self.move_data(), path,
550 |child| self.set_drop_flag(loc, child, DropFlagState::Present)
551 );
552 }
553 }
554 }
555
556 fn drop_flags_for_args(&mut self) {
557 let loc = Location::START;
558 dataflow::drop_flag_effects_for_function_entry(
559 self.tcx, self.body, self.env, |path, ds| {
560 self.set_drop_flag(loc, path, ds);
561 }
562 )
563 }
564
565 fn drop_flags_for_locs(&mut self) {
566 // We intentionally iterate only over the *old* basic blocks.
567 //
568 // Basic blocks created by drop elaboration update their
569 // drop flags by themselves, to avoid the drop flags being
570 // clobbered before they are read.
571
572 for (bb, data) in self.body.basic_blocks().iter_enumerated() {
573 debug!("drop_flags_for_locs({:?})", data);
574 for i in 0..(data.statements.len()+1) {
575 debug!("drop_flag_for_locs: stmt {}", i);
576 let mut allow_initializations = true;
577 if i == data.statements.len() {
578 match data.terminator().kind {
579 TerminatorKind::Drop { .. } => {
580 // drop elaboration should handle that by itself
581 continue
582 }
583 TerminatorKind::DropAndReplace { .. } => {
584 // this contains the move of the source and
585 // the initialization of the destination. We
586 // only want the former - the latter is handled
587 // by the elaboration code and must be done
588 // *after* the destination is dropped.
589 assert!(self.patch.is_patched(bb));
590 allow_initializations = false;
591 }
592 TerminatorKind::Resume => {
593 // It is possible for `Resume` to be patched
594 // (in particular it can be patched to be replaced with
595 // a Goto; see `MirPatch::new`).
596 }
597 _ => {
598 assert!(!self.patch.is_patched(bb));
599 }
600 }
601 }
602 let loc = Location { block: bb, statement_index: i };
603 dataflow::drop_flag_effects_for_location(
604 self.tcx, self.body, self.env, loc, |path, ds| {
605 if ds == DropFlagState::Absent || allow_initializations {
606 self.set_drop_flag(loc, path, ds)
607 }
608 }
609 )
610 }
611
612 // There may be a critical edge after this call,
613 // so mark the return as initialized *before* the
614 // call.
615 if let TerminatorKind::Call {
616 destination: Some((ref place, _)), cleanup: None, ..
617 } = data.terminator().kind {
618 assert!(!self.patch.is_patched(bb));
619
620 let loc = Location { block: bb, statement_index: data.statements.len() };
621 let path = self.move_data().rev_lookup.find(place.as_ref());
622 on_lookup_result_bits(
623 self.tcx, self.body, self.move_data(), path,
624 |child| self.set_drop_flag(loc, child, DropFlagState::Present)
625 );
626 }
627 }
628 }
629 }