src/librustc_mir/dataflow/generic/cursor.rs

   1 //! Random access inspection of the results of a dataflow analysis.
   2
   3 use std::borrow::Borrow;
   4
   5 use rustc::mir::{self, BasicBlock, Location, TerminatorKind};
   6 use rustc_index::bit_set::BitSet;
   7
   8 use super::{Analysis, Results};
   9
  10 /// A `ResultsCursor` that borrows the underlying `Results`.
  11 pub type ResultsRefCursor<'a, 'mir, 'tcx, A> = ResultsCursor<'mir, 'tcx, A, &'a Results<'tcx, A>>;
  12
  13 /// Allows random access inspection of the results of a dataflow analysis.
  14 ///
  15 /// This cursor only has linear performance within a basic block when its statements are visited in
  16 /// order. In the worst case—when statements are visited in *reverse* order—performance will be
  17 /// quadratic in the number of statements in the block. The order in which basic blocks are
  18 /// inspected has no impact on performance.
  19 ///
  20 /// A `ResultsCursor` can either own (the default) or borrow the dataflow results it inspects. The
  21 /// type of ownership is determined by `R` (see `ResultsRefCursor` above).
  22 pub struct ResultsCursor<'mir, 'tcx, A, R = Results<'tcx, A>>
  23 where
  24     A: Analysis<'tcx>,
  25 {
  26     body: &'mir mir::Body<'tcx>,
  27     results: R,
  28     state: BitSet<A::Idx>,
  29
  30     pos: CursorPosition,
  31
  32     /// When this flag is set, the cursor is pointing at a `Call` or `Yield` terminator whose call
  33     /// return or resume effect has been applied to `state`.
  34     ///
  35     /// This flag helps to ensure that multiple calls to `seek_after_assume_success` with the
  36     /// same target will result in exactly one invocation of `apply_call_return_effect`. It is
  37     /// sufficient to clear this only in `seek_to_block_start`, since seeking away from a
  38     /// terminator will always require a cursor reset.
  39     success_effect_applied: bool,
  40 }
  41
  42 impl<'mir, 'tcx, A, R> ResultsCursor<'mir, 'tcx, A, R>
  43 where
  44     A: Analysis<'tcx>,
  45     R: Borrow<Results<'tcx, A>>,
  46 {
  47     /// Returns a new cursor for `results` that points to the start of the `START_BLOCK`.
  48     pub fn new(body: &'mir mir::Body<'tcx>, results: R) -> Self {
  49         ResultsCursor {
  50             body,
  51             pos: CursorPosition::BlockStart(mir::START_BLOCK),
  52             state: results.borrow().entry_sets[mir::START_BLOCK].clone(),
  53             success_effect_applied: false,
  54             results,
  55         }
  56     }
  57
  58     /// Returns the `Analysis` used to generate the underlying results.
  59     pub fn analysis(&self) -> &A {
  60         &self.results.borrow().analysis
  61     }
  62
  63     /// Returns the dataflow state at the current location.
  64     pub fn get(&self) -> &BitSet<A::Idx> {
  65         &self.state
  66     }
  67
  68     /// Returns `true` if the dataflow state at the current location contains the given element.
  69     ///
  70     /// Shorthand for `self.get().contains(elem)`
  71     pub fn contains(&self, elem: A::Idx) -> bool {
  72         self.state.contains(elem)
  73     }
  74
  75     /// Resets the cursor to the start of the given basic block.
  76     pub fn seek_to_block_start(&mut self, block: BasicBlock) {
  77         self.state.overwrite(&self.results.borrow().entry_sets[block]);
  78         self.pos = CursorPosition::BlockStart(block);
  79         self.success_effect_applied = false;
  80     }
  81
  82     /// Advances the cursor to hold all effects up to and including to the "before" effect of the
  83     /// statement (or terminator) at the given location.
  84     ///
  85     /// If you wish to observe the full effect of a statement or terminator, not just the "before"
  86     /// effect, use `seek_after` or `seek_after_assume_success`.
  87     pub fn seek_before(&mut self, target: Location) {
  88         assert!(target <= self.body.terminator_loc(target.block));
  89         self.seek_(target, false);
  90     }
  91
  92     /// Advances the cursor to hold the full effect of all statements (and possibly closing
  93     /// terminators) up to and including the `target`.
  94     ///
  95     /// If the `target` is a `Call` terminator, any call return effect for that terminator will
  96     /// **not** be observed. Use `seek_after_assume_success` if you wish to observe the call
  97     /// return effect.
  98     pub fn seek_after(&mut self, target: Location) {
  99         assert!(target <= self.body.terminator_loc(target.block));
 100
 101         // If we have already applied the call return effect, we are currently pointing at a `Call`
 102         // terminator. Unconditionally reset the dataflow cursor, since there is no way to "undo"
 103         // the call return effect.
 104         if self.success_effect_applied {
 105             self.seek_to_block_start(target.block);
 106         }
 107
 108         self.seek_(target, true);
 109     }
 110
 111     /// Advances the cursor to hold all effects up to and including of the statement (or
 112     /// terminator) at the given location.
 113     ///
 114     /// If the `target` is a `Call` or `Yield` terminator, any call return or resume effect for that
 115     /// terminator will be observed. Use `seek_after` if you do **not** wish to observe the
 116     /// "success" effect.
 117     pub fn seek_after_assume_success(&mut self, target: Location) {
 118         let terminator_loc = self.body.terminator_loc(target.block);
 119         assert!(target.statement_index <= terminator_loc.statement_index);
 120
 121         self.seek_(target, true);
 122
 123         if target != terminator_loc || self.success_effect_applied {
 124             return;
 125         }
 126
 127         // Apply the effect of the "success" path of the terminator.
 128
 129         self.success_effect_applied = true;
 130         let terminator = self.body.basic_blocks()[target.block].terminator();
 131         match &terminator.kind {
 132             TerminatorKind::Call { destination: Some((return_place, _)), func, args, .. } => {
 133                 self.results.borrow().analysis.apply_call_return_effect(
 134                     &mut self.state,
 135                     target.block,
 136                     func,
 137                     args,
 138                     return_place,
 139                 );
 140             }
 141             TerminatorKind::Yield { resume, resume_arg, .. } => {
 142                 self.results.borrow().analysis.apply_yield_resume_effect(
 143                     &mut self.state,
 144                     *resume,
 145                     resume_arg,
 146                 );
 147             }
 148             _ => {}
 149         }
 150     }
 151
 152     fn seek_(&mut self, target: Location, apply_after_effect_at_target: bool) {
 153         use CursorPosition::*;
 154
 155         match self.pos {
 156             // Return early if we are already at the target location.
 157             Before(curr) if curr == target && !apply_after_effect_at_target => return,
 158             After(curr) if curr == target && apply_after_effect_at_target => return,
 159
 160             // Otherwise, we must reset to the start of the target block if...
 161
 162             // we are in a different block entirely.
 163             BlockStart(block) | Before(Location { block, .. }) | After(Location { block, .. })
 164                 if block != target.block =>
 165             {
 166                 self.seek_to_block_start(target.block)
 167             }
 168
 169             // we are in the same block but have advanced past the target statement.
 170             Before(curr) | After(curr) if curr.statement_index > target.statement_index => {
 171                 self.seek_to_block_start(target.block)
 172             }
 173
 174             // we have already applied the entire effect of a statement but only wish to observe
 175             // its "before" effect.
 176             After(curr)
 177                 if curr.statement_index == target.statement_index
 178                     && !apply_after_effect_at_target =>
 179             {
 180                 self.seek_to_block_start(target.block)
 181             }
 182
 183             // N.B., `success_effect_applied` is checked in `seek_after`, not here.
 184             _ => (),
 185         }
 186
 187         let analysis = &self.results.borrow().analysis;
 188         let block_data = &self.body.basic_blocks()[target.block];
 189
 190         // At this point, the cursor is in the same block as the target location at an earlier
 191         // statement.
 192         debug_assert_eq!(target.block, self.pos.block());
 193
 194         // Find the first statement whose transfer function has not yet been applied.
 195         let first_unapplied_statement = match self.pos {
 196             BlockStart(_) => 0,
 197             After(Location { statement_index, .. }) => statement_index + 1,
 198
 199             // If we have only applied the "before" effect for the current statement, apply the
 200             // remainder before continuing.
 201             Before(curr) => {
 202                 if curr.statement_index == block_data.statements.len() {
 203                     let terminator = block_data.terminator();
 204                     analysis.apply_terminator_effect(&mut self.state, terminator, curr);
 205                 } else {
 206                     let statement = &block_data.statements[curr.statement_index];
 207                     analysis.apply_statement_effect(&mut self.state, statement, curr);
 208                 }
 209
 210                 // If all we needed to do was go from `Before` to `After` in the same statement,
 211                 // we are now done.
 212                 if curr.statement_index == target.statement_index {
 213                     debug_assert!(apply_after_effect_at_target);
 214                     self.pos = After(target);
 215                     return;
 216                 }
 217
 218                 curr.statement_index + 1
 219             }
 220         };
 221
 222         // We have now applied all effects prior to `first_unapplied_statement`.
 223
 224         // Apply the effects of all statements before `target`.
 225         let mut location = Location { block: target.block, statement_index: 0 };
 226         for statement_index in first_unapplied_statement..target.statement_index {
 227             location.statement_index = statement_index;
 228             let statement = &block_data.statements[statement_index];
 229             analysis.apply_before_statement_effect(&mut self.state, statement, location);
 230             analysis.apply_statement_effect(&mut self.state, statement, location);
 231         }
 232
 233         // Apply the effect of the statement (or terminator) at `target`.
 234         location.statement_index = target.statement_index;
 235         if target.statement_index == block_data.statements.len() {
 236             let terminator = &block_data.terminator();
 237             analysis.apply_before_terminator_effect(&mut self.state, terminator, location);
 238
 239             if apply_after_effect_at_target {
 240                 analysis.apply_terminator_effect(&mut self.state, terminator, location);
 241                 self.pos = After(target);
 242             } else {
 243                 self.pos = Before(target);
 244             }
 245         } else {
 246             let statement = &block_data.statements[target.statement_index];
 247             analysis.apply_before_statement_effect(&mut self.state, statement, location);
 248
 249             if apply_after_effect_at_target {
 250                 analysis.apply_statement_effect(&mut self.state, statement, location);
 251                 self.pos = After(target)
 252             } else {
 253                 self.pos = Before(target);
 254             }
 255         }
 256     }
 257 }
 258
 259 #[derive(Clone, Copy, Debug)]
 260 enum CursorPosition {
 261     /// No effects within this block have been applied.
 262     BlockStart(BasicBlock),
 263
 264     /// Only the "before" effect of the statement (or terminator) at this location has been
 265     /// applied (along with the effects of all previous statements).
 266     Before(Location),
 267
 268     /// The effects of all statements up to and including the one at this location have been
 269     /// applied.
 270     After(Location),
 271 }
 272
 273 impl CursorPosition {
 274     fn block(&self) -> BasicBlock {
 275         match *self {
 276             Self::BlockStart(block) => block,
 277             Self::Before(loc) | Self::After(loc) => loc.block,
 278         }
 279     }
 280 }