[wip] COFF: New symbol table design.

[pcc]

Summary

This is a port of the new symbol table design from r268178 to the COFF linker.

I measured a small regression in link time with this patch (about 5-10%
for Chromium's chrome_child.dll) on my Windows machine. There is still a
regression if I disable the parallel object file parsing feature in the
existing code. I haven't had a chance to investigate the root cause yet.
I think we probably shouldn't land this until this is tracked down.

[ruiu]

It's interesting that this patch regresses performance even though this approach proved to be effective for the ELF linker. Does it mean the parallel object file parsing is effective for COFF? If so, it may indicate a possible optimization we can make for the ELF linker.

[pcc]

I still don't understand the cause of the regression. As I mentioned, I
still see a regression if I disable parallel object file parsing in the
existing code (by replacing the code starting at COFF/SymbolTable.cpp:28
with just "std::launch Policy = std::launch::deferred;") so it might not
have anything to do with parallel object file parsing.

I would also like to see whether this has something to do with the host OS.
I am working on a patch that adds a /reproduce flag to the COFF linker to
make it easier to measure performance on a Linux host.

Peter

[pcc]

Reviving this in preparation for running some performance measurements

[ruiu]

I think I want to get this in to close the architectural difference between COFF and ELF, and I like it removes the half-baked parallel file parsing.

So now that I'm able to link chrome_child.dll on Linux it turns out that I get very different results with "perf stat":

Before (median of 5 runs): 11.623297415 seconds time elapsed
After: 8.123567205 seconds time elapsed

#include <sys/time.h>

static uint64_t microsec(struct timespec Time) {
  return Time.tv_sec * 1000000 + (Time.tv_nsec / 1000);
}

void elf::log2(const Twine &Msg) {
  static uint64_t Start = 0;
  struct timespec Time;
  clock_gettime(CLOCK_MONOTONIC, &Time);
  if (Start == 0)
    Start = microsec(Time);
  llvm::errs() << (microsec(Time) - Start) << " " << Msg << "\n";
}

I often add this piece of code to measure time of each pass. This is hacky but still better than time command. Did you try to measure this patch on Windows?

lld/COFF/SymbolTable.cpp

78 ↗

(On Diff #80854)

Remove llvm:: from here and other places.

[pcc]

In D21166#618607, @ruiu wrote:

I think I want to get this in to close the architectural difference between COFF and ELF, and I like it removes the half-baked parallel file parsing.

So now that I'm able to link chrome_child.dll on Linux it turns out that I get very different results with "perf stat":

Before (median of 5 runs): 11.623297415 seconds time elapsed
After: 8.123567205 seconds time elapsed

#include <sys/time.h>

static uint64_t microsec(struct timespec Time) {
  return Time.tv_sec * 1000000 + (Time.tv_nsec / 1000);
}

void elf::log2(const Twine &Msg) {
  static uint64_t Start = 0;
  struct timespec Time;
  clock_gettime(CLOCK_MONOTONIC, &Time);
  if (Start == 0)
    Start = microsec(Time);
  llvm::errs() << (microsec(Time) - Start) << " " << Msg << "\n";
}

I often add this piece of code to measure time of each pass. This is hacky but still better than time command. Did you try to measure this patch on Windows?

Yes, and I'm still seeing the regression on Windows. The MSVC profiler tells me that I'm spending a lot of time creating memory maps for files, so I'm wondering whether memory map performance on Windows is the root cause of the very different performance results as compared to Linux (maybe this patch somehow causes us to open files repeatedly or something, I don't know). I'm still investigating, but I think I'd be fine with landing this in parallel with the investigation.

[ruiu]

LGTM. Please submit this patch. I'm now trying to close the gap between ELF and COFF, and that's exactly what I want. Thank you for doing this.

COFF/Chunks.h

 namespace lld {
 namespace coff {
 
 using llvm::COFF::ImportDirectoryTableEntry;
 using llvm::object::COFFSymbolRef;
 using llvm::object::SectionRef;
 using llvm::object::coff_relocation;
 using llvm::object::coff_section;
-using llvm::sys::fs::file_magic;
 
 class Baserel;
 class Defined;
 class DefinedImportData;
 class DefinedRegular;
 class ObjectFile;
 class OutputSection;
 class SymbolBody;

COFF/Chunks.cpp

if (!hasData())
     return;
   // Copy section contents from source object file to output file.
   ArrayRef<uint8_t> A = getContents();
   memcpy(Buf + OutputSectionOff, A.data(), A.size());
 
   // Apply relocations.
   for (const coff_relocation &Rel : Relocs) {
     uint8_t *Off = Buf + OutputSectionOff + Rel.VirtualAddress;
-    SymbolBody *Body = File->getSymbolBody(Rel.SymbolTableIndex)->repl();
+    SymbolBody *Body = File->getSymbolBody(Rel.SymbolTableIndex);
     Defined *Sym = cast<Defined>(Body);
     uint64_t P = RVA + Rel.VirtualAddress;
     switch (Config->Machine) {
     case AMD64:
       applyRelX64(Off, Rel.Type, Sym, P);
       break;
     case I386:
       applyRelX86(Off, Rel.Type, Sym, P);

 // Collect all locations that contain absolute addresses, which need to be
 // fixed by the loader if load-time relocation is needed.
 // Only called when base relocation is enabled.
 void SectionChunk::getBaserels(std::vector<Baserel> *Res) {
   for (const coff_relocation &Rel : Relocs) {
     uint8_t Ty = getBaserelType(Rel);
     if (Ty == IMAGE_REL_BASED_ABSOLUTE)
       continue;
-    SymbolBody *Body = File->getSymbolBody(Rel.SymbolTableIndex)->repl();
+    SymbolBody *Body = File->getSymbolBody(Rel.SymbolTableIndex);
     if (isa<DefinedAbsolute>(Body))
       continue;
     Res->emplace_back(RVA + Rel.VirtualAddress, Ty);
   }
 }
 
 bool SectionChunk::hasData() const {
   return !(Header->Characteristics & IMAGE_SCN_CNT_UNINITIALIZED_DATA);

COFF/Config.h

 namespace coff {
 
 using llvm::COFF::IMAGE_FILE_MACHINE_UNKNOWN;
 using llvm::COFF::WindowsSubsystem;
 using llvm::StringRef;
 class DefinedAbsolute;
 class DefinedRelative;
 class StringChunk;
-class Undefined;
+struct Symbol;
+class SymbolBody;
 
 // Short aliases.
 static const auto AMD64 = llvm::COFF::IMAGE_FILE_MACHINE_AMD64;
 static const auto ARMNT = llvm::COFF::IMAGE_FILE_MACHINE_ARMNT;
 static const auto I386 = llvm::COFF::IMAGE_FILE_MACHINE_I386;
 
 // Represents an /export option.
 struct Export {
   StringRef Name;       // N in /export:N or /export:E=N
   StringRef ExtName;    // E in /export:E=N
-  Undefined *Sym = nullptr;
+  SymbolBody *Sym = nullptr;
   uint16_t Ordinal = 0;
   bool Noname = false;
   bool Data = false;
   bool Private = false;
 
   // If an export is a form of /export:foo=dllname.bar, that means
   // that foo should be exported as an alias to bar in the DLL.
   // ForwardTo is set to "dllname.bar" part. Usually empty.

 // Global configuration.
 struct Configuration {
   enum ManifestKind { SideBySide, Embed, No };
   bool is64() { return Machine == AMD64; }
 
   llvm::COFF::MachineTypes Machine = IMAGE_FILE_MACHINE_UNKNOWN;
   bool Verbose = false;
   WindowsSubsystem Subsystem = llvm::COFF::IMAGE_SUBSYSTEM_UNKNOWN;
-  Undefined *Entry = nullptr;
+  SymbolBody *Entry = nullptr;
   bool NoEntry = false;
   std::string OutputFile;
   bool DoGC = true;
   bool DoICF = true;
   bool Relocatable = true;
   bool Force = false;
   bool Debug = false;
   bool WriteSymtab = true;
 
   // Symbols in this set are considered as live by the garbage collector.
-  std::set<Undefined *> GCRoot;
+  std::set<SymbolBody *> GCRoot;
 
   std::set<StringRef> NoDefaultLibs;
   bool NoDefaultLibAll = false;
 
   // True if we are creating a DLL.
   bool DLL = false;
   StringRef Implib;
   std::vector<Export> Exports;
   std::set<std::string> DelayLoads;
   std::map<std::string, int> DLLOrder;
-  Undefined *DelayLoadHelper = nullptr;
+  SymbolBody *DelayLoadHelper = nullptr;
 
   // Used for SafeSEH.
-  DefinedRelative *SEHTable = nullptr;
-  DefinedAbsolute *SEHCount = nullptr;
+  Symbol *SEHTable = nullptr;
+  Symbol *SEHCount = nullptr;
 
   // Used for /opt:lldlto=N
   unsigned LTOOptLevel = 2;
 
   // Used for /opt:lldltojobs=N
   unsigned LTOJobs = 1;
 
   // Used for /merge:from=to (e.g. /merge:.rdata=.text)

COFF/DLL.cpp

public:
   size_t getSize() const override { return Size * 4; }
 
   void writeTo(uint8_t *Buf) const override {
     for (Export &E : Config->Exports) {
       uint8_t *P = Buf + OutputSectionOff + E.Ordinal * 4;
       if (E.ForwardChunk) {
         write32le(P, E.ForwardChunk->getRVA());
       } else {
-        write32le(P, cast<Defined>(E.Sym->repl())->getRVA());
+        write32le(P, cast<Defined>(E.Sym)->getRVA());
       }
     }
   }
 
 private:
   size_t Size;
 };
 

COFF/Driver.h

private:
   std::vector<const char *> replaceResponseFiles(std::vector<const char *>);
 
   llvm::BumpPtrAllocator AllocAux;
   llvm::StringSaver Alloc;
 };
 
 class LinkerDriver {
 public:
-  LinkerDriver() : Alloc(AllocAux) {}
+  LinkerDriver() : Alloc(AllocAux) {
+    coff::Symtab = &Symtab;
+  }
   void link(llvm::ArrayRef<const char *> Args);
 
   // Used by the resolver to parse .drectve section contents.
   void parseDirectives(StringRef S);
 
 private:
   llvm::BumpPtrAllocator AllocAux;
   llvm::StringSaver Alloc;
private:
 
   // Parses LIB environment which contains a list of search paths.
   void addLibSearchPaths();
 
   // Library search path. The first element is always "" (current directory).
   std::vector<StringRef> SearchPaths;
   std::set<std::string> VisitedFiles;
 
-  Undefined *addUndefined(StringRef Sym);
+  SymbolBody *addUndefined(StringRef Sym);
   StringRef mangle(StringRef Sym);
 
   // Windows specific -- "main" is not the only main function in Windows.
   // You can choose one from these four -- {w,}{WinMain,main}.
   // There are four different entry point functions for them,
   // {w,}{WinMain,main}CRTStartup, respectively. The linker needs to
   // choose the right one depending on which "main" function is defined.
   // This function looks up the symbol table and resolve corresponding

COFF/Driver.cpp

void LinkerDriver::addLibSearchPaths() {
   StringRef Env = Alloc.save(*EnvOpt);
   while (!Env.empty()) {
     StringRef Path;
     std::tie(Path, Env) = Env.split(';');
     SearchPaths.push_back(Path);
   }
 }
 
-Undefined *LinkerDriver::addUndefined(StringRef Name) {
-  Undefined *U = Symtab.addUndefined(Name);
-  Config->GCRoot.insert(U);
-  return U;
+SymbolBody *LinkerDriver::addUndefined(StringRef Name) {
+  SymbolBody *B = Symtab.addUndefined(Name);
+  Config->GCRoot.insert(B);
+  return B;
 }
 
 // Symbol names are mangled by appending "_" prefix on x86.
 StringRef LinkerDriver::mangle(StringRef Sym) {
   assert(Config->Machine != IMAGE_FILE_MACHINE_UNKNOWN);
   if (Config->Machine == I386)
     return Alloc.save("_" + Sym);
   return Sym;
 }
 
 // Windows specific -- find default entry point name.
 StringRef LinkerDriver::findDefaultEntry() {
   // User-defined main functions and their corresponding entry points.
   static const char *Entries[][2] = {
       {"main", "mainCRTStartup"},
       {"wmain", "wmainCRTStartup"},
       {"WinMain", "WinMainCRTStartup"},
       {"wWinMain", "wWinMainCRTStartup"},
   };
   for (auto E : Entries) {
     StringRef Entry = Symtab.findMangle(mangle(E[0]));
-    if (!Entry.empty() && !isa<Undefined>(Symtab.find(Entry)->Body))
+    if (!Entry.empty() && !isa<Undefined>(Symtab.find(Entry)->body()))
       return mangle(E[1]);
   }
   return "";
 }
 
 WindowsSubsystem LinkerDriver::inferSubsystem() {
   if (Config->DLL)
     return IMAGE_SUBSYSTEM_WINDOWS_GUI;
for (;;) {
     // Add weak aliases. Weak aliases is a mechanism to give remaining
     // undefined symbols final chance to be resolved successfully.
     for (auto Pair : Config->AlternateNames) {
       StringRef From = Pair.first;
       StringRef To = Pair.second;
       Symbol *Sym = Symtab.find(From);
       if (!Sym)
         continue;
-      if (auto *U = dyn_cast<Undefined>(Sym->Body))
+      if (auto *U = dyn_cast<Undefined>(Sym->body()))
         if (!U->WeakAlias)
           U->WeakAlias = Symtab.addUndefined(To);
     }
 
     // Windows specific -- if __load_config_used can be resolved, resolve it.
     if (Symtab.findUnderscore("_load_config_used"))
       addUndefined(mangle("_load_config_used"));
 
     if (Symtab.queueEmpty())
       break;
     Symtab.run();
   }
 
   // Do LTO by compiling bitcode input files to a set of native COFF files then
   // link those files.
   Symtab.addCombinedLTOObjects();
 
   // Make sure we have resolved all symbols.
-  Symtab.reportRemainingUndefines(/*Resolve=*/true);
+  Symtab.reportRemainingUndefines();
 
   // Windows specific -- if no /subsystem is given, we need to infer
   // that from entry point name.
   if (Config->Subsystem == IMAGE_SUBSYSTEM_UNKNOWN) {
     Config->Subsystem = inferSubsystem();
     if (Config->Subsystem == IMAGE_SUBSYSTEM_UNKNOWN)
       error("subsystem must be defined");
   }

COFF/DriverUtils.cpp

void fixupExports() {
   for (Export &E : Config->Exports) {
     if (E.Ordinal == 0)
       continue;
     if (!Ords.insert(E.Ordinal).second)
       error("duplicate export ordinal: " + E.Name);
   }
 
   for (Export &E : Config->Exports) {
+    SymbolBody *Sym = E.Sym;
     if (!E.ForwardTo.empty()) {
       E.SymbolName = E.Name;
-    } else if (Undefined *U = cast_or_null<Undefined>(E.Sym->WeakAlias)) {
-      E.SymbolName = U->getName();
-    } else {
-      E.SymbolName = E.Sym->getName();
-    }
+    } else if (auto *U = dyn_cast<Undefined>(Sym))
+      if (U->WeakAlias)
+        Sym = U->WeakAlias;
+    E.SymbolName = Sym->getName();
   }
 
   for (Export &E : Config->Exports) {
     if (!E.ForwardTo.empty()) {
       E.ExportName = undecorate(E.Name);
     } else {
       E.ExportName = undecorate(E.ExtName.empty() ? E.Name : E.ExtName);
     }

COFF/ICF.cpp

if (A->AssocChildren[I]->GroupID != B->AssocChildren[I]->GroupID)
       return false;
 
   // Compare relocations.
   auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
     if (R1.Type != R2.Type ||
         R1.VirtualAddress != R2.VirtualAddress) {
       return false;
     }
-    SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex)->repl();
-    SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex)->repl();
+    SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex);
+    SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex);
     if (B1 == B2)
       return true;
     if (auto *D1 = dyn_cast<DefinedRegular>(B1))
       if (auto *D2 = dyn_cast<DefinedRegular>(B2))
         return D1->getValue() == D2->getValue() &&
                D1->getChunk()->GroupID == D2->getChunk()->GroupID;
     return false;
   };

 bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) {
   // Compare associative sections.
   for (size_t I = 0, E = A->AssocChildren.size(); I != E; ++I)
     if (A->AssocChildren[I]->GroupID != B->AssocChildren[I]->GroupID)
       return false;
 
   // Compare relocations.
   auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
-    SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex)->repl();
-    SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex)->repl();
+    SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex);
+    SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex);
     if (B1 == B2)
       return true;
     if (auto *D1 = dyn_cast<DefinedRegular>(B1))
       if (auto *D2 = dyn_cast<DefinedRegular>(B2))
         return D1->getChunk()->GroupID == D2->getChunk()->GroupID;
     return false;
   };
   return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq);

COFF/InputFiles.h

 namespace coff {
 
 using llvm::LTOModule;
 using llvm::COFF::IMAGE_FILE_MACHINE_UNKNOWN;
 using llvm::COFF::MachineTypes;
 using llvm::object::Archive;
 using llvm::object::COFFObjectFile;
 using llvm::object::COFFSymbolRef;
+using llvm::object::coff_import_header;
 using llvm::object::coff_section;
 
 class Chunk;
 class Defined;
 class DefinedImportData;
 class DefinedImportThunk;
 class Lazy;
+struct Symbol;
 class SymbolBody;
 class Undefined;
 
 // The root class of input files.
 class InputFile {
 public:
   enum Kind { ArchiveKind, ObjectKind, ImportKind, BitcodeKind };
   Kind kind() const { return FileKind; }
   virtual ~InputFile() {}
 
   // Returns the filename.
   StringRef getName() { return MB.getBufferIdentifier(); }
 
-  // Returns symbols defined by this file.
-  virtual std::vector<SymbolBody *> &getSymbols() = 0;
-
   // Reads a file (the constructor doesn't do that).
   virtual void parse() = 0;
 
   // Returns the CPU type this file was compiled to.
   virtual MachineTypes getMachineType() { return IMAGE_FILE_MACHINE_UNKNOWN; }
 
   // Returns a short, human-friendly filename. If this is a member of
   // an archive file, a returned value includes parent's filename.
   // Used for logging or debugging.
   std::string getShortName();
 
   // Sets a parent filename if this file is created from an archive.
   void setParentName(StringRef N) { ParentName = N; }
 
   // Returns .drectve section contents if exist.
   StringRef getDirectives() { return StringRef(Directives).trim(); }
 
-  // Each file has a unique index. The index number is used to
-  // resolve ties in symbol resolution.
-  int Index;
-  static int NextIndex;
-
 protected:
-  InputFile(Kind K, MemoryBufferRef M)
-      : Index(NextIndex++), MB(M), FileKind(K) {}
+  InputFile(Kind K, MemoryBufferRef M) : MB(M), FileKind(K) {}
 
   MemoryBufferRef MB;
   std::string Directives;
 
 private:
   const Kind FileKind;
   StringRef ParentName;
 };
 
 // .lib or .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() override;
 
-  // 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<Lazy> getLazySymbols() { return LazySymbols; }
-
-  // All symbols returned by ArchiveFiles are of Lazy type.
-  std::vector<SymbolBody *> &getSymbols() override {
-    llvm_unreachable("internal error");
-  }
+  // Returns an input file for a given symbol. A null pointer is returned if we
+  // have already returned the same input file. (So that we don't instantiate
+  // the same member more than once.)
+  std::unique_ptr<InputFile> getMember(const Archive::Symbol *Sym);
 
 private:
   std::unique_ptr<Archive> File;
   std::string Filename;
-  std::vector<Lazy> LazySymbols;
   std::map<uint64_t, std::atomic_flag> Seen;
 };
 
 // .obj or .o file. This may be a member of an archive file.
 class ObjectFile : public InputFile {
 public:
   explicit ObjectFile(MemoryBufferRef M) : InputFile(ObjectKind, M) {}
   static bool classof(const InputFile *F) { return F->kind() == ObjectKind; }
   void parse() override;
   MachineTypes getMachineType() override;
   std::vector<Chunk *> &getChunks() { return Chunks; }
-  std::vector<SymbolBody *> &getSymbols() override { return SymbolBodies; }
+  std::vector<SymbolBody *> &getSymbols() { return SymbolBodies; }
 
   // Returns a SymbolBody object for the SymbolIndex'th symbol in the
   // underlying object file.
   SymbolBody *getSymbolBody(uint32_t SymbolIndex) {
     return SparseSymbolBodies[SymbolIndex];
   }
 
   // Returns the underying COFF file.
   COFFObjectFile *getCOFFObj() { return COFFObj.get(); }
 
   // True if this object file is compatible with SEH.
   // COFF-specific and x86-only.
   bool SEHCompat = false;
 
   // The list of safe exception handlers listed in .sxdata section.
   // COFF-specific and x86-only.
   std::set<SymbolBody *> SEHandlers;
 
 private:
   void initializeChunks();
   void initializeSymbols();
   void initializeSEH();
 
-  Defined *createDefined(COFFSymbolRef Sym, const void *Aux, bool IsFirst);
-  Undefined *createUndefined(COFFSymbolRef Sym);
+  SymbolBody *createDefined(COFFSymbolRef Sym, const void *Aux, bool IsFirst);
+  SymbolBody *createUndefined(COFFSymbolRef Sym);
 
   std::unique_ptr<COFFObjectFile> COFFObj;
   llvm::BumpPtrAllocator Alloc;
   const coff_section *SXData = nullptr;
 
   // List of all chunks defined by this file. This includes both section
   // chunks and non-section chunks for common symbols.
   std::vector<Chunk *> Chunks;

 // This type represents import library members that contain DLL names
 // and symbols exported from the DLLs. See Microsoft PE/COFF spec. 7
 // for details about the format.
 class ImportFile : public InputFile {
 public:
   explicit ImportFile(MemoryBufferRef M)
       : InputFile(ImportKind, M), StringAlloc(StringAllocAux) {}
   static bool classof(const InputFile *F) { return F->kind() == ImportKind; }
-  std::vector<SymbolBody *> &getSymbols() override { return SymbolBodies; }
 
   DefinedImportData *ImpSym = nullptr;
   DefinedImportThunk *ThunkSym = nullptr;
   std::string DLLName;
 
 private:
   void parse() override;
 
-  std::vector<SymbolBody *> SymbolBodies;
   llvm::BumpPtrAllocator Alloc;
   llvm::BumpPtrAllocator StringAllocAux;
   llvm::StringSaver StringAlloc;
+
+public:
+  StringRef ExternalName;
+  const coff_import_header *Hdr;
+  Chunk *Location = nullptr;
 };
 
 // Used for LTO.
 class BitcodeFile : public InputFile {
 public:
   explicit BitcodeFile(MemoryBufferRef M) : InputFile(BitcodeKind, M) {}
   static bool classof(const InputFile *F) { return F->kind() == BitcodeKind; }
-  std::vector<SymbolBody *> &getSymbols() override { return SymbolBodies; }
+  std::vector<SymbolBody *> &getSymbols() { return SymbolBodies; }
   MachineTypes getMachineType() override;
   std::unique_ptr<LTOModule> takeModule() { return std::move(M); }
 
   static llvm::LLVMContext Context;
 
 private:
   void parse() override;
 

COFF/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 "Chunks.h"
 #include "Config.h"
 #include "Error.h"
 #include "InputFiles.h"
+#include "SymbolTable.h"
 #include "Symbols.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/LTO/LTOModule.h"
 #include "llvm/Object/Binary.h"
 #include "llvm/Object/COFF.h"

 #include <utility>
 
 using namespace llvm::COFF;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 
 using llvm::Triple;
 using llvm::support::ulittle32_t;
+using llvm::sys::fs::file_magic;
+using llvm::sys::fs::identify_magic;
 
 namespace lld {
 namespace coff {
 
-int InputFile::NextIndex = 0;
 llvm::LLVMContext BitcodeFile::Context;
 
 // Returns the last element of a path, which is supposed to be a filename.
 static StringRef getBasename(StringRef Path) {
   size_t Pos = Path.find_last_of("\\/");
   if (Pos == StringRef::npos)
     return Path;
   return Path.substr(Pos + 1);

 }
 
 void ArchiveFile::parse() {
   // Parse a MemoryBufferRef as an archive file.
   auto ArchiveOrErr = Archive::create(MB);
   error(ArchiveOrErr, "Failed to parse static library");
   File = std::move(*ArchiveOrErr);
 
-  // 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);
-
   // Seen is a map from member files to boolean values. Initially
   // all members are mapped to false, which indicates all these files
   // are not read yet.
   for (auto &ChildOrErr : File->children()) {
     error(ChildOrErr, "Failed to parse static library");
     const Archive::Child &Child = *ChildOrErr;
     Seen[Child.getChildOffset()].clear();
   }
+
+  // Read the symbol table to construct Lazy objects.
+  for (const Archive::Symbol &Sym : File->symbols())
+    Symtab->addLazy(this, Sym);
 }
 
 // Returns a buffer pointing to a member file containing a given symbol.
 // This function is thread-safe.
-MemoryBufferRef ArchiveFile::getMember(const Archive::Symbol *Sym) {
+std::unique_ptr<InputFile> ArchiveFile::getMember(const Archive::Symbol *Sym) {
   auto COrErr = Sym->getMember();
   error(COrErr, Twine("Could not get the member for symbol ") + Sym->getName());
   const Archive::Child &C = *COrErr;
 
   // Return an empty buffer if we have already returned the same buffer.
   if (Seen[C.getChildOffset()].test_and_set())
-    return MemoryBufferRef();
-  ErrorOr<MemoryBufferRef> Ret = C.getMemoryBufferRef();
-  error(Ret, Twine("Could not get the buffer for the member defining symbol ") +
-                 Sym->getName());
-  return *Ret;
+    return std::unique_ptr<InputFile>(nullptr);
+  ErrorOr<MemoryBufferRef> MBRef = C.getMemoryBufferRef();
+  error(MBRef,
+        Twine("Could not get the buffer for the member defining symbol ") +
+
+  file_magic Magic = identify_magic(MBRef->getBuffer());
+  if (Magic == file_magic::coff_import_library)
+    return std::unique_ptr<InputFile>(new ImportFile(*MBRef));
+
+  std::unique_ptr<InputFile> Obj;
+  if (Magic == file_magic::coff_object)
+    Obj.reset(new ObjectFile(*MBRef));
+  else if (Magic == file_magic::bitcode)
+    Obj.reset(new BitcodeFile(*MBRef));
+  else
+    error(Twine(MBRef->getBufferIdentifier()) + ": unknown file type");
+
+  Obj->setParentName(getName());
+  return Obj;
 }
 
 void ObjectFile::parse() {
   // Parse a memory buffer as a COFF file.
   auto BinOrErr = createBinary(MB);
   if (!BinOrErr)
     error(errorToErrorCode(BinOrErr.takeError()),
                            "Failed to parse object file");
for (uint32_t I = 1; I < NumSections + 1; ++I) {
     SparseChunks[I] = C;
   }
 }
 
 void ObjectFile::initializeSymbols() {
   uint32_t NumSymbols = COFFObj->getNumberOfSymbols();
   SymbolBodies.reserve(NumSymbols);
   SparseSymbolBodies.resize(NumSymbols);
-  llvm::SmallVector<std::pair<Undefined *, uint32_t>, 8> WeakAliases;
+  llvm::SmallVector<std::pair<SymbolBody *, uint32_t>, 8> WeakAliases;
   int32_t LastSectionNumber = 0;
   for (uint32_t I = 0; I < NumSymbols; ++I) {
     // Get a COFFSymbolRef object.
     auto SymOrErr = COFFObj->getSymbol(I);
     error(SymOrErr, Twine("broken object file: ") + getName());
 
     COFFSymbolRef Sym = *SymOrErr;
 
     const void *AuxP = nullptr;
     if (Sym.getNumberOfAuxSymbols())
       AuxP = COFFObj->getSymbol(I + 1)->getRawPtr();
     bool IsFirst = (LastSectionNumber != Sym.getSectionNumber());
 
     SymbolBody *Body = nullptr;
     if (Sym.isUndefined()) {
       Body = createUndefined(Sym);
     } else if (Sym.isWeakExternal()) {
       Body = createUndefined(Sym);
       uint32_t TagIndex =
           static_cast<const coff_aux_weak_external *>(AuxP)->TagIndex;
-      WeakAliases.emplace_back((Undefined *)Body, TagIndex);
+      WeakAliases.emplace_back(Body, TagIndex);
     } else {
       Body = createDefined(Sym, AuxP, IsFirst);
     }
     if (Body) {
       SymbolBodies.push_back(Body);
       SparseSymbolBodies[I] = Body;
     }
     I += Sym.getNumberOfAuxSymbols();
     LastSectionNumber = Sym.getSectionNumber();
   }
-  for (auto WeakAlias : WeakAliases)
-    WeakAlias.first->WeakAlias = SparseSymbolBodies[WeakAlias.second];
+  for (auto WeakAlias : WeakAliases) {
+    auto *U = dyn_cast<Undefined>(WeakAlias.first);
+    if (!U)
+      continue;
+    // Report an error if two undefined symbols have different weak aliases.
+    if (U->WeakAlias && U->WeakAlias != SparseSymbolBodies[WeakAlias.second])
+      Symtab->reportDuplicate(U->symbol(), this);
+    U->WeakAlias = SparseSymbolBodies[WeakAlias.second];
+  }
 }
 
-Undefined *ObjectFile::createUndefined(COFFSymbolRef Sym) {
+SymbolBody *ObjectFile::createUndefined(COFFSymbolRef Sym) {
   StringRef Name;
   COFFObj->getSymbolName(Sym, Name);
-  return new (Alloc) Undefined(Name);
+  return Symtab->addUndefined(Name, this, Sym.isWeakExternal())->body();
 }
 
-Defined *ObjectFile::createDefined(COFFSymbolRef Sym, const void *AuxP,
+SymbolBody *ObjectFile::createDefined(COFFSymbolRef Sym, const void *AuxP,
                                       bool IsFirst) {
   StringRef Name;
   if (Sym.isCommon()) {
     auto *C = new (Alloc) CommonChunk(Sym);
     Chunks.push_back(C);
-    return new (Alloc) DefinedCommon(this, Sym, C);
+    return Symtab->addCommon(this, Sym, C)->body();
   }
   if (Sym.isAbsolute()) {
     COFFObj->getSymbolName(Sym, Name);
     // Skip special symbols.
     if (Name == "@comp.id")
       return nullptr;
     // COFF spec 5.10.1. The .sxdata section.
     if (Name == "@feat.00") {
       if (Sym.getValue() & 1)
         SEHCompat = true;
       return nullptr;
     }
+    if (Sym.isExternal())
+      return Symtab->addAbsolute(Name, Sym)->body();
+    else
       return new (Alloc) DefinedAbsolute(Name, Sym);
   }
   int32_t SectionNumber = Sym.getSectionNumber();
   if (SectionNumber == llvm::COFF::IMAGE_SYM_DEBUG)
     return nullptr;
 
   // Reserved sections numbers don't have contents.
   if (llvm::COFF::isReservedSectionNumber(SectionNumber))
     error(Twine("broken object file: ") + getName());
if (IsFirst && AuxP) {
     auto *Aux = reinterpret_cast<const coff_aux_section_definition *>(AuxP);
     if (Aux->Selection == IMAGE_COMDAT_SELECT_ASSOCIATIVE)
       if (auto *ParentSC = cast_or_null<SectionChunk>(
               SparseChunks[Aux->getNumber(Sym.isBigObj())]))
         ParentSC->addAssociative(SC);
     SC->Checksum = Aux->CheckSum;
   }
 
-  auto *B = new (Alloc) DefinedRegular(this, Sym, SC);
+  DefinedRegular *B;
+  if (Sym.isExternal())
+    B = cast<DefinedRegular>(Symtab->addRegular(this, Sym, SC)->body());
+  else
+    B = new (Alloc) DefinedRegular(this, Sym, SC);
   if (SC->isCOMDAT() && Sym.getValue() == 0 && !AuxP)
     SC->setSymbol(B);
 
   return B;
 }
 
 void ObjectFile::initializeSEH() {
   if (!SEHCompat || !SXData)
void ImportFile::parse() {
   case IMPORT_NAME_NOPREFIX:
     ExtName = ltrim1(Name, "?@_");
     break;
   case IMPORT_NAME_UNDECORATE:
     ExtName = ltrim1(Name, "?@_");
     ExtName = ExtName.substr(0, ExtName.find('@'));
     break;
   }
-  ImpSym = new (Alloc) DefinedImportData(DLLName, ImpName, ExtName, Hdr);
-  SymbolBodies.push_back(ImpSym);
+
+  this->Hdr = Hdr;
+  ExternalName = ExtName;
+
+  ImpSym = cast<DefinedImportData>(
+      Symtab->addImportData(ImpName, this)->body());
 
   // If type is function, we need to create a thunk which jump to an
   // address pointed by the __imp_ symbol. (This allows you to call
   // DLL functions just like regular non-DLL functions.)
   if (Hdr->getType() != llvm::COFF::IMPORT_CODE)
     return;
-  ThunkSym = new (Alloc) DefinedImportThunk(Name, ImpSym, Hdr->Machine);
-  SymbolBodies.push_back(ThunkSym);
+  ThunkSym = cast<DefinedImportThunk>(
+      Symtab->addImportThunk(Name, ImpSym, Hdr->Machine)->body());
 }
 
 void BitcodeFile::parse() {
-  // Usually parse() is thread-safe, but bitcode file is an exception.
-  std::lock_guard<std::mutex> Lock(Mu);
-
   Context.enableDebugTypeODRUniquing();
   ErrorOr<std::unique_ptr<LTOModule>> ModOrErr = LTOModule::createFromBuffer(
       Context, MB.getBufferStart(), MB.getBufferSize(), llvm::TargetOptions());
   error(ModOrErr, "Could not create lto module");
   M = std::move(*ModOrErr);
 
   llvm::StringSaver Saver(Alloc);
   for (unsigned I = 0, E = M->getSymbolCount(); I != E; ++I) {
     lto_symbol_attributes Attrs = M->getSymbolAttributes(I);
     if ((Attrs & LTO_SYMBOL_SCOPE_MASK) == LTO_SYMBOL_SCOPE_INTERNAL)
       continue;
 
     StringRef SymName = Saver.save(M->getSymbolName(I));
     int SymbolDef = Attrs & LTO_SYMBOL_DEFINITION_MASK;
     if (SymbolDef == LTO_SYMBOL_DEFINITION_UNDEFINED) {
-      SymbolBodies.push_back(new (Alloc) Undefined(SymName));
+      SymbolBodies.push_back(Symtab->addUndefined(SymName, this, false)->body());
     } else {
       bool Replaceable =
           (SymbolDef == LTO_SYMBOL_DEFINITION_TENTATIVE || // common
            (Attrs & LTO_SYMBOL_COMDAT) ||                  // comdat
            (SymbolDef == LTO_SYMBOL_DEFINITION_WEAK &&     // weak external
             (Attrs & LTO_SYMBOL_ALIAS)));
-      SymbolBodies.push_back(new (Alloc) DefinedBitcode(this, SymName,
-                                                        Replaceable));
+      SymbolBodies.push_back(
+          Symtab->addBitcode(this, SymName, Replaceable)->body());
     }
   }
 
   Directives = M->getLinkerOpts();
 }
 
 MachineTypes BitcodeFile::getMachineType() {
   if (!M)

COFF/MarkLive.cpp

void markLive(const std::vector<Chunk *> &Chunks) {
   auto Enqueue = [&](SectionChunk *C) {
     if (C->isLive())
       return;
     C->markLive();
     Worklist.push_back(C);
   };
 
   // Add GC root chunks.
-  for (Undefined *U : Config->GCRoot)
-    if (auto *D = dyn_cast<DefinedRegular>(U->repl()))
+  for (SymbolBody *B : Config->GCRoot)
+    if (auto *D = dyn_cast<DefinedRegular>(B))
       Enqueue(D->getChunk());
 
   while (!Worklist.empty()) {
     SectionChunk *SC = Worklist.pop_back_val();
     assert(SC->isLive() && "We mark as live when pushing onto the worklist!");
 
     // Mark all symbols listed in the relocation table for this section.
     for (SymbolBody *S : SC->symbols())
-      if (auto *D = dyn_cast<DefinedRegular>(S->repl()))
+      if (auto *D = dyn_cast<DefinedRegular>(S))
         Enqueue(D->getChunk());
 
     // Mark associative sections if any.
     for (SectionChunk *C : SC->children())
       Enqueue(C);
   }
 }
 
 }
 }

COFF/SymbolTable.h

 #include "llvm/Support/raw_ostream.h"
 
 #ifdef _MSC_VER
 // <future> depends on <eh.h> for __uncaught_exception.
 #include <eh.h>
 #endif
 
 #include <future>
+#include <list>
 
 namespace llvm {
 struct LTOCodeGenerator;
 }
 
 namespace lld {
 namespace coff {
 
 class Chunk;
+class CommonChunk;
 class Defined;
 class Lazy;
+class SectionChunk;
 class SymbolBody;
 struct Symbol;
 
 // SymbolTable is a bucket of all known symbols, including defined,
 // 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.
 class SymbolTable {
 public:
   void addFile(std::unique_ptr<InputFile> File);
   std::vector<std::unique_ptr<InputFile>> &getFiles() { return Files; }
   void step();
   void run();
   bool queueEmpty();
 
-  // Print an error message on undefined symbols. If Resolve is true, try to
-  // resolve any undefined symbols and update the symbol table accordingly.
-  void reportRemainingUndefines(bool Resolve);
+  // Try to resolve any undefined symbols and update the symbol table
+  // accordingly, then print an error message for any remaining undefined
+  // symbols.
+  void reportRemainingUndefines();
 
   // Returns a list of chunks of selected symbols.
   std::vector<Chunk *> getChunks();
 
   // Returns a symbol for a given name. Returns a nullptr if not found.
   Symbol *find(StringRef Name);
   Symbol *findUnderscore(StringRef Name);
 
   // Occasionally we have to resolve an undefined symbol to its
   // mangled symbol. This function tries to find a mangled name
   // for U from the symbol table, and if found, set the symbol as
   // a weak alias for U.
-  void mangleMaybe(Undefined *U);
+  void mangleMaybe(SymbolBody *B);
   StringRef findMangle(StringRef Name);
 
   // Print a layout map to OS.
   void printMap(llvm::raw_ostream &OS);
 
   // Build a set of COFF objects representing the combined contents of
   // BitcodeFiles and add them to the symbol table. Called after all files are
   // added and before the writer writes results to a file.
   void addCombinedLTOObjects();
 
   // The writer needs to handle DLL import libraries specially in
   // order to create the import descriptor table.
   std::vector<ImportFile *> ImportFiles;
 
   // The writer needs to infer the machine type from the object files.
   std::vector<ObjectFile *> ObjectFiles;
 
   // Creates an Undefined symbol for a given name.
-  Undefined *addUndefined(StringRef Name);
-  DefinedRelative *addRelative(StringRef Name, uint64_t VA);
-  DefinedAbsolute *addAbsolute(StringRef Name, uint64_t VA);
+  SymbolBody *addUndefined(StringRef Name);
+
+  Symbol *addRelative(StringRef N, uint64_t VA);
+  Symbol *addAbsolute(StringRef N, uint64_t VA);
+
+  Symbol *addUndefined(StringRef Name, InputFile *F, bool IsWeakAlias);
+  void addLazy(ArchiveFile *F, const Archive::Symbol Sym);
+  Symbol *addAbsolute(StringRef N, COFFSymbolRef S);
+  Symbol *addRegular(ObjectFile *F, COFFSymbolRef S, SectionChunk *C);
+  Symbol *addBitcode(BitcodeFile *F, StringRef N, bool IsReplaceable);
+  Symbol *addCommon(ObjectFile *F, COFFSymbolRef S, CommonChunk *C);
+  Symbol *addImportData(StringRef N, ImportFile *F);
+  Symbol *addImportThunk(StringRef Name, DefinedImportData *S,
+                         uint16_t Machine);
+
+  void reportDuplicate(Symbol *Existing, InputFile *NewFile);
 
   // A list of chunks which to be added to .rdata.
   std::vector<Chunk *> LocalImportChunks;
 
 private:
-  void readArchives();
+  void readArchive();
   void readObjects();
 
-  void addSymbol(SymbolBody *New);
-  void addLazy(Lazy *New, std::vector<Symbol *> *Accum);
-  Symbol *insert(SymbolBody *New);
+  std::pair<Symbol *, bool> insert(StringRef Name);
   StringRef findByPrefix(StringRef Prefix);
 
-  void addMemberFile(Lazy *Body);
+  void addMemberFile(ArchiveFile *F, const Archive::Symbol Sym);
   void addCombinedLTOObject(ObjectFile *Obj);
   std::vector<ObjectFile *> createLTOObjects(llvm::LTOCodeGenerator *CG);
 
   llvm::DenseMap<StringRef, Symbol *> Symtab;
 
   std::vector<std::unique_ptr<InputFile>> Files;
-  std::vector<std::future<ArchiveFile *>> ArchiveQueue;
-  std::vector<std::future<InputFile *>> ObjectQueue;
+  std::list<ArchiveFile *> ArchiveQueue;
+  std::vector<InputFile *> ObjectQueue;
 
   std::vector<BitcodeFile *> BitcodeFiles;
   std::vector<SmallString<0>> Objs;
   llvm::BumpPtrAllocator Alloc;
 };
 
+extern SymbolTable *Symtab;
+
 } // namespace coff
 } // namespace lld
 
 #endif

COFF/SymbolTable.cpp

 //===- SymbolTable.cpp ----------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Config.h"
 #include "Driver.h"
 #include "Error.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
-#include "lld/Core/Parallel.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/LTO/LTOCodeGenerator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <utility>
 
 using namespace llvm;
 
 namespace lld {
 namespace coff {
 
-void SymbolTable::addFile(std::unique_ptr<InputFile> FileP) {
-#if LLVM_ENABLE_THREADS
-  std::launch Policy = std::launch::async;
-#else
-  std::launch Policy = std::launch::deferred;
-#endif
+SymbolTable *Symtab;
 
+void SymbolTable::addFile(std::unique_ptr<InputFile> FileP) {
   InputFile *File = FileP.get();
   Files.push_back(std::move(FileP));
   if (auto *F = dyn_cast<ArchiveFile>(File)) {
-    ArchiveQueue.push_back(
-        std::async(Policy, [=]() { F->parse(); return F; }));
+    ArchiveQueue.push_back(F);
     return;
   }
-  ObjectQueue.push_back(
-      std::async(Policy, [=]() { File->parse(); return File; }));
+  ObjectQueue.push_back(File);
   if (auto *F = dyn_cast<ObjectFile>(File)) {
     ObjectFiles.push_back(F);
   } else if (auto *F = dyn_cast<BitcodeFile>(File)) {
     BitcodeFiles.push_back(F);
   } else {
     ImportFiles.push_back(cast<ImportFile>(File));
   }
 }
 
 void SymbolTable::step() {
   if (queueEmpty())
     return;
   readObjects();
-  readArchives();
+  readArchive();
 }
 
 void SymbolTable::run() {
   while (!queueEmpty())
     step();
 }
 
-void SymbolTable::readArchives() {
+void SymbolTable::readArchive() {
   if (ArchiveQueue.empty())
     return;
 
   // Add lazy symbols to the symbol table. Lazy symbols that conflict
   // with existing undefined symbols are accumulated in LazySyms.
-  std::vector<Symbol *> LazySyms;
-  for (std::future<ArchiveFile *> &Future : ArchiveQueue) {
-    ArchiveFile *File = Future.get();
-    if (Config->Verbose)
-      llvm::outs() << "Reading " << File->getShortName() << "\n";
-    for (Lazy &Sym : File->getLazySymbols())
-      addLazy(&Sym, &LazySyms);
-  }
-  ArchiveQueue.clear();
-
-  // Add archive member files to ObjectQueue that should resolve
-  // existing undefined symbols.
-  for (Symbol *Sym : LazySyms)
-    addMemberFile(cast<Lazy>(Sym->Body));
+  ArchiveFile *File = ArchiveQueue.front();
+  ArchiveQueue.pop_front();
+  File->parse();
 }
 
 void SymbolTable::readObjects() {
   if (ObjectQueue.empty())
     return;
 
   // Add defined and undefined symbols to the symbol table.
   std::vector<StringRef> Directives;
   for (size_t I = 0; I < ObjectQueue.size(); ++I) {
-    InputFile *File = ObjectQueue[I].get();
+    InputFile *File = ObjectQueue[I];
     if (Config->Verbose)
       llvm::outs() << "Reading " << File->getShortName() << "\n";
+    File->parse();
     // Adding symbols may add more files to ObjectQueue
     // (but not to ArchiveQueue).
-    for (SymbolBody *Sym : File->getSymbols())
-      if (Sym->isExternal())
-        addSymbol(Sym);
     StringRef S = File->getDirectives();
     if (!S.empty()) {
       Directives.push_back(S);
       if (Config->Verbose)
         llvm::outs() << "Directives: " << File->getShortName()
                      << ": " << S << "\n";
     }
   }
   ObjectQueue.clear();
 
   // Parse directive sections. This may add files to
   // ArchiveQueue and ObjectQueue.
   for (StringRef S : Directives)
     Driver->parseDirectives(S);
 }
 
 bool SymbolTable::queueEmpty() {
   return ArchiveQueue.empty() && ObjectQueue.empty();
 }
 
-void SymbolTable::reportRemainingUndefines(bool Resolve) {
+void SymbolTable::reportRemainingUndefines() {
   llvm::SmallPtrSet<SymbolBody *, 8> Undefs;
   for (auto &I : Symtab) {
     Symbol *Sym = I.second;
-    auto *Undef = dyn_cast<Undefined>(Sym->Body);
+    auto *Undef = dyn_cast<Undefined>(Sym->body());
     if (!Undef)
       continue;
+    if (!Sym->IsUsedInRegularObj)
+      continue;
     StringRef Name = Undef->getName();
     // A weak alias may have been resolved, so check for that.
     if (Defined *D = Undef->getWeakAlias()) {
-      if (Resolve)
-        Sym->Body = D;
+      // We resolve weak aliases by replacing the alias's SymbolBody with the
+      // target's SymbolBody. This causes all SymbolBody pointers referring to
+      // the old symbol to instead refer to the new symbol. However, we can't
+      // just blindly copy sizeof(Symbol::Body) bytes from D to Sym->Body
+      // because D may be an internal symbol, and internal symbols are stored as
+      // "unparented" SymbolBodies. For that reason we need to check which type
+      // of symbol we are dealing with and copy the correct number of bytes.
+      if (isa<DefinedRegular>(D))
+        memcpy(Sym->Body.buffer, D, sizeof(DefinedRegular));
+      else if (isa<DefinedAbsolute>(D))
+        memcpy(Sym->Body.buffer, D, sizeof(DefinedAbsolute));
+      else
+        // No other internal symbols are possible.
+        Sym->Body = D->symbol()->Body;
       continue;
     }
     // If we can resolve a symbol by removing __imp_ prefix, do that.
     // This odd rule is for compatibility with MSVC linker.
     if (Name.startswith("__imp_")) {
       Symbol *Imp = find(Name.substr(strlen("__imp_")));
-      if (Imp && isa<Defined>(Imp->Body)) {
-        if (!Resolve)
-          continue;
-        auto *D = cast<Defined>(Imp->Body);
-        auto *S = new (Alloc) DefinedLocalImport(Name, D);
-        LocalImportChunks.push_back(S->getChunk());
-        Sym->Body = S;
+      if (Imp && isa<Defined>(Imp->body())) {
+        auto *D = cast<Defined>(Imp->body());
+        replaceBody<DefinedLocalImport>(Sym, Name, D);
+        LocalImportChunks.push_back(
+            cast<DefinedLocalImport>(Sym->body())->getChunk());
         continue;
       }
     }
     // Remaining undefined symbols are not fatal if /force is specified.
     // They are replaced with dummy defined symbols.
-    if (Config->Force && Resolve)
-      Sym->Body = new (Alloc) DefinedAbsolute(Name, 0);
-    Undefs.insert(Sym->Body);
+    if (Config->Force)
+      replaceBody<DefinedAbsolute>(Sym, Name, 0);
+    Undefs.insert(Sym->body());
   }
   if (Undefs.empty())
     return;
-  for (Undefined *U : Config->GCRoot)
-    if (Undefs.count(U->repl()))
-      llvm::errs() << "<root>: undefined symbol: " << U->getName() << "\n";
-  for (std::unique_ptr<InputFile> &File : Files)
-    if (!isa<ArchiveFile>(File.get()))
-      for (SymbolBody *Sym : File->getSymbols())
-        if (Undefs.count(Sym->repl()))
-          llvm::errs() << File->getShortName() << ": undefined symbol: "
-                       << Sym->getName() << "\n";
+  for (SymbolBody *B : Config->GCRoot)
+    if (Undefs.count(B))
+      llvm::errs() << "<root>: undefined symbol: " << B->getName() << "\n";
+  for (ObjectFile *File : ObjectFiles)
+      if (Undefs.count(Sym))
+        llvm::errs() << File->getShortName()
+                     << ": undefined symbol: " << Sym->getName() << "\n";
   if (!Config->Force)
     error("Link failed");
 }
 
-void SymbolTable::addLazy(Lazy *New, std::vector<Symbol *> *Accum) {
-  Symbol *Sym = insert(New);
-  if (Sym->Body == New)
-    return;
-  SymbolBody *Existing = Sym->Body;
-  if (isa<Defined>(Existing))
-    return;
-  if (Lazy *L = dyn_cast<Lazy>(Existing))
-    if (L->getFileIndex() < New->getFileIndex())
-      return;
-  Sym->Body = New;
-  New->setBackref(Sym);
-  if (isa<Undefined>(Existing))
-    Accum->push_back(Sym);
+std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
+  Symbol *&Sym = Symtab[Name];
+  if (Sym)
+    return {Sym, false};
+  Sym = new (Alloc) Symbol;
+  Sym->IsUsedInRegularObj = false;
+  return {Sym, true};
+}
+
+Symbol *SymbolTable::addUndefined(StringRef Name, InputFile *F,
+                                  bool IsWeakAlias) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(Name);
+  if (!F || !isa<BitcodeFile>(F))
+    S->IsUsedInRegularObj = true;
+  if (WasInserted || (isa<Lazy>(S->body()) && IsWeakAlias)) {
+    replaceBody<Undefined>(S, Name);
+    return S;
+  }
+  if (auto *L = dyn_cast<Lazy>(S->body()))
+    addMemberFile(L->File, L->Sym);
+  return S;
 }
 
-void SymbolTable::addSymbol(SymbolBody *New) {
-  // Find an existing symbol or create and insert a new one.
-  assert(isa<Defined>(New) || isa<Undefined>(New));
-  Symbol *Sym = insert(New);
-  if (Sym->Body == New)
-    return;
-  SymbolBody *Existing = Sym->Body;
+void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol Sym) {
+  StringRef Name = Sym.getName();
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(Name);
+  if (WasInserted) {
+    replaceBody<Lazy>(S, F, Sym);
+    return;
+  }
+  auto *U = dyn_cast<Undefined>(S->body());
+  if (!U || U->WeakAlias)
+    return;
+  addMemberFile(F, Sym);
+}
+
+void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
+  error(Twine("duplicate symbol: ") + Existing->body()->getDebugName() +
+        " and " + (NewFile ? NewFile->getShortName() : "(internal)"));
+}
+
+Symbol *SymbolTable::addAbsolute(StringRef N, COFFSymbolRef Sym) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(N);
+  S->IsUsedInRegularObj = true;
+  if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
+    replaceBody<DefinedAbsolute>(S, N, Sym);
+  else if (!isa<DefinedCOFF>(S->body()))
+    reportDuplicate(S, nullptr);
+  return S;
+}
 
-  // If we have an undefined symbol and a lazy symbol,
-  // let the lazy symbol to read a member file.
-  if (auto *L = dyn_cast<Lazy>(Existing)) {
-    // Undefined symbols with weak aliases need not to be resolved,
-    // since they would be replaced with weak aliases if they remain
-    // undefined.
-    if (auto *U = dyn_cast<Undefined>(New)) {
-      if (!U->WeakAlias) {
-        addMemberFile(L);
-        return;
-      }
-    }
-    Sym->Body = New;
-    return;
-  }
+Symbol *SymbolTable::addAbsolute(StringRef N, uint64_t VA) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(N);
+  S->IsUsedInRegularObj = true;
+  if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
+    replaceBody<DefinedAbsolute>(S, N, VA);
+  else if (!isa<DefinedCOFF>(S->body()))
+    reportDuplicate(S, nullptr);
+  return S;
+
+Symbol *SymbolTable::addRelative(StringRef N, uint64_t VA) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(N);
+  S->IsUsedInRegularObj = true;
+  if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
+    replaceBody<DefinedRelative>(S, N, VA);
+  else if (!isa<DefinedCOFF>(S->body()))
+    reportDuplicate(S, nullptr);
+  return S;
+
+Symbol *SymbolTable::addRegular(ObjectFile *F, COFFSymbolRef Sym,
+                                SectionChunk *C) {
+  StringRef Name;
+  F->getCOFFObj()->getSymbolName(Sym, Name);
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(Name);
+  S->IsUsedInRegularObj = true;
+  if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
+    replaceBody<DefinedRegular>(S, F, Sym, C);
+  else if (auto *R = dyn_cast<DefinedRegular>(S->body())) {
+    if (!C->isCOMDAT() || !R->isCOMDAT())
+      reportDuplicate(S, F);
+  } else if (auto *B = dyn_cast<DefinedBitcode>(S->body())) {
+    if (B->IsReplaceable)
+      replaceBody<DefinedRegular>(S, F, Sym, C);
+    else if (!C->isCOMDAT())
+      reportDuplicate(S, F);
+  } else
+    replaceBody<DefinedRegular>(S, F, Sym, C);
+  return S;
+}
+
+Symbol *SymbolTable::addBitcode(BitcodeFile *F, StringRef N, bool IsReplaceable) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(N);
+  if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body())) {
+    replaceBody<DefinedBitcode>(S, F, N, IsReplaceable);
+    return S;
+  }
+  if (isa<DefinedCommon>(S->body()))
+    return S;
+  if (IsReplaceable)
+    if (isa<DefinedRegular>(S->body()) || isa<DefinedBitcode>(S->body()))
+      return S;
+  reportDuplicate(S, F);
+  return S;
+}
+
+Symbol *SymbolTable::addCommon(ObjectFile *F, COFFSymbolRef Sym,
+                               CommonChunk *C) {
+  StringRef Name;
+  F->getCOFFObj()->getSymbolName(Sym, Name);
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(Name);
+  S->IsUsedInRegularObj = true;
+  if (WasInserted || !isa<DefinedCOFF>(S->body()))
+    replaceBody<DefinedCommon>(S, F, Sym, C);
+  else if (auto *DC = dyn_cast<DefinedCommon>(S->body()))
+    if (Sym.getValue() > DC->getSize())
+      replaceBody<DefinedCommon>(S, F, Sym, C);
+  return S;
 
-  // 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)
-    error(Twine("duplicate symbol: ") + Existing->getDebugName() + " and " +
-          New->getDebugName());
-  if (Comp < 0)
-    Sym->Body = New;
-}
-
-Symbol *SymbolTable::insert(SymbolBody *New) {
-  Symbol *&Sym = Symtab[New->getName()];
-  if (Sym) {
-    New->setBackref(Sym);
-    return Sym;
-  }
-  Sym = new (Alloc) Symbol(New);
-  New->setBackref(Sym);
-  return Sym;
+Symbol *SymbolTable::addImportData(StringRef N, ImportFile *F) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(N);
+  S->IsUsedInRegularObj = true;
+  if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
+    replaceBody<DefinedImportData>(S, N, F);
+  else if (!isa<DefinedCOFF>(S->body()))
+    reportDuplicate(S, nullptr);
+  return S;
+}
+
+Symbol *SymbolTable::addImportThunk(StringRef Name, DefinedImportData *ID,
+                                    uint16_t Machine) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(Name);
+  S->IsUsedInRegularObj = true;
+  if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
+    replaceBody<DefinedImportThunk>(S, Name, ID, Machine);
+  else if (!isa<DefinedCOFF>(S->body()))
+    reportDuplicate(S, nullptr);
+  return S;
 }
 
 // Reads an archive member file pointed by a given symbol.
-void SymbolTable::addMemberFile(Lazy *Body) {
-  std::unique_ptr<InputFile> File = Body->getMember();
+void SymbolTable::addMemberFile(ArchiveFile *F, const Archive::Symbol Sym) {
+  std::unique_ptr<InputFile> File = F->getMember(&Sym);
 
   // getMember returns an empty buffer if the member was already
   // read from the library.
   if (!File)
     return;
   if (Config->Verbose)
     llvm::outs() << "Loaded " << File->getShortName() << " for "
-                 << Body->getName() << "\n";
+                 << Sym.getName() << "\n";
   addFile(std::move(File));
 }
 
 std::vector<Chunk *> SymbolTable::getChunks() {
   std::vector<Chunk *> Res;
   for (ObjectFile *File : ObjectFiles) {
     std::vector<Chunk *> &V = File->getChunks();
     Res.insert(Res.end(), V.begin(), V.end());
for (auto Pair : Symtab) {
     if (Name.startswith(Prefix))
       return Name;
   }
   return "";
 }
 
 StringRef SymbolTable::findMangle(StringRef Name) {
   if (Symbol *Sym = find(Name))
-    if (!isa<Undefined>(Sym->Body))
+    if (!isa<Undefined>(Sym->body()))
       return Name;
   if (Config->Machine != I386)
     return findByPrefix(("?" + Name + "@@Y").str());
   if (!Name.startswith("_"))
     return "";
   // Search for x86 C function.
   StringRef S = findByPrefix((Name + "@").str());
   if (!S.empty())
     return S;
   // Search for x86 C++ non-member function.
   return findByPrefix(("?" + Name.substr(1) + "@@Y").str());
 }
 
-void SymbolTable::mangleMaybe(Undefined *U) {
-  if (U->WeakAlias)
-    return;
-  if (!isa<Undefined>(U->repl()))
+void SymbolTable::mangleMaybe(SymbolBody *B) {
+  auto *U = dyn_cast<Undefined>(B);
+  if (!U || U->WeakAlias)
     return;
   StringRef Alias = findMangle(U->getName());
   if (!Alias.empty())
     U->WeakAlias = addUndefined(Alias);
 }
 
-Undefined *SymbolTable::addUndefined(StringRef Name) {
-  auto *New = new (Alloc) Undefined(Name);
-  addSymbol(New);
-  if (auto *U = dyn_cast<Undefined>(New->repl()))
-    return U;
-  return New;
-}
-
-DefinedRelative *SymbolTable::addRelative(StringRef Name, uint64_t VA) {
-  auto *New = new (Alloc) DefinedRelative(Name, VA);
-  addSymbol(New);
-  return New;
-}
-
-DefinedAbsolute *SymbolTable::addAbsolute(StringRef Name, uint64_t VA) {
-  auto *New = new (Alloc) DefinedAbsolute(Name, VA);
-  addSymbol(New);
-  return New;
+SymbolBody *SymbolTable::addUndefined(StringRef Name) {
+  return addUndefined(Name, nullptr, false)->body();
 }
 
 void SymbolTable::printMap(llvm::raw_ostream &OS) {
   for (ObjectFile *File : ObjectFiles) {
     OS << File->getShortName() << ":\n";
     for (SymbolBody *Body : File->getSymbols())
       if (auto *R = dyn_cast<DefinedRegular>(Body))
         if (R->getChunk()->isLive())
           OS << Twine::utohexstr(Config->ImageBase + R->getRVA())
              << " " << R->getName() << "\n";
   }
 }
 
-void SymbolTable::addCombinedLTOObject(ObjectFile *Obj) {
-  for (SymbolBody *Body : Obj->getSymbols()) {
-    if (!Body->isExternal())
-      continue;
-    // We should not see any new undefined symbols at this point, but we'll
-    // diagnose them later in reportRemainingUndefines().
-    StringRef Name = Body->getName();
-    Symbol *Sym = insert(Body);
-    SymbolBody *Existing = Sym->Body;
-
-    if (Existing == Body)
-      continue;
-
-    if (isa<DefinedBitcode>(Existing)) {
-      Sym->Body = Body;
-      continue;
-    }
-    if (auto *L = dyn_cast<Lazy>(Existing)) {
-      // We may see new references to runtime library symbols such as __chkstk
-      // here. These symbols must be wholly defined in non-bitcode files.
-      addMemberFile(L);
-      continue;
-    }
-
-    int Comp = Existing->compare(Body);
-    if (Comp == 0)
-      error(Twine("LTO: unexpected duplicate symbol: ") + Name);
-    if (Comp < 0)
-      Sym->Body = Body;
-  }
-}
-
 void SymbolTable::addCombinedLTOObjects() {
   if (BitcodeFiles.empty())
     return;
 
-  // Diagnose any undefined symbols early, but do not resolve weak externals,
-  // as resolution breaks the invariant that each Symbol points to a unique
-  // SymbolBody, which we rely on to replace DefinedBitcode symbols correctly.
-  reportRemainingUndefines(/*Resolve=*/false);
-
   // Create an object file and add it to the symbol table by replacing any
   // DefinedBitcode symbols with the definitions in the object file.
   LTOCodeGenerator CG(BitcodeFile::Context);
   CG.setOptLevel(Config->LTOOptLevel);
   std::vector<ObjectFile *> Objs = createLTOObjects(&CG);
 
-  for (ObjectFile *Obj : Objs)
-    addCombinedLTOObject(Obj);
-
   size_t NumBitcodeFiles = BitcodeFiles.size();
+  for (ObjectFile *Obj : Objs)
+    Obj->parse();
   run();
   if (BitcodeFiles.size() != NumBitcodeFiles)
     error("LTO: late loaded symbol created new bitcode reference");
 }
 
 // Combine and compile bitcode files and then return the result
 // as a vector of regular COFF object files.
 std::vector<ObjectFile *> SymbolTable::createLTOObjects(LTOCodeGenerator *CG) {
-  // All symbols referenced by non-bitcode objects must be preserved.
-  for (ObjectFile *File : ObjectFiles)
-    for (SymbolBody *Body : File->getSymbols())
-      if (auto *S = dyn_cast<DefinedBitcode>(Body->repl()))
-        CG->addMustPreserveSymbol(S->getName());
-
-  // Likewise for bitcode symbols which we initially resolved to non-bitcode.
+  // All symbols referenced by non-bitcode objects, including GC roots, must be
+  // preserved. We must also replace bitcode symbols with undefined symbols so
+  // that they may be replaced with real definitions without conflicting.
   for (BitcodeFile *File : BitcodeFiles)
-    for (SymbolBody *Body : File->getSymbols())
-      if (isa<DefinedBitcode>(Body) && !isa<DefinedBitcode>(Body->repl()))
+    for (SymbolBody *Body : File->getSymbols()) {
+      if (!isa<DefinedBitcode>(Body))
+        continue;
+      if (Body->symbol()->IsUsedInRegularObj)
         CG->addMustPreserveSymbol(Body->getName());
-
-  // Likewise for other symbols that must be preserved.
-  for (Undefined *U : Config->GCRoot) {
-    if (auto *S = dyn_cast<DefinedBitcode>(U->repl()))
-      CG->addMustPreserveSymbol(S->getName());
-    else if (auto *S = dyn_cast_or_null<DefinedBitcode>(U->getWeakAlias()))
-      CG->addMustPreserveSymbol(S->getName());
+      replaceBody<Undefined>(Body->symbol(), Body->getName());
     }
 
   CG->setModule(BitcodeFiles[0]->takeModule());
   for (unsigned I = 1, E = BitcodeFiles.size(); I != E; ++I)
     CG->addModule(BitcodeFiles[I]->takeModule().get());
 
   bool DisableVerify = true;
 #ifdef NDEBUG
   DisableVerify = false;
#endif
   if (!CG->compileOptimized(OSPtrs))
     error(""); // compileOptimized() should have emitted any error message.
 
   std::vector<ObjectFile *> ObjFiles;
   for (SmallString<0> &Obj : Objs) {
     auto *ObjFile = new ObjectFile(MemoryBufferRef(Obj, "<LTO object>"));
     Files.emplace_back(ObjFile);
     ObjectFiles.push_back(ObjFile);
-    ObjFile->parse();
     ObjFiles.push_back(ObjFile);
   }
 
   return ObjFiles;
 }
 
 } // namespace coff
 } // namespace lld

COFF/Symbols.h

 using llvm::object::COFFSymbolRef;
 using llvm::object::coff_import_header;
 using llvm::object::coff_symbol_generic;
 
 class ArchiveFile;
 class BitcodeFile;
 class InputFile;
 class ObjectFile;
-class SymbolBody;
-
-// 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.
-struct Symbol {
-  explicit Symbol(SymbolBody *P) : Body(P) {}
-  SymbolBody *Body;
-};
+struct Symbol;
+class SymbolTable;
 
 // The base class for real symbol classes.
 class SymbolBody {
 public:
   enum Kind {
     // The order of these is significant. We start with the regular defined
     // symbols as those are the most prevelant and the zero tag is the cheapest
     // to set. Among the defined kinds, the lower the kind is preferred over
public:
   Kind kind() const { return static_cast<Kind>(SymbolKind); }
 
   // Returns true if this is an external symbol.
   bool isExternal() { return IsExternal; }
 
   // Returns the symbol name.
   StringRef getName();
 
-  // 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.
-  void setBackref(Symbol *P) { Backref = P; }
-  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);
+  Symbol *symbol();
+  const Symbol *symbol() const {
+    return const_cast<SymbolBody *>(this)->symbol();
+  }
 
   // Returns a name of this symbol including source file name.
   // Used only for debugging and logging.
   std::string getDebugName();
 
 protected:
+  friend SymbolTable;
   explicit SymbolBody(Kind K, StringRef N = "")
       : SymbolKind(K), IsExternal(true), IsCOMDAT(false),
         IsReplaceable(false), Name(N) {}
 
   const unsigned SymbolKind : 8;
   unsigned IsExternal : 1;
 
   // This bit is used by the \c DefinedRegular subclass.
   unsigned IsCOMDAT : 1;
 
   // This bit is used by the \c DefinedBitcode subclass.
   unsigned IsReplaceable : 1;
 
   StringRef Name;
-  Symbol *Backref = nullptr;
 };
 
 // The base class for any defined symbols, including absolute symbols,
 // etc.
 class Defined : public SymbolBody {
 public:
   Defined(Kind K, StringRef N = "") : SymbolBody(K, N) {}
 

 public:
   DefinedCOFF(Kind K, ObjectFile *F, COFFSymbolRef S)
       : Defined(K), File(F), Sym(S.getGeneric()) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() <= LastDefinedCOFFKind;
   }
 
-  int getFileIndex() { return File->Index; }
-
   COFFSymbolRef getCOFFSymbol();
 
 protected:
   ObjectFile *File;
   const coff_symbol_generic *Sym;
 };
 
 // Regular defined symbols read from object file symbol tables.
public:
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedCommonKind;
   }
 
   uint64_t getRVA() { return Data->getRVA(); }
 
 private:
-  friend SymbolBody;
+  friend SymbolTable;
   uint64_t getSize() { return Sym->Value; }
   CommonChunk *Data;
 };
 
 // Absolute symbols.
 class DefinedAbsolute : public Defined {
 public:
   DefinedAbsolute(StringRef N, COFFSymbolRef S)

 // the same name, it will ask the Lazy to load a file.
 class Lazy : public SymbolBody {
 public:
   Lazy(ArchiveFile *F, const Archive::Symbol S)
       : SymbolBody(LazyKind, S.getName()), File(F), Sym(S) {}
 
   static bool classof(const SymbolBody *S) { return S->kind() == LazyKind; }
 
-  // Returns an object file for this symbol, or a nullptr if the file
-  // was already returned.
-  std::unique_ptr<InputFile> getMember();
-
-  int getFileIndex() { return File->Index; }
-
 private:
+  friend SymbolTable;
   ArchiveFile *File;
   const Archive::Symbol Sym;
 };
 
 // Undefined symbols.
 class Undefined : public SymbolBody {
 public:
   explicit Undefined(StringRef N) : SymbolBody(UndefinedKind, N) {}

 // Windows-specific classes.
 
 // This class represents a symbol imported from a DLL. This has two
 // names for internal use and external use. The former is used for
 // name resolution, and the latter is used for the import descriptor
 // table in an output. The former has "__imp_" prefix.
 class DefinedImportData : public Defined {
 public:
-  DefinedImportData(StringRef D, StringRef N, StringRef E,
-                    const coff_import_header *H)
-      : Defined(DefinedImportDataKind, N), DLLName(D), ExternalName(E), Hdr(H) {
+  DefinedImportData(StringRef N, ImportFile *F)
+      : Defined(DefinedImportDataKind, N), File(F) {
   }
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedImportDataKind;
   }
 
-  uint64_t getRVA() { return Location->getRVA(); }
-  StringRef getDLLName() { return DLLName; }
-  StringRef getExternalName() { return ExternalName; }
-  void setLocation(Chunk *AddressTable) { Location = AddressTable; }
-  uint16_t getOrdinal() { return Hdr->OrdinalHint; }
+  uint64_t getRVA() { return File->Location->getRVA(); }
+  StringRef getDLLName() { return File->DLLName; }
+  StringRef getExternalName() { return File->ExternalName; }
+  void setLocation(Chunk *AddressTable) { File->Location = AddressTable; }
+  uint16_t getOrdinal() { return File->Hdr->OrdinalHint; }
 
 private:
-  StringRef DLLName;
-  StringRef ExternalName;
-  const coff_import_header *Hdr;
-  Chunk *Location = nullptr;
+  ImportFile *File;
 };
 
 // This class represents a symbol for a jump table entry which jumps
 // to a function in a DLL. Linker are supposed to create such symbols
 // without "__imp_" prefix for all function symbols exported from
 // DLLs, so that you can call DLL functions as regular functions with
 // a regular name. A function pointer is given as a DefinedImportData.
 class DefinedImportThunk : public Defined {

 // If you have a symbol "__imp_foo" in your object file, a symbol name
 // "foo" becomes automatically available as a pointer to "__imp_foo".
 // This class is for such automatically-created symbols.
 // Yes, this is an odd feature. We didn't intend to implement that.
 // This is here just for compatibility with MSVC.
 class DefinedLocalImport : public Defined {
 public:
   DefinedLocalImport(StringRef N, Defined *S)
-      : Defined(DefinedLocalImportKind, N), Data(S) {}
+      : Defined(DefinedLocalImportKind, N), Data(new LocalImportChunk(S)) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedLocalImportKind;
   }
 
-  uint64_t getRVA() { return Data.getRVA(); }
-  Chunk *getChunk() { return &Data; }
+  uint64_t getRVA() { return Data->getRVA(); }
+  Chunk *getChunk() { return Data.get(); }
 
 private:
-  LocalImportChunk Data;
+  std::unique_ptr<LocalImportChunk> Data;
 };
 
 class DefinedBitcode : public Defined {
   friend SymbolBody;
 public:
   DefinedBitcode(BitcodeFile *F, StringRef N, bool IsReplaceable)
       : Defined(DefinedBitcodeKind, N), File(F) {
+    // IsReplaceable tracks whether the bitcode symbol may be replaced with some
+    // other (defined, common or bitcode) symbol. This is the case for common,
+    // comdat and weak external symbols. We try to replace bitcode symbols with
+    // "real" symbols (see SymbolTable::add{Regular,Bitcode}), and resolve the
+    // result against the real symbol from the combined LTO object.
     this->IsReplaceable = IsReplaceable;
   }
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedBitcodeKind;
   }
 
 private:
case DefinedBitcodeKind:
     llvm_unreachable("There is no address for a bitcode symbol.");
   case LazyKind:
   case UndefinedKind:
     llvm_unreachable("Cannot get the address for an undefined symbol.");
   }
   llvm_unreachable("unknown symbol kind");
 }
 
+// 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 {
+  // True if this symbol was referenced by a regular (non-bitcode) object.
+  unsigned IsUsedInRegularObj : 1;
+
+  // 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.
+  llvm::AlignedCharArrayUnion<DefinedRegular, DefinedCommon, DefinedAbsolute,
+                              DefinedRelative, Lazy, Undefined,
+                              DefinedImportData, DefinedImportThunk,
+                              DefinedLocalImport, DefinedBitcode>
+      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(llvm::AlignOf<T>::Alignment <=
+                    llvm::AlignOf<decltype(S->Body)>::Alignment,
+                "Body not aligned enough");
+  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(isExternal());
+  return reinterpret_cast<Symbol *>(reinterpret_cast<char *>(this) -
+                                    offsetof(Symbol, Body));
+}
+
 } // namespace coff
 } // namespace lld
 
 #endif

COFF/Symbols.cpp

 #include "Error.h"
 #include "InputFiles.h"
 #include "Symbols.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm::object;
-using llvm::sys::fs::identify_magic;
-using llvm::sys::fs::file_magic;
 
 namespace lld {
 namespace coff {
 
 StringRef SymbolBody::getName() {
   // DefinedCOFF names are read lazily for a performance reason.
   // Non-external symbol names are never used by the linker except for logging
   // or debugging. Their internal references are resolved not by name but by
   // symbol index. And because they are not external, no one can refer them by
   // name. Object files contain lots of non-external symbols, and creating
   // StringRefs for them (which involves lots of strlen() on the string table)
   // is a waste of time.
   if (Name.empty()) {
     auto *D = cast<DefinedCOFF>(this);
     D->File->getCOFFObj()->getSymbolName(D->Sym, Name);
   }
   return Name;
 }
 
-// Returns 1, 0 or -1 if this symbol should take precedence
-// over the Other, tie or lose, respectively.
-int SymbolBody::compare(SymbolBody *Other) {
-  Kind LK = kind(), RK = Other->kind();
-
-  // Normalize so that the smaller kind is on the left.
-  if (LK > RK)
-    return -Other->compare(this);
-
-  // First handle comparisons between two different kinds.
-  if (LK != RK) {
-    if (RK > LastDefinedKind) {
-      if (LK == LazyKind && cast<Undefined>(Other)->WeakAlias)
-        return -1;
-
-      // The LHS is either defined or lazy and so it wins.
-      assert((LK <= LastDefinedKind || LK == LazyKind) && "Bad kind!");
-      return 1;
-    }
-
-    // Bitcode has special complexities.
-    if (RK == DefinedBitcodeKind) {
-      auto *RHS = cast<DefinedBitcode>(Other);
-
-      switch (LK) {
-      case DefinedCommonKind:
-        return 1;
-
-      case DefinedRegularKind:
-        // As an approximation, regular symbols win over bitcode symbols,
-        // but we definitely have a conflict if the regular symbol is not
-        // replaceable and neither is the bitcode symbol. We do not
-        // replicate the rest of the symbol resolution logic here; symbol
-        // resolution will be done accurately after lowering bitcode symbols
-        // to regular symbols in addCombinedLTOObject().
-        if (cast<DefinedRegular>(this)->isCOMDAT() || RHS->IsReplaceable)
-          return 1;
-
-        // Fallthrough to the default of a tie otherwise.
-      default:
-        return 0;
-      }
-    }
-
-    // Either of the object file kind will trump a higher kind.
-    if (LK <= LastDefinedCOFFKind)
-      return 1;
-
-    // The remaining kind pairs are ties amongst defined symbols.
-    return 0;
-  }
-
-  // Now handle the case where the kinds are the same.
-  switch (LK) {
-  case DefinedRegularKind: {
-    auto *LHS = cast<DefinedRegular>(this);
-    auto *RHS = cast<DefinedRegular>(Other);
-    if (LHS->isCOMDAT() && RHS->isCOMDAT())
-      return LHS->getFileIndex() < RHS->getFileIndex() ? 1 : -1;
-    return 0;
-  }
-
-  case DefinedCommonKind: {
-    auto *LHS = cast<DefinedCommon>(this);
-    auto *RHS = cast<DefinedCommon>(Other);
-    if (LHS->getSize() == RHS->getSize())
-      return LHS->getFileIndex() < RHS->getFileIndex() ? 1 : -1;
-    return LHS->getSize() > RHS->getSize() ? 1 : -1;
-  }
-
-  case DefinedBitcodeKind: {
-    auto *LHS = cast<DefinedBitcode>(this);
-    auto *RHS = cast<DefinedBitcode>(Other);
-    // If both are non-replaceable, we have a tie.
-    if (!LHS->IsReplaceable && !RHS->IsReplaceable)
-      return 0;
-
-    // Non-replaceable symbols win, but even two replaceable symboles don't
-    // tie. If both symbols are replaceable, choice is arbitrary.
-    if (RHS->IsReplaceable && LHS->IsReplaceable)
-      return uintptr_t(LHS) < uintptr_t(RHS) ? 1 : -1;
-    return LHS->IsReplaceable ? -1 : 1;
-  }
-
-  case LazyKind: {
-    // Don't tie, pick the earliest.
-    auto *LHS = cast<Lazy>(this);
-    auto *RHS = cast<Lazy>(Other);
-    return LHS->getFileIndex() < RHS->getFileIndex() ? 1 : -1;
-  }
-
-  case UndefinedKind: {
-    auto *LHS = cast<Undefined>(this);
-    auto *RHS = cast<Undefined>(Other);
-    // Tie if both undefined symbols have different weak aliases.
-    if (LHS->WeakAlias && RHS->WeakAlias) {
-      if (LHS->WeakAlias->getName() != RHS->WeakAlias->getName())
-        return 0;
-      return uintptr_t(LHS) < uintptr_t(RHS) ? 1 : -1;
-    }
-    return LHS->WeakAlias ? 1 : -1;
-  }
-
-  case DefinedLocalImportKind:
-  case DefinedImportThunkKind:
-  case DefinedImportDataKind:
-  case DefinedAbsoluteKind:
-  case DefinedRelativeKind:
-    // These all simply tie.
-    return 0;
-  }
-  llvm_unreachable("unknown symbol kind");
-}
-
 std::string SymbolBody::getDebugName() {
   std::string N = getName().str();
   if (auto *D = dyn_cast<DefinedCOFF>(this)) {
     N += " ";
     N += D->File->getShortName();
   } else if (auto *D = dyn_cast<DefinedBitcode>(this)) {
     N += " ";
     N += D->File->getShortName();
DefinedImportThunk::DefinedImportThunk(StringRef Name, DefinedImportData *S,
   switch (Machine) {
   case AMD64: Data.reset(new ImportThunkChunkX64(S)); return;
   case I386:  Data.reset(new ImportThunkChunkX86(S)); return;
   case ARMNT: Data.reset(new ImportThunkChunkARM(S)); return;
   default:    llvm_unreachable("unknown machine type");
   }
 }
 
-std::unique_ptr<InputFile> Lazy::getMember() {
-  MemoryBufferRef MBRef = File->getMember(&Sym);
-
-  // getMember returns an empty buffer if the member was already
-  // read from the library.
-  if (MBRef.getBuffer().empty())
-    return std::unique_ptr<InputFile>(nullptr);
-
-  file_magic Magic = identify_magic(MBRef.getBuffer());
-  if (Magic == file_magic::coff_import_library)
-    return std::unique_ptr<InputFile>(new ImportFile(MBRef));
-
-  std::unique_ptr<InputFile> Obj;
-  if (Magic == file_magic::coff_object)
-    Obj.reset(new ObjectFile(MBRef));
-  else if (Magic == file_magic::bitcode)
-    Obj.reset(new BitcodeFile(MBRef));
-  else
-    error(Twine(File->getName()) + ": unknown file type");
-
-  Obj->setParentName(File->getName());
-  return Obj;
-}
-
 Defined *Undefined::getWeakAlias() {
   // A weak alias may be a weak alias to another symbol, so check recursively.
   for (SymbolBody *A = WeakAlias; A; A = cast<Undefined>(A)->WeakAlias)
-    if (auto *D = dyn_cast<Defined>(A->repl()))
+    if (auto *D = dyn_cast<Defined>(A))
       return D;
   return nullptr;
 }
 
 } // namespace coff
 } // namespace lld

COFF/Writer.cpp

void Writer::createMiscChunks() {
   // Create SEH table. x86-only.
   if (Config->Machine != I386)
     return;
   std::set<Defined *> Handlers;
   for (lld::coff::ObjectFile *File : Symtab->ObjectFiles) {
     if (!File->SEHCompat)
       return;
     for (SymbolBody *B : File->SEHandlers)
-      Handlers.insert(cast<Defined>(B->repl()));
+      Handlers.insert(cast<Defined>(B));
   }
   SEHTable.reset(new SEHTableChunk(Handlers));
   createSection(".rdata")->addChunk(SEHTable.get());
 }
 
 // Create .idata section for the DLL-imported symbol table.
 // The format of this section is inherently Windows-specific.
 // IdataContents class abstracted away the details for us,
for (ImportFile *File : Symtab->ImportFiles) {
     }
   }
   if (!Idata.empty()) {
     OutputSection *Sec = createSection(".idata");
     for (Chunk *C : Idata.getChunks())
       Sec->addChunk(C);
   }
   if (!DelayIdata.empty()) {
-    Defined *Helper = cast<Defined>(Config->DelayLoadHelper->repl());
+    Defined *Helper = cast<Defined>(Config->DelayLoadHelper);
     DelayIdata.create(Helper);
     OutputSection *Sec = createSection(".didat");
     for (Chunk *C : DelayIdata.getChunks())
       Sec->addChunk(C);
     Sec = createSection(".data");
     for (Chunk *C : DelayIdata.getDataChunks())
       Sec->addChunk(C);
     Sec = createSection(".text");
size_t Writer::addEntryToStringTable(StringRef Str) {
   assert(Str.size() > COFF::NameSize);
   size_t OffsetOfEntry = Strtab.size() + 4; // +4 for the size field
   Strtab.insert(Strtab.end(), Str.begin(), Str.end());
   Strtab.push_back('\0');
   return OffsetOfEntry;
 }
 
 Optional<coff_symbol16> Writer::createSymbol(Defined *Def) {
+  // Relative symbols are unrepresentable in a COFF symbol table.
+  if (isa<DefinedRelative>(Def))
+    return None;
+
   if (auto *D = dyn_cast<DefinedRegular>(Def))
     if (!D->getChunk()->isLive())
       return None;
 
   coff_symbol16 Sym;
   StringRef Name = Def->getName();
   if (Name.size() > COFF::NameSize) {
     Sym.Name.Offset.Zeroes = 0;
Optional<coff_symbol16> Writer::createSymbol(Defined *Def) {
   } else {
     Sym.Type = IMAGE_SYM_TYPE_NULL;
     Sym.StorageClass = IMAGE_SYM_CLASS_EXTERNAL;
   }
   Sym.NumberOfAuxSymbols = 0;
 
   switch (Def->kind()) {
   case SymbolBody::DefinedAbsoluteKind:
-  case SymbolBody::DefinedRelativeKind:
     Sym.Value = Def->getRVA();
     Sym.SectionNumber = IMAGE_SYM_ABSOLUTE;
     break;
   default: {
     uint64_t RVA = Def->getRVA();
     OutputSection *Sec = nullptr;
     for (OutputSection *S : OutputSections) {
       if (S->getRVA() > RVA)
void Writer::createSymbolAndStringTable() {
   // to be written to the string table. First, construct string table.
   for (OutputSection *Sec : OutputSections) {
     StringRef Name = Sec->getName();
     if (Name.size() <= COFF::NameSize)
       continue;
     Sec->setStringTableOff(addEntryToStringTable(Name));
   }
 
+  std::set<SymbolBody *> SeenSymbols;
   for (lld::coff::ObjectFile *File : Symtab->ObjectFiles)
     for (SymbolBody *B : File->getSymbols())
       if (auto *D = dyn_cast<Defined>(B))
+        if (SeenSymbols.insert(D).second)
           if (Optional<coff_symbol16> Sym = createSymbol(D))
             OutputSymtab.push_back(*Sym);
 
-  for (ImportFile *File : Symtab->ImportFiles)
-    for (SymbolBody *B : File->getSymbols())
-      if (Optional<coff_symbol16> Sym = createSymbol(cast<Defined>(B)))
-        OutputSymtab.push_back(*Sym);
-
   OutputSection *LastSection = OutputSections.back();
   // We position the symbol table to be adjacent to the end of the last section.
   uint64_t FileOff = LastSection->getFileOff() +
                      alignTo(LastSection->getRawSize(), SectorSize);
   if (!OutputSymtab.empty()) {
     PointerToSymbolTable = FileOff;
     FileOff += OutputSymtab.size() * sizeof(coff_symbol16);
   }
template <typename PEHeaderTy> void Writer::writeHeader() {
   PE->MajorOperatingSystemVersion = Config->MajorOSVersion;
   PE->MinorOperatingSystemVersion = Config->MinorOSVersion;
   PE->MajorSubsystemVersion = Config->MajorOSVersion;
   PE->MinorSubsystemVersion = Config->MinorOSVersion;
   PE->Subsystem = Config->Subsystem;
   PE->SizeOfImage = SizeOfImage;
   PE->SizeOfHeaders = SizeOfHeaders;
   if (!Config->NoEntry) {
-    Defined *Entry = cast<Defined>(Config->Entry->repl());
+    Defined *Entry = cast<Defined>(Config->Entry);
     PE->AddressOfEntryPoint = Entry->getRVA();
     // Pointer to thumb code must have the LSB set, so adjust it.
     if (Config->Machine == ARMNT)
       PE->AddressOfEntryPoint |= 1;
   }
   PE->SizeOfStackReserve = Config->StackReserve;
   PE->SizeOfStackCommit = Config->StackCommit;
   PE->SizeOfHeapReserve = Config->HeapReserve;
if (OutputSection *Sec = findSection(".reloc")) {
     Dir[BASE_RELOCATION_TABLE].RelativeVirtualAddress = Sec->getRVA();
     Dir[BASE_RELOCATION_TABLE].Size = Sec->getVirtualSize();
   }
   if (OutputSection *Sec = findSection(".pdata")) {
     Dir[EXCEPTION_TABLE].RelativeVirtualAddress = Sec->getRVA();
     Dir[EXCEPTION_TABLE].Size = Sec->getVirtualSize();
   }
   if (Symbol *Sym = Symtab->findUnderscore("_tls_used")) {
-    if (Defined *B = dyn_cast<Defined>(Sym->Body)) {
+    if (Defined *B = dyn_cast<Defined>(Sym->body())) {
       Dir[TLS_TABLE].RelativeVirtualAddress = B->getRVA();
       Dir[TLS_TABLE].Size = Config->is64()
                                 ? sizeof(object::coff_tls_directory64)
                                 : sizeof(object::coff_tls_directory32);
     }
   }
   if (Symbol *Sym = Symtab->findUnderscore("_load_config_used")) {
-    if (auto *B = dyn_cast<DefinedRegular>(Sym->Body)) {
+    if (auto *B = dyn_cast<DefinedRegular>(Sym->body())) {
       SectionChunk *SC = B->getChunk();
       assert(B->getRVA() >= SC->getRVA());
       uint64_t OffsetInChunk = B->getRVA() - SC->getRVA();
       if (!SC->hasData() || OffsetInChunk + 4 > SC->getSize())
         error("_load_config_used is malformed");
 
       ArrayRef<uint8_t> SecContents = SC->getContents();
       uint32_t LoadConfigSize =
ErrorOr<std::unique_ptr<FileOutputBuffer>> BufferOrErr =
       FileOutputBuffer::create(Path, FileSize, FileOutputBuffer::F_executable);
   error(BufferOrErr, Twine("failed to open ") + Path);
   Buffer = std::move(*BufferOrErr);
 }
 
 void Writer::fixSafeSEHSymbols() {
   if (!SEHTable)
     return;
-  Config->SEHTable->setRVA(SEHTable->getRVA());
-  Config->SEHCount->setVA(SEHTable->getSize() / 4);
+  if (auto *T = dyn_cast<DefinedRelative>(Config->SEHTable->body()))
+    T->setRVA(SEHTable->getRVA());
+  if (auto *C = dyn_cast<DefinedAbsolute>(Config->SEHCount->body()))
+    C->setVA(SEHTable->getSize() / 4);
 }
 
 // Write section contents to a mmap'ed file.
 void Writer::writeSections() {
   uint8_t *Buf = Buffer->getBufferStart();
   for (OutputSection *Sec : OutputSections) {
     uint8_t *SecBuf = Buf + Sec->getFileOff();
     // Fill gaps between functions in .text with INT3 instructions

test/COFF/conflict.test

 # RUN: yaml2obj < %s > %t1.obj
 # RUN: yaml2obj < %s > %t2.obj
 # RUN: not lld-link /out:%t.exe %t1.obj %t2.obj >& %t.log
 # RUN: FileCheck %s < %t.log
 
 # RUN: llvm-as -o %t.lto1.obj %S/Inputs/conflict.ll
 # RUN: llvm-as -o %t.lto2.obj %S/Inputs/conflict.ll
 # RUN: not lld-link /out:%t.exe %t.lto1.obj %t.lto2.obj >& %t.log
 # RUN: FileCheck %s < %t.log
 
-# CHECK: duplicate symbol: foo {{.+}}1.obj and foo {{.+}}2.obj
+# CHECK: duplicate symbol: foo {{.+}}1.obj and {{.+}}2.obj
 
 ---
 header:
   Machine:         IMAGE_FILE_MACHINE_AMD64
   Characteristics: []
 sections:
   - Name:            .text
     Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]

test/COFF/include2.test

 # RUN: yaml2obj < %p/Inputs/include1a.yaml > %t1.obj
 # RUN: yaml2obj < %p/Inputs/include1b.yaml > %t2.obj
 # RUN: yaml2obj < %p/Inputs/include1c.yaml > %t3.obj
 # RUN: rm -f %t2.lib %t3.lib
 # RUN: llvm-ar cru %t2.lib %t2.obj
 # RUN: llvm-ar cru %t3.lib %t3.obj
 # RUN: lld-link /out:%t.exe /entry:main %t1.obj %t2.lib %t3.lib /verbose >& %t.log
 # RUN: FileCheck %s < %t.log
 
 CHECK: include2.test.tmp1.obj
 CHECK: include2.test.tmp2.lib
-CHECK: include2.test.tmp3.lib
 CHECK: include2.test.tmp2.lib(include2.test.tmp2.obj) for foo
+CHECK: include2.test.tmp3.lib
 CHECK: include2.test.tmp3.lib(include2.test.tmp3.obj) for bar

test/COFF/order.test

 # RUN: yaml2obj < %p/Inputs/include1a.yaml > %t1.obj
 # RUN: yaml2obj < %p/Inputs/include1b.yaml > %t2.obj
 # RUN: yaml2obj < %p/Inputs/include1c.yaml > %t3.obj
 # RUN: rm -f %t2.lib %t3.lib
 # RUN: llvm-ar cru %t2.lib %t2.obj
 # RUN: llvm-ar cru %t3.lib %t3.obj
 # RUN: lld-link /out:%t.exe /entry:main \
 # RUN:   %t1.obj %t2.lib %t3.obj %t3.lib /verbose >& %t.log
 # RUN: FileCheck %s < %t.log
 
 CHECK: order.test.tmp1.obj
 CHECK: order.test.tmp3.obj
 CHECK: order.test.tmp2.lib
-CHECK: order.test.tmp3.lib
 CHECK: order.test.tmp2.lib(order.test.tmp2.obj) for foo
+CHECK: order.test.tmp3.lib

test/COFF/symtab.test

 # CHECK-NEXT:     Value: 0
 # CHECK-NEXT:     Section: .data (1)
 # CHECK-NEXT:     BaseType: Null (0x0)
 # CHECK-NEXT:     ComplexType: Null (0x0)
 # CHECK-NEXT:     StorageClass: Static (0x3)
 # CHECK-NEXT:     AuxSymbolCount: 0
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: message
-# CHECK-NEXT:     Value: 6
-# CHECK-NEXT:     Section: .text2 (3)
+# CHECK-NEXT:     Name: MessageBoxA
+# CHECK-NEXT:     Value: 80
+# CHECK-NEXT:     Section: .text (2)
 # CHECK-NEXT:     BaseType: Null (0x0)
 # CHECK-NEXT:     ComplexType: Null (0x0)
-# CHECK-NEXT:     StorageClass: Static (0x3)
+# CHECK-NEXT:     StorageClass: External (0x2)
 # CHECK-NEXT:     AuxSymbolCount: 0
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: main
-# CHECK-NEXT:     Value: 0
+# CHECK-NEXT:     Name: ExitProcess
+# CHECK-NEXT:     Value: 64
 # CHECK-NEXT:     Section: .text (2)
 # CHECK-NEXT:     BaseType: Null (0x0)
 # CHECK-NEXT:     ComplexType: Null (0x0)
 # CHECK-NEXT:     StorageClass: External (0x2)
 # CHECK-NEXT:     AuxSymbolCount: 0
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: caption
-# CHECK-NEXT:     Value: 0
+# CHECK-NEXT:     Name: message
+# CHECK-NEXT:     Value: 6
 # CHECK-NEXT:     Section: .text2 (3)
 # CHECK-NEXT:     BaseType: Null (0x0)
 # CHECK-NEXT:     ComplexType: Null (0x0)
 # CHECK-NEXT:     StorageClass: Static (0x3)
 # CHECK-NEXT:     AuxSymbolCount: 0
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: abs_symbol
-# CHECK-NEXT:     Value: 2662186735
-# CHECK-NEXT:     Section: IMAGE_SYM_ABSOLUTE (-1)
-# CHECK-NEXT:     BaseType: Null (0x0)
-# CHECK-NEXT:     ComplexType: Null (0x0)
-# CHECK-NEXT:     StorageClass: External (0x2)
-# CHECK-NEXT:     AuxSymbolCount: 0
-# CHECK-NEXT:   }
-# CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: __imp_ExitProcess
-# CHECK-NEXT:     Value: 64
-# CHECK-NEXT:     Section: .idata (4)
-# CHECK-NEXT:     BaseType: Null (0x0)
-# CHECK-NEXT:     ComplexType: Null (0x0)
-# CHECK-NEXT:     StorageClass: External (0x2)
-# CHECK-NEXT:     AuxSymbolCount: 0
-# CHECK-NEXT:   }
-# CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: ExitProcess
-# CHECK-NEXT:     Value: 64
+# CHECK-NEXT:     Name: main
+# CHECK-NEXT:     Value: 0
 # CHECK-NEXT:     Section: .text (2)
 # CHECK-NEXT:     BaseType: Null (0x0)
 # CHECK-NEXT:     ComplexType: Null (0x0)
 # CHECK-NEXT:     StorageClass: External (0x2)
 # CHECK-NEXT:     AuxSymbolCount: 0
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: __imp_MessageBoxA
-# CHECK-NEXT:     Value: 72
-# CHECK-NEXT:     Section: .idata (4)
+# CHECK-NEXT:     Name: caption
+# CHECK-NEXT:     Value: 0
+# CHECK-NEXT:     Section: .text2 (3)
 # CHECK-NEXT:     BaseType: Null (0x0)
 # CHECK-NEXT:     ComplexType: Null (0x0)
-# CHECK-NEXT:     StorageClass: External (0x2)
+# CHECK-NEXT:     StorageClass: Static (0x3)
 # CHECK-NEXT:     AuxSymbolCount: 0
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: MessageBoxA
-# CHECK-NEXT:     Value: 80
-# CHECK-NEXT:     Section: .text (2)
+# CHECK-NEXT:     Name: abs_symbol
+# CHECK-NEXT:     Value: 2662186735
+# CHECK-NEXT:     Section: IMAGE_SYM_ABSOLUTE (-1)
 # CHECK-NEXT:     BaseType: Null (0x0)
 # CHECK-NEXT:     ComplexType: Null (0x0)
 # CHECK-NEXT:     StorageClass: External (0x2)
 # CHECK-NEXT:     AuxSymbolCount: 0
 # CHECK-NEXT:   }
 # CHECK-NEXT: ]
 
 # NO: Symbols [