#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>

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 cl::opt< unsigned >	CacheGlobalLimit ("memdep-cache-global-limit", cl::Hidden, cl::init(10000), cl::desc("The max number of entries allowed in a cache (default = 10000)"))
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()

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 704 of file MemoryDependenceAnalysis.cpp.

References assert(), and llvm::Count.

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

◆ canSkipClobberingStore()

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

static

Definition at line 344 of file MemoryDependenceAnalysis.cpp.

References llvm::BatchAAResults::alias(), llvm::dyn_cast(), 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, Size, and llvm::MemoryLocation::Size.

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

◆ GetLocation()

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 112 of file MemoryDependenceAnalysis.cpp.

References llvm::dyn_cast(), llvm::MemoryLocation::get(), llvm::MemoryLocation::getAfter(), llvm::MemoryLocation::getForArgument(), llvm::getFreedOperand(), II, llvm::Instruction::mayReadFromMemory(), llvm::Instruction::mayWriteToMemory(), llvm::Mod, llvm::ModRef, llvm::Monotonic, llvm::NoModRef, and llvm::Ref.

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

◆ INITIALIZE_PASS_BEGIN()

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

References INITIALIZE_PASS_DEPENDENCY.

◆ RemoveFromReverseMap()

template<typename KeyTy>

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 95 of file MemoryDependenceAnalysis.cpp.

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

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

◆ SortNonLocalDepInfoCache()

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 988 of file MemoryDependenceAnalysis.cpp.

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

◆ 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 1734 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::MemoryDependenceAnalysis::MemoryDependenceAnalysis(), and llvm::MemoryDependenceWrapperPass::runOnFunction().

◆ CacheGlobalLimit

cl::opt< unsigned > CacheGlobalLimit("memdep-cache-global-limit", cl::Hidden, cl::init(10000), cl::desc("The max number of entries allowed in a cache (default = 10000)"))	(	"memdep-cache-global-limit"	,
		cl::Hidden	,
		cl::init(10000)	,
		cl::desc("The max number of entries allowed in a cache (default = 10000)")	)

static

◆ false

Memory Dependence false

Definition at line 1734 of file MemoryDependenceAnalysis.cpp.

◆ memdep

memdep

Definition at line 1733 of file MemoryDependenceAnalysis.cpp.

◆ NumResultsLimit

const unsigned int NumResultsLimit = 100

static

Definition at line 88 of file MemoryDependenceAnalysis.cpp.

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ AssertSorted()

◆ canSkipClobberingStore()

◆ GetLocation()

◆ INITIALIZE_PASS_BEGIN()

◆ RemoveFromReverseMap()

◆ SortNonLocalDepInfoCache()

◆ STATISTIC() [1/7]

◆ STATISTIC() [2/7]

◆ STATISTIC() [3/7]

◆ STATISTIC() [4/7]

◆ STATISTIC() [5/7]

◆ STATISTIC() [6/7]

◆ STATISTIC() [7/7]

Variable Documentation

◆ Analysis

◆ BlockNumberLimit

◆ BlockScanLimit

◆ CacheGlobalLimit

◆ false

◆ memdep

◆ NumResultsLimit