[CodeView Type Merging] Make a Type Index Iterator that bypasses the visitor framework

[zturner]

Summary

The visitor abstraction is useful for plugging lots of somewhat related components together, but with abstraction comes a cost in performance. Type Merging is easily the slowest part of a link, so it makes sense to consider whether it's worth sacrifcing abstractional purity in exchange for speed here.

This patch swings completely the opposite direction. It bypasses the TempSerializer, it bypasses the FieldListRecordBuilder, it bypasses the TypeRecordMapping, and it bypasses the visitation switch and instead re-implements the record deserialization switch in a hand rolled algorithm that doesn't care about deserializing at all, but only about knowing what offsets within a record's byte sequence contain type indices.

For field list records in particular, this algorithm also implements the logic of skipping a record to find the next record. This allows us to completely skip the process of deserializing field list records in order to determine what indices to remap, and then re-serializing them. Furthermore, computing "how many bytes is this field list member record" is somewhat faster than actually pulling out all the fields of the record.

The algorithm here simply gets as input a sequence of bytes, and returns as output a list of offsets that we need to remap.

Performance wise, this is a huge win. This is linking lld using clang-cl generated objects and library inputs (so /Z7) before this patch, after this patch, and using MSVC.

MSVC: 25.67s
Before Patch: 18.59s
After Patch: 8.92s

[rnk]

Sweet, the minimal thing. :)

llvm/include/llvm/DebugInfo/CodeView/TypeIndexIterator.h

1 ↗

(On Diff #100289)

This basically builds a SmallVector. Its... sort of like an iterator. Do we still want to call it one? I feel like "Iterator" has a specific meaning in C++, and this isn't it. Maybe TypeIndexFinder.h to go with findTypeIndexOffsets or something?

Alternatively, do you want to just mush all this functionality into TypeSerializer.h/cpp?

llvm/include/llvm/DebugInfo/CodeView/TypeRecord.h

288 ↗

(On Diff #100289)

How is this new constructor used? It's reasonable to not force the caller to construct a MemberPointerInfo and instead take both the Class type index and the member pointer representation, but defaulting unknown seems error-prone.

llvm/lib/DebugInfo/CodeView/TypeIndexIterator.cpp

1 ↗

(On Diff #100289)

This should have one of those silly LLVM-style comment headers.

272 ↗

(On Diff #100289)

If we still had those Layout struct types, we could use offsetof(FuncIdRecord::Layout, ParentScope) etc here to avoid the hardcoded offsets. It would save work when we add new type records. Probably not a change for today, but maybe worth a FIXME comment?

[zturner]

llvm/include/llvm/DebugInfo/CodeView/TypeIndexIterator.h

1 ↗

(On Diff #100289)

Yea, I originally intended to give it an iterator like interface, but it was non-trivial and this was just easier. And then I forgot to change the file name. Anyway, yea I'll change it.

llvm/include/llvm/DebugInfo/CodeView/TypeRecord.h

288 ↗

(On Diff #100289)

It's used in the unit test.

[rnk]

llvm/include/llvm/DebugInfo/CodeView/TypeRecord.h

288 ↗

(On Diff #100289)

Got it, I searched for PointerRecord( and got no hits. I'd still prefer to make that constructor call build a MemberPointerInfo().

[zturner]

Getting a crash with this in llvm-readobj, so I need to fix that and will upload a new version.

[zturner]

Fix the crasher. It was because we were only handling LF_CLASS, but not LF_STRUCTURE which has the same format. Added a unit test for this.

[rnk]

lgtm!

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

+//===- TypeIndexDiscovery.h -------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_CODEVIEW_TYPEINDEXDISCOVERY_H
+#define LLVM_DEBUGINFO_CODEVIEW_TYPEINDEXDISCOVERY_H
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/DebugInfo/CodeView/TypeRecord.h"
+#include "llvm/Support/Error.h"
+
+namespace llvm {
+namespace codeview {
+enum class TiRefKind { TypeRef, IndexRef };
+struct TiReference {
+  TiRefKind Kind;
+  uint32_t Offset;
+  uint32_t Count;
+};
+
+void discoverTypeIndices(ArrayRef<uint8_t> RecordData,
+                         SmallVectorImpl<TiReference> &Refs);
+void discoverTypeIndices(const CVType &Type,
+                         SmallVectorImpl<TiReference> &Refs);
+}
+}
+
+#endif

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

PointerRecord(TypeIndex ReferentType, uint32_t Attrs)
         Attrs(Attrs) {}
 
   PointerRecord(TypeIndex ReferentType, PointerKind PK, PointerMode PM,
                 PointerOptions PO, uint8_t Size)
       : TypeRecord(TypeRecordKind::Pointer), ReferentType(ReferentType),
         Attrs(calcAttrs(PK, PM, PO, Size)) {}
 
   PointerRecord(TypeIndex ReferentType, PointerKind PK, PointerMode PM,
-                PointerOptions PO, uint8_t Size,
-                const MemberPointerInfo &Member)
+                PointerOptions PO, uint8_t Size, const MemberPointerInfo &MPI)
       : TypeRecord(TypeRecordKind::Pointer), ReferentType(ReferentType),
-        Attrs(calcAttrs(PK, PM, PO, Size)), MemberInfo(Member) {}
-
-  PointerRecord(TypeIndex ReferentType, uint32_t Attrs,
-                const MemberPointerInfo &Member)
-      : TypeRecord(TypeRecordKind::Pointer), ReferentType(ReferentType),
-        Attrs(Attrs), MemberInfo(Member) {}
+        Attrs(calcAttrs(PK, PM, PO, Size)), MemberInfo(MPI) {}
 
   TypeIndex getReferentType() const { return ReferentType; }
 
   PointerKind getPointerKind() const {
     return static_cast<PointerKind>((Attrs >> PointerKindShift) &
                                     PointerKindMask);
   }
 

llvm/trunk/lib/DebugInfo/CodeView/CMakeLists.txt

add_llvm_library(LLVMDebugInfoCodeView
   StringTable.cpp
   SymbolRecordMapping.cpp
   SymbolDumper.cpp
   SymbolSerializer.cpp
   TypeDatabase.cpp
   TypeDatabaseVisitor.cpp
   TypeDumpVisitor.cpp
   TypeIndex.cpp
+  TypeIndexDiscovery.cpp
   TypeRecordMapping.cpp
   TypeSerializer.cpp
   TypeStreamMerger.cpp
   TypeTableCollection.cpp
   
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/DebugInfo/CodeView
   )

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

+//===- TypeIndexDiscovery.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/TypeIndexDiscovery.h"
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/Endian.h"
+
+using namespace llvm;
+using namespace llvm::codeview;
+
+static inline MethodKind getMethodKind(uint16_t Attrs) {
+  Attrs &= uint16_t(MethodOptions::MethodKindMask);
+  Attrs >>= 2;
+  return MethodKind(Attrs);
+}
+
+static inline bool isIntroVirtual(uint16_t Attrs) {
+  MethodKind MK = getMethodKind(Attrs);
+  return MK == MethodKind::IntroducingVirtual ||
+         MK == MethodKind::PureIntroducingVirtual;
+}
+
+static inline PointerMode getPointerMode(uint32_t Attrs) {
+  return static_cast<PointerMode>((Attrs >> PointerRecord::PointerModeShift) &
+                                  PointerRecord::PointerModeMask);
+}
+
+static inline bool isMemberPointer(uint32_t Attrs) {
+  PointerMode Mode = getPointerMode(Attrs);
+  return Mode == PointerMode::PointerToDataMember ||
+         Mode == PointerMode::PointerToDataMember;
+}
+
+static inline uint32_t getEncodedIntegerLength(ArrayRef<uint8_t> Data) {
+  uint16_t N = support::endian::read16le(Data.data());
+  if (N < LF_NUMERIC)
+    return 2;
+
+  assert(N <= LF_UQUADWORD);
+
+  constexpr uint32_t Sizes[] = {
+      1,  // LF_CHAR
+      2,  // LF_SHORT
+      2,  // LF_USHORT
+      4,  // LF_LONG
+      4,  // LF_ULONG
+      4,  // LF_REAL32
+      8,  // LF_REAL64
+      10, // LF_REAL80
+      16, // LF_REAL128
+      8,  // LF_QUADWORD
+      8,  // LF_UQUADWORD
+  };
+
+  return Sizes[N - LF_NUMERIC];
+}
+
+static inline uint32_t getCStringLength(ArrayRef<uint8_t> Data) {
+  const char *S = reinterpret_cast<const char *>(Data.data());
+  return strlen(S) + 1;
+}
+
+static void handleMethodOverloadList(ArrayRef<uint8_t> Content,
+                                     SmallVectorImpl<TiReference> &Refs) {
+  uint32_t Offset = 0;
+
+  while (!Content.empty()) {
+    // Array of:
+    //   0: Attrs
+    //   2: Padding
+    //   4: TypeIndex
+    //   if (isIntroVirtual())
+    //     8: VFTableOffset
+
+    // At least 8 bytes are guaranteed.  4 extra bytes come iff function is an
+    // intro virtual.
+    uint32_t Len = 8;
+
+    uint16_t Attrs = support::endian::read16le(Content.data());
+    Refs.push_back({TiRefKind::TypeRef, Offset + 4, 1});
+
+    if (LLVM_UNLIKELY(isIntroVirtual(Attrs)))
+      Len += 4;
+    Offset += Len;
+    Content = Content.drop_front(Len);
+  }
+}
+
+static uint32_t handleBaseClass(ArrayRef<uint8_t> Data, uint32_t Offset,
+                                SmallVectorImpl<TiReference> &Refs) {
+  // 0: Kind
+  // 2: Padding
+  // 4: TypeIndex
+  // 8: Encoded Integer
+  Refs.push_back({TiRefKind::TypeRef, Offset + 4, 1});
+  return 8 + getEncodedIntegerLength(Data.drop_front(8));
+}
+
+static uint32_t handleEnumerator(ArrayRef<uint8_t> Data, uint32_t Offset,
+                                 SmallVectorImpl<TiReference> &Refs) {
+  // 0: Kind
+  // 2: Padding
+  // 4: Encoded Integer
+  // <next>: Name
+  uint32_t Size = 4 + getEncodedIntegerLength(Data.drop_front(4));
+  return Size + getCStringLength(Data.drop_front(Size));
+}
+
+static uint32_t handleDataMember(ArrayRef<uint8_t> Data, uint32_t Offset,
+                                 SmallVectorImpl<TiReference> &Refs) {
+  // 0: Kind
+  // 2: Padding
+  // 4: TypeIndex
+  // 8: Encoded Integer
+  // <next>: Name
+  Refs.push_back({TiRefKind::TypeRef, Offset + 4, 1});
+  uint32_t Size = 8 + getEncodedIntegerLength(Data.drop_front(8));
+  return Size + getCStringLength(Data.drop_front(Size));
+}
+
+static uint32_t handleOverloadedMethod(ArrayRef<uint8_t> Data, uint32_t Offset,
+                                       SmallVectorImpl<TiReference> &Refs) {
+  // 0: Kind
+  // 2: Padding
+  // 4: TypeIndex
+  // 8: Name
+  Refs.push_back({TiRefKind::TypeRef, Offset + 4, 1});
+  return 8 + getCStringLength(Data.drop_front(8));
+}
+
+static uint32_t handleOneMethod(ArrayRef<uint8_t> Data, uint32_t Offset,
+                                SmallVectorImpl<TiReference> &Refs) {
+  // 0: Kind
+  // 2: Attributes
+  // 4: Type
+  // if (isIntroVirtual)
+  //   8: VFTableOffset
+  // <next>: Name
+  uint32_t Size = 8;
+  Refs.push_back({TiRefKind::TypeRef, Offset + 4, 1});
+
+  uint16_t Attrs = support::endian::read16le(Data.drop_front(2).data());
+  if (LLVM_UNLIKELY(isIntroVirtual(Attrs)))
+    Size += 4;
+
+  return Size + getCStringLength(Data.drop_front(Size));
+}
+
+static uint32_t handleNestedType(ArrayRef<uint8_t> Data, uint32_t Offset,
+                                 SmallVectorImpl<TiReference> &Refs) {
+  // 0: Kind
+  // 2: Padding
+  // 4: TypeIndex
+  // 8: Name
+  Refs.push_back({TiRefKind::TypeRef, Offset + 4, 1});
+  return 8 + getCStringLength(Data.drop_front(8));
+}
+
+static uint32_t handleStaticDataMember(ArrayRef<uint8_t> Data, uint32_t Offset,
+                                       SmallVectorImpl<TiReference> &Refs) {
+  // 0: Kind
+  // 2: Padding
+  // 4: TypeIndex
+  // 8: Name
+  Refs.push_back({TiRefKind::TypeRef, Offset + 4, 1});
+  return 8 + getCStringLength(Data.drop_front(8));
+}
+
+static uint32_t handleVirtualBaseClass(ArrayRef<uint8_t> Data, uint32_t Offset,
+                                       bool IsIndirect,
+                                       SmallVectorImpl<TiReference> &Refs) {
+  // 0: Kind
+  // 2: Attrs
+  // 4: TypeIndex
+  // 8: TypeIndex
+  // 12: Encoded Integer
+  // <next>: Encoded Integer
+  uint32_t Size = 12;
+  Refs.push_back({TiRefKind::TypeRef, Offset + 4, 2});
+  Size += getEncodedIntegerLength(Data.drop_front(Size));
+  Size += getEncodedIntegerLength(Data.drop_front(Size));
+  return Size;
+}
+
+static uint32_t handleVFPtr(ArrayRef<uint8_t> Data, uint32_t Offset,
+                            SmallVectorImpl<TiReference> &Refs) {
+  // 0: Kind
+  // 2: Padding
+  // 4: TypeIndex
+  Refs.push_back({TiRefKind::TypeRef, Offset + 4, 1});
+  return 8;
+}
+
+static uint32_t handleListContinuation(ArrayRef<uint8_t> Data, uint32_t Offset,
+                                       SmallVectorImpl<TiReference> &Refs) {
+  // 0: Kind
+  // 2: Padding
+  // 4: TypeIndex
+  Refs.push_back({TiRefKind::TypeRef, Offset + 4, 1});
+  return 8;
+}
+
+static void handleFieldList(ArrayRef<uint8_t> Content,
+                            SmallVectorImpl<TiReference> &Refs) {
+  uint32_t Offset = 0;
+  uint32_t ThisLen = 0;
+  while (!Content.empty()) {
+    TypeLeafKind Kind =
+        static_cast<TypeLeafKind>(support::endian::read16le(Content.data()));
+    switch (Kind) {
+    case LF_BCLASS:
+      ThisLen = handleBaseClass(Content, Offset, Refs);
+      break;
+    case LF_ENUMERATE:
+      ThisLen = handleEnumerator(Content, Offset, Refs);
+      break;
+    case LF_MEMBER:
+      ThisLen = handleDataMember(Content, Offset, Refs);
+      break;
+    case LF_METHOD:
+      ThisLen = handleOverloadedMethod(Content, Offset, Refs);
+      break;
+    case LF_ONEMETHOD:
+      ThisLen = handleOneMethod(Content, Offset, Refs);
+      break;
+    case LF_NESTTYPE:
+      ThisLen = handleNestedType(Content, Offset, Refs);
+      break;
+    case LF_STMEMBER:
+      ThisLen = handleStaticDataMember(Content, Offset, Refs);
+      break;
+    case LF_VBCLASS:
+    case LF_IVBCLASS:
+      ThisLen =
+          handleVirtualBaseClass(Content, Offset, Kind == LF_VBCLASS, Refs);
+      break;
+    case LF_VFUNCTAB:
+      ThisLen = handleVFPtr(Content, Offset, Refs);
+      break;
+    case LF_INDEX:
+      ThisLen = handleListContinuation(Content, Offset, Refs);
+      break;
+    default:
+      return;
+    }
+    Content = Content.drop_front(ThisLen);
+    Offset += ThisLen;
+    if (!Content.empty()) {
+      uint8_t Pad = Content.front();
+      if (Pad >= LF_PAD0) {
+        uint32_t Skip = Pad & 0x0F;
+        Content = Content.drop_front(Skip);
+        Offset += Skip;
+      }
+    }
+  }
+}
+
+static void handlePointer(ArrayRef<uint8_t> Content,
+                          SmallVectorImpl<TiReference> &Refs) {
+  Refs.push_back({TiRefKind::TypeRef, 0, 1});
+
+  uint32_t Attrs = support::endian::read32le(Content.drop_front(4).data());
+  if (isMemberPointer(Attrs))
+    Refs.push_back({TiRefKind::TypeRef, 8, 1});
+}
+
+static void discoverTypeIndices(ArrayRef<uint8_t> Content, TypeLeafKind Kind,
+                                SmallVectorImpl<TiReference> &Refs) {
+  uint32_t Count;
+  // FIXME: In the future it would be nice if we could avoid hardcoding these
+  // values.  One idea is to define some structures representing these types
+  // that would allow the use of offsetof().
+  switch (Kind) {
+  case TypeLeafKind::LF_FUNC_ID:
+    Refs.push_back({TiRefKind::IndexRef, 0, 1});
+    Refs.push_back({TiRefKind::TypeRef, 4, 1});
+    break;
+  case TypeLeafKind::LF_MFUNC_ID:
+    Refs.push_back({TiRefKind::TypeRef, 0, 2});
+    break;
+  case TypeLeafKind::LF_STRING_ID:
+    Refs.push_back({TiRefKind::IndexRef, 0, 1});
+    break;
+  case TypeLeafKind::LF_SUBSTR_LIST:
+    Count = support::endian::read32le(Content.data());
+    if (Count > 0)
+      Refs.push_back({TiRefKind::IndexRef, 4, Count});
+    break;
+  case TypeLeafKind::LF_BUILDINFO:
+    Count = support::endian::read16le(Content.data());
+    if (Count > 0)
+      Refs.push_back({TiRefKind::IndexRef, 2, Count});
+    break;
+  case TypeLeafKind::LF_UDT_SRC_LINE:
+    Refs.push_back({TiRefKind::TypeRef, 0, 1});
+    Refs.push_back({TiRefKind::IndexRef, 4, 1});
+    break;
+  case TypeLeafKind::LF_UDT_MOD_SRC_LINE:
+    Refs.push_back({TiRefKind::TypeRef, 0, 1});
+    break;
+  case TypeLeafKind::LF_MODIFIER:
+    Refs.push_back({TiRefKind::TypeRef, 0, 1});
+    break;
+  case TypeLeafKind::LF_PROCEDURE:
+    Refs.push_back({TiRefKind::TypeRef, 0, 1});
+    Refs.push_back({TiRefKind::TypeRef, 8, 1});
+    break;
+  case TypeLeafKind::LF_MFUNCTION:
+    Refs.push_back({TiRefKind::TypeRef, 0, 3});
+    Refs.push_back({TiRefKind::TypeRef, 16, 1});
+    break;
+  case TypeLeafKind::LF_ARGLIST:
+    Count = support::endian::read32le(Content.data());
+    if (Count > 0)
+      Refs.push_back({TiRefKind::TypeRef, 4, Count});
+    break;
+  case TypeLeafKind::LF_ARRAY:
+    Refs.push_back({TiRefKind::TypeRef, 0, 2});
+    break;
+  case TypeLeafKind::LF_CLASS:
+  case TypeLeafKind::LF_STRUCTURE:
+  case TypeLeafKind::LF_INTERFACE:
+    Refs.push_back({TiRefKind::TypeRef, 4, 3});
+    break;
+  case TypeLeafKind::LF_UNION:
+    Refs.push_back({TiRefKind::TypeRef, 4, 1});
+    break;
+  case TypeLeafKind::LF_ENUM:
+    Refs.push_back({TiRefKind::TypeRef, 4, 2});
+    break;
+  case TypeLeafKind::LF_BITFIELD:
+    Refs.push_back({TiRefKind::TypeRef, 0, 1});
+    break;
+  case TypeLeafKind::LF_VFTABLE:
+    Refs.push_back({TiRefKind::TypeRef, 0, 2});
+    break;
+  case TypeLeafKind::LF_VTSHAPE:
+    break;
+  case TypeLeafKind::LF_METHODLIST:
+    handleMethodOverloadList(Content, Refs);
+    break;
+  case TypeLeafKind::LF_FIELDLIST:
+    handleFieldList(Content, Refs);
+    break;
+  case TypeLeafKind::LF_POINTER:
+    handlePointer(Content, Refs);
+    break;
+  default:
+    break;
+  }
+}
+
+void llvm::codeview::discoverTypeIndices(const CVType &Type,
+                                         SmallVectorImpl<TiReference> &Refs) {
+  ::discoverTypeIndices(Type.content(), Type.kind(), Refs);
+}
+
+void llvm::codeview::discoverTypeIndices(ArrayRef<uint8_t> RecordData,
+                                         SmallVectorImpl<TiReference> &Refs) {
+  const RecordPrefix *P =
+      reinterpret_cast<const RecordPrefix *>(RecordData.data());
+  TypeLeafKind K = static_cast<TypeLeafKind>(uint16_t(P->RecordKind));
+  ::discoverTypeIndices(RecordData.drop_front(sizeof(RecordPrefix)), K, Refs);
+}

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

 //===-- 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/TypeDeserializer.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
+#include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ScopedPrinter.h"
 
 using namespace llvm;
 using namespace llvm::codeview;
public:
   explicit TypeStreamMerger(SmallVectorImpl<TypeIndex> &SourceToDest,
                             TypeServerHandler *Handler)
       : 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 mergeTypesAndIds(TypeTableBuilder &DestIds, TypeTableBuilder &DestTypes,
     const CVTypeArray &IdsAndTypes);
   Error mergeIdRecords(TypeTableBuilder &Dest,
                        ArrayRef<TypeIndex> TypeSourceToDest,
     const CVTypeArray &Ids);
   Error mergeTypeRecords(TypeTableBuilder &Dest, const CVTypeArray &Types);
 
 private:
   Error doit(const CVTypeArray &Types);
 
   void addMapping(TypeIndex Idx);
 
   bool remapTypeIndex(TypeIndex &Idx);
   bool remapItemIndex(TypeIndex &Idx);
 
-  bool remapIndices(RemappedType &Record, ArrayRef<uint32_t> TidOffs,
-                    ArrayRef<uint32_t> IidOffs) {
+  bool remapIndices(RemappedType &Record, ArrayRef<TiReference> Refs) {
     auto OriginalData = Record.OriginalRecord.content();
     bool Success = true;
-    for (auto Off : TidOffs) {
-      ArrayRef<uint8_t> Bytes = OriginalData.slice(Off, sizeof(TypeIndex));
-      TypeIndex OldTI(
-          *reinterpret_cast<const support::ulittle32_t *>(Bytes.data()));
-      TypeIndex NewTI = OldTI;
-      bool ThisSuccess = remapTypeIndex(NewTI);
-      if (ThisSuccess && NewTI != OldTI)
-        Record.Mappings.emplace_back(Off, NewTI);
+    for (auto &Ref : Refs) {
+      uint32_t Offset = Ref.Offset;
+      ArrayRef<uint8_t> Bytes =
+          OriginalData.slice(Ref.Offset, sizeof(TypeIndex));
+      ArrayRef<TypeIndex> TIs(reinterpret_cast<const TypeIndex *>(Bytes.data()),
+                              Ref.Count);
+      for (auto TI : TIs) {
+        TypeIndex NewTI = TI;
+        bool ThisSuccess = (Ref.Kind == TiRefKind::IndexRef)
+                               ? remapItemIndex(NewTI)
+                               : remapTypeIndex(NewTI);
+        if (ThisSuccess && NewTI != TI)
+          Record.Mappings.emplace_back(Offset, NewTI);
+        Offset += sizeof(TypeIndex);
         Success &= ThisSuccess;
       }
-    for (auto Off : IidOffs) {
-      ArrayRef<uint8_t> Bytes = OriginalData.slice(Off, sizeof(TypeIndex));
-      TypeIndex OldTI(
-          *reinterpret_cast<const support::ulittle32_t *>(Bytes.data()));
-      TypeIndex NewTI = OldTI;
-      bool ThisSuccess = remapItemIndex(NewTI);
-      if (ThisSuccess && NewTI != OldTI)
-        Record.Mappings.emplace_back(Off, NewTI);
-      Success &= ThisSuccess;
     }
     return Success;
   }
 
   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 writeKnownRecord(TypeTableBuilder &Dest, RecordType &R,
-                         bool RemapSuccess) {
-    TypeIndex DestIdx = Untranslated;
-    if (RemapSuccess)
-      DestIdx = Dest.writeKnownType(R);
-    addMapping(DestIdx);
-    return Error::success();
-  }
-
-  template <typename RecordType>
-  Error writeKnownTypeRecord(RecordType &R, bool RemapSuccess) {
-    return writeKnownRecord(*DestTypeStream, R, RemapSuccess);
-  }
-
-  template <typename RecordType>
-  Error writeKnownIdRecord(RecordType &R, bool RemapSuccess) {
-    return writeKnownRecord(*DestIdStream, R, RemapSuccess);
-  }
-
   Error writeRecord(TypeTableBuilder &Dest, const RemappedType &Record,
                     bool RemapSuccess) {
     TypeIndex DestIdx = Untranslated;
     if (RemapSuccess)
       DestIdx = Dest.writeSerializedRecord(Record);
     addMapping(DestIdx);
     return Error::success();
   }
 
   Error writeTypeRecord(const CVType &Record) {
     TypeIndex DestIdx =
         DestTypeStream->writeSerializedRecord(Record.RecordData);
     addMapping(DestIdx);
     return Error::success();
   }
 
   Error writeTypeRecord(const RemappedType &Record, bool RemapSuccess) {
     return writeRecord(*DestTypeStream, Record, RemapSuccess);
   }
 
   Error writeIdRecord(const RemappedType &Record, bool RemapSuccess) {
     return writeRecord(*DestIdStream, Record, RemapSuccess);
   }
 
-  template <typename RecordType>
-  Error writeMember(RecordType &R, bool RemapSuccess) {
-    if (RemapSuccess)
-      FieldListBuilder->writeMemberType(R);
-    else
-      HadUntranslatedMember = true;
-    return Error::success();
-  }
-
   Optional<Error> LastError;
 
   bool IsSecondPass = false;
 
   bool HadUntranslatedMember = false;
 
   unsigned NumBadIndices = 0;
 
-  BumpPtrAllocator Allocator;
-
   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);
 
-Error TypeStreamMerger::visitTypeBegin(CVType &Rec) { return Error::success(); }
+Error TypeStreamMerger::visitTypeBegin(CVType &Rec) {
+  RemappedType R(Rec);
+  SmallVector<TiReference, 32> Refs;
+  discoverTypeIndices(Rec.RecordData, Refs);
+  bool Success = remapIndices(R, Refs);
+  switch (Rec.kind()) {
+  case TypeLeafKind::LF_FUNC_ID:
+  case TypeLeafKind::LF_MFUNC_ID:
+  case TypeLeafKind::LF_STRING_ID:
+  case TypeLeafKind::LF_SUBSTR_LIST:
+  case TypeLeafKind::LF_BUILDINFO:
+  case TypeLeafKind::LF_UDT_SRC_LINE:
+  case TypeLeafKind::LF_UDT_MOD_SRC_LINE:
+    return writeIdRecord(R, Success);
+  default:
+    return writeTypeRecord(R, Success);
+  }
+  return Error::success();
+}
 
 Error TypeStreamMerger::visitTypeEnd(CVType &Rec) {
   ++CurIndex;
   if (!IsSecondPass)
     assert(IndexMap.size() == slotForIndex(CurIndex) &&
            "visitKnownRecord should add one index map entry");
   return Error::success();
 }
 
-Error TypeStreamMerger::visitMemberEnd(CVMemberRecord &Rec) {
-  return Error::success();
-}
-
 void TypeStreamMerger::addMapping(TypeIndex Idx) {
   if (!IsSecondPass) {
     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::remapTypeIndex(TypeIndex &Idx) {
   return remapIndex(Idx, IndexMap);
 }
 
 bool TypeStreamMerger::remapItemIndex(TypeIndex &Idx) {
   assert(DestIdStream);
   return remapIndex(Idx, IndexMap);
 }
 
-//----------------------------------------------------------------------------//
-// Item records
-//----------------------------------------------------------------------------//
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, FuncIdRecord &R) {
-  assert(DestIdStream);
-
-  RemappedType RR(CVR);
-  return writeIdRecord(RR, remapIndices(RR, {4}, {0}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, MemberFuncIdRecord &R) {
-  assert(DestIdStream);
-
-  RemappedType RR(CVR);
-  return writeIdRecord(RR, remapIndices(RR, {0, 4}, {}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, StringIdRecord &R) {
-  assert(DestIdStream);
-
-  RemappedType RR(CVR);
-  return writeIdRecord(RR, remapIndices(RR, {}, {0}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, StringListRecord &R) {
-  assert(DestIdStream);
-
-  if (auto EC = TypeDeserializer::deserializeAs<StringListRecord>(CVR, R))
-    return EC;
-  bool Success = true;
-
-  for (TypeIndex &Id : R.StringIndices)
-    Success &= remapItemIndex(Id);
-  return writeKnownIdRecord(R, Success);
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, BuildInfoRecord &R) {
-  assert(DestIdStream);
-
-  if (auto EC = TypeDeserializer::deserializeAs(CVR, R))
-    return EC;
-
-  bool Success = true;
-  for (TypeIndex &Str : R.ArgIndices)
-    Success &= remapItemIndex(Str);
-  return writeKnownIdRecord(R, Success);
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, UdtSourceLineRecord &R) {
-  assert(DestIdStream);
-
-  RemappedType RR(CVR);
-
-  // FIXME: Translate UdtSourceLineRecord into UdtModSourceLineRecords in the
-  // IPI stream.
-  return writeIdRecord(RR, remapIndices(RR, {0}, {4}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR,
-                                         UdtModSourceLineRecord &R) {
-  assert(DestIdStream);
-
-  RemappedType RR(CVR);
-
-  // UdtModSourceLine Source File Ids are offsets into the global string table,
-  // not type indices.
-  // FIXME: We need to merge string table records for this to be valid.
-  return writeIdRecord(RR, remapIndices(RR, {0}, {}));
-}
-
-//----------------------------------------------------------------------------//
-// Type records
-//----------------------------------------------------------------------------//
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, ModifierRecord &R) {
-  assert(DestTypeStream);
-
-  RemappedType RR(CVR);
-  return writeTypeRecord(RR, remapIndices(RR, {0}, {}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, ProcedureRecord &R) {
-  assert(DestTypeStream);
-
-  RemappedType RR(CVR);
-  return writeTypeRecord(RR, remapIndices(RR, {0, 8}, {}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, MemberFunctionRecord &R) {
-  assert(DestTypeStream);
-
-  RemappedType RR(CVR);
-  return writeTypeRecord(RR, remapIndices(RR, {0, 4, 8, 16}, {}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, ArgListRecord &R) {
-  assert(DestTypeStream);
-
-  if (auto EC = TypeDeserializer::deserializeAs(CVR, R))
-    return EC;
-
-  bool Success = true;
-  for (TypeIndex &Arg : R.ArgIndices)
-    Success &= remapTypeIndex(Arg);
-
-  return writeKnownTypeRecord(R, Success);
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, PointerRecord &R) {
-  assert(DestTypeStream);
-
-  // Pointer records have a different number of TypeIndex mappings depending
-  // on whether or not it is a pointer to member.
-  if (auto EC = TypeDeserializer::deserializeAs(CVR, R))
-    return EC;
-
-  bool Success = remapTypeIndex(R.ReferentType);
-  if (R.isPointerToMember())
-    Success &= remapTypeIndex(R.MemberInfo->ContainingType);
-  return writeKnownTypeRecord(R, Success);
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, ArrayRecord &R) {
-  assert(DestTypeStream);
-
-  RemappedType RR(CVR);
-  return writeTypeRecord(RR, remapIndices(RR, {0, 4}, {}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, ClassRecord &R) {
-  assert(DestTypeStream);
-
-  RemappedType RR(CVR);
-  return writeTypeRecord(RR, remapIndices(RR, {4, 8, 12}, {}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, UnionRecord &R) {
-  assert(DestTypeStream);
-
-  RemappedType RR(CVR);
-  return writeTypeRecord(RR, remapIndices(RR, {4}, {}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, EnumRecord &R) {
-  assert(DestTypeStream);
-
-  RemappedType RR(CVR);
-  return writeTypeRecord(RR, remapIndices(RR, {4, 8}, {}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, BitFieldRecord &R) {
-  assert(DestTypeStream);
-
-  RemappedType RR(CVR);
-  return writeTypeRecord(RR, remapIndices(RR, {0}, {}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, VFTableShapeRecord &R) {
-  assert(DestTypeStream);
-
-  return writeTypeRecord(CVR);
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, TypeServer2Record &R) {
-  assert(DestTypeStream);
-
-  return writeTypeRecord(CVR);
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, LabelRecord &R) {
-  assert(DestTypeStream);
-
-  return writeTypeRecord(CVR);
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, VFTableRecord &R) {
-  assert(DestTypeStream);
-
-  RemappedType RR(CVR);
-  return writeTypeRecord(RR, remapIndices(RR, {0, 4}, {}));
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR,
-                                         MethodOverloadListRecord &R) {
-  assert(DestTypeStream);
-
-  if (auto EC = TypeDeserializer::deserializeAs(CVR, R))
-    return EC;
-
-  bool Success = true;
-  for (OneMethodRecord &Meth : R.Methods)
-    Success &= remapTypeIndex(Meth.Type);
-  return writeKnownTypeRecord(R, Success);
-}
-
-Error TypeStreamMerger::visitKnownRecord(CVType &CVR, FieldListRecord &R) {
-  assert(DestTypeStream);
-  // Visit the members inside the field list.
-  HadUntranslatedMember = false;
-  if (!FieldListBuilder)
-    FieldListBuilder =
-        llvm::make_unique<FieldListRecordBuilder>(*DestTypeStream);
-
-  FieldListBuilder->begin();
-  if (auto EC = codeview::visitMemberRecordStream(CVR.content(), *this))
-    return EC;
-
-  // Write the record if we translated all field list members.
-  TypeIndex DestIdx = FieldListBuilder->end(!HadUntranslatedMember);
-  addMapping(HadUntranslatedMember ? Untranslated : DestIdx);
-
-  return Error::success();
-}
-
-//----------------------------------------------------------------------------//
-// Member records
-//----------------------------------------------------------------------------//
-
-Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
-                                         NestedTypeRecord &R) {
-  return writeMember(R, remapTypeIndex(R.Type));
-}
-
-Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, OneMethodRecord &R) {
-  bool Success = true;
-  Success &= remapTypeIndex(R.Type);
-  return writeMember(R, Success);
-}
-
-Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
-                                         OverloadedMethodRecord &R) {
-  return writeMember(R, remapTypeIndex(R.MethodList));
-}
-
-Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
-                                         DataMemberRecord &R) {
-  return writeMember(R, remapTypeIndex(R.Type));
-}
-
-Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
-                                         StaticDataMemberRecord &R) {
-  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, remapTypeIndex(R.Type));
-}
-
-Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, BaseClassRecord &R) {
-  return writeMember(R, remapTypeIndex(R.Type));
-}
-
-Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
-                                         VirtualBaseClassRecord &R) {
-  bool Success = true;
-  Success &= remapTypeIndex(R.BaseType);
-  Success &= remapTypeIndex(R.VBPtrType);
-  return writeMember(R, Success);
-}
-
-Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
-                                         ListContinuationRecord &R) {
-  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::mergeTypeRecords(TypeTableBuilder &Dest,
   const CVTypeArray &Types) {
   DestTypeStream = &Dest;
 
   return doit(Types);
 }
 
 Error TypeStreamMerger::mergeIdRecords(TypeTableBuilder &Dest,

 }
 
 Error TypeStreamMerger::doit(const CVTypeArray &Types) {
   LastError = Error::success();
 
   // We don't want to deserialize records.  I guess this flag is poorly named,
   // but it really means "Don't deserialize records before switching on the
   // concrete type.
+  // FIXME: We can probably get even more speed here if we don't use the visitor
+  // pipeline here, but instead write the switch ourselves.  I don't think it
+  // would buy us much since it's already pretty fast, but it's probably worth
+  // a few cycles.
   if (auto EC =
           codeview::visitTypeStream(Types, *this, VDS_BytesExternal, 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
   // is the only known CodeView producer that makes type streams that aren't

llvm/trunk/unittests/DebugInfo/CodeView/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   DebugInfoCodeView
   )
 
 set(DebugInfoCodeViewSources
   RandomAccessVisitorTest.cpp
+  TypeIndexDiscoveryTest.cpp
   )
 
 add_llvm_unittest(DebugInfoCodeViewTests
   ${DebugInfoCodeViewSources}
   )

llvm/trunk/unittests/DebugInfo/CodeView/ErrorChecking.h

 #define EXPECT_ERROR(Err)                                                      \
   {                                                                            \
     auto E = Err;                                                              \
     EXPECT_TRUE(static_cast<bool>(E));                                         \
     if (E)                                                                     \
       consumeError(std::move(E));                                              \
   }
 
+#define ASSERT_EXPECTED(Exp)                                                   \
+  {                                                                            \
+    auto E = Exp.takeError();                                                  \
+    bool Success = static_cast<bool>(E);                                       \
+    if (!Success)                                                              \
+      consumeError(std::move(E));                                              \
+    ASSERT_FALSE(Success);                                                     \
+  }
+
 #define EXPECT_EXPECTED(Exp)                                                   \
   {                                                                            \
     auto E = Exp.takeError();                                                  \
     EXPECT_FALSE(static_cast<bool>(E));                                        \
     if (E) {                                                                   \
       consumeError(std::move(E));                                              \
       return;                                                                  \
     }                                                                          \

llvm/trunk/unittests/DebugInfo/CodeView/TypeIndexDiscoveryTest.cpp

+//===- llvm/unittest/DebugInfo/CodeView/TypeIndexDiscoveryTest.cpp --------===//
+//
+//                     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/TypeIndexDiscovery.h"
+
+#include "ErrorChecking.h"
+#include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
+#include "llvm/Support/Allocator.h"
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using namespace llvm::codeview;
+
+class TypeIndexIteratorTest : public testing::Test {
+public:
+  TypeIndexIteratorTest() {}
+
+  void SetUp() override {
+    Refs.clear();
+    TTB = make_unique<TypeTableBuilder>(Storage);
+    FLRB = make_unique<FieldListRecordBuilder>(*TTB);
+  }
+
+  void TearDown() override {
+    FLRB.reset();
+    TTB.reset();
+  }
+
+protected:
+  template <typename... Indices>
+  bool checkTypeReferences(uint32_t RecordIndex, Indices &&... TIs) const {
+    EXPECT_EQ(sizeof...(Indices), countRefs(RecordIndex));
+    return checkTypeReferencesImpl(RecordIndex, std::forward<Indices>(TIs)...);
+  }
+
+  template <typename... T> void writeFieldList(T &&... MemberRecords) {
+    FLRB->begin();
+    writeFieldListImpl(std::forward<T>(MemberRecords)...);
+    FLRB->end(true);
+    ASSERT_EQ(1u, TTB->records().size());
+    discoverAllTypeIndices();
+  }
+
+  template <typename... T> void writeTypeRecords(T &&... Records) {
+    writeTypeRecordsImpl(std::forward<T>(Records)...);
+    ASSERT_EQ(sizeof...(T), TTB->records().size());
+    discoverAllTypeIndices();
+  }
+
+  std::unique_ptr<TypeTableBuilder> TTB;
+
+private:
+  uint32_t countRefs(uint32_t RecordIndex) const {
+    auto &R = Refs[RecordIndex];
+    uint32_t Count = 0;
+    for (auto &Ref : R) {
+      Count += Ref.Count;
+    }
+    return Count;
+  }
+
+  bool checkOneTypeReference(uint32_t RecordIndex, ArrayRef<uint8_t> RecordData,
+                             TypeIndex TI) const {
+    RecordData = RecordData.drop_front(sizeof(RecordPrefix));
+    auto &RefList = Refs[RecordIndex];
+    for (auto &Ref : RefList) {
+      uint32_t Offset = Ref.Offset;
+      ArrayRef<uint8_t> Loc = RecordData.drop_front(Offset);
+      ArrayRef<TypeIndex> Indices(
+          reinterpret_cast<const TypeIndex *>(Loc.data()), Ref.Count);
+      if (llvm::any_of(Indices,
+                       [TI](const TypeIndex &Other) { return Other == TI; }))
+        return true;
+    }
+    return false;
+  }
+
+  template <typename... Indices>
+  bool checkTypeReferencesImpl(uint32_t RecordIndex) const {
+    return true;
+  }
+
+  template <typename... Indices>
+  bool checkTypeReferencesImpl(uint32_t RecordIndex, TypeIndex TI,
+                               Indices &&... Rest) const {
+    ArrayRef<uint8_t> Record = TTB->records()[RecordIndex];
+    bool Success = checkOneTypeReference(RecordIndex, Record, TI);
+    EXPECT_TRUE(Success);
+    return Success &
+           checkTypeReferencesImpl(RecordIndex, std::forward<Indices>(Rest)...);
+  }
+
+  void discoverAllTypeIndices() {
+    Refs.resize(TTB->records().size());
+    for (uint32_t I = 0; I < TTB->records().size(); ++I) {
+      ArrayRef<uint8_t> Data = TTB->records()[I];
+      discoverTypeIndices(Data, Refs[I]);
+    }
+  }
+
+  // Helper function to write out a field list record with the given list
+  // of member records.
+  void writeFieldListImpl() {}
+
+  template <typename RecType, typename... Rest>
+  void writeFieldListImpl(RecType &&Record, Rest &&... Records) {
+    FLRB->writeMemberType(Record);
+    writeFieldListImpl(std::forward<Rest>(Records)...);
+  }
+
+  // Helper function to write out a list of type records.
+  void writeTypeRecordsImpl() {}
+
+  template <typename RecType, typename... Rest>
+  void writeTypeRecordsImpl(RecType &&Record, Rest &&... Records) {
+    TTB->writeKnownType(Record);
+    writeTypeRecordsImpl(std::forward<Rest>(Records)...);
+  }
+
+  std::vector<SmallVector<TiReference, 4>> Refs;
+  std::unique_ptr<FieldListRecordBuilder> FLRB;
+  BumpPtrAllocator Storage;
+};
+
+namespace leafs {
+static FuncIdRecord FuncId(TypeIndex(1), TypeIndex(2), "FuncId");
+static MemberFuncIdRecord MemFuncId(TypeIndex(3), TypeIndex(4), "FuncId");
+static StringIdRecord StringId(TypeIndex(5), "TheString");
+static struct {
+  std::vector<TypeIndex> Ids = {TypeIndex(6), TypeIndex(7), TypeIndex(8)};
+  StringListRecord Record{TypeRecordKind::StringList, Ids};
+} StringList;
+static struct {
+  std::vector<TypeIndex> Ids = {TypeIndex(9), TypeIndex(10), TypeIndex(11)};
+  BuildInfoRecord Record{Ids};
+} BuildInfo;
+static UdtSourceLineRecord UdtSourceLine(TypeIndex(12), TypeIndex(13), 0);
+static UdtModSourceLineRecord UdtModSourceLine(TypeIndex(14), TypeIndex(15), 0,
+                                               0);
+static ModifierRecord Modifier(TypeIndex(16), ModifierOptions::None);
+static ProcedureRecord Procedure(TypeIndex(17), CallingConvention::PpcCall,
+                                 FunctionOptions::None, 0, TypeIndex(18));
+static MemberFunctionRecord MemberFunction(TypeIndex(19), TypeIndex(20),
+                                           TypeIndex(21),
+                                           CallingConvention::ThisCall,
+                                           FunctionOptions::None, 2,
+                                           TypeIndex(22), 0);
+static struct {
+  std::vector<TypeIndex> Ids = {TypeIndex(23), TypeIndex(24), TypeIndex(25)};
+  ArgListRecord Record{TypeRecordKind::ArgList, Ids};
+} ArgList;
+static ArrayRecord Array(TypeIndex(26), TypeIndex(27), 10, "MyArray");
+static ClassRecord Class(TypeRecordKind::Class, 3, ClassOptions::None,
+                         TypeIndex(28), TypeIndex(29), TypeIndex(30), 10,
+                         "MyClass", "MyClassUniqueName");
+static ClassRecord Struct(TypeRecordKind::Struct, 3, ClassOptions::None,
+                          TypeIndex(31), TypeIndex(32), TypeIndex(33), 10,
+                          "MyClass", "MyClassUniqueName");
+static UnionRecord Union(1, ClassOptions::None, TypeIndex(34), 10, "MyUnion",
+                         "MyUnionUniqueName");
+static EnumRecord Enum(1, ClassOptions::None, TypeIndex(35), "MyEnum",
+                       "EnumUniqueName", TypeIndex(36));
+static BitFieldRecord BitField(TypeIndex(37), 1, 0);
+static VFTableRecord VFTable(TypeIndex(38), TypeIndex(39), 1, "VFT", {});
+static VFTableShapeRecord VTableShape({});
+static struct {
+  const TypeIndex T1{40};
+  const TypeIndex T2{41};
+  const TypeIndex T3{42};
+  const TypeIndex T4{43};
+
+  std::vector<OneMethodRecord> Methods{
+      {T1, MemberAccess::Public, MethodKind::IntroducingVirtual,
+       MethodOptions::None, 0, "Method1"},
+      {T2, MemberAccess::Public, MethodKind::PureVirtual, MethodOptions::None,
+       0, "Method1"},
+      {T3, MemberAccess::Public, MethodKind::PureIntroducingVirtual,
+       MethodOptions::None, 0, "Method1"},
+      {T4, MemberAccess::Public, MethodKind::Static, MethodOptions::None, 0,
+       "Method1"}};
+
+  MethodOverloadListRecord Record{Methods};
+} MethodOverloadList;
+static PointerRecord Pointer(TypeIndex(44), PointerKind::Near32,
+                             PointerMode::Pointer, PointerOptions::Const, 3);
+static PointerRecord MemberPointer(
+    TypeIndex(45), PointerKind::Near32, PointerMode::PointerToDataMember,
+    PointerOptions::Const, 3,
+    MemberPointerInfo(TypeIndex(46),
+                      PointerToMemberRepresentation::GeneralData));
+}
+
+namespace members {
+static BaseClassRecord BaseClass(MemberAccess::Public, TypeIndex(47), 0);
+static EnumeratorRecord Enumerator(MemberAccess::Public,
+                                   APSInt(APInt(8, 3, false)), "Test");
+DataMemberRecord DataMember(MemberAccess::Public, TypeIndex(48), 0, "Test");
+OverloadedMethodRecord OverloadedMethod(3, TypeIndex(49), "MethodList");
+static struct {
+  const TypeIndex T1{50};
+  const TypeIndex T2{51};
+  const TypeIndex T3{52};
+  const TypeIndex T4{53};
+  OneMethodRecord R1{T1,
+                     MemberAccess::Public,
+                     MethodKind::IntroducingVirtual,
+                     MethodOptions::None,
+                     0,
+                     "M1"};
+  OneMethodRecord R2{T2,
+                     MemberAccess::Public,
+                     MethodKind::PureVirtual,
+                     MethodOptions::None,
+                     0,
+                     "M2"};
+  OneMethodRecord R3{T3,
+                     MemberAccess::Public,
+                     MethodKind::PureIntroducingVirtual,
+                     MethodOptions::None,
+                     0,
+                     "M3"};
+  OneMethodRecord R4{T4,
+                     MemberAccess::Protected,
+                     MethodKind::Vanilla,
+                     MethodOptions::CompilerGenerated,
+                     0,
+                     "M4"};
+} OneMethod;
+static NestedTypeRecord NestedType(TypeIndex(54), "MyClass");
+static StaticDataMemberRecord StaticDataMember(MemberAccess::Public,
+                                               TypeIndex(55), "Foo");
+static VirtualBaseClassRecord VirtualBaseClass(TypeRecordKind::VirtualBaseClass,
+                                               MemberAccess::Public,
+                                               TypeIndex(56), TypeIndex(57), 0,
+                                               0);
+static VFPtrRecord VFPtr(TypeIndex(58));
+static ListContinuationRecord Continuation(TypeIndex(59));
+}
+
+TEST_F(TypeIndexIteratorTest, FuncId) {
+  using namespace leafs;
+  writeTypeRecords(FuncId);
+  checkTypeReferences(0, FuncId.FunctionType, FuncId.ParentScope);
+}
+
+TEST_F(TypeIndexIteratorTest, MemFuncId) {
+  using namespace leafs;
+  writeTypeRecords(MemFuncId);
+  checkTypeReferences(0, MemFuncId.ClassType, MemFuncId.FunctionType);
+}
+
+TEST_F(TypeIndexIteratorTest, StringId) {
+  using namespace leafs;
+  writeTypeRecords(StringId);
+  checkTypeReferences(0, StringId.Id);
+}
+
+TEST_F(TypeIndexIteratorTest, SubstrList) {
+  using namespace leafs;
+  writeTypeRecords(StringList.Record);
+  checkTypeReferences(0, StringList.Ids[0], StringList.Ids[1],
+                      StringList.Ids[2]);
+}
+
+TEST_F(TypeIndexIteratorTest, BuildInfo) {
+  using namespace leafs;
+  writeTypeRecords(BuildInfo.Record);
+  checkTypeReferences(0, BuildInfo.Ids[0], BuildInfo.Ids[1], BuildInfo.Ids[2]);
+}
+
+TEST_F(TypeIndexIteratorTest, UdtSrcLine) {
+  using namespace leafs;
+  writeTypeRecords(UdtSourceLine);
+  checkTypeReferences(0, UdtSourceLine.UDT, UdtSourceLine.SourceFile);
+}
+
+TEST_F(TypeIndexIteratorTest, UdtModSrcLine) {
+  using namespace leafs;
+  writeTypeRecords(UdtModSourceLine);
+  checkTypeReferences(0, UdtModSourceLine.UDT, UdtModSourceLine.SourceFile);
+}
+
+TEST_F(TypeIndexIteratorTest, Modifier) {
+  using namespace leafs;
+  writeTypeRecords(Modifier);
+  checkTypeReferences(0, Modifier.ModifiedType);
+}
+
+TEST_F(TypeIndexIteratorTest, Procedure) {
+  using namespace leafs;
+  writeTypeRecords(Procedure);
+  checkTypeReferences(0, Procedure.ReturnType, Procedure.ArgumentList);
+}
+
+TEST_F(TypeIndexIteratorTest, MemFunc) {
+  using namespace leafs;
+  writeTypeRecords(MemberFunction);
+  checkTypeReferences(0, MemberFunction.ReturnType, MemberFunction.ClassType,
+                      MemberFunction.ThisType, MemberFunction.ArgumentList);
+}
+
+TEST_F(TypeIndexIteratorTest, ArgList) {
+  using namespace leafs;
+  writeTypeRecords(ArgList.Record);
+  checkTypeReferences(0, ArgList.Ids[0], ArgList.Ids[1], ArgList.Ids[2]);
+}
+
+TEST_F(TypeIndexIteratorTest, Array) {
+  using namespace leafs;
+  writeTypeRecords(Array);
+  checkTypeReferences(0, Array.ElementType, Array.IndexType);
+}
+
+TEST_F(TypeIndexIteratorTest, Class) {
+  using namespace leafs;
+  writeTypeRecords(Class);
+  checkTypeReferences(0, Class.FieldList, Class.DerivationList,
+                      Class.VTableShape);
+}
+
+TEST_F(TypeIndexIteratorTest, Struct) {
+  using namespace leafs;
+  writeTypeRecords(Struct);
+  checkTypeReferences(0, Struct.FieldList, Struct.DerivationList,
+                      Struct.VTableShape);
+}
+
+TEST_F(TypeIndexIteratorTest, Union) {
+  using namespace leafs;
+  writeTypeRecords(Union);
+  checkTypeReferences(0, Union.FieldList);
+}
+
+TEST_F(TypeIndexIteratorTest, Enum) {
+  using namespace leafs;
+  writeTypeRecords(Enum);
+  checkTypeReferences(0, Enum.FieldList, Enum.UnderlyingType);
+}
+
+TEST_F(TypeIndexIteratorTest, Bitfield) {
+  using namespace leafs;
+  writeTypeRecords(BitField);
+  checkTypeReferences(0, BitField.Type);
+}
+
+TEST_F(TypeIndexIteratorTest, VTable) {
+  using namespace leafs;
+  writeTypeRecords(VFTable);
+  checkTypeReferences(0, VFTable.CompleteClass, VFTable.OverriddenVFTable);
+}
+
+TEST_F(TypeIndexIteratorTest, VTShape) {
+  using namespace leafs;
+  writeTypeRecords(VTableShape);
+  checkTypeReferences(0);
+}
+
+TEST_F(TypeIndexIteratorTest, OverloadList) {
+  using namespace leafs;
+  writeTypeRecords(MethodOverloadList.Record);
+  checkTypeReferences(0, MethodOverloadList.T1, MethodOverloadList.T2,
+                      MethodOverloadList.T3, MethodOverloadList.T4);
+}
+
+TEST_F(TypeIndexIteratorTest, Pointer) {
+  using namespace leafs;
+  writeTypeRecords(Pointer);
+  checkTypeReferences(0, Pointer.ReferentType);
+}
+
+TEST_F(TypeIndexIteratorTest, MemberPointer) {
+  using namespace leafs;
+  writeTypeRecords(MemberPointer);
+  checkTypeReferences(0, MemberPointer.ReferentType,
+                      MemberPointer.MemberInfo->ContainingType);
+}
+
+TEST_F(TypeIndexIteratorTest, ManyTypes) {
+
+  using namespace leafs;
+  writeTypeRecords(FuncId, MemFuncId, StringId, StringList.Record,
+                   BuildInfo.Record, UdtSourceLine, UdtModSourceLine, Modifier,
+                   Procedure, MemberFunction, ArgList.Record, Array, Class,
+                   Union, Enum, BitField, VFTable, VTableShape,
+                   MethodOverloadList.Record, Pointer, MemberPointer);
+
+  checkTypeReferences(0, FuncId.FunctionType, FuncId.ParentScope);
+  checkTypeReferences(1, MemFuncId.ClassType, MemFuncId.FunctionType);
+  checkTypeReferences(2, StringId.Id);
+  checkTypeReferences(3, StringList.Ids[0], StringList.Ids[1],
+                      StringList.Ids[2]);
+  checkTypeReferences(4, BuildInfo.Ids[0], BuildInfo.Ids[1], BuildInfo.Ids[2]);
+  checkTypeReferences(5, UdtSourceLine.UDT, UdtSourceLine.SourceFile);
+  checkTypeReferences(6, UdtModSourceLine.UDT, UdtModSourceLine.SourceFile);
+  checkTypeReferences(7, Modifier.ModifiedType);
+  checkTypeReferences(8, Procedure.ReturnType, Procedure.ArgumentList);
+  checkTypeReferences(9, MemberFunction.ReturnType, MemberFunction.ClassType,
+                      MemberFunction.ThisType, MemberFunction.ArgumentList);
+  checkTypeReferences(10, ArgList.Ids[0], ArgList.Ids[1], ArgList.Ids[2]);
+  checkTypeReferences(11, Array.ElementType, Array.IndexType);
+  checkTypeReferences(12, Class.FieldList, Class.DerivationList,
+                      Class.VTableShape);
+  checkTypeReferences(13, Union.FieldList);
+  checkTypeReferences(14, Enum.FieldList, Enum.UnderlyingType);
+  checkTypeReferences(15, BitField.Type);
+  checkTypeReferences(16, VFTable.CompleteClass, VFTable.OverriddenVFTable);
+  checkTypeReferences(17);
+  checkTypeReferences(18, MethodOverloadList.T1, MethodOverloadList.T2,
+                      MethodOverloadList.T3, MethodOverloadList.T4);
+  checkTypeReferences(19, Pointer.ReferentType);
+  checkTypeReferences(20, MemberPointer.ReferentType,
+                      MemberPointer.MemberInfo->ContainingType);
+}
+
+TEST_F(TypeIndexIteratorTest, FieldListBaseClass) {
+  using namespace members;
+  writeFieldList(BaseClass);
+  checkTypeReferences(0, BaseClass.Type);
+}
+
+TEST_F(TypeIndexIteratorTest, FieldListEnumerator) {
+  using namespace members;
+  writeFieldList(Enumerator);
+  checkTypeReferences(0);
+}
+
+TEST_F(TypeIndexIteratorTest, FieldListMember) {
+  using namespace members;
+  writeFieldList(DataMember);
+  checkTypeReferences(0, DataMember.Type);
+}
+
+TEST_F(TypeIndexIteratorTest, FieldListMethod) {
+  using namespace members;
+  writeFieldList(OverloadedMethod);
+  checkTypeReferences(0, OverloadedMethod.MethodList);
+}
+
+TEST_F(TypeIndexIteratorTest, FieldListOneMethod) {
+  using namespace members;
+  writeFieldList(OneMethod.R1, OneMethod.R2, OneMethod.R3, OneMethod.R4);
+  checkTypeReferences(0, OneMethod.T1, OneMethod.T2, OneMethod.T3,
+                      OneMethod.T4);
+}
+
+TEST_F(TypeIndexIteratorTest, FieldListNestedType) {
+  using namespace members;
+  writeFieldList(NestedType);
+  checkTypeReferences(0, NestedType.Type);
+}
+
+TEST_F(TypeIndexIteratorTest, FieldListStaticMember) {
+  using namespace members;
+  writeFieldList(StaticDataMember);
+  checkTypeReferences(0, StaticDataMember.Type);
+}
+
+TEST_F(TypeIndexIteratorTest, FieldListVirtualBase) {
+  using namespace members;
+  writeFieldList(VirtualBaseClass);
+  checkTypeReferences(0, VirtualBaseClass.BaseType, VirtualBaseClass.VBPtrType);
+}
+
+TEST_F(TypeIndexIteratorTest, FieldListVFTable) {
+  using namespace members;
+  writeFieldList(VFPtr);
+  checkTypeReferences(0, VFPtr.Type);
+}
+
+TEST_F(TypeIndexIteratorTest, FieldListContinuation) {
+  using namespace members;
+  writeFieldList(Continuation);
+  checkTypeReferences(0, Continuation.ContinuationIndex);
+}
+
+TEST_F(TypeIndexIteratorTest, ManyMembers) {
+  using namespace members;
+  writeFieldList(BaseClass, Enumerator, DataMember, OverloadedMethod,
+                 OneMethod.R1, OneMethod.R2, OneMethod.R3, OneMethod.R4,
+                 NestedType, StaticDataMember, VirtualBaseClass, VFPtr,
+                 Continuation);
+
+  checkTypeReferences(
+      0, BaseClass.Type, DataMember.Type, OverloadedMethod.MethodList,
+      OneMethod.T1, OneMethod.T2, OneMethod.T3, OneMethod.T4, NestedType.Type,
+      StaticDataMember.Type, VirtualBaseClass.BaseType,
+      VirtualBaseClass.VBPtrType, VFPtr.Type, Continuation.ContinuationIndex);
+}
 No newline at end of file