[ORC] Switch to asynchronous resolution in JITSymbolResolver.

Asynchronous resolution (where the caller receives a callback once the requested
set of symbols are resolved) is a core part of the new concurrent ORC APIs. This
change extends the asynchronous resolution model down to RuntimeDyld, which is
necessary to prevent deadlocks when compiling/linking on a fixed number of
threads: If RuntimeDyld's linking process were a blocking operation, then any
complete K-graph in a program will require at least K threads to link in the
worst case, as each thread would block waiting for all the others to complete.
Using callbacks instead allows the work to be passed between dependent threads
until it is complete.

For backwards compatibility, all existing RuntimeDyld functions will continue
to operate in blocking mode as before. This change will enable the introduction
of a new async finalization process in a subsequent patch to enable asynchronous
JIT linking.

llvm-svn: 342939

5 files changed, 99 insertions, 55 deletions

diff --git a/llvm/lib/ExecutionEngine/RuntimeDyld/JITSymbol.cpp b/llvm/lib/ExecutionEngine/RuntimeDyld/JITSymbol.cpp
index d865216cf31..b6ef8ad9675 100644
--- a/llvm/lib/ExecutionEngine/RuntimeDyld/JITSymbol.cpp
+++ b/llvm/lib/ExecutionEngine/RuntimeDyld/JITSymbol.cpp
@@ -62,34 +62,42 @@ llvm::ARMJITSymbolFlags::fromObjectSymbol(const object::SymbolRef &Symbol) {
 /// Performs lookup by, for each symbol, first calling
 ///        findSymbolInLogicalDylib and if that fails calling
 ///        findSymbol.
-Expected<JITSymbolResolver::LookupResult>
-LegacyJITSymbolResolver::lookup(const LookupSet &Symbols) {
+void LegacyJITSymbolResolver::lookup(const LookupSet &Symbols,
+                                     OnResolvedFunction OnResolved) {
   JITSymbolResolver::LookupResult Result;
   for (auto &Symbol : Symbols) {
     std::string SymName = Symbol.str();
     if (auto Sym = findSymbolInLogicalDylib(SymName)) {
       if (auto AddrOrErr = Sym.getAddress())
         Result[Symbol] = JITEvaluatedSymbol(*AddrOrErr, Sym.getFlags());
-      else
-        return AddrOrErr.takeError();
-    } else if (auto Err = Sym.takeError())
-      return std::move(Err);
-    else {
+      else {
+        OnResolved(AddrOrErr.takeError());
+        return;
+      }
+    } else if (auto Err = Sym.takeError()) {
+      OnResolved(std::move(Err));
+      return;
+    } else {
       // findSymbolInLogicalDylib failed. Lets try findSymbol.
       if (auto Sym = findSymbol(SymName)) {
         if (auto AddrOrErr = Sym.getAddress())
           Result[Symbol] = JITEvaluatedSymbol(*AddrOrErr, Sym.getFlags());
-        else
-          return AddrOrErr.takeError();
-      } else if (auto Err = Sym.takeError())
-        return std::move(Err);
-      else
-        return make_error<StringError>("Symbol not found: " + Symbol,
-                                       inconvertibleErrorCode());
+        else {
+          OnResolved(AddrOrErr.takeError());
+          return;
+        }
+      } else if (auto Err = Sym.takeError()) {
+        OnResolved(std::move(Err));
+        return;
+      } else {
+        OnResolved(make_error<StringError>("Symbol not found: " + Symbol,
+                                           inconvertibleErrorCode()));
+        return;
+      }
     }
   }
 
-  return std::move(Result);
+  OnResolved(std::move(Result));
 }
 
 /// Performs flags lookup by calling findSymbolInLogicalDylib and
diff --git a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp
index 43c99b52c34..a651e78f7f0 100644
--- a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp
+++ b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp
@@ -23,6 +23,8 @@
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/MutexGuard.h"
 
+#include <future>
+
 using namespace llvm;
 using namespace llvm::object;
 
@@ -996,42 +998,8 @@ void RuntimeDyldImpl::resolveRelocationList(const RelocationList &Relocs,
   }
 }
 
-Error RuntimeDyldImpl::resolveExternalSymbols() {
-  StringMap<JITEvaluatedSymbol> ExternalSymbolMap;
-
-  // Resolution can trigger emission of more symbols, so iterate until
-  // we've resolved *everything*.
-  {
-    JITSymbolResolver::LookupSet ResolvedSymbols;
-
-    while (true) {
-      JITSymbolResolver::LookupSet NewSymbols;
-
-      for (auto &RelocKV : ExternalSymbolRelocations) {
-        StringRef Name = RelocKV.first();
-        if (!Name.empty() && !GlobalSymbolTable.count(Name) &&
-            !ResolvedSymbols.count(Name))
-          NewSymbols.insert(Name);
-      }
-
-      if (NewSymbols.empty())
-        break;
-
-      auto NewResolverResults = Resolver.lookup(NewSymbols);
-      if (!NewResolverResults)
-        return NewResolverResults.takeError();
-
-      assert(NewResolverResults->size() == NewSymbols.size() &&
-             "Should have errored on unresolved symbols");
-
-      for (auto &RRKV : *NewResolverResults) {
-        assert(!ResolvedSymbols.count(RRKV.first) && "Redundant resolution?");
-        ExternalSymbolMap.insert(RRKV);
-        ResolvedSymbols.insert(RRKV.first);
-      }
-    }
-  }
-
+void RuntimeDyldImpl::applyExternalSymbolRelocations(
+    const StringMap<JITEvaluatedSymbol> ExternalSymbolMap) {
   while (!ExternalSymbolRelocations.empty()) {
 
     StringMap<RelocationList>::iterator i = ExternalSymbolRelocations.begin();
@@ -1093,6 +1061,54 @@ Error RuntimeDyldImpl::resolveExternalSymbols() {
 
     ExternalSymbolRelocations.erase(i);
   }
+}
+
+Error RuntimeDyldImpl::resolveExternalSymbols() {
+  StringMap<JITEvaluatedSymbol> ExternalSymbolMap;
+
+  // Resolution can trigger emission of more symbols, so iterate until
+  // we've resolved *everything*.
+  {
+    JITSymbolResolver::LookupSet ResolvedSymbols;
+
+    while (true) {
+      JITSymbolResolver::LookupSet NewSymbols;
+
+      for (auto &RelocKV : ExternalSymbolRelocations) {
+        StringRef Name = RelocKV.first();
+        if (!Name.empty() && !GlobalSymbolTable.count(Name) &&
+            !ResolvedSymbols.count(Name))
+          NewSymbols.insert(Name);
+      }
+
+      if (NewSymbols.empty())
+        break;
+
+      auto NewSymbolsP = std::make_shared<
+          std::promise<Expected<JITSymbolResolver::LookupResult>>>();
+      auto NewSymbolsF = NewSymbolsP->get_future();
+      Resolver.lookup(NewSymbols,
+                      [=](Expected<JITSymbolResolver::LookupResult> Result) {
+                        NewSymbolsP->set_value(std::move(Result));
+                      });
+
+      auto NewResolverResults = NewSymbolsF.get();
+
+      if (!NewResolverResults)
+        return NewResolverResults.takeError();
+
+      assert(NewResolverResults->size() == NewSymbols.size() &&
+             "Should have errored on unresolved symbols");
+
+      for (auto &RRKV : *NewResolverResults) {
+        assert(!ResolvedSymbols.count(RRKV.first) && "Redundant resolution?");
+        ExternalSymbolMap.insert(RRKV);
+        ResolvedSymbols.insert(RRKV.first);
+      }
+    }
+  }
+
+  applyExternalSymbolRelocations(ExternalSymbolMap);
 
   return Error::success();
 }
diff --git a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldChecker.cpp b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldChecker.cpp
index fa8906869b3..79a1bbb1a77 100644
--- a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldChecker.cpp
+++ b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldChecker.cpp
@@ -16,6 +16,7 @@
 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/Path.h"
 #include <cctype>
+#include <future>
 #include <memory>
 #include <utility>
 
@@ -729,15 +730,29 @@ bool RuntimeDyldCheckerImpl::checkAllRulesInBuffer(StringRef RulePrefix,
   return DidAllTestsPass && (NumRules != 0);
 }
 
+Expected<JITSymbolResolver::LookupResult> RuntimeDyldCheckerImpl::lookup(
+    const JITSymbolResolver::LookupSet &Symbols) const {
+  auto ResultP = std::make_shared<
+      std::promise<Expected<JITSymbolResolver::LookupResult>>>();
+  auto ResultF = ResultP->get_future();
+
+  getRTDyld().Resolver.lookup(
+      Symbols, [=](Expected<JITSymbolResolver::LookupResult> Result) {
+        ResultP->set_value(std::move(Result));
+      });
+  return ResultF.get();
+}
+
 bool RuntimeDyldCheckerImpl::isSymbolValid(StringRef Symbol) const {
   if (getRTDyld().getSymbol(Symbol))
     return true;
-  JITSymbolResolver::LookupSet Symbols({Symbol});
-  auto Result = getRTDyld().Resolver.lookup(Symbols);
+  auto Result = lookup({Symbol});
+
   if (!Result) {
     logAllUnhandledErrors(Result.takeError(), errs(), "RTDyldChecker: ");
     return false;
   }
+
   assert(Result->count(Symbol) && "Missing symbol result");
   return true;
 }
@@ -751,8 +766,7 @@ uint64_t RuntimeDyldCheckerImpl::getSymbolRemoteAddr(StringRef Symbol) const {
   if (auto InternalSymbol = getRTDyld().getSymbol(Symbol))
     return InternalSymbol.getAddress();
 
-  JITSymbolResolver::LookupSet Symbols({Symbol});
-  auto Result = getRTDyld().Resolver.lookup(Symbols);
+  auto Result = lookup({Symbol});
   if (!Result) {
     logAllUnhandledErrors(Result.takeError(), errs(), "RTDyldChecker: ");
     return 0;
diff --git a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldCheckerImpl.h b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldCheckerImpl.h
index b462ef2c00c..6da1a68d06d 100644
--- a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldCheckerImpl.h
+++ b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldCheckerImpl.h
@@ -41,6 +41,9 @@ private:
 
   RuntimeDyldImpl &getRTDyld() const { return *RTDyld.Dyld; }
 
+  Expected<JITSymbolResolver::LookupResult>
+  lookup(const JITSymbolResolver::LookupSet &Symbols) const;
+
   bool isSymbolValid(StringRef Symbol) const;
   uint64_t getSymbolLocalAddr(StringRef Symbol) const;
   uint64_t getSymbolRemoteAddr(StringRef Symbol) const;
diff --git a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldImpl.h b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldImpl.h
index 9b339524162..f01d3103f82 100644
--- a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldImpl.h
+++ b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldImpl.h
@@ -433,6 +433,9 @@ protected:
                        const ObjectFile &Obj, ObjSectionToIDMap &ObjSectionToID,
                        StubMap &Stubs) = 0;
 
+  void applyExternalSymbolRelocations(
+      const StringMap<JITEvaluatedSymbol> ExternalSymbolMap);
+
   /// Resolve relocations to external symbols.
   Error resolveExternalSymbols();