#include "llvm/Transforms/Scalar/DeadStoreElimination.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.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/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <map>
#include <utility>

Include dependency graph for DeadStoreElimination.cpp:

Macros
#define	DEBUG_TYPE "dse"

Typedefs
using	OverlapIntervalsTy = std::map< int64_t, int64_t >

using	InstOverlapIntervalsTy = DenseMap< Instruction *, OverlapIntervalsTy >

Enumerations
enum	OverwriteResult

Functions
	STATISTIC (NumRedundantStores, "Number of redundant stores deleted")

	STATISTIC (NumFastStores, "Number of stores deleted")

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

	STATISTIC (NumCompletePartials, "Number of stores dead by later partials")

	STATISTIC (NumModifiedStores, "Number of stores modified")

static void	deleteDeadInstruction (Instruction I, BasicBlock::iterator BBI, MemoryDependenceResults &MD, const TargetLibraryInfo &TLI, InstOverlapIntervalsTy &IOL, DenseMap< Instruction , size_t > InstrOrdering, SmallSetVector< Value , 16 > ValueSet=nullptr)
	Delete this instruction. More...

static bool	hasAnalyzableMemoryWrite (Instruction *I, const TargetLibraryInfo &TLI)
	Does this instruction write some memory? This only returns true for things that we can analyze with other helpers below. More...

static MemoryLocation	getLocForWrite (Instruction *Inst)
	Return a Location stored to by the specified instruction. More...

static MemoryLocation	getLocForRead (Instruction *Inst, const TargetLibraryInfo &TLI)
	Return the location read by the specified "hasAnalyzableMemoryWrite" instruction if any. More...

static bool	isRemovable (Instruction *I)
	If the value of this instruction and the memory it writes to is unused, may we delete this instruction? More...

static bool	isShortenableAtTheEnd (Instruction *I)
	Returns true if the end of this instruction can be safely shortened in length. More...

static bool	isShortenableAtTheBeginning (Instruction *I)
	Returns true if the beginning of this instruction can be safely shortened in length. More...

static Value *	getStoredPointerOperand (Instruction *I)
	Return the pointer that is being written to. More...

static uint64_t	getPointerSize (const Value V, const DataLayout &DL, const TargetLibraryInfo &TLI, const Function F)

static OverwriteResult	isOverwrite (const MemoryLocation &Later, const MemoryLocation &Earlier, const DataLayout &DL, const TargetLibraryInfo &TLI, int64_t &EarlierOff, int64_t &LaterOff, Instruction DepWrite, InstOverlapIntervalsTy &IOL, AliasAnalysis &AA, const Function F)
	Return 'OW_Complete' if a store to the 'Later' location completely overwrites a store to the 'Earlier' location, 'OW_End' if the end of the 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the beginning of the 'Earlier' location is overwritten by 'Later'. More...

static bool	isPossibleSelfRead (Instruction Inst, const MemoryLocation &InstStoreLoc, Instruction DepWrite, const TargetLibraryInfo &TLI, AliasAnalysis &AA)
	If 'Inst' might be a self read (i.e. More...

static bool	memoryIsNotModifiedBetween (Instruction FirstI, Instruction SecondI, AliasAnalysis *AA)
	Returns true if the memory which is accessed by the second instruction is not modified between the first and the second instruction. More...

static void	findUnconditionalPreds (SmallVectorImpl< BasicBlock > &Blocks, BasicBlock BB, DominatorTree *DT)
	Find all blocks that will unconditionally lead to the block BB and append them to F. More...

static bool	handleFree (CallInst F, AliasAnalysis AA, MemoryDependenceResults MD, DominatorTree DT, const TargetLibraryInfo TLI, InstOverlapIntervalsTy &IOL, DenseMap< Instruction , size_t > *InstrOrdering)
	Handle frees of entire structures whose dependency is a store to a field of that structure. More...

static void	removeAccessedObjects (const MemoryLocation &LoadedLoc, SmallSetVector< Value , 16 > &DeadStackObjects, const DataLayout &DL, AliasAnalysis AA, const TargetLibraryInfo TLI, const Function F)
	Check to see if the specified location may alias any of the stack objects in the DeadStackObjects set. More...

static bool	handleEndBlock (BasicBlock &BB, AliasAnalysis AA, MemoryDependenceResults MD, const TargetLibraryInfo TLI, InstOverlapIntervalsTy &IOL, DenseMap< Instruction , size_t > *InstrOrdering)
	Remove dead stores to stack-allocated locations in the function end block. More...

static bool	tryToShorten (Instruction *EarlierWrite, int64_t &EarlierOffset, int64_t &EarlierSize, int64_t LaterOffset, int64_t LaterSize, bool IsOverwriteEnd)

static bool	tryToShortenEnd (Instruction *EarlierWrite, OverlapIntervalsTy &IntervalMap, int64_t &EarlierStart, int64_t &EarlierSize)

static bool	tryToShortenBegin (Instruction *EarlierWrite, OverlapIntervalsTy &IntervalMap, int64_t &EarlierStart, int64_t &EarlierSize)

static bool	removePartiallyOverlappedStores (AliasAnalysis *AA, const DataLayout &DL, InstOverlapIntervalsTy &IOL)

static bool	eliminateNoopStore (Instruction Inst, BasicBlock::iterator &BBI, AliasAnalysis AA, MemoryDependenceResults MD, const DataLayout &DL, const TargetLibraryInfo TLI, InstOverlapIntervalsTy &IOL, DenseMap< Instruction , size_t > InstrOrdering)

static bool	eliminateDeadStores (BasicBlock &BB, AliasAnalysis AA, MemoryDependenceResults MD, DominatorTree DT, const TargetLibraryInfo TLI)

static bool	eliminateDeadStores (Function &F, AliasAnalysis AA, MemoryDependenceResults MD, DominatorTree DT, const TargetLibraryInfo TLI)

	INITIALIZE_PASS_BEGIN (DSELegacyPass, "dse", "Dead Store Elimination", false, false) INITIALIZE_PASS_END(DSELegacyPass

Variables
static cl::opt< bool >	EnablePartialOverwriteTracking ("enable-dse-partial-overwrite-tracking", cl::init(true), cl::Hidden, cl::desc("Enable partial-overwrite tracking in DSE"))

static cl::opt< bool >	EnablePartialStoreMerging ("enable-dse-partial-store-merging", cl::init(true), cl::Hidden, cl::desc("Enable partial store merging in DSE"))

	dse

Dead Store	Elimination

Dead Store	false

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "dse"

Definition at line 70 of file DeadStoreElimination.cpp.

Typedef Documentation

◆ InstOverlapIntervalsTy

using InstOverlapIntervalsTy = DenseMap<Instruction *, OverlapIntervalsTy>

Definition at line 92 of file DeadStoreElimination.cpp.

◆ OverlapIntervalsTy

using OverlapIntervalsTy = std::map<int64_t, int64_t>

Definition at line 91 of file DeadStoreElimination.cpp.

Enumeration Type Documentation

◆ OverwriteResult

enum OverwriteResult

Definition at line 326 of file DeadStoreElimination.cpp.

Function Documentation

◆ deleteDeadInstruction()

static void deleteDeadInstruction	(	Instruction *	I,
		BasicBlock::iterator *	BBI,
		MemoryDependenceResults &	MD,
		const TargetLibraryInfo &	TLI,
		InstOverlapIntervalsTy &	IOL,
		DenseMap< Instruction , size_t >	InstrOrdering,
		SmallSetVector< Value , 16 >	ValueSet = `nullptr`
	)

static

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 99 of file DeadStoreElimination.cpp.

References llvm::SmallVectorBase::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::Instruction::eraseFromParent(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::isInstructionTriviallyDead(), op, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::MemoryDependenceResults::removeInstruction(), llvm::salvageDebugInfo(), llvm::User::setOperand(), and llvm::Value::use_empty().

Referenced by eliminateDeadStores(), eliminateNoopStore(), handleEndBlock(), and handleFree().

◆ eliminateDeadStores() [1/2]

static bool eliminateDeadStores	(	BasicBlock &	BB,
		AliasAnalysis *	AA,
		MemoryDependenceResults *	MD,
		DominatorTree *	DT,
		const TargetLibraryInfo *	TLI
	)

static

Definition at line 1070 of file DeadStoreElimination.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::dbgs(), deleteDeadInstruction(), llvm::dyn_cast(), eliminateNoopStore(), EnablePartialOverwriteTracking, EnablePartialStoreMerging, llvm::BasicBlock::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::erase(), F(), llvm::BasicBlock::front(), llvm::ConstantInt::get(), llvm::APInt::getBitsSet(), llvm::APInt::getBitWidth(), llvm::Module::getDataLayout(), llvm::MemoryDependenceResults::getDefaultBlockScanLimit(), llvm::MemoryDependenceResults::getDependency(), llvm::MemDepResult::getInst(), llvm::ilist_node_impl< OptionsT >::getIterator(), getLocForWrite(), llvm::AAResults::getModRefInfo(), llvm::BasicBlock::getModule(), llvm::Instruction::getNumSuccessors(), llvm::BasicBlock::getParent(), llvm::MemoryDependenceResults::getPointerDependencyFrom(), llvm::BasicBlock::getTerminator(), llvm::GetUnderlyingObject(), llvm::LocationSize::getValue(), handleEndBlock(), handleFree(), hasAnalyzableMemoryWrite(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::isAllocLikeFn(), llvm::DataLayout::isBigEndian(), llvm::MemDepResult::isClobber(), llvm::MemDepResult::isDef(), llvm::isFreeCall(), isOverwrite(), isPossibleSelfRead(), llvm::isRefSet(), isRemovable(), isShortenableAtTheBeginning(), isShortenableAtTheEnd(), LLVM_DEBUG, llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::BitmaskEnumDetail::Mask(), llvm::Instruction::mayThrow(), llvm::LLVMContext::MD_alias_scope, llvm::LLVMContext::MD_dbg, llvm::LLVMContext::MD_noalias, llvm::LLVMContext::MD_nontemporal, llvm::LLVMContext::MD_tbaa, memoryIsNotModifiedBetween(), OR, llvm::PointerMayBeCaptured(), llvm::MemoryLocation::Ptr, removePartiallyOverlappedStores(), SI, llvm::MemoryLocation::Size, tryToShorten(), llvm::BitmaskEnumDetail::Underlying(), and llvm::APInt::zext().

Referenced by eliminateDeadStores(), and llvm::DSEPass::run().

◆ eliminateDeadStores() [2/2]

static bool eliminateDeadStores	(	Function &	F,
		AliasAnalysis *	AA,
		MemoryDependenceResults *	MD,
		DominatorTree *	DT,
		const TargetLibraryInfo *	TLI
	)

static

Definition at line 1314 of file DeadStoreElimination.cpp.

References eliminateDeadStores(), and llvm::DominatorTree::isReachableFromEntry().

◆ eliminateNoopStore()

static bool eliminateNoopStore	(	Instruction *	Inst,
		BasicBlock::iterator &	BBI,
		AliasAnalysis *	AA,
		MemoryDependenceResults *	MD,
		const DataLayout &	DL,
		const TargetLibraryInfo *	TLI,
		InstOverlapIntervalsTy &	IOL,
		DenseMap< Instruction , size_t >	InstrOrdering
	)

static

Definition at line 1023 of file DeadStoreElimination.cpp.

References llvm::dbgs(), deleteDeadInstruction(), llvm::dyn_cast(), llvm::StoreInst::getPointerOperand(), llvm::GetUnderlyingObject(), llvm::StoreInst::getValueOperand(), llvm::isCallocLikeFn(), llvm::Constant::isNullValue(), isRemovable(), LLVM_DEBUG, memoryIsNotModifiedBetween(), and SI.

Referenced by eliminateDeadStores().

◆ findUnconditionalPreds()

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 E, llvm::Instruction::getNumSuccessors(), llvm::BasicBlock::getTerminator(), I, llvm::DominatorTree::isReachableFromEntry(), llvm::pred_begin(), llvm::pred_end(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by handleFree().

◆ getLocForRead()

static MemoryLocation getLocForRead	(	Instruction *	Inst,
		const TargetLibraryInfo &	TLI
	)

static

Return the location read by the specified "hasAnalyzableMemoryWrite" instruction if any.

Definition at line 222 of file DeadStoreElimination.cpp.

References assert(), llvm::MemoryLocation::getForSource(), and hasAnalyzableMemoryWrite().

Referenced by isPossibleSelfRead().

◆ getLocForWrite()

static MemoryLocation getLocForWrite ( Instruction * Inst )

static

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 190 of file DeadStoreElimination.cpp.

References llvm::MemoryLocation::get(), llvm::MemoryLocation::getForDest(), llvm::Intrinsic::init_trampoline, llvm::Intrinsic::lifetime_end, MI, and SI.

Referenced by eliminateDeadStores(), getStoredPointerOperand(), and removePartiallyOverlappedStores().

◆ getPointerSize()

static uint64_t getPointerSize	(	const Value *	V,
		const DataLayout &	DL,
		const TargetLibraryInfo &	TLI,
		const Function *	F
	)

static

Definition at line 312 of file DeadStoreElimination.cpp.

References llvm::getObjectSize(), llvm::ObjectSizeOpts::NullIsUnknownSize, llvm::NullPointerIsDefined(), Size, and llvm::MemoryLocation::UnknownSize.

Referenced by llvm::DataLayout::fitsInLegalInteger(), llvm::pdb::PDBFile::getAllocator(), getFixupKindNumBytes(), llvm::DataLayout::getPointerSizeInBits(), handleEndBlock(), isOverwrite(), and removeAccessedObjects().

◆ getStoredPointerOperand()

static Value* getStoredPointerOperand ( Instruction * I )

static

Return the pointer that is being written to.

Definition at line 303 of file DeadStoreElimination.cpp.

References assert(), getLocForWrite(), and llvm::MemoryLocation::Ptr.

Referenced by handleEndBlock(), and handleFree().

◆ handleEndBlock()

static bool handleEndBlock	(	BasicBlock &	BB,
		AliasAnalysis *	AA,
		MemoryDependenceResults *	MD,
		const TargetLibraryInfo *	TLI,
		InstOverlapIntervalsTy &	IOL,
		DenseMap< Instruction , size_t >	InstrOrdering
	)

static

Remove dead stores to stack-allocated locations in the function end block.

Ex: A = alloca i32 ... store i32 1, i32* A ret void

Definition at line 749 of file DeadStoreElimination.cpp.

References llvm::Function::args(), llvm::BasicBlock::begin(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::count(), llvm::dbgs(), llvm::RegState::Dead, deleteDeadInstruction(), llvm::AAResults::doesNotAccessMemory(), E, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty(), llvm::BasicBlock::end(), llvm::Function::front(), llvm::MemoryLocation::get(), llvm::Module::getDataLayout(), llvm::AAResults::getModRefInfo(), llvm::BasicBlock::getModule(), llvm::BasicBlock::getParent(), getPointerSize(), getStoredPointerOperand(), llvm::GetUnderlyingObjects(), hasAnalyzableMemoryWrite(), I, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert(), llvm::isAllocLikeFn(), llvm::isInstructionTriviallyDead(), llvm::isRefSet(), isRemovable(), LLVM_DEBUG, llvm::PointerMayBeCaptured(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::remove(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::remove_if(), and removeAccessedObjects().

Referenced by eliminateDeadStores().

◆ handleFree()

static bool handleFree	(	CallInst *	F,
		AliasAnalysis *	AA,
		MemoryDependenceResults *	MD,
		DominatorTree *	DT,
		const TargetLibraryInfo *	TLI,
		InstOverlapIntervalsTy &	IOL,
		DenseMap< Instruction , size_t >	InstrOrdering
	)

static

Handle frees of entire structures whose dependency is a store to a field of that structure.

Definition at line 657 of file DeadStoreElimination.cpp.

References llvm::dbgs(), deleteDeadInstruction(), findUnconditionalPreds(), llvm::CallBase::getArgOperand(), llvm::Module::getDataLayout(), llvm::MemDepResult::getInst(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getModule(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::MemoryDependenceResults::getPointerDependencyFrom(), getStoredPointerOperand(), llvm::BasicBlock::getTerminator(), llvm::GetUnderlyingObject(), hasAnalyzableMemoryWrite(), llvm::MemDepResult::isClobber(), llvm::MemDepResult::isDef(), llvm::AAResults::isMustAlias(), llvm::MemDepResult::isNonLocal(), isRemovable(), LLVM_DEBUG, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by eliminateDeadStores().

◆ hasAnalyzableMemoryWrite()

static bool hasAnalyzableMemoryWrite	(	Instruction *	I,
		const TargetLibraryInfo &	TLI
	)

static

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

Definition at line 152 of file DeadStoreElimination.cpp.

References F(), llvm::TargetLibraryInfo::getName(), llvm::TargetLibraryInfo::has(), llvm::Intrinsic::init_trampoline, llvm::Intrinsic::lifetime_end, llvm::Intrinsic::memcpy, llvm::Intrinsic::memcpy_element_unordered_atomic, llvm::Intrinsic::memmove, llvm::Intrinsic::memmove_element_unordered_atomic, llvm::Intrinsic::memset, and llvm::Intrinsic::memset_element_unordered_atomic.

Referenced by eliminateDeadStores(), getLocForRead(), handleEndBlock(), and handleFree().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	DSELegacyPass	,
		"dse"	,
		"Dead Store Elimination"	,
		false	,
		false
	)

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

◆ isOverwrite()

static OverwriteResult isOverwrite	(	const MemoryLocation &	Later,
		const MemoryLocation &	Earlier,
		const DataLayout &	DL,
		const TargetLibraryInfo &	TLI,
		int64_t &	EarlierOff,
		int64_t &	LaterOff,
		Instruction *	DepWrite,
		InstOverlapIntervalsTy &	IOL,
		AliasAnalysis &	AA,
		const Function *	F
	)

static

Return 'OW_Complete' if a store to the 'Later' location completely overwrites a store to the 'Earlier' location, 'OW_End' if the end of the 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the beginning of the 'Earlier' location is overwritten by 'Later'.

'OW_PartialEarlierWithFullLater' means that an earlier (big) store was overwritten by a latter (smaller) store which doesn't write outside the big store's memory locations. Returns 'OW_Unknown' if nothing can be determined.

Definition at line 343 of file DeadStoreElimination.cpp.

References assert(), llvm::dbgs(), EnablePartialOverwriteTracking, EnablePartialStoreMerging, llvm::GetPointerBaseWithConstantOffset(), getPointerSize(), llvm::GetUnderlyingObject(), llvm::LocationSize::getValue(), llvm::AAResults::isMustAlias(), llvm::LocationSize::isPrecise(), LLVM_DEBUG, llvm::max(), llvm::MemoryLocation::Ptr, llvm::MemoryLocation::Size, llvm::Value::stripPointerCasts(), and llvm::MemoryLocation::UnknownSize.

Referenced by eliminateDeadStores().

◆ isPossibleSelfRead()

static bool isPossibleSelfRead	(	Instruction *	Inst,
		const MemoryLocation &	InstStoreLoc,
		Instruction *	DepWrite,
		const TargetLibraryInfo &	TLI,
		AliasAnalysis &	AA
	)

static

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:

memmove(A <- B) memmove(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 540 of file DeadStoreElimination.cpp.

References getLocForRead(), llvm::AAResults::isMustAlias(), llvm::AAResults::isNoAlias(), and llvm::MemoryLocation::Ptr.

Referenced by eliminateDeadStores().

◆ isRemovable()

static bool isRemovable ( Instruction * I )

static

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

Definition at line 235 of file DeadStoreElimination.cpp.

References llvm::Intrinsic::init_trampoline, isVolatile(), llvm::Intrinsic::lifetime_end, llvm_unreachable, llvm::Intrinsic::memcpy, llvm::Intrinsic::memcpy_element_unordered_atomic, llvm::Intrinsic::memmove, llvm::Intrinsic::memmove_element_unordered_atomic, llvm::Intrinsic::memset, llvm::Intrinsic::memset_element_unordered_atomic, and SI.

Referenced by eliminateDeadStores(), eliminateNoopStore(), handleEndBlock(), handleFree(), and removePartiallyOverlappedStores().

◆ isShortenableAtTheBeginning()

static bool isShortenableAtTheBeginning ( Instruction * I )

static

Returns true if the beginning of this instruction can be safely shortened in length.

Definition at line 296 of file DeadStoreElimination.cpp.

References I.

Referenced by eliminateDeadStores(), and tryToShortenBegin().

◆ isShortenableAtTheEnd()

static bool isShortenableAtTheEnd ( Instruction * I )

static

Returns true if the end of this instruction can be safely shortened in length.

Definition at line 271 of file DeadStoreElimination.cpp.

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

Referenced by eliminateDeadStores(), and tryToShortenEnd().

◆ memoryIsNotModifiedBetween()

static bool memoryIsNotModifiedBetween	(	Instruction *	FirstI,
		Instruction *	SecondI,
		AliasAnalysis *	AA
	)

static

Returns true if the memory which is accessed by the second instruction is not modified between the first and the second instruction.

Precondition: Second instruction must be dominated by the first instruction.

Definition at line 586 of file DeadStoreElimination.cpp.

References assert(), B, llvm::BasicBlock::begin(), llvm::SmallVectorBase::empty(), llvm::BasicBlock::end(), llvm::MemoryLocation::get(), llvm::Function::getEntryBlock(), llvm::AAResults::getModRefInfo(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isModSet(), llvm::Instruction::mayWriteToMemory(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::pred_begin(), llvm::pred_end(), and llvm::SmallVectorTemplateBase< T >::push_back().

Referenced by eliminateDeadStores(), and eliminateNoopStore().

◆ removeAccessedObjects()

static void removeAccessedObjects	(	const MemoryLocation &	LoadedLoc,
		SmallSetVector< Value *, 16 > &	DeadStackObjects,
		const DataLayout &	DL,
		AliasAnalysis *	AA,
		const TargetLibraryInfo *	TLI,
		const Function *	F
	)

static

Check to see if the specified location may alias any of the stack objects in the DeadStackObjects set.

If so, they become live because the location is being loaded.

Definition at line 717 of file DeadStoreElimination.cpp.

References getPointerSize(), llvm::GetUnderlyingObject(), I, llvm::AAResults::isNoAlias(), llvm::MemoryLocation::Ptr, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::remove(), and llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::remove_if().

Referenced by handleEndBlock().

◆ removePartiallyOverlappedStores()

static bool removePartiallyOverlappedStores	(	AliasAnalysis *	AA,
		const DataLayout &	DL,
		InstOverlapIntervalsTy &	IOL
	)

static

Definition at line 999 of file DeadStoreElimination.cpp.

References assert(), getLocForWrite(), llvm::GetPointerBaseWithConstantOffset(), llvm::LocationSize::getValue(), isRemovable(), llvm::MemoryLocation::Ptr, llvm::MemoryLocation::Size, llvm::Value::stripPointerCasts(), tryToShortenBegin(), and tryToShortenEnd().

Referenced by eliminateDeadStores().

◆ STATISTIC() [1/5]

STATISTIC	(	NumRedundantStores	,
		"Number of redundant stores deleted"
	)

◆ STATISTIC() [2/5]

STATISTIC	(	NumFastStores	,
		"Number of stores deleted"
	)

◆ STATISTIC() [3/5]

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

◆ STATISTIC() [4/5]

STATISTIC	(	NumCompletePartials	,
		"Number of stores dead by later partials"
	)

◆ STATISTIC() [5/5]

STATISTIC	(	NumModifiedStores	,
		"Number of stores modified"
	)

◆ tryToShorten()

static bool tryToShorten	(	Instruction *	EarlierWrite,
		int64_t &	EarlierOffset,
		int64_t &	EarlierSize,
		int64_t	LaterOffset,
		int64_t	LaterSize,
		bool	IsOverwriteEnd
	)

static

Definition at line 903 of file DeadStoreElimination.cpp.

References llvm::GetElementPtrInst::CreateInBounds(), llvm::dbgs(), llvm::ConstantInt::get(), llvm::Value::getType(), llvm::isPowerOf2_64(), and LLVM_DEBUG.

Referenced by eliminateDeadStores(), tryToShortenBegin(), and tryToShortenEnd().

◆ tryToShortenBegin()

static bool tryToShortenBegin	(	Instruction *	EarlierWrite,
		OverlapIntervalsTy &	IntervalMap,
		int64_t &	EarlierStart,
		int64_t &	EarlierSize
	)

static

Definition at line 977 of file DeadStoreElimination.cpp.

References assert(), isShortenableAtTheBeginning(), and tryToShorten().

Referenced by removePartiallyOverlappedStores().

◆ tryToShortenEnd()

static bool tryToShortenEnd	(	Instruction *	EarlierWrite,
		OverlapIntervalsTy &	IntervalMap,
		int64_t &	EarlierStart,
		int64_t &	EarlierSize
	)

static

Definition at line 956 of file DeadStoreElimination.cpp.

References isShortenableAtTheEnd(), and tryToShorten().

Referenced by removePartiallyOverlappedStores().

Variable Documentation

◆ dse

dse

Definition at line 1394 of file DeadStoreElimination.cpp.

◆ Elimination

Dead Store Elimination

Definition at line 1394 of file DeadStoreElimination.cpp.

◆ EnablePartialOverwriteTracking

cl::opt<bool> EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking", cl::init(true), cl::Hidden, cl::desc("Enable partial-overwrite tracking in DSE"))

static

Referenced by eliminateDeadStores(), and isOverwrite().

◆ EnablePartialStoreMerging

cl::opt<bool> EnablePartialStoreMerging("enable-dse-partial-store-merging", cl::init(true), cl::Hidden, cl::desc("Enable partial store merging in DSE"))

static

Referenced by eliminateDeadStores(), and isOverwrite().

◆ false

Dead Store false

Definition at line 1394 of file DeadStoreElimination.cpp.

Macros

Typedefs

Enumerations

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Typedef Documentation

◆ InstOverlapIntervalsTy

◆ OverlapIntervalsTy

Enumeration Type Documentation

◆ OverwriteResult

Function Documentation

◆ deleteDeadInstruction()

◆ eliminateDeadStores() [1/2]

◆ eliminateDeadStores() [2/2]

◆ eliminateNoopStore()

◆ findUnconditionalPreds()

◆ getLocForRead()

◆ getLocForWrite()

◆ getPointerSize()

◆ getStoredPointerOperand()

◆ handleEndBlock()

◆ handleFree()

◆ hasAnalyzableMemoryWrite()

◆ INITIALIZE_PASS_BEGIN()

◆ isOverwrite()

◆ isPossibleSelfRead()

◆ isRemovable()

◆ isShortenableAtTheBeginning()

◆ isShortenableAtTheEnd()

◆ memoryIsNotModifiedBetween()

◆ removeAccessedObjects()

◆ removePartiallyOverlappedStores()

◆ STATISTIC() [1/5]

◆ STATISTIC() [2/5]

◆ STATISTIC() [3/5]

◆ STATISTIC() [4/5]

◆ STATISTIC() [5/5]

◆ tryToShorten()

◆ tryToShortenBegin()

◆ tryToShortenEnd()

Variable Documentation

◆ dse

◆ Elimination

◆ EnablePartialOverwriteTracking

◆ EnablePartialStoreMerging

◆ false