#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <iterator>
#include <utility>
#include <vector>

Namespaces
	llvm
	This class represents lattice values for constants.

Macros
#define	DEBUG_TYPE "loop-accesses"

#define	LAA_NAME "loop-accesses"

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

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

static bool	isNoWrap (PredicatedScalarEvolution &PSE, const ValueToValueMap &Strides, Value Ptr, Loop L)
	Check whether a pointer address cannot wrap. More...

static bool	isInBoundsGep (Value *Ptr)

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. More...

static unsigned	getAddressSpaceOperand (Value *I)
	Take the address space operand from the Load/Store instruction. More...

static bool	isSafeDependenceDistance (const DataLayout &DL, ScalarEvolution &SE, const SCEV &BackedgeTakenCount, const SCEV &Dist, uint64_t Stride, uint64_t TypeByteSize)
	Given a non-constant (unknown) dependence-distance `Dist` between two memory accesses, that have the same stride whose absolute value is given in `Stride`, and that have the same type size `TypeByteSize`, in a loop whose takenCount is `BackedgeTakenCount`, 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. More...

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

static Instruction *	getFirstInst (Instruction FirstInst, Value V, Instruction *Loc)

static PointerBounds	expandBounds (const RuntimePointerChecking::CheckingPtrGroup CG, Loop TheLoop, Instruction Loc, SCEVExpander &Exp, ScalarEvolution SE, const RuntimePointerChecking &PtrRtChecking)
	Expand code for the lower and upper bound of the pointer group `CG` in `TheLoop`. More...

static SmallVector< std::pair< PointerBounds, PointerBounds >, 4 >	expandBounds (const SmallVectorImpl< RuntimePointerChecking::PointerCheck > &PointerChecks, Loop L, Instruction Loc, ScalarEvolution *SE, SCEVExpander &Exp, const RuntimePointerChecking &PtrRtChecking)
	Turns a collection of checks into a collection of expanded upper and lower bounds for both pointers in the check. More...

Pass *	llvm::createLAAPass ()

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. More...

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. More...

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. More...

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. More...

static const char	laa_name [] = "Loop Access Analysis"

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "loop-accesses"

Definition at line 71 of file LoopAccessAnalysis.cpp.

Referenced by llvm::LoopAccessInfo::blockNeedsPredication().

◆ LAA_NAME

#define LAA_NAME "loop-accesses"

Definition at line 2421 of file LoopAccessAnalysis.cpp.

Function Documentation

◆ areStridedAccessesIndependent()

static bool areStridedAccessesIndependent	(	uint64_t	Distance,
		uint64_t	Stride,
		uint64_t	TypeByteSize
	)

static

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 1397 of file LoopAccessAnalysis.cpp.

References llvm::abs(), llvm::APInt::abs(), assert(), B, C, llvm::dbgs(), llvm::dyn_cast(), EnableForwardingConflictDetection, llvm::SCEVConstant::getAPInt(), llvm::Type::getPointerAddressSpace(), llvm::Type::getPointerElementType(), llvm::getPtrStride(), llvm::APInt::getSExtValue(), llvm::Value::getType(), llvm::APInt::getZExtValue(), llvm::APInt::isNegative(), isSafeDependenceDistance(), llvm::APInt::isStrictlyPositive(), LLVM_DEBUG, llvm::max(), llvm::cl::Sink, std::swap(), llvm::Unknown, llvm::VectorizerParams::VectorizationFactor, and llvm::VectorizerParams::VectorizationInterleave.

◆ expandBounds() [1/2]

static PointerBounds expandBounds	(	const RuntimePointerChecking::CheckingPtrGroup *	CG,
		Loop *	TheLoop,
		Instruction *	Loc,
		SCEVExpander &	Exp,
		ScalarEvolution *	SE,
		const RuntimePointerChecking &	PtrRtChecking
	)

static

Expand code for the lower and upper bound of the pointer group CG in TheLoop.

Returns: the values for the bounds.

Definition at line 2124 of file LoopAccessAnalysis.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dbgs(), llvm::dyn_cast(), llvm::SCEVExpander::expandCodeFor(), llvm::ScalarEvolution::getAddExpr(), llvm::Value::getContext(), llvm::Type::getInt8PtrTy(), llvm::ScalarEvolution::getOne(), llvm::Type::getPointerAddressSpace(), llvm::ScalarEvolution::getSCEV(), llvm::Value::getType(), llvm::ScalarEvolution::isLoopInvariant(), LLVM_DEBUG, llvm::RuntimePointerChecking::CheckingPtrGroup::Members, and llvm::RuntimePointerChecking::Pointers.

Referenced by llvm::LoopAccessInfo::addRuntimeChecks(), and expandBounds().

◆ expandBounds() [2/2]

static SmallVector<std::pair<PointerBounds, PointerBounds>, 4> expandBounds	(	const SmallVectorImpl< RuntimePointerChecking::PointerCheck > &	PointerChecks,
		Loop *	L,
		Instruction *	Loc,
		ScalarEvolution *	SE,
		SCEVExpander &	Exp,
		const RuntimePointerChecking &	PtrRtChecking
	)

static

Turns a collection of checks into a collection of expanded upper and lower bounds for both pointers in the check.

Definition at line 2162 of file LoopAccessAnalysis.cpp.

References Check(), expandBounds(), and llvm::transform().

◆ getAddressSpaceOperand()

static unsigned getAddressSpaceOperand ( Value * I )

static

Take the address space operand from the Load/Store instruction.

Returns -1 if this is not a valid Load/Store instruction.

Definition at line 1162 of file LoopAccessAnalysis.cpp.

Referenced by llvm::isConsecutiveAccess().

◆ getFirstInst()

static Instruction* getFirstInst	(	Instruction *	FirstInst,
		Value *	V,
		Instruction *	Loc
	)

static

Definition at line 2099 of file LoopAccessAnalysis.cpp.

References llvm::Instruction::getParent(), and I.

Referenced by llvm::LoopAccessInfo::addRuntimeChecks().

◆ getMinFromExprs()

static const SCEV* getMinFromExprs	(	const SCEV *	I,
		const SCEV *	J,
		ScalarEvolution *	SE
	)

static

Compare I and J and return the minimum.

Return nullptr in case we couldn't find an answer.

Definition at line 267 of file LoopAccessAnalysis.cpp.

References C, llvm::dyn_cast(), llvm::ScalarEvolution::getMinusSCEV(), llvm::SCEVConstant::getValue(), I, and llvm::ConstantInt::isNegative().

◆ hasComputableBounds()

static bool hasComputableBounds	(	PredicatedScalarEvolution &	PSE,
		const ValueToValueMap &	Strides,
		Value *	Ptr,
		Loop *	L,
		bool	Assume
	)

static

Check whether a pointer can participate in a runtime bounds check.

If Assume, try harder to prove that we can compute the bounds of Ptr by adding run-time checks (overflow checks) if necessary.

Definition at line 619 of file LoopAccessAnalysis.cpp.

References llvm::dyn_cast(), llvm::PredicatedScalarEvolution::getAsAddRec(), llvm::PredicatedScalarEvolution::getSE(), llvm::SCEVAddRecExpr::isAffine(), llvm::ScalarEvolution::isLoopInvariant(), and llvm::replaceSymbolicStrideSCEV().

Referenced by isNoWrap().

◆ isInBoundsGep()

static bool isInBoundsGep ( Value * Ptr )

static

Definition at line 935 of file LoopAccessAnalysis.cpp.

References GEP.

Referenced by llvm::getPtrStride().

◆ isNoWrap()

static bool isNoWrap	(	PredicatedScalarEvolution &	PSE,
		const ValueToValueMap &	Strides,
		Value *	Ptr,
		Loop *	L
	)

static

Check whether a pointer address cannot wrap.

Definition at line 640 of file LoopAccessAnalysis.cpp.

References assert(), llvm::dbgs(), llvm::RuntimePointerChecking::generateChecks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::EquivalenceClasses< ElemTy >::getLeaderValue(), llvm::RuntimePointerChecking::getNumberOfChecks(), llvm::BasicBlock::getParent(), llvm::Type::getPointerAddressSpace(), llvm::getPtrStride(), llvm::PredicatedScalarEvolution::getSCEV(), llvm::PredicatedScalarEvolution::getSE(), llvm::Value::getType(), llvm::GlobalValue::getType(), llvm::GetUnderlyingObjects(), hasComputableBounds(), llvm::PredicatedScalarEvolution::hasNoOverflow(), llvm::SCEVWrapPredicate::IncrementNUSW, llvm::EquivalenceClasses< ElemTy >::insert(), llvm::RuntimePointerChecking::insert(), llvm::ScalarEvolution::isLoopInvariant(), LLVM_DEBUG, llvm::RuntimePointerChecking::Need, llvm::NullPointerIsDefined(), llvm::RuntimePointerChecking::Pointers, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::RuntimePointerChecking::reset(), and llvm::EquivalenceClasses< ElemTy >::unionSets().

◆ isNoWrapAddRec()

static bool isNoWrapAddRec	(	Value *	Ptr,
		const SCEVAddRecExpr *	AR,
		PredicatedScalarEvolution &	PSE,
		const Loop *	L
	)

static

Return true if an AddRec pointer Ptr is unsigned non-wrapping, i.e.

monotonically increasing/decreasing.

Definition at line 943 of file LoopAccessAnalysis.cpp.

References llvm::dyn_cast(), llvm::SCEV::FlagNSW, GEP, llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::PredicatedScalarEvolution::getSCEV(), llvm::make_range(), and llvm::SCEV::NoWrapMask.

Referenced by llvm::getPtrStride().

◆ isSafeDependenceDistance()

static bool isSafeDependenceDistance	(	const DataLayout &	DL,
		ScalarEvolution &	SE,
		const SCEV &	BackedgeTakenCount,
		const SCEV &	Dist,
		uint64_t	Stride,
		uint64_t	TypeByteSize
	)

static

Given a non-constant (unknown) dependence-distance Dist between two memory accesses, that have the same stride whose absolute value is given in Stride, and that have the same type size TypeByteSize, in a loop whose takenCount is BackedgeTakenCount, 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 1337 of file LoopAccessAnalysis.cpp.

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

Referenced by areStridedAccessesIndependent().

Variable Documentation

◆ 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))

static

Enable store-to-load forwarding conflict detection.

This option can be disabled for correctness testing.

Referenced by areStridedAccessesIndependent().

◆ EnableMemAccessVersioning

cl::opt<bool> EnableMemAccessVersioning("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 ...

Referenced by llvm::MemoryDepChecker::Dependence::print().

◆ laa_name

const char laa_name[] = "Loop Access Analysis"

static

Definition at line 2420 of file LoopAccessAnalysis.cpp.

◆ 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))

static

We collect dependences up to this threshold.

Referenced by llvm::MemoryDepChecker::areDepsSafe().

◆ 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))

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

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

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

static

Referenced by llvm::VectorizerParams::isInterleaveForced().

Namespaces

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

◆ LAA_NAME

Function Documentation

◆ areStridedAccessesIndependent()

◆ expandBounds() [1/2]

◆ expandBounds() [2/2]

◆ getAddressSpaceOperand()

◆ getFirstInst()

◆ getMinFromExprs()

◆ hasComputableBounds()

◆ isInBoundsGep()

◆ isNoWrap()

◆ isNoWrapAddRec()

◆ isSafeDependenceDistance()

Variable Documentation

◆ EnableForwardingConflictDetection

◆ EnableMemAccessVersioning

◆ laa_name

◆ MaxDependences

◆ MemoryCheckMergeThreshold

◆ RuntimeMemoryCheckThreshold

◆ VectorizationFactor

◆ VectorizationInterleave