Non-destructive detection of einsum clusters in a StructuredSDFG. More...

#include <sdfg/einsum/einsum_detection.h>

Inheritance diagram for sdfg::einsum::EinsumDetection:

Classes
struct	BlockState
struct	LoopScopeState

Public Member Functions
	EinsumDetection ()=default
void	find_einsum_core_ops (BlockState &state, structured_control_flow::Block &block)
	Loop for operations (reductions) that can form the core of einsum clusters.
void	consume_input_operations (BlockState &state)
	for all the clusters of the block last scanned into BlockState, try to consume all the input operations that feed into them and are still unconsumed, and add them to the clusters.
bool	try_to_consume_loop (EinsumCluster &einsum, structured_control_flow::StructuredLoop &loop)
	If there is a cluster representing the full contents of the loop, try to have it consume this loop.
void	filter_for_coverage ()
size_t	run (structured_control_flow::ControlFlowNode &start)
	Run detection starting from the given control flow node.
const std::vector< std::unique_ptr< EinsumCluster > > &	einsums () const
	All einsum clusters found during the last run.
bool	visit (structured_control_flow::Block &node) override
bool	visit (structured_control_flow::AssignmentBlock &node) override
bool	visit (structured_control_flow::IfElse &node) override
bool	visit (structured_control_flow::While &node) override
bool	visit (structured_control_flow::Return &node) override
bool	handleStructuredLoop (structured_control_flow::StructuredLoop &loop) override
bool	visit (sdfg::structured_control_flow::ControlFlowNode &node)
virtual bool	visit (sdfg::structured_control_flow::Sequence &node)
virtual bool	visit (sdfg::structured_control_flow::For &node)
virtual bool	visit (sdfg::structured_control_flow::Map &node)
virtual bool	visit (sdfg::structured_control_flow::Reduce &node)
virtual bool	visit (sdfg::structured_control_flow::Continue &node)
virtual bool	visit (sdfg::structured_control_flow::Break &node)
Public Member Functions inherited from sdfg::visitor::ActualStructuredSDFGVisitor
	ActualStructuredSDFGVisitor ()
virtual	~ActualStructuredSDFGVisitor ()=default
bool	visit (sdfg::structured_control_flow::ControlFlowNode &node)
bool	dispatch (sdfg::structured_control_flow::ControlFlowNode &node)

Protected Member Functions
EinsumCluster &	new_cluster (structured_control_flow::Block &block)
EinsumCluster *	try_lift (structured_control_flow::Block &block, data_flow::Tasklet &tasklet)
	Try to lift a reduction tasklet into a fresh einsum cluster core.
EinsumCluster *	from_einsum_node (structured_control_flow::Block &block, EinsumNode &einsum_node)
	Mirror an already existing EinsumNode into a cluster.
PromotionCheck	can_promote (EinsumCluster &cluster, structured_control_flow::StructuredLoop &loop)
	Verify the loop can be folded and return the new dimension's per-operand contributions.
void	apply_promote (EinsumCluster &cluster, structured_control_flow::StructuredLoop &loop, const PromotionCheck &check)
void	recompute_einsum_indices (EinsumCluster &cluster)
	Recompute the per-operand inner-index mappings from the current dims and subsets.
bool	block_fully_consumed (BlockState &state, structured_control_flow::Block &block)
void	register_cluster_in_scope (EinsumCluster *cluster)

Static Protected Member Functions
static bool	subsets_eq (const data_flow::Subset &subset1, const data_flow::Subset &subset2)
static bool	try_extend (BlockState &state, EinsumCluster &cluster)
	Try to fold a multiplication feeding an input into the cluster. Returns true if applied.
static symbolic::Expression	cnf_to_upper_bound (const symbolic::CNF &cnf, const symbolic::Symbol indvar)
static bool	subset_contains_symbol (const data_flow::Subset &subset, const symbolic::Symbol &symbol)

Protected Attributes
std::vector< std::unique_ptr< EinsumCluster > >	all_einsums_
	all that have been found
std::vector< LoopScopeState >	loop_stack_
	those that are relevant to the current scope.

Detailed Description

Non-destructive detection of einsum clusters in a StructuredSDFG.

Traverses the graph from a user-chosen starting point, builds the loop stack and tries to represent each Block of dataflow with a single EinsumCluster. If a loop scope only contains a single EinsumCluster and no other operation, the loop is folded into that cluster on the way out of the scope.

The SDFG is never modified.

Constructor & Destructor Documentation

◆ EinsumDetection()

sdfg::einsum::EinsumDetection::EinsumDetection ( )

default

Member Function Documentation

◆ apply_promote()

void sdfg::einsum::EinsumDetection::apply_promote	(	EinsumCluster &	cluster,
		structured_control_flow::StructuredLoop &	loop,
		const PromotionCheck &	check )

protected

◆ block_fully_consumed()

bool sdfg::einsum::EinsumDetection::block_fully_consumed	(	BlockState &	state,
		structured_control_flow::Block &	block )

protected

◆ can_promote()

PromotionCheck sdfg::einsum::EinsumDetection::can_promote	(	EinsumCluster &	cluster,
		structured_control_flow::StructuredLoop &	loop )

protected

Verify the loop can be folded and return the new dimension's per-operand contributions.

◆ cnf_to_upper_bound()

symbolic::Expression sdfg::einsum::EinsumDetection::cnf_to_upper_bound	(	const symbolic::CNF &	cnf,
		const symbolic::Symbol	indvar )

staticprotected

◆ consume_input_operations()

void sdfg::einsum::EinsumDetection::consume_input_operations ( BlockState & state )

for all the clusters of the block last scanned into BlockState, try to consume all the input operations that feed into them and are still unconsumed, and add them to the clusters.

◆ einsums()

const std::vector< std::unique_ptr< EinsumCluster > > & sdfg::einsum::EinsumDetection::einsums ( ) const

inline

All einsum clusters found during the last run.

◆ filter_for_coverage()

void sdfg::einsum::EinsumDetection::filter_for_coverage ( )

◆ find_einsum_core_ops()

void sdfg::einsum::EinsumDetection::find_einsum_core_ops	(	BlockState &	state,
		structured_control_flow::Block &	block )

Loop for operations (reductions) that can form the core of einsum clusters.

◆ from_einsum_node()

EinsumCluster * sdfg::einsum::EinsumDetection::from_einsum_node	(	structured_control_flow::Block &	block,
		EinsumNode &	einsum_node )

protected

Mirror an already existing EinsumNode into a cluster.

◆ handleStructuredLoop()

bool sdfg::einsum::EinsumDetection::handleStructuredLoop ( structured_control_flow::StructuredLoop & loop )

overridevirtual

Reimplemented from sdfg::visitor::ActualStructuredSDFGVisitor.

◆ new_cluster()

EinsumCluster & sdfg::einsum::EinsumDetection::new_cluster ( structured_control_flow::Block & block )

protected

◆ recompute_einsum_indices()

void sdfg::einsum::EinsumDetection::recompute_einsum_indices ( EinsumCluster & cluster )

protected

Recompute the per-operand inner-index mappings from the current dims and subsets.

◆ register_cluster_in_scope()

void sdfg::einsum::EinsumDetection::register_cluster_in_scope ( EinsumCluster * cluster )

protected

◆ run()

size_t sdfg::einsum::EinsumDetection::run ( structured_control_flow::ControlFlowNode & start )

Run detection starting from the given control flow node.

◆ subset_contains_symbol()

bool sdfg::einsum::EinsumDetection::subset_contains_symbol	(	const data_flow::Subset &	subset,
		const symbolic::Symbol &	symbol )

staticprotected

◆ subsets_eq()

bool sdfg::einsum::EinsumDetection::subsets_eq	(	const data_flow::Subset &	subset1,
		const data_flow::Subset &	subset2 )

staticprotected

◆ try_extend()

bool sdfg::einsum::EinsumDetection::try_extend	(	BlockState &	state,
		EinsumCluster &	cluster )

staticprotected

Try to fold a multiplication feeding an input into the cluster. Returns true if applied.

◆ try_lift()

EinsumCluster * sdfg::einsum::EinsumDetection::try_lift	(	structured_control_flow::Block &	block,
		data_flow::Tasklet &	tasklet )

protected

Try to lift a reduction tasklet into a fresh einsum cluster core.

◆ try_to_consume_loop()

bool sdfg::einsum::EinsumDetection::try_to_consume_loop	(	EinsumCluster &	einsum,
		structured_control_flow::StructuredLoop &	loop )

If there is a cluster representing the full contents of the loop, try to have it consume this loop.

Parameters

state
loop

Returns: true if the loop was successfully consumed by the cluster, false otherwise.

◆ visit() [1/12]

virtual bool sdfg::visitor::ActualStructuredSDFGVisitor::visit ( sdfg::structured_control_flow::Break & node )

virtual

Reimplemented from sdfg::visitor::ActualStructuredSDFGVisitor.

◆ visit() [2/12]

virtual bool sdfg::visitor::ActualStructuredSDFGVisitor::visit ( sdfg::structured_control_flow::Continue & node )

virtual

◆ all_einsums_

std::vector<std::unique_ptr<EinsumCluster> > sdfg::einsum::EinsumDetection::all_einsums_

protected

all that have been found

◆ loop_stack_

std::vector<LoopScopeState> sdfg::einsum::EinsumDetection::loop_stack_

protected

those that are relevant to the current scope.

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

opt/include/sdfg/einsum/einsum_detection.h

Classes

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ EinsumDetection()

Member Function Documentation

◆ apply_promote()

◆ block_fully_consumed()

◆ can_promote()

◆ cnf_to_upper_bound()

◆ consume_input_operations()

◆ einsums()

◆ filter_for_coverage()

◆ find_einsum_core_ops()

◆ from_einsum_node()

◆ handleStructuredLoop()

◆ new_cluster()

◆ recompute_einsum_indices()

◆ register_cluster_in_scope()

◆ run()

◆ subset_contains_symbol()

◆ subsets_eq()

◆ try_extend()

◆ try_lift()

◆ try_to_consume_loop()

◆ visit() [1/12]

◆ visit() [2/12]

◆ visit() [3/12]

◆ visit() [4/12]

◆ visit() [5/12]

◆ visit() [6/12]

◆ visit() [7/12]

◆ visit() [8/12]

◆ visit() [9/12]

◆ visit() [10/12]

◆ visit() [11/12]

◆ visit() [12/12]

Member Data Documentation

◆ all_einsums_

◆ loop_stack_