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