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	VectorizationSafetyStatus { VectorizationSafetyStatus::Safe, VectorizationSafetyStatus::PossiblySafeWithRtChecks, VectorizationSafetyStatus::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. More...

Public Member Functions
	MemoryDepChecker (PredicatedScalarEvolution &PSE, const Loop *L)

void	addAccess (StoreInst *SI)
	Register the location (instructions are given increasing numbers) of a write access. More...

void	addAccess (LoadInst *LI)
	Register the location (instructions are given increasing numbers) of a write access. More...

bool	areDepsSafe (DepCandidates &AccessSets, MemAccessInfoList &CheckDeps, const ValueToValueMap &Strides)
	Check whether the dependencies between the accesses are safe. More...

bool	isSafeForVectorization () const
	No memory dependence was encountered that would inhibit vectorization. More...

uint64_t	getMaxSafeDepDistBytes ()
	The maximum number of bytes of a vector register we can vectorize the accesses safely with. More...

uint64_t	getMaxSafeRegisterWidth () const
	Return the number of elements that are safe to operate on simultaneously, multiplied by the size of the element in bits. More...

bool	shouldRetryWithRuntimeCheck () const
	In same cases when the dependency check fails we can still vectorize the loop with a dynamic array access check. More...

const SmallVectorImpl< Dependence > *	getDependences () const
	Returns the memory dependences. More...

void	clearDependences ()

const SmallVectorImpl< Instruction * > &	getMemoryInstructions () const
	The vector of memory access instructions. More...

DenseMap< Instruction *, unsigned >	generateInstructionOrderMap () const
	Generate a mapping between the memory instructions and their indices according to program order. More...

SmallVector< Instruction *, 4 >	getInstructionsForAccess (Value *Ptr, bool isWrite) const
	Find the set of instructions that read or write via `Ptr`. More...

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

Member Typedef Documentation

◆ DepCandidates

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

Set of potential dependent memory accesses.

Definition at line 98 of file LoopAccessAnalysis.h.

◆ MemAccessInfo

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

Definition at line 95 of file LoopAccessAnalysis.h.

◆ MemAccessInfoList

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

Definition at line 96 of file LoopAccessAnalysis.h.

Member Enumeration Documentation

◆ VectorizationSafetyStatus

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

Constructor & Destructor Documentation

◆ MemoryDepChecker()

llvm::MemoryDepChecker::MemoryDepChecker	(	PredicatedScalarEvolution &	PSE,
		const Loop *	L
	)

inline

Definition at line 178 of file LoopAccessAnalysis.h.

Member Function Documentation

◆ addAccess() [1/2]

void llvm::MemoryDepChecker::addAccess ( StoreInst * SI )

inline

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

Definition at line 185 of file LoopAccessAnalysis.h.

References llvm::StoreInst::getPointerOperand().

◆ addAccess() [2/2]

void llvm::MemoryDepChecker::addAccess ( LoadInst * LI )

inline

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

Definition at line 194 of file LoopAccessAnalysis.h.

References llvm::LoadInst::getPointerOperand().

◆ areDepsSafe()

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

Check whether the dependencies between the accesses are safe.

Only checks sets with elements in CheckDeps.

Definition at line 1623 of file LoopAccessAnalysis.cpp.

References assert(), llvm::sys::path::begin(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::sys::path::end(), llvm::EquivalenceClasses< ElemTy >::findValue(), llvm::EquivalenceClasses< ElemTy >::getLeaderValue(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, MaxDependences, llvm::EquivalenceClasses< ElemTy >::member_begin(), llvm::EquivalenceClasses< ElemTy >::member_end(), and std::swap().

◆ clearDependences()

void llvm::MemoryDepChecker::clearDependences ( )

inline

Definition at line 235 of file LoopAccessAnalysis.h.

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

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

References B, and I.

Referenced by isLoadConditional().

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

Referenced by isLoadConditional(), and llvm::InterleavedAccessInfo::requiresScalarEpilogue().

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

References llvm::MemoryDepChecker::Dependence::DepName, and llvm::transform().

◆ getMaxSafeDepDistBytes()

uint64_t llvm::MemoryDepChecker::getMaxSafeDepDistBytes ( )

inline

The maximum number of bytes of a vector register we can vectorize the accesses safely with.

Definition at line 215 of file LoopAccessAnalysis.h.

◆ getMaxSafeRegisterWidth()

uint64_t llvm::MemoryDepChecker::getMaxSafeRegisterWidth ( ) 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 219 of file LoopAccessAnalysis.h.

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

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

◆ isSafeForVectorization()

bool llvm::MemoryDepChecker::isSafeForVectorization ( ) const

inline

No memory dependence was encountered that would inhibit vectorization.

Definition at line 209 of file LoopAccessAnalysis.h.

◆ shouldRetryWithRuntimeCheck()

bool llvm::MemoryDepChecker::shouldRetryWithRuntimeCheck ( ) 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 223 of file LoopAccessAnalysis.h.

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

◆ getDependences()

◆ getInstructionsForAccess()

◆ getMaxSafeDepDistBytes()

◆ getMaxSafeRegisterWidth()

◆ getMemoryInstructions()

◆ isSafeForVectorization()

◆ shouldRetryWithRuntimeCheck()