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 *Pred : predecessors(BB)) {
 682     if (Pred == BB)
 683       continue;
 684     // The second check below prevents adding blocks that form a cycle with BB
 685     // in order to avoid potential problems due to MemoryDependenceAnalysis,
 686     // isOverwrite, etc. being not loop-aware.
 687     if (!DT->isReachableFromEntry(Pred) || DT->dominates(BB, Pred))
 688       continue;
 689
 690     bool PredIsSafe = true;
 691     for (auto *Succ : successors(Pred)) {
 692       if (Succ == BB || Succ == Pred) // shortcut, BB should be in SafeBlocks
 693         continue;
 694       if (!SafeBlocks.count(Succ)) {
 695         PredIsSafe = false;
 696         break;
 697       }
 698     }
 699     if (PredIsSafe)
 700       PredBlocks.push_back(Pred);
 701   }
 702 }
 703
 704 static bool underlyingObjectsDoNotAlias(StoreInst *SI, LoadInst *LI,
 705                                         const DataLayout &DL,
 706                                         AliasAnalysis &AA) {
 707   Value *AObj = GetUnderlyingObject(SI->getPointerOperand(), DL);
 708   SmallVector<Value *, 4> Pointers;
 709   GetUnderlyingObjects(LI->getPointerOperand(), Pointers, DL);
 710
 711   for (auto *BObj : Pointers) {
 712     if (!AA.isNoAlias(AObj, DL.getTypeStoreSize(AObj->getType()), BObj,
 713                       DL.getTypeStoreSize(BObj->getType())))
 714       return false;
 715   }
 716   return true;
 717 }
 718
 719 /// handleNonLocalDependency - Handle a non-local dependency on
 720 /// the input instruction Inst located in BB in attempt to remove
 721 /// redundant stores outside BB.
 722 bool DSE::handleNonLocalDependency(Instruction *Inst) {
 723   auto *SI = dyn_cast<StoreInst>(Inst);
 724   if (!SI)
 725     return false;
 726   // Get the location being stored to.
 727   // If we don't get a useful location, bail out.
 728   MemoryLocation Loc = getLocForWrite(SI, *AA);
 729   if (!Loc.Ptr)
 730     return false;
 731
 732   bool MadeChange = false;
 733   BasicBlock *BB = Inst->getParent();
 734   const DataLayout &DL = BB->getModule()->getDataLayout();
 735
 736   // Worklist of predecessor blocks of BB
 737   SmallVector<BasicBlock *, 8> Blocks;
 738   // Keep track of all predecessor blocks that are safe to search through
 739   SmallSetVector<BasicBlock *, 8> SafeBlocks;
 740   SafeBlocks.insert(BB);
 741   findSafePreds(Blocks, SafeBlocks, BB, DT);
 742
 743   while (!Blocks.empty()) {
 744     BasicBlock *PB = Blocks.pop_back_val();
 745     MemDepResult Dep =
 746         MD->getPointerDependencyFrom(Loc, false, PB->end(), PB, SI);
 747     while (Dep.isDef() || Dep.isClobber()) {
 748       Instruction *Dependency = Dep.getInst();
 749
 750       // Filter out false dependency from a load to SI looking through phis.
 751       if (auto *LI = dyn_cast<LoadInst>(Dependency)) {
 752         if (underlyingObjectsDoNotAlias(SI, LI, DL, *AA)) {
 753           Dep = MD->getPointerDependencyFrom(Loc, false,
 754                                              Dependency->getIterator(), PB, SI);
 755           continue;
 756         }
 757       }
 758
 759       // If we don't get a useful location for the dependent instruction,
 760       // it doesn't write memory, it is not removable, or it might read Loc,
 761       // then bail out.
 762       MemoryLocation DepLoc = getLocForWrite(Dependency, *AA);
 763       if (!DepLoc.Ptr || !hasMemoryWrite(Dependency, *TLI) ||
 764           !isRemovable(Dependency) ||
 765           (AA->getModRefInfo(Dependency, Loc) & MRI_Ref))
 766         break;
 767
 768       // Don't remove a store within single-block loops;
 769       // we need more analysis: e.g. looking for an interferring load
 770       // above the store within the loop, etc.
 771       bool SingleBlockLoop = false;
 772       for (auto I = succ_begin(PB), E = succ_end(PB); I != E; ++I) {
 773         BasicBlock *Succ = *I;
 774         if (Succ == PB) {
 775           SingleBlockLoop = true;
 776           break;
 777         }
 778       }
 779       if (SingleBlockLoop)
 780         break;
 781
 782       int64_t InstWriteOffset, DepWriteOffset;
 783       OverwriteResult OR =
 784           isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset, InstWriteOffset);
 785       if (OR == OverwriteComplete) {
 786         DEBUG(dbgs() << "DSE: Remove Non-Local Dead Store:\n  DEAD: "
 787                      << *Dependency << "\n  KILLER: " << *SI << '\n');
 788
 789         // Delete redundant store and now-dead instructions that feed it.
 790         auto Next = std::next(Dependency->getIterator());
 791         DeleteDeadInstruction(Dependency, *MD, *TLI);
 792         ++NumNonLocalStores;
 793         MadeChange = true;
 794         Dep = MD->getPointerDependencyFrom(Loc, false, Next, PB, SI);
 795         continue;
 796       }
 797       // TODO: attempt shortening of Dependency inst as in the local case
 798       break;
 799     }
 800
 801     if (Dep.isNonLocal()) {
 802       SafeBlocks.insert(PB);
 803       findSafePreds(Blocks, SafeBlocks, PB, DT);
 804     }
 805   }
 806
 807   return MadeChange;
 808 }
 809
 810 /// Returns true if the memory which is accessed by the second instruction is not
 811 /// modified between the first and the second instruction.
 812 /// Precondition: Second instruction must be dominated by the first
 813 /// instruction.
 814 bool DSE::MemoryIsNotModifiedBetween(Instruction *FirstI,
 815                                      Instruction *SecondI) {
 816   SmallVector<BasicBlock *, 16> WorkList;
 817   SmallPtrSet<BasicBlock *, 8> Visited;
 818   BasicBlock::iterator FirstBBI(FirstI);
 819   ++FirstBBI;
 820   BasicBlock::iterator SecondBBI(SecondI);
 821   BasicBlock *FirstBB = FirstI->getParent();
 822   BasicBlock *SecondBB = SecondI->getParent();
 823   MemoryLocation MemLoc = MemoryLocation::get(SecondI);
 824
 825   // Start checking the store-block.
 826   WorkList.push_back(SecondBB);
 827   bool isFirstBlock = true;
 828
 829   // Check all blocks going backward until we reach the load-block.
 830   while (!WorkList.empty()) {
 831     BasicBlock *B = WorkList.pop_back_val();
 832
 833     // Ignore instructions before LI if this is the FirstBB.
 834     BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
 835
 836     BasicBlock::iterator EI;
 837     if (isFirstBlock) {
 838       // Ignore instructions after SI if this is the first visit of SecondBB.
 839       assert(B == SecondBB && "first block is not the store block");
 840       EI = SecondBBI;
 841       isFirstBlock = false;
 842     } else {
 843       // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
 844       // In this case we also have to look at instructions after SI.
 845       EI = B->end();
 846     }
 847     for (; BI != EI; ++BI) {
 848       Instruction *I = &*BI;
 849       if (I->mayWriteToMemory() && I != SecondI) {
 850         auto Res = AA->getModRefInfo(I, MemLoc);
 851         if (Res != MRI_NoModRef)
 852           return false;
 853       }
 854     }
 855     if (B != FirstBB) {
 856       assert(B != &FirstBB->getParent()->getEntryBlock() &&
 857           "Should not hit the entry block because SI must be dominated by LI");
 858       for (auto *PredI : predecessors(B)) {
 859         if (!Visited.insert(PredI).second)
 860           continue;
 861         WorkList.push_back(PredI);
 862       }
 863     }
 864   }
 865   return true;
 866 }
 867
 868 /// Find all blocks that will unconditionally lead to the block BB and append
 869 /// them to F.
 870 static void FindUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks,
 871                                    BasicBlock *BB, DominatorTree *DT) {
 872   for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
 873     BasicBlock *Pred = *I;
 874     if (Pred == BB) continue;
 875     TerminatorInst *PredTI = Pred->getTerminator();
 876     if (PredTI->getNumSuccessors() != 1)
 877       continue;
 878
 879     if (DT->isReachableFromEntry(Pred))
 880       Blocks.push_back(Pred);
 881   }
 882 }
 883
 884 /// HandleFree - Handle frees of entire structures whose dependency is a store
 885 /// to a field of that structure.
 886 bool DSE::HandleFree(CallInst *F) {
 887   bool MadeChange = false;
 888
 889   MemoryLocation Loc = MemoryLocation(F->getOperand(0));
 890   SmallVector<BasicBlock *, 16> Blocks;
 891   Blocks.push_back(F->getParent());
 892   const DataLayout &DL = F->getModule()->getDataLayout();
 893
 894   while (!Blocks.empty()) {
 895     BasicBlock *BB = Blocks.pop_back_val();
 896     Instruction *InstPt = BB->getTerminator();
 897     if (BB == F->getParent()) InstPt = F;
 898
 899     MemDepResult Dep =
 900         MD->getPointerDependencyFrom(Loc, false, InstPt->getIterator(), BB);
 901     while (Dep.isDef() || Dep.isClobber()) {
 902       Instruction *Dependency = Dep.getInst();
 903       if (!hasMemoryWrite(Dependency, *TLI) || !isRemovable(Dependency))
 904         break;
 905
 906       Value *DepPointer =
 907           GetUnderlyingObject(getStoredPointerOperand(Dependency), DL);
 908
 909       // Check for aliasing.
 910       if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
 911         break;
 912
 913       auto Next = ++Dependency->getIterator();
 914
 915       // DCE instructions only used to calculate that store
 916       DeleteDeadInstruction(Dependency, *MD, *TLI);
 917       ++NumFastStores;
 918       MadeChange = true;
 919
 920       // Inst's old Dependency is now deleted. Compute the next dependency,
 921       // which may also be dead, as in
 922       //    s[0] = 0;
 923       //    s[1] = 0; // This has just been deleted.
 924       //    free(s);
 925       Dep = MD->getPointerDependencyFrom(Loc, false, Next, BB);
 926     }
 927
 928     if (Dep.isNonLocal())
 929       FindUnconditionalPreds(Blocks, BB, DT);
 930   }
 931
 932   return MadeChange;
 933 }
 934
 935 /// handleEndBlock - Remove dead stores to stack-allocated locations in the
 936 /// function end block.  Ex:
 937 /// %A = alloca i32
 938 /// ...
 939 /// store i32 1, i32* %A
 940 /// ret void
 941 bool DSE::handleEndBlock(BasicBlock &BB) {
 942   bool MadeChange = false;
 943
 944   // Keep track of all of the stack objects that are dead at the end of the
 945   // function.
 946   SmallSetVector<Value*, 16> DeadStackObjects;
 947
 948   // Find all of the alloca'd pointers in the entry block.
 949   BasicBlock &Entry = BB.getParent()->front();
 950   for (Instruction &I : Entry) {
 951     if (isa<AllocaInst>(&I))
 952       DeadStackObjects.insert(&I);
 953
 954     // Okay, so these are dead heap objects, but if the pointer never escapes
 955     // then it's leaked by this function anyways.
 956     else if (isAllocLikeFn(&I, TLI) && !PointerMayBeCaptured(&I, true, true))
 957       DeadStackObjects.insert(&I);
 958   }
 959
 960   // Treat byval or inalloca arguments the same, stores to them are dead at the
 961   // end of the function.
 962   for (Argument &AI : BB.getParent()->args())
 963     if (AI.hasByValOrInAllocaAttr())
 964       DeadStackObjects.insert(&AI);
 965
 966   const DataLayout &DL = BB.getModule()->getDataLayout();
 967
 968   // Scan the basic block backwards
 969   for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
 970     --BBI;
 971
 972     // If we find a store, check to see if it points into a dead stack value.
 973     if (hasMemoryWrite(&*BBI, *TLI) && isRemovable(&*BBI)) {
 974       // See through pointer-to-pointer bitcasts
 975       SmallVector<Value *, 4> Pointers;
 976       GetUnderlyingObjects(getStoredPointerOperand(&*BBI), Pointers, DL);
 977
 978       // Stores to stack values are valid candidates for removal.
 979       bool AllDead = true;
 980       for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(),
 981            E = Pointers.end(); I != E; ++I)
 982         if (!DeadStackObjects.count(*I)) {
 983           AllDead = false;
 984           break;
 985         }
 986
 987       if (AllDead) {
 988         Instruction *Dead = &*BBI++;
 989
 990         DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 991                      << *Dead << "\n  Objects: ";
 992               for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(),
 993                    E = Pointers.end(); I != E; ++I) {
 994                 dbgs() << **I;
 995                 if (std::next(I) != E)
 996                   dbgs() << ", ";
 997               }
 998               dbgs() << '\n');
 999
1000         // DCE instructions only used to calculate that store.
1001         DeleteDeadInstruction(Dead, *MD, *TLI, &DeadStackObjects);
1002         ++NumFastStores;
1003         MadeChange = true;
1004         continue;
1005       }
1006     }
1007
1008     // Remove any dead non-memory-mutating instructions.
1009     if (isInstructionTriviallyDead(&*BBI, TLI)) {
1010       Instruction *Inst = &*BBI++;
1011       DeleteDeadInstruction(Inst, *MD, *TLI, &DeadStackObjects);
1012       ++NumFastOther;
1013       MadeChange = true;
1014       continue;
1015     }
1016
1017     if (isa<AllocaInst>(BBI)) {
1018       // Remove allocas from the list of dead stack objects; there can't be
1019       // any references before the definition.
1020       DeadStackObjects.remove(&*BBI);
1021       continue;
1022     }
1023
1024     if (auto CS = CallSite(&*BBI)) {
1025       // Remove allocation function calls from the list of dead stack objects;
1026       // there can't be any references before the definition.
1027       if (isAllocLikeFn(&*BBI, TLI))
1028         DeadStackObjects.remove(&*BBI);
1029
1030       // If this call does not access memory, it can't be loading any of our
1031       // pointers.
1032       if (AA->doesNotAccessMemory(CS))
1033         continue;
1034
1035       // If the call might load from any of our allocas, then any store above
1036       // the call is live.
1037       DeadStackObjects.remove_if([&](Value *I) {
1038         // See if the call site touches the value.
1039         ModRefInfo A = AA->getModRefInfo(CS, I, getPointerSize(I, DL, *TLI));
1040
1041         return A == MRI_ModRef || A == MRI_Ref;
1042       });
1043
1044       // If all of the allocas were clobbered by the call then we're not going
1045       // to find anything else to process.
1046       if (DeadStackObjects.empty())
1047         break;
1048
1049       continue;
1050     }
1051
1052     MemoryLocation LoadedLoc;
1053
1054     // If we encounter a use of the pointer, it is no longer considered dead
1055     if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
1056       if (!L->isUnordered()) // Be conservative with atomic/volatile load
1057         break;
1058       LoadedLoc = MemoryLocation::get(L);
1059     } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
1060       LoadedLoc = MemoryLocation::get(V);
1061     } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) {
1062       LoadedLoc = MemoryLocation::getForSource(MTI);
1063     } else if (!BBI->mayReadFromMemory()) {
1064       // Instruction doesn't read memory.  Note that stores that weren't removed
1065       // above will hit this case.
1066       continue;
1067     } else {
1068       // Unknown inst; assume it clobbers everything.
1069       break;
1070     }
1071
1072     // Remove any allocas from the DeadPointer set that are loaded, as this
1073     // makes any stores above the access live.
1074     RemoveAccessedObjects(LoadedLoc, DeadStackObjects, DL);
1075
1076     // If all of the allocas were clobbered by the access then we're not going
1077     // to find anything else to process.
1078     if (DeadStackObjects.empty())
1079       break;
1080   }
1081
1082   return MadeChange;
1083 }
1084
1085 /// RemoveAccessedObjects - Check to see if the specified location may alias any
1086 /// of the stack objects in the DeadStackObjects set.  If so, they become live
1087 /// because the location is being loaded.
1088 void DSE::RemoveAccessedObjects(const MemoryLocation &LoadedLoc,
1089                                 SmallSetVector<Value *, 16> &DeadStackObjects,
1090                                 const DataLayout &DL) {
1091   const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr, DL);
1092
1093   // A constant can't be in the dead pointer set.
1094   if (isa<Constant>(UnderlyingPointer))
1095     return;
1096
1097   // If the kill pointer can be easily reduced to an alloca, don't bother doing
1098   // extraneous AA queries.
1099   if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) {
1100     DeadStackObjects.remove(const_cast<Value*>(UnderlyingPointer));
1101     return;
1102   }
1103
1104   // Remove objects that could alias LoadedLoc.
1105   DeadStackObjects.remove_if([&](Value *I) {
1106     // See if the loaded location could alias the stack location.
1107     MemoryLocation StackLoc(I, getPointerSize(I, DL, *TLI));
1108     return !AA->isNoAlias(StackLoc, LoadedLoc);
1109   });
1110 }