[PDB] Add the ability to lookup global symbols by name.

The Globals table is a hash table keyed on symbol name, so
it's possible to lookup symbols by name in O(1) time.  Add
a function to the globals stream to do this, and add an option
to llvm-pdbutil to exercise this, then use it to write some
tests to verify correctness.

llvm-svn: 343951

3 files changed, 63 insertions, 6 deletions

diff --git a/llvm/lib/DebugInfo/PDB/Native/DbiStream.cpp b/llvm/lib/DebugInfo/PDB/Native/DbiStream.cpp
index edaa783398c..60ac17b655a 100644
--- a/llvm/lib/DebugInfo/PDB/Native/DbiStream.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/DbiStream.cpp
@@ -197,7 +197,7 @@ PDB_Machine DbiStream::getMachineType() const {
   return static_cast<PDB_Machine>(Machine);
 }
 
-FixedStreamArray<object::coff_section> DbiStream::getSectionHeaders() {
+FixedStreamArray<object::coff_section> DbiStream::getSectionHeaders() const {
   return SectionHeaders;
 }
 
diff --git a/llvm/lib/DebugInfo/PDB/Native/GlobalsStream.cpp b/llvm/lib/DebugInfo/PDB/Native/GlobalsStream.cpp
index 36076f436ad..3a4c65ecb58 100644
--- a/llvm/lib/DebugInfo/PDB/Native/GlobalsStream.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/GlobalsStream.cpp
@@ -20,7 +20,11 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/PDB/Native/GlobalsStream.h"
+
+#include "llvm/DebugInfo/CodeView/RecordName.h"
+#include "llvm/DebugInfo/PDB/Native/Hash.h"
 #include "llvm/DebugInfo/PDB/Native/RawError.h"
+#include "llvm/DebugInfo/PDB/Native/SymbolStream.h"
 #include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/Error.h"
 #include <algorithm>
@@ -41,6 +45,35 @@ Error GlobalsStream::reload() {
   return Error::success();
 }
 
+std::vector<std::pair<uint32_t, codeview::CVSymbol>>
+GlobalsStream::findRecordsByName(StringRef Name,
+                                 const SymbolStream &Symbols) const {
+  std::vector<std::pair<uint32_t, codeview::CVSymbol>> Result;
+
+  // Hash the name to figure out which bucket this goes into.
+  size_t ExpandedBucketIndex = hashStringV1(Name) % IPHR_HASH;
+  uint32_t CompressedBucketIndex = GlobalsTable.BucketMap[ExpandedBucketIndex];
+  if (CompressedBucketIndex == -1)
+    return Result;
+
+  uint32_t ChainStartOffset = GlobalsTable.HashBuckets[CompressedBucketIndex];
+  uint32_t NextChainStart = GlobalsTable.HashBuckets.size();
+  if (CompressedBucketIndex + 1 < GlobalsTable.HashBuckets.size())
+    NextChainStart = GlobalsTable.HashBuckets[CompressedBucketIndex + 1];
+  ChainStartOffset /= 12;
+  NextChainStart /= 12;
+
+  while (ChainStartOffset < NextChainStart) {
+    PSHashRecord PSH = GlobalsTable.HashRecords[ChainStartOffset];
+    uint32_t Off = PSH.Off - 1;
+    codeview::CVSymbol Record = Symbols.readRecord(Off);
+    if (codeview::getSymbolName(Record) == Name)
+      Result.push_back(std::make_pair(Off, std::move(Record)));
+    ++ChainStartOffset;
+  }
+  return Result;
+}
+
 static Error checkHashHdrVersion(const GSIHashHeader *HashHdr) {
   if (HashHdr->VerHdr != GSIHashHeader::HdrVersion)
     return make_error<RawError>(
@@ -86,7 +119,8 @@ static Error readGSIHashRecords(FixedStreamArray<PSHashRecord> &HashRecords,
 
 static Error
 readGSIHashBuckets(FixedStreamArray<support::ulittle32_t> &HashBuckets,
-                   ArrayRef<uint8_t> &HashBitmap, const GSIHashHeader *HashHdr,
+                   ArrayRef<uint32_t> &HashBitmap, const GSIHashHeader *HashHdr,
+                   MutableArrayRef<int32_t> BucketMap,
                    BinaryStreamReader &Reader) {
   if (auto EC = checkHashHdrVersion(HashHdr))
     return EC;
@@ -94,13 +128,27 @@ readGSIHashBuckets(FixedStreamArray<support::ulittle32_t> &HashBuckets,
   // Before the actual hash buckets, there is a bitmap of length determined by
   // IPHR_HASH.
   size_t BitmapSizeInBits = alignTo(IPHR_HASH + 1, 32);
-  uint32_t NumBitmapEntries = BitmapSizeInBits / 8;
-  if (auto EC = Reader.readBytes(HashBitmap, NumBitmapEntries))
+  uint32_t NumBitmapEntries = BitmapSizeInBits / 32;
+  if (auto EC = Reader.readArray(HashBitmap, NumBitmapEntries))
     return joinErrors(std::move(EC),
                       make_error<RawError>(raw_error_code::corrupt_file,
                                            "Could not read a bitmap."));
+  uint32_t NumBuckets1 = 0;
+  uint32_t CompressedBucketIdx = 0;
+  for (uint32_t I = 0; I <= IPHR_HASH; ++I) {
+    uint8_t WordIdx = I / 32;
+    uint8_t BitIdx = I % 32;
+    bool IsSet = HashBitmap[WordIdx] & (1U << BitIdx);
+    if (IsSet) {
+      ++NumBuckets1;
+      BucketMap[I] = CompressedBucketIdx++;
+    } else {
+      BucketMap[I] = -1;
+    }
+  }
+
   uint32_t NumBuckets = 0;
-  for (uint8_t B : HashBitmap)
+  for (uint32_t B : HashBitmap)
     NumBuckets += countPopulation(B);
 
   // Hash buckets follow.
@@ -118,7 +166,8 @@ Error GSIHashTable::read(BinaryStreamReader &Reader) {
   if (auto EC = readGSIHashRecords(HashRecords, HashHdr, Reader))
     return EC;
   if (HashHdr->HrSize > 0)
-    if (auto EC = readGSIHashBuckets(HashBuckets, HashBitmap, HashHdr, Reader))
+    if (auto EC = readGSIHashBuckets(HashBuckets, HashBitmap, HashHdr,
+                                     BucketMap, Reader))
       return EC;
   return Error::success();
 }
diff --git a/llvm/lib/DebugInfo/PDB/Native/ModuleDebugStream.cpp b/llvm/lib/DebugInfo/PDB/Native/ModuleDebugStream.cpp
index 2e1f61c7a25..6464b85982e 100644
--- a/llvm/lib/DebugInfo/PDB/Native/ModuleDebugStream.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/ModuleDebugStream.cpp
@@ -97,6 +97,14 @@ ModuleDebugStreamRef::symbols(bool *HadError) const {
   return make_range(SymbolArray.begin(HadError), SymbolArray.end());
 }
 
+CVSymbol ModuleDebugStreamRef::readSymbolAtOffset(uint32_t Offset) const {
+  // Offsets include the size of the 4-byte magic at the beginning, but lookup
+  // doesn't take that into account, so subtract it here.
+  auto Iter = SymbolArray.at(Offset - 4);
+  assert(Iter != SymbolArray.end());
+  return *Iter;
+}
+
 iterator_range<ModuleDebugStreamRef::DebugSubsectionIterator>
 ModuleDebugStreamRef::subsections() const {
   return make_range(Subsections.begin(), Subsections.end());