Speed up --start-lib and --end-lib.

[ruiu]

Summary

--{start,end}-lib give files grouped by the options the archive file
semantics. That is, each object file between them acts as if it were
in an archive file whose sole member is the file.

Therefore, files between --{start,end}-lib are linked to the final
output only if they are needed to resolve some undefined symbols.

Previously, the feature was implemented this way:

1. We read a symbol table and insert defined symbols to the symbol table as lazy symbols.
2. If an undefind symbol is resolved to a lazy symbol, that lazy symbol instantiate ObjFile class for that symbol, which re-insert all defined symbols to the symbol table.

So, if an ObjFile is instantiated, defined symbols are inserted to the
symbol table twice. Since inserting long symbol names is not cheap,
there's a room to optimize here.

This patch optimzies it. Now, LazyObjFile remembers symbol handles and
passed them over to a new ObjFile instance, so that the ObjFile
doesn't insert the same strings.

Here is a quick benchmark to link clang. "Original" is the original
lld with unmodified command line options. For "With" and "Without", I
extracted all files from archive files and replace .a's in a command
line with .o's wrapped with --{start,end}-lib.

    With this patch: 5.674s (+0.0%)
Withtout this patch: 6.087s (+7.2%)
           Original: 5.886s (+3.7%)

So, interestingly, --{start,end}-lib are now faster than the regular
linking scheme with archive files. That's perhaps not too surprising,
though, because for regular archive files, we look up the symbol table
with the same string twice.

[ruiu]

• remove dead declaration

[MaskRay]

This is interesting! I'll take a closer look tomorrow

lld/ELF/InputFiles.cpp

995

Missing default:

[ruiu]

lld/ELF/InputFiles.cpp

995

Does this have to be exhaustive? We have a fatal after this switch. Anyways, I think I can rewrite this with if.

[ruiu]

• address review comment

[ruiu]

• rebase

[MaskRay]

In LazyObjFile::parse():

for (size_t I = FirstGlobal, End = ESyms.size(); I != End; ++I)
  if (ESyms[I].st_shndx != SHN_UNDEF)
    // resolveSymbol() called by addSymbol() checks if the symbol was originally undefined.
    // If that is the case, addSymbol() will transitively call SymbolTable::fetchLazy, which calls LazyObjFile::fetch().
    this->Symbols[I] = Symtab->addSymbol(
        LazyObject{*this, CHECK(ESyms[I].getName(Strtab), this)});
return;

In LazyObjFile::parse():

// Symbols[0,I) are inherited from LazyObjFile::parse(), other entries are nullptr.
// This has another problem: it increases memory usage.
// The copy assignment cannot be replaced with move assignment, because
// parse() will continue processing Symbols[I+1] Symbols[I+2] ...
File->Symbols = Symbols;

I think in most cases (that are not flagged by --warn-backrefs), this may not have a perceivable improvement in the current form. Actually,
For an (input: 4.2G; output: 1.6G) executable, I measure a performance regression, 1% or lower, but the memory usage increases by ~1.6%. Do you know if the problem can be fixed?

lld/ELF/InputFiles.cpp

952

typo. first object -> `other

[ruiu]

In D62188#1511412, @MaskRay wrote:

In LazyObjFile::parse():

for (size_t I = FirstGlobal, End = ESyms.size(); I != End; ++I)
  if (ESyms[I].st_shndx != SHN_UNDEF)
    // resolveSymbol() called by addSymbol() checks if the symbol was originally undefined.
    // If that is the case, addSymbol() will transitively call SymbolTable::fetchLazy, which calls LazyObjFile::fetch().
    this->Symbols[I] = Symtab->addSymbol(
        LazyObject{*this, CHECK(ESyms[I].getName(Strtab), this)});
return;

Good point. I didn't think about that, but looks like that's a problem. I believe this can be fixed by inserting placeholder symbols first and then resolve them against LazyObject symbols. Let me try to do that.

In LazyObjFile::parse():

// Symbols[0,I) are inherited from LazyObjFile::parse(), other entries are nullptr.
// This has another problem: it increases memory usage.
// The copy assignment cannot be replaced with move assignment, because
// parse() will continue processing Symbols[I+1] Symbols[I+2] ...
File->Symbols = Symbols;

I think in most cases (that are not flagged by --warn-backrefs), this may not have a perceivable improvement in the current form. Actually,
For an (input: 4.2G; output: 1.6G) executable, I measure a performance regression, 1% or lower, but the memory usage increases by ~1.6%. Do you know if the problem can be fixed?

What program did you use for your testing?

[MaskRay]

lld/ELF/InputFiles.cpp

995

It doesn't have to be exhaustive. I thinkg -Wswitch-enum doesn't fire if the variable (Binding) is not of the enum type. I find the original switch easier to read...

[MaskRay]

Good point. I didn't think about that, but looks like that's a problem. I believe this can be fixed by inserting placeholder symbols first and then resolve them against LazyObject symbols. Let me try to do that.

In LazyObjFile::parse():

// Symbols[0,I) are inherited from LazyObjFile::parse(), other entries are nullptr.
// This has another problem: it increases memory usage.
// The copy assignment cannot be replaced with move assignment, because
// parse() will continue processing Symbols[I+1] Symbols[I+2] ...
File->Symbols = Symbols;

I think in most cases (that are not flagged by --warn-backrefs), this may not have a perceivable improvement in the current form. Actually,
For an (input: 4.2G; output: 1.6G) executable, I measure a performance regression, 1% or lower, but the memory usage increases by ~1.6%. Do you know if the problem can be fixed?

What program did you use for your testing?

An internal indexing program. It was compiled with -O3 -ffunction-sections -fdata-sections and many other flags that shouldn't cause a big difference to the linker. I think the patch may show improvement after it is parallelized.

[ruiu]

• add placeholder symbols first before adding LazyObjSymbol
• reduce memory consumption using std::move.

[ruiu]

It looks like this new patch runs faster than the previous ones. Can you confirm?

[ruiu]

• instead of relying on https://reviews.llvm.org/D62234, use Symbol::getName() to obtain cached strings.

[grimar]

With this patch: 5.674s (+0.0%)
Withtout this patch: 6.087s (+7.2%)
Original: 5.886s (+3.7%)

Can it be that you are running debug LLD? I think linking clang was much faster in the past.

lld/ELF/InputFiles.cpp

919

Did you use this-> intentionally in the comments? I think just Symbols would look better.

927

What is wrong with calling resize without check? It should do nothing I think.

[ruiu]

I should've said that I used clang *with debug info* for testing.

lld/ELF/InputFiles.cpp

919

This is needed because this is a template derived class. You'll get a compile error if you don't write this-> in this case.

927

Good point, I'll do that.

[grimar]

lld/ELF/InputFiles.cpp

919

I was talking about comments :)

"Initialize this->Symbols. this->Symbols is a parallel array as" -> "Initialize Symbols. Symbols is a parallel array as"?

[ruiu]

lld/ELF/InputFiles.cpp

919

Ah. This is for consistency with the code that this comment explains. Not a big deal, but I thought that this is better.

[ruiu]

• rebase

[MaskRay]

For one program, I measured 3.0% time decrease with 0.25% memory increase. Looks great!

lld/ELF/InputFiles.cpp

1522

Nit:

if (ESyms[I].st_shndx != SHN_UNDEF)
  this->Symbols[I] = Symtab->insert(CHECK(ESyms[I].getName(Strtab), this));

lld/ELF/InputFiles.h

public:
   // group ID. For more info, see checkDependency() in SymbolTable.cpp.
   uint32_t GroupId;
   static bool IsInGroup;
   static uint32_t NextGroupId;
 
   // Index of MIPS GOT built for this file.
   llvm::Optional<size_t> MipsGotIndex;
 
+  std::vector<Symbol *> Symbols;
+
 protected:
   InputFile(Kind K, MemoryBufferRef M);
   std::vector<InputSectionBase *> Sections;
-  std::vector<Symbol *> Symbols;
 
 private:
   const Kind FileKind;
 };
 
 class ELFFileBase : public InputFile {
 public:
   ELFFileBase(Kind K, MemoryBufferRef M);
private:
   void initializeSymbols();
   void initializeJustSymbols();
   void initializeDwarf();
   InputSectionBase *getRelocTarget(const Elf_Shdr &Sec);
   InputSectionBase *createInputSection(const Elf_Shdr &Sec);
   StringRef getSectionName(const Elf_Shdr &Sec);
 
   bool shouldMerge(const Elf_Shdr &Sec);
-  Symbol *createSymbol(const Elf_Sym *Sym);
 
   // Each ELF symbol contains a section index which the symbol belongs to.
   // However, because the number of bits dedicated for that is limited, a
   // symbol can directly point to a section only when the section index is
   // equal to or smaller than 65280.
   //
   // If an object file contains more than 65280 sections, the file must
   // contain .symtab_shndx section. The section contains an array of

lld/ELF/InputFiles.cpp

InputSectionBase *ObjFile<ELFT>::createInputSection(const Elf_Shdr &Sec) {
   return make<InputSection>(*this, Sec, Name);
 }
 
 template <class ELFT>
 StringRef ObjFile<ELFT>::getSectionName(const Elf_Shdr &Sec) {
   return CHECK(getObj().getSectionName(&Sec, SectionStringTable), this);
 }
 
+// Initialize this->Symbols. this->Symbols is a parallel array as
+// its corresponding ELF symbol table.
 template <class ELFT> void ObjFile<ELFT>::initializeSymbols() {
-  this->Symbols.reserve(this->getELFSyms<ELFT>().size());
-  for (const Elf_Sym &Sym : this->getELFSyms<ELFT>())
-    this->Symbols.push_back(createSymbol(&Sym));
-}
+  ArrayRef<Elf_Sym> ESyms = this->getELFSyms<ELFT>();
+
+  // Our symbol table may have already been partially initialized
+  // because of LazyObjFile.
+  if (this->Symbols.empty())
+    this->Symbols.resize(ESyms.size());
 
-template <class ELFT> Symbol *ObjFile<ELFT>::createSymbol(const Elf_Sym *Sym) {
-  uint32_t SecIdx = getSectionIndex(*Sym);
+  for (size_t I = 0, End = ESyms.size(); I != End; ++I)
+    if (!this->Symbols[I] && ESyms[I].getBinding() != STB_LOCAL)
+      this->Symbols[I] =
+          Symtab->insert(CHECK(ESyms[I].getName(this->StringTable), this));
+
+  // Fill this->Symbols. A symbol is either local or global.
+  for (size_t I = 0, End = ESyms.size(); I != End; ++I) {
+    const Elf_Sym &ESym = ESyms[I];
+    uint32_t SecIdx = getSectionIndex(ESym);
     if (SecIdx >= this->Sections.size())
       fatal(toString(this) + ": invalid section index: " + Twine(SecIdx));
 
     InputSectionBase *Sec = this->Sections[SecIdx];
-  uint8_t Binding = Sym->getBinding();
-  uint8_t StOther = Sym->st_other;
-  uint8_t Type = Sym->getType();
-  uint64_t Value = Sym->st_value;
-  uint64_t Size = Sym->st_size;
+    uint8_t Binding = ESym.getBinding();
+    uint8_t StOther = ESym.st_other;
+    uint8_t Type = ESym.getType();
+    uint64_t Value = ESym.st_value;
+    uint64_t Size = ESym.st_size;
+    StringRefZ Name = this->StringTable.data() + ESym.st_name;
 
     if (Binding == STB_LOCAL) {
-    if (Sym->getType() == STT_FILE)
-      SourceFile = CHECK(Sym->getName(this->StringTable), this);
+      // Local symbols are not added to the symbol table because they
+      // are not visible from object object files. We allocate symbol
+      // instances and added their pointers to Symbols.
+      if (ESym.getType() == STT_FILE)
+        SourceFile = CHECK(ESym.getName(this->StringTable), this);
 
-    if (this->StringTable.size() <= Sym->st_name)
+      if (this->StringTable.size() <= ESym.st_name)
         fatal(toString(this) + ": invalid symbol name offset");
 
-    StringRefZ Name = this->StringTable.data() + Sym->st_name;
-    if (Sym->st_shndx == SHN_UNDEF)
-      return make<Undefined>(this, Name, Binding, StOther, Type);
-    return make<Defined>(this, Name, Binding, StOther, Type, Value, Size, Sec);
+      if (ESym.st_shndx == SHN_UNDEF)
+        this->Symbols[I] = make<Undefined>(this, Name, Binding, StOther, Type);
+      else
+        this->Symbols[I] =
+            make<Defined>(this, Name, Binding, StOther, Type, Value, Size, Sec);
+      continue;
     }
 
-  StringRef Name = CHECK(Sym->getName(this->StringTable), this);
-
-  switch (Sym->st_shndx) {
+    // Global symbols are compared against existing symbols for name
+    // resolution.
+    switch (ESym.st_shndx) {
     case SHN_UNDEF:
-    return Symtab->addSymbol(Undefined{this, Name, Binding, StOther, Type});
+      resolveSymbol(this->Symbols[I],
+                    Undefined{this, Name, Binding, StOther, Type});
+      continue;
     case SHN_COMMON:
       if (Value == 0 || Value >= UINT32_MAX)
-      fatal(toString(this) + ": common symbol '" + Name +
+        fatal(toString(this) + ": common symbol '" + StringRef(Name.Data) +
               "' has invalid alignment: " + Twine(Value));
-    return Symtab->addSymbol(
-        CommonSymbol{this, Name, Binding, StOther, Type, Value, Size});
+      resolveSymbol(this->Symbols[I], CommonSymbol{this, Name, Binding, StOther,
+                                                   Type, Value, Size});
+      continue;
     }
 
     switch (Binding) {
-  default:
-    fatal(toString(this) + ": unexpected binding: " + Twine((int)Binding));
     case STB_GLOBAL:
     case STB_WEAK:
     case STB_GNU_UNIQUE:
       if (Sec == &InputSection::Discarded)
-      return Symtab->addSymbol(Undefined{this, Name, Binding, StOther, Type});
-    return Symtab->addSymbol(
-        Defined{this, Name, Binding, StOther, Type, Value, Size, Sec});
+        resolveSymbol(this->Symbols[I],
+                      Undefined{this, Name, Binding, StOther, Type});
+      else
+        resolveSymbol(this->Symbols[I], Defined{this, Name, Binding, StOther,
+                                                Type, Value, Size, Sec});
+      continue;
+    }
+
+    fatal(toString(this) + ": unexpected binding: " + Twine((int)Binding));
   }
 }
 
 ArchiveFile::ArchiveFile(std::unique_ptr<Archive> &&File)
     : InputFile(ArchiveKind, File->getMemoryBufferRef()),
       File(std::move(File)) {}
 
 void ArchiveFile::parse() {

 
 InputFile *LazyObjFile::fetch() {
   MemoryBufferRef MBRef = getBuffer();
   if (MBRef.getBuffer().empty())
     return nullptr;
 
   InputFile *File = createObjectFile(MBRef, ArchiveName, OffsetInArchive);
   File->GroupId = GroupId;
+
+  // Copy symbol vector so that the new InputFile doesn't have to
+  // insert the same defined symbols to the symbol table again.
+  File->Symbols = Symbols;
   return File;
 }
 
 template <class ELFT> void LazyObjFile::parse() {
+  using Elf_Sym = typename ELFT::Sym;
+
   // A lazy object file wraps either a bitcode file or an ELF file.
   if (isBitcode(this->MB)) {
     std::unique_ptr<lto::InputFile> Obj =
         CHECK(lto::InputFile::create(this->MB), this);
     for (const lto::InputFile::Symbol &Sym : Obj->symbols()) {
       if (Sym.isUndefined())
         continue;
       Symtab->addSymbol(LazyObject{*this, Saver.save(Sym.getName())});
     }
     return;
   }
 
   if (getELFKind(this->MB, ArchiveName) != Config->EKind) {
     error("incompatible file: " + this->MB.getBufferIdentifier());
     return;
   }
 
   ELFFile<ELFT> Obj = check(ELFFile<ELFT>::create(MB.getBuffer()));
   ArrayRef<typename ELFT::Shdr> Sections = CHECK(Obj.sections(), this);
 
   for (const typename ELFT::Shdr &Sec : Sections) {
     if (Sec.sh_type != SHT_SYMTAB)
       continue;
 
-    typename ELFT::SymRange Syms = CHECK(Obj.symbols(&Sec), this);
+    ArrayRef<Elf_Sym> ESyms = CHECK(Obj.symbols(&Sec), this);
     uint32_t FirstGlobal = Sec.sh_info;
-    StringRef StringTable =
-        CHECK(Obj.getStringTableForSymtab(Sec, Sections), this);
+    StringRef Strtab = CHECK(Obj.getStringTableForSymtab(Sec, Sections), this);
+    this->Symbols.resize(ESyms.size());
 
-    for (const typename ELFT::Sym &Sym : Syms.slice(FirstGlobal)) {
-      if (Sym.st_shndx == SHN_UNDEF)
-        continue;
-      Symtab->addSymbol(
-          LazyObject{*this, CHECK(Sym.getName(StringTable), this)});
-    }
+    for (size_t I = FirstGlobal, End = ESyms.size(); I != End; ++I)
+      if (ESyms[I].st_shndx != SHN_UNDEF)
+        this->Symbols[I] = Symtab->addSymbol(
+            LazyObject{*this, CHECK(ESyms[I].getName(Strtab), this)});
     return;
   }
 }
 
 std::string elf::replaceThinLTOSuffix(StringRef Path) {
   StringRef Suffix = Config->ThinLTOObjectSuffixReplace.first;
   StringRef Repl = Config->ThinLTOObjectSuffixReplace.second;