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...

bool	hasConvergentOp () const
	Return true if there is a convergent operation in the loop. More...

const RuntimePointerChecking *	getRuntimePointerChecking () 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 OptimizationRemarkAnalysis *	getReport () const
	The diagnostics report generated for the analysis. More...

const MemoryDepChecker &	getDepChecker () 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 ValueToValueMap &	getSymbolicStrides () 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	hasDependenceInvolvingLoopInvariantAddress () const
	If the loop has memory dependence involving an invariant address, i.e. More...

const PredicatedScalarEvolution &	getPSE () 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 516 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 2344 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 2274 of file LoopAccessAnalysis.cpp.

References llvm::dbgs(), 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(), LLVM_DEBUG, and SI.

Referenced by llvm::InnerLoopVectorizer::emitMemRuntimeChecks(), and 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 2203 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

Return true if the block BB needs to be predicated in order for the loop to be vectorized.

Definition at line 2078 of file LoopAccessAnalysis.cpp.

References assert(), llvm::LoopBase< BlockT, LoopT >::contains(), DEBUG_TYPE, llvm::DominatorTree::dominates(), llvm::Instruction::getDebugLoc(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), llvm::Loop::getStartLoc(), and I.

Referenced by llvm::LoopVectorizationLegality::blockNeedsPredication(), and llvm::InterleavedAccessInfo::requiresScalarEpilogue().

◆ 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 523 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 576 of file LoopAccessAnalysis.h.

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

◆ 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 580 of file LoopAccessAnalysis.h.

◆ getMaxSafeDepDistBytes()

uint64_t llvm::LoopAccessInfo::getMaxSafeDepDistBytes ( ) const

inline

Definition at line 548 of file LoopAccessAnalysis.h.

◆ getNumLoads()

unsigned llvm::LoopAccessInfo::getNumLoads ( ) const

inline

Definition at line 550 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 536 of file LoopAccessAnalysis.h.

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

◆ getNumStores()

unsigned llvm::LoopAccessInfo::getNumStores ( ) const

inline

Definition at line 549 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 606 of file LoopAccessAnalysis.h.

References B, CheckType(), llvm::getPtrStride(), llvm::isConsecutiveAccess(), llvm::replaceSymbolicStrideSCEV(), llvm::sortPtrAccesses(), 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 572 of file LoopAccessAnalysis.h.

◆ getRuntimePointerChecking()

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

inline

Definition at line 530 of file LoopAccessAnalysis.h.

Referenced by isLoadConditional(), llvm::LoopVersioning::LoopVersioning(), and llvm::LoopVersioning::prepareNoAliasMetadata().

◆ 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 587 of file LoopAccessAnalysis.h.

Referenced by llvm::LoopVectorizationCostModel::runtimeChecksRequired().

◆ hasConvergentOp()

bool llvm::LoopAccessInfo::hasConvergentOp ( ) const

inline

Return true if there is a convergent operation in the loop.

There may still be reported runtime pointer checks that would be required, but it is not legal to insert them.

Definition at line 528 of file LoopAccessAnalysis.h.

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

◆ hasDependenceInvolvingLoopInvariantAddress()

bool llvm::LoopAccessInfo::hasDependenceInvolvingLoopInvariantAddress ( ) const

inline

If the loop has memory dependence involving an invariant address, i.e.

two stores or a store and a load, then return true, else return false.

Definition at line 597 of file LoopAccessAnalysis.h.

◆ hasStride()

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

inline

Pointer has a symbolic stride.

Definition at line 590 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 2107 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 2357 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:

include/llvm/Analysis/LoopAccessAnalysis.h
lib/Analysis/LoopAccessAnalysis.cpp

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ LoopAccessInfo()

Member Function Documentation

◆ addRuntimeChecks() [1/2]

◆ addRuntimeChecks() [2/2]

◆ blockNeedsPredication()

◆ canVectorizeMemory()

◆ getDepChecker()

◆ getInstructionsForAccess()

◆ getMaxSafeDepDistBytes()

◆ getNumLoads()

◆ getNumRuntimePointerChecks()

◆ getNumStores()

◆ getPSE()

◆ getReport()

◆ getRuntimePointerChecking()

◆ getSymbolicStrides()

◆ hasConvergentOp()

◆ hasDependenceInvolvingLoopInvariantAddress()

◆ hasStride()

◆ isUniform()

◆ print()