DependenceAnalysis.cpp File Reference

#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Delinearization.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Module.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"

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, ScalarEvolution &SE, bool NormalizeResults)
static AliasResult	underlyingObjectsAlias (AAResults *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 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::desc("Try to delinearize array references."))
static cl::opt< bool >	DisableDelinearizationChecks ("da-disable-delinearization-checks", cl::Hidden, cl::desc("Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension."))
static cl::opt< unsigned >	MIVMaxLevelThreshold ("da-miv-max-level-threshold", cl::init(7), cl::Hidden, cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors."))
	da
Dependence	Analysis
Dependence	true

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "da"

Definition at line 70 of file DependenceAnalysis.cpp.

Function Documentation

ceilingOfQuotient()

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

static

Definition at line 1534 of file DependenceAnalysis.cpp.

References A, B, and llvm::APInt::sdivrem().

dumpExampleDependence()

static void dumpExampleDependence ( raw_ostream &  OS, DependenceInfo *  DA, ScalarEvolution &  SE, bool  NormalizeResults  )

static

Definition at line 179 of file DependenceAnalysis.cpp.

References D, F, llvm::inst_begin(), llvm::inst_end(), and OS.

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

dumpSmallBitVector()

static void dumpSmallBitVector ( SmallBitVector &  BV )

static

Definition at line 3553 of file DependenceAnalysis.cpp.

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

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

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

floorOfQuotient()

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

static

Definition at line 1521 of file DependenceAnalysis.cpp.

References A, B, and llvm::APInt::sdivrem().

getConstantPart()

static const SCEVConstant * getConstantPart ( const SCEV *  Expr )

static

Definition at line 2374 of file DependenceAnalysis.cpp.

INITIALIZE_PASS_BEGIN()

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

isLoadOrStore()

static bool isLoadOrStore ( const Instruction *  I )

static

Definition at line 750 of file DependenceAnalysis.cpp.

References I.

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

isRemainderZero()

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

static

Definition at line 1720 of file DependenceAnalysis.cpp.

References llvm::SCEVConstant::getAPInt(), and llvm::APInt::srem().

STATISTIC() [1/32]

STATISTIC	(	BanerjeeApplications	,
		"Banerjee applications"
	)

STATISTIC() [2/32]

STATISTIC	(	BanerjeeIndependence	,
		"Banerjee independence"
	)

STATISTIC() [3/32]

STATISTIC	(	BanerjeeSuccesses	,
		"Banerjee successes"
	)

STATISTIC() [4/32]

STATISTIC	(	CoupledSubscriptPairs	,
		"Coupled subscript pairs"
	)

STATISTIC() [5/32]

STATISTIC	(	DeltaApplications	,
		"Delta applications"
	)

STATISTIC() [6/32]

STATISTIC	(	DeltaIndependence	,
		"Delta independence"
	)

STATISTIC() [7/32]

STATISTIC	(	DeltaPropagations	,
		"Delta propagations"
	)

STATISTIC() [8/32]

STATISTIC	(	DeltaSuccesses	,
		"Delta successes"
	)

STATISTIC() [9/32]

STATISTIC	(	ExactRDIVapplications	,
		"Exact RDIV applications"
	)

STATISTIC() [10/32]

STATISTIC	(	ExactRDIVindependence	,
		"Exact RDIV independence"
	)

STATISTIC() [11/32]

STATISTIC	(	ExactSIVapplications	,
		"Exact SIV applications"
	)

STATISTIC() [12/32]

STATISTIC	(	ExactSIVindependence	,
		"Exact SIV independence"
	)

STATISTIC() [13/32]

STATISTIC	(	ExactSIVsuccesses	,
		"Exact SIV successes"
	)

STATISTIC() [14/32]

STATISTIC	(	GCDapplications	,
		"GCD applications"
	)

STATISTIC() [15/32]

STATISTIC	(	GCDindependence	,
		"GCD independence"
	)

STATISTIC() [16/32]

STATISTIC	(	GCDsuccesses	,
		"GCD successes"
	)

STATISTIC() [17/32]

STATISTIC	(	NonlinearSubscriptPairs	,
		"Nonlinear subscript pairs"
	)

STATISTIC() [18/32]

STATISTIC	(	SeparableSubscriptPairs	,
		"Separable subscript pairs"
	)

STATISTIC() [19/32]

STATISTIC	(	StrongSIVapplications	,
		"Strong SIV applications"
	)

STATISTIC() [20/32]

STATISTIC	(	StrongSIVindependence	,
		"Strong SIV independence"
	)

STATISTIC() [21/32]

STATISTIC	(	StrongSIVsuccesses	,
		"Strong SIV successes"
	)

STATISTIC() [22/32]

STATISTIC	(	SymbolicRDIVapplications	,
		"Symbolic RDIV applications"
	)

STATISTIC() [23/32]

STATISTIC	(	SymbolicRDIVindependence	,
		"Symbolic RDIV independence"
	)

STATISTIC() [24/32]

STATISTIC	(	TotalArrayPairs	,
		"Array pairs tested"
	)

STATISTIC() [25/32]

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

STATISTIC() [26/32]

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

STATISTIC() [27/32]

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

STATISTIC() [28/32]

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

STATISTIC() [29/32]

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

STATISTIC() [30/32]

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

STATISTIC() [31/32]

STATISTIC	(	ZIVapplications	,
		"ZIV applications"
	)

STATISTIC() [32/32]

STATISTIC	(	ZIVindependence	,
		"ZIV independence"
	)

underlyingObjectsAlias()

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

static

Definition at line 715 of file DependenceAnalysis.cpp.

References llvm::MemoryLocation::AATags, llvm::MemoryLocation::getBeforeOrAfter(), llvm::getUnderlyingObject(), llvm::isIdentifiedObject(), llvm::AAResults::isNoAlias(), llvm::AliasResult::MayAlias, llvm::AliasResult::MustAlias, llvm::AliasResult::NoAlias, and llvm::MemoryLocation::Ptr.

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

Variable Documentation

Analysis

Dependence Analysis

Definition at line 142 of file DependenceAnalysis.cpp.

da

da

Definition at line 142 of file DependenceAnalysis.cpp.

Delinearize

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

static

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

DisableDelinearizationChecks

cl::opt< bool > DisableDelinearizationChecks("da-disable-delinearization-checks", cl::Hidden, cl::desc( "Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension.")) ( "da-disable-delinearization-checks"  , cl::Hidden  , cl::desc( "Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension.")    )

static

MIVMaxLevelThreshold

cl::opt< unsigned > MIVMaxLevelThreshold("da-miv-max-level-threshold", cl::init(7), cl::Hidden, cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors.")) ( "da-miv-max-level-threshold"  , cl::init(7)  , cl::Hidden  , cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors.")    )

static

true

Dependence true

Definition at line 143 of file DependenceAnalysis.cpp.