Struct SparseDataFlowAnalysis 

pub struct SparseDataFlowAnalysis<A, D> { /* private fields */ }

This type provides an AnalysisStrategy for sparse data-flow analyses.

In short, it implements the DataFlowAnalysis trait, and handles all of the boilerplate that any well-structured sparse data-flow analysis requires. Analyses can make use of this strategy by implementing one of the sparse data-flow analysis traits, which SparseDataFlowAnalysis will use to delegate analysis-specific details to the analysis implementation. The two traits are:

• SparseForwardDataFlowAnalysis, for forward-propagating sparse analyses
• SparseBackwardDataFlowAnalysis, for backward-propagating sparse analyses

What is a sparse analysis?

A sparse data-flow analysis is one which associates analysis state with SSA value definitions, in order to represent known facts about those values, either as a result of deriving them from previous values used as operands of the defining operation (forward analysis), or as a result of deriving them based on how the value is used along all possible paths that execution might take (backward analysis). The state associated with a value does not change as a program executes, it is fixed at the value definition, derived only from the states of other values and the defining op itself.

This is in contrast to dense data-flow analysis, which associates state with program points, which then evolves as the program executes. This is also where the distinction between dense and sparse comes from - program points are dense, while SSA value definitions are sparse (insofar as the state associated with an SSA value only ever occurs once, while states associated with program points are duplicated at each point).

Some examples of sparse analyses:

• Constant propagation - if a value is determined to be constant, the constant value is the state associated with a given value definition. This determination is made based on the semantics of an operation and its operands (i.e. if an operation can be constant-folded, then the results of that operation are themselves constant). This is a forward analysis.
• Dead value analysis - determines whether or not a value is ever used. This is a backward analysis, as it propagates uses to definitions. In our IR, we do not require this analysis, as it is implicit in the use-def graph, however the concept is what we’re interested in here.

Usage

This type is meant to be used indirectly, as an AnalysisStrategy implementation, rather than directly as a DataFlowAnalysis implementation, as shown below:

use midenc_hir::dataflow::*;

#[derive(Default)]
pub struct MyAnalysis;
impl BuildableDataFlowAnalysis for MyAnalysis {
    type Strategy = SparseDataFlowAnalysis<Self, Forward>;

    fn new(_solver: &mut DataFlowSolver) -> Self {
        Self
    }
}
impl SparseForwardDataFlowAnalysis for MyAnalysis {
    type Lattice = Lattice<u32>;

    //...
}

The above permits us to load MyAnalysis into a DataFlowSolver without ever mentioning the SparseDataFlowAnalysis type at all, like so:

let mut solver = DataFlowSolver::default();
solver.load::<MyAnalysis>();
solver.initialize_and_run(&op, analysis_manager);

Trait Implementations

impl<A: SparseBackwardDataFlowAnalysis> AnalysisStrategy<A> for SparseDataFlowAnalysis<A, Backward>

type Direction = Backward

The direction in which analysis state is propagated (forward vs backward) by this analysis.

type Kind = Sparse

The kind (dense vs sparse) of the analysis being performed

fn build(analysis: A, _solver: &mut DataFlowSolver) -> Self

Construct a valid DataFlowAnalysis instance using this strategy, by providing an instance of the underlying analysis type.

impl<A: SparseForwardDataFlowAnalysis> AnalysisStrategy<A> for SparseDataFlowAnalysis<A, Forward>

type Direction = Forward

The direction in which analysis state is propagated (forward vs backward) by this analysis.

type Kind = Sparse

The kind (dense vs sparse) of the analysis being performed

fn build(analysis: A, _solver: &mut DataFlowSolver) -> Self

Construct a valid DataFlowAnalysis instance using this strategy, by providing an instance of the underlying analysis type.

impl<A: SparseBackwardDataFlowAnalysis> DataFlowAnalysis for SparseDataFlowAnalysis<A, Backward>

fn initialize( &self, top: &Operation, solver: &mut DataFlowSolver, _analysis_manager: AnalysisManager, ) -> Result<(), Report>

Initialize the analysis by visiting the operation and everything nested under it.

fn visit( &self, point: &ProgramPoint, solver: &mut DataFlowSolver, ) -> Result<(), Report>

Visit a program point.

If it is after call operation or an operation with block or region control-flow, then operand lattices are set accordingly. Otherwise, invokes the operation transfer function.

fn debug_name(&self) -> &'static str

A friendly name for this analysis in diagnostics

fn analysis_id(&self) -> TypeId

The unique type identifier of the concrete analysis type.

impl<A: SparseForwardDataFlowAnalysis> DataFlowAnalysis for SparseDataFlowAnalysis<A, Forward>

fn initialize( &self, top: &Operation, solver: &mut DataFlowSolver, _analysis_manager: AnalysisManager, ) -> Result<(), Report>

Initialize the analysis by visiting every owner of an SSA value: all operations and blocks.

fn visit( &self, point: &ProgramPoint, solver: &mut DataFlowSolver, ) -> Result<(), Report>

Visit a program point.

If this is at beginning of block and all control-flow predecessors or callsites are known, then the arguments lattices are propagated from them. If this is after call operation or an operation with region control-flow, then its result lattices are set accordingly. Otherwise, the operation transfer function is invoked.

fn debug_name(&self) -> &'static str

A friendly name for this analysis in diagnostics

fn analysis_id(&self) -> TypeId

The unique type identifier of the concrete analysis type.

impl<A: SparseBackwardDataFlowAnalysis> SparseBackwardDataFlowAnalysis for SparseDataFlowAnalysis<A, Backward>

type Lattice = <A as SparseBackwardDataFlowAnalysis>::Lattice

fn debug_name(&self) -> &'static str

fn visit_operation( &self, op: &Operation, operands: &mut [AnalysisStateGuardMut<'_, Self::Lattice>], results: &[AnalysisStateGuard<'_, Self::Lattice>], solver: &mut DataFlowSolver, ) -> Result<(), Report>

The operation transfer function.

fn set_to_exit_state( &self, lattice: &mut AnalysisStateGuardMut<'_, Self::Lattice>, )

Set the given lattice element(s) at control flow exit point(s).

fn visit_call_operand( &self, operand: &OpOperandImpl, solver: &mut DataFlowSolver, )

Visit operands on call instructions that are not forwarded.

fn visit_external_call( &self, call: &dyn CallOpInterface, arguments: &mut [AnalysisStateGuardMut<'_, Self::Lattice>], results: &[AnalysisStateGuard<'_, Self::Lattice>], solver: &mut DataFlowSolver, )

The transfer function for calls to external functions.

fn visit_branch_operand( &self, operand: &OpOperandImpl, solver: &mut DataFlowSolver, )

Visit operands on branch instructions that are not forwarded.

impl<A: SparseForwardDataFlowAnalysis> SparseForwardDataFlowAnalysis for SparseDataFlowAnalysis<A, Forward>

type Lattice = <A as SparseForwardDataFlowAnalysis>::Lattice

fn debug_name(&self) -> &'static str

fn visit_operation( &self, op: &Operation, operands: &[AnalysisStateGuard<'_, Self::Lattice>], results: &mut [AnalysisStateGuardMut<'_, Self::Lattice>], solver: &mut DataFlowSolver, ) -> Result<(), Report>

The operation transfer function.

fn set_to_entry_state( &self, lattice: &mut AnalysisStateGuardMut<'_, Self::Lattice>, )

Set the given lattice element(s) at control flow entry point(s).

fn visit_external_call( &self, call: &dyn CallOpInterface, arguments: &[AnalysisStateGuard<'_, Self::Lattice>], results: &mut [AnalysisStateGuardMut<'_, Self::Lattice>], solver: &mut DataFlowSolver, )

The transfer function for calls to external functions.

fn visit_non_control_flow_arguments( &self, op: &Operation, successor: &RegionSuccessor<'_>, arguments: &mut [AnalysisStateGuardMut<'_, Self::Lattice>], first_index: usize, solver: &mut DataFlowSolver, )

Given an operation with region control-flow, the lattices of the operands, and a region successor, compute the lattice values for block arguments that are not accounted for by the branching control flow (ex. the bounds of loops).