LLVM: llvm::MemoryDepChecker Class Reference (original) (raw)

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](LoopAccessAnalysis%5F8h%5Fsource.html)"

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

◆ DepCandidates

◆ MemAccessInfo

◆ MemAccessInfoList

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

Definition at line 101 of file LoopAccessAnalysis.h.

◆ addAccess() [1/2]

◆ addAccess() [2/2]

◆ areDepsSafe()

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

◆ generateInstructionOrderMap()

Generate a mapping between the memory instructions and their indices according to program order.

Definition at line 265 of file LoopAccessAnalysis.h.

References I.

◆ getAC()

◆ getDependences()

Returns the memory dependences.

If null is returned we exceeded the MaxDependences threshold and this information is not available.

Definition at line 251 of file LoopAccessAnalysis.h.

◆ getDT()

◆ getInnermostLoop()

◆ getInstructionsForAccess()

◆ getMaxSafeVectorWidthInBits()

◆ getMemoryInstructions()

◆ getOrderForAccess()

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

References I.

◆ getPointerBounds()

◆ getStoreLoadForwardSafeDistanceInBits()

◆ isSafeForAnyStoreLoadForwardDistances()

◆ isSafeForAnyVectorWidth()

◆ isSafeForVectorization()

◆ shouldRetryWithRuntimeChecks()

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

• include/llvm/Analysis/LoopAccessAnalysis.h
• lib/Analysis/LoopAccessAnalysis.cpp