[llvm-dwp] Implement the required on-disk probed hash table

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@254770 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/test/tools/llvm-dwp/X86/simple.test b/test/tools/llvm-dwp/X86/simple.test
index 3c9795fbb9342cbcd73cbec3ed158b352d5aa883..2ed8e611844a4125a7a32ff93f6be93a842b32b1 100644 (file)
--- a/test/tools/llvm-dwp/X86/simple.test
+++ b/test/tools/llvm-dwp/X86/simple.test
@@ -47,8 +47,8 @@ CHECK: .debug_cu_index contents:
 Ensure only the relevant/contained sections are included in the table:
 CHECK: Index Signature          INFO                     ABBREV                   LINE                     STR_OFFSETS
 Don't bother checking the Signatures, they aren't correct yet.
-CHECK:     1 [[DWOA]]           [0x00000000, 0x00000029) [0x00000000, 0x00000031) [0x00000000, 0x00000011) [0x00000000, 0x00000010)
-CHECK:     2 [[DWOB]]           [0x00000029, 0x0000005e) [0x00000031, 0x00000075) [0x00000011, 0x00000022) [0x00000010, 0x00000024)
+CHECK:     3 [[DWOA]]           [0x00000000, 0x00000029) [0x00000000, 0x00000031) [0x00000000, 0x00000011) [0x00000000, 0x00000010)
+CHECK:     4 [[DWOB]]           [0x00000029, 0x0000005e) [0x00000031, 0x00000075) [0x00000011, 0x00000022) [0x00000010, 0x00000024)
 
 CHECK: .debug_str.dwo contents:
 CHECK: "clang version

diff --git a/tools/llvm-dwp/llvm-dwp.cpp b/tools/llvm-dwp/llvm-dwp.cpp
index f67ecbf3437f7968486c3a46cfc1aafef1290dfb..b4aaea3b238d4c457f0cd8652c26801743fbb432 100644 (file)
--- a/tools/llvm-dwp/llvm-dwp.cpp
+++ b/tools/llvm-dwp/llvm-dwp.cpp
@@ -19,6 +19,7 @@
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/DebugInfo/DWARF/DWARFUnitIndex.h"
+#include "llvm/Support/MathExtras.h"
 #include <memory>
 #include <list>
 #include <unordered_set>
@@ -222,20 +223,30 @@ static std::error_code write(MCStreamer &Out, ArrayRef<std::string> Inputs) {
     if (C)
       ++Columns;
 
+  std::vector<unsigned> Buckets(NextPowerOf2(3 * IndexEntries.size() / 2));
+  uint64_t Mask = Buckets.size() - 1;
+  for (size_t i = 0; i != IndexEntries.size(); ++i) {
+    auto S = IndexEntries[i].Signature;
+    auto H = S & Mask;
+    while (Buckets[H])
+      H += ((S >> 32) & Mask) | 1;
+    Buckets[H] = i + 1;
+  }
+
   Out.SwitchSection(MCOFI.getDwarfCUIndexSection());
   Out.EmitIntValue(2, 4);                   // Version
   Out.EmitIntValue(Columns, 4);             // Columns
   Out.EmitIntValue(IndexEntries.size(), 4); // Num Units
   // FIXME: This is not the right number of buckets for a real hash.
-  Out.EmitIntValue(IndexEntries.size(), 4); // Num Buckets
+  Out.EmitIntValue(Buckets.size(), 4); // Num Buckets
 
   // Write the signatures.
-  for (const auto &E : IndexEntries)
-    Out.EmitIntValue(E.Signature, 8);
+  for (const auto &I : Buckets)
+    Out.EmitIntValue(I ? IndexEntries[I - 1].Signature : 0, 8);
 
   // Write the indexes.
-  for (size_t i = 0; i != IndexEntries.size(); ++i)
-    Out.EmitIntValue(i + 1, 4);
+  for (const auto &I : Buckets)
+    Out.EmitIntValue(I, 4);
 
   // Write the column headers (which sections will appear in the table)
   for (size_t i = 0; i != array_lengthof(ContributionOffsets); ++i)