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.basic_blocks.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 } => {
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.basic_blocks.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 } => {
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()