[ELF] - Stop handling local symbols in a special way.

[grimar]

Summary

Previously we stored kept locals in a KeptLocalSyms arrays,
belonged to files.

Patch makes SymbolTableSection to store locals in Symbols member,
that already present and was used for globals.
SymbolTableSection already had NumLocals counter member, so change
itself is trivial.

That allows to simplify handling of -r,
Body::DynsymIndex is no more used as "symbol table index" for relocatable
output.

Change was suggested during review of D28773 and opens road for D28612.

[ruiu]

lld/trunk/ELF/SyntheticSections.cpp

1073–1077

You can use stable_partition here.

1104–1109

This is a linear scan, so this makes the algorithm O(n^2), right? Did you verify that that is not a problem? Anyway, it needs comment as always -- you should explain that this is O(n^2) but in practice it is not an issue because blah blah (if that's the case.)

[grimar]

lld/trunk/ELF/SyntheticSections.cpp

1104–1109

O(n*m). N bodies, M relocations, probably it is can be quadratic, yes.
I did not verify because it is for -relocatable only, it should be not often case.

But actually I already suggested 2 ways of solutions for that:
https://reviews.llvm.org/D28773#inline-250840

I supposed we can implement the second one just to be sure we do not have obviously slow place, what do you think ?

[ruiu]

Well, I think the problem was not in the code but in (the lack of) comments. It might have been OK if you add a comment saying that, for -r, we piggy back symbol's .symtab offsets to DynsymIndex because -r will never be used to produce DSOs. You probably want to spend more efforts on comments as it is sometimes the easiest way to solve a problem.

[grimar]

In D29021#653665, @ruiu wrote:

Well, I think the problem was not in the code but in (the lack of) comments. It might have been OK if you add a comment saying that, for -r, we piggy back symbol's .symtab offsets to DynsymIndex because -r will never be used to produce DSOs. You probably want to spend more efforts on comments as it is sometimes the easiest way to solve a problem.

I'll try.

It might have work for -relocatable, but piggybacking does not work fine for --emit-relocs (D28612) as it is possible to use it in dynamic case.
I think --emit-relocs was initial reason of why this patch appeared :)

[ruiu]

Or, if you find that adding a new field to Symbol class doesn't really hurt any metrics, you can simply add it. Or, even if it slows down the linker a little bit, you may still be able to convince that that is necessary. I believe adding a new field is the simplest and sufficient way to do what you want to do, but I think you want to stop to think and investigate a few different ways, and then make your conclusion (because all I said were my guesses and not conclusions in any sense.)

[grimar]

In D29021#653797, @ruiu wrote:

Or, if you find that adding a new field to Symbol class doesn't really hurt any metrics, you can simply add it. Or, even if it slows down the linker a little bit, you may still be able to convince that that is necessary. I believe adding a new field is the simplest and sufficient way to do what you want to do, but I think you want to stop to think and investigate a few different ways, and then make your conclusion (because all I said were my guesses and not conclusions in any sense.)

Mmmm. Sorry, did you get this had LGTM and was already landed ? (I am not sure, I thought we discussing post commit details.)

I think I agree with Rafael that for now we can go with this solution and see if we want to optimize for -r or not separatelly later.
-relocatable output is not general use case and I think I am agree extending Symbol simply not worth doing if can be avoided.
No matter if that slows down linker or not.

This patch removed KeptLocalSyms and localized symbols handling in one place, what IMO made code cleaner. So it was useful to have.
And even if we decide to add field to Symbol, this patch helps to do that in a easy way still.

lld/trunk/ELF/InputFiles.h

public:
   // If no information is available, returns "".
   std::string getLineInfo(InputSectionBase<ELFT> *S, uintX_t Offset);
 
   // MIPS GP0 value defined by this file. This value represents the gp value
   // used to create the relocatable object and required to support
   // R_MIPS_GPREL16 / R_MIPS_GPREL32 relocations.
   uint32_t MipsGp0 = 0;
 
-  // The number is the offset in the string table. It will be used as the
-  // st_name of the symbol.
-  std::vector<std::pair<const DefinedRegular<ELFT> *, unsigned>> KeptLocalSyms;
-
   // Name of source file obtained from STT_FILE symbol value,
   // or empty string if there is no such symbol in object file
   // symbol table.
   StringRef SourceFile;
 
 private:
   void
   initializeSections(llvm::DenseSet<llvm::CachedHashStringRef> &ComdatGroups);

lld/trunk/ELF/InputSection.cpp

for (const RelTy &Rel : Rels) {
     SymbolBody &Body = this->File->getRelocTargetSym(Rel);
 
     Elf_Rela *P = reinterpret_cast<Elf_Rela *>(Buf);
     Buf += sizeof(RelTy);
 
     if (Config->Rela)
       P->r_addend = getAddend<ELFT>(Rel);
     P->r_offset = RelocatedSection->getOffset(Rel.r_offset);
-    P->setSymbolAndType(Body.DynsymIndex, Type, Config->Mips64EL);
+    P->setSymbolAndType(In<ELFT>::SymTab->getSymbolIndex(&Body), Type,
+                        Config->Mips64EL);
   }
 }
 
 static uint32_t getARMUndefinedRelativeWeakVA(uint32_t Type, uint32_t A,
                                               uint32_t P) {
   switch (Type) {
   case R_ARM_THM_JUMP11:
     return P + 2;

lld/trunk/ELF/SyntheticSections.h

public:
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::SymRange Elf_Sym_Range;
   typedef typename ELFT::uint uintX_t;
   SymbolTableSection(StringTableSection<ELFT> &StrTabSec);
 
   void finalize() override;
   void writeTo(uint8_t *Buf) override;
   size_t getSize() const override { return getNumSymbols() * sizeof(Elf_Sym); }
-  void addSymbol(SymbolBody *Body);
+  void addGlobal(SymbolBody *Body);
+  void addLocal(SymbolBody *Body);
   StringTableSection<ELFT> &getStrTabSec() const { return StrTabSec; }
-  unsigned getNumSymbols() const { return NumLocals + Symbols.size() + 1; }
+  unsigned getNumSymbols() const { return Symbols.size() + 1; }
+  size_t getSymbolIndex(SymbolBody *Body);
 
   ArrayRef<SymbolTableEntry> getSymbols() const { return Symbols; }
 
   static const OutputSectionBase *getOutputSection(SymbolBody *Sym);
 
-  unsigned NumLocals = 0;
-  StringTableSection<ELFT> &StrTabSec;
-
 private:
   void writeLocalSymbols(uint8_t *&Buf);
   void writeGlobalSymbols(uint8_t *Buf);
 
   // A vector of symbols and their string table offsets.
   std::vector<SymbolTableEntry> Symbols;
+
+  StringTableSection<ELFT> &StrTabSec;
+
+  unsigned NumLocals = 0;
 };
 
 // Outputs GNU Hash section. For detailed explanation see:
 // https://blogs.oracle.com/ali/entry/gnu_hash_elf_sections
 template <class ELFT>
 class GnuHashTableSection final : public SyntheticSection<ELFT> {
   typedef typename ELFT::Off Elf_Off;
   typedef typename ELFT::Word Elf_Word;

lld/trunk/ELF/SyntheticSections.cpp

static bool sortMipsSymbols(const SymbolBody *L, const SymbolBody *R) {
   return L->GotIndex < R->GotIndex;
 }
 
 template <class ELFT> void SymbolTableSection<ELFT>::finalize() {
   this->OutSec->Link = this->Link = StrTabSec.OutSec->SectionIndex;
   this->OutSec->Info = this->Info = NumLocals + 1;
   this->OutSec->Entsize = this->Entsize;
 
-  if (Config->Relocatable) {
-    size_t I = NumLocals;
-    for (const SymbolTableEntry &S : Symbols)
-      S.Symbol->DynsymIndex = ++I;
+  if (Config->Relocatable)
     return;
-  }
 
   if (!StrTabSec.isDynamic()) {
-    std::stable_sort(
-        Symbols.begin(), Symbols.end(),
-        [](const SymbolTableEntry &L, const SymbolTableEntry &R) {
-          return L.Symbol->symbol()->computeBinding() == STB_LOCAL &&
-                 R.Symbol->symbol()->computeBinding() != STB_LOCAL;
-        });
+    auto GlobBegin = Symbols.begin() + NumLocals;
+    std::stable_sort(GlobBegin, Symbols.end(), [](const SymbolTableEntry &L,
+                                                  const SymbolTableEntry &R) {
     return;
   }
+
   if (In<ELFT>::GnuHashTab)
     // NB: It also sorts Symbols to meet the GNU hash table requirements.
     In<ELFT>::GnuHashTab->addSymbols(Symbols);
   else if (Config->EMachine == EM_MIPS)
     std::stable_sort(Symbols.begin(), Symbols.end(),
                      [](const SymbolTableEntry &L, const SymbolTableEntry &R) {
                        return sortMipsSymbols(L.Symbol, R.Symbol);
                      });
   size_t I = 0;
   for (const SymbolTableEntry &S : Symbols)
     S.Symbol->DynsymIndex = ++I;
 }
 
-template <class ELFT> void SymbolTableSection<ELFT>::addSymbol(SymbolBody *B) {
+template <class ELFT> void SymbolTableSection<ELFT>::addGlobal(SymbolBody *B) {
   Symbols.push_back({B, StrTabSec.addString(B->getName(), false)});
 }
 
+template <class ELFT> void SymbolTableSection<ELFT>::addLocal(SymbolBody *B) {
+  assert(!StrTabSec.isDynamic());
+  ++NumLocals;
+  Symbols.push_back({B, StrTabSec.addString(B->getName())});
+}
+
+template <class ELFT>
+size_t SymbolTableSection<ELFT>::getSymbolIndex(SymbolBody *Body) {
+  auto I = llvm::find_if(
+      Symbols, [&](const SymbolTableEntry &E) { return E.Symbol == Body; });
+  return I - Symbols.begin() + 1;
+}
+
 template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *Buf) {
   Buf += sizeof(Elf_Sym);
 
   // All symbols with STB_LOCAL binding precede the weak and global symbols.
   // .dynsym only contains global symbols.
   if (Config->Discard != DiscardPolicy::All && !StrTabSec.isDynamic())
     writeLocalSymbols(Buf);
 
   writeGlobalSymbols(Buf);
 }
 
 template <class ELFT>
 void SymbolTableSection<ELFT>::writeLocalSymbols(uint8_t *&Buf) {
   // Iterate over all input object files to copy their local symbols
   // to the output symbol table pointed by Buf.
-  for (ObjectFile<ELFT> *File : Symtab<ELFT>::X->getObjectFiles()) {
-    for (const std::pair<const DefinedRegular<ELFT> *, size_t> &P :
-         File->KeptLocalSyms) {
-      const DefinedRegular<ELFT> &Body = *P.first;
-      InputSectionBase<ELFT> *Section = Body.Section;
-      auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
+
+  for (auto I = Symbols.begin(); I != Symbols.begin() + NumLocals; ++I) {
+    const DefinedRegular<ELFT> &Body = *cast<DefinedRegular<ELFT>>(I->Symbol);
 
-      if (!Section) {
-        ESym->st_shndx = SHN_ABS;
-        ESym->st_value = Body.Value;
-      } else {
-        const OutputSectionBase *OutSec = Section->OutSec;
-        ESym->st_shndx = OutSec->SectionIndex;
-        ESym->st_value = OutSec->Addr + Section->getOffset(Body);
-      }
-      ESym->st_name = P.second;
-      ESym->st_size = Body.template getSize<ELFT>();
-      ESym->setBindingAndType(STB_LOCAL, Body.Type);
-      Buf += sizeof(*ESym);
-    }
-  }
-}
+    ESym->st_name = I->StrTabOffset;
 
 template <class ELFT>
 void SymbolTableSection<ELFT>::writeGlobalSymbols(uint8_t *Buf) {
   // Write the internal symbol table contents to the output symbol table
   // pointed by Buf.
   auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
-  for (const SymbolTableEntry &S : Symbols) {
+
+  for (auto I = Symbols.begin() + NumLocals; I != Symbols.end(); ++I) {
+    const SymbolTableEntry &S = *I;
     SymbolBody *Body = S.Symbol;
     size_t StrOff = S.StrTabOffset;
 
     uint8_t Type = Body->Type;
     uintX_t Size = Body->getSize<ELFT>();
 
     ESym->setBindingAndType(Body->symbol()->computeBinding(), Type);
     ESym->st_size = Size;

lld/trunk/ELF/Writer.cpp

for (SymbolBody *B : F->getLocalSymbols()) {
       if (!DR)
         continue;
       if (!includeInSymtab<ELFT>(*B))
         continue;
 
       InputSectionBase<ELFT> *Sec = DR->Section;
       if (!shouldKeepInSymtab<ELFT>(Sec, B->getName(), *B))
         continue;
-      ++In<ELFT>::SymTab->NumLocals;
-      if (Config->Relocatable)
-        B->DynsymIndex = In<ELFT>::SymTab->NumLocals;
-      F->KeptLocalSyms.push_back(std::make_pair(
-          DR, In<ELFT>::SymTab->StrTabSec.addString(B->getName())));
+      In<ELFT>::SymTab->addLocal(B);
     }
   }
 }
 
 // PPC64 has a number of special SHT_PROGBITS+SHF_ALLOC+SHF_WRITE sections that
 // we would like to make sure appear is a specific order to maximize their
 // coverage by a single signed 16-bit offset from the TOC base pointer.
 // Conversely, the special .tocbss section should be first among all SHT_NOBITS
template <class ELFT> void Writer<ELFT>::finalizeSections() {
   // Now that we have defined all possible symbols including linker-
   // synthesized ones. Visit all symbols to give the finishing touches.
   for (Symbol *S : Symtab<ELFT>::X->getSymbols()) {
     SymbolBody *Body = S->body();
 
     if (!includeInSymtab<ELFT>(*Body))
       continue;
     if (In<ELFT>::SymTab)
-      In<ELFT>::SymTab->addSymbol(Body);
+      In<ELFT>::SymTab->addGlobal(Body);
 
     if (In<ELFT>::DynSymTab && S->includeInDynsym()) {
-      In<ELFT>::DynSymTab->addSymbol(Body);
+      In<ELFT>::DynSymTab->addGlobal(Body);
       if (auto *SS = dyn_cast<SharedSymbol<ELFT>>(Body))
         if (SS->file()->isNeeded())
           In<ELFT>::VerNeed->addSymbol(SS);
     }
   }
 
   // Do not proceed if there was an undefined symbol.
   if (ErrorCount)