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.

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().