Implement various flavors of type merging

[zturner]

Summary

Our previous algorithm assumed that types and id records were in a single unified stream. For type information in object files this is the case, but for type information in PDB files the IDs and types have already been split out. In that case, we need a mode where we can assume that a given type stream contains only type records or only id records. This patch adds such a mode.

[rnk]

lgtm!

llvm/test/DebugInfo/PDB/pdbdump-merge-ids-and-types.test

4 ↗

(On Diff #99784)

This would make the test slightly faster:

; RUN: llvm-pdbdump raw -tpi-records %t.3.pdb > %t.tpi
; RUN: llvm-pdbdump raw -ipi-records %t.3.pdb > %t.ipi
; RUN: FileCheck %s -check-prefix=TPI-TYPES < %t.tpi
; RUN: FileCheck %s -check-prefix=INTMAIN < %t.tpi
; RUN: FileCheck %s -check-prefix=VOIDMAIN < %t.tpi
; RUN: FileCheck %s -check-prefix=IPI-TYPES < %t.ipi
; RUN: FileCheck %s -check-prefix=IPI-NAMES< %t.ipi
; RUN: FileCheck %s -check-prefix=IPI-UDT< %t.ipi

Up to you. It's probably only worth it for 4+ runs.

lld/trunk/COFF/PDB.cpp

for (ObjectFile *File : Symtab->ObjectFiles) {
     // Follow type servers.  If the same type server is encountered more than
     // once for this instance of `PDBTypeServerHandler` (for example if many
     // object files reference the same TypeServer), the types from the
     // TypeServer will only be visited once.
     pdb::PDBTypeServerHandler Handler;
     Handler.addSearchPath(llvm::sys::path::parent_path(File->getName()));
     if (auto EC = Reader.readArray(Types, Reader.getLength()))
       fatal(EC, "Reader::readArray failed");
-    if (auto Err = codeview::mergeTypeStreams(IDTable, TypeTable, SourceToDest,
-                                              &Handler, Types))
+    codeview::LazyRandomTypeCollection TypesAndIds(Types, 100);
+    if (auto Err = codeview::mergeTypeAndIdRecords(
+            IDTable, TypeTable, SourceToDest, &Handler, TypesAndIds))
       fatal(Err, "codeview::mergeTypeStreams failed");
   }
 
   // Construct TPI stream contents.
   addTypeInfo(Builder.getTpiBuilder(), TypeTable);
 
   // Construct IPI stream contents.
   addTypeInfo(Builder.getIpiBuilder(), IDTable);

llvm/trunk/include/llvm/DebugInfo/CodeView/TypeStreamMerger.h

 
 namespace llvm {
 namespace codeview {
 
 class TypeIndex;
 class TypeServerHandler;
 class TypeTableBuilder;
 
-/// Merges one type stream into another. Returns true on success.
-Error mergeTypeStreams(TypeTableBuilder &DestIdStream,
-                       TypeTableBuilder &DestTypeStream,
+/// \brief Merge one set of type records into another.  This method assumes
+/// that all records are type records, and there are no Id records present.
+///
+/// \param Dest The table to store the re-written type records into.
+///
+/// \param SourceToDest A vector, indexed by the TypeIndex in the source
+/// type stream, that contains the index of the corresponding type record
+/// in the destination stream.
+///
+/// \param Handler (optional) If non-null, an interface that gets invoked
+/// to handle type server records.
+///
+/// \param Types The collection of types to merge in.
+///
+/// \returns Error::success() if the operation succeeded, otherwise an
+/// appropriate error code.
+Error mergeTypeRecords(TypeTableBuilder &Dest,
                        SmallVectorImpl<TypeIndex> &SourceToDest,
-                       TypeServerHandler *Handler, const CVTypeArray &Types);
+                       TypeServerHandler *Handler, TypeCollection &Types);
+
+/// \brief Merge one set of id records into another.  This method assumes
+/// that all records are id records, and there are no Type records present.
+/// However, since Id records can refer back to Type records, this method
+/// assumes that the referenced type records have also been merged into
+/// another type stream (for example using the above method), and accepts
+/// the mapping from source to dest for that stream so that it can re-write
+/// the type record mappings accordingly.
+///
+/// \param Dest The table to store the re-written id records into.
+///
+/// \param Types The mapping to use for the type records that these id
+/// records refer to.
+///
+/// \param SourceToDest A vector, indexed by the TypeIndex in the source
+/// id stream, that contains the index of the corresponding id record
+/// in the destination stream.
+///
+/// \param Types The collection of id records to merge in.
+///
+/// \returns Error::success() if the operation succeeded, otherwise an
+/// appropriate error code.
+Error mergeIdRecords(TypeTableBuilder &Dest, ArrayRef<TypeIndex> Types,
+                     SmallVectorImpl<TypeIndex> &SourceToDest,
+                     TypeCollection &Ids);
+
+/// \brief Merge a unified set of type and id records, splitting them into
+/// separate output streams.
+///
+/// \param DestIds The table to store the re-written id records into.
+///
+/// \param DestTypes the table to store the re-written type records into.
+///
+/// \param SourceToDest A vector, indexed by the TypeIndex in the source
+/// id stream, that contains the index of the corresponding id record
+/// in the destination stream.
+///
+/// \param Handler (optional) If non-null, an interface that gets invoked
+/// to handle type server records.
+///
+/// \param IdsAndTypes The collection of id records to merge in.
+///
+/// \returns Error::success() if the operation succeeded, otherwise an
+/// appropriate error code.
+Error mergeTypeAndIdRecords(TypeTableBuilder &DestIds,
+                            TypeTableBuilder &DestTypes,
+                            SmallVectorImpl<TypeIndex> &SourceToDest,
+                            TypeServerHandler *Handler,
+                            TypeCollection &IdsAndTypes);
 
 } // end namespace codeview
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_CODEVIEW_TYPESTREAMMERGER_H

llvm/trunk/include/llvm/DebugInfo/PDB/Native/TpiStream.h

 #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
 #include "llvm/DebugInfo/PDB/PDBTypes.h"
 #include "llvm/Support/BinaryStreamArray.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include "llvm/Support/Error.h"
 
 namespace llvm {
+namespace codeview {
+class LazyRandomTypeCollection;
+}
 namespace msf {
 class MappedBlockStream;
 }
 namespace pdb {
 class PDBFile;
 
 class TpiStream {
   friend class TpiStreamBuilder;
public:
   uint32_t getNumHashBuckets() const;
   FixedStreamArray<support::ulittle32_t> getHashValues() const;
   FixedStreamArray<codeview::TypeIndexOffset> getTypeIndexOffsets() const;
   HashTable &getHashAdjusters();
 
   codeview::CVTypeRange types(bool *HadError) const;
   const codeview::CVTypeArray &typeArray() const { return TypeRecords; }
 
+  codeview::LazyRandomTypeCollection &typeCollection() { return *Types; }
+
   Error commit();
 
 private:
   const PDBFile &Pdb;
   std::unique_ptr<msf::MappedBlockStream> Stream;
 
+  std::unique_ptr<codeview::LazyRandomTypeCollection> Types;
+
   codeview::CVTypeArray TypeRecords;
 
   std::unique_ptr<BinaryStream> HashStream;
   FixedStreamArray<support::ulittle32_t> HashValues;
   FixedStreamArray<codeview::TypeIndexOffset> TypeIndexOffsets;
   HashTable HashAdjusters;
 
   const TpiStreamHeader *Header;
 };
 }
 }
 
 #endif

llvm/trunk/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

 ///   existing destination type index.
 ///
 /// As an additional complication, type stream merging actually produces two
 /// streams: an item (or IPI) stream and a type stream, as this is what is
 /// actually stored in the final PDB. We choose which records go where by
 /// looking at the record kind.
 class TypeStreamMerger : public TypeVisitorCallbacks {
 public:
-  TypeStreamMerger(TypeTableBuilder &DestIdStream,
-                   TypeTableBuilder &DestTypeStream,
-                   SmallVectorImpl<TypeIndex> &SourceToDest,
+  explicit TypeStreamMerger(SmallVectorImpl<TypeIndex> &SourceToDest,
                             TypeServerHandler *Handler)
-      : DestIdStream(DestIdStream), DestTypeStream(DestTypeStream),
-        FieldListBuilder(DestTypeStream), Handler(Handler),
-        IndexMap(SourceToDest) {}
+      : Handler(Handler), IndexMap(SourceToDest) {
+    SourceToDest.clear();
+  }
 
   static const TypeIndex Untranslated;
 
 /// TypeVisitorCallbacks overrides.
 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
   Error visitKnownRecord(CVType &CVR, Name##Record &Record) override;
 #define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
   Error visitKnownMember(CVMemberRecord &CVR, Name##Record &Record) override;
 #define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
 #define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
 #include "llvm/DebugInfo/CodeView/TypeRecords.def"
 
   Error visitUnknownType(CVType &Record) override;
 
   Error visitTypeBegin(CVType &Record) override;
   Error visitTypeEnd(CVType &Record) override;
   Error visitMemberEnd(CVMemberRecord &Record) override;
 
-  Error mergeStream(const CVTypeArray &Types);
+  Error mergeTypesAndIds(TypeTableBuilder &DestIds, TypeTableBuilder &DestTypes,
+                         TypeCollection &IdsAndTypes);
+  Error mergeIdRecords(TypeTableBuilder &Dest,
+                       ArrayRef<TypeIndex> TypeSourceToDest,
+                       TypeCollection &Ids);
+  Error mergeTypeRecords(TypeTableBuilder &Dest, TypeCollection &Types);
 
 private:
+  Error doit(TypeCollection &Types);
+
   void addMapping(TypeIndex Idx);
 
-  bool remapIndex(TypeIndex &Idx);
+  bool remapTypeIndex(TypeIndex &Idx);
+  bool remapItemIndex(TypeIndex &Idx);
+
+  bool remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map);
 
   size_t slotForIndex(TypeIndex Idx) const {
     assert(!Idx.isSimple() && "simple type indices have no slots");
     return Idx.getIndex() - TypeIndex::FirstNonSimpleIndex;
   }
 
   Error errorCorruptRecord() const {
     return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
   }
 
   template <typename RecordType>
   Error writeRecord(RecordType &R, bool RemapSuccess) {
     TypeIndex DestIdx = Untranslated;
     if (RemapSuccess)
-      DestIdx = DestTypeStream.writeKnownType(R);
+      DestIdx = DestTypeStream->writeKnownType(R);
     addMapping(DestIdx);
     return Error::success();
   }
 
   template <typename RecordType>
   Error writeIdRecord(RecordType &R, bool RemapSuccess) {
     TypeIndex DestIdx = Untranslated;
     if (RemapSuccess)
-      DestIdx = DestIdStream.writeKnownType(R);
+      DestIdx = DestIdStream->writeKnownType(R);
     addMapping(DestIdx);
     return Error::success();
   }
 
   template <typename RecordType>
   Error writeMember(RecordType &R, bool RemapSuccess) {
     if (RemapSuccess)
-      FieldListBuilder.writeMemberType(R);
+      FieldListBuilder->writeMemberType(R);
     else
       HadUntranslatedMember = true;
     return Error::success();
   }
 
   Optional<Error> LastError;
 
   bool IsSecondPass = false;
 
   bool HadUntranslatedMember = false;
 
   unsigned NumBadIndices = 0;
 
   BumpPtrAllocator Allocator;
 
-  TypeTableBuilder &DestIdStream;
-  TypeTableBuilder &DestTypeStream;
-  FieldListRecordBuilder FieldListBuilder;
-  TypeServerHandler *Handler;
-
   TypeIndex CurIndex{TypeIndex::FirstNonSimpleIndex};
 
+  TypeTableBuilder *DestIdStream = nullptr;
+  TypeTableBuilder *DestTypeStream = nullptr;
+  std::unique_ptr<FieldListRecordBuilder> FieldListBuilder;
+  TypeServerHandler *Handler = nullptr;
+
+  // If we're only mapping id records, this array contains the mapping for
+  // type records.
+  ArrayRef<TypeIndex> TypeLookup;
+
   /// Map from source type index to destination type index. Indexed by source
   /// type index minus 0x1000.
   SmallVectorImpl<TypeIndex> &IndexMap;
 };
 
 } // end anonymous namespace
 
 const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);
assert(IndexMap.size() == slotForIndex(CurIndex) &&
            "visitKnownRecord should add one index map entry");
     IndexMap.push_back(Idx);
   } else {
     assert(slotForIndex(CurIndex) < IndexMap.size());
     IndexMap[slotForIndex(CurIndex)] = Idx;
   }
 }
 
-bool TypeStreamMerger::remapIndex(TypeIndex &Idx) {
+bool TypeStreamMerger::remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map) {
   // Simple types are unchanged.
   if (Idx.isSimple())
     return true;
 
   // Check if this type index refers to a record we've already translated
   // successfully. If it refers to a type later in the stream or a record we
   // had to defer, defer it until later pass.
   unsigned MapPos = slotForIndex(Idx);
-  if (MapPos < IndexMap.size() && IndexMap[MapPos] != Untranslated) {
-    Idx = IndexMap[MapPos];
+  if (MapPos < Map.size() && Map[MapPos] != Untranslated) {
+    Idx = Map[MapPos];
     return true;
   }
 
   // If this is the second pass and this index isn't in the map, then it points
   // outside the current type stream, and this is a corrupt record.
-  if (IsSecondPass && MapPos >= IndexMap.size()) {
+  if (IsSecondPass && MapPos >= Map.size()) {
     // FIXME: Print a more useful error. We can give the current record and the
     // index that we think its pointing to.
     LastError = joinErrors(std::move(*LastError), errorCorruptRecord());
   }
 
   ++NumBadIndices;
 
   // This type index is invalid. Remap this to "not translated by cvpack",
   // and return failure.
   Idx = Untranslated;
   return false;
 }
 
+bool TypeStreamMerger::remapTypeIndex(TypeIndex &Idx) {
+  // If we're mapping a pure index stream, then IndexMap only contains mappings
+  // from OldIdStream -> NewIdStream, in which case we will need to use the
+  // special mapping from OldTypeStream -> NewTypeStream which was computed
+  // externally.  Regardless, we use this special map if and only if we are
+  // doing an id-only mapping.
+  if (DestTypeStream == nullptr)
+    return remapIndex(Idx, TypeLookup);
+
+  assert(TypeLookup.empty());
+  return remapIndex(Idx, IndexMap);
+}
+
+bool TypeStreamMerger::remapItemIndex(TypeIndex &Idx) {
+  assert(DestIdStream);
+  return remapIndex(Idx, IndexMap);
+}
+
 //----------------------------------------------------------------------------//
 // Item records
 //----------------------------------------------------------------------------//
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, FuncIdRecord &R) {
+  assert(DestIdStream);
   bool Success = true;
-  Success &= remapIndex(R.ParentScope);
-  Success &= remapIndex(R.FunctionType);
+  Success &= remapItemIndex(R.ParentScope);
+  Success &= remapTypeIndex(R.FunctionType);
   return writeIdRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, MemberFuncIdRecord &R) {
+  assert(DestIdStream);
   bool Success = true;
-  Success &= remapIndex(R.ClassType);
-  Success &= remapIndex(R.FunctionType);
+  Success &= remapTypeIndex(R.ClassType);
+  Success &= remapTypeIndex(R.FunctionType);
   return writeIdRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, StringIdRecord &R) {
-  return writeIdRecord(R, remapIndex(R.Id));
+  assert(DestIdStream);
+  return writeIdRecord(R, remapItemIndex(R.Id));
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, StringListRecord &R) {
+  assert(DestIdStream);
   bool Success = true;
   for (TypeIndex &Str : R.StringIndices)
-    Success &= remapIndex(Str);
+    Success &= remapItemIndex(Str);
   return writeIdRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, BuildInfoRecord &R) {
+  assert(DestIdStream);
   bool Success = true;
   for (TypeIndex &Arg : R.ArgIndices)
-    Success &= remapIndex(Arg);
+    Success &= remapItemIndex(Arg);
   return writeIdRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, UdtSourceLineRecord &R) {
+  assert(DestIdStream);
   bool Success = true;
-  Success &= remapIndex(R.UDT);
-  Success &= remapIndex(R.SourceFile);
+  Success &= remapTypeIndex(R.UDT);
+  Success &= remapItemIndex(R.SourceFile);
   // FIXME: Translate UdtSourceLineRecord into UdtModSourceLineRecords in the
   // IPI stream.
   return writeIdRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, UdtModSourceLineRecord &R) {
+  assert(DestIdStream);
   bool Success = true;
-  Success &= remapIndex(R.UDT);
-  Success &= remapIndex(R.SourceFile);
+  Success &= remapTypeIndex(R.UDT);
+  // UdtModSourceLine Source File Ids are offsets into the global string table.
+  // FIXME: We need to merge string table records for this to be valid.
+  // Success &= remapItemIndex(R.SourceFile);
   return writeIdRecord(R, Success);
 }
 
 //----------------------------------------------------------------------------//
 // Type records
 //----------------------------------------------------------------------------//
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, ModifierRecord &R) {
-  return writeRecord(R, remapIndex(R.ModifiedType));
+  assert(DestTypeStream);
+  return writeRecord(R, remapTypeIndex(R.ModifiedType));
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, ProcedureRecord &R) {
+  assert(DestTypeStream);
   bool Success = true;
-  Success &= remapIndex(R.ReturnType);
-  Success &= remapIndex(R.ArgumentList);
+  Success &= remapTypeIndex(R.ReturnType);
+  Success &= remapTypeIndex(R.ArgumentList);
   return writeRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, MemberFunctionRecord &R) {
+  assert(DestTypeStream);
   bool Success = true;
-  Success &= remapIndex(R.ReturnType);
-  Success &= remapIndex(R.ClassType);
-  Success &= remapIndex(R.ThisType);
-  Success &= remapIndex(R.ArgumentList);
+  Success &= remapTypeIndex(R.ReturnType);
+  Success &= remapTypeIndex(R.ClassType);
+  Success &= remapTypeIndex(R.ThisType);
+  Success &= remapTypeIndex(R.ArgumentList);
   return writeRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &Type, ArgListRecord &R) {
+  assert(DestTypeStream);
   bool Success = true;
   for (TypeIndex &Arg : R.ArgIndices)
-    Success &= remapIndex(Arg);
+    Success &= remapTypeIndex(Arg);
   if (auto EC = writeRecord(R, Success))
     return EC;
   return Error::success();
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, PointerRecord &R) {
+  assert(DestTypeStream);
   bool Success = true;
-  Success &= remapIndex(R.ReferentType);
+  Success &= remapTypeIndex(R.ReferentType);
   if (R.isPointerToMember())
-    Success &= remapIndex(R.MemberInfo->ContainingType);
+    Success &= remapTypeIndex(R.MemberInfo->ContainingType);
   return writeRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, ArrayRecord &R) {
+  assert(DestTypeStream);
   bool Success = true;
-  Success &= remapIndex(R.ElementType);
-  Success &= remapIndex(R.IndexType);
+  Success &= remapTypeIndex(R.ElementType);
+  Success &= remapTypeIndex(R.IndexType);
   return writeRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, ClassRecord &R) {
+  assert(DestTypeStream);
   bool Success = true;
-  Success &= remapIndex(R.FieldList);
-  Success &= remapIndex(R.DerivationList);
-  Success &= remapIndex(R.VTableShape);
+  Success &= remapTypeIndex(R.FieldList);
+  Success &= remapTypeIndex(R.DerivationList);
+  Success &= remapTypeIndex(R.VTableShape);
   return writeRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, UnionRecord &R) {
-  return writeRecord(R, remapIndex(R.FieldList));
+  assert(DestTypeStream);
+  return writeRecord(R, remapTypeIndex(R.FieldList));
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, EnumRecord &R) {
+  assert(DestTypeStream);
   bool Success = true;
-  Success &= remapIndex(R.FieldList);
-  Success &= remapIndex(R.UnderlyingType);
+  Success &= remapTypeIndex(R.FieldList);
+  Success &= remapTypeIndex(R.UnderlyingType);
   return writeRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, BitFieldRecord &R) {
-  return writeRecord(R, remapIndex(R.Type));
+  assert(DestTypeStream);
+  return writeRecord(R, remapTypeIndex(R.Type));
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, VFTableShapeRecord &R) {
+  assert(DestTypeStream);
   return writeRecord(R, true);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, TypeServer2Record &R) {
+  assert(DestTypeStream);
   return writeRecord(R, true);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, LabelRecord &R) {
+  assert(DestTypeStream);
   return writeRecord(R, true);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, VFTableRecord &R) {
+  assert(DestTypeStream);
   bool Success = true;
-  Success &= remapIndex(R.CompleteClass);
-  Success &= remapIndex(R.OverriddenVFTable);
+  Success &= remapTypeIndex(R.CompleteClass);
+  Success &= remapTypeIndex(R.OverriddenVFTable);
   return writeRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &,
                                          MethodOverloadListRecord &R) {
+  assert(DestTypeStream);
   bool Success = true;
   for (OneMethodRecord &Meth : R.Methods)
-    Success &= remapIndex(Meth.Type);
+    Success &= remapTypeIndex(Meth.Type);
   return writeRecord(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownRecord(CVType &, FieldListRecord &R) {
+  assert(DestTypeStream);
   // Visit the members inside the field list.
   HadUntranslatedMember = false;
-  FieldListBuilder.begin();
+  FieldListBuilder->begin();
   if (auto EC = codeview::visitMemberRecordStream(R.Data, *this))
     return EC;
 
   // Write the record if we translated all field list members.
   TypeIndex DestIdx = Untranslated;
   if (!HadUntranslatedMember)
-    DestIdx = FieldListBuilder.end();
+    DestIdx = FieldListBuilder->end();
   else
-    FieldListBuilder.reset();
+    FieldListBuilder->reset();
   addMapping(DestIdx);
 
   return Error::success();
 }
 
 //----------------------------------------------------------------------------//
 // Member records
 //----------------------------------------------------------------------------//
 
 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
                                          NestedTypeRecord &R) {
-  return writeMember(R, remapIndex(R.Type));
+  return writeMember(R, remapTypeIndex(R.Type));
 }
 
 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, OneMethodRecord &R) {
   bool Success = true;
-  Success &= remapIndex(R.Type);
+  Success &= remapTypeIndex(R.Type);
   return writeMember(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
                                          OverloadedMethodRecord &R) {
-  return writeMember(R, remapIndex(R.MethodList));
+  return writeMember(R, remapTypeIndex(R.MethodList));
 }
 
 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
                                          DataMemberRecord &R) {
-  return writeMember(R, remapIndex(R.Type));
+  return writeMember(R, remapTypeIndex(R.Type));
 }
 
 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
                                          StaticDataMemberRecord &R) {
-  return writeMember(R, remapIndex(R.Type));
+  return writeMember(R, remapTypeIndex(R.Type));
 }
 
 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
                                          EnumeratorRecord &R) {
   return writeMember(R, true);
 }
 
 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, VFPtrRecord &R) {
-  return writeMember(R, remapIndex(R.Type));
+  return writeMember(R, remapTypeIndex(R.Type));
 }
 
 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, BaseClassRecord &R) {
-  return writeMember(R, remapIndex(R.Type));
+  return writeMember(R, remapTypeIndex(R.Type));
 }
 
 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
                                          VirtualBaseClassRecord &R) {
   bool Success = true;
-  Success &= remapIndex(R.BaseType);
-  Success &= remapIndex(R.VBPtrType);
+  Success &= remapTypeIndex(R.BaseType);
+  Success &= remapTypeIndex(R.VBPtrType);
   return writeMember(R, Success);
 }
 
 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
                                          ListContinuationRecord &R) {
-  return writeMember(R, remapIndex(R.ContinuationIndex));
+  return writeMember(R, remapTypeIndex(R.ContinuationIndex));
 }
 
 Error TypeStreamMerger::visitUnknownType(CVType &Rec) {
   // We failed to translate a type. Translate this index as "not translated".
   addMapping(TypeIndex(SimpleTypeKind::NotTranslated));
   return errorCorruptRecord();
 }
 
-Error TypeStreamMerger::mergeStream(const CVTypeArray &Types) {
-  assert(IndexMap.empty());
+Error TypeStreamMerger::mergeTypeRecords(TypeTableBuilder &Dest,
+                                         TypeCollection &Types) {
+  DestTypeStream = &Dest;
+  FieldListBuilder = llvm::make_unique<FieldListRecordBuilder>(Dest);
+
+  return doit(Types);
+}
+
+Error TypeStreamMerger::mergeIdRecords(TypeTableBuilder &Dest,
+                                       ArrayRef<TypeIndex> TypeSourceToDest,
+                                       TypeCollection &Ids) {
+  DestIdStream = &Dest;
+  TypeLookup = TypeSourceToDest;
+
+  return doit(Ids);
+}
+
+Error TypeStreamMerger::mergeTypesAndIds(TypeTableBuilder &DestIds,
+                                         TypeTableBuilder &DestTypes,
+                                         TypeCollection &IdsAndTypes) {
+  DestIdStream = &DestIds;
+  DestTypeStream = &DestTypes;
+  FieldListBuilder = llvm::make_unique<FieldListRecordBuilder>(DestTypes);
+
+  return doit(IdsAndTypes);
+}
+
+Error TypeStreamMerger::doit(TypeCollection &Types) {
   LastError = Error::success();
 
   if (auto EC = codeview::visitTypeStream(Types, *this, Handler))
     return EC;
 
   // If we found bad indices but no other errors, try doing another pass and see
   // if we can resolve the indices that weren't in the map on the first pass.
   // This may require multiple passes, but we should always make progress. MASM
while (!*LastError && NumBadIndices > 0) {
     assert(NumBadIndices <= BadIndicesRemaining &&
            "second pass found more bad indices");
     if (!*LastError && NumBadIndices == BadIndicesRemaining) {
       return llvm::make_error<CodeViewError>(
           cv_error_code::corrupt_record, "input type graph contains cycles");
     }
   }
 
-  IndexMap.clear();
-
   Error Ret = std::move(*LastError);
   LastError.reset();
   return Ret;
 }
 
-Error llvm::codeview::mergeTypeStreams(TypeTableBuilder &DestIdStream,
-                                       TypeTableBuilder &DestTypeStream,
+Error llvm::codeview::mergeTypeRecords(TypeTableBuilder &Dest,
                                        SmallVectorImpl<TypeIndex> &SourceToDest,
                                        TypeServerHandler *Handler,
-                                       const CVTypeArray &Types) {
-  return TypeStreamMerger(DestIdStream, DestTypeStream, SourceToDest, Handler)
-      .mergeStream(Types);
+                                       TypeCollection &Types) {
+  TypeStreamMerger M(SourceToDest, Handler);
+  return M.mergeTypeRecords(Dest, Types);
+}
+
+Error llvm::codeview::mergeIdRecords(TypeTableBuilder &Dest,
+                                     ArrayRef<TypeIndex> TypeSourceToDest,
+                                     SmallVectorImpl<TypeIndex> &SourceToDest,
+                                     TypeCollection &Ids) {
+  TypeStreamMerger M(SourceToDest, nullptr);
+  return M.mergeIdRecords(Dest, TypeSourceToDest, Ids);
+}
+
+Error llvm::codeview::mergeTypeAndIdRecords(
+    TypeTableBuilder &DestIds, TypeTableBuilder &DestTypes,
+    SmallVectorImpl<TypeIndex> &SourceToDest, TypeServerHandler *Handler,
+    TypeCollection &IdsAndTypes) {
+
+  TypeStreamMerger M(SourceToDest, Handler);
+  return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes);
 }

llvm/trunk/lib/DebugInfo/PDB/Native/TpiStream.cpp

 //===- TpiStream.cpp - PDB Type Info (TPI) Stream 2 Access ----------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/PDB/Native/TpiStream.h"
+
 #include "llvm/ADT/iterator_range.h"
+#include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
 #include "llvm/DebugInfo/PDB/Native/PDBFile.h"
 #include "llvm/DebugInfo/PDB/Native/PDBTypeServerHandler.h"
 #include "llvm/DebugInfo/PDB/Native/RawConstants.h"
 #include "llvm/DebugInfo/PDB/Native/RawError.h"
 #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
 #include "llvm/DebugInfo/PDB/Native/TpiHashing.h"
if (Header->HashAdjBuffer.Length > 0) {
       HSR.setOffset(Header->HashAdjBuffer.Off);
       if (auto EC = HashAdjusters.load(HSR))
         return EC;
     }
 
     HashStream = std::move(HS);
   }
 
+  Types = llvm::make_unique<LazyRandomTypeCollection>(
+      TypeRecords, getNumTypeRecords(), getTypeIndexOffsets());
   return Error::success();
 }
 
 PdbRaw_TpiVer TpiStream::getTpiVersion() const {
   uint32_t Value = Header->Version;
   return static_cast<PdbRaw_TpiVer>(Value);
 }
 

llvm/trunk/test/DebugInfo/PDB/Inputs/merge-ids-1.yaml

+IpiStream:
+  Records:
+    # 'One' [TypeIndex: 0x1000 (4096)]
+    - Kind:            LF_STRING_ID
+      StringId:        
+        Id:              0
+        String:          'One'
+    # 'Two' [TypeIndex: 0x1001 (4097)]
+    - Kind:            LF_STRING_ID
+      StringId:        
+        Id:              0
+        String:          'Two'
+    # 'OnlyInFirst' [TypeIndex: 0x1002 (4098)]
+    - Kind:            LF_STRING_ID
+      StringId:        
+        Id:              0
+        String:          'OnlyInFirst'
+    # 'SubOne' [TypeIndex: 0x1003 (4099)]
+    - Kind:            LF_STRING_ID
+      StringId:        
+        Id:              0
+        String:          'SubOne'
+    # 'SubTwo' [TypeIndex: 0x1004 (4100)]
+    - Kind:            LF_STRING_ID
+      StringId:        
+        Id:              0
+        String:          'SubTwo'
+    # 'SubOne', 'SubTwo' [TypeIndex: 0x1005 (4101)]
+    - Kind:            LF_SUBSTR_LIST
+      StringList:      
+        StringIndices:   [ 4099, 4100 ]
+    # 'Main' {'SubOne', 'SubTwo'} [TypeIndex: 0x1006 (4102)]
+    - Kind:            LF_STRING_ID
+      StringId:        
+        Id:              4101
+        String:          'Main'

llvm/trunk/test/DebugInfo/PDB/Inputs/merge-ids-2.yaml

+IpiStream:       
+  Records:
+    # 'SubTwo' [TypeIndex: 0x1000 (4096)]
+    - Kind:            LF_STRING_ID
+      StringId:        
+        Id:              0
+        String:          'SubTwo'
+    # 'OnlyInSecond' [TypeIndex: 0x1001 (4097)]
+    - Kind:            LF_STRING_ID
+      StringId:        
+        Id:              0
+        String:          'OnlyInSecond'
+    # 'SubOne' [TypeIndex: 0x1002 (4098)]
+    - Kind:            LF_STRING_ID
+      StringId:        
+        Id:              0
+        String:          'SubOne'
+    # 'SubOne', 'SubTwo' [TypeIndex: 0x1003 (4099)]
+    - Kind:            LF_SUBSTR_LIST
+      StringList:      
+        StringIndices:   [ 4098, 4096 ]
+    # 'One' [TypeIndex: 0x1004 (4100)]
+    - Kind:            LF_STRING_ID
+      StringId:        
+        Id:              0
+        String:          'One'
+    # 'Main' {'SubOne', 'SubTwo'} [TypeIndex: 0x1005 (4101)]
+    - Kind:            LF_STRING_ID
+      StringId:        
+        Id:              4099
+        String:          'Main'

llvm/trunk/test/DebugInfo/PDB/Inputs/merge-ids-and-types-1.yaml

+# The idea is to set up some types in the TPI stream, and then have records in
+# the IPI stream that refer to them.  There are three types of IPI records that
+# can refer to TPI records.  They are:
+# 1) LF_PROCEDURE - Referred to by LF_FUNC_ID
+# 2) LF_STRUCTURE - Referred to by LF_UDT_MOD_SRC_LINE
+#                   Referred to by LF_UDT_SRC_LINE
+# 3) LF_MFUNCTION - Referred to by LF_MFUNC_ID
+# We will set up one of each of these, and then create IPI records that refer to
+# them.  We intentionally choose an unintuitive ordering of the records in both
+# streams (while still maintaining the topological sorting required by CodeView
+# type streams), to make sure the merging algorithm is sufficiently exercised.
+# For easy understanding, a semantic representation of the types we will set up
+# is as follows:
+#  - int main(int, char**)
+#
+#  - struct FooBar {
+#    public:
+#      void *FooMember;
+#      void FooMethod(int);
+#    };
+TpiStream:
+  Records:
+    # TypeIndex: 4096 (0x1000)
+    # char**
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    1136
+        Attrs:           32778
+    # TypeIndex: 4097 (0x1001)
+    # public void *FooMember
+    - Kind:            LF_FIELDLIST
+      FieldList:       
+        - Kind:            LF_MEMBER
+          DataMember:      
+            Attrs:           3           # public
+            Type:            1027        # void*
+            FieldOffset:     0
+            Name:            FooMember   # FooMember
+    # TypeIndex: 4098 (0x1002)
+    # (int, char**)
+    - Kind:            LF_ARGLIST
+      ArgList:         
+        ArgIndices:      [ 116, 4096 ]
+    # TypeIndex: 4099 (0x1003)
+    # struct FooBar {
+    # public:
+    #   void *FooMember;
+    # };
+    - Kind:            LF_STRUCTURE
+      Class:           
+        MemberCount:     1
+        Options:         [ None, HasUniqueName ]
+        FieldList:       4097
+        Name:            FooBar
+        UniqueName:      'FooBar'
+        DerivationList:  0
+        VTableShape:     0
+        Size:            4
+    # TypeIndex: 4100 (0x1004)
+    # FooBar *
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    4099       # FooBar
+        Attrs:           32778
+    # TypeIndex: 4101 (0x1005)
+    # (int)
+    - Kind:            LF_ARGLIST
+      ArgList:         
+        ArgIndices:      [ 116 ]
+    # TypeIndex: 4102 (0x1006)
+    - Kind:            LF_MFUNCTION
+      MemberFunction:  
+        ReturnType:      3                      # void
+        ClassType:       4099                   # struct FooBar
+        ThisType:        4100                   # FooBar *
+        CallConv:        ThisCall
+        Options:         [ None, Constructor ]
+        ParameterCount:  1
+        ArgumentList:    4101                   # (int)
+        ThisPointerAdjustment: 0
+    # TypeIndex: 4103 (0x1007)
+    # int (int, char**)
+    - Kind:            LF_PROCEDURE
+      Procedure:       
+        ReturnType:      116         # int
+        CallConv:        NearC
+        Options:         [ None ]
+        ParameterCount:  2
+        ArgumentList:    4098        # (int, char**)
+IpiStream:
+  Records:
+    # TypeIndex: 4096 (0x1000)
+    # int main(int, char **)
+    - Kind:            LF_FUNC_ID
+      FuncId:          
+        ParentScope:     0
+        FunctionType:    4103       # int main(int, char**)
+        Name:            main
+    # TypeIndex: 4097 (0x1001)
+    # void FooBar::FooMethod(int)
+    - Kind:            LF_MFUNC_ID
+      MemberFuncId:    
+        ClassType:       4099       # struct FooBar
+        FunctionType:    4102       # void FooMethod(int)
+        Name:            FooMethod
+    # TypeIndex: 4098 (0x1002)
+    # struct FooBar
+    - Kind:            LF_UDT_MOD_SRC_LINE
+      UdtModSourceLine: 
+        UDT:             4099       # struct FooBar
+        SourceFile:      0          # We don't support this yet
+        LineNumber:      0
+        Module:          0          # We don't support this yet

llvm/trunk/test/DebugInfo/PDB/Inputs/merge-ids-and-types-2.yaml

+# In file 1 we set up some basic types and IDs to refer to them.  In this file
+# we will set up the same types.  For some of them we will make them identical
+# but re-order the records in the file to make sure they have different type
+# indices and appear in different orders.  In other cases we will make slight
+# adjustments to the types, to ensure that they do not get merged in.
+# 
+# For easy understanding, a semantic representation of the types we will set up
+# is as follows:
+#  - int main(int, char**)    // This record should share an LF_PROCEDURE and id
+#                             // record with corresponding function from the
+#                             // first file.
+#  - int main2(int, char**)   // This record should share the LF_PROCEDURE
+#                             // record but have a unique id record.
+#  - void foo(int, char**)    // This record should have a unique LF_PROCEDURE
+#                             // record, but the LF_ARGLIST record internally
+#                             // should be shared.
+#
+#  - struct FooBar {          // Because the type of this record exactly matches
+#                             // the corresponding file, its entire type record
+#                             // hierarchy should be shared.
+#    public:
+#      void *FooMember;
+#      void FooMethod2(int);  // Note that the *type* of this member should be
+#                             // the same as the type of the record from the
+#                             // first stream.  But since it has a different
+#                             // name, it will not share an id record.
+#    };
+TpiStream:
+  Records:
+    # TypeIndex: 4096 (0x1000)
+    # (int)
+    - Kind:            LF_ARGLIST
+      ArgList:         
+        ArgIndices:      [ 116 ]
+    # TypeIndex: 4097 (0x1001)
+    # public void *FooMember
+    - Kind:            LF_FIELDLIST
+      FieldList:       
+        - Kind:            LF_MEMBER
+          DataMember:      
+            Attrs:           3           # public
+            Type:            1027        # void*
+            FieldOffset:     0
+            Name:            FooMember   # FooMember
+    # TypeIndex: 4098 (0x1002)
+    # char**
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    1136
+        Attrs:           32778
+    # TypeIndex: 4099 (0x1003)
+    # (int, char**)
+    - Kind:            LF_ARGLIST
+      ArgList:         
+        ArgIndices:      [ 116, 4098 ]
+    # TypeIndex: 4100 (0x1004)
+    # struct FooBar {
+    # public:
+    #   void *FooMember;
+    # };
+    - Kind:            LF_STRUCTURE
+      Class:           
+        MemberCount:     1
+        Options:         [ None, HasUniqueName ]
+        FieldList:       4097
+        Name:            FooBar
+        UniqueName:      'FooBar'
+        DerivationList:  0
+        VTableShape:     0
+        Size:            4
+    # TypeIndex: 4101 (0x1005)
+    # void (int, char**)
+    - Kind:            LF_PROCEDURE
+      Procedure:       
+        ReturnType:      3           # void
+        CallConv:        NearC
+        Options:         [ None ]
+        ParameterCount:  2
+        ArgumentList:    4099        # (int, char**)
+    # TypeIndex: 4102 (0x1006)
+    # FooBar *
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    4100       # FooBar
+        Attrs:           32778
+    # TypeIndex: 4103 (0x1007)
+    # int (int, char**)
+    - Kind:            LF_PROCEDURE
+      Procedure:       
+        ReturnType:      116         # int
+        CallConv:        NearC
+        Options:         [ None ]
+        ParameterCount:  2
+        ArgumentList:    4099        # (int, char**)
+    # TypeIndex: 4104 (0x1008)
+    - Kind:            LF_MFUNCTION
+      MemberFunction:  
+        ReturnType:      3                      # void
+        ClassType:       4100                   # struct FooBar
+        ThisType:        4102                   # FooBar *
+        CallConv:        ThisCall
+        Options:         [ None, Constructor ]
+        ParameterCount:  1
+        ArgumentList:    4096                   # (int)
+        ThisPointerAdjustment: 0
+IpiStream:
+  Records:
+    # TypeIndex: 4096 (0x1000)
+    # struct FooBar
+    - Kind:            LF_UDT_MOD_SRC_LINE
+      UdtModSourceLine: 
+        UDT:             4100       # struct FooBar
+        SourceFile:      0          # We don't support this yet
+        LineNumber:      0
+        Module:          0          # We don't support this yet
+    # TypeIndex: 4097 (0x1001)
+    # int main2(int, char **)
+    - Kind:            LF_FUNC_ID
+      FuncId:          
+        ParentScope:     0
+        FunctionType:    4103       # int main2(int, char**)
+        Name:            main2
+    # TypeIndex: 4098 (0x1002)
+    # void foo(int, char **)
+    - Kind:            LF_FUNC_ID
+      FuncId:          
+        ParentScope:     0
+        FunctionType:    4101       # void main2(int, char**)
+        Name:            foo
+    # TypeIndex: 4099 (0x1003)
+    # void FooBar::FooMethod2(int)
+    - Kind:            LF_MFUNC_ID
+      MemberFuncId:    
+        ClassType:       4100       # struct FooBar
+        FunctionType:    4104       # void FooBar::FooMethod2(int)
+        Name:            FooMethod2
+    # TypeIndex: 4100 (0x1004)
+    # int main(int, char **)
+    - Kind:            LF_FUNC_ID
+      FuncId:          
+        ParentScope:     0
+        FunctionType:    4103       # int main(int, char**)
+        Name:            main

llvm/trunk/test/DebugInfo/PDB/Inputs/merge-types-1.yaml

+---
+TpiStream:
+  Records:
+    # uint32_t* [Index: 0x1000]
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    117
+        Attrs:           32778
+    # int64_t* [Index: 0x1001]
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    118
+        Attrs:           32778
+    # struct OnlyInMerge1 [Index: 0x1002]
+    - Kind:            LF_STRUCTURE
+      Class:           
+        MemberCount:     0
+        Options:         [ None, ForwardReference, HasUniqueName ]
+        FieldList:       0
+        Name:            'OnlyInMerge1'
+        UniqueName:      'OnlyInMerge1'
+        DerivationList:  0
+        VTableShape:     0
+        Size:            0
+    # uint32_t** [Index: 0x1003]
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    4096
+        Attrs:           32778
+    # uint32_t*** [Index: 0x1004]
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    4099
+        Attrs:           32778
+    # int64_t* [Index: 0x1005]
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    4097
+        Attrs:           32778
+    # [uint32_t, uint32_t*, uint32_t**] [Index: 0x1006]
+    - Kind:            LF_ARGLIST
+      ArgList:         
+        ArgIndices:      [ 117, 4096, 4099 ]
+    # uint32_t (uint32_t, uint32_t*, uint32_t**) [Index: 0x1007]
+    - Kind:            LF_PROCEDURE
+      Procedure:       
+        ReturnType:      117
+        CallConv:        NearC
+        Options:         [ None ]
+        ParameterCount:  0
+        ArgumentList:    4102
+...

llvm/trunk/test/DebugInfo/PDB/Inputs/merge-types-2.yaml

+---
+TpiStream:
+  Records:         
+    # uint32_t* [Index: 0x1000]
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    117     
+        Attrs:           32778
+    # uint32_t** [Index: 0x1001]
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    4096    
+        Attrs:           32778
+    # uint32_t*** [Index: 0x1002]
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    4097    
+        Attrs:           32778
+    # [uint32_t, uint32_t*, uint32_t**] [Index: 0x1003]
+    - Kind:            LF_ARGLIST
+      ArgList:         
+        ArgIndices:      [ 117, 4096, 4097 ]
+    # uint32_t (uint32_t, uint32_t*, uint32_t**) [Index: 0x1004]
+    - Kind:            LF_PROCEDURE
+      Procedure:       
+        ReturnType:      117
+        CallConv:        NearC
+        Options:         [ None ]
+        ParameterCount:  0
+        ArgumentList:    4099
+    # int64_t* [Index: 0x1005]
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    118     
+        Attrs:           32778
+    # int64_t** [Index: 0x1006]
+    - Kind:            LF_POINTER
+      Pointer:         
+        ReferentType:    4101
+        Attrs:           32778
+    # struct OnlyInMerge2 [Index: 0x1007]
+    - Kind:            LF_STRUCTURE
+      Class:           
+        MemberCount:     0
+        Options:         [ None, ForwardReference, HasUniqueName ]
+        FieldList:       0
+        Name:            'OnlyInMerge2'
+        UniqueName:      'OnlyInMerge2'
+        DerivationList:  0
+        VTableShape:     0
+        Size:            0
+...

llvm/trunk/test/DebugInfo/PDB/Inputs/merge1.yaml

----
-TpiStream:
-  Records:
-    # uint32_t* [Index: 0x1000]
-    - Kind:            LF_POINTER
-      Pointer:         
-        ReferentType:    117
-        Attrs:           32778
-    # int64_t* [Index: 0x1001]
-    - Kind:            LF_POINTER
-      Pointer:         
-        ReferentType:    118
-        Attrs:           32778
-    # struct OnlyInMerge1 [Index: 0x1002]
-    - Kind:            LF_STRUCTURE
-      Class:           
-        MemberCount:     0
-        Options:         [ None, ForwardReference, HasUniqueName ]
-        FieldList:       0
-        Name:            'OnlyInMerge1'
-        UniqueName:      'OnlyInMerge1'
-        DerivationList:  0
-        VTableShape:     0
-        Size:            0
-    # uint32_t** [Index: 0x1003]
-    - Kind:            LF_POINTER
-      Pointer:         
-        ReferentType:    4096
-        Attrs:           32778
-    # uint32_t*** [Index: 0x1004]
-    - Kind:            LF_POINTER
-      Pointer:         
-        ReferentType:    4099
-        Attrs:           32778
-    # int64_t* [Index: 0x1005]
-    - Kind:            LF_POINTER
-      Pointer:         
-        ReferentType:    4097
-        Attrs:           32778
-    # [uint32_t, uint32_t*, uint32_t**] [Index: 0x1006]
-    - Kind:            LF_ARGLIST
-      ArgList:         
-        ArgIndices:      [ 117, 4096, 4099 ]
-    # uint32_t (uint32_t, uint32_t*, uint32_t**) [Index: 0x1007]
-    - Kind:            LF_PROCEDURE
-      Procedure:       
-        ReturnType:      117
-        CallConv:        NearC
-        Options:         [ None ]
-        ParameterCount:  0
-        ArgumentList:    4102
-...

llvm/trunk/test/DebugInfo/PDB/Inputs/merge2.yaml

----
-TpiStream:
-  Records:         
-    # uint32_t* [Index: 0x1000]
-    - Kind:            LF_POINTER
-      Pointer:         
-        ReferentType:    117     
-        Attrs:           32778
-    # uint32_t** [Index: 0x1001]
-    - Kind:            LF_POINTER
-      Pointer:         
-        ReferentType:    4096    
-        Attrs:           32778
-    # uint32_t*** [Index: 0x1002]
-    - Kind:            LF_POINTER
-      Pointer:         
-        ReferentType:    4097    
-        Attrs:           32778
-    # [uint32_t, uint32_t*, uint32_t**] [Index: 0x1003]
-    - Kind:            LF_ARGLIST
-      ArgList:         
-        ArgIndices:      [ 117, 4096, 4097 ]
-    # uint32_t (uint32_t, uint32_t*, uint32_t**) [Index: 0x1004]
-    - Kind:            LF_PROCEDURE
-      Procedure:       
-        ReturnType:      117
-        CallConv:        NearC
-        Options:         [ None ]
-        ParameterCount:  0
-        ArgumentList:    4099
-    # int64_t* [Index: 0x1005]
-    - Kind:            LF_POINTER
-      Pointer:         
-        ReferentType:    118     
-        Attrs:           32778
-    # int64_t** [Index: 0x1006]
-    - Kind:            LF_POINTER
-      Pointer:         
-        ReferentType:    4101
-        Attrs:           32778
-    # struct OnlyInMerge2 [Index: 0x1007]
-    - Kind:            LF_STRUCTURE
-      Class:           
-        MemberCount:     0
-        Options:         [ None, ForwardReference, HasUniqueName ]
-        FieldList:       0
-        Name:            'OnlyInMerge2'
-        UniqueName:      'OnlyInMerge2'
-        DerivationList:  0
-        VTableShape:     0
-        Size:            0
-...

llvm/trunk/test/DebugInfo/PDB/pdbdump-merge-ids-and-types.test

+; RUN: llvm-pdbdump yaml2pdb -pdb=%t.1.pdb %p/Inputs/merge-ids-and-types-1.yaml
+; RUN: llvm-pdbdump yaml2pdb -pdb=%t.2.pdb %p/Inputs/merge-ids-and-types-2.yaml
+; RUN: llvm-pdbdump merge -pdb=%t.3.pdb %t.1.pdb %t.2.pdb
+; RUN: llvm-pdbdump raw -tpi-records %t.3.pdb | FileCheck -check-prefix=TPI-TYPES %s
+; RUN: llvm-pdbdump raw -tpi-records %t.3.pdb | FileCheck -check-prefix=INTMAIN %s
+; RUN: llvm-pdbdump raw -tpi-records %t.3.pdb | FileCheck -check-prefix=VOIDMAIN %s
+; RUN: llvm-pdbdump raw -ipi-records %t.3.pdb | FileCheck -check-prefix=IPI-TYPES %s
+; RUN: llvm-pdbdump raw -ipi-records %t.3.pdb | FileCheck -check-prefix=IPI-NAMES %s
+; RUN: llvm-pdbdump raw -ipi-records %t.3.pdb | FileCheck -check-prefix=IPI-UDT %s
+
+TPI-TYPES:     Type Info Stream (TPI)
+TPI-TYPES:     Record count: 9
+TPI-TYPES-DAG: TypeLeafKind: LF_POINTER
+TPI-TYPES-DAG: TypeLeafKind: LF_FIELDLIST
+TPI-TYPES-DAG: TypeLeafKind: LF_ARGLIST
+TPI-TYPES-DAG: TypeLeafKind: LF_STRUCTURE
+TPI-TYPES-DAG: TypeLeafKind: LF_MEMBER
+TPI-TYPES-DAG: TypeLeafKind: LF_POINTER
+TPI-TYPES-DAG: TypeLeafKind: LF_ARGLIST
+TPI-TYPES-DAG: TypeLeafKind: LF_MFUNCTION
+TPI-TYPES-DAG: TypeLeafKind: LF_PROCEDURE
+TPI-TYPES-DAG: TypeLeafKind: LF_PROCEDURE
+TPI-TYPES-DAG: TypeLeafKind: LF_ARGLIST
+
+; Both procedures should use the same arglist even though they have a different
+; return type.
+INTMAIN:      ArgList ([[ID:.*]])
+INTMAIN-NEXT:   TypeLeafKind: LF_ARGLIST
+INTMAIN-NEXT:   NumArgs: 2
+INTMAIN-NEXT:   Arguments [
+INTMAIN-NEXT:     ArgType: int
+INTMAIN-NEXT:     ArgType: char**
+INTMAIN:        TypeLeafKind: LF_PROCEDURE
+INTMAIN:          ReturnType: int
+INTMAIN:          NumParameters: 2
+INTMAIN-NEXT:     ArgListType: (int, char**) ([[ID]])
+
+VOIDMAIN:      ArgList ([[ID:.*]])
+VOIDMAIN-NEXT:   TypeLeafKind: LF_ARGLIST
+VOIDMAIN-NEXT:   NumArgs: 2
+VOIDMAIN-NEXT:   Arguments [
+VOIDMAIN-NEXT:     ArgType: int
+VOIDMAIN-NEXT:     ArgType: char**
+VOIDMAIN:        TypeLeafKind: LF_PROCEDURE
+VOIDMAIN:          ReturnType: void
+VOIDMAIN:          NumParameters: 2
+VOIDMAIN-NEXT:     ArgListType: (int, char**) ([[ID]])
+
+IPI-TYPES:     Type Info Stream (IPI)
+IPI-TYPES:     Record count: 6
+IPI-TYPES-DAG: TypeLeafKind: LF_FUNC_ID
+IPI-TYPES-DAG: TypeLeafKind: LF_MFUNC_ID
+IPI-TYPES-DAG: TypeLeafKind: LF_UDT_MOD_SRC_LINE
+IPI-TYPES-DAG: TypeLeafKind: LF_FUNC_ID
+IPI-TYPES-DAG: TypeLeafKind: LF_FUNC_ID
+IPI-TYPES-DAG: TypeLeafKind: LF_MFUNC_ID
+
+IPI-NAMES-DAG: Name: main
+IPI-NAMES-DAG: Name: FooMethod
+IPI-NAMES-DAG: Name: main2
+IPI-NAMES-DAG: Name: foo
+IPI-NAMES-DAG: Name: FooMethod2
+
+IPI-UDT:      TypeLeafKind: LF_UDT_MOD_SRC_LINE
+IPI-UDT-NEXT: UDT: FooBar

llvm/trunk/test/DebugInfo/PDB/pdbdump-mergeids.test

+; RUN: llvm-pdbdump yaml2pdb -pdb=%t.1.pdb %p/Inputs/merge-ids-1.yaml
+; RUN: llvm-pdbdump yaml2pdb -pdb=%t.2.pdb %p/Inputs/merge-ids-2.yaml
+; RUN: llvm-pdbdump merge -pdb=%t.3.pdb %t.1.pdb %t.2.pdb
+; RUN: llvm-pdbdump raw -ipi-records %t.3.pdb | FileCheck -check-prefix=MERGED %s
+; RUN: llvm-pdbdump raw -ipi-records %t.3.pdb | FileCheck -check-prefix=SUBSTRS %s
+; RUN: llvm-pdbdump raw -tpi-records %t.3.pdb | FileCheck -check-prefix=TPI-EMPTY %s
+
+
+MERGED: Type Info Stream (IPI)
+MERGED: Record count: 8
+MERGED-DAG: StringData: One
+MERGED-DAG: StringData: Two
+MERGED-DAG: StringData: SubOne
+MERGED-DAG: StringData: SubTwo
+MERGED-DAG: StringData: Main
+MERGED-DAG: TypeLeafKind: LF_SUBSTR_LIST
+MERGED-DAG: StringData: OnlyInFirst
+MERGED-DAG: StringData: OnlyInSecond
+
+SUBSTRS:      StringList
+SUBSTRS:        TypeLeafKind: LF_SUBSTR_LIST
+SUBSTRS-NEXT:   NumStrings: 2
+SUBSTRS-NEXT:   Strings [
+SUBSTRS-NEXT:     SubOne
+SUBSTRS-NEXT:     SubTwo
+SUBSTRS:      StringId
+SUBSTRS-NEXT:   TypeLeafKind: LF_STRING_ID
+SUBSTRS-NEXT:   Id: "SubOne" "SubTwo"
+SUBSTRS-NEXT:   StringData: Main
+
+TPI-EMPTY: Record count: 0

llvm/trunk/test/DebugInfo/PDB/pdbdump-mergetypes.test

-; RUN: llvm-pdbdump yaml2pdb -pdb=%t.1.pdb %p/Inputs/merge1.yaml
-; RUN: llvm-pdbdump yaml2pdb -pdb=%t.2.pdb %p/Inputs/merge2.yaml
+; RUN: llvm-pdbdump yaml2pdb -pdb=%t.1.pdb %p/Inputs/merge-types-1.yaml
+; RUN: llvm-pdbdump yaml2pdb -pdb=%t.2.pdb %p/Inputs/merge-types-2.yaml
 ; RUN: llvm-pdbdump merge -pdb=%t.3.pdb %t.1.pdb %t.2.pdb
 ; RUN: llvm-pdbdump raw -tpi-records %t.3.pdb | FileCheck -check-prefix=MERGED %s
 ; RUN: llvm-pdbdump raw -tpi-records %t.3.pdb | FileCheck -check-prefix=ARGLIST %s
 
 
 MERGED: Type Info Stream (TPI)
 MERGED: Record count: 9
 MERGED-DAG: PointeeType: unsigned

llvm/trunk/tools/llvm-pdbdump/llvm-pdbdump.cpp

if (YamlObj.StringTable.hasValue()) {
     auto &Strings = Builder.getStringTableBuilder();
     for (auto S : *YamlObj.StringTable)
       Strings.insert(S);
   }
 
   pdb::yaml::PdbInfoStream DefaultInfoStream;
   pdb::yaml::PdbDbiStream DefaultDbiStream;
   pdb::yaml::PdbTpiStream DefaultTpiStream;
+  pdb::yaml::PdbTpiStream DefaultIpiStream;
 
   const auto &Info = YamlObj.PdbStream.getValueOr(DefaultInfoStream);
 
   auto &InfoBuilder = Builder.getInfoBuilder();
   InfoBuilder.setAge(Info.Age);
   InfoBuilder.setGuid(Info.Guid);
   InfoBuilder.setSignature(Info.Signature);
   InfoBuilder.setVersion(Info.Version);
static void yamlToPdb(StringRef Path) {
   }
 
   auto &TpiBuilder = Builder.getTpiBuilder();
   const auto &Tpi = YamlObj.TpiStream.getValueOr(DefaultTpiStream);
   TpiBuilder.setVersionHeader(Tpi.Version);
   for (const auto &R : Tpi.Records)
     TpiBuilder.addTypeRecord(R.Record.data(), R.Record.Hash);
 
-  const auto &Ipi = YamlObj.IpiStream.getValueOr(DefaultTpiStream);
+  const auto &Ipi = YamlObj.IpiStream.getValueOr(DefaultIpiStream);
   auto &IpiBuilder = Builder.getIpiBuilder();
   IpiBuilder.setVersionHeader(Ipi.Version);
   for (const auto &R : Ipi.Records)
-    TpiBuilder.addTypeRecord(R.Record.data(), R.Record.Hash);
+    IpiBuilder.addTypeRecord(R.Record.data(), R.Record.Hash);
 
   ExitOnErr(Builder.commit(opts::yaml2pdb::YamlPdbOutputFile));
 }
 
 static PDBFile &loadPDB(StringRef Path, std::unique_ptr<IPDBSession> &Session) {
   ExitOnErr(loadDataForPDB(PDB_ReaderType::Native, Path, Session));
 
   NativeSession *NS = static_cast<NativeSession *>(Session.get());
static void mergePdbs() {
   BumpPtrAllocator Allocator;
   TypeTableBuilder MergedTpi(Allocator);
   TypeTableBuilder MergedIpi(Allocator);
 
   // Create a Tpi and Ipi type table with all types from all input files.
   for (const auto &Path : opts::merge::InputFilenames) {
     std::unique_ptr<IPDBSession> Session;
     auto &File = loadPDB(Path, Session);
-    SmallVector<TypeIndex, 128> SourceToDest;
+    SmallVector<TypeIndex, 128> TypeMap;
+    SmallVector<TypeIndex, 128> IdMap;
     if (File.hasPDBTpiStream()) {
-      SourceToDest.clear();
       auto &Tpi = ExitOnErr(File.getPDBTpiStream());
-      ExitOnErr(codeview::mergeTypeStreams(MergedIpi, MergedTpi, SourceToDest,
-                                           nullptr, Tpi.typeArray()));
+      ExitOnErr(codeview::mergeTypeRecords(MergedTpi, TypeMap, nullptr,
+                                           Tpi.typeCollection()));
     }
     if (File.hasPDBIpiStream()) {
-      SourceToDest.clear();
       auto &Ipi = ExitOnErr(File.getPDBIpiStream());
-      ExitOnErr(codeview::mergeTypeStreams(MergedIpi, MergedTpi, SourceToDest,
-                                           nullptr, Ipi.typeArray()));
+      ExitOnErr(codeview::mergeIdRecords(MergedIpi, TypeMap, IdMap,
+                                         Ipi.typeCollection()));
     }
   }
 
   // Then write the PDB.
   PDBFileBuilder Builder(Allocator);
   ExitOnErr(Builder.initialize(4096));
   // Add each of the reserved streams.  We might not put any data in them,
   // but at least they have to be present.

llvm/trunk/tools/llvm-readobj/COFFDumper.cpp

if (SectionName == ".debug$T") {
 
       CVTypeArray Types;
       BinaryStreamReader Reader(Data, llvm::support::little);
       if (auto EC = Reader.readArray(Types, Reader.getLength())) {
         consumeError(std::move(EC));
         W.flush();
         error(object_error::parse_failed);
       }
+      LazyRandomTypeCollection TypesAndIds(Types, 100);
       SmallVector<TypeIndex, 128> SourceToDest;
-      if (auto EC =
-              mergeTypeStreams(CVIDs, CVTypes, SourceToDest, nullptr, Types))
+      if (auto EC = mergeTypeAndIdRecords(CVIDs, CVTypes, SourceToDest, nullptr,
+                                          TypesAndIds))
         return error(std::move(EC));
     }
   }
 }
 
 void COFFDumper::printCodeViewTypeSection(StringRef SectionName,
                                           const SectionRef &Section) {
   ListScope D(W, "CodeViewTypes");