#include "polly/DependenceInfo.h"
#include "polly/LinkAllPasses.h"
#include "polly/Options.h"
#include "polly/ScopInfo.h"
#include "polly/Support/GICHelper.h"
#include "polly/Support/ISLTools.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/Support/Debug.h"
#include "isl/aff.h"
#include "isl/ctx.h"
#include "isl/flow.h"
#include "isl/map.h"
#include "isl/schedule.h"
#include "isl/set.h"
#include "isl/union_map.h"
#include "isl/union_set.h"
#include "polly/Support/PollyDebug.h"

Macros
#define	DEBUG_TYPE "polly-dependence"

Enumerations
enum	AnalysisType { VALUE_BASED_ANALYSIS , MEMORY_BASED_ANALYSIS }

Functions
static cl::opt< int >	OptComputeOut ("polly-dependences-computeout", cl::desc("Bound the dependence analysis by a maximal amount of " "computational steps (0 means no bound)"), cl::Hidden, cl::init(500000), cl::cat(PollyCategory))

static cl::opt< bool >	LegalityCheckDisabled ("disable-polly-legality", cl::desc("Disable polly legality check"), cl::Hidden, cl::cat(PollyCategory))

static cl::opt< bool >	UseReductions ("polly-dependences-use-reductions", cl::desc("Exploit reductions in dependence analysis"), cl::Hidden, cl::init(true), cl::cat(PollyCategory))

static cl::opt< enum AnalysisType >	OptAnalysisType ("polly-dependences-analysis-type", cl::desc("The kind of dependence analysis to use"), cl::values(clEnumValN(VALUE_BASED_ANALYSIS, "value-based", "Exact dependences without transitive dependences"), clEnumValN(MEMORY_BASED_ANALYSIS, "memory-based", "Overapproximation of dependences")), cl::Hidden, cl::init(VALUE_BASED_ANALYSIS), cl::cat(PollyCategory))

static cl::opt< Dependences::AnalysisLevel >	OptAnalysisLevel ("polly-dependences-analysis-level", cl::desc("The level of dependence analysis"), cl::values(clEnumValN(Dependences::AL_Statement, "statement-wise", "Statement-level analysis"), clEnumValN(Dependences::AL_Reference, "reference-wise", "Memory reference level analysis that distinguish" " accessed references in the same statement"), clEnumValN(Dependences::AL_Access, "access-wise", "Memory reference level analysis that distinguish" " access instructions in the same statement")), cl::Hidden, cl::init(Dependences::AL_Statement), cl::cat(PollyCategory))

static __isl_give isl_map *	tag (__isl_take isl_map Relation, __isl_take isl_id TagId)
	Tag the `Relation` domain with `TagId`.

static __isl_give isl_map *	tag (__isl_take isl_map Relation, MemoryAccess MA, Dependences::AnalysisLevel TagLevel)
	Tag the `Relation` domain with either MA->getArrayId() or MA->getId() based on `TagLevel`.

static void	collectInfo (Scop &S, isl_union_map &Read, isl_union_map &MustWrite, isl_union_map &MayWrite, isl_union_map &ReductionTagMap, isl_union_set *&TaggedStmtDomain, Dependences::AnalysisLevel Level)
	Collect information about the SCoP `S`.

static void	fixSetToZero (isl::set Zero, isl::union_set *User)
	Fix all dimension of `Zero` to 0 and add it to `user`.

static __isl_give isl_union_flow *	buildFlow (__isl_keep isl_union_map Snk, __isl_keep isl_union_map Src, __isl_keep isl_union_map MaySrc, __isl_keep isl_union_map Kill, __isl_keep isl_schedule *Schedule)

static void	printDependencyMap (raw_ostream &OS, __isl_keep isl_union_map *DM)

	INITIALIZE_PASS_BEGIN (DependenceInfo, "polly-dependences", "Polly - Calculate dependences", false, false)

	INITIALIZE_PASS_DEPENDENCY (ScopInfoRegionPass)

	INITIALIZE_PASS_END (DependenceInfo, "polly-dependences", "Polly - Calculate dependences", false, false) namespace

	INITIALIZE_PASS_BEGIN (DependenceInfoPrinterLegacyPass, "polly-print-dependences", "Polly - Print dependences", false, false)

	INITIALIZE_PASS_DEPENDENCY (DependenceInfo)

	INITIALIZE_PASS_END (DependenceInfoPrinterLegacyPass, "polly-print-dependences", "Polly - Print dependences", false, false) const Dependences &DependenceInfoWrapperPass

	INITIALIZE_PASS_BEGIN (DependenceInfoWrapperPass, "polly-function-dependences", "Polly - Calculate dependences for all the SCoPs of a function", false, false) INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass)

	INITIALIZE_PASS_END (DependenceInfoWrapperPass, "polly-function-dependences", "Polly - Calculate dependences for all the SCoPs of a function", false, false) namespace

	INITIALIZE_PASS_BEGIN (DependenceInfoPrinterLegacyFunctionPass, "polly-print-function-dependences", "Polly - Print dependences for all the SCoPs of a function", false, false)

	INITIALIZE_PASS_DEPENDENCY (DependenceInfoWrapperPass)

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "polly-dependence"

Definition at line 43 of file DependenceInfo.cpp.

Enumeration Type Documentation

◆ AnalysisType

enum AnalysisType

Enumerator
VALUE_BASED_ANALYSIS
MEMORY_BASED_ANALYSIS

Definition at line 61 of file DependenceInfo.cpp.

Function Documentation

◆ buildFlow()

static __isl_give isl_union_flow * buildFlow	(	__isl_keep isl_union_map *	Snk,
		__isl_keep isl_union_map *	Src,
		__isl_keep isl_union_map *	MaySrc,
		__isl_keep isl_union_map *	Kill,
		__isl_keep isl_schedule *	Schedule
	)

static

Definition at line 288 of file DependenceInfo.cpp.

References isl_ctx_last_error(), isl_schedule_copy(), isl_schedule_get_ctx(), isl_union_access_info_compute_flow(), isl_union_access_info_from_sink(), isl_union_access_info_set_kill(), isl_union_access_info_set_may_source(), isl_union_access_info_set_must_source(), isl_union_access_info_set_schedule(), isl_union_map_copy(), and POLLY_DEBUG.

Referenced by polly::Dependences::calculateDependences().

◆ collectInfo()

static void collectInfo	(	Scop &	S,
		isl_union_map *&	Read,
		isl_union_map *&	MustWrite,
		isl_union_map *&	MayWrite,
		isl_union_map *&	ReductionTagMap,
		isl_union_set *&	TaggedStmtDomain,
		Dependences::AnalysisLevel	Level
	)

static

Collect information about the SCoP S.

Definition at line 114 of file DependenceInfo.cpp.

References polly::Dependences::AL_Statement, assert, isl_map_copy(), isl_map_intersect_domain(), isl_map_range_map(), isl_space_copy(), isl_union_map_add_map(), isl_union_map_coalesce(), isl_union_map_domain(), isl_union_map_empty(), isl_union_map_intersect_params(), tag(), and UseReductions().

Referenced by polly::Dependences::calculateDependences().

◆ fixSetToZero()

static void fixSetToZero	(	isl::set	Zero,
		isl::union_set *	User
	)

static

Fix all dimension of Zero to 0 and add it to user.

Definition at line 191 of file DependenceInfo.cpp.

References isl::set::fix_si(), polly::rangeIslSize(), isl::set, isl::set::tuple_dim(), and isl::union_set::unite().

Referenced by polly::Dependences::addPrivatizationDependences().

◆ INITIALIZE_PASS_BEGIN() [1/4]

INITIALIZE_PASS_BEGIN	(	DependenceInfo	,
		"polly-dependences"	,
		"Polly - Calculate dependences"	,
		false	,
		false
	)

◆ INITIALIZE_PASS_BEGIN() [2/4]

INITIALIZE_PASS_BEGIN	(	DependenceInfoPrinterLegacyFunctionPass	,
		"polly-print-function-dependences"	,
		"Polly - Print dependences for all the SCoPs of a function"	,
		false	,
		false
	)

◆ INITIALIZE_PASS_BEGIN() [3/4]

INITIALIZE_PASS_BEGIN	(	DependenceInfoPrinterLegacyPass	,
		"polly-print-dependences"	,
		"Polly - Print dependences"	,
		false	,
		false
	)

◆ INITIALIZE_PASS_BEGIN() [4/4]

INITIALIZE_PASS_BEGIN	(	DependenceInfoWrapperPass	,
		"polly-function-dependences"	,
		"Polly - Calculate dependences for all the SCoPs of a function"	,
		false	,
		false
	)

◆ INITIALIZE_PASS_DEPENDENCY() [1/3]

INITIALIZE_PASS_DEPENDENCY ( DependenceInfo )

◆ INITIALIZE_PASS_DEPENDENCY() [2/3]

INITIALIZE_PASS_DEPENDENCY ( DependenceInfoWrapperPass )

◆ INITIALIZE_PASS_DEPENDENCY() [3/3]

INITIALIZE_PASS_DEPENDENCY ( ScopInfoRegionPass )

◆ INITIALIZE_PASS_END() [1/3]

INITIALIZE_PASS_END	(	DependenceInfo	,
		"polly-dependences"	,
		"Polly - Calculate dependences"	,
		false	,
		false
	)

Print result from DependenceAnalysis.

Definition at line 935 of file DependenceInfo.cpp.

References polly::ScopPass::getAnalysisUsage(), and polly::DependenceInfo::printScop().

◆ INITIALIZE_PASS_END() [2/3]

INITIALIZE_PASS_END	(	DependenceInfoPrinterLegacyPass	,
		"polly-print-dependences"	,
		"Polly - Print dependences"	,
		false	,
		false
	)		const &

Definition at line 983 of file DependenceInfo.cpp.

◆ INITIALIZE_PASS_END() [3/3]

INITIALIZE_PASS_END	(	DependenceInfoWrapperPass	,
		"polly-function-dependences"	,
		"Polly - Calculate dependences for all the SCoPs of a function"	,
		false	,
		false
	)

Print result from DependenceInfoWrapperPass.

Definition at line 1040 of file DependenceInfo.cpp.

References Function, and polly::DependenceInfoWrapperPass::print().

◆ LegalityCheckDisabled()

static cl::opt< bool > LegalityCheckDisabled	(	"disable-polly-legality"	,
		cl::desc("Disable polly legality check")	,
		cl::Hidden	,
		cl::cat(PollyCategory)
	)

static

Referenced by polly::Dependences::isValidSchedule().

◆ OptAnalysisLevel()

static cl::opt< Dependences::AnalysisLevel > OptAnalysisLevel	(	"polly-dependences-analysis-level"	,
		cl::desc("The level of dependence analysis")	,
		cl::values(clEnumValN(Dependences::AL_Statement, "statement-wise", "Statement-level analysis"), clEnumValN(Dependences::AL_Reference, "reference-wise", "Memory reference level analysis that distinguish" " accessed references in the same statement"), clEnumValN(Dependences::AL_Access, "access-wise", "Memory reference level analysis that distinguish" " access instructions in the same statement"))	,
		cl::Hidden	,
		cl::init(Dependences::AL_Statement)	,
		cl::cat(PollyCategory)
	)

static

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

◆ OptAnalysisType()

static cl::opt< enum AnalysisType > OptAnalysisType	(	"polly-dependences-analysis-type"	,
		cl::desc("The kind of dependence analysis to use")	,
		cl::values(clEnumValN(VALUE_BASED_ANALYSIS, "value-based", "Exact dependences without transitive dependences"), clEnumValN(MEMORY_BASED_ANALYSIS, "memory-based", "Overapproximation of dependences"))	,
		cl::Hidden	,
		cl::init(VALUE_BASED_ANALYSIS)	,
		cl::cat(PollyCategory)
	)

static

Referenced by polly::Dependences::calculateDependences().

◆ OptComputeOut()

static cl::opt< int > OptComputeOut	(	"polly-dependences-computeout"	,
		cl::desc("Bound the dependence analysis by a maximal amount of " "computational steps (0 means no bound)")	,
		cl::Hidden	,
		cl::init(500000)	,
		cl::cat(PollyCategory)
	)

static

Referenced by polly::ScopBuilder::buildAliasGroups(), and polly::Dependences::calculateDependences().

◆ printDependencyMap()

static void printDependencyMap	(	raw_ostream &	OS,
		__isl_keep isl_union_map *	DM
	)

static

Definition at line 760 of file DependenceInfo.cpp.

Referenced by polly::Dependences::print().

◆ tag() [1/2]

static __isl_give isl_map * tag	(	__isl_take isl_map *	Relation,
		__isl_take isl_id *	TagId
	)

static

Tag the Relation domain with TagId.

Definition at line 88 of file DependenceInfo.cpp.

References isl_dim_out, isl_map_dim(), isl_map_get_space(), isl_map_preimage_domain_multi_aff(), isl_multi_aff_domain_map(), isl_space_drop_dims(), and isl_space_set_tuple_id().

Referenced by apply(), collectInfo(), isl_schedule_constraints_apply(), main(), rsa_pkcs1v15_decode(), rsa_pkcs1v15_encode(), and tag().

◆ tag() [2/2]

static __isl_give isl_map * tag	(	__isl_take isl_map *	Relation,
		MemoryAccess *	MA,
		Dependences::AnalysisLevel	TagLevel
	)

static

Tag the Relation domain with either MA->getArrayId() or MA->getId() based on TagLevel.

Definition at line 101 of file DependenceInfo.cpp.

References polly::Dependences::AL_Access, polly::Dependences::AL_Reference, polly::MemoryAccess::getArrayId(), polly::MemoryAccess::getId(), isl::id::release(), and tag().

◆ UseReductions()

static cl::opt< bool > UseReductions	(	"polly-dependences-use-reductions"	,
		cl::desc("Exploit reductions in dependence analysis")	,
		cl::Hidden	,
		cl::init(true)	,
		cl::cat(PollyCategory)
	)

static

Referenced by collectInfo().

Macros

Enumerations

Functions

Macro Definition Documentation

◆ DEBUG_TYPE

Enumeration Type Documentation

◆ AnalysisType

Function Documentation

◆ buildFlow()

◆ collectInfo()

◆ fixSetToZero()

◆ INITIALIZE_PASS_BEGIN() [1/4]

◆ INITIALIZE_PASS_BEGIN() [2/4]

◆ INITIALIZE_PASS_BEGIN() [3/4]

◆ INITIALIZE_PASS_BEGIN() [4/4]

◆ INITIALIZE_PASS_DEPENDENCY() [1/3]

◆ INITIALIZE_PASS_DEPENDENCY() [2/3]

◆ INITIALIZE_PASS_DEPENDENCY() [3/3]

◆ INITIALIZE_PASS_END() [1/3]

◆ INITIALIZE_PASS_END() [2/3]

◆ INITIALIZE_PASS_END() [3/3]

◆ LegalityCheckDisabled()

◆ OptAnalysisLevel()

◆ OptAnalysisType()

◆ OptComputeOut()

◆ printDependencyMap()

◆ tag() [1/2]

◆ tag() [2/2]

◆ UseReductions()