Checks memory dependences among accesses to the same underlying object to determine whether there vectorization is legal or not (and at which vectorization factor). More...

#include "llvm/Analysis/LoopAccessAnalysis.h"

Classes
struct	Dependence
	Dependece between memory access instructions. More...

Public Types
enum class	VectorizationSafetyStatus { Safe , PossiblySafeWithRtChecks , Unsafe }
	Type to keep track of the status of the dependence check. More...
typedef PointerIntPair< Value *, 1, bool >	MemAccessInfo
typedef SmallVector< MemAccessInfo, 8 >	MemAccessInfoList
typedef EquivalenceClasses< MemAccessInfo >	DepCandidates
	Set of potential dependent memory accesses.

Public Member Functions
	MemoryDepChecker (PredicatedScalarEvolution &PSE, AssumptionCache AC, DominatorTree DT, const Loop L, const DenseMap< Value , const SCEV * > &SymbolicStrides, unsigned MaxTargetVectorWidthInBits, std::optional< ScalarEvolution::LoopGuards > &LoopGuards)
LLVM_ABI void	addAccess (StoreInst *SI)
	Register the location (instructions are given increasing numbers) of a write access.
LLVM_ABI void	addAccess (LoadInst *LI)
	Register the location (instructions are given increasing numbers) of a write access.
LLVM_ABI bool	areDepsSafe (const DepCandidates &AccessSets, const MemAccessInfoList &CheckDeps)
	Check whether the dependencies between the accesses are safe, and records the dependence information in Dependences if so.
bool	isSafeForVectorization () const
	No memory dependence was encountered that would inhibit vectorization.
bool	isSafeForAnyVectorWidth () const
	Return true if the number of elements that are safe to operate on simultaneously is not bounded.
uint64_t	getMaxSafeVectorWidthInBits () const
	Return the number of elements that are safe to operate on simultaneously, multiplied by the size of the element in bits.
bool	isSafeForAnyStoreLoadForwardDistances () const
	Return true if there are no store-load forwarding dependencies.
uint64_t	getStoreLoadForwardSafeDistanceInBits () const
	Return safe power-of-2 number of elements, which do not prevent store-load forwarding, multiplied by the size of the elements in bits.
bool	shouldRetryWithRuntimeChecks () const
	In same cases when the dependency check fails we can still vectorize the loop with a dynamic array access check.
const SmallVectorImpl< Dependence > *	getDependences () const
	Returns the memory dependences.
void	clearDependences ()
const SmallVectorImpl< Instruction * > &	getMemoryInstructions () const
	The vector of memory access instructions.
DenseMap< Instruction *, unsigned >	generateInstructionOrderMap () const
	Generate a mapping between the memory instructions and their indices according to program order.
LLVM_ABI SmallVector< Instruction *, 4 >	getInstructionsForAccess (Value *Ptr, bool isWrite) const
	Find the set of instructions that read or write via `Ptr`.
ArrayRef< unsigned >	getOrderForAccess (Value *Ptr, bool IsWrite) const
	Return the program order indices for the access location (Ptr, IsWrite).
const Loop *	getInnermostLoop () const
DenseMap< std::pair< const SCEV , Type >, std::pair< const SCEV , const SCEV > > &	getPointerBounds ()
DominatorTree *	getDT () const
AssumptionCache *	getAC () const

Detailed Description

Checks memory dependences among accesses to the same underlying object to determine whether there vectorization is legal or not (and at which vectorization factor).

Note: This class will compute a conservative dependence for access to different underlying pointers. Clients, such as the loop vectorizer, will sometimes deal these potential dependencies by emitting runtime checks.

We use the ScalarEvolution framework to symbolically evalutate access functions pairs. Since we currently don't restructure the loop we can rely on the program order of memory accesses to determine their safety. At the moment we will only deem accesses as safe for:

A negative constant distance assuming program order.

Safe: tmp = a[i + 1]; OR a[i + 1] = x; a[i] = tmp; y = a[i];

The latter case is safe because later checks guarantuee that there can't be a cycle through a phi node (that is, we check that "x" and "y" is not the same variable: a header phi can only be an induction or a reduction, a reduction can't have a memory sink, an induction can't have a memory source). This is important and must not be violated (or we have to resort to checking for cycles through memory).
A positive constant distance assuming program order that is bigger than the biggest memory access.

tmp = a[i] OR b[i] = x a[i+2] = tmp y = b[i+2];

Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
Zero distances and all accesses have the same size.

Definition at line 91 of file LoopAccessAnalysis.h.

Member Typedef Documentation

◆ DepCandidates

typedef EquivalenceClasses<MemAccessInfo> llvm::MemoryDepChecker::DepCandidates

Set of potential dependent memory accesses.

Definition at line 96 of file LoopAccessAnalysis.h.

◆ MemAccessInfo

typedef PointerIntPair<Value *, 1, bool> llvm::MemoryDepChecker::MemAccessInfo

Definition at line 93 of file LoopAccessAnalysis.h.

◆ MemAccessInfoList

typedef SmallVector<MemAccessInfo, 8> llvm::MemoryDepChecker::MemAccessInfoList

Definition at line 94 of file LoopAccessAnalysis.h.

Member Enumeration Documentation

◆ VectorizationSafetyStatus

enum class llvm::MemoryDepChecker::VectorizationSafetyStatus

strong

Type to keep track of the status of the dependence check.

The order of the elements is important and has to be from most permissive to least permissive.

Enumerator
Safe
PossiblySafeWithRtChecks
Unsafe

Definition at line 101 of file LoopAccessAnalysis.h.

Constructor & Destructor Documentation

◆ MemoryDepChecker()

llvm::MemoryDepChecker::MemoryDepChecker	(	PredicatedScalarEvolution &	PSE,
		AssumptionCache *	AC,
		DominatorTree *	DT,
		const Loop *	L,
		const DenseMap< Value , const SCEV > &	SymbolicStrides,
		unsigned	MaxTargetVectorWidthInBits,
		std::optional< ScalarEvolution::LoopGuards > &	LoopGuards )

inline

Definition at line 183 of file LoopAccessAnalysis.h.

Referenced by llvm::MemoryDepChecker::Dependence::getDestination(), and llvm::MemoryDepChecker::Dependence::getSource().

Member Function Documentation

◆ addAccess() [1/2]

void MemoryDepChecker::addAccess ( LoadInst * LI )

Register the location (instructions are given increasing numbers) of a write access.

Definition at line 1764 of file LoopAccessAnalysis.cpp.

References llvm::LoadInst::getPointerOperand(), Ptr, and visitPointers().

◆ addAccess() [2/2]

void MemoryDepChecker::addAccess ( StoreInst * SI )

Register the location (instructions are given increasing numbers) of a write access.

Definition at line 1755 of file LoopAccessAnalysis.cpp.

References Ptr, and visitPointers().

◆ areDepsSafe()

bool MemoryDepChecker::areDepsSafe	(	const DepCandidates &	AccessSets,
		const MemAccessInfoList &	CheckDeps )

Check whether the dependencies between the accesses are safe, and records the dependence information in Dependences if so.

Only checks sets with elements in CheckDeps.

Definition at line 2339 of file LoopAccessAnalysis.cpp.

References A(), assert(), B(), llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::dbgs(), llvm::EquivalenceClasses< ElemTy >::findLeader(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::MemoryDepChecker::Dependence::isSafeForVectorization(), isSafeForVectorization(), LLVM_DEBUG, MaxDependences, llvm::EquivalenceClasses< ElemTy >::member_end(), llvm::MemoryDepChecker::Dependence::NoDep, and std::swap().

◆ clearDependences()

void llvm::MemoryDepChecker::clearDependences ( )

inline

Definition at line 255 of file LoopAccessAnalysis.h.

◆ generateInstructionOrderMap()

DenseMap< Instruction *, unsigned > llvm::MemoryDepChecker::generateInstructionOrderMap ( ) const

inline

Generate a mapping between the memory instructions and their indices according to program order.

Definition at line 265 of file LoopAccessAnalysis.h.

References I.

◆ getAC()

AssumptionCache * llvm::MemoryDepChecker::getAC ( ) const

inline

Definition at line 299 of file LoopAccessAnalysis.h.

References assert().

◆ getDependences()

const SmallVectorImpl< Dependence > * llvm::MemoryDepChecker::getDependences ( ) const

inline

Returns the memory dependences.

If null is returned we exceeded the MaxDependences threshold and this information is not available.

Definition at line 251 of file LoopAccessAnalysis.h.

◆ getDT()

DominatorTree * llvm::MemoryDepChecker::getDT ( ) const

inline

Definition at line 295 of file LoopAccessAnalysis.h.

References assert().

◆ getInnermostLoop()

const Loop * llvm::MemoryDepChecker::getInnermostLoop ( ) const

inline

Definition at line 287 of file LoopAccessAnalysis.h.

◆ getInstructionsForAccess()

SmallVector< Instruction *, 4 > MemoryDepChecker::getInstructionsForAccess	(	Value *	Ptr,
		bool	isWrite ) const

Find the set of instructions that read or write via Ptr.

Definition at line 2413 of file LoopAccessAnalysis.cpp.

References Access, I, Ptr, and llvm::transform().

◆ getMaxSafeVectorWidthInBits()

uint64_t llvm::MemoryDepChecker::getMaxSafeVectorWidthInBits ( ) const

inline

Return the number of elements that are safe to operate on simultaneously, multiplied by the size of the element in bits.

Definition at line 222 of file LoopAccessAnalysis.h.

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

◆ getMemoryInstructions()

const SmallVectorImpl< Instruction * > & llvm::MemoryDepChecker::getMemoryInstructions ( ) const

inline

The vector of memory access instructions.

The indices are used as instruction identifiers in the Dependence class.

Definition at line 259 of file LoopAccessAnalysis.h.

Referenced by llvm::MemoryDepChecker::Dependence::getDestination(), and llvm::MemoryDepChecker::Dependence::getSource().

◆ getOrderForAccess()

ArrayRef< unsigned > llvm::MemoryDepChecker::getOrderForAccess	(	Value *	Ptr,
		bool	IsWrite ) const

inline

Return the program order indices for the access location (Ptr, IsWrite).

Returns an empty ArrayRef if there are no accesses for the location.

Definition at line 280 of file LoopAccessAnalysis.h.

References I, and Ptr.

◆ getPointerBounds()

DenseMap< std::pair< const SCEV *, Type * >, std::pair< const SCEV *, const SCEV * > > & llvm::MemoryDepChecker::getPointerBounds ( )

inline

Definition at line 291 of file LoopAccessAnalysis.h.

◆ getStoreLoadForwardSafeDistanceInBits()

uint64_t llvm::MemoryDepChecker::getStoreLoadForwardSafeDistanceInBits ( ) const

inline

Return safe power-of-2 number of elements, which do not prevent store-load forwarding, multiplied by the size of the elements in bits.

Definition at line 234 of file LoopAccessAnalysis.h.

References assert(), and isSafeForAnyStoreLoadForwardDistances().

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

◆ isSafeForAnyStoreLoadForwardDistances()

bool llvm::MemoryDepChecker::isSafeForAnyStoreLoadForwardDistances ( ) const

inline

Return true if there are no store-load forwarding dependencies.

Definition at line 227 of file LoopAccessAnalysis.h.

Referenced by getStoreLoadForwardSafeDistanceInBits(), and llvm::LoopAccessInfo::print().

◆ isSafeForAnyVectorWidth()

bool llvm::MemoryDepChecker::isSafeForAnyVectorWidth ( ) const

inline

Return true if the number of elements that are safe to operate on simultaneously is not bounded.

Definition at line 216 of file LoopAccessAnalysis.h.

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

◆ isSafeForVectorization()

bool llvm::MemoryDepChecker::isSafeForVectorization ( ) const

inline

No memory dependence was encountered that would inhibit vectorization.

Definition at line 210 of file LoopAccessAnalysis.h.

References Safe.

Referenced by areDepsSafe().

◆ shouldRetryWithRuntimeChecks()

bool llvm::MemoryDepChecker::shouldRetryWithRuntimeChecks ( ) const

inline

In same cases when the dependency check fails we can still vectorize the loop with a dynamic array access check.

Definition at line 243 of file LoopAccessAnalysis.h.

References PossiblySafeWithRtChecks.

The documentation for this class was generated from the following files:

include/llvm/Analysis/LoopAccessAnalysis.h
lib/Analysis/LoopAccessAnalysis.cpp

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ DepCandidates

◆ MemAccessInfo

◆ MemAccessInfoList

Member Enumeration Documentation

◆ VectorizationSafetyStatus

Constructor & Destructor Documentation

◆ MemoryDepChecker()

Member Function Documentation

◆ addAccess() [1/2]

◆ addAccess() [2/2]

◆ areDepsSafe()

◆ clearDependences()

◆ generateInstructionOrderMap()

◆ getAC()

◆ getDependences()

◆ getDT()

◆ getInnermostLoop()

◆ getInstructionsForAccess()

◆ getMaxSafeVectorWidthInBits()

◆ getMemoryInstructions()

◆ getOrderForAccess()

◆ getPointerBounds()

◆ getStoreLoadForwardSafeDistanceInBits()

◆ isSafeForAnyStoreLoadForwardDistances()

◆ isSafeForAnyVectorWidth()

◆ isSafeForVectorization()

◆ shouldRetryWithRuntimeChecks()