1 //===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file implements a trivial dead store elimination that only considers
10 // basic-block local redundant stores.
12 // FIXME: This should eventually be extended to be a post-dominator tree
13 // traversal. Doing so would be pretty trivial.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
18 #include "llvm/ADT/APInt.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/ADT/StringRef.h"
25 #include "llvm/Analysis/AliasAnalysis.h"
26 #include "llvm/Analysis/CaptureTracking.h"
27 #include "llvm/Analysis/GlobalsModRef.h"
28 #include "llvm/Analysis/MemoryBuiltins.h"
29 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
30 #include "llvm/Analysis/MemoryLocation.h"
31 #include "llvm/Analysis/OrderedBasicBlock.h"
32 #include "llvm/Analysis/TargetLibraryInfo.h"
33 #include "llvm/Analysis/ValueTracking.h"
34 #include "llvm/IR/Argument.h"
35 #include "llvm/IR/BasicBlock.h"
36 #include "llvm/IR/CallSite.h"
37 #include "llvm/IR/Constant.h"
38 #include "llvm/IR/Constants.h"
39 #include "llvm/IR/DataLayout.h"
40 #include "llvm/IR/Dominators.h"
41 #include "llvm/IR/Function.h"
42 #include "llvm/IR/InstrTypes.h"
43 #include "llvm/IR/Instruction.h"
44 #include "llvm/IR/Instructions.h"
45 #include "llvm/IR/IntrinsicInst.h"
46 #include "llvm/IR/Intrinsics.h"
47 #include "llvm/IR/LLVMContext.h"
48 #include "llvm/IR/Module.h"
49 #include "llvm/IR/PassManager.h"
50 #include "llvm/IR/Value.h"
51 #include "llvm/Pass.h"
52 #include "llvm/Support/Casting.h"
53 #include "llvm/Support/CommandLine.h"
54 #include "llvm/Support/Debug.h"
55 #include "llvm/Support/ErrorHandling.h"
56 #include "llvm/Support/MathExtras.h"
57 #include "llvm/Support/raw_ostream.h"
58 #include "llvm/Transforms/Scalar.h"
59 #include "llvm/Transforms/Utils/Local.h"
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");
79 EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",
80 cl::init(true), cl::Hidden
,
81 cl::desc("Enable partial-overwrite tracking in DSE"));
84 EnablePartialStoreMerging("enable-dse-partial-store-merging",
85 cl::init(true), cl::Hidden
,
86 cl::desc("Enable partial store merging in DSE"));
88 //===----------------------------------------------------------------------===//
90 //===----------------------------------------------------------------------===//
91 using OverlapIntervalsTy
= std::map
<int64_t, int64_t>;
92 using InstOverlapIntervalsTy
= DenseMap
<Instruction
*, OverlapIntervalsTy
>;
94 /// Delete this instruction. Before we do, go through and zero out all the
95 /// operands of this instruction. If any of them become dead, delete them and
96 /// the computation tree that feeds them.
97 /// If ValueSet is non-null, remove any deleted instructions from it as well.
99 deleteDeadInstruction(Instruction
*I
, BasicBlock::iterator
*BBI
,
100 MemoryDependenceResults
&MD
, const TargetLibraryInfo
&TLI
,
101 InstOverlapIntervalsTy
&IOL
, OrderedBasicBlock
&OBB
,
102 SmallSetVector
<const Value
*, 16> *ValueSet
= nullptr) {
103 SmallVector
<Instruction
*, 32> NowDeadInsts
;
105 NowDeadInsts
.push_back(I
);
108 // Keeping the iterator straight is a pain, so we let this routine tell the
109 // caller what the next instruction is after we're done mucking about.
110 BasicBlock::iterator NewIter
= *BBI
;
112 // Before we touch this instruction, remove it from memdep!
114 Instruction
*DeadInst
= NowDeadInsts
.pop_back_val();
117 // Try to preserve debug information attached to the dead instruction.
118 salvageDebugInfo(*DeadInst
);
120 // This instruction is dead, zap it, in stages. Start by removing it from
121 // MemDep, which needs to know the operands and needs it to be in the
123 MD
.removeInstruction(DeadInst
);
125 for (unsigned op
= 0, e
= DeadInst
->getNumOperands(); op
!= e
; ++op
) {
126 Value
*Op
= DeadInst
->getOperand(op
);
127 DeadInst
->setOperand(op
, nullptr);
129 // If this operand just became dead, add it to the NowDeadInsts list.
130 if (!Op
->use_empty()) continue;
132 if (Instruction
*OpI
= dyn_cast
<Instruction
>(Op
))
133 if (isInstructionTriviallyDead(OpI
, &TLI
))
134 NowDeadInsts
.push_back(OpI
);
137 if (ValueSet
) ValueSet
->remove(DeadInst
);
139 OBB
.eraseInstruction(DeadInst
);
141 if (NewIter
== DeadInst
->getIterator())
142 NewIter
= DeadInst
->eraseFromParent();
144 DeadInst
->eraseFromParent();
145 } while (!NowDeadInsts
.empty());
149 /// Does this instruction write some memory? This only returns true for things
150 /// that we can analyze with other helpers below.
151 static bool hasAnalyzableMemoryWrite(Instruction
*I
,
152 const TargetLibraryInfo
&TLI
) {
153 if (isa
<StoreInst
>(I
))
155 if (IntrinsicInst
*II
= dyn_cast
<IntrinsicInst
>(I
)) {
156 switch (II
->getIntrinsicID()) {
159 case Intrinsic::memset
:
160 case Intrinsic::memmove
:
161 case Intrinsic::memcpy
:
162 case Intrinsic::memcpy_element_unordered_atomic
:
163 case Intrinsic::memmove_element_unordered_atomic
:
164 case Intrinsic::memset_element_unordered_atomic
:
165 case Intrinsic::init_trampoline
:
166 case Intrinsic::lifetime_end
:
170 if (auto CS
= CallSite(I
)) {
171 if (Function
*F
= CS
.getCalledFunction()) {
172 StringRef FnName
= F
->getName();
173 if (TLI
.has(LibFunc_strcpy
) && FnName
== TLI
.getName(LibFunc_strcpy
))
175 if (TLI
.has(LibFunc_strncpy
) && FnName
== TLI
.getName(LibFunc_strncpy
))
177 if (TLI
.has(LibFunc_strcat
) && FnName
== TLI
.getName(LibFunc_strcat
))
179 if (TLI
.has(LibFunc_strncat
) && FnName
== TLI
.getName(LibFunc_strncat
))
186 /// Return a Location stored to by the specified instruction. If isRemovable
187 /// returns true, this function and getLocForRead completely describe the memory
188 /// operations for this instruction.
189 static MemoryLocation
getLocForWrite(Instruction
*Inst
) {
191 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(Inst
))
192 return MemoryLocation::get(SI
);
194 if (auto *MI
= dyn_cast
<AnyMemIntrinsic
>(Inst
)) {
195 // memcpy/memmove/memset.
196 MemoryLocation Loc
= MemoryLocation::getForDest(MI
);
200 if (IntrinsicInst
*II
= dyn_cast
<IntrinsicInst
>(Inst
)) {
201 switch (II
->getIntrinsicID()) {
203 return MemoryLocation(); // Unhandled intrinsic.
204 case Intrinsic::init_trampoline
:
205 return MemoryLocation(II
->getArgOperand(0));
206 case Intrinsic::lifetime_end
: {
207 uint64_t Len
= cast
<ConstantInt
>(II
->getArgOperand(0))->getZExtValue();
208 return MemoryLocation(II
->getArgOperand(1), Len
);
212 if (auto CS
= CallSite(Inst
))
213 // All the supported TLI functions so far happen to have dest as their
215 return MemoryLocation(CS
.getArgument(0));
216 return MemoryLocation();
219 /// Return the location read by the specified "hasAnalyzableMemoryWrite"
220 /// instruction if any.
221 static MemoryLocation
getLocForRead(Instruction
*Inst
,
222 const TargetLibraryInfo
&TLI
) {
223 assert(hasAnalyzableMemoryWrite(Inst
, TLI
) && "Unknown instruction case");
225 // The only instructions that both read and write are the mem transfer
226 // instructions (memcpy/memmove).
227 if (auto *MTI
= dyn_cast
<AnyMemTransferInst
>(Inst
))
228 return MemoryLocation::getForSource(MTI
);
229 return MemoryLocation();
232 /// If the value of this instruction and the memory it writes to is unused, may
233 /// we delete this instruction?
234 static bool isRemovable(Instruction
*I
) {
235 // Don't remove volatile/atomic stores.
236 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(I
))
237 return SI
->isUnordered();
239 if (IntrinsicInst
*II
= dyn_cast
<IntrinsicInst
>(I
)) {
240 switch (II
->getIntrinsicID()) {
241 default: llvm_unreachable("doesn't pass 'hasAnalyzableMemoryWrite' predicate");
242 case Intrinsic::lifetime_end
:
243 // Never remove dead lifetime_end's, e.g. because it is followed by a
246 case Intrinsic::init_trampoline
:
247 // Always safe to remove init_trampoline.
249 case Intrinsic::memset
:
250 case Intrinsic::memmove
:
251 case Intrinsic::memcpy
:
252 // Don't remove volatile memory intrinsics.
253 return !cast
<MemIntrinsic
>(II
)->isVolatile();
254 case Intrinsic::memcpy_element_unordered_atomic
:
255 case Intrinsic::memmove_element_unordered_atomic
:
256 case Intrinsic::memset_element_unordered_atomic
:
261 // note: only get here for calls with analyzable writes - i.e. libcalls
262 if (auto CS
= CallSite(I
))
263 return CS
.getInstruction()->use_empty();
268 /// Returns true if the end of this instruction can be safely shortened in
270 static bool isShortenableAtTheEnd(Instruction
*I
) {
271 // Don't shorten stores for now
272 if (isa
<StoreInst
>(I
))
275 if (IntrinsicInst
*II
= dyn_cast
<IntrinsicInst
>(I
)) {
276 switch (II
->getIntrinsicID()) {
277 default: return false;
278 case Intrinsic::memset
:
279 case Intrinsic::memcpy
:
280 case Intrinsic::memcpy_element_unordered_atomic
:
281 case Intrinsic::memset_element_unordered_atomic
:
282 // Do shorten memory intrinsics.
283 // FIXME: Add memmove if it's also safe to transform.
288 // Don't shorten libcalls calls for now.
293 /// Returns true if the beginning of this instruction can be safely shortened
295 static bool isShortenableAtTheBeginning(Instruction
*I
) {
296 // FIXME: Handle only memset for now. Supporting memcpy/memmove should be
297 // easily done by offsetting the source address.
298 return isa
<AnyMemSetInst
>(I
);
301 /// Return the pointer that is being written to.
302 static Value
*getStoredPointerOperand(Instruction
*I
) {
303 //TODO: factor this to reuse getLocForWrite
304 MemoryLocation Loc
= getLocForWrite(I
);
306 "unable to find pointer written for analyzable instruction?");
307 // TODO: most APIs don't expect const Value *
308 return const_cast<Value
*>(Loc
.Ptr
);
311 static uint64_t getPointerSize(const Value
*V
, const DataLayout
&DL
,
312 const TargetLibraryInfo
&TLI
,
316 Opts
.NullIsUnknownSize
= NullPointerIsDefined(F
);
318 if (getObjectSize(V
, Size
, DL
, &TLI
, Opts
))
320 return MemoryLocation::UnknownSize
;
325 enum OverwriteResult
{
329 OW_PartialEarlierWithFullLater
,
333 } // end anonymous namespace
335 /// Return 'OW_Complete' if a store to the 'Later' location completely
336 /// overwrites a store to the 'Earlier' location, 'OW_End' if the end of the
337 /// 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the
338 /// beginning of the 'Earlier' location is overwritten by 'Later'.
339 /// 'OW_PartialEarlierWithFullLater' means that an earlier (big) store was
340 /// overwritten by a latter (smaller) store which doesn't write outside the big
341 /// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.
342 static OverwriteResult
isOverwrite(const MemoryLocation
&Later
,
343 const MemoryLocation
&Earlier
,
344 const DataLayout
&DL
,
345 const TargetLibraryInfo
&TLI
,
346 int64_t &EarlierOff
, int64_t &LaterOff
,
347 Instruction
*DepWrite
,
348 InstOverlapIntervalsTy
&IOL
,
351 // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
352 // get imprecise values here, though (except for unknown sizes).
353 if (!Later
.Size
.isPrecise() || !Earlier
.Size
.isPrecise())
356 const uint64_t LaterSize
= Later
.Size
.getValue();
357 const uint64_t EarlierSize
= Earlier
.Size
.getValue();
359 const Value
*P1
= Earlier
.Ptr
->stripPointerCasts();
360 const Value
*P2
= Later
.Ptr
->stripPointerCasts();
362 // If the start pointers are the same, we just have to compare sizes to see if
363 // the later store was larger than the earlier store.
364 if (P1
== P2
|| AA
.isMustAlias(P1
, P2
)) {
365 // Make sure that the Later size is >= the Earlier size.
366 if (LaterSize
>= EarlierSize
)
370 // Check to see if the later store is to the entire object (either a global,
371 // an alloca, or a byval/inalloca argument). If so, then it clearly
372 // overwrites any other store to the same object.
373 const Value
*UO1
= GetUnderlyingObject(P1
, DL
),
374 *UO2
= GetUnderlyingObject(P2
, DL
);
376 // If we can't resolve the same pointers to the same object, then we can't
377 // analyze them at all.
381 // If the "Later" store is to a recognizable object, get its size.
382 uint64_t ObjectSize
= getPointerSize(UO2
, DL
, TLI
, F
);
383 if (ObjectSize
!= MemoryLocation::UnknownSize
)
384 if (ObjectSize
== LaterSize
&& ObjectSize
>= EarlierSize
)
387 // Okay, we have stores to two completely different pointers. Try to
388 // decompose the pointer into a "base + constant_offset" form. If the base
389 // pointers are equal, then we can reason about the two stores.
392 const Value
*BP1
= GetPointerBaseWithConstantOffset(P1
, EarlierOff
, DL
);
393 const Value
*BP2
= GetPointerBaseWithConstantOffset(P2
, LaterOff
, DL
);
395 // If the base pointers still differ, we have two completely different stores.
399 // The later store completely overlaps the earlier store if:
401 // 1. Both start at the same offset and the later one's size is greater than
402 // or equal to the earlier one's, or
407 // 2. The earlier store has an offset greater than the later offset, but which
408 // still lies completely within the later store.
411 // |----- later ------|
413 // We have to be careful here as *Off is signed while *.Size is unsigned.
414 if (EarlierOff
>= LaterOff
&&
415 LaterSize
>= EarlierSize
&&
416 uint64_t(EarlierOff
- LaterOff
) + EarlierSize
<= LaterSize
)
419 // We may now overlap, although the overlap is not complete. There might also
420 // be other incomplete overlaps, and together, they might cover the complete
422 // Note: The correctness of this logic depends on the fact that this function
423 // is not even called providing DepWrite when there are any intervening reads.
424 if (EnablePartialOverwriteTracking
&&
425 LaterOff
< int64_t(EarlierOff
+ EarlierSize
) &&
426 int64_t(LaterOff
+ LaterSize
) >= EarlierOff
) {
428 // Insert our part of the overlap into the map.
429 auto &IM
= IOL
[DepWrite
];
430 LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: Earlier [" << EarlierOff
431 << ", " << int64_t(EarlierOff
+ EarlierSize
)
432 << ") Later [" << LaterOff
<< ", "
433 << int64_t(LaterOff
+ LaterSize
) << ")\n");
435 // Make sure that we only insert non-overlapping intervals and combine
436 // adjacent intervals. The intervals are stored in the map with the ending
437 // offset as the key (in the half-open sense) and the starting offset as
439 int64_t LaterIntStart
= LaterOff
, LaterIntEnd
= LaterOff
+ LaterSize
;
441 // Find any intervals ending at, or after, LaterIntStart which start
442 // before LaterIntEnd.
443 auto ILI
= IM
.lower_bound(LaterIntStart
);
444 if (ILI
!= IM
.end() && ILI
->second
<= LaterIntEnd
) {
445 // This existing interval is overlapped with the current store somewhere
446 // in [LaterIntStart, LaterIntEnd]. Merge them by erasing the existing
447 // intervals and adjusting our start and end.
448 LaterIntStart
= std::min(LaterIntStart
, ILI
->second
);
449 LaterIntEnd
= std::max(LaterIntEnd
, ILI
->first
);
452 // Continue erasing and adjusting our end in case other previous
453 // intervals are also overlapped with the current store.
455 // |--- ealier 1 ---| |--- ealier 2 ---|
456 // |------- later---------|
458 while (ILI
!= IM
.end() && ILI
->second
<= LaterIntEnd
) {
459 assert(ILI
->second
> LaterIntStart
&& "Unexpected interval");
460 LaterIntEnd
= std::max(LaterIntEnd
, ILI
->first
);
465 IM
[LaterIntEnd
] = LaterIntStart
;
468 if (ILI
->second
<= EarlierOff
&&
469 ILI
->first
>= int64_t(EarlierOff
+ EarlierSize
)) {
470 LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: Earlier ["
471 << EarlierOff
<< ", "
472 << int64_t(EarlierOff
+ EarlierSize
)
473 << ") Composite Later [" << ILI
->second
<< ", "
474 << ILI
->first
<< ")\n");
475 ++NumCompletePartials
;
480 // Check for an earlier store which writes to all the memory locations that
481 // the later store writes to.
482 if (EnablePartialStoreMerging
&& LaterOff
>= EarlierOff
&&
483 int64_t(EarlierOff
+ EarlierSize
) > LaterOff
&&
484 uint64_t(LaterOff
- EarlierOff
) + LaterSize
<= EarlierSize
) {
485 LLVM_DEBUG(dbgs() << "DSE: Partial overwrite an earlier load ["
486 << EarlierOff
<< ", "
487 << int64_t(EarlierOff
+ EarlierSize
)
488 << ") by a later store [" << LaterOff
<< ", "
489 << int64_t(LaterOff
+ LaterSize
) << ")\n");
490 // TODO: Maybe come up with a better name?
491 return OW_PartialEarlierWithFullLater
;
494 // Another interesting case is if the later store overwrites the end of the
500 // In this case we may want to trim the size of earlier to avoid generating
501 // writes to addresses which will definitely be overwritten later
502 if (!EnablePartialOverwriteTracking
&&
503 (LaterOff
> EarlierOff
&& LaterOff
< int64_t(EarlierOff
+ EarlierSize
) &&
504 int64_t(LaterOff
+ LaterSize
) >= int64_t(EarlierOff
+ EarlierSize
)))
507 // Finally, we also need to check if the later store overwrites the beginning
508 // of the earlier store.
513 // In this case we may want to move the destination address and trim the size
514 // of earlier to avoid generating writes to addresses which will definitely
515 // be overwritten later.
516 if (!EnablePartialOverwriteTracking
&&
517 (LaterOff
<= EarlierOff
&& int64_t(LaterOff
+ LaterSize
) > EarlierOff
)) {
518 assert(int64_t(LaterOff
+ LaterSize
) < int64_t(EarlierOff
+ EarlierSize
) &&
519 "Expect to be handled as OW_Complete");
522 // Otherwise, they don't completely overlap.
526 /// If 'Inst' might be a self read (i.e. a noop copy of a
527 /// memory region into an identical pointer) then it doesn't actually make its
528 /// input dead in the traditional sense. Consider this case:
533 /// In this case, the second store to A does not make the first store to A dead.
534 /// The usual situation isn't an explicit A<-A store like this (which can be
535 /// trivially removed) but a case where two pointers may alias.
537 /// This function detects when it is unsafe to remove a dependent instruction
538 /// because the DSE inducing instruction may be a self-read.
539 static bool isPossibleSelfRead(Instruction
*Inst
,
540 const MemoryLocation
&InstStoreLoc
,
541 Instruction
*DepWrite
,
542 const TargetLibraryInfo
&TLI
,
544 // Self reads can only happen for instructions that read memory. Get the
546 MemoryLocation InstReadLoc
= getLocForRead(Inst
, TLI
);
547 if (!InstReadLoc
.Ptr
)
548 return false; // Not a reading instruction.
550 // If the read and written loc obviously don't alias, it isn't a read.
551 if (AA
.isNoAlias(InstReadLoc
, InstStoreLoc
))
554 if (isa
<AnyMemCpyInst
>(Inst
)) {
555 // LLVM's memcpy overlap semantics are not fully fleshed out (see PR11763)
556 // but in practice memcpy(A <- B) either means that A and B are disjoint or
557 // are equal (i.e. there are not partial overlaps). Given that, if we have:
559 // memcpy/memmove(A <- B) // DepWrite
560 // memcpy(A <- B) // Inst
562 // with Inst reading/writing a >= size than DepWrite, we can reason as
565 // - If A == B then both the copies are no-ops, so the DepWrite can be
567 // - If A != B then A and B are disjoint locations in Inst. Since
568 // Inst.size >= DepWrite.size A and B are disjoint in DepWrite too.
569 // Therefore DepWrite can be removed.
570 MemoryLocation DepReadLoc
= getLocForRead(DepWrite
, TLI
);
572 if (DepReadLoc
.Ptr
&& AA
.isMustAlias(InstReadLoc
.Ptr
, DepReadLoc
.Ptr
))
576 // If DepWrite doesn't read memory or if we can't prove it is a must alias,
577 // then it can't be considered dead.
581 /// Returns true if the memory which is accessed by the second instruction is not
582 /// modified between the first and the second instruction.
583 /// Precondition: Second instruction must be dominated by the first
585 static bool memoryIsNotModifiedBetween(Instruction
*FirstI
,
586 Instruction
*SecondI
,
588 SmallVector
<BasicBlock
*, 16> WorkList
;
589 SmallPtrSet
<BasicBlock
*, 8> Visited
;
590 BasicBlock::iterator
FirstBBI(FirstI
);
592 BasicBlock::iterator
SecondBBI(SecondI
);
593 BasicBlock
*FirstBB
= FirstI
->getParent();
594 BasicBlock
*SecondBB
= SecondI
->getParent();
595 MemoryLocation MemLoc
= MemoryLocation::get(SecondI
);
597 // Start checking the store-block.
598 WorkList
.push_back(SecondBB
);
599 bool isFirstBlock
= true;
601 // Check all blocks going backward until we reach the load-block.
602 while (!WorkList
.empty()) {
603 BasicBlock
*B
= WorkList
.pop_back_val();
605 // Ignore instructions before LI if this is the FirstBB.
606 BasicBlock::iterator BI
= (B
== FirstBB
? FirstBBI
: B
->begin());
608 BasicBlock::iterator EI
;
610 // Ignore instructions after SI if this is the first visit of SecondBB.
611 assert(B
== SecondBB
&& "first block is not the store block");
613 isFirstBlock
= false;
615 // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
616 // In this case we also have to look at instructions after SI.
619 for (; BI
!= EI
; ++BI
) {
620 Instruction
*I
= &*BI
;
621 if (I
->mayWriteToMemory() && I
!= SecondI
)
622 if (isModSet(AA
->getModRefInfo(I
, MemLoc
)))
626 assert(B
!= &FirstBB
->getParent()->getEntryBlock() &&
627 "Should not hit the entry block because SI must be dominated by LI");
628 for (auto PredI
= pred_begin(B
), PE
= pred_end(B
); PredI
!= PE
; ++PredI
) {
629 if (!Visited
.insert(*PredI
).second
)
631 WorkList
.push_back(*PredI
);
638 /// Find all blocks that will unconditionally lead to the block BB and append
640 static void findUnconditionalPreds(SmallVectorImpl
<BasicBlock
*> &Blocks
,
641 BasicBlock
*BB
, DominatorTree
*DT
) {
642 for (pred_iterator I
= pred_begin(BB
), E
= pred_end(BB
); I
!= E
; ++I
) {
643 BasicBlock
*Pred
= *I
;
644 if (Pred
== BB
) continue;
645 Instruction
*PredTI
= Pred
->getTerminator();
646 if (PredTI
->getNumSuccessors() != 1)
649 if (DT
->isReachableFromEntry(Pred
))
650 Blocks
.push_back(Pred
);
654 /// Handle frees of entire structures whose dependency is a store
655 /// to a field of that structure.
656 static bool handleFree(CallInst
*F
, AliasAnalysis
*AA
,
657 MemoryDependenceResults
*MD
, DominatorTree
*DT
,
658 const TargetLibraryInfo
*TLI
,
659 InstOverlapIntervalsTy
&IOL
, OrderedBasicBlock
&OBB
) {
660 bool MadeChange
= false;
662 MemoryLocation Loc
= MemoryLocation(F
->getOperand(0));
663 SmallVector
<BasicBlock
*, 16> Blocks
;
664 Blocks
.push_back(F
->getParent());
665 const DataLayout
&DL
= F
->getModule()->getDataLayout();
667 while (!Blocks
.empty()) {
668 BasicBlock
*BB
= Blocks
.pop_back_val();
669 Instruction
*InstPt
= BB
->getTerminator();
670 if (BB
== F
->getParent()) InstPt
= F
;
673 MD
->getPointerDependencyFrom(Loc
, false, InstPt
->getIterator(), BB
);
674 while (Dep
.isDef() || Dep
.isClobber()) {
675 Instruction
*Dependency
= Dep
.getInst();
676 if (!hasAnalyzableMemoryWrite(Dependency
, *TLI
) ||
677 !isRemovable(Dependency
))
681 GetUnderlyingObject(getStoredPointerOperand(Dependency
), DL
);
683 // Check for aliasing.
684 if (!AA
->isMustAlias(F
->getArgOperand(0), DepPointer
))
688 dbgs() << "DSE: Dead Store to soon to be freed memory:\n DEAD: "
689 << *Dependency
<< '\n');
691 // DCE instructions only used to calculate that store.
692 BasicBlock::iterator
BBI(Dependency
);
693 deleteDeadInstruction(Dependency
, &BBI
, *MD
, *TLI
, IOL
, OBB
);
697 // Inst's old Dependency is now deleted. Compute the next dependency,
698 // which may also be dead, as in
700 // s[1] = 0; // This has just been deleted.
702 Dep
= MD
->getPointerDependencyFrom(Loc
, false, BBI
, BB
);
705 if (Dep
.isNonLocal())
706 findUnconditionalPreds(Blocks
, BB
, DT
);
712 /// Check to see if the specified location may alias any of the stack objects in
713 /// the DeadStackObjects set. If so, they become live because the location is
715 static void removeAccessedObjects(const MemoryLocation
&LoadedLoc
,
716 SmallSetVector
<const Value
*, 16> &DeadStackObjects
,
717 const DataLayout
&DL
, AliasAnalysis
*AA
,
718 const TargetLibraryInfo
*TLI
,
720 const Value
*UnderlyingPointer
= GetUnderlyingObject(LoadedLoc
.Ptr
, DL
);
722 // A constant can't be in the dead pointer set.
723 if (isa
<Constant
>(UnderlyingPointer
))
726 // If the kill pointer can be easily reduced to an alloca, don't bother doing
727 // extraneous AA queries.
728 if (isa
<AllocaInst
>(UnderlyingPointer
) || isa
<Argument
>(UnderlyingPointer
)) {
729 DeadStackObjects
.remove(UnderlyingPointer
);
733 // Remove objects that could alias LoadedLoc.
734 DeadStackObjects
.remove_if([&](const Value
*I
) {
735 // See if the loaded location could alias the stack location.
736 MemoryLocation
StackLoc(I
, getPointerSize(I
, DL
, *TLI
, F
));
737 return !AA
->isNoAlias(StackLoc
, LoadedLoc
);
741 /// Remove dead stores to stack-allocated locations in the function end block.
745 /// store i32 1, i32* %A
747 static bool handleEndBlock(BasicBlock
&BB
, AliasAnalysis
*AA
,
748 MemoryDependenceResults
*MD
,
749 const TargetLibraryInfo
*TLI
,
750 InstOverlapIntervalsTy
&IOL
,
751 OrderedBasicBlock
&OBB
) {
752 bool MadeChange
= false;
754 // Keep track of all of the stack objects that are dead at the end of the
756 SmallSetVector
<const Value
*, 16> DeadStackObjects
;
758 // Find all of the alloca'd pointers in the entry block.
759 BasicBlock
&Entry
= BB
.getParent()->front();
760 for (Instruction
&I
: Entry
) {
761 if (isa
<AllocaInst
>(&I
))
762 DeadStackObjects
.insert(&I
);
764 // Okay, so these are dead heap objects, but if the pointer never escapes
765 // then it's leaked by this function anyways.
766 else if (isAllocLikeFn(&I
, TLI
) && !PointerMayBeCaptured(&I
, true, true))
767 DeadStackObjects
.insert(&I
);
770 // Treat byval or inalloca arguments the same, stores to them are dead at the
771 // end of the function.
772 for (Argument
&AI
: BB
.getParent()->args())
773 if (AI
.hasByValOrInAllocaAttr())
774 DeadStackObjects
.insert(&AI
);
776 const DataLayout
&DL
= BB
.getModule()->getDataLayout();
778 // Scan the basic block backwards
779 for (BasicBlock::iterator BBI
= BB
.end(); BBI
!= BB
.begin(); ){
782 // If we find a store, check to see if it points into a dead stack value.
783 if (hasAnalyzableMemoryWrite(&*BBI
, *TLI
) && isRemovable(&*BBI
)) {
784 // See through pointer-to-pointer bitcasts
785 SmallVector
<const Value
*, 4> Pointers
;
786 GetUnderlyingObjects(getStoredPointerOperand(&*BBI
), Pointers
, DL
);
788 // Stores to stack values are valid candidates for removal.
790 for (const Value
*Pointer
: Pointers
)
791 if (!DeadStackObjects
.count(Pointer
)) {
797 Instruction
*Dead
= &*BBI
;
799 LLVM_DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
800 << *Dead
<< "\n Objects: ";
801 for (SmallVectorImpl
<const Value
*>::iterator I
=
806 if (std::next(I
) != E
)
811 // DCE instructions only used to calculate that store.
812 deleteDeadInstruction(Dead
, &BBI
, *MD
, *TLI
, IOL
, OBB
,
820 // Remove any dead non-memory-mutating instructions.
821 if (isInstructionTriviallyDead(&*BBI
, TLI
)) {
822 LLVM_DEBUG(dbgs() << "DSE: Removing trivially dead instruction:\n DEAD: "
824 deleteDeadInstruction(&*BBI
, &BBI
, *MD
, *TLI
, IOL
, OBB
,
831 if (isa
<AllocaInst
>(BBI
)) {
832 // Remove allocas from the list of dead stack objects; there can't be
833 // any references before the definition.
834 DeadStackObjects
.remove(&*BBI
);
838 if (auto *Call
= dyn_cast
<CallBase
>(&*BBI
)) {
839 // Remove allocation function calls from the list of dead stack objects;
840 // there can't be any references before the definition.
841 if (isAllocLikeFn(&*BBI
, TLI
))
842 DeadStackObjects
.remove(&*BBI
);
844 // If this call does not access memory, it can't be loading any of our
846 if (AA
->doesNotAccessMemory(Call
))
849 // If the call might load from any of our allocas, then any store above
851 DeadStackObjects
.remove_if([&](const Value
*I
) {
852 // See if the call site touches the value.
853 return isRefSet(AA
->getModRefInfo(
854 Call
, I
, getPointerSize(I
, DL
, *TLI
, BB
.getParent())));
857 // If all of the allocas were clobbered by the call then we're not going
858 // to find anything else to process.
859 if (DeadStackObjects
.empty())
865 // We can remove the dead stores, irrespective of the fence and its ordering
866 // (release/acquire/seq_cst). Fences only constraints the ordering of
867 // already visible stores, it does not make a store visible to other
868 // threads. So, skipping over a fence does not change a store from being
870 if (isa
<FenceInst
>(*BBI
))
873 MemoryLocation LoadedLoc
;
875 // If we encounter a use of the pointer, it is no longer considered dead
876 if (LoadInst
*L
= dyn_cast
<LoadInst
>(BBI
)) {
877 if (!L
->isUnordered()) // Be conservative with atomic/volatile load
879 LoadedLoc
= MemoryLocation::get(L
);
880 } else if (VAArgInst
*V
= dyn_cast
<VAArgInst
>(BBI
)) {
881 LoadedLoc
= MemoryLocation::get(V
);
882 } else if (!BBI
->mayReadFromMemory()) {
883 // Instruction doesn't read memory. Note that stores that weren't removed
884 // above will hit this case.
887 // Unknown inst; assume it clobbers everything.
891 // Remove any allocas from the DeadPointer set that are loaded, as this
892 // makes any stores above the access live.
893 removeAccessedObjects(LoadedLoc
, DeadStackObjects
, DL
, AA
, TLI
, BB
.getParent());
895 // If all of the allocas were clobbered by the access then we're not going
896 // to find anything else to process.
897 if (DeadStackObjects
.empty())
904 static bool tryToShorten(Instruction
*EarlierWrite
, int64_t &EarlierOffset
,
905 int64_t &EarlierSize
, int64_t LaterOffset
,
906 int64_t LaterSize
, bool IsOverwriteEnd
) {
907 // TODO: base this on the target vector size so that if the earlier
908 // store was too small to get vector writes anyway then its likely
909 // a good idea to shorten it
910 // Power of 2 vector writes are probably always a bad idea to optimize
911 // as any store/memset/memcpy is likely using vector instructions so
912 // shortening it to not vector size is likely to be slower
913 auto *EarlierIntrinsic
= cast
<AnyMemIntrinsic
>(EarlierWrite
);
914 unsigned EarlierWriteAlign
= EarlierIntrinsic
->getDestAlignment();
916 LaterOffset
= int64_t(LaterOffset
+ LaterSize
);
918 if (!(isPowerOf2_64(LaterOffset
) && EarlierWriteAlign
<= LaterOffset
) &&
919 !((EarlierWriteAlign
!= 0) && LaterOffset
% EarlierWriteAlign
== 0))
922 int64_t NewLength
= IsOverwriteEnd
923 ? LaterOffset
- EarlierOffset
924 : EarlierSize
- (LaterOffset
- EarlierOffset
);
926 if (auto *AMI
= dyn_cast
<AtomicMemIntrinsic
>(EarlierWrite
)) {
927 // When shortening an atomic memory intrinsic, the newly shortened
928 // length must remain an integer multiple of the element size.
929 const uint32_t ElementSize
= AMI
->getElementSizeInBytes();
930 if (0 != NewLength
% ElementSize
)
934 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW "
935 << (IsOverwriteEnd
? "END" : "BEGIN") << ": "
936 << *EarlierWrite
<< "\n KILLER (offset " << LaterOffset
937 << ", " << EarlierSize
<< ")\n");
939 Value
*EarlierWriteLength
= EarlierIntrinsic
->getLength();
940 Value
*TrimmedLength
=
941 ConstantInt::get(EarlierWriteLength
->getType(), NewLength
);
942 EarlierIntrinsic
->setLength(TrimmedLength
);
944 EarlierSize
= NewLength
;
945 if (!IsOverwriteEnd
) {
946 int64_t OffsetMoved
= (LaterOffset
- EarlierOffset
);
947 Value
*Indices
[1] = {
948 ConstantInt::get(EarlierWriteLength
->getType(), OffsetMoved
)};
949 GetElementPtrInst
*NewDestGEP
= GetElementPtrInst::CreateInBounds(
950 EarlierIntrinsic
->getRawDest()->getType()->getPointerElementType(),
951 EarlierIntrinsic
->getRawDest(), Indices
, "", EarlierWrite
);
952 NewDestGEP
->setDebugLoc(EarlierIntrinsic
->getDebugLoc());
953 EarlierIntrinsic
->setDest(NewDestGEP
);
954 EarlierOffset
= EarlierOffset
+ OffsetMoved
;
959 static bool tryToShortenEnd(Instruction
*EarlierWrite
,
960 OverlapIntervalsTy
&IntervalMap
,
961 int64_t &EarlierStart
, int64_t &EarlierSize
) {
962 if (IntervalMap
.empty() || !isShortenableAtTheEnd(EarlierWrite
))
965 OverlapIntervalsTy::iterator OII
= --IntervalMap
.end();
966 int64_t LaterStart
= OII
->second
;
967 int64_t LaterSize
= OII
->first
- LaterStart
;
969 if (LaterStart
> EarlierStart
&& LaterStart
< EarlierStart
+ EarlierSize
&&
970 LaterStart
+ LaterSize
>= EarlierStart
+ EarlierSize
) {
971 if (tryToShorten(EarlierWrite
, EarlierStart
, EarlierSize
, LaterStart
,
973 IntervalMap
.erase(OII
);
980 static bool tryToShortenBegin(Instruction
*EarlierWrite
,
981 OverlapIntervalsTy
&IntervalMap
,
982 int64_t &EarlierStart
, int64_t &EarlierSize
) {
983 if (IntervalMap
.empty() || !isShortenableAtTheBeginning(EarlierWrite
))
986 OverlapIntervalsTy::iterator OII
= IntervalMap
.begin();
987 int64_t LaterStart
= OII
->second
;
988 int64_t LaterSize
= OII
->first
- LaterStart
;
990 if (LaterStart
<= EarlierStart
&& LaterStart
+ LaterSize
> EarlierStart
) {
991 assert(LaterStart
+ LaterSize
< EarlierStart
+ EarlierSize
&&
992 "Should have been handled as OW_Complete");
993 if (tryToShorten(EarlierWrite
, EarlierStart
, EarlierSize
, LaterStart
,
995 IntervalMap
.erase(OII
);
1002 static bool removePartiallyOverlappedStores(AliasAnalysis
*AA
,
1003 const DataLayout
&DL
,
1004 InstOverlapIntervalsTy
&IOL
) {
1005 bool Changed
= false;
1006 for (auto OI
: IOL
) {
1007 Instruction
*EarlierWrite
= OI
.first
;
1008 MemoryLocation Loc
= getLocForWrite(EarlierWrite
);
1009 assert(isRemovable(EarlierWrite
) && "Expect only removable instruction");
1011 const Value
*Ptr
= Loc
.Ptr
->stripPointerCasts();
1012 int64_t EarlierStart
= 0;
1013 int64_t EarlierSize
= int64_t(Loc
.Size
.getValue());
1014 GetPointerBaseWithConstantOffset(Ptr
, EarlierStart
, DL
);
1015 OverlapIntervalsTy
&IntervalMap
= OI
.second
;
1017 tryToShortenEnd(EarlierWrite
, IntervalMap
, EarlierStart
, EarlierSize
);
1018 if (IntervalMap
.empty())
1021 tryToShortenBegin(EarlierWrite
, IntervalMap
, EarlierStart
, EarlierSize
);
1026 static bool eliminateNoopStore(Instruction
*Inst
, BasicBlock::iterator
&BBI
,
1027 AliasAnalysis
*AA
, MemoryDependenceResults
*MD
,
1028 const DataLayout
&DL
,
1029 const TargetLibraryInfo
*TLI
,
1030 InstOverlapIntervalsTy
&IOL
,
1031 OrderedBasicBlock
&OBB
) {
1032 // Must be a store instruction.
1033 StoreInst
*SI
= dyn_cast
<StoreInst
>(Inst
);
1037 // If we're storing the same value back to a pointer that we just loaded from,
1038 // then the store can be removed.
1039 if (LoadInst
*DepLoad
= dyn_cast
<LoadInst
>(SI
->getValueOperand())) {
1040 if (SI
->getPointerOperand() == DepLoad
->getPointerOperand() &&
1041 isRemovable(SI
) && memoryIsNotModifiedBetween(DepLoad
, SI
, AA
)) {
1044 dbgs() << "DSE: Remove Store Of Load from same pointer:\n LOAD: "
1045 << *DepLoad
<< "\n STORE: " << *SI
<< '\n');
1047 deleteDeadInstruction(SI
, &BBI
, *MD
, *TLI
, IOL
, OBB
);
1048 ++NumRedundantStores
;
1053 // Remove null stores into the calloc'ed objects
1054 Constant
*StoredConstant
= dyn_cast
<Constant
>(SI
->getValueOperand());
1055 if (StoredConstant
&& StoredConstant
->isNullValue() && isRemovable(SI
)) {
1056 Instruction
*UnderlyingPointer
=
1057 dyn_cast
<Instruction
>(GetUnderlyingObject(SI
->getPointerOperand(), DL
));
1059 if (UnderlyingPointer
&& isCallocLikeFn(UnderlyingPointer
, TLI
) &&
1060 memoryIsNotModifiedBetween(UnderlyingPointer
, SI
, AA
)) {
1062 dbgs() << "DSE: Remove null store to the calloc'ed object:\n DEAD: "
1063 << *Inst
<< "\n OBJECT: " << *UnderlyingPointer
<< '\n');
1065 deleteDeadInstruction(SI
, &BBI
, *MD
, *TLI
, IOL
, OBB
);
1066 ++NumRedundantStores
;
1073 static bool eliminateDeadStores(BasicBlock
&BB
, AliasAnalysis
*AA
,
1074 MemoryDependenceResults
*MD
, DominatorTree
*DT
,
1075 const TargetLibraryInfo
*TLI
) {
1076 const DataLayout
&DL
= BB
.getModule()->getDataLayout();
1077 bool MadeChange
= false;
1079 OrderedBasicBlock
OBB(&BB
);
1080 Instruction
*LastThrowing
= nullptr;
1082 // A map of interval maps representing partially-overwritten value parts.
1083 InstOverlapIntervalsTy IOL
;
1085 // Do a top-down walk on the BB.
1086 for (BasicBlock::iterator BBI
= BB
.begin(), BBE
= BB
.end(); BBI
!= BBE
; ) {
1087 // Handle 'free' calls specially.
1088 if (CallInst
*F
= isFreeCall(&*BBI
, TLI
)) {
1089 MadeChange
|= handleFree(F
, AA
, MD
, DT
, TLI
, IOL
, OBB
);
1090 // Increment BBI after handleFree has potentially deleted instructions.
1091 // This ensures we maintain a valid iterator.
1096 Instruction
*Inst
= &*BBI
++;
1098 if (Inst
->mayThrow()) {
1099 LastThrowing
= Inst
;
1103 // Check to see if Inst writes to memory. If not, continue.
1104 if (!hasAnalyzableMemoryWrite(Inst
, *TLI
))
1107 // eliminateNoopStore will update in iterator, if necessary.
1108 if (eliminateNoopStore(Inst
, BBI
, AA
, MD
, DL
, TLI
, IOL
, OBB
)) {
1113 // If we find something that writes memory, get its memory dependence.
1114 MemDepResult InstDep
= MD
->getDependency(Inst
, &OBB
);
1116 // Ignore any store where we can't find a local dependence.
1117 // FIXME: cross-block DSE would be fun. :)
1118 if (!InstDep
.isDef() && !InstDep
.isClobber())
1121 // Figure out what location is being stored to.
1122 MemoryLocation Loc
= getLocForWrite(Inst
);
1124 // If we didn't get a useful location, fail.
1128 // Loop until we find a store we can eliminate or a load that
1129 // invalidates the analysis. Without an upper bound on the number of
1130 // instructions examined, this analysis can become very time-consuming.
1131 // However, the potential gain diminishes as we process more instructions
1132 // without eliminating any of them. Therefore, we limit the number of
1133 // instructions we look at.
1134 auto Limit
= MD
->getDefaultBlockScanLimit();
1135 while (InstDep
.isDef() || InstDep
.isClobber()) {
1136 // Get the memory clobbered by the instruction we depend on. MemDep will
1137 // skip any instructions that 'Loc' clearly doesn't interact with. If we
1138 // end up depending on a may- or must-aliased load, then we can't optimize
1139 // away the store and we bail out. However, if we depend on something
1140 // that overwrites the memory location we *can* potentially optimize it.
1142 // Find out what memory location the dependent instruction stores.
1143 Instruction
*DepWrite
= InstDep
.getInst();
1144 if (!hasAnalyzableMemoryWrite(DepWrite
, *TLI
))
1146 MemoryLocation DepLoc
= getLocForWrite(DepWrite
);
1147 // If we didn't get a useful location, or if it isn't a size, bail out.
1151 // Make sure we don't look past a call which might throw. This is an
1152 // issue because MemoryDependenceAnalysis works in the wrong direction:
1153 // it finds instructions which dominate the current instruction, rather than
1154 // instructions which are post-dominated by the current instruction.
1156 // If the underlying object is a non-escaping memory allocation, any store
1157 // to it is dead along the unwind edge. Otherwise, we need to preserve
1159 if (LastThrowing
&& OBB
.dominates(DepWrite
, LastThrowing
)) {
1160 const Value
* Underlying
= GetUnderlyingObject(DepLoc
.Ptr
, DL
);
1161 bool IsStoreDeadOnUnwind
= isa
<AllocaInst
>(Underlying
);
1162 if (!IsStoreDeadOnUnwind
) {
1163 // We're looking for a call to an allocation function
1164 // where the allocation doesn't escape before the last
1165 // throwing instruction; PointerMayBeCaptured
1166 // reasonably fast approximation.
1167 IsStoreDeadOnUnwind
= isAllocLikeFn(Underlying
, TLI
) &&
1168 !PointerMayBeCaptured(Underlying
, false, true);
1170 if (!IsStoreDeadOnUnwind
)
1174 // If we find a write that is a) removable (i.e., non-volatile), b) is
1175 // completely obliterated by the store to 'Loc', and c) which we know that
1176 // 'Inst' doesn't load from, then we can remove it.
1177 // Also try to merge two stores if a later one only touches memory written
1178 // to by the earlier one.
1179 if (isRemovable(DepWrite
) &&
1180 !isPossibleSelfRead(Inst
, Loc
, DepWrite
, *TLI
, *AA
)) {
1181 int64_t InstWriteOffset
, DepWriteOffset
;
1182 OverwriteResult OR
= isOverwrite(Loc
, DepLoc
, DL
, *TLI
, DepWriteOffset
,
1183 InstWriteOffset
, DepWrite
, IOL
, *AA
,
1185 if (OR
== OW_Complete
) {
1186 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " << *DepWrite
1187 << "\n KILLER: " << *Inst
<< '\n');
1189 // Delete the store and now-dead instructions that feed it.
1190 deleteDeadInstruction(DepWrite
, &BBI
, *MD
, *TLI
, IOL
, OBB
);
1194 // We erased DepWrite; start over.
1195 InstDep
= MD
->getDependency(Inst
, &OBB
);
1197 } else if ((OR
== OW_End
&& isShortenableAtTheEnd(DepWrite
)) ||
1199 isShortenableAtTheBeginning(DepWrite
)))) {
1200 assert(!EnablePartialOverwriteTracking
&& "Do not expect to perform "
1201 "when partial-overwrite "
1202 "tracking is enabled");
1203 // The overwrite result is known, so these must be known, too.
1204 int64_t EarlierSize
= DepLoc
.Size
.getValue();
1205 int64_t LaterSize
= Loc
.Size
.getValue();
1206 bool IsOverwriteEnd
= (OR
== OW_End
);
1207 MadeChange
|= tryToShorten(DepWrite
, DepWriteOffset
, EarlierSize
,
1208 InstWriteOffset
, LaterSize
, IsOverwriteEnd
);
1209 } else if (EnablePartialStoreMerging
&&
1210 OR
== OW_PartialEarlierWithFullLater
) {
1211 auto *Earlier
= dyn_cast
<StoreInst
>(DepWrite
);
1212 auto *Later
= dyn_cast
<StoreInst
>(Inst
);
1213 if (Earlier
&& isa
<ConstantInt
>(Earlier
->getValueOperand()) &&
1214 DL
.typeSizeEqualsStoreSize(
1215 Earlier
->getValueOperand()->getType()) &&
1216 Later
&& isa
<ConstantInt
>(Later
->getValueOperand()) &&
1217 DL
.typeSizeEqualsStoreSize(
1218 Later
->getValueOperand()->getType()) &&
1219 memoryIsNotModifiedBetween(Earlier
, Later
, AA
)) {
1220 // If the store we find is:
1221 // a) partially overwritten by the store to 'Loc'
1222 // b) the later store is fully contained in the earlier one and
1223 // c) they both have a constant value
1224 // d) none of the two stores need padding
1225 // Merge the two stores, replacing the earlier store's value with a
1226 // merge of both values.
1227 // TODO: Deal with other constant types (vectors, etc), and probably
1228 // some mem intrinsics (if needed)
1230 APInt EarlierValue
=
1231 cast
<ConstantInt
>(Earlier
->getValueOperand())->getValue();
1233 cast
<ConstantInt
>(Later
->getValueOperand())->getValue();
1234 unsigned LaterBits
= LaterValue
.getBitWidth();
1235 assert(EarlierValue
.getBitWidth() > LaterValue
.getBitWidth());
1236 LaterValue
= LaterValue
.zext(EarlierValue
.getBitWidth());
1238 // Offset of the smaller store inside the larger store
1239 unsigned BitOffsetDiff
= (InstWriteOffset
- DepWriteOffset
) * 8;
1240 unsigned LShiftAmount
=
1242 ? EarlierValue
.getBitWidth() - BitOffsetDiff
- LaterBits
1245 APInt::getBitsSet(EarlierValue
.getBitWidth(), LShiftAmount
,
1246 LShiftAmount
+ LaterBits
);
1247 // Clear the bits we'll be replacing, then OR with the smaller
1248 // store, shifted appropriately.
1250 (EarlierValue
& ~Mask
) | (LaterValue
<< LShiftAmount
);
1251 LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n Earlier: " << *DepWrite
1252 << "\n Later: " << *Inst
1253 << "\n Merged Value: " << Merged
<< '\n');
1255 auto *SI
= new StoreInst(
1256 ConstantInt::get(Earlier
->getValueOperand()->getType(), Merged
),
1257 Earlier
->getPointerOperand(), false,
1258 MaybeAlign(Earlier
->getAlignment()), Earlier
->getOrdering(),
1259 Earlier
->getSyncScopeID(), DepWrite
);
1261 unsigned MDToKeep
[] = {LLVMContext::MD_dbg
, LLVMContext::MD_tbaa
,
1262 LLVMContext::MD_alias_scope
,
1263 LLVMContext::MD_noalias
,
1264 LLVMContext::MD_nontemporal
};
1265 SI
->copyMetadata(*DepWrite
, MDToKeep
);
1266 ++NumModifiedStores
;
1268 // Remove earlier, wider, store
1269 OBB
.replaceInstruction(DepWrite
, SI
);
1271 // Delete the old stores and now-dead instructions that feed them.
1272 deleteDeadInstruction(Inst
, &BBI
, *MD
, *TLI
, IOL
, OBB
);
1273 deleteDeadInstruction(DepWrite
, &BBI
, *MD
, *TLI
, IOL
, OBB
);
1276 // We erased DepWrite and Inst (Loc); start over.
1282 // If this is a may-aliased store that is clobbering the store value, we
1283 // can keep searching past it for another must-aliased pointer that stores
1284 // to the same location. For example, in:
1288 // we can remove the first store to P even though we don't know if P and Q
1290 if (DepWrite
== &BB
.front()) break;
1292 // Can't look past this instruction if it might read 'Loc'.
1293 if (isRefSet(AA
->getModRefInfo(DepWrite
, Loc
)))
1296 InstDep
= MD
->getPointerDependencyFrom(Loc
, /*isLoad=*/ false,
1297 DepWrite
->getIterator(), &BB
,
1298 /*QueryInst=*/ nullptr, &Limit
);
1302 if (EnablePartialOverwriteTracking
)
1303 MadeChange
|= removePartiallyOverlappedStores(AA
, DL
, IOL
);
1305 // If this block ends in a return, unwind, or unreachable, all allocas are
1306 // dead at its end, which means stores to them are also dead.
1307 if (BB
.getTerminator()->getNumSuccessors() == 0)
1308 MadeChange
|= handleEndBlock(BB
, AA
, MD
, TLI
, IOL
, OBB
);
1313 static bool eliminateDeadStores(Function
&F
, AliasAnalysis
*AA
,
1314 MemoryDependenceResults
*MD
, DominatorTree
*DT
,
1315 const TargetLibraryInfo
*TLI
) {
1316 bool MadeChange
= false;
1317 for (BasicBlock
&BB
: F
)
1318 // Only check non-dead blocks. Dead blocks may have strange pointer
1319 // cycles that will confuse alias analysis.
1320 if (DT
->isReachableFromEntry(&BB
))
1321 MadeChange
|= eliminateDeadStores(BB
, AA
, MD
, DT
, TLI
);
1326 //===----------------------------------------------------------------------===//
1328 //===----------------------------------------------------------------------===//
1329 PreservedAnalyses
DSEPass::run(Function
&F
, FunctionAnalysisManager
&AM
) {
1330 AliasAnalysis
*AA
= &AM
.getResult
<AAManager
>(F
);
1331 DominatorTree
*DT
= &AM
.getResult
<DominatorTreeAnalysis
>(F
);
1332 MemoryDependenceResults
*MD
= &AM
.getResult
<MemoryDependenceAnalysis
>(F
);
1333 const TargetLibraryInfo
*TLI
= &AM
.getResult
<TargetLibraryAnalysis
>(F
);
1335 if (!eliminateDeadStores(F
, AA
, MD
, DT
, TLI
))
1336 return PreservedAnalyses::all();
1338 PreservedAnalyses PA
;
1339 PA
.preserveSet
<CFGAnalyses
>();
1340 PA
.preserve
<GlobalsAA
>();
1341 PA
.preserve
<MemoryDependenceAnalysis
>();
1347 /// A legacy pass for the legacy pass manager that wraps \c DSEPass.
1348 class DSELegacyPass
: public FunctionPass
{
1350 static char ID
; // Pass identification, replacement for typeid
1352 DSELegacyPass() : FunctionPass(ID
) {
1353 initializeDSELegacyPassPass(*PassRegistry::getPassRegistry());
1356 bool runOnFunction(Function
&F
) override
{
1357 if (skipFunction(F
))
1360 DominatorTree
*DT
= &getAnalysis
<DominatorTreeWrapperPass
>().getDomTree();
1361 AliasAnalysis
*AA
= &getAnalysis
<AAResultsWrapperPass
>().getAAResults();
1362 MemoryDependenceResults
*MD
=
1363 &getAnalysis
<MemoryDependenceWrapperPass
>().getMemDep();
1364 const TargetLibraryInfo
*TLI
=
1365 &getAnalysis
<TargetLibraryInfoWrapperPass
>().getTLI(F
);
1367 return eliminateDeadStores(F
, AA
, MD
, DT
, TLI
);
1370 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
1371 AU
.setPreservesCFG();
1372 AU
.addRequired
<DominatorTreeWrapperPass
>();
1373 AU
.addRequired
<AAResultsWrapperPass
>();
1374 AU
.addRequired
<MemoryDependenceWrapperPass
>();
1375 AU
.addRequired
<TargetLibraryInfoWrapperPass
>();
1376 AU
.addPreserved
<DominatorTreeWrapperPass
>();
1377 AU
.addPreserved
<GlobalsAAWrapperPass
>();
1378 AU
.addPreserved
<MemoryDependenceWrapperPass
>();
1382 } // end anonymous namespace
1384 char DSELegacyPass::ID
= 0;
1386 INITIALIZE_PASS_BEGIN(DSELegacyPass
, "dse", "Dead Store Elimination", false,
1388 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass
)
1389 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass
)
1390 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass
)
1391 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass
)
1392 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass
)
1393 INITIALIZE_PASS_END(DSELegacyPass
, "dse", "Dead Store Elimination", false,
1396 FunctionPass
*llvm::createDeadStoreEliminationPass() {
1397 return new DSELegacyPass();