[loop idiom Recognition] support memcpy for multiple consecutive loads and stores

[DIVYA]

Summary

This pass converts multiple consecutive loads and stores inside a loop to memcpy operation.
For example, the stores and loads in the below code can be converted to a memcpy .

struct foo
{

int a;
int b;

} f,g;

for(int i=0;i<n;i++)
{

f[i].a  =  g[i].a;
f[i].b  =  g[i].b;

}

Worked in collaboration with Sebastian Pop and Aditya Kumar.

[mgrang]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

162

Extra newline.

371

Extra newline.

459

Ditto.

497

Ditto.

918

Use i != e instead of i < e.

952

This loop looks a bit hacky. Can this be re-written in a better way?

955

Check indentation.

1203–1204

Newline removed.

1607–1608

Newline removed.

test/Transforms/LoopIdiom/memcpy_structPattern.ll

12 ↗

(On Diff #104483)

Can the test case be simplified/minimized by removing unwanted/extra attributes?

[mgrang]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

900–902

Extra / in comments. Also check comment spacing.

test/Transforms/LoopIdiom/memcpy_structPattern.ll

1 ↗

(On Diff #104483)

Unit test names follow all lowercase naming convention: memcpy_struct_pattern.ll

[DIVYA]

• Removed Extra Newlines
• Added IndexQueue(SmallVector) for storing possible consecutive stores
• changed testcase filename

[haicheng]

Please check the inlined comment.

Is it possible to reuse the code of processLoopStores() and processLoopStridedStore()?

Haicheng

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

527

I think this comment should be changed.

900

I think we need to emphasize that loads and stores are consecutive.

930

What if FirstStoreLoad is nullptr?

968

Same thing here.

1070

Please check the format.

1077

memset?

1105

memset?

[DIVYA]

• Updated some comments

[haicheng]

Just a few more comments. Please use clang format on your code.

Haicheng

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

981

I think you can remove this one or change it to an assert.

At this point, I think we know the stores have the same strides and loads have the same strides as their users (stores), so the strides of the loads should be the same.

1148

What if some Loads/Stores are atomic and some are not?

[DIVYA]

• If there are multiple stores and loads ,which are consecutive, but if any of them is atomic , then it won't be converted to memcpy.
• isAtomicStoreLoad flag checks for any atomic store or load, when there are multiple stores and loads .
• If there is single store and load , then it will converted to memcpy or atomic memcpy depending on whether the store and load are atomic or not.

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

976

Can we just return from here?

[DIVYA]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

968

This will be checked in the isLegalStore() function itself.

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

930

Then you can use cast instead of dyn_cast

[DIVYA]

• Changed dyn_cast to cast

[DIVYA]

ping

[haicheng]

I think you can refactor your code to reuse most of the implementation of processLoopStores() and processLoopStridedStore(). Maybe just add a flag to do the extra work for the loads.

[DIVYA]

• Refactored code to reuse implementation of processLoopStores() and processLoopStridedStore()
• Added ForMemcpy flag

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

134

I think you can pass in an enum which has value ForMemset, ForMemsetPattern, ForMemcpy like LegalStoreKind above or just use LegalStoreKind if possible.

650–674

I think code here can refactor with code above

692

I think processLoopStoreOfLoopLoad() can refactor with processLoopStridedStore(), then you don't need if...else... here.

[DIVYA]

• Used enum for ForMemcpy
• Refactored some code

[DIVYA]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

692

processLoopStoreOfLoopLoad() function was already present,so I haven't refactored it with processLoopStridedStore() in this patch.I can do that in the next patch

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

624

Please add a comment to make it clear it is for memcpy.

or add if (memcpy)

or write this part as a switch.

636–641

clang-format here

692

I think you can go ahead.

[DIVYA]

• modified comment

[DIVYA]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

692

So should I do it in this patch or next one?

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

692

I think in this patch.

[DIVYA]

• processLoopStoreOfLoopLoad() refactored with processLoopStridedStore(),

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

790

a space between stride and comma.

794–802

This part can be written as

if (Memset)
  SplatValue = 
else if (memsetpattern)
  Patternvalue =

1163

This can be changed to

if (memset)

1166

this can be changed to

else if (memset_pattern)

1196–1203

I think after creating newCall, setDebugLoc and debug dumping can be refactored too.

[DIVYA]

• setDebugLoc and debug dumping refactored

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

144

I think we should use MemIdiom and IsLoopMemset can be removed.

[DIVYA]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

144

But when processLoopStridedStore() is called from processLoopMemSet() function , then IsLoopMemset is set true and when it is called from processLoopStores() function , then IsLoopMemset is set false.Even though both can have MemIdiom set to LegalStoreKind::Memset .So using MemIdiom alone would not be sufficient.As, we need IsLoopMemset to indicate if memset which can be promoted to a large memset.

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

144

Yes, you are right. I think we can move the check avoidLIRForMultiBlockLoop() much earlier so that we don't need this flag and we can save compilation time. But, we can do that in the next patch.

922–1096

I think here can be written as

if (Memset)
else if (MemsetPattern)
else (Memcpy)

not nested if

[DIVYA]

• Removed nested if

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

575

SL[i]->getValueOperand() => FirstStoredVal

632

SL[k]->getValueOperand() => SecondStoredVal

842

not only memset here

[DIVYA]

• modified comment

[haicheng]

LGTM

Thanks for working on that. Please fully check the correctness before committing the patch.

[DIVYA]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

public:
 
   bool runOnLoop(Loop *L);
 
 private:
   typedef SmallVector<StoreInst *, 8> StoreList;
   typedef MapVector<Value *, StoreList> StoreListMap;
   StoreListMap StoreRefsForMemset;
   StoreListMap StoreRefsForMemsetPattern;
-  StoreList StoreRefsForMemcpy;
+  StoreListMap StoreRefsForMemcpy;
   bool HasMemset;
   bool HasMemsetPattern;
   bool HasMemcpy;
   /// Return code for isLegalStore()
   enum LegalStoreKind {
     None = 0,
     Memset,
     MemsetPattern,
     Memcpy,
     UnorderedAtomicMemcpy,
     DontUse // Dummy retval never to be used. Allows catching errors in retval
             // handling.
   };
 
   /// \name Countable Loop Idiom Handling
   /// @{
 
   bool runOnCountableLoop();
   bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
                       SmallVectorImpl<BasicBlock *> &ExitBlocks);
 
   void collectStores(BasicBlock *BB);
   LegalStoreKind isLegalStore(StoreInst *SI);
   bool processLoopStores(SmallVectorImpl<StoreInst *> &SL, const SCEV *BECount,
                          bool ForMemset);
   bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount);
 
   bool processLoopStridedStore(Value *DestPtr, unsigned StoreSize,
                                unsigned StoreAlignment, Value *StoredVal,
                                Instruction *TheStore,
                                SmallPtrSetImpl<Instruction *> &Stores,
                                const SCEVAddRecExpr *Ev, const SCEV *BECount,
                                bool NegStride, bool IsLoopMemset = false);
-  bool processLoopStoreOfLoopLoad(StoreInst *SI, const SCEV *BECount);
+  bool processLoopStoreOfLoopLoad(SmallVectorImpl<StoreInst *> &SL,
+      const SCEV *BECount);
+  bool processLoopStoreOfLoopLoadMain(
+      Value *DestPtr, unsigned StoreSize, StoreInst *TheStore,LoadInst *TheLoad,
+      SmallPtrSetImpl<Instruction *> &Stores, const SCEVAddRecExpr *Ev,
+      Value *LoadPtr, const SCEVAddRecExpr *LoadEv,
+      const SCEV *BECount, bool NegStride);
   bool avoidLIRForMultiBlockLoop(bool IsMemset = false,
                                  bool IsLoopMemset = false);
 
   /// @}
   /// \name Noncountable Loop Idiom Handling
   /// @{
 
   bool runOnNoncountableLoop();
 
   bool recognizePopcount();
   void transformLoopToPopcount(BasicBlock *PreCondBB, Instruction *CntInst,
                                PHINode *CntPhi, Value *Var);
   bool recognizeAndInsertCTLZ();
   void transformLoopToCountable(BasicBlock *PreCondBB, Instruction *CntInst,
                                 PHINode *CntPhi, Value *Var, const DebugLoc DL,
                                 bool ZeroCheck, bool IsCntPhiUsedOutsideLoop);
  
   /// @}
 };
 
 class LoopIdiomRecognizeLegacyPass : public LoopPass {
 public:
   static char ID;
   explicit LoopIdiomRecognizeLegacyPass() : LoopPass(ID) {
     initializeLoopIdiomRecognizeLegacyPassPass(
LoopIdiomRecognize::isLegalStore(StoreInst *SI) {
 
   // Don't touch volatile stores.
   if (SI->isVolatile())
     return LegalStoreKind::None;
   // We only want simple or unordered-atomic stores.
   if (!SI->isUnordered())
     return LegalStoreKind::None;
 
   // Don't convert stores of non-integral pointer types to memsets (which stores
   // integers).
   if (DL->isNonIntegralPointerType(SI->getValueOperand()->getType()))
     return LegalStoreKind::None;
 
   // Avoid merging nontemporal stores.
   if (SI->getMetadata(LLVMContext::MD_nontemporal))
     return LegalStoreKind::None;
 
if (!UnorderedAtomic && HasMemset && SplatValue &&
     // It looks like we can use PatternValue!
     return LegalStoreKind::MemsetPattern;
   }
 
   // Otherwise, see if the store can be turned into a memcpy.
   if (HasMemcpy) {
     // Check to see if the stride matches the size of the store.  If so, then we
     // know that every byte is touched in the loop.
-    APInt Stride = getStoreStride(StoreEv);
-    unsigned StoreSize = getStoreSizeInBytes(SI, DL);
-    if (StoreSize != Stride && StoreSize != -Stride)
-      return LegalStoreKind::None;
 
     // The store must be feeding a non-volatile load.
     LoadInst *LI = dyn_cast<LoadInst>(SI->getValueOperand());
 
     // Only allow non-volatile loads
     if (!LI || LI->isVolatile())
       return LegalStoreKind::None;
     // Only allow simple or unordered-atomic loads
if (HasMemcpy) {
     // The store and load must share the same stride.
     if (StoreEv->getOperand(1) != LoadEv->getOperand(1))
       return LegalStoreKind::None;
 
     // Success.  This store can be converted into a memcpy.
     UnorderedAtomic = UnorderedAtomic || LI->isAtomic();
     return UnorderedAtomic ? LegalStoreKind::UnorderedAtomicMemcpy
                            : LegalStoreKind::Memcpy;
   }
   // This store can't be transformed into a memset/memcpy.
   return LegalStoreKind::None;
 }
 
 void LoopIdiomRecognize::collectStores(BasicBlock *BB) {
   StoreRefsForMemset.clear();
   StoreRefsForMemsetPattern.clear();
   StoreRefsForMemcpy.clear();
case LegalStoreKind::Memset: {
       StoreRefsForMemset[Ptr].push_back(SI);
     } break;
     case LegalStoreKind::MemsetPattern: {
       // Find the base pointer.
       Value *Ptr = GetUnderlyingObject(SI->getPointerOperand(), *DL);
       StoreRefsForMemsetPattern[Ptr].push_back(SI);
     } break;
     case LegalStoreKind::Memcpy:
-    case LegalStoreKind::UnorderedAtomicMemcpy:
-      StoreRefsForMemcpy.push_back(SI);
-      break;
+    case LegalStoreKind::UnorderedAtomicMemcpy: {
+      //Find the base pointer.
+      Value *Ptr = GetUnderlyingObject(SI->getPointerOperand(), *DL);
+      StoreRefsForMemcpy[Ptr].push_back(SI);
+    } break;
     default:
       assert(false && "unhandled return value");
       break;
     }
   }
 }
 
 /// runOnLoopBlock - Process the specified block, which lives in a counted loop
 /// with the specified backedge count.  This block is known to be in the current
 /// loop and not in any subloops.
 bool LoopIdiomRecognize::runOnLoopBlock(
     BasicBlock *BB, const SCEV *BECount,
bool LoopIdiomRecognize::runOnLoopBlock(
   // optimized into a memset (memset_pattern).  The latter most commonly happens
   // with structs and handunrolled loops.
   for (auto &SL : StoreRefsForMemset)
     MadeChange |= processLoopStores(SL.second, BECount, true);
 
   for (auto &SL : StoreRefsForMemsetPattern)
     MadeChange |= processLoopStores(SL.second, BECount, false);
 
   // Optimize the store into a memcpy, if it feeds an similarly strided load.
   for (auto &SI : StoreRefsForMemcpy)
-    MadeChange |= processLoopStoreOfLoopLoad(SI, BECount);
+    MadeChange |= processLoopStoreOfLoopLoad(SI.second, BECount);
 
   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     Instruction *Inst = &*I++;
     // Look for memset instructions, which may be optimized to a larger memset.
     if (MemSetInst *MSI = dyn_cast<MemSetInst>(Inst)) {
       WeakTrackingVH InstPtr(&*I);
       if (!processLoopMemSet(MSI, BECount))
         continue;
for (unsigned i = 0, e = SL.size(); i < e; ++i) {
     const SCEVAddRecExpr *FirstStoreEv =
         cast<SCEVAddRecExpr>(SE->getSCEV(FirstStorePtr));
     APInt FirstStride = getStoreStride(FirstStoreEv);
     unsigned FirstStoreSize = getStoreSizeInBytes(SL[i], DL);
 
     // See if we can optimize just this store in isolation.
     if (FirstStride == FirstStoreSize || -FirstStride == FirstStoreSize) {
       Heads.insert(SL[i]);
       continue;
     }
 
     Value *FirstSplatValue = nullptr;
     Constant *FirstPatternValue = nullptr;
 
     if (ForMemset)
       FirstSplatValue = isBytewiseValue(FirstStoredVal);
     else
for (auto &k : IndexQueue) {
       else
         SecondPatternValue = getMemSetPatternValue(SecondStoredVal, DL);
 
       assert((SecondSplatValue || SecondPatternValue) &&
              "Expected either splat value or pattern value.");
 
       if (isConsecutiveAccess(SL[i], SL[k], *DL, *SE, false)) {
         if (ForMemset) {
           if (FirstSplatValue != SecondSplatValue)
             continue;
         } else {
           if (FirstPatternValue != SecondPatternValue)
             continue;
         }
         Tails.insert(SL[k]);
         Heads.insert(SL[i]);
         ConsecutiveChain[SL[i]] = SL[k];
         break;
       }
     }
   }
 
   // We may run into multiple chains that merge into a single chain. We mark the
   // stores that we transformed so that we don't visit the same store twice.
   SmallPtrSet<Value *, 16> TransformedStores;
   bool Changed = false;
 
   // For stores that start but don't end a link in the chain:
   for (SetVector<StoreInst *>::iterator it = Heads.begin(), e = Heads.end();
        it != e; ++it) {
     if (Tails.count(*it))
       continue;
 
     // We found a store instr that starts a chain. Now follow the chain and try
     // to transform it.
     SmallPtrSet<Instruction *, 8> AdjacentStores;
     StoreInst *I = *it;
 
     StoreInst *HeadStore = I;
     unsigned StoreSize = 0;
 
     // Collect the chain into a list.
     while (Tails.count(I) || Heads.count(I)) {
       if (TransformedStores.count(I))
         break;
       AdjacentStores.insert(I);
 
       StoreSize += getStoreSizeInBytes(I, DL);
       // Move to the next value in the chain.
       I = ConsecutiveChain[I];
     }
 
     Value *StoredVal = HeadStore->getValueOperand();
     Value *StorePtr = HeadStore->getPointerOperand();
     const SCEVAddRecExpr *StoreEv = cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
     APInt Stride = getStoreStride(StoreEv);
 
     // Check to see if the stride matches the size of the stores.  If so, then
     // we know that every byte is touched in the loop.
     if (StoreSize != Stride && StoreSize != -Stride)
       continue;
 
     bool NegStride = StoreSize == -Stride;
 
     if (processLoopStridedStore(StorePtr, StoreSize, HeadStore->getAlignment(),
                                 StoredVal, HeadStore, AdjacentStores, StoreEv,
                                 BECount, NegStride)) {
       TransformedStores.insert(AdjacentStores.begin(), AdjacentStores.end());
       Changed = true;
     }
   }
 
   return Changed;
 }
 
 /// processLoopMemSet - See if this memset can be promoted to a large memset.
 bool LoopIdiomRecognize::processLoopMemSet(MemSetInst *MSI,
                                            const SCEV *BECount) {
   // We can only handle non-volatile memsets with a constant size.
   if (MSI->isVolatile() || !isa<ConstantInt>(MSI->getLength()))
     return false;
 
   // If we're not allowed to hack on memset, we fail.
   if (!HasMemset)
     return false;
if (StoreSize != 1)
     Index = SE->getMulExpr(Index, SE->getConstant(IntPtr, StoreSize),
                            SCEV::FlagNUW);
   return SE->getMinusSCEV(Start, Index);
 }
 
 /// processLoopStridedStore - We see a strided store of some value.  If we can
 /// transform this into a memset or memset_pattern in the loop preheader, do so.
 bool LoopIdiomRecognize::processLoopStridedStore(
     Value *DestPtr, unsigned StoreSize, unsigned StoreAlignment,
     Value *StoredVal, Instruction *TheStore,
     SmallPtrSetImpl<Instruction *> &Stores, const SCEVAddRecExpr *Ev,
     const SCEV *BECount, bool NegStride, bool IsLoopMemset) {
   Value *SplatValue = isBytewiseValue(StoredVal);
   Constant *PatternValue = nullptr;
 
   if (!SplatValue)
     PatternValue = getMemSetPatternValue(StoredVal, DL);
 
   assert((SplatValue || PatternValue) &&
          "Expected either splat value or pattern value.");
 
   // 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.
   unsigned DestAS = DestPtr->getType()->getPointerAddressSpace();
   BasicBlock *Preheader = CurLoop->getLoopPreheader();
   IRBuilder<> Builder(Preheader->getTerminator());
   SCEVExpander Expander(*SE, *DL, "loop-idiom");
 
if (mayLoopAccessLocation(BasePtr, MRI_ModRef, CurLoop, BECount, StoreSize,
     // If we generated new code for the base pointer, clean up.
     RecursivelyDeleteTriviallyDeadInstructions(BasePtr, TLI);
     return false;
   }
 
   if (avoidLIRForMultiBlockLoop(/*IsMemset=*/true, IsLoopMemset))
     return false;
 
   // Okay, everything looks good, insert the memset.
 
   // The # stored bytes is (BECount+1)*Size.  Expand the trip count out to
   // pointer size if it isn't already.
   BECount = SE->getTruncateOrZeroExtend(BECount, IntPtr);
 
   const SCEV *NumBytesS =
       SE->getAddExpr(BECount, SE->getOne(IntPtr), SCEV::FlagNUW);
   if (StoreSize != 1) {
if (SplatValue) {
     // an constant array of 16-bytes.  Plop the value into a mergable global.
     GlobalVariable *GV = new GlobalVariable(*M, PatternValue->getType(), true,
                                             GlobalValue::PrivateLinkage,
                                             PatternValue, ".memset_pattern");
     GV->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); // Ok to merge these.
     GV->setAlignment(16);
     Value *PatternPtr = ConstantExpr::getBitCast(GV, Int8PtrTy);
     NewCall = Builder.CreateCall(MSP, {BasePtr, PatternPtr, NumBytes});
-  }
 
   DEBUG(dbgs() << "  Formed memset: " << *NewCall << "\n"
                << "    from store to: " << *Ev << " at: " << *TheStore << "\n");
   NewCall->setDebugLoc(TheStore->getDebugLoc());
 
   // Okay, the memset has been formed.  Zap the original store and anything that
   // feeds into it.
   for (auto *I : Stores)
     deleteDeadInstruction(I);
   ++NumMemSet;
   return true;
 }
 
-/// If the stored value is a strided load in the same loop with the same stride
-/// this may be transformable into a memcpy.  This kicks in for stuff like
+/// If there are one or multiple stored values , which are strided loads
+/// in the same loop with the same stride , then this amy be transformed into
+/// a memcpy.This kicks in for stuff like
 /// for (i) A[i] = B[i];
-bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
-                                                    const SCEV *BECount) {
-  assert(SI->isUnordered() && "Expected only non-volatile non-ordered stores.");
+/// for (i)
+/// {
+///   A[i].a = B[i].a
+///   A[i].b = B[i].b
+/// }
+bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(
+    SmallVectorImpl<StoreInst *> &SL,const SCEV *BECount) {
+  // Try to find consecutive stores and loads that can be transformed
+  // into memcpy.
+  SetVector<StoreInst *> Heads, Tails;
+  SmallDenseMap<StoreInst *, StoreInst *> ConsecutiveChain;
 
-  Value *StorePtr = SI->getPointerOperand();
+  // Do a quadratic search on all of the given stores and find
+  // all of the pairs of stores that follow each other.
+  SmallVector<unsigned, 16> IndexQueue;
+  for (unsigned i = 0, e = SL.size(); i < e; ++i) {
+    assert(SL[i]->isUnordered() && 
+           "Expected only non-volatile non-ordered stores.");
+
+    Value *FirstStorePtr = SL[i]->getPointerOperand();
+    const SCEVAddRecExpr *FirstStoreEv =
+       cast<SCEVAddRecExpr>(SE->getSCEV(FirstStorePtr));
+    APInt FirstStride = getStoreStride(FirstStoreEv);
+
+    unsigned FirstStoreSize = getStoreSizeInBytes(SL[i], DL);
+
+    LoadInst *FirstStoreLoad = dyn_cast<LoadInst>(SL[i]->getValueOperand());
+    assert(FirstStoreLoad->isUnordered() && 
+    "Expected only non-volatile non-ordered loads.");
+    Value *FirstLoadPtr =
+        GetUnderlyingObject(FirstStoreLoad->getPointerOperand(), *DL);
+
+    const SCEVAddRecExpr *FirstLoadEv =
+     dyn_cast<SCEVAddRecExpr>(SE->getSCEV(FirstStoreLoad->getPointerOperand()));
+
+    // See if we can optimize just this store in isolation.
+    if (FirstStride == FirstStoreSize || -FirstStride == FirstStoreSize) {
+      Heads.insert(SL[i]);
+      continue;
+    }
+
+    IndexQueue.clear();
+    // If a store has multiple consecutive store candidates, search Stores
+    // array according to the sequence: from i+1 to e, then from i-1 to 0.
+    // This is because usually pairing with immediate succeeding or preceding
+    // candidate create the best chance to find memcpy opportunity.
+
+    unsigned j = 0;
+    for (j = i + 1; j < e; ++j)
+      IndexQueue.push_back(j);
+    for (j = i; j > 0; --j)
+      IndexQueue.push_back(j - 1);
+
+    for (auto &k : IndexQueue) {
+      assert(SL[k]->isUnordered() && 
+       "Expected only non-volatile non-ordered stores.");
+      Value *SecondStorePtr = SL[k]->getPointerOperand();
+      const SCEVAddRecExpr *SecondStoreEv =
+                        cast<SCEVAddRecExpr>(SE->getSCEV(SecondStorePtr));
+
+      APInt SecondStride = getStoreStride(SecondStoreEv);
+      if (FirstStride != SecondStride)
+        continue;
+
+      LoadInst *SecondStoreLoad = dyn_cast<LoadInst>(SL[k]->getValueOperand());
+      assert(SecondStoreLoad->isUnordered() && 
+       "Expected only non-volatile non-ordered loads.");
+      Value *SecondLoadPtr =
+          GetUnderlyingObject(SecondStoreLoad->getPointerOperand(), *DL);
+
+      if (FirstLoadPtr != SecondLoadPtr)
+        continue;
+
+      const SCEVAddRecExpr *SecondLoadEv =
+      dyn_cast<SCEVAddRecExpr>(
+          SE->getSCEV(SecondStoreLoad->getPointerOperand()));
+
+      // The stride of both loads should be equal
+      if (FirstLoadEv->getOperand(1) != SecondLoadEv->getOperand(1))
+        continue;
+
+      //Both stores and loads should be consecutive
+      if (isConsecutiveAccess(SL[i], SL[k], *DL, *SE, false)) {
+        if (isConsecutiveAccess(
+          FirstStoreLoad, SecondStoreLoad, *DL, *SE, false)) {
+          Tails.insert(SL[k]);
+          Heads.insert(SL[i]);
+          ConsecutiveChain[SL[i]] = SL[k];
+          break;
+        }
+      }
+   }
+  }
+
+  SmallPtrSet<Value *, 16> TransformedStores;
+  bool Changed = false;
+  // For stores that start but don't end a link in the chain:
+  for (SetVector<StoreInst *>::iterator it = Heads.begin(), e = Heads.end();
+        it != e; ++it) {
+  if (Tails.count(*it))
+      continue;
+
+    // We found a store instr that starts a chain. Now follow the chain and try
+    // to transform it.
+    SmallPtrSet<Instruction *, 8> AdjacentStores;
+    StoreInst *I = *it;
+
+    StoreInst *HeadStore = I;
+    unsigned StoreSize = 0;
+
+    // Collect the chain into a list.
+    while (Tails.count(I) || Heads.count(I)) {
+      if (TransformedStores.count(I))
+        break;
+      AdjacentStores.insert(I);
+
+      StoreSize += getStoreSizeInBytes(I, DL);
+      // Move to the next value in the chain.
+      I = ConsecutiveChain[I];
+    }
+
+    Value *StorePtr = HeadStore->getPointerOperand();
     const SCEVAddRecExpr *StoreEv = cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
     APInt Stride = getStoreStride(StoreEv);
-  unsigned StoreSize = getStoreSizeInBytes(SI, DL);
+
+    LoadInst *StoreLoadInst = dyn_cast<LoadInst>(HeadStore->getValueOperand());
+    Value *LoadPtr =
+        GetUnderlyingObject(StoreLoadInst->getPointerOperand(), *DL);
+    const SCEVAddRecExpr *LoadEv =
+      dyn_cast<SCEVAddRecExpr>(SE->getSCEV(StoreLoadInst->getPointerOperand()));
+
+
+    // Check to see if the stride matches the size of the stores.  If so, then
+    // we know that every byte is touched in the loop.
+    if (StoreSize != Stride && StoreSize != -Stride)
+      continue;
+
     bool NegStride = StoreSize == -Stride;
+    if (processLoopStoreOfLoopLoadMain(StorePtr, StoreSize, HeadStore,
+                                       StoreLoadInst, AdjacentStores,
+                                       StoreEv,LoadPtr,LoadEv, BECount,
+                                       NegStride)) {
+      TransformedStores.insert(AdjacentStores.begin(), AdjacentStores.end());
+      Changed = true;
+     }
+   }
 
-  // The store must be feeding a non-volatile load.
-  LoadInst *LI = cast<LoadInst>(SI->getValueOperand());
-  assert(LI->isUnordered() && "Expected only non-volatile non-ordered loads.");
+   return Changed;
+}
 
-  // See if the pointer expression is an AddRec like {base,+,1} on the current
-  // loop, which indicates a strided load.  If we have something else, it's a
-  // random load we can't handle.
-  const SCEVAddRecExpr *LoadEv =
-      cast<SCEVAddRecExpr>(SE->getSCEV(LI->getPointerOperand()));
+/// processLoopStoreOfLoopLoadMain - We see strided stores and loads , If we can
+/// transform this into a memcpy in the loop preheader , do so.
+bool LoopIdiomRecognize::processLoopStoreOfLoopLoadMain(
+    Value *DestPtr, unsigned StoreSize, StoreInst *TheStore,
+    LoadInst *TheLoad, SmallPtrSetImpl<Instruction *> &Stores,
+    const SCEVAddRecExpr *Ev, Value *LoadPtr,
+  const SCEVAddRecExpr *LoadEv, const SCEV *BECount, bool NegStride) {
 
   // 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, *DL, "loop-idiom");
 
-  const SCEV *StrStart = StoreEv->getStart();
-  unsigned StrAS = SI->getPointerAddressSpace();
+  const SCEV *StrStart = Ev->getStart();
+  unsigned StrAS =  DestPtr->getType()->getPointerAddressSpace();
   Type *IntPtrTy = Builder.getIntPtrTy(*DL, StrAS);
 
   // Handle negative strided loops.
   if (NegStride)
     StrStart = getStartForNegStride(StrStart, BECount, IntPtrTy, StoreSize, SE);
 
+  // TODO: ideally we should still be able to generate memset if SCEV expander
+  // is taught to generate the dependencies at the latest point.
+  if (!isSafeToExpand(StrStart, *SE))
+    return false;
   // 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.  However, this
   // would be unsafe to do if there is anything else in the loop that may read
   // or write the memory region we're storing to.  This includes the load that
   // feeds the stores.  Check for an alias by generating the base address and
   // checking everything.
   Value *StoreBasePtr = Expander.expandCodeFor(
       StrStart, Builder.getInt8PtrTy(StrAS), Preheader->getTerminator());
 
-  SmallPtrSet<Instruction *, 1> Stores;
-  Stores.insert(SI);
   if (mayLoopAccessLocation(StoreBasePtr, MRI_ModRef, CurLoop, BECount,
                             StoreSize, *AA, Stores)) {
     Expander.clear();
     // If we generated new code for the base pointer, clean up.
     RecursivelyDeleteTriviallyDeadInstructions(StoreBasePtr, TLI);
     return false;
   }
 
   const SCEV *LdStart = LoadEv->getStart();
-  unsigned LdAS = LI->getPointerAddressSpace();
+  unsigned LdAS = LoadPtr->getType()->getPointerAddressSpace();
 
   // Handle negative strided loops.
   if (NegStride)
     LdStart = getStartForNegStride(LdStart, BECount, IntPtrTy, StoreSize, SE);
 
+  // TODO: ideally we should still be able to generate memset if SCEV expander
+  // is taught to generate the dependencies at the latest point.
+  if (!isSafeToExpand(LdStart, *SE))
+    return false;
+
   // For a memcpy, we have to make sure that the input array is not being
   // mutated by the loop.
   Value *LoadBasePtr = Expander.expandCodeFor(
       LdStart, Builder.getInt8PtrTy(LdAS), Preheader->getTerminator());
 
   if (mayLoopAccessLocation(LoadBasePtr, MRI_Mod, CurLoop, BECount, StoreSize,
                             *AA, Stores)) {
     Expander.clear();
bool LoopIdiomRecognize::processLoopStoreOfLoopLoadMain(
 
   if (StoreSize != 1)
     NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtrTy, StoreSize),
                                SCEV::FlagNUW);
 
   Value *NumBytes =
       Expander.expandCodeFor(NumBytesS, IntPtrTy, Preheader->getTerminator());
 
-  unsigned Align = std::min(SI->getAlignment(), LI->getAlignment());
+  unsigned Align = std::min(TheStore->getAlignment(), TheLoad->getAlignment());
   CallInst *NewCall = nullptr;
   // Check whether to generate an unordered atomic memcpy:
   //  If the load or store are atomic, then they must neccessarily be unordered
   //  by previous checks.
-  if (!SI->isAtomic() && !LI->isAtomic())
+  if (!TheStore->isAtomic() && !TheLoad->isAtomic())
     NewCall = Builder.CreateMemCpy(StoreBasePtr, LoadBasePtr, NumBytes, Align);
   else {
     // We cannot allow unaligned ops for unordered load/store, so reject
     // anything where the alignment isn't at least the element size.
     if (Align < StoreSize)
       return false;
 
     // If the element.atomic memcpy is not lowered into explicit
     // loads/stores later, then it will be lowered into an element-size
     // specific lib call. If the lib call doesn't exist for our store size, then
     // we shouldn't generate the memcpy.
     if (StoreSize > TTI->getAtomicMemIntrinsicMaxElementSize())
       return false;
 
     NewCall = Builder.CreateElementUnorderedAtomicMemCpy(
         StoreBasePtr, LoadBasePtr, NumBytes, StoreSize);
 
     // Propagate alignment info onto the pointer args. Note that unordered
     // atomic loads/stores are *required* by the spec to have an alignment
     // but non-atomic loads/stores may not.
     NewCall->addParamAttr(0, Attribute::getWithAlignment(NewCall->getContext(),
-                                                         SI->getAlignment()));
+                                                     TheStore->getAlignment()));
     NewCall->addParamAttr(1, Attribute::getWithAlignment(NewCall->getContext(),
-                                                         LI->getAlignment()));
+                                                     TheLoad->getAlignment()));
   }
-  NewCall->setDebugLoc(SI->getDebugLoc());
+  NewCall->setDebugLoc(TheStore->getDebugLoc());
 
   DEBUG(dbgs() << "  Formed memcpy: " << *NewCall << "\n"
-               << "    from load ptr=" << *LoadEv << " at: " << *LI << "\n"
-               << "    from store ptr=" << *StoreEv << " at: " << *SI << "\n");
+               << "    from load ptr=" << *LoadEv << " at: " << *TheLoad << "\n"
+               << "    from store ptr=" << *Ev << " at: " << *TheStore << "\n");
 
   // Okay, the memcpy has been formed.  Zap the original store and anything that
   // feeds into it.
-  deleteDeadInstruction(SI);
+  for (auto *I : Stores)
+    deleteDeadInstruction(I);
   ++NumMemCpy;
   return true;
 }
 
 // When compiling for codesize we avoid idiom recognition for a multi-block loop
 // unless it is a loop_memset idiom or a memset/memcpy idiom in a nested loop.
 //
 bool LoopIdiomRecognize::avoidLIRForMultiBlockLoop(bool IsMemset,
                                                    bool IsLoopMemset) {
   if (ApplyCodeSizeHeuristics && CurLoop->getNumBlocks() > 1) {
     if (!CurLoop->getParentLoop() && (!IsMemset || !IsLoopMemset)) {
       DEBUG(dbgs() << "  " << CurLoop->getHeader()->getParent()->getName()
                    << " : LIR " << (IsMemset ? "Memset" : "Memcpy")
                    << " avoided: multi-block top-level loop\n");
       return true;
     }
   }
 
   return false;
 }
 
 bool LoopIdiomRecognize::runOnNoncountableLoop() {
   return recognizePopcount() || recognizeAndInsertCTLZ();
 }
 
 /// Check if the given conditional branch is based on the comparison between
 /// a variable and zero, and if the variable is non-zero, the control yields to
 /// the loop entry. If the branch matches the behavior, the variable involved
 /// in the comparison is returned. This function will be called to see if the
static CallInst *createPopcntIntrinsic(IRBuilder<> &IRBuilder, Value *Val,
   CI->setDebugLoc(DL);
 
   return CI;
 }
 
 static CallInst *createCTLZIntrinsic(IRBuilder<> &IRBuilder, Value *Val,
                                      const DebugLoc &DL, bool ZeroCheck) {
   Value *Ops[] = {Val, ZeroCheck ? IRBuilder.getTrue() : IRBuilder.getFalse()};
   Type *Tys[] = {Val->getType()};
 
   Module *M = IRBuilder.GetInsertBlock()->getParent()->getParent();
   Value *Func = Intrinsic::getDeclaration(M, Intrinsic::ctlz, Tys);
   CallInst *CI = IRBuilder.CreateCall(Func, Ops);
   CI->setDebugLoc(DL);
 
   return CI;
 }
 

test/Transforms/LoopIdiom/memcpy_struct_pattern.ll

+; RUN: opt -globals-aa -loop-idiom < %s -S | FileCheck %s
+
+; ModuleID = '<stdin>'
+source_filename = "../Newmemcpytest/test17.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.foo = type { i32, i32 }
+%struct.foo1 = type { i32 }
+%struct.foo3 = type { i32, i32, i32 }
+
+@bar3.g = private unnamed_addr constant [14 x %struct.foo] [%struct.foo { i32 2, i32 3 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }, %struct.foo { i32 2, i32 3 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }], align 16
+@bar4.g = private unnamed_addr constant [14 x %struct.foo1] [%struct.foo1 { i32 2 }, %struct.foo1 { i32 4 }, %struct.foo1 { i32 5 }, %struct.foo1 { i32 6 }, %struct.foo1 { i32 9 }, %struct.foo1 { i32 5 }, %struct.foo1 { i32 1 }, %struct.foo1 { i32 2 }, %struct.foo1 { i32 3 }, %struct.foo1 { i32 3 }, %struct.foo1 { i32 5 }, %struct.foo1 { i32 7 }, %struct.foo1 { i32 8 }, %struct.foo1 { i32 19 }], align 16
+@bar5.g = private unnamed_addr constant [14 x %struct.foo] [%struct.foo { i32 2, i32 3 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }, %struct.foo { i32 2, i32 3 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }], align 16
+@bar6.g = private unnamed_addr constant [14 x %struct.foo] [%struct.foo { i32 12, i32 3 }, %struct.foo { i32 3, i32 54 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }, %struct.foo { i32 2, i32 53 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 74, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }], align 16
+@bar7.g = private unnamed_addr constant [14 x %struct.foo] [%struct.foo { i32 2, i32 3 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }, %struct.foo { i32 2, i32 3 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }], align 16
+@bar8.g = private unnamed_addr constant [14 x %struct.foo] [%struct.foo { i32 2, i32 3 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }, %struct.foo { i32 2, i32 3 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }], align 16
+@bar9.g = private unnamed_addr constant [14 x %struct.foo3] [%struct.foo3 { i32 2, i32 3, i32 4 }, %struct.foo3 { i32 3, i32 4, i32 1 }, %struct.foo3 { i32 1, i32 8, i32 34 }, %struct.foo3 { i32 3, i32 2, i32 21 }, %struct.foo3 { i32 4, i32 5, i32 78 }, %struct.foo3 { i32 4, i32 5, i32 123 }, %struct.foo3 { i32 1, i32 2, i32 3 }, %struct.foo3 { i32 2, i32 3, i32 34 }, %struct.foo3 { i32 3, i32 4, i32 34 }, %struct.foo3 { i32 1, i32 8, i32 53 }, %struct.foo3 { i32 3, i32 2, i32 87 }, %struct.foo3 { i32 4, i32 5, i32 43 }, %struct.foo3 { i32 4, i32 5, i32 34 }, %struct.foo3 { i32 1, i32 2, i32 45 }], align 16
+@bar10.g = private unnamed_addr constant [14 x %struct.foo3] [%struct.foo3 { i32 2, i32 3, i32 4 }, %struct.foo3 { i32 3, i32 4, i32 1 }, %struct.foo3 { i32 1, i32 8, i32 34 }, %struct.foo3 { i32 3, i32 2, i32 21 }, %struct.foo3 { i32 4, i32 5, i32 78 }, %struct.foo3 { i32 4, i32 5, i32 123 }, %struct.foo3 { i32 1, i32 2, i32 3 }, %struct.foo3 { i32 2, i32 3, i32 34 }, %struct.foo3 { i32 3, i32 4, i32 34 }, %struct.foo3 { i32 1, i32 8, i32 53 }, %struct.foo3 { i32 3, i32 2, i32 87 }, %struct.foo3 { i32 4, i32 5, i32 43 }, %struct.foo3 { i32 4, i32 5, i32 34 }, %struct.foo3 { i32 1, i32 2, i32 45 }], align 16
+@bar11.g = private unnamed_addr constant [14 x %struct.foo3] [%struct.foo3 { i32 2, i32 3, i32 4 }, %struct.foo3 { i32 3, i32 4, i32 1 }, %struct.foo3 { i32 1, i32 8, i32 34 }, %struct.foo3 { i32 3, i32 2, i32 21 }, %struct.foo3 { i32 4, i32 5, i32 78 }, %struct.foo3 { i32 4, i32 5, i32 123 }, %struct.foo3 { i32 1, i32 2, i32 3 }, %struct.foo3 { i32 2, i32 3, i32 34 }, %struct.foo3 { i32 3, i32 4, i32 34 }, %struct.foo3 { i32 1, i32 8, i32 53 }, %struct.foo3 { i32 3, i32 2, i32 87 }, %struct.foo3 { i32 4, i32 5, i32 43 }, %struct.foo3 { i32 4, i32 5, i32 34 }, %struct.foo3 { i32 1, i32 2, i32 45 }], align 16
+@bar12.g = private unnamed_addr constant [14 x %struct.foo3] [%struct.foo3 { i32 2, i32 3, i32 4 }, %struct.foo3 { i32 3, i32 4, i32 1 }, %struct.foo3 { i32 1, i32 8, i32 34 }, %struct.foo3 { i32 3, i32 2, i32 21 }, %struct.foo3 { i32 4, i32 5, i32 78 }, %struct.foo3 { i32 4, i32 5, i32 123 }, %struct.foo3 { i32 1, i32 2, i32 3 }, %struct.foo3 { i32 2, i32 3, i32 34 }, %struct.foo3 { i32 3, i32 4, i32 34 }, %struct.foo3 { i32 1, i32 8, i32 53 }, %struct.foo3 { i32 3, i32 2, i32 87 }, %struct.foo3 { i32 4, i32 5, i32 43 }, %struct.foo3 { i32 4, i32 5, i32 34 }, %struct.foo3 { i32 1, i32 2, i32 45 }], align 16
+@bar13.g = private unnamed_addr constant [14 x %struct.foo] [%struct.foo { i32 2, i32 3 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }, %struct.foo { i32 2, i32 3 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }], align 16
+@bar14.g = private unnamed_addr constant [14 x %struct.foo1] [%struct.foo1 { i32 2 }, %struct.foo1 { i32 4 }, %struct.foo1 { i32 5 }, %struct.foo1 { i32 6 }, %struct.foo1 { i32 9 }, %struct.foo1 { i32 5 }, %struct.foo1 { i32 1 }, %struct.foo1 { i32 2 }, %struct.foo1 { i32 3 }, %struct.foo1 { i32 3 }, %struct.foo1 { i32 5 }, %struct.foo1 { i32 7 }, %struct.foo1 { i32 8 }, %struct.foo1 { i32 19 }], align 16
+@bar15.g = private unnamed_addr constant [14 x %struct.foo] [%struct.foo { i32 2, i32 3 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }, %struct.foo { i32 2, i32 3 }, %struct.foo { i32 3, i32 4 }, %struct.foo { i32 1, i32 8 }, %struct.foo { i32 3, i32 2 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 4, i32 5 }, %struct.foo { i32 1, i32 2 }], align 16
+
+; Function Attrs: nounwind uwtable
+define void @bar1(%struct.foo* nocapture %f) local_unnamed_addr #0 {
+entry:
+  %g = alloca [14 x %struct.foo], align 16
+  %0 = bitcast [14 x %struct.foo]* %g to i8*
+  call void @llvm.lifetime.start.p0i8(i64 112, i8* nonnull %0) #3
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 13, %entry ], [ %indvars.iv.next, %for.body ]
+  %a = getelementptr inbounds [14 x %struct.foo], [14 x %struct.foo]* %g, i64 0, i64 %indvars.iv, i32 0
+  %1 = load i32, i32* %a, align 8, !tbaa !1
+  %a3 = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 0
+  store i32 %1, i32* %a3, align 4, !tbaa !1
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, 0
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  call void @llvm.lifetime.end.p0i8(i64 112, i8* nonnull %0) #3
+  ret void
+; CHECK-LABEL: @bar1(
+; CHECK-NOT: call void @llvm.memcpy.p0i8.p0i8.i64
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) #1
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) #1
+
+; Function Attrs: nounwind uwtable
+define void @bar2(%struct.foo1* nocapture %f) local_unnamed_addr #0 {
+entry:
+  %g = alloca [14 x %struct.foo1], align 16
+  %0 = bitcast [14 x %struct.foo1]* %g to i8*
+  call void @llvm.lifetime.start.p0i8(i64 56, i8* nonnull %0) #3
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 13, %entry ], [ %indvars.iv.next, %for.body ]
+  %a = getelementptr inbounds [14 x %struct.foo1], [14 x %struct.foo1]* %g, i64 0, i64 %indvars.iv, i32 0
+  %1 = load i32, i32* %a, align 4, !tbaa !6
+  %a3 = getelementptr inbounds %struct.foo1, %struct.foo1* %f, i64 %indvars.iv, i32 0
+  store i32 %1, i32* %a3, align 4, !tbaa !6
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, 0
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  call void @llvm.lifetime.end.p0i8(i64 56, i8* nonnull %0) #3
+  ret void
+; CHECK-LABEL: @bar2(
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64
+; CHECK-NOT: store
+}
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar3(%struct.foo* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %a = getelementptr inbounds [14 x %struct.foo], [14 x %struct.foo]* @bar3.g, i64 0, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %a, align 8, !tbaa !1
+  %a3 = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 0
+  store i32 %0, i32* %a3, align 4, !tbaa !1
+  %b = getelementptr inbounds [14 x %struct.foo], [14 x %struct.foo]* @bar3.g, i64 0, i64 %indvars.iv, i32 1
+  %1 = load i32, i32* %b, align 4, !tbaa !8
+  %b8 = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 1
+  store i32 %1, i32* %b8, align 4, !tbaa !8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 14
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar3(
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64
+; CHECK-NOT: store
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i32, i1) #1
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar4(%struct.foo1* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %a = getelementptr inbounds [14 x %struct.foo1], [14 x %struct.foo1]* @bar4.g, i64 0, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %a, align 4, !tbaa !6
+  %a3 = getelementptr inbounds %struct.foo1, %struct.foo1* %f, i64 %indvars.iv, i32 0
+  store i32 %0, i32* %a3, align 4, !tbaa !6
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 14
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar4(
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64
+; CHECK-NOT: store
+}
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar5(%struct.foo* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %a = getelementptr inbounds [14 x %struct.foo], [14 x %struct.foo]* @bar5.g, i64 0, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %a, align 8, !tbaa !1
+  %b = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 1
+  store i32 %0, i32* %b, align 4, !tbaa !8
+  %b5 = getelementptr inbounds [14 x %struct.foo], [14 x %struct.foo]* @bar5.g, i64 0, i64 %indvars.iv, i32 1
+  %1 = load i32, i32* %b5, align 4, !tbaa !8
+  %a8 = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 0
+  store i32 %1, i32* %a8, align 4, !tbaa !1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 14
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar5(
+; CHECK-NOT: call void @llvm.memcpy.p0i8.p0i8.i64
+}
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar6(%struct.foo* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 13, %entry ], [ %indvars.iv.next, %for.body ]
+  %a = getelementptr inbounds [14 x %struct.foo], [14 x %struct.foo]* @bar6.g, i64 0, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %a, align 8, !tbaa !1
+  %a3 = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 0
+  store i32 %0, i32* %a3, align 4, !tbaa !1
+  %b = getelementptr inbounds [14 x %struct.foo], [14 x %struct.foo]* @bar6.g, i64 0, i64 %indvars.iv, i32 1
+  %1 = load i32, i32* %b, align 4, !tbaa !8
+  %b8 = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 1
+  store i32 %1, i32* %b8, align 4, !tbaa !8
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, 0
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar6(
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64
+; CHECK-NOT: store
+}
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar7(%struct.foo* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %a = getelementptr inbounds [14 x %struct.foo], [14 x %struct.foo]* @bar7.g, i64 0, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %a, align 8, !tbaa !1
+  %a3 = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 0
+  store i32 %0, i32* %a3, align 4, !tbaa !1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 14
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar7(
+; CHECK-NOT: call void @llvm.memcpy.p0i8.p0i8.i64
+}
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar8(%struct.foo* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %a = getelementptr inbounds [14 x %struct.foo], [14 x %struct.foo]* @bar8.g, i64 0, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %a, align 8, !tbaa !1
+  %b = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 1
+  store i32 %0, i32* %b, align 4, !tbaa !8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 14
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar8(
+; CHECK-NOT: call void @llvm.memcpy.p0i8.p0i8.i64
+}
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar9(%struct.foo3* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 13, %entry ], [ %indvars.iv.next, %for.body ]
+  %a = getelementptr inbounds [14 x %struct.foo3], [14 x %struct.foo3]* @bar9.g, i64 0, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %a, align 4, !tbaa !9
+  %a3 = getelementptr inbounds %struct.foo3, %struct.foo3* %f, i64 %indvars.iv, i32 0
+  store i32 %0, i32* %a3, align 4, !tbaa !9
+  %b = getelementptr inbounds [14 x %struct.foo3], [14 x %struct.foo3]* @bar9.g, i64 0, i64 %indvars.iv, i32 1
+  %1 = load i32, i32* %b, align 4, !tbaa !11
+  %b8 = getelementptr inbounds %struct.foo3, %struct.foo3* %f, i64 %indvars.iv, i32 1
+  store i32 %1, i32* %b8, align 4, !tbaa !11
+  %c = getelementptr inbounds [14 x %struct.foo3], [14 x %struct.foo3]* @bar9.g, i64 0, i64 %indvars.iv, i32 2
+  %2 = load i32, i32* %c, align 4, !tbaa !12
+  %c13 = getelementptr inbounds %struct.foo3, %struct.foo3* %f, i64 %indvars.iv, i32 2
+  store i32 %2, i32* %c13, align 4, !tbaa !12
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, 0
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar9(
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64
+; CHECK-NOT: store
+}
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar10(%struct.foo3* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 13, %entry ], [ %indvars.iv.next, %for.body ]
+  %a = getelementptr inbounds [14 x %struct.foo3], [14 x %struct.foo3]* @bar10.g, i64 0, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %a, align 4, !tbaa !9
+  %a3 = getelementptr inbounds %struct.foo3, %struct.foo3* %f, i64 %indvars.iv, i32 0
+  store i32 %0, i32* %a3, align 4, !tbaa !9
+  %b = getelementptr inbounds [14 x %struct.foo3], [14 x %struct.foo3]* @bar10.g, i64 0, i64 %indvars.iv, i32 1
+  %1 = load i32, i32* %b, align 4, !tbaa !11
+  %b8 = getelementptr inbounds %struct.foo3, %struct.foo3* %f, i64 %indvars.iv, i32 1
+  store i32 %1, i32* %b8, align 4, !tbaa !11
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, 0
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar10(
+; CHECK-NOT: call void @llvm.memcpy.p0i8.p0i8.i64
+}
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar11(%struct.foo3* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 13, %entry ], [ %indvars.iv.next, %for.body ]
+  %a = getelementptr inbounds [14 x %struct.foo3], [14 x %struct.foo3]* @bar11.g, i64 0, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %a, align 4, !tbaa !9
+  %a3 = getelementptr inbounds %struct.foo3, %struct.foo3* %f, i64 %indvars.iv, i32 0
+  store i32 %0, i32* %a3, align 4, !tbaa !9
+  %c = getelementptr inbounds [14 x %struct.foo3], [14 x %struct.foo3]* @bar11.g, i64 0, i64 %indvars.iv, i32 2
+  %1 = load i32, i32* %c, align 4, !tbaa !12
+  %c8 = getelementptr inbounds %struct.foo3, %struct.foo3* %f, i64 %indvars.iv, i32 2
+  store i32 %1, i32* %c8, align 4, !tbaa !12
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, 0
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar11(
+; CHECK-NOT: call void @llvm.memcpy.p0i8.p0i8.i64
+}
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar12(%struct.foo3* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 13, %entry ], [ %indvars.iv.next, %for.body ]
+  %a = getelementptr inbounds [14 x %struct.foo3], [14 x %struct.foo3]* @bar12.g, i64 0, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %a, align 4, !tbaa !9
+  %a3 = getelementptr inbounds %struct.foo3, %struct.foo3* %f, i64 %indvars.iv, i32 0
+  store i32 %0, i32* %a3, align 4, !tbaa !9
+  %b = getelementptr inbounds [14 x %struct.foo3], [14 x %struct.foo3]* @bar12.g, i64 0, i64 %indvars.iv, i32 1
+  %1 = load i32, i32* %b, align 4, !tbaa !11
+  %b8 = getelementptr inbounds %struct.foo3, %struct.foo3* %f, i64 %indvars.iv, i32 1
+  store i32 %1, i32* %b8, align 4, !tbaa !11
+  %2 = load i32, i32* %a, align 4, !tbaa !9
+  %c = getelementptr inbounds %struct.foo3, %struct.foo3* %f, i64 %indvars.iv, i32 2
+  store i32 %2, i32* %c, align 4, !tbaa !12
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, 0
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar12(
+; CHECK-NOT: call void @llvm.memcpy.p0i8.p0i8.i64
+}
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar13(%struct.foo* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %b = getelementptr inbounds [14 x %struct.foo], [14 x %struct.foo]* @bar13.g, i64 0, i64 %indvars.iv, i32 1
+  %0 = load i32, i32* %b, align 4, !tbaa !8
+  %a = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 0
+  store i32 %0, i32* %a, align 4, !tbaa !1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 14
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar13(
+; CHECK-NOT: call void @llvm.memcpy.p0i8.p0i8.i64
+}
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar14(%struct.foo1* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %0 = sub nuw nsw i64 13, %indvars.iv
+  %a = getelementptr inbounds [14 x %struct.foo1], [14 x %struct.foo1]* @bar14.g, i64 0, i64 %0, i32 0
+  %1 = load i32, i32* %a, align 4, !tbaa !6
+  %a3 = getelementptr inbounds %struct.foo1, %struct.foo1* %f, i64 %indvars.iv, i32 0
+  store i32 %1, i32* %a3, align 4, !tbaa !6
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 14
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar14(
+; CHECK-NOT: call void @llvm.memcpy.p0i8.p0i8.i64
+}
+
+; Function Attrs: norecurse nounwind uwtable
+define void @bar15(%struct.foo* nocapture %f) local_unnamed_addr #2 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %0 = sub nuw nsw i64 13, %indvars.iv
+  %a = getelementptr inbounds [14 x %struct.foo], [14 x %struct.foo]* @bar15.g, i64 0, i64 %0, i32 0
+  %1 = load i32, i32* %a, align 8, !tbaa !1
+  %a4 = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %0, i32 0
+  store i32 %1, i32* %a4, align 4, !tbaa !1
+  %b = getelementptr inbounds [14 x %struct.foo], [14 x %struct.foo]* @bar15.g, i64 0, i64 %indvars.iv, i32 1
+  %2 = load i32, i32* %b, align 4, !tbaa !8
+  %b10 = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %0, i32 1
+  store i32 %2, i32* %b10, align 4, !tbaa !8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 14
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+; CHECK-LABEL: @bar15(
+; CHECK-NOT: call void @llvm.memcpy.p0i8.p0i8.i64
+}
+
+attributes #0 = { nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind }
+attributes #2 = { norecurse nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { nounwind }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 5.0.0 "}
+!1 = !{!2, !3, i64 0}
+!2 = !{!"foo", !3, i64 0, !3, i64 4}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C/C++ TBAA"}
+!6 = !{!7, !3, i64 0}
+!7 = !{!"foo1", !3, i64 0}
+!8 = !{!2, !3, i64 4}
+!9 = !{!10, !3, i64 0}
+!10 = !{!"foo3", !3, i64 0, !3, i64 4, !3, i64 8}
+!11 = !{!10, !3, i64 4}
+!12 = !{!10, !3, i64 8}