1 use rustc_index
::bit_set
::BitSet
;
2 use rustc_middle
::mir
::{self, BasicBlock, Location, SwitchTargets}
;
3 use rustc_middle
::ty
::TyCtxt
;
4 use std
::ops
::RangeInclusive
;
6 use super::visitor
::{ResultsVisitable, ResultsVisitor}
;
8 Analysis
, CallReturnPlaces
, Effect
, EffectIndex
, GenKillAnalysis
, GenKillSet
, SwitchIntTarget
,
12 const IS_FORWARD
: bool
;
14 const IS_BACKWARD
: bool
= !Self::IS_FORWARD
;
16 /// Applies all effects between the given `EffectIndex`s.
18 /// `effects.start()` must precede or equal `effects.end()` in this direction.
19 fn apply_effects_in_range
<'tcx
, A
>(
21 state
: &mut A
::Domain
,
23 block_data
: &mir
::BasicBlockData
<'tcx
>,
24 effects
: RangeInclusive
<EffectIndex
>,
28 fn apply_effects_in_block
<'tcx
, A
>(
30 state
: &mut A
::Domain
,
32 block_data
: &mir
::BasicBlockData
<'tcx
>,
36 fn gen_kill_effects_in_block
<'tcx
, A
>(
38 trans
: &mut GenKillSet
<A
::Idx
>,
40 block_data
: &mir
::BasicBlockData
<'tcx
>,
42 A
: GenKillAnalysis
<'tcx
>;
44 fn visit_results_in_block
<'mir
, 'tcx
, F
, R
>(
47 block_data
: &'mir mir
::BasicBlockData
<'tcx
>,
49 vis
: &mut impl ResultsVisitor
<'mir
, 'tcx
, FlowState
= F
>,
51 R
: ResultsVisitable
<'tcx
, FlowState
= F
>;
53 fn join_state_into_successors_of
<'tcx
, A
>(
56 body
: &mir
::Body
<'tcx
>,
57 dead_unwinds
: Option
<&BitSet
<BasicBlock
>>,
58 exit_state
: &mut A
::Domain
,
59 block
: (BasicBlock
, &'_ mir
::BasicBlockData
<'tcx
>),
60 propagate
: impl FnMut(BasicBlock
, &A
::Domain
),
65 /// Dataflow that runs from the exit of a block (the terminator), to its entry (the first statement).
68 impl Direction
for Backward
{
69 const IS_FORWARD
: bool
= false;
71 fn apply_effects_in_block
<'tcx
, A
>(
73 state
: &mut A
::Domain
,
75 block_data
: &mir
::BasicBlockData
<'tcx
>,
79 let terminator
= block_data
.terminator();
80 let location
= Location { block, statement_index: block_data.statements.len() }
;
81 analysis
.apply_before_terminator_effect(state
, terminator
, location
);
82 analysis
.apply_terminator_effect(state
, terminator
, location
);
84 for (statement_index
, statement
) in block_data
.statements
.iter().enumerate().rev() {
85 let location
= Location { block, statement_index }
;
86 analysis
.apply_before_statement_effect(state
, statement
, location
);
87 analysis
.apply_statement_effect(state
, statement
, location
);
91 fn gen_kill_effects_in_block
<'tcx
, A
>(
93 trans
: &mut GenKillSet
<A
::Idx
>,
95 block_data
: &mir
::BasicBlockData
<'tcx
>,
97 A
: GenKillAnalysis
<'tcx
>,
99 let terminator
= block_data
.terminator();
100 let location
= Location { block, statement_index: block_data.statements.len() }
;
101 analysis
.before_terminator_effect(trans
, terminator
, location
);
102 analysis
.terminator_effect(trans
, terminator
, location
);
104 for (statement_index
, statement
) in block_data
.statements
.iter().enumerate().rev() {
105 let location
= Location { block, statement_index }
;
106 analysis
.before_statement_effect(trans
, statement
, location
);
107 analysis
.statement_effect(trans
, statement
, location
);
111 fn apply_effects_in_range
<'tcx
, A
>(
113 state
: &mut A
::Domain
,
115 block_data
: &mir
::BasicBlockData
<'tcx
>,
116 effects
: RangeInclusive
<EffectIndex
>,
120 let (from
, to
) = (*effects
.start(), *effects
.end());
121 let terminator_index
= block_data
.statements
.len();
123 assert
!(from
.statement_index
<= terminator_index
);
124 assert
!(!to
.precedes_in_backward_order(from
));
126 // Handle the statement (or terminator) at `from`.
128 let next_effect
= match from
.effect
{
129 // If we need to apply the terminator effect in all or in part, do so now.
130 _
if from
.statement_index
== terminator_index
=> {
131 let location
= Location { block, statement_index: from.statement_index }
;
132 let terminator
= block_data
.terminator();
134 if from
.effect
== Effect
::Before
{
135 analysis
.apply_before_terminator_effect(state
, terminator
, location
);
136 if to
== Effect
::Before
.at_index(terminator_index
) {
141 analysis
.apply_terminator_effect(state
, terminator
, location
);
142 if to
== Effect
::Primary
.at_index(terminator_index
) {
146 // If `from.statement_index` is `0`, we will have hit one of the earlier comparisons
148 from
.statement_index
- 1
152 let location
= Location { block, statement_index: from.statement_index }
;
153 let statement
= &block_data
.statements
[from
.statement_index
];
155 analysis
.apply_statement_effect(state
, statement
, location
);
156 if to
== Effect
::Primary
.at_index(from
.statement_index
) {
160 from
.statement_index
- 1
163 Effect
::Before
=> from
.statement_index
,
166 // Handle all statements between `first_unapplied_idx` and `to.statement_index`.
168 for statement_index
in (to
.statement_index
..next_effect
).rev().map(|i
| i
+ 1) {
169 let location
= Location { block, statement_index }
;
170 let statement
= &block_data
.statements
[statement_index
];
171 analysis
.apply_before_statement_effect(state
, statement
, location
);
172 analysis
.apply_statement_effect(state
, statement
, location
);
175 // Handle the statement at `to`.
177 let location
= Location { block, statement_index: to.statement_index }
;
178 let statement
= &block_data
.statements
[to
.statement_index
];
179 analysis
.apply_before_statement_effect(state
, statement
, location
);
181 if to
.effect
== Effect
::Before
{
185 analysis
.apply_statement_effect(state
, statement
, location
);
188 fn visit_results_in_block
<'mir
, 'tcx
, F
, R
>(
191 block_data
: &'mir mir
::BasicBlockData
<'tcx
>,
193 vis
: &mut impl ResultsVisitor
<'mir
, 'tcx
, FlowState
= F
>,
195 R
: ResultsVisitable
<'tcx
, FlowState
= F
>,
197 results
.reset_to_block_entry(state
, block
);
199 vis
.visit_block_end(&state
, block_data
, block
);
202 let loc
= Location { block, statement_index: block_data.statements.len() }
;
203 let term
= block_data
.terminator();
204 results
.reconstruct_before_terminator_effect(state
, term
, loc
);
205 vis
.visit_terminator_before_primary_effect(state
, term
, loc
);
206 results
.reconstruct_terminator_effect(state
, term
, loc
);
207 vis
.visit_terminator_after_primary_effect(state
, term
, loc
);
209 for (statement_index
, stmt
) in block_data
.statements
.iter().enumerate().rev() {
210 let loc
= Location { block, statement_index }
;
211 results
.reconstruct_before_statement_effect(state
, stmt
, loc
);
212 vis
.visit_statement_before_primary_effect(state
, stmt
, loc
);
213 results
.reconstruct_statement_effect(state
, stmt
, loc
);
214 vis
.visit_statement_after_primary_effect(state
, stmt
, loc
);
217 vis
.visit_block_start(state
, block_data
, block
);
220 fn join_state_into_successors_of
<'tcx
, A
>(
223 body
: &mir
::Body
<'tcx
>,
224 dead_unwinds
: Option
<&BitSet
<BasicBlock
>>,
225 exit_state
: &mut A
::Domain
,
226 (bb
, _bb_data
): (BasicBlock
, &'_ mir
::BasicBlockData
<'tcx
>),
227 mut propagate
: impl FnMut(BasicBlock
, &A
::Domain
),
231 for pred
in body
.predecessors()[bb
].iter().copied() {
232 match body
[pred
].terminator().kind
{
233 // Apply terminator-specific edge effects.
235 // FIXME(ecstaticmorse): Avoid cloning the exit state unconditionally.
236 mir
::TerminatorKind
::Call { destination, target: Some(dest), .. }
if dest
== bb
=> {
237 let mut tmp
= exit_state
.clone();
238 analysis
.apply_call_return_effect(
241 CallReturnPlaces
::Call(destination
),
243 propagate(pred
, &tmp
);
246 mir
::TerminatorKind
::InlineAsm
{
247 destination
: Some(dest
), ref operands
, ..
249 let mut tmp
= exit_state
.clone();
250 analysis
.apply_call_return_effect(
253 CallReturnPlaces
::InlineAsm(operands
),
255 propagate(pred
, &tmp
);
258 mir
::TerminatorKind
::Yield { resume, resume_arg, .. }
if resume
== bb
=> {
259 let mut tmp
= exit_state
.clone();
260 analysis
.apply_yield_resume_effect(&mut tmp
, resume
, resume_arg
);
261 propagate(pred
, &tmp
);
264 mir
::TerminatorKind
::SwitchInt { targets: _, ref discr, switch_ty: _ }
=> {
265 let mut applier
= BackwardSwitchIntEdgeEffectsApplier
{
270 propagate
: &mut propagate
,
271 effects_applied
: false,
274 analysis
.apply_switch_int_edge_effects(pred
, discr
, &mut applier
);
276 if !applier
.effects_applied
{
277 propagate(pred
, exit_state
)
281 // Ignore dead unwinds.
282 mir
::TerminatorKind
::Call { cleanup: Some(unwind), .. }
283 | mir
::TerminatorKind
::Assert { cleanup: Some(unwind), .. }
284 | mir
::TerminatorKind
::Drop { unwind: Some(unwind), .. }
285 | mir
::TerminatorKind
::DropAndReplace { unwind: Some(unwind), .. }
286 | mir
::TerminatorKind
::FalseUnwind { unwind: Some(unwind), .. }
287 | mir
::TerminatorKind
::InlineAsm { cleanup: Some(unwind), .. }
290 if dead_unwinds
.map_or(true, |dead
| !dead
.contains(bb
)) {
291 propagate(pred
, exit_state
);
295 _
=> propagate(pred
, exit_state
),
301 struct BackwardSwitchIntEdgeEffectsApplier
<'a
, 'tcx
, D
, F
> {
302 body
: &'a mir
::Body
<'tcx
>,
304 exit_state
: &'a
mut D
,
306 propagate
: &'a
mut F
,
308 effects_applied
: bool
,
311 impl<D
, F
> super::SwitchIntEdgeEffects
<D
> for BackwardSwitchIntEdgeEffectsApplier
<'_
, '_
, D
, F
>
314 F
: FnMut(BasicBlock
, &D
),
316 fn apply(&mut self, mut apply_edge_effect
: impl FnMut(&mut D
, SwitchIntTarget
)) {
317 assert
!(!self.effects_applied
);
319 let values
= &self.body
.switch_sources()[&(self.bb
, self.pred
)];
320 let targets
= values
.iter().map(|&value
| SwitchIntTarget { value, target: self.bb }
);
323 for target
in targets
{
324 let tmp
= opt_clone_from_or_clone(&mut tmp
, self.exit_state
);
325 apply_edge_effect(tmp
, target
);
326 (self.propagate
)(self.pred
, tmp
);
329 self.effects_applied
= true;
333 /// Dataflow that runs from the entry of a block (the first statement), to its exit (terminator).
336 impl Direction
for Forward
{
337 const IS_FORWARD
: bool
= true;
339 fn apply_effects_in_block
<'tcx
, A
>(
341 state
: &mut A
::Domain
,
343 block_data
: &mir
::BasicBlockData
<'tcx
>,
347 for (statement_index
, statement
) in block_data
.statements
.iter().enumerate() {
348 let location
= Location { block, statement_index }
;
349 analysis
.apply_before_statement_effect(state
, statement
, location
);
350 analysis
.apply_statement_effect(state
, statement
, location
);
353 let terminator
= block_data
.terminator();
354 let location
= Location { block, statement_index: block_data.statements.len() }
;
355 analysis
.apply_before_terminator_effect(state
, terminator
, location
);
356 analysis
.apply_terminator_effect(state
, terminator
, location
);
359 fn gen_kill_effects_in_block
<'tcx
, A
>(
361 trans
: &mut GenKillSet
<A
::Idx
>,
363 block_data
: &mir
::BasicBlockData
<'tcx
>,
365 A
: GenKillAnalysis
<'tcx
>,
367 for (statement_index
, statement
) in block_data
.statements
.iter().enumerate() {
368 let location
= Location { block, statement_index }
;
369 analysis
.before_statement_effect(trans
, statement
, location
);
370 analysis
.statement_effect(trans
, statement
, location
);
373 let terminator
= block_data
.terminator();
374 let location
= Location { block, statement_index: block_data.statements.len() }
;
375 analysis
.before_terminator_effect(trans
, terminator
, location
);
376 analysis
.terminator_effect(trans
, terminator
, location
);
379 fn apply_effects_in_range
<'tcx
, A
>(
381 state
: &mut A
::Domain
,
383 block_data
: &mir
::BasicBlockData
<'tcx
>,
384 effects
: RangeInclusive
<EffectIndex
>,
388 let (from
, to
) = (*effects
.start(), *effects
.end());
389 let terminator_index
= block_data
.statements
.len();
391 assert
!(to
.statement_index
<= terminator_index
);
392 assert
!(!to
.precedes_in_forward_order(from
));
394 // If we have applied the before affect of the statement or terminator at `from` but not its
395 // after effect, do so now and start the loop below from the next statement.
397 let first_unapplied_index
= match from
.effect
{
398 Effect
::Before
=> from
.statement_index
,
400 Effect
::Primary
if from
.statement_index
== terminator_index
=> {
401 debug_assert_eq
!(from
, to
);
403 let location
= Location { block, statement_index: terminator_index }
;
404 let terminator
= block_data
.terminator();
405 analysis
.apply_terminator_effect(state
, terminator
, location
);
410 let location
= Location { block, statement_index: from.statement_index }
;
411 let statement
= &block_data
.statements
[from
.statement_index
];
412 analysis
.apply_statement_effect(state
, statement
, location
);
414 // If we only needed to apply the after effect of the statement at `idx`, we are done.
419 from
.statement_index
+ 1
423 // Handle all statements between `from` and `to` whose effects must be applied in full.
425 for statement_index
in first_unapplied_index
..to
.statement_index
{
426 let location
= Location { block, statement_index }
;
427 let statement
= &block_data
.statements
[statement_index
];
428 analysis
.apply_before_statement_effect(state
, statement
, location
);
429 analysis
.apply_statement_effect(state
, statement
, location
);
432 // Handle the statement or terminator at `to`.
434 let location
= Location { block, statement_index: to.statement_index }
;
435 if to
.statement_index
== terminator_index
{
436 let terminator
= block_data
.terminator();
437 analysis
.apply_before_terminator_effect(state
, terminator
, location
);
439 if to
.effect
== Effect
::Primary
{
440 analysis
.apply_terminator_effect(state
, terminator
, location
);
443 let statement
= &block_data
.statements
[to
.statement_index
];
444 analysis
.apply_before_statement_effect(state
, statement
, location
);
446 if to
.effect
== Effect
::Primary
{
447 analysis
.apply_statement_effect(state
, statement
, location
);
452 fn visit_results_in_block
<'mir
, 'tcx
, F
, R
>(
455 block_data
: &'mir mir
::BasicBlockData
<'tcx
>,
457 vis
: &mut impl ResultsVisitor
<'mir
, 'tcx
, FlowState
= F
>,
459 R
: ResultsVisitable
<'tcx
, FlowState
= F
>,
461 results
.reset_to_block_entry(state
, block
);
463 vis
.visit_block_start(state
, block_data
, block
);
465 for (statement_index
, stmt
) in block_data
.statements
.iter().enumerate() {
466 let loc
= Location { block, statement_index }
;
467 results
.reconstruct_before_statement_effect(state
, stmt
, loc
);
468 vis
.visit_statement_before_primary_effect(state
, stmt
, loc
);
469 results
.reconstruct_statement_effect(state
, stmt
, loc
);
470 vis
.visit_statement_after_primary_effect(state
, stmt
, loc
);
473 let loc
= Location { block, statement_index: block_data.statements.len() }
;
474 let term
= block_data
.terminator();
475 results
.reconstruct_before_terminator_effect(state
, term
, loc
);
476 vis
.visit_terminator_before_primary_effect(state
, term
, loc
);
477 results
.reconstruct_terminator_effect(state
, term
, loc
);
478 vis
.visit_terminator_after_primary_effect(state
, term
, loc
);
480 vis
.visit_block_end(state
, block_data
, block
);
483 fn join_state_into_successors_of
<'tcx
, A
>(
486 _body
: &mir
::Body
<'tcx
>,
487 dead_unwinds
: Option
<&BitSet
<BasicBlock
>>,
488 exit_state
: &mut A
::Domain
,
489 (bb
, bb_data
): (BasicBlock
, &'_ mir
::BasicBlockData
<'tcx
>),
490 mut propagate
: impl FnMut(BasicBlock
, &A
::Domain
),
494 use mir
::TerminatorKind
::*;
495 match bb_data
.terminator().kind
{
496 Return
| Resume
| Abort
| GeneratorDrop
| Unreachable
=> {}
498 Goto { target }
=> propagate(target
, exit_state
),
500 Assert { target, cleanup: unwind, expected: _, msg: _, cond: _ }
501 | Drop { target, unwind, place: _ }
502 | DropAndReplace { target, unwind, value: _, place: _ }
503 | FalseUnwind { real_target: target, unwind }
=> {
504 if let Some(unwind
) = unwind
{
505 if dead_unwinds
.map_or(true, |dead
| !dead
.contains(bb
)) {
506 propagate(unwind
, exit_state
);
510 propagate(target
, exit_state
);
513 FalseEdge { real_target, imaginary_target }
=> {
514 propagate(real_target
, exit_state
);
515 propagate(imaginary_target
, exit_state
);
518 Yield { resume: target, drop, resume_arg, value: _ }
=> {
519 if let Some(drop
) = drop
{
520 propagate(drop
, exit_state
);
523 analysis
.apply_yield_resume_effect(exit_state
, target
, resume_arg
);
524 propagate(target
, exit_state
);
536 if let Some(unwind
) = cleanup
{
537 if dead_unwinds
.map_or(true, |dead
| !dead
.contains(bb
)) {
538 propagate(unwind
, exit_state
);
542 if let Some(target
) = target
{
543 // N.B.: This must be done *last*, otherwise the unwind path will see the call
545 analysis
.apply_call_return_effect(
548 CallReturnPlaces
::Call(destination
),
550 propagate(target
, exit_state
);
562 if let Some(unwind
) = cleanup
{
563 if dead_unwinds
.map_or(true, |dead
| !dead
.contains(bb
)) {
564 propagate(unwind
, exit_state
);
568 if let Some(target
) = destination
{
569 // N.B.: This must be done *last*, otherwise the unwind path will see the call
571 analysis
.apply_call_return_effect(
574 CallReturnPlaces
::InlineAsm(operands
),
576 propagate(target
, exit_state
);
580 SwitchInt { ref targets, ref discr, switch_ty: _ }
=> {
581 let mut applier
= ForwardSwitchIntEdgeEffectsApplier
{
585 effects_applied
: false,
588 analysis
.apply_switch_int_edge_effects(bb
, discr
, &mut applier
);
590 let ForwardSwitchIntEdgeEffectsApplier
{
597 if !effects_applied
{
598 for target
in targets
.all_targets() {
599 propagate(*target
, exit_state
);
607 struct ForwardSwitchIntEdgeEffectsApplier
<'a
, D
, F
> {
608 exit_state
: &'a
mut D
,
609 targets
: &'a SwitchTargets
,
612 effects_applied
: bool
,
615 impl<D
, F
> super::SwitchIntEdgeEffects
<D
> for ForwardSwitchIntEdgeEffectsApplier
<'_
, D
, F
>
618 F
: FnMut(BasicBlock
, &D
),
620 fn apply(&mut self, mut apply_edge_effect
: impl FnMut(&mut D
, SwitchIntTarget
)) {
621 assert
!(!self.effects_applied
);
624 for (value
, target
) in self.targets
.iter() {
625 let tmp
= opt_clone_from_or_clone(&mut tmp
, self.exit_state
);
626 apply_edge_effect(tmp
, SwitchIntTarget { value: Some(value), target }
);
627 (self.propagate
)(target
, tmp
);
630 // Once we get to the final, "otherwise" branch, there is no need to preserve `exit_state`,
631 // so pass it directly to `apply_edge_effect` to save a clone of the dataflow state.
632 let otherwise
= self.targets
.otherwise();
633 apply_edge_effect(self.exit_state
, SwitchIntTarget { value: None, target: otherwise }
);
634 (self.propagate
)(otherwise
, self.exit_state
);
636 self.effects_applied
= true;
640 /// An analogue of `Option::get_or_insert_with` that stores a clone of `val` into `opt`, but uses
641 /// the more efficient `clone_from` if `opt` was `Some`.
643 /// Returns a mutable reference to the new clone that resides in `opt`.
645 // FIXME: Figure out how to express this using `Option::clone_from`, or maybe lift it into the
647 fn opt_clone_from_or_clone
<'a
, T
: Clone
>(opt
: &'a
mut Option
<T
>, val
: &T
) -> &'a
mut T
{
649 let ret
= opt
.as_mut().unwrap();
653 *opt
= Some(val
.clone());
654 opt
.as_mut().unwrap()