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