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