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