lib/Transforms/Scalar/LoopIdiomRecognize.cpp

   1 //===-- LoopIdiomRecognize.cpp - Loop idiom recognition -------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass implements an idiom recognizer that transforms simple loops into a
  11 // non-loop form.  In cases that this kicks in, it can be a significant
  12 // performance win.
  13 //
  14 //===----------------------------------------------------------------------===//
  15 //
  16 // TODO List:
  17 //
  18 // Future loop memory idioms to recognize:
  19 //   memcmp, memmove, strlen, etc.
  20 // Future floating point idioms to recognize in -ffast-math mode:
  21 //   fpowi
  22 // Future integer operation idioms to recognize:
  23 //   ctpop, ctlz, cttz
  24 //
  25 // Beware that isel's default lowering for ctpop is highly inefficient for
  26 // i64 and larger types when i64 is legal and the value has few bits set.  It
  27 // would be good to enhance isel to emit a loop for ctpop in this case.
  28 //
  29 // We should enhance the memset/memcpy recognition to handle multiple stores in
  30 // the loop.  This would handle things like:
  31 //   void foo(_Complex float *P)
  32 //     for (i) { __real__(*P) = 0;  __imag__(*P) = 0; }
  33 //
  34 // We should enhance this to handle negative strides through memory.
  35 // Alternatively (and perhaps better) we could rely on an earlier pass to force
  36 // forward iteration through memory, which is generally better for cache
  37 // behavior.  Negative strides *do* happen for memset/memcpy loops.
  38 //
  39 // This could recognize common matrix multiplies and dot product idioms and
  40 // replace them with calls to BLAS (if linked in??).
  41 //
  42 //===----------------------------------------------------------------------===//
  43
  44 #define DEBUG_TYPE "loop-idiom"
  45 #include "llvm/Transforms/Scalar.h"
  46 #include "llvm/IRBuilder.h"
  47 #include "llvm/IntrinsicInst.h"
  48 #include "llvm/Module.h"
  49 #include "llvm/ADT/Statistic.h"
  50 #include "llvm/Analysis/AliasAnalysis.h"
  51 #include "llvm/Analysis/DependenceAnalysis.h"
  52 #include "llvm/Analysis/LoopPass.h"
  53 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  54 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  55 #include "llvm/Analysis/ValueTracking.h"
  56 #include "llvm/Support/Debug.h"
  57 #include "llvm/Support/raw_ostream.h"
  58 #include "llvm/DataLayout.h"
  59 #include "llvm/Target/TargetLibraryInfo.h"
  60 #include "llvm/Transforms/Utils/Local.h"
  61 using namespace llvm;
  62
  63 STATISTIC(NumMemSet, "Number of memset's formed from loop stores");
  64 STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores");
  65
  66 namespace {
  67   class LoopIdiomRecognize : public LoopPass {
  68     Loop *CurLoop;
  69     const DataLayout *TD;
  70     DominatorTree *DT;
  71     ScalarEvolution *SE;
  72     TargetLibraryInfo *TLI;
  73   public:
  74     static char ID;
  75     explicit LoopIdiomRecognize() : LoopPass(ID) {
  76       initializeLoopIdiomRecognizePass(*PassRegistry::getPassRegistry());
  77     }
  78
  79     bool runOnLoop(Loop *L, LPPassManager &LPM);
  80     bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
  81                         SmallVectorImpl<BasicBlock*> &ExitBlocks);
  82
  83     bool processLoopStore(StoreInst *SI, const SCEV *BECount);
  84     bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount);
  85
  86     bool processLoopStridedStore(Value *DestPtr, unsigned StoreSize,
  87                                  unsigned StoreAlignment,
  88                                  Value *SplatValue, Instruction *TheStore,
  89                                  const SCEVAddRecExpr *Ev,
  90                                  const SCEV *BECount);
  91     bool processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize,
  92                                     const SCEVAddRecExpr *StoreEv,
  93                                     const SCEVAddRecExpr *LoadEv,
  94                                     const SCEV *BECount);
  95
  96     /// This transformation requires natural loop information & requires that
  97     /// loop preheaders be inserted into the CFG.
  98     ///
  99     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 100       AU.addRequired<LoopInfo>();
 101       AU.addPreserved<LoopInfo>();
 102       AU.addRequiredID(LoopSimplifyID);
 103       AU.addPreservedID(LoopSimplifyID);
 104       AU.addRequiredID(LCSSAID);
 105       AU.addPreservedID(LCSSAID);
 106       AU.addRequired<AliasAnalysis>();
 107       AU.addPreserved<AliasAnalysis>();
 108       AU.addRequired<ScalarEvolution>();
 109       AU.addPreserved<ScalarEvolution>();
 110       AU.addRequired<DependenceAnalysis>();
 111       AU.addPreserved<DependenceAnalysis>();
 112       AU.addPreserved<DominatorTree>();
 113       AU.addRequired<DominatorTree>();
 114       AU.addRequired<TargetLibraryInfo>();
 115     }
 116   };
 117 }
 118
 119 char LoopIdiomRecognize::ID = 0;
 120 INITIALIZE_PASS_BEGIN(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms",
 121                       false, false)
 122 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
 123 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 124 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 125 INITIALIZE_PASS_DEPENDENCY(LCSSA)
 126 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
 127 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 128 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysis)
 129 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 130 INITIALIZE_PASS_END(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms",
 131                     false, false)
 132
 133 Pass *llvm::createLoopIdiomPass() { return new LoopIdiomRecognize(); }
 134
 135 /// deleteDeadInstruction - Delete this instruction.  Before we do, go through
 136 /// and zero out all the operands of this instruction.  If any of them become
 137 /// dead, delete them and the computation tree that feeds them.
 138 ///
 139 static void deleteDeadInstruction(Instruction *I, ScalarEvolution &SE,
 140                                   const TargetLibraryInfo *TLI) {
 141   SmallVector<Instruction*, 32> NowDeadInsts;
 142
 143   NowDeadInsts.push_back(I);
 144
 145   // Before we touch this instruction, remove it from SE!
 146   do {
 147     Instruction *DeadInst = NowDeadInsts.pop_back_val();
 148
 149     // This instruction is dead, zap it, in stages.  Start by removing it from
 150     // SCEV.
 151     SE.forgetValue(DeadInst);
 152
 153     for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
 154       Value *Op = DeadInst->getOperand(op);
 155       DeadInst->setOperand(op, 0);
 156
 157       // If this operand just became dead, add it to the NowDeadInsts list.
 158       if (!Op->use_empty()) continue;
 159
 160       if (Instruction *OpI = dyn_cast<Instruction>(Op))
 161         if (isInstructionTriviallyDead(OpI, TLI))
 162           NowDeadInsts.push_back(OpI);
 163     }
 164
 165     DeadInst->eraseFromParent();
 166
 167   } while (!NowDeadInsts.empty());
 168 }
 169
 170 bool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
 171   CurLoop = L;
 172
 173   // If the loop could not be converted to canonical form, it must have an
 174   // indirectbr in it, just give up.
 175   if (!L->getLoopPreheader())
 176     return false;
 177
 178   // Disable loop idiom recognition if the function's name is a common idiom.
 179   StringRef Name = L->getHeader()->getParent()->getName();
 180   if (Name == "memset" || Name == "memcpy")
 181     return false;
 182
 183   // The trip count of the loop must be analyzable.
 184   SE = &getAnalysis<ScalarEvolution>();
 185   if (!SE->hasLoopInvariantBackedgeTakenCount(L))
 186     return false;
 187   const SCEV *BECount = SE->getBackedgeTakenCount(L);
 188   if (isa<SCEVCouldNotCompute>(BECount)) return false;
 189
 190   // If this loop executes exactly one time, then it should be peeled, not
 191   // optimized by this pass.
 192   if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
 193     if (BECst->getValue()->getValue() == 0)
 194       return false;
 195
 196   // We require target data for now.
 197   TD = getAnalysisIfAvailable<DataLayout>();
 198   if (TD == 0) return false;
 199
 200   DT = &getAnalysis<DominatorTree>();
 201   LoopInfo &LI = getAnalysis<LoopInfo>();
 202   TLI = &getAnalysis<TargetLibraryInfo>();
 203
 204   SmallVector<BasicBlock*, 8> ExitBlocks;
 205   CurLoop->getUniqueExitBlocks(ExitBlocks);
 206
 207   DEBUG(dbgs() << "loop-idiom Scanning: F["
 208                << L->getHeader()->getParent()->getName()
 209                << "] Loop %" << L->getHeader()->getName() << "\n");
 210
 211   bool MadeChange = false;
 212   // Scan all the blocks in the loop that are not in subloops.
 213   for (Loop::block_iterator BI = L->block_begin(), E = L->block_end(); BI != E;
 214        ++BI) {
 215     // Ignore blocks in subloops.
 216     if (LI.getLoopFor(*BI) != CurLoop)
 217       continue;
 218
 219     MadeChange |= runOnLoopBlock(*BI, BECount, ExitBlocks);
 220   }
 221   return MadeChange;
 222 }
 223
 224 /// runOnLoopBlock - Process the specified block, which lives in a counted loop
 225 /// with the specified backedge count.  This block is known to be in the current
 226 /// loop and not in any subloops.
 227 bool LoopIdiomRecognize::runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
 228                                      SmallVectorImpl<BasicBlock*> &ExitBlocks) {
 229   // We can only promote stores in this block if they are unconditionally
 230   // executed in the loop.  For a block to be unconditionally executed, it has
 231   // to dominate all the exit blocks of the loop.  Verify this now.
 232   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
 233     if (!DT->dominates(BB, ExitBlocks[i]))
 234       return false;
 235
 236   bool MadeChange = false;
 237   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
 238     Instruction *Inst = I++;
 239     // Look for store instructions, which may be optimized to memset/memcpy.
 240     if (StoreInst *SI = dyn_cast<StoreInst>(Inst))  {
 241       WeakVH InstPtr(I);
 242       if (!processLoopStore(SI, BECount)) continue;
 243       MadeChange = true;
 244
 245       // If processing the store invalidated our iterator, start over from the
 246       // top of the block.
 247       if (InstPtr == 0)
 248         I = BB->begin();
 249       continue;
 250     }
 251
 252     // Look for memset instructions, which may be optimized to a larger memset.
 253     if (MemSetInst *MSI = dyn_cast<MemSetInst>(Inst))  {
 254       WeakVH InstPtr(I);
 255       if (!processLoopMemSet(MSI, BECount)) continue;
 256       MadeChange = true;
 257
 258       // If processing the memset invalidated our iterator, start over from the
 259       // top of the block.
 260       if (InstPtr == 0)
 261         I = BB->begin();
 262       continue;
 263     }
 264   }
 265
 266   return MadeChange;
 267 }
 268
 269
 270 /// processLoopStore - See if this store can be promoted to a memset or memcpy.
 271 bool LoopIdiomRecognize::processLoopStore(StoreInst *SI, const SCEV *BECount) {
 272   if (!SI->isSimple()) return false;
 273
 274   Value *StoredVal = SI->getValueOperand();
 275   Value *StorePtr = SI->getPointerOperand();
 276
 277   // Reject stores that are so large that they overflow an unsigned.
 278   uint64_t SizeInBits = TD->getTypeSizeInBits(StoredVal->getType());
 279   if ((SizeInBits & 7) || (SizeInBits >> 32) != 0)
 280     return false;
 281
 282   // See if the pointer expression is an AddRec like {base,+,1} on the current
 283   // loop, which indicates a strided store.  If we have something else, it's a
 284   // random store we can't handle.
 285   const SCEVAddRecExpr *StoreEv =
 286     dyn_cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
 287   if (StoreEv == 0 || StoreEv->getLoop() != CurLoop || !StoreEv->isAffine())
 288     return false;
 289
 290   // Check to see if the stride matches the size of the store.  If so, then we
 291   // know that every byte is touched in the loop.
 292   unsigned StoreSize = (unsigned)SizeInBits >> 3;
 293   const SCEVConstant *Stride = dyn_cast<SCEVConstant>(StoreEv->getOperand(1));
 294
 295   if (Stride == 0 || StoreSize != Stride->getValue()->getValue()) {
 296     // TODO: Could also handle negative stride here someday, that will require
 297     // the validity check in mayLoopAccessLocation to be updated though.
 298     // Enable this to print exact negative strides.
 299     if (0 && Stride && StoreSize == -Stride->getValue()->getValue()) {
 300       dbgs() << "NEGATIVE STRIDE: " << *SI << "\n";
 301       dbgs() << "BB: " << *SI->getParent();
 302     }
 303
 304     return false;
 305   }
 306
 307   // See if we can optimize just this store in isolation.
 308   if (processLoopStridedStore(StorePtr, StoreSize, SI->getAlignment(),
 309                               StoredVal, SI, StoreEv, BECount))
 310     return true;
 311
 312   // If the stored value is a strided load in the same loop with the same stride
 313   // this this may be transformable into a memcpy.  This kicks in for stuff like
 314   //   for (i) A[i] = B[i];
 315   if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
 316     const SCEVAddRecExpr *LoadEv =
 317       dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LI->getOperand(0)));
 318     if (LoadEv && LoadEv->getLoop() == CurLoop && LoadEv->isAffine() &&
 319         StoreEv->getOperand(1) == LoadEv->getOperand(1) && LI->isSimple())
 320       if (processLoopStoreOfLoopLoad(SI, StoreSize, StoreEv, LoadEv, BECount))
 321         return true;
 322   }
 323   //errs() << "UNHANDLED strided store: " << *StoreEv << " - " << *SI << "\n";
 324
 325   return false;
 326 }
 327
 328 /// processLoopMemSet - See if this memset can be promoted to a large memset.
 329 bool LoopIdiomRecognize::
 330 processLoopMemSet(MemSetInst *MSI, const SCEV *BECount) {
 331   // We can only handle non-volatile memsets with a constant size.
 332   if (MSI->isVolatile() || !isa<ConstantInt>(MSI->getLength())) return false;
 333
 334   // If we're not allowed to hack on memset, we fail.
 335   if (!TLI->has(LibFunc::memset))
 336     return false;
 337
 338   Value *Pointer = MSI->getDest();
 339
 340   // See if the pointer expression is an AddRec like {base,+,1} on the current
 341   // loop, which indicates a strided store.  If we have something else, it's a
 342   // random store we can't handle.
 343   const SCEVAddRecExpr *Ev = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Pointer));
 344   if (Ev == 0 || Ev->getLoop() != CurLoop || !Ev->isAffine())
 345     return false;
 346
 347   // Reject memsets that are so large that they overflow an unsigned.
 348   uint64_t SizeInBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue();
 349   if ((SizeInBytes >> 32) != 0)
 350     return false;
 351
 352   // Check to see if the stride matches the size of the memset.  If so, then we
 353   // know that every byte is touched in the loop.
 354   const SCEVConstant *Stride = dyn_cast<SCEVConstant>(Ev->getOperand(1));
 355
 356   // TODO: Could also handle negative stride here someday, that will require the
 357   // validity check in mayLoopAccessLocation to be updated though.
 358   if (Stride == 0 || MSI->getLength() != Stride->getValue())
 359     return false;
 360
 361   return processLoopStridedStore(Pointer, (unsigned)SizeInBytes,
 362                                  MSI->getAlignment(), MSI->getValue(),
 363                                  MSI, Ev, BECount);
 364 }
 365
 366 /// getMemSetPatternValue - If a strided store of the specified value is safe to
 367 /// turn into a memset_pattern16, return a ConstantArray of 16 bytes that should
 368 /// be passed in.  Otherwise, return null.
 369 ///
 370 /// Note that we don't ever attempt to use memset_pattern8 or 4, because these
 371 /// just replicate their input array and then pass on to memset_pattern16.
 372 static Constant *getMemSetPatternValue(Value *V, const DataLayout &TD) {
 373   // If the value isn't a constant, we can't promote it to being in a constant
 374   // array.  We could theoretically do a store to an alloca or something, but
 375   // that doesn't seem worthwhile.
 376   Constant *C = dyn_cast<Constant>(V);
 377   if (C == 0) return 0;
 378
 379   // Only handle simple values that are a power of two bytes in size.
 380   uint64_t Size = TD.getTypeSizeInBits(V->getType());
 381   if (Size == 0 || (Size & 7) || (Size & (Size-1)))
 382     return 0;
 383
 384   // Don't care enough about darwin/ppc to implement this.
 385   if (TD.isBigEndian())
 386     return 0;
 387
 388   // Convert to size in bytes.
 389   Size /= 8;
 390
 391   // TODO: If CI is larger than 16-bytes, we can try slicing it in half to see
 392   // if the top and bottom are the same (e.g. for vectors and large integers).
 393   if (Size > 16) return 0;
 394
 395   // If the constant is exactly 16 bytes, just use it.
 396   if (Size == 16) return C;
 397
 398   // Otherwise, we'll use an array of the constants.
 399   unsigned ArraySize = 16/Size;
 400   ArrayType *AT = ArrayType::get(V->getType(), ArraySize);
 401   return ConstantArray::get(AT, std::vector<Constant*>(ArraySize, C));
 402 }
 403
 404
 405 /// processLoopStridedStore - We see a strided store of some value.  If we can
 406 /// transform this into a memset or memset_pattern in the loop preheader, do so.
 407 bool LoopIdiomRecognize::
 408 processLoopStridedStore(Value *DestPtr, unsigned StoreSize,
 409                         unsigned StoreAlignment, Value *StoredVal,
 410                         Instruction *TheStore, const SCEVAddRecExpr *Ev,
 411                         const SCEV *BECount) {
 412
 413   // If the stored value is a byte-wise value (like i32 -1), then it may be
 414   // turned into a memset of i8 -1, assuming that all the consecutive bytes
 415   // are stored.  A store of i32 0x01020304 can never be turned into a memset,
 416   // but it can be turned into memset_pattern if the target supports it.
 417   Value *SplatValue = isBytewiseValue(StoredVal);
 418   Constant *PatternValue = 0;
 419
 420   // If we're allowed to form a memset, and the stored value would be acceptable
 421   // for memset, use it.
 422   if (SplatValue && TLI->has(LibFunc::memset) &&
 423       // Verify that the stored value is loop invariant.  If not, we can't
 424       // promote the memset.
 425       CurLoop->isLoopInvariant(SplatValue)) {
 426     // Keep and use SplatValue.
 427     PatternValue = 0;
 428   } else if (TLI->has(LibFunc::memset_pattern16) &&
 429              (PatternValue = getMemSetPatternValue(StoredVal, *TD))) {
 430     // It looks like we can use PatternValue!
 431     SplatValue = 0;
 432   } else {
 433     // Otherwise, this isn't an idiom we can transform.  For example, we can't
 434     // do anything with a 3-byte store.
 435     return false;
 436   }
 437
 438   // Make sure the store has no dependencies (i.e. other loads and stores) in
 439   // the loop.
 440   DependenceAnalysis &DA = getAnalysis<DependenceAnalysis>();
 441   for (Loop::block_iterator BI = CurLoop->block_begin(),
 442        BE = CurLoop->block_end(); BI != BE; ++BI)
 443     for (BasicBlock::iterator I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I)
 444       if (&*I != TheStore && I->mayReadOrWriteMemory()) {
 445         OwningPtr<Dependence> D(DA.depends(TheStore, I, true));
 446         if (D)
 447           return false;
 448       }
 449
 450   // The trip count of the loop and the base pointer of the addrec SCEV is
 451   // guaranteed to be loop invariant, which means that it should dominate the
 452   // header.  This allows us to insert code for it in the preheader.
 453   BasicBlock *Preheader = CurLoop->getLoopPreheader();
 454   IRBuilder<> Builder(Preheader->getTerminator());
 455   SCEVExpander Expander(*SE, "loop-idiom");
 456
 457   // Okay, we have a strided store "p[i]" of a splattable value.  We can turn
 458   // this into a memset in the loop preheader now if we want.  However, this
 459   // would be unsafe to do if there is anything else in the loop that may read
 460   // or write to the aliased location.
 461   assert(DestPtr->getType()->isPointerTy()
 462       && "Must be a pointer type.");
 463   unsigned AddrSpace = DestPtr->getType()->getPointerAddressSpace();
 464   Value *BasePtr =
 465     Expander.expandCodeFor(Ev->getStart(), Builder.getInt8PtrTy(AddrSpace),
 466                            Preheader->getTerminator());
 467
 468
 469   // Okay, everything looks good, insert the memset.
 470
 471   // The # stored bytes is (BECount+1)*Size.  Expand the trip count out to
 472   // pointer size if it isn't already.
 473   Type *IntPtr = TD->getIntPtrType(DestPtr->getType());
 474   BECount = SE->getTruncateOrZeroExtend(BECount, IntPtr);
 475
 476   const SCEV *NumBytesS = SE->getAddExpr(BECount, SE->getConstant(IntPtr, 1),
 477                                          SCEV::FlagNUW);
 478   if (StoreSize != 1)
 479     NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtr, StoreSize),
 480                                SCEV::FlagNUW);
 481
 482   Value *NumBytes =
 483     Expander.expandCodeFor(NumBytesS, IntPtr, Preheader->getTerminator());
 484
 485   CallInst *NewCall;
 486   if (SplatValue)
 487     NewCall = Builder.CreateMemSet(BasePtr, SplatValue,NumBytes,StoreAlignment);
 488   else {
 489     Module *M = TheStore->getParent()->getParent()->getParent();
 490     Value *MSP = M->getOrInsertFunction("memset_pattern16",
 491                                         Builder.getVoidTy(),
 492                                         Builder.getInt8PtrTy(),
 493                                         Builder.getInt8PtrTy(), IntPtr,
 494                                         (void*)0);
 495
 496     // Otherwise we should form a memset_pattern16.  PatternValue is known to be
 497     // an constant array of 16-bytes.  Plop the value into a mergable global.
 498     GlobalVariable *GV = new GlobalVariable(*M, PatternValue->getType(), true,
 499                                             GlobalValue::InternalLinkage,
 500                                             PatternValue, ".memset_pattern");
 501     GV->setUnnamedAddr(true); // Ok to merge these.
 502     GV->setAlignment(16);
 503     Value *PatternPtr = ConstantExpr::getBitCast(GV, Builder.getInt8PtrTy());
 504     NewCall = Builder.CreateCall3(MSP, BasePtr, PatternPtr, NumBytes);
 505   }
 506
 507   DEBUG(dbgs() << "  Formed memset: " << *NewCall << "\n"
 508                << "    from store to: " << *Ev << " at: " << *TheStore << "\n");
 509   NewCall->setDebugLoc(TheStore->getDebugLoc());
 510
 511   // Okay, the memset has been formed.  Zap the original store and anything that
 512   // feeds into it.
 513   deleteDeadInstruction(TheStore, *SE, TLI);
 514   ++NumMemSet;
 515   return true;
 516 }
 517
 518 /// processLoopStoreOfLoopLoad - We see a strided store whose value is a
 519 /// same-strided load.
 520 bool LoopIdiomRecognize::
 521 processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize,
 522                            const SCEVAddRecExpr *StoreEv,
 523                            const SCEVAddRecExpr *LoadEv,
 524                            const SCEV *BECount) {
 525   // If we're not allowed to form memcpy, we fail.
 526   if (!TLI->has(LibFunc::memcpy))
 527     return false;
 528
 529   LoadInst *LI = cast<LoadInst>(SI->getValueOperand());
 530
 531   // Make sure the load and the store have no dependencies (i.e. other loads and
 532   // stores) in the loop. We ignore the direct dependency between SI and LI here
 533   // and check it later.
 534   DependenceAnalysis &DA = getAnalysis<DependenceAnalysis>();
 535   for (Loop::block_iterator BI = CurLoop->block_begin(),
 536        BE = CurLoop->block_end(); BI != BE; ++BI)
 537     for (BasicBlock::iterator I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I)
 538       if (&*I != SI && &*I != LI && I->mayReadOrWriteMemory()) {
 539         // First, check if there is a dependence of the store.
 540         OwningPtr<Dependence> DS(DA.depends(SI, I, true));
 541         if (DS)
 542           return false;
 543         // If the scanned instructon may modify memory then we also have to
 544         // check for dependencys on the load.
 545         if (I->mayWriteToMemory()) {
 546           OwningPtr<Dependence> DL(DA.depends(I, LI, true));
 547           if (DL)
 548             return false;
 549         }
 550       }
 551
 552   // Now check the dependency between SI and LI. If there is no dependency we
 553   // can safely emit a memcpy.
 554   OwningPtr<Dependence> Dep(DA.depends(SI, LI, true));
 555   if (Dep)
 556     return false;
 557
 558   // The trip count of the loop and the base pointer of the addrec SCEV is
 559   // guaranteed to be loop invariant, which means that it should dominate the
 560   // header.  This allows us to insert code for it in the preheader.
 561   BasicBlock *Preheader = CurLoop->getLoopPreheader();
 562   IRBuilder<> Builder(Preheader->getTerminator());
 563   SCEVExpander Expander(*SE, "loop-idiom");
 564
 565   // Okay, we have a strided store "p[i]" of a loaded value.  We can turn
 566   // this into a memcpy in the loop preheader now if we want.
 567   Value *StoreBasePtr =
 568     Expander.expandCodeFor(StoreEv->getStart(),
 569                            Builder.getInt8PtrTy(SI->getPointerAddressSpace()),
 570                            Preheader->getTerminator());
 571   Value *LoadBasePtr =
 572     Expander.expandCodeFor(LoadEv->getStart(),
 573                            Builder.getInt8PtrTy(LI->getPointerAddressSpace()),
 574                            Preheader->getTerminator());
 575
 576   // Okay, everything is safe, we can transform this!
 577
 578
 579   // The # stored bytes is (BECount+1)*Size.  Expand the trip count out to
 580   // pointer size if it isn't already.
 581   Type *IntPtr = TD->getIntPtrType(SI->getType());
 582   BECount = SE->getTruncateOrZeroExtend(BECount, IntPtr);
 583
 584   const SCEV *NumBytesS = SE->getAddExpr(BECount, SE->getConstant(IntPtr, 1),
 585                                          SCEV::FlagNUW);
 586   if (StoreSize != 1)
 587     NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtr, StoreSize),
 588                                SCEV::FlagNUW);
 589
 590   Value *NumBytes =
 591     Expander.expandCodeFor(NumBytesS, IntPtr, Preheader->getTerminator());
 592
 593   CallInst *NewCall =
 594     Builder.CreateMemCpy(StoreBasePtr, LoadBasePtr, NumBytes,
 595                          std::min(SI->getAlignment(), LI->getAlignment()));
 596   NewCall->setDebugLoc(SI->getDebugLoc());
 597
 598   DEBUG(dbgs() << "  Formed memcpy: " << *NewCall << "\n"
 599                << "    from load ptr=" << *LoadEv << " at: " << *LI << "\n"
 600                << "    from store ptr=" << *StoreEv << " at: " << *SI << "\n");
 601
 602
 603   // Okay, the memset has been formed.  Zap the original store and anything that
 604   // feeds into it.
 605   deleteDeadInstruction(SI, *SE, TLI);
 606   ++NumMemCpy;
 607   return true;
 608 }