[PDB] Merge types in parallel when using ghashing

[rnk]

Summary

This makes type merging much faster (-24% on chrome.dll) when multiple
threads are available, but it slightly increases the time to link (+10%)
when /threads:1 is passed. With only one more thread, the new type
merging is faster (-11%).

To give an idea, here is the /time output placed side by side:

                            BEFORE    | AFTER
Input File Reading:           956 ms  |  968 ms 
Code Layout:                  258 ms  |  190 ms 
Commit Output File:             6 ms  |    7 ms 
PDB Emission (Cumulative):   6691 ms  | 4253 ms 
  Add Objects:               4341 ms  | 2927 ms 
    Type Merging:            2814 ms  | 1269 ms  -55%!
    Symbol Merging:          1509 ms  | 1645 ms 
  Publics Stream Layout:      111 ms  |  112 ms 
  TPI Stream Layout:          764 ms  |   26 ms  trivial
  Commit to Disk:            1322 ms  | 1036 ms  -300ms

---

Total Link Time: 8416 ms 5882 ms -30% overall

The main source of the additional overhead in the single-threaded case
is the need to iterate all .debug$T sections up front to check which
type records should go in the IPI stream. See fillIsItemIndexFromDebugT.
With changes to the .debug$H section, we could pre-calculate this info
and eliminate the need to do this walk up front. That should restore
single-threaded performance back to what it was before this change.

This change will cause LLD to be much more parallel than it used to, and
for users who do multiple links in parallel, it could regress
performance. However, when the user is only doing one link, it's a huge
improvement. In the future, we can use NT worker threads to avoid
oversaturating the machine with work, but for now, this is such an
improvement for the single-link use case that I think we should land
this as is.

Algorithm

Before this change, we essentially used a
DenseMap<GloballyHashedType, TypeIndex> to check if a type has already
been seen, and if it hasn't been seen, insert it now and use the next
available type index for it in the destination type stream. DenseMap
does not support concurrent insertion, and even if it did, the linker
must be deterministic: it cannot produce different PDBs by using
different numbers of threads. The output type stream must be in the same
order regardless of the order of hash table insertions.

In order to create a hash table that supports concurrent insertion, the
table cells must be small enough that they can be updated atomically.
The algorithm I used for updating the table using linear probing is
described in this paper, "Concurrent Hash Tables: Fast and General(?)!":
https://dl.acm.org/doi/10.1145/3309206

The GHashCell in this change is essentially a pair of 32-bit integer
indices: <sourceIndex, typeIndex>. The sourceIndex is the index of the
TpiSource object, and it represents an input type stream. The typeIndex
is the index of the type in the stream. Together, we have something like
a ragged 2D array of ghashes, which can be looked up as:

tpiSources[tpiSrcIndex]->ghashes[typeIndex]

By using these side tables, we can omit the key data from the hash
table, and keep the table cell small. There is a cost to this: resolving
hash table collisions requires many more loads than simply looking at
the key in the same cache line as the insertion position. However, most
supported platforms should have a 64-bit CAS operation to update the
cell atomically.

To make the result of concurrent insertion deterministic, the cell
payloads must have a priority function. Defining one is pretty
straightforward: compare the two 32-bit numbers as a combined 64-bit
number. This means that types coming from inputs earlier on the command
line have a higher priority and are more likely to appear earlier in the
final PDB type stream than types from an input appearing later on the
link line.

After table insertion, the non-empty cells in the table can be copied
out of the main table and sorted by priority to determine the ordering
of the final type index stream. At this point, item and type records
must be separated, either by sorting or by splitting into two arrays,
and I chose sorting. This is why the GHashCell must contain the isItem
bit.

Once the final PDB TPI stream ordering is known, we need to compute a
mapping from source type index to PDB type index. To avoid starting over
from scratch and looking up every type again by its ghash, we save the
insertion position of every hash table insertion during the first
insertion phase. Because the table does not support rehashing, the
insertion position is stable. Using the array of insertion positions
indexed by source type index, we can replace the source type indices in
the ghash table cells with the PDB type indices.

Once the table cells have been updated to contain PDB type indices, the
mapping for each type source can be computed in parallel. Simply iterate
the list of cell positions and replace them with the PDB type index,
since the insertion positions are no longer needed.

Once we have a source to destination type index mapping for every type
source, there are no more data dependencies. We know which type records
are "unique" (not duplicates), and what their final type indices will
be. We can do the remapping in parallel, and accumulate type sizes and
type hashes in parallel by type source.

Lastly, TPI stream layout must be done serially. Accumulate all the type
records, sizes, and hashes, and add them to the PDB.

Depends On D87736

[rnk]

• rebase over previous changes
• fix funcIdToType map for /Yu files

[aganea]

Thanks a lot for working on this Reid, really neat!

This is a huge change, how do you validate that the resulting PDB is equivalent to that of the previous version (before patch) or non-ghash merging?

lld/COFF/DebugTypes.cpp

618

Fun fact, microsoft-pdb does (mistakenly?) < not <=: https://github.com/microsoft/microsoft-pdb/blob/082c5290e5aff028ae84e43affa8be717aa7af73/PDB/dbi/tpi.cpp#L1130
However it does reserve cbRecMax bytes (L942).

629

We're doing this all over the place, it'd be nice to eventually converge all variants (later).

827

I am wondering if this doesn't belong in a new file? Since the code is quite small, we could possibly have different implementations (in the future), depending on the dataset. 32-bit, 64-bit or 128-bit with no ghash indirection (if the CPU supports 128-bit CAS).

893

I can't help thinking that this smells like Clang's SourceManager index, where all sources all collated into a single index (not a 2D array).
If you did that, it would reduce the size of the cell data to 32-bit, iff we limit ourselves to 2^32 input records.
Am I being too optimistic? ;-)

952

It'd be interesting to collect statistics on how many collisions you get. And also compare linear (current behavior) vs. quadratic probing.

One issue I can see is that since the table will be 99.9% full at the end of the insertion pass, there will lots of collisions toward the end. What about making the table 25% bigger, like DenseHash does?

994

Looks like the limit in the PDB is 28-bit wide indices, probably because the PDB limit is 4 GB and because the smallest type record cannot be less that 8 bytes (4-byte header + 1 byte payload + padding).

https://github.com/microsoft/microsoft-pdb/blob/082c5290e5aff028ae84e43affa8be717aa7af73/PDB/dbi/dbiimpl.h#L62

In practice, I never saw more that a few tens of millions of type records in a 2-GB PDB. It is very unlikely that we'll ever reach this 28-bit limit.

However in this case you're talking about the cumulative (input) records count, right? That can be pretty large, I've seen 1 billion input type records (when we link our games without Unity/Jumbo files).

How many input type records do you see on your largest EXE/DLL? (we could add the total input type records count to /summary)

1031

.reserve?

1113

Remove ;

lld/COFF/PDB.cpp

898

After this patch, /DEBUG:GHASH could become the new default?

lld/test/COFF/pdb-procid-remapping.test

1–3

I know @MaskRay recently changed all < to cmd-line input and > to -o. Do you need < > here?

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

70–71

Since you probably already know how many records/hashes you're inserting, can you .reserve() TypeRecBuffers and TypeHashes in advance?

93

Same here (.reserve).

[rnk]

In D87805#2282836, @aganea wrote:

Thanks a lot for working on this Reid, really neat!

Thanks. :)

This is a huge change, how do you validate that the resulting PDB is equivalent to that of the previous version (before patch) or non-ghash merging?

Truly, I think I haven't done enough validation. But, the resulting PDB should actually be identical: it should contain the same type records, in the same order as before.

---

TODOs:

• More validation
• Look at that stale comment
• Stale ; } thing
• Maybe gather more numbers in other scenarios (concurrent links)

lld/COFF/DebugTypes.cpp

618

Right, I remember this was a source of difference between clang type records and MSVC type records. This comes up pretty regularly in the LF_FIELDLIST record of a long enum (LLVM intrinsics) for example. With an off-by-one error, you get cascading differences. It's not really a goal for the compiler to emit byte-identical types with MSVC, though, it just results in extra type info.

629

It's true. This patch does reimplement a lot of library code, rather than improving the library, which is unfortunate. I just found it really difficult to restructure the library in a way that would still be high performance.

827

Maybe it does, but I really wanted GHashTable::insert to get internal linkage from the anonymous namespace. If this becomes a template, then it matters less.

833

Hah, this comment is stale. The table actually doesn't support lookup at all anymore. It used to, before I figured out the trick of saving the insert position from the parallel insert step.

893

It's an idea, but it's expensive to decompose a SourceLocation into a file id and file offset. However... we could build one giant array of ghashes indexed by this new combined index. This would copy all .debug$H sections, but it could be worth it. This would save a level of indirection during ghash insertion collision resolution, which might be worth a lot. Hm.

Another thing to consider is that MSVC emits many more types than clang. Users mostly use /Zi, which pre-duplicates them, but if they use /Z7, it would probably break this 32-bit limit on the number of input type records. There are already perf issues with lld /debug:ghash + cl /Z7 (extra .debug$T pass), so maybe it's not worth worrying about.

952

I don't have collision stats, but I can say that the load factor in the tests I was using goes from 70% (small PDBs) to 14% (big programs, lots of duplicate types to eliminate). So, the more inputs you run it on, the more memory gets allocated, the fewer collisions their are, and the shorter the chains are.

994

Yeah, this is input records. This table size ends up being really large and this allocates a lot of memory, but remember, the .debug$T was in theory already memory mapped anyway, and this hash table is smaller than that at 8 bytes of cell vs minimum 8 bytes per record.

I logged the load factor and capacity of the table later, and this is what I got for chrome.dll:

lld-link: ghash table load factor: 26.25% (size 17307224 / capacity 65942084)

That is 65,942,084 input type records, and essentially 73.75% of them ended up being duplicates.

1031

We don't know how many cells are empty until we iterate over the table. The load factor varies widely depending on the input. I think it's better in this case to dynamically resize.

lld/COFF/PDB.cpp

898

I hope so, but let's do it separately.

lld/test/COFF/pdb-procid-remapping.test

1–3

Oh, I probably flubbed the conflict resolution. No reason.

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

70–71

I can't, this is the old entry point API, which takes one type record from the caller at a time.

93

I could reserve here, but that might actually defeat the dynamic resizing. Consider that this loop is N^2:

std::vector<int> vec;
for (int i =0 ; i < n; ++i) {
  vec.reserve(vec.size()+1);
  vec.push_back(i);
}

addTypeRecords gets called for each TpiSource, so we would end up reallocating the vector for every type source that contributes types, and maybe not increasing the size enough to remain O(n). IMO it's better to let resizing do its thing here.

[aganea]

In D87805#2283132, @rnk wrote:

Truly, I think I haven't done enough validation. But, the resulting PDB should actually be identical: it should contain the same type records, in the same order as before.

I suppose a simple way could be to temporarily retain the old algorithm and have them both run side-by-side and assert if things are different.

lld/COFF/DebugTypes.cpp

893

This would copy all .debug$H sections

I am wondering if we couldn't combine all ghashes into a contiguous virtual range of memory (both the pre-existing .debug$H and the locally computed, "owned" ones). The MapViewOfFile2/3 APIs allow changing the destination BaseAddress. There will be some dangling data around .debug$H mappings because the mapping only works on 64K-ranges, but it's maybe better than copying around a few GB worth of .debug$H sections (which also implies duplicating the memory storage for ghashes, because of the file mapping, unless we munmap after each copy).

There are already perf issues with lld /debug:ghash + cl /Z7 (extra .debug$T pass)

Like I mentionned in D55585, once ghashes computation is parallelized, it is faster on a 6-core to use /DEBUG:GHASH rather than the default /DEBUG. Were you thinking of anything else, when you say "there are already perf issues"? We've been using MSVC cl+LLD+D55585 for a long time and the timings of LLD are close to that of Clang+LLD.

994

It is clearer now, thanks. I am wondering if LLD could let the user know of an optimal table size, and let them provide that value on the cmd-line. But then it is a trade-off between the increased number of collisions (which imply an extra ghash indirection) and the smaller table size which would reduce cache misses. Just thinking out loud.

1031

Never mind, I misunderstood how the algorithm worked. It is clear now. For some reason I thought you were constructing equivalence classes.

lld/COFF/PDB.cpp

898

Sure.

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

93

Yes, you're right.

[aganea]

Some figures with this patch (6-core Xeon) -- link times only:

	VS2019 16.6.3 link.exe	LLD 10 (/DEBUG)	LLD 12 + this patch (/DEBUG)	LLD 12 + this patch (/DEBUG:GHASH)
Game - Editor MSVC	1 min 2 sec	51 sec		27 sec
Game - Editor Clang		28 sec	23 sec	16 sec
Game - Engine Release Clang		20 sec	17 sec	12 sec
Game - Engine Retail Clang		17 sec	15 sec	11 sec

lld/COFF/DebugTypes.cpp

765

This needs to be:

Expected<TypeServerSource *> tsSrc = getTypeServerSource();
if (!tsSrc)
  return; // ignore errors at this point.

Since a missing PDB is not en error, we just won't have types & symbols for that .OBJ - and we're already handling that later in mergeDebugT. Could you also please modify pdb-type-server-missing.yaml as it lacks /DEBUG:GHASH coverage, which should catch this case?

923

Note for future developement: It would be nice to support other kinds of hashers in .debug$H. SHA1 is not the best choice, see https://reviews.llvm.org/D55585#1356894 - xxHash64 seems like a better solution. I've also tried MeowHash, and since it uses AES instructions it run pretty much at memory bandwidth speed: https://github.com/cmuratori/meow_hash

973

Can you please add a timer for this part? (just the ghash generation for all files)

[rnk]

In D87805#2298905, @aganea wrote:

Some figures with this patch (6-core Xeon) -- link times only:

Thanks! For the MSVC configuration, what debug info flags are used for the compile? /Zi or /Z7, and is /Yu used?

---

I'm a bit distracted by other things, so I haven't done more validation on this yet.

lld/COFF/DebugTypes.cpp

893

Regarding the MapViewOfFile APIs, maybe. But it might be cheaper to copy the memory into huge pages anyway.

Regarding the perf issues with MSVC /Z7, I mean that MSVC /Z7 objects tend to be truly massive, containing many duplicate types. Those massive objects are usually slow to link. MSVC users typically use /Zi or /Yu to pre-deduplicate some of those types. If they were to use /Z7 instead, there might be more than 4 billion input type records, meaning we can't create a single 32-bit input type index space. But, if you have 4 billion input type records, you already have a size problem, and you can fix it by using either /Zi or clang-cl, which emits less type info.

923

I suppose the way to do this would be to receive GloballyHashedType as a template parameter. Probably necessary, but I worked so hard to make this code untemplated. :)

[rnk]

The next patch has some changes to make the output PDB identical to the old ghash PDB. I had to sort the dependency type sources to the front so that dependency types appear earlier in the final type stream. I did a few links and MD5'd the before and after PDBs with /Brepro, and they are the same. I'm reasonably confident in this at this point.

Hopefully I addressed all the outstanding comments. I think this is probably ready to land, and then we should probably make ghashing the default, since it's basically faster than the standard type merging implementation at this point. I don't have exhaustive testing for /Zi objects, though, so you might want to do some validation there.

lld/COFF/DebugTypes.cpp

765

Done, and added the coverage.

833

I updated the comments here.

952

I didn't end up collecting more stats, but the load factor is in the /verbose output if you want to check.

973

Sure, the new output looks like:

  Input File Reading:          7367 ms ( 25.9%)
  Code Layout:                 1434 ms (  5.0%)
  Commit Output File:            44 ms (  0.2%)
  PDB Emission (Cumulative):  17956 ms ( 63.2%)
    Global Type Hashing:        651 ms (  2.3%)
    GHash Type Merging:        2533 ms (  8.9%)
    Add Objects:              10098 ms ( 35.5%)
      Symbol Merging:          6882 ms ( 24.2%)
    Publics Stream Layout:     1027 ms (  3.6%)
    TPI Stream Layout:          111 ms (  0.4%)
    Commit to Disk:            5410 ms ( 19.0%)
-------------------------------------------------
Total Link Time:              28427 ms (100.0%)

[rnk]

• respond to comments
• sort dependency sources first

[aganea]

Thanks again!

LGTM with a few minor things (please see inlines below).

In D87805#2299073, @rnk wrote:

For the MSVC configuration, what debug info flags are used for the compile? /Zi or /Z7, and is /Yu used?

/Z7 because of the distribution and caching, and /Yc /Yu for locally-compiled files. We also link with a bunch of third-party libs (not ours) that are built with /Zi.

lld/COFF/DebugTypes.cpp

173

Isn't all this equivalent to llvm::stable_sort(instances, [](auto *a, auto *b) { return a->isDependency() < b->isDependency(); });?

335

Just fyi, there's a bug here when dealing with PCH (it was there since rG54a335a2f60b0f7bb85d01780bb6bbf653b1f399).
L318 should be added with: unsigned nbHeadRecords = indexMapStorage.size();
L335 should be: uint32_t srcIdx = nbHeadRecords;

lld/COFF/PDB.cpp

1575

Remove this line and the one after.

[rnk]

In D87805#2304630, @aganea wrote:

Thanks again!

LGTM with a few minor things (please see inlines below).

Thanks!

In D87805#2299073, @rnk wrote:

For the MSVC configuration, what debug info flags are used for the compile? /Zi or /Z7, and is /Yu used?

/Z7 because of the distribution and caching, and /Yc /Yu for locally-compiled files. We also link with a bunch of third-party libs (not ours) that are built with /Zi.

I see. But, you are using unity builds, right? Each /Z7 object will contain the world of STL types (std::string), but because of the unity build, the multiplier (number of objects) isn't as large.

lld/COFF/DebugTypes.cpp

173

Almost (reverse order), but I need to loop over the sources anyway to count how many dependencies there are to build the ArrayRefs. I figured it was better to write one loop to do both things. Maybe that's too much micro-optimization.

lld/COFF/PDB.cpp

1575

I wonder what is causing this. It seems related to the arcanist + clang-format presubmit, so it gets added when I upload a diff.

[aganea]

I've tried building one of our worst targets with MSVC. That is with /Z7, Unity/Jumbo files, static executable:

                                    Summary
--------------------------------------------------------------------------------
           4862 Input OBJ files (expanded from all cmd-line inputs)
             61 PDB type server dependencies
             38 Precomp OBJ dependencies
   >> 131346190 Input type records <<
        7993312 Merged TPI records
        2810451 Merged IPI records
          58136 Output PDB strings
        8313160 Global symbol records
       23959902 Module symbol records
        2098602 Public symbol records

That's 131 million type records, out of about 26 GB of .OBJ files.

Timings:

VS2019 16.6.3 link.exe	1 min 2 sec
LLD 12 + this patch	51 sec	/DEBUG
LLD 12 + this patch	21 sec	/DEBUG:GHASH

Now the same target NoUnity/NoJumbo:

                                    Summary
--------------------------------------------------------------------------------
          21351 Input OBJ files (expanded from all cmd-line inputs)
             61 PDB type server dependencies
             38 Precomp OBJ dependencies
  >> 1420669231 Input type records <<
    78665073382 Input type records bytes
        8801393 Merged TPI records
        3177158 Merged IPI records
          59194 Output PDB strings
       71576766 Global symbol records
       25416935 Module symbol records
        2103431 Public symbol records

That's 1.4 billion type records, spanning over more than 100 GB of .OBJ files. We never compile this target with debug info, because historically it wasn't even linking (link.exe was crashing, since VS2019 it seems to be fine). This is only a validation target for the build system. The resulting PDB is 2.6 GB.

Timings:

VS2019 16.6.3 link.exe	51 min 4 sec
LLD 12 + this patch	11 min 21 sec	/DEBUG
LLD 12 + this patch	6 min 38 sec	/DEBUG:GHASH

With NoUnity/NoJumbo, memory commit peaks with link.exe at over 125 GB and LLD at about 115 GB.

Given these figures, I'm not sure how we can ever reach 2^32 input records. That would be several hundreds of GB of OBJ files, and would need 256 or 512 GB of RAM to link. That could happen if the PCH files were disabled maybe. But then compilation times would skyrocket, and so would the link times.

(all timings on a 6-core Xeon)

[aganea]

lld/COFF/DebugTypes.cpp

621

@rnk: Just to follow up on https://reviews.llvm.org/D94267#2491643, the .resize() here takes 3.5 sec out of 74 sec (cumulated thread time on 72 hyper-threads).

I've modified the code to do instead two passes, then .reserve(), and that saves about 0.6 sec median walltime. Although I think it is better to wait on prefetching mmap'ed memory pages first.

Benchmark #1: before\lld-link.exe @link.rsp /threads:12
  Time (mean ± σ):     17.939 s ±  1.215 s    [User: 2.7 ms, System: 3.5 ms]
  Range (min … max):   15.537 s … 18.597 s    10 runs

Benchmark #2: after\lld-link.exe @link.rsp /threads:12
  Time (mean ± σ):     17.298 s ±  1.511 s    [User: 1.4 ms, System: 8.9 ms]
  Range (min … max):   15.512 s … 18.513 s    10 runs

As you see, there's also quite some variability in execution time, mostly because of the contention issues that I've mentionned in D94267.

[rnk]

lld/COFF/DebugTypes.cpp

621

I see, makes sense. I think it's worth doing something about this to avoid the memcpy resize overhead. We don't really need a flat buffer of type records here, I just thought it would be more efficient to flatten them than to have separate allocations for each type when most of them are small.

652

Doing an up front size calculation requires iterating all types in the TpiSource twice. The second pass will probably be hot in cache, so it's probably faster to precalculate the size with two iterations than it is to use a different, dynamic buffering strategy.

lld/COFF/DebugTypes.h

 //===- DebugTypes.h ---------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_COFF_DEBUGTYPES_H
 #define LLD_COFF_DEBUGTYPES_H
 
 #include "lld/Common/LLVM.h"
-#include "llvm/DebugInfo/CodeView/TypeIndex.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
+#include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MemoryBuffer.h"
 
 namespace llvm {
 namespace codeview {
-class PrecompRecord;
-class TypeServer2Record;
+struct GloballyHashedType;
 } // namespace codeview
 namespace pdb {
 class NativeSession;
+class TpiStream;
 }
 } // namespace llvm
 
 namespace lld {
 namespace coff {
 
+using llvm::codeview::GloballyHashedType;
 using llvm::codeview::TypeIndex;
 
 class ObjFile;
 class PDBInputFile;
 class TypeMerger;
+struct GHashState;
 
 class TpiSource {
 public:
-  enum TpiKind { Regular, PCH, UsingPCH, PDB, PDBIpi, UsingPDB };
+  enum TpiKind : uint8_t { Regular, PCH, UsingPCH, PDB, PDBIpi, UsingPDB };
 
   TpiSource(TpiKind k, ObjFile *f);
   virtual ~TpiSource();
 
   /// Produce a mapping from the type and item indices used in the object
   /// file to those in the destination PDB.
   ///
   /// If the object file uses a type server PDB (compiled with /Zi), merge TPI
   /// and IPI from the type server PDB and return a map for it. Each unique type
   /// server PDB is merged at most once, so this may return an existing index
   /// mapping.
   ///
   /// If the object does not use a type server PDB (compiled with /Z7), we merge
   /// all the type and item records from the .debug$S stream and fill in the
   /// caller-provided ObjectIndexMap.
   virtual Error mergeDebugT(TypeMerger *m);
 
+  /// Load global hashes, either by hashing types directly, or by loading them
+  /// from LLVM's .debug$H section.
+  virtual void loadGHashes();
+
+  /// Use global hashes to merge type information.
+  virtual void remapTpiWithGHashes(GHashState *g);
+
+  // Remap a type index in place.
+  bool remapTypeIndex(TypeIndex &ti, llvm::codeview::TiRefKind refKind) const;
+
+protected:
+  void remapRecord(MutableArrayRef<uint8_t> rec,
+                   ArrayRef<llvm::codeview::TiReference> typeRefs);
+
+  void mergeTypeRecord(llvm::codeview::CVType ty);
+
+  // Merge the type records listed in uniqueTypes. beginIndex is the TypeIndex
+  // of the first record in this source, typically 0x1000. When PCHs are
+  // involved, it may start higher.
+  void mergeUniqueTypeRecords(
+      ArrayRef<uint8_t> debugTypes,
+      TypeIndex beginIndex = TypeIndex(TypeIndex::FirstNonSimpleIndex));
+
+  // Use the ghash table to construct a map from source type index to
+  // destination PDB type index. Usable for either TPI or IPI.
+  void fillMapFromGHashes(GHashState *m,
+                          llvm::SmallVectorImpl<TypeIndex> &indexMap);
+
+  // Copies ghashes from a vector into an array. These are long lived, so it's
+  // worth the time to copy these into an appropriately sized vector to reduce
+  // memory usage.
+  void assignGHashesFromVector(std::vector<GloballyHashedType> &&hashVec);
+
+  // Walk over file->debugTypes and fill in the isItemIndex bit vector.
+  void fillIsItemIndexFromDebugT();
+
+public:
+  bool remapTypesInSymbolRecord(MutableArrayRef<uint8_t> rec);
+
+  void remapTypesInTypeRecord(MutableArrayRef<uint8_t> rec);
+
   /// Is this a dependent file that needs to be processed first, before other
   /// OBJs?
   virtual bool isDependency() const { return false; }
 
-  static void forEachSource(llvm::function_ref<void(TpiSource *)> fn);
+  /// Returns true if this type record should be omitted from the PDB, even if
+  /// it is unique. This prevents a record from being added to the input ghash
+  /// table.
+  bool shouldOmitFromPdb(uint32_t ghashIdx) {
+    return ghashIdx == endPrecompGHashIdx;
+  }
+
+  /// All sources of type information in the program.
+  static std::vector<TpiSource *> instances;
+
+  /// Dependency type sources, such as type servers or PCH object files. These
+  /// must be processed before objects that rely on them. Set by
+  /// TpiSources::sortDependencies.
+  static ArrayRef<TpiSource *> dependencySources;
+
+  /// Object file sources. These must be processed after dependencySources.
+  static ArrayRef<TpiSource *> objectSources;
+
+  /// Sorts the dependencies and reassigns TpiSource indices.
+  static void sortDependencies();
 
   static uint32_t countTypeServerPDBs();
   static uint32_t countPrecompObjs();
 
+  /// Free heap allocated ghashes.
+  static void clearGHashes();
+
   /// Clear global data structures for TpiSources.
   static void clear();
 
   const TpiKind kind;
+  bool ownedGHashes = true;
+  uint32_t tpiSrcIdx = 0;
+
+protected:
+  /// The ghash index (zero based, not 0x1000-based) of the LF_ENDPRECOMP record
+  /// in this object, if one exists. This is the all ones value otherwise. It is
+  /// recorded here so that it can be omitted from the final ghash table.
+  uint32_t endPrecompGHashIdx = ~0U;
+
+public:
   ObjFile *file;
 
+  /// An error encountered during type merging, if any.
+  Error typeMergingError = Error::success();
+
   // Storage for tpiMap or ipiMap, depending on the kind of source.
   llvm::SmallVector<TypeIndex, 0> indexMapStorage;
 
   // Source type index to PDB type index mapping for type and item records.
   // These mappings will be the same for /Z7 objects, and distinct for /Zi
   // objects.
   llvm::ArrayRef<TypeIndex> tpiMap;
   llvm::ArrayRef<TypeIndex> ipiMap;
+
+  /// Array of global type hashes, indexed by TypeIndex. May be calculated on
+  /// demand, or present in input object files.
+  llvm::ArrayRef<llvm::codeview::GloballyHashedType> ghashes;
+
+  /// When ghashing is used, record the mapping from LF_[M]FUNC_ID to function
+  /// type index here. Both indices are PDB indices, not object type indexes.
+  llvm::DenseMap<TypeIndex, TypeIndex> funcIdToType;
+
+  /// Indicates if a type record is an item index or a type index.
+  llvm::BitVector isItemIndex;
+
+  /// A list of all "unique" type indices which must be merged into the final
+  /// PDB. GHash type deduplication produces this list, and it should be
+  /// considerably smaller than the input.
+  std::vector<uint32_t> uniqueTypes;
+
+  struct MergedInfo {
+    std::vector<uint8_t> recs;
+    std::vector<uint16_t> recSizes;
+    std::vector<uint32_t> recHashes;
+  };
+
+  MergedInfo mergedTpi;
+  MergedInfo mergedIpi;
 };
 
 TpiSource *makeTpiSource(ObjFile *file);
 TpiSource *makeTypeServerSource(PDBInputFile *pdbInputFile);
 TpiSource *makeUseTypeServerSource(ObjFile *file,
                                    llvm::codeview::TypeServer2Record ts);
 TpiSource *makePrecompSource(ObjFile *file);
 TpiSource *makeUsePrecompSource(ObjFile *file,
                                 llvm::codeview::PrecompRecord ts);
 
 } // namespace coff
 } // namespace lld
 
 #endif

lld/COFF/DebugTypes.cpp

 //===- DebugTypes.cpp -----------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "DebugTypes.h"
 #include "Chunks.h"
 #include "Driver.h"
 #include "InputFiles.h"
+#include "PDB.h"
 #include "TypeMerger.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
+#include "lld/Common/Timer.h"
+#include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/CodeView/TypeRecordHelpers.h"
 #include "llvm/DebugInfo/CodeView/TypeStreamMerger.h"
 #include "llvm/DebugInfo/PDB/GenericError.h"
 #include "llvm/DebugInfo/PDB/Native/InfoStream.h"
 #include "llvm/DebugInfo/PDB/Native/NativeSession.h"
 #include "llvm/DebugInfo/PDB/Native/PDBFile.h"
+#include "llvm/DebugInfo/PDB/Native/TpiHashing.h"
 #include "llvm/DebugInfo/PDB/Native/TpiStream.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
 
 using namespace llvm;
 using namespace llvm::codeview;
 using namespace lld;
 using namespace lld::coff;
 
 namespace {
explicit TypeServerSource(PDBInputFile *f)
     if (!expectedInfo)
       return;
     auto it = mappings.emplace(expectedInfo->getGuid(), this);
     assert(it.second);
     (void)it;
   }
 
   Error mergeDebugT(TypeMerger *m) override;
+
+  void loadGHashes() override;
+  void remapTpiWithGHashes(GHashState *g) override;
+
   bool isDependency() const override { return true; }
 
   PDBInputFile *pdbInputFile = nullptr;
 
   // TpiSource for IPI stream.
   TypeServerIpiSource *ipiSrc = nullptr;
 
   static std::map<codeview::GUID, TypeServerSource *> mappings;
 };
 
 // Companion to TypeServerSource. Stores the index map for the IPI stream in the
 // PDB. Modeling PDBs with two sources for TPI and IPI helps establish the
 // invariant of one type index space per source.
 class TypeServerIpiSource : public TpiSource {
 public:
   explicit TypeServerIpiSource() : TpiSource(PDBIpi, nullptr) {}
 
   friend class TypeServerSource;
 
-  // IPI merging is handled in TypeServerSource::mergeDebugT, since it depends
-  // directly on type merging.
+  // All of the TpiSource methods are no-ops. The parent TypeServerSource
+  // handles both TPI and IPI.
   Error mergeDebugT(TypeMerger *m) override { return Error::success(); }
-
+  void loadGHashes() override {}
+  void remapTpiWithGHashes(GHashState *g) override {}
   bool isDependency() const override { return true; }
 };
 
 // This class represents the debug type stream of an OBJ file that depends on a
 // PDB type server (see TypeServerSource).
 class UseTypeServerSource : public TpiSource {
+  Expected<TypeServerSource *> getTypeServerSource();
+
 public:
   UseTypeServerSource(ObjFile *f, TypeServer2Record ts)
       : TpiSource(UsingPDB, f), typeServerDependency(ts) {}
 
   Error mergeDebugT(TypeMerger *m) override;
 
+  // No need to load ghashes from /Zi objects.
+  void loadGHashes() override {}
+  void remapTpiWithGHashes(GHashState *g) override;
+
   // Information about the PDB type server dependency, that needs to be loaded
   // in before merging this OBJ.
   TypeServer2Record typeServerDependency;
 };
 
 // This class represents the debug type stream of a Microsoft precompiled
 // headers OBJ (PCH OBJ). This OBJ kind needs to be merged first in the output
 // PDB, before any other OBJs that depend on this. Note that only MSVC generate
 // such files, clang does not.
 class PrecompSource : public TpiSource {
 public:
   PrecompSource(ObjFile *f) : TpiSource(PCH, f) {
     if (!f->pchSignature || !*f->pchSignature)
       fatal(toString(f) +
             " claims to be a PCH object, but does not have a valid signature");
     auto it = mappings.emplace(*f->pchSignature, this);
     if (!it.second)
       fatal("a PCH object with the same signature has already been provided (" +
             toString(it.first->second->file) + " and " + toString(file) + ")");
   }
 
+  void loadGHashes() override;
+
   bool isDependency() const override { return true; }
 
   static std::map<uint32_t, PrecompSource *> mappings;
 };
 
 // This class represents the debug type stream of an OBJ file that depends on a
 // Microsoft precompiled headers OBJ (see PrecompSource).
 class UsePrecompSource : public TpiSource {
 public:
   UsePrecompSource(ObjFile *f, PrecompRecord precomp)
       : TpiSource(UsingPCH, f), precompDependency(precomp) {}
 
   Error mergeDebugT(TypeMerger *m) override;
 
+  void loadGHashes() override;
+  void remapTpiWithGHashes(GHashState *g) override;
+
+private:
+  Error mergeInPrecompHeaderObj();
+
+public:
   // Information about the Precomp OBJ dependency, that needs to be loaded in
   // before merging this OBJ.
   PrecompRecord precompDependency;
 };
 } // namespace
 
-static std::vector<TpiSource *> gc;
-
-TpiSource::TpiSource(TpiKind k, ObjFile *f) : kind(k), file(f) {
-  gc.push_back(this);
+std::vector<TpiSource *> TpiSource::instances;
+ArrayRef<TpiSource *> TpiSource::dependencySources;
+ArrayRef<TpiSource *> TpiSource::objectSources;
+
+TpiSource::TpiSource(TpiKind k, ObjFile *f)
+    : kind(k), tpiSrcIdx(instances.size()), file(f) {
+  instances.push_back(this);
 }
 
 // Vtable key method.
 TpiSource::~TpiSource() = default;
 
+void TpiSource::sortDependencies() {
+  // Order dependencies first, but preserve the existing order.
+  std::vector<TpiSource *> deps;
+  std::vector<TpiSource *> objs;
+  for (TpiSource *s : instances)
+    (s->isDependency() ? deps : objs).push_back(s);
+  uint32_t numDeps = deps.size();
+  uint32_t numObjs = objs.size();
+  instances = std::move(deps);
+  instances.insert(instances.end(), objs.begin(), objs.end());
+  for (uint32_t i = 0, e = instances.size(); i < e; ++i)
+    instances[i]->tpiSrcIdx = i;
+  dependencySources = makeArrayRef(instances.data(), numDeps);
+  objectSources = makeArrayRef(instances.data() + numDeps, numObjs);
+}
+
 TpiSource *lld::coff::makeTpiSource(ObjFile *file) {
   return make<TpiSource>(TpiSource::Regular, file);
 }
 
 TpiSource *lld::coff::makeTypeServerSource(PDBInputFile *pdbInputFile) {
   // Type server sources come in pairs: the TPI stream, and the IPI stream.
   auto *tpiSource = make<TypeServerSource>(pdbInputFile);
   if (pdbInputFile->session->getPDBFile().hasPDBIpiStream())
TpiSource *lld::coff::makePrecompSource(ObjFile *file) {
   return make<PrecompSource>(file);
 }
 
 TpiSource *lld::coff::makeUsePrecompSource(ObjFile *file,
                                            PrecompRecord precomp) {
   return make<UsePrecompSource>(file, precomp);
 }
 
-void TpiSource::forEachSource(llvm::function_ref<void(TpiSource *)> fn) {
-  for_each(gc, fn);
-}
-
 std::map<codeview::GUID, TypeServerSource *> TypeServerSource::mappings;
 
 std::map<uint32_t, PrecompSource *> PrecompSource::mappings;
 
+bool TpiSource::remapTypeIndex(TypeIndex &ti, TiRefKind refKind) const {
+  if (ti.isSimple())
+    return true;
+
+  // This can be an item index or a type index. Choose the appropriate map.
+  ArrayRef<TypeIndex> tpiOrIpiMap =
+      (refKind == TiRefKind::IndexRef) ? ipiMap : tpiMap;
+  if (ti.toArrayIndex() >= tpiOrIpiMap.size())
+    return false;
+  ti = tpiOrIpiMap[ti.toArrayIndex()];
+  return true;
+}
+
+void TpiSource::remapRecord(MutableArrayRef<uint8_t> rec,
+                            ArrayRef<TiReference> typeRefs) {
+  MutableArrayRef<uint8_t> contents = rec.drop_front(sizeof(RecordPrefix));
+  for (const TiReference &ref : typeRefs) {
+    unsigned byteSize = ref.Count * sizeof(TypeIndex);
+    if (contents.size() < ref.Offset + byteSize)
+      fatal("symbol record too short");
+
+    MutableArrayRef<TypeIndex> indices(
+        reinterpret_cast<TypeIndex *>(contents.data() + ref.Offset), ref.Count);
+    for (TypeIndex &ti : indices) {
+      if (!remapTypeIndex(ti, ref.Kind)) {
+        if (config->verbose) {
+          uint16_t kind =
+              reinterpret_cast<const RecordPrefix *>(rec.data())->RecordKind;
+          StringRef fname = file ? file->getName() : "<unknown PDB>";
+          log("failed to remap type index in record of kind 0x" +
+              utohexstr(kind) + " in " + fname + " with bad " +
+              (ref.Kind == TiRefKind::IndexRef ? "item" : "type") +
+              " index 0x" + utohexstr(ti.getIndex()));
+        }
+        ti = TypeIndex(SimpleTypeKind::NotTranslated);
+        continue;
+      }
+    }
+  }
+}
+
+void TpiSource::remapTypesInTypeRecord(MutableArrayRef<uint8_t> rec) {
+  // TODO: Handle errors similar to symbols.
+  SmallVector<TiReference, 32> typeRefs;
+  discoverTypeIndices(CVType(rec), typeRefs);
+  remapRecord(rec, typeRefs);
+}
+
+bool TpiSource::remapTypesInSymbolRecord(MutableArrayRef<uint8_t> rec) {
+  // Discover type index references in the record. Skip it if we don't
+  // know where they are.
+  SmallVector<TiReference, 32> typeRefs;
+  if (!discoverTypeIndicesInSymbol(rec, typeRefs))
+    return false;
+  remapRecord(rec, typeRefs);
+  return true;
+}
+
 // A COFF .debug$H section is currently a clang extension.  This function checks
 // if a .debug$H section is in a format that we expect / understand, so that we
 // can ignore any sections which are coincidentally also named .debug$H but do
 // not contain a format we recognize.
 static bool canUseDebugH(ArrayRef<uint8_t> debugH) {
   if (debugH.size() < sizeof(object::debug_h_header))
     return false;
   auto *header =
static Optional<ArrayRef<uint8_t>> getDebugH(ObjFile *file) {
   if (!canUseDebugH(contents))
     return None;
   return contents;
 }
 
 static ArrayRef<GloballyHashedType>
 getHashesFromDebugH(ArrayRef<uint8_t> debugH) {
   assert(canUseDebugH(debugH));
-
   debugH = debugH.drop_front(sizeof(object::debug_h_header));
   uint32_t count = debugH.size() / sizeof(GloballyHashedType);
   return {reinterpret_cast<const GloballyHashedType *>(debugH.data()), count};
 }
 
 // Merge .debug$T for a generic object file.
 Error TpiSource::mergeDebugT(TypeMerger *m) {
+  assert(!config->debugGHashes &&
+         "use remapTpiWithGHashes when ghash is enabled");
+
   CVTypeArray types;
   BinaryStreamReader reader(file->debugTypes, support::little);
   cantFail(reader.readArray(types, reader.getLength()));
 
-  if (config->debugGHashes) {
-    ArrayRef<GloballyHashedType> hashes;
-    std::vector<GloballyHashedType> ownedHashes;
-    if (Optional<ArrayRef<uint8_t>> debugH = getDebugH(file))
-      hashes = getHashesFromDebugH(*debugH);
-    else {
-      ownedHashes = GloballyHashedType::hashTypes(types);
-      hashes = ownedHashes;
-    }
-
-    if (auto err = mergeTypeAndIdRecords(m->globalIDTable, m->globalTypeTable,
-                                         indexMapStorage, types, hashes,
-                                         file->pchSignature))
-      fatal("codeview::mergeTypeAndIdRecords failed: " +
-            toString(std::move(err)));
-  } else {
-    if (auto err =
-            mergeTypeAndIdRecords(m->idTable, m->typeTable, indexMapStorage,
-                                  types, file->pchSignature))
-      fatal("codeview::mergeTypeAndIdRecords failed: " +
-            toString(std::move(err)));
-  }
+  if (auto err = mergeTypeAndIdRecords(
+          m->idTable, m->typeTable, indexMapStorage, types, file->pchSignature))
 
   // In an object, there is only one mapping for both types and items.
   tpiMap = indexMapStorage;
   ipiMap = indexMapStorage;
 
   if (config->showSummary) {
     // Count how many times we saw each type record in our input. This
     // calculation requires a second pass over the type records to classify each
     // record as a type or index. This is slow, but this code executes when
     // collecting statistics.
     m->tpiCounts.resize(m->getTypeTable().size());
     m->ipiCounts.resize(m->getIDTable().size());
     uint32_t srcIdx = 0;
     for (CVType &ty : types) {
       TypeIndex dstIdx = tpiMap[srcIdx++];
       // Type merging may fail, so a complex source type may become the simple
       // NotTranslated type, which cannot be used as an array index.
       if (dstIdx.isSimple())
         continue;
       SmallVectorImpl<uint32_t> &counts =
           isIdRecord(ty.kind()) ? m->ipiCounts : m->tpiCounts;
       ++counts[dstIdx.toArrayIndex()];
     }
   }
 
   return Error::success();
 }
 
 // Merge types from a type server PDB.
 Error TypeServerSource::mergeDebugT(TypeMerger *m) {
+  assert(!config->debugGHashes &&
+         "use remapTpiWithGHashes when ghash is enabled");
+
   pdb::PDBFile &pdbFile = pdbInputFile->session->getPDBFile();
   Expected<pdb::TpiStream &> expectedTpi = pdbFile.getPDBTpiStream();
   if (auto e = expectedTpi.takeError())
     fatal("Type server does not have TPI stream: " + toString(std::move(e)));
   pdb::TpiStream *maybeIpi = nullptr;
   if (pdbFile.hasPDBIpiStream()) {
     Expected<pdb::TpiStream &> expectedIpi = pdbFile.getPDBIpiStream();
     if (auto e = expectedIpi.takeError())
       fatal("Error getting type server IPI stream: " + toString(std::move(e)));
     maybeIpi = &*expectedIpi;
   }
 
-  if (config->debugGHashes) {
-    // PDBs do not actually store global hashes, so when merging a type server
-    // PDB we have to synthesize global hashes.  To do this, we first synthesize
-    // global hashes for the TPI stream, since it is independent, then we
-    // synthesize hashes for the IPI stream, using the hashes for the TPI stream
-    // as inputs.
-    auto tpiHashes = GloballyHashedType::hashTypes(expectedTpi->typeArray());
-    Optional<uint32_t> endPrecomp;
-    // Merge TPI first, because the IPI stream will reference type indices.
-    if (auto err =
-            mergeTypeRecords(m->globalTypeTable, indexMapStorage,
-                             expectedTpi->typeArray(), tpiHashes, endPrecomp))
-      fatal("codeview::mergeTypeRecords failed: " + toString(std::move(err)));
-    tpiMap = indexMapStorage;
-
-    // Merge IPI.
-    if (maybeIpi) {
-      auto ipiHashes =
-          GloballyHashedType::hashIds(maybeIpi->typeArray(), tpiHashes);
-      if (auto err =
-              mergeIdRecords(m->globalIDTable, tpiMap, ipiSrc->indexMapStorage,
-                             maybeIpi->typeArray(), ipiHashes))
-        fatal("codeview::mergeIdRecords failed: " + toString(std::move(err)));
-      ipiMap = ipiSrc->indexMapStorage;
-    }
-  } else {
-    // Merge TPI first, because the IPI stream will reference type indices.
-    if (auto err = mergeTypeRecords(m->typeTable, indexMapStorage,
-                                    expectedTpi->typeArray()))
-      fatal("codeview::mergeTypeRecords failed: " + toString(std::move(err)));
-    tpiMap = indexMapStorage;
 
-    // Merge IPI.
-    if (maybeIpi) {
-      if (auto err = mergeIdRecords(m->idTable, tpiMap, ipiSrc->indexMapStorage,
-                                    maybeIpi->typeArray()))
-        fatal("codeview::mergeIdRecords failed: " + toString(std::move(err)));
-      ipiMap = ipiSrc->indexMapStorage;
-    }
-  }
 
   if (config->showSummary) {
     // Count how many times we saw each type record in our input. If a
     // destination type index is present in the source to destination type index
     // map, that means we saw it once in the input. Add it to our histogram.
     m->tpiCounts.resize(m->getTypeTable().size());
     m->ipiCounts.resize(m->getIDTable().size());
     for (TypeIndex ti : tpiMap)
       if (!ti.isSimple())
         ++m->tpiCounts[ti.toArrayIndex()];
     for (TypeIndex ti : ipiMap)
       if (!ti.isSimple())
         ++m->ipiCounts[ti.toArrayIndex()];
   }
 
   return Error::success();
 }
 
-Error UseTypeServerSource::mergeDebugT(TypeMerger *m) {
+Expected<TypeServerSource *> UseTypeServerSource::getTypeServerSource() {
   const codeview::GUID &tsId = typeServerDependency.getGuid();
   StringRef tsPath = typeServerDependency.getName();
 
   TypeServerSource *tsSrc;
   auto it = TypeServerSource::mappings.find(tsId);
   if (it != TypeServerSource::mappings.end()) {
     tsSrc = it->second;
   } else {
     // The file failed to load, lookup by name
     PDBInputFile *pdb = PDBInputFile::findFromRecordPath(tsPath, file);
     if (!pdb)
       return createFileError(tsPath, errorCodeToError(std::error_code(
                                          ENOENT, std::generic_category())));
     // If an error occurred during loading, throw it now
     if (pdb->loadErr && *pdb->loadErr)
       return createFileError(tsPath, std::move(*pdb->loadErr));
 
     tsSrc = (TypeServerSource *)pdb->debugTypesObj;
   }
+  return tsSrc;
+}
 
-  pdb::PDBFile &pdbSession = tsSrc->pdbInputFile->session->getPDBFile();
+Error UseTypeServerSource::mergeDebugT(TypeMerger *m) {
+  Expected<TypeServerSource *> tsSrc = getTypeServerSource();
+  if (!tsSrc)
+    return tsSrc.takeError();
+
+  pdb::PDBFile &pdbSession = (*tsSrc)->pdbInputFile->session->getPDBFile();
   auto expectedInfo = pdbSession.getPDBInfoStream();
   if (!expectedInfo)
     return expectedInfo.takeError();
 
   // Just because a file with a matching name was found and it was an actual
   // PDB file doesn't mean it matches.  For it to match the InfoStream's GUID
   // must match the GUID specified in the TypeServer2 record.
   if (expectedInfo->getGuid() != typeServerDependency.getGuid())
     return createFileError(
-        tsPath,
+        typeServerDependency.getName(),
         make_error<pdb::PDBError>(pdb::pdb_error_code::signature_out_of_date));
 
   // Reuse the type index map of the type server.
-  tpiMap = tsSrc->tpiMap;
-  ipiMap = tsSrc->ipiMap;
+  tpiMap = (*tsSrc)->tpiMap;
+  ipiMap = (*tsSrc)->ipiMap;
   return Error::success();
 }
 
 static bool equalsPath(StringRef path1, StringRef path2) {
 #if defined(_WIN32)
   return path1.equals_lower(path2);
 #else
   return path1.equals(path2);
for (auto kv : PrecompSource::mappings) {
 
     // Compare based solely on the file name (link.exe behavior)
     if (equalsPath(currentFileName, fileNameOnly))
       return kv.second;
   }
   return nullptr;
 }
 
-static Expected<PrecompSource *> findPrecompMap(ObjFile *file,
-                                                PrecompRecord &pr) {
+static PrecompSource *findPrecompSource(ObjFile *file, PrecompRecord &pr) {
   // Cross-compile warning: given that Clang doesn't generate LF_PRECOMP
   // records, we assume the OBJ comes from a Windows build of cl.exe. Thusly,
   // the paths embedded in the OBJs are in the Windows format.
   SmallString<128> prFileName =
       sys::path::filename(pr.getPrecompFilePath(), sys::path::Style::windows);
 
-  PrecompSource *precomp;
   auto it = PrecompSource::mappings.find(pr.getSignature());
   if (it != PrecompSource::mappings.end()) {
-    precomp = it->second;
-  } else {
-    // Lookup by name
-    precomp = findObjByName(prFileName);
-  }
+    return it->second;
+  }
+  return findObjByName(prFileName);
 
+static Expected<PrecompSource *> findPrecompMap(ObjFile *file,
+                                                PrecompRecord &pr) {
+  PrecompSource *precomp = findPrecompSource(file, pr);
+
   if (!precomp)
     return createFileError(
-        prFileName,
+        pr.getPrecompFilePath(),
         make_error<pdb::PDBError>(pdb::pdb_error_code::no_matching_pch));
 
   if (pr.getSignature() != file->pchSignature)
     return createFileError(
         toString(file),
         make_error<pdb::PDBError>(pdb::pdb_error_code::no_matching_pch));
 
   if (pr.getSignature() != *precomp->file->pchSignature)
     return createFileError(
         toString(precomp->file),
         make_error<pdb::PDBError>(pdb::pdb_error_code::no_matching_pch));
 
   return precomp;
 }
 
 /// Merges a precompiled headers TPI map into the current TPI map. The
 /// precompiled headers object will also be loaded and remapped in the
 /// process.
-static Error
-mergeInPrecompHeaderObj(ObjFile *file,
-                        SmallVectorImpl<TypeIndex> &indexMapStorage,
-                        PrecompRecord &precomp) {
-  auto e = findPrecompMap(file, precomp);
+Error UsePrecompSource::mergeInPrecompHeaderObj() {
+  auto e = findPrecompMap(file, precompDependency);
   if (!e)
     return e.takeError();
 
   PrecompSource *precompSrc = *e;
   if (precompSrc->tpiMap.empty())
     return Error::success();
 
-  assert(precomp.getStartTypeIndex() == TypeIndex::FirstNonSimpleIndex);
-  assert(precomp.getTypesCount() <= precompSrc->tpiMap.size());
+  assert(precompDependency.getStartTypeIndex() ==
+         TypeIndex::FirstNonSimpleIndex);
+  assert(precompDependency.getTypesCount() <= precompSrc->tpiMap.size());
   // Use the previously remapped index map from the precompiled headers.
   indexMapStorage.append(precompSrc->tpiMap.begin(),
-                         precompSrc->tpiMap.begin() + precomp.getTypesCount());
+                         precompSrc->tpiMap.begin() +
+                             precompDependency.getTypesCount());
+
+  if (config->debugGHashes)
+    funcIdToType = precompSrc->funcIdToType; // FIXME: Save copy
+
   return Error::success();
 }
 
 Error UsePrecompSource::mergeDebugT(TypeMerger *m) {
   // This object was compiled with /Yu, so process the corresponding
   // precompiled headers object (/Yc) first. Some type indices in the current
   // object are referencing data in the precompiled headers object, so we need
   // both to be loaded.
-  if (Error e =
-          mergeInPrecompHeaderObj(file, indexMapStorage, precompDependency))
+  if (Error e = mergeInPrecompHeaderObj())
     return e;
 
   return TpiSource::mergeDebugT(m);
 }
 
 uint32_t TpiSource::countTypeServerPDBs() {
   return TypeServerSource::mappings.size();
 }
 
 uint32_t TpiSource::countPrecompObjs() {
   return PrecompSource::mappings.size();
 }
 
 void TpiSource::clear() {
-  gc.clear();
+  // Clean up any owned ghash allocations.
+  clearGHashes();
+  TpiSource::instances.clear();
   TypeServerSource::mappings.clear();
   PrecompSource::mappings.clear();
 }
+
+//===----------------------------------------------------------------------===//
+// Parellel GHash type merging implementation.
+//===----------------------------------------------------------------------===//
+
+void TpiSource::loadGHashes() {
+  if (Optional<ArrayRef<uint8_t>> debugH = getDebugH(file)) {
+    ghashes = getHashesFromDebugH(*debugH);
+    ownedGHashes = false;
+  } else {
+    CVTypeArray types;
+    BinaryStreamReader reader(file->debugTypes, support::little);
+    cantFail(reader.readArray(types, reader.getLength()));
+    assignGHashesFromVector(GloballyHashedType::hashTypes(types));
+  }
+
+  fillIsItemIndexFromDebugT();
+}
+
+// Copies ghashes from a vector into an array. These are long lived, so it's
+// worth the time to copy these into an appropriately sized vector to reduce
+// memory usage.
+void TpiSource::assignGHashesFromVector(
+    std::vector<GloballyHashedType> &&hashVec) {
+  GloballyHashedType *hashes = new GloballyHashedType[hashVec.size()];
+  memcpy(hashes, hashVec.data(), hashVec.size() * sizeof(GloballyHashedType));
+  ghashes = makeArrayRef(hashes, hashVec.size());
+  ownedGHashes = true;
+}
+
+// Faster way to iterate type records. forEachTypeChecked is faster than
+// iterating CVTypeArray. It avoids virtual readBytes calls in inner loops.
+static void forEachTypeChecked(ArrayRef<uint8_t> types,
+                               function_ref<void(const CVType &)> fn) {
+  checkError(
+      forEachCodeViewRecord<CVType>(types, [fn](const CVType &ty) -> Error {
+        fn(ty);
+        return Error::success();
+      }));
+}
+
+// Walk over file->debugTypes and fill in the isItemIndex bit vector.
+// TODO: Store this information in .debug$H so that we don't have to recompute
+// it. This is the main bottleneck slowing down parallel ghashing with one
+// thread over single-threaded ghashing.
+void TpiSource::fillIsItemIndexFromDebugT() {
+  uint32_t index = 0;
+  isItemIndex.resize(ghashes.size());
+  forEachTypeChecked(file->debugTypes, [&](const CVType &ty) {
+    if (isIdRecord(ty.kind()))
+      isItemIndex.set(index);
+    ++index;
+  });
+}
+
+void TpiSource::mergeTypeRecord(CVType ty) {
+  // Decide if the merged type goes into TPI or IPI.
+  bool isItem = isIdRecord(ty.kind());
+  MergedInfo &merged = isItem ? mergedIpi : mergedTpi;
+
+  // Copy the type into our mutable buffer.
+  assert(ty.length() <= codeview::MaxRecordLength);
+  size_t offset = merged.recs.size();
+  size_t newSize = alignTo(ty.length(), 4);
+  merged.recs.resize(offset + newSize);
+  auto newRec = makeMutableArrayRef(&merged.recs[offset], newSize);
+  memcpy(newRec.data(), ty.data().data(), newSize);
+
+  // Fix up the record prefix and padding bytes if it required resizing.
+  if (newSize != ty.length()) {
+    reinterpret_cast<RecordPrefix *>(newRec.data())->RecordLen = newSize - 2;
+    for (size_t i = ty.length(); i < newSize; ++i)
+      newRec[i] = LF_PAD0 + (newSize - i);
+  }
+
+  // Remap the type indices in the new record.
+  remapTypesInTypeRecord(newRec);
+  uint32_t pdbHash = check(pdb::hashTypeRecord(CVType(newRec)));
+  merged.recSizes.push_back(static_cast<uint16_t>(newSize));
+  merged.recHashes.push_back(pdbHash);
+}
+
+void TpiSource::mergeUniqueTypeRecords(ArrayRef<uint8_t> typeRecords,
+                                       TypeIndex beginIndex) {
+  // Re-sort the list of unique types by index.
+  if (kind == PDB)
+    assert(std::is_sorted(uniqueTypes.begin(), uniqueTypes.end()));
+  else
+    llvm::sort(uniqueTypes);
+
+  // Accumulate all the unique types into one buffer in mergedTypes.
+  uint32_t ghashIndex = 0;
+  auto nextUniqueIndex = uniqueTypes.begin();
+  assert(mergedTpi.recs.empty());
+  assert(mergedIpi.recs.empty());
+  forEachTypeChecked(typeRecords, [&](const CVType &ty) {
+    if (nextUniqueIndex != uniqueTypes.end() &&
+        *nextUniqueIndex == ghashIndex) {
+      mergeTypeRecord(ty);
+      ++nextUniqueIndex;
+    }
+    if (ty.kind() == LF_FUNC_ID || ty.kind() == LF_MFUNC_ID) {
+      bool success = ty.length() >= 12;
+      TypeIndex srcFuncIdIndex = beginIndex + ghashIndex;
+      TypeIndex funcId = srcFuncIdIndex;
+      TypeIndex funcType;
+      if (success) {
+        funcType = *reinterpret_cast<const TypeIndex *>(&ty.data()[8]);
+        success &= remapTypeIndex(funcId, TiRefKind::IndexRef);
+        success &= remapTypeIndex(funcType, TiRefKind::TypeRef);
+      }
+      if (success) {
+        funcIdToType.insert({funcId, funcType});
+      } else {
+        StringRef fname = file ? file->getName() : "<unknown PDB>";
+        warn("corrupt LF_[M]FUNC_ID record 0x" +
+             utohexstr(srcFuncIdIndex.getIndex()) + " in " + fname);
+      }
+    }
+    ++ghashIndex;
+  });
+  assert(nextUniqueIndex == uniqueTypes.end() &&
+         "failed to merge all desired records");
+  assert(uniqueTypes.size() ==
+             mergedTpi.recSizes.size() + mergedIpi.recSizes.size() &&
+         "missing desired record");
+}
+
+void TpiSource::remapTpiWithGHashes(GHashState *g) {
+  assert(config->debugGHashes && "ghashes must be enabled");
+  fillMapFromGHashes(g, indexMapStorage);
+  tpiMap = indexMapStorage;
+  ipiMap = indexMapStorage;
+  mergeUniqueTypeRecords(file->debugTypes);
+  // TODO: Free all unneeded ghash resources now that we have a full index map.
+}
+
+// PDBs do not actually store global hashes, so when merging a type server
+// PDB we have to synthesize global hashes.  To do this, we first synthesize
+// global hashes for the TPI stream, since it is independent, then we
+// synthesize hashes for the IPI stream, using the hashes for the TPI stream
+// as inputs.
+void TypeServerSource::loadGHashes() {
+  // Don't hash twice.
+  if (!ghashes.empty())
+    return;
+  pdb::PDBFile &pdbFile = pdbInputFile->session->getPDBFile();
+
+  // Hash TPI stream.
+  Expected<pdb::TpiStream &> expectedTpi = pdbFile.getPDBTpiStream();
+  if (auto e = expectedTpi.takeError())
+    fatal("Type server does not have TPI stream: " + toString(std::move(e)));
+  assignGHashesFromVector(
+      GloballyHashedType::hashTypes(expectedTpi->typeArray()));
+  isItemIndex.resize(ghashes.size());
+
+  // Hash IPI stream, which depends on TPI ghashes.
+  if (!pdbFile.hasPDBIpiStream())
+    return;
+  Expected<pdb::TpiStream &> expectedIpi = pdbFile.getPDBIpiStream();
+  if (auto e = expectedIpi.takeError())
+    fatal("error retreiving IPI stream: " + toString(std::move(e)));
+  ipiSrc->assignGHashesFromVector(
+      GloballyHashedType::hashIds(expectedIpi->typeArray(), ghashes));
+
+  // The IPI stream isItemIndex bitvector should be all ones.
+  ipiSrc->isItemIndex.resize(ipiSrc->ghashes.size());
+  ipiSrc->isItemIndex.set(0, ipiSrc->ghashes.size());
+}
+
+// Flatten discontiguous PDB type arrays to bytes so that we can use
+// forEachTypeChecked instead of CVTypeArray iteration. Copying all types from
+// type servers is faster than iterating all object files compiled with /Z7 with
+// CVTypeArray, which has high overheads due to the virtual interface of
+// BinaryStream::readBytes.
+static ArrayRef<uint8_t> typeArrayToBytes(const CVTypeArray &types) {
+  BinaryStreamRef stream = types.getUnderlyingStream();
+  ArrayRef<uint8_t> debugTypes;
+  checkError(stream.readBytes(0, stream.getLength(), debugTypes));
+  return debugTypes;
+}
+
+// Merge types from a type server PDB.
+void TypeServerSource::remapTpiWithGHashes(GHashState *g) {
+  assert(config->debugGHashes && "ghashes must be enabled");
+
+  // IPI merging depends on TPI, so do TPI first, then do IPI.  No need to
+  // propagate errors, those should've been handled during ghash loading.
+  pdb::PDBFile &pdbFile = pdbInputFile->session->getPDBFile();
+  pdb::TpiStream &tpi = check(pdbFile.getPDBTpiStream());
+  fillMapFromGHashes(g, indexMapStorage);
+  tpiMap = indexMapStorage;
+  mergeUniqueTypeRecords(typeArrayToBytes(tpi.typeArray()));
+  if (pdbFile.hasPDBIpiStream()) {
+    pdb::TpiStream &ipi = check(pdbFile.getPDBIpiStream());
+    ipiSrc->indexMapStorage.resize(ipiSrc->ghashes.size());
+    ipiSrc->fillMapFromGHashes(g, ipiSrc->indexMapStorage);
+    ipiMap = ipiSrc->indexMapStorage;
+    ipiSrc->tpiMap = tpiMap;
+    ipiSrc->ipiMap = ipiMap;
+    ipiSrc->mergeUniqueTypeRecords(typeArrayToBytes(ipi.typeArray()));
+    funcIdToType = ipiSrc->funcIdToType; // FIXME: Save copy
+  }
+}
+
+void UseTypeServerSource::remapTpiWithGHashes(GHashState *g) {
+  // No remapping to do with /Zi objects. Simply use the index map from the type
+  // server. Errors should have been reported earlier. Symbols from this object
+  // will be ignored.
+  Expected<TypeServerSource *> maybeTsSrc = getTypeServerSource();
+  if (!maybeTsSrc) {
+    typeMergingError = maybeTsSrc.takeError();
+    return;
+  }
+  TypeServerSource *tsSrc = *maybeTsSrc;
+  tpiMap = tsSrc->tpiMap;
+  ipiMap = tsSrc->ipiMap;
+  funcIdToType = tsSrc->funcIdToType; // FIXME: Save copy
+}
+
+void PrecompSource::loadGHashes() {
+  if (getDebugH(file)) {
+    warn("ignoring .debug$H section; pch with ghash is not implemented");
+  }
+
+  uint32_t ghashIdx = 0;
+  std::vector<GloballyHashedType> hashVec;
+  forEachTypeChecked(file->debugTypes, [&](const CVType &ty) {
+    // Remember the index of the LF_ENDPRECOMP record so it can be excluded from
+    // the PDB. There must be an entry in the list of ghashes so that the type
+    // indexes of the following records in the /Yc PCH object line up.
+    if (ty.kind() == LF_ENDPRECOMP)
+      endPrecompGHashIdx = ghashIdx;
+
+    hashVec.push_back(GloballyHashedType::hashType(ty, hashVec, hashVec));
+    isItemIndex.push_back(isIdRecord(ty.kind()));
+    ++ghashIdx;
+  });
+  assignGHashesFromVector(std::move(hashVec));
+}
+
+void UsePrecompSource::loadGHashes() {
+  PrecompSource *pchSrc = findPrecompSource(file, precompDependency);
+  if (!pchSrc)
+    return;
+
+  // To compute ghashes of a /Yu object file, we need to build on the the
+  // ghashes of the /Yc PCH object. After we are done hashing, discard the
+  // ghashes from the PCH source so we don't unnecessarily try to deduplicate
+  // them.
+  std::vector<GloballyHashedType> hashVec =
+      pchSrc->ghashes.take_front(precompDependency.getTypesCount());
+  forEachTypeChecked(file->debugTypes, [&](const CVType &ty) {
+    hashVec.push_back(GloballyHashedType::hashType(ty, hashVec, hashVec));
+    isItemIndex.push_back(isIdRecord(ty.kind()));
+  });
+  hashVec.erase(hashVec.begin(),
+                hashVec.begin() + precompDependency.getTypesCount());
+  assignGHashesFromVector(std::move(hashVec));
+}
+
+void UsePrecompSource::remapTpiWithGHashes(GHashState *g) {
+  // This object was compiled with /Yu, so process the corresponding
+  // precompiled headers object (/Yc) first. Some type indices in the current
+  // object are referencing data in the precompiled headers object, so we need
+  // both to be loaded.
+  if (Error e = mergeInPrecompHeaderObj()) {
+    typeMergingError = std::move(e);
+    return;
+  }
+
+  fillMapFromGHashes(g, indexMapStorage);
+  tpiMap = indexMapStorage;
+  ipiMap = indexMapStorage;
+  mergeUniqueTypeRecords(file->debugTypes,
+                         TypeIndex(precompDependency.getStartTypeIndex() +
+                                   precompDependency.getTypesCount()));
+}
+
+namespace {
+/// A concurrent hash table for global type hashing. It is based on this paper:
+/// Concurrent Hash Tables: Fast and General(?)!
+/// https://dl.acm.org/doi/10.1145/3309206
+///
+/// This hash table is meant to be used in two phases:
+/// 1. concurrent insertions
+/// 2. concurrent reads
+/// It does not support lookup, deletion, or rehashing. It uses linear probing.
+///
+/// The paper describes storing a key-value pair in two machine words.
+/// Generally, the values stored in this map are type indices, and we can use
+/// those values to recover the ghash key from a side table. This allows us to
+/// shrink the table entries further at the cost of some loads, and sidesteps
+/// the need for a 128 bit atomic compare-and-swap operation.
+///
+/// During insertion, a priority function is used to decide which insertion
+/// should be preferred. This ensures that the output is deterministic. For
+/// ghashing, lower tpiSrcIdx values (earlier inputs) are preferred.
+///
+class GHashCell;
+struct GHashTable {
+  GHashCell *table = nullptr;
+  uint32_t tableSize = 0;
+
+  GHashTable() = default;
+  ~GHashTable();
+
+  /// Initialize the table with the given size. Because the table cannot be
+  /// resized, the initial size of the table must be large enough to contain all
+  /// inputs, or insertion may not be able to find an empty cell.
+  void init(uint32_t newTableSize);
+
+  /// Insert the cell with the given ghash into the table. Return the insertion
+  /// position in the table. It is safe for the caller to store the insertion
+  /// position because the table cannot be resized.
+  uint32_t insert(GloballyHashedType ghash, GHashCell newCell);
+};
+
+/// A ghash table cell for deduplicating types from TpiSources.
+class GHashCell {
+  uint64_t data = 0;
+
+public:
+  GHashCell() = default;
+
+  // Construct data most to least significant so that sorting works well:
+  // - isItem
+  // - tpiSrcIdx
+  // - ghashIdx
+  // Add one to the tpiSrcIdx so that the 0th record from the 0th source has a
+  // non-zero representation.
+  GHashCell(bool isItem, uint32_t tpiSrcIdx, uint32_t ghashIdx)
+      : data((uint64_t(isItem) << 63U) | (uint64_t(tpiSrcIdx + 1) << 32ULL) |
+             ghashIdx) {
+    assert(tpiSrcIdx == getTpiSrcIdx() && "round trip failure");
+    assert(ghashIdx == getGHashIdx() && "round trip failure");
+  }
+
+  explicit GHashCell(uint64_t data) : data(data) {}
+
+  // The empty cell is all zeros.
+  bool isEmpty() const { return data == 0ULL; }
+
+  /// Extract the tpiSrcIdx.
+  uint32_t getTpiSrcIdx() const {
+    return ((uint32_t)(data >> 32U) & 0x7FFFFFFF) - 1;
+  }
+
+  /// Extract the index into the ghash array of the TpiSource.
+  uint32_t getGHashIdx() const { return (uint32_t)data; }
+
+  bool isItem() const { return data & (1ULL << 63U); }
+
+  /// Get the ghash key for this cell.
+  GloballyHashedType getGHash() const {
+    return TpiSource::instances[getTpiSrcIdx()]->ghashes[getGHashIdx()];
+  }
+
+  /// The priority function for the cell. The data is stored such that lower
+  /// tpiSrcIdx and ghashIdx values are preferred, which means that type record
+  /// from earlier sources are more likely to prevail.
+  friend inline bool operator<(const GHashCell &l, const GHashCell &r) {
+    return l.data < r.data;
+  }
+};
+} // namespace
+
+namespace lld {
+namespace coff {
+/// This type is just a wrapper around GHashTable with external linkage so it
+/// can be used from a header.
+struct GHashState {
+  GHashTable table;
+};
+} // namespace coff
+} // namespace lld
+
+GHashTable::~GHashTable() { delete[] table; }
+
+void GHashTable::init(uint32_t newTableSize) {
+  table = new GHashCell[newTableSize];
+  memset(table, 0, newTableSize * sizeof(GHashCell));
+  tableSize = newTableSize;
+}
+
+uint32_t GHashTable::insert(GloballyHashedType ghash, GHashCell newCell) {
+  assert(!newCell.isEmpty() && "cannot insert empty cell value");
+
+  // FIXME: The low bytes of SHA1 have low entropy for short records, which
+  // type records are. Swap the byte order for better entropy. A better ghash
+  // won't need this.
+  uint32_t startIdx =
+      ByteSwap_64(*reinterpret_cast<uint64_t *>(&ghash)) % tableSize;
+
+  // Do a linear probe starting at startIdx.
+  uint32_t idx = startIdx;
+  while (true) {
+    // Run a compare and swap loop. There are four cases:
+    // - cell is empty: CAS into place and return
+    // - cell has matching key, earlier priority: do nothing, return
+    // - cell has matching key, later priority: CAS into place and return
+    // - cell has non-matching key: hash collision, probe next cell
+    auto *cellPtr = reinterpret_cast<std::atomic<GHashCell> *>(&table[idx]);
+    GHashCell oldCell(cellPtr->load());
+    while (oldCell.isEmpty() || oldCell.getGHash() == ghash) {
+      // Check if there is an existing ghash entry with a higher priority
+      // (earlier ordering). If so, this is a duplicate, we are done.
+      if (!oldCell.isEmpty() && oldCell < newCell)
+        return idx;
+      // Either the cell is empty, or our value is higher priority. Try to
+      // compare and swap. If it succeeds, we are done.
+      if (cellPtr->compare_exchange_weak(oldCell, newCell))
+        return idx;
+      // If the CAS failed, check this cell again.
+    }
+
+    // Advance the probe. Wrap around to the beginning if we run off the end.
+    ++idx;
+    idx = idx == tableSize ? 0 : idx;
+    if (idx == startIdx) {
+      // If this becomes an issue, we could mark failure and rehash from the
+      // beginning with a bigger table. There is no difference between rehashing
+      // internally and starting over.
+      report_fatal_error("ghash table is full");
+    }
+  }
+  llvm_unreachable("left infloop");
+}
+
+TypeMerger::TypeMerger(llvm::BumpPtrAllocator &alloc)
+    : typeTable(alloc), idTable(alloc) {}
+
+TypeMerger::~TypeMerger() = default;
+
+void TypeMerger::mergeTypesWithGHash() {
+  // Load ghashes. Do type servers and PCH objects first.
+  {
+    ScopedTimer t1(loadGHashTimer);
+    parallelForEach(TpiSource::dependencySources,
+                    [&](TpiSource *source) { source->loadGHashes(); });
+    parallelForEach(TpiSource::objectSources,
+                    [&](TpiSource *source) { source->loadGHashes(); });
+  }
+
+  ScopedTimer t2(mergeGHashTimer);
+  GHashState ghashState;
+
+  // Estimate the size of hash table needed to deduplicate ghashes. This *must*
+  // be larger than the number of unique types, or hash table insertion may not
+  // be able to find a vacant slot. Summing the input types guarantees this, but
+  // it is a gross overestimate. The table size could be reduced to save memory,
+  // but it would require implementing rehashing, and this table is generally
+  // small compared to total memory usage, at eight bytes per input type record,
+  // and most input type records are larger than eight bytes.
+  size_t tableSize = 0;
+  for (TpiSource *source : TpiSource::instances)
+    tableSize += source->ghashes.size();
+
+  // Cap the table size so that we can use 32-bit cell indices. Type indices are
+  // also 32-bit, so this is an inherent PDB file format limit anyway.
+  tableSize = std::min(size_t(INT32_MAX), tableSize);
+  ghashState.table.init(static_cast<uint32_t>(tableSize));
+
+  // Insert ghashes in parallel. During concurrent insertion, we cannot observe
+  // the contents of the hash table cell, but we can remember the insertion
+  // position. Because the table does not rehash, the position will not change
+  // under insertion. After insertion is done, the value of the cell can be read
+  // to retreive the final PDB type index.
+  parallelForEachN(0, TpiSource::instances.size(), [&](size_t tpiSrcIdx) {
+    TpiSource *source = TpiSource::instances[tpiSrcIdx];
+    source->indexMapStorage.resize(source->ghashes.size());
+    for (uint32_t i = 0, e = source->ghashes.size(); i < e; i++) {
+      if (source->shouldOmitFromPdb(i)) {
+        source->indexMapStorage[i] = TypeIndex(SimpleTypeKind::NotTranslated);
+        continue;
+      }
+      GloballyHashedType ghash = source->ghashes[i];
+      bool isItem = source->isItemIndex.test(i);
+      uint32_t cellIdx =
+          ghashState.table.insert(ghash, GHashCell(isItem, tpiSrcIdx, i));
+
+      // Store the ghash cell index as a type index in indexMapStorage. Later
+      // we will replace it with the PDB type index.
+      source->indexMapStorage[i] = TypeIndex::fromArrayIndex(cellIdx);
+    }
+  });
+
+  // Collect all non-empty cells and sort them. This will implicitly assign
+  // destination type indices, and partition the entries into type records and
+  // item records. It arranges types in this order:
+  // - type records
+  //   - source 0, type 0...
+  //   - source 1, type 1...
+  // - item records
+  //   - source 0, type 1...
+  //   - source 1, type 0...
+  std::vector<GHashCell> entries;
+  for (const GHashCell &cell :
+       makeArrayRef(ghashState.table.table, tableSize)) {
+    if (!cell.isEmpty())
+      entries.push_back(cell);
+  }
+  parallelSort(entries, std::less<GHashCell>());
+  log(formatv("ghash table load factor: {0:p} (size {1} / capacity {2})\n",
+              double(entries.size()) / tableSize, entries.size(), tableSize));
+
+  // Find out how many type and item indices there are.
+  auto mid =
+      std::lower_bound(entries.begin(), entries.end(), GHashCell(true, 0, 0));
+  assert((mid == entries.end() || mid->isItem()) &&
+         (mid == entries.begin() || !std::prev(mid)->isItem()) &&
+         "midpoint is not midpoint");
+  uint32_t numTypes = std::distance(entries.begin(), mid);
+  uint32_t numItems = std::distance(mid, entries.end());
+  log("Tpi record count: " + Twine(numTypes));
+  log("Ipi record count: " + Twine(numItems));
+
+  // Make a list of the "unique" type records to merge for each tpi source. Type
+  // merging will skip indices not on this list. Store the destination PDB type
+  // index for these unique types in the tpiMap for each source. The entries for
+  // non-unique types will be filled in prior to type merging.
+  for (uint32_t i = 0, e = entries.size(); i < e; ++i) {
+    auto &cell = entries[i];
+    uint32_t tpiSrcIdx = cell.getTpiSrcIdx();
+    TpiSource *source = TpiSource::instances[tpiSrcIdx];
+    source->uniqueTypes.push_back(cell.getGHashIdx());
+
+    // Update the ghash table to store the destination PDB type index in the
+    // table.
+    uint32_t pdbTypeIndex = i < numTypes ? i : i - numTypes;
+    uint32_t ghashCellIndex =
+        source->indexMapStorage[cell.getGHashIdx()].toArrayIndex();
+    ghashState.table.table[ghashCellIndex] =
+        GHashCell(cell.isItem(), cell.getTpiSrcIdx(), pdbTypeIndex);
+  }
+
+  // In parallel, remap all types.
+  for_each(TpiSource::dependencySources, [&](TpiSource *source) {
+    source->remapTpiWithGHashes(&ghashState);
+  });
+  parallelForEach(TpiSource::objectSources, [&](TpiSource *source) {
+    source->remapTpiWithGHashes(&ghashState);
+  });
+
+  TpiSource::clearGHashes();
+}
+
+/// Given the index into the ghash table for a particular type, return the type
+/// index for that type in the output PDB.
+static TypeIndex loadPdbTypeIndexFromCell(GHashState *g,
+                                          uint32_t ghashCellIdx) {
+  GHashCell cell = g->table.table[ghashCellIdx];
+  return TypeIndex::fromArrayIndex(cell.getGHashIdx());
+}
+
+// Fill in a TPI or IPI index map using ghashes. For each source type, use its
+// ghash to lookup its final type index in the PDB, and store that in the map.
+void TpiSource::fillMapFromGHashes(GHashState *g,
+                                   SmallVectorImpl<TypeIndex> &mapToFill) {
+  for (size_t i = 0, e = ghashes.size(); i < e; ++i) {
+    TypeIndex fakeCellIndex = indexMapStorage[i];
+    if (fakeCellIndex.isSimple())
+      mapToFill[i] = fakeCellIndex;
+    else
+      mapToFill[i] = loadPdbTypeIndexFromCell(g, fakeCellIndex.toArrayIndex());
+  }
+}
+
+void TpiSource::clearGHashes() {
+  for (TpiSource *src : TpiSource::instances) {
+    if (src->ownedGHashes)
+      delete[] src->ghashes.data();
+    src->ghashes = {};
+    src->isItemIndex.clear();
+    src->uniqueTypes.clear();
+  }
+}

lld/COFF/Driver.cpp

 LinkerDriver *driver;
 
 bool link(ArrayRef<const char *> args, bool canExitEarly, raw_ostream &stdoutOS,
           raw_ostream &stderrOS) {
   lld::stdoutOS = &stdoutOS;
   lld::stderrOS = &stderrOS;
 
   errorHandler().cleanupCallback = []() {
+    TpiSource::clear();
     freeArena();
     ObjFile::instances.clear();
     PDBInputFile::instances.clear();
     ImportFile::instances.clear();
     BitcodeFile::instances.clear();
     memset(MergeChunk::instances, 0, sizeof(MergeChunk::instances));
-    TpiSource::clear();
     OutputSection::clear();
   };
 
   errorHandler().logName = args::getFilenameWithoutExe(args[0]);
   errorHandler().errorLimitExceededMsg =
       "too many errors emitted, stopping now"
       " (use /errorlimit:0 to see all errors)";
   errorHandler().exitEarly = canExitEarly;

lld/COFF/PDB.h

 
 namespace llvm {
 namespace codeview {
 union DebugInfo;
 }
 }
 
 namespace lld {
+class Timer;
+
 namespace coff {
 class OutputSection;
 class SectionChunk;
 class SymbolTable;
 
 void createPDB(SymbolTable *symtab,
                llvm::ArrayRef<OutputSection *> outputSections,
                llvm::ArrayRef<uint8_t> sectionTable,
                llvm::codeview::DebugInfo *buildId);
 
 llvm::Optional<std::pair<llvm::StringRef, uint32_t>>
 getFileLineCodeView(const SectionChunk *c, uint32_t addr);
+
+extern Timer loadGHashTimer;
+extern Timer mergeGHashTimer;
+
 } // namespace coff
 } // namespace lld
 
 #endif

lld/COFF/PDB.cpp

 using namespace lld;
 using namespace lld::coff;
 
 using llvm::object::coff_section;
 
 static ExitOnError exitOnErr;
 
 static Timer totalPdbLinkTimer("PDB Emission (Cumulative)", Timer::root());
-
+Timer lld::coff::loadGHashTimer("Global Type Hashing", totalPdbLinkTimer);
+Timer lld::coff::mergeGHashTimer("GHash Type Merging", totalPdbLinkTimer);
 static Timer addObjectsTimer("Add Objects", totalPdbLinkTimer);
 static Timer typeMergingTimer("Type Merging", addObjectsTimer);
 static Timer symbolMergingTimer("Symbol Merging", addObjectsTimer);
 static Timer publicsLayoutTimer("Publics Stream Layout", totalPdbLinkTimer);
 static Timer tpiStreamLayoutTimer("TPI Stream Layout", totalPdbLinkTimer);
 static Timer diskCommitTimer("Commit to Disk", totalPdbLinkTimer);
 
 namespace {
public:
   /// Link info for each import file in the symbol table into the PDB.
   void addImportFilesToPDB(ArrayRef<OutputSection *> outputSections);
 
   /// Link CodeView from a single object file into the target (output) PDB.
   /// When a precompiled headers object is linked, its TPI map might be provided
   /// externally.
   void addDebug(TpiSource *source);
 
-  bool mergeTypeRecords(TpiSource *source);
-
   void addDebugSymbols(TpiSource *source);
 
   void mergeSymbolRecords(TpiSource *source,
                           std::vector<ulittle32_t *> &stringTableRefs,
                           BinaryStreamRef symData);
 
   /// Add the section map and section contributions to the PDB.
   void addSections(ArrayRef<OutputSection *> outputSections,
static void addTypeInfo(pdb::TpiStreamBuilder &tpiBuilder,
   typeTable.ForEachRecord([&](TypeIndex ti, const CVType &type) {
     auto hash = pdb::hashTypeRecord(type);
     if (auto e = hash.takeError())
       fatal("type hashing error");
     tpiBuilder.addTypeRecord(type.RecordData, *hash);
   });
 }
 
-static bool remapTypeIndex(TypeIndex &ti, ArrayRef<TypeIndex> typeIndexMap) {
-  if (ti.isSimple())
-    return true;
-  if (ti.toArrayIndex() >= typeIndexMap.size())
-    return false;
-  ti = typeIndexMap[ti.toArrayIndex()];
-  return true;
-}
-
-static void remapTypesInSymbolRecord(ObjFile *file, SymbolKind symKind,
-                                     MutableArrayRef<uint8_t> recordBytes,
-                                     TpiSource *source,
-                                     ArrayRef<TiReference> typeRefs) {
-  MutableArrayRef<uint8_t> contents =
-      recordBytes.drop_front(sizeof(RecordPrefix));
-  for (const TiReference &ref : typeRefs) {
-    unsigned byteSize = ref.Count * sizeof(TypeIndex);
-    if (contents.size() < ref.Offset + byteSize)
-      fatal("symbol record too short");
-
-    // This can be an item index or a type index. Choose the appropriate map.
-    bool isItemIndex = ref.Kind == TiRefKind::IndexRef;
-    ArrayRef<TypeIndex> typeOrItemMap =
-        isItemIndex ? source->ipiMap : source->tpiMap;
-
-    MutableArrayRef<TypeIndex> tIs(
-        reinterpret_cast<TypeIndex *>(contents.data() + ref.Offset), ref.Count);
-    for (TypeIndex &ti : tIs) {
-      if (!remapTypeIndex(ti, typeOrItemMap)) {
-        log("ignoring symbol record of kind 0x" + utohexstr(symKind) + " in " +
-            file->getName() + " with bad " + (isItemIndex ? "item" : "type") +
-            " index 0x" + utohexstr(ti.getIndex()));
-        ti = TypeIndex(SimpleTypeKind::NotTranslated);
-        continue;
-      }
-    }
-  }
+static void addGHashTypeInfo(pdb::PDBFileBuilder &builder) {
+  // Start the TPI or IPI stream header.
+  builder.getTpiBuilder().setVersionHeader(pdb::PdbTpiV80);
+  builder.getIpiBuilder().setVersionHeader(pdb::PdbTpiV80);
+  for_each(TpiSource::instances, [&](TpiSource *source) {
+    builder.getTpiBuilder().addTypeRecords(source->mergedTpi.recs,
+                                           source->mergedTpi.recSizes,
+                                           source->mergedTpi.recHashes);
+    builder.getIpiBuilder().addTypeRecords(source->mergedIpi.recs,
+                                           source->mergedIpi.recSizes,
+                                           source->mergedIpi.recHashes);
+  });
 }
 
 static void
 recordStringTableReferenceAtOffset(MutableArrayRef<uint8_t> contents,
                                    uint32_t offset,
                                    std::vector<ulittle32_t *> &strTableRefs) {
   contents =
       contents.drop_front(offset).take_front(sizeof(support::ulittle32_t));

 static SymbolKind symbolKind(ArrayRef<uint8_t> recordData) {
   const RecordPrefix *prefix =
       reinterpret_cast<const RecordPrefix *>(recordData.data());
   return static_cast<SymbolKind>(uint16_t(prefix->RecordKind));
 }
 
 /// MSVC translates S_PROC_ID_END to S_END, and S_[LG]PROC32_ID to S_[LG]PROC32
 static void translateIdSymbols(MutableArrayRef<uint8_t> &recordData,
-                               TypeCollection &idTable) {
+                               TypeMerger &tMerger, TpiSource *source) {
   RecordPrefix *prefix = reinterpret_cast<RecordPrefix *>(recordData.data());
 
   SymbolKind kind = symbolKind(recordData);
 
   if (kind == SymbolKind::S_PROC_ID_END) {
     prefix->RecordKind = SymbolKind::S_END;
     return;
   }
if (kind == SymbolKind::S_GPROC32_ID || kind == SymbolKind::S_LPROC32_ID) {
     discoverTypeIndicesInSymbol(sym, refs);
     assert(refs.size() == 1);
     assert(refs.front().Count == 1);
 
     TypeIndex *ti =
         reinterpret_cast<TypeIndex *>(content.data() + refs[0].Offset);
     // `ti` is the index of a FuncIdRecord or MemberFuncIdRecord which lives in
     // the IPI stream, whose `FunctionType` member refers to the TPI stream.
-    // Note that LF_FUNC_ID and LF_MEMFUNC_ID have the same record layout, and
+    // Note that LF_FUNC_ID and LF_MFUNC_ID have the same record layout, and
     // in both cases we just need the second type index.
     if (!ti->isSimple() && !ti->isNoneType()) {
-      CVType funcIdData = idTable.getType(*ti);
+      if (config->debugGHashes) {
+        auto idToType = source->funcIdToType.find(*ti);
+        if (idToType == source->funcIdToType.end()) {
+          warn(formatv("S_[GL]PROC32_ID record in {0} refers to PDB item "
+                       "index {1:X} which is not a LF_[M]FUNC_ID record",
+                       source->file->getName(), ti->getIndex()));
+          *ti = TypeIndex(SimpleTypeKind::NotTranslated);
+        } else {
+          *ti = idToType->second;
+        }
+      } else {
+        CVType funcIdData = tMerger.getIDTable().getType(*ti);
         ArrayRef<uint8_t> tiBuf = funcIdData.data().slice(8, 4);
-      assert(tiBuf.size() == 4 && "corrupt LF_[MEM]FUNC_ID record");
+        assert(tiBuf.size() == 4 && "corrupt LF_[M]FUNC_ID record");
         *ti = *reinterpret_cast<const TypeIndex *>(tiBuf.data());
       }
+    }
 
     kind = (kind == SymbolKind::S_GPROC32_ID) ? SymbolKind::S_GPROC32
                                               : SymbolKind::S_LPROC32;
     prefix->RecordKind = uint16_t(kind);
   }
 }
 
 /// Copy the symbol record. In a PDB, symbol records must be 4 byte aligned.
cantFail(forEachCodeViewRecord<CVSymbol>(
           sym = CVSymbol(recordBytes);
         } else {
           // Otherwise, we can actually mutate the symbol directly, since we
           // copied it to apply relocations.
           recordBytes = makeMutableArrayRef(
               const_cast<uint8_t *>(sym.data().data()), sym.length());
         }
 
-        // Discover type index references in the record. Skip it if we don't
-        // know where they are.
-        SmallVector<TiReference, 32> typeRefs;
-        if (!discoverTypeIndicesInSymbol(sym, typeRefs)) {
-          log("ignoring unknown symbol record with kind 0x" +
-              utohexstr(sym.kind()));
+        // Re-map all the type index references.
+        if (!source->remapTypesInSymbolRecord(recordBytes)) {
+          log("error remapping types in symbol of kind 0x" +
+              utohexstr(sym.kind()) + ", ignoring");
           return Error::success();
         }
 
-        // Re-map all the type index references.
-        remapTypesInSymbolRecord(file, sym.kind(), recordBytes, source,
-                                 typeRefs);
-
         // An object file may have S_xxx_ID symbols, but these get converted to
         // "real" symbols in a PDB.
-        translateIdSymbols(recordBytes, tMerger.getIDTable());
+        translateIdSymbols(recordBytes, tMerger, source);
         sym = CVSymbol(recordBytes);
 
         // If this record refers to an offset in the object file's string table,
         // add that item to the global PDB string table and re-write the index.
         recordStringTableReferences(sym.kind(), recordBytes, stringTableRefs);
 
         // Fill in "Parent" and "End" fields by maintaining a stack of scopes.
         if (symbolOpensScope(sym.kind()))
getFileName(const DebugStringTableSubsectionRef &strings,
   uint32_t offset = iter->FileNameOffset;
   return strings.getString(offset);
 }
 
 void DebugSHandler::mergeInlineeLines(
     const DebugSubsectionRecord &inlineeSubsection) {
   DebugInlineeLinesSubsectionRef inlineeLines;
   exitOnErr(inlineeLines.initialize(inlineeSubsection.getRecordData()));
+  if (!source) {
+    warn("ignoring inlinee lines section in file that lacks type information");
+    return;
+  }
 
   // Remap type indices in inlinee line records in place.
   for (const InlineeSourceLine &line : inlineeLines) {
     TypeIndex &inlinee = *const_cast<TypeIndex *>(&line.Header->Inlinee);
-    if (!remapTypeIndex(inlinee, source->ipiMap)) {
+    if (!source->remapTypeIndex(inlinee, TiRefKind::IndexRef)) {
       log("bad inlinee line record in " + file.getName() +
           " with bad inlinee index 0x" + utohexstr(inlinee.getIndex()));
     }
   }
 
   // Add the modified inlinee line subsection directly.
   file.moduleDBI->addDebugSubsection(inlineeSubsection);
 }
static void warnUnusable(InputFile *f, Error e) {
   }
   auto msg = "Cannot use debug info for '" + toString(f) + "' [LNK4099]";
   if (e)
     warn(msg + "\n>>> failed to load reference " + toString(std::move(e)));
   else
     warn(msg);
 }
 
-bool PDBLinker::mergeTypeRecords(TpiSource *source) {
-  ScopedTimer t(typeMergingTimer);
-  // Before we can process symbol substreams from .debug$S, we need to process
-  // type information, file checksums, and the string table.  Add type info to
-  // the PDB first, so that we can get the map from object file type and item
-  // indices to PDB type and item indices.
-  if (Error e = source->mergeDebugT(&tMerger)) {
-    // If the .debug$T sections fail to merge, assume there is no debug info.
-    warnUnusable(source->file, std::move(e));
-    return false;
-  }
-  return true;
-}
-
 // Allocate memory for a .debug$S / .debug$F section and relocate it.
 static ArrayRef<uint8_t> relocateDebugChunk(SectionChunk &debugChunk) {
   uint8_t *buffer = bAlloc.Allocate<uint8_t>(debugChunk.getSize());
   assert(debugChunk.getOutputSectionIdx() == 0 &&
          "debug sections should not be in output sections");
   debugChunk.writeTo(buffer);
   return makeArrayRef(buffer, debugChunk.getSize());
 }
if (!secChunk || !secChunk->live)
       continue;
     pdb::SectionContrib sc = createSectionContrib(secChunk, modi);
     file->moduleDBI->setFirstSectionContrib(sc);
     break;
   }
 }
 
 void PDBLinker::addDebug(TpiSource *source) {
+  // Before we can process symbol substreams from .debug$S, we need to process
+  // type information, file checksums, and the string table. Add type info to
+  // the PDB first, so that we can get the map from object file type and item
+  // indices to PDB type and item indices.  If we are using ghashes, types have
+  // already been merged.
+  if (!config->debugGHashes) {
+    ScopedTimer t(typeMergingTimer);
+    if (Error e = source->mergeDebugT(&tMerger)) {
+      // If type merging failed, ignore the symbols.
+      warnUnusable(source->file, std::move(e));
+      return;
+    }
+  } else {
     // If type merging failed, ignore the symbols.
-  if (mergeTypeRecords(source))
-    addDebugSymbols(source);
+    if (source->typeMergingError) {
+      warnUnusable(source->file, std::move(source->typeMergingError));
+      return;
+    }
+  }
+
 }
 
 static pdb::BulkPublic createPublic(Defined *def) {
   pdb::BulkPublic pub;
   pub.Name = def->getName().data();
   pub.NameLen = def->getName().size();
 
   PublicSymFlags flags = PublicSymFlags::None;

 // TpiData.
 void PDBLinker::addObjectsToPDB() {
   ScopedTimer t1(addObjectsTimer);
 
   // Create module descriptors
   for_each(ObjFile::instances,
            [&](ObjFile *obj) { createModuleDBI(builder, obj); });
 
-  // Merge dependencies
-  TpiSource::forEachSource([&](TpiSource *source) {
-    if (source->isDependency())
-      addDebug(source);
-  });
+  // Reorder dependency type sources to come first.
+  TpiSource::sortDependencies();
 
-  // Merge regular and dependent OBJs
-  TpiSource::forEachSource([&](TpiSource *source) {
-    if (!source->isDependency())
-      addDebug(source);
-  });
+  // Merge type information from input files using global type hashing.
+  if (config->debugGHashes)
+    tMerger.mergeTypesWithGHash();
+
+  // Merge dependencies and then regular objects.
+  for_each(TpiSource::dependencySources,
+           [&](TpiSource *source) { addDebug(source); });
+  for_each(TpiSource::objectSources,
+           [&](TpiSource *source) { addDebug(source); });
 
   builder.getStringTableBuilder().setStrings(pdbStrTab);
   t1.stop();
 
   // Construct TPI and IPI stream contents.
   ScopedTimer t2(tpiStreamLayoutTimer);
+  // Collect all the merged types.
+  if (config->debugGHashes) {
+    addGHashTypeInfo(builder);
+  } else {
     addTypeInfo(builder.getTpiBuilder(), tMerger.getTypeTable());
     addTypeInfo(builder.getIpiBuilder(), tMerger.getIDTable());
+  }
   t2.stop();
 }
 
 void PDBLinker::addPublicsToPDB() {
   ScopedTimer t3(publicsLayoutTimer);
   // Compute the public symbols.
   auto &gsiBuilder = builder.getGsiBuilder();
   std::vector<pdb::BulkPublic> publics;
void PDBLinker::printStats() {
   auto print = [&](uint64_t v, StringRef s) {
     stream << format_decimal(v, 15) << " " << s << '\n';
   };
 
   print(ObjFile::instances.size(),
         "Input OBJ files (expanded from all cmd-line inputs)");
   print(TpiSource::countTypeServerPDBs(), "PDB type server dependencies");
   print(TpiSource::countPrecompObjs(), "Precomp OBJ dependencies");
-  print(tMerger.getTypeTable().size() + tMerger.getIDTable().size(),
-        "Merged TPI records");
+  print(builder.getTpiBuilder().getRecordCount(), "Merged TPI records");
+  print(builder.getIpiBuilder().getRecordCount(), "Merged IPI records");
   print(pdbStrTab.size(), "Output PDB strings");
   print(globalSymbols, "Global symbol records");
   print(moduleSymbols, "Module symbol records");
   print(publicSymbols, "Public symbol records");
 
   auto printLargeInputTypeRecs = [&](StringRef name,
                                      ArrayRef<uint32_t> recCounts,
                                      TypeCollection &records) {
if (!tsis.empty()) {
       stream
           << "Run llvm-pdbutil to print details about a particular record:\n";
       stream << formatv("llvm-pdbutil dump -{0}s -{0}-index {1:X} {2}\n",
                         (name == "TPI" ? "type" : "id"),
                         tsis.back().typeIndex.getIndex(), config->pdbPath);
     }
   };
 
+  if (!config->debugGHashes) {
+    // FIXME: Reimplement for ghash.
     printLargeInputTypeRecs("TPI", tMerger.tpiCounts, tMerger.getTypeTable());
     printLargeInputTypeRecs("IPI", tMerger.ipiCounts, tMerger.getIDTable());
+  }
 
   message(buffer);
 }
 
 void PDBLinker::addNatvisFiles() {
   for (StringRef file : config->natvisFiles) {
     ErrorOr<std::unique_ptr<MemoryBuffer>> dataOrErr =
         MemoryBuffer::getFile(file);
for (const LineNumberEntry &ln : entry.LineNumbers) {
       lineNumber = li.getStartLine();
     }
   }
   if (!nameIndex)
     return None;
   StringRef filename = exitOnErr(getFileName(cvStrTab, checksums, *nameIndex));
   return std::make_pair(filename, *lineNumber);
 }
+Number);
+}

lld/COFF/TypeMerger.h

 //===- TypeMerger.h ---------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_COFF_TYPEMERGER_H
 #define LLD_COFF_TYPEMERGER_H
 
 #include "Config.h"
-#include "llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h"
 #include "llvm/DebugInfo/CodeView/MergingTypeTableBuilder.h"
+#include "llvm/DebugInfo/CodeView/TypeHashing.h"
 #include "llvm/Support/Allocator.h"
+#include <atomic>
 
 namespace lld {
 namespace coff {
 
+using llvm::codeview::GloballyHashedType;
+using llvm::codeview::TypeIndex;
+
+struct GHashState;
+
 class TypeMerger {
 public:
-  TypeMerger(llvm::BumpPtrAllocator &alloc)
-      : typeTable(alloc), idTable(alloc), globalTypeTable(alloc),
-        globalIDTable(alloc) {}
+  TypeMerger(llvm::BumpPtrAllocator &alloc);
+
+  ~TypeMerger();
 
   /// Get the type table or the global type table if /DEBUG:GHASH is enabled.
   inline llvm::codeview::TypeCollection &getTypeTable() {
-    if (config->debugGHashes)
-      return globalTypeTable;
+    assert(!config->debugGHashes);
     return typeTable;
   }
 
   /// Get the ID table or the global ID table if /DEBUG:GHASH is enabled.
   inline llvm::codeview::TypeCollection &getIDTable() {
-    if (config->debugGHashes)
-      return globalIDTable;
+    assert(!config->debugGHashes);
     return idTable;
   }
 
+  /// Use global hashes to eliminate duplicate types and identify unique type
+  /// indices in each TpiSource.
+  void mergeTypesWithGHash();
+
   /// Type records that will go into the PDB TPI stream.
   llvm::codeview::MergingTypeTableBuilder typeTable;
 
   /// Item records that will go into the PDB IPI stream.
   llvm::codeview::MergingTypeTableBuilder idTable;
 
-  /// Type records that will go into the PDB TPI stream (for /DEBUG:GHASH)
-  llvm::codeview::GlobalTypeTableBuilder globalTypeTable;
-
-  /// Item records that will go into the PDB IPI stream (for /DEBUG:GHASH)
-  llvm::codeview::GlobalTypeTableBuilder globalIDTable;
-
   // When showSummary is enabled, these are histograms of TPI and IPI records
   // keyed by type index.
   SmallVector<uint32_t, 0> tpiCounts;
   SmallVector<uint32_t, 0> ipiCounts;
 };
 
 } // namespace coff
 } // namespace lld
 
 #endif

lld/include/lld/Common/ErrorHandler.h

 }
 
 template <class T> T check(Expected<T> e) {
   if (!e)
     fatal(llvm::toString(e.takeError()));
   return std::move(*e);
 }
 
+// Don't move from Expected wrappers around references.
+template <class T> T &check(Expected<T &> e) {
+  if (!e)
+    fatal(llvm::toString(e.takeError()));
+  return *e;
+}
+
 template <class T>
 T check2(ErrorOr<T> e, llvm::function_ref<std::string()> prefix) {
   if (auto ec = e.getError())
     fatal(prefix() + ": " + ec.message());
   return std::move(*e);
 }
 
 template <class T>

lld/test/COFF/pdb-global-hashes.test

 RUN: yaml2obj %p/Inputs/pdb-hashes-1.yaml -o %t.1.obj
 RUN: yaml2obj %p/Inputs/pdb-hashes-2.yaml -o %t.2.obj
 RUN: yaml2obj %p/Inputs/pdb-hashes-2-missing.yaml -o %t.2.missing.obj
 RUN: lld-link /debug %t.1.obj %t.2.obj /entry:main /nodefaultlib /PDB:%t.nohash.pdb
-RUN: lld-link /debug:ghash %t.1.obj %t.2.obj /entry:main /nodefaultlib /PDB:%t.hash.pdb
+RUN: lld-link /debug:ghash -verbose %t.1.obj %t.2.obj /entry:main /nodefaultlib /PDB:%t.hash.pdb
 RUN: lld-link /debug:ghash %t.1.obj %t.2.missing.obj /entry:main /nodefaultlib /PDB:%t.mixed.pdb
 RUN: llvm-pdbutil dump -types -ids -dont-resolve-forward-refs %t.nohash.pdb | FileCheck %s
 RUN: llvm-pdbutil dump -types -ids -dont-resolve-forward-refs %t.hash.pdb | FileCheck %s
 RUN: llvm-pdbutil dump -types -ids -dont-resolve-forward-refs %t.mixed.pdb | FileCheck %s
 
 ; These object files were generated via the following inputs and commands:
 ; ----------------------------------------------
 ; // obj.h

lld/test/COFF/pdb-procid-remapping.test

-# RUN: yaml2obj %p/Inputs/pdb1.yaml -o %t1.obj
-# RUN: yaml2obj %p/Inputs/pdb2.yaml -o %t2.obj
+# RUN: yaml2obj < %p/Inputs/pdb1.yaml > %t1.obj
+# RUN: yaml2obj < %p/Inputs/pdb2.yaml > %t2.obj
+
 # RUN: lld-link /debug /pdb:%t.pdb /dll /out:%t.dll /entry:main /nodefaultlib \
 # RUN:   %t1.obj %t2.obj
+# RUN: llvm-pdbutil dump -symbols %t.pdb | FileCheck %s
 
+# RUN: lld-link /debug /debug:ghash /pdb:%t.pdb /dll /out:%t.dll /entry:main /nodefaultlib \
+# RUN:   %t1.obj %t2.obj
 # RUN: llvm-pdbutil dump -symbols %t.pdb | FileCheck %s
 
 CHECK:                                Symbols
 CHECK-NEXT: ============================================================
 CHECK-LABEL:    Mod 0000 |
 CHECK:                92 | S_GPROC32 [size = 44] `main`
 CHECK-NEXT:                parent = 0, end = 168, addr = 0001:0000, code size = 14
 CHECK-NEXT:                type = `0x1004 (int (<no type>))`, debug start = 4, debug end = 9, flags = none

lld/test/COFF/pdb-type-server-missing.yaml

 # This is an object compiled with /Zi (see the LF_TYPESERVER2 record) without an
 # adjacent type server PDB. Test that LLD fails gracefully on it.
 # Also try linking another OBJ with a reference to the same PDB
 
 # RUN: yaml2obj %s -o %t1.obj
 # RUN: yaml2obj %p/Inputs/pdb-type-server-missing-2.yaml -o %t2.obj
 # RUN: lld-link %t1.obj %t2.obj -out:%t.exe -debug -pdb:%t.pdb -nodefaultlib -entry:main 2>&1 | FileCheck %s -check-prefix=WARN
+# RUN: lld-link %t1.obj %t2.obj -out:%t.exe -debug:ghash -pdb:%t.pdb -nodefaultlib -entry:main 2>&1 | FileCheck %s -check-prefix=WARN
 # RUN: lld-link %t1.obj %t2.obj -out:%t.exe -debug -pdb:%t.pdb -nodefaultlib -entry:main /ignore:4099 2>&1 | FileCheck %s -check-prefix=IGNORE -allow-empty
 # RUN: not lld-link %t1.obj %t2.obj -out:%t.exe -debug -pdb:%t.pdb -nodefaultlib -entry:main /WX 2>&1 | FileCheck %s -check-prefix=ERR
 # RUN: lld-link %t1.obj %t2.obj -out:%t.exe -debug -pdb:%t.pdb -nodefaultlib -entry:main /ignore:4099 /WX 2>&1 | FileCheck %s -check-prefix=IGNORE-ERR -allow-empty
 
 # WARN: warning: Cannot use debug info for '{{.*}}.obj' [LNK4099]
 # WARN-NEXT: {{N|n}}o such file or directory
 
 # IGNORE-NOT: warning: Cannot use debug info for '{{.*}}.obj' [LNK4099]

lld/test/COFF/pdb-type-server-simple.test

 $ cl -c a.c b.c -Zi -Fdts.pdb
 
 $ lld-link a.obj b.obj -debug -entry:main -nodefaultlib -out:t.exe
 
 RUN: rm -rf %t && mkdir -p %t && cd %t
 RUN: yaml2obj %S/Inputs/pdb-type-server-simple-a.yaml -o a.obj
 RUN: yaml2obj %S/Inputs/pdb-type-server-simple-b.yaml -o b.obj
 RUN: llvm-pdbutil yaml2pdb %S/Inputs/pdb-type-server-simple-ts.yaml -pdb ts.pdb
-RUN: lld-link a.obj b.obj -entry:main -debug -out:t.exe -pdb:t.pdb -nodefaultlib /summary | FileCheck %s -check-prefix SUMMARY
+RUN: lld-link a.obj b.obj -entry:main -debug -out:t.exe -pdb:t.pdb -nodefaultlib -summary | FileCheck %s -check-prefix SUMMARY
+RUN: llvm-pdbutil dump -symbols -types -ids -globals %t/t.pdb | FileCheck %s
+
+Re-run with /DEBUG:GHASH
+RUN: lld-link a.obj b.obj -entry:main -debug:ghash -out:t.exe -pdb:t.pdb -nodefaultlib -summary -verbose
 RUN: llvm-pdbutil dump -symbols -types -ids -globals %t/t.pdb | FileCheck %s
 
 
 CHECK-LABEL: Types (TPI Stream)
 CHECK: ============================================================
 
 CHECK:   [[FOO_DECL:[^ ]*]] | LF_STRUCTURE [size = 36] `Foo`
 

 CHECK:      200 | S_BUILDINFO [size = 8] BuildId = `[[B_BUILD]]`
 CHECK-LABEL:   Mod 0002 | `* Linker *`:
 
 SUMMARY:                                     Summary
 SUMMARY-NEXT: --------------------------------------------------------------------------------
 SUMMARY-NEXT:               2 Input OBJ files (expanded from all cmd-line inputs)
 SUMMARY-NEXT:               1 PDB type server dependencies
 SUMMARY-NEXT:               0 Precomp OBJ dependencies
-SUMMARY-NEXT:              25 Merged TPI records
+SUMMARY-NEXT:               9 Merged TPI records
+SUMMARY-NEXT:              16 Merged IPI records
 SUMMARY-NEXT:               3 Output PDB strings
 SUMMARY-NEXT:               4 Global symbol records
 SUMMARY-NEXT:              14 Module symbol records
 SUMMARY-NEXT:               2 Public symbol records
 
 SUMMARY:      Top 10 types responsible for the most TPI input:
 SUMMARY-NEXT:        index     total bytes   count     size
 SUMMARY-NEXT:       0x1006:             36 =     1 *     36
 SUMMARY: Run llvm-pdbutil to print details about a particular record:
 SUMMARY-NEXT: llvm-pdbutil dump -types -type-index 0x1006 t.pdb
 
 SUMMARY:      Top 10 types responsible for the most IPI input:
 SUMMARY-NEXT:        index     total bytes   count     size
 SUMMARY-NEXT:       0x1006:            256 =     1 *    256
 SUMMARY: Run llvm-pdbutil to print details about a particular record:
 SUMMARY-NEXT: llvm-pdbutil dump -ids -id-index 0x1006 t.pdb

lld/test/COFF/precomp-link.test

 RUN: lld-link %S/Inputs/precomp-a.obj %S/Inputs/precomp-b.obj %S/Inputs/precomp.obj /nodefaultlib /entry:main /debug /pdb:%t.pdb /out:%t.exe /opt:ref /opt:icf /summary | FileCheck %s -check-prefix SUMMARY
 RUN: llvm-pdbutil dump -types %t.pdb | FileCheck %s
 
 RUN: lld-link %S/Inputs/precomp.obj %S/Inputs/precomp-a.obj %S/Inputs/precomp-b.obj /nodefaultlib /entry:main /debug /pdb:%t.pdb /out:%t.exe /opt:ref /opt:icf
 RUN: llvm-pdbutil dump -types %t.pdb | FileCheck %s
 
 RUN: lld-link %S/Inputs/precomp-a.obj %S/Inputs/precomp-invalid.obj %S/Inputs/precomp.obj /nodefaultlib /entry:main /debug /pdb:%t.pdb /out:%t.exe /opt:ref /opt:icf 2>&1 | FileCheck %s -check-prefix FAILURE
+RUN: lld-link %S/Inputs/precomp-a.obj %S/Inputs/precomp-invalid.obj %S/Inputs/precomp.obj /nodefaultlib /entry:main /debug:ghash /pdb:%t.pdb /out:%t.exe /opt:ref /opt:icf 2>&1 | FileCheck %s -check-prefix FAILURE
 
 FIXME: The following RUN line should fail, regardless of whether debug info is
 enabled or not. Normally this would result in an error due to missing _PchSym_
 references, but SymbolTable.cpp suppresses such errors. MSVC seems to have a
 special case for those symbols and it emits the LNK2011 error.
 
 RUN: lld-link %S/Inputs/precomp-a.obj %S/Inputs/precomp-b.obj /nodefaultlib /entry:main /debug /pdb:%t.pdb /out:%t.exe /opt:ref /opt:icf 2>&1 | FileCheck %s -check-prefix FAILURE-MISSING-PRECOMPOBJ
 

 FAILURE-DUP-SIGNATURE: error: a PCH object with the same signature has already been provided ({{.*precomp.obj and .*precomp-dup.obj.*}})
 
 
 CHECK: Types (TPI Stream)
 CHECK-NOT: LF_PRECOMP
 CHECK-NOT: LF_ENDPRECOMP
 
 
+Re-run with ghash. Eventually, perhaps this will be the default.
+
+RUN: lld-link %S/Inputs/precomp-a.obj %S/Inputs/precomp-b.obj %S/Inputs/precomp.obj /nodefaultlib /entry:main /debug /debug:ghash /pdb:%t.pdb /out:%t.exe /opt:ref /opt:icf /summary | FileCheck %s -check-prefix SUMMARY
+RUN: llvm-pdbutil dump -types %t.pdb | FileCheck %s
+
+
 SUMMARY:                                     Summary
 SUMMARY-NEXT: --------------------------------------------------------------------------------
 SUMMARY-NEXT:               3 Input OBJ files (expanded from all cmd-line inputs)
 SUMMARY-NEXT:               0 PDB type server dependencies
 SUMMARY-NEXT:               1 Precomp OBJ dependencies
-SUMMARY-NEXT:            1044 Merged TPI records
+SUMMARY-NEXT:            874 Merged TPI records
+SUMMARY-NEXT:            170 Merged IPI records
 SUMMARY-NEXT:               5 Output PDB strings
 SUMMARY-NEXT:             167 Global symbol records
 SUMMARY-NEXT:              20 Module symbol records
 SUMMARY-NEXT:               3 Public symbol records
 
 // precomp.h
 #pragma once
 int Function(char A);

lld/test/COFF/s_udt.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-pc-windows-msvc < %s > %t.obj
 # RUN: lld-link /DEBUG:FULL /nodefaultlib /entry:main %t.obj /PDB:%t.pdb /OUT:%t.exe
 # RUN: llvm-pdbutil dump -types -globals -symbols -modi=0 %t.pdb | FileCheck %s
+# RUN: lld-link /DEBUG:FULL /debug:ghash /nodefaultlib /entry:main %t.obj /PDB:%t.pdb /OUT:%t.exe
+# RUN: llvm-pdbutil dump -types -globals -symbols -modi=0 %t.pdb | FileCheck %s
 
 # CHECK:                               Types (TPI Stream)
 # CHECK-NEXT: ============================================================
 # CHECK:      0x1003 | LF_STRUCTURE [size = 44] `Struct`
 # CHECK-NEXT:          unique name: `.?AUStruct@@`
 # CHECK-NEXT:          vtable: <no type>, base list: <no type>, field list: <no type>
 # CHECK-NEXT:          options: forward ref (-> 0x1006) | has unique name, sizeof 0
 # CHECK-NEXT: 0x1004 | LF_POINTER [size = 12]

llvm/include/llvm/DebugInfo/CodeView/TypeHashing.h

struct GloballyHashedType {
   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; }
 
+  friend inline bool operator==(const GloballyHashedType &L,
+                                const GloballyHashedType &R) {
+    return L.Hash == R.Hash;
+  }
+
+  friend inline bool operator!=(const GloballyHashedType &L,
+                                const GloballyHashedType &R) {
+    return !(L.Hash == R.Hash);
+  }
+
   /// 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);
 
template <> struct DenseMapInfo<codeview::GloballyHashedType> {
   static codeview::GloballyHashedType getTombstoneKey() { return Tombstone; }
 
   static unsigned getHashValue(codeview::GloballyHashedType Val) {
     return *reinterpret_cast<const unsigned *>(Val.Hash.data());
   }
 
   static bool isEqual(codeview::GloballyHashedType LHS,
                       codeview::GloballyHashedType RHS) {
-    return LHS.Hash == RHS.Hash;
+    return LHS == RHS;
   }
 };
 
 template <> struct format_provider<codeview::LocallyHashedType> {
 public:
   static void format(const codeview::LocallyHashedType &V,
                      llvm::raw_ostream &Stream, StringRef Style) {
     write_hex(Stream, V.Hash, HexPrintStyle::Upper, 8);

llvm/include/llvm/DebugInfo/CodeView/TypeIndex.h

public:
   void setIndex(uint32_t I) { Index = I; }
   bool isSimple() const { return Index < FirstNonSimpleIndex; }
   bool isDecoratedItemId() const { return !!(Index & DecoratedItemIdMask); }
 
   bool isNoneType() const { return *this == None(); }
 
   uint32_t toArrayIndex() const {
     assert(!isSimple());
-    return getIndex() - FirstNonSimpleIndex;
+    return (getIndex() & ~DecoratedItemIdMask) - FirstNonSimpleIndex;
   }
 
   static TypeIndex fromArrayIndex(uint32_t Index) {
     return TypeIndex(Index + FirstNonSimpleIndex);
   }
 
+  static TypeIndex fromDecoratedArrayIndex(bool IsItem, uint32_t Index) {
+    return TypeIndex((Index + FirstNonSimpleIndex) |
+                     (IsItem ? DecoratedItemIdMask : 0));
+  }
+
+  TypeIndex removeDecoration() {
+    return TypeIndex(Index & ~DecoratedItemIdMask);
+  }
+
   SimpleTypeKind getSimpleKind() const {
     assert(isSimple());
     return static_cast<SimpleTypeKind>(Index & SimpleKindMask);
   }
 
   SimpleTypeMode getSimpleMode() const {
     assert(isSimple());
     return static_cast<SimpleTypeMode>(Index & SimpleModeMask);

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

public:
   explicit TpiStreamBuilder(msf::MSFBuilder &Msf, uint32_t StreamIdx);
   ~TpiStreamBuilder();
 
   TpiStreamBuilder(const TpiStreamBuilder &) = delete;
   TpiStreamBuilder &operator=(const TpiStreamBuilder &) = delete;
 
   void setVersionHeader(PdbRaw_TpiVer Version);
   void addTypeRecord(ArrayRef<uint8_t> Type, Optional<uint32_t> Hash);
+  void addTypeRecords(ArrayRef<uint8_t> Types, ArrayRef<uint16_t> Sizes,
+                      ArrayRef<uint32_t> Hashes);
 
   Error finalizeMsfLayout();
 
-  uint32_t getRecordCount() const { return TypeRecords.size(); }
+  uint32_t getRecordCount() const { return TypeRecordCount; }
 
   Error commit(const msf::MSFLayout &Layout, WritableBinaryStreamRef Buffer);
 
   uint32_t calculateSerializedLength();
 
 private:
+  void updateTypeIndexOffsets(ArrayRef<uint16_t> Sizes);
+
   uint32_t calculateHashBufferSize() const;
   uint32_t calculateIndexOffsetSize() const;
   Error finalize();
 
   msf::MSFBuilder &Msf;
   BumpPtrAllocator &Allocator;
 
+  uint32_t TypeRecordCount = 0;
   size_t TypeRecordBytes = 0;
 
   PdbRaw_TpiVer VerHeader = PdbRaw_TpiVer::PdbTpiV80;
-  std::vector<ArrayRef<uint8_t>> TypeRecords;
+  std::vector<ArrayRef<uint8_t>> TypeRecBuffers;
   std::vector<uint32_t> TypeHashes;
   std::vector<codeview::TypeIndexOffset> TypeIndexOffsets;
   uint32_t HashStreamIndex = kInvalidStreamIndex;
   std::unique_ptr<BinaryByteStream> HashValueStream;
 
   const TpiStreamHeader *Header;
   uint32_t Idx;
 };
 }
 }
 
 #endif

llvm/lib/DebugInfo/CodeView/RecordName.cpp

 //===- RecordName.cpp ----------------------------------------- *- C++ --*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/CodeView/RecordName.h"
 
 #include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/DebugInfo/CodeView/CVSymbolVisitor.h"
 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
 #include "llvm/DebugInfo/CodeView/SymbolRecordMapping.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
 #include "llvm/Support/FormatVariadic.h"
 
 using namespace llvm;
 using namespace llvm::codeview;
Error TypeNameComputer::visitKnownRecord(CVRecord<TypeLeafKind> &CVR,
   return Error::success();
 }
 
 Error TypeNameComputer::visitKnownRecord(CVType &CVR, ArgListRecord &Args) {
   auto Indices = Args.getIndices();
   uint32_t Size = Indices.size();
   Name = "(";
   for (uint32_t I = 0; I < Size; ++I) {
-    assert(Indices[I] < CurrentTypeIndex);
-
+    if (Indices[I] < CurrentTypeIndex)
       Name.append(Types.getTypeName(Indices[I]));
+    else
+      Name.append("<unknown 0x" + utohexstr(Indices[I].getIndex()) + ">");
     if (I + 1 != Size)
       Name.append(", ");
   }
   Name.push_back(')');
   return Error::success();
 }
 
 Error TypeNameComputer::visitKnownRecord(CVType &CVR,

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

 #include "llvm/Support/BinaryByteStream.h"
 #include "llvm/Support/BinaryStreamArray.h"
 #include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/BinaryStreamWriter.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include <algorithm>
 #include <cstdint>
+#include <numeric>
 
 using namespace llvm;
 using namespace llvm::msf;
 using namespace llvm::pdb;
 using namespace llvm::support;
 
 TpiStreamBuilder::TpiStreamBuilder(MSFBuilder &Msf, uint32_t StreamIdx)
     : Msf(Msf), Allocator(Msf.getAllocator()), Header(nullptr), Idx(StreamIdx) {
 }
 
 TpiStreamBuilder::~TpiStreamBuilder() = default;
 
 void TpiStreamBuilder::setVersionHeader(PdbRaw_TpiVer Version) {
   VerHeader = Version;
 }
 
-void TpiStreamBuilder::addTypeRecord(ArrayRef<uint8_t> Record,
-                                     Optional<uint32_t> Hash) {
+void TpiStreamBuilder::updateTypeIndexOffsets(ArrayRef<uint16_t> Sizes) {
   // If we just crossed an 8KB threshold, add a type index offset.
-  assert(((Record.size() & 3) == 0) &&
-         "The type record's size is not a multiple of 4 bytes which will "
-         "cause misalignment in the output TPI stream!");
-  size_t NewSize = TypeRecordBytes + Record.size();
+  for (uint16_t Size : Sizes) {
+    size_t NewSize = TypeRecordBytes + Size;
     constexpr size_t EightKB = 8 * 1024;
-  if (NewSize / EightKB > TypeRecordBytes / EightKB || TypeRecords.empty()) {
+    if (NewSize / EightKB > TypeRecordBytes / EightKB || TypeRecordCount == 0) {
       TypeIndexOffsets.push_back(
           {codeview::TypeIndex(codeview::TypeIndex::FirstNonSimpleIndex +
-                             TypeRecords.size()),
+                               TypeRecordCount),
            ulittle32_t(TypeRecordBytes)});
     }
+    ++TypeRecordCount;
     TypeRecordBytes = NewSize;
+  }
+}
 
-  TypeRecords.push_back(Record);
+void TpiStreamBuilder::addTypeRecord(ArrayRef<uint8_t> Record,
+                                     Optional<uint32_t> Hash) {
+  assert(((Record.size() & 3) == 0) &&
+         "The type record's size is not a multiple of 4 bytes which will "
+         "cause misalignment in the output TPI stream!");
+  assert(Record.size() <= codeview::MaxRecordLength);
+  uint16_t OneSize = (uint16_t)Record.size();
+  updateTypeIndexOffsets(makeArrayRef(&OneSize, 1));
+
+  TypeRecBuffers.push_back(Record);
+  // FIXME: Require it.
   if (Hash)
     TypeHashes.push_back(*Hash);
 }
 
+void TpiStreamBuilder::addTypeRecords(ArrayRef<uint8_t> Types,
+                                      ArrayRef<uint16_t> Sizes,
+                                      ArrayRef<uint32_t> Hashes) {
+  // Ignore empty type buffers. There should be no hashes or sizes in this case.
+  if (Types.empty()) {
+    assert(Sizes.empty() && Hashes.empty());
+    return;
+  }
+
+  assert(((Types.size() & 3) == 0) &&
+         "The type record's size is not a multiple of 4 bytes which will "
+         "cause misalignment in the output TPI stream!");
+  assert(Sizes.size() == Hashes.size() && "sizes and hashes should be in sync");
+  assert(std::accumulate(Sizes.begin(), Sizes.end(), 0U) == Types.size() &&
+         "sizes of type records should sum to the size of the types");
+  updateTypeIndexOffsets(Sizes);
+
+  TypeRecBuffers.push_back(Types);
+  TypeHashes.insert(TypeHashes.end(), Hashes.begin(), Hashes.end());
+}
+
 Error TpiStreamBuilder::finalize() {
   if (Header)
     return Error::success();
 
   TpiStreamHeader *H = Allocator.Allocate<TpiStreamHeader>();
 
-  uint32_t Count = TypeRecords.size();
-
   H->Version = VerHeader;
   H->HeaderSize = sizeof(TpiStreamHeader);
   H->TypeIndexBegin = codeview::TypeIndex::FirstNonSimpleIndex;
-  H->TypeIndexEnd = H->TypeIndexBegin + Count;
+  H->TypeIndexEnd = H->TypeIndexBegin + TypeRecordCount;
   H->TypeRecordBytes = TypeRecordBytes;
 
   H->HashStreamIndex = HashStreamIndex;
   H->HashAuxStreamIndex = kInvalidStreamIndex;
   H->HashKeySize = sizeof(ulittle32_t);
   H->NumHashBuckets = MaxTpiHashBuckets - 1;
 
   // Recall that hash values go into a completely different stream identified by
Error TpiStreamBuilder::finalize() {
   return Error::success();
 }
 
 uint32_t TpiStreamBuilder::calculateSerializedLength() {
   return sizeof(TpiStreamHeader) + TypeRecordBytes;
 }
 
 uint32_t TpiStreamBuilder::calculateHashBufferSize() const {
-  assert((TypeRecords.size() == TypeHashes.size() || TypeHashes.empty()) &&
+  assert((TypeRecordCount == TypeHashes.size() || TypeHashes.empty()) &&
          "either all or no type records should have hashes");
   return TypeHashes.size() * sizeof(ulittle32_t);
 }
 
 uint32_t TpiStreamBuilder::calculateIndexOffsetSize() const {
   return TypeIndexOffsets.size() * sizeof(codeview::TypeIndexOffset);
 }
 
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 : TypeRecBuffers) {
     assert(!Rec.empty() && "Attempting to write an empty type record shifts "
                            "all offsets in the TPI stream!");
     assert(((Rec.size() & 3) == 0) &&
            "The type record's size is not a multiple of 4 bytes which will "
            "cause misalignment in the output TPI stream!");
     if (auto EC = Writer.writeBytes(Rec))
       return EC;
   }