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