ELF: New symbol table design.

[pcc]

Summary

This patch implements a new design for the symbol table that stores
SymbolBodies within a memory region of the Symbol object. Symbols are mutated
by constructing SymbolBodies in place over existing SymbolBodies, rather
than by mutating pointers. As mentioned in the initial proposal [1], this
memory layout helps reduce the cache miss rate by improving memory locality.

Performance numbers:

old(s) new(s)

Without debug info:
chrome 7.178 6.432 (-11.5%)
LLVMgold.so 0.505 0.502 (-0.5%)
clang 0.954 0.827 (-15.4%)
llvm-as 0.052 0.045 (-15.5%)
With debug info:
scylla 5.695 5.613 (-1.5%)
clang 14.396 14.143 (-1.8%)

Performance counter results show that the fewer required indirections is
indeed the cause of the improved performance. For example, when linking
chrome, stalled cycles decreases from 14,556,444,002 to 12,959,238,310, and
instructions per cycle increases from 0.78 to 0.83. We are also executing
many fewer instructions (15,516,401,933 down to 15,002,434,310), probably
because we spend less time allocating SymbolBodies.

The new mechanism by which symbols are added to the symbol table is by calling
add* functions on the SymbolTable. In order to make this work for untemplated
file types such as BitcodeFile, I split SymbolTable into an untemplated base
class and a templated derived class.

In this patch, I handle local symbols by storing them inside "unparented"
SymbolBodies. This is suboptimal, but if we do want to try to avoid allocating
these SymbolBodies, we can probably do that separately.

I also removed a few members from the SymbolBody class that were only being
used to pass information from the input file to the symbol table.

This patch implements the new design for the ELF linker only. Once we're
happy with the new implementation, I intend to prepare a similar patch for
the COFF linker. I have updated the documentation under the assumption that
we will update both linkers, but we can probably land this first.

[1] http://lists.llvm.org/pipermail/llvm-dev/2016-April/098832.html

[ruiu]

This is generally looking good. First round of review comments.

ELF/InputFiles.h

126–127 ↗

(On Diff #55688)

I think it's better to make Symtab globally accessible just like Config object. It is a singleton, and it is accessed everywhere (Writer is using it, symbol resolution of course uses it, and now file parsing is starting to use it.)

190 ↗

(On Diff #55688)

Can we merge SymbolTableBase with SymbolTable<ELFT> if you template this, ArchiveFile::parse and BitcodeFile::parse functions?

ELF/LTO.cpp

112 ↗

(On Diff #55688)

undefine -> Undefine

ELF/SymbolTable.cpp

136 ↗

(On Diff #55688)

This comment seems obsolete.

266 ↗

(On Diff #55688)

Can you define two variables for P's members and use std::tie?

293 ↗

(On Diff #55688)

Please separate the pair members so that we can give explicit name for each member.

330 ↗

(On Diff #55688)

auto -> int

[• rafael]

I really like where this is going. I can also reproduce the speed improvements:

chromium

master 5.024864816
patch  4.623026768 0.92003007788

chromium fast

master 1.79596235
patch  1.674374543 0.932299356387

the gold plugin

master 0.380117134
patch  0.35906784 0.9446241905

clang

master 0.661575233
patch  0.623685952 0.942728688878

llvm-as

master 0.036052227
patch  0.034932404 0.968938867494

the gold plugin fsds

master 0.407010562
patch  0.384177885 0.943901512315

clang fsds

master 0.74843173
patch  0.704943104 0.941893663434

llvm-as fsds

master 0.032178185
patch  0.031151157 0.968083097291

scylla

master 4.159922688
patch  4.089454365 0.983060184459

ELF/InputFiles.h

212 ↗

(On Diff #55688)

I am really happy to see these temporary vectors go. We now only have object local vector of symbols when something refers to them by index (relocations) :-)

ELF/Symbols.h

427 ↗

(On Diff #55688)

Using ELF64LE is here is problematic as the SharedSymbol has a pointer to Elf_Sym. As silly as it sounds I think you need to include the various ELFTs in the "union".

And can this be just a plain union?

[• rafael]

• void parse(); -
• llvm::MutableArrayRef<LazyObject> getLazySymbols() { return LazySymbols; }

+ void parse(SymbolTableBase *Symtab);

---

Can we merge SymbolTableBase with SymbolTable<ELFT> if you template this, ArchiveFile::parse and BitcodeFile::parse functions?

I assume these vectors make it hard:

std::vector<std::unique_ptr<ObjectFile<ELFT>>> ObjectFiles;

std::vector<std::unique_ptr<SharedFile<ELFT>>> SharedFiles;

Cheers,
Rafael

[pcc]

• Merge SymbolTableBase and SymbolTable, and add Symtab global
• Fix merge error
• Remove some unused members of SymbolBody
• undefine -> Undefine
• Remove obsolete comment
• auto Cmp -> int Cmp
• Use std::tie

ELF/InputFiles.h

190 ↗

(On Diff #55688)

I can, done. I'm not sure if it's a good idea to add more template bloat like this, but we can probably think about that separately.

ELF/Symbols.h

427 ↗

(On Diff #55688)

All I need is an appropriately sized and aligned char array. That's what AlignedCharArrayUnion provides. I never actually access this field as a SharedSymbol<ELF64LE> for example (unless of course I'm in a templated function with ELFT=ELF64LE). I'm making an assumption here that ELF32* data structures are not larger or more aligned than ELF64* data structures (and the same for LE and BE), but if they somehow are not, that's what the static_asserts below are for.

I think this could be a union, but we'd need default constructors in every derived class of SymbolBody, and I think we'd need to use the unrestricted unions feature of C++, which MSVC doesn't support until 2015.

[dblaikie]

Just some cursory code review because I was curious to see the implementation (the aligned storage usage, etc) - nothing vital, feel free to take-or-leave as you see fit.

ELF/MarkLive.cpp

141–142 ↗

(On Diff #55688)

(unrelated cleanup: this could/should just be dyn_cast_or_null)

ELF/SymbolTable.cpp

282–283 ↗

(On Diff #55688)

Should this just be an else-if?

334–335 ↗

(On Diff #55688)

else-after-return

369–373 ↗

(On Diff #55688)

Seems to be a bit of inconsistency about whether single line blocks have {} or not here (& elsewhere in this change)

451 ↗

(On Diff #55688)

Could invert this & use an early return to reduce indentation, perhaps.

489–490 ↗

(On Diff #55688)

Could roll these together with dyn_cast_or_null

ELF/Symbols.h

63–65 ↗

(On Diff #55688)

I think, technically, from a UB perspective, you want to implement the non-const version in terms of the const version rather than the other way around.

If this object were really const then you'd have UB const_casting it and calling a member function. But if you do it the other way - you just call a const operation, knowing you have a non-const object, and cast away the constness of the result because you know it's not really const.

431 ↗

(On Diff #55688)

Same here (wrt const/non-const overload implementation)

[• rafael]

And can this be just a plain union?

All I need is an appropriately sized and aligned char array. That's what AlignedCharArrayUnion provides. I never actually access this field as a SharedSymbol<ELF64LE> for example (unless of course I'm in a templated function with ELFT=ELF64LE). I'm making an assumption here that ELF32* data structures are not larger or more aligned than ELF64* data structures (and the same for LE and BE), but if they somehow are not, that's what the static_asserts below are for.

Got it. Please add a comment :-)

I liked the non templated base, but yes, we can discuss that in another patch.

Cheers,
Rafael

[• rafael]

In any case. I am happy with this patch if others are happy.

We can discuss templating less code in another patch.

[pcc]

• A few simplifications from David
• Improve comment for Symbol::Body

[pcc]

Got it. Please add a comment :-)

Done

ELF/Symbols.h

63–65 ↗

(On Diff #55732)

I see. I think all the Symbol objects we ever create are in fact non-const, so this is somewhat of a moot point. Writing these the other way around would I think be a little more verbose, so I'll keep this the way it is. Thanks for pointing that out though.

[davide]

Thank for doing this, I found your code to be up to 15% faster while linking some FreeBSD system binaries.
As a general comment, I find the new logic slightly easier to understand, so my hope is that you convert the COFF linker once you get a chance. I don't find any obvious problems with the patch, and others commented at length on the style, so I have very little to add. lgtm.

lld/trunk/ELF/Driver.cpp

void LinkerDriver::createFiles(opt::InputArgList &Args) {
   if (Files.empty() && !HasError)
     error("no input files.");
 }
 
 // Do actual linking. Note that when this function is called,
 // all linker scripts have already been parsed.
 template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   SymbolTable<ELFT> Symtab;
+  elf::Symtab<ELFT>::X = &Symtab;
 
   std::unique_ptr<TargetInfo> TI(createTarget());
   Target = TI.get();
   LinkerScript<ELFT> LS;
   Script<ELFT>::X = &LS;
 
   Config->Rela = ELFT::Is64Bits;
 
   // Add entry symbol. Note that AMDGPU binaries have no entry points.
   if (Config->Entry.empty() && !Config->Shared && !Config->Relocatable &&
       Config->EMachine != EM_AMDGPU)
     Config->Entry = (Config->EMachine == EM_MIPS) ? "__start" : "_start";
 
   // Default output filename is "a.out" by the Unix tradition.
   if (Config->OutputFile.empty())
     Config->OutputFile = "a.out";
 
   // Set either EntryAddr (if S is a number) or EntrySym (otherwise).
   if (!Config->Entry.empty()) {
     StringRef S = Config->Entry;
     if (S.getAsInteger(0, Config->EntryAddr))
-      Config->EntrySym = Symtab.addUndefined(S)->Backref;
+      Config->EntrySym = Symtab.addUndefined(S);
   }
 
   for (std::unique_ptr<InputFile> &F : Files)
     Symtab.addFile(std::move(F));
   if (HasError)
     return; // There were duplicate symbols or incompatible files
 
   Symtab.scanUndefinedFlags();

lld/trunk/ELF/InputFiles.h

public:
   uint8_t getOSABI() const {
     return getObj().getHeader()->e_ident[llvm::ELF::EI_OSABI];
   }
 
   StringRef getStringTable() const { return StringTable; }
 
   uint32_t getSectionIndex(const Elf_Sym &Sym) const;
 
+  Elf_Sym_Range getElfSymbols(bool OnlyGlobals);
+
 protected:
   llvm::object::ELFFile<ELFT> ELFObj;
   const Elf_Shdr *Symtab = nullptr;
   ArrayRef<Elf_Word> SymtabSHNDX;
   StringRef StringTable;
   void initStringTable();
-  Elf_Sym_Range getElfSymbols(bool OnlyGlobals);
 };
 
 // .o file.
 template <class ELFT> class ObjectFile : public ELFFileBase<ELFT> {
   typedef ELFFileBase<ELFT> Base;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::SymRange Elf_Sym_Range;
public:
 
   explicit ObjectFile(MemoryBufferRef M);
   void parse(llvm::DenseSet<StringRef> &ComdatGroups);
 
   ArrayRef<InputSectionBase<ELFT> *> getSections() const { return Sections; }
   InputSectionBase<ELFT> *getSection(const Elf_Sym &Sym) const;
 
   SymbolBody &getSymbolBody(uint32_t SymbolIndex) const {
-    return SymbolBodies[SymbolIndex]->repl();
+    return *SymbolBodies[SymbolIndex];
   }
 
   template <typename RelT> SymbolBody &getRelocTargetSym(const RelT &Rel) const {
     uint32_t SymIndex = Rel.getSymbol(Config->Mips64EL);
     return getSymbolBody(SymIndex);
   }
 
   const Elf_Shdr *getSymbolTable() const { return this->Symtab; };

 class LazyObjectFile : public InputFile {
 public:
   explicit LazyObjectFile(MemoryBufferRef M) : InputFile(LazyObjectKind, M) {}
 
   static bool classof(const InputFile *F) {
     return F->kind() == LazyObjectKind;
   }
 
-  void parse();
-
-  llvm::MutableArrayRef<LazyObject> getLazySymbols() { return LazySymbols; }
+  template <class ELFT> void parse();
 
 private:
   std::vector<StringRef> getSymbols();
   template <class ELFT> std::vector<StringRef> getElfSymbols();
   std::vector<StringRef> getBitcodeSymbols();
 
   llvm::BumpPtrAllocator Alloc;
   llvm::StringSaver Saver{Alloc};
-  std::vector<LazyObject> LazySymbols;
 };
 
 // An ArchiveFile object represents a .a file.
 class ArchiveFile : public InputFile {
 public:
   explicit ArchiveFile(MemoryBufferRef M) : InputFile(ArchiveKind, M) {}
   static bool classof(const InputFile *F) { return F->kind() == ArchiveKind; }
-  void parse();
+  template <class ELFT> void parse();
 
   // Returns a memory buffer for a given symbol. An empty memory buffer
   // is returned if we have already returned the same memory buffer.
   // (So that we don't instantiate same members more than once.)
   MemoryBufferRef getMember(const Archive::Symbol *Sym);
 
-  llvm::MutableArrayRef<LazyArchive> getLazySymbols() { return LazySymbols; }
-
 private:
   std::unique_ptr<Archive> File;
-  std::vector<LazyArchive> LazySymbols;
   llvm::DenseSet<uint64_t> Seen;
 };
 
 class BitcodeFile : public InputFile {
 public:
   explicit BitcodeFile(MemoryBufferRef M);
-  static bool classof(const InputFile *F);
+  static bool classof(const InputFile *F) { return F->kind() == BitcodeKind; }
+  template <class ELFT>
   void parse(llvm::DenseSet<StringRef> &ComdatGroups);
-  ArrayRef<SymbolBody *> getSymbols() { return SymbolBodies; }
-  static bool shouldSkip(const llvm::object::BasicSymbolRef &Sym);
+  ArrayRef<Symbol *> getSymbols() { return Symbols; }
+  static bool shouldSkip(uint32_t Flags);
   std::unique_ptr<llvm::object::IRObjectFile> Obj;
 
 private:
-  std::vector<SymbolBody *> SymbolBodies;
+  std::vector<Symbol *> Symbols;
   llvm::BumpPtrAllocator Alloc;
   llvm::StringSaver Saver{Alloc};
-  SymbolBody *
-  createSymbolBody(const llvm::DenseSet<const llvm::Comdat *> &KeptComdats,
+  template <class ELFT>
+  Symbol *createSymbol(const llvm::DenseSet<const llvm::Comdat *> &KeptComdats,
                        const llvm::object::IRObjectFile &Obj,
                        const llvm::object::BasicSymbolRef &Sym);
-  SymbolBody *
-  createBody(const llvm::DenseSet<const llvm::Comdat *> &KeptComdats,
-             const llvm::object::IRObjectFile &Obj,
-             const llvm::object::BasicSymbolRef &Sym,
-             const llvm::GlobalValue *GV);
 };
 
 // .so file.
 template <class ELFT> class SharedFile : public ELFFileBase<ELFT> {
   typedef ELFFileBase<ELFT> Base;
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Word Elf_Word;
   typedef typename ELFT::SymRange Elf_Sym_Range;
   typedef typename ELFT::Versym Elf_Versym;
   typedef typename ELFT::Verdef Elf_Verdef;
 
-  std::vector<SharedSymbol<ELFT>> SymbolBodies;
   std::vector<StringRef> Undefs;
   StringRef SoName;
   const Elf_Shdr *VersymSec = nullptr;
   const Elf_Shdr *VerdefSec = nullptr;
 
 public:
   StringRef getSoName() const { return SoName; }
-  llvm::MutableArrayRef<SharedSymbol<ELFT>> getSharedSymbols() {
-    return SymbolBodies;
-  }
   const Elf_Shdr *getSection(const Elf_Sym &Sym) const;
   llvm::ArrayRef<StringRef> getUndefinedSymbols() { return Undefs; }
 
   static bool classof(const InputFile *F) {
     return F->kind() == Base::SharedKind;
   }
 
   explicit SharedFile(MemoryBufferRef M);

lld/trunk/ELF/InputFiles.cpp

 //===- InputFiles.cpp -----------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputFiles.h"
 #include "Driver.h"
 #include "Error.h"
 #include "InputSection.h"
+#include "SymbolTable.h"
 #include "Symbols.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
if (Sym->st_shndx == SHN_UNDEF)
       return new (Alloc) Undefined(Sym->st_name, Sym->st_other, Sym->getType());
     return new (Alloc) DefinedRegular<ELFT>(*Sym, Sec);
   }
 
   StringRef Name = check(Sym->getName(this->StringTable));
 
   switch (Sym->st_shndx) {
   case SHN_UNDEF:
-    return new (Alloc) Undefined(Name, Binding, Sym->st_other, Sym->getType(),
-                                 /*IsBitcode*/ false);
+    return Symtab<ELFT>::X
+        ->addUndefined(Name, Binding, Sym->st_other, Sym->getType(), this)
+        ->body();
   case SHN_COMMON:
-    return new (Alloc) DefinedCommon(Name, Sym->st_size, Sym->st_value, Binding,
-                                     Sym->st_other, Sym->getType());
+    return Symtab<ELFT>::X
+        ->addCommon(Name, Sym->st_size, Sym->st_value, Binding, Sym->st_other,
+                    Sym->getType(), this)
+        ->body();
   }
 
   switch (Binding) {
   default:
     fatal("unexpected binding");
   case STB_GLOBAL:
   case STB_WEAK:
   case STB_GNU_UNIQUE:
     if (Sec == &InputSection<ELFT>::Discarded)
-      return new (Alloc) Undefined(Name, Binding, Sym->st_other, Sym->getType(),
-                                   /*IsBitcode*/ false);
-    return new (Alloc) DefinedRegular<ELFT>(Name, *Sym, Sec);
+      return Symtab<ELFT>::X
+          ->addUndefined(Name, Binding, Sym->st_other, Sym->getType(), this)
+          ->body();
+    return Symtab<ELFT>::X->addRegular(Name, *Sym, Sec)->body();
   }
 }
 
-void ArchiveFile::parse() {
+template <class ELFT> void ArchiveFile::parse() {
   File = check(Archive::create(MB), "failed to parse archive");
 
-  // Allocate a buffer for Lazy objects.
-  size_t NumSyms = File->getNumberOfSymbols();
-  LazySymbols.reserve(NumSyms);
-
   // Read the symbol table to construct Lazy objects.
   for (const Archive::Symbol &Sym : File->symbols())
-    LazySymbols.emplace_back(this, Sym);
+    Symtab<ELFT>::X->addLazyArchive(this, Sym);
 }
 
 // Returns a buffer pointing to a member file containing a given symbol.
 MemoryBufferRef ArchiveFile::getMember(const Archive::Symbol *Sym) {
   Archive::Child C =
       check(Sym->getMember(),
             "could not get the member for symbol " + Sym->getName());
 

 
 // Fully parse the shared object file. This must be called after parseSoName().
 template <class ELFT> void SharedFile<ELFT>::parseRest() {
   // Create mapping from version identifiers to Elf_Verdef entries.
   const Elf_Versym *Versym = nullptr;
   std::vector<const Elf_Verdef *> Verdefs = parseVerdefs(Versym);
 
   Elf_Sym_Range Syms = this->getElfSymbols(true);
-  uint32_t NumSymbols = std::distance(Syms.begin(), Syms.end());
-  SymbolBodies.reserve(NumSymbols);
   for (const Elf_Sym &Sym : Syms) {
     unsigned VersymIndex = 0;
     if (Versym) {
       VersymIndex = Versym->vs_index;
       ++Versym;
     }
 
     StringRef Name = check(Sym.getName(this->StringTable));
     if (Sym.isUndefined()) {
       Undefs.push_back(Name);
       continue;
     }
 
     if (Versym) {
       // Ignore local symbols and non-default versions.
       if (VersymIndex == 0 || (VersymIndex & VERSYM_HIDDEN))
         continue;
     }
-    SymbolBodies.emplace_back(this, Name, Sym, Verdefs[VersymIndex]);
+    Symtab<ELFT>::X->addShared(this, Name, Sym, Verdefs[VersymIndex]);
   }
 }
 
 BitcodeFile::BitcodeFile(MemoryBufferRef M) : InputFile(BitcodeKind, M) {}
 
-bool BitcodeFile::classof(const InputFile *F) {
-  return F->kind() == BitcodeKind;
-}
-
 static uint8_t getGvVisibility(const GlobalValue *GV) {
   switch (GV->getVisibility()) {
   case GlobalValue::DefaultVisibility:
     return STV_DEFAULT;
   case GlobalValue::HiddenVisibility:
     return STV_HIDDEN;
   case GlobalValue::ProtectedVisibility:
     return STV_PROTECTED;
   }
   llvm_unreachable("unknown visibility");
 }
 
-SymbolBody *
-BitcodeFile::createBody(const DenseSet<const Comdat *> &KeptComdats,
+template <class ELFT>
+Symbol *BitcodeFile::createSymbol(const DenseSet<const Comdat *> &KeptComdats,
                                   const IRObjectFile &Obj,
-                              const BasicSymbolRef &Sym,
-                              const GlobalValue *GV) {
+                                  const BasicSymbolRef &Sym) {
+  const GlobalValue *GV = Obj.getSymbolGV(Sym.getRawDataRefImpl());
+
   SmallString<64> Name;
   raw_svector_ostream OS(Name);
   Sym.printName(OS);
   StringRef NameRef = Saver.save(StringRef(Name));
-  SymbolBody *Body;
 
   uint32_t Flags = Sym.getFlags();
   bool IsWeak = Flags & BasicSymbolRef::SF_Weak;
   uint32_t Binding = IsWeak ? STB_WEAK : STB_GLOBAL;
 
+  uint8_t Type = STT_NOTYPE;
+  bool CanOmitFromDynSym = false;
+  // FIXME: Expose a thread-local flag for module asm symbols.
+  if (GV) {
+    if (GV->isThreadLocal())
+      Type = STT_TLS;
+    CanOmitFromDynSym = canBeOmittedFromSymbolTable(GV);
+  }
+
   uint8_t Visibility;
   if (GV)
     Visibility = getGvVisibility(GV);
   else
     // FIXME: Set SF_Hidden flag correctly for module asm symbols, and expose
     // protected visibility.
     Visibility = STV_DEFAULT;
 
   if (GV)
     if (const Comdat *C = GV->getComdat())
-      if (!KeptComdats.count(C)) {
-        Body = new (Alloc) Undefined(NameRef, Binding, Visibility, /*Type*/ 0,
-                                     /*IsBitcode*/ true);
-        return Body;
-      }
+      if (!KeptComdats.count(C))
+        return Symtab<ELFT>::X->addUndefined(NameRef, Binding, Visibility, Type,
+                                             this);
 
   const Module &M = Obj.getModule();
   if (Flags & BasicSymbolRef::SF_Undefined)
-    return new (Alloc) Undefined(NameRef, Binding, Visibility, /*Type*/ 0,
-                                 /*IsBitcode*/ true);
+    return Symtab<ELFT>::X->addUndefined(NameRef, Binding, Visibility, Type,
+                                         this);
   if (Flags & BasicSymbolRef::SF_Common) {
     // FIXME: Set SF_Common flag correctly for module asm symbols, and expose
     // size and alignment.
     assert(GV);
     const DataLayout &DL = M.getDataLayout();
     uint64_t Size = DL.getTypeAllocSize(GV->getValueType());
-    return new (Alloc) DefinedCommon(NameRef, Size, GV->getAlignment(), Binding,
-                                     Visibility, /*Type*/ 0);
+    return Symtab<ELFT>::X->addCommon(NameRef, Size, GV->getAlignment(),
+                                      Binding, Visibility, STT_OBJECT, this);
   }
-  return new (Alloc) DefinedBitcode(NameRef, IsWeak, Visibility);
+  return Symtab<ELFT>::X->addBitcode(NameRef, IsWeak, Visibility, Type,
+                                     CanOmitFromDynSym, this);
 }
 
-SymbolBody *
-BitcodeFile::createSymbolBody(const DenseSet<const Comdat *> &KeptComdats,
-                              const IRObjectFile &Obj,
-                              const BasicSymbolRef &Sym) {
-  const GlobalValue *GV = Obj.getSymbolGV(Sym.getRawDataRefImpl());
-  SymbolBody *Body = createBody(KeptComdats, Obj, Sym, GV);
-
-  // FIXME: Expose a thread-local flag for module asm symbols.
-  if (GV) {
-    if (GV->isThreadLocal())
-      Body->Type = STT_TLS;
-    Body->CanOmitFromDynSym = canBeOmittedFromSymbolTable(GV);
-  }
-  return Body;
-}
-
-bool BitcodeFile::shouldSkip(const BasicSymbolRef &Sym) {
-  uint32_t Flags = Sym.getFlags();
+bool BitcodeFile::shouldSkip(uint32_t Flags) {
   if (!(Flags & BasicSymbolRef::SF_Global))
     return true;
   if (Flags & BasicSymbolRef::SF_FormatSpecific)
     return true;
   return false;
 }
 
+template <class ELFT>
 void BitcodeFile::parse(DenseSet<StringRef> &ComdatGroups) {
   Obj = check(IRObjectFile::create(MB, Driver->Context));
   const Module &M = Obj->getModule();
 
   DenseSet<const Comdat *> KeptComdats;
   for (const auto &P : M.getComdatSymbolTable()) {
     StringRef N = Saver.save(P.first());
     if (ComdatGroups.insert(N).second)
       KeptComdats.insert(&P.second);
   }
 
   for (const BasicSymbolRef &Sym : Obj->symbols())
-    if (!shouldSkip(Sym))
-      SymbolBodies.push_back(createSymbolBody(KeptComdats, *Obj, Sym));
+    if (!shouldSkip(Sym.getFlags()))
+      Symbols.push_back(createSymbol<ELFT>(KeptComdats, *Obj, Sym));
 }
 
 template <typename T>
 static std::unique_ptr<InputFile> createELFFileAux(MemoryBufferRef MB) {
   std::unique_ptr<T> Ret = llvm::make_unique<T>(MB);
 
   if (!Config->FirstElf)
     Config->FirstElf = Ret.get();
std::unique_ptr<InputFile> elf::createObjectFile(MemoryBufferRef MB,
   F->ArchiveName = ArchiveName;
   return F;
 }
 
 std::unique_ptr<InputFile> elf::createSharedFile(MemoryBufferRef MB) {
   return createELFFile<SharedFile>(MB);
 }
 
+template <class ELFT>
 void LazyObjectFile::parse() {
   for (StringRef Sym : getSymbols())
-    LazySymbols.emplace_back(Sym, this->MB);
+    Symtab<ELFT>::X->addLazyObject(Sym, this->MB);
 }
 
 template <class ELFT> std::vector<StringRef> LazyObjectFile::getElfSymbols() {
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::SymRange Elf_Sym_Range;
 
   const ELFFile<ELFT> Obj = createELFObj<ELFT>(this->MB);

 }
 
 std::vector<StringRef> LazyObjectFile::getBitcodeSymbols() {
   LLVMContext Context;
   std::unique_ptr<IRObjectFile> Obj =
       check(IRObjectFile::create(this->MB, Context));
   std::vector<StringRef> V;
   for (const BasicSymbolRef &Sym : Obj->symbols()) {
-    if (BitcodeFile::shouldSkip(Sym))
+    uint32_t Flags = Sym.getFlags();
+    if (BitcodeFile::shouldSkip(Flags))
       continue;
-    if (Sym.getFlags() & BasicSymbolRef::SF_Undefined)
+    if (Flags & BasicSymbolRef::SF_Undefined)
       continue;
     SmallString<64> Name;
     raw_svector_ostream OS(Name);
     Sym.printName(OS);
     V.push_back(Saver.save(StringRef(Name)));
   }
   return V;
 }
if (Endian == ELFDATA2LSB)
       return getElfSymbols<ELF32LE>();
     return getElfSymbols<ELF32BE>();
   }
   if (Endian == ELFDATA2LSB)
     return getElfSymbols<ELF64LE>();
   return getElfSymbols<ELF64BE>();
 }
 
+template void ArchiveFile::parse<ELF32LE>();
+template void ArchiveFile::parse<ELF32BE>();
+template void ArchiveFile::parse<ELF64LE>();
+template void ArchiveFile::parse<ELF64BE>();
+
+template void
+BitcodeFile::parse<ELF32LE>(llvm::DenseSet<StringRef> &ComdatGroups);
+template void
+BitcodeFile::parse<ELF32BE>(llvm::DenseSet<StringRef> &ComdatGroups);
+template void
+BitcodeFile::parse<ELF64LE>(llvm::DenseSet<StringRef> &ComdatGroups);
+template void
+BitcodeFile::parse<ELF64BE>(llvm::DenseSet<StringRef> &ComdatGroups);
+
+template void LazyObjectFile::parse<ELF32LE>();
+template void LazyObjectFile::parse<ELF32BE>();
+template void LazyObjectFile::parse<ELF64LE>();
+template void LazyObjectFile::parse<ELF64BE>();
+
 template class elf::ELFFileBase<ELF32LE>;
 template class elf::ELFFileBase<ELF32BE>;
 template class elf::ELFFileBase<ELF64LE>;
 template class elf::ELFFileBase<ELF64BE>;
 
 template class elf::ObjectFile<ELF32LE>;
 template class elf::ObjectFile<ELF32BE>;
 template class elf::ObjectFile<ELF64LE>;
 template class elf::ObjectFile<ELF64BE>;
 
 template class elf::SharedFile<ELF32LE>;
 template class elf::SharedFile<ELF32BE>;
 template class elf::SharedFile<ELF64LE>;
 template class elf::SharedFile<ELF64BE>;

lld/trunk/ELF/LTO.cpp

static void runLTOPasses(Module &M, TargetMachine &TM) {
   PMB.populateLTOPassManager(LtoPasses);
   LtoPasses.run(M);
 
   if (Config->SaveTemps)
     saveBCFile(M, ".lto.opt.bc");
 }
 
 static bool shouldInternalize(const SmallPtrSet<GlobalValue *, 8> &Used,
-                              SymbolBody &B, GlobalValue *GV) {
-  if (B.Backref->IsUsedInRegularObj)
+                              Symbol *S, GlobalValue *GV) {
+  if (S->IsUsedInRegularObj)
     return false;
 
   if (Used.count(GV))
     return false;
 
-  return !B.Backref->includeInDynsym();
+  return !S->includeInDynsym();
 }
 
 BitcodeCompiler::BitcodeCompiler()
     : Combined(new llvm::Module("ld-temp.o", Driver->Context)),
       Mover(*Combined) {}
 
 void BitcodeCompiler::add(BitcodeFile &F) {
   std::unique_ptr<IRObjectFile> Obj = std::move(F.Obj);
   std::vector<GlobalValue *> Keep;
   unsigned BodyIndex = 0;
-  ArrayRef<SymbolBody *> Bodies = F.getSymbols();
+  ArrayRef<Symbol *> Syms = F.getSymbols();
 
   Module &M = Obj->getModule();
   if (M.getDataLayoutStr().empty())
     fatal("invalid bitcode file: " + F.getName() + " has no datalayout");
 
   // If a symbol appears in @llvm.used, the linker is required
   // to treat the symbol as there is a reference to the symbol
   // that it cannot see. Therefore, we can't internalize.
   SmallPtrSet<GlobalValue *, 8> Used;
   collectUsedGlobalVariables(M, Used, /* CompilerUsed */ false);
 
+  // This function is called if we know that the combined LTO object will
+  // provide a definition of a symbol. It undefines the symbol so that the
+  // definition in the combined LTO object will replace it when parsed.
+  auto Undefine = [](Symbol *S) {
+    replaceBody<Undefined>(S, S->body()->getName(), STV_DEFAULT, 0);
+  };
+
   for (const BasicSymbolRef &Sym : Obj->symbols()) {
+    uint32_t Flags = Sym.getFlags();
     GlobalValue *GV = Obj->getSymbolGV(Sym.getRawDataRefImpl());
-    // Ignore module asm symbols.
-    if (!GV)
-      continue;
-    if (GV->hasAppendingLinkage()) {
+    if (GV && GV->hasAppendingLinkage())
       Keep.push_back(GV);
+    if (BitcodeFile::shouldSkip(Flags))
       continue;
-    }
-    if (BitcodeFile::shouldSkip(Sym))
+    Symbol *S = Syms[BodyIndex++];
+    if (Flags & BasicSymbolRef::SF_Undefined)
+      continue;
+    if (!GV) {
+      // Module asm symbol.
+      Undefine(S);
       continue;
-    SymbolBody *B = Bodies[BodyIndex++];
-    if (!B || &B->repl() != B || !isa<DefinedBitcode>(B))
+    }
+    auto *B = dyn_cast<DefinedBitcode>(S->body());
+    if (!B || B->File != &F)
       continue;
     switch (GV->getLinkage()) {
     default:
       break;
     case llvm::GlobalValue::LinkOnceAnyLinkage:
       GV->setLinkage(GlobalValue::WeakAnyLinkage);
       break;
     case llvm::GlobalValue::LinkOnceODRLinkage:
       GV->setLinkage(GlobalValue::WeakODRLinkage);
       break;
     }
 
     // We collect the set of symbols we want to internalize here
     // and change the linkage after the IRMover executed, i.e. after
     // we imported the symbols and satisfied undefined references
     // to it. We can't just change linkage here because otherwise
     // the IRMover will just rename the symbol.
-    if (shouldInternalize(Used, *B, GV))
+    if (shouldInternalize(Used, S, GV))
       InternalizedSyms.insert(GV->getName());
+    else
+      Undefine(S);
 
     Keep.push_back(GV);
   }
 
   Mover.move(Obj->takeModule(), Keep,
              [](GlobalValue &, IRMover::ValueAdder) {});
 }
 

lld/trunk/ELF/MarkLive.cpp

auto Enqueue = [&](ResolvedReloc<ELFT> R) {
     }
     if (R.Sec->Live)
       return;
     R.Sec->Live = true;
     if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(R.Sec))
       Q.push_back(S);
   };
 
-  auto MarkSymbol = [&](SymbolBody *Sym) {
-    if (Sym)
-      if (auto *D = dyn_cast<DefinedRegular<ELFT>>(Sym))
-        Enqueue({D->Section, D->Value});
+  auto MarkSymbol = [&](const SymbolBody *Sym) {
+    if (auto *D = dyn_cast_or_null<DefinedRegular<ELFT>>(Sym))
   };
 
   // Add GC root symbols.
   if (Config->EntrySym)
-    MarkSymbol(Config->EntrySym->Body);
+    MarkSymbol(Config->EntrySym->body());
   MarkSymbol(Symtab->find(Config->Init));
   MarkSymbol(Symtab->find(Config->Fini));
   for (StringRef S : Config->Undefined)
     MarkSymbol(Symtab->find(S));
 
   // Preserve externally-visible symbols if the symbols defined by this
   // file can interrupt other ELF file's symbols at runtime.
   for (const Symbol *S : Symtab->getSymbols())
     if (S->includeInDynsym())
-      MarkSymbol(S->Body);
+      MarkSymbol(S->body());
 
   // Preserve special sections and those which are specified in linker
   // script KEEP command.
   for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab->getObjectFiles())
     for (InputSectionBase<ELFT> *Sec : F->getSections())
       if (Sec && Sec != &InputSection<ELFT>::Discarded)
         if (isReserved(Sec) || Script<ELFT>::X->shouldKeep(Sec))
           Enqueue({Sec, 0});

lld/trunk/ELF/OutputSections.cpp

if (!Sym.isPreemptible()) {
       return;
     }
   }
   Sym.GotIndex = Entries.size();
   Entries.push_back(&Sym);
 }
 
 template <class ELFT> bool GotSection<ELFT>::addDynTlsEntry(SymbolBody &Sym) {
-  if (Sym.hasGlobalDynIndex())
+  if (Sym.symbol()->GlobalDynIndex != -1U)
     return false;
-  Sym.GlobalDynIndex = Entries.size();
+  Sym.symbol()->GlobalDynIndex = Entries.size();
   // Global Dynamic TLS entries take two GOT slots.
   Entries.push_back(&Sym);
   Entries.push_back(nullptr);
   return true;
 }
 
 // Reserves TLS entries for a TLS module ID and a TLS block offset.
 // In total it takes two GOT slots.
GotSection<ELFT>::getMipsLocalEntryOffset(uintX_t EntryValue) {
   auto P = MipsLocalGotPos.insert(std::make_pair(EntryValue, NewIndex));
   assert(!P.second || MipsLocalGotPos.size() <= MipsLocalEntries);
   return P.first->second * sizeof(uintX_t) - MipsGPOffset;
 }
 
 template <class ELFT>
 typename GotSection<ELFT>::uintX_t
 GotSection<ELFT>::getGlobalDynAddr(const SymbolBody &B) const {
-  return this->getVA() + B.GlobalDynIndex * sizeof(uintX_t);
+  return this->getVA() + B.symbol()->GlobalDynIndex * sizeof(uintX_t);
 }
 
 template <class ELFT>
 typename GotSection<ELFT>::uintX_t
 GotSection<ELFT>::getGlobalDynOffset(const SymbolBody &B) const {
-  return B.GlobalDynIndex * sizeof(uintX_t);
+  return B.symbol()->GlobalDynIndex * sizeof(uintX_t);
 }
 
 template <class ELFT>
 const SymbolBody *GotSection<ELFT>::getMipsFirstGlobalEntry() const {
   return Entries.empty() ? nullptr : Entries.front();
 }
 
 template <class ELFT>
static bool sortMipsSymbols(const std::pair<SymbolBody *, unsigned> &L,
   bool LIsInLocalGot = !L.first->isInGot() || !L.first->isPreemptible();
   bool RIsInLocalGot = !R.first->isInGot() || !R.first->isPreemptible();
   if (LIsInLocalGot || RIsInLocalGot)
     return !RIsInLocalGot;
   return L.first->GotIndex < R.first->GotIndex;
 }
 
 static uint8_t getSymbolBinding(SymbolBody *Body) {
-  Symbol *S = Body->Backref;
+  Symbol *S = Body->symbol();
   uint8_t Visibility = S->Visibility;
   if (Visibility != STV_DEFAULT && Visibility != STV_PROTECTED)
     return STB_LOCAL;
   if (Config->NoGnuUnique && S->Binding == STB_GNU_UNIQUE)
     return STB_GLOBAL;
   return S->Binding;
 }
 
for (const std::pair<SymbolBody *, size_t> &P : Symbols) {
     size_t StrOff = P.second;
 
     uint8_t Type = Body->Type;
     uintX_t Size = Body->getSize<ELFT>();
 
     ESym->setBindingAndType(getSymbolBinding(Body), Type);
     ESym->st_size = Size;
     ESym->st_name = StrOff;
-    ESym->setVisibility(Body->Backref->Visibility);
+    ESym->setVisibility(Body->symbol()->Visibility);
     ESym->st_value = Body->getVA<ELFT>();
 
     if (const OutputSectionBase<ELFT> *OutSec = getOutputSection(Body))
       ESym->st_shndx = OutSec->SectionIndex;
     else if (isa<DefinedRegular<ELFT>>(Body))
       ESym->st_shndx = SHN_ABS;
 
     // On MIPS we need to mark symbol which has a PLT entry and requires pointer

lld/trunk/ELF/SymbolTable.h

 // undefined, or lazy symbols (the last one is symbols in archive
 // files whose archive members are not yet loaded).
 //
 // We put all symbols of all files to a SymbolTable, and the
 // SymbolTable selects the "best" symbols if there are name
 // conflicts. For example, obviously, a defined symbol is better than
 // an undefined symbol. Or, if there's a conflict between a lazy and a
 // undefined, it'll read an archive member to read a real definition
-// to replace the lazy symbol. The logic is implemented in resolve().
+// to replace the lazy symbol. The logic is implemented in the
+// add*() functions, which are called by input files as they are parsed. There
+// is one add* function per symbol type.
 template <class ELFT> class SymbolTable {
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::uint uintX_t;
 
 public:
   void addFile(std::unique_ptr<InputFile> File);
   void addCombinedLtoObject();
 
   llvm::ArrayRef<Symbol *> getSymbols() const { return SymVector; }
 
   const std::vector<std::unique_ptr<ObjectFile<ELFT>>> &getObjectFiles() const {
     return ObjectFiles;
   }
 
   const std::vector<std::unique_ptr<SharedFile<ELFT>>> &getSharedFiles() const {
     return SharedFiles;
   }
 
-  SymbolBody *addUndefined(StringRef Name);
   DefinedRegular<ELFT> *addAbsolute(StringRef Name,
                                     uint8_t Visibility = llvm::ELF::STV_HIDDEN);
-  SymbolBody *addSynthetic(StringRef Name, OutputSectionBase<ELFT> &Section,
-                           uintX_t Value);
   DefinedRegular<ELFT> *addIgnored(StringRef Name,
                                    uint8_t Visibility = llvm::ELF::STV_HIDDEN);
 
+  Symbol *addUndefined(StringRef Name);
+  Symbol *addUndefined(StringRef Name, uint8_t Binding, uint8_t StOther,
+                       uint8_t Type, InputFile *File);
+
+  Symbol *addRegular(StringRef Name, const Elf_Sym &Sym,
+                     InputSectionBase<ELFT> *Section);
+  Symbol *addRegular(StringRef Name, uint8_t Binding, uint8_t StOther);
+  Symbol *addSynthetic(StringRef N, OutputSectionBase<ELFT> &Section,
+                       uintX_t Value);
+  void addShared(SharedFile<ELFT> *F, StringRef Name, const Elf_Sym &Sym,
+                 const typename ELFT::Verdef *Verdef);
+
+  void addLazyArchive(ArchiveFile *F, const llvm::object::Archive::Symbol S);
+  void addLazyObject(StringRef Name, MemoryBufferRef MBRef);
+  Symbol *addBitcode(StringRef Name, bool IsWeak, uint8_t StOther, uint8_t Type,
+                     bool CanOmitFromDynSym, BitcodeFile *File);
+
+  Symbol *addCommon(StringRef N, uint64_t Size, uint64_t Alignment,
+                    uint8_t Binding, uint8_t StOther, uint8_t Type,
+                    InputFile *File);
+
   void scanUndefinedFlags();
   void scanShlibUndefined();
   void scanDynamicList();
   void scanVersionScript();
   SymbolBody *find(StringRef Name);
   void wrap(StringRef Name);
   InputFile *findFile(SymbolBody *B);
 
 private:
-  Symbol *insert(SymbolBody *New);
-  void addLazy(Lazy *New);
-  void addMemberFile(SymbolBody *Undef, Lazy *L);
-  void resolve(SymbolBody *Body);
-  std::string conflictMsg(SymbolBody *Old, SymbolBody *New);
+  std::pair<Symbol *, bool> insert(StringRef Name);
+  std::pair<Symbol *, bool> insert(StringRef Name, uint8_t Type,
+                                   uint8_t Visibility, bool CanOmitFromDynSym,
+                                   bool IsUsedInRegularObj, InputFile *File);
+
+  std::string conflictMsg(SymbolBody *Existing, InputFile *NewFile);
+  void reportDuplicate(SymbolBody *Existing, InputFile *NewFile);
 
   // The order the global symbols are in is not defined. We can use an arbitrary
   // order, but it has to be reproducible. That is true even when cross linking.
   // The default hashing of StringRef produces different results on 32 and 64
   // bit systems so we use a map to a vector. That is arbitrary, deterministic
   // but a bit inefficient.
   // FIXME: Experiment with passing in a custom hashing or sorting the symbols
   // once symbol resolution is finished.
private:
   std::vector<std::unique_ptr<BitcodeFile>> BitcodeFiles;
 
   // Set of .so files to not link the same shared object file more than once.
   llvm::DenseSet<StringRef> SoNames;
 
   std::unique_ptr<BitcodeCompiler> Lto;
 };
 
+template <class ELFT> struct Symtab { static SymbolTable<ELFT> *X; };
+template <class ELFT> SymbolTable<ELFT> *Symtab<ELFT>::X;
+
 } // namespace elf
 } // namespace lld
 
 #endif

lld/trunk/ELF/SymbolTable.cpp

 void SymbolTable<ELFT>::addFile(std::unique_ptr<InputFile> File) {
   InputFile *FileP = File.get();
   if (!isCompatible<ELFT>(FileP))
     return;
 
   // .a file
   if (auto *F = dyn_cast<ArchiveFile>(FileP)) {
     ArchiveFiles.emplace_back(cast<ArchiveFile>(File.release()));
-    F->parse();
-    for (Lazy &Sym : F->getLazySymbols())
-      addLazy(&Sym);
+    F->parse<ELFT>();
     return;
   }
 
   // Lazy object file
   if (auto *F = dyn_cast<LazyObjectFile>(FileP)) {
     LazyObjectFiles.emplace_back(cast<LazyObjectFile>(File.release()));
-    F->parse();
-    for (Lazy &Sym : F->getLazySymbols())
-      addLazy(&Sym);
+    F->parse<ELFT>();
     return;
   }
 
   if (Config->Trace)
     llvm::outs() << getFilename(FileP) << "\n";
 
   // .so file
   if (auto *F = dyn_cast<SharedFile<ELFT>>(FileP)) {
     // DSOs are uniquified not by filename but by soname.
     F->parseSoName();
     if (!SoNames.insert(F->getSoName()).second)
       return;
 
     SharedFiles.emplace_back(cast<SharedFile<ELFT>>(File.release()));
     F->parseRest();
-    for (SharedSymbol<ELFT> &B : F->getSharedSymbols())
-      resolve(&B);
     return;
   }
 
   // LLVM bitcode file
   if (auto *F = dyn_cast<BitcodeFile>(FileP)) {
     BitcodeFiles.emplace_back(cast<BitcodeFile>(File.release()));
-    F->parse(ComdatGroups);
-    for (SymbolBody *B : F->getSymbols())
-      if (B)
-        resolve(B);
+    F->parse<ELFT>(ComdatGroups);
     return;
   }
 
   // Regular object file
   auto *F = cast<ObjectFile<ELFT>>(FileP);
   ObjectFiles.emplace_back(cast<ObjectFile<ELFT>>(File.release()));
   F->parse(ComdatGroups);
-  for (SymbolBody *B : F->getNonLocalSymbols())
-    resolve(B);
 }
 
 // This function is where all the optimizations of link-time
 // optimization happens. When LTO is in use, some input files are
 // not in native object file format but in the LLVM bitcode format.
 // This function compiles bitcode files into a few big native files
 // using LLVM functions and replaces bitcode symbols with the results.
 // Because all bitcode files that consist of a program are passed
template <class ELFT> void SymbolTable<ELFT>::addCombinedLtoObject() {
   std::vector<std::unique_ptr<InputFile>> IFs = Lto->compile();
 
   // Replace bitcode symbols.
   for (auto &IF : IFs) {
     ObjectFile<ELFT> *Obj = cast<ObjectFile<ELFT>>(IF.release());
 
     llvm::DenseSet<StringRef> DummyGroups;
     Obj->parse(DummyGroups);
-    for (SymbolBody *Body : Obj->getNonLocalSymbols()) {
-      Symbol *Sym = insert(Body);
-      if (!Sym->Body->isUndefined() && Body->isUndefined())
-        continue;
-      Sym->Body = Body;
-    }
     ObjectFiles.emplace_back(Obj);
   }
 }
 
-// Add an undefined symbol.
-template <class ELFT>
-SymbolBody *SymbolTable<ELFT>::addUndefined(StringRef Name) {
-  auto *Sym = new (Alloc) Undefined(Name, STB_GLOBAL, STV_DEFAULT, /*Type*/ 0,
-                                    /*IsBitcode*/ false);
-  resolve(Sym);
-  return Sym;
-}
-
 template <class ELFT>
 DefinedRegular<ELFT> *SymbolTable<ELFT>::addAbsolute(StringRef Name,
                                                      uint8_t Visibility) {
-  // Pass nullptr because absolute symbols have no corresponding input sections.
-  auto *Sym = new (Alloc) DefinedRegular<ELFT>(Name, STB_GLOBAL, Visibility);
-  resolve(Sym);
-  return Sym;
-}
-
-template <class ELFT>
-SymbolBody *SymbolTable<ELFT>::addSynthetic(StringRef Name,
-                                            OutputSectionBase<ELFT> &Sec,
-                                            uintX_t Val) {
-  auto *Sym = new (Alloc) DefinedSynthetic<ELFT>(Name, Val, Sec);
-  resolve(Sym);
-  return Sym;
+  return cast<DefinedRegular<ELFT>>(
+      addRegular(Name, STB_GLOBAL, Visibility)->body());
 }
 
 // Add Name as an "ignored" symbol. An ignored symbol is a regular
 // linker-synthesized defined symbol, but is only defined if needed.
 template <class ELFT>
 DefinedRegular<ELFT> *SymbolTable<ELFT>::addIgnored(StringRef Name,
                                                     uint8_t Visibility) {
   if (!find(Name))
     return nullptr;
   return addAbsolute(Name, Visibility);
 }
 
 // Rename SYM as __wrap_SYM. The original symbol is preserved as __real_SYM.
 // Used to implement --wrap.
 template <class ELFT> void SymbolTable<ELFT>::wrap(StringRef Name) {
   SymbolBody *B = find(Name);
   if (!B)
     return;
   StringSaver Saver(Alloc);
-  Symbol *Sym = B->Backref;
-  Symbol *Real = addUndefined(Saver.save("__real_" + Name))->Backref;
-  Symbol *Wrap = addUndefined(Saver.save("__wrap_" + Name))->Backref;
-  Real->Body = Sym->Body;
-  Sym->Body = Wrap->Body;
+  Symbol *Sym = B->symbol();
+  Symbol *Real = addUndefined(Saver.save("__real_" + Name));
+  Symbol *Wrap = addUndefined(Saver.save("__wrap_" + Name));
+  // We rename symbols by replacing the old symbol's SymbolBody with the new
+  // symbol's SymbolBody. This causes all SymbolBody pointers referring to the
+  // old symbol to instead refer to the new symbol.
+  memcpy(Real->Body.buffer, Sym->Body.buffer, sizeof(Sym->Body));
+  memcpy(Sym->Body.buffer, Wrap->Body.buffer, sizeof(Wrap->Body));
 }
 
 // Returns a file from which symbol B was created.
 // If B does not belong to any file, returns a nullptr.
 // This function is slow, but it's okay as it is used only for error messages.
 template <class ELFT> InputFile *SymbolTable<ELFT>::findFile(SymbolBody *B) {
+  // If this symbol has a definition, follow pointers in the symbol to its
+  // defining file.
+  if (auto *R = dyn_cast<DefinedRegular<ELFT>>(B))
+    if (auto *S = R->Section)
+      return S->getFile();
+  if (auto *SS = dyn_cast<SharedSymbol<ELFT>>(B))
+    return SS->File;
+  if (auto *BC = dyn_cast<DefinedBitcode>(B))
+    return BC->File;
+  // If not, we might be able to find it by searching symbol tables of files.
+  // This code is generally only used for undefined symbols. Note that we can't
+  // rely exclusively on a file search because we may find what was originally
+  // an undefined symbol that was later replaced with a defined symbol, and we
+  // want to return the file that defined the symbol.
   for (const std::unique_ptr<ObjectFile<ELFT>> &F : ObjectFiles) {
     ArrayRef<SymbolBody *> Syms = F->getSymbols();
     if (std::find(Syms.begin(), Syms.end(), B) != Syms.end())
       return F.get();
   }
   for (const std::unique_ptr<BitcodeFile> &F : BitcodeFiles) {
-    ArrayRef<SymbolBody *> Syms = F->getSymbols();
-    if (std::find(Syms.begin(), Syms.end(), B) != Syms.end())
+    ArrayRef<Symbol *> Syms = F->getSymbols();
+    if (std::find(Syms.begin(), Syms.end(), B->symbol()) != Syms.end())
       return F.get();
   }
   return nullptr;
 }
 
-// Construct a string in the form of "Sym in File1 and File2".
-// Used to construct an error message.
-template <class ELFT>
-std::string SymbolTable<ELFT>::conflictMsg(SymbolBody *Old, SymbolBody *New) {
-  InputFile *F1 = findFile(Old);
-  InputFile *F2 = findFile(New);
-  StringRef Sym = Old->getName();
-  return demangle(Sym) + " in " + getFilename(F1) + " and " + getFilename(F2);
-}
-
-// This function resolves conflicts if there's an existing symbol with
-// the same name. Decisions are made based on symbol type.
-template <class ELFT> void SymbolTable<ELFT>::resolve(SymbolBody *New) {
-  Symbol *Sym = insert(New);
-  if (Sym->Body == New)
-    return;
-
-  SymbolBody *Existing = Sym->Body;
-
-  if (auto *L = dyn_cast<Lazy>(Existing)) {
-    Sym->Binding = New->Binding;
-    if (New->isUndefined()) {
-      addMemberFile(New, L);
-      return;
-    }
-    // Found a definition for something also in an archive.
-    // Ignore the archive definition.
-    Sym->Body = New;
-    return;
-  }
-
-  if (New->isTls() != Existing->isTls()) {
-    error("TLS attribute mismatch for symbol: " + conflictMsg(Existing, New));
-    return;
-  }
-
-  // compare() returns -1, 0, or 1 if the lhs symbol is less preferable,
-  // equivalent (conflicting), or more preferable, respectively.
-  int Comp = Existing->compare(New);
-  if (Comp == 0) {
-    std::string S = "duplicate symbol: " + conflictMsg(Existing, New);
-    if (Config->AllowMultipleDefinition)
-      warning(S);
-    else
-      error(S);
-    return;
-  }
-  if (Comp < 0) {
-    Sym->Body = New;
-    if (!New->isShared())
-      Sym->Binding = New->Binding;
-  }
-}
-
 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);
 }
 
-static bool shouldExport(SymbolBody *B) {
-  if (Config->Shared || Config->ExportDynamic) {
-    // Export most symbols except for those that do not need to be exported.
-    return !B->CanOmitFromDynSym;
-  }
-  // Make sure we preempt DSO symbols with default visibility.
-  return B->isShared() && B->getVisibility() == STV_DEFAULT;
-}
-
 // Find an existing symbol or create and insert a new one.
-template <class ELFT> Symbol *SymbolTable<ELFT>::insert(SymbolBody *New) {
-  StringRef Name = New->getName();
+template <class ELFT>
+std::pair<Symbol *, bool> SymbolTable<ELFT>::insert(StringRef Name) {
   unsigned NumSyms = SymVector.size();
   auto P = Symtab.insert(std::make_pair(Name, NumSyms));
   Symbol *Sym;
   if (P.second) {
     Sym = new (Alloc) Symbol;
-    Sym->Body = New;
-    Sym->Binding = New->isShared() ? (uint8_t)STB_GLOBAL : New->Binding;
+    Sym->Binding = STB_WEAK;
     Sym->Visibility = STV_DEFAULT;
     Sym->IsUsedInRegularObj = false;
     Sym->ExportDynamic = false;
     Sym->VersionScriptGlobal = !Config->VersionScript;
     SymVector.push_back(Sym);
   } else {
     Sym = SymVector[P.first->second];
   }
-  New->Backref = Sym;
+  return {Sym, P.second};
+}
 
-  // Merge in the new symbol's visibility. DSO symbols do not affect visibility
-  // in the output.
-  if (!New->isShared())
-    Sym->Visibility = getMinVisibility(Sym->Visibility, New->getVisibility());
-  Sym->ExportDynamic = Sym->ExportDynamic || shouldExport(New);
-  SymbolBody::Kind K = New->kind();
-  if (K == SymbolBody::DefinedRegularKind ||
-      K == SymbolBody::DefinedCommonKind ||
-      K == SymbolBody::DefinedSyntheticKind ||
-      (K == SymbolBody::UndefinedKind && !New->IsUndefinedBitcode))
-    Sym->IsUsedInRegularObj = true;
-  return Sym;
+// Find an existing symbol or create and insert a new one, then apply the given
+// attributes.
+template <class ELFT>
+std::pair<Symbol *, bool>
+SymbolTable<ELFT>::insert(StringRef Name, uint8_t Type, uint8_t Visibility,
+                          bool CanOmitFromDynSym, bool IsUsedInRegularObj,
+                          InputFile *File) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(Name);
+
+  // Merge in the new symbol's visibility.
+  S->Visibility = getMinVisibility(S->Visibility, Visibility);
+  if (!CanOmitFromDynSym && (Config->Shared || Config->ExportDynamic))
+    S->ExportDynamic = true;
+  if (IsUsedInRegularObj)
+    S->IsUsedInRegularObj = true;
+  if (!WasInserted && ((Type == STT_TLS) != S->body()->isTls()))
+    error("TLS attribute mismatch for symbol: " +
+          conflictMsg(S->body(), File));
+
+  return {S, WasInserted};
+}
+
+// Construct a string in the form of "Sym in File1 and File2".
+// Used to construct an error message.
+template <typename ELFT>
+std::string SymbolTable<ELFT>::conflictMsg(SymbolBody *Existing,
+                                           InputFile *NewFile) {
+  StringRef Sym = Existing->getName();
+  return demangle(Sym) + " in " + getFilename(findFile(Existing)) + " and " +
+         getFilename(NewFile);
+}
+
+template <class ELFT> Symbol *SymbolTable<ELFT>::addUndefined(StringRef Name) {
+  return addUndefined(Name, STB_GLOBAL, STV_DEFAULT, /*Type*/ 0,
+                      /*File*/ nullptr);
+}
+
+template <class ELFT>
+Symbol *SymbolTable<ELFT>::addUndefined(StringRef Name, uint8_t Binding,
+                                        uint8_t StOther, uint8_t Type,
+                                        InputFile *File) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) =
+      insert(Name, Type, StOther & 3, /*CanOmitFromDynSym*/ false,
+             /*IsUsedInRegularObj*/ !File || !isa<BitcodeFile>(File), File);
+  if (WasInserted) {
+    S->Binding = Binding;
+    replaceBody<Undefined>(S, Name, StOther, Type);
+    return S;
+  }
+  if (Binding != STB_WEAK &&
+      (S->body()->isShared() || S->body()->isLazy()))
+    S->Binding = Binding;
+  if (auto *L = dyn_cast<Lazy>(S->body())) {
+    // An undefined weak will not fetch archive members, but we have to remember
+    // its type. See also comment in addLazyArchive.
+    if (S->isWeak())
+      L->Type = Type;
+    else if (auto F = L->getFile())
+      addFile(std::move(F));
+  }
+  return S;
+}
+
+// We have a new defined symbol with the specified binding. Return 1 if the new
+// symbol should win, -1 if the new symbol should lose, or 0 if both symbols are
+// strong defined symbols.
+static int compareDefined(Symbol *S, bool WasInserted, uint8_t Binding) {
+  if (WasInserted)
+    return 1;
+  SymbolBody *Body = S->body();
+  if (Body->isLazy() || Body->isUndefined() || Body->isShared())
+    return 1;
+  if (Binding == STB_WEAK)
+    return -1;
+  if (S->isWeak())
+    return 1;
+  return 0;
+}
+
+// We have a new non-common defined symbol with the specified binding. Return 1
+// if the new symbol should win, -1 if the new symbol should lose, or 0 if there
+// is a conflict. If the new symbol wins, also update the binding.
+static int compareDefinedNonCommon(Symbol *S, bool WasInserted, uint8_t Binding) {
+  if (int Cmp = compareDefined(S, WasInserted, Binding)) {
+    if (Cmp > 0)
+      S->Binding = Binding;
+    return Cmp;
+  }
+  if (isa<DefinedCommon>(S->body())) {
+    // Non-common symbols take precedence over common symbols.
+    if (Config->WarnCommon)
+      warning("common " + S->body()->getName() + " is overridden");
+    return 1;
+  }
+  return 0;
+}
+
+template <class ELFT>
+Symbol *SymbolTable<ELFT>::addCommon(StringRef N, uint64_t Size,
+                                     uint64_t Alignment, uint8_t Binding,
+                                     uint8_t StOther, uint8_t Type,
+                                     InputFile *File) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) =
+      insert(N, Type, StOther & 3, /*CanOmitFromDynSym*/ false,
+             /*IsUsedInRegularObj*/ true, File);
+  int Cmp = compareDefined(S, WasInserted, Binding);
+  if (Cmp > 0) {
+    S->Binding = Binding;
+    replaceBody<DefinedCommon>(S, N, Size, Alignment, StOther, Type);
+  } else if (Cmp == 0) {
+    auto *C = dyn_cast<DefinedCommon>(S->body());
+    if (!C) {
+      // Non-common symbols take precedence over common symbols.
+      if (Config->WarnCommon)
+        warning("common " + S->body()->getName() + " is overridden");
+      return S;
+    }
+
+    if (Config->WarnCommon)
+      warning("multiple common of " + S->body()->getName());
+
+    C->Size = std::max(C->Size, Size);
+    C->Alignment = std::max(C->Alignment, Alignment);
+  }
+  return S;
+}
+
+template <class ELFT>
+void SymbolTable<ELFT>::reportDuplicate(SymbolBody *Existing,
+                                        InputFile *NewFile) {
+  std::string Msg = "duplicate symbol: " + conflictMsg(Existing, NewFile);
+  if (Config->AllowMultipleDefinition)
+    warning(Msg);
+  else
+    error(Msg);
+}
+
+template <typename ELFT>
+Symbol *SymbolTable<ELFT>::addRegular(StringRef Name, const Elf_Sym &Sym,
+                                      InputSectionBase<ELFT> *Section) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) =
+      insert(Name, Sym.getType(), Sym.getVisibility(),
+             /*CanOmitFromDynSym*/ false, /*IsUsedInRegularObj*/ true,
+             Section ? Section->getFile() : nullptr);
+  int Cmp = compareDefinedNonCommon(S, WasInserted, Sym.getBinding());
+  if (Cmp > 0)
+    replaceBody<DefinedRegular<ELFT>>(S, Name, Sym, Section);
+  else if (Cmp == 0)
+    reportDuplicate(S->body(), Section->getFile());
+  return S;
+}
+
+template <typename ELFT>
+Symbol *SymbolTable<ELFT>::addRegular(StringRef Name, uint8_t Binding,
+                                      uint8_t StOther) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) =
+      insert(Name, STT_NOTYPE, StOther & 3, /*CanOmitFromDynSym*/ false,
+             /*IsUsedInRegularObj*/ true, nullptr);
+  int Cmp = compareDefinedNonCommon(S, WasInserted, Binding);
+  if (Cmp > 0)
+    replaceBody<DefinedRegular<ELFT>>(S, Name, StOther);
+  else if (Cmp == 0)
+    reportDuplicate(S->body(), nullptr);
+  return S;
+}
+
+template <typename ELFT>
+Symbol *SymbolTable<ELFT>::addSynthetic(StringRef N,
+                                        OutputSectionBase<ELFT> &Section,
+                                        uintX_t Value) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) =
+      insert(N, STT_NOTYPE, STV_HIDDEN, /*CanOmitFromDynSym*/ false,
+             /*IsUsedInRegularObj*/ true, nullptr);
+  int Cmp = compareDefinedNonCommon(S, WasInserted, STB_GLOBAL);
+  if (Cmp > 0)
+    replaceBody<DefinedSynthetic<ELFT>>(S, N, Value, Section);
+  else if (Cmp == 0)
+    reportDuplicate(S->body(), nullptr);
+  return S;
+}
+
+template <typename ELFT>
+void SymbolTable<ELFT>::addShared(SharedFile<ELFT> *F, StringRef Name,
+                                  const Elf_Sym &Sym,
+                                  const typename ELFT::Verdef *Verdef) {
+  // DSO symbols do not affect visibility in the output, so we pass STV_DEFAULT
+  // as the visibility, which will leave the visibility in the symbol table
+  // unchanged.
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) =
+      insert(Name, Sym.getType(), STV_DEFAULT, /*CanOmitFromDynSym*/ true,
+             /*IsUsedInRegularObj*/ false, F);
+  // Make sure we preempt DSO symbols with default visibility.
+  if (Sym.getVisibility() == STV_DEFAULT)
+    S->ExportDynamic = true;
+  if (WasInserted || isa<Undefined>(S->body()))
+    replaceBody<SharedSymbol<ELFT>>(S, F, Name, Sym, Verdef);
+}
+
+template <class ELFT>
+Symbol *SymbolTable<ELFT>::addBitcode(StringRef Name, bool IsWeak,
+                                      uint8_t StOther, uint8_t Type,
+                                      bool CanOmitFromDynSym, BitcodeFile *F) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(Name, Type, StOther & 3, CanOmitFromDynSym,
+                                    /*IsUsedInRegularObj*/ false, F);
+  int Cmp =
+      compareDefinedNonCommon(S, WasInserted, IsWeak ? STB_WEAK : STB_GLOBAL);
+  if (Cmp > 0)
+    replaceBody<DefinedBitcode>(S, Name, StOther, Type, F);
+  else if (Cmp == 0)
+    reportDuplicate(S->body(), F);
+  return S;
 }
 
 template <class ELFT> SymbolBody *SymbolTable<ELFT>::find(StringRef Name) {
   auto It = Symtab.find(Name);
   if (It == Symtab.end())
     return nullptr;
-  return SymVector[It->second]->Body;
+  return SymVector[It->second]->body();
 }
 
-template <class ELFT> void SymbolTable<ELFT>::addLazy(Lazy *L) {
-  Symbol *Sym = insert(L);
-  SymbolBody *Cur = Sym->Body;
-  if (Cur == L)
-    return;
-  if (Cur->isUndefined()) {
-    Sym->Body = L;
-    addMemberFile(Cur, L);
-  }
+template <class ELFT>
+void SymbolTable<ELFT>::addLazyArchive(
+    ArchiveFile *F, const llvm::object::Archive::Symbol Sym) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(Sym.getName());
+  if (WasInserted) {
+    replaceBody<LazyArchive>(S, F, Sym, STT_NOTYPE);
+    return;
+  }
+  if (!S->body()->isUndefined())
+    return;
+
+  // Weak undefined symbols should not fetch members from archives. If we were
+  // to keep old symbol we would not know that an archive member was available
+  // if a strong undefined symbol shows up afterwards in the link. If a strong
+  // undefined symbol never shows up, this lazy symbol will get to the end of
+  // the link and must be treated as the weak undefined one. We already marked
+  // this symbol as used when we added it to the symbol table, but we also need
+  // to preserve its type. FIXME: Move the Type field to Symbol.
+  if (S->isWeak()) {
+    replaceBody<LazyArchive>(S, F, Sym, S->body()->Type);
+    return;
+  }
+  MemoryBufferRef MBRef = F->getMember(&Sym);
+  if (!MBRef.getBuffer().empty())
+    addFile(createObjectFile(MBRef, F->getName()));
 }
 
 template <class ELFT>
-void SymbolTable<ELFT>::addMemberFile(SymbolBody *Undef, Lazy *L) {
-  // Weak undefined symbols should not fetch members from archives.
-  // If we were to keep old symbol we would not know that an archive member was
-  // available if a strong undefined symbol shows up afterwards in the link.
-  // If a strong undefined symbol never shows up, this lazy symbol will
-  // get to the end of the link and must be treated as the weak undefined one.
-  // We already marked this symbol as used when we added it to the symbol table,
-  // but we also need to preserve its binding and type.
-  if (Undef->isWeak()) {
-    // FIXME: Consider moving these members to Symbol.
-    L->Type = Undef->Type;
+void SymbolTable<ELFT>::addLazyObject(StringRef Name, MemoryBufferRef MBRef) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(Name);
+  if (WasInserted) {
+    replaceBody<LazyObject>(S, Name, MBRef, STT_NOTYPE);
     return;
   }
+  if (!S->body()->isUndefined())
+    return;
 
-  // Fetch a member file that has the definition for L.
-  // getMember returns nullptr if the member was already read from the library.
-  if (std::unique_ptr<InputFile> File = L->getFile())
-    addFile(std::move(File));
+  // See comment for addLazyArchive above.
+  if (S->isWeak())
+    replaceBody<LazyObject>(S, Name, MBRef, S->body()->Type);
+  else
+    addFile(createObjectFile(MBRef));
 }
 
 // Process undefined (-u) flags by loading lazy symbols named by those flags.
-template <class ELFT>
-void SymbolTable<ELFT>::scanUndefinedFlags() {
+template <class ELFT> void SymbolTable<ELFT>::scanUndefinedFlags() {
   for (StringRef S : Config->Undefined)
-    if (SymbolBody *Sym = find(S))
-      if (auto *L = dyn_cast<Lazy>(Sym))
-        if (std::unique_ptr<InputFile> File = L->getFile())
-          addFile(std::move(File));
+    if (auto *L = dyn_cast_or_null<Lazy>(find(S)))
 }
 
 // This function takes care of the case in which shared libraries depend on
 // the user program (not the other way, which is usual). Shared libraries
 // may have undefined symbols, expecting that the user program provides
 // the definitions for them. An example is BSD's __progname symbol.
 // We need to put such symbols to the main program's .dynsym so that
 // shared libraries can find them.
 // Except this, we ignore undefined symbols in DSOs.
 template <class ELFT> void SymbolTable<ELFT>::scanShlibUndefined() {
   for (std::unique_ptr<SharedFile<ELFT>> &File : SharedFiles)
     for (StringRef U : File->getUndefinedSymbols())
       if (SymbolBody *Sym = find(U))
         if (Sym->isDefined())
-          Sym->Backref->ExportDynamic = true;
+          Sym->symbol()->ExportDynamic = true;
 }
 
 // This function process the dynamic list option by marking all the symbols
 // to be exported in the dynamic table.
 template <class ELFT> void SymbolTable<ELFT>::scanDynamicList() {
   for (StringRef S : Config->DynamicList)
     if (SymbolBody *B = find(S))
-      B->Backref->ExportDynamic = true;
+      B->symbol()->ExportDynamic = true;
 }
 
 // This function processes the --version-script option by marking all global
 // symbols with the VersionScriptGlobal flag, which acts as a filter on the
 // dynamic symbol table.
 template <class ELFT> void SymbolTable<ELFT>::scanVersionScript() {
   for (StringRef S : Config->VersionScriptGlobals)
     if (SymbolBody *B = find(S))
-      B->Backref->VersionScriptGlobal = true;
+      B->symbol()->VersionScriptGlobal = true;
 }
 
 template class elf::SymbolTable<ELF32LE>;
 template class elf::SymbolTable<ELF32BE>;
 template class elf::SymbolTable<ELF64LE>;
 template class elf::SymbolTable<ELF64BE>;

lld/trunk/ELF/Symbols.h

 #ifndef LLD_ELF_SYMBOLS_H
 #define LLD_ELF_SYMBOLS_H
 
 #include "InputSection.h"
 
 #include "lld/Core/LLVM.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Object/ELF.h"
+#include "llvm/Support/AlignOf.h"
 
 namespace lld {
 namespace elf {
 
 class ArchiveFile;
+class BitcodeFile;
 class InputFile;
 class SymbolBody;
 template <class ELFT> class ObjectFile;
 template <class ELFT> class OutputSection;
 template <class ELFT> class OutputSectionBase;
 template <class ELFT> class SharedFile;
 
 // Returns a demangled C++ symbol name. If Name is not a mangled
 // name or the system does not provide __cxa_demangle function,
 // it returns the unmodified string.
 std::string demangle(StringRef Name);
 
-// A real symbol object, SymbolBody, is usually accessed indirectly
-// through a Symbol. There's always one Symbol for each symbol name.
-// The resolver updates SymbolBody pointers as it resolves symbols.
-// Symbol also holds computed properties of symbol names.
-struct Symbol {
-  SymbolBody *Body;
-
-  // Symbol binding. This is on the Symbol to track changes during resolution.
-  // In particular:
-  // An undefined weak is still weak when it resolves to a shared library.
-  // An undefined weak will not fetch archive members, but we have to remember
-  // it is weak.
-  uint8_t Binding;
-
-  // Symbol visibility. This is the computed minimum visibility of all
-  // observed non-DSO symbols.
-  unsigned Visibility : 2;
-
-  // True if the symbol was used for linking and thus need to be added to the
-  // output file's symbol table. This is true for all symbols except for
-  // unreferenced DSO symbols and bitcode symbols that are unreferenced except
-  // by other bitcode objects.
-  unsigned IsUsedInRegularObj : 1;
-
-  // If this flag is true and the symbol has protected or default visibility, it
-  // will appear in .dynsym. This flag is set by interposable DSO symbols in
-  // executables, by most symbols in DSOs and executables built with
-  // --export-dynamic, and by dynamic lists.
-  unsigned ExportDynamic : 1;
-
-  // This flag acts as an additional filter on the dynamic symbol list. It is
-  // set if there is no version script, or if the symbol appears in the global
-  // section of the version script.
-  unsigned VersionScriptGlobal : 1;
-
-  bool includeInDynsym() const;
-
-  bool isWeak() const { return Binding == llvm::ELF::STB_WEAK; }
-};
+struct Symbol;
 
 // The base class for real symbol classes.
 class SymbolBody {
   void init();
 
 public:
   enum Kind {
     DefinedFirst,
     DefinedRegularKind = DefinedFirst,
     SharedKind,
     DefinedCommonKind,
     DefinedBitcodeKind,
     DefinedSyntheticKind,
     DefinedLast = DefinedSyntheticKind,
     UndefinedKind,
     LazyArchiveKind,
     LazyObjectKind,
   };
 
+  Symbol *symbol();
+  const Symbol *symbol() const {
+    return const_cast<SymbolBody *>(this)->symbol();
+  }
+
   Kind kind() const { return static_cast<Kind>(SymbolKind); }
 
-  bool isWeak() const { return Binding == llvm::ELF::STB_WEAK; }
   bool isUndefined() const { return SymbolKind == UndefinedKind; }
   bool isDefined() const { return SymbolKind <= DefinedLast; }
   bool isCommon() const { return SymbolKind == DefinedCommonKind; }
   bool isLazy() const {
     return SymbolKind == LazyArchiveKind || SymbolKind == LazyObjectKind;
   }
   bool isShared() const { return SymbolKind == SharedKind; }
-  bool isLocal() const { return Binding == llvm::ELF::STB_LOCAL; }
+  bool isLocal() const { return IsLocal; }
   bool isPreemptible() const;
 
   // Returns the symbol name.
   StringRef getName() const {
     assert(!isLocal());
     return StringRef(Name.S, Name.Len);
   }
   uint32_t getNameOffset() const {
     assert(isLocal());
     return NameOffset;
   }
 
   uint8_t getVisibility() const { return StOther & 0x3; }
 
   unsigned DynsymIndex = 0;
-  uint32_t GlobalDynIndex = -1;
   uint32_t GotIndex = -1;
   uint32_t GotPltIndex = -1;
   uint32_t PltIndex = -1;
   uint32_t ThunkIndex = -1;
-  bool hasGlobalDynIndex() { return GlobalDynIndex != uint32_t(-1); }
   bool isInGot() const { return GotIndex != -1U; }
   bool isInPlt() const { return PltIndex != -1U; }
   bool hasThunk() const { return ThunkIndex != -1U; }
 
   template <class ELFT>
   typename ELFT::uint getVA(typename ELFT::uint Addend = 0) const;
 
   template <class ELFT> typename ELFT::uint getGotOffset() const;
   template <class ELFT> typename ELFT::uint getGotVA() const;
   template <class ELFT> typename ELFT::uint getGotPltOffset() const;
   template <class ELFT> typename ELFT::uint getGotPltVA() const;
   template <class ELFT> typename ELFT::uint getPltVA() const;
   template <class ELFT> typename ELFT::uint getThunkVA() const;
   template <class ELFT> typename ELFT::uint getSize() const;
 
-  // A SymbolBody has a backreference to a Symbol. Originally they are
-  // doubly-linked. A backreference will never change. But the pointer
-  // in the Symbol may be mutated by the resolver. If you have a
-  // pointer P to a SymbolBody and are not sure whether the resolver
-  // has chosen the object among other objects having the same name,
-  // you can access P->Backref->Body to get the resolver's result.
-  SymbolBody &repl() { return Backref ? *Backref->Body : *this; }
-
-  // Decides which symbol should "win" in the symbol table, this or
-  // the Other. Returns 1 if this wins, -1 if the Other wins, or 0 if
-  // they are duplicate (conflicting) symbols.
-  int compare(SymbolBody *Other);
-
 protected:
-  SymbolBody(Kind K, StringRef Name, uint8_t Binding, uint8_t StOther,
-             uint8_t Type);
+  SymbolBody(Kind K, StringRef Name, uint8_t StOther, uint8_t Type);
 
   SymbolBody(Kind K, uint32_t NameOffset, uint8_t StOther, uint8_t Type);
 
   const unsigned SymbolKind : 8;
 
 public:
-  // True if this symbol can be omitted from the symbol table if nothing else
-  // requires it to be there. Right now this is only used for linkonce_odr in
-  // LTO, but we could add the feature to ELF. It would be similar to
-  // MachO's .weak_def_can_be_hidden.
-  unsigned CanOmitFromDynSym : 1;
-
   // True if the linker has to generate a copy relocation for this shared
   // symbol or if the symbol should point to its plt entry.
   unsigned NeedsCopyOrPltAddr : 1;
 
-  // True if the symbol is undefined and comes from a bitcode file. We need to
-  // keep track of this because undefined symbols only prevent internalization
-  // of bitcode symbols if they did not come from a bitcode file.
-  unsigned IsUndefinedBitcode : 1;
+  // True if this is a local symbol.
+  unsigned IsLocal : 1;
 
   // The following fields have the same meaning as the ELF symbol attributes.
   uint8_t Type;    // symbol type
-  uint8_t Binding; // symbol binding
   uint8_t StOther; // st_other field value
 
   bool isSection() const { return Type == llvm::ELF::STT_SECTION; }
   bool isTls() const { return Type == llvm::ELF::STT_TLS; }
   bool isFunc() const { return Type == llvm::ELF::STT_FUNC; }
   bool isGnuIFunc() const { return Type == llvm::ELF::STT_GNU_IFUNC; }
   bool isObject() const { return Type == llvm::ELF::STT_OBJECT; }
   bool isFile() const { return Type == llvm::ELF::STT_FILE; }
 
-  Symbol *Backref = nullptr;
-
 protected:
   struct Str {
     const char *S;
     size_t Len;
   };
   union {
     Str Name;
     uint32_t NameOffset;
   };
 };
 
 // The base class for any defined symbols.
 class Defined : public SymbolBody {
 public:
-  Defined(Kind K, StringRef Name, uint8_t Binding, uint8_t StOther,
-          uint8_t Type);
+  Defined(Kind K, StringRef Name, uint8_t StOther, uint8_t Type);
   Defined(Kind K, uint32_t NameOffset, uint8_t StOther, uint8_t Type);
   static bool classof(const SymbolBody *S) { return S->isDefined(); }
 };
 
 // The defined symbol in LLVM bitcode files.
 class DefinedBitcode : public Defined {
 public:
-  DefinedBitcode(StringRef Name, bool IsWeak, uint8_t StOther);
+  DefinedBitcode(StringRef Name, uint8_t StOther, uint8_t Type, BitcodeFile *F);
   static bool classof(const SymbolBody *S);
+
+  BitcodeFile *File;
 };
 
 class DefinedCommon : public Defined {
 public:
-  DefinedCommon(StringRef N, uint64_t Size, uint64_t Alignment, uint8_t Binding,
-                uint8_t StOther, uint8_t Type);
+  DefinedCommon(StringRef N, uint64_t Size, uint64_t Alignment, uint8_t StOther,
+                uint8_t Type);
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == SymbolBody::DefinedCommonKind;
   }
 
   // The output offset of this common symbol in the output bss. Computed by the
   // writer.
   uint64_t OffsetInBss;
 
   // The maximum alignment we have seen for this symbol.
   uint64_t Alignment;
 
   uint64_t Size;
 };
 
 // Regular defined symbols read from object file symbol tables.
 template <class ELFT> class DefinedRegular : public Defined {
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::uint uintX_t;
 
 public:
   DefinedRegular(StringRef Name, const Elf_Sym &Sym,
                  InputSectionBase<ELFT> *Section)
-      : Defined(SymbolBody::DefinedRegularKind, Name, Sym.getBinding(),
-                Sym.st_other, Sym.getType()),
+      : Defined(SymbolBody::DefinedRegularKind, Name, Sym.st_other,
+                Sym.getType()),
         Value(Sym.st_value), Size(Sym.st_size),
         Section(Section ? Section->Repl : NullInputSection) {}
 
   DefinedRegular(const Elf_Sym &Sym, InputSectionBase<ELFT> *Section)
       : Defined(SymbolBody::DefinedRegularKind, Sym.st_name, Sym.st_other,
                 Sym.getType()),
         Value(Sym.st_value), Size(Sym.st_size),
         Section(Section ? Section->Repl : NullInputSection) {
     assert(isLocal());
   }
 
-  DefinedRegular(StringRef Name, uint8_t Binding, uint8_t StOther)
-      : Defined(SymbolBody::DefinedRegularKind, Name, Binding, StOther,
+  DefinedRegular(StringRef Name, uint8_t StOther)
+      : Defined(SymbolBody::DefinedRegularKind, Name, StOther,
                 llvm::ELF::STT_NOTYPE),
         Value(0), Size(0), Section(NullInputSection) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == SymbolBody::DefinedRegularKind;
   }
 
   uintX_t Value;
public:
   static const uintX_t SectionEnd = uintX_t(-1);
 
   uintX_t Value;
   const OutputSectionBase<ELFT> &Section;
 };
 
 class Undefined : public SymbolBody {
 public:
-  Undefined(StringRef Name, uint8_t Binding, uint8_t StOther, uint8_t Type,
-            bool IsBitcode);
+  Undefined(StringRef Name, uint8_t StOther, uint8_t Type);
   Undefined(uint32_t NameOffset, uint8_t StOther, uint8_t Type);
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == UndefinedKind;
   }
 };
 
 template <class ELFT> class SharedSymbol : public Defined {
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Verdef Elf_Verdef;
   typedef typename ELFT::uint uintX_t;
 
 public:
   static bool classof(const SymbolBody *S) {
     return S->kind() == SymbolBody::SharedKind;
   }
 
   SharedSymbol(SharedFile<ELFT> *F, StringRef Name, const Elf_Sym &Sym,
                const Elf_Verdef *Verdef)
-      : Defined(SymbolBody::SharedKind, Name, Sym.getBinding(), Sym.st_other,
-                Sym.getType()),
+      : Defined(SymbolBody::SharedKind, Name, Sym.st_other, Sym.getType()),
         File(F), Sym(Sym), Verdef(Verdef) {
     // IFuncs defined in DSOs are treated as functions by the static linker.
     if (isGnuIFunc())
       Type = llvm::ELF::STT_FUNC;
   }
 
   SharedFile<ELFT> *File;
   const Elf_Sym &Sym;

 
 // This class represents a symbol defined in an archive file. It is
 // created from an archive file header, and it knows how to load an
 // object file from an archive to replace itself with a defined
 // symbol. If the resolver finds both Undefined and Lazy for
 // the same name, it will ask the Lazy to load a file.
 class Lazy : public SymbolBody {
 public:
-  Lazy(SymbolBody::Kind K, StringRef Name)
-      : SymbolBody(K, Name, llvm::ELF::STB_GLOBAL, llvm::ELF::STV_DEFAULT,
-                   /* Type */ 0) {}
+  Lazy(SymbolBody::Kind K, StringRef Name, uint8_t Type)
+      : SymbolBody(K, Name, llvm::ELF::STV_DEFAULT, Type) {}
 
   static bool classof(const SymbolBody *S) { return S->isLazy(); }
 
   // Returns an object file for this symbol, or a nullptr if the file
   // was already returned.
   std::unique_ptr<InputFile> getFile();
 };
 
 // LazyArchive symbols represents symbols in archive files.
 class LazyArchive : public Lazy {
 public:
-  LazyArchive(ArchiveFile *F, const llvm::object::Archive::Symbol S)
-      : Lazy(LazyArchiveKind, S.getName()), File(F), Sym(S) {}
+  LazyArchive(ArchiveFile *F, const llvm::object::Archive::Symbol S,
+              uint8_t Type)
+      : Lazy(LazyArchiveKind, S.getName(), Type), File(F), Sym(S) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == LazyArchiveKind;
   }
 
   std::unique_ptr<InputFile> getFile();
 
 private:
   ArchiveFile *File;
   const llvm::object::Archive::Symbol Sym;
 };
 
 // LazyObject symbols represents symbols in object files between
 // --start-lib and --end-lib options.
 class LazyObject : public Lazy {
 public:
-  LazyObject(StringRef Name, MemoryBufferRef M)
-      : Lazy(LazyObjectKind, Name), MBRef(M) {}
+  LazyObject(StringRef Name, MemoryBufferRef M, uint8_t Type)
+      : Lazy(LazyObjectKind, Name, Type), MBRef(M) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == LazyObjectKind;
   }
 
   std::unique_ptr<InputFile> getFile();
 
 private:
template <class ELFT> struct ElfSym {
   // The content for _edata and edata symbols.
   static DefinedRegular<ELFT> *Edata;
   static DefinedRegular<ELFT> *Edata2;
 
   // The content for _end and end symbols.
   static DefinedRegular<ELFT> *End;
   static DefinedRegular<ELFT> *End2;
 
-  // The content for _gp symbol for MIPS target.
-  static SymbolBody *MipsGp;
-
-  static SymbolBody *MipsLocalGp;
+  // The content for _gp_disp symbol for MIPS target.
   static SymbolBody *MipsGpDisp;
-
-  // __rel_iplt_start/__rel_iplt_end for signaling
-  // where R_[*]_IRELATIVE relocations do live.
-  static SymbolBody *RelaIpltStart;
-  static SymbolBody *RelaIpltEnd;
 };
 
 template <class ELFT> DefinedRegular<ELFT> *ElfSym<ELFT>::Etext;
 template <class ELFT> DefinedRegular<ELFT> *ElfSym<ELFT>::Etext2;
 template <class ELFT> DefinedRegular<ELFT> *ElfSym<ELFT>::Edata;
 template <class ELFT> DefinedRegular<ELFT> *ElfSym<ELFT>::Edata2;
 template <class ELFT> DefinedRegular<ELFT> *ElfSym<ELFT>::End;
 template <class ELFT> DefinedRegular<ELFT> *ElfSym<ELFT>::End2;
-template <class ELFT> SymbolBody *ElfSym<ELFT>::MipsGp;
-template <class ELFT> SymbolBody *ElfSym<ELFT>::MipsLocalGp;
 template <class ELFT> SymbolBody *ElfSym<ELFT>::MipsGpDisp;
-template <class ELFT> SymbolBody *ElfSym<ELFT>::RelaIpltStart;
-template <class ELFT> SymbolBody *ElfSym<ELFT>::RelaIpltEnd;
+
+// A real symbol object, SymbolBody, is usually stored within a Symbol. There's
+// always one Symbol for each symbol name. The resolver updates the SymbolBody
+// stored in the Body field of this object as it resolves symbols. Symbol also
+// holds computed properties of symbol names.
+struct Symbol {
+  uint32_t GlobalDynIndex = -1;
+
+  // Symbol binding. This is on the Symbol to track changes during resolution.
+  // In particular:
+  // An undefined weak is still weak when it resolves to a shared library.
+  // An undefined weak will not fetch archive members, but we have to remember
+  // it is weak.
+  uint8_t Binding;
+
+  // Symbol visibility. This is the computed minimum visibility of all
+  // observed non-DSO symbols.
+  unsigned Visibility : 2;
+
+  // True if the symbol was used for linking and thus need to be added to the
+  // output file's symbol table. This is true for all symbols except for
+  // unreferenced DSO symbols and bitcode symbols that are unreferenced except
+  // by other bitcode objects.
+  unsigned IsUsedInRegularObj : 1;
+
+  // If this flag is true and the symbol has protected or default visibility, it
+  // will appear in .dynsym. This flag is set by interposable DSO symbols in
+  // executables, by most symbols in DSOs and executables built with
+  // --export-dynamic, and by dynamic lists.
+  unsigned ExportDynamic : 1;
+
+  // This flag acts as an additional filter on the dynamic symbol list. It is
+  // set if there is no version script, or if the symbol appears in the global
+  // section of the version script.
+  unsigned VersionScriptGlobal : 1;
+
+  bool includeInDynsym() const;
+  bool isWeak() const { return Binding == llvm::ELF::STB_WEAK; }
+
+  // This field is used to store the Symbol's SymbolBody. This instantiation of
+  // AlignedCharArrayUnion gives us a struct with a char array field that is
+  // large and aligned enough to store any derived class of SymbolBody. We
+  // assume that the size and alignment of ELF64LE symbols is sufficient for any
+  // ELFT, and we verify this with the static_asserts in replaceBody.
+  llvm::AlignedCharArrayUnion<
+      DefinedBitcode, DefinedCommon, DefinedRegular<llvm::object::ELF64LE>,
+      DefinedSynthetic<llvm::object::ELF64LE>, Undefined,
+      SharedSymbol<llvm::object::ELF64LE>, LazyArchive, LazyObject>
+      Body;
+
+  SymbolBody *body() { return reinterpret_cast<SymbolBody *>(Body.buffer); }
+  const SymbolBody *body() const { return const_cast<Symbol *>(this)->body(); }
+};
+
+template <typename T, typename... ArgT>
+void replaceBody(Symbol *S, ArgT &&... Arg) {
+  static_assert(sizeof(T) <= sizeof(S->Body), "Body too small");
+  static_assert(alignof(T) <= alignof(decltype(S->Body)),
+                "Body not aligned enough");
+  static_assert(static_cast<SymbolBody *>(static_cast<T *>(nullptr)) == nullptr,
+                "Not a SymbolBody");
+  new (S->Body.buffer) T(std::forward<ArgT>(Arg)...);
+}
+
+inline Symbol *SymbolBody::symbol() {
+  assert(!isLocal());
+  return reinterpret_cast<Symbol *>(reinterpret_cast<char *>(this) -
+                                    offsetof(Symbol, Body));
+}
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/trunk/ELF/Symbols.cpp

case SymbolBody::SharedKind: {
     if (SS.isFunc())
       return Body.getPltVA<ELFT>();
     return Out<ELFT>::Bss->getVA() + SS.OffsetInBss;
   }
   case SymbolBody::UndefinedKind:
     return 0;
   case SymbolBody::LazyArchiveKind:
   case SymbolBody::LazyObjectKind:
-    assert(Body.Backref->IsUsedInRegularObj && "lazy symbol reached writer");
+    assert(Body.symbol()->IsUsedInRegularObj && "lazy symbol reached writer");
     return 0;
   case SymbolBody::DefinedBitcodeKind:
     llvm_unreachable("should have been replaced");
   }
   llvm_unreachable("invalid symbol kind");
 }
 
 SymbolBody::SymbolBody(Kind K, uint32_t NameOffset, uint8_t StOther,
                        uint8_t Type)
-    : SymbolKind(K), Type(Type), Binding(STB_LOCAL), StOther(StOther),
+    : SymbolKind(K), IsLocal(true), Type(Type), StOther(StOther),
       NameOffset(NameOffset) {
   init();
 }
 
-SymbolBody::SymbolBody(Kind K, StringRef Name, uint8_t Binding, uint8_t StOther,
-                       uint8_t Type)
-    : SymbolKind(K), Type(Type), Binding(Binding), StOther(StOther),
+SymbolBody::SymbolBody(Kind K, StringRef Name, uint8_t StOther, uint8_t Type)
+    : SymbolKind(K), IsLocal(false), Type(Type), StOther(StOther),
       Name({Name.data(), Name.size()}) {
-  assert(!isLocal());
   init();
 }
 
 void SymbolBody::init() {
   NeedsCopyOrPltAddr = false;
-  CanOmitFromDynSym = false;
 }
 
 // Returns true if a symbol can be replaced at load-time by a symbol
 // with the same name defined in other ELF executable or DSO.
 bool SymbolBody::isPreemptible() const {
   if (isLocal())
     return false;
 
   // Shared symbols resolve to the definition in the DSO.
   if (isShared())
     return true;
 
   // That's all that can be preempted in a non-DSO.
   if (!Config->Shared)
     return false;
 
   // Only symbols that appear in dynsym can be preempted.
-  if (!Backref->includeInDynsym())
+  if (!symbol()->includeInDynsym())
     return false;
 
   // Normally only default visibility symbols can be preempted, but -Bsymbolic
   // means that not even they can be preempted.
   if (Config->Bsymbolic || (Config->BsymbolicFunctions && isFunc()))
     return !isDefined();
-  return Backref->Visibility == STV_DEFAULT;
+  return symbol()->Visibility == STV_DEFAULT;
 }
 
 template <class ELFT>
 typename ELFT::uint SymbolBody::getVA(typename ELFT::uint Addend) const {
   typename ELFT::uint OutVA = getSymVA<ELFT>(*this, Addend);
   return OutVA + Addend;
 }
 
if (const auto *C = dyn_cast<DefinedCommon>(this))
     return C->Size;
   if (const auto *DR = dyn_cast<DefinedRegular<ELFT>>(this))
     return DR->Size;
   if (const auto *S = dyn_cast<SharedSymbol<ELFT>>(this))
     return S->Sym.st_size;
   return 0;
 }
 
-// Returns 1, 0 or -1 if this symbol should take precedence
-// over the Other, tie or lose, respectively.
-int SymbolBody::compare(SymbolBody *Other) {
-  assert(!isLazy() && !Other->isLazy());
-  std::tuple<bool, bool, bool> L(isDefined(), !isShared(), !isWeak());
-  std::tuple<bool, bool, bool> R(Other->isDefined(), !Other->isShared(),
-                                 !Other->isWeak());
-
-  // Compare the two by symbol type.
-  if (L > R)
-    return -Other->compare(this);
-  if (L != R)
-    return -1;
-  if (!isDefined() || isShared() || isWeak())
-    return 1;
-
-  // If both are equal in terms of symbol type, then at least
-  // one of them must be a common symbol. Otherwise, they conflict.
-  auto *A = dyn_cast<DefinedCommon>(this);
-  auto *B = dyn_cast<DefinedCommon>(Other);
-  if (!A && !B)
-    return 0;
-
-  // If both are common, the larger one is chosen.
-  if (A && B) {
-    if (Config->WarnCommon)
-      warning("multiple common of " + A->getName());
-    A->Alignment = B->Alignment = std::max(A->Alignment, B->Alignment);
-    return A->Size < B->Size ? -1 : 1;
-  }
-
-  // Non-common symbols takes precedence over common symbols.
-  if (Config->WarnCommon)
-    warning("common " + this->getName() + " is overridden");
-  return A ? -1 : 1;
-}
-
-Defined::Defined(Kind K, StringRef Name, uint8_t Binding, uint8_t StOther,
-                 uint8_t Type)
-    : SymbolBody(K, Name, Binding, StOther, Type) {}
+Defined::Defined(Kind K, StringRef Name, uint8_t StOther, uint8_t Type)
+    : SymbolBody(K, Name, StOther, Type) {}
 
 Defined::Defined(Kind K, uint32_t NameOffset, uint8_t StOther, uint8_t Type)
     : SymbolBody(K, NameOffset, StOther, Type) {}
 
-DefinedBitcode::DefinedBitcode(StringRef Name, bool IsWeak, uint8_t StOther)
-    : Defined(DefinedBitcodeKind, Name, IsWeak ? STB_WEAK : STB_GLOBAL,
-              StOther, 0 /* Type */) {}
+DefinedBitcode::DefinedBitcode(StringRef Name, uint8_t StOther, uint8_t Type,
+                               BitcodeFile *F)
+    : Defined(DefinedBitcodeKind, Name, StOther, Type), File(F) {}
 
 bool DefinedBitcode::classof(const SymbolBody *S) {
   return S->kind() == DefinedBitcodeKind;
 }
 
-Undefined::Undefined(StringRef Name, uint8_t Binding, uint8_t StOther,
-                     uint8_t Type, bool IsBitcode)
-    : SymbolBody(SymbolBody::UndefinedKind, Name, Binding, StOther, Type) {
-  this->IsUndefinedBitcode = IsBitcode;
-}
+Undefined::Undefined(StringRef Name, uint8_t StOther, uint8_t Type)
+    : SymbolBody(SymbolBody::UndefinedKind, Name, StOther, Type) {}
 
 Undefined::Undefined(uint32_t NameOffset, uint8_t StOther, uint8_t Type)
-    : SymbolBody(SymbolBody::UndefinedKind, NameOffset, StOther, Type) {
-  this->IsUndefinedBitcode = false;
-}
+    : SymbolBody(SymbolBody::UndefinedKind, NameOffset, StOther, Type) {}
 
 template <typename ELFT>
 DefinedSynthetic<ELFT>::DefinedSynthetic(StringRef N, uintX_t Value,
                                          OutputSectionBase<ELFT> &Section)
-    : Defined(SymbolBody::DefinedSyntheticKind, N, STB_GLOBAL, STV_HIDDEN,
-              0 /* Type */),
+    : Defined(SymbolBody::DefinedSyntheticKind, N, STV_HIDDEN, 0 /* Type */),
       Value(Value), Section(Section) {}
 
 DefinedCommon::DefinedCommon(StringRef N, uint64_t Size, uint64_t Alignment,
-                             uint8_t Binding, uint8_t StOther, uint8_t Type)
-    : Defined(SymbolBody::DefinedCommonKind, N, Binding, StOther, Type),
+                             uint8_t StOther, uint8_t Type)
+    : Defined(SymbolBody::DefinedCommonKind, N, StOther, Type),
       Alignment(Alignment), Size(Size) {}
 
 std::unique_ptr<InputFile> Lazy::getFile() {
   if (auto *S = dyn_cast<LazyArchive>(this))
     return S->getFile();
   return cast<LazyObject>(this)->getFile();
 }
 
#else
   free(Buf);
   return S;
 #endif
 }
 
 bool Symbol::includeInDynsym() const {
   if (Visibility != STV_DEFAULT && Visibility != STV_PROTECTED)
     return false;
-  return (ExportDynamic && VersionScriptGlobal) || Body->isShared() ||
-         (Body->isUndefined() && Config->Shared);
+  return (ExportDynamic && VersionScriptGlobal) || body()->isShared() ||
+         (body()->isUndefined() && Config->Shared);
 }
 
 template uint32_t SymbolBody::template getVA<ELF32LE>(uint32_t) const;
 template uint32_t SymbolBody::template getVA<ELF32BE>(uint32_t) const;
 template uint64_t SymbolBody::template getVA<ELF64LE>(uint64_t) const;
 template uint64_t SymbolBody::template getVA<ELF64BE>(uint64_t) const;
 
 template uint32_t SymbolBody::template getGotVA<ELF32LE>() const;

lld/trunk/ELF/Writer.cpp

static int32_t findMipsPairedAddend(const uint8_t *Buf, const uint8_t *BufLoc,
   StringRef NewName = getELFRelocationTypeName(Config->EMachine, Type);
   warning("can't find matching " + NewName + " relocation for " + OldName);
   return 0;
 }
 
 // True if non-preemptable symbol always has the same value regardless of where
 // the DSO is loaded.
 template <class ELFT> static bool isAbsolute(const SymbolBody &Body) {
-  Symbol *Sym = Body.Backref;
-  if (Body.isUndefined()) {
-    if (!Sym)
-      return false; // undefined local. That is the dummy symbol 0.
-    if (Sym->isWeak())
-      return true; // always 0
-  }
+  if (Body.isUndefined())
+    return !Body.isLocal() && Body.symbol()->isWeak();
   if (const auto *DR = dyn_cast<DefinedRegular<ELFT>>(&Body))
     return DR->Section == nullptr; // Absolute symbol.
   return false;
 }
 
 static bool needsPlt(RelExpr Expr) {
   return Expr == R_PLT_PC || Expr == R_PPC_PLT_OPD || Expr == R_PLT;
 }

 }
 
 template <class ELFT>
 static void reportUndefined(SymbolTable<ELFT> &Symtab, SymbolBody *Sym) {
   if (!Config->NoUndefined) {
     if (Config->Relocatable)
       return;
     if (Config->Shared)
-      if (Sym->Backref->Visibility == STV_DEFAULT)
+      if (Sym->symbol()->Visibility == STV_DEFAULT)
         return;
   }
 
   std::string Msg = "undefined symbol: " + Sym->getName().str();
   if (InputFile *File = Symtab.findFile(Sym))
     Msg += " in " + File->getName().str();
   if (Config->NoinhibitExec)
     warning(Msg);

 void Writer<ELFT>::addCopyRelSymbol(SharedSymbol<ELFT> *SS) {
   ensureBss();
   uintX_t Align = getAlignment(SS);
   uintX_t Off = alignTo(Out<ELFT>::Bss->getSize(), Align);
   Out<ELFT>::Bss->setSize(Off + SS->template getSize<ELFT>());
   Out<ELFT>::Bss->updateAlign(Align);
   uintX_t Shndx = SS->Sym.st_shndx;
   uintX_t Value = SS->Sym.st_value;
-  // Look through the DSO's dynamic symbol for aliases and create a dynamic
-  // symbol for each one. This causes the copy relocation to correctly interpose
-  // any aliases.
-  for (SharedSymbol<ELFT> &S : SS->File->getSharedSymbols()) {
-    if (S.Sym.st_shndx != Shndx || S.Sym.st_value != Value)
-      continue;
-    S.OffsetInBss = Off;
-    S.NeedsCopyOrPltAddr = true;
-    S.Backref->IsUsedInRegularObj = true;
+  // Look through the DSO's dynamic symbol table for aliases and create a
+  // dynamic symbol for each one. This causes the copy relocation to correctly
+  // interpose any aliases.
+  for (const Elf_Sym &S : SS->File->getElfSymbols(true)) {
+    if (S.st_shndx != Shndx || S.st_value != Value)
+      continue;
+    auto *Alias = dyn_cast_or_null<SharedSymbol<ELFT>>(
+        Symtab.find(check(S.getName(SS->File->getStringTable()))));
+    if (!Alias)
+      continue;
+    Alias->OffsetInBss = Off;
+    Alias->NeedsCopyOrPltAddr = true;
+    Alias->symbol()->IsUsedInRegularObj = true;
   }
   Out<ELFT>::RelaDyn->addReloc(
       {Target->CopyRel, Out<ELFT>::Bss, SS->OffsetInBss, false, SS, 0});
 }
 
 template <class ELFT>
 StringRef Writer<ELFT>::getOutputSectionName(InputSectionBase<ELFT> *S) const {
   StringRef Dest = Script<ELFT>::X->getOutputSection(S);

 
 template <class ELFT>
 bool Writer<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) const {
   return !S || S == &InputSection<ELFT>::Discarded || !S->Live ||
          Script<ELFT>::X->isDiscarded(S);
 }
 
 template <class ELFT>
-static SymbolBody *
-addOptionalSynthetic(SymbolTable<ELFT> &Table, StringRef Name,
-                     OutputSectionBase<ELFT> &Sec, typename ELFT::uint Val) {
+static Symbol *addOptionalSynthetic(SymbolTable<ELFT> &Table, StringRef Name,
+                                    OutputSectionBase<ELFT> &Sec,
+                                    typename ELFT::uint Val) {
   if (!Table.find(Name))
     return nullptr;
   return Table.addSynthetic(Name, Sec, Val);
 }
 
 // The beginning and the ending of .rel[a].plt section are marked
 // with __rel[a]_iplt_{start,end} symbols if it is a statically linked
 // executable. The runtime needs these symbols in order to resolve
 // all IRELATIVE relocs on startup. For dynamic executables, we don't
 // need these symbols, since IRELATIVE relocs are resolved through GOT
 // and PLT. For details, see http://www.airs.com/blog/archives/403.
 template <class ELFT> void Writer<ELFT>::addRelIpltSymbols() {
   if (isOutputDynamic() || !Out<ELFT>::RelaPlt)
     return;
   StringRef S = Config->Rela ? "__rela_iplt_start" : "__rel_iplt_start";
-  ElfSym<ELFT>::RelaIpltStart =
-      addOptionalSynthetic(Symtab, S, *Out<ELFT>::RelaPlt, 0);
 
   S = Config->Rela ? "__rela_iplt_end" : "__rel_iplt_end";
-  ElfSym<ELFT>::RelaIpltEnd = addOptionalSynthetic(
-      Symtab, S, *Out<ELFT>::RelaPlt, DefinedSynthetic<ELFT>::SectionEnd);
+  addOptionalSynthetic(Symtab, S, *Out<ELFT>::RelaPlt,
+                       DefinedSynthetic<ELFT>::SectionEnd);
 }
 
 template <class ELFT> static bool includeInSymtab(const SymbolBody &B) {
-  if (!B.Backref->IsUsedInRegularObj)
+  if (!B.symbol()->IsUsedInRegularObj)
     return false;
 
   if (auto *D = dyn_cast<DefinedRegular<ELFT>>(&B)) {
     // Exclude symbols pointing to garbage-collected sections.
     if (D->Section && !D->Section->Live)
       return false;
   }
   return true;

 // The linker is expected to define some symbols depending on
 // the linking result. This function defines such symbols.
 template <class ELFT> void Writer<ELFT>::addReservedSymbols() {
   if (Config->EMachine == EM_MIPS) {
     // Define _gp for MIPS. st_value of _gp symbol will be updated by Writer
     // so that it points to an absolute address which is relative to GOT.
     // See "Global Data Symbols" in Chapter 6 in the following document:
     // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
-    ElfSym<ELFT>::MipsGp =
-        Symtab.addSynthetic("_gp", *Out<ELFT>::Got, MipsGPOffset);
 
     // On MIPS O32 ABI, _gp_disp is a magic symbol designates offset between
     // start of function and 'gp' pointer into GOT.
     ElfSym<ELFT>::MipsGpDisp =
-        addOptionalSynthetic(Symtab, "_gp_disp", *Out<ELFT>::Got, MipsGPOffset);
+        addOptionalSynthetic(Symtab, "_gp_disp", *Out<ELFT>::Got, MipsGPOffset)
+            ->body();
     // The __gnu_local_gp is a magic symbol equal to the current value of 'gp'
     // pointer. This symbol is used in the code generated by .cpload pseudo-op
     // in case of using -mno-shared option.
     // https://sourceware.org/ml/binutils/2004-12/msg00094.html
-    ElfSym<ELFT>::MipsLocalGp = addOptionalSynthetic(
-        Symtab, "__gnu_local_gp", *Out<ELFT>::Got, MipsGPOffset);
+    addOptionalSynthetic(Symtab, "__gnu_local_gp", *Out<ELFT>::Got,
+                         MipsGPOffset);
   }
 
   // In the assembly for 32 bit x86 the _GLOBAL_OFFSET_TABLE_ symbol
   // is magical and is used to produce a R_386_GOTPC relocation.
   // The R_386_GOTPC relocation value doesn't actually depend on the
   // symbol value, so it could use an index of STN_UNDEF which, according
   // to the spec, means the symbol value is 0.
   // Unfortunately both gas and MC keep the _GLOBAL_OFFSET_TABLE_ symbol in
Sec->forEachInputSection([&](InputSectionBase<ELFT> *S) {
       }
     });
   }
 
   // Now that we have defined all possible symbols including linker-
   // synthesized ones. Visit all symbols to give the finishing touches.
   std::vector<DefinedCommon *> CommonSymbols;
   for (Symbol *S : Symtab.getSymbols()) {
-    SymbolBody *Body = S->Body;
+    SymbolBody *Body = S->body();
 
     // Set "used" bit for --as-needed.
     if (S->IsUsedInRegularObj && !S->isWeak())
       if (auto *SS = dyn_cast<SharedSymbol<ELFT>>(Body))
         SS->File->IsUsed = true;
 
     if (Body->isUndefined() && !S->isWeak())
       reportUndefined<ELFT>(Symtab, Body);
static uint32_t getMipsEFlags(bool Is64Bits) {
   uint32_t V = EF_MIPS_CPIC | EF_MIPS_ABI_O32 | EF_MIPS_ARCH_32R2;
   if (Config->Shared)
     V |= EF_MIPS_PIC;
   return V;
 }
 
 template <class ELFT> static typename ELFT::uint getEntryAddr() {
   if (Symbol *S = Config->EntrySym)
-    return S->Body->getVA<ELFT>();
+    return S->body()->getVA<ELFT>();
   if (Config->EntryAddr != uint64_t(-1))
     return Config->EntryAddr;
   return 0;
 }
 
 template <class ELFT> static uint8_t getELFEncoding() {
   if (ELFT::TargetEndianness == llvm::support::little)
     return ELFDATA2LSB;

lld/trunk/docs/NewLLD.rst

- Defined symbols are for all symbols that are considered as "resolved",
     absolute symbols, linker-created symbols, etc.
   - Undefined symbols represent undefined symbols, which need to be replaced by
     Defined symbols by the resolver until the link is complete.
   - Lazy symbols represent symbols we found in archive file headers
     which can turn into Defined if we read archieve members.
 
 * Symbol
 
-  Symbol is a pointer to a SymbolBody. There's only one Symbol for
-  each unique symbol name (this uniqueness is guaranteed by the symbol table).
-  Because SymbolBodies are created for each file independently,
-  there can be many SymbolBodies for the same name.
-  Thus, the relationship between Symbols and SymbolBodies is 1:N.
-  You can think of Symbols as handles for SymbolBodies.
-
-  The resolver keeps the Symbol's pointer to always point to the "best" SymbolBody.
-  Pointer mutation is the resolve operation of this linker.
-
-  SymbolBodies have pointers to their Symbols.
-  That means you can always find the best SymbolBody from
-  any SymbolBody by following pointers twice.
-  This structure makes it very easy and cheap to find replacements for symbols.
-  For example, if you have an Undefined SymbolBody, you can find a Defined
-  SymbolBody for that symbol just by going to its Symbol and then to SymbolBody,
-  assuming the resolver have successfully resolved all undefined symbols.
+  A Symbol is a container for a SymbolBody. There's only one Symbol for each
+  unique symbol name (this uniqueness is guaranteed by the symbol table).
+  Each global symbol has only one SymbolBody at any one time, which is
+  the SymbolBody stored within a memory region of the Symbol large enough
+  to store any SymbolBody.
+
+  As the resolver reads symbols from input files, it replaces the Symbol's
+  SymbolBody with the "best" SymbolBody for its symbol name by constructing
+  the new SymbolBody in place on top of the existing SymbolBody. For example,
+  if the resolver is given a defined symbol, and the SymbolBody with its name
+  is undefined, it will construct a Defined SymbolBody over the Undefined
+  SymbolBody.
+
+  This means that each SymbolBody pointer always points to the best SymbolBody,
+  and it is possible to get from a SymbolBody to a Symbol, or vice versa,
+  by adding or subtracting a fixed offset. This memory layout helps reduce
+  the cache miss rate through high locality and a small number of required
+  pointer indirections.
 
 * SymbolTable
 
   SymbolTable is basically a hash table from strings to Symbols
   with a logic to resolve symbol conflicts. It resolves conflicts by symbol type.
 
   - If we add Defined and Undefined symbols, the symbol table will keep the former.
   - If we add Defined and Lazy symbols, it will keep the former.

lld/trunk/test/ELF/lto/common2.ll

 ; produced.
 ; CHECK-NOT: @a = common global i8 0, align 8
 
 ; SHARED: Symbol {
 ; SHARED:   Name: a
 ; SHARED-NEXT:   Value: 0x2000
 ; SHARED-NEXT:   Size: 1
 ; SHARED-NEXT:   Binding: Global
-; SHARED-NEXT:   Type: None
+; SHARED-NEXT:   Type: Object
 ; SHARED-NEXT:   Other: 0
 ; SHARED-NEXT:   Section: .bss
 ; SHARED-NEXT: }

lld/trunk/test/ELF/relocation-copy-alias.s

 // CHECK-NEXT: Binding: Global
 // CHECK-NEXT: Type: Object (0x1)
 // CHECK-NEXT: Other: 0
 // CHECK-NEXT: Section: .bss
 
 // CHECK:      Name: a2
 // CHECK-NEXT: Value: [[A]]
 // CHECK-NEXT: Size: 1
-// CHECK-NEXT: Binding: Global
+// CHECK-NEXT: Binding: Weak
 // CHECK-NEXT: Type: Object (0x1)
 // CHECK-NEXT: Other: 0
 // CHECK-NEXT: Section: .bss
 
 // CHECK:      Name: b3
 // CHECK-NEXT: Value: [[B]]
 // CHECK-NEXT: Size: 1
-// CHECK-NEXT: Binding: Global (0x1)
+// CHECK-NEXT: Binding: Weak
 // CHECK-NEXT: Type: Object (0x1)
 // CHECK-NEXT: Other: 0
 // CHECK-NEXT: Section: .bss