class MemoryDepChecker

Declaration

class MemoryDepChecker { /* full declaration omitted */ };

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.

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:86

Member Variables

private llvm::PredicatedScalarEvolution& PSE
A wrapper around ScalarEvolution, used to add runtime SCEV checks, and applies dynamic knowledge to simplify SCEV expressions and convert them to a more usable form. We need this in case assumptions about SCEV expressions need to be made in order to avoid unknown dependences. For example we might assume a unit stride for a pointer in order to prove that a memory access is strided and doesn't wrap.
private const llvm::Loop* InnermostLoop
private DenseMap<llvm::MemoryDepChecker::MemAccessInfo, std::vector<unsigned int>> Accesses
Maps access locations (ptr, read/write) to program order.
private SmallVector<llvm::Instruction*, 16> InstMap
Memory access instructions in program order.
private unsigned int AccessIdx = 0
The program order index to be used for the next instruction.
private uint64_t MaxSafeDepDistBytes = 0
private uint64_t MaxSafeVectorWidthInBits = -1U
Number of elements (from consecutive iterations) that are safe to operate on simultaneously, multiplied by the size of the element in bits. The size of the element is taken from the memory access that is most restrictive.
private bool FoundNonConstantDistanceDependence = false
If we see a non-constant dependence distance we can still try to vectorize this loop with runtime checks.
private llvm::MemoryDepChecker::VectorizationSafetyStatus Status = VectorizationSafetyStatus::Safe
Result of the dependence checks, indicating whether the checked dependences are safe for vectorization, require RT checks or are known to be unsafe.
private bool RecordDependences = true
/ True if Dependences reflects the dependences in the / loop. If false we exceeded MaxDependences and / Dependences is invalid.
private SmallVector<llvm::MemoryDepChecker::Dependence, 8> Dependences
Memory dependences collected during the analysis. Only valid if RecordDependences is true.

Method Overview

Methods

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

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:171

Parameters

llvm::PredicatedScalarEvolution& PSE
const llvm::Loop* L

void addAccess(llvm::StoreInst* SI)

Description

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

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:176

Parameters

llvm::StoreInst* SI

void addAccess(llvm::LoadInst* LI)

Description

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

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:180

Parameters

llvm::LoadInst* LI

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

Description

Check whether the dependencies between the accesses are safe. Only checks sets with elements in \p CheckDeps.

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:185

Parameters

llvm::MemoryDepChecker::DepCandidates& AccessSets
llvm::MemoryDepChecker::MemAccessInfoList& CheckDeps
const llvm::ValueToValueMap& Strides

void clearDependences()

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:224

bool couldPreventStoreLoadForward(
    uint64_t Distance,
    uint64_t TypeByteSize)

Description

Check whether the data dependence could prevent store-load forwarding.

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:325

Parameters

uint64_t Distance
uint64_t TypeByteSize

Returns

false if we shouldn't vectorize at all or avoid larger vectorization factors by limiting MaxSafeDepDistBytes.

DenseMap<llvm::Instruction*, unsigned int>
generateInstructionOrderMap() const

Description

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

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:234

const SmallVectorImpl<
    llvm::MemoryDepChecker::Dependence>*
getDependences() const

Description

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

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:220

const llvm::Loop* getInnermostLoop() const

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:256

SmallVector<llvm::Instruction*, 4>
getInstructionsForAccess(llvm::Value* Ptr,
                         bool isWrite) const

Description

Find the set of instructions that read or write via \p Ptr.

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:244

Parameters

llvm::Value* Ptr
bool isWrite

uint64_t getMaxSafeDepDistBytes()

Description

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

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:202

uint64_t getMaxSafeVectorWidthInBits() const

Description

Return the number of elements that are safe to operate on simultaneously, multiplied by the size of the element in bits.

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:206

const SmallVectorImpl<llvm::Instruction*>&
getMemoryInstructions() const

Description

The vector of memory access instructions. The indices are used as instruction identifiers in the Dependence class.

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:228

ArrayRef<unsigned int> getOrderForAccess(
    llvm::Value* Ptr,
    bool IsWrite) const

Description

Return the program order indices for the access location (Ptr, IsWrite). Returns an empty ArrayRef if there are no accesses for the location.

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:249

Parameters

llvm::Value* Ptr
bool IsWrite

Dependence::DepType isDependent(
    const llvm::MemoryDepChecker::MemAccessInfo&
        A,
    unsigned int AIdx,
    const llvm::MemoryDepChecker::MemAccessInfo&
        B,
    unsigned int BIdx,
    const llvm::ValueToValueMap& Strides)

Description

Check whether there is a plausible dependence between the two accesses. Access \p A must happen before \p B in program order. The two indices identify the index into the program order map. This function checks whether there is a plausible dependence (or the absence of such can't be proved) between the two accesses. If there is a plausible dependence but the dependence distance is bigger than one element access it records this distance in \p MaxSafeDepDistBytes (if this distance is smaller than any other distance encountered so far). Otherwise, this function returns true signaling a possible dependence.

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:316

Parameters

const llvm::MemoryDepChecker::MemAccessInfo& A
unsigned int AIdx
const llvm::MemoryDepChecker::MemAccessInfo& B
unsigned int BIdx
const llvm::ValueToValueMap& Strides

bool isSafeForAnyVectorWidth() const

Description

Return true if the number of elements that are safe to operate on simultaneously is not bounded.

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:196

bool isSafeForVectorization() const

Description

No memory dependence was encountered that would inhibit vectorization.

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:190

void mergeInStatus(
    llvm::MemoryDepChecker::
        VectorizationSafetyStatus S)

Description

Updates the current safety status with \p S. We can go from Safe to either PossiblySafeWithRtChecks or Unsafe and from PossiblySafeWithRtChecks to Unsafe.

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:330

Parameters

llvm::MemoryDepChecker::VectorizationSafetyStatus S

bool shouldRetryWithRuntimeCheck() const

Description

In same cases when the dependency check fails we can still vectorize the loop with a dynamic array access check.

Declared at: llvm/include/llvm/Analysis/LoopAccessAnalysis.h:212