[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

1464

/*Merge=*/

1478

/*isVolatile=*/

1482

/*isVolatile=*/

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

3

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

21

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

38

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

65

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

1181

We will also need a memset test.

[wsmoses]

Add memset test

[wsmoses]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1181

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

[wsmoses]

Add memset struct-path tests

[jeroen.dobbelaere]

LGTM. Thanks !

llvm/include/llvm/IR/Metadata.h

 //===- llvm/IR/Metadata.h - Metadata definitions ----------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
struct AAMDNodes {
   MDNode *NoAlias = nullptr;
 
   // Shift tbaa Metadata node to start off bytes later
   static MDNode *shiftTBAA(MDNode *M, size_t off);
 
   // Shift tbaa.struct Metadata node to start off bytes later
   static MDNode *shiftTBAAStruct(MDNode *M, size_t off);
 
+  // Extend tbaa Metadata node to apply to a series of bytes of length len.
+  // A size of -1 denotes an unknown size.
+  static MDNode *extendToTBAA(MDNode *TBAA, ssize_t len);
+
   /// Given two sets of AAMDNodes that apply to the same pointer,
   /// give the best AAMDNodes that are compatible with both (i.e. a set of
   /// nodes whose allowable aliasing conclusions are a subset of those
   /// allowable by both of the inputs). However, for efficiency
   /// reasons, do not create any new MDNodes.
   AAMDNodes intersect(const AAMDNodes &Other) const {
     AAMDNodes Result;
     Result.TBAA = Other.TBAA == TBAA ? TBAA : nullptr;
AAMDNodes shift(size_t Offset) const {
     Result.TBAA = TBAA ? shiftTBAA(TBAA, Offset) : nullptr;
     Result.TBAAStruct =
         TBAAStruct ? shiftTBAAStruct(TBAAStruct, Offset) : nullptr;
     Result.Scope = Scope;
     Result.NoAlias = NoAlias;
     return Result;
   }
 
+  /// Create a new AAMDNode that describes this AAMDNode after extending it to
+  /// apply to a series of bytes of length Len. A size of -1 denotes an unknown
+  /// size.
+  AAMDNodes extendTo(ssize_t Len) const {
+    AAMDNodes Result;
+    Result.TBAA = TBAA ? extendToTBAA(TBAA, Len) : nullptr;
+    // tbaa.struct contains (offset, size, type) triples. Extending the length
+    // of the tbaa.struct doesn't require changing this (though more information
+    // could be provided by adding more triples at subsequent lengths).
+    Result.TBAAStruct = TBAAStruct;
+    Result.Scope = Scope;
+    Result.NoAlias = NoAlias;
+    return Result;
+  }
+
   /// Given two sets of AAMDNodes applying to potentially different locations,
   /// determine the best AAMDNodes that apply to both.
   AAMDNodes merge(const AAMDNodes &Other) const;
 
   /// Determine the best AAMDNodes after concatenating two different locations
   /// together. Different from `merge`, where different locations should
   /// overlap each other, `concat` puts non-overlapping locations together.
   AAMDNodes concat(const AAMDNodes &Other) const;

llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp

 //===- TypeBasedAliasAnalysis.cpp - Type-Based Alias Analysis -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
for (size_t i = 0, size = MD->getNumOperands(); i < size; i += 3) {
     Sub.push_back(ConstantAsMetadata::get(
         ConstantInt::get(InnerOffset->getType(), NewOffset)));
     Sub.push_back(ConstantAsMetadata::get(
         ConstantInt::get(InnerSize->getType(), NewSize)));
     Sub.push_back(MD->getOperand(i + 2));
   }
   return MDNode::get(MD->getContext(), Sub);
 }
+
+MDNode *AAMDNodes::extendToTBAA(MDNode *MD, ssize_t Len) {
+  // Fast path if 0-length
+  if (Len == 0)
+    return nullptr;
+
+  // Regular TBAA is invariant of length, so we only need to consider
+  // struct-path TBAA.
+  if (!isStructPathTBAA(MD))
+    return MD;
+
+  TBAAStructTagNode Tag(MD);
+
+  // Only new format TBAA has a size
+  if (!Tag.isNewFormat())
+    return MD;
+
+  // If unknown size, drop the TBAA.
+  if (Len == -1)
+    return nullptr;
+
+  // Otherwise, create TBAA with the new Len
+  SmallVector<Metadata *, 4> NextNodes(MD->operands());
+  ConstantInt *PreviousSize = mdconst::extract<ConstantInt>(NextNodes[3]);
+
+  // Don't create a new MDNode if it is the same length.
+  if (PreviousSize->equalsInt(Len))
+    return MD;
+
+  NextNodes[3] =
+      ConstantAsMetadata::get(ConstantInt::get(PreviousSize->getType(), Len));
+  return MDNode::get(MD->getContext(), NextNodes);
+}

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 //===- LoopIdiomRecognize.cpp - Loop idiom recognition --------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
bool LoopIdiomRecognize::processLoopStridedStore(
   if (!isSafeToExpand(NumBytesS, *SE))
     return Changed;
 
   Value *NumBytes =
       Expander.expandCodeFor(NumBytesS, IntIdxTy, Preheader->getTerminator());
 
   CallInst *NewCall;
   if (SplatValue) {
-    NewCall = Builder.CreateMemSet(BasePtr, SplatValue, NumBytes,
-                                   MaybeAlign(StoreAlignment));
+    AAMDNodes AATags = TheStore->getAAMetadata();
+    if (auto CI = dyn_cast<ConstantInt>(NumBytes))
+      AATags = AATags.extendTo(CI->getZExtValue());
+    else
+      AATags = AATags.extendTo(-1);
+
+    NewCall = Builder.CreateMemSet(
+        BasePtr, SplatValue, NumBytes, MaybeAlign(StoreAlignment),
+        /*isVolatile=*/false, AATags.TBAA, AATags.Scope, AATags.NoAlias);
   } 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);
bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(
   // Okay, everything is safe, we can transform this!
 
   const SCEV *NumBytesS =
       getNumBytes(BECount, IntIdxTy, StoreSizeSCEV, CurLoop, DL, SE);
 
   Value *NumBytes =
       Expander.expandCodeFor(NumBytesS, IntIdxTy, Preheader->getTerminator());
 
+  AAMDNodes AATags = TheLoad->getAAMetadata();
+  AAMDNodes StoreAATags = TheStore->getAAMetadata();
+  AATags = AATags.merge(StoreAATags);
+  if (auto CI = dyn_cast<ConstantInt>(NumBytes))
+    AATags = AATags.extendTo(CI->getZExtValue());
+  else
+    AATags = AATags.extendTo(-1);
+
   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 -passes="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
+}
+
+
+define void @looperBadMerge(double* noalias nocapture readonly %M, double* noalias nocapture %out) {
+; CHECK-LABEL: @looperBadMerge(
+; 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 [[TBAAF:![0-9]+]]
+; CHECK-NOT: tbaa
+; 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 !3
+  %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
+}
+
+define void @looperGoodMerge(double* noalias nocapture readonly %M, double* noalias nocapture %out) {
+; CHECK-LABEL: @looperGoodMerge(
+; 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)
+; CHECK-NOT:     !tbaa
+; 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
+  %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
+}
+
+define void @looperConstantTBAAStruct(double* nocapture noalias %out, double* nocapture noalias %in) {
+; CHECK-LABEL: @looperConstantTBAAStruct(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[OUT1:%.*]] = bitcast double* [[OUT:%.*]] to i8*
+; CHECK-NEXT:    [[IN1:%.*]] = bitcast double* [[IN:%.*]] to i8*
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 [[OUT1]], i8* align 8 [[IN1]], i64 32, i1 false), !tbaa [[TBAA8:![0-9]+]]
+;
+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* %in, i64 %j.020
+  %a0 = load double, double* %arrayidx, align 8, !tbaa !10
+  %arrayidx8 = getelementptr inbounds double, double* %out, i64 %j.020
+  store double %a0, double* %arrayidx8, align 8, !tbaa !10
+  %inc = add nuw nsw i64 %j.020, 1
+  %cmp2 = icmp ult i64 %j.020, 3
+  br i1 %cmp2, label %for.body4, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3
+  ret void
+}
+
+define void @looperVarTBAAStruct(double* nocapture noalias %out, double* nocapture noalias %in, i64 %len) {
+; CHECK-LABEL: @looperVarTBAAStruct(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[OUT1:%.*]] = bitcast double* [[OUT:%.*]] to i8*
+; CHECK-NEXT:    [[IN1:%.*]] = bitcast double* [[IN:%.*]] to i8*
+; CHECK-NEXT:    [[umax:%.*]] = call i64 @llvm.umax.i64(i64 %len, i64 1)
+; CHECK-NEXT:    [[I0:%.*]] = shl nuw i64 [[umax]], 3
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 [[OUT1]], i8* align 8 [[IN1]], i64 [[I0]], i1 false)
+; CHECK-NOT: !tbaa
+; CHECK-NEXT:    br 
+;
+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* %in, i64 %j.020
+  %a0 = load double, double* %arrayidx, align 8, !tbaa !10
+  %arrayidx8 = getelementptr inbounds double, double* %out, i64 %j.020
+  store double %a0, double* %arrayidx8, align 8, !tbaa !10
+  %inc = add nuw nsw i64 %j.020, 1
+  %cmp2 = icmp ult i64 %inc, %len
+  br i1 %cmp2, label %for.body4, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup3
+  ret void
+}
+
+
+; CHECK: [[TBAA0]] = !{[[TBAA1:.+]], [[TBAA1]], i64 0}
+; CHECK: [[TBAA1]] = !{!"double", [[TBAA2:.+]], i64 0}
+; CHECK: [[TBAA2]] = !{!"omnipotent char", [[TBAA3:.+]], i64 0}
+; CHECK: [[TBAAF]] = !{[[TBAA2]], [[TBAA2]], i64 0}
+
+; CHECK: [[TBAA8]] = !{[[TBAA5:.+]], [[TBAA6:.+]], i64 0, i64 32}
+; CHECK: [[TBAA5]] = !{[[TBAA7:.+]], i64 32, !"_ZTS1A", [[TBAA6]], i64 0, i64 8, [[TBAA6]], i64 8, i64 8, [[TBAA6]], i64 16, i64 8, [[TBAA6]], i64 24, i64 8}
+; CHECK: [[TBAA7]] = !{[[TBAA3]], i64 0, !"omnipotent char"}
+; CHECK: [[TBAA6]] = !{[[TBAA7]], i64 8, !"double"}
+
+!3 = !{!4, !4, i64 0}
+!4 = !{!"float", !7, i64 0}
+!5 = !{!6, !6, i64 0}
+!6 = !{!"double", !7, i64 0}
+!7 = !{!"omnipotent char", !8, i64 0}
+!8 = !{!"Simple C++ TBAA"}
+
+!15 = !{!8, i64 0, !"omnipotent char"}
+!17 = !{!15, i64 8, !"double"}
+!9 = !{!15, i64 32, !"_ZTS1A", !17, i64 0, i64 8, !17, i64 8, i64 8, !17, i64 16, i64 8, !17, i64 24, i64 8}
+!10 = !{!9, !17, i64 0, i64 8}

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes="loop-idiom" < %s -S | FileCheck %s
+
+define void @looper(double* nocapture %out) {
+; CHECK-LABEL: @looper(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[OUT1:%.*]] = bitcast double* [[OUT:%.*]] to i8*
+; CHECK-NEXT:    [[M:%.*]] = getelementptr double, double* %out, i32 16
+; CHECK-NEXT:    [[M2:%.*]] = bitcast double* [[M]] to i8*
+; CHECK-NEXT:    call void @llvm.memmove.p0i8.p0i8.i64(i8* align 8 [[OUT1]], i8* align 8 [[M2]], i64 256, i1 false), !tbaa [[TBAA0:![0-9]+]]
+;
+entry:
+  %M = getelementptr double, double* %out, i32 16
+  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
+}
+
+
+define void @looperBadMerge(double* nocapture %out) {
+; CHECK-LABEL: @looperBadMerge(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[OUT1:%.*]] = bitcast double* [[OUT:%.*]] to i8*
+; CHECK-NEXT:    [[M:%.*]] = getelementptr double, double* %out, i32 16
+; CHECK-NEXT:    [[M2:%.*]] = bitcast double* [[M]] to i8*
+; CHECK-NEXT:    call void @llvm.memmove.p0i8.p0i8.i64(i8* align 8 [[OUT1]], i8* align 8 [[M2]], i64 256, i1 false), !tbaa [[TBAAF:![0-9]+]]
+; CHECK-NEXT:    br label [[FOR_BODY4:%.*]]
+;
+entry:
+  %M = getelementptr double, double* %out, i32 16
+  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 !3
+  %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
+}
+
+define void @looperGoodMerge(double* nocapture %out) {
+; CHECK-LABEL: @looperGoodMerge(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[OUT1:%.*]] = bitcast double* [[OUT:%.*]] to i8*
+; CHECK-NEXT:    [[M:%.*]] = getelementptr double, double* %out, i32 16
+; CHECK-NEXT:    [[M2:%.*]] = bitcast double* [[M]] to i8*
+; CHECK-NEXT:    call void @llvm.memmove.p0i8.p0i8.i64(i8* align 8 [[OUT1]], i8* align 8 [[M2]], i64 256, i1 false) 
+; CHECK-NOT:     !tbaa
+; CHECK-NEXT:    br label [[FOR_BODY4:%.*]]
+;
+entry:
+  %M = getelementptr double, double* %out, i32 16
+  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
+  %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
+}
+
+; CHECK: [[TBAA0]] = !{[[TBAA1:.+]], [[TBAA1]], i64 0}
+; CHECK: [[TBAA1]] = !{!"double", [[TBAA2:.+]], i64 0}
+; CHECK: [[TBAA2]] = !{!"omnipotent char", [[TBAA3:.+]], i64 0}
+; CHECK: [[TBAAF]] = !{[[TBAA2]], [[TBAA2]], i64 0}
+
+!3 = !{!4, !4, i64 0}
+!4 = !{!"float", !7, i64 0}
+!5 = !{!6, !6, i64 0}
+!6 = !{!"double", !7, i64 0}
+!7 = !{!"omnipotent char", !8, i64 0}
+!8 = !{!"Simple C++ TBAA"}

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes="loop-idiom" < %s -S | FileCheck %s
+
+
+define dso_local void @double_memset(i8* nocapture %p) {
+; CHECK-LABEL: @double_memset(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[P:%.*]], i8 0, i64 16, i1 false), !tbaa [[TBAA0:![0-9]+]]
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body:
+; CHECK-NEXT:    [[I_07:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_BODY]] ], [ 0, %entry ]
+; CHECK-NEXT:    [[INCDEC_PTR1:.+]] = getelementptr inbounds i8, i8* [[P]], i64 [[I_07]]
+; CHECK-NEXT:    [[INC]] = add nuw nsw i64 [[I_07]], 1
+; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INC]], 16
+; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label [[FOR_COND_CLEANUP_LOOPEXIT:%.*]], label [[FOR_BODY]]
+;
+entry:
+  br label %for.body
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %i.07 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
+  %ptr1 = getelementptr inbounds i8, i8* %p, i64 %i.07
+  store i8 0, i8* %ptr1, align 1, !tbaa !5
+  %inc = add nuw nsw i64 %i.07, 1
+  %exitcond.not = icmp eq i64 %inc, 16
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK: [[TBAA0]] = !{[[TBAA1:.+]], [[TBAA1]], i64 0}
+; CHECK: [[TBAA1]] = !{!"double", [[TBAA2:.+]], i64 0}
+; CHECK: [[TBAA2]] = !{!"omnipotent char", [[TBAA3:.+]], i64 0}
+
+!5 = !{!6, !6, i64 0}
+!6 = !{!"double", !7, i64 0}
+!7 = !{!"omnipotent char", !8, i64 0}
+!8 = !{!"Simple C++ TBAA"}