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...
using	MemAccessInfo
using	DepCandidates = EquivalenceClasses<MemAccessInfo>
	Set of potential dependent memory accesses.

Public Member Functions
	MemoryDepChecker (PredicatedScalarEvolution &PSE, AssumptionCache AC, DominatorTree DT, const Loop *L, const SymbolicStrideMap &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, ArrayRef< MemAccessInfo > 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 , const SCEV >, std::pair< const SCEV , const SCEV > > &	getPointerBounds ()
DominatorTree *	getDT () const
AssumptionCache *	getAC () const

Static Public Member Functions
static bool	isStoreLoadForwardingConflict (uint64_t Distance, uint64_t VectorStoreSize, uint64_t TypeByteSize, uint64_t LoadElementSize=0)
	Returns true if a memory dependence at byte distance `Distance` between a store (with element size `TypeByteSize` bytes) widened to `VectorStoreSize` bytes and a subsequent load of `LoadElementSize` bytes would prevent store-to-load forwarding.

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 96 of file LoopAccessAnalysis.h.

Member Typedef Documentation

◆ DepCandidates

using llvm::MemoryDepChecker::DepCandidates = EquivalenceClasses<MemAccessInfo>

Set of potential dependent memory accesses.

Definition at line 101 of file LoopAccessAnalysis.h.

◆ MemAccessInfo

using llvm::MemoryDepChecker::MemAccessInfo

Initial value:

PointerIntPair<Value * , 1, bool >

llvm::PointerIntPair

PointerIntPair - This class implements a pair of a pointer and small integer.

Definition PointerIntPair.h:80

Definition at line 98 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 106 of file LoopAccessAnalysis.h.

Constructor & Destructor Documentation

◆ MemoryDepChecker()

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

inline

Definition at line 193 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 1925 of file LoopAccessAnalysis.cpp.

References llvm::LoadInst::getPointerOperand(), 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 1916 of file LoopAccessAnalysis.cpp.

References visitPointers().

◆ areDepsSafe()

bool MemoryDepChecker::areDepsSafe	(	const DepCandidates &	AccessSets,
		ArrayRef< MemAccessInfo >	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 2528 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 296 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 306 of file LoopAccessAnalysis.h.

References I.

◆ getAC()

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

inline

Definition at line 340 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 292 of file LoopAccessAnalysis.h.

◆ getDT()

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

inline

Definition at line 336 of file LoopAccessAnalysis.h.

References assert().

◆ getInnermostLoop()

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

inline

Definition at line 328 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 2603 of file LoopAccessAnalysis.cpp.

References Access, I, 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 232 of file LoopAccessAnalysis.h.

References uint64_t.

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 300 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 321 of file LoopAccessAnalysis.h.

References I.

◆ getPointerBounds()

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

inline

Definition at line 332 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 275 of file LoopAccessAnalysis.h.

References assert(), isSafeForAnyStoreLoadForwardDistances(), and uint64_t.

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 237 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 226 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 220 of file LoopAccessAnalysis.h.

References Safe.

Referenced by areDepsSafe().

◆ isStoreLoadForwardingConflict()

bool llvm::MemoryDepChecker::isStoreLoadForwardingConflict	(	uint64_t	Distance,
		uint64_t	VectorStoreSize,
		uint64_t	TypeByteSize,
		uint64_t	LoadElementSize = 0 )

inlinestatic

Returns true if a memory dependence at byte distance Distance between a store (with element size TypeByteSize bytes) widened to VectorStoreSize bytes and a subsequent load of LoadElementSize bytes would prevent store-to-load forwarding.

The conflicting store must still be likely to be in the store buffer, i.e. Distance / VectorStoreSize is below 8 * TypeByteSize iterations. Given that, the load overruns from the widened store it starts in into the next one when either: (a) it starts misaligned, R = Distance % VectorStoreSize bytes below a widened-store boundary, and is wider than those R bytes (LoadElementSize > R), or (b) it starts aligned (R == 0) but is itself wider than the widened store window (LoadElementSize > VectorStoreSize). A LoadElementSize of 0 (the default) leaves the load width unknown and disables both terms. Passing VectorStoreSize makes (a) reduce to "any misalignment conflicts" and (b) never fire, matching the original, width-agnostic predicate.

Definition at line 260 of file LoopAccessAnalysis.h.

References assert(), and uint64_t.

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

Static Public Member Functions

Detailed Description

Member Typedef Documentation

◆ DepCandidates

◆ MemAccessInfo

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

◆ isStoreLoadForwardingConflict()

◆ shouldRetryWithRuntimeChecks()