1 //! Random access inspection of the results of a dataflow analysis. 2 3 use std::borrow::Borrow; 4 use std::cmp::Ordering; 5 6 use rustc_index::bit_set::BitSet; 7 use rustc_index::vec::Idx; 8 use rustc_middle::mir::{self, BasicBlock, Location}; 9 10 use super::{Analysis, Direction, Effect, EffectIndex, Results}; 11 12 /// A `ResultsCursor` that borrows the underlying `Results`. 13 pub type ResultsRefCursor<'a, 'mir, 'tcx, A> = ResultsCursor<'mir, 'tcx, A, &'a Results<'tcx, A>>; 14 15 /// Allows random access inspection of the results of a dataflow analysis. 16 /// 17 /// This cursor only has linear performance within a basic block when its statements are visited in 18 /// the same order as the `DIRECTION` of the analysis. In the worst case—when statements are 19 /// visited in *reverse* order—performance will be quadratic in the number of statements in the 20 /// block. The order in which basic blocks are inspected has no impact on performance. 21 /// 22 /// A `ResultsCursor` can either own (the default) or borrow the dataflow results it inspects. The 23 /// type of ownership is determined by `R` (see `ResultsRefCursor` above). 24 pub struct ResultsCursor<'mir, 'tcx, A, R = Results<'tcx, A>> 25 where 26 A: Analysis<'tcx>, 27 { 28 body: &'mir mir::Body<'tcx>, 29 results: R, 30 state: A::Domain, 31 32 pos: CursorPosition, 33 34 /// Indicates that `state` has been modified with a custom effect. 35 /// 36 /// When this flag is set, we need to reset to an entry set before doing a seek. 37 state_needs_reset: bool, 38 39 #[cfg(debug_assertions)] 40 reachable_blocks: BitSet<BasicBlock>, 41 } 42 43 impl<'mir, 'tcx, A, R> ResultsCursor<'mir, 'tcx, A, R> 44 where 45 A: Analysis<'tcx>, 46 R: Borrow<Results<'tcx, A>>, 47 { 48 /// Returns a new cursor that can inspect `results`. new(body: &'mir mir::Body<'tcx>, results: R) -> Self49 pub fn new(body: &'mir mir::Body<'tcx>, results: R) -> Self { 50 let bottom_value = results.borrow().analysis.bottom_value(body); 51 ResultsCursor { 52 body, 53 results, 54 55 // Initialize to the `bottom_value` and set `state_needs_reset` to tell the cursor that 56 // it needs to reset to block entry before the first seek. The cursor position is 57 // immaterial. 58 state_needs_reset: true, 59 state: bottom_value, 60 pos: CursorPosition::block_entry(mir::START_BLOCK), 61 62 #[cfg(debug_assertions)] 63 reachable_blocks: mir::traversal::reachable_as_bitset(body), 64 } 65 } 66 67 /// Allows inspection of unreachable basic blocks even with `debug_assertions` enabled. 68 #[cfg(test)] allow_unreachable(&mut self)69 pub(crate) fn allow_unreachable(&mut self) { 70 #[cfg(debug_assertions)] 71 self.reachable_blocks.insert_all() 72 } 73 74 /// Returns the underlying `Results`. results(&self) -> &Results<'tcx, A>75 pub fn results(&self) -> &Results<'tcx, A> { 76 &self.results.borrow() 77 } 78 79 /// Returns the `Analysis` used to generate the underlying `Results`. analysis(&self) -> &A80 pub fn analysis(&self) -> &A { 81 &self.results.borrow().analysis 82 } 83 84 /// Returns the dataflow state at the current location. get(&self) -> &A::Domain85 pub fn get(&self) -> &A::Domain { 86 &self.state 87 } 88 89 /// Resets the cursor to hold the entry set for the given basic block. 90 /// 91 /// For forward dataflow analyses, this is the dataflow state prior to the first statement. 92 /// 93 /// For backward dataflow analyses, this is the dataflow state after the terminator. seek_to_block_entry(&mut self, block: BasicBlock)94 pub(super) fn seek_to_block_entry(&mut self, block: BasicBlock) { 95 #[cfg(debug_assertions)] 96 assert!(self.reachable_blocks.contains(block)); 97 98 self.state.clone_from(&self.results.borrow().entry_set_for_block(block)); 99 self.pos = CursorPosition::block_entry(block); 100 self.state_needs_reset = false; 101 } 102 103 /// Resets the cursor to hold the state prior to the first statement in a basic block. 104 /// 105 /// For forward analyses, this is the entry set for the given block. 106 /// 107 /// For backward analyses, this is the state that will be propagated to its 108 /// predecessors (ignoring edge-specific effects). seek_to_block_start(&mut self, block: BasicBlock)109 pub fn seek_to_block_start(&mut self, block: BasicBlock) { 110 if A::Direction::is_forward() { 111 self.seek_to_block_entry(block) 112 } else { 113 self.seek_after(Location { block, statement_index: 0 }, Effect::Primary) 114 } 115 } 116 117 /// Resets the cursor to hold the state after the terminator in a basic block. 118 /// 119 /// For backward analyses, this is the entry set for the given block. 120 /// 121 /// For forward analyses, this is the state that will be propagated to its 122 /// successors (ignoring edge-specific effects). seek_to_block_end(&mut self, block: BasicBlock)123 pub fn seek_to_block_end(&mut self, block: BasicBlock) { 124 if A::Direction::is_backward() { 125 self.seek_to_block_entry(block) 126 } else { 127 self.seek_after(self.body.terminator_loc(block), Effect::Primary) 128 } 129 } 130 131 /// Advances the cursor to hold the dataflow state at `target` before its "primary" effect is 132 /// applied. 133 /// 134 /// The "before" effect at the target location *will be* applied. seek_before_primary_effect(&mut self, target: Location)135 pub fn seek_before_primary_effect(&mut self, target: Location) { 136 self.seek_after(target, Effect::Before) 137 } 138 139 /// Advances the cursor to hold the dataflow state at `target` after its "primary" effect is 140 /// applied. 141 /// 142 /// The "before" effect at the target location will be applied as well. seek_after_primary_effect(&mut self, target: Location)143 pub fn seek_after_primary_effect(&mut self, target: Location) { 144 self.seek_after(target, Effect::Primary) 145 } 146 seek_after(&mut self, target: Location, effect: Effect)147 fn seek_after(&mut self, target: Location, effect: Effect) { 148 assert!(target <= self.body.terminator_loc(target.block)); 149 150 // Reset to the entry of the target block if any of the following are true: 151 // - A custom effect has been applied to the cursor state. 152 // - We are in a different block than the target. 153 // - We are in the same block but have advanced past the target effect. 154 if self.state_needs_reset || self.pos.block != target.block { 155 self.seek_to_block_entry(target.block); 156 } else if let Some(curr_effect) = self.pos.curr_effect_index { 157 let mut ord = curr_effect.statement_index.cmp(&target.statement_index); 158 if A::Direction::is_backward() { 159 ord = ord.reverse() 160 } 161 162 match ord.then_with(|| curr_effect.effect.cmp(&effect)) { 163 Ordering::Equal => return, 164 Ordering::Greater => self.seek_to_block_entry(target.block), 165 Ordering::Less => {} 166 } 167 } 168 169 // At this point, the cursor is in the same block as the target location at an earlier 170 // statement. 171 debug_assert_eq!(target.block, self.pos.block); 172 173 let block_data = &self.body[target.block]; 174 let next_effect = if A::Direction::is_forward() { 175 #[rustfmt::skip] 176 self.pos.curr_effect_index.map_or_else( 177 || Effect::Before.at_index(0), 178 EffectIndex::next_in_forward_order, 179 ) 180 } else { 181 self.pos.curr_effect_index.map_or_else( 182 || Effect::Before.at_index(block_data.statements.len()), 183 EffectIndex::next_in_backward_order, 184 ) 185 }; 186 187 let analysis = &self.results.borrow().analysis; 188 let target_effect_index = effect.at_index(target.statement_index); 189 190 A::Direction::apply_effects_in_range( 191 analysis, 192 &mut self.state, 193 target.block, 194 block_data, 195 next_effect..=target_effect_index, 196 ); 197 198 self.pos = 199 CursorPosition { block: target.block, curr_effect_index: Some(target_effect_index) }; 200 } 201 202 /// Applies `f` to the cursor's internal state. 203 /// 204 /// This can be used, e.g., to apply the call return effect directly to the cursor without 205 /// creating an extra copy of the dataflow state. apply_custom_effect(&mut self, f: impl FnOnce(&A, &mut A::Domain))206 pub fn apply_custom_effect(&mut self, f: impl FnOnce(&A, &mut A::Domain)) { 207 f(&self.results.borrow().analysis, &mut self.state); 208 self.state_needs_reset = true; 209 } 210 } 211 212 impl<'mir, 'tcx, A, R, T> ResultsCursor<'mir, 'tcx, A, R> 213 where 214 A: Analysis<'tcx, Domain = BitSet<T>>, 215 T: Idx, 216 R: Borrow<Results<'tcx, A>>, 217 { contains(&self, elem: T) -> bool218 pub fn contains(&self, elem: T) -> bool { 219 self.get().contains(elem) 220 } 221 } 222 223 #[derive(Clone, Copy, Debug)] 224 struct CursorPosition { 225 block: BasicBlock, 226 curr_effect_index: Option<EffectIndex>, 227 } 228 229 impl CursorPosition { block_entry(block: BasicBlock) -> CursorPosition230 fn block_entry(block: BasicBlock) -> CursorPosition { 231 CursorPosition { block, curr_effect_index: None } 232 } 233 } 234