[PDB] Print the most redundant type record indices with /summary

[rnk]

Summary

I used this information to motivate splitting up the Intrinsic::ID enum
(5d986953c8b917bacfaa1f800fc1e242559f76be) and adding a key method to
clang::Sema (586f65d31f32ca6bc8cfdb8a4f61bee5057bf6c8) which saved a
fair amount of object file size.

Example output for clang.pdb:

Top 10 types responsible for the most TPI input bytes:
       index     total bytes   count     size
      0x3890:      8,671,220 = 1,805 *  4,804
     0xE13BE:      5,634,720 =   252 * 22,360
     0x6874C:      5,181,600 =   408 * 12,700
      0x2A1F:      4,520,528 = 1,574 *  2,872
     0x64BFF:      4,024,020 =   469 *  8,580
      0x1123:      4,012,020 = 2,157 *  1,860
      0x6952:      3,753,792 =   912 *  4,116
      0xC16F:      3,630,888 =   633 *  5,736
      0x69DD:      3,601,160 =   985 *  3,656
      0x678D:      3,577,904 =   319 * 11,216

In this case, we can see that record 0x3890 is responsible for ~8MB of
total object file size for objects in clang.

The user can then use llvm-pdbutil to find out what the record is:

$ llvm-pdbutil dump -types -type-index 0x3890
                     Types (TPI Stream)
============================================================
  Showing 1 records.
     0x3890 | LF_FIELDLIST [size = 4804]
              - LF_STMEMBER [name = `WORDTYPE_MAX`, type = 0x1001, attrs = public]
              - LF_MEMBER [name = `U`, Type = 0x37F0, offset = 0, attrs = private]
              - LF_MEMBER [name = `BitWidth`, Type = 0x0075 (unsigned), offset = 8, attrs = private]
              - LF_METHOD [name = `APInt`, # overloads = 8, overload list = 0x3805]
...

In this case, we can see that these are members of the APInt class,
which is emitted in 1805 object files.

The next largest type is ASTContext:

$ llvm-pdbutil dump -types -type-index 0xE13BE bin/clang.pdb
    0xE13BE | LF_FIELDLIST [size = 22360]
              - LF_BCLASS
                type = 0x653EA, offset = 0, attrs = public
              - LF_MEMBER [name = `Types`, Type = 0x653EB, offset = 8, attrs = private]
              - LF_MEMBER [name = `ExtQualNodes`, Type = 0x653EC, offset = 24, attrs = private]
              - LF_MEMBER [name = `ComplexTypes`, Type = 0x653ED, offset = 48, attrs = private]
              - LF_MEMBER [name = `PointerTypes`, Type = 0x653EE, offset = 72, attrs = private]
...

ASTContext only appears 252 times, but the list of members is long, and
must be repeated everywhere it is used.

This was the output before I split Intrinsic::ID:

Top 10 types responsible for the most TPI input:
      0x686C:     69,823,920 = 1,070 * 65,256
      0x686D:     69,819,640 = 1,070 * 65,252
      0x686E:     69,819,640 = 1,070 * 65,252
      0x686B:     16,371,000 = 1,070 * 15,300
      ...

These records were all lists of intrinsic enums.

[rnk]

• share isIdRecord

[ruiu]

Looks like this is an interesting feature, but the output might be a bit too spartan? It feels to me that it is not easy to make this feature's output into an actionable item unless you are not familiar with the debug record format. I wonder if there's an way to print out some "recommendation" to the user, say "<some class> is repeated xxx times. consider moving it out of a header file if it is written in a header.".

[rnk]

Do you think I could just print a note that says "run llvm-pdbutil dump -types -type-index 0xNN path/to/foo.pdb to view a type record"? I could add more functionality to textually dump the type as more than a hex number to try to get closer to something actionable for the user, but I hesitate to duplicate functionality already available in llvm-pdbutil. And I wouldn't want LLD to depend on all the llvm-pdbutil dumping code, either.

[ruiu]

Yeah, I guess that showing that tip line would help users.

[rnk]

• print llvm-pdbutil command
• fix variable names

[merge_guards_bot]

Unit tests: pass. 61012 tests passed, 0 failed and 728 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[MaskRay]

The PDB subject made me worry that I don't have enough knowledge to review it. Now I see it is a new feature and is related to debug info, which I really should learn more. I'll take some time tomorrow to understand it...

[MaskRay]

lld/COFF/PDB.cpp

431

Can tpiCounts be a non-empty vector before resize()?

If yes, assign(tMerger.getTypeTable().size(), 0);

437

Excuse my ignorance. What does "Untranslated or other" mean? I cannot find "untranslated" at other call sites of isSimple.

517

auto -> TypeIndex

1390

I've seen SmallVector<..., 0> in some code. Does that has any advantage over std::vector<...>?

[rnk]

lld/COFF/PDB.cpp

431

Yes, it can be non-empty, but why is assign better? resize() does zero initialization, it is not reserve.

437

Type merging can fail for some records, and rather than failing the whole link, the the record is discarded. Any indexes referring to it are replaced with SimpleTypeKind::NotTranslated, which is a simple type. The programmer could reasonably assume that complex types always map to complex types, but this is the common case where that assumption won't hold. The toArrayIndex call below will assert in that case.

1390

I've been assuming it does since I saw @bkramer doing it:
https://github.com/llvm/llvm-project/commit/bb76eaa2c73818c79773fdc8012b92846a1eebbe

[rnk]

• some changes

[merge_guards_bot]

Unit tests: pass. 61147 tests passed, 0 failed and 728 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[MaskRay]

lld/COFF/PDB.cpp

431

If it was non-empty, existing non-zero values would not be zeroed.

If the current size is less than count,

1) additional default-inserted elements are appended

[rnk]

lld/COFF/PDB.cpp

431

If it was non-empty, existing non-zero values would not be zeroed.

That is the intended behavior. I can't think of another good way to express this: grow the array, fill it with zeros, do it in a way that will trigger quadratic growth. Maybe a longer .insert call? .insert(tpiCounts.end(), size, 0)?

Well, I will commit it this way for now.

[MaskRay]

lld/COFF/PDB.cpp

431

Sorry I thought you wanted to zero the whole array. resize is the best to insert zeros while keeping existing values unchanged.

lld/COFF/PDB.cpp

 #include "Config.h"
 #include "DebugTypes.h"
 #include "Driver.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "TypeMerger.h"
 #include "Writer.h"
 #include "lld/Common/ErrorHandler.h"
-#include "lld/Common/Timer.h"
 #include "lld/Common/Threads.h"
+#include "lld/Common/Timer.h"
 #include "llvm/DebugInfo/CodeView/DebugFrameDataSubsection.h"
 #include "llvm/DebugInfo/CodeView/DebugSubsectionRecord.h"
 #include "llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h"
 #include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
 #include "llvm/DebugInfo/CodeView/MergingTypeTableBuilder.h"
 #include "llvm/DebugInfo/CodeView/RecordName.h"
 #include "llvm/DebugInfo/CodeView/SymbolDeserializer.h"
 #include "llvm/DebugInfo/CodeView/SymbolRecordHelpers.h"
 #include "llvm/DebugInfo/CodeView/SymbolSerializer.h"
 #include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
 #include "llvm/DebugInfo/CodeView/TypeDumpVisitor.h"
 #include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
+#include "llvm/DebugInfo/CodeView/TypeRecordHelpers.h"
 #include "llvm/DebugInfo/CodeView/TypeStreamMerger.h"
 #include "llvm/DebugInfo/MSF/MSFBuilder.h"
 #include "llvm/DebugInfo/MSF/MSFCommon.h"
 #include "llvm/DebugInfo/PDB/GenericError.h"
 #include "llvm/DebugInfo/PDB/Native/DbiModuleDescriptorBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/DbiStream.h"
 #include "llvm/DebugInfo/PDB/Native/DbiStreamBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/GSIStreamBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/InfoStream.h"
 #include "llvm/DebugInfo/PDB/Native/InfoStreamBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/NativeSession.h"
 #include "llvm/DebugInfo/PDB/Native/PDBFile.h"
 #include "llvm/DebugInfo/PDB/Native/PDBFileBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/PDBStringTableBuilder.h"
 #include "llvm/DebugInfo/PDB/Native/TpiHashing.h"
 #include "llvm/DebugInfo/PDB/Native/TpiStream.h"
 #include "llvm/DebugInfo/PDB/Native/TpiStreamBuilder.h"
 #include "llvm/DebugInfo/PDB/PDB.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Object/CVDebugRecord.h"
 #include "llvm/Support/BinaryByteStream.h"
 #include "llvm/Support/CRC.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Errc.h"
+#include "llvm/Support/FormatAdapters.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include <memory>
 
 using namespace llvm;
 using namespace llvm::codeview;
 
private:
   /// Type index mappings of precompiled objects type map that we've loaded so
   /// far.
   std::map<uint32_t, CVIndexMap> precompTypeIndexMappings;
 
   // For statistics
   uint64_t globalSymbols = 0;
   uint64_t moduleSymbols = 0;
   uint64_t publicSymbols = 0;
+
+  // When showSummary is enabled, these are histograms of TPI and IPI records
+  // keyed by type index.
+  SmallVector<uint32_t, 0> tpiCounts;
+  SmallVector<uint32_t, 0> ipiCounts;
 };
 
 class DebugSHandler {
   PDBLinker &linker;
 
   /// The object file whose .debug$S sections we're processing.
   ObjFile &file;
 
if (auto err = mergeTypeAndIdRecords(
             toString(std::move(err)));
   } else {
     if (auto err = mergeTypeAndIdRecords(tMerger.iDTable, tMerger.typeTable,
                                          objectIndexMap->tpiMap, types,
                                          file->pchSignature))
       fatal("codeview::mergeTypeAndIdRecords failed: " +
             toString(std::move(err)));
   }
+
+  if (config->showSummary) {
+    // Count how many times we saw each type record in our input. This
+    // calculation requires a second pass over the type records to classify each
+    // record as a type or index. This is slow, but this code executes when
+    // collecting statistics.
+    tpiCounts.resize(tMerger.getTypeTable().size());
+    ipiCounts.resize(tMerger.getIDTable().size());
+    uint32_t srcIdx = 0;
+    for (CVType &ty : types) {
+      TypeIndex dstIdx = objectIndexMap->tpiMap[srcIdx++];
+      if (dstIdx.isSimple())
+        continue; // Untranslated or other.
+      SmallVectorImpl<uint32_t> &counts =
+          isIdRecord(ty.kind()) ? ipiCounts : tpiCounts;
+      ++counts[dstIdx.toArrayIndex()];
+    }
+  }
+
   return *objectIndexMap;
 }
 
 Expected<const CVIndexMap &> PDBLinker::maybeMergeTypeServerPDB(ObjFile *file) {
   Expected<llvm::pdb::NativeSession *> pdbSession = findTypeServerSource(file);
   if (!pdbSession)
     return pdbSession.takeError();
 
if (config->debugGHashes) {
     // Merge IPI.
     if (maybeIpi) {
       if (auto err = mergeIdRecords(tMerger.iDTable, indexMap.tpiMap,
                                     indexMap.ipiMap, maybeIpi->typeArray()))
         fatal("codeview::mergeIdRecords failed: " + toString(std::move(err)));
     }
   }
 
+  if (config->showSummary) {
+    // Count how many times we saw each type record in our input. If a
+    // destination type index is present in the source to destination type index
+    // map, that means we saw it once in the input. Add it to our histogram.
+    tpiCounts.resize(tMerger.getTypeTable().size());
+    ipiCounts.resize(tMerger.getIDTable().size());
+    for (auto ti : indexMap.tpiMap)
+      ++tpiCounts[ti.toArrayIndex()];
+    for (auto ti : indexMap.ipiMap)
+      ++ipiCounts[ti.toArrayIndex()];
+  }
+
   return indexMap;
 }
 
 Error PDBLinker::mergeInPrecompHeaderObj(ObjFile *file,
                                          CVIndexMap *objectIndexMap) {
   const PrecompRecord &precomp =
       retrieveDependencyInfo<PrecompRecord>(file->debugTypesObj);
 
void PDBLinker::printStats() {
   print(precompTypeIndexMappings.size(), "Precomp OBJ dependencies");
   print(tMerger.getTypeTable().size() + tMerger.getIDTable().size(),
         "Merged TPI records");
   print(pdbStrTab.size(), "Output PDB strings");
   print(globalSymbols, "Global symbol records");
   print(moduleSymbols, "Module symbol records");
   print(publicSymbols, "Public symbol records");
 
+  auto printLargeInputTypeRecs = [&](StringRef name,
+                                     ArrayRef<uint32_t> recCounts,
+                                     TypeCollection &records) {
+    // Figure out which type indices were responsible for the most duplicate
+    // bytes in the input files. These should be frequently emitted LF_CLASS and
+    // LF_FIELDLIST records.
+    struct TypeSizeInfo {
+      uint32_t TypeSize;
+      uint32_t DupCount;
+      TypeIndex TI;
+      uint64_t totalInputSize() const { return uint64_t(DupCount) * TypeSize; }
+      bool operator<(const TypeSizeInfo &RHS) const {
+        return totalInputSize() < RHS.totalInputSize();
+      }
+    };
+    SmallVector<TypeSizeInfo, 0> TSIs;
+    for (auto E : enumerate(recCounts)) {
+      TypeIndex TI = TypeIndex::fromArrayIndex(E.index());
+      uint32_t TypeSize = records.getType(TI).length();
+      uint32_t DupCount = E.value();
+      TSIs.push_back({TypeSize, DupCount, TI});
+    }
+
+    if (!TSIs.empty()) {
+      stream << "\nTop 10 types responsible for the most " << name
+             << " input:\n";
+      stream << "       index     total bytes   count     size\n";
+      llvm::sort(TSIs);
+      unsigned I = 0;
+      for (const auto &TSI : reverse(TSIs)) {
+        stream << formatv("  {0,10:X}: {1,14:N} = {2,5:N} * {3,6:N}\n",
+                          TSI.TI.getIndex(), TSI.totalInputSize(), TSI.DupCount,
+                          TSI.TypeSize);
+        if (++I >= 10)
+          break;
+      }
+    }
+  };
+
+  printLargeInputTypeRecs("TPI", tpiCounts, tMerger.getTypeTable());
+  printLargeInputTypeRecs("IPI", ipiCounts, tMerger.getIDTable());
+
   message(buffer);
 }
 
 void PDBLinker::addNatvisFiles() {
   for (StringRef file : config->natvisFiles) {
     ErrorOr<std::unique_ptr<MemoryBuffer>> dataOrErr =
         MemoryBuffer::getFile(file);
     if (!dataOrErr) {

lld/test/COFF/pdb-type-server-simple.test

 SUMMARY-NEXT: --------------------------------------------------------------------------------
 SUMMARY-NEXT:               2 Input OBJ files (expanded from all cmd-line inputs)
 SUMMARY-NEXT:               1 PDB type server dependencies
 SUMMARY-NEXT:               0 Precomp OBJ dependencies
 SUMMARY-NEXT:              25 Merged TPI records
 SUMMARY-NEXT:               3 Output PDB strings
 SUMMARY-NEXT:               4 Global symbol records
 SUMMARY-NEXT:              14 Module symbol records
-SUMMARY-NEXT:               2 Public symbol records
+SUMMARY-NEXT:               2 Public symbol records
+
+SUMMARY:      Top 10 types responsible for the most TPI input:
+SUMMARY-NEXT:        index     total bytes   count     size
+SUMMARY-NEXT:       0x1006:             36 =     1 *     36
+
+SUMMARY:      Top 10 types responsible for the most IPI input:
+SUMMARY-NEXT:        index     total bytes   count     size
+SUMMARY-NEXT:       0x1006:            256 =     1 *    256

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

class GlobalTypeTableBuilder : public TypeCollection {
   SimpleTypeSerializer SimpleSerializer;
 
   /// Hash table.
   DenseMap<GloballyHashedType, TypeIndex> HashedRecords;
 
   /// Contains a list of all records indexed by TypeIndex.toArrayIndex().
   SmallVector<ArrayRef<uint8_t>, 2> SeenRecords;
 
-  /// Contains a list of all hash values inexed by TypeIndex.toArrayIndex().
+  /// Contains a list of all hash values indexed by TypeIndex.toArrayIndex().
   SmallVector<GloballyHashedType, 2> SeenHashes;
 
 public:
   explicit GlobalTypeTableBuilder(BumpPtrAllocator &Storage);
   ~GlobalTypeTableBuilder();
 
   // TypeTableCollection overrides
   Optional<TypeIndex> getFirst() override;

llvm/include/llvm/DebugInfo/CodeView/TypeRecordHelpers.h

 //===- TypeRecordHelpers.h --------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_CODEVIEW_TYPERECORDHELPERS_H
 #define LLVM_DEBUGINFO_CODEVIEW_TYPERECORDHELPERS_H
 
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 
 namespace llvm {
-  namespace codeview {
-    /// Given an arbitrary codeview type, determine if it is an LF_STRUCTURE,
-    /// LF_CLASS, LF_INTERFACE, LF_UNION, or LF_ENUM with the forward ref class
-    /// option.
-    bool isUdtForwardRef(CVType CVT);
+
 
-    /// Given a CVType which is assumed to be an LF_MODIFIER, return the
-    /// TypeIndex of the type that the LF_MODIFIER modifies.
-    TypeIndex getModifiedType(const CVType &CVT);
+
+/// Return true if this record should be in the IPI stream of a PDB. In an
+/// object file, these record kinds will appear mixed into the .debug$T section.
+inline 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:
+  case TypeLeafKind::LF_BUILDINFO:
+  case TypeLeafKind::LF_UDT_SRC_LINE:
+  case TypeLeafKind::LF_UDT_MOD_SRC_LINE:
+    return true;
+  default:
+    return false;
   }
 }
 
+} // namespace codeview
+} // namespace llvm
+
 #endif

llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h"
 #include "llvm/DebugInfo/CodeView/MergingTypeTableBuilder.h"
 #include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
 #include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
+#include "llvm/DebugInfo/CodeView/TypeRecordHelpers.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;
private:
 
   Optional<uint32_t> PCHSignature;
 };
 
 } // end anonymous namespace
 
 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:
-  case TypeLeafKind::LF_BUILDINFO:
-  case TypeLeafKind::LF_UDT_SRC_LINE:
-  case TypeLeafKind::LF_UDT_MOD_SRC_LINE:
-    return true;
-  default:
-    return false;
-  }
-}
-
 void TypeStreamMerger::addMapping(TypeIndex Idx) {
   if (!IsSecondPass) {
     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;