src/librustc_mir/dataflow/framework/direction.rs

   1 use rustc_index::bit_set::BitSet;
   2 use rustc_middle::mir::{self, BasicBlock, Location};
   3 use rustc_middle::ty::{self, TyCtxt};
   4 use std::ops::RangeInclusive;
   5
   6 use super::visitor::{ResultsVisitable, ResultsVisitor};
   7 use super::{Analysis, Effect, EffectIndex, GenKillAnalysis, GenKillSet};
   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 BitSet<A::Idx>,
  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 BitSet<A::Idx>,
  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 BitSet<A::Idx>,
  59         block: (BasicBlock, &'_ mir::BasicBlockData<'tcx>),
  60         propagate: impl FnMut(BasicBlock, &BitSet<A::Idx>),
  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 BitSet<A::Idx>,
  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 BitSet<A::Idx>,
 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 BitSet<A::Idx>,
 228         (bb, _bb_data): (BasicBlock, &'_ mir::BasicBlockData<'tcx>),
 229         mut propagate: impl FnMut(BasicBlock, &BitSet<A::Idx>),
 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 BitSet<A::Idx>,
 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 BitSet<A::Idx>,
 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 BitSet<A::Idx>,
 432         (bb, bb_data): (BasicBlock, &'_ mir::BasicBlockData<'tcx>),
 433         mut propagate: impl FnMut(BasicBlock, &BitSet<A::Idx>),
 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 enum_ = discr
 493                     .place()
 494                     .and_then(|discr| switch_on_enum_discriminant(tcx, &body, bb_data, discr));
 495                 match enum_ {
 496                     // If this is a switch on an enum discriminant, a custom effect may be applied
 497                     // along each outgoing edge.
 498                     Some((enum_place, enum_def)) => {
 499                         // MIR building adds discriminants to the `values` array in the same order as they
 500                         // are yielded by `AdtDef::discriminants`. We rely on this to match each
 501                         // discriminant in `values` to its corresponding variant in linear time.
 502                         let mut tmp = BitSet::new_empty(exit_state.domain_size());
 503                         let mut discriminants = enum_def.discriminants(tcx);
 504                         for (value, target) in values.iter().zip(targets.iter().copied()) {
 505                             let (variant_idx, _) =
 506                                 discriminants.find(|&(_, discr)| discr.val == *value).expect(
 507                                     "Order of `AdtDef::discriminants` differed \
 508                                          from that of `SwitchInt::values`",
 509                                 );
 510
 511                             tmp.overwrite(exit_state);
 512                             analysis.apply_discriminant_switch_effect(
 513                                 &mut tmp,
 514                                 bb,
 515                                 enum_place,
 516                                 enum_def,
 517                                 variant_idx,
 518                             );
 519                             propagate(target, &tmp);
 520                         }
 521
 522                         // Move out of `tmp` so we don't accidentally use it below.
 523                         std::mem::drop(tmp);
 524
 525                         // Propagate dataflow state along the "otherwise" edge.
 526                         let otherwise = targets.last().copied().unwrap();
 527                         propagate(otherwise, exit_state)
 528                     }
 529
 530                     // Otherwise, it's just a normal `SwitchInt`, and every successor sees the same
 531                     // exit state.
 532                     None => {
 533                         for target in targets.iter().copied() {
 534                             propagate(target, exit_state);
 535                         }
 536                     }
 537                 }
 538             }
 539         }
 540     }
 541 }
 542
 543 /// Inspect a `SwitchInt`-terminated basic block to see if the condition of that `SwitchInt` is
 544 /// an enum discriminant.
 545 ///
 546 /// We expect such blocks to have a call to `discriminant` as their last statement like so:
 547 ///   _42 = discriminant(_1)
 548 ///   SwitchInt(_42, ..)
 549 ///
 550 /// If the basic block matches this pattern, this function returns the place corresponding to the
 551 /// enum (`_1` in the example above) as well as the `AdtDef` of that enum.
 552 fn switch_on_enum_discriminant(
 553     tcx: TyCtxt<'tcx>,
 554     body: &'mir mir::Body<'tcx>,
 555     block: &'mir mir::BasicBlockData<'tcx>,
 556     switch_on: mir::Place<'tcx>,
 557 ) -> Option<(mir::Place<'tcx>, &'tcx ty::AdtDef)> {
 558     match block.statements.last().map(|stmt| &stmt.kind) {
 559         Some(mir::StatementKind::Assign(box (lhs, mir::Rvalue::Discriminant(discriminated))))
 560             if *lhs == switch_on =>
 561         {
 562             match &discriminated.ty(body, tcx).ty.kind {
 563                 ty::Adt(def, _) => Some((*discriminated, def)),
 564
 565                 // `Rvalue::Discriminant` is also used to get the active yield point for a
 566                 // generator, but we do not need edge-specific effects in that case. This may
 567                 // change in the future.
 568                 ty::Generator(..) => None,
 569
 570                 t => bug!("`discriminant` called on unexpected type {:?}", t),
 571             }
 572         }
 573
 574         _ => None,
 575     }
 576 }