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