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