COFF: Open and map input files asynchronously on Windows.

[pcc]

Summary

Profiling revealed that the majority of lld's execution time on Windows was
spent opening and mapping input files. We can reduce this cost significantly
by performing these operations asynchronously.

This change introduces a queue for all operations on input file data. When
we discover that we need to load a file (for example, when we find a lazy
archive for an undefined symbol, or when we read a linker directive to
load a file from disk), the file operation is launched using a future and
the symbol resolution operation is enqueued. This implies another change
to symbol resolution semantics, but it seems to be harmless ("ninja All"
in Chromium still succeeds).

To measure the perf impact of this change I linked Chromium's chrome_child.dll
with both thin and fat archives.

Thin archives:

Before (median of 5 runs): 19.50s
After: 10.93s

Fat archives:

Before: 12.00s
After: 9.90s

On Linux I found that doing this asynchronously had a negative effect on
performance, probably because the cost of mapping a file is small enough that
it becomes outweighed by the cost of managing the futures. So on non-Windows
platforms I use the deferred execution strategy.

[ruiu]

Which is actually slow, open or mmap? My wild guess is that mmap is slow. If so, can we open a file to get an error early and then mmap? It will simplify std::future<MBErrPair> to std::future<MemoryBuffer>.

lld/COFF/Driver.cpp

794 ↗

(On Diff #81422)

Is this enough to run this only once? In the above code we repeat until converge.

lld/COFF/InputFiles.h

86 ↗

(On Diff #81422)

Update comment.

[pcc]

In D27768#622639, @ruiu wrote:

Which is actually slow, open or mmap?

The MSVC profiler took 7510 "samples" inside getOpenFileImpl (which just maps the file) as compared to 7683 inside getFileAux (which opens the file then calls getOpenFileImpl).

My wild guess is that mmap is slow. If so, can we open a file to get an error early and then mmap? It will simplify std::future<MBErrPair> to std::future<MemoryBuffer>.

That's a good point, I'll do that. Although we could fail to map the file, it's probably fine to exit on the thread since that's less likely than open failing.

lld/COFF/Driver.cpp

794 ↗

(On Diff #81422)

We would only need to run addCombinedLTOObjects again if the native COFF file contained a compiler-generated reference to a bitcode symbol. This is unlikely to occur in the COFF linker because the compiler will generally only create references to the runtime library, which of course MSVC ships as regular object files. We previously tried to handle that situation by reporting an error (see SymbolTable.cpp:380 in the old code), but that code was untested. I didn't think it was worth it to preserve the error as this is basically a "don't care" situation, but I guess it wouldn't be too hard to do that and write a test.

lld/COFF/InputFiles.h

86 ↗

(On Diff #81422)

Will do.

[pcc]

• Only map the file asynchronously

[pcc]

In D27768#622969, @pcc wrote:

That's a good point, I'll do that. Although we could fail to map the file, it's probably fine to exit on the thread since that's less likely than open failing.

Done. Although the code certainly looks cleaner, now that I've thought about it more I'm not sure whether it's a good idea. Since we now leave file descriptors open for a longer period of time, we may become liable to exceeding limits on the number of open file descriptors, whereas with the previous patch a reasonable implementation of std::future would limit the number of concurrent tasks and hence the number of open file descriptors. I guess one way to avoid that could be to dequeue tasks once we reach a predefined size limit. That would make the behavior a little harder to reason about though.

That said, the new latency numbers are: fat archives 9.85s, thin archives 11.08s. Which seems reasonable to me.

[ruiu]

I don't know for sure, but I guess that resources associated with a file descriptor are freed when all references to the descriptor is released. If you mmap a file descriptor and close it, that close is at the moment almost no-op (except it decrements a kernel internal counter by one), and the resources associated with it will be released when you munmap, no?

[pcc]

In D27768#623208, @ruiu wrote:

I don't know for sure, but I guess that resources associated with a file descriptor are freed when all references to the descriptor is released. If you mmap a file descriptor and close it, that close is at the moment almost no-op (except it decrements a kernel internal counter by one), and the resources associated with it will be released when you munmap, no?

I don't think that's quite right on Windows. According to [0], on Windows file descriptors are distinct from, and a more limited resource as compared to, OS-level handles (the default limit on the number of file descriptors is 512, and it's possible to increase it to up to 2048; OS-level handles are effectively unlimited). Until now we have only been using file descriptors ephemerally (on Windows MemoryBuffer::getFile will create a handle, create a descriptor from that, extract the handle from the descriptor to map the file and finally close the descriptor), so this hasn't been a problem before. But now descriptors can potentially live much longer.

All of that suggests a cleaner fix: change LLVM's MemoryBuffer API so that it uses handles on Windows. That's probably way outside of the scope of this patch, though. Perhaps we can go back to the earlier version with a FIXME?

[0] http://stackoverflow.com/questions/870173/is-there-a-limit-on-number-of-open-files-in-windows

[ruiu]

Sure. I'm fine in either way. LGTM.

[pcc]

Thanks, I went with the previous approach with a FIXME.

lld/trunk/COFF/Driver.h

 #define LLD_COFF_DRIVER_H
 
 #include "Config.h"
 #include "SymbolTable.h"
 #include "lld/Core/LLVM.h"
 #include "lld/Core/Reproduce.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Object/Archive.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Option/Arg.h"
 #include "llvm/Option/ArgList.h"
 #include <memory>
 #include <set>
 #include <vector>
 
 namespace lld {

 class LinkerDriver {
 public:
   LinkerDriver() { coff::Symtab = &Symtab; }
   void link(llvm::ArrayRef<const char *> Args);
 
   // Used by the resolver to parse .drectve section contents.
   void parseDirectives(StringRef S);
 
-  std::unique_ptr<CpioFile> Cpio; // for /linkrepro
+  // Used by ArchiveFile to enqueue members.
+  void enqueueArchiveMember(const Archive::Child &C, StringRef SymName,
+                            StringRef ParentName);
 
 private:
   ArgParser Parser;
   SymbolTable Symtab;
 
+  std::unique_ptr<CpioFile> Cpio; // for /linkrepro
+
   // Opens a file. Path has to be resolved already.
   MemoryBufferRef openFile(StringRef Path);
 
   // Searches a file from search paths.
   Optional<StringRef> findFile(StringRef Filename);
   Optional<StringRef> findLib(StringRef Filename);
   StringRef doFindFile(StringRef Filename);
   StringRef doFindLib(StringRef Filename);
private:
   // 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
   // entry point name.
   StringRef findDefaultEntry();
   WindowsSubsystem inferSubsystem();
 
+  MemoryBufferRef takeBuffer(std::unique_ptr<MemoryBuffer> MB);
+  void addBuffer(std::unique_ptr<MemoryBuffer> MB);
+  void addArchiveBuffer(MemoryBufferRef MBRef, StringRef SymName,
+                        StringRef ParentName);
+
+  void enqueuePath(StringRef Path);
+
+  void enqueueTask(std::function<void()> Task);
+  bool run();
+
   // Driver is the owner of all opened files.
   // InputFiles have MemoryBufferRefs to them.
   std::vector<std::unique_ptr<MemoryBuffer>> OwningMBs;
+
+  std::list<std::function<void()>> TaskQueue;
+  std::vector<StringRef> FilePaths;
+  std::vector<MemoryBufferRef> Resources;
 };
 
 void parseModuleDefs(MemoryBufferRef MB);
 void writeImportLibrary();
 
 // Functions below this line are defined in DriverUtils.cpp.
 
 void printHelp(const char *Argv0);

lld/trunk/COFF/Driver.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Process.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <memory>
 
+#ifdef _MSC_VER
+// <future> depends on <eh.h> for __uncaught_exception.
+#include <eh.h>
+#endif
+
+#include <future>
+
 using namespace llvm;
 using namespace llvm::COFF;
 using llvm::sys::Process;
 using llvm::sys::fs::OpenFlags;
 using llvm::sys::fs::file_magic;
 using llvm::sys::fs::identify_magic;
 
 namespace lld {

 // Drop directory components and replace extension with ".exe" or ".dll".
 static std::string getOutputPath(StringRef Path) {
   auto P = Path.find_last_of("\\/");
   StringRef S = (P == StringRef::npos) ? Path : Path.substr(P + 1);
   const char* E = Config->DLL ? ".dll" : ".exe";
   return (S.substr(0, S.rfind('.')) + E).str();
 }
 
-// Opens a file. Path has to be resolved already.
-// Newly created memory buffers are owned by this driver.
-MemoryBufferRef LinkerDriver::openFile(StringRef Path) {
-  std::unique_ptr<MemoryBuffer> MB =
-      check(MemoryBuffer::getFile(Path), "could not open " + Path);
-  MemoryBufferRef MBRef = MB->getMemBufferRef();
-  OwningMBs.push_back(std::move(MB)); // take ownership
+// ErrorOr is not default constructible, so it cannot be used as the type
+// parameter of a future.
+// FIXME: We could open the file in createFutureForFile and avoid needing to
+// return an error here, but for the moment that would cost us a file descriptor
+// (a limited resource on Windows) for the duration that the future is pending.
+typedef std::pair<std::unique_ptr<MemoryBuffer>, std::error_code> MBErrPair;
+
+// Create a std::future that opens and maps a file using the best strategy for
+// the host platform.
+static std::future<MBErrPair> createFutureForFile(std::string Path) {
+#if LLVM_ON_WIN32
+  // On Windows, file I/O is relatively slow so it is best to do this
+  // asynchronously.
+  auto Strategy = std::launch::async;
+#else
+  auto Strategy = std::launch::deferred;
+#endif
+  return std::async(Strategy, [=]() {
+    auto MBOrErr = MemoryBuffer::getFile(Path);
+    if (!MBOrErr)
+      return MBErrPair{nullptr, MBOrErr.getError()};
+    return MBErrPair{std::move(*MBOrErr), std::error_code()};
+  });
+}
+
+MemoryBufferRef LinkerDriver::takeBuffer(std::unique_ptr<MemoryBuffer> MB) {
+  MemoryBufferRef MBRef = *MB;
+  OwningMBs.push_back(std::move(MB));
+
+  if (Driver->Cpio)
+    Driver->Cpio->append(relativeToRoot(MBRef.getBufferIdentifier()),
+                         MBRef.getBuffer());
+
   return MBRef;
 }
 
-static InputFile *createFile(MemoryBufferRef MB) {
-  if (Driver->Cpio)
-    Driver->Cpio->append(relativeToRoot(MB.getBufferIdentifier()),
-                         MB.getBuffer());
+void LinkerDriver::addBuffer(std::unique_ptr<MemoryBuffer> MB) {
+  MemoryBufferRef MBRef = takeBuffer(std::move(MB));
 
   // File type is detected by contents, not by file extension.
-  file_magic Magic = identify_magic(MB.getBuffer());
+  file_magic Magic = identify_magic(MBRef.getBuffer());
+  if (Magic == file_magic::windows_resource) {
+    Resources.push_back(MBRef);
+    return;
+  }
+
+  FilePaths.push_back(MBRef.getBufferIdentifier());
   if (Magic == file_magic::archive)
-    return make<ArchiveFile>(MB);
+    return Symtab.addFile(make<ArchiveFile>(MBRef));
   if (Magic == file_magic::bitcode)
-    return make<BitcodeFile>(MB);
+    return Symtab.addFile(make<BitcodeFile>(MBRef));
   if (Magic == file_magic::coff_cl_gl_object)
-    fatal(MB.getBufferIdentifier() + ": is not a native COFF file. "
+    fatal(MBRef.getBufferIdentifier() + ": is not a native COFF file. "
           "Recompile without /GL");
+  Symtab.addFile(make<ObjectFile>(MBRef));
+}
+
+void LinkerDriver::enqueuePath(StringRef Path) {
+  auto Future =
+      std::make_shared<std::future<MBErrPair>>(createFutureForFile(Path));
+  std::string PathStr = Path;
+  enqueueTask([=]() {
+    auto MBOrErr = Future->get();
+    if (MBOrErr.second)
+      fatal(MBOrErr.second, "could not open " + PathStr);
+    Driver->addBuffer(std::move(MBOrErr.first));
+  });
+
   if (Config->OutputFile == "")
-    Config->OutputFile = getOutputPath(MB.getBufferIdentifier());
-  return make<ObjectFile>(MB);
+    Config->OutputFile = getOutputPath(Path);
+}
+
+void LinkerDriver::addArchiveBuffer(MemoryBufferRef MB, StringRef SymName,
+                                    StringRef ParentName) {
+  file_magic Magic = identify_magic(MB.getBuffer());
+  if (Magic == file_magic::coff_import_library) {
+    Symtab.addFile(make<ImportFile>(MB));
+    return;
+  }
+
+  InputFile *Obj;
+  if (Magic == file_magic::coff_object)
+    Obj = make<ObjectFile>(MB);
+  else if (Magic == file_magic::bitcode)
+    Obj = make<BitcodeFile>(MB);
+  else
+    fatal("unknown file type: " + MB.getBufferIdentifier());
+
+  Obj->ParentName = ParentName;
+  Symtab.addFile(Obj);
+  if (Config->Verbose)
+    outs() << "Loaded " << toString(Obj) << " for " << SymName << "\n";
+}
+
+void LinkerDriver::enqueueArchiveMember(const Archive::Child &C,
+                                        StringRef SymName,
+                                        StringRef ParentName) {
+  if (!C.getParent()->isThin()) {
+    MemoryBufferRef MB = check(
+        C.getMemoryBufferRef(),
+        "could not get the buffer for the member defining symbol " + SymName);
+    enqueueTask([=]() { Driver->addArchiveBuffer(MB, SymName, ParentName); });
+    return;
+  }
+
+  auto Future = std::make_shared<std::future<MBErrPair>>(createFutureForFile(
+      check(C.getFullName(),
+            "could not get the filename for the member defining symbol " +
+                SymName)));
+  enqueueTask([=]() {
+    auto MBOrErr = Future->get();
+    if (MBOrErr.second)
+      fatal(MBOrErr.second,
+            "could not get the buffer for the member defining " + SymName);
+    Driver->addArchiveBuffer(takeBuffer(std::move(MBOrErr.first)), SymName,
+                             ParentName);
+  });
 }
 
 static bool isDecorated(StringRef Sym) {
   return Sym.startswith("_") || Sym.startswith("@") || Sym.startswith("?");
 }
 
 // Parses .drectve section contents and returns a list of files
 // specified by /defaultlib.
 void LinkerDriver::parseDirectives(StringRef S) {
   opt::InputArgList Args = Parser.parse(S);
 
   for (auto *Arg : Args) {
     switch (Arg->getOption().getID()) {
     case OPT_alternatename:
       parseAlternateName(Arg->getValue());
       break;
     case OPT_defaultlib:
-      if (Optional<StringRef> Path = findLib(Arg->getValue())) {
-        MemoryBufferRef MB = openFile(*Path);
-        Symtab.addFile(createFile(MB));
-      }
+      if (Optional<StringRef> Path = findLib(Arg->getValue()))
+        enqueuePath(*Path);
       break;
     case OPT_export: {
       Export E = parseExport(Arg->getValue());
       E.Directives = true;
       Config->Exports.push_back(E);
       break;
     }
     case OPT_failifmismatch:

 
 static uint64_t getDefaultImageBase() {
   if (Config->is64())
     return Config->DLL ? 0x180000000 : 0x140000000;
   return Config->DLL ? 0x10000000 : 0x400000;
 }
 
 static std::string createResponseFile(const opt::InputArgList &Args,
-                                      ArrayRef<MemoryBufferRef> MBs,
+                                      ArrayRef<StringRef> FilePaths,
                                       ArrayRef<StringRef> SearchPaths) {
   SmallString<0> Data;
   raw_svector_ostream OS(Data);
 
   for (auto *Arg : Args) {
     switch (Arg->getOption().getID()) {
     case OPT_linkrepro:
     case OPT_INPUT:
     case OPT_defaultlib:
     case OPT_libpath:
       break;
     default:
       OS << stringize(Arg) << "\n";
     }
   }
 
   for (StringRef Path : SearchPaths) {
     std::string RelPath = relativeToRoot(Path);
     OS << "/libpath:" << quote(RelPath) << "\n";
   }
 
-  for (MemoryBufferRef MB : MBs) {
-    std::string InputPath = relativeToRoot(MB.getBufferIdentifier());
-    OS << quote(InputPath) << "\n";
-  }
+  for (StringRef Path : FilePaths)
+    OS << quote(relativeToRoot(Path)) << "\n";
 
   return Data.str();
 }
 
 static unsigned getDefaultDebugType(const opt::InputArgList &Args) {
   unsigned DebugTypes = static_cast<unsigned>(DebugType::CV);
   if (Args.hasArg(OPT_driver))
     DebugTypes |= static_cast<unsigned>(DebugType::PData);
static std::string getMapFile(const opt::InputArgList &Args) {
   if (Arg->getOption().getID() == OPT_lldmap_file)
     return Arg->getValue();
 
   assert(Arg->getOption().getID() == OPT_lldmap);
   StringRef OutFile = Config->OutputFile;
   return (OutFile.substr(0, OutFile.rfind('.')) + ".map").str();
 }
 
+void LinkerDriver::enqueueTask(std::function<void()> Task) {
+  TaskQueue.push_back(std::move(Task));
+}
+
+bool LinkerDriver::run() {
+  bool DidWork = !TaskQueue.empty();
+  while (!TaskQueue.empty()) {
+    TaskQueue.front()();
+    TaskQueue.pop_front();
+  }
+  return DidWork;
+}
+
 void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
   // If the first command line argument is "/lib", link.exe acts like lib.exe.
   // We call our own implementation of lib.exe that understands bitcode files.
   if (ArgsArr.size() > 1 && StringRef(ArgsArr[1]).equals_lower("/lib")) {
     if (llvm::libDriverMain(ArgsArr.slice(1)) != 0)
       fatal("lib failed");
     return;
   }
if (Args.hasArg(OPT_tsaware_no))
     Config->TerminalServerAware = false;
   if (Args.hasArg(OPT_nosymtab))
     Config->WriteSymtab = false;
   Config->DumpPdb = Args.hasArg(OPT_dumppdb);
   Config->DebugPdb = Args.hasArg(OPT_debugpdb);
 
   // Create a list of input files. Files can be given as arguments
   // for /defaultlib option.
-  std::vector<StringRef> Paths;
   std::vector<MemoryBufferRef> MBs;
   for (auto *Arg : Args.filtered(OPT_INPUT))
     if (Optional<StringRef> Path = findFile(Arg->getValue()))
-      Paths.push_back(*Path);
+      enqueuePath(*Path);
   for (auto *Arg : Args.filtered(OPT_defaultlib))
     if (Optional<StringRef> Path = findLib(Arg->getValue()))
-      Paths.push_back(*Path);
-  for (StringRef Path : Paths)
-    MBs.push_back(openFile(Path));
+      enqueuePath(*Path);
 
   // Windows specific -- Create a resource file containing a manifest file.
-  if (Config->Manifest == Configuration::Embed) {
-    std::unique_ptr<MemoryBuffer> MB = createManifestRes();
-    MBs.push_back(MB->getMemBufferRef());
-    OwningMBs.push_back(std::move(MB)); // take ownership
-  }
-
-  // Windows specific -- Input files can be Windows resource files (.res files).
-  // We invoke cvtres.exe to convert resource files to a regular COFF file
-  // then link the result file normally.
-  std::vector<MemoryBufferRef> Resources;
-  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());
-  }
+  if (Config->Manifest == Configuration::Embed)
+    addBuffer(createManifestRes());
 
   // Read all input files given via the command line.
-  for (MemoryBufferRef MB : MBs)
-    Symtab.addFile(createFile(MB));
+  run();
 
   // 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);
-    Symtab.addFile(createFile(MB->getMemBufferRef()));
-
-    MBs.push_back(MB->getMemBufferRef());
-    OwningMBs.push_back(std::move(MB)); // take ownership
-  }
+  // Windows specific -- Input files can be Windows resource files (.res files).
+  // We invoke cvtres.exe to convert resource files to a regular COFF file
+  // then link the result file normally.
+  if (!Resources.empty())
+    addBuffer(convertResToCOFF(Resources));
 
   if (Cpio)
     Cpio->append("response.txt",
-                 createResponseFile(Args, MBs,
+                 createResponseFile(Args, FilePaths,
                                     ArrayRef<StringRef>(SearchPaths).slice(1)));
 
   // Handle /largeaddressaware
   if (Config->is64() || Args.hasArg(OPT_largeaddressaware))
     Config->LargeAddressAware = true;
 
   // Handle /highentropyva
   if (Config->is64() && !Args.hasArg(OPT_highentropyva_no))
if (Config->Machine == I386) {
       if (!E.ExtName.empty() && !isDecorated(E.ExtName))
         E.ExtName = Saver.save("_" + E.ExtName);
     }
     Config->Exports.push_back(E);
   }
 
   // Handle /def
   if (auto *Arg = Args.getLastArg(OPT_deffile)) {
-    MemoryBufferRef MB = openFile(Arg->getValue());
     // parseModuleDefs mutates Config object.
-    parseModuleDefs(MB);
+    parseModuleDefs(
+        takeBuffer(check(MemoryBuffer::getFile(Arg->getValue()),
+                         Twine("could not open ") + Arg->getValue())));
   }
 
   // Handle /delayload
   for (auto *Arg : Args.filtered(OPT_delayload)) {
     Config->DelayLoads.insert(StringRef(Arg->getValue()).lower());
     if (Config->Machine == I386) {
       Config->DelayLoadHelper = addUndefined("___delayLoadHelper2@8");
     } else {
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);
 
+  // This code may add new undefined symbols to the link, which may enqueue more
+  // symbol resolution tasks, so we need to continue executing tasks until we
+  // converge.
+  do {
     // 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"));
+  } while (run());
 
   // Do LTO by compiling bitcode input files to a set of native COFF files then
   // link those files.
   Symtab.addCombinedLTOObjects();
+  run();
 
   // Make sure we have resolved all symbols.
   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();

lld/trunk/COFF/InputFiles.h

 
 // .lib or .a file.
 class ArchiveFile : public InputFile {
 public:
   explicit ArchiveFile(MemoryBufferRef M);
   static bool classof(const InputFile *F) { return F->kind() == ArchiveKind; }
   void parse() override;
 
-  // 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.)
-  InputFile *getMember(const Archive::Symbol *Sym);
+  // Enqueues an archive member load for the given symbol. If we've already
+  // enqueued a load for the same archive member, this function does nothing,
+  // which ensures that we don't load the same member more than once.
+  void addMember(const Archive::Symbol *Sym);
 
 private:
   std::unique_ptr<Archive> File;
   std::string Filename;
   llvm::DenseSet<uint64_t> Seen;
 };
 
 // .obj or .o file. This may be a member of an archive file.

lld/trunk/COFF/InputFiles.cpp

void ArchiveFile::parse() {
   File = check(Archive::create(MB), toString(this));
 
   // 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.
-InputFile *ArchiveFile::getMember(const Archive::Symbol *Sym) {
+void ArchiveFile::addMember(const Archive::Symbol *Sym) {
   const Archive::Child &C =
       check(Sym->getMember(),
             "could not get the member for symbol " + Sym->getName());
 
   // Return an empty buffer if we have already returned the same buffer.
   if (!Seen.insert(C.getChildOffset()).second)
-    return nullptr;
-
-  MemoryBufferRef MB =
-      check(C.getMemoryBufferRef(),
-            "could not get the buffer for the member defining symbol " +
-                Sym->getName());
-  if (C.getParent()->isThin() && Driver->Cpio)
-    Driver->Cpio->append(relativeToRoot(check(C.getFullName())),
-                         MB.getBuffer());
-
-  file_magic Magic = identify_magic(MB.getBuffer());
-  if (Magic == file_magic::coff_import_library)
-    return make<ImportFile>(MB);
-
-  InputFile *Obj;
-  if (Magic == file_magic::coff_object)
-    Obj = make<ObjectFile>(MB);
-  else if (Magic == file_magic::bitcode)
-    Obj = make<BitcodeFile>(MB);
-  else
-    fatal("unknown file type: " + MB.getBufferIdentifier());
+    return;
 
-  Obj->ParentName = getName();
-  return Obj;
+  Driver->enqueueArchiveMember(C, Sym->getName(), getName());
 }
 
 void ObjectFile::parse() {
   // Parse a memory buffer as a COFF file.
   std::unique_ptr<Binary> Bin = check(createBinary(MB), toString(this));
 
   if (auto *Obj = dyn_cast<COFFObjectFile>(Bin.get())) {
     Bin.release();

lld/trunk/COFF/SymbolTable.h

 
 #include "InputFiles.h"
 #include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.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
-
 namespace llvm {
 struct LTOCodeGenerator;
 }
 
 namespace lld {
 namespace coff {
 
 class Chunk;

 
 private:
   void readArchive();
   void readObjects();
 
   std::pair<Symbol *, bool> insert(StringRef Name);
   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<llvm::CachedHashStringRef, Symbol *> Symtab;
 
   std::vector<BitcodeFile *> BitcodeFiles;
   std::vector<SmallString<0>> Objs;
 };
 
 extern SymbolTable *Symtab;
 
 } // namespace coff
 } // namespace lld
 
 #endif

lld/trunk/COFF/SymbolTable.cpp

 }
 
 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
   Symbol *&Sym = Symtab[CachedHashStringRef(Name)];
   if (Sym)
     return {Sym, false};
   Sym = make<Symbol>();
   Sym->IsUsedInRegularObj = false;
+  Sym->PendingArchiveLoad = 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);
+  if (auto *L = dyn_cast<Lazy>(S->body())) {
+    if (!S->PendingArchiveLoad) {
+      S->PendingArchiveLoad = true;
+      L->File->addMember(&L->Sym);
+    }
+  }
   return S;
 }
 
 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)
+  if (!U || U->WeakAlias || S->PendingArchiveLoad)
     return;
-  addMemberFile(F, Sym);
+  S->PendingArchiveLoad = true;
+  F->addMember(&Sym);
 }
 
 void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
   fatal("duplicate symbol: " + toString(*Existing->body()) + " in " +
         toString(Existing->body()->getFile()) + " and in " +
         (NewFile ? toString(NewFile) : "(internal)"));
 }
 
Symbol *SymbolTable::addImportThunk(StringRef Name, DefinedImportData *ID,
   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(ArchiveFile *F, const Archive::Symbol Sym) {
-  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)
-    outs() << "Loaded " << toString(File) << " for " << Sym.getName() << "\n";
-  addFile(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());
   }
   return Res;
 }

 void SymbolTable::addCombinedLTOObjects() {
   if (BitcodeFiles.empty())
     return;
 
   // 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);
-
-  size_t NumBitcodeFiles = BitcodeFiles.size();
-  for (ObjectFile *Obj : Objs)
+  for (ObjectFile *Obj : createLTOObjects(&CG))
     Obj->parse();
-  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
   // preserved. We must also replace bitcode symbols with undefined symbols so
   // that they may be replaced with real definitions without conflicting.

lld/trunk/COFF/Symbols.h

 // 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;
 
+  // True if we've seen both a lazy and an undefined symbol with this symbol
+  // name, which means that we have enqueued an archive member load and should
+  // not load any more archive members to resolve the same symbol.
+  unsigned PendingArchiveLoad : 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;

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