[ORC] Redesign the JITSymbolResolver interface to support bulk queries.

Bulk queries reduce IPC/RPC overhead for cross-process JITing and expose
opportunities for parallel compilation.

The two new query methods are lookupFlags, which finds the flags for each of a
set of symbols; and lookup, which finds the address and flags for each of a
set of symbols. (See doxygen comments for more details.)

The existing JITSymbolResolver class is renamed LegacyJITSymbolResolver, and
modified to extend the new JITSymbolResolver class using the following scheme:

- lookupFlags is implemented by calling findSymbolInLogicalDylib for each of the
symbols, then returning the result of calling getFlags() on each of these
symbols. (Importantly: lookupFlags does NOT call getAddress on the returned
symbols, so lookupFlags will never trigger materialization, and lookupFlags will
never call findSymbol, so only symbols that are part of the logical dylib will
return results.)

- lookup is implemented by calling findSymbolInLogicalDylib for each symbol and
falling back to findSymbol if findSymbolInLogicalDylib returns a null result.
Assuming a symbol is found its getAddress method is called to materialize it and
the result (if getAddress succeeds) is stored in the result map, or the error
(if getAddress fails) is returned immediately from lookup. If any symbol is not
found then lookup returns immediately with an error.

This change will break any out-of-tree derivatives of JITSymbolResolver. This
can be fixed by updating those classes to derive from LegacyJITSymbolResolver
instead.

llvm-svn: 322913

4 files changed, 229 insertions, 148 deletions

diff --git a/llvm/lib/ExecutionEngine/RuntimeDyld/JITSymbol.cpp b/llvm/lib/ExecutionEngine/RuntimeDyld/JITSymbol.cpp
index 87059ef2b88..670c6d2fa3f 100644
--- a/llvm/lib/ExecutionEngine/RuntimeDyld/JITSymbol.cpp
+++ b/llvm/lib/ExecutionEngine/RuntimeDyld/JITSymbol.cpp
@@ -47,3 +47,53 @@ ARMJITSymbolFlags llvm::ARMJITSymbolFlags::fromObjectSymbol(
     Flags |= ARMJITSymbolFlags::Thumb;
   return Flags;
 }
+
+/// @brief Performs lookup by, for each symbol, first calling
+///        findSymbolInLogicalDylib and if that fails calling
+///        findSymbol.
+Expected<JITSymbolResolver::LookupResult>
+LegacyJITSymbolResolver::lookup(const SymbolNameSet &Symbols) {
+  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 {
+      // 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());
+    }
+  }
+
+  return std::move(Result);
+}
+
+/// @brief Performs flags lookup by calling findSymbolInLogicalDylib and
+///        returning the flags value for that symbol.
+Expected<JITSymbolResolver::LookupFlagsResult>
+LegacyJITSymbolResolver::lookupFlags(const SymbolNameSet &Symbols) {
+  JITSymbolResolver::LookupFlagsResult Result;
+
+  for (auto &Symbol : Symbols) {
+    std::string SymName = Symbol.str();
+    if (auto Sym = findSymbolInLogicalDylib(SymName))
+      Result[Symbol] = Sym.getFlags();
+    else if (auto Err = Sym.takeError())
+      return std::move(Err);
+  }
+
+  return std::move(Result);
+}
diff --git a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp
index 3a025f4c026..ce8d480a408 100644
--- a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp
+++ b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp
@@ -202,7 +202,33 @@ RuntimeDyldImpl::loadObjectImpl(const object::ObjectFile &Obj) {
   ObjSectionToIDMap LocalSections;
 
   // Common symbols requiring allocation, with their sizes and alignments
-  CommonSymbolList CommonSymbols;
+  CommonSymbolList CommonSymbolsToAllocate;
+
+  uint64_t CommonSize = 0;
+  uint32_t CommonAlign = 0;
+
+  // First, collect all weak and common symbols. We need to know if stronger
+  // definitions occur elsewhere.
+  JITSymbolResolver::LookupFlagsResult SymbolFlags;
+  {
+    JITSymbolResolver::SymbolNameSet Symbols;
+    for (auto &Sym : Obj.symbols()) {
+      uint32_t Flags = Sym.getFlags();
+      if ((Flags & SymbolRef::SF_Common) || (Flags & SymbolRef::SF_Weak)) {
+        // Get symbol name.
+        StringRef Name;
+        if (auto NameOrErr = Sym.getName())
+          Symbols.insert(*NameOrErr);
+        else
+          return NameOrErr.takeError();
+      }
+    }
+
+    if (auto FlagsResultOrErr = Resolver.lookupFlags(Symbols))
+      SymbolFlags = std::move(*FlagsResultOrErr);
+    else
+      return FlagsResultOrErr.takeError();
+  }
 
   // Parse symbols
   DEBUG(dbgs() << "Parse symbols:\n");
@@ -214,102 +240,108 @@ RuntimeDyldImpl::loadObjectImpl(const object::ObjectFile &Obj) {
     if (Flags & SymbolRef::SF_Undefined)
       continue;
 
-    if (Flags & SymbolRef::SF_Common)
-      CommonSymbols.push_back(*I);
-    else {
+    // Get the symbol type.
+    object::SymbolRef::Type SymType;
+    if (auto SymTypeOrErr = I->getType())
+      SymType = *SymTypeOrErr;
+    else
+      return SymTypeOrErr.takeError();
 
-      // Get the symbol type.
-      object::SymbolRef::Type SymType;
-      if (auto SymTypeOrErr = I->getType())
-        SymType =  *SymTypeOrErr;
-      else
-        return SymTypeOrErr.takeError();
+    // Get symbol name.
+    StringRef Name;
+    if (auto NameOrErr = I->getName())
+      Name = *NameOrErr;
+    else
+      return NameOrErr.takeError();
 
-      // Get symbol name.
-      StringRef Name;
-      if (auto NameOrErr = I->getName())
-        Name = *NameOrErr;
-      else
-        return NameOrErr.takeError();
-
-      // Compute JIT symbol flags.
-      JITSymbolFlags JITSymFlags = getJITSymbolFlags(*I);
-
-      // If this is a weak definition, check to see if there's a strong one.
-      // If there is, skip this symbol (we won't be providing it: the strong
-      // definition will). If there's no strong definition, make this definition
-      // strong.
-      if (JITSymFlags.isWeak()) {
-        // First check whether there's already a definition in this instance.
-        // FIXME: Override existing weak definitions with strong ones.
-        if (GlobalSymbolTable.count(Name))
-          continue;
-        // Then check the symbol resolver to see if there's a definition
-        // elsewhere in this logical dylib.
-        if (auto Sym = Resolver.findSymbolInLogicalDylib(Name)) {
-          if (Sym.getFlags().isStrong())
-            continue;
-        } else if (auto Err = Sym.takeError())
-          return std::move(Err);
-        // else
-        JITSymFlags &= ~JITSymbolFlags::Weak;
-      }
+    // Compute JIT symbol flags.
+    JITSymbolFlags JITSymFlags = getJITSymbolFlags(*I);
+
+    // If this is a weak definition, check to see if there's a strong one.
+    // If there is, skip this symbol (we won't be providing it: the strong
+    // definition will). If there's no strong definition, make this definition
+    // strong.
+    if (JITSymFlags.isWeak() || JITSymFlags.isCommon()) {
+      // First check whether there's already a definition in this instance.
+      // FIXME: Override existing weak definitions with strong ones.
+      if (GlobalSymbolTable.count(Name))
+        continue;
 
-      if (Flags & SymbolRef::SF_Absolute &&
-          SymType != object::SymbolRef::ST_File) {
-        uint64_t Addr = 0;
-        if (auto AddrOrErr = I->getAddress())
-          Addr = *AddrOrErr;
-        else
-          return AddrOrErr.takeError();
-
-        unsigned SectionID = AbsoluteSymbolSection;
-
-        DEBUG(dbgs() << "\tType: " << SymType << " (absolute) Name: " << Name
-                     << " SID: " << SectionID << " Offset: "
-                     << format("%p", (uintptr_t)Addr)
-                     << " flags: " << Flags << "\n");
-        GlobalSymbolTable[Name] =
-          SymbolTableEntry(SectionID, Addr, JITSymFlags);
-      } else if (SymType == object::SymbolRef::ST_Function ||
-                 SymType == object::SymbolRef::ST_Data ||
-                 SymType == object::SymbolRef::ST_Unknown ||
-                 SymType == object::SymbolRef::ST_Other) {
-
-        section_iterator SI = Obj.section_end();
-        if (auto SIOrErr = I->getSection())
-          SI = *SIOrErr;
-        else
-          return SIOrErr.takeError();
+      // Then check whether we found flags for an existing symbol during the
+      // flags lookup earlier.
+      auto FlagsI = SymbolFlags.find(Name);
+      if (FlagsI == SymbolFlags.end() ||
+          (JITSymFlags.isWeak() && !FlagsI->second.isStrong()) ||
+          (JITSymFlags.isCommon() && FlagsI->second.isCommon())) {
+        if (JITSymFlags.isWeak())
+          JITSymFlags &= ~JITSymbolFlags::Weak;
+        if (JITSymFlags.isCommon()) {
+          JITSymFlags &= ~JITSymbolFlags::Common;
+          uint32_t Align = I->getAlignment();
+          uint64_t Size = I->getCommonSize();
+          if (!CommonAlign)
+            CommonAlign = Align;
+          CommonSize += alignTo(CommonSize, Align) + Size;
+          CommonSymbolsToAllocate.push_back(*I);
+        }
+      } else
+        continue;
+    }
+
+    if (Flags & SymbolRef::SF_Absolute &&
+        SymType != object::SymbolRef::ST_File) {
+      uint64_t Addr = 0;
+      if (auto AddrOrErr = I->getAddress())
+        Addr = *AddrOrErr;
+      else
+        return AddrOrErr.takeError();
+
+      unsigned SectionID = AbsoluteSymbolSection;
+
+      DEBUG(dbgs() << "\tType: " << SymType << " (absolute) Name: " << Name
+                   << " SID: " << SectionID
+                   << " Offset: " << format("%p", (uintptr_t)Addr)
+                   << " flags: " << Flags << "\n");
+      GlobalSymbolTable[Name] = SymbolTableEntry(SectionID, Addr, JITSymFlags);
+    } else if (SymType == object::SymbolRef::ST_Function ||
+               SymType == object::SymbolRef::ST_Data ||
+               SymType == object::SymbolRef::ST_Unknown ||
+               SymType == object::SymbolRef::ST_Other) {
+
+      section_iterator SI = Obj.section_end();
+      if (auto SIOrErr = I->getSection())
+        SI = *SIOrErr;
+      else
+        return SIOrErr.takeError();
 
-        if (SI == Obj.section_end())
-          continue;
+      if (SI == Obj.section_end())
+        continue;
 
-        // Get symbol offset.
-        uint64_t SectOffset;
-        if (auto Err = getOffset(*I, *SI, SectOffset))
-          return std::move(Err);
+      // Get symbol offset.
+      uint64_t SectOffset;
+      if (auto Err = getOffset(*I, *SI, SectOffset))
+        return std::move(Err);
 
-        bool IsCode = SI->isText();
-        unsigned SectionID;
-        if (auto SectionIDOrErr = findOrEmitSection(Obj, *SI, IsCode,
-                                                    LocalSections))
-          SectionID = *SectionIDOrErr;
-        else
-          return SectionIDOrErr.takeError();
+      bool IsCode = SI->isText();
+      unsigned SectionID;
+      if (auto SectionIDOrErr =
+              findOrEmitSection(Obj, *SI, IsCode, LocalSections))
+        SectionID = *SectionIDOrErr;
+      else
+        return SectionIDOrErr.takeError();
 
-        DEBUG(dbgs() << "\tType: " << SymType << " Name: " << Name
-                     << " SID: " << SectionID << " Offset: "
-                     << format("%p", (uintptr_t)SectOffset)
-                     << " flags: " << Flags << "\n");
-        GlobalSymbolTable[Name] =
+      DEBUG(dbgs() << "\tType: " << SymType << " Name: " << Name
+                   << " SID: " << SectionID
+                   << " Offset: " << format("%p", (uintptr_t)SectOffset)
+                   << " flags: " << Flags << "\n");
+      GlobalSymbolTable[Name] =
           SymbolTableEntry(SectionID, SectOffset, JITSymFlags);
-      }
     }
   }
 
   // Allocate common symbols
-  if (auto Err = emitCommonSymbols(Obj, CommonSymbols))
+  if (auto Err = emitCommonSymbols(Obj, CommonSymbolsToAllocate, CommonSize,
+                                   CommonAlign))
     return std::move(Err);
 
   // Parse and process relocations
@@ -621,45 +653,12 @@ JITSymbolFlags RuntimeDyldImpl::getJITSymbolFlags(const BasicSymbolRef &SR) {
 }
 
 Error RuntimeDyldImpl::emitCommonSymbols(const ObjectFile &Obj,
-                                         CommonSymbolList &CommonSymbols) {
-  if (CommonSymbols.empty())
+                                         CommonSymbolList &SymbolsToAllocate,
+                                         uint64_t CommonSize,
+                                         uint32_t CommonAlign) {
+  if (SymbolsToAllocate.empty())
     return Error::success();
 
-  uint64_t CommonSize = 0;
-  uint32_t CommonAlign = CommonSymbols.begin()->getAlignment();
-  CommonSymbolList SymbolsToAllocate;
-
-  DEBUG(dbgs() << "Processing common symbols...\n");
-
-  for (const auto &Sym : CommonSymbols) {
-    StringRef Name;
-    if (auto NameOrErr = Sym.getName())
-      Name = *NameOrErr;
-    else
-      return NameOrErr.takeError();
-
-    // Skip common symbols already elsewhere.
-    if (GlobalSymbolTable.count(Name)) {
-      DEBUG(dbgs() << "\tSkipping already emitted common symbol '" << Name
-                   << "'\n");
-      continue;
-    }
-
-    if (auto Sym = Resolver.findSymbolInLogicalDylib(Name)) {
-      if (!Sym.getFlags().isCommon()) {
-        DEBUG(dbgs() << "\tSkipping common symbol '" << Name
-                     << "' in favor of stronger definition.\n");
-        continue;
-      }
-    }
-    uint32_t Align = Sym.getAlignment();
-    uint64_t Size = Sym.getCommonSize();
-
-    CommonSize = alignTo(CommonSize, Align) + Size;
-
-    SymbolsToAllocate.push_back(Sym);
-  }
-
   // Allocate memory for the section
   unsigned SectionID = Sections.size();
   uint8_t *Addr = MemMgr.allocateDataSection(CommonSize, CommonAlign, SectionID,
@@ -997,7 +996,40 @@ void RuntimeDyldImpl::resolveRelocationList(const RelocationList &Relocs,
 }
 
 Error RuntimeDyldImpl::resolveExternalSymbols() {
+  JITSymbolResolver::LookupResult ExternalSymbolMap;
+
+  // Resolution can trigger emission of more symbols, so iterate until
+  // we've resolved *everything*.
+  {
+    JITSymbolResolver::SymbolNameSet ResolvedSymbols;
+
+    while (true) {
+      JITSymbolResolver::SymbolNameSet 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();
+
+      for (auto &RRKV : *NewResolverResults) {
+        assert(!ResolvedSymbols.count(RRKV.first) && "Redundant resolution?");
+        ExternalSymbolMap.insert(RRKV);
+        ResolvedSymbols.insert(RRKV.first);
+      }
+    }
+  }
+
   while (!ExternalSymbolRelocations.empty()) {
+
     StringMap<RelocationList>::iterator i = ExternalSymbolRelocations.begin();
 
     StringRef Name = i->first();
@@ -1012,29 +1044,10 @@ Error RuntimeDyldImpl::resolveExternalSymbols() {
       JITSymbolFlags Flags;
       RTDyldSymbolTable::const_iterator Loc = GlobalSymbolTable.find(Name);
       if (Loc == GlobalSymbolTable.end()) {
-        // This is an external symbol, try to get its address from the symbol
-        // resolver.
-        // First search for the symbol in this logical dylib.
-        if (auto Sym = Resolver.findSymbolInLogicalDylib(Name.data())) {
-          if (auto AddrOrErr = Sym.getAddress()) {
-            Addr = *AddrOrErr;
-            Flags = Sym.getFlags();
-          } else
-            return AddrOrErr.takeError();
-        } else if (auto Err = Sym.takeError())
-          return Err;
-
-        // If that fails, try searching for an external symbol.
-        if (!Addr) {
-          if (auto Sym = Resolver.findSymbol(Name.data())) {
-            if (auto AddrOrErr = Sym.getAddress()) {
-              Addr = *AddrOrErr;
-              Flags = Sym.getFlags();
-            } else
-              return AddrOrErr.takeError();
-          } else if (auto Err = Sym.takeError())
-            return Err;
-        }
+        auto RRI = ExternalSymbolMap.find(Name);
+        assert(RRI != ExternalSymbolMap.end() && "No result for symbol");
+        Addr = RRI->second.getAddress();
+        Flags = RRI->second.getFlags();
         // The call to getSymbolAddress may have caused additional modules to
         // be loaded, which may have added new entries to the
         // ExternalSymbolRelocations map.  Consquently, we need to update our
@@ -1095,6 +1108,7 @@ uint64_t RuntimeDyld::LoadedObjectInfo::getSectionLoadAddress(
 
 void RuntimeDyld::MemoryManager::anchor() {}
 void JITSymbolResolver::anchor() {}
+void LegacyJITSymbolResolver::anchor() {}
 
 RuntimeDyld::RuntimeDyld(RuntimeDyld::MemoryManager &MemMgr,
                          JITSymbolResolver &Resolver)
diff --git a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldChecker.cpp b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldChecker.cpp
index 5bc7434e703..0f4534f2c9f 100644
--- a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldChecker.cpp
+++ b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldChecker.cpp
@@ -731,7 +731,14 @@ bool RuntimeDyldCheckerImpl::checkAllRulesInBuffer(StringRef RulePrefix,
 bool RuntimeDyldCheckerImpl::isSymbolValid(StringRef Symbol) const {
   if (getRTDyld().getSymbol(Symbol))
     return true;
-  return !!getRTDyld().Resolver.findSymbol(Symbol);
+  JITSymbolResolver::SymbolNameSet Symbols({Symbol});
+  auto Result = getRTDyld().Resolver.lookup(Symbols);
+  if (!Result) {
+    logAllUnhandledErrors(Result.takeError(), errs(), "RTDyldChecker: ");
+    return false;
+  }
+  assert(Result->count(Symbol) && "Missing symbol result");
+  return true;
 }
 
 uint64_t RuntimeDyldCheckerImpl::getSymbolLocalAddr(StringRef Symbol) const {
@@ -742,7 +749,16 @@ uint64_t RuntimeDyldCheckerImpl::getSymbolLocalAddr(StringRef Symbol) const {
 uint64_t RuntimeDyldCheckerImpl::getSymbolRemoteAddr(StringRef Symbol) const {
   if (auto InternalSymbol = getRTDyld().getSymbol(Symbol))
     return InternalSymbol.getAddress();
-  return cantFail(getRTDyld().Resolver.findSymbol(Symbol).getAddress());
+
+  JITSymbolResolver::SymbolNameSet Symbols({Symbol});
+  auto Result = getRTDyld().Resolver.lookup(Symbols);
+  if (!Result) {
+    logAllUnhandledErrors(Result.takeError(), errs(), "RTDyldChecker: ");
+    return 0;
+  }
+  auto I = Result->find(Symbol);
+  assert(I != Result->end() && "Missing symbol result");
+  return I->second.getAddress();
 }
 
 uint64_t RuntimeDyldCheckerImpl::readMemoryAtAddr(uint64_t SrcAddr,
diff --git a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldImpl.h b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldImpl.h
index e046a8504e9..e940004bb2e 100644
--- a/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldImpl.h
+++ b/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldImpl.h
@@ -385,7 +385,8 @@ protected:
   /// new section for them and update the symbol mappings in the object and
   /// symbol table.
   Error emitCommonSymbols(const ObjectFile &Obj,
-                          CommonSymbolList &CommonSymbols);
+                          CommonSymbolList &CommonSymbols, uint64_t CommonSize,
+                          uint32_t CommonAlign);
 
   /// \brief Emits section data from the object file to the MemoryManager.
   /// \param IsCode if it's true then allocateCodeSection() will be