LLVM  6.0.0svn
Classes | Public Member Functions | List of all members
llvm::DependenceInfo Class Reference

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

#include "llvm/Analysis/DependenceAnalysis.h"

Public Member Functions

 DependenceInfo (Function *F, AliasAnalysis *AA, ScalarEvolution *SE, LoopInfo *LI)
 
std::unique_ptr< Dependencedepends (Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
 depends - Tests for a dependence between the Src and Dst instructions. More...
 
const SCEVgetSplitIteration (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. More...
 
FunctiongetFunction () const
 

Detailed Description

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

Definition at line 272 of file DependenceAnalysis.h.

Constructor & Destructor Documentation

◆ DependenceInfo()

llvm::DependenceInfo::DependenceInfo ( Function F,
AliasAnalysis AA,
ScalarEvolution SE,
LoopInfo LI 
)
inline

Definition at line 274 of file DependenceAnalysis.h.

Member Function Documentation

◆ depends()

std::unique_ptr< Dependence > DependenceInfo::depends ( Instruction Src,
Instruction Dst,
bool  PossiblyLoopIndependent 
)

◆ getFunction()

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

◆ 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 3746 of file DependenceAnalysis.cpp.

References llvm::SmallBitVector::any(), assert(), llvm::SmallBitVector::count(), llvm::dbgs(), DEBUG, Delinearize, llvm::dyn_cast(), F(), llvm::Dependence::getDst(), llvm::User::getNumOperands(), llvm::Instruction::getParent(), llvm::GEPOperator::getPointerOperand(), getPointerOperand(), llvm::GEPOperator::getPointerOperandType(), llvm::Dependence::getSrc(), llvm::GEPOperator::idx_begin(), llvm::GEPOperator::idx_end(), isLoadOrStore(), isLoopInvariant(), llvm::Dependence::isSplitable(), llvm_unreachable, llvm::Instruction::mayReadFromMemory(), llvm::Instruction::mayWriteToMemory(), llvm::MustAlias, P, propagate(), llvm::SmallBitVector::reset(), llvm::SmallVectorImpl< T >::resize(), llvm::SmallBitVector::set(), llvm::SmallBitVector::set_bits(), SI, llvm::SmallVectorTemplateCommon< T >::size(), and underlyingObjectsAlias().

Referenced by dumpExampleDependence().


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