compiler/rustc_mir/src/dataflow/framework/direction.rs

   1 use rustc_index::bit_set::BitSet;
   2 use rustc_middle::mir::{self, BasicBlock, Location};
   3 use rustc_middle::ty::TyCtxt;
   4 use std::ops::RangeInclusive;
   5
   6 use super::visitor::{ResultsVisitable, ResultsVisitor};
   7 use super::{Analysis, Effect, EffectIndex, GenKillAnalysis, GenKillSet, SwitchIntTarget};
   8
   9 pub trait Direction {
  10     fn is_forward() -> bool;
  11
  12     fn is_backward() -> bool {
  13         !Self::is_forward()
  14     }
  15
  16     /// Applies all effects between the given `EffectIndex`s.
  17     ///
  18     /// `effects.start()` must precede or equal `effects.end()` in this direction.
  19     fn apply_effects_in_range<A>(
  20         analysis: &A,
  21         state: &mut A::Domain,
  22         block: BasicBlock,
  23         block_data: &mir::BasicBlockData<'tcx>,
  24         effects: RangeInclusive<EffectIndex>,
  25     ) where
  26         A: Analysis<'tcx>;
  27
  28     fn apply_effects_in_block<A>(
  29         analysis: &A,
  30         state: &mut A::Domain,
  31         block: BasicBlock,
  32         block_data: &mir::BasicBlockData<'tcx>,
  33     ) where
  34         A: Analysis<'tcx>;
  35
  36     fn gen_kill_effects_in_block<A>(
  37         analysis: &A,
  38         trans: &mut GenKillSet<A::Idx>,
  39         block: BasicBlock,
  40         block_data: &mir::BasicBlockData<'tcx>,
  41     ) where
  42         A: GenKillAnalysis<'tcx>;
  43
  44     fn visit_results_in_block<F, R>(
  45         state: &mut F,
  46         block: BasicBlock,
  47         block_data: &'mir mir::BasicBlockData<'tcx>,
  48         results: &R,
  49         vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = F>,
  50     ) where
  51         R: ResultsVisitable<'tcx, FlowState = F>;
  52
  53     fn join_state_into_successors_of<A>(
  54         analysis: &A,
  55         tcx: TyCtxt<'tcx>,
  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),
  61     ) where
  62         A: Analysis<'tcx>;
  63 }
  64
  65 /// Dataflow that runs from the exit of a block (the terminator), to its entry (the first statement).
  66 pub struct Backward;
  67
  68 impl Direction for Backward {
  69     fn is_forward() -> bool {
  70         false
  71     }
  72
  73     fn apply_effects_in_block<A>(
  74         analysis: &A,
  75         state: &mut A::Domain,
  76         block: BasicBlock,
  77         block_data: &mir::BasicBlockData<'tcx>,
  78     ) where
  79         A: Analysis<'tcx>,
  80     {
  81         let terminator = block_data.terminator();
  82         let location = Location { block, statement_index: block_data.statements.len() };
  83         analysis.apply_before_terminator_effect(state, terminator, location);
  84         analysis.apply_terminator_effect(state, terminator, location);
  85
  86         for (statement_index, statement) in block_data.statements.iter().enumerate().rev() {
  87             let location = Location { block, statement_index };
  88             analysis.apply_before_statement_effect(state, statement, location);
  89             analysis.apply_statement_effect(state, statement, location);
  90         }
  91     }
  92
  93     fn gen_kill_effects_in_block<A>(
  94         analysis: &A,
  95         trans: &mut GenKillSet<A::Idx>,
  96         block: BasicBlock,
  97         block_data: &mir::BasicBlockData<'tcx>,
  98     ) where
  99         A: GenKillAnalysis<'tcx>,
 100     {
 101         let terminator = block_data.terminator();
 102         let location = Location { block, statement_index: block_data.statements.len() };
 103         analysis.before_terminator_effect(trans, terminator, location);
 104         analysis.terminator_effect(trans, terminator, location);
 105
 106         for (statement_index, statement) in block_data.statements.iter().enumerate().rev() {
 107             let location = Location { block, statement_index };
 108             analysis.before_statement_effect(trans, statement, location);
 109             analysis.statement_effect(trans, statement, location);
 110         }
 111     }
 112
 113     fn apply_effects_in_range<A>(
 114         analysis: &A,
 115         state: &mut A::Domain,
 116         block: BasicBlock,
 117         block_data: &mir::BasicBlockData<'tcx>,
 118         effects: RangeInclusive<EffectIndex>,
 119     ) where
 120         A: Analysis<'tcx>,
 121     {
 122         let (from, to) = (*effects.start(), *effects.end());
 123         let terminator_index = block_data.statements.len();
 124
 125         assert!(from.statement_index <= terminator_index);
 126         assert!(!to.precedes_in_backward_order(from));
 127
 128         // Handle the statement (or terminator) at `from`.
 129
 130         let next_effect = match from.effect {
 131             // If we need to apply the terminator effect in all or in part, do so now.
 132             _ if from.statement_index == terminator_index => {
 133                 let location = Location { block, statement_index: from.statement_index };
 134                 let terminator = block_data.terminator();
 135
 136                 if from.effect == Effect::Before {
 137                     analysis.apply_before_terminator_effect(state, terminator, location);
 138                     if to == Effect::Before.at_index(terminator_index) {
 139                         return;
 140                     }
 141                 }
 142
 143                 analysis.apply_terminator_effect(state, terminator, location);
 144                 if to == Effect::Primary.at_index(terminator_index) {
 145                     return;
 146                 }
 147
 148                 // If `from.statement_index` is `0`, we will have hit one of the earlier comparisons
 149                 // with `to`.
 150                 from.statement_index - 1
 151             }
 152
 153             Effect::Primary => {
 154                 let location = Location { block, statement_index: from.statement_index };
 155                 let statement = &block_data.statements[from.statement_index];
 156
 157                 analysis.apply_statement_effect(state, statement, location);
 158                 if to == Effect::Primary.at_index(from.statement_index) {
 159                     return;
 160                 }
 161
 162                 from.statement_index - 1
 163             }
 164
 165             Effect::Before => from.statement_index,
 166         };
 167
 168         // Handle all statements between `first_unapplied_idx` and `to.statement_index`.
 169
 170         for statement_index in (to.statement_index..next_effect).rev().map(|i| i + 1) {
 171             let location = Location { block, statement_index };
 172             let statement = &block_data.statements[statement_index];
 173             analysis.apply_before_statement_effect(state, statement, location);
 174             analysis.apply_statement_effect(state, statement, location);
 175         }
 176
 177         // Handle the statement at `to`.
 178
 179         let location = Location { block, statement_index: to.statement_index };
 180         let statement = &block_data.statements[to.statement_index];
 181         analysis.apply_before_statement_effect(state, statement, location);
 182
 183         if to.effect == Effect::Before {
 184             return;
 185         }
 186
 187         analysis.apply_statement_effect(state, statement, location);
 188     }
 189
 190     fn visit_results_in_block<F, R>(
 191         state: &mut F,
 192         block: BasicBlock,
 193         block_data: &'mir mir::BasicBlockData<'tcx>,
 194         results: &R,
 195         vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = F>,
 196     ) where
 197         R: ResultsVisitable<'tcx, FlowState = F>,
 198     {
 199         results.reset_to_block_entry(state, block);
 200
 201         vis.visit_block_end(&state, block_data, block);
 202
 203         // Terminator
 204         let loc = Location { block, statement_index: block_data.statements.len() };
 205         let term = block_data.terminator();
 206         results.reconstruct_before_terminator_effect(state, term, loc);
 207         vis.visit_terminator_before_primary_effect(state, term, loc);
 208         results.reconstruct_terminator_effect(state, term, loc);
 209         vis.visit_terminator_after_primary_effect(state, term, loc);
 210
 211         for (statement_index, stmt) in block_data.statements.iter().enumerate().rev() {
 212             let loc = Location { block, statement_index };
 213             results.reconstruct_before_statement_effect(state, stmt, loc);
 214             vis.visit_statement_before_primary_effect(state, stmt, loc);
 215             results.reconstruct_statement_effect(state, stmt, loc);
 216             vis.visit_statement_after_primary_effect(state, stmt, loc);
 217         }
 218
 219         vis.visit_block_start(state, block_data, block);
 220     }
 221
 222     fn join_state_into_successors_of<A>(
 223         analysis: &A,
 224         _tcx: TyCtxt<'tcx>,
 225         body: &mir::Body<'tcx>,
 226         dead_unwinds: Option<&BitSet<BasicBlock>>,
 227         exit_state: &mut A::Domain,
 228         (bb, _bb_data): (BasicBlock, &'_ mir::BasicBlockData<'tcx>),
 229         mut propagate: impl FnMut(BasicBlock, &A::Domain),
 230     ) where
 231         A: Analysis<'tcx>,
 232     {
 233         for pred in body.predecessors()[bb].iter().copied() {
 234             match body[pred].terminator().kind {
 235                 // Apply terminator-specific edge effects.
 236                 //
 237                 // FIXME(ecstaticmorse): Avoid cloning the exit state unconditionally.
 238                 mir::TerminatorKind::Call {
 239                     destination: Some((return_place, dest)),
 240                     ref func,
 241                     ref args,
 242                     ..
 243                 } if dest == bb => {
 244                     let mut tmp = exit_state.clone();
 245                     analysis.apply_call_return_effect(&mut tmp, pred, func, args, return_place);
 246                     propagate(pred, &tmp);
 247                 }
 248
 249                 mir::TerminatorKind::Yield { resume, resume_arg, .. } if resume == bb => {
 250                     let mut tmp = exit_state.clone();
 251                     analysis.apply_yield_resume_effect(&mut tmp, resume, resume_arg);
 252                     propagate(pred, &tmp);
 253                 }
 254
 255                 // Ignore dead unwinds.
 256                 mir::TerminatorKind::Call { cleanup: Some(unwind), .. }
 257                 | mir::TerminatorKind::Assert { cleanup: Some(unwind), .. }
 258                 | mir::TerminatorKind::Drop { unwind: Some(unwind), .. }
 259                 | mir::TerminatorKind::DropAndReplace { unwind: Some(unwind), .. }
 260                 | mir::TerminatorKind::FalseUnwind { unwind: Some(unwind), .. }
 261                     if unwind == bb =>
 262                 {
 263                     if dead_unwinds.map_or(true, |dead| !dead.contains(bb)) {
 264                         propagate(pred, exit_state);
 265                     }
 266                 }
 267
 268                 _ => propagate(pred, exit_state),
 269             }
 270         }
 271     }
 272 }
 273
 274 /// Dataflow that runs from the entry of a block (the first statement), to its exit (terminator).
 275 pub struct Forward;
 276
 277 impl Direction for Forward {
 278     fn is_forward() -> bool {
 279         true
 280     }
 281
 282     fn apply_effects_in_block<A>(
 283         analysis: &A,
 284         state: &mut A::Domain,
 285         block: BasicBlock,
 286         block_data: &mir::BasicBlockData<'tcx>,
 287     ) where
 288         A: Analysis<'tcx>,
 289     {
 290         for (statement_index, statement) in block_data.statements.iter().enumerate() {
 291             let location = Location { block, statement_index };
 292             analysis.apply_before_statement_effect(state, statement, location);
 293             analysis.apply_statement_effect(state, statement, location);
 294         }
 295
 296         let terminator = block_data.terminator();
 297         let location = Location { block, statement_index: block_data.statements.len() };
 298         analysis.apply_before_terminator_effect(state, terminator, location);
 299         analysis.apply_terminator_effect(state, terminator, location);
 300     }
 301
 302     fn gen_kill_effects_in_block<A>(
 303         analysis: &A,
 304         trans: &mut GenKillSet<A::Idx>,
 305         block: BasicBlock,
 306         block_data: &mir::BasicBlockData<'tcx>,
 307     ) where
 308         A: GenKillAnalysis<'tcx>,
 309     {
 310         for (statement_index, statement) in block_data.statements.iter().enumerate() {
 311             let location = Location { block, statement_index };
 312             analysis.before_statement_effect(trans, statement, location);
 313             analysis.statement_effect(trans, statement, location);
 314         }
 315
 316         let terminator = block_data.terminator();
 317         let location = Location { block, statement_index: block_data.statements.len() };
 318         analysis.before_terminator_effect(trans, terminator, location);
 319         analysis.terminator_effect(trans, terminator, location);
 320     }
 321
 322     fn apply_effects_in_range<A>(
 323         analysis: &A,
 324         state: &mut A::Domain,
 325         block: BasicBlock,
 326         block_data: &mir::BasicBlockData<'tcx>,
 327         effects: RangeInclusive<EffectIndex>,
 328     ) where
 329         A: Analysis<'tcx>,
 330     {
 331         let (from, to) = (*effects.start(), *effects.end());
 332         let terminator_index = block_data.statements.len();
 333
 334         assert!(to.statement_index <= terminator_index);
 335         assert!(!to.precedes_in_forward_order(from));
 336
 337         // If we have applied the before affect of the statement or terminator at `from` but not its
 338         // after effect, do so now and start the loop below from the next statement.
 339
 340         let first_unapplied_index = match from.effect {
 341             Effect::Before => from.statement_index,
 342
 343             Effect::Primary if from.statement_index == terminator_index => {
 344                 debug_assert_eq!(from, to);
 345
 346                 let location = Location { block, statement_index: terminator_index };
 347                 let terminator = block_data.terminator();
 348                 analysis.apply_terminator_effect(state, terminator, location);
 349                 return;
 350             }
 351
 352             Effect::Primary => {
 353                 let location = Location { block, statement_index: from.statement_index };
 354                 let statement = &block_data.statements[from.statement_index];
 355                 analysis.apply_statement_effect(state, statement, location);
 356
 357                 // If we only needed to apply the after effect of the statement at `idx`, we are done.
 358                 if from == to {
 359                     return;
 360                 }
 361
 362                 from.statement_index + 1
 363             }
 364         };
 365
 366         // Handle all statements between `from` and `to` whose effects must be applied in full.
 367
 368         for statement_index in first_unapplied_index..to.statement_index {
 369             let location = Location { block, statement_index };
 370             let statement = &block_data.statements[statement_index];
 371             analysis.apply_before_statement_effect(state, statement, location);
 372             analysis.apply_statement_effect(state, statement, location);
 373         }
 374
 375         // Handle the statement or terminator at `to`.
 376
 377         let location = Location { block, statement_index: to.statement_index };
 378         if to.statement_index == terminator_index {
 379             let terminator = block_data.terminator();
 380             analysis.apply_before_terminator_effect(state, terminator, location);
 381
 382             if to.effect == Effect::Primary {
 383                 analysis.apply_terminator_effect(state, terminator, location);
 384             }
 385         } else {
 386             let statement = &block_data.statements[to.statement_index];
 387             analysis.apply_before_statement_effect(state, statement, location);
 388
 389             if to.effect == Effect::Primary {
 390                 analysis.apply_statement_effect(state, statement, location);
 391             }
 392         }
 393     }
 394
 395     fn visit_results_in_block<F, R>(
 396         state: &mut F,
 397         block: BasicBlock,
 398         block_data: &'mir mir::BasicBlockData<'tcx>,
 399         results: &R,
 400         vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = F>,
 401     ) where
 402         R: ResultsVisitable<'tcx, FlowState = F>,
 403     {
 404         results.reset_to_block_entry(state, block);
 405
 406         vis.visit_block_start(state, block_data, block);
 407
 408         for (statement_index, stmt) in block_data.statements.iter().enumerate() {
 409             let loc = Location { block, statement_index };
 410             results.reconstruct_before_statement_effect(state, stmt, loc);
 411             vis.visit_statement_before_primary_effect(state, stmt, loc);
 412             results.reconstruct_statement_effect(state, stmt, loc);
 413             vis.visit_statement_after_primary_effect(state, stmt, loc);
 414         }
 415
 416         let loc = Location { block, statement_index: block_data.statements.len() };
 417         let term = block_data.terminator();
 418         results.reconstruct_before_terminator_effect(state, term, loc);
 419         vis.visit_terminator_before_primary_effect(state, term, loc);
 420         results.reconstruct_terminator_effect(state, term, loc);
 421         vis.visit_terminator_after_primary_effect(state, term, loc);
 422
 423         vis.visit_block_end(state, block_data, block);
 424     }
 425
 426     fn join_state_into_successors_of<A>(
 427         analysis: &A,
 428         _tcx: TyCtxt<'tcx>,
 429         _body: &mir::Body<'tcx>,
 430         dead_unwinds: Option<&BitSet<BasicBlock>>,
 431         exit_state: &mut A::Domain,
 432         (bb, bb_data): (BasicBlock, &'_ mir::BasicBlockData<'tcx>),
 433         mut propagate: impl FnMut(BasicBlock, &A::Domain),
 434     ) where
 435         A: Analysis<'tcx>,
 436     {
 437         use mir::TerminatorKind::*;
 438         match bb_data.terminator().kind {
 439             Return | Resume | Abort | GeneratorDrop | Unreachable => {}
 440
 441             Goto { target } => propagate(target, exit_state),
 442
 443             Assert { target, cleanup: unwind, expected: _, msg: _, cond: _ }
 444             | Drop { target, unwind, place: _ }
 445             | DropAndReplace { target, unwind, value: _, place: _ }
 446             | FalseUnwind { real_target: target, unwind } => {
 447                 if let Some(unwind) = unwind {
 448                     if dead_unwinds.map_or(true, |dead| !dead.contains(bb)) {
 449                         propagate(unwind, exit_state);
 450                     }
 451                 }
 452
 453                 propagate(target, exit_state);
 454             }
 455
 456             FalseEdge { real_target, imaginary_target } => {
 457                 propagate(real_target, exit_state);
 458                 propagate(imaginary_target, exit_state);
 459             }
 460
 461             Yield { resume: target, drop, resume_arg, value: _ } => {
 462                 if let Some(drop) = drop {
 463                     propagate(drop, exit_state);
 464                 }
 465
 466                 analysis.apply_yield_resume_effect(exit_state, target, resume_arg);
 467                 propagate(target, exit_state);
 468             }
 469
 470             Call { cleanup, destination, ref func, ref args, from_hir_call: _, fn_span: _ } => {
 471                 if let Some(unwind) = cleanup {
 472                     if dead_unwinds.map_or(true, |dead| !dead.contains(bb)) {
 473                         propagate(unwind, exit_state);
 474                     }
 475                 }
 476
 477                 if let Some((dest_place, target)) = destination {
 478                     // N.B.: This must be done *last*, otherwise the unwind path will see the call
 479                     // return effect.
 480                     analysis.apply_call_return_effect(exit_state, bb, func, args, dest_place);
 481                     propagate(target, exit_state);
 482                 }
 483             }
 484
 485             InlineAsm { template: _, operands: _, options: _, line_spans: _, destination } => {
 486                 if let Some(target) = destination {
 487                     propagate(target, exit_state);
 488                 }
 489             }
 490
 491             SwitchInt { ref targets, ref values, ref discr, switch_ty: _ } => {
 492                 let mut applier = SwitchIntEdgeEffectApplier {
 493                     exit_state,
 494                     targets: targets.as_ref(),
 495                     values: values.as_ref(),
 496                     propagate,
 497                     effects_applied: false,
 498                 };
 499
 500                 analysis.apply_switch_int_edge_effects(bb, discr, &mut applier);
 501
 502                 let SwitchIntEdgeEffectApplier {
 503                     exit_state, mut propagate, effects_applied, ..
 504                 } = applier;
 505
 506                 if !effects_applied {
 507                     for &target in targets.iter() {
 508                         propagate(target, exit_state);
 509                     }
 510                 }
 511             }
 512         }
 513     }
 514 }
 515
 516 struct SwitchIntEdgeEffectApplier<'a, D, F> {
 517     exit_state: &'a mut D,
 518     values: &'a [u128],
 519     targets: &'a [BasicBlock],
 520     propagate: F,
 521
 522     effects_applied: bool,
 523 }
 524
 525 impl<D, F> super::SwitchIntEdgeEffects<D> for SwitchIntEdgeEffectApplier<'_, D, F>
 526 where
 527     D: Clone,
 528     F: FnMut(BasicBlock, &D),
 529 {
 530     fn apply(&mut self, mut apply_edge_effect: impl FnMut(&mut D, SwitchIntTarget)) {
 531         assert!(!self.effects_applied);
 532
 533         let mut tmp = None;
 534         for (&value, &target) in self.values.iter().zip(self.targets.iter()) {
 535             let tmp = opt_clone_from_or_clone(&mut tmp, self.exit_state);
 536             apply_edge_effect(tmp, SwitchIntTarget { value: Some(value), target });
 537             (self.propagate)(target, tmp);
 538         }
 539
 540         // Once we get to the final, "otherwise" branch, there is no need to preserve `exit_state`,
 541         // so pass it directly to `apply_edge_effect` to save a clone of the dataflow state.
 542         let otherwise = self.targets.last().copied().unwrap();
 543         apply_edge_effect(self.exit_state, SwitchIntTarget { value: None, target: otherwise });
 544         (self.propagate)(otherwise, self.exit_state);
 545
 546         self.effects_applied = true;
 547     }
 548 }
 549
 550 /// An analogue of `Option::get_or_insert_with` that stores a clone of `val` into `opt`, but uses
 551 /// the more efficient `clone_from` if `opt` was `Some`.
 552 ///
 553 /// Returns a mutable reference to the new clone that resides in `opt`.
 554 //
 555 // FIXME: Figure out how to express this using `Option::clone_from`, or maybe lift it into the
 556 // standard library?
 557 fn opt_clone_from_or_clone<T: Clone>(opt: &'a mut Option<T>, val: &T) -> &'a mut T {
 558     if opt.is_some() {
 559         let ret = opt.as_mut().unwrap();
 560         ret.clone_from(val);
 561         ret
 562     } else {
 563         *opt = Some(val.clone());
 564         opt.as_mut().unwrap()
 565     }
 566 }