[CodeView] Add a random access type visitor.

This adds a visitor that is capable of accessing type
records randomly and caching intermediate results that it
learns about during partial linear scans.  This yields
amortized O(1) access to a type stream even though type
streams cannot normally be indexed.

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

llvm-svn: 302936

7 files changed, 160 insertions, 89 deletions

diff --git a/llvm/lib/DebugInfo/CodeView/CMakeLists.txt b/llvm/lib/DebugInfo/CodeView/CMakeLists.txt
index 47cbcfd1990..8d9353ae5f5 100644
--- a/llvm/lib/DebugInfo/CodeView/CMakeLists.txt
+++ b/llvm/lib/DebugInfo/CodeView/CMakeLists.txt
@@ -13,6 +13,7 @@ add_llvm_library(LLVMDebugInfoCodeView
   ModuleDebugFragmentVisitor.cpp
   ModuleDebugInlineeLinesFragment.cpp
   ModuleDebugLineFragment.cpp
+  RandomAccessTypeVisitor.cpp
   RecordSerialization.cpp
   StringTable.cpp
   SymbolRecordMapping.cpp
diff --git a/llvm/lib/DebugInfo/CodeView/CVTypeVisitor.cpp b/llvm/lib/DebugInfo/CodeView/CVTypeVisitor.cpp
index 23f2c40543a..b6ed0453d9c 100644
--- a/llvm/lib/DebugInfo/CodeView/CVTypeVisitor.cpp
+++ b/llvm/lib/DebugInfo/CodeView/CVTypeVisitor.cpp
@@ -26,8 +26,7 @@ CVTypeVisitor::CVTypeVisitor(TypeVisitorCallbacks &Callbacks)
     : Callbacks(Callbacks) {}
 
 template <typename T>
-static Error visitKnownRecord(CVTypeVisitor &Visitor, CVType &Record,
-                              TypeVisitorCallbacks &Callbacks) {
+static Error visitKnownRecord(CVType &Record, TypeVisitorCallbacks &Callbacks) {
   TypeRecordKind RK = static_cast<TypeRecordKind>(Record.Type);
   T KnownRecord(RK);
   if (auto EC = Callbacks.visitKnownRecord(Record, KnownRecord))
@@ -107,7 +106,7 @@ Error CVTypeVisitor::finishVisitation(CVType &Record) {
     break;
 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
   case EnumName: {                                                             \
-    if (auto EC = visitKnownRecord<Name##Record>(*this, Record, Callbacks))    \
+    if (auto EC = visitKnownRecord<Name##Record>(Record, Callbacks))           \
       return EC;                                                               \
     break;                                                                     \
   }
diff --git a/llvm/lib/DebugInfo/CodeView/RandomAccessTypeVisitor.cpp b/llvm/lib/DebugInfo/CodeView/RandomAccessTypeVisitor.cpp
new file mode 100644
index 00000000000..4cb9acbe07d
--- /dev/null
+++ b/llvm/lib/DebugInfo/CodeView/RandomAccessTypeVisitor.cpp
@@ -0,0 +1,91 @@
+//===- RandomAccessTypeVisitor.cpp ---------------------------- *- C++ --*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/CodeView/RandomAccessTypeVisitor.h"
+
+#include "llvm/DebugInfo/CodeView/TypeDatabase.h"
+#include "llvm/DebugInfo/CodeView/TypeServerHandler.h"
+#include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
+
+using namespace llvm;
+using namespace llvm::codeview;
+
+RandomAccessTypeVisitor::RandomAccessTypeVisitor(
+    const CVTypeArray &Types, uint32_t NumRecords,
+    PartialOffsetArray PartialOffsets)
+    : Database(NumRecords), Types(Types), DatabaseVisitor(Database),
+      InternalVisitor(Pipeline), PartialOffsets(PartialOffsets) {
+  Pipeline.addCallbackToPipeline(Deserializer);
+  Pipeline.addCallbackToPipeline(DatabaseVisitor);
+
+  KnownOffsets.resize(Database.capacity());
+}
+
+Error RandomAccessTypeVisitor::visitTypeIndex(TypeIndex TI,
+                                              TypeVisitorCallbacks &Callbacks) {
+  assert(TI.toArrayIndex() < Database.capacity());
+
+  if (!Database.contains(TI)) {
+    if (auto EC = visitRangeForType(TI))
+      return EC;
+  }
+
+  assert(Database.contains(TI));
+  auto &Record = Database.getTypeRecord(TI);
+  CVTypeVisitor V(Callbacks);
+  return V.visitTypeRecord(Record, TI);
+}
+
+Error RandomAccessTypeVisitor::visitRangeForType(TypeIndex TI) {
+  if (PartialOffsets.empty()) {
+    TypeIndex TIB(TypeIndex::FirstNonSimpleIndex);
+    TypeIndex TIE = TIB + Database.capacity();
+    return visitRange(TIB, 0, TIE);
+  }
+
+  auto Next = std::upper_bound(PartialOffsets.begin(), PartialOffsets.end(), TI,
+                               [](TypeIndex Value, const TypeIndexOffset &IO) {
+                                 return Value < IO.Type;
+                               });
+
+  assert(Next != PartialOffsets.begin());
+  auto Prev = std::prev(Next);
+
+  TypeIndex TIB = Prev->Type;
+  TypeIndex TIE;
+  if (Next == PartialOffsets.end()) {
+    TIE = TypeIndex::fromArrayIndex(Database.capacity());
+  } else {
+    TIE = Next->Type;
+  }
+
+  if (auto EC = visitRange(TIB, Prev->Offset, TIE))
+    return EC;
+  return Error::success();
+}
+
+Error RandomAccessTypeVisitor::visitRange(TypeIndex Begin, uint32_t BeginOffset,
+                                          TypeIndex End) {
+
+  auto RI = Types.at(BeginOffset);
+  assert(RI != Types.end());
+
+  while (Begin != End) {
+    assert(!Database.contains(Begin));
+    if (auto EC = InternalVisitor.visitTypeRecord(*RI, Begin))
+      return EC;
+    KnownOffsets[Begin.toArrayIndex()] = BeginOffset;
+
+    BeginOffset += RI.getRecordLength();
+    ++Begin;
+    ++RI;
+  }
+
+  return Error::success();
+}
diff --git a/llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp b/llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp
index 1f2a5d7b333..7924440e5e2 100644
--- a/llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp
+++ b/llvm/lib/DebugInfo/CodeView/TypeDatabase.cpp
@@ -65,20 +65,32 @@ static const SimpleTypeEntry SimpleTypeNames[] = {
     {"__bool64*", SimpleTypeKind::Boolean64},
 };
 
-TypeDatabase::TypeDatabase(uint32_t ExpectedSize) : TypeNameStorage(Allocator) {
-  CVUDTNames.reserve(ExpectedSize);
-  TypeRecords.reserve(ExpectedSize);
+TypeDatabase::TypeDatabase(uint32_t Capacity) : TypeNameStorage(Allocator) {
+  CVUDTNames.resize(Capacity);
+  TypeRecords.resize(Capacity);
+  ValidRecords.resize(Capacity);
 }
 
-/// Gets the type index for the next type record.
-TypeIndex TypeDatabase::getNextTypeIndex() const {
-  return TypeIndex(TypeIndex::FirstNonSimpleIndex + CVUDTNames.size());
+TypeIndex TypeDatabase::appendType(StringRef Name, const CVType &Data) {
+  TypeIndex TI;
+  TI = getAppendIndex();
+  if (TI.toArrayIndex() >= capacity())
+    grow();
+  recordType(Name, TI, Data);
+  return TI;
 }
 
-/// Records the name of a type, and reserves its type index.
-void TypeDatabase::recordType(StringRef Name, const CVType &Data) {
-  CVUDTNames.push_back(Name);
-  TypeRecords.push_back(Data);
+void TypeDatabase::recordType(StringRef Name, TypeIndex Index,
+                              const CVType &Data) {
+  uint32_t AI = Index.toArrayIndex();
+
+  assert(!contains(Index));
+  assert(AI < capacity());
+
+  CVUDTNames[AI] = Name;
+  TypeRecords[AI] = Data;
+  ValidRecords.set(AI);
+  ++Count;
 }
 
 /// Saves the name in a StringSet and creates a stable StringRef.
@@ -104,69 +116,47 @@ StringRef TypeDatabase::getTypeName(TypeIndex Index) const {
     return "<unknown simple type>";
   }
 
-  uint32_t I = Index.getIndex() - TypeIndex::FirstNonSimpleIndex;
-  if (I < CVUDTNames.size())
-    return CVUDTNames[I];
+  if (contains(Index))
+    return CVUDTNames[Index.toArrayIndex()];
 
   return "<unknown UDT>";
 }
 
 const CVType &TypeDatabase::getTypeRecord(TypeIndex Index) const {
-  return TypeRecords[toArrayIndex(Index)];
+  assert(contains(Index));
+  return TypeRecords[Index.toArrayIndex()];
 }
 
 CVType &TypeDatabase::getTypeRecord(TypeIndex Index) {
-  return TypeRecords[toArrayIndex(Index)];
-}
-
-bool TypeDatabase::containsTypeIndex(TypeIndex Index) const {
-  return toArrayIndex(Index) < CVUDTNames.size();
+  assert(contains(Index));
+  return TypeRecords[Index.toArrayIndex()];
 }
 
-uint32_t TypeDatabase::size() const { return CVUDTNames.size(); }
+bool TypeDatabase::contains(TypeIndex Index) const {
+  uint32_t AI = Index.toArrayIndex();
+  if (AI >= capacity())
+    return false;
 
-uint32_t TypeDatabase::toArrayIndex(TypeIndex Index) const {
-  assert(Index.getIndex() >= TypeIndex::FirstNonSimpleIndex);
-  return Index.getIndex() - TypeIndex::FirstNonSimpleIndex;
+  return ValidRecords.test(AI);
 }
 
-RandomAccessTypeDatabase::RandomAccessTypeDatabase(uint32_t ExpectedSize)
-    : TypeDatabase(ExpectedSize) {
-  ValidRecords.resize(ExpectedSize);
-  CVUDTNames.resize(ExpectedSize);
-  TypeRecords.resize(ExpectedSize);
-}
+uint32_t TypeDatabase::size() const { return Count; }
 
-void RandomAccessTypeDatabase::recordType(StringRef Name, TypeIndex Index,
-                                          const CVType &Data) {
-  assert(!containsTypeIndex(Index));
-  uint32_t ZI = Index.getIndex() - TypeIndex::FirstNonSimpleIndex;
+uint32_t TypeDatabase::capacity() const { return TypeRecords.size(); }
 
-  CVUDTNames[ZI] = Name;
-  TypeRecords[ZI] = Data;
-  ValidRecords.set(ZI);
+void TypeDatabase::grow() {
+  TypeRecords.emplace_back();
+  CVUDTNames.emplace_back();
+  ValidRecords.resize(ValidRecords.size() + 1);
 }
 
-StringRef RandomAccessTypeDatabase::getTypeName(TypeIndex Index) const {
-  assert(containsTypeIndex(Index));
-  return TypeDatabase::getTypeName(Index);
-}
+bool TypeDatabase::empty() const { return size() == 0; }
 
-const CVType &RandomAccessTypeDatabase::getTypeRecord(TypeIndex Index) const {
-  assert(containsTypeIndex(Index));
-  return TypeDatabase::getTypeRecord(Index);
-}
+TypeIndex TypeDatabase::getAppendIndex() const {
+  if (empty())
+    return TypeIndex::fromArrayIndex(0);
 
-CVType &RandomAccessTypeDatabase::getTypeRecord(TypeIndex Index) {
-  assert(containsTypeIndex(Index));
-  return TypeDatabase::getTypeRecord(Index);
+  int Index = ValidRecords.find_last();
+  assert(Index != -1);
+  return TypeIndex::fromArrayIndex(Index) + 1;
 }
-
-bool RandomAccessTypeDatabase::containsTypeIndex(TypeIndex Index) const {
-  if (Index.isSimple())
-    return true;
-
-  return ValidRecords.test(toArrayIndex(Index));
-}
-
-uint32_t RandomAccessTypeDatabase::size() const { return ValidRecords.count(); }
diff --git a/llvm/lib/DebugInfo/CodeView/TypeDatabaseVisitor.cpp b/llvm/lib/DebugInfo/CodeView/TypeDatabaseVisitor.cpp
index 8c1a651b653..8d97f8b1cb4 100644
--- a/llvm/lib/DebugInfo/CodeView/TypeDatabaseVisitor.cpp
+++ b/llvm/lib/DebugInfo/CodeView/TypeDatabaseVisitor.cpp
@@ -16,8 +16,6 @@ using namespace llvm;
 using namespace llvm::codeview;
 
 Error TypeDatabaseVisitor::visitTypeBegin(CVType &Record) {
-  assert(TypeDB.is<TypeDatabase *>());
-
   assert(!IsInFieldList);
   // Reset Name to the empty string. If the visitor sets it, we know it.
   Name = "";
@@ -30,27 +28,7 @@ Error TypeDatabaseVisitor::visitTypeBegin(CVType &Record) {
   return Error::success();
 }
 
-StringRef TypeDatabaseVisitor::getTypeName(TypeIndex Index) const {
-  if (auto DB = TypeDB.get<TypeDatabase *>())
-    return DB->getTypeName(Index);
-  else if (auto DB = TypeDB.get<RandomAccessTypeDatabase *>())
-    return DB->getTypeName(Index);
-
-  llvm_unreachable("Invalid TypeDB Kind!");
-}
-
-StringRef TypeDatabaseVisitor::saveTypeName(StringRef Name) {
-  if (auto DB = TypeDB.get<TypeDatabase *>())
-    return DB->saveTypeName(Name);
-  else if (auto DB = TypeDB.get<RandomAccessTypeDatabase *>())
-    return DB->saveTypeName(Name);
-
-  llvm_unreachable("Invalid TypeDB Kind!");
-}
-
 Error TypeDatabaseVisitor::visitTypeBegin(CVType &Record, TypeIndex Index) {
-  assert(TypeDB.is<RandomAccessTypeDatabase *>());
-
   if (auto EC = visitTypeBegin(Record))
     return EC;
 
@@ -58,6 +36,14 @@ Error TypeDatabaseVisitor::visitTypeBegin(CVType &Record, TypeIndex Index) {
   return Error::success();
 }
 
+StringRef TypeDatabaseVisitor::getTypeName(TypeIndex Index) const {
+  return TypeDB->getTypeName(Index);
+}
+
+StringRef TypeDatabaseVisitor::saveTypeName(StringRef Name) {
+  return TypeDB->saveTypeName(Name);
+}
+
 Error TypeDatabaseVisitor::visitTypeEnd(CVType &CVR) {
   if (CVR.Type == LF_FIELDLIST) {
     assert(IsInFieldList);
@@ -69,11 +55,12 @@ Error TypeDatabaseVisitor::visitTypeEnd(CVType &CVR) {
   // CVUDTNames is indexed by type index, and must have one entry for every
   // type.  Field list members are not recorded, and are only referenced by
   // their containing field list record.
-  if (auto DB = TypeDB.get<TypeDatabase *>())
-    DB->recordType(Name, CVR);
-  else if (auto DB = TypeDB.get<RandomAccessTypeDatabase *>())
-    DB->recordType(Name, CurrentTypeIndex, CVR);
+  if (CurrentTypeIndex)
+    TypeDB->recordType(Name, *CurrentTypeIndex, CVR);
+  else
+    TypeDB->appendType(Name, CVR);
 
+  CurrentTypeIndex.reset();
   return Error::success();
 }
 
diff --git a/llvm/lib/DebugInfo/CodeView/TypeDumpVisitor.cpp b/llvm/lib/DebugInfo/CodeView/TypeDumpVisitor.cpp
index 870d95221e7..27a6e098788 100644
--- a/llvm/lib/DebugInfo/CodeView/TypeDumpVisitor.cpp
+++ b/llvm/lib/DebugInfo/CodeView/TypeDumpVisitor.cpp
@@ -173,10 +173,13 @@ void TypeDumpVisitor::printItemIndex(StringRef FieldName, TypeIndex TI) const {
 }
 
 Error TypeDumpVisitor::visitTypeBegin(CVType &Record) {
+  TypeIndex TI = getSourceDB().getAppendIndex();
+  return visitTypeBegin(Record, TI);
+}
+
+Error TypeDumpVisitor::visitTypeBegin(CVType &Record, TypeIndex Index) {
   W->startLine() << getLeafTypeName(Record.Type);
-  W->getOStream() << " ("
-                  << HexNumber(getSourceDB().getNextTypeIndex().getIndex())
-                  << ")";
+  W->getOStream() << " (" << HexNumber(Index.getIndex()) << ")";
   W->getOStream() << " {\n";
   W->indent();
   W->printEnum("TypeLeafKind", unsigned(Record.Type),
diff --git a/llvm/lib/DebugInfo/PDB/Native/TpiStreamBuilder.cpp b/llvm/lib/DebugInfo/PDB/Native/TpiStreamBuilder.cpp
index 375c35b1114..701a318511b 100644
--- a/llvm/lib/DebugInfo/PDB/Native/TpiStreamBuilder.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/TpiStreamBuilder.cpp
@@ -109,7 +109,7 @@ uint32_t TpiStreamBuilder::calculateHashBufferSize() const {
 }
 
 uint32_t TpiStreamBuilder::calculateIndexOffsetSize() const {
-  return TypeIndexOffsets.size() * sizeof(TypeIndexOffset);
+  return TypeIndexOffsets.size() * sizeof(codeview::TypeIndexOffset);
 }
 
 Error TpiStreamBuilder::finalizeMsfLayout() {