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
   9 use std::borrow::Borrow;
  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, DR = DataflowResults<'tcx, BD>>
  64 where
  65     BD: BitDenotation<'tcx>,
  66     DR: Borrow<DataflowResults<'tcx, BD>>,
  67 {
  68     base_results: DR,
  69     curr_state: BitSet<BD::Idx>,
  70     stmt_trans: GenKillSet<BD::Idx>,
  71 }
  72
  73 impl<'tcx, BD, DR> FlowAtLocation<'tcx, BD, DR>
  74 where
  75     BD: BitDenotation<'tcx>,
  76     DR: Borrow<DataflowResults<'tcx, BD>>,
  77 {
  78     /// Iterate over each bit set in the current state.
  79     pub fn each_state_bit<F>(&self, f: F)
  80     where
  81         F: FnMut(BD::Idx),
  82     {
  83         self.curr_state.iter().for_each(f)
  84     }
  85
  86     /// Iterate over each `gen` bit in the current effect (invoke
  87     /// `reconstruct_statement_effect` or
  88     /// `reconstruct_terminator_effect` first).
  89     pub fn each_gen_bit<F>(&self, f: F)
  90     where
  91         F: FnMut(BD::Idx),
  92     {
  93         self.stmt_trans.gen_set.iter().for_each(f)
  94     }
  95
  96     pub fn new(results: DR) -> Self {
  97         let bits_per_block = results.borrow().sets().bits_per_block();
  98         let curr_state = BitSet::new_empty(bits_per_block);
  99         let stmt_trans = GenKillSet::from_elem(HybridBitSet::new_empty(bits_per_block));
 100         FlowAtLocation { base_results: results, curr_state, stmt_trans }
 101     }
 102
 103     /// Access the underlying operator.
 104     pub fn operator(&self) -> &BD {
 105         self.base_results.borrow().operator()
 106     }
 107
 108     pub fn contains(&self, x: BD::Idx) -> bool {
 109         self.curr_state.contains(x)
 110     }
 111
 112     /// Returns an iterator over the elements present in the current state.
 113     pub fn iter_incoming(&self) -> iter::Peekable<BitIter<'_, BD::Idx>> {
 114         self.curr_state.iter().peekable()
 115     }
 116
 117     /// Creates a clone of the current state and applies the local
 118     /// effects to the clone (leaving the state of self intact).
 119     /// Invokes `f` with an iterator over the resulting state.
 120     pub fn with_iter_outgoing<F>(&self, f: F)
 121     where
 122         F: FnOnce(BitIter<'_, BD::Idx>),
 123     {
 124         let mut curr_state = self.curr_state.clone();
 125         self.stmt_trans.apply(&mut curr_state);
 126         f(curr_state.iter());
 127     }
 128
 129     /// Returns a bitset of the elements present in the current state.
 130     pub fn as_dense(&self) -> &BitSet<BD::Idx> {
 131         &self.curr_state
 132     }
 133 }
 134
 135 impl<'tcx, BD, DR> FlowsAtLocation for FlowAtLocation<'tcx, BD, DR>
 136 where
 137     BD: BitDenotation<'tcx>,
 138     DR: Borrow<DataflowResults<'tcx, BD>>,
 139 {
 140     fn reset_to_entry_of(&mut self, bb: BasicBlock) {
 141         self.curr_state.overwrite(self.base_results.borrow().sets().entry_set_for(bb.index()));
 142     }
 143
 144     fn reset_to_exit_of(&mut self, bb: BasicBlock) {
 145         self.reset_to_entry_of(bb);
 146         let trans = self.base_results.borrow().sets().trans_for(bb.index());
 147         trans.apply(&mut self.curr_state)
 148     }
 149
 150     fn reconstruct_statement_effect(&mut self, loc: Location) {
 151         self.stmt_trans.clear();
 152         self.base_results.borrow().operator().before_statement_effect(&mut self.stmt_trans, loc);
 153         self.stmt_trans.apply(&mut self.curr_state);
 154
 155         self.base_results.borrow().operator().statement_effect(&mut self.stmt_trans, loc);
 156     }
 157
 158     fn reconstruct_terminator_effect(&mut self, loc: Location) {
 159         self.stmt_trans.clear();
 160         self.base_results.borrow().operator().before_terminator_effect(&mut self.stmt_trans, loc);
 161         self.stmt_trans.apply(&mut self.curr_state);
 162
 163         self.base_results.borrow().operator().terminator_effect(&mut self.stmt_trans, loc);
 164     }
 165
 166     fn apply_local_effect(&mut self, _loc: Location) {
 167         self.stmt_trans.apply(&mut self.curr_state)
 168     }
 169 }