[ELF] - Speedup -r and --emit-relocs

[grimar]

Summary

This is "Bug 34688 - lld much slower than bfd when linking the linux kernel"

Inside copyRelocations() we have O(N*M) algorithm, where N - amount of
relocations and M - amount of symbols in symbol table. It isincredibly slow for linking linux kernel.

Patch creates local search tables to speedup.
With this fix link time goes for me from 12.95s to 0.55s what is almost 23x faster. (used release LLD).

[ruiu]

Honestly this doesn't look good. I cannot point out how you can improve it at the moment, but your new helper functions handle too low-level things. Such details shouldn't be leaked here.

[grimar]

• Reimplemented.

[grimar]

In D38129#877829, @ruiu wrote:

Honestly this doesn't look good. I cannot point out how you can improve it at the moment, but your new helper functions handle too low-level things. Such details shouldn't be leaked here.

What do you think about new version ? It incapsulates all low level logic inside SymbolTableSection class.

[grimar]

• Removed stale comment.

[ruiu]

ELF/SyntheticSections.cpp

1363

Flip the condition and swap then and else.

1366–1371

You should use lookup instead of find.

[grimar]

• Addressed review comments.

[ruiu]

ELF/SyntheticSections.cpp

1356–1358

is -> are
allow to -> allow us to

Probably a better comment is just: Initializes a symbol lookup table lazily. This is used only for -r or -emit-relocs.

1362–1365

I think the following comment suffices.

// Section symbols are mapped based on their output sections to maintain their semantics.

ELF/SyntheticSections.h

422–424 ↗

(On Diff #116505)

Rename OnceFlag, SymbolIndexMap and SectionIndexMap.

[grimar]

• Addressed review comments.

ELF/SyntheticSections.cpp

1356–1358

Used "Initializes a symbol lookup tables lazily. This is used only for -r or -emit-relocs.".

[ruiu]

LGTM

ELF/SyntheticSections.cpp

1356–1357

Remove "a".

ELF/InputSection.cpp

 }
 
 InputSectionBase *InputSection::getRelocatedSection() {
   assert(this->Type == SHT_RELA || this->Type == SHT_REL);
   ArrayRef<InputSectionBase *> Sections = this->File->getSections();
   return Sections[this->Info];
 }
 
+static DenseMap<SymbolBody *, size_t> createSymbolToIndexMap() {
+  DenseMap<SymbolBody *, size_t> Ret(InX::SymTab->getSymbols().size());
+  uint64_t I = 0;
+  for (const SymbolTableEntry &S : InX::SymTab->getSymbols())
+    Ret.insert({S.Symbol, ++I});
+  return Ret;
+}
+
+static DenseMap<OutputSection *, size_t> createSectionToIndexMap() {
+  ArrayRef<SymbolTableEntry> V = InX::SymTab->getSymbols();
+  DenseMap<OutputSection *, size_t> Ret(V.size());
+  for (size_t I = 0, E = V.size(); I != E; ++I)
+    if (V[I].Symbol->Type == STT_SECTION)
+      Ret.insert({V[I].Symbol->getOutputSection(), I + 1});
+  return Ret;
+}
+
 // This is used for -r and --emit-relocs. We can't use memcpy to copy
 // relocations because we need to update symbol table offset and section index
 // for each relocation. So we copy relocations one by one.
 template <class ELFT, class RelTy>
 void InputSection::copyRelocations(uint8_t *Buf, ArrayRef<RelTy> Rels) {
+  // Next mappings used for optimization. We have to create separate mapping for
+  // section symbols, because want to handle case when multiple section symbols
+  // being combined and them are not in symbol table.
+  static DenseMap<SymbolBody *, size_t> SymbolToIndex = createSymbolToIndexMap();
+  static DenseMap<OutputSection *, size_t> SectionToIndex = createSectionToIndexMap();
   InputSectionBase *RelocatedSection = getRelocatedSection();
 
-  // Loop is slow and have complexity O(N*M), where N - amount of
-  // relocations and M - amount of symbols in symbol table.
-  // That happens because getSymbolIndex(...) call below performs
-  // simple linear search.
   for (const RelTy &Rel : Rels) {
     uint32_t Type = Rel.getType(Config->IsMips64EL);
     SymbolBody &Body = this->getFile<ELFT>()->getRelocTargetSym(Rel);
 
     auto *P = reinterpret_cast<typename ELFT::Rela *>(Buf);
     Buf += sizeof(RelTy);
 
     if (Config->IsRela)
       P->r_addend = getAddend<ELFT>(Rel);
 
     // Output section VA is zero for -r, so r_offset is an offset within the
     // section, but for --emit-relocs it is an virtual address.
     P->r_offset = RelocatedSection->getOutputSection()->Addr +
                   RelocatedSection->getOffset(Rel.r_offset);
-    P->setSymbolAndType(InX::SymTab->getSymbolIndex(&Body), Type,
-                        Config->IsMips64EL);
+
+    size_t Sym = (Body.Type == STT_SECTION)
+                     ? SectionToIndex[Body.getOutputSection()]
+                     : SymbolToIndex[&Body];
+    P->setSymbolAndType(Sym, Type, Config->IsMips64EL);
 
     if (Body.Type == STT_SECTION) {
       // We combine multiple section symbols into only one per
       // section. This means we have to update the addend. That is
       // trivial for Elf_Rela, but for Elf_Rel we have to write to the
       // section data. We do that by adding to the Relocation vector.
 
       // .eh_frame is horribly special and can reference discarded sections. To

ELF/SyntheticSections.cpp

 void SymbolTableBaseSection::addSymbol(SymbolBody *B) {
   // Adding a local symbol to a .dynsym is a bug.
   assert(this->Type != SHT_DYNSYM || !B->isLocal());
 
   bool HashIt = B->isLocal();
   Symbols.push_back({B, StrTabSec.addString(B->getName(), HashIt)});
 }
 
 size_t SymbolTableBaseSection::getSymbolIndex(SymbolBody *Body) {
-  auto I = llvm::find_if(Symbols, [&](const SymbolTableEntry &E) {
-    if (E.Symbol == Body)
-      return true;
-    // This is used for -r, so we have to handle multiple section
-    // symbols being combined.
-    if (Body->Type == STT_SECTION && E.Symbol->Type == STT_SECTION)
-      return Body->getOutputSection() == E.Symbol->getOutputSection();
-    return false;
-  });
+  auto I = llvm::find_if(
+      Symbols, [&](const SymbolTableEntry &E) { return E.Symbol == Body; });
   if (I == Symbols.end())
     return 0;
   return I - Symbols.begin() + 1;
 }
 
 template <class ELFT>
 SymbolTableSection<ELFT>::SymbolTableSection(StringTableSection &StrTabSec)
     : SymbolTableBaseSection(StrTabSec) {
   this->Entsize = sizeof(Elf_Sym);
 }
 
 // Write the internal symbol table contents to the output symbol table.
 template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *Buf) {
   // The first entry is a null entry as per the ELF spec.
   Buf += sizeof(Elf_Sym);
 
   auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
 
   for (SymbolTableEntry &Ent : Symbols) {
     SymbolBody *Body = Ent.Symbol;