[Verifier] Add verification for TBAA metadata

[sanjoy]

Summary

This change adds some verification in the IR verifier around struct path
TBAA metadata.

Other than some basic sanity checks (e.g. we get constant integers where
we expect integers), this checks:

• That by the time an struct access tuple (base-type, offset) is "reduced" to a scalar base type, the offset is 0. For instance, in C++ you can't start from, say ("struct-a", 16), and end up with ("int", 4) -- by the time the base type is "int", the offset better be zero. In particular, a variant of this invariant is needed for llvm::getMostGenericTBAA to be correct.
• That there are no cycles in a struct path.
• That struct type nodes have their offsets listed in an ascending order.
• That when generating the struct access path, you eventually reach the access type listed in the tbaa tag node.

[sanjoy]

FYI: I'm also actively working on documentation for struct path TBAA. Once the documentation is complete, I expect I'll have to rename some of the functions and variables here to be consistent with the documentation.

[manmanren]

There is one place where there is an ambiguity in the specification:
given a base type !{!"whatever", !N, i64 1} there is no way to tell if
this is a struct containing !N at offset i64 1 or a scalar immutable
TBAA node with !N as the parent. Right now I interpret this as the
former (as the implementation has been doing for 3 years). I will fix
the specification in a forthcoming documentation patch.

I may have misunderstood your point, but for struct-path TBAA, the last integer for a type node is the offset. Only for old scalar TBAA, the last optional integer specifies whether it is immutable. There is no ambiguity in struct-path TBAA.

This patch is for general goodness. Thanks for working on it. I wonder if it makes sense to share some logic between the verifier and TypeBasedAliasAnalysis.cpp, in terms of how to parse the various fields of the struct path tag nodes and the struct type nodes.

Cheers,
Manman

lib/IR/Verifier.cpp

408–409

Can we also change the format here, like the below statement?

4067

I wonder why we switched the order between TBAAMetadata and MD_dereferenceable_or_null.

[sanjoy]

I may have misunderstood your point, but for struct-path TBAA, the last integer for a type node is the offset. Only for old scalar TBAA, the last optional integer specifies whether it is immutable. There is no ambiguity in struct-path TBAA.

Thanks, that clears it up for me.

This patch is for general goodness. Thanks for working on it. I wonder if it makes sense to share some logic between the verifier and TypeBasedAliasAnalysis.cpp, in terms of how to parse the various fields of the struct path tag nodes and the struct type nodes.

I didn't share too much since I want the verifier to be as self contained as is reasonable. Moreover, I want utilities in TypeBasedAliasAnalysis.cpp to trip asserts when a node is malformed, whereas in the verifier I want them to fail gracefully.

lib/IR/Verifier.cpp

408–409

I'll check in a one line cleanup change now and rebase.

4067

It was unintentional -- I'll move it back.

[sanjoy]

Hi Manman,

In D26438#590834, @sanjoy wrote:

I may have misunderstood your point, but for struct-path TBAA, the last integer for a type node is the offset. Only for old scalar TBAA, the last optional integer specifies whether it is immutable. There is no ambiguity in struct-path TBAA.

Thanks, that clears it up for me.

There is this bit of language in the TBAA implementation:

// The second field is the access type node, it
// must be a scalar type node.

but in the TBAA metadata generated by clang it seems like we have access types like !{!"int", !N, i64 0} which look like struct nodes. I can think of three ways to resolve this:

1. State that access types are not necessarily scalar type nodes. However, this is not consistent with how getMostGenericTBAA walks up the parent types of the access type node.
2. State that !{!"int", !N, i64 0} is a scalar type node.
3. State that access types can be either scalar type nodes or a struct type node with one member at offset 0.

I'm not sure what the cleanest option is though I'm slightly leaning towards the second one.

A second related point to what you said before about the immutable bit is that today we'll upgrade

define i32 @f(i32* %p) {
  %val = load i32, i32* %p, !tbaa !0
  ret i32 %val
}

!0 = !{!"const int", !1, i64 1}
!1 = !{!"const char", !2, i64 1}
!2 = !{!"char", !3}
!3 = !{!"root"}

to

define i32 @f(i32* %p) {
  %val = load i32, i32* %p, !tbaa !0
  ret i32 %val
}

!0 = !{!1, !1, i64 0, i64 1}
!1 = !{!"const int", !2}
!2 = !{!"const char", !3, i64 1}
!3 = !{!"char", !4}
!4 = !{!"root"}

This is a problem since in the old scalar tbaa metadata !{!"char", !2, i64 1} meant "immutable const char" but after the upgrade it means struct const_char with a char at offset 1. IOW, given what you said, I don't think the auto-upgrade path is correct.

[mehdi_amini]

When did we stop using the "old" form? We don't need to preserve an auto-upgrade forever, as long as we can simply drop metadata for old bitcodes this is as valid alternative.

[sanjoy]

In D26438#591194, @mehdi_amini wrote:

When did we stop using the "old" form? We don't need to preserve an auto-upgrade forever, as long as we can simply drop metadata for old bitcodes this is as valid alternative.

We've had the auto upgrade logic for what looks like approximately 3 years. I think it is reasonable to deprecate the functionality and eventually remove it, though I know (from off-list emails) that it will break (in terms of performance, not correctness) downstream users.

However, I'm trying to point that, given what I understand so far, we're miscompiling programs today. This makes me wonder if I'm missing something.

[sanjoy]

Be clearer around "scalar-ness" of access types.

The new rhetoric is that some type describing nodes are "scalar like"

• they're either scalar nodes or struct nodes that have one member at

offset 0 that itself is "scalar like". Access types need to be
"scalar like" nodes.

[sanjoy]

NFC code motion

[manmanren]

In D26438#591021, @sanjoy wrote:

Hi Manman,

In D26438#590834, @sanjoy wrote:

I may have misunderstood your point, but for struct-path TBAA, the last integer for a type node is the offset. Only for old scalar TBAA, the last optional integer specifies whether it is immutable. There is no ambiguity in struct-path TBAA.

Thanks, that clears it up for me.

There is this bit of language in the TBAA implementation:

// The second field is the access type node, it
// must be a scalar type node.

but in the TBAA metadata generated by clang it seems like we have access types like !{!"int", !N, i64 0} which look like struct nodes.

Can you give an example where clang generates a struct path tag node where the 2nd field is not a scalar type node?

I can think of three ways to resolve this:

1. State that access types are not necessarily scalar type nodes. However, this is not consistent with how getMostGenericTBAA walks up the parent types of the access type node.
2. State that !{!"int", !N, i64 0} is a scalar type node.
3. State that access types can be either scalar type nodes or a struct type node with one member at offset 0.

I'm not sure what the cleanest option is though I'm slightly leaning towards the second one.

A second related point to what you said before about the immutable bit is that today we'll upgrade

define i32 @f(i32* %p) {
  %val = load i32, i32* %p, !tbaa !0
  ret i32 %val
}

!0 = !{!"const int", !1, i64 1}
!1 = !{!"const char", !2, i64 1}
!2 = !{!"char", !3}
!3 = !{!"root"}

to

define i32 @f(i32* %p) {
  %val = load i32, i32* %p, !tbaa !0
  ret i32 %val
}

!0 = !{!1, !1, i64 0, i64 1}
!1 = !{!"const int", !2}
!2 = !{!"const char", !3, i64 1}
!3 = !{!"char", !4}
!4 = !{!"root"}

This is a problem since in the old scalar tbaa metadata !{!"char", !2, i64 1} meant "immutable const char" but after the upgrade it means struct const_char with a char at offset 1. IOW, given what you said, I don't think the auto-upgrade path is correct.

I think we only check the immutable bit on the tag node (not the type nodes).

Manman

[manmanren]

In D26438#591227, @sanjoy wrote:

In D26438#591194, @mehdi_amini wrote:

When did we stop using the "old" form? We don't need to preserve an auto-upgrade forever, as long as we can simply drop metadata for old bitcodes this is as valid alternative.

We've had the auto upgrade logic for what looks like approximately 3 years. I think it is reasonable to deprecate the functionality and eventually remove it, though I know (from off-list emails) that it will break (in terms of performance, not correctness) downstream users.

Can you explain more on why it will break downstream users in terms of performance?

Cheers,
Manman

However, I'm trying to point that, given what I understand so far, we're miscompiling programs today. This makes me wonder if I'm missing something.

[sanjoy]

In D26438#591399, @manmanren wrote:

There is this bit of language in the TBAA implementation:

// The second field is the access type node, it
// must be a scalar type node.

but in the TBAA metadata generated by clang it seems like we have access types like !{!"int", !N, i64 0} which look like struct nodes.

Can you give an example where clang generates a struct path tag node where the 2nd field is not a scalar type node?

That seems to be the case everywhere. E.g.

struct S {
     int i;
     float f;
};

float f(struct S* s) {
     return s->f;
}

compiles to

; ModuleID = 'x.c'
source_filename = "x.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.12.0"

%struct.S = type { i32, float }

; Function Attrs: norecurse nounwind readonly ssp uwtable
define float @f(%struct.S* nocapture readonly %s) local_unnamed_addr #0 {
entry:
  %f = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1
  %0 = load float, float* %f, align 4, !tbaa !2
  ret float %0
}

attributes #0 = { ... }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (http://llvm.org/git/clang.git b74377b0a34a33cb3c7b565f0e543cd3e56b3f6b) (llvm/trunk 286280)"}
!2 = !{!3, !7, i64 4}
!3 = !{!"S", !4, i64 0, !7, i64 4}
!4 = !{!"int", !5, i64 0}
!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}
!7 = !{!"float", !5, i64 0}

The tag for the load instruction is !2 whose access type is !7 == !{!"float", !5, i64 0}.

I think we only check the immutable bit on the tag node (not the type nodes).

You're right -- that's what the implementation does; but that constraint is not mentioned in the langref or the file comment in the TBAA implementation (so just by reading the docs and comments it would seem like it is okay to mark type nodes as immutable, and even if that is a no-op today, it may help in the future). But I will happily change the spec to conform to the implementation here since it makes life simpler. :)

[sanjoy]

In D26438#591400, @manmanren wrote:

In D26438#591227, @sanjoy wrote:

In D26438#591194, @mehdi_amini wrote:

When did we stop using the "old" form? We don't need to preserve an auto-upgrade forever, as long as we can simply drop metadata for old bitcodes this is as valid alternative.

We've had the auto upgrade logic for what looks like approximately 3 years. I think it is reasonable to deprecate the functionality and eventually remove it, though I know (from off-list emails) that it will break (in terms of performance, not correctness) downstream users.

Can you explain more on why it will break downstream users in terms of performance?

I meant if we go by Mehdi's strategy of dropping old style tbaa metadata instead of auto-upgrading them then downstream users who generate the old style tbaa metadata will no longer get the benefit of TBAA. Their code will be correctly compiled, but will run slower.

[manmanren]

In D26438#591405, @sanjoy wrote:

In D26438#591400, @manmanren wrote:

In D26438#591227, @sanjoy wrote:

In D26438#591194, @mehdi_amini wrote:

When did we stop using the "old" form? We don't need to preserve an auto-upgrade forever, as long as we can simply drop metadata for old bitcodes this is as valid alternative.

We've had the auto upgrade logic for what looks like approximately 3 years. I think it is reasonable to deprecate the functionality and eventually remove it, though I know (from off-list emails) that it will break (in terms of performance, not correctness) downstream users.

Can you explain more on why it will break downstream users in terms of performance?

I meant if we go by Mehdi's strategy of dropping old style tbaa metadata instead of auto-upgrading them then downstream users who generate the old style tbaa metadata will no longer get the benefit of TBAA. Their code will be correctly compiled, but will run slower.

Got it!

[manmanren]

In D26438#591404, @sanjoy wrote:

In D26438#591399, @manmanren wrote:

There is this bit of language in the TBAA implementation:

// The second field is the access type node, it
// must be a scalar type node.

but in the TBAA metadata generated by clang it seems like we have access types like !{!"int", !N, i64 0} which look like struct nodes.

Can you give an example where clang generates a struct path tag node where the 2nd field is not a scalar type node?

That seems to be the case everywhere. E.g.

struct S {
     int i;
     float f;
};

float f(struct S* s) {
     return s->f;
}

compiles to

; ModuleID = 'x.c'
source_filename = "x.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.12.0"

%struct.S = type { i32, float }

; Function Attrs: norecurse nounwind readonly ssp uwtable
define float @f(%struct.S* nocapture readonly %s) local_unnamed_addr #0 {
entry:
  %f = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1
  %0 = load float, float* %f, align 4, !tbaa !2
  ret float %0
}

attributes #0 = { ... }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (http://llvm.org/git/clang.git b74377b0a34a33cb3c7b565f0e543cd3e56b3f6b) (llvm/trunk 286280)"}
!2 = !{!3, !7, i64 4}
!3 = !{!"S", !4, i64 0, !7, i64 4}
!4 = !{!"int", !5, i64 0}
!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}
!7 = !{!"float", !5, i64 0}

The tag for the load instruction is !2 whose access type is !7 == !{!"float", !5, i64 0}.

!7 is a scalar type node, it is a float, right?

Manman

[sanjoy]

In D26438#591414, @manmanren wrote:

The tag for the load instruction is !2 whose access type is !7 == !{!"float", !5, i64 0}.

!7 is a scalar type node, it is a float, right?

Perhaps we are talking past each other, but are you concluding that it is scalar by looking at its name? I thought the names themselves were not supposed to be significant within the TBAA type system.

Structurally, it is exactly a struct that with a single char field. If I compile

struct S {
     int i;
     float f;
};

struct S2 {
     char c;
};

float f(struct S* s, struct S2* s2) {
     return s->f + s2->c;
}

then I get:

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (http://llvm.org/git/clang.git b74377b0a34a33cb3c7b565f0e543cd3e56b3f6b) (llvm/trunk 286280)"}
!2 = !{!3, !7, i64 4}
!3 = !{!"S", !4, i64 0, !7, i64 4}
!4 = !{!"int", !5, i64 0}
!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}
!7 = !{!"float", !5, i64 0}
!8 = !{!9, !5, i64 0}
!9 = !{!"S2", !5, i64 0}

with !2 as the access tag for s->f and !8 as the access tag for s2->c. !2 has !7 as its access type (which means it must be a scalar type), which is indistinguishable from the struct type node !9, except from its name. Without a priori knowledge of what "float" and "S2" mean, we can't conclude one way or the other.

[mehdi_amini]

We've had the auto upgrade logic for what looks like approximately 3 years. I think it is reasonable to deprecate the functionality and eventually remove it, though I know (from off-list emails) that it will break (in terms of performance, not correctness) downstream users.

Can you explain more on why it will break downstream users in terms of performance?

I meant if we go by Mehdi's strategy of dropping old style tbaa metadata instead of auto-upgrading them then downstream users who generate the old style tbaa metadata will no longer get the benefit of TBAA. Their code will be correctly compiled, but will run slower.

Right, we can does not mean we should. I'd only do it if it simplifies your work and clean-up code. If it is well contained and isolated let's just keep it.

[manmanren]

In D26438#591415, @sanjoy wrote:

In D26438#591414, @manmanren wrote:

The tag for the load instruction is !2 whose access type is !7 == !{!"float", !5, i64 0}.

!7 is a scalar type node, it is a float, right?

Perhaps we are talking past each other, but are you concluding that it is scalar by looking at its name? I thought the names themselves were not supposed to be significant within the TBAA type system.

Structurally, it is exactly a struct that with a single char field. If I compile

struct S {
     int i;
     float f;
};

struct S2 {
     char c;
};

float f(struct S* s, struct S2* s2) {
     return s->f + s2->c;
}

then I get:

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (http://llvm.org/git/clang.git b74377b0a34a33cb3c7b565f0e543cd3e56b3f6b) (llvm/trunk 286280)"}
!2 = !{!3, !7, i64 4}
!3 = !{!"S", !4, i64 0, !7, i64 4}
!4 = !{!"int", !5, i64 0}
!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C/C++ TBAA"}
!7 = !{!"float", !5, i64 0}
!8 = !{!9, !5, i64 0}
!9 = !{!"S2", !5, i64 0}

with !2 as the access tag for s->f and !8 as the access tag for s2->c. !2 has !7 as its access type (which means it must be a scalar type), which is indistinguishable from the struct type node !9, except from its name. Without a priori knowledge of what "float" and "S2" mean, we can't conclude one way or the other.

I got your point now. In path-aware TBAA, you can't tell if a type node is a struct type node with a single field or a scalar type node by looking at the format of the single MDNode. The formats are uniform to make implementation easy. You can tell from the usage case. If it is the 2nd field of a struct tag node, it should be a scalar node. Being a scalar node means we don't have to check the offset (the offset should be zero).

Hope this clears things up,
Manman

[sanjoy]

You can tell from the usage case. If it is the 2nd field of a struct tag node, it should be a scalar node. Being a scalar node means we don't have to check the offset (the offset should be zero).

Given that, what do you think of the verification rule this patch has right now -- access types must satisfy IsScalarLikeTBAANode?

[sanjoy]

Hi all (esp. @manmanren ),

Are you happy with the general direction here? If so, I'll start writing some FileCheck unit tests (I don't want to sink time into tests if there we are likely going to see major corrections here).

[manmanren]

In D26438#593369, @sanjoy wrote:

Hi all (esp. @manmanren ),

Are you happy with the general direction here? If so, I'll start writing some FileCheck unit tests (I don't want to sink time into tests if there we are likely going to see major corrections here).

Yes, thanks for cleaning things up.

Manamn

[sanjoy]

• Add unit tests
• Minor NFC code-cleanup changes

[manmanren]

The rest looks pretty reasonable.

Manman

lib/IR/Verifier.cpp

3971

This seems somewhat heavy-weighted. I guess you are trying to differentiate a scalar type node from a struct type node with a single field, given that both can have 3 operands with the 2nd operand being a type and the 3rd being an offset. I don't think you can really differentiate the two cases. I feel like checking the offset being zero for the access type node of a tag should be enough.

I will not call them *singular" struct type node, since they are scalar type node.

createTBAAScalarTypeNode will generate such a scalar type node with 3 operands, createTBAANode (which is not used in clang any more) can generate a scalar type node with 2 operands.

[sanjoy]

lib/IR/Verifier.cpp

3971

Hi Manman,

I'd like to keep the recursive nature of this check and not just check
the offset only on the MDNode for the access tag.

IOW, I'd like to avoid invalid cases where the access tag has a full
blown struct type descriptor at offset 0, since in such (invalid)
cases getMostGenericTBAA will produce bad merged metadata that would
be hard to debug:

;; Invalid metadata that I want the verifier to reject

!root = !{!"C++ TBAA"}
!int = !{!"int", !root}
!float = !{!"float", !root}
!s_a = !{"s_a", !int, 5, !float, 20}
!s_b = !{"s_b", !int, 6, !float, 20}

!scalar_a = !{!"scalar-a", !s_a, 0}
!scalar_b = !{!"scalar-b", !s_b, 0}

!tag_a = !{!some_struct, !scalar_a, 20}
!tag_b = !{!some_struct, !scalar_b, 20}

!tag_c = !{!float, !float, 0}

!generic_tag = !{!int, !int, 0}

Both !tag_a and !tag_b should may-alias with !tag_c, but
getMostGenericTBAA will merge !tag_a and !tag_b into
!generic_tag which does not alias with !tag_c.

However, I'm happy to call replace "singular" with "scalar".

[manmanren]

Thanks for the work!

Manman

lib/IR/Verifier.cpp

3875

Is this necessary given that we just checked BaseNode is not in TBAABaseNodes?

3971

Sounds good. More checking means fewer bugs.
Please rename singular to scalar and add a testing case for the above example if it is not in the patch.

[sanjoy]

• Address review

lib/IR/Verifier.cpp

3875

No, it is redundant, which is why it is an assert and not an Assert. :)

3971

Renamed and added a test case.

[sanjoy]

• clang-format

[manmanren]

Thanks,

Manman

lib/IR/Verifier.cpp

private:
   }
 
   void Write(const Comdat *C) {
     if (!C)
       return;
     *OS << *C;
   }
 
+  void Write(const APInt *AI) {
+    if (!AI)
+      return;
+    *OS << *AI;
+  }
+
   template <typename T> void Write(ArrayRef<T> Vs) {
     for (const T &V : Vs)
       Write(V);
   }
 
   template <typename T1, typename... Ts>
   void WriteTs(const T1 &V1, const Ts &... Vs) {
     Write(V1);
class Verifier : public InstVisitor<Verifier>, VerifierSupport {
   SmallVector<const Function *, 4> DeoptimizeDeclarations;
 
   // Verify that this GlobalValue is only used in this module.
   // This map is used to avoid visiting uses twice. We can arrive at a user
   // twice, if they have multiple operands. In particular for very large
   // constant expressions, we can arrive at a particular user many times.
   SmallPtrSet<const Value *, 32> 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<bool, unsigned> TBAABaseNodeSummary;
+  DenseMap<MDNode *, TBAABaseNodeSummary> TBAABaseNodes;
+
   void checkAtomicMemAccessSize(Type *Ty, const Instruction *I);
 
 public:
   explicit Verifier(raw_ostream *OS, bool ShouldTreatBrokenDebugInfoAsError,
                     const Module &M)
       : VerifierSupport(OS, M), LandingPadResultTy(nullptr),
         SawFrameEscape(false) {
     TreatBrokenDebugInfoAsError = ShouldTreatBrokenDebugInfoAsError;
private:
   void visitValueAsMetadata(const ValueAsMetadata &MD, Function *F);
   void visitComdat(const Comdat &C);
   void visitModuleIdents(const Module &M);
   void visitModuleFlags(const Module &M);
   void visitModuleFlag(const MDNode *Op,
                        DenseMap<const MDString *, const MDNode *> &SeenIDs,
                        SmallVectorImpl<const MDNode *> &Requirements);
   void visitFunction(const Function &F);
   void visitBasicBlock(BasicBlock &BB);
   void visitRangeMetadata(Instruction &I, MDNode *Range, Type *Ty);
   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 <class Ty> bool isValidMetadataArray(const MDTuple &N);
 #define HANDLE_SPECIALIZED_MDNODE_LEAF(CLASS) void visit##CLASS(const CLASS &N);
 #include "llvm/IR/Metadata.def"
   void visitDIScope(const DIScope &N);
   void visitDIVariable(const DIVariable &N);
   void visitDILexicalBlockBase(const DILexicalBlockBase &N);
   void visitDITemplateParameter(const DITemplateParameter &N);
 
if (NumRanges > 2) {
     ConstantRange FirstRange(FirstLow, FirstHigh);
     Assert(FirstRange.intersectWith(LastRange).isEmptySet(),
            "Intervals are overlapping", Range);
     Assert(!isContiguous(FirstRange, LastRange), "Intervals are contiguous",
            Range);
   }
 }
 
+/// 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<MDNode>(BaseNode->getOperand(1))) {
+      CheckFailed("Invalid parent operand in scalar TBAA node", &I, BaseNode);
+      return InvalidNode;
+    }
+    if (!isa<MDString>(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<APInt> 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<MDNode>(FieldTy)) {
+      CheckFailed("Incorrect field entry in struct type node!", &I, BaseNode);
+      Failed = true;
+      continue;
+    }
+
+    auto *OffsetEntryCI =
+        mdconst::dyn_extract_or_null<ConstantInt>(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 IsScalarTBAANode(const MDNode *MD) {
+  return MD->getNumOperands() == 2;
+}
+
+static bool IsRootTBAANode(const MDNode *MD) {
+  return MD->getNumOperands() < 2;
+}
+
+static bool IsScalarOrRootTBAANode(const MDNode *MD) {
+  return IsScalarTBAANode(MD) || IsRootTBAANode(MD);
+}
+
+static bool IsSingularStructTBAANode(const MDNode *MD,
+                                     SmallPtrSetImpl<const MDNode *> &Visited) {
+  if (MD->getNumOperands() != 3)
+    return false;
+
+  auto *Offset = mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
+  if (!(Offset && Offset->isZero() && isa<MDString>(MD->getOperand(0))))
+    return false;
+
+  auto *Parent = dyn_cast<MDNode>(MD->getOperand(1));
+  return Visited.insert(Parent).second && IsRootTBAANode(Parent) ||
+         IsSingularStructTBAANode(Parent, Visited);
+}
+
+static bool IsScalarLikeTBAANode(const MDNode *MD) {
+  SmallPtrSet<const MDNode *, 4> Visited;
+  return IsScalarTBAANode(MD) || IsSingularStructTBAANode(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<MDNode>(BaseNode->getOperand(1));
+
+  for (unsigned Idx = 1; Idx < BaseNode->getNumOperands(); Idx += 2) {
+    auto *OffsetEntryCI =
+        mdconst::extract<ConstantInt>(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<ConstantInt>(BaseNode->getOperand(Idx - 1));
+      Offset -= PrevOffsetEntryCI->getValue();
+      return cast<MDNode>(BaseNode->getOperand(Idx - 2));
+    }
+  }
+
+  auto *LastOffsetEntryCI = mdconst::extract<ConstantInt>(
+      BaseNode->getOperand(BaseNode->getNumOperands() - 1));
+
+  Offset -= LastOffsetEntryCI->getValue();
+  return cast<MDNode>(BaseNode->getOperand(BaseNode->getNumOperands() - 2));
+}
+
 void Verifier::checkAtomicMemAccessSize(Type *Ty, const Instruction *I) {
   unsigned Size = DL.getTypeSizeInBits(Ty);
   Assert(Size >= 8, "atomic memory access' size must be byte-sized", Ty, I);
   Assert(!(Size & (Size - 1)),
          "atomic memory access' operand must have a power-of-two size", Ty, I);
 }
 
 void Verifier::visitLoadInst(LoadInst &LI) {

 
 void Verifier::visitTBAAMetadata(Instruction &I, MDNode *MD) {
   bool IsStructPathTBAA =
       isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
 
   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<MDNode>(MD->getOperand(0));
+  MDNode *AccessType = dyn_cast_or_null<MDNode>(MD->getOperand(1));
+
+  if (MD->getNumOperands() == 4) {
+    auto *IsImmutableCI =
+        mdconst::dyn_extract_or_null<ConstantInt>(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(IsScalarLikeTBAANode(AccessType),
+         "Access type node must be scalar-like", &I, MD, AccessType);
+
+  auto *OffsetCI = mdconst::dyn_extract_or_null<ConstantInt>(MD->getOperand(2));
+  Assert(OffsetCI, "Offset must be constant integer", &I, MD);
+
+  APInt Offset = OffsetCI->getValue();
+  bool SeenAccessTypeInPath = false;
+
+  SmallPtrSet<MDNode *, 4> 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;
+
+    Assert(BaseNodeBitWidth == Offset.getBitWidth() ||
+               (BaseNodeBitWidth == 0 && Offset == 0),
+           "Access bit-width not the same as description bit-width", &I, MD);
+
+    SeenAccessTypeInPath |= BaseNode == AccessType;
+
+    if (IsScalarTBAANode(BaseNode) || BaseNode == AccessType)
+      Assert(Offset == 0, "Offset not zero at the point of scalar access", &I,
+             MD, &Offset);
+  }
+
+  Assert(SeenAccessTypeInPath, "Did not see access type in access path!", &I,
+         MD);
 }
 
 /// verifyInstruction - Verify that an instruction is well formed.
 ///
 void Verifier::visitInstruction(Instruction &I) {
   BasicBlock *BB = I.getParent();
   Assert(BB, "Instruction not embedded in basic block!", &I);
 
if (Instruction *Used = dyn_cast<Instruction>(U.getUser()))
              "Instruction referencing"
              " instruction not embedded in a basic block!",
              &I, Used);
     else {
       CheckFailed("Use of instruction is not an instruction!", U);
       return;
     }
   }
 
   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
     Assert(I.getOperand(i) != nullptr, "Instruction has null operand!", &I);
 
     // Check to make sure that only first-class-values are operands to
     // instructions.
     if (!I.getOperand(i)->getType()->isFirstClassType()) {
       Assert(false, "Instruction operands must be first-class values!", &I);
     }
void Verifier::visitInstruction(Instruction &I) {
   }
 
   if (MDNode *MD = I.getMetadata(LLVMContext::MD_dereferenceable))
     visitDereferenceableMetadata(I, MD);
 
   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<LoadInst>(I) || isa<StoreInst>(I) || isa<CallInst>(I) ||
+               isa<VAArgInst>(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",
            &I);
     Assert(isa<LoadInst>(I), "align applies only to load instructions, "
            "use attributes for calls or invokes", &I);
     Assert(AlignMD->getNumOperands() == 1, "align takes one operand!", &I);
     ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(AlignMD->getOperand(0));

test/Analysis/BasicAA/full-store-partial-alias.ll

entry:
   %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* %tmp4, i64 0, i64 %idxprom
   %tmp5 = load i32, i32* %arrayidx, align 4, !tbaa !3
   %tmp5.lobit = lshr i32 %tmp5, 31
   ret i32 %tmp5.lobit
 }
 
 !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}

test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll

entry:
   %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* %tmp4, i64 0, i64 %idxprom
   %tmp5 = load i32, i32* %arrayidx, align 4, !tbaa !3
   %tmp5.lobit = lshr i32 %tmp5, 31
   ret i32 %tmp5.lobit
 }
 
 !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}

test/Analysis/TypeBasedAliasAnalysis/aliastest.ll

 
 ; Invariant memory.
 !5 = !{!11, !11, i64 0, i1 1}
 ; Not invariant memory.
 !6 = !{!11, !11, i64 0, i1 0}
 !7 = !{ !"foo", !0 }
 !8 = !{ !"bar", !0 }
 !9 = !{ !"foo", !0 }
-!10 = !{ !"bar", !"different" }
+!10 = !{ !"bar", !12 }
 !11 = !{ !"qux", !0}
+!12 = !{!"different"}

test/Analysis/TypeBasedAliasAnalysis/cyclic.ll

 ; RUN: not opt -instcombine < %s 2>&1 | FileCheck %s
-; CHECK: Cycle found in TBAA metadata.
+; CHECK: Access type node must be scalar-like
 
 define void @test6(i32* %gi) #0 {
 entry:
   store i32 42, i32* %gi, align 4, !tbaa !0
   br label %for.cond
 
 for.cond:                                         ; preds = %for.body, %entry
   br i1 undef, label %for.body, label %for.end

test/Analysis/TypeBasedAliasAnalysis/dse.ll

 
 ; Invariant memory.
 !5 = !{!11, !11, i64 0, i1 1}
 ; Not invariant memory.
 !6 = !{!11, !11, i64 0, i1 0}
 !7 = !{ !"foo", !0 }
 !8 = !{ !"bar", !0 }
 !9 = !{ !"foo", !0 }
-!10 = !{ !"bar", !"different" }
+!10 = !{ !"bar", !12}
 !11 = !{ !"qux", !0}
+!12 = !{!"different"}

test/Analysis/TypeBasedAliasAnalysis/dynamic-indices.ll

for.end:                                          ; preds = %for.body
   %tmp10 = load float, float* %f9, align 4, !tbaa !5
   ret float %tmp10
 }
 
 ; CHECK: [[TAG]] = !{[[TYPE_LL:!.*]], [[TYPE_LL]], i64 0}
 ; 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}
 !6 = !{!"short", !1}
 !7 = !{!"long long", !1}
 !8 = !{!"int", !1}
 !9 = !{!"float", !1}

test/Analysis/TypeBasedAliasAnalysis/gvn-nonlocal-type-mismatch.ll

 
 !0 = !{}
 !1 = !{!5, !5, i64 0}
 !2 = !{!6, !6, i64 0}
 !3 = !{!7, !7, i64 0}
 !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"}

test/Analysis/TypeBasedAliasAnalysis/intrinsics.ll

 
 declare <8 x i16> @llvm.arm.neon.vld1.v8i16.p0i8(i8*, i32) nounwind readonly
 declare void @llvm.arm.neon.vst1.p0i8.v8i16(i8*, <8 x i16>, i32) nounwind
 
 ; CHECK: attributes #0 = { argmemonly nounwind readonly }
 ; 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}
 !4 = !{!"B", !0}

test/Analysis/TypeBasedAliasAnalysis/licm.ll

for.body:                                         ; preds = %entry, %for.body
   %inc = add i64 %i.07, 1
   %exitcond = icmp eq i64 %inc, %n
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
-!0 = !{!"root", null}
+!0 = !{!"root"}
 !1 = !{!6, !6, i64 0}
 !2 = !{!7, !7, i64 0}
 
 ; LICM shouldn't hoist anything here.
 
 ; CHECK: @bar
 ; CHECK: loop:
 ; CHECK: load
loop:
   store i8* %tmp51, i8** %p
   %tmp40 = load i8, i8* %q, !tbaa !5
   store i8 %tmp40, i8* %q
   br label %loop
 }
 
 !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}

test/Analysis/TypeBasedAliasAnalysis/memcpyopt.ll

define void @foo(i8* nocapture %p, i8* nocapture %q, i8* nocapture %s) nounwind {
   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %q, i8* %p, i64 16, i32 1, i1 false), !tbaa !2
   ret void
 }
 
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32, i1) nounwind
 
 ; 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}
 !4 = !{!"B", !0}

test/CodeGen/ARM/2011-05-04-MultipleLandingPadSuccs.ll

 declare i32 @__gxx_personality_sj0(...)
 
 declare void @_Unwind_SjLj_Resume_or_Rethrow(i8*)
 
 declare void @_ZSt9terminatev()
 
 !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}

test/Instrumentation/AddressSanitizer/X86/bug_11395.ll

entry:
   %sub = sub nsw i32 0, %blocksize
   store i32 %sub, i32* %blocksize.addr, align 4, !tbaa !3
   %2 = call { i32*, i32*, i32* } asm sideeffect "1:                           \0A\09xor           %esi, %esi\0A\09xor           %ecx, %ecx\0A\09jmp  *$5                     \0A\09ff_mlp_firorder_8:            \0A\09mov   0x1c+0($0), %eax\0A\09imull 0x1c+0($1)       \0A\09add                %eax , %esi\0A\09adc                %edx , %ecx\0A\09ff_mlp_firorder_7:            \0A\09mov   0x18+0($0), %eax\0A\09imull 0x18+0($1)       \0A\09add                %eax , %esi\0A\09adc                %edx , %ecx\0A\09ff_mlp_firorder_6:            \0A\09mov   0x14+0($0), %eax\0A\09imull 0x14+0($1)       \0A\09add                %eax , %esi\0A\09adc                %edx , %ecx\0A\09ff_mlp_firorder_5:            \0A\09mov   0x10+0($0), %eax\0A\09imull 0x10+0($1)       \0A\09add                %eax , %esi\0A\09adc                %edx , %ecx\0A\09ff_mlp_firorder_4:            \0A\09mov   0x0c+0($0), %eax\0A\09imull 0x0c+0($1)       \0A\09add                %eax , %esi\0A\09adc                %edx , %ecx\0A\09ff_mlp_firorder_3:            \0A\09mov   0x08+0($0), %eax\0A\09imull 0x08+0($1)       \0A\09add                %eax , %esi\0A\09adc                %edx , %ecx\0A\09ff_mlp_firorder_2:            \0A\09mov   0x04+0($0), %eax\0A\09imull 0x04+0($1)       \0A\09add                %eax , %esi\0A\09adc                %edx , %ecx\0A\09ff_mlp_firorder_1:            \0A\09mov   0x00+0($0), %eax\0A\09imull 0x00+0($1)       \0A\09add                %eax , %esi\0A\09adc                %edx , %ecx\0A\09ff_mlp_firorder_0:\0A\09jmp  *$6                     \0A\09ff_mlp_iirorder_4:            \0A\09mov   0x0c+4*(8 + (40 * 4))($0), %eax\0A\09imull 0x0c+4* 8($1)       \0A\09add                %eax , %esi\0A\09adc                %edx , %ecx\0A\09ff_mlp_iirorder_3:            \0A\09mov   0x08+4*(8 + (40 * 4))($0), %eax\0A\09imull 0x08+4* 8($1)       \0A\09add                %eax , %esi\0A\09adc                %edx , %ecx\0A\09ff_mlp_iirorder_2:            \0A\09mov   0x04+4*(8 + (40 * 4))($0), %eax\0A\09imull 0x04+4* 8($1)       \0A\09add                %eax , %esi\0A\09adc                %edx , %ecx\0A\09ff_mlp_iirorder_1:            \0A\09mov   0x00+4*(8 + (40 * 4))($0), %eax\0A\09imull 0x00+4* 8($1)       \0A\09add                %eax , %esi\0A\09adc                %edx , %ecx\0A\09ff_mlp_iirorder_0:\0A\09mov           %ecx, %edx\0A\09mov           %esi, %eax\0A\09movzbl        $7   , %ecx\0A\09shrd    %cl, %edx, %eax\0A\09mov  %eax  ,%edx      \0A\09add  ($2)      ,%eax     \0A\09and   $4       ,%eax     \0A\09sub   $$4       ,  $0         \0A\09mov  %eax, ($0)        \0A\09mov  %eax, ($2)        \0A\09add $$4* 8    ,  $2         \0A\09sub  %edx   ,%eax     \0A\09mov  %eax,4*(8 + (40 * 4))($0)  \0A\09incl              $3         \0A\09js 1b                        \0A\09", "=r,=r,=r,=*m,*m,*m,*m,*m,0,1,2,*m,~{eax},~{edx},~{esi},~{ecx},~{dirflag},~{fpsr},~{flags}"(i32* %blocksize.addr, i32* %mask.addr, i8** %firjump, i8** %iirjump, i32* %filter_shift.addr, i32* %state, i32* %coeff, i32* %sample_buffer, i32* %blocksize.addr) nounwind, !srcloc !4
   ret void
 }
 
 !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}
 !6 = !{!"int", !1}

test/Instrumentation/ThreadSanitizer/read_from_global.ll

 
 ; CHECK: define void @call_virtual_func
 ; CHECK: __tsan_vptr_read
 ; CHECK: = load
 ; CHECK-NOT: __tsan_read
 ; 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}

test/Instrumentation/ThreadSanitizer/vptr_read.ll

 ; RUN: opt < %s -tsan -S | FileCheck %s
 ; Check that vptr reads are treated in a special way.
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 define i8 @Foo(i8* %a) nounwind uwtable sanitize_thread {
 entry:
 ; CHECK: call void @__tsan_vptr_read
   %0 = load i8, i8* %a, align 8, !tbaa !0
   ret i8 %0
 }
 !0 = !{!2, !2, i64 0}
-!1 = !{!"Simple C/C++ TBAA", null}
+!1 = !{!"Simple C/C++ TBAA"}
 !2 = !{!"vtable pointer", !1}

test/Instrumentation/ThreadSanitizer/vptr_update.ll

 ; CHECK: call void @__tsan_vptr_update{{.*}}Func1
 ; CHECK-NOT: call void @__tsan_vptr_update
 ; CHECK: ret void
   store <2 x i8 *> <i8* bitcast(i32 ()* @Func1 to i8 *), i8* bitcast(i32 ()* @Func2 to i8 *)>,  <2 x i8 *>* %a, align 8, !tbaa !0
   ret void
 }
 
 !0 = !{!2, !2, i64 0}
-!1 = !{!"Simple C/C++ TBAA", null}
+!1 = !{!"Simple C/C++ TBAA"}
 !2 = !{!"vtable pointer", !1}

test/Transforms/GVN/PRE/preserve-tbaa.ll

for.body:                                         ; preds = %for.body, %bb.nph
   br i1 false, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 !0 = !{!3, !3, i64 0}
 !1 = !{!"omnipotent char", !2}
-!2 = !{!"Simple C/C++ TBAA", null}
+!2 = !{!"Simple C/C++ TBAA"}
 !3 = !{!"short", !1}

test/Transforms/GVN/tbaa.ll

 ; CHECK: [[TAGC]] = !{[[TYPEC:!.*]], [[TYPEC]], i64 0}
 ; CHECK: [[TYPEC]] = !{!"C", [[TYPEA:!.*]]}
 ; CHECK: [[TYPEA]] = !{!"A", !{{.*}}}
 ; CHECK: [[TAGB]] = !{[[TYPEB:!.*]], [[TYPEB]], i64 0}
 ; CHECK: [[TYPEB]] = !{!"B", [[TYPEA]]}
 ; 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
 !9 = !{!"yet another root"}
 !10 = !{!"node", !9, i64 1}
 

test/Transforms/InstCombine/load-combine-metadata.ll

 !0 = !{ i32 0, i32 5 }
 !1 = !{ i32 7, i32 9 }
 !2 = !{!2}
 !3 = !{!3, !2}
 !4 = !{!4, !2}
 !5 = !{!3}
 !6 = !{!4}
 !7 = !{ !"tbaa root" }
-!8 = !{ !7, !7, i64 0 }
+!8 = !{ !9, !9, i64 0 }
+!9 = !{ !"scalar type", !7}

test/Transforms/InstCombine/loadstore-metadata.ll

entry:
   %l = load float, float* %ptr, !tbaa !0
   %c = bitcast float %l to i32
   ret i32 %c
 }
 
 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
 }
 
 define float @test_load_cast_combine_range(i32* %ptr) {
 ; Ensure (cast (load (...))) -> (load (cast (...))) drops range metadata. It
 ; would be nice to preserve or update it somehow but this is hard when moving
 ; between types.
 ; CHECK-LABEL: @test_load_cast_combine_range(
 ; CHECK: load float, float* %{{.*}}
 ; 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
 }
 
 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
 }
 
 define i32 @test_load_cast_combine_nontemporal(float* %ptr) {
 ; 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
 }
 
 define i8* @test_load_cast_combine_align(i32** %ptr) {
 ; 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
 }
 
 define i8* @test_load_cast_combine_deref(i32** %ptr) {
 ; 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
 }
 
 define i8* @test_load_cast_combine_deref_or_null(i32** %ptr) {
 ; 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
 }
 
 define void @test_load_cast_combine_loop(float* %src, i32* %dst, i32 %n) {
 ; 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
 
 loop:
   %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
   %cmp = icmp slt i32 %i.next, %n
   br i1 %cmp, label %loop, label %exit, !llvm.loop !1
 
 exit:
   ret void

 ; have the tests break. For now, this function must always come last in this
 ; file, and no LABEL lines are to be added after this point.
 ;
 ; CHECK-LABEL: @test_load_cast_combine_nonnull(
 ; CHECK: %[[V:.*]] = load i64, i64* %{{.*}}, !range ![[MD:[0-9]+]]
 ; 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
 }
 
 ; 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}

test/Transforms/InstCombine/tbaa-store-to-load.ll

 ; RUN: opt -S -instcombine < %s 2>&1 | FileCheck %s
 
 define i64 @f(i64* %p1, i64* %p2) {
 top:
   ; check that the tbaa is preserved
   ; CHECK-LABEL: @f(
   ; CHECK: %v1 = load i64, i64* %p1, align 8, !tbaa !0
   ; CHECK: store i64 %v1, i64* %p2, align 8
   ; CHECK: ret i64 %v1
   %v1 = load i64, i64* %p1, align 8, !tbaa !0
   store i64 %v1, i64* %p2, align 8
   %v2 = load i64, i64* %p2, align 8
   ret i64 %v2
 }
 
 !0 = !{!1, !1, i64 0}
-!1 = !{!"load_tbaa"}
+!1 = !{!"scalar type", !2}
+!2 = !{!"load_tbaa"}

test/Transforms/JumpThreading/thread-loads.ll

 
 ret2:
   %xxx = tail call i32 (...) @f1() nounwind
   ret void
 }
 
 !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 }
 !6 = !{!6}
 !7 = !{!7, !6}
 !8 = !{!8, !6}
 !9 = !{!7}
 !10 = !{!8}

test/Transforms/LICM/2011-04-06-PromoteResultOfPromotion.ll

for.body:                                         ; preds = %entry, %for.inc
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:                                          ; preds = %for.inc
   ret void
 }
 
 !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}
 !6 = !{!"int", !1}

test/Transforms/SLPVectorizer/X86/crash_scheduling.ll

-; 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"
 
 define void @_foo(double %p1, double %p2, double %p3) #0 {
 entry:
   %tab1 = alloca [256 x i32], align 16
   %tab2 = alloca [256 x i32], align 16

test/Transforms/SimplifyCFG/basictest.ll

 ; CHECK-NEXT: load i8, i8* %r, align 1, !dbg !{{[0-9]+$}}
 
 bb0:
   %r = alloca i8, align 1
   %tmp = call i8 @test6g(i8* %r)
   %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:
   br label %bb3
 bb3:
   %tmp6 = phi i8 [ 0, %bb2 ], [ 1, %bb1 ]
   ret i8 %tmp6
 }
 declare i8 @test6g(i8*)
 
 !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)
 !4 = !{}
 !5 = !DILocation(line: 23, scope: !6)
 !6 = distinct !DISubprogram(name: "foo", scope: !3, file: !7, line: 1, type: !DISubroutineType(types: !4), isLocal: false, isDefinition: true, scopeLine: 1, flags: DIFlagPrototyped, isOptimized: false, unit: !3, variables: !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}

test/Transforms/Util/store-first-op.ll

 !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 3.8.0 (https://github.com/llvm-mirror/clang 89dda3855cda574f355e6defa1d77bdae5053994) (llvm/trunk 257597)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug)
 !1 = !DIFile(filename: "none", directory: ".")
 !2 = !{i32 2, !"Debug Info Version", i32 3}
 !3 = !DILocalVariable(name: "getU", scope: !4, file: !1, line: 25, type: !5)
 !4 = distinct !DISubprogram(name: "multiply64", linkageName: "_ZN4llvm13ScaledNumbers10multiply64Emm", scope: null, file: !1, line: 22, isLocal: false, isDefinition: true, scopeLine: 23, flags: DIFlagPrototyped, isOptimized: true, unit: !0)
 !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}