ELF: New symbol table design.

This patch implements a new design for the symbol table that stores
SymbolBodies within a memory region of the Symbol object. Symbols are mutated
by constructing SymbolBodies in place over existing SymbolBodies, rather
than by mutating pointers. As mentioned in the initial proposal [1], this
memory layout helps reduce the cache miss rate by improving memory locality.

Performance numbers:

           old(s) new(s)
Without debug info:
chrome      7.178  6.432 (-11.5%)
LLVMgold.so 0.505  0.502 (-0.5%)
clang       0.954  0.827 (-15.4%)
llvm-as     0.052  0.045 (-15.5%)
With debug info:
scylla      5.695  5.613 (-1.5%)
clang      14.396 14.143 (-1.8%)

Performance counter results show that the fewer required indirections is
indeed the cause of the improved performance. For example, when linking
chrome, stalled cycles decreases from 14,556,444,002 to 12,959,238,310, and
instructions per cycle increases from 0.78 to 0.83. We are also executing
many fewer instructions (15,516,401,933 down to 15,002,434,310), probably
because we spend less time allocating SymbolBodies.

The new mechanism by which symbols are added to the symbol table is by calling
add* functions on the SymbolTable.

In this patch, I handle local symbols by storing them inside "unparented"
SymbolBodies. This is suboptimal, but if we do want to try to avoid allocating
these SymbolBodies, we can probably do that separately.

I also removed a few members from the SymbolBody class that were only being
used to pass information from the input file to the symbol table.

This patch implements the new design for the ELF linker only. I intend to
prepare a similar patch for the COFF linker.

[1] http://lists.llvm.org/pipermail/llvm-dev/2016-April/098832.html

Differential Revision: http://reviews.llvm.org/D19752

llvm-svn: 268178

1 files changed, 29 insertions, 31 deletions

diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index ca668ebe349..8fc2595b229 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -428,13 +428,8 @@ static int32_t findMipsPairedAddend(const uint8_t *Buf, const uint8_t *BufLoc,
 // True if non-preemptable symbol always has the same value regardless of where
 // the DSO is loaded.
 template <class ELFT> static bool isAbsolute(const SymbolBody &Body) {
-  Symbol *Sym = Body.Backref;
-  if (Body.isUndefined()) {
-    if (!Sym)
-      return false; // undefined local. That is the dummy symbol 0.
-    if (Sym->isWeak())
-      return true; // always 0
-  }
+  if (Body.isUndefined())
+    return !Body.isLocal() && Body.symbol()->isWeak();
   if (const auto *DR = dyn_cast<DefinedRegular<ELFT>>(&Body))
     return DR->Section == nullptr; // Absolute symbol.
   return false;
@@ -771,7 +766,7 @@ static void reportUndefined(SymbolTable<ELFT> &Symtab, SymbolBody *Sym) {
     if (Config->Relocatable)
       return;
     if (Config->Shared)
-      if (Sym->Backref->Visibility == STV_DEFAULT)
+      if (Sym->symbol()->Visibility == STV_DEFAULT)
         return;
   }
 
@@ -1022,15 +1017,19 @@ void Writer<ELFT>::addCopyRelSymbol(SharedSymbol<ELFT> *SS) {
   Out<ELFT>::Bss->updateAlign(Align);
   uintX_t Shndx = SS->Sym.st_shndx;
   uintX_t Value = SS->Sym.st_value;
-  // Look through the DSO's dynamic symbol for aliases and create a dynamic
-  // symbol for each one. This causes the copy relocation to correctly interpose
-  // any aliases.
-  for (SharedSymbol<ELFT> &S : SS->File->getSharedSymbols()) {
-    if (S.Sym.st_shndx != Shndx || S.Sym.st_value != Value)
+  // Look through the DSO's dynamic symbol table for aliases and create a
+  // dynamic symbol for each one. This causes the copy relocation to correctly
+  // interpose any aliases.
+  for (const Elf_Sym &S : SS->File->getElfSymbols(true)) {
+    if (S.st_shndx != Shndx || S.st_value != Value)
+      continue;
+    auto *Alias = dyn_cast_or_null<SharedSymbol<ELFT>>(
+        Symtab.find(check(S.getName(SS->File->getStringTable()))));
+    if (!Alias)
       continue;
-    S.OffsetInBss = Off;
-    S.NeedsCopyOrPltAddr = true;
-    S.Backref->IsUsedInRegularObj = true;
+    Alias->OffsetInBss = Off;
+    Alias->NeedsCopyOrPltAddr = true;
+    Alias->symbol()->IsUsedInRegularObj = true;
   }
   Out<ELFT>::RelaDyn->addReloc(
       {Target->CopyRel, Out<ELFT>::Bss, SS->OffsetInBss, false, SS, 0});
@@ -1067,9 +1066,9 @@ bool Writer<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) const {
 }
 
 template <class ELFT>
-static SymbolBody *
-addOptionalSynthetic(SymbolTable<ELFT> &Table, StringRef Name,
-                     OutputSectionBase<ELFT> &Sec, typename ELFT::uint Val) {
+static Symbol *addOptionalSynthetic(SymbolTable<ELFT> &Table, StringRef Name,
+                                    OutputSectionBase<ELFT> &Sec,
+                                    typename ELFT::uint Val) {
   if (!Table.find(Name))
     return nullptr;
   return Table.addSynthetic(Name, Sec, Val);
@@ -1085,16 +1084,15 @@ template <class ELFT> void Writer<ELFT>::addRelIpltSymbols() {
   if (isOutputDynamic() || !Out<ELFT>::RelaPlt)
     return;
   StringRef S = Config->Rela ? "__rela_iplt_start" : "__rel_iplt_start";
-  ElfSym<ELFT>::RelaIpltStart =
-      addOptionalSynthetic(Symtab, S, *Out<ELFT>::RelaPlt, 0);
+  addOptionalSynthetic(Symtab, S, *Out<ELFT>::RelaPlt, 0);
 
   S = Config->Rela ? "__rela_iplt_end" : "__rel_iplt_end";
-  ElfSym<ELFT>::RelaIpltEnd = addOptionalSynthetic(
-      Symtab, S, *Out<ELFT>::RelaPlt, DefinedSynthetic<ELFT>::SectionEnd);
+  addOptionalSynthetic(Symtab, S, *Out<ELFT>::RelaPlt,
+                       DefinedSynthetic<ELFT>::SectionEnd);
 }
 
 template <class ELFT> static bool includeInSymtab(const SymbolBody &B) {
-  if (!B.Backref->IsUsedInRegularObj)
+  if (!B.symbol()->IsUsedInRegularObj)
     return false;
 
   if (auto *D = dyn_cast<DefinedRegular<ELFT>>(&B)) {
@@ -1191,19 +1189,19 @@ template <class ELFT> void Writer<ELFT>::addReservedSymbols() {
     // so that it points to an absolute address which is relative to GOT.
     // See "Global Data Symbols" in Chapter 6 in the following document:
     // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
-    ElfSym<ELFT>::MipsGp =
-        Symtab.addSynthetic("_gp", *Out<ELFT>::Got, MipsGPOffset);
+    Symtab.addSynthetic("_gp", *Out<ELFT>::Got, MipsGPOffset);
 
     // On MIPS O32 ABI, _gp_disp is a magic symbol designates offset between
     // start of function and 'gp' pointer into GOT.
     ElfSym<ELFT>::MipsGpDisp =
-        addOptionalSynthetic(Symtab, "_gp_disp", *Out<ELFT>::Got, MipsGPOffset);
+        addOptionalSynthetic(Symtab, "_gp_disp", *Out<ELFT>::Got, MipsGPOffset)
+            ->body();
     // The __gnu_local_gp is a magic symbol equal to the current value of 'gp'
     // pointer. This symbol is used in the code generated by .cpload pseudo-op
     // in case of using -mno-shared option.
     // https://sourceware.org/ml/binutils/2004-12/msg00094.html
-    ElfSym<ELFT>::MipsLocalGp = addOptionalSynthetic(
-        Symtab, "__gnu_local_gp", *Out<ELFT>::Got, MipsGPOffset);
+    addOptionalSynthetic(Symtab, "__gnu_local_gp", *Out<ELFT>::Got,
+                         MipsGPOffset);
   }
 
   // In the assembly for 32 bit x86 the _GLOBAL_OFFSET_TABLE_ symbol
@@ -1363,7 +1361,7 @@ template <class ELFT> void Writer<ELFT>::createSections() {
   // synthesized ones. Visit all symbols to give the finishing touches.
   std::vector<DefinedCommon *> CommonSymbols;
   for (Symbol *S : Symtab.getSymbols()) {
-    SymbolBody *Body = S->Body;
+    SymbolBody *Body = S->body();
 
     // Set "used" bit for --as-needed.
     if (S->IsUsedInRegularObj && !S->isWeak())
@@ -1781,7 +1779,7 @@ static uint32_t getMipsEFlags(bool Is64Bits) {
 
 template <class ELFT> static typename ELFT::uint getEntryAddr() {
   if (Symbol *S = Config->EntrySym)
-    return S->Body->getVA<ELFT>();
+    return S->body()->getVA<ELFT>();
   if (Config->EntryAddr != uint64_t(-1))
     return Config->EntryAddr;
   return 0;