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     #[inline]
 260     fn into_engine<'mir>(
 261         self,
 262         tcx: TyCtxt<'tcx>,
 263         body: &'mir mir::Body<'tcx>,
 264     ) -> Engine<'mir, 'tcx, Self>
 265     where
 266         Self: Sized,
 267     {
 268         Engine::new_generic(tcx, body, self)
 269     }
 270 }
 271
 272 /// A gen/kill dataflow problem.
 273 ///
 274 /// Each method in this trait has a corresponding one in `Analysis`. However, these methods only
 275 /// allow modification of the dataflow state via "gen" and "kill" operations. By defining transfer
 276 /// functions for each statement in this way, the transfer function for an entire basic block can
 277 /// be computed efficiently.
 278 ///
 279 /// `Analysis` is automatically implemented for all implementers of `GenKillAnalysis`.
 280 pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> {
 281     type Idx: Idx;
 282
 283     /// See `Analysis::apply_statement_effect`.
 284     fn statement_effect(
 285         &self,
 286         trans: &mut impl GenKill<Self::Idx>,
 287         statement: &mir::Statement<'tcx>,
 288         location: Location,
 289     );
 290
 291     /// See `Analysis::apply_before_statement_effect`.
 292     fn before_statement_effect(
 293         &self,
 294         _trans: &mut impl GenKill<Self::Idx>,
 295         _statement: &mir::Statement<'tcx>,
 296         _location: Location,
 297     ) {
 298     }
 299
 300     /// See `Analysis::apply_terminator_effect`.
 301     fn terminator_effect(
 302         &self,
 303         trans: &mut impl GenKill<Self::Idx>,
 304         terminator: &mir::Terminator<'tcx>,
 305         location: Location,
 306     );
 307
 308     /// See `Analysis::apply_before_terminator_effect`.
 309     fn before_terminator_effect(
 310         &self,
 311         _trans: &mut impl GenKill<Self::Idx>,
 312         _terminator: &mir::Terminator<'tcx>,
 313         _location: Location,
 314     ) {
 315     }
 316
 317     /* Edge-specific effects */
 318
 319     /// See `Analysis::apply_call_return_effect`.
 320     fn call_return_effect(
 321         &self,
 322         trans: &mut impl GenKill<Self::Idx>,
 323         block: BasicBlock,
 324         return_places: CallReturnPlaces<'_, 'tcx>,
 325     );
 326
 327     /// See `Analysis::apply_yield_resume_effect`.
 328     fn yield_resume_effect(
 329         &self,
 330         _trans: &mut impl GenKill<Self::Idx>,
 331         _resume_block: BasicBlock,
 332         _resume_place: mir::Place<'tcx>,
 333     ) {
 334     }
 335
 336     /// See `Analysis::apply_switch_int_edge_effects`.
 337     fn switch_int_edge_effects<G: GenKill<Self::Idx>>(
 338         &self,
 339         _block: BasicBlock,
 340         _discr: &mir::Operand<'tcx>,
 341         _edge_effects: &mut impl SwitchIntEdgeEffects<G>,
 342     ) {
 343     }
 344 }
 345
 346 impl<'tcx, A> Analysis<'tcx> for A
 347 where
 348     A: GenKillAnalysis<'tcx>,
 349     A::Domain: GenKill<A::Idx> + BitSetExt<A::Idx>,
 350 {
 351     fn apply_statement_effect(
 352         &self,
 353         state: &mut A::Domain,
 354         statement: &mir::Statement<'tcx>,
 355         location: Location,
 356     ) {
 357         self.statement_effect(state, statement, location);
 358     }
 359
 360     fn apply_before_statement_effect(
 361         &self,
 362         state: &mut A::Domain,
 363         statement: &mir::Statement<'tcx>,
 364         location: Location,
 365     ) {
 366         self.before_statement_effect(state, statement, location);
 367     }
 368
 369     fn apply_terminator_effect(
 370         &self,
 371         state: &mut A::Domain,
 372         terminator: &mir::Terminator<'tcx>,
 373         location: Location,
 374     ) {
 375         self.terminator_effect(state, terminator, location);
 376     }
 377
 378     fn apply_before_terminator_effect(
 379         &self,
 380         state: &mut A::Domain,
 381         terminator: &mir::Terminator<'tcx>,
 382         location: Location,
 383     ) {
 384         self.before_terminator_effect(state, terminator, location);
 385     }
 386
 387     /* Edge-specific effects */
 388
 389     fn apply_call_return_effect(
 390         &self,
 391         state: &mut A::Domain,
 392         block: BasicBlock,
 393         return_places: CallReturnPlaces<'_, 'tcx>,
 394     ) {
 395         self.call_return_effect(state, block, return_places);
 396     }
 397
 398     fn apply_yield_resume_effect(
 399         &self,
 400         state: &mut A::Domain,
 401         resume_block: BasicBlock,
 402         resume_place: mir::Place<'tcx>,
 403     ) {
 404         self.yield_resume_effect(state, resume_block, resume_place);
 405     }
 406
 407     fn apply_switch_int_edge_effects(
 408         &self,
 409         block: BasicBlock,
 410         discr: &mir::Operand<'tcx>,
 411         edge_effects: &mut impl SwitchIntEdgeEffects<A::Domain>,
 412     ) {
 413         self.switch_int_edge_effects(block, discr, edge_effects);
 414     }
 415
 416     /* Extension methods */
 417     #[inline]
 418     fn into_engine<'mir>(
 419         self,
 420         tcx: TyCtxt<'tcx>,
 421         body: &'mir mir::Body<'tcx>,
 422     ) -> Engine<'mir, 'tcx, Self>
 423     where
 424         Self: Sized,
 425     {
 426         Engine::new_gen_kill(tcx, body, self)
 427     }
 428 }
 429
 430 /// The legal operations for a transfer function in a gen/kill problem.
 431 ///
 432 /// This abstraction exists because there are two different contexts in which we call the methods in
 433 /// `GenKillAnalysis`. Sometimes we need to store a single transfer function that can be efficiently
 434 /// applied multiple times, such as when computing the cumulative transfer function for each block.
 435 /// These cases require a `GenKillSet`, which in turn requires two `BitSet`s of storage. Oftentimes,
 436 /// however, we only need to apply an effect once. In *these* cases, it is more efficient to pass the
 437 /// `BitSet` representing the state vector directly into the `*_effect` methods as opposed to
 438 /// building up a `GenKillSet` and then throwing it away.
 439 pub trait GenKill<T> {
 440     /// Inserts `elem` into the state vector.
 441     fn gen(&mut self, elem: T);
 442
 443     /// Removes `elem` from the state vector.
 444     fn kill(&mut self, elem: T);
 445
 446     /// Calls `gen` for each element in `elems`.
 447     fn gen_all(&mut self, elems: impl IntoIterator<Item = T>) {
 448         for elem in elems {
 449             self.gen(elem);
 450         }
 451     }
 452
 453     /// Calls `kill` for each element in `elems`.
 454     fn kill_all(&mut self, elems: impl IntoIterator<Item = T>) {
 455         for elem in elems {
 456             self.kill(elem);
 457         }
 458     }
 459 }
 460
 461 /// Stores a transfer function for a gen/kill problem.
 462 ///
 463 /// Calling `gen`/`kill` on a `GenKillSet` will "build up" a transfer function so that it can be
 464 /// applied multiple times efficiently. When there are multiple calls to `gen` and/or `kill` for
 465 /// the same element, the most recent one takes precedence.
 466 #[derive(Clone)]
 467 pub struct GenKillSet<T> {
 468     gen: HybridBitSet<T>,
 469     kill: HybridBitSet<T>,
 470 }
 471
 472 impl<T: Idx> GenKillSet<T> {
 473     /// Creates a new transfer function that will leave the dataflow state unchanged.
 474     pub fn identity(universe: usize) -> Self {
 475         GenKillSet {
 476             gen: HybridBitSet::new_empty(universe),
 477             kill: HybridBitSet::new_empty(universe),
 478         }
 479     }
 480
 481     pub fn apply(&self, state: &mut impl BitSetExt<T>) {
 482         state.union(&self.gen);
 483         state.subtract(&self.kill);
 484     }
 485 }
 486
 487 impl<T: Idx> GenKill<T> for GenKillSet<T> {
 488     fn gen(&mut self, elem: T) {
 489         self.gen.insert(elem);
 490         self.kill.remove(elem);
 491     }
 492
 493     fn kill(&mut self, elem: T) {
 494         self.kill.insert(elem);
 495         self.gen.remove(elem);
 496     }
 497 }
 498
 499 impl<T: Idx> GenKill<T> for BitSet<T> {
 500     fn gen(&mut self, elem: T) {
 501         self.insert(elem);
 502     }
 503
 504     fn kill(&mut self, elem: T) {
 505         self.remove(elem);
 506     }
 507 }
 508
 509 impl<T: Idx> GenKill<T> for ChunkedBitSet<T> {
 510     fn gen(&mut self, elem: T) {
 511         self.insert(elem);
 512     }
 513
 514     fn kill(&mut self, elem: T) {
 515         self.remove(elem);
 516     }
 517 }
 518
 519 impl<T: Idx> GenKill<T> for lattice::Dual<BitSet<T>> {
 520     fn gen(&mut self, elem: T) {
 521         self.0.insert(elem);
 522     }
 523
 524     fn kill(&mut self, elem: T) {
 525         self.0.remove(elem);
 526     }
 527 }
 528
 529 // NOTE: DO NOT CHANGE VARIANT ORDER. The derived `Ord` impls rely on the current order.
 530 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
 531 pub enum Effect {
 532     /// The "before" effect (e.g., `apply_before_statement_effect`) for a statement (or
 533     /// terminator).
 534     Before,
 535
 536     /// The "primary" effect (e.g., `apply_statement_effect`) for a statement (or terminator).
 537     Primary,
 538 }
 539
 540 impl Effect {
 541     pub const fn at_index(self, statement_index: usize) -> EffectIndex {
 542         EffectIndex { effect: self, statement_index }
 543     }
 544 }
 545
 546 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
 547 pub struct EffectIndex {
 548     statement_index: usize,
 549     effect: Effect,
 550 }
 551
 552 impl EffectIndex {
 553     fn next_in_forward_order(self) -> Self {
 554         match self.effect {
 555             Effect::Before => Effect::Primary.at_index(self.statement_index),
 556             Effect::Primary => Effect::Before.at_index(self.statement_index + 1),
 557         }
 558     }
 559
 560     fn next_in_backward_order(self) -> Self {
 561         match self.effect {
 562             Effect::Before => Effect::Primary.at_index(self.statement_index),
 563             Effect::Primary => Effect::Before.at_index(self.statement_index - 1),
 564         }
 565     }
 566
 567     /// Returns `true` if the effect at `self` should be applied earlier than the effect at `other`
 568     /// in forward order.
 569     fn precedes_in_forward_order(self, other: Self) -> bool {
 570         let ord = self
 571             .statement_index
 572             .cmp(&other.statement_index)
 573             .then_with(|| self.effect.cmp(&other.effect));
 574         ord == Ordering::Less
 575     }
 576
 577     /// Returns `true` if the effect at `self` should be applied earlier than the effect at `other`
 578     /// in backward order.
 579     fn precedes_in_backward_order(self, other: Self) -> bool {
 580         let ord = other
 581             .statement_index
 582             .cmp(&self.statement_index)
 583             .then_with(|| self.effect.cmp(&other.effect));
 584         ord == Ordering::Less
 585     }
 586 }
 587
 588 pub struct SwitchIntTarget {
 589     pub value: Option<u128>,
 590     pub target: BasicBlock,
 591 }
 592
 593 /// A type that records the edge-specific effects for a `SwitchInt` terminator.
 594 pub trait SwitchIntEdgeEffects<D> {
 595     /// Calls `apply_edge_effect` for each outgoing edge from a `SwitchInt` terminator and
 596     /// records the results.
 597     fn apply(&mut self, apply_edge_effect: impl FnMut(&mut D, SwitchIntTarget));
 598 }
 599
 600 /// List of places that are written to after a successful (non-unwind) return
 601 /// from a `Call` or `InlineAsm`.
 602 pub enum CallReturnPlaces<'a, 'tcx> {
 603     Call(mir::Place<'tcx>),
 604     InlineAsm(&'a [mir::InlineAsmOperand<'tcx>]),
 605 }
 606
 607 impl<'tcx> CallReturnPlaces<'_, 'tcx> {
 608     pub fn for_each(&self, mut f: impl FnMut(mir::Place<'tcx>)) {
 609         match *self {
 610             Self::Call(place) => f(place),
 611             Self::InlineAsm(operands) => {
 612                 for op in operands {
 613                     match *op {
 614                         mir::InlineAsmOperand::Out { place: Some(place), .. }
 615                         | mir::InlineAsmOperand::InOut { out_place: Some(place), .. } => f(place),
 616                         _ => {}
 617                     }
 618                 }
 619             }
 620         }
 621     }
 622 }
 623
 624 #[cfg(test)]
 625 mod tests;