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, const Loop L, const DenseMap< Value , const SCEV * > &SymbolicStrides, unsigned MaxTargetVectorWidthInBits)

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

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

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

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

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

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

Member Typedef Documentation

◆ DepCandidates

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

Set of potential dependent memory accesses.

Definition at line 95 of file LoopAccessAnalysis.h.

◆ MemAccessInfo

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

Definition at line 92 of file LoopAccessAnalysis.h.

◆ MemAccessInfoList

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

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

Constructor & Destructor Documentation

◆ MemoryDepChecker()

llvm::MemoryDepChecker::MemoryDepChecker	(	PredicatedScalarEvolution &	PSE,
		const Loop *	L,
		const DenseMap< Value , const SCEV > &	SymbolicStrides,
		unsigned	MaxTargetVectorWidthInBits
	)

inline

Definition at line 181 of file LoopAccessAnalysis.h.

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 1673 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 1664 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.

Only checks sets with elements in CheckDeps.

Definition at line 2244 of file LoopAccessAnalysis.cpp.

References A, assert(), B, llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::sys::path::const_iterator::end, llvm::EquivalenceClasses< ElemTy, Compare >::findValue(), llvm::EquivalenceClasses< ElemTy, Compare >::getLeaderValue(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), isSafeForVectorization(), llvm::MemoryDepChecker::Dependence::isSafeForVectorization(), LLVM_DEBUG, MaxDependences, llvm::EquivalenceClasses< ElemTy, Compare >::member_begin(), llvm::EquivalenceClasses< ElemTy, Compare >::member_end(), llvm::MemoryDepChecker::Dependence::NoDep, and std::swap().

◆ clearDependences()

void llvm::MemoryDepChecker::clearDependences ( )

inline

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

References I.

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

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

◆ getInnermostLoop()

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

inline

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

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

Referenced by llvm::LoopVectorizationLegality::getMaxSafeVectorWidthInBits(), and 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 237 of file LoopAccessAnalysis.h.

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

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

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

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

Referenced by llvm::LoopVectorizationLegality::isSafeForAnyVectorWidth(), and llvm::LoopAccessInfo::print().

◆ isSafeForVectorization()

bool llvm::MemoryDepChecker::isSafeForVectorization ( ) const

inline

No memory dependence was encountered that would inhibit vectorization.

Definition at line 203 of file LoopAccessAnalysis.h.

References Safe.

Referenced by areDepsSafe().

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

◆ getDependences()

◆ getInnermostLoop()

◆ getInstructionsForAccess()

◆ getMaxSafeVectorWidthInBits()

◆ getMemoryInstructions()

◆ getOrderForAccess()

◆ getPointerBounds()

◆ isSafeForAnyVectorWidth()

◆ isSafeForVectorization()

◆ shouldRetryWithRuntimeCheck()