1 //! Random access inspection of the results of a dataflow analysis.
3 use crate::framework::BitSetExt;
5 use std::borrow::Borrow;
6 use std::cmp::Ordering;
8 #[cfg(debug_assertions)]
9 use rustc_index::bit_set::BitSet;
10 use rustc_middle::mir::{self, BasicBlock, Location};
12 use super::{Analysis, Direction, Effect, EffectIndex, Results};
14 /// A `ResultsCursor` that borrows the underlying `Results`.
15 pub type ResultsRefCursor<'a, 'mir, 'tcx, A> = ResultsCursor<'mir, 'tcx, A, &'a Results<'tcx, A>>;
17 /// Allows random access inspection of the results of a dataflow analysis.
19 /// This cursor only has linear performance within a basic block when its statements are visited in
20 /// the same order as the `DIRECTION` of the analysis. In the worst case—when statements are
21 /// visited in *reverse* order—performance will be quadratic in the number of statements in the
22 /// block. The order in which basic blocks are inspected has no impact on performance.
24 /// A `ResultsCursor` can either own (the default) or borrow the dataflow results it inspects. The
25 /// type of ownership is determined by `R` (see `ResultsRefCursor` above).
26 pub struct ResultsCursor<'mir, 'tcx, A, R = Results<'tcx, A>>
30 body: &'mir mir::Body<'tcx>,
36 /// Indicates that `state` has been modified with a custom effect.
38 /// When this flag is set, we need to reset to an entry set before doing a seek.
39 state_needs_reset: bool,
41 #[cfg(debug_assertions)]
42 reachable_blocks: BitSet<BasicBlock>,
45 impl<'mir, 'tcx, A, R> ResultsCursor<'mir, 'tcx, A, R>
48 R: Borrow<Results<'tcx, A>>,
50 /// Returns a new cursor that can inspect `results`.
51 pub fn new(body: &'mir mir::Body<'tcx>, results: R) -> Self {
52 let bottom_value = results.borrow().analysis.bottom_value(body);
57 // Initialize to the `bottom_value` and set `state_needs_reset` to tell the cursor that
58 // it needs to reset to block entry before the first seek. The cursor position is
60 state_needs_reset: true,
62 pos: CursorPosition::block_entry(mir::START_BLOCK),
64 #[cfg(debug_assertions)]
65 reachable_blocks: mir::traversal::reachable_as_bitset(body),
69 /// Allows inspection of unreachable basic blocks even with `debug_assertions` enabled.
71 pub(crate) fn allow_unreachable(&mut self) {
72 #[cfg(debug_assertions)]
73 self.reachable_blocks.insert_all()
76 /// Returns the underlying `Results`.
77 pub fn results(&self) -> &Results<'tcx, A> {
78 &self.results.borrow()
81 /// Returns the `Analysis` used to generate the underlying `Results`.
82 pub fn analysis(&self) -> &A {
83 &self.results.borrow().analysis
86 /// Returns the dataflow state at the current location.
87 pub fn get(&self) -> &A::Domain {
91 /// Resets the cursor to hold the entry set for the given basic block.
93 /// For forward dataflow analyses, this is the dataflow state prior to the first statement.
95 /// For backward dataflow analyses, this is the dataflow state after the terminator.
96 pub(super) fn seek_to_block_entry(&mut self, block: BasicBlock) {
97 #[cfg(debug_assertions)]
98 assert!(self.reachable_blocks.contains(block));
100 self.state.clone_from(&self.results.borrow().entry_set_for_block(block));
101 self.pos = CursorPosition::block_entry(block);
102 self.state_needs_reset = false;
105 /// Resets the cursor to hold the state prior to the first statement in a basic block.
107 /// For forward analyses, this is the entry set for the given block.
109 /// For backward analyses, this is the state that will be propagated to its
110 /// predecessors (ignoring edge-specific effects).
111 pub fn seek_to_block_start(&mut self, block: BasicBlock) {
112 if A::Direction::IS_FORWARD {
113 self.seek_to_block_entry(block)
115 self.seek_after(Location { block, statement_index: 0 }, Effect::Primary)
119 /// Resets the cursor to hold the state after the terminator in a basic block.
121 /// For backward analyses, this is the entry set for the given block.
123 /// For forward analyses, this is the state that will be propagated to its
124 /// successors (ignoring edge-specific effects).
125 pub fn seek_to_block_end(&mut self, block: BasicBlock) {
126 if A::Direction::IS_BACKWARD {
127 self.seek_to_block_entry(block)
129 self.seek_after(self.body.terminator_loc(block), Effect::Primary)
133 /// Advances the cursor to hold the dataflow state at `target` before its "primary" effect is
136 /// The "before" effect at the target location *will be* applied.
137 pub fn seek_before_primary_effect(&mut self, target: Location) {
138 self.seek_after(target, Effect::Before)
141 /// Advances the cursor to hold the dataflow state at `target` after its "primary" effect is
144 /// The "before" effect at the target location will be applied as well.
145 pub fn seek_after_primary_effect(&mut self, target: Location) {
146 self.seek_after(target, Effect::Primary)
149 fn seek_after(&mut self, target: Location, effect: Effect) {
150 assert!(target <= self.body.terminator_loc(target.block));
152 // Reset to the entry of the target block if any of the following are true:
153 // - A custom effect has been applied to the cursor state.
154 // - We are in a different block than the target.
155 // - We are in the same block but have advanced past the target effect.
156 if self.state_needs_reset || self.pos.block != target.block {
157 self.seek_to_block_entry(target.block);
158 } else if let Some(curr_effect) = self.pos.curr_effect_index {
159 let mut ord = curr_effect.statement_index.cmp(&target.statement_index);
160 if A::Direction::IS_BACKWARD {
164 match ord.then_with(|| curr_effect.effect.cmp(&effect)) {
165 Ordering::Equal => return,
166 Ordering::Greater => self.seek_to_block_entry(target.block),
171 // At this point, the cursor is in the same block as the target location at an earlier
173 debug_assert_eq!(target.block, self.pos.block);
175 let block_data = &self.body[target.block];
176 let next_effect = if A::Direction::IS_FORWARD {
178 self.pos.curr_effect_index.map_or_else(
179 || Effect::Before.at_index(0),
180 EffectIndex::next_in_forward_order,
183 self.pos.curr_effect_index.map_or_else(
184 || Effect::Before.at_index(block_data.statements.len()),
185 EffectIndex::next_in_backward_order,
189 let analysis = &self.results.borrow().analysis;
190 let target_effect_index = effect.at_index(target.statement_index);
192 A::Direction::apply_effects_in_range(
197 next_effect..=target_effect_index,
201 CursorPosition { block: target.block, curr_effect_index: Some(target_effect_index) };
204 /// Applies `f` to the cursor's internal state.
206 /// This can be used, e.g., to apply the call return effect directly to the cursor without
207 /// creating an extra copy of the dataflow state.
208 pub fn apply_custom_effect(&mut self, f: impl FnOnce(&A, &mut A::Domain)) {
209 f(&self.results.borrow().analysis, &mut self.state);
210 self.state_needs_reset = true;
214 impl<'mir, 'tcx, A, R> ResultsCursor<'mir, 'tcx, A, R>
216 A: crate::GenKillAnalysis<'tcx>,
217 A::Domain: BitSetExt<A::Idx>,
218 R: Borrow<Results<'tcx, A>>,
220 pub fn contains(&self, elem: A::Idx) -> bool {
221 self.get().contains(elem)
225 #[derive(Clone, Copy, Debug)]
226 struct CursorPosition {
228 curr_effect_index: Option<EffectIndex>,
231 impl CursorPosition {
232 fn block_entry(block: BasicBlock) -> CursorPosition {
233 CursorPosition { block, curr_effect_index: None }