Speed up the -Map option.

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.

Differential Revision: https://reviews.llvm.org/D32631

llvm-svn: 301659

1 files changed, 103 insertions, 58 deletions

diff --git a/lld/ELF/MapFile.cpp b/lld/ELF/MapFile.cpp
index 31c8091bb6a..7cf328da593 100644
--- a/lld/ELF/MapFile.cpp
+++ b/lld/ELF/MapFile.cpp
@@ -24,6 +24,8 @@
 #include "MapFile.h"
 #include "InputFiles.h"
 #include "Strings.h"
+#include "SymbolTable.h"
+#include "Threads.h"
 
 #include "llvm/Support/raw_ostream.h"
 
@@ -33,82 +35,125 @@ 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);
+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 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 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 rather than 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();
+    });
+  }
 
-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 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]] = std::move(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,
-                          ArrayRef<OutputSection *> OutputSections) {
-  int Width = ELFT::Is64Bits ? 16 : 8;
-
-  OS << left_justify("Address", Width) << ' ' << left_justify("Size", Width)
+void PrettyPrinter<ELFT>::print(raw_ostream &OS,
+                                ArrayRef<OutputSection *> OutputSections) {
+  // 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);
   }
 }
 
@@ -122,7 +167,7 @@ void elf::writeMapFile(ArrayRef<OutputSection *> OutputSections) {
   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 *>);