compiler/rustc_mir_dataflow/src/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     /// Returns the underlying `Results`.
  68     pub fn results(&self) -> &Results<'tcx, A> {
  69         &self.results.borrow()
  70     }
  71
  72     /// Returns the `Analysis` used to generate the underlying `Results`.
  73     pub fn analysis(&self) -> &A {
  74         &self.results.borrow().analysis
  75     }
  76
  77     /// Returns the dataflow state at the current location.
  78     pub fn get(&self) -> &A::Domain {
  79         &self.state
  80     }
  81
  82     /// Resets the cursor to hold the entry set for the given basic block.
  83     ///
  84     /// For forward dataflow analyses, this is the dataflow state prior to the first statement.
  85     ///
  86     /// For backward dataflow analyses, this is the dataflow state after the terminator.
  87     pub(super) fn seek_to_block_entry(&mut self, block: BasicBlock) {
  88         #[cfg(debug_assertions)]
  89         assert!(self.reachable_blocks.contains(block));
  90
  91         self.state.clone_from(&self.results.borrow().entry_set_for_block(block));
  92         self.pos = CursorPosition::block_entry(block);
  93         self.state_needs_reset = false;
  94     }
  95
  96     /// Resets the cursor to hold the state prior to the first statement in a basic block.
  97     ///
  98     /// For forward analyses, this is the entry set for the given block.
  99     ///
 100     /// For backward analyses, this is the state that will be propagated to its
 101     /// predecessors (ignoring edge-specific effects).
 102     pub fn seek_to_block_start(&mut self, block: BasicBlock) {
 103         if A::Direction::is_forward() {
 104             self.seek_to_block_entry(block)
 105         } else {
 106             self.seek_after(Location { block, statement_index: 0 }, Effect::Primary)
 107         }
 108     }
 109
 110     /// Resets the cursor to hold the state after the terminator in a basic block.
 111     ///
 112     /// For backward analyses, this is the entry set for the given block.
 113     ///
 114     /// For forward analyses, this is the state that will be propagated to its
 115     /// successors (ignoring edge-specific effects).
 116     pub fn seek_to_block_end(&mut self, block: BasicBlock) {
 117         if A::Direction::is_backward() {
 118             self.seek_to_block_entry(block)
 119         } else {
 120             self.seek_after(self.body.terminator_loc(block), Effect::Primary)
 121         }
 122     }
 123
 124     /// Advances the cursor to hold the dataflow state at `target` before its "primary" effect is
 125     /// applied.
 126     ///
 127     /// The "before" effect at the target location *will be* applied.
 128     pub fn seek_before_primary_effect(&mut self, target: Location) {
 129         self.seek_after(target, Effect::Before)
 130     }
 131
 132     /// Advances the cursor to hold the dataflow state at `target` after its "primary" effect is
 133     /// applied.
 134     ///
 135     /// The "before" effect at the target location will be applied as well.
 136     pub fn seek_after_primary_effect(&mut self, target: Location) {
 137         self.seek_after(target, Effect::Primary)
 138     }
 139
 140     fn seek_after(&mut self, target: Location, effect: Effect) {
 141         assert!(target <= self.body.terminator_loc(target.block));
 142
 143         // Reset to the entry of the target block if any of the following are true:
 144         //   - A custom effect has been applied to the cursor state.
 145         //   - We are in a different block than the target.
 146         //   - We are in the same block but have advanced past the target effect.
 147         if self.state_needs_reset || self.pos.block != target.block {
 148             self.seek_to_block_entry(target.block);
 149         } else if let Some(curr_effect) = self.pos.curr_effect_index {
 150             let mut ord = curr_effect.statement_index.cmp(&target.statement_index);
 151             if A::Direction::is_backward() {
 152                 ord = ord.reverse()
 153             }
 154
 155             match ord.then_with(|| curr_effect.effect.cmp(&effect)) {
 156                 Ordering::Equal => return,
 157                 Ordering::Greater => self.seek_to_block_entry(target.block),
 158                 Ordering::Less => {}
 159             }
 160         }
 161
 162         // At this point, the cursor is in the same block as the target location at an earlier
 163         // statement.
 164         debug_assert_eq!(target.block, self.pos.block);
 165
 166         let block_data = &self.body[target.block];
 167         let next_effect = if A::Direction::is_forward() {
 168             #[rustfmt::skip]
 169             self.pos.curr_effect_index.map_or_else(
 170                 || Effect::Before.at_index(0),
 171                 EffectIndex::next_in_forward_order,
 172             )
 173         } else {
 174             self.pos.curr_effect_index.map_or_else(
 175                 || Effect::Before.at_index(block_data.statements.len()),
 176                 EffectIndex::next_in_backward_order,
 177             )
 178         };
 179
 180         let analysis = &self.results.borrow().analysis;
 181         let target_effect_index = effect.at_index(target.statement_index);
 182
 183         A::Direction::apply_effects_in_range(
 184             analysis,
 185             &mut self.state,
 186             target.block,
 187             block_data,
 188             next_effect..=target_effect_index,
 189         );
 190
 191         self.pos =
 192             CursorPosition { block: target.block, curr_effect_index: Some(target_effect_index) };
 193     }
 194
 195     /// Applies `f` to the cursor's internal state.
 196     ///
 197     /// This can be used, e.g., to apply the call return effect directly to the cursor without
 198     /// creating an extra copy of the dataflow state.
 199     pub fn apply_custom_effect(&mut self, f: impl FnOnce(&A, &mut A::Domain)) {
 200         f(&self.results.borrow().analysis, &mut self.state);
 201         self.state_needs_reset = true;
 202     }
 203 }
 204
 205 impl<'mir, 'tcx, A, R, T> ResultsCursor<'mir, 'tcx, A, R>
 206 where
 207     A: Analysis<'tcx, Domain = BitSet<T>>,
 208     T: Idx,
 209     R: Borrow<Results<'tcx, A>>,
 210 {
 211     pub fn contains(&self, elem: T) -> bool {
 212         self.get().contains(elem)
 213     }
 214 }
 215
 216 #[derive(Clone, Copy, Debug)]
 217 struct CursorPosition {
 218     block: BasicBlock,
 219     curr_effect_index: Option<EffectIndex>,
 220 }
 221
 222 impl CursorPosition {
 223     fn block_entry(block: BasicBlock) -> CursorPosition {
 224         CursorPosition { block, curr_effect_index: None }
 225     }
 226 }