Rewrites loop-carried scalar recurrences into closed-form expressions. More...

#include <sdfg/passes/symbolic/symbol_evolution.h>

Inheritance diagram for sdfg::passes::SymbolEvolution:

Public Member Functions
	SymbolEvolution ()
	Constructs a new SymbolEvolution pass instance.
std::string	name () override
	Returns the name of this pass.
virtual bool	run_pass (builder::StructuredSDFGBuilder &builder, analysis::AnalysisManager &analysis_manager) override
	Runs the symbol evolution pass on the given SDFG.
Public Member Functions inherited from sdfg::passes::Pass
	Pass ()=default
	Pass (const Options &options)
virtual	~Pass ()=default
virtual std::vector< OptionSpec >	options ()
bool	run (builder::SDFGBuilder &builder, bool create_report=false)
bool	run (builder::StructuredSDFGBuilder &builder, analysis::AnalysisManager &analysis_manager, bool create_report=false)
virtual bool	run_pass (builder::SDFGBuilder &builder)
virtual void	invalidates (analysis::AnalysisManager &analysis_manager, bool applied)

Additional Inherited Members
Protected Member Functions inherited from sdfg::passes::Pass
template<class T>
T	option (const OptionKey< T > &key, T fallback=T{}) const

Detailed Description

Rewrites loop-carried scalar recurrences into closed-form expressions.

For every structured loop the pass identifies integer-scalar symbols whose body update can be modelled as the affine recurrence

sym_{n+1} = a * sym_n + b * indvar_n + c     (a, b, c loop-invariant)

and rewrites them so the body redefines the symbol from the induction variable directly. This breaks loop-carried dependencies and exposes the symbol as an affine function of the induction variable to downstream polyhedral / memlet analyses.

Solvable recurrence classes:

a == 1, b == 0 (accumulator): closed(i) = sym_init + c * (i - init) / stride
a == 0 (function of i): closed(i) = b * (i - stride) + c

Loops are processed innermost-first; each loop is rewritten to a fixpoint, with analyses invalidated between rewrites because each rewrite mutates the IR.

Constructor & Destructor Documentation

◆ SymbolEvolution()

sdfg::passes::SymbolEvolution::SymbolEvolution ( )

Constructs a new SymbolEvolution pass instance.

Member Function Documentation

◆ name()

std::string sdfg::passes::SymbolEvolution::name ( )

overridevirtual

Returns the name of this pass.

Returns: "SymbolEvolution"

Implements sdfg::passes::Pass.

◆ run_pass()

virtual bool sdfg::passes::SymbolEvolution::run_pass	(	builder::StructuredSDFGBuilder &	builder,
		analysis::AnalysisManager &	analysis_manager )

overridevirtual

Runs the symbol evolution pass on the given SDFG.

Traverses all structured loops in the SDFG and attempts to derive closed-form expressions for loop-dependent scalar symbols.

Parameters

builder	The SDFG builder providing access to the graph
analysis_manager	The analysis manager for running required analyses

Returns: true if the pass modified the SDFG, false otherwise

Reimplemented from sdfg::passes::Pass.

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

sdfg/include/sdfg/passes/symbolic/symbol_evolution.h