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

48

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

50

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

99

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.

99

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 "SymbolTable.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);
-}
-
-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);
-}
-
-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);
-}
-
-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);
+namespace {
+template <class ELFT> class PrettyPrinter {
+public:
+  PrettyPrinter();
+  void print(raw_ostream &OS, ArrayRef<OutputSection *> OutputSections);
+
+private:
+  void writeInputSection(raw_ostream &OS, const InputSection *IS,
+                         StringRef &CurSection);
+
+  // Maps sections to their symbols.
+  DenseMap<const SectionBase *, SmallVector<DefinedRegular *, 4>> Symbols;
+
+  // Contains a string like this
+  //
+  //   0020100e 00000000     0                         f(int)
+  //
+  // for each symbol.
+  DenseMap<SymbolBody *, std::string> SymStr;
+};
+} // 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 std::string indent(int depth) { return std::string(depth * 8, ' '); }
+
+template <class ELFT> PrettyPrinter<ELFT>::PrettyPrinter() {
+  // Collect all symbols that we want to print out.
+  std::vector<DefinedRegular *> Syms;
+  for (elf::ObjectFile<ELFT> *File : Symtab<ELFT>::X->getObjectFiles())
+    for (SymbolBody *B : File->getSymbols())
+      if (B->File == File && !B->isSection())
+        if (auto *Sym = dyn_cast<DefinedRegular>(B))
+          if (Sym->Section)
+            Syms.push_back(Sym);
+
+  // Initialize the map from sections to their symbols.
+  for (DefinedRegular *Sym : Syms)
+    Symbols[Sym->Section].push_back(Sym);
+
+  // Sort symbols by address. We want to print out symbols in the
+  // order in the output file instead of the order they appeared
+  // in the input files.
+  for (auto &It : Symbols) {
+    SmallVectorImpl<DefinedRegular *> &V = It.second;
+    std::sort(V.begin(), V.end(), [](DefinedRegular *A, DefinedRegular *B) {
+      return A->getVA() < B->getVA();
+    });
+  }
+
+  // Construct a map from symbols to their stringified representations.
+  // Demangling symbols is slow, so we use the parallel-for.
+  std::vector<std::string> Str(Syms.size());
+  parallelFor(0, Syms.size(), [&](size_t I) {
+    raw_string_ostream OS(Str[I]);
+    writeHeader<ELFT>(OS, Syms[I]->getVA(), Syms[I]->template getSize<ELFT>(),
+                      0);
+    OS << indent(3) << left_justify(toString(*Syms[I]), 7) << '\n';
+  });
+  for (size_t I = 0, E = Syms.size(); I < E; ++I)
+    SymStr[Syms[I]] = Str[I];
 }
 
 template <class ELFT>
-static void writeInputSection(raw_fd_ostream &OS, const InputSection *IS,
-                              StringRef &PrevName) {
-  int Width = ELFT::Is64Bits ? 16 : 8;
+void PrettyPrinter<ELFT>::writeInputSection(raw_ostream &OS,
+                                            const InputSection *IS,
+                                            StringRef &CurSection) {
+  // 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
+  //
+  // once 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 << indent(1) << left_justify(Name, 7) << '\n';
+    CurSection = Name;
   }
 
+  // Write a line for each symbol defined 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';
-  }
+
+  writeHeader<ELFT>(OS, IS->OutSec->Addr + IS->OutSecOff, IS->getSize(),
+                    IS->Alignment);
+  OS << indent(2) << left_justify(toString(File), 7) << '\n';
+
+  for (DefinedRegular *Sym : Symbols[IS])
+    OS << SymStr[Sym];
 }
 
 template <class ELFT>
-static void writeMapFile2(raw_fd_ostream &OS,
+void PrettyPrinter<ELFT>::print(raw_ostream &OS,
                                 ArrayRef<OutputSection *> OutputSections) {
-  int Width = ELFT::Is64Bits ? 16 : 8;
-
-  OS << left_justify("Address", Width) << ' ' << left_justify("Size", Width)
+  // 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);
-    }
+    StringRef CurSection;
+    for (InputSection *IS : Sec->Sections)
+      writeInputSection(OS, IS, CurSection);
   }
 }
 
 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>().print(OS, OutputSections);
 }
 
 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
 nop
 .weak bar
 bar:
 .long bar - .
 .long zed - .
 local:
 .comm   common,4,16
 
 // CHECK:      Address          Size             Align Out     In      File    Symbol
 // CHECK-NEXT: 0000000000200158 0000000000000030     8 .eh_frame
 // CHECK-NEXT: 0000000000200158 0000000000000030     8         .eh_frame
 // CHECK-NEXT: 0000000000201000 0000000000000015     4 .text
 // CHECK-NEXT: 0000000000201000 000000000000000e     4         .text
 // CHECK-NEXT: 0000000000201000 000000000000000e     4                 {{.*}}{{/|\\}}map-file.s.tmp1.o
-// CHECK-NEXT: 000000000020100e 0000000000000000     0                         local
-// CHECK-NEXT: 0000000000201005 0000000000000000     0                         f(int)
 // CHECK-NEXT: 0000000000201000 0000000000000000     0                         _start
+// CHECK-NEXT: 0000000000201005 0000000000000000     0                         f(int)
+// CHECK-NEXT: 000000000020100e 0000000000000000     0                         local
 // CHECK-NEXT: 0000000000201010 0000000000000002     4                 {{.*}}{{/|\\}}map-file.s.tmp2.o
 // CHECK-NEXT: 0000000000201010 0000000000000000     0                         foo
 // CHECK-NEXT: 0000000000201011 0000000000000000     0                         bar
 // CHECK-NEXT: 0000000000201012 0000000000000000     1         .text.zed
 // CHECK-NEXT: 0000000000201012 0000000000000000     1                 {{.*}}{{/|\\}}map-file.s.tmp2.o
 // CHECK-NEXT: 0000000000201012 0000000000000000     0                         zed
 // CHECK-NEXT: 0000000000201014 0000000000000000     4         .text
 // CHECK-NEXT: 0000000000201014 0000000000000000     4                 {{.*}}{{/|\\}}map-file.s.tmp3.o