LLVM  7.0.0svn
DeadStoreElimination.cpp
Go to the documentation of this file.
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 
19 #include "llvm/ADT/APInt.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/SetVector.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/ADT/StringRef.h"
35 #include "llvm/IR/Argument.h"
36 #include "llvm/IR/BasicBlock.h"
37 #include "llvm/IR/CallSite.h"
38 #include "llvm/IR/Constant.h"
39 #include "llvm/IR/Constants.h"
40 #include "llvm/IR/DataLayout.h"
41 #include "llvm/IR/Dominators.h"
42 #include "llvm/IR/Function.h"
43 #include "llvm/IR/InstrTypes.h"
44 #include "llvm/IR/Instruction.h"
45 #include "llvm/IR/Instructions.h"
46 #include "llvm/IR/IntrinsicInst.h"
47 #include "llvm/IR/Intrinsics.h"
48 #include "llvm/IR/LLVMContext.h"
49 #include "llvm/IR/Module.h"
50 #include "llvm/IR/PassManager.h"
51 #include "llvm/IR/Value.h"
52 #include "llvm/Pass.h"
53 #include "llvm/Support/Casting.h"
55 #include "llvm/Support/Debug.h"
59 #include "llvm/Transforms/Scalar.h"
60 #include <algorithm>
61 #include <cassert>
62 #include <cstddef>
63 #include <cstdint>
64 #include <iterator>
65 #include <map>
66 #include <utility>
67 
68 using namespace llvm;
69 
70 #define DEBUG_TYPE "dse"
71 
72 STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
73 STATISTIC(NumFastStores, "Number of stores deleted");
74 STATISTIC(NumFastOther , "Number of other instrs removed");
75 STATISTIC(NumCompletePartials, "Number of stores dead by later partials");
76 STATISTIC(NumModifiedStores, "Number of stores modified");
77 
78 static cl::opt<bool>
79 EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",
80  cl::init(true), cl::Hidden,
81  cl::desc("Enable partial-overwrite tracking in DSE"));
82 
83 static cl::opt<bool>
84 EnablePartialStoreMerging("enable-dse-partial-store-merging",
85  cl::init(true), cl::Hidden,
86  cl::desc("Enable partial store merging in DSE"));
87 
88 //===----------------------------------------------------------------------===//
89 // Helper functions
90 //===----------------------------------------------------------------------===//
91 using OverlapIntervalsTy = std::map<int64_t, int64_t>;
93 
94 /// Delete this instruction. Before we do, go through and zero out all the
95 /// operands of this instruction. If any of them become dead, delete them and
96 /// the computation tree that feeds them.
97 /// If ValueSet is non-null, remove any deleted instructions from it as well.
98 static void
102  DenseMap<Instruction*, size_t> *InstrOrdering,
103  SmallSetVector<Value *, 16> *ValueSet = nullptr) {
104  SmallVector<Instruction*, 32> NowDeadInsts;
105 
106  NowDeadInsts.push_back(I);
107  --NumFastOther;
108 
109  // Keeping the iterator straight is a pain, so we let this routine tell the
110  // caller what the next instruction is after we're done mucking about.
111  BasicBlock::iterator NewIter = *BBI;
112 
113  // Before we touch this instruction, remove it from memdep!
114  do {
115  Instruction *DeadInst = NowDeadInsts.pop_back_val();
116  ++NumFastOther;
117 
118  // Try to preserve debug information attached to the dead instruction.
119  salvageDebugInfo(*DeadInst);
120 
121  // This instruction is dead, zap it, in stages. Start by removing it from
122  // MemDep, which needs to know the operands and needs it to be in the
123  // function.
124  MD.removeInstruction(DeadInst);
125 
126  for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
127  Value *Op = DeadInst->getOperand(op);
128  DeadInst->setOperand(op, nullptr);
129 
130  // If this operand just became dead, add it to the NowDeadInsts list.
131  if (!Op->use_empty()) continue;
132 
133  if (Instruction *OpI = dyn_cast<Instruction>(Op))
134  if (isInstructionTriviallyDead(OpI, &TLI))
135  NowDeadInsts.push_back(OpI);
136  }
137 
138  if (ValueSet) ValueSet->remove(DeadInst);
139  InstrOrdering->erase(DeadInst);
140  IOL.erase(DeadInst);
141 
142  if (NewIter == DeadInst->getIterator())
143  NewIter = DeadInst->eraseFromParent();
144  else
145  DeadInst->eraseFromParent();
146  } while (!NowDeadInsts.empty());
147  *BBI = NewIter;
148 }
149 
150 /// Does this instruction write some memory? This only returns true for things
151 /// that we can analyze with other helpers below.
153  const TargetLibraryInfo &TLI) {
154  if (isa<StoreInst>(I))
155  return true;
156  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
157  switch (II->getIntrinsicID()) {
158  default:
159  return false;
160  case Intrinsic::memset:
161  case Intrinsic::memmove:
162  case Intrinsic::memcpy:
163  case Intrinsic::memcpy_element_unordered_atomic:
164  case Intrinsic::memmove_element_unordered_atomic:
165  case Intrinsic::memset_element_unordered_atomic:
166  case Intrinsic::init_trampoline:
167  case Intrinsic::lifetime_end:
168  return true;
169  }
170  }
171  if (auto CS = CallSite(I)) {
172  if (Function *F = CS.getCalledFunction()) {
173  StringRef FnName = F->getName();
174  if (TLI.has(LibFunc_strcpy) && FnName == TLI.getName(LibFunc_strcpy))
175  return true;
176  if (TLI.has(LibFunc_strncpy) && FnName == TLI.getName(LibFunc_strncpy))
177  return true;
178  if (TLI.has(LibFunc_strcat) && FnName == TLI.getName(LibFunc_strcat))
179  return true;
180  if (TLI.has(LibFunc_strncat) && FnName == TLI.getName(LibFunc_strncat))
181  return true;
182  }
183  }
184  return false;
185 }
186 
187 /// Return a Location stored to by the specified instruction. If isRemovable
188 /// returns true, this function and getLocForRead completely describe the memory
189 /// operations for this instruction.
191 
192  if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
193  return MemoryLocation::get(SI);
194 
195  if (auto *MI = dyn_cast<AnyMemIntrinsic>(Inst)) {
196  // memcpy/memmove/memset.
198  return Loc;
199  }
200 
201  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
202  switch (II->getIntrinsicID()) {
203  default:
204  return MemoryLocation(); // Unhandled intrinsic.
205  case Intrinsic::init_trampoline:
206  return MemoryLocation(II->getArgOperand(0));
207  case Intrinsic::lifetime_end: {
208  uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
209  return MemoryLocation(II->getArgOperand(1), Len);
210  }
211  }
212  }
213  if (auto CS = CallSite(Inst))
214  // All the supported TLI functions so far happen to have dest as their
215  // first argument.
216  return MemoryLocation(CS.getArgument(0));
217  return MemoryLocation();
218 }
219 
220 /// Return the location read by the specified "hasAnalyzableMemoryWrite"
221 /// instruction if any.
223  const TargetLibraryInfo &TLI) {
224  assert(hasAnalyzableMemoryWrite(Inst, TLI) && "Unknown instruction case");
225 
226  // The only instructions that both read and write are the mem transfer
227  // instructions (memcpy/memmove).
228  if (auto *MTI = dyn_cast<AnyMemTransferInst>(Inst))
229  return MemoryLocation::getForSource(MTI);
230  return MemoryLocation();
231 }
232 
233 /// If the value of this instruction and the memory it writes to is unused, may
234 /// we delete this instruction?
235 static bool isRemovable(Instruction *I) {
236  // Don't remove volatile/atomic stores.
237  if (StoreInst *SI = dyn_cast<StoreInst>(I))
238  return SI->isUnordered();
239 
240  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
241  switch (II->getIntrinsicID()) {
242  default: llvm_unreachable("doesn't pass 'hasAnalyzableMemoryWrite' predicate");
243  case Intrinsic::lifetime_end:
244  // Never remove dead lifetime_end's, e.g. because it is followed by a
245  // free.
246  return false;
247  case Intrinsic::init_trampoline:
248  // Always safe to remove init_trampoline.
249  return true;
250  case Intrinsic::memset:
251  case Intrinsic::memmove:
252  case Intrinsic::memcpy:
253  // Don't remove volatile memory intrinsics.
254  return !cast<MemIntrinsic>(II)->isVolatile();
255  case Intrinsic::memcpy_element_unordered_atomic:
256  case Intrinsic::memmove_element_unordered_atomic:
257  case Intrinsic::memset_element_unordered_atomic:
258  return true;
259  }
260  }
261 
262  // note: only get here for calls with analyzable writes - i.e. libcalls
263  if (auto CS = CallSite(I))
264  return CS.getInstruction()->use_empty();
265 
266  return false;
267 }
268 
269 /// Returns true if the end of this instruction can be safely shortened in
270 /// length.
272  // Don't shorten stores for now
273  if (isa<StoreInst>(I))
274  return false;
275 
276  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
277  switch (II->getIntrinsicID()) {
278  default: return false;
279  case Intrinsic::memset:
280  case Intrinsic::memcpy:
281  case Intrinsic::memcpy_element_unordered_atomic:
282  case Intrinsic::memset_element_unordered_atomic:
283  // Do shorten memory intrinsics.
284  // FIXME: Add memmove if it's also safe to transform.
285  return true;
286  }
287  }
288 
289  // Don't shorten libcalls calls for now.
290 
291  return false;
292 }
293 
294 /// Returns true if the beginning of this instruction can be safely shortened
295 /// in length.
297  // FIXME: Handle only memset for now. Supporting memcpy/memmove should be
298  // easily done by offsetting the source address.
299  return isa<AnyMemSetInst>(I);
300 }
301 
302 /// Return the pointer that is being written to.
304  //TODO: factor this to reuse getLocForWrite
306  assert(Loc.Ptr &&
307  "unable to find pointer written for analyzable instruction?");
308  // TODO: most APIs don't expect const Value *
309  return const_cast<Value*>(Loc.Ptr);
310 }
311 
312 static uint64_t getPointerSize(const Value *V, const DataLayout &DL,
313  const TargetLibraryInfo &TLI,
314  const Function *F) {
315  uint64_t Size;
316  ObjectSizeOpts Opts;
318 
319  if (getObjectSize(V, Size, DL, &TLI, Opts))
320  return Size;
322 }
323 
324 namespace {
325 
327  OW_Begin,
328  OW_Complete,
329  OW_End,
330  OW_PartialEarlierWithFullLater,
331  OW_Unknown
332 };
333 
334 } // end anonymous namespace
335 
336 /// Return 'OW_Complete' if a store to the 'Later' location completely
337 /// overwrites a store to the 'Earlier' location, 'OW_End' if the end of the
338 /// 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the
339 /// beginning of the 'Earlier' location is overwritten by 'Later'.
340 /// 'OW_PartialEarlierWithFullLater' means that an earlier (big) store was
341 /// overwritten by a latter (smaller) store which doesn't write outside the big
342 /// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.
344  const MemoryLocation &Earlier,
345  const DataLayout &DL,
346  const TargetLibraryInfo &TLI,
347  int64_t &EarlierOff, int64_t &LaterOff,
348  Instruction *DepWrite,
350  AliasAnalysis &AA,
351  const Function *F) {
352  // If we don't know the sizes of either access, then we can't do a comparison.
353  if (Later.Size == MemoryLocation::UnknownSize ||
355  return OW_Unknown;
356 
357  const Value *P1 = Earlier.Ptr->stripPointerCasts();
358  const Value *P2 = Later.Ptr->stripPointerCasts();
359 
360  // If the start pointers are the same, we just have to compare sizes to see if
361  // the later store was larger than the earlier store.
362  if (P1 == P2 || AA.isMustAlias(P1, P2)) {
363  // Make sure that the Later size is >= the Earlier size.
364  if (Later.Size >= Earlier.Size)
365  return OW_Complete;
366  }
367 
368  // Check to see if the later store is to the entire object (either a global,
369  // an alloca, or a byval/inalloca argument). If so, then it clearly
370  // overwrites any other store to the same object.
371  const Value *UO1 = GetUnderlyingObject(P1, DL),
372  *UO2 = GetUnderlyingObject(P2, DL);
373 
374  // If we can't resolve the same pointers to the same object, then we can't
375  // analyze them at all.
376  if (UO1 != UO2)
377  return OW_Unknown;
378 
379  // If the "Later" store is to a recognizable object, get its size.
380  uint64_t ObjectSize = getPointerSize(UO2, DL, TLI, F);
381  if (ObjectSize != MemoryLocation::UnknownSize)
382  if (ObjectSize == Later.Size && ObjectSize >= Earlier.Size)
383  return OW_Complete;
384 
385  // Okay, we have stores to two completely different pointers. Try to
386  // decompose the pointer into a "base + constant_offset" form. If the base
387  // pointers are equal, then we can reason about the two stores.
388  EarlierOff = 0;
389  LaterOff = 0;
390  const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);
391  const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL);
392 
393  // If the base pointers still differ, we have two completely different stores.
394  if (BP1 != BP2)
395  return OW_Unknown;
396 
397  // The later store completely overlaps the earlier store if:
398  //
399  // 1. Both start at the same offset and the later one's size is greater than
400  // or equal to the earlier one's, or
401  //
402  // |--earlier--|
403  // |-- later --|
404  //
405  // 2. The earlier store has an offset greater than the later offset, but which
406  // still lies completely within the later store.
407  //
408  // |--earlier--|
409  // |----- later ------|
410  //
411  // We have to be careful here as *Off is signed while *.Size is unsigned.
412  if (EarlierOff >= LaterOff &&
413  Later.Size >= Earlier.Size &&
414  uint64_t(EarlierOff - LaterOff) + Earlier.Size <= Later.Size)
415  return OW_Complete;
416 
417  // We may now overlap, although the overlap is not complete. There might also
418  // be other incomplete overlaps, and together, they might cover the complete
419  // earlier write.
420  // Note: The correctness of this logic depends on the fact that this function
421  // is not even called providing DepWrite when there are any intervening reads.
423  LaterOff < int64_t(EarlierOff + Earlier.Size) &&
424  int64_t(LaterOff + Later.Size) >= EarlierOff) {
425 
426  // Insert our part of the overlap into the map.
427  auto &IM = IOL[DepWrite];
428  LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: Earlier [" << EarlierOff
429  << ", " << int64_t(EarlierOff + Earlier.Size)
430  << ") Later [" << LaterOff << ", "
431  << int64_t(LaterOff + Later.Size) << ")\n");
432 
433  // Make sure that we only insert non-overlapping intervals and combine
434  // adjacent intervals. The intervals are stored in the map with the ending
435  // offset as the key (in the half-open sense) and the starting offset as
436  // the value.
437  int64_t LaterIntStart = LaterOff, LaterIntEnd = LaterOff + Later.Size;
438 
439  // Find any intervals ending at, or after, LaterIntStart which start
440  // before LaterIntEnd.
441  auto ILI = IM.lower_bound(LaterIntStart);
442  if (ILI != IM.end() && ILI->second <= LaterIntEnd) {
443  // This existing interval is overlapped with the current store somewhere
444  // in [LaterIntStart, LaterIntEnd]. Merge them by erasing the existing
445  // intervals and adjusting our start and end.
446  LaterIntStart = std::min(LaterIntStart, ILI->second);
447  LaterIntEnd = std::max(LaterIntEnd, ILI->first);
448  ILI = IM.erase(ILI);
449 
450  // Continue erasing and adjusting our end in case other previous
451  // intervals are also overlapped with the current store.
452  //
453  // |--- ealier 1 ---| |--- ealier 2 ---|
454  // |------- later---------|
455  //
456  while (ILI != IM.end() && ILI->second <= LaterIntEnd) {
457  assert(ILI->second > LaterIntStart && "Unexpected interval");
458  LaterIntEnd = std::max(LaterIntEnd, ILI->first);
459  ILI = IM.erase(ILI);
460  }
461  }
462 
463  IM[LaterIntEnd] = LaterIntStart;
464 
465  ILI = IM.begin();
466  if (ILI->second <= EarlierOff &&
467  ILI->first >= int64_t(EarlierOff + Earlier.Size)) {
468  LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: Earlier ["
469  << EarlierOff << ", "
470  << int64_t(EarlierOff + Earlier.Size)
471  << ") Composite Later [" << ILI->second << ", "
472  << ILI->first << ")\n");
473  ++NumCompletePartials;
474  return OW_Complete;
475  }
476  }
477 
478  // Check for an earlier store which writes to all the memory locations that
479  // the later store writes to.
480  if (EnablePartialStoreMerging && LaterOff >= EarlierOff &&
481  int64_t(EarlierOff + Earlier.Size) > LaterOff &&
482  uint64_t(LaterOff - EarlierOff) + Later.Size <= Earlier.Size) {
483  LLVM_DEBUG(dbgs() << "DSE: Partial overwrite an earlier load ["
484  << EarlierOff << ", "
485  << int64_t(EarlierOff + Earlier.Size)
486  << ") by a later store [" << LaterOff << ", "
487  << int64_t(LaterOff + Later.Size) << ")\n");
488  // TODO: Maybe come up with a better name?
489  return OW_PartialEarlierWithFullLater;
490  }
491 
492  // Another interesting case is if the later store overwrites the end of the
493  // earlier store.
494  //
495  // |--earlier--|
496  // |-- later --|
497  //
498  // In this case we may want to trim the size of earlier to avoid generating
499  // writes to addresses which will definitely be overwritten later
501  (LaterOff > EarlierOff && LaterOff < int64_t(EarlierOff + Earlier.Size) &&
502  int64_t(LaterOff + Later.Size) >= int64_t(EarlierOff + Earlier.Size)))
503  return OW_End;
504 
505  // Finally, we also need to check if the later store overwrites the beginning
506  // of the earlier store.
507  //
508  // |--earlier--|
509  // |-- later --|
510  //
511  // In this case we may want to move the destination address and trim the size
512  // of earlier to avoid generating writes to addresses which will definitely
513  // be overwritten later.
515  (LaterOff <= EarlierOff && int64_t(LaterOff + Later.Size) > EarlierOff)) {
516  assert(int64_t(LaterOff + Later.Size) <
517  int64_t(EarlierOff + Earlier.Size) &&
518  "Expect to be handled as OW_Complete");
519  return OW_Begin;
520  }
521  // Otherwise, they don't completely overlap.
522  return OW_Unknown;
523 }
524 
525 /// If 'Inst' might be a self read (i.e. a noop copy of a
526 /// memory region into an identical pointer) then it doesn't actually make its
527 /// input dead in the traditional sense. Consider this case:
528 ///
529 /// memmove(A <- B)
530 /// memmove(A <- A)
531 ///
532 /// In this case, the second store to A does not make the first store to A dead.
533 /// The usual situation isn't an explicit A<-A store like this (which can be
534 /// trivially removed) but a case where two pointers may alias.
535 ///
536 /// This function detects when it is unsafe to remove a dependent instruction
537 /// because the DSE inducing instruction may be a self-read.
538 static bool isPossibleSelfRead(Instruction *Inst,
539  const MemoryLocation &InstStoreLoc,
540  Instruction *DepWrite,
541  const TargetLibraryInfo &TLI,
542  AliasAnalysis &AA) {
543  // Self reads can only happen for instructions that read memory. Get the
544  // location read.
545  MemoryLocation InstReadLoc = getLocForRead(Inst, TLI);
546  if (!InstReadLoc.Ptr)
547  return false; // Not a reading instruction.
548 
549  // If the read and written loc obviously don't alias, it isn't a read.
550  if (AA.isNoAlias(InstReadLoc, InstStoreLoc))
551  return false;
552 
553  if (isa<AnyMemCpyInst>(Inst)) {
554  // LLVM's memcpy overlap semantics are not fully fleshed out (see PR11763)
555  // but in practice memcpy(A <- B) either means that A and B are disjoint or
556  // are equal (i.e. there are not partial overlaps). Given that, if we have:
557  //
558  // memcpy/memmove(A <- B) // DepWrite
559  // memcpy(A <- B) // Inst
560  //
561  // with Inst reading/writing a >= size than DepWrite, we can reason as
562  // follows:
563  //
564  // - If A == B then both the copies are no-ops, so the DepWrite can be
565  // removed.
566  // - If A != B then A and B are disjoint locations in Inst. Since
567  // Inst.size >= DepWrite.size A and B are disjoint in DepWrite too.
568  // Therefore DepWrite can be removed.
569  MemoryLocation DepReadLoc = getLocForRead(DepWrite, TLI);
570 
571  if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr))
572  return false;
573  }
574 
575  // If DepWrite doesn't read memory or if we can't prove it is a must alias,
576  // then it can't be considered dead.
577  return true;
578 }
579 
580 /// Returns true if the memory which is accessed by the second instruction is not
581 /// modified between the first and the second instruction.
582 /// Precondition: Second instruction must be dominated by the first
583 /// instruction.
585  Instruction *SecondI,
586  AliasAnalysis *AA) {
589  BasicBlock::iterator FirstBBI(FirstI);
590  ++FirstBBI;
591  BasicBlock::iterator SecondBBI(SecondI);
592  BasicBlock *FirstBB = FirstI->getParent();
593  BasicBlock *SecondBB = SecondI->getParent();
594  MemoryLocation MemLoc = MemoryLocation::get(SecondI);
595 
596  // Start checking the store-block.
597  WorkList.push_back(SecondBB);
598  bool isFirstBlock = true;
599 
600  // Check all blocks going backward until we reach the load-block.
601  while (!WorkList.empty()) {
602  BasicBlock *B = WorkList.pop_back_val();
603 
604  // Ignore instructions before LI if this is the FirstBB.
605  BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
606 
608  if (isFirstBlock) {
609  // Ignore instructions after SI if this is the first visit of SecondBB.
610  assert(B == SecondBB && "first block is not the store block");
611  EI = SecondBBI;
612  isFirstBlock = false;
613  } else {
614  // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
615  // In this case we also have to look at instructions after SI.
616  EI = B->end();
617  }
618  for (; BI != EI; ++BI) {
619  Instruction *I = &*BI;
620  if (I->mayWriteToMemory() && I != SecondI)
621  if (isModSet(AA->getModRefInfo(I, MemLoc)))
622  return false;
623  }
624  if (B != FirstBB) {
625  assert(B != &FirstBB->getParent()->getEntryBlock() &&
626  "Should not hit the entry block because SI must be dominated by LI");
627  for (auto PredI = pred_begin(B), PE = pred_end(B); PredI != PE; ++PredI) {
628  if (!Visited.insert(*PredI).second)
629  continue;
630  WorkList.push_back(*PredI);
631  }
632  }
633  }
634  return true;
635 }
636 
637 /// Find all blocks that will unconditionally lead to the block BB and append
638 /// them to F.
640  BasicBlock *BB, DominatorTree *DT) {
641  for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
642  BasicBlock *Pred = *I;
643  if (Pred == BB) continue;
644  TerminatorInst *PredTI = Pred->getTerminator();
645  if (PredTI->getNumSuccessors() != 1)
646  continue;
647 
648  if (DT->isReachableFromEntry(Pred))
649  Blocks.push_back(Pred);
650  }
651 }
652 
653 /// Handle frees of entire structures whose dependency is a store
654 /// to a field of that structure.
655 static bool handleFree(CallInst *F, AliasAnalysis *AA,
657  const TargetLibraryInfo *TLI,
659  DenseMap<Instruction*, size_t> *InstrOrdering) {
660  bool MadeChange = false;
661 
664  Blocks.push_back(F->getParent());
665  const DataLayout &DL = F->getModule()->getDataLayout();
666 
667  while (!Blocks.empty()) {
668  BasicBlock *BB = Blocks.pop_back_val();
669  Instruction *InstPt = BB->getTerminator();
670  if (BB == F->getParent()) InstPt = F;
671 
672  MemDepResult Dep =
673  MD->getPointerDependencyFrom(Loc, false, InstPt->getIterator(), BB);
674  while (Dep.isDef() || Dep.isClobber()) {
675  Instruction *Dependency = Dep.getInst();
676  if (!hasAnalyzableMemoryWrite(Dependency, *TLI) ||
677  !isRemovable(Dependency))
678  break;
679 
680  Value *DepPointer =
682 
683  // Check for aliasing.
684  if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
685  break;
686 
687  LLVM_DEBUG(
688  dbgs() << "DSE: Dead Store to soon to be freed memory:\n DEAD: "
689  << *Dependency << '\n');
690 
691  // DCE instructions only used to calculate that store.
692  BasicBlock::iterator BBI(Dependency);
693  deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL, InstrOrdering);
694  ++NumFastStores;
695  MadeChange = true;
696 
697  // Inst's old Dependency is now deleted. Compute the next dependency,
698  // which may also be dead, as in
699  // s[0] = 0;
700  // s[1] = 0; // This has just been deleted.
701  // free(s);
702  Dep = MD->getPointerDependencyFrom(Loc, false, BBI, BB);
703  }
704 
705  if (Dep.isNonLocal())
706  findUnconditionalPreds(Blocks, BB, DT);
707  }
708 
709  return MadeChange;
710 }
711 
712 /// Check to see if the specified location may alias any of the stack objects in
713 /// the DeadStackObjects set. If so, they become live because the location is
714 /// being loaded.
715 static void removeAccessedObjects(const MemoryLocation &LoadedLoc,
716  SmallSetVector<Value *, 16> &DeadStackObjects,
717  const DataLayout &DL, AliasAnalysis *AA,
718  const TargetLibraryInfo *TLI,
719  const Function *F) {
720  const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr, DL);
721 
722  // A constant can't be in the dead pointer set.
723  if (isa<Constant>(UnderlyingPointer))
724  return;
725 
726  // If the kill pointer can be easily reduced to an alloca, don't bother doing
727  // extraneous AA queries.
728  if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) {
729  DeadStackObjects.remove(const_cast<Value*>(UnderlyingPointer));
730  return;
731  }
732 
733  // Remove objects that could alias LoadedLoc.
734  DeadStackObjects.remove_if([&](Value *I) {
735  // See if the loaded location could alias the stack location.
736  MemoryLocation StackLoc(I, getPointerSize(I, DL, *TLI, F));
737  return !AA->isNoAlias(StackLoc, LoadedLoc);
738  });
739 }
740 
741 /// Remove dead stores to stack-allocated locations in the function end block.
742 /// Ex:
743 /// %A = alloca i32
744 /// ...
745 /// store i32 1, i32* %A
746 /// ret void
749  const TargetLibraryInfo *TLI,
751  DenseMap<Instruction*, size_t> *InstrOrdering) {
752  bool MadeChange = false;
753 
754  // Keep track of all of the stack objects that are dead at the end of the
755  // function.
756  SmallSetVector<Value*, 16> DeadStackObjects;
757 
758  // Find all of the alloca'd pointers in the entry block.
759  BasicBlock &Entry = BB.getParent()->front();
760  for (Instruction &I : Entry) {
761  if (isa<AllocaInst>(&I))
762  DeadStackObjects.insert(&I);
763 
764  // Okay, so these are dead heap objects, but if the pointer never escapes
765  // then it's leaked by this function anyways.
766  else if (isAllocLikeFn(&I, TLI) && !PointerMayBeCaptured(&I, true, true))
767  DeadStackObjects.insert(&I);
768  }
769 
770  // Treat byval or inalloca arguments the same, stores to them are dead at the
771  // end of the function.
772  for (Argument &AI : BB.getParent()->args())
773  if (AI.hasByValOrInAllocaAttr())
774  DeadStackObjects.insert(&AI);
775 
776  const DataLayout &DL = BB.getModule()->getDataLayout();
777 
778  // Scan the basic block backwards
779  for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
780  --BBI;
781 
782  // If we find a store, check to see if it points into a dead stack value.
783  if (hasAnalyzableMemoryWrite(&*BBI, *TLI) && isRemovable(&*BBI)) {
784  // See through pointer-to-pointer bitcasts
785  SmallVector<Value *, 4> Pointers;
786  GetUnderlyingObjects(getStoredPointerOperand(&*BBI), Pointers, DL);
787 
788  // Stores to stack values are valid candidates for removal.
789  bool AllDead = true;
790  for (Value *Pointer : Pointers)
791  if (!DeadStackObjects.count(Pointer)) {
792  AllDead = false;
793  break;
794  }
795 
796  if (AllDead) {
797  Instruction *Dead = &*BBI;
798 
799  LLVM_DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
800  << *Dead << "\n Objects: ";
801  for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(),
802  E = Pointers.end();
803  I != E; ++I) {
804  dbgs() << **I;
805  if (std::next(I) != E)
806  dbgs() << ", ";
807  } dbgs()
808  << '\n');
809 
810  // DCE instructions only used to calculate that store.
811  deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, InstrOrdering, &DeadStackObjects);
812  ++NumFastStores;
813  MadeChange = true;
814  continue;
815  }
816  }
817 
818  // Remove any dead non-memory-mutating instructions.
819  if (isInstructionTriviallyDead(&*BBI, TLI)) {
820  LLVM_DEBUG(dbgs() << "DSE: Removing trivially dead instruction:\n DEAD: "
821  << *&*BBI << '\n');
822  deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, InstrOrdering, &DeadStackObjects);
823  ++NumFastOther;
824  MadeChange = true;
825  continue;
826  }
827 
828  if (isa<AllocaInst>(BBI)) {
829  // Remove allocas from the list of dead stack objects; there can't be
830  // any references before the definition.
831  DeadStackObjects.remove(&*BBI);
832  continue;
833  }
834 
835  if (auto CS = CallSite(&*BBI)) {
836  // Remove allocation function calls from the list of dead stack objects;
837  // there can't be any references before the definition.
838  if (isAllocLikeFn(&*BBI, TLI))
839  DeadStackObjects.remove(&*BBI);
840 
841  // If this call does not access memory, it can't be loading any of our
842  // pointers.
843  if (AA->doesNotAccessMemory(CS))
844  continue;
845 
846  // If the call might load from any of our allocas, then any store above
847  // the call is live.
848  DeadStackObjects.remove_if([&](Value *I) {
849  // See if the call site touches the value.
850  return isRefSet(AA->getModRefInfo(CS, I, getPointerSize(I, DL, *TLI,
851  BB.getParent())));
852  });
853 
854  // If all of the allocas were clobbered by the call then we're not going
855  // to find anything else to process.
856  if (DeadStackObjects.empty())
857  break;
858 
859  continue;
860  }
861 
862  // We can remove the dead stores, irrespective of the fence and its ordering
863  // (release/acquire/seq_cst). Fences only constraints the ordering of
864  // already visible stores, it does not make a store visible to other
865  // threads. So, skipping over a fence does not change a store from being
866  // dead.
867  if (isa<FenceInst>(*BBI))
868  continue;
869 
870  MemoryLocation LoadedLoc;
871 
872  // If we encounter a use of the pointer, it is no longer considered dead
873  if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
874  if (!L->isUnordered()) // Be conservative with atomic/volatile load
875  break;
876  LoadedLoc = MemoryLocation::get(L);
877  } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
878  LoadedLoc = MemoryLocation::get(V);
879  } else if (!BBI->mayReadFromMemory()) {
880  // Instruction doesn't read memory. Note that stores that weren't removed
881  // above will hit this case.
882  continue;
883  } else {
884  // Unknown inst; assume it clobbers everything.
885  break;
886  }
887 
888  // Remove any allocas from the DeadPointer set that are loaded, as this
889  // makes any stores above the access live.
890  removeAccessedObjects(LoadedLoc, DeadStackObjects, DL, AA, TLI, BB.getParent());
891 
892  // If all of the allocas were clobbered by the access then we're not going
893  // to find anything else to process.
894  if (DeadStackObjects.empty())
895  break;
896  }
897 
898  return MadeChange;
899 }
900 
901 static bool tryToShorten(Instruction *EarlierWrite, int64_t &EarlierOffset,
902  int64_t &EarlierSize, int64_t LaterOffset,
903  int64_t LaterSize, bool IsOverwriteEnd) {
904  // TODO: base this on the target vector size so that if the earlier
905  // store was too small to get vector writes anyway then its likely
906  // a good idea to shorten it
907  // Power of 2 vector writes are probably always a bad idea to optimize
908  // as any store/memset/memcpy is likely using vector instructions so
909  // shortening it to not vector size is likely to be slower
910  auto *EarlierIntrinsic = cast<AnyMemIntrinsic>(EarlierWrite);
911  unsigned EarlierWriteAlign = EarlierIntrinsic->getDestAlignment();
912  if (!IsOverwriteEnd)
913  LaterOffset = int64_t(LaterOffset + LaterSize);
914 
915  if (!(isPowerOf2_64(LaterOffset) && EarlierWriteAlign <= LaterOffset) &&
916  !((EarlierWriteAlign != 0) && LaterOffset % EarlierWriteAlign == 0))
917  return false;
918 
919  int64_t NewLength = IsOverwriteEnd
920  ? LaterOffset - EarlierOffset
921  : EarlierSize - (LaterOffset - EarlierOffset);
922 
923  if (auto *AMI = dyn_cast<AtomicMemIntrinsic>(EarlierWrite)) {
924  // When shortening an atomic memory intrinsic, the newly shortened
925  // length must remain an integer multiple of the element size.
926  const uint32_t ElementSize = AMI->getElementSizeInBytes();
927  if (0 != NewLength % ElementSize)
928  return false;
929  }
930 
931  LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW "
932  << (IsOverwriteEnd ? "END" : "BEGIN") << ": "
933  << *EarlierWrite << "\n KILLER (offset " << LaterOffset
934  << ", " << EarlierSize << ")\n");
935 
936  Value *EarlierWriteLength = EarlierIntrinsic->getLength();
937  Value *TrimmedLength =
938  ConstantInt::get(EarlierWriteLength->getType(), NewLength);
939  EarlierIntrinsic->setLength(TrimmedLength);
940 
941  EarlierSize = NewLength;
942  if (!IsOverwriteEnd) {
943  int64_t OffsetMoved = (LaterOffset - EarlierOffset);
944  Value *Indices[1] = {
945  ConstantInt::get(EarlierWriteLength->getType(), OffsetMoved)};
947  EarlierIntrinsic->getRawDest(), Indices, "", EarlierWrite);
948  EarlierIntrinsic->setDest(NewDestGEP);
949  EarlierOffset = EarlierOffset + OffsetMoved;
950  }
951  return true;
952 }
953 
954 static bool tryToShortenEnd(Instruction *EarlierWrite,
956  int64_t &EarlierStart, int64_t &EarlierSize) {
957  if (IntervalMap.empty() || !isShortenableAtTheEnd(EarlierWrite))
958  return false;
959 
960  OverlapIntervalsTy::iterator OII = --IntervalMap.end();
961  int64_t LaterStart = OII->second;
962  int64_t LaterSize = OII->first - LaterStart;
963 
964  if (LaterStart > EarlierStart && LaterStart < EarlierStart + EarlierSize &&
965  LaterStart + LaterSize >= EarlierStart + EarlierSize) {
966  if (tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,
967  LaterSize, true)) {
968  IntervalMap.erase(OII);
969  return true;
970  }
971  }
972  return false;
973 }
974 
975 static bool tryToShortenBegin(Instruction *EarlierWrite,
977  int64_t &EarlierStart, int64_t &EarlierSize) {
978  if (IntervalMap.empty() || !isShortenableAtTheBeginning(EarlierWrite))
979  return false;
980 
981  OverlapIntervalsTy::iterator OII = IntervalMap.begin();
982  int64_t LaterStart = OII->second;
983  int64_t LaterSize = OII->first - LaterStart;
984 
985  if (LaterStart <= EarlierStart && LaterStart + LaterSize > EarlierStart) {
986  assert(LaterStart + LaterSize < EarlierStart + EarlierSize &&
987  "Should have been handled as OW_Complete");
988  if (tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,
989  LaterSize, false)) {
990  IntervalMap.erase(OII);
991  return true;
992  }
993  }
994  return false;
995 }
996 
998  const DataLayout &DL,
999  InstOverlapIntervalsTy &IOL) {
1000  bool Changed = false;
1001  for (auto OI : IOL) {
1002  Instruction *EarlierWrite = OI.first;
1003  MemoryLocation Loc = getLocForWrite(EarlierWrite);
1004  assert(isRemovable(EarlierWrite) && "Expect only removable instruction");
1005  assert(Loc.Size != MemoryLocation::UnknownSize && "Unexpected mem loc");
1006 
1007  const Value *Ptr = Loc.Ptr->stripPointerCasts();
1008  int64_t EarlierStart = 0;
1009  int64_t EarlierSize = int64_t(Loc.Size);
1010  GetPointerBaseWithConstantOffset(Ptr, EarlierStart, DL);
1011  OverlapIntervalsTy &IntervalMap = OI.second;
1012  Changed |=
1013  tryToShortenEnd(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
1014  if (IntervalMap.empty())
1015  continue;
1016  Changed |=
1017  tryToShortenBegin(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
1018  }
1019  return Changed;
1020 }
1021 
1024  const DataLayout &DL,
1025  const TargetLibraryInfo *TLI,
1027  DenseMap<Instruction*, size_t> *InstrOrdering) {
1028  // Must be a store instruction.
1029  StoreInst *SI = dyn_cast<StoreInst>(Inst);
1030  if (!SI)
1031  return false;
1032 
1033  // If we're storing the same value back to a pointer that we just loaded from,
1034  // then the store can be removed.
1035  if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
1036  if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
1037  isRemovable(SI) && memoryIsNotModifiedBetween(DepLoad, SI, AA)) {
1038 
1039  LLVM_DEBUG(
1040  dbgs() << "DSE: Remove Store Of Load from same pointer:\n LOAD: "
1041  << *DepLoad << "\n STORE: " << *SI << '\n');
1042 
1043  deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, InstrOrdering);
1044  ++NumRedundantStores;
1045  return true;
1046  }
1047  }
1048 
1049  // Remove null stores into the calloc'ed objects
1050  Constant *StoredConstant = dyn_cast<Constant>(SI->getValueOperand());
1051  if (StoredConstant && StoredConstant->isNullValue() && isRemovable(SI)) {
1052  Instruction *UnderlyingPointer =
1054 
1055  if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
1056  memoryIsNotModifiedBetween(UnderlyingPointer, SI, AA)) {
1057  LLVM_DEBUG(
1058  dbgs() << "DSE: Remove null store to the calloc'ed object:\n DEAD: "
1059  << *Inst << "\n OBJECT: " << *UnderlyingPointer << '\n');
1060 
1061  deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, InstrOrdering);
1062  ++NumRedundantStores;
1063  return true;
1064  }
1065  }
1066  return false;
1067 }
1068 
1071  const TargetLibraryInfo *TLI) {
1072  const DataLayout &DL = BB.getModule()->getDataLayout();
1073  bool MadeChange = false;
1074 
1075  // FIXME: Maybe change this to use some abstraction like OrderedBasicBlock?
1076  // The current OrderedBasicBlock can't deal with mutation at the moment.
1077  size_t LastThrowingInstIndex = 0;
1078  DenseMap<Instruction*, size_t> InstrOrdering;
1079  size_t InstrIndex = 1;
1080 
1081  // A map of interval maps representing partially-overwritten value parts.
1083 
1084  // Do a top-down walk on the BB.
1085  for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
1086  // Handle 'free' calls specially.
1087  if (CallInst *F = isFreeCall(&*BBI, TLI)) {
1088  MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, &InstrOrdering);
1089  // Increment BBI after handleFree has potentially deleted instructions.
1090  // This ensures we maintain a valid iterator.
1091  ++BBI;
1092  continue;
1093  }
1094 
1095  Instruction *Inst = &*BBI++;
1096 
1097  size_t CurInstNumber = InstrIndex++;
1098  InstrOrdering.insert(std::make_pair(Inst, CurInstNumber));
1099  if (Inst->mayThrow()) {
1100  LastThrowingInstIndex = CurInstNumber;
1101  continue;
1102  }
1103 
1104  // Check to see if Inst writes to memory. If not, continue.
1105  if (!hasAnalyzableMemoryWrite(Inst, *TLI))
1106  continue;
1107 
1108  // eliminateNoopStore will update in iterator, if necessary.
1109  if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, &InstrOrdering)) {
1110  MadeChange = true;
1111  continue;
1112  }
1113 
1114  // If we find something that writes memory, get its memory dependence.
1115  MemDepResult InstDep = MD->getDependency(Inst);
1116 
1117  // Ignore any store where we can't find a local dependence.
1118  // FIXME: cross-block DSE would be fun. :)
1119  if (!InstDep.isDef() && !InstDep.isClobber())
1120  continue;
1121 
1122  // Figure out what location is being stored to.
1123  MemoryLocation Loc = getLocForWrite(Inst);
1124 
1125  // If we didn't get a useful location, fail.
1126  if (!Loc.Ptr)
1127  continue;
1128 
1129  // Loop until we find a store we can eliminate or a load that
1130  // invalidates the analysis. Without an upper bound on the number of
1131  // instructions examined, this analysis can become very time-consuming.
1132  // However, the potential gain diminishes as we process more instructions
1133  // without eliminating any of them. Therefore, we limit the number of
1134  // instructions we look at.
1135  auto Limit = MD->getDefaultBlockScanLimit();
1136  while (InstDep.isDef() || InstDep.isClobber()) {
1137  // Get the memory clobbered by the instruction we depend on. MemDep will
1138  // skip any instructions that 'Loc' clearly doesn't interact with. If we
1139  // end up depending on a may- or must-aliased load, then we can't optimize
1140  // away the store and we bail out. However, if we depend on something
1141  // that overwrites the memory location we *can* potentially optimize it.
1142  //
1143  // Find out what memory location the dependent instruction stores.
1144  Instruction *DepWrite = InstDep.getInst();
1145  if (!hasAnalyzableMemoryWrite(DepWrite, *TLI))
1146  break;
1147  MemoryLocation DepLoc = getLocForWrite(DepWrite);
1148  // If we didn't get a useful location, or if it isn't a size, bail out.
1149  if (!DepLoc.Ptr)
1150  break;
1151 
1152  // Make sure we don't look past a call which might throw. This is an
1153  // issue because MemoryDependenceAnalysis works in the wrong direction:
1154  // it finds instructions which dominate the current instruction, rather than
1155  // instructions which are post-dominated by the current instruction.
1156  //
1157  // If the underlying object is a non-escaping memory allocation, any store
1158  // to it is dead along the unwind edge. Otherwise, we need to preserve
1159  // the store.
1160  size_t DepIndex = InstrOrdering.lookup(DepWrite);
1161  assert(DepIndex && "Unexpected instruction");
1162  if (DepIndex <= LastThrowingInstIndex) {
1163  const Value* Underlying = GetUnderlyingObject(DepLoc.Ptr, DL);
1164  bool IsStoreDeadOnUnwind = isa<AllocaInst>(Underlying);
1165  if (!IsStoreDeadOnUnwind) {
1166  // We're looking for a call to an allocation function
1167  // where the allocation doesn't escape before the last
1168  // throwing instruction; PointerMayBeCaptured
1169  // reasonably fast approximation.
1170  IsStoreDeadOnUnwind = isAllocLikeFn(Underlying, TLI) &&
1171  !PointerMayBeCaptured(Underlying, false, true);
1172  }
1173  if (!IsStoreDeadOnUnwind)
1174  break;
1175  }
1176 
1177  // If we find a write that is a) removable (i.e., non-volatile), b) is
1178  // completely obliterated by the store to 'Loc', and c) which we know that
1179  // 'Inst' doesn't load from, then we can remove it.
1180  // Also try to merge two stores if a later one only touches memory written
1181  // to by the earlier one.
1182  if (isRemovable(DepWrite) &&
1183  !isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)) {
1184  int64_t InstWriteOffset, DepWriteOffset;
1185  OverwriteResult OR = isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset,
1186  InstWriteOffset, DepWrite, IOL, *AA,
1187  BB.getParent());
1188  if (OR == OW_Complete) {
1189  LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " << *DepWrite
1190  << "\n KILLER: " << *Inst << '\n');
1191 
1192  // Delete the store and now-dead instructions that feed it.
1193  deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, &InstrOrdering);
1194  ++NumFastStores;
1195  MadeChange = true;
1196 
1197  // We erased DepWrite; start over.
1198  InstDep = MD->getDependency(Inst);
1199  continue;
1200  } else if ((OR == OW_End && isShortenableAtTheEnd(DepWrite)) ||
1201  ((OR == OW_Begin &&
1202  isShortenableAtTheBeginning(DepWrite)))) {
1203  assert(!EnablePartialOverwriteTracking && "Do not expect to perform "
1204  "when partial-overwrite "
1205  "tracking is enabled");
1206  int64_t EarlierSize = DepLoc.Size;
1207  int64_t LaterSize = Loc.Size;
1208  bool IsOverwriteEnd = (OR == OW_End);
1209  MadeChange |= tryToShorten(DepWrite, DepWriteOffset, EarlierSize,
1210  InstWriteOffset, LaterSize, IsOverwriteEnd);
1211  } else if (EnablePartialStoreMerging &&
1212  OR == OW_PartialEarlierWithFullLater) {
1213  auto *Earlier = dyn_cast<StoreInst>(DepWrite);
1214  auto *Later = dyn_cast<StoreInst>(Inst);
1215  if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&
1216  Later && isa<ConstantInt>(Later->getValueOperand()) &&
1217  memoryIsNotModifiedBetween(Earlier, Later, AA)) {
1218  // If the store we find is:
1219  // a) partially overwritten by the store to 'Loc'
1220  // b) the later store is fully contained in the earlier one and
1221  // c) they both have a constant value
1222  // Merge the two stores, replacing the earlier store's value with a
1223  // merge of both values.
1224  // TODO: Deal with other constant types (vectors, etc), and probably
1225  // some mem intrinsics (if needed)
1226 
1227  APInt EarlierValue =
1228  cast<ConstantInt>(Earlier->getValueOperand())->getValue();
1229  APInt LaterValue =
1230  cast<ConstantInt>(Later->getValueOperand())->getValue();
1231  unsigned LaterBits = LaterValue.getBitWidth();
1232  assert(EarlierValue.getBitWidth() > LaterValue.getBitWidth());
1233  LaterValue = LaterValue.zext(EarlierValue.getBitWidth());
1234 
1235  // Offset of the smaller store inside the larger store
1236  unsigned BitOffsetDiff = (InstWriteOffset - DepWriteOffset) * 8;
1237  unsigned LShiftAmount =
1238  DL.isBigEndian()
1239  ? EarlierValue.getBitWidth() - BitOffsetDiff - LaterBits
1240  : BitOffsetDiff;
1241  APInt Mask =
1242  APInt::getBitsSet(EarlierValue.getBitWidth(), LShiftAmount,
1243  LShiftAmount + LaterBits);
1244  // Clear the bits we'll be replacing, then OR with the smaller
1245  // store, shifted appropriately.
1246  APInt Merged =
1247  (EarlierValue & ~Mask) | (LaterValue << LShiftAmount);
1248  LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n Earlier: " << *DepWrite
1249  << "\n Later: " << *Inst
1250  << "\n Merged Value: " << Merged << '\n');
1251 
1252  auto *SI = new StoreInst(
1253  ConstantInt::get(Earlier->getValueOperand()->getType(), Merged),
1254  Earlier->getPointerOperand(), false, Earlier->getAlignment(),
1255  Earlier->getOrdering(), Earlier->getSyncScopeID(), DepWrite);
1256 
1257  unsigned MDToKeep[] = {LLVMContext::MD_dbg, LLVMContext::MD_tbaa,
1261  SI->copyMetadata(*DepWrite, MDToKeep);
1262  ++NumModifiedStores;
1263 
1264  // Remove earlier, wider, store
1265  size_t Idx = InstrOrdering.lookup(DepWrite);
1266  InstrOrdering.erase(DepWrite);
1267  InstrOrdering.insert(std::make_pair(SI, Idx));
1268 
1269  // Delete the old stores and now-dead instructions that feed them.
1270  deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, &InstrOrdering);
1271  deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
1272  &InstrOrdering);
1273  MadeChange = true;
1274 
1275  // We erased DepWrite and Inst (Loc); start over.
1276  break;
1277  }
1278  }
1279  }
1280 
1281  // If this is a may-aliased store that is clobbering the store value, we
1282  // can keep searching past it for another must-aliased pointer that stores
1283  // to the same location. For example, in:
1284  // store -> P
1285  // store -> Q
1286  // store -> P
1287  // we can remove the first store to P even though we don't know if P and Q
1288  // alias.
1289  if (DepWrite == &BB.front()) break;
1290 
1291  // Can't look past this instruction if it might read 'Loc'.
1292  if (isRefSet(AA->getModRefInfo(DepWrite, Loc)))
1293  break;
1294 
1295  InstDep = MD->getPointerDependencyFrom(Loc, /*isLoad=*/ false,
1296  DepWrite->getIterator(), &BB,
1297  /*QueryInst=*/ nullptr, &Limit);
1298  }
1299  }
1300 
1302  MadeChange |= removePartiallyOverlappedStores(AA, DL, IOL);
1303 
1304  // If this block ends in a return, unwind, or unreachable, all allocas are
1305  // dead at its end, which means stores to them are also dead.
1306  if (BB.getTerminator()->getNumSuccessors() == 0)
1307  MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, &InstrOrdering);
1308 
1309  return MadeChange;
1310 }
1311 
1314  const TargetLibraryInfo *TLI) {
1315  bool MadeChange = false;
1316  for (BasicBlock &BB : F)
1317  // Only check non-dead blocks. Dead blocks may have strange pointer
1318  // cycles that will confuse alias analysis.
1319  if (DT->isReachableFromEntry(&BB))
1320  MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI);
1321 
1322  return MadeChange;
1323 }
1324 
1325 //===----------------------------------------------------------------------===//
1326 // DSE Pass
1327 //===----------------------------------------------------------------------===//
1329  AliasAnalysis *AA = &AM.getResult<AAManager>(F);
1333 
1334  if (!eliminateDeadStores(F, AA, MD, DT, TLI))
1335  return PreservedAnalyses::all();
1336 
1337  PreservedAnalyses PA;
1338  PA.preserveSet<CFGAnalyses>();
1339  PA.preserve<GlobalsAA>();
1341  return PA;
1342 }
1343 
1344 namespace {
1345 
1346 /// A legacy pass for the legacy pass manager that wraps \c DSEPass.
1347 class DSELegacyPass : public FunctionPass {
1348 public:
1349  static char ID; // Pass identification, replacement for typeid
1350 
1351  DSELegacyPass() : FunctionPass(ID) {
1353  }
1354 
1355  bool runOnFunction(Function &F) override {
1356  if (skipFunction(F))
1357  return false;
1358 
1359  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1360  AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
1362  &getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
1363  const TargetLibraryInfo *TLI =
1364  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1365 
1366  return eliminateDeadStores(F, AA, MD, DT, TLI);
1367  }
1368 
1369  void getAnalysisUsage(AnalysisUsage &AU) const override {
1370  AU.setPreservesCFG();
1378  }
1379 };
1380 
1381 } // end anonymous namespace
1382 
1383 char DSELegacyPass::ID = 0;
1384 
1385 INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,
1386  false)
1393  false)
1394 
1396  return new DSELegacyPass();
1397 }
Legacy wrapper pass to provide the GlobalsAAResult object.
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
Value * getValueOperand()
Definition: Instructions.h:399
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Provides a lazy, caching interface for making common memory aliasing information queries, backed by LLVM&#39;s alias analysis passes.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This is the interface for a simple mod/ref and alias analysis over globals.
void initializeDSELegacyPassPass(PassRegistry &)
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are no-alias. ...
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:864
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can&#39;t be evaluated...
This class represents a function call, abstracting a target machine&#39;s calling convention.
bool isNonLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the block...
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
StringRef getName(LibFunc F) const
bool salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Definition: Local.cpp:1598
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:225
F(f)
static bool handleFree(CallInst *F, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, const TargetLibraryInfo *TLI, InstOverlapIntervalsTy &IOL, DenseMap< Instruction *, size_t > *InstrOrdering)
Handle frees of entire structures whose dependency is a store to a field of that structure.
An instruction for reading from memory.
Definition: Instructions.h:168
static bool isPossibleSelfRead(Instruction *Inst, const MemoryLocation &InstStoreLoc, Instruction *DepWrite, const TargetLibraryInfo &TLI, AliasAnalysis &AA)
If &#39;Inst&#39; might be a self read (i.e.
#define op(i)
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:295
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1502
static void findUnconditionalPreds(SmallVectorImpl< BasicBlock *> &Blocks, BasicBlock *BB, DominatorTree *DT)
Find all blocks that will unconditionally lead to the block BB and append them to F...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
const CallInst * isFreeCall(const Value *I, const TargetLibraryInfo *TLI)
isFreeCall - Returns non-null if the value is a call to the builtin free()
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:264
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:134
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
bool isDef() const
Tests if this MemDepResult represents a query that is an instruction definition dependency.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
bool isClobber() const
Tests if this MemDepResult represents a query that is an instruction clobber dependency.
static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, MemoryDependenceResults *MD, const TargetLibraryInfo *TLI, InstOverlapIntervalsTy &IOL, DenseMap< Instruction *, size_t > *InstrOrdering)
Remove dead stores to stack-allocated locations in the function end block.
unsigned getDefaultBlockScanLimit() const
Some methods limit the number of instructions they will examine.
An analysis that produces MemoryDependenceResults for a function.
static MemoryLocation getLocForWrite(Instruction *Inst)
Return a Location stored to by the specified instruction.
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:158
This file implements a class to represent arbitrary precision integral constant values and operations...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:85
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
static Value * getStoredPointerOperand(Instruction *I)
Return the pointer that is being written to.
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
Value * GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout &DL)
Analyze the specified pointer to see if it can be expressed as a base pointer plus a constant offset...
bool has(LibFunc F) const
Tests whether a library function is available.
std::map< int64_t, int64_t > OverlapIntervalsTy
static uint64_t getPointerSize(const Value *V, const DataLayout &DL, const TargetLibraryInfo &TLI, const Function *F)
An instruction for storing to memory.
Definition: Instructions.h:310
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
Value * getOperand(unsigned i) const
Definition: User.h:170
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:211
Value * getOperand(unsigned i_nocapture) const
const BasicBlock & getEntryBlock() const
Definition: Function.h:626
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:841
static bool runOnFunction(Function &F, bool PostInlining)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
static bool isShortenableAtTheBeginning(Instruction *I)
Returns true if the beginning of this instruction can be safely shortened in length.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:55
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
static bool removePartiallyOverlappedStores(AliasAnalysis *AA, const DataLayout &DL, InstOverlapIntervalsTy &IOL)
static OverwriteResult isOverwrite(const MemoryLocation &Later, const MemoryLocation &Earlier, const DataLayout &DL, const TargetLibraryInfo &TLI, int64_t &EarlierOff, int64_t &LaterOff, Instruction *DepWrite, InstOverlapIntervalsTy &IOL, AliasAnalysis &AA, const Function *F)
Return &#39;OW_Complete&#39; if a store to the &#39;Later&#39; location completely overwrites a store to the &#39;Earlier...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:276
A manager for alias analyses.
static ManagedStatic< OptionRegistry > OR
Definition: Options.cpp:31
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
bool mayThrow() const
Return true if this instruction may throw an exception.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
static bool isShortenableAtTheEnd(Instruction *I)
Returns true if the end of this instruction can be safely shortened in length.
Represent the analysis usage information of a pass.
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:434
FunctionPass * createDeadStoreEliminationPass()
static bool memoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI, AliasAnalysis *AA)
Returns true if the memory which is accessed by the second instruction is not modified between the fi...
std::underlying_type< E >::type Underlying(E Val)
Check that Val is in range for E, and return Val cast to E&#39;s underlying type.
Definition: BitmaskEnum.h:91
Analysis pass providing a never-invalidated alias analysis result.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known...
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
self_iterator getIterator()
Definition: ilist_node.h:82
INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false, false) INITIALIZE_PASS_END(DSELegacyPass
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, and aliases.
Definition: Value.cpp:539
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
Dead Store Elimination
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance...
Value * GetUnderlyingObject(Value *V, const DataLayout &DL, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
A memory dependence query can return one of three different answers.
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
static cl::opt< bool > EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking", cl::init(true), cl::Hidden, cl::desc("Enable partial-overwrite tracking in DSE"))
MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst=nullptr, unsigned *Limit=nullptr)
Returns the instruction on which a memory location depends.
static void deleteDeadInstruction(Instruction *I, BasicBlock::iterator *BBI, MemoryDependenceResults &MD, const TargetLibraryInfo &TLI, InstOverlapIntervalsTy &IOL, DenseMap< Instruction *, size_t > *InstrOrdering, SmallSetVector< Value *, 16 > *ValueSet=nullptr)
Delete this instruction.
static cl::opt< bool > EnablePartialStoreMerging("enable-dse-partial-store-merging", cl::init(true), cl::Hidden, cl::desc("Enable partial store merging in DSE"))
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
bool doesNotAccessMemory(ImmutableCallSite CS)
Checks if the specified call is known to never read or write memory.
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:192
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
static void removeAccessedObjects(const MemoryLocation &LoadedLoc, SmallSetVector< Value *, 16 > &DeadStackObjects, const DataLayout &DL, AliasAnalysis *AA, const TargetLibraryInfo *TLI, const Function *F)
Check to see if the specified location may alias any of the stack objects in the DeadStackObjects set...
iterator end()
Definition: BasicBlock.h:266
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:376
static bool hasAnalyzableMemoryWrite(Instruction *I, const TargetLibraryInfo &TLI)
Does this instruction write some memory? This only returns true for things that we can analyze with o...
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:621
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI, AliasAnalysis *AA, MemoryDependenceResults *MD, const DataLayout &DL, const TargetLibraryInfo *TLI, InstOverlapIntervalsTy &IOL, DenseMap< Instruction *, size_t > *InstrOrdering)
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
Definition: Function.cpp:1426
void setOperand(unsigned i, Value *Val)
Definition: User.h:175
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:56
Class for arbitrary precision integers.
Definition: APInt.h:69
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are must-alias.
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit)
Get a value with a block of bits set.
Definition: APInt.h:606
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
static bool tryToShortenBegin(Instruction *EarlierWrite, OverlapIntervalsTy &IntervalMap, int64_t &EarlierStart, int64_t &EarlierSize)
Instruction * getInst() const
If this is a normal dependency, returns the instruction that is depended on.
static MemoryLocation getLocForRead(Instruction *Inst, const TargetLibraryInfo &TLI)
Return the location read by the specified "hasAnalyzableMemoryWrite" instruction if any...
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
This file provides utility analysis objects describing memory locations.
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:189
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates zero-filled memory (such as...
#define I(x, y, z)
Definition: MD5.cpp:58
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:73
bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates memory (either malloc...
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:181
Analysis pass providing the TargetLibraryInfo.
void GetUnderlyingObjects(Value *V, SmallVectorImpl< Value *> &Objects, const DataLayout &DL, LoopInfo *LI=nullptr, unsigned MaxLookup=6)
This method is similar to GetUnderlyingObject except that it can look through phi and select instruct...
static GetElementPtrInst * CreateInBounds(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Create an "inbounds" getelementptr.
Definition: Instructions.h:901
static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, const TargetLibraryInfo *TLI)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const BasicBlock & front() const
Definition: Function.h:649
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:346
LLVM Value Representation.
Definition: Value.h:73
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
bool remove_if(UnaryPredicate P)
Remove items from the set vector based on a predicate function.
Definition: SetVector.h:200
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
static bool isRemovable(Instruction *I)
If the value of this instruction and the memory it writes to is unused, may we delete this instructio...
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
Various options to control the behavior of getObjectSize.
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:254
static bool isVolatile(Instruction *Inst)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
This header defines various interfaces for pass management in LLVM.
bool isBigEndian() const
Definition: DataLayout.h:222
#define LLVM_DEBUG(X)
Definition: Debug.h:119
Value * getPointerOperand()
Definition: Instructions.h:402
bool use_empty() const
Definition: Value.h:322
static bool tryToShorten(Instruction *EarlierWrite, int64_t &EarlierOffset, int64_t &EarlierSize, int64_t LaterOffset, int64_t LaterSize, bool IsOverwriteEnd)
iterator_range< arg_iterator > args()
Definition: Function.h:675
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:67
static bool tryToShortenEnd(Instruction *EarlierWrite, OverlapIntervalsTy &IntervalMap, int64_t &EarlierStart, int64_t &EarlierSize)
MemDepResult getDependency(Instruction *QueryInst)
Returns the instruction on which a memory operation depends.
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)