LLVM  10.0.0svn
Public Member Functions | Friends | List of all members
llvm::IndexedReference Class Reference

Represents a memory reference as a base pointer and a set of indexing operations. More...

#include "llvm/Analysis/LoopCacheAnalysis.h"

Public Member Functions

 IndexedReference (Instruction &StoreOrLoadInst, const LoopInfo &LI, ScalarEvolution &SE)
 Construct an indexed reference given a StoreOrLoadInst instruction. More...
 
bool isValid () const
 
const SCEVgetBasePointer () const
 
size_t getNumSubscripts () const
 
const SCEVgetSubscript (unsigned SubNum) const
 
const SCEVgetFirstSubscript () const
 
const SCEVgetLastSubscript () const
 
Optional< boolhasSpacialReuse (const IndexedReference &Other, unsigned CLS, AliasAnalysis &AA) const
 Return true/false if the current object and the indexed reference Other are/aren't in the same cache line of size CLS. More...
 
Optional< boolhasTemporalReuse (const IndexedReference &Other, unsigned MaxDistance, const Loop &L, DependenceInfo &DI, AliasAnalysis &AA) const
 Return true if the current object and the indexed reference Other have distance smaller than MaxDistance in the dimension associated with the given loop L. More...
 
CacheCostTy computeRefCost (const Loop &L, unsigned CLS) const
 Compute the cost of the reference w.r.t. More...
 

Friends

raw_ostreamoperator<< (raw_ostream &OS, const IndexedReference &R)
 

Detailed 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]

Definition at line 44 of file LoopCacheAnalysis.h.

Constructor & Destructor Documentation

◆ IndexedReference()

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

Construct an indexed reference given a StoreOrLoadInst instruction.

Definition at line 128 of file LoopCacheAnalysis.cpp.

References assert(), llvm::dbgs(), and LLVM_DEBUG.

Member Function Documentation

◆ computeRefCost()

CacheCostTy IndexedReference::computeRefCost ( const Loop L,
unsigned  CLS 
) const

Compute the cost of the reference w.r.t.

the given loop 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'.

Definition at line 254 of file LoopCacheAnalysis.cpp.

References llvm::all_of(), assert(), CacheLineSize, computeTripCount(), llvm::dbgs(), DefaultTripCount, llvm::ScalarEvolution::delinearize(), llvm::dyn_cast(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getElementSize(), getLastSubscript(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::Loop::getName(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::ScalarEvolution::getPointerBase(), llvm::getPointerOperand(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::getSCEVAtScope(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::ScalarEvolution::getUDivExactExpr(), llvm::ScalarEvolution::getUDivExpr(), llvm::CmpInst::ICMP_ULT, llvm::raw_ostream::indent(), llvm::CacheCost::InvalidCost, llvm::SCEVAddRecExpr::isAffine(), llvm::ScalarEvolution::isKnownPredicate(), llvm::ScalarEvolution::isLoopInvariant(), isOneDimensionalArray(), llvm::ScalarEvolution::isSCEVable(), and LLVM_DEBUG.

Referenced by getLastSubscript().

◆ getBasePointer()

const SCEV* llvm::IndexedReference::getBasePointer ( ) const
inline

Definition at line 53 of file LoopCacheAnalysis.h.

Referenced by hasSpacialReuse(), and hasTemporalReuse().

◆ getFirstSubscript()

const SCEV* llvm::IndexedReference::getFirstSubscript ( ) const
inline

Definition at line 59 of file LoopCacheAnalysis.h.

References assert().

◆ getLastSubscript()

const SCEV* llvm::IndexedReference::getLastSubscript ( ) const
inline

◆ getNumSubscripts()

size_t llvm::IndexedReference::getNumSubscripts ( ) const
inline

Definition at line 54 of file LoopCacheAnalysis.h.

Referenced by getSubscript(), and hasSpacialReuse().

◆ getSubscript()

const SCEV* llvm::IndexedReference::getSubscript ( unsigned  SubNum) const
inline

Definition at line 55 of file LoopCacheAnalysis.h.

References assert(), and getNumSubscripts().

Referenced by hasSpacialReuse().

◆ hasSpacialReuse()

Optional< bool > IndexedReference::hasSpacialReuse ( const IndexedReference Other,
unsigned  CLS,
AliasAnalysis AA 
) const

Return true/false if the current object and the indexed reference Other are/aren't in the same cache line of size 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.

Definition at line 140 of file LoopCacheAnalysis.cpp.

References assert(), llvm::dbgs(), llvm::dyn_cast(), getBasePointer(), getLastSubscript(), llvm::ScalarEvolution::getMinusSCEV(), getNumSubscripts(), llvm::ConstantInt::getSExtValue(), getSubscript(), llvm::SCEVConstant::getValue(), llvm::raw_ostream::indent(), LLVM_DEBUG, and llvm::None.

Referenced by getLastSubscript().

◆ hasTemporalReuse()

Optional< bool > IndexedReference::hasTemporalReuse ( const IndexedReference Other,
unsigned  MaxDistance,
const Loop L,
DependenceInfo DI,
AliasAnalysis AA 
) const

Return true if the current object and the indexed reference Other have distance smaller than MaxDistance in the dimension associated with the given loop L.

Return false if the distance is not smaller than MaxDistance and None if unsure.

Definition at line 195 of file LoopCacheAnalysis.cpp.

References assert(), D, llvm::dbgs(), llvm::DependenceInfo::depends(), getBasePointer(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::ConstantInt::getSExtValue(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::isZero(), LLVM_DEBUG, and llvm::None.

Referenced by getLastSubscript().

◆ isValid()

bool llvm::IndexedReference::isValid ( ) const
inline

Definition at line 52 of file LoopCacheAnalysis.h.

Friends And Related Function Documentation

◆ operator<<

raw_ostream& operator<< ( raw_ostream OS,
const IndexedReference R 
)
friend

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