70 #define DEBUG_TYPE "dse" 72 STATISTIC(NumRedundantStores,
"Number of redundant stores deleted");
73 STATISTIC(NumFastStores,
"Number of stores deleted");
74 STATISTIC(NumFastOther,
"Number of other instrs removed");
75 STATISTIC(NumCompletePartials,
"Number of stores dead by later partials");
76 STATISTIC(NumModifiedStores,
"Number of stores modified");
81 cl::desc(
"Enable partial-overwrite tracking in DSE"));
86 cl::desc(
"Enable partial store merging in DSE"));
138 if (ValueSet) ValueSet->remove(DeadInst);
139 InstrOrdering->
erase(DeadInst);
146 }
while (!NowDeadInsts.
empty());
154 if (isa<StoreInst>(I))
157 switch (II->getIntrinsicID()) {
172 if (
Function *
F = CS.getCalledFunction()) {
174 if (TLI.
has(LibFunc_strcpy) && FnName == TLI.
getName(LibFunc_strcpy))
176 if (TLI.
has(LibFunc_strncpy) && FnName == TLI.
getName(LibFunc_strncpy))
178 if (TLI.
has(LibFunc_strcat) && FnName == TLI.
getName(LibFunc_strcat))
180 if (TLI.
has(LibFunc_strncat) && FnName == TLI.
getName(LibFunc_strncat))
195 if (
auto *
MI = dyn_cast<AnyMemIntrinsic>(Inst)) {
202 switch (II->getIntrinsicID()) {
208 uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
228 if (
auto *MTI = dyn_cast<AnyMemTransferInst>(Inst))
238 return SI->isUnordered();
241 switch (II->getIntrinsicID()) {
242 default:
llvm_unreachable(
"doesn't pass 'hasAnalyzableMemoryWrite' predicate");
264 return CS.getInstruction()->use_empty();
273 if (isa<StoreInst>(I))
277 switch (II->getIntrinsicID()) {
278 default:
return false;
299 return isa<AnyMemSetInst>(
I);
307 "unable to find pointer written for analyzable instruction?");
330 OW_PartialEarlierWithFullLater,
347 int64_t &EarlierOff, int64_t &LaterOff,
367 if (LaterSize >= EarlierSize)
385 if (ObjectSize == LaterSize && ObjectSize >= EarlierSize)
415 if (EarlierOff >= LaterOff &&
416 LaterSize >= EarlierSize &&
417 uint64_t(EarlierOff - LaterOff) + EarlierSize <= LaterSize)
426 LaterOff < int64_t(EarlierOff + EarlierSize) &&
427 int64_t(LaterOff + LaterSize) >= EarlierOff) {
430 auto &IM = IOL[DepWrite];
431 LLVM_DEBUG(
dbgs() <<
"DSE: Partial overwrite: Earlier [" << EarlierOff
432 <<
", " << int64_t(EarlierOff + EarlierSize)
433 <<
") Later [" << LaterOff <<
", " 434 << int64_t(LaterOff + LaterSize) <<
")\n");
440 int64_t LaterIntStart = LaterOff, LaterIntEnd = LaterOff + LaterSize;
444 auto ILI = IM.lower_bound(LaterIntStart);
445 if (ILI != IM.end() && ILI->second <= LaterIntEnd) {
449 LaterIntStart = std::min(LaterIntStart, ILI->second);
450 LaterIntEnd =
std::max(LaterIntEnd, ILI->first);
459 while (ILI != IM.end() && ILI->second <= LaterIntEnd) {
460 assert(ILI->second > LaterIntStart &&
"Unexpected interval");
461 LaterIntEnd =
std::max(LaterIntEnd, ILI->first);
466 IM[LaterIntEnd] = LaterIntStart;
469 if (ILI->second <= EarlierOff &&
470 ILI->first >= int64_t(EarlierOff + EarlierSize)) {
471 LLVM_DEBUG(
dbgs() <<
"DSE: Full overwrite from partials: Earlier [" 472 << EarlierOff <<
", " 473 << int64_t(EarlierOff + EarlierSize)
474 <<
") Composite Later [" << ILI->second <<
", " 475 << ILI->first <<
")\n");
476 ++NumCompletePartials;
484 int64_t(EarlierOff + EarlierSize) > LaterOff &&
485 uint64_t(LaterOff - EarlierOff) + LaterSize <= EarlierSize) {
487 << EarlierOff <<
", " 488 << int64_t(EarlierOff + EarlierSize)
489 <<
") by a later store [" << LaterOff <<
", " 490 << int64_t(LaterOff + LaterSize) <<
")\n");
492 return OW_PartialEarlierWithFullLater;
504 (LaterOff > EarlierOff && LaterOff < int64_t(EarlierOff + EarlierSize) &&
505 int64_t(LaterOff + LaterSize) >= int64_t(EarlierOff + EarlierSize)))
518 (LaterOff <= EarlierOff && int64_t(LaterOff + LaterSize) > EarlierOff)) {
519 assert(int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize) &&
520 "Expect to be handled as OW_Complete");
548 if (!InstReadLoc.
Ptr)
552 if (AA.
isNoAlias(InstReadLoc, InstStoreLoc))
555 if (isa<AnyMemCpyInst>(Inst)) {
600 bool isFirstBlock =
true;
603 while (!WorkList.
empty()) {
612 assert(B == SecondBB &&
"first block is not the store block");
614 isFirstBlock =
false;
620 for (; BI != EI; ++BI) {
628 "Should not hit the entry block because SI must be dominated by LI");
630 if (!Visited.
insert(*PredI).second)
645 if (Pred == BB)
continue;
662 bool MadeChange =
false;
669 while (!Blocks.empty()) {
690 dbgs() <<
"DSE: Dead Store to soon to be freed memory:\n DEAD: " 691 << *Dependency <<
'\n');
725 if (isa<Constant>(UnderlyingPointer))
730 if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) {
731 DeadStackObjects.
remove(const_cast<Value*>(UnderlyingPointer));
739 return !AA->
isNoAlias(StackLoc, LoadedLoc);
754 bool MadeChange =
false;
763 if (isa<AllocaInst>(&
I))
775 if (AI.hasByValOrInAllocaAttr())
776 DeadStackObjects.
insert(&AI);
792 for (
Value *Pointer : Pointers)
793 if (!DeadStackObjects.
count(Pointer)) {
802 << *Dead <<
"\n Objects: ";
807 if (std::next(
I) !=
E)
822 LLVM_DEBUG(
dbgs() <<
"DSE: Removing trivially dead instruction:\n DEAD: " 830 if (isa<AllocaInst>(BBI)) {
833 DeadStackObjects.
remove(&*BBI);
837 if (
auto *Call = dyn_cast<CallBase>(&*BBI)) {
841 DeadStackObjects.
remove(&*BBI);
858 if (DeadStackObjects.
empty())
869 if (isa<FenceInst>(*BBI))
875 if (
LoadInst *L = dyn_cast<LoadInst>(BBI)) {
876 if (!L->isUnordered())
879 }
else if (
VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
881 }
else if (!BBI->mayReadFromMemory()) {
896 if (DeadStackObjects.
empty())
904 int64_t &EarlierSize, int64_t LaterOffset,
905 int64_t LaterSize,
bool IsOverwriteEnd) {
912 auto *EarlierIntrinsic = cast<AnyMemIntrinsic>(EarlierWrite);
913 unsigned EarlierWriteAlign = EarlierIntrinsic->getDestAlignment();
915 LaterOffset = int64_t(LaterOffset + LaterSize);
917 if (!(
isPowerOf2_64(LaterOffset) && EarlierWriteAlign <= LaterOffset) &&
918 !((EarlierWriteAlign != 0) && LaterOffset % EarlierWriteAlign == 0))
921 int64_t NewLength = IsOverwriteEnd
922 ? LaterOffset - EarlierOffset
923 : EarlierSize - (LaterOffset - EarlierOffset);
925 if (
auto *AMI = dyn_cast<AtomicMemIntrinsic>(EarlierWrite)) {
928 const uint32_t ElementSize = AMI->getElementSizeInBytes();
929 if (0 != NewLength % ElementSize)
934 << (IsOverwriteEnd ?
"END" :
"BEGIN") <<
": " 935 << *EarlierWrite <<
"\n KILLER (offset " << LaterOffset
936 <<
", " << EarlierSize <<
")\n");
938 Value *EarlierWriteLength = EarlierIntrinsic->getLength();
939 Value *TrimmedLength =
941 EarlierIntrinsic->setLength(TrimmedLength);
943 EarlierSize = NewLength;
944 if (!IsOverwriteEnd) {
945 int64_t OffsetMoved = (LaterOffset - EarlierOffset);
946 Value *Indices[1] = {
949 EarlierIntrinsic->getRawDest(), Indices,
"", EarlierWrite);
950 EarlierIntrinsic->setDest(NewDestGEP);
951 EarlierOffset = EarlierOffset + OffsetMoved;
958 int64_t &EarlierStart, int64_t &EarlierSize) {
962 OverlapIntervalsTy::iterator OII = --IntervalMap.end();
963 int64_t LaterStart = OII->second;
964 int64_t LaterSize = OII->first - LaterStart;
966 if (LaterStart > EarlierStart && LaterStart < EarlierStart + EarlierSize &&
967 LaterStart + LaterSize >= EarlierStart + EarlierSize) {
968 if (
tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,
970 IntervalMap.erase(OII);
979 int64_t &EarlierStart, int64_t &EarlierSize) {
983 OverlapIntervalsTy::iterator OII = IntervalMap.begin();
984 int64_t LaterStart = OII->second;
985 int64_t LaterSize = OII->first - LaterStart;
987 if (LaterStart <= EarlierStart && LaterStart + LaterSize > EarlierStart) {
988 assert(LaterStart + LaterSize < EarlierStart + EarlierSize &&
989 "Should have been handled as OW_Complete");
990 if (
tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,
992 IntervalMap.erase(OII);
1002 bool Changed =
false;
1003 for (
auto OI : IOL) {
1009 int64_t EarlierStart = 0;
1014 tryToShortenEnd(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
1015 if (IntervalMap.empty())
1041 dbgs() <<
"DSE: Remove Store Of Load from same pointer:\n LOAD: " 1042 << *DepLoad <<
"\n STORE: " << *SI <<
'\n');
1045 ++NumRedundantStores;
1056 if (UnderlyingPointer &&
isCallocLikeFn(UnderlyingPointer, TLI) &&
1059 dbgs() <<
"DSE: Remove null store to the calloc'ed object:\n DEAD: " 1060 << *Inst <<
"\n OBJECT: " << *UnderlyingPointer <<
'\n');
1063 ++NumRedundantStores;
1074 bool MadeChange =
false;
1078 size_t LastThrowingInstIndex = 0;
1080 size_t InstrIndex = 1;
1089 MadeChange |=
handleFree(
F, AA, MD, DT, TLI, IOL, &InstrOrdering);
1098 size_t CurInstNumber = InstrIndex++;
1099 InstrOrdering.
insert(std::make_pair(Inst, CurInstNumber));
1101 LastThrowingInstIndex = CurInstNumber;
1161 size_t DepIndex = InstrOrdering.
lookup(DepWrite);
1162 assert(DepIndex &&
"Unexpected instruction");
1163 if (DepIndex <= LastThrowingInstIndex) {
1165 bool IsStoreDeadOnUnwind = isa<AllocaInst>(
Underlying);
1166 if (!IsStoreDeadOnUnwind) {
1174 if (!IsStoreDeadOnUnwind)
1185 int64_t InstWriteOffset, DepWriteOffset;
1187 InstWriteOffset, DepWrite, IOL, *AA,
1189 if (OR == OW_Complete) {
1190 LLVM_DEBUG(
dbgs() <<
"DSE: Remove Dead Store:\n DEAD: " << *DepWrite
1191 <<
"\n KILLER: " << *Inst <<
'\n');
1205 "when partial-overwrite " 1206 "tracking is enabled");
1210 bool IsOverwriteEnd = (OR == OW_End);
1211 MadeChange |=
tryToShorten(DepWrite, DepWriteOffset, EarlierSize,
1212 InstWriteOffset, LaterSize, IsOverwriteEnd);
1214 OR == OW_PartialEarlierWithFullLater) {
1217 if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&
1218 Later && isa<ConstantInt>(Later->getValueOperand()) &&
1229 APInt EarlierValue =
1230 cast<ConstantInt>(Earlier->getValueOperand())->getValue();
1232 cast<ConstantInt>(Later->getValueOperand())->getValue();
1238 unsigned BitOffsetDiff = (InstWriteOffset - DepWriteOffset) * 8;
1239 unsigned LShiftAmount =
1241 ? EarlierValue.
getBitWidth() - BitOffsetDiff - LaterBits
1245 LShiftAmount + LaterBits);
1249 (EarlierValue & ~Mask) | (LaterValue << LShiftAmount);
1250 LLVM_DEBUG(
dbgs() <<
"DSE: Merge Stores:\n Earlier: " << *DepWrite
1251 <<
"\n Later: " << *Inst
1252 <<
"\n Merged Value: " << Merged <<
'\n');
1256 Earlier->getPointerOperand(),
false, Earlier->getAlignment(),
1257 Earlier->getOrdering(), Earlier->getSyncScopeID(), DepWrite);
1263 SI->copyMetadata(*DepWrite, MDToKeep);
1264 ++NumModifiedStores;
1267 size_t Idx = InstrOrdering.
lookup(DepWrite);
1268 InstrOrdering.
erase(DepWrite);
1269 InstrOrdering.
insert(std::make_pair(
SI, Idx));
1291 if (DepWrite == &BB.
front())
break;
1309 MadeChange |=
handleEndBlock(BB, AA, MD, TLI, IOL, &InstrOrdering);
1317 bool MadeChange =
false;
1358 if (skipFunction(F))
1361 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1362 AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
1364 &getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
1366 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1398 return new DSELegacyPass();
Legacy wrapper pass to provide the GlobalsAAResult object.
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
Value * getValueOperand()
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
A parsed version of the target data layout string in and methods for querying it. ...
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Provides a lazy, caching interface for making common memory aliasing information queries, backed by LLVM's alias analysis passes.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents an incoming formal argument to a Function.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
This class represents lattice values for constants.
This is the interface for a simple mod/ref and alias analysis over globals.
void initializeDSELegacyPassPass(PassRegistry &)
void push_back(const T &Elt)
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are no-alias. ...
APInt zext(unsigned width) const
Zero extend to a new width.
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated...
This class represents a function call, abstracting a target machine's calling convention.
bool isNonLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the block...
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
StringRef getName(LibFunc F) const
bool salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
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.
An instruction for reading from memory.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
static bool isPossibleSelfRead(Instruction *Inst, const MemoryLocation &InstStoreLoc, Instruction *DepWrite, const TargetLibraryInfo &TLI, AliasAnalysis &AA)
If 'Inst' might be a self read (i.e.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
unsigned getBitWidth() const
Return the number of bits in the APInt.
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...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
const CallInst * isFreeCall(const Value *I, const TargetLibraryInfo *TLI)
isFreeCall - Returns non-null if the value is a call to the builtin free()
iterator begin()
Instruction iterator methods.
Value * getArgOperand(unsigned i) const
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
#define INITIALIZE_PASS_DEPENDENCY(depName)
bool isDef() const
Tests if this MemDepResult represents a query that is an instruction definition dependency.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
bool isClobber() const
Tests if this MemDepResult represents a query that is an instruction clobber dependency.
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.
unsigned getDefaultBlockScanLimit() const
Some methods limit the number of instructions they will examine.
An analysis that produces MemoryDependenceResults for a function.
static MemoryLocation getLocForWrite(Instruction *Inst)
Return a Location stored to by the specified instruction.
bool remove(const value_type &X)
Remove an item from the set vector.
This file implements a class to represent arbitrary precision integral constant values and operations...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Type * getType() const
All values are typed, get the type of this value.
bool insert(const value_type &X)
Insert a new element into the SetVector.
static Value * getStoredPointerOperand(Instruction *I)
Return the pointer that is being written to.
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
Value * GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout &DL)
Analyze the specified pointer to see if it can be expressed as a base pointer plus a constant offset...
bool has(LibFunc F) const
Tests whether a library function is available.
std::map< int64_t, int64_t > OverlapIntervalsTy
static uint64_t getPointerSize(const Value *V, const DataLayout &DL, const TargetLibraryInfo &TLI, const Function *F)
An instruction for storing to memory.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Value * getOperand(unsigned i) const
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
uint64_t getValue() const
const BasicBlock & getEntryBlock() const
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
static bool runOnFunction(Function &F, bool PostInlining)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
initializer< Ty > init(const Ty &Val)
bool erase(const KeyT &Val)
static bool isShortenableAtTheBeginning(Instruction *I)
Returns true if the beginning of this instruction can be safely shortened in length.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
LLVM Basic Block Representation.
static bool removePartiallyOverlappedStores(AliasAnalysis *AA, const DataLayout &DL, InstOverlapIntervalsTy &IOL)
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...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
A manager for alias analyses.
static ManagedStatic< OptionRegistry > OR
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool mayThrow() const
Return true if this instruction may throw an exception.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
static bool isShortenableAtTheEnd(Instruction *I)
Returns true if the end of this instruction can be safely shortened in length.
Represent the analysis usage information of a pass.
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
FunctionPass * createDeadStoreEliminationPass()
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 fi...
std::underlying_type< E >::type Underlying(E Val)
Check that Val is in range for E, and return Val cast to E's underlying type.
Analysis pass providing a never-invalidated alias analysis result.
FunctionPass class - This class is used to implement most global optimizations.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known...
Interval::pred_iterator pred_end(Interval *I)
self_iterator getIterator()
INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false, false) INITIALIZE_PASS_END(DSELegacyPass
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, and aliases.
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance...
Value * GetUnderlyingObject(Value *V, const DataLayout &DL, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
A memory dependence query can return one of three different answers.
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
static cl::opt< bool > EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking", cl::init(true), cl::Hidden, cl::desc("Enable partial-overwrite tracking in DSE"))
MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst=nullptr, unsigned *Limit=nullptr)
Returns the instruction on which a memory location depends.
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.
static cl::opt< bool > EnablePartialStoreMerging("enable-dse-partial-store-merging", cl::init(true), cl::Hidden, cl::desc("Enable partial store merging in DSE"))
A SetVector that performs no allocations if smaller than a certain size.
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
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...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
LLVM_NODISCARD T pop_back_val()
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 o...
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
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)
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
void setOperand(unsigned i, Value *Val)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Class for arbitrary precision integers.
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are must-alias.
Represents analyses that only rely on functions' control flow.
static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit)
Get a value with a block of bits set.
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
static bool tryToShortenBegin(Instruction *EarlierWrite, OverlapIntervalsTy &IntervalMap, int64_t &EarlierStart, int64_t &EarlierSize)
bool doesNotAccessMemory(const CallBase *Call)
Checks if the specified call is known to never read or write memory.
Instruction * getInst() const
If this is a normal dependency, returns the instruction that is depended on.
static MemoryLocation getLocForRead(Instruction *Inst, const TargetLibraryInfo &TLI)
Return the location read by the specified "hasAnalyzableMemoryWrite" instruction if any...
LLVM_NODISCARD bool empty() const
This file provides utility analysis objects describing memory locations.
void preserveSet()
Mark an analysis set as preserved.
const Function * getParent() const
Return the enclosing method, or null if none.
bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates zero-filled memory (such as...
bool empty() const
Determine if the SetVector is empty or not.
bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates memory (either malloc...
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
void preserve()
Mark an analysis as preserved.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Analysis pass providing the TargetLibraryInfo.
void GetUnderlyingObjects(Value *V, SmallVectorImpl< Value *> &Objects, const DataLayout &DL, LoopInfo *LI=nullptr, unsigned MaxLookup=6)
This method is similar to GetUnderlyingObject except that it can look through phi and select instruct...
static GetElementPtrInst * CreateInBounds(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Create an "inbounds" getelementptr.
static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, const TargetLibraryInfo *TLI)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const BasicBlock & front() const
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
LLVM Value Representation.
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
bool remove_if(UnaryPredicate P)
Remove items from the set vector based on a predicate function.
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
static bool isRemovable(Instruction *I)
If the value of this instruction and the memory it writes to is unused, may we delete this instructio...
StringRef - Represent a constant reference to a string, i.e.
Various options to control the behavior of getObjectSize.
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
static bool isVolatile(Instruction *Inst)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
This header defines various interfaces for pass management in LLVM.
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
Value * getPointerOperand()
static bool tryToShorten(Instruction *EarlierWrite, int64_t &EarlierOffset, int64_t &EarlierSize, int64_t LaterOffset, int64_t LaterSize, bool IsOverwriteEnd)
iterator_range< arg_iterator > args()
A wrapper class for inspecting calls to intrinsic functions.
const BasicBlock * getParent() const
static bool tryToShortenEnd(Instruction *EarlierWrite, OverlapIntervalsTy &IntervalMap, int64_t &EarlierStart, int64_t &EarlierSize)
MemDepResult getDependency(Instruction *QueryInst)
Returns the instruction on which a memory operation depends.
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=DefaultMaxUsesToExplore)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)