[LoopIdiomRecognize] Add support for memmove. Fixes PR25165

[EricWF]

Summary

This patch adds support for memmove formation to LoopIdiomRecognize.cpp, which fixes llvm.org/PR25165.

The following loops now optimize to a memmove.

void copy(int *begin, int *end, int *out) {
  for (; begin != end; ++begin, ++out)
    *out = *begin;
}

void copy2(int *dest, int *source, int size) {
  for (int i=0; i < size; ++i)
    dest[i] = source[i];
}

void copy3(int *arr) {
  for (int i=0; i < 1023; ++i)
    arr[i] = arr[i+1];
}

[EricWF]

• Add more tests.

[chandlerc]

Some quick comments on the code etc., want to think a bit harder about the loop access checks just to make sure I'm not missing anything. Ben may also have thoughts there.

lib/IR/IRBuilder.cpp

169–186

Maybe factor this out and share it between MemCpy and MemMove?

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

484

Why the check for HasMemcpy here? Seems a bit odd to check it here rather than later....

1056–1057

Maybe leave a FIXME that we should build an atomic memmove lowering much like we did for memcpy that has specified element-width operations....

[EricWF]

lib/IR/IRBuilder.cpp

169–186

Actually, I made a dumb mistake, and missed the already existing CreateMemMove function. I'll be removing this entirely.

Perhaps it still makes sense to factor out the shared code, but that should be a separate commit.

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

484

We checked HasMemcpy || HasMemmove at the top of this block, so it's possible (but unlikely) that we only have memmove. Since we don't have any way to lower the atomic store, it seems logical to report LegalStoreKind::None right away.

[EricWF]

• Address inline comments.
• Remove duplicate CreateMemmove function in IrBuilder.h.

[EricWF]

@chandlerc All of your review comments have been better addressed in the follow up commit D42890, which adds support for atomic memmove's ,

[EricWF]

• Avoid unnecessary calculation of non-modifying memory references if we already have already found a modifying memory reference.

[EricWF]

Upload the correct patch for avoiding unnecessary calculation of non-modifying memory references when we already have already found a modifying memory reference.

[EricWF]

Fix silly logic bug in last update. Sorry for the spam.

[efriedma]

This transform isn't legal. Consider:

#include <assert.h>
void not_memmove(int *x, int *y, int n) {
  for (int i = 0; i < n; ++i)
    x[i] = y[i];
}
int main() {
  int x[] = { 1, 2, 3, 4, 5, 6 };
  not_memmove(&x[1], &x[0], 5);
  for (int i = 0; i < 6; ++i)
    assert(x[i] == 1);
}

[EricWF]

In D42889#998260, @efriedma wrote:

This transform isn't legal. Consider:

#include <assert.h>
void not_memmove(int *x, int *y, int n) {
  for (int i = 0; i < n; ++i)
    x[i] = y[i];
}

Woops. Thanks for the correction. I'll attempt to clean this up.

include/llvm/IR/IRBuilder.h

CallInst *CreateMemCpy(Value *Dst, Value *Src, Value *Size, unsigned Align,
                          bool isVolatile = false, MDNode *TBAATag = nullptr,
                          MDNode *TBAAStructTag = nullptr,
                          MDNode *ScopeTag = nullptr,
                          MDNode *NoAliasTag = nullptr) {
     return CreateMemCpy(Dst, Align, Src, Align, Size, isVolatile, TBAATag,
                         TBAAStructTag, ScopeTag, NoAliasTag);
   }
 
+  /// \brief Create and insert a memmove between the specified pointers.
+  ///
+  /// If the pointers aren't i8*, they will be converted.  If a TBAA tag is
+  /// specified, it will be added to the instruction. Likewise with alias.scope
+  /// and noalias tags.
+  CallInst *CreateMemmove(Value *Dst, unsigned DstAlign, Value *Src,
+                          unsigned SrcAlign, uint64_t Size,
+                          bool isVolatile = false, MDNode *TBAATag = nullptr,
+                          MDNode *TBAAStructTag = nullptr,
+                          MDNode *ScopeTag = nullptr,
+                          MDNode *NoAliasTag = nullptr) {
+    return CreateMemmove(Dst, DstAlign, Src, SrcAlign, getInt64(Size),
+                         isVolatile, TBAATag, TBAAStructTag, ScopeTag,
+                         NoAliasTag);
+  }
+
+  CallInst *CreateMemmove(Value *Dst, unsigned DstAlign, Value *Src,
+                          unsigned SrcAlign, Value *Size,
+                          bool isVolatile = false, MDNode *TBAATag = nullptr,
+                          MDNode *TBAAStructTag = nullptr,
+                          MDNode *ScopeTag = nullptr,
+                          MDNode *NoAliasTag = nullptr);
+
   /// \brief Create and insert an element unordered-atomic memcpy between the
   /// specified pointers.
   ///
   /// DstAlign/SrcAlign are the alignments of the Dst/Src pointers, respectively.
   ///
   /// If the pointers aren't i8*, they will be converted.  If a TBAA tag is
   /// specified, it will be added to the instruction. Likewise with alias.scope
   /// and noalias tags.

lib/IR/IRBuilder.cpp

CreateMemCpy(Value *Dst, unsigned DstAlign, Value *Src, unsigned SrcAlign,
   assert((SrcAlign == 0 || isPowerOf2_32(SrcAlign)) && "Must be 0 or a power of 2");
   Dst = getCastedInt8PtrValue(Dst);
   Src = getCastedInt8PtrValue(Src);
 
   Value *Ops[] = {Dst, Src, Size, getInt1(isVolatile)};
   Type *Tys[] = { Dst->getType(), Src->getType(), Size->getType() };
   Module *M = BB->getParent()->getParent();
   Value *TheFn = Intrinsic::getDeclaration(M, Intrinsic::memcpy, Tys);
-  
   CallInst *CI = createCallHelper(TheFn, Ops, this);
 
   auto* MCI = cast<MemCpyInst>(CI);
   if (DstAlign > 0)
     MCI->setDestAlignment(DstAlign);
   if (SrcAlign > 0)
     MCI->setSourceAlignment(SrcAlign);
 
   // Set the TBAA info if present.
   if (TBAATag)
     CI->setMetadata(LLVMContext::MD_tbaa, TBAATag);
 
   // Set the TBAA Struct info if present.
   if (TBAAStructTag)
     CI->setMetadata(LLVMContext::MD_tbaa_struct, TBAAStructTag);
- 
   if (ScopeTag)
     CI->setMetadata(LLVMContext::MD_alias_scope, ScopeTag);
- 
   if (NoAliasTag)
     CI->setMetadata(LLVMContext::MD_noalias, NoAliasTag);
 
-  return CI;  
+  return CI;
 }
 
+CallInst *IRBuilderBase::CreateMemmove(Value *Dst, unsigned DstAlign,
+                                       Value *Src, unsigned SrcAlign,
+                                       Value *Size, bool isVolatile,
+                                       MDNode *TBAATag, MDNode *TBAAStructTag,
+                                       MDNode *ScopeTag, MDNode *NoAliasTag) {
+  assert((DstAlign == 0 || isPowerOf2_32(DstAlign)) &&
+         "Must be 0 or a power of 2");
+  assert((SrcAlign == 0 || isPowerOf2_32(SrcAlign)) &&
+         "Must be 0 or a power of 2");
+  Dst = getCastedInt8PtrValue(Dst);
+  Src = getCastedInt8PtrValue(Src);
+
+  Value *Ops[] = {Dst, Src, Size, getInt1(isVolatile)};
+  Type *Tys[] = {Dst->getType(), Src->getType(), Size->getType()};
+  Module *M = BB->getParent()->getParent();
+  Value *TheFn = Intrinsic::getDeclaration(M, Intrinsic::memmove, Tys);
+
+  CallInst *CI = createCallHelper(TheFn, Ops, this);
+
+  auto *MCI = cast<MemMoveInst>(CI);
+  if (DstAlign > 0)
+    MCI->setDestAlignment(DstAlign);
+  if (SrcAlign > 0)
+    MCI->setSourceAlignment(SrcAlign);
+
+  // Set the TBAA info if present.
+  if (TBAATag)
+    CI->setMetadata(LLVMContext::MD_tbaa, TBAATag);
+
+  // Set the TBAA Struct info if present.
+  if (TBAAStructTag)
+    CI->setMetadata(LLVMContext::MD_tbaa_struct, TBAAStructTag);
+
+  if (ScopeTag)
+    CI->setMetadata(LLVMContext::MD_alias_scope, ScopeTag);
+
+  if (NoAliasTag)
+    CI->setMetadata(LLVMContext::MD_noalias, NoAliasTag);
+
+  return CI;
+}
+
 CallInst *IRBuilderBase::CreateElementUnorderedAtomicMemCpy(
     Value *Dst, unsigned DstAlign, Value *Src, unsigned SrcAlign, Value *Size,
     uint32_t ElementSize, MDNode *TBAATag, MDNode *TBAAStructTag,
     MDNode *ScopeTag, MDNode *NoAliasTag) {
   assert(DstAlign >= ElementSize &&
          "Pointer alignment must be at least element size");
   assert(SrcAlign >= ElementSize &&
          "Pointer alignment must be at least element size");

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-idiom"
 
 STATISTIC(NumMemSet, "Number of memset's formed from loop stores");
 STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores");
+STATISTIC(NumMemMove, "Number of memmove's formed from loop load+stores");
 
 static cl::opt<bool> UseLIRCodeSizeHeurs(
     "use-lir-code-size-heurs",
     cl::desc("Use loop idiom recognition code size heuristics when compiling"
              "with -Os/-Oz"),
     cl::init(true), cl::Hidden);
 
 namespace {
public:
   bool runOnLoop(Loop *L);
 
 private:
   using StoreList = SmallVector<StoreInst *, 8>;
   using StoreListMap = MapVector<Value *, StoreList>;
 
   StoreListMap StoreRefsForMemset;
   StoreListMap StoreRefsForMemsetPattern;
-  StoreList StoreRefsForMemcpy;
+  StoreList StoreRefsForMemcpyOrMemmove;
   bool HasMemset;
   bool HasMemsetPattern;
   bool HasMemcpy;
+  bool HasMemmove;
 
   /// Return code for isLegalStore()
   enum LegalStoreKind {
     None = 0,
     Memset,
     MemsetPattern,
-    Memcpy,
+    MemcpyOrMemmove,
     UnorderedAtomicMemcpy,
     DontUse // Dummy retval never to be used. Allows catching errors in retval
             // handling.
   };
 
   /// \name Countable Loop Idiom Handling
   /// @{
 
bool LoopIdiomRecognize::runOnLoop(Loop *L) {
   CurLoop = L;
   // If the loop could not be converted to canonical form, it must have an
   // indirectbr in it, just give up.
   if (!L->getLoopPreheader())
     return false;
 
   // Disable loop idiom recognition if the function's name is a common idiom.
   StringRef Name = L->getHeader()->getParent()->getName();
-  if (Name == "memset" || Name == "memcpy")
+  if (Name == "memset" || Name == "memcpy" || Name == "memmove")
     return false;
 
   // Determine if code size heuristics need to be applied.
   ApplyCodeSizeHeuristics =
       L->getHeader()->getParent()->optForSize() && UseLIRCodeSizeHeurs;
 
   HasMemset = TLI->has(LibFunc_memset);
   HasMemsetPattern = TLI->has(LibFunc_memset_pattern16);
   HasMemcpy = TLI->has(LibFunc_memcpy);
+  HasMemmove = TLI->has(LibFunc_memmove);
 
-  if (HasMemset || HasMemsetPattern || HasMemcpy)
+  if (HasMemset || HasMemsetPattern || HasMemcpy || HasMemmove)
     if (SE->hasLoopInvariantBackedgeTakenCount(L))
       return runOnCountableLoop();
 
   return runOnNoncountableLoop();
 }
 
 bool LoopIdiomRecognize::runOnCountableLoop() {
   const SCEV *BECount = SE->getBackedgeTakenCount(CurLoop);
LoopIdiomRecognize::isLegalStore(StoreInst *SI) {
   } else if (!UnorderedAtomic && HasMemsetPattern &&
              // Don't create memset_pattern16s with address spaces.
              StorePtr->getType()->getPointerAddressSpace() == 0 &&
              (PatternValue = getMemSetPatternValue(StoredVal, DL))) {
     // It looks like we can use PatternValue!
     return LegalStoreKind::MemsetPattern;
   }
 
-  // Otherwise, see if the store can be turned into a memcpy.
-  if (HasMemcpy) {
+  // Otherwise, see if the store can be turned into a memcpy or memmove.
+  if (HasMemcpy || HasMemmove) {
     // 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 = DL->getTypeStoreSize(SI->getValueOperand()->getType());
     if (StoreSize != Stride && StoreSize != -Stride)
       return LegalStoreKind::None;
 
     // The store must be feeding a non-volatile load.
const SCEVAddRecExpr *LoadEv =
         dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LI->getPointerOperand()));
     if (!LoadEv || LoadEv->getLoop() != CurLoop || !LoadEv->isAffine())
       return LegalStoreKind::None;
 
     // 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;
+    if (UnorderedAtomic || LI->isAtomic())
+      return HasMemcpy ? LegalStoreKind::UnorderedAtomicMemcpy
+                       : LegalStoreKind::None;
+
+    // Success.  This store can be converted into a memcpy or memmove.
+    return LegalStoreKind::MemcpyOrMemmove;
   }
   // This store can't be transformed into a memset/memcpy.
   return LegalStoreKind::None;
 }
 
 void LoopIdiomRecognize::collectStores(BasicBlock *BB) {
   StoreRefsForMemset.clear();
   StoreRefsForMemsetPattern.clear();
-  StoreRefsForMemcpy.clear();
+  StoreRefsForMemcpyOrMemmove.clear();
   for (Instruction &I : *BB) {
     StoreInst *SI = dyn_cast<StoreInst>(&I);
     if (!SI)
       continue;
 
     // Make sure this is a strided store with a constant stride.
     switch (isLegalStore(SI)) {
     case LegalStoreKind::None:
       // Nothing to do
       break;
     case LegalStoreKind::Memset: {
       // Find the base pointer.
       Value *Ptr = GetUnderlyingObject(SI->getPointerOperand(), *DL);
       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::MemcpyOrMemmove:
     case LegalStoreKind::UnorderedAtomicMemcpy:
-      StoreRefsForMemcpy.push_back(SI);
+      StoreRefsForMemcpyOrMemmove.push_back(SI);
       break;
     default:
       assert(false && "unhandled return value");
       break;
     }
   }
 }
 
bool LoopIdiomRecognize::runOnLoopBlock(
   // 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)
+  for (auto &SI : StoreRefsForMemcpyOrMemmove)
     MadeChange |= processLoopStoreOfLoopLoad(SI, 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))
bool LoopIdiomRecognize::processLoopStridedStore(
   // 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
-/// for (i) A[i] = B[i];
+/// this may be transformable into a memcpy or memmove.  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.");
 
   Value *StorePtr = SI->getPointerOperand();
   const SCEVAddRecExpr *StoreEv = cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
   APInt Stride = getStoreStride(StoreEv);
   unsigned StoreSize = DL->getTypeStoreSize(SI->getValueOperand()->getType());
bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
   if (NegStride)
     StrStart = getStartForNegStride(StrStart, BECount, IntPtrTy, StoreSize, SE);
 
   // 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.
+  // checking everything.  If the access is only a load, then perform a memmove
+  // instead of a memcpy.
   Value *StoreBasePtr = Expander.expandCodeFor(
       StrStart, Builder.getInt8PtrTy(StrAS), Preheader->getTerminator());
 
   SmallPtrSet<Instruction *, 1> Stores;
   Stores.insert(SI);
-  if (mayLoopAccessLocation(StoreBasePtr, ModRefInfo::ModRef, CurLoop, BECount,
-                            StoreSize, *AA, Stores)) {
+  bool StoreIsModified = mayLoopAccessLocation(
+      StoreBasePtr, ModRefInfo::Mod, CurLoop, BECount, StoreSize, *AA, Stores);
+  bool PerformMemmove = mayLoopAccessLocation(
+      StoreBasePtr, ModRefInfo::Ref, CurLoop, BECount, StoreSize, *AA, Stores);
+
+  if (StoreIsModified || (PerformMemmove && !HasMemmove)) {
     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();
 
   // Handle negative strided loops.
   if (NegStride)
     LdStart = getStartForNegStride(LdStart, BECount, IntPtrTy, StoreSize, SE);
 
-  // For a memcpy, we have to make sure that the input array is not being
-  // mutated by the loop.
+  // For a memcpy or memmove, 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, ModRefInfo::Mod, CurLoop, BECount,
                             StoreSize, *AA, Stores)) {
     Expander.clear();
     // If we generated new code for the base pointer, clean up.
     RecursivelyDeleteTriviallyDeadInstructions(LoadBasePtr, TLI);
const SCEV *NumBytesS =
       getNumBytes(BECount, IntPtrTy, StoreSize, CurLoop, DL, SE);
 
   Value *NumBytes =
       Expander.expandCodeFor(NumBytesS, IntPtrTy, Preheader->getTerminator());
 
   unsigned Align = std::min(SI->getAlignment(), LI->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
+  //  If the load or store are atomic, then they must necessarily be unordered
   //  by previous checks.
-  if (!SI->isAtomic() && !LI->isAtomic())
+  bool IsAtomicLoadOrStore = SI->isAtomic() || LI->isAtomic();
+  assert((!IsAtomicLoadOrStore || !PerformMemmove) &&
+         "cannot memmove atomic load or store");
+
+  if (PerformMemmove)
+    NewCall = Builder.CreateMemmove(StoreBasePtr, Align, LoadBasePtr, Align,
+                                    NumBytes);
+  else if (!IsAtomicLoadOrStore)
     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;
 
     // Create the call.
     // Note that unordered atomic loads/stores are *required* by the spec to
     // have an alignment but non-atomic loads/stores may not.
     NewCall = Builder.CreateElementUnorderedAtomicMemCpy(
         StoreBasePtr, SI->getAlignment(), LoadBasePtr, LI->getAlignment(),
         NumBytes, StoreSize);
   }
   NewCall->setDebugLoc(SI->getDebugLoc());
 
-  DEBUG(dbgs() << "  Formed memcpy: " << *NewCall << "\n"
+
+  DEBUG(dbgs() << "  Formed " << (PerformMemmove ? "memmove: " : "memcpy: ")
+               << *NewCall << "\n"
                << "    from load ptr=" << *LoadEv << " at: " << *LI << "\n"
                << "    from store ptr=" << *StoreEv << " at: " << *SI << "\n");
 
-  // Okay, the memcpy has been formed.  Zap the original store and anything that
-  // feeds into it.
+  // Okay, the memcpy or memmove has been formed.  Zap the original store and
+  // anything that feeds into it.
   deleteDeadInstruction(SI);
+  if (PerformMemmove)
+    ++NumMemMove;
+  else
     ++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) {

test/Transforms/LoopIdiom/basic-address-space.ll

 
 ; PR9815 - This is a partial overlap case that cannot be safely transformed
 ; into a memcpy.
 @g_50 = addrspace(2) global [7 x i32] [i32 0, i32 0, i32 0, i32 0, i32 1, i32 0, i32 0], align 16
 
 
 define i32 @test14() nounwind {
 ; CHECK-LABEL: @test14(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: call void @llvm.memmove.p2i8.p2i8.i16
 ; CHECK: for.body:
-; CHECK: load i32
-; CHECK: store i32
+; CHECK-NOT: store
 ; CHECK: br i1 %cmp
 
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.inc, %for.body.lr.ph
   %tmp5 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
   %add = add nsw i32 %tmp5, 4

test/Transforms/LoopIdiom/basic.ll

for.body:                                         ; preds = %for.inc, %for.body.lr.ph
   %inc = add nsw i32 %tmp5, 1
   %cmp = icmp slt i32 %inc, 2
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:                                          ; preds = %for.inc
   %tmp8 = load i32, i32* getelementptr inbounds ([7 x i32], [7 x i32]* @g_50, i32 0, i64 6), align 4
   ret i32 %tmp8
 ; CHECK-LABEL: @test14(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: call void @llvm.memmove.p0i8.p0i8.i64(i8* align 4 bitcast (i32* getelementptr inbounds ([7 x i32], [7 x i32]* @g_50, i64 0, i64 5) to i8*), i8* align 4 bitcast (i32* getelementptr inbounds ([7 x i32], [7 x i32]* @g_50, i64 0, i64 4) to i8*), i64 8, i1 false)
 ; CHECK: for.body:
-; CHECK: load i32
-; CHECK: store i32
+; CHECK-NOT: store
 ; CHECK: br i1 %cmp
 
 }
 
 define void @PR14241(i32* %s, i64 %size) {
 ; Ensure that we don't form a memcpy for strided loops. Briefly, when we taught
 ; LoopIdiom about memmove and strided loops, this got miscompiled into a memcpy
-; instead of a memmove. If we get the memmove transform back, this will catch
-; regressions.
+; instead of a memmove. We now have the memmove transform back. Ensure this
+; still doesn't generate a memcpy to catch regressions.
 ;
 ; CHECK-LABEL: @PR14241(
 
 entry:
   %end.idx = add i64 %size, -1
   %end.ptr = getelementptr inbounds i32, i32* %s, i64 %end.idx
   br label %while.body
 ; CHECK-NOT: memcpy
-;
-; FIXME: When we regain the ability to form a memmove here, this test should be
-; reversed and turned into a positive assertion.
-; CHECK-NOT: memmove
+; CHECK: call void @llvm.memmove.p0i8.p0i8.i64(i8* align 4 %s1, i8* align 4 %scevgep2, i64 %4, i1 false)
+; CHECK-NEXT: br label %while.body
+; CHECK-NOT: memcpy
+
 
 while.body:
+; CHECK: while.body:
+; CHECK-NOT: store
   %phi.ptr = phi i32* [ %s, %entry ], [ %next.ptr, %while.body ]
   %src.ptr = getelementptr inbounds i32, i32* %phi.ptr, i64 1
   %val = load i32, i32* %src.ptr, align 4
 ; CHECK: load
   %dst.ptr = getelementptr inbounds i32, i32* %phi.ptr, i64 0
   store i32 %val, i32* %dst.ptr, align 4
-; CHECK: store
+; CHECK-NOT: store
   %next.ptr = getelementptr inbounds i32, i32* %phi.ptr, i64 1
   %cmp = icmp eq i32* %next.ptr, %end.ptr
   br i1 %cmp, label %exit, label %while.body
 
+; CHECK: exit:
 exit:
   ret void
 ; CHECK: ret void
 }
 
 ; Recognize loops with a negative stride.
 define void @test15(i32* nocapture %f) {
 entry:

 
 loop.exit:
   br label %exit
 
 exit:
   ret void
 }
 
+; Memmove formation tests
+
+declare void @eat(i8 signext)
+
+define void @test_memmove_formation(i8* nocapture %dest, i8* nocapture readonly %source, i64 %size) nounwind ssp {
+entry:
+  %cmp8 = icmp sgt i64 %size, 0
+  br i1 %cmp8, label %for.body.preheader, label %for.end
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds i8, i8* %source, i64 %indvars.iv
+  %0 = load i8, i8* %arrayidx, align 1
+  %arrayidx3 = getelementptr inbounds i8, i8* %dest, i64 %indvars.iv
+  store i8 %0, i8* %arrayidx3, align 1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, %size
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                 ; preds = %for.body, %entry
+  ret void
+; CHECK-LABEL: @test_memmove_formation(
+; CHECK: @llvm.memmove.p0i8.p0i8.i64(i8* align 1 %dest, i8* align 1 %source, i64 %size, i1 false)
+; CHECK-NOT: store
+; CHECK: ret void
+}
+
+define void @test_memmove_two(i8* readonly %begin, i8* readnone %end, i8* nocapture %out) nounwind ssp {
+entry:
+  %cmp1 = icmp eq i8* %begin, %end
+  br i1 %cmp1, label %for.end, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %dest.i = phi i8* [ %dest.next, %for.body ], [ %out, %for.body.preheader ]
+  %begin.i = phi i8* [ %begin.next, %for.body ], [ %begin, %for.body.preheader ]
+  %0 = load i8, i8* %begin.i, align 1
+  store i8 %0, i8* %dest.i, align 1
+  %begin.next = getelementptr inbounds i8, i8* %begin.i, i64 1
+  %dest.next = getelementptr inbounds i8, i8* %dest.i, i64 1
+  %cmp = icmp eq i8* %begin.next, %end
+  br i1 %cmp, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+; CHECK-LABEL: @test_memmove_two(
+; CHECK: call void @llvm.memmove.p0i8.p0i8.i64(i8* align 1 %out, i8* align 1 %begin
+; CHECK-NOT: store
+; CHECK: ret void
+}
+
+
+; test memmove is not performed since the source array is accessed during the loop.
+define void @copy_access_source(i8* readonly %begin, i8* readonly %end, i8* nocapture %out) nounwind ssp {
+entry:
+  %add.ptr = getelementptr inbounds i8, i8* %end, i64 -1
+  %cmp7 = icmp eq i8* %begin, %end
+  br i1 %cmp7, label %for.end, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %begin.i = phi i8* [ %begin.next, %for.body ], [ %begin, %for.body.preheader ]
+  %dest.i = phi i8* [ %dest.next, %for.body ], [ %out, %for.body.preheader ]
+  %0 = load i8, i8* %begin.i, align 1
+  store i8 %0, i8* %dest.i, align 1
+  %1 = load i8, i8* %add.ptr, align 1
+  tail call void @eat(i8 signext %1)
+  %begin.next = getelementptr inbounds i8, i8* %begin.i, i64 1
+  %dest.next = getelementptr inbounds i8, i8* %dest.i, i64 1
+  %cmp = icmp eq i8* %begin.next, %end
+  br i1 %cmp, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+; CHECK-LABEL: @copy_access_source
+; CHECK-NOT: llvm.memmove
+; CHECK-NOT: llvm.memcpy
+; CHECK: ret void
+}
+
+; test memmove is not performed since the destination array is accessed during the loop.
+define void @copy_access_dest(i8* readonly %begin, i8* readnone %end, i8* nocapture %out) nounwind ssp {
+entry:
+  %add.ptr = getelementptr inbounds i8, i8* %out, i64 1
+  %cmp1 = icmp eq i8* %begin, %end
+  br i1 %cmp1, label %for.end, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %begin.i = phi i8* [ %begin.next, %for.body ], [ %begin, %for.body.preheader ]
+  %dest.i = phi i8* [ %dest.next, %for.body ], [ %out, %for.body.preheader ]
+  %0 = load i8, i8* %add.ptr, align 1
+  tail call void @eat(i8 signext %0) #3
+  %1 = load i8, i8* %begin.i, align 1
+  store i8 %1, i8* %dest.i, align 1
+  %begin.next = getelementptr inbounds i8, i8* %begin.i, i64 1
+  %dest.next = getelementptr inbounds i8, i8* %dest.i, i64 1
+  %cmp = icmp eq i8* %begin.next, %end
+  br i1 %cmp, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+; CHECK-LABEL: @copy_access_dest
+; CHECK-NOT: llvm.memmove
+; CHECK-NOT: llvm.memcpy
+; CHECK: ret void
+}
+
+
 ; Validate that "memset_pattern" has the proper attributes.
 ; CHECK: declare void @memset_pattern16(i8* nocapture, i8* nocapture readonly, i64) [[ATTRS:#[0-9]+]]
 ; CHECK: [[ATTRS]] = { argmemonly }