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