src/librustc_mir/dataflow/at_location.rs

   1 //! A nice wrapper to consume dataflow results at several CFG
   2 //! locations.
   3
   4 use rustc::mir::{BasicBlock, Location};
   5 use rustc_data_structures::bit_set::{BitIter, BitSet, HybridBitSet};
   6
   7 use crate::dataflow::{BitDenotation, BlockSets, DataflowResults};
   8 use crate::dataflow::move_paths::{HasMoveData, MovePathIndex};
   9
  10 use std::iter;
  11
  12 /// A trait for "cartesian products" of multiple FlowAtLocation.
  13 ///
  14 /// There's probably a way to auto-impl this, but I think
  15 /// it is cleaner to have manual visitor impls.
  16 pub trait FlowsAtLocation {
  17     /// Reset the state bitvector to represent the entry to block `bb`.
  18     fn reset_to_entry_of(&mut self, bb: BasicBlock);
  19
  20     /// Reset the state bitvector to represent the exit of the
  21     /// terminator of block `bb`.
  22     ///
  23     /// **Important:** In the case of a `Call` terminator, these
  24     /// effects do *not* include the result of storing the destination
  25     /// of the call, since that is edge-dependent (in other words, the
  26     /// effects don't apply to the unwind edge).
  27     fn reset_to_exit_of(&mut self, bb: BasicBlock);
  28
  29     /// Builds gen and kill sets for statement at `loc`.
  30     ///
  31     /// Note that invoking this method alone does not change the
  32     /// `curr_state` -- you must invoke `apply_local_effect`
  33     /// afterwards.
  34     fn reconstruct_statement_effect(&mut self, loc: Location);
  35
  36     /// Builds gen and kill sets for terminator for `loc`.
  37     ///
  38     /// Note that invoking this method alone does not change the
  39     /// `curr_state` -- you must invoke `apply_local_effect`
  40     /// afterwards.
  41     fn reconstruct_terminator_effect(&mut self, loc: Location);
  42
  43     /// Apply current gen + kill sets to `flow_state`.
  44     ///
  45     /// (`loc` parameters can be ignored if desired by
  46     /// client. For the terminator, the `stmt_idx` will be the number
  47     /// of statements in the block.)
  48     fn apply_local_effect(&mut self, loc: Location);
  49 }
  50
  51 /// Represents the state of dataflow at a particular
  52 /// CFG location, both before and after it is
  53 /// executed.
  54 ///
  55 /// Data flow results are typically computed only as basic block
  56 /// boundaries. A `FlowInProgress` allows you to reconstruct the
  57 /// effects at any point in the control-flow graph by starting with
  58 /// the state at the start of the basic block (`reset_to_entry_of`)
  59 /// and then replaying the effects of statements and terminators
  60 /// (e.g., via `reconstruct_statement_effect` and
  61 /// `reconstruct_terminator_effect`; don't forget to call
  62 /// `apply_local_effect`).
  63 pub struct FlowAtLocation<'tcx, BD>
  64 where
  65     BD: BitDenotation<'tcx>,
  66 {
  67     base_results: DataflowResults<'tcx, BD>,
  68     curr_state: BitSet<BD::Idx>,
  69     stmt_gen: HybridBitSet<BD::Idx>,
  70     stmt_kill: HybridBitSet<BD::Idx>,
  71 }
  72
  73 impl<'tcx, BD> FlowAtLocation<'tcx, BD>
  74 where
  75     BD: BitDenotation<'tcx>,
  76 {
  77     /// Iterate over each bit set in the current state.
  78     pub fn each_state_bit<F>(&self, f: F)
  79     where
  80         F: FnMut(BD::Idx),
  81     {
  82         self.curr_state.iter().for_each(f)
  83     }
  84
  85     /// Iterate over each `gen` bit in the current effect (invoke
  86     /// `reconstruct_statement_effect` or
  87     /// `reconstruct_terminator_effect` first).
  88     pub fn each_gen_bit<F>(&self, f: F)
  89     where
  90         F: FnMut(BD::Idx),
  91     {
  92         self.stmt_gen.iter().for_each(f)
  93     }
  94
  95     pub fn new(results: DataflowResults<'tcx, BD>) -> Self {
  96         let bits_per_block = results.sets().bits_per_block();
  97         let curr_state = BitSet::new_empty(bits_per_block);
  98         let stmt_gen = HybridBitSet::new_empty(bits_per_block);
  99         let stmt_kill = HybridBitSet::new_empty(bits_per_block);
 100         FlowAtLocation {
 101             base_results: results,
 102             curr_state: curr_state,
 103             stmt_gen: stmt_gen,
 104             stmt_kill: stmt_kill,
 105         }
 106     }
 107
 108     /// Access the underlying operator.
 109     pub fn operator(&self) -> &BD {
 110         self.base_results.operator()
 111     }
 112
 113     pub fn contains(&self, x: BD::Idx) -> bool {
 114         self.curr_state.contains(x)
 115     }
 116
 117     /// Returns an iterator over the elements present in the current state.
 118     pub fn iter_incoming(&self) -> iter::Peekable<BitIter<'_, BD::Idx>> {
 119         self.curr_state.iter().peekable()
 120     }
 121
 122     /// Creates a clone of the current state and applies the local
 123     /// effects to the clone (leaving the state of self intact).
 124     /// Invokes `f` with an iterator over the resulting state.
 125     pub fn with_iter_outgoing<F>(&self, f: F)
 126     where
 127         F: FnOnce(BitIter<'_, BD::Idx>),
 128     {
 129         let mut curr_state = self.curr_state.clone();
 130         curr_state.union(&self.stmt_gen);
 131         curr_state.subtract(&self.stmt_kill);
 132         f(curr_state.iter());
 133     }
 134
 135     /// Returns a bitset of the elements present in the current state.
 136     pub fn as_dense(&self) -> &BitSet<BD::Idx> {
 137         &self.curr_state
 138     }
 139 }
 140
 141 impl<'tcx, BD> FlowsAtLocation for FlowAtLocation<'tcx, BD>
 142     where BD: BitDenotation<'tcx>
 143 {
 144     fn reset_to_entry_of(&mut self, bb: BasicBlock) {
 145         self.curr_state.overwrite(self.base_results.sets().on_entry_set_for(bb.index()));
 146     }
 147
 148     fn reset_to_exit_of(&mut self, bb: BasicBlock) {
 149         self.reset_to_entry_of(bb);
 150         self.curr_state.union(self.base_results.sets().gen_set_for(bb.index()));
 151         self.curr_state.subtract(self.base_results.sets().kill_set_for(bb.index()));
 152     }
 153
 154     fn reconstruct_statement_effect(&mut self, loc: Location) {
 155         self.stmt_gen.clear();
 156         self.stmt_kill.clear();
 157         {
 158             let mut sets = BlockSets {
 159                 on_entry: &mut self.curr_state,
 160                 gen_set: &mut self.stmt_gen,
 161                 kill_set: &mut self.stmt_kill,
 162             };
 163             self.base_results
 164                 .operator()
 165                 .before_statement_effect(&mut sets, loc);
 166         }
 167         self.apply_local_effect(loc);
 168
 169         let mut sets = BlockSets {
 170             on_entry: &mut self.curr_state,
 171             gen_set: &mut self.stmt_gen,
 172             kill_set: &mut self.stmt_kill,
 173         };
 174         self.base_results
 175             .operator()
 176             .statement_effect(&mut sets, loc);
 177     }
 178
 179     fn reconstruct_terminator_effect(&mut self, loc: Location) {
 180         self.stmt_gen.clear();
 181         self.stmt_kill.clear();
 182         {
 183             let mut sets = BlockSets {
 184                 on_entry: &mut self.curr_state,
 185                 gen_set: &mut self.stmt_gen,
 186                 kill_set: &mut self.stmt_kill,
 187             };
 188             self.base_results
 189                 .operator()
 190                 .before_terminator_effect(&mut sets, loc);
 191         }
 192         self.apply_local_effect(loc);
 193
 194         let mut sets = BlockSets {
 195             on_entry: &mut self.curr_state,
 196             gen_set: &mut self.stmt_gen,
 197             kill_set: &mut self.stmt_kill,
 198         };
 199         self.base_results
 200             .operator()
 201             .terminator_effect(&mut sets, loc);
 202     }
 203
 204     fn apply_local_effect(&mut self, _loc: Location) {
 205         self.curr_state.union(&self.stmt_gen);
 206         self.curr_state.subtract(&self.stmt_kill);
 207     }
 208 }
 209
 210
 211 impl<'tcx, T> FlowAtLocation<'tcx, T>
 212 where
 213     T: HasMoveData<'tcx> + BitDenotation<'tcx, Idx = MovePathIndex>,
 214 {
 215     pub fn has_any_child_of(&self, mpi: T::Idx) -> Option<T::Idx> {
 216         // We process `mpi` before the loop below, for two reasons:
 217         // - it's a little different from the loop case (we don't traverse its
 218         //   siblings);
 219         // - ~99% of the time the loop isn't reached, and this code is hot, so
 220         //   we don't want to allocate `todo` unnecessarily.
 221         if self.contains(mpi) {
 222             return Some(mpi);
 223         }
 224         let move_data = self.operator().move_data();
 225         let move_path = &move_data.move_paths[mpi];
 226         let mut todo = if let Some(child) = move_path.first_child {
 227             vec![child]
 228         } else {
 229             return None;
 230         };
 231
 232         while let Some(mpi) = todo.pop() {
 233             if self.contains(mpi) {
 234                 return Some(mpi);
 235             }
 236             let move_path = &move_data.move_paths[mpi];
 237             if let Some(child) = move_path.first_child {
 238                 todo.push(child);
 239             }
 240             // After we've processed the original `mpi`, we should always
 241             // traverse the siblings of any of its children.
 242             if let Some(sibling) = move_path.next_sibling {
 243                 todo.push(sibling);
 244             }
 245         }
 246         return None;
 247     }
 248 }