compiler/rustc_mir_dataflow/src/framework/mod.rs

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