[CodeView] Fix cycles in debug info when merging Types with global hashes

[aganea]

Summary

When type streams with forward references were merged using GHashes, cycles were introduced in the debug info. This was caused by GlobalTypeTableBuilder::insertRecordAs() not inserting the record on the second pass, thus yielding an empty ArrayRef at that record slot. Later on, upon PDB emission, TpiStreamBuilder::commit() would skip that empty record, thus offseting all indices that came after in the stream.

The solution comes in two steps:

1. Fix the hash calculation, by doing a multiple-step resolution, iff there are forward references in the input stream.
2. Fix merge by resolving with multiple passes, therefore moving records with forward references at the end of the stream.

I had to make some esthetic changes, such as to support GHashes in llvm-readoj - I could commit that separately.
There's also a bugfix for dumpCodeViewMergedTypes() which previously could reference deleted memory (see comment in llvm-readobj.cpp).

Fixes PR40221

[rnk]

include/llvm/DebugInfo/CodeView/TypeCollection.h

33 ↗

(On Diff #185405)

I guess this is a question for @zturner.

include/llvm/DebugInfo/CodeView/TypeHashing.h

119

I think this would have to go to fix point, not just two passes. Consider the case where each record in the type stream refers to the next, i.e. a pointer to a pointer to a pointer ... to void, and everything is backwards. =(

[aganea]

include/llvm/DebugInfo/CodeView/TypeHashing.h

119

Good point. I can make a test case, and modify to handle that.

[zturner]

include/llvm/DebugInfo/CodeView/TypeHashing.h

119

I think we can do slightly better than go to fixed point. First go forwards, then go backwards over the remaining records. That's verrrrrry likely to get you to the end in 2 passes. If nothing else, definitely a better heuristic then always going forward.

[zturner]

include/llvm/DebugInfo/CodeView/TypeCollection.h

33 ↗

(On Diff #185405)

I'm not sold on this method. It doesn't make much sense in the base class here, because you could theoretically have implementations that aren't backed by an array. It sounds like you even ran into this in LazyRandomTypeCollection. However, I don't actually think you need this anyway. More on why later in a later comment.

tools/llvm-readobj/COFFDumper.cpp

1920–1923

Instead of constructing a TypeTableCollection here and passing it CVTypes.records(), I think you can just use the CVTypes directly. Specifically, something like this should work:

{
  ListScope S(Writer, "MergedTypeStream");
  TypeDumpVisitor TDV(CVTypes, &Writer, opts::CodeViewSubsectionBytes);
  error(codeview::visitTypeStream(TpiTypes, TDV);
  Writer.flush();
}

and similarly for the code below.

[aganea]

Simplified, following comments.

I made the test a bit more complicated, how I'm not sure such things happen with real life OBJs. The whole test resolves in 1+3 passes (1 initial and 3 extra). Evidently if we could walk backwards it could resolve in 1+2 passes, but I think it's not worth it. This whole bug only happens with very small MASM OBJs.

[aganea]

include/llvm/DebugInfo/CodeView/TypeHashing.h

119

Tried that, but given we're dealing with CVTypeArray as a Range type, we can't iterate back; unless we use something like LazyRandomTypeCollection for caching after the first run. Given that forward references seem to happen on MASM OBJs only, using a LazyRandomTypeCollection for every OBJ sounds a bit overkill. So instead I opted for several passes, like TypeStreamMerger.

tools/llvm-readobj/llvm-readobj.cpp

647

I had to move this here, because otherwise in the old place the TPI stream would reference deleted memory (because BinaryOrErr is deleted above when dumpInput() exits)

[rnk]

include/llvm/DebugInfo/CodeView/TypeHashing.h

120

I think there should be a comment before this loop explaining why it's needed, and that it's not performance critical because most objs don't have forward references.

tools/llvm-readobj/llvm-readobj.cpp

647

Hm, but won't this print the merged stream once per obj? And won't we still reference deleted memory on the second obj input? I guess the proper fix is to std::move the OwningBinary into a vector in the global ReadObjTypeTableBuilder object.

[aganea]

Removed changes that aren't critical for this fix.

[rnk]

lgtm!

test/tools/llvm-readobj/codeview-merging-ghash.test

108

Nice test!

include/llvm/DebugInfo/CodeView/AppendingTypeTableBuilder.h

class AppendingTypeTableBuilder : public TypeCollection {
 
   /// Contains a list of all records indexed by TypeIndex.toArrayIndex().
   SmallVector<ArrayRef<uint8_t>, 2> SeenRecords;
 
 public:
   explicit AppendingTypeTableBuilder(BumpPtrAllocator &Storage);
   ~AppendingTypeTableBuilder();
 
-  // TypeTableCollection overrides
+  // TypeCollection overrides
   Optional<TypeIndex> getFirst() override;
   Optional<TypeIndex> getNext(TypeIndex Prev) override;
   CVType getType(TypeIndex Index) override;
   StringRef getTypeName(TypeIndex Index) override;
   bool contains(TypeIndex Index) override;
   uint32_t size() override;
   uint32_t capacity() override;
 

include/llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h

class GlobalTypeTableBuilder : public TypeCollection {
 
   /// Contains a list of all hash values inexed by TypeIndex.toArrayIndex().
   SmallVector<GloballyHashedType, 2> SeenHashes;
 
 public:
   explicit GlobalTypeTableBuilder(BumpPtrAllocator &Storage);
   ~GlobalTypeTableBuilder();
 
-  // TypeTableCollection overrides
+  // TypeCollection overrides
   Optional<TypeIndex> getFirst() override;
   Optional<TypeIndex> getNext(TypeIndex Prev) override;
   CVType getType(TypeIndex Index) override;
   StringRef getTypeName(TypeIndex Index) override;
   bool contains(TypeIndex Index) override;
   uint32_t size() override;
   uint32_t capacity() override;
 
   // public interface
-  void reset();
   TypeIndex nextTypeIndex() const;
 
   BumpPtrAllocator &getAllocator() { return RecordStorage; }
 
   ArrayRef<ArrayRef<uint8_t>> records() const;
   ArrayRef<GloballyHashedType> hashes() const;
 
   template <typename CreateFunc>
   TypeIndex insertRecordAs(GloballyHashedType Hash, size_t RecordSize,
                            CreateFunc Create) {
     auto Result = HashedRecords.try_emplace(Hash, nextTypeIndex());
 
-    if (LLVM_UNLIKELY(Result.second)) {
+    if (LLVM_UNLIKELY(Result.second /*inserted*/ ||
+                      Result.first->second.isSimple())) {
       uint8_t *Stable = RecordStorage.Allocate<uint8_t>(RecordSize);
       MutableArrayRef<uint8_t> Data(Stable, RecordSize);
-      SeenRecords.push_back(Create(Data));
+      ArrayRef<uint8_t> StableRecord = Create(Data);
+      if (StableRecord.empty()) {
+        // Records with forward references into the Type stream will be deferred
+        // for insertion at a later time, on the second pass.
+        Result.first->getSecond() = TypeIndex(SimpleTypeKind::NotTranslated);
+        return TypeIndex(SimpleTypeKind::NotTranslated);
+      }
+      if (Result.first->second.isSimple()) {
+        assert(Result.first->second.getIndex() ==
+               (uint32_t)SimpleTypeKind::NotTranslated);
+        // On the second pass, update with index to remapped record. The
+        // (initially misbehaved) record will now come *after* other records
+        // resolved in the first pass, with proper *back* references in the
+        // stream.
+        Result.first->second = nextTypeIndex();
+      }
+      SeenRecords.push_back(StableRecord);
       SeenHashes.push_back(Hash);
     }
 
-    // Update the caller's copy of Record to point a stable copy.
     return Result.first->second;
   }
 
   TypeIndex insertRecordBytes(ArrayRef<uint8_t> Data);
   TypeIndex insertRecord(ContinuationRecordBuilder &Builder);
 
   template <typename T> TypeIndex writeLeafType(T &Record) {
     ArrayRef<uint8_t> Data = SimpleSerializer.serialize(Record);
     return insertRecordBytes(Data);
   }
 };
 
 } // end namespace codeview
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_CODEVIEW_MERGINGTYPETABLEBUILDER_H

include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h

class LazyRandomTypeCollection : public TypeCollection {
   struct CacheEntry {
     CVType Type;
     uint32_t Offset;
     StringRef Name;
   };
 
 public:
   explicit LazyRandomTypeCollection(uint32_t RecordCountHint);
-  LazyRandomTypeCollection(StringRef Data, uint32_t RecordCountHint);
-  LazyRandomTypeCollection(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint,
                            PartialOffsetArray PartialOffsets);
   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint);
 
   void reset(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
   void reset(StringRef Data, uint32_t RecordCountHint);
   void reset(BinaryStreamReader &Reader, uint32_t RecordCountHint);
 

include/llvm/DebugInfo/CodeView/MergingTypeTableBuilder.h

class MergingTypeTableBuilder : public TypeCollection {
 
   /// Contains a list of all records indexed by TypeIndex.toArrayIndex().
   SmallVector<ArrayRef<uint8_t>, 2> SeenRecords;
 
 public:
   explicit MergingTypeTableBuilder(BumpPtrAllocator &Storage);
   ~MergingTypeTableBuilder();
 
-  // TypeTableCollection overrides
+  // TypeCollection overrides
   Optional<TypeIndex> getFirst() override;
   Optional<TypeIndex> getNext(TypeIndex Prev) override;
   CVType getType(TypeIndex Index) override;
   StringRef getTypeName(TypeIndex Index) override;
   bool contains(TypeIndex Index) override;
   uint32_t size() override;
   uint32_t capacity() override;
 

include/llvm/DebugInfo/CodeView/TypeHashing.h

struct GloballyHashedType {
   GloballyHashedType(StringRef H)
       : GloballyHashedType(ArrayRef<uint8_t>(H.bytes_begin(), H.bytes_end())) {}
   GloballyHashedType(ArrayRef<uint8_t> H) {
     assert(H.size() == 8);
     ::memcpy(Hash.data(), H.data(), 8);
   }
   std::array<uint8_t, 8> Hash;
 
+  bool empty() const { return *(const uint64_t*)Hash.data() == 0; }
+
   /// Given a sequence of bytes representing a record, compute a global hash for
   /// this record.  Due to the nature of global hashes incorporating the hashes
   /// of referenced records, this function requires a list of types and ids
   /// that RecordData might reference, indexable by TypeIndex.
   static GloballyHashedType hashType(ArrayRef<uint8_t> RecordData,
                                      ArrayRef<GloballyHashedType> PreviousTypes,
                                      ArrayRef<GloballyHashedType> PreviousIds);
 
   /// Given a sequence of bytes representing a record, compute a global hash for
   /// this record.  Due to the nature of global hashes incorporating the hashes
   /// of referenced records, this function requires a list of types and ids
   /// that RecordData might reference, indexable by TypeIndex.
   static GloballyHashedType hashType(CVType Type,
                                      ArrayRef<GloballyHashedType> PreviousTypes,
                                      ArrayRef<GloballyHashedType> PreviousIds) {
     return hashType(Type.RecordData, PreviousTypes, PreviousIds);
   }
 
   /// Given a sequence of combined type and ID records, compute global hashes
   /// for each of them, returning the results in a vector of hashed types.
   template <typename Range>
   static std::vector<GloballyHashedType> hashTypes(Range &&Records) {
     std::vector<GloballyHashedType> Hashes;
-    for (const auto &R : Records)
-      Hashes.push_back(hashType(R, Hashes, Hashes));
+    bool UnresolvedRecords = false;
+    for (const auto &R : Records) {
+      GloballyHashedType H = hashType(R, Hashes, Hashes);
+      if (H.empty())
+        UnresolvedRecords = true;
+      Hashes.push_back(H);
+    }
+
+    while (UnresolvedRecords) {
+      UnresolvedRecords = false;
+      auto HashIt = Hashes.begin();
+      for (const auto &R : Records) {
+        if (HashIt->empty()) {
+          GloballyHashedType H = hashType(R, Hashes, Hashes);
+          if (H.empty())
+            UnresolvedRecords = true;
+          else
+            *HashIt = H;
+        }
+        ++HashIt;
+      }
+    }
 
     return Hashes;
   }
 
   /// Given a sequence of combined type and ID records, compute global hashes
   /// for each of them, returning the results in a vector of hashed types.
   template <typename Range>
   static std::vector<GloballyHashedType>

include/llvm/Support/BinaryStreamArray.h

public:
   BinaryStreamRef getUnderlyingStream() const { return Stream; }
   void setUnderlyingStream(BinaryStreamRef S, uint32_t Skew = 0) {
     Stream = S;
     this->Skew = Skew;
   }
 
   void drop_front() { Skew += begin()->length(); }
 
+  ArrayRef<uint8_t> getBytes() const {
+    ArrayRef<uint8_t> Buffer;
+    cantFail(Stream.readBytes(Skew, Stream.getLength() - Skew, Buffer));
+    return Buffer;
+  }
+
 private:
   BinaryStreamRef Stream;
   Extractor E;
   uint32_t Skew;
 };
 
 template <typename ValueType, typename Extractor>
 class VarStreamArrayIterator

lib/DebugInfo/CodeView/GlobalTypeTableBuilder.cpp

 ArrayRef<ArrayRef<uint8_t>> GlobalTypeTableBuilder::records() const {
   return SeenRecords;
 }
 
 ArrayRef<GloballyHashedType> GlobalTypeTableBuilder::hashes() const {
   return SeenHashes;
 }
 
-void GlobalTypeTableBuilder::reset() {
-  HashedRecords.clear();
-  SeenRecords.clear();
-}
-
 TypeIndex GlobalTypeTableBuilder::insertRecordBytes(ArrayRef<uint8_t> Record) {
   GloballyHashedType GHT =
       GloballyHashedType::hashType(Record, SeenHashes, SeenHashes);
   return insertRecordAs(GHT, Record.size(),
                         [Record](MutableArrayRef<uint8_t> Data) {
                           assert(Data.size() == Record.size());
                           ::memcpy(Data.data(), Record.data(), Record.size());
                           return Data;

lib/DebugInfo/CodeView/LazyRandomTypeCollection.cpp

 
 LazyRandomTypeCollection::LazyRandomTypeCollection(
     const CVTypeArray &Types, uint32_t RecordCountHint,
     PartialOffsetArray PartialOffsets)
     : NameStorage(Allocator), Types(Types), PartialOffsets(PartialOffsets) {
   Records.resize(RecordCountHint);
 }
 
-LazyRandomTypeCollection::LazyRandomTypeCollection(ArrayRef<uint8_t> Data,
-                                                   uint32_t RecordCountHint)
-    : LazyRandomTypeCollection(RecordCountHint) {
-}
-
-LazyRandomTypeCollection::LazyRandomTypeCollection(StringRef Data,
-                                                   uint32_t RecordCountHint)
-    : LazyRandomTypeCollection(
-          makeArrayRef(Data.bytes_begin(), Data.bytes_end()), RecordCountHint) {
-}
-
 LazyRandomTypeCollection::LazyRandomTypeCollection(const CVTypeArray &Types,
                                                    uint32_t NumRecords)
     : LazyRandomTypeCollection(Types, NumRecords, PartialOffsetArray()) {}
 
 void LazyRandomTypeCollection::reset(BinaryStreamReader &Reader,
                                      uint32_t RecordCountHint) {
   Count = 0;
   PartialOffsets = PartialOffsetArray();
Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
   assert(Next != PartialOffsets.begin());
   auto Prev = std::prev(Next);
 
   TypeIndex TIB = Prev->Type;
   if (contains(TIB)) {
     // They've asked us to fetch a type index, but the entry we found in the
     // partial offsets array has already been visited.  Since we visit an entire
     // block every time, that means this record should have been previously
-    // discovered.  Ultimately, this means this is a request for a non-existant
+    // discovered.  Ultimately, this means this is a request for a non-existent
     // type index.
     return make_error<CodeViewError>("Invalid type index");
   }
 
   TypeIndex TIE;
   if (Next == PartialOffsets.end()) {
     TIE = TypeIndex::fromArrayIndex(capacity());
   } else {

lib/DebugInfo/CodeView/TypeHashing.cpp

for (const auto &Ref : Refs) {
 
     auto RefData = RecordData.slice(Ref.Offset, Ref.Count * sizeof(TypeIndex));
     // For each type index referenced, add in the previously computed hash
     // value of that type.
     ArrayRef<TypeIndex> Indices(
         reinterpret_cast<const TypeIndex *>(RefData.data()), Ref.Count);
     for (TypeIndex TI : Indices) {
       ArrayRef<uint8_t> BytesToHash;
-      if (TI.isSimple() || TI.isNoneType() || TI.toArrayIndex() >= Prev.size()) {
+      if (TI.isSimple() || TI.isNoneType()) {
         const uint8_t *IndexBytes = reinterpret_cast<const uint8_t *>(&TI);
         BytesToHash = makeArrayRef(IndexBytes, sizeof(TypeIndex));
       } else {
+        if (TI.toArrayIndex() >= Prev.size() ||
+            Prev[TI.toArrayIndex()].empty()) {
+          // There are references to yet-unhashed records. Suspend hashing for
+          // this record until all the other records are processed.
+          return {};
+        }
         BytesToHash = Prev[TI.toArrayIndex()].Hash;
       }
       S.update(BytesToHash);
     }
 
     Off = Ref.Offset + Ref.Count * sizeof(TypeIndex);
   }
 
   // Don't forget to add in any trailing bytes.
   auto TrailingBytes = RecordData.drop_front(Off);
   S.update(TrailingBytes);
 
   return {S.final().take_back(8)};
 }

lib/DebugInfo/CodeView/TypeStreamMerger.cpp

Error TypeStreamMerger::doit(const CVTypeArray &Types) {
   }
 
   if (LastError)
     return std::move(*LastError);
   return Error::success();
 }
 
 Error TypeStreamMerger::remapAllTypes(const CVTypeArray &Types) {
-  BinaryStreamRef Stream = Types.getUnderlyingStream();
-  ArrayRef<uint8_t> Buffer;
-  cantFail(Stream.readBytes(0, Stream.getLength(), Buffer));
-
   return forEachCodeViewRecord<CVType>(
-      Buffer, [this](const CVType &T) { return remapType(T); });
+      Types.getBytes(), [this](const CVType &T) { return remapType(T); });
 }
 
 Error TypeStreamMerger::remapType(const CVType &Type) {
   auto R = shouldRemapType(Type);
   if (!R)
     return R.takeError();
 
   TypeIndex DestIdx = Untranslated;

lib/DebugInfo/PDB/Native/TpiStreamBuilder.cpp

Error TpiStreamBuilder::commit(const msf::MSFLayout &Layout,
 
   auto InfoS = WritableMappedBlockStream::createIndexedStream(Layout, Buffer,
                                                               Idx, Allocator);
 
   BinaryStreamWriter Writer(*InfoS);
   if (auto EC = Writer.writeObject(*Header))
     return EC;
 
-  for (auto Rec : TypeRecords)
+  for (auto Rec : TypeRecords) {
+    assert(!Rec.empty()); // An empty record will not write anything, but it
+                          // will shift all offsets from here on.
     if (auto EC = Writer.writeBytes(Rec))
       return EC;
+  }
 
   if (HashStreamIndex != kInvalidStreamIndex) {
     auto HVS = WritableMappedBlockStream::createIndexedStream(
         Layout, Buffer, HashStreamIndex, Allocator);
     BinaryStreamWriter HW(*HVS);
     if (HashValueStream) {
       if (auto EC = HW.writeStreamRef(*HashValueStream))
         return EC;

test/tools/llvm-readobj/codeview-merging-ghash.test

+# RUN: yaml2obj %s -o=%t.obj
+# RUN: llvm-readobj -codeview-merged-types %t.obj | FileCheck %s --check-prefix=MERGED
+# RUN: llvm-readobj -codeview-merged-types -codeview-ghash %t.obj | FileCheck %s --check-prefix=MERGED
+
+# MERGED: Format: COFF-x86-64
+# MERGED-NEXT: Arch: x86_64
+# MERGED-NEXT: AddressSize: 64bit
+# MERGED-NEXT: MergedTypeStream [
+# MERGED-NEXT:   ArgList (0x1000) {
+# MERGED-NEXT:     TypeLeafKind: LF_ARGLIST (0x1201)
+# MERGED-NEXT:     NumArgs: 0
+# MERGED-NEXT:     Arguments [
+# MERGED-NEXT:     ]
+# MERGED-NEXT:   }
+# MERGED-NEXT:   Modifier (0x1001) {
+# MERGED-NEXT:     TypeLeafKind: LF_MODIFIER (0x1001)
+# MERGED-NEXT:     ModifiedType: void (0x3)
+# MERGED-NEXT:     Modifiers [ (0x3)
+# MERGED-NEXT:       Const (0x1)
+# MERGED-NEXT:       Volatile (0x2)
+# MERGED-NEXT:     ]
+# MERGED-NEXT:   }
+# MERGED-NEXT:   Procedure (0x1002) {
+# MERGED-NEXT:     TypeLeafKind: LF_PROCEDURE (0x1008)
+# MERGED-NEXT:     ReturnType: void (0x3)
+# MERGED-NEXT:     CallingConvention: NearC (0x0)
+# MERGED-NEXT:     FunctionOptions [ (0x0)
+# MERGED-NEXT:     ]
+# MERGED-NEXT:     NumParameters: 0
+# MERGED-NEXT:     ArgListType: () (0x1000)
+# MERGED-NEXT:   }
+# MERGED-NEXT:   Pointer (0x1003) {
+# MERGED-NEXT:     TypeLeafKind: LF_POINTER (0x1002)
+# MERGED-NEXT:     PointeeType: const volatile void (0x1001)
+# MERGED-NEXT:     PtrType: Near64 (0xC)
+# MERGED-NEXT:     PtrMode: Pointer (0x0)
+# MERGED-NEXT:     IsFlat: 0
+# MERGED-NEXT:     IsConst: 1
+# MERGED-NEXT:     IsVolatile: 0
+# MERGED-NEXT:     IsUnaligned: 0
+# MERGED-NEXT:     IsRestrict: 0
+# MERGED-NEXT:     IsThisPtr&: 0
+# MERGED-NEXT:     IsThisPtr&&: 0
+# MERGED-NEXT:     SizeOf: 8
+# MERGED-NEXT:   }
+# MERGED-NEXT:   Pointer (0x1004) {
+# MERGED-NEXT:     TypeLeafKind: LF_POINTER (0x1002)
+# MERGED-NEXT:     PointeeType: const volatile void* const (0x1003)
+# MERGED-NEXT:     PtrType: Near64 (0xC)
+# MERGED-NEXT:     PtrMode: Pointer (0x0)
+# MERGED-NEXT:     IsFlat: 0
+# MERGED-NEXT:     IsConst: 1
+# MERGED-NEXT:     IsVolatile: 0
+# MERGED-NEXT:     IsUnaligned: 0
+# MERGED-NEXT:     IsRestrict: 0
+# MERGED-NEXT:     IsThisPtr&: 0
+# MERGED-NEXT:     IsThisPtr&&: 0
+# MERGED-NEXT:     SizeOf: 8
+# MERGED-NEXT:   }
+# MERGED-NEXT:   Pointer (0x1005) {
+# MERGED-NEXT:     TypeLeafKind: LF_POINTER (0x1002)
+# MERGED-NEXT:     PointeeType: const volatile void* const* const (0x1004)
+# MERGED-NEXT:     PtrType: Near64 (0xC)
+# MERGED-NEXT:     PtrMode: Pointer (0x0)
+# MERGED-NEXT:     IsFlat: 0
+# MERGED-NEXT:     IsConst: 1
+# MERGED-NEXT:     IsVolatile: 0
+# MERGED-NEXT:     IsUnaligned: 0
+# MERGED-NEXT:     IsRestrict: 0
+# MERGED-NEXT:     IsThisPtr&: 0
+# MERGED-NEXT:     IsThisPtr&&: 0
+# MERGED-NEXT:     SizeOf: 8
+# MERGED-NEXT:   }
+# MERGED-NEXT:   Pointer (0x1006) {
+# MERGED-NEXT:     TypeLeafKind: LF_POINTER (0x1002)
+# MERGED-NEXT:     PointeeType: const volatile void* const* const* const (0x1005)
+# MERGED-NEXT:     PtrType: Near64 (0xC)
+# MERGED-NEXT:     PtrMode: Pointer (0x0)
+# MERGED-NEXT:     IsFlat: 0
+# MERGED-NEXT:     IsConst: 1
+# MERGED-NEXT:     IsVolatile: 0
+# MERGED-NEXT:     IsUnaligned: 0
+# MERGED-NEXT:     IsRestrict: 0
+# MERGED-NEXT:     IsThisPtr&: 0
+# MERGED-NEXT:     IsThisPtr&&: 0
+# MERGED-NEXT:     SizeOf: 8
+# MERGED-NEXT:   }
+# MERGED-NEXT: ]
+# MERGED-NEXT: MergedIDStream [
+# MERGED-NEXT: ]
+
+--- !COFF
+header:          
+  Machine:         IMAGE_FILE_MACHINE_AMD64
+  Characteristics: [  ]
+sections:        
+  - Name:            '.debug$T'
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_DISCARDABLE, IMAGE_SCN_MEM_READ ]
+    Alignment:       1
+    Types:           
+      - Kind:            LF_PROCEDURE
+        Procedure:       
+          ReturnType:      3
+          CallConv:        NearC
+          Options:         [ None ]
+          ParameterCount:  0
+          ArgumentList:    4097
+      - Kind:            LF_ARGLIST
+        ArgList:         
+          ArgIndices:      [  ]
+      - Kind:            LF_POINTER
+        Pointer:         
+          ReferentType:    4099
+          Attrs:           66572
+      - Kind:            LF_POINTER
+        Pointer:         
+          ReferentType:    4100
+          Attrs:           66572
+      - Kind:            LF_POINTER
+        Pointer:         
+          ReferentType:    4101
+          Attrs:           66572
+      - Kind:            LF_MODIFIER
+        Modifier:        
+          ModifiedType:    3
+          Modifiers:       [ None, Const, Volatile ]
+      - Kind:            LF_POINTER
+        Pointer:         
+          ReferentType:    4098
+          Attrs:           66572
+symbols:         
+...

tools/llvm-readobj/COFFDumper.cpp

public:
   void printCOFFImports() override;
   void printCOFFExports() override;
   void printCOFFDirectives() override;
   void printCOFFBaseReloc() override;
   void printCOFFDebugDirectory() override;
   void printCOFFResources() override;
   void printCOFFLoadConfig() override;
   void printCodeViewDebugInfo() override;
-  void
-  mergeCodeViewTypes(llvm::codeview::MergingTypeTableBuilder &CVIDs,
-                     llvm::codeview::MergingTypeTableBuilder &CVTypes) override;
+  void mergeCodeViewTypes(llvm::codeview::MergingTypeTableBuilder &CVIDs,
+                          llvm::codeview::MergingTypeTableBuilder &CVTypes,
+                          llvm::codeview::GlobalTypeTableBuilder &GlobalCVIDs,
+                          llvm::codeview::GlobalTypeTableBuilder &GlobalCVTypes,
+                          bool GHash) override;
   void printStackMap() const override;
   void printAddrsig() override;
 private:
   void printSymbols() override;
   void printDynamicSymbols() override;
   void printSymbol(const SymbolRef &Sym);
   void printRelocation(const SectionRef &Section, const RelocationRef &Reloc,
                        uint64_t Bias = 0);
StringRef COFFDumper::getFileNameForFileOffset(uint32_t FileOffset) {
   return error(CVStringTable.getString(Iter->FileNameOffset));
 }
 
 void COFFDumper::printFileNameForOffset(StringRef Label, uint32_t FileOffset) {
   W.printHex(Label, getFileNameForFileOffset(FileOffset), FileOffset);
 }
 
 void COFFDumper::mergeCodeViewTypes(MergingTypeTableBuilder &CVIDs,
-                                    MergingTypeTableBuilder &CVTypes) {
+                                    MergingTypeTableBuilder &CVTypes,
+                                    GlobalTypeTableBuilder &GlobalCVIDs,
+                                    GlobalTypeTableBuilder &GlobalCVTypes,
+                                    bool GHash) {
   for (const SectionRef &S : Obj->sections()) {
     StringRef SectionName;
     error(S.getName(SectionName));
     if (SectionName == ".debug$T") {
       StringRef Data;
       error(S.getContents(Data));
       uint32_t Magic;
       error(consume(Data, Magic));
       if (Magic != 4)
         error(object_error::parse_failed);
 
       CVTypeArray Types;
       BinaryStreamReader Reader(Data, llvm::support::little);
       if (auto EC = Reader.readArray(Types, Reader.getLength())) {
         consumeError(std::move(EC));
         W.flush();
         error(object_error::parse_failed);
       }
       SmallVector<TypeIndex, 128> SourceToDest;
       Optional<uint32_t> PCHSignature;
+      if (GHash) {
+        std::vector<GloballyHashedType> Hashes =
+            GloballyHashedType::hashTypes(Types);
+        if (auto EC = mergeTypeAndIdRecords(GlobalCVIDs, GlobalCVTypes, SourceToDest, Types,
+                                            Hashes, PCHSignature))
+          return error(std::move(EC));
+      } else {
         if (auto EC = mergeTypeAndIdRecords(CVIDs, CVTypes, SourceToDest, Types,
                                             PCHSignature))
           return error(std::move(EC));
       }
     }
   }
+}
 
 void COFFDumper::printCodeViewTypeSection(StringRef SectionName,
                                           const SectionRef &Section) {
   ListScope D(W, "CodeViewTypes");
   W.printNumber("Section", SectionName, Obj->getSectionID(Section));
 
   StringRef Data;
   error(Section.getContents(Data));
if (EC || (EC = Obj->getSymbolName(*Sym, SymName))) {
       error(EC);
     }
 
     W.printNumber("Sym", SymName, SymIndex);
     Cur += Size;
   }
 }
 
-void llvm::dumpCodeViewMergedTypes(
-    ScopedPrinter &Writer, llvm::codeview::MergingTypeTableBuilder &IDTable,
-    llvm::codeview::MergingTypeTableBuilder &CVTypes) {
-  // Flatten it first, then run our dumper on it.
-  SmallString<0> TypeBuf;
-  CVTypes.ForEachRecord([&](TypeIndex TI, const CVType &Record) {
-    TypeBuf.append(Record.RecordData.begin(), Record.RecordData.end());
-  });
-
-  TypeTableCollection TpiTypes(CVTypes.records());
+void llvm::dumpCodeViewMergedTypes(ScopedPrinter &Writer,
+                                   ArrayRef<ArrayRef<uint8_t>> IpiRecords,
+                                   ArrayRef<ArrayRef<uint8_t>> TpiRecords) {
+  TypeTableCollection TpiTypes(TpiRecords);
   {
     ListScope S(Writer, "MergedTypeStream");
     TypeDumpVisitor TDV(TpiTypes, &Writer, opts::CodeViewSubsectionBytes);
     error(codeview::visitTypeStream(TpiTypes, TDV));
     Writer.flush();
   }
 
   // Flatten the id stream and print it next. The ID stream refers to names from
   // the type stream.
-  TypeTableCollection IpiTypes(IDTable.records());
+  TypeTableCollection IpiTypes(IpiRecords);
   {
     ListScope S(Writer, "MergedIDStream");
     TypeDumpVisitor TDV(TpiTypes, &Writer, opts::CodeViewSubsectionBytes);
     TDV.setIpiTypes(IpiTypes);
     error(codeview::visitTypeStream(IpiTypes, TDV));
     Writer.flush();
   }
 }

tools/llvm-readobj/ObjDumper.h

 #include "llvm/Support/CommandLine.h"
 
 namespace llvm {
 namespace object {
 class COFFImportFile;
 class ObjectFile;
 }
 namespace codeview {
+class GlobalTypeTableBuilder;
 class MergingTypeTableBuilder;
-}
+} // namespace codeview
 
 class ScopedPrinter;
 
 class ObjDumper {
 public:
   ObjDumper(ScopedPrinter &Writer);
   virtual ~ObjDumper();
 
public:
   virtual void printCOFFDirectives() { }
   virtual void printCOFFBaseReloc() { }
   virtual void printCOFFDebugDirectory() { }
   virtual void printCOFFResources() {}
   virtual void printCOFFLoadConfig() { }
   virtual void printCodeViewDebugInfo() { }
   virtual void
   mergeCodeViewTypes(llvm::codeview::MergingTypeTableBuilder &CVIDs,
-                     llvm::codeview::MergingTypeTableBuilder &CVTypes) {}
+                     llvm::codeview::MergingTypeTableBuilder &CVTypes,
+                     llvm::codeview::GlobalTypeTableBuilder &GlobalCVIDs,
+                     llvm::codeview::GlobalTypeTableBuilder &GlobalCVTypes,
+                     bool GHash) {}
 
   // Only implemented for MachO.
   virtual void printMachODataInCode() { }
   virtual void printMachOVersionMin() { }
   virtual void printMachODysymtab() { }
   virtual void printMachOSegment() { }
   virtual void printMachOIndirectSymbols() { }
   virtual void printMachOLinkerOptions() { }

 
 std::error_code createWasmDumper(const object::ObjectFile *Obj,
                                  ScopedPrinter &Writer,
                                  std::unique_ptr<ObjDumper> &Result);
 
 void dumpCOFFImportFile(const object::COFFImportFile *File,
                         ScopedPrinter &Writer);
 
-void dumpCodeViewMergedTypes(
-    ScopedPrinter &Writer, llvm::codeview::MergingTypeTableBuilder &IDTable,
-    llvm::codeview::MergingTypeTableBuilder &TypeTable);
+void dumpCodeViewMergedTypes(ScopedPrinter &Writer,
+                             ArrayRef<ArrayRef<uint8_t>> IpiRecords,
+                             ArrayRef<ArrayRef<uint8_t>> TpiRecords);
 
 } // namespace llvm
 
 #endif

tools/llvm-readobj/llvm-readobj.cpp

 // Output should be specialized for each format where appropriate.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm-readobj.h"
 #include "Error.h"
 #include "ObjDumper.h"
 #include "WindowsResourceDumper.h"
+#include "llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h"
 #include "llvm/DebugInfo/CodeView/MergingTypeTableBuilder.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Object/COFFImportFile.h"
 #include "llvm/Object/MachOUniversal.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/Object/WindowsResource.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
namespace opts {
   cl::opt<bool> CodeView("codeview",
                          cl::desc("Display CodeView debug information"));
 
   // -codeview-merged-types
   cl::opt<bool>
       CodeViewMergedTypes("codeview-merged-types",
                           cl::desc("Display the merged CodeView type stream"));
 
+  // -codeview-ghash
+  cl::opt<bool> CodeViewEnableGHash(
+      "codeview-ghash",
+      cl::desc(
+          "Enable global hashing for CodeView type stream de-duplication"));
+
   // -codeview-subsection-bytes
   cl::opt<bool> CodeViewSubsectionBytes(
       "codeview-subsection-bytes",
       cl::desc("Dump raw contents of codeview debug sections and records"));
 
   // -arm-attributes
   cl::opt<bool> ARMAttributes("arm-attributes",
                               cl::desc("Display the ARM attributes section"));
case llvm::Triple::mips64el:
     return true;
   default:
     return false;
   }
 }
 namespace {
 struct ReadObjTypeTableBuilder {
   ReadObjTypeTableBuilder()
-      : Allocator(), IDTable(Allocator), TypeTable(Allocator) {}
+      : Allocator(), IDTable(Allocator), TypeTable(Allocator),
+        GlobalIDTable(Allocator), GlobalTypeTable(Allocator) {}
 
   llvm::BumpPtrAllocator Allocator;
   llvm::codeview::MergingTypeTableBuilder IDTable;
   llvm::codeview::MergingTypeTableBuilder TypeTable;
+  llvm::codeview::GlobalTypeTableBuilder GlobalIDTable;
+  llvm::codeview::GlobalTypeTableBuilder GlobalTypeTable;
 };
-}
+} // namespace
 static ReadObjTypeTableBuilder CVTypes;
 
 /// Creates an format-specific object file dumper.
 static std::error_code createDumper(const ObjectFile *Obj,
                                     ScopedPrinter &Writer,
                                     std::unique_ptr<ObjDumper> &Result) {
   if (!Obj)
     return readobj_error::unsupported_file_format;
if (opts::COFFResources)
       Dumper->printCOFFResources();
     if (opts::COFFLoadConfig)
       Dumper->printCOFFLoadConfig();
     if (opts::Addrsig)
       Dumper->printAddrsig();
     if (opts::CodeView)
       Dumper->printCodeViewDebugInfo();
     if (opts::CodeViewMergedTypes)
-      Dumper->mergeCodeViewTypes(CVTypes.IDTable, CVTypes.TypeTable);
+      Dumper->mergeCodeViewTypes(CVTypes.IDTable, CVTypes.TypeTable,
+                                 CVTypes.GlobalIDTable, CVTypes.GlobalTypeTable,
+                                 opts::CodeViewEnableGHash);
   }
   if (Obj->isMachO()) {
     if (opts::MachODataInCode)
       Dumper->printMachODataInCode();
     if (opts::MachOIndirectSymbols)
       Dumper->printMachOIndirectSymbols();
     if (opts::MachOLinkerOptions)
       Dumper->printMachOLinkerOptions();
static void dumpInput(StringRef File) {
   else if (ObjectFile *Obj = dyn_cast<ObjectFile>(&Binary))
     dumpObject(Obj, Writer);
   else if (COFFImportFile *Import = dyn_cast<COFFImportFile>(&Binary))
     dumpCOFFImportFile(Import, Writer);
   else if (WindowsResource *WinRes = dyn_cast<WindowsResource>(&Binary))
     dumpWindowsResourceFile(WinRes);
   else
     reportError(File, readobj_error::unrecognized_file_format);
+
+  if (opts::CodeViewMergedTypes) {
+    ScopedPrinter W(outs());
+    if (opts::CodeViewEnableGHash)
+      dumpCodeViewMergedTypes(W, CVTypes.GlobalIDTable.records(),
+                              CVTypes.GlobalTypeTable.records());
+    else
+      dumpCodeViewMergedTypes(W, CVTypes.IDTable.records(),
+                              CVTypes.TypeTable.records());
+  }
 }
 
 /// Registers aliases that should only be allowed by readobj.
 static void registerReadobjAliases() {
   // -s has meant --sections for a very long time in llvm-readobj despite
   // meaning --symbols in readelf.
   static cl::alias SectionsShort("s", cl::desc("Alias for --section-headers"),
                                  cl::aliasopt(opts::SectionHeaders),
int main(int argc, const char *argv[]) {
   }
 
   // Default to stdin if no filename is specified.
   if (opts::InputFilenames.empty())
     opts::InputFilenames.push_back("-");
 
   llvm::for_each(opts::InputFilenames, dumpInput);
 
-  if (opts::CodeViewMergedTypes) {
-    ScopedPrinter W(outs());
-    dumpCodeViewMergedTypes(W, CVTypes.IDTable, CVTypes.TypeTable);
-  }
-
   return 0;
 }