[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

1364 ↗

(On Diff #116348)

Flip the condition and swap then and else.

1375–1380 ↗

(On Diff #116348)

You should use lookup instead of find.

[grimar]

• Addressed review comments.

[ruiu]

ELF/SyntheticSections.cpp

1358–1360 ↗

(On Diff #116505)

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.

1372–1375 ↗

(On Diff #116505)

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

1358–1360 ↗

(On Diff #116505)

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

[ruiu]

LGTM

ELF/SyntheticSections.cpp

1358 ↗

(On Diff #116650)

Remove "a".

lld/trunk/ELF/InputSection.cpp

 }
 
 // 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) {
   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)

lld/trunk/ELF/SyntheticSections.h

public:
   size_t getSymbolIndex(SymbolBody *Body);
   ArrayRef<SymbolTableEntry> getSymbols() const { return Symbols; }
 
 protected:
   // A vector of symbols and their string table offsets.
   std::vector<SymbolTableEntry> Symbols;
 
   StringTableSection &StrTabSec;
+
+  llvm::once_flag OnceFlag;
+  llvm::DenseMap<SymbolBody *, size_t> SymbolIndexMap;
+  llvm::DenseMap<OutputSection *, size_t> SectionIndexMap;
 };
 
 template <class ELFT>
 class SymbolTableSection final : public SymbolTableBaseSection {
   typedef typename ELFT::Sym Elf_Sym;
 
 public:
   SymbolTableSection(StringTableSection &StrTabSec);

lld/trunk/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;
+  // Initializes symbol lookup tables lazily. This is used only
+  // for -r or -emit-relocs.
+  llvm::call_once(OnceFlag, [&] {
+    SymbolIndexMap.reserve(Symbols.size());
+    size_t I = 0;
+    for (const SymbolTableEntry &E : Symbols) {
+      if (E.Symbol->Type == STT_SECTION)
+        SectionIndexMap[E.Symbol->getOutputSection()] = ++I;
+      else
+        SymbolIndexMap[E.Symbol] = ++I;
+    }
   });
-  if (I == Symbols.end())
-    return 0;
-  return I - Symbols.begin() + 1;
+
+  // Section symbols are mapped based on their output sections
+  // to maintain their semantics.
+  if (Body->Type == STT_SECTION)
+    return SectionIndexMap.lookup(Body->getOutputSection());
+  return SymbolIndexMap.lookup(Body);
 }
 
 template <class ELFT>
 SymbolTableSection<ELFT>::SymbolTableSection(StringTableSection &StrTabSec)
     : SymbolTableBaseSection(StrTabSec) {
   this->Entsize = sizeof(Elf_Sym);
 }