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