/redundancyReport proof of concept

[thakis]

Summary

I don't think we want to check this in, but maybe lld should have a feature that's kind of like this one [1].

During a C++ compilation, inline functions can be codegen'd into many .o files, only to be then merged by the linker. If a class is dllexported, _all_ its inline member functions get codegen'd into _every_ TU that includes the header declaring the class. This generates lots of redundant work that can often be saved fairly easily, but there's currently no good way to ask the linker which inline functions have the "most" redundancy. This patch adds a "/redundancyReport:file" flag to lld-link. If present, lld-link will write a line with the three columns containing "total number of redundantly codegen'd bytes due to function, number of times function was present in linked-in obj files, name of function" for each function, sorted by total redundancy.

With some python scripts doing pretty heavy postprocessing of lld-link's output, I was able to reduce link.exe's memory consumption for linking blink_core.dll by 600MB / 6%, and the size of blink_core.ilk (which link.exe uses to do incremental linking) by 20%, see https://bugs.chromium.org/p/chromium/issues/detail?id=560475#c60 and the following 10 or so comments. Since so much post processing was needed, we probably don't want this feature, but maybe something like it. So just putting this out there in case someone else has a good idea upon seeing it.

1: https://www.youtube.com/watch?v=COCmaZA3d08

[ruiu]

This is interesting. If we could make the output of this feature usable, and if the feature is useful for other applications than chromium, it might be useful to add this feature to the linker. I'd create a new subdirectory analysis under COFF and put this code there.

[pcc]

I'm wondering whether .ilk size is mostly a factor of the #sections rather than the size of each section. If so, it may be simpler to create the redundancy report by counting the number of "comdat discarded" messages.

[dblaikie]

Neat!

I've done this without linker support (scraping objdump -s output, glomming it together with python, etc) to assess the impact of modular codegen, which can remove some of this redundancy. Be happy to give this version a whirl.

Does this measure redundancy in objects that don't end up linked? (eg: a library dependency where some of the objects go unused) Maybe not a big deal, perhaps their distribution of redundancy would be about the same as the rest of the population, so it wouldn't skew the results much...

COFF/Chunks.cpp

 
 bool SectionChunk::isCOMDAT() const {
   return Header->Characteristics & IMAGE_SCN_LNK_COMDAT;
 }
 
 void SectionChunk::printDiscardedMessage() const {
   // Removed by dead-stripping. If it's removed by ICF, ICF already
   // printed out the name, so don't repeat that here.
+// XXX
   if (Sym && this == Repl) {
     if (Discarded)
       message("Discarded comdat symbol " + Sym->getName());
     else if (!Live)
       message("Discarded " + Sym->getName());
   }
 }
 

COFF/Config.h

struct Configuration {
   std::map<StringRef, StringRef> MustMatch;
 
   // Used for /alternatename.
   std::map<StringRef, StringRef> AlternateNames;
 
   // Used for /lldmap.
   std::string MapFile;
 
+  // Used for /redundancyReport.
+  std::string RedudancyReportFile;
+
   uint64_t ImageBase = -1;
   uint64_t StackReserve = 1024 * 1024;
   uint64_t StackCommit = 4096;
   uint64_t HeapReserve = 1024 * 1024;
   uint64_t HeapCommit = 4096;
   uint32_t MajorImageVersion = 0;
   uint32_t MinorImageVersion = 0;
   uint32_t MajorOSVersion = 6;

COFF/Driver.cpp

void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
   if (Args.hasArg(OPT_nxcompat_no))
     Config->NxCompat = false;
   if (Args.hasArg(OPT_tsaware_no))
     Config->TerminalServerAware = false;
   if (Args.hasArg(OPT_nosymtab))
     Config->WriteSymtab = false;
 
   Config->MapFile = getMapFile(Args);
+  if (auto *Arg = Args.getLastArg(OPT_redundancyReport))
+    Config->RedudancyReportFile = Arg->getValue();
 
   if (ErrorCount)
     return;
 
   // Create a list of input files. Files can be given as arguments
   // for /defaultlib option.
   std::vector<MemoryBufferRef> MBs;
   for (auto *Arg : Args.filtered(OPT_INPUT))

COFF/Options.td

 // LLD extensions
 def nopdb : F<"nopdb">, HelpText<"Disable PDB generation for DWARF users">;
 def nosymtab : F<"nosymtab">;
 def msvclto : F<"msvclto">;
 
 // Flags for debugging
 def lldmap : F<"lldmap">;
 def lldmap_file : Joined<["/", "-"], "lldmap:">;
+def redundancyReport: Joined<["/", "-"], "redundancyReport:">;
 
 //==============================================================================
 // The flags below do nothing. They are defined only for link.exe compatibility.
 //==============================================================================
 
 class QF<string name> : Joined<["/", "-", "-?"], name#":">;
 
 multiclass QB<string name> {

COFF/SymbolTable.cpp

Symbol *SymbolTable::addRegular(InputFile *F, StringRef N, bool IsCOMDAT,
   if (!isa<BitcodeFile>(F))
     S->IsUsedInRegularObj = true;
   SymbolPreference SP = compareDefined(S, WasInserted, IsCOMDAT);
   if (SP == SP_CONFLICT) {
     reportDuplicate(S, F);
   } else if (SP == SP_NEW) {
     replaceBody<DefinedRegular>(S, F, N, IsCOMDAT, /*IsExternal*/ true, Sym, C);
   } else if (SP == SP_EXISTING && IsCOMDAT && C) {
+// XXX here?
     C->markDiscarded();
     // Discard associative chunks that we've parsed so far. No need to recurse
     // because an associative section cannot have children.
     for (SectionChunk *Child : C->children())
       Child->markDiscarded();
   }
   return S;
 }

COFF/Writer.cpp

private:
   void createSymbolAndStringTable();
   void openFile(StringRef OutputPath);
   template <typename PEHeaderTy> void writeHeader();
   void fixSafeSEHSymbols();
   void setSectionPermissions();
   void writeSections();
   void sortExceptionTable();
   void writeBuildId();
+  void writeRedundancyReport();
 
   llvm::Optional<coff_symbol16> createSymbol(Defined *D);
   size_t addEntryToStringTable(StringRef Str);
 
   OutputSection *findSection(StringRef Name);
   OutputSection *createSection(StringRef Name);
   void addBaserels(OutputSection *Dest);
   void addBaserelBlocks(OutputSection *Dest, std::vector<Baserel> &V);
void Writer::run() {
   if (!Config->PDBPath.empty() && Config->Debug) {
     const llvm::codeview::DebugInfo *DI = nullptr;
     if (Config->DebugTypes & static_cast<unsigned>(coff::DebugType::CV))
       DI = BuildId->DI;
     createPDB(Symtab, OutputSections, SectionTable, DI);
   }
 
   writeMapFile(OutputSections);
+  writeRedundancyReport();
 
   if (auto EC = Buffer->commit())
     fatal(EC, "failed to write the output file");
 }
 
 static StringRef getOutputSection(StringRef Name) {
   StringRef S = Name.split('$').first;
   auto It = Config->Merge.find(S);

 
 Optional<coff_symbol16> Writer::createSymbol(Defined *Def) {
   // Relative symbols are unrepresentable in a COFF symbol table.
   if (isa<DefinedSynthetic>(Def))
     return None;
 
   // Don't write dead symbols or symbols in codeview sections to the symbol
   // table.
+  // XXX but do include them in stats
   if (!Def->isLive())
     return None;
   if (auto *D = dyn_cast<DefinedRegular>(Def))
     if (D->getChunk()->isCodeView())
       return None;
 
   coff_symbol16 Sym;
   StringRef Name = Def->getName();
void Writer::writeBuildId() {
   // Compute an MD5 hash.
   ArrayRef<uint8_t> Buf(Buffer->getBufferStart(), Buffer->getBufferEnd());
   memcpy(BuildId->DI->PDB70.Signature, MD5::hash(Buf).data(), 16);
 
   // TODO(compnerd) track the Age
   BuildId->DI->PDB70.Age = 1;
 }
 
+void Writer::writeRedundancyReport() {
+  if (Config->RedudancyReportFile.empty())
+    return;
+
+  FILE* f = fopen(Config->RedudancyReportFile.c_str(), "wb");
+
+  // First, bin chunks by name.
+  // XXX i think this misses stuff from .obj files never added to the link.
+  // probably fine.
+  struct Entry {
+    int total_size = 0;
+    int count = 0;
+  };
+  std::map<StringRef, Entry> Map;
+  for (Chunk *C : Symtab->getChunks()) {
+    auto *SC = dyn_cast<SectionChunk>(C);
+    if (!SC || SC->isLive())
+      continue;
+
+    Entry& e = Map[C->getDebugName()];
+    e.count++;
+    e.total_size += SC->getSize();
+  }
+
+  std::vector<std::pair<StringRef, Entry>> Entries(Map.begin(), Map.end());
+  std::sort(Entries.begin(), Entries.end(),
+            [](const std::pair<StringRef, Entry> &a,
+               const std::pair<StringRef, Entry> &b) {
+              return a.second.total_size > b.second.total_size;
+            });
+
+  for (const std::pair<StringRef, Entry>& E : Entries) {
+    fprintf(f, "%d\t%d\t%.*s\n", E.second.total_size, E.second.count,
+            (int)E.first.size(), E.first.data());
+  }
+  fclose(f);
+}
+
 OutputSection *Writer::findSection(StringRef Name) {
   for (OutputSection *Sec : OutputSections)
     if (Sec->getName() == Name)
       return Sec;
   return nullptr;
 }
 
 uint32_t Writer::getSizeOfInitializedData() {