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/OrderedBasicBlock.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/Analysis/PhiValues.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.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/User.h"
#include "llvm/IR/Value.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 "llvm/Support/MathExtras.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <utility>

Include dependency graph for MemoryDependenceAnalysis.cpp:

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. More...
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. More...
static bool	isVolatile (Instruction *Inst)
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. More...
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. More...
	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(1000), cl::desc("The number of blocks to scan during memory " "dependency analysis (default = 1000)"))
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 66 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 771 of file MemoryDependenceAnalysis.cpp.

References assert().

Referenced by llvm::MemoryDependenceResults::getNonLocalCallDependency(), and SortNonLocalDepInfoCache().

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

References llvm::BasicBlock::begin(), BlockScanLimit, llvm::MemoryLocation::get(), llvm::MemDepResult::getClobber(), llvm::MemDepResult::getDef(), llvm::Function::getEntryBlock(), llvm::MemoryLocation::getForArgument(), llvm::AAResults::getModRefInfo(), llvm::MemDepResult::getNonFuncLocal(), llvm::MemDepResult::getNonLocal(), llvm::BasicBlock::getParent(), llvm::MemDepResult::getUnknown(), llvm::Intrinsic::invariant_end, llvm::Intrinsic::invariant_start, llvm::isFreeCall(), llvm::Instruction::isIdenticalToWhenDefined(), llvm::isModOrRefSet(), llvm::isModSet(), llvm::isNoModRef(), llvm::Intrinsic::lifetime_end, llvm::Intrinsic::lifetime_start, llvm::Instruction::mayReadFromMemory(), llvm::Instruction::mayWriteToMemory(), llvm::Mod, llvm::ModRef, llvm::Monotonic, llvm::NoModRef, llvm::MemoryLocation::Ptr, llvm::Ref, and SI.

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

INITIALIZE_PASS_BEGIN()

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

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

isVolatile()

static bool isVolatile ( Instruction *  Inst )

static

Definition at line 318 of file MemoryDependenceAnalysis.cpp.

References SI.

Referenced by llvm::LoadInst::cloneImpl(), llvm::StoreInst::cloneImpl(), llvm::AtomicCmpXchgInst::cloneImpl(), llvm::AtomicRMWInst::cloneImpl(), llvm::FunctionComparator::cmpOperations(), combineStore(), llvm::IRBuilder< TargetFolder >::CreateAlignedLoad(), llvm::IRBuilder< TargetFolder >::CreateAlignedStore(), llvm::IRBuilder< TargetFolder >::CreateLoad(), llvm::IRBuilderBase::CreateMemCpy(), llvm::IRBuilderBase::CreateMemMove(), llvm::IRBuilderBase::CreateMemSet(), llvm::IRBuilder< TargetFolder >::CreateStore(), determinePointerReadAttrs(), emitSignedInt64(), llvm::X86SelectionDAGInfo::EmitTargetCodeForMemset(), foldBitcastedFPLogic(), foldICmpShlOne(), FunctionNumber(), llvm::MemoryDependenceResults::getNonLocalPointerDependency(), llvm::MemoryDependenceResults::getSimplePointerDependencyFrom(), hasNormalLoadOperand(), hasOnlySelectUsers(), haveSameSpecialState(), isRemovable(), IsSafeAndProfitableToMove(), isSafeAndProfitableToSinkLoad(), llvm::LoadInst::isSimple(), llvm::StoreInst::isSimple(), llvm::ImplicitControlFlowTracking::isSpecialInstruction(), isTruncateOf(), llvm::MachineMemOperand::isUnordered(), llvm::LoadInst::isUnordered(), llvm::StoreInst::isUnordered(), LLVMGetVolatile(), lowerVectorShuffleAsBroadcast(), maybePrintCallAddrSpace(), PerformInsertEltCombine(), performIntToFpCombine(), PerformVMOVRRDCombine(), pickOpcodeForVT(), llvm::PointerMayBeCaptured(), replaceShuffleOfInsert(), tryToFoldExtOfLoad(), and llvm::InstCombiner::visitFCmpInst().

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

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

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

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

References llvm::MemoryLocation::AATags, llvm::SmallVectorImpl< T >::append(), assert(), AssertSorted(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::SmallVectorTemplateCommon< T >::begin(), BlockNumberLimit, llvm::SmallVectorImpl< T >::clear(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::SmallVectorBase::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::SmallVectorTemplateCommon< T >::end(), entry, llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::PredIteratorCache::get(), llvm::PHITransAddr::getAddr(), llvm::Instruction::getParent(), llvm::MemDepResult::getUnknown(), llvm::LocationSize::getValue(), llvm::MemoryLocation::getWithNewPtr(), llvm::MemoryLocation::getWithNewSize(), llvm::MemoryLocation::getWithoutAATags(), llvm::LocationSize::hasValue(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), isLoad(), llvm::MemDepResult::isNonLocal(), llvm::PHITransAddr::IsPotentiallyPHITranslatable(), llvm::LocationSize::isPrecise(), llvm::DominatorTree::isReachableFromEntry(), LLVM_DEBUG, LLVM_FALLTHROUGH, llvm::PHITransAddr::NeedsPHITranslationFromBlock(), NumResultsLimit, P, llvm::PHITransAddr::PHITranslateValue(), llvm::SmallVectorTemplateBase< T >::pop_back(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), RemoveFromReverseMap(), llvm::reverse(), llvm::SmallVectorBase::size(), llvm::MemoryLocation::Size, llvm::sort(), llvm::upper_bound(), and VI.

STATISTIC() [1/7]

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

STATISTIC() [2/7]

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

STATISTIC() [3/7]

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

STATISTIC() [4/7]

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

STATISTIC() [5/7]

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

STATISTIC() [6/7]

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

STATISTIC() [7/7]

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

Variable Documentation

Analysis

Memory Dependence Analysis

Definition at line 1764 of file MemoryDependenceAnalysis.cpp.

BlockNumberLimit

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

static

Referenced by SortNonLocalDepInfoCache().

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

static

Referenced by llvm::MemoryDependenceResults::getDefaultBlockScanLimit(), GetLocation(), and llvm::MemoryDependenceResults::getSimplePointerDependencyFrom().

false

Memory Dependence false

Definition at line 1764 of file MemoryDependenceAnalysis.cpp.

memdep

memdep

Definition at line 1764 of file MemoryDependenceAnalysis.cpp.

NumResultsLimit

const unsigned int NumResultsLimit = 100

static

Definition at line 93 of file MemoryDependenceAnalysis.cpp.

Referenced by SortNonLocalDepInfoCache().