[codeview] Add type stream merging prototype

Summary:
This code is intended to be used as part of LLD's PDB writing. Until
that exists, this is exposed via llvm-readobj for testing purposes.

Type stream merging uses the following algorithm:

- Begin with a new empty stream, and a new empty hash table that maps
  from type record contents to new type index.
- For each new type stream, maintain a map from source type index to
  destination type index.
- For each record, copy it and rewrite its type indices to be valid in
  the destination type stream.
- If the new type record is not already present in the destination
  stream hash table, append it to the destination type stream, assign it
  the next type index, and update the two hash tables.
- If the type record already exists in the destination stream, discard
  it and update the type index map to forward the source type index to
  the existing destination type index.

Reviewers: zturner, ruiu

Subscribers: llvm-commits

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

llvm-svn: 269521

7 files changed, 504 insertions, 88 deletions

diff --git a/llvm/lib/DebugInfo/CodeView/CMakeLists.txt b/llvm/lib/DebugInfo/CodeView/CMakeLists.txt
index cdca673474d..ecddfaf9d7b 100644
--- a/llvm/lib/DebugInfo/CodeView/CMakeLists.txt
+++ b/llvm/lib/DebugInfo/CodeView/CMakeLists.txt
@@ -6,7 +6,9 @@ add_llvm_library(LLVMDebugInfoCodeView
   MethodListRecordBuilder.cpp
   RecordSerialization.cpp
   TypeDumper.cpp
+  TypeRecord.cpp
   TypeRecordBuilder.cpp
+  TypeStreamMerger.cpp
   TypeTableBuilder.cpp
 
   ADDITIONAL_HEADER_DIRS
diff --git a/llvm/lib/DebugInfo/CodeView/FieldListRecordBuilder.cpp b/llvm/lib/DebugInfo/CodeView/FieldListRecordBuilder.cpp
index 62bc4c481cb..5f229e3d9f9 100644
--- a/llvm/lib/DebugInfo/CodeView/FieldListRecordBuilder.cpp
+++ b/llvm/lib/DebugInfo/CodeView/FieldListRecordBuilder.cpp
@@ -15,151 +15,118 @@ using namespace codeview;
 FieldListRecordBuilder::FieldListRecordBuilder()
     : ListRecordBuilder(TypeRecordKind::FieldList) {}
 
-void FieldListRecordBuilder::writeBaseClass(MemberAccess Access, TypeIndex Type,
-                                            uint64_t Offset) {
+void FieldListRecordBuilder::writeBaseClass(const BaseClassRecord &Record) {
   TypeRecordBuilder &Builder = getBuilder();
 
   Builder.writeTypeRecordKind(TypeRecordKind::BaseClass);
-  Builder.writeUInt16(static_cast<uint16_t>(Access));
-  Builder.writeTypeIndex(Type);
-  Builder.writeEncodedUnsignedInteger(Offset);
+  Builder.writeUInt16(static_cast<uint16_t>(Record.getAccess()));
+  Builder.writeTypeIndex(Record.getBaseType());
+  Builder.writeEncodedUnsignedInteger(Record.getBaseOffset());
 
   finishSubRecord();
 }
 
-void FieldListRecordBuilder::writeEnumerate(MemberAccess Access, uint64_t Value,
-                                            StringRef Name) {
+void FieldListRecordBuilder::writeEnumerator(const EnumeratorRecord &Record) {
   TypeRecordBuilder &Builder = getBuilder();
 
   Builder.writeTypeRecordKind(TypeRecordKind::Enumerator);
-  Builder.writeUInt16(static_cast<uint16_t>(Access));
-  Builder.writeEncodedUnsignedInteger(Value);
-  Builder.writeNullTerminatedString(Name);
+  Builder.writeUInt16(static_cast<uint16_t>(Record.getAccess()));
+  // FIXME: Handle full APInt such as __int128.
+  Builder.writeEncodedUnsignedInteger(Record.getValue().getZExtValue());
+  Builder.writeNullTerminatedString(Record.getName());
 
   finishSubRecord();
 }
 
-void FieldListRecordBuilder::writeMember(MemberAccess Access, TypeIndex Type,
-                                         uint64_t Offset, StringRef Name) {
+void FieldListRecordBuilder::writeDataMember(const DataMemberRecord &Record) {
   TypeRecordBuilder &Builder = getBuilder();
 
-  Builder.writeTypeRecordKind(TypeRecordKind::DataMember);
-  Builder.writeUInt16(static_cast<uint16_t>(Access));
-  Builder.writeTypeIndex(Type);
-  Builder.writeEncodedUnsignedInteger(Offset);
-  Builder.writeNullTerminatedString(Name);
+  Builder.writeTypeRecordKind(Record.getKind());
+  Builder.writeUInt16(static_cast<uint16_t>(Record.getAccess()));
+  Builder.writeTypeIndex(Record.getType());
+  Builder.writeEncodedUnsignedInteger(Record.getFieldOffset());
+  Builder.writeNullTerminatedString(Record.getName());
 
   finishSubRecord();
 }
 
-void FieldListRecordBuilder::writeMethod(uint16_t OverloadCount,
-                                         TypeIndex MethodList, StringRef Name) {
+void FieldListRecordBuilder::writeOverloadedMethod(
+    const OverloadedMethodRecord &Record) {
   TypeRecordBuilder &Builder = getBuilder();
 
   Builder.writeTypeRecordKind(TypeRecordKind::OverloadedMethod);
-  Builder.writeUInt16(OverloadCount);
-  Builder.writeTypeIndex(MethodList);
-  Builder.writeNullTerminatedString(Name);
+  Builder.writeUInt16(Record.getNumOverloads());
+  Builder.writeTypeIndex(Record.getMethodList());
+  Builder.writeNullTerminatedString(Record.getName());
 
   finishSubRecord();
 }
 
-void FieldListRecordBuilder::writeOneMethod(
-    MemberAccess Access, MethodKind Kind, MethodOptions Options, TypeIndex Type,
-    int32_t VTableSlotOffset, StringRef Name) {
+void FieldListRecordBuilder::writeOneMethod(const OneMethodRecord &Record) {
   TypeRecordBuilder &Builder = getBuilder();
 
-  uint16_t Flags = static_cast<uint16_t>(Access);
-  Flags |= static_cast<uint16_t>(Kind) << MethodKindShift;
-  Flags |= static_cast<uint16_t>(Options);
+  uint16_t Flags = static_cast<uint16_t>(Record.getAccess());
+  Flags |= static_cast<uint16_t>(Record.getKind()) << MethodKindShift;
+  Flags |= static_cast<uint16_t>(Record.getOptions());
 
   Builder.writeTypeRecordKind(TypeRecordKind::OneMethod);
   Builder.writeUInt16(Flags);
-  Builder.writeTypeIndex(Type);
-  switch (Kind) {
-  case MethodKind::IntroducingVirtual:
-  case MethodKind::PureIntroducingVirtual:
-    assert(VTableSlotOffset >= 0);
-    Builder.writeInt32(VTableSlotOffset);
-    break;
-
-  default:
-    assert(VTableSlotOffset == -1);
-    break;
+  Builder.writeTypeIndex(Record.getType());
+  if (Record.isIntroducingVirtual()) {
+    assert(Record.getVFTableOffset() >= 0);
+    Builder.writeInt32(Record.getVFTableOffset());
+  } else {
+    assert(Record.getVFTableOffset() == -1);
   }
 
-  Builder.writeNullTerminatedString(Name);
+  Builder.writeNullTerminatedString(Record.getName());
 
   finishSubRecord();
 }
 
-void FieldListRecordBuilder::writeOneMethod(const MethodInfo &Method,
-                                            StringRef Name) {
-  writeOneMethod(Method.getAccess(), Method.getKind(), Method.getOptions(),
-                 Method.getType(), Method.getVTableSlotOffset(), Name);
-}
-
-void FieldListRecordBuilder::writeNestedType(TypeIndex Type, StringRef Name) {
+void FieldListRecordBuilder::writeNestedType(const NestedTypeRecord &Record) {
   TypeRecordBuilder &Builder = getBuilder();
 
-  Builder.writeTypeRecordKind(TypeRecordKind::NestedType);
+  Builder.writeTypeRecordKind(Record.getKind());
   Builder.writeUInt16(0);
-  Builder.writeTypeIndex(Type);
-  Builder.writeNullTerminatedString(Name);
+  Builder.writeTypeIndex(Record.getNestedType());
+  Builder.writeNullTerminatedString(Record.getName());
 
   finishSubRecord();
 }
 
-void FieldListRecordBuilder::writeStaticMember(MemberAccess Access,
-                                               TypeIndex Type, StringRef Name) {
+void FieldListRecordBuilder::writeStaticDataMember(
+    const StaticDataMemberRecord &Record) {
   TypeRecordBuilder &Builder = getBuilder();
 
-  Builder.writeTypeRecordKind(TypeRecordKind::StaticDataMember);
-  Builder.writeUInt16(static_cast<uint16_t>(Access));
-  Builder.writeTypeIndex(Type);
-  Builder.writeNullTerminatedString(Name);
+  Builder.writeTypeRecordKind(Record.getKind());
+  Builder.writeUInt16(static_cast<uint16_t>(Record.getAccess()));
+  Builder.writeTypeIndex(Record.getType());
+  Builder.writeNullTerminatedString(Record.getName());
 
   finishSubRecord();
 }
 
-void FieldListRecordBuilder::writeIndirectVirtualBaseClass(
-    MemberAccess Access, TypeIndex Type, TypeIndex VirtualBasePointerType,
-    int64_t VirtualBasePointerOffset, uint64_t SlotIndex) {
-  writeVirtualBaseClass(TypeRecordKind::IndirectVirtualBaseClass, Access, Type,
-                        VirtualBasePointerType, VirtualBasePointerOffset,
-                        SlotIndex);
-}
-
-void FieldListRecordBuilder::writeVirtualBaseClass(
-    MemberAccess Access, TypeIndex Type, TypeIndex VirtualBasePointerType,
-    int64_t VirtualBasePointerOffset, uint64_t SlotIndex) {
-  writeVirtualBaseClass(TypeRecordKind::VirtualBaseClass, Access, Type,
-                        VirtualBasePointerType, VirtualBasePointerOffset,
-                        SlotIndex);
-}
-
 void FieldListRecordBuilder::writeVirtualBaseClass(
-    TypeRecordKind Kind, MemberAccess Access, TypeIndex Type,
-    TypeIndex VirtualBasePointerType, int64_t VirtualBasePointerOffset,
-    uint64_t SlotIndex) {
+    const VirtualBaseClassRecord &Record) {
   TypeRecordBuilder &Builder = getBuilder();
 
-  Builder.writeTypeRecordKind(Kind);
-  Builder.writeUInt16(static_cast<uint16_t>(Access));
-  Builder.writeTypeIndex(Type);
-  Builder.writeTypeIndex(VirtualBasePointerType);
-  Builder.writeEncodedInteger(VirtualBasePointerOffset);
-  Builder.writeEncodedUnsignedInteger(SlotIndex);
+  Builder.writeTypeRecordKind(Record.getKind());
+  Builder.writeUInt16(static_cast<uint16_t>(Record.getAccess()));
+  Builder.writeTypeIndex(Record.getBaseType());
+  Builder.writeTypeIndex(Record.getVBPtrType());
+  Builder.writeEncodedInteger(Record.getVBPtrOffset());
+  Builder.writeEncodedUnsignedInteger(Record.getVTableIndex());
 
   finishSubRecord();
 }
 
-void FieldListRecordBuilder::writeVirtualFunctionTablePointer(TypeIndex Type) {
+void FieldListRecordBuilder::writeVFPtr(const VFPtrRecord &Record) {
   TypeRecordBuilder &Builder = getBuilder();
 
   Builder.writeTypeRecordKind(TypeRecordKind::VFPtr);
   Builder.writeUInt16(0);
-  Builder.writeTypeIndex(Type);
+  Builder.writeTypeIndex(Record.getType());
 
   finishSubRecord();
 }
diff --git a/llvm/lib/DebugInfo/CodeView/TypeDumper.cpp b/llvm/lib/DebugInfo/CodeView/TypeDumper.cpp
index 6a42fc42433..50a7e6c841b 100644
--- a/llvm/lib/DebugInfo/CodeView/TypeDumper.cpp
+++ b/llvm/lib/DebugInfo/CodeView/TypeDumper.cpp
@@ -280,6 +280,7 @@ void CVTypeDumperImpl::visitStringId(TypeLeafKind Leaf,
   // Put this in CVUDTNames so it gets printed with LF_UDT_SRC_LINE.
   Name = String.getString();
 }
+
 void CVTypeDumperImpl::visitArgList(TypeLeafKind Leaf, ArgListRecord &Args) {
   auto Indices = Args.getIndices();
   uint32_t Size = Indices.size();
diff --git a/llvm/lib/DebugInfo/CodeView/TypeRecord.cpp b/llvm/lib/DebugInfo/CodeView/TypeRecord.cpp
new file mode 100644
index 00000000000..57cd5b7e264
--- /dev/null
+++ b/llvm/lib/DebugInfo/CodeView/TypeRecord.cpp
@@ -0,0 +1,191 @@
+//===-- TypeRecord.cpp ------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/CodeView/TypeRecord.h"
+#include "llvm/DebugInfo/CodeView/TypeIndex.h"
+
+using namespace llvm;
+using namespace llvm::codeview;
+
+static bool remapIndex(ArrayRef<TypeIndex> IndexMap, TypeIndex &Idx) {
+  // Simple types are unchanged.
+  if (Idx.isSimple())
+    return true;
+  unsigned MapPos = Idx.getIndex() - TypeIndex::FirstNonSimpleIndex;
+  if (MapPos < IndexMap.size()) {
+    Idx = IndexMap[MapPos];
+    return true;
+  }
+
+  // This type index is invalid. Remap this to "not translated by cvpack",
+  // and return failure.
+  Idx = TypeIndex(SimpleTypeKind::NotTranslated, SimpleTypeMode::Direct);
+  return false;
+}
+
+bool ModifierRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return remapIndex(IndexMap, ModifiedType);
+}
+
+bool ProcedureRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  Success &= remapIndex(IndexMap, ReturnType);
+  Success &= remapIndex(IndexMap, ArgumentList);
+  return Success;
+}
+
+bool MemberFunctionRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  Success &= remapIndex(IndexMap, ReturnType);
+  Success &= remapIndex(IndexMap, ClassType);
+  Success &= remapIndex(IndexMap, ThisType);
+  Success &= remapIndex(IndexMap, ArgumentList);
+  return Success;
+}
+
+bool MemberFuncIdRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  Success &= remapIndex(IndexMap, ClassType);
+  Success &= remapIndex(IndexMap, FunctionType);
+  return Success;
+}
+
+bool ArgListRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  for (TypeIndex &Str : StringIndices)
+    Success &= remapIndex(IndexMap, Str);
+  return Success;
+}
+
+bool MemberPointerInfo::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return remapIndex(IndexMap, ContainingType);
+}
+
+bool PointerRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  Success &= remapIndex(IndexMap, ReferentType);
+  if (isPointerToMember())
+    Success &= MemberInfo.remapTypeIndices(IndexMap);
+  return Success;
+}
+
+bool NestedTypeRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return remapIndex(IndexMap, Type);
+}
+
+bool ArrayRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  Success &= remapIndex(IndexMap, ElementType);
+  Success &= remapIndex(IndexMap, IndexType);
+  return Success;
+}
+
+bool TagRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return remapIndex(IndexMap, FieldList);
+}
+
+bool ClassRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  Success &= TagRecord::remapTypeIndices(IndexMap);
+  Success &= remapIndex(IndexMap, DerivationList);
+  Success &= remapIndex(IndexMap, VTableShape);
+  return Success;
+}
+
+bool EnumRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  Success &= TagRecord::remapTypeIndices(IndexMap);
+  Success &= remapIndex(IndexMap, UnderlyingType);
+  return Success;
+}
+
+bool VFTableShapeRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return true;
+}
+
+bool TypeServer2Record::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return true;
+}
+
+bool StringIdRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return remapIndex(IndexMap, Id);
+}
+
+bool FuncIdRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  Success &= remapIndex(IndexMap, ParentScope);
+  Success &= remapIndex(IndexMap, FunctionType);
+  return Success;
+}
+
+bool UdtSourceLineRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  Success &= remapIndex(IndexMap, UDT);
+  Success &= remapIndex(IndexMap, SourceFile);
+  return Success;
+}
+
+bool BuildInfoRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  for (TypeIndex &Arg : ArgIndices)
+    Success &= remapIndex(IndexMap, Arg);
+  return Success;
+}
+
+bool VFTableRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  Success &= remapIndex(IndexMap, CompleteClass);
+  Success &= remapIndex(IndexMap, OverriddenVFTable);
+  return Success;
+}
+
+bool OneMethodRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  Success &= remapIndex(IndexMap, Type);
+  return Success;
+}
+
+bool MethodOverloadListRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  for (OneMethodRecord &Meth : Methods)
+    if ((Success = Meth.remapTypeIndices(IndexMap)))
+      return Success;
+  return Success;
+}
+
+bool OverloadedMethodRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return remapIndex(IndexMap, MethodList);
+}
+
+bool DataMemberRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return remapIndex(IndexMap, Type);
+}
+
+bool StaticDataMemberRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return remapIndex(IndexMap, Type);
+}
+
+bool EnumeratorRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return true;
+}
+
+bool VFPtrRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return remapIndex(IndexMap, Type);
+}
+
+bool BaseClassRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  return remapIndex(IndexMap, Type);
+}
+
+bool VirtualBaseClassRecord::remapTypeIndices(ArrayRef<TypeIndex> IndexMap) {
+  bool Success = true;
+  Success &= remapIndex(IndexMap, BaseType);
+  Success &= remapIndex(IndexMap, VBPtrType);
+  return Success;
+}
diff --git a/llvm/lib/DebugInfo/CodeView/TypeRecordBuilder.cpp b/llvm/lib/DebugInfo/CodeView/TypeRecordBuilder.cpp
index 3cc56ba2c19..f1c293e39fd 100644
--- a/llvm/lib/DebugInfo/CodeView/TypeRecordBuilder.cpp
+++ b/llvm/lib/DebugInfo/CodeView/TypeRecordBuilder.cpp
@@ -12,8 +12,8 @@
 using namespace llvm;
 using namespace codeview;
 
-TypeRecordBuilder::TypeRecordBuilder(TypeRecordKind Kind) : Stream(Buffer),
-  Writer(Stream) {
+TypeRecordBuilder::TypeRecordBuilder(TypeRecordKind Kind)
+    : Stream(Buffer), Writer(Stream) {
   writeTypeRecordKind(Kind);
 }
 
@@ -104,6 +104,11 @@ void TypeRecordBuilder::writeNullTerminatedString(StringRef Value) {
   writeUInt8(0);
 }
 
+void TypeRecordBuilder::writeGuid(StringRef Guid) {
+  assert(Guid.size() == 16);
+  Stream.write(Guid.data(), 16);
+}
+
 void TypeRecordBuilder::writeTypeIndex(TypeIndex TypeInd) {
   writeUInt32(TypeInd.getIndex());
 }
diff --git a/llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp b/llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp
new file mode 100644
index 00000000000..5ee7cb17000
--- /dev/null
+++ b/llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp
@@ -0,0 +1,144 @@
+//===-- TypeStreamMerger.cpp ------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/CodeView/TypeStreamMerger.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
+#include "llvm/DebugInfo/CodeView/FieldListRecordBuilder.h"
+#include "llvm/DebugInfo/CodeView/TypeIndex.h"
+#include "llvm/DebugInfo/CodeView/TypeRecord.h"
+#include "llvm/DebugInfo/CodeView/TypeStream.h"
+#include "llvm/Support/ScopedPrinter.h"
+
+using namespace llvm;
+using namespace llvm::codeview;
+
+namespace {
+
+/// Implementation of CodeView type stream merging.
+///
+/// A CodeView type stream is a series of records that reference each other
+/// through type indices. A type index is either "simple", meaning it is less
+/// than 0x1000 and refers to a builtin type, or it is complex, meaning it
+/// refers to a prior type record in the current stream. The type index of a
+/// record is equal to the number of records before it in the stream plus
+/// 0x1000.
+///
+/// Type records are only allowed to use type indices smaller than their own, so
+/// a type stream is effectively a topologically sorted DAG. Cycles occuring in
+/// the type graph of the source program are resolved with forward declarations
+/// of composite types. This class implements the following type stream merging
+/// algorithm, which relies on this DAG structure:
+///
+/// - Begin with a new empty stream, and a new empty hash table that maps from
+///   type record contents to new type index.
+/// - For each new type stream, maintain a map from source type index to
+///   destination type index.
+/// - For each record, copy it and rewrite its type indices to be valid in the
+///   destination type stream.
+/// - If the new type record is not already present in the destination stream
+///   hash table, append it to the destination type stream, assign it the next
+///   type index, and update the two hash tables.
+/// - If the type record already exists in the destination stream, discard it
+///   and update the type index map to forward the source type index to the
+///   existing destination type index.
+class TypeStreamMerger : public CVTypeVisitor<TypeStreamMerger> {
+public:
+  TypeStreamMerger(TypeTableBuilder &DestStream) : DestStream(DestStream) {
+    assert(!hadError());
+  }
+
+  /// CVTypeVisitor overrides.
+#define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
+  void visit##Name(TypeLeafKind LeafType, Name##Record &Record);
+#define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
+#define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
+  void visit##Name(TypeLeafKind LeafType, Name##Record &Record);
+#define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
+#include "llvm/DebugInfo/CodeView/TypeRecords.def"
+
+  void visitUnknownMember(TypeLeafKind Leaf);
+
+  void visitTypeBegin(TypeLeafKind Leaf, ArrayRef<uint8_t> RecordData);
+  void visitTypeEnd(TypeLeafKind Leaf, ArrayRef<uint8_t> RecordData);
+
+  void visitFieldList(TypeLeafKind Leaf, ArrayRef<uint8_t> FieldData);
+
+  bool mergeStream(ArrayRef<uint8_t> SrcStream);
+
+private:
+  bool hadError() { return FoundBadTypeIndex || CVTypeVisitor::hadError(); }
+
+  bool FoundBadTypeIndex = false;
+
+  FieldListRecordBuilder FieldBuilder;
+
+  TypeTableBuilder &DestStream;
+
+  size_t BeginIndexMapSize = 0;
+
+  /// Map from source type index to destination type index. Indexed by source
+  /// type index minus 0x1000.
+  SmallVector<TypeIndex, 0> IndexMap;
+};
+
+} // end anonymous namespace
+
+void TypeStreamMerger::visitTypeBegin(TypeLeafKind Leaf,
+                                      ArrayRef<uint8_t> RecordData) {
+  BeginIndexMapSize = IndexMap.size();
+}
+
+void TypeStreamMerger::visitTypeEnd(TypeLeafKind Leaf,
+                                    ArrayRef<uint8_t> RecordData) {
+  assert(IndexMap.size() == BeginIndexMapSize + 1);
+}
+
+void TypeStreamMerger::visitFieldList(TypeLeafKind Leaf,
+                                      ArrayRef<uint8_t> FieldData) {
+  CVTypeVisitor::visitFieldList(Leaf, FieldData);
+  IndexMap.push_back(DestStream.writeFieldList(FieldBuilder));
+  FieldBuilder.reset();
+}
+
+#define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
+  void TypeStreamMerger::visit##Name(TypeLeafKind LeafType,                    \
+                                     Name##Record &Record) {                   \
+    FoundBadTypeIndex |= !Record.remapTypeIndices(IndexMap);              \
+    IndexMap.push_back(DestStream.write##Name(Record));                        \
+  }
+#define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
+#define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
+  void TypeStreamMerger::visit##Name(TypeLeafKind LeafType,                    \
+                                     Name##Record &Record) {                   \
+    FoundBadTypeIndex |= !Record.remapTypeIndices(IndexMap);              \
+    FieldBuilder.write##Name(Record);                                          \
+  }
+#define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
+#include "llvm/DebugInfo/CodeView/TypeRecords.def"
+
+void TypeStreamMerger::visitUnknownMember(TypeLeafKind LF) {
+  // We failed to translate a type. Translate this index as "not translated".
+  IndexMap.push_back(
+      TypeIndex(SimpleTypeKind::NotTranslated, SimpleTypeMode::Direct));
+  parseError();
+}
+
+bool TypeStreamMerger::mergeStream(ArrayRef<uint8_t> SrcStream) {
+  assert(IndexMap.empty());
+  visitTypeStream(SrcStream);
+  IndexMap.clear();
+  return !hadError();
+}
+
+bool llvm::codeview::mergeTypeStreams(TypeTableBuilder &DestStream,
+                                      ArrayRef<uint8_t> SrcStream) {
+  return TypeStreamMerger(DestStream).mergeStream(SrcStream);
+}
diff --git a/llvm/lib/DebugInfo/CodeView/TypeTableBuilder.cpp b/llvm/lib/DebugInfo/CodeView/TypeTableBuilder.cpp
index 39e2a82f40a..3f48f6495f2 100644
--- a/llvm/lib/DebugInfo/CodeView/TypeTableBuilder.cpp
+++ b/llvm/lib/DebugInfo/CodeView/TypeTableBuilder.cpp
@@ -128,6 +128,23 @@ TypeIndex TypeTableBuilder::writeClass(const ClassRecord &Record) {
   return writeRecord(Builder);
 }
 
+TypeIndex TypeTableBuilder::writeUnion(const UnionRecord &Record) {
+  TypeRecordBuilder Builder(TypeRecordKind::Union);
+  Builder.writeUInt16(Record.getMemberCount());
+  uint16_t Flags =
+      static_cast<uint16_t>(Record.getOptions()) |
+      (static_cast<uint16_t>(Record.getHfa()) << ClassRecord::HfaKindShift);
+  Builder.writeUInt16(Flags);
+  Builder.writeTypeIndex(Record.getFieldList());
+  Builder.writeEncodedUnsignedInteger(Record.getSize());
+  Builder.writeNullTerminatedString(Record.getName());
+  if ((Record.getOptions() & ClassOptions::HasUniqueName) !=
+      ClassOptions::None) {
+    Builder.writeNullTerminatedString(Record.getUniqueName());
+  }
+  return writeRecord(Builder);
+}
+
 TypeIndex TypeTableBuilder::writeEnum(const EnumRecord &Record) {
   TypeRecordBuilder Builder(Record.getKind());
 
@@ -172,6 +189,70 @@ TypeTableBuilder::writeVFTableShape(const VFTableShapeRecord &Record) {
   return writeRecord(Builder);
 }
 
+TypeIndex
+TypeTableBuilder::writeVFTable(const VFTableRecord &Record) {
+  TypeRecordBuilder Builder(Record.getKind());
+  Builder.writeTypeIndex(Record.getCompleteClass());
+  Builder.writeTypeIndex(Record.getOverriddenVTable());
+  Builder.writeUInt32(Record.getVFPtrOffset());
+
+  // Sum up the lengths of the null-terminated names.
+  size_t NamesLen = Record.getName().size() + 1;
+  for (StringRef MethodName : Record.getMethodNames())
+    NamesLen += MethodName.size() + 1;
+
+  Builder.writeUInt32(NamesLen);
+  Builder.writeNullTerminatedString(Record.getName());
+  for (StringRef MethodName : Record.getMethodNames())
+    Builder.writeNullTerminatedString(MethodName);
+
+  return writeRecord(Builder);
+}
+
+TypeIndex TypeTableBuilder::writeStringId(const StringIdRecord &Record) {
+  TypeRecordBuilder Builder(TypeRecordKind::StringId);
+  Builder.writeTypeIndex(Record.getId());
+  Builder.writeNullTerminatedString(Record.getString());
+  return writeRecord(Builder);
+}
+
+TypeIndex
+TypeTableBuilder::writeUdtSourceLine(const UdtSourceLineRecord &Record) {
+  TypeRecordBuilder Builder(Record.getKind());
+  Builder.writeTypeIndex(Record.getUDT());
+  Builder.writeTypeIndex(Record.getSourceFile());
+  Builder.writeUInt32(Record.getLineNumber());
+  return writeRecord(Builder);
+}
+
+TypeIndex
+TypeTableBuilder::writeFuncId(const FuncIdRecord &Record) {
+  TypeRecordBuilder Builder(Record.getKind());
+  Builder.writeTypeIndex(Record.getParentScope());
+  Builder.writeTypeIndex(Record.getFunctionType());
+  Builder.writeNullTerminatedString(Record.getName());
+  return writeRecord(Builder);
+}
+
+TypeIndex
+TypeTableBuilder::writeMemberFuncId(const MemberFuncIdRecord &Record) {
+  TypeRecordBuilder Builder(Record.getKind());
+  Builder.writeTypeIndex(Record.getClassType());
+  Builder.writeTypeIndex(Record.getFunctionType());
+  Builder.writeNullTerminatedString(Record.getName());
+  return writeRecord(Builder);
+}
+
+TypeIndex
+TypeTableBuilder::writeBuildInfo(const BuildInfoRecord &Record) {
+  TypeRecordBuilder Builder(Record.getKind());
+  assert(Record.getArgs().size() <= UINT16_MAX);
+  Builder.writeUInt16(Record.getArgs().size());
+  for (TypeIndex Arg : Record.getArgs())
+    Builder.writeTypeIndex(Arg);
+  return writeRecord(Builder);
+}
+
 TypeIndex TypeTableBuilder::writeRecord(TypeRecordBuilder &Builder) {
   return writeRecord(Builder.str());
 }
@@ -182,9 +263,34 @@ TypeIndex TypeTableBuilder::writeFieldList(FieldListRecordBuilder &FieldList) {
   return writeRecord(FieldList.str());
 }
 
-TypeIndex
-TypeTableBuilder::writeMethodList(MethodListRecordBuilder &MethodList) {
+TypeIndex TypeTableBuilder::writeMethodOverloadList(
+    const MethodOverloadListRecord &Record) {
+  TypeRecordBuilder Builder(Record.getKind());
+  for (const OneMethodRecord &Method : Record.getMethods()) {
+    uint16_t Flags = static_cast<uint16_t>(Method.getAccess());
+    Flags |= static_cast<uint16_t>(Method.getKind())
+             << MemberAttributes::MethodKindShift;
+    Flags |= static_cast<uint16_t>(Method.getOptions());
+    Builder.writeUInt16(Flags);
+    Builder.writeUInt16(0); // padding
+    Builder.writeTypeIndex(Method.getType());
+    if (Method.isIntroducingVirtual()) {
+      assert(Method.getVFTableOffset() >= 0);
+      Builder.writeInt32(Method.getVFTableOffset());
+    } else {
+      assert(Method.getVFTableOffset() == -1);
+    }
+  }
+
   // TODO: Split the list into multiple records if it's longer than 64KB, using
   // a subrecord of TypeRecordKind::Index to chain the records together.
-  return writeRecord(MethodList.str());
+  return writeRecord(Builder);
+}
+
+TypeIndex TypeTableBuilder::writeTypeServer2(const TypeServer2Record &Record) {
+  TypeRecordBuilder Builder(Record.getKind());
+  Builder.writeGuid(Record.getGuid());
+  Builder.writeUInt32(Record.getAge());
+  Builder.writeNullTerminatedString(Record.getName());
+  return writeRecord(Builder);
 }