DeadStoreElimination.cpp File Reference

#include "llvm/Transforms/Scalar/DeadStoreElimination.h"
#include "ScalarOptions.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopedHashTable.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/AssumptionCache.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/CycleAnalysis.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/AttributeMask.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRangeList.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
#include "llvm/Transforms/Utils/BuildLibCalls.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <map>
#include <optional>
#include <utility>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "dse"

Typedefs
using	OverlapIntervalsTy = std::map<int64_t, int64_t>
using	InstOverlapIntervalsTy = MapVector<Instruction *, OverlapIntervalsTy>

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 ScalarOptions &Opts, 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 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 void	pushMemUses (MemoryAccess *Acc, SmallVectorImpl< MemoryAccess * > &WorkList, SmallPtrSetImpl< MemoryAccess * > &Visited)
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 CycleInfo &CI)
	INITIALIZE_PASS_BEGIN (DSELegacyPass, "dse", "Dead Store Elimination", false, false) INITIALIZE_PASS_END(DSELegacyPass

Variables
	dse
Dead Store	Elimination
Dead Store	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "dse"

Definition at line 97 of file DeadStoreElimination.cpp.

Typedef Documentation

InstOverlapIntervalsTy

using InstOverlapIntervalsTy = MapVector<Instruction *, OverlapIntervalsTy>

Definition at line 120 of file DeadStoreElimination.cpp.

OverlapIntervalsTy

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

Definition at line 119 of file DeadStoreElimination.cpp.

Function Documentation

adjustArgAttributes()

void adjustArgAttributes ( AnyMemIntrinsic * Intrinsic, unsigned ArgNo, uint64_t PtrOffset )

static

Update the attributes given that a memory access is updated (the dereferenced pointer could be moved forward when shortening a mem intrinsic).

Definition at line 527 of file DeadStoreElimination.cpp.

References llvm::AttributeMask::addAttribute(), llvm::isAligned(), and uint64_t.

Referenced by tryToShorten().

canSkipDef()

bool canSkipDef ( MemoryDef * D, bool DefVisibleToCaller )

static

Definition at line 793 of file DeadStoreElimination.cpp.

References D(), llvm::dyn_cast(), llvm::isa(), isNoopIntrinsic(), and llvm::Instruction::mayThrow().

DEBUG_COUNTER()

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

eliminateDeadStores()

bool eliminateDeadStores ( Function & F, AliasAnalysis & AA, MemorySSA & MSSA, DominatorTree & DT, PostDominatorTree & PDT, const TargetLibraryInfo & TLI, const CycleInfo & CI )

static

Definition at line 2722 of file DeadStoreElimination.cpp.

References llvm::Instruction::eraseFromParent(), F, llvm::MemoryUseOrDef::getMemoryInst(), and I.

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

getIntersectedInitRangeList()

ConstantRangeList getIntersectedInitRangeList ( ArrayRef< ArgumentInitInfo > Args, bool CallHasNoUnwindAttr )

static

Definition at line 873 of file DeadStoreElimination.cpp.

References llvm::ConstantRangeList::intersectWith().

getPointerSize()

std::optional< TypeSize > getPointerSize ( const Value * V, const DataLayout & DL, const TargetLibraryInfo & TLI, const Function * F )

static

Definition at line 155 of file DeadStoreElimination.cpp.

References DL, F, llvm::TypeSize::getFixed(), llvm::getObjectSize(), llvm::ObjectSizeOpts::NullIsUnknownSize, llvm::NullPointerIsDefined(), Size, and uint64_t.

hasInitializesAttr()

bool hasInitializesAttr ( Instruction * I )

static

Definition at line 863 of file DeadStoreElimination.cpp.

References llvm::dyn_cast(), llvm::CallBase::getArgOperandWithAttribute(), and I.

INITIALIZE_PASS_BEGIN()

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

References INITIALIZE_PASS_DEPENDENCY.

isFuncLocalAndNotCaptured()

bool isFuncLocalAndNotCaptured ( Value * Arg, const CallBase * CB, EarliestEscapeAnalysis & EA )

static

Definition at line 1120 of file DeadStoreElimination.cpp.

References llvm::capturesNothing(), llvm::EarliestEscapeAnalysis::getCapturesBefore(), llvm::getUnderlyingObject(), and llvm::isIdentifiedFunctionLocal().

isMaskedStoreOverwrite()

OverwriteResult isMaskedStoreOverwrite ( const Instruction * KillingI, const Instruction * DeadI, BatchAAResults & AA )

static

Check if two instruction are masked stores that completely overwrite one another.

More specifically, KillingI has to overwrite DeadI.

Definition at line 185 of file DeadStoreElimination.cpp.

References llvm::cast(), DL, and llvm::dyn_cast().

isNoopIntrinsic()

bool isNoopIntrinsic ( Instruction * I )

static

Definition at line 772 of file DeadStoreElimination.cpp.

References llvm::dyn_cast(), I, II, and llvm_unreachable.

Referenced by canSkipDef().

isPartialOverwrite()

OverwriteResult isPartialOverwrite ( const ScalarOptions & Opts, const MemoryLocation & KillingLoc, const MemoryLocation & DeadLoc, int64_t KillingOff, int64_t DeadOff, Instruction * DeadI, InstOverlapIntervalsTy & IOL )

static

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

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

isShortenableAtTheBeginning()

bool isShortenableAtTheBeginning ( Instruction * I )

static

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

Definition at line 149 of file DeadStoreElimination.cpp.

References I, and llvm::isa().

Referenced by tryToShortenBegin().

isShortenableAtTheEnd()

bool isShortenableAtTheEnd ( Instruction * I )

static

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

Definition at line 124 of file DeadStoreElimination.cpp.

References llvm::dyn_cast(), I, II, and llvm::isa().

Referenced by tryToShortenEnd().

memoryIsNotModifiedBetween()

bool memoryIsNotModifiedBetween ( Instruction * FirstI, Instruction * SecondI, BatchAAResults & AA, const DataLayout & DL, DominatorTree * DT )

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 362 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< StorageT, 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().

pushMemUses()

void pushMemUses ( MemoryAccess * Acc, SmallVectorImpl< MemoryAccess * > & WorkList, SmallPtrSetImpl< MemoryAccess * > & Visited )

static

Definition at line 1109 of file DeadStoreElimination.cpp.

References llvm::cast(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::Value::uses().

shortenAssignment()

void shortenAssignment ( Instruction * Inst, Value * OriginalDest, uint64_t OldSizeInBits, uint64_t NewSizeInBits, bool IsOverwriteEnd )

static

Definition at line 449 of file DeadStoreElimination.cpp.

References llvm::at::calculateFragmentIntersect(), llvm::DIExpression::createFragmentExpression(), DL, llvm::MDNode::get(), llvm::Value::getContext(), llvm::Instruction::getDataLayout(), llvm::DIAssignID::getDistinct(), llvm::at::getDVRAssignmentMarkers(), and uint64_t.

Referenced by tryToShorten().

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

Constant * tryToMergePartialOverlappingStores ( StoreInst * KillingI, StoreInst * DeadI, int64_t KillingOffset, int64_t DeadOffset, const DataLayout & DL, BatchAAResults & AA, DominatorTree * DT )

static

Definition at line 711 of file DeadStoreElimination.cpp.

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

tryToShorten()

bool tryToShorten ( Instruction * DeadI, int64_t & DeadStart, uint64_t & DeadSize, int64_t KillingStart, uint64_t KillingSize, bool IsOverwriteEnd )

static

Definition at line 561 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, Off, llvm::offsetToAlignment(), llvm::Instruction::setDebugLoc(), shortenAssignment(), uint64_t, and llvm::Align::value().

Referenced by tryToShortenBegin(), and tryToShortenEnd().

tryToShortenBegin()

bool tryToShortenBegin ( Instruction * DeadI, OverlapIntervalsTy & IntervalMap, int64_t & DeadStart, uint64_t & DeadSize )

static

Definition at line 681 of file DeadStoreElimination.cpp.

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

tryToShortenEnd()

bool tryToShortenEnd ( Instruction * DeadI, OverlapIntervalsTy & IntervalMap, int64_t & DeadStart, uint64_t & DeadSize )

static

Definition at line 654 of file DeadStoreElimination.cpp.

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

Variable Documentation

dse

dse

Definition at line 2850 of file DeadStoreElimination.cpp.

Elimination

Dead Store Elimination

Definition at line 2850 of file DeadStoreElimination.cpp.

false

Dead Store false

Definition at line 2850 of file DeadStoreElimination.cpp.