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