DeadStoreElimination.cpp File Reference

#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/Local.h"

Include dependency graph for DeadStoreElimination.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "dse"

Enumerations
enum	OverwriteResult

Functions
	STATISTIC (NumFastStores,"Number of stores deleted")
	STATISTIC (NumFastOther,"Number of other instrs removed")
static void	DeleteDeadInstruction (Instruction *I, MemoryDependenceAnalysis &MD, const TargetLibraryInfo *TLI, SmallSetVector< Value *, 16 > *ValueSet=0)
static bool	hasMemoryWrite (Instruction *I, const TargetLibraryInfo *TLI)
static AliasAnalysis::Location	getLocForWrite (Instruction *Inst, AliasAnalysis &AA)
static AliasAnalysis::Location	getLocForRead (Instruction *Inst, AliasAnalysis &AA)
static bool	isRemovable (Instruction *I)
static bool	isShortenable (Instruction *I)
static Value *	getStoredPointerOperand (Instruction *I)
	getStoredPointerOperand - Return the pointer that is being written to. More...
static uint64_t	getPointerSize (const Value *V, AliasAnalysis &AA)
static OverwriteResult	isOverwrite (const AliasAnalysis::Location &Later, const AliasAnalysis::Location &Earlier, AliasAnalysis &AA, int64_t &EarlierOff, int64_t &LaterOff)
static bool	isPossibleSelfRead (Instruction *Inst, const AliasAnalysis::Location &InstStoreLoc, Instruction *DepWrite, AliasAnalysis &AA)
static void	FindUnconditionalPreds (SmallVectorImpl< BasicBlock * > &Blocks, BasicBlock *BB, DominatorTree *DT)

Macro Definition Documentation

#define DEBUG_TYPE   "dse"

Definition at line 18 of file DeadStoreElimination.cpp.

Enumeration Type Documentation

enum OverwriteResult

Definition at line 327 of file DeadStoreElimination.cpp.

Function Documentation

static void DeleteDeadInstruction ( Instruction *  I, MemoryDependenceAnalysis &  MD, const TargetLibraryInfo *  TLI, SmallSetVector< Value *, 16 > *  ValueSet = 0  )

static

DeleteDeadInstruction - Delete this instruction. Before we do, go through and zero out all the operands of this instruction. If any of them become dead, delete them and the computation tree that feeds them.

If ValueSet is non-null, remove any deleted instructions from it as well.

Definition at line 110 of file DeadStoreElimination.cpp.

References llvm::SmallVectorBase::empty(), llvm::Instruction::eraseFromParent(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::isInstructionTriviallyDead(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::MemoryDependenceAnalysis::removeInstruction(), llvm::User::setOperand(), and llvm::Value::use_empty().

static void FindUnconditionalPreds ( SmallVectorImpl< BasicBlock * > &  Blocks, BasicBlock *  BB, DominatorTree *  DT  )

static

Find all blocks that will unconditionally lead to the block BB and append them to F.

Definition at line 641 of file DeadStoreElimination.cpp.

References llvm::TerminatorInst::getNumSuccessors(), llvm::BasicBlock::getTerminator(), I, llvm::DominatorTree::isReachableFromEntry(), llvm::pred_begin(), llvm::pred_end(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

static AliasAnalysis::Location getLocForRead ( Instruction *  Inst, AliasAnalysis &  AA  )

static

getLocForRead - Return the location read by the specified "hasMemoryWrite" instruction if any.

Definition at line 231 of file DeadStoreElimination.cpp.

References llvm::AliasAnalysis::getLocationForSource(), llvm::AliasAnalysis::getTargetLibraryInfo(), and hasMemoryWrite().

Referenced by isPossibleSelfRead().

static AliasAnalysis::Location getLocForWrite ( Instruction *  Inst, AliasAnalysis &  AA  )

static

getLocForWrite - Return a Location stored to by the specified instruction. If isRemovable returns true, this function and getLocForRead completely describe the memory operations for this instruction.

Definition at line 192 of file DeadStoreElimination.cpp.

References llvm::dyn_cast(), llvm::CallInst::getArgOperand(), llvm::AliasAnalysis::getDataLayout(), llvm::IntrinsicInst::getIntrinsicID(), llvm::AliasAnalysis::getLocation(), llvm::AliasAnalysis::getLocationForDest(), llvm::Intrinsic::init_trampoline, llvm::Intrinsic::lifetime_end, llvm::A64CC::MI, llvm::AliasAnalysis::Location::Size, and llvm::AliasAnalysis::UnknownSize.

static uint64_t getPointerSize ( const Value *  V, AliasAnalysis &  AA  )

static

Definition at line 319 of file DeadStoreElimination.cpp.

References llvm::AliasAnalysis::getDataLayout(), llvm::getObjectSize(), llvm::AliasAnalysis::getTargetLibraryInfo(), and llvm::AliasAnalysis::UnknownSize.

Referenced by isOverwrite().

static Value* getStoredPointerOperand ( Instruction *  I )

static

getStoredPointerOperand - Return the pointer that is being written to.

Definition at line 299 of file DeadStoreElimination.cpp.

References llvm::CallSiteBase< FunTy, ValTy, UserTy, InstrTy, CallTy, InvokeTy, IterTy >::getArgument(), I, llvm::Intrinsic::init_trampoline, llvm_unreachable, and llvm::A64CC::MI.

static bool hasMemoryWrite ( Instruction *  I, const TargetLibraryInfo *  TLI  )

static

hasMemoryWrite - Does this instruction write some memory? This only returns true for things that we can analyze with other helpers below.

Definition at line 150 of file DeadStoreElimination.cpp.

References llvm::Value::getName(), llvm::TargetLibraryInfo::getName(), llvm::TargetLibraryInfo::has(), llvm::Intrinsic::init_trampoline, llvm::Intrinsic::lifetime_end, llvm::Intrinsic::memcpy, llvm::Intrinsic::memmove, llvm::Intrinsic::memset, llvm::LibFunc::strcat, llvm::LibFunc::strcpy, llvm::LibFunc::strncat, and llvm::LibFunc::strncpy.

Referenced by getLocForRead().

static OverwriteResult isOverwrite ( const AliasAnalysis::Location &  Later, const AliasAnalysis::Location &  Earlier, AliasAnalysis &  AA, int64_t &  EarlierOff, int64_t &  LaterOff  )

static

isOverwrite - Return 'OverwriteComplete' if a store to the 'Later' location completely overwrites a store to the 'Earlier' location. 'OverwriteEnd' if the end of the 'Earlier' location is completely overwritten by 'Later', or 'OverwriteUnknown' if nothing can be determined

Definition at line 339 of file DeadStoreElimination.cpp.

References llvm::AliasAnalysis::getDataLayout(), llvm::GetPointerBaseWithConstantOffset(), getPointerSize(), llvm::Value::getType(), llvm::GetUnderlyingObject(), llvm::AliasAnalysis::Location::Ptr, llvm::AliasAnalysis::Location::Size, llvm::Value::stripPointerCasts(), TD, and llvm::AliasAnalysis::UnknownSize.

static bool isPossibleSelfRead ( Instruction *  Inst, const AliasAnalysis::Location &  InstStoreLoc, Instruction *  DepWrite, AliasAnalysis &  AA  )

static

isPossibleSelfRead - If 'Inst' might be a self read (i.e. a noop copy of a memory region into an identical pointer) then it doesn't actually make its input dead in the traditional sense. Consider this case:

memcpy(A <- B) memcpy(A <- A)

In this case, the second store to A does not make the first store to A dead. The usual situation isn't an explicit A<-A store like this (which can be trivially removed) but a case where two pointers may alias.

This function detects when it is unsafe to remove a dependent instruction because the DSE inducing instruction may be a self-read.

Definition at line 457 of file DeadStoreElimination.cpp.

References getLocForRead(), llvm::AliasAnalysis::isMustAlias(), llvm::AliasAnalysis::isNoAlias(), and llvm::AliasAnalysis::Location::Ptr.

static bool isRemovable ( Instruction *  I )

static

isRemovable - If the value of this instruction and the memory it writes to is unused, may we delete this instruction?

Definition at line 245 of file DeadStoreElimination.cpp.

References llvm::Intrinsic::init_trampoline, llvm::Intrinsic::lifetime_end, llvm_unreachable, llvm::Intrinsic::memcpy, llvm::Intrinsic::memmove, and llvm::Intrinsic::memset.

static bool isShortenable ( Instruction *  I )

static

isShortenable - Returns true if this instruction can be safely shortened in length.

Definition at line 278 of file DeadStoreElimination.cpp.

References llvm::Intrinsic::memcpy, and llvm::Intrinsic::memset.

STATISTIC	(	NumFastStores	,
		"Number of stores deleted"
	)

STATISTIC	(	NumFastOther	,
		"Number of other instrs removed"
	)