[LoopIdiom] Don't transform loop into memmove when load from body has more than one use

[yurai007]

Summary

This change fixes issue found by Markus: https://reviews.llvm.org/rG11338e998df1
Before this patch following code was transformed to memmove:

for (int i = 15; i >= 1; i--) {
  p[i] = p[i-1];
  sum += p[i-1];
}

However load from p[i-1] is used not only by store to p[i] but also by sum computation.
Therefore we cannot emit memmove in loop header.

[lebedev.ri]

The description doesn't actually describe the problem.
That being said, alive agrees this is a miscompile.
That being said, if load has extra uses,
can we retain the transform by querying AA that there's no overlap?

[xbolva00]

Not sure about the timing of base patch, but maybe this patch is also candidate for llvm 13 (backport)?

[efriedma]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1314

I think this belongs earlier, with the other mayLoopAccessLocation check? It's basically a variation of the same check.

[yurai007]

@efriedma @lebedev.ri:

I think this belongs earlier, with the other mayLoopAccessLocation check? It's basically a variation of the same check.

can we retain the transform by querying AA that there's no overlap?

I'm not sure if I follow your comments regarding AA (done in mayLoopAccessLocation). The problem in UT is not about 'load'-'store' relationship but about 'load'-'add' pair.
'Load' has 2 users - 'store' and 'add'. How AA can help in case when 'add' instruction is not seen by getModRefInfo at all? Currently getModRefInfo says always NoModRef when reaching 'add'.

[yurai007]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1314

Reffering to my previous comment - if you mean just moving this check before mayLoopAccessLocation then yes, I agree and you may ignore what I said about AA there :)

[yurai007]

In D107964#2941507, @xbolva00 wrote:

Not sure about the timing of base patch, but maybe this patch is also candidate for llvm 13 (backport)?

Indeed I can see base patch on release/13.x. I can cherry-pick change if it get acceptance.

[markus]

If the review is going to take a while maybe it is best to revert the offending patch in the meantime.

[yurai007]

@markus: Since all comments are addressed maybe it's just matter of sending ping to Roman and Eli. @lebedev.ri @eli.friedman can you take a second look please?

[yurai007]

Adding proper Eli's account @efriedma.

[lebedev.ri]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1308–1309

The new bailout needs some similar comment.

llvm/test/Transforms/LoopIdiom/basic.ll

1303

Please precommit the test

[yurai007]

Rebased to https://reviews.llvm.org/rG2e8534beb2890d258efc711ef7520c8bff54befd and addressed all comments.

[lebedev.ri]

LG
I believe this fix needs to be cherry-picked into 13.0 branch?

[yurai007]

LG
I believe this fix needs to be cherry-picked into 13.0 branch?

Thanks. Yes, it's under preparation.

[yurai007]

Thanks. Yes, it's under preparation.

Done: https://reviews.llvm.org/rGc22eb9a4a5ddfb6985dd2bc218be4e0ca5e9e512 and https://reviews.llvm.org/rG4e692c97a8c17a6eaf60f81327edff357086aa74

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

if (IsNegStride)
     LdStart =
         getStartForNegStride(LdStart, BECount, IntIdxTy, StoreSizeSCEV, 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 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)
     Stores.erase(TheStore);
   if (mayLoopAccessLocation(LoadBasePtr, ModRefInfo::Mod, CurLoop, BECount,
-                            StoreSizeSCEV, *AA, Stores)) {
+                            StoreSizeSCEV, *AA, Stores) ||
+      (UseMemMove && !TheLoad->hasOneUse())) {
     ORE.emit([&]() {
       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;

llvm/test/Transforms/LoopIdiom/basic.ll

for.body:                                         ; preds = %bb.nph, %for.body
   %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 load has more than one use.
+define i32 @do_not_form_memmove5(i32* %p) {
+; CHECK-LABEL: @do_not_form_memmove5(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i32 [ 15, [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[SUB]] = add nsw i32 [[INDEX]], -1
+; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[SUB]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 [[TMP0]]
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[IDXPROM:%.*]] = zext i32 [[INDEX]] to i64
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 [[IDXPROM]]
+; CHECK-NEXT:    store i32 [[TMP1]], i32* [[ARRAYIDX2]], align 4
+; CHECK-NEXT:    [[ADD]] = add nsw i32 [[TMP1]], [[SUM:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[INDEX]], 1
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_CLEANUP]]
+;
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  %add.lcssa = phi i32 [ %add, %for.body ]
+  ret i32 %add.lcssa
+
+for.body:                                      ; preds = %entry, %for.body
+  %index = phi i32 [ 15, %entry ], [ %sub, %for.body ]
+  %sum = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %sub = add nsw i32 %index, -1
+  %0 = zext i32 %sub to i64
+  %arrayidx = getelementptr inbounds i32, i32* %p, i64 %0
+  %1 = load i32, i32* %arrayidx, align 4
+  %idxprom = zext i32 %index to i64
+  %arrayidx2 = getelementptr inbounds i32, i32* %p, i64 %idxprom
+  store i32 %1, i32* %arrayidx2, align 4
+  %add = add nsw i32 %1, %sum
+  %cmp = icmp sgt i32 %index, 1
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}
+
 ;; 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: