]> git.lizzy.rs Git - rust.git/blob - src/librustc_mir/transform/elaborate_drops.rs
Run `rustfmt --file-lines ...` for changes from previous commits.
[rust.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 MirPass for ElaborateDrops {
24     fn run_pass<'tcx>(&self, tcx: TyCtxt<'tcx, '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, 'tcx>,
78     body: &Body<'tcx>,
79     def_id: hir::def_id::DefId,
80     env: &MoveDataParamEnv<'tcx, '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().on_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) {
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, 'tcx>,
142         body: &Body<'tcx>,
143         env: &MoveDataParamEnv<'tcx, '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: 'a, 'tcx: 'b> {
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, '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, |p| {
240             match p {
241                 &Projection {
242                     elem: ProjectionElem::Field(idx, _), ..
243                 } => idx == field,
244                 _ => false
245             }
246         })
247     }
248
249     fn array_subpath(&self, path: Self::Path, index: u32, size: u32) -> Option<Self::Path> {
250         dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
251             match p {
252                 &Projection {
253                     elem: ProjectionElem::ConstantIndex{offset, min_length: _, from_end: false}, ..
254                 } => offset == index,
255                 &Projection {
256                     elem: ProjectionElem::ConstantIndex{offset, min_length: _, from_end: true}, ..
257                 } => size - offset == index,
258                 _ => false
259             }
260         })
261     }
262
263     fn deref_subpath(&self, path: Self::Path) -> Option<Self::Path> {
264         dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
265             match p {
266                 &Projection { elem: ProjectionElem::Deref, .. } => true,
267                 _ => false
268             }
269         })
270     }
271
272     fn downcast_subpath(&self, path: Self::Path, variant: VariantIdx) -> Option<Self::Path> {
273         dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
274             match p {
275                 &Projection {
276                     elem: ProjectionElem::Downcast(_, idx), ..
277                 } => idx == variant,
278                 _ => false
279             }
280         })
281     }
282
283     fn get_drop_flag(&mut self, path: Self::Path) -> Option<Operand<'tcx>> {
284         self.ctxt.drop_flag(path).map(Operand::Copy)
285     }
286 }
287
288 struct ElaborateDropsCtxt<'a, 'tcx: 'a> {
289     tcx: TyCtxt<'tcx, 'tcx>,
290     body: &'a Body<'tcx>,
291     env: &'a MoveDataParamEnv<'tcx, 'tcx>,
292     flow_inits: DataflowResults<'tcx, MaybeInitializedPlaces<'a, 'tcx, 'tcx>>,
293     flow_uninits: DataflowResults<'tcx, MaybeUninitializedPlaces<'a, 'tcx, 'tcx>>,
294     drop_flags: FxHashMap<MovePathIndex, Local>,
295     patch: MirPatch<'tcx>,
296 }
297
298 impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
299     fn move_data(&self) -> &'b MoveData<'tcx> { &self.env.move_data }
300
301     fn param_env(&self) -> ty::ParamEnv<'tcx> {
302         self.env.param_env
303     }
304
305     fn initialization_data_at(&self, loc: Location) -> InitializationData {
306         let mut data = InitializationData {
307             live: self.flow_inits.sets().on_entry_set_for(loc.block.index())
308                 .to_owned(),
309             dead: self.flow_uninits.sets().on_entry_set_for(loc.block.index())
310                 .to_owned(),
311         };
312         for stmt in 0..loc.statement_index {
313             data.apply_location(self.tcx, self.body, self.env,
314                                 Location { block: loc.block, statement_index: stmt });
315         }
316         data
317     }
318
319     fn create_drop_flag(&mut self, index: MovePathIndex, span: Span) {
320         let tcx = self.tcx;
321         let patch = &mut self.patch;
322         debug!("create_drop_flag({:?})", self.body.span);
323         self.drop_flags.entry(index).or_insert_with(|| {
324             patch.new_internal(tcx.types.bool, span)
325         });
326     }
327
328     fn drop_flag(&mut self, index: MovePathIndex) -> Option<Place<'tcx>> {
329         self.drop_flags.get(&index).map(|t| Place::Base(PlaceBase::Local(*t)))
330     }
331
332     /// create a patch that elaborates all drops in the input
333     /// MIR.
334     fn elaborate(mut self) -> MirPatch<'tcx>
335     {
336         self.collect_drop_flags();
337
338         self.elaborate_drops();
339
340         self.drop_flags_on_init();
341         self.drop_flags_for_fn_rets();
342         self.drop_flags_for_args();
343         self.drop_flags_for_locs();
344
345         self.patch
346     }
347
348     fn collect_drop_flags(&mut self)
349     {
350         for (bb, data) in self.body.basic_blocks().iter_enumerated() {
351             let terminator = data.terminator();
352             let location = match terminator.kind {
353                 TerminatorKind::Drop { ref location, .. } |
354                 TerminatorKind::DropAndReplace { ref location, .. } => location,
355                 _ => continue
356             };
357
358             let init_data = self.initialization_data_at(Location {
359                 block: bb,
360                 statement_index: data.statements.len()
361             });
362
363             let path = self.move_data().rev_lookup.find(location);
364             debug!("collect_drop_flags: {:?}, place {:?} ({:?})",
365                    bb, location, path);
366
367             let path = match path {
368                 LookupResult::Exact(e) => e,
369                 LookupResult::Parent(None) => continue,
370                 LookupResult::Parent(Some(parent)) => {
371                     let (_maybe_live, maybe_dead) = init_data.state(parent);
372                     if maybe_dead {
373                         span_bug!(terminator.source_info.span,
374                                   "drop of untracked, uninitialized value {:?}, place {:?} ({:?})",
375                                   bb, location, path);
376                     }
377                     continue
378                 }
379             };
380
381             on_all_drop_children_bits(self.tcx, self.body, self.env, path, |child| {
382                 let (maybe_live, maybe_dead) = init_data.state(child);
383                 debug!("collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
384                        child, location, path, (maybe_live, maybe_dead));
385                 if maybe_live && maybe_dead {
386                     self.create_drop_flag(child, terminator.source_info.span)
387                 }
388             });
389         }
390     }
391
392     fn elaborate_drops(&mut self)
393     {
394         for (bb, data) in self.body.basic_blocks().iter_enumerated() {
395             let loc = Location { block: bb, statement_index: data.statements.len() };
396             let terminator = data.terminator();
397
398             let resume_block = self.patch.resume_block();
399             match terminator.kind {
400                 TerminatorKind::Drop { ref location, target, unwind } => {
401                     let init_data = self.initialization_data_at(loc);
402                     match self.move_data().rev_lookup.find(location) {
403                         LookupResult::Exact(path) => {
404                             elaborate_drop(
405                                 &mut Elaborator {
406                                     init_data: &init_data,
407                                     ctxt: self
408                                 },
409                                 terminator.source_info,
410                                 location,
411                                 path,
412                                 target,
413                                 if data.is_cleanup {
414                                     Unwind::InCleanup
415                                 } else {
416                                     Unwind::To(Option::unwrap_or(unwind, resume_block))
417                                 },
418                                 bb)
419                         }
420                         LookupResult::Parent(..) => {
421                             span_bug!(terminator.source_info.span,
422                                       "drop of untracked value {:?}", bb);
423                         }
424                     }
425                 }
426                 TerminatorKind::DropAndReplace { ref location, ref value,
427                                                  target, unwind } =>
428                 {
429                     assert!(!data.is_cleanup);
430
431                     self.elaborate_replace(
432                         loc,
433                         location, value,
434                         target, unwind
435                     );
436                 }
437                 _ => continue
438             }
439         }
440     }
441
442     /// Elaborate a MIR `replace` terminator. This instruction
443     /// is not directly handled by codegen, and therefore
444     /// must be desugared.
445     ///
446     /// The desugaring drops the location if needed, and then writes
447     /// the value (including setting the drop flag) over it in *both* arms.
448     ///
449     /// The `replace` terminator can also be called on places that
450     /// are not tracked by elaboration (for example,
451     /// `replace x[i] <- tmp0`). The borrow checker requires that
452     /// these locations are initialized before the assignment,
453     /// so we just generate an unconditional drop.
454     fn elaborate_replace(
455         &mut self,
456         loc: Location,
457         location: &Place<'tcx>,
458         value: &Operand<'tcx>,
459         target: BasicBlock,
460         unwind: Option<BasicBlock>)
461     {
462         let bb = loc.block;
463         let data = &self.body[bb];
464         let terminator = data.terminator();
465         assert!(!data.is_cleanup, "DropAndReplace in unwind path not supported");
466
467         let assign = Statement {
468             kind: StatementKind::Assign(location.clone(), box Rvalue::Use(value.clone())),
469             source_info: terminator.source_info
470         };
471
472         let unwind = unwind.unwrap_or_else(|| self.patch.resume_block());
473         let unwind = self.patch.new_block(BasicBlockData {
474             statements: vec![assign.clone()],
475             terminator: Some(Terminator {
476                 kind: TerminatorKind::Goto { target: unwind },
477                 ..*terminator
478             }),
479             is_cleanup: true
480         });
481
482         let target = self.patch.new_block(BasicBlockData {
483             statements: vec![assign],
484             terminator: Some(Terminator {
485                 kind: TerminatorKind::Goto { target },
486                 ..*terminator
487             }),
488             is_cleanup: false,
489         });
490
491         match self.move_data().rev_lookup.find(location) {
492             LookupResult::Exact(path) => {
493                 debug!("elaborate_drop_and_replace({:?}) - tracked {:?}", terminator, path);
494                 let init_data = self.initialization_data_at(loc);
495
496                 elaborate_drop(
497                     &mut Elaborator {
498                         init_data: &init_data,
499                         ctxt: self
500                     },
501                     terminator.source_info,
502                     location,
503                     path,
504                     target,
505                     Unwind::To(unwind),
506                     bb);
507                 on_all_children_bits(self.tcx, self.body, self.move_data(), path, |child| {
508                     self.set_drop_flag(Location { block: target, statement_index: 0 },
509                                        child, DropFlagState::Present);
510                     self.set_drop_flag(Location { block: unwind, statement_index: 0 },
511                                        child, DropFlagState::Present);
512                 });
513             }
514             LookupResult::Parent(parent) => {
515                 // drop and replace behind a pointer/array/whatever. The location
516                 // must be initialized.
517                 debug!("elaborate_drop_and_replace({:?}) - untracked {:?}", terminator, parent);
518                 self.patch.patch_terminator(bb, TerminatorKind::Drop {
519                     location: location.clone(),
520                     target,
521                     unwind: Some(unwind)
522                 });
523             }
524         }
525     }
526
527     fn constant_bool(&self, span: Span, val: bool) -> Rvalue<'tcx> {
528         Rvalue::Use(Operand::Constant(Box::new(Constant {
529             span,
530             ty: self.tcx.types.bool,
531             user_ty: None,
532             literal: ty::Const::from_bool(self.tcx, val),
533         })))
534     }
535
536     fn set_drop_flag(&mut self, loc: Location, path: MovePathIndex, val: DropFlagState) {
537         if let Some(&flag) = self.drop_flags.get(&path) {
538             let span = self.patch.source_info_for_location(self.body, loc).span;
539             let val = self.constant_bool(span, val.value());
540             self.patch.add_assign(loc, Place::Base(PlaceBase::Local(flag)), val);
541         }
542     }
543
544     fn drop_flags_on_init(&mut self) {
545         let loc = Location::START;
546         let span = self.patch.source_info_for_location(self.body, loc).span;
547         let false_ = self.constant_bool(span, false);
548         for flag in self.drop_flags.values() {
549             self.patch.add_assign(loc, Place::Base(PlaceBase::Local(*flag)), false_.clone());
550         }
551     }
552
553     fn drop_flags_for_fn_rets(&mut self) {
554         for (bb, data) in self.body.basic_blocks().iter_enumerated() {
555             if let TerminatorKind::Call {
556                 destination: Some((ref place, tgt)), cleanup: Some(_), ..
557             } = data.terminator().kind {
558                 assert!(!self.patch.is_patched(bb));
559
560                 let loc = Location { block: tgt, statement_index: 0 };
561                 let path = self.move_data().rev_lookup.find(place);
562                 on_lookup_result_bits(
563                     self.tcx, self.body, self.move_data(), path,
564                     |child| self.set_drop_flag(loc, child, DropFlagState::Present)
565                 );
566             }
567         }
568     }
569
570     fn drop_flags_for_args(&mut self) {
571         let loc = Location::START;
572         dataflow::drop_flag_effects_for_function_entry(
573             self.tcx, self.body, self.env, |path, ds| {
574                 self.set_drop_flag(loc, path, ds);
575             }
576         )
577     }
578
579     fn drop_flags_for_locs(&mut self) {
580         // We intentionally iterate only over the *old* basic blocks.
581         //
582         // Basic blocks created by drop elaboration update their
583         // drop flags by themselves, to avoid the drop flags being
584         // clobbered before they are read.
585
586         for (bb, data) in self.body.basic_blocks().iter_enumerated() {
587             debug!("drop_flags_for_locs({:?})", data);
588             for i in 0..(data.statements.len()+1) {
589                 debug!("drop_flag_for_locs: stmt {}", i);
590                 let mut allow_initializations = true;
591                 if i == data.statements.len() {
592                     match data.terminator().kind {
593                         TerminatorKind::Drop { .. } => {
594                             // drop elaboration should handle that by itself
595                             continue
596                         }
597                         TerminatorKind::DropAndReplace { .. } => {
598                             // this contains the move of the source and
599                             // the initialization of the destination. We
600                             // only want the former - the latter is handled
601                             // by the elaboration code and must be done
602                             // *after* the destination is dropped.
603                             assert!(self.patch.is_patched(bb));
604                             allow_initializations = false;
605                         }
606                         TerminatorKind::Resume => {
607                             // It is possible for `Resume` to be patched
608                             // (in particular it can be patched to be replaced with
609                             // a Goto; see `MirPatch::new`).
610                         }
611                         _ => {
612                             assert!(!self.patch.is_patched(bb));
613                         }
614                     }
615                 }
616                 let loc = Location { block: bb, statement_index: i };
617                 dataflow::drop_flag_effects_for_location(
618                     self.tcx, self.body, self.env, loc, |path, ds| {
619                         if ds == DropFlagState::Absent || allow_initializations {
620                             self.set_drop_flag(loc, path, ds)
621                         }
622                     }
623                 )
624             }
625
626             // There may be a critical edge after this call,
627             // so mark the return as initialized *before* the
628             // call.
629             if let TerminatorKind::Call {
630                 destination: Some((ref place, _)), cleanup: None, ..
631             } = data.terminator().kind {
632                 assert!(!self.patch.is_patched(bb));
633
634                 let loc = Location { block: bb, statement_index: data.statements.len() };
635                 let path = self.move_data().rev_lookup.find(place);
636                 on_lookup_result_bits(
637                     self.tcx, self.body, self.move_data(), path,
638                     |child| self.set_drop_flag(loc, child, DropFlagState::Present)
639                 );
640             }
641         }
642     }
643 }