Trait Analysis

pub trait Analysis<'tcx> {
    type Domain: Clone + JoinSemiLattice;
    type Direction: Direction = Forward;
    type SwitchIntData = !;

    const NAME: &'static str;

    // Required methods
    fn bottom_value(&self, body: &Body<'tcx>) -> Self::Domain;
    fn initialize_start_block(
        &self,
        body: &Body<'tcx>,
        state: &mut Self::Domain,
    );
    fn apply_primary_statement_effect(
        &mut self,
        state: &mut Self::Domain,
        statement: &Statement<'tcx>,
        location: Location,
    );

    // Provided methods
    fn apply_early_statement_effect(
        &mut self,
        _state: &mut Self::Domain,
        _statement: &Statement<'tcx>,
        _location: Location,
    ) { ... }
    fn apply_early_terminator_effect(
        &mut self,
        _state: &mut Self::Domain,
        _terminator: &Terminator<'tcx>,
        _location: Location,
    ) { ... }
    fn apply_primary_terminator_effect<'mir>(
        &mut self,
        _state: &mut Self::Domain,
        terminator: &'mir Terminator<'tcx>,
        _location: Location,
    ) -> TerminatorEdges<'mir, 'tcx> { ... }
    fn apply_call_return_effect(
        &mut self,
        _state: &mut Self::Domain,
        _block: BasicBlock,
        _return_places: CallReturnPlaces<'_, 'tcx>,
    ) { ... }
    fn get_switch_int_data(
        &mut self,
        _block: BasicBlock,
        _discr: &Operand<'tcx>,
    ) -> Option<Self::SwitchIntData> { ... }
    fn apply_switch_int_edge_effect(
        &mut self,
        _data: &mut Self::SwitchIntData,
        _state: &mut Self::Domain,
        _edge: SwitchIntTarget,
    ) { ... }
    fn iterate_to_fixpoint<'mir>(
        self,
        tcx: TyCtxt<'tcx>,
        body: &'mir Body<'tcx>,
        pass_name: Option<&'static str>,
    ) -> Results<'tcx, Self>
       where Self: Sized,
             Self::Domain: DebugWithContext<Self> { ... }
}

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 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.

Required Associated Constants

const NAME: &'static str

A descriptive name for this analysis. Used only for debugging.

This name should be brief and contain no spaces, periods or other characters that are not suitable as part of a filename.

Required Associated Types

type Domain: Clone + JoinSemiLattice

The type that holds the dataflow state at any given point in the program.

Provided Associated Types

type Direction: Direction = Forward

The direction of this analysis. Either Forward or Backward.

type SwitchIntData = !

Auxiliary data used for analyzing SwitchInt terminators, if necessary.

Required Methods

fn bottom_value(&self, body: &Body<'tcx>) -> Self::Domain

Returns the initial value of the dataflow state upon entry to each basic block.

fn initialize_start_block(&self, body: &Body<'tcx>, state: &mut Self::Domain)

Mutates the initial value of the dataflow state upon entry to the START_BLOCK.

For backward analyses, initial state (besides the bottom value) is not yet supported. Trying to mutate the initial state will result in a panic.

fn apply_primary_statement_effect( &mut self, state: &mut Self::Domain, statement: &Statement<'tcx>, location: Location, )

Updates the current dataflow state with the effect of evaluating a statement.

Provided Methods

fn apply_early_statement_effect( &mut self, _state: &mut Self::Domain, _statement: &Statement<'tcx>, _location: Location, )

Updates the current dataflow state with an “early” effect, i.e. one that occurs immediately before the given statement.

This method is useful if the consumer of the results of this analysis only needs to observe part of the effect of a statement (e.g. for two-phase borrows). As a general rule, analyses should not implement this without also implementing apply_primary_statement_effect.

fn apply_early_terminator_effect( &mut self, _state: &mut Self::Domain, _terminator: &Terminator<'tcx>, _location: Location, )

Updates the current dataflow state with an effect that occurs immediately before the given terminator.

This method is useful if the consumer of the results of this analysis needs only to observe part of the effect of a terminator (e.g. for two-phase borrows). As a general rule, analyses should not implement this without also implementing apply_primary_terminator_effect.

fn apply_primary_terminator_effect<'mir>( &mut self, _state: &mut Self::Domain, terminator: &'mir Terminator<'tcx>, _location: Location, ) -> TerminatorEdges<'mir, 'tcx>

Updates the current dataflow state with the effect of evaluating a terminator.

The effect of a successful return from a Call terminator should not be accounted for in this function. That should go in apply_call_return_effect. For example, in the InitializedPlaces analyses, the return place for a function call is not marked as initialized here.

fn apply_call_return_effect( &mut self, _state: &mut Self::Domain, _block: BasicBlock, _return_places: CallReturnPlaces<'_, 'tcx>, )

Updates the current dataflow state with the effect of a successful return from a Call terminator.

This is separate from apply_primary_terminator_effect to properly track state across unwind edges.

fn get_switch_int_data( &mut self, _block: BasicBlock, _discr: &Operand<'tcx>, ) -> Option<Self::SwitchIntData>

Used to update the current dataflow state with the effect of taking a particular branch in a SwitchInt terminator.

Unlike the other edge-specific effects, which are allowed to mutate Self::Domain directly, overriders of this method must return a Self::SwitchIntData value (wrapped in Some). The apply_switch_int_edge_effect method will then be called once for each outgoing edge and will have access to the dataflow state that will be propagated along that edge, and also the Self::SwitchIntData value.

This interface is somewhat more complex than the other visitor-like “effect” methods. However, it is both more ergonomic—callers don’t need to recompute or cache information about a given SwitchInt terminator for each one of its edges—and more efficient—the engine doesn’t need to clone the exit state for a block unless get_switch_int_data is actually called.

fn apply_switch_int_edge_effect( &mut self, _data: &mut Self::SwitchIntData, _state: &mut Self::Domain, _edge: SwitchIntTarget, )

See comments on get_switch_int_data.

fn iterate_to_fixpoint<'mir>( self, tcx: TyCtxt<'tcx>, body: &'mir Body<'tcx>, pass_name: Option<&'static str>, ) -> Results<'tcx, Self>

where Self: Sized, Self::Domain: DebugWithContext<Self>,

Finds the fixpoint for this dataflow problem.

You shouldn’t need to override this. Its purpose is to enable method chaining like so:

let results = MyAnalysis::new(tcx, body)
    .iterate_to_fixpoint(tcx, body, None)
    .into_results_cursor(body);

You can optionally add a pass_name to the graphviz output for this particular run of a dataflow analysis. Some analyses are run multiple times in the compilation pipeline. Without a pass_name to differentiates them, only the results for the latest run will be saved.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a>

const NAME: &'static str = "transitive liveness"

type Domain = BitSet<Local>

type Direction = Backward

impl<'a, 'tcx> Analysis<'tcx> for MaybeStorageDead<'a>

const NAME: &'static str = "maybe_storage_dead"

type Domain = BitSet<Local>

impl<'a, 'tcx> Analysis<'tcx> for MaybeStorageLive<'a>

const NAME: &'static str = "maybe_storage_live"

type Domain = BitSet<Local>

impl<'tcx> Analysis<'tcx> for MaybeBorrowedLocals

const NAME: &'static str = "maybe_borrowed_locals"

type Domain = BitSet<Local>

impl<'tcx> Analysis<'tcx> for EverInitializedPlaces<'_, 'tcx>

const NAME: &'static str = "ever_init"

type Domain = MixedBitSet<InitIndex>

impl<'tcx> Analysis<'tcx> for MaybeInitializedPlaces<'_, 'tcx>

const NAME: &'static str = "maybe_init"

type Domain = MaybeReachable<MixedBitSet<MovePathIndex>>

type SwitchIntData = MaybePlacesSwitchIntData<'tcx>

impl<'tcx> Analysis<'tcx> for MaybeUninitializedPlaces<'_, 'tcx>

const NAME: &'static str = "maybe_uninit"

type Domain = MixedBitSet<MovePathIndex>

type SwitchIntData = MaybePlacesSwitchIntData<'tcx>

impl<'tcx> Analysis<'tcx> for MaybeLiveLocals

const NAME: &'static str = "liveness"

type Domain = BitSet<Local>

type Direction = Backward

impl<'tcx> Analysis<'tcx> for MaybeRequiresStorage<'_, 'tcx>

const NAME: &'static str = "requires_storage"

type Domain = BitSet<Local>