[ORC][JITLink] Add support for weak references, and improve handling of static

libraries.

This patch substantially updates ORCv2's lookup API in order to support weak
references, and to better support static archives. Key changes:

-- Each symbol being looked for is now associated with a SymbolLookupFlags
   value. If the associated value is SymbolLookupFlags::RequiredSymbol then
   the symbol must be defined in one of the JITDylibs being searched (or be
   able to be generated in one of these JITDylibs via an attached definition
   generator) or the lookup will fail with an error. If the associated value is
   SymbolLookupFlags::WeaklyReferencedSymbol then the symbol is permitted to be
   undefined, in which case it will simply not appear in the resulting
   SymbolMap if the rest of the lookup succeeds.

   Since lookup now requires these flags for each symbol, the lookup method now
   takes an instance of a new SymbolLookupSet type rather than a SymbolNameSet.
   SymbolLookupSet is a vector-backed set of (name, flags) pairs. Clients are
   responsible for ensuring that the set property (i.e. unique elements) holds,
   though this is usually simple and SymbolLookupSet provides convenience
   methods to support this.

-- Lookups now have an associated LookupKind value, which is either
   LookupKind::Static or LookupKind::DLSym. Definition generators can inspect
   the lookup kind when determining whether or not to generate new definitions.
   The StaticLibraryDefinitionGenerator is updated to only pull in new objects
   from the archive if the lookup kind is Static. This allows lookup to be
   re-used to emulate dlsym for JIT'd symbols without pulling in new objects
   from archives (which would not happen in a normal dlsym call).

-- JITLink is updated to allow externals to be assigned weak linkage, and
   weak externals now use the SymbolLookupFlags::WeaklyReferencedSymbol value
   for lookups. Unresolved weak references will be assigned the default value of
   zero.

Since this patch was modifying the lookup API anyway, it alo replaces all of the
"MatchNonExported" boolean arguments with a "JITDylibLookupFlags" enum for
readability. If a JITDylib's associated value is
JITDylibLookupFlags::MatchExportedSymbolsOnly then the lookup will only
match against exported (non-hidden) symbols in that JITDylib. If a JITDylib's
associated value is JITDylibLookupFlags::MatchAllSymbols then the lookup will
match against any symbol defined in the JITDylib.

13 files changed, 461 insertions, 388 deletions

diff --git a/llvm/lib/ExecutionEngine/JITLink/JITLink.cpp b/llvm/lib/ExecutionEngine/JITLink/JITLink.cpp
index 9df79670d9f..6c924f88957 100644
--- a/llvm/lib/ExecutionEngine/JITLink/JITLink.cpp
+++ b/llvm/lib/ExecutionEngine/JITLink/JITLink.cpp
@@ -266,6 +266,16 @@ void LinkGraph::dump(raw_ostream &OS,
        << "\n";
 }
 
+raw_ostream &operator<<(raw_ostream &OS, const SymbolLookupFlags &LF) {
+  switch (LF) {
+  case SymbolLookupFlags::RequiredSymbol:
+    return OS << "RequiredSymbol";
+  case SymbolLookupFlags::WeaklyReferencedSymbol:
+    return OS << "WeaklyReferencedSymbol";
+  }
+  llvm_unreachable("Unrecognized lookup flags");
+}
+
 void JITLinkAsyncLookupContinuation::anchor() {}
 
 JITLinkContext::~JITLinkContext() {}
diff --git a/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp b/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp
index 9707b9624d9..7b594fd2c0e 100644
--- a/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp
+++ b/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp
@@ -257,25 +257,35 @@ Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) {
   return Error::success();
 }
 
-DenseSet<StringRef> JITLinkerBase::getExternalSymbolNames() const {
+JITLinkContext::LookupMap JITLinkerBase::getExternalSymbolNames() const {
   // Identify unresolved external symbols.
-  DenseSet<StringRef> UnresolvedExternals;
+  JITLinkContext::LookupMap UnresolvedExternals;
   for (auto *Sym : G->external_symbols()) {
     assert(Sym->getAddress() == 0 &&
            "External has already been assigned an address");
     assert(Sym->getName() != StringRef() && Sym->getName() != "" &&
            "Externals must be named");
-    UnresolvedExternals.insert(Sym->getName());
+    SymbolLookupFlags LookupFlags =
+        Sym->getLinkage() == Linkage::Weak
+            ? SymbolLookupFlags::WeaklyReferencedSymbol
+            : SymbolLookupFlags::RequiredSymbol;
+    UnresolvedExternals[Sym->getName()] = LookupFlags;
   }
   return UnresolvedExternals;
 }
 
 void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
   for (auto *Sym : G->external_symbols()) {
+    assert(Sym->getOffset() == 0 &&
+           "External symbol is not at the start of its addressable block");
     assert(Sym->getAddress() == 0 && "Symbol already resolved");
     assert(!Sym->isDefined() && "Symbol being resolved is already defined");
-    assert(Result.count(Sym->getName()) && "Missing resolution for symbol");
-    Sym->getAddressable().setAddress(Result[Sym->getName()].getAddress());
+    auto ResultI = Result.find(Sym->getName());
+    if (ResultI != Result.end())
+      Sym->getAddressable().setAddress(ResultI->second.getAddress());
+    else
+      assert(Sym->getLinkage() == Linkage::Weak &&
+             "Failed to resolve non-weak reference");
   }
 
   LLVM_DEBUG({
@@ -285,8 +295,11 @@ void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
              << formatv("{0:x16}", Sym->getAddress()) << "\n";
   });
   assert(llvm::all_of(G->external_symbols(),
-                      [](Symbol *Sym) { return Sym->getAddress() != 0; }) &&
-         "All symbols should have been resolved by this point");
+                      [](Symbol *Sym) {
+                        return Sym->getAddress() != 0 ||
+                               Sym->getLinkage() == Linkage::Weak;
+                      }) &&
+         "All strong external symbols should have been resolved by now");
 }
 
 void JITLinkerBase::deallocateAndBailOut(Error Err) {
diff --git a/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.h b/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.h
index 07dee6cee20..d5687b7afc9 100644
--- a/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.h
+++ b/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.h
@@ -106,7 +106,7 @@ private:
 
   SegmentLayoutMap layOutBlocks();
   Error allocateSegments(const SegmentLayoutMap &Layout);
-  DenseSet<StringRef> getExternalSymbolNames() const;
+  JITLinkContext::LookupMap getExternalSymbolNames() const;
   void applyLookupResult(AsyncLookupResult LR);
   void deallocateAndBailOut(Error Err);
 
diff --git a/llvm/lib/ExecutionEngine/JITLink/MachOLinkGraphBuilder.cpp b/llvm/lib/ExecutionEngine/JITLink/MachOLinkGraphBuilder.cpp
index c1dc138ee70..1881bd0b287 100644
--- a/llvm/lib/ExecutionEngine/JITLink/MachOLinkGraphBuilder.cpp
+++ b/llvm/lib/ExecutionEngine/JITLink/MachOLinkGraphBuilder.cpp
@@ -321,7 +321,9 @@ Error MachOLinkGraphBuilder::graphifyRegularSymbols() {
           return make_error<JITLinkError>("Anonymous external symbol at "
                                           "index " +
                                           Twine(KV.first));
-        NSym.GraphSymbol = &G->addExternalSymbol(*NSym.Name, 0);
+        NSym.GraphSymbol = &G->addExternalSymbol(
+            *NSym.Name, 0,
+            NSym.Desc & MachO::N_WEAK_REF ? Linkage::Weak : Linkage::Strong);
       }
       break;
     case MachO::N_ABS:
diff --git a/llvm/lib/ExecutionEngine/Orc/CompileOnDemandLayer.cpp b/llvm/lib/ExecutionEngine/Orc/CompileOnDemandLayer.cpp
index 75ddbc30445..b8e42922027 100644
--- a/llvm/lib/ExecutionEngine/Orc/CompileOnDemandLayer.cpp
+++ b/llvm/lib/ExecutionEngine/Orc/CompileOnDemandLayer.cpp
@@ -162,7 +162,8 @@ void CompileOnDemandLayer::emit(MaterializationResponsibility R,
     return;
   }
 
-  R.replace(reexports(PDR.getImplDylib(), std::move(NonCallables), true));
+  R.replace(reexports(PDR.getImplDylib(), std::move(NonCallables),
+                      JITDylibLookupFlags::MatchAllSymbols));
   R.replace(lazyReexports(LCTMgr, PDR.getISManager(), PDR.getImplDylib(),
                           std::move(Callables), AliaseeImpls));
 }
@@ -173,16 +174,20 @@ CompileOnDemandLayer::getPerDylibResources(JITDylib &TargetD) {
   if (I == DylibResources.end()) {
     auto &ImplD = getExecutionSession().createJITDylib(
         TargetD.getName() + ".impl", false);
-    TargetD.withSearchOrderDo([&](const JITDylibSearchList &TargetSearchOrder) {
-      auto NewSearchOrder = TargetSearchOrder;
-      assert(!NewSearchOrder.empty() &&
-             NewSearchOrder.front().first == &TargetD &&
-             NewSearchOrder.front().second == true &&
-             "TargetD must be at the front of its own search order and match "
-             "non-exported symbol");
-      NewSearchOrder.insert(std::next(NewSearchOrder.begin()), {&ImplD, true});
-      ImplD.setSearchOrder(std::move(NewSearchOrder), false);
-    });
+    TargetD.withSearchOrderDo(
+        [&](const JITDylibSearchOrder &TargetSearchOrder) {
+          auto NewSearchOrder = TargetSearchOrder;
+          assert(
+              !NewSearchOrder.empty() &&
+              NewSearchOrder.front().first == &TargetD &&
+              NewSearchOrder.front().second ==
+                  JITDylibLookupFlags::MatchAllSymbols &&
+              "TargetD must be at the front of its own search order and match "
+              "non-exported symbol");
+          NewSearchOrder.insert(std::next(NewSearchOrder.begin()),
+                                {&ImplD, JITDylibLookupFlags::MatchAllSymbols});
+          ImplD.setSearchOrder(std::move(NewSearchOrder), false);
+        });
     PerDylibResources PDR(ImplD, BuildIndirectStubsManager());
     I = DylibResources.insert(std::make_pair(&TargetD, std::move(PDR))).first;
   }
diff --git a/llvm/lib/ExecutionEngine/Orc/Core.cpp b/llvm/lib/ExecutionEngine/Orc/Core.cpp
index 9e024ba0f10..0814ec1c5f8 100644
--- a/llvm/lib/ExecutionEngine/Orc/Core.cpp
+++ b/llvm/lib/ExecutionEngine/Orc/Core.cpp
@@ -7,6 +7,8 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ExecutionEngine/Orc/Core.h"
+
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/ExecutionEngine/Orc/OrcError.h"
 #include "llvm/IR/Mangler.h"
@@ -77,16 +79,19 @@ bool flagsMatchCLOpts(const JITSymbolFlags &Flags) {
 #endif // NDEBUG
 }
 
-// Prints a set of items, filtered by an user-supplied predicate.
-template <typename Set, typename Pred = PrintAll<typename Set::value_type>>
-class SetPrinter {
+// Prints a sequence of items, filtered by an user-supplied predicate.
+template <typename Sequence,
+          typename Pred = PrintAll<typename Sequence::value_type>>
+class SequencePrinter {
 public:
-  SetPrinter(const Set &S, Pred ShouldPrint = Pred())
-      : S(S), ShouldPrint(std::move(ShouldPrint)) {}
+  SequencePrinter(const Sequence &S, char OpenSeq, char CloseSeq,
+                  Pred ShouldPrint = Pred())
+      : S(S), OpenSeq(OpenSeq), CloseSeq(CloseSeq),
+        ShouldPrint(std::move(ShouldPrint)) {}
 
   void printTo(llvm::raw_ostream &OS) const {
     bool PrintComma = false;
-    OS << "{";
+    OS << OpenSeq;
     for (auto &E : S) {
       if (ShouldPrint(E)) {
         if (PrintComma)
@@ -95,23 +100,26 @@ public:
         PrintComma = true;
       }
     }
-    OS << " }";
+    OS << ' ' << CloseSeq;
   }
 
 private:
-  const Set &S;
+  const Sequence &S;
+  char OpenSeq;
+  char CloseSeq;
   mutable Pred ShouldPrint;
 };
 
-template <typename Set, typename Pred>
-SetPrinter<Set, Pred> printSet(const Set &S, Pred P = Pred()) {
-  return SetPrinter<Set, Pred>(S, std::move(P));
+template <typename Sequence, typename Pred>
+SequencePrinter<Sequence, Pred> printSequence(const Sequence &S, char OpenSeq,
+                                              char CloseSeq, Pred P = Pred()) {
+  return SequencePrinter<Sequence, Pred>(S, OpenSeq, CloseSeq, std::move(P));
 }
 
-// Render a SetPrinter by delegating to its printTo method.
-template <typename Set, typename Pred>
+// Render a SequencePrinter by delegating to its printTo method.
+template <typename Sequence, typename Pred>
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
-                              const SetPrinter<Set, Pred> &Printer) {
+                              const SequencePrinter<Sequence, Pred> &Printer) {
   Printer.printTo(OS);
   return OS;
 }
@@ -147,7 +155,11 @@ raw_ostream &operator<<(raw_ostream &OS, const SymbolStringPtr &Sym) {
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolNameSet &Symbols) {
-  return OS << printSet(Symbols, PrintAll<SymbolStringPtr>());
+  return OS << printSequence(Symbols, '{', '}', PrintAll<SymbolStringPtr>());
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const SymbolNameVector &Symbols) {
+  return OS << printSequence(Symbols, '[', ']', PrintAll<SymbolStringPtr>());
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const JITSymbolFlags &Flags) {
@@ -182,11 +194,13 @@ raw_ostream &operator<<(raw_ostream &OS, const SymbolMap::value_type &KV) {
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolFlagsMap &SymbolFlags) {
-  return OS << printSet(SymbolFlags, PrintSymbolFlagsMapElemsMatchingCLOpts());
+  return OS << printSequence(SymbolFlags, '{', '}',
+                             PrintSymbolFlagsMapElemsMatchingCLOpts());
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolMap &Symbols) {
-  return OS << printSet(Symbols, PrintSymbolMapElemsMatchingCLOpts());
+  return OS << printSequence(Symbols, '{', '}',
+                             PrintSymbolMapElemsMatchingCLOpts());
 }
 
 raw_ostream &operator<<(raw_ostream &OS,
@@ -195,7 +209,8 @@ raw_ostream &operator<<(raw_ostream &OS,
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolDependenceMap &Deps) {
-  return OS << printSet(Deps, PrintAll<SymbolDependenceMap::value_type>());
+  return OS << printSequence(Deps, '{', '}',
+                             PrintAll<SymbolDependenceMap::value_type>());
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const MaterializationUnit &MU) {
@@ -205,16 +220,59 @@ raw_ostream &operator<<(raw_ostream &OS, const MaterializationUnit &MU) {
   return OS << ")";
 }
 
-raw_ostream &operator<<(raw_ostream &OS, const JITDylibSearchList &JDs) {
+raw_ostream &operator<<(raw_ostream &OS, const LookupKind &K) {
+  switch (K) {
+  case LookupKind::Static:
+    return OS << "Static";
+  case LookupKind::DLSym:
+    return OS << "DLSym";
+  }
+  llvm_unreachable("Invalid lookup kind");
+}
+
+raw_ostream &operator<<(raw_ostream &OS,
+                        const JITDylibLookupFlags &JDLookupFlags) {
+  switch (JDLookupFlags) {
+  case JITDylibLookupFlags::MatchExportedSymbolsOnly:
+    return OS << "MatchExportedSymbolsOnly";
+  case JITDylibLookupFlags::MatchAllSymbols:
+    return OS << "MatchAllSymbols";
+  }
+  llvm_unreachable("Invalid JITDylib lookup flags");
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const SymbolLookupFlags &LookupFlags) {
+  switch (LookupFlags) {
+  case SymbolLookupFlags::RequiredSymbol:
+    return OS << "RequiredSymbol";
+  case SymbolLookupFlags::WeaklyReferencedSymbol:
+    return OS << "WeaklyReferencedSymbol";
+  }
+  llvm_unreachable("Invalid symbol lookup flags");
+}
+
+raw_ostream &operator<<(raw_ostream &OS,
+                        const SymbolLookupSet::value_type &KV) {
+  return OS << "(" << KV.first << ", " << KV.second << ")";
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const SymbolLookupSet &LookupSet) {
+  return OS << printSequence(LookupSet, '{', '}',
+                             PrintAll<SymbolLookupSet::value_type>());
+}
+
+raw_ostream &operator<<(raw_ostream &OS,
+                        const JITDylibSearchOrder &SearchOrder) {
   OS << "[";
-  if (!JDs.empty()) {
-    assert(JDs.front().first && "JITDylibList entries must not be null");
-    OS << " (\"" << JDs.front().first->getName() << "\", "
-       << (JDs.front().second ? "true" : "false") << ")";
-    for (auto &KV : make_range(std::next(JDs.begin()), JDs.end())) {
+  if (!SearchOrder.empty()) {
+    assert(SearchOrder.front().first &&
+           "JITDylibList entries must not be null");
+    OS << " (\"" << SearchOrder.front().first->getName() << "\", "
+       << SearchOrder.begin()->second << ")";
+    for (auto &KV :
+         make_range(std::next(SearchOrder.begin(), 1), SearchOrder.end())) {
       assert(KV.first && "JITDylibList entries must not be null");
-      OS << ", (\"" << KV.first->getName() << "\", "
-         << (KV.second ? "true" : "false") << ")";
+      OS << ", (\"" << KV.first->getName() << "\", " << KV.second << ")";
     }
   }
   OS << " ]";
@@ -262,7 +320,13 @@ void FailedToMaterialize::log(raw_ostream &OS) const {
   OS << "Failed to materialize symbols: " << *Symbols;
 }
 
-SymbolsNotFound::SymbolsNotFound(SymbolNameSet Symbols)
+SymbolsNotFound::SymbolsNotFound(SymbolNameSet Symbols) {
+  for (auto &Sym : Symbols)
+    this->Symbols.push_back(Sym);
+  assert(!this->Symbols.empty() && "Can not fail to resolve an empty set");
+}
+
+SymbolsNotFound::SymbolsNotFound(SymbolNameVector Symbols)
     : Symbols(std::move(Symbols)) {
   assert(!this->Symbols.empty() && "Can not fail to resolve an empty set");
 }
@@ -289,7 +353,7 @@ void SymbolsCouldNotBeRemoved::log(raw_ostream &OS) const {
 }
 
 AsynchronousSymbolQuery::AsynchronousSymbolQuery(
-    const SymbolNameSet &Symbols, SymbolState RequiredState,
+    const SymbolLookupSet &Symbols, SymbolState RequiredState,
     SymbolsResolvedCallback NotifyComplete)
     : NotifyComplete(std::move(NotifyComplete)), RequiredState(RequiredState) {
   assert(RequiredState >= SymbolState::Resolved &&
@@ -298,8 +362,8 @@ AsynchronousSymbolQuery::AsynchronousSymbolQuery(
 
   OutstandingSymbolsCount = Symbols.size();
 
-  for (auto &S : Symbols)
-    ResolvedSymbols[S] = nullptr;
+  for (auto &KV : Symbols)
+    ResolvedSymbols[KV.first] = nullptr;
 }
 
 void AsynchronousSymbolQuery::notifySymbolMetRequiredState(
@@ -511,10 +575,10 @@ AbsoluteSymbolsMaterializationUnit::extractFlags(const SymbolMap &Symbols) {
 }
 
 ReExportsMaterializationUnit::ReExportsMaterializationUnit(
-    JITDylib *SourceJD, bool MatchNonExported, SymbolAliasMap Aliases,
-    VModuleKey K)
+    JITDylib *SourceJD, JITDylibLookupFlags SourceJDLookupFlags,
+    SymbolAliasMap Aliases, VModuleKey K)
     : MaterializationUnit(extractFlags(Aliases), std::move(K)),
-      SourceJD(SourceJD), MatchNonExported(MatchNonExported),
+      SourceJD(SourceJD), SourceJDLookupFlags(SourceJDLookupFlags),
       Aliases(std::move(Aliases)) {}
 
 StringRef ReExportsMaterializationUnit::getName() const {
@@ -551,7 +615,7 @@ void ReExportsMaterializationUnit::materialize(
 
   if (!Aliases.empty()) {
     if (SourceJD)
-      R.replace(reexports(*SourceJD, std::move(Aliases), MatchNonExported));
+      R.replace(reexports(*SourceJD, std::move(Aliases), SourceJDLookupFlags));
     else
       R.replace(symbolAliases(std::move(Aliases)));
   }
@@ -572,11 +636,11 @@ void ReExportsMaterializationUnit::materialize(
   // be waitin on a symbol that it itself had to resolve. Usually this will just
   // involve one round and a single query.
 
-  std::vector<std::pair<SymbolNameSet, std::shared_ptr<OnResolveInfo>>>
+  std::vector<std::pair<SymbolLookupSet, std::shared_ptr<OnResolveInfo>>>
       QueryInfos;
   while (!RequestedAliases.empty()) {
     SymbolNameSet ResponsibilitySymbols;
-    SymbolNameSet QuerySymbols;
+    SymbolLookupSet QuerySymbols;
     SymbolAliasMap QueryAliases;
 
     // Collect as many aliases as we can without including a chain.
@@ -587,7 +651,7 @@ void ReExportsMaterializationUnit::materialize(
         continue;
 
       ResponsibilitySymbols.insert(KV.first);
-      QuerySymbols.insert(KV.second.Aliasee);
+      QuerySymbols.add(KV.second.Aliasee);
       QueryAliases[KV.first] = std::move(KV.second);
     }
 
@@ -657,8 +721,9 @@ void ReExportsMaterializationUnit::materialize(
       }
     };
 
-    ES.lookup(JITDylibSearchList({{&SrcJD, MatchNonExported}}), QuerySymbols,
-              SymbolState::Resolved, std::move(OnComplete),
+    ES.lookup(LookupKind::Static,
+              JITDylibSearchOrder({{&SrcJD, SourceJDLookupFlags}}),
+              QuerySymbols, SymbolState::Resolved, std::move(OnComplete),
               std::move(RegisterDependencies));
   }
 }
@@ -681,16 +746,16 @@ ReExportsMaterializationUnit::extractFlags(const SymbolAliasMap &Aliases) {
 
 Expected<SymbolAliasMap>
 buildSimpleReexportsAliasMap(JITDylib &SourceJD, const SymbolNameSet &Symbols) {
-  auto Flags = SourceJD.lookupFlags(Symbols);
+  SymbolLookupSet LookupSet(Symbols);
+  auto Flags = SourceJD.lookupFlags(
+      LookupKind::Static, JITDylibLookupFlags::MatchAllSymbols, LookupSet);
 
   if (!Flags)
     return Flags.takeError();
 
-  if (Flags->size() != Symbols.size()) {
-    SymbolNameSet Unresolved = Symbols;
-    for (auto &KV : *Flags)
-      Unresolved.erase(KV.first);
-    return make_error<SymbolsNotFound>(std::move(Unresolved));
+  if (!LookupSet.empty()) {
+    LookupSet.sortByName();
+    return make_error<SymbolsNotFound>(LookupSet.getSymbolNames());
   }
 
   SymbolAliasMap Result;
@@ -703,32 +768,32 @@ buildSimpleReexportsAliasMap(JITDylib &SourceJD, const SymbolNameSet &Symbols) {
 }
 
 ReexportsGenerator::ReexportsGenerator(JITDylib &SourceJD,
-                                       bool MatchNonExported,
+                                       JITDylibLookupFlags SourceJDLookupFlags,
                                        SymbolPredicate Allow)
-    : SourceJD(SourceJD), MatchNonExported(MatchNonExported),
+    : SourceJD(SourceJD), SourceJDLookupFlags(SourceJDLookupFlags),
       Allow(std::move(Allow)) {}
 
-Expected<SymbolNameSet>
-ReexportsGenerator::tryToGenerate(JITDylib &JD, const SymbolNameSet &Names) {
-  orc::SymbolNameSet Added;
-  orc::SymbolAliasMap AliasMap;
-
-  auto Flags = SourceJD.lookupFlags(Names);
+Error ReexportsGenerator::tryToGenerate(LookupKind K, JITDylib &JD,
+                                        JITDylibLookupFlags JDLookupFlags,
+                                        const SymbolLookupSet &LookupSet) {
+  assert(&JD != &SourceJD && "Cannot re-export from the same dylib");
 
+  // Use lookupFlags to find the subset of symbols that match our lookup.
+  auto Flags = SourceJD.lookupFlags(K, JDLookupFlags, LookupSet);
   if (!Flags)
     return Flags.takeError();
 
-  for (auto &KV : *Flags) {
-    if (Allow && !Allow(KV.first))
-      continue;
-    AliasMap[KV.first] = SymbolAliasMapEntry(KV.first, KV.second);
-    Added.insert(KV.first);
-  }
+  // Create an alias map.
+  orc::SymbolAliasMap AliasMap;
+  for (auto &KV : *Flags)
+    if (!Allow || Allow(KV.first))
+      AliasMap[KV.first] = SymbolAliasMapEntry(KV.first, KV.second);
 
-  if (!Added.empty())
-    cantFail(JD.define(reexports(SourceJD, AliasMap, MatchNonExported)));
+  if (AliasMap.empty())
+    return Error::success();
 
-  return Added;
+  // Define the re-exports.
+  return JD.define(reexports(SourceJD, AliasMap, SourceJDLookupFlags));
 }
 
 JITDylib::DefinitionGenerator::~DefinitionGenerator() {}
@@ -1252,41 +1317,41 @@ void JITDylib::notifyFailed(FailedSymbolsWorklist Worklist) {
     Q->handleFailed(make_error<FailedToMaterialize>(FailedSymbolsMap));
 }
 
-void JITDylib::setSearchOrder(JITDylibSearchList NewSearchOrder,
-                              bool SearchThisJITDylibFirst,
-                              bool MatchNonExportedInThisDylib) {
-  if (SearchThisJITDylibFirst) {
-    if (NewSearchOrder.empty() || NewSearchOrder.front().first != this)
-      NewSearchOrder.insert(NewSearchOrder.begin(),
-                            {this, MatchNonExportedInThisDylib});
-  }
-
-  ES.runSessionLocked([&]() { SearchOrder = std::move(NewSearchOrder); });
-}
-
-void JITDylib::addToSearchOrder(JITDylib &JD, bool MatchNonExported) {
+void JITDylib::setSearchOrder(JITDylibSearchOrder NewSearchOrder,
+                              bool SearchThisJITDylibFirst) {
   ES.runSessionLocked([&]() {
-    SearchOrder.push_back({&JD, MatchNonExported});
+    if (SearchThisJITDylibFirst) {
+      SearchOrder.clear();
+      if (NewSearchOrder.empty() || NewSearchOrder.front().first != this)
+        SearchOrder.push_back(
+            std::make_pair(this, JITDylibLookupFlags::MatchAllSymbols));
+      SearchOrder.insert(SearchOrder.end(), NewSearchOrder.begin(),
+                         NewSearchOrder.end());
+    } else
+      SearchOrder = std::move(NewSearchOrder);
   });
 }
 
+void JITDylib::addToSearchOrder(JITDylib &JD,
+                                JITDylibLookupFlags JDLookupFlags) {
+  ES.runSessionLocked([&]() { SearchOrder.push_back({&JD, JDLookupFlags}); });
+}
+
 void JITDylib::replaceInSearchOrder(JITDylib &OldJD, JITDylib &NewJD,
-                                    bool MatchNonExported) {
+                                    JITDylibLookupFlags JDLookupFlags) {
   ES.runSessionLocked([&]() {
-    auto I = std::find_if(SearchOrder.begin(), SearchOrder.end(),
-                          [&](const JITDylibSearchList::value_type &KV) {
-                            return KV.first == &OldJD;
-                          });
-
-    if (I != SearchOrder.end())
-      *I = {&NewJD, MatchNonExported};
+    for (auto &KV : SearchOrder)
+      if (KV.first == &OldJD) {
+        KV = {&NewJD, JDLookupFlags};
+        break;
+      }
   });
 }
 
 void JITDylib::removeFromSearchOrder(JITDylib &JD) {
   ES.runSessionLocked([&]() {
     auto I = std::find_if(SearchOrder.begin(), SearchOrder.end(),
-                          [&](const JITDylibSearchList::value_type &KV) {
+                          [&](const JITDylibSearchOrder::value_type &KV) {
                             return KV.first == &JD;
                           });
     if (I != SearchOrder.end())
@@ -1349,63 +1414,54 @@ Error JITDylib::remove(const SymbolNameSet &Names) {
   });
 }
 
-Expected<SymbolFlagsMap> JITDylib::lookupFlags(const SymbolNameSet &Names) {
+Expected<SymbolFlagsMap>
+JITDylib::lookupFlags(LookupKind K, JITDylibLookupFlags JDLookupFlags,
+                      SymbolLookupSet LookupSet) {
   return ES.runSessionLocked([&, this]() -> Expected<SymbolFlagsMap> {
     SymbolFlagsMap Result;
-    auto Unresolved = lookupFlagsImpl(Result, Names);
-    if (!Unresolved)
-      return Unresolved.takeError();
+    lookupFlagsImpl(Result, K, JDLookupFlags, LookupSet);
 
-    /// Run any definition generators.
+    // Run any definition generators.
     for (auto &DG : DefGenerators) {
 
-      // Bail out early if we've resolved everything.
-      if (Unresolved->empty())
+      // Bail out early if we found everything.
+      if (LookupSet.empty())
         break;
 
       // Run this generator.
-      auto NewDefs = DG->tryToGenerate(*this, *Unresolved);
-      if (!NewDefs)
-        return NewDefs.takeError();
-
-      if (!NewDefs->empty()) {
-        auto Unresolved2 = lookupFlagsImpl(Result, *NewDefs);
-        if (!Unresolved2)
-          return Unresolved2.takeError();
-        (void)Unresolved2;
-        assert(Unresolved2->empty() &&
-               "All fallback defs should have been found by lookupFlagsImpl");
-      }
+      if (auto Err = DG->tryToGenerate(K, *this, JDLookupFlags, LookupSet))
+        return std::move(Err);
 
-      for (auto &Name : *NewDefs)
-        Unresolved->erase(Name);
+      // Re-try the search.
+      lookupFlagsImpl(Result, K, JDLookupFlags, LookupSet);
     }
+
     return Result;
   });
 }
 
-Expected<SymbolNameSet> JITDylib::lookupFlagsImpl(SymbolFlagsMap &Flags,
-                                                  const SymbolNameSet &Names) {
-  SymbolNameSet Unresolved;
+void JITDylib::lookupFlagsImpl(SymbolFlagsMap &Result, LookupKind K,
+                               JITDylibLookupFlags JDLookupFlags,
+                               SymbolLookupSet &LookupSet) {
 
-  for (auto &Name : Names) {
-    auto I = Symbols.find(Name);
-    if (I != Symbols.end()) {
-      assert(!Flags.count(Name) && "Symbol already present in Flags map");
-      Flags[Name] = I->second.getFlags();
-    } else
-      Unresolved.insert(Name);
-  }
-
-  return Unresolved;
+  LookupSet.forEachWithRemoval(
+      [&](const SymbolStringPtr &Name, SymbolLookupFlags Flags) -> bool {
+        auto I = Symbols.find(Name);
+        if (I == Symbols.end())
+          return false;
+        assert(!Result.count(Name) && "Symbol already present in Flags map");
+        Result[Name] = I->second.getFlags();
+        return true;
+      });
 }
 
-Error JITDylib::lodgeQuery(std::shared_ptr<AsynchronousSymbolQuery> &Q,
-                           SymbolNameSet &Unresolved, bool MatchNonExported,
-                           MaterializationUnitList &MUs) {
+Error JITDylib::lodgeQuery(MaterializationUnitList &MUs,
+                           std::shared_ptr<AsynchronousSymbolQuery> &Q,
+                           LookupKind K, JITDylibLookupFlags JDLookupFlags,
+                           SymbolLookupSet &Unresolved) {
   assert(Q && "Query can not be null");
 
-  if (auto Err = lodgeQueryImpl(Q, Unresolved, MatchNonExported, MUs))
+  if (auto Err = lodgeQueryImpl(MUs, Q, K, JDLookupFlags, Unresolved))
     return Err;
 
   // Run any definition generators.
@@ -1416,104 +1472,86 @@ Error JITDylib::lodgeQuery(std::shared_ptr<AsynchronousSymbolQuery> &Q,
       break;
 
     // Run the generator.
-    auto NewDefs = DG->tryToGenerate(*this, Unresolved);
-
-    // If the generator returns an error then bail out.
-    if (!NewDefs)
-      return NewDefs.takeError();
-
-    // If the generator was able to generate new definitions for any of the
-    // unresolved symbols then lodge the query against them.
-    if (!NewDefs->empty()) {
-      for (auto &D : *NewDefs)
-        Unresolved.erase(D);
-
-      // Lodge query. This can not fail as any new definitions were added
-      // by the generator under the session locked. Since they can't have
-      // started materializing yet the can not have failed.
-      cantFail(lodgeQueryImpl(Q, *NewDefs, MatchNonExported, MUs));
+    if (auto Err = DG->tryToGenerate(K, *this, JDLookupFlags, Unresolved))
+      return Err;
 
-      assert(NewDefs->empty() &&
-             "All fallback defs should have been found by lookupImpl");
-    }
+    // Lodge query. This can not fail as any new definitions were added
+    // by the generator under the session locked. Since they can't have
+    // started materializing yet they can not have failed.
+    cantFail(lodgeQueryImpl(MUs, Q, K, JDLookupFlags, Unresolved));
   }
 
   return Error::success();
 }
 
-Error JITDylib::lodgeQueryImpl(
-    std::shared_ptr<AsynchronousSymbolQuery> &Q, SymbolNameSet &Unresolved,
-    bool MatchNonExported,
-    std::vector<std::unique_ptr<MaterializationUnit>> &MUs) {
-
-  std::vector<SymbolStringPtr> ToRemove;
-  for (auto Name : Unresolved) {
-
-    // Search for the name in Symbols. Skip it if not found.
-    auto SymI = Symbols.find(Name);
-    if (SymI == Symbols.end())
-      continue;
-
-    // If this is a non exported symbol and we're skipping those then skip it.
-    if (!SymI->second.getFlags().isExported() && !MatchNonExported)
-      continue;
-
-    // If we matched against Name in JD, mark it to be removed from the
-    // Unresolved set.
-    ToRemove.push_back(Name);
-
-    // If we matched against this symbol but it is in the error state then
-    // bail out and treat it as a failure to materialize.
-    if (SymI->second.getFlags().hasError()) {
-      auto FailedSymbolsMap = std::make_shared<SymbolDependenceMap>();
-      (*FailedSymbolsMap)[this] = {Name};
-      return make_error<FailedToMaterialize>(std::move(FailedSymbolsMap));
-    }
-
-    // If this symbol already meets the required state for then notify the
-    // query and continue.
-    if (SymI->second.getState() >= Q->getRequiredState()) {
-      Q->notifySymbolMetRequiredState(Name, SymI->second.getSymbol());
-      continue;
-    }
-
-    // Otherwise this symbol does not yet meet the required state. Check whether
-    // it has a materializer attached, and if so prepare to run it.
-    if (SymI->second.hasMaterializerAttached()) {
-      assert(SymI->second.getAddress() == 0 &&
-             "Symbol not resolved but already has address?");
-      auto UMII = UnmaterializedInfos.find(Name);
-      assert(UMII != UnmaterializedInfos.end() &&
-             "Lazy symbol should have UnmaterializedInfo");
-      auto MU = std::move(UMII->second->MU);
-      assert(MU != nullptr && "Materializer should not be null");
-
-      // Move all symbols associated with this MaterializationUnit into
-      // materializing state.
-      for (auto &KV : MU->getSymbols()) {
-        auto SymK = Symbols.find(KV.first);
-        SymK->second.setMaterializerAttached(false);
-        SymK->second.setState(SymbolState::Materializing);
-        UnmaterializedInfos.erase(KV.first);
-      }
+Error JITDylib::lodgeQueryImpl(MaterializationUnitList &MUs,
+                               std::shared_ptr<AsynchronousSymbolQuery> &Q,
+                               LookupKind K, JITDylibLookupFlags JDLookupFlags,
+                               SymbolLookupSet &Unresolved) {
+
+  return Unresolved.forEachWithRemoval(
+      [&](const SymbolStringPtr &Name,
+          SymbolLookupFlags SymLookupFlags) -> Expected<bool> {
+        // Search for name in symbols. If not found then continue without
+        // removal.
+        auto SymI = Symbols.find(Name);
+        if (SymI == Symbols.end())
+          return false;
+
+        // If this is a non exported symbol and we're matching exported symbols
+        // only then skip this symbol without removal.
+        if (!SymI->second.getFlags().isExported() &&
+            JDLookupFlags == JITDylibLookupFlags::MatchExportedSymbolsOnly)
+          return false;
+
+        // If we matched against this symbol but it is in the error state then
+        // bail out and treat it as a failure to materialize.
+        if (SymI->second.getFlags().hasError()) {
+          auto FailedSymbolsMap = std::make_shared<SymbolDependenceMap>();
+          (*FailedSymbolsMap)[this] = {Name};
+          return make_error<FailedToMaterialize>(std::move(FailedSymbolsMap));
+        }
 
-      // Add MU to the list of MaterializationUnits to be materialized.
-      MUs.push_back(std::move(MU));
-    }
+        // If this symbol already meets the required state for then notify the
+        // query, then remove the symbol and continue.
+        if (SymI->second.getState() >= Q->getRequiredState()) {
+          Q->notifySymbolMetRequiredState(Name, SymI->second.getSymbol());
+          return true;
+        }
 
-    // Add the query to the PendingQueries list.
-    assert(SymI->second.isInMaterializationPhase() &&
-           "By this line the symbol should be materializing");
-    auto &MI = MaterializingInfos[Name];
-    MI.addQuery(Q);
-    Q->addQueryDependence(*this, Name);
-  }
+        // Otherwise this symbol does not yet meet the required state. Check
+        // whether it has a materializer attached, and if so prepare to run it.
+        if (SymI->second.hasMaterializerAttached()) {
+          assert(SymI->second.getAddress() == 0 &&
+                 "Symbol not resolved but already has address?");
+          auto UMII = UnmaterializedInfos.find(Name);
+          assert(UMII != UnmaterializedInfos.end() &&
+                 "Lazy symbol should have UnmaterializedInfo");
+          auto MU = std::move(UMII->second->MU);
+          assert(MU != nullptr && "Materializer should not be null");
+
+          // Move all symbols associated with this MaterializationUnit into
+          // materializing state.
+          for (auto &KV : MU->getSymbols()) {
+            auto SymK = Symbols.find(KV.first);
+            SymK->second.setMaterializerAttached(false);
+            SymK->second.setState(SymbolState::Materializing);
+            UnmaterializedInfos.erase(KV.first);
+          }
 
-  // Remove any symbols that we found.
-  for (auto &Name : ToRemove)
-    Unresolved.erase(Name);
+          // Add MU to the list of MaterializationUnits to be materialized.
+          MUs.push_back(std::move(MU));
+        }
 
-  return Error::success();
+        // Add the query to the PendingQueries list and continue, deleting the
+        // element.
+        assert(SymI->second.isInMaterializationPhase() &&
+               "By this line the symbol should be materializing");
+        auto &MI = MaterializingInfos[Name];
+        MI.addQuery(Q);
+        Q->addQueryDependence(*this, Name);
+        return true;
+      });
 }
 
 Expected<SymbolNameSet>
@@ -1526,7 +1564,7 @@ JITDylib::legacyLookup(std::shared_ptr<AsynchronousSymbolQuery> Q,
   bool QueryComplete = false;
   std::vector<std::unique_ptr<MaterializationUnit>> MUs;
 
-  SymbolNameSet Unresolved = std::move(Names);
+  SymbolLookupSet Unresolved(Names);
   auto Err = ES.runSessionLocked([&, this]() -> Error {
     QueryComplete = lookupImpl(Q, MUs, Unresolved);
 
@@ -1538,16 +1576,13 @@ JITDylib::legacyLookup(std::shared_ptr<AsynchronousSymbolQuery> Q,
         break;
 
       assert(!QueryComplete && "query complete but unresolved symbols remain?");
-      auto NewDefs = DG->tryToGenerate(*this, Unresolved);
-      if (!NewDefs)
-        return NewDefs.takeError();
-      if (!NewDefs->empty()) {
-        for (auto &D : *NewDefs)
-          Unresolved.erase(D);
-        QueryComplete = lookupImpl(Q, MUs, *NewDefs);
-        assert(NewDefs->empty() &&
-               "All fallback defs should have been found by lookupImpl");
-      }
+      if (auto Err = DG->tryToGenerate(LookupKind::Static, *this,
+                                       JITDylibLookupFlags::MatchAllSymbols,
+                                       Unresolved))
+        return Err;
+
+      if (!Unresolved.empty())
+        QueryComplete = lookupImpl(Q, MUs, Unresolved);
     }
     return Error::success();
   });
@@ -1575,68 +1610,68 @@ JITDylib::legacyLookup(std::shared_ptr<AsynchronousSymbolQuery> Q,
   // for (auto &MU : MUs)
   //  ES.dispatchMaterialization(*this, std::move(MU));
 
-  return Unresolved;
+  SymbolNameSet RemainingSymbols;
+  for (auto &KV : Unresolved)
+    RemainingSymbols.insert(KV.first);
+
+  return RemainingSymbols;
 }
 
 bool JITDylib::lookupImpl(
     std::shared_ptr<AsynchronousSymbolQuery> &Q,
     std::vector<std::unique_ptr<MaterializationUnit>> &MUs,
-    SymbolNameSet &Unresolved) {
+    SymbolLookupSet &Unresolved) {
   bool QueryComplete = false;
 
   std::vector<SymbolStringPtr> ToRemove;
-  for (auto Name : Unresolved) {
-
-    // Search for the name in Symbols. Skip it if not found.
-    auto SymI = Symbols.find(Name);
-    if (SymI == Symbols.end())
-      continue;
-
-    // If we found Name, mark it to be removed from the Unresolved set.
-    ToRemove.push_back(Name);
-
-    if (SymI->second.getState() >= Q->getRequiredState()) {
-      Q->notifySymbolMetRequiredState(Name, SymI->second.getSymbol());
-      if (Q->isComplete())
-        QueryComplete = true;
-      continue;
-    }
-
-    // If the symbol is lazy, get the MaterialiaztionUnit for it.
-    if (SymI->second.hasMaterializerAttached()) {
-      assert(SymI->second.getAddress() == 0 &&
-             "Lazy symbol should not have a resolved address");
-      auto UMII = UnmaterializedInfos.find(Name);
-      assert(UMII != UnmaterializedInfos.end() &&
-             "Lazy symbol should have UnmaterializedInfo");
-      auto MU = std::move(UMII->second->MU);
-      assert(MU != nullptr && "Materializer should not be null");
-
-      // Kick all symbols associated with this MaterializationUnit into
-      // materializing state.
-      for (auto &KV : MU->getSymbols()) {
-        auto SymK = Symbols.find(KV.first);
-        assert(SymK != Symbols.end() && "Missing symbol table entry");
-        SymK->second.setState(SymbolState::Materializing);
-        SymK->second.setMaterializerAttached(false);
-        UnmaterializedInfos.erase(KV.first);
-      }
+  Unresolved.forEachWithRemoval(
+      [&](const SymbolStringPtr &Name, SymbolLookupFlags Flags) -> bool {
+        // Search for the name in Symbols. Skip without removing if not found.
+        auto SymI = Symbols.find(Name);
+        if (SymI == Symbols.end())
+          return false;
+
+        // If the symbol is already in the required state then notify the query
+        // and remove.
+        if (SymI->second.getState() >= Q->getRequiredState()) {
+          Q->notifySymbolMetRequiredState(Name, SymI->second.getSymbol());
+          if (Q->isComplete())
+            QueryComplete = true;
+          return true;
+        }
 
-      // Add MU to the list of MaterializationUnits to be materialized.
-      MUs.push_back(std::move(MU));
-    }
+        // If the symbol is lazy, get the MaterialiaztionUnit for it.
+        if (SymI->second.hasMaterializerAttached()) {
+          assert(SymI->second.getAddress() == 0 &&
+                 "Lazy symbol should not have a resolved address");
+          auto UMII = UnmaterializedInfos.find(Name);
+          assert(UMII != UnmaterializedInfos.end() &&
+                 "Lazy symbol should have UnmaterializedInfo");
+          auto MU = std::move(UMII->second->MU);
+          assert(MU != nullptr && "Materializer should not be null");
+
+          // Kick all symbols associated with this MaterializationUnit into
+          // materializing state.
+          for (auto &KV : MU->getSymbols()) {
+            auto SymK = Symbols.find(KV.first);
+            assert(SymK != Symbols.end() && "Missing symbol table entry");
+            SymK->second.setState(SymbolState::Materializing);
+            SymK->second.setMaterializerAttached(false);
+            UnmaterializedInfos.erase(KV.first);
+          }
 
-    // Add the query to the PendingQueries list.
-    assert(SymI->second.isInMaterializationPhase() &&
-           "By this line the symbol should be materializing");
-    auto &MI = MaterializingInfos[Name];
-    MI.addQuery(Q);
-    Q->addQueryDependence(*this, Name);
-  }
+          // Add MU to the list of MaterializationUnits to be materialized.
+          MUs.push_back(std::move(MU));
+        }
 
-  // Remove any marked symbols from the Unresolved set.
-  for (auto &Name : ToRemove)
-    Unresolved.erase(Name);
+        // Add the query to the PendingQueries list.
+        assert(SymI->second.isInMaterializationPhase() &&
+               "By this line the symbol should be materializing");
+        auto &MI = MaterializingInfos[Name];
+        MI.addQuery(Q);
+        Q->addQueryDependence(*this, Name);
+        return true;
+      });
 
   return QueryComplete;
 }
@@ -1645,11 +1680,7 @@ void JITDylib::dump(raw_ostream &OS) {
   ES.runSessionLocked([&, this]() {
     OS << "JITDylib \"" << JITDylibName << "\" (ES: "
        << format("0x%016" PRIx64, reinterpret_cast<uintptr_t>(&ES)) << "):\n"
-       << "Search order: [";
-    for (auto &KV : SearchOrder)
-      OS << " (\"" << KV.first->getName() << "\", "
-         << (KV.second ? "all" : "exported only") << ")";
-    OS << " ]\n"
+       << "Search order: " << SearchOrder << "\n"
        << "Symbol table:\n";
 
     for (auto &KV : Symbols) {
@@ -1730,7 +1761,7 @@ JITDylib::MaterializingInfo::takeQueriesMeeting(SymbolState RequiredState) {
 
 JITDylib::JITDylib(ExecutionSession &ES, std::string Name)
     : ES(ES), JITDylibName(std::move(Name)) {
-  SearchOrder.push_back({this, true});
+  SearchOrder.push_back({this, JITDylibLookupFlags::MatchAllSymbols});
 }
 
 Error JITDylib::defineImpl(MaterializationUnit &MU) {
@@ -1898,7 +1929,7 @@ Expected<SymbolMap> ExecutionSession::legacyLookup(
 #endif
 
   auto Query = std::make_shared<AsynchronousSymbolQuery>(
-      Names, RequiredState, std::move(NotifyComplete));
+      SymbolLookupSet(Names), RequiredState, std::move(NotifyComplete));
   // FIXME: This should be run session locked along with the registration code
   // and error reporting below.
   SymbolNameSet UnresolvedSymbols = AsyncLookup(Query, std::move(Names));
@@ -1935,8 +1966,9 @@ Expected<SymbolMap> ExecutionSession::legacyLookup(
 }
 
 void ExecutionSession::lookup(
-    const JITDylibSearchList &SearchOrder, SymbolNameSet Symbols,
-    SymbolState RequiredState, SymbolsResolvedCallback NotifyComplete,
+    LookupKind K, const JITDylibSearchOrder &SearchOrder,
+    SymbolLookupSet Symbols, SymbolState RequiredState,
+    SymbolsResolvedCallback NotifyComplete,
     RegisterDependenciesFunction RegisterDependencies) {
 
   LLVM_DEBUG({
@@ -1965,14 +1997,24 @@ void ExecutionSession::lookup(
                "JITDylibList should not contain duplicate entries");
 
         auto &JD = *KV.first;
-        auto MatchNonExported = KV.second;
-        if (auto Err = JD.lodgeQuery(Q, Unresolved, MatchNonExported,
-                                     CollectedMUsMap[&JD]))
+        auto JDLookupFlags = KV.second;
+        if (auto Err = JD.lodgeQuery(CollectedMUsMap[&JD], Q, K, JDLookupFlags,
+                                     Unresolved))
           return Err;
       }
 
+      // Strip any weakly referenced symbols that were not found.
+      Unresolved.forEachWithRemoval(
+          [&](const SymbolStringPtr &Name, SymbolLookupFlags Flags) {
+            if (Flags == SymbolLookupFlags::WeaklyReferencedSymbol) {
+              Q->dropSymbol(Name);
+              return true;
+            }
+            return false;
+          });
+
       if (!Unresolved.empty())
-        return make_error<SymbolsNotFound>(std::move(Unresolved));
+        return make_error<SymbolsNotFound>(Unresolved.getSymbolNames());
 
       return Error::success();
     };
@@ -2026,8 +2068,8 @@ void ExecutionSession::lookup(
 }
 
 Expected<SymbolMap>
-ExecutionSession::lookup(const JITDylibSearchList &SearchOrder,
-                         const SymbolNameSet &Symbols,
+ExecutionSession::lookup(const JITDylibSearchOrder &SearchOrder,
+                         const SymbolLookupSet &Symbols, LookupKind K,
                          SymbolState RequiredState,
                          RegisterDependenciesFunction RegisterDependencies) {
 #if LLVM_ENABLE_THREADS
@@ -2059,7 +2101,7 @@ ExecutionSession::lookup(const JITDylibSearchList &SearchOrder,
 #endif
 
   // Perform the asynchronous lookup.
-  lookup(SearchOrder, Symbols, RequiredState, NotifyComplete,
+  lookup(K, SearchOrder, Symbols, RequiredState, NotifyComplete,
          RegisterDependencies);
 
 #if LLVM_ENABLE_THREADS
@@ -2080,12 +2122,12 @@ ExecutionSession::lookup(const JITDylibSearchList &SearchOrder,
 }
 
 Expected<JITEvaluatedSymbol>
-ExecutionSession::lookup(const JITDylibSearchList &SearchOrder,
+ExecutionSession::lookup(const JITDylibSearchOrder &SearchOrder,
                          SymbolStringPtr Name) {
-  SymbolNameSet Names({Name});
+  SymbolLookupSet Names({Name});
 
-  if (auto ResultMap = lookup(SearchOrder, std::move(Names), SymbolState::Ready,
-                              NoDependenciesToRegister)) {
+  if (auto ResultMap = lookup(SearchOrder, std::move(Names), LookupKind::Static,
+                              SymbolState::Ready, NoDependenciesToRegister)) {
     assert(ResultMap->size() == 1 && "Unexpected number of results");
     assert(ResultMap->count(Name) && "Missing result for symbol");
     return std::move(ResultMap->begin()->second);
@@ -2096,14 +2138,7 @@ ExecutionSession::lookup(const JITDylibSearchList &SearchOrder,
 Expected<JITEvaluatedSymbol>
 ExecutionSession::lookup(ArrayRef<JITDylib *> SearchOrder,
                          SymbolStringPtr Name) {
-  SymbolNameSet Names({Name});
-
-  JITDylibSearchList FullSearchOrder;
-  FullSearchOrder.reserve(SearchOrder.size());
-  for (auto *JD : SearchOrder)
-    FullSearchOrder.push_back({JD, false});
-
-  return lookup(FullSearchOrder, Name);
+  return lookup(makeJITDylibSearchOrder(SearchOrder), Name);
 }
 
 Expected<JITEvaluatedSymbol>
diff --git a/llvm/lib/ExecutionEngine/Orc/ExecutionUtils.cpp b/llvm/lib/ExecutionEngine/Orc/ExecutionUtils.cpp
index 4a886ac0597..4a3482242db 100644
--- a/llvm/lib/ExecutionEngine/Orc/ExecutionUtils.cpp
+++ b/llvm/lib/ExecutionEngine/Orc/ExecutionUtils.cpp
@@ -118,19 +118,17 @@ void CtorDtorRunner::add(iterator_range<CtorDtorIterator> CtorDtors) {
 Error CtorDtorRunner::run() {
   using CtorDtorTy = void (*)();
 
-  SymbolNameSet Names;
-
-  for (auto &KV : CtorDtorsByPriority) {
-    for (auto &Name : KV.second) {
-      auto Added = Names.insert(Name).second;
-      (void)Added;
-      assert(Added && "Ctor/Dtor names clashed");
-    }
-  }
+  SymbolLookupSet LookupSet;
+  for (auto &KV : CtorDtorsByPriority)
+    for (auto &Name : KV.second)
+      LookupSet.add(Name);
+  assert(!LookupSet.containsDuplicates() &&
+         "Ctor/Dtor list contains duplicates");
 
   auto &ES = JD.getExecutionSession();
-  if (auto CtorDtorMap =
-          ES.lookup(JITDylibSearchList({{&JD, true}}), std::move(Names))) {
+  if (auto CtorDtorMap = ES.lookup(
+          makeJITDylibSearchOrder(&JD, JITDylibLookupFlags::MatchAllSymbols),
+          std::move(LookupSet))) {
     for (auto &KV : CtorDtorsByPriority) {
       for (auto &Name : KV.second) {
         assert(CtorDtorMap->count(Name) && "No entry for Name");
@@ -190,15 +188,16 @@ DynamicLibrarySearchGenerator::Load(const char *FileName, char GlobalPrefix,
       std::move(Lib), GlobalPrefix, std::move(Allow));
 }
 
-Expected<SymbolNameSet>
-DynamicLibrarySearchGenerator::tryToGenerate(JITDylib &JD,
-                                             const SymbolNameSet &Names) {
-  orc::SymbolNameSet Added;
+Error DynamicLibrarySearchGenerator::tryToGenerate(
+    LookupKind K, JITDylib &JD, JITDylibLookupFlags JDLookupFlags,
+    const SymbolLookupSet &Symbols) {
   orc::SymbolMap NewSymbols;
 
   bool HasGlobalPrefix = (GlobalPrefix != '\0');
 
-  for (auto &Name : Names) {
+  for (auto &KV : Symbols) {
+    auto &Name = KV.first;
+
     if ((*Name).empty())
       continue;
 
@@ -211,20 +210,16 @@ DynamicLibrarySearchGenerator::tryToGenerate(JITDylib &JD,
     std::string Tmp((*Name).data() + HasGlobalPrefix,
                     (*Name).size() - HasGlobalPrefix);
     if (void *Addr = Dylib.getAddressOfSymbol(Tmp.c_str())) {
-      Added.insert(Name);
       NewSymbols[Name] = JITEvaluatedSymbol(
           static_cast<JITTargetAddress>(reinterpret_cast<uintptr_t>(Addr)),
           JITSymbolFlags::Exported);
     }
   }
 
-  // Add any new symbols to JD. Since the generator is only called for symbols
-  // that are not already defined, this will never trigger a duplicate
-  // definition error, so we can wrap this call in a 'cantFail'.
-  if (!NewSymbols.empty())
-    cantFail(JD.define(absoluteSymbols(std::move(NewSymbols))));
+  if (NewSymbols.empty())
+    return Error::success();
 
-  return Added;
+  return JD.define(absoluteSymbols(std::move(NewSymbols)));
 }
 
 Expected<std::unique_ptr<StaticLibraryDefinitionGenerator>>
@@ -251,15 +246,24 @@ StaticLibraryDefinitionGenerator::Create(
   return std::move(ADG);
 }
 
-Expected<SymbolNameSet>
-StaticLibraryDefinitionGenerator::tryToGenerate(JITDylib &JD,
-                                                const SymbolNameSet &Names) {
+Error StaticLibraryDefinitionGenerator::tryToGenerate(
+    LookupKind K, JITDylib &JD, JITDylibLookupFlags JDLookupFlags,
+    const SymbolLookupSet &Symbols) {
+
+  // Don't materialize symbols from static archives unless this is a static
+  // lookup.
+  if (K != LookupKind::Static)
+    return Error::success();
+
+  // Bail out early if we've already freed the archive.
+  if (!Archive)
+    return Error::success();
 
   DenseSet<std::pair<StringRef, StringRef>> ChildBufferInfos;
-  SymbolNameSet NewDefs;
 
-  for (const auto &Name : Names) {
-    auto Child = Archive.findSym(*Name);
+  for (const auto &KV : Symbols) {
+    const auto &Name = KV.first;
+    auto Child = Archive->findSym(*Name);
     if (!Child)
       return Child.takeError();
     if (*Child == None)
@@ -269,7 +273,6 @@ StaticLibraryDefinitionGenerator::tryToGenerate(JITDylib &JD,
       return ChildBuffer.takeError();
     ChildBufferInfos.insert(
         {ChildBuffer->getBuffer(), ChildBuffer->getBufferIdentifier()});
-    NewDefs.insert(Name);
   }
 
   for (auto ChildBufferInfo : ChildBufferInfos) {
@@ -278,31 +281,16 @@ StaticLibraryDefinitionGenerator::tryToGenerate(JITDylib &JD,
 
     if (auto Err =
             L.add(JD, MemoryBuffer::getMemBuffer(ChildBufferRef), VModuleKey()))
-      return std::move(Err);
-
-    --UnrealizedObjects;
+      return Err;
   }
 
-  return NewDefs;
+  return Error::success();
 }
 
 StaticLibraryDefinitionGenerator::StaticLibraryDefinitionGenerator(
     ObjectLayer &L, std::unique_ptr<MemoryBuffer> ArchiveBuffer, Error &Err)
     : L(L), ArchiveBuffer(std::move(ArchiveBuffer)),
-      Archive(*this->ArchiveBuffer, Err) {
-
-  if (Err)
-    return;
-
-  Error Err2 = Error::success();
-  for (auto _ : Archive.children(Err2)) {
-    (void)_;
-    ++UnrealizedObjects;
-  }
-
-  // No need to check this: We will leave it to the caller.
-  Err = std::move(Err2);
-}
+      Archive(std::make_unique<object::Archive>(*this->ArchiveBuffer, Err)) {}
 
 } // End namespace orc.
 } // End namespace llvm.
diff --git a/llvm/lib/ExecutionEngine/Orc/IndirectionUtils.cpp b/llvm/lib/ExecutionEngine/Orc/IndirectionUtils.cpp
index 0295db7633d..440935ffe9f 100644
--- a/llvm/lib/ExecutionEngine/Orc/IndirectionUtils.cpp
+++ b/llvm/lib/ExecutionEngine/Orc/IndirectionUtils.cpp
@@ -101,7 +101,10 @@ JITTargetAddress JITCompileCallbackManager::executeCompileCallback(
       Name = I->second;
   }
 
-  if (auto Sym = ES.lookup(JITDylibSearchList({{&CallbacksJD, true}}), Name))
+  if (auto Sym =
+          ES.lookup(makeJITDylibSearchOrder(
+                        &CallbacksJD, JITDylibLookupFlags::MatchAllSymbols),
+                    Name))
     return Sym->getAddress();
   else {
     llvm::dbgs() << "Didn't find callback.\n";
diff --git a/llvm/lib/ExecutionEngine/Orc/LLJIT.cpp b/llvm/lib/ExecutionEngine/Orc/LLJIT.cpp
index 03f22e0c2a2..fb5515ca64d 100644
--- a/llvm/lib/ExecutionEngine/Orc/LLJIT.cpp
+++ b/llvm/lib/ExecutionEngine/Orc/LLJIT.cpp
@@ -56,7 +56,9 @@ Error LLJIT::addObjectFile(JITDylib &JD, std::unique_ptr<MemoryBuffer> Obj) {
 
 Expected<JITEvaluatedSymbol> LLJIT::lookupLinkerMangled(JITDylib &JD,
                                                         StringRef Name) {
-  return ES->lookup(JITDylibSearchList({{&JD, true}}), ES->intern(Name));
+  return ES->lookup(
+      makeJITDylibSearchOrder(&JD, JITDylibLookupFlags::MatchAllSymbols),
+      ES->intern(Name));
 }
 
 std::unique_ptr<ObjectLayer>
diff --git a/llvm/lib/ExecutionEngine/Orc/LazyReexports.cpp b/llvm/lib/ExecutionEngine/Orc/LazyReexports.cpp
index 93aabd817d6..aab490feb8e 100644
--- a/llvm/lib/ExecutionEngine/Orc/LazyReexports.cpp
+++ b/llvm/lib/ExecutionEngine/Orc/LazyReexports.cpp
@@ -50,8 +50,10 @@ LazyCallThroughManager::callThroughToSymbol(JITTargetAddress TrampolineAddr) {
     SourceJD = I->second.first;
     SymbolName = I->second.second;
   }
-  auto LookupResult =
-      ES.lookup(JITDylibSearchList({{SourceJD, true}}), SymbolName);
+
+  auto LookupResult = ES.lookup(
+      makeJITDylibSearchOrder(SourceJD, JITDylibLookupFlags::MatchAllSymbols),
+      SymbolName);
 
   if (!LookupResult) {
     ES.reportError(LookupResult.takeError());
diff --git a/llvm/lib/ExecutionEngine/Orc/Legacy.cpp b/llvm/lib/ExecutionEngine/Orc/Legacy.cpp
index 9f9a6730b2c..67b804c3728 100644
--- a/llvm/lib/ExecutionEngine/Orc/Legacy.cpp
+++ b/llvm/lib/ExecutionEngine/Orc/Legacy.cpp
@@ -37,7 +37,8 @@ void JITSymbolResolverAdapter::lookup(const LookupSet &Symbols,
   };
 
   auto Q = std::make_shared<AsynchronousSymbolQuery>(
-      InternedSymbols, SymbolState::Resolved, std::move(OnResolvedWithUnwrap));
+      SymbolLookupSet(InternedSymbols), SymbolState::Resolved,
+      std::move(OnResolvedWithUnwrap));
 
   auto Unresolved = R.lookup(Q, InternedSymbols);
   if (Unresolved.empty()) {
diff --git a/llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp b/llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp
index 874decb2ade..be0ce4a1d75 100644
--- a/llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp
+++ b/llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp
@@ -47,18 +47,28 @@ public:
     MR.failMaterialization();
   }
 
-  void lookup(const DenseSet<StringRef> &Symbols,
+  void lookup(const LookupMap &Symbols,
               std::unique_ptr<JITLinkAsyncLookupContinuation> LC) override {
 
-    JITDylibSearchList SearchOrder;
+    JITDylibSearchOrder SearchOrder;
     MR.getTargetJITDylib().withSearchOrderDo(
-        [&](const JITDylibSearchList &JDs) { SearchOrder = JDs; });
+        [&](const JITDylibSearchOrder &O) { SearchOrder = O; });
 
     auto &ES = Layer.getExecutionSession();
 
-    SymbolNameSet InternedSymbols;
-    for (auto &S : Symbols)
-      InternedSymbols.insert(ES.intern(S));
+    SymbolLookupSet LookupSet;
+    for (auto &KV : Symbols) {
+      orc::SymbolLookupFlags LookupFlags;
+      switch (KV.second) {
+      case jitlink::SymbolLookupFlags::RequiredSymbol:
+        LookupFlags = orc::SymbolLookupFlags::RequiredSymbol;
+        break;
+      case jitlink::SymbolLookupFlags::WeaklyReferencedSymbol:
+        LookupFlags = orc::SymbolLookupFlags::WeaklyReferencedSymbol;
+        break;
+      }
+      LookupSet.add(ES.intern(KV.first), LookupFlags);
+    }
 
     // OnResolve -- De-intern the symbols and pass the result to the linker.
     auto OnResolve = [this, LookupContinuation = std::move(LC)](
@@ -74,8 +84,9 @@ public:
       }
     };
 
-    ES.lookup(SearchOrder, std::move(InternedSymbols), SymbolState::Resolved,
-              std::move(OnResolve), [this](const SymbolDependenceMap &Deps) {
+    ES.lookup(LookupKind::Static, SearchOrder, std::move(LookupSet),
+              SymbolState::Resolved, std::move(OnResolve),
+              [this](const SymbolDependenceMap &Deps) {
                 registerDependencies(Deps);
               });
   }
diff --git a/llvm/lib/ExecutionEngine/Orc/RTDyldObjectLinkingLayer.cpp b/llvm/lib/ExecutionEngine/Orc/RTDyldObjectLinkingLayer.cpp
index 939cd539d1f..3344bd4d53f 100644
--- a/llvm/lib/ExecutionEngine/Orc/RTDyldObjectLinkingLayer.cpp
+++ b/llvm/lib/ExecutionEngine/Orc/RTDyldObjectLinkingLayer.cpp
@@ -19,11 +19,11 @@ public:
 
   void lookup(const LookupSet &Symbols, OnResolvedFunction OnResolved) {
     auto &ES = MR.getTargetJITDylib().getExecutionSession();
-    SymbolNameSet InternedSymbols;
+    SymbolLookupSet InternedSymbols;
 
     // Intern the requested symbols: lookup takes interned strings.
     for (auto &S : Symbols)
-      InternedSymbols.insert(ES.intern(S));
+      InternedSymbols.add(ES.intern(S));
 
     // Build an OnResolve callback to unwrap the interned strings and pass them
     // to the OnResolved callback.
@@ -46,11 +46,12 @@ public:
       MR.addDependenciesForAll(Deps);
     };
 
-    JITDylibSearchList SearchOrder;
+    JITDylibSearchOrder SearchOrder;
     MR.getTargetJITDylib().withSearchOrderDo(
-        [&](const JITDylibSearchList &JDs) { SearchOrder = JDs; });
-    ES.lookup(SearchOrder, InternedSymbols, SymbolState::Resolved,
-              std::move(OnResolvedWithUnwrap), RegisterDependencies);
+        [&](const JITDylibSearchOrder &JDs) { SearchOrder = JDs; });
+    ES.lookup(LookupKind::Static, SearchOrder, InternedSymbols,
+              SymbolState::Resolved, std::move(OnResolvedWithUnwrap),
+              RegisterDependencies);
   }
 
   Expected<LookupSet> getResponsibilitySet(const LookupSet &Symbols) {