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.
isl::boolean	isKnownParallel (isl::union_map Schedule, isl::union_map Deps, 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

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 45 of file DependenceInfo.h.

Member Typedef Documentation

◆ ReductionDependencesMapTy

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

Map type for reduction dependences.

Definition at line 59 of file DependenceInfo.h.

◆ StatementToIslMapTy

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

Map type to associate statements with schedules.

Definition at line 62 of file DependenceInfo.h.

Member Enumeration Documentation

◆ AnalysisLevel

enum polly::Dependences::AnalysisLevel

Enumerator
AL_Statement
AL_Reference
AL_Access
NumAnalysisLevels

Definition at line 48 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 75 of file DependenceInfo.h.

Constructor & Destructor Documentation

◆ ~Dependences()

polly::Dependences::~Dependences ( )

inline

Destructor that will free internal objects.

Definition at line 161 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 165 of file DependenceInfo.h.

References IslCtx, Level, RAW, RED, TC_RED, WAR, and WAW.

Referenced by isValidSchedule().

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 244 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, 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::checked::manage(), isl::checked::manage_copy(), RAW, RED, isl::checked::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 315 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, 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, 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.

◆ dump()

void Dependences::dump ( ) const

Dump the dependence information stored to the dbgs stream.

Definition at line 791 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 150 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 807 of file DependenceInfo.cpp.

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

Referenced by astScheduleDimIsParallel(), and isValidSchedule().

◆ getReductionDependences() [1/2]

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

inline

Return all reduction dependences.

Definition at line 110 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 837 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 92 of file DependenceInfo.h.

References IslCtx.

Referenced by runIslAst().

◆ hasValidDependences()

bool Dependences::hasValidDependences ( ) const

Report if valid dependences are available.

Definition at line 832 of file DependenceInfo.cpp.

References RAW, WAR, and WAW.

Referenced by astScheduleDimIsParallel(), and getDependences().

◆ isKnownParallel()

isl::boolean Dependences::isKnownParallel	(	isl::union_map	Schedule,
		isl::union_map	Deps,
		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: isl::boolean::true if executing parallel the outermost dimension of Schedule is valid according to the dependences Deps, isl::boolean::false if it is not, and isl::boolean::error() if the result could not be computed (e.g. the ISL operation quota was exhausted during AST generation).

Definition at line 715 of file DependenceInfo.cpp.

References isl::checked::union_map::apply_domain(), isl::checked::union_map::apply_range(), isl::checked::set::coalesce(), isl::checked::map::deltas(), isl::boolean::error(), isl::map::from_union_map(), isl::checked::set::get_space(), isl::in, isl::checked::set::intersect(), isl::checked::set::is_empty(), isl::checked::union_map::is_empty(), isl::checked::boolean::is_error(), isl::checked::size::is_error(), isl::checked::union_map::is_null(), isl::checked::boolean::is_true(), isl::out, isl::set, and isl::set::universe().