LLVM 18.0.0git
|
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) | |
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 *, 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 |
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.
Definition at line 93 of file LoopAccessAnalysis.h.
Set of potential dependent memory accesses.
Definition at line 98 of file LoopAccessAnalysis.h.
typedef PointerIntPair<Value *, 1, bool> llvm::MemoryDepChecker::MemAccessInfo |
Definition at line 95 of file LoopAccessAnalysis.h.
Definition at line 96 of file LoopAccessAnalysis.h.
|
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.
|
inline |
Definition at line 184 of file LoopAccessAnalysis.h.
void MemoryDepChecker::addAccess | ( | LoadInst * | LI | ) |
Register the location (instructions are given increasing numbers) of a write access.
Definition at line 1652 of file LoopAccessAnalysis.cpp.
References llvm::LoadInst::getPointerOperand(), Ptr, and visitPointers().
void MemoryDepChecker::addAccess | ( | StoreInst * | SI | ) |
Register the location (instructions are given increasing numbers) of a write access.
Definition at line 1643 of file LoopAccessAnalysis.cpp.
References Ptr, and visitPointers().
bool MemoryDepChecker::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.
Only checks sets with elements in CheckDeps
.
Definition at line 2128 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().
|
inline |
Definition at line 235 of file LoopAccessAnalysis.h.
|
inline |
Generate a mapping between the memory instructions and their indices according to program order.
Definition at line 245 of file LoopAccessAnalysis.h.
References I.
|
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.
Definition at line 267 of file LoopAccessAnalysis.h.
SmallVector< Instruction *, 4 > MemoryDepChecker::getInstructionsForAccess | ( | Value * | Ptr, |
bool | isWrite | ||
) | const |
Find the set of instructions that read or write via Ptr
.
Definition at line 2209 of file LoopAccessAnalysis.cpp.
References Idx, Ptr, and llvm::transform().
|
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 217 of file LoopAccessAnalysis.h.
Referenced by llvm::LoopVectorizationLegality::getMaxSafeVectorWidthInBits(), and llvm::LoopAccessInfo::print().
|
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(), and llvm::MemoryDepChecker::Dependence::getSource().
|
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 260 of file LoopAccessAnalysis.h.
|
inline |
Return true if the number of elements that are safe to operate on simultaneously is not bounded.
Definition at line 211 of file LoopAccessAnalysis.h.
Referenced by llvm::LoopVectorizationLegality::isSafeForAnyVectorWidth(), and llvm::LoopAccessInfo::print().
|
inline |
No memory dependence was encountered that would inhibit vectorization.
Definition at line 205 of file LoopAccessAnalysis.h.
References Safe.
Referenced by areDepsSafe().
|
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.
References PossiblySafeWithRtChecks.