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