Move symbol resolution code out of SymbolTable class.

[ruiu]

Summary

This is the last patch of the series of patches to make it possible to
resolve symbols without asking SymbolTable to do so.

The main point of this patch is the introduction of
elf::resolveSymbol(Symbol *Old, Symbol *New). That function resolves
or merges given symbols by examining symbol types and call
replaceSymbol (which memcpy's New to Old) if necessary.

With the new function, we have now separated symbol resolution from
symbol lookup. If you already have a Symbol pointer, you can directly
resolve the symbol without asking SymbolTable to do that.

Now that the nice abstraction become available, I can start working on
performance improvement of the linker. As a starter, I'm thinking of
making --{start,end}-lib faster.

--{start,end}-lib is currently unnecessarily slow because it looks up
the symbol table twice for each symbol.

• The first hash table lookup/insertion occurs when we instantiate a LazyObject file to insert LazyObject symbols.
• The second hash table lookup/insertion occurs when we create an ObjFile from LazyObject file. That overwrites LazyObject symbols with Defined symbols.

I think it is not too hard to see how we can now eliminate the second
hash table lookup. We can keep LazyObject symbols in Step 1, and then
call elf::resolveSymbol() to do Step 2.

[MaskRay]

lld/ELF/SymbolTable.cpp

577 ↗

(On Diff #199425)

Have you checked if this chain of dyn_cast is as efficient as a switch dispatch on New->kind()?

getSymbolSize below dispatches on SymbolKind.

lld/ELF/Symbols.h

428 ↗

(On Diff #199425)

Sym->kind()

[ruiu]

lld/ELF/SymbolTable.cpp

577 ↗

(On Diff #199425)

Done.

lld/ELF/Symbols.h

428 ↗

(On Diff #199425)

Done.

[ruiu]

• review comments

[ruiu]

• minor fix

[MaskRay]

lld/ELF/SymbolTable.cpp

605 ↗

(On Diff #199742)

symbol kind?

lld/ELF/Symbols.h

449 ↗

(On Diff #199742)

Does const Symbol &New work? Other add* functions use const references, e.g.

static void addShared(Symbol *Old, const SharedSymbol &New) {

[ruiu]

lld/ELF/SymbolTable.cpp

605 ↗

(On Diff #199742)

Done

lld/ELF/Symbols.h

449 ↗

(On Diff #199742)

Done.

ELF/Driver.cpp

for (Symbol *Sym : Symtab->getSymbols()) {
     auto *S = dyn_cast<CommonSymbol>(Sym);
     if (!S)
       continue;
 
     auto *Bss = make<BssSection>("COMMON", S->Size, S->Alignment);
     Bss->File = S->File;
     Bss->Live = !Config->GcSections;
     InputSections.push_back(Bss);
-
-    Defined New(S->File, S->getName(), S->Binding, S->StOther, S->Type,
-                /*Value=*/0, S->Size, Bss);
-    replaceSymbol(S, &New);
+    replaceSymbol(S, Defined{S->File, S->getName(), S->Binding, S->StOther,
+                             S->Type,
+                             /*Value=*/0, S->Size, Bss});
   }
 }
 
 // If all references to a DSO happen to be weak, the DSO is not added
 // to DT_NEEDED. If that happens, we need to eliminate shared symbols
 // created from the DSO. Otherwise, they become dangling references
 // that point to a non-existent DSO.
 static void demoteSharedSymbols() {
   for (Symbol *Sym : Symtab->getSymbols()) {
     auto *S = dyn_cast<SharedSymbol>(Sym);
     if (!S || S->getFile().IsNeeded)
       continue;
 
     bool Used = S->Used;
-    Undefined New(nullptr, S->getName(), STB_WEAK, S->StOther, S->Type);
-    replaceSymbol(S, &New);
+    replaceSymbol(
+        S, Undefined{nullptr, S->getName(), STB_WEAK, S->StOther, S->Type});
     S->Used = Used;
   }
 }
 
 // The section referred to by S is considered address-significant. Set the
 // KeepUnique flag on the section if appropriate.
 static void markAddrsig(Symbol *S) {
   if (auto *D = dyn_cast_or_null<Defined>(S))
if (Obj->AddrsigSec) {
       // conservatively mark all of its symbols as address-significant.
       for (Symbol *S : Syms)
         markAddrsig(S);
     }
   }
 }
 
 template <class ELFT> static Symbol *addUndefined(StringRef Name) {
-  return Symtab->addUndefined(
+  return Symtab->addSymbol(
       Undefined{nullptr, Name, STB_GLOBAL, STV_DEFAULT, 0});
 }
 
 // The --wrap option is a feature to rename symbols so that you can write
 // wrappers for existing functions. If you pass `-wrap=foo`, all
 // occurrences of symbol `foo` are resolved to `wrap_foo` (so, you are
 // expected to write `wrap_foo` function as a wrapper). The original
 // symbol becomes accessible as `real_foo`, so you can call that from your

ELF/InputFiles.cpp

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);
   }
 
   StringRef Name = CHECK(Sym->getName(this->StringTable), this);
 
   switch (Sym->st_shndx) {
   case SHN_UNDEF:
-    return Symtab->addUndefined(Undefined{this, Name, Binding, StOther, Type});
+    return Symtab->addSymbol(Undefined{this, Name, Binding, StOther, Type});
   case SHN_COMMON:
     if (Value == 0 || Value >= UINT32_MAX)
       fatal(toString(this) + ": common symbol '" + Name +
             "' has invalid alignment: " + Twine(Value));
-    return Symtab->addCommon(
+    return Symtab->addSymbol(
         CommonSymbol{this, Name, Binding, StOther, Type, Value, Size});
   }
 
   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->addUndefined(
-          Undefined{this, Name, Binding, StOther, Type});
-    return Symtab->addDefined(
+      return Symtab->addSymbol(Undefined{this, Name, Binding, StOther, Type});
+    return Symtab->addSymbol(
         Defined{this, Name, Binding, StOther, Type, Value, Size, Sec});
   }
 }
 
 ArchiveFile::ArchiveFile(std::unique_ptr<Archive> &&File)
     : InputFile(ArchiveKind, File->getMemoryBufferRef()),
       File(std::move(File)) {}
 
 void ArchiveFile::parse() {
   for (const Archive::Symbol &Sym : File->symbols())
-    Symtab->addLazyArchive(LazyArchive{*this, Sym});
+    Symtab->addSymbol(LazyArchive{*this, Sym});
 }
 
 // Returns a buffer pointing to a member file containing a given symbol.
 InputFile *ArchiveFile::fetch(const Archive::Symbol &Sym) {
   Archive::Child C =
       CHECK(Sym.getMember(), toString(this) +
                                  ": could not get the member for symbol " +
                                  Sym.getName());
for (size_t I = 0; I < Syms.size(); ++I) {
     StringRef Name = CHECK(Sym.getName(this->StringTable), this);
     if (Sym.getBinding() == STB_LOCAL) {
       warn("found local symbol '" + Name +
            "' in global part of symbol table in file " + toString(this));
       continue;
     }
 
     if (Sym.isUndefined()) {
-      Symbol *S = Symtab->addUndefined(
+      Symbol *S = Symtab->addSymbol(
           Undefined{this, Name, Sym.getBinding(), Sym.st_other, Sym.getType()});
       S->ExportDynamic = true;
       continue;
     }
 
     // MIPS BFD linker puts _gp_disp symbol into DSO files and incorrectly
     // assigns VER_NDX_LOCAL to this section global symbol. Here is a
     // workaround for this bug.
     uint32_t Idx = Versyms[I] & ~VERSYM_HIDDEN;
     if (Config->EMachine == EM_MIPS && Idx == VER_NDX_LOCAL &&
         Name == "_gp_disp")
       continue;
 
     uint32_t Alignment = getAlignment<ELFT>(Sections, Sym);
     if (!(Versyms[I] & VERSYM_HIDDEN)) {
-      Symtab->addShared(SharedSymbol{*this, Name, Sym.getBinding(),
+      Symtab->addSymbol(SharedSymbol{*this, Name, Sym.getBinding(),
                                      Sym.st_other, Sym.getType(), Sym.st_value,
                                      Sym.st_size, Alignment, Idx});
     }
 
     // Also add the symbol with the versioned name to handle undefined symbols
     // with explicit versions.
     if (Idx == VER_NDX_GLOBAL)
       continue;
 
     if (Idx >= Verdefs.size() || Idx == VER_NDX_LOCAL) {
       error("corrupt input file: version definition index " + Twine(Idx) +
             " for symbol " + Name + " is out of bounds\n>>> defined in " +
             toString(this));
       continue;
     }
 
     StringRef VerName =
         this->StringTable.data() +
         reinterpret_cast<const Elf_Verdef *>(Verdefs[Idx])->getAux()->vda_name;
     VersionedNameBuffer.clear();
     Name = (Name + "@" + VerName).toStringRef(VersionedNameBuffer);
-    Symtab->addShared(SharedSymbol{*this, Saver.save(Name), Sym.getBinding(),
+    Symtab->addSymbol(SharedSymbol{*this, Saver.save(Name), Sym.getBinding(),
                                    Sym.st_other, Sym.getType(), Sym.st_value,
                                    Sym.st_size, Alignment, Idx});
   }
 }
 
 static ELFKind getBitcodeELFKind(const Triple &T) {
   if (T.isLittleEndian())
     return T.isArch64Bit() ? ELF64LEKind : ELF32LEKind;
static Symbol *createBitcodeSymbol(const std::vector<bool> &KeptComdats,
   uint8_t Visibility = mapVisibility(ObjSym.getVisibility());
   bool CanOmitFromDynSym = ObjSym.canBeOmittedFromSymbolTable();
 
   int C = ObjSym.getComdatIndex();
   if (ObjSym.isUndefined() || (C != -1 && !KeptComdats[C])) {
     Undefined New(&F, Name, Binding, Visibility, Type);
     if (CanOmitFromDynSym)
       New.ExportDynamic = false;
-    return Symtab->addUndefined(New);
+    return Symtab->addSymbol(New);
   }
 
   if (ObjSym.isCommon())
-    return Symtab->addCommon(
+    return Symtab->addSymbol(
         CommonSymbol{&F, Name, Binding, Visibility, STT_OBJECT,
                      ObjSym.getCommonAlignment(), ObjSym.getCommonSize()});
 
   Defined New(&F, Name, Binding, Visibility, Type, 0, 0, nullptr);
   if (CanOmitFromDynSym)
     New.ExportDynamic = false;
-  return Symtab->addDefined(New);
+  return Symtab->addSymbol(New);
 }
 
 template <class ELFT>
 void BitcodeFile::parse(DenseSet<CachedHashStringRef> &ComdatGroups) {
   std::vector<bool> KeptComdats;
   for (StringRef S : Obj->getComdatTable())
     KeptComdats.push_back(ComdatGroups.insert(CachedHashStringRef(S)).second);
 
void BinaryFile::parse() {
   // blob, we define _binary_foo_{start,end,size} symbols, so that
   // user programs can access blobs by name. Non-alphanumeric
   // characters in a filename are replaced with underscore.
   std::string S = "_binary_" + MB.getBufferIdentifier().str();
   for (size_t I = 0; I < S.size(); ++I)
     if (!isAlnum(S[I]))
       S[I] = '_';
 
-  Symtab->addDefined(Defined{nullptr, Saver.save(S + "_start"), STB_GLOBAL,
-                             STV_DEFAULT, STT_OBJECT, 0, 0, Section});
-  Symtab->addDefined(Defined{nullptr, Saver.save(S + "_end"), STB_GLOBAL,
-                             STV_DEFAULT, STT_OBJECT, Data.size(), 0, Section});
-  Symtab->addDefined(Defined{nullptr, Saver.save(S + "_size"), STB_GLOBAL,
-                             STV_DEFAULT, STT_OBJECT, Data.size(), 0, nullptr});
+  Symtab->addSymbol(Defined{nullptr, Saver.save(S + "_start"), STB_GLOBAL,
+  Symtab->addSymbol(Defined{nullptr, Saver.save(S + "_end"), STB_GLOBAL,
+  Symtab->addSymbol(Defined{nullptr, Saver.save(S + "_size"), STB_GLOBAL,
 }
 
 InputFile *elf::createObjectFile(MemoryBufferRef MB, StringRef ArchiveName,
                                  uint64_t OffsetInArchive) {
   if (isBitcode(MB))
     return make<BitcodeFile>(MB, ArchiveName, OffsetInArchive);
 
   switch (getELFKind(MB, ArchiveName)) {

 template <class ELFT> void LazyObjFile::parse() {
   // 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->addLazyObject(LazyObject{*this, Saver.save(Sym.getName())});
+      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);
     uint32_t FirstGlobal = Sec.sh_info;
     StringRef StringTable =
         CHECK(Obj.getStringTableForSymtab(Sec, Sections), this);
 
     for (const typename ELFT::Sym &Sym : Syms.slice(FirstGlobal)) {
       if (Sym.st_shndx == SHN_UNDEF)
         continue;
-      Symtab->addLazyObject(
+      Symtab->addSymbol(
           LazyObject{*this, CHECK(Sym.getName(StringTable), this)});
     }
     return;
   }
 }
 
 std::string elf::replaceThinLTOSuffix(StringRef Path) {
   StringRef Suffix = Config->ThinLTOObjectSuffixReplace.first;

ELF/LTO.cpp

for (Symbol *Sym : Symtab->getSymbols()) {
     for (StringRef Prefix : {"__start_", "__stop_"})
       if (S.startswith(Prefix))
         UsedStartStop.insert(S.substr(Prefix.size()));
   }
 }
 
 BitcodeCompiler::~BitcodeCompiler() = default;
 
-static void undefine(Symbol *S) {
-  Undefined New(nullptr, S->getName(), STB_GLOBAL, STV_DEFAULT, S->Type);
-  replaceSymbol(S, &New);
-}
-
 void BitcodeCompiler::add(BitcodeFile &F) {
   lto::InputFile &Obj = *F.Obj;
   bool IsExec = !Config->Shared && !Config->Relocatable;
 
   if (Config->ThinLTOIndexOnly)
     ThinIndices.insert(Obj.getName());
 
   ArrayRef<Symbol *> Syms = F.getSymbols();
R.FinalDefinitionInLinkageUnit =
         // Skip absolute symbols from ELF objects, otherwise PC-rel relocations
         // will be generated by for them, triggering linker errors.
         // Symbol section is always null for bitcode symbols, hence the check
         // for isElf(). Skip linker script defined symbols as well: they have
         // no File defined.
         !(DR->Section == nullptr && (!Sym->File || Sym->File->isElf()));
 
     if (R.Prevailing)
-      undefine(Sym);
+      replaceSymbol(Sym, Undefined{nullptr, Sym->getName(), STB_GLOBAL,
+                                   STV_DEFAULT, Sym->Type});
 
     // We tell LTO to not apply interprocedural optimization for wrapped
     // (with --wrap) symbols because otherwise LTO would inline them while
     // their values are still not final.
     R.LinkerRedefined = !Sym->CanInline;
   }
   checkError(LTOObj->add(std::move(F.Obj), Resols));
 }

ELF/LinkerScript.cpp

void LinkerScript::addSymbol(SymbolAssignment *Cmd) {
   // We want to set symbol values early if we can. This allows us to
   // use symbols as variables in linker scripts. Doing so allows us to
   // write expressions like this: `alignment = 16; . = ALIGN(., alignment)`.
   uint64_t SymValue = Value.Sec ? 0 : Value.getValue();
 
   Defined New(nullptr, Cmd->Name, STB_GLOBAL, Visibility, STT_NOTYPE, SymValue,
               0, Sec);
 
-  Symbol *Sym = Symtab->insert(New);
-  Symtab->mergeProperties(Sym, New);
-  replaceSymbol(Sym, &New);
+  Symbol *Sym = Symtab->insert(Cmd->Name);
+  mergeSymbolProperties(Sym, New);
+  replaceSymbol(Sym, New);
   Cmd->Sym = cast<Defined>(Sym);
 }
 
 // This function is called from LinkerScript::declareSymbols.
 // It creates a placeholder symbol if needed.
 static void declareSymbol(SymbolAssignment *Cmd) {
   if (!shouldDefineSym(Cmd))
     return;
 
   uint8_t Visibility = Cmd->Hidden ? STV_HIDDEN : STV_DEFAULT;
   Defined New(nullptr, Cmd->Name, STB_GLOBAL, Visibility, STT_NOTYPE, 0, 0,
               nullptr);
 
   // We can't calculate final value right now.
-  Symbol *Sym = Symtab->insert(New);
-  Symtab->mergeProperties(Sym, New);
-  replaceSymbol(Sym, &New);
+  Symbol *Sym = Symtab->insert(Cmd->Name);
+  mergeSymbolProperties(Sym, New);
+  replaceSymbol(Sym, New);
 
   Cmd->Sym = cast<Defined>(Sym);
   Cmd->Provide = false;
   Sym->ScriptDefined = true;
 }
 
 // This method is used to handle INSERT AFTER statement. Here we rebuild
 // the list of script commands to mix sections inserted into.

ELF/Relocations.cpp

 // effectively a defined symbol. In the case of copy relocation the symbol is
 // in .bss and in the case of a canonical plt entry it is in .plt. This function
 // replaces the existing symbol with a Defined pointing to the appropriate
 // location.
 static void replaceWithDefined(Symbol &Sym, SectionBase *Sec, uint64_t Value,
                                uint64_t Size) {
   Symbol Old = Sym;
 
-  Defined New(Sym.File, Sym.getName(), Sym.Binding, Sym.StOther, Sym.Type,
-              Value, Size, Sec);
-  replaceSymbol(&Sym, &New);
+  replaceSymbol(&Sym, Defined{Sym.File, Sym.getName(), Sym.Binding, Sym.StOther,
+                              Sym.Type, Value, Size, Sec});
 
   Sym.PltIndex = Old.PltIndex;
   Sym.GotIndex = Old.GotIndex;
   Sym.VerdefIndex = Old.VerdefIndex;
   Sym.PPC64BranchltIndex = Old.PPC64BranchltIndex;
   Sym.IsPreemptible = true;
   Sym.ExportDynamic = true;
   Sym.IsUsedInRegularObj = true;

ELF/SymbolTable.h

 // is one add* function per symbol type.
 class SymbolTable {
 public:
   template <class ELFT> void addCombinedLTOObject();
   void wrap(Symbol *Sym, Symbol *Real, Symbol *Wrap);
 
   ArrayRef<Symbol *> getSymbols() const { return SymVector; }
 
-  Symbol *addUndefined(const Undefined &New);
-  Symbol *addDefined(const Defined &New);
-  Symbol *addShared(const SharedSymbol &New);
-  Symbol *addLazyArchive(const LazyArchive &New);
-  Symbol *addLazyObject(const LazyObject &New);
-  Symbol *addCommon(const CommonSymbol &New);
+  Symbol *insert(StringRef Name);
 
-  Symbol *insert(const Symbol &New);
-  void mergeProperties(Symbol *Old, const Symbol &New);
+  Symbol *addSymbol(const Symbol &New);
 
   void fetchLazy(Symbol *Sym);
 
   void scanVersionScript();
 
   Symbol *find(StringRef Name);
 
   void trace(StringRef Name);
 
   void handleDynamicList();
 
   // Set of .so files to not link the same shared object file more than once.
   llvm::DenseMap<StringRef, SharedFile *> SoNames;
 
 private:
-  template <class LazyT> Symbol *addLazy(const LazyT &New);
-
   std::vector<Symbol *> findByVersion(SymbolVersion Ver);
   std::vector<Symbol *> findAllByVersion(SymbolVersion Ver);
 
   llvm::StringMap<std::vector<Symbol *>> &getDemangledSyms();
   void handleAnonymousVersion();
   void assignExactVersion(SymbolVersion Ver, uint16_t VersionId,
                           StringRef VersionName);
   void assignWildcardVersion(SymbolVersion Ver, uint16_t VersionId);
private:
   // directive in version scripts.
   llvm::Optional<llvm::StringMap<std::vector<Symbol *>>> DemangledSyms;
 
   // For LTO.
   std::unique_ptr<BitcodeCompiler> LTO;
 };
 
 extern SymbolTable *Symtab;
+
+void mergeSymbolProperties(Symbol *Old, const Symbol &New);
+void resolveSymbol(Symbol *Old, const Symbol &New);
+
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/SymbolTable.cpp

 static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) {
   if (VA == STV_DEFAULT)
     return VB;
   if (VB == STV_DEFAULT)
     return VA;
   return std::min(VA, VB);
 }
 
-// Find an existing symbol or create and insert a new one.
-Symbol *SymbolTable::insert(const Symbol &New) {
+// Find an existing symbol or create a new one.
+Symbol *SymbolTable::insert(StringRef Name) {
   // <name>@@<version> means the symbol is the default version. In that
   // case <name>@@<version> will be used to resolve references to <name>.
   //
   // Since this is a hot path, the following string search code is
   // optimized for speed. StringRef::find(char) is much faster than
   // StringRef::find(StringRef).
-  StringRef Name = New.getName();
   size_t Pos = Name.find('@');
   if (Pos != StringRef::npos && Pos + 1 < Name.size() && Name[Pos + 1] == '@')
     Name = Name.take_front(Pos);
 
   auto P = SymMap.insert({CachedHashStringRef(Name), (int)SymVector.size()});
   int &SymIndex = P.first->second;
   bool IsNew = P.second;
   bool Traced = false;
 
   if (SymIndex == -1) {
     SymIndex = SymVector.size();
     IsNew = true;
     Traced = true;
   }
 
-  Symbol *Old;
-  if (IsNew) {
-    Old = reinterpret_cast<Symbol *>(make<SymbolUnion>());
-    SymVector.push_back(Old);
-
-    Old->SymbolKind = Symbol::PlaceholderKind;
-    Old->VersionId = Config->DefaultSymbolVersion;
-    Old->Visibility = STV_DEFAULT;
-    Old->IsUsedInRegularObj = false;
-    Old->ExportDynamic = false;
-    Old->CanInline = true;
-    Old->Traced = Traced;
-    Old->ScriptDefined = false;
-  } else {
-    Old = SymVector[SymIndex];
-  }
+  if (!IsNew)
+    return SymVector[SymIndex];
 
-  return Old;
-}
-
-// Merge symbol properties.
-//
-// When we have many symbols of the same name, we choose one of them,
-// and that's the result of symbol resolution. However, symbols that
-// were not chosen still affect some symbol properteis.
-void SymbolTable::mergeProperties(Symbol *Old, const Symbol &New) {
-  // Merge symbol properties.
-  Old->ExportDynamic = Old->ExportDynamic || New.ExportDynamic;
-  Old->IsUsedInRegularObj = Old->IsUsedInRegularObj || New.IsUsedInRegularObj;
+  Symbol *Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
+  SymVector.push_back(Sym);
 
-  // DSO symbols do not affect visibility in the output.
-  if (!isa<SharedSymbol>(New))
-    Old->Visibility = getMinVisibility(Old->Visibility, New.Visibility);
+  Sym->SymbolKind = Symbol::PlaceholderKind;
+  Sym->VersionId = Config->DefaultSymbolVersion;
+  Sym->Visibility = STV_DEFAULT;
+  Sym->IsUsedInRegularObj = false;
+  Sym->ExportDynamic = false;
+  Sym->CanInline = true;
+  Sym->Traced = Traced;
+  Sym->ScriptDefined = false;
+  return Sym;
 }
 
-Symbol *SymbolTable::addUndefined(const Undefined &New) {
-  Symbol *Old = insert(New);
-  mergeProperties(Old, New);
-
-  if (Old->isPlaceholder()) {
-    replaceSymbol(Old, &New);
-    return Old;
-  }
+Symbol *SymbolTable::addSymbol(const Symbol &New) {
+  Symbol *Old = Symtab->insert(New.getName());
+  resolveSymbol(Old, New);
 
+static void addUndefined(Symbol *Old, const Undefined &New) {
   // An undefined symbol with non default visibility must be satisfied
   // in the same DSO.
   if (Old->isShared() && New.Visibility != STV_DEFAULT) {
-    replaceSymbol(Old, &New);
-    return Old;
+    replaceSymbol(Old, New);
+    return;
   }
 
   if (Old->isShared() || Old->isLazy() ||
       (Old->isUndefined() && New.Binding != STB_WEAK))
     Old->Binding = New.Binding;
 
   if (Old->isLazy()) {
     // An undefined weak will not fetch archive members. See comment on Lazy in
     // Symbols.h for the details.
     if (New.Binding == STB_WEAK) {
       Old->Type = New.Type;
-      return Old;
+      return;
     }
 
     // Do extra check for --warn-backrefs.
     //
     // --warn-backrefs is an option to prevent an undefined reference from
     // fetching an archive member written earlier in the command line. It can be
     // used to keep compatibility with GNU linkers to some degree.
     // I'll explain the feature and why you may find it useful in this comment.
if (Old->isLazy()) {
     //
     //   ld.lld A B --start-group C D --end-group E
     //
     // A forms group 0. B form group 1. C and D (including their member object
     // files) form group 2. E forms group 3. I think that you can see how this
     // group assignment rule simulates the traditional linker's semantics.
     bool Backref = Config->WarnBackrefs && New.File &&
                    Old->File->GroupId < New.File->GroupId;
-    fetchLazy(Old);
+    Symtab->fetchLazy(Old);
 
     // We don't report backward references to weak symbols as they can be
     // overridden later.
     if (Backref && !Old->isWeak())
       warn("backward reference detected: " + New.getName() + " in " +
            toString(New.File) + " refers to " + toString(Old->File));
   }
-  return Old;
 }
 
 // Using .symver foo,foo@@VER unfortunately creates two symbols: foo and
 // foo@@VER. We want to effectively ignore foo, so give precedence to
 // foo@@VER.
 // FIXME: If users can transition to using
 // .symver foo,foo@@@VER
 // we can delete this hack.
static int compare(const Symbol *Old, const Symbol *New) {
 
   if (!OldSym->Section && !NewSym->Section && OldSym->Value == NewSym->Value &&
       NewSym->Binding == STB_GLOBAL)
     return -1;
 
   return 0;
 }
 
-Symbol *SymbolTable::addCommon(const CommonSymbol &New) {
-  Symbol *Old = insert(New);
-  mergeProperties(Old, New);
-
-  if (Old->isPlaceholder()) {
-    replaceSymbol(Old, &New);
-    return Old;
-  }
-
+static void addCommon(Symbol *Old, const CommonSymbol &New) {
   int Cmp = compare(Old, &New);
   if (Cmp < 0)
-    return Old;
+    return;
 
   if (Cmp > 0) {
-    replaceSymbol(Old, &New);
-    return Old;
+    replaceSymbol(Old, New);
+    return;
   }
 
   CommonSymbol *OldSym = cast<CommonSymbol>(Old);
 
   OldSym->Alignment = std::max(OldSym->Alignment, New.Alignment);
   if (OldSym->Size < New.Size) {
     OldSym->File = New.File;
     OldSym->Size = New.Size;
   }
-  return OldSym;
 }
 
 static void reportDuplicate(Symbol *Sym, InputFile *NewFile,
                             InputSectionBase *ErrSec, uint64_t ErrOffset) {
   if (Config->AllowMultipleDefinition)
     return;
 
   Defined *D = cast<Defined>(Sym);
if (!Src1.empty())
     Msg += Src1 + "\n>>>            ";
   Msg += Obj1 + "\n>>> defined at ";
   if (!Src2.empty())
     Msg += Src2 + "\n>>>            ";
   Msg += Obj2;
   error(Msg);
 }
 
-Symbol *SymbolTable::addDefined(const Defined &New) {
-  Symbol *Old = insert(New);
-  mergeProperties(Old, New);
-
-  if (Old->isPlaceholder()) {
-    replaceSymbol(Old, &New);
-    return Old;
-  }
-
+static void addDefined(Symbol *Old, const Defined &New) {
   int Cmp = compare(Old, &New);
   if (Cmp > 0)
-    replaceSymbol(Old, &New);
+    replaceSymbol(Old, New);
   else if (Cmp == 0)
     reportDuplicate(Old, New.File,
                     dyn_cast_or_null<InputSectionBase>(New.Section), New.Value);
-  return Old;
-}
-
-Symbol *SymbolTable::addShared(const SharedSymbol &New) {
-  Symbol *Old = insert(New);
-  mergeProperties(Old, New);
-
-  // Make sure we preempt DSO symbols with default visibility.
-  if (New.Visibility == STV_DEFAULT)
-    Old->ExportDynamic = true;
-
-  if (Old->isPlaceholder()) {
-    replaceSymbol(Old, &New);
-    return Old;
-  }
 
+static void addShared(Symbol *Old, const SharedSymbol &New) {
   if (Old->Visibility == STV_DEFAULT && (Old->isUndefined() || Old->isLazy())) {
     // An undefined symbol with non default visibility must be satisfied
     // in the same DSO.
     uint8_t Binding = Old->Binding;
-    replaceSymbol(Old, &New);
+    replaceSymbol(Old, New);
     Old->Binding = Binding;
   }
-  return Old;
 }
 
 Symbol *SymbolTable::find(StringRef Name) {
   auto It = SymMap.find(CachedHashStringRef(Name));
   if (It == SymMap.end())
     return nullptr;
   if (It->second == -1)
     return nullptr;
   return SymVector[It->second];
 }
 
-template <class LazyT> Symbol *SymbolTable::addLazy(const LazyT &New) {
-  Symbol *Old = insert(New);
-  mergeProperties(Old, New);
-
-  if (Old->isPlaceholder()) {
-    replaceSymbol(Old, &New);
-    return Old;
-  }
-
+template <class LazyT> static void addLazy(Symbol *Old, const LazyT &New) {
   if (!Old->isUndefined())
-    return Old;
+    return;
 
   // An undefined weak will not fetch archive members. See comment on Lazy in
   // Symbols.h for the details.
   if (Old->isWeak()) {
     uint8_t Type = Old->Type;
-    replaceSymbol(Old, &New);
+    replaceSymbol(Old, New);
     Old->Type = Type;
     Old->Binding = STB_WEAK;
-    return Old;
+    return;
   }
 
   if (InputFile *F = New.fetch())
     parseFile(F);
-  return Old;
 }
 
-Symbol *SymbolTable::addLazyArchive(const LazyArchive &New) {
-  return addLazy(New);
+static void addLazyArchive(Symbol *Old, const LazyArchive &New) {
+  addLazy(Old, New);
 }
 
-Symbol *SymbolTable::addLazyObject(const LazyObject &New) {
-  return addLazy(New);
+static void addLazyObject(Symbol *Old, const LazyObject &New) {
+  addLazy(Old, New);
 }
 
 void SymbolTable::fetchLazy(Symbol *Sym) {
   if (auto *S = dyn_cast<LazyArchive>(Sym)) {
     if (InputFile *File = S->fetch())
       parseFile(File);
     return;
   }
void SymbolTable::scanVersionScript() {
 
   // Symbol themselves might know their versions because symbols
   // can contain versions in the form of <name>@<version>.
   // Let them parse and update their names to exclude version suffix.
   for (Symbol *Sym : SymVector)
     Sym->parseSymbolVersion();
 }
 
+// Merge symbol properties.
+//
+// When we have many symbols of the same name, we choose one of them,
+// and that's the result of symbol resolution. However, symbols that
+// were not chosen still affect some symbol properties.
+void elf::mergeSymbolProperties(Symbol *Old, const Symbol &New) {
+  // Merge symbol properties.
+  Old->ExportDynamic = Old->ExportDynamic || New.ExportDynamic;
+  Old->IsUsedInRegularObj = Old->IsUsedInRegularObj || New.IsUsedInRegularObj;
+
+  // DSO symbols do not affect visibility in the output.
+  if (!New.isShared())
+    Old->Visibility = getMinVisibility(Old->Visibility, New.Visibility);
+}
+
+void elf::resolveSymbol(Symbol *Old, const Symbol &New) {
+  mergeSymbolProperties(Old, New);
+
+  if (Old->isPlaceholder()) {
+    replaceSymbol(Old, New);
+    return;
+  }
+
+  switch (New.kind()) {
+  case Symbol::UndefinedKind:
+    addUndefined(Old, cast<Undefined>(New));
+    break;
+  case Symbol::CommonKind:
+    addCommon(Old, cast<CommonSymbol>(New));
+    break;
+  case Symbol::DefinedKind:
+    addDefined(Old, cast<Defined>(New));
+    break;
+  case Symbol::LazyArchiveKind:
+    addLazyArchive(Old, cast<LazyArchive>(New));
+    break;
+  case Symbol::LazyObjectKind:
+    addLazyObject(Old, cast<LazyObject>(New));
+    break;
+  case Symbol::SharedKind:
+    addShared(Old, cast<SharedSymbol>(New));
+    break;
+  case Symbol::PlaceholderKind:
+    llvm_unreachable("bad symbol kind");
+  }
+}
+
 template void SymbolTable::addCombinedLTOObject<ELF32LE>();
 template void SymbolTable::addCombinedLTOObject<ELF32BE>();
 template void SymbolTable::addCombinedLTOObject<ELF64LE>();
 template void SymbolTable::addCombinedLTOObject<ELF64BE>();

ELF/Symbols.h

public:
   uint64_t getGotPltOffset() const;
   uint64_t getGotPltVA() const;
   uint64_t getPltVA() const;
   uint64_t getPPC64LongBranchTableVA() const;
   uint64_t getPPC64LongBranchOffset() const;
   uint64_t getSize() const;
   OutputSection *getOutputSection() const;
 
+private:
+  static bool isExportDynamic(Kind K, uint8_t Visibility) {
+    if (K == SharedKind)
+      return Visibility == llvm::ELF::STV_DEFAULT;
+    return Config->Shared || Config->ExportDynamic;
+  }
+
 protected:
   Symbol(Kind K, InputFile *File, StringRefZ Name, uint8_t Binding,
          uint8_t StOther, uint8_t Type)
       : File(File), NameData(Name.Data), NameSize(Name.Size), Binding(Binding),
         Type(Type), StOther(StOther), SymbolKind(K), Visibility(StOther & 3),
         IsUsedInRegularObj(!File || File->kind() == InputFile::ObjKind),
-        ExportDynamic(K != SharedKind &&
-                      (Config->Shared || Config->ExportDynamic)),
-        CanInline(false), Traced(false), NeedsPltAddr(false), IsInIplt(false),
-        GotInIgot(false), IsPreemptible(false), Used(!Config->GcSections),
-        NeedsTocRestore(false), ScriptDefined(false) {}
+        ExportDynamic(isExportDynamic(K, Visibility)), CanInline(false),
+        Traced(false), NeedsPltAddr(false), IsInIplt(false), GotInIgot(false),
+        IsPreemptible(false), Used(!Config->GcSections), NeedsTocRestore(false),
+        ScriptDefined(false) {}
 
 public:
   // True the symbol should point to its PLT entry.
   // For SharedSymbol only.
   unsigned NeedsPltAddr : 1;
 
   // True if this symbol is in the Iplt sub-section of the Plt and the Igot
   // sub-section of the .got.plt or .got.
struct ElfSym {
   static Defined *RelaIpltEnd;
 };
 
 // A buffer class that is large enough to hold any Symbol-derived
 // object. We allocate memory using this class and instantiate a symbol
 // using the placement new.
 union SymbolUnion {
   alignas(Defined) char A[sizeof(Defined)];
+  alignas(CommonSymbol) char B[sizeof(CommonSymbol)];
   alignas(Undefined) char C[sizeof(Undefined)];
   alignas(SharedSymbol) char D[sizeof(SharedSymbol)];
   alignas(LazyArchive) char E[sizeof(LazyArchive)];
   alignas(LazyObject) char F[sizeof(LazyObject)];
 };
 
-void printTraceSymbol(Symbol *Sym);
-
-template <typename T> void replaceSymbol(Symbol *Sym, const T *New) {
-  using llvm::ELF::STT_TLS;
-
+template <typename T> struct AssertSymbol {
   static_assert(std::is_trivially_destructible<T>(),
                 "Symbol types must be trivially destructible");
   static_assert(sizeof(T) <= sizeof(SymbolUnion), "SymbolUnion too small");
   static_assert(alignof(T) <= alignof(SymbolUnion),
                 "SymbolUnion not aligned enough");
-  assert(static_cast<Symbol *>(static_cast<T *>(nullptr)) == nullptr &&
-         "Not a Symbol");
+};
+
+static inline void assertSymbols() {
+  AssertSymbol<Defined>();
+  AssertSymbol<CommonSymbol>();
+  AssertSymbol<Undefined>();
+  AssertSymbol<SharedSymbol>();
+  AssertSymbol<LazyArchive>();
+  AssertSymbol<LazyObject>();
+}
+
+void printTraceSymbol(Symbol *Sym);
+
+static size_t getSymbolSize(const Symbol &Sym) {
+  switch (Sym.kind()) {
+  case Symbol::CommonKind:
+    return sizeof(CommonSymbol);
+  case Symbol::DefinedKind:
+    return sizeof(Defined);
+  case Symbol::LazyArchiveKind:
+    return sizeof(LazyArchive);
+  case Symbol::LazyObjectKind:
+    return sizeof(LazyObject);
+  case Symbol::SharedKind:
+    return sizeof(SharedSymbol);
+  case Symbol::UndefinedKind:
+    return sizeof(Undefined);
+  case Symbol::PlaceholderKind:
+    return sizeof(Symbol);
+  }
+}
+
+inline void replaceSymbol(Symbol *Sym, const Symbol &New) {
+  using llvm::ELF::STT_TLS;
 
   // Symbols representing thread-local variables must be referenced by
   // TLS-aware relocations, and non-TLS symbols must be reference by
   // non-TLS relocations, so there's a clear distinction between TLS
   // and non-TLS symbols. It is an error if the same symbol is defined
   // as a TLS symbol in one file and as a non-TLS symbol in other file.
   if (Sym->SymbolKind != Symbol::PlaceholderKind && !Sym->isLazy() &&
-      !New->isLazy()) {
-    bool TlsMismatch = (Sym->Type == STT_TLS && New->Type != STT_TLS) ||
-                       (Sym->Type != STT_TLS && New->Type == STT_TLS);
+      !New.isLazy()) {
+    bool TlsMismatch = (Sym->Type == STT_TLS && New.Type != STT_TLS) ||
+                       (Sym->Type != STT_TLS && New.Type == STT_TLS);
     if (TlsMismatch)
       error("TLS attribute mismatch: " + toString(*Sym) + "\n>>> defined in " +
-            toString(New->File) + "\n>>> defined in " + toString(Sym->File));
+            toString(New.File) + "\n>>> defined in " + toString(Sym->File));
   }
 
   Symbol Old = *Sym;
-  memcpy(Sym, New, sizeof(T));
+  memcpy(Sym, &New, getSymbolSize(New));
 
   Sym->VersionId = Old.VersionId;
   Sym->Visibility = Old.Visibility;
   Sym->IsUsedInRegularObj = Old.IsUsedInRegularObj;
   Sym->ExportDynamic = Old.ExportDynamic;
   Sym->CanInline = Old.CanInline;
   Sym->Traced = Old.Traced;
   Sym->ScriptDefined = Old.ScriptDefined;

ELF/Writer.cpp

 
 static Defined *addOptionalRegular(StringRef Name, SectionBase *Sec,
                                    uint64_t Val, uint8_t StOther = STV_HIDDEN,
                                    uint8_t Binding = STB_GLOBAL) {
   Symbol *S = Symtab->find(Name);
   if (!S || S->isDefined())
     return nullptr;
 
-  return cast<Defined>(Symtab->addDefined(
+  return cast<Defined>(Symtab->addSymbol(
       Defined{/*File=*/nullptr, Name, Binding, StOther, STT_NOTYPE, Val,
               /*Size=*/0, Sec}));
 }
 
 static Defined *addAbsolute(StringRef Name) {
-  Defined New(nullptr, Name, STB_GLOBAL, STV_HIDDEN, STT_NOTYPE, 0, 0, nullptr);
-  Symbol *Sym = Symtab->addDefined(New);
+  Symbol *Sym = Symtab->addSymbol(Defined{nullptr, Name, STB_GLOBAL, STV_HIDDEN,
+                                          STT_NOTYPE, 0, 0, nullptr});
   if (!Sym->isDefined())
     error("duplicate symbol: " + toString(*Sym));
   return cast<Defined>(Sym);
 }
 
 // The linker is expected to define some symbols depending on
 // the linking result. This function defines such symbols.
 void elf::addReservedSymbols() {
if (S->isDefined()) {
             GotSymName + "'");
       return;
     }
 
     uint64_t GotOff = 0;
     if (Config->EMachine == EM_PPC || Config->EMachine == EM_PPC64)
       GotOff = 0x8000;
 
-    Symtab->addDefined(Defined{/*File=*/nullptr, GotSymName, STB_GLOBAL,
-                               STV_HIDDEN, STT_NOTYPE, GotOff, /*Size=*/0,
-                               Out::ElfHeader});
+    Symtab->addSymbol(Defined{/*File=*/nullptr, GotSymName, STB_GLOBAL,
     ElfSym::GlobalOffsetTable = cast<Defined>(S);
   }
 
   // __ehdr_start is the location of ELF file headers. Note that we define
   // this symbol unconditionally even when using a linker script, which
   // differs from the behavior implemented by GNU linker which only define
   // this symbol if ELF headers are in the memory mapped segment.
   addOptionalRegular("__ehdr_start", Out::ElfHeader, 0, STV_HIDDEN);
for (BaseCommand *Base : Script->SectionCommands)
         addStartStopSymbols(Sec);
   }
 
   // Add _DYNAMIC symbol. Unlike GNU gold, our _DYNAMIC symbol has no type.
   // It should be okay as no one seems to care about the type.
   // Even the author of gold doesn't remember why gold behaves that way.
   // https://sourceware.org/ml/binutils/2002-03/msg00360.html
   if (In.Dynamic->Parent)
-    Symtab->addDefined(Defined{/*File=*/nullptr, "_DYNAMIC", STB_WEAK,
-                               STV_HIDDEN, STT_NOTYPE,
-                               /*Value=*/0, /*Size=*/0, In.Dynamic});
+    Symtab->addSymbol(Defined{/*File=*/nullptr, "_DYNAMIC", STB_WEAK,
 
   // Define __rel[a]_iplt_{start,end} symbols if needed.
   addRelIpltSymbols();
 
   // RISC-V's gp can address +/- 2 KiB, set it to .sdata + 0x800 if not defined.
   if (Config->EMachine == EM_RISCV)
     if (!dyn_cast_or_null<Defined>(Symtab->find("__global_pointer$")))
       addOptionalRegular("__global_pointer$", findSection(".sdata"), 0x800);