GVN.cpp File Reference

#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionTracker.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include <vector>

Include dependency graph for GVN.cpp:

Go to the source code of this file.

Classes
struct	llvm::DenseMapInfo< Expression >
Namespaces
namespace	llvm
	List of target independent CodeGen pass IDs.
Defines
#define	DEBUG_TYPE   "gvn"
Functions
	STATISTIC (NumGVNInstr,"Number of instructions deleted")
	STATISTIC (NumGVNLoad,"Number of loads deleted")
	STATISTIC (NumGVNPRE,"Number of instructions PRE'd")
	STATISTIC (NumGVNBlocks,"Number of blocks merged")
	STATISTIC (NumGVNSimpl,"Number of instructions simplified")
	STATISTIC (NumGVNEqProp,"Number of equalities propagated")
	STATISTIC (NumPRELoad,"Number of loads PRE'd")
static bool	IsValueFullyAvailableInBlock (BasicBlock *BB, DenseMap< BasicBlock *, char > &FullyAvailableBlocks, uint32_t RecurseDepth)
static bool	CanCoerceMustAliasedValueToLoad (Value *StoredVal, Type *LoadTy, const DataLayout &DL)
static Value *	CoerceAvailableValueToLoadType (Value *StoredVal, Type *LoadedTy, Instruction *InsertPt, const DataLayout &DL)
static int	AnalyzeLoadFromClobberingWrite (Type *LoadTy, Value *LoadPtr, Value *WritePtr, uint64_t WriteSizeInBits, const DataLayout &DL)
static int	AnalyzeLoadFromClobberingStore (Type *LoadTy, Value *LoadPtr, StoreInst *DepSI, const DataLayout &DL)
static int	AnalyzeLoadFromClobberingLoad (Type *LoadTy, Value *LoadPtr, LoadInst *DepLI, const DataLayout &DL)
static int	AnalyzeLoadFromClobberingMemInst (Type *LoadTy, Value *LoadPtr, MemIntrinsic *MI, const DataLayout &DL)
static Value *	GetStoreValueForLoad (Value *SrcVal, unsigned Offset, Type *LoadTy, Instruction *InsertPt, const DataLayout &DL)
static Value *	GetLoadValueForLoad (LoadInst *SrcVal, unsigned Offset, Type *LoadTy, Instruction *InsertPt, GVN &gvn)
static Value *	GetMemInstValueForLoad (MemIntrinsic *SrcInst, unsigned Offset, Type *LoadTy, Instruction *InsertPt, const DataLayout &DL)
static Value *	ConstructSSAForLoadSet (LoadInst *LI, SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, GVN &gvn)
static bool	isLifetimeStart (const Instruction *Inst)
static void	patchReplacementInstruction (Instruction *I, Value *Repl)
static void	patchAndReplaceAllUsesWith (Instruction *I, Value *Repl)
static bool	isOnlyReachableViaThisEdge (const BasicBlockEdge &E, DominatorTree *DT)
Variables
static cl::opt< bool >	EnablePRE ("enable-pre", cl::init(true), cl::Hidden)
static cl::opt< bool >	EnableLoadPRE ("enable-load-pre", cl::init(true))
static cl::opt< uint32_t >	MaxRecurseDepth ("max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore, cl::desc("Max recurse depth (default = 1000)"))

---

Define Documentation

#define DEBUG_TYPE   "gvn"

Definition at line 55 of file GVN.cpp.

---

Function Documentation

static int AnalyzeLoadFromClobberingLoad	(	Type *	LoadTy,
		Value *	LoadPtr,
		LoadInst *	DepLI,
		const DataLayout &	DL
	)		[static]

AnalyzeLoadFromClobberingLoad - This function is called when we have a memdep query of a load that ends up being clobbered by another load. See if the other load can feed into the second load.

Definition at line 1038 of file GVN.cpp.

References AnalyzeLoadFromClobberingWrite(), llvm::MemoryDependenceAnalysis::getLoadLoadClobberFullWidthSize(), llvm::GetPointerBaseWithConstantOffset(), llvm::LoadInst::getPointerOperand(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), llvm::DataLayout::getTypeStoreSize(), llvm::Type::isArrayTy(), and llvm::Type::isStructTy().

static int AnalyzeLoadFromClobberingMemInst	(	Type *	LoadTy,
		Value *	LoadPtr,
		MemIntrinsic *	MI,
		const DataLayout &	DL
	)		[static]

Definition at line 1065 of file GVN.cpp.

References AnalyzeLoadFromClobberingWrite(), llvm::ConstantFoldLoadFromConstPtr(), llvm::dyn_cast(), llvm::ConstantInt::get(), llvm::PointerType::get(), llvm::ConstantExpr::getBitCast(), llvm::MemIntrinsic::getDest(), llvm::ConstantExpr::getGetElementPtr(), llvm::Type::getInt64Ty(), llvm::Type::getInt8PtrTy(), llvm::IntrinsicInst::getIntrinsicID(), llvm::MemIntrinsic::getLength(), llvm::MemTransferInst::getSource(), llvm::GetUnderlyingObject(), llvm::ConstantInt::getZExtValue(), llvm::GlobalVariable::isConstant(), llvm::LibFunc::memset, and llvm::AArch64CC::MI.

static int AnalyzeLoadFromClobberingStore	(	Type *	LoadTy,
		Value *	LoadPtr,
		StoreInst *	DepSI,
		const DataLayout &	DL
	)		[static]

AnalyzeLoadFromClobberingStore - This function is called when we have a memdep query of a load that ends up being a clobbering store.

Definition at line 1021 of file GVN.cpp.

References AnalyzeLoadFromClobberingWrite(), llvm::StoreInst::getPointerOperand(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), llvm::StoreInst::getValueOperand(), llvm::Type::isArrayTy(), and llvm::Type::isStructTy().

static int AnalyzeLoadFromClobberingWrite	(	Type *	LoadTy,
		Value *	LoadPtr,
		Value *	WritePtr,
		uint64_t	WriteSizeInBits,
		const DataLayout &	DL
	)		[static]

AnalyzeLoadFromClobberingWrite - This function is called when we have a memdep query of a load that ends up being a clobbering memory write (store, memset, memcpy, memmove). This means that the write *may* provide bits used by the load but we can't be sure because the pointers don't mustalias.

Check this case to see if there is anything more we can do before we give up. This returns -1 if we have to give up, or a byte number in the stored value of the piece that feeds the load.

Definition at line 947 of file GVN.cpp.

References llvm::dbgs(), llvm::GetPointerBaseWithConstantOffset(), llvm::DataLayout::getTypeSizeInBits(), llvm::Type::isArrayTy(), and llvm::Type::isStructTy().

Referenced by AnalyzeLoadFromClobberingLoad(), AnalyzeLoadFromClobberingMemInst(), and AnalyzeLoadFromClobberingStore().

static bool CanCoerceMustAliasedValueToLoad	(	Value *	StoredVal,
		Type *	LoadTy,
		const DataLayout &	DL
	)		[static]

CanCoerceMustAliasedValueToLoad - Return true if CoerceAvailableValueToLoadType will succeed.

Definition at line 836 of file GVN.cpp.

References llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), llvm::Type::isArrayTy(), and llvm::Type::isStructTy().

Referenced by CoerceAvailableValueToLoadType().

static Value* CoerceAvailableValueToLoadType	(	Value *	StoredVal,
		Type *	LoadedTy,
		Instruction *	InsertPt,
		const DataLayout &	DL
	)		[static]

CoerceAvailableValueToLoadType - If we saw a store of a value to memory, and then a load from a must-aliased pointer of a different type, try to coerce the stored value. LoadedTy is the type of the load we want to replace and InsertPt is the place to insert new instructions.

If we can't do it, return null.

Definition at line 860 of file GVN.cpp.

References CanCoerceMustAliasedValueToLoad(), llvm::IntegerType::get(), llvm::ConstantInt::get(), llvm::Type::getContext(), llvm::DataLayout::getIntPtrType(), llvm::Type::getScalarType(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), llvm::DataLayout::isBigEndian(), llvm::Type::isIntegerTy(), and llvm::Type::isPointerTy().

Referenced by GetMemInstValueForLoad(), and GetStoreValueForLoad().

static Value* ConstructSSAForLoadSet	(	LoadInst *	LI,
		SmallVectorImpl< AvailableValueInBlock > &	ValuesPerBlock,
		GVN &	gvn
	)		[static]

ConstructSSAForLoadSet - Given a set of loads specified by ValuesPerBlock, construct SSA form, allowing us to eliminate LI. This returns the value that should be used at LI's definition site.

Definition at line 1273 of file GVN.cpp.

References llvm::SSAUpdater::AddAvailableValue(), llvm::AliasAnalysis::addEscapingUse(), llvm::AliasAnalysis::copyValue(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::PHINode::getOperandNumForIncomingValue(), llvm::User::getOperandUse(), llvm::Instruction::getParent(), llvm::Type::getScalarType(), llvm::Value::getType(), llvm::SSAUpdater::GetValueInMiddleOfBlock(), llvm::SSAUpdater::HasValueForBlock(), llvm::SSAUpdater::Initialize(), llvm::Type::isPointerTy(), P, and llvm::SmallVectorTemplateCommon< T >::size().

static Value* GetLoadValueForLoad	(	LoadInst *	SrcVal,
		unsigned	Offset,
		Type *	LoadTy,
		Instruction *	InsertPt,
		GVN &	gvn
	)		[static]

GetLoadValueForLoad - This function is called when we have a memdep query of a load that ends up being a clobbering load. This means that the load *may* provide bits used by the load but we can't be sure because the pointers don't mustalias. Check this case to see if there is anything more we can do before we give up.

Definition at line 1155 of file GVN.cpp.

References llvm::dbgs(), DEBUG, llvm::IntegerType::get(), llvm::PointerType::get(), llvm::LoadInst::getAlignment(), llvm::Type::getContext(), llvm::Instruction::getDebugLoc(), llvm::Instruction::getParent(), llvm::Type::getPointerAddressSpace(), llvm::LoadInst::getPointerOperand(), llvm::Type::getPrimitiveSizeInBits(), GetStoreValueForLoad(), llvm::Value::getType(), llvm::DataLayout::getTypeStoreSize(), llvm::DataLayout::isBigEndian(), llvm::Type::isIntegerTy(), llvm::isPowerOf2_32(), llvm::LoadInst::isSimple(), llvm::NextPowerOf2(), llvm::Value::replaceAllUsesWith(), llvm::LoadInst::setAlignment(), and llvm::Value::takeName().

static Value* GetMemInstValueForLoad	(	MemIntrinsic *	SrcInst,
		unsigned	Offset,
		Type *	LoadTy,
		Instruction *	InsertPt,
		const DataLayout &	DL
	)		[static]

GetMemInstValueForLoad - This function is called when we have a memdep query of a load that ends up being a clobbering mem intrinsic.

Definition at line 1215 of file GVN.cpp.

References CoerceAvailableValueToLoadType(), llvm::ConstantFoldLoadFromConstPtr(), llvm::IntegerType::get(), llvm::ConstantInt::get(), llvm::PointerType::get(), llvm::ConstantExpr::getBitCast(), llvm::Type::getContext(), llvm::ConstantExpr::getGetElementPtr(), llvm::Type::getInt64Ty(), llvm::Type::getInt8PtrTy(), llvm::Instruction::getParent(), llvm::Type::getPointerAddressSpace(), llvm::MemTransferInst::getSource(), llvm::Value::getType(), and llvm::DataLayout::getTypeSizeInBits().

static Value* GetStoreValueForLoad	(	Value *	SrcVal,
		unsigned	Offset,
		Type *	LoadTy,
		Instruction *	InsertPt,
		const DataLayout &	DL
	)		[static]

GetStoreValueForLoad - This function is called when we have a memdep query of a load that ends up being a clobbering store. This means that the store provides bits used by the load but we the pointers don't mustalias. Check this case to see if there is anything more we can do before we give up.

Definition at line 1116 of file GVN.cpp.

References CoerceAvailableValueToLoadType(), llvm::IntegerType::get(), llvm::Type::getContext(), llvm::DataLayout::getIntPtrType(), llvm::Instruction::getParent(), llvm::Type::getScalarType(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), llvm::Type::isIntegerTy(), llvm::DataLayout::isLittleEndian(), and llvm::Type::isPointerTy().

Referenced by GetLoadValueForLoad().

static bool isLifetimeStart

(

const Instruction *

Inst

)

[static]

Definition at line 1369 of file GVN.cpp.

static bool isOnlyReachableViaThisEdge	(	const BasicBlockEdge &	E,
		DominatorTree *	DT
	)		[static]

isOnlyReachableViaThisEdge - There is an edge from 'Src' to 'Dst'. Return true if every path from the entry block to 'Dst' passes via this edge. In particular 'Dst' must not be reachable via another edge from 'Src'.

Definition at line 2058 of file GVN.cpp.

References llvm::BasicBlockEdge::getEnd(), llvm::BasicBlock::getSinglePredecessor(), and llvm::BasicBlockEdge::getStart().

static bool IsValueFullyAvailableInBlock	(	BasicBlock *	BB,
		DenseMap< BasicBlock *, char > &	FullyAvailableBlocks,
		uint32_t	RecurseDepth
	)		[static]

IsValueFullyAvailableInBlock - Return true if we can prove that the value we're analyzing is fully available in the specified block. As we go, keep track of which blocks we know are fully alive in FullyAvailableBlocks. This map is actually a tri-state map with the following values: 0) we know the block *is not* fully available. 1) we know the block *is* fully available. 2) we do not know whether the block is fully available or not, but we are currently speculating that it will be. 3) we are speculating for this block and have used that to speculate for other blocks.

Definition at line 763 of file GVN.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorBase::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::insert(), MaxRecurseDepth, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::succ_begin(), and llvm::succ_end().

static void patchAndReplaceAllUsesWith	(	Instruction *	I,
		Value *	Repl
	)		[static]

Definition at line 1805 of file GVN.cpp.

References patchReplacementInstruction(), and llvm::Value::replaceAllUsesWith().

static void patchReplacementInstruction	(	Instruction *	I,
		Value *	Repl
	)		[static]

Definition at line 1771 of file GVN.cpp.

References llvm::combineMetadata(), llvm::dyn_cast(), llvm::BinaryOperator::hasNoSignedWrap(), llvm::BinaryOperator::hasNoUnsignedWrap(), I, llvm::LLVMContext::MD_alias_scope, llvm::LLVMContext::MD_fpmath, llvm::LLVMContext::MD_invariant_load, llvm::LLVMContext::MD_noalias, llvm::LLVMContext::MD_range, llvm::LLVMContext::MD_tbaa, and llvm::BinaryOperator::setHasNoSignedWrap().

Referenced by patchAndReplaceAllUsesWith().

STATISTIC	(	NumGVNInstr	,
		"Number of instructions deleted"
	)

STATISTIC	(	NumGVNLoad	,
		"Number of loads deleted"
	)

STATISTIC	(	NumGVNPRE	,
		"Number of instructions PRE'd"
	)

STATISTIC	(	NumGVNBlocks	,
		"Number of blocks merged"
	)

STATISTIC	(	NumGVNSimpl	,
		"Number of instructions simplified"
	)

STATISTIC	(	NumGVNEqProp	,
		"Number of equalities propagated"
	)

STATISTIC	(	NumPRELoad	,
		"Number of loads PRE'd"
	)

---

Variable Documentation

cl::opt<bool> EnableLoadPRE("enable-load-pre", cl::init(true)) [static]

cl::opt<bool> EnablePRE("enable-pre", cl::init(true), cl::Hidden) [static]

cl::opt<uint32_t> MaxRecurseDepth("max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore, cl::desc("Max recurse depth (default = 1000)")) [static]

Referenced by IsValueFullyAvailableInBlock().