Index: llvm/trunk/lib/IR/Verifier.cpp =================================================================== --- llvm/trunk/lib/IR/Verifier.cpp +++ llvm/trunk/lib/IR/Verifier.cpp @@ -187,6 +187,14 @@ *OS << *C; } + void Write(const APInt *AI) { + if (!AI) + return; + *OS << *AI << '\n'; + } + + void Write(const unsigned i) { *OS << i << '\n'; } + template void Write(ArrayRef Vs) { for (const T &V : Vs) Write(V); @@ -285,6 +293,17 @@ // constant expressions, we can arrive at a particular user many times. SmallPtrSet GlobalValueVisited; + /// Cache of TBAA base nodes that have already been visited. This cachce maps + /// a node that has been visited to a pair (IsInvalid, BitWidth) where + /// + /// \c IsInvalid is true iff the node is invalid. + /// \c BitWidth, if non-zero, is the bitwidth of the integer used to denoting + /// the offset of the access. If zero, only a zero offset is allowed. + /// + /// \c BitWidth has no meaning if \c IsInvalid is true. + typedef std::pair TBAABaseNodeSummary; + DenseMap TBAABaseNodes; + void checkAtomicMemAccessSize(Type *Ty, const Instruction *I); public: @@ -393,6 +412,14 @@ void visitDereferenceableMetadata(Instruction &I, MDNode *MD); void visitTBAAMetadata(Instruction &I, MDNode *MD); + /// \name Helper functions used by \c visitTBAAMetadata. + /// @{ + MDNode *getFieldNodeFromTBAABaseNode(Instruction &I, MDNode *BaseNode, + APInt &Offset); + TBAABaseNodeSummary verifyTBAABaseNode(Instruction &I, MDNode *BaseNode); + TBAABaseNodeSummary verifyTBAABaseNodeImpl(Instruction &I, MDNode *BaseNode); + /// @} + template bool isValidMetadataArray(const MDTuple &N); #define HANDLE_SPECIALIZED_MDNODE_LEAF(CLASS) void visit##CLASS(const CLASS &N); #include "llvm/IR/Metadata.def" @@ -3657,6 +3684,174 @@ "dereferenceable_or_null metadata value must be an i64!", &I); } +/// Verify that \p BaseNode can be used as the "base type" in the struct-path +/// TBAA scheme. This means \p BaseNode is either a scalar node, or a +/// struct-type node describing an aggregate data structure (like a struct). +Verifier::TBAABaseNodeSummary Verifier::verifyTBAABaseNode(Instruction &I, + MDNode *BaseNode) { + if (BaseNode->getNumOperands() < 2) { + CheckFailed("Base nodes must have at least two operands", &I, BaseNode); + return {true, ~0u}; + } + + auto Itr = TBAABaseNodes.find(BaseNode); + if (Itr != TBAABaseNodes.end()) + return Itr->second; + + auto Result = verifyTBAABaseNodeImpl(I, BaseNode); + auto InsertResult = TBAABaseNodes.insert({BaseNode, Result}); + (void)InsertResult; + assert(InsertResult.second && "We just checked!"); + return Result; +} + +Verifier::TBAABaseNodeSummary +Verifier::verifyTBAABaseNodeImpl(Instruction &I, MDNode *BaseNode) { + const Verifier::TBAABaseNodeSummary InvalidNode = {true, ~0u}; + + if (BaseNode->getNumOperands() == 2) { + // This is a scalar base node. + if (!BaseNode->getOperand(0) || !BaseNode->getOperand(1)) { + CheckFailed("Null operands in scalar type nodes!", &I, BaseNode); + return InvalidNode; + } + if (!isa(BaseNode->getOperand(1))) { + CheckFailed("Invalid parent operand in scalar TBAA node", &I, BaseNode); + return InvalidNode; + } + if (!isa(BaseNode->getOperand(0))) { + CheckFailed("Invalid name operand in scalar TBAA node", &I, BaseNode); + return InvalidNode; + } + + // Scalar nodes can only be accessed at offset 0. + return {false, 0}; + } + + if (BaseNode->getNumOperands() % 2 != 1) { + CheckFailed("Struct tag nodes must have an odd number of operands!", + BaseNode); + return InvalidNode; + } + + bool Failed = false; + + Optional PrevOffset; + unsigned BitWidth = ~0u; + + // We've already checked that BaseNode is not a degenerate root node with one + // operand in \c verifyTBAABaseNode, so this loop should run at least once. + for (unsigned Idx = 1; Idx < BaseNode->getNumOperands(); Idx += 2) { + const MDOperand &FieldTy = BaseNode->getOperand(Idx); + const MDOperand &FieldOffset = BaseNode->getOperand(Idx + 1); + if (!isa(FieldTy)) { + CheckFailed("Incorrect field entry in struct type node!", &I, BaseNode); + Failed = true; + continue; + } + + auto *OffsetEntryCI = + mdconst::dyn_extract_or_null(FieldOffset); + if (!OffsetEntryCI) { + CheckFailed("Offset entries must be constants!", &I, BaseNode); + Failed = true; + continue; + } + + if (BitWidth == ~0u) + BitWidth = OffsetEntryCI->getBitWidth(); + + if (OffsetEntryCI->getBitWidth() != BitWidth) { + CheckFailed( + "Bitwidth between the offsets and struct type entries must match", &I, + BaseNode); + Failed = true; + continue; + } + + // NB! As far as I can tell, we generate a non-strictly increasing offset + // sequence only from structs that have zero size bit fields. When + // recursing into a contained struct in \c getFieldNodeFromTBAABaseNode we + // pick the field lexically the latest in struct type metadata node. This + // mirrors the actual behavior of the alias analysis implementation. + bool IsAscending = + !PrevOffset || PrevOffset->ule(OffsetEntryCI->getValue()); + + if (!IsAscending) { + CheckFailed("Offsets must be increasing!", &I, BaseNode); + Failed = true; + } + + PrevOffset = OffsetEntryCI->getValue(); + } + + return Failed ? InvalidNode : Verifier::TBAABaseNodeSummary(false, BitWidth); +} + +static bool IsRootTBAANode(const MDNode *MD) { + return MD->getNumOperands() < 2; +} + +static bool IsScalarTBAANodeImpl(const MDNode *MD, + SmallPtrSetImpl &Visited) { + if (MD->getNumOperands() == 2) + return true; + + if (MD->getNumOperands() != 3) + return false; + + auto *Offset = mdconst::dyn_extract(MD->getOperand(2)); + if (!(Offset && Offset->isZero() && isa(MD->getOperand(0)))) + return false; + + auto *Parent = dyn_cast(MD->getOperand(1)); + return Visited.insert(Parent).second && + (IsRootTBAANode(Parent) || IsScalarTBAANodeImpl(Parent, Visited)); +} + +static bool IsScalarTBAANode(const MDNode *MD) { + SmallPtrSet Visited; + return IsScalarTBAANodeImpl(MD, Visited); +} + +/// Returns the field node at the offset \p Offset in \p BaseNode. Update \p +/// Offset in place to be the offset within the field node returned. +/// +/// We assume we've okayed \p BaseNode via \c verifyTBAABaseNode. +MDNode *Verifier::getFieldNodeFromTBAABaseNode(Instruction &I, MDNode *BaseNode, + APInt &Offset) { + assert(BaseNode->getNumOperands() >= 2 && "Invalid base node!"); + + // Scalar nodes have only one possible "field" -- their parent in the access + // hierarchy. Offset must be zero at this point, but our caller is supposed + // to Assert that. + if (BaseNode->getNumOperands() == 2) + return cast(BaseNode->getOperand(1)); + + for (unsigned Idx = 1; Idx < BaseNode->getNumOperands(); Idx += 2) { + auto *OffsetEntryCI = + mdconst::extract(BaseNode->getOperand(Idx + 1)); + if (OffsetEntryCI->getValue().ugt(Offset)) { + if (Idx == 1) { + CheckFailed("Could not find TBAA parent in struct type node", &I, + BaseNode, &Offset); + return nullptr; + } + + auto *PrevOffsetEntryCI = + mdconst::extract(BaseNode->getOperand(Idx - 1)); + Offset -= PrevOffsetEntryCI->getValue(); + return cast(BaseNode->getOperand(Idx - 2)); + } + } + + auto *LastOffsetEntryCI = mdconst::extract( + BaseNode->getOperand(BaseNode->getNumOperands() - 1)); + + Offset -= LastOffsetEntryCI->getValue(); + return cast(BaseNode->getOperand(BaseNode->getNumOperands() - 2)); +} + void Verifier::visitTBAAMetadata(Instruction &I, MDNode *MD) { bool IsStructPathTBAA = isa(MD->getOperand(0)) && MD->getNumOperands() >= 3; @@ -3664,6 +3859,70 @@ Assert(IsStructPathTBAA, "Old-style TBAA is no longer allowed, use struct-path TBAA instead", &I); + + Assert(MD->getNumOperands() < 5, + "Struct tag metadata must have either 3 or 4 operands", &I, MD); + + MDNode *BaseNode = dyn_cast_or_null(MD->getOperand(0)); + MDNode *AccessType = dyn_cast_or_null(MD->getOperand(1)); + + if (MD->getNumOperands() == 4) { + auto *IsImmutableCI = + mdconst::dyn_extract_or_null(MD->getOperand(3)); + Assert(IsImmutableCI, + "Immutability tag on struct tag metadata must be a constant", &I, + MD); + Assert(IsImmutableCI->isZero() || IsImmutableCI->isOne(), + "Immutability part of the struct tag metadata must be either 0 or 1", + &I, MD); + } + + Assert(BaseNode && AccessType, + "Malformed struct tag metadata: base and access-type " + "should be non-null and point to Metadata nodes", + &I, MD, BaseNode, AccessType); + + Assert(IsScalarTBAANode(AccessType), "Access type node must be scalar", &I, + MD, AccessType); + + auto *OffsetCI = mdconst::dyn_extract_or_null(MD->getOperand(2)); + Assert(OffsetCI, "Offset must be constant integer", &I, MD); + + APInt Offset = OffsetCI->getValue(); + bool SeenAccessTypeInPath = false; + + SmallPtrSet StructPath; + + for (/* empty */; BaseNode && !IsRootTBAANode(BaseNode); + BaseNode = getFieldNodeFromTBAABaseNode(I, BaseNode, Offset)) { + if (!StructPath.insert(BaseNode).second) { + CheckFailed("Cycle detected in struct path", &I, MD); + return; + } + + bool Invalid; + unsigned BaseNodeBitWidth; + std::tie(Invalid, BaseNodeBitWidth) = verifyTBAABaseNode(I, BaseNode); + + // If the base node is invalid in itself, then we've already printed all the + // errors we wanted to print. + if (Invalid) + return; + + SeenAccessTypeInPath |= BaseNode == AccessType; + + if (IsScalarTBAANode(BaseNode) || BaseNode == AccessType) + Assert(Offset == 0, "Offset not zero at the point of scalar access", &I, + MD, &Offset); + + Assert(BaseNodeBitWidth == Offset.getBitWidth() || + (BaseNodeBitWidth == 0 && Offset == 0), + "Access bit-width not the same as description bit-width", &I, MD, + BaseNodeBitWidth, Offset.getBitWidth()); + } + + Assert(SeenAccessTypeInPath, "Did not see access type in access path!", &I, + MD); } /// verifyInstruction - Verify that an instruction is well formed. @@ -3801,8 +4060,12 @@ if (MDNode *MD = I.getMetadata(LLVMContext::MD_dereferenceable_or_null)) visitDereferenceableMetadata(I, MD); - if (MDNode *MD = I.getMetadata(LLVMContext::MD_tbaa)) - visitTBAAMetadata(I, MD); + if (MDNode *TBAA = I.getMetadata(LLVMContext::MD_tbaa)) { + Assert(isa(I) || isa(I) || isa(I) || + isa(I), + "TBAA is only for loads, stores and calls!", &I); + visitTBAAMetadata(I, TBAA); + } if (MDNode *AlignMD = I.getMetadata(LLVMContext::MD_align)) { Assert(I.getType()->isPointerTy(), "align applies only to pointer types", Index: llvm/trunk/test/Analysis/BasicAA/full-store-partial-alias.ll =================================================================== --- llvm/trunk/test/Analysis/BasicAA/full-store-partial-alias.ll +++ llvm/trunk/test/Analysis/BasicAA/full-store-partial-alias.ll @@ -31,7 +31,7 @@ !0 = !{!4, !4, i64 0} !1 = !{!"omnipotent char", !2} -!2 = !{!"Simple C/C++ TBAA", null} +!2 = !{!"Simple C/C++ TBAA"} !3 = !{!5, !5, i64 0} !4 = !{!"double", !1} !5 = !{!"int", !1} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll @@ -33,7 +33,7 @@ !0 = !{!4, !4, i64 0} !1 = !{!"omnipotent char", !2} -!2 = !{!"Simple C/C++ TBAA", null} +!2 = !{!"Simple C/C++ TBAA"} !3 = !{!5, !5, i64 0} !4 = !{!"double", !1} !5 = !{!"int", !1} Index: llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/aliastest.ll =================================================================== --- llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/aliastest.ll +++ llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/aliastest.ll @@ -63,5 +63,6 @@ !7 = !{ !"foo", !0 } !8 = !{ !"bar", !0 } !9 = !{ !"foo", !0 } -!10 = !{ !"bar", !"different" } +!10 = !{ !"bar", !12 } !11 = !{ !"qux", !0} +!12 = !{!"different"} Index: llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/cyclic.ll =================================================================== --- llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/cyclic.ll +++ llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/cyclic.ll @@ -1,5 +1,5 @@ ; RUN: not opt -instcombine < %s 2>&1 | FileCheck %s -; CHECK: Cycle found in TBAA metadata. +; CHECK: Access type node must be scalar define void @test6(i32* %gi) #0 { entry: Index: llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/dse.ll =================================================================== --- llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/dse.ll +++ llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/dse.ll @@ -68,5 +68,6 @@ !7 = !{ !"foo", !0 } !8 = !{ !"bar", !0 } !9 = !{ !"foo", !0 } -!10 = !{ !"bar", !"different" } +!10 = !{ !"bar", !12} !11 = !{ !"qux", !0} +!12 = !{!"different"} Index: llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/dynamic-indices.ll =================================================================== --- llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/dynamic-indices.ll +++ llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/dynamic-indices.ll @@ -127,7 +127,7 @@ ; CHECK: [[TYPE_LL]] = !{!"long long", {{!.*}}} !0 = !{!6, !6, i64 0} !1 = !{!"omnipotent char", !2} -!2 = !{!"Simple C/C++ TBAA", null} +!2 = !{!"Simple C/C++ TBAA"} !3 = !{!7, !7, i64 0} !4 = !{!8, !8, i64 0} !5 = !{!9, !9, i64 0} Index: llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/gvn-nonlocal-type-mismatch.ll =================================================================== --- llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/gvn-nonlocal-type-mismatch.ll +++ llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/gvn-nonlocal-type-mismatch.ll @@ -91,5 +91,6 @@ !4 = !{!8, !8, i64 0} !5 = !{!"red", !0} !6 = !{!"blu", !0} -!7 = !{!"outer space"} +!7 = !{!"outer space", !9} !8 = !{!"brick red", !5} +!9 = !{!"observable universe"} Index: llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/intrinsics.ll =================================================================== --- llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/intrinsics.ll +++ llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/intrinsics.ll @@ -26,7 +26,7 @@ ; CHECK: attributes #1 = { argmemonly nounwind } ; CHECK: attributes [[NUW]] = { nounwind } -!0 = !{!"tbaa root", null} +!0 = !{!"tbaa root"} !1 = !{!3, !3, i64 0} !2 = !{!4, !4, i64 0} !3 = !{!"A", !0} Index: llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/licm.ll =================================================================== --- llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/licm.ll +++ llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/licm.ll @@ -29,7 +29,7 @@ ret void } -!0 = !{!"root", null} +!0 = !{!"root"} !1 = !{!6, !6, i64 0} !2 = !{!7, !7, i64 0} @@ -58,8 +58,9 @@ !3 = !{!"pointer", !8} !4 = !{!8, !8, i64 0} -!5 = !{!9, !9, i64 0} +!5 = !{!10, !10, i64 0} !6 = !{!"pointer", !0} !7 = !{!"double", !0} !8 = !{!"char", !9} -!9 = !{!"root", null} +!9 = !{!"root"} +!10 = !{!"scalar-type", !9} Index: llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/memcpyopt.ll =================================================================== --- llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/memcpyopt.ll +++ llvm/trunk/test/Analysis/TypeBasedAliasAnalysis/memcpyopt.ll @@ -20,7 +20,7 @@ ; CHECK: [[TAGA]] = !{[[TYPEA:!.*]], [[TYPEA]], i64 0} ; CHECK: [[TYPEA]] = !{!"A", !{{.*}}} -!0 = !{!"tbaa root", null} +!0 = !{!"tbaa root"} !1 = !{!3, !3, i64 0} !2 = !{!4, !4, i64 0} !3 = !{!"A", !0} Index: llvm/trunk/test/CodeGen/AMDGPU/llvm.SI.load.dword.ll =================================================================== --- llvm/trunk/test/CodeGen/AMDGPU/llvm.SI.load.dword.ll +++ llvm/trunk/test/CodeGen/AMDGPU/llvm.SI.load.dword.ll @@ -49,4 +49,5 @@ attributes #0 = { nounwind readonly } -!0 = !{!"const", null, i32 1} +!0 = !{!"const", !1, i32 1} +!1 = !{!"tbaa root"} Index: llvm/trunk/test/CodeGen/AMDGPU/sgpr-copy.ll =================================================================== --- llvm/trunk/test/CodeGen/AMDGPU/sgpr-copy.ll +++ llvm/trunk/test/CodeGen/AMDGPU/sgpr-copy.ll @@ -412,5 +412,6 @@ attributes #2 = { nounwind readonly } !0 = !{!1, !1, i64 0, i32 1} -!1 = !{!"const", null} +!1 = !{!"const", !3} !2 = !{!1, !1, i64 0} +!3 = !{!"tbaa root"} Index: llvm/trunk/test/CodeGen/AMDGPU/si-lod-bias.ll =================================================================== --- llvm/trunk/test/CodeGen/AMDGPU/si-lod-bias.ll +++ llvm/trunk/test/CodeGen/AMDGPU/si-lod-bias.ll @@ -49,4 +49,5 @@ attributes #1 = { nounwind readnone } !0 = !{!1, !1, i64 0, i32 1} -!1 = !{!"const", null} +!1 = !{!"const", !2} +!2 = !{!"tbaa root"} Index: llvm/trunk/test/CodeGen/AMDGPU/si-scheduler.ll =================================================================== --- llvm/trunk/test/CodeGen/AMDGPU/si-scheduler.ll +++ llvm/trunk/test/CodeGen/AMDGPU/si-scheduler.ll @@ -57,4 +57,5 @@ attributes #1 = { nounwind readnone } !0 = !{!1, !1, i64 0, i32 1} -!1 = !{!"const", null} +!1 = !{!"const", !2} +!2 = !{!"tbaa root"} Index: llvm/trunk/test/CodeGen/AMDGPU/si-sgpr-spill.ll =================================================================== --- llvm/trunk/test/CodeGen/AMDGPU/si-sgpr-spill.ll +++ llvm/trunk/test/CodeGen/AMDGPU/si-sgpr-spill.ll @@ -1619,4 +1619,5 @@ attributes #3 = { nounwind readonly } !0 = !{!1, !1, i64 0, i32 1} -!1 = !{!"const", null} +!1 = !{!"const", !2} +!2 = !{!"tbaa root"} Index: llvm/trunk/test/CodeGen/AMDGPU/split-smrd.ll =================================================================== --- llvm/trunk/test/CodeGen/AMDGPU/split-smrd.ll +++ llvm/trunk/test/CodeGen/AMDGPU/split-smrd.ll @@ -42,5 +42,6 @@ attributes #1 = { nounwind readnone } !0 = !{!1, !1, i64 0, i32 1} -!1 = !{!"const", null} +!1 = !{!"const", !3} !2 = !{!1, !1, i64 0} +!3 = !{!"tbaa root"} Index: llvm/trunk/test/CodeGen/AMDGPU/vgpr-spill-emergency-stack-slot.ll =================================================================== --- llvm/trunk/test/CodeGen/AMDGPU/vgpr-spill-emergency-stack-slot.ll +++ llvm/trunk/test/CodeGen/AMDGPU/vgpr-spill-emergency-stack-slot.ll @@ -497,4 +497,5 @@ attributes #1 = { nounwind readnone } !0 = !{!1, !1, i64 0, i32 1} -!1 = !{!"const", null} +!1 = !{!"const", !2} +!2 = !{!"tbaa root"} Index: llvm/trunk/test/CodeGen/AMDGPU/wait.ll =================================================================== --- llvm/trunk/test/CodeGen/AMDGPU/wait.ll +++ llvm/trunk/test/CodeGen/AMDGPU/wait.ll @@ -82,4 +82,5 @@ attributes #2 = { nounwind readnone } !0 = !{!1, !1, i64 0, i32 1} -!1 = !{!"const", null} +!1 = !{!"const", !2} +!2 = !{!"tbaa root"} Index: llvm/trunk/test/CodeGen/ARM/2011-05-04-MultipleLandingPadSuccs.ll =================================================================== --- llvm/trunk/test/CodeGen/ARM/2011-05-04-MultipleLandingPadSuccs.ll +++ llvm/trunk/test/CodeGen/ARM/2011-05-04-MultipleLandingPadSuccs.ll @@ -83,6 +83,6 @@ !0 = !{!"any pointer", !1} !1 = !{!"omnipotent char", !2} -!2 = !{!"Simple C/C++ TBAA", null} +!2 = !{!"Simple C/C++ TBAA"} !3 = !{!"bool", !1} !4 = !{!"int", !1} Index: llvm/trunk/test/Instrumentation/AddressSanitizer/X86/bug_11395.ll =================================================================== --- llvm/trunk/test/Instrumentation/AddressSanitizer/X86/bug_11395.ll +++ llvm/trunk/test/Instrumentation/AddressSanitizer/X86/bug_11395.ll @@ -66,7 +66,7 @@ !0 = !{!5, !5, i64 0} !1 = !{!"omnipotent char", !2} -!2 = !{!"Simple C/C++ TBAA", null} +!2 = !{!"Simple C/C++ TBAA"} !3 = !{!6, !6, i64 0} !4 = !{i32 156132, i32 156164, i32 156205, i32 156238, i32 156282, i32 156332, i32 156370, i32 156408, i32 156447, i32 156486, i32 156536, i32 156574, i32 156612, i32 156651, i32 156690, i32 156740, i32 156778, i32 156816, i32 156855, i32 156894, i32 156944, i32 156982, i32 157020, i32 157059, i32 157098, i32 157148, i32 157186, i32 157224, i32 157263, i32 157302, i32 157352, i32 157390, i32 157428, i32 157467, i32 157506, i32 157556, i32 157594, i32 157632, i32 157671, i32 157710, i32 157760, i32 157798, i32 157836, i32 157875, i32 157914, i32 157952, i32 157996, i32 158046, i32 158099, i32 158140, i32 158179, i32 158218, i32 158268, i32 158321, i32 158362, i32 158401, i32 158440, i32 158490, i32 158543, i32 158584, i32 158623, i32 158662, i32 158712, i32 158765, i32 158806, i32 158845, i32 158884, i32 158922, i32 158963, i32 158996, i32 159029, i32 159062, i32 159109, i32 159154, i32 159199, i32 159243, i32 159286, i32 159329, i32 159375, i32 159422, i32 159478, i32 159522, i32 159566} !5 = !{!"any pointer", !1} Index: llvm/trunk/test/Instrumentation/ThreadSanitizer/read_from_global.ll =================================================================== --- llvm/trunk/test/Instrumentation/ThreadSanitizer/read_from_global.ll +++ llvm/trunk/test/Instrumentation/ThreadSanitizer/read_from_global.ll @@ -54,6 +54,6 @@ ; CHECK: = load ; CHECK: ret void -!0 = !{!"Simple C/C++ TBAA", null} +!0 = !{!"Simple C/C++ TBAA"} !1 = !{!"vtable pointer", !0} !2 = !{!1, !1, i64 0} Index: llvm/trunk/test/Instrumentation/ThreadSanitizer/vptr_read.ll =================================================================== --- llvm/trunk/test/Instrumentation/ThreadSanitizer/vptr_read.ll +++ llvm/trunk/test/Instrumentation/ThreadSanitizer/vptr_read.ll @@ -9,5 +9,5 @@ ret i8 %0 } !0 = !{!2, !2, i64 0} -!1 = !{!"Simple C/C++ TBAA", null} +!1 = !{!"Simple C/C++ TBAA"} !2 = !{!"vtable pointer", !1} Index: llvm/trunk/test/Instrumentation/ThreadSanitizer/vptr_update.ll =================================================================== --- llvm/trunk/test/Instrumentation/ThreadSanitizer/vptr_update.ll +++ llvm/trunk/test/Instrumentation/ThreadSanitizer/vptr_update.ll @@ -36,5 +36,5 @@ } !0 = !{!2, !2, i64 0} -!1 = !{!"Simple C/C++ TBAA", null} +!1 = !{!"Simple C/C++ TBAA"} !2 = !{!"vtable pointer", !1} Index: llvm/trunk/test/Transforms/GVN/PRE/preserve-tbaa.ll =================================================================== --- llvm/trunk/test/Transforms/GVN/PRE/preserve-tbaa.ll +++ llvm/trunk/test/Transforms/GVN/PRE/preserve-tbaa.ll @@ -27,5 +27,5 @@ !0 = !{!3, !3, i64 0} !1 = !{!"omnipotent char", !2} -!2 = !{!"Simple C/C++ TBAA", null} +!2 = !{!"Simple C/C++ TBAA"} !3 = !{!"short", !1} Index: llvm/trunk/test/Transforms/GVN/tbaa.ll =================================================================== --- llvm/trunk/test/Transforms/GVN/tbaa.ll +++ llvm/trunk/test/Transforms/GVN/tbaa.ll @@ -113,13 +113,14 @@ ; CHECK: [[TAGA]] = !{[[TYPEA]], [[TYPEA]], i64 0} !0 = !{!5, !5, i64 0} !1 = !{!6, !6, i64 0} -!2 = !{!"tbaa root", null} +!2 = !{!"tbaa root"} !3 = !{!7, !7, i64 0} -!4 = !{!8, !8, i64 0} +!4 = !{!11, !11, i64 0} !5 = !{!"C", !6} !6 = !{!"A", !2} !7 = !{!"B", !6} -!8 = !{!"another root", null} +!8 = !{!"another root"} +!11 = !{!"scalar type", !8} ;; A TBAA structure who's only point is to have a constant location Index: llvm/trunk/test/Transforms/InstCombine/load-combine-metadata.ll =================================================================== --- llvm/trunk/test/Transforms/InstCombine/load-combine-metadata.ll +++ llvm/trunk/test/Transforms/InstCombine/load-combine-metadata.ll @@ -26,4 +26,5 @@ !5 = !{!3} !6 = !{!4} !7 = !{ !"tbaa root" } -!8 = !{ !7, !7, i64 0 } +!8 = !{ !9, !9, i64 0 } +!9 = !{ !"scalar type", !7} Index: llvm/trunk/test/Transforms/InstCombine/loadstore-metadata.ll =================================================================== --- llvm/trunk/test/Transforms/InstCombine/loadstore-metadata.ll +++ llvm/trunk/test/Transforms/InstCombine/loadstore-metadata.ll @@ -15,9 +15,9 @@ define i32 @test_load_cast_combine_noalias(float* %ptr) { ; Ensure (cast (load (...))) -> (load (cast (...))) preserves no-alias metadata. ; CHECK-LABEL: @test_load_cast_combine_noalias( -; CHECK: load i32, i32* %{{.*}}, !alias.scope !2, !noalias !1 +; CHECK: load i32, i32* %{{.*}}, !alias.scope !3, !noalias !4 entry: - %l = load float, float* %ptr, !alias.scope !2, !noalias !1 + %l = load float, float* %ptr, !alias.scope !3, !noalias !4 %c = bitcast float %l to i32 ret i32 %c } @@ -31,7 +31,7 @@ ; CHECK-NOT: !range ; CHECK: ret float entry: - %l = load i32, i32* %ptr, !range !6 + %l = load i32, i32* %ptr, !range !5 %c = bitcast i32 %l to float ret float %c } @@ -39,9 +39,9 @@ define i32 @test_load_cast_combine_invariant(float* %ptr) { ; Ensure (cast (load (...))) -> (load (cast (...))) preserves invariant metadata. ; CHECK-LABEL: @test_load_cast_combine_invariant( -; CHECK: load i32, i32* %{{.*}}, !invariant.load !3 +; CHECK: load i32, i32* %{{.*}}, !invariant.load !5 entry: - %l = load float, float* %ptr, !invariant.load !3 + %l = load float, float* %ptr, !invariant.load !6 %c = bitcast float %l to i32 ret i32 %c } @@ -50,9 +50,9 @@ ; Ensure (cast (load (...))) -> (load (cast (...))) preserves nontemporal ; metadata. ; CHECK-LABEL: @test_load_cast_combine_nontemporal( -; CHECK: load i32, i32* %{{.*}}, !nontemporal !4 +; CHECK: load i32, i32* %{{.*}}, !nontemporal !6 entry: - %l = load float, float* %ptr, !nontemporal !4 + %l = load float, float* %ptr, !nontemporal !7 %c = bitcast float %l to i32 ret i32 %c } @@ -61,9 +61,9 @@ ; Ensure (cast (load (...))) -> (load (cast (...))) preserves align ; metadata. ; CHECK-LABEL: @test_load_cast_combine_align( -; CHECK: load i8*, i8** %{{.*}}, !align !5 +; CHECK: load i8*, i8** %{{.*}}, !align !7 entry: - %l = load i32*, i32** %ptr, !align !5 + %l = load i32*, i32** %ptr, !align !8 %c = bitcast i32* %l to i8* ret i8* %c } @@ -72,9 +72,9 @@ ; Ensure (cast (load (...))) -> (load (cast (...))) preserves dereferenceable ; metadata. ; CHECK-LABEL: @test_load_cast_combine_deref( -; CHECK: load i8*, i8** %{{.*}}, !dereferenceable !5 +; CHECK: load i8*, i8** %{{.*}}, !dereferenceable !7 entry: - %l = load i32*, i32** %ptr, !dereferenceable !5 + %l = load i32*, i32** %ptr, !dereferenceable !8 %c = bitcast i32* %l to i8* ret i8* %c } @@ -83,9 +83,9 @@ ; Ensure (cast (load (...))) -> (load (cast (...))) preserves ; dereferenceable_or_null metadata. ; CHECK-LABEL: @test_load_cast_combine_deref_or_null( -; CHECK: load i8*, i8** %{{.*}}, !dereferenceable_or_null !5 +; CHECK: load i8*, i8** %{{.*}}, !dereferenceable_or_null !7 entry: - %l = load i32*, i32** %ptr, !dereferenceable_or_null !5 + %l = load i32*, i32** %ptr, !dereferenceable_or_null !8 %c = bitcast i32* %l to i8* ret i8* %c } @@ -94,7 +94,7 @@ ; Ensure (cast (load (...))) -> (load (cast (...))) preserves loop access ; metadata. ; CHECK-LABEL: @test_load_cast_combine_loop( -; CHECK: load i32, i32* %{{.*}}, !llvm.mem.parallel_loop_access !1 +; CHECK: load i32, i32* %{{.*}}, !llvm.mem.parallel_loop_access !4 entry: br label %loop @@ -102,7 +102,7 @@ %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] %src.gep = getelementptr inbounds float, float* %src, i32 %i %dst.gep = getelementptr inbounds i32, i32* %dst, i32 %i - %l = load float, float* %src.gep, !llvm.mem.parallel_loop_access !1 + %l = load float, float* %src.gep, !llvm.mem.parallel_loop_access !4 %c = bitcast float %l to i32 store i32 %c, i32* %dst.gep %i.next = add i32 %i, 1 @@ -130,7 +130,7 @@ ; CHECK-NOT: !nonnull ; CHECK: store i64 %[[V]], i64* entry: - %p = load float*, float** %ptr, !nonnull !3 + %p = load float*, float** %ptr, !nonnull !6 %gep = getelementptr float*, float** %ptr, i32 42 store float* %p, float** %gep ret void @@ -138,10 +138,12 @@ ; This is the metadata tuple that we reference above: ; CHECK: ![[MD]] = !{i64 1, i64 0} -!0 = !{ !1, !1, i64 0 } -!1 = !{ !1 } -!2 = !{ !2, !1 } -!3 = !{ } -!4 = !{ i32 1 } -!5 = !{ i64 8 } -!6 = !{ i32 0, i32 42 } +!0 = !{!1, !1, i64 0} +!1 = !{!"scalar type", !2} +!2 = !{!"root"} +!3 = distinct !{!3, !4} +!4 = distinct !{!4} +!5 = !{i32 0, i32 42} +!6 = !{} +!7 = !{i32 1} +!8 = !{i64 8} Index: llvm/trunk/test/Transforms/InstCombine/tbaa-store-to-load.ll =================================================================== --- llvm/trunk/test/Transforms/InstCombine/tbaa-store-to-load.ll +++ llvm/trunk/test/Transforms/InstCombine/tbaa-store-to-load.ll @@ -14,4 +14,5 @@ } !0 = !{!1, !1, i64 0} -!1 = !{!"load_tbaa"} +!1 = !{!"scalar type", !2} +!2 = !{!"load_tbaa"} Index: llvm/trunk/test/Transforms/JumpThreading/thread-loads.ll =================================================================== --- llvm/trunk/test/Transforms/JumpThreading/thread-loads.ll +++ llvm/trunk/test/Transforms/JumpThreading/thread-loads.ll @@ -304,7 +304,7 @@ !0 = !{!3, !3, i64 0} !1 = !{!"omnipotent char", !2} -!2 = !{!"Simple C/C++ TBAA", null} +!2 = !{!"Simple C/C++ TBAA"} !3 = !{!"int", !1} !4 = !{ i32 0, i32 1 } !5 = !{ i32 8, i32 10 } Index: llvm/trunk/test/Transforms/LICM/2011-04-06-PromoteResultOfPromotion.ll =================================================================== --- llvm/trunk/test/Transforms/LICM/2011-04-06-PromoteResultOfPromotion.ll +++ llvm/trunk/test/Transforms/LICM/2011-04-06-PromoteResultOfPromotion.ll @@ -32,7 +32,7 @@ !0 = !{!5, !5, i64 0} !1 = !{!"omnipotent char", !2} -!2 = !{!"Simple C/C++ TBAA", null} +!2 = !{!"Simple C/C++ TBAA"} !3 = !{!"short", !1} !4 = !{!6, !6, i64 0} !5 = !{!"any pointer", !1} Index: llvm/trunk/test/Transforms/LoopVectorize/ARM/vector_cast.ll =================================================================== --- llvm/trunk/test/Transforms/LoopVectorize/ARM/vector_cast.ll +++ llvm/trunk/test/Transforms/LoopVectorize/ARM/vector_cast.ll @@ -32,6 +32,6 @@ !6 = !{!"omnipotent char", !7, i64 0} !7 = !{!"Simple C/C++ TBAA"} !8 = !{!9, !5, i64 0} -!9 = !{!5, i64 0, !10, i64 4} +!9 = !{!"some struct", !5, i64 0, !10, i64 4} !10 = !{!"int", !6, i64 0} !11 = !{!9, !10, i64 4} Index: llvm/trunk/test/Transforms/SLPVectorizer/X86/crash_scheduling.ll =================================================================== --- llvm/trunk/test/Transforms/SLPVectorizer/X86/crash_scheduling.ll +++ llvm/trunk/test/Transforms/SLPVectorizer/X86/crash_scheduling.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -basicaa -slp-vectorizer -S -mtriple=x86_64-apple-macosx10.8.0 -mcpu=corei7 +; RUN: opt < %s -basicaa -disable-verify -slp-vectorizer -S -mtriple=x86_64-apple-macosx10.8.0 -mcpu=corei7 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-apple-darwin13.3.0" Index: llvm/trunk/test/Transforms/SimplifyCFG/basictest.ll =================================================================== --- llvm/trunk/test/Transforms/SimplifyCFG/basictest.ll +++ llvm/trunk/test/Transforms/SimplifyCFG/basictest.ll @@ -106,7 +106,7 @@ %tmp1 = icmp eq i8 %tmp, 0 br i1 %tmp1, label %bb2, label %bb1 bb1: - %tmp3 = load i8, i8* %r, align 1, !range !2, !tbaa !1, !dbg !5 + %tmp3 = load i8, i8* %r, align 1, !range !2, !tbaa !10, !dbg !5 %tmp4 = icmp eq i8 %tmp3, 1 br i1 %tmp4, label %bb2, label %bb3 bb2: @@ -120,7 +120,7 @@ !llvm.dbg.cu = !{!3} !llvm.module.flags = !{!8, !9} -!0 = !{!1, !1, i64 0} +!0 = !{!10, !10, i64 0} !1 = !{!"foo"} !2 = !{i8 0, i8 2} !3 = distinct !DICompileUnit(language: DW_LANG_C99, file: !7, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !4) @@ -130,3 +130,4 @@ !7 = !DIFile(filename: "foo.c", directory: "/") !8 = !{i32 2, !"Dwarf Version", i32 2} !9 = !{i32 2, !"Debug Info Version", i32 3} +!10 = !{!"scalar type", !1} Index: llvm/trunk/test/Transforms/Util/store-first-op.ll =================================================================== --- llvm/trunk/test/Transforms/Util/store-first-op.ll +++ llvm/trunk/test/Transforms/Util/store-first-op.ll @@ -32,5 +32,6 @@ !5 = !DICompositeType(tag: DW_TAG_class_type, scope: !4, file: !1, line: 25, size: 8, align: 8) !6 = !DIExpression() !7 = !DILocation(line: 25, column: 8, scope: !4) -!8 = !{!9, !9, i64 0} +!8 = !{!10, !10, i64 0} !9 = !{i64 0} +!10 = !{!"scalar type", !9} Index: llvm/trunk/test/Verifier/tbaa.ll =================================================================== --- llvm/trunk/test/Verifier/tbaa.ll +++ llvm/trunk/test/Verifier/tbaa.ll @@ -0,0 +1,109 @@ +; RUN: not llvm-as < %s 2>&1 | FileCheck %s + +define void @f_0(i32* %ptr) { +; This part checks for the easy syntactic verifier rules. + +; CHECK: Struct tag metadata must have either 3 or 4 operands +; CHECK-NEXT: store i32 0, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Immutability tag on struct tag metadata must be a constant +; CHECK-NEXT: store i32 1, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Immutability part of the struct tag metadata must be either 0 or 1 +; CHECK-NEXT: store i32 2, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Offset must be constant integer +; CHECK-NEXT: store i32 3, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Malformed struct tag metadata: base and access-type should be non-null and point to Metadata nodes +; CHECK-NEXT: store i32 4, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Access type node must be scalar +; CHECK-NEXT: store i32 5, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Access bit-width not the same as description bit-width +; CHECK-NEXT: store i32 6, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Access type node must be scalar +; CHECK-NEXT: store i32 7, i32* %ptr, !tbaa !{{[0-9]+}} + + store i32 0, i32* %ptr, !tbaa !{!3, !2, i64 40, i64 0, i64 1, i64 2} + store i32 1, i32* %ptr, !tbaa !{!3, !2, i64 40, !"immutable"} + store i32 2, i32* %ptr, !tbaa !{!3, !2, i64 40, i64 4} + store i32 3, i32* %ptr, !tbaa !{!3, !2, !"40", i64 0} + store i32 4, i32* %ptr, !tbaa !{!3, null, !"40", i64 0} + store i32 5, i32* %ptr, !tbaa !{!3, !3, !"40", i64 0} + store i32 6, i32* %ptr, !tbaa !{!3, !2, i32 40, i64 0} + store i32 7, i32* %ptr, !tbaa !{!3, !12, i32 40, i64 0} + ret void +} + + +define void @f_1(i32* %ptr) { +; This part checks for more semantic verifier rules. + +; CHECK: Cycle detected in struct path +; CHECK-NEXT: store i32 0, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Offset not zero at the point of scalar access +; CHECK-NEXT: store i32 1, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Offset not zero at the point of scalar access +; CHECK-NEXT: store i32 2, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Could not find TBAA parent in struct type node +; CHECK-NEXT: store i32 3, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Did not see access type in access path! +; CHECK-NEXT: store i32 3, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Invalid parent operand in scalar TBAA node +; CHECK-NEXT: store i32 4, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Invalid name operand in scalar TBAA node +; CHECK-NEXT: store i32 5, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Null operands in scalar type nodes! +; CHECK-NEXT: store i32 6, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Struct tag nodes must have an odd number of operands! +; CHECK-NEXT:!{{[0-9]+}} = !{!"bad-struct-type-0", !{{[0-9]+}}, i64 40, !{{[0-9]+}}} + +; CHECK: Incorrect field entry in struct type node! +; CHECK-NEXT: store i32 8, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Bitwidth between the offsets and struct type entries must match +; CHECK-NEXT: store i32 9, i32* %ptr, !tbaa !{{[0-9]+}} + +; CHECK: Offsets must be increasing! +; CHECK-NEXT: store i32 10, i32* %ptr, !tbaa !{{[0-9]+}} + + store i32 0, i32* %ptr, !tbaa !{!4, !2, i64 40} + store i32 1, i32* %ptr, !tbaa !{!3, !2, i64 45} + store i32 2, i32* %ptr, !tbaa !{!3, !2, i64 45} + store i32 3, i32* %ptr, !tbaa !{!3, !2, i64 10} + store i32 4, i32* %ptr, !tbaa !{!5, !5, i64 0} + store i32 5, i32* %ptr, !tbaa !{!6, !6, i64 0} + store i32 6, i32* %ptr, !tbaa !{!7, !7, i64 0} + store i32 7, i32* %ptr, !tbaa !{!8, !1, i64 40} + store i32 8, i32* %ptr, !tbaa !{!9, !1, i64 40} + store i32 9, i32* %ptr, !tbaa !{!10, !1, i64 40} + store i32 10, i32* %ptr, !tbaa !{!11, !1, i64 40} + ret void +} + + + +!0 = !{!"root"} +!1 = !{!"scalar-a", !0} +!2 = !{!"scalar-b", !0} +!3 = !{!"struct-a", !2, i64 20, !1, i64 40} +!4 = distinct !{!"self-recursive-struct", !2, i64 20, !4, i64 40} +!5 = !{!"bad-scalar-0", i64 40} +!6 = !{i64 42, !0} +!7 = !{!"bad-scalar-1", null} +!8 = !{!"bad-struct-type-0", !1, i64 40, !1} +!9 = !{!"bad-struct-type-1", !1, i64 40, i64 56, !1} +!10 = !{!"bad-struct-type-2", !1, i64 40, !1, i32 56} +!11 = !{!"bad-struct-type-2", !1, i64 80, !1, i64 56} +!12 = !{!"bad-scalar-2", !3, i64 0}