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