compiler/rustc_mir_dataflow/src/framework/cursor.rs

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