DeadStoreElimination.cpp File Reference (original) (raw)

Go to the source code of this file.

Macros
#define	DEBUG_TYPE "dse"

Functions
	STATISTIC (NumRemainingStores, "Number of stores remaining after DSE")
	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")
	STATISTIC (NumCFGChecks, "Number of stores modified")
	STATISTIC (NumCFGTries, "Number of stores modified")
	STATISTIC (NumCFGSuccess, "Number of stores modified")
	STATISTIC (NumGetDomMemoryDefPassed, "Number of times a valid candidate is returned from getDomMemoryDef")
	STATISTIC (NumDomMemDefChecks, "Number iterations check for reads in getDomMemoryDef")
	DEBUG_COUNTER (MemorySSACounter, "dse-memoryssa", "Controls which MemoryDefs are eliminated.")
static bool	isShortenableAtTheEnd (Instruction *I)
	Returns true if the end of this instruction can be safely shortened in length.
static bool	isShortenableAtTheBeginning (Instruction *I)
	Returns true if the beginning of this instruction can be safely shortened in length.
static std::optional< TypeSize >	getPointerSize (const Value V, const DataLayout &DL, const TargetLibraryInfo &TLI, const Function F)
static OverwriteResult	isMaskedStoreOverwrite (const Instruction KillingI, const Instruction DeadI, BatchAAResults &AA)
	Check if two instruction are masked stores that completely overwrite one another.
static OverwriteResult	isPartialOverwrite (const MemoryLocation &KillingLoc, const MemoryLocation &DeadLoc, int64_t KillingOff, int64_t DeadOff, Instruction *DeadI, InstOverlapIntervalsTy &IOL)
	Return 'OW_Complete' if a store to the 'KillingLoc' location completely overwrites a store to the 'DeadLoc' location, 'OW_End' if the end of the 'DeadLoc' location is completely overwritten by 'KillingLoc', 'OW_Begin' if the beginning of the 'DeadLoc' location is overwritten by 'KillingLoc'.
static bool	memoryIsNotModifiedBetween (Instruction FirstI, Instruction SecondI, BatchAAResults &AA, const DataLayout &DL, DominatorTree *DT)
	Returns true if the memory which is accessed by the second instruction is not modified between the first and the second instruction.
static void	shortenAssignment (Instruction Inst, Value OriginalDest, uint64_t OldOffsetInBits, uint64_t OldSizeInBits, uint64_t NewSizeInBits, bool IsOverwriteEnd)
static void	adjustArgAttributes (AnyMemIntrinsic *Intrinsic, unsigned ArgNo, uint64_t PtrOffset)
	Update the attributes given that a memory access is updated (the dereferenced pointer could be moved forward when shortening a mem intrinsic).
static bool	tryToShorten (Instruction *DeadI, int64_t &DeadStart, uint64_t &DeadSize, int64_t KillingStart, uint64_t KillingSize, bool IsOverwriteEnd)
static bool	tryToShortenEnd (Instruction *DeadI, OverlapIntervalsTy &IntervalMap, int64_t &DeadStart, uint64_t &DeadSize)
static bool	tryToShortenBegin (Instruction *DeadI, OverlapIntervalsTy &IntervalMap, int64_t &DeadStart, uint64_t &DeadSize)
static Constant *	tryToMergePartialOverlappingStores (StoreInst KillingI, StoreInst DeadI, int64_t KillingOffset, int64_t DeadOffset, const DataLayout &DL, BatchAAResults &AA, DominatorTree *DT)
static bool	isNoopIntrinsic (Instruction *I)
static bool	canSkipDef (MemoryDef *D, bool DefVisibleToCaller)
static bool	hasInitializesAttr (Instruction *I)
static ConstantRangeList	getIntersectedInitRangeList (ArrayRef< ArgumentInitInfo > Args, bool CallHasNoUnwindAttr)
static bool	isFuncLocalAndNotCaptured (Value Arg, const CallBase CB, EarliestEscapeAnalysis &EA)
static bool	eliminateDeadStores (Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT, PostDominatorTree &PDT, const TargetLibraryInfo &TLI, const LoopInfo &LI)
	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"))
static cl::opt< unsigned >	MemorySSAScanLimit ("dse-memoryssa-scanlimit", cl::init(150), cl::Hidden, cl::desc("The number of memory instructions to scan for " "dead store elimination (default = 150)"))
static cl::opt< unsigned >	MemorySSAUpwardsStepLimit ("dse-memoryssa-walklimit", cl::init(90), cl::Hidden, cl::desc("The maximum number of steps while walking upwards to find " "MemoryDefs that may be killed (default = 90)"))
static cl::opt< unsigned >	MemorySSAPartialStoreLimit ("dse-memoryssa-partial-store-limit", cl::init(5), cl::Hidden, cl::desc("The maximum number candidates that only partially overwrite the " "killing MemoryDef to consider" " (default = 5)"))
static cl::opt< unsigned >	MemorySSADefsPerBlockLimit ("dse-memoryssa-defs-per-block-limit", cl::init(5000), cl::Hidden, cl::desc("The number of MemoryDefs we consider as candidates to eliminated " "other stores per basic block (default = 5000)"))
static cl::opt< unsigned >	MemorySSASameBBStepCost ("dse-memoryssa-samebb-cost", cl::init(1), cl::Hidden, cl::desc("The cost of a step in the same basic block as the killing MemoryDef" "(default = 1)"))
static cl::opt< unsigned >	MemorySSAOtherBBStepCost ("dse-memoryssa-otherbb-cost", cl::init(5), cl::Hidden, cl::desc("The cost of a step in a different basic " "block than the killing MemoryDef" "(default = 5)"))
static cl::opt< unsigned >	MemorySSAPathCheckLimit ("dse-memoryssa-path-check-limit", cl::init(50), cl::Hidden, cl::desc("The maximum number of blocks to check when trying to prove that " "all paths to an exit go through a killing block (default = 50)"))
static cl::opt< bool >	OptimizeMemorySSA ("dse-optimize-memoryssa", cl::init(true), cl::Hidden, cl::desc("Allow DSE to optimize memory accesses."))
static cl::opt< bool >	EnableInitializesImprovement ("enable-dse-initializes-attr-improvement", cl::init(true), cl::Hidden, cl::desc("Enable the initializes attr improvement in DSE"))
	dse
Dead Store	Elimination
Dead Store	false

◆ DEBUG_TYPE

◆ InstOverlapIntervalsTy

◆ OverlapIntervalsTy

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

◆ adjustArgAttributes()

◆ canSkipDef()

◆ DEBUG_COUNTER()

DEBUG_COUNTER	(	MemorySSACounter	,
"dse-memoryssa"	,
"Controls which MemoryDefs are eliminated."	)

◆ eliminateDeadStores()

◆ getIntersectedInitRangeList()

◆ getPointerSize()

◆ hasInitializesAttr()

◆ INITIALIZE_PASS_BEGIN()

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

◆ isFuncLocalAndNotCaptured()

◆ isMaskedStoreOverwrite()

◆ isNoopIntrinsic()

◆ isPartialOverwrite()

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

'OW_PartialEarlierWithFullLater' means that a dead (big) store was overwritten by a killing (smaller) store which doesn't write outside the big store's memory locations. Returns 'OW_Unknown' if nothing can be determined. NOTE: This function must only be called if both KillingLoc and DeadLoc belong to the same underlying object with valid KillingOff and DeadOff.

Definition at line 303 of file DeadStoreElimination.cpp.

References assert(), llvm::dbgs(), EnablePartialOverwriteTracking, EnablePartialStoreMerging, llvm::LocationSize::getValue(), LLVM_DEBUG, and llvm::MemoryLocation::Size.

◆ isShortenableAtTheBeginning()

◆ isShortenableAtTheEnd()

◆ memoryIsNotModifiedBetween()

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

References assert(), B(), DL, llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::MemoryLocation::get(), llvm::PHITransAddr::getAddr(), llvm::Function::getEntryBlock(), llvm::MemoryLocation::getForDest(), llvm::BasicBlock::getParent(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::MemoryLocation::getWithNewPtr(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::isModSet(), llvm::PHITransAddr::isPotentiallyPHITranslatable(), llvm::PHITransAddr::needsPHITranslationFromBlock(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::predecessors(), llvm::MemoryLocation::Ptr, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::PHITransAddr::translateValue().

Referenced by tryToMergePartialOverlappingStores().

◆ shortenAssignment()

◆ STATISTIC() [1/11]

STATISTIC	(	NumCFGChecks	,
"Number of stores modified"	)

◆ STATISTIC() [2/11]

STATISTIC	(	NumCFGSuccess	,
"Number of stores modified"	)

◆ STATISTIC() [3/11]

STATISTIC	(	NumCFGTries	,
"Number of stores modified"	)

◆ STATISTIC() [4/11]

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

◆ STATISTIC() [5/11]

STATISTIC	(	NumDomMemDefChecks	,
"Number iterations check for reads in getDomMemoryDef"	)

◆ STATISTIC() [6/11]

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

◆ STATISTIC() [7/11]

STATISTIC	(	NumFastStores	,
"Number of stores deleted"	)

◆ STATISTIC() [8/11]

STATISTIC	(	NumGetDomMemoryDefPassed	,
"Number of times a valid candidate is returned from getDomMemoryDef"	)

◆ STATISTIC() [9/11]

STATISTIC	(	NumModifiedStores	,
"Number of stores modified"	)

◆ STATISTIC() [10/11]

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

◆ STATISTIC() [11/11]

STATISTIC	(	NumRemainingStores	,
"Number of stores remaining after DSE"	)

◆ tryToMergePartialOverlappingStores()

Definition at line 764 of file DeadStoreElimination.cpp.

References assert(), llvm::cast(), llvm::dbgs(), DL, llvm::APInt::getBitsSet(), llvm::APInt::getBitWidth(), llvm::Value::getType(), llvm::StoreInst::getValueOperand(), llvm::isa(), LLVM_DEBUG, memoryIsNotModifiedBetween(), and llvm::APInt::zext().

◆ tryToShorten()

Definition at line 613 of file DeadStoreElimination.cpp.

References adjustArgAttributes(), assert(), llvm::cast(), llvm::GetElementPtrInst::CreateInBounds(), llvm::dbgs(), llvm::Type::getInt8Ty(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::isAligned(), LLVM_DEBUG, llvm::offsetToAlignment(), llvm::Instruction::setDebugLoc(), shortenAssignment(), and llvm::Align::value().

Referenced by tryToShortenBegin(), and tryToShortenEnd().

◆ tryToShortenBegin()

Definition at line 734 of file DeadStoreElimination.cpp.

References assert(), llvm::IntervalMap< KeyT, ValT, N, Traits >::begin(), llvm::IntervalMap< KeyT, ValT, N, Traits >::empty(), isShortenableAtTheBeginning(), and tryToShorten().

◆ tryToShortenEnd()

Definition at line 707 of file DeadStoreElimination.cpp.

References assert(), llvm::IntervalMap< KeyT, ValT, N, Traits >::empty(), llvm::IntervalMap< KeyT, ValT, N, Traits >::end(), isShortenableAtTheEnd(), and tryToShorten().

◆ dse

◆ Elimination

◆ EnableInitializesImprovement

cl::opt< bool > EnableInitializesImprovement("enable-dse-initializes-attr-improvement", cl::init(true), cl::Hidden, cl::desc("Enable the initializes attr improvement in DSE")) ( "enable-dse-initializes-attr-improvement" , cl::init(true) , cl::Hidden , cl::desc("Enable the initializes attr improvement in DSE") )	static

◆ EnablePartialOverwriteTracking

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

◆ EnablePartialStoreMerging

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

◆ false

◆ MemorySSADefsPerBlockLimit

◆ MemorySSAOtherBBStepCost

cl::opt< unsigned > MemorySSAOtherBBStepCost("dse-memoryssa-otherbb-cost", cl::init(5), cl::Hidden, cl::desc("The cost of a step in a different basic " "block than the killing MemoryDef" "(default = 5)")) ( "dse-memoryssa-otherbb-cost" , cl::init(5) , cl::Hidden , cl::desc("The cost of a step in a different basic " "block than the killing MemoryDef" "(default = 5)") )	static

◆ MemorySSAPartialStoreLimit

cl::opt< unsigned > MemorySSAPartialStoreLimit("dse-memoryssa-partial-store-limit", cl::init(5), cl::Hidden, cl::desc("The maximum number candidates that only partially overwrite the " "killing MemoryDef to consider" " (default = 5)")) ( "dse-memoryssa-partial-store-limit" , cl::init(5) , cl::Hidden , cl::desc("The maximum number candidates that only partially overwrite the " "killing MemoryDef to consider" " (default = 5)") )

static

◆ MemorySSAPathCheckLimit

cl::opt< unsigned > MemorySSAPathCheckLimit("dse-memoryssa-path-check-limit", cl::init(50), cl::Hidden, cl::desc("The maximum number of blocks to check when trying to prove that " "all paths to an exit go through a killing block (default = 50)")) ( "dse-memoryssa-path-check-limit" , cl::init(50) , cl::Hidden , cl::desc("The maximum number of blocks to check when trying to prove that " "all paths to an exit go through a killing block (default = 50)") )

static

◆ MemorySSASameBBStepCost

cl::opt< unsigned > MemorySSASameBBStepCost("dse-memoryssa-samebb-cost", cl::init(1), cl::Hidden, cl::desc( "The cost of a step in the same basic block as the killing MemoryDef" "(default = 1)")) ( "dse-memoryssa-samebb-cost" , cl::init(1) , cl::Hidden , cl::desc( "The cost of a step in the same basic block as the killing MemoryDef" "(default = 1)") )	static

◆ MemorySSAScanLimit

◆ MemorySSAUpwardsStepLimit

cl::opt< unsigned > MemorySSAUpwardsStepLimit("dse-memoryssa-walklimit", cl::init(90), cl::Hidden, cl::desc("The maximum number of steps while walking upwards to find " "MemoryDefs that may be killed (default = 90)")) ( "dse-memoryssa-walklimit" , cl::init(90) , cl::Hidden , cl::desc("The maximum number of steps while walking upwards to find " "MemoryDefs that may be killed (default = 90)") )	static

◆ OptimizeMemorySSA

cl::opt< bool > OptimizeMemorySSA("dse-optimize-memoryssa", cl::init(true), cl::Hidden, cl::desc("Allow DSE to optimize memory accesses.")) ( "dse-optimize-memoryssa" , cl::init(true) , cl::Hidden , cl::desc("Allow DSE to optimize memory accesses.") )	static