class IndexedReference

Declaration

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

Description

Represents a memory reference as a base pointer and a set of indexing operations. For example given the array reference A[i][2j+1][3k+2] in a 3-dim loop nest: for(i=0;i <n ;++i) for(j=0;j <m ;++j) for(k=0;k <o ;++k) ... A[i][2j+1][3k+2] ... We expect: BasePointer -> A Subscripts -> [{0,+,1} < %for.i>][{1,+,2} < %for.j>][{2,+,3} < %for.k>] Sizes -> [m][o][4]

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:47

Member Variables

private bool IsValid = false
True if the reference can be delinearized, false otherwise.
private llvm::Instruction& StoreOrLoadInst
Represent the memory reference instruction.
private const llvm::SCEV* BasePointer = nullptr
The base pointer of the memory reference.
private SmallVector<const llvm::SCEV*, 3> Subscripts
The subscript (indexes) of the memory reference.
private SmallVector<const llvm::SCEV*, 3> Sizes
The dimensions of the memory reference.
private llvm::ScalarEvolution& SE

Method Overview

Methods

IndexedReference(
    llvm::Instruction& StoreOrLoadInst,
    const llvm::LoopInfo& LI,
    llvm::ScalarEvolution& SE)

Description

Construct an indexed reference given a \p StoreOrLoadInst instruction.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:52

Parameters

llvm::Instruction& StoreOrLoadInst
const llvm::LoopInfo& LI
llvm::ScalarEvolution& SE

llvm::CacheCostTy computeRefCost(
    const llvm::Loop& L,
    unsigned int CLS) const

Description

Compute the cost of the reference w.r.t. the given loop \p L when it is considered in the innermost position in the loop nest. The cost is defined as: - equal to one if the reference is loop invariant, or - equal to '(TripCount * stride) / cache_line_size' if: + the reference stride is less than the cache line size, and + the coefficient of this loop's index variable used in all other subscripts is zero - or otherwise equal to 'TripCount'.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:95

Parameters

const llvm::Loop& L
unsigned int CLS

bool delinearize(const llvm::LoopInfo& LI)

Description

Attempt to delinearize the indexed reference.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:99

Parameters

const llvm::LoopInfo& LI

const llvm::SCEV* getBasePointer() const

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:56

const llvm::SCEV* getFirstSubscript() const

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:62

const llvm::SCEV* getLastCoefficient() const

Description

Return the coefficient used in the rightmost dimension.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:123

const llvm::SCEV* getLastSubscript() const

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:66

size_t getNumSubscripts() const

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:57

const llvm::SCEV* getSubscript(
    unsigned int SubNum) const

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:58

Parameters

unsigned int SubNum

int getSubscriptIndex(const llvm::Loop& L) const

Description

Retrieve the index of the subscript corresponding to the given loop \p L. Return a zero-based positive index if the subscript index is succesfully located and a negative value otherwise. For example given the indexed reference 'A[i][2j+1][3k+2]', the call 'getSubscriptIndex(loop-k)' would return value 2.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:120

Parameters

const llvm::Loop& L

Optional<bool> hasSpacialReuse(
    const llvm::IndexedReference& Other,
    unsigned int CLS,
    llvm::AAResults& AA) const

Description

Return true/false if the current object and the indexed reference \p Other are/aren't in the same cache line of size \p CLS. Two references are in the same chace line iff the distance between them in the innermost dimension is less than the cache line size. Return None if unsure.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:75

Parameters

const llvm::IndexedReference& Other
unsigned int CLS
llvm::AAResults& AA

Optional<bool> hasTemporalReuse(
    const llvm::IndexedReference& Other,
    unsigned int MaxDistance,
    const llvm::Loop& L,
    llvm::DependenceInfo& DI,
    llvm::AAResults& AA) const

Description

Return true if the current object and the indexed reference \p Other have distance smaller than \p MaxDistance in the dimension associated with the given loop \p L. Return false if the distance is not smaller than \p MaxDistance and None if unsure.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:82

Parameters

const llvm::IndexedReference& Other
unsigned int MaxDistance
const llvm::Loop& L
llvm::DependenceInfo& DI
llvm::AAResults& AA

bool isAliased(
    const llvm::IndexedReference& Other,
    llvm::AAResults& AA) const

Description

Return true if the given reference \p Other is definetely aliased with the indexed reference represented by this class.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:136

Parameters

const llvm::IndexedReference& Other
llvm::AAResults& AA

bool isCoeffForLoopZeroOrInvariant(
    const llvm::SCEV& Subscript,
    const llvm::Loop& L) const

Description

Return true if the coefficient corresponding to induction variable of loop \p L in the given \p Subscript is zero or is loop invariant in \p L.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:127

Parameters

const llvm::SCEV& Subscript
const llvm::Loop& L

bool isConsecutive(const llvm::Loop& L,
                   const llvm::SCEV*& Stride,
                   unsigned int CLS) const

Description

Return true if the indexed reference is 'consecutive' in loop \p L. An indexed reference is 'consecutive' if the only coefficient that uses the loop induction variable is the rightmost one, and the access stride is smaller than the cache line size \p CLS. Provide a valid \p Stride value if the indexed reference is 'consecutive'.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:113

Parameters

const llvm::Loop& L
const llvm::SCEV*& Stride
unsigned int CLS

bool isLoopInvariant(const llvm::Loop& L) const

Description

Return true if the index reference is invariant with respect to loop \p L.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:106

Parameters

const llvm::Loop& L

bool isSimpleAddRecurrence(
    const llvm::SCEV& Subscript,
    const llvm::Loop& L) const

Description

Verify that the given \p Subscript is 'well formed' (must be a simple add recurrence).

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:132

Parameters

const llvm::SCEV& Subscript
const llvm::Loop& L

bool isValid() const

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:55

bool tryDelinearizeFixedSize(
    const llvm::SCEV* AccessFn,
    SmallVectorImpl<const llvm::SCEV*>&
        Subscripts)

Description

Attempt to delinearize \p AccessFn for fixed-size arrays.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:102

Parameters

const llvm::SCEV* AccessFn
SmallVectorImpl<const llvm::SCEV*>& Subscripts