1 //! Random access inspection of the results of a dataflow analysis.
3 use std::borrow::Borrow;
5 use rustc::mir::{self, BasicBlock, Location, TerminatorKind};
6 use rustc_index::bit_set::BitSet;
8 use super::{Analysis, Results};
10 /// A `ResultsCursor` that borrows the underlying `Results`.
11 pub type ResultsRefCursor<'a, 'mir, 'tcx, A> = ResultsCursor<'mir, 'tcx, A, &'a Results<'tcx, A>>;
13 /// Allows random access inspection of the results of a dataflow analysis.
15 /// This cursor only has linear performance within a basic block when its statements are visited in
16 /// order. In the worst case—when statements are visited in *reverse* order—performance will be
17 /// quadratic in the number of statements in the block. The order in which basic blocks are
18 /// inspected has no impact on performance.
20 /// A `ResultsCursor` can either own (the default) or borrow the dataflow results it inspects. The
21 /// type of ownership is determined by `R` (see `ResultsRefCursor` above).
22 pub struct ResultsCursor<'mir, 'tcx, A, R = Results<'tcx, A>>
26 body: &'mir mir::Body<'tcx>,
28 state: BitSet<A::Idx>,
32 /// When this flag is set, the cursor is pointing at a `Call` or `Yield` terminator whose call
33 /// return or resume effect has been applied to `state`.
35 /// This flag helps to ensure that multiple calls to `seek_after_assume_success` with the
36 /// same target will result in exactly one invocation of `apply_call_return_effect`. It is
37 /// sufficient to clear this only in `seek_to_block_start`, since seeking away from a
38 /// terminator will always require a cursor reset.
39 success_effect_applied: bool,
42 impl<'mir, 'tcx, A, R> ResultsCursor<'mir, 'tcx, A, R>
45 R: Borrow<Results<'tcx, A>>,
47 /// Returns a new cursor for `results` that points to the start of the `START_BLOCK`.
48 pub fn new(body: &'mir mir::Body<'tcx>, results: R) -> Self {
51 pos: CursorPosition::BlockStart(mir::START_BLOCK),
52 state: results.borrow().entry_sets[mir::START_BLOCK].clone(),
53 success_effect_applied: false,
58 /// Returns the `Analysis` used to generate the underlying results.
59 pub fn analysis(&self) -> &A {
60 &self.results.borrow().analysis
63 /// Returns the dataflow state at the current location.
64 pub fn get(&self) -> &BitSet<A::Idx> {
68 /// Returns `true` if the dataflow state at the current location contains the given element.
70 /// Shorthand for `self.get().contains(elem)`
71 pub fn contains(&self, elem: A::Idx) -> bool {
72 self.state.contains(elem)
75 /// Resets the cursor to the start of the given basic block.
76 pub fn seek_to_block_start(&mut self, block: BasicBlock) {
77 self.state.overwrite(&self.results.borrow().entry_sets[block]);
78 self.pos = CursorPosition::BlockStart(block);
79 self.success_effect_applied = false;
82 /// Advances the cursor to hold all effects up to and including to the "before" effect of the
83 /// statement (or terminator) at the given location.
85 /// If you wish to observe the full effect of a statement or terminator, not just the "before"
86 /// effect, use `seek_after` or `seek_after_assume_success`.
87 pub fn seek_before(&mut self, target: Location) {
88 assert!(target <= self.body.terminator_loc(target.block));
89 self.seek_(target, false);
92 /// Advances the cursor to hold the full effect of all statements (and possibly closing
93 /// terminators) up to and including the `target`.
95 /// If the `target` is a `Call` terminator, any call return effect for that terminator will
96 /// **not** be observed. Use `seek_after_assume_success` if you wish to observe the call
98 pub fn seek_after(&mut self, target: Location) {
99 assert!(target <= self.body.terminator_loc(target.block));
101 // If we have already applied the call return effect, we are currently pointing at a `Call`
102 // terminator. Unconditionally reset the dataflow cursor, since there is no way to "undo"
103 // the call return effect.
104 if self.success_effect_applied {
105 self.seek_to_block_start(target.block);
108 self.seek_(target, true);
111 /// Advances the cursor to hold all effects up to and including of the statement (or
112 /// terminator) at the given location.
114 /// If the `target` is a `Call` or `Yield` terminator, any call return or resume effect for that
115 /// terminator will be observed. Use `seek_after` if you do **not** wish to observe the
116 /// "success" effect.
117 pub fn seek_after_assume_success(&mut self, target: Location) {
118 let terminator_loc = self.body.terminator_loc(target.block);
119 assert!(target.statement_index <= terminator_loc.statement_index);
121 self.seek_(target, true);
123 if target != terminator_loc || self.success_effect_applied {
127 // Apply the effect of the "success" path of the terminator.
129 self.success_effect_applied = true;
130 let terminator = self.body.basic_blocks()[target.block].terminator();
131 match &terminator.kind {
132 TerminatorKind::Call { destination: Some((return_place, _)), func, args, .. } => {
133 self.results.borrow().analysis.apply_call_return_effect(
141 TerminatorKind::Yield { resume, resume_arg, .. } => {
142 self.results.borrow().analysis.apply_yield_resume_effect(
152 fn seek_(&mut self, target: Location, apply_after_effect_at_target: bool) {
153 use CursorPosition::*;
156 // Return early if we are already at the target location.
157 Before(curr) if curr == target && !apply_after_effect_at_target => return,
158 After(curr) if curr == target && apply_after_effect_at_target => return,
160 // Otherwise, we must reset to the start of the target block if...
162 // we are in a different block entirely.
163 BlockStart(block) | Before(Location { block, .. }) | After(Location { block, .. })
164 if block != target.block =>
166 self.seek_to_block_start(target.block)
169 // we are in the same block but have advanced past the target statement.
170 Before(curr) | After(curr) if curr.statement_index > target.statement_index => {
171 self.seek_to_block_start(target.block)
174 // we have already applied the entire effect of a statement but only wish to observe
175 // its "before" effect.
177 if curr.statement_index == target.statement_index
178 && !apply_after_effect_at_target =>
180 self.seek_to_block_start(target.block)
183 // N.B., `success_effect_applied` is checked in `seek_after`, not here.
187 let analysis = &self.results.borrow().analysis;
188 let block_data = &self.body.basic_blocks()[target.block];
190 // At this point, the cursor is in the same block as the target location at an earlier
192 debug_assert_eq!(target.block, self.pos.block());
194 // Find the first statement whose transfer function has not yet been applied.
195 let first_unapplied_statement = match self.pos {
197 After(Location { statement_index, .. }) => statement_index + 1,
199 // If we have only applied the "before" effect for the current statement, apply the
200 // remainder before continuing.
202 if curr.statement_index == block_data.statements.len() {
203 let terminator = block_data.terminator();
204 analysis.apply_terminator_effect(&mut self.state, terminator, curr);
206 let statement = &block_data.statements[curr.statement_index];
207 analysis.apply_statement_effect(&mut self.state, statement, curr);
210 // If all we needed to do was go from `Before` to `After` in the same statement,
212 if curr.statement_index == target.statement_index {
213 debug_assert!(apply_after_effect_at_target);
214 self.pos = After(target);
218 curr.statement_index + 1
222 // We have now applied all effects prior to `first_unapplied_statement`.
224 // Apply the effects of all statements before `target`.
225 let mut location = Location { block: target.block, statement_index: 0 };
226 for statement_index in first_unapplied_statement..target.statement_index {
227 location.statement_index = statement_index;
228 let statement = &block_data.statements[statement_index];
229 analysis.apply_before_statement_effect(&mut self.state, statement, location);
230 analysis.apply_statement_effect(&mut self.state, statement, location);
233 // Apply the effect of the statement (or terminator) at `target`.
234 location.statement_index = target.statement_index;
235 if target.statement_index == block_data.statements.len() {
236 let terminator = &block_data.terminator();
237 analysis.apply_before_terminator_effect(&mut self.state, terminator, location);
239 if apply_after_effect_at_target {
240 analysis.apply_terminator_effect(&mut self.state, terminator, location);
241 self.pos = After(target);
243 self.pos = Before(target);
246 let statement = &block_data.statements[target.statement_index];
247 analysis.apply_before_statement_effect(&mut self.state, statement, location);
249 if apply_after_effect_at_target {
250 analysis.apply_statement_effect(&mut self.state, statement, location);
251 self.pos = After(target)
253 self.pos = Before(target);
259 #[derive(Clone, Copy, Debug)]
260 enum CursorPosition {
261 /// No effects within this block have been applied.
262 BlockStart(BasicBlock),
264 /// Only the "before" effect of the statement (or terminator) at this location has been
265 /// applied (along with the effects of all previous statements).
268 /// The effects of all statements up to and including the one at this location have been
273 impl CursorPosition {
274 fn block(&self) -> BasicBlock {
276 Self::BlockStart(block) => block,
277 Self::Before(loc) | Self::After(loc) => loc.block,