diff options
Diffstat (limited to 'compiler/rustc_mir_dataflow/src/framework/mod.rs')
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/mod.rs | 265 |
1 files changed, 37 insertions, 228 deletions
diff --git a/compiler/rustc_mir_dataflow/src/framework/mod.rs b/compiler/rustc_mir_dataflow/src/framework/mod.rs index d0472e35fe0..959f1ea5340 100644 --- a/compiler/rustc_mir_dataflow/src/framework/mod.rs +++ b/compiler/rustc_mir_dataflow/src/framework/mod.rs @@ -1,9 +1,11 @@ //! A framework that can express both [gen-kill] and generic dataflow problems. //! -//! To use this framework, implement either the [`Analysis`] or the -//! [`GenKillAnalysis`] trait. If your transfer function can be expressed with only gen/kill -//! operations, prefer `GenKillAnalysis` since it will run faster while iterating to fixpoint. The -//! `impls` module contains several examples of gen/kill dataflow analyses. +//! To use this framework, implement the [`Analysis`] trait. There used to be a `GenKillAnalysis` +//! alternative trait for gen-kill analyses that would pre-compute the transfer function for each +//! block. It was intended as an optimization, but it ended up not being any faster than +//! `Analysis`. +//! +//! The `impls` module contains several examples of dataflow analyses. //! //! Create an `Engine` for your analysis using the `into_engine` method on the `Analysis` trait, //! then call `iterate_to_fixpoint`. From there, you can use a `ResultsCursor` to inspect the @@ -87,11 +89,26 @@ impl<T: Idx> BitSetExt<T> for ChunkedBitSet<T> { } } -/// Defines the domain of a dataflow problem. +/// A dataflow problem with an arbitrarily complex transfer function. +/// +/// This trait specifies the lattice on which this analysis operates (the domain), its +/// initial value at the entry point of each basic block, and various operations. +/// +/// # Convergence +/// +/// When implementing this trait it's possible to choose a transfer function such that the analysis +/// does not reach fixpoint. To guarantee convergence, your transfer functions must maintain the +/// following invariant: +/// +/// > If the dataflow state **before** some point in the program changes to be greater +/// than the prior state **before** that point, the dataflow state **after** that point must +/// also change to be greater than the prior state **after** that point. /// -/// This trait specifies the lattice on which this analysis operates (the domain) as well as its -/// initial value at the entry point of each basic block. -pub trait AnalysisDomain<'tcx> { +/// This invariant guarantees that the dataflow state at a given point in the program increases +/// monotonically until fixpoint is reached. Note that this monotonicity requirement only applies +/// to the same point in the program at different points in time. The dataflow state at a given +/// point in the program may or may not be greater than the state at any preceding point. +pub trait Analysis<'tcx> { /// The type that holds the dataflow state at any given point in the program. type Domain: Clone + JoinSemiLattice; @@ -116,25 +133,7 @@ pub trait AnalysisDomain<'tcx> { // block where control flow could exit the MIR body (e.g., those terminated with `return` or // `resume`). It's not obvious how to handle `yield` points in coroutines, however. fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut Self::Domain); -} -/// A dataflow problem with an arbitrarily complex transfer function. -/// -/// # Convergence -/// -/// When implementing this trait directly (not via [`GenKillAnalysis`]), it's possible to choose a -/// transfer function such that the analysis does not reach fixpoint. To guarantee convergence, -/// your transfer functions must maintain the following invariant: -/// -/// > If the dataflow state **before** some point in the program changes to be greater -/// than the prior state **before** that point, the dataflow state **after** that point must -/// also change to be greater than the prior state **after** that point. -/// -/// This invariant guarantees that the dataflow state at a given point in the program increases -/// monotonically until fixpoint is reached. Note that this monotonicity requirement only applies -/// to the same point in the program at different points in time. The dataflow state at a given -/// point in the program may or may not be greater than the state at any preceding point. -pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { /// Updates the current dataflow state with the effect of evaluating a statement. fn apply_statement_effect( &mut self, @@ -165,10 +164,12 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { /// initialized here. fn apply_terminator_effect<'mir>( &mut self, - state: &mut Self::Domain, + _state: &mut Self::Domain, terminator: &'mir mir::Terminator<'tcx>, - location: Location, - ) -> TerminatorEdges<'mir, 'tcx>; + _location: Location, + ) -> TerminatorEdges<'mir, 'tcx> { + terminator.edges() + } /// Updates the current dataflow state with an effect that occurs immediately *before* the /// given terminator. @@ -193,10 +194,11 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { /// edges. fn apply_call_return_effect( &mut self, - state: &mut Self::Domain, - block: BasicBlock, - return_places: CallReturnPlaces<'_, 'tcx>, - ); + _state: &mut Self::Domain, + _block: BasicBlock, + _return_places: CallReturnPlaces<'_, 'tcx>, + ) { + } /// Updates the current dataflow state with the effect of taking a particular branch in a /// `SwitchInt` terminator. @@ -223,9 +225,7 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { /// Creates an `Engine` to find the fixpoint for this dataflow problem. /// - /// You shouldn't need to override this outside this module, since the combination of the - /// default impl and the one for all `A: GenKillAnalysis` will do the right thing. - /// Its purpose is to enable method chaining like so: + /// You shouldn't need to override this. Its purpose is to enable method chaining like so: /// /// ```ignore (cross-crate-imports) /// let results = MyAnalysis::new(tcx, body) @@ -242,164 +242,11 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { where Self: Sized, { - Engine::new_generic(tcx, body, self) - } -} - -/// A gen/kill dataflow problem. -/// -/// Each method in this trait has a corresponding one in `Analysis`. However, the first two methods -/// here only allow modification of the dataflow state via "gen" and "kill" operations. By defining -/// transfer functions for each statement in this way, the transfer function for an entire basic -/// block can be computed efficiently. The remaining methods match up with `Analysis` exactly. -/// -/// `Analysis` is automatically implemented for all implementers of `GenKillAnalysis` via a blanket -/// impl below. -pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> { - type Idx: Idx; - - fn domain_size(&self, body: &mir::Body<'tcx>) -> usize; - - /// See `Analysis::apply_statement_effect`. Note how the second arg differs. - fn statement_effect( - &mut self, - trans: &mut impl GenKill<Self::Idx>, - statement: &mir::Statement<'tcx>, - location: Location, - ); - - /// See `Analysis::apply_before_statement_effect`. Note how the second arg - /// differs. - fn before_statement_effect( - &mut self, - _trans: &mut impl GenKill<Self::Idx>, - _statement: &mir::Statement<'tcx>, - _location: Location, - ) { - } - - /// See `Analysis::apply_terminator_effect`. - fn terminator_effect<'mir>( - &mut self, - trans: &mut Self::Domain, - terminator: &'mir mir::Terminator<'tcx>, - location: Location, - ) -> TerminatorEdges<'mir, 'tcx>; - - /// See `Analysis::apply_before_terminator_effect`. - fn before_terminator_effect( - &mut self, - _trans: &mut Self::Domain, - _terminator: &mir::Terminator<'tcx>, - _location: Location, - ) { - } - - /* Edge-specific effects */ - - /// See `Analysis::apply_call_return_effect`. - fn call_return_effect( - &mut self, - trans: &mut Self::Domain, - block: BasicBlock, - return_places: CallReturnPlaces<'_, 'tcx>, - ); - - /// See `Analysis::apply_switch_int_edge_effects`. - fn switch_int_edge_effects<G: GenKill<Self::Idx>>( - &mut self, - _block: BasicBlock, - _discr: &mir::Operand<'tcx>, - _edge_effects: &mut impl SwitchIntEdgeEffects<G>, - ) { - } -} - -// Blanket impl: any impl of `GenKillAnalysis` automatically impls `Analysis`. -impl<'tcx, A> Analysis<'tcx> for A -where - A: GenKillAnalysis<'tcx>, - A::Domain: GenKill<A::Idx> + BitSetExt<A::Idx>, -{ - fn apply_statement_effect( - &mut self, - state: &mut A::Domain, - statement: &mir::Statement<'tcx>, - location: Location, - ) { - self.statement_effect(state, statement, location); - } - - fn apply_before_statement_effect( - &mut self, - state: &mut A::Domain, - statement: &mir::Statement<'tcx>, - location: Location, - ) { - self.before_statement_effect(state, statement, location); - } - - fn apply_terminator_effect<'mir>( - &mut self, - state: &mut A::Domain, - terminator: &'mir mir::Terminator<'tcx>, - location: Location, - ) -> TerminatorEdges<'mir, 'tcx> { - self.terminator_effect(state, terminator, location) - } - - fn apply_before_terminator_effect( - &mut self, - state: &mut A::Domain, - terminator: &mir::Terminator<'tcx>, - location: Location, - ) { - self.before_terminator_effect(state, terminator, location); - } - - /* Edge-specific effects */ - - fn apply_call_return_effect( - &mut self, - state: &mut A::Domain, - block: BasicBlock, - return_places: CallReturnPlaces<'_, 'tcx>, - ) { - self.call_return_effect(state, block, return_places); - } - - fn apply_switch_int_edge_effects( - &mut self, - block: BasicBlock, - discr: &mir::Operand<'tcx>, - edge_effects: &mut impl SwitchIntEdgeEffects<A::Domain>, - ) { - self.switch_int_edge_effects(block, discr, edge_effects); - } - - /* Extension methods */ - #[inline] - fn into_engine<'mir>( - self, - tcx: TyCtxt<'tcx>, - body: &'mir mir::Body<'tcx>, - ) -> Engine<'mir, 'tcx, Self> - where - Self: Sized, - { - Engine::new_gen_kill(tcx, body, self) + Engine::new(tcx, body, self) } } /// The legal operations for a transfer function in a gen/kill problem. -/// -/// This abstraction exists because there are two different contexts in which we call the methods in -/// `GenKillAnalysis`. Sometimes we need to store a single transfer function that can be efficiently -/// applied multiple times, such as when computing the cumulative transfer function for each block. -/// These cases require a `GenKillSet`, which in turn requires two `BitSet`s of storage. Oftentimes, -/// however, we only need to apply an effect once. In *these* cases, it is more efficient to pass the -/// `BitSet` representing the state vector directly into the `*_effect` methods as opposed to -/// building up a `GenKillSet` and then throwing it away. pub trait GenKill<T> { /// Inserts `elem` into the state vector. fn gen_(&mut self, elem: T); @@ -422,44 +269,6 @@ pub trait GenKill<T> { } } -/// Stores a transfer function for a gen/kill problem. -/// -/// Calling `gen_`/`kill` on a `GenKillSet` will "build up" a transfer function so that it can be -/// applied multiple times efficiently. When there are multiple calls to `gen_` and/or `kill` for -/// the same element, the most recent one takes precedence. -#[derive(Clone)] -pub struct GenKillSet<T> { - gen_: HybridBitSet<T>, - kill: HybridBitSet<T>, -} - -impl<T: Idx> GenKillSet<T> { - /// Creates a new transfer function that will leave the dataflow state unchanged. - pub fn identity(universe: usize) -> Self { - GenKillSet { - gen_: HybridBitSet::new_empty(universe), - kill: HybridBitSet::new_empty(universe), - } - } - - pub fn apply(&self, state: &mut impl BitSetExt<T>) { - state.union(&self.gen_); - state.subtract(&self.kill); - } -} - -impl<T: Idx> GenKill<T> for GenKillSet<T> { - fn gen_(&mut self, elem: T) { - self.gen_.insert(elem); - self.kill.remove(elem); - } - - fn kill(&mut self, elem: T) { - self.kill.insert(elem); - self.gen_.remove(elem); - } -} - impl<T: Idx> GenKill<T> for BitSet<T> { fn gen_(&mut self, elem: T) { self.insert(elem); |