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:92

Method Overview

Methods

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

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

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:184

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:193

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:203

Parameters

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

void clearDependences()

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

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:244

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:230

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:254

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:214

uint64_t getMaxSafeRegisterWidth() 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:218

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:238

bool isSafeForVectorization() const

Description

No memory dependence was encountered that would inhibit vectorization.

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

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:222