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::move_paths::{HasMoveData, MovePathIndex};
   8 use crate::dataflow::{BitDenotation, DataflowResults, GenKillSet};
   9
  10 use std::borrow::Borrow;
  11 use std::iter;
  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 { base_results: results, curr_state, stmt_trans }
 102     }
 103
 104     /// Access the underlying operator.
 105     pub fn operator(&self) -> &BD {
 106         self.base_results.borrow().operator()
 107     }
 108
 109     pub fn contains(&self, x: BD::Idx) -> bool {
 110         self.curr_state.contains(x)
 111     }
 112
 113     /// Returns an iterator over the elements present in the current state.
 114     pub fn iter_incoming(&self) -> iter::Peekable<BitIter<'_, BD::Idx>> {
 115         self.curr_state.iter().peekable()
 116     }
 117
 118     /// Creates a clone of the current state and applies the local
 119     /// effects to the clone (leaving the state of self intact).
 120     /// Invokes `f` with an iterator over the resulting state.
 121     pub fn with_iter_outgoing<F>(&self, f: F)
 122     where
 123         F: FnOnce(BitIter<'_, BD::Idx>),
 124     {
 125         let mut curr_state = self.curr_state.clone();
 126         self.stmt_trans.apply(&mut curr_state);
 127         f(curr_state.iter());
 128     }
 129
 130     /// Returns a bitset of the elements present in the current state.
 131     pub fn as_dense(&self) -> &BitSet<BD::Idx> {
 132         &self.curr_state
 133     }
 134 }
 135
 136 impl<'tcx, BD, DR> FlowsAtLocation for FlowAtLocation<'tcx, BD, DR>
 137 where
 138     BD: BitDenotation<'tcx>,
 139     DR: Borrow<DataflowResults<'tcx, BD>>,
 140 {
 141     fn reset_to_entry_of(&mut self, bb: BasicBlock) {
 142         self.curr_state.overwrite(self.base_results.borrow().sets().entry_set_for(bb.index()));
 143     }
 144
 145     fn reset_to_exit_of(&mut self, bb: BasicBlock) {
 146         self.reset_to_entry_of(bb);
 147         let trans = self.base_results.borrow().sets().trans_for(bb.index());
 148         trans.apply(&mut self.curr_state)
 149     }
 150
 151     fn reconstruct_statement_effect(&mut self, loc: Location) {
 152         self.stmt_trans.clear();
 153         self.base_results.borrow().operator().before_statement_effect(&mut self.stmt_trans, loc);
 154         self.stmt_trans.apply(&mut self.curr_state);
 155
 156         self.base_results.borrow().operator().statement_effect(&mut self.stmt_trans, loc);
 157     }
 158
 159     fn reconstruct_terminator_effect(&mut self, loc: Location) {
 160         self.stmt_trans.clear();
 161         self.base_results.borrow().operator().before_terminator_effect(&mut self.stmt_trans, loc);
 162         self.stmt_trans.apply(&mut self.curr_state);
 163
 164         self.base_results.borrow().operator().terminator_effect(&mut self.stmt_trans, loc);
 165     }
 166
 167     fn apply_local_effect(&mut self, _loc: Location) {
 168         self.stmt_trans.apply(&mut self.curr_state)
 169     }
 170 }
 171
 172 impl<'tcx, T, DR> FlowAtLocation<'tcx, T, DR>
 173 where
 174     T: HasMoveData<'tcx> + BitDenotation<'tcx, Idx = MovePathIndex>,
 175     DR: Borrow<DataflowResults<'tcx, T>>,
 176 {
 177     pub fn has_any_child_of(&self, mpi: T::Idx) -> Option<T::Idx> {
 178         // We process `mpi` before the loop below, for two reasons:
 179         // - it's a little different from the loop case (we don't traverse its
 180         //   siblings);
 181         // - ~99% of the time the loop isn't reached, and this code is hot, so
 182         //   we don't want to allocate `todo` unnecessarily.
 183         if self.contains(mpi) {
 184             return Some(mpi);
 185         }
 186         let move_data = self.operator().move_data();
 187         let move_path = &move_data.move_paths[mpi];
 188         let mut todo = if let Some(child) = move_path.first_child {
 189             vec![child]
 190         } else {
 191             return None;
 192         };
 193
 194         while let Some(mpi) = todo.pop() {
 195             if self.contains(mpi) {
 196                 return Some(mpi);
 197             }
 198             let move_path = &move_data.move_paths[mpi];
 199             if let Some(child) = move_path.first_child {
 200                 todo.push(child);
 201             }
 202             // After we've processed the original `mpi`, we should always
 203             // traverse the siblings of any of its children.
 204             if let Some(sibling) = move_path.next_sibling {
 205                 todo.push(sibling);
 206             }
 207         }
 208         return None;
 209     }
 210 }