[MS-ABI] Implements MS-compatible RTTI

Enables the emission of MS-compatible RTTI data structures for use with 
typeid, dynamic_cast and exceptions.  Does not implement dynamic_cast 
or exceptions.  As an artiface, typeid works in some cases but proper 
support an testing will coming in a subsequent patch.

majnemer has fuzzed the results.  Test cases included.

Differential Revision: http://reviews.llvm.org/D3833

llvm-svn: 209523

7 files changed, 509 insertions, 46 deletions

diff --git a/clang/lib/AST/MicrosoftMangle.cpp b/clang/lib/AST/MicrosoftMangle.cpp
index 58e14919810..d064b157719 100644
--- a/clang/lib/AST/MicrosoftMangle.cpp
+++ b/clang/lib/AST/MicrosoftMangle.cpp
@@ -113,7 +113,7 @@ public:
   void mangleCXXRTTI(QualType T, raw_ostream &Out) override;
   void mangleCXXRTTIName(QualType T, raw_ostream &Out) override;
   void mangleCXXRTTIBaseClassDescriptor(const CXXRecordDecl *Derived,
-                                        uint32_t NVOffset, uint32_t VBPtrOffset,
+                                        uint32_t NVOffset, int32_t VBPtrOffset,
                                         uint32_t VBTableOffset, uint32_t Flags,
                                         raw_ostream &Out) override;
   void mangleCXXRTTIBaseClassArray(const CXXRecordDecl *Derived,
@@ -2258,7 +2258,7 @@ void MicrosoftMangleContextImpl::mangleCXXRTTIName(QualType T,
 }
 
 void MicrosoftMangleContextImpl::mangleCXXRTTIBaseClassDescriptor(
-    const CXXRecordDecl *Derived, uint32_t NVOffset, uint32_t VBPtrOffset,
+    const CXXRecordDecl *Derived, uint32_t NVOffset, int32_t VBPtrOffset,
     uint32_t VBTableOffset, uint32_t Flags, raw_ostream &Out) {
   MicrosoftCXXNameMangler Mangler(*this, Out);
   Mangler.getStream() << "\01??_R1";
@@ -2267,7 +2267,7 @@ void MicrosoftMangleContextImpl::mangleCXXRTTIBaseClassDescriptor(
   Mangler.mangleNumber(VBTableOffset);
   Mangler.mangleNumber(Flags);
   Mangler.mangleName(Derived);
-  Mangler.getStream() << "@8";
+  Mangler.getStream() << "8";
 }
 
 void MicrosoftMangleContextImpl::mangleCXXRTTIBaseClassArray(
@@ -2275,7 +2275,7 @@ void MicrosoftMangleContextImpl::mangleCXXRTTIBaseClassArray(
   MicrosoftCXXNameMangler Mangler(*this, Out);
   Mangler.getStream() << "\01??_R2";
   Mangler.mangleName(Derived);
-  Mangler.getStream() << "@8";
+  Mangler.getStream() << "8";
 }
 
 void MicrosoftMangleContextImpl::mangleCXXRTTIClassHierarchyDescriptor(
@@ -2283,7 +2283,7 @@ void MicrosoftMangleContextImpl::mangleCXXRTTIClassHierarchyDescriptor(
   MicrosoftCXXNameMangler Mangler(*this, Out);
   Mangler.getStream() << "\01??_R3";
   Mangler.mangleName(Derived);
-  Mangler.getStream() << "@8";
+  Mangler.getStream() << "8";
 }
 
 void MicrosoftMangleContextImpl::mangleCXXRTTICompleteObjectLocator(
diff --git a/clang/lib/CodeGen/CGExpr.cpp b/clang/lib/CodeGen/CGExpr.cpp
index 1f8a804bd73..ba0e468c23d 100644
--- a/clang/lib/CodeGen/CGExpr.cpp
+++ b/clang/lib/CodeGen/CGExpr.cpp
@@ -2086,7 +2086,7 @@ LValue CodeGenFunction::EmitPredefinedLValue(const PredefinedExpr *E) {
 /// integer, 1 for a floating point value, and -1 for anything else.
 llvm::Constant *CodeGenFunction::EmitCheckTypeDescriptor(QualType T) {
   // Only emit each type's descriptor once.
-  if (llvm::Constant *C = CGM.getTypeDescriptor(T))
+  if (llvm::Constant *C = CGM.getTypeDescriptorFromMap(T))
     return C;
 
   uint16_t TypeKind = -1;
@@ -2121,7 +2121,7 @@ llvm::Constant *CodeGenFunction::EmitCheckTypeDescriptor(QualType T) {
   GV->setUnnamedAddr(true);
 
   // Remember the descriptor for this type.
-  CGM.setTypeDescriptor(T, GV);
+  CGM.setTypeDescriptorInMap(T, GV);
 
   return GV;
 }
diff --git a/clang/lib/CodeGen/CGRTTI.cpp b/clang/lib/CodeGen/CGRTTI.cpp
index e6f9a57a09b..4ca315ca249 100644
--- a/clang/lib/CodeGen/CGRTTI.cpp
+++ b/clang/lib/CodeGen/CGRTTI.cpp
@@ -22,7 +22,7 @@ using namespace clang;
 using namespace CodeGen;
 
 namespace {
-class RTTIBuilder {
+class ItaniumRTTIBuilder {
   CodeGenModule &CGM;  // Per-module state.
   llvm::LLVMContext &VMContext;
   
@@ -62,7 +62,7 @@ class RTTIBuilder {
   void BuildPointerToMemberTypeInfo(const MemberPointerType *Ty);
   
 public:
-  RTTIBuilder(CodeGenModule &CGM) : CGM(CGM), 
+  ItaniumRTTIBuilder(CodeGenModule &CGM) : CGM(CGM), 
     VMContext(CGM.getModule().getContext()) { }
 
   // Pointer type info flags.
@@ -110,7 +110,7 @@ public:
 }
 
 llvm::GlobalVariable *
-RTTIBuilder::GetAddrOfTypeName(QualType Ty, 
+ItaniumRTTIBuilder::GetAddrOfTypeName(QualType Ty,
                                llvm::GlobalVariable::LinkageTypes Linkage) {
   SmallString<256> OutName;
   llvm::raw_svector_ostream Out(OutName);
@@ -132,7 +132,8 @@ RTTIBuilder::GetAddrOfTypeName(QualType Ty,
   return GV;
 }
 
-llvm::Constant *RTTIBuilder::GetAddrOfExternalRTTIDescriptor(QualType Ty) {
+llvm::Constant *
+ItaniumRTTIBuilder::GetAddrOfExternalRTTIDescriptor(QualType Ty) {
   // Mangle the RTTI name.
   SmallString<256> OutName;
   llvm::raw_svector_ostream Out(OutName);
@@ -317,8 +318,8 @@ static bool ContainsIncompleteClassType(QualType Ty) {
 
 /// getTypeInfoLinkage - Return the linkage that the type info and type info
 /// name constants should have for the given type.
-static llvm::GlobalVariable::LinkageTypes 
-getTypeInfoLinkage(CodeGenModule &CGM, QualType Ty) {
+llvm::GlobalVariable::LinkageTypes 
+CodeGenModule::getTypeInfoLinkage(QualType Ty) {
   // Itanium C++ ABI 2.9.5p7:
   //   In addition, it and all of the intermediate abi::__pointer_type_info 
   //   structs in the chain down to the abi::__class_type_info for the
@@ -339,7 +340,7 @@ getTypeInfoLinkage(CodeGenModule &CGM, QualType Ty) {
 
   case VisibleNoLinkage:
   case ExternalLinkage:
-    if (!CGM.getLangOpts().RTTI) {
+    if (!getLangOpts().RTTI) {
       // RTTI is not enabled, which means that this type info struct is going
       // to be used for exception handling. Give it linkonce_odr linkage.
       return llvm::GlobalValue::LinkOnceODRLinkage;
@@ -350,7 +351,7 @@ getTypeInfoLinkage(CodeGenModule &CGM, QualType Ty) {
       if (RD->hasAttr<WeakAttr>())
         return llvm::GlobalValue::WeakODRLinkage;
       if (RD->isDynamicClass())
-        return CGM.getVTableLinkage(RD);
+        return getVTableLinkage(RD);
     }
 
     return llvm::GlobalValue::LinkOnceODRLinkage;
@@ -388,7 +389,7 @@ static bool CanUseSingleInheritance(const CXXRecordDecl *RD) {
   return true;
 }
 
-void RTTIBuilder::BuildVTablePointer(const Type *Ty) {
+void ItaniumRTTIBuilder::BuildVTablePointer(const Type *Ty) {
   // abi::__class_type_info.
   static const char * const ClassTypeInfo =
     "_ZTVN10__cxxabiv117__class_type_infoE";
@@ -509,7 +510,7 @@ void RTTIBuilder::BuildVTablePointer(const Type *Ty) {
   Fields.push_back(VTable);
 }
 
-llvm::Constant *RTTIBuilder::BuildTypeInfo(QualType Ty, bool Force) {
+llvm::Constant *ItaniumRTTIBuilder::BuildTypeInfo(QualType Ty, bool Force) {
   // We want to operate on the canonical type.
   Ty = CGM.getContext().getCanonicalType(Ty);
 
@@ -538,7 +539,7 @@ llvm::Constant *RTTIBuilder::BuildTypeInfo(QualType Ty, bool Force) {
   if (IsStdLib)
     Linkage = llvm::GlobalValue::ExternalLinkage;
   else
-    Linkage = getTypeInfoLinkage(CGM, Ty);
+    Linkage = CGM.getTypeInfoLinkage(Ty);
 
   // Add the vtable pointer.
   BuildVTablePointer(cast<Type>(Ty));
@@ -699,18 +700,18 @@ static unsigned ComputeQualifierFlags(Qualifiers Quals) {
   unsigned Flags = 0;
 
   if (Quals.hasConst())
-    Flags |= RTTIBuilder::PTI_Const;
+    Flags |= ItaniumRTTIBuilder::PTI_Const;
   if (Quals.hasVolatile())
-    Flags |= RTTIBuilder::PTI_Volatile;
+    Flags |= ItaniumRTTIBuilder::PTI_Volatile;
   if (Quals.hasRestrict())
-    Flags |= RTTIBuilder::PTI_Restrict;
+    Flags |= ItaniumRTTIBuilder::PTI_Restrict;
 
   return Flags;
 }
 
 /// BuildObjCObjectTypeInfo - Build the appropriate kind of type_info
 /// for the given Objective-C object type.
-void RTTIBuilder::BuildObjCObjectTypeInfo(const ObjCObjectType *OT) {
+void ItaniumRTTIBuilder::BuildObjCObjectTypeInfo(const ObjCObjectType *OT) {
   // Drop qualifiers.
   const Type *T = OT->getBaseType().getTypePtr();
   assert(isa<BuiltinType>(T) || isa<ObjCInterfaceType>(T));
@@ -728,18 +729,18 @@ void RTTIBuilder::BuildObjCObjectTypeInfo(const ObjCObjectType *OT) {
   QualType SuperTy = CGM.getContext().getObjCInterfaceType(Super);
 
   // Everything else is single inheritance.
-  llvm::Constant *BaseTypeInfo = RTTIBuilder(CGM).BuildTypeInfo(SuperTy);
+  llvm::Constant *BaseTypeInfo = ItaniumRTTIBuilder(CGM).BuildTypeInfo(SuperTy);
   Fields.push_back(BaseTypeInfo);
 }
 
 /// BuildSIClassTypeInfo - Build an abi::__si_class_type_info, used for single
 /// inheritance, according to the Itanium C++ ABI, 2.95p6b.
-void RTTIBuilder::BuildSIClassTypeInfo(const CXXRecordDecl *RD) {
+void ItaniumRTTIBuilder::BuildSIClassTypeInfo(const CXXRecordDecl *RD) {
   // Itanium C++ ABI 2.9.5p6b:
   // It adds to abi::__class_type_info a single member pointing to the 
   // type_info structure for the base type,
   llvm::Constant *BaseTypeInfo = 
-    RTTIBuilder(CGM).BuildTypeInfo(RD->bases_begin()->getType());
+    ItaniumRTTIBuilder(CGM).BuildTypeInfo(RD->bases_begin()->getType());
   Fields.push_back(BaseTypeInfo);
 }
 
@@ -768,20 +769,20 @@ static unsigned ComputeVMIClassTypeInfoFlags(const CXXBaseSpecifier *Base,
     if (!Bases.VirtualBases.insert(BaseDecl)) {
       // If this virtual base has been seen before, then the class is diamond
       // shaped.
-      Flags |= RTTIBuilder::VMI_DiamondShaped;
+      Flags |= ItaniumRTTIBuilder::VMI_DiamondShaped;
     } else {
       if (Bases.NonVirtualBases.count(BaseDecl))
-        Flags |= RTTIBuilder::VMI_NonDiamondRepeat;
+        Flags |= ItaniumRTTIBuilder::VMI_NonDiamondRepeat;
     }
   } else {
     // Mark the non-virtual base as seen.
     if (!Bases.NonVirtualBases.insert(BaseDecl)) {
       // If this non-virtual base has been seen before, then the class has non-
       // diamond shaped repeated inheritance.
-      Flags |= RTTIBuilder::VMI_NonDiamondRepeat;
+      Flags |= ItaniumRTTIBuilder::VMI_NonDiamondRepeat;
     } else {
       if (Bases.VirtualBases.count(BaseDecl))
-        Flags |= RTTIBuilder::VMI_NonDiamondRepeat;
+        Flags |= ItaniumRTTIBuilder::VMI_NonDiamondRepeat;
     }
   }
 
@@ -806,7 +807,7 @@ static unsigned ComputeVMIClassTypeInfoFlags(const CXXRecordDecl *RD) {
 /// BuildVMIClassTypeInfo - Build an abi::__vmi_class_type_info, used for
 /// classes with bases that do not satisfy the abi::__si_class_type_info 
 /// constraints, according ti the Itanium C++ ABI, 2.9.5p5c.
-void RTTIBuilder::BuildVMIClassTypeInfo(const CXXRecordDecl *RD) {
+void ItaniumRTTIBuilder::BuildVMIClassTypeInfo(const CXXRecordDecl *RD) {
   llvm::Type *UnsignedIntLTy = 
     CGM.getTypes().ConvertType(CGM.getContext().UnsignedIntTy);
   
@@ -847,7 +848,7 @@ void RTTIBuilder::BuildVMIClassTypeInfo(const CXXRecordDecl *RD) {
   //   };
   for (const auto &Base : RD->bases()) {
     // The __base_type member points to the RTTI for the base type.
-    Fields.push_back(RTTIBuilder(CGM).BuildTypeInfo(Base.getType()));
+    Fields.push_back(ItaniumRTTIBuilder(CGM).BuildTypeInfo(Base.getType()));
 
     const CXXRecordDecl *BaseDecl = 
       cast<CXXRecordDecl>(Base.getType()->getAs<RecordType>()->getDecl());
@@ -882,7 +883,7 @@ void RTTIBuilder::BuildVMIClassTypeInfo(const CXXRecordDecl *RD) {
 
 /// BuildPointerTypeInfo - Build an abi::__pointer_type_info struct,
 /// used for pointer types.
-void RTTIBuilder::BuildPointerTypeInfo(QualType PointeeTy) {  
+void ItaniumRTTIBuilder::BuildPointerTypeInfo(QualType PointeeTy) {
   Qualifiers Quals;
   QualType UnqualifiedPointeeTy = 
     CGM.getContext().getUnqualifiedArrayType(PointeeTy, Quals);
@@ -906,13 +907,14 @@ void RTTIBuilder::BuildPointerTypeInfo(QualType PointeeTy) {
   //  __pointee is a pointer to the std::type_info derivation for the 
   //  unqualified type being pointed to.
   llvm::Constant *PointeeTypeInfo = 
-    RTTIBuilder(CGM).BuildTypeInfo(UnqualifiedPointeeTy);
+    ItaniumRTTIBuilder(CGM).BuildTypeInfo(UnqualifiedPointeeTy);
   Fields.push_back(PointeeTypeInfo);
 }
 
 /// BuildPointerToMemberTypeInfo - Build an abi::__pointer_to_member_type_info 
 /// struct, used for member pointer types.
-void RTTIBuilder::BuildPointerToMemberTypeInfo(const MemberPointerType *Ty) {
+void
+ItaniumRTTIBuilder::BuildPointerToMemberTypeInfo(const MemberPointerType *Ty) {
   QualType PointeeTy = Ty->getPointeeType();
   
   Qualifiers Quals;
@@ -943,14 +945,15 @@ void RTTIBuilder::BuildPointerToMemberTypeInfo(const MemberPointerType *Ty) {
   //   __pointee is a pointer to the std::type_info derivation for the 
   //   unqualified type being pointed to.
   llvm::Constant *PointeeTypeInfo = 
-    RTTIBuilder(CGM).BuildTypeInfo(UnqualifiedPointeeTy);
+    ItaniumRTTIBuilder(CGM).BuildTypeInfo(UnqualifiedPointeeTy);
   Fields.push_back(PointeeTypeInfo);
 
   // Itanium C++ ABI 2.9.5p9:
   //   __context is a pointer to an abi::__class_type_info corresponding to the
   //   class type containing the member pointed to 
   //   (e.g., the "A" in "int A::*").
-  Fields.push_back(RTTIBuilder(CGM).BuildTypeInfo(QualType(ClassType, 0)));
+  Fields.push_back(
+      ItaniumRTTIBuilder(CGM).BuildTypeInfo(QualType(ClassType, 0)));
 }
 
 llvm::Constant *CodeGenModule::GetAddrOfRTTIDescriptor(QualType Ty,
@@ -965,15 +968,17 @@ llvm::Constant *CodeGenModule::GetAddrOfRTTIDescriptor(QualType Ty,
       LangOpts.ObjCRuntime.isGNUFamily())
     return ObjCRuntime->GetEHType(Ty);
 
-  return RTTIBuilder(*this).BuildTypeInfo(Ty);
+  if (getTarget().getCXXABI().isMicrosoft())
+    return getMSTypeDescriptor(Ty);
+  return ItaniumRTTIBuilder(*this).BuildTypeInfo(Ty);
 }
 
 void CodeGenModule::EmitFundamentalRTTIDescriptor(QualType Type) {
   QualType PointerType = Context.getPointerType(Type);
   QualType PointerTypeConst = Context.getPointerType(Type.withConst());
-  RTTIBuilder(*this).BuildTypeInfo(Type, true);
-  RTTIBuilder(*this).BuildTypeInfo(PointerType, true);
-  RTTIBuilder(*this).BuildTypeInfo(PointerTypeConst, true);
+  ItaniumRTTIBuilder(*this).BuildTypeInfo(Type, true);
+  ItaniumRTTIBuilder(*this).BuildTypeInfo(PointerType, true);
+  ItaniumRTTIBuilder(*this).BuildTypeInfo(PointerTypeConst, true);
 }
 
 void CodeGenModule::EmitFundamentalRTTIDescriptors() {
diff --git a/clang/lib/CodeGen/CMakeLists.txt b/clang/lib/CodeGen/CMakeLists.txt
index 8cd5580df98..4b7d51b06fc 100644
--- a/clang/lib/CodeGen/CMakeLists.txt
+++ b/clang/lib/CodeGen/CMakeLists.txt
@@ -60,6 +60,7 @@ add_clang_library(clangCodeGen
   CodeGenTypes.cpp
   ItaniumCXXABI.cpp
   MicrosoftCXXABI.cpp
+  MicrosoftRTTI.cpp
   ModuleBuilder.cpp
   TargetInfo.cpp
 
diff --git a/clang/lib/CodeGen/CodeGenModule.h b/clang/lib/CodeGen/CodeGenModule.h
index 7b467291e42..eff51cea8bd 100644
--- a/clang/lib/CodeGen/CodeGenModule.h
+++ b/clang/lib/CodeGen/CodeGenModule.h
@@ -528,10 +528,10 @@ public:
     AtomicGetterHelperFnMap[Ty] = Fn;
   }
 
-  llvm::Constant *getTypeDescriptor(QualType Ty) {
+  llvm::Constant *getTypeDescriptorFromMap(QualType Ty) {
     return TypeDescriptorMap[Ty];
   }
-  void setTypeDescriptor(QualType Ty, llvm::Constant *C) {
+  void setTypeDescriptorInMap(QualType Ty, llvm::Constant *C) {
     TypeDescriptorMap[Ty] = C;
   }
 
@@ -710,6 +710,12 @@ public:
   /// The type of a generic block literal.
   llvm::Type *getGenericBlockLiteralType();
 
+  /// \brief Gets or a creats a Microsoft TypeDescriptor.
+  llvm::Constant *getMSTypeDescriptor(QualType Ty);
+  /// \brief Gets or a creats a Microsoft CompleteObjectLocator.
+  llvm::GlobalVariable *getMSCompleteObjectLocator(const CXXRecordDecl *RD,
+                                                   const VPtrInfo *Info);
+
   /// Gets the address of a block which requires no captures.
   llvm::Constant *GetAddrOfGlobalBlock(const BlockExpr *BE, const char *);
   
@@ -945,6 +951,9 @@ public:
     F->setLinkage(getFunctionLinkage(GD));
   }
 
+  /// \brief Returns the appropriate linkage for the TypeInfo struct for a type.
+  llvm::GlobalVariable::LinkageTypes getTypeInfoLinkage(QualType Ty);
+
   /// Return the appropriate linkage for the vtable, VTT, and type information
   /// of the given class.
   llvm::GlobalVariable::LinkageTypes getVTableLinkage(const CXXRecordDecl *RD);
diff --git a/clang/lib/CodeGen/MicrosoftCXXABI.cpp b/clang/lib/CodeGen/MicrosoftCXXABI.cpp
index 65b98d2bd01..5b7ea61c0de 100644
--- a/clang/lib/CodeGen/MicrosoftCXXABI.cpp
+++ b/clang/lib/CodeGen/MicrosoftCXXABI.cpp
@@ -897,14 +897,15 @@ void MicrosoftCXXABI::emitVTableDefinitions(CodeGenVTables &CGVT,
   VPtrInfoVector VFPtrs = VFTContext.getVFPtrOffsets(RD);
   llvm::GlobalVariable::LinkageTypes Linkage = CGM.getVTableLinkage(RD);
 
-  for (VPtrInfoVector::iterator I = VFPtrs.begin(), E = VFPtrs.end(); I != E;
-       ++I) {
-    llvm::GlobalVariable *VTable = getAddrOfVTable(RD, (*I)->FullOffsetInMDC);
+  for (VPtrInfo *Info : VFPtrs) {
+    llvm::GlobalVariable *VTable = getAddrOfVTable(RD, Info->FullOffsetInMDC);
     if (VTable->hasInitializer())
       continue;
+    if (getContext().getLangOpts().RTTI)
+      CGM.getMSCompleteObjectLocator(RD, Info);
 
     const VTableLayout &VTLayout =
-        VFTContext.getVFTableLayout(RD, (*I)->FullOffsetInMDC);
+      VFTContext.getVFTableLayout(RD, Info->FullOffsetInMDC);
     llvm::Constant *Init = CGVT.CreateVTableInitializer(
         RD, VTLayout.vtable_component_begin(),
         VTLayout.getNumVTableComponents(), VTLayout.vtable_thunk_begin(),
diff --git a/clang/lib/CodeGen/MicrosoftRTTI.cpp b/clang/lib/CodeGen/MicrosoftRTTI.cpp
new file mode 100644
index 00000000000..bd4789733a5
--- /dev/null
+++ b/clang/lib/CodeGen/MicrosoftRTTI.cpp
@@ -0,0 +1,447 @@
+//===--- CGCXXRTTI.cpp - Emit LLVM Code for C++ RTTI descriptors ----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This contains code dealing with C++ code generation of RTTI descriptors.
+//
+//===----------------------------------------------------------------------===//
+
+#include "CodeGenModule.h"
+#include "CGCXXABI.h"
+#include "CGObjCRuntime.h"
+#include "clang/AST/RecordLayout.h"
+#include "clang/AST/Type.h"
+#include "clang/Frontend/CodeGenOptions.h"
+
+using namespace clang;
+using namespace CodeGen;
+
+// MS RTTI Overview:
+// The run time type information emitted by cl.exe contains 5 distinct types of
+// structures.  Many of them reference each other.
+//
+// TypeInfo:  Static classes that are returned by typeid.
+//
+// CompleteObjectLocator:  Referenced by vftables.  They contain information
+//   required for dynamic casting, including OffsetFromTop.  They also contain
+//   a reference to the TypeInfo for the type and a reference to the
+//   CompleteHierarchyDescriptor for the type.
+//
+// ClassHieararchyDescriptor: Contains information about a class hierarchy.
+//   Used during dynamic_cast to walk a class hierarchy.  References a base
+//   class array and the size of said array.
+//
+// BaseClassArray: Contains a list of classes in a hierarchy.  BaseClassArray is
+//   somewhat of a misnomer because the most derived class is also in the list
+//   as well as multiple copies of virtual bases (if they occur multiple times
+//   in the hiearchy.)  The BaseClassArray contains one BaseClassDescriptor for
+//   every path in the hierarchy, in pre-order depth first order.  Note, we do
+//   not declare a specific llvm type for BaseClassArray, it's merely an array
+//   of BaseClassDescriptor pointers.
+//
+// BaseClassDescriptor: Contains information about a class in a class hierarchy.
+//   BaseClassDescriptor is also somewhat of a misnomer for the same reason that
+//   BaseClassArray is.  It contains information about a class within a
+//   hierarchy such as: is this base is ambiguous and what is its offset in the
+//   vbtable.  The names of the BaseClassDescriptors have all of their fields
+//   mangled into them so they can be aggressively deduplicated by the linker.
+
+// 5 routines for constructing the llvm types for MS RTTI structs.
+llvm::StructType *getClassHierarchyDescriptorType(CodeGenModule &CGM);
+
+static llvm::StructType *getTypeDescriptorType(CodeGenModule &CGM,
+                                               StringRef TypeInfoString) {
+  llvm::SmallString<32> TDTypeName("MSRTTITypeDescriptor");
+  TDTypeName += TypeInfoString.size();
+  if (auto Type = CGM.getModule().getTypeByName(TDTypeName))
+    return Type;
+  llvm::Type *FieldTypes[] = {
+      CGM.Int8PtrPtrTy,
+      CGM.Int8PtrTy,
+      llvm::ArrayType::get(CGM.Int8Ty, TypeInfoString.size() + 1)};
+  return llvm::StructType::create(CGM.getLLVMContext(), FieldTypes, TDTypeName);
+}
+
+static llvm::StructType *getBaseClassDescriptorType(CodeGenModule &CGM) {
+  static const char Name[] = "MSRTTIBaseClassDescriptor";
+  if (auto Type = CGM.getModule().getTypeByName(Name))
+    return Type;
+  llvm::Type *FieldTypes[] = {
+      CGM.Int8PtrTy,
+      CGM.IntTy,
+      CGM.IntTy,
+      CGM.IntTy,
+      CGM.IntTy,
+      CGM.IntTy,
+      getClassHierarchyDescriptorType(CGM)->getPointerTo()};
+  return llvm::StructType::create(CGM.getLLVMContext(), FieldTypes, Name);
+}
+
+static llvm::StructType *getClassHierarchyDescriptorType(CodeGenModule &CGM) {
+  static const char Name[] = "MSRTTIClassHierarchyDescriptor";
+  if (auto Type = CGM.getModule().getTypeByName(Name))
+    return Type;
+  // Forward declare RTTIClassHierarchyDescriptor to break a cycle.
+  llvm::StructType *Type = llvm::StructType::create(CGM.getLLVMContext(), Name);
+  llvm::Type *FieldTypes[] = {
+    CGM.IntTy,
+    CGM.IntTy,
+    CGM.IntTy,
+    getBaseClassDescriptorType(CGM)->getPointerTo()->getPointerTo()};
+  Type->setBody(FieldTypes);
+  return Type;
+}
+
+static llvm::StructType *getCompleteObjectLocatorType(CodeGenModule &CGM) {
+  static const char Name[] = "MSRTTICompleteObjectLocator";
+  if (auto Type = CGM.getModule().getTypeByName(Name))
+    return Type;
+  llvm::Type *FieldTypes[] = {
+    CGM.IntTy,
+    CGM.IntTy,
+    CGM.IntTy,
+    CGM.Int8PtrTy,
+    getClassHierarchyDescriptorType(CGM)->getPointerTo() };
+  return llvm::StructType::create(CGM.getLLVMContext(), FieldTypes, Name);
+}
+
+static llvm::GlobalVariable *getTypeInfoVTable(CodeGenModule &CGM) {
+  StringRef MangledName("\01??_7type_info@@6B@");
+  if (auto VTable = CGM.getModule().getNamedGlobal(MangledName))
+    return VTable;
+  return new llvm::GlobalVariable(CGM.getModule(), CGM.Int8PtrTy,
+                                  /*Constant=*/true,
+                                  llvm::GlobalVariable::ExternalLinkage,
+                                  /*Initializer=*/0, MangledName);
+}
+
+namespace {
+
+/// \brief A Helper struct that stores information about a class in a class
+/// hierarchy.  The information stored in these structs struct is used during
+/// the generation of ClassHierarchyDescriptors and BaseClassDescriptors.
+// During RTTI creation, MSRTTIClasses are stored in a contiguous array with
+// implicit depth first pre-order tree connectivity.  getFirstChild and
+// getNextSibling allow us to walk the tree efficiently.
+struct MSRTTIClass {
+  enum {
+    IsPrivateOnPath = 1 | 8,
+    IsAmbiguous = 2,
+    IsPrivate = 4,
+    IsVirtual = 16,
+    HasHierarchyDescriptor = 64
+  };
+  MSRTTIClass(const CXXRecordDecl *RD) : RD(RD) {}
+  uint32_t initialize(const MSRTTIClass *Parent,
+                      const CXXBaseSpecifier *Specifier);
+
+  MSRTTIClass *getFirstChild() { return this + 1; }
+  static MSRTTIClass *getNextChild(MSRTTIClass *Child) {
+    return Child + 1 + Child->NumBases;
+  }
+
+  const CXXRecordDecl *RD, *VirtualRoot;
+  uint32_t Flags, NumBases, OffsetInVBase;
+};
+
+/// \brief Recursively initialize the base class array.
+uint32_t MSRTTIClass::initialize(const MSRTTIClass *Parent,
+                                 const CXXBaseSpecifier *Specifier) {
+  Flags = HasHierarchyDescriptor;
+  if (!Parent) {
+    VirtualRoot = 0;
+    OffsetInVBase = 0;
+  } else {
+    if (Specifier->getAccessSpecifier() != AS_public)
+      Flags |= IsPrivate | IsPrivateOnPath;
+    if (Specifier->isVirtual()) {
+      Flags |= IsVirtual;
+      VirtualRoot = RD;
+      OffsetInVBase = 0;
+    } else {
+      if (Parent->Flags & IsPrivateOnPath)
+        Flags |= IsPrivateOnPath;
+      VirtualRoot = Parent->VirtualRoot;
+      OffsetInVBase = Parent->OffsetInVBase + RD->getASTContext()
+          .getASTRecordLayout(Parent->RD).getBaseClassOffset(RD).getQuantity();
+    }
+  }
+  NumBases = 0;
+  MSRTTIClass *Child = getFirstChild();
+  for (const CXXBaseSpecifier &Base : RD->bases()) {
+    NumBases += Child->initialize(this, &Base) + 1;
+    Child = getNextChild(Child);
+  }
+  return NumBases;
+}
+
+/// \brief An ephemeral helper class for building MS RTTI types.  It caches some
+/// calls to the module and information about the most derived class in a
+/// hierarchy.
+struct MSRTTIBuilder {
+  enum {
+    HasBranchingHierarchy = 1,
+    HasVirtualBranchingHierarchy = 2,
+    HasAmbiguousBases = 4
+  };
+
+  MSRTTIBuilder(CodeGenModule &CGM, const CXXRecordDecl *RD)
+      : CGM(CGM), Context(CGM.getContext()), VMContext(CGM.getLLVMContext()),
+        Module(CGM.getModule()), RD(RD), Linkage(CGM.getVTableLinkage(RD)),
+        Mangler(
+            cast<MicrosoftMangleContext>(CGM.getCXXABI().getMangleContext())) {}
+
+  llvm::GlobalVariable *getBaseClassDescriptor(const MSRTTIClass &Classes);
+  llvm::GlobalVariable *
+  getBaseClassArray(SmallVectorImpl<MSRTTIClass> &Classes);
+  llvm::GlobalVariable *getClassHierarchyDescriptor();
+  llvm::GlobalVariable *getCompleteObjectLocator(const VPtrInfo *Info);
+
+  CodeGenModule &CGM;
+  ASTContext &Context;
+  llvm::LLVMContext &VMContext;
+  llvm::Module &Module;
+  const CXXRecordDecl *RD;
+  llvm::GlobalVariable::LinkageTypes Linkage;
+  MicrosoftMangleContext &Mangler;
+};
+
+} // namespace
+
+/// \brief Recursively serializes a class hierarchy in pre-order depth first
+/// order.
+static void serializeClassHierarchy(SmallVectorImpl<MSRTTIClass> &Classes,
+                                    const CXXRecordDecl *RD) {
+  Classes.push_back(MSRTTIClass(RD));
+  for (const CXXBaseSpecifier &Base : RD->bases())
+    serializeClassHierarchy(Classes, Base.getType()->getAsCXXRecordDecl());
+}
+
+/// \brief Find ambiguity among base classes.
+static void
+detectAmbiguousBases(SmallVectorImpl<MSRTTIClass> &Classes) {
+  llvm::SmallPtrSet<const CXXRecordDecl *, 8> VirtualBases;
+  llvm::SmallPtrSet<const CXXRecordDecl *, 8> UniqueBases;
+  llvm::SmallPtrSet<const CXXRecordDecl *, 8> AmbiguousBases;
+  for (MSRTTIClass *Class = &Classes.front(); Class <= &Classes.back();) {
+    if ((Class->Flags & MSRTTIClass::IsVirtual) &&
+        !VirtualBases.insert(Class->RD)) {
+      Class = MSRTTIClass::getNextChild(Class);
+      continue;
+    }
+    if (!UniqueBases.insert(Class->RD))
+      AmbiguousBases.insert(Class->RD);
+    Class++;
+  }
+  if (AmbiguousBases.empty())
+    return;
+  for (MSRTTIClass &Class : Classes)
+    if (AmbiguousBases.count(Class.RD))
+      Class.Flags |= MSRTTIClass::IsAmbiguous;
+}
+
+llvm::GlobalVariable *MSRTTIBuilder::getClassHierarchyDescriptor() {
+  SmallString<256> MangledName;
+  {
+    llvm::raw_svector_ostream Out(MangledName);
+    Mangler.mangleCXXRTTIClassHierarchyDescriptor(RD, Out);
+  }
+
+  // Check to see if we've already declared this ClassHierarchyDescriptor.
+  if (auto CHD = Module.getNamedGlobal(MangledName))
+    return CHD;
+
+  // Serialize the class hierarchy and initalize the CHD Fields.
+  SmallVector<MSRTTIClass, 8> Classes;
+  serializeClassHierarchy(Classes, RD);
+  Classes.front().initialize(/*Parent=*/0, /*Specifier=*/0);
+  detectAmbiguousBases(Classes);
+  int Flags = 0;
+  for (auto Class : Classes) {
+    if (Class.RD->getNumBases() > 1)
+      Flags |= HasBranchingHierarchy;
+    // Note: cl.exe does not calculate "HasAmbiguousBases" correctly.  We
+    // believe the field isn't actually used.
+    if (Class.Flags & MSRTTIClass::IsAmbiguous)
+      Flags |= HasAmbiguousBases;
+  }
+  if ((Flags & HasBranchingHierarchy) && RD->getNumVBases() != 0)
+    Flags |= HasVirtualBranchingHierarchy;
+  // These gep indices are used to get the address of the first element of the
+  // base class array.
+  llvm::Value *GEPIndices[] = {llvm::ConstantInt::get(CGM.IntTy, 0),
+                               llvm::ConstantInt::get(CGM.IntTy, 0)};
+
+  // Forward declare the class hierarchy descriptor
+  auto Type = getClassHierarchyDescriptorType(CGM);
+  auto CHD = new llvm::GlobalVariable(Module, Type, /*Constant=*/true, Linkage,
+                                      /*Initializer=*/0, MangledName.c_str());
+
+  // Initialize the base class ClassHierarchyDescriptor.
+  llvm::Constant *Fields[] = {
+    llvm::ConstantInt::get(CGM.IntTy, 0), // Unknown
+    llvm::ConstantInt::get(CGM.IntTy, Flags),
+    llvm::ConstantInt::get(CGM.IntTy, Classes.size()),
+    llvm::ConstantExpr::getInBoundsGetElementPtr(
+        getBaseClassArray(Classes),
+        llvm::ArrayRef<llvm::Value *>(GEPIndices))};
+  CHD->setInitializer(llvm::ConstantStruct::get(Type, Fields));
+  return CHD;
+}
+
+llvm::GlobalVariable *
+MSRTTIBuilder::getBaseClassArray(SmallVectorImpl<MSRTTIClass> &Classes) {
+  SmallString<256> MangledName;
+  {
+    llvm::raw_svector_ostream Out(MangledName);
+    Mangler.mangleCXXRTTIBaseClassArray(RD, Out);
+  }
+
+  // Foward declare the base class array.
+  // cl.exe pads the base class array with 1 (in 32 bit mode) or 4 (in 64 bit
+  // mode) bytes of padding.  We provide a pointer sized amount of padding by
+  // adding +1 to Classes.size().  The sections have pointer alignment and are
+  // marked pick-any so it shouldn't matter.
+  auto PtrType = getBaseClassDescriptorType(CGM)->getPointerTo();
+  auto ArrayType = llvm::ArrayType::get(PtrType, Classes.size() + 1);
+  auto BCA = new llvm::GlobalVariable(Module, ArrayType,
+      /*Constant=*/true, Linkage, /*Initializer=*/0, MangledName.c_str());
+
+  // Initialize the BaseClassArray.
+  SmallVector<llvm::Constant *, 8> BaseClassArrayData;
+  for (MSRTTIClass &Class : Classes)
+    BaseClassArrayData.push_back(getBaseClassDescriptor(Class));
+  BaseClassArrayData.push_back(llvm::ConstantPointerNull::get(PtrType));
+  BCA->setInitializer(llvm::ConstantArray::get(ArrayType, BaseClassArrayData));
+  return BCA;
+}
+
+llvm::GlobalVariable *
+MSRTTIBuilder::getBaseClassDescriptor(const MSRTTIClass &Class) {
+  // Compute the fields for the BaseClassDescriptor.  They are computed up front
+  // because they are mangled into the name of the object.
+  uint32_t OffsetInVBTable = 0;
+  int32_t VBPtrOffset = -1;
+  if (Class.VirtualRoot) {
+    auto &VTableContext = CGM.getMicrosoftVTableContext();
+    OffsetInVBTable = VTableContext.getVBTableIndex(RD, Class.VirtualRoot) * 4;
+    VBPtrOffset = Context.getASTRecordLayout(RD).getVBPtrOffset().getQuantity();
+  }
+
+  SmallString<256> MangledName;
+  {
+    llvm::raw_svector_ostream Out(MangledName);
+    Mangler.mangleCXXRTTIBaseClassDescriptor(Class.RD, Class.OffsetInVBase,
+                                             VBPtrOffset, OffsetInVBTable,
+                                             Class.Flags, Out);
+  }
+
+  // Check to see if we've already declared declared this object.
+  if (auto BCD = Module.getNamedGlobal(MangledName))
+    return BCD;
+
+  // Forward declare the base class descriptor.
+  auto Type = getBaseClassDescriptorType(CGM);
+  auto BCD = new llvm::GlobalVariable(Module, Type, /*Constant=*/true, Linkage,
+                                      /*Initializer=*/0, MangledName.c_str());
+
+  // Initialize the BaseClassDescriptor.
+  llvm::Constant *Fields[] = {
+    CGM.getMSTypeDescriptor(Context.getTypeDeclType(Class.RD)),
+    llvm::ConstantInt::get(CGM.IntTy, Class.NumBases),
+    llvm::ConstantInt::get(CGM.IntTy, Class.OffsetInVBase),
+    llvm::ConstantInt::get(CGM.IntTy, VBPtrOffset),
+    llvm::ConstantInt::get(CGM.IntTy, OffsetInVBTable),
+    llvm::ConstantInt::get(CGM.IntTy, Class.Flags),
+    MSRTTIBuilder(CGM, Class.RD).getClassHierarchyDescriptor()};
+  BCD->setInitializer(llvm::ConstantStruct::get(Type, Fields));
+  return BCD;
+}
+
+llvm::GlobalVariable *
+MSRTTIBuilder::getCompleteObjectLocator(const VPtrInfo *Info) {
+  SmallString<256> MangledName;
+  {
+    llvm::raw_svector_ostream Out(MangledName);
+    Mangler.mangleCXXRTTICompleteObjectLocator(RD, Info->MangledPath, Out);
+  }
+
+  // Check to see if we've already computed this complete object locator.
+  if (auto COL = Module.getNamedGlobal(MangledName))
+    return COL;
+
+  // Compute the fields of the complete object locator.
+  int OffsetToTop = Info->FullOffsetInMDC.getQuantity();
+  int VFPtrOffset = 0;
+  // The offset includes the vtordisp if one exists.
+  if (const CXXRecordDecl *VBase = Info->getVBaseWithVPtr())
+    if (Context.getASTRecordLayout(RD)
+      .getVBaseOffsetsMap()
+      .find(VBase)
+      ->second.hasVtorDisp())
+      VFPtrOffset = Info->NonVirtualOffset.getQuantity() + 4;
+
+  // Forward declare the complete object locator.
+  llvm::StructType *Type = getCompleteObjectLocatorType(CGM);
+  auto COL = new llvm::GlobalVariable(Module, Type, /*Constant=*/true, Linkage,
+    /*Initializer=*/0, MangledName.c_str());
+
+  // Initialize the CompleteObjectLocator.
+  llvm::Constant *Fields[] = {
+    llvm::ConstantInt::get(CGM.IntTy, 0), // IsDeltaEncoded
+    llvm::ConstantInt::get(CGM.IntTy, OffsetToTop),
+    llvm::ConstantInt::get(CGM.IntTy, VFPtrOffset),
+    CGM.getMSTypeDescriptor(Context.getTypeDeclType(RD)),
+    getClassHierarchyDescriptor()};
+  COL->setInitializer(llvm::ConstantStruct::get(Type, Fields));
+  return COL;
+}
+
+
+/// \brief Gets a TypeDescriptor.  Returns a llvm::Constant * rather than a
+/// llvm::GlobalVariable * because different type descriptors have different
+/// types, and need to be abstracted.  They are abstracting by casting the
+/// address to an Int8PtrTy.
+llvm::Constant *CodeGenModule::getMSTypeDescriptor(QualType Type) {
+  auto &Mangler(cast<MicrosoftMangleContext>(getCXXABI().getMangleContext()));
+  SmallString<256> MangledName, TypeInfoString;
+  {
+    llvm::raw_svector_ostream Out(MangledName);
+    Mangler.mangleCXXRTTI(Type, Out);
+  }
+
+  // Check to see if we've already declared this TypeDescriptor.
+  if (auto TypeDescriptor = getModule().getNamedGlobal(MangledName))
+    return llvm::ConstantExpr::getBitCast(TypeDescriptor, Int8PtrTy);
+
+  // Compute the fields for the TypeDescriptor.
+  {
+    llvm::raw_svector_ostream Out(TypeInfoString);
+    Mangler.mangleCXXRTTIName(Type, Out);
+  }
+
+  // Declare and initialize the TypeDescriptor.
+  llvm::Constant *Fields[] = {
+    getTypeInfoVTable(*this),                  // VFPtr
+    llvm::ConstantPointerNull::get(Int8PtrTy), // Runtime data
+    llvm::ConstantDataArray::getString(VMContext, TypeInfoString)};
+  auto TypeDescriptorType = getTypeDescriptorType(*this, TypeInfoString);
+  return llvm::ConstantExpr::getBitCast(
+      new llvm::GlobalVariable(
+          getModule(), TypeDescriptorType, /*Constant=*/false,
+          getTypeInfoLinkage(Type),
+          llvm::ConstantStruct::get(TypeDescriptorType, Fields),
+          MangledName.c_str()),
+      Int8PtrTy);
+}
+
+llvm::GlobalVariable *
+CodeGenModule::getMSCompleteObjectLocator(const CXXRecordDecl *RD,
+                                          const VPtrInfo *Info) {
+  return MSRTTIBuilder(*this, RD).getCompleteObjectLocator(Info);
+}