[Analysis] Fix merging TBAA tags with different final access types

[kosarev]

Summary

There are cases when we have to merge TBAA access tags with the same base access type, but different final access types. For example, accesses to different members of the same structure may be vectorized into a single load or store instruction. Since we currently assume that the tags to merge always share the same final access type, we incorrectly return a tag that describes an access to one of the original final access types as the generic tag. This patch fixes that by producing generic tags for the common type and not the final access types of the original tags.

Resolves:
PR35225: Wrong tbaa metadata after load store vectorizer due to recent change
https://bugs.llvm.org/show_bug.cgi?id=35225

[hfinkel]

lib/Analysis/TypeBasedAliasAnalysis.cpp

545

Can you please *explain* the problem in the patch description.

Also, we're now creating new metadata nodes speculatively (i.e., in cases where we we'll return false); can we avoid doing that? (maybe using a lambda function would help?)

[kosarev]

lib/Analysis/TypeBasedAliasAnalysis.cpp

545

Sure, sorry.

Re: creating nodes: we have to produce the generic tag regardless of whether the input tags may alias. We did it before and we do it now; the patch is not supposed to change anything in this regard.

[hfinkel]

lib/Analysis/TypeBasedAliasAnalysis.cpp

545

Thanks. LGTM.

lib/Analysis/TypeBasedAliasAnalysis.cpp

while (const MDNode *BaseTypeNode = BaseType.getNode()) {
     // Follow the edge with the correct offset, Offset will be adjusted to
     // be relative to the field type.
     BaseType = BaseType.getParent(OffsetInBase);
   }
   return false;
 }
 
 static const MDNode *createAccessTag(const MDNode *AccessType) {
+  // If there is no access type or the access type is the root node, then
+  // we don't have any useful access tag to return.
+  if (!AccessType || AccessType->getNumOperands() < 2)
+    return nullptr;
+
   Type *Int64 = IntegerType::get(AccessType->getContext(), 64);
   auto *ImmutabilityFlag = ConstantAsMetadata::get(ConstantInt::get(Int64, 0));
   Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
                      const_cast<MDNode*>(AccessType), ImmutabilityFlag};
   return MDNode::get(AccessType->getContext(), Ops);
 }
 
 /// matchTags - Return true if the given couple of accesses are allowed to
static bool matchAccessTags(const MDNode *A, const MDNode *B,
   }
 
   // Verify that both input nodes are struct-path aware.  Auto-upgrade should
   // have taken care of this.
   assert(isStructPathTBAA(A) && "Access A is not struct-path aware!");
   assert(isStructPathTBAA(B) && "Access B is not struct-path aware!");
 
   TBAAStructTagNode TagA(A), TagB(B);
+  const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(),
+                                                TagB.getAccessType());
+  if (GenericTag)
+    *GenericTag = createAccessTag(CommonType);
 
   // TODO: We need to check if AccessType of TagA encloses AccessType of
   // TagB to support aggregate AccessType. If yes, return true.
 
-  const MDNode *BaseA = TagA.getBaseType();
-  const MDNode *BaseB = TagB.getBaseType();
-
   // Climb the type DAG from base type of A to see if we reach base type of B.
   uint64_t OffsetA;
-  if (findAccessType(TagA, BaseB, OffsetA)) {
-    if (GenericTag)
-      *GenericTag = createAccessTag(TagB.getAccessType());
+  if (findAccessType(TagA, TagB.getBaseType(), OffsetA))
     return OffsetA == TagB.getOffset();
-  }
 
   // Climb the type DAG from base type of B to see if we reach base type of A.
   uint64_t OffsetB;
-  if (findAccessType(TagB, BaseA, OffsetB)) {
-    if (GenericTag)
-      *GenericTag = createAccessTag(TagA.getAccessType());
+  if (findAccessType(TagB, TagA.getBaseType(), OffsetB))
     return OffsetB == TagA.getOffset();
-  }
-
-  // If neither node is an ancestor of the other, then try to find the type
-  // that is common to both the final access types.
-  const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(),
-                                                TagB.getAccessType());
-
-  // If there is no common type or the only common type is the root node, then
-  // we don't have any useful generic access tag to return.
-  if (GenericTag)
-    *GenericTag = !CommonType || CommonType->getNumOperands() < 2 ?
-        nullptr : createAccessTag(CommonType);
 
-  // If they have different roots, they're part of different potentially
-  // unrelated type systems, so we must be conservative.
+  // If the final access types have different roots, they're part of different
+  // potentially unrelated type systems, so we must be conservative.
   if (!CommonType)
     return true;
 
   // If they have the same root, then we've proved there's no alias.
   return false;
 }
 
 /// Aliases - Test whether the access represented by tag A may alias the

test/Transforms/LoadStoreVectorizer/X86/merge-tbaa.ll

+; RUN: opt -mtriple=x86_64-unknown-linux-gnu -load-store-vectorizer -S < %s | \
+; RUN:     FileCheck %s
+;
+; The GPU Load & Store Vectorizer may merge differently-typed accesses into a
+; single instruction. This test checks that we merge TBAA tags for such
+; accesses correctly.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; struct S {
+;   float f;
+;   int i;
+; };
+%struct.S = type { float, i32 }
+
+; float foo(S *p) {
+;   p->f -= 1;
+;   p->i -= 1;
+;   return p->f;
+; }
+define float @foo(%struct.S* %p) {
+entry:
+; CHECK-LABEL: foo
+; CHECK: load <2 x i32>, {{.*}}, !tbaa [[TAG_char:!.*]]
+; CHECK: store <2 x i32> {{.*}}, !tbaa [[TAG_char]]
+  %f = getelementptr inbounds %struct.S, %struct.S* %p, i64 0, i32 0
+  %0 = load float, float* %f, align 4, !tbaa !2
+  %sub = fadd float %0, -1.000000e+00
+  store float %sub, float* %f, align 4, !tbaa !2
+  %i = getelementptr inbounds %struct.S, %struct.S* %p, i64 0, i32 1
+  %1 = load i32, i32* %i, align 4, !tbaa !8
+  %sub1 = add nsw i32 %1, -1
+  store i32 %sub1, i32* %i, align 4, !tbaa !8
+  ret float %sub
+}
+
+!2 = !{!3, !4, i64 0}
+!3 = !{!"_ZTS1S", !4, i64 0, !7, i64 4}
+!4 = !{!"float", !5, i64 0}
+!5 = !{!"omnipotent char", !6, i64 0}
+!6 = !{!"Simple C++ TBAA"}
+!7 = !{!"int", !5, i64 0}
+!8 = !{!3, !7, i64 4}
+
+; CHECK-DAG: [[TYPE_char:!.*]] = !{!"omnipotent char", {{.*}}, i64 0}
+; CHECK-FAG: [[TAG_char]] = !{[[TYPE_char]], [[TYPE_char]], i64 0}