src/librustc_mir/dataflow/generic/mod.rs

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