LLVM  10.0.0svn
MemCpyOptimizer.cpp
Go to the documentation of this file.
1 //===- MemCpyOptimizer.cpp - Optimize use of memcpy and friends -----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass performs various transformations related to eliminating memcpy
10 // calls, or transforming sets of stores into memset's.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/DenseSet.h"
16 #include "llvm/ADT/None.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
29 #include "llvm/IR/Argument.h"
30 #include "llvm/IR/BasicBlock.h"
31 #include "llvm/IR/CallSite.h"
32 #include "llvm/IR/Constants.h"
33 #include "llvm/IR/DataLayout.h"
34 #include "llvm/IR/DerivedTypes.h"
35 #include "llvm/IR/Dominators.h"
36 #include "llvm/IR/Function.h"
38 #include "llvm/IR/GlobalVariable.h"
39 #include "llvm/IR/IRBuilder.h"
40 #include "llvm/IR/InstrTypes.h"
41 #include "llvm/IR/Instruction.h"
42 #include "llvm/IR/Instructions.h"
43 #include "llvm/IR/IntrinsicInst.h"
44 #include "llvm/IR/Intrinsics.h"
45 #include "llvm/IR/LLVMContext.h"
46 #include "llvm/IR/Module.h"
47 #include "llvm/IR/Operator.h"
48 #include "llvm/IR/PassManager.h"
49 #include "llvm/IR/Type.h"
50 #include "llvm/IR/User.h"
51 #include "llvm/IR/Value.h"
52 #include "llvm/Pass.h"
53 #include "llvm/Support/Casting.h"
54 #include "llvm/Support/Debug.h"
57 #include "llvm/Transforms/Scalar.h"
58 #include <algorithm>
59 #include <cassert>
60 #include <cstdint>
61 #include <utility>
62 
63 using namespace llvm;
64 
65 #define DEBUG_TYPE "memcpyopt"
66 
67 STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted");
68 STATISTIC(NumMemSetInfer, "Number of memsets inferred");
69 STATISTIC(NumMoveToCpy, "Number of memmoves converted to memcpy");
70 STATISTIC(NumCpyToSet, "Number of memcpys converted to memset");
71 
72 namespace {
73 
74 /// Represents a range of memset'd bytes with the ByteVal value.
75 /// This allows us to analyze stores like:
76 /// store 0 -> P+1
77 /// store 0 -> P+0
78 /// store 0 -> P+3
79 /// store 0 -> P+2
80 /// which sometimes happens with stores to arrays of structs etc. When we see
81 /// the first store, we make a range [1, 2). The second store extends the range
82 /// to [0, 2). The third makes a new range [2, 3). The fourth store joins the
83 /// two ranges into [0, 3) which is memset'able.
84 struct MemsetRange {
85  // Start/End - A semi range that describes the span that this range covers.
86  // The range is closed at the start and open at the end: [Start, End).
87  int64_t Start, End;
88 
89  /// StartPtr - The getelementptr instruction that points to the start of the
90  /// range.
91  Value *StartPtr;
92 
93  /// Alignment - The known alignment of the first store.
94  unsigned Alignment;
95 
96  /// TheStores - The actual stores that make up this range.
98 
99  bool isProfitableToUseMemset(const DataLayout &DL) const;
100 };
101 
102 } // end anonymous namespace
103 
104 bool MemsetRange::isProfitableToUseMemset(const DataLayout &DL) const {
105  // If we found more than 4 stores to merge or 16 bytes, use memset.
106  if (TheStores.size() >= 4 || End-Start >= 16) return true;
107 
108  // If there is nothing to merge, don't do anything.
109  if (TheStores.size() < 2) return false;
110 
111  // If any of the stores are a memset, then it is always good to extend the
112  // memset.
113  for (Instruction *SI : TheStores)
114  if (!isa<StoreInst>(SI))
115  return true;
116 
117  // Assume that the code generator is capable of merging pairs of stores
118  // together if it wants to.
119  if (TheStores.size() == 2) return false;
120 
121  // If we have fewer than 8 stores, it can still be worthwhile to do this.
122  // For example, merging 4 i8 stores into an i32 store is useful almost always.
123  // However, merging 2 32-bit stores isn't useful on a 32-bit architecture (the
124  // memset will be split into 2 32-bit stores anyway) and doing so can
125  // pessimize the llvm optimizer.
126  //
127  // Since we don't have perfect knowledge here, make some assumptions: assume
128  // the maximum GPR width is the same size as the largest legal integer
129  // size. If so, check to see whether we will end up actually reducing the
130  // number of stores used.
131  unsigned Bytes = unsigned(End-Start);
132  unsigned MaxIntSize = DL.getLargestLegalIntTypeSizeInBits() / 8;
133  if (MaxIntSize == 0)
134  MaxIntSize = 1;
135  unsigned NumPointerStores = Bytes / MaxIntSize;
136 
137  // Assume the remaining bytes if any are done a byte at a time.
138  unsigned NumByteStores = Bytes % MaxIntSize;
139 
140  // If we will reduce the # stores (according to this heuristic), do the
141  // transformation. This encourages merging 4 x i8 -> i32 and 2 x i16 -> i32
142  // etc.
143  return TheStores.size() > NumPointerStores+NumByteStores;
144 }
145 
146 namespace {
147 
148 class MemsetRanges {
149  using range_iterator = SmallVectorImpl<MemsetRange>::iterator;
150 
151  /// A sorted list of the memset ranges.
153 
154  const DataLayout &DL;
155 
156 public:
157  MemsetRanges(const DataLayout &DL) : DL(DL) {}
158 
159  using const_iterator = SmallVectorImpl<MemsetRange>::const_iterator;
160 
161  const_iterator begin() const { return Ranges.begin(); }
162  const_iterator end() const { return Ranges.end(); }
163  bool empty() const { return Ranges.empty(); }
164 
165  void addInst(int64_t OffsetFromFirst, Instruction *Inst) {
166  if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
167  addStore(OffsetFromFirst, SI);
168  else
169  addMemSet(OffsetFromFirst, cast<MemSetInst>(Inst));
170  }
171 
172  void addStore(int64_t OffsetFromFirst, StoreInst *SI) {
173  int64_t StoreSize = DL.getTypeStoreSize(SI->getOperand(0)->getType());
174 
175  addRange(OffsetFromFirst, StoreSize,
176  SI->getPointerOperand(), SI->getAlignment(), SI);
177  }
178 
179  void addMemSet(int64_t OffsetFromFirst, MemSetInst *MSI) {
180  int64_t Size = cast<ConstantInt>(MSI->getLength())->getZExtValue();
181  addRange(OffsetFromFirst, Size, MSI->getDest(), MSI->getDestAlignment(), MSI);
182  }
183 
184  void addRange(int64_t Start, int64_t Size, Value *Ptr,
185  unsigned Alignment, Instruction *Inst);
186 };
187 
188 } // end anonymous namespace
189 
190 /// Add a new store to the MemsetRanges data structure. This adds a
191 /// new range for the specified store at the specified offset, merging into
192 /// existing ranges as appropriate.
193 void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr,
194  unsigned Alignment, Instruction *Inst) {
195  int64_t End = Start+Size;
196 
197  range_iterator I = partition_point(
198  Ranges, [=](const MemsetRange &O) { return O.End < Start; });
199 
200  // We now know that I == E, in which case we didn't find anything to merge
201  // with, or that Start <= I->End. If End < I->Start or I == E, then we need
202  // to insert a new range. Handle this now.
203  if (I == Ranges.end() || End < I->Start) {
204  MemsetRange &R = *Ranges.insert(I, MemsetRange());
205  R.Start = Start;
206  R.End = End;
207  R.StartPtr = Ptr;
208  R.Alignment = Alignment;
209  R.TheStores.push_back(Inst);
210  return;
211  }
212 
213  // This store overlaps with I, add it.
214  I->TheStores.push_back(Inst);
215 
216  // At this point, we may have an interval that completely contains our store.
217  // If so, just add it to the interval and return.
218  if (I->Start <= Start && I->End >= End)
219  return;
220 
221  // Now we know that Start <= I->End and End >= I->Start so the range overlaps
222  // but is not entirely contained within the range.
223 
224  // See if the range extends the start of the range. In this case, it couldn't
225  // possibly cause it to join the prior range, because otherwise we would have
226  // stopped on *it*.
227  if (Start < I->Start) {
228  I->Start = Start;
229  I->StartPtr = Ptr;
230  I->Alignment = Alignment;
231  }
232 
233  // Now we know that Start <= I->End and Start >= I->Start (so the startpoint
234  // is in or right at the end of I), and that End >= I->Start. Extend I out to
235  // End.
236  if (End > I->End) {
237  I->End = End;
238  range_iterator NextI = I;
239  while (++NextI != Ranges.end() && End >= NextI->Start) {
240  // Merge the range in.
241  I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end());
242  if (NextI->End > I->End)
243  I->End = NextI->End;
244  Ranges.erase(NextI);
245  NextI = I;
246  }
247  }
248 }
249 
250 //===----------------------------------------------------------------------===//
251 // MemCpyOptLegacyPass Pass
252 //===----------------------------------------------------------------------===//
253 
254 namespace {
255 
256 class MemCpyOptLegacyPass : public FunctionPass {
257  MemCpyOptPass Impl;
258 
259 public:
260  static char ID; // Pass identification, replacement for typeid
261 
262  MemCpyOptLegacyPass() : FunctionPass(ID) {
264  }
265 
266  bool runOnFunction(Function &F) override;
267 
268 private:
269  // This transformation requires dominator postdominator info
270  void getAnalysisUsage(AnalysisUsage &AU) const override {
271  AU.setPreservesCFG();
279  }
280 };
281 
282 } // end anonymous namespace
283 
284 char MemCpyOptLegacyPass::ID = 0;
285 
286 /// The public interface to this file...
287 FunctionPass *llvm::createMemCpyOptPass() { return new MemCpyOptLegacyPass(); }
288 
289 INITIALIZE_PASS_BEGIN(MemCpyOptLegacyPass, "memcpyopt", "MemCpy Optimization",
290  false, false)
297 INITIALIZE_PASS_END(MemCpyOptLegacyPass, "memcpyopt", "MemCpy Optimization",
298  false, false)
299 
300 /// When scanning forward over instructions, we look for some other patterns to
301 /// fold away. In particular, this looks for stores to neighboring locations of
302 /// memory. If it sees enough consecutive ones, it attempts to merge them
303 /// together into a memcpy/memset.
304 Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,
305  Value *StartPtr,
306  Value *ByteVal) {
307  const DataLayout &DL = StartInst->getModule()->getDataLayout();
308 
309  // Okay, so we now have a single store that can be splatable. Scan to find
310  // all subsequent stores of the same value to offset from the same pointer.
311  // Join these together into ranges, so we can decide whether contiguous blocks
312  // are stored.
313  MemsetRanges Ranges(DL);
314 
315  BasicBlock::iterator BI(StartInst);
316  for (++BI; !BI->isTerminator(); ++BI) {
317  if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) {
318  // If the instruction is readnone, ignore it, otherwise bail out. We
319  // don't even allow readonly here because we don't want something like:
320  // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A).
321  if (BI->mayWriteToMemory() || BI->mayReadFromMemory())
322  break;
323  continue;
324  }
325 
326  if (StoreInst *NextStore = dyn_cast<StoreInst>(BI)) {
327  // If this is a store, see if we can merge it in.
328  if (!NextStore->isSimple()) break;
329 
330  // Check to see if this stored value is of the same byte-splattable value.
331  Value *StoredByte = isBytewiseValue(NextStore->getOperand(0), DL);
332  if (isa<UndefValue>(ByteVal) && StoredByte)
333  ByteVal = StoredByte;
334  if (ByteVal != StoredByte)
335  break;
336 
337  // Check to see if this store is to a constant offset from the start ptr.
339  isPointerOffset(StartPtr, NextStore->getPointerOperand(), DL);
340  if (!Offset)
341  break;
342 
343  Ranges.addStore(*Offset, NextStore);
344  } else {
345  MemSetInst *MSI = cast<MemSetInst>(BI);
346 
347  if (MSI->isVolatile() || ByteVal != MSI->getValue() ||
348  !isa<ConstantInt>(MSI->getLength()))
349  break;
350 
351  // Check to see if this store is to a constant offset from the start ptr.
352  Optional<int64_t> Offset = isPointerOffset(StartPtr, MSI->getDest(), DL);
353  if (!Offset)
354  break;
355 
356  Ranges.addMemSet(*Offset, MSI);
357  }
358  }
359 
360  // If we have no ranges, then we just had a single store with nothing that
361  // could be merged in. This is a very common case of course.
362  if (Ranges.empty())
363  return nullptr;
364 
365  // If we had at least one store that could be merged in, add the starting
366  // store as well. We try to avoid this unless there is at least something
367  // interesting as a small compile-time optimization.
368  Ranges.addInst(0, StartInst);
369 
370  // If we create any memsets, we put it right before the first instruction that
371  // isn't part of the memset block. This ensure that the memset is dominated
372  // by any addressing instruction needed by the start of the block.
373  IRBuilder<> Builder(&*BI);
374 
375  // Now that we have full information about ranges, loop over the ranges and
376  // emit memset's for anything big enough to be worthwhile.
377  Instruction *AMemSet = nullptr;
378  for (const MemsetRange &Range : Ranges) {
379  if (Range.TheStores.size() == 1) continue;
380 
381  // If it is profitable to lower this range to memset, do so now.
382  if (!Range.isProfitableToUseMemset(DL))
383  continue;
384 
385  // Otherwise, we do want to transform this! Create a new memset.
386  // Get the starting pointer of the block.
387  StartPtr = Range.StartPtr;
388 
389  // Determine alignment
390  unsigned Alignment = Range.Alignment;
391  if (Alignment == 0) {
392  Type *EltType =
393  cast<PointerType>(StartPtr->getType())->getElementType();
394  Alignment = DL.getABITypeAlignment(EltType);
395  }
396 
397  AMemSet =
398  Builder.CreateMemSet(StartPtr, ByteVal, Range.End-Range.Start, Alignment);
399 
400  LLVM_DEBUG(dbgs() << "Replace stores:\n"; for (Instruction *SI
401  : Range.TheStores) dbgs()
402  << *SI << '\n';
403  dbgs() << "With: " << *AMemSet << '\n');
404 
405  if (!Range.TheStores.empty())
406  AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc());
407 
408  // Zap all the stores.
409  for (Instruction *SI : Range.TheStores) {
410  MD->removeInstruction(SI);
411  SI->eraseFromParent();
412  }
413  ++NumMemSetInfer;
414  }
415 
416  return AMemSet;
417 }
418 
419 static unsigned findStoreAlignment(const DataLayout &DL, const StoreInst *SI) {
420  unsigned StoreAlign = SI->getAlignment();
421  if (!StoreAlign)
422  StoreAlign = DL.getABITypeAlignment(SI->getOperand(0)->getType());
423  return StoreAlign;
424 }
425 
426 static unsigned findLoadAlignment(const DataLayout &DL, const LoadInst *LI) {
427  unsigned LoadAlign = LI->getAlignment();
428  if (!LoadAlign)
429  LoadAlign = DL.getABITypeAlignment(LI->getType());
430  return LoadAlign;
431 }
432 
433 static unsigned findCommonAlignment(const DataLayout &DL, const StoreInst *SI,
434  const LoadInst *LI) {
435  unsigned StoreAlign = findStoreAlignment(DL, SI);
436  unsigned LoadAlign = findLoadAlignment(DL, LI);
437  return MinAlign(StoreAlign, LoadAlign);
438 }
439 
440 // This method try to lift a store instruction before position P.
441 // It will lift the store and its argument + that anything that
442 // may alias with these.
443 // The method returns true if it was successful.
444 static bool moveUp(AliasAnalysis &AA, StoreInst *SI, Instruction *P,
445  const LoadInst *LI) {
446  // If the store alias this position, early bail out.
447  MemoryLocation StoreLoc = MemoryLocation::get(SI);
448  if (isModOrRefSet(AA.getModRefInfo(P, StoreLoc)))
449  return false;
450 
451  // Keep track of the arguments of all instruction we plan to lift
452  // so we can make sure to lift them as well if appropriate.
454  if (auto *Ptr = dyn_cast<Instruction>(SI->getPointerOperand()))
455  if (Ptr->getParent() == SI->getParent())
456  Args.insert(Ptr);
457 
458  // Instruction to lift before P.
460 
461  // Memory locations of lifted instructions.
462  SmallVector<MemoryLocation, 8> MemLocs{StoreLoc};
463 
464  // Lifted calls.
466 
467  const MemoryLocation LoadLoc = MemoryLocation::get(LI);
468 
469  for (auto I = --SI->getIterator(), E = P->getIterator(); I != E; --I) {
470  auto *C = &*I;
471 
473 
474  bool NeedLift = false;
475  if (Args.erase(C))
476  NeedLift = true;
477  else if (MayAlias) {
478  NeedLift = llvm::any_of(MemLocs, [C, &AA](const MemoryLocation &ML) {
479  return isModOrRefSet(AA.getModRefInfo(C, ML));
480  });
481 
482  if (!NeedLift)
483  NeedLift = llvm::any_of(Calls, [C, &AA](const CallBase *Call) {
484  return isModOrRefSet(AA.getModRefInfo(C, Call));
485  });
486  }
487 
488  if (!NeedLift)
489  continue;
490 
491  if (MayAlias) {
492  // Since LI is implicitly moved downwards past the lifted instructions,
493  // none of them may modify its source.
494  if (isModSet(AA.getModRefInfo(C, LoadLoc)))
495  return false;
496  else if (const auto *Call = dyn_cast<CallBase>(C)) {
497  // If we can't lift this before P, it's game over.
498  if (isModOrRefSet(AA.getModRefInfo(P, Call)))
499  return false;
500 
501  Calls.push_back(Call);
502  } else if (isa<LoadInst>(C) || isa<StoreInst>(C) || isa<VAArgInst>(C)) {
503  // If we can't lift this before P, it's game over.
504  auto ML = MemoryLocation::get(C);
505  if (isModOrRefSet(AA.getModRefInfo(P, ML)))
506  return false;
507 
508  MemLocs.push_back(ML);
509  } else
510  // We don't know how to lift this instruction.
511  return false;
512  }
513 
514  ToLift.push_back(C);
515  for (unsigned k = 0, e = C->getNumOperands(); k != e; ++k)
516  if (auto *A = dyn_cast<Instruction>(C->getOperand(k))) {
517  if (A->getParent() == SI->getParent()) {
518  // Cannot hoist user of P above P
519  if(A == P) return false;
520  Args.insert(A);
521  }
522  }
523  }
524 
525  // We made it, we need to lift
526  for (auto *I : llvm::reverse(ToLift)) {
527  LLVM_DEBUG(dbgs() << "Lifting " << *I << " before " << *P << "\n");
528  I->moveBefore(P);
529  }
530 
531  return true;
532 }
533 
534 bool MemCpyOptPass::processStore(StoreInst *SI, BasicBlock::iterator &BBI) {
535  if (!SI->isSimple()) return false;
536 
537  // Avoid merging nontemporal stores since the resulting
538  // memcpy/memset would not be able to preserve the nontemporal hint.
539  // In theory we could teach how to propagate the !nontemporal metadata to
540  // memset calls. However, that change would force the backend to
541  // conservatively expand !nontemporal memset calls back to sequences of
542  // store instructions (effectively undoing the merging).
543  if (SI->getMetadata(LLVMContext::MD_nontemporal))
544  return false;
545 
546  const DataLayout &DL = SI->getModule()->getDataLayout();
547 
548  // Load to store forwarding can be interpreted as memcpy.
549  if (LoadInst *LI = dyn_cast<LoadInst>(SI->getOperand(0))) {
550  if (LI->isSimple() && LI->hasOneUse() &&
551  LI->getParent() == SI->getParent()) {
552 
553  auto *T = LI->getType();
554  if (T->isAggregateType()) {
555  AliasAnalysis &AA = LookupAliasAnalysis();
556  MemoryLocation LoadLoc = MemoryLocation::get(LI);
557 
558  // We use alias analysis to check if an instruction may store to
559  // the memory we load from in between the load and the store. If
560  // such an instruction is found, we try to promote there instead
561  // of at the store position.
562  Instruction *P = SI;
563  for (auto &I : make_range(++LI->getIterator(), SI->getIterator())) {
564  if (isModSet(AA.getModRefInfo(&I, LoadLoc))) {
565  P = &I;
566  break;
567  }
568  }
569 
570  // We found an instruction that may write to the loaded memory.
571  // We can try to promote at this position instead of the store
572  // position if nothing alias the store memory after this and the store
573  // destination is not in the range.
574  if (P && P != SI) {
575  if (!moveUp(AA, SI, P, LI))
576  P = nullptr;
577  }
578 
579  // If a valid insertion position is found, then we can promote
580  // the load/store pair to a memcpy.
581  if (P) {
582  // If we load from memory that may alias the memory we store to,
583  // memmove must be used to preserve semantic. If not, memcpy can
584  // be used.
585  bool UseMemMove = false;
586  if (!AA.isNoAlias(MemoryLocation::get(SI), LoadLoc))
587  UseMemMove = true;
588 
589  uint64_t Size = DL.getTypeStoreSize(T);
590 
591  IRBuilder<> Builder(P);
592  Instruction *M;
593  if (UseMemMove)
594  M = Builder.CreateMemMove(
595  SI->getPointerOperand(), findStoreAlignment(DL, SI),
596  LI->getPointerOperand(), findLoadAlignment(DL, LI), Size);
597  else
598  M = Builder.CreateMemCpy(
599  SI->getPointerOperand(), findStoreAlignment(DL, SI),
600  LI->getPointerOperand(), findLoadAlignment(DL, LI), Size);
601 
602  LLVM_DEBUG(dbgs() << "Promoting " << *LI << " to " << *SI << " => "
603  << *M << "\n");
604 
605  MD->removeInstruction(SI);
606  SI->eraseFromParent();
607  MD->removeInstruction(LI);
608  LI->eraseFromParent();
609  ++NumMemCpyInstr;
610 
611  // Make sure we do not invalidate the iterator.
612  BBI = M->getIterator();
613  return true;
614  }
615  }
616 
617  // Detect cases where we're performing call slot forwarding, but
618  // happen to be using a load-store pair to implement it, rather than
619  // a memcpy.
620  MemDepResult ldep = MD->getDependency(LI);
621  CallInst *C = nullptr;
622  if (ldep.isClobber() && !isa<MemCpyInst>(ldep.getInst()))
623  C = dyn_cast<CallInst>(ldep.getInst());
624 
625  if (C) {
626  // Check that nothing touches the dest of the "copy" between
627  // the call and the store.
628  Value *CpyDest = SI->getPointerOperand()->stripPointerCasts();
629  bool CpyDestIsLocal = isa<AllocaInst>(CpyDest);
630  AliasAnalysis &AA = LookupAliasAnalysis();
631  MemoryLocation StoreLoc = MemoryLocation::get(SI);
632  for (BasicBlock::iterator I = --SI->getIterator(), E = C->getIterator();
633  I != E; --I) {
634  if (isModOrRefSet(AA.getModRefInfo(&*I, StoreLoc))) {
635  C = nullptr;
636  break;
637  }
638  // The store to dest may never happen if an exception can be thrown
639  // between the load and the store.
640  if (I->mayThrow() && !CpyDestIsLocal) {
641  C = nullptr;
642  break;
643  }
644  }
645  }
646 
647  if (C) {
648  bool changed = performCallSlotOptzn(
650  LI->getPointerOperand()->stripPointerCasts(),
651  DL.getTypeStoreSize(SI->getOperand(0)->getType()),
652  findCommonAlignment(DL, SI, LI), C);
653  if (changed) {
654  MD->removeInstruction(SI);
655  SI->eraseFromParent();
656  MD->removeInstruction(LI);
657  LI->eraseFromParent();
658  ++NumMemCpyInstr;
659  return true;
660  }
661  }
662  }
663  }
664 
665  // There are two cases that are interesting for this code to handle: memcpy
666  // and memset. Right now we only handle memset.
667 
668  // Ensure that the value being stored is something that can be memset'able a
669  // byte at a time like "0" or "-1" or any width, as well as things like
670  // 0xA0A0A0A0 and 0.0.
671  auto *V = SI->getOperand(0);
672  if (Value *ByteVal = isBytewiseValue(V, DL)) {
673  if (Instruction *I = tryMergingIntoMemset(SI, SI->getPointerOperand(),
674  ByteVal)) {
675  BBI = I->getIterator(); // Don't invalidate iterator.
676  return true;
677  }
678 
679  // If we have an aggregate, we try to promote it to memset regardless
680  // of opportunity for merging as it can expose optimization opportunities
681  // in subsequent passes.
682  auto *T = V->getType();
683  if (T->isAggregateType()) {
684  uint64_t Size = DL.getTypeStoreSize(T);
685  unsigned Align = SI->getAlignment();
686  if (!Align)
687  Align = DL.getABITypeAlignment(T);
688  IRBuilder<> Builder(SI);
689  auto *M =
690  Builder.CreateMemSet(SI->getPointerOperand(), ByteVal, Size, Align);
691 
692  LLVM_DEBUG(dbgs() << "Promoting " << *SI << " to " << *M << "\n");
693 
694  MD->removeInstruction(SI);
695  SI->eraseFromParent();
696  NumMemSetInfer++;
697 
698  // Make sure we do not invalidate the iterator.
699  BBI = M->getIterator();
700  return true;
701  }
702  }
703 
704  return false;
705 }
706 
707 bool MemCpyOptPass::processMemSet(MemSetInst *MSI, BasicBlock::iterator &BBI) {
708  // See if there is another memset or store neighboring this memset which
709  // allows us to widen out the memset to do a single larger store.
710  if (isa<ConstantInt>(MSI->getLength()) && !MSI->isVolatile())
711  if (Instruction *I = tryMergingIntoMemset(MSI, MSI->getDest(),
712  MSI->getValue())) {
713  BBI = I->getIterator(); // Don't invalidate iterator.
714  return true;
715  }
716  return false;
717 }
718 
719 /// Takes a memcpy and a call that it depends on,
720 /// and checks for the possibility of a call slot optimization by having
721 /// the call write its result directly into the destination of the memcpy.
722 bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpy, Value *cpyDest,
723  Value *cpySrc, uint64_t cpyLen,
724  unsigned cpyAlign, CallInst *C) {
725  // The general transformation to keep in mind is
726  //
727  // call @func(..., src, ...)
728  // memcpy(dest, src, ...)
729  //
730  // ->
731  //
732  // memcpy(dest, src, ...)
733  // call @func(..., dest, ...)
734  //
735  // Since moving the memcpy is technically awkward, we additionally check that
736  // src only holds uninitialized values at the moment of the call, meaning that
737  // the memcpy can be discarded rather than moved.
738 
739  // Lifetime marks shouldn't be operated on.
740  if (Function *F = C->getCalledFunction())
741  if (F->isIntrinsic() && F->getIntrinsicID() == Intrinsic::lifetime_start)
742  return false;
743 
744  // Deliberately get the source and destination with bitcasts stripped away,
745  // because we'll need to do type comparisons based on the underlying type.
746  CallSite CS(C);
747 
748  // Require that src be an alloca. This simplifies the reasoning considerably.
749  AllocaInst *srcAlloca = dyn_cast<AllocaInst>(cpySrc);
750  if (!srcAlloca)
751  return false;
752 
753  ConstantInt *srcArraySize = dyn_cast<ConstantInt>(srcAlloca->getArraySize());
754  if (!srcArraySize)
755  return false;
756 
757  const DataLayout &DL = cpy->getModule()->getDataLayout();
758  uint64_t srcSize = DL.getTypeAllocSize(srcAlloca->getAllocatedType()) *
759  srcArraySize->getZExtValue();
760 
761  if (cpyLen < srcSize)
762  return false;
763 
764  // Check that accessing the first srcSize bytes of dest will not cause a
765  // trap. Otherwise the transform is invalid since it might cause a trap
766  // to occur earlier than it otherwise would.
767  if (AllocaInst *A = dyn_cast<AllocaInst>(cpyDest)) {
768  // The destination is an alloca. Check it is larger than srcSize.
769  ConstantInt *destArraySize = dyn_cast<ConstantInt>(A->getArraySize());
770  if (!destArraySize)
771  return false;
772 
773  uint64_t destSize = DL.getTypeAllocSize(A->getAllocatedType()) *
774  destArraySize->getZExtValue();
775 
776  if (destSize < srcSize)
777  return false;
778  } else if (Argument *A = dyn_cast<Argument>(cpyDest)) {
779  // The store to dest may never happen if the call can throw.
780  if (C->mayThrow())
781  return false;
782 
783  if (A->getDereferenceableBytes() < srcSize) {
784  // If the destination is an sret parameter then only accesses that are
785  // outside of the returned struct type can trap.
786  if (!A->hasStructRetAttr())
787  return false;
788 
789  Type *StructTy = cast<PointerType>(A->getType())->getElementType();
790  if (!StructTy->isSized()) {
791  // The call may never return and hence the copy-instruction may never
792  // be executed, and therefore it's not safe to say "the destination
793  // has at least <cpyLen> bytes, as implied by the copy-instruction",
794  return false;
795  }
796 
797  uint64_t destSize = DL.getTypeAllocSize(StructTy);
798  if (destSize < srcSize)
799  return false;
800  }
801  } else {
802  return false;
803  }
804 
805  // Check that dest points to memory that is at least as aligned as src.
806  unsigned srcAlign = srcAlloca->getAlignment();
807  if (!srcAlign)
808  srcAlign = DL.getABITypeAlignment(srcAlloca->getAllocatedType());
809  bool isDestSufficientlyAligned = srcAlign <= cpyAlign;
810  // If dest is not aligned enough and we can't increase its alignment then
811  // bail out.
812  if (!isDestSufficientlyAligned && !isa<AllocaInst>(cpyDest))
813  return false;
814 
815  // Check that src is not accessed except via the call and the memcpy. This
816  // guarantees that it holds only undefined values when passed in (so the final
817  // memcpy can be dropped), that it is not read or written between the call and
818  // the memcpy, and that writing beyond the end of it is undefined.
819  SmallVector<User*, 8> srcUseList(srcAlloca->user_begin(),
820  srcAlloca->user_end());
821  while (!srcUseList.empty()) {
822  User *U = srcUseList.pop_back_val();
823 
824  if (isa<BitCastInst>(U) || isa<AddrSpaceCastInst>(U)) {
825  for (User *UU : U->users())
826  srcUseList.push_back(UU);
827  continue;
828  }
829  if (GetElementPtrInst *G = dyn_cast<GetElementPtrInst>(U)) {
830  if (!G->hasAllZeroIndices())
831  return false;
832 
833  for (User *UU : U->users())
834  srcUseList.push_back(UU);
835  continue;
836  }
837  if (const IntrinsicInst *IT = dyn_cast<IntrinsicInst>(U))
838  if (IT->isLifetimeStartOrEnd())
839  continue;
840 
841  if (U != C && U != cpy)
842  return false;
843  }
844 
845  // Check that src isn't captured by the called function since the
846  // transformation can cause aliasing issues in that case.
847  for (unsigned i = 0, e = CS.arg_size(); i != e; ++i)
848  if (CS.getArgument(i) == cpySrc && !CS.doesNotCapture(i))
849  return false;
850 
851  // Since we're changing the parameter to the callsite, we need to make sure
852  // that what would be the new parameter dominates the callsite.
853  DominatorTree &DT = LookupDomTree();
854  if (Instruction *cpyDestInst = dyn_cast<Instruction>(cpyDest))
855  if (!DT.dominates(cpyDestInst, C))
856  return false;
857 
858  // In addition to knowing that the call does not access src in some
859  // unexpected manner, for example via a global, which we deduce from
860  // the use analysis, we also need to know that it does not sneakily
861  // access dest. We rely on AA to figure this out for us.
862  AliasAnalysis &AA = LookupAliasAnalysis();
863  ModRefInfo MR = AA.getModRefInfo(C, cpyDest, LocationSize::precise(srcSize));
864  // If necessary, perform additional analysis.
865  if (isModOrRefSet(MR))
866  MR = AA.callCapturesBefore(C, cpyDest, LocationSize::precise(srcSize), &DT);
867  if (isModOrRefSet(MR))
868  return false;
869 
870  // We can't create address space casts here because we don't know if they're
871  // safe for the target.
872  if (cpySrc->getType()->getPointerAddressSpace() !=
873  cpyDest->getType()->getPointerAddressSpace())
874  return false;
875  for (unsigned i = 0; i < CS.arg_size(); ++i)
876  if (CS.getArgument(i)->stripPointerCasts() == cpySrc &&
877  cpySrc->getType()->getPointerAddressSpace() !=
879  return false;
880 
881  // All the checks have passed, so do the transformation.
882  bool changedArgument = false;
883  for (unsigned i = 0; i < CS.arg_size(); ++i)
884  if (CS.getArgument(i)->stripPointerCasts() == cpySrc) {
885  Value *Dest = cpySrc->getType() == cpyDest->getType() ? cpyDest
886  : CastInst::CreatePointerCast(cpyDest, cpySrc->getType(),
887  cpyDest->getName(), C);
888  changedArgument = true;
889  if (CS.getArgument(i)->getType() == Dest->getType())
890  CS.setArgument(i, Dest);
891  else
893  CS.getArgument(i)->getType(), Dest->getName(), C));
894  }
895 
896  if (!changedArgument)
897  return false;
898 
899  // If the destination wasn't sufficiently aligned then increase its alignment.
900  if (!isDestSufficientlyAligned) {
901  assert(isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!");
902  cast<AllocaInst>(cpyDest)->setAlignment(MaybeAlign(srcAlign));
903  }
904 
905  // Drop any cached information about the call, because we may have changed
906  // its dependence information by changing its parameter.
907  MD->removeInstruction(C);
908 
909  // Update AA metadata
910  // FIXME: MD_tbaa_struct and MD_mem_parallel_loop_access should also be
911  // handled here, but combineMetadata doesn't support them yet
912  unsigned KnownIDs[] = {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
913  LLVMContext::MD_noalias,
914  LLVMContext::MD_invariant_group,
915  LLVMContext::MD_access_group};
916  combineMetadata(C, cpy, KnownIDs, true);
917 
918  // Remove the memcpy.
919  MD->removeInstruction(cpy);
920  ++NumMemCpyInstr;
921 
922  return true;
923 }
924 
925 /// We've found that the (upward scanning) memory dependence of memcpy 'M' is
926 /// the memcpy 'MDep'. Try to simplify M to copy from MDep's input if we can.
927 bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M,
928  MemCpyInst *MDep) {
929  // We can only transforms memcpy's where the dest of one is the source of the
930  // other.
931  if (M->getSource() != MDep->getDest() || MDep->isVolatile())
932  return false;
933 
934  // If dep instruction is reading from our current input, then it is a noop
935  // transfer and substituting the input won't change this instruction. Just
936  // ignore the input and let someone else zap MDep. This handles cases like:
937  // memcpy(a <- a)
938  // memcpy(b <- a)
939  if (M->getSource() == MDep->getSource())
940  return false;
941 
942  // Second, the length of the memcpy's must be the same, or the preceding one
943  // must be larger than the following one.
944  ConstantInt *MDepLen = dyn_cast<ConstantInt>(MDep->getLength());
945  ConstantInt *MLen = dyn_cast<ConstantInt>(M->getLength());
946  if (!MDepLen || !MLen || MDepLen->getZExtValue() < MLen->getZExtValue())
947  return false;
948 
949  AliasAnalysis &AA = LookupAliasAnalysis();
950 
951  // Verify that the copied-from memory doesn't change in between the two
952  // transfers. For example, in:
953  // memcpy(a <- b)
954  // *b = 42;
955  // memcpy(c <- a)
956  // It would be invalid to transform the second memcpy into memcpy(c <- b).
957  //
958  // TODO: If the code between M and MDep is transparent to the destination "c",
959  // then we could still perform the xform by moving M up to the first memcpy.
960  //
961  // NOTE: This is conservative, it will stop on any read from the source loc,
962  // not just the defining memcpy.
963  MemDepResult SourceDep =
964  MD->getPointerDependencyFrom(MemoryLocation::getForSource(MDep), false,
965  M->getIterator(), M->getParent());
966  if (!SourceDep.isClobber() || SourceDep.getInst() != MDep)
967  return false;
968 
969  // If the dest of the second might alias the source of the first, then the
970  // source and dest might overlap. We still want to eliminate the intermediate
971  // value, but we have to generate a memmove instead of memcpy.
972  bool UseMemMove = false;
975  UseMemMove = true;
976 
977  // If all checks passed, then we can transform M.
978  LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy->memcpy src:\n"
979  << *MDep << '\n' << *M << '\n');
980 
981  // TODO: Is this worth it if we're creating a less aligned memcpy? For
982  // example we could be moving from movaps -> movq on x86.
983  IRBuilder<> Builder(M);
984  if (UseMemMove)
985  Builder.CreateMemMove(M->getRawDest(), M->getDestAlignment(),
986  MDep->getRawSource(), MDep->getSourceAlignment(),
987  M->getLength(), M->isVolatile());
988  else
989  Builder.CreateMemCpy(M->getRawDest(), M->getDestAlignment(),
990  MDep->getRawSource(), MDep->getSourceAlignment(),
991  M->getLength(), M->isVolatile());
992 
993  // Remove the instruction we're replacing.
994  MD->removeInstruction(M);
995  M->eraseFromParent();
996  ++NumMemCpyInstr;
997  return true;
998 }
999 
1000 /// We've found that the (upward scanning) memory dependence of \p MemCpy is
1001 /// \p MemSet. Try to simplify \p MemSet to only set the trailing bytes that
1002 /// weren't copied over by \p MemCpy.
1003 ///
1004 /// In other words, transform:
1005 /// \code
1006 /// memset(dst, c, dst_size);
1007 /// memcpy(dst, src, src_size);
1008 /// \endcode
1009 /// into:
1010 /// \code
1011 /// memcpy(dst, src, src_size);
1012 /// memset(dst + src_size, c, dst_size <= src_size ? 0 : dst_size - src_size);
1013 /// \endcode
1014 bool MemCpyOptPass::processMemSetMemCpyDependence(MemCpyInst *MemCpy,
1015  MemSetInst *MemSet) {
1016  // We can only transform memset/memcpy with the same destination.
1017  if (MemSet->getDest() != MemCpy->getDest())
1018  return false;
1019 
1020  // Check that there are no other dependencies on the memset destination.
1021  MemDepResult DstDepInfo =
1022  MD->getPointerDependencyFrom(MemoryLocation::getForDest(MemSet), false,
1023  MemCpy->getIterator(), MemCpy->getParent());
1024  if (DstDepInfo.getInst() != MemSet)
1025  return false;
1026 
1027  // Use the same i8* dest as the memcpy, killing the memset dest if different.
1028  Value *Dest = MemCpy->getRawDest();
1029  Value *DestSize = MemSet->getLength();
1030  Value *SrcSize = MemCpy->getLength();
1031 
1032  // By default, create an unaligned memset.
1033  unsigned Align = 1;
1034  // If Dest is aligned, and SrcSize is constant, use the minimum alignment
1035  // of the sum.
1036  const unsigned DestAlign =
1037  std::max(MemSet->getDestAlignment(), MemCpy->getDestAlignment());
1038  if (DestAlign > 1)
1039  if (ConstantInt *SrcSizeC = dyn_cast<ConstantInt>(SrcSize))
1040  Align = MinAlign(SrcSizeC->getZExtValue(), DestAlign);
1041 
1042  IRBuilder<> Builder(MemCpy);
1043 
1044  // If the sizes have different types, zext the smaller one.
1045  if (DestSize->getType() != SrcSize->getType()) {
1046  if (DestSize->getType()->getIntegerBitWidth() >
1047  SrcSize->getType()->getIntegerBitWidth())
1048  SrcSize = Builder.CreateZExt(SrcSize, DestSize->getType());
1049  else
1050  DestSize = Builder.CreateZExt(DestSize, SrcSize->getType());
1051  }
1052 
1053  Value *Ule = Builder.CreateICmpULE(DestSize, SrcSize);
1054  Value *SizeDiff = Builder.CreateSub(DestSize, SrcSize);
1055  Value *MemsetLen = Builder.CreateSelect(
1056  Ule, ConstantInt::getNullValue(DestSize->getType()), SizeDiff);
1057  Builder.CreateMemSet(
1058  Builder.CreateGEP(Dest->getType()->getPointerElementType(), Dest,
1059  SrcSize),
1060  MemSet->getOperand(1), MemsetLen, Align);
1061 
1062  MD->removeInstruction(MemSet);
1063  MemSet->eraseFromParent();
1064  return true;
1065 }
1066 
1067 /// Determine whether the instruction has undefined content for the given Size,
1068 /// either because it was freshly alloca'd or started its lifetime.
1069 static bool hasUndefContents(Instruction *I, ConstantInt *Size) {
1070  if (isa<AllocaInst>(I))
1071  return true;
1072 
1073  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
1074  if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1075  if (ConstantInt *LTSize = dyn_cast<ConstantInt>(II->getArgOperand(0)))
1076  if (LTSize->getZExtValue() >= Size->getZExtValue())
1077  return true;
1078 
1079  return false;
1080 }
1081 
1082 /// Transform memcpy to memset when its source was just memset.
1083 /// In other words, turn:
1084 /// \code
1085 /// memset(dst1, c, dst1_size);
1086 /// memcpy(dst2, dst1, dst2_size);
1087 /// \endcode
1088 /// into:
1089 /// \code
1090 /// memset(dst1, c, dst1_size);
1091 /// memset(dst2, c, dst2_size);
1092 /// \endcode
1093 /// When dst2_size <= dst1_size.
1094 ///
1095 /// The \p MemCpy must have a Constant length.
1096 bool MemCpyOptPass::performMemCpyToMemSetOptzn(MemCpyInst *MemCpy,
1097  MemSetInst *MemSet) {
1098  AliasAnalysis &AA = LookupAliasAnalysis();
1099 
1100  // Make sure that memcpy(..., memset(...), ...), that is we are memsetting and
1101  // memcpying from the same address. Otherwise it is hard to reason about.
1102  if (!AA.isMustAlias(MemSet->getRawDest(), MemCpy->getRawSource()))
1103  return false;
1104 
1105  // A known memset size is required.
1106  ConstantInt *MemSetSize = dyn_cast<ConstantInt>(MemSet->getLength());
1107  if (!MemSetSize)
1108  return false;
1109 
1110  // Make sure the memcpy doesn't read any more than what the memset wrote.
1111  // Don't worry about sizes larger than i64.
1112  ConstantInt *CopySize = cast<ConstantInt>(MemCpy->getLength());
1113  if (CopySize->getZExtValue() > MemSetSize->getZExtValue()) {
1114  // If the memcpy is larger than the memset, but the memory was undef prior
1115  // to the memset, we can just ignore the tail. Technically we're only
1116  // interested in the bytes from MemSetSize..CopySize here, but as we can't
1117  // easily represent this location, we use the full 0..CopySize range.
1118  MemoryLocation MemCpyLoc = MemoryLocation::getForSource(MemCpy);
1119  MemDepResult DepInfo = MD->getPointerDependencyFrom(
1120  MemCpyLoc, true, MemSet->getIterator(), MemSet->getParent());
1121  if (DepInfo.isDef() && hasUndefContents(DepInfo.getInst(), CopySize))
1122  CopySize = MemSetSize;
1123  else
1124  return false;
1125  }
1126 
1127  IRBuilder<> Builder(MemCpy);
1128  Builder.CreateMemSet(MemCpy->getRawDest(), MemSet->getOperand(1),
1129  CopySize, MemCpy->getDestAlignment());
1130  return true;
1131 }
1132 
1133 /// Perform simplification of memcpy's. If we have memcpy A
1134 /// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite
1135 /// B to be a memcpy from X to Z (or potentially a memmove, depending on
1136 /// circumstances). This allows later passes to remove the first memcpy
1137 /// altogether.
1138 bool MemCpyOptPass::processMemCpy(MemCpyInst *M) {
1139  // We can only optimize non-volatile memcpy's.
1140  if (M->isVolatile()) return false;
1141 
1142  // If the source and destination of the memcpy are the same, then zap it.
1143  if (M->getSource() == M->getDest()) {
1144  MD->removeInstruction(M);
1145  M->eraseFromParent();
1146  return false;
1147  }
1148 
1149  // If copying from a constant, try to turn the memcpy into a memset.
1150  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getSource()))
1151  if (GV->isConstant() && GV->hasDefinitiveInitializer())
1152  if (Value *ByteVal = isBytewiseValue(GV->getInitializer(),
1153  M->getModule()->getDataLayout())) {
1154  IRBuilder<> Builder(M);
1155  Builder.CreateMemSet(M->getRawDest(), ByteVal, M->getLength(),
1156  M->getDestAlignment(), false);
1157  MD->removeInstruction(M);
1158  M->eraseFromParent();
1159  ++NumCpyToSet;
1160  return true;
1161  }
1162 
1163  MemDepResult DepInfo = MD->getDependency(M);
1164 
1165  // Try to turn a partially redundant memset + memcpy into
1166  // memcpy + smaller memset. We don't need the memcpy size for this.
1167  if (DepInfo.isClobber())
1168  if (MemSetInst *MDep = dyn_cast<MemSetInst>(DepInfo.getInst()))
1169  if (processMemSetMemCpyDependence(M, MDep))
1170  return true;
1171 
1172  // The optimizations after this point require the memcpy size.
1173  ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength());
1174  if (!CopySize) return false;
1175 
1176  // There are four possible optimizations we can do for memcpy:
1177  // a) memcpy-memcpy xform which exposes redundance for DSE.
1178  // b) call-memcpy xform for return slot optimization.
1179  // c) memcpy from freshly alloca'd space or space that has just started its
1180  // lifetime copies undefined data, and we can therefore eliminate the
1181  // memcpy in favor of the data that was already at the destination.
1182  // d) memcpy from a just-memset'd source can be turned into memset.
1183  if (DepInfo.isClobber()) {
1184  if (CallInst *C = dyn_cast<CallInst>(DepInfo.getInst())) {
1185  // FIXME: Can we pass in either of dest/src alignment here instead
1186  // of conservatively taking the minimum?
1187  unsigned Align = MinAlign(M->getDestAlignment(), M->getSourceAlignment());
1188  if (performCallSlotOptzn(M, M->getDest(), M->getSource(),
1189  CopySize->getZExtValue(), Align,
1190  C)) {
1191  MD->removeInstruction(M);
1192  M->eraseFromParent();
1193  return true;
1194  }
1195  }
1196  }
1197 
1199  MemDepResult SrcDepInfo = MD->getPointerDependencyFrom(
1200  SrcLoc, true, M->getIterator(), M->getParent());
1201 
1202  if (SrcDepInfo.isClobber()) {
1203  if (MemCpyInst *MDep = dyn_cast<MemCpyInst>(SrcDepInfo.getInst()))
1204  return processMemCpyMemCpyDependence(M, MDep);
1205  } else if (SrcDepInfo.isDef()) {
1206  if (hasUndefContents(SrcDepInfo.getInst(), CopySize)) {
1207  MD->removeInstruction(M);
1208  M->eraseFromParent();
1209  ++NumMemCpyInstr;
1210  return true;
1211  }
1212  }
1213 
1214  if (SrcDepInfo.isClobber())
1215  if (MemSetInst *MDep = dyn_cast<MemSetInst>(SrcDepInfo.getInst()))
1216  if (performMemCpyToMemSetOptzn(M, MDep)) {
1217  MD->removeInstruction(M);
1218  M->eraseFromParent();
1219  ++NumCpyToSet;
1220  return true;
1221  }
1222 
1223  return false;
1224 }
1225 
1226 /// Transforms memmove calls to memcpy calls when the src/dst are guaranteed
1227 /// not to alias.
1228 bool MemCpyOptPass::processMemMove(MemMoveInst *M) {
1229  AliasAnalysis &AA = LookupAliasAnalysis();
1230 
1231  if (!TLI->has(LibFunc_memmove))
1232  return false;
1233 
1234  // See if the pointers alias.
1237  return false;
1238 
1239  LLVM_DEBUG(dbgs() << "MemCpyOptPass: Optimizing memmove -> memcpy: " << *M
1240  << "\n");
1241 
1242  // If not, then we know we can transform this.
1243  Type *ArgTys[3] = { M->getRawDest()->getType(),
1244  M->getRawSource()->getType(),
1245  M->getLength()->getType() };
1247  Intrinsic::memcpy, ArgTys));
1248 
1249  // MemDep may have over conservative information about this instruction, just
1250  // conservatively flush it from the cache.
1251  MD->removeInstruction(M);
1252 
1253  ++NumMoveToCpy;
1254  return true;
1255 }
1256 
1257 /// This is called on every byval argument in call sites.
1258 bool MemCpyOptPass::processByValArgument(CallSite CS, unsigned ArgNo) {
1259  const DataLayout &DL = CS.getCaller()->getParent()->getDataLayout();
1260  // Find out what feeds this byval argument.
1261  Value *ByValArg = CS.getArgument(ArgNo);
1262  Type *ByValTy = cast<PointerType>(ByValArg->getType())->getElementType();
1263  uint64_t ByValSize = DL.getTypeAllocSize(ByValTy);
1264  MemDepResult DepInfo = MD->getPointerDependencyFrom(
1265  MemoryLocation(ByValArg, LocationSize::precise(ByValSize)), true,
1267  if (!DepInfo.isClobber())
1268  return false;
1269 
1270  // If the byval argument isn't fed by a memcpy, ignore it. If it is fed by
1271  // a memcpy, see if we can byval from the source of the memcpy instead of the
1272  // result.
1273  MemCpyInst *MDep = dyn_cast<MemCpyInst>(DepInfo.getInst());
1274  if (!MDep || MDep->isVolatile() ||
1275  ByValArg->stripPointerCasts() != MDep->getDest())
1276  return false;
1277 
1278  // The length of the memcpy must be larger or equal to the size of the byval.
1279  ConstantInt *C1 = dyn_cast<ConstantInt>(MDep->getLength());
1280  if (!C1 || C1->getValue().getZExtValue() < ByValSize)
1281  return false;
1282 
1283  // Get the alignment of the byval. If the call doesn't specify the alignment,
1284  // then it is some target specific value that we can't know.
1285  unsigned ByValAlign = CS.getParamAlignment(ArgNo);
1286  if (ByValAlign == 0) return false;
1287 
1288  // If it is greater than the memcpy, then we check to see if we can force the
1289  // source of the memcpy to the alignment we need. If we fail, we bail out.
1290  AssumptionCache &AC = LookupAssumptionCache();
1291  DominatorTree &DT = LookupDomTree();
1292  if (MDep->getSourceAlignment() < ByValAlign &&
1293  getOrEnforceKnownAlignment(MDep->getSource(), ByValAlign, DL,
1294  CS.getInstruction(), &AC, &DT) < ByValAlign)
1295  return false;
1296 
1297  // The address space of the memcpy source must match the byval argument
1298  if (MDep->getSource()->getType()->getPointerAddressSpace() !=
1299  ByValArg->getType()->getPointerAddressSpace())
1300  return false;
1301 
1302  // Verify that the copied-from memory doesn't change in between the memcpy and
1303  // the byval call.
1304  // memcpy(a <- b)
1305  // *b = 42;
1306  // foo(*a)
1307  // It would be invalid to transform the second memcpy into foo(*b).
1308  //
1309  // NOTE: This is conservative, it will stop on any read from the source loc,
1310  // not just the defining memcpy.
1311  MemDepResult SourceDep = MD->getPointerDependencyFrom(
1312  MemoryLocation::getForSource(MDep), false,
1313  CS.getInstruction()->getIterator(), MDep->getParent());
1314  if (!SourceDep.isClobber() || SourceDep.getInst() != MDep)
1315  return false;
1316 
1317  Value *TmpCast = MDep->getSource();
1318  if (MDep->getSource()->getType() != ByValArg->getType())
1319  TmpCast = new BitCastInst(MDep->getSource(), ByValArg->getType(),
1320  "tmpcast", CS.getInstruction());
1321 
1322  LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"
1323  << " " << *MDep << "\n"
1324  << " " << *CS.getInstruction() << "\n");
1325 
1326  // Otherwise we're good! Update the byval argument.
1327  CS.setArgument(ArgNo, TmpCast);
1328  ++NumMemCpyInstr;
1329  return true;
1330 }
1331 
1332 /// Executes one iteration of MemCpyOptPass.
1333 bool MemCpyOptPass::iterateOnFunction(Function &F) {
1334  bool MadeChange = false;
1335 
1336  DominatorTree &DT = LookupDomTree();
1337 
1338  // Walk all instruction in the function.
1339  for (BasicBlock &BB : F) {
1340  // Skip unreachable blocks. For example processStore assumes that an
1341  // instruction in a BB can't be dominated by a later instruction in the
1342  // same BB (which is a scenario that can happen for an unreachable BB that
1343  // has itself as a predecessor).
1344  if (!DT.isReachableFromEntry(&BB))
1345  continue;
1346 
1347  for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
1348  // Avoid invalidating the iterator.
1349  Instruction *I = &*BI++;
1350 
1351  bool RepeatInstruction = false;
1352 
1353  if (StoreInst *SI = dyn_cast<StoreInst>(I))
1354  MadeChange |= processStore(SI, BI);
1355  else if (MemSetInst *M = dyn_cast<MemSetInst>(I))
1356  RepeatInstruction = processMemSet(M, BI);
1357  else if (MemCpyInst *M = dyn_cast<MemCpyInst>(I))
1358  RepeatInstruction = processMemCpy(M);
1359  else if (MemMoveInst *M = dyn_cast<MemMoveInst>(I))
1360  RepeatInstruction = processMemMove(M);
1361  else if (auto CS = CallSite(I)) {
1362  for (unsigned i = 0, e = CS.arg_size(); i != e; ++i)
1363  if (CS.isByValArgument(i))
1364  MadeChange |= processByValArgument(CS, i);
1365  }
1366 
1367  // Reprocess the instruction if desired.
1368  if (RepeatInstruction) {
1369  if (BI != BB.begin())
1370  --BI;
1371  MadeChange = true;
1372  }
1373  }
1374  }
1375 
1376  return MadeChange;
1377 }
1378 
1380  auto &MD = AM.getResult<MemoryDependenceAnalysis>(F);
1381  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1382 
1383  auto LookupAliasAnalysis = [&]() -> AliasAnalysis & {
1384  return AM.getResult<AAManager>(F);
1385  };
1386  auto LookupAssumptionCache = [&]() -> AssumptionCache & {
1387  return AM.getResult<AssumptionAnalysis>(F);
1388  };
1389  auto LookupDomTree = [&]() -> DominatorTree & {
1390  return AM.getResult<DominatorTreeAnalysis>(F);
1391  };
1392 
1393  bool MadeChange = runImpl(F, &MD, &TLI, LookupAliasAnalysis,
1394  LookupAssumptionCache, LookupDomTree);
1395  if (!MadeChange)
1396  return PreservedAnalyses::all();
1397 
1398  PreservedAnalyses PA;
1399  PA.preserveSet<CFGAnalyses>();
1400  PA.preserve<GlobalsAA>();
1402  return PA;
1403 }
1404 
1407  std::function<AliasAnalysis &()> LookupAliasAnalysis_,
1408  std::function<AssumptionCache &()> LookupAssumptionCache_,
1409  std::function<DominatorTree &()> LookupDomTree_) {
1410  bool MadeChange = false;
1411  MD = MD_;
1412  TLI = TLI_;
1413  LookupAliasAnalysis = std::move(LookupAliasAnalysis_);
1414  LookupAssumptionCache = std::move(LookupAssumptionCache_);
1415  LookupDomTree = std::move(LookupDomTree_);
1416 
1417  // If we don't have at least memset and memcpy, there is little point of doing
1418  // anything here. These are required by a freestanding implementation, so if
1419  // even they are disabled, there is no point in trying hard.
1420  if (!TLI->has(LibFunc_memset) || !TLI->has(LibFunc_memcpy))
1421  return false;
1422 
1423  while (true) {
1424  if (!iterateOnFunction(F))
1425  break;
1426  MadeChange = true;
1427  }
1428 
1429  MD = nullptr;
1430  return MadeChange;
1431 }
1432 
1433 /// This is the main transformation entry point for a function.
1435  if (skipFunction(F))
1436  return false;
1437 
1438  auto *MD = &getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
1439  auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1440 
1441  auto LookupAliasAnalysis = [this]() -> AliasAnalysis & {
1442  return getAnalysis<AAResultsWrapperPass>().getAAResults();
1443  };
1444  auto LookupAssumptionCache = [this, &F]() -> AssumptionCache & {
1445  return getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1446  };
1447  auto LookupDomTree = [this]() -> DominatorTree & {
1448  return getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1449  };
1450 
1451  return Impl.runImpl(F, MD, TLI, LookupAliasAnalysis, LookupAssumptionCache,
1452  LookupDomTree);
1453 }
Legacy wrapper pass to provide the GlobalsAAResult object.
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
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...
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1571
unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, const DataLayout &DL, const Instruction *CxtI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to ensure that the alignment of V is at least PrefAlign bytes.
Definition: Local.cpp:1181
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:320
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:777
This class represents lattice values for constants.
Definition: AllocatorList.h:23
INITIALIZE_PASS_BEGIN(MemCpyOptLegacyPass, "memcpyopt", "MemCpy Optimization", false, false) INITIALIZE_PASS_END(MemCpyOptLegacyPass
This is the interface for a simple mod/ref and alias analysis over globals.
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:265
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are no-alias. ...
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
This class represents a function call, abstracting a target machine&#39;s calling convention.
An immutable pass that tracks lazily created AssumptionCache objects.
unsigned getSourceAlignment() const
Value * getValue() const
A cache of @llvm.assume calls within a function.
static LocationSize precise(uint64_t Value)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This class wraps the llvm.memset intrinsic.
STATISTIC(NumFunctions, "Total number of functions")
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:635
CallInst * CreateMemSet(Value *Ptr, Value *Val, uint64_t Size, unsigned Align, bool isVolatile=false, MDNode *TBAATag=nullptr, MDNode *ScopeTag=nullptr, MDNode *NoAliasTag=nullptr)
Create and insert a memset to the specified pointer and the specified value.
Definition: IRBuilder.h:440
An instruction for reading from memory.
Definition: Instructions.h:169
Value * CreateICmpULE(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2121
Value * getLength() const
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:299
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: CallSite.h:602
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:289
Value * getDest() const
This is just like getRawDest, but it strips off any cast instructions (including addrspacecast) that ...
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
bool isDef() const
Tests if this MemDepResult represents a query that is an instruction definition dependency.
Type * getPointerElementType() const
Definition: Type.h:381
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
unsigned getAlignment() const
Return the alignment of the memory that is being allocated by the instruction.
Definition: Instructions.h:112
static unsigned findStoreAlignment(const DataLayout &DL, const StoreInst *SI)
bool isClobber() const
Tests if this MemDepResult represents a query that is an instruction clobber dependency.
This class wraps the llvm.memmove intrinsic.
static bool hasUndefContents(Instruction *I, ConstantInt *Size)
Determine whether the instruction has undefined content for the given Size, either because it was fre...
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
An analysis that produces MemoryDependenceResults for a function.
CallInst * CreateMemMove(Value *Dst, unsigned DstAlign, Value *Src, unsigned SrcAlign, uint64_t Size, bool isVolatile=false, MDNode *TBAATag=nullptr, MDNode *ScopeTag=nullptr, MDNode *NoAliasTag=nullptr)
Create and insert a memmove between the specified pointers.
Definition: IRBuilder.h:530
unsigned getDestAlignment() const
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:261
InstrTy * getInstruction() const
Definition: CallSite.h:96
auto partition_point(R &&Range, Predicate P) -> decltype(adl_begin(Range))
Binary search for the first iterator in a range where a predicate is false.
Definition: STLExtras.h:1302
void setArgument(unsigned ArgNo, Value *newVal)
Definition: CallSite.h:198
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
TypeSize getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type...
Definition: DataLayout.h:454
void setCalledFunction(Function *Fn)
Sets the function called, including updating the function type.
Definition: InstrTypes.h:1323
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
This class represents a no-op cast from one type to another.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:244
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef< unsigned > KnownIDs, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2282
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:137
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1135
An instruction for storing to memory.
Definition: Instructions.h:325
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1877
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Function * getDeclaration(Module *M, ID id, ArrayRef< Type *> Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1093
Value * getOperand(unsigned i) const
Definition: User.h:169
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:661
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:881
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:148
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:328
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.h:2287
A manager for alias analyses.
TypeSize getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:486
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:193
bool mayThrow() const
Return true if this instruction may throw an exception.
Represent the analysis usage information of a pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1172
Analysis pass providing a never-invalidated alias analysis result.
constexpr double e
Definition: MathExtras.h:57
unsigned getLargestLegalIntTypeSizeInBits() const
Returns the size of largest legal integer type size, or 0 if none are set.
Definition: DataLayout.cpp:791
FunctionPass * createMemCpyOptPass()
The public interface to this file...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
self_iterator getIterator()
Definition: ilist_node.h:81
static CastInst * CreatePointerCast(Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd)
Create a BitCast AddrSpaceCast, or a PtrToInt cast instruction.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:529
iterator erase(const_iterator CI)
Definition: SmallVector.h:434
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
void initializeMemCpyOptLegacyPassPass(PassRegistry &)
const Value * getArraySize() const
Get the number of elements allocated.
Definition: Instructions.h:92
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance...
bool isVolatile() const
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:40
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:105
A memory dependence query can return one of three different answers.
bool runImpl(Function &F, MemoryDependenceResults *MD_, TargetLibraryInfo *TLI_, std::function< AliasAnalysis &()> LookupAliasAnalysis_, std::function< AssumptionCache &()> LookupAssumptionCache_, std::function< DominatorTree &()> LookupDomTree_)
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:197
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:86
Value * isBytewiseValue(Value *V, const DataLayout &DL)
If the specified value can be set by repeating the same byte in memory, return the i8 value that it i...
Value * CreateGEP(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &Name="")
Definition: IRBuilder.h:1676
Representation for a specific memory location.
A function analysis which provides an AssumptionCache.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:191
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
This struct is a compact representation of a valid (power of two) or undefined (0) alignment...
Definition: Alignment.h:117
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
unsigned arg_size() const
Definition: CallSite.h:226
unsigned getABITypeAlignment(Type *Ty) const
Returns the minimum ABI-required alignment for the specified type.
Definition: DataLayout.cpp:755
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
static unsigned findLoadAlignment(const DataLayout &DL, const LoadInst *LI)
CallInst * CreateMemCpy(Value *Dst, unsigned DstAlign, Value *Src, unsigned SrcAlign, uint64_t Size, bool isVolatile=false, MDNode *TBAATag=nullptr, MDNode *TBAAStructTag=nullptr, MDNode *ScopeTag=nullptr, MDNode *NoAliasTag=nullptr)
Create and insert a memcpy between the specified pointers.
Definition: IRBuilder.h:482
This class wraps the llvm.memcpy intrinsic.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
Value * getRawSource() const
Return the arguments to the instruction.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Optional< int64_t > isPointerOffset(const Value *Ptr1, const Value *Ptr2, const DataLayout &DL)
If Ptr1 is provably equal to Ptr2 plus a constant offset, return that offset.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:55
ModRefInfo callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT, OrderedBasicBlock *OBB=nullptr)
Return information about whether a particular call site modifies or reads the specified memory locati...
typename SuperClass::iterator iterator
Definition: SmallVector.h:319
iterator_range< user_iterator > users()
Definition: Value.h:420
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are must-alias.
MemCpy Optimization
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:115
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:467
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::ZeroOrMore, cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate IT block based on arch"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow deprecated IT based on ARMv8"), clEnumValN(NoRestrictedIT, "arm-no-restrict-it", "Allow IT blocks based on ARMv7")))
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
unsigned getAlignment() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:242
Instruction * getInst() const
If this is a normal dependency, returns the instruction that is depended on.
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:102
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
This file provides utility analysis objects describing memory locations.
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:190
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1287
#define I(x, y, z)
Definition: MD5.cpp:58
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:332
uint32_t Size
Definition: Profile.cpp:46
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:175
unsigned getAlignment() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:368
static void addRange(SmallVectorImpl< ConstantInt *> &EndPoints, ConstantInt *Low, ConstantInt *High)
Definition: Metadata.cpp:967
Analysis pass providing the TargetLibraryInfo.
bool isByValArgument(unsigned ArgNo) const
Determine whether this argument is passed by value.
Definition: CallSite.h:607
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:396
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
LLVM Value Representation.
Definition: Value.h:74
unsigned getParamAlignment(unsigned ArgNo) const
Extract the alignment for a call or parameter (0=unknown).
Definition: CallSite.h:414
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Value * getSource() const
This is just like getRawSource, but it strips off any cast instructions that feed it...
print Print MemDeps of function
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
LLVM_NODISCARD bool isModOrRefSet(const ModRefInfo MRI)
static bool moveUp(AliasAnalysis &AA, StoreInst *SI, Instruction *P, const LoadInst *LI)
static unsigned findCommonAlignment(const DataLayout &DL, const StoreInst *SI, const LoadInst *LI)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
bool isSimple() const
Definition: Instructions.h:407
This header defines various interfaces for pass management in LLVM.
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Value * getPointerOperand()
Definition: Instructions.h:418
Value * getRawDest() const
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
const BasicBlock * getParent() const
Definition: Instruction.h:66
an instruction to allocate memory on the stack
Definition: Instructions.h:59
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
user_iterator user_end()
Definition: Value.h:404
FunTy * getCaller() const
Return the caller function for this call site.
Definition: CallSite.h:275