Standalone loop-carried dependency analysis. More...

#include <sdfg/parallelization/analysis/loop_carried_dependency_analysis.h>

Inheritance diagram for sdfg::parallelization::LoopCarriedDependencyAnalysis:

Public Member Functions
	LoopCarriedDependencyAnalysis (StructuredSDFG &sdfg)
std::string	name () const override
void	run (analysis::AnalysisManager &analysis_manager) override
	Only records the analysis manager; results are computed on demand per loop.
bool	available (structured_control_flow::StructuredLoop &loop)
	Whether the loop can be analyzed (monotonic, with boundary information).
const std::unordered_map< std::string, LoopCarriedDependencyInfo > &	dependencies (structured_control_flow::StructuredLoop &loop)
	Per-container summary of loop-carried dependencies for a loop.
const std::vector< LoopCarriedDependencyPair > &	pairs (structured_control_flow::StructuredLoop &loop)
	Per-pair list of loop-carried dependencies for a loop.
std::vector< const LoopCarriedDependencyPair * >	pairs_between (structured_control_flow::StructuredLoop &loop, const structured_control_flow::ControlFlowNode &subtree_a, const structured_control_flow::ControlFlowNode &subtree_b)
	Filter pairs(loop) to those whose writer lies in subtree_a and reader lies in subtree_b (or vice versa for WAW between two writes).
bool	has_loop_carried (structured_control_flow::StructuredLoop &loop)
	True if any loop-carried dependency exists for the loop.
bool	has_loop_carried_raw (structured_control_flow::StructuredLoop &loop)
	True if any loop-carried RAW dependency exists for the loop.
bool	has_loop_carried_hazard (structured_control_flow::StructuredLoop &loop)
	True if RAW or undefined loop-carried dependency exists.
const std::vector< structured_control_flow::ReductionInfo > &	reductions (structured_control_flow::StructuredLoop &loop)
	Recognized reductions carried by the loop.
bool	has_reductions (structured_control_flow::StructuredLoop &loop)
	True if the loop carries at least one recognized reduction.
bool	is_reduction_only (structured_control_flow::StructuredLoop &loop)
	True if every loop-carried hazard (RAW or undefined) of the loop is a recognized reduction, and at least one reduction exists.
Public Member Functions inherited from sdfg::analysis::Analysis
	Analysis (StructuredSDFG &sdfg)
	Analysis (StructuredSDFG &sdfg, const Options &options)
virtual	~Analysis ()=default
virtual bool	invalidate (structured_control_flow::ControlFlowNode &changed)
	Updates the analysis after a change confined to the subtree of `changed`.
	Analysis (const Analysis &a)=delete
Analysis &	operator= (const Analysis &)=delete

Friends
class	analysis::AnalysisManager

Additional Inherited Members
Protected Member Functions inherited from sdfg::analysis::Analysis
template<class T>
T	option (const OptionKey< T > &key, T fallback=T{}) const
Protected Attributes inherited from sdfg::analysis::Analysis
StructuredSDFG &	sdfg_
symbolic::Assumptions	additional_assumptions_
const Options *	options_ = &Options::empty()

Detailed Description

Standalone loop-carried dependency analysis.

Computes per-loop loop-carried (cross-iteration) dependencies by consuming DataDependencyAnalysis's per-loop boundary snapshots (upward-exposed reads and escaping definitions) and pairing them with symbolic::maps::dependence_deltas.

For a loop L with induction variable i_L: pairs(L) = { (W,R, RAW, Δ_L(W,R)) : W ∈ esc(L), R ∈ ue(L), cont(W) = cont(R), Δ ≠ ∅ } ∪ { (W₁,W₂, WAW, Δ_L(W₁,W₂)) : W₁,W₂ ∈ esc(L), cont(W₁) = cont(W₂), Δ ≠ ∅ }

Results are computed lazily on the first query for a loop and cached until the analysis is invalidated. The data dependency analysis runs once per outermost loop nest and serves all loops in it; dependence distances and reductions are computed per queried loop.

Constructor & Destructor Documentation

◆ LoopCarriedDependencyAnalysis()

sdfg::parallelization::LoopCarriedDependencyAnalysis::LoopCarriedDependencyAnalysis ( StructuredSDFG & sdfg )

Member Function Documentation

◆ available()

bool sdfg::parallelization::LoopCarriedDependencyAnalysis::available ( structured_control_flow::StructuredLoop & loop )

Whether the loop can be analyzed (monotonic, with boundary information).

◆ dependencies()

const std::unordered_map< std::string, LoopCarriedDependencyInfo > & sdfg::parallelization::LoopCarriedDependencyAnalysis::dependencies ( structured_control_flow::StructuredLoop & loop )

Per-container summary of loop-carried dependencies for a loop.

Returns a map from container name to the (kind, merged delta-set) for each container that participates in any loop-carried dependency.

◆ has_loop_carried()

bool sdfg::parallelization::LoopCarriedDependencyAnalysis::has_loop_carried ( structured_control_flow::StructuredLoop & loop )

True if any loop-carried dependency exists for the loop.

◆ has_loop_carried_hazard()

bool sdfg::parallelization::LoopCarriedDependencyAnalysis::has_loop_carried_hazard ( structured_control_flow::StructuredLoop & loop )

True if RAW or undefined loop-carried dependency exists.

Either is a hazard for example for For2Map / parallization

◆ has_loop_carried_raw()

bool sdfg::parallelization::LoopCarriedDependencyAnalysis::has_loop_carried_raw ( structured_control_flow::StructuredLoop & loop )

True if any loop-carried RAW dependency exists for the loop.

◆ has_reductions()

bool sdfg::parallelization::LoopCarriedDependencyAnalysis::has_reductions ( structured_control_flow::StructuredLoop & loop )

True if the loop carries at least one recognized reduction.

◆ is_reduction_only()

bool sdfg::parallelization::LoopCarriedDependencyAnalysis::is_reduction_only ( structured_control_flow::StructuredLoop & loop )

True if every loop-carried hazard (RAW or undefined) of the loop is a recognized reduction, and at least one reduction exists.

This is the precise condition under which a parallelizable For is a reduction loop rather than a fully independent (Map) loop: the only cross-iteration dependencies are reorderable accumulations.

◆ name()

std::string sdfg::parallelization::LoopCarriedDependencyAnalysis::name ( ) const

inlineoverridevirtual

Implements sdfg::analysis::Analysis.

◆ pairs()

const std::vector< LoopCarriedDependencyPair > & sdfg::parallelization::LoopCarriedDependencyAnalysis::pairs ( structured_control_flow::StructuredLoop & loop )

Per-pair list of loop-carried dependencies for a loop.

◆ pairs_between()

std::vector< const LoopCarriedDependencyPair * > sdfg::parallelization::LoopCarriedDependencyAnalysis::pairs_between	(	structured_control_flow::StructuredLoop &	loop,
		const structured_control_flow::ControlFlowNode &	subtree_a,
		const structured_control_flow::ControlFlowNode &	subtree_b )

Filter pairs(loop) to those whose writer lies in subtree_a and reader lies in subtree_b (or vice versa for WAW between two writes).

Useful for transformations like LoopDistribute that need to ask whether any cross-iteration dependency crosses a particular partition boundary.

◆ reductions()

const std::vector< structured_control_flow::ReductionInfo > & sdfg::parallelization::LoopCarriedDependencyAnalysis::reductions ( structured_control_flow::StructuredLoop & loop )

Recognized reductions carried by the loop.

Each entry pairs an associative/commutative operator with the accumulator container it combines into. A container appears here iff it has a loop-carried read-write dependency that is realized by a single combine operator (acc = acc OP x) over a loop-invariant accumulator location. Empty for loops with no recognized reduction.

◆ run()

void sdfg::parallelization::LoopCarriedDependencyAnalysis::run ( analysis::AnalysisManager & analysis_manager )

overridevirtual

Only records the analysis manager; results are computed on demand per loop.

Implements sdfg::analysis::Analysis.

◆ analysis::AnalysisManager

friend class analysis::AnalysisManager

friend

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

opt/include/sdfg/parallelization/analysis/loop_carried_dependency_analysis.h

Public Member Functions

Friends

Additional Inherited Members