src/librustc_mir/dataflow/generic/mod.rs

   1 //! A framework for expressing dataflow problems.
   2
   3 use std::io;
   4
   5 use rustc::mir::{self, BasicBlock, Location};
   6 use rustc_index::bit_set::{BitSet, HybridBitSet};
   7 use rustc_index::vec::{Idx, IndexVec};
   8
   9 use crate::dataflow::BottomValue;
  10
  11 mod cursor;
  12 mod engine;
  13 mod graphviz;
  14
  15 pub use self::cursor::{ResultsCursor, ResultsRefCursor};
  16 pub use self::engine::Engine;
  17
  18 /// A dataflow analysis that has converged to fixpoint.
  19 pub struct Results<'tcx, A>
  20 where
  21     A: Analysis<'tcx>,
  22 {
  23     pub analysis: A,
  24     entry_sets: IndexVec<BasicBlock, BitSet<A::Idx>>,
  25 }
  26
  27 impl<A> Results<'tcx, A>
  28 where
  29     A: Analysis<'tcx>,
  30 {
  31     pub fn into_cursor(self, body: &'mir mir::Body<'tcx>) -> ResultsCursor<'mir, 'tcx, A> {
  32         ResultsCursor::new(body, self)
  33     }
  34
  35     pub fn on_block_entry(&self, block: BasicBlock) -> &BitSet<A::Idx> {
  36         &self.entry_sets[block]
  37     }
  38 }
  39
  40 /// Define the domain of a dataflow problem.
  41 ///
  42 /// This trait specifies the lattice on which this analysis operates. For now, this must be a
  43 /// powerset of values of type `Idx`. The elements of this lattice are represented with a `BitSet`
  44 /// and referred to as the state vector.
  45 ///
  46 /// This trait also defines the initial value for the dataflow state upon entry to the
  47 /// `START_BLOCK`, as well as some names used to refer to this analysis when debugging.
  48 pub trait AnalysisDomain<'tcx>: BottomValue {
  49     /// The type of the elements in the state vector.
  50     type Idx: Idx;
  51
  52     /// A descriptive name for this analysis. Used only for debugging.
  53     ///
  54     /// This name should be brief and contain no spaces, periods or other characters that are not
  55     /// suitable as part of a filename.
  56     const NAME: &'static str;
  57
  58     /// The size of the state vector.
  59     fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize;
  60
  61     /// Mutates the entry set of the `START_BLOCK` to contain the initial state for dataflow
  62     /// analysis.
  63     fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>);
  64
  65     /// Prints an element in the state vector for debugging.
  66     fn pretty_print_idx(&self, w: &mut impl io::Write, idx: Self::Idx) -> io::Result<()> {
  67         write!(w, "{:?}", idx)
  68     }
  69 }
  70
  71 /// Define a dataflow problem with an arbitrarily complex transfer function.
  72 pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
  73     /// Updates the current dataflow state with the effect of evaluating a statement.
  74     fn apply_statement_effect(
  75         &self,
  76         state: &mut BitSet<Self::Idx>,
  77         statement: &mir::Statement<'tcx>,
  78         location: Location,
  79     );
  80
  81     /// Updates the current dataflow state with an effect that occurs immediately *before* the
  82     /// given statement.
  83     ///
  84     /// This method is useful if the consumer of the results of this analysis needs only to observe
  85     /// *part* of the effect of a statement (e.g. for two-phase borrows). As a general rule,
  86     /// analyses should not implement this without implementing `apply_statement_effect`.
  87     fn apply_before_statement_effect(
  88         &self,
  89         _state: &mut BitSet<Self::Idx>,
  90         _statement: &mir::Statement<'tcx>,
  91         _location: Location,
  92     ) {
  93     }
  94
  95     /// Updates the current dataflow state with the effect of evaluating a terminator.
  96     ///
  97     /// The effect of a successful return from a `Call` terminator should **not** be accounted for
  98     /// in this function. That should go in `apply_call_return_effect`. For example, in the
  99     /// `InitializedPlaces` analyses, the return place for a function call is not marked as
 100     /// initialized here.
 101     fn apply_terminator_effect(
 102         &self,
 103         state: &mut BitSet<Self::Idx>,
 104         terminator: &mir::Terminator<'tcx>,
 105         location: Location,
 106     );
 107
 108     /// Updates the current dataflow state with an effect that occurs immediately *before* the
 109     /// given terminator.
 110     ///
 111     /// This method is useful if the consumer of the results of this analysis needs only to observe
 112     /// *part* of the effect of a terminator (e.g. for two-phase borrows). As a general rule,
 113     /// analyses should not implement this without implementing `apply_terminator_effect`.
 114     fn apply_before_terminator_effect(
 115         &self,
 116         _state: &mut BitSet<Self::Idx>,
 117         _terminator: &mir::Terminator<'tcx>,
 118         _location: Location,
 119     ) {
 120     }
 121
 122     /// Updates the current dataflow state with the effect of a successful return from a `Call`
 123     /// terminator.
 124     ///
 125     /// This is separate from `apply_terminator_effect` to properly track state across unwind
 126     /// edges.
 127     fn apply_call_return_effect(
 128         &self,
 129         state: &mut BitSet<Self::Idx>,
 130         block: BasicBlock,
 131         func: &mir::Operand<'tcx>,
 132         args: &[mir::Operand<'tcx>],
 133         return_place: &mir::Place<'tcx>,
 134     );
 135 }
 136
 137 /// Define a gen/kill dataflow problem.
 138 ///
 139 /// Each method in this trait has a corresponding one in `Analysis`. However, these methods only
 140 /// allow modification of the dataflow state via "gen" and "kill" operations. By defining transfer
 141 /// functions for each statement in this way, the transfer function for an entire basic block can
 142 /// be computed efficiently.
 143 ///
 144 /// `Analysis` is automatically implemented for all implementers of `GenKillAnalysis`.
 145 pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> {
 146     /// See `Analysis::apply_statement_effect`.
 147     fn statement_effect(
 148         &self,
 149         trans: &mut impl GenKill<Self::Idx>,
 150         statement: &mir::Statement<'tcx>,
 151         location: Location,
 152     );
 153
 154     /// See `Analysis::apply_before_statement_effect`.
 155     fn before_statement_effect(
 156         &self,
 157         _trans: &mut impl GenKill<Self::Idx>,
 158         _statement: &mir::Statement<'tcx>,
 159         _location: Location,
 160     ) {
 161     }
 162
 163     /// See `Analysis::apply_terminator_effect`.
 164     fn terminator_effect(
 165         &self,
 166         trans: &mut impl GenKill<Self::Idx>,
 167         terminator: &mir::Terminator<'tcx>,
 168         location: Location,
 169     );
 170
 171     /// See `Analysis::apply_before_terminator_effect`.
 172     fn before_terminator_effect(
 173         &self,
 174         _trans: &mut impl GenKill<Self::Idx>,
 175         _terminator: &mir::Terminator<'tcx>,
 176         _location: Location,
 177     ) {
 178     }
 179
 180     /// See `Analysis::apply_call_return_effect`.
 181     fn call_return_effect(
 182         &self,
 183         trans: &mut impl GenKill<Self::Idx>,
 184         block: BasicBlock,
 185         func: &mir::Operand<'tcx>,
 186         args: &[mir::Operand<'tcx>],
 187         return_place: &mir::Place<'tcx>,
 188     );
 189 }
 190
 191 impl<A> Analysis<'tcx> for A
 192 where
 193     A: GenKillAnalysis<'tcx>,
 194 {
 195     fn apply_statement_effect(
 196         &self,
 197         state: &mut BitSet<Self::Idx>,
 198         statement: &mir::Statement<'tcx>,
 199         location: Location,
 200     ) {
 201         self.statement_effect(state, statement, location);
 202     }
 203
 204     fn apply_before_statement_effect(
 205         &self,
 206         state: &mut BitSet<Self::Idx>,
 207         statement: &mir::Statement<'tcx>,
 208         location: Location,
 209     ) {
 210         self.before_statement_effect(state, statement, location);
 211     }
 212
 213     fn apply_terminator_effect(
 214         &self,
 215         state: &mut BitSet<Self::Idx>,
 216         terminator: &mir::Terminator<'tcx>,
 217         location: Location,
 218     ) {
 219         self.terminator_effect(state, terminator, location);
 220     }
 221
 222     fn apply_before_terminator_effect(
 223         &self,
 224         state: &mut BitSet<Self::Idx>,
 225         terminator: &mir::Terminator<'tcx>,
 226         location: Location,
 227     ) {
 228         self.before_terminator_effect(state, terminator, location);
 229     }
 230
 231     fn apply_call_return_effect(
 232         &self,
 233         state: &mut BitSet<Self::Idx>,
 234         block: BasicBlock,
 235         func: &mir::Operand<'tcx>,
 236         args: &[mir::Operand<'tcx>],
 237         return_place: &mir::Place<'tcx>,
 238     ) {
 239         self.call_return_effect(state, block, func, args, return_place);
 240     }
 241 }
 242
 243 /// The legal operations for a transfer function in a gen/kill problem.
 244 pub trait GenKill<T>: Sized {
 245     /// Inserts `elem` into the `gen` set, removing it the `kill` set if present.
 246     fn gen(&mut self, elem: T);
 247
 248     /// Inserts `elem` into the `kill` set, removing it the `gen` set if present.
 249     fn kill(&mut self, elem: T);
 250
 251     /// Inserts the given elements into the `gen` set, removing them from the `kill` set if present.
 252     fn gen_all(&mut self, elems: impl IntoIterator<Item = T>) {
 253         for elem in elems {
 254             self.gen(elem);
 255         }
 256     }
 257
 258     /// Inserts the given elements into the `kill` set, removing them from the `gen` set if present.
 259     fn kill_all(&mut self, elems: impl IntoIterator<Item = T>) {
 260         for elem in elems {
 261             self.kill(elem);
 262         }
 263     }
 264 }
 265
 266 /// Stores a transfer function for a gen/kill problem.
 267 #[derive(Clone)]
 268 pub struct GenKillSet<T: Idx> {
 269     gen: HybridBitSet<T>,
 270     kill: HybridBitSet<T>,
 271 }
 272
 273 impl<T: Idx> GenKillSet<T> {
 274     /// Creates a new transfer function that will leave the dataflow state unchanged.
 275     pub fn identity(universe: usize) -> Self {
 276         GenKillSet {
 277             gen: HybridBitSet::new_empty(universe),
 278             kill: HybridBitSet::new_empty(universe),
 279         }
 280     }
 281
 282     /// Applies this transfer function to the given bitset.
 283     pub fn apply(&self, state: &mut BitSet<T>) {
 284         state.union(&self.gen);
 285         state.subtract(&self.kill);
 286     }
 287 }
 288
 289 impl<T: Idx> GenKill<T> for GenKillSet<T> {
 290     fn gen(&mut self, elem: T) {
 291         self.gen.insert(elem);
 292         self.kill.remove(elem);
 293     }
 294
 295     fn kill(&mut self, elem: T) {
 296         self.kill.insert(elem);
 297         self.gen.remove(elem);
 298     }
 299 }
 300
 301 impl<T: Idx> GenKill<T> for BitSet<T> {
 302     fn gen(&mut self, elem: T) {
 303         self.insert(elem);
 304     }
 305
 306     fn kill(&mut self, elem: T) {
 307         self.remove(elem);
 308     }
 309 }
 310
 311 #[cfg(test)]
 312 mod tests;