]>
Commit | Line | Data |
---|---|---|
dfeec247 XL |
1 | //! A test for the logic that updates the state in a `ResultsCursor` during seek. |
2 | ||
f9f354fc XL |
3 | use std::marker::PhantomData; |
4 | ||
dfeec247 XL |
5 | use rustc_index::bit_set::BitSet; |
6 | use rustc_index::vec::IndexVec; | |
ba9703b0 XL |
7 | use rustc_middle::mir::{self, BasicBlock, Location}; |
8 | use rustc_middle::ty; | |
dfeec247 XL |
9 | use rustc_span::DUMMY_SP; |
10 | ||
11 | use super::*; | |
12 | use 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. | |
18 | fn 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 | 84 | struct MockAnalysis<'tcx, D> { |
dfeec247 | 85 | body: &'tcx mir::Body<'tcx>, |
f9f354fc | 86 | dir: PhantomData<D>, |
dfeec247 XL |
87 | } |
88 | ||
f9f354fc | 89 | impl<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 | 164 | impl<D: Direction> BottomValue for MockAnalysis<'tcx, D> { |
dfeec247 XL |
165 | const BOTTOM_VALUE: bool = false; |
166 | } | |
167 | ||
f9f354fc | 168 | impl<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 | 183 | impl<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)] | |
236 | enum SeekTarget { | |
f9f354fc | 237 | BlockEntry(BasicBlock), |
dfeec247 XL |
238 | Before(Location), |
239 | After(Location), | |
dfeec247 XL |
240 | } |
241 | ||
242 | impl 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 |
270 | fn 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] | |
312 | fn 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] | |
320 | fn forward_cursor() { | |
321 | let body = mock_body(); | |
322 | let body = &body; | |
323 | let analysis = MockAnalysis { body, dir: PhantomData::<Forward> }; | |
324 | test_cursor(analysis) | |
325 | } |