LLVM API Documentation

MemCpyOptimizer.cpp
Go to the documentation of this file.
00001 //===- MemCpyOptimizer.cpp - Optimize use of memcpy and friends -----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass performs various transformations related to eliminating memcpy
00011 // calls, or transforming sets of stores into memset's.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #define DEBUG_TYPE "memcpyopt"
00016 #include "llvm/Transforms/Scalar.h"
00017 #include "llvm/ADT/SmallVector.h"
00018 #include "llvm/ADT/Statistic.h"
00019 #include "llvm/Analysis/AliasAnalysis.h"
00020 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
00021 #include "llvm/Analysis/ValueTracking.h"
00022 #include "llvm/IR/DataLayout.h"
00023 #include "llvm/IR/Dominators.h"
00024 #include "llvm/IR/GetElementPtrTypeIterator.h"
00025 #include "llvm/IR/GlobalVariable.h"
00026 #include "llvm/IR/IRBuilder.h"
00027 #include "llvm/IR/Instructions.h"
00028 #include "llvm/IR/IntrinsicInst.h"
00029 #include "llvm/Support/Debug.h"
00030 #include "llvm/Support/raw_ostream.h"
00031 #include "llvm/Target/TargetLibraryInfo.h"
00032 #include "llvm/Transforms/Utils/Local.h"
00033 #include <list>
00034 using namespace llvm;
00035 
00036 STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted");
00037 STATISTIC(NumMemSetInfer, "Number of memsets inferred");
00038 STATISTIC(NumMoveToCpy,   "Number of memmoves converted to memcpy");
00039 STATISTIC(NumCpyToSet,    "Number of memcpys converted to memset");
00040 
00041 static int64_t GetOffsetFromIndex(const GEPOperator *GEP, unsigned Idx,
00042                                   bool &VariableIdxFound, const DataLayout &TD){
00043   // Skip over the first indices.
00044   gep_type_iterator GTI = gep_type_begin(GEP);
00045   for (unsigned i = 1; i != Idx; ++i, ++GTI)
00046     /*skip along*/;
00047 
00048   // Compute the offset implied by the rest of the indices.
00049   int64_t Offset = 0;
00050   for (unsigned i = Idx, e = GEP->getNumOperands(); i != e; ++i, ++GTI) {
00051     ConstantInt *OpC = dyn_cast<ConstantInt>(GEP->getOperand(i));
00052     if (OpC == 0)
00053       return VariableIdxFound = true;
00054     if (OpC->isZero()) continue;  // No offset.
00055 
00056     // Handle struct indices, which add their field offset to the pointer.
00057     if (StructType *STy = dyn_cast<StructType>(*GTI)) {
00058       Offset += TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue());
00059       continue;
00060     }
00061 
00062     // Otherwise, we have a sequential type like an array or vector.  Multiply
00063     // the index by the ElementSize.
00064     uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType());
00065     Offset += Size*OpC->getSExtValue();
00066   }
00067 
00068   return Offset;
00069 }
00070 
00071 /// IsPointerOffset - Return true if Ptr1 is provably equal to Ptr2 plus a
00072 /// constant offset, and return that constant offset.  For example, Ptr1 might
00073 /// be &A[42], and Ptr2 might be &A[40].  In this case offset would be -8.
00074 static bool IsPointerOffset(Value *Ptr1, Value *Ptr2, int64_t &Offset,
00075                             const DataLayout &TD) {
00076   Ptr1 = Ptr1->stripPointerCasts();
00077   Ptr2 = Ptr2->stripPointerCasts();
00078 
00079   // Handle the trivial case first.
00080   if (Ptr1 == Ptr2) {
00081     Offset = 0;
00082     return true;
00083   }
00084 
00085   GEPOperator *GEP1 = dyn_cast<GEPOperator>(Ptr1);
00086   GEPOperator *GEP2 = dyn_cast<GEPOperator>(Ptr2);
00087 
00088   bool VariableIdxFound = false;
00089 
00090   // If one pointer is a GEP and the other isn't, then see if the GEP is a
00091   // constant offset from the base, as in "P" and "gep P, 1".
00092   if (GEP1 && GEP2 == 0 && GEP1->getOperand(0)->stripPointerCasts() == Ptr2) {
00093     Offset = -GetOffsetFromIndex(GEP1, 1, VariableIdxFound, TD);
00094     return !VariableIdxFound;
00095   }
00096 
00097   if (GEP2 && GEP1 == 0 && GEP2->getOperand(0)->stripPointerCasts() == Ptr1) {
00098     Offset = GetOffsetFromIndex(GEP2, 1, VariableIdxFound, TD);
00099     return !VariableIdxFound;
00100   }
00101 
00102   // Right now we handle the case when Ptr1/Ptr2 are both GEPs with an identical
00103   // base.  After that base, they may have some number of common (and
00104   // potentially variable) indices.  After that they handle some constant
00105   // offset, which determines their offset from each other.  At this point, we
00106   // handle no other case.
00107   if (!GEP1 || !GEP2 || GEP1->getOperand(0) != GEP2->getOperand(0))
00108     return false;
00109 
00110   // Skip any common indices and track the GEP types.
00111   unsigned Idx = 1;
00112   for (; Idx != GEP1->getNumOperands() && Idx != GEP2->getNumOperands(); ++Idx)
00113     if (GEP1->getOperand(Idx) != GEP2->getOperand(Idx))
00114       break;
00115 
00116   int64_t Offset1 = GetOffsetFromIndex(GEP1, Idx, VariableIdxFound, TD);
00117   int64_t Offset2 = GetOffsetFromIndex(GEP2, Idx, VariableIdxFound, TD);
00118   if (VariableIdxFound) return false;
00119 
00120   Offset = Offset2-Offset1;
00121   return true;
00122 }
00123 
00124 
00125 /// MemsetRange - Represents a range of memset'd bytes with the ByteVal value.
00126 /// This allows us to analyze stores like:
00127 ///   store 0 -> P+1
00128 ///   store 0 -> P+0
00129 ///   store 0 -> P+3
00130 ///   store 0 -> P+2
00131 /// which sometimes happens with stores to arrays of structs etc.  When we see
00132 /// the first store, we make a range [1, 2).  The second store extends the range
00133 /// to [0, 2).  The third makes a new range [2, 3).  The fourth store joins the
00134 /// two ranges into [0, 3) which is memset'able.
00135 namespace {
00136 struct MemsetRange {
00137   // Start/End - A semi range that describes the span that this range covers.
00138   // The range is closed at the start and open at the end: [Start, End).
00139   int64_t Start, End;
00140 
00141   /// StartPtr - The getelementptr instruction that points to the start of the
00142   /// range.
00143   Value *StartPtr;
00144 
00145   /// Alignment - The known alignment of the first store.
00146   unsigned Alignment;
00147 
00148   /// TheStores - The actual stores that make up this range.
00149   SmallVector<Instruction*, 16> TheStores;
00150 
00151   bool isProfitableToUseMemset(const DataLayout &TD) const;
00152 
00153 };
00154 } // end anon namespace
00155 
00156 bool MemsetRange::isProfitableToUseMemset(const DataLayout &TD) const {
00157   // If we found more than 4 stores to merge or 16 bytes, use memset.
00158   if (TheStores.size() >= 4 || End-Start >= 16) return true;
00159 
00160   // If there is nothing to merge, don't do anything.
00161   if (TheStores.size() < 2) return false;
00162 
00163   // If any of the stores are a memset, then it is always good to extend the
00164   // memset.
00165   for (unsigned i = 0, e = TheStores.size(); i != e; ++i)
00166     if (!isa<StoreInst>(TheStores[i]))
00167       return true;
00168 
00169   // Assume that the code generator is capable of merging pairs of stores
00170   // together if it wants to.
00171   if (TheStores.size() == 2) return false;
00172 
00173   // If we have fewer than 8 stores, it can still be worthwhile to do this.
00174   // For example, merging 4 i8 stores into an i32 store is useful almost always.
00175   // However, merging 2 32-bit stores isn't useful on a 32-bit architecture (the
00176   // memset will be split into 2 32-bit stores anyway) and doing so can
00177   // pessimize the llvm optimizer.
00178   //
00179   // Since we don't have perfect knowledge here, make some assumptions: assume
00180   // the maximum GPR width is the same size as the largest legal integer
00181   // size. If so, check to see whether we will end up actually reducing the
00182   // number of stores used.
00183   unsigned Bytes = unsigned(End-Start);
00184   unsigned MaxIntSize = TD.getLargestLegalIntTypeSize();
00185   if (MaxIntSize == 0)
00186     MaxIntSize = 1;
00187   unsigned NumPointerStores = Bytes / MaxIntSize;
00188 
00189   // Assume the remaining bytes if any are done a byte at a time.
00190   unsigned NumByteStores = Bytes - NumPointerStores * MaxIntSize;
00191 
00192   // If we will reduce the # stores (according to this heuristic), do the
00193   // transformation.  This encourages merging 4 x i8 -> i32 and 2 x i16 -> i32
00194   // etc.
00195   return TheStores.size() > NumPointerStores+NumByteStores;
00196 }
00197 
00198 
00199 namespace {
00200 class MemsetRanges {
00201   /// Ranges - A sorted list of the memset ranges.  We use std::list here
00202   /// because each element is relatively large and expensive to copy.
00203   std::list<MemsetRange> Ranges;
00204   typedef std::list<MemsetRange>::iterator range_iterator;
00205   const DataLayout &DL;
00206 public:
00207   MemsetRanges(const DataLayout &DL) : DL(DL) {}
00208 
00209   typedef std::list<MemsetRange>::const_iterator const_iterator;
00210   const_iterator begin() const { return Ranges.begin(); }
00211   const_iterator end() const { return Ranges.end(); }
00212   bool empty() const { return Ranges.empty(); }
00213 
00214   void addInst(int64_t OffsetFromFirst, Instruction *Inst) {
00215     if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
00216       addStore(OffsetFromFirst, SI);
00217     else
00218       addMemSet(OffsetFromFirst, cast<MemSetInst>(Inst));
00219   }
00220 
00221   void addStore(int64_t OffsetFromFirst, StoreInst *SI) {
00222     int64_t StoreSize = DL.getTypeStoreSize(SI->getOperand(0)->getType());
00223 
00224     addRange(OffsetFromFirst, StoreSize,
00225              SI->getPointerOperand(), SI->getAlignment(), SI);
00226   }
00227 
00228   void addMemSet(int64_t OffsetFromFirst, MemSetInst *MSI) {
00229     int64_t Size = cast<ConstantInt>(MSI->getLength())->getZExtValue();
00230     addRange(OffsetFromFirst, Size, MSI->getDest(), MSI->getAlignment(), MSI);
00231   }
00232 
00233   void addRange(int64_t Start, int64_t Size, Value *Ptr,
00234                 unsigned Alignment, Instruction *Inst);
00235 
00236 };
00237 
00238 } // end anon namespace
00239 
00240 
00241 /// addRange - Add a new store to the MemsetRanges data structure.  This adds a
00242 /// new range for the specified store at the specified offset, merging into
00243 /// existing ranges as appropriate.
00244 ///
00245 /// Do a linear search of the ranges to see if this can be joined and/or to
00246 /// find the insertion point in the list.  We keep the ranges sorted for
00247 /// simplicity here.  This is a linear search of a linked list, which is ugly,
00248 /// however the number of ranges is limited, so this won't get crazy slow.
00249 void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr,
00250                             unsigned Alignment, Instruction *Inst) {
00251   int64_t End = Start+Size;
00252   range_iterator I = Ranges.begin(), E = Ranges.end();
00253 
00254   while (I != E && Start > I->End)
00255     ++I;
00256 
00257   // We now know that I == E, in which case we didn't find anything to merge
00258   // with, or that Start <= I->End.  If End < I->Start or I == E, then we need
00259   // to insert a new range.  Handle this now.
00260   if (I == E || End < I->Start) {
00261     MemsetRange &R = *Ranges.insert(I, MemsetRange());
00262     R.Start        = Start;
00263     R.End          = End;
00264     R.StartPtr     = Ptr;
00265     R.Alignment    = Alignment;
00266     R.TheStores.push_back(Inst);
00267     return;
00268   }
00269 
00270   // This store overlaps with I, add it.
00271   I->TheStores.push_back(Inst);
00272 
00273   // At this point, we may have an interval that completely contains our store.
00274   // If so, just add it to the interval and return.
00275   if (I->Start <= Start && I->End >= End)
00276     return;
00277 
00278   // Now we know that Start <= I->End and End >= I->Start so the range overlaps
00279   // but is not entirely contained within the range.
00280 
00281   // See if the range extends the start of the range.  In this case, it couldn't
00282   // possibly cause it to join the prior range, because otherwise we would have
00283   // stopped on *it*.
00284   if (Start < I->Start) {
00285     I->Start = Start;
00286     I->StartPtr = Ptr;
00287     I->Alignment = Alignment;
00288   }
00289 
00290   // Now we know that Start <= I->End and Start >= I->Start (so the startpoint
00291   // is in or right at the end of I), and that End >= I->Start.  Extend I out to
00292   // End.
00293   if (End > I->End) {
00294     I->End = End;
00295     range_iterator NextI = I;
00296     while (++NextI != E && End >= NextI->Start) {
00297       // Merge the range in.
00298       I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end());
00299       if (NextI->End > I->End)
00300         I->End = NextI->End;
00301       Ranges.erase(NextI);
00302       NextI = I;
00303     }
00304   }
00305 }
00306 
00307 //===----------------------------------------------------------------------===//
00308 //                         MemCpyOpt Pass
00309 //===----------------------------------------------------------------------===//
00310 
00311 namespace {
00312   class MemCpyOpt : public FunctionPass {
00313     MemoryDependenceAnalysis *MD;
00314     TargetLibraryInfo *TLI;
00315     const DataLayout *DL;
00316   public:
00317     static char ID; // Pass identification, replacement for typeid
00318     MemCpyOpt() : FunctionPass(ID) {
00319       initializeMemCpyOptPass(*PassRegistry::getPassRegistry());
00320       MD = 0;
00321       TLI = 0;
00322       DL = 0;
00323     }
00324 
00325     bool runOnFunction(Function &F) override;
00326 
00327   private:
00328     // This transformation requires dominator postdominator info
00329     void getAnalysisUsage(AnalysisUsage &AU) const override {
00330       AU.setPreservesCFG();
00331       AU.addRequired<DominatorTreeWrapperPass>();
00332       AU.addRequired<MemoryDependenceAnalysis>();
00333       AU.addRequired<AliasAnalysis>();
00334       AU.addRequired<TargetLibraryInfo>();
00335       AU.addPreserved<AliasAnalysis>();
00336       AU.addPreserved<MemoryDependenceAnalysis>();
00337     }
00338 
00339     // Helper fuctions
00340     bool processStore(StoreInst *SI, BasicBlock::iterator &BBI);
00341     bool processMemSet(MemSetInst *SI, BasicBlock::iterator &BBI);
00342     bool processMemCpy(MemCpyInst *M);
00343     bool processMemMove(MemMoveInst *M);
00344     bool performCallSlotOptzn(Instruction *cpy, Value *cpyDst, Value *cpySrc,
00345                               uint64_t cpyLen, unsigned cpyAlign, CallInst *C);
00346     bool processMemCpyMemCpyDependence(MemCpyInst *M, MemCpyInst *MDep,
00347                                        uint64_t MSize);
00348     bool processByValArgument(CallSite CS, unsigned ArgNo);
00349     Instruction *tryMergingIntoMemset(Instruction *I, Value *StartPtr,
00350                                       Value *ByteVal);
00351 
00352     bool iterateOnFunction(Function &F);
00353   };
00354 
00355   char MemCpyOpt::ID = 0;
00356 }
00357 
00358 // createMemCpyOptPass - The public interface to this file...
00359 FunctionPass *llvm::createMemCpyOptPass() { return new MemCpyOpt(); }
00360 
00361 INITIALIZE_PASS_BEGIN(MemCpyOpt, "memcpyopt", "MemCpy Optimization",
00362                       false, false)
00363 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
00364 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
00365 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
00366 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
00367 INITIALIZE_PASS_END(MemCpyOpt, "memcpyopt", "MemCpy Optimization",
00368                     false, false)
00369 
00370 /// tryMergingIntoMemset - When scanning forward over instructions, we look for
00371 /// some other patterns to fold away.  In particular, this looks for stores to
00372 /// neighboring locations of memory.  If it sees enough consecutive ones, it
00373 /// attempts to merge them together into a memcpy/memset.
00374 Instruction *MemCpyOpt::tryMergingIntoMemset(Instruction *StartInst,
00375                                              Value *StartPtr, Value *ByteVal) {
00376   if (DL == 0) return 0;
00377 
00378   // Okay, so we now have a single store that can be splatable.  Scan to find
00379   // all subsequent stores of the same value to offset from the same pointer.
00380   // Join these together into ranges, so we can decide whether contiguous blocks
00381   // are stored.
00382   MemsetRanges Ranges(*DL);
00383 
00384   BasicBlock::iterator BI = StartInst;
00385   for (++BI; !isa<TerminatorInst>(BI); ++BI) {
00386     if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) {
00387       // If the instruction is readnone, ignore it, otherwise bail out.  We
00388       // don't even allow readonly here because we don't want something like:
00389       // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A).
00390       if (BI->mayWriteToMemory() || BI->mayReadFromMemory())
00391         break;
00392       continue;
00393     }
00394 
00395     if (StoreInst *NextStore = dyn_cast<StoreInst>(BI)) {
00396       // If this is a store, see if we can merge it in.
00397       if (!NextStore->isSimple()) break;
00398 
00399       // Check to see if this stored value is of the same byte-splattable value.
00400       if (ByteVal != isBytewiseValue(NextStore->getOperand(0)))
00401         break;
00402 
00403       // Check to see if this store is to a constant offset from the start ptr.
00404       int64_t Offset;
00405       if (!IsPointerOffset(StartPtr, NextStore->getPointerOperand(),
00406                            Offset, *DL))
00407         break;
00408 
00409       Ranges.addStore(Offset, NextStore);
00410     } else {
00411       MemSetInst *MSI = cast<MemSetInst>(BI);
00412 
00413       if (MSI->isVolatile() || ByteVal != MSI->getValue() ||
00414           !isa<ConstantInt>(MSI->getLength()))
00415         break;
00416 
00417       // Check to see if this store is to a constant offset from the start ptr.
00418       int64_t Offset;
00419       if (!IsPointerOffset(StartPtr, MSI->getDest(), Offset, *DL))
00420         break;
00421 
00422       Ranges.addMemSet(Offset, MSI);
00423     }
00424   }
00425 
00426   // If we have no ranges, then we just had a single store with nothing that
00427   // could be merged in.  This is a very common case of course.
00428   if (Ranges.empty())
00429     return 0;
00430 
00431   // If we had at least one store that could be merged in, add the starting
00432   // store as well.  We try to avoid this unless there is at least something
00433   // interesting as a small compile-time optimization.
00434   Ranges.addInst(0, StartInst);
00435 
00436   // If we create any memsets, we put it right before the first instruction that
00437   // isn't part of the memset block.  This ensure that the memset is dominated
00438   // by any addressing instruction needed by the start of the block.
00439   IRBuilder<> Builder(BI);
00440 
00441   // Now that we have full information about ranges, loop over the ranges and
00442   // emit memset's for anything big enough to be worthwhile.
00443   Instruction *AMemSet = 0;
00444   for (MemsetRanges::const_iterator I = Ranges.begin(), E = Ranges.end();
00445        I != E; ++I) {
00446     const MemsetRange &Range = *I;
00447 
00448     if (Range.TheStores.size() == 1) continue;
00449 
00450     // If it is profitable to lower this range to memset, do so now.
00451     if (!Range.isProfitableToUseMemset(*DL))
00452       continue;
00453 
00454     // Otherwise, we do want to transform this!  Create a new memset.
00455     // Get the starting pointer of the block.
00456     StartPtr = Range.StartPtr;
00457 
00458     // Determine alignment
00459     unsigned Alignment = Range.Alignment;
00460     if (Alignment == 0) {
00461       Type *EltType =
00462         cast<PointerType>(StartPtr->getType())->getElementType();
00463       Alignment = DL->getABITypeAlignment(EltType);
00464     }
00465 
00466     AMemSet =
00467       Builder.CreateMemSet(StartPtr, ByteVal, Range.End-Range.Start, Alignment);
00468 
00469     DEBUG(dbgs() << "Replace stores:\n";
00470           for (unsigned i = 0, e = Range.TheStores.size(); i != e; ++i)
00471             dbgs() << *Range.TheStores[i] << '\n';
00472           dbgs() << "With: " << *AMemSet << '\n');
00473 
00474     if (!Range.TheStores.empty())
00475       AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc());
00476 
00477     // Zap all the stores.
00478     for (SmallVectorImpl<Instruction *>::const_iterator
00479          SI = Range.TheStores.begin(),
00480          SE = Range.TheStores.end(); SI != SE; ++SI) {
00481       MD->removeInstruction(*SI);
00482       (*SI)->eraseFromParent();
00483     }
00484     ++NumMemSetInfer;
00485   }
00486 
00487   return AMemSet;
00488 }
00489 
00490 
00491 bool MemCpyOpt::processStore(StoreInst *SI, BasicBlock::iterator &BBI) {
00492   if (!SI->isSimple()) return false;
00493 
00494   if (DL == 0) return false;
00495 
00496   // Detect cases where we're performing call slot forwarding, but
00497   // happen to be using a load-store pair to implement it, rather than
00498   // a memcpy.
00499   if (LoadInst *LI = dyn_cast<LoadInst>(SI->getOperand(0))) {
00500     if (LI->isSimple() && LI->hasOneUse() &&
00501         LI->getParent() == SI->getParent()) {
00502       MemDepResult ldep = MD->getDependency(LI);
00503       CallInst *C = 0;
00504       if (ldep.isClobber() && !isa<MemCpyInst>(ldep.getInst()))
00505         C = dyn_cast<CallInst>(ldep.getInst());
00506 
00507       if (C) {
00508         // Check that nothing touches the dest of the "copy" between
00509         // the call and the store.
00510         AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
00511         AliasAnalysis::Location StoreLoc = AA.getLocation(SI);
00512         for (BasicBlock::iterator I = --BasicBlock::iterator(SI),
00513                                   E = C; I != E; --I) {
00514           if (AA.getModRefInfo(&*I, StoreLoc) != AliasAnalysis::NoModRef) {
00515             C = 0;
00516             break;
00517           }
00518         }
00519       }
00520 
00521       if (C) {
00522         unsigned storeAlign = SI->getAlignment();
00523         if (!storeAlign)
00524           storeAlign = DL->getABITypeAlignment(SI->getOperand(0)->getType());
00525         unsigned loadAlign = LI->getAlignment();
00526         if (!loadAlign)
00527           loadAlign = DL->getABITypeAlignment(LI->getType());
00528 
00529         bool changed = performCallSlotOptzn(LI,
00530                         SI->getPointerOperand()->stripPointerCasts(),
00531                         LI->getPointerOperand()->stripPointerCasts(),
00532                         DL->getTypeStoreSize(SI->getOperand(0)->getType()),
00533                         std::min(storeAlign, loadAlign), C);
00534         if (changed) {
00535           MD->removeInstruction(SI);
00536           SI->eraseFromParent();
00537           MD->removeInstruction(LI);
00538           LI->eraseFromParent();
00539           ++NumMemCpyInstr;
00540           return true;
00541         }
00542       }
00543     }
00544   }
00545 
00546   // There are two cases that are interesting for this code to handle: memcpy
00547   // and memset.  Right now we only handle memset.
00548 
00549   // Ensure that the value being stored is something that can be memset'able a
00550   // byte at a time like "0" or "-1" or any width, as well as things like
00551   // 0xA0A0A0A0 and 0.0.
00552   if (Value *ByteVal = isBytewiseValue(SI->getOperand(0)))
00553     if (Instruction *I = tryMergingIntoMemset(SI, SI->getPointerOperand(),
00554                                               ByteVal)) {
00555       BBI = I;  // Don't invalidate iterator.
00556       return true;
00557     }
00558 
00559   return false;
00560 }
00561 
00562 bool MemCpyOpt::processMemSet(MemSetInst *MSI, BasicBlock::iterator &BBI) {
00563   // See if there is another memset or store neighboring this memset which
00564   // allows us to widen out the memset to do a single larger store.
00565   if (isa<ConstantInt>(MSI->getLength()) && !MSI->isVolatile())
00566     if (Instruction *I = tryMergingIntoMemset(MSI, MSI->getDest(),
00567                                               MSI->getValue())) {
00568       BBI = I;  // Don't invalidate iterator.
00569       return true;
00570     }
00571   return false;
00572 }
00573 
00574 
00575 /// performCallSlotOptzn - takes a memcpy and a call that it depends on,
00576 /// and checks for the possibility of a call slot optimization by having
00577 /// the call write its result directly into the destination of the memcpy.
00578 bool MemCpyOpt::performCallSlotOptzn(Instruction *cpy,
00579                                      Value *cpyDest, Value *cpySrc,
00580                                      uint64_t cpyLen, unsigned cpyAlign,
00581                                      CallInst *C) {
00582   // The general transformation to keep in mind is
00583   //
00584   //   call @func(..., src, ...)
00585   //   memcpy(dest, src, ...)
00586   //
00587   // ->
00588   //
00589   //   memcpy(dest, src, ...)
00590   //   call @func(..., dest, ...)
00591   //
00592   // Since moving the memcpy is technically awkward, we additionally check that
00593   // src only holds uninitialized values at the moment of the call, meaning that
00594   // the memcpy can be discarded rather than moved.
00595 
00596   // Deliberately get the source and destination with bitcasts stripped away,
00597   // because we'll need to do type comparisons based on the underlying type.
00598   CallSite CS(C);
00599 
00600   // Require that src be an alloca.  This simplifies the reasoning considerably.
00601   AllocaInst *srcAlloca = dyn_cast<AllocaInst>(cpySrc);
00602   if (!srcAlloca)
00603     return false;
00604 
00605   // Check that all of src is copied to dest.
00606   if (DL == 0) return false;
00607 
00608   ConstantInt *srcArraySize = dyn_cast<ConstantInt>(srcAlloca->getArraySize());
00609   if (!srcArraySize)
00610     return false;
00611 
00612   uint64_t srcSize = DL->getTypeAllocSize(srcAlloca->getAllocatedType()) *
00613     srcArraySize->getZExtValue();
00614 
00615   if (cpyLen < srcSize)
00616     return false;
00617 
00618   // Check that accessing the first srcSize bytes of dest will not cause a
00619   // trap.  Otherwise the transform is invalid since it might cause a trap
00620   // to occur earlier than it otherwise would.
00621   if (AllocaInst *A = dyn_cast<AllocaInst>(cpyDest)) {
00622     // The destination is an alloca.  Check it is larger than srcSize.
00623     ConstantInt *destArraySize = dyn_cast<ConstantInt>(A->getArraySize());
00624     if (!destArraySize)
00625       return false;
00626 
00627     uint64_t destSize = DL->getTypeAllocSize(A->getAllocatedType()) *
00628       destArraySize->getZExtValue();
00629 
00630     if (destSize < srcSize)
00631       return false;
00632   } else if (Argument *A = dyn_cast<Argument>(cpyDest)) {
00633     // If the destination is an sret parameter then only accesses that are
00634     // outside of the returned struct type can trap.
00635     if (!A->hasStructRetAttr())
00636       return false;
00637 
00638     Type *StructTy = cast<PointerType>(A->getType())->getElementType();
00639     if (!StructTy->isSized()) {
00640       // The call may never return and hence the copy-instruction may never
00641       // be executed, and therefore it's not safe to say "the destination
00642       // has at least <cpyLen> bytes, as implied by the copy-instruction",
00643       return false;
00644     }
00645 
00646     uint64_t destSize = DL->getTypeAllocSize(StructTy);
00647     if (destSize < srcSize)
00648       return false;
00649   } else {
00650     return false;
00651   }
00652 
00653   // Check that dest points to memory that is at least as aligned as src.
00654   unsigned srcAlign = srcAlloca->getAlignment();
00655   if (!srcAlign)
00656     srcAlign = DL->getABITypeAlignment(srcAlloca->getAllocatedType());
00657   bool isDestSufficientlyAligned = srcAlign <= cpyAlign;
00658   // If dest is not aligned enough and we can't increase its alignment then
00659   // bail out.
00660   if (!isDestSufficientlyAligned && !isa<AllocaInst>(cpyDest))
00661     return false;
00662 
00663   // Check that src is not accessed except via the call and the memcpy.  This
00664   // guarantees that it holds only undefined values when passed in (so the final
00665   // memcpy can be dropped), that it is not read or written between the call and
00666   // the memcpy, and that writing beyond the end of it is undefined.
00667   SmallVector<User*, 8> srcUseList(srcAlloca->user_begin(),
00668                                    srcAlloca->user_end());
00669   while (!srcUseList.empty()) {
00670     User *U = srcUseList.pop_back_val();
00671 
00672     if (isa<BitCastInst>(U) || isa<AddrSpaceCastInst>(U)) {
00673       for (User *UU : U->users())
00674         srcUseList.push_back(UU);
00675     } else if (GetElementPtrInst *G = dyn_cast<GetElementPtrInst>(U)) {
00676       if (G->hasAllZeroIndices())
00677         for (User *UU : U->users())
00678           srcUseList.push_back(UU);
00679       else
00680         return false;
00681     } else if (U != C && U != cpy) {
00682       return false;
00683     }
00684   }
00685 
00686   // Since we're changing the parameter to the callsite, we need to make sure
00687   // that what would be the new parameter dominates the callsite.
00688   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
00689   if (Instruction *cpyDestInst = dyn_cast<Instruction>(cpyDest))
00690     if (!DT.dominates(cpyDestInst, C))
00691       return false;
00692 
00693   // In addition to knowing that the call does not access src in some
00694   // unexpected manner, for example via a global, which we deduce from
00695   // the use analysis, we also need to know that it does not sneakily
00696   // access dest.  We rely on AA to figure this out for us.
00697   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
00698   AliasAnalysis::ModRefResult MR = AA.getModRefInfo(C, cpyDest, srcSize);
00699   // If necessary, perform additional analysis.
00700   if (MR != AliasAnalysis::NoModRef)
00701     MR = AA.callCapturesBefore(C, cpyDest, srcSize, &DT);
00702   if (MR != AliasAnalysis::NoModRef)
00703     return false;
00704 
00705   // All the checks have passed, so do the transformation.
00706   bool changedArgument = false;
00707   for (unsigned i = 0; i < CS.arg_size(); ++i)
00708     if (CS.getArgument(i)->stripPointerCasts() == cpySrc) {
00709       Value *Dest = cpySrc->getType() == cpyDest->getType() ?  cpyDest
00710         : CastInst::CreatePointerCast(cpyDest, cpySrc->getType(),
00711                                       cpyDest->getName(), C);
00712       changedArgument = true;
00713       if (CS.getArgument(i)->getType() == Dest->getType())
00714         CS.setArgument(i, Dest);
00715       else
00716         CS.setArgument(i, CastInst::CreatePointerCast(Dest,
00717                           CS.getArgument(i)->getType(), Dest->getName(), C));
00718     }
00719 
00720   if (!changedArgument)
00721     return false;
00722 
00723   // If the destination wasn't sufficiently aligned then increase its alignment.
00724   if (!isDestSufficientlyAligned) {
00725     assert(isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!");
00726     cast<AllocaInst>(cpyDest)->setAlignment(srcAlign);
00727   }
00728 
00729   // Drop any cached information about the call, because we may have changed
00730   // its dependence information by changing its parameter.
00731   MD->removeInstruction(C);
00732 
00733   // Remove the memcpy.
00734   MD->removeInstruction(cpy);
00735   ++NumMemCpyInstr;
00736 
00737   return true;
00738 }
00739 
00740 /// processMemCpyMemCpyDependence - We've found that the (upward scanning)
00741 /// memory dependence of memcpy 'M' is the memcpy 'MDep'.  Try to simplify M to
00742 /// copy from MDep's input if we can.  MSize is the size of M's copy.
00743 ///
00744 bool MemCpyOpt::processMemCpyMemCpyDependence(MemCpyInst *M, MemCpyInst *MDep,
00745                                               uint64_t MSize) {
00746   // We can only transforms memcpy's where the dest of one is the source of the
00747   // other.
00748   if (M->getSource() != MDep->getDest() || MDep->isVolatile())
00749     return false;
00750 
00751   // If dep instruction is reading from our current input, then it is a noop
00752   // transfer and substituting the input won't change this instruction.  Just
00753   // ignore the input and let someone else zap MDep.  This handles cases like:
00754   //    memcpy(a <- a)
00755   //    memcpy(b <- a)
00756   if (M->getSource() == MDep->getSource())
00757     return false;
00758 
00759   // Second, the length of the memcpy's must be the same, or the preceding one
00760   // must be larger than the following one.
00761   ConstantInt *MDepLen = dyn_cast<ConstantInt>(MDep->getLength());
00762   ConstantInt *MLen = dyn_cast<ConstantInt>(M->getLength());
00763   if (!MDepLen || !MLen || MDepLen->getZExtValue() < MLen->getZExtValue())
00764     return false;
00765 
00766   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
00767 
00768   // Verify that the copied-from memory doesn't change in between the two
00769   // transfers.  For example, in:
00770   //    memcpy(a <- b)
00771   //    *b = 42;
00772   //    memcpy(c <- a)
00773   // It would be invalid to transform the second memcpy into memcpy(c <- b).
00774   //
00775   // TODO: If the code between M and MDep is transparent to the destination "c",
00776   // then we could still perform the xform by moving M up to the first memcpy.
00777   //
00778   // NOTE: This is conservative, it will stop on any read from the source loc,
00779   // not just the defining memcpy.
00780   MemDepResult SourceDep =
00781     MD->getPointerDependencyFrom(AA.getLocationForSource(MDep),
00782                                  false, M, M->getParent());
00783   if (!SourceDep.isClobber() || SourceDep.getInst() != MDep)
00784     return false;
00785 
00786   // If the dest of the second might alias the source of the first, then the
00787   // source and dest might overlap.  We still want to eliminate the intermediate
00788   // value, but we have to generate a memmove instead of memcpy.
00789   bool UseMemMove = false;
00790   if (!AA.isNoAlias(AA.getLocationForDest(M), AA.getLocationForSource(MDep)))
00791     UseMemMove = true;
00792 
00793   // If all checks passed, then we can transform M.
00794 
00795   // Make sure to use the lesser of the alignment of the source and the dest
00796   // since we're changing where we're reading from, but don't want to increase
00797   // the alignment past what can be read from or written to.
00798   // TODO: Is this worth it if we're creating a less aligned memcpy? For
00799   // example we could be moving from movaps -> movq on x86.
00800   unsigned Align = std::min(MDep->getAlignment(), M->getAlignment());
00801 
00802   IRBuilder<> Builder(M);
00803   if (UseMemMove)
00804     Builder.CreateMemMove(M->getRawDest(), MDep->getRawSource(), M->getLength(),
00805                           Align, M->isVolatile());
00806   else
00807     Builder.CreateMemCpy(M->getRawDest(), MDep->getRawSource(), M->getLength(),
00808                          Align, M->isVolatile());
00809 
00810   // Remove the instruction we're replacing.
00811   MD->removeInstruction(M);
00812   M->eraseFromParent();
00813   ++NumMemCpyInstr;
00814   return true;
00815 }
00816 
00817 
00818 /// processMemCpy - perform simplification of memcpy's.  If we have memcpy A
00819 /// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite
00820 /// B to be a memcpy from X to Z (or potentially a memmove, depending on
00821 /// circumstances). This allows later passes to remove the first memcpy
00822 /// altogether.
00823 bool MemCpyOpt::processMemCpy(MemCpyInst *M) {
00824   // We can only optimize non-volatile memcpy's.
00825   if (M->isVolatile()) return false;
00826 
00827   // If the source and destination of the memcpy are the same, then zap it.
00828   if (M->getSource() == M->getDest()) {
00829     MD->removeInstruction(M);
00830     M->eraseFromParent();
00831     return false;
00832   }
00833 
00834   // If copying from a constant, try to turn the memcpy into a memset.
00835   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getSource()))
00836     if (GV->isConstant() && GV->hasDefinitiveInitializer())
00837       if (Value *ByteVal = isBytewiseValue(GV->getInitializer())) {
00838         IRBuilder<> Builder(M);
00839         Builder.CreateMemSet(M->getRawDest(), ByteVal, M->getLength(),
00840                              M->getAlignment(), false);
00841         MD->removeInstruction(M);
00842         M->eraseFromParent();
00843         ++NumCpyToSet;
00844         return true;
00845       }
00846 
00847   // The optimizations after this point require the memcpy size.
00848   ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength());
00849   if (CopySize == 0) return false;
00850 
00851   // The are three possible optimizations we can do for memcpy:
00852   //   a) memcpy-memcpy xform which exposes redundance for DSE.
00853   //   b) call-memcpy xform for return slot optimization.
00854   //   c) memcpy from freshly alloca'd space or space that has just started its
00855   //      lifetime copies undefined data, and we can therefore eliminate the
00856   //      memcpy in favor of the data that was already at the destination.
00857   MemDepResult DepInfo = MD->getDependency(M);
00858   if (DepInfo.isClobber()) {
00859     if (CallInst *C = dyn_cast<CallInst>(DepInfo.getInst())) {
00860       if (performCallSlotOptzn(M, M->getDest(), M->getSource(),
00861                                CopySize->getZExtValue(), M->getAlignment(),
00862                                C)) {
00863         MD->removeInstruction(M);
00864         M->eraseFromParent();
00865         return true;
00866       }
00867     }
00868   }
00869 
00870   AliasAnalysis::Location SrcLoc = AliasAnalysis::getLocationForSource(M);
00871   MemDepResult SrcDepInfo = MD->getPointerDependencyFrom(SrcLoc, true,
00872                                                          M, M->getParent());
00873   if (SrcDepInfo.isClobber()) {
00874     if (MemCpyInst *MDep = dyn_cast<MemCpyInst>(SrcDepInfo.getInst()))
00875       return processMemCpyMemCpyDependence(M, MDep, CopySize->getZExtValue());
00876   } else if (SrcDepInfo.isDef()) {
00877     Instruction *I = SrcDepInfo.getInst();
00878     bool hasUndefContents = false;
00879 
00880     if (isa<AllocaInst>(I)) {
00881       hasUndefContents = true;
00882     } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
00883       if (II->getIntrinsicID() == Intrinsic::lifetime_start)
00884         if (ConstantInt *LTSize = dyn_cast<ConstantInt>(II->getArgOperand(0)))
00885           if (LTSize->getZExtValue() >= CopySize->getZExtValue())
00886             hasUndefContents = true;
00887     }
00888 
00889     if (hasUndefContents) {
00890       MD->removeInstruction(M);
00891       M->eraseFromParent();
00892       ++NumMemCpyInstr;
00893       return true;
00894     }
00895   }
00896 
00897   return false;
00898 }
00899 
00900 /// processMemMove - Transforms memmove calls to memcpy calls when the src/dst
00901 /// are guaranteed not to alias.
00902 bool MemCpyOpt::processMemMove(MemMoveInst *M) {
00903   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
00904 
00905   if (!TLI->has(LibFunc::memmove))
00906     return false;
00907 
00908   // See if the pointers alias.
00909   if (!AA.isNoAlias(AA.getLocationForDest(M), AA.getLocationForSource(M)))
00910     return false;
00911 
00912   DEBUG(dbgs() << "MemCpyOpt: Optimizing memmove -> memcpy: " << *M << "\n");
00913 
00914   // If not, then we know we can transform this.
00915   Module *Mod = M->getParent()->getParent()->getParent();
00916   Type *ArgTys[3] = { M->getRawDest()->getType(),
00917                       M->getRawSource()->getType(),
00918                       M->getLength()->getType() };
00919   M->setCalledFunction(Intrinsic::getDeclaration(Mod, Intrinsic::memcpy,
00920                                                  ArgTys));
00921 
00922   // MemDep may have over conservative information about this instruction, just
00923   // conservatively flush it from the cache.
00924   MD->removeInstruction(M);
00925 
00926   ++NumMoveToCpy;
00927   return true;
00928 }
00929 
00930 /// processByValArgument - This is called on every byval argument in call sites.
00931 bool MemCpyOpt::processByValArgument(CallSite CS, unsigned ArgNo) {
00932   if (DL == 0) return false;
00933 
00934   // Find out what feeds this byval argument.
00935   Value *ByValArg = CS.getArgument(ArgNo);
00936   Type *ByValTy = cast<PointerType>(ByValArg->getType())->getElementType();
00937   uint64_t ByValSize = DL->getTypeAllocSize(ByValTy);
00938   MemDepResult DepInfo =
00939     MD->getPointerDependencyFrom(AliasAnalysis::Location(ByValArg, ByValSize),
00940                                  true, CS.getInstruction(),
00941                                  CS.getInstruction()->getParent());
00942   if (!DepInfo.isClobber())
00943     return false;
00944 
00945   // If the byval argument isn't fed by a memcpy, ignore it.  If it is fed by
00946   // a memcpy, see if we can byval from the source of the memcpy instead of the
00947   // result.
00948   MemCpyInst *MDep = dyn_cast<MemCpyInst>(DepInfo.getInst());
00949   if (MDep == 0 || MDep->isVolatile() ||
00950       ByValArg->stripPointerCasts() != MDep->getDest())
00951     return false;
00952 
00953   // The length of the memcpy must be larger or equal to the size of the byval.
00954   ConstantInt *C1 = dyn_cast<ConstantInt>(MDep->getLength());
00955   if (C1 == 0 || C1->getValue().getZExtValue() < ByValSize)
00956     return false;
00957 
00958   // Get the alignment of the byval.  If the call doesn't specify the alignment,
00959   // then it is some target specific value that we can't know.
00960   unsigned ByValAlign = CS.getParamAlignment(ArgNo+1);
00961   if (ByValAlign == 0) return false;
00962 
00963   // If it is greater than the memcpy, then we check to see if we can force the
00964   // source of the memcpy to the alignment we need.  If we fail, we bail out.
00965   if (MDep->getAlignment() < ByValAlign &&
00966       getOrEnforceKnownAlignment(MDep->getSource(),ByValAlign, DL) < ByValAlign)
00967     return false;
00968 
00969   // Verify that the copied-from memory doesn't change in between the memcpy and
00970   // the byval call.
00971   //    memcpy(a <- b)
00972   //    *b = 42;
00973   //    foo(*a)
00974   // It would be invalid to transform the second memcpy into foo(*b).
00975   //
00976   // NOTE: This is conservative, it will stop on any read from the source loc,
00977   // not just the defining memcpy.
00978   MemDepResult SourceDep =
00979     MD->getPointerDependencyFrom(AliasAnalysis::getLocationForSource(MDep),
00980                                  false, CS.getInstruction(), MDep->getParent());
00981   if (!SourceDep.isClobber() || SourceDep.getInst() != MDep)
00982     return false;
00983 
00984   Value *TmpCast = MDep->getSource();
00985   if (MDep->getSource()->getType() != ByValArg->getType())
00986     TmpCast = new BitCastInst(MDep->getSource(), ByValArg->getType(),
00987                               "tmpcast", CS.getInstruction());
00988 
00989   DEBUG(dbgs() << "MemCpyOpt: Forwarding memcpy to byval:\n"
00990                << "  " << *MDep << "\n"
00991                << "  " << *CS.getInstruction() << "\n");
00992 
00993   // Otherwise we're good!  Update the byval argument.
00994   CS.setArgument(ArgNo, TmpCast);
00995   ++NumMemCpyInstr;
00996   return true;
00997 }
00998 
00999 /// iterateOnFunction - Executes one iteration of MemCpyOpt.
01000 bool MemCpyOpt::iterateOnFunction(Function &F) {
01001   bool MadeChange = false;
01002 
01003   // Walk all instruction in the function.
01004   for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) {
01005     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
01006       // Avoid invalidating the iterator.
01007       Instruction *I = BI++;
01008 
01009       bool RepeatInstruction = false;
01010 
01011       if (StoreInst *SI = dyn_cast<StoreInst>(I))
01012         MadeChange |= processStore(SI, BI);
01013       else if (MemSetInst *M = dyn_cast<MemSetInst>(I))
01014         RepeatInstruction = processMemSet(M, BI);
01015       else if (MemCpyInst *M = dyn_cast<MemCpyInst>(I))
01016         RepeatInstruction = processMemCpy(M);
01017       else if (MemMoveInst *M = dyn_cast<MemMoveInst>(I))
01018         RepeatInstruction = processMemMove(M);
01019       else if (CallSite CS = (Value*)I) {
01020         for (unsigned i = 0, e = CS.arg_size(); i != e; ++i)
01021           if (CS.isByValArgument(i))
01022             MadeChange |= processByValArgument(CS, i);
01023       }
01024 
01025       // Reprocess the instruction if desired.
01026       if (RepeatInstruction) {
01027         if (BI != BB->begin()) --BI;
01028         MadeChange = true;
01029       }
01030     }
01031   }
01032 
01033   return MadeChange;
01034 }
01035 
01036 // MemCpyOpt::runOnFunction - This is the main transformation entry point for a
01037 // function.
01038 //
01039 bool MemCpyOpt::runOnFunction(Function &F) {
01040   if (skipOptnoneFunction(F))
01041     return false;
01042 
01043   bool MadeChange = false;
01044   MD = &getAnalysis<MemoryDependenceAnalysis>();
01045   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
01046   DL = DLP ? &DLP->getDataLayout() : 0;
01047   TLI = &getAnalysis<TargetLibraryInfo>();
01048 
01049   // If we don't have at least memset and memcpy, there is little point of doing
01050   // anything here.  These are required by a freestanding implementation, so if
01051   // even they are disabled, there is no point in trying hard.
01052   if (!TLI->has(LibFunc::memset) || !TLI->has(LibFunc::memcpy))
01053     return false;
01054 
01055   while (1) {
01056     if (!iterateOnFunction(F))
01057       break;
01058     MadeChange = true;
01059   }
01060 
01061   MD = 0;
01062   return MadeChange;
01063 }