DependenceInfo - This class is the main dependence-analysis driver. More...

#include "llvm/Analysis/DependenceAnalysis.h"

Public Member Functions
	DependenceInfo (Function F, AAResults AA, ScalarEvolution SE, LoopInfo LI)

LLVM_ABI bool	invalidate (Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
	Handle transitive invalidation when the cached analysis results go away.

LLVM_ABI std::unique_ptr< Dependence >	depends (Instruction Src, Instruction Dst, bool UnderRuntimeAssumptions=false)
	depends - Tests for a dependence between the Src and Dst instructions.

LLVM_ABI const SCEV *	getSplitIteration (const Dependence &Dep, unsigned Level)
	getSplitIteration - Give a dependence that's splittable at some particular level, return the iteration that should be used to split the loop.

Function *	getFunction () const

LLVM_ABI SCEVUnionPredicate	getRuntimeAssumptions () const
	getRuntimeAssumptions - Returns all the runtime assumptions under which the dependence test is valid.

Detailed Description

DependenceInfo - This class is the main dependence-analysis driver.

Definition at line 285 of file DependenceAnalysis.h.

Constructor & Destructor Documentation

◆ DependenceInfo()

llvm::DependenceInfo::DependenceInfo	(	Function *	F,
		AAResults *	AA,
		ScalarEvolution *	SE,
		LoopInfo *	LI
	)

inline

Definition at line 287 of file DependenceAnalysis.h.

References F.

Member Function Documentation

◆ depends()

std::unique_ptr< Dependence > DependenceInfo::depends	(	Instruction *	Src,
		Instruction *	Dst,
		bool	UnderRuntimeAssumptions = `false`
	)

depends - Tests for a dependence between the Src and Dst instructions.

Returns NULL if no dependence; otherwise, returns a Dependence (or a FullDependence) with as much information as can be gleaned. By default, the dependence test collects a set of runtime assumptions that cannot be solved at compilation time. By default UnderRuntimeAssumptions is false for a safe approximation of the dependence relation that does not require runtime checks.

Definition at line 3563 of file DependenceAnalysis.cpp.

References llvm::SmallBitVector::any(), assert(), llvm::SmallBitVector::count(), llvm::dbgs(), Delinearize, llvm::Done, dumpSmallBitVector(), llvm::Dependence::DVEntry::EQ, llvm::MemoryLocation::get(), llvm::Function::getDataLayout(), llvm::getLoadStorePointerOperand(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getPointerBase(), llvm::ScalarEvolution::getSCEV(), llvm::SCEV::getType(), llvm::ScalarEvolution::getZero(), I, II, llvm::ScalarEvolution::isKnownMultipleOf(), isLoadOrStore(), llvm::LocationSize::isPrecise(), llvm::SCEV::isZero(), LLVM_DEBUG, llvm_unreachable, Loops, llvm::AliasResult::MayAlias, llvm::AliasResult::MustAlias, N, llvm::AliasResult::NoAlias, llvm::Dependence::DVEntry::NONE, P, llvm::AliasResult::PartialAlias, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallBitVector::reset(), llvm::SmallVectorImpl< T >::resize(), llvm::SmallBitVector::set(), llvm::SmallBitVector::set_bits(), llvm::SmallVectorBase< Size_T >::size(), llvm::MemoryLocation::Size, llvm::LocationSize::toRaw(), and underlyingObjectsAlias().

Referenced by checkDependency(), llvm::DependenceGraphInfo< NodeType >::getDependencies(), llvm::IndexedReference::hasTemporalReuse(), llvm::isSafeToMoveBefore(), and populateDependencyMatrix().

◆ getFunction()

Function * llvm::DependenceInfo::getFunction ( ) const

inline

Definition at line 347 of file DependenceAnalysis.h.

◆ getRuntimeAssumptions()

SCEVUnionPredicate DependenceInfo::getRuntimeAssumptions ( ) const

getRuntimeAssumptions - Returns all the runtime assumptions under which the dependence test is valid.

Definition at line 3547 of file DependenceAnalysis.cpp.

◆ getSplitIteration()

const SCEV * DependenceInfo::getSplitIteration	(	const Dependence &	Dep,
		unsigned	Level
	)

getSplitIteration - Give a dependence that's splittable at some particular level, return the iteration that should be used to split the loop.

Generally, the dependence analyzer will be used to build a dependence graph for a function (basically a map from instructions to dependences). Looking for cycles in the graph shows us loops that cannot be trivially vectorized/parallelized.

We can try to improve the situation by examining all the dependences that make up the cycle, looking for ones we can break. Sometimes, peeling the first or last iteration of a loop will break dependences, and there are flags for those possibilities. Sometimes, splitting a loop at some other iteration will do the trick, and we've got a flag for that case. Rather than waste the space to record the exact iteration (since we rarely know), we provide a method that calculates the iteration. It's a drag that it must work from scratch, but wonderful in that it's possible.

Here's an example:

for (i = 0; i < 10; i++) A[i] = ... ... = A[11 - i]

There's a loop-carried flow dependence from the store to the load, found by the weak-crossing SIV test. The dependence will have a flag, indicating that the dependence can be broken by splitting the loop. Calling getSplitIteration will return 5. Splitting the loop breaks the dependence, like so:

for (i = 0; i <= 5; i++) A[i] = ... ... = A[11 - i] for (i = 6; i < 10; i++) A[i] = ... ... = A[11 - i]

breaks the dependence and allows us to vectorize/parallelize both loops.

Definition at line 4067 of file DependenceAnalysis.cpp.

References llvm::SmallBitVector::any(), assert(), llvm::dbgs(), Delinearize, llvm::Done, llvm::SmallBitVector::empty(), llvm::MemoryLocation::get(), llvm::Function::getDataLayout(), llvm::Dependence::getDst(), llvm::getLoadStorePointerOperand(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::ScalarEvolution::getSCEV(), llvm::Dependence::getSrc(), II, isLoadOrStore(), llvm::Dependence::isSplitable(), LLVM_DEBUG, llvm_unreachable, Loops, llvm::AliasResult::MustAlias, P, llvm::SmallBitVector::reset(), llvm::SmallVectorImpl< T >::resize(), llvm::SmallBitVector::set(), llvm::SmallBitVector::set_bits(), llvm::SmallVectorBase< Size_T >::size(), and underlyingObjectsAlias().

◆ invalidate()

bool DependenceInfo::invalidate	(	Function &	F,
		const PreservedAnalyses &	PA,
		FunctionAnalysisManager::Invalidator &	Inv
	)

Handle transitive invalidation when the cached analysis results go away.

Definition at line 3534 of file DependenceAnalysis.cpp.

References F, llvm::PreservedAnalyses::getChecker(), and llvm::AnalysisManager< IRUnitT, ExtraArgTs >::Invalidator::invalidate().

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

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

Public Member Functions