[PDB] Add the ability to resolve forward references

[zturner]

Summary

Some records point to an LF_CLASS, LF_UNION, LF_STRUCTURE, or LF_ENUM which is a forward reference and doesn't contain complete debug information. In these cases, we'd like to be able to quickly locate the full record. The TPI stream stores an array of pre-computed record hash values, one for each type record. If we pre-process this on startup, we can build a mapping from hash value -> {list of possible matching type indices}. Since hashes of full records are only based on the name and or unique name and not the full record contents, we can then use forward ref record to compute the hash of what *would* be the full record by just hashing the name, use this to get the list of possible matches, and iterate those looking for a match on name or unique name.

llvm-pdbutil is updated to resolve forward references for the purposes of testing (plus it's just useful).

[zturner]

Remove the exe and obj file.

[zturner]

This was originally a combination of several patches which I tried to split up into smaller functionality. Apparently I didn't do a very good job. Removed a bunch of code that shouldn't have been in this patch.

[rnk]

llvm/include/llvm/DebugInfo/PDB/Native/TpiHashing.h

60 ↗

(On Diff #166191)

You will probably have to name the union field for this to build with all supported compilers.

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

87 ↗

(On Diff #166191)

Nested C++ containers don't usually perform the best. Here come some obnoxious data structure micro-optimization suggestions down below!

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

146 ↗

(On Diff #166191)

How about this:

1. Allocate an array of TypeIndex of size TypeIndexEnd - TypeIndexBegin, i.e. an array of all the type indices in the hash table.
2. Make HashMap a std::vector<std::pair<unsigned, unsigned>>, where these are begin/end indices of ranges into the previous array. We can write a helper that takes a hash value and returns an ArrayRef<TypeIndex> using these two arrays.
3. Build a temporary array of pairs of HashValue+TypeIndex, and sort it by hash value.
4. Iterate over the sorted array of hash values and type indices. Push each type index onto the array. When the hash value changes, store a pair of begin/end indices for the type indices that share this hash code into the HashMap.

157 ↗

(On Diff #166191)

If HV >= Header->NumHashBuckets, I would report an error or just drop the type. We could hash the type ourselves as a recovery, but it's a corrupt input file, anything but UB or crashing works.

[zturner]

It’s true that nested containers don’t usually perform well, but in this
case the outer vector *never* resizes. So it seems like it should be ok?

[rnk]

In D52283#1239983, @zturner wrote:

It’s true that nested containers don’t usually perform well, but in this
case the outer vector *never* resizes. So it seems like it should be ok?

I'd be fine with the simple code, sure. We want the PDB to load fast, though, being cache friendly is the best way to do that, IMO. :)

[zturner]

I can probably also just use the pdb::HashTable class where the key is the
actual hash value. I’ll go with the vector first since it’s simple and
obviously correct then try to change it to something more efficient in a
followup

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

struct SrcHeaderBlockEntry {
   support::ulittle32_t ObjNI;    // String table index of object name.
   support::ulittle32_t VFileNI;  // String table index of virtual file name.
   uint8_t Compression;           // PDB_SourceCompression enumeration.
   uint8_t IsVirtual;             // Is this a virtual file (injected)?
   short Padding;                 // Pad to 4 bytes.
   char Reserved[8];
 };
 
-constexpr int I = sizeof(SrcHeaderBlockEntry);
 static_assert(sizeof(SrcHeaderBlockEntry) == 40, "Incorrect struct size!");
 
 } // namespace pdb
 } // namespace llvm
 
 #endif

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

 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/Support/Error.h"
 
 namespace llvm {
 namespace pdb {
 
 Expected<uint32_t> hashTypeRecord(const llvm::codeview::CVType &Type);
 
+struct TagRecordHash {
+  explicit TagRecordHash(codeview::ClassRecord CR, uint32_t Full,
+                         uint32_t Forward)
+      : Class(std::move(CR)), FullRecordHash(Full), ForwardDeclHash(Forward) {
+    State = 0;
+  }
+
+  explicit TagRecordHash(codeview::EnumRecord ER, uint32_t Full,
+                         uint32_t Forward)
+      : Enum(std::move(ER)), FullRecordHash(Full), ForwardDeclHash(Forward) {
+    State = 1;
+  }
+
+  explicit TagRecordHash(codeview::UnionRecord UR, uint32_t Full,
+                         uint32_t Forward)
+      : Union(std::move(UR)), FullRecordHash(Full), ForwardDeclHash(Forward) {
+    State = 2;
+  }
+
+  uint32_t FullRecordHash;
+  uint32_t ForwardDeclHash;
+
+  codeview::TagRecord &getRecord() {
+    switch (State) {
+    case 0:
+      return Class;
+    case 1:
+      return Enum;
+    case 2:
+      return Union;
+    }
+    llvm_unreachable("unreachable!");
+  }
+
+private:
+  union {
+    codeview::ClassRecord Class;
+    codeview::EnumRecord Enum;
+    codeview::UnionRecord Union;
+  };
+
+  uint8_t State = 0;
+};
+
+/// Given a CVType referring to a class, structure, union, or enum, compute
+/// the hash of its forward decl and full decl.
+Expected<TagRecordHash> hashTagRecord(const codeview::CVType &Type);
+
 } // end namespace pdb
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_PDB_TPIHASHING_H

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

public:
   FixedStreamArray<codeview::TypeIndexOffset> getTypeIndexOffsets() const;
   HashTable<support::ulittle32_t> &getHashAdjusters();
 
   codeview::CVTypeRange types(bool *HadError) const;
   const codeview::CVTypeArray &typeArray() const { return TypeRecords; }
 
   codeview::LazyRandomTypeCollection &typeCollection() { return *Types; }
 
+  Expected<codeview::TypeIndex>
+  findFullDeclForForwardRef(codeview::TypeIndex ForwardRefTI) const;
+
   BinarySubstreamRef getTypeRecordsSubstream() const;
 
   Error commit();
 
+  void buildHashMap();
+
+  bool supportsTypeLookup() const;
+
 private:
   PDBFile &Pdb;
   std::unique_ptr<msf::MappedBlockStream> Stream;
 
   std::unique_ptr<codeview::LazyRandomTypeCollection> Types;
 
   BinarySubstreamRef TypeRecordsSubstream;
 
   codeview::CVTypeArray TypeRecords;
 
   std::unique_ptr<BinaryStream> HashStream;
   FixedStreamArray<support::ulittle32_t> HashValues;
   FixedStreamArray<codeview::TypeIndexOffset> TypeIndexOffsets;
   HashTable<support::ulittle32_t> HashAdjusters;
 
+  std::vector<std::vector<codeview::TypeIndex>> HashMap;
+
   const TpiStreamHeader *Header;
 };
 }
 }
 
 #endif

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

static Expected<uint32_t> getHashForUdt(const CVType &Rec) {
   T Deserialized;
   if (auto E = TypeDeserializer::deserializeAs(const_cast<CVType &>(Rec),
                                                Deserialized))
     return std::move(E);
   return getHashForUdt(Deserialized, Rec.data());
 }
 
 template <typename T>
+static Expected<TagRecordHash> getTagRecordHashForUdt(const CVType &Rec) {
+  T Deserialized;
+  if (auto E = TypeDeserializer::deserializeAs(const_cast<CVType &>(Rec),
+                                               Deserialized))
+    return std::move(E);
+
+  ClassOptions Opts = Deserialized.getOptions();
+
+  bool ForwardRef = bool(Opts & ClassOptions::ForwardReference);
+
+  uint32_t ThisRecordHash = getHashForUdt(Deserialized, Rec.data());
+
+  // If we don't have a forward ref we can't compute the hash of it from the
+  // full record because it requires hashing the entire buffer.
+  if (!ForwardRef)
+    return TagRecordHash{std::move(Deserialized), ThisRecordHash, 0};
+
+  bool Scoped = bool(Opts & ClassOptions::Scoped);
+
+  StringRef NameToHash =
+      Scoped ? Deserialized.getUniqueName() : Deserialized.getName();
+  uint32_t FullHash = hashStringV1(NameToHash);
+  return TagRecordHash{std::move(Deserialized), FullHash, ThisRecordHash};
+}
+
+template <typename T>
 static Expected<uint32_t> getSourceLineHash(const CVType &Rec) {
   T Deserialized;
   if (auto E = TypeDeserializer::deserializeAs(const_cast<CVType &>(Rec),
                                                Deserialized))
     return std::move(E);
   char Buf[4];
   support::endian::write32le(Buf, Deserialized.getUDT().getIndex());
   return hashStringV1(StringRef(Buf, 4));
 }
 
+Expected<TagRecordHash> llvm::pdb::hashTagRecord(const codeview::CVType &Type) {
+  switch (Type.kind()) {
+  case LF_CLASS:
+  case LF_STRUCTURE:
+  case LF_INTERFACE:
+    return getTagRecordHashForUdt<ClassRecord>(Type);
+  case LF_UNION:
+    return getTagRecordHashForUdt<UnionRecord>(Type);
+  case LF_ENUM:
+    return getTagRecordHashForUdt<EnumRecord>(Type);
+  default:
+    assert(false && "Type is not a tag record!");
+  }
+  return make_error<StringError>("Invalid record type",
+                                 inconvertibleErrorCode());
+}
+
 Expected<uint32_t> llvm::pdb::hashTypeRecord(const CVType &Rec) {
   switch (Rec.kind()) {
   case LF_CLASS:
   case LF_STRUCTURE:
   case LF_INTERFACE:
     return getHashForUdt<ClassRecord>(Rec);
   case LF_UNION:
     return getHashForUdt<UnionRecord>(Rec);

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/TypeDeserializer.h"
+#include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
+#include "llvm/DebugInfo/PDB/Native/Hash.h"
 #include "llvm/DebugInfo/PDB/Native/PDBFile.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"
 #include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"

 
 uint16_t TpiStream::getTypeHashStreamAuxIndex() const {
   return Header->HashAuxStreamIndex;
 }
 
 uint32_t TpiStream::getNumHashBuckets() const { return Header->NumHashBuckets; }
 uint32_t TpiStream::getHashKeySize() const { return Header->HashKeySize; }
 
+void TpiStream::buildHashMap() {
+  if (!HashMap.empty())
+    return;
+  if (HashValues.empty())
+    return;
+
+  HashMap.resize(Header->NumHashBuckets);
+
+  TypeIndex TIB{Header->TypeIndexBegin};
+  TypeIndex TIE{Header->TypeIndexEnd};
+  while (TIB < TIE) {
+    uint32_t HV = HashValues[TIB.toArrayIndex()];
+    HashMap[HV].push_back(TIB++);
+  }
+}
+
+bool TpiStream::supportsTypeLookup() const { return !HashMap.empty(); }
+
+template <typename RecordT> static ClassOptions getUdtOptions(CVType CVT) {
+  RecordT Record;
+  if (auto EC = TypeDeserializer::deserializeAs<RecordT>(CVT, Record)) {
+    consumeError(std::move(EC));
+    return ClassOptions::None;
+  }
+  return Record.getOptions();
+}
+
+static bool isUdtForwardRef(CVType CVT) {
+  ClassOptions UdtOptions = ClassOptions::None;
+  switch (CVT.kind()) {
+  case LF_STRUCTURE:
+  case LF_CLASS:
+  case LF_INTERFACE:
+    UdtOptions = getUdtOptions<ClassRecord>(std::move(CVT));
+    break;
+  case LF_ENUM:
+    UdtOptions = getUdtOptions<EnumRecord>(std::move(CVT));
+    break;
+  case LF_UNION:
+    UdtOptions = getUdtOptions<UnionRecord>(std::move(CVT));
+    break;
+  default:
+    return false;
+  }
+  return (UdtOptions & ClassOptions::ForwardReference) != ClassOptions::None;
+}
+
+Expected<TypeIndex>
+TpiStream::findFullDeclForForwardRef(TypeIndex ForwardRefTI) const {
+  CVType F = Types->getType(ForwardRefTI);
+  if (!isUdtForwardRef(F))
+    return ForwardRefTI;
+
+  Expected<TagRecordHash> ForwardTRH = hashTagRecord(F);
+  if (!ForwardTRH)
+    return ForwardTRH.takeError();
+
+  TagRecordHash Copy = std::move(*ForwardTRH);
+  uint32_t BucketIdx = ForwardTRH->FullRecordHash % Header->NumHashBuckets;
+
+  for (TypeIndex TI : HashMap[BucketIdx]) {
+    CVType CVT = Types->getType(TI);
+    if (CVT.kind() != F.kind())
+      continue;
+
+    Expected<TagRecordHash> FullTRH = hashTagRecord(CVT);
+    if (!FullTRH)
+      return FullTRH.takeError();
+    if (ForwardTRH->FullRecordHash != FullTRH->FullRecordHash)
+      continue;
+    TagRecord &ForwardTR = ForwardTRH->getRecord();
+    TagRecord &FullTR = FullTRH->getRecord();
+
+    if (!ForwardTR.hasUniqueName()) {
+      if (ForwardTR.getName() == FullTR.getName())
+        return TI;
+      continue;
+    }
+
+    if (!FullTR.hasUniqueName())
+      continue;
+    if (ForwardTR.getUniqueName() == FullTR.getUniqueName())
+      return TI;
+  }
+  return ForwardRefTI;
+}
+
 BinarySubstreamRef TpiStream::getTypeRecordsSubstream() const {
   return TypeRecordsSubstream;
 }
 
 FixedStreamArray<support::ulittle32_t> TpiStream::getHashValues() const {
   return HashValues;
 }
 

llvm/trunk/test/DebugInfo/PDB/Inputs/every-class.cpp

+// Build with "cl.exe /Z7 /GR- /GS- /GX- every-class.cpp /link /debug:full /nodefaultlib /incremental:no /entry:main"
+
+#include <stdint.h>
+
+// clang-format off
+void *__purecall = 0;
+
+void __cdecl operator delete(void *, unsigned int) {}
+void __cdecl operator delete(void *, unsigned __int64) {}
+
+struct Nothing {};
+struct Constructor { Constructor() {} };
+struct Assignment {
+  Assignment &operator=(Assignment Other) { return *this; }
+};
+struct Cast {
+  operator int() { return 42; }
+};
+
+struct Nested {
+  struct F {};
+};
+struct Operator {
+  int operator+(int X) { return 42; }
+};
+
+class Class {};
+
+union Union {};
+
+enum class Enum {A};
+
+
+template<typename T> void f(T t) {}
+
+int main(int argc, char **argv) {
+  struct Scoped {};
+  
+  struct { } Anonymous;
+
+  f(Nothing{});
+  f(Constructor{});
+  f(Assignment{});
+  f(Cast{});
+  f(Nested{});
+  f(Operator{});
+  f(Nested::F{});
+  f(Scoped{});
+  f(Class{});
+  f(Union{});
+  f(Anonymous);
+  f(Enum::A);
+  
+
+  f<const Nothing>(Nothing{});
+  f<volatile Nothing>(Nothing{});
+  f<const volatile Nothing>(Nothing{});
+  f<__unaligned Nothing>(Nothing{});
+
+  return 0;
+}

llvm/trunk/test/DebugInfo/PDB/every-type.test

 The test input (every-type.pdb) is generated from some short and trivial C++ code
 that exercises the entire type system to generate every possible type record that
 we claim to understand.  We then test this in two ways:
   1) We just dump the output for the purposes of readability.  This tests that we
      we can dump every possible type record.
   2) We dump the output to yaml, and then re-generate a PDB with the same type
      stream, and then run test 1 on the new PDB.  This verifies that the PDB
      hasn't changed.
 
 
 RUN: llvm-pdbutil dump -type-index=0x101A,0x102C,0x103D,0x104D,0x1098,0x10AA,0x10AC \
-RUN:   -dependents %p/Inputs/every-type.pdb | FileCheck --check-prefix=TYPES %s
+RUN:   -dont-resolve-forward-refs -dependents %p/Inputs/every-type.pdb \
+RUN:   | FileCheck --check-prefix=TYPES %s
 
 RUN: llvm-pdbutil pdb2yaml -tpi-stream -ipi-stream %p/Inputs/every-type.pdb > %t.pdb.yaml
 RUN: llvm-pdbutil yaml2pdb -pdb=%t.yaml.pdb %t.pdb.yaml
 RUN: llvm-pdbutil dump -type-index=0x101A,0x102C,0x103D,0x104D,0x1098,0x10AA,0x10AC \
-RUN:   -dependents %t.yaml.pdb | FileCheck --check-prefix=TYPES %s
+RUN:   -dependents -dont-resolve-forward-refs %t.yaml.pdb \
+RUN:   | FileCheck --check-prefix=TYPES %s
 
 TYPES:                           Types (TPI Stream)
 TYPES-NEXT: ============================================================
 TYPES-NEXT:   Showing 7 records and their dependents (72 records total)
 TYPES-NEXT:   0x1007 | LF_MODIFIER [size = 12]
 TYPES-NEXT:            referent = 0x0074 (int), modifiers = const
 TYPES-NEXT:   0x1008 | LF_CLASS [size = 48] `FooClass`
 TYPES-NEXT:            unique name: `.?AVFooClass@@`

llvm/trunk/test/DebugInfo/PDB/pdb-resolve-forward-refs.test

+; RUN: llvm-pdbutil dump -types %p/Inputs/every-class.pdb \
+; RUN:   | FileCheck %s
+
+; CHECK:                      Types (TPI Stream)                     
+; CHECK: ============================================================
+; CHECK:   Showing 157 records
+; CHECK:   0x1008 | LF_STRUCTURE [size = 124] `main::__l2::<unnamed-type-Anonymous>`
+; CHECK:            unique name: `.?AU<unnamed-type-Anonymous>@?1??main@@YAHHPEAPEAD@Z@`aa6523bc`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: 0x1007
+; CHECK:            options: has unique name | scoped, sizeof 1
+; CHECK:   0x1009 | LF_STRUCTURE [size = 88] `main::__l2::Scoped`
+; CHECK:            unique name: `.?AUScoped@?1??main@@YAHHPEAPEAD@Z@`aa6523bc`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: 0x1007
+; CHECK:            options: has unique name | scoped, sizeof 1
+; CHECK:   0x1054 | LF_STRUCTURE [size = 48] `Nested::F`
+; CHECK:            unique name: `.?AUF@Nested@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: <no type>
+; CHECK:            options: forward ref (-> 0x1057) | has unique name | is nested, sizeof 0
+; CHECK:   0x1056 | LF_STRUCTURE [size = 44] `Nested`
+; CHECK:            unique name: `.?AUNested@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: 0x1055
+; CHECK:            options: contains nested class | has unique name, sizeof 1
+; CHECK:   0x1057 | LF_STRUCTURE [size = 48] `Nested::F`
+; CHECK:            unique name: `.?AUF@Nested@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: 0x1007
+; CHECK:            options: has unique name | is nested, sizeof 1
+; CHECK:   0x1058 | LF_STRUCTURE [size = 52] `Constructor`
+; CHECK:            unique name: `.?AUConstructor@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: <no type>
+; CHECK:            options: forward ref (-> 0x105C) | has unique name, sizeof 0
+; CHECK:   0x105C | LF_STRUCTURE [size = 52] `Constructor`
+; CHECK:            unique name: `.?AUConstructor@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: 0x105B
+; CHECK:            options: has ctor / dtor | has unique name, sizeof 1
+; CHECK:   0x105D | LF_CLASS [size = 40] `Class`
+; CHECK:            unique name: `.?AVClass@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: 0x1007
+; CHECK:            options: has unique name, sizeof 1
+; CHECK:   0x105E | LF_UNION [size = 32] `Union`
+; CHECK:            unique name: `.?ATUnion@@`
+; CHECK:            field list: 0x1007
+; CHECK:            options: has unique name | sealed, sizeof 1
+; CHECK:   0x105F | LF_STRUCTURE [size = 48] `Operator`
+; CHECK:            unique name: `.?AUOperator@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: <no type>
+; CHECK:            options: forward ref (-> 0x1064) | has unique name, sizeof 0
+; CHECK:   0x1064 | LF_STRUCTURE [size = 48] `Operator`
+; CHECK:            unique name: `.?AUOperator@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: 0x1063
+; CHECK:            options: has unique name | overloaded operator, sizeof 1
+; CHECK:   0x1066 | LF_ENUM [size = 36] `Enum`
+; CHECK:            unique name: `.?AW4Enum@@`
+; CHECK:            field list: 0x1065, underlying type: 0x0074 (int)
+; CHECK:            options: has unique name
+; CHECK:   0x1067 | LF_STRUCTURE [size = 40] `Cast`
+; CHECK:            unique name: `.?AUCast@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: <no type>
+; CHECK:            options: forward ref (-> 0x106B) | has unique name, sizeof 0
+; CHECK:   0x106B | LF_STRUCTURE [size = 40] `Cast`
+; CHECK:            unique name: `.?AUCast@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: 0x106A
+; CHECK:            options: conversion operator | has unique name | overloaded operator, sizeof 1
+; CHECK:   0x106C | LF_STRUCTURE [size = 44] `Nothing`
+; CHECK:            unique name: `.?AUNothing@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: 0x1007
+; CHECK:            options: has unique name, sizeof 1
+; CHECK:   0x106D | LF_STRUCTURE [size = 52] `Assignment`
+; CHECK:            unique name: `.?AUAssignment@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: <no type>
+; CHECK:            options: forward ref (-> 0x1073) | has unique name, sizeof 0
+; CHECK:   0x1073 | LF_STRUCTURE [size = 52] `Assignment`
+; CHECK:            unique name: `.?AUAssignment@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: 0x1072
+; CHECK:            options: has unique name | overloaded operator | overloaded operator=, sizeof 1
+; CHECK:   0x1074 | LF_STRUCTURE [size = 44] `Nothing`
+; CHECK:            unique name: `.?AUNothing@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: <no type>
+; CHECK:            options: forward ref (<- 0x106C) | has unique name, sizeof 0
+; CHECK:   0x1081 | LF_UNION [size = 32] `Union`
+; CHECK:            unique name: `.?ATUnion@@`
+; CHECK:            field list: <no type>
+; CHECK:            options: forward ref (<- 0x105E) | has unique name, sizeof 0
+; CHECK:   0x1084 | LF_STRUCTURE [size = 124] `main::__l2::<unnamed-type-Anonymous>`
+; CHECK:            unique name: `.?AU<unnamed-type-Anonymous>@?1??main@@YAHHPEAPEAD@Z@`aa6523bc`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: <no type>
+; CHECK:            options: forward ref (<- 0x1008) | has unique name | scoped, sizeof 0
+; CHECK:   0x108E | LF_STRUCTURE [size = 44] `Nested`
+; CHECK:            unique name: `.?AUNested@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: <no type>
+; CHECK:            options: forward ref (<- 0x1056) | has unique name, sizeof 0
+; CHECK:   0x1095 | LF_STRUCTURE [size = 88] `main::__l2::Scoped`
+; CHECK:            unique name: `.?AUScoped@?1??main@@YAHHPEAPEAD@Z@`aa6523bc`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: <no type>
+; CHECK:            options: forward ref (<- 0x1009) | has unique name | scoped, sizeof 0
+; CHECK:   0x1098 | LF_CLASS [size = 40] `Class`
+; CHECK:            unique name: `.?AVClass@@`
+; CHECK:            vtable: <no type>, base list: <no type>, field list: <no type>
+; CHECK:            options: forward ref (<- 0x105D) | has unique name, sizeof 0

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

-; RUN: llvm-pdbutil dump -all %p/Inputs/empty.pdb | FileCheck -check-prefix=ALL %s
+; RUN: llvm-pdbutil dump -all -dont-resolve-forward-refs %p/Inputs/empty.pdb \
+; RUN:   | FileCheck -check-prefix=ALL %s
 ; RUN: llvm-pdbutil dump -summary -modules -files \
 ; RUN:              %p/Inputs/big-read.pdb | FileCheck -check-prefix=BIG %s
-; RUN: not llvm-pdbutil dump -summary %p/Inputs/bad-block-size.pdb 2>&1 | FileCheck -check-prefix=BAD-BLOCK-SIZE %s
+; RUN: not llvm-pdbutil dump -summary %p/Inputs/bad-block-size.pdb 2>&1 \
+; RUN:   | FileCheck -check-prefix=BAD-BLOCK-SIZE %s
 
 ALL:                                Summary
 ALL-NEXT: ============================================================
 ALL-NEXT:   Block Size: 4096
 ALL-NEXT:   Number of blocks: 25
 ALL-NEXT:   Number of streams: 17
 ALL-NEXT:   Signature: 1424295906
 ALL-NEXT:   Age: 1

llvm/trunk/tools/llvm-pdbutil/DumpOutputStyle.cpp

for (const auto &I : Indices) {
     buildDepSet(Types, DepList, DepSet);
   }
 }
 
 static void
 dumpFullTypeStream(LinePrinter &Printer, LazyRandomTypeCollection &Types,
                    uint32_t NumTypeRecords, uint32_t NumHashBuckets,
                    FixedStreamArray<support::ulittle32_t> HashValues,
-                   bool Bytes, bool Extras) {
+                   TpiStream *Stream, bool Bytes, bool Extras) {
 
   Printer.formatLine("Showing {0:N} records", NumTypeRecords);
   uint32_t Width = NumDigits(TypeIndex::FirstNonSimpleIndex + NumTypeRecords);
 
   MinimalTypeDumpVisitor V(Printer, Width + 2, Bytes, Extras, Types,
-                           NumHashBuckets, HashValues);
+                           NumHashBuckets, HashValues, Stream);
 
   if (auto EC = codeview::visitTypeStream(Types, V)) {
     Printer.formatLine("An error occurred dumping type records: {0}",
                        toString(std::move(EC)));
   }
 }
 
 static void dumpPartialTypeStream(LinePrinter &Printer,
                                   LazyRandomTypeCollection &Types,
                                   TpiStream &Stream, ArrayRef<TypeIndex> TiList,
                                   bool Bytes, bool Extras, bool Deps) {
   uint32_t Width =
       NumDigits(TypeIndex::FirstNonSimpleIndex + Stream.getNumTypeRecords());
 
   MinimalTypeDumpVisitor V(Printer, Width + 2, Bytes, Extras, Types,
-                           Stream.getNumHashBuckets(), Stream.getHashValues());
+                           Stream.getNumHashBuckets(), Stream.getHashValues(),
+                           &Stream);
 
   if (opts::dump::DumpTypeDependents) {
     // If we need to dump all dependents, then iterate each index and find
     // all dependents, adding them to a map ordered by TypeIndex.
     std::map<TypeIndex, CVType> DepSet;
     buildDepSet(Types, TiList, DepSet);
 
     Printer.formatLine(
if (auto EC = Reader.readInteger(Magic))
       return EC;
     if (Magic != COFF::DEBUG_SECTION_MAGIC)
       return make_error<StringError>("Invalid CodeView debug section.",
                                      inconvertibleErrorCode());
 
     Types.reset(Reader, 100);
 
     if (opts::dump::DumpTypes) {
-      dumpFullTypeStream(P, Types, 0, 0, {}, opts::dump::DumpTypeData, false);
+      dumpFullTypeStream(P, Types, 0, 0, {}, nullptr, opts::dump::DumpTypeData,
+                         false);
     } else if (opts::dump::DumpTypeExtras) {
       auto LocalHashes = LocallyHashedType::hashTypeCollection(Types);
       auto GlobalHashes = GloballyHashedType::hashTypeCollection(Types);
       assert(LocalHashes.size() == GlobalHashes.size());
 
       P.formatLine("Local / Global hashes:");
       TypeIndex TI(TypeIndex::FirstNonSimpleIndex);
       for (const auto &H : zip(LocalHashes, GlobalHashes)) {
Error DumpOutputStyle::dumpTpiStream(uint32_t StreamIdx) {
   AutoIndent Indent(P);
   ExitOnError Err("Unexpected error processing types: ");
 
   auto &Stream = Err((StreamIdx == StreamTPI) ? getPdb().getPDBTpiStream()
                                               : getPdb().getPDBIpiStream());
 
   auto &Types = (StreamIdx == StreamTPI) ? File.types() : File.ids();
 
+  // Enable resolving forward decls.
+  Stream.buildHashMap();
+
   if (DumpTypes || !Indices.empty()) {
     if (Indices.empty())
       dumpFullTypeStream(P, Types, Stream.getNumTypeRecords(),
                          Stream.getNumHashBuckets(), Stream.getHashValues(),
-                         DumpBytes, DumpExtras);
+                         &Stream, DumpBytes, DumpExtras);
     else {
       std::vector<TypeIndex> TiList(Indices.begin(), Indices.end());
       dumpPartialTypeStream(P, Types, Stream, TiList, DumpBytes, DumpExtras,
                             opts::dump::DumpTypeDependents);
     }
   }
 
   if (DumpExtras) {

llvm/trunk/tools/llvm-pdbutil/MinimalTypeDumper.h

 
 namespace llvm {
 namespace codeview {
 class LazyRandomTypeCollection;
 }
 
 namespace pdb {
 class LinePrinter;
+class TpiStream;
 
 class MinimalTypeDumpVisitor : public codeview::TypeVisitorCallbacks {
 public:
   MinimalTypeDumpVisitor(LinePrinter &P, uint32_t Width, bool RecordBytes,
                          bool Hashes, codeview::LazyRandomTypeCollection &Types,
                          uint32_t NumHashBuckets,
-                         FixedStreamArray<support::ulittle32_t> HashValues)
+                         FixedStreamArray<support::ulittle32_t> HashValues,
+                         pdb::TpiStream *Stream)
       : P(P), Width(Width), RecordBytes(RecordBytes), Hashes(Hashes),
-        Types(Types), NumHashBuckets(NumHashBuckets), HashValues(HashValues) {}
+        Types(Types), NumHashBuckets(NumHashBuckets), HashValues(HashValues),
+        Stream(Stream) {}
 
   Error visitTypeBegin(codeview::CVType &Record,
                        codeview::TypeIndex Index) override;
   Error visitTypeEnd(codeview::CVType &Record) override;
   Error visitMemberBegin(codeview::CVMemberRecord &Record) override;
   Error visitMemberEnd(codeview::CVMemberRecord &Record) override;
 
 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
private:
   StringRef getTypeName(codeview::TypeIndex TI) const;
 
   LinePrinter &P;
   uint32_t Width;
   bool RecordBytes = false;
   bool Hashes = false;
   codeview::LazyRandomTypeCollection &Types;
   uint32_t NumHashBuckets;
+  codeview::TypeIndex CurrentTypeIndex;
   FixedStreamArray<support::ulittle32_t> HashValues;
+  pdb::TpiStream *Stream = nullptr;
 };
 } // namespace pdb
 } // namespace llvm
 
 #endif

llvm/trunk/tools/llvm-pdbutil/MinimalTypeDumper.cpp

 //===- MinimalTypeDumper.cpp ---------------------------------- *- C++ --*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "MinimalTypeDumper.h"
 
 #include "FormatUtil.h"
 #include "LinePrinter.h"
 
+#include "llvm-pdbutil.h"
 #include "llvm/DebugInfo/CodeView/CVRecord.h"
 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
 #include "llvm/DebugInfo/CodeView/CodeView.h"
 #include "llvm/DebugInfo/CodeView/Formatters.h"
 #include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/PDB/Native/TpiHashing.h"
+#include "llvm/DebugInfo/PDB/Native/TpiStream.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/MathExtras.h"
 
 using namespace llvm;
 using namespace llvm::codeview;
 using namespace llvm::pdb;
 
 static std::string formatClassOptions(uint32_t IndentLevel,
-                                      ClassOptions Options) {
+                                      ClassOptions Options, TpiStream *Stream,
+                                      TypeIndex CurrentTypeIndex) {
   std::vector<std::string> Opts;
+
+  if (Stream && Stream->supportsTypeLookup() &&
+      !opts::dump::DontResolveForwardRefs &&
+      ((Options & ClassOptions::ForwardReference) != ClassOptions::None)) {
+    // If we're able to resolve forward references, do that.
+    Expected<TypeIndex> ETI =
+        Stream->findFullDeclForForwardRef(CurrentTypeIndex);
+    if (!ETI) {
+      consumeError(ETI.takeError());
+      PUSH_FLAG(ClassOptions, ForwardReference, Options, "forward ref (???)");
+    } else {
+      const char *Direction = (*ETI == CurrentTypeIndex)
+                                  ? "="
+                                  : ((*ETI < CurrentTypeIndex) ? "<-" : "->");
+      std::string Formatted =
+          formatv("forward ref ({0} {1})", Direction, *ETI).str();
+      PUSH_FLAG(ClassOptions, ForwardReference, Options, std::move(Formatted));
+    }
+  } else {
+    PUSH_FLAG(ClassOptions, ForwardReference, Options, "forward ref");
+  }
+
   PUSH_FLAG(ClassOptions, HasConstructorOrDestructor, Options,
             "has ctor / dtor");
   PUSH_FLAG(ClassOptions, ContainsNestedClass, Options,
             "contains nested class");
   PUSH_FLAG(ClassOptions, HasConversionOperator, Options,
             "conversion operator");
-  PUSH_FLAG(ClassOptions, ForwardReference, Options, "forward ref");
   PUSH_FLAG(ClassOptions, HasUniqueName, Options, "has unique name");
   PUSH_FLAG(ClassOptions, Intrinsic, Options, "intrin");
   PUSH_FLAG(ClassOptions, Nested, Options, "is nested");
   PUSH_FLAG(ClassOptions, HasOverloadedOperator, Options,
             "overloaded operator");
   PUSH_FLAG(ClassOptions, HasOverloadedAssignmentOperator, Options,
             "overloaded operator=");
   PUSH_FLAG(ClassOptions, Packed, Options, "packed");
PUSH_FLAG(FunctionOptions, ConstructorWithVirtualBases, Options,
             "constructor with virtual bases");
   PUSH_FLAG(FunctionOptions, Constructor, Options, "constructor");
   if (Opts.empty())
     return "None";
   return join(Opts, " | ");
 }
 
 Error MinimalTypeDumpVisitor::visitTypeBegin(CVType &Record, TypeIndex Index) {
+  CurrentTypeIndex = Index;
   // formatLine puts the newline at the beginning, so we use formatLine here
   // to start a new line, and then individual visit methods use format to
   // append to the existing line.
   if (!Hashes) {
     P.formatLine("{0} | {1} [size = {2}]",
                  fmt_align(Index, AlignStyle::Right, Width),
                  formatTypeLeafKind(Record.Type), Record.length());
   } else {

 Error MinimalTypeDumpVisitor::visitKnownRecord(CVType &CVR,
                                                ClassRecord &Class) {
   P.format(" `{0}`", Class.Name);
   if (Class.hasUniqueName())
     P.formatLine("unique name: `{0}`", Class.UniqueName);
   P.formatLine("vtable: {0}, base list: {1}, field list: {2}",
                Class.VTableShape, Class.DerivationList, Class.FieldList);
   P.formatLine("options: {0}, sizeof {1}",
-               formatClassOptions(P.getIndentLevel(), Class.Options),
+               formatClassOptions(P.getIndentLevel(), Class.Options, Stream,
+                                  CurrentTypeIndex),
                Class.Size);
   return Error::success();
 }
 
 Error MinimalTypeDumpVisitor::visitKnownRecord(CVType &CVR,
                                                UnionRecord &Union) {
   P.format(" `{0}`", Union.Name);
   if (Union.hasUniqueName())
     P.formatLine("unique name: `{0}`", Union.UniqueName);
   P.formatLine("field list: {0}", Union.FieldList);
   P.formatLine("options: {0}, sizeof {1}",
-               formatClassOptions(P.getIndentLevel(), Union.Options),
+               formatClassOptions(P.getIndentLevel(), Union.Options, Stream,
+                                  CurrentTypeIndex),
                Union.Size);
   return Error::success();
 }
 
 Error MinimalTypeDumpVisitor::visitKnownRecord(CVType &CVR, EnumRecord &Enum) {
   P.format(" `{0}`", Enum.Name);
   if (Enum.hasUniqueName())
     P.formatLine("unique name: `{0}`", Enum.UniqueName);
   P.formatLine("field list: {0}, underlying type: {1}", Enum.FieldList,
                Enum.UnderlyingType);
   P.formatLine("options: {0}",
-               formatClassOptions(P.getIndentLevel(), Enum.Options));
+               formatClassOptions(P.getIndentLevel(), Enum.Options, Stream,
+                                  CurrentTypeIndex));
   return Error::success();
 }
 
 Error MinimalTypeDumpVisitor::visitKnownRecord(CVType &CVR, ArrayRecord &AT) {
   if (AT.Name.empty()) {
     P.formatLine("size: {0}, index type: {1}, element type: {2}", AT.Size,
                  AT.IndexType, AT.ElementType);
   } else {

llvm/trunk/tools/llvm-pdbutil/llvm-pdbutil.h

 extern llvm::cl::opt<bool> DumpSectionHeaders;
 
 extern llvm::cl::opt<bool> DumpIds;
 extern llvm::cl::opt<bool> DumpIdData;
 extern llvm::cl::opt<bool> DumpIdExtras;
 extern llvm::cl::list<uint32_t> DumpIdIndex;
 extern llvm::cl::opt<uint32_t> DumpModi;
 extern llvm::cl::opt<bool> JustMyCode;
+extern llvm::cl::opt<bool> DontResolveForwardRefs;
 extern llvm::cl::opt<bool> DumpSymbols;
 extern llvm::cl::opt<bool> DumpSymRecordBytes;
 extern llvm::cl::opt<bool> DumpGSIRecords;
 extern llvm::cl::opt<bool> DumpGlobals;
 extern llvm::cl::opt<bool> DumpGlobalExtras;
 extern llvm::cl::opt<bool> DumpPublics;
 extern llvm::cl::opt<bool> DumpPublicExtras;
 extern llvm::cl::opt<bool> DumpSectionContribs;

llvm/trunk/tools/llvm-pdbutil/llvm-pdbutil.cpp

Recurse("recurse",
             cl::desc("When dumping a SymIndexId, dump the full details of the "
                      "corresponding record"),
             cl::sub(DiaDumpSubcommand));
 
 static cl::opt<bool> Enums("enums", cl::desc("Dump enum types"),
                            cl::sub(DiaDumpSubcommand));
 static cl::opt<bool> Pointers("pointers", cl::desc("Dump enum types"),
                               cl::sub(DiaDumpSubcommand));
+static cl::opt<bool> UDTs("udts", cl::desc("Dump udt types"),
+                          cl::sub(DiaDumpSubcommand));
 static cl::opt<bool> Compilands("compilands",
                                 cl::desc("Dump compiland information"),
                                 cl::sub(DiaDumpSubcommand));
 } // namespace diadump
 
 namespace pretty {
 cl::list<std::string> InputFilenames(cl::Positional,
                                      cl::desc("<input PDB files>"),
cl::opt<bool> DumpTypeData(
     "type-data",
     cl::desc("dump CodeView type record raw bytes from TPI stream"),
     cl::cat(TypeOptions), cl::sub(DumpSubcommand));
 
 cl::opt<bool> DumpTypeExtras("type-extras",
                              cl::desc("dump type hashes and index offsets"),
                              cl::cat(TypeOptions), cl::sub(DumpSubcommand));
 
+cl::opt<bool> DontResolveForwardRefs(
+    "dont-resolve-forward-refs",
+    cl::desc("When dumping type records for classes, unions, enums, and "
+             "structs, don't try to resolve forward references"),
+    cl::cat(TypeOptions), cl::sub(DumpSubcommand));
+
 cl::list<uint32_t> DumpTypeIndex(
     "type-index", cl::ZeroOrMore, cl::CommaSeparated,
     cl::desc("only dump types with the specified hexadecimal type index"),
     cl::cat(TypeOptions), cl::sub(DumpSubcommand));
 
 cl::opt<bool> DumpIds("ids",
                       cl::desc("dump CodeView type records from IPI stream"),
                       cl::cat(TypeOptions), cl::sub(DumpSubcommand));