sdfg::analysis::ForwardStructuredDataFlowAnalysis< State > Class Template Reference

Base class for forward data-flow analysis over structured control flow. More...

#include <sdfg/analysis/structured_data_flow_analysis.h>

Classes
struct	SolveProgress

Public Types
using	ExposedType = typename State::ExposedType

Public Member Functions
virtual	~ForwardStructuredDataFlowAnalysis ()=default
void	run_forward (structured_control_flow::Sequence &root)
	Run the analysis starting from the given root sequence.
const State &	state (const structured_control_flow::ControlFlowNode &node) const
	Retrieve the computed data-flow state for a node.
bool	has_state (const structured_control_flow::ControlFlowNode &node) const

Protected Member Functions
State &	get_or_create_state (const structured_control_flow::ControlFlowNode &node)
virtual std::unique_ptr< State >	create_initial_state (const structured_control_flow::ControlFlowNode &node)=0
virtual ExposedType	boundary ()
	Provide the initial set flowing into the root.

Detailed Description

template<typename State>
class sdfg::analysis::ForwardStructuredDataFlowAnalysis< State >

Base class for forward data-flow analysis over structured control flow.

The analysis walks the structured CFG tree (Sequence, Block, IfElse, StructuredLoop, While, Return, Break, Continue) in forward order and propagates sets of instances of type T using the classic gen/kill framework:

out(n) = gen(n) ∪ (in(n) − kill(n))

Merge at join points (after IfElse branches, loop back-edges) is performed by the virtual merge function which defaults to set union.

Usage:

1. Derive per-node State from DataFlowState<T> or ElementIdMapDataFlowState 1a. Pick the container T that will represent the live sets between the per-node states 1b. implement the static functions empty_in() and merge(a, b, MergeMode) on the DataFlowState impl.
2. Derive from ForwardDataFlowAnalysis<YourStateType>.
3. Implement create_initial_state(node) to fill the per-node gen & kill lists
4. Optionally override boundary to provide the initial set that flows into the root of the tree.
5. Call run_forward(root_sequence). Afterwards query state(node) for any visited node.

Template Parameters

T	Element type. Must support operator< (used in std::set).

Member Typedef Documentation

ExposedType

template<typename State>

using sdfg::analysis::ForwardStructuredDataFlowAnalysis< State >::ExposedType = typename State::ExposedType

Constructor & Destructor Documentation

~ForwardStructuredDataFlowAnalysis()

template<typename State>

virtual sdfg::analysis::ForwardStructuredDataFlowAnalysis< State >::~ForwardStructuredDataFlowAnalysis ( )

virtualdefault

Member Function Documentation

boundary()

template<typename State>

virtual ExposedType sdfg::analysis::ForwardStructuredDataFlowAnalysis< State >::boundary ( )

inlineprotectedvirtual

Provide the initial set flowing into the root.

Override to seed the analysis with an initial set (e.g. function arguments that are live on entry). Default: empty set.

create_initial_state()

template<typename State>

virtual std::unique_ptr< State > sdfg::analysis::ForwardStructuredDataFlowAnalysis< State >::create_initial_state ( const structured_control_flow::ControlFlowNode & node )

protectedpure virtual

Implemented in sdfg::analysis::DataTransferEliminationAnalysis.

get_or_create_state()

template<typename State>

State & sdfg::analysis::ForwardStructuredDataFlowAnalysis< State >::get_or_create_state ( const structured_control_flow::ControlFlowNode & node )

inlineprotected

has_state()

template<typename State>

bool sdfg::analysis::ForwardStructuredDataFlowAnalysis< State >::has_state ( const structured_control_flow::ControlFlowNode & node ) const

inline

run_forward()

template<typename State>

void sdfg::analysis::ForwardStructuredDataFlowAnalysis< State >::run_forward ( structured_control_flow::Sequence & root )

inline

Run the analysis starting from the given root sequence.

Parameters

root	Typically sdfg.root().

state()

template<typename State>

const State & sdfg::analysis::ForwardStructuredDataFlowAnalysis< State >::state ( const structured_control_flow::ControlFlowNode & node ) const

inline

Retrieve the computed data-flow state for a node.

Parameters

node	A node that was visited during run.

Returns

Reference to its DataFlowState (in/out sets).

---

The documentation for this class was generated from the following file:

• opt/include/sdfg/analysis/structured_data_flow_analysis.h