src/librustc_mir/dataflow/at_location.rs

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