sdfg::structured_control_flow::Reduce Class Reference

Represents a loop with an associative/commutative reduction carried dependency. More...

#include <sdfg/structured_control_flow/reduce.h>

Inheritance diagram for sdfg::structured_control_flow::Reduce:

Public Member Functions
	Reduce (const Reduce &node)=delete
Reduce &	operator= (const Reduce &)=delete
ElementType	type_id () const override
	Returns the type of the element.
bool	accept (visitor::ActualStructuredSDFGVisitor &visitor) override
void	validate (const Function &function) const override
	Validates the element.
void	replace (const symbolic::Expression old_expression, const symbolic::Expression new_expression) override
void	replace (const symbolic::ExpressionMapping &replacements) override
const std::vector< ReductionInfo > &	reductions () const
	Get the reductions carried by this loop.
void	replace_reduction_container (const std::string &old_name, const std::string &new_name)
	Retarget any reduction whose accumulator is old_name to new_name.
void	original_index (const std::string &container, symbolic::Expression index)
Public Member Functions inherited from sdfg::structured_control_flow::StructuredLoop
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	~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
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)
Static Public Member Functions inherited from sdfg::structured_control_flow::StructuredLoop
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)

Friends
class	sdfg::builder::StructuredSDFGBuilder

Additional Inherited Members
Static Public Attributes inherited from sdfg::structured_control_flow::StructuredLoop
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 inherited from sdfg::structured_control_flow::StructuredLoop
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 inherited from sdfg::structured_control_flow::StructuredLoop
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 inherited from sdfg::structured_control_flow::StructuredLoop
static constexpr size_t	REQUIRED_ELEMENT_IDS = 2

Detailed Description

Represents a loop with an associative/commutative reduction carried dependency.

A Reduce loop has the same shape as a For loop (induction variable, init, update, condition and a body sequence), but additionally carries the semantic information that its body combines per-iteration values into an accumulator using an associative and commutative ReductionOperation.

Unlike a Map, the iterations of a Reduce loop are not independent: they all contribute to a shared accumulator. Unlike a plain For, the combine is known to be reorderable, which is what later transformations exploit to lower it to a parallel (tree / warp-shuffle) reduction.

The accumulator container(s) and the concrete combine tasklet remain in the loop body; this node records, per reduction, the operator together with the name of the accumulator container (see ReductionInfo) so that codegen and transformations know how to initialize partials and combine them. A single Reduce may carry multiple reductions at once.

See also

StructuredLoop

For

Map

Constructor & Destructor Documentation

Reduce()

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

delete

Member Function Documentation

accept()

bool sdfg::structured_control_flow::Reduce::accept ( visitor::ActualStructuredSDFGVisitor & visitor )

overridevirtual

Implements sdfg::structured_control_flow::ControlFlowNode.

classof()

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

inlinestatic

operator=()

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

delete

original_index()

void sdfg::structured_control_flow::Reduce::original_index	(	const std::string &	container,
		symbolic::Expression	index )

reductions()

const std::vector< ReductionInfo > & sdfg::structured_control_flow::Reduce::reductions

(

)

const

Get the reductions carried by this loop.

Each entry pairs an associative/commutative operator with the name of the accumulator container it combines into. There is at least one entry.

replace() [1/2]

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

overridevirtual

Implements sdfg::Element.

replace() [2/2]

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

overridevirtual

Reimplemented from sdfg::Element.

replace_reduction_container()

void sdfg::structured_control_flow::Reduce::replace_reduction_container	(	const std::string &	old_name,
		const std::string &	new_name )

Retarget any reduction whose accumulator is old_name to new_name.

The accumulator container name is denormalized here; passes that rewrite accumulator access nodes directly (e.g. reference propagation) use this to keep the ReductionInfo consistent with the dataflow graph.

type_id()

ElementType sdfg::structured_control_flow::Reduce::type_id ( ) const

inlineoverridevirtual

Returns the type of the element.

Implements sdfg::Element.

validate()

void sdfg::structured_control_flow::Reduce::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

---

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

• sdfg/include/sdfg/structured_control_flow/reduce.h