DependenceAnalysis.cpp File Reference

#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"

Include dependency graph for DependenceAnalysis.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "da"

Functions
	STATISTIC (TotalArrayPairs, "Array pairs tested")
	STATISTIC (SeparableSubscriptPairs, "Separable subscript pairs")
	STATISTIC (CoupledSubscriptPairs, "Coupled subscript pairs")
	STATISTIC (NonlinearSubscriptPairs, "Nonlinear subscript pairs")
	STATISTIC (ZIVapplications, "ZIV applications")
	STATISTIC (ZIVindependence, "ZIV independence")
	STATISTIC (StrongSIVapplications, "Strong SIV applications")
	STATISTIC (StrongSIVsuccesses, "Strong SIV successes")
	STATISTIC (StrongSIVindependence, "Strong SIV independence")
	STATISTIC (WeakCrossingSIVapplications, "Weak-Crossing SIV applications")
	STATISTIC (WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes")
	STATISTIC (WeakCrossingSIVindependence, "Weak-Crossing SIV independence")
	STATISTIC (ExactSIVapplications, "Exact SIV applications")
	STATISTIC (ExactSIVsuccesses, "Exact SIV successes")
	STATISTIC (ExactSIVindependence, "Exact SIV independence")
	STATISTIC (WeakZeroSIVapplications, "Weak-Zero SIV applications")
	STATISTIC (WeakZeroSIVsuccesses, "Weak-Zero SIV successes")
	STATISTIC (WeakZeroSIVindependence, "Weak-Zero SIV independence")
	STATISTIC (ExactRDIVapplications, "Exact RDIV applications")
	STATISTIC (ExactRDIVindependence, "Exact RDIV independence")
	STATISTIC (SymbolicRDIVapplications, "Symbolic RDIV applications")
	STATISTIC (SymbolicRDIVindependence, "Symbolic RDIV independence")
	STATISTIC (DeltaApplications, "Delta applications")
	STATISTIC (DeltaSuccesses, "Delta successes")
	STATISTIC (DeltaIndependence, "Delta independence")
	STATISTIC (DeltaPropagations, "Delta propagations")
	STATISTIC (GCDapplications, "GCD applications")
	STATISTIC (GCDsuccesses, "GCD successes")
	STATISTIC (GCDindependence, "GCD independence")
	STATISTIC (BanerjeeApplications, "Banerjee applications")
	STATISTIC (BanerjeeIndependence, "Banerjee independence")
	STATISTIC (BanerjeeSuccesses, "Banerjee successes")
	INITIALIZE_PASS_BEGIN (DependenceAnalysisWrapperPass, "da", "Dependence Analysis", true, true) INITIALIZE_PASS_END(DependenceAnalysisWrapperPass
static void	dumpExampleDependence (raw_ostream &OS, DependenceInfo *DA)
static AliasResult	underlyingObjectsAlias (AliasAnalysis *AA, const DataLayout &DL, const MemoryLocation &LocA, const MemoryLocation &LocB)
static bool	isLoadOrStore (const Instruction *I)
static bool	findGCD (unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y)
static APInt	floorOfQuotient (const APInt &A, const APInt &B)
static APInt	ceilingOfQuotient (const APInt &A, const APInt &B)
static APInt	maxAPInt (APInt A, APInt B)
static APInt	minAPInt (APInt A, APInt B)
static bool	isRemainderZero (const SCEVConstant *Dividend, const SCEVConstant *Divisor)
static const SCEVConstant *	getConstantPart (const SCEV *Expr)
static void	dumpSmallBitVector (SmallBitVector &BV)

Variables
static cl::opt< bool >	Delinearize ("da-delinearize", cl::init(true), cl::Hidden, cl::ZeroOrMore, cl::desc("Try to delinearize array references."))
	da
Dependence	Analysis
Dependence	true

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "da"

Definition at line 72 of file DependenceAnalysis.cpp.

Function Documentation

ceilingOfQuotient()

static APInt ceilingOfQuotient ( const APInt &  A, const APInt &  B  )

static

Definition at line 1445 of file DependenceAnalysis.cpp.

References llvm::APInt::sdivrem(), llvm::APInt::sgt(), and llvm::APInt::slt().

Referenced by isRemainderZero(), and minAPInt().

dumpExampleDependence()

static void dumpExampleDependence ( raw_ostream &  OS, DependenceInfo *  DA  )

static

Definition at line 165 of file DependenceAnalysis.cpp.

References D, llvm::DependenceInfo::depends(), F(), llvm::DependenceInfo::getFunction(), llvm::DependenceInfo::getSplitIteration(), llvm::inst_begin(), and llvm::inst_end().

Referenced by llvm::DependenceAnalysisWrapperPass::print(), and llvm::DependenceAnalysisPrinterPass::run().

dumpSmallBitVector()

static void dumpSmallBitVector ( SmallBitVector &  BV )

static

Definition at line 3361 of file DependenceAnalysis.cpp.

References llvm::dbgs(), llvm::SmallBitVector::find_next(), llvm::SmallBitVector::set_bits(), and VI.

Referenced by llvm::DependenceInfo::depends().

findGCD()

static bool findGCD ( unsigned  Bits, const APInt &  AM, const APInt &  BM, const APInt &  Delta, APInt &  G, APInt &  X, APInt &  Y  )

static

Definition at line 1402 of file DependenceAnalysis.cpp.

References llvm::APInt::abs(), llvm::dbgs(), LLVM_DEBUG, llvm::APInt::sdiv(), llvm::APInt::sdivrem(), llvm::APInt::slt(), and llvm::APInt::srem().

Referenced by isRemainderZero(), and minAPInt().

floorOfQuotient()

static APInt floorOfQuotient ( const APInt &  A, const APInt &  B  )

static

Definition at line 1432 of file DependenceAnalysis.cpp.

References llvm::APInt::sdivrem(), llvm::APInt::sgt(), and llvm::APInt::slt().

Referenced by isRemainderZero(), and minAPInt().

getConstantPart()

static const SCEVConstant* getConstantPart ( const SCEV *  Expr )

static

Definition at line 2294 of file DependenceAnalysis.cpp.

References llvm::APInt::abs(), llvm::Dependence::DVEntry::ALL, assert(), B, C, llvm::dbgs(), llvm::Dependence::DVEntry::Direction, llvm::Dependence::DVEntry::Distance, llvm::Dependence::dump(), llvm::dyn_cast(), llvm::Dependence::DVEntry::EQ, llvm::SCEV::FlagAnyWrap, llvm::SCEVConstant::getAPInt(), llvm::getLoadStorePointerOperand(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::APInt::getNullValue(), llvm::Instruction::getParent(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEV::getType(), llvm::APIntOps::GreatestCommonDivisor(), llvm::Dependence::DVEntry::GT, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::SCEVAddRecExpr::isAffine(), llvm::isKnownNonNegative(), isLoadOrStore(), llvm::SCEV::isZero(), isZero(), LLVM_DEBUG, llvm_unreachable, llvm::Lower, llvm::Dependence::DVEntry::LT, llvm::Dependence::DVEntry::NONE, llvm::SmallVectorImpl< T >::resize(), llvm::Dependence::DVEntry::Scalar, llvm::APInt::sdiv(), llvm::SmallBitVector::set_bits(), llvm::SmallVectorBase::size(), llvm::size(), llvm::APInt::srem(), and llvm::Upper.

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	DependenceAnalysisWrapperPass	,
		"da"	,
		"Dependence Analysis"	,
		true	,
		true
	)

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

isLoadOrStore()

static bool isLoadOrStore ( const Instruction *  I )

static

Definition at line 670 of file DependenceAnalysis.cpp.

References assert(), D, llvm::dyn_cast(), llvm::IntegerType::getBitWidth(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::SCEVCastExpr::getOperand(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::SCEV::getType(), isLoopInvariant(), Loops, llvm::SmallBitVector::set(), and SI.

Referenced by llvm::DependenceInfo::depends(), getConstantPart(), and llvm::DependenceInfo::getSplitIteration().

isRemainderZero()

static bool isRemainderZero ( const SCEVConstant *  Dividend, const SCEVConstant *  Divisor  )

static

Definition at line 1656 of file DependenceAnalysis.cpp.

References assert(), llvm::tgtok::Bits, ceilingOfQuotient(), llvm::dbgs(), llvm::dyn_cast(), findGCD(), floorOfQuotient(), G, llvm::Dependence::DVEntry::GE, llvm::SCEVConstant::getAPInt(), llvm::APInt::getBitWidth(), llvm::SCEVAddRecExpr::getLoop(), llvm::APInt::getSignedMaxValue(), llvm::APInt::getSignedMinValue(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEV::getType(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::Dependence::DVEntry::LE, LLVM_DEBUG, llvm_unreachable, maxAPInt(), minAPInt(), llvm::APInt::sdiv(), llvm::APInt::sgt(), llvm::APInt::srem(), X, and Y.

maxAPInt()

static APInt maxAPInt ( APInt  A, APInt  B  )

static

Definition at line 1460 of file DependenceAnalysis.cpp.

References B, and llvm::APInt::sgt().

Referenced by isRemainderZero(), and minAPInt().

minAPInt()

static APInt minAPInt ( APInt  A, APInt  B  )

static

Definition at line 1466 of file DependenceAnalysis.cpp.

References assert(), B, llvm::tgtok::Bits, ceilingOfQuotient(), llvm::dbgs(), llvm::dyn_cast(), llvm::Dependence::DVEntry::EQ, findGCD(), floorOfQuotient(), G, llvm::SCEVConstant::getAPInt(), llvm::APInt::getBitWidth(), llvm::APInt::getSignedMaxValue(), llvm::APInt::getSignedMinValue(), llvm::SCEV::getType(), llvm::Dependence::DVEntry::GT, LLVM_DEBUG, llvm::Dependence::DVEntry::LT, maxAPInt(), llvm::Dependence::DVEntry::NONE, llvm::APInt::sdiv(), llvm::APInt::sgt(), llvm::APInt::sle(), llvm::APInt::slt(), X, and Y.

Referenced by isRemainderZero().

STATISTIC() [1/32]

STATISTIC	(	TotalArrayPairs	,
		"Array pairs tested"
	)

STATISTIC() [2/32]

STATISTIC	(	SeparableSubscriptPairs	,
		"Separable subscript pairs"
	)

STATISTIC() [3/32]

STATISTIC	(	CoupledSubscriptPairs	,
		"Coupled subscript pairs"
	)

STATISTIC() [4/32]

STATISTIC	(	NonlinearSubscriptPairs	,
		"Nonlinear subscript pairs"
	)

STATISTIC() [5/32]

STATISTIC	(	ZIVapplications	,
		"ZIV applications"
	)

STATISTIC() [6/32]

STATISTIC	(	ZIVindependence	,
		"ZIV independence"
	)

STATISTIC() [7/32]

STATISTIC	(	StrongSIVapplications	,
		"Strong SIV applications"
	)

STATISTIC() [8/32]

STATISTIC	(	StrongSIVsuccesses	,
		"Strong SIV successes"
	)

STATISTIC() [9/32]

STATISTIC	(	StrongSIVindependence	,
		"Strong SIV independence"
	)

STATISTIC() [10/32]

STATISTIC	(	WeakCrossingSIVapplications	,
		"Weak-Crossing SIV applications"
	)

STATISTIC() [11/32]

STATISTIC	(	WeakCrossingSIVsuccesses	,
		"Weak-Crossing SIV successes"
	)

STATISTIC() [12/32]

STATISTIC	(	WeakCrossingSIVindependence	,
		"Weak-Crossing SIV independence"
	)

STATISTIC() [13/32]

STATISTIC	(	ExactSIVapplications	,
		"Exact SIV applications"
	)

STATISTIC() [14/32]

STATISTIC	(	ExactSIVsuccesses	,
		"Exact SIV successes"
	)

STATISTIC() [15/32]

STATISTIC	(	ExactSIVindependence	,
		"Exact SIV independence"
	)

STATISTIC() [16/32]

STATISTIC	(	WeakZeroSIVapplications	,
		"Weak-Zero SIV applications"
	)

STATISTIC() [17/32]

STATISTIC	(	WeakZeroSIVsuccesses	,
		"Weak-Zero SIV successes"
	)

STATISTIC() [18/32]

STATISTIC	(	WeakZeroSIVindependence	,
		"Weak-Zero SIV independence"
	)

STATISTIC() [19/32]

STATISTIC	(	ExactRDIVapplications	,
		"Exact RDIV applications"
	)

STATISTIC() [20/32]

STATISTIC	(	ExactRDIVindependence	,
		"Exact RDIV independence"
	)

STATISTIC() [21/32]

STATISTIC	(	SymbolicRDIVapplications	,
		"Symbolic RDIV applications"
	)

STATISTIC() [22/32]

STATISTIC	(	SymbolicRDIVindependence	,
		"Symbolic RDIV independence"
	)

STATISTIC() [23/32]

STATISTIC	(	DeltaApplications	,
		"Delta applications"
	)

STATISTIC() [24/32]

STATISTIC	(	DeltaSuccesses	,
		"Delta successes"
	)

STATISTIC() [25/32]

STATISTIC	(	DeltaIndependence	,
		"Delta independence"
	)

STATISTIC() [26/32]

STATISTIC	(	DeltaPropagations	,
		"Delta propagations"
	)

STATISTIC() [27/32]

STATISTIC	(	GCDapplications	,
		"GCD applications"
	)

STATISTIC() [28/32]

STATISTIC	(	GCDsuccesses	,
		"GCD successes"
	)

STATISTIC() [29/32]

STATISTIC	(	GCDindependence	,
		"GCD independence"
	)

STATISTIC() [30/32]

STATISTIC	(	BanerjeeApplications	,
		"Banerjee applications"
	)

STATISTIC() [31/32]

STATISTIC	(	BanerjeeIndependence	,
		"Banerjee independence"
	)

STATISTIC() [32/32]

STATISTIC	(	BanerjeeSuccesses	,
		"Banerjee successes"
	)

underlyingObjectsAlias()

static AliasResult underlyingObjectsAlias ( AliasAnalysis *  AA, const DataLayout &  DL, const MemoryLocation &  LocA, const MemoryLocation &  LocB  )

static

Definition at line 637 of file DependenceAnalysis.cpp.

References llvm::MemoryLocation::AATags, llvm::AAResults::alias(), llvm::GetUnderlyingObject(), llvm::isIdentifiedObject(), llvm::MayAlias, llvm::MustAlias, llvm::NoAlias, llvm::MemoryLocation::Ptr, and llvm::LocationSize::unknown().

Referenced by llvm::DependenceInfo::depends(), and llvm::DependenceInfo::getSplitIteration().

Variable Documentation

Analysis

Dependence Analysis

Definition at line 132 of file DependenceAnalysis.cpp.

da

da

Definition at line 132 of file DependenceAnalysis.cpp.

Delinearize

cl::opt<bool> Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::ZeroOrMore, cl::desc("Try to delinearize array references."))

static

Referenced by llvm::DependenceInfo::depends(), and llvm::DependenceInfo::getSplitIteration().

true

Dependence true

Definition at line 132 of file DependenceAnalysis.cpp.