DependenceAnalysis.cpp File Reference (original) (raw)

Go to the source code of this file.

Macros
#define	DEBUG_TYPE "da"

Functions
	STATISTIC (TotalArrayPairs, "Array pairs tested")
	STATISTIC (NonlinearSubscriptPairs, "Nonlinear subscript pairs")
	STATISTIC (ZIVapplications, "ZIV applications")
	STATISTIC (ZIVindependence, "ZIV independence")
	STATISTIC (StrongSIVapplications, "Strong SIV applications")
	STATISTIC (StrongSIVsuccesses, "Strong SIV successes")
	STATISTIC (StrongSIVindependence, "Strong SIV independence")
	STATISTIC (WeakCrossingSIVapplications, "Weak-Crossing SIV applications")
	STATISTIC (WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes")
	STATISTIC (WeakCrossingSIVindependence, "Weak-Crossing SIV independence")
	STATISTIC (ExactSIVapplications, "Exact SIV applications")
	STATISTIC (ExactSIVsuccesses, "Exact SIV successes")
	STATISTIC (ExactSIVindependence, "Exact SIV independence")
	STATISTIC (WeakZeroSIVapplications, "Weak-Zero SIV applications")
	STATISTIC (WeakZeroSIVsuccesses, "Weak-Zero SIV successes")
	STATISTIC (WeakZeroSIVindependence, "Weak-Zero SIV independence")
	STATISTIC (ExactRDIVapplications, "Exact RDIV applications")
	STATISTIC (ExactRDIVindependence, "Exact RDIV independence")
	STATISTIC (SymbolicRDIVapplications, "Symbolic RDIV applications")
	STATISTIC (SymbolicRDIVindependence, "Symbolic RDIV independence")
	STATISTIC (GCDapplications, "GCD applications")
	STATISTIC (GCDsuccesses, "GCD successes")
	STATISTIC (GCDindependence, "GCD independence")
	STATISTIC (BanerjeeApplications, "Banerjee applications")
	STATISTIC (BanerjeeIndependence, "Banerjee independence")
	STATISTIC (BanerjeeSuccesses, "Banerjee successes")
	STATISTIC (SameSDLoopsCount, "Loops with Same iteration Space and Depth")
	INITIALIZE_PASS_BEGIN (DependenceAnalysisWrapperPass, "da", "Dependence Analysis", true, true) INITIALIZE_PASS_END(DependenceAnalysisWrapperPass
static void	dumpExampleDependence (raw_ostream &OS, DependenceInfo *DA, ScalarEvolution &SE, LoopInfo &LI, bool NormalizeResults)
static AliasResult	underlyingObjectsAlias (AAResults *AA, const DataLayout &DL, const MemoryLocation &LocA, const MemoryLocation &LocB)
static bool	isLoadOrStore (const Instruction *I)
static const SCEV *	minusSCEVNoSignedOverflow (const SCEV A, const SCEV B, ScalarEvolution &SE)
	Returns A - B if it guaranteed not to signed wrap.
static const SCEV *	mulSCEVNoSignedOverflow (const SCEV A, const SCEV B, ScalarEvolution &SE)
	Returns A * B if it guaranteed not to signed wrap.
static const SCEV *	absSCEVNoSignedOverflow (const SCEV *A, ScalarEvolution &SE)
	Returns the absolute value of A.
static bool	isDependenceTestEnabled (DependenceTestType Test)
	Returns true iff Test is enabled.
static bool	findGCD (unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y)
static APInt	floorOfQuotient (const APInt &A, const APInt &B)
static APInt	ceilingOfQuotient (const APInt &A, const APInt &B)
static std::pair< std::optional< APInt >, std::optional< APInt > >	inferDomainOfAffine (const APInt &A, const APInt &B, const std::optional< APInt > &UB)
	Given an affine expression of the form A*k + B, where k is an arbitrary integer, infer the possible range of k based on the known range of the affine expression.
static bool	isRemainderZero (const SCEVConstant Dividend, const SCEVConstant Divisor)
static std::optional< APInt >	getConstantCoefficient (const SCEV *Expr)
	Given a SCEVMulExpr, returns its first operand if its first operand is a constant and the product doesn't overflow in a signed sense.
static void	dumpSmallBitVector (SmallBitVector &BV)

Variables
static cl::opt< bool >	Delinearize ("da-delinearize", cl::init(true), cl::Hidden, cl::desc("Try to delinearize array references."))
static cl::opt< bool >	DisableDelinearizationChecks ("da-disable-delinearization-checks", cl::Hidden, cl::desc("Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension."))
static cl::opt< unsigned >	MIVMaxLevelThreshold ("da-miv-max-level-threshold", cl::init(7), cl::Hidden, cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors."))
static cl::opt< DependenceTestType >	EnableDependenceTest ("da-enable-dependence-test", cl::init(DependenceTestType::All), cl::ReallyHidden, cl::desc("Run only specified dependence test routine and disable others. " "The purpose is mainly to exclude the influence of other " "dependence test routines in regression tests. If set to All, all " "dependence test routines are enabled."), cl::values(clEnumValN(DependenceTestType::All, "all", "Enable all dependence test routines."), clEnumValN(DependenceTestType::StrongSIV, "strong-siv", "Enable only Strong SIV test."), clEnumValN(DependenceTestType::WeakCrossingSIV, "weak-crossing-siv", "Enable only Weak-Crossing SIV test."), clEnumValN(DependenceTestType::ExactSIV, "exact-siv", "Enable only Exact SIV test."), clEnumValN(DependenceTestType::WeakZeroSIV, "weak-zero-siv", "Enable only Weak-Zero SIV test."), clEnumValN(DependenceTestType::ExactRDIV, "exact-rdiv", "Enable only Exact RDIV test."), clEnumValN(DependenceTestType::SymbolicRDIV, "symbolic-rdiv", "Enable only Symbolic RDIV test."), clEnumValN(DependenceTestType::GCDMIV, "gcd-miv", "Enable only GCD MIV test."), clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv", "Enable only Banerjee MIV test.")))
static cl::opt< bool >	EnableMonotonicityCheck ("da-enable-monotonicity-check", cl::init(false), cl::Hidden, cl::desc("Check if the subscripts are monotonic. If it's not, dependence " "is reported as unknown."))
static cl::opt< bool >	DumpMonotonicityReport ("da-dump-monotonicity-report", cl::init(false), cl::Hidden, cl::desc("When printing analysis, dump the results of monotonicity checks."))
	da
Dependence	Analysis
Dependence	true

◆ DEBUG_TYPE

◆ absSCEVNoSignedOverflow()

Returns the absolute value of A.

In the context of dependence analysis, we need an absolute value in a mathematical sense. If A is the signed minimum value, we cannot represent it unless extending the original type. Thus if we cannot prove that A is not the signed minimum value, returns nullptr.

Definition at line 1221 of file DependenceAnalysis.cpp.

References A(), llvm::cast(), llvm::ScalarEvolution::getAbsExpr(), llvm::ScalarEvolution::getConstant(), llvm::APInt::getSignedMinValue(), llvm::CmpInst::ICMP_NE, llvm::ScalarEvolution::isKnownPredicate(), and llvm::SMin.

◆ ceilingOfQuotient()

◆ dumpExampleDependence()

Definition at line 386 of file DependenceAnalysis.cpp.

References assert(), D(), DumpMonotonicityReport, llvm::Dependence::DVEntry::EQ, F, llvm::getLoadStorePointerOperand(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::ScalarEvolution::getSCEVAtScope(), llvm::raw_ostream::indent(), llvm::inst_begin(), llvm::inst_end(), instructions, llvm::isa(), llvm::SCEV::isZero(), and llvm::ScalarEvolution::removePointerBase().

Referenced by llvm::DependenceAnalysisWrapperPass::print(), and llvm::DependenceAnalysisPrinterPass::run().

◆ dumpSmallBitVector()

◆ findGCD()

◆ floorOfQuotient()

◆ getConstantCoefficient()

std::optional< APInt > getConstantCoefficient ( const SCEV * Expr)	static

Given a SCEVMulExpr, returns its first operand if its first operand is a constant and the product doesn't overflow in a signed sense.

Otherwise, returns std::nullopt. For example, given (10 * X * Y), it returns 10. Notably, if it doesn't have nsw, the multiplication may overflow, and if so, it may not a multiple of 10.

Definition at line 2498 of file DependenceAnalysis.cpp.

References llvm::dyn_cast().

◆ inferDomainOfAffine()

Given an affine expression of the form A*k + B, where k is an arbitrary integer, infer the possible range of k based on the known range of the affine expression.

If we know A*k + B is non-negative, i.e.,

A*k + B >= 0

we can derive the following inequalities for k when A is positive:

k >= -B / A

Since k is an integer, it means k is greater than or equal to the ceil(-B / A).

If the upper bound of the affine expression UB is passed, the following inequality can be derived as well:

A*k + B <= UB

which leads to:

k <= (UB - B) / A

Again, as k is an integer, it means k is less than or equal to the floor((UB - B) / A).

The similar logic applies when A is negative, but the inequalities sign flip while working with them.

Preconditions: A is non-zero, and we know A*k + B is non-negative.

Definition at line 1666 of file DependenceAnalysis.cpp.

References A(), assert(), B(), ceilingOfQuotient(), llvm::dbgs(), floorOfQuotient(), and LLVM_DEBUG.

◆ INITIALIZE_PASS_BEGIN()

◆ isDependenceTestEnabled()

bool isDependenceTestEnabled ( DependenceTestType Test)	static

◆ isLoadOrStore()

◆ isRemainderZero()

◆ minusSCEVNoSignedOverflow()

◆ mulSCEVNoSignedOverflow()

◆ STATISTIC() [1/27]

STATISTIC	(	BanerjeeApplications	,
"Banerjee applications"	)

◆ STATISTIC() [2/27]

STATISTIC	(	BanerjeeIndependence	,
"Banerjee independence"	)

◆ STATISTIC() [3/27]

STATISTIC	(	BanerjeeSuccesses	,
"Banerjee successes"	)

◆ STATISTIC() [4/27]

STATISTIC	(	ExactRDIVapplications	,
"Exact RDIV applications"	)

◆ STATISTIC() [5/27]

STATISTIC	(	ExactRDIVindependence	,
"Exact RDIV independence"	)

◆ STATISTIC() [6/27]

STATISTIC	(	ExactSIVapplications	,
"Exact SIV applications"	)

◆ STATISTIC() [7/27]

STATISTIC	(	ExactSIVindependence	,
"Exact SIV independence"	)

◆ STATISTIC() [8/27]

STATISTIC	(	ExactSIVsuccesses	,
"Exact SIV successes"	)

◆ STATISTIC() [9/27]

STATISTIC	(	GCDapplications	,
"GCD applications"	)

◆ STATISTIC() [10/27]

STATISTIC	(	GCDindependence	,
"GCD independence"	)

◆ STATISTIC() [11/27]

STATISTIC	(	GCDsuccesses	,
"GCD successes"	)

◆ STATISTIC() [12/27]

STATISTIC	(	NonlinearSubscriptPairs	,
"Nonlinear subscript pairs"	)

◆ STATISTIC() [13/27]

STATISTIC	(	SameSDLoopsCount	,
"Loops with Same iteration Space and Depth"	)

◆ STATISTIC() [14/27]

STATISTIC	(	StrongSIVapplications	,
"Strong SIV applications"	)

◆ STATISTIC() [15/27]

STATISTIC	(	StrongSIVindependence	,
"Strong SIV independence"	)

◆ STATISTIC() [16/27]

STATISTIC	(	StrongSIVsuccesses	,
"Strong SIV successes"	)

◆ STATISTIC() [17/27]

STATISTIC	(	SymbolicRDIVapplications	,
"Symbolic RDIV applications"	)

◆ STATISTIC() [18/27]

STATISTIC	(	SymbolicRDIVindependence	,
"Symbolic RDIV independence"	)

◆ STATISTIC() [19/27]

STATISTIC	(	TotalArrayPairs	,
"Array pairs tested"	)

◆ STATISTIC() [20/27]

STATISTIC	(	WeakCrossingSIVapplications	,
"Weak-Crossing SIV applications"	)

◆ STATISTIC() [21/27]

STATISTIC	(	WeakCrossingSIVindependence	,
"Weak-Crossing SIV independence"	)

◆ STATISTIC() [22/27]

STATISTIC	(	WeakCrossingSIVsuccesses	,
"Weak-Crossing SIV successes"	)

◆ STATISTIC() [23/27]

STATISTIC	(	WeakZeroSIVapplications	,
"Weak-Zero SIV applications"	)

◆ STATISTIC() [24/27]

STATISTIC	(	WeakZeroSIVindependence	,
"Weak-Zero SIV independence"	)

◆ STATISTIC() [25/27]

STATISTIC	(	WeakZeroSIVsuccesses	,
"Weak-Zero SIV successes"	)

◆ STATISTIC() [26/27]

STATISTIC	(	ZIVapplications	,
"ZIV applications"	)

◆ STATISTIC() [27/27]

STATISTIC	(	ZIVindependence	,
"ZIV independence"	)

◆ underlyingObjectsAlias()

Definition at line 763 of file DependenceAnalysis.cpp.

References llvm::MemoryLocation::AATags, DL, llvm::BatchAAResults::enableCrossIterationMode(), llvm::MemoryLocation::getBeforeOrAfter(), llvm::getUnderlyingObject(), llvm::isIdentifiedObject(), llvm::BatchAAResults::isNoAlias(), llvm::AliasResult::MayAlias, llvm::AliasResult::MustAlias, llvm::AliasResult::NoAlias, and llvm::MemoryLocation::Ptr.

Referenced by llvm::DependenceInfo::depends().

◆ da

◆ Delinearize

cl::opt< bool > Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::desc("Try to delinearize array references.")) ( "da-delinearize" , cl::init(true) , cl::Hidden , cl::desc("Try to delinearize array references.") )	static

◆ DisableDelinearizationChecks

cl::opt< bool > DisableDelinearizationChecks("da-disable-delinearization-checks", cl::Hidden, cl::desc( "Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension.")) ( "da-disable-delinearization-checks" , cl::Hidden , cl::desc( "Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension.") )

static

◆ DumpMonotonicityReport

cl::opt< bool > DumpMonotonicityReport("da-dump-monotonicity-report", cl::init(false), cl::Hidden, cl::desc( "When printing analysis, dump the results of monotonicity checks.")) ( "da-dump-monotonicity-report" , cl::init(false) , cl::Hidden , cl::desc( "When printing analysis, dump the results of monotonicity checks.") )	static

◆ EnableDependenceTest

cl::opt< DependenceTestType > EnableDependenceTest("da-enable-dependence-test", cl::init(DependenceTestType::All), cl::ReallyHidden, cl::desc("Run only specified dependence test routine and disable others. " "The purpose is mainly to exclude the influence of other " "dependence test routines in regression tests. If set to All, all " "dependence test routines are enabled."), cl::values(clEnumValN(DependenceTestType::All, "all", "Enable all dependence test routines."), clEnumValN(DependenceTestType::StrongSIV, "strong-siv", "Enable only Strong SIV test."), clEnumValN(DependenceTestType::WeakCrossingSIV, "weak-crossing-siv", "Enable only Weak-Crossing SIV test."), clEnumValN(DependenceTestType::ExactSIV, "exact-siv", "Enable only Exact SIV test."), clEnumValN(DependenceTestType::WeakZeroSIV, "weak-zero-siv", "Enable only Weak-Zero SIV test."), clEnumValN(DependenceTestType::ExactRDIV, "exact-rdiv", "Enable only Exact RDIV test."), clEnumValN(DependenceTestType::SymbolicRDIV, "symbolic-rdiv", "Enable only Symbolic RDIV test."), clEnumValN(DependenceTestType::GCDMIV, "gcd-miv", "Enable only GCD MIV test."), clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv", "Enable only Banerjee MIV test."))) ( "da-enable-dependence-test" , cl::init(DependenceTestType::All) , cl::ReallyHidden , cl::desc("Run only specified dependence test routine and disable others. " "The purpose is mainly to exclude the influence of other " "dependence test routines in regression tests. If set to All, all " "dependence test routines are enabled.") , cl::values(clEnumValN(DependenceTestType::All, "all", "Enable all dependence test routines."), clEnumValN(DependenceTestType::StrongSIV, "strong-siv", "Enable only Strong SIV test."), clEnumValN(DependenceTestType::WeakCrossingSIV, "weak-crossing-siv", "Enable only Weak-Crossing SIV test."), clEnumValN(DependenceTestType::ExactSIV, "exact-siv", "Enable only Exact SIV test."), clEnumValN(DependenceTestType::WeakZeroSIV, "weak-zero-siv", "Enable only Weak-Zero SIV test."), clEnumValN(DependenceTestType::ExactRDIV, "exact-rdiv", "Enable only Exact RDIV test."), clEnumValN(DependenceTestType::SymbolicRDIV, "symbolic-rdiv", "Enable only Symbolic RDIV test."), clEnumValN(DependenceTestType::GCDMIV, "gcd-miv", "Enable only GCD MIV test."), clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv", "Enable only Banerjee MIV test.")) )