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

   1 //! Random access inspection of the results of a dataflow analysis.
   2
   3 use std::borrow::Borrow;
   4 use std::cmp::Ordering;
   5
   6 use rustc_index::bit_set::BitSet;
   7 use rustc_index::vec::Idx;
   8 use rustc_middle::mir::{self, BasicBlock, Location};
   9
  10 use super::{Analysis, Direction, Effect, EffectIndex, Results};
  11
  12 /// A `ResultsCursor` that borrows the underlying `Results`.
  13 pub type ResultsRefCursor<'a, 'mir, 'tcx, A> = ResultsCursor<'mir, 'tcx, A, &'a Results<'tcx, A>>;
  14
  15 /// Allows random access inspection of the results of a dataflow analysis.
  16 ///
  17 /// This cursor only has linear performance within a basic block when its statements are visited in
  18 /// the same order as the `DIRECTION` of the analysis. In the worst case—when statements are
  19 /// visited in *reverse* order—performance will be quadratic in the number of statements in the
  20 /// block. The order in which basic blocks are inspected has no impact on performance.
  21 ///
  22 /// A `ResultsCursor` can either own (the default) or borrow the dataflow results it inspects. The
  23 /// type of ownership is determined by `R` (see `ResultsRefCursor` above).
  24 pub struct ResultsCursor<'mir, 'tcx, A, R = Results<'tcx, A>>
  25 where
  26     A: Analysis<'tcx>,
  27 {
  28     body: &'mir mir::Body<'tcx>,
  29     results: R,
  30     state: A::Domain,
  31
  32     pos: CursorPosition,
  33
  34     /// Indicates that `state` has been modified with a custom effect.
  35     ///
  36     /// When this flag is set, we need to reset to an entry set before doing a seek.
  37     state_needs_reset: bool,
  38
  39     #[cfg(debug_assertions)]
  40     reachable_blocks: BitSet<BasicBlock>,
  41 }
  42
  43 impl<'mir, 'tcx, A, R> ResultsCursor<'mir, 'tcx, A, R>
  44 where
  45     A: Analysis<'tcx>,
  46     R: Borrow<Results<'tcx, A>>,
  47 {
  48     /// Returns a new cursor that can inspect `results`.
  49     pub fn new(body: &'mir mir::Body<'tcx>, results: R) -> Self {
  50         let bottom_value = results.borrow().analysis.bottom_value(body);
  51         ResultsCursor {
  52             body,
  53             results,
  54
  55             // Initialize to the `bottom_value` and set `state_needs_reset` to tell the cursor that
  56             // it needs to reset to block entry before the first seek. The cursor position is
  57             // immaterial.
  58             state_needs_reset: true,
  59             state: bottom_value,
  60             pos: CursorPosition::block_entry(mir::START_BLOCK),
  61
  62             #[cfg(debug_assertions)]
  63             reachable_blocks: mir::traversal::reachable_as_bitset(body),
  64         }
  65     }
  66
  67     pub fn body(&self) -> &'mir mir::Body<'tcx> {
  68         self.body
  69     }
  70
  71     /// Returns the underlying `Results`.
  72     pub fn results(&self) -> &Results<'tcx, A> {
  73         &self.results.borrow()
  74     }
  75
  76     /// Returns the `Analysis` used to generate the underlying `Results`.
  77     pub fn analysis(&self) -> &A {
  78         &self.results.borrow().analysis
  79     }
  80
  81     /// Returns the dataflow state at the current location.
  82     pub fn get(&self) -> &A::Domain {
  83         &self.state
  84     }
  85
  86     /// Resets the cursor to hold the entry set for the given basic block.
  87     ///
  88     /// For forward dataflow analyses, this is the dataflow state prior to the first statement.
  89     ///
  90     /// For backward dataflow analyses, this is the dataflow state after the terminator.
  91     pub(super) fn seek_to_block_entry(&mut self, block: BasicBlock) {
  92         #[cfg(debug_assertions)]
  93         assert!(self.reachable_blocks.contains(block));
  94
  95         self.state.clone_from(&self.results.borrow().entry_set_for_block(block));
  96         self.pos = CursorPosition::block_entry(block);
  97         self.state_needs_reset = false;
  98     }
  99
 100     /// Resets the cursor to hold the state prior to the first statement in a basic block.
 101     ///
 102     /// For forward analyses, this is the entry set for the given block.
 103     ///
 104     /// For backward analyses, this is the state that will be propagated to its
 105     /// predecessors (ignoring edge-specific effects).
 106     pub fn seek_to_block_start(&mut self, block: BasicBlock) {
 107         if A::Direction::is_forward() {
 108             self.seek_to_block_entry(block)
 109         } else {
 110             self.seek_after(Location { block, statement_index: 0 }, Effect::Primary)
 111         }
 112     }
 113
 114     /// Resets the cursor to hold the state after the terminator in a basic block.
 115     ///
 116     /// For backward analyses, this is the entry set for the given block.
 117     ///
 118     /// For forward analyses, this is the state that will be propagated to its
 119     /// successors (ignoring edge-specific effects).
 120     pub fn seek_to_block_end(&mut self, block: BasicBlock) {
 121         if A::Direction::is_backward() {
 122             self.seek_to_block_entry(block)
 123         } else {
 124             self.seek_after(self.body.terminator_loc(block), Effect::Primary)
 125         }
 126     }
 127
 128     /// Advances the cursor to hold the dataflow state at `target` before its "primary" effect is
 129     /// applied.
 130     ///
 131     /// The "before" effect at the target location *will be* applied.
 132     pub fn seek_before_primary_effect(&mut self, target: Location) {
 133         self.seek_after(target, Effect::Before)
 134     }
 135
 136     /// Advances the cursor to hold the dataflow state at `target` after its "primary" effect is
 137     /// applied.
 138     ///
 139     /// The "before" effect at the target location will be applied as well.
 140     pub fn seek_after_primary_effect(&mut self, target: Location) {
 141         self.seek_after(target, Effect::Primary)
 142     }
 143
 144     fn seek_after(&mut self, target: Location, effect: Effect) {
 145         assert!(target <= self.body.terminator_loc(target.block));
 146
 147         // Reset to the entry of the target block if any of the following are true:
 148         //   - A custom effect has been applied to the cursor state.
 149         //   - We are in a different block than the target.
 150         //   - We are in the same block but have advanced past the target effect.
 151         if self.state_needs_reset || self.pos.block != target.block {
 152             self.seek_to_block_entry(target.block);
 153         } else if let Some(curr_effect) = self.pos.curr_effect_index {
 154             let mut ord = curr_effect.statement_index.cmp(&target.statement_index);
 155             if A::Direction::is_backward() {
 156                 ord = ord.reverse()
 157             }
 158
 159             match ord.then_with(|| curr_effect.effect.cmp(&effect)) {
 160                 Ordering::Equal => return,
 161                 Ordering::Greater => self.seek_to_block_entry(target.block),
 162                 Ordering::Less => {}
 163             }
 164         }
 165
 166         // At this point, the cursor is in the same block as the target location at an earlier
 167         // statement.
 168         debug_assert_eq!(target.block, self.pos.block);
 169
 170         let block_data = &self.body[target.block];
 171         let next_effect = if A::Direction::is_forward() {
 172             #[rustfmt::skip]
 173             self.pos.curr_effect_index.map_or_else(
 174                 || Effect::Before.at_index(0),
 175                 EffectIndex::next_in_forward_order,
 176             )
 177         } else {
 178             self.pos.curr_effect_index.map_or_else(
 179                 || Effect::Before.at_index(block_data.statements.len()),
 180                 EffectIndex::next_in_backward_order,
 181             )
 182         };
 183
 184         let analysis = &self.results.borrow().analysis;
 185         let target_effect_index = effect.at_index(target.statement_index);
 186
 187         A::Direction::apply_effects_in_range(
 188             analysis,
 189             &mut self.state,
 190             target.block,
 191             block_data,
 192             next_effect..=target_effect_index,
 193         );
 194
 195         self.pos =
 196             CursorPosition { block: target.block, curr_effect_index: Some(target_effect_index) };
 197     }
 198
 199     /// Applies `f` to the cursor's internal state.
 200     ///
 201     /// This can be used, e.g., to apply the call return effect directly to the cursor without
 202     /// creating an extra copy of the dataflow state.
 203     pub fn apply_custom_effect(&mut self, f: impl FnOnce(&A, &mut A::Domain)) {
 204         f(&self.results.borrow().analysis, &mut self.state);
 205         self.state_needs_reset = true;
 206     }
 207 }
 208
 209 impl<'mir, 'tcx, A, R, T> ResultsCursor<'mir, 'tcx, A, R>
 210 where
 211     A: Analysis<'tcx, Domain = BitSet<T>>,
 212     T: Idx,
 213     R: Borrow<Results<'tcx, A>>,
 214 {
 215     pub fn contains(&self, elem: T) -> bool {
 216         self.get().contains(elem)
 217     }
 218 }
 219
 220 #[derive(Clone, Copy, Debug)]
 221 struct CursorPosition {
 222     block: BasicBlock,
 223     curr_effect_index: Option<EffectIndex>,
 224 }
 225
 226 impl CursorPosition {
 227     fn block_entry(block: BasicBlock) -> CursorPosition {
 228         CursorPosition { block, curr_effect_index: None }
 229     }
 230 }