lib/Transforms/Scalar/DeadStoreElimination.cpp

   1 //===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements dead store elimination that considers redundant stores
  11 // within a basic-block as well as across basic blocks in a reverse CFG order.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/Scalar.h"
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/ADT/SetVector.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/Analysis/AliasAnalysis.h"
  20 #include "llvm/Analysis/CaptureTracking.h"
  21 #include "llvm/Analysis/GlobalsModRef.h"
  22 #include "llvm/Analysis/MemoryBuiltins.h"
  23 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
  24 #include "llvm/Analysis/TargetLibraryInfo.h"
  25 #include "llvm/Analysis/ValueTracking.h"
  26 #include "llvm/IR/Constants.h"
  27 #include "llvm/IR/DataLayout.h"
  28 #include "llvm/IR/Dominators.h"
  29 #include "llvm/IR/Function.h"
  30 #include "llvm/IR/GlobalVariable.h"
  31 #include "llvm/IR/Instructions.h"
  32 #include "llvm/IR/IntrinsicInst.h"
  33 #include "llvm/Pass.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/raw_ostream.h"
  36 #include "llvm/Transforms/Utils/Local.h"
  37 using namespace llvm;
  38
  39 #define DEBUG_TYPE "dse"
  40
  41 STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
  42 STATISTIC(NumFastStores, "Number of stores deleted");
  43 STATISTIC(NumFastOther , "Number of other instrs removed");
  44 STATISTIC(NumNonLocalStores, "Number of non-local stores deleted");
  45
  46 static cl::opt<bool> EnableNonLocalDSE("enable-nonlocal-dse", cl::init(true));
  47
  48 /// MaxNonLocalAttempts is an arbitrary threshold that provides
  49 /// an early opportunitiy for bail out to control compile time.
  50 static const unsigned MaxNonLocalAttempts = 100;
  51
  52 namespace {
  53   struct DSE : public FunctionPass {
  54     AliasAnalysis *AA;
  55     MemoryDependenceAnalysis *MD;
  56     DominatorTree *DT;
  57     const TargetLibraryInfo *TLI;
  58
  59     static char ID; // Pass identification, replacement for typeid
  60     DSE() : FunctionPass(ID), AA(nullptr), MD(nullptr), DT(nullptr) {
  61       initializeDSEPass(*PassRegistry::getPassRegistry());
  62     }
  63
  64     bool runOnFunction(Function &F) override {
  65       if (skipOptnoneFunction(F))
  66         return false;
  67
  68       AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
  69       MD = &getAnalysis<MemoryDependenceAnalysis>();
  70       DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  71       TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
  72
  73       bool Changed = false;
  74       for (BasicBlock &I : F)
  75         // Only check non-dead blocks.  Dead blocks may have strange pointer
  76         // cycles that will confuse alias analysis.
  77         if (DT->isReachableFromEntry(&I))
  78           Changed |= runOnBasicBlock(I);
  79
  80       AA = nullptr; MD = nullptr; DT = nullptr;
  81       return Changed;
  82     }
  83
  84     bool runOnBasicBlock(BasicBlock &BB);
  85     bool MemoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI);
  86     bool HandleFree(CallInst *F);
  87     bool handleNonLocalDependency(Instruction *Inst);
  88     bool handleEndBlock(BasicBlock &BB);
  89     void RemoveAccessedObjects(const MemoryLocation &LoadedLoc,
  90                                SmallSetVector<Value *, 16> &DeadStackObjects,
  91                                const DataLayout &DL);
  92
  93     void getAnalysisUsage(AnalysisUsage &AU) const override {
  94       AU.setPreservesCFG();
  95       AU.addRequired<DominatorTreeWrapperPass>();
  96       AU.addRequired<AAResultsWrapperPass>();
  97       AU.addRequired<MemoryDependenceAnalysis>();
  98       AU.addRequired<TargetLibraryInfoWrapperPass>();
  99       AU.addPreserved<DominatorTreeWrapperPass>();
 100       AU.addPreserved<GlobalsAAWrapperPass>();
 101       AU.addPreserved<MemoryDependenceAnalysis>();
 102     }
 103   };
 104 }
 105
 106 char DSE::ID = 0;
 107 INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false)
 108 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 109 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 110 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 111 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
 112 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 113 INITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false)
 114
 115 FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
 116
 117 //===----------------------------------------------------------------------===//
 118 // Helper functions
 119 //===----------------------------------------------------------------------===//
 120
 121 /// DeleteDeadInstruction - Delete this instruction.  Before we do, go through
 122 /// and zero out all the operands of this instruction.  If any of them become
 123 /// dead, delete them and the computation tree that feeds them.
 124 ///
 125 /// If ValueSet is non-null, remove any deleted instructions from it as well.
 126 ///
 127 static void DeleteDeadInstruction(Instruction *I,
 128                                MemoryDependenceAnalysis &MD,
 129                                const TargetLibraryInfo &TLI,
 130                                SmallSetVector<Value*, 16> *ValueSet = nullptr) {
 131   SmallVector<Instruction*, 32> NowDeadInsts;
 132
 133   NowDeadInsts.push_back(I);
 134   --NumFastOther;
 135
 136   // Before we touch this instruction, remove it from memdep!
 137   do {
 138     Instruction *DeadInst = NowDeadInsts.pop_back_val();
 139     ++NumFastOther;
 140
 141     // This instruction is dead, zap it, in stages.  Start by removing it from
 142     // MemDep, which needs to know the operands and needs it to be in the
 143     // function.
 144     MD.removeInstruction(DeadInst);
 145
 146     for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
 147       Value *Op = DeadInst->getOperand(op);
 148       DeadInst->setOperand(op, nullptr);
 149
 150       // If this operand just became dead, add it to the NowDeadInsts list.
 151       if (!Op->use_empty()) continue;
 152
 153       if (Instruction *OpI = dyn_cast<Instruction>(Op))
 154         if (isInstructionTriviallyDead(OpI, &TLI))
 155           NowDeadInsts.push_back(OpI);
 156     }
 157
 158     DeadInst->eraseFromParent();
 159
 160     if (ValueSet) ValueSet->remove(DeadInst);
 161   } while (!NowDeadInsts.empty());
 162 }
 163
 164
 165 /// hasMemoryWrite - Does this instruction write some memory?  This only returns
 166 /// true for things that we can analyze with other helpers below.
 167 static bool hasMemoryWrite(Instruction *I, const TargetLibraryInfo &TLI) {
 168   if (isa<StoreInst>(I))
 169     return true;
 170   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
 171     switch (II->getIntrinsicID()) {
 172     default:
 173       return false;
 174     case Intrinsic::memset:
 175     case Intrinsic::memmove:
 176     case Intrinsic::memcpy:
 177     case Intrinsic::init_trampoline:
 178     case Intrinsic::lifetime_end:
 179       return true;
 180     }
 181   }
 182   if (auto CS = CallSite(I)) {
 183     if (Function *F = CS.getCalledFunction()) {
 184       if (TLI.has(LibFunc::strcpy) &&
 185           F->getName() == TLI.getName(LibFunc::strcpy)) {
 186         return true;
 187       }
 188       if (TLI.has(LibFunc::strncpy) &&
 189           F->getName() == TLI.getName(LibFunc::strncpy)) {
 190         return true;
 191       }
 192       if (TLI.has(LibFunc::strcat) &&
 193           F->getName() == TLI.getName(LibFunc::strcat)) {
 194         return true;
 195       }
 196       if (TLI.has(LibFunc::strncat) &&
 197           F->getName() == TLI.getName(LibFunc::strncat)) {
 198         return true;
 199       }
 200     }
 201   }
 202   return false;
 203 }
 204
 205 /// getLocForWrite - Return a Location stored to by the specified instruction.
 206 /// If isRemovable returns true, this function and getLocForRead completely
 207 /// describe the memory operations for this instruction.
 208 static MemoryLocation getLocForWrite(Instruction *Inst, AliasAnalysis &AA) {
 209   if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
 210     return MemoryLocation::get(SI);
 211
 212   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) {
 213     // memcpy/memmove/memset.
 214     MemoryLocation Loc = MemoryLocation::getForDest(MI);
 215     return Loc;
 216   }
 217
 218   IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst);
 219   if (!II)
 220     return MemoryLocation();
 221
 222   switch (II->getIntrinsicID()) {
 223   default:
 224     return MemoryLocation(); // Unhandled intrinsic.
 225   case Intrinsic::init_trampoline:
 226     // FIXME: We don't know the size of the trampoline, so we can't really
 227     // handle it here.
 228     return MemoryLocation(II->getArgOperand(0));
 229   case Intrinsic::lifetime_end: {
 230     uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
 231     return MemoryLocation(II->getArgOperand(1), Len);
 232   }
 233   }
 234 }
 235
 236 /// getLocForRead - Return the location read by the specified "hasMemoryWrite"
 237 /// instruction if any.
 238 static MemoryLocation getLocForRead(Instruction *Inst,
 239                                     const TargetLibraryInfo &TLI) {
 240   assert(hasMemoryWrite(Inst, TLI) && "Unknown instruction case");
 241
 242   // The only instructions that both read and write are the mem transfer
 243   // instructions (memcpy/memmove).
 244   if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(Inst))
 245     return MemoryLocation::getForSource(MTI);
 246   return MemoryLocation();
 247 }
 248
 249
 250 /// isRemovable - If the value of this instruction and the memory it writes to
 251 /// is unused, may we delete this instruction?
 252 static bool isRemovable(Instruction *I) {
 253   // Don't remove volatile/atomic stores.
 254   if (StoreInst *SI = dyn_cast<StoreInst>(I))
 255     return SI->isUnordered();
 256
 257   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
 258     switch (II->getIntrinsicID()) {
 259     default: llvm_unreachable("doesn't pass 'hasMemoryWrite' predicate");
 260     case Intrinsic::lifetime_end:
 261       // Never remove dead lifetime_end's, e.g. because it is followed by a
 262       // free.
 263       return false;
 264     case Intrinsic::init_trampoline:
 265       // Always safe to remove init_trampoline.
 266       return true;
 267
 268     case Intrinsic::memset:
 269     case Intrinsic::memmove:
 270     case Intrinsic::memcpy:
 271       // Don't remove volatile memory intrinsics.
 272       return !cast<MemIntrinsic>(II)->isVolatile();
 273     }
 274   }
 275
 276   if (auto CS = CallSite(I))
 277     return CS.getInstruction()->use_empty();
 278
 279   return false;
 280 }
 281
 282
 283 /// isShortenable - Returns true if this instruction can be safely shortened in
 284 /// length.
 285 static bool isShortenable(Instruction *I) {
 286   // Don't shorten stores for now
 287   if (isa<StoreInst>(I))
 288     return false;
 289
 290   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
 291     switch (II->getIntrinsicID()) {
 292       default: return false;
 293       case Intrinsic::memset:
 294       case Intrinsic::memcpy:
 295         // Do shorten memory intrinsics.
 296         return true;
 297     }
 298   }
 299
 300   // Don't shorten libcalls calls for now.
 301
 302   return false;
 303 }
 304
 305 /// getStoredPointerOperand - Return the pointer that is being written to.
 306 static Value *getStoredPointerOperand(Instruction *I) {
 307   if (StoreInst *SI = dyn_cast<StoreInst>(I))
 308     return SI->getPointerOperand();
 309   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
 310     return MI->getDest();
 311
 312   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
 313     switch (II->getIntrinsicID()) {
 314     default: llvm_unreachable("Unexpected intrinsic!");
 315     case Intrinsic::init_trampoline:
 316       return II->getArgOperand(0);
 317     }
 318   }
 319
 320   CallSite CS(I);
 321   // All the supported functions so far happen to have dest as their first
 322   // argument.
 323   return CS.getArgument(0);
 324 }
 325
 326 static uint64_t getPointerSize(const Value *V, const DataLayout &DL,
 327                                const TargetLibraryInfo &TLI) {
 328   uint64_t Size;
 329   if (getObjectSize(V, Size, DL, &TLI))
 330     return Size;
 331   return MemoryLocation::UnknownSize;
 332 }
 333
 334 namespace {
 335   enum OverwriteResult
 336   {
 337     OverwriteComplete,
 338     OverwriteEnd,
 339     OverwriteUnknown
 340   };
 341 }
 342
 343 /// isOverwrite - Return 'OverwriteComplete' if a store to the 'Later' location
 344 /// completely overwrites a store to the 'Earlier' location.
 345 /// 'OverwriteEnd' if the end of the 'Earlier' location is completely
 346 /// overwritten by 'Later', or 'OverwriteUnknown' if nothing can be determined
 347 static OverwriteResult isOverwrite(const MemoryLocation &Later,
 348                                    const MemoryLocation &Earlier,
 349                                    const DataLayout &DL,
 350                                    const TargetLibraryInfo &TLI,
 351                                    int64_t &EarlierOff, int64_t &LaterOff) {
 352   const Value *P1 = Earlier.Ptr->stripPointerCasts();
 353   const Value *P2 = Later.Ptr->stripPointerCasts();
 354
 355   // If the start pointers are the same, we just have to compare sizes to see if
 356   // the later store was larger than the earlier store.
 357   if (P1 == P2) {
 358     // If we don't know the sizes of either access, then we can't do a
 359     // comparison.
 360     if (Later.Size == MemoryLocation::UnknownSize ||
 361         Earlier.Size == MemoryLocation::UnknownSize)
 362       return OverwriteUnknown;
 363
 364     // Make sure that the Later size is >= the Earlier size.
 365     if (Later.Size >= Earlier.Size)
 366       return OverwriteComplete;
 367   }
 368
 369   // Otherwise, we have to have size information, and the later store has to be
 370   // larger than the earlier one.
 371   if (Later.Size == MemoryLocation::UnknownSize ||
 372       Earlier.Size == MemoryLocation::UnknownSize)
 373     return OverwriteUnknown;
 374
 375   // Check to see if the later store is to the entire object (either a global,
 376   // an alloca, or a byval/inalloca argument).  If so, then it clearly
 377   // overwrites any other store to the same object.
 378   const Value *UO1 = GetUnderlyingObject(P1, DL),
 379               *UO2 = GetUnderlyingObject(P2, DL);
 380
 381   // If we can't resolve the same pointers to the same object, then we can't
 382   // analyze them at all.
 383   if (UO1 != UO2)
 384     return OverwriteUnknown;
 385
 386   // If the "Later" store is to a recognizable object, get its size.
 387   uint64_t ObjectSize = getPointerSize(UO2, DL, TLI);
 388   if (ObjectSize != MemoryLocation::UnknownSize)
 389     if (ObjectSize == Later.Size && ObjectSize >= Earlier.Size)
 390       return OverwriteComplete;
 391
 392   // Okay, we have stores to two completely different pointers.  Try to
 393   // decompose the pointer into a "base + constant_offset" form.  If the base
 394   // pointers are equal, then we can reason about the two stores.
 395   EarlierOff = 0;
 396   LaterOff = 0;
 397   const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);
 398   const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL);
 399
 400   // If the base pointers still differ, we have two completely different stores.
 401   if (BP1 != BP2)
 402     return OverwriteUnknown;
 403
 404   // The later store completely overlaps the earlier store if:
 405   //
 406   // 1. Both start at the same offset and the later one's size is greater than
 407   //    or equal to the earlier one's, or
 408   //
 409   //      |--earlier--|
 410   //      |--   later   --|
 411   //
 412   // 2. The earlier store has an offset greater than the later offset, but which
 413   //    still lies completely within the later store.
 414   //
 415   //        |--earlier--|
 416   //    |-----  later  ------|
 417   //
 418   // We have to be careful here as *Off is signed while *.Size is unsigned.
 419   if (EarlierOff >= LaterOff &&
 420       Later.Size >= Earlier.Size &&
 421       uint64_t(EarlierOff - LaterOff) + Earlier.Size <= Later.Size)
 422     return OverwriteComplete;
 423
 424   // The other interesting case is if the later store overwrites the end of
 425   // the earlier store
 426   //
 427   //      |--earlier--|
 428   //                |--   later   --|
 429   //
 430   // In this case we may want to trim the size of earlier to avoid generating
 431   // writes to addresses which will definitely be overwritten later
 432   if (LaterOff > EarlierOff &&
 433       LaterOff < int64_t(EarlierOff + Earlier.Size) &&
 434       int64_t(LaterOff + Later.Size) >= int64_t(EarlierOff + Earlier.Size))
 435     return OverwriteEnd;
 436
 437   // Otherwise, they don't completely overlap.
 438   return OverwriteUnknown;
 439 }
 440
 441 /// isPossibleSelfRead - If 'Inst' might be a self read (i.e. a noop copy of a
 442 /// memory region into an identical pointer) then it doesn't actually make its
 443 /// input dead in the traditional sense.  Consider this case:
 444 ///
 445 ///   memcpy(A <- B)
 446 ///   memcpy(A <- A)
 447 ///
 448 /// In this case, the second store to A does not make the first store to A dead.
 449 /// The usual situation isn't an explicit A<-A store like this (which can be
 450 /// trivially removed) but a case where two pointers may alias.
 451 ///
 452 /// This function detects when it is unsafe to remove a dependent instruction
 453 /// because the DSE inducing instruction may be a self-read.
 454 static bool isPossibleSelfRead(Instruction *Inst,
 455                                const MemoryLocation &InstStoreLoc,
 456                                Instruction *DepWrite,
 457                                const TargetLibraryInfo &TLI,
 458                                AliasAnalysis &AA) {
 459   // Self reads can only happen for instructions that read memory.  Get the
 460   // location read.
 461   MemoryLocation InstReadLoc = getLocForRead(Inst, TLI);
 462   if (!InstReadLoc.Ptr) return false;  // Not a reading instruction.
 463
 464   // If the read and written loc obviously don't alias, it isn't a read.
 465   if (AA.isNoAlias(InstReadLoc, InstStoreLoc)) return false;
 466
 467   // Okay, 'Inst' may copy over itself.  However, we can still remove a the
 468   // DepWrite instruction if we can prove that it reads from the same location
 469   // as Inst.  This handles useful cases like:
 470   //   memcpy(A <- B)
 471   //   memcpy(A <- B)
 472   // Here we don't know if A/B may alias, but we do know that B/B are must
 473   // aliases, so removing the first memcpy is safe (assuming it writes <= #
 474   // bytes as the second one.
 475   MemoryLocation DepReadLoc = getLocForRead(DepWrite, TLI);
 476
 477   if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr))
 478     return false;
 479
 480   // If DepWrite doesn't read memory or if we can't prove it is a must alias,
 481   // then it can't be considered dead.
 482   return true;
 483 }
 484
 485
 486 //===----------------------------------------------------------------------===//
 487 // DSE Pass
 488 //===----------------------------------------------------------------------===//
 489
 490 bool DSE::runOnBasicBlock(BasicBlock &BB) {
 491   const DataLayout &DL = BB.getModule()->getDataLayout();
 492   bool MadeChange = false;
 493   unsigned NumNonLocalAttempts = 0;
 494
 495   // Do a top-down walk on the BB.
 496   for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
 497     Instruction *Inst = &*BBI++;
 498
 499     // Handle 'free' calls specially.
 500     if (CallInst *F = isFreeCall(Inst, TLI)) {
 501       MadeChange |= HandleFree(F);
 502       continue;
 503     }
 504
 505     // If we find something that writes memory, get its memory dependence.
 506     if (!hasMemoryWrite(Inst, *TLI))
 507       continue;
 508
 509     // If we're storing the same value back to a pointer that we just
 510     // loaded from, then the store can be removed.
 511     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 512
 513       auto RemoveDeadInstAndUpdateBBI = [&](Instruction *DeadInst) {
 514         // DeleteDeadInstruction can delete the current instruction.  Save BBI
 515         // in case we need it.
 516         WeakVH NextInst(&*BBI);
 517
 518         DeleteDeadInstruction(DeadInst, *MD, *TLI);
 519
 520         if (!NextInst) // Next instruction deleted.
 521           BBI = BB.begin();
 522         else if (BBI != BB.begin()) // Revisit this instruction if possible.
 523           --BBI;
 524         ++NumRedundantStores;
 525         MadeChange = true;
 526       };
 527
 528       if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
 529         if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
 530             isRemovable(SI) &&
 531             MemoryIsNotModifiedBetween(DepLoad, SI)) {
 532
 533           DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n  "
 534                        << "LOAD: " << *DepLoad << "\n  STORE: " << *SI << '\n');
 535
 536           RemoveDeadInstAndUpdateBBI(SI);
 537           continue;
 538         }
 539       }
 540
 541       // Remove null stores into the calloc'ed objects
 542       Constant *StoredConstant = dyn_cast<Constant>(SI->getValueOperand());
 543
 544       if (StoredConstant && StoredConstant->isNullValue() &&
 545           isRemovable(SI)) {
 546         Instruction *UnderlyingPointer = dyn_cast<Instruction>(
 547             GetUnderlyingObject(SI->getPointerOperand(), DL));
 548
 549         if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
 550             MemoryIsNotModifiedBetween(UnderlyingPointer, SI)) {
 551           DEBUG(dbgs()
 552                 << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
 553                 << *Inst << "\n  OBJECT: " << *UnderlyingPointer << '\n');
 554
 555           RemoveDeadInstAndUpdateBBI(SI);
 556           continue;
 557         }
 558       }
 559     }
 560
 561     MemDepResult InstDep = MD->getDependency(Inst);
 562
 563     if (InstDep.isDef() || InstDep.isClobber()) {
 564       // Figure out what location is being stored to.
 565       MemoryLocation Loc = getLocForWrite(Inst, *AA);
 566
 567       // If we didn't get a useful location, fail.
 568       if (!Loc.Ptr)
 569         continue;
 570
 571       while (InstDep.isDef() || InstDep.isClobber()) {
 572         // Get the memory clobbered by the instruction we depend on.  MemDep
 573         // will skip any instructions that 'Loc' clearly doesn't interact with.
 574         // If we end up depending on a may- or must-aliased load, then we can't
 575         // optimize away the store and we bail out.  However, if we depend on on
 576         // something that overwrites the memory location we *can* potentially
 577         // optimize it.
 578         //
 579         // Find out what memory location the dependent instruction stores.
 580         Instruction *DepWrite = InstDep.getInst();
 581         MemoryLocation DepLoc = getLocForWrite(DepWrite, *AA);
 582         // If we didn't get a useful location, or if it isn't a size, bail out.
 583         if (!DepLoc.Ptr)
 584           break;
 585
 586         // If we find a write that is a) removable (i.e., non-volatile), b) is
 587         // completely obliterated by the store to 'Loc', and c) which we know
 588         // that 'Inst' doesn't load from, then we can remove it.
 589         if (isRemovable(DepWrite) &&
 590             !isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)) {
 591           int64_t InstWriteOffset, DepWriteOffset;
 592           OverwriteResult OR = isOverwrite(Loc, DepLoc, DL, *TLI,
 593                                            DepWriteOffset, InstWriteOffset);
 594           if (OR == OverwriteComplete) {
 595             DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *DepWrite
 596                          << "\n  KILLER: " << *Inst << '\n');
 597
 598             // Delete the store and now-dead instructions that feed it.
 599             DeleteDeadInstruction(DepWrite, *MD, *TLI);
 600             ++NumFastStores;
 601             MadeChange = true;
 602
 603             // DeleteDeadInstruction can delete the current instruction in loop
 604             // cases, reset BBI.
 605             BBI = Inst->getIterator();
 606             if (BBI != BB.begin())
 607               --BBI;
 608             break;
 609           } else if (OR == OverwriteEnd && isShortenable(DepWrite)) {
 610             // TODO: base this on the target vector size so that if the earlier
 611             // store was too small to get vector writes anyway then its likely a
 612             // good idea to shorten it.
 613
 614             // Power of 2 vector writes are probably always a bad idea to
 615             // optimize as any store/memset/memcpy is likely using vector
 616             // instructions so shortening it to not vector size is likely to be
 617             // slower.
 618             MemIntrinsic *DepIntrinsic = cast<MemIntrinsic>(DepWrite);
 619             unsigned DepWriteAlign = DepIntrinsic->getAlignment();
 620             if (llvm::isPowerOf2_64(InstWriteOffset) ||
 621                 ((DepWriteAlign != 0) &&
 622                  InstWriteOffset % DepWriteAlign == 0)) {
 623
 624               DEBUG(dbgs() << "DSE: Remove Dead Store:\n  OW END: " << *DepWrite
 625                            << "\n  KILLER (offset " << InstWriteOffset << ", "
 626                            << DepLoc.Size << ")" << *Inst << '\n');
 627
 628               Value *DepWriteLength = DepIntrinsic->getLength();
 629               Value *TrimmedLength = ConstantInt::get(
 630                   DepWriteLength->getType(), InstWriteOffset - DepWriteOffset);
 631               DepIntrinsic->setLength(TrimmedLength);
 632               MadeChange = true;
 633             }
 634           }
 635         }
 636
 637         // If this is a may-aliased store that is clobbering the store value, we
 638         // can keep searching past it for another must-aliased pointer that
 639         // stores to the same location.  For example, in
 640         //   store -> P
 641         //   store -> Q
 642         //   store -> P
 643         // we can remove the first store to P even though we don't know if P and
 644         // Q alias.
 645         if (DepWrite == &BB.front())
 646           break;
 647
 648         // Can't look past this instruction if it might read 'Loc'.
 649         if (AA->getModRefInfo(DepWrite, Loc) & MRI_Ref)
 650           break;
 651
 652         InstDep = MD->getPointerDependencyFrom(Loc, false,
 653                                                DepWrite->getIterator(), &BB);
 654       }
 655     } else if (EnableNonLocalDSE && InstDep.isNonLocal()) { // DSE across BB
 656       if (++NumNonLocalAttempts < MaxNonLocalAttempts)
 657         MadeChange |= handleNonLocalDependency(Inst);
 658     }
 659   }
 660
 661   // If this block ends in a return, unwind, or unreachable, all allocas are
 662   // dead at its end, which means stores to them are also dead.
 663   if (BB.getTerminator()->getNumSuccessors() == 0)
 664     MadeChange |= handleEndBlock(BB);
 665
 666   return MadeChange;
 667 }
 668
 669 /// A helper for handleNonLocalDependency() function to find all blocks
 670 /// that lead to the input block BB and append them to the output PredBlocks.
 671 /// PredBlocks will include not only predecessors of BB that unconditionally
 672 /// lead to BB but also:
 673 ///   - single-block loops that lead to BB, and
 674 ///   - if-blocks for which one edge goes to BB and the other edge goes to
 675 ///     a block in the input SafeBlocks.
 676 /// PredBlocks will not include blocks unreachable from the entry block, nor
 677 /// blocks that form cycles with BB.
 678 static void findSafePreds(SmallVectorImpl<BasicBlock *> &PredBlocks,
 679                           SmallSetVector<BasicBlock *, 8> &SafeBlocks,
 680                           BasicBlock *BB, DominatorTree *DT) {
 681   for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
 682     BasicBlock *Pred = *I;
 683     if (Pred == BB)
 684       continue;
 685     // The second check below prevents adding blocks that form a cycle with BB
 686     // in order to avoid potential problems due to MemoryDependenceAnalysis,
 687     // isOverwrite, etc. being not loop-aware.
 688     if (!DT->isReachableFromEntry(Pred) || DT->dominates(BB, Pred))
 689       continue;
 690
 691     bool PredIsSafe = true;
 692     for (auto II = succ_begin(Pred), EE = succ_end(Pred); II != EE; ++II) {
 693       BasicBlock *Succ = *II;
 694       if (Succ == BB || Succ == Pred) // shortcut, BB should be in SafeBlocks
 695         continue;
 696       if (!SafeBlocks.count(Succ)) {
 697         PredIsSafe = false;
 698         break;
 699       }
 700     }
 701     if (PredIsSafe)
 702       PredBlocks.push_back(Pred);
 703   }
 704 }
 705
 706 static bool underlyingObjectsDoNotAlias(StoreInst *SI, LoadInst *LI,
 707                                         const DataLayout &DL,
 708                                         AliasAnalysis &AA) {
 709   Value *AObj = GetUnderlyingObject(SI->getPointerOperand(), DL);
 710   SmallVector<Value *, 4> Pointers;
 711   GetUnderlyingObjects(LI->getPointerOperand(), Pointers, DL);
 712
 713   for (auto I = Pointers.begin(), E = Pointers.end(); I != E; ++I) {
 714     Value *BObj = *I;
 715     if (!AA.isNoAlias(AObj, DL.getTypeStoreSize(AObj->getType()), BObj,
 716                       DL.getTypeStoreSize(BObj->getType())))
 717       return false;
 718   }
 719   return true;
 720 }
 721
 722 /// handleNonLocalDependency - Handle a non-local dependency on
 723 /// the input instruction Inst located in BB in attempt to remove
 724 /// redundant stores outside BB.
 725 bool DSE::handleNonLocalDependency(Instruction *Inst) {
 726   auto *SI = dyn_cast<StoreInst>(Inst);
 727   if (!SI)
 728     return false;
 729   // Get the location being stored to.
 730   // If we don't get a useful location, bail out.
 731   MemoryLocation Loc = getLocForWrite(SI, *AA);
 732   if (!Loc.Ptr)
 733     return false;
 734
 735   bool MadeChange = false;
 736   BasicBlock *BB = Inst->getParent();
 737   const DataLayout &DL = BB->getModule()->getDataLayout();
 738
 739   // Worklist of predecessor blocks of BB
 740   SmallVector<BasicBlock *, 8> Blocks;
 741   // Keep track of all predecessor blocks that are safe to search through
 742   SmallSetVector<BasicBlock *, 8> SafeBlocks;
 743   SafeBlocks.insert(BB);
 744   findSafePreds(Blocks, SafeBlocks, BB, DT);
 745
 746   while (!Blocks.empty()) {
 747     BasicBlock *PB = Blocks.pop_back_val();
 748     MemDepResult Dep =
 749         MD->getPointerDependencyFrom(Loc, false, PB->end(), PB, SI);
 750     while (Dep.isDef() || Dep.isClobber()) {
 751       Instruction *Dependency = Dep.getInst();
 752
 753       // Filter out false dependency from a load to SI looking through phis.
 754       if (auto *LI = dyn_cast<LoadInst>(Dependency)) {
 755         if (underlyingObjectsDoNotAlias(SI, LI, DL, *AA)) {
 756           Dep = MD->getPointerDependencyFrom(Loc, false,
 757                                              Dependency->getIterator(), PB, SI);
 758           continue;
 759         }
 760       }
 761
 762       // If we don't get a useful location for the dependent instruction,
 763       // it doesn't write memory, it is not removable, or it might read Loc,
 764       // then bail out.
 765       MemoryLocation DepLoc = getLocForWrite(Dependency, *AA);
 766       if (!DepLoc.Ptr || !hasMemoryWrite(Dependency, *TLI) ||
 767           !isRemovable(Dependency) ||
 768           (AA->getModRefInfo(Dependency, Loc) & MRI_Ref))
 769         break;
 770
 771       // Don't remove a store within single-block loops;
 772       // we need more analysis: e.g. looking for an interferring load
 773       // above the store within the loop, etc.
 774       bool SingleBlockLoop = false;
 775       for (auto I = succ_begin(PB), E = succ_end(PB); I != E; ++I) {
 776         BasicBlock *Succ = *I;
 777         if (Succ == PB) {
 778           SingleBlockLoop = true;
 779           break;
 780         }
 781       }
 782       if (SingleBlockLoop)
 783         break;
 784
 785       int64_t InstWriteOffset, DepWriteOffset;
 786       OverwriteResult OR =
 787           isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset, InstWriteOffset);
 788       if (OR == OverwriteComplete) {
 789         DEBUG(dbgs() << "DSE: Remove Non-Local Dead Store:\n  DEAD: "
 790                      << *Dependency << "\n  KILLER: " << *SI << '\n');
 791
 792         // Delete redundant store and now-dead instructions that feed it.
 793         auto Next = std::next(Dependency->getIterator());
 794         DeleteDeadInstruction(Dependency, *MD, *TLI);
 795         ++NumNonLocalStores;
 796         MadeChange = true;
 797         Dep = MD->getPointerDependencyFrom(Loc, false, Next, PB, SI);
 798         continue;
 799       }
 800       // TODO: attempt shortening of Dependency inst as in the local case
 801       break;
 802     }
 803
 804     if (Dep.isNonLocal()) {
 805       SafeBlocks.insert(PB);
 806       findSafePreds(Blocks, SafeBlocks, PB, DT);
 807     }
 808   }
 809
 810   return MadeChange;
 811 }
 812
 813 /// Returns true if the memory which is accessed by the second instruction is not
 814 /// modified between the first and the second instruction.
 815 /// Precondition: Second instruction must be dominated by the first
 816 /// instruction.
 817 bool DSE::MemoryIsNotModifiedBetween(Instruction *FirstI,
 818                                      Instruction *SecondI) {
 819   SmallVector<BasicBlock *, 16> WorkList;
 820   SmallPtrSet<BasicBlock *, 8> Visited;
 821   BasicBlock::iterator FirstBBI(FirstI);
 822   ++FirstBBI;
 823   BasicBlock::iterator SecondBBI(SecondI);
 824   BasicBlock *FirstBB = FirstI->getParent();
 825   BasicBlock *SecondBB = SecondI->getParent();
 826   MemoryLocation MemLoc = MemoryLocation::get(SecondI);
 827
 828   // Start checking the store-block.
 829   WorkList.push_back(SecondBB);
 830   bool isFirstBlock = true;
 831
 832   // Check all blocks going backward until we reach the load-block.
 833   while (!WorkList.empty()) {
 834     BasicBlock *B = WorkList.pop_back_val();
 835
 836     // Ignore instructions before LI if this is the FirstBB.
 837     BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
 838
 839     BasicBlock::iterator EI;
 840     if (isFirstBlock) {
 841       // Ignore instructions after SI if this is the first visit of SecondBB.
 842       assert(B == SecondBB && "first block is not the store block");
 843       EI = SecondBBI;
 844       isFirstBlock = false;
 845     } else {
 846       // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
 847       // In this case we also have to look at instructions after SI.
 848       EI = B->end();
 849     }
 850     for (; BI != EI; ++BI) {
 851       Instruction *I = &*BI;
 852       if (I->mayWriteToMemory() && I != SecondI) {
 853         auto Res = AA->getModRefInfo(I, MemLoc);
 854         if (Res != MRI_NoModRef)
 855           return false;
 856       }
 857     }
 858     if (B != FirstBB) {
 859       assert(B != &FirstBB->getParent()->getEntryBlock() &&
 860           "Should not hit the entry block because SI must be dominated by LI");
 861       for (auto PredI = pred_begin(B), PE = pred_end(B); PredI != PE; ++PredI) {
 862         if (!Visited.insert(*PredI).second)
 863           continue;
 864         WorkList.push_back(*PredI);
 865       }
 866     }
 867   }
 868   return true;
 869 }
 870
 871 /// Find all blocks that will unconditionally lead to the block BB and append
 872 /// them to F.
 873 static void FindUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks,
 874                                    BasicBlock *BB, DominatorTree *DT) {
 875   for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
 876     BasicBlock *Pred = *I;
 877     if (Pred == BB) continue;
 878     TerminatorInst *PredTI = Pred->getTerminator();
 879     if (PredTI->getNumSuccessors() != 1)
 880       continue;
 881
 882     if (DT->isReachableFromEntry(Pred))
 883       Blocks.push_back(Pred);
 884   }
 885 }
 886
 887 /// HandleFree - Handle frees of entire structures whose dependency is a store
 888 /// to a field of that structure.
 889 bool DSE::HandleFree(CallInst *F) {
 890   bool MadeChange = false;
 891
 892   MemoryLocation Loc = MemoryLocation(F->getOperand(0));
 893   SmallVector<BasicBlock *, 16> Blocks;
 894   Blocks.push_back(F->getParent());
 895   const DataLayout &DL = F->getModule()->getDataLayout();
 896
 897   while (!Blocks.empty()) {
 898     BasicBlock *BB = Blocks.pop_back_val();
 899     Instruction *InstPt = BB->getTerminator();
 900     if (BB == F->getParent()) InstPt = F;
 901
 902     MemDepResult Dep =
 903         MD->getPointerDependencyFrom(Loc, false, InstPt->getIterator(), BB);
 904     while (Dep.isDef() || Dep.isClobber()) {
 905       Instruction *Dependency = Dep.getInst();
 906       if (!hasMemoryWrite(Dependency, *TLI) || !isRemovable(Dependency))
 907         break;
 908
 909       Value *DepPointer =
 910           GetUnderlyingObject(getStoredPointerOperand(Dependency), DL);
 911
 912       // Check for aliasing.
 913       if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
 914         break;
 915
 916       auto Next = ++Dependency->getIterator();
 917
 918       // DCE instructions only used to calculate that store
 919       DeleteDeadInstruction(Dependency, *MD, *TLI);
 920       ++NumFastStores;
 921       MadeChange = true;
 922
 923       // Inst's old Dependency is now deleted. Compute the next dependency,
 924       // which may also be dead, as in
 925       //    s[0] = 0;
 926       //    s[1] = 0; // This has just been deleted.
 927       //    free(s);
 928       Dep = MD->getPointerDependencyFrom(Loc, false, Next, BB);
 929     }
 930
 931     if (Dep.isNonLocal())
 932       FindUnconditionalPreds(Blocks, BB, DT);
 933   }
 934
 935   return MadeChange;
 936 }
 937
 938 /// handleEndBlock - Remove dead stores to stack-allocated locations in the
 939 /// function end block.  Ex:
 940 /// %A = alloca i32
 941 /// ...
 942 /// store i32 1, i32* %A
 943 /// ret void
 944 bool DSE::handleEndBlock(BasicBlock &BB) {
 945   bool MadeChange = false;
 946
 947   // Keep track of all of the stack objects that are dead at the end of the
 948   // function.
 949   SmallSetVector<Value*, 16> DeadStackObjects;
 950
 951   // Find all of the alloca'd pointers in the entry block.
 952   BasicBlock &Entry = BB.getParent()->front();
 953   for (Instruction &I : Entry) {
 954     if (isa<AllocaInst>(&I))
 955       DeadStackObjects.insert(&I);
 956
 957     // Okay, so these are dead heap objects, but if the pointer never escapes
 958     // then it's leaked by this function anyways.
 959     else if (isAllocLikeFn(&I, TLI) && !PointerMayBeCaptured(&I, true, true))
 960       DeadStackObjects.insert(&I);
 961   }
 962
 963   // Treat byval or inalloca arguments the same, stores to them are dead at the
 964   // end of the function.
 965   for (Argument &AI : BB.getParent()->args())
 966     if (AI.hasByValOrInAllocaAttr())
 967       DeadStackObjects.insert(&AI);
 968
 969   const DataLayout &DL = BB.getModule()->getDataLayout();
 970
 971   // Scan the basic block backwards
 972   for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
 973     --BBI;
 974
 975     // If we find a store, check to see if it points into a dead stack value.
 976     if (hasMemoryWrite(&*BBI, *TLI) && isRemovable(&*BBI)) {
 977       // See through pointer-to-pointer bitcasts
 978       SmallVector<Value *, 4> Pointers;
 979       GetUnderlyingObjects(getStoredPointerOperand(&*BBI), Pointers, DL);
 980
 981       // Stores to stack values are valid candidates for removal.
 982       bool AllDead = true;
 983       for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(),
 984            E = Pointers.end(); I != E; ++I)
 985         if (!DeadStackObjects.count(*I)) {
 986           AllDead = false;
 987           break;
 988         }
 989
 990       if (AllDead) {
 991         Instruction *Dead = &*BBI++;
 992
 993         DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 994                      << *Dead << "\n  Objects: ";
 995               for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(),
 996                    E = Pointers.end(); I != E; ++I) {
 997                 dbgs() << **I;
 998                 if (std::next(I) != E)
 999                   dbgs() << ", ";
1000               }
1001               dbgs() << '\n');
1002
1003         // DCE instructions only used to calculate that store.
1004         DeleteDeadInstruction(Dead, *MD, *TLI, &DeadStackObjects);
1005         ++NumFastStores;
1006         MadeChange = true;
1007         continue;
1008       }
1009     }
1010
1011     // Remove any dead non-memory-mutating instructions.
1012     if (isInstructionTriviallyDead(&*BBI, TLI)) {
1013       Instruction *Inst = &*BBI++;
1014       DeleteDeadInstruction(Inst, *MD, *TLI, &DeadStackObjects);
1015       ++NumFastOther;
1016       MadeChange = true;
1017       continue;
1018     }
1019
1020     if (isa<AllocaInst>(BBI)) {
1021       // Remove allocas from the list of dead stack objects; there can't be
1022       // any references before the definition.
1023       DeadStackObjects.remove(&*BBI);
1024       continue;
1025     }
1026
1027     if (auto CS = CallSite(&*BBI)) {
1028       // Remove allocation function calls from the list of dead stack objects;
1029       // there can't be any references before the definition.
1030       if (isAllocLikeFn(&*BBI, TLI))
1031         DeadStackObjects.remove(&*BBI);
1032
1033       // If this call does not access memory, it can't be loading any of our
1034       // pointers.
1035       if (AA->doesNotAccessMemory(CS))
1036         continue;
1037
1038       // If the call might load from any of our allocas, then any store above
1039       // the call is live.
1040       DeadStackObjects.remove_if([&](Value *I) {
1041         // See if the call site touches the value.
1042         ModRefInfo A = AA->getModRefInfo(CS, I, getPointerSize(I, DL, *TLI));
1043
1044         return A == MRI_ModRef || A == MRI_Ref;
1045       });
1046
1047       // If all of the allocas were clobbered by the call then we're not going
1048       // to find anything else to process.
1049       if (DeadStackObjects.empty())
1050         break;
1051
1052       continue;
1053     }
1054
1055     MemoryLocation LoadedLoc;
1056
1057     // If we encounter a use of the pointer, it is no longer considered dead
1058     if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
1059       if (!L->isUnordered()) // Be conservative with atomic/volatile load
1060         break;
1061       LoadedLoc = MemoryLocation::get(L);
1062     } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
1063       LoadedLoc = MemoryLocation::get(V);
1064     } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) {
1065       LoadedLoc = MemoryLocation::getForSource(MTI);
1066     } else if (!BBI->mayReadFromMemory()) {
1067       // Instruction doesn't read memory.  Note that stores that weren't removed
1068       // above will hit this case.
1069       continue;
1070     } else {
1071       // Unknown inst; assume it clobbers everything.
1072       break;
1073     }
1074
1075     // Remove any allocas from the DeadPointer set that are loaded, as this
1076     // makes any stores above the access live.
1077     RemoveAccessedObjects(LoadedLoc, DeadStackObjects, DL);
1078
1079     // If all of the allocas were clobbered by the access then we're not going
1080     // to find anything else to process.
1081     if (DeadStackObjects.empty())
1082       break;
1083   }
1084
1085   return MadeChange;
1086 }
1087
1088 /// RemoveAccessedObjects - Check to see if the specified location may alias any
1089 /// of the stack objects in the DeadStackObjects set.  If so, they become live
1090 /// because the location is being loaded.
1091 void DSE::RemoveAccessedObjects(const MemoryLocation &LoadedLoc,
1092                                 SmallSetVector<Value *, 16> &DeadStackObjects,
1093                                 const DataLayout &DL) {
1094   const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr, DL);
1095
1096   // A constant can't be in the dead pointer set.
1097   if (isa<Constant>(UnderlyingPointer))
1098     return;
1099
1100   // If the kill pointer can be easily reduced to an alloca, don't bother doing
1101   // extraneous AA queries.
1102   if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) {
1103     DeadStackObjects.remove(const_cast<Value*>(UnderlyingPointer));
1104     return;
1105   }
1106
1107   // Remove objects that could alias LoadedLoc.
1108   DeadStackObjects.remove_if([&](Value *I) {
1109     // See if the loaded location could alias the stack location.
1110     MemoryLocation StackLoc(I, getPointerSize(I, DL, *TLI));
1111     return !AA->isNoAlias(StackLoc, LoadedLoc);
1112   });
1113 }