[loop-idiom] Support memcpy instructions for memmove-like loops

[zhuhan0]

Summary

Following https://reviews.llvm.org/D104464. In addition to load and store
instructions, also handle memcpy intrinsics in loop body. The constraints are
same as before (same base pointer, etc.).

Fixed the FIXME added in D104464, and added two more tests.

[yurai007]

@zhuhan0: Thanks for following up my memmove change! Actually there is analogous follow up but it didn't catch lot of attention: https://reviews.llvm.org/D107075.
Maybe you can reuse some parts of that change. I feel you could at least copy most unit tests from there for better coverage.
And last but not least - there is one ongoing small but important fix for https://reviews.llvm.org/D104464 which can be found here: https://reviews.llvm.org/D107964
It would be great if you and @hoy could take a look since your changes depends on it.

[yurai007]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1356

IIRC I think I had 'kind of' similar idea to use 4th mayLoopAccessLocation but since it seems expensive I ended up in 3 calls: https://reviews.llvm.org/D107075 I admit I didn't measure impact on compile time. Maybe it's not so bad.

[zhuhan0]

In D108353#2954114, @yurai007 wrote:

@zhuhan0: Thanks for following up my memmove change! Actually there is analogous follow up but it didn't catch lot of attention: https://reviews.llvm.org/D107075.
Maybe you can reuse some parts of that change. I feel you could at least copy most unit tests from there for better coverage.
And last but not least - there is one ongoing small but important fix for https://reviews.llvm.org/D104464 which can be found here: https://reviews.llvm.org/D107964
It would be great if you and @hoy could take a look since your changes depends on it.

Oops I didn't know you had a follow-up patch already! Is it really okay for me to copy your diff? I can also review your diff and land that. Which do you prefer?

[yurai007]

Oops I didn't know you had a follow-up patch already! Is it really okay for me to copy your diff? I can also review your diff and land that. Which do you prefer?

Well, it's up to you :) I don't have problem with abandoning https://reviews.llvm.org/D107075. But if you see there are benefits in (re)using it then go ahead.

[zhuhan0]

https://reviews.llvm.org/D107075 landed.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(
 
   // 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 the store is a memcpy instruction, we must check if it will write to
   // the load memory locations. So remove it from the ignored stores.
-  if (IsMemCpy)
+  if (IsMemCpy) {
     IgnoredInsts.erase(TheStore);
+    UseMemMove = false;
+  }
   if (mayLoopAccessLocation(LoadBasePtr, ModRefInfo::Mod, CurLoop, BECount,
                             StoreSizeSCEV, *AA, IgnoredInsts)) {
+    // If this is a memcpy instruction, and the only instruction accessing the
+    // load is the memcpy itself, we can transform it to memmove since memmove
+    // handles overlapping copy.
+    if (IsMemCpy) {
+      IgnoredInsts.insert(TheStore);
+      UseMemMove =
+          !mayLoopAccessLocation(LoadBasePtr, ModRefInfo::Mod, CurLoop, BECount,
+                                 StoreSizeSCEV, *AA, IgnoredInsts);
+    }
+    if (!IsMemCpy || !UseMemMove) {
       ORE.emit([&]() {
-      return OptimizationRemarkMissed(DEBUG_TYPE, "LoopMayAccessLoad", TheLoad)
+        return OptimizationRemarkMissed(DEBUG_TYPE, "LoopMayAccessLoad",
+                                        TheLoad)
                << ore::NV("Inst", InstRemark) << " in "
                << ore::NV("Function", TheStore->getFunction())
                << " function will not be hoisted: "
                << ore::NV("Reason", "The loop may access load location");
       });
       return Changed;
     }
+  }
   if (UseMemMove) {
     // Ensure that LoadBasePtr is after StoreBasePtr or before StoreBasePtr for
     // negative stride. LoadBasePtr shouldn't overlap with StoreBasePtr.
     int64_t LoadOff = 0, StoreOff = 0;
     const Value *BP1 = llvm::GetPointerBaseWithConstantOffset(
         LoadBasePtr->stripPointerCasts(), LoadOff, *DL);
     const Value *BP2 = llvm::GetPointerBaseWithConstantOffset(
         StoreBasePtr->stripPointerCasts(), StoreOff, *DL);
     int64_t LoadSize =
-        DL->getTypeSizeInBits(TheLoad->getType()).getFixedSize() / 8;
+        IsMemCpy ? StoreSize
+                 : DL->getTypeSizeInBits(TheLoad->getType()).getFixedSize() / 8;
     if (BP1 != BP2 || LoadSize != int64_t(StoreSize))
       return Changed;
     if ((!IsNegStride && LoadOff < StoreOff + int64_t(StoreSize)) ||
         (IsNegStride && LoadOff + LoadSize > StoreOff))
       return Changed;
   }
 
   if (avoidLIRForMultiBlockLoop())

llvm/test/Transforms/LoopIdiom/basic.ll

while.body:
   br i1 %cmp, label %exit, label %while.body
 
 exit:
   ret void
 }
 
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture writeonly, i8* noalias nocapture readonly, i64, i1 immarg)
 
-;; FIXME: Do not form memmove from loop body containing memcpy.
-define void @do_not_form_memmove4(i8* %Src, i64 %Size) {
-; CHECK-LABEL: @do_not_form_memmove4(
+define void @memcpy_to_memmove(i8* %Src, i64 %Size) {
+; CHECK-LABEL: @memcpy_to_memmove(
 ; CHECK-NEXT:  bb.nph:
+; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, i8* [[SRC:%.*]], i64 1
+; CHECK-NEXT:    call void @llvm.memmove.p0i8.p0i8.i64(i8* align 1 [[SRC]], i8* align 1 [[SCEVGEP]], i64 [[SIZE:%.*]], i1 false)
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[STEP:%.*]] = add nuw nsw i64 [[INDVAR]], 1
 ; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr i8, i8* [[SRC]], i64 [[STEP]]
 ; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i8, i8* [[SRC]], i64 [[INDVAR]]
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 1 [[DESTI]], i8* align 1 [[SRCI]], i64 1, i1 false)
 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE:%.*]]
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 bb.nph:
   br label %for.body
 
 for.body:                                         ; preds = %bb.nph, %for.body
   %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
   %Step = add nuw nsw i64 %indvar, 1
   %SrcI = getelementptr i8, i8* %Src, i64 %Step
   %DestI = getelementptr i8, i8* %Src, i64 %indvar
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 1 %DestI, i8* align 1 %SrcI, i64 1, i1 false)
   %indvar.next = add i64 %indvar, 1
   %exitcond = icmp eq i64 %indvar.next, %Size
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
+;; Do not form memmove when loop writes to load location
+define void @do_not_form_memmove4(i8* %Src, i64 %Size) {
+; CHECK-LABEL: @do_not_form_memmove4(
+; CHECK-NEXT:  bb.nph:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ], [ 0, [[BB_NPH:%.*]] ]
+; CHECK-NEXT:    [[STEP:%.*]] = add nuw nsw i64 [[INDVAR]], 1
+; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr i8, i8* [[SRC:%.*]], i64 [[STEP]]
+; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr i8, i8* [[SRC]], i64 [[INDVAR]]
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 1 [[DESTI]], i8* align 1 [[SRCI]], i64 1, i1 false)
+; CHECK-NEXT:    [[MOD:%.*]] = load i8, i8* [[SRCI]], align 1
+; CHECK-NEXT:    [[INC:%.*]] = add i8 [[MOD]], 1
+; CHECK-NEXT:    store i8 [[INC]], i8* [[SRCI]], align 1
+; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE:%.*]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+bb.nph:
+  br label %for.body
+
+for.body:                                         ; preds = %bb.nph, %for.body
+  %indvar = phi i64 [ %indvar.next, %for.body ], [ 0, %bb.nph ]
+  %Step = add nuw nsw i64 %indvar, 1
+  %SrcI = getelementptr i8, i8* %Src, i64 %Step
+  %DestI = getelementptr i8, i8* %Src, i64 %indvar
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 1 %DestI, i8* align 1 %SrcI, i64 1, i1 false)
+  %Mod = load i8, i8* %SrcI, align 1
+  %inc = add i8 %Mod, 1
+  store i8 %inc, i8* %SrcI, align 1
+  %indvar.next = add i64 %indvar, 1
+  %exitcond = icmp eq i64 %indvar.next, %Size
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
 ;; Memcpy formation is still preferred over memmove.
 define void @prefer_memcpy_over_memmove(i8* noalias %Src, i8* noalias %Dest, i64 %Size) {
 ; CHECK-LABEL: @prefer_memcpy_over_memmove(
 ; CHECK-NEXT:  bb.nph:
 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, i8* [[SRC:%.*]], i64 42
 ; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 1 [[DEST:%.*]], i8* align 1 [[SCEVGEP]], i64 [[SIZE:%.*]], i1 false)
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:

llvm/test/Transforms/LoopIdiom/memcpy-intrinsic.ll

for.body:                                         ; preds = %for.body.preheader, %for.body
   %0 = bitcast %struct.SAligned* %arrayidx2 to i8*
   %1 = bitcast %struct.SAligned* %arrayidx to i8*
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 16 dereferenceable(16) %0, i8* nonnull align 16 dereferenceable(16) %1, i64 16, i1 false)
   %inc = add nuw nsw i32 %i.08, 1
   %cmp = icmp slt i32 %inc, %n
   br i1 %cmp, label %for.body, label %for.cond.cleanup.loopexit
 }
 
+;; A memmove-like loop with memcpys in loop body
+define void @to_memmove(%struct.S* %Src, i64 %Size) {
+; CHECK-LABEL: @to_memmove(
+; CHECK-NEXT:  bb.nph:
+; CHECK-NEXT:    [[SRC1:%.*]] = bitcast %struct.S* [[SRC:%.*]] to i8*
+; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr [[STRUCT_S:%.*]], %struct.S* [[SRC]], i64 1
+; CHECK-NEXT:    [[SCEVGEP2:%.*]] = bitcast %struct.S* [[SCEVGEP]] to i8*
+; CHECK-NEXT:    [[TMP0:%.*]] = mul nuw i64 [[SIZE:%.*]], 12
+; CHECK-NEXT:    call void @llvm.memmove.p0i8.p0i8.i64(i8* align 4 [[SRC1]], i8* align 4 [[SCEVGEP2]], i64 [[TMP0]], i1 false)
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[BB_NPH:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[STEP:%.*]] = add nuw nsw i64 [[INDVAR]], 1
+; CHECK-NEXT:    [[SRCI:%.*]] = getelementptr [[STRUCT_S]], %struct.S* [[SRC]], i64 [[STEP]]
+; CHECK-NEXT:    [[DESTI:%.*]] = getelementptr [[STRUCT_S]], %struct.S* [[SRC]], i64 [[INDVAR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast %struct.S* [[DESTI]] to i8*
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast %struct.S* [[SRCI]] to i8*
+; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], [[SIZE]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+bb.nph:
+  br label %for.body
+
+for.body:                                         ; preds = %bb.nph, %for.body
+  %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.body ]
+  %Step = add nuw nsw i64 %indvar, 1
+  %SrcI = getelementptr %struct.S, %struct.S* %Src, i64 %Step
+  %DestI = getelementptr %struct.S, %struct.S* %Src, i64 %indvar
+  %0 = bitcast %struct.S* %DestI to i8*
+  %1 = bitcast %struct.S* %SrcI to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 %0, i8* align 4 %1, i64 12, i1 false)
+  %indvar.next = add i64 %indvar, 1
+  %exitcond = icmp eq i64 %indvar.next, %Size
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
 ; Function Attrs: argmemonly nofree nosync nounwind willreturn
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture writeonly, i8* noalias nocapture readonly, i64, i1 immarg) #1