Extract a TBAAVerifier out of the verifier (NFC)

[mehdi_amini]

Summary

This is intended to be used (in a later patch) by the BitcodeReader
to detect invalid TBAA and drop them when loading bitcode, so that
we don't break client that have legacy bitcode with possible invalid
TBAA.

[sanjoy]

This is just code motion, right? If so LGTM.

[mehdi_amini]

The patch was partial (I didn't squash properly before), here is the full one (hopefully)

[mehdi_amini]

In D27838#624648, @sanjoy wrote:

This is just code motion, right? If so LGTM.

Mostly: it is moving the code outside of the anonymous namespace and grouping it in its own class, but yes the body of the function is unchanged, except that visitTBAAMetadata also returns a boolean now (ignored by the verifier).

I didn't upload the full patch before (didn't squash the early refactoring), you may want to look again.

[sanjoy]

lgtm but with one nit inline

llvm/lib/IR/Verifier.cpp

4472 ↗

(On Diff #81708)

I assume you'll add a this->HasFailed = true type thing here later?

Also, I'd mildly prefer using this->Diagnostic instead of Diagnostic, since this is in a macro.

Actually, why is this a macro at all? Can't it be a normal templated function just like VerifierSupport::CheckFailed?

[mehdi_amini]

llvm/lib/IR/Verifier.cpp

4472 ↗

(On Diff #81708)

I assume you'll add a this->HasFailed = true type thing here later?

Not in my plan? I expect to always return false (from the AssertTBAA macro on invalid). I sent you D27839 so you can see how it is used in the Reader.

Actually, why is this a macro at all? Can't it be a normal templated function just like VerifierSupport::CheckFailed?

Good point! Done.

[sanjoy]

llvm/trunk/include/llvm/IR/Verifier.h

68

Minor typo: "return false if an"

llvm/trunk/include/llvm/IR/Verifier.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_VERIFIER_H
 #define LLVM_IR_VERIFIER_H
 
 #include "llvm/IR/PassManager.h"
 
+namespace {
+struct VerifierSupport;
+}
+
 namespace llvm {
 
 class Function;
 class FunctionPass;
 class ModulePass;
 class Module;
 class raw_ostream;
 
+/// Verify that the TBAA Metadatas are valid.
+class TBAAVerifier {
+  VerifierSupport *Diagnostic = nullptr;
+
+  /// Helper to diagnose a failure
+  template <typename... Tys> void CheckFailed(Tys &&... Args);
+
+  /// 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;
+
+  /// \name Helper functions used by \c visitTBAAMetadata.
+  /// @{
+  MDNode *getFieldNodeFromTBAABaseNode(Instruction &I, MDNode *BaseNode,
+                                       APInt &Offset);
+  TBAAVerifier::TBAABaseNodeSummary verifyTBAABaseNode(Instruction &I,
+                                                       MDNode *BaseNode);
+  TBAABaseNodeSummary verifyTBAABaseNodeImpl(Instruction &I, MDNode *BaseNode);
+  /// @}
+
+public:
+  TBAAVerifier(VerifierSupport *Diagnostic = nullptr)
+      : Diagnostic(Diagnostic) {}
+  // Visit an instruction and return true if it is valid, return false it an
+  // invalid TBAA is attached.
+  bool visitTBAAMetadata(Instruction &I, MDNode *MD);
+};
+
 /// \brief Check a function for errors, useful for use when debugging a
 /// pass.
 ///
 /// If there are no errors, the function returns false. If an error is found,
 /// a message describing the error is written to OS (if non-null) and true is
 /// returned.
 bool verifyFunction(const Function &F, raw_ostream *OS = nullptr);
 

llvm/trunk/lib/IR/Verifier.cpp

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;
+  TBAAVerifier TBAAVerifyHelper;
 
   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) {
+        SawFrameEscape(false), TBAAVerifyHelper(this) {
     TreatBrokenDebugInfoAsError = ShouldTreatBrokenDebugInfoAsError;
   }
 
   bool hasBrokenDebugInfo() const { return BrokenDebugInfo; }
 
   bool verify(const Function &F) {
     assert(F.getParent() == &M &&
            "An instance of this class only works with a specific module!");
private:
   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);
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);
 }
 
-/// 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 IsRootTBAANode(const MDNode *MD) {
-  return MD->getNumOperands() < 2;
-}
-
-static bool IsScalarTBAANodeImpl(const MDNode *MD,
-                                 SmallPtrSetImpl<const MDNode *> &Visited) {
-  if (MD->getNumOperands() == 2)
-    return true;
-
-  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) || IsScalarTBAANodeImpl(Parent, Visited));
-}
-
-static bool IsScalarTBAANode(const MDNode *MD) {
-  SmallPtrSet<const MDNode *, 4> Visited;
-  return IsScalarTBAANodeImpl(MD, Visited);
-}
-
-/// Returns the field node at the offset \p Offset in \p BaseNode.  Update \p
-/// Offset in place to be the offset within the field node returned.
-///
-/// We assume we've okayed \p BaseNode via \c verifyTBAABaseNode.
-MDNode *Verifier::getFieldNodeFromTBAABaseNode(Instruction &I, MDNode *BaseNode,
-                                               APInt &Offset) {
-  assert(BaseNode->getNumOperands() >= 2 && "Invalid base node!");
-
-  // Scalar nodes have only one possible "field" -- their parent in the access
-  // hierarchy.  Offset must be zero at this point, but our caller is supposed
-  // to Assert that.
-  if (BaseNode->getNumOperands() == 2)
-    return cast<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::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(IsScalarTBAANode(AccessType), "Access type node must be scalar", &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;
-
-    SeenAccessTypeInPath |= BaseNode == AccessType;
-
-    if (IsScalarTBAANode(BaseNode) || BaseNode == AccessType)
-      Assert(Offset == 0, "Offset not zero at the point of scalar access", &I,
-             MD, &Offset);
-
-    Assert(BaseNodeBitWidth == Offset.getBitWidth() ||
-               (BaseNodeBitWidth == 0 && Offset == 0),
-           "Access bit-width not the same as description bit-width", &I, MD,
-           BaseNodeBitWidth, Offset.getBitWidth());
-  }
-
-  Assert(SeenAccessTypeInPath, "Did not see access type in access path!", &I,
-         MD);
-}
-
 /// verifyInstruction - Verify that an instruction is well formed.
 ///
 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()) {
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 *TBAA = I.getMetadata(LLVMContext::MD_tbaa)) {
-    Assert(isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallInst>(I) ||
-               isa<VAArgInst>(I) || isa<AtomicRMWInst>(I) ||
-               isa<AtomicCmpXchgInst>(I),
-           "TBAA is only for loads, stores and calls!", &I);
-    visitTBAAMetadata(I, TBAA);
-  }
+  if (MDNode *TBAA = I.getMetadata(LLVMContext::MD_tbaa))
+    TBAAVerifyHelper.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));
struct VerifierLegacyPass : public FunctionPass {
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
   }
 };
 
 } // end anonymous namespace
 
+/// Helper to issue failure from the TBAA verification
+template <typename... Tys> void TBAAVerifier::CheckFailed(Tys &&... Args) {
+  if (Diagnostic)
+    return Diagnostic->CheckFailed(Args...);
+}
+
+#define AssertTBAA(C, ...)                                                     \
+  do {                                                                         \
+    if (!(C)) {                                                                \
+      CheckFailed(__VA_ARGS__);                                                \
+      return false;                                                            \
+    }                                                                          \
+  } while (false)
+
+/// 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).
+TBAAVerifier::TBAABaseNodeSummary
+TBAAVerifier::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;
+}
+
+TBAAVerifier::TBAABaseNodeSummary
+TBAAVerifier::verifyTBAABaseNodeImpl(Instruction &I, MDNode *BaseNode) {
+  const TBAAVerifier::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
+                : TBAAVerifier::TBAABaseNodeSummary(false, BitWidth);
+}
+
+static bool IsRootTBAANode(const MDNode *MD) {
+  return MD->getNumOperands() < 2;
+}
+
+static bool IsScalarTBAANodeImpl(const MDNode *MD,
+                                 SmallPtrSetImpl<const MDNode *> &Visited) {
+  if (MD->getNumOperands() == 2)
+    return true;
+
+  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) || IsScalarTBAANodeImpl(Parent, Visited));
+}
+
+static bool IsScalarTBAANode(const MDNode *MD) {
+  SmallPtrSet<const MDNode *, 4> Visited;
+  return IsScalarTBAANodeImpl(MD, Visited);
+}
+
+/// Returns the field node at the offset \p Offset in \p BaseNode.  Update \p
+/// Offset in place to be the offset within the field node returned.
+///
+/// We assume we've okayed \p BaseNode via \c verifyTBAABaseNode.
+MDNode *TBAAVerifier::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));
+}
+
+bool TBAAVerifier::visitTBAAMetadata(Instruction &I, MDNode *MD) {
+  AssertTBAA(isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallInst>(I) ||
+             isa<VAArgInst>(I) || isa<AtomicRMWInst>(I) ||
+             isa<AtomicCmpXchgInst>(I),
+             "TBAA is only for loads, stores and calls!", &I);
+
+  bool IsStructPathTBAA =
+      isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
+
+  AssertTBAA(
+      IsStructPathTBAA,
+      "Old-style TBAA is no longer allowed, use struct-path TBAA instead", &I);
+
+  AssertTBAA(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));
+    AssertTBAA(IsImmutableCI,
+               "Immutability tag on struct tag metadata must be a constant", &I,
+               MD);
+    AssertTBAA(
+        IsImmutableCI->isZero() || IsImmutableCI->isOne(),
+        "Immutability part of the struct tag metadata must be either 0 or 1",
+        &I, MD);
+  }
+
+  AssertTBAA(BaseNode && AccessType,
+             "Malformed struct tag metadata:  base and access-type "
+             "should be non-null and point to Metadata nodes",
+             &I, MD, BaseNode, AccessType);
+
+  AssertTBAA(IsScalarTBAANode(AccessType), "Access type node must be scalar",
+             &I, MD, AccessType);
+
+  auto *OffsetCI = mdconst::dyn_extract_or_null<ConstantInt>(MD->getOperand(2));
+  AssertTBAA(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 false;
+    }
+
+    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 false;
+
+    SeenAccessTypeInPath |= BaseNode == AccessType;
+
+    if (IsScalarTBAANode(BaseNode) || BaseNode == AccessType)
+      AssertTBAA(Offset == 0, "Offset not zero at the point of scalar access",
+                 &I, MD, &Offset);
+
+    AssertTBAA(BaseNodeBitWidth == Offset.getBitWidth() ||
+                   (BaseNodeBitWidth == 0 && Offset == 0),
+               "Access bit-width not the same as description bit-width", &I, MD,
+               BaseNodeBitWidth, Offset.getBitWidth());
+  }
+
+  AssertTBAA(SeenAccessTypeInPath, "Did not see access type in access path!",
+             &I, MD);
+  return true;
+}
+
 char VerifierLegacyPass::ID = 0;
 INITIALIZE_PASS(VerifierLegacyPass, "verify", "Module Verifier", false, false)
 
 FunctionPass *llvm::createVerifierPass(bool FatalErrors) {
   return new VerifierLegacyPass(FatalErrors);
 }
 
 AnalysisKey VerifierAnalysis::Key;