Speed up the -Map option.

[ruiu]

Summary

We found that some part of code for the -Map option takes O(m*n)
where m is the number of input sections in some file and n is
the number of symbols in the same file. If you do LTO, we usually
have only a few object files as inputs for the -Map option
feature, so this performance characteristic was worse than I
expected.

This patch rewrites the -Map option feature to speed it up.
I eliminated the O(m*n) bottleneck and also used multi-threading.

As a result, clang link time with the -Map option improved from
18.7 seconds to 11.2 seconds. Without -Map, it takes 7.7 seconds,
so the -Map option is now about 3x faster than before for this
test case (from 11.0 seconds to 3.5 seconds.) The generated output
file size was 223 MiB, and the file contains 1.2M lines.

[ruiu]

• Fix indentation errors and add -strict-whitespace to FileCheck to catch that kind of errors.

[dberris]

lld/ELF/MapFile.cpp

50

No SmallVector<...> ?

[ruiu]

lld/ELF/MapFile.cpp

50

Does it make any noticeable difference? I usually use data structures in the standard library unless that is not appropriate because most people are more familiar with std::* than llvm:*.

[dberris]

lld/ELF/MapFile.cpp

50

I suspect it should, especially if you size the SmallVector with enough values to not require an additional indirection when reaching for the values. It should be easy to measure, given that you already have a test case. :)

[ruiu]

lld/ELF/MapFile.cpp

50

OK, let me do that tomorrow.

[pcc]

Another idea I had for eliminating the O(m * n) behaviour was to collect a list of symbols (externals from the global symbol table and internals from the input files), sort it by VA, and print it in order, emitting input and output section lines whenever either of them changes. That would still be O(n * log n) like your solution, but I think it would have a few other benefits (e.g. it would make it easier to print absolute and synthetic symbols). We can think about doing that separately, though.

lld/ELF/MapFile.cpp

50

I think the key type of this map could be const InputSection *.

92

I think you can enumerate Symtab<ELFT>::X->getObjectFiles() instead here.

116

Can you avoid calling this function twice?

[ruiu]

• Address review comments.

[ruiu]

Yes, I think we do not have a multimap in LLVM. I could use std::unordered_multimap, but that's probably slower than DenseMap<T, std::vector<U>>.

lld/ELF/MapFile.cpp

50

It actually cannot.

50

Changing the type from std::vector to SmallVector sped it up by a few hundred milliseconds for the clang test case, so that actually mattered.

116

Done.

[ruiu]

I implemented Peter's suggestion to collect all symbols first, and then print them out in the increasing VA order. It turned out that doesn't print out all output sections because some sections doesn't have symbols at all. For example, .eh_frame doesn't have any symbols that point to the section. There might be some way to handle this, but I'll leave it alone for now.

[pcc]

LGTM

lld/ELF/MapFile.cpp

 // 0020100e 00000000     0                         local
 // 00201005 00000000     0                         f(int)
 //
 //===----------------------------------------------------------------------===//
 
 #include "MapFile.h"
 #include "InputFiles.h"
 #include "Strings.h"
+#include "Threads.h"
 
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 using namespace llvm::object;
 
 using namespace lld;
 using namespace lld::elf;
 
-static void writeOutSecLine(raw_fd_ostream &OS, int Width, uint64_t Address,
-                            uint64_t Size, uint64_t Align, StringRef Name) {
-  OS << format("%0*llx %0*llx %5lld ", Width, Address, Width, Size, Align)
-     << left_justify(Name, 7);
+namespace {
+template <class ELFT> class PrettyPrinter {
+public:
+  PrettyPrinter(ArrayRef<OutputSection *> OutputSections);
+  void print(raw_ostream &OS);
+
+private:
+  void writeInputSection(raw_ostream &OS, const InputSection *IS);
+
+  // All output sections.
+  ArrayRef<OutputSection *> OutputSections;
+
+  // Maps sections to their symbols.
+  DenseMap<const SectionBase *, std::vector<SymbolBody *>> Symbols;
+
+  // Contains a string like this
+  //
+  //   0020100e 00000000     0                         f(int)
+  //
+  // for each symbol. Since constructing strings containing demangled
+  // symbols is slow, we create this map in batch using multiple
+  // threads.
+  DenseMap<SymbolBody *, std::string> SymStr;
+
+  // Current input section name. We want to print out a line like
+  //
+  //   Address  Size     Align Out     In      File    Symbol
+  //   =================================================================
+  //   00201000 00000015     4 .text
+  //   00201000 0000000e     4         .text             <----- THIS
+  //   00201000 0000000e     4                 test.o
+  //
+  // only once for each input section.
+  StringRef CurSection;
+};
+} // namespace
+
+// Print out the first three columns of a line.
+template <class ELFT>
+static void writeHeader(raw_ostream &OS, uint64_t Addr, uint64_t Size,
+                        uint64_t Align) {
+  int W = ELFT::Is64Bits ? 16 : 8;
+  OS << format("%0*llx %0*llx %5lld ", W, Addr, W, Size, Align);
 }
 
-static void writeInSecLine(raw_fd_ostream &OS, int Width, uint64_t Address,
-                           uint64_t Size, uint64_t Align, StringRef Name) {
-  // Pass an empty name to align the text to the correct column.
-  writeOutSecLine(OS, Width, Address, Size, Align, "");
-  OS << ' ' << left_justify(Name, 7);
+// Returns all symbols that we want to print out.
+template <class ELFT>
+static std::vector<DefinedRegular *> getSymbols(ArrayRef<OutputSection *> V) {
+  DenseSet<elf::ObjectFile<ELFT> *> Files;
+  for (OutputSection *OSec : V)
+    for (InputSection *ISec : OSec->Sections)
+      if (elf::ObjectFile<ELFT> *File = ISec->template getFile<ELFT>())
+        Files.insert(File);
+
+  std::vector<DefinedRegular *> Ret;
+  for (elf::ObjectFile<ELFT> *File : Files)
+    for (SymbolBody *B : File->getSymbols())
+      if (B->File == File && !B->isSection())
+        if (auto *Sym = dyn_cast<DefinedRegular>(B))
+          if (Sym->Section)
+            Ret.push_back(Sym);
+  return Ret;
 }
 
-static void writeFileLine(raw_fd_ostream &OS, int Width, uint64_t Address,
-                          uint64_t Size, uint64_t Align, StringRef Name) {
-  // Pass an empty name to align the text to the correct column.
-  writeInSecLine(OS, Width, Address, Size, Align, "");
-  OS << ' ' << left_justify(Name, 7);
+// Returns a map from sections to their symbols.
+template <class ELFT>
+static DenseMap<const SectionBase *, std::vector<SymbolBody *>>
+groupSymbols(ArrayRef<OutputSection *> V) {
+  DenseMap<const SectionBase *, std::vector<SymbolBody *>> Map;
+  for (DefinedRegular *Sym : getSymbols<ELFT>(V))
+    Map[Sym->Section].push_back(Sym);
+  return Map;
 }
 
-static void writeSymbolLine(raw_fd_ostream &OS, int Width, uint64_t Address,
-                            uint64_t Size, StringRef Name) {
-  // Pass an empty name to align the text to the correct column.
-  writeFileLine(OS, Width, Address, Size, 0, "");
-  OS << ' ' << left_justify(Name, 7);
+// Construct a map from symbols to their stringified representation.
+// Demangling symbols is slow, so we use multi-threads in this function.
+template <class ELFT>
+static DenseMap<SymbolBody *, std::string>
+formatSymbols(ArrayRef<OutputSection *> V) {
+  std::vector<DefinedRegular *> Syms = getSymbols<ELFT>(V);
+
+  std::vector<std::string> Res(Syms.size());
+  parallelFor(0, Syms.size(), [&](size_t I) {
+    raw_string_ostream OS(Res[I]);
+    writeHeader<ELFT>(OS, Syms[I]->getVA(), Syms[I]->getSize<ELFT>(), 0);
+    OS << "                        "
+       << left_justify(toString(*Syms[I]), 7) << '\n';
+  });
+
+  DenseMap<SymbolBody *, std::string> Map;
+  for (size_t I = 0, E = Syms.size(); I < E; ++I)
+    Map[Syms[I]] = Res[I];
+  return Map;
 }
 
 template <class ELFT>
-static void writeInputSection(raw_fd_ostream &OS, const InputSection *IS,
-                              StringRef &PrevName) {
-  int Width = ELFT::Is64Bits ? 16 : 8;
+PrettyPrinter<ELFT>::PrettyPrinter(ArrayRef<OutputSection *> V)
+    : OutputSections(V), Symbols(groupSymbols<ELFT>(V)),
+      SymStr(formatSymbols<ELFT>(V)) {}
+
+template <class ELFT>
+void PrettyPrinter<ELFT>::writeInputSection(raw_ostream &OS,
+                                            const InputSection *IS) {
+  // Write an input section header line for each new input section.
   StringRef Name = IS->Name;
-  if (Name != PrevName) {
-    writeInSecLine(OS, Width, IS->OutSec->Addr + IS->OutSecOff, IS->getSize(),
-                   IS->Alignment, Name);
-    OS << '\n';
-    PrevName = Name;
+  if (Name != CurSection) {
+    writeHeader<ELFT>(OS, IS->OutSec->Addr + IS->OutSecOff, IS->getSize(),
+                      IS->Alignment);
+    OS << "        " << left_justify(Name, 7) << '\n';
+    CurSection = Name;
   }
 
+  // Write a line for each symbol in the given section.
   elf::ObjectFile<ELFT> *File = IS->template getFile<ELFT>();
   if (!File)
     return;
-  writeFileLine(OS, Width, IS->OutSec->Addr + IS->OutSecOff, IS->getSize(),
-                IS->Alignment, toString(File));
-  OS << '\n';
-
-  for (SymbolBody *Sym : File->getSymbols()) {
-    auto *DR = dyn_cast<DefinedRegular>(Sym);
-    if (!DR)
-      continue;
-    if (DR->Section != IS)
-      continue;
-    if (DR->isSection())
-      continue;
-    writeSymbolLine(OS, Width, Sym->getVA(), Sym->getSize<ELFT>(),
-                    toString(*Sym));
-    OS << '\n';
-  }
-}
 
-template <class ELFT>
-static void writeMapFile2(raw_fd_ostream &OS,
-                          ArrayRef<OutputSection *> OutputSections) {
-  int Width = ELFT::Is64Bits ? 16 : 8;
+  writeHeader<ELFT>(OS, IS->OutSec->Addr + IS->OutSecOff, IS->getSize(),
+                    IS->Alignment);
+  OS << "                " << left_justify(toString(File), 7) << '\n';
+
+  for (SymbolBody *B : Symbols[IS])
+    OS << SymStr[B];
+}
 
-  OS << left_justify("Address", Width) << ' ' << left_justify("Size", Width)
+template <class ELFT> void PrettyPrinter<ELFT>::print(raw_ostream &OS) {
+  // Print out the header line.
+  int W = ELFT::Is64Bits ? 16 : 8;
+  OS << left_justify("Address", W) << ' ' << left_justify("Size", W)
      << " Align Out     In      File    Symbol\n";
 
+  // Print out a mapfile.
   for (OutputSection *Sec : OutputSections) {
-    writeOutSecLine(OS, Width, Sec->Addr, Sec->Size, Sec->Alignment, Sec->Name);
-    OS << '\n';
+    writeHeader<ELFT>(OS, Sec->Addr, Sec->Size, Sec->Alignment);
+    OS << left_justify(Sec->Name, 7) << '\n';
 
-    StringRef PrevName = "";
-    for (InputSection *IS : Sec->Sections) {
-      writeInputSection<ELFT>(OS, IS, PrevName);
-    }
+    CurSection = "";
+    for (InputSection *IS : Sec->Sections)
+      writeInputSection(OS, IS);
   }
 }
 
 template <class ELFT>
 void elf::writeMapFile(ArrayRef<OutputSection *> OutputSections) {
   if (Config->MapFile.empty())
     return;
 
   std::error_code EC;
   raw_fd_ostream OS(Config->MapFile, EC, sys::fs::F_None);
   if (EC)
     error("cannot open " + Config->MapFile + ": " + EC.message());
   else
-    writeMapFile2<ELFT>(OS, OutputSections);
+    PrettyPrinter<ELFT>(OutputSections).print(OS);
 }
 
 template void elf::writeMapFile<ELF32LE>(ArrayRef<OutputSection *>);
 template void elf::writeMapFile<ELF32BE>(ArrayRef<OutputSection *>);
 template void elf::writeMapFile<ELF64LE>(ArrayRef<OutputSection *>);
 template void elf::writeMapFile<ELF64BE>(ArrayRef<OutputSection *>);

lld/test/ELF/map-file.s

 // REQUIRES: x86
 
 // RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t1.o
 // RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %p/Inputs/map-file2.s -o %t2.o
 // RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %p/Inputs/map-file3.s -o %t3.o
 // RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %p/Inputs/map-file4.s -o %t4.o
 // RUN: rm -f %t4.a
 // RUN: llvm-ar rc %t4.a %t4.o
-// RUN: ld.lld %t1.o %t2.o %t3.o %t4.a -o %t -M | FileCheck %s
-// RUN: ld.lld %t1.o %t2.o %t3.o %t4.a -o %t -print-map | FileCheck %s
+// RUN: ld.lld %t1.o %t2.o %t3.o %t4.a -o %t -M | FileCheck -strict-whitespace %s
+// RUN: ld.lld %t1.o %t2.o %t3.o %t4.a -o %t -print-map | FileCheck -strict-whitespace  %s
 // RUN: ld.lld %t1.o %t2.o %t3.o %t4.a -o %t -Map=%t.map
-// RUN: FileCheck %s < %t.map
+// RUN: FileCheck -strict-whitespace  %s < %t.map
 
 .global _start
 _start:
         call baz
 .global _Z1fi
 _Z1fi:
 .cfi_startproc
 .cfi_endproc