LLVM 19.0.0git
Classes | Public Types | Public Member Functions | List of all members
llvm::MemoryDepChecker Class Reference

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, boolMemAccessInfo
 
typedef SmallVector< MemAccessInfo, 8 > MemAccessInfoList
 
typedef EquivalenceClasses< MemAccessInfoDepCandidates
 Set of potential dependent memory accesses.
 

Public Member Functions

 MemoryDepChecker (PredicatedScalarEvolution &PSE, const Loop *L, 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 (DepCandidates &AccessSets, MemAccessInfoList &CheckDeps, const DenseMap< Value *, const SCEV * > &Strides, const DenseMap< Value *, SmallVector< const Value *, 16 > > &UnderlyingObjects)
 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 *, unsignedgenerateInstructionOrderMap () 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< unsignedgetOrderForAccess (Value *Ptr, bool IsWrite) const
 Return the program order indices for the access location (Ptr, IsWrite).
 
const LoopgetInnermostLoop () 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:

Definition at line 93 of file LoopAccessAnalysis.h.

Member Typedef Documentation

◆ DepCandidates

Set of potential dependent memory accesses.

Definition at line 98 of file LoopAccessAnalysis.h.

◆ MemAccessInfo

Definition at line 95 of file LoopAccessAnalysis.h.

◆ MemAccessInfoList

Definition at line 96 of file LoopAccessAnalysis.h.

Member Enumeration Documentation

◆ VectorizationSafetyStatus

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,
unsigned  MaxTargetVectorWidthInBits 
)
inline

Definition at line 184 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 1681 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 1672 of file LoopAccessAnalysis.cpp.

References Ptr, and visitPointers().

◆ areDepsSafe()

bool MemoryDepChecker::areDepsSafe ( DepCandidates AccessSets,
MemAccessInfoList CheckDeps,
const DenseMap< Value *, const SCEV * > &  Strides,
const DenseMap< Value *, SmallVector< const Value *, 16 > > &  UnderlyingObjects 
)

◆ clearDependences()

void llvm::MemoryDepChecker::clearDependences ( )
inline

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

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

◆ getInnermostLoop()

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

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

References 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 219 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 241 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 262 of file LoopAccessAnalysis.h.

References I, and Ptr.

◆ 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 213 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 207 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 225 of file LoopAccessAnalysis.h.

References PossiblySafeWithRtChecks.


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