[LoopIdiom] memmove() on aliased pointers

[baziotis]

Summary

When trying to recognize memcpy(), if the store is aliased only by the load, then we can use memmove().

Note: Just yesterday I opened LoopIdiom pass for the first time, so I'm not super familiar. Definitely I want to check the tests
again and maybe add one or two.

[baziotis]

Ping. :)

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

bool LoopIdiomRecognize::processLoopMemSet(MemSetInst *MSI,
   SmallPtrSet<Instruction *, 1> MSIs;
   MSIs.insert(MSI);
   bool NegStride = SizeInBytes == -Stride;
   return processLoopStridedStore(
       Pointer, (unsigned)SizeInBytes, MaybeAlign(MSI->getDestAlignment()),
       SplatValue, MSI, MSIs, Ev, BECount, NegStride, /*IsLoopMemset=*/true);
 }
 
-/// mayLoopAccessLocation - Return true if the specified loop might access the
-/// specified pointer location, which is a loop-strided access.  The 'Access'
-/// argument specifies what the verboten forms of access are (read or write).
-static bool
-mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L,
-                      const SCEV *BECount, unsigned StoreSize,
-                      AliasAnalysis &AA,
-                      SmallPtrSetImpl<Instruction *> &IgnoredStores) {
+enum class LoopAccessKind { IllegalAccess = 0, LegalConstrained, Legal };
+
+/// mayLoopAccessLocation - Return IllegalAccess if the specified loop might
+/// access the \p Ptr, which is a loop-strided access, from an instruction that
+/// is not \p II.  Otherwise, if it accesses it from \p II, it is a
+/// LegalConstrained is returned. Otherwise, if it accesses from no instruction,
+/// Legal is returned. \p Access specifies what the verboten
+/// forms of access are (read or write).
+static LoopAccessKind mayLoopAccessLocation(
+    Value *Ptr, ModRefInfo Access, Loop *L, const SCEV *BECount,
+    unsigned StoreSize, AliasAnalysis &AA,
+    SmallPtrSetImpl<Instruction *> &IgnoredStores, Instruction *II = nullptr) {
   // Get the location that may be stored across the loop.  Since the access is
   // strided positively through memory, we say that the modified location starts
   // at the pointer and has infinite size.
   LocationSize AccessSize = LocationSize::unknown();
 
   // If the loop iterates a fixed number of times, we can refine the access size
   // to be exactly the size of the memset, which is (BECount+1)*StoreSize
   if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
     AccessSize = LocationSize::precise((BECst->getValue()->getZExtValue() + 1) *
                                        StoreSize);
 
   // TODO: For this to be really effective, we have to dive into the pointer
   // operand in the store.  Store to &A[i] of 100 will always return may alias
   // with store of &A[100], we need to StoreLoc to be "A" with size of 100,
   // which will then no-alias a store to &A[100].
   MemoryLocation StoreLoc(Ptr, AccessSize);
 
+  LoopAccessKind LoopAccess = LoopAccessKind::Legal;
   for (Loop::block_iterator BI = L->block_begin(), E = L->block_end(); BI != E;
        ++BI)
     for (Instruction &I : **BI)
       if (IgnoredStores.count(&I) == 0 &&
           isModOrRefSet(
-              intersectModRef(AA.getModRefInfo(&I, StoreLoc), Access)))
-        return true;
+              intersectModRef(AA.getModRefInfo(&I, StoreLoc), Access))) {
+        if (&I == II)
+          LoopAccess = LoopAccessKind::LegalConstrained;
+        else
+          return LoopAccessKind::IllegalAccess;
+      }
 
-  return false;
+  return LoopAccess;
 }
 
 // If we have a negative stride, Start refers to the end of the memory location
 // we're trying to memset.  Therefore, we need to recompute the base pointer,
 // which is just Start - BECount*Size.
 static const SCEV *getStartForNegStride(const SCEV *Start, const SCEV *BECount,
                                         Type *IntPtr, unsigned StoreSize,
                                         ScalarEvolution *SE) {
bool LoopIdiomRecognize::processLoopStridedStore(
 
   // Okay, we have a strided store "p[i]" of a splattable value.  We can turn
   // this into a memset 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 to the aliased location.  Check for any overlap by generating the
   // base pointer and checking the region.
   Value *BasePtr =
       Expander.expandCodeFor(Start, DestInt8PtrTy, Preheader->getTerminator());
-  if (mayLoopAccessLocation(BasePtr, ModRefInfo::ModRef, CurLoop, BECount,
-                            StoreSize, *AA, Stores)) {
+  auto LoopAccess = mayLoopAccessLocation(BasePtr, ModRefInfo::ModRef, CurLoop,
+                                          BECount, StoreSize, *AA, Stores);
+  if (LoopAccess == LoopAccessKind::IllegalAccess) {
     Expander.clear();
     // If we generated new code for the base pointer, clean up.
     RecursivelyDeleteTriviallyDeadInstructions(BasePtr, TLI);
     return false;
   }
 
   if (avoidLIRForMultiBlockLoop(/*IsMemset=*/true, IsLoopMemset))
     return false;
bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
   // 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, ModRefInfo::ModRef, CurLoop, BECount,
-                            StoreSize, *AA, Stores)) {
+  LoopAccessKind StoreLoopAccess =
+      mayLoopAccessLocation(StoreBasePtr, ModRefInfo::ModRef, CurLoop, BECount,
+                            StoreSize, *AA, Stores, LI);
+  if (StoreLoopAccess == LoopAccessKind::IllegalAccess) {
     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, IntIdxTy, StoreSize, SE);
 
   // 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, ModRefInfo::Mod, CurLoop, BECount,
-                            StoreSize, *AA, Stores)) {
+  LoopAccessKind LoadLoopAccess = mayLoopAccessLocation(
+      LoadBasePtr, ModRefInfo::Mod, CurLoop, BECount, StoreSize, *AA, Stores);
+  assert(
+      LoadLoopAccess != LoopAccessKind::LegalConstrained &&
+      "The load can never have constrained access because we don't "
+      "pass any argument that can only constrain it and not make it illegal");
+  if (LoadLoopAccess == LoopAccessKind::IllegalAccess) {
     Expander.clear();
     // If we generated new code for the base pointer, clean up.
     RecursivelyDeleteTriviallyDeadInstructions(LoadBasePtr, TLI);
     RecursivelyDeleteTriviallyDeadInstructions(StoreBasePtr, TLI);
     return false;
   }
 
   if (avoidLIRForMultiBlockLoop())
     return false;
 
   // Okay, everything is safe, we can transform this!
 
   const SCEV *NumBytesS =
       getNumBytes(BECount, IntIdxTy, StoreSize, CurLoop, DL, SE);
 
   Value *NumBytes =
       Expander.expandCodeFor(NumBytesS, IntIdxTy, Preheader->getTerminator());
 
   CallInst *NewCall = nullptr;
   // Check whether to generate an unordered atomic memcpy:
   //  If the load or store are atomic, then they must necessarily be unordered
   //  by previous checks.
-  if (!SI->isAtomic() && !LI->isAtomic())
+  if (!SI->isAtomic() && !LI->isAtomic()) {
+    if (StoreLoopAccess == LoopAccessKind::Legal) {
       NewCall = Builder.CreateMemCpy(StoreBasePtr, SI->getAlign(), LoadBasePtr,
                                      LI->getAlign(), NumBytes);
-  else {
+    } else {
+      assert(StoreLoopAccess == LoopAccessKind::LegalConstrained &&
+             "We must have constrained access to insert a memmove");
+      NewCall = Builder.CreateMemMove(StoreBasePtr, SI->getAlign(), LoadBasePtr,
+                                      LI->getAlign(), NumBytes);
+    }
+  } else {
     // We cannot allow unaligned ops for unordered load/store, so reject
     // anything where the alignment isn't at least the element size.
     const MaybeAlign StoreAlign = SI->getAlign();
     const MaybeAlign LoadAlign = LI->getAlign();
     if (StoreAlign == None || LoadAlign == None)
       return false;
     if (*StoreAlign < StoreSize || *LoadAlign < StoreSize)
       return false;
 
-    // If the element.atomic memcpy is not lowered into explicit
+    // If the element.atomic memcpy / memmove 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.
+    if (StoreLoopAccess == LoopAccessKind::Legal) {
       NewCall = Builder.CreateElementUnorderedAtomicMemCpy(
           StoreBasePtr, *StoreAlign, LoadBasePtr, *LoadAlign, NumBytes,
           StoreSize);
+    } else {
+      assert(StoreLoopAccess == LoopAccessKind::LegalConstrained &&
+             "We must have constrained access to insert a memmove");
+      NewCall = Builder.CreateElementUnorderedAtomicMemMove(
+          StoreBasePtr, *StoreAlign, LoadBasePtr, *LoadAlign, NumBytes,
+          StoreSize);
+    }
   }
   NewCall->setDebugLoc(SI->getDebugLoc());
 
   if (MSSAU) {
     MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
         NewCall, nullptr, NewCall->getParent(), MemorySSA::BeforeTerminator);
     MSSAU->insertDef(cast<MemoryDef>(NewMemAcc), true);
   }

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

for.body:                                         ; preds = %entry, %for.body
   %exitcond = icmp eq i64 %indvar.next, 10000
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }
 
 ; PR9815 - This is a partial overlap case that cannot be safely transformed
-; into a memcpy.
+; into a memcpy. It should be transformed to memmove
 @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: memmove
 ; CHECK: for.body:
 ; CHECK: load i32
-; CHECK: store i32
 ; 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

llvm/test/Transforms/LoopIdiom/basic.ll

 ; CHECK-NEXT: memset_pattern
 ; CHECK-NOT: store
 ; CHECK: ret void
 }
 
 
 
 ; PR9815 - This is a partial overlap case that cannot be safely transformed
-; into a memcpy.
+; into a memcpy. It should be transformed to memmove.
 @g_50 = global [7 x i32] [i32 0, i32 0, i32 0, i32 0, i32 1, i32 0, i32 0], align 16
 
 define i32 @test14() nounwind {
 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
   %idxprom = sext i32 %add to i64
   %arrayidx = getelementptr inbounds [7 x i32], [7 x i32]* @g_50, i32 0, i64 %idxprom
   %tmp2 = load i32, i32* %arrayidx, align 4
   %add4 = add nsw i32 %tmp5, 5
   %idxprom5 = sext i32 %add4 to i64
   %arrayidx6 = getelementptr inbounds [7 x i32], [7 x i32]* @g_50, i32 0, i64 %idxprom5
   store i32 %tmp2, i32* %arrayidx6, align 4
   %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: memmove
 ; CHECK: for.body:
 ; CHECK: load i32
-; CHECK: store i32
 ; 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.
 ;
 ; 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: memmove
 
 while.body:
   %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
   %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
 
 exit:
   ret void
 ; CHECK: ret void
 }

llvm/test/Transforms/LoopIdiom/pr28196.ll

for.body:                                         ; preds = %for.body, %for.body.preheader
   store i32 %0, i32* %add.ptr3, align 4
   %indvars.iv.next = add nsw i32 %indvars.iv, 1
   %exitcond = icmp ne i32 %indvars.iv.next, 6
   br i1 %exitcond, label %for.body, label %for.body.preheader
 }
 
 ; CHECK-LABEL: define void @test1_no_null_opt(
 ; CHECK-NOT: call void @llvm.memcpy
+; CHECK: call void @llvm.memmove
 ; CHECK: getelementptr
 ; CHECK: getelementptr
 ; CHECK: load
-; CHECK: store
 
 attributes #0 = { "null-pointer-is-valid"="true" }