[CodeView] Speed up type merging by about 20%

[zturner]

Summary

The critical loop in type merging is (unsurprisingly) the one that iterates over every type record and remaps indices.

The patch here mostly focuses on improving inlining behavior and saving unnecessary memcpys. The way the algorithm works is that for every record, it tries to insert it into a hash table, and if it succeeded (because it was new), it then calls into a callback to serialize the record and save it off. There were multiple levels of outlined functions in this tight loop. This brings my test case down from 40 seconds to ~35 seconds when built with clang with optimizations.

[rnk]

llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

376–377 ↗

(On Diff #131517)

Maybe the next step is to templatize this so we don't have to build a vector of offsets to iterate? Maybe it doesn't matter, though. It'd save the branch on the TiRefKind inside the loop, though.

I think the ideal code for type index remapping would basically be a giant switch on record kind followed by inlined code that implements the remappings inline in each case block.

393 ↗

(On Diff #131517)

Looks like we lost error handling here.

[zturner]

llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

393 ↗

(On Diff #131517)

It turns out nothing actually depended on or used the error handling. It seems like if we decide we need it in the future, we could just go back and re-add it. For now, I was just trying to make the code as fast as possible. If you think we should put it back though, I can. The current behavior is actually the same as the original behavior though.

[zturner]

llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

376–377 ↗

(On Diff #131517)

Yea, I basically had the same idea. Just like we have ForEachCodeViewRecord we could have ForEachTypeIndex that works the same way. That can be later though.

[rnk]

llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

393 ↗

(On Diff #131517)

No, we were returning an empty record in the case where remapping failed. I mean, I'm sure we don't have tests for this case, but it would be nice to keep this NFC.

[zturner]

Return an empty record when remapping fails.

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

 Error forEachCodeViewRecord(ArrayRef<uint8_t> StreamBuffer, Func F) {
   while (!StreamBuffer.empty()) {
     if (StreamBuffer.size() < sizeof(RecordPrefix))
       return make_error<CodeViewError>(cv_error_code::corrupt_record);
 
     const RecordPrefix *Prefix =
         reinterpret_cast<const RecordPrefix *>(StreamBuffer.data());
 
-    uint16_t RealLen = Prefix->RecordLen + 2;
+    size_t RealLen = Prefix->RecordLen + 2;
     if (StreamBuffer.size() < RealLen)
       return make_error<CodeViewError>(cv_error_code::corrupt_record);
 
     ArrayRef<uint8_t> Data = StreamBuffer.take_front(RealLen);
     StreamBuffer = StreamBuffer.drop_front(RealLen);
 
     Record R(static_cast<decltype(Record::Type)>((uint16_t)Prefix->RecordKind),
              Data);

llvm/trunk/include/llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h

public:
   void reset();
   TypeIndex nextTypeIndex() const;
 
   BumpPtrAllocator &getAllocator() { return RecordStorage; }
 
   ArrayRef<ArrayRef<uint8_t>> records() const;
   ArrayRef<GloballyHashedType> hashes() const;
 
-  using CreateRecord = llvm::function_ref<ArrayRef<uint8_t>()>;
+  template <typename CreateFunc>
+  TypeIndex insertRecordAs(GloballyHashedType Hash, size_t RecordSize,
+                           CreateFunc Create) {
+    auto Result = HashedRecords.try_emplace(Hash, nextTypeIndex());
+
+    if (LLVM_UNLIKELY(Result.second)) {
+      uint8_t *Stable = RecordStorage.Allocate<uint8_t>(RecordSize);
+      MutableArrayRef<uint8_t> Data(Stable, RecordSize);
+      SeenRecords.push_back(Create(Data));
+      SeenHashes.push_back(Hash);
+    }
+
+    // Update the caller's copy of Record to point a stable copy.
+    return Result.first->second;
+  }
 
-  TypeIndex insertRecordAs(GloballyHashedType Hash, CreateRecord Create);
   TypeIndex insertRecordBytes(ArrayRef<uint8_t> Data);
   TypeIndex insertRecord(ContinuationRecordBuilder &Builder);
 
   template <typename T> TypeIndex writeLeafType(T &Record) {
     ArrayRef<uint8_t> Data = SimpleSerializer.serialize(Record);
     return insertRecordBytes(Data);
   }
 };
 
 } // end namespace codeview
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_CODEVIEW_MERGINGTYPETABLEBUILDER_H

llvm/trunk/lib/DebugInfo/CodeView/GlobalTypeTableBuilder.cpp

Optional<TypeIndex> GlobalTypeTableBuilder::getNext(TypeIndex Prev) {
   if (++Prev == nextTypeIndex())
     return None;
   return Prev;
 }
 
 CVType GlobalTypeTableBuilder::getType(TypeIndex Index) {
   CVType Type;
   Type.RecordData = SeenRecords[Index.toArrayIndex()];
+  if (!Type.RecordData.empty()) {
+    assert(Type.RecordData.size() >= sizeof(RecordPrefix));
     const RecordPrefix *P =
         reinterpret_cast<const RecordPrefix *>(Type.RecordData.data());
     Type.Type = static_cast<TypeLeafKind>(uint16_t(P->RecordKind));
+  }
   return Type;
 }
 
 StringRef GlobalTypeTableBuilder::getTypeName(TypeIndex Index) {
   llvm_unreachable("Method not implemented");
 }
 
 bool GlobalTypeTableBuilder::contains(TypeIndex Index) {
ArrayRef<GloballyHashedType> GlobalTypeTableBuilder::hashes() const {
   return SeenHashes;
 }
 
 void GlobalTypeTableBuilder::reset() {
   HashedRecords.clear();
   SeenRecords.clear();
 }
 
-static inline ArrayRef<uint8_t> stabilize(BumpPtrAllocator &Alloc,
-                                          ArrayRef<uint8_t> Data) {
-  uint8_t *Stable = Alloc.Allocate<uint8_t>(Data.size());
-  memcpy(Stable, Data.data(), Data.size());
-  return makeArrayRef(Stable, Data.size());
-}
-
-TypeIndex GlobalTypeTableBuilder::insertRecordAs(GloballyHashedType Hash,
-                                                 CreateRecord Create) {
-  auto Result = HashedRecords.try_emplace(Hash, nextTypeIndex());
-
-  if (Result.second) {
-    ArrayRef<uint8_t> RecordData = stabilize(RecordStorage, Create());
-    SeenRecords.push_back(RecordData);
-    SeenHashes.push_back(Hash);
-  }
-
-  // Update the caller's copy of Record to point a stable copy.
-  return Result.first->second;
-}
-
 TypeIndex GlobalTypeTableBuilder::insertRecordBytes(ArrayRef<uint8_t> Record) {
   GloballyHashedType GHT =
       GloballyHashedType::hashType(Record, SeenHashes, SeenHashes);
-  return insertRecordAs(GHT, [Record]() { return Record; });
+  return insertRecordAs(GHT, Record.size(),
+                        [Record](MutableArrayRef<uint8_t> Data) {
+                          assert(Data.size() == Record.size());
+                          ::memcpy(Data.data(), Record.data(), Record.size());
+                          return Data;
+                        });
 }
 
 TypeIndex
 GlobalTypeTableBuilder::insertRecord(ContinuationRecordBuilder &Builder) {
   TypeIndex TI;
   auto Fragments = Builder.end(nextTypeIndex());
   assert(!Fragments.empty());
   for (auto C : Fragments)
     TI = insertRecordBytes(C.RecordData);
   return TI;
 }

llvm/trunk/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 #include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/Support/Error.h"
 
 using namespace llvm;
 using namespace llvm::codeview;
 
+static inline size_t slotForIndex(TypeIndex Idx) {
+  assert(!Idx.isSimple() && "simple type indices have no slots");
+  return Idx.getIndex() - TypeIndex::FirstNonSimpleIndex;
+}
+
 namespace {
 
 /// Implementation of CodeView type stream merging.
 ///
 /// A CodeView type stream is a series of records that reference each other
 /// through type indices. A type index is either "simple", meaning it is less
 /// than 0x1000 and refers to a builtin type, or it is complex, meaning it
 /// refers to a prior type record in the current stream. The type index of a
private:
   Error doit(const CVTypeArray &Types);
 
   Error remapAllTypes(const CVTypeArray &Types);
 
   Error remapType(const CVType &Type);
 
   void addMapping(TypeIndex Idx);
 
-  bool remapTypeIndex(TypeIndex &Idx);
-  bool remapItemIndex(TypeIndex &Idx);
+  inline bool remapTypeIndex(TypeIndex &Idx) {
+    // If we're mapping a pure index stream, then IndexMap only contains
+    // mappings from OldIdStream -> NewIdStream, in which case we will need to
+    // use the special mapping from OldTypeStream -> NewTypeStream which was
+    // computed externally.  Regardless, we use this special map if and only if
+    // we are doing an id-only mapping.
+    if (!hasTypeStream())
+      return remapIndex(Idx, TypeLookup);
+
+    assert(TypeLookup.empty());
+    return remapIndex(Idx, IndexMap);
+  }
+  inline bool remapItemIndex(TypeIndex &Idx) {
+    assert(hasIdStream());
+    return remapIndex(Idx, IndexMap);
+  }
 
   bool hasTypeStream() const {
     return (UseGlobalHashes) ? (!!DestGlobalTypeStream) : (!!DestTypeStream);
   }
 
   bool hasIdStream() const {
     return (UseGlobalHashes) ? (!!DestGlobalIdStream) : (!!DestIdStream);
   }
 
-  ArrayRef<uint8_t> serializeRemapped(const RemappedType &Record);
+  ArrayRef<uint8_t> remapIndices(const CVType &OriginalType,
+                                 MutableArrayRef<uint8_t> Storage);
 
-  bool remapIndices(RemappedType &Record, ArrayRef<TiReference> Refs);
+  inline bool remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map) {
+    if (LLVM_LIKELY(remapIndexSimple(Idx, Map)))
+      return true;
 
-  bool remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map);
+    return remapIndexFallback(Idx, Map);
+  }
 
-  size_t slotForIndex(TypeIndex Idx) const {
-    assert(!Idx.isSimple() && "simple type indices have no slots");
-    return Idx.getIndex() - TypeIndex::FirstNonSimpleIndex;
+  inline bool remapIndexSimple(TypeIndex &Idx, ArrayRef<TypeIndex> Map) const {
+    // Simple types are unchanged.
+    if (Idx.isSimple())
+      return true;
+
+    // Check if this type index refers to a record we've already translated
+    // successfully. If it refers to a type later in the stream or a record we
+    // had to defer, defer it until later pass.
+    unsigned MapPos = slotForIndex(Idx);
+    if (LLVM_UNLIKELY(MapPos >= Map.size() || Map[MapPos] == Untranslated))
+      return false;
+
+    Idx = Map[MapPos];
+    return true;
   }
 
+  bool remapIndexFallback(TypeIndex &Idx, ArrayRef<TypeIndex> Map);
+
   Error errorCorruptRecord() const {
     return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
   }
 
   Optional<Error> LastError;
 
   bool UseGlobalHashes = false;
 
private:
 
   /// Temporary storage that we use to copy a record's data while re-writing
   /// its type indices.
   SmallVector<uint8_t, 256> RemapStorage;
 };
 
 } // end anonymous namespace
 
-ArrayRef<uint8_t>
-TypeStreamMerger::serializeRemapped(const RemappedType &Record) {
-  TypeIndex TI;
-  ArrayRef<uint8_t> OriginalData = Record.OriginalRecord.RecordData;
-  if (Record.Mappings.empty())
-    return OriginalData;
-
-  // At least one type index was remapped.  We copy the full record bytes,
-  // re-write each type index, then return that.
-  RemapStorage.resize(OriginalData.size());
-  ::memcpy(&RemapStorage[0], OriginalData.data(), OriginalData.size());
-  uint8_t *ContentBegin = RemapStorage.data() + sizeof(RecordPrefix);
-  for (const auto &M : Record.Mappings) {
-    // First 4 bytes of every record are the record prefix, but the mapping
-    // offset is relative to the content which starts after.
-    *(TypeIndex *)(ContentBegin + M.first) = M.second;
-  }
-  auto RemapRef = makeArrayRef(RemapStorage);
-  return RemapRef;
-}
-
 const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);
 
 static bool isIdRecord(TypeLeafKind K) {
   switch (K) {
   case TypeLeafKind::LF_FUNC_ID:
   case TypeLeafKind::LF_MFUNC_ID:
   case TypeLeafKind::LF_STRING_ID:
   case TypeLeafKind::LF_SUBSTR_LIST:
assert(IndexMap.size() == slotForIndex(CurIndex) &&
            "visitKnownRecord should add one index map entry");
     IndexMap.push_back(Idx);
   } else {
     assert(slotForIndex(CurIndex) < IndexMap.size());
     IndexMap[slotForIndex(CurIndex)] = Idx;
   }
 }
 
-bool TypeStreamMerger::remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map) {
-  // Simple types are unchanged.
-  if (Idx.isSimple())
-    return true;
-
-  // Check if this type index refers to a record we've already translated
-  // successfully. If it refers to a type later in the stream or a record we
-  // had to defer, defer it until later pass.
-  unsigned MapPos = slotForIndex(Idx);
-  if (MapPos < Map.size() && Map[MapPos] != Untranslated) {
-    Idx = Map[MapPos];
-    return true;
-  }
+bool TypeStreamMerger::remapIndexFallback(TypeIndex &Idx,
+                                          ArrayRef<TypeIndex> Map) {
+  size_t MapPos = slotForIndex(Idx);
 
   // If this is the second pass and this index isn't in the map, then it points
   // outside the current type stream, and this is a corrupt record.
   if (IsSecondPass && MapPos >= Map.size()) {
     // FIXME: Print a more useful error. We can give the current record and the
     // index that we think its pointing to.
     LastError = joinErrors(std::move(*LastError), errorCorruptRecord());
   }
 
   ++NumBadIndices;
 
   // This type index is invalid. Remap this to "not translated by cvpack",
   // and return failure.
   Idx = Untranslated;
   return false;
 }
 
-bool TypeStreamMerger::remapTypeIndex(TypeIndex &Idx) {
-  // If we're mapping a pure index stream, then IndexMap only contains mappings
-  // from OldIdStream -> NewIdStream, in which case we will need to use the
-  // special mapping from OldTypeStream -> NewTypeStream which was computed
-  // externally.  Regardless, we use this special map if and only if we are
-  // doing an id-only mapping.
-  if (!hasTypeStream())
-    return remapIndex(Idx, TypeLookup);
-
-  assert(TypeLookup.empty());
-  return remapIndex(Idx, IndexMap);
-}
-
-bool TypeStreamMerger::remapItemIndex(TypeIndex &Idx) {
-  assert(hasIdStream());
-  return remapIndex(Idx, IndexMap);
-}
-
 // Local hashing entry points
 Error TypeStreamMerger::mergeTypeRecords(MergingTypeTableBuilder &Dest,
                                          const CVTypeArray &Types) {
   DestTypeStream = &Dest;
   UseGlobalHashes = false;
 
   return doit(Types);
 }
Error TypeStreamMerger::remapAllTypes(const CVTypeArray &Types) {
   ArrayRef<uint8_t> Buffer;
   cantFail(Stream.readBytes(0, Stream.getLength(), Buffer));
 
   return 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))
-      return {};
-    return serializeRemapped(R);
+  auto DoSerialize =
+      [this, Type](MutableArrayRef<uint8_t> Storage) -> ArrayRef<uint8_t> {
+    return remapIndices(Type, Storage);
   };
 
   TypeIndex DestIdx = Untranslated;
-  if (UseGlobalHashes) {
+  if (LLVM_LIKELY(UseGlobalHashes)) {
     GlobalTypeTableBuilder &Dest =
         isIdRecord(Type.kind()) ? *DestGlobalIdStream : *DestGlobalTypeStream;
     GloballyHashedType H = GlobalHashes[CurIndex.toArrayIndex()];
-    DestIdx = Dest.insertRecordAs(H, DoSerialize);
+    DestIdx = Dest.insertRecordAs(H, Type.RecordData.size(), DoSerialize);
   } else {
     MergingTypeTableBuilder &Dest =
         isIdRecord(Type.kind()) ? *DestIdStream : *DestTypeStream;
 
-    auto Data = DoSerialize();
-    if (!Data.empty())
-      DestIdx = Dest.insertRecordBytes(Data);
+    RemapStorage.resize(Type.RecordData.size());
+    ArrayRef<uint8_t> Result = DoSerialize(RemapStorage);
+    if (!Result.empty())
+      DestIdx = Dest.insertRecordBytes(Result);
   }
   addMapping(DestIdx);
 
   ++CurIndex;
   assert((IsSecondPass || IndexMap.size() == slotForIndex(CurIndex)) &&
          "visitKnownRecord should add one index map entry");
   return Error::success();
 }
 
-bool TypeStreamMerger::remapIndices(RemappedType &Record,
-                                    ArrayRef<TiReference> Refs) {
-  ArrayRef<uint8_t> OriginalData = Record.OriginalRecord.content();
-  bool Success = true;
+ArrayRef<uint8_t>
+TypeStreamMerger::remapIndices(const CVType &OriginalType,
+                               MutableArrayRef<uint8_t> Storage) {
+  SmallVector<TiReference, 4> Refs;
+  discoverTypeIndices(OriginalType.RecordData, Refs);
+  if (Refs.empty())
+    return OriginalType.RecordData;
+
+  ::memcpy(Storage.data(), OriginalType.RecordData.data(),
+           OriginalType.RecordData.size());
+
+  uint8_t *DestContent = Storage.data() + sizeof(RecordPrefix);
+
   for (auto &Ref : Refs) {
-    uint32_t Offset = Ref.Offset;
-    ArrayRef<uint8_t> Bytes = OriginalData.slice(Ref.Offset, sizeof(TypeIndex));
-    ArrayRef<TypeIndex> TIs(reinterpret_cast<const TypeIndex *>(Bytes.data()),
-                            Ref.Count);
-    for (auto TI : TIs) {
-      TypeIndex NewTI = TI;
-      bool ThisSuccess = (Ref.Kind == TiRefKind::IndexRef)
-                             ? remapItemIndex(NewTI)
-                             : remapTypeIndex(NewTI);
-      if (ThisSuccess && NewTI != TI)
-        Record.Mappings.emplace_back(Offset, NewTI);
-      Offset += sizeof(TypeIndex);
-      Success &= ThisSuccess;
+    TypeIndex *DestTIs =
+        reinterpret_cast<TypeIndex *>(DestContent + Ref.Offset);
+
+    for (size_t I = 0; I < Ref.Count; ++I) {
+      TypeIndex &TI = DestTIs[I];
+      bool Success = (Ref.Kind == TiRefKind::IndexRef) ? remapItemIndex(TI)
+                                                       : remapTypeIndex(TI);
+      if (LLVM_UNLIKELY(!Success))
+        return {};
     }
   }
-  return Success;
+  return Storage;
 }
 
 Error llvm::codeview::mergeTypeRecords(MergingTypeTableBuilder &Dest,
                                        SmallVectorImpl<TypeIndex> &SourceToDest,
                                        const CVTypeArray &Types) {
   TypeStreamMerger M(SourceToDest);
   return M.mergeTypeRecords(Dest, Types);
 }