COFF: Load inputs immediately instead of adding them to a queue.

[pcc]

Summary

This patch replaces the symbol table's object and archive queues, as well as
the convergent loop in the linker driver, with a design more similar to the
ELF linker where symbol resolution directly causes input files to be added to
the link, including input files arising from linker directives. Effectively
this removes the last vestiges of the old parallel input file loader.

[ruiu]

I think this changes the order how object files in archive files are resolved. Can you still link Chromium?

[pcc]

Yes, I verified that "ninja All" succeeds after this patch.

[ruiu]

LGTM

lld/COFF/SymbolTable.cpp

36–37

You can assign to MT unconditionally.

lld/COFF/SymbolTable.h

24

I believe you can remove this include.

lld/COFF/Driver.cpp

auto NotResource = [](MemoryBufferRef MB) {
     return identify_magic(MB.getBuffer()) != file_magic::windows_resource;
   };
   auto It = std::stable_partition(MBs.begin(), MBs.end(), NotResource);
   if (It != MBs.end()) {
     Resources.insert(Resources.end(), It, MBs.end());
     MBs.erase(It, MBs.end());
   }
 
-  // Read all input files given via the command line. Note that step()
-  // doesn't read files that are specified by directive sections.
+  // Read all input files given via the command line.
   for (MemoryBufferRef MB : MBs)
     Symtab.addFile(createFile(MB));
-  Symtab.step();
 
-  // Determine machine type and check if all object files are
-  // for the same CPU type. Note that this needs to be done before
-  // any call to mangle().
-  for (InputFile *File : Symtab.getFiles()) {
-    MachineTypes MT = File->getMachineType();
-    if (MT == IMAGE_FILE_MACHINE_UNKNOWN)
-      continue;
-    if (Config->Machine == IMAGE_FILE_MACHINE_UNKNOWN) {
-      Config->Machine = MT;
-      continue;
-    }
-    if (Config->Machine != MT)
-      fatal(toString(File) + ": machine type " + machineToStr(MT) +
-            " conflicts with " + machineToStr(Config->Machine));
-  }
+  // We should have inferred a machine type by now from the input files, but if
+  // not we assume x64.
   if (Config->Machine == IMAGE_FILE_MACHINE_UNKNOWN) {
     errs() << "warning: /machine is not specified. x64 is assumed.\n";
     Config->Machine = AMD64;
   }
 
   // Windows specific -- Convert Windows resource files to a COFF file.
   if (!Resources.empty()) {
     std::unique_ptr<MemoryBuffer> MB = convertResToCOFF(Resources);
void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
   }
 
   // We do not support /guard:cf (control flow protection) yet.
   // Define CFG symbols anyway so that we can link MSVC 2015 CRT.
   Symtab.addAbsolute(mangle("__guard_fids_table"), 0);
   Symtab.addAbsolute(mangle("__guard_fids_count"), 0);
   Symtab.addAbsolute(mangle("__guard_flags"), 0x100);
 
-  // Read as much files as we can from directives sections.
-  Symtab.run();
-
-  // Resolve auxiliary symbols until we get a convergence.
-  // (Trying to resolve a symbol may trigger a Lazy symbol to load a new file.
-  // A new file may contain a directive section to add new command line options.
-  // That's why we have to repeat until converge.)
-  for (;;) {
-    // Windows specific -- if entry point is not found,
-    // search for its mangled names.
-    if (Config->Entry)
-      Symtab.mangleMaybe(Config->Entry);
 
-    // Windows specific -- Make sure we resolve all dllexported symbols.
-    for (Export &E : Config->Exports) {
-      if (!E.ForwardTo.empty())
-        continue;
-      E.Sym = addUndefined(E.Name);
-      if (!E.Directives)
-        Symtab.mangleMaybe(E.Sym);
-    }
 
-    // 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 (!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();
 
   // Windows specific -- if no /subsystem is given, we need to infer

lld/COFF/SymbolTable.h

 #include "llvm/Support/Allocator.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 {

 // 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 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(InputFile *File);
-  std::vector<InputFile *> &getFiles() { return Files; }
-  void step();
-  void run();
-  bool queueEmpty();
 
   // 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();
private:
   StringRef findByPrefix(StringRef Prefix);
 
   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<InputFile *> Files;
-  std::list<ArchiveFile *> ArchiveQueue;
-  std::vector<InputFile *> ObjectQueue;
-
   std::vector<BitcodeFile *> BitcodeFiles;
   std::vector<SmallString<0>> Objs;
 };
 
 extern SymbolTable *Symtab;
 
 } // namespace coff
 } // namespace lld
 
 #endif

lld/COFF/SymbolTable.cpp

 using namespace llvm;
 
 namespace lld {
 namespace coff {
 
 SymbolTable *Symtab;
 
 void SymbolTable::addFile(InputFile *File) {
-  Files.push_back(File);
-  if (auto *F = dyn_cast<ArchiveFile>(File)) {
-    ArchiveQueue.push_back(F);
-    return;
+  if (Config->Verbose)
+    outs() << "Reading " << toString(File) << "\n";
+  File->parse();
+
+  MachineTypes MT = File->getMachineType();
+  if (Config->Machine == IMAGE_FILE_MACHINE_UNKNOWN) {
+    if (MT != IMAGE_FILE_MACHINE_UNKNOWN)
+      Config->Machine = MT;
+  } else if (MT != IMAGE_FILE_MACHINE_UNKNOWN && Config->Machine != MT) {
+    fatal(toString(File) + ": machine type " + machineToStr(MT) +
+          " conflicts with " + machineToStr(Config->Machine));
   }
-  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));
-  }
+  } else if (auto *F = dyn_cast<ImportFile>(File)) {
+    ImportFiles.push_back(F);
   }
 
-void SymbolTable::step() {
-  if (queueEmpty())
-    return;
-  readObjects();
-  readArchive();
-}
-
-void SymbolTable::run() {
-  while (!queueEmpty())
-    step();
-}
-
-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.
-  ArchiveFile *File = ArchiveQueue.front();
-  ArchiveQueue.pop_front();
-  if (Config->Verbose)
-    outs() << "Reading " << toString(File) << "\n";
-  File->parse();
-}
-
-void SymbolTable::readObjects() {
-  if (ObjectQueue.empty())
+  StringRef S = File->getDirectives();
+  if (S.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];
-    if (Config->Verbose)
-      outs() << "Reading " << toString(File) << "\n";
-    File->parse();
-    // Adding symbols may add more files to ObjectQueue
-    // (but not to ArchiveQueue).
-    StringRef S = File->getDirectives();
-    if (!S.empty()) {
-      Directives.push_back(S);
-      if (Config->Verbose)
-        outs() << "Directives: " << toString(File) << ": " << 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() {
   SmallPtrSet<SymbolBody *, 8> Undefs;
   for (auto &I : Symtab) {
     Symbol *Sym = I.second;
     auto *Undef = dyn_cast<Undefined>(Sym->body());
     if (!Undef)
       continue;
     if (!Sym->IsUsedInRegularObj)
void SymbolTable::addCombinedLTOObjects() {
   // DefinedBitcode symbols with the definitions in the object file.
   LTOCodeGenerator CG(BitcodeFile::Context);
   CG.setOptLevel(Config->LTOOptLevel);
   std::vector<ObjectFile *> Objs = createLTOObjects(&CG);
 
   size_t NumBitcodeFiles = BitcodeFiles.size();
   for (ObjectFile *Obj : Objs)
     Obj->parse();
-  run();
   if (BitcodeFiles.size() != NumBitcodeFiles)
     fatal("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, including GC roots, must be
#endif
   }
 
   if (!CG->compileOptimized(OSPtrs))
     fatal(""); // 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);
     ObjFiles.push_back(ObjFile);
   }
 
   return ObjFiles;
 }
 
 } // namespace coff
 } // namespace lld

lld/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.tmp2.lib(order.test.tmp2.obj) for foo
+CHECK: order.test.tmp3.obj
 CHECK: order.test.tmp3.lib