LoopAccessAnalysis.cpp File Reference (original) (raw)

Go to the source code of this file.

Functions
static std::pair< const SCEV , const SCEV >	getStartAndEndForAccess (const Loop Lp, const SCEV PtrExpr, Type AccessTy, PredicatedScalarEvolution &PSE, DenseMap< std::pair< const SCEV , Type * >, std::pair< const SCEV , const SCEV > > &PointerBounds)
	Calculate Start and End points of memory access.

static const SCEV *	getMinFromExprs (const SCEV I, const SCEV J, ScalarEvolution *SE)
	Compare I and J and return the minimum.

static bool	hasComputableBounds (PredicatedScalarEvolution &PSE, Value Ptr, const SCEV PtrScev, Loop *L, bool Assume)
	Check whether a pointer can participate in a runtime bounds check.

static bool	isNoWrap (PredicatedScalarEvolution &PSE, const DenseMap< Value , const SCEV > &Strides, Value Ptr, Type AccessTy, Loop *L, bool Assume)
	Check whether a pointer address cannot wrap.

static void	visitPointers (Value StartPtr, const Loop &InnermostLoop, function_ref< void(Value )> AddPointer)

static void	findForkedSCEVs (ScalarEvolution SE, const Loop L, Value Ptr, SmallVectorImpl< PointerIntPair< const SCEV , 1, bool > > &ScevList, unsigned Depth)

static SmallVector< PointerIntPair< const SCEV *, 1, bool > >	findForkedPointer (PredicatedScalarEvolution &PSE, const DenseMap< Value , const SCEV > &StridesMap, Value Ptr, const Loop L)

static bool	isNoWrapAddRec (Value Ptr, const SCEVAddRecExpr AR, PredicatedScalarEvolution &PSE, const Loop *L)
	Return true if an AddRec pointer Ptr is unsigned non-wrapping, i.e.

static bool	isSafeDependenceDistance (const DataLayout &DL, ScalarEvolution &SE, const SCEV &MaxBTC, const SCEV &Dist, uint64_t MaxStride, uint64_t TypeByteSize)
	Given a dependence-distance Dist between two memory accesses, that have strides in the same direction whose absolute value of the maximum stride is given in MaxStride, and that have the same type size TypeByteSize, in a loop whose maximum backedge taken count is MaxBTC, check if it is possible to prove statically that the dependence distance is larger than the range that the accesses will travel through the execution of the loop.

static bool	areStridedAccessesIndependent (uint64_t Distance, uint64_t Stride, uint64_t TypeByteSize)
	Check the dependence for two accesses with the same stride Stride.

static unsigned	getGEPInductionOperand (const GetElementPtrInst *Gep)
	Find the operand of the GEP that should be checked for consecutive stores.

static Value *	stripGetElementPtr (Value Ptr, ScalarEvolution SE, Loop *Lp)
	If the argument is a GEP, then returns the operand identified by getGEPInductionOperand.

static const SCEV *	getStrideFromPointer (Value Ptr, ScalarEvolution SE, Loop *Lp)
	Get the stride of a pointer access in a loop.

Variables
static cl::opt< unsigned, true >	VectorizationFactor ("force-vector-width", cl::Hidden, cl::desc("Sets the SIMD width. Zero is autoselect."), cl::location(VectorizerParams::VectorizationFactor))

static cl::opt< unsigned, true >	VectorizationInterleave ("force-vector-interleave", cl::Hidden, cl::desc("Sets the vectorization interleave count. " "Zero is autoselect."), cl::location(VectorizerParams::VectorizationInterleave))

static cl::opt< unsigned, true >	RuntimeMemoryCheckThreshold ("runtime-memory-check-threshold", cl::Hidden, cl::desc("When performing memory disambiguation checks at runtime do not " "generate more than this number of comparisons (default = 8)."), cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8))

static cl::opt< unsigned >	MemoryCheckMergeThreshold ("memory-check-merge-threshold", cl::Hidden, cl::desc("Maximum number of comparisons done when trying to merge " "runtime memory checks. (default = 100)"), cl::init(100))
	The maximum iterations used to merge memory checks.

static cl::opt< unsigned >	MaxDependences ("max-dependences", cl::Hidden, cl::desc("Maximum number of dependences collected by " "loop-access analysis (default = 100)"), cl::init(100))
	We collect dependences up to this threshold.

static cl::opt< bool >	EnableMemAccessVersioning ("enable-mem-access-versioning", cl::init(true), cl::Hidden, cl::desc("Enable symbolic stride memory access versioning"))
	This enables versioning on the strides of symbolically striding memory accesses in code like the following.

static cl::opt< bool >	EnableForwardingConflictDetection ("store-to-load-forwarding-conflict-detection", cl::Hidden, cl::desc("Enable conflict detection in loop-access analysis"), cl::init(true))
	Enable store-to-load forwarding conflict detection.

static cl::opt< unsigned >	MaxForkedSCEVDepth ("max-forked-scev-depth", cl::Hidden, cl::desc("Maximum recursion depth when finding forked SCEVs (default = 5)"), cl::init(5))

static cl::opt< bool >	SpeculateUnitStride ("laa-speculate-unit-stride", cl::Hidden, cl::desc("Speculate that non-constant strides are unit in LAA"), cl::init(true))

static cl::opt< bool, true >	HoistRuntimeChecks ("hoist-runtime-checks", cl::Hidden, cl::desc("Hoist inner loop runtime memory checks to outer loop if possible"), cl::location(VectorizerParams::HoistRuntimeChecks), cl::init(true))

◆ DEBUG_TYPE

#define DEBUG_TYPE "loop-accesses"

◆ areStridedAccessesIndependent()

Check the dependence for two accesses with the same stride Stride.

Distance is the positive distance and TypeByteSize is type size in bytes.

Returns

true if they are independent.

Definition at line 1857 of file LoopAccessAnalysis.cpp.

References assert().

◆ findForkedPointer()

Definition at line 1033 of file LoopAccessAnalysis.cpp.

References assert(), llvm::dbgs(), findForkedSCEVs(), llvm::PredicatedScalarEvolution::getSE(), llvm::ScalarEvolution::isLoopInvariant(), llvm::ScalarEvolution::isSCEVable(), LLVM_DEBUG, MaxForkedSCEVDepth, Ptr, llvm::replaceSymbolicStrideSCEV(), and llvm::SmallVectorBase< Size_T >::size().

◆ findForkedSCEVs()

Definition at line 878 of file LoopAccessAnalysis.cpp.

References llvm::any_of(), llvm::dbgs(), llvm::Depth, findForkedSCEVs(), GEP, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getEffectiveSCEVType(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::getSizeOfExpr(), llvm::ScalarEvolution::getTruncateOrSignExtend(), llvm::SCEV::getType(), I, llvm::isGuaranteedNotToBeUndefOrPoison(), llvm::Type::isVectorTy(), LLVM_DEBUG, llvm_unreachable, Ptr, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorBase< Size_T >::size(), and Size.

Referenced by findForkedPointer(), and findForkedSCEVs().

◆ getGEPInductionOperand()

Find the operand of the GEP that should be checked for consecutive stores.

This ignores trailing indices that have no effect on the final pointer.

Definition at line 2824 of file LoopAccessAnalysis.cpp.

References DL, llvm::gep_type_begin(), llvm::Instruction::getDataLayout(), llvm::generic_gep_type_iterator< ItTy >::getIndexedType(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::GetElementPtrInst::getResultElementType(), llvm::generic_gep_type_iterator< ItTy >::getSequentialElementStride(), llvm::generic_gep_type_iterator< ItTy >::isStruct(), llvm::PatternMatch::m_Zero(), and llvm::PatternMatch::match().

Referenced by stripGetElementPtr().

◆ getMinFromExprs()

◆ getStartAndEndForAccess()

Calculate Start and End points of memory access.

Let's assume A is the first access and B is a memory access on N-th loop iteration. Then B is calculated as: B = A + Step*N . Step value may be positive or negative. N is a calculated back-edge taken count: N = (TripCount > 0) ? RoundDown(TripCount -1 , VF) : 0 Start and End points are calculated in the following way: Start = UMIN(A, B) ; End = UMAX(A, B) + SizeOfElt, where SizeOfElt is the size of single memory access in bytes.

There is no conflict when the intervals are disjoint: NoConflict = (P2.Start >= P1.End) || (P1.Start >= P2.End)

Definition at line 206 of file LoopAccessAnalysis.cpp.

References assert(), DL, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::BasicBlock::getDataLayout(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PredicatedScalarEvolution::getSE(), llvm::ScalarEvolution::getStoreSizeOfExpr(), llvm::PredicatedScalarEvolution::getSymbolicMaxBackedgeTakenCount(), llvm::SCEV::getType(), llvm::ScalarEvolution::getUMaxExpr(), llvm::ScalarEvolution::getUMinExpr(), llvm::ScalarEvolution::isLoopInvariant(), and std::swap().

Referenced by llvm::RuntimePointerChecking::insert().

◆ getStrideFromPointer()

Get the stride of a pointer access in a loop.

Looks for symbolic strides "a[i*stride]". Returns the symbolic stride, or null otherwise.

Definition at line 2869 of file LoopAccessAnalysis.cpp.

References llvm::CallingConv::C, llvm::APInt::getBitWidth(), llvm::SCEVAddRecExpr::getLoop(), llvm::ScalarEvolution::getSCEV(), llvm::APInt::getSExtValue(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::ScalarEvolution::isLoopInvariant(), Ptr, llvm::scConstant, and stripGetElementPtr().

◆ hasComputableBounds()

◆ isNoWrap()

◆ isNoWrapAddRec()

◆ isSafeDependenceDistance()

Given a dependence-distance Dist between two memory accesses, that have strides in the same direction whose absolute value of the maximum stride is given in MaxStride, and that have the same type size TypeByteSize, in a loop whose maximum backedge taken count is MaxBTC, check if it is possible to prove statically that the dependence distance is larger than the range that the accesses will travel through the execution of the loop.

If so, return true; false otherwise. This is useful for example in loops such as the following (PR31098): for (i = 0; i < D; ++i) { = out[i]; out[i+D] = }

Definition at line 1800 of file LoopAccessAnalysis.cpp.

References DL, llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getNegativeSCEV(), llvm::ScalarEvolution::getNoopOrSignExtend(), llvm::SCEV::getType(), llvm::ScalarEvolution::getZeroExtendExpr(), llvm::ScalarEvolution::isKnownPositive(), and llvm::Minus.

◆ stripGetElementPtr()

◆ visitPointers()

◆ EnableForwardingConflictDetection

cl::opt< bool > EnableForwardingConflictDetection("store-to-load-forwarding-conflict-detection", cl::Hidden, cl::desc("Enable conflict detection in loop-access analysis"), cl::init(true)) ( "store-to-load-forwarding-conflict-detection" , cl::Hidden , cl::desc("Enable conflict detection in loop-access analysis") , cl::init(true) )	static

Enable store-to-load forwarding conflict detection.

This option can be disabled for correctness testing.

◆ EnableMemAccessVersioning

cl::opt< bool > EnableMemAccessVersioning("enable-mem-access-versioning", cl::init(true), cl::Hidden, cl::desc("Enable symbolic stride memory access versioning")) ( "enable-mem-access-versioning" , cl::init(true) , cl::Hidden , cl::desc("Enable symbolic stride memory access versioning") )	static

This enables versioning on the strides of symbolically striding memory accesses in code like the following.

for (i = 0; i < N; ++i) A[i * Stride1] += B[i * Stride2] ...

Will be roughly translated to if (Stride1 == 1 && Stride2 == 1) { for (i = 0; i < N; i+=4) A[i:i+3] += ... } else ...

◆ HoistRuntimeChecks

cl::opt< bool, true > HoistRuntimeChecks("hoist-runtime-checks", cl::Hidden, cl::desc( "Hoist inner loop runtime memory checks to outer loop if possible"), cl::location(VectorizerParams::HoistRuntimeChecks), cl::init(true)) ( "hoist-runtime-checks" , cl::Hidden , cl::desc( "Hoist inner loop runtime memory checks to outer loop if possible") , cl::location(VectorizerParams::HoistRuntimeChecks) , cl::init(true) )

static

◆ MaxDependences

cl::opt< unsigned > MaxDependences("max-dependences", cl::Hidden, cl::desc("Maximum number of dependences collected by " "loop-access analysis (default = 100)"), cl::init(100)) ( "max-dependences" , cl::Hidden , cl::desc("Maximum number of dependences collected by " "loop-access analysis (default = 100)") , cl::init(100) )	static

◆ MaxForkedSCEVDepth

cl::opt< unsigned > MaxForkedSCEVDepth("max-forked-scev-depth", cl::Hidden, cl::desc("Maximum recursion depth when finding forked SCEVs (default = 5)"), cl::init(5)) ( "max-forked-scev-depth" , cl::Hidden , cl::desc("Maximum recursion depth when finding forked SCEVs (default = 5)") , cl::init(5) )	static

◆ MemoryCheckMergeThreshold

cl::opt< unsigned > MemoryCheckMergeThreshold("memory-check-merge-threshold", cl::Hidden, cl::desc("Maximum number of comparisons done when trying to merge " "runtime memory checks. (default = 100)"), cl::init(100)) ( "memory-check-merge-threshold" , cl::Hidden , cl::desc("Maximum number of comparisons done when trying to merge " "runtime memory checks. (default = 100)") , cl::init(100) )	static

The maximum iterations used to merge memory checks.

◆ RuntimeMemoryCheckThreshold

cl::opt< unsigned, true > RuntimeMemoryCheckThreshold("runtime-memory-check-threshold", cl::Hidden, cl::desc("When performing memory disambiguation checks at runtime do not " "generate more than this number of comparisons (default = 8)."), cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8)) ( "runtime-memory-check-threshold" , cl::Hidden , cl::desc("When performing memory disambiguation checks at runtime do not " "generate more than this number of comparisons (default = 8).") , cl::location(VectorizerParams::RuntimeMemoryCheckThreshold) , cl::init(8) )

static

◆ SpeculateUnitStride

cl::opt< bool > SpeculateUnitStride("laa-speculate-unit-stride", cl::Hidden, cl::desc("Speculate that non-constant strides are unit in LAA"), cl::init(true)) ( "laa-speculate-unit-stride" , cl::Hidden , cl::desc("Speculate that non-constant strides are unit in LAA") , cl::init(true) )	static

◆ VectorizationFactor

cl::opt< unsigned, true > VectorizationFactor("force-vector-width", cl::Hidden, cl::desc("Sets the SIMD width. Zero is autoselect."), cl::location(VectorizerParams::VectorizationFactor)) ( "force-vector-width" , cl::Hidden , cl::desc("Sets the SIMD width. Zero is autoselect.") , cl::location(VectorizerParams::VectorizationFactor) )	static

◆ VectorizationInterleave

cl::opt< unsigned, true > VectorizationInterleave("force-vector-interleave", cl::Hidden, cl::desc("Sets the vectorization interleave count. " "Zero is autoselect."), cl::location( VectorizerParams::VectorizationInterleave)) ( "force-vector-interleave" , cl::Hidden , cl::desc("Sets the vectorization interleave count. " "Zero is autoselect.") , cl::location( VectorizerParams::VectorizationInterleave) )

static