The accumulated dependence information for a SCoP. More...

#include <DependenceInfo.h>

Public Types
enum	AnalysisLevel { AL_Statement = 0 , AL_Reference , AL_Access , NumAnalysisLevels }

enum	Type { TYPE_WAR = 1 << 0 , TYPE_RAW = 1 << 1 , TYPE_WAW = 1 << 2 , TYPE_RED = 1 << 3 , TYPE_TC_RED = 1 << 4 }
	The type of the dependences. More...

using	ReductionDependencesMapTy = DenseMap< MemoryAccess , isl_map >
	Map type for reduction dependences.

using	StatementToIslMapTy = DenseMap< ScopStmt *, isl::map >
	Map type to associate statements with schedules.

Public Member Functions
const std::shared_ptr< isl_ctx > &	getSharedIslCtx () const

isl::union_map	getDependences (int Kinds) const
	Get the dependences of type `Kinds`.

bool	hasValidDependences () const
	Report if valid dependences are available.

__isl_give isl_map *	getReductionDependences (MemoryAccess *MA) const
	Return the reduction dependences caused by `MA`.

const ReductionDependencesMapTy &	getReductionDependences () const
	Return all reduction dependences.

bool	isParallel (__isl_keep isl_union_map Schedule, __isl_take isl_union_map Deps, __isl_give isl_pw_aff **MinDistancePtr=nullptr) const
	Check if a partial schedule is parallel wrt to `Deps`.

bool	isValidSchedule (Scop &S, const StatementToIslMapTy &NewSchedules) const
	Check if a new schedule is valid.

bool	isValidSchedule (Scop &S, isl::schedule NewSched) const
	Return true of the schedule `NewSched` is a schedule for @S that does not violate any dependences.

void	print (llvm::raw_ostream &OS) const
	Print the stored dependence information.

void	dump () const
	Dump the dependence information stored to the dbgs stream.

AnalysisLevel	getDependenceLevel ()
	Return the granularity of this dependence analysis.

	~Dependences ()
	Destructor that will free internal objects.

Private Member Functions
	Dependences (const std::shared_ptr< isl_ctx > &IslCtx, AnalysisLevel Level)
	Create an empty dependences struct.

void	addPrivatizationDependences ()
	Calculate and add at the privatization dependences.

void	calculateDependences (Scop &S)
	Calculate the dependences for a certain SCoP `S`.

void	setReductionDependences (MemoryAccess MA, __isl_take isl_map Deps)
	Set the reduction dependences for `MA` to `Deps`.

void	releaseMemory ()
	Free the objects associated with this Dependences struct.

Private Attributes
isl_union_map *	RAW
	The different basic kinds of dependences we calculate.

isl_union_map *	WAR

isl_union_map *	WAW

isl_union_map *	RED
	The special reduction dependences.

isl_union_map *	TC_RED
	The (reverse) transitive closure of reduction dependences.

ReductionDependencesMapTy	ReductionDependences
	Mapping from memory accesses to their reduction dependences.

std::shared_ptr< isl_ctx >	IslCtx
	Isl context from the SCoP.

const AnalysisLevel	Level
	Granularity of this dependence analysis.

Friends
struct	DependenceAnalysis
	Allow the DependenceInfo access to private members and methods.

struct	DependenceInfoPrinterPass

class	DependenceInfo

class	DependenceInfoWrapperPass

Detailed Description

The accumulated dependence information for a SCoP.

The Dependences struct holds all dependence information we collect and compute for one SCoP. It also offers an interface that allows users to query only specific parts.

Definition at line 36 of file DependenceInfo.h.

Member Typedef Documentation

◆ ReductionDependencesMapTy

using polly::Dependences::ReductionDependencesMapTy = DenseMap<MemoryAccess *, isl_map *>

Map type for reduction dependences.

Definition at line 50 of file DependenceInfo.h.

◆ StatementToIslMapTy

using polly::Dependences::StatementToIslMapTy = DenseMap<ScopStmt *, isl::map>

Map type to associate statements with schedules.

Definition at line 53 of file DependenceInfo.h.

Member Enumeration Documentation

◆ AnalysisLevel

enum polly::Dependences::AnalysisLevel

Enumerator
AL_Statement
AL_Reference
AL_Access
NumAnalysisLevels

Definition at line 39 of file DependenceInfo.h.

◆ Type

enum polly::Dependences::Type

The type of the dependences.

Reduction dependences are separated from RAW/WAW/WAR dependences because we can ignore them during the scheduling. That's because the order in which the reduction statements are executed does not matter. However, if they are executed in parallel we need to take additional measures (e.g, privatization) to ensure a correct result. The (reverse) transitive closure of the reduction dependences are used to check for parallel executed reduction statements during code generation. These dependences connect all instances of a reduction with each other, they are therefore cyclic and possibly "reversed".

Enumerator
TYPE_WAR
TYPE_RAW
TYPE_WAW
TYPE_RED
TYPE_TC_RED

Definition at line 66 of file DependenceInfo.h.

Constructor & Destructor Documentation

◆ ~Dependences()

polly::Dependences::~Dependences ( )

inline

Destructor that will free internal objects.

Definition at line 151 of file DependenceInfo.h.

References releaseMemory().

◆ Dependences()

polly::Dependences::Dependences	(	const std::shared_ptr< isl_ctx > &	IslCtx,
		AnalysisLevel	Level
	)

inlineexplicitprivate

Create an empty dependences struct.

Definition at line 155 of file DependenceInfo.h.

Member Function Documentation

◆ addPrivatizationDependences()

void Dependences::addPrivatizationDependences ( )

private

Calculate and add at the privatization dependences.

Compute the privatization dependences for a given dependency Map.

Privatization dependences are widened original dependences which originate or end in a reduction access. To compute them we apply the transitive close of the reduction dependences (which maps each iteration of a reduction statement to all following ones) on the RAW/WAR/WAW dependences. The dependences which start or end at a reduction statement will be extended to depend on all following reduction statement iterations as well. Note: "Following" here means according to the reduction dependences.

For the input:

S0: *sum = 0; for (int i = 0; i < 1024; i++) S1: *sum += i; S2: *sum = *sum * 3;

we have the following dependences before we add privatization dependences:

RAW: { S0[] -> S1[0]; S1[1023] -> S2[] } WAR: { } WAW: { S0[] -> S1[0]; S1[1024] -> S2[] } RED: { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }

and afterwards:

RAW: { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023; S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023} WAR: { } WAW: { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023; S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023} RED: { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }

Note: This function also computes the (reverse) transitive closure of the reduction dependences.

Definition at line 240 of file DependenceInfo.cpp.

References fixSetToZero(), isl_union_map_apply_range(), isl_union_map_coalesce(), isl_union_map_copy(), isl_union_map_deltas(), isl_union_map_reverse(), isl_union_map_subtract(), isl_union_map_transitive_closure(), isl_union_map_union(), isl_union_set_copy(), isl_union_set_empty(), isl_union_set_free(), isl_union_set_get_space(), isl_union_set_lex_le_union_set(), isl_union_set_universe(), isl::manage(), isl::manage_copy(), RAW, RED, isl::union_set::release(), TC_RED, WAR, and WAW.

Referenced by calculateDependences().

◆ calculateDependences()

void Dependences::calculateDependences ( Scop & S )

private

Calculate the dependences for a certain SCoP S.

Definition at line 311 of file DependenceInfo.cpp.

References addPrivatizationDependences(), AL_Statement, assert, buildFlow(), collectInfo(), dump(), isl_ctx_last_error(), isl_ctx_reset_error(), isl_error_quota, isl_map_copy(), isl_map_domain(), isl_map_from_domain_and_range(), isl_map_from_union_map(), isl_map_wrap(), isl_map_zip(), isl_schedule_free(), isl_schedule_pullback_union_pw_multi_aff(), isl_set_copy(), isl_set_unwrap(), isl_union_flow_free(), isl_union_flow_get_may_dependence(), isl_union_flow_get_must_dependence(), isl_union_map_add_map(), isl_union_map_coalesce(), isl_union_map_copy(), isl_union_map_domain(), isl_union_map_domain_map_union_pw_multi_aff(), isl_union_map_empty(), isl_union_map_free(), isl_union_map_get_space(), isl_union_map_intersect(), isl_union_map_intersect_domain(), isl_union_map_is_empty(), isl_union_map_is_equal(), isl_union_map_subtract(), isl_union_map_union(), isl_union_map_zip(), isl_union_pw_multi_aff_from_union_map(), isl_union_pw_multi_aff_union_add(), isl_union_set_copy(), isl_union_set_free(), isl_union_set_from_set(), isl_union_set_get_space(), isl_union_set_identity(), isl_union_set_unwrap(), IslCtx, Level, OptAnalysisType(), OptComputeOut(), POLLY_DEBUG, RAW, RED, setReductionDependences(), TC_RED, VALUE_BASED_ANALYSIS, WAR, and WAW.

Referenced by polly::DependenceInfo::printScop(), polly::DependenceAnalysis::Result::recomputeDependences(), polly::DependenceInfo::recomputeDependences(), and polly::DependenceInfoPrinterPass::run().

◆ dump()

void Dependences::dump ( ) const

Dump the dependence information stored to the dbgs stream.

Definition at line 780 of file DependenceInfo.cpp.

References print().

Referenced by calculateDependences().

◆ getDependenceLevel()

AnalysisLevel polly::Dependences::getDependenceLevel ( )

inline

Return the granularity of this dependence analysis.

Definition at line 139 of file DependenceInfo.h.

References Level.

◆ getDependences()

isl::union_map Dependences::getDependences ( int Kinds ) const

Get the dependences of type Kinds.

Parameters

Kinds This integer defines the different kinds of dependences that will be returned. To return more than one kind, the different kinds are 'ored' together.

Definition at line 796 of file DependenceInfo.cpp.

References assert, isl::union_map::coalesce(), isl::space::ctx(), isl::union_map::detect_equalities(), isl::union_map::empty(), hasValidDependences(), isl::manage_copy(), RAW, RED, TC_RED, TYPE_RAW, TYPE_RED, TYPE_TC_RED, TYPE_WAR, TYPE_WAW, isl::union_map::unite(), WAR, and WAW.

Referenced by astScheduleDimIsParallel(), polly::PolyhedralInfo::checkParallel(), isValidSchedule(), and polly::IslAstInfoWrapperPass::runOnScop().

◆ getReductionDependences() [1/2]

const ReductionDependencesMapTy & polly::Dependences::getReductionDependences ( ) const

inline

Return all reduction dependences.

Definition at line 101 of file DependenceInfo.h.

References ReductionDependences.

◆ getReductionDependences() [2/2]

__isl_give isl_map * Dependences::getReductionDependences ( MemoryAccess * MA ) const

Return the reduction dependences caused by MA.

Returns: The reduction dependences caused by MA or nullptr if none.

Definition at line 826 of file DependenceInfo.cpp.

References isl_map_copy(), and ReductionDependences.

Referenced by astScheduleDimIsParallel().

◆ getSharedIslCtx()

const std::shared_ptr< isl_ctx > & polly::Dependences::getSharedIslCtx ( ) const

inline

Definition at line 83 of file DependenceInfo.h.

References IslCtx.

Referenced by runIslAst().

◆ hasValidDependences()

bool Dependences::hasValidDependences ( ) const

Report if valid dependences are available.

Definition at line 821 of file DependenceInfo.cpp.

References RAW, WAR, and WAW.

Referenced by astScheduleDimIsParallel(), polly::PolyhedralInfo::checkParallel(), and getDependences().

◆ isParallel()

bool Dependences::isParallel	(	__isl_keep isl_union_map *	Schedule,
		__isl_take isl_union_map *	Deps,
		__isl_give isl_pw_aff **	MinDistancePtr = `nullptr`
	)		const

Check if a partial schedule is parallel wrt to Deps.

Parameters

Schedule	The subset of the schedule space that we want to check.
Deps	The dependences `Schedule` needs to respect.
MinDistancePtr	If not nullptr, the minimal dependence distance will be returned at the address of that pointer

Returns: Returns true, if executing parallel the outermost dimension of Schedule is valid according to the dependences Deps.

Definition at line 711 of file DependenceInfo.cpp.

References isl_dim_in, isl_dim_out, isl_dim_set, isl_map_deltas(), isl_map_dim(), isl_map_equate(), isl_map_from_union_map(), isl_pw_aff_coalesce(), isl_set_coalesce(), isl_set_dim_min(), isl_set_fix_si(), isl_set_free(), isl_set_get_space(), isl_set_intersect(), isl_set_is_empty(), isl_set_lower_bound_si(), isl_set_project_out(), isl_set_universe(), isl_union_map_apply_domain(), isl_union_map_apply_range(), isl_union_map_copy(), isl_union_map_free(), and isl_union_map_is_empty().

Referenced by astScheduleDimIsParallel(), and polly::PolyhedralInfo::checkParallel().

◆ isValidSchedule() [1/2]

bool Dependences::isValidSchedule	(	Scop &	S,
		const StatementToIslMapTy &	NewSchedules
	)		const

Check if a new schedule is valid.

Parameters

S	The current SCoP.
NewSchedules	The new schedules

Returns: True if the new schedule is valid, false if it reverses dependences.

Definition at line 651 of file DependenceInfo.cpp.

References assert, isl::union_map::empty(), isl::set::fix_si(), isl::map::get_space(), isl::set::get_space(), getDependences(), isl::multi_pw_aff::identity_on_domain(), isl::map::intersect_domain(), isl::map::intersect_range(), isl::map::is_empty(), isl::map::is_null(), isl::space::is_null(), LegalityCheckDisabled(), isl::map::lex_le_at(), isl::space::map_from_set(), isl::space::range(), polly::rangeIslSize(), isl::set, polly::singleton(), isl::set::tuple_dim(), TYPE_RAW, TYPE_WAR, TYPE_WAW, isl::union_map::unite(), isl::map::universe(), and isl::set::universe().

Referenced by importSchedule(), and isValidSchedule().

◆ isValidSchedule() [2/2]

bool Dependences::isValidSchedule	(	Scop &	S,
		isl::schedule	NewSched
	)		const

Return true of the schedule NewSched is a schedule for @S that does not violate any dependences.

Definition at line 638 of file DependenceInfo.cpp.

References isl::schedule::get_map(), isl::union_map::get_map_list(), isl::in, and isValidSchedule().

◆ print()

void Dependences::print ( llvm::raw_ostream & OS ) const

Print the stored dependence information.

Definition at line 767 of file DependenceInfo.cpp.

References printDependencyMap(), RAW, RED, TC_RED, WAR, and WAW.

Referenced by dump(), polly::DependenceInfo::printScop(), and polly::DependenceInfoPrinterPass::run().

◆ releaseMemory()

void Dependences::releaseMemory ( )

private

Free the objects associated with this Dependences struct.

The Dependences struct will again be "empty" afterwards.

Definition at line 782 of file DependenceInfo.cpp.

References isl_map_free(), isl_union_map_free(), RAW, RED, ReductionDependences, TC_RED, WAR, and WAW.

Referenced by ~Dependences().

◆ setReductionDependences()

void Dependences::setReductionDependences	(	MemoryAccess *	MA,
		__isl_take isl_map *	Deps
	)

private

Set the reduction dependences for MA to Deps.

Definition at line 830 of file DependenceInfo.cpp.

References assert, and ReductionDependences.

Referenced by calculateDependences().

Friends And Related Function Documentation

◆ DependenceAnalysis

friend struct DependenceAnalysis

friend

Allow the DependenceInfo access to private members and methods.

To restrict access to the internal state, only the DependenceInfo class is able to call or modify a Dependences struct.

Definition at line 145 of file DependenceInfo.h.

◆ DependenceInfo

friend class DependenceInfo

friend

Definition at line 147 of file DependenceInfo.h.

◆ DependenceInfoPrinterPass

friend struct DependenceInfoPrinterPass

friend

Definition at line 146 of file DependenceInfo.h.

◆ DependenceInfoWrapperPass

friend class DependenceInfoWrapperPass

friend

Definition at line 148 of file DependenceInfo.h.

Member Data Documentation

◆ IslCtx

std::shared_ptr<isl_ctx> polly::Dependences::IslCtx

private

Isl context from the SCoP.

Definition at line 189 of file DependenceInfo.h.

Referenced by calculateDependences(), and getSharedIslCtx().

◆ Level

const AnalysisLevel polly::Dependences::Level

private

Granularity of this dependence analysis.

Definition at line 192 of file DependenceInfo.h.

Referenced by calculateDependences(), and getDependenceLevel().

◆ RAW

isl_union_map* polly::Dependences::RAW

private

The different basic kinds of dependences we calculate.

Definition at line 175 of file DependenceInfo.h.

Referenced by addPrivatizationDependences(), calculateDependences(), getDependences(), hasValidDependences(), print(), and releaseMemory().

◆ RED

isl_union_map* polly::Dependences::RED

private

The special reduction dependences.

Definition at line 180 of file DependenceInfo.h.

Referenced by addPrivatizationDependences(), calculateDependences(), getDependences(), print(), and releaseMemory().

◆ ReductionDependences

ReductionDependencesMapTy polly::Dependences::ReductionDependences

private

Mapping from memory accesses to their reduction dependences.

Definition at line 186 of file DependenceInfo.h.

Referenced by getReductionDependences(), releaseMemory(), and setReductionDependences().

◆ TC_RED

isl_union_map* polly::Dependences::TC_RED

private

The (reverse) transitive closure of reduction dependences.

Definition at line 183 of file DependenceInfo.h.

Referenced by addPrivatizationDependences(), calculateDependences(), getDependences(), print(), and releaseMemory().

◆ WAR

isl_union_map* polly::Dependences::WAR

private

Definition at line 176 of file DependenceInfo.h.

Referenced by addPrivatizationDependences(), calculateDependences(), getDependences(), hasValidDependences(), print(), and releaseMemory().

◆ WAW

isl_union_map* polly::Dependences::WAW

private

Definition at line 177 of file DependenceInfo.h.

Referenced by addPrivatizationDependences(), calculateDependences(), getDependences(), hasValidDependences(), print(), and releaseMemory().

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

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ ReductionDependencesMapTy

◆ StatementToIslMapTy

Member Enumeration Documentation

◆ AnalysisLevel

◆ Type

Constructor & Destructor Documentation

◆ ~Dependences()

◆ Dependences()

Member Function Documentation

◆ addPrivatizationDependences()

◆ calculateDependences()

◆ dump()

◆ getDependenceLevel()

◆ getDependences()

◆ getReductionDependences() [1/2]

◆ getReductionDependences() [2/2]

◆ getSharedIslCtx()

◆ hasValidDependences()

◆ isParallel()

◆ isValidSchedule() [1/2]

◆ isValidSchedule() [2/2]

◆ print()

◆ releaseMemory()

◆ setReductionDependences()

Friends And Related Function Documentation

◆ DependenceAnalysis

◆ DependenceInfo

◆ DependenceInfoPrinterPass

◆ DependenceInfoWrapperPass

Member Data Documentation

◆ IslCtx

◆ Level

◆ RAW

◆ RED

◆ ReductionDependences

◆ TC_RED

◆ WAR

◆ WAW