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/SmallPtrSet.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/Dominators.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/Assembly/Writer.h"
#include "llvm/IR/DataLayout.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/Support/Allocator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/PatternMatch.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.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
	llvm
	List of target independent CodeGen pass IDs.

Macros
#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 &TD)
static Value *	CoerceAvailableValueToLoadType (Value *StoredVal, Type *LoadedTy, Instruction *InsertPt, const DataLayout &TD)
static int	AnalyzeLoadFromClobberingWrite (Type *LoadTy, Value *LoadPtr, Value *WritePtr, uint64_t WriteSizeInBits, const DataLayout &TD)
static int	AnalyzeLoadFromClobberingStore (Type *LoadTy, Value *LoadPtr, StoreInst *DepSI, const DataLayout &TD)
static int	AnalyzeLoadFromClobberingLoad (Type *LoadTy, Value *LoadPtr, LoadInst *DepLI, const DataLayout &TD)
static int	AnalyzeLoadFromClobberingMemInst (Type *LoadTy, Value *LoadPtr, MemIntrinsic *MI, const DataLayout &TD)
static Value *	GetStoreValueForLoad (Value *SrcVal, unsigned Offset, Type *LoadTy, Instruction *InsertPt, const DataLayout &TD)
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 &TD)
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)"))

Macro Definition Documentation

#define DEBUG_TYPE   "gvn"

Definition at line 18 of file GVN.cpp.

Function Documentation

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

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 1033 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 &  TD  )

static

Definition at line 1060 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::Intrinsic::memset, llvm::A64CC::MI, and TD.

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

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 1016 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 &  TD  )

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 942 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 &  TD  )

static

CanCoerceMustAliasedValueToLoad - Return true if CoerceAvailableValueToLoadType will succeed.

Definition at line 831 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 &  TD  )

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 855 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 1268 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 1150 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(), llvm::Value::takeName(), and TD.

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

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 1210 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 &  TD  )

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 1111 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 1364 of file GVN.cpp.

References llvm::Intrinsic::lifetime_start.

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 2046 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 757 of file GVN.cpp.

References llvm::SmallVectorBase::empty(), I, 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 1802 of file GVN.cpp.

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

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

static

Definition at line 1760 of file GVN.cpp.

References llvm::dyn_cast(), llvm::Instruction::getMetadata(), llvm::MDNode::getMostGenericFPMath(), llvm::MDNode::getMostGenericRange(), llvm::MDNode::getMostGenericTBAA(), llvm::BinaryOperator::hasNoSignedWrap(), llvm::BinaryOperator::hasNoUnsignedWrap(), I, llvm_unreachable, llvm::LLVMContext::MD_dbg, llvm::LLVMContext::MD_fpmath, llvm::LLVMContext::MD_prof, llvm::LLVMContext::MD_range, llvm::LLVMContext::MD_tbaa, llvm::BinaryOperator::setHasNoSignedWrap(), and llvm::SmallVectorTemplateCommon< T >::size().

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().