xref: /freebsd-src/contrib/llvm-project/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
1fe6060f1SDimitry Andric //===- DeadStoreElimination.cpp - MemorySSA Backed Dead Store Elimination -===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
9fe6060f1SDimitry Andric // The code below implements dead store elimination using MemorySSA. It uses
10fe6060f1SDimitry Andric // the following general approach: given a MemoryDef, walk upwards to find
11fe6060f1SDimitry Andric // clobbering MemoryDefs that may be killed by the starting def. Then check
12fe6060f1SDimitry Andric // that there are no uses that may read the location of the original MemoryDef
13fe6060f1SDimitry Andric // in between both MemoryDefs. A bit more concretely:
140b57cec5SDimitry Andric //
15fe6060f1SDimitry Andric // For all MemoryDefs StartDef:
16349cc55cSDimitry Andric // 1. Get the next dominating clobbering MemoryDef (MaybeDeadAccess) by walking
17fe6060f1SDimitry Andric //    upwards.
18349cc55cSDimitry Andric // 2. Check that there are no reads between MaybeDeadAccess and the StartDef by
19349cc55cSDimitry Andric //    checking all uses starting at MaybeDeadAccess and walking until we see
20fe6060f1SDimitry Andric //    StartDef.
21fe6060f1SDimitry Andric // 3. For each found CurrentDef, check that:
22fe6060f1SDimitry Andric //   1. There are no barrier instructions between CurrentDef and StartDef (like
23fe6060f1SDimitry Andric //       throws or stores with ordering constraints).
24fe6060f1SDimitry Andric //   2. StartDef is executed whenever CurrentDef is executed.
25fe6060f1SDimitry Andric //   3. StartDef completely overwrites CurrentDef.
26fe6060f1SDimitry Andric // 4. Erase CurrentDef from the function and MemorySSA.
270b57cec5SDimitry Andric //
280b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
290b57cec5SDimitry Andric 
300b57cec5SDimitry Andric #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
310b57cec5SDimitry Andric #include "llvm/ADT/APInt.h"
320b57cec5SDimitry Andric #include "llvm/ADT/DenseMap.h"
33480093f4SDimitry Andric #include "llvm/ADT/MapVector.h"
345ffd83dbSDimitry Andric #include "llvm/ADT/PostOrderIterator.h"
350b57cec5SDimitry Andric #include "llvm/ADT/SetVector.h"
360b57cec5SDimitry Andric #include "llvm/ADT/SmallPtrSet.h"
370b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h"
380b57cec5SDimitry Andric #include "llvm/ADT/Statistic.h"
390b57cec5SDimitry Andric #include "llvm/ADT/StringRef.h"
400b57cec5SDimitry Andric #include "llvm/Analysis/AliasAnalysis.h"
410b57cec5SDimitry Andric #include "llvm/Analysis/CaptureTracking.h"
420b57cec5SDimitry Andric #include "llvm/Analysis/GlobalsModRef.h"
43fe6060f1SDimitry Andric #include "llvm/Analysis/LoopInfo.h"
440b57cec5SDimitry Andric #include "llvm/Analysis/MemoryBuiltins.h"
450b57cec5SDimitry Andric #include "llvm/Analysis/MemoryLocation.h"
465ffd83dbSDimitry Andric #include "llvm/Analysis/MemorySSA.h"
475ffd83dbSDimitry Andric #include "llvm/Analysis/MemorySSAUpdater.h"
48fe6060f1SDimitry Andric #include "llvm/Analysis/MustExecute.h"
495ffd83dbSDimitry Andric #include "llvm/Analysis/PostDominators.h"
500b57cec5SDimitry Andric #include "llvm/Analysis/TargetLibraryInfo.h"
510b57cec5SDimitry Andric #include "llvm/Analysis/ValueTracking.h"
520b57cec5SDimitry Andric #include "llvm/IR/Argument.h"
530b57cec5SDimitry Andric #include "llvm/IR/BasicBlock.h"
540b57cec5SDimitry Andric #include "llvm/IR/Constant.h"
550b57cec5SDimitry Andric #include "llvm/IR/Constants.h"
560b57cec5SDimitry Andric #include "llvm/IR/DataLayout.h"
57bdd1243dSDimitry Andric #include "llvm/IR/DebugInfo.h"
580b57cec5SDimitry Andric #include "llvm/IR/Dominators.h"
590b57cec5SDimitry Andric #include "llvm/IR/Function.h"
60349cc55cSDimitry Andric #include "llvm/IR/IRBuilder.h"
615ffd83dbSDimitry Andric #include "llvm/IR/InstIterator.h"
620b57cec5SDimitry Andric #include "llvm/IR/InstrTypes.h"
630b57cec5SDimitry Andric #include "llvm/IR/Instruction.h"
640b57cec5SDimitry Andric #include "llvm/IR/Instructions.h"
650b57cec5SDimitry Andric #include "llvm/IR/IntrinsicInst.h"
660b57cec5SDimitry Andric #include "llvm/IR/Module.h"
670b57cec5SDimitry Andric #include "llvm/IR/PassManager.h"
685ffd83dbSDimitry Andric #include "llvm/IR/PatternMatch.h"
690b57cec5SDimitry Andric #include "llvm/IR/Value.h"
700b57cec5SDimitry Andric #include "llvm/Support/Casting.h"
710b57cec5SDimitry Andric #include "llvm/Support/CommandLine.h"
720b57cec5SDimitry Andric #include "llvm/Support/Debug.h"
735ffd83dbSDimitry Andric #include "llvm/Support/DebugCounter.h"
740b57cec5SDimitry Andric #include "llvm/Support/ErrorHandling.h"
750b57cec5SDimitry Andric #include "llvm/Support/raw_ostream.h"
765ffd83dbSDimitry Andric #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
77349cc55cSDimitry Andric #include "llvm/Transforms/Utils/BuildLibCalls.h"
780b57cec5SDimitry Andric #include "llvm/Transforms/Utils/Local.h"
790b57cec5SDimitry Andric #include <algorithm>
800b57cec5SDimitry Andric #include <cassert>
810b57cec5SDimitry Andric #include <cstdint>
820b57cec5SDimitry Andric #include <iterator>
830b57cec5SDimitry Andric #include <map>
84bdd1243dSDimitry Andric #include <optional>
850b57cec5SDimitry Andric #include <utility>
860b57cec5SDimitry Andric 
870b57cec5SDimitry Andric using namespace llvm;
885ffd83dbSDimitry Andric using namespace PatternMatch;
890b57cec5SDimitry Andric 
900b57cec5SDimitry Andric #define DEBUG_TYPE "dse"
910b57cec5SDimitry Andric 
925ffd83dbSDimitry Andric STATISTIC(NumRemainingStores, "Number of stores remaining after DSE");
930b57cec5SDimitry Andric STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
940b57cec5SDimitry Andric STATISTIC(NumFastStores, "Number of stores deleted");
950b57cec5SDimitry Andric STATISTIC(NumFastOther, "Number of other instrs removed");
960b57cec5SDimitry Andric STATISTIC(NumCompletePartials, "Number of stores dead by later partials");
970b57cec5SDimitry Andric STATISTIC(NumModifiedStores, "Number of stores modified");
985ffd83dbSDimitry Andric STATISTIC(NumCFGChecks, "Number of stores modified");
995ffd83dbSDimitry Andric STATISTIC(NumCFGTries, "Number of stores modified");
1005ffd83dbSDimitry Andric STATISTIC(NumCFGSuccess, "Number of stores modified");
101e8d8bef9SDimitry Andric STATISTIC(NumGetDomMemoryDefPassed,
102e8d8bef9SDimitry Andric           "Number of times a valid candidate is returned from getDomMemoryDef");
103e8d8bef9SDimitry Andric STATISTIC(NumDomMemDefChecks,
104e8d8bef9SDimitry Andric           "Number iterations check for reads in getDomMemoryDef");
1055ffd83dbSDimitry Andric 
1065ffd83dbSDimitry Andric DEBUG_COUNTER(MemorySSACounter, "dse-memoryssa",
1075ffd83dbSDimitry Andric               "Controls which MemoryDefs are eliminated.");
1080b57cec5SDimitry Andric 
1090b57cec5SDimitry Andric static cl::opt<bool>
1100b57cec5SDimitry Andric EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",
1110b57cec5SDimitry Andric   cl::init(true), cl::Hidden,
1120b57cec5SDimitry Andric   cl::desc("Enable partial-overwrite tracking in DSE"));
1130b57cec5SDimitry Andric 
1140b57cec5SDimitry Andric static cl::opt<bool>
1150b57cec5SDimitry Andric EnablePartialStoreMerging("enable-dse-partial-store-merging",
1160b57cec5SDimitry Andric   cl::init(true), cl::Hidden,
1170b57cec5SDimitry Andric   cl::desc("Enable partial store merging in DSE"));
1180b57cec5SDimitry Andric 
1195ffd83dbSDimitry Andric static cl::opt<unsigned>
120e8d8bef9SDimitry Andric     MemorySSAScanLimit("dse-memoryssa-scanlimit", cl::init(150), cl::Hidden,
1215ffd83dbSDimitry Andric                        cl::desc("The number of memory instructions to scan for "
122349cc55cSDimitry Andric                                 "dead store elimination (default = 150)"));
123e8d8bef9SDimitry Andric static cl::opt<unsigned> MemorySSAUpwardsStepLimit(
124e8d8bef9SDimitry Andric     "dse-memoryssa-walklimit", cl::init(90), cl::Hidden,
125e8d8bef9SDimitry Andric     cl::desc("The maximum number of steps while walking upwards to find "
126e8d8bef9SDimitry Andric              "MemoryDefs that may be killed (default = 90)"));
127e8d8bef9SDimitry Andric 
128e8d8bef9SDimitry Andric static cl::opt<unsigned> MemorySSAPartialStoreLimit(
129e8d8bef9SDimitry Andric     "dse-memoryssa-partial-store-limit", cl::init(5), cl::Hidden,
130e8d8bef9SDimitry Andric     cl::desc("The maximum number candidates that only partially overwrite the "
131e8d8bef9SDimitry Andric              "killing MemoryDef to consider"
132e8d8bef9SDimitry Andric              " (default = 5)"));
1335ffd83dbSDimitry Andric 
1345ffd83dbSDimitry Andric static cl::opt<unsigned> MemorySSADefsPerBlockLimit(
1355ffd83dbSDimitry Andric     "dse-memoryssa-defs-per-block-limit", cl::init(5000), cl::Hidden,
1365ffd83dbSDimitry Andric     cl::desc("The number of MemoryDefs we consider as candidates to eliminated "
1375ffd83dbSDimitry Andric              "other stores per basic block (default = 5000)"));
1385ffd83dbSDimitry Andric 
139e8d8bef9SDimitry Andric static cl::opt<unsigned> MemorySSASameBBStepCost(
140e8d8bef9SDimitry Andric     "dse-memoryssa-samebb-cost", cl::init(1), cl::Hidden,
141e8d8bef9SDimitry Andric     cl::desc(
142e8d8bef9SDimitry Andric         "The cost of a step in the same basic block as the killing MemoryDef"
143e8d8bef9SDimitry Andric         "(default = 1)"));
144e8d8bef9SDimitry Andric 
145e8d8bef9SDimitry Andric static cl::opt<unsigned>
146e8d8bef9SDimitry Andric     MemorySSAOtherBBStepCost("dse-memoryssa-otherbb-cost", cl::init(5),
147e8d8bef9SDimitry Andric                              cl::Hidden,
148e8d8bef9SDimitry Andric                              cl::desc("The cost of a step in a different basic "
149e8d8bef9SDimitry Andric                                       "block than the killing MemoryDef"
150e8d8bef9SDimitry Andric                                       "(default = 5)"));
151e8d8bef9SDimitry Andric 
1525ffd83dbSDimitry Andric static cl::opt<unsigned> MemorySSAPathCheckLimit(
1535ffd83dbSDimitry Andric     "dse-memoryssa-path-check-limit", cl::init(50), cl::Hidden,
1545ffd83dbSDimitry Andric     cl::desc("The maximum number of blocks to check when trying to prove that "
1555ffd83dbSDimitry Andric              "all paths to an exit go through a killing block (default = 50)"));
1565ffd83dbSDimitry Andric 
1574824e7fdSDimitry Andric // This flags allows or disallows DSE to optimize MemorySSA during its
1584824e7fdSDimitry Andric // traversal. Note that DSE optimizing MemorySSA may impact other passes
1594824e7fdSDimitry Andric // downstream of the DSE invocation and can lead to issues not being
1604824e7fdSDimitry Andric // reproducible in isolation (i.e. when MemorySSA is built from scratch). In
1614824e7fdSDimitry Andric // those cases, the flag can be used to check if DSE's MemorySSA optimizations
1624824e7fdSDimitry Andric // impact follow-up passes.
1634824e7fdSDimitry Andric static cl::opt<bool>
1644824e7fdSDimitry Andric     OptimizeMemorySSA("dse-optimize-memoryssa", cl::init(true), cl::Hidden,
1654824e7fdSDimitry Andric                       cl::desc("Allow DSE to optimize memory accesses."));
1664824e7fdSDimitry Andric 
1670b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
1680b57cec5SDimitry Andric // Helper functions
1690b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
1700b57cec5SDimitry Andric using OverlapIntervalsTy = std::map<int64_t, int64_t>;
1710b57cec5SDimitry Andric using InstOverlapIntervalsTy = DenseMap<Instruction *, OverlapIntervalsTy>;
1720b57cec5SDimitry Andric 
1730b57cec5SDimitry Andric /// Returns true if the end of this instruction can be safely shortened in
1740b57cec5SDimitry Andric /// length.
1750b57cec5SDimitry Andric static bool isShortenableAtTheEnd(Instruction *I) {
1760b57cec5SDimitry Andric   // Don't shorten stores for now
1770b57cec5SDimitry Andric   if (isa<StoreInst>(I))
1780b57cec5SDimitry Andric     return false;
1790b57cec5SDimitry Andric 
1800b57cec5SDimitry Andric   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
1810b57cec5SDimitry Andric     switch (II->getIntrinsicID()) {
1820b57cec5SDimitry Andric       default: return false;
1830b57cec5SDimitry Andric       case Intrinsic::memset:
1840b57cec5SDimitry Andric       case Intrinsic::memcpy:
1850b57cec5SDimitry Andric       case Intrinsic::memcpy_element_unordered_atomic:
1860b57cec5SDimitry Andric       case Intrinsic::memset_element_unordered_atomic:
1870b57cec5SDimitry Andric         // Do shorten memory intrinsics.
1880b57cec5SDimitry Andric         // FIXME: Add memmove if it's also safe to transform.
1890b57cec5SDimitry Andric         return true;
1900b57cec5SDimitry Andric     }
1910b57cec5SDimitry Andric   }
1920b57cec5SDimitry Andric 
1930b57cec5SDimitry Andric   // Don't shorten libcalls calls for now.
1940b57cec5SDimitry Andric 
1950b57cec5SDimitry Andric   return false;
1960b57cec5SDimitry Andric }
1970b57cec5SDimitry Andric 
1980b57cec5SDimitry Andric /// Returns true if the beginning of this instruction can be safely shortened
1990b57cec5SDimitry Andric /// in length.
2000b57cec5SDimitry Andric static bool isShortenableAtTheBeginning(Instruction *I) {
2010b57cec5SDimitry Andric   // FIXME: Handle only memset for now. Supporting memcpy/memmove should be
2020b57cec5SDimitry Andric   // easily done by offsetting the source address.
2030b57cec5SDimitry Andric   return isa<AnyMemSetInst>(I);
2040b57cec5SDimitry Andric }
2050b57cec5SDimitry Andric 
2065f757f3fSDimitry Andric static std::optional<TypeSize> getPointerSize(const Value *V,
2075f757f3fSDimitry Andric                                               const DataLayout &DL,
2080b57cec5SDimitry Andric                                               const TargetLibraryInfo &TLI,
2090b57cec5SDimitry Andric                                               const Function *F) {
2100b57cec5SDimitry Andric   uint64_t Size;
2110b57cec5SDimitry Andric   ObjectSizeOpts Opts;
2120b57cec5SDimitry Andric   Opts.NullIsUnknownSize = NullPointerIsDefined(F);
2130b57cec5SDimitry Andric 
2140b57cec5SDimitry Andric   if (getObjectSize(V, Size, DL, &TLI, Opts))
2155f757f3fSDimitry Andric     return TypeSize::getFixed(Size);
2165f757f3fSDimitry Andric   return std::nullopt;
2170b57cec5SDimitry Andric }
2180b57cec5SDimitry Andric 
2190b57cec5SDimitry Andric namespace {
2200b57cec5SDimitry Andric 
2210b57cec5SDimitry Andric enum OverwriteResult {
2220b57cec5SDimitry Andric   OW_Begin,
2230b57cec5SDimitry Andric   OW_Complete,
2240b57cec5SDimitry Andric   OW_End,
2250b57cec5SDimitry Andric   OW_PartialEarlierWithFullLater,
226e8d8bef9SDimitry Andric   OW_MaybePartial,
2274824e7fdSDimitry Andric   OW_None,
2280b57cec5SDimitry Andric   OW_Unknown
2290b57cec5SDimitry Andric };
2300b57cec5SDimitry Andric 
2310b57cec5SDimitry Andric } // end anonymous namespace
2320b57cec5SDimitry Andric 
233e8d8bef9SDimitry Andric /// Check if two instruction are masked stores that completely
234349cc55cSDimitry Andric /// overwrite one another. More specifically, \p KillingI has to
235349cc55cSDimitry Andric /// overwrite \p DeadI.
236349cc55cSDimitry Andric static OverwriteResult isMaskedStoreOverwrite(const Instruction *KillingI,
237349cc55cSDimitry Andric                                               const Instruction *DeadI,
238fe6060f1SDimitry Andric                                               BatchAAResults &AA) {
239349cc55cSDimitry Andric   const auto *KillingII = dyn_cast<IntrinsicInst>(KillingI);
240349cc55cSDimitry Andric   const auto *DeadII = dyn_cast<IntrinsicInst>(DeadI);
241349cc55cSDimitry Andric   if (KillingII == nullptr || DeadII == nullptr)
242e8d8bef9SDimitry Andric     return OW_Unknown;
243bdd1243dSDimitry Andric   if (KillingII->getIntrinsicID() != DeadII->getIntrinsicID())
244bdd1243dSDimitry Andric     return OW_Unknown;
245bdd1243dSDimitry Andric   if (KillingII->getIntrinsicID() == Intrinsic::masked_store) {
246bdd1243dSDimitry Andric     // Type size.
247bdd1243dSDimitry Andric     VectorType *KillingTy =
248bdd1243dSDimitry Andric         cast<VectorType>(KillingII->getArgOperand(0)->getType());
249bdd1243dSDimitry Andric     VectorType *DeadTy = cast<VectorType>(DeadII->getArgOperand(0)->getType());
250bdd1243dSDimitry Andric     if (KillingTy->getScalarSizeInBits() != DeadTy->getScalarSizeInBits())
251bdd1243dSDimitry Andric       return OW_Unknown;
252bdd1243dSDimitry Andric     // Element count.
253bdd1243dSDimitry Andric     if (KillingTy->getElementCount() != DeadTy->getElementCount())
254e8d8bef9SDimitry Andric       return OW_Unknown;
255e8d8bef9SDimitry Andric     // Pointers.
256349cc55cSDimitry Andric     Value *KillingPtr = KillingII->getArgOperand(1)->stripPointerCasts();
257349cc55cSDimitry Andric     Value *DeadPtr = DeadII->getArgOperand(1)->stripPointerCasts();
258349cc55cSDimitry Andric     if (KillingPtr != DeadPtr && !AA.isMustAlias(KillingPtr, DeadPtr))
259e8d8bef9SDimitry Andric       return OW_Unknown;
260e8d8bef9SDimitry Andric     // Masks.
261349cc55cSDimitry Andric     // TODO: check that KillingII's mask is a superset of the DeadII's mask.
262349cc55cSDimitry Andric     if (KillingII->getArgOperand(3) != DeadII->getArgOperand(3))
263e8d8bef9SDimitry Andric       return OW_Unknown;
264e8d8bef9SDimitry Andric     return OW_Complete;
265e8d8bef9SDimitry Andric   }
266bdd1243dSDimitry Andric   return OW_Unknown;
267bdd1243dSDimitry Andric }
268e8d8bef9SDimitry Andric 
269349cc55cSDimitry Andric /// Return 'OW_Complete' if a store to the 'KillingLoc' location completely
270349cc55cSDimitry Andric /// overwrites a store to the 'DeadLoc' location, 'OW_End' if the end of the
271349cc55cSDimitry Andric /// 'DeadLoc' location is completely overwritten by 'KillingLoc', 'OW_Begin'
272349cc55cSDimitry Andric /// if the beginning of the 'DeadLoc' location is overwritten by 'KillingLoc'.
273349cc55cSDimitry Andric /// 'OW_PartialEarlierWithFullLater' means that a dead (big) store was
274349cc55cSDimitry Andric /// overwritten by a killing (smaller) store which doesn't write outside the big
275e8d8bef9SDimitry Andric /// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.
276349cc55cSDimitry Andric /// NOTE: This function must only be called if both \p KillingLoc and \p
277349cc55cSDimitry Andric /// DeadLoc belong to the same underlying object with valid \p KillingOff and
278349cc55cSDimitry Andric /// \p DeadOff.
279349cc55cSDimitry Andric static OverwriteResult isPartialOverwrite(const MemoryLocation &KillingLoc,
280349cc55cSDimitry Andric                                           const MemoryLocation &DeadLoc,
281349cc55cSDimitry Andric                                           int64_t KillingOff, int64_t DeadOff,
282349cc55cSDimitry Andric                                           Instruction *DeadI,
283e8d8bef9SDimitry Andric                                           InstOverlapIntervalsTy &IOL) {
284349cc55cSDimitry Andric   const uint64_t KillingSize = KillingLoc.Size.getValue();
285349cc55cSDimitry Andric   const uint64_t DeadSize = DeadLoc.Size.getValue();
2860b57cec5SDimitry Andric   // We may now overlap, although the overlap is not complete. There might also
2870b57cec5SDimitry Andric   // be other incomplete overlaps, and together, they might cover the complete
288349cc55cSDimitry Andric   // dead store.
2890b57cec5SDimitry Andric   // Note: The correctness of this logic depends on the fact that this function
2900b57cec5SDimitry Andric   // is not even called providing DepWrite when there are any intervening reads.
2910b57cec5SDimitry Andric   if (EnablePartialOverwriteTracking &&
292349cc55cSDimitry Andric       KillingOff < int64_t(DeadOff + DeadSize) &&
293349cc55cSDimitry Andric       int64_t(KillingOff + KillingSize) >= DeadOff) {
2940b57cec5SDimitry Andric 
2950b57cec5SDimitry Andric     // Insert our part of the overlap into the map.
296349cc55cSDimitry Andric     auto &IM = IOL[DeadI];
297349cc55cSDimitry Andric     LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: DeadLoc [" << DeadOff << ", "
298349cc55cSDimitry Andric                       << int64_t(DeadOff + DeadSize) << ") KillingLoc ["
299349cc55cSDimitry Andric                       << KillingOff << ", " << int64_t(KillingOff + KillingSize)
300349cc55cSDimitry Andric                       << ")\n");
3010b57cec5SDimitry Andric 
3020b57cec5SDimitry Andric     // Make sure that we only insert non-overlapping intervals and combine
3030b57cec5SDimitry Andric     // adjacent intervals. The intervals are stored in the map with the ending
3040b57cec5SDimitry Andric     // offset as the key (in the half-open sense) and the starting offset as
3050b57cec5SDimitry Andric     // the value.
306349cc55cSDimitry Andric     int64_t KillingIntStart = KillingOff;
307349cc55cSDimitry Andric     int64_t KillingIntEnd = KillingOff + KillingSize;
3080b57cec5SDimitry Andric 
309349cc55cSDimitry Andric     // Find any intervals ending at, or after, KillingIntStart which start
310349cc55cSDimitry Andric     // before KillingIntEnd.
311349cc55cSDimitry Andric     auto ILI = IM.lower_bound(KillingIntStart);
312349cc55cSDimitry Andric     if (ILI != IM.end() && ILI->second <= KillingIntEnd) {
3130b57cec5SDimitry Andric       // This existing interval is overlapped with the current store somewhere
314349cc55cSDimitry Andric       // in [KillingIntStart, KillingIntEnd]. Merge them by erasing the existing
3150b57cec5SDimitry Andric       // intervals and adjusting our start and end.
316349cc55cSDimitry Andric       KillingIntStart = std::min(KillingIntStart, ILI->second);
317349cc55cSDimitry Andric       KillingIntEnd = std::max(KillingIntEnd, ILI->first);
3180b57cec5SDimitry Andric       ILI = IM.erase(ILI);
3190b57cec5SDimitry Andric 
3200b57cec5SDimitry Andric       // Continue erasing and adjusting our end in case other previous
3210b57cec5SDimitry Andric       // intervals are also overlapped with the current store.
3220b57cec5SDimitry Andric       //
323349cc55cSDimitry Andric       // |--- dead 1 ---|  |--- dead 2 ---|
324349cc55cSDimitry Andric       //     |------- killing---------|
3250b57cec5SDimitry Andric       //
326349cc55cSDimitry Andric       while (ILI != IM.end() && ILI->second <= KillingIntEnd) {
327349cc55cSDimitry Andric         assert(ILI->second > KillingIntStart && "Unexpected interval");
328349cc55cSDimitry Andric         KillingIntEnd = std::max(KillingIntEnd, ILI->first);
3290b57cec5SDimitry Andric         ILI = IM.erase(ILI);
3300b57cec5SDimitry Andric       }
3310b57cec5SDimitry Andric     }
3320b57cec5SDimitry Andric 
333349cc55cSDimitry Andric     IM[KillingIntEnd] = KillingIntStart;
3340b57cec5SDimitry Andric 
3350b57cec5SDimitry Andric     ILI = IM.begin();
336349cc55cSDimitry Andric     if (ILI->second <= DeadOff && ILI->first >= int64_t(DeadOff + DeadSize)) {
337349cc55cSDimitry Andric       LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: DeadLoc ["
338349cc55cSDimitry Andric                         << DeadOff << ", " << int64_t(DeadOff + DeadSize)
339349cc55cSDimitry Andric                         << ") Composite KillingLoc [" << ILI->second << ", "
3400b57cec5SDimitry Andric                         << ILI->first << ")\n");
3410b57cec5SDimitry Andric       ++NumCompletePartials;
3420b57cec5SDimitry Andric       return OW_Complete;
3430b57cec5SDimitry Andric     }
3440b57cec5SDimitry Andric   }
3450b57cec5SDimitry Andric 
346349cc55cSDimitry Andric   // Check for a dead store which writes to all the memory locations that
347349cc55cSDimitry Andric   // the killing store writes to.
348349cc55cSDimitry Andric   if (EnablePartialStoreMerging && KillingOff >= DeadOff &&
349349cc55cSDimitry Andric       int64_t(DeadOff + DeadSize) > KillingOff &&
350349cc55cSDimitry Andric       uint64_t(KillingOff - DeadOff) + KillingSize <= DeadSize) {
351349cc55cSDimitry Andric     LLVM_DEBUG(dbgs() << "DSE: Partial overwrite a dead load [" << DeadOff
352349cc55cSDimitry Andric                       << ", " << int64_t(DeadOff + DeadSize)
353349cc55cSDimitry Andric                       << ") by a killing store [" << KillingOff << ", "
354349cc55cSDimitry Andric                       << int64_t(KillingOff + KillingSize) << ")\n");
3550b57cec5SDimitry Andric     // TODO: Maybe come up with a better name?
3560b57cec5SDimitry Andric     return OW_PartialEarlierWithFullLater;
3570b57cec5SDimitry Andric   }
3580b57cec5SDimitry Andric 
359349cc55cSDimitry Andric   // Another interesting case is if the killing store overwrites the end of the
360349cc55cSDimitry Andric   // dead store.
3610b57cec5SDimitry Andric   //
362349cc55cSDimitry Andric   //      |--dead--|
363349cc55cSDimitry Andric   //                |--   killing   --|
3640b57cec5SDimitry Andric   //
365349cc55cSDimitry Andric   // In this case we may want to trim the size of dead store to avoid
366349cc55cSDimitry Andric   // generating stores to addresses which will definitely be overwritten killing
367349cc55cSDimitry Andric   // store.
3680b57cec5SDimitry Andric   if (!EnablePartialOverwriteTracking &&
369349cc55cSDimitry Andric       (KillingOff > DeadOff && KillingOff < int64_t(DeadOff + DeadSize) &&
370349cc55cSDimitry Andric        int64_t(KillingOff + KillingSize) >= int64_t(DeadOff + DeadSize)))
3710b57cec5SDimitry Andric     return OW_End;
3720b57cec5SDimitry Andric 
373349cc55cSDimitry Andric   // Finally, we also need to check if the killing store overwrites the
374349cc55cSDimitry Andric   // beginning of the dead store.
3750b57cec5SDimitry Andric   //
376349cc55cSDimitry Andric   //                |--dead--|
377349cc55cSDimitry Andric   //      |--  killing  --|
3780b57cec5SDimitry Andric   //
3790b57cec5SDimitry Andric   // In this case we may want to move the destination address and trim the size
380349cc55cSDimitry Andric   // of dead store to avoid generating stores to addresses which will definitely
381349cc55cSDimitry Andric   // be overwritten killing store.
3820b57cec5SDimitry Andric   if (!EnablePartialOverwriteTracking &&
383349cc55cSDimitry Andric       (KillingOff <= DeadOff && int64_t(KillingOff + KillingSize) > DeadOff)) {
384349cc55cSDimitry Andric     assert(int64_t(KillingOff + KillingSize) < int64_t(DeadOff + DeadSize) &&
3850b57cec5SDimitry Andric            "Expect to be handled as OW_Complete");
3860b57cec5SDimitry Andric     return OW_Begin;
3870b57cec5SDimitry Andric   }
3880b57cec5SDimitry Andric   // Otherwise, they don't completely overlap.
3890b57cec5SDimitry Andric   return OW_Unknown;
3900b57cec5SDimitry Andric }
3910b57cec5SDimitry Andric 
3920b57cec5SDimitry Andric /// Returns true if the memory which is accessed by the second instruction is not
3930b57cec5SDimitry Andric /// modified between the first and the second instruction.
3940b57cec5SDimitry Andric /// Precondition: Second instruction must be dominated by the first
3950b57cec5SDimitry Andric /// instruction.
396e8d8bef9SDimitry Andric static bool
397fe6060f1SDimitry Andric memoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI,
398fe6060f1SDimitry Andric                            BatchAAResults &AA, const DataLayout &DL,
399fe6060f1SDimitry Andric                            DominatorTree *DT) {
4005ffd83dbSDimitry Andric   // Do a backwards scan through the CFG from SecondI to FirstI. Look for
4015ffd83dbSDimitry Andric   // instructions which can modify the memory location accessed by SecondI.
4025ffd83dbSDimitry Andric   //
4035ffd83dbSDimitry Andric   // While doing the walk keep track of the address to check. It might be
4045ffd83dbSDimitry Andric   // different in different basic blocks due to PHI translation.
4055ffd83dbSDimitry Andric   using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;
4065ffd83dbSDimitry Andric   SmallVector<BlockAddressPair, 16> WorkList;
4075ffd83dbSDimitry Andric   // Keep track of the address we visited each block with. Bail out if we
4085ffd83dbSDimitry Andric   // visit a block with different addresses.
4095ffd83dbSDimitry Andric   DenseMap<BasicBlock *, Value *> Visited;
4105ffd83dbSDimitry Andric 
4110b57cec5SDimitry Andric   BasicBlock::iterator FirstBBI(FirstI);
4120b57cec5SDimitry Andric   ++FirstBBI;
4130b57cec5SDimitry Andric   BasicBlock::iterator SecondBBI(SecondI);
4140b57cec5SDimitry Andric   BasicBlock *FirstBB = FirstI->getParent();
4150b57cec5SDimitry Andric   BasicBlock *SecondBB = SecondI->getParent();
416349cc55cSDimitry Andric   MemoryLocation MemLoc;
417349cc55cSDimitry Andric   if (auto *MemSet = dyn_cast<MemSetInst>(SecondI))
418349cc55cSDimitry Andric     MemLoc = MemoryLocation::getForDest(MemSet);
419349cc55cSDimitry Andric   else
420349cc55cSDimitry Andric     MemLoc = MemoryLocation::get(SecondI);
421349cc55cSDimitry Andric 
4225ffd83dbSDimitry Andric   auto *MemLocPtr = const_cast<Value *>(MemLoc.Ptr);
4230b57cec5SDimitry Andric 
4245ffd83dbSDimitry Andric   // Start checking the SecondBB.
4255ffd83dbSDimitry Andric   WorkList.push_back(
4265ffd83dbSDimitry Andric       std::make_pair(SecondBB, PHITransAddr(MemLocPtr, DL, nullptr)));
4270b57cec5SDimitry Andric   bool isFirstBlock = true;
4280b57cec5SDimitry Andric 
4295ffd83dbSDimitry Andric   // Check all blocks going backward until we reach the FirstBB.
4300b57cec5SDimitry Andric   while (!WorkList.empty()) {
4315ffd83dbSDimitry Andric     BlockAddressPair Current = WorkList.pop_back_val();
4325ffd83dbSDimitry Andric     BasicBlock *B = Current.first;
4335ffd83dbSDimitry Andric     PHITransAddr &Addr = Current.second;
4345ffd83dbSDimitry Andric     Value *Ptr = Addr.getAddr();
4350b57cec5SDimitry Andric 
4365ffd83dbSDimitry Andric     // Ignore instructions before FirstI if this is the FirstBB.
4370b57cec5SDimitry Andric     BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
4380b57cec5SDimitry Andric 
4390b57cec5SDimitry Andric     BasicBlock::iterator EI;
4400b57cec5SDimitry Andric     if (isFirstBlock) {
4415ffd83dbSDimitry Andric       // Ignore instructions after SecondI if this is the first visit of SecondBB.
4420b57cec5SDimitry Andric       assert(B == SecondBB && "first block is not the store block");
4430b57cec5SDimitry Andric       EI = SecondBBI;
4440b57cec5SDimitry Andric       isFirstBlock = false;
4450b57cec5SDimitry Andric     } else {
4460b57cec5SDimitry Andric       // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
4475ffd83dbSDimitry Andric       // In this case we also have to look at instructions after SecondI.
4480b57cec5SDimitry Andric       EI = B->end();
4490b57cec5SDimitry Andric     }
4500b57cec5SDimitry Andric     for (; BI != EI; ++BI) {
4510b57cec5SDimitry Andric       Instruction *I = &*BI;
4520b57cec5SDimitry Andric       if (I->mayWriteToMemory() && I != SecondI)
453e8d8bef9SDimitry Andric         if (isModSet(AA.getModRefInfo(I, MemLoc.getWithNewPtr(Ptr))))
4540b57cec5SDimitry Andric           return false;
4550b57cec5SDimitry Andric     }
4560b57cec5SDimitry Andric     if (B != FirstBB) {
4570b57cec5SDimitry Andric       assert(B != &FirstBB->getParent()->getEntryBlock() &&
4580b57cec5SDimitry Andric           "Should not hit the entry block because SI must be dominated by LI");
459fe6060f1SDimitry Andric       for (BasicBlock *Pred : predecessors(B)) {
4605ffd83dbSDimitry Andric         PHITransAddr PredAddr = Addr;
46106c3fb27SDimitry Andric         if (PredAddr.needsPHITranslationFromBlock(B)) {
46206c3fb27SDimitry Andric           if (!PredAddr.isPotentiallyPHITranslatable())
4635ffd83dbSDimitry Andric             return false;
46406c3fb27SDimitry Andric           if (!PredAddr.translateValue(B, Pred, DT, false))
4655ffd83dbSDimitry Andric             return false;
4665ffd83dbSDimitry Andric         }
4675ffd83dbSDimitry Andric         Value *TranslatedPtr = PredAddr.getAddr();
468fe6060f1SDimitry Andric         auto Inserted = Visited.insert(std::make_pair(Pred, TranslatedPtr));
4695ffd83dbSDimitry Andric         if (!Inserted.second) {
4705ffd83dbSDimitry Andric           // We already visited this block before. If it was with a different
4715ffd83dbSDimitry Andric           // address - bail out!
4725ffd83dbSDimitry Andric           if (TranslatedPtr != Inserted.first->second)
4735ffd83dbSDimitry Andric             return false;
4745ffd83dbSDimitry Andric           // ... otherwise just skip it.
4750b57cec5SDimitry Andric           continue;
4765ffd83dbSDimitry Andric         }
477fe6060f1SDimitry Andric         WorkList.push_back(std::make_pair(Pred, PredAddr));
4780b57cec5SDimitry Andric       }
4790b57cec5SDimitry Andric     }
4800b57cec5SDimitry Andric   }
4810b57cec5SDimitry Andric   return true;
4820b57cec5SDimitry Andric }
4830b57cec5SDimitry Andric 
48406c3fb27SDimitry Andric static void shortenAssignment(Instruction *Inst, Value *OriginalDest,
48506c3fb27SDimitry Andric                               uint64_t OldOffsetInBits, uint64_t OldSizeInBits,
48606c3fb27SDimitry Andric                               uint64_t NewSizeInBits, bool IsOverwriteEnd) {
487*0fca6ea1SDimitry Andric   const DataLayout &DL = Inst->getDataLayout();
48806c3fb27SDimitry Andric   uint64_t DeadSliceSizeInBits = OldSizeInBits - NewSizeInBits;
48906c3fb27SDimitry Andric   uint64_t DeadSliceOffsetInBits =
490bdd1243dSDimitry Andric       OldOffsetInBits + (IsOverwriteEnd ? NewSizeInBits : 0);
4917a6dacacSDimitry Andric   auto SetDeadFragExpr = [](auto *Assign,
49206c3fb27SDimitry Andric                             DIExpression::FragmentInfo DeadFragment) {
49306c3fb27SDimitry Andric     // createFragmentExpression expects an offset relative to the existing
49406c3fb27SDimitry Andric     // fragment offset if there is one.
49506c3fb27SDimitry Andric     uint64_t RelativeOffset = DeadFragment.OffsetInBits -
4967a6dacacSDimitry Andric                               Assign->getExpression()
49706c3fb27SDimitry Andric                                   ->getFragmentInfo()
49806c3fb27SDimitry Andric                                   .value_or(DIExpression::FragmentInfo(0, 0))
49906c3fb27SDimitry Andric                                   .OffsetInBits;
50006c3fb27SDimitry Andric     if (auto NewExpr = DIExpression::createFragmentExpression(
5017a6dacacSDimitry Andric             Assign->getExpression(), RelativeOffset, DeadFragment.SizeInBits)) {
5027a6dacacSDimitry Andric       Assign->setExpression(*NewExpr);
50306c3fb27SDimitry Andric       return;
50406c3fb27SDimitry Andric     }
50506c3fb27SDimitry Andric     // Failed to create a fragment expression for this so discard the value,
50606c3fb27SDimitry Andric     // making this a kill location.
50706c3fb27SDimitry Andric     auto *Expr = *DIExpression::createFragmentExpression(
5087a6dacacSDimitry Andric         DIExpression::get(Assign->getContext(), std::nullopt),
509bdd1243dSDimitry Andric         DeadFragment.OffsetInBits, DeadFragment.SizeInBits);
5107a6dacacSDimitry Andric     Assign->setExpression(Expr);
5117a6dacacSDimitry Andric     Assign->setKillLocation();
512bdd1243dSDimitry Andric   };
513bdd1243dSDimitry Andric 
514bdd1243dSDimitry Andric   // A DIAssignID to use so that the inserted dbg.assign intrinsics do not
515bdd1243dSDimitry Andric   // link to any instructions. Created in the loop below (once).
516bdd1243dSDimitry Andric   DIAssignID *LinkToNothing = nullptr;
51706c3fb27SDimitry Andric   LLVMContext &Ctx = Inst->getContext();
51806c3fb27SDimitry Andric   auto GetDeadLink = [&Ctx, &LinkToNothing]() {
51906c3fb27SDimitry Andric     if (!LinkToNothing)
52006c3fb27SDimitry Andric       LinkToNothing = DIAssignID::getDistinct(Ctx);
52106c3fb27SDimitry Andric     return LinkToNothing;
52206c3fb27SDimitry Andric   };
523bdd1243dSDimitry Andric 
524bdd1243dSDimitry Andric   // Insert an unlinked dbg.assign intrinsic for the dead fragment after each
52506c3fb27SDimitry Andric   // overlapping dbg.assign intrinsic. The loop invalidates the iterators
52606c3fb27SDimitry Andric   // returned by getAssignmentMarkers so save a copy of the markers to iterate
52706c3fb27SDimitry Andric   // over.
52806c3fb27SDimitry Andric   auto LinkedRange = at::getAssignmentMarkers(Inst);
529*0fca6ea1SDimitry Andric   SmallVector<DbgVariableRecord *> LinkedDVRAssigns =
530*0fca6ea1SDimitry Andric       at::getDVRAssignmentMarkers(Inst);
53106c3fb27SDimitry Andric   SmallVector<DbgAssignIntrinsic *> Linked(LinkedRange.begin(),
53206c3fb27SDimitry Andric                                            LinkedRange.end());
5337a6dacacSDimitry Andric   auto InsertAssignForOverlap = [&](auto *Assign) {
53406c3fb27SDimitry Andric     std::optional<DIExpression::FragmentInfo> NewFragment;
53506c3fb27SDimitry Andric     if (!at::calculateFragmentIntersect(DL, OriginalDest, DeadSliceOffsetInBits,
5367a6dacacSDimitry Andric                                         DeadSliceSizeInBits, Assign,
53706c3fb27SDimitry Andric                                         NewFragment) ||
53806c3fb27SDimitry Andric         !NewFragment) {
53906c3fb27SDimitry Andric       // We couldn't calculate the intersecting fragment for some reason. Be
54006c3fb27SDimitry Andric       // cautious and unlink the whole assignment from the store.
5417a6dacacSDimitry Andric       Assign->setKillAddress();
5427a6dacacSDimitry Andric       Assign->setAssignId(GetDeadLink());
5437a6dacacSDimitry Andric       return;
544bdd1243dSDimitry Andric     }
54506c3fb27SDimitry Andric     // No intersect.
54606c3fb27SDimitry Andric     if (NewFragment->SizeInBits == 0)
5477a6dacacSDimitry Andric       return;
548bdd1243dSDimitry Andric 
549bdd1243dSDimitry Andric     // Fragments overlap: insert a new dbg.assign for this dead part.
5507a6dacacSDimitry Andric     auto *NewAssign = static_cast<decltype(Assign)>(Assign->clone());
5517a6dacacSDimitry Andric     NewAssign->insertAfter(Assign);
55206c3fb27SDimitry Andric     NewAssign->setAssignId(GetDeadLink());
55306c3fb27SDimitry Andric     if (NewFragment)
55406c3fb27SDimitry Andric       SetDeadFragExpr(NewAssign, *NewFragment);
555bdd1243dSDimitry Andric     NewAssign->setKillAddress();
5567a6dacacSDimitry Andric   };
5577a6dacacSDimitry Andric   for_each(Linked, InsertAssignForOverlap);
558*0fca6ea1SDimitry Andric   for_each(LinkedDVRAssigns, InsertAssignForOverlap);
559bdd1243dSDimitry Andric }
560bdd1243dSDimitry Andric 
561349cc55cSDimitry Andric static bool tryToShorten(Instruction *DeadI, int64_t &DeadStart,
562349cc55cSDimitry Andric                          uint64_t &DeadSize, int64_t KillingStart,
563349cc55cSDimitry Andric                          uint64_t KillingSize, bool IsOverwriteEnd) {
564349cc55cSDimitry Andric   auto *DeadIntrinsic = cast<AnyMemIntrinsic>(DeadI);
565349cc55cSDimitry Andric   Align PrefAlign = DeadIntrinsic->getDestAlign().valueOrOne();
5660b57cec5SDimitry Andric 
567fe6060f1SDimitry Andric   // We assume that memet/memcpy operates in chunks of the "largest" native
568fe6060f1SDimitry Andric   // type size and aligned on the same value. That means optimal start and size
569fe6060f1SDimitry Andric   // of memset/memcpy should be modulo of preferred alignment of that type. That
570fe6060f1SDimitry Andric   // is it there is no any sense in trying to reduce store size any further
571fe6060f1SDimitry Andric   // since any "extra" stores comes for free anyway.
572fe6060f1SDimitry Andric   // On the other hand, maximum alignment we can achieve is limited by alignment
573fe6060f1SDimitry Andric   // of initial store.
574fe6060f1SDimitry Andric 
575fe6060f1SDimitry Andric   // TODO: Limit maximum alignment by preferred (or abi?) alignment of the
576fe6060f1SDimitry Andric   // "largest" native type.
577fe6060f1SDimitry Andric   // Note: What is the proper way to get that value?
578fe6060f1SDimitry Andric   // Should TargetTransformInfo::getRegisterBitWidth be used or anything else?
579fe6060f1SDimitry Andric   // PrefAlign = std::min(DL.getPrefTypeAlign(LargestType), PrefAlign);
580fe6060f1SDimitry Andric 
581fe6060f1SDimitry Andric   int64_t ToRemoveStart = 0;
582fe6060f1SDimitry Andric   uint64_t ToRemoveSize = 0;
583fe6060f1SDimitry Andric   // Compute start and size of the region to remove. Make sure 'PrefAlign' is
584fe6060f1SDimitry Andric   // maintained on the remaining store.
585fe6060f1SDimitry Andric   if (IsOverwriteEnd) {
586349cc55cSDimitry Andric     // Calculate required adjustment for 'KillingStart' in order to keep
587349cc55cSDimitry Andric     // remaining store size aligned on 'PerfAlign'.
588fe6060f1SDimitry Andric     uint64_t Off =
589349cc55cSDimitry Andric         offsetToAlignment(uint64_t(KillingStart - DeadStart), PrefAlign);
590349cc55cSDimitry Andric     ToRemoveStart = KillingStart + Off;
591349cc55cSDimitry Andric     if (DeadSize <= uint64_t(ToRemoveStart - DeadStart))
5920b57cec5SDimitry Andric       return false;
593349cc55cSDimitry Andric     ToRemoveSize = DeadSize - uint64_t(ToRemoveStart - DeadStart);
594fe6060f1SDimitry Andric   } else {
595349cc55cSDimitry Andric     ToRemoveStart = DeadStart;
596349cc55cSDimitry Andric     assert(KillingSize >= uint64_t(DeadStart - KillingStart) &&
597fe6060f1SDimitry Andric            "Not overlapping accesses?");
598349cc55cSDimitry Andric     ToRemoveSize = KillingSize - uint64_t(DeadStart - KillingStart);
599fe6060f1SDimitry Andric     // Calculate required adjustment for 'ToRemoveSize'in order to keep
600fe6060f1SDimitry Andric     // start of the remaining store aligned on 'PerfAlign'.
601fe6060f1SDimitry Andric     uint64_t Off = offsetToAlignment(ToRemoveSize, PrefAlign);
602fe6060f1SDimitry Andric     if (Off != 0) {
603fe6060f1SDimitry Andric       if (ToRemoveSize <= (PrefAlign.value() - Off))
604fe6060f1SDimitry Andric         return false;
605fe6060f1SDimitry Andric       ToRemoveSize -= PrefAlign.value() - Off;
606fe6060f1SDimitry Andric     }
607fe6060f1SDimitry Andric     assert(isAligned(PrefAlign, ToRemoveSize) &&
608fe6060f1SDimitry Andric            "Should preserve selected alignment");
609fe6060f1SDimitry Andric   }
6100b57cec5SDimitry Andric 
611fe6060f1SDimitry Andric   assert(ToRemoveSize > 0 && "Shouldn't reach here if nothing to remove");
612349cc55cSDimitry Andric   assert(DeadSize > ToRemoveSize && "Can't remove more than original size");
6130b57cec5SDimitry Andric 
614349cc55cSDimitry Andric   uint64_t NewSize = DeadSize - ToRemoveSize;
615349cc55cSDimitry Andric   if (auto *AMI = dyn_cast<AtomicMemIntrinsic>(DeadI)) {
6160b57cec5SDimitry Andric     // When shortening an atomic memory intrinsic, the newly shortened
6170b57cec5SDimitry Andric     // length must remain an integer multiple of the element size.
6180b57cec5SDimitry Andric     const uint32_t ElementSize = AMI->getElementSizeInBytes();
619fe6060f1SDimitry Andric     if (0 != NewSize % ElementSize)
6200b57cec5SDimitry Andric       return false;
6210b57cec5SDimitry Andric   }
6220b57cec5SDimitry Andric 
6230b57cec5SDimitry Andric   LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  OW "
624349cc55cSDimitry Andric                     << (IsOverwriteEnd ? "END" : "BEGIN") << ": " << *DeadI
625349cc55cSDimitry Andric                     << "\n  KILLER [" << ToRemoveStart << ", "
626fe6060f1SDimitry Andric                     << int64_t(ToRemoveStart + ToRemoveSize) << ")\n");
6270b57cec5SDimitry Andric 
628349cc55cSDimitry Andric   Value *DeadWriteLength = DeadIntrinsic->getLength();
629349cc55cSDimitry Andric   Value *TrimmedLength = ConstantInt::get(DeadWriteLength->getType(), NewSize);
630349cc55cSDimitry Andric   DeadIntrinsic->setLength(TrimmedLength);
631349cc55cSDimitry Andric   DeadIntrinsic->setDestAlignment(PrefAlign);
6320b57cec5SDimitry Andric 
633349cc55cSDimitry Andric   Value *OrigDest = DeadIntrinsic->getRawDest();
63406c3fb27SDimitry Andric   if (!IsOverwriteEnd) {
6350b57cec5SDimitry Andric     Value *Indices[1] = {
636349cc55cSDimitry Andric         ConstantInt::get(DeadWriteLength->getType(), ToRemoveSize)};
637fe6060f1SDimitry Andric     Instruction *NewDestGEP = GetElementPtrInst::CreateInBounds(
638*0fca6ea1SDimitry Andric         Type::getInt8Ty(DeadIntrinsic->getContext()), OrigDest, Indices, "",
639*0fca6ea1SDimitry Andric         DeadI->getIterator());
640349cc55cSDimitry Andric     NewDestGEP->setDebugLoc(DeadIntrinsic->getDebugLoc());
641349cc55cSDimitry Andric     DeadIntrinsic->setDest(NewDestGEP);
6420b57cec5SDimitry Andric   }
643fe6060f1SDimitry Andric 
644bdd1243dSDimitry Andric   // Update attached dbg.assign intrinsics. Assume 8-bit byte.
64506c3fb27SDimitry Andric   shortenAssignment(DeadI, OrigDest, DeadStart * 8, DeadSize * 8, NewSize * 8,
646bdd1243dSDimitry Andric                     IsOverwriteEnd);
647bdd1243dSDimitry Andric 
648349cc55cSDimitry Andric   // Finally update start and size of dead access.
649fe6060f1SDimitry Andric   if (!IsOverwriteEnd)
650349cc55cSDimitry Andric     DeadStart += ToRemoveSize;
651349cc55cSDimitry Andric   DeadSize = NewSize;
652fe6060f1SDimitry Andric 
6530b57cec5SDimitry Andric   return true;
6540b57cec5SDimitry Andric }
6550b57cec5SDimitry Andric 
656349cc55cSDimitry Andric static bool tryToShortenEnd(Instruction *DeadI, OverlapIntervalsTy &IntervalMap,
657349cc55cSDimitry Andric                             int64_t &DeadStart, uint64_t &DeadSize) {
658349cc55cSDimitry Andric   if (IntervalMap.empty() || !isShortenableAtTheEnd(DeadI))
6590b57cec5SDimitry Andric     return false;
6600b57cec5SDimitry Andric 
6610b57cec5SDimitry Andric   OverlapIntervalsTy::iterator OII = --IntervalMap.end();
662349cc55cSDimitry Andric   int64_t KillingStart = OII->second;
663349cc55cSDimitry Andric   uint64_t KillingSize = OII->first - KillingStart;
6640b57cec5SDimitry Andric 
665349cc55cSDimitry Andric   assert(OII->first - KillingStart >= 0 && "Size expected to be positive");
666e8d8bef9SDimitry Andric 
667349cc55cSDimitry Andric   if (KillingStart > DeadStart &&
668349cc55cSDimitry Andric       // Note: "KillingStart - KillingStart" is known to be positive due to
669e8d8bef9SDimitry Andric       // preceding check.
670349cc55cSDimitry Andric       (uint64_t)(KillingStart - DeadStart) < DeadSize &&
671349cc55cSDimitry Andric       // Note: "DeadSize - (uint64_t)(KillingStart - DeadStart)" is known to
672e8d8bef9SDimitry Andric       // be non negative due to preceding checks.
673349cc55cSDimitry Andric       KillingSize >= DeadSize - (uint64_t)(KillingStart - DeadStart)) {
674349cc55cSDimitry Andric     if (tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
675349cc55cSDimitry Andric                      true)) {
6760b57cec5SDimitry Andric       IntervalMap.erase(OII);
6770b57cec5SDimitry Andric       return true;
6780b57cec5SDimitry Andric     }
6790b57cec5SDimitry Andric   }
6800b57cec5SDimitry Andric   return false;
6810b57cec5SDimitry Andric }
6820b57cec5SDimitry Andric 
683349cc55cSDimitry Andric static bool tryToShortenBegin(Instruction *DeadI,
6840b57cec5SDimitry Andric                               OverlapIntervalsTy &IntervalMap,
685349cc55cSDimitry Andric                               int64_t &DeadStart, uint64_t &DeadSize) {
686349cc55cSDimitry Andric   if (IntervalMap.empty() || !isShortenableAtTheBeginning(DeadI))
6870b57cec5SDimitry Andric     return false;
6880b57cec5SDimitry Andric 
6890b57cec5SDimitry Andric   OverlapIntervalsTy::iterator OII = IntervalMap.begin();
690349cc55cSDimitry Andric   int64_t KillingStart = OII->second;
691349cc55cSDimitry Andric   uint64_t KillingSize = OII->first - KillingStart;
6920b57cec5SDimitry Andric 
693349cc55cSDimitry Andric   assert(OII->first - KillingStart >= 0 && "Size expected to be positive");
694e8d8bef9SDimitry Andric 
695349cc55cSDimitry Andric   if (KillingStart <= DeadStart &&
696349cc55cSDimitry Andric       // Note: "DeadStart - KillingStart" is known to be non negative due to
697e8d8bef9SDimitry Andric       // preceding check.
698349cc55cSDimitry Andric       KillingSize > (uint64_t)(DeadStart - KillingStart)) {
699349cc55cSDimitry Andric     // Note: "KillingSize - (uint64_t)(DeadStart - DeadStart)" is known to
700349cc55cSDimitry Andric     // be positive due to preceding checks.
701349cc55cSDimitry Andric     assert(KillingSize - (uint64_t)(DeadStart - KillingStart) < DeadSize &&
7020b57cec5SDimitry Andric            "Should have been handled as OW_Complete");
703349cc55cSDimitry Andric     if (tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
704349cc55cSDimitry Andric                      false)) {
7050b57cec5SDimitry Andric       IntervalMap.erase(OII);
7060b57cec5SDimitry Andric       return true;
7070b57cec5SDimitry Andric     }
7080b57cec5SDimitry Andric   }
7090b57cec5SDimitry Andric   return false;
7100b57cec5SDimitry Andric }
7110b57cec5SDimitry Andric 
712349cc55cSDimitry Andric static Constant *
713349cc55cSDimitry Andric tryToMergePartialOverlappingStores(StoreInst *KillingI, StoreInst *DeadI,
714349cc55cSDimitry Andric                                    int64_t KillingOffset, int64_t DeadOffset,
715349cc55cSDimitry Andric                                    const DataLayout &DL, BatchAAResults &AA,
716fe6060f1SDimitry Andric                                    DominatorTree *DT) {
7175ffd83dbSDimitry Andric 
718349cc55cSDimitry Andric   if (DeadI && isa<ConstantInt>(DeadI->getValueOperand()) &&
719349cc55cSDimitry Andric       DL.typeSizeEqualsStoreSize(DeadI->getValueOperand()->getType()) &&
720349cc55cSDimitry Andric       KillingI && isa<ConstantInt>(KillingI->getValueOperand()) &&
721349cc55cSDimitry Andric       DL.typeSizeEqualsStoreSize(KillingI->getValueOperand()->getType()) &&
722349cc55cSDimitry Andric       memoryIsNotModifiedBetween(DeadI, KillingI, AA, DL, DT)) {
7235ffd83dbSDimitry Andric     // If the store we find is:
7245ffd83dbSDimitry Andric     //   a) partially overwritten by the store to 'Loc'
725349cc55cSDimitry Andric     //   b) the killing store is fully contained in the dead one and
7265ffd83dbSDimitry Andric     //   c) they both have a constant value
7275ffd83dbSDimitry Andric     //   d) none of the two stores need padding
728349cc55cSDimitry Andric     // Merge the two stores, replacing the dead store's value with a
7295ffd83dbSDimitry Andric     // merge of both values.
7305ffd83dbSDimitry Andric     // TODO: Deal with other constant types (vectors, etc), and probably
7315ffd83dbSDimitry Andric     // some mem intrinsics (if needed)
7325ffd83dbSDimitry Andric 
733349cc55cSDimitry Andric     APInt DeadValue = cast<ConstantInt>(DeadI->getValueOperand())->getValue();
734349cc55cSDimitry Andric     APInt KillingValue =
735349cc55cSDimitry Andric         cast<ConstantInt>(KillingI->getValueOperand())->getValue();
736349cc55cSDimitry Andric     unsigned KillingBits = KillingValue.getBitWidth();
737349cc55cSDimitry Andric     assert(DeadValue.getBitWidth() > KillingValue.getBitWidth());
738349cc55cSDimitry Andric     KillingValue = KillingValue.zext(DeadValue.getBitWidth());
7395ffd83dbSDimitry Andric 
7405ffd83dbSDimitry Andric     // Offset of the smaller store inside the larger store
741349cc55cSDimitry Andric     unsigned BitOffsetDiff = (KillingOffset - DeadOffset) * 8;
742349cc55cSDimitry Andric     unsigned LShiftAmount =
743349cc55cSDimitry Andric         DL.isBigEndian() ? DeadValue.getBitWidth() - BitOffsetDiff - KillingBits
7445ffd83dbSDimitry Andric                          : BitOffsetDiff;
745349cc55cSDimitry Andric     APInt Mask = APInt::getBitsSet(DeadValue.getBitWidth(), LShiftAmount,
746349cc55cSDimitry Andric                                    LShiftAmount + KillingBits);
7475ffd83dbSDimitry Andric     // Clear the bits we'll be replacing, then OR with the smaller
7485ffd83dbSDimitry Andric     // store, shifted appropriately.
749349cc55cSDimitry Andric     APInt Merged = (DeadValue & ~Mask) | (KillingValue << LShiftAmount);
750349cc55cSDimitry Andric     LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n  Dead: " << *DeadI
751349cc55cSDimitry Andric                       << "\n  Killing: " << *KillingI
7525ffd83dbSDimitry Andric                       << "\n  Merged Value: " << Merged << '\n');
753349cc55cSDimitry Andric     return ConstantInt::get(DeadI->getValueOperand()->getType(), Merged);
7545ffd83dbSDimitry Andric   }
7555ffd83dbSDimitry Andric   return nullptr;
7565ffd83dbSDimitry Andric }
7575ffd83dbSDimitry Andric 
7585ffd83dbSDimitry Andric namespace {
75906c3fb27SDimitry Andric // Returns true if \p I is an intrinsic that does not read or write memory.
760e8d8bef9SDimitry Andric bool isNoopIntrinsic(Instruction *I) {
761e8d8bef9SDimitry Andric   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
7625ffd83dbSDimitry Andric     switch (II->getIntrinsicID()) {
7635ffd83dbSDimitry Andric     case Intrinsic::lifetime_start:
7645ffd83dbSDimitry Andric     case Intrinsic::lifetime_end:
7655ffd83dbSDimitry Andric     case Intrinsic::invariant_end:
7665ffd83dbSDimitry Andric     case Intrinsic::launder_invariant_group:
7675ffd83dbSDimitry Andric     case Intrinsic::assume:
7685ffd83dbSDimitry Andric       return true;
7695ffd83dbSDimitry Andric     case Intrinsic::dbg_declare:
7705ffd83dbSDimitry Andric     case Intrinsic::dbg_label:
7715ffd83dbSDimitry Andric     case Intrinsic::dbg_value:
7725ffd83dbSDimitry Andric       llvm_unreachable("Intrinsic should not be modeled in MemorySSA");
7735ffd83dbSDimitry Andric     default:
7745ffd83dbSDimitry Andric       return false;
7755ffd83dbSDimitry Andric     }
7765ffd83dbSDimitry Andric   }
7775ffd83dbSDimitry Andric   return false;
7785ffd83dbSDimitry Andric }
7795ffd83dbSDimitry Andric 
7805ffd83dbSDimitry Andric // Check if we can ignore \p D for DSE.
78104eeddc0SDimitry Andric bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller) {
7825ffd83dbSDimitry Andric   Instruction *DI = D->getMemoryInst();
7835ffd83dbSDimitry Andric   // Calls that only access inaccessible memory cannot read or write any memory
7845ffd83dbSDimitry Andric   // locations we consider for elimination.
7855ffd83dbSDimitry Andric   if (auto *CB = dyn_cast<CallBase>(DI))
78604eeddc0SDimitry Andric     if (CB->onlyAccessesInaccessibleMemory())
7875ffd83dbSDimitry Andric       return true;
78804eeddc0SDimitry Andric 
7895ffd83dbSDimitry Andric   // We can eliminate stores to locations not visible to the caller across
7905ffd83dbSDimitry Andric   // throwing instructions.
7915ffd83dbSDimitry Andric   if (DI->mayThrow() && !DefVisibleToCaller)
7925ffd83dbSDimitry Andric     return true;
7935ffd83dbSDimitry Andric 
7945ffd83dbSDimitry Andric   // We can remove the dead stores, irrespective of the fence and its ordering
7955ffd83dbSDimitry Andric   // (release/acquire/seq_cst). Fences only constraints the ordering of
7965ffd83dbSDimitry Andric   // already visible stores, it does not make a store visible to other
7975ffd83dbSDimitry Andric   // threads. So, skipping over a fence does not change a store from being
7985ffd83dbSDimitry Andric   // dead.
7995ffd83dbSDimitry Andric   if (isa<FenceInst>(DI))
8005ffd83dbSDimitry Andric     return true;
8015ffd83dbSDimitry Andric 
8025ffd83dbSDimitry Andric   // Skip intrinsics that do not really read or modify memory.
803349cc55cSDimitry Andric   if (isNoopIntrinsic(DI))
8045ffd83dbSDimitry Andric     return true;
8055ffd83dbSDimitry Andric 
8065ffd83dbSDimitry Andric   return false;
8075ffd83dbSDimitry Andric }
8085ffd83dbSDimitry Andric 
8095ffd83dbSDimitry Andric struct DSEState {
8105ffd83dbSDimitry Andric   Function &F;
8115ffd83dbSDimitry Andric   AliasAnalysis &AA;
812349cc55cSDimitry Andric   EarliestEscapeInfo EI;
813e8d8bef9SDimitry Andric 
814e8d8bef9SDimitry Andric   /// The single BatchAA instance that is used to cache AA queries. It will
815e8d8bef9SDimitry Andric   /// not be invalidated over the whole run. This is safe, because:
816e8d8bef9SDimitry Andric   /// 1. Only memory writes are removed, so the alias cache for memory
817e8d8bef9SDimitry Andric   ///    locations remains valid.
818e8d8bef9SDimitry Andric   /// 2. No new instructions are added (only instructions removed), so cached
819e8d8bef9SDimitry Andric   ///    information for a deleted value cannot be accessed by a re-used new
820e8d8bef9SDimitry Andric   ///    value pointer.
821e8d8bef9SDimitry Andric   BatchAAResults BatchAA;
822e8d8bef9SDimitry Andric 
8235ffd83dbSDimitry Andric   MemorySSA &MSSA;
8245ffd83dbSDimitry Andric   DominatorTree &DT;
8255ffd83dbSDimitry Andric   PostDominatorTree &PDT;
8265ffd83dbSDimitry Andric   const TargetLibraryInfo &TLI;
827e8d8bef9SDimitry Andric   const DataLayout &DL;
828fe6060f1SDimitry Andric   const LoopInfo &LI;
829fe6060f1SDimitry Andric 
830fe6060f1SDimitry Andric   // Whether the function contains any irreducible control flow, useful for
831fe6060f1SDimitry Andric   // being accurately able to detect loops.
832fe6060f1SDimitry Andric   bool ContainsIrreducibleLoops;
8335ffd83dbSDimitry Andric 
8345ffd83dbSDimitry Andric   // All MemoryDefs that potentially could kill other MemDefs.
8355ffd83dbSDimitry Andric   SmallVector<MemoryDef *, 64> MemDefs;
8365ffd83dbSDimitry Andric   // Any that should be skipped as they are already deleted
8375ffd83dbSDimitry Andric   SmallPtrSet<MemoryAccess *, 4> SkipStores;
83804eeddc0SDimitry Andric   // Keep track whether a given object is captured before return or not.
83904eeddc0SDimitry Andric   DenseMap<const Value *, bool> CapturedBeforeReturn;
8405ffd83dbSDimitry Andric   // Keep track of all of the objects that are invisible to the caller after
8415ffd83dbSDimitry Andric   // the function returns.
842e8d8bef9SDimitry Andric   DenseMap<const Value *, bool> InvisibleToCallerAfterRet;
8435ffd83dbSDimitry Andric   // Keep track of blocks with throwing instructions not modeled in MemorySSA.
8445ffd83dbSDimitry Andric   SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;
8455ffd83dbSDimitry Andric   // Post-order numbers for each basic block. Used to figure out if memory
8465ffd83dbSDimitry Andric   // accesses are executed before another access.
8475ffd83dbSDimitry Andric   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
8485ffd83dbSDimitry Andric 
8495ffd83dbSDimitry Andric   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
8505ffd83dbSDimitry Andric   /// basic block.
8514824e7fdSDimitry Andric   MapVector<BasicBlock *, InstOverlapIntervalsTy> IOLs;
852d781ede6SDimitry Andric   // Check if there are root nodes that are terminated by UnreachableInst.
853d781ede6SDimitry Andric   // Those roots pessimize post-dominance queries. If there are such roots,
854d781ede6SDimitry Andric   // fall back to CFG scan starting from all non-unreachable roots.
855d781ede6SDimitry Andric   bool AnyUnreachableExit;
8565ffd83dbSDimitry Andric 
857fcaf7f86SDimitry Andric   // Whether or not we should iterate on removing dead stores at the end of the
858fcaf7f86SDimitry Andric   // function due to removing a store causing a previously captured pointer to
859fcaf7f86SDimitry Andric   // no longer be captured.
860fcaf7f86SDimitry Andric   bool ShouldIterateEndOfFunctionDSE;
861fcaf7f86SDimitry Andric 
862439352acSDimitry Andric   /// Dead instructions to be removed at the end of DSE.
863439352acSDimitry Andric   SmallVector<Instruction *> ToRemove;
864439352acSDimitry Andric 
865349cc55cSDimitry Andric   // Class contains self-reference, make sure it's not copied/moved.
866349cc55cSDimitry Andric   DSEState(const DSEState &) = delete;
867349cc55cSDimitry Andric   DSEState &operator=(const DSEState &) = delete;
868349cc55cSDimitry Andric 
8695ffd83dbSDimitry Andric   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
8705f757f3fSDimitry Andric            PostDominatorTree &PDT, const TargetLibraryInfo &TLI,
8715f757f3fSDimitry Andric            const LoopInfo &LI)
8725f757f3fSDimitry Andric       : F(F), AA(AA), EI(DT, &LI), BatchAA(AA, &EI), MSSA(MSSA), DT(DT),
873*0fca6ea1SDimitry Andric         PDT(PDT), TLI(TLI), DL(F.getDataLayout()), LI(LI) {
8745ffd83dbSDimitry Andric     // Collect blocks with throwing instructions not modeled in MemorySSA and
8755ffd83dbSDimitry Andric     // alloc-like objects.
8765ffd83dbSDimitry Andric     unsigned PO = 0;
8775ffd83dbSDimitry Andric     for (BasicBlock *BB : post_order(&F)) {
878349cc55cSDimitry Andric       PostOrderNumbers[BB] = PO++;
8795ffd83dbSDimitry Andric       for (Instruction &I : *BB) {
8805ffd83dbSDimitry Andric         MemoryAccess *MA = MSSA.getMemoryAccess(&I);
8815ffd83dbSDimitry Andric         if (I.mayThrow() && !MA)
882349cc55cSDimitry Andric           ThrowingBlocks.insert(I.getParent());
8835ffd83dbSDimitry Andric 
8845ffd83dbSDimitry Andric         auto *MD = dyn_cast_or_null<MemoryDef>(MA);
885349cc55cSDimitry Andric         if (MD && MemDefs.size() < MemorySSADefsPerBlockLimit &&
8860eae32dcSDimitry Andric             (getLocForWrite(&I) || isMemTerminatorInst(&I)))
887349cc55cSDimitry Andric           MemDefs.push_back(MD);
8885ffd83dbSDimitry Andric       }
8895ffd83dbSDimitry Andric     }
8905ffd83dbSDimitry Andric 
8915ffd83dbSDimitry Andric     // Treat byval or inalloca arguments the same as Allocas, stores to them are
8925ffd83dbSDimitry Andric     // dead at the end of the function.
8935ffd83dbSDimitry Andric     for (Argument &AI : F.args())
89404eeddc0SDimitry Andric       if (AI.hasPassPointeeByValueCopyAttr())
895349cc55cSDimitry Andric         InvisibleToCallerAfterRet.insert({&AI, true});
8965ffd83dbSDimitry Andric 
897fe6060f1SDimitry Andric     // Collect whether there is any irreducible control flow in the function.
898349cc55cSDimitry Andric     ContainsIrreducibleLoops = mayContainIrreducibleControl(F, &LI);
899d781ede6SDimitry Andric 
900d781ede6SDimitry Andric     AnyUnreachableExit = any_of(PDT.roots(), [](const BasicBlock *E) {
901d781ede6SDimitry Andric       return isa<UnreachableInst>(E->getTerminator());
902d781ede6SDimitry Andric     });
9035ffd83dbSDimitry Andric   }
9045ffd83dbSDimitry Andric 
905*0fca6ea1SDimitry Andric   static void pushMemUses(MemoryAccess *Acc,
906*0fca6ea1SDimitry Andric                           SmallVectorImpl<MemoryAccess *> &WorkList,
907*0fca6ea1SDimitry Andric                           SmallPtrSetImpl<MemoryAccess *> &Visited) {
908*0fca6ea1SDimitry Andric     for (Use &U : Acc->uses()) {
909*0fca6ea1SDimitry Andric       auto *MA = cast<MemoryAccess>(U.getUser());
910*0fca6ea1SDimitry Andric       if (Visited.insert(MA).second)
911*0fca6ea1SDimitry Andric         WorkList.push_back(MA);
912*0fca6ea1SDimitry Andric     }
913*0fca6ea1SDimitry Andric   };
914*0fca6ea1SDimitry Andric 
915bdd1243dSDimitry Andric   LocationSize strengthenLocationSize(const Instruction *I,
916bdd1243dSDimitry Andric                                       LocationSize Size) const {
917bdd1243dSDimitry Andric     if (auto *CB = dyn_cast<CallBase>(I)) {
918bdd1243dSDimitry Andric       LibFunc F;
919bdd1243dSDimitry Andric       if (TLI.getLibFunc(*CB, F) && TLI.has(F) &&
920bdd1243dSDimitry Andric           (F == LibFunc_memset_chk || F == LibFunc_memcpy_chk)) {
921bdd1243dSDimitry Andric         // Use the precise location size specified by the 3rd argument
922bdd1243dSDimitry Andric         // for determining KillingI overwrites DeadLoc if it is a memset_chk
923bdd1243dSDimitry Andric         // instruction. memset_chk will write either the amount specified as 3rd
924bdd1243dSDimitry Andric         // argument or the function will immediately abort and exit the program.
925bdd1243dSDimitry Andric         // NOTE: AA may determine NoAlias if it can prove that the access size
926bdd1243dSDimitry Andric         // is larger than the allocation size due to that being UB. To avoid
927bdd1243dSDimitry Andric         // returning potentially invalid NoAlias results by AA, limit the use of
928bdd1243dSDimitry Andric         // the precise location size to isOverwrite.
929bdd1243dSDimitry Andric         if (const auto *Len = dyn_cast<ConstantInt>(CB->getArgOperand(2)))
930bdd1243dSDimitry Andric           return LocationSize::precise(Len->getZExtValue());
931bdd1243dSDimitry Andric       }
932bdd1243dSDimitry Andric     }
933bdd1243dSDimitry Andric     return Size;
934bdd1243dSDimitry Andric   }
935bdd1243dSDimitry Andric 
936349cc55cSDimitry Andric   /// Return 'OW_Complete' if a store to the 'KillingLoc' location (by \p
937349cc55cSDimitry Andric   /// KillingI instruction) completely overwrites a store to the 'DeadLoc'
938349cc55cSDimitry Andric   /// location (by \p DeadI instruction).
939349cc55cSDimitry Andric   /// Return OW_MaybePartial if \p KillingI does not completely overwrite
940349cc55cSDimitry Andric   /// \p DeadI, but they both write to the same underlying object. In that
941349cc55cSDimitry Andric   /// case, use isPartialOverwrite to check if \p KillingI partially overwrites
9424824e7fdSDimitry Andric   /// \p DeadI. Returns 'OR_None' if \p KillingI is known to not overwrite the
943349cc55cSDimitry Andric   /// \p DeadI. Returns 'OW_Unknown' if nothing can be determined.
944349cc55cSDimitry Andric   OverwriteResult isOverwrite(const Instruction *KillingI,
945349cc55cSDimitry Andric                               const Instruction *DeadI,
946349cc55cSDimitry Andric                               const MemoryLocation &KillingLoc,
947349cc55cSDimitry Andric                               const MemoryLocation &DeadLoc,
948349cc55cSDimitry Andric                               int64_t &KillingOff, int64_t &DeadOff) {
949fe6060f1SDimitry Andric     // AliasAnalysis does not always account for loops. Limit overwrite checks
950349cc55cSDimitry Andric     // to dependencies for which we can guarantee they are independent of any
951fe6060f1SDimitry Andric     // loops they are in.
952349cc55cSDimitry Andric     if (!isGuaranteedLoopIndependent(DeadI, KillingI, DeadLoc))
953fe6060f1SDimitry Andric       return OW_Unknown;
954fe6060f1SDimitry Andric 
955bdd1243dSDimitry Andric     LocationSize KillingLocSize =
956bdd1243dSDimitry Andric         strengthenLocationSize(KillingI, KillingLoc.Size);
95704eeddc0SDimitry Andric     const Value *DeadPtr = DeadLoc.Ptr->stripPointerCasts();
95804eeddc0SDimitry Andric     const Value *KillingPtr = KillingLoc.Ptr->stripPointerCasts();
95904eeddc0SDimitry Andric     const Value *DeadUndObj = getUnderlyingObject(DeadPtr);
96004eeddc0SDimitry Andric     const Value *KillingUndObj = getUnderlyingObject(KillingPtr);
96104eeddc0SDimitry Andric 
96204eeddc0SDimitry Andric     // Check whether the killing store overwrites the whole object, in which
96304eeddc0SDimitry Andric     // case the size/offset of the dead store does not matter.
9645f757f3fSDimitry Andric     if (DeadUndObj == KillingUndObj && KillingLocSize.isPrecise() &&
9655f757f3fSDimitry Andric         isIdentifiedObject(KillingUndObj)) {
9665f757f3fSDimitry Andric       std::optional<TypeSize> KillingUndObjSize =
9675f757f3fSDimitry Andric           getPointerSize(KillingUndObj, DL, TLI, &F);
9685f757f3fSDimitry Andric       if (KillingUndObjSize && *KillingUndObjSize == KillingLocSize.getValue())
96904eeddc0SDimitry Andric         return OW_Complete;
97004eeddc0SDimitry Andric     }
97104eeddc0SDimitry Andric 
972fe6060f1SDimitry Andric     // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
973fe6060f1SDimitry Andric     // get imprecise values here, though (except for unknown sizes).
974bdd1243dSDimitry Andric     if (!KillingLocSize.isPrecise() || !DeadLoc.Size.isPrecise()) {
975fe6060f1SDimitry Andric       // In case no constant size is known, try to an IR values for the number
976fe6060f1SDimitry Andric       // of bytes written and check if they match.
977349cc55cSDimitry Andric       const auto *KillingMemI = dyn_cast<MemIntrinsic>(KillingI);
978349cc55cSDimitry Andric       const auto *DeadMemI = dyn_cast<MemIntrinsic>(DeadI);
979349cc55cSDimitry Andric       if (KillingMemI && DeadMemI) {
980349cc55cSDimitry Andric         const Value *KillingV = KillingMemI->getLength();
981349cc55cSDimitry Andric         const Value *DeadV = DeadMemI->getLength();
982349cc55cSDimitry Andric         if (KillingV == DeadV && BatchAA.isMustAlias(DeadLoc, KillingLoc))
983fe6060f1SDimitry Andric           return OW_Complete;
984fe6060f1SDimitry Andric       }
985fe6060f1SDimitry Andric 
986fe6060f1SDimitry Andric       // Masked stores have imprecise locations, but we can reason about them
987fe6060f1SDimitry Andric       // to some extent.
988349cc55cSDimitry Andric       return isMaskedStoreOverwrite(KillingI, DeadI, BatchAA);
989fe6060f1SDimitry Andric     }
990fe6060f1SDimitry Andric 
9915f757f3fSDimitry Andric     const TypeSize KillingSize = KillingLocSize.getValue();
9925f757f3fSDimitry Andric     const TypeSize DeadSize = DeadLoc.Size.getValue();
9935f757f3fSDimitry Andric     // Bail on doing Size comparison which depends on AA for now
9945f757f3fSDimitry Andric     // TODO: Remove AnyScalable once Alias Analysis deal with scalable vectors
9955f757f3fSDimitry Andric     const bool AnyScalable =
9965f757f3fSDimitry Andric         DeadSize.isScalable() || KillingLocSize.isScalable();
997fe6060f1SDimitry Andric 
9985f757f3fSDimitry Andric     if (AnyScalable)
9995f757f3fSDimitry Andric       return OW_Unknown;
1000fe6060f1SDimitry Andric     // Query the alias information
1001349cc55cSDimitry Andric     AliasResult AAR = BatchAA.alias(KillingLoc, DeadLoc);
1002fe6060f1SDimitry Andric 
1003fe6060f1SDimitry Andric     // If the start pointers are the same, we just have to compare sizes to see if
1004349cc55cSDimitry Andric     // the killing store was larger than the dead store.
1005fe6060f1SDimitry Andric     if (AAR == AliasResult::MustAlias) {
1006349cc55cSDimitry Andric       // Make sure that the KillingSize size is >= the DeadSize size.
1007349cc55cSDimitry Andric       if (KillingSize >= DeadSize)
1008fe6060f1SDimitry Andric         return OW_Complete;
1009fe6060f1SDimitry Andric     }
1010fe6060f1SDimitry Andric 
1011fe6060f1SDimitry Andric     // If we hit a partial alias we may have a full overwrite
1012fe6060f1SDimitry Andric     if (AAR == AliasResult::PartialAlias && AAR.hasOffset()) {
1013fe6060f1SDimitry Andric       int32_t Off = AAR.getOffset();
1014349cc55cSDimitry Andric       if (Off >= 0 && (uint64_t)Off + DeadSize <= KillingSize)
1015fe6060f1SDimitry Andric         return OW_Complete;
1016fe6060f1SDimitry Andric     }
1017fe6060f1SDimitry Andric 
1018fe6060f1SDimitry Andric     // If we can't resolve the same pointers to the same object, then we can't
1019fe6060f1SDimitry Andric     // analyze them at all.
10204824e7fdSDimitry Andric     if (DeadUndObj != KillingUndObj) {
10214824e7fdSDimitry Andric       // Non aliasing stores to different objects don't overlap. Note that
10224824e7fdSDimitry Andric       // if the killing store is known to overwrite whole object (out of
10234824e7fdSDimitry Andric       // bounds access overwrites whole object as well) then it is assumed to
10244824e7fdSDimitry Andric       // completely overwrite any store to the same object even if they don't
10254824e7fdSDimitry Andric       // actually alias (see next check).
10264824e7fdSDimitry Andric       if (AAR == AliasResult::NoAlias)
10274824e7fdSDimitry Andric         return OW_None;
1028fe6060f1SDimitry Andric       return OW_Unknown;
10294824e7fdSDimitry Andric     }
1030fe6060f1SDimitry Andric 
1031fe6060f1SDimitry Andric     // Okay, we have stores to two completely different pointers.  Try to
1032fe6060f1SDimitry Andric     // decompose the pointer into a "base + constant_offset" form.  If the base
1033fe6060f1SDimitry Andric     // pointers are equal, then we can reason about the two stores.
1034349cc55cSDimitry Andric     DeadOff = 0;
1035349cc55cSDimitry Andric     KillingOff = 0;
1036349cc55cSDimitry Andric     const Value *DeadBasePtr =
1037349cc55cSDimitry Andric         GetPointerBaseWithConstantOffset(DeadPtr, DeadOff, DL);
1038349cc55cSDimitry Andric     const Value *KillingBasePtr =
1039349cc55cSDimitry Andric         GetPointerBaseWithConstantOffset(KillingPtr, KillingOff, DL);
1040fe6060f1SDimitry Andric 
1041349cc55cSDimitry Andric     // If the base pointers still differ, we have two completely different
1042349cc55cSDimitry Andric     // stores.
1043349cc55cSDimitry Andric     if (DeadBasePtr != KillingBasePtr)
1044fe6060f1SDimitry Andric       return OW_Unknown;
1045fe6060f1SDimitry Andric 
1046349cc55cSDimitry Andric     // The killing access completely overlaps the dead store if and only if
1047349cc55cSDimitry Andric     // both start and end of the dead one is "inside" the killing one:
1048349cc55cSDimitry Andric     //    |<->|--dead--|<->|
1049349cc55cSDimitry Andric     //    |-----killing------|
1050fe6060f1SDimitry Andric     // Accesses may overlap if and only if start of one of them is "inside"
1051fe6060f1SDimitry Andric     // another one:
1052349cc55cSDimitry Andric     //    |<->|--dead--|<-------->|
1053349cc55cSDimitry Andric     //    |-------killing--------|
1054fe6060f1SDimitry Andric     //           OR
1055349cc55cSDimitry Andric     //    |-------dead-------|
1056349cc55cSDimitry Andric     //    |<->|---killing---|<----->|
1057fe6060f1SDimitry Andric     //
1058fe6060f1SDimitry Andric     // We have to be careful here as *Off is signed while *.Size is unsigned.
1059fe6060f1SDimitry Andric 
1060349cc55cSDimitry Andric     // Check if the dead access starts "not before" the killing one.
1061349cc55cSDimitry Andric     if (DeadOff >= KillingOff) {
1062349cc55cSDimitry Andric       // If the dead access ends "not after" the killing access then the
1063349cc55cSDimitry Andric       // dead one is completely overwritten by the killing one.
1064349cc55cSDimitry Andric       if (uint64_t(DeadOff - KillingOff) + DeadSize <= KillingSize)
1065fe6060f1SDimitry Andric         return OW_Complete;
1066349cc55cSDimitry Andric       // If start of the dead access is "before" end of the killing access
1067349cc55cSDimitry Andric       // then accesses overlap.
1068349cc55cSDimitry Andric       else if ((uint64_t)(DeadOff - KillingOff) < KillingSize)
1069fe6060f1SDimitry Andric         return OW_MaybePartial;
1070fe6060f1SDimitry Andric     }
1071349cc55cSDimitry Andric     // If start of the killing access is "before" end of the dead access then
1072fe6060f1SDimitry Andric     // accesses overlap.
1073349cc55cSDimitry Andric     else if ((uint64_t)(KillingOff - DeadOff) < DeadSize) {
1074fe6060f1SDimitry Andric       return OW_MaybePartial;
1075fe6060f1SDimitry Andric     }
1076fe6060f1SDimitry Andric 
10774824e7fdSDimitry Andric     // Can reach here only if accesses are known not to overlap.
10784824e7fdSDimitry Andric     return OW_None;
1079fe6060f1SDimitry Andric   }
1080fe6060f1SDimitry Andric 
1081e8d8bef9SDimitry Andric   bool isInvisibleToCallerAfterRet(const Value *V) {
1082e8d8bef9SDimitry Andric     if (isa<AllocaInst>(V))
1083e8d8bef9SDimitry Andric       return true;
1084e8d8bef9SDimitry Andric     auto I = InvisibleToCallerAfterRet.insert({V, false});
1085e8d8bef9SDimitry Andric     if (I.second) {
108604eeddc0SDimitry Andric       if (!isInvisibleToCallerOnUnwind(V)) {
1087e8d8bef9SDimitry Andric         I.first->second = false;
108804eeddc0SDimitry Andric       } else if (isNoAliasCall(V)) {
10895f757f3fSDimitry Andric         I.first->second = !PointerMayBeCaptured(V, true, false);
1090e8d8bef9SDimitry Andric       }
1091e8d8bef9SDimitry Andric     }
1092e8d8bef9SDimitry Andric     return I.first->second;
1093e8d8bef9SDimitry Andric   }
1094e8d8bef9SDimitry Andric 
109504eeddc0SDimitry Andric   bool isInvisibleToCallerOnUnwind(const Value *V) {
109604eeddc0SDimitry Andric     bool RequiresNoCaptureBeforeUnwind;
109704eeddc0SDimitry Andric     if (!isNotVisibleOnUnwind(V, RequiresNoCaptureBeforeUnwind))
109804eeddc0SDimitry Andric       return false;
109904eeddc0SDimitry Andric     if (!RequiresNoCaptureBeforeUnwind)
1100e8d8bef9SDimitry Andric       return true;
110104eeddc0SDimitry Andric 
110204eeddc0SDimitry Andric     auto I = CapturedBeforeReturn.insert({V, true});
110304eeddc0SDimitry Andric     if (I.second)
1104e8d8bef9SDimitry Andric       // NOTE: This could be made more precise by PointerMayBeCapturedBefore
1105e8d8bef9SDimitry Andric       // with the killing MemoryDef. But we refrain from doing so for now to
1106e8d8bef9SDimitry Andric       // limit compile-time and this does not cause any changes to the number
1107e8d8bef9SDimitry Andric       // of stores removed on a large test set in practice.
11085f757f3fSDimitry Andric       I.first->second = PointerMayBeCaptured(V, false, true);
110904eeddc0SDimitry Andric     return !I.first->second;
1110e8d8bef9SDimitry Andric   }
1111e8d8bef9SDimitry Andric 
1112bdd1243dSDimitry Andric   std::optional<MemoryLocation> getLocForWrite(Instruction *I) const {
11135ffd83dbSDimitry Andric     if (!I->mayWriteToMemory())
1114bdd1243dSDimitry Andric       return std::nullopt;
11155ffd83dbSDimitry Andric 
11160eae32dcSDimitry Andric     if (auto *CB = dyn_cast<CallBase>(I))
11170eae32dcSDimitry Andric       return MemoryLocation::getForDest(CB, TLI);
11185ffd83dbSDimitry Andric 
11195ffd83dbSDimitry Andric     return MemoryLocation::getOrNone(I);
11205ffd83dbSDimitry Andric   }
11215ffd83dbSDimitry Andric 
11220eae32dcSDimitry Andric   /// Assuming this instruction has a dead analyzable write, can we delete
11230eae32dcSDimitry Andric   /// this instruction?
11240eae32dcSDimitry Andric   bool isRemovable(Instruction *I) {
11250eae32dcSDimitry Andric     assert(getLocForWrite(I) && "Must have analyzable write");
11260eae32dcSDimitry Andric 
11270eae32dcSDimitry Andric     // Don't remove volatile/atomic stores.
11280eae32dcSDimitry Andric     if (StoreInst *SI = dyn_cast<StoreInst>(I))
11290eae32dcSDimitry Andric       return SI->isUnordered();
11300eae32dcSDimitry Andric 
11310eae32dcSDimitry Andric     if (auto *CB = dyn_cast<CallBase>(I)) {
11320eae32dcSDimitry Andric       // Don't remove volatile memory intrinsics.
11330eae32dcSDimitry Andric       if (auto *MI = dyn_cast<MemIntrinsic>(CB))
11340eae32dcSDimitry Andric         return !MI->isVolatile();
11350eae32dcSDimitry Andric 
11360eae32dcSDimitry Andric       // Never remove dead lifetime intrinsics, e.g. because they are followed
11370eae32dcSDimitry Andric       // by a free.
11380eae32dcSDimitry Andric       if (CB->isLifetimeStartOrEnd())
11390eae32dcSDimitry Andric         return false;
11400eae32dcSDimitry Andric 
114181ad6265SDimitry Andric       return CB->use_empty() && CB->willReturn() && CB->doesNotThrow() &&
114281ad6265SDimitry Andric              !CB->isTerminator();
11430eae32dcSDimitry Andric     }
11440eae32dcSDimitry Andric 
11450eae32dcSDimitry Andric     return false;
11460eae32dcSDimitry Andric   }
11470eae32dcSDimitry Andric 
1148e8d8bef9SDimitry Andric   /// Returns true if \p UseInst completely overwrites \p DefLoc
1149e8d8bef9SDimitry Andric   /// (stored by \p DefInst).
1150e8d8bef9SDimitry Andric   bool isCompleteOverwrite(const MemoryLocation &DefLoc, Instruction *DefInst,
1151e8d8bef9SDimitry Andric                            Instruction *UseInst) {
11525ffd83dbSDimitry Andric     // UseInst has a MemoryDef associated in MemorySSA. It's possible for a
11535ffd83dbSDimitry Andric     // MemoryDef to not write to memory, e.g. a volatile load is modeled as a
11545ffd83dbSDimitry Andric     // MemoryDef.
11555ffd83dbSDimitry Andric     if (!UseInst->mayWriteToMemory())
11565ffd83dbSDimitry Andric       return false;
11575ffd83dbSDimitry Andric 
11585ffd83dbSDimitry Andric     if (auto *CB = dyn_cast<CallBase>(UseInst))
11595ffd83dbSDimitry Andric       if (CB->onlyAccessesInaccessibleMemory())
11605ffd83dbSDimitry Andric         return false;
11615ffd83dbSDimitry Andric 
11625ffd83dbSDimitry Andric     int64_t InstWriteOffset, DepWriteOffset;
11630eae32dcSDimitry Andric     if (auto CC = getLocForWrite(UseInst))
1164349cc55cSDimitry Andric       return isOverwrite(UseInst, DefInst, *CC, DefLoc, InstWriteOffset,
1165349cc55cSDimitry Andric                          DepWriteOffset) == OW_Complete;
1166e8d8bef9SDimitry Andric     return false;
11675ffd83dbSDimitry Andric   }
11685ffd83dbSDimitry Andric 
11695ffd83dbSDimitry Andric   /// Returns true if \p Def is not read before returning from the function.
1170*0fca6ea1SDimitry Andric   bool isWriteAtEndOfFunction(MemoryDef *Def, const MemoryLocation &DefLoc) {
11715ffd83dbSDimitry Andric     LLVM_DEBUG(dbgs() << "  Check if def " << *Def << " ("
11725ffd83dbSDimitry Andric                       << *Def->getMemoryInst()
11735ffd83dbSDimitry Andric                       << ") is at the end the function \n");
11745ffd83dbSDimitry Andric     SmallVector<MemoryAccess *, 4> WorkList;
11755ffd83dbSDimitry Andric     SmallPtrSet<MemoryAccess *, 8> Visited;
1176*0fca6ea1SDimitry Andric 
1177*0fca6ea1SDimitry Andric     pushMemUses(Def, WorkList, Visited);
11785ffd83dbSDimitry Andric     for (unsigned I = 0; I < WorkList.size(); I++) {
11795ffd83dbSDimitry Andric       if (WorkList.size() >= MemorySSAScanLimit) {
11805ffd83dbSDimitry Andric         LLVM_DEBUG(dbgs() << "  ... hit exploration limit.\n");
11815ffd83dbSDimitry Andric         return false;
11825ffd83dbSDimitry Andric       }
11835ffd83dbSDimitry Andric 
11845ffd83dbSDimitry Andric       MemoryAccess *UseAccess = WorkList[I];
1185bdd1243dSDimitry Andric       if (isa<MemoryPhi>(UseAccess)) {
1186bdd1243dSDimitry Andric         // AliasAnalysis does not account for loops. Limit elimination to
1187bdd1243dSDimitry Andric         // candidates for which we can guarantee they always store to the same
1188bdd1243dSDimitry Andric         // memory location.
1189*0fca6ea1SDimitry Andric         if (!isGuaranteedLoopInvariant(DefLoc.Ptr))
1190e8d8bef9SDimitry Andric           return false;
11915ffd83dbSDimitry Andric 
1192*0fca6ea1SDimitry Andric         pushMemUses(cast<MemoryPhi>(UseAccess), WorkList, Visited);
1193bdd1243dSDimitry Andric         continue;
1194bdd1243dSDimitry Andric       }
11955ffd83dbSDimitry Andric       // TODO: Checking for aliasing is expensive. Consider reducing the amount
11965ffd83dbSDimitry Andric       // of times this is called and/or caching it.
11975ffd83dbSDimitry Andric       Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1198*0fca6ea1SDimitry Andric       if (isReadClobber(DefLoc, UseInst)) {
11995ffd83dbSDimitry Andric         LLVM_DEBUG(dbgs() << "  ... hit read clobber " << *UseInst << ".\n");
12005ffd83dbSDimitry Andric         return false;
12015ffd83dbSDimitry Andric       }
12025ffd83dbSDimitry Andric 
12035ffd83dbSDimitry Andric       if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
1204*0fca6ea1SDimitry Andric         pushMemUses(UseDef, WorkList, Visited);
12055ffd83dbSDimitry Andric     }
12065ffd83dbSDimitry Andric     return true;
12075ffd83dbSDimitry Andric   }
12085ffd83dbSDimitry Andric 
12095ffd83dbSDimitry Andric   /// If \p I is a memory  terminator like llvm.lifetime.end or free, return a
12105ffd83dbSDimitry Andric   /// pair with the MemoryLocation terminated by \p I and a boolean flag
12115ffd83dbSDimitry Andric   /// indicating whether \p I is a free-like call.
1212bdd1243dSDimitry Andric   std::optional<std::pair<MemoryLocation, bool>>
12135ffd83dbSDimitry Andric   getLocForTerminator(Instruction *I) const {
12145ffd83dbSDimitry Andric     uint64_t Len;
12155ffd83dbSDimitry Andric     Value *Ptr;
12165ffd83dbSDimitry Andric     if (match(I, m_Intrinsic<Intrinsic::lifetime_end>(m_ConstantInt(Len),
12175ffd83dbSDimitry Andric                                                       m_Value(Ptr))))
12185ffd83dbSDimitry Andric       return {std::make_pair(MemoryLocation(Ptr, Len), false)};
12195ffd83dbSDimitry Andric 
12205ffd83dbSDimitry Andric     if (auto *CB = dyn_cast<CallBase>(I)) {
1221fcaf7f86SDimitry Andric       if (Value *FreedOp = getFreedOperand(CB, &TLI))
1222fcaf7f86SDimitry Andric         return {std::make_pair(MemoryLocation::getAfter(FreedOp), true)};
12235ffd83dbSDimitry Andric     }
12245ffd83dbSDimitry Andric 
1225bdd1243dSDimitry Andric     return std::nullopt;
12265ffd83dbSDimitry Andric   }
12275ffd83dbSDimitry Andric 
12285ffd83dbSDimitry Andric   /// Returns true if \p I is a memory terminator instruction like
12295ffd83dbSDimitry Andric   /// llvm.lifetime.end or free.
12305ffd83dbSDimitry Andric   bool isMemTerminatorInst(Instruction *I) const {
1231fcaf7f86SDimitry Andric     auto *CB = dyn_cast<CallBase>(I);
1232fcaf7f86SDimitry Andric     return CB && (CB->getIntrinsicID() == Intrinsic::lifetime_end ||
1233fcaf7f86SDimitry Andric                   getFreedOperand(CB, &TLI) != nullptr);
12345ffd83dbSDimitry Andric   }
12355ffd83dbSDimitry Andric 
1236e8d8bef9SDimitry Andric   /// Returns true if \p MaybeTerm is a memory terminator for \p Loc from
1237e8d8bef9SDimitry Andric   /// instruction \p AccessI.
1238e8d8bef9SDimitry Andric   bool isMemTerminator(const MemoryLocation &Loc, Instruction *AccessI,
1239e8d8bef9SDimitry Andric                        Instruction *MaybeTerm) {
1240bdd1243dSDimitry Andric     std::optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
12415ffd83dbSDimitry Andric         getLocForTerminator(MaybeTerm);
12425ffd83dbSDimitry Andric 
12435ffd83dbSDimitry Andric     if (!MaybeTermLoc)
12445ffd83dbSDimitry Andric       return false;
12455ffd83dbSDimitry Andric 
12465ffd83dbSDimitry Andric     // If the terminator is a free-like call, all accesses to the underlying
12475ffd83dbSDimitry Andric     // object can be considered terminated.
1248e8d8bef9SDimitry Andric     if (getUnderlyingObject(Loc.Ptr) !=
1249e8d8bef9SDimitry Andric         getUnderlyingObject(MaybeTermLoc->first.Ptr))
1250e8d8bef9SDimitry Andric       return false;
1251e8d8bef9SDimitry Andric 
1252e8d8bef9SDimitry Andric     auto TermLoc = MaybeTermLoc->first;
12535ffd83dbSDimitry Andric     if (MaybeTermLoc->second) {
1254e8d8bef9SDimitry Andric       const Value *LocUO = getUnderlyingObject(Loc.Ptr);
1255e8d8bef9SDimitry Andric       return BatchAA.isMustAlias(TermLoc.Ptr, LocUO);
12565ffd83dbSDimitry Andric     }
1257349cc55cSDimitry Andric     int64_t InstWriteOffset = 0;
1258349cc55cSDimitry Andric     int64_t DepWriteOffset = 0;
1259349cc55cSDimitry Andric     return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, InstWriteOffset,
1260349cc55cSDimitry Andric                        DepWriteOffset) == OW_Complete;
12615ffd83dbSDimitry Andric   }
12625ffd83dbSDimitry Andric 
12635ffd83dbSDimitry Andric   // Returns true if \p Use may read from \p DefLoc.
1264e8d8bef9SDimitry Andric   bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {
1265e8d8bef9SDimitry Andric     if (isNoopIntrinsic(UseInst))
1266e8d8bef9SDimitry Andric       return false;
1267e8d8bef9SDimitry Andric 
1268e8d8bef9SDimitry Andric     // Monotonic or weaker atomic stores can be re-ordered and do not need to be
1269e8d8bef9SDimitry Andric     // treated as read clobber.
1270e8d8bef9SDimitry Andric     if (auto SI = dyn_cast<StoreInst>(UseInst))
1271e8d8bef9SDimitry Andric       return isStrongerThan(SI->getOrdering(), AtomicOrdering::Monotonic);
1272e8d8bef9SDimitry Andric 
12735ffd83dbSDimitry Andric     if (!UseInst->mayReadFromMemory())
12745ffd83dbSDimitry Andric       return false;
12755ffd83dbSDimitry Andric 
12765ffd83dbSDimitry Andric     if (auto *CB = dyn_cast<CallBase>(UseInst))
12775ffd83dbSDimitry Andric       if (CB->onlyAccessesInaccessibleMemory())
12785ffd83dbSDimitry Andric         return false;
12795ffd83dbSDimitry Andric 
1280e8d8bef9SDimitry Andric     return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));
12815ffd83dbSDimitry Andric   }
12825ffd83dbSDimitry Andric 
1283fe6060f1SDimitry Andric   /// Returns true if a dependency between \p Current and \p KillingDef is
1284fe6060f1SDimitry Andric   /// guaranteed to be loop invariant for the loops that they are in. Either
1285fe6060f1SDimitry Andric   /// because they are known to be in the same block, in the same loop level or
1286fe6060f1SDimitry Andric   /// by guaranteeing that \p CurrentLoc only references a single MemoryLocation
1287fe6060f1SDimitry Andric   /// during execution of the containing function.
1288fe6060f1SDimitry Andric   bool isGuaranteedLoopIndependent(const Instruction *Current,
1289fe6060f1SDimitry Andric                                    const Instruction *KillingDef,
1290fe6060f1SDimitry Andric                                    const MemoryLocation &CurrentLoc) {
1291fe6060f1SDimitry Andric     // If the dependency is within the same block or loop level (being careful
1292fe6060f1SDimitry Andric     // of irreducible loops), we know that AA will return a valid result for the
1293fe6060f1SDimitry Andric     // memory dependency. (Both at the function level, outside of any loop,
1294fe6060f1SDimitry Andric     // would also be valid but we currently disable that to limit compile time).
1295fe6060f1SDimitry Andric     if (Current->getParent() == KillingDef->getParent())
1296fe6060f1SDimitry Andric       return true;
1297fe6060f1SDimitry Andric     const Loop *CurrentLI = LI.getLoopFor(Current->getParent());
1298fe6060f1SDimitry Andric     if (!ContainsIrreducibleLoops && CurrentLI &&
1299fe6060f1SDimitry Andric         CurrentLI == LI.getLoopFor(KillingDef->getParent()))
1300fe6060f1SDimitry Andric       return true;
1301fe6060f1SDimitry Andric     // Otherwise check the memory location is invariant to any loops.
1302fe6060f1SDimitry Andric     return isGuaranteedLoopInvariant(CurrentLoc.Ptr);
1303fe6060f1SDimitry Andric   }
1304fe6060f1SDimitry Andric 
1305e8d8bef9SDimitry Andric   /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
1306e8d8bef9SDimitry Andric   /// loop. In particular, this guarantees that it only references a single
1307e8d8bef9SDimitry Andric   /// MemoryLocation during execution of the containing function.
1308fe6060f1SDimitry Andric   bool isGuaranteedLoopInvariant(const Value *Ptr) {
1309e8d8bef9SDimitry Andric     Ptr = Ptr->stripPointerCasts();
13100eae32dcSDimitry Andric     if (auto *GEP = dyn_cast<GEPOperator>(Ptr))
13110eae32dcSDimitry Andric       if (GEP->hasAllConstantIndices())
13120eae32dcSDimitry Andric         Ptr = GEP->getPointerOperand()->stripPointerCasts();
1313e8d8bef9SDimitry Andric 
1314bdd1243dSDimitry Andric     if (auto *I = dyn_cast<Instruction>(Ptr)) {
1315bdd1243dSDimitry Andric       return I->getParent()->isEntryBlock() ||
1316bdd1243dSDimitry Andric              (!ContainsIrreducibleLoops && !LI.getLoopFor(I->getParent()));
1317bdd1243dSDimitry Andric     }
1318e8d8bef9SDimitry Andric     return true;
1319e8d8bef9SDimitry Andric   }
1320e8d8bef9SDimitry Andric 
1321349cc55cSDimitry Andric   // Find a MemoryDef writing to \p KillingLoc and dominating \p StartAccess,
1322349cc55cSDimitry Andric   // with no read access between them or on any other path to a function exit
1323349cc55cSDimitry Andric   // block if \p KillingLoc is not accessible after the function returns. If
1324bdd1243dSDimitry Andric   // there is no such MemoryDef, return std::nullopt. The returned value may not
1325349cc55cSDimitry Andric   // (completely) overwrite \p KillingLoc. Currently we bail out when we
1326349cc55cSDimitry Andric   // encounter an aliasing MemoryUse (read).
1327bdd1243dSDimitry Andric   std::optional<MemoryAccess *>
1328e8d8bef9SDimitry Andric   getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,
1329349cc55cSDimitry Andric                   const MemoryLocation &KillingLoc, const Value *KillingUndObj,
1330e8d8bef9SDimitry Andric                   unsigned &ScanLimit, unsigned &WalkerStepLimit,
1331e8d8bef9SDimitry Andric                   bool IsMemTerm, unsigned &PartialLimit) {
1332e8d8bef9SDimitry Andric     if (ScanLimit == 0 || WalkerStepLimit == 0) {
1333e8d8bef9SDimitry Andric       LLVM_DEBUG(dbgs() << "\n    ...  hit scan limit\n");
1334bdd1243dSDimitry Andric       return std::nullopt;
1335e8d8bef9SDimitry Andric     }
1336e8d8bef9SDimitry Andric 
1337e8d8bef9SDimitry Andric     MemoryAccess *Current = StartAccess;
1338e8d8bef9SDimitry Andric     Instruction *KillingI = KillingDef->getMemoryInst();
1339e8d8bef9SDimitry Andric     LLVM_DEBUG(dbgs() << "  trying to get dominating access\n");
1340e8d8bef9SDimitry Andric 
13414824e7fdSDimitry Andric     // Only optimize defining access of KillingDef when directly starting at its
13424824e7fdSDimitry Andric     // defining access. The defining access also must only access KillingLoc. At
13434824e7fdSDimitry Andric     // the moment we only support instructions with a single write location, so
13444824e7fdSDimitry Andric     // it should be sufficient to disable optimizations for instructions that
13454824e7fdSDimitry Andric     // also read from memory.
13464824e7fdSDimitry Andric     bool CanOptimize = OptimizeMemorySSA &&
13474824e7fdSDimitry Andric                        KillingDef->getDefiningAccess() == StartAccess &&
13484824e7fdSDimitry Andric                        !KillingI->mayReadFromMemory();
13494824e7fdSDimitry Andric 
1350e8d8bef9SDimitry Andric     // Find the next clobbering Mod access for DefLoc, starting at StartAccess.
1351bdd1243dSDimitry Andric     std::optional<MemoryLocation> CurrentLoc;
1352fe6060f1SDimitry Andric     for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
1353e8d8bef9SDimitry Andric       LLVM_DEBUG({
1354e8d8bef9SDimitry Andric         dbgs() << "   visiting " << *Current;
1355e8d8bef9SDimitry Andric         if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef>(Current))
1356e8d8bef9SDimitry Andric           dbgs() << " (" << *cast<MemoryUseOrDef>(Current)->getMemoryInst()
1357e8d8bef9SDimitry Andric                  << ")";
1358e8d8bef9SDimitry Andric         dbgs() << "\n";
1359e8d8bef9SDimitry Andric       });
1360e8d8bef9SDimitry Andric 
13615ffd83dbSDimitry Andric       // Reached TOP.
1362e8d8bef9SDimitry Andric       if (MSSA.isLiveOnEntryDef(Current)) {
1363e8d8bef9SDimitry Andric         LLVM_DEBUG(dbgs() << "   ...  found LiveOnEntryDef\n");
136481ad6265SDimitry Andric         if (CanOptimize && Current != KillingDef->getDefiningAccess())
136581ad6265SDimitry Andric           // The first clobbering def is... none.
136681ad6265SDimitry Andric           KillingDef->setOptimized(Current);
1367bdd1243dSDimitry Andric         return std::nullopt;
1368e8d8bef9SDimitry Andric       }
13695ffd83dbSDimitry Andric 
1370e8d8bef9SDimitry Andric       // Cost of a step. Accesses in the same block are more likely to be valid
1371e8d8bef9SDimitry Andric       // candidates for elimination, hence consider them cheaper.
1372e8d8bef9SDimitry Andric       unsigned StepCost = KillingDef->getBlock() == Current->getBlock()
1373e8d8bef9SDimitry Andric                               ? MemorySSASameBBStepCost
1374e8d8bef9SDimitry Andric                               : MemorySSAOtherBBStepCost;
1375e8d8bef9SDimitry Andric       if (WalkerStepLimit <= StepCost) {
1376e8d8bef9SDimitry Andric         LLVM_DEBUG(dbgs() << "   ...  hit walker step limit\n");
1377bdd1243dSDimitry Andric         return std::nullopt;
1378e8d8bef9SDimitry Andric       }
1379e8d8bef9SDimitry Andric       WalkerStepLimit -= StepCost;
1380e8d8bef9SDimitry Andric 
1381e8d8bef9SDimitry Andric       // Return for MemoryPhis. They cannot be eliminated directly and the
1382e8d8bef9SDimitry Andric       // caller is responsible for traversing them.
13835ffd83dbSDimitry Andric       if (isa<MemoryPhi>(Current)) {
1384e8d8bef9SDimitry Andric         LLVM_DEBUG(dbgs() << "   ...  found MemoryPhi\n");
1385e8d8bef9SDimitry Andric         return Current;
13865ffd83dbSDimitry Andric       }
1387e8d8bef9SDimitry Andric 
1388e8d8bef9SDimitry Andric       // Below, check if CurrentDef is a valid candidate to be eliminated by
1389e8d8bef9SDimitry Andric       // KillingDef. If it is not, check the next candidate.
1390e8d8bef9SDimitry Andric       MemoryDef *CurrentDef = cast<MemoryDef>(Current);
1391e8d8bef9SDimitry Andric       Instruction *CurrentI = CurrentDef->getMemoryInst();
1392e8d8bef9SDimitry Andric 
139304eeddc0SDimitry Andric       if (canSkipDef(CurrentDef, !isInvisibleToCallerOnUnwind(KillingUndObj))) {
13944824e7fdSDimitry Andric         CanOptimize = false;
1395e8d8bef9SDimitry Andric         continue;
13964824e7fdSDimitry Andric       }
1397e8d8bef9SDimitry Andric 
1398e8d8bef9SDimitry Andric       // Before we try to remove anything, check for any extra throwing
1399e8d8bef9SDimitry Andric       // instructions that block us from DSEing
1400349cc55cSDimitry Andric       if (mayThrowBetween(KillingI, CurrentI, KillingUndObj)) {
1401e8d8bef9SDimitry Andric         LLVM_DEBUG(dbgs() << "  ... skip, may throw!\n");
1402bdd1243dSDimitry Andric         return std::nullopt;
1403e8d8bef9SDimitry Andric       }
1404e8d8bef9SDimitry Andric 
1405e8d8bef9SDimitry Andric       // Check for anything that looks like it will be a barrier to further
1406e8d8bef9SDimitry Andric       // removal
1407349cc55cSDimitry Andric       if (isDSEBarrier(KillingUndObj, CurrentI)) {
1408e8d8bef9SDimitry Andric         LLVM_DEBUG(dbgs() << "  ... skip, barrier\n");
1409bdd1243dSDimitry Andric         return std::nullopt;
1410e8d8bef9SDimitry Andric       }
1411e8d8bef9SDimitry Andric 
1412e8d8bef9SDimitry Andric       // If Current is known to be on path that reads DefLoc or is a read
1413e8d8bef9SDimitry Andric       // clobber, bail out, as the path is not profitable. We skip this check
1414e8d8bef9SDimitry Andric       // for intrinsic calls, because the code knows how to handle memcpy
1415e8d8bef9SDimitry Andric       // intrinsics.
1416349cc55cSDimitry Andric       if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(KillingLoc, CurrentI))
1417bdd1243dSDimitry Andric         return std::nullopt;
14185ffd83dbSDimitry Andric 
1419e8d8bef9SDimitry Andric       // Quick check if there are direct uses that are read-clobbers.
1420349cc55cSDimitry Andric       if (any_of(Current->uses(), [this, &KillingLoc, StartAccess](Use &U) {
1421e8d8bef9SDimitry Andric             if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
1422e8d8bef9SDimitry Andric               return !MSSA.dominates(StartAccess, UseOrDef) &&
1423349cc55cSDimitry Andric                      isReadClobber(KillingLoc, UseOrDef->getMemoryInst());
1424e8d8bef9SDimitry Andric             return false;
1425e8d8bef9SDimitry Andric           })) {
1426e8d8bef9SDimitry Andric         LLVM_DEBUG(dbgs() << "   ...  found a read clobber\n");
1427bdd1243dSDimitry Andric         return std::nullopt;
14285ffd83dbSDimitry Andric       }
14295ffd83dbSDimitry Andric 
14304824e7fdSDimitry Andric       // If Current does not have an analyzable write location or is not
14314824e7fdSDimitry Andric       // removable, skip it.
14320eae32dcSDimitry Andric       CurrentLoc = getLocForWrite(CurrentI);
14334824e7fdSDimitry Andric       if (!CurrentLoc || !isRemovable(CurrentI)) {
14344824e7fdSDimitry Andric         CanOptimize = false;
1435e8d8bef9SDimitry Andric         continue;
14364824e7fdSDimitry Andric       }
1437e8d8bef9SDimitry Andric 
1438e8d8bef9SDimitry Andric       // AliasAnalysis does not account for loops. Limit elimination to
1439e8d8bef9SDimitry Andric       // candidates for which we can guarantee they always store to the same
1440fe6060f1SDimitry Andric       // memory location and not located in different loops.
1441fe6060f1SDimitry Andric       if (!isGuaranteedLoopIndependent(CurrentI, KillingI, *CurrentLoc)) {
1442fe6060f1SDimitry Andric         LLVM_DEBUG(dbgs() << "  ... not guaranteed loop independent\n");
14434824e7fdSDimitry Andric         CanOptimize = false;
1444e8d8bef9SDimitry Andric         continue;
1445e8d8bef9SDimitry Andric       }
1446e8d8bef9SDimitry Andric 
1447e8d8bef9SDimitry Andric       if (IsMemTerm) {
1448e8d8bef9SDimitry Andric         // If the killing def is a memory terminator (e.g. lifetime.end), check
1449e8d8bef9SDimitry Andric         // the next candidate if the current Current does not write the same
1450e8d8bef9SDimitry Andric         // underlying object as the terminator.
14514824e7fdSDimitry Andric         if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {
14524824e7fdSDimitry Andric           CanOptimize = false;
1453e8d8bef9SDimitry Andric           continue;
14544824e7fdSDimitry Andric         }
1455e8d8bef9SDimitry Andric       } else {
1456349cc55cSDimitry Andric         int64_t KillingOffset = 0;
1457349cc55cSDimitry Andric         int64_t DeadOffset = 0;
1458349cc55cSDimitry Andric         auto OR = isOverwrite(KillingI, CurrentI, KillingLoc, *CurrentLoc,
1459349cc55cSDimitry Andric                               KillingOffset, DeadOffset);
14604824e7fdSDimitry Andric         if (CanOptimize) {
14614824e7fdSDimitry Andric           // CurrentDef is the earliest write clobber of KillingDef. Use it as
14624824e7fdSDimitry Andric           // optimized access. Do not optimize if CurrentDef is already the
14634824e7fdSDimitry Andric           // defining access of KillingDef.
14644824e7fdSDimitry Andric           if (CurrentDef != KillingDef->getDefiningAccess() &&
14654824e7fdSDimitry Andric               (OR == OW_Complete || OR == OW_MaybePartial))
14664824e7fdSDimitry Andric             KillingDef->setOptimized(CurrentDef);
14674824e7fdSDimitry Andric 
14684824e7fdSDimitry Andric           // Once a may-aliasing def is encountered do not set an optimized
14694824e7fdSDimitry Andric           // access.
14704824e7fdSDimitry Andric           if (OR != OW_None)
14714824e7fdSDimitry Andric             CanOptimize = false;
14724824e7fdSDimitry Andric         }
14734824e7fdSDimitry Andric 
1474e8d8bef9SDimitry Andric         // If Current does not write to the same object as KillingDef, check
1475e8d8bef9SDimitry Andric         // the next candidate.
14764824e7fdSDimitry Andric         if (OR == OW_Unknown || OR == OW_None)
1477fe6060f1SDimitry Andric           continue;
1478fe6060f1SDimitry Andric         else if (OR == OW_MaybePartial) {
1479e8d8bef9SDimitry Andric           // If KillingDef only partially overwrites Current, check the next
1480e8d8bef9SDimitry Andric           // candidate if the partial step limit is exceeded. This aggressively
1481e8d8bef9SDimitry Andric           // limits the number of candidates for partial store elimination,
1482e8d8bef9SDimitry Andric           // which are less likely to be removable in the end.
1483e8d8bef9SDimitry Andric           if (PartialLimit <= 1) {
1484e8d8bef9SDimitry Andric             WalkerStepLimit -= 1;
14854824e7fdSDimitry Andric             LLVM_DEBUG(dbgs() << "   ... reached partial limit ... continue with next access\n");
1486e8d8bef9SDimitry Andric             continue;
1487e8d8bef9SDimitry Andric           }
1488e8d8bef9SDimitry Andric           PartialLimit -= 1;
1489e8d8bef9SDimitry Andric         }
1490e8d8bef9SDimitry Andric       }
1491fe6060f1SDimitry Andric       break;
1492fe6060f1SDimitry Andric     };
14935ffd83dbSDimitry Andric 
14945ffd83dbSDimitry Andric     // Accesses to objects accessible after the function returns can only be
1495349cc55cSDimitry Andric     // eliminated if the access is dead along all paths to the exit. Collect
14965ffd83dbSDimitry Andric     // the blocks with killing (=completely overwriting MemoryDefs) and check if
1497349cc55cSDimitry Andric     // they cover all paths from MaybeDeadAccess to any function exit.
1498e8d8bef9SDimitry Andric     SmallPtrSet<Instruction *, 16> KillingDefs;
1499e8d8bef9SDimitry Andric     KillingDefs.insert(KillingDef->getMemoryInst());
1500349cc55cSDimitry Andric     MemoryAccess *MaybeDeadAccess = Current;
1501349cc55cSDimitry Andric     MemoryLocation MaybeDeadLoc = *CurrentLoc;
1502349cc55cSDimitry Andric     Instruction *MaybeDeadI = cast<MemoryDef>(MaybeDeadAccess)->getMemoryInst();
1503349cc55cSDimitry Andric     LLVM_DEBUG(dbgs() << "  Checking for reads of " << *MaybeDeadAccess << " ("
1504349cc55cSDimitry Andric                       << *MaybeDeadI << ")\n");
15055ffd83dbSDimitry Andric 
1506*0fca6ea1SDimitry Andric     SmallVector<MemoryAccess *, 32> WorkList;
1507*0fca6ea1SDimitry Andric     SmallPtrSet<MemoryAccess *, 32> Visited;
1508*0fca6ea1SDimitry Andric     pushMemUses(MaybeDeadAccess, WorkList, Visited);
15095ffd83dbSDimitry Andric 
1510349cc55cSDimitry Andric     // Check if DeadDef may be read.
15115ffd83dbSDimitry Andric     for (unsigned I = 0; I < WorkList.size(); I++) {
15125ffd83dbSDimitry Andric       MemoryAccess *UseAccess = WorkList[I];
15135ffd83dbSDimitry Andric 
15145ffd83dbSDimitry Andric       LLVM_DEBUG(dbgs() << "   " << *UseAccess);
1515e8d8bef9SDimitry Andric       // Bail out if the number of accesses to check exceeds the scan limit.
1516e8d8bef9SDimitry Andric       if (ScanLimit < (WorkList.size() - I)) {
15175ffd83dbSDimitry Andric         LLVM_DEBUG(dbgs() << "\n    ...  hit scan limit\n");
1518bdd1243dSDimitry Andric         return std::nullopt;
15195ffd83dbSDimitry Andric       }
1520e8d8bef9SDimitry Andric       --ScanLimit;
1521e8d8bef9SDimitry Andric       NumDomMemDefChecks++;
15225ffd83dbSDimitry Andric 
15235ffd83dbSDimitry Andric       if (isa<MemoryPhi>(UseAccess)) {
1524e8d8bef9SDimitry Andric         if (any_of(KillingDefs, [this, UseAccess](Instruction *KI) {
1525e8d8bef9SDimitry Andric               return DT.properlyDominates(KI->getParent(),
1526e8d8bef9SDimitry Andric                                           UseAccess->getBlock());
1527e8d8bef9SDimitry Andric             })) {
1528e8d8bef9SDimitry Andric           LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing block\n");
1529e8d8bef9SDimitry Andric           continue;
1530e8d8bef9SDimitry Andric         }
15315ffd83dbSDimitry Andric         LLVM_DEBUG(dbgs() << "\n    ... adding PHI uses\n");
1532*0fca6ea1SDimitry Andric         pushMemUses(UseAccess, WorkList, Visited);
15335ffd83dbSDimitry Andric         continue;
15345ffd83dbSDimitry Andric       }
15355ffd83dbSDimitry Andric 
15365ffd83dbSDimitry Andric       Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
15375ffd83dbSDimitry Andric       LLVM_DEBUG(dbgs() << " (" << *UseInst << ")\n");
15385ffd83dbSDimitry Andric 
1539e8d8bef9SDimitry Andric       if (any_of(KillingDefs, [this, UseInst](Instruction *KI) {
1540e8d8bef9SDimitry Andric             return DT.dominates(KI, UseInst);
1541e8d8bef9SDimitry Andric           })) {
1542e8d8bef9SDimitry Andric         LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing def\n");
15435ffd83dbSDimitry Andric         continue;
15445ffd83dbSDimitry Andric       }
15455ffd83dbSDimitry Andric 
15465ffd83dbSDimitry Andric       // A memory terminator kills all preceeding MemoryDefs and all succeeding
15475ffd83dbSDimitry Andric       // MemoryAccesses. We do not have to check it's users.
1548349cc55cSDimitry Andric       if (isMemTerminator(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1549e8d8bef9SDimitry Andric         LLVM_DEBUG(
1550e8d8bef9SDimitry Andric             dbgs()
1551e8d8bef9SDimitry Andric             << " ... skipping, memterminator invalidates following accesses\n");
15525ffd83dbSDimitry Andric         continue;
1553e8d8bef9SDimitry Andric       }
1554e8d8bef9SDimitry Andric 
1555e8d8bef9SDimitry Andric       if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
1556e8d8bef9SDimitry Andric         LLVM_DEBUG(dbgs() << "    ... adding uses of intrinsic\n");
1557*0fca6ea1SDimitry Andric         pushMemUses(UseAccess, WorkList, Visited);
1558e8d8bef9SDimitry Andric         continue;
1559e8d8bef9SDimitry Andric       }
1560e8d8bef9SDimitry Andric 
156104eeddc0SDimitry Andric       if (UseInst->mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj)) {
1562e8d8bef9SDimitry Andric         LLVM_DEBUG(dbgs() << "  ... found throwing instruction\n");
1563bdd1243dSDimitry Andric         return std::nullopt;
1564e8d8bef9SDimitry Andric       }
15655ffd83dbSDimitry Andric 
15665ffd83dbSDimitry Andric       // Uses which may read the original MemoryDef mean we cannot eliminate the
15675ffd83dbSDimitry Andric       // original MD. Stop walk.
1568349cc55cSDimitry Andric       if (isReadClobber(MaybeDeadLoc, UseInst)) {
15695ffd83dbSDimitry Andric         LLVM_DEBUG(dbgs() << "    ... found read clobber\n");
1570bdd1243dSDimitry Andric         return std::nullopt;
15715ffd83dbSDimitry Andric       }
15725ffd83dbSDimitry Andric 
1573fe6060f1SDimitry Andric       // If this worklist walks back to the original memory access (and the
1574fe6060f1SDimitry Andric       // pointer is not guarenteed loop invariant) then we cannot assume that a
1575fe6060f1SDimitry Andric       // store kills itself.
1576349cc55cSDimitry Andric       if (MaybeDeadAccess == UseAccess &&
1577349cc55cSDimitry Andric           !isGuaranteedLoopInvariant(MaybeDeadLoc.Ptr)) {
1578fe6060f1SDimitry Andric         LLVM_DEBUG(dbgs() << "    ... found not loop invariant self access\n");
1579bdd1243dSDimitry Andric         return std::nullopt;
1580fe6060f1SDimitry Andric       }
1581349cc55cSDimitry Andric       // Otherwise, for the KillingDef and MaybeDeadAccess we only have to check
1582fe6060f1SDimitry Andric       // if it reads the memory location.
15835ffd83dbSDimitry Andric       // TODO: It would probably be better to check for self-reads before
15845ffd83dbSDimitry Andric       // calling the function.
1585349cc55cSDimitry Andric       if (KillingDef == UseAccess || MaybeDeadAccess == UseAccess) {
15865ffd83dbSDimitry Andric         LLVM_DEBUG(dbgs() << "    ... skipping killing def/dom access\n");
15875ffd83dbSDimitry Andric         continue;
15885ffd83dbSDimitry Andric       }
15895ffd83dbSDimitry Andric 
15905ffd83dbSDimitry Andric       // Check all uses for MemoryDefs, except for defs completely overwriting
15915ffd83dbSDimitry Andric       // the original location. Otherwise we have to check uses of *all*
15925ffd83dbSDimitry Andric       // MemoryDefs we discover, including non-aliasing ones. Otherwise we might
15935ffd83dbSDimitry Andric       // miss cases like the following
1594349cc55cSDimitry Andric       //   1 = Def(LoE) ; <----- DeadDef stores [0,1]
15955ffd83dbSDimitry Andric       //   2 = Def(1)   ; (2, 1) = NoAlias,   stores [2,3]
15965ffd83dbSDimitry Andric       //   Use(2)       ; MayAlias 2 *and* 1, loads [0, 3].
15975ffd83dbSDimitry Andric       //                  (The Use points to the *first* Def it may alias)
15985ffd83dbSDimitry Andric       //   3 = Def(1)   ; <---- Current  (3, 2) = NoAlias, (3,1) = MayAlias,
15995ffd83dbSDimitry Andric       //                  stores [0,1]
16005ffd83dbSDimitry Andric       if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
1601349cc55cSDimitry Andric         if (isCompleteOverwrite(MaybeDeadLoc, MaybeDeadI, UseInst)) {
16025ffd83dbSDimitry Andric           BasicBlock *MaybeKillingBlock = UseInst->getParent();
16035ffd83dbSDimitry Andric           if (PostOrderNumbers.find(MaybeKillingBlock)->second <
1604349cc55cSDimitry Andric               PostOrderNumbers.find(MaybeDeadAccess->getBlock())->second) {
1605349cc55cSDimitry Andric             if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1606e8d8bef9SDimitry Andric               LLVM_DEBUG(dbgs()
1607e8d8bef9SDimitry Andric                          << "    ... found killing def " << *UseInst << "\n");
1608e8d8bef9SDimitry Andric               KillingDefs.insert(UseInst);
16095ffd83dbSDimitry Andric             }
1610fe6060f1SDimitry Andric           } else {
1611fe6060f1SDimitry Andric             LLVM_DEBUG(dbgs()
1612fe6060f1SDimitry Andric                        << "    ... found preceeding def " << *UseInst << "\n");
1613bdd1243dSDimitry Andric             return std::nullopt;
16145ffd83dbSDimitry Andric           }
16155ffd83dbSDimitry Andric         } else
1616*0fca6ea1SDimitry Andric           pushMemUses(UseDef, WorkList, Visited);
16175ffd83dbSDimitry Andric       }
16185ffd83dbSDimitry Andric     }
16195ffd83dbSDimitry Andric 
16205ffd83dbSDimitry Andric     // For accesses to locations visible after the function returns, make sure
1621349cc55cSDimitry Andric     // that the location is dead (=overwritten) along all paths from
1622349cc55cSDimitry Andric     // MaybeDeadAccess to the exit.
1623349cc55cSDimitry Andric     if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1624e8d8bef9SDimitry Andric       SmallPtrSet<BasicBlock *, 16> KillingBlocks;
1625e8d8bef9SDimitry Andric       for (Instruction *KD : KillingDefs)
1626e8d8bef9SDimitry Andric         KillingBlocks.insert(KD->getParent());
16275ffd83dbSDimitry Andric       assert(!KillingBlocks.empty() &&
16285ffd83dbSDimitry Andric              "Expected at least a single killing block");
1629e8d8bef9SDimitry Andric 
16305ffd83dbSDimitry Andric       // Find the common post-dominator of all killing blocks.
16315ffd83dbSDimitry Andric       BasicBlock *CommonPred = *KillingBlocks.begin();
1632349cc55cSDimitry Andric       for (BasicBlock *BB : llvm::drop_begin(KillingBlocks)) {
16335ffd83dbSDimitry Andric         if (!CommonPred)
16345ffd83dbSDimitry Andric           break;
1635349cc55cSDimitry Andric         CommonPred = PDT.findNearestCommonDominator(CommonPred, BB);
16365ffd83dbSDimitry Andric       }
16375ffd83dbSDimitry Andric 
1638349cc55cSDimitry Andric       // If the common post-dominator does not post-dominate MaybeDeadAccess,
1639349cc55cSDimitry Andric       // there is a path from MaybeDeadAccess to an exit not going through a
1640e8d8bef9SDimitry Andric       // killing block.
1641d781ede6SDimitry Andric       if (!PDT.dominates(CommonPred, MaybeDeadAccess->getBlock())) {
1642d781ede6SDimitry Andric         if (!AnyUnreachableExit)
1643bdd1243dSDimitry Andric           return std::nullopt;
16445ffd83dbSDimitry Andric 
1645d781ede6SDimitry Andric         // Fall back to CFG scan starting at all non-unreachable roots if not
1646d781ede6SDimitry Andric         // all paths to the exit go through CommonPred.
1647d781ede6SDimitry Andric         CommonPred = nullptr;
1648d781ede6SDimitry Andric       }
1649d781ede6SDimitry Andric 
1650d781ede6SDimitry Andric       // If CommonPred itself is in the set of killing blocks, we're done.
1651d781ede6SDimitry Andric       if (KillingBlocks.count(CommonPred))
1652d781ede6SDimitry Andric         return {MaybeDeadAccess};
1653d781ede6SDimitry Andric 
1654d781ede6SDimitry Andric       SetVector<BasicBlock *> WorkList;
16555ffd83dbSDimitry Andric       // If CommonPred is null, there are multiple exits from the function.
16565ffd83dbSDimitry Andric       // They all have to be added to the worklist.
16575ffd83dbSDimitry Andric       if (CommonPred)
16585ffd83dbSDimitry Andric         WorkList.insert(CommonPred);
16595ffd83dbSDimitry Andric       else
1660d781ede6SDimitry Andric         for (BasicBlock *R : PDT.roots()) {
1661d781ede6SDimitry Andric           if (!isa<UnreachableInst>(R->getTerminator()))
16625ffd83dbSDimitry Andric             WorkList.insert(R);
1663d781ede6SDimitry Andric         }
16645ffd83dbSDimitry Andric 
16655ffd83dbSDimitry Andric       NumCFGTries++;
16665ffd83dbSDimitry Andric       // Check if all paths starting from an exit node go through one of the
1667349cc55cSDimitry Andric       // killing blocks before reaching MaybeDeadAccess.
16685ffd83dbSDimitry Andric       for (unsigned I = 0; I < WorkList.size(); I++) {
16695ffd83dbSDimitry Andric         NumCFGChecks++;
16705ffd83dbSDimitry Andric         BasicBlock *Current = WorkList[I];
16715ffd83dbSDimitry Andric         if (KillingBlocks.count(Current))
16725ffd83dbSDimitry Andric           continue;
1673349cc55cSDimitry Andric         if (Current == MaybeDeadAccess->getBlock())
1674bdd1243dSDimitry Andric           return std::nullopt;
16755ffd83dbSDimitry Andric 
1676349cc55cSDimitry Andric         // MaybeDeadAccess is reachable from the entry, so we don't have to
1677e8d8bef9SDimitry Andric         // explore unreachable blocks further.
16785ffd83dbSDimitry Andric         if (!DT.isReachableFromEntry(Current))
16795ffd83dbSDimitry Andric           continue;
16805ffd83dbSDimitry Andric 
16815ffd83dbSDimitry Andric         for (BasicBlock *Pred : predecessors(Current))
16825ffd83dbSDimitry Andric           WorkList.insert(Pred);
16835ffd83dbSDimitry Andric 
16845ffd83dbSDimitry Andric         if (WorkList.size() >= MemorySSAPathCheckLimit)
1685bdd1243dSDimitry Andric           return std::nullopt;
16865ffd83dbSDimitry Andric       }
16875ffd83dbSDimitry Andric       NumCFGSuccess++;
16885ffd83dbSDimitry Andric     }
16895ffd83dbSDimitry Andric 
1690349cc55cSDimitry Andric     // No aliasing MemoryUses of MaybeDeadAccess found, MaybeDeadAccess is
1691e8d8bef9SDimitry Andric     // potentially dead.
1692349cc55cSDimitry Andric     return {MaybeDeadAccess};
16935ffd83dbSDimitry Andric   }
16945ffd83dbSDimitry Andric 
1695439352acSDimitry Andric   /// Delete dead memory defs and recursively add their operands to ToRemove if
1696439352acSDimitry Andric   /// they became dead.
169755a2a91cSDimitry Andric   void
169855a2a91cSDimitry Andric   deleteDeadInstruction(Instruction *SI,
169955a2a91cSDimitry Andric                         SmallPtrSetImpl<MemoryAccess *> *Deleted = nullptr) {
17005ffd83dbSDimitry Andric     MemorySSAUpdater Updater(&MSSA);
17015ffd83dbSDimitry Andric     SmallVector<Instruction *, 32> NowDeadInsts;
17025ffd83dbSDimitry Andric     NowDeadInsts.push_back(SI);
17035ffd83dbSDimitry Andric     --NumFastOther;
17045ffd83dbSDimitry Andric 
17055ffd83dbSDimitry Andric     while (!NowDeadInsts.empty()) {
17065ffd83dbSDimitry Andric       Instruction *DeadInst = NowDeadInsts.pop_back_val();
17075ffd83dbSDimitry Andric       ++NumFastOther;
17085ffd83dbSDimitry Andric 
17095ffd83dbSDimitry Andric       // Try to preserve debug information attached to the dead instruction.
17105ffd83dbSDimitry Andric       salvageDebugInfo(*DeadInst);
17115ffd83dbSDimitry Andric       salvageKnowledge(DeadInst);
17125ffd83dbSDimitry Andric 
17135ffd83dbSDimitry Andric       // Remove the Instruction from MSSA.
1714439352acSDimitry Andric       MemoryAccess *MA = MSSA.getMemoryAccess(DeadInst);
1715439352acSDimitry Andric       bool IsMemDef = MA && isa<MemoryDef>(MA);
1716439352acSDimitry Andric       if (MA) {
1717439352acSDimitry Andric         if (IsMemDef) {
1718439352acSDimitry Andric           auto *MD = cast<MemoryDef>(MA);
17195ffd83dbSDimitry Andric           SkipStores.insert(MD);
172055a2a91cSDimitry Andric           if (Deleted)
172155a2a91cSDimitry Andric             Deleted->insert(MD);
1722fcaf7f86SDimitry Andric           if (auto *SI = dyn_cast<StoreInst>(MD->getMemoryInst())) {
1723fcaf7f86SDimitry Andric             if (SI->getValueOperand()->getType()->isPointerTy()) {
1724fcaf7f86SDimitry Andric               const Value *UO = getUnderlyingObject(SI->getValueOperand());
1725fcaf7f86SDimitry Andric               if (CapturedBeforeReturn.erase(UO))
1726fcaf7f86SDimitry Andric                 ShouldIterateEndOfFunctionDSE = true;
1727fcaf7f86SDimitry Andric               InvisibleToCallerAfterRet.erase(UO);
1728fcaf7f86SDimitry Andric             }
1729fcaf7f86SDimitry Andric           }
17305ffd83dbSDimitry Andric         }
1731349cc55cSDimitry Andric 
17325ffd83dbSDimitry Andric         Updater.removeMemoryAccess(MA);
17335ffd83dbSDimitry Andric       }
17345ffd83dbSDimitry Andric 
17355ffd83dbSDimitry Andric       auto I = IOLs.find(DeadInst->getParent());
17365ffd83dbSDimitry Andric       if (I != IOLs.end())
17375ffd83dbSDimitry Andric         I->second.erase(DeadInst);
17385ffd83dbSDimitry Andric       // Remove its operands
17395ffd83dbSDimitry Andric       for (Use &O : DeadInst->operands())
17405ffd83dbSDimitry Andric         if (Instruction *OpI = dyn_cast<Instruction>(O)) {
1741439352acSDimitry Andric           O.set(PoisonValue::get(O->getType()));
17425ffd83dbSDimitry Andric           if (isInstructionTriviallyDead(OpI, &TLI))
17435ffd83dbSDimitry Andric             NowDeadInsts.push_back(OpI);
17445ffd83dbSDimitry Andric         }
17455ffd83dbSDimitry Andric 
1746349cc55cSDimitry Andric       EI.removeInstruction(DeadInst);
1747439352acSDimitry Andric       // Remove memory defs directly if they don't produce results, but only
1748439352acSDimitry Andric       // queue other dead instructions for later removal. They may have been
1749439352acSDimitry Andric       // used as memory locations that have been cached by BatchAA. Removing
1750439352acSDimitry Andric       // them here may lead to newly created instructions to be allocated at the
1751439352acSDimitry Andric       // same address, yielding stale cache entries.
1752439352acSDimitry Andric       if (IsMemDef && DeadInst->getType()->isVoidTy())
17535ffd83dbSDimitry Andric         DeadInst->eraseFromParent();
1754439352acSDimitry Andric       else
1755439352acSDimitry Andric         ToRemove.push_back(DeadInst);
17565ffd83dbSDimitry Andric     }
17575ffd83dbSDimitry Andric   }
17585ffd83dbSDimitry Andric 
1759349cc55cSDimitry Andric   // Check for any extra throws between \p KillingI and \p DeadI that block
1760349cc55cSDimitry Andric   // DSE.  This only checks extra maythrows (those that aren't MemoryDef's).
1761349cc55cSDimitry Andric   // MemoryDef that may throw are handled during the walk from one def to the
1762349cc55cSDimitry Andric   // next.
1763349cc55cSDimitry Andric   bool mayThrowBetween(Instruction *KillingI, Instruction *DeadI,
1764349cc55cSDimitry Andric                        const Value *KillingUndObj) {
1765349cc55cSDimitry Andric     // First see if we can ignore it by using the fact that KillingI is an
17665ffd83dbSDimitry Andric     // alloca/alloca like object that is not visible to the caller during
17675ffd83dbSDimitry Andric     // execution of the function.
176804eeddc0SDimitry Andric     if (KillingUndObj && isInvisibleToCallerOnUnwind(KillingUndObj))
17695ffd83dbSDimitry Andric       return false;
17705ffd83dbSDimitry Andric 
1771349cc55cSDimitry Andric     if (KillingI->getParent() == DeadI->getParent())
1772349cc55cSDimitry Andric       return ThrowingBlocks.count(KillingI->getParent());
17735ffd83dbSDimitry Andric     return !ThrowingBlocks.empty();
17745ffd83dbSDimitry Andric   }
17755ffd83dbSDimitry Andric 
1776349cc55cSDimitry Andric   // Check if \p DeadI acts as a DSE barrier for \p KillingI. The following
1777349cc55cSDimitry Andric   // instructions act as barriers:
1778349cc55cSDimitry Andric   //  * A memory instruction that may throw and \p KillingI accesses a non-stack
17795ffd83dbSDimitry Andric   //  object.
17805ffd83dbSDimitry Andric   //  * Atomic stores stronger that monotonic.
1781349cc55cSDimitry Andric   bool isDSEBarrier(const Value *KillingUndObj, Instruction *DeadI) {
1782349cc55cSDimitry Andric     // If DeadI may throw it acts as a barrier, unless we are to an
1783349cc55cSDimitry Andric     // alloca/alloca like object that does not escape.
178404eeddc0SDimitry Andric     if (DeadI->mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj))
17855ffd83dbSDimitry Andric       return true;
17865ffd83dbSDimitry Andric 
1787349cc55cSDimitry Andric     // If DeadI is an atomic load/store stronger than monotonic, do not try to
17885ffd83dbSDimitry Andric     // eliminate/reorder it.
1789349cc55cSDimitry Andric     if (DeadI->isAtomic()) {
1790349cc55cSDimitry Andric       if (auto *LI = dyn_cast<LoadInst>(DeadI))
17915ffd83dbSDimitry Andric         return isStrongerThanMonotonic(LI->getOrdering());
1792349cc55cSDimitry Andric       if (auto *SI = dyn_cast<StoreInst>(DeadI))
17935ffd83dbSDimitry Andric         return isStrongerThanMonotonic(SI->getOrdering());
1794349cc55cSDimitry Andric       if (auto *ARMW = dyn_cast<AtomicRMWInst>(DeadI))
1795e8d8bef9SDimitry Andric         return isStrongerThanMonotonic(ARMW->getOrdering());
1796349cc55cSDimitry Andric       if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(DeadI))
1797e8d8bef9SDimitry Andric         return isStrongerThanMonotonic(CmpXchg->getSuccessOrdering()) ||
1798e8d8bef9SDimitry Andric                isStrongerThanMonotonic(CmpXchg->getFailureOrdering());
17995ffd83dbSDimitry Andric       llvm_unreachable("other instructions should be skipped in MemorySSA");
18005ffd83dbSDimitry Andric     }
18015ffd83dbSDimitry Andric     return false;
18025ffd83dbSDimitry Andric   }
18035ffd83dbSDimitry Andric 
18045ffd83dbSDimitry Andric   /// Eliminate writes to objects that are not visible in the caller and are not
18055ffd83dbSDimitry Andric   /// accessed before returning from the function.
18065ffd83dbSDimitry Andric   bool eliminateDeadWritesAtEndOfFunction() {
18075ffd83dbSDimitry Andric     bool MadeChange = false;
18085ffd83dbSDimitry Andric     LLVM_DEBUG(
18095ffd83dbSDimitry Andric         dbgs()
18105ffd83dbSDimitry Andric         << "Trying to eliminate MemoryDefs at the end of the function\n");
1811fcaf7f86SDimitry Andric     do {
1812fcaf7f86SDimitry Andric       ShouldIterateEndOfFunctionDSE = false;
18130eae32dcSDimitry Andric       for (MemoryDef *Def : llvm::reverse(MemDefs)) {
18140eae32dcSDimitry Andric         if (SkipStores.contains(Def))
18155ffd83dbSDimitry Andric           continue;
18165ffd83dbSDimitry Andric 
18175ffd83dbSDimitry Andric         Instruction *DefI = Def->getMemoryInst();
18180eae32dcSDimitry Andric         auto DefLoc = getLocForWrite(DefI);
1819*0fca6ea1SDimitry Andric         if (!DefLoc || !isRemovable(DefI)) {
1820*0fca6ea1SDimitry Andric           LLVM_DEBUG(dbgs() << "  ... could not get location for write or "
1821*0fca6ea1SDimitry Andric                                "instruction not removable.\n");
1822e8d8bef9SDimitry Andric           continue;
1823*0fca6ea1SDimitry Andric         }
18245ffd83dbSDimitry Andric 
1825fcaf7f86SDimitry Andric         // NOTE: Currently eliminating writes at the end of a function is
1826fcaf7f86SDimitry Andric         // limited to MemoryDefs with a single underlying object, to save
1827fcaf7f86SDimitry Andric         // compile-time. In practice it appears the case with multiple
1828fcaf7f86SDimitry Andric         // underlying objects is very uncommon. If it turns out to be important,
1829fcaf7f86SDimitry Andric         // we can use getUnderlyingObjects here instead.
1830e8d8bef9SDimitry Andric         const Value *UO = getUnderlyingObject(DefLoc->Ptr);
1831349cc55cSDimitry Andric         if (!isInvisibleToCallerAfterRet(UO))
1832e8d8bef9SDimitry Andric           continue;
1833e8d8bef9SDimitry Andric 
1834*0fca6ea1SDimitry Andric         if (isWriteAtEndOfFunction(Def, *DefLoc)) {
1835e8d8bef9SDimitry Andric           // See through pointer-to-pointer bitcasts
18365ffd83dbSDimitry Andric           LLVM_DEBUG(dbgs() << "   ... MemoryDef is not accessed until the end "
18375ffd83dbSDimitry Andric                                "of the function\n");
18385ffd83dbSDimitry Andric           deleteDeadInstruction(DefI);
18395ffd83dbSDimitry Andric           ++NumFastStores;
18405ffd83dbSDimitry Andric           MadeChange = true;
18415ffd83dbSDimitry Andric         }
18425ffd83dbSDimitry Andric       }
1843fcaf7f86SDimitry Andric     } while (ShouldIterateEndOfFunctionDSE);
18445ffd83dbSDimitry Andric     return MadeChange;
18455ffd83dbSDimitry Andric   }
18465ffd83dbSDimitry Andric 
184704eeddc0SDimitry Andric   /// If we have a zero initializing memset following a call to malloc,
184804eeddc0SDimitry Andric   /// try folding it into a call to calloc.
184904eeddc0SDimitry Andric   bool tryFoldIntoCalloc(MemoryDef *Def, const Value *DefUO) {
18500eae32dcSDimitry Andric     Instruction *DefI = Def->getMemoryInst();
18510eae32dcSDimitry Andric     MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);
185204eeddc0SDimitry Andric     if (!MemSet)
185304eeddc0SDimitry Andric       // TODO: Could handle zero store to small allocation as well.
185404eeddc0SDimitry Andric       return false;
185504eeddc0SDimitry Andric     Constant *StoredConstant = dyn_cast<Constant>(MemSet->getValue());
185604eeddc0SDimitry Andric     if (!StoredConstant || !StoredConstant->isNullValue())
18570eae32dcSDimitry Andric       return false;
18580eae32dcSDimitry Andric 
18590eae32dcSDimitry Andric     if (!isRemovable(DefI))
186004eeddc0SDimitry Andric       // The memset might be volatile..
18610eae32dcSDimitry Andric       return false;
1862fe6060f1SDimitry Andric 
1863349cc55cSDimitry Andric     if (F.hasFnAttribute(Attribute::SanitizeMemory) ||
1864349cc55cSDimitry Andric         F.hasFnAttribute(Attribute::SanitizeAddress) ||
1865349cc55cSDimitry Andric         F.hasFnAttribute(Attribute::SanitizeHWAddress) ||
1866349cc55cSDimitry Andric         F.getName() == "calloc")
1867349cc55cSDimitry Andric       return false;
186804eeddc0SDimitry Andric     auto *Malloc = const_cast<CallInst *>(dyn_cast<CallInst>(DefUO));
1869349cc55cSDimitry Andric     if (!Malloc)
1870349cc55cSDimitry Andric       return false;
1871349cc55cSDimitry Andric     auto *InnerCallee = Malloc->getCalledFunction();
1872349cc55cSDimitry Andric     if (!InnerCallee)
1873349cc55cSDimitry Andric       return false;
1874349cc55cSDimitry Andric     LibFunc Func;
1875349cc55cSDimitry Andric     if (!TLI.getLibFunc(*InnerCallee, Func) || !TLI.has(Func) ||
1876349cc55cSDimitry Andric         Func != LibFunc_malloc)
1877349cc55cSDimitry Andric       return false;
18785f757f3fSDimitry Andric     // Gracefully handle malloc with unexpected memory attributes.
18795f757f3fSDimitry Andric     auto *MallocDef = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(Malloc));
18805f757f3fSDimitry Andric     if (!MallocDef)
18815f757f3fSDimitry Andric       return false;
1882349cc55cSDimitry Andric 
1883349cc55cSDimitry Andric     auto shouldCreateCalloc = [](CallInst *Malloc, CallInst *Memset) {
1884349cc55cSDimitry Andric       // Check for br(icmp ptr, null), truebb, falsebb) pattern at the end
1885349cc55cSDimitry Andric       // of malloc block
1886349cc55cSDimitry Andric       auto *MallocBB = Malloc->getParent(),
1887349cc55cSDimitry Andric         *MemsetBB = Memset->getParent();
1888349cc55cSDimitry Andric       if (MallocBB == MemsetBB)
1889349cc55cSDimitry Andric         return true;
1890349cc55cSDimitry Andric       auto *Ptr = Memset->getArgOperand(0);
1891349cc55cSDimitry Andric       auto *TI = MallocBB->getTerminator();
1892349cc55cSDimitry Andric       ICmpInst::Predicate Pred;
1893349cc55cSDimitry Andric       BasicBlock *TrueBB, *FalseBB;
1894349cc55cSDimitry Andric       if (!match(TI, m_Br(m_ICmp(Pred, m_Specific(Ptr), m_Zero()), TrueBB,
1895349cc55cSDimitry Andric                           FalseBB)))
1896349cc55cSDimitry Andric         return false;
1897349cc55cSDimitry Andric       if (Pred != ICmpInst::ICMP_EQ || MemsetBB != FalseBB)
1898349cc55cSDimitry Andric         return false;
1899349cc55cSDimitry Andric       return true;
1900349cc55cSDimitry Andric     };
1901349cc55cSDimitry Andric 
190204eeddc0SDimitry Andric     if (Malloc->getOperand(0) != MemSet->getLength())
190304eeddc0SDimitry Andric       return false;
190404eeddc0SDimitry Andric     if (!shouldCreateCalloc(Malloc, MemSet) ||
190504eeddc0SDimitry Andric         !DT.dominates(Malloc, MemSet) ||
190604eeddc0SDimitry Andric         !memoryIsNotModifiedBetween(Malloc, MemSet, BatchAA, DL, &DT))
190704eeddc0SDimitry Andric       return false;
1908349cc55cSDimitry Andric     IRBuilder<> IRB(Malloc);
1909bdd1243dSDimitry Andric     Type *SizeTTy = Malloc->getArgOperand(0)->getType();
1910bdd1243dSDimitry Andric     auto *Calloc = emitCalloc(ConstantInt::get(SizeTTy, 1),
191104eeddc0SDimitry Andric                               Malloc->getArgOperand(0), IRB, TLI);
191204eeddc0SDimitry Andric     if (!Calloc)
191304eeddc0SDimitry Andric       return false;
1914aaabed1dSDimitry Andric 
1915349cc55cSDimitry Andric     MemorySSAUpdater Updater(&MSSA);
191604eeddc0SDimitry Andric     auto *NewAccess =
19175f757f3fSDimitry Andric       Updater.createMemoryAccessAfter(cast<Instruction>(Calloc), nullptr,
19185f757f3fSDimitry Andric                                       MallocDef);
1919349cc55cSDimitry Andric     auto *NewAccessMD = cast<MemoryDef>(NewAccess);
1920349cc55cSDimitry Andric     Updater.insertDef(NewAccessMD, /*RenameUses=*/true);
1921349cc55cSDimitry Andric     Malloc->replaceAllUsesWith(Calloc);
1922aaabed1dSDimitry Andric     deleteDeadInstruction(Malloc);
1923349cc55cSDimitry Andric     return true;
1924349cc55cSDimitry Andric   }
192504eeddc0SDimitry Andric 
1926*0fca6ea1SDimitry Andric   // Check if there is a dominating condition, that implies that the value
1927*0fca6ea1SDimitry Andric   // being stored in a ptr is already present in the ptr.
1928*0fca6ea1SDimitry Andric   bool dominatingConditionImpliesValue(MemoryDef *Def) {
1929*0fca6ea1SDimitry Andric     auto *StoreI = cast<StoreInst>(Def->getMemoryInst());
1930*0fca6ea1SDimitry Andric     BasicBlock *StoreBB = StoreI->getParent();
1931*0fca6ea1SDimitry Andric     Value *StorePtr = StoreI->getPointerOperand();
1932*0fca6ea1SDimitry Andric     Value *StoreVal = StoreI->getValueOperand();
1933*0fca6ea1SDimitry Andric 
1934*0fca6ea1SDimitry Andric     DomTreeNode *IDom = DT.getNode(StoreBB)->getIDom();
1935*0fca6ea1SDimitry Andric     if (!IDom)
1936*0fca6ea1SDimitry Andric       return false;
1937*0fca6ea1SDimitry Andric 
1938*0fca6ea1SDimitry Andric     auto *BI = dyn_cast<BranchInst>(IDom->getBlock()->getTerminator());
1939*0fca6ea1SDimitry Andric     if (!BI || !BI->isConditional())
1940*0fca6ea1SDimitry Andric       return false;
1941*0fca6ea1SDimitry Andric 
1942*0fca6ea1SDimitry Andric     // In case both blocks are the same, it is not possible to determine
1943*0fca6ea1SDimitry Andric     // if optimization is possible. (We would not want to optimize a store
1944*0fca6ea1SDimitry Andric     // in the FalseBB if condition is true and vice versa.)
1945*0fca6ea1SDimitry Andric     if (BI->getSuccessor(0) == BI->getSuccessor(1))
1946*0fca6ea1SDimitry Andric       return false;
1947*0fca6ea1SDimitry Andric 
1948*0fca6ea1SDimitry Andric     Instruction *ICmpL;
1949*0fca6ea1SDimitry Andric     ICmpInst::Predicate Pred;
1950*0fca6ea1SDimitry Andric     if (!match(BI->getCondition(),
1951*0fca6ea1SDimitry Andric                m_c_ICmp(Pred,
1952*0fca6ea1SDimitry Andric                         m_CombineAnd(m_Load(m_Specific(StorePtr)),
1953*0fca6ea1SDimitry Andric                                      m_Instruction(ICmpL)),
1954*0fca6ea1SDimitry Andric                         m_Specific(StoreVal))) ||
1955*0fca6ea1SDimitry Andric         !ICmpInst::isEquality(Pred))
1956*0fca6ea1SDimitry Andric       return false;
1957*0fca6ea1SDimitry Andric 
1958*0fca6ea1SDimitry Andric     // In case the else blocks also branches to the if block or the other way
1959*0fca6ea1SDimitry Andric     // around it is not possible to determine if the optimization is possible.
1960*0fca6ea1SDimitry Andric     if (Pred == ICmpInst::ICMP_EQ &&
1961*0fca6ea1SDimitry Andric         !DT.dominates(BasicBlockEdge(BI->getParent(), BI->getSuccessor(0)),
1962*0fca6ea1SDimitry Andric                       StoreBB))
1963*0fca6ea1SDimitry Andric       return false;
1964*0fca6ea1SDimitry Andric 
1965*0fca6ea1SDimitry Andric     if (Pred == ICmpInst::ICMP_NE &&
1966*0fca6ea1SDimitry Andric         !DT.dominates(BasicBlockEdge(BI->getParent(), BI->getSuccessor(1)),
1967*0fca6ea1SDimitry Andric                       StoreBB))
1968*0fca6ea1SDimitry Andric       return false;
1969*0fca6ea1SDimitry Andric 
1970*0fca6ea1SDimitry Andric     MemoryAccess *LoadAcc = MSSA.getMemoryAccess(ICmpL);
1971*0fca6ea1SDimitry Andric     MemoryAccess *ClobAcc =
1972*0fca6ea1SDimitry Andric         MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def, BatchAA);
1973*0fca6ea1SDimitry Andric 
1974*0fca6ea1SDimitry Andric     return MSSA.dominates(ClobAcc, LoadAcc);
1975*0fca6ea1SDimitry Andric   }
1976*0fca6ea1SDimitry Andric 
197704eeddc0SDimitry Andric   /// \returns true if \p Def is a no-op store, either because it
197804eeddc0SDimitry Andric   /// directly stores back a loaded value or stores zero to a calloced object.
197904eeddc0SDimitry Andric   bool storeIsNoop(MemoryDef *Def, const Value *DefUO) {
198004eeddc0SDimitry Andric     Instruction *DefI = Def->getMemoryInst();
198104eeddc0SDimitry Andric     StoreInst *Store = dyn_cast<StoreInst>(DefI);
198204eeddc0SDimitry Andric     MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);
198304eeddc0SDimitry Andric     Constant *StoredConstant = nullptr;
198404eeddc0SDimitry Andric     if (Store)
198504eeddc0SDimitry Andric       StoredConstant = dyn_cast<Constant>(Store->getOperand(0));
198604eeddc0SDimitry Andric     else if (MemSet)
198704eeddc0SDimitry Andric       StoredConstant = dyn_cast<Constant>(MemSet->getValue());
198804eeddc0SDimitry Andric     else
1989349cc55cSDimitry Andric       return false;
199004eeddc0SDimitry Andric 
199104eeddc0SDimitry Andric     if (!isRemovable(DefI))
199204eeddc0SDimitry Andric       return false;
199304eeddc0SDimitry Andric 
199481ad6265SDimitry Andric     if (StoredConstant) {
199581ad6265SDimitry Andric       Constant *InitC =
199681ad6265SDimitry Andric           getInitialValueOfAllocation(DefUO, &TLI, StoredConstant->getType());
199704eeddc0SDimitry Andric       // If the clobbering access is LiveOnEntry, no instructions between them
199804eeddc0SDimitry Andric       // can modify the memory location.
199904eeddc0SDimitry Andric       if (InitC && InitC == StoredConstant)
200004eeddc0SDimitry Andric         return MSSA.isLiveOnEntryDef(
2001bdd1243dSDimitry Andric             MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def, BatchAA));
2002fe6060f1SDimitry Andric     }
2003fe6060f1SDimitry Andric 
20045ffd83dbSDimitry Andric     if (!Store)
20055ffd83dbSDimitry Andric       return false;
20065ffd83dbSDimitry Andric 
2007*0fca6ea1SDimitry Andric     if (dominatingConditionImpliesValue(Def))
2008*0fca6ea1SDimitry Andric       return true;
2009*0fca6ea1SDimitry Andric 
20105ffd83dbSDimitry Andric     if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
20115ffd83dbSDimitry Andric       if (LoadI->getPointerOperand() == Store->getOperand(1)) {
2012e8d8bef9SDimitry Andric         // Get the defining access for the load.
20135ffd83dbSDimitry Andric         auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess();
2014e8d8bef9SDimitry Andric         // Fast path: the defining accesses are the same.
2015e8d8bef9SDimitry Andric         if (LoadAccess == Def->getDefiningAccess())
2016e8d8bef9SDimitry Andric           return true;
2017e8d8bef9SDimitry Andric 
2018e8d8bef9SDimitry Andric         // Look through phi accesses. Recursively scan all phi accesses by
2019e8d8bef9SDimitry Andric         // adding them to a worklist. Bail when we run into a memory def that
2020e8d8bef9SDimitry Andric         // does not match LoadAccess.
2021e8d8bef9SDimitry Andric         SetVector<MemoryAccess *> ToCheck;
2022e8d8bef9SDimitry Andric         MemoryAccess *Current =
2023bdd1243dSDimitry Andric             MSSA.getWalker()->getClobberingMemoryAccess(Def, BatchAA);
2024e8d8bef9SDimitry Andric         // We don't want to bail when we run into the store memory def. But,
2025e8d8bef9SDimitry Andric         // the phi access may point to it. So, pretend like we've already
2026e8d8bef9SDimitry Andric         // checked it.
2027e8d8bef9SDimitry Andric         ToCheck.insert(Def);
2028e8d8bef9SDimitry Andric         ToCheck.insert(Current);
2029e8d8bef9SDimitry Andric         // Start at current (1) to simulate already having checked Def.
2030e8d8bef9SDimitry Andric         for (unsigned I = 1; I < ToCheck.size(); ++I) {
2031e8d8bef9SDimitry Andric           Current = ToCheck[I];
2032e8d8bef9SDimitry Andric           if (auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
2033e8d8bef9SDimitry Andric             // Check all the operands.
2034e8d8bef9SDimitry Andric             for (auto &Use : PhiAccess->incoming_values())
2035e8d8bef9SDimitry Andric               ToCheck.insert(cast<MemoryAccess>(&Use));
2036e8d8bef9SDimitry Andric             continue;
2037e8d8bef9SDimitry Andric           }
2038e8d8bef9SDimitry Andric 
2039e8d8bef9SDimitry Andric           // If we found a memory def, bail. This happens when we have an
2040e8d8bef9SDimitry Andric           // unrelated write in between an otherwise noop store.
2041e8d8bef9SDimitry Andric           assert(isa<MemoryDef>(Current) &&
2042e8d8bef9SDimitry Andric                  "Only MemoryDefs should reach here.");
2043e8d8bef9SDimitry Andric           // TODO: Skip no alias MemoryDefs that have no aliasing reads.
2044e8d8bef9SDimitry Andric           // We are searching for the definition of the store's destination.
2045e8d8bef9SDimitry Andric           // So, if that is the same definition as the load, then this is a
2046e8d8bef9SDimitry Andric           // noop. Otherwise, fail.
2047e8d8bef9SDimitry Andric           if (LoadAccess != Current)
2048e8d8bef9SDimitry Andric             return false;
2049e8d8bef9SDimitry Andric         }
2050e8d8bef9SDimitry Andric         return true;
20515ffd83dbSDimitry Andric       }
20525ffd83dbSDimitry Andric     }
20535ffd83dbSDimitry Andric 
20545ffd83dbSDimitry Andric     return false;
20555ffd83dbSDimitry Andric   }
2056349cc55cSDimitry Andric 
2057349cc55cSDimitry Andric   bool removePartiallyOverlappedStores(InstOverlapIntervalsTy &IOL) {
2058349cc55cSDimitry Andric     bool Changed = false;
2059349cc55cSDimitry Andric     for (auto OI : IOL) {
2060349cc55cSDimitry Andric       Instruction *DeadI = OI.first;
20610eae32dcSDimitry Andric       MemoryLocation Loc = *getLocForWrite(DeadI);
2062349cc55cSDimitry Andric       assert(isRemovable(DeadI) && "Expect only removable instruction");
2063349cc55cSDimitry Andric 
2064349cc55cSDimitry Andric       const Value *Ptr = Loc.Ptr->stripPointerCasts();
2065349cc55cSDimitry Andric       int64_t DeadStart = 0;
2066349cc55cSDimitry Andric       uint64_t DeadSize = Loc.Size.getValue();
2067349cc55cSDimitry Andric       GetPointerBaseWithConstantOffset(Ptr, DeadStart, DL);
2068349cc55cSDimitry Andric       OverlapIntervalsTy &IntervalMap = OI.second;
2069349cc55cSDimitry Andric       Changed |= tryToShortenEnd(DeadI, IntervalMap, DeadStart, DeadSize);
2070349cc55cSDimitry Andric       if (IntervalMap.empty())
2071349cc55cSDimitry Andric         continue;
2072349cc55cSDimitry Andric       Changed |= tryToShortenBegin(DeadI, IntervalMap, DeadStart, DeadSize);
2073349cc55cSDimitry Andric     }
2074349cc55cSDimitry Andric     return Changed;
2075349cc55cSDimitry Andric   }
2076349cc55cSDimitry Andric 
2077349cc55cSDimitry Andric   /// Eliminates writes to locations where the value that is being written
2078349cc55cSDimitry Andric   /// is already stored at the same location.
2079349cc55cSDimitry Andric   bool eliminateRedundantStoresOfExistingValues() {
2080349cc55cSDimitry Andric     bool MadeChange = false;
2081349cc55cSDimitry Andric     LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs that write the "
2082349cc55cSDimitry Andric                          "already existing value\n");
2083349cc55cSDimitry Andric     for (auto *Def : MemDefs) {
20840eae32dcSDimitry Andric       if (SkipStores.contains(Def) || MSSA.isLiveOnEntryDef(Def))
2085349cc55cSDimitry Andric         continue;
20860eae32dcSDimitry Andric 
20870eae32dcSDimitry Andric       Instruction *DefInst = Def->getMemoryInst();
20880eae32dcSDimitry Andric       auto MaybeDefLoc = getLocForWrite(DefInst);
20890eae32dcSDimitry Andric       if (!MaybeDefLoc || !isRemovable(DefInst))
20900eae32dcSDimitry Andric         continue;
20910eae32dcSDimitry Andric 
20924824e7fdSDimitry Andric       MemoryDef *UpperDef;
20934824e7fdSDimitry Andric       // To conserve compile-time, we avoid walking to the next clobbering def.
20944824e7fdSDimitry Andric       // Instead, we just try to get the optimized access, if it exists. DSE
20954824e7fdSDimitry Andric       // will try to optimize defs during the earlier traversal.
20964824e7fdSDimitry Andric       if (Def->isOptimized())
20974824e7fdSDimitry Andric         UpperDef = dyn_cast<MemoryDef>(Def->getOptimized());
20984824e7fdSDimitry Andric       else
20994824e7fdSDimitry Andric         UpperDef = dyn_cast<MemoryDef>(Def->getDefiningAccess());
2100349cc55cSDimitry Andric       if (!UpperDef || MSSA.isLiveOnEntryDef(UpperDef))
2101349cc55cSDimitry Andric         continue;
2102349cc55cSDimitry Andric 
2103349cc55cSDimitry Andric       Instruction *UpperInst = UpperDef->getMemoryInst();
21040eae32dcSDimitry Andric       auto IsRedundantStore = [&]() {
2105349cc55cSDimitry Andric         if (DefInst->isIdenticalTo(UpperInst))
2106349cc55cSDimitry Andric           return true;
2107349cc55cSDimitry Andric         if (auto *MemSetI = dyn_cast<MemSetInst>(UpperInst)) {
2108349cc55cSDimitry Andric           if (auto *SI = dyn_cast<StoreInst>(DefInst)) {
21090eae32dcSDimitry Andric             // MemSetInst must have a write location.
2110*0fca6ea1SDimitry Andric             auto UpperLoc = getLocForWrite(UpperInst);
2111*0fca6ea1SDimitry Andric             if (!UpperLoc)
2112*0fca6ea1SDimitry Andric               return false;
2113349cc55cSDimitry Andric             int64_t InstWriteOffset = 0;
2114349cc55cSDimitry Andric             int64_t DepWriteOffset = 0;
2115*0fca6ea1SDimitry Andric             auto OR = isOverwrite(UpperInst, DefInst, *UpperLoc, *MaybeDefLoc,
2116349cc55cSDimitry Andric                                   InstWriteOffset, DepWriteOffset);
2117349cc55cSDimitry Andric             Value *StoredByte = isBytewiseValue(SI->getValueOperand(), DL);
2118349cc55cSDimitry Andric             return StoredByte && StoredByte == MemSetI->getOperand(1) &&
2119349cc55cSDimitry Andric                    OR == OW_Complete;
2120349cc55cSDimitry Andric           }
2121349cc55cSDimitry Andric         }
2122349cc55cSDimitry Andric         return false;
2123349cc55cSDimitry Andric       };
2124349cc55cSDimitry Andric 
21250eae32dcSDimitry Andric       if (!IsRedundantStore() || isReadClobber(*MaybeDefLoc, DefInst))
2126349cc55cSDimitry Andric         continue;
2127349cc55cSDimitry Andric       LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n  DEAD: " << *DefInst
2128349cc55cSDimitry Andric                         << '\n');
2129349cc55cSDimitry Andric       deleteDeadInstruction(DefInst);
2130349cc55cSDimitry Andric       NumRedundantStores++;
2131349cc55cSDimitry Andric       MadeChange = true;
2132349cc55cSDimitry Andric     }
2133349cc55cSDimitry Andric     return MadeChange;
2134349cc55cSDimitry Andric   }
21355ffd83dbSDimitry Andric };
21365ffd83dbSDimitry Andric 
2137fe6060f1SDimitry Andric static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
2138fe6060f1SDimitry Andric                                 DominatorTree &DT, PostDominatorTree &PDT,
2139fe6060f1SDimitry Andric                                 const TargetLibraryInfo &TLI,
2140fe6060f1SDimitry Andric                                 const LoopInfo &LI) {
21415ffd83dbSDimitry Andric   bool MadeChange = false;
21425ffd83dbSDimitry Andric 
21435f757f3fSDimitry Andric   DSEState State(F, AA, MSSA, DT, PDT, TLI, LI);
21445ffd83dbSDimitry Andric   // For each store:
21455ffd83dbSDimitry Andric   for (unsigned I = 0; I < State.MemDefs.size(); I++) {
21465ffd83dbSDimitry Andric     MemoryDef *KillingDef = State.MemDefs[I];
21475ffd83dbSDimitry Andric     if (State.SkipStores.count(KillingDef))
21485ffd83dbSDimitry Andric       continue;
2149349cc55cSDimitry Andric     Instruction *KillingI = KillingDef->getMemoryInst();
21505ffd83dbSDimitry Andric 
2151bdd1243dSDimitry Andric     std::optional<MemoryLocation> MaybeKillingLoc;
2152bdd1243dSDimitry Andric     if (State.isMemTerminatorInst(KillingI)) {
2153bdd1243dSDimitry Andric       if (auto KillingLoc = State.getLocForTerminator(KillingI))
2154bdd1243dSDimitry Andric         MaybeKillingLoc = KillingLoc->first;
2155bdd1243dSDimitry Andric     } else {
21560eae32dcSDimitry Andric       MaybeKillingLoc = State.getLocForWrite(KillingI);
2157bdd1243dSDimitry Andric     }
21585ffd83dbSDimitry Andric 
2159349cc55cSDimitry Andric     if (!MaybeKillingLoc) {
21605ffd83dbSDimitry Andric       LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for "
2161349cc55cSDimitry Andric                         << *KillingI << "\n");
21625ffd83dbSDimitry Andric       continue;
21635ffd83dbSDimitry Andric     }
2164349cc55cSDimitry Andric     MemoryLocation KillingLoc = *MaybeKillingLoc;
2165349cc55cSDimitry Andric     assert(KillingLoc.Ptr && "KillingLoc should not be null");
2166349cc55cSDimitry Andric     const Value *KillingUndObj = getUnderlyingObject(KillingLoc.Ptr);
21675ffd83dbSDimitry Andric     LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "
2168349cc55cSDimitry Andric                       << *KillingDef << " (" << *KillingI << ")\n");
21695ffd83dbSDimitry Andric 
2170e8d8bef9SDimitry Andric     unsigned ScanLimit = MemorySSAScanLimit;
2171e8d8bef9SDimitry Andric     unsigned WalkerStepLimit = MemorySSAUpwardsStepLimit;
2172e8d8bef9SDimitry Andric     unsigned PartialLimit = MemorySSAPartialStoreLimit;
21735ffd83dbSDimitry Andric     // Worklist of MemoryAccesses that may be killed by KillingDef.
217455a2a91cSDimitry Andric     SmallSetVector<MemoryAccess *, 8> ToCheck;
217555a2a91cSDimitry Andric     // Track MemoryAccesses that have been deleted in the loop below, so we can
217655a2a91cSDimitry Andric     // skip them. Don't use SkipStores for this, which may contain reused
217755a2a91cSDimitry Andric     // MemoryAccess addresses.
217855a2a91cSDimitry Andric     SmallPtrSet<MemoryAccess *, 8> Deleted;
217955a2a91cSDimitry Andric     [[maybe_unused]] unsigned OrigNumSkipStores = State.SkipStores.size();
21805ffd83dbSDimitry Andric     ToCheck.insert(KillingDef->getDefiningAccess());
21815ffd83dbSDimitry Andric 
2182e8d8bef9SDimitry Andric     bool Shortend = false;
2183349cc55cSDimitry Andric     bool IsMemTerm = State.isMemTerminatorInst(KillingI);
21845ffd83dbSDimitry Andric     // Check if MemoryAccesses in the worklist are killed by KillingDef.
21855ffd83dbSDimitry Andric     for (unsigned I = 0; I < ToCheck.size(); I++) {
2186349cc55cSDimitry Andric       MemoryAccess *Current = ToCheck[I];
218755a2a91cSDimitry Andric       if (Deleted.contains(Current))
21885ffd83dbSDimitry Andric         continue;
21895ffd83dbSDimitry Andric 
2190bdd1243dSDimitry Andric       std::optional<MemoryAccess *> MaybeDeadAccess = State.getDomMemoryDef(
2191349cc55cSDimitry Andric           KillingDef, Current, KillingLoc, KillingUndObj, ScanLimit,
2192349cc55cSDimitry Andric           WalkerStepLimit, IsMemTerm, PartialLimit);
21935ffd83dbSDimitry Andric 
2194349cc55cSDimitry Andric       if (!MaybeDeadAccess) {
21955ffd83dbSDimitry Andric         LLVM_DEBUG(dbgs() << "  finished walk\n");
21965ffd83dbSDimitry Andric         continue;
21975ffd83dbSDimitry Andric       }
21985ffd83dbSDimitry Andric 
2199349cc55cSDimitry Andric       MemoryAccess *DeadAccess = *MaybeDeadAccess;
2200349cc55cSDimitry Andric       LLVM_DEBUG(dbgs() << " Checking if we can kill " << *DeadAccess);
2201349cc55cSDimitry Andric       if (isa<MemoryPhi>(DeadAccess)) {
22025ffd83dbSDimitry Andric         LLVM_DEBUG(dbgs() << "\n  ... adding incoming values to worklist\n");
2203349cc55cSDimitry Andric         for (Value *V : cast<MemoryPhi>(DeadAccess)->incoming_values()) {
22045ffd83dbSDimitry Andric           MemoryAccess *IncomingAccess = cast<MemoryAccess>(V);
22055ffd83dbSDimitry Andric           BasicBlock *IncomingBlock = IncomingAccess->getBlock();
2206349cc55cSDimitry Andric           BasicBlock *PhiBlock = DeadAccess->getBlock();
22075ffd83dbSDimitry Andric 
22085ffd83dbSDimitry Andric           // We only consider incoming MemoryAccesses that come before the
22095ffd83dbSDimitry Andric           // MemoryPhi. Otherwise we could discover candidates that do not
22105ffd83dbSDimitry Andric           // strictly dominate our starting def.
22115ffd83dbSDimitry Andric           if (State.PostOrderNumbers[IncomingBlock] >
22125ffd83dbSDimitry Andric               State.PostOrderNumbers[PhiBlock])
22135ffd83dbSDimitry Andric             ToCheck.insert(IncomingAccess);
22145ffd83dbSDimitry Andric         }
22155ffd83dbSDimitry Andric         continue;
22165ffd83dbSDimitry Andric       }
2217349cc55cSDimitry Andric       auto *DeadDefAccess = cast<MemoryDef>(DeadAccess);
2218349cc55cSDimitry Andric       Instruction *DeadI = DeadDefAccess->getMemoryInst();
2219349cc55cSDimitry Andric       LLVM_DEBUG(dbgs() << " (" << *DeadI << ")\n");
2220349cc55cSDimitry Andric       ToCheck.insert(DeadDefAccess->getDefiningAccess());
2221e8d8bef9SDimitry Andric       NumGetDomMemoryDefPassed++;
22225ffd83dbSDimitry Andric 
22235ffd83dbSDimitry Andric       if (!DebugCounter::shouldExecute(MemorySSACounter))
22245ffd83dbSDimitry Andric         continue;
22255ffd83dbSDimitry Andric 
22260eae32dcSDimitry Andric       MemoryLocation DeadLoc = *State.getLocForWrite(DeadI);
22275ffd83dbSDimitry Andric 
2228e8d8bef9SDimitry Andric       if (IsMemTerm) {
2229349cc55cSDimitry Andric         const Value *DeadUndObj = getUnderlyingObject(DeadLoc.Ptr);
2230349cc55cSDimitry Andric         if (KillingUndObj != DeadUndObj)
22315ffd83dbSDimitry Andric           continue;
2232349cc55cSDimitry Andric         LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *DeadI
2233349cc55cSDimitry Andric                           << "\n  KILLER: " << *KillingI << '\n');
223455a2a91cSDimitry Andric         State.deleteDeadInstruction(DeadI, &Deleted);
22355ffd83dbSDimitry Andric         ++NumFastStores;
22365ffd83dbSDimitry Andric         MadeChange = true;
22375ffd83dbSDimitry Andric       } else {
2238349cc55cSDimitry Andric         // Check if DeadI overwrites KillingI.
2239349cc55cSDimitry Andric         int64_t KillingOffset = 0;
2240349cc55cSDimitry Andric         int64_t DeadOffset = 0;
2241349cc55cSDimitry Andric         OverwriteResult OR = State.isOverwrite(
2242349cc55cSDimitry Andric             KillingI, DeadI, KillingLoc, DeadLoc, KillingOffset, DeadOffset);
2243e8d8bef9SDimitry Andric         if (OR == OW_MaybePartial) {
22445ffd83dbSDimitry Andric           auto Iter = State.IOLs.insert(
22455ffd83dbSDimitry Andric               std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
2246349cc55cSDimitry Andric                   DeadI->getParent(), InstOverlapIntervalsTy()));
22475ffd83dbSDimitry Andric           auto &IOL = Iter.first->second;
2248349cc55cSDimitry Andric           OR = isPartialOverwrite(KillingLoc, DeadLoc, KillingOffset,
2249349cc55cSDimitry Andric                                   DeadOffset, DeadI, IOL);
2250e8d8bef9SDimitry Andric         }
22515ffd83dbSDimitry Andric 
22525ffd83dbSDimitry Andric         if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {
2253349cc55cSDimitry Andric           auto *DeadSI = dyn_cast<StoreInst>(DeadI);
2254349cc55cSDimitry Andric           auto *KillingSI = dyn_cast<StoreInst>(KillingI);
2255e8d8bef9SDimitry Andric           // We are re-using tryToMergePartialOverlappingStores, which requires
22565f757f3fSDimitry Andric           // DeadSI to dominate KillingSI.
2257e8d8bef9SDimitry Andric           // TODO: implement tryToMergeParialOverlappingStores using MemorySSA.
2258349cc55cSDimitry Andric           if (DeadSI && KillingSI && DT.dominates(DeadSI, KillingSI)) {
22595ffd83dbSDimitry Andric             if (Constant *Merged = tryToMergePartialOverlappingStores(
2260349cc55cSDimitry Andric                     KillingSI, DeadSI, KillingOffset, DeadOffset, State.DL,
2261e8d8bef9SDimitry Andric                     State.BatchAA, &DT)) {
22625ffd83dbSDimitry Andric 
22635ffd83dbSDimitry Andric               // Update stored value of earlier store to merged constant.
2264349cc55cSDimitry Andric               DeadSI->setOperand(0, Merged);
22655ffd83dbSDimitry Andric               ++NumModifiedStores;
22665ffd83dbSDimitry Andric               MadeChange = true;
22675ffd83dbSDimitry Andric 
2268e8d8bef9SDimitry Andric               Shortend = true;
2269349cc55cSDimitry Andric               // Remove killing store and remove any outstanding overlap
2270349cc55cSDimitry Andric               // intervals for the updated store.
227155a2a91cSDimitry Andric               State.deleteDeadInstruction(KillingSI, &Deleted);
2272349cc55cSDimitry Andric               auto I = State.IOLs.find(DeadSI->getParent());
22735ffd83dbSDimitry Andric               if (I != State.IOLs.end())
2274349cc55cSDimitry Andric                 I->second.erase(DeadSI);
22755ffd83dbSDimitry Andric               break;
22765ffd83dbSDimitry Andric             }
22775ffd83dbSDimitry Andric           }
2278e8d8bef9SDimitry Andric         }
22795ffd83dbSDimitry Andric 
22805ffd83dbSDimitry Andric         if (OR == OW_Complete) {
2281349cc55cSDimitry Andric           LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *DeadI
2282349cc55cSDimitry Andric                             << "\n  KILLER: " << *KillingI << '\n');
228355a2a91cSDimitry Andric           State.deleteDeadInstruction(DeadI, &Deleted);
22845ffd83dbSDimitry Andric           ++NumFastStores;
22855ffd83dbSDimitry Andric           MadeChange = true;
22865ffd83dbSDimitry Andric         }
22875ffd83dbSDimitry Andric       }
22885ffd83dbSDimitry Andric     }
2289e8d8bef9SDimitry Andric 
229055a2a91cSDimitry Andric     assert(State.SkipStores.size() - OrigNumSkipStores == Deleted.size() &&
229155a2a91cSDimitry Andric            "SkipStores and Deleted out of sync?");
229255a2a91cSDimitry Andric 
2293e8d8bef9SDimitry Andric     // Check if the store is a no-op.
22940eae32dcSDimitry Andric     if (!Shortend && State.storeIsNoop(KillingDef, KillingUndObj)) {
2295349cc55cSDimitry Andric       LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n  DEAD: " << *KillingI
2296349cc55cSDimitry Andric                         << '\n');
2297349cc55cSDimitry Andric       State.deleteDeadInstruction(KillingI);
2298e8d8bef9SDimitry Andric       NumRedundantStores++;
2299e8d8bef9SDimitry Andric       MadeChange = true;
2300e8d8bef9SDimitry Andric       continue;
2301e8d8bef9SDimitry Andric     }
230204eeddc0SDimitry Andric 
230304eeddc0SDimitry Andric     // Can we form a calloc from a memset/malloc pair?
230404eeddc0SDimitry Andric     if (!Shortend && State.tryFoldIntoCalloc(KillingDef, KillingUndObj)) {
230504eeddc0SDimitry Andric       LLVM_DEBUG(dbgs() << "DSE: Remove memset after forming calloc:\n"
230604eeddc0SDimitry Andric                         << "  DEAD: " << *KillingI << '\n');
230704eeddc0SDimitry Andric       State.deleteDeadInstruction(KillingI);
230804eeddc0SDimitry Andric       MadeChange = true;
230904eeddc0SDimitry Andric       continue;
231004eeddc0SDimitry Andric     }
23115ffd83dbSDimitry Andric   }
23125ffd83dbSDimitry Andric 
23135ffd83dbSDimitry Andric   if (EnablePartialOverwriteTracking)
23145ffd83dbSDimitry Andric     for (auto &KV : State.IOLs)
2315349cc55cSDimitry Andric       MadeChange |= State.removePartiallyOverlappedStores(KV.second);
23165ffd83dbSDimitry Andric 
2317349cc55cSDimitry Andric   MadeChange |= State.eliminateRedundantStoresOfExistingValues();
23185ffd83dbSDimitry Andric   MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
2319439352acSDimitry Andric 
2320439352acSDimitry Andric   while (!State.ToRemove.empty()) {
2321439352acSDimitry Andric     Instruction *DeadInst = State.ToRemove.pop_back_val();
2322439352acSDimitry Andric     DeadInst->eraseFromParent();
2323439352acSDimitry Andric   }
2324439352acSDimitry Andric 
23255ffd83dbSDimitry Andric   return MadeChange;
23265ffd83dbSDimitry Andric }
23275ffd83dbSDimitry Andric } // end anonymous namespace
23285ffd83dbSDimitry Andric 
23290b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
23300b57cec5SDimitry Andric // DSE Pass
23310b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
23320b57cec5SDimitry Andric PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
23335ffd83dbSDimitry Andric   AliasAnalysis &AA = AM.getResult<AAManager>(F);
23345ffd83dbSDimitry Andric   const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);
23355ffd83dbSDimitry Andric   DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
23365ffd83dbSDimitry Andric   MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
23375ffd83dbSDimitry Andric   PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
2338fe6060f1SDimitry Andric   LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
23395ffd83dbSDimitry Andric 
23405f757f3fSDimitry Andric   bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI);
23415ffd83dbSDimitry Andric 
23425ffd83dbSDimitry Andric #ifdef LLVM_ENABLE_STATS
23435ffd83dbSDimitry Andric   if (AreStatisticsEnabled())
23445ffd83dbSDimitry Andric     for (auto &I : instructions(F))
23455ffd83dbSDimitry Andric       NumRemainingStores += isa<StoreInst>(&I);
23465ffd83dbSDimitry Andric #endif
23475ffd83dbSDimitry Andric 
23485ffd83dbSDimitry Andric   if (!Changed)
23490b57cec5SDimitry Andric     return PreservedAnalyses::all();
23500b57cec5SDimitry Andric 
23510b57cec5SDimitry Andric   PreservedAnalyses PA;
23520b57cec5SDimitry Andric   PA.preserveSet<CFGAnalyses>();
23535ffd83dbSDimitry Andric   PA.preserve<MemorySSAAnalysis>();
2354fe6060f1SDimitry Andric   PA.preserve<LoopAnalysis>();
23550b57cec5SDimitry Andric   return PA;
23560b57cec5SDimitry Andric }
2357