+/// processLoopStoreOfLoopLoad - We see a strided store whose value is a
+/// same-strided load.
+bool LoopIdiomRecognize::
+processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize,
+ const SCEVAddRecExpr *StoreEv,
+ const SCEVAddRecExpr *LoadEv,
+ const SCEV *BECount) {
+ // If we're not allowed to form memcpy, we fail.
+ if (!TLI->has(LibFunc::memcpy))
+ return false;
+
+ LoadInst *LI = cast<LoadInst>(SI->getValueOperand());
+
+ // Make sure the load and the store have no dependencies (i.e. other loads and
+ // stores) in the loop. We ignore the direct dependency between SI and LI here
+ // and check it later.
+ DependenceAnalysis &DA = getAnalysis<DependenceAnalysis>();
+ bool isMemcpySafe = true;
+ for (Loop::block_iterator BI = CurLoop->block_begin(),
+ BE = CurLoop->block_end(); BI != BE; ++BI)
+ for (BasicBlock::iterator I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I)
+ if (&*I != SI && &*I != LI && I->mayReadOrWriteMemory()) {
+ // First, check if there is a dependence of the store.
+ OwningPtr<Dependence> DS(DA.depends(SI, I, true));
+ if (DS)
+ return false;
+ // If the scanned instructon may modify memory then we also have to
+ // check for dependencys on the load.
+ if (I->mayWriteToMemory()) {
+ OwningPtr<Dependence> DL(DA.depends(I, LI, true));
+ if (DL)
+ return false;
+ }
+ }
+
+ // Now check the dependency between SI and LI. If there is no dependency we
+ // can safely emit a memcpy.
+ OwningPtr<Dependence> Dep(DA.depends(SI, LI, true));
+ if (Dep) {
+ // If there is a dependence but the direction is positive we can still
+ // safely turn this into memmove.
+ if (Dep->getLevels() != 1 ||
+ Dep->getDirection(1) != Dependence::DVEntry::GT)
+ return false;
+ isMemcpySafe = false;
+ }
+
+ // The trip count of the loop and the base pointer of the addrec SCEV is
+ // guaranteed to be loop invariant, which means that it should dominate the
+ // header. This allows us to insert code for it in the preheader.
+ BasicBlock *Preheader = CurLoop->getLoopPreheader();
+ IRBuilder<> Builder(Preheader->getTerminator());
+ SCEVExpander Expander(*SE, "loop-idiom");
+
+ // Okay, we have a strided store "p[i]" of a loaded value. We can turn
+ // this into a memcpy in the loop preheader now if we want.
+ Value *StoreBasePtr =
+ Expander.expandCodeFor(StoreEv->getStart(),
+ Builder.getInt8PtrTy(SI->getPointerAddressSpace()),
+ Preheader->getTerminator());
+ Value *LoadBasePtr =
+ Expander.expandCodeFor(LoadEv->getStart(),
+ Builder.getInt8PtrTy(LI->getPointerAddressSpace()),
+ Preheader->getTerminator());
+
+ // Okay, everything is safe, we can transform this!
+
+
+ // The # stored bytes is (BECount+1)*Size. Expand the trip count out to
+ // pointer size if it isn't already.
+ Type *IntPtr = TD->getIntPtrType(SI->getType());
+ BECount = SE->getTruncateOrZeroExtend(BECount, IntPtr);
+
+ const SCEV *NumBytesS = SE->getAddExpr(BECount, SE->getConstant(IntPtr, 1),
+ SCEV::FlagNUW);
+ if (StoreSize != 1)
+ NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtr, StoreSize),
+ SCEV::FlagNUW);
+
+ Value *NumBytes =
+ Expander.expandCodeFor(NumBytesS, IntPtr, Preheader->getTerminator());
+
+ CallInst *NewCall;
+ unsigned Align = std::min(SI->getAlignment(), LI->getAlignment());
+ if (isMemcpySafe) {
+ NewCall = Builder.CreateMemCpy(StoreBasePtr, LoadBasePtr, NumBytes, Align);
+ ++NumMemCpy;
+ } else {
+ NewCall = Builder.CreateMemMove(StoreBasePtr, LoadBasePtr, NumBytes, Align);
+ ++NumMemMove;
+ }
+ NewCall->setDebugLoc(SI->getDebugLoc());
+
+ DEBUG(dbgs() << " Formed " << (isMemcpySafe ? "memcpy: " : "memmove: ")
+ << *NewCall << "\n"
+ << " from load ptr=" << *LoadEv << " at: " << *LI << "\n"
+ << " from store ptr=" << *StoreEv << " at: " << *SI << "\n");
+
+
+ // Okay, the memset has been formed. Zap the original store and anything that
+ // feeds into it.
+ deleteDeadInstruction(SI, *SE, TLI);
+ return true;
+}