[PDB] Make our PDBs look more like MS PDBs.

When investigating bugs in PDB generation, the first step is
often to do the same link with link.exe and then compare PDBs.

But comparing PDBs is hard because two completely different byte
sequences can both be correct, so it hampers the investigation when
you also have to spend time figuring out not just which bytes are
different, but also if the difference is meaningful.

This patch fixes a couple of cases related to string table emission,
hash table emission, and the order in which we emit strings that
makes more of our bytes the same as the bytes generated by MS PDBs.

Differential Revision: https://reviews.llvm.org/D44810

llvm-svn: 328348

1 files changed, 61 insertions, 6 deletions

diff --git a/llvm/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp b/llvm/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp
index 5020423..0975d9e 100644
--- a/llvm/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp
@@ -15,6 +15,8 @@
 #include "llvm/Support/BinaryStreamWriter.h"
 #include "llvm/Support/Endian.h"
 
+#include <map>
+
 using namespace llvm;
 using namespace llvm::msf;
 using namespace llvm::support;
@@ -33,13 +35,66 @@ StringRef PDBStringTableBuilder::getStringForId(uint32_t Id) const {
   return Strings.getStringForId(Id);
 }
 
+// This is a precomputed list of Buckets given the specified number of
+// strings.  Matching the reference algorithm exactly is not strictly
+// necessary for correctness, but it helps when comparing LLD's PDBs with
+// Microsoft's PDBs so as to eliminate superfluous differences.
+static std::map<uint32_t, uint32_t> StringsToBuckets = {
+    {1, 2},
+    {2, 4},
+    {4, 7},
+    {6, 11},
+    {9, 17},
+    {13, 26},
+    {20, 40},
+    {31, 61},
+    {46, 92},
+    {70, 139},
+    {105, 209},
+    {157, 314},
+    {236, 472},
+    {355, 709},
+    {532, 1064},
+    {799, 1597},
+    {1198, 2396},
+    {1798, 3595},
+    {2697, 5393},
+    {4045, 8090},
+    {6068, 12136},
+    {9103, 18205},
+    {13654, 27308},
+    {20482, 40963},
+    {30723, 61445},
+    {46084, 92168},
+    {69127, 138253},
+    {103690, 207380},
+    {155536, 311071},
+    {233304, 466607},
+    {349956, 699911},
+    {524934, 1049867},
+    {787401, 1574801},
+    {1181101, 2362202},
+    {1771652, 3543304},
+    {2657479, 5314957},
+    {3986218, 7972436},
+    {5979328, 11958655},
+    {8968992, 17937983},
+    {13453488, 26906975},
+    {20180232, 40360463},
+    {30270348, 60540695},
+    {45405522, 90811043},
+    {68108283, 136216565},
+    {102162424, 204324848},
+    {153243637, 306487273},
+    {229865455, 459730910},
+    {344798183, 689596366},
+    {517197275, 1034394550},
+    {775795913, 1551591826}};
+
 static uint32_t computeBucketCount(uint32_t NumStrings) {
-  // The /names stream is basically an on-disk open-addressing hash table.
-  // Hash collisions are resolved by linear probing. We cannot make
-  // utilization 100% because it will make the linear probing extremely
-  // slow. But lower utilization wastes disk space. As a reasonable
-  // load factor, we choose 80%. We need +1 because slot 0 is reserved.
-  return (NumStrings + 1) * 1.25;
+  auto Entry = StringsToBuckets.lower_bound(NumStrings);
+  assert(Entry != StringsToBuckets.end());
+  return Entry->second;
 }
 
 uint32_t PDBStringTableBuilder::calculateHashTableSize() const {