compiler/rustc_mir/src/dataflow/framework/mod.rs

   1 //! A framework that can express both [gen-kill] and generic dataflow problems.
   2 //!
   3 //! To actually use this framework, you must implement either the `Analysis` or the
   4 //! `GenKillAnalysis` trait. If your transfer function can be expressed with only gen/kill
   5 //! operations, prefer `GenKillAnalysis` since it will run faster while iterating to fixpoint. The
   6 //! `impls` module contains several examples of gen/kill dataflow analyses.
   7 //!
   8 //! Create an `Engine` for your analysis using the `into_engine` method on the `Analysis` trait,
   9 //! then call `iterate_to_fixpoint`. From there, you can use a `ResultsCursor` to inspect the
  10 //! fixpoint solution to your dataflow problem, or implement the `ResultsVisitor` interface and use
  11 //! `visit_results`. The following example uses the `ResultsCursor` approach.
  12 //!
  13 //! ```ignore(cross-crate-imports)
  14 //! use rustc_mir::dataflow::Analysis; // Makes `into_engine` available.
  15 //!
  16 //! fn do_my_analysis(tcx: TyCtxt<'tcx>, body: &mir::Body<'tcx>) {
  17 //!     let analysis = MyAnalysis::new()
  18 //!         .into_engine(tcx, body)
  19 //!         .iterate_to_fixpoint()
  20 //!         .into_results_cursor(body);
  21 //!
  22 //!     // Print the dataflow state *after* each statement in the start block.
  23 //!     for (_, statement_index) in body.block_data[START_BLOCK].statements.iter_enumerated() {
  24 //!         cursor.seek_after(Location { block: START_BLOCK, statement_index });
  25 //!         let state = cursor.get();
  26 //!         println!("{:?}", state);
  27 //!     }
  28 //! }
  29 //! ```
  30 //!
  31 //! [gen-kill]: https://en.wikipedia.org/wiki/Data-flow_analysis#Bit_vector_problems
  32
  33 use std::borrow::BorrowMut;
  34 use std::cmp::Ordering;
  35
  36 use rustc_index::bit_set::{BitSet, HybridBitSet};
  37 use rustc_index::vec::Idx;
  38 use rustc_middle::mir::{self, BasicBlock, Location};
  39 use rustc_middle::ty::TyCtxt;
  40
  41 mod cursor;
  42 mod direction;
  43 mod engine;
  44 pub mod fmt;
  45 mod graphviz;
  46 pub mod lattice;
  47 mod visitor;
  48
  49 pub use self::cursor::{ResultsCursor, ResultsRefCursor};
  50 pub use self::direction::{Backward, Direction, Forward};
  51 pub use self::engine::{Engine, Results};
  52 pub use self::lattice::{JoinSemiLattice, MeetSemiLattice};
  53 pub use self::visitor::{visit_results, ResultsVisitor};
  54 pub use self::visitor::{BorrowckFlowState, BorrowckResults};
  55
  56 /// Define the domain of a dataflow problem.
  57 ///
  58 /// This trait specifies the lattice on which this analysis operates (the domain) as well as its
  59 /// initial value at the entry point of each basic block.
  60 pub trait AnalysisDomain<'tcx> {
  61     /// The type that holds the dataflow state at any given point in the program.
  62     type Domain: Clone + JoinSemiLattice;
  63
  64     /// The direction of this analysis. Either `Forward` or `Backward`.
  65     type Direction: Direction = Forward;
  66
  67     /// A descriptive name for this analysis. Used only for debugging.
  68     ///
  69     /// This name should be brief and contain no spaces, periods or other characters that are not
  70     /// suitable as part of a filename.
  71     const NAME: &'static str;
  72
  73     /// The initial value of the dataflow state upon entry to each basic block.
  74     fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain;
  75
  76     /// Mutates the initial value of the dataflow state upon entry to the `START_BLOCK`.
  77     ///
  78     /// For backward analyses, initial state besides the bottom value is not yet supported. Trying
  79     /// to mutate the initial state will result in a panic.
  80     //
  81     // FIXME: For backward dataflow analyses, the initial state should be applied to every basic
  82     // block where control flow could exit the MIR body (e.g., those terminated with `return` or
  83     // `resume`). It's not obvious how to handle `yield` points in generators, however.
  84     fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut Self::Domain);
  85 }
  86
  87 /// A dataflow problem with an arbitrarily complex transfer function.
  88 ///
  89 /// # Convergence
  90 ///
  91 /// When implementing this trait directly (not via [`GenKillAnalysis`]), it's possible to choose a
  92 /// transfer function such that the analysis does not reach fixpoint. To guarantee convergence,
  93 /// your transfer functions must maintain the following invariant:
  94 ///
  95 /// > If the dataflow state **before** some point in the program changes to be greater
  96 /// than the prior state **before** that point, the dataflow state **after** that point must
  97 /// also change to be greater than the prior state **after** that point.
  98 ///
  99 /// This invariant guarantees that the dataflow state at a given point in the program increases
 100 /// monotonically until fixpoint is reached. Note that this monotonicity requirement only applies
 101 /// to the same point in the program at different points in time. The dataflow state at a given
 102 /// point in the program may or may not be greater than the state at any preceding point.
 103 pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
 104     /// Updates the current dataflow state with the effect of evaluating a statement.
 105     fn apply_statement_effect(
 106         &self,
 107         state: &mut Self::Domain,
 108         statement: &mir::Statement<'tcx>,
 109         location: Location,
 110     );
 111
 112     /// Updates the current dataflow state with an effect that occurs immediately *before* the
 113     /// given statement.
 114     ///
 115     /// This method is useful if the consumer of the results of this analysis needs only to observe
 116     /// *part* of the effect of a statement (e.g. for two-phase borrows). As a general rule,
 117     /// analyses should not implement this without implementing `apply_statement_effect`.
 118     fn apply_before_statement_effect(
 119         &self,
 120         _state: &mut Self::Domain,
 121         _statement: &mir::Statement<'tcx>,
 122         _location: Location,
 123     ) {
 124     }
 125
 126     /// Updates the current dataflow state with the effect of evaluating a terminator.
 127     ///
 128     /// The effect of a successful return from a `Call` terminator should **not** be accounted for
 129     /// in this function. That should go in `apply_call_return_effect`. For example, in the
 130     /// `InitializedPlaces` analyses, the return place for a function call is not marked as
 131     /// initialized here.
 132     fn apply_terminator_effect(
 133         &self,
 134         state: &mut Self::Domain,
 135         terminator: &mir::Terminator<'tcx>,
 136         location: Location,
 137     );
 138
 139     /// Updates the current dataflow state with an effect that occurs immediately *before* the
 140     /// given terminator.
 141     ///
 142     /// This method is useful if the consumer of the results of this analysis needs only to observe
 143     /// *part* of the effect of a terminator (e.g. for two-phase borrows). As a general rule,
 144     /// analyses should not implement this without implementing `apply_terminator_effect`.
 145     fn apply_before_terminator_effect(
 146         &self,
 147         _state: &mut Self::Domain,
 148         _terminator: &mir::Terminator<'tcx>,
 149         _location: Location,
 150     ) {
 151     }
 152
 153     /* Edge-specific effects */
 154
 155     /// Updates the current dataflow state with the effect of a successful return from a `Call`
 156     /// terminator.
 157     ///
 158     /// This is separate from `apply_terminator_effect` to properly track state across unwind
 159     /// edges.
 160     fn apply_call_return_effect(
 161         &self,
 162         state: &mut Self::Domain,
 163         block: BasicBlock,
 164         func: &mir::Operand<'tcx>,
 165         args: &[mir::Operand<'tcx>],
 166         return_place: mir::Place<'tcx>,
 167     );
 168
 169     /// Updates the current dataflow state with the effect of resuming from a `Yield` terminator.
 170     ///
 171     /// This is similar to `apply_call_return_effect` in that it only takes place after the
 172     /// generator is resumed, not when it is dropped.
 173     ///
 174     /// By default, no effects happen.
 175     fn apply_yield_resume_effect(
 176         &self,
 177         _state: &mut Self::Domain,
 178         _resume_block: BasicBlock,
 179         _resume_place: mir::Place<'tcx>,
 180     ) {
 181     }
 182
 183     /// Updates the current dataflow state with the effect of taking a particular branch in a
 184     /// `SwitchInt` terminator.
 185     ///
 186     /// Unlike the other edge-specific effects, which are allowed to mutate `Self::Domain`
 187     /// directly, overriders of this method must pass a callback to
 188     /// `SwitchIntEdgeEffects::apply`. The callback will be run once for each outgoing edge and
 189     /// will have access to the dataflow state that will be propagated along that edge.
 190     ///
 191     /// This interface is somewhat more complex than the other visitor-like "effect" methods.
 192     /// However, it is both more ergonomic—callers don't need to recompute or cache information
 193     /// about a given `SwitchInt` terminator for each one of its edges—and more efficient—the
 194     /// engine doesn't need to clone the exit state for a block unless
 195     /// `SwitchIntEdgeEffects::apply` is actually called.
 196     ///
 197     /// FIXME: This class of effects is not supported for backward dataflow analyses.
 198     fn apply_switch_int_edge_effects(
 199         &self,
 200         _block: BasicBlock,
 201         _discr: &mir::Operand<'tcx>,
 202         _apply_edge_effects: &mut impl SwitchIntEdgeEffects<Self::Domain>,
 203     ) {
 204     }
 205
 206     /* Extension methods */
 207
 208     /// Creates an `Engine` to find the fixpoint for this dataflow problem.
 209     ///
 210     /// You shouldn't need to override this outside this module, since the combination of the
 211     /// default impl and the one for all `A: GenKillAnalysis` will do the right thing.
 212     /// Its purpose is to enable method chaining like so:
 213     ///
 214     /// ```ignore(cross-crate-imports)
 215     /// let results = MyAnalysis::new(tcx, body)
 216     ///     .into_engine(tcx, body, def_id)
 217     ///     .iterate_to_fixpoint()
 218     ///     .into_results_cursor(body);
 219     /// ```
 220     fn into_engine(self, tcx: TyCtxt<'tcx>, body: &'mir mir::Body<'tcx>) -> Engine<'mir, 'tcx, Self>
 221     where
 222         Self: Sized,
 223     {
 224         Engine::new_generic(tcx, body, self)
 225     }
 226 }
 227
 228 /// A gen/kill dataflow problem.
 229 ///
 230 /// Each method in this trait has a corresponding one in `Analysis`. However, these methods only
 231 /// allow modification of the dataflow state via "gen" and "kill" operations. By defining transfer
 232 /// functions for each statement in this way, the transfer function for an entire basic block can
 233 /// be computed efficiently.
 234 ///
 235 /// `Analysis` is automatically implemented for all implementers of `GenKillAnalysis`.
 236 pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> {
 237     type Idx: Idx;
 238
 239     /// See `Analysis::apply_statement_effect`.
 240     fn statement_effect(
 241         &self,
 242         trans: &mut impl GenKill<Self::Idx>,
 243         statement: &mir::Statement<'tcx>,
 244         location: Location,
 245     );
 246
 247     /// See `Analysis::apply_before_statement_effect`.
 248     fn before_statement_effect(
 249         &self,
 250         _trans: &mut impl GenKill<Self::Idx>,
 251         _statement: &mir::Statement<'tcx>,
 252         _location: Location,
 253     ) {
 254     }
 255
 256     /// See `Analysis::apply_terminator_effect`.
 257     fn terminator_effect(
 258         &self,
 259         trans: &mut impl GenKill<Self::Idx>,
 260         terminator: &mir::Terminator<'tcx>,
 261         location: Location,
 262     );
 263
 264     /// See `Analysis::apply_before_terminator_effect`.
 265     fn before_terminator_effect(
 266         &self,
 267         _trans: &mut impl GenKill<Self::Idx>,
 268         _terminator: &mir::Terminator<'tcx>,
 269         _location: Location,
 270     ) {
 271     }
 272
 273     /* Edge-specific effects */
 274
 275     /// See `Analysis::apply_call_return_effect`.
 276     fn call_return_effect(
 277         &self,
 278         trans: &mut impl GenKill<Self::Idx>,
 279         block: BasicBlock,
 280         func: &mir::Operand<'tcx>,
 281         args: &[mir::Operand<'tcx>],
 282         return_place: mir::Place<'tcx>,
 283     );
 284
 285     /// See `Analysis::apply_yield_resume_effect`.
 286     fn yield_resume_effect(
 287         &self,
 288         _trans: &mut impl GenKill<Self::Idx>,
 289         _resume_block: BasicBlock,
 290         _resume_place: mir::Place<'tcx>,
 291     ) {
 292     }
 293
 294     /// See `Analysis::apply_switch_int_edge_effects`.
 295     fn switch_int_edge_effects<G: GenKill<Self::Idx>>(
 296         &self,
 297         _block: BasicBlock,
 298         _discr: &mir::Operand<'tcx>,
 299         _edge_effects: &mut impl SwitchIntEdgeEffects<G>,
 300     ) {
 301     }
 302 }
 303
 304 impl<A> Analysis<'tcx> for A
 305 where
 306     A: GenKillAnalysis<'tcx>,
 307     A::Domain: GenKill<A::Idx> + BorrowMut<BitSet<A::Idx>>,
 308 {
 309     fn apply_statement_effect(
 310         &self,
 311         state: &mut A::Domain,
 312         statement: &mir::Statement<'tcx>,
 313         location: Location,
 314     ) {
 315         self.statement_effect(state, statement, location);
 316     }
 317
 318     fn apply_before_statement_effect(
 319         &self,
 320         state: &mut A::Domain,
 321         statement: &mir::Statement<'tcx>,
 322         location: Location,
 323     ) {
 324         self.before_statement_effect(state, statement, location);
 325     }
 326
 327     fn apply_terminator_effect(
 328         &self,
 329         state: &mut A::Domain,
 330         terminator: &mir::Terminator<'tcx>,
 331         location: Location,
 332     ) {
 333         self.terminator_effect(state, terminator, location);
 334     }
 335
 336     fn apply_before_terminator_effect(
 337         &self,
 338         state: &mut A::Domain,
 339         terminator: &mir::Terminator<'tcx>,
 340         location: Location,
 341     ) {
 342         self.before_terminator_effect(state, terminator, location);
 343     }
 344
 345     /* Edge-specific effects */
 346
 347     fn apply_call_return_effect(
 348         &self,
 349         state: &mut A::Domain,
 350         block: BasicBlock,
 351         func: &mir::Operand<'tcx>,
 352         args: &[mir::Operand<'tcx>],
 353         return_place: mir::Place<'tcx>,
 354     ) {
 355         self.call_return_effect(state, block, func, args, return_place);
 356     }
 357
 358     fn apply_yield_resume_effect(
 359         &self,
 360         state: &mut A::Domain,
 361         resume_block: BasicBlock,
 362         resume_place: mir::Place<'tcx>,
 363     ) {
 364         self.yield_resume_effect(state, resume_block, resume_place);
 365     }
 366
 367     fn apply_switch_int_edge_effects(
 368         &self,
 369         block: BasicBlock,
 370         discr: &mir::Operand<'tcx>,
 371         edge_effects: &mut impl SwitchIntEdgeEffects<A::Domain>,
 372     ) {
 373         self.switch_int_edge_effects(block, discr, edge_effects);
 374     }
 375
 376     /* Extension methods */
 377
 378     fn into_engine(self, tcx: TyCtxt<'tcx>, body: &'mir mir::Body<'tcx>) -> Engine<'mir, 'tcx, Self>
 379     where
 380         Self: Sized,
 381     {
 382         Engine::new_gen_kill(tcx, body, self)
 383     }
 384 }
 385
 386 /// The legal operations for a transfer function in a gen/kill problem.
 387 ///
 388 /// This abstraction exists because there are two different contexts in which we call the methods in
 389 /// `GenKillAnalysis`. Sometimes we need to store a single transfer function that can be efficiently
 390 /// applied multiple times, such as when computing the cumulative transfer function for each block.
 391 /// These cases require a `GenKillSet`, which in turn requires two `BitSet`s of storage. Oftentimes,
 392 /// however, we only need to apply an effect once. In *these* cases, it is more efficient to pass the
 393 /// `BitSet` representing the state vector directly into the `*_effect` methods as opposed to
 394 /// building up a `GenKillSet` and then throwing it away.
 395 pub trait GenKill<T> {
 396     /// Inserts `elem` into the state vector.
 397     fn gen(&mut self, elem: T);
 398
 399     /// Removes `elem` from the state vector.
 400     fn kill(&mut self, elem: T);
 401
 402     /// Calls `gen` for each element in `elems`.
 403     fn gen_all(&mut self, elems: impl IntoIterator<Item = T>) {
 404         for elem in elems {
 405             self.gen(elem);
 406         }
 407     }
 408
 409     /// Calls `kill` for each element in `elems`.
 410     fn kill_all(&mut self, elems: impl IntoIterator<Item = T>) {
 411         for elem in elems {
 412             self.kill(elem);
 413         }
 414     }
 415 }
 416
 417 /// Stores a transfer function for a gen/kill problem.
 418 ///
 419 /// Calling `gen`/`kill` on a `GenKillSet` will "build up" a transfer function so that it can be
 420 /// applied multiple times efficiently. When there are multiple calls to `gen` and/or `kill` for
 421 /// the same element, the most recent one takes precedence.
 422 #[derive(Clone)]
 423 pub struct GenKillSet<T> {
 424     gen: HybridBitSet<T>,
 425     kill: HybridBitSet<T>,
 426 }
 427
 428 impl<T: Idx> GenKillSet<T> {
 429     /// Creates a new transfer function that will leave the dataflow state unchanged.
 430     pub fn identity(universe: usize) -> Self {
 431         GenKillSet {
 432             gen: HybridBitSet::new_empty(universe),
 433             kill: HybridBitSet::new_empty(universe),
 434         }
 435     }
 436
 437     pub fn apply(&self, state: &mut BitSet<T>) {
 438         state.union(&self.gen);
 439         state.subtract(&self.kill);
 440     }
 441 }
 442
 443 impl<T: Idx> GenKill<T> for GenKillSet<T> {
 444     fn gen(&mut self, elem: T) {
 445         self.gen.insert(elem);
 446         self.kill.remove(elem);
 447     }
 448
 449     fn kill(&mut self, elem: T) {
 450         self.kill.insert(elem);
 451         self.gen.remove(elem);
 452     }
 453 }
 454
 455 impl<T: Idx> GenKill<T> for BitSet<T> {
 456     fn gen(&mut self, elem: T) {
 457         self.insert(elem);
 458     }
 459
 460     fn kill(&mut self, elem: T) {
 461         self.remove(elem);
 462     }
 463 }
 464
 465 impl<T: Idx> GenKill<T> for lattice::Dual<BitSet<T>> {
 466     fn gen(&mut self, elem: T) {
 467         self.0.insert(elem);
 468     }
 469
 470     fn kill(&mut self, elem: T) {
 471         self.0.remove(elem);
 472     }
 473 }
 474
 475 // NOTE: DO NOT CHANGE VARIANT ORDER. The derived `Ord` impls rely on the current order.
 476 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
 477 pub enum Effect {
 478     /// The "before" effect (e.g., `apply_before_statement_effect`) for a statement (or
 479     /// terminator).
 480     Before,
 481
 482     /// The "primary" effect (e.g., `apply_statement_effect`) for a statement (or terminator).
 483     Primary,
 484 }
 485
 486 impl Effect {
 487     pub const fn at_index(self, statement_index: usize) -> EffectIndex {
 488         EffectIndex { effect: self, statement_index }
 489     }
 490 }
 491
 492 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
 493 pub struct EffectIndex {
 494     statement_index: usize,
 495     effect: Effect,
 496 }
 497
 498 impl EffectIndex {
 499     fn next_in_forward_order(self) -> Self {
 500         match self.effect {
 501             Effect::Before => Effect::Primary.at_index(self.statement_index),
 502             Effect::Primary => Effect::Before.at_index(self.statement_index + 1),
 503         }
 504     }
 505
 506     fn next_in_backward_order(self) -> Self {
 507         match self.effect {
 508             Effect::Before => Effect::Primary.at_index(self.statement_index),
 509             Effect::Primary => Effect::Before.at_index(self.statement_index - 1),
 510         }
 511     }
 512
 513     /// Returns `true` if the effect at `self` should be applied eariler than the effect at `other`
 514     /// in forward order.
 515     fn precedes_in_forward_order(self, other: Self) -> bool {
 516         let ord = self
 517             .statement_index
 518             .cmp(&other.statement_index)
 519             .then_with(|| self.effect.cmp(&other.effect));
 520         ord == Ordering::Less
 521     }
 522
 523     /// Returns `true` if the effect at `self` should be applied earlier than the effect at `other`
 524     /// in backward order.
 525     fn precedes_in_backward_order(self, other: Self) -> bool {
 526         let ord = other
 527             .statement_index
 528             .cmp(&self.statement_index)
 529             .then_with(|| self.effect.cmp(&other.effect));
 530         ord == Ordering::Less
 531     }
 532 }
 533
 534 pub struct SwitchIntTarget {
 535     pub value: Option<u128>,
 536     pub target: BasicBlock,
 537 }
 538
 539 /// A type that records the edge-specific effects for a `SwitchInt` terminator.
 540 pub trait SwitchIntEdgeEffects<D> {
 541     /// Calls `apply_edge_effect` for each outgoing edge from a `SwitchInt` terminator and
 542     /// records the results.
 543     fn apply(&mut self, apply_edge_effect: impl FnMut(&mut D, SwitchIntTarget));
 544 }
 545
 546 #[cfg(test)]
 547 mod tests;