[LoopIdiom] Keep TBAA when creating memcpy/memmove

[wsmoses]

Summary

When upgrading a loop of load/store to a memcpy, the existing pass does not keep existing aliasing information. This patch allows existing aliasing information to be kept.

[eopXD]

Is there any intention why this patch misses adding TBAA to Builder::CreateMemSet?

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1387

/*Merge=*/

1397

/*isVolatile=*/

1401

/*isVolatile=*/

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

2

Use the new PM.

opt -passes="loop-idiom"

[jeroen.dobbelaere]

Hmm.. what does it mean to have a !tbaa tag on a llvm.memcpy/llvm.memmove ? The langref only seem to mention !tbaa.struct for llvm.memcpy. Is it allowed to have both a !tbaa and a !tbaa.struct ? What would that mean ?

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

20

Can you also add a testcase where the merge is done ? Also the actual !tbaa representation is missing for the check.

[wsmoses]

Address comments

[wsmoses]

Hmm.. what does it mean to have a !tbaa tag on a llvm.memcpy/llvm.memmove ? The langref only seem to mention !tbaa.struct for llvm.memcpy. Is it allowed to have both a !tbaa and a !tbaa.struct ? What would that mean ?

I presume it's used to mark that the (src and dst) pointer have the aliasing properties of the given TBAA metadata for the entire range. I'm not sure about the lang ref, but it does appear that regular TBAA occurs on memcpy throughout the test suite.

wmoses@beast:/mnt/sabrent/wmoses/llvm-main/llvm/test ((HEAD detached from origin/main)) $ git grep "memcpy.*tbaa"
Analysis/TypeBasedAliasAnalysis/functionattrs.ll:  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %q, i64 %n, i1 false), !tbaa !1
Analysis/TypeBasedAliasAnalysis/functionattrs.ll:  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %q, i64 %n, i1 false), !tbaa !2
Analysis/TypeBasedAliasAnalysis/memcpyopt.ll:; CHECK-NEXT: tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull align 1 dereferenceable(16) %p, i8* noundef nonnull align 1 dereferenceable(16) %q, i64 16, i1 false), !tbaa !0
Analysis/TypeBasedAliasAnalysis/memcpyopt.ll:  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %q, i64 16, i1 false), !tbaa !2
Analysis/TypeBasedAliasAnalysis/memcpyopt.ll:  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %q, i8* %p, i64 16, i1 false), !tbaa !2

The TBAA memcpyopt test has a meaningful use of the metadata on memcpy, namely:

$ cat Analysis/TypeBasedAliasAnalysis/memcpyopt.ll
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -S -tbaa -basic-aa -memcpyopt -instcombine < %s | FileCheck %s

target datalayout = "e-p:64:64:64"

; The second memcpy is redundant and can be deleted. There's an intervening store, but
; it has a TBAA tag which declares that it is unrelated.

define void @foo(i8* nocapture %p, i8* nocapture %q, i8* nocapture %s) nounwind {
; CHECK: @foo
; CHECK-NEXT: tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull align 1 dereferenceable(16) %p, i8* noundef nonnull align 1 dereferenceable(16) %q, i64 16, i1 false), !tbaa !0
; CHECK-NEXT: store i8 2, i8* %s, align 1, !tbaa [[TAGA:!.*]]
; CHECK-NEXT: ret void
  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %q, i64 16, i1 false), !tbaa !2
  store i8 2, i8* %s, align 1, !tbaa !1
  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %q, i8* %p, i64 16, i1 false), !tbaa !2
  ret void
}

declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind

; CHECK: [[TAGA]] = !{[[TYPEA:!.*]], [[TYPEA]], i64 0}
; CHECK: [[TYPEA]] = !{!"A", !{{.*}}}
!0 = !{!"tbaa root"}
!1 = !{!3, !3, i64 0}
!2 = !{!4, !4, i64 0}
!3 = !{!"A", !0}
!4 = !{!"B", !0}

[jdoerfert]

@jeroen.dobbelaere Is this good enough for now and we try it out?

[jeroen.dobbelaere]

• A memmove test seems to be missing ?
• When the tbaa format is in 'new struct path tbaa' (-Xclang -new-struct-path-tbaa) format, the resulting shuffling should not be valid ? aka, the new struct path tbaa contains offset and size. Offset is likely to be 0 and size should be the size of a single element.
  • Either that should be filtered out,
  • or the size should be adapted, (But what with about an unknown size ?)
  • or maybe it should be converted into 'struct path tbaa' ?

[wsmoses]

Add memmove test and properly handle new-struct-path tbaa

[wsmoses]

@jeroen.dobbelaere Finally got around to updating this. Per your comments it now tests memmove and correctly deals with new-struct-tbaa (adding a relevant helper utility).

Let me know if you think this is good to land.

[wsmoses]

@jeroen.dobbelaere bump

[jeroen.dobbelaere]

I checked the testcases for now and found some interesting effects. Can you comment on those ?

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

46

I get !tbaa %0. Is this what we would expect ? Shouldn't the tbaa be dropped here ? (float vs double)

82

; CHECK-NOT: tbaa

143

Shouldn't this be on the next line ?

llvm/test/Transforms/LoopIdiom/memmove-tbaa.ll

37 ↗

(On Diff #402383)

I get !tbaa %0. Is this what we would expect ? Shouldn't the tbaa be dropped here ? (float vs double)

64 ↗

(On Diff #402383)

This should be on the next line

[wsmoses]

Fix rebase regression

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

46

Good catch, it appears the merge has become not in place. Fixed

[wsmoses]

Fix test

[jeroen.dobbelaere]

Sorry about not mentioning it with the previous part.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1174

We will also need a memset test.

[wsmoses]

Add memset test

[wsmoses]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1174

Added, apparently I hadn't done a git add.

[wsmoses]

Add memset struct-path tests

[jeroen.dobbelaere]

LGTM. Thanks !

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

bool LoopIdiomRecognize::processLoopStridedStore(
   if (SplatValue) {
     NewCall = Builder.CreateMemSet(BasePtr, SplatValue, NumBytes,
                                    MaybeAlign(StoreAlignment));
   } else {
     // Everything is emitted in default address space
     Type *Int8PtrTy = DestInt8PtrTy;
 
     Module *M = TheStore->getModule();
     StringRef FuncName = "memset_pattern16";
     FunctionCallee MSP = M->getOrInsertFunction(FuncName, Builder.getVoidTy(),
                                                 Int8PtrTy, Int8PtrTy, IntIdxTy);
     inferLibFuncAttributes(M, FuncName, *TLI);
 
     // Otherwise we should form a memset_pattern16.  PatternValue is known to be
     // an constant array of 16-bytes.  Plop the value into a mergable global.
     GlobalVariable *GV = new GlobalVariable(*M, PatternValue->getType(), true,
                                             GlobalValue::PrivateLinkage,
bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(
   // Okay, everything is safe, we can transform this!
 
   const SCEV *NumBytesS = getNumBytes(
       BECount, IntIdxTy, SE->getConstant(IntIdxTy, StoreSize), CurLoop, DL, SE);
 
   Value *NumBytes =
       Expander.expandCodeFor(NumBytesS, IntIdxTy, Preheader->getTerminator());
 
+  AAMDNodes AATags;
+  TheLoad->getAAMetadata(AATags);
+  TheStore->getAAMetadata(AATags, /*Merge*/ true);
+
   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 (!TheStore->isAtomic() && !TheLoad->isAtomic()) {
     if (UseMemMove)
-      NewCall = Builder.CreateMemMove(StoreBasePtr, StoreAlign, LoadBasePtr,
-                                      LoadAlign, NumBytes);
+      NewCall = Builder.CreateMemMove(
+          StoreBasePtr, StoreAlign, LoadBasePtr, LoadAlign, NumBytes,
+          /*isVolatile*/ false, AATags.TBAA, AATags.Scope, AATags.NoAlias);
     else
-      NewCall = Builder.CreateMemCpy(StoreBasePtr, StoreAlign, LoadBasePtr,
-                                     LoadAlign, NumBytes);
+      NewCall =
+          Builder.CreateMemCpy(StoreBasePtr, StoreAlign, LoadBasePtr, LoadAlign,
+                               NumBytes, /*isVolatile*/ false, AATags.TBAA,
+                               AATags.TBAAStruct, AATags.Scope, AATags.NoAlias);
   } else {
     // For now don't support unordered atomic memmove.
     if (UseMemMove)
       return Changed;
     // We cannot allow unaligned ops for unordered load/store, so reject
     // anything where the alignment isn't at least the element size.
     assert((StoreAlign.hasValue() && LoadAlign.hasValue()) &&
            "Expect unordered load/store to have align.");
     if (StoreAlign.getValue() < StoreSize || LoadAlign.getValue() < StoreSize)
       return Changed;
 
     // 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 Changed;
 
     // 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, StoreAlign.getValue(), LoadBasePtr, LoadAlign.getValue(),
-        NumBytes, StoreSize);
+        NumBytes, StoreSize, AATags.TBAA, AATags.TBAAStruct, AATags.Scope,
+        AATags.NoAlias);
   }
   NewCall->setDebugLoc(TheStore->getDebugLoc());
 
   if (MSSAU) {
     MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
         NewCall, nullptr, NewCall->getParent(), MemorySSA::BeforeTerminator);
     MSSAU->insertDef(cast<MemoryDef>(NewMemAcc), true);
   }

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -loop-idiom < %s -S | FileCheck %s
+
+define void @looper(double* noalias nocapture readonly %M, double* noalias nocapture %out) {
+; CHECK-LABEL: @looper(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[OUT1:%.*]] = bitcast double* [[OUT:%.*]] to i8*
+; CHECK-NEXT:    [[M2:%.*]] = bitcast double* [[M:%.*]] to i8*
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 [[OUT1]], i8* align 8 [[M2]], i64 256, i1 false), !tbaa [[TBAA0:![0-9]+]]
+; CHECK-NEXT:    br label [[FOR_BODY4:%.*]]
+; CHECK:       for.body4:
+; CHECK-NEXT:    [[J_020:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY4]] ]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds double, double* [[M]], i64 [[J_020]]
+; CHECK-NEXT:    [[A0:%.*]] = load double, double* [[ARRAYIDX]], align 8, !tbaa [[TBAA0]]
+; CHECK-NEXT:    [[ARRAYIDX8:%.*]] = getelementptr inbounds double, double* [[OUT]], i64 [[J_020]]
+; CHECK-NEXT:    [[INC]] = add nuw nsw i64 [[J_020]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[J_020]], 31
+; CHECK-NEXT:    br i1 [[CMP2]], label [[FOR_BODY4]], label [[FOR_COND_CLEANUP:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.body4
+
+for.body4:                                        ; preds = %for.cond1.preheader, %for.body4
+  %j.020 = phi i64 [ 0, %entry ], [ %inc, %for.body4 ]
+  %arrayidx = getelementptr inbounds double, double* %M, i64 %j.020
+  %a0 = load double, double* %arrayidx, align 8, !tbaa !5
+  %arrayidx8 = getelementptr inbounds double, double* %out, i64 %j.020
+  store double %a0, double* %arrayidx8, align 8, !tbaa !5
+  %inc = add nuw nsw i64 %j.020, 1
+  %cmp2 = icmp ult i64 %j.020, 31
+  br i1 %cmp2, label %for.body4, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3
+  ret void
+}
+
+!5 = !{!6, !6, i64 0}
+!6 = !{!"double", !7, i64 0}
+!7 = !{!"omnipotent char", !8, i64 0}
+!8 = !{!"Simple C++ TBAA"}