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