[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

409

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

4050

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

409

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

4050

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

4026

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

4026

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

3930

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

4026

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

3930

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

4026

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 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 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);
+}
+
+/// 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 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::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);
+
+  auto *OffsetCI = mdconst::dyn_extract_or_null<ConstantInt>(MD->getOperand(2));
+  Assert(OffsetCI, "Offset must be constant integer", &I, MD);
+
+  APInt Offset = OffsetCI->getValue();
+
+  auto IsScalarOrRootNode =
+      [&](const MDNode *MD) { return MD->getNumOperands() <= 2; };
+
+  auto IsRootNode = [&](const MDNode *MD) { return MD->getNumOperands() < 2; };
+
+  bool SeenAccessTypeInPath = false;
+
+  SmallPtrSet<MDNode *, 4> StructPath;
+  StructPath.insert(BaseNode);
+
+  while (!IsRootNode(BaseNode)) {
+    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;
+    BaseNode = getFieldNodeFromTBAABaseNode(I, BaseNode, Offset);
+    if (!StructPath.insert(BaseNode).second) {
+      CheckFailed("Cycle detected in struct path!", &I, MD);
+      return;
+    }
+
+    if (IsScalarOrRootNode(BaseNode) || BaseNode == AccessType) {
+      // Ideally we should have been able to guard this clause just under
+      // IsScalarOrRootNode(BaseNode), but unfortunately we have an ambiguity in
+      // TBAA metadata today -- we don't have a way to tell a scalar node
+      // explicitly denoting its non-constness (resp. constness) and a struct
+      // node with only one field at offset 0 (resp. offset 1).  This means we
+      // can have "access type" nodes for which IsScalarOrRootNode returns
+      // false.
+      Assert(Offset == 0, "Offset not zero at the point of scalar access", &I,
+             MD, &Offset);
+    }
+  }
+
+  SeenAccessTypeInPath |= BaseNode == AccessType;
+  Assert(SeenAccessTypeInPath, "Did not see access type in access path!", &I,
+         MD);
+}
+
 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) {
Assert(isa<LoadInst>(I),
          " instructions, use attributes for calls or invokes", &I);
   Assert(MD->getNumOperands() == 1, "dereferenceable, dereferenceable_or_null "
          "take one operand!", &I);
   ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(MD->getOperand(0));
   Assert(CI && CI->getType()->isIntegerTy(64), "dereferenceable, "
          "dereferenceable_or_null metadata value must be an i64!", &I);
 }
 
-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);
-}
-
 /// 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 (!isa<PHINode>(I)) {   // Check that non-phi nodes are not self referential
     for (User *U : I.users()) {
       Assert(U != (User *)&I || !DT.isReachableFromEntry(BB),
              "Only PHI nodes may reference their own value!", &I);
     }
   }
 
   // Check that void typed values don't have names
   Assert(!I.getType()->isVoidTy() || !I.hasName(),
          "Instruction has a name, but provides a void value!", &I);
 
   // Check that the return value of the instruction is either void or a legal
   // value type.
   Assert(I.getType()->isVoidTy() || I.getType()->isFirstClassType(),
          "Instruction returns a non-scalar type!", &I);
 
   // Check that the instruction doesn't produce metadata. Calls are already
   // checked against the callee type.
   Assert(!I.getType()->isMetadataTy() || isa<CallInst>(I) || isa<InvokeInst>(I),
          "Invalid use of metadata!", &I);
if (ConstantFP *CFP0 =
       Assert(&Accuracy.getSemantics() == &APFloat::IEEEsingle,
              "fpmath accuracy must have float type", &I);
       Assert(Accuracy.isFiniteNonZero() && !Accuracy.isNegative(),
              "fpmath accuracy not a positive number!", &I);
     } else {
       Assert(false, "invalid fpmath accuracy!", &I);
     }
   }
 
   if (MDNode *Range = I.getMetadata(LLVMContext::MD_range)) {
     Assert(isa<LoadInst>(I) || isa<CallInst>(I) || isa<InvokeInst>(I),
            "Ranges are only for loads, calls and invokes!", &I);
     visitRangeMetadata(I, Range, I.getType());
   }
 
   if (I.getMetadata(LLVMContext::MD_nonnull)) {
     Assert(I.getType()->isPointerTy(), "nonnull applies only to pointer types",
            &I);
     Assert(isa<LoadInst>(I),
            "nonnull applies only to load instructions, use attributes"
            " for calls or invokes",
            &I);
   }
 
   if (MDNode *MD = I.getMetadata(LLVMContext::MD_dereferenceable))
     visitDereferenceableMetadata(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 *MD = I.getMetadata(LLVMContext::MD_dereferenceable_or_null))
     visitDereferenceableMetadata(I, MD);
 
-  if (MDNode *MD = I.getMetadata(LLVMContext::MD_tbaa))
-    visitTBAAMetadata(I, MD);
-
   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));
     Assert(CI && CI->getType()->isIntegerTy(64),

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: Did not see access type in access path!
 
 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/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

 }
 
 !3 = !{!"pointer", !8}
 !4 = !{!8, !8, i64 0}
 !5 = !{!9, !9, i64 0}
 !6 = !{!"pointer", !0}
 !7 = !{!"double", !0}
 !8 = !{!"char", !9}
-!9 = !{!"root", null}
+!9 = !{!"root"}

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}
 !5 = !{!"C", !6}
 !6 = !{!"A", !2}
 !7 = !{!"B", !6}
-!8 = !{!"another root", null}
+!8 = !{!"another root"}
 
 
 ;; A TBAA structure who's only point is to have a constant location
 !9 = !{!"yet another root"}
 !10 = !{!"node", !9, i64 1}
 

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