[PATCH] Speculatively instantiate archive members

LLD parses archive file index table only at first. When it finds a symbol
it is looking for is defined in a member file in an archive file, it actually
reads the member from the archive file. That's done in the core linker.

That's a single-thread process since the core linker is single threaded.
If your command line contains a few object files and a lot of archive files
(which is quite often the case), LLD hardly utilizes hardware parallelism.

This patch improves parallelism by speculatively instantiating archive
file members. At the beginning of the core linking, we first create a map
containing all symbols defined in all members, and each time we find a
new undefined symbol, we instantiate a member file containing the
symbol (if such file exists). File instantiation is side effect free, so this
should not affect correctness.

This is a quick benchmark result. Time to link self-link LLD executable:

Linux   9.78s -> 8.50s (0.86x)
Windows 6.18s -> 4.51s (0.73x)

http://reviews.llvm.org/D7015

llvm-svn: 226336

2 files changed, 56 insertions, 5 deletions

diff --git a/lld/lib/ReaderWriter/FileArchive.cpp b/lld/lib/ReaderWriter/FileArchive.cpp
index a344fdf72a7..fe336aa4cea 100644
--- a/lld/lib/ReaderWriter/FileArchive.cpp
+++ b/lld/lib/ReaderWriter/FileArchive.cpp
@@ -17,7 +17,9 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/MemoryBuffer.h"
+#include <future>
 #include <memory>
+#include <mutex>
 #include <set>
 #include <unordered_map>
 
@@ -57,6 +59,17 @@ public:
       return nullptr;
 
     _membersInstantiated.insert(memberStart);
+
+    // Check if a file is preloaded.
+    {
+      std::lock_guard<std::mutex> lock(_mutex);
+      auto it = _preloaded.find(memberStart);
+      if (it != _preloaded.end()) {
+        std::future<const File *> &future = it->second;
+        return future.get();
+      }
+    }
+
     std::unique_ptr<File> result;
     if (instantiateMember(ci, result))
       return nullptr;
@@ -65,6 +78,37 @@ public:
     return result.release();
   }
 
+  // Instantiate a member file containing a given symbol name.
+  void preload(TaskGroup &group, StringRef name) override {
+    auto member = _symbolMemberMap.find(name);
+    if (member == _symbolMemberMap.end())
+      return;
+    Archive::child_iterator ci = member->second;
+
+    // Do nothing if a member is already instantiated.
+    const char *memberStart = ci->getBuffer().data();
+    if (_membersInstantiated.count(memberStart))
+      return;
+
+    std::lock_guard<std::mutex> lock(_mutex);
+    if (_preloaded.find(memberStart) != _preloaded.end())
+      return;
+
+    // Instantiate the member
+    auto *promise = new std::promise<const File *>;
+    _preloaded[memberStart] = promise->get_future();
+    _promises.push_back(std::unique_ptr<std::promise<const File *>>(promise));
+
+    group.spawn([=] {
+      std::unique_ptr<File> result;
+      if (instantiateMember(ci, result)) {
+        promise->set_value(nullptr);
+        return;
+      }
+      promise->set_value(result.release());
+    });
+  }
+
   /// \brief parse each member
   std::error_code
   parseAllMembers(std::vector<std::unique_ptr<File>> &result) override {
@@ -117,7 +161,8 @@ public:
   }
 
   /// Returns a set of all defined symbols in the archive.
-  std::set<StringRef> getDefinedSymbols() const override {
+  std::set<StringRef> getDefinedSymbols() override {
+    parse();
     std::set<StringRef> ret;
     for (const auto &e : _symbolMemberMap)
       ret.insert(e.first);
@@ -225,6 +270,9 @@ private:
   atom_collection_vector<AbsoluteAtom> _absoluteAtoms;
   bool _logLoading;
   mutable std::vector<std::unique_ptr<MemoryBuffer>> _memberBuffers;
+  mutable std::map<const char *, std::future<const File *>> _preloaded;
+  mutable std::vector<std::unique_ptr<std::promise<const File *>>> _promises;
+  mutable std::mutex _mutex;
 };
 
 class ArchiveReader : public Reader {
diff --git a/lld/lib/ReaderWriter/PECOFF/ReaderCOFF.cpp b/lld/lib/ReaderWriter/PECOFF/ReaderCOFF.cpp
index adcee29f649..dd261614c1c 100644
--- a/lld/lib/ReaderWriter/PECOFF/ReaderCOFF.cpp
+++ b/lld/lib/ReaderWriter/PECOFF/ReaderCOFF.cpp
@@ -106,6 +106,8 @@ public:
     return _absoluteAtoms;
   }
 
+  void beforeLink() override;
+
   void addDefinedAtom(AliasAtom *atom) {
     atom->setOrdinal(_ordinal++);
     _definedAtoms._atoms.push_back(atom);
@@ -382,7 +384,10 @@ std::error_code FileCOFF::doParse() {
   // The mapping for /alternatename is in the context object. This helper
   // function iterate over defined atoms and create alias atoms if needed.
   createAlternateNameAtoms();
+  return std::error_code();
+}
 
+void FileCOFF::beforeLink() {
   // Acquire the mutex to mutate _ctx.
   std::lock_guard<std::recursive_mutex> lock(_ctx.getMutex());
 
@@ -392,10 +397,8 @@ std::error_code FileCOFF::doParse() {
     _ctx.setSafeSEH(false);
 
   if (_ctx.deadStrip())
-    for (StringRef sym : undefinedSymbols)
-      _ctx.addDeadStripRoot(sym);
-
-  return std::error_code();
+    for (const UndefinedAtom *undef : undefined())
+      _ctx.addDeadStripRoot(undef->name());
 }
 
 /// Iterate over the symbol table to retrieve all symbols.