sdfg::structured_control_flow::StructuredLoop Class Reference

Base class for structured loop constructs. More...

#include <sdfg/structured_control_flow/structured_loop.h>

Inheritance diagram for sdfg::structured_control_flow::StructuredLoop:

Public Member Functions
virtual	~StructuredLoop ()=default
	StructuredLoop (const StructuredLoop &node)=delete
StructuredLoop &	operator= (const StructuredLoop &)=delete
void	validate (const Function &function) const override
	Validates the element.
const symbolic::Symbol	indvar () const
	Get the induction variable (loop counter) symbol.
const symbolic::Expression	init () const
	Get the initialization expression for the induction variable.
const symbolic::Expression	update () const
	Get the update expression for the induction variable.
const symbolic::Condition	condition () const
	Get the loop continuation condition.
Sequence &	root () const
	Access the loop body sequence.
const ScheduleType &	schedule_type () const
	Get the scheduling strategy for this Map.
void	replace (const symbolic::Expression old_expression, const symbolic::Expression new_expression) override
	Replace occurrences of an expression in loop parameters and body.
void	replace (const symbolic::ExpressionMapping &replacements) override
symbolic::Integer	stride () const
	Describes the stride of a loop's update as a constant.
bool	is_contiguous () const
	Checks if the loop has a positive unit stride (i.e., update is indvar + 1).
bool	is_monotonic () const
	Checks if the loop is monotonic (i.e., stride is a positive integer).
symbolic::Expression	canonical_bound () const
	Describes the bound of a loop as a closed-form expression.
symbolic::Expression	canonical_bound_upper () const
	Describes the upper bound of a loop (for positive stride).
symbolic::Expression	canonical_bound_lower () const
	Describes the lower bound of a loop (for negative stride).
symbolic::Expression	num_iterations () const
	Describes the number of iterations of a loop as a closed-form expression.
symbolic::Expression	num_iterations_approx () const
	Overapproximated (upper-bound) number of iterations.
bool	is_loop_normal_form () const
	Checks if the loop is in a normal form.
Public Member Functions inherited from sdfg::structured_control_flow::ControlFlowNode
virtual bool	accept (visitor::ActualStructuredSDFGVisitor &visitor)=0
virtual	~ControlFlowNode ()=default
ControlFlowNode *	get_parent ()
const ControlFlowNode *	get_parent () const
	ControlFlowNode (const ControlFlowNode &node)=delete
ControlFlowNode &	operator= (const ControlFlowNode &)=delete
Public Member Functions inherited from sdfg::Element
	Element (size_t element_id, const DebugInfo &debug_info)
virtual	~Element ()=default
size_t	element_id () const
const DebugInfo &	debug_info () const
void	set_debug_info (const DebugInfo &debug_info)
void	add_metadata (const std::string &key, const std::string &value)
void	remove_metadata (const std::string &key)
const std::string &	metadata (const std::string &key) const
const std::string *	metadata_if_exists (const std::string &key) const
const std::unordered_map< std::string, std::string > &	metadata () const
virtual ElementType	type_id () const =0
	Returns the type of the element.
std::string_view	element_type () const
	Returns the type of the element as a human-readable string.

Static Public Member Functions
static bool	classof (const Element &element)
	LLVM-style RTTI predicate: true if element is a StructuredLoop.
Static Public Member Functions inherited from sdfg::structured_control_flow::ControlFlowNode
static bool	classof (const Element &element)
	LLVM-style RTTI predicate: true if element is a ControlFlowNode.
static std::vector< ControlFlowNode * >	parent_chain (ControlFlowNode &child)

Static Public Attributes
static constexpr ElementType	TypeGroup = ElementType::For | ElementType::Map | ElementType::Reduce
	Bitmask of all concrete ElementTypes that are StructuredLoops.
Static Public Attributes inherited from sdfg::structured_control_flow::ControlFlowNode
static constexpr ElementType	TypeGroup
	Bitmask of all concrete ElementTypes that are ControlFlowNodes.

Protected Member Functions
void	reset_cache ()
symbolic::Integer	compute_stride () const
symbolic::Expression	compute_canonical_bound () const
symbolic::Expression	compute_num_iterations () const
	StructuredLoop (size_t element_id, const DebugInfo &debug_info, ControlFlowNode *parent, symbolic::Symbol indvar, symbolic::Expression init, symbolic::Expression update, symbolic::Condition condition, const ScheduleType &schedule_type=ScheduleType_Sequential::create())
Protected Member Functions inherited from sdfg::structured_control_flow::ControlFlowNode
	ControlFlowNode (size_t element_id, const DebugInfo &debug_info, ControlFlowNode *parent)
	Protected constructor for control flow nodes with parent.

Protected Attributes
symbolic::Symbol	indvar_
symbolic::Expression	init_
symbolic::Expression	update_
symbolic::Condition	condition_
std::unique_ptr< Sequence >	root_
ScheduleType	schedule_type_
std::optional< symbolic::Integer >	stride_cache_
std::optional< symbolic::Expression >	canonical_bound_cache_
std::optional< symbolic::Expression >	num_iterations_cache_
Protected Attributes inherited from sdfg::structured_control_flow::ControlFlowNode
ControlFlowNode *	parent_
Protected Attributes inherited from sdfg::Element
size_t	element_id_
DebugInfo	debug_info_
std::unordered_map< std::string, std::string >	metadata_

Static Protected Attributes
static constexpr size_t	REQUIRED_ELEMENT_IDS = 2

Friends
class	sdfg::builder::StructuredSDFGBuilder

Detailed Description

Base class for structured loop constructs.

StructuredLoop is the abstract base class for all structured loop types in a StructuredSDFG. It provides common functionality for loops with:

• An induction variable (loop counter)
• An initialization expression
• An update expression (how the induction variable changes each iteration)
• A loop condition (when to continue iterating)
• A body sequence containing the loop's control flow

Derived loop types include:

• For: Traditional for-loops with explicit initialization, condition, and update
• Map: Parallel loops that can be mapped to parallel execution

Loop Structure:

indvar = init
while (condition):
  <body sequence>
  indvar = update

The loop body is a Sequence that can contain any control flow nodes (blocks, nested loops, conditionals, etc.).

See also

For

Map

Sequence

Constructor & Destructor Documentation

StructuredLoop() [1/2]

sdfg::structured_control_flow::StructuredLoop::StructuredLoop ( size_t element_id, const DebugInfo & debug_info, ControlFlowNode * parent, symbolic::Symbol indvar, symbolic::Expression init, symbolic::Expression update, symbolic::Condition condition, const ScheduleType & schedule_type = ScheduleType_Sequential::create() )

protected

~StructuredLoop()

virtual sdfg::structured_control_flow::StructuredLoop::~StructuredLoop ( )

virtualdefault

StructuredLoop() [2/2]

sdfg::structured_control_flow::StructuredLoop::StructuredLoop ( const StructuredLoop & node )

delete

Member Function Documentation

canonical_bound()

symbolic::Expression sdfg::structured_control_flow::StructuredLoop::canonical_bound

(

)

const

Describes the bound of a loop as a closed-form expression.

Example: i <= N && i < M -> i < min(N + 1, M)

Returns

The bound of the loop as a closed-form expression, otherwise null.

canonical_bound_lower()

symbolic::Expression sdfg::structured_control_flow::StructuredLoop::canonical_bound_lower

(

)

const

Describes the lower bound of a loop (for negative stride).

Extracts the exclusive lower bound from conditions like:

• bound < i -> bound
• bound <= i -> bound - 1

Returns

The lower bound expression, or null if not extractable.

canonical_bound_upper()

symbolic::Expression sdfg::structured_control_flow::StructuredLoop::canonical_bound_upper

(

)

const

Describes the upper bound of a loop (for positive stride).

Extracts the exclusive upper bound from conditions like:

• i < N -> N
• i <= N -> N + 1
• i + offset < N -> N - offset

Returns

The upper bound expression, or null if not extractable.

classof()

bool sdfg::structured_control_flow::StructuredLoop::classof ( const Element & element )

inlinestatic

LLVM-style RTTI predicate: true if element is a StructuredLoop.

compute_canonical_bound()

symbolic::Expression sdfg::structured_control_flow::StructuredLoop::compute_canonical_bound ( ) const

protected

compute_num_iterations()

symbolic::Expression sdfg::structured_control_flow::StructuredLoop::compute_num_iterations ( ) const

protected

compute_stride()

symbolic::Integer sdfg::structured_control_flow::StructuredLoop::compute_stride ( ) const

protected

condition()

const symbolic::Condition sdfg::structured_control_flow::StructuredLoop::condition

(

)

const

Get the loop continuation condition.

Returns

Boolean expression evaluated before each iteration; loop continues while true

indvar()

const symbolic::Symbol sdfg::structured_control_flow::StructuredLoop::indvar

(

)

const

Get the induction variable (loop counter) symbol.

Returns

The loop's induction variable

init()

const symbolic::Expression sdfg::structured_control_flow::StructuredLoop::init

(

)

const

Get the initialization expression for the induction variable.

Returns

Expression evaluated to initialize the induction variable

is_contiguous()

bool sdfg::structured_control_flow::StructuredLoop::is_contiguous

(

)

const

Checks if the loop has a positive unit stride (i.e., update is indvar + 1).

Returns

True if the loop has a positive unit stride, false otherwise.

is_loop_normal_form()

bool sdfg::structured_control_flow::StructuredLoop::is_loop_normal_form

(

)

const

Checks if the loop is in a normal form.

Criteria:

• Loop starts from zero
• Loop has positive unit stride (i + 1)
• Loop has canonical bound

is_monotonic()

bool sdfg::structured_control_flow::StructuredLoop::is_monotonic

(

)

const

Checks if the loop is monotonic (i.e., stride is a positive integer).

Returns

True if the loop is monotonic, false otherwise.

num_iterations()

symbolic::Expression sdfg::structured_control_flow::StructuredLoop::num_iterations

(

)

const

Describes the number of iterations of a loop as a closed-form expression.

Returns

The number of iterations of the loop as a closed-form expression, otherwise null.

num_iterations_approx()

symbolic::Expression sdfg::structured_control_flow::StructuredLoop::num_iterations_approx

(

)

const

Overapproximated (upper-bound) number of iterations.

Same formula as num_iterations, but applies symbolic::overapproximate to the numerator before dividing by the stride. This collapses tile-style patterns where the canonical bound is a min(...) containing the loop's init expression. For example, with init = k_tile0 and condition k < k_tile0 + 8 && k < 500, num_iterations returns max(0, min(500 - k_tile0, 8)) while this helper returns the constant 8.

The returned expression is always >= num_iterations for all symbol valuations. Use this when a conservative integer upper bound is needed (e.g. tile sizing, working-set estimates) and the exact symbolic form is not required.

Returns

An expression that upper-bounds the iteration count, otherwise null.

operator=()

StructuredLoop & sdfg::structured_control_flow::StructuredLoop::operator= ( const StructuredLoop & )

delete

replace() [1/2]

void sdfg::structured_control_flow::StructuredLoop::replace ( const symbolic::Expression old_expression, const symbolic::Expression new_expression )

overridevirtual

Replace occurrences of an expression in loop parameters and body.

Parameters

old_expression	Expression to replace
new_expression	Expression to replace with

Implements sdfg::Element.

replace() [2/2]

void sdfg::structured_control_flow::StructuredLoop::replace ( const symbolic::ExpressionMapping & replacements )

overridevirtual

Reimplemented from sdfg::Element.

reset_cache()

void sdfg::structured_control_flow::StructuredLoop::reset_cache ( )

protected

root()

Sequence & sdfg::structured_control_flow::StructuredLoop::root

(

)

const

Access the loop body sequence.

Returns

Reference to the sequence containing the loop body

schedule_type()

const ScheduleType & sdfg::structured_control_flow::StructuredLoop::schedule_type

(

)

const

Get the scheduling strategy for this Map.

Returns

The schedule type (sequential, parallel, etc.)

stride()

symbolic::Integer sdfg::structured_control_flow::StructuredLoop::stride

(

)

const

Describes the stride of a loop's update as a constant.

Returns

The stride of the loop's update as a constant, otherwise null.

update()

const symbolic::Expression sdfg::structured_control_flow::StructuredLoop::update

(

)

const

Get the update expression for the induction variable.

Returns

Expression evaluated to update the induction variable each iteration

validate()

void sdfg::structured_control_flow::StructuredLoop::validate ( const Function & function ) const

overridevirtual

Validates the element.

Exceptions

InvalidSDFGException

if the element is invalid

Implements sdfg::Element.

Friends And Related Symbol Documentation

sdfg::builder::StructuredSDFGBuilder

friend class sdfg::builder::StructuredSDFGBuilder

friend

Member Data Documentation

canonical_bound_cache_

std::optional<symbolic::Expression> sdfg::structured_control_flow::StructuredLoop::canonical_bound_cache_

mutableprotected

condition_

symbolic::Condition sdfg::structured_control_flow::StructuredLoop::condition_

protected

indvar_

symbolic::Symbol sdfg::structured_control_flow::StructuredLoop::indvar_

protected

init_

symbolic::Expression sdfg::structured_control_flow::StructuredLoop::init_

protected

num_iterations_cache_

std::optional<symbolic::Expression> sdfg::structured_control_flow::StructuredLoop::num_iterations_cache_

mutableprotected

REQUIRED_ELEMENT_IDS

size_t sdfg::structured_control_flow::StructuredLoop::REQUIRED_ELEMENT_IDS = 2

staticconstexprprotected

root_

std::unique_ptr<Sequence> sdfg::structured_control_flow::StructuredLoop::root_

protected

schedule_type_

ScheduleType sdfg::structured_control_flow::StructuredLoop::schedule_type_

protected

stride_cache_

std::optional<symbolic::Integer> sdfg::structured_control_flow::StructuredLoop::stride_cache_

mutableprotected

TypeGroup

ElementType sdfg::structured_control_flow::StructuredLoop::TypeGroup = ElementType::For | ElementType::Map | ElementType::Reduce

staticconstexpr

Bitmask of all concrete ElementTypes that are StructuredLoops.

update_

symbolic::Expression sdfg::structured_control_flow::StructuredLoop::update_

protected

---

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

• sdfg/include/sdfg/structured_control_flow/structured_loop.h