[CodeView] Speed up type iteration

[zturner]

Summary

The abstractions in use for iterating over sequences of types are apparently slow. This is not easy to fix, but it basically boils down to abstraction overhead. The internal abstractions have several layers of pointer indirections and shared_ptr copies, which slows things down considerably considering this is in the hot path.

Going back to raw byte-level constructs speeds this up rather significantly, on the order of 10%-15% of total link time. The particular test case here went from 41.6s (pre-patch) to 36s (post-patch), for a solid 15% improvement.

[ruiu]

llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

353–355

nit: you can directly return a return value of forEachCodeViewRecord.

[rnk]

llvm/include/llvm/DebugInfo/CodeView/CVRecord.h

67

This needs to be bounds checked. That's why we came up with that consumeObject pattern, right?

lld/COFF/PDB.cpp

 static void mergeSymbolRecords(BumpPtrAllocator &Alloc, ObjFile *File,
                                pdb::GSIStreamBuilder &GsiBuilder,
                                const CVIndexMap &IndexMap,
                                TypeCollection &IDTable,
                                std::vector<ulittle32_t *> &StringTableRefs,
                                BinaryStreamRef SymData) {
   // FIXME: Improve error recovery by warning and skipping records when
   // possible.
-  CVSymbolArray Syms;
-  BinaryStreamReader Reader(SymData);
-  ExitOnErr(Reader.readArray(Syms, Reader.getLength()));
+  ArrayRef<uint8_t> SymsBuffer;
+  cantFail(SymData.readBytes(0, SymData.getLength(), SymsBuffer));
   SmallVector<SymbolScope, 4> Scopes;
-  for (CVSymbol Sym : Syms) {
-    // Discover type index references in the record. Skip it if we don't know
-    // where they are.
+
+  auto EC = forEachCodeViewRecord<CVSymbol>(
+      SymsBuffer, [&](const CVSymbol &Sym) -> llvm::Error {
+        // 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()));
-      continue;
+          log("ignoring unknown symbol record with kind 0x" +
+              utohexstr(Sym.kind()));
+          return Error::success();
         }
 
         // Copy the symbol record so we can mutate it.
         MutableArrayRef<uint8_t> NewData = copySymbolForPdb(Sym, Alloc);
 
         // Re-map all the type index references.
         MutableArrayRef<uint8_t> Contents =
             NewData.drop_front(sizeof(RecordPrefix));
-    remapTypesInSymbolRecord(File, Sym.kind(), Contents, IndexMap, TypeRefs);
+        remapTypesInSymbolRecord(File, Sym.kind(), Contents, IndexMap,
+                                 TypeRefs);
 
         // An object file may have S_xxx_ID symbols, but these get converted to
         // "real" symbols in a PDB.
         translateIdSymbols(NewData, IDTable);
 
         // 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(), Contents, StringTableRefs);
 
         SymbolKind NewKind = symbolKind(NewData);
 
         // Fill in "Parent" and "End" fields by maintaining a stack of scopes.
         CVSymbol NewSym(NewKind, NewData);
         if (symbolOpensScope(NewKind))
-      scopeStackOpen(Scopes, File->ModuleDBI->getNextSymbolOffset(), NewSym);
+          scopeStackOpen(Scopes, File->ModuleDBI->getNextSymbolOffset(),
+                         NewSym);
         else if (symbolEndsScope(NewKind))
           scopeStackClose(Scopes, File->ModuleDBI->getNextSymbolOffset(), File);
 
-    // Add the symbol to the globals stream if necessary.  Do this before adding
-    // the symbol to the module since we may need to get the next symbol offset,
-    // and writing to the module's symbol stream will update that offset.
+        // Add the symbol to the globals stream if necessary.  Do this before
+        // adding the symbol to the module since we may need to get the next
+        // symbol offset, and writing to the module's symbol stream will update
+        // that offset.
         if (symbolGoesInGlobalsStream(NewSym))
           addGlobalSymbol(GsiBuilder, *File, NewSym);
 
         // Add the symbol to the module.
         if (symbolGoesInModuleStream(NewSym))
           File->ModuleDBI->addSymbol(NewSym);
-  }
+        return Error::success();
+      });
+  cantFail(std::move(EC));
 }
 
 // Allocate memory for a .debug$S section and relocate it.
 static ArrayRef<uint8_t> relocateDebugChunk(BumpPtrAllocator &Alloc,
                                             SectionChunk *DebugChunk) {
   uint8_t *Buffer = Alloc.Allocate<uint8_t>(DebugChunk->getSize());
   assert(DebugChunk->OutputSectionOff == 0 &&
          "debug sections should not be in output sections");

llvm/include/llvm/DebugInfo/CodeView/CVRecord.h

 
 template <typename Kind> struct RemappedRecord {
   explicit RemappedRecord(const CVRecord<Kind> &R) : OriginalRecord(R) {}
 
   CVRecord<Kind> OriginalRecord;
   SmallVector<std::pair<uint32_t, TypeIndex>, 8> Mappings;
 };
 
+template <typename Record, typename Func>
+Error forEachCodeViewRecord(ArrayRef<uint8_t> StreamBuffer, Func F) {
+  while (!StreamBuffer.empty()) {
+    const RecordPrefix *Prefix = (const RecordPrefix *)StreamBuffer.data();
+
+    ArrayRef<uint8_t> Data = StreamBuffer.take_front(Prefix->RecordLen + 2);
+    StreamBuffer = StreamBuffer.drop_front(Prefix->RecordLen + 2);
+
+    Record R(static_cast<decltype(Record::Type)>((uint16_t)Prefix->RecordKind),
+             Data);
+    if (auto EC = F(R))
+      return EC;
+  }
+  return Error::success();
+}
+
 /// Read a complete record from a stream at a random offset.
 template <typename Kind>
 inline Expected<CVRecord<Kind>> readCVRecordFromStream(BinaryStreamRef Stream,
                                                        uint32_t Offset) {
   const RecordPrefix *Prefix = nullptr;
   BinaryStreamReader Reader(Stream);
   Reader.setOffset(Offset);
 

llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

Error TypeStreamMerger::doit(const CVTypeArray &Types) {
   }
 
   if (LastError)
     return std::move(*LastError);
   return Error::success();
 }
 
 Error TypeStreamMerger::remapAllTypes(const CVTypeArray &Types) {
-  for (const CVType &Type : Types)
-    if (auto EC = remapType(Type))
-      return EC;
-  return Error::success();
+  BinaryStreamRef Stream = Types.getUnderlyingStream();
+  ArrayRef<uint8_t> Buffer;
+  cantFail(Stream.readBytes(0, Stream.getLength(), Buffer));
+
+  auto EC = forEachCodeViewRecord<CVType>(
+      Buffer, [this](const CVType &T) { return remapType(T); });
 }
 
 Error TypeStreamMerger::remapType(const CVType &Type) {
   auto DoSerialize = [this, Type]() -> ArrayRef<uint8_t> {
     RemappedType R(Type);
     SmallVector<TiReference, 32> Refs;
     discoverTypeIndices(Type.RecordData, Refs);
     if (!remapIndices(R, Refs))