LLVM  6.0.0svn
Public Member Functions | Static Public Member Functions | List of all members
llvm::LoopAccessInfo Class Reference

Drive the analysis of memory accesses in the loop. More...

#include "llvm/Analysis/LoopAccessAnalysis.h"

Public Member Functions

 LoopAccessInfo (Loop *L, ScalarEvolution *SE, const TargetLibraryInfo *TLI, AliasAnalysis *AA, DominatorTree *DT, LoopInfo *LI)
 
bool canVectorizeMemory () const
 Return true we can analyze the memory accesses in the loop and there are no memory dependence cycles. More...
 
const RuntimePointerCheckinggetRuntimePointerChecking () const
 
unsigned getNumRuntimePointerChecks () const
 Number of memchecks required to prove independence of otherwise may-alias pointers. More...
 
bool isUniform (Value *V) const
 Returns true if the value V is uniform within the loop. More...
 
uint64_t getMaxSafeDepDistBytes () const
 
unsigned getNumStores () const
 
unsigned getNumLoads () const
 
std::pair< Instruction *, Instruction * > addRuntimeChecks (Instruction *Loc) const
 Add code that checks at runtime if the accessed arrays overlap. More...
 
std::pair< Instruction *, Instruction * > addRuntimeChecks (Instruction *Loc, const SmallVectorImpl< RuntimePointerChecking::PointerCheck > &PointerChecks) const
 Generete the instructions for the checks in PointerChecks. More...
 
const OptimizationRemarkAnalysisgetReport () const
 The diagnostics report generated for the analysis. More...
 
const MemoryDepCheckergetDepChecker () const
 the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences between memory accesses. More...
 
SmallVector< Instruction *, 4 > getInstructionsForAccess (Value *Ptr, bool isWrite) const
 Return the list of instructions that use Ptr to read or write memory. More...
 
const ValueToValueMapgetSymbolicStrides () const
 If an access has a symbolic strides, this maps the pointer value to the stride symbol. More...
 
bool hasStride (Value *V) const
 Pointer has a symbolic stride. More...
 
void print (raw_ostream &OS, unsigned Depth=0) const
 Print the information about the memory accesses in the loop. More...
 
bool hasStoreToLoopInvariantAddress () const
 Checks existence of store to invariant address inside loop. More...
 
const PredicatedScalarEvolutiongetPSE () const
 Used to add runtime SCEV checks. More...
 

Static Public Member Functions

static bool blockNeedsPredication (BasicBlock *BB, Loop *TheLoop, DominatorTree *DT)
 Return true if the block BB needs to be predicated in order for the loop to be vectorized. More...
 

Detailed Description

Drive the analysis of memory accesses in the loop.

This class is responsible for analyzing the memory accesses of a loop. It collects the accesses and then its main helper the AccessAnalysis class finds and categorizes the dependences in buildDependenceSets.

For memory dependences that can be analyzed at compile time, it determines whether the dependence is part of cycle inhibiting vectorization. This work is delegated to the MemoryDepChecker class.

For memory dependences that cannot be determined at compile time, it generates run-time checks to prove independence. This is done by AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the RuntimePointerCheck class.

If pointers can wrap or can't be expressed as affine AddRec expressions by ScalarEvolution, we will generate run-time checks by emitting a SCEVUnionPredicate.

Checks for both memory dependences and the SCEV predicates contained in the PSE must be emitted in order for the results of this analysis to be valid.

Definition at line 493 of file LoopAccessAnalysis.h.

Constructor & Destructor Documentation

◆ LoopAccessInfo()

LoopAccessInfo::LoopAccessInfo ( Loop L,
ScalarEvolution SE,
const TargetLibraryInfo TLI,
AliasAnalysis AA,
DominatorTree DT,
LoopInfo LI 
)

Definition at line 2259 of file LoopAccessAnalysis.cpp.

Referenced by llvm::LoopAccessAnalysis::run().

Member Function Documentation

◆ addRuntimeChecks() [1/2]

std::pair< Instruction *, Instruction * > LoopAccessInfo::addRuntimeChecks ( Instruction Loc) const

Add code that checks at runtime if the accessed arrays overlap.

Returns a pair of instructions where the first element is the first instruction generated in possibly a sequence of instructions and the second value is the final comparator value or NULL if no check is needed.

Definition at line 2190 of file LoopAccessAnalysis.cpp.

References llvm::dbgs(), DEBUG, llvm::Module::getDataLayout(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::ScalarEvolution::getMinusSCEV(), llvm::BasicBlock::getModule(), llvm::ScalarEvolution::getNoopOrSignExtend(), llvm::getStrideFromPointer(), llvm::SCEV::getType(), llvm::DataLayout::getTypeAllocSize(), llvm::ScalarEvolution::getZeroExtendExpr(), llvm::ScalarEvolution::isKnownPositive(), and SI.

Referenced by llvm::LoopVersioning::versionLoop().

◆ addRuntimeChecks() [2/2]

std::pair< Instruction *, Instruction * > LoopAccessInfo::addRuntimeChecks ( Instruction Loc,
const SmallVectorImpl< RuntimePointerChecking::PointerCheck > &  PointerChecks 
) const

Generete the instructions for the checks in PointerChecks.

Returns a pair of instructions where the first element is the first instruction generated in possibly a sequence of instructions and the second value is the final comparator value or NULL if no check is needed.

Definition at line 2119 of file LoopAccessAnalysis.cpp.

References assert(), Check(), llvm::IRBuilder< T, Inserter >::CreateAnd(), llvm::IRBuilder< T, Inserter >::CreateBitCast(), llvm::IRBuilder< T, Inserter >::CreateICmpULT(), llvm::IRBuilder< T, Inserter >::CreateOr(), expandBounds(), llvm::Value::getContext(), llvm::Module::getDataLayout(), getFirstInst(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Type::getInt8PtrTy(), llvm::BasicBlock::getModule(), llvm::ConstantInt::getTrue(), and llvm::IRBuilder< T, Inserter >::Insert().

◆ blockNeedsPredication()

bool LoopAccessInfo::blockNeedsPredication ( BasicBlock BB,
Loop TheLoop,
DominatorTree DT 
)
static

◆ canVectorizeMemory()

bool llvm::LoopAccessInfo::canVectorizeMemory ( ) const
inline

Return true we can analyze the memory accesses in the loop and there are no memory dependence cycles.

Definition at line 500 of file LoopAccessAnalysis.h.

◆ getDepChecker()

const MemoryDepChecker& llvm::LoopAccessInfo::getDepChecker ( ) const
inline

the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences between memory accesses.

Definition at line 548 of file LoopAccessAnalysis.h.

Referenced by llvm::InnerLoopVectorizer::addMetadata(), llvm::LoopVersioning::annotateLoopWithNoAlias(), llvm::MemoryDepChecker::Dependence::getDestination(), llvm::MemoryDepChecker::Dependence::getSource(), and isLoadConditional().

◆ getInstructionsForAccess()

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

Return the list of instructions that use Ptr to read or write memory.

Definition at line 552 of file LoopAccessAnalysis.h.

◆ getMaxSafeDepDistBytes()

uint64_t llvm::LoopAccessInfo::getMaxSafeDepDistBytes ( ) const
inline

Definition at line 520 of file LoopAccessAnalysis.h.

Referenced by emitMissedWarning().

◆ getNumLoads()

unsigned llvm::LoopAccessInfo::getNumLoads ( ) const
inline

Definition at line 522 of file LoopAccessAnalysis.h.

◆ getNumRuntimePointerChecks()

unsigned llvm::LoopAccessInfo::getNumRuntimePointerChecks ( ) const
inline

Number of memchecks required to prove independence of otherwise may-alias pointers.

Definition at line 508 of file LoopAccessAnalysis.h.

Referenced by llvm::LoopVersioning::annotateInstWithNoAlias().

◆ getNumStores()

unsigned llvm::LoopAccessInfo::getNumStores ( ) const
inline

Definition at line 521 of file LoopAccessAnalysis.h.

◆ getPSE()

const PredicatedScalarEvolution& llvm::LoopAccessInfo::getPSE ( ) const
inline

Used to add runtime SCEV checks.

Simplifies SCEV expressions and converts them to a more usable form. All SCEV expressions during the analysis should be re-written (and therefore simplified) according to PSE. A user of LoopAccessAnalysis will need to emit the runtime checks associated with this predicate.

Definition at line 579 of file LoopAccessAnalysis.h.

References B, CheckType(), llvm::getPtrStride(), llvm::isConsecutiveAccess(), llvm::BitmaskEnumDetail::Mask(), llvm::replaceSymbolicStrideSCEV(), llvm::sortLoadAccesses(), and llvm::stripIntegerCast().

Referenced by llvm::LoopVersioning::annotateInstWithNoAlias(), isLoadConditional(), llvm::LoopVersioning::LoopVersioning(), and llvm::LoopVersioning::versionLoop().

◆ getReport()

const OptimizationRemarkAnalysis* llvm::LoopAccessInfo::getReport ( ) const
inline

The diagnostics report generated for the analysis.

E.g. why we couldn't analyze the loop.

Definition at line 544 of file LoopAccessAnalysis.h.

◆ getRuntimePointerChecking()

const RuntimePointerChecking* llvm::LoopAccessInfo::getRuntimePointerChecking ( ) const
inline

◆ getSymbolicStrides()

const ValueToValueMap& llvm::LoopAccessInfo::getSymbolicStrides ( ) const
inline

If an access has a symbolic strides, this maps the pointer value to the stride symbol.

Definition at line 559 of file LoopAccessAnalysis.h.

◆ hasStoreToLoopInvariantAddress()

bool llvm::LoopAccessInfo::hasStoreToLoopInvariantAddress ( ) const
inline

Checks existence of store to invariant address inside loop.

If the loop has any store to invariant address, then it returns true, else returns false.

Definition at line 570 of file LoopAccessAnalysis.h.

◆ hasStride()

bool llvm::LoopAccessInfo::hasStride ( Value V) const
inline

Pointer has a symbolic stride.

Definition at line 562 of file LoopAccessAnalysis.h.

References llvm::Depth, and print().

◆ isUniform()

bool LoopAccessInfo::isUniform ( Value V) const

Returns true if the value V is uniform within the loop.

Definition at line 2024 of file LoopAccessAnalysis.cpp.

References llvm::ScalarEvolution::getSCEV(), llvm::Value::getType(), llvm::ScalarEvolution::isLoopInvariant(), and llvm::ScalarEvolution::isSCEVable().

◆ print()

void LoopAccessInfo::print ( raw_ostream OS,
unsigned  Depth = 0 
) const

Print the information about the memory accesses in the loop.

Definition at line 2271 of file LoopAccessAnalysis.cpp.

References llvm::raw_ostream::indent().

Referenced by llvm::LoopAccessLegacyAnalysis::print().


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