Unit tests for TBAA metadata generation.

[sepavloff]

Summary

Now tests for metadata created by clang involve compiling code snippets
placed into c/c++ source files and matching interesting patterns in the
obtained textual representation of IR. Writting such tests is a painful
process as metadata often form complex tree-like structures but textual
representation of IR contains only a pile of metadata at the module end.

This change implements IR matchers that may be used to match required
patterns in the binary IR representation. In this case the metadata
structure is not broken and creation of match patterns is easier.

The change adds unit tests for TBAA metadata generation.

[rjmccall]

Interesting. Okay, LGTM.

cfe/trunk/unittests/CodeGen/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Core
   Support
   )
 
 add_clang_unittest(ClangCodeGenTests
   BufferSourceTest.cpp
   CodeGenExternalTest.cpp
   IncrementalProcessingTest.cpp
+  TBAAMetadataTest.cpp
   )
 
 target_link_libraries(ClangCodeGenTests
   PRIVATE
   clangAST
   clangBasic
   clangCodeGen
   clangFrontend
   clangLex
   clangParse
   )

cfe/trunk/unittests/CodeGen/IRMatchers.h

+//=== unittests/CodeGen/IRMatchers.h - Match on the LLVM IR -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file provides a simple mechanism for performing search operations over
+/// IR including metadata and types. It allows writing complex search patterns
+/// using understandable syntax. For instance, the code:
+///
+/// \code
+///       const BasicBlock *BB = ...
+///       const Instruction *I = match(BB,
+///           MInstruction(Instruction::Store,
+///               MConstInt(4, 8),
+///               MMTuple(
+///                   MMTuple(
+///                       MMString("omnipotent char"),
+///                       MMTuple(
+///                           MMString("Simple C/C++ TBAA")),
+///                       MConstInt(0, 64)),
+///                   MSameAs(0),
+///                   MConstInt(0))));
+/// \endcode
+///
+/// searches the basic block BB for the 'store' instruction, first argument of
+/// which is 'i8 4', and the attached metadata has an item described by the
+/// given tree.
+//===----------------------------------------------------------------------===//
+
+#ifndef CLANG_UNITTESTS_CODEGEN_IRMATCHERS_H
+#define CLANG_UNITTESTS_CODEGEN_IRMATCHERS_H
+
+#include "llvm/ADT/PointerUnion.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Metadata.h"
+#include "llvm/IR/Value.h"
+
+namespace llvm {
+
+/// Keeps information about pending match queries.
+///
+/// This class stores state of all unfinished match actions. It allows to
+/// use queries like "this operand is the same as n-th operand", which are
+/// hard to implement otherwise.
+///
+class MatcherContext {
+public:
+
+  /// Describes pending match query.
+  ///
+  /// The query is represented by the current entity being investigated (type,
+  /// value or metadata). If the entity is a member of a list (like arguments),
+  /// the query also keeps the entity number in that list.
+  ///
+  class Query {
+    PointerUnion3<const Value *, const Metadata *, const Type *> Entity;
+    unsigned OperandNo;
+
+  public:
+    Query(const Value *V, unsigned N) : Entity(V), OperandNo(N) {}
+    Query(const Metadata *M, unsigned N) : Entity(M), OperandNo(N) {}
+    Query(const Type *T, unsigned N) : Entity(T), OperandNo(N) {}
+
+    template<typename T>
+    const T *get() const {
+      return Entity.dyn_cast<const T *>();
+    }
+
+    unsigned getOperandNo() const { return OperandNo; }
+  };
+
+  template<typename T>
+  void push(const T *V, unsigned N = ~0) {
+    MatchStack.push_back(Query(V, N));
+  }
+
+  void pop() { MatchStack.pop_back(); }
+
+  template<typename T>
+  const T *top() const { return MatchStack.back().get<T>(); }
+
+  size_t size() const { return MatchStack.size(); }
+
+  unsigned getOperandNo() const { return MatchStack.back().getOperandNo(); }
+
+  /// Returns match query at the given offset from the top of queries.
+  ///
+  /// Offset 0 corresponds to the topmost query.
+  ///
+  const Query &getQuery(unsigned Offset) const {
+    assert(MatchStack.size() > Offset);
+    return MatchStack[MatchStack.size() - 1 - Offset];
+  }
+
+private:
+  SmallVector<Query, 8> MatchStack;
+};
+
+
+/// Base of all matcher classes.
+///
+class Matcher {
+public:
+  virtual ~Matcher() {}
+
+  /// Returns true if the entity on the top of the specified context satisfies
+  /// the matcher condition.
+  ///
+  virtual bool match(MatcherContext &MC) = 0;
+};
+
+
+/// Base class of matchers that test particular entity.
+///
+template<typename T>
+class EntityMatcher : public Matcher {
+public:
+  bool match(MatcherContext &MC) override {
+    if (auto V = MC.top<T>())
+      return matchEntity(*V, MC);
+    return false;
+  }
+  virtual bool matchEntity(const T &M, MatcherContext &C) = 0;
+};
+
+
+/// Matcher that matches any entity of the specified kind.
+///
+template<typename T>
+class AnyMatcher : public EntityMatcher<T> {
+public:
+  bool matchEntity(const T &M, MatcherContext &C) override { return true; }
+};
+
+
+/// Matcher that tests if the current entity satisfies the specified
+/// condition.
+///
+template<typename T>
+class CondMatcher : public EntityMatcher<T> {
+  std::function<bool(const T &)> Condition;
+public:
+  CondMatcher(std::function<bool(const T &)> C) : Condition(C) {}
+  bool matchEntity(const T &V, MatcherContext &C) override {
+    return Condition(V);
+  }
+};
+
+
+/// Matcher that save pointer to the entity that satisfies condition of the
+// specified matcher.
+///
+template<typename T>
+class SavingMatcher : public EntityMatcher<T> {
+  const T *&Var;
+  std::shared_ptr<Matcher> Next;
+public:
+  SavingMatcher(const T *&V, std::shared_ptr<Matcher> N) : Var(V), Next(N) {}
+  bool matchEntity(const T &V, MatcherContext &C) override {
+    bool Result = Next->match(C);
+    if (Result)
+      Var = &V;
+    return Result;
+  }
+};
+
+
+/// Matcher that checks that the entity is identical to another entity in the
+/// same container.
+///
+class SameAsMatcher : public Matcher {
+  unsigned OpNo;
+public:
+  SameAsMatcher(unsigned N) : OpNo(N) {}
+  bool match(MatcherContext &C) override {
+    if (C.getOperandNo() != ~0U) {
+      // Handle all known containers here.
+      const MatcherContext::Query &StackRec = C.getQuery(1);
+      if (const Metadata *MR = StackRec.get<Metadata>()) {
+        if (const auto *MT = dyn_cast<MDTuple>(MR)) {
+          if (OpNo < MT->getNumOperands())
+            return C.top<Metadata>() == MT->getOperand(OpNo).get();
+          return false;
+        }
+        llvm_unreachable("Unknown metadata container");
+      }
+      if (const Value *VR = StackRec.get<Value>()) {
+        if (const auto *Insn = dyn_cast<Instruction>(VR)) {
+          if (OpNo < Insn->getNumOperands())
+            return C.top<Value>() == Insn->getOperand(OpNo);
+          return false;
+        }
+        llvm_unreachable("Unknown value container");
+      }
+      llvm_unreachable("Unknown type container");
+    }
+    return false;
+  }
+};
+
+
+/// Matcher that tests if the entity is a constant integer.
+///
+class ConstantIntMatcher : public Matcher {
+  uint64_t IntValue;
+  unsigned Width;
+public:
+  ConstantIntMatcher(uint64_t V, unsigned W = 0) : IntValue(V), Width(W) {}
+  bool match(MatcherContext &Ctx) override {
+    if (const Value *V = Ctx.top<Value>()) {
+      if (const auto *CI = dyn_cast<ConstantInt>(V))
+        return (Width == 0 || CI->getBitWidth() == Width) &&
+               CI->getLimitedValue() == IntValue;
+    }
+    if (const Metadata *M = Ctx.top<Metadata>()) {
+      if (const auto *MT = dyn_cast<ValueAsMetadata>(M))
+        if (const auto *C = dyn_cast<ConstantInt>(MT->getValue()))
+          return (Width == 0 || C->getBitWidth() == Width) &&
+                 C->getLimitedValue() == IntValue;
+    }
+    return false;
+  }
+};
+
+
+/// Value matcher tuned to test instructions.
+///
+class InstructionMatcher : public EntityMatcher<Value> {
+  SmallVector<std::shared_ptr<Matcher>, 8> OperandMatchers;
+  std::shared_ptr<EntityMatcher<Metadata>> MetaMatcher = nullptr;
+  unsigned Code;
+public:
+  InstructionMatcher(unsigned C) : Code(C) {}
+
+  void push(std::shared_ptr<EntityMatcher<Metadata>> M) {
+    assert(!MetaMatcher && "Only one metadata matcher may be specified");
+    MetaMatcher = M;
+  }
+  void push(std::shared_ptr<Matcher> V) { OperandMatchers.push_back(V); }
+  template<typename... Args>
+  void push(std::shared_ptr<Matcher> V, Args... A) {
+    push(V);
+    push(A...);
+  }
+
+  virtual bool matchInstruction(const Instruction &I) {
+    return I.getOpcode() == Code;
+  }
+
+  bool matchEntity(const Value &V, MatcherContext &C) override {
+    if (const auto *I = dyn_cast<Instruction>(&V)) {
+      if (!matchInstruction(*I))
+        return false;
+      if (OperandMatchers.size() > I->getNumOperands())
+        return false;
+      for (unsigned N = 0, E = OperandMatchers.size(); N != E; ++N) {
+        C.push(I->getOperand(N), N);
+        if (!OperandMatchers[N]->match(C)) {
+          C.pop();
+          return false;
+        }
+        C.pop();
+      }
+      if (MetaMatcher) {
+        SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
+        I->getAllMetadata(MDs);
+        bool Found = false;
+        for (auto Item : MDs) {
+          C.push(Item.second);
+          if (MetaMatcher->match(C)) {
+            Found = true;
+            C.pop();
+            break;
+          }
+          C.pop();
+        }
+        return Found;
+      }
+      return true;
+    }
+    return false;
+  }
+};
+
+
+/// Matcher that tests type of the current value using the specified
+/// type matcher.
+///
+class ValueTypeMatcher : public EntityMatcher<Value> {
+  std::shared_ptr<EntityMatcher<Type>> TyM;
+public:
+  ValueTypeMatcher(std::shared_ptr<EntityMatcher<Type>> T) : TyM(T) {}
+  ValueTypeMatcher(const Type *T)
+    : TyM(new CondMatcher<Type>([T](const Type &Ty) -> bool {
+                                  return &Ty == T;
+                                })) {}
+  bool matchEntity(const Value &V, MatcherContext &Ctx) override {
+    Type *Ty = V.getType();
+    Ctx.push(Ty);
+    bool Res = TyM->match(Ctx);
+    Ctx.pop();
+    return Res;
+  }
+};
+
+
+/// Matcher that matches string metadata.
+///
+class NameMetaMatcher : public EntityMatcher<Metadata> {
+  StringRef Name;
+public:
+  NameMetaMatcher(StringRef N) : Name(N) {}
+  bool matchEntity(const Metadata &M, MatcherContext &C) override {
+    if (auto *MDS = dyn_cast<MDString>(&M))
+      return MDS->getString().equals(Name);
+    return false;
+  }
+};
+
+
+/// Matcher that matches metadata tuples.
+///
+class MTupleMatcher : public EntityMatcher<Metadata> {
+  SmallVector<std::shared_ptr<Matcher>, 4> Operands;
+public:
+  void push(std::shared_ptr<Matcher> M) { Operands.push_back(M); }
+  template<typename... Args>
+  void push(std::shared_ptr<Matcher> M, Args... A) {
+    push(M);
+    push(A...);
+  }
+  bool matchEntity(const Metadata &M, MatcherContext &C) override {
+    if (const auto *MT = dyn_cast<MDTuple>(&M)) {
+      if (MT->getNumOperands() != Operands.size())
+        return false;
+      for (unsigned I = 0, E = MT->getNumOperands(); I != E; ++I) {
+        const MDOperand &Op = MT->getOperand(I);
+        C.push(Op.get(), I);
+        if (!Operands[I]->match(C)) {
+          C.pop();
+          return false;
+        }
+        C.pop();
+      }
+      return true;
+    }
+    return false;
+  }
+};
+
+
+// Helper function used to construct matchers.
+
+std::shared_ptr<Matcher> MSameAs(unsigned N) {
+  return std::shared_ptr<Matcher>(new SameAsMatcher(N));
+}
+
+template<typename... T>
+std::shared_ptr<InstructionMatcher> MInstruction(unsigned C, T... Args) {
+  auto Result = new InstructionMatcher(C);
+  Result->push(Args...);
+  return std::shared_ptr<InstructionMatcher>(Result);
+}
+
+std::shared_ptr<Matcher> MConstInt(uint64_t V, unsigned W = 0) {
+  return std::shared_ptr<Matcher>(new ConstantIntMatcher(V, W));
+}
+
+std::shared_ptr<EntityMatcher<Value>>
+ MValType(std::shared_ptr<EntityMatcher<Type>> T) {
+  return std::shared_ptr<EntityMatcher<Value>>(new ValueTypeMatcher(T));
+}
+
+std::shared_ptr<EntityMatcher<Value>> MValType(const Type *T) {
+  return std::shared_ptr<EntityMatcher<Value>>(new ValueTypeMatcher(T));
+}
+
+std::shared_ptr<EntityMatcher<Type>>
+MType(std::function<bool(const Type &)> C) {
+  return std::shared_ptr<EntityMatcher<Type>>(new CondMatcher<Type>(C));
+}
+
+std::shared_ptr<EntityMatcher<Metadata>> MMAny() {
+  return std::shared_ptr<EntityMatcher<Metadata>>(new AnyMatcher<Metadata>);
+}
+
+std::shared_ptr<EntityMatcher<Metadata>>
+MMSave(const Metadata *&V, std::shared_ptr<EntityMatcher<Metadata>> M) {
+  return std::shared_ptr<EntityMatcher<Metadata>>(
+      new SavingMatcher<Metadata>(V, M));
+}
+
+std::shared_ptr<EntityMatcher<Metadata>>
+MMString(const char *Name) {
+  return std::shared_ptr<EntityMatcher<Metadata>>(new NameMetaMatcher(Name));
+}
+
+template<typename... T>
+std::shared_ptr<EntityMatcher<Metadata>> MMTuple(T... Args) {
+  auto Res = new MTupleMatcher();
+  Res->push(Args...);
+  return std::shared_ptr<EntityMatcher<Metadata>>(Res);
+}
+
+
+/// Looks for the instruction that satisfies condition of the specified
+/// matcher inside the given basic block.
+/// \returns Pointer to the found instruction or nullptr if such instruction
+///          was not found.
+///
+const Instruction *match(const BasicBlock *BB, std::shared_ptr<Matcher> M) {
+  MatcherContext MC;
+  for (const auto &I : *BB) {
+    MC.push(&I);
+    if (M->match(MC))
+      return &I;
+    MC.pop();
+  }
+  assert(MC.size() == 0);
+  return nullptr;
+}
+
+
+/// Looks for the instruction that satisfies condition of the specified
+/// matcher starting from the specified instruction inside the same basic block.
+///
+/// The given instruction is not checked.
+///
+const Instruction *matchNext(const Instruction *I, std::shared_ptr<Matcher> M) {
+  if (!I)
+    return nullptr;
+  MatcherContext MC;
+  const BasicBlock *BB = I->getParent();
+  if (!BB)
+    return nullptr;
+  for (auto P = ++BasicBlock::const_iterator(I), E = BB->end(); P != E; ++P) {
+    MC.push(&*P);
+    if (M->match(MC))
+      return &*P;
+    MC.pop();
+  }
+  assert(MC.size() == 0);
+  return nullptr;
+}
+
+}
+#endif

cfe/trunk/unittests/CodeGen/TBAAMetadataTest.cpp

+//=== unittests/CodeGen/TBAAMetadataTest.cpp - Checks metadata generation -===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "IRMatchers.h"
+#include "clang/AST/ASTConsumer.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/CodeGen/ModuleBuilder.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Parse/ParseAST.h"
+#include "llvm/ADT/Triple.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "gtest/gtest.h"
+#include <memory>
+
+using namespace llvm;
+
+namespace {
+
+struct TestCompiler {
+  LLVMContext Context;
+  clang::CompilerInstance compiler;
+  clang::CodeGenerator *CG = nullptr;
+  llvm::Module *M = nullptr;
+  unsigned PtrSize = 0;
+
+  void init(const char *TestProgram) {
+    compiler.createDiagnostics();
+    compiler.getCodeGenOpts().StructPathTBAA = 1;
+    compiler.getCodeGenOpts().OptimizationLevel = 1;
+
+    std::string TrStr = llvm::Triple::normalize(llvm::sys::getProcessTriple());
+    llvm::Triple Tr(TrStr);
+    Tr.setOS(Triple::Linux);
+    Tr.setVendor(Triple::VendorType::UnknownVendor);
+    Tr.setEnvironment(Triple::EnvironmentType::UnknownEnvironment);
+    compiler.getTargetOpts().Triple = Tr.getTriple();
+    compiler.setTarget(clang::TargetInfo::CreateTargetInfo(
+        compiler.getDiagnostics(),
+        std::make_shared<clang::TargetOptions>(compiler.getTargetOpts())));
+
+    const clang::TargetInfo &TInfo = compiler.getTarget();
+    PtrSize = TInfo.getPointerWidth(0) / 8;
+
+    compiler.createFileManager();
+    compiler.createSourceManager(compiler.getFileManager());
+    compiler.createPreprocessor(clang::TU_Prefix);
+
+    compiler.createASTContext();
+
+    CG = CreateLLVMCodeGen(
+        compiler.getDiagnostics(),
+        "main-module",
+        compiler.getHeaderSearchOpts(),
+        compiler.getPreprocessorOpts(),
+        compiler.getCodeGenOpts(),
+        Context);
+    compiler.setASTConsumer(std::unique_ptr<clang::ASTConsumer>(CG));
+
+    compiler.createSema(clang::TU_Prefix, nullptr);
+
+    clang::SourceManager &sm = compiler.getSourceManager();
+    sm.setMainFileID(sm.createFileID(
+        llvm::MemoryBuffer::getMemBuffer(TestProgram), clang::SrcMgr::C_User));
+  }
+
+  const BasicBlock *compile() {
+    clang::ParseAST(compiler.getSema(), false, false);
+    M = CG->GetModule();
+
+    // Do not expect more than one function definition.
+    auto FuncPtr = M->begin();
+    for (; FuncPtr != M->end(); ++FuncPtr)
+      if (!FuncPtr->isDeclaration())
+        break;
+    assert(FuncPtr != M->end());
+    const llvm::Function &Func = *FuncPtr;
+    ++FuncPtr;
+    for (; FuncPtr != M->end(); ++FuncPtr)
+      if (!FuncPtr->isDeclaration())
+        break;
+    assert(FuncPtr == M->end());
+
+    // The function must consist of single basic block.
+    auto BBPtr = Func.begin();
+    assert(Func.begin() != Func.end());
+    const BasicBlock &BB = *BBPtr;
+    ++BBPtr;
+    assert(BBPtr == Func.end());
+
+    return &BB;
+  }
+};
+
+
+auto OmnipotentCharC = MMTuple(
+  MMString("omnipotent char"),
+  MMTuple(
+    MMString("Simple C/C++ TBAA")),
+  MConstInt(0, 64)
+);
+
+
+auto OmnipotentCharCXX = MMTuple(
+  MMString("omnipotent char"),
+  MMTuple(
+    MMString("Simple C++ TBAA")),
+  MConstInt(0, 64)
+);
+
+
+TEST(TBAAMetadataTest, BasicTypes) {
+  const char TestProgram[] = R"**(
+    void func(char *CP, short *SP, int *IP, long long *LP, void **VPP,
+              int **IPP) {
+      *CP = 4;
+      *SP = 11;
+      *IP = 601;
+      *LP = 604;
+      *VPP = CP;
+      *IPP = IP;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().C11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MConstInt(4, 8),
+        MMTuple(
+          OmnipotentCharC,
+          MSameAs(0),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(11, 16),
+        MMTuple(
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MSameAs(0),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(601, 32),
+        MMTuple(
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MSameAs(0),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(604, 64),
+        MMTuple(
+          MMTuple(
+            MMString("long long"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MSameAs(0),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MValType(Type::getInt8PtrTy(Compiler.Context)),
+        MMTuple(
+          MMTuple(
+            MMString("any pointer"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MSameAs(0),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MValType(Type::getInt32PtrTy(Compiler.Context)),
+        MMTuple(
+          MMTuple(
+            MMString("any pointer"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MSameAs(0),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+}
+
+TEST(TBAAMetadataTest, CFields) {
+  const char TestProgram[] = R"**(
+    struct ABC {
+       short f16;
+       int f32;
+       long long f64;
+       unsigned short f16_2;
+       unsigned f32_2;
+       unsigned long long f64_2;
+    };
+
+    void func(struct ABC *A) {
+      A->f32 = 4;
+      A->f16 = 11;
+      A->f64 = 601;
+      A->f16_2 = 22;
+      A->f32_2 = 77;
+      A->f64_2 = 604;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().C11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  auto StructABC = MMTuple(
+    MMString("ABC"),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharC,
+      MConstInt(0)),
+    MConstInt(0),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharC,
+      MConstInt(0)),
+    MConstInt(4),
+    MMTuple(
+      MMString("long long"),
+      OmnipotentCharC,
+      MConstInt(0)),
+    MConstInt(8),
+    MSameAs(1),
+    MConstInt(16),
+    MSameAs(3),
+    MConstInt(20),
+    MSameAs(5),
+    MConstInt(24));
+
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MConstInt(4, 32),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(4))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(11, 16),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(601, 64),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("long long"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(8))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(22, 16),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(16))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(77, 32),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(20))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(604, 64),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("long long"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(24))));
+  ASSERT_TRUE(I);
+}
+
+TEST(TBAAMetadataTest, CTypedefFields) {
+  const char TestProgram[] = R"**(
+    typedef struct {
+       short f16;
+       int f32;
+    } ABC;
+    typedef struct {
+       short value_f16;
+       int value_f32;
+    } CDE;
+
+    void func(ABC *A, CDE *B) {
+      A->f32 = 4;
+      A->f16 = 11;
+      B->value_f32 = 44;
+      B->value_f16 = 111;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().C11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  auto NamelessStruct = MMTuple(
+    MMString(""),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharC,
+      MConstInt(0)),
+    MConstInt(0),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharC,
+      MConstInt(0)),
+    MConstInt(4));
+
+  const Metadata *MetaABC = nullptr;
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MConstInt(4, 32),
+        MMTuple(
+          MMSave(MetaABC, NamelessStruct),
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(4))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(11, 16),
+        MMTuple(
+          NamelessStruct,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  const Metadata *MetaCDE = nullptr;
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(44, 32),
+        MMTuple(
+          MMSave(MetaCDE, NamelessStruct),
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(4))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(111, 16),
+        MMTuple(
+          NamelessStruct,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  // FIXME: Nameless structures used in definitions of 'ABC' and 'CDE' are
+  // different structures and must be described by different descriptors.
+  //ASSERT_TRUE(MetaABC != MetaCDE);
+}
+
+TEST(TBAAMetadataTest, CTypedefFields2) {
+  const char TestProgram[] = R"**(
+    typedef struct {
+       short f16;
+       int f32;
+    } ABC;
+    typedef struct {
+       short f16;
+       int f32;
+    } CDE;
+
+    void func(ABC *A, CDE *B) {
+      A->f32 = 4;
+      A->f16 = 11;
+      B->f32 = 44;
+      B->f16 = 111;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().C11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  auto NamelessStruct = MMTuple(
+    MMString(""),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharC,
+      MConstInt(0)),
+    MConstInt(0),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharC,
+      MConstInt(0)),
+    MConstInt(4));
+
+  const Metadata *MetaABC = nullptr;
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MConstInt(4, 32),
+        MMTuple(
+          MMSave(MetaABC, NamelessStruct),
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(4))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(11, 16),
+        MMTuple(
+          NamelessStruct,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  const Metadata *MetaCDE = nullptr;
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(44, 32),
+        MMTuple(
+          MMSave(MetaCDE, NamelessStruct),
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(4))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(111, 16),
+        MMTuple(
+          NamelessStruct,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  // FIXME: Nameless structures used in definitions of 'ABC' and 'CDE' are
+  // different structures, although they have the same field sequence. They must
+  // be described by different descriptors.
+  //ASSERT_TRUE(MetaABC != MetaCDE);
+}
+
+TEST(TBAAMetadataTest, CTypedefFields3) {
+  const char TestProgram[] = R"**(
+    typedef struct {
+       short f16;
+       int f32;
+    } ABC;
+    typedef struct {
+       int f32;
+       short f16;
+    } CDE;
+
+    void func(ABC *A, CDE *B) {
+      A->f32 = 4;
+      A->f16 = 11;
+      B->f32 = 44;
+      B->f16 = 111;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().C11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  auto NamelessStruct1 = MMTuple(
+    MMString(""),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharC,
+      MConstInt(0)),
+    MConstInt(0),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharC,
+      MConstInt(0)),
+    MConstInt(4));
+
+  auto NamelessStruct2 = MMTuple(
+    MMString(""),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharC,
+      MConstInt(0)),
+    MConstInt(0),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharC,
+      MConstInt(0)),
+    MConstInt(4));
+
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MConstInt(4, 32),
+        MMTuple(
+          NamelessStruct1,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(4))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(11, 16),
+        MMTuple(
+          NamelessStruct1,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(44, 32),
+        MMTuple(
+          NamelessStruct2,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(111, 16),
+        MMTuple(
+          NamelessStruct2,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharC,
+            MConstInt(0)),
+          MConstInt(4))));
+  ASSERT_TRUE(I);
+}
+
+TEST(TBAAMetadataTest, CXXFields) {
+  const char TestProgram[] = R"**(
+    struct ABC {
+       short f16;
+       int f32;
+       long long f64;
+       unsigned short f16_2;
+       unsigned f32_2;
+       unsigned long long f64_2;
+    };
+
+    void func(struct ABC *A) {
+      A->f32 = 4;
+      A->f16 = 11;
+      A->f64 = 601;
+      A->f16_2 = 22;
+      A->f32_2 = 77;
+      A->f64_2 = 604;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().CPlusPlus = 1;
+  Compiler.compiler.getLangOpts().CPlusPlus11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  auto StructABC = MMTuple(
+    MMString("_ZTS3ABC"),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(0),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(4),
+    MMTuple(
+      MMString("long long"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(8),
+    MSameAs(1),
+    MConstInt(16),
+    MSameAs(3),
+    MConstInt(20),
+    MSameAs(5),
+    MConstInt(24));
+
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MConstInt(4, 32),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(4))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(11, 16),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(601, 64),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("long long"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(8))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(22, 16),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(16))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(77, 32),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(20))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(604, 64),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("long long"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(24))));
+  ASSERT_TRUE(I);
+}
+
+TEST(TBAAMetadataTest, CXXTypedefFields) {
+  const char TestProgram[] = R"**(
+    typedef struct {
+       short f16;
+       int f32;
+    } ABC;
+    typedef struct {
+       short value_f16;
+       int value_f32;
+    } CDE;
+
+    void func(ABC *A, CDE *B) {
+      A->f32 = 4;
+      A->f16 = 11;
+      B->value_f32 = 44;
+      B->value_f16 = 111;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().CPlusPlus = 1;
+  Compiler.compiler.getLangOpts().CPlusPlus11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  auto StructABC = MMTuple(
+    MMString("_ZTS3ABC"),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(0),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(4));
+
+  auto StructCDE = MMTuple(
+    MMString("_ZTS3CDE"),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(0),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(4));
+
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MConstInt(4, 32),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(4))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(11, 16),
+        MMTuple(
+          StructABC,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(44, 32),
+        MMTuple(
+          StructCDE,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(4))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(111, 16),
+        MMTuple(
+          StructCDE,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+}
+
+TEST(TBAAMetadataTest, StructureFields) {
+  const char TestProgram[] = R"**(
+    struct Inner {
+      int f32;
+    };
+
+    struct Outer {
+      short f16;
+      Inner b1;
+      Inner b2;
+    };
+
+    void func(Outer *S) {
+      S->f16 = 14;
+      S->b1.f32 = 35;
+      S->b2.f32 = 77;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().CPlusPlus = 1;
+  Compiler.compiler.getLangOpts().CPlusPlus11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  auto StructInner = MMTuple(
+    MMString("_ZTS5Inner"),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(0));
+
+  auto StructOuter = MMTuple(
+    MMString("_ZTS5Outer"),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(0),
+    StructInner,
+    MConstInt(4),
+    MSameAs(3),
+    MConstInt(8));
+
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MConstInt(14, 16),
+        MMTuple(
+          StructOuter,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(35, 32),
+        MMTuple(
+          StructOuter,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(4))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(77, 32),
+        MMTuple(
+          StructOuter,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(8))));
+  ASSERT_TRUE(I);
+}
+
+TEST(TBAAMetadataTest, ArrayFields) {
+  const char TestProgram[] = R"**(
+    struct Inner {
+      int f32;
+    };
+
+    struct Outer {
+      short f16;
+      Inner b1[2];
+    };
+
+    void func(Outer *S) {
+      S->f16 = 14;
+      S->b1[0].f32 = 35;
+      S->b1[1].f32 = 77;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().CPlusPlus = 1;
+  Compiler.compiler.getLangOpts().CPlusPlus11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  auto StructInner = MMTuple(
+    MMString("_ZTS5Inner"),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(0));
+
+  auto StructOuter = MMTuple(
+    MMString("_ZTS5Outer"),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(0),
+    OmnipotentCharCXX,    // FIXME: Info about array field is lost.
+    MConstInt(4));
+
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MConstInt(14, 16),
+        MMTuple(
+          StructOuter,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(35, 32),
+        MMTuple(
+          StructInner,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(77, 32),
+        MMTuple(
+          StructInner,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+}
+
+TEST(TBAAMetadataTest, BaseClass) {
+  const char TestProgram[] = R"**(
+    struct Base {
+      int f32;
+    };
+
+    struct Derived : public Base {
+      short f16;
+    };
+
+    void func(Base *B, Derived *D) {
+      B->f32 = 14;
+      D->f16 = 35;
+      D->f32 = 77;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().CPlusPlus = 1;
+  Compiler.compiler.getLangOpts().CPlusPlus11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  auto ClassBase = MMTuple(
+    MMString("_ZTS4Base"),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(0));
+
+  auto ClassDerived = MMTuple(
+    MMString("_ZTS7Derived"),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(4));
+
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MConstInt(14, 32),
+        MMTuple(
+          ClassBase,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(35, 16),
+        MMTuple(
+          ClassDerived,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(4))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(77, 32),
+        MMTuple(
+          ClassBase,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+}
+
+TEST(TBAAMetadataTest, PolymorphicClass) {
+  const char TestProgram[] = R"**(
+    struct Base {
+      virtual void m1(int *) = 0;
+      int f32;
+    };
+
+    struct Derived : public Base {
+      virtual void m1(int *) override;
+      short f16;
+    };
+
+    void func(Base *B, Derived *D) {
+      B->f32 = 14;
+      D->f16 = 35;
+      D->f32 = 77;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().CPlusPlus = 1;
+  Compiler.compiler.getLangOpts().CPlusPlus11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  auto ClassBase = MMTuple(
+    MMString("_ZTS4Base"),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(Compiler.PtrSize));
+
+  auto ClassDerived = MMTuple(
+    MMString("_ZTS7Derived"),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(Compiler.PtrSize + 4));
+
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MConstInt(14, 32),
+        MMTuple(
+          ClassBase,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(Compiler.PtrSize))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(35, 16),
+        MMTuple(
+          ClassDerived,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(Compiler.PtrSize + 4))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(77, 32),
+        MMTuple(
+          ClassBase,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(Compiler.PtrSize))));
+  ASSERT_TRUE(I);
+}
+
+TEST(TBAAMetadataTest, VirtualBase) {
+  const char TestProgram[] = R"**(
+    struct Base {
+      int f32;
+    };
+
+    struct Derived : public virtual Base {
+      short f16;
+    };
+
+    void func(Base *B, Derived *D) {
+      B->f32 = 14;
+      D->f16 = 35;
+      D->f32 = 77;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().CPlusPlus = 1;
+  Compiler.compiler.getLangOpts().CPlusPlus11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  auto ClassBase = MMTuple(
+    MMString("_ZTS4Base"),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(0));
+
+  auto ClassDerived = MMTuple(
+    MMString("_ZTS7Derived"),
+    MMTuple(
+      MMString("short"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(Compiler.PtrSize));
+
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MConstInt(14, 32),
+        MMTuple(
+          ClassBase,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(35, 16),
+        MMTuple(
+          ClassDerived,
+          MMTuple(
+            MMString("short"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(Compiler.PtrSize))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Load,
+        MMTuple(
+          MMTuple(
+            MMString("vtable pointer"),
+            MMTuple(
+              MMString("Simple C++ TBAA")),
+            MConstInt(0)),
+          MSameAs(0),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(77, 32),
+        MMTuple(
+          ClassBase,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+}
+
+TEST(TBAAMetadataTest, TemplSpec) {
+  const char TestProgram[] = R"**(
+    template<typename T1, typename T2>
+    struct ABC {
+      T1 f1;
+      T2 f2;
+    };
+
+    void func(ABC<double, int> *p) {
+      p->f1 = 12.1;
+      p->f2 = 44;
+    }
+  )**";
+
+  TestCompiler Compiler;
+  Compiler.compiler.getLangOpts().CPlusPlus = 1;
+  Compiler.compiler.getLangOpts().CPlusPlus11 = 1;
+  Compiler.init(TestProgram);
+  const BasicBlock *BB = Compiler.compile();
+
+  auto SpecABC = MMTuple(
+    MMString("_ZTS3ABCIdiE"),
+    MMTuple(
+      MMString("double"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(0),
+    MMTuple(
+      MMString("int"),
+      OmnipotentCharCXX,
+      MConstInt(0)),
+    MConstInt(8));
+
+  const Instruction *I = match(BB,
+      MInstruction(Instruction::Store,
+        MValType(MType([](const Type &T)->bool { return T.isDoubleTy(); })),
+        MMTuple(
+          SpecABC,
+          MMTuple(
+            MMString("double"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(0))));
+  ASSERT_TRUE(I);
+
+  I = matchNext(I,
+      MInstruction(Instruction::Store,
+        MConstInt(44, 32),
+        MMTuple(
+          SpecABC,
+          MMTuple(
+            MMString("int"),
+            OmnipotentCharCXX,
+            MConstInt(0)),
+          MConstInt(8))));
+  ASSERT_TRUE(I);
+}
+}