Index: llvm/trunk/lib/Analysis/TypeBasedAliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/TypeBasedAliasAnalysis.cpp +++ llvm/trunk/lib/Analysis/TypeBasedAliasAnalysis.cpp @@ -104,21 +104,6 @@ // 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" @@ -146,6 +131,17 @@ 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(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. @@ -160,8 +156,15 @@ /// 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 getParent() const { + if (isNewFormat()) + return TBAANodeImpl(cast(Node->getOperand(0))); + if (Node->getNumOperands() < 2) return TBAANodeImpl(); MDNodeTy *P = dyn_cast_or_null(Node->getOperand(1)); @@ -196,7 +199,7 @@ /// information is encoded in its operands. template class TBAAStructTagNodeImpl { - /// This node should be created with createTBAAStructTagNode. + /// This node should be created with createTBAAAccessTag(). MDNodeTy *Node; public: @@ -205,6 +208,17 @@ /// 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(AccessType).isNewFormat()) + return false; + return true; + } + MDNodeTy *getBaseType() const { return dyn_cast_or_null(Node->getOperand(0)); } @@ -217,13 +231,20 @@ return mdconst::extract(Node->getOperand(2))->getZExtValue(); } + uint64_t getSize() const { + if (!isNewFormat()) + return UINT64_MAX; + return mdconst::extract(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(Node->getOperand(3)); + ConstantInt *CI = mdconst::dyn_extract(Node->getOperand(OpNo)); if (!CI) return false; return CI->getValue()[0]; @@ -241,7 +262,7 @@ /// 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: @@ -251,43 +272,80 @@ /// 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(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 { - // 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(Node->getOperand(2)) - ->getZExtValue(); - Offset -= Cur; - MDNode *P = dyn_cast_or_null(Node->getOperand(1)); - if (!P) + 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(); - return TBAAStructTypeNode(P); + + // 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(Node->getOperand(2)) + ->getZExtValue(); + Offset -= Cur; + MDNode *P = dyn_cast_or_null(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(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(Node->getOperand(TheIdx + 1)) ->getZExtValue(); Offset -= Cur; @@ -403,15 +461,11 @@ } // For struct-path aware TBAA, we use the access type of the tag. - if (getNumOperands() < 2) - return false; - MDNode *Tag = cast_or_null(getOperand(1)); - if (!Tag) - return false; - if (MDString *Tag1 = dyn_cast(Tag->getOperand(0))) { - if (Tag1->getString() == "vtable pointer") + TBAAStructTagNode Tag(this); + TBAAStructTypeNode AccessType(Tag.getAccessType()); + if(auto *Id = dyn_cast(AccessType.getId())) + if (Id->getString() == "vtable pointer") return true; - } return false; } @@ -485,26 +539,6 @@ 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. @@ -512,12 +546,111 @@ 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(AccessType), + const_cast(AccessType), + OffsetNode, SizeNode}; + return MDNode::get(AccessType->getContext(), Ops); + } + Metadata *Ops[] = {const_cast(AccessType), - const_cast(AccessType), ImmutabilityFlag}; + const_cast(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. @@ -545,38 +678,26 @@ 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; } Index: llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/aggregates.ll =================================================================== --- llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/aggregates.ll +++ llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/aggregates.ll @@ -0,0 +1,138 @@ +; 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 Index: llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/tbaa-path-new.ll =================================================================== --- llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/tbaa-path-new.ll +++ llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/tbaa-path-new.ll @@ -0,0 +1,306 @@ +; 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}