MemoryDependenceAnalysis.cpp File Reference

#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PredIteratorCache.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/AtomicOrdering.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <utility>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "memdep"

Functions
	STATISTIC (NumCacheNonLocal, "Number of fully cached non-local responses")
	STATISTIC (NumCacheDirtyNonLocal, "Number of dirty cached non-local responses")
	STATISTIC (NumUncacheNonLocal, "Number of uncached non-local responses")
	STATISTIC (NumCacheNonLocalPtr, "Number of fully cached non-local ptr responses")
	STATISTIC (NumCacheDirtyNonLocalPtr, "Number of cached, but dirty, non-local ptr responses")
	STATISTIC (NumUncacheNonLocalPtr, "Number of uncached non-local ptr responses")
	STATISTIC (NumCacheCompleteNonLocalPtr, "Number of block queries that were completely cached")
template<typename KeyTy >
static void	RemoveFromReverseMap (DenseMap< Instruction *, SmallPtrSet< KeyTy, 4 > > &ReverseMap, Instruction *Inst, KeyTy Val)
	This is a helper function that removes Val from 'Inst's set in ReverseMap.
static ModRefInfo	GetLocation (const Instruction *Inst, MemoryLocation &Loc, const TargetLibraryInfo &TLI)
	If the given instruction references a specific memory location, fill in Loc with the details, otherwise set Loc.Ptr to null.
static bool	canSkipClobberingStore (const StoreInst *SI, const MemoryLocation &MemLoc, Align MemLocAlign, BatchAAResults &BatchAA, unsigned ScanLimit)
static void	AssertSorted (MemoryDependenceResults::NonLocalDepInfo &Cache, int Count=-1)
	This method is used when -debug is specified to verify that cache arrays are properly kept sorted.
static void	SortNonLocalDepInfoCache (MemoryDependenceResults::NonLocalDepInfo &Cache, unsigned NumSortedEntries)
	Sort the NonLocalDepInfo cache, given a certain number of elements in the array that are already properly ordered.
	INITIALIZE_PASS_BEGIN (MemoryDependenceWrapperPass, "memdep", "Memory Dependence Analysis", false, true) INITIALIZE_PASS_END(MemoryDependenceWrapperPass

Variables
static cl::opt< unsigned >	BlockScanLimit ("memdep-block-scan-limit", cl::Hidden, cl::init(100), cl::desc("The number of instructions to scan in a block in memory " "dependency analysis (default = 100)"))
static cl::opt< unsigned >	BlockNumberLimit ("memdep-block-number-limit", cl::Hidden, cl::init(200), cl::desc("The number of blocks to scan during memory " "dependency analysis (default = 200)"))
static const unsigned int	NumResultsLimit = 100
	memdep
Memory Dependence	Analysis
Memory Dependence	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "memdep"

Definition at line 57 of file MemoryDependenceAnalysis.cpp.

Function Documentation

AssertSorted()

static void AssertSorted ( MemoryDependenceResults::NonLocalDepInfo &  Cache, int  Count = -1  )

static

This method is used when -debug is specified to verify that cache arrays are properly kept sorted.

Definition at line 737 of file MemoryDependenceAnalysis.cpp.

References assert().

Referenced by llvm::MemoryDependenceResults::getNonLocalCallDependency().

canSkipClobberingStore()

static bool canSkipClobberingStore ( const StoreInst *  SI, const MemoryLocation &  MemLoc, Align  MemLocAlign, BatchAAResults &  BatchAA, unsigned  ScanLimit  )

static

Definition at line 368 of file MemoryDependenceAnalysis.cpp.

References llvm::BatchAAResults::alias(), llvm::MemoryLocation::get(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::getKnownMinValue(), llvm::BatchAAResults::getModRefInfo(), llvm::LocationSize::getValue(), llvm::LocationSize::hasValue(), I, llvm::isModSet(), llvm::LocationSize::isScalable(), llvm::AliasResult::MustAlias, llvm::MemoryLocation::Size, and Size.

Referenced by llvm::MemoryDependenceResults::getSimplePointerDependencyFrom().

GetLocation()

static ModRefInfo GetLocation ( const Instruction *  Inst, MemoryLocation &  Loc, const TargetLibraryInfo &  TLI  )

static

If the given instruction references a specific memory location, fill in Loc with the details, otherwise set Loc.Ptr to null.

Returns a ModRefInfo value describing the general behavior of the instruction.

Definition at line 108 of file MemoryDependenceAnalysis.cpp.

References llvm::MemoryLocation::get(), llvm::MemoryLocation::getAfter(), llvm::MemoryLocation::getForArgument(), llvm::getFreedOperand(), llvm::Instruction::mayReadFromMemory(), and llvm::Instruction::mayWriteToMemory().

Referenced by llvm::MemoryDependenceResults::getDependency(), and llvm::MemoryDependenceResults::getSimplePointerDependencyFrom().

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	MemoryDependenceWrapperPass	,
		"memdep"	,
		"Memory Dependence Analysis"	,
		false	,
		true
	)

RemoveFromReverseMap()

template<typename KeyTy >

static void RemoveFromReverseMap ( DenseMap< Instruction *, SmallPtrSet< KeyTy, 4 > > &  ReverseMap, Instruction *  Inst, KeyTy  Val  )

static

This is a helper function that removes Val from 'Inst's set in ReverseMap.

If the set becomes empty, remove Inst's entry.

Definition at line 91 of file MemoryDependenceAnalysis.cpp.

References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find().

Referenced by llvm::MemoryDependenceResults::getDependency(), and llvm::MemoryDependenceResults::removeInstruction().

SortNonLocalDepInfoCache()

static void SortNonLocalDepInfoCache ( MemoryDependenceResults::NonLocalDepInfo &  Cache, unsigned  NumSortedEntries  )

static

Sort the NonLocalDepInfo cache, given a certain number of elements in the array that are already properly ordered.

This is optimized for the case when only a few entries are added.

Definition at line 1021 of file MemoryDependenceAnalysis.cpp.

References llvm::sort(), and llvm::upper_bound().

STATISTIC() [1/7]

STATISTIC	(	NumCacheCompleteNonLocalPtr	,
		"Number of block queries that were completely cached"
	)

STATISTIC() [2/7]

STATISTIC	(	NumCacheDirtyNonLocal	,
		"Number of dirty cached non-local responses"
	)

STATISTIC() [3/7]

STATISTIC	(	NumCacheDirtyNonLocalPtr	,
		"Number of	cached,
		but	dirty,
		non-local ptr responses"
	)

STATISTIC() [4/7]

STATISTIC	(	NumCacheNonLocal	,
		"Number of fully cached non-local responses"
	)

STATISTIC() [5/7]

STATISTIC	(	NumCacheNonLocalPtr	,
		"Number of fully cached non-local ptr responses"
	)

STATISTIC() [6/7]

STATISTIC	(	NumUncacheNonLocal	,
		"Number of uncached non-local responses"
	)

STATISTIC() [7/7]

STATISTIC	(	NumUncacheNonLocalPtr	,
		"Number of uncached non-local ptr responses"
	)

Variable Documentation

Analysis

Memory Dependence Analysis

Definition at line 1779 of file MemoryDependenceAnalysis.cpp.

BlockNumberLimit

cl::opt< unsigned > BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(200), cl::desc("The number of blocks to scan during memory " "dependency analysis (default = 200)")) ( "memdep-block-number-limit"  , cl::Hidden  , cl::init(200)  , cl::desc("The number of blocks to scan during memory " "dependency analysis (default = 200)")    )

static

BlockScanLimit

cl::opt< unsigned > BlockScanLimit("memdep-block-scan-limit", cl::Hidden, cl::init(100), cl::desc("The number of instructions to scan in a block in memory " "dependency analysis (default = 100)")) ( "memdep-block-scan-limit"  , cl::Hidden  , cl::init(100)  , cl::desc("The number of instructions to scan in a block in memory " "dependency analysis (default = 100)")    )

static

Referenced by llvm::MemoryDependenceWrapperPass::runOnFunction().

false

Memory Dependence false

Definition at line 1779 of file MemoryDependenceAnalysis.cpp.

memdep

memdep

Definition at line 1778 of file MemoryDependenceAnalysis.cpp.

NumResultsLimit

const unsigned int NumResultsLimit = 100

static

Definition at line 84 of file MemoryDependenceAnalysis.cpp.