[Analysis] Support aggregate access types in TBAA

[kosarev]

Summary

This patch implements analysis for new-format TBAA access tags with aggregate types as their final access types.

[kosarev]

Ping.

[kosarev]

Hal, can you please review this patch?

[hfinkel]

lib/Analysis/TypeBasedAliasAnalysis.cpp

153 ↗

(On Diff #127905)

Add a comment here reminding the reader that, in the old format, this first operand was a string.

231 ↗

(On Diff #127905)

0 does not seem like a conservatively-correct result. I think this should either assert or return UINT64_MAX.

272 ↗

(On Diff #127905)

This is the same as the function above. Maybe make a static helper function to avoid repeating the logic?

337 ↗

(On Diff #127905)

Align this with the unsigned above.

555 ↗

(On Diff #127905)

I think this should be UINT64_MAX, not 0, to be conservatively correct. IR generated by this code might be interpreted later by an implementation that does care about the sizes.

580 ↗

(On Diff #127905)

Please document the meaning of this function's parameters and return value.

604 ↗

(On Diff #127905)

Space after for.

608 ↗

(On Diff #127905)

The assert should have a string that explains what's going on.

[kosarev]

Updated.

[kosarev]

Ping.

[hfinkel]

A couple comments, but otherwise LGTM.

lib/Analysis/TypeBasedAliasAnalysis.cpp

640 ↗

(On Diff #130397)

Please name this something other than BaseType because we already have a variable by that name in scope, and moreover, this is an access type (and so calling it 'BaseType' seems somewhat confusing (given that BaseType above is not necessarily an access type). Maybe just calling it BaseAccessType would be better.

Alternatively, just remove this because, to get here, I think that BaseType is always equal to the access type.

642 ↗

(On Diff #130397)

Especially because, in the past, access types were only scalars, I think it would be useful to have a comment here reminding the reader than the access type might be an aggregate (thus explaining the need for this check).

llvm/trunk/lib/Analysis/TypeBasedAliasAnalysis.cpp

 // If we reach the Root node, perform the above starting from base type of tagY
 // to see if we reach base type of tagX.
 //
 // If they have different roots, they're part of different potentially
 // unrelated type systems, so we return Alias to be conservative.
 // If neither node is an ancestor of the other and they have the same root,
 // then we say NoAlias.
 //
-// TODO: The current metadata format doesn't support struct
-// fields. For example:
-//   struct X {
-//     double d;
-//     int i;
-//   };
-//   void foo(struct X *x, struct X *y, double *p) {
-//     *x = *y;
-//     *p = 0.0;
-//   }
-// Struct X has a double member, so the store to *x can alias the store to *p.
-// Currently it's not possible to precisely describe all the things struct X
-// aliases, so struct assignments must use conservative TBAA nodes. There's
-// no scheme for attaching metadata to @llvm.memcpy yet either.
-//
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"

 
 // A handy option for disabling TBAA functionality. The same effect can also be
 // achieved by stripping the !tbaa tags from IR, but this option is sometimes
 // more convenient.
 static cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true), cl::Hidden);
 
 namespace {
 
+/// isNewFormatTypeNode - Return true iff the given type node is in the new
+/// size-aware format.
+static bool isNewFormatTypeNode(const MDNode *N) {
+  if (N->getNumOperands() < 3)
+    return false;
+  // In the old format the first operand is a string.
+  if (!isa<MDNode>(N->getOperand(0)))
+    return false;
+  return true;
+}
+
 /// This is a simple wrapper around an MDNode which provides a higher-level
 /// interface by hiding the details of how alias analysis information is encoded
 /// in its operands.
 template<typename MDNodeTy>
 class TBAANodeImpl {
   MDNodeTy *Node = nullptr;
 
 public:
   TBAANodeImpl() = default;
   explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {}
 
   /// getNode - Get the MDNode for this TBAANode.
   MDNodeTy *getNode() const { return Node; }
 
+  /// isNewFormat - Return true iff the wrapped type node is in the new
+  /// size-aware format.
+  bool isNewFormat() const { return isNewFormatTypeNode(Node); }
+
   /// getParent - Get this TBAANode's Alias tree parent.
   TBAANodeImpl<MDNodeTy> getParent() const {
+    if (isNewFormat())
+      return TBAANodeImpl(cast<MDNodeTy>(Node->getOperand(0)));
+
     if (Node->getNumOperands() < 2)
       return TBAANodeImpl<MDNodeTy>();
     MDNodeTy *P = dyn_cast_or_null<MDNodeTy>(Node->getOperand(1));
     if (!P)
       return TBAANodeImpl<MDNodeTy>();
     // Ok, this node has a valid parent. Return it.
     return TBAANodeImpl<MDNodeTy>(P);
   }

 using MutableTBAANode = TBAANodeImpl<MDNode>;
 /// @}
 
 /// This is a simple wrapper around an MDNode which provides a
 /// higher-level interface by hiding the details of how alias analysis
 /// information is encoded in its operands.
 template<typename MDNodeTy>
 class TBAAStructTagNodeImpl {
-  /// This node should be created with createTBAAStructTagNode.
+  /// This node should be created with createTBAAAccessTag().
   MDNodeTy *Node;
 
 public:
   explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {}
 
   /// Get the MDNode for this TBAAStructTagNode.
   MDNodeTy *getNode() const { return Node; }
 
+  /// isNewFormat - Return true iff the wrapped access tag is in the new
+  /// size-aware format.
+  bool isNewFormat() const {
+    if (Node->getNumOperands() < 4)
+      return false;
+    if (MDNodeTy *AccessType = getAccessType())
+      if (!TBAANodeImpl<MDNodeTy>(AccessType).isNewFormat())
+        return false;
+    return true;
+  }
+
   MDNodeTy *getBaseType() const {
     return dyn_cast_or_null<MDNode>(Node->getOperand(0));
   }
 
   MDNodeTy *getAccessType() const {
     return dyn_cast_or_null<MDNode>(Node->getOperand(1));
   }
 
   uint64_t getOffset() const {
     return mdconst::extract<ConstantInt>(Node->getOperand(2))->getZExtValue();
   }
 
+  uint64_t getSize() const {
+    if (!isNewFormat())
+      return UINT64_MAX;
+    return mdconst::extract<ConstantInt>(Node->getOperand(3))->getZExtValue();
+  }
+
   /// Test if this TBAAStructTagNode represents a type for objects
   /// which are not modified (by any means) in the context where this
   /// AliasAnalysis is relevant.
   bool isTypeImmutable() const {
-    if (Node->getNumOperands() < 4)
+    unsigned OpNo = isNewFormat() ? 4 : 3;
+    if (Node->getNumOperands() < OpNo + 1)
       return false;
-    ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(3));
+    ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(OpNo));
     if (!CI)
       return false;
     return CI->getValue()[0];
   }
 };
 
 /// \name Specializations of \c TBAAStructTagNodeImpl for const and non const
 /// qualified \c MDNods.
 /// @{
 using TBAAStructTagNode = TBAAStructTagNodeImpl<const MDNode>;
 using MutableTBAAStructTagNode = TBAAStructTagNodeImpl<MDNode>;
 /// @}
 
 /// This is a simple wrapper around an MDNode which provides a
 /// higher-level interface by hiding the details of how alias analysis
 /// information is encoded in its operands.
 class TBAAStructTypeNode {
-  /// This node should be created with createTBAAStructTypeNode.
+  /// This node should be created with createTBAATypeNode().
   const MDNode *Node = nullptr;
 
 public:
   TBAAStructTypeNode() = default;
   explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {}
 
   /// Get the MDNode for this TBAAStructTypeNode.
   const MDNode *getNode() const { return Node; }
 
+  /// isNewFormat - Return true iff the wrapped type node is in the new
+  /// size-aware format.
+  bool isNewFormat() const { return isNewFormatTypeNode(Node); }
+
+  bool operator==(const TBAAStructTypeNode &Other) const {
+    return getNode() == Other.getNode();
+  }
+
+  /// getId - Return type identifier.
+  Metadata *getId() const {
+    return Node->getOperand(isNewFormat() ? 2 : 0);
+  }
+
+  unsigned getNumFields() const {
+    unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;
+    unsigned NumOpsPerField = isNewFormat() ? 3 : 2;
+    return (getNode()->getNumOperands() - FirstFieldOpNo) / NumOpsPerField;
+  }
+
+  TBAAStructTypeNode getFieldType(unsigned FieldIndex) const {
+    unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;
+    unsigned NumOpsPerField = isNewFormat() ? 3 : 2;
+    unsigned OpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField;
+    auto *TypeNode = cast<MDNode>(getNode()->getOperand(OpIndex));
+    return TBAAStructTypeNode(TypeNode);
+  }
+
   /// Get this TBAAStructTypeNode's field in the type DAG with
   /// given offset. Update the offset to be relative to the field type.
-  TBAAStructTypeNode getParent(uint64_t &Offset) const {
+  TBAAStructTypeNode getField(uint64_t &Offset) const {
+    bool NewFormat = isNewFormat();
+    if (NewFormat) {
+      // New-format root and scalar type nodes have no fields.
+      if (Node->getNumOperands() < 6)
+        return TBAAStructTypeNode();
+    } else {
       // Parent can be omitted for the root node.
       if (Node->getNumOperands() < 2)
         return TBAAStructTypeNode();
 
       // Fast path for a scalar type node and a struct type node with a single
       // field.
       if (Node->getNumOperands() <= 3) {
         uint64_t Cur = Node->getNumOperands() == 2
                            ? 0
                            : mdconst::extract<ConstantInt>(Node->getOperand(2))
                                  ->getZExtValue();
         Offset -= Cur;
         MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
         if (!P)
           return TBAAStructTypeNode();
         return TBAAStructTypeNode(P);
       }
+    }
 
     // Assume the offsets are in order. We return the previous field if
     // the current offset is bigger than the given offset.
+    unsigned FirstFieldOpNo = NewFormat ? 3 : 1;
+    unsigned NumOpsPerField = NewFormat ? 3 : 2;
     unsigned TheIdx = 0;
-    for (unsigned Idx = 1; Idx < Node->getNumOperands(); Idx += 2) {
+    for (unsigned Idx = FirstFieldOpNo; Idx < Node->getNumOperands();
+         Idx += NumOpsPerField) {
       uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(Idx + 1))
                          ->getZExtValue();
       if (Cur > Offset) {
-        assert(Idx >= 3 &&
-               "TBAAStructTypeNode::getParent should have an offset match!");
-        TheIdx = Idx - 2;
+        assert(Idx >= FirstFieldOpNo + NumOpsPerField &&
+               "TBAAStructTypeNode::getField should have an offset match!");
+        TheIdx = Idx - NumOpsPerField;
         break;
       }
     }
     // Move along the last field.
     if (TheIdx == 0)
-      TheIdx = Node->getNumOperands() - 2;
+      TheIdx = Node->getNumOperands() - NumOpsPerField;
     uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(TheIdx + 1))
                        ->getZExtValue();
     Offset -= Cur;
     MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx));
     if (!P)
       return TBAAStructTypeNode();
     return TBAAStructTypeNode(P);
   }
if (!isStructPathTBAA(this)) {
     if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) {
       if (Tag1->getString() == "vtable pointer")
         return true;
     }
     return false;
   }
 
   // For struct-path aware TBAA, we use the access type of the tag.
-  if (getNumOperands() < 2)
-    return false;
-  MDNode *Tag = cast_or_null<MDNode>(getOperand(1));
-  if (!Tag)
-    return false;
-  if (MDString *Tag1 = dyn_cast<MDString>(Tag->getOperand(0))) {
-    if (Tag1->getString() == "vtable pointer")
+  TBAAStructTagNode Tag(this);
+  TBAAStructTypeNode AccessType(Tag.getAccessType());
+  if(auto *Id = dyn_cast<MDString>(AccessType.getId()))
+    if (Id->getString() == "vtable pointer")
       return true;
-  }
   return false;
 }
 
 static bool matchAccessTags(const MDNode *A, const MDNode *B,
                             const MDNode **GenericTag = nullptr);
 
 MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) {
   const MDNode *GenericTag;
void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const {
 
   if (Merge)
     N.NoAlias =
         MDNode::intersect(N.NoAlias, getMetadata(LLVMContext::MD_noalias));
   else
     N.NoAlias = getMetadata(LLVMContext::MD_noalias);
 }
 
-static bool findAccessType(TBAAStructTagNode BaseTag,
-                           const MDNode *AccessTypeNode,
-                           uint64_t &OffsetInBase) {
-  // Start from the base type, follow the edge with the correct offset in
-  // the type DAG and adjust the offset until we reach the access type or
-  // until we reach a root node.
-  TBAAStructTypeNode BaseType(BaseTag.getBaseType());
-  OffsetInBase = BaseTag.getOffset();
-
-  while (const MDNode *BaseTypeNode = BaseType.getNode()) {
-    if (BaseTypeNode == AccessTypeNode)
-      return true;
-
-    // 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));
+  auto *OffsetNode = ConstantAsMetadata::get(ConstantInt::get(Int64, 0));
+
+  if (TBAAStructTypeNode(AccessType).isNewFormat()) {
+    // TODO: Take access ranges into account when matching access tags and
+    // fix this code to generate actual access sizes for generic tags.
+    uint64_t AccessSize = UINT64_MAX;
+    auto *SizeNode =
+        ConstantAsMetadata::get(ConstantInt::get(Int64, AccessSize));
     Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
-                     const_cast<MDNode*>(AccessType), ImmutabilityFlag};
+                       const_cast<MDNode*>(AccessType),
+                       OffsetNode, SizeNode};
     return MDNode::get(AccessType->getContext(), Ops);
   }
 
+  Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
+                     const_cast<MDNode*>(AccessType),
+                     OffsetNode};
+  return MDNode::get(AccessType->getContext(), Ops);
+}
+
+static bool hasField(TBAAStructTypeNode BaseType,
+                     TBAAStructTypeNode FieldType) {
+  for (unsigned I = 0, E = BaseType.getNumFields(); I != E; ++I) {
+    TBAAStructTypeNode T = BaseType.getFieldType(I);
+    if (T == FieldType || hasField(T, FieldType))
+      return true;
+  }
+  return false;
+}
+
+/// Return true if for two given accesses, one of the accessed objects may be a
+/// subobject of the other. The \p BaseTag and \p SubobjectTag parameters
+/// describe the accesses to the base object and the subobject respectively.
+/// \p CommonType must be the metadata node describing the common type of the
+/// accessed objects. On return, \p MayAlias is set to true iff these accesses
+/// may alias and \p Generic, if not null, points to the most generic access
+/// tag for the given two.
+static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag,
+                                     TBAAStructTagNode SubobjectTag,
+                                     const MDNode *CommonType,
+                                     const MDNode **GenericTag,
+                                     bool &MayAlias) {
+  // If the base object is of the least common type, then this may be an access
+  // to its subobject.
+  if (BaseTag.getAccessType() == BaseTag.getBaseType() &&
+      BaseTag.getAccessType() == CommonType) {
+    if (GenericTag)
+      *GenericTag = createAccessTag(CommonType);
+    MayAlias = true;
+    return true;
+  }
+
+  // If the access to the base object is through a field of the subobject's
+  // type, then this may be an access to that field. To check for that we start
+  // from the base type, follow the edge with the correct offset in the type DAG
+  // and adjust the offset until we reach the field type or until we reach the
+  // access type.
+  bool NewFormat = BaseTag.isNewFormat();
+  TBAAStructTypeNode BaseType(BaseTag.getBaseType());
+  uint64_t OffsetInBase = BaseTag.getOffset();
+
+  for (;;) {
+    // In the old format there is no distinction between fields and parent
+    // types, so in this case we consider all nodes up to the root.
+    if (!BaseType.getNode()) {
+      assert(!NewFormat && "Did not see access type in access path!");
+      break;
+    }
+
+    if (BaseType.getNode() == SubobjectTag.getBaseType()) {
+      bool SameMemberAccess = OffsetInBase == SubobjectTag.getOffset();
+      if (GenericTag) {
+        *GenericTag = SameMemberAccess ? SubobjectTag.getNode() :
+                                         createAccessTag(CommonType);
+      }
+      MayAlias = SameMemberAccess;
+      return true;
+    }
+
+    // With new-format nodes we stop at the access type.
+    if (NewFormat && BaseType.getNode() == BaseTag.getAccessType())
+      break;
+
+    // Follow the edge with the correct offset. Offset will be adjusted to
+    // be relative to the field type.
+    BaseType = BaseType.getField(OffsetInBase);
+  }
+
+  // If the base object has a direct or indirect field of the subobject's type,
+  // then this may be an access to that field. We need this to check now that
+  // we support aggreagtes as access types.
+  if (NewFormat) {
+    // TBAAStructTypeNode BaseAccessType(BaseTag.getAccessType());
+    TBAAStructTypeNode FieldType(SubobjectTag.getBaseType());
+    if (hasField(BaseType, FieldType)) {
+      if (GenericTag)
+        *GenericTag = createAccessTag(CommonType);
+      MayAlias = true;
+      return true;
+    }
+  }
+
+  return false;
+}
+
 /// matchTags - Return true if the given couple of accesses are allowed to
 /// overlap. If \arg GenericTag is not null, then on return it points to the
 /// most generic access descriptor for the given two.
 static bool matchAccessTags(const MDNode *A, const MDNode *B,
                             const MDNode **GenericTag) {
   if (A == B) {
     if (GenericTag)
       *GenericTag = A;
static bool matchAccessTags(const MDNode *A, const MDNode *B,
   // 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());
 
-  // TODO: We need to check if AccessType of TagA encloses AccessType of
-  // TagB to support aggregate AccessType. If yes, return true.
-
-  // Climb the type DAG from base type of A to see if we reach base type of B.
-  uint64_t OffsetA;
-  if (findAccessType(TagA, TagB.getBaseType(), OffsetA)) {
-    bool SameMemberAccess = OffsetA == TagB.getOffset();
+  // If the final access types have different roots, they're part of different
+  // potentially unrelated type systems, so we must be conservative.
+  if (!CommonType) {
     if (GenericTag)
-      *GenericTag = SameMemberAccess ? TagB.getNode() :
-                                       createAccessTag(CommonType);
-    return SameMemberAccess;
+      *GenericTag = nullptr;
+    return true;
   }
 
-  // Climb the type DAG from base type of B to see if we reach base type of A.
-  uint64_t OffsetB;
-  if (findAccessType(TagB, TagA.getBaseType(), OffsetB)) {
-    bool SameMemberAccess = OffsetB == TagA.getOffset();
-    if (GenericTag)
-      *GenericTag = SameMemberAccess ? TagA.getNode() :
-                                       createAccessTag(CommonType);
-    return SameMemberAccess;
-  }
+  // If one of the accessed objects may be a subobject of the other, then such
+  // accesses may alias.
+  bool MayAlias;
+  if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB,
+                               CommonType, GenericTag, MayAlias) ||
+      mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA,
+                               CommonType, GenericTag, MayAlias))
+    return MayAlias;
 
+  // Otherwise, we've proved there's no alias.
   if (GenericTag)
     *GenericTag = createAccessTag(CommonType);
-
-  // 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
 /// access represented by tag B.
 bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
   return matchAccessTags(A, B);
 }

llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/aggregates.ll

+; RUN: opt < %s -tbaa -basicaa -aa-eval -evaluate-aa-metadata \
+; RUN:     -print-no-aliases -print-may-aliases -disable-output 2>&1 | \
+; RUN:     FileCheck %s
+; RUN: opt < %s -tbaa -basicaa -gvn -S | FileCheck %s --check-prefix=OPT
+;
+; Check that TBAA handles access tags with aggregate final access types
+; correctly.
+
+%A = type { i32 }  ; struct A { int i; };
+%B = type { %A }   ; struct B { A a; };
+%C = type { %B }   ; struct C { B b; };
+%D = type { i16 }  ; struct D { short s; };
+
+; int vs. A::i  =>  MayAlias.
+define i32 @f1(i32* %i, %A* %a) {
+entry:
+; CHECK-LABEL: f1
+; CHECK: MayAlias: store i32 7, {{.*}} <-> store i32 5,
+; OPT-LABEL: f1
+; OPT: store i32 5,
+; OPT: store i32 7,
+; OPT: %[[RET:.*]] = load i32,
+; OPT: ret i32 %[[RET]]
+  store i32 5, i32* %i, align 4, !tbaa !3  ; TAG_int
+  %A_i = getelementptr inbounds %A, %A* %a, i64 0, i32 0
+  store i32 7, i32* %A_i, align 4, !tbaa !5  ; TAG_A_i
+  %0 = load i32, i32* %i, align 4, !tbaa !3  ; TAG_int
+  ret i32 %0
+}
+
+; int vs. B::a  =>  MayAlias.
+define i32 @f2(i32* %i, %B* %b) {
+entry:
+; CHECK-LABEL: f2
+; CHECK: MayAlias: store i32 7, {{.*}} <-> store i32 5,
+; OPT-LABEL: f2
+; OPT: store i32 5,
+; OPT: store i32 7,
+; OPT: %[[RET:.*]] = load i32,
+; OPT: ret i32 %[[RET]]
+  store i32 5, i32* %i, align 4, !tbaa !3  ; TAG_int
+  %B_a = getelementptr inbounds %B, %B* %b, i64 0, i32 0, i32 0
+  store i32 7, i32* %B_a, align 4, !tbaa !7  ; TAG_B_a
+  %0 = load i32, i32* %i, align 4, !tbaa !3  ; TAG_int
+  ret i32 %0
+}
+
+; int vs. C::b  =>  MayAlias.
+define i32 @f3(i32* %i, %C* %c) {
+entry:
+; CHECK-LABEL: f3
+; CHECK: MayAlias: store i32 7, {{.*}} <-> store i32 5,
+; OPT-LABEL: f3
+; OPT: store i32 5,
+; OPT: store i32 7,
+; OPT: %[[RET:.*]] = load i32,
+; OPT: ret i32 %[[RET]]
+  store i32 5, i32* %i, align 4, !tbaa !3  ; TAG_int
+  %C_b = getelementptr inbounds %C, %C* %c, i64 0, i32 0, i32 0, i32 0
+  store i32 7, i32* %C_b, align 4, !tbaa !9  ; TAG_C_b
+  %0 = load i32, i32* %i, align 4, !tbaa !3  ; TAG_int
+  ret i32 %0
+}
+
+; A vs. C::b  =>  MayAlias.
+define i32 @f4(%A* %a, %C* %c) {
+entry:
+; CHECK-LABEL: f4
+; CHECK: MayAlias: store i32 7, {{.*}} <-> store i32 5,
+; OPT-LABEL: f4
+; OPT: store i32 5,
+; OPT: store i32 7,
+; OPT: %[[RET:.*]] = load i32,
+; OPT: ret i32 %[[RET]]
+  %ap = getelementptr inbounds %A, %A* %a, i64 0, i32 0
+  store i32 5, i32* %ap, align 4, !tbaa !10   ; TAG_A
+  %C_b = getelementptr inbounds %C, %C* %c, i64 0, i32 0, i32 0, i32 0
+  store i32 7, i32* %C_b, align 4, !tbaa !9   ; TAG_C_b
+  %0 = load i32, i32* %ap, align 4, !tbaa !10  ; TAG_A
+  ret i32 %0
+}
+
+; short vs. C::b  =>  NoAlias.
+define i32 @f5(i32* %i, %C* %c) {
+entry:
+; CHECK-LABEL: f5
+; CHECK: NoAlias: store i32 7, {{.*}} <-> store i32 5,
+; OPT-LABEL: f5
+; OPT: store i32 5,
+; OPT: store i32 7,
+; OPT: ret i32 5
+  store i32 5, i32* %i, align 4, !tbaa !12  ; TAG_short
+  %C_b = getelementptr inbounds %C, %C* %c, i64 0, i32 0, i32 0, i32 0
+  store i32 7, i32* %C_b, align 4, !tbaa !9  ; TAG_C_b
+  %0 = load i32, i32* %i, align 4, !tbaa !12  ; TAG_short
+  ret i32 %0
+}
+
+; C vs. D  =>  NoAlias.
+define i32 @f6(%C* %c, %D* %d) {
+entry:
+; CHECK-LABEL: f6
+; CHECK: NoAlias: store i16 7, {{.*}} <-> store i32 5,
+; OPT-LABEL: f6
+; OPT: store i32 5,
+; OPT: store i16 7,
+; OPT: ret i32 5
+  %cp = getelementptr inbounds %C, %C* %c, i64 0, i32 0, i32 0, i32 0
+  store i32 5, i32* %cp, align 4, !tbaa !13  ; TAG_C
+  %dp = getelementptr inbounds %D, %D* %d, i64 0, i32 0
+  store i16 7, i16* %dp, align 4, !tbaa !15  ; TAG_D
+  %0 = load i32, i32* %cp, align 4, !tbaa !13  ; TAG_C
+  ret i32 %0
+}
+
+!0 = !{!"root"}
+!1 = !{!0, i64 1, !"char"}
+!2 = !{!1, i64 4, !"int"}
+!3 = !{!2, !2, i64 0, i64 4}  ; TAG_int
+
+!4 = !{!1, i64 4, !"A", !2, i64 0, i64 4}
+!5 = !{!4, !2, i64 0, i64 4}  ; TAG_A_i
+
+!6 = !{!1, i64 4, !"B", !4, i64 0, i64 4}
+!7 = !{!6, !4, i64 0, i64 4}  ; TAG_B_a
+
+!8 = !{!1, i64 4, !"C", !6, i64 0, i64 4}
+!9 = !{!8, !6, i64 0, i64 4}  ; TAG_C_b
+
+!10 = !{!4, !4, i64 0, i64 4}  ; TAG_A
+
+!11 = !{!1, i64 2, !"short"}
+!12 = !{!11, !11, i64 0, i64 2}  ; TAG_short
+
+!13 = !{!8, !8, i64 0, i64 4}  ; TAG_C
+
+!14 = !{!4, i64 2, !"D", !11, i64 0, i64 2}
+!15 = !{!14, !14, i64 0, i64 2}  ; TAG_D

llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/tbaa-path-new.ll

+; RUN: opt < %s -tbaa -basicaa -aa-eval -evaluate-aa-metadata -print-no-aliases -print-may-aliases -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -tbaa -basicaa -gvn -S | FileCheck %s --check-prefix=OPT
+; Generated from clang/test/CodeGen/tbaa.cpp with "-O1 -new-struct-path-tbaa".
+
+%struct.StructA = type { i16, i32, i16, i32 }
+%struct.StructB = type { i16, %struct.StructA, i32 }
+%struct.StructS = type { i16, i32 }
+%struct.StructS2 = type { i16, i32 }
+%struct.StructC = type { i16, %struct.StructB, i32 }
+%struct.StructD = type { i16, %struct.StructB, i32, i8 }
+
+; uint32_t g(uint32_t *s, StructA *A, uint64_t count) {
+;   *s = 1;
+;   A->f32 = 4;
+;   return *s;
+; }
+;
+define i32 @_Z1gPjP7StructAy(i32* nocapture %s, %struct.StructA* nocapture %A, i64 %count) {
+entry:
+; CHECK-LABEL: Z1gPjP7StructAy
+; CHECK: MayAlias: store i32 4, {{.*}} <-> store i32 1,
+; OPT-LABEL: _Z1gPjP7StructAy
+; OPT: store i32 1,
+; OPT: store i32 4,
+; OPT: %[[RET:.*]] = load i32,
+; OPT: ret i32 %[[RET]]
+  store i32 1, i32* %s, align 4, !tbaa !2
+  %f32 = getelementptr inbounds %struct.StructA, %struct.StructA* %A, i64 0, i32 1
+  store i32 4, i32* %f32, align 4, !tbaa !6
+  %0 = load i32, i32* %s, align 4, !tbaa !2
+  ret i32 %0
+}
+
+; uint32_t g2(uint32_t *s, StructA *A, uint64_t count) {
+;   *s = 1;
+;   A->f16 = 4;
+;   return *s;
+; }
+;
+define i32 @_Z2g2PjP7StructAy(i32* nocapture %s, %struct.StructA* nocapture %A, i64 %count) {
+entry:
+; CHECK-LABEL: _Z2g2PjP7StructAy
+; CHECK: NoAlias: store i16 4, {{.*}} <-> store i32 1,
+; OPT-LABEL: _Z2g2PjP7StructAy
+; OPT: store i32 1,
+; OPT: store i16 4,
+; Remove a load and propagate the value from store.
+; OPT: ret i32 1
+  store i32 1, i32* %s, align 4, !tbaa !2
+  %f16 = getelementptr inbounds %struct.StructA, %struct.StructA* %A, i64 0, i32 0
+  store i16 4, i16* %f16, align 4, !tbaa !9
+  ret i32 1
+}
+
+; uint32_t g3(StructA *A, StructB *B, uint64_t count) {
+;   A->f32 = 1;
+;   B->a.f32 = 4;
+;   return A->f32;
+; }
+;
+define i32 @_Z2g3P7StructAP7StructBy(%struct.StructA* nocapture %A, %struct.StructB* nocapture %B, i64 %count) {
+entry:
+; CHECK-LABEL: _Z2g3P7StructAP7StructBy
+; CHECK: MayAlias: store i32 4, {{.*}} <-> store i32 1,
+; OPT-LABEL: _Z2g3P7StructAP7StructBy
+; OPT: store i32 1
+; OPT: store i32 4
+; OPT: %[[RET:.*]] = load i32,
+; OPT: ret i32 %[[RET]]
+  %f32 = getelementptr inbounds %struct.StructA, %struct.StructA* %A, i64 0, i32 1
+  store i32 1, i32* %f32, align 4, !tbaa !6
+  %f321 = getelementptr inbounds %struct.StructB, %struct.StructB* %B, i64 0, i32 1, i32 1
+  store i32 4, i32* %f321, align 4, !tbaa !10
+  %0 = load i32, i32* %f32, align 4, !tbaa !6
+  ret i32 %0
+}
+
+; uint32_t g4(StructA *A, StructB *B, uint64_t count) {
+;   A->f32 = 1;
+;   B->a.f16 = 4;
+;   return A->f32;
+; }
+;
+define i32 @_Z2g4P7StructAP7StructBy(%struct.StructA* nocapture %A, %struct.StructB* nocapture %B, i64 %count) {
+entry:
+; CHECK-LABEL: _Z2g4P7StructAP7StructBy
+; CHECK: NoAlias: store i16 4, {{.*}} <-> store i32 1,
+; OPT-LABEL: _Z2g4P7StructAP7StructBy
+; OPT: store i32 1,
+; OPT: store i16 4,
+; Remove a load and propagate the value from store.
+; OPT: ret i32 1
+  %f32 = getelementptr inbounds %struct.StructA, %struct.StructA* %A, i64 0, i32 1
+  store i32 1, i32* %f32, align 4, !tbaa !6
+  %f16 = getelementptr inbounds %struct.StructB, %struct.StructB* %B, i64 0, i32 1, i32 0
+  store i16 4, i16* %f16, align 4, !tbaa !12
+  ret i32 1
+}
+
+; uint32_t g5(StructA *A, StructB *B, uint64_t count) {
+;   A->f32 = 1;
+;   B->f32 = 4;
+;   return A->f32;
+; }
+;
+define i32 @_Z2g5P7StructAP7StructBy(%struct.StructA* nocapture %A, %struct.StructB* nocapture %B, i64 %count) {
+entry:
+; CHECK-LABEL: _Z2g5P7StructAP7StructBy
+; CHECK: NoAlias: store i32 4, {{.*}} <-> store i32 1,
+; OPT-LABEL: _Z2g5P7StructAP7StructBy
+; OPT: store i32 1,
+; OPT: store i32 4,
+; Remove a load and propagate the value from store.
+; OPT: ret i32 1
+  %f32 = getelementptr inbounds %struct.StructA, %struct.StructA* %A, i64 0, i32 1
+  store i32 1, i32* %f32, align 4, !tbaa !6
+  %f321 = getelementptr inbounds %struct.StructB, %struct.StructB* %B, i64 0, i32 2
+  store i32 4, i32* %f321, align 4, !tbaa !13
+  ret i32 1
+}
+
+; uint32_t g6(StructA *A, StructB *B, uint64_t count) {
+;   A->f32 = 1;
+;   B->a.f32_2 = 4;
+;   return A->f32;
+; }
+;
+define i32 @_Z2g6P7StructAP7StructBy(%struct.StructA* nocapture %A, %struct.StructB* nocapture %B, i64 %count) {
+entry:
+; CHECK-LABEL: _Z2g6P7StructAP7StructBy
+; CHECK: NoAlias: store i32 4, {{.*}} <-> store i32 1,
+; OPT-LABEL: _Z2g6P7StructAP7StructBy
+; OPT: store i32 1,
+; OPT: store i32 4,
+; Remove a load and propagate the value from store.
+; OPT: ret i32 1
+  %f32 = getelementptr inbounds %struct.StructA, %struct.StructA* %A, i64 0, i32 1
+  store i32 1, i32* %f32, align 4, !tbaa !6
+  %f32_2 = getelementptr inbounds %struct.StructB, %struct.StructB* %B, i64 0, i32 1, i32 3
+  store i32 4, i32* %f32_2, align 4, !tbaa !14
+  ret i32 1
+}
+
+; uint32_t g7(StructA *A, StructS *S, uint64_t count) {
+;   A->f32 = 1;
+;   S->f32 = 4;
+;   return A->f32;
+; }
+;
+define i32 @_Z2g7P7StructAP7StructSy(%struct.StructA* nocapture %A, %struct.StructS* nocapture %S, i64 %count) {
+entry:
+; CHECK-LABEL: _Z2g7P7StructAP7StructSy
+; CHECK: NoAlias: store i32 4, {{.*}} <-> store i32 1,
+; OPT-LABEL: _Z2g7P7StructAP7StructSy
+; OPT: store i32 1,
+; OPT: store i32 4,
+; Remove a load and propagate the value from store.
+; OPT: ret i32 1
+  %f32 = getelementptr inbounds %struct.StructA, %struct.StructA* %A, i64 0, i32 1
+  store i32 1, i32* %f32, align 4, !tbaa !6
+  %f321 = getelementptr inbounds %struct.StructS, %struct.StructS* %S, i64 0, i32 1
+  store i32 4, i32* %f321, align 4, !tbaa !15
+  ret i32 1
+}
+
+; uint32_t g8(StructA *A, StructS *S, uint64_t count) {
+;   A->f32 = 1;
+;   S->f16 = 4;
+;   return A->f32;
+; }
+;
+define i32 @_Z2g8P7StructAP7StructSy(%struct.StructA* nocapture %A, %struct.StructS* nocapture %S, i64 %count) {
+entry:
+; CHECK-LABEL: _Z2g8P7StructAP7StructSy
+; CHECK: NoAlias: store i16 4, {{.*}} <-> store i32 1,
+; OPT-LABEL: _Z2g8P7StructAP7StructSy
+; OPT: store i32 1,
+; OPT: store i16 4,
+; Remove a load and propagate the value from store.
+; OPT: ret i32 1
+  %f32 = getelementptr inbounds %struct.StructA, %struct.StructA* %A, i64 0, i32 1
+  store i32 1, i32* %f32, align 4, !tbaa !6
+  %f16 = getelementptr inbounds %struct.StructS, %struct.StructS* %S, i64 0, i32 0
+  store i16 4, i16* %f16, align 4, !tbaa !17
+  ret i32 1
+}
+
+; uint32_t g9(StructS *S, StructS2 *S2, uint64_t count) {
+;   S->f32 = 1;
+;   S2->f32 = 4;
+;   return S->f32;
+; }
+;
+define i32 @_Z2g9P7StructSP8StructS2y(%struct.StructS* nocapture %S, %struct.StructS2* nocapture %S2, i64 %count) {
+entry:
+; CHECK-LABEL: _Z2g9P7StructSP8StructS2y
+; CHECK: NoAlias: store i32 4, {{.*}} <-> store i32 1,
+; OPT-LABEL: _Z2g9P7StructSP8StructS2y
+; OPT: store i32 1,
+; OPT: store i32 4,
+; Remove a load and propagate the value from store.
+; OPT: ret i32 1
+  %f32 = getelementptr inbounds %struct.StructS, %struct.StructS* %S, i64 0, i32 1
+  store i32 1, i32* %f32, align 4, !tbaa !15
+  %f321 = getelementptr inbounds %struct.StructS2, %struct.StructS2* %S2, i64 0, i32 1
+  store i32 4, i32* %f321, align 4, !tbaa !18
+  ret i32 1
+}
+
+; uint32_t g10(StructS *S, StructS2 *S2, uint64_t count) {
+;   S->f32 = 1;
+;   S2->f16 = 4;
+;   return S->f32;
+; }
+;
+define i32 @_Z3g10P7StructSP8StructS2y(%struct.StructS* nocapture %S, %struct.StructS2* nocapture %S2, i64 %count) {
+entry:
+; CHECK-LABEL: _Z3g10P7StructSP8StructS2y
+; CHECK: NoAlias: store i16 4, {{.*}} <-> store i32 1,
+; OPT-LABEL: _Z3g10P7StructSP8StructS2y
+; OPT: store i32 1,
+; OPT: store i16 4,
+; Remove a load and propagate the value from store.
+; OPT: ret i32 1
+  %f32 = getelementptr inbounds %struct.StructS, %struct.StructS* %S, i64 0, i32 1
+  store i32 1, i32* %f32, align 4, !tbaa !15
+  %f16 = getelementptr inbounds %struct.StructS2, %struct.StructS2* %S2, i64 0, i32 0
+  store i16 4, i16* %f16, align 4, !tbaa !20
+  ret i32 1
+}
+
+; uint32_t g11(StructC *C, StructD *D, uint64_t count) {
+;   C->b.a.f32 = 1;
+;   D->b.a.f32 = 4;
+;   return C->b.a.f32;
+; }
+;
+define i32 @_Z3g11P7StructCP7StructDy(%struct.StructC* nocapture %C, %struct.StructD* nocapture %D, i64 %count) {
+entry:
+; CHECK-LABEL: _Z3g11P7StructCP7StructDy
+; CHECK: NoAlias: store i32 4, {{.*}} <-> store i32 1,
+; OPT-LABEL: _Z3g11P7StructCP7StructDy
+; OPT: store i32 1,
+; OPT: store i32 4,
+; Remove a load and propagate the value from store.
+; OPT: ret i32 1
+  %f32 = getelementptr inbounds %struct.StructC, %struct.StructC* %C, i64 0, i32 1, i32 1, i32 1
+  store i32 1, i32* %f32, align 4, !tbaa !21
+  %f323 = getelementptr inbounds %struct.StructD, %struct.StructD* %D, i64 0, i32 1, i32 1, i32 1
+  store i32 4, i32* %f323, align 4, !tbaa !23
+  ret i32 1
+}
+
+; uint32_t g12(StructC *C, StructD *D, uint64_t count) {
+;   StructB *b1 = &(C->b);
+;   StructB *b2 = &(D->b);
+;   // b1, b2 have different context.
+;   b1->a.f32 = 1;
+;   b2->a.f32 = 4;
+;   return b1->a.f32;
+; }
+;
+define i32 @_Z3g12P7StructCP7StructDy(%struct.StructC* nocapture %C, %struct.StructD* nocapture %D, i64 %count) {
+entry:
+; CHECK-LABEL: _Z3g12P7StructCP7StructDy
+; CHECK: MayAlias: store i32 4, {{.*}} <-> store i32 1,
+; OPT-LABEL: _Z3g12P7StructCP7StructDy
+; OPT: store i32 1,
+; OPT: store i32 4,
+; OPT: %[[RET:.*]] = load i32,
+; OPT: ret i32 %[[RET]]
+  %f32 = getelementptr inbounds %struct.StructC, %struct.StructC* %C, i64 0, i32 1, i32 1, i32 1
+  store i32 1, i32* %f32, align 4, !tbaa !10
+  %f325 = getelementptr inbounds %struct.StructD, %struct.StructD* %D, i64 0, i32 1, i32 1, i32 1
+  store i32 4, i32* %f325, align 4, !tbaa !10
+  %0 = load i32, i32* %f32, align 4, !tbaa !10
+  ret i32 %0
+}
+
+!2 = !{!3, !3, i64 0, i64 4}
+!3 = !{!4, i64 4, !"int"}
+!4 = !{!5, i64 1, !"omnipotent char"}
+!5 = !{!"Simple C++ TBAA"}
+!6 = !{!7, !3, i64 4, i64 4}
+!7 = !{!4, i64 16, !"_ZTS7StructA", !8, i64 0, i64 2, !3, i64 4, i64 4, !8, i64 8, i64 2, !3, i64 12, i64 4}
+!8 = !{!4, i64 2, !"short"}
+!9 = !{!7, !8, i64 0, i64 2}
+!10 = !{!11, !3, i64 8, i64 4}
+!11 = !{!4, i64 24, !"_ZTS7StructB", !8, i64 0, i64 2, !7, i64 4, i64 16, !3, i64 20, i64 4}
+!12 = !{!11, !8, i64 4, i64 2}
+!13 = !{!11, !3, i64 20, i64 4}
+!14 = !{!11, !3, i64 16, i64 4}
+!15 = !{!16, !3, i64 4, i64 4}
+!16 = !{!4, i64 8, !"_ZTS7StructS", !8, i64 0, i64 2, !3, i64 4, i64 4}
+!17 = !{!16, !8, i64 0, i64 2}
+!18 = !{!19, !3, i64 4, i64 4}
+!19 = !{!4, i64 8, !"_ZTS8StructS2", !8, i64 0, i64 2, !3, i64 4, i64 4}
+!20 = !{!19, !8, i64 0, i64 2}
+!21 = !{!22, !3, i64 12, i64 4}
+!22 = !{!4, i64 32, !"_ZTS7StructC", !8, i64 0, i64 2, !11, i64 4, i64 24, !3, i64 28, i64 4}
+!23 = !{!24, !3, i64 12, i64 4}
+!24 = !{!4, i64 36, !"_ZTS7StructD", !8, i64 0, i64 2, !11, i64 4, i64 24, !3, i64 28, i64 4, !4, i64 32, i64 1}
+!25 = !{!26, !4, i64 1, i64 1}
+!26 = !{!4, i64 3, !"_ZTS4five", !4, i64 0, i64 1, !3, i64 1, i64 4, !4, i64 1, i64 1, !4, i64 2, i64 1}
+!27 = !{!28, !4, i64 4, i64 1}
+!28 = !{!4, i64 6, !"_ZTS3six", !4, i64 0, i64 1, !3, i64 4, i64 4, !4, i64 4, i64 1, !4, i64 5, i64 1}