DependenceInfo.cpp File Reference

#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"

Go to the source code of this file.

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.

Referenced by polly::ScopBuilder::addUserAssumptions(), polly::ScopBuilder::buildAliasGroup(), polly::emitRejectionRemarks(), polly::ScopBuilder::ScopBuilder(), and polly::Scop::trackAssumption().

Enumeration Type Documentation

AnalysisType

enum AnalysisType

Enumerator
VALUE_BASED_ANALYSIS
MEMORY_BASED_ANALYSIS

Definition at line 61 of file DependenceInfo.cpp.

Function Documentation

buildFlow()

__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_give, __isl_keep, 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()

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_set, 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(), isl_union_set, S, tag(), and UseReductions().

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

fixSetToZero()

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	)

Referenced by INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), and INITIALIZE_PASS_BEGIN().

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	)

References INITIALIZE_PASS_DEPENDENCY().

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

)

Referenced by INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), and INITIALIZE_PASS_BEGIN().

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(), polly::DependenceInfo::printScop(), and S.

Referenced by INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_END(), INITIALIZE_PASS_END(), and INITIALIZE_PASS_END().

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.

References if(), and S.

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, INITIALIZE_PASS_END(), and polly::DependenceInfoWrapperPass::print().

LegalityCheckDisabled()

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

static

References PollyCategory.

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

OptAnalysisLevel()

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

References polly::Dependences::AL_Access, polly::Dependences::AL_Reference, polly::Dependences::AL_Statement, and PollyCategory.

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

OptAnalysisType()

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

References MEMORY_BASED_ANALYSIS, PollyCategory, and VALUE_BASED_ANALYSIS.

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

OptComputeOut()

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

References PollyCategory.

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

printDependencyMap()

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

static

Definition at line 760 of file DependenceInfo.cpp.

References __isl_keep.

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

tag() [1/2]

__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_give, __isl_take, 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]

__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 __isl_give, __isl_take, polly::Dependences::AL_Access, polly::Dependences::AL_Reference, polly::MemoryAccess::getArrayId(), polly::MemoryAccess::getId(), isl::id::release(), and tag().

UseReductions()

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

static

References PollyCategory.

Referenced by collectInfo().