src/librustc_mir/dataflow/framework/tests.rs

   1 //! A test for the logic that updates the state in a `ResultsCursor` during seek.
   2
   3 use rustc_index::bit_set::BitSet;
   4 use rustc_index::vec::IndexVec;
   5 use rustc_middle::mir::{self, BasicBlock, Location};
   6 use rustc_middle::ty;
   7 use rustc_span::DUMMY_SP;
   8
   9 use super::*;
  10 use crate::dataflow::BottomValue;
  11
  12 /// Returns `true` if the given location points to a `Call` terminator that can return
  13 /// successfully.
  14 fn is_call_terminator_non_diverging(body: &mir::Body<'_>, loc: Location) -> bool {
  15     loc == body.terminator_loc(loc.block)
  16         && matches!(
  17             body[loc.block].terminator().kind,
  18             mir::TerminatorKind::Call { destination: Some(_), ..  }
  19         )
  20 }
  21
  22 /// Creates a `mir::Body` with a few disconnected basic blocks.
  23 ///
  24 /// This is the `Body` that will be used by the `MockAnalysis` below. The shape of its CFG is not
  25 /// important.
  26 fn mock_body() -> mir::Body<'static> {
  27     let source_info = mir::SourceInfo { scope: mir::OUTERMOST_SOURCE_SCOPE, span: DUMMY_SP };
  28
  29     let mut blocks = IndexVec::new();
  30     let mut block = |n, kind| {
  31         let nop = mir::Statement { source_info, kind: mir::StatementKind::Nop };
  32
  33         blocks.push(mir::BasicBlockData {
  34             statements: std::iter::repeat(&nop).cloned().take(n).collect(),
  35             terminator: Some(mir::Terminator { source_info, kind }),
  36             is_cleanup: false,
  37         })
  38     };
  39
  40     let dummy_place = mir::Place { local: mir::RETURN_PLACE, projection: ty::List::empty() };
  41
  42     block(4, mir::TerminatorKind::Return);
  43     block(1, mir::TerminatorKind::Return);
  44     block(
  45         2,
  46         mir::TerminatorKind::Call {
  47             func: mir::Operand::Copy(dummy_place.clone()),
  48             args: vec![],
  49             destination: Some((dummy_place.clone(), mir::START_BLOCK)),
  50             cleanup: None,
  51             from_hir_call: false,
  52         },
  53     );
  54     block(3, mir::TerminatorKind::Return);
  55     block(0, mir::TerminatorKind::Return);
  56     block(
  57         4,
  58         mir::TerminatorKind::Call {
  59             func: mir::Operand::Copy(dummy_place.clone()),
  60             args: vec![],
  61             destination: Some((dummy_place.clone(), mir::START_BLOCK)),
  62             cleanup: None,
  63             from_hir_call: false,
  64         },
  65     );
  66
  67     mir::Body::new_cfg_only(blocks)
  68 }
  69
  70 /// A dataflow analysis whose state is unique at every possible `SeekTarget`.
  71 ///
  72 /// Uniqueness is achieved by having a *locally* unique effect before and after each statement and
  73 /// terminator (see `effect_at_target`) while ensuring that the entry set for each block is
  74 /// *globally* unique (see `mock_entry_set`).
  75 ///
  76 /// For example, a `BasicBlock` with ID `2` and a `Call` terminator has the following state at each
  77 /// location ("+x" indicates that "x" is added to the state).
  78 ///
  79 /// | Location               | Before            | After  |
  80 /// |------------------------|-------------------|--------|
  81 /// | (on_entry)             | {102}                     ||
  82 /// | Statement 0            | +0                | +1     |
  83 /// | statement 1            | +2                | +3     |
  84 /// | `Call` terminator      | +4                | +5     |
  85 /// | (on unwind)            | {102,0,1,2,3,4,5}         ||
  86 /// | (on successful return) | +6                        ||
  87 ///
  88 /// The `102` in the block's entry set is derived from the basic block index and ensures that the
  89 /// expected state is unique across all basic blocks. Remember, it is generated by
  90 /// `mock_entry_sets`, not from actually running `MockAnalysis` to fixpoint.
  91 struct MockAnalysis<'tcx> {
  92     body: &'tcx mir::Body<'tcx>,
  93 }
  94
  95 impl MockAnalysis<'tcx> {
  96     const BASIC_BLOCK_OFFSET: usize = 100;
  97
  98     /// The entry set for each `BasicBlock` is the ID of that block offset by a fixed amount to
  99     /// avoid colliding with the statement/terminator effects.
 100     fn mock_entry_set(&self, bb: BasicBlock) -> BitSet<usize> {
 101         let mut ret = BitSet::new_empty(self.bits_per_block(self.body));
 102         ret.insert(Self::BASIC_BLOCK_OFFSET + bb.index());
 103         ret
 104     }
 105
 106     fn mock_entry_sets(&self) -> IndexVec<BasicBlock, BitSet<usize>> {
 107         let empty = BitSet::new_empty(self.bits_per_block(self.body));
 108         let mut ret = IndexVec::from_elem(empty, &self.body.basic_blocks());
 109
 110         for (bb, _) in self.body.basic_blocks().iter_enumerated() {
 111             ret[bb] = self.mock_entry_set(bb);
 112         }
 113
 114         ret
 115     }
 116
 117     /// Returns the index that should be added to the dataflow state at the given target.
 118     ///
 119     /// This index is only unique within a given basic block. `SeekAfter` and
 120     /// `SeekAfterAssumeCallReturns` have the same effect unless `target` is a `Call` terminator.
 121     fn effect_at_target(&self, target: SeekTarget) -> Option<usize> {
 122         use SeekTarget::*;
 123
 124         let idx = match target {
 125             BlockStart(_) => return None,
 126
 127             AfterAssumeCallReturns(loc) if is_call_terminator_non_diverging(self.body, loc) => {
 128                 loc.statement_index * 2 + 2
 129             }
 130
 131             Before(loc) => loc.statement_index * 2,
 132             After(loc) | AfterAssumeCallReturns(loc) => loc.statement_index * 2 + 1,
 133         };
 134
 135         assert!(idx < Self::BASIC_BLOCK_OFFSET, "Too many statements in basic block");
 136         Some(idx)
 137     }
 138
 139     /// Returns the expected state at the given `SeekTarget`.
 140     ///
 141     /// This is the union of index of the target basic block, the index assigned to the
 142     /// target statement or terminator, and the indices of all preceding statements in the target
 143     /// basic block.
 144     ///
 145     /// For example, the expected state when calling
 146     /// `seek_before(Location { block: 2, statement_index: 2 })` would be `[102, 0, 1, 2, 3, 4]`.
 147     fn expected_state_at_target(&self, target: SeekTarget) -> BitSet<usize> {
 148         let mut ret = BitSet::new_empty(self.bits_per_block(self.body));
 149         ret.insert(Self::BASIC_BLOCK_OFFSET + target.block().index());
 150
 151         if let Some(target_effect) = self.effect_at_target(target) {
 152             for i in 0..=target_effect {
 153                 ret.insert(i);
 154             }
 155         }
 156
 157         ret
 158     }
 159 }
 160
 161 impl BottomValue for MockAnalysis<'tcx> {
 162     const BOTTOM_VALUE: bool = false;
 163 }
 164
 165 impl AnalysisDomain<'tcx> for MockAnalysis<'tcx> {
 166     type Idx = usize;
 167
 168     const NAME: &'static str = "mock";
 169
 170     fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize {
 171         Self::BASIC_BLOCK_OFFSET + body.basic_blocks().len()
 172     }
 173
 174     fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut BitSet<Self::Idx>) {
 175         unimplemented!("This is never called since `MockAnalysis` is never iterated to fixpoint");
 176     }
 177 }
 178
 179 impl Analysis<'tcx> for MockAnalysis<'tcx> {
 180     fn apply_statement_effect(
 181         &self,
 182         state: &mut BitSet<Self::Idx>,
 183         _statement: &mir::Statement<'tcx>,
 184         location: Location,
 185     ) {
 186         let idx = self.effect_at_target(SeekTarget::After(location)).unwrap();
 187         assert!(state.insert(idx));
 188     }
 189
 190     fn apply_before_statement_effect(
 191         &self,
 192         state: &mut BitSet<Self::Idx>,
 193         _statement: &mir::Statement<'tcx>,
 194         location: Location,
 195     ) {
 196         let idx = self.effect_at_target(SeekTarget::Before(location)).unwrap();
 197         assert!(state.insert(idx));
 198     }
 199
 200     fn apply_terminator_effect(
 201         &self,
 202         state: &mut BitSet<Self::Idx>,
 203         _terminator: &mir::Terminator<'tcx>,
 204         location: Location,
 205     ) {
 206         let idx = self.effect_at_target(SeekTarget::After(location)).unwrap();
 207         assert!(state.insert(idx));
 208     }
 209
 210     fn apply_before_terminator_effect(
 211         &self,
 212         state: &mut BitSet<Self::Idx>,
 213         _terminator: &mir::Terminator<'tcx>,
 214         location: Location,
 215     ) {
 216         let idx = self.effect_at_target(SeekTarget::Before(location)).unwrap();
 217         assert!(state.insert(idx));
 218     }
 219
 220     fn apply_call_return_effect(
 221         &self,
 222         state: &mut BitSet<Self::Idx>,
 223         block: BasicBlock,
 224         _func: &mir::Operand<'tcx>,
 225         _args: &[mir::Operand<'tcx>],
 226         _return_place: mir::Place<'tcx>,
 227     ) {
 228         let location = self.body.terminator_loc(block);
 229         let idx = self.effect_at_target(SeekTarget::AfterAssumeCallReturns(location)).unwrap();
 230         assert!(state.insert(idx));
 231     }
 232 }
 233
 234 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
 235 enum SeekTarget {
 236     BlockStart(BasicBlock),
 237     Before(Location),
 238     After(Location),
 239     AfterAssumeCallReturns(Location),
 240 }
 241
 242 impl SeekTarget {
 243     fn block(&self) -> BasicBlock {
 244         use SeekTarget::*;
 245
 246         match *self {
 247             BlockStart(block) => block,
 248             Before(loc) | After(loc) | AfterAssumeCallReturns(loc) => loc.block,
 249         }
 250     }
 251
 252     /// An iterator over all possible `SeekTarget`s in a given block in order, starting with
 253     /// `BlockStart`.
 254     ///
 255     /// This includes both `After` and `AfterAssumeCallReturns` for every `Location`.
 256     fn iter_in_block(body: &mir::Body<'_>, block: BasicBlock) -> impl Iterator<Item = Self> {
 257         let statements_and_terminator = (0..=body[block].statements.len())
 258             .flat_map(|i| (0..3).map(move |j| (i, j)))
 259             .map(move |(i, kind)| {
 260                 let loc = Location { block, statement_index: i };
 261                 match kind {
 262                     0 => SeekTarget::Before(loc),
 263                     1 => SeekTarget::After(loc),
 264                     2 => SeekTarget::AfterAssumeCallReturns(loc),
 265                     _ => unreachable!(),
 266                 }
 267             });
 268
 269         std::iter::once(SeekTarget::BlockStart(block)).chain(statements_and_terminator)
 270     }
 271 }
 272
 273 #[test]
 274 fn cursor_seek() {
 275     let body = mock_body();
 276     let body = &body;
 277     let analysis = MockAnalysis { body };
 278
 279     let mut cursor =
 280         Results { entry_sets: analysis.mock_entry_sets(), analysis }.into_results_cursor(body);
 281
 282     // Sanity check: the mock call return effect is unique and actually being applied.
 283     let call_terminator_loc = Location { block: BasicBlock::from_usize(2), statement_index: 2 };
 284     assert!(is_call_terminator_non_diverging(body, call_terminator_loc));
 285
 286     let call_return_effect = cursor
 287         .analysis()
 288         .effect_at_target(SeekTarget::AfterAssumeCallReturns(call_terminator_loc))
 289         .unwrap();
 290     assert_ne!(
 291         call_return_effect,
 292         cursor.analysis().effect_at_target(SeekTarget::After(call_terminator_loc)).unwrap()
 293     );
 294
 295     cursor.seek_after(call_terminator_loc);
 296     assert!(!cursor.get().contains(call_return_effect));
 297     cursor.seek_after_assume_success(call_terminator_loc);
 298     assert!(cursor.get().contains(call_return_effect));
 299
 300     let every_target = || {
 301         body.basic_blocks()
 302             .iter_enumerated()
 303             .flat_map(|(bb, _)| SeekTarget::iter_in_block(body, bb))
 304     };
 305
 306     let mut seek_to_target = |targ| {
 307         use SeekTarget::*;
 308
 309         match targ {
 310             BlockStart(block) => cursor.seek_to_block_start(block),
 311             Before(loc) => cursor.seek_before(loc),
 312             After(loc) => cursor.seek_after(loc),
 313             AfterAssumeCallReturns(loc) => cursor.seek_after_assume_success(loc),
 314         }
 315
 316         assert_eq!(cursor.get(), &cursor.analysis().expected_state_at_target(targ));
 317     };
 318
 319     // Seek *to* every possible `SeekTarget` *from* every possible `SeekTarget`.
 320     //
 321     // By resetting the cursor to `from` each time it changes, we end up checking some edges twice.
 322     // What we really want is an Eulerian cycle for the complete digraph over all possible
 323     // `SeekTarget`s, but it's not worth spending the time to compute it.
 324     for from in every_target() {
 325         seek_to_target(from);
 326
 327         for to in every_target() {
 328             seek_to_target(to);
 329             seek_to_target(from);
 330         }
 331     }
 332 }