DependenceAnalysis.cpp File Reference

#include "llvm/Analysis/DependenceAnalysis.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/IR/Operator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/InstIterator.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 (DependenceAnalysis,"da","Dependence Analysis", true, true) INITIALIZE_PASS_END(DependenceAnalysis
static void	dumpExampleDependence (raw_ostream &OS, Function *F, DependenceAnalysis *DA)
static AliasAnalysis::AliasResult	underlyingObjectsAlias (AliasAnalysis *AA, const Value *A, const Value *B)
static bool	isLoadOrStore (const Instruction *I)
static Value *	getPointerOperand (Instruction *I)
static bool	findGCD (unsigned Bits, APInt AM, APInt BM, APInt Delta, APInt &G, APInt &X, APInt &Y)
static APInt	floorOfQuotient (APInt A, APInt B)
static APInt	ceilingOfQuotient (APInt A, 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 SCEVMulExpr *Product)
static void	dumpSmallBitVector (SmallBitVector &BV)

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

Macro Definition Documentation

#define DEBUG_TYPE   "da"

Definition at line 54 of file DependenceAnalysis.cpp.

Function Documentation

static APInt ceilingOfQuotient ( APInt  A, APInt  B  )

static

Definition at line 1328 of file DependenceAnalysis.cpp.

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

static void dumpExampleDependence ( raw_ostream &  OS, Function *  F, DependenceAnalysis *  DA  )

static

Definition at line 157 of file DependenceAnalysis.cpp.

References llvm::DependenceAnalysis::depends(), llvm::DependenceAnalysis::getSplitIteration(), llvm::inst_begin(), and llvm::inst_end().

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

static void dumpSmallBitVector ( SmallBitVector &  BV )

static

Definition at line 3233 of file DependenceAnalysis.cpp.

References llvm::dbgs(), llvm::SmallBitVector::find_first(), and llvm::SmallBitVector::find_next().

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

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

static

Definition at line 1281 of file DependenceAnalysis.cpp.

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

Referenced by llvm::SCEVAddRecExpr::delinearize().

static APInt floorOfQuotient ( APInt  A, APInt  B  )

static

Definition at line 1313 of file DependenceAnalysis.cpp.

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

static const SCEVConstant* getConstantPart ( const SCEVMulExpr *  Product )

static

Definition at line 2192 of file DependenceAnalysis.cpp.

References llvm::ISD::Constant, llvm::SCEVNAryExpr::getNumOperands(), and llvm::SCEVNAryExpr::getOperand().

static Value* getPointerOperand ( Instruction *  I )

static

Definition at line 655 of file DependenceAnalysis.cpp.

References LI, and llvm_unreachable.

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

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

static bool isLoadOrStore ( const Instruction *  I )

static

Definition at line 645 of file DependenceAnalysis.cpp.

References LI.

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

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

static

Definition at line 1542 of file DependenceAnalysis.cpp.

References llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), and llvm::APInt::srem().

static APInt maxAPInt ( APInt  A, APInt  B  )

static

Definition at line 1343 of file DependenceAnalysis.cpp.

References llvm::APInt::sgt().

static APInt minAPInt ( APInt  A, APInt  B  )

static

Definition at line 1349 of file DependenceAnalysis.cpp.

References llvm::APInt::slt().

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"
	)

static AliasAnalysis::AliasResult underlyingObjectsAlias ( AliasAnalysis *  AA, const Value *  A, const Value *  B  )

static

Definition at line 632 of file DependenceAnalysis.cpp.

References llvm::AliasAnalysis::alias(), llvm::Value::getType(), llvm::AliasAnalysis::getTypeStoreSize(), and llvm::GetUnderlyingObject().

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

Variable Documentation

Dependence Analysis

Definition at line 120 of file DependenceAnalysis.cpp.

da

Definition at line 120 of file DependenceAnalysis.cpp.

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

static

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

Dependence true

Definition at line 120 of file DependenceAnalysis.cpp.