brintos / llvm-project-archived public Read only

1//===- DeadStoreElimination.cpp - MemorySSA Backed Dead Store Elimination -===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// The code below implements dead store elimination using MemorySSA. It uses10// the following general approach: given a MemoryDef, walk upwards to find11// clobbering MemoryDefs that may be killed by the starting def. Then check12// that there are no uses that may read the location of the original MemoryDef13// in between both MemoryDefs. A bit more concretely:14//15// For all MemoryDefs StartDef:16// 1. Get the next dominating clobbering MemoryDef (MaybeDeadAccess) by walking17//    upwards.18// 2. Check that there are no reads between MaybeDeadAccess and the StartDef by19//    checking all uses starting at MaybeDeadAccess and walking until we see20//    StartDef.21// 3. For each found CurrentDef, check that:22//   1. There are no barrier instructions between CurrentDef and StartDef (like23//       throws or stores with ordering constraints).24//   2. StartDef is executed whenever CurrentDef is executed.25//   3. StartDef completely overwrites CurrentDef.26// 4. Erase CurrentDef from the function and MemorySSA.27//28//===----------------------------------------------------------------------===//29 30#include "llvm/Transforms/Scalar/DeadStoreElimination.h"31#include "llvm/ADT/APInt.h"32#include "llvm/ADT/DenseMap.h"33#include "llvm/ADT/MapVector.h"34#include "llvm/ADT/PostOrderIterator.h"35#include "llvm/ADT/SetVector.h"36#include "llvm/ADT/SmallPtrSet.h"37#include "llvm/ADT/SmallVector.h"38#include "llvm/ADT/Statistic.h"39#include "llvm/ADT/StringRef.h"40#include "llvm/Analysis/AliasAnalysis.h"41#include "llvm/Analysis/AssumptionCache.h"42#include "llvm/Analysis/CaptureTracking.h"43#include "llvm/Analysis/GlobalsModRef.h"44#include "llvm/Analysis/LoopInfo.h"45#include "llvm/Analysis/MemoryBuiltins.h"46#include "llvm/Analysis/MemoryLocation.h"47#include "llvm/Analysis/MemorySSA.h"48#include "llvm/Analysis/MemorySSAUpdater.h"49#include "llvm/Analysis/MustExecute.h"50#include "llvm/Analysis/PostDominators.h"51#include "llvm/Analysis/TargetLibraryInfo.h"52#include "llvm/Analysis/ValueTracking.h"53#include "llvm/IR/Argument.h"54#include "llvm/IR/AttributeMask.h"55#include "llvm/IR/BasicBlock.h"56#include "llvm/IR/Constant.h"57#include "llvm/IR/ConstantRangeList.h"58#include "llvm/IR/Constants.h"59#include "llvm/IR/DataLayout.h"60#include "llvm/IR/DebugInfo.h"61#include "llvm/IR/Dominators.h"62#include "llvm/IR/Function.h"63#include "llvm/IR/IRBuilder.h"64#include "llvm/IR/InstIterator.h"65#include "llvm/IR/InstrTypes.h"66#include "llvm/IR/Instruction.h"67#include "llvm/IR/Instructions.h"68#include "llvm/IR/IntrinsicInst.h"69#include "llvm/IR/Module.h"70#include "llvm/IR/PassManager.h"71#include "llvm/IR/PatternMatch.h"72#include "llvm/IR/Value.h"73#include "llvm/InitializePasses.h"74#include "llvm/Support/Casting.h"75#include "llvm/Support/CommandLine.h"76#include "llvm/Support/Debug.h"77#include "llvm/Support/DebugCounter.h"78#include "llvm/Support/ErrorHandling.h"79#include "llvm/Support/raw_ostream.h"80#include "llvm/Transforms/Scalar.h"81#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"82#include "llvm/Transforms/Utils/BuildLibCalls.h"83#include "llvm/Transforms/Utils/Local.h"84#include <algorithm>85#include <cassert>86#include <cstdint>87#include <map>88#include <optional>89#include <utility>90 91using namespace llvm;92using namespace PatternMatch;93 94#define DEBUG_TYPE "dse"95 96STATISTIC(NumRemainingStores, "Number of stores remaining after DSE");97STATISTIC(NumRedundantStores, "Number of redundant stores deleted");98STATISTIC(NumFastStores, "Number of stores deleted");99STATISTIC(NumFastOther, "Number of other instrs removed");100STATISTIC(NumCompletePartials, "Number of stores dead by later partials");101STATISTIC(NumModifiedStores, "Number of stores modified");102STATISTIC(NumCFGChecks, "Number of stores modified");103STATISTIC(NumCFGTries, "Number of stores modified");104STATISTIC(NumCFGSuccess, "Number of stores modified");105STATISTIC(NumGetDomMemoryDefPassed,106          "Number of times a valid candidate is returned from getDomMemoryDef");107STATISTIC(NumDomMemDefChecks,108          "Number iterations check for reads in getDomMemoryDef");109 110DEBUG_COUNTER(MemorySSACounter, "dse-memoryssa",111              "Controls which MemoryDefs are eliminated.");112 113static cl::opt<bool>114EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",115  cl::init(true), cl::Hidden,116  cl::desc("Enable partial-overwrite tracking in DSE"));117 118static cl::opt<bool>119EnablePartialStoreMerging("enable-dse-partial-store-merging",120  cl::init(true), cl::Hidden,121  cl::desc("Enable partial store merging in DSE"));122 123static cl::opt<unsigned>124    MemorySSAScanLimit("dse-memoryssa-scanlimit", cl::init(150), cl::Hidden,125                       cl::desc("The number of memory instructions to scan for "126                                "dead store elimination (default = 150)"));127static cl::opt<unsigned> MemorySSAUpwardsStepLimit(128    "dse-memoryssa-walklimit", cl::init(90), cl::Hidden,129    cl::desc("The maximum number of steps while walking upwards to find "130             "MemoryDefs that may be killed (default = 90)"));131 132static cl::opt<unsigned> MemorySSAPartialStoreLimit(133    "dse-memoryssa-partial-store-limit", cl::init(5), cl::Hidden,134    cl::desc("The maximum number candidates that only partially overwrite the "135             "killing MemoryDef to consider"136             " (default = 5)"));137 138static cl::opt<unsigned> MemorySSADefsPerBlockLimit(139    "dse-memoryssa-defs-per-block-limit", cl::init(5000), cl::Hidden,140    cl::desc("The number of MemoryDefs we consider as candidates to eliminated "141             "other stores per basic block (default = 5000)"));142 143static cl::opt<unsigned> MemorySSASameBBStepCost(144    "dse-memoryssa-samebb-cost", cl::init(1), cl::Hidden,145    cl::desc(146        "The cost of a step in the same basic block as the killing MemoryDef"147        "(default = 1)"));148 149static cl::opt<unsigned>150    MemorySSAOtherBBStepCost("dse-memoryssa-otherbb-cost", cl::init(5),151                             cl::Hidden,152                             cl::desc("The cost of a step in a different basic "153                                      "block than the killing MemoryDef"154                                      "(default = 5)"));155 156static cl::opt<unsigned> MemorySSAPathCheckLimit(157    "dse-memoryssa-path-check-limit", cl::init(50), cl::Hidden,158    cl::desc("The maximum number of blocks to check when trying to prove that "159             "all paths to an exit go through a killing block (default = 50)"));160 161// This flags allows or disallows DSE to optimize MemorySSA during its162// traversal. Note that DSE optimizing MemorySSA may impact other passes163// downstream of the DSE invocation and can lead to issues not being164// reproducible in isolation (i.e. when MemorySSA is built from scratch). In165// those cases, the flag can be used to check if DSE's MemorySSA optimizations166// impact follow-up passes.167static cl::opt<bool>168    OptimizeMemorySSA("dse-optimize-memoryssa", cl::init(true), cl::Hidden,169                      cl::desc("Allow DSE to optimize memory accesses."));170 171// TODO: remove this flag.172static cl::opt<bool> EnableInitializesImprovement(173    "enable-dse-initializes-attr-improvement", cl::init(true), cl::Hidden,174    cl::desc("Enable the initializes attr improvement in DSE"));175 176//===----------------------------------------------------------------------===//177// Helper functions178//===----------------------------------------------------------------------===//179using OverlapIntervalsTy = std::map<int64_t, int64_t>;180using InstOverlapIntervalsTy = MapVector<Instruction *, OverlapIntervalsTy>;181 182/// Returns true if the end of this instruction can be safely shortened in183/// length.184static bool isShortenableAtTheEnd(Instruction *I) {185  // Don't shorten stores for now186  if (isa<StoreInst>(I))187    return false;188 189  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {190    switch (II->getIntrinsicID()) {191      default: return false;192      case Intrinsic::memset:193      case Intrinsic::memcpy:194      case Intrinsic::memcpy_element_unordered_atomic:195      case Intrinsic::memset_element_unordered_atomic:196        // Do shorten memory intrinsics.197        // FIXME: Add memmove if it's also safe to transform.198        return true;199    }200  }201 202  // Don't shorten libcalls calls for now.203 204  return false;205}206 207/// Returns true if the beginning of this instruction can be safely shortened208/// in length.209static bool isShortenableAtTheBeginning(Instruction *I) {210  // FIXME: Handle only memset for now. Supporting memcpy/memmove should be211  // easily done by offsetting the source address.212  return isa<AnyMemSetInst>(I);213}214 215static std::optional<TypeSize> getPointerSize(const Value *V,216                                              const DataLayout &DL,217                                              const TargetLibraryInfo &TLI,218                                              const Function *F) {219  uint64_t Size;220  ObjectSizeOpts Opts;221  Opts.NullIsUnknownSize = NullPointerIsDefined(F);222 223  if (getObjectSize(V, Size, DL, &TLI, Opts))224    return TypeSize::getFixed(Size);225  return std::nullopt;226}227 228namespace {229 230enum OverwriteResult {231  OW_Begin,232  OW_Complete,233  OW_End,234  OW_PartialEarlierWithFullLater,235  OW_MaybePartial,236  OW_None,237  OW_Unknown238};239 240} // end anonymous namespace241 242/// Check if two instruction are masked stores that completely243/// overwrite one another. More specifically, \p KillingI has to244/// overwrite \p DeadI.245static OverwriteResult isMaskedStoreOverwrite(const Instruction *KillingI,246                                              const Instruction *DeadI,247                                              BatchAAResults &AA) {248  const auto *KillingII = dyn_cast<IntrinsicInst>(KillingI);249  const auto *DeadII = dyn_cast<IntrinsicInst>(DeadI);250  if (KillingII == nullptr || DeadII == nullptr)251    return OW_Unknown;252  if (KillingII->getIntrinsicID() != DeadII->getIntrinsicID())253    return OW_Unknown;254 255  switch (KillingII->getIntrinsicID()) {256  case Intrinsic::masked_store:257  case Intrinsic::vp_store: {258    const DataLayout &DL = KillingII->getDataLayout();259    auto *KillingTy = KillingII->getArgOperand(0)->getType();260    auto *DeadTy = DeadII->getArgOperand(0)->getType();261    if (DL.getTypeSizeInBits(KillingTy) != DL.getTypeSizeInBits(DeadTy))262      return OW_Unknown;263    // Element count.264    if (cast<VectorType>(KillingTy)->getElementCount() !=265        cast<VectorType>(DeadTy)->getElementCount())266      return OW_Unknown;267    // Pointers.268    Value *KillingPtr = KillingII->getArgOperand(1);269    Value *DeadPtr = DeadII->getArgOperand(1);270    if (KillingPtr != DeadPtr && !AA.isMustAlias(KillingPtr, DeadPtr))271      return OW_Unknown;272    if (KillingII->getIntrinsicID() == Intrinsic::masked_store) {273      // Masks.274      // TODO: check that KillingII's mask is a superset of the DeadII's mask.275      if (KillingII->getArgOperand(2) != DeadII->getArgOperand(2))276        return OW_Unknown;277    } else if (KillingII->getIntrinsicID() == Intrinsic::vp_store) {278      // Masks.279      // TODO: check that KillingII's mask is a superset of the DeadII's mask.280      if (KillingII->getArgOperand(2) != DeadII->getArgOperand(2))281        return OW_Unknown;282      // Lengths.283      if (KillingII->getArgOperand(3) != DeadII->getArgOperand(3))284        return OW_Unknown;285    }286    return OW_Complete;287  }288  default:289    return OW_Unknown;290  }291}292 293/// Return 'OW_Complete' if a store to the 'KillingLoc' location completely294/// overwrites a store to the 'DeadLoc' location, 'OW_End' if the end of the295/// 'DeadLoc' location is completely overwritten by 'KillingLoc', 'OW_Begin'296/// if the beginning of the 'DeadLoc' location is overwritten by 'KillingLoc'.297/// 'OW_PartialEarlierWithFullLater' means that a dead (big) store was298/// overwritten by a killing (smaller) store which doesn't write outside the big299/// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.300/// NOTE: This function must only be called if both \p KillingLoc and \p301/// DeadLoc belong to the same underlying object with valid \p KillingOff and302/// \p DeadOff.303static OverwriteResult isPartialOverwrite(const MemoryLocation &KillingLoc,304                                          const MemoryLocation &DeadLoc,305                                          int64_t KillingOff, int64_t DeadOff,306                                          Instruction *DeadI,307                                          InstOverlapIntervalsTy &IOL) {308  const uint64_t KillingSize = KillingLoc.Size.getValue();309  const uint64_t DeadSize = DeadLoc.Size.getValue();310  // We may now overlap, although the overlap is not complete. There might also311  // be other incomplete overlaps, and together, they might cover the complete312  // dead store.313  // Note: The correctness of this logic depends on the fact that this function314  // is not even called providing DepWrite when there are any intervening reads.315  if (EnablePartialOverwriteTracking &&316      KillingOff < int64_t(DeadOff + DeadSize) &&317      int64_t(KillingOff + KillingSize) >= DeadOff) {318 319    // Insert our part of the overlap into the map.320    auto &IM = IOL[DeadI];321    LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: DeadLoc [" << DeadOff << ", "322                      << int64_t(DeadOff + DeadSize) << ") KillingLoc ["323                      << KillingOff << ", " << int64_t(KillingOff + KillingSize)324                      << ")\n");325 326    // Make sure that we only insert non-overlapping intervals and combine327    // adjacent intervals. The intervals are stored in the map with the ending328    // offset as the key (in the half-open sense) and the starting offset as329    // the value.330    int64_t KillingIntStart = KillingOff;331    int64_t KillingIntEnd = KillingOff + KillingSize;332 333    // Find any intervals ending at, or after, KillingIntStart which start334    // before KillingIntEnd.335    auto ILI = IM.lower_bound(KillingIntStart);336    if (ILI != IM.end() && ILI->second <= KillingIntEnd) {337      // This existing interval is overlapped with the current store somewhere338      // in [KillingIntStart, KillingIntEnd]. Merge them by erasing the existing339      // intervals and adjusting our start and end.340      KillingIntStart = std::min(KillingIntStart, ILI->second);341      KillingIntEnd = std::max(KillingIntEnd, ILI->first);342      ILI = IM.erase(ILI);343 344      // Continue erasing and adjusting our end in case other previous345      // intervals are also overlapped with the current store.346      //347      // |--- dead 1 ---|  |--- dead 2 ---|348      //     |------- killing---------|349      //350      while (ILI != IM.end() && ILI->second <= KillingIntEnd) {351        assert(ILI->second > KillingIntStart && "Unexpected interval");352        KillingIntEnd = std::max(KillingIntEnd, ILI->first);353        ILI = IM.erase(ILI);354      }355    }356 357    IM[KillingIntEnd] = KillingIntStart;358 359    ILI = IM.begin();360    if (ILI->second <= DeadOff && ILI->first >= int64_t(DeadOff + DeadSize)) {361      LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: DeadLoc ["362                        << DeadOff << ", " << int64_t(DeadOff + DeadSize)363                        << ") Composite KillingLoc [" << ILI->second << ", "364                        << ILI->first << ")\n");365      ++NumCompletePartials;366      return OW_Complete;367    }368  }369 370  // Check for a dead store which writes to all the memory locations that371  // the killing store writes to.372  if (EnablePartialStoreMerging && KillingOff >= DeadOff &&373      int64_t(DeadOff + DeadSize) > KillingOff &&374      uint64_t(KillingOff - DeadOff) + KillingSize <= DeadSize) {375    LLVM_DEBUG(dbgs() << "DSE: Partial overwrite a dead load [" << DeadOff376                      << ", " << int64_t(DeadOff + DeadSize)377                      << ") by a killing store [" << KillingOff << ", "378                      << int64_t(KillingOff + KillingSize) << ")\n");379    // TODO: Maybe come up with a better name?380    return OW_PartialEarlierWithFullLater;381  }382 383  // Another interesting case is if the killing store overwrites the end of the384  // dead store.385  //386  //      |--dead--|387  //                |--   killing   --|388  //389  // In this case we may want to trim the size of dead store to avoid390  // generating stores to addresses which will definitely be overwritten killing391  // store.392  if (!EnablePartialOverwriteTracking &&393      (KillingOff > DeadOff && KillingOff < int64_t(DeadOff + DeadSize) &&394       int64_t(KillingOff + KillingSize) >= int64_t(DeadOff + DeadSize)))395    return OW_End;396 397  // Finally, we also need to check if the killing store overwrites the398  // beginning of the dead store.399  //400  //                |--dead--|401  //      |--  killing  --|402  //403  // In this case we may want to move the destination address and trim the size404  // of dead store to avoid generating stores to addresses which will definitely405  // be overwritten killing store.406  if (!EnablePartialOverwriteTracking &&407      (KillingOff <= DeadOff && int64_t(KillingOff + KillingSize) > DeadOff)) {408    assert(int64_t(KillingOff + KillingSize) < int64_t(DeadOff + DeadSize) &&409           "Expect to be handled as OW_Complete");410    return OW_Begin;411  }412  // Otherwise, they don't completely overlap.413  return OW_Unknown;414}415 416/// Returns true if the memory which is accessed by the second instruction is not417/// modified between the first and the second instruction.418/// Precondition: Second instruction must be dominated by the first419/// instruction.420static bool421memoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI,422                           BatchAAResults &AA, const DataLayout &DL,423                           DominatorTree *DT) {424  // Do a backwards scan through the CFG from SecondI to FirstI. Look for425  // instructions which can modify the memory location accessed by SecondI.426  //427  // While doing the walk keep track of the address to check. It might be428  // different in different basic blocks due to PHI translation.429  using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;430  SmallVector<BlockAddressPair, 16> WorkList;431  // Keep track of the address we visited each block with. Bail out if we432  // visit a block with different addresses.433  DenseMap<BasicBlock *, Value *> Visited;434 435  BasicBlock::iterator FirstBBI(FirstI);436  ++FirstBBI;437  BasicBlock::iterator SecondBBI(SecondI);438  BasicBlock *FirstBB = FirstI->getParent();439  BasicBlock *SecondBB = SecondI->getParent();440  MemoryLocation MemLoc;441  if (auto *MemSet = dyn_cast<MemSetInst>(SecondI))442    MemLoc = MemoryLocation::getForDest(MemSet);443  else444    MemLoc = MemoryLocation::get(SecondI);445 446  auto *MemLocPtr = const_cast<Value *>(MemLoc.Ptr);447 448  // Start checking the SecondBB.449  WorkList.push_back(450      std::make_pair(SecondBB, PHITransAddr(MemLocPtr, DL, nullptr)));451  bool isFirstBlock = true;452 453  // Check all blocks going backward until we reach the FirstBB.454  while (!WorkList.empty()) {455    BlockAddressPair Current = WorkList.pop_back_val();456    BasicBlock *B = Current.first;457    PHITransAddr &Addr = Current.second;458    Value *Ptr = Addr.getAddr();459 460    // Ignore instructions before FirstI if this is the FirstBB.461    BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());462 463    BasicBlock::iterator EI;464    if (isFirstBlock) {465      // Ignore instructions after SecondI if this is the first visit of SecondBB.466      assert(B == SecondBB && "first block is not the store block");467      EI = SecondBBI;468      isFirstBlock = false;469    } else {470      // It's not SecondBB or (in case of a loop) the second visit of SecondBB.471      // In this case we also have to look at instructions after SecondI.472      EI = B->end();473    }474    for (; BI != EI; ++BI) {475      Instruction *I = &*BI;476      if (I->mayWriteToMemory() && I != SecondI)477        if (isModSet(AA.getModRefInfo(I, MemLoc.getWithNewPtr(Ptr))))478          return false;479    }480    if (B != FirstBB) {481      assert(B != &FirstBB->getParent()->getEntryBlock() &&482          "Should not hit the entry block because SI must be dominated by LI");483      for (BasicBlock *Pred : predecessors(B)) {484        PHITransAddr PredAddr = Addr;485        if (PredAddr.needsPHITranslationFromBlock(B)) {486          if (!PredAddr.isPotentiallyPHITranslatable())487            return false;488          if (!PredAddr.translateValue(B, Pred, DT, false))489            return false;490        }491        Value *TranslatedPtr = PredAddr.getAddr();492        auto Inserted = Visited.insert(std::make_pair(Pred, TranslatedPtr));493        if (!Inserted.second) {494          // We already visited this block before. If it was with a different495          // address - bail out!496          if (TranslatedPtr != Inserted.first->second)497            return false;498          // ... otherwise just skip it.499          continue;500        }501        WorkList.push_back(std::make_pair(Pred, PredAddr));502      }503    }504  }505  return true;506}507 508static void shortenAssignment(Instruction *Inst, Value *OriginalDest,509                              uint64_t OldOffsetInBits, uint64_t OldSizeInBits,510                              uint64_t NewSizeInBits, bool IsOverwriteEnd) {511  const DataLayout &DL = Inst->getDataLayout();512  uint64_t DeadSliceSizeInBits = OldSizeInBits - NewSizeInBits;513  uint64_t DeadSliceOffsetInBits =514      OldOffsetInBits + (IsOverwriteEnd ? NewSizeInBits : 0);515  auto SetDeadFragExpr = [](auto *Assign,516                            DIExpression::FragmentInfo DeadFragment) {517    // createFragmentExpression expects an offset relative to the existing518    // fragment offset if there is one.519    uint64_t RelativeOffset = DeadFragment.OffsetInBits -520                              Assign->getExpression()521                                  ->getFragmentInfo()522                                  .value_or(DIExpression::FragmentInfo(0, 0))523                                  .OffsetInBits;524    if (auto NewExpr = DIExpression::createFragmentExpression(525            Assign->getExpression(), RelativeOffset, DeadFragment.SizeInBits)) {526      Assign->setExpression(*NewExpr);527      return;528    }529    // Failed to create a fragment expression for this so discard the value,530    // making this a kill location.531    auto *Expr = *DIExpression::createFragmentExpression(532        DIExpression::get(Assign->getContext(), {}), DeadFragment.OffsetInBits,533        DeadFragment.SizeInBits);534    Assign->setExpression(Expr);535    Assign->setKillLocation();536  };537 538  // A DIAssignID to use so that the inserted dbg.assign intrinsics do not539  // link to any instructions. Created in the loop below (once).540  DIAssignID *LinkToNothing = nullptr;541  LLVMContext &Ctx = Inst->getContext();542  auto GetDeadLink = [&Ctx, &LinkToNothing]() {543    if (!LinkToNothing)544      LinkToNothing = DIAssignID::getDistinct(Ctx);545    return LinkToNothing;546  };547 548  // Insert an unlinked dbg.assign intrinsic for the dead fragment after each549  // overlapping dbg.assign intrinsic.550  for (DbgVariableRecord *Assign : at::getDVRAssignmentMarkers(Inst)) {551    std::optional<DIExpression::FragmentInfo> NewFragment;552    if (!at::calculateFragmentIntersect(DL, OriginalDest, DeadSliceOffsetInBits,553                                        DeadSliceSizeInBits, Assign,554                                        NewFragment) ||555        !NewFragment) {556      // We couldn't calculate the intersecting fragment for some reason. Be557      // cautious and unlink the whole assignment from the store.558      Assign->setKillAddress();559      Assign->setAssignId(GetDeadLink());560      continue;561    }562    // No intersect.563    if (NewFragment->SizeInBits == 0)564      continue;565 566    // Fragments overlap: insert a new dbg.assign for this dead part.567    auto *NewAssign = static_cast<decltype(Assign)>(Assign->clone());568    NewAssign->insertAfter(Assign->getIterator());569    NewAssign->setAssignId(GetDeadLink());570    if (NewFragment)571      SetDeadFragExpr(NewAssign, *NewFragment);572    NewAssign->setKillAddress();573  }574}575 576/// Update the attributes given that a memory access is updated (the577/// dereferenced pointer could be moved forward when shortening a578/// mem intrinsic).579static void adjustArgAttributes(AnyMemIntrinsic *Intrinsic, unsigned ArgNo,580                                uint64_t PtrOffset) {581  // Remember old attributes.582  AttributeSet OldAttrs = Intrinsic->getParamAttributes(ArgNo);583 584  // Find attributes that should be kept, and remove the rest.585  AttributeMask AttrsToRemove;586  for (auto &Attr : OldAttrs) {587    if (Attr.hasKindAsEnum()) {588      switch (Attr.getKindAsEnum()) {589      default:590        break;591      case Attribute::Alignment:592        // Only keep alignment if PtrOffset satisfy the alignment.593        if (isAligned(Attr.getAlignment().valueOrOne(), PtrOffset))594          continue;595        break;596      case Attribute::Dereferenceable:597      case Attribute::DereferenceableOrNull:598        // We could reduce the size of these attributes according to599        // PtrOffset. But we simply drop these for now.600        break;601      case Attribute::NonNull:602      case Attribute::NoUndef:603        continue;604      }605    }606    AttrsToRemove.addAttribute(Attr);607  }608 609  // Remove the attributes that should be dropped.610  Intrinsic->removeParamAttrs(ArgNo, AttrsToRemove);611}612 613static bool tryToShorten(Instruction *DeadI, int64_t &DeadStart,614                         uint64_t &DeadSize, int64_t KillingStart,615                         uint64_t KillingSize, bool IsOverwriteEnd) {616  auto *DeadIntrinsic = cast<AnyMemIntrinsic>(DeadI);617  Align PrefAlign = DeadIntrinsic->getDestAlign().valueOrOne();618 619  // We assume that memet/memcpy operates in chunks of the "largest" native620  // type size and aligned on the same value. That means optimal start and size621  // of memset/memcpy should be modulo of preferred alignment of that type. That622  // is it there is no any sense in trying to reduce store size any further623  // since any "extra" stores comes for free anyway.624  // On the other hand, maximum alignment we can achieve is limited by alignment625  // of initial store.626 627  // TODO: Limit maximum alignment by preferred (or abi?) alignment of the628  // "largest" native type.629  // Note: What is the proper way to get that value?630  // Should TargetTransformInfo::getRegisterBitWidth be used or anything else?631  // PrefAlign = std::min(DL.getPrefTypeAlign(LargestType), PrefAlign);632 633  int64_t ToRemoveStart = 0;634  uint64_t ToRemoveSize = 0;635  // Compute start and size of the region to remove. Make sure 'PrefAlign' is636  // maintained on the remaining store.637  if (IsOverwriteEnd) {638    // Calculate required adjustment for 'KillingStart' in order to keep639    // remaining store size aligned on 'PerfAlign'.640    uint64_t Off =641        offsetToAlignment(uint64_t(KillingStart - DeadStart), PrefAlign);642    ToRemoveStart = KillingStart + Off;643    if (DeadSize <= uint64_t(ToRemoveStart - DeadStart))644      return false;645    ToRemoveSize = DeadSize - uint64_t(ToRemoveStart - DeadStart);646  } else {647    ToRemoveStart = DeadStart;648    assert(KillingSize >= uint64_t(DeadStart - KillingStart) &&649           "Not overlapping accesses?");650    ToRemoveSize = KillingSize - uint64_t(DeadStart - KillingStart);651    // Calculate required adjustment for 'ToRemoveSize'in order to keep652    // start of the remaining store aligned on 'PerfAlign'.653    uint64_t Off = offsetToAlignment(ToRemoveSize, PrefAlign);654    if (Off != 0) {655      if (ToRemoveSize <= (PrefAlign.value() - Off))656        return false;657      ToRemoveSize -= PrefAlign.value() - Off;658    }659    assert(isAligned(PrefAlign, ToRemoveSize) &&660           "Should preserve selected alignment");661  }662 663  assert(ToRemoveSize > 0 && "Shouldn't reach here if nothing to remove");664  assert(DeadSize > ToRemoveSize && "Can't remove more than original size");665 666  uint64_t NewSize = DeadSize - ToRemoveSize;667  if (DeadIntrinsic->isAtomic()) {668    // When shortening an atomic memory intrinsic, the newly shortened669    // length must remain an integer multiple of the element size.670    const uint32_t ElementSize = DeadIntrinsic->getElementSizeInBytes();671    if (0 != NewSize % ElementSize)672      return false;673  }674 675  LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  OW "676                    << (IsOverwriteEnd ? "END" : "BEGIN") << ": " << *DeadI677                    << "\n  KILLER [" << ToRemoveStart << ", "678                    << int64_t(ToRemoveStart + ToRemoveSize) << ")\n");679 680  DeadIntrinsic->setLength(NewSize);681  DeadIntrinsic->setDestAlignment(PrefAlign);682 683  Value *OrigDest = DeadIntrinsic->getRawDest();684  if (!IsOverwriteEnd) {685    Value *Indices[1] = {686        ConstantInt::get(DeadIntrinsic->getLength()->getType(), ToRemoveSize)};687    Instruction *NewDestGEP = GetElementPtrInst::CreateInBounds(688        Type::getInt8Ty(DeadIntrinsic->getContext()), OrigDest, Indices, "",689        DeadI->getIterator());690    NewDestGEP->setDebugLoc(DeadIntrinsic->getDebugLoc());691    DeadIntrinsic->setDest(NewDestGEP);692    adjustArgAttributes(DeadIntrinsic, 0, ToRemoveSize);693  }694 695  // Update attached dbg.assign intrinsics. Assume 8-bit byte.696  shortenAssignment(DeadI, OrigDest, DeadStart * 8, DeadSize * 8, NewSize * 8,697                    IsOverwriteEnd);698 699  // Finally update start and size of dead access.700  if (!IsOverwriteEnd)701    DeadStart += ToRemoveSize;702  DeadSize = NewSize;703 704  return true;705}706 707static bool tryToShortenEnd(Instruction *DeadI, OverlapIntervalsTy &IntervalMap,708                            int64_t &DeadStart, uint64_t &DeadSize) {709  if (IntervalMap.empty() || !isShortenableAtTheEnd(DeadI))710    return false;711 712  OverlapIntervalsTy::iterator OII = --IntervalMap.end();713  int64_t KillingStart = OII->second;714  uint64_t KillingSize = OII->first - KillingStart;715 716  assert(OII->first - KillingStart >= 0 && "Size expected to be positive");717 718  if (KillingStart > DeadStart &&719      // Note: "KillingStart - KillingStart" is known to be positive due to720      // preceding check.721      (uint64_t)(KillingStart - DeadStart) < DeadSize &&722      // Note: "DeadSize - (uint64_t)(KillingStart - DeadStart)" is known to723      // be non negative due to preceding checks.724      KillingSize >= DeadSize - (uint64_t)(KillingStart - DeadStart)) {725    if (tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,726                     true)) {727      IntervalMap.erase(OII);728      return true;729    }730  }731  return false;732}733 734static bool tryToShortenBegin(Instruction *DeadI,735                              OverlapIntervalsTy &IntervalMap,736                              int64_t &DeadStart, uint64_t &DeadSize) {737  if (IntervalMap.empty() || !isShortenableAtTheBeginning(DeadI))738    return false;739 740  OverlapIntervalsTy::iterator OII = IntervalMap.begin();741  int64_t KillingStart = OII->second;742  uint64_t KillingSize = OII->first - KillingStart;743 744  assert(OII->first - KillingStart >= 0 && "Size expected to be positive");745 746  if (KillingStart <= DeadStart &&747      // Note: "DeadStart - KillingStart" is known to be non negative due to748      // preceding check.749      KillingSize > (uint64_t)(DeadStart - KillingStart)) {750    // Note: "KillingSize - (uint64_t)(DeadStart - DeadStart)" is known to751    // be positive due to preceding checks.752    assert(KillingSize - (uint64_t)(DeadStart - KillingStart) < DeadSize &&753           "Should have been handled as OW_Complete");754    if (tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,755                     false)) {756      IntervalMap.erase(OII);757      return true;758    }759  }760  return false;761}762 763static Constant *764tryToMergePartialOverlappingStores(StoreInst *KillingI, StoreInst *DeadI,765                                   int64_t KillingOffset, int64_t DeadOffset,766                                   const DataLayout &DL, BatchAAResults &AA,767                                   DominatorTree *DT) {768 769  if (DeadI && isa<ConstantInt>(DeadI->getValueOperand()) &&770      DL.typeSizeEqualsStoreSize(DeadI->getValueOperand()->getType()) &&771      KillingI && isa<ConstantInt>(KillingI->getValueOperand()) &&772      DL.typeSizeEqualsStoreSize(KillingI->getValueOperand()->getType()) &&773      memoryIsNotModifiedBetween(DeadI, KillingI, AA, DL, DT)) {774    // If the store we find is:775    //   a) partially overwritten by the store to 'Loc'776    //   b) the killing store is fully contained in the dead one and777    //   c) they both have a constant value778    //   d) none of the two stores need padding779    // Merge the two stores, replacing the dead store's value with a780    // merge of both values.781    // TODO: Deal with other constant types (vectors, etc), and probably782    // some mem intrinsics (if needed)783 784    APInt DeadValue = cast<ConstantInt>(DeadI->getValueOperand())->getValue();785    APInt KillingValue =786        cast<ConstantInt>(KillingI->getValueOperand())->getValue();787    unsigned KillingBits = KillingValue.getBitWidth();788    assert(DeadValue.getBitWidth() > KillingValue.getBitWidth());789    KillingValue = KillingValue.zext(DeadValue.getBitWidth());790 791    // Offset of the smaller store inside the larger store792    unsigned BitOffsetDiff = (KillingOffset - DeadOffset) * 8;793    unsigned LShiftAmount =794        DL.isBigEndian() ? DeadValue.getBitWidth() - BitOffsetDiff - KillingBits795                         : BitOffsetDiff;796    APInt Mask = APInt::getBitsSet(DeadValue.getBitWidth(), LShiftAmount,797                                   LShiftAmount + KillingBits);798    // Clear the bits we'll be replacing, then OR with the smaller799    // store, shifted appropriately.800    APInt Merged = (DeadValue & ~Mask) | (KillingValue << LShiftAmount);801    LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n  Dead: " << *DeadI802                      << "\n  Killing: " << *KillingI803                      << "\n  Merged Value: " << Merged << '\n');804    return ConstantInt::get(DeadI->getValueOperand()->getType(), Merged);805  }806  return nullptr;807}808 809// Returns true if \p I is an intrinsic that does not read or write memory.810static bool isNoopIntrinsic(Instruction *I) {811  if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {812    switch (II->getIntrinsicID()) {813    case Intrinsic::lifetime_start:814    case Intrinsic::lifetime_end:815    case Intrinsic::invariant_end:816    case Intrinsic::launder_invariant_group:817    case Intrinsic::assume:818      return true;819    case Intrinsic::dbg_declare:820    case Intrinsic::dbg_label:821    case Intrinsic::dbg_value:822      llvm_unreachable("Intrinsic should not be modeled in MemorySSA");823    default:824      return false;825    }826  }827  return false;828}829 830// Check if we can ignore \p D for DSE.831static bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller) {832  Instruction *DI = D->getMemoryInst();833  // Calls that only access inaccessible memory cannot read or write any memory834  // locations we consider for elimination.835  if (auto *CB = dyn_cast<CallBase>(DI))836    if (CB->onlyAccessesInaccessibleMemory())837      return true;838 839  // We can eliminate stores to locations not visible to the caller across840  // throwing instructions.841  if (DI->mayThrow() && !DefVisibleToCaller)842    return true;843 844  // We can remove the dead stores, irrespective of the fence and its ordering845  // (release/acquire/seq_cst). Fences only constraints the ordering of846  // already visible stores, it does not make a store visible to other847  // threads. So, skipping over a fence does not change a store from being848  // dead.849  if (isa<FenceInst>(DI))850    return true;851 852  // Skip intrinsics that do not really read or modify memory.853  if (isNoopIntrinsic(DI))854    return true;855 856  return false;857}858 859namespace {860 861// A memory location wrapper that represents a MemoryLocation, `MemLoc`,862// defined by `MemDef`.863struct MemoryLocationWrapper {864  MemoryLocationWrapper(MemoryLocation MemLoc, MemoryDef *MemDef,865                        bool DefByInitializesAttr)866      : MemLoc(MemLoc), MemDef(MemDef),867        DefByInitializesAttr(DefByInitializesAttr) {868    assert(MemLoc.Ptr && "MemLoc should be not null");869    UnderlyingObject = getUnderlyingObject(MemLoc.Ptr);870    DefInst = MemDef->getMemoryInst();871  }872 873  MemoryLocation MemLoc;874  const Value *UnderlyingObject;875  MemoryDef *MemDef;876  Instruction *DefInst;877  bool DefByInitializesAttr = false;878};879 880// A memory def wrapper that represents a MemoryDef and the MemoryLocation(s)881// defined by this MemoryDef.882struct MemoryDefWrapper {883  MemoryDefWrapper(MemoryDef *MemDef,884                   ArrayRef<std::pair<MemoryLocation, bool>> MemLocations) {885    DefInst = MemDef->getMemoryInst();886    for (auto &[MemLoc, DefByInitializesAttr] : MemLocations)887      DefinedLocations.push_back(888          MemoryLocationWrapper(MemLoc, MemDef, DefByInitializesAttr));889  }890  Instruction *DefInst;891  SmallVector<MemoryLocationWrapper, 1> DefinedLocations;892};893 894struct ArgumentInitInfo {895  unsigned Idx;896  bool IsDeadOrInvisibleOnUnwind;897  ConstantRangeList Inits;898};899} // namespace900 901static bool hasInitializesAttr(Instruction *I) {902  CallBase *CB = dyn_cast<CallBase>(I);903  return CB && CB->getArgOperandWithAttribute(Attribute::Initializes);904}905 906// Return the intersected range list of the initializes attributes of "Args".907// "Args" are call arguments that alias to each other.908// If any argument in "Args" doesn't have dead_on_unwind attr and909// "CallHasNoUnwindAttr" is false, return empty.910static ConstantRangeList911getIntersectedInitRangeList(ArrayRef<ArgumentInitInfo> Args,912                            bool CallHasNoUnwindAttr) {913  if (Args.empty())914    return {};915 916  // To address unwind, the function should have nounwind attribute or the917  // arguments have dead or invisible on unwind. Otherwise, return empty.918  for (const auto &Arg : Args) {919    if (!CallHasNoUnwindAttr && !Arg.IsDeadOrInvisibleOnUnwind)920      return {};921    if (Arg.Inits.empty())922      return {};923  }924 925  ConstantRangeList IntersectedIntervals = Args.front().Inits;926  for (auto &Arg : Args.drop_front())927    IntersectedIntervals = IntersectedIntervals.intersectWith(Arg.Inits);928 929  return IntersectedIntervals;930}931 932namespace {933 934struct DSEState {935  Function &F;936  AliasAnalysis &AA;937  EarliestEscapeAnalysis EA;938 939  /// The single BatchAA instance that is used to cache AA queries. It will940  /// not be invalidated over the whole run. This is safe, because:941  /// 1. Only memory writes are removed, so the alias cache for memory942  ///    locations remains valid.943  /// 2. No new instructions are added (only instructions removed), so cached944  ///    information for a deleted value cannot be accessed by a re-used new945  ///    value pointer.946  BatchAAResults BatchAA;947 948  MemorySSA &MSSA;949  DominatorTree &DT;950  PostDominatorTree &PDT;951  const TargetLibraryInfo &TLI;952  const DataLayout &DL;953  const LoopInfo &LI;954 955  // Whether the function contains any irreducible control flow, useful for956  // being accurately able to detect loops.957  bool ContainsIrreducibleLoops;958 959  // All MemoryDefs that potentially could kill other MemDefs.960  SmallVector<MemoryDef *, 64> MemDefs;961  // Any that should be skipped as they are already deleted962  SmallPtrSet<MemoryAccess *, 4> SkipStores;963  // Keep track whether a given object is captured before return or not.964  DenseMap<const Value *, bool> CapturedBeforeReturn;965  // Keep track of all of the objects that are invisible to the caller after966  // the function returns.967  DenseMap<const Value *, bool> InvisibleToCallerAfterRet;968  // Keep track of blocks with throwing instructions not modeled in MemorySSA.969  SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;970  // Post-order numbers for each basic block. Used to figure out if memory971  // accesses are executed before another access.972  DenseMap<BasicBlock *, unsigned> PostOrderNumbers;973 974  /// Keep track of instructions (partly) overlapping with killing MemoryDefs per975  /// basic block.976  MapVector<BasicBlock *, InstOverlapIntervalsTy> IOLs;977  // Check if there are root nodes that are terminated by UnreachableInst.978  // Those roots pessimize post-dominance queries. If there are such roots,979  // fall back to CFG scan starting from all non-unreachable roots.980  bool AnyUnreachableExit;981 982  // Whether or not we should iterate on removing dead stores at the end of the983  // function due to removing a store causing a previously captured pointer to984  // no longer be captured.985  bool ShouldIterateEndOfFunctionDSE;986 987  /// Dead instructions to be removed at the end of DSE.988  SmallVector<Instruction *> ToRemove;989 990  // Class contains self-reference, make sure it's not copied/moved.991  DSEState(const DSEState &) = delete;992  DSEState &operator=(const DSEState &) = delete;993 994  DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,995           PostDominatorTree &PDT, const TargetLibraryInfo &TLI,996           const LoopInfo &LI)997      : F(F), AA(AA), EA(DT, &LI), BatchAA(AA, &EA), MSSA(MSSA), DT(DT),998        PDT(PDT), TLI(TLI), DL(F.getDataLayout()), LI(LI) {999    // Collect blocks with throwing instructions not modeled in MemorySSA and1000    // alloc-like objects.1001    unsigned PO = 0;1002    for (BasicBlock *BB : post_order(&F)) {1003      PostOrderNumbers[BB] = PO++;1004      for (Instruction &I : *BB) {1005        MemoryAccess *MA = MSSA.getMemoryAccess(&I);1006        if (I.mayThrow() && !MA)1007          ThrowingBlocks.insert(I.getParent());1008 1009        auto *MD = dyn_cast_or_null<MemoryDef>(MA);1010        if (MD && MemDefs.size() < MemorySSADefsPerBlockLimit &&1011            (getLocForWrite(&I) || isMemTerminatorInst(&I) ||1012             (EnableInitializesImprovement && hasInitializesAttr(&I))))1013          MemDefs.push_back(MD);1014      }1015    }1016 1017    // Treat byval, inalloca or dead on return arguments the same as Allocas,1018    // stores to them are dead at the end of the function.1019    for (Argument &AI : F.args())1020      if (AI.hasPassPointeeByValueCopyAttr() || AI.hasDeadOnReturnAttr())1021        InvisibleToCallerAfterRet.insert({&AI, true});1022 1023    // Collect whether there is any irreducible control flow in the function.1024    ContainsIrreducibleLoops = mayContainIrreducibleControl(F, &LI);1025 1026    AnyUnreachableExit = any_of(PDT.roots(), [](const BasicBlock *E) {1027      return isa<UnreachableInst>(E->getTerminator());1028    });1029  }1030 1031  static void pushMemUses(MemoryAccess *Acc,1032                          SmallVectorImpl<MemoryAccess *> &WorkList,1033                          SmallPtrSetImpl<MemoryAccess *> &Visited) {1034    for (Use &U : Acc->uses()) {1035      auto *MA = cast<MemoryAccess>(U.getUser());1036      if (Visited.insert(MA).second)1037        WorkList.push_back(MA);1038    }1039  };1040 1041  LocationSize strengthenLocationSize(const Instruction *I,1042                                      LocationSize Size) const {1043    if (auto *CB = dyn_cast<CallBase>(I)) {1044      LibFunc F;1045      if (TLI.getLibFunc(*CB, F) && TLI.has(F) &&1046          (F == LibFunc_memset_chk || F == LibFunc_memcpy_chk)) {1047        // Use the precise location size specified by the 3rd argument1048        // for determining KillingI overwrites DeadLoc if it is a memset_chk1049        // instruction. memset_chk will write either the amount specified as 3rd1050        // argument or the function will immediately abort and exit the program.1051        // NOTE: AA may determine NoAlias if it can prove that the access size1052        // is larger than the allocation size due to that being UB. To avoid1053        // returning potentially invalid NoAlias results by AA, limit the use of1054        // the precise location size to isOverwrite.1055        if (const auto *Len = dyn_cast<ConstantInt>(CB->getArgOperand(2)))1056          return LocationSize::precise(Len->getZExtValue());1057      }1058    }1059    return Size;1060  }1061 1062  /// Return 'OW_Complete' if a store to the 'KillingLoc' location (by \p1063  /// KillingI instruction) completely overwrites a store to the 'DeadLoc'1064  /// location (by \p DeadI instruction).1065  /// Return OW_MaybePartial if \p KillingI does not completely overwrite1066  /// \p DeadI, but they both write to the same underlying object. In that1067  /// case, use isPartialOverwrite to check if \p KillingI partially overwrites1068  /// \p DeadI. Returns 'OR_None' if \p KillingI is known to not overwrite the1069  /// \p DeadI. Returns 'OW_Unknown' if nothing can be determined.1070  OverwriteResult isOverwrite(const Instruction *KillingI,1071                              const Instruction *DeadI,1072                              const MemoryLocation &KillingLoc,1073                              const MemoryLocation &DeadLoc,1074                              int64_t &KillingOff, int64_t &DeadOff) {1075    // AliasAnalysis does not always account for loops. Limit overwrite checks1076    // to dependencies for which we can guarantee they are independent of any1077    // loops they are in.1078    if (!isGuaranteedLoopIndependent(DeadI, KillingI, DeadLoc))1079      return OW_Unknown;1080 1081    LocationSize KillingLocSize =1082        strengthenLocationSize(KillingI, KillingLoc.Size);1083    const Value *DeadPtr = DeadLoc.Ptr->stripPointerCasts();1084    const Value *KillingPtr = KillingLoc.Ptr->stripPointerCasts();1085    const Value *DeadUndObj = getUnderlyingObject(DeadPtr);1086    const Value *KillingUndObj = getUnderlyingObject(KillingPtr);1087 1088    // Check whether the killing store overwrites the whole object, in which1089    // case the size/offset of the dead store does not matter.1090    if (DeadUndObj == KillingUndObj && KillingLocSize.isPrecise() &&1091        isIdentifiedObject(KillingUndObj)) {1092      std::optional<TypeSize> KillingUndObjSize =1093          getPointerSize(KillingUndObj, DL, TLI, &F);1094      if (KillingUndObjSize && *KillingUndObjSize == KillingLocSize.getValue())1095        return OW_Complete;1096    }1097 1098    // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll1099    // get imprecise values here, though (except for unknown sizes).1100    if (!KillingLocSize.isPrecise() || !DeadLoc.Size.isPrecise()) {1101      // In case no constant size is known, try to an IR values for the number1102      // of bytes written and check if they match.1103      const auto *KillingMemI = dyn_cast<MemIntrinsic>(KillingI);1104      const auto *DeadMemI = dyn_cast<MemIntrinsic>(DeadI);1105      if (KillingMemI && DeadMemI) {1106        const Value *KillingV = KillingMemI->getLength();1107        const Value *DeadV = DeadMemI->getLength();1108        if (KillingV == DeadV && BatchAA.isMustAlias(DeadLoc, KillingLoc))1109          return OW_Complete;1110      }1111 1112      // Masked stores have imprecise locations, but we can reason about them1113      // to some extent.1114      return isMaskedStoreOverwrite(KillingI, DeadI, BatchAA);1115    }1116 1117    const TypeSize KillingSize = KillingLocSize.getValue();1118    const TypeSize DeadSize = DeadLoc.Size.getValue();1119    // Bail on doing Size comparison which depends on AA for now1120    // TODO: Remove AnyScalable once Alias Analysis deal with scalable vectors1121    const bool AnyScalable =1122        DeadSize.isScalable() || KillingLocSize.isScalable();1123 1124    if (AnyScalable)1125      return OW_Unknown;1126    // Query the alias information1127    AliasResult AAR = BatchAA.alias(KillingLoc, DeadLoc);1128 1129    // If the start pointers are the same, we just have to compare sizes to see if1130    // the killing store was larger than the dead store.1131    if (AAR == AliasResult::MustAlias) {1132      // Make sure that the KillingSize size is >= the DeadSize size.1133      if (KillingSize >= DeadSize)1134        return OW_Complete;1135    }1136 1137    // If we hit a partial alias we may have a full overwrite1138    if (AAR == AliasResult::PartialAlias && AAR.hasOffset()) {1139      int32_t Off = AAR.getOffset();1140      if (Off >= 0 && (uint64_t)Off + DeadSize <= KillingSize)1141        return OW_Complete;1142    }1143 1144    // If we can't resolve the same pointers to the same object, then we can't1145    // analyze them at all.1146    if (DeadUndObj != KillingUndObj) {1147      // Non aliasing stores to different objects don't overlap. Note that1148      // if the killing store is known to overwrite whole object (out of1149      // bounds access overwrites whole object as well) then it is assumed to1150      // completely overwrite any store to the same object even if they don't1151      // actually alias (see next check).1152      if (AAR == AliasResult::NoAlias)1153        return OW_None;1154      return OW_Unknown;1155    }1156 1157    // Okay, we have stores to two completely different pointers.  Try to1158    // decompose the pointer into a "base + constant_offset" form.  If the base1159    // pointers are equal, then we can reason about the two stores.1160    DeadOff = 0;1161    KillingOff = 0;1162    const Value *DeadBasePtr =1163        GetPointerBaseWithConstantOffset(DeadPtr, DeadOff, DL);1164    const Value *KillingBasePtr =1165        GetPointerBaseWithConstantOffset(KillingPtr, KillingOff, DL);1166 1167    // If the base pointers still differ, we have two completely different1168    // stores.1169    if (DeadBasePtr != KillingBasePtr)1170      return OW_Unknown;1171 1172    // The killing access completely overlaps the dead store if and only if1173    // both start and end of the dead one is "inside" the killing one:1174    //    |<->|--dead--|<->|1175    //    |-----killing------|1176    // Accesses may overlap if and only if start of one of them is "inside"1177    // another one:1178    //    |<->|--dead--|<-------->|1179    //    |-------killing--------|1180    //           OR1181    //    |-------dead-------|1182    //    |<->|---killing---|<----->|1183    //1184    // We have to be careful here as *Off is signed while *.Size is unsigned.1185 1186    // Check if the dead access starts "not before" the killing one.1187    if (DeadOff >= KillingOff) {1188      // If the dead access ends "not after" the killing access then the1189      // dead one is completely overwritten by the killing one.1190      if (uint64_t(DeadOff - KillingOff) + DeadSize <= KillingSize)1191        return OW_Complete;1192      // If start of the dead access is "before" end of the killing access1193      // then accesses overlap.1194      else if ((uint64_t)(DeadOff - KillingOff) < KillingSize)1195        return OW_MaybePartial;1196    }1197    // If start of the killing access is "before" end of the dead access then1198    // accesses overlap.1199    else if ((uint64_t)(KillingOff - DeadOff) < DeadSize) {1200      return OW_MaybePartial;1201    }1202 1203    // Can reach here only if accesses are known not to overlap.1204    return OW_None;1205  }1206 1207  bool isInvisibleToCallerAfterRet(const Value *V) {1208    if (isa<AllocaInst>(V))1209      return true;1210 1211    auto I = InvisibleToCallerAfterRet.insert({V, false});1212    if (I.second && isInvisibleToCallerOnUnwind(V) && isNoAliasCall(V))1213      I.first->second = capturesNothing(PointerMayBeCaptured(1214          V, /*ReturnCaptures=*/true, CaptureComponents::Provenance));1215    return I.first->second;1216  }1217 1218  bool isInvisibleToCallerOnUnwind(const Value *V) {1219    bool RequiresNoCaptureBeforeUnwind;1220    if (!isNotVisibleOnUnwind(V, RequiresNoCaptureBeforeUnwind))1221      return false;1222    if (!RequiresNoCaptureBeforeUnwind)1223      return true;1224 1225    auto I = CapturedBeforeReturn.insert({V, true});1226    if (I.second)1227      // NOTE: This could be made more precise by PointerMayBeCapturedBefore1228      // with the killing MemoryDef. But we refrain from doing so for now to1229      // limit compile-time and this does not cause any changes to the number1230      // of stores removed on a large test set in practice.1231      I.first->second = capturesAnything(PointerMayBeCaptured(1232          V, /*ReturnCaptures=*/false, CaptureComponents::Provenance));1233    return !I.first->second;1234  }1235 1236  std::optional<MemoryLocation> getLocForWrite(Instruction *I) const {1237    if (!I->mayWriteToMemory())1238      return std::nullopt;1239 1240    if (auto *CB = dyn_cast<CallBase>(I))1241      return MemoryLocation::getForDest(CB, TLI);1242 1243    return MemoryLocation::getOrNone(I);1244  }1245 1246  // Returns a list of <MemoryLocation, bool> pairs written by I.1247  // The bool means whether the write is from Initializes attr.1248  SmallVector<std::pair<MemoryLocation, bool>, 1>1249  getLocForInst(Instruction *I, bool ConsiderInitializesAttr) {1250    SmallVector<std::pair<MemoryLocation, bool>, 1> Locations;1251    if (isMemTerminatorInst(I)) {1252      if (auto Loc = getLocForTerminator(I))1253        Locations.push_back(std::make_pair(Loc->first, false));1254      return Locations;1255    }1256 1257    if (auto Loc = getLocForWrite(I))1258      Locations.push_back(std::make_pair(*Loc, false));1259 1260    if (ConsiderInitializesAttr) {1261      for (auto &MemLoc : getInitializesArgMemLoc(I)) {1262        Locations.push_back(std::make_pair(MemLoc, true));1263      }1264    }1265    return Locations;1266  }1267 1268  /// Assuming this instruction has a dead analyzable write, can we delete1269  /// this instruction?1270  bool isRemovable(Instruction *I) {1271    assert(getLocForWrite(I) && "Must have analyzable write");1272 1273    // Don't remove volatile/atomic stores.1274    if (StoreInst *SI = dyn_cast<StoreInst>(I))1275      return SI->isUnordered();1276 1277    if (auto *CB = dyn_cast<CallBase>(I)) {1278      // Don't remove volatile memory intrinsics.1279      if (auto *MI = dyn_cast<MemIntrinsic>(CB))1280        return !MI->isVolatile();1281 1282      // Never remove dead lifetime intrinsics, e.g. because they are followed1283      // by a free.1284      if (CB->isLifetimeStartOrEnd())1285        return false;1286 1287      return CB->use_empty() && CB->willReturn() && CB->doesNotThrow() &&1288             !CB->isTerminator();1289    }1290 1291    return false;1292  }1293 1294  /// Returns true if \p UseInst completely overwrites \p DefLoc1295  /// (stored by \p DefInst).1296  bool isCompleteOverwrite(const MemoryLocation &DefLoc, Instruction *DefInst,1297                           Instruction *UseInst) {1298    // UseInst has a MemoryDef associated in MemorySSA. It's possible for a1299    // MemoryDef to not write to memory, e.g. a volatile load is modeled as a1300    // MemoryDef.1301    if (!UseInst->mayWriteToMemory())1302      return false;1303 1304    if (auto *CB = dyn_cast<CallBase>(UseInst))1305      if (CB->onlyAccessesInaccessibleMemory())1306        return false;1307 1308    int64_t InstWriteOffset, DepWriteOffset;1309    if (auto CC = getLocForWrite(UseInst))1310      return isOverwrite(UseInst, DefInst, *CC, DefLoc, InstWriteOffset,1311                         DepWriteOffset) == OW_Complete;1312    return false;1313  }1314 1315  /// Returns true if \p Def is not read before returning from the function.1316  bool isWriteAtEndOfFunction(MemoryDef *Def, const MemoryLocation &DefLoc) {1317    LLVM_DEBUG(dbgs() << "  Check if def " << *Def << " ("1318                      << *Def->getMemoryInst()1319                      << ") is at the end the function \n");1320    SmallVector<MemoryAccess *, 4> WorkList;1321    SmallPtrSet<MemoryAccess *, 8> Visited;1322 1323    pushMemUses(Def, WorkList, Visited);1324    for (unsigned I = 0; I < WorkList.size(); I++) {1325      if (WorkList.size() >= MemorySSAScanLimit) {1326        LLVM_DEBUG(dbgs() << "  ... hit exploration limit.\n");1327        return false;1328      }1329 1330      MemoryAccess *UseAccess = WorkList[I];1331      if (isa<MemoryPhi>(UseAccess)) {1332        // AliasAnalysis does not account for loops. Limit elimination to1333        // candidates for which we can guarantee they always store to the same1334        // memory location.1335        if (!isGuaranteedLoopInvariant(DefLoc.Ptr))1336          return false;1337 1338        pushMemUses(cast<MemoryPhi>(UseAccess), WorkList, Visited);1339        continue;1340      }1341      // TODO: Checking for aliasing is expensive. Consider reducing the amount1342      // of times this is called and/or caching it.1343      Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();1344      if (isReadClobber(DefLoc, UseInst)) {1345        LLVM_DEBUG(dbgs() << "  ... hit read clobber " << *UseInst << ".\n");1346        return false;1347      }1348 1349      if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))1350        pushMemUses(UseDef, WorkList, Visited);1351    }1352    return true;1353  }1354 1355  /// If \p I is a memory  terminator like llvm.lifetime.end or free, return a1356  /// pair with the MemoryLocation terminated by \p I and a boolean flag1357  /// indicating whether \p I is a free-like call.1358  std::optional<std::pair<MemoryLocation, bool>>1359  getLocForTerminator(Instruction *I) const {1360    if (auto *CB = dyn_cast<CallBase>(I)) {1361      if (CB->getIntrinsicID() == Intrinsic::lifetime_end)1362        return {1363            std::make_pair(MemoryLocation::getForArgument(CB, 0, &TLI), false)};1364      if (Value *FreedOp = getFreedOperand(CB, &TLI))1365        return {std::make_pair(MemoryLocation::getAfter(FreedOp), true)};1366    }1367 1368    return std::nullopt;1369  }1370 1371  /// Returns true if \p I is a memory terminator instruction like1372  /// llvm.lifetime.end or free.1373  bool isMemTerminatorInst(Instruction *I) const {1374    auto *CB = dyn_cast<CallBase>(I);1375    return CB && (CB->getIntrinsicID() == Intrinsic::lifetime_end ||1376                  getFreedOperand(CB, &TLI) != nullptr);1377  }1378 1379  /// Returns true if \p MaybeTerm is a memory terminator for \p Loc from1380  /// instruction \p AccessI.1381  bool isMemTerminator(const MemoryLocation &Loc, Instruction *AccessI,1382                       Instruction *MaybeTerm) {1383    std::optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =1384        getLocForTerminator(MaybeTerm);1385 1386    if (!MaybeTermLoc)1387      return false;1388 1389    // If the terminator is a free-like call, all accesses to the underlying1390    // object can be considered terminated.1391    if (getUnderlyingObject(Loc.Ptr) !=1392        getUnderlyingObject(MaybeTermLoc->first.Ptr))1393      return false;1394 1395    auto TermLoc = MaybeTermLoc->first;1396    if (MaybeTermLoc->second) {1397      const Value *LocUO = getUnderlyingObject(Loc.Ptr);1398      return BatchAA.isMustAlias(TermLoc.Ptr, LocUO);1399    }1400    int64_t InstWriteOffset = 0;1401    int64_t DepWriteOffset = 0;1402    return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, InstWriteOffset,1403                       DepWriteOffset) == OW_Complete;1404  }1405 1406  // Returns true if \p Use may read from \p DefLoc.1407  bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {1408    if (isNoopIntrinsic(UseInst))1409      return false;1410 1411    // Monotonic or weaker atomic stores can be re-ordered and do not need to be1412    // treated as read clobber.1413    if (auto SI = dyn_cast<StoreInst>(UseInst))1414      return isStrongerThan(SI->getOrdering(), AtomicOrdering::Monotonic);1415 1416    if (!UseInst->mayReadFromMemory())1417      return false;1418 1419    if (auto *CB = dyn_cast<CallBase>(UseInst))1420      if (CB->onlyAccessesInaccessibleMemory())1421        return false;1422 1423    return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));1424  }1425 1426  /// Returns true if a dependency between \p Current and \p KillingDef is1427  /// guaranteed to be loop invariant for the loops that they are in. Either1428  /// because they are known to be in the same block, in the same loop level or1429  /// by guaranteeing that \p CurrentLoc only references a single MemoryLocation1430  /// during execution of the containing function.1431  bool isGuaranteedLoopIndependent(const Instruction *Current,1432                                   const Instruction *KillingDef,1433                                   const MemoryLocation &CurrentLoc) {1434    // If the dependency is within the same block or loop level (being careful1435    // of irreducible loops), we know that AA will return a valid result for the1436    // memory dependency. (Both at the function level, outside of any loop,1437    // would also be valid but we currently disable that to limit compile time).1438    if (Current->getParent() == KillingDef->getParent())1439      return true;1440    const Loop *CurrentLI = LI.getLoopFor(Current->getParent());1441    if (!ContainsIrreducibleLoops && CurrentLI &&1442        CurrentLI == LI.getLoopFor(KillingDef->getParent()))1443      return true;1444    // Otherwise check the memory location is invariant to any loops.1445    return isGuaranteedLoopInvariant(CurrentLoc.Ptr);1446  }1447 1448  /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible1449  /// loop. In particular, this guarantees that it only references a single1450  /// MemoryLocation during execution of the containing function.1451  bool isGuaranteedLoopInvariant(const Value *Ptr) {1452    Ptr = Ptr->stripPointerCasts();1453    if (auto *GEP = dyn_cast<GEPOperator>(Ptr))1454      if (GEP->hasAllConstantIndices())1455        Ptr = GEP->getPointerOperand()->stripPointerCasts();1456 1457    if (auto *I = dyn_cast<Instruction>(Ptr)) {1458      return I->getParent()->isEntryBlock() ||1459             (!ContainsIrreducibleLoops && !LI.getLoopFor(I->getParent()));1460    }1461    return true;1462  }1463 1464  // Find a MemoryDef writing to \p KillingLoc and dominating \p StartAccess,1465  // with no read access between them or on any other path to a function exit1466  // block if \p KillingLoc is not accessible after the function returns. If1467  // there is no such MemoryDef, return std::nullopt. The returned value may not1468  // (completely) overwrite \p KillingLoc. Currently we bail out when we1469  // encounter an aliasing MemoryUse (read).1470  std::optional<MemoryAccess *>1471  getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,1472                  const MemoryLocation &KillingLoc, const Value *KillingUndObj,1473                  unsigned &ScanLimit, unsigned &WalkerStepLimit,1474                  bool IsMemTerm, unsigned &PartialLimit,1475                  bool IsInitializesAttrMemLoc) {1476    if (ScanLimit == 0 || WalkerStepLimit == 0) {1477      LLVM_DEBUG(dbgs() << "\n    ...  hit scan limit\n");1478      return std::nullopt;1479    }1480 1481    MemoryAccess *Current = StartAccess;1482    Instruction *KillingI = KillingDef->getMemoryInst();1483    LLVM_DEBUG(dbgs() << "  trying to get dominating access\n");1484 1485    // Only optimize defining access of KillingDef when directly starting at its1486    // defining access. The defining access also must only access KillingLoc. At1487    // the moment we only support instructions with a single write location, so1488    // it should be sufficient to disable optimizations for instructions that1489    // also read from memory.1490    bool CanOptimize = OptimizeMemorySSA &&1491                       KillingDef->getDefiningAccess() == StartAccess &&1492                       !KillingI->mayReadFromMemory();1493 1494    // Find the next clobbering Mod access for DefLoc, starting at StartAccess.1495    std::optional<MemoryLocation> CurrentLoc;1496    for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {1497      LLVM_DEBUG({1498        dbgs() << "   visiting " << *Current;1499        if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef>(Current))1500          dbgs() << " (" << *cast<MemoryUseOrDef>(Current)->getMemoryInst()1501                 << ")";1502        dbgs() << "\n";1503      });1504 1505      // Reached TOP.1506      if (MSSA.isLiveOnEntryDef(Current)) {1507        LLVM_DEBUG(dbgs() << "   ...  found LiveOnEntryDef\n");1508        if (CanOptimize && Current != KillingDef->getDefiningAccess())1509          // The first clobbering def is... none.1510          KillingDef->setOptimized(Current);1511        return std::nullopt;1512      }1513 1514      // Cost of a step. Accesses in the same block are more likely to be valid1515      // candidates for elimination, hence consider them cheaper.1516      unsigned StepCost = KillingDef->getBlock() == Current->getBlock()1517                              ? MemorySSASameBBStepCost1518                              : MemorySSAOtherBBStepCost;1519      if (WalkerStepLimit <= StepCost) {1520        LLVM_DEBUG(dbgs() << "   ...  hit walker step limit\n");1521        return std::nullopt;1522      }1523      WalkerStepLimit -= StepCost;1524 1525      // Return for MemoryPhis. They cannot be eliminated directly and the1526      // caller is responsible for traversing them.1527      if (isa<MemoryPhi>(Current)) {1528        LLVM_DEBUG(dbgs() << "   ...  found MemoryPhi\n");1529        return Current;1530      }1531 1532      // Below, check if CurrentDef is a valid candidate to be eliminated by1533      // KillingDef. If it is not, check the next candidate.1534      MemoryDef *CurrentDef = cast<MemoryDef>(Current);1535      Instruction *CurrentI = CurrentDef->getMemoryInst();1536 1537      if (canSkipDef(CurrentDef, !isInvisibleToCallerOnUnwind(KillingUndObj))) {1538        CanOptimize = false;1539        continue;1540      }1541 1542      // Before we try to remove anything, check for any extra throwing1543      // instructions that block us from DSEing1544      if (mayThrowBetween(KillingI, CurrentI, KillingUndObj)) {1545        LLVM_DEBUG(dbgs() << "  ... skip, may throw!\n");1546        return std::nullopt;1547      }1548 1549      // Check for anything that looks like it will be a barrier to further1550      // removal1551      if (isDSEBarrier(KillingUndObj, CurrentI)) {1552        LLVM_DEBUG(dbgs() << "  ... skip, barrier\n");1553        return std::nullopt;1554      }1555 1556      // If Current is known to be on path that reads DefLoc or is a read1557      // clobber, bail out, as the path is not profitable. We skip this check1558      // for intrinsic calls, because the code knows how to handle memcpy1559      // intrinsics.1560      if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(KillingLoc, CurrentI))1561        return std::nullopt;1562 1563      // Quick check if there are direct uses that are read-clobbers.1564      if (any_of(Current->uses(), [this, &KillingLoc, StartAccess](Use &U) {1565            if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))1566              return !MSSA.dominates(StartAccess, UseOrDef) &&1567                     isReadClobber(KillingLoc, UseOrDef->getMemoryInst());1568            return false;1569          })) {1570        LLVM_DEBUG(dbgs() << "   ...  found a read clobber\n");1571        return std::nullopt;1572      }1573 1574      // If Current does not have an analyzable write location or is not1575      // removable, skip it.1576      CurrentLoc = getLocForWrite(CurrentI);1577      if (!CurrentLoc || !isRemovable(CurrentI)) {1578        CanOptimize = false;1579        continue;1580      }1581 1582      // AliasAnalysis does not account for loops. Limit elimination to1583      // candidates for which we can guarantee they always store to the same1584      // memory location and not located in different loops.1585      if (!isGuaranteedLoopIndependent(CurrentI, KillingI, *CurrentLoc)) {1586        LLVM_DEBUG(dbgs() << "  ... not guaranteed loop independent\n");1587        CanOptimize = false;1588        continue;1589      }1590 1591      if (IsMemTerm) {1592        // If the killing def is a memory terminator (e.g. lifetime.end), check1593        // the next candidate if the current Current does not write the same1594        // underlying object as the terminator.1595        if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {1596          CanOptimize = false;1597          continue;1598        }1599      } else {1600        int64_t KillingOffset = 0;1601        int64_t DeadOffset = 0;1602        auto OR = isOverwrite(KillingI, CurrentI, KillingLoc, *CurrentLoc,1603                              KillingOffset, DeadOffset);1604        if (CanOptimize) {1605          // CurrentDef is the earliest write clobber of KillingDef. Use it as1606          // optimized access. Do not optimize if CurrentDef is already the1607          // defining access of KillingDef.1608          if (CurrentDef != KillingDef->getDefiningAccess() &&1609              (OR == OW_Complete || OR == OW_MaybePartial))1610            KillingDef->setOptimized(CurrentDef);1611 1612          // Once a may-aliasing def is encountered do not set an optimized1613          // access.1614          if (OR != OW_None)1615            CanOptimize = false;1616        }1617 1618        // If Current does not write to the same object as KillingDef, check1619        // the next candidate.1620        if (OR == OW_Unknown || OR == OW_None)1621          continue;1622        else if (OR == OW_MaybePartial) {1623          // If KillingDef only partially overwrites Current, check the next1624          // candidate if the partial step limit is exceeded. This aggressively1625          // limits the number of candidates for partial store elimination,1626          // which are less likely to be removable in the end.1627          if (PartialLimit <= 1) {1628            WalkerStepLimit -= 1;1629            LLVM_DEBUG(dbgs() << "   ... reached partial limit ... continue with next access\n");1630            continue;1631          }1632          PartialLimit -= 1;1633        }1634      }1635      break;1636    };1637 1638    // Accesses to objects accessible after the function returns can only be1639    // eliminated if the access is dead along all paths to the exit. Collect1640    // the blocks with killing (=completely overwriting MemoryDefs) and check if1641    // they cover all paths from MaybeDeadAccess to any function exit.1642    SmallPtrSet<Instruction *, 16> KillingDefs;1643    KillingDefs.insert(KillingDef->getMemoryInst());1644    MemoryAccess *MaybeDeadAccess = Current;1645    MemoryLocation MaybeDeadLoc = *CurrentLoc;1646    Instruction *MaybeDeadI = cast<MemoryDef>(MaybeDeadAccess)->getMemoryInst();1647    LLVM_DEBUG(dbgs() << "  Checking for reads of " << *MaybeDeadAccess << " ("1648                      << *MaybeDeadI << ")\n");1649 1650    SmallVector<MemoryAccess *, 32> WorkList;1651    SmallPtrSet<MemoryAccess *, 32> Visited;1652    pushMemUses(MaybeDeadAccess, WorkList, Visited);1653 1654    // Check if DeadDef may be read.1655    for (unsigned I = 0; I < WorkList.size(); I++) {1656      MemoryAccess *UseAccess = WorkList[I];1657 1658      LLVM_DEBUG(dbgs() << "   " << *UseAccess);1659      // Bail out if the number of accesses to check exceeds the scan limit.1660      if (ScanLimit < (WorkList.size() - I)) {1661        LLVM_DEBUG(dbgs() << "\n    ...  hit scan limit\n");1662        return std::nullopt;1663      }1664      --ScanLimit;1665      NumDomMemDefChecks++;1666 1667      if (isa<MemoryPhi>(UseAccess)) {1668        if (any_of(KillingDefs, [this, UseAccess](Instruction *KI) {1669              return DT.properlyDominates(KI->getParent(),1670                                          UseAccess->getBlock());1671            })) {1672          LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing block\n");1673          continue;1674        }1675        LLVM_DEBUG(dbgs() << "\n    ... adding PHI uses\n");1676        pushMemUses(UseAccess, WorkList, Visited);1677        continue;1678      }1679 1680      Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();1681      LLVM_DEBUG(dbgs() << " (" << *UseInst << ")\n");1682 1683      if (any_of(KillingDefs, [this, UseInst](Instruction *KI) {1684            return DT.dominates(KI, UseInst);1685          })) {1686        LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing def\n");1687        continue;1688      }1689 1690      // A memory terminator kills all preceeding MemoryDefs and all succeeding1691      // MemoryAccesses. We do not have to check it's users.1692      if (isMemTerminator(MaybeDeadLoc, MaybeDeadI, UseInst)) {1693        LLVM_DEBUG(1694            dbgs()1695            << " ... skipping, memterminator invalidates following accesses\n");1696        continue;1697      }1698 1699      if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {1700        LLVM_DEBUG(dbgs() << "    ... adding uses of intrinsic\n");1701        pushMemUses(UseAccess, WorkList, Visited);1702        continue;1703      }1704 1705      if (UseInst->mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj)) {1706        LLVM_DEBUG(dbgs() << "  ... found throwing instruction\n");1707        return std::nullopt;1708      }1709 1710      // Uses which may read the original MemoryDef mean we cannot eliminate the1711      // original MD. Stop walk.1712      // If KillingDef is a CallInst with "initializes" attribute, the reads in1713      // the callee would be dominated by initializations, so it should be safe.1714      bool IsKillingDefFromInitAttr = false;1715      if (IsInitializesAttrMemLoc) {1716        if (KillingI == UseInst &&1717            KillingUndObj == getUnderlyingObject(MaybeDeadLoc.Ptr))1718          IsKillingDefFromInitAttr = true;1719      }1720 1721      if (isReadClobber(MaybeDeadLoc, UseInst) && !IsKillingDefFromInitAttr) {1722        LLVM_DEBUG(dbgs() << "    ... found read clobber\n");1723        return std::nullopt;1724      }1725 1726      // If this worklist walks back to the original memory access (and the1727      // pointer is not guarenteed loop invariant) then we cannot assume that a1728      // store kills itself.1729      if (MaybeDeadAccess == UseAccess &&1730          !isGuaranteedLoopInvariant(MaybeDeadLoc.Ptr)) {1731        LLVM_DEBUG(dbgs() << "    ... found not loop invariant self access\n");1732        return std::nullopt;1733      }1734      // Otherwise, for the KillingDef and MaybeDeadAccess we only have to check1735      // if it reads the memory location.1736      // TODO: It would probably be better to check for self-reads before1737      // calling the function.1738      if (KillingDef == UseAccess || MaybeDeadAccess == UseAccess) {1739        LLVM_DEBUG(dbgs() << "    ... skipping killing def/dom access\n");1740        continue;1741      }1742 1743      // Check all uses for MemoryDefs, except for defs completely overwriting1744      // the original location. Otherwise we have to check uses of *all*1745      // MemoryDefs we discover, including non-aliasing ones. Otherwise we might1746      // miss cases like the following1747      //   1 = Def(LoE) ; <----- DeadDef stores [0,1]1748      //   2 = Def(1)   ; (2, 1) = NoAlias,   stores [2,3]1749      //   Use(2)       ; MayAlias 2 *and* 1, loads [0, 3].1750      //                  (The Use points to the *first* Def it may alias)1751      //   3 = Def(1)   ; <---- Current  (3, 2) = NoAlias, (3,1) = MayAlias,1752      //                  stores [0,1]1753      if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {1754        if (isCompleteOverwrite(MaybeDeadLoc, MaybeDeadI, UseInst)) {1755          BasicBlock *MaybeKillingBlock = UseInst->getParent();1756          if (PostOrderNumbers.find(MaybeKillingBlock)->second <1757              PostOrderNumbers.find(MaybeDeadAccess->getBlock())->second) {1758            if (!isInvisibleToCallerAfterRet(KillingUndObj)) {1759              LLVM_DEBUG(dbgs()1760                         << "    ... found killing def " << *UseInst << "\n");1761              KillingDefs.insert(UseInst);1762            }1763          } else {1764            LLVM_DEBUG(dbgs()1765                       << "    ... found preceeding def " << *UseInst << "\n");1766            return std::nullopt;1767          }1768        } else1769          pushMemUses(UseDef, WorkList, Visited);1770      }1771    }1772 1773    // For accesses to locations visible after the function returns, make sure1774    // that the location is dead (=overwritten) along all paths from1775    // MaybeDeadAccess to the exit.1776    if (!isInvisibleToCallerAfterRet(KillingUndObj)) {1777      SmallPtrSet<BasicBlock *, 16> KillingBlocks;1778      for (Instruction *KD : KillingDefs)1779        KillingBlocks.insert(KD->getParent());1780      assert(!KillingBlocks.empty() &&1781             "Expected at least a single killing block");1782 1783      // Find the common post-dominator of all killing blocks.1784      BasicBlock *CommonPred = *KillingBlocks.begin();1785      for (BasicBlock *BB : llvm::drop_begin(KillingBlocks)) {1786        if (!CommonPred)1787          break;1788        CommonPred = PDT.findNearestCommonDominator(CommonPred, BB);1789      }1790 1791      // If the common post-dominator does not post-dominate MaybeDeadAccess,1792      // there is a path from MaybeDeadAccess to an exit not going through a1793      // killing block.1794      if (!PDT.dominates(CommonPred, MaybeDeadAccess->getBlock())) {1795        if (!AnyUnreachableExit)1796          return std::nullopt;1797 1798        // Fall back to CFG scan starting at all non-unreachable roots if not1799        // all paths to the exit go through CommonPred.1800        CommonPred = nullptr;1801      }1802 1803      // If CommonPred itself is in the set of killing blocks, we're done.1804      if (KillingBlocks.count(CommonPred))1805        return {MaybeDeadAccess};1806 1807      SetVector<BasicBlock *> WorkList;1808      // If CommonPred is null, there are multiple exits from the function.1809      // They all have to be added to the worklist.1810      if (CommonPred)1811        WorkList.insert(CommonPred);1812      else1813        for (BasicBlock *R : PDT.roots()) {1814          if (!isa<UnreachableInst>(R->getTerminator()))1815            WorkList.insert(R);1816        }1817 1818      NumCFGTries++;1819      // Check if all paths starting from an exit node go through one of the1820      // killing blocks before reaching MaybeDeadAccess.1821      for (unsigned I = 0; I < WorkList.size(); I++) {1822        NumCFGChecks++;1823        BasicBlock *Current = WorkList[I];1824        if (KillingBlocks.count(Current))1825          continue;1826        if (Current == MaybeDeadAccess->getBlock())1827          return std::nullopt;1828 1829        // MaybeDeadAccess is reachable from the entry, so we don't have to1830        // explore unreachable blocks further.1831        if (!DT.isReachableFromEntry(Current))1832          continue;1833 1834        WorkList.insert_range(predecessors(Current));1835 1836        if (WorkList.size() >= MemorySSAPathCheckLimit)1837          return std::nullopt;1838      }1839      NumCFGSuccess++;1840    }1841 1842    // No aliasing MemoryUses of MaybeDeadAccess found, MaybeDeadAccess is1843    // potentially dead.1844    return {MaybeDeadAccess};1845  }1846 1847  /// Delete dead memory defs and recursively add their operands to ToRemove if1848  /// they became dead.1849  void1850  deleteDeadInstruction(Instruction *SI,1851                        SmallPtrSetImpl<MemoryAccess *> *Deleted = nullptr) {1852    MemorySSAUpdater Updater(&MSSA);1853    SmallVector<Instruction *, 32> NowDeadInsts;1854    NowDeadInsts.push_back(SI);1855    --NumFastOther;1856 1857    while (!NowDeadInsts.empty()) {1858      Instruction *DeadInst = NowDeadInsts.pop_back_val();1859      ++NumFastOther;1860 1861      // Try to preserve debug information attached to the dead instruction.1862      salvageDebugInfo(*DeadInst);1863      salvageKnowledge(DeadInst);1864 1865      // Remove the Instruction from MSSA.1866      MemoryAccess *MA = MSSA.getMemoryAccess(DeadInst);1867      bool IsMemDef = MA && isa<MemoryDef>(MA);1868      if (MA) {1869        if (IsMemDef) {1870          auto *MD = cast<MemoryDef>(MA);1871          SkipStores.insert(MD);1872          if (Deleted)1873            Deleted->insert(MD);1874          if (auto *SI = dyn_cast<StoreInst>(MD->getMemoryInst())) {1875            if (SI->getValueOperand()->getType()->isPointerTy()) {1876              const Value *UO = getUnderlyingObject(SI->getValueOperand());1877              if (CapturedBeforeReturn.erase(UO))1878                ShouldIterateEndOfFunctionDSE = true;1879              InvisibleToCallerAfterRet.erase(UO);1880            }1881          }1882        }1883 1884        Updater.removeMemoryAccess(MA);1885      }1886 1887      auto I = IOLs.find(DeadInst->getParent());1888      if (I != IOLs.end())1889        I->second.erase(DeadInst);1890      // Remove its operands1891      for (Use &O : DeadInst->operands())1892        if (Instruction *OpI = dyn_cast<Instruction>(O)) {1893          O.set(PoisonValue::get(O->getType()));1894          if (isInstructionTriviallyDead(OpI, &TLI))1895            NowDeadInsts.push_back(OpI);1896        }1897 1898      EA.removeInstruction(DeadInst);1899      // Remove memory defs directly if they don't produce results, but only1900      // queue other dead instructions for later removal. They may have been1901      // used as memory locations that have been cached by BatchAA. Removing1902      // them here may lead to newly created instructions to be allocated at the1903      // same address, yielding stale cache entries.1904      if (IsMemDef && DeadInst->getType()->isVoidTy())1905        DeadInst->eraseFromParent();1906      else1907        ToRemove.push_back(DeadInst);1908    }1909  }1910 1911  // Check for any extra throws between \p KillingI and \p DeadI that block1912  // DSE.  This only checks extra maythrows (those that aren't MemoryDef's).1913  // MemoryDef that may throw are handled during the walk from one def to the1914  // next.1915  bool mayThrowBetween(Instruction *KillingI, Instruction *DeadI,1916                       const Value *KillingUndObj) {1917    // First see if we can ignore it by using the fact that KillingI is an1918    // alloca/alloca like object that is not visible to the caller during1919    // execution of the function.1920    if (KillingUndObj && isInvisibleToCallerOnUnwind(KillingUndObj))1921      return false;1922 1923    if (KillingI->getParent() == DeadI->getParent())1924      return ThrowingBlocks.count(KillingI->getParent());1925    return !ThrowingBlocks.empty();1926  }1927 1928  // Check if \p DeadI acts as a DSE barrier for \p KillingI. The following1929  // instructions act as barriers:1930  //  * A memory instruction that may throw and \p KillingI accesses a non-stack1931  //  object.1932  //  * Atomic stores stronger that monotonic.1933  bool isDSEBarrier(const Value *KillingUndObj, Instruction *DeadI) {1934    // If DeadI may throw it acts as a barrier, unless we are to an1935    // alloca/alloca like object that does not escape.1936    if (DeadI->mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj))1937      return true;1938 1939    // If DeadI is an atomic load/store stronger than monotonic, do not try to1940    // eliminate/reorder it.1941    if (DeadI->isAtomic()) {1942      if (auto *LI = dyn_cast<LoadInst>(DeadI))1943        return isStrongerThanMonotonic(LI->getOrdering());1944      if (auto *SI = dyn_cast<StoreInst>(DeadI))1945        return isStrongerThanMonotonic(SI->getOrdering());1946      if (auto *ARMW = dyn_cast<AtomicRMWInst>(DeadI))1947        return isStrongerThanMonotonic(ARMW->getOrdering());1948      if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(DeadI))1949        return isStrongerThanMonotonic(CmpXchg->getSuccessOrdering()) ||1950               isStrongerThanMonotonic(CmpXchg->getFailureOrdering());1951      llvm_unreachable("other instructions should be skipped in MemorySSA");1952    }1953    return false;1954  }1955 1956  /// Eliminate writes to objects that are not visible in the caller and are not1957  /// accessed before returning from the function.1958  bool eliminateDeadWritesAtEndOfFunction() {1959    bool MadeChange = false;1960    LLVM_DEBUG(1961        dbgs()1962        << "Trying to eliminate MemoryDefs at the end of the function\n");1963    do {1964      ShouldIterateEndOfFunctionDSE = false;1965      for (MemoryDef *Def : llvm::reverse(MemDefs)) {1966        if (SkipStores.contains(Def))1967          continue;1968 1969        Instruction *DefI = Def->getMemoryInst();1970        auto DefLoc = getLocForWrite(DefI);1971        if (!DefLoc || !isRemovable(DefI)) {1972          LLVM_DEBUG(dbgs() << "  ... could not get location for write or "1973                               "instruction not removable.\n");1974          continue;1975        }1976 1977        // NOTE: Currently eliminating writes at the end of a function is1978        // limited to MemoryDefs with a single underlying object, to save1979        // compile-time. In practice it appears the case with multiple1980        // underlying objects is very uncommon. If it turns out to be important,1981        // we can use getUnderlyingObjects here instead.1982        const Value *UO = getUnderlyingObject(DefLoc->Ptr);1983        if (!isInvisibleToCallerAfterRet(UO))1984          continue;1985 1986        if (isWriteAtEndOfFunction(Def, *DefLoc)) {1987          // See through pointer-to-pointer bitcasts1988          LLVM_DEBUG(dbgs() << "   ... MemoryDef is not accessed until the end "1989                               "of the function\n");1990          deleteDeadInstruction(DefI);1991          ++NumFastStores;1992          MadeChange = true;1993        }1994      }1995    } while (ShouldIterateEndOfFunctionDSE);1996    return MadeChange;1997  }1998 1999  /// If we have a zero initializing memset following a call to malloc,2000  /// try folding it into a call to calloc.2001  bool tryFoldIntoCalloc(MemoryDef *Def, const Value *DefUO) {2002    Instruction *DefI = Def->getMemoryInst();2003    MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);2004    if (!MemSet)2005      // TODO: Could handle zero store to small allocation as well.2006      return false;2007    Constant *StoredConstant = dyn_cast<Constant>(MemSet->getValue());2008    if (!StoredConstant || !StoredConstant->isNullValue())2009      return false;2010 2011    if (!isRemovable(DefI))2012      // The memset might be volatile..2013      return false;2014 2015    if (F.hasFnAttribute(Attribute::SanitizeMemory) ||2016        F.hasFnAttribute(Attribute::SanitizeAddress) ||2017        F.hasFnAttribute(Attribute::SanitizeHWAddress) ||2018        F.getName() == "calloc")2019      return false;2020    auto *Malloc = const_cast<CallInst *>(dyn_cast<CallInst>(DefUO));2021    if (!Malloc)2022      return false;2023    auto *InnerCallee = Malloc->getCalledFunction();2024    if (!InnerCallee)2025      return false;2026    LibFunc Func = NotLibFunc;2027    StringRef ZeroedVariantName;2028    if (!TLI.getLibFunc(*InnerCallee, Func) || !TLI.has(Func) ||2029        Func != LibFunc_malloc) {2030      Attribute Attr = Malloc->getFnAttr("alloc-variant-zeroed");2031      if (!Attr.isValid())2032        return false;2033      ZeroedVariantName = Attr.getValueAsString();2034      if (ZeroedVariantName.empty())2035        return false;2036    }2037 2038    // Gracefully handle malloc with unexpected memory attributes.2039    auto *MallocDef = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(Malloc));2040    if (!MallocDef)2041      return false;2042 2043    auto shouldCreateCalloc = [](CallInst *Malloc, CallInst *Memset) {2044      // Check for br(icmp ptr, null), truebb, falsebb) pattern at the end2045      // of malloc block2046      auto *MallocBB = Malloc->getParent(),2047        *MemsetBB = Memset->getParent();2048      if (MallocBB == MemsetBB)2049        return true;2050      auto *Ptr = Memset->getArgOperand(0);2051      auto *TI = MallocBB->getTerminator();2052      BasicBlock *TrueBB, *FalseBB;2053      if (!match(TI, m_Br(m_SpecificICmp(ICmpInst::ICMP_EQ, m_Specific(Ptr),2054                                         m_Zero()),2055                          TrueBB, FalseBB)))2056        return false;2057      if (MemsetBB != FalseBB)2058        return false;2059      return true;2060    };2061 2062    if (Malloc->getOperand(0) != MemSet->getLength())2063      return false;2064    if (!shouldCreateCalloc(Malloc, MemSet) || !DT.dominates(Malloc, MemSet) ||2065        !memoryIsNotModifiedBetween(Malloc, MemSet, BatchAA, DL, &DT))2066      return false;2067    IRBuilder<> IRB(Malloc);2068    assert(Func == LibFunc_malloc || !ZeroedVariantName.empty());2069    Value *Calloc = nullptr;2070    if (!ZeroedVariantName.empty()) {2071      LLVMContext &Ctx = Malloc->getContext();2072      AttributeList Attrs = InnerCallee->getAttributes();2073      AllocFnKind AllocKind =2074          Attrs.getFnAttr(Attribute::AllocKind).getAllocKind() |2075          AllocFnKind::Zeroed;2076      AllocKind &= ~AllocFnKind::Uninitialized;2077      Attrs =2078          Attrs.addFnAttribute(Ctx, Attribute::getWithAllocKind(Ctx, AllocKind))2079              .removeFnAttribute(Ctx, "alloc-variant-zeroed");2080      FunctionCallee ZeroedVariant = Malloc->getModule()->getOrInsertFunction(2081          ZeroedVariantName, InnerCallee->getFunctionType(), Attrs);2082      SmallVector<Value *, 3> Args;2083      Args.append(Malloc->arg_begin(), Malloc->arg_end());2084      Calloc = IRB.CreateCall(ZeroedVariant, Args, ZeroedVariantName);2085    } else {2086      Type *SizeTTy = Malloc->getArgOperand(0)->getType();2087      Calloc =2088          emitCalloc(ConstantInt::get(SizeTTy, 1), Malloc->getArgOperand(0),2089                     IRB, TLI, Malloc->getType()->getPointerAddressSpace());2090    }2091    if (!Calloc)2092      return false;2093 2094    MemorySSAUpdater Updater(&MSSA);2095    auto *NewAccess =2096      Updater.createMemoryAccessAfter(cast<Instruction>(Calloc), nullptr,2097                                      MallocDef);2098    auto *NewAccessMD = cast<MemoryDef>(NewAccess);2099    Updater.insertDef(NewAccessMD, /*RenameUses=*/true);2100    Malloc->replaceAllUsesWith(Calloc);2101    deleteDeadInstruction(Malloc);2102    return true;2103  }2104 2105  // Check if there is a dominating condition, that implies that the value2106  // being stored in a ptr is already present in the ptr.2107  bool dominatingConditionImpliesValue(MemoryDef *Def) {2108    auto *StoreI = cast<StoreInst>(Def->getMemoryInst());2109    BasicBlock *StoreBB = StoreI->getParent();2110    Value *StorePtr = StoreI->getPointerOperand();2111    Value *StoreVal = StoreI->getValueOperand();2112 2113    DomTreeNode *IDom = DT.getNode(StoreBB)->getIDom();2114    if (!IDom)2115      return false;2116 2117    auto *BI = dyn_cast<BranchInst>(IDom->getBlock()->getTerminator());2118    if (!BI || !BI->isConditional())2119      return false;2120 2121    // In case both blocks are the same, it is not possible to determine2122    // if optimization is possible. (We would not want to optimize a store2123    // in the FalseBB if condition is true and vice versa.)2124    if (BI->getSuccessor(0) == BI->getSuccessor(1))2125      return false;2126 2127    Instruction *ICmpL;2128    CmpPredicate Pred;2129    if (!match(BI->getCondition(),2130               m_c_ICmp(Pred,2131                        m_CombineAnd(m_Load(m_Specific(StorePtr)),2132                                     m_Instruction(ICmpL)),2133                        m_Specific(StoreVal))) ||2134        !ICmpInst::isEquality(Pred))2135      return false;2136 2137    // In case the else blocks also branches to the if block or the other way2138    // around it is not possible to determine if the optimization is possible.2139    if (Pred == ICmpInst::ICMP_EQ &&2140        !DT.dominates(BasicBlockEdge(BI->getParent(), BI->getSuccessor(0)),2141                      StoreBB))2142      return false;2143 2144    if (Pred == ICmpInst::ICMP_NE &&2145        !DT.dominates(BasicBlockEdge(BI->getParent(), BI->getSuccessor(1)),2146                      StoreBB))2147      return false;2148 2149    MemoryAccess *LoadAcc = MSSA.getMemoryAccess(ICmpL);2150    MemoryAccess *ClobAcc =2151        MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def, BatchAA);2152 2153    return MSSA.dominates(ClobAcc, LoadAcc);2154  }2155 2156  /// \returns true if \p Def is a no-op store, either because it2157  /// directly stores back a loaded value or stores zero to a calloced object.2158  bool storeIsNoop(MemoryDef *Def, const Value *DefUO) {2159    Instruction *DefI = Def->getMemoryInst();2160    StoreInst *Store = dyn_cast<StoreInst>(DefI);2161    MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);2162    Constant *StoredConstant = nullptr;2163    if (Store)2164      StoredConstant = dyn_cast<Constant>(Store->getOperand(0));2165    else if (MemSet)2166      StoredConstant = dyn_cast<Constant>(MemSet->getValue());2167    else2168      return false;2169 2170    if (!isRemovable(DefI))2171      return false;2172 2173    if (StoredConstant) {2174      Constant *InitC =2175          getInitialValueOfAllocation(DefUO, &TLI, StoredConstant->getType());2176      // If the clobbering access is LiveOnEntry, no instructions between them2177      // can modify the memory location.2178      if (InitC && InitC == StoredConstant)2179        return MSSA.isLiveOnEntryDef(2180            MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def, BatchAA));2181    }2182 2183    if (!Store)2184      return false;2185 2186    if (dominatingConditionImpliesValue(Def))2187      return true;2188 2189    if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {2190      if (LoadI->getPointerOperand() == Store->getOperand(1)) {2191        // Get the defining access for the load.2192        auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess();2193        // Fast path: the defining accesses are the same.2194        if (LoadAccess == Def->getDefiningAccess())2195          return true;2196 2197        // Look through phi accesses. Recursively scan all phi accesses by2198        // adding them to a worklist. Bail when we run into a memory def that2199        // does not match LoadAccess.2200        SetVector<MemoryAccess *> ToCheck;2201        MemoryAccess *Current =2202            MSSA.getWalker()->getClobberingMemoryAccess(Def, BatchAA);2203        // We don't want to bail when we run into the store memory def. But,2204        // the phi access may point to it. So, pretend like we've already2205        // checked it.2206        ToCheck.insert(Def);2207        ToCheck.insert(Current);2208        // Start at current (1) to simulate already having checked Def.2209        for (unsigned I = 1; I < ToCheck.size(); ++I) {2210          Current = ToCheck[I];2211          if (auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {2212            // Check all the operands.2213            for (auto &Use : PhiAccess->incoming_values())2214              ToCheck.insert(cast<MemoryAccess>(&Use));2215            continue;2216          }2217 2218          // If we found a memory def, bail. This happens when we have an2219          // unrelated write in between an otherwise noop store.2220          assert(isa<MemoryDef>(Current) &&2221                 "Only MemoryDefs should reach here.");2222          // TODO: Skip no alias MemoryDefs that have no aliasing reads.2223          // We are searching for the definition of the store's destination.2224          // So, if that is the same definition as the load, then this is a2225          // noop. Otherwise, fail.2226          if (LoadAccess != Current)2227            return false;2228        }2229        return true;2230      }2231    }2232 2233    return false;2234  }2235 2236  bool removePartiallyOverlappedStores(InstOverlapIntervalsTy &IOL) {2237    bool Changed = false;2238    for (auto OI : IOL) {2239      Instruction *DeadI = OI.first;2240      MemoryLocation Loc = *getLocForWrite(DeadI);2241      assert(isRemovable(DeadI) && "Expect only removable instruction");2242 2243      const Value *Ptr = Loc.Ptr->stripPointerCasts();2244      int64_t DeadStart = 0;2245      uint64_t DeadSize = Loc.Size.getValue();2246      GetPointerBaseWithConstantOffset(Ptr, DeadStart, DL);2247      OverlapIntervalsTy &IntervalMap = OI.second;2248      Changed |= tryToShortenEnd(DeadI, IntervalMap, DeadStart, DeadSize);2249      if (IntervalMap.empty())2250        continue;2251      Changed |= tryToShortenBegin(DeadI, IntervalMap, DeadStart, DeadSize);2252    }2253    return Changed;2254  }2255 2256  /// Eliminates writes to locations where the value that is being written2257  /// is already stored at the same location.2258  bool eliminateRedundantStoresOfExistingValues() {2259    bool MadeChange = false;2260    LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs that write the "2261                         "already existing value\n");2262    for (auto *Def : MemDefs) {2263      if (SkipStores.contains(Def) || MSSA.isLiveOnEntryDef(Def))2264        continue;2265 2266      Instruction *DefInst = Def->getMemoryInst();2267      auto MaybeDefLoc = getLocForWrite(DefInst);2268      if (!MaybeDefLoc || !isRemovable(DefInst))2269        continue;2270 2271      MemoryDef *UpperDef;2272      // To conserve compile-time, we avoid walking to the next clobbering def.2273      // Instead, we just try to get the optimized access, if it exists. DSE2274      // will try to optimize defs during the earlier traversal.2275      if (Def->isOptimized())2276        UpperDef = dyn_cast<MemoryDef>(Def->getOptimized());2277      else2278        UpperDef = dyn_cast<MemoryDef>(Def->getDefiningAccess());2279      if (!UpperDef || MSSA.isLiveOnEntryDef(UpperDef))2280        continue;2281 2282      Instruction *UpperInst = UpperDef->getMemoryInst();2283      auto IsRedundantStore = [&]() {2284        // We don't care about differences in call attributes here.2285        if (DefInst->isIdenticalToWhenDefined(UpperInst,2286                                              /*IntersectAttrs=*/true))2287          return true;2288        if (auto *MemSetI = dyn_cast<MemSetInst>(UpperInst)) {2289          if (auto *SI = dyn_cast<StoreInst>(DefInst)) {2290            // MemSetInst must have a write location.2291            auto UpperLoc = getLocForWrite(UpperInst);2292            if (!UpperLoc)2293              return false;2294            int64_t InstWriteOffset = 0;2295            int64_t DepWriteOffset = 0;2296            auto OR = isOverwrite(UpperInst, DefInst, *UpperLoc, *MaybeDefLoc,2297                                  InstWriteOffset, DepWriteOffset);2298            Value *StoredByte = isBytewiseValue(SI->getValueOperand(), DL);2299            return StoredByte && StoredByte == MemSetI->getOperand(1) &&2300                   OR == OW_Complete;2301          }2302        }2303        return false;2304      };2305 2306      if (!IsRedundantStore() || isReadClobber(*MaybeDefLoc, DefInst))2307        continue;2308      LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n  DEAD: " << *DefInst2309                        << '\n');2310      deleteDeadInstruction(DefInst);2311      NumRedundantStores++;2312      MadeChange = true;2313    }2314    return MadeChange;2315  }2316 2317  // Return the locations written by the initializes attribute.2318  // Note that this function considers:2319  // 1. Unwind edge: use "initializes" attribute only if the callee has2320  //    "nounwind" attribute, or the argument has "dead_on_unwind" attribute,2321  //    or the argument is invisible to caller on unwind. That is, we don't2322  //    perform incorrect DSE on unwind edges in the current function.2323  // 2. Argument alias: for aliasing arguments, the "initializes" attribute is2324  //    the intersected range list of their "initializes" attributes.2325  SmallVector<MemoryLocation, 1> getInitializesArgMemLoc(const Instruction *I);2326 2327  // Try to eliminate dead defs that access `KillingLocWrapper.MemLoc` and are2328  // killed by `KillingLocWrapper.MemDef`. Return whether2329  // any changes were made, and whether `KillingLocWrapper.DefInst` was deleted.2330  std::pair<bool, bool>2331  eliminateDeadDefs(const MemoryLocationWrapper &KillingLocWrapper);2332 2333  // Try to eliminate dead defs killed by `KillingDefWrapper` and return the2334  // change state: whether make any change.2335  bool eliminateDeadDefs(const MemoryDefWrapper &KillingDefWrapper);2336};2337} // namespace2338 2339// Return true if "Arg" is function local and isn't captured before "CB".2340static bool isFuncLocalAndNotCaptured(Value *Arg, const CallBase *CB,2341                                      EarliestEscapeAnalysis &EA) {2342  const Value *UnderlyingObj = getUnderlyingObject(Arg);2343  return isIdentifiedFunctionLocal(UnderlyingObj) &&2344         capturesNothing(2345             EA.getCapturesBefore(UnderlyingObj, CB, /*OrAt*/ true));2346}2347 2348SmallVector<MemoryLocation, 1>2349DSEState::getInitializesArgMemLoc(const Instruction *I) {2350  const CallBase *CB = dyn_cast<CallBase>(I);2351  if (!CB)2352    return {};2353 2354  // Collect aliasing arguments and their initializes ranges.2355  SmallMapVector<Value *, SmallVector<ArgumentInitInfo, 2>, 2> Arguments;2356  for (unsigned Idx = 0, Count = CB->arg_size(); Idx < Count; ++Idx) {2357    Value *CurArg = CB->getArgOperand(Idx);2358    if (!CurArg->getType()->isPointerTy())2359      continue;2360 2361    ConstantRangeList Inits;2362    Attribute InitializesAttr = CB->getParamAttr(Idx, Attribute::Initializes);2363    // initializes on byval arguments refers to the callee copy, not the2364    // original memory the caller passed in.2365    if (InitializesAttr.isValid() && !CB->isByValArgument(Idx))2366      Inits = InitializesAttr.getValueAsConstantRangeList();2367 2368    // Check whether "CurArg" could alias with global variables. We require2369    // either it's function local and isn't captured before or the "CB" only2370    // accesses arg or inaccessible mem.2371    if (!Inits.empty() && !CB->onlyAccessesInaccessibleMemOrArgMem() &&2372        !isFuncLocalAndNotCaptured(CurArg, CB, EA))2373      Inits = ConstantRangeList();2374 2375    // We don't perform incorrect DSE on unwind edges in the current function,2376    // and use the "initializes" attribute to kill dead stores if:2377    // - The call does not throw exceptions, "CB->doesNotThrow()".2378    // - Or the callee parameter has "dead_on_unwind" attribute.2379    // - Or the argument is invisible to caller on unwind, and there are no2380    //   unwind edges from this call in the current function (e.g. `CallInst`).2381    bool IsDeadOrInvisibleOnUnwind =2382        CB->paramHasAttr(Idx, Attribute::DeadOnUnwind) ||2383        (isa<CallInst>(CB) && isInvisibleToCallerOnUnwind(CurArg));2384    ArgumentInitInfo InitInfo{Idx, IsDeadOrInvisibleOnUnwind, Inits};2385    bool FoundAliasing = false;2386    for (auto &[Arg, AliasList] : Arguments) {2387      auto AAR = BatchAA.alias(MemoryLocation::getBeforeOrAfter(Arg),2388                               MemoryLocation::getBeforeOrAfter(CurArg));2389      if (AAR == AliasResult::NoAlias) {2390        continue;2391      } else if (AAR == AliasResult::MustAlias) {2392        FoundAliasing = true;2393        AliasList.push_back(InitInfo);2394      } else {2395        // For PartialAlias and MayAlias, there is an offset or may be an2396        // unknown offset between the arguments and we insert an empty init2397        // range to discard the entire initializes info while intersecting.2398        FoundAliasing = true;2399        AliasList.push_back(ArgumentInitInfo{Idx, IsDeadOrInvisibleOnUnwind,2400                                             ConstantRangeList()});2401      }2402    }2403    if (!FoundAliasing)2404      Arguments[CurArg] = {InitInfo};2405  }2406 2407  SmallVector<MemoryLocation, 1> Locations;2408  for (const auto &[_, Args] : Arguments) {2409    auto IntersectedRanges =2410        getIntersectedInitRangeList(Args, CB->doesNotThrow());2411    if (IntersectedRanges.empty())2412      continue;2413 2414    for (const auto &Arg : Args) {2415      for (const auto &Range : IntersectedRanges) {2416        int64_t Start = Range.getLower().getSExtValue();2417        int64_t End = Range.getUpper().getSExtValue();2418        // For now, we only handle locations starting at offset 0.2419        if (Start == 0)2420          Locations.push_back(MemoryLocation(CB->getArgOperand(Arg.Idx),2421                                             LocationSize::precise(End - Start),2422                                             CB->getAAMetadata()));2423      }2424    }2425  }2426  return Locations;2427}2428 2429std::pair<bool, bool>2430DSEState::eliminateDeadDefs(const MemoryLocationWrapper &KillingLocWrapper) {2431  bool Changed = false;2432  bool DeletedKillingLoc = false;2433  unsigned ScanLimit = MemorySSAScanLimit;2434  unsigned WalkerStepLimit = MemorySSAUpwardsStepLimit;2435  unsigned PartialLimit = MemorySSAPartialStoreLimit;2436  // Worklist of MemoryAccesses that may be killed by2437  // "KillingLocWrapper.MemDef".2438  SmallSetVector<MemoryAccess *, 8> ToCheck;2439  // Track MemoryAccesses that have been deleted in the loop below, so we can2440  // skip them. Don't use SkipStores for this, which may contain reused2441  // MemoryAccess addresses.2442  SmallPtrSet<MemoryAccess *, 8> Deleted;2443  [[maybe_unused]] unsigned OrigNumSkipStores = SkipStores.size();2444  ToCheck.insert(KillingLocWrapper.MemDef->getDefiningAccess());2445 2446  // Check if MemoryAccesses in the worklist are killed by2447  // "KillingLocWrapper.MemDef".2448  for (unsigned I = 0; I < ToCheck.size(); I++) {2449    MemoryAccess *Current = ToCheck[I];2450    if (Deleted.contains(Current))2451      continue;2452    std::optional<MemoryAccess *> MaybeDeadAccess = getDomMemoryDef(2453        KillingLocWrapper.MemDef, Current, KillingLocWrapper.MemLoc,2454        KillingLocWrapper.UnderlyingObject, ScanLimit, WalkerStepLimit,2455        isMemTerminatorInst(KillingLocWrapper.DefInst), PartialLimit,2456        KillingLocWrapper.DefByInitializesAttr);2457 2458    if (!MaybeDeadAccess) {2459      LLVM_DEBUG(dbgs() << "  finished walk\n");2460      continue;2461    }2462    MemoryAccess *DeadAccess = *MaybeDeadAccess;2463    LLVM_DEBUG(dbgs() << " Checking if we can kill " << *DeadAccess);2464    if (isa<MemoryPhi>(DeadAccess)) {2465      LLVM_DEBUG(dbgs() << "\n  ... adding incoming values to worklist\n");2466      for (Value *V : cast<MemoryPhi>(DeadAccess)->incoming_values()) {2467        MemoryAccess *IncomingAccess = cast<MemoryAccess>(V);2468        BasicBlock *IncomingBlock = IncomingAccess->getBlock();2469        BasicBlock *PhiBlock = DeadAccess->getBlock();2470 2471        // We only consider incoming MemoryAccesses that come before the2472        // MemoryPhi. Otherwise we could discover candidates that do not2473        // strictly dominate our starting def.2474        if (PostOrderNumbers[IncomingBlock] > PostOrderNumbers[PhiBlock])2475          ToCheck.insert(IncomingAccess);2476      }2477      continue;2478    }2479    // We cannot apply the initializes attribute to DeadAccess/DeadDef.2480    // It would incorrectly consider a call instruction as redundant store2481    // and remove this call instruction.2482    // TODO: this conflates the existence of a MemoryLocation with being able2483    // to delete the instruction. Fix isRemovable() to consider calls with2484    // side effects that cannot be removed, e.g. calls with the initializes2485    // attribute, and remove getLocForInst(ConsiderInitializesAttr = false).2486    MemoryDefWrapper DeadDefWrapper(2487        cast<MemoryDef>(DeadAccess),2488        getLocForInst(cast<MemoryDef>(DeadAccess)->getMemoryInst(),2489                      /*ConsiderInitializesAttr=*/false));2490    assert(DeadDefWrapper.DefinedLocations.size() == 1);2491    MemoryLocationWrapper &DeadLocWrapper =2492        DeadDefWrapper.DefinedLocations.front();2493    LLVM_DEBUG(dbgs() << " (" << *DeadLocWrapper.DefInst << ")\n");2494    ToCheck.insert(DeadLocWrapper.MemDef->getDefiningAccess());2495    NumGetDomMemoryDefPassed++;2496 2497    if (!DebugCounter::shouldExecute(MemorySSACounter))2498      continue;2499    if (isMemTerminatorInst(KillingLocWrapper.DefInst)) {2500      if (KillingLocWrapper.UnderlyingObject != DeadLocWrapper.UnderlyingObject)2501        continue;2502      LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: "2503                        << *DeadLocWrapper.DefInst << "\n  KILLER: "2504                        << *KillingLocWrapper.DefInst << '\n');2505      deleteDeadInstruction(DeadLocWrapper.DefInst, &Deleted);2506      ++NumFastStores;2507      Changed = true;2508    } else {2509      // Check if DeadI overwrites KillingI.2510      int64_t KillingOffset = 0;2511      int64_t DeadOffset = 0;2512      OverwriteResult OR =2513          isOverwrite(KillingLocWrapper.DefInst, DeadLocWrapper.DefInst,2514                      KillingLocWrapper.MemLoc, DeadLocWrapper.MemLoc,2515                      KillingOffset, DeadOffset);2516      if (OR == OW_MaybePartial) {2517        auto &IOL = IOLs[DeadLocWrapper.DefInst->getParent()];2518        OR = isPartialOverwrite(KillingLocWrapper.MemLoc, DeadLocWrapper.MemLoc,2519                                KillingOffset, DeadOffset,2520                                DeadLocWrapper.DefInst, IOL);2521      }2522      if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {2523        auto *DeadSI = dyn_cast<StoreInst>(DeadLocWrapper.DefInst);2524        auto *KillingSI = dyn_cast<StoreInst>(KillingLocWrapper.DefInst);2525        // We are re-using tryToMergePartialOverlappingStores, which requires2526        // DeadSI to dominate KillingSI.2527        // TODO: implement tryToMergeParialOverlappingStores using MemorySSA.2528        if (DeadSI && KillingSI && DT.dominates(DeadSI, KillingSI)) {2529          if (Constant *Merged = tryToMergePartialOverlappingStores(2530                  KillingSI, DeadSI, KillingOffset, DeadOffset, DL, BatchAA,2531                  &DT)) {2532 2533            // Update stored value of earlier store to merged constant.2534            DeadSI->setOperand(0, Merged);2535            ++NumModifiedStores;2536            Changed = true;2537            DeletedKillingLoc = true;2538 2539            // Remove killing store and remove any outstanding overlap2540            // intervals for the updated store.2541            deleteDeadInstruction(KillingSI, &Deleted);2542            auto I = IOLs.find(DeadSI->getParent());2543            if (I != IOLs.end())2544              I->second.erase(DeadSI);2545            break;2546          }2547        }2548      }2549      if (OR == OW_Complete) {2550        LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: "2551                          << *DeadLocWrapper.DefInst << "\n  KILLER: "2552                          << *KillingLocWrapper.DefInst << '\n');2553        deleteDeadInstruction(DeadLocWrapper.DefInst, &Deleted);2554        ++NumFastStores;2555        Changed = true;2556      }2557    }2558  }2559 2560  assert(SkipStores.size() - OrigNumSkipStores == Deleted.size() &&2561         "SkipStores and Deleted out of sync?");2562 2563  return {Changed, DeletedKillingLoc};2564}2565 2566bool DSEState::eliminateDeadDefs(const MemoryDefWrapper &KillingDefWrapper) {2567  if (KillingDefWrapper.DefinedLocations.empty()) {2568    LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for "2569                      << *KillingDefWrapper.DefInst << "\n");2570    return false;2571  }2572 2573  bool MadeChange = false;2574  for (auto &KillingLocWrapper : KillingDefWrapper.DefinedLocations) {2575    LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "2576                      << *KillingLocWrapper.MemDef << " ("2577                      << *KillingLocWrapper.DefInst << ")\n");2578    auto [Changed, DeletedKillingLoc] = eliminateDeadDefs(KillingLocWrapper);2579    MadeChange |= Changed;2580 2581    // Check if the store is a no-op.2582    if (!DeletedKillingLoc && storeIsNoop(KillingLocWrapper.MemDef,2583                                          KillingLocWrapper.UnderlyingObject)) {2584      LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n  DEAD: "2585                        << *KillingLocWrapper.DefInst << '\n');2586      deleteDeadInstruction(KillingLocWrapper.DefInst);2587      NumRedundantStores++;2588      MadeChange = true;2589      continue;2590    }2591    // Can we form a calloc from a memset/malloc pair?2592    if (!DeletedKillingLoc &&2593        tryFoldIntoCalloc(KillingLocWrapper.MemDef,2594                          KillingLocWrapper.UnderlyingObject)) {2595      LLVM_DEBUG(dbgs() << "DSE: Remove memset after forming calloc:\n"2596                        << "  DEAD: " << *KillingLocWrapper.DefInst << '\n');2597      deleteDeadInstruction(KillingLocWrapper.DefInst);2598      MadeChange = true;2599      continue;2600    }2601  }2602  return MadeChange;2603}2604 2605static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,2606                                DominatorTree &DT, PostDominatorTree &PDT,2607                                const TargetLibraryInfo &TLI,2608                                const LoopInfo &LI) {2609  bool MadeChange = false;2610  DSEState State(F, AA, MSSA, DT, PDT, TLI, LI);2611  // For each store:2612  for (unsigned I = 0; I < State.MemDefs.size(); I++) {2613    MemoryDef *KillingDef = State.MemDefs[I];2614    if (State.SkipStores.count(KillingDef))2615      continue;2616 2617    MemoryDefWrapper KillingDefWrapper(2618        KillingDef, State.getLocForInst(KillingDef->getMemoryInst(),2619                                        EnableInitializesImprovement));2620    MadeChange |= State.eliminateDeadDefs(KillingDefWrapper);2621  }2622 2623  if (EnablePartialOverwriteTracking)2624    for (auto &KV : State.IOLs)2625      MadeChange |= State.removePartiallyOverlappedStores(KV.second);2626 2627  MadeChange |= State.eliminateRedundantStoresOfExistingValues();2628  MadeChange |= State.eliminateDeadWritesAtEndOfFunction();2629 2630  while (!State.ToRemove.empty()) {2631    Instruction *DeadInst = State.ToRemove.pop_back_val();2632    DeadInst->eraseFromParent();2633  }2634 2635  return MadeChange;2636}2637 2638//===----------------------------------------------------------------------===//2639// DSE Pass2640//===----------------------------------------------------------------------===//2641PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {2642  AliasAnalysis &AA = AM.getResult<AAManager>(F);2643  const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);2644  DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);2645  MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();2646  PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);2647  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);2648 2649  bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI);2650 2651#ifdef LLVM_ENABLE_STATS2652  if (AreStatisticsEnabled())2653    for (auto &I : instructions(F))2654      NumRemainingStores += isa<StoreInst>(&I);2655#endif2656 2657  if (!Changed)2658    return PreservedAnalyses::all();2659 2660  PreservedAnalyses PA;2661  PA.preserveSet<CFGAnalyses>();2662  PA.preserve<MemorySSAAnalysis>();2663  PA.preserve<LoopAnalysis>();2664  return PA;2665}2666 2667namespace {2668 2669/// A legacy pass for the legacy pass manager that wraps \c DSEPass.2670class DSELegacyPass : public FunctionPass {2671public:2672  static char ID; // Pass identification, replacement for typeid2673 2674  DSELegacyPass() : FunctionPass(ID) {2675    initializeDSELegacyPassPass(*PassRegistry::getPassRegistry());2676  }2677 2678  bool runOnFunction(Function &F) override {2679    if (skipFunction(F))2680      return false;2681 2682    AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();2683    DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();2684    const TargetLibraryInfo &TLI =2685        getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);2686    MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();2687    PostDominatorTree &PDT =2688        getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();2689    LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();2690 2691    bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI);2692 2693#ifdef LLVM_ENABLE_STATS2694    if (AreStatisticsEnabled())2695      for (auto &I : instructions(F))2696        NumRemainingStores += isa<StoreInst>(&I);2697#endif2698 2699    return Changed;2700  }2701 2702  void getAnalysisUsage(AnalysisUsage &AU) const override {2703    AU.setPreservesCFG();2704    AU.addRequired<AAResultsWrapperPass>();2705    AU.addRequired<TargetLibraryInfoWrapperPass>();2706    AU.addPreserved<GlobalsAAWrapperPass>();2707    AU.addRequired<DominatorTreeWrapperPass>();2708    AU.addPreserved<DominatorTreeWrapperPass>();2709    AU.addRequired<PostDominatorTreeWrapperPass>();2710    AU.addRequired<MemorySSAWrapperPass>();2711    AU.addPreserved<PostDominatorTreeWrapperPass>();2712    AU.addPreserved<MemorySSAWrapperPass>();2713    AU.addRequired<LoopInfoWrapperPass>();2714    AU.addPreserved<LoopInfoWrapperPass>();2715    AU.addRequired<AssumptionCacheTracker>();2716  }2717};2718 2719} // end anonymous namespace2720 2721char DSELegacyPass::ID = 0;2722 2723INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,2724                      false)2725INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)2726INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)2727INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)2728INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)2729INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)2730INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)2731INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)2732INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)2733INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)2734INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false,2735                    false)2736 2737LLVM_ABI FunctionPass *llvm::createDeadStoreEliminationPass() {2738  return new DSELegacyPass();2739}2740