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
;
16 use rustc
::util
::nodemap
::FxHashMap
;
17 use rustc_data_structures
::bit_set
::BitSet
;
21 pub struct ElaborateDrops
;
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
);
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.
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());
43 let elaborate_patch
= {
45 let env
= MoveDataParamEnv
{
49 let dead_unwinds
= find_dead_unwinds(tcx
, body
, def_id
, &env
);
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
]));
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
]));
65 drop_flags
: Default
::default(),
66 patch
: MirPatch
::new(body
),
69 elaborate_patch
.apply(body
);
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
>(
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());
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
,
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()),
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
);
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");
116 debug
!("find_dead_unwinds @ {:?}: path({:?})={:?}", bb
, location
, path
);
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
;
124 debug
!("find_dead_unwinds @ {:?}: maybe_live={}", bb
, maybe_live
);
126 dead_unwinds
.insert(bb
);
133 struct InitializationData
{
134 live
: BitSet
<MovePathIndex
>,
135 dead
: BitSet
<MovePathIndex
>
138 impl InitializationData
{
139 fn apply_location
<'tcx
>(
143 env
: &MoveDataParamEnv
<'tcx
>,
146 drop_flag_effects_for_location(tcx
, body
, env
, loc
, |path
, df
| {
147 debug
!("at location {:?}: setting {:?} to {:?}",
150 DropFlagState
::Present
=> {
151 self.live
.insert(path
);
152 self.dead
.remove(path
);
154 DropFlagState
::Absent
=> {
155 self.dead
.insert(path
);
156 self.live
.remove(path
);
162 fn state(&self, path
: MovePathIndex
) -> (bool
, bool
) {
163 (self.live
.contains(path
), self.dead
.contains(path
))
167 struct Elaborator
<'a
, 'b
, 'tcx
> {
168 init_data
: &'a InitializationData
,
169 ctxt
: &'a
mut ElaborateDropsCtxt
<'b
, 'tcx
>,
172 impl<'a
, 'b
, 'tcx
> fmt
::Debug
for Elaborator
<'a
, 'b
, 'tcx
> {
173 fn fmt(&self, _f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
178 impl<'a
, 'b
, 'tcx
> DropElaborator
<'a
, 'tcx
> for Elaborator
<'a
, 'b
, 'tcx
> {
179 type Path
= MovePathIndex
;
181 fn patch(&mut self) -> &mut MirPatch
<'tcx
> {
185 fn body(&self) -> &'a Body
<'tcx
> {
189 fn tcx(&self) -> TyCtxt
<'tcx
> {
193 fn param_env(&self) -> ty
::ParamEnv
<'tcx
> {
194 self.ctxt
.param_env()
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
));
213 ((some_live
, some_dead
), children_count
!= 1)
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
,
224 fn clear_drop_flag(&mut self, loc
: Location
, path
: Self::Path
, mode
: DropFlagMode
) {
226 DropFlagMode
::Shallow
=> {
227 self.ctxt
.set_drop_flag(loc
, path
, DropFlagState
::Absent
);
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
)
238 fn field_subpath(&self, path
: Self::Path
, field
: Field
) -> Option
<Self::Path
> {
239 dataflow
::move_path_children_matching(self.ctxt
.move_data(), path
, |e
| match e
{
240 ProjectionElem
::Field(idx
, _
) => *idx
== field
,
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
, |e
| match e
{
247 ProjectionElem
::ConstantIndex { offset, min_length: _, from_end: false }
=> {
250 ProjectionElem
::ConstantIndex { offset, min_length: _, from_end: true }
=> {
251 size
- offset
== index
257 fn deref_subpath(&self, path
: Self::Path
) -> Option
<Self::Path
> {
258 dataflow
::move_path_children_matching(self.ctxt
.move_data(), path
, |e
| {
259 *e
== ProjectionElem
::Deref
263 fn downcast_subpath(&self, path
: Self::Path
, variant
: VariantIdx
) -> Option
<Self::Path
> {
264 dataflow
::move_path_children_matching(self.ctxt
.move_data(), path
, |e
| match e
{
265 ProjectionElem
::Downcast(_
, idx
) => *idx
== variant
,
270 fn get_drop_flag(&mut self, path
: Self::Path
) -> Option
<Operand
<'tcx
>> {
271 self.ctxt
.drop_flag(path
).map(Operand
::Copy
)
275 struct ElaborateDropsCtxt
<'a
, 'tcx
> {
277 body
: &'a Body
<'tcx
>,
278 env
: &'a MoveDataParamEnv
<'tcx
>,
279 flow_inits
: DataflowResults
<'tcx
, MaybeInitializedPlaces
<'a
, 'tcx
>>,
280 flow_uninits
: DataflowResults
<'tcx
, MaybeUninitializedPlaces
<'a
, 'tcx
>>,
281 drop_flags
: FxHashMap
<MovePathIndex
, Local
>,
282 patch
: MirPatch
<'tcx
>,
285 impl<'b
, 'tcx
> ElaborateDropsCtxt
<'b
, 'tcx
> {
286 fn move_data(&self) -> &'b MoveData
<'tcx
> { &self.env.move_data }
288 fn param_env(&self) -> ty
::ParamEnv
<'tcx
> {
292 fn initialization_data_at(&self, loc
: Location
) -> InitializationData
{
293 let mut data
= InitializationData
{
294 live
: self.flow_inits
.sets().entry_set_for(loc
.block
.index())
296 dead
: self.flow_uninits
.sets().entry_set_for(loc
.block
.index())
299 for stmt
in 0..loc
.statement_index
{
300 data
.apply_location(self.tcx
, self.body
, self.env
,
301 Location { block: loc.block, statement_index: stmt }
);
306 fn create_drop_flag(&mut self, index
: MovePathIndex
, span
: Span
) {
308 let patch
= &mut self.patch
;
309 debug
!("create_drop_flag({:?})", self.body
.span
);
310 self.drop_flags
.entry(index
).or_insert_with(|| {
311 patch
.new_internal(tcx
.types
.bool
, span
)
315 fn drop_flag(&mut self, index
: MovePathIndex
) -> Option
<Place
<'tcx
>> {
316 self.drop_flags
.get(&index
).map(|t
| Place
::from(*t
))
319 /// create a patch that elaborates all drops in the input
321 fn elaborate(mut self) -> MirPatch
<'tcx
>
323 self.collect_drop_flags();
325 self.elaborate_drops();
327 self.drop_flags_on_init();
328 self.drop_flags_for_fn_rets();
329 self.drop_flags_for_args();
330 self.drop_flags_for_locs();
335 fn collect_drop_flags(&mut self)
337 for (bb
, data
) in self.body
.basic_blocks().iter_enumerated() {
338 let terminator
= data
.terminator();
339 let location
= match terminator
.kind
{
340 TerminatorKind
::Drop { ref location, .. }
|
341 TerminatorKind
::DropAndReplace { ref location, .. }
=> location
,
345 let init_data
= self.initialization_data_at(Location
{
347 statement_index
: data
.statements
.len()
350 let path
= self.move_data().rev_lookup
.find(location
.as_ref());
351 debug
!("collect_drop_flags: {:?}, place {:?} ({:?})",
354 let path
= match path
{
355 LookupResult
::Exact(e
) => e
,
356 LookupResult
::Parent(None
) => continue,
357 LookupResult
::Parent(Some(parent
)) => {
358 let (_maybe_live
, maybe_dead
) = init_data
.state(parent
);
360 span_bug
!(terminator
.source_info
.span
,
361 "drop of untracked, uninitialized value {:?}, place {:?} ({:?})",
368 on_all_drop_children_bits(self.tcx
, self.body
, self.env
, path
, |child
| {
369 let (maybe_live
, maybe_dead
) = init_data
.state(child
);
370 debug
!("collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
371 child
, location
, path
, (maybe_live
, maybe_dead
));
372 if maybe_live
&& maybe_dead
{
373 self.create_drop_flag(child
, terminator
.source_info
.span
)
379 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();
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
) => {
393 init_data
: &init_data
,
396 terminator
.source_info
,
403 Unwind
::To(Option
::unwrap_or(unwind
, resume_block
))
407 LookupResult
::Parent(..) => {
408 span_bug
!(terminator
.source_info
.span
,
409 "drop of untracked value {:?}", bb
);
413 TerminatorKind
::DropAndReplace
{ ref location
, ref value
,
416 assert
!(!data
.is_cleanup
);
418 self.elaborate_replace(
429 /// Elaborate a MIR `replace` terminator. This instruction
430 /// is not directly handled by codegen, and therefore
431 /// must be desugared.
433 /// The desugaring drops the location if needed, and then writes
434 /// the value (including setting the drop flag) over it in *both* arms.
436 /// The `replace` terminator can also be called on places that
437 /// are not tracked by elaboration (for example,
438 /// `replace x[i] <- tmp0`). The borrow checker requires that
439 /// these locations are initialized before the assignment,
440 /// so we just generate an unconditional drop.
441 fn elaborate_replace(
444 location
: &Place
<'tcx
>,
445 value
: &Operand
<'tcx
>,
447 unwind
: Option
<BasicBlock
>)
450 let data
= &self.body
[bb
];
451 let terminator
= data
.terminator();
452 assert
!(!data
.is_cleanup
, "DropAndReplace in unwind path not supported");
454 let assign
= Statement
{
455 kind
: StatementKind
::Assign(box(location
.clone(), Rvalue
::Use(value
.clone()))),
456 source_info
: terminator
.source_info
459 let unwind
= unwind
.unwrap_or_else(|| self.patch
.resume_block());
460 let unwind
= self.patch
.new_block(BasicBlockData
{
461 statements
: vec
![assign
.clone()],
462 terminator
: Some(Terminator
{
463 kind
: TerminatorKind
::Goto { target: unwind }
,
469 let target
= self.patch
.new_block(BasicBlockData
{
470 statements
: vec
![assign
],
471 terminator
: Some(Terminator
{
472 kind
: TerminatorKind
::Goto { target }
,
478 match self.move_data().rev_lookup
.find(location
.as_ref()) {
479 LookupResult
::Exact(path
) => {
480 debug
!("elaborate_drop_and_replace({:?}) - tracked {:?}", terminator
, path
);
481 let init_data
= self.initialization_data_at(loc
);
485 init_data
: &init_data
,
488 terminator
.source_info
,
494 on_all_children_bits(self.tcx
, self.body
, self.move_data(), path
, |child
| {
495 self.set_drop_flag(Location { block: target, statement_index: 0 }
,
496 child
, DropFlagState
::Present
);
497 self.set_drop_flag(Location { block: unwind, statement_index: 0 }
,
498 child
, DropFlagState
::Present
);
501 LookupResult
::Parent(parent
) => {
502 // drop and replace behind a pointer/array/whatever. The location
503 // must be initialized.
504 debug
!("elaborate_drop_and_replace({:?}) - untracked {:?}", terminator
, parent
);
505 self.patch
.patch_terminator(bb
, TerminatorKind
::Drop
{
506 location
: location
.clone(),
514 fn constant_bool(&self, span
: Span
, val
: bool
) -> Rvalue
<'tcx
> {
515 Rvalue
::Use(Operand
::Constant(Box
::new(Constant
{
518 literal
: ty
::Const
::from_bool(self.tcx
, val
),
522 fn set_drop_flag(&mut self, loc
: Location
, path
: MovePathIndex
, val
: DropFlagState
) {
523 if let Some(&flag
) = self.drop_flags
.get(&path
) {
524 let span
= self.patch
.source_info_for_location(self.body
, loc
).span
;
525 let val
= self.constant_bool(span
, val
.value());
526 self.patch
.add_assign(loc
, Place
::from(flag
), val
);
530 fn drop_flags_on_init(&mut self) {
531 let loc
= Location
::START
;
532 let span
= self.patch
.source_info_for_location(self.body
, loc
).span
;
533 let false_
= self.constant_bool(span
, false);
534 for flag
in self.drop_flags
.values() {
535 self.patch
.add_assign(loc
, Place
::from(*flag
), false_
.clone());
539 fn drop_flags_for_fn_rets(&mut self) {
540 for (bb
, data
) in self.body
.basic_blocks().iter_enumerated() {
541 if let TerminatorKind
::Call
{
542 destination
: Some((ref place
, tgt
)), cleanup
: Some(_
), ..
543 } = data
.terminator().kind
{
544 assert
!(!self.patch
.is_patched(bb
));
546 let loc
= Location { block: tgt, statement_index: 0 }
;
547 let path
= self.move_data().rev_lookup
.find(place
.as_ref());
548 on_lookup_result_bits(
549 self.tcx
, self.body
, self.move_data(), path
,
550 |child
| self.set_drop_flag(loc
, child
, DropFlagState
::Present
)
556 fn drop_flags_for_args(&mut self) {
557 let loc
= Location
::START
;
558 dataflow
::drop_flag_effects_for_function_entry(
559 self.tcx
, self.body
, self.env
, |path
, ds
| {
560 self.set_drop_flag(loc
, path
, ds
);
565 fn drop_flags_for_locs(&mut self) {
566 // We intentionally iterate only over the *old* basic blocks.
568 // Basic blocks created by drop elaboration update their
569 // drop flags by themselves, to avoid the drop flags being
570 // clobbered before they are read.
572 for (bb
, data
) in self.body
.basic_blocks().iter_enumerated() {
573 debug
!("drop_flags_for_locs({:?})", data
);
574 for i
in 0..(data
.statements
.len()+1) {
575 debug
!("drop_flag_for_locs: stmt {}", i
);
576 let mut allow_initializations
= true;
577 if i
== data
.statements
.len() {
578 match data
.terminator().kind
{
579 TerminatorKind
::Drop { .. }
=> {
580 // drop elaboration should handle that by itself
583 TerminatorKind
::DropAndReplace { .. }
=> {
584 // this contains the move of the source and
585 // the initialization of the destination. We
586 // only want the former - the latter is handled
587 // by the elaboration code and must be done
588 // *after* the destination is dropped.
589 assert
!(self.patch
.is_patched(bb
));
590 allow_initializations
= false;
592 TerminatorKind
::Resume
=> {
593 // It is possible for `Resume` to be patched
594 // (in particular it can be patched to be replaced with
595 // a Goto; see `MirPatch::new`).
598 assert
!(!self.patch
.is_patched(bb
));
602 let loc
= Location { block: bb, statement_index: i }
;
603 dataflow
::drop_flag_effects_for_location(
604 self.tcx
, self.body
, self.env
, loc
, |path
, ds
| {
605 if ds
== DropFlagState
::Absent
|| allow_initializations
{
606 self.set_drop_flag(loc
, path
, ds
)
612 // There may be a critical edge after this call,
613 // so mark the return as initialized *before* the
615 if let TerminatorKind
::Call
{
616 destination
: Some((ref place
, _
)), cleanup
: None
, ..
617 } = data
.terminator().kind
{
618 assert
!(!self.patch
.is_patched(bb
));
620 let loc
= Location { block: bb, statement_index: data.statements.len() }
;
621 let path
= self.move_data().rev_lookup
.find(place
.as_ref());
622 on_lookup_result_bits(
623 self.tcx
, self.body
, self.move_data(), path
,
624 |child
| self.set_drop_flag(loc
, child
, DropFlagState
::Present
)