LLVM  mainline
DeadStoreElimination.cpp
Go to the documentation of this file.
00001 //===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a trivial dead store elimination that only considers
00011 // basic-block local redundant stores.
00012 //
00013 // FIXME: This should eventually be extended to be a post-dominator tree
00014 // traversal.  Doing so would be pretty trivial.
00015 //
00016 //===----------------------------------------------------------------------===//
00017 
00018 #include "llvm/Transforms/Scalar.h"
00019 #include "llvm/ADT/STLExtras.h"
00020 #include "llvm/ADT/SetVector.h"
00021 #include "llvm/ADT/Statistic.h"
00022 #include "llvm/Analysis/AliasAnalysis.h"
00023 #include "llvm/Analysis/CaptureTracking.h"
00024 #include "llvm/Analysis/GlobalsModRef.h"
00025 #include "llvm/Analysis/MemoryBuiltins.h"
00026 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
00027 #include "llvm/Analysis/TargetLibraryInfo.h"
00028 #include "llvm/Analysis/ValueTracking.h"
00029 #include "llvm/IR/Constants.h"
00030 #include "llvm/IR/DataLayout.h"
00031 #include "llvm/IR/Dominators.h"
00032 #include "llvm/IR/Function.h"
00033 #include "llvm/IR/GlobalVariable.h"
00034 #include "llvm/IR/Instructions.h"
00035 #include "llvm/IR/IntrinsicInst.h"
00036 #include "llvm/Pass.h"
00037 #include "llvm/Support/Debug.h"
00038 #include "llvm/Support/raw_ostream.h"
00039 #include "llvm/Transforms/Utils/Local.h"
00040 using namespace llvm;
00041 
00042 #define DEBUG_TYPE "dse"
00043 
00044 STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
00045 STATISTIC(NumFastStores, "Number of stores deleted");
00046 STATISTIC(NumFastOther , "Number of other instrs removed");
00047 
00048 namespace {
00049   struct DSE : public FunctionPass {
00050     AliasAnalysis *AA;
00051     MemoryDependenceAnalysis *MD;
00052     DominatorTree *DT;
00053     const TargetLibraryInfo *TLI;
00054 
00055     static char ID; // Pass identification, replacement for typeid
00056     DSE() : FunctionPass(ID), AA(nullptr), MD(nullptr), DT(nullptr) {
00057       initializeDSEPass(*PassRegistry::getPassRegistry());
00058     }
00059 
00060     bool runOnFunction(Function &F) override {
00061       if (skipOptnoneFunction(F))
00062         return false;
00063 
00064       AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
00065       MD = &getAnalysis<MemoryDependenceAnalysis>();
00066       DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
00067       TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
00068 
00069       bool Changed = false;
00070       for (BasicBlock &I : F)
00071         // Only check non-dead blocks.  Dead blocks may have strange pointer
00072         // cycles that will confuse alias analysis.
00073         if (DT->isReachableFromEntry(&I))
00074           Changed |= runOnBasicBlock(I);
00075 
00076       AA = nullptr; MD = nullptr; DT = nullptr;
00077       return Changed;
00078     }
00079 
00080     bool runOnBasicBlock(BasicBlock &BB);
00081     bool MemoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI);
00082     bool HandleFree(CallInst *F);
00083     bool handleEndBlock(BasicBlock &BB);
00084     void RemoveAccessedObjects(const MemoryLocation &LoadedLoc,
00085                                SmallSetVector<Value *, 16> &DeadStackObjects,
00086                                const DataLayout &DL);
00087 
00088     void getAnalysisUsage(AnalysisUsage &AU) const override {
00089       AU.setPreservesCFG();
00090       AU.addRequired<DominatorTreeWrapperPass>();
00091       AU.addRequired<AAResultsWrapperPass>();
00092       AU.addRequired<MemoryDependenceAnalysis>();
00093       AU.addRequired<TargetLibraryInfoWrapperPass>();
00094       AU.addPreserved<DominatorTreeWrapperPass>();
00095       AU.addPreserved<GlobalsAAWrapperPass>();
00096       AU.addPreserved<MemoryDependenceAnalysis>();
00097     }
00098   };
00099 }
00100 
00101 char DSE::ID = 0;
00102 INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false)
00103 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
00104 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
00105 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
00106 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
00107 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
00108 INITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false)
00109 
00110 FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
00111 
00112 //===----------------------------------------------------------------------===//
00113 // Helper functions
00114 //===----------------------------------------------------------------------===//
00115 
00116 /// DeleteDeadInstruction - Delete this instruction.  Before we do, go through
00117 /// and zero out all the operands of this instruction.  If any of them become
00118 /// dead, delete them and the computation tree that feeds them.
00119 ///
00120 /// If ValueSet is non-null, remove any deleted instructions from it as well.
00121 ///
00122 static void DeleteDeadInstruction(Instruction *I,
00123                                MemoryDependenceAnalysis &MD,
00124                                const TargetLibraryInfo &TLI,
00125                                SmallSetVector<Value*, 16> *ValueSet = nullptr) {
00126   SmallVector<Instruction*, 32> NowDeadInsts;
00127 
00128   NowDeadInsts.push_back(I);
00129   --NumFastOther;
00130 
00131   // Before we touch this instruction, remove it from memdep!
00132   do {
00133     Instruction *DeadInst = NowDeadInsts.pop_back_val();
00134     ++NumFastOther;
00135 
00136     // This instruction is dead, zap it, in stages.  Start by removing it from
00137     // MemDep, which needs to know the operands and needs it to be in the
00138     // function.
00139     MD.removeInstruction(DeadInst);
00140 
00141     for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
00142       Value *Op = DeadInst->getOperand(op);
00143       DeadInst->setOperand(op, nullptr);
00144 
00145       // If this operand just became dead, add it to the NowDeadInsts list.
00146       if (!Op->use_empty()) continue;
00147 
00148       if (Instruction *OpI = dyn_cast<Instruction>(Op))
00149         if (isInstructionTriviallyDead(OpI, &TLI))
00150           NowDeadInsts.push_back(OpI);
00151     }
00152 
00153     DeadInst->eraseFromParent();
00154 
00155     if (ValueSet) ValueSet->remove(DeadInst);
00156   } while (!NowDeadInsts.empty());
00157 }
00158 
00159 
00160 /// hasMemoryWrite - Does this instruction write some memory?  This only returns
00161 /// true for things that we can analyze with other helpers below.
00162 static bool hasMemoryWrite(Instruction *I, const TargetLibraryInfo &TLI) {
00163   if (isa<StoreInst>(I))
00164     return true;
00165   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
00166     switch (II->getIntrinsicID()) {
00167     default:
00168       return false;
00169     case Intrinsic::memset:
00170     case Intrinsic::memmove:
00171     case Intrinsic::memcpy:
00172     case Intrinsic::init_trampoline:
00173     case Intrinsic::lifetime_end:
00174       return true;
00175     }
00176   }
00177   if (auto CS = CallSite(I)) {
00178     if (Function *F = CS.getCalledFunction()) {
00179       if (TLI.has(LibFunc::strcpy) &&
00180           F->getName() == TLI.getName(LibFunc::strcpy)) {
00181         return true;
00182       }
00183       if (TLI.has(LibFunc::strncpy) &&
00184           F->getName() == TLI.getName(LibFunc::strncpy)) {
00185         return true;
00186       }
00187       if (TLI.has(LibFunc::strcat) &&
00188           F->getName() == TLI.getName(LibFunc::strcat)) {
00189         return true;
00190       }
00191       if (TLI.has(LibFunc::strncat) &&
00192           F->getName() == TLI.getName(LibFunc::strncat)) {
00193         return true;
00194       }
00195     }
00196   }
00197   return false;
00198 }
00199 
00200 /// getLocForWrite - Return a Location stored to by the specified instruction.
00201 /// If isRemovable returns true, this function and getLocForRead completely
00202 /// describe the memory operations for this instruction.
00203 static MemoryLocation getLocForWrite(Instruction *Inst, AliasAnalysis &AA) {
00204   if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
00205     return MemoryLocation::get(SI);
00206 
00207   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) {
00208     // memcpy/memmove/memset.
00209     MemoryLocation Loc = MemoryLocation::getForDest(MI);
00210     return Loc;
00211   }
00212 
00213   IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst);
00214   if (!II)
00215     return MemoryLocation();
00216 
00217   switch (II->getIntrinsicID()) {
00218   default:
00219     return MemoryLocation(); // Unhandled intrinsic.
00220   case Intrinsic::init_trampoline:
00221     // FIXME: We don't know the size of the trampoline, so we can't really
00222     // handle it here.
00223     return MemoryLocation(II->getArgOperand(0));
00224   case Intrinsic::lifetime_end: {
00225     uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
00226     return MemoryLocation(II->getArgOperand(1), Len);
00227   }
00228   }
00229 }
00230 
00231 /// getLocForRead - Return the location read by the specified "hasMemoryWrite"
00232 /// instruction if any.
00233 static MemoryLocation getLocForRead(Instruction *Inst,
00234                                     const TargetLibraryInfo &TLI) {
00235   assert(hasMemoryWrite(Inst, TLI) && "Unknown instruction case");
00236 
00237   // The only instructions that both read and write are the mem transfer
00238   // instructions (memcpy/memmove).
00239   if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(Inst))
00240     return MemoryLocation::getForSource(MTI);
00241   return MemoryLocation();
00242 }
00243 
00244 
00245 /// isRemovable - If the value of this instruction and the memory it writes to
00246 /// is unused, may we delete this instruction?
00247 static bool isRemovable(Instruction *I) {
00248   // Don't remove volatile/atomic stores.
00249   if (StoreInst *SI = dyn_cast<StoreInst>(I))
00250     return SI->isUnordered();
00251 
00252   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
00253     switch (II->getIntrinsicID()) {
00254     default: llvm_unreachable("doesn't pass 'hasMemoryWrite' predicate");
00255     case Intrinsic::lifetime_end:
00256       // Never remove dead lifetime_end's, e.g. because it is followed by a
00257       // free.
00258       return false;
00259     case Intrinsic::init_trampoline:
00260       // Always safe to remove init_trampoline.
00261       return true;
00262 
00263     case Intrinsic::memset:
00264     case Intrinsic::memmove:
00265     case Intrinsic::memcpy:
00266       // Don't remove volatile memory intrinsics.
00267       return !cast<MemIntrinsic>(II)->isVolatile();
00268     }
00269   }
00270 
00271   if (auto CS = CallSite(I))
00272     return CS.getInstruction()->use_empty();
00273 
00274   return false;
00275 }
00276 
00277 
00278 /// isShortenable - Returns true if this instruction can be safely shortened in
00279 /// length.
00280 static bool isShortenable(Instruction *I) {
00281   // Don't shorten stores for now
00282   if (isa<StoreInst>(I))
00283     return false;
00284 
00285   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
00286     switch (II->getIntrinsicID()) {
00287       default: return false;
00288       case Intrinsic::memset:
00289       case Intrinsic::memcpy:
00290         // Do shorten memory intrinsics.
00291         return true;
00292     }
00293   }
00294 
00295   // Don't shorten libcalls calls for now.
00296 
00297   return false;
00298 }
00299 
00300 /// getStoredPointerOperand - Return the pointer that is being written to.
00301 static Value *getStoredPointerOperand(Instruction *I) {
00302   if (StoreInst *SI = dyn_cast<StoreInst>(I))
00303     return SI->getPointerOperand();
00304   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
00305     return MI->getDest();
00306 
00307   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
00308     switch (II->getIntrinsicID()) {
00309     default: llvm_unreachable("Unexpected intrinsic!");
00310     case Intrinsic::init_trampoline:
00311       return II->getArgOperand(0);
00312     }
00313   }
00314 
00315   CallSite CS(I);
00316   // All the supported functions so far happen to have dest as their first
00317   // argument.
00318   return CS.getArgument(0);
00319 }
00320 
00321 static uint64_t getPointerSize(const Value *V, const DataLayout &DL,
00322                                const TargetLibraryInfo &TLI) {
00323   uint64_t Size;
00324   if (getObjectSize(V, Size, DL, &TLI))
00325     return Size;
00326   return MemoryLocation::UnknownSize;
00327 }
00328 
00329 namespace {
00330   enum OverwriteResult
00331   {
00332     OverwriteComplete,
00333     OverwriteEnd,
00334     OverwriteUnknown
00335   };
00336 }
00337 
00338 /// isOverwrite - Return 'OverwriteComplete' if a store to the 'Later' location
00339 /// completely overwrites a store to the 'Earlier' location.
00340 /// 'OverwriteEnd' if the end of the 'Earlier' location is completely
00341 /// overwritten by 'Later', or 'OverwriteUnknown' if nothing can be determined
00342 static OverwriteResult isOverwrite(const MemoryLocation &Later,
00343                                    const MemoryLocation &Earlier,
00344                                    const DataLayout &DL,
00345                                    const TargetLibraryInfo &TLI,
00346                                    int64_t &EarlierOff, int64_t &LaterOff) {
00347   const Value *P1 = Earlier.Ptr->stripPointerCasts();
00348   const Value *P2 = Later.Ptr->stripPointerCasts();
00349 
00350   // If the start pointers are the same, we just have to compare sizes to see if
00351   // the later store was larger than the earlier store.
00352   if (P1 == P2) {
00353     // If we don't know the sizes of either access, then we can't do a
00354     // comparison.
00355     if (Later.Size == MemoryLocation::UnknownSize ||
00356         Earlier.Size == MemoryLocation::UnknownSize)
00357       return OverwriteUnknown;
00358 
00359     // Make sure that the Later size is >= the Earlier size.
00360     if (Later.Size >= Earlier.Size)
00361       return OverwriteComplete;
00362   }
00363 
00364   // Otherwise, we have to have size information, and the later store has to be
00365   // larger than the earlier one.
00366   if (Later.Size == MemoryLocation::UnknownSize ||
00367       Earlier.Size == MemoryLocation::UnknownSize)
00368     return OverwriteUnknown;
00369 
00370   // Check to see if the later store is to the entire object (either a global,
00371   // an alloca, or a byval/inalloca argument).  If so, then it clearly
00372   // overwrites any other store to the same object.
00373   const Value *UO1 = GetUnderlyingObject(P1, DL),
00374               *UO2 = GetUnderlyingObject(P2, DL);
00375 
00376   // If we can't resolve the same pointers to the same object, then we can't
00377   // analyze them at all.
00378   if (UO1 != UO2)
00379     return OverwriteUnknown;
00380 
00381   // If the "Later" store is to a recognizable object, get its size.
00382   uint64_t ObjectSize = getPointerSize(UO2, DL, TLI);
00383   if (ObjectSize != MemoryLocation::UnknownSize)
00384     if (ObjectSize == Later.Size && ObjectSize >= Earlier.Size)
00385       return OverwriteComplete;
00386 
00387   // Okay, we have stores to two completely different pointers.  Try to
00388   // decompose the pointer into a "base + constant_offset" form.  If the base
00389   // pointers are equal, then we can reason about the two stores.
00390   EarlierOff = 0;
00391   LaterOff = 0;
00392   const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);
00393   const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL);
00394 
00395   // If the base pointers still differ, we have two completely different stores.
00396   if (BP1 != BP2)
00397     return OverwriteUnknown;
00398 
00399   // The later store completely overlaps the earlier store if:
00400   //
00401   // 1. Both start at the same offset and the later one's size is greater than
00402   //    or equal to the earlier one's, or
00403   //
00404   //      |--earlier--|
00405   //      |--   later   --|
00406   //
00407   // 2. The earlier store has an offset greater than the later offset, but which
00408   //    still lies completely within the later store.
00409   //
00410   //        |--earlier--|
00411   //    |-----  later  ------|
00412   //
00413   // We have to be careful here as *Off is signed while *.Size is unsigned.
00414   if (EarlierOff >= LaterOff &&
00415       Later.Size >= Earlier.Size &&
00416       uint64_t(EarlierOff - LaterOff) + Earlier.Size <= Later.Size)
00417     return OverwriteComplete;
00418 
00419   // The other interesting case is if the later store overwrites the end of
00420   // the earlier store
00421   //
00422   //      |--earlier--|
00423   //                |--   later   --|
00424   //
00425   // In this case we may want to trim the size of earlier to avoid generating
00426   // writes to addresses which will definitely be overwritten later
00427   if (LaterOff > EarlierOff &&
00428       LaterOff < int64_t(EarlierOff + Earlier.Size) &&
00429       int64_t(LaterOff + Later.Size) >= int64_t(EarlierOff + Earlier.Size))
00430     return OverwriteEnd;
00431 
00432   // Otherwise, they don't completely overlap.
00433   return OverwriteUnknown;
00434 }
00435 
00436 /// isPossibleSelfRead - If 'Inst' might be a self read (i.e. a noop copy of a
00437 /// memory region into an identical pointer) then it doesn't actually make its
00438 /// input dead in the traditional sense.  Consider this case:
00439 ///
00440 ///   memcpy(A <- B)
00441 ///   memcpy(A <- A)
00442 ///
00443 /// In this case, the second store to A does not make the first store to A dead.
00444 /// The usual situation isn't an explicit A<-A store like this (which can be
00445 /// trivially removed) but a case where two pointers may alias.
00446 ///
00447 /// This function detects when it is unsafe to remove a dependent instruction
00448 /// because the DSE inducing instruction may be a self-read.
00449 static bool isPossibleSelfRead(Instruction *Inst,
00450                                const MemoryLocation &InstStoreLoc,
00451                                Instruction *DepWrite,
00452                                const TargetLibraryInfo &TLI,
00453                                AliasAnalysis &AA) {
00454   // Self reads can only happen for instructions that read memory.  Get the
00455   // location read.
00456   MemoryLocation InstReadLoc = getLocForRead(Inst, TLI);
00457   if (!InstReadLoc.Ptr) return false;  // Not a reading instruction.
00458 
00459   // If the read and written loc obviously don't alias, it isn't a read.
00460   if (AA.isNoAlias(InstReadLoc, InstStoreLoc)) return false;
00461 
00462   // Okay, 'Inst' may copy over itself.  However, we can still remove a the
00463   // DepWrite instruction if we can prove that it reads from the same location
00464   // as Inst.  This handles useful cases like:
00465   //   memcpy(A <- B)
00466   //   memcpy(A <- B)
00467   // Here we don't know if A/B may alias, but we do know that B/B are must
00468   // aliases, so removing the first memcpy is safe (assuming it writes <= #
00469   // bytes as the second one.
00470   MemoryLocation DepReadLoc = getLocForRead(DepWrite, TLI);
00471 
00472   if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr))
00473     return false;
00474 
00475   // If DepWrite doesn't read memory or if we can't prove it is a must alias,
00476   // then it can't be considered dead.
00477   return true;
00478 }
00479 
00480 
00481 //===----------------------------------------------------------------------===//
00482 // DSE Pass
00483 //===----------------------------------------------------------------------===//
00484 
00485 bool DSE::runOnBasicBlock(BasicBlock &BB) {
00486   const DataLayout &DL = BB.getModule()->getDataLayout();
00487   bool MadeChange = false;
00488 
00489   // Do a top-down walk on the BB.
00490   for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
00491     Instruction *Inst = &*BBI++;
00492 
00493     // Handle 'free' calls specially.
00494     if (CallInst *F = isFreeCall(Inst, TLI)) {
00495       MadeChange |= HandleFree(F);
00496       continue;
00497     }
00498 
00499     // If we find something that writes memory, get its memory dependence.
00500     if (!hasMemoryWrite(Inst, *TLI))
00501       continue;
00502 
00503     // If we're storing the same value back to a pointer that we just
00504     // loaded from, then the store can be removed.
00505     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
00506 
00507       auto RemoveDeadInstAndUpdateBBI = [&](Instruction *DeadInst) {
00508         // DeleteDeadInstruction can delete the current instruction.  Save BBI
00509         // in case we need it.
00510         WeakVH NextInst(&*BBI);
00511 
00512         DeleteDeadInstruction(DeadInst, *MD, *TLI);
00513 
00514         if (!NextInst) // Next instruction deleted.
00515           BBI = BB.begin();
00516         else if (BBI != BB.begin()) // Revisit this instruction if possible.
00517           --BBI;
00518         ++NumRedundantStores;
00519         MadeChange = true;
00520       };
00521 
00522       if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
00523         if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
00524             isRemovable(SI) &&
00525             MemoryIsNotModifiedBetween(DepLoad, SI)) {
00526 
00527           DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n  "
00528                        << "LOAD: " << *DepLoad << "\n  STORE: " << *SI << '\n');
00529 
00530           RemoveDeadInstAndUpdateBBI(SI);
00531           continue;
00532         }
00533       }
00534 
00535       // Remove null stores into the calloc'ed objects
00536       Constant *StoredConstant = dyn_cast<Constant>(SI->getValueOperand());
00537 
00538       if (StoredConstant && StoredConstant->isNullValue() &&
00539           isRemovable(SI)) {
00540         Instruction *UnderlyingPointer = dyn_cast<Instruction>(
00541             GetUnderlyingObject(SI->getPointerOperand(), DL));
00542 
00543         if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
00544             MemoryIsNotModifiedBetween(UnderlyingPointer, SI)) {
00545           DEBUG(dbgs()
00546                 << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
00547                 << *Inst << "\n  OBJECT: " << *UnderlyingPointer << '\n');
00548 
00549           RemoveDeadInstAndUpdateBBI(SI);
00550           continue;
00551         }
00552       }
00553     }
00554 
00555     MemDepResult InstDep = MD->getDependency(Inst);
00556 
00557     // Ignore any store where we can't find a local dependence.
00558     // FIXME: cross-block DSE would be fun. :)
00559     if (!InstDep.isDef() && !InstDep.isClobber())
00560       continue;
00561 
00562     // Figure out what location is being stored to.
00563     MemoryLocation Loc = getLocForWrite(Inst, *AA);
00564 
00565     // If we didn't get a useful location, fail.
00566     if (!Loc.Ptr)
00567       continue;
00568 
00569     while (InstDep.isDef() || InstDep.isClobber()) {
00570       // Get the memory clobbered by the instruction we depend on.  MemDep will
00571       // skip any instructions that 'Loc' clearly doesn't interact with.  If we
00572       // end up depending on a may- or must-aliased load, then we can't optimize
00573       // away the store and we bail out.  However, if we depend on on something
00574       // that overwrites the memory location we *can* potentially optimize it.
00575       //
00576       // Find out what memory location the dependent instruction stores.
00577       Instruction *DepWrite = InstDep.getInst();
00578       MemoryLocation DepLoc = getLocForWrite(DepWrite, *AA);
00579       // If we didn't get a useful location, or if it isn't a size, bail out.
00580       if (!DepLoc.Ptr)
00581         break;
00582 
00583       // If we find a write that is a) removable (i.e., non-volatile), b) is
00584       // completely obliterated by the store to 'Loc', and c) which we know that
00585       // 'Inst' doesn't load from, then we can remove it.
00586       if (isRemovable(DepWrite) &&
00587           !isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)) {
00588         int64_t InstWriteOffset, DepWriteOffset;
00589         OverwriteResult OR =
00590             isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset, InstWriteOffset);
00591         if (OR == OverwriteComplete) {
00592           DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: "
00593                 << *DepWrite << "\n  KILLER: " << *Inst << '\n');
00594 
00595           // Delete the store and now-dead instructions that feed it.
00596           DeleteDeadInstruction(DepWrite, *MD, *TLI);
00597           ++NumFastStores;
00598           MadeChange = true;
00599 
00600           // DeleteDeadInstruction can delete the current instruction in loop
00601           // cases, reset BBI.
00602           BBI = Inst->getIterator();
00603           if (BBI != BB.begin())
00604             --BBI;
00605           break;
00606         } else if (OR == OverwriteEnd && isShortenable(DepWrite)) {
00607           // TODO: base this on the target vector size so that if the earlier
00608           // store was too small to get vector writes anyway then its likely
00609           // a good idea to shorten it
00610           // Power of 2 vector writes are probably always a bad idea to optimize
00611           // as any store/memset/memcpy is likely using vector instructions so
00612           // shortening it to not vector size is likely to be slower
00613           MemIntrinsic* DepIntrinsic = cast<MemIntrinsic>(DepWrite);
00614           unsigned DepWriteAlign = DepIntrinsic->getAlignment();
00615           if (llvm::isPowerOf2_64(InstWriteOffset) ||
00616               ((DepWriteAlign != 0) && InstWriteOffset % DepWriteAlign == 0)) {
00617 
00618             DEBUG(dbgs() << "DSE: Remove Dead Store:\n  OW END: "
00619                   << *DepWrite << "\n  KILLER (offset "
00620                   << InstWriteOffset << ", "
00621                   << DepLoc.Size << ")"
00622                   << *Inst << '\n');
00623 
00624             Value* DepWriteLength = DepIntrinsic->getLength();
00625             Value* TrimmedLength = ConstantInt::get(DepWriteLength->getType(),
00626                                                     InstWriteOffset -
00627                                                     DepWriteOffset);
00628             DepIntrinsic->setLength(TrimmedLength);
00629             MadeChange = true;
00630           }
00631         }
00632       }
00633 
00634       // If this is a may-aliased store that is clobbering the store value, we
00635       // can keep searching past it for another must-aliased pointer that stores
00636       // to the same location.  For example, in:
00637       //   store -> P
00638       //   store -> Q
00639       //   store -> P
00640       // we can remove the first store to P even though we don't know if P and Q
00641       // alias.
00642       if (DepWrite == &BB.front()) break;
00643 
00644       // Can't look past this instruction if it might read 'Loc'.
00645       if (AA->getModRefInfo(DepWrite, Loc) & MRI_Ref)
00646         break;
00647 
00648       InstDep = MD->getPointerDependencyFrom(Loc, false,
00649                                              DepWrite->getIterator(), &BB);
00650     }
00651   }
00652 
00653   // If this block ends in a return, unwind, or unreachable, all allocas are
00654   // dead at its end, which means stores to them are also dead.
00655   if (BB.getTerminator()->getNumSuccessors() == 0)
00656     MadeChange |= handleEndBlock(BB);
00657 
00658   return MadeChange;
00659 }
00660 
00661 /// Returns true if the memory which is accessed by the second instruction is not
00662 /// modified between the first and the second instruction.
00663 /// Precondition: Second instruction must be dominated by the first
00664 /// instruction.
00665 bool DSE::MemoryIsNotModifiedBetween(Instruction *FirstI,
00666                                      Instruction *SecondI) {
00667   SmallVector<BasicBlock *, 16> WorkList;
00668   SmallPtrSet<BasicBlock *, 8> Visited;
00669   BasicBlock::iterator FirstBBI(FirstI);
00670   ++FirstBBI;
00671   BasicBlock::iterator SecondBBI(SecondI);
00672   BasicBlock *FirstBB = FirstI->getParent();
00673   BasicBlock *SecondBB = SecondI->getParent();
00674   MemoryLocation MemLoc = MemoryLocation::get(SecondI);
00675 
00676   // Start checking the store-block.
00677   WorkList.push_back(SecondBB);
00678   bool isFirstBlock = true;
00679 
00680   // Check all blocks going backward until we reach the load-block.
00681   while (!WorkList.empty()) {
00682     BasicBlock *B = WorkList.pop_back_val();
00683 
00684     // Ignore instructions before LI if this is the FirstBB.
00685     BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
00686 
00687     BasicBlock::iterator EI;
00688     if (isFirstBlock) {
00689       // Ignore instructions after SI if this is the first visit of SecondBB.
00690       assert(B == SecondBB && "first block is not the store block");
00691       EI = SecondBBI;
00692       isFirstBlock = false;
00693     } else {
00694       // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
00695       // In this case we also have to look at instructions after SI.
00696       EI = B->end();
00697     }
00698     for (; BI != EI; ++BI) {
00699       Instruction *I = &*BI;
00700       if (I->mayWriteToMemory() && I != SecondI) {
00701         auto Res = AA->getModRefInfo(I, MemLoc);
00702         if (Res != MRI_NoModRef)
00703           return false;
00704       }
00705     }
00706     if (B != FirstBB) {
00707       assert(B != &FirstBB->getParent()->getEntryBlock() &&
00708           "Should not hit the entry block because SI must be dominated by LI");
00709       for (auto PredI = pred_begin(B), PE = pred_end(B); PredI != PE; ++PredI) {
00710         if (!Visited.insert(*PredI).second)
00711           continue;
00712         WorkList.push_back(*PredI);
00713       }
00714     }
00715   }
00716   return true;
00717 }
00718 
00719 /// Find all blocks that will unconditionally lead to the block BB and append
00720 /// them to F.
00721 static void FindUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks,
00722                                    BasicBlock *BB, DominatorTree *DT) {
00723   for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
00724     BasicBlock *Pred = *I;
00725     if (Pred == BB) continue;
00726     TerminatorInst *PredTI = Pred->getTerminator();
00727     if (PredTI->getNumSuccessors() != 1)
00728       continue;
00729 
00730     if (DT->isReachableFromEntry(Pred))
00731       Blocks.push_back(Pred);
00732   }
00733 }
00734 
00735 /// HandleFree - Handle frees of entire structures whose dependency is a store
00736 /// to a field of that structure.
00737 bool DSE::HandleFree(CallInst *F) {
00738   bool MadeChange = false;
00739 
00740   MemoryLocation Loc = MemoryLocation(F->getOperand(0));
00741   SmallVector<BasicBlock *, 16> Blocks;
00742   Blocks.push_back(F->getParent());
00743   const DataLayout &DL = F->getModule()->getDataLayout();
00744 
00745   while (!Blocks.empty()) {
00746     BasicBlock *BB = Blocks.pop_back_val();
00747     Instruction *InstPt = BB->getTerminator();
00748     if (BB == F->getParent()) InstPt = F;
00749 
00750     MemDepResult Dep =
00751         MD->getPointerDependencyFrom(Loc, false, InstPt->getIterator(), BB);
00752     while (Dep.isDef() || Dep.isClobber()) {
00753       Instruction *Dependency = Dep.getInst();
00754       if (!hasMemoryWrite(Dependency, *TLI) || !isRemovable(Dependency))
00755         break;
00756 
00757       Value *DepPointer =
00758           GetUnderlyingObject(getStoredPointerOperand(Dependency), DL);
00759 
00760       // Check for aliasing.
00761       if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
00762         break;
00763 
00764       auto Next = ++Dependency->getIterator();
00765 
00766       // DCE instructions only used to calculate that store
00767       DeleteDeadInstruction(Dependency, *MD, *TLI);
00768       ++NumFastStores;
00769       MadeChange = true;
00770 
00771       // Inst's old Dependency is now deleted. Compute the next dependency,
00772       // which may also be dead, as in
00773       //    s[0] = 0;
00774       //    s[1] = 0; // This has just been deleted.
00775       //    free(s);
00776       Dep = MD->getPointerDependencyFrom(Loc, false, Next, BB);
00777     }
00778 
00779     if (Dep.isNonLocal())
00780       FindUnconditionalPreds(Blocks, BB, DT);
00781   }
00782 
00783   return MadeChange;
00784 }
00785 
00786 /// handleEndBlock - Remove dead stores to stack-allocated locations in the
00787 /// function end block.  Ex:
00788 /// %A = alloca i32
00789 /// ...
00790 /// store i32 1, i32* %A
00791 /// ret void
00792 bool DSE::handleEndBlock(BasicBlock &BB) {
00793   bool MadeChange = false;
00794 
00795   // Keep track of all of the stack objects that are dead at the end of the
00796   // function.
00797   SmallSetVector<Value*, 16> DeadStackObjects;
00798 
00799   // Find all of the alloca'd pointers in the entry block.
00800   BasicBlock &Entry = BB.getParent()->front();
00801   for (Instruction &I : Entry) {
00802     if (isa<AllocaInst>(&I))
00803       DeadStackObjects.insert(&I);
00804 
00805     // Okay, so these are dead heap objects, but if the pointer never escapes
00806     // then it's leaked by this function anyways.
00807     else if (isAllocLikeFn(&I, TLI) && !PointerMayBeCaptured(&I, true, true))
00808       DeadStackObjects.insert(&I);
00809   }
00810 
00811   // Treat byval or inalloca arguments the same, stores to them are dead at the
00812   // end of the function.
00813   for (Argument &AI : BB.getParent()->args())
00814     if (AI.hasByValOrInAllocaAttr())
00815       DeadStackObjects.insert(&AI);
00816 
00817   const DataLayout &DL = BB.getModule()->getDataLayout();
00818 
00819   // Scan the basic block backwards
00820   for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
00821     --BBI;
00822 
00823     // If we find a store, check to see if it points into a dead stack value.
00824     if (hasMemoryWrite(&*BBI, *TLI) && isRemovable(&*BBI)) {
00825       // See through pointer-to-pointer bitcasts
00826       SmallVector<Value *, 4> Pointers;
00827       GetUnderlyingObjects(getStoredPointerOperand(&*BBI), Pointers, DL);
00828 
00829       // Stores to stack values are valid candidates for removal.
00830       bool AllDead = true;
00831       for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(),
00832            E = Pointers.end(); I != E; ++I)
00833         if (!DeadStackObjects.count(*I)) {
00834           AllDead = false;
00835           break;
00836         }
00837 
00838       if (AllDead) {
00839         Instruction *Dead = &*BBI++;
00840 
00841         DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
00842                      << *Dead << "\n  Objects: ";
00843               for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(),
00844                    E = Pointers.end(); I != E; ++I) {
00845                 dbgs() << **I;
00846                 if (std::next(I) != E)
00847                   dbgs() << ", ";
00848               }
00849               dbgs() << '\n');
00850 
00851         // DCE instructions only used to calculate that store.
00852         DeleteDeadInstruction(Dead, *MD, *TLI, &DeadStackObjects);
00853         ++NumFastStores;
00854         MadeChange = true;
00855         continue;
00856       }
00857     }
00858 
00859     // Remove any dead non-memory-mutating instructions.
00860     if (isInstructionTriviallyDead(&*BBI, TLI)) {
00861       Instruction *Inst = &*BBI++;
00862       DeleteDeadInstruction(Inst, *MD, *TLI, &DeadStackObjects);
00863       ++NumFastOther;
00864       MadeChange = true;
00865       continue;
00866     }
00867 
00868     if (isa<AllocaInst>(BBI)) {
00869       // Remove allocas from the list of dead stack objects; there can't be
00870       // any references before the definition.
00871       DeadStackObjects.remove(&*BBI);
00872       continue;
00873     }
00874 
00875     if (auto CS = CallSite(&*BBI)) {
00876       // Remove allocation function calls from the list of dead stack objects; 
00877       // there can't be any references before the definition.
00878       if (isAllocLikeFn(&*BBI, TLI))
00879         DeadStackObjects.remove(&*BBI);
00880 
00881       // If this call does not access memory, it can't be loading any of our
00882       // pointers.
00883       if (AA->doesNotAccessMemory(CS))
00884         continue;
00885 
00886       // If the call might load from any of our allocas, then any store above
00887       // the call is live.
00888       DeadStackObjects.remove_if([&](Value *I) {
00889         // See if the call site touches the value.
00890         ModRefInfo A = AA->getModRefInfo(CS, I, getPointerSize(I, DL, *TLI));
00891 
00892         return A == MRI_ModRef || A == MRI_Ref;
00893       });
00894 
00895       // If all of the allocas were clobbered by the call then we're not going
00896       // to find anything else to process.
00897       if (DeadStackObjects.empty())
00898         break;
00899 
00900       continue;
00901     }
00902 
00903     MemoryLocation LoadedLoc;
00904 
00905     // If we encounter a use of the pointer, it is no longer considered dead
00906     if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
00907       if (!L->isUnordered()) // Be conservative with atomic/volatile load
00908         break;
00909       LoadedLoc = MemoryLocation::get(L);
00910     } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
00911       LoadedLoc = MemoryLocation::get(V);
00912     } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) {
00913       LoadedLoc = MemoryLocation::getForSource(MTI);
00914     } else if (!BBI->mayReadFromMemory()) {
00915       // Instruction doesn't read memory.  Note that stores that weren't removed
00916       // above will hit this case.
00917       continue;
00918     } else {
00919       // Unknown inst; assume it clobbers everything.
00920       break;
00921     }
00922 
00923     // Remove any allocas from the DeadPointer set that are loaded, as this
00924     // makes any stores above the access live.
00925     RemoveAccessedObjects(LoadedLoc, DeadStackObjects, DL);
00926 
00927     // If all of the allocas were clobbered by the access then we're not going
00928     // to find anything else to process.
00929     if (DeadStackObjects.empty())
00930       break;
00931   }
00932 
00933   return MadeChange;
00934 }
00935 
00936 /// RemoveAccessedObjects - Check to see if the specified location may alias any
00937 /// of the stack objects in the DeadStackObjects set.  If so, they become live
00938 /// because the location is being loaded.
00939 void DSE::RemoveAccessedObjects(const MemoryLocation &LoadedLoc,
00940                                 SmallSetVector<Value *, 16> &DeadStackObjects,
00941                                 const DataLayout &DL) {
00942   const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr, DL);
00943 
00944   // A constant can't be in the dead pointer set.
00945   if (isa<Constant>(UnderlyingPointer))
00946     return;
00947 
00948   // If the kill pointer can be easily reduced to an alloca, don't bother doing
00949   // extraneous AA queries.
00950   if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) {
00951     DeadStackObjects.remove(const_cast<Value*>(UnderlyingPointer));
00952     return;
00953   }
00954 
00955   // Remove objects that could alias LoadedLoc.
00956   DeadStackObjects.remove_if([&](Value *I) {
00957     // See if the loaded location could alias the stack location.
00958     MemoryLocation StackLoc(I, getPointerSize(I, DL, *TLI));
00959     return !AA->isNoAlias(StackLoc, LoadedLoc);
00960   });
00961 }