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