lib/ExecutionEngine/Orc/Core.cpp

   1 //===--- Core.cpp - Core ORC APIs (MaterializationUnit, JITDylib, etc.) ---===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ExecutionEngine/Orc/Core.h"
  10 #include "llvm/Config/llvm-config.h"
  11 #include "llvm/ExecutionEngine/Orc/OrcError.h"
  12 #include "llvm/IR/Mangler.h"
  13 #include "llvm/Support/CommandLine.h"
  14 #include "llvm/Support/Debug.h"
  15 #include "llvm/Support/Format.h"
  16
  17 #if LLVM_ENABLE_THREADS
  18 #include <future>
  19 #endif
  20
  21 #define DEBUG_TYPE "orc"
  22
  23 using namespace llvm;
  24
  25 namespace {
  26
  27 #ifndef NDEBUG
  28
  29 cl::opt<bool> PrintHidden("debug-orc-print-hidden", cl::init(true),
  30                           cl::desc("debug print hidden symbols defined by "
  31                                    "materialization units"),
  32                           cl::Hidden);
  33
  34 cl::opt<bool> PrintCallable("debug-orc-print-callable", cl::init(true),
  35                             cl::desc("debug print callable symbols defined by "
  36                                      "materialization units"),
  37                             cl::Hidden);
  38
  39 cl::opt<bool> PrintData("debug-orc-print-data", cl::init(true),
  40                         cl::desc("debug print data symbols defined by "
  41                                  "materialization units"),
  42                         cl::Hidden);
  43
  44 #endif // NDEBUG
  45
  46 // SetPrinter predicate that prints every element.
  47 template <typename T> struct PrintAll {
  48   bool operator()(const T &E) { return true; }
  49 };
  50
  51 bool anyPrintSymbolOptionSet() {
  52 #ifndef NDEBUG
  53   return PrintHidden || PrintCallable || PrintData;
  54 #else
  55   return false;
  56 #endif // NDEBUG
  57 }
  58
  59 bool flagsMatchCLOpts(const JITSymbolFlags &Flags) {
  60 #ifndef NDEBUG
  61   // Bail out early if this is a hidden symbol and we're not printing hiddens.
  62   if (!PrintHidden && !Flags.isExported())
  63     return false;
  64
  65   // Return true if this is callable and we're printing callables.
  66   if (PrintCallable && Flags.isCallable())
  67     return true;
  68
  69   // Return true if this is data and we're printing data.
  70   if (PrintData && !Flags.isCallable())
  71     return true;
  72
  73   // otherwise return false.
  74   return false;
  75 #else
  76   return false;
  77 #endif // NDEBUG
  78 }
  79
  80 // Prints a set of items, filtered by an user-supplied predicate.
  81 template <typename Set, typename Pred = PrintAll<typename Set::value_type>>
  82 class SetPrinter {
  83 public:
  84   SetPrinter(const Set &S, Pred ShouldPrint = Pred())
  85       : S(S), ShouldPrint(std::move(ShouldPrint)) {}
  86
  87   void printTo(llvm::raw_ostream &OS) const {
  88     bool PrintComma = false;
  89     OS << "{";
  90     for (auto &E : S) {
  91       if (ShouldPrint(E)) {
  92         if (PrintComma)
  93           OS << ',';
  94         OS << ' ' << E;
  95         PrintComma = true;
  96       }
  97     }
  98     OS << " }";
  99   }
 100
 101 private:
 102   const Set &S;
 103   mutable Pred ShouldPrint;
 104 };
 105
 106 template <typename Set, typename Pred>
 107 SetPrinter<Set, Pred> printSet(const Set &S, Pred P = Pred()) {
 108   return SetPrinter<Set, Pred>(S, std::move(P));
 109 }
 110
 111 // Render a SetPrinter by delegating to its printTo method.
 112 template <typename Set, typename Pred>
 113 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
 114                               const SetPrinter<Set, Pred> &Printer) {
 115   Printer.printTo(OS);
 116   return OS;
 117 }
 118
 119 struct PrintSymbolFlagsMapElemsMatchingCLOpts {
 120   bool operator()(const orc::SymbolFlagsMap::value_type &KV) {
 121     return flagsMatchCLOpts(KV.second);
 122   }
 123 };
 124
 125 struct PrintSymbolMapElemsMatchingCLOpts {
 126   bool operator()(const orc::SymbolMap::value_type &KV) {
 127     return flagsMatchCLOpts(KV.second.getFlags());
 128   }
 129 };
 130
 131 } // end anonymous namespace
 132
 133 namespace llvm {
 134 namespace orc {
 135
 136 char FailedToMaterialize::ID = 0;
 137 char SymbolsNotFound::ID = 0;
 138 char SymbolsCouldNotBeRemoved::ID = 0;
 139
 140 RegisterDependenciesFunction NoDependenciesToRegister =
 141     RegisterDependenciesFunction();
 142
 143 void MaterializationUnit::anchor() {}
 144
 145 raw_ostream &operator<<(raw_ostream &OS, const SymbolStringPtr &Sym) {
 146   return OS << *Sym;
 147 }
 148
 149 raw_ostream &operator<<(raw_ostream &OS, const SymbolNameSet &Symbols) {
 150   return OS << printSet(Symbols, PrintAll<SymbolStringPtr>());
 151 }
 152
 153 raw_ostream &operator<<(raw_ostream &OS, const JITSymbolFlags &Flags) {
 154   if (Flags.hasError())
 155     OS << "[*ERROR*]";
 156   if (Flags.isCallable())
 157     OS << "[Callable]";
 158   else
 159     OS << "[Data]";
 160   if (Flags.isWeak())
 161     OS << "[Weak]";
 162   else if (Flags.isCommon())
 163     OS << "[Common]";
 164
 165   if (!Flags.isExported())
 166     OS << "[Hidden]";
 167
 168   return OS;
 169 }
 170
 171 raw_ostream &operator<<(raw_ostream &OS, const JITEvaluatedSymbol &Sym) {
 172   return OS << format("0x%016" PRIx64, Sym.getAddress()) << " "
 173             << Sym.getFlags();
 174 }
 175
 176 raw_ostream &operator<<(raw_ostream &OS, const SymbolFlagsMap::value_type &KV) {
 177   return OS << "(\"" << KV.first << "\", " << KV.second << ")";
 178 }
 179
 180 raw_ostream &operator<<(raw_ostream &OS, const SymbolMap::value_type &KV) {
 181   return OS << "(\"" << KV.first << "\": " << KV.second << ")";
 182 }
 183
 184 raw_ostream &operator<<(raw_ostream &OS, const SymbolFlagsMap &SymbolFlags) {
 185   return OS << printSet(SymbolFlags, PrintSymbolFlagsMapElemsMatchingCLOpts());
 186 }
 187
 188 raw_ostream &operator<<(raw_ostream &OS, const SymbolMap &Symbols) {
 189   return OS << printSet(Symbols, PrintSymbolMapElemsMatchingCLOpts());
 190 }
 191
 192 raw_ostream &operator<<(raw_ostream &OS,
 193                         const SymbolDependenceMap::value_type &KV) {
 194   return OS << "(" << KV.first << ", " << KV.second << ")";
 195 }
 196
 197 raw_ostream &operator<<(raw_ostream &OS, const SymbolDependenceMap &Deps) {
 198   return OS << printSet(Deps, PrintAll<SymbolDependenceMap::value_type>());
 199 }
 200
 201 raw_ostream &operator<<(raw_ostream &OS, const MaterializationUnit &MU) {
 202   OS << "MU@" << &MU << " (\"" << MU.getName() << "\"";
 203   if (anyPrintSymbolOptionSet())
 204     OS << ", " << MU.getSymbols();
 205   return OS << ")";
 206 }
 207
 208 raw_ostream &operator<<(raw_ostream &OS, const JITDylibSearchList &JDs) {
 209   OS << "[";
 210   if (!JDs.empty()) {
 211     assert(JDs.front().first && "JITDylibList entries must not be null");
 212     OS << " (\"" << JDs.front().first->getName() << "\", "
 213        << (JDs.front().second ? "true" : "false") << ")";
 214     for (auto &KV : make_range(std::next(JDs.begin()), JDs.end())) {
 215       assert(KV.first && "JITDylibList entries must not be null");
 216       OS << ", (\"" << KV.first->getName() << "\", "
 217          << (KV.second ? "true" : "false") << ")";
 218     }
 219   }
 220   OS << " ]";
 221   return OS;
 222 }
 223
 224 raw_ostream &operator<<(raw_ostream &OS, const SymbolAliasMap &Aliases) {
 225   OS << "{";
 226   for (auto &KV : Aliases)
 227     OS << " " << *KV.first << ": " << KV.second.Aliasee << " "
 228        << KV.second.AliasFlags;
 229   OS << " }\n";
 230   return OS;
 231 }
 232
 233 raw_ostream &operator<<(raw_ostream &OS, const SymbolState &S) {
 234   switch (S) {
 235   case SymbolState::Invalid:
 236     return OS << "Invalid";
 237   case SymbolState::NeverSearched:
 238     return OS << "Never-Searched";
 239   case SymbolState::Materializing:
 240     return OS << "Materializing";
 241   case SymbolState::Resolved:
 242     return OS << "Resolved";
 243   case SymbolState::Emitted:
 244     return OS << "Emitted";
 245   case SymbolState::Ready:
 246     return OS << "Ready";
 247   }
 248   llvm_unreachable("Invalid state");
 249 }
 250
 251 FailedToMaterialize::FailedToMaterialize(
 252     std::shared_ptr<SymbolDependenceMap> Symbols)
 253     : Symbols(std::move(Symbols)) {
 254   assert(!this->Symbols->empty() && "Can not fail to resolve an empty set");
 255 }
 256
 257 std::error_code FailedToMaterialize::convertToErrorCode() const {
 258   return orcError(OrcErrorCode::UnknownORCError);
 259 }
 260
 261 void FailedToMaterialize::log(raw_ostream &OS) const {
 262   OS << "Failed to materialize symbols: " << *Symbols;
 263 }
 264
 265 SymbolsNotFound::SymbolsNotFound(SymbolNameSet Symbols)
 266     : Symbols(std::move(Symbols)) {
 267   assert(!this->Symbols.empty() && "Can not fail to resolve an empty set");
 268 }
 269
 270 std::error_code SymbolsNotFound::convertToErrorCode() const {
 271   return orcError(OrcErrorCode::UnknownORCError);
 272 }
 273
 274 void SymbolsNotFound::log(raw_ostream &OS) const {
 275   OS << "Symbols not found: " << Symbols;
 276 }
 277
 278 SymbolsCouldNotBeRemoved::SymbolsCouldNotBeRemoved(SymbolNameSet Symbols)
 279     : Symbols(std::move(Symbols)) {
 280   assert(!this->Symbols.empty() && "Can not fail to resolve an empty set");
 281 }
 282
 283 std::error_code SymbolsCouldNotBeRemoved::convertToErrorCode() const {
 284   return orcError(OrcErrorCode::UnknownORCError);
 285 }
 286
 287 void SymbolsCouldNotBeRemoved::log(raw_ostream &OS) const {
 288   OS << "Symbols could not be removed: " << Symbols;
 289 }
 290
 291 AsynchronousSymbolQuery::AsynchronousSymbolQuery(
 292     const SymbolNameSet &Symbols, SymbolState RequiredState,
 293     SymbolsResolvedCallback NotifyComplete)
 294     : NotifyComplete(std::move(NotifyComplete)), RequiredState(RequiredState) {
 295   assert(RequiredState >= SymbolState::Resolved &&
 296          "Cannot query for a symbols that have not reached the resolve state "
 297          "yet");
 298
 299   OutstandingSymbolsCount = Symbols.size();
 300
 301   for (auto &S : Symbols)
 302     ResolvedSymbols[S] = nullptr;
 303 }
 304
 305 void AsynchronousSymbolQuery::notifySymbolMetRequiredState(
 306     const SymbolStringPtr &Name, JITEvaluatedSymbol Sym) {
 307   auto I = ResolvedSymbols.find(Name);
 308   assert(I != ResolvedSymbols.end() &&
 309          "Resolving symbol outside the requested set");
 310   assert(I->second.getAddress() == 0 && "Redundantly resolving symbol Name");
 311   I->second = std::move(Sym);
 312   --OutstandingSymbolsCount;
 313 }
 314
 315 void AsynchronousSymbolQuery::handleComplete() {
 316   assert(OutstandingSymbolsCount == 0 &&
 317          "Symbols remain, handleComplete called prematurely");
 318
 319   auto TmpNotifyComplete = std::move(NotifyComplete);
 320   NotifyComplete = SymbolsResolvedCallback();
 321   TmpNotifyComplete(std::move(ResolvedSymbols));
 322 }
 323
 324 bool AsynchronousSymbolQuery::canStillFail() { return !!NotifyComplete; }
 325
 326 void AsynchronousSymbolQuery::handleFailed(Error Err) {
 327   assert(QueryRegistrations.empty() && ResolvedSymbols.empty() &&
 328          OutstandingSymbolsCount == 0 &&
 329          "Query should already have been abandoned");
 330   NotifyComplete(std::move(Err));
 331   NotifyComplete = SymbolsResolvedCallback();
 332 }
 333
 334 void AsynchronousSymbolQuery::addQueryDependence(JITDylib &JD,
 335                                                  SymbolStringPtr Name) {
 336   bool Added = QueryRegistrations[&JD].insert(std::move(Name)).second;
 337   (void)Added;
 338   assert(Added && "Duplicate dependence notification?");
 339 }
 340
 341 void AsynchronousSymbolQuery::removeQueryDependence(
 342     JITDylib &JD, const SymbolStringPtr &Name) {
 343   auto QRI = QueryRegistrations.find(&JD);
 344   assert(QRI != QueryRegistrations.end() &&
 345          "No dependencies registered for JD");
 346   assert(QRI->second.count(Name) && "No dependency on Name in JD");
 347   QRI->second.erase(Name);
 348   if (QRI->second.empty())
 349     QueryRegistrations.erase(QRI);
 350 }
 351
 352 void AsynchronousSymbolQuery::detach() {
 353   ResolvedSymbols.clear();
 354   OutstandingSymbolsCount = 0;
 355   for (auto &KV : QueryRegistrations)
 356     KV.first->detachQueryHelper(*this, KV.second);
 357   QueryRegistrations.clear();
 358 }
 359
 360 MaterializationResponsibility::MaterializationResponsibility(
 361     JITDylib &JD, SymbolFlagsMap SymbolFlags, VModuleKey K)
 362     : JD(JD), SymbolFlags(std::move(SymbolFlags)), K(std::move(K)) {
 363   assert(!this->SymbolFlags.empty() && "Materializing nothing?");
 364 }
 365
 366 MaterializationResponsibility::~MaterializationResponsibility() {
 367   assert(SymbolFlags.empty() &&
 368          "All symbols should have been explicitly materialized or failed");
 369 }
 370
 371 SymbolNameSet MaterializationResponsibility::getRequestedSymbols() const {
 372   return JD.getRequestedSymbols(SymbolFlags);
 373 }
 374
 375 Error MaterializationResponsibility::notifyResolved(const SymbolMap &Symbols) {
 376   LLVM_DEBUG({
 377     dbgs() << "In " << JD.getName() << " resolving " << Symbols << "\n";
 378   });
 379 #ifndef NDEBUG
 380   for (auto &KV : Symbols) {
 381     auto I = SymbolFlags.find(KV.first);
 382     assert(I != SymbolFlags.end() &&
 383            "Resolving symbol outside this responsibility set");
 384     if (I->second.isWeak())
 385       assert(I->second == (KV.second.getFlags() | JITSymbolFlags::Weak) &&
 386              "Resolving symbol with incorrect flags");
 387     else
 388       assert(I->second == KV.second.getFlags() &&
 389              "Resolving symbol with incorrect flags");
 390   }
 391 #endif
 392
 393   return JD.resolve(Symbols);
 394 }
 395
 396 Error MaterializationResponsibility::notifyEmitted() {
 397
 398   LLVM_DEBUG({
 399     dbgs() << "In " << JD.getName() << " emitting " << SymbolFlags << "\n";
 400   });
 401
 402   if (auto Err = JD.emit(SymbolFlags))
 403     return Err;
 404
 405   SymbolFlags.clear();
 406   return Error::success();
 407 }
 408
 409 Error MaterializationResponsibility::defineMaterializing(
 410     const SymbolFlagsMap &NewSymbolFlags) {
 411   // Add the given symbols to this responsibility object.
 412   // It's ok if we hit a duplicate here: In that case the new version will be
 413   // discarded, and the JITDylib::defineMaterializing method will return a
 414   // duplicate symbol error.
 415   for (auto &KV : NewSymbolFlags)
 416     SymbolFlags.insert(KV);
 417
 418   return JD.defineMaterializing(NewSymbolFlags);
 419 }
 420
 421 void MaterializationResponsibility::failMaterialization() {
 422
 423   LLVM_DEBUG({
 424     dbgs() << "In " << JD.getName() << " failing materialization for "
 425            << SymbolFlags << "\n";
 426   });
 427
 428   JITDylib::FailedSymbolsWorklist Worklist;
 429
 430   for (auto &KV : SymbolFlags)
 431     Worklist.push_back(std::make_pair(&JD, KV.first));
 432   SymbolFlags.clear();
 433
 434   JD.notifyFailed(std::move(Worklist));
 435 }
 436
 437 void MaterializationResponsibility::replace(
 438     std::unique_ptr<MaterializationUnit> MU) {
 439   for (auto &KV : MU->getSymbols())
 440     SymbolFlags.erase(KV.first);
 441
 442   LLVM_DEBUG(JD.getExecutionSession().runSessionLocked([&]() {
 443     dbgs() << "In " << JD.getName() << " replacing symbols with " << *MU
 444            << "\n";
 445   }););
 446
 447   JD.replace(std::move(MU));
 448 }
 449
 450 MaterializationResponsibility
 451 MaterializationResponsibility::delegate(const SymbolNameSet &Symbols,
 452                                         VModuleKey NewKey) {
 453
 454   if (NewKey == VModuleKey())
 455     NewKey = K;
 456
 457   SymbolFlagsMap DelegatedFlags;
 458
 459   for (auto &Name : Symbols) {
 460     auto I = SymbolFlags.find(Name);
 461     assert(I != SymbolFlags.end() &&
 462            "Symbol is not tracked by this MaterializationResponsibility "
 463            "instance");
 464
 465     DelegatedFlags[Name] = std::move(I->second);
 466     SymbolFlags.erase(I);
 467   }
 468
 469   return MaterializationResponsibility(JD, std::move(DelegatedFlags),
 470                                        std::move(NewKey));
 471 }
 472
 473 void MaterializationResponsibility::addDependencies(
 474     const SymbolStringPtr &Name, const SymbolDependenceMap &Dependencies) {
 475   assert(SymbolFlags.count(Name) &&
 476          "Symbol not covered by this MaterializationResponsibility instance");
 477   JD.addDependencies(Name, Dependencies);
 478 }
 479
 480 void MaterializationResponsibility::addDependenciesForAll(
 481     const SymbolDependenceMap &Dependencies) {
 482   for (auto &KV : SymbolFlags)
 483     JD.addDependencies(KV.first, Dependencies);
 484 }
 485
 486 AbsoluteSymbolsMaterializationUnit::AbsoluteSymbolsMaterializationUnit(
 487     SymbolMap Symbols, VModuleKey K)
 488     : MaterializationUnit(extractFlags(Symbols), std::move(K)),
 489       Symbols(std::move(Symbols)) {}
 490
 491 StringRef AbsoluteSymbolsMaterializationUnit::getName() const {
 492   return "<Absolute Symbols>";
 493 }
 494
 495 void AbsoluteSymbolsMaterializationUnit::materialize(
 496     MaterializationResponsibility R) {
 497   // No dependencies, so these calls can't fail.
 498   cantFail(R.notifyResolved(Symbols));
 499   cantFail(R.notifyEmitted());
 500 }
 501
 502 void AbsoluteSymbolsMaterializationUnit::discard(const JITDylib &JD,
 503                                                  const SymbolStringPtr &Name) {
 504   assert(Symbols.count(Name) && "Symbol is not part of this MU");
 505   Symbols.erase(Name);
 506 }
 507
 508 SymbolFlagsMap
 509 AbsoluteSymbolsMaterializationUnit::extractFlags(const SymbolMap &Symbols) {
 510   SymbolFlagsMap Flags;
 511   for (const auto &KV : Symbols)
 512     Flags[KV.first] = KV.second.getFlags();
 513   return Flags;
 514 }
 515
 516 ReExportsMaterializationUnit::ReExportsMaterializationUnit(
 517     JITDylib *SourceJD, bool MatchNonExported, SymbolAliasMap Aliases,
 518     VModuleKey K)
 519     : MaterializationUnit(extractFlags(Aliases), std::move(K)),
 520       SourceJD(SourceJD), MatchNonExported(MatchNonExported),
 521       Aliases(std::move(Aliases)) {}
 522
 523 StringRef ReExportsMaterializationUnit::getName() const {
 524   return "<Reexports>";
 525 }
 526
 527 void ReExportsMaterializationUnit::materialize(
 528     MaterializationResponsibility R) {
 529
 530   auto &ES = R.getTargetJITDylib().getExecutionSession();
 531   JITDylib &TgtJD = R.getTargetJITDylib();
 532   JITDylib &SrcJD = SourceJD ? *SourceJD : TgtJD;
 533
 534   // Find the set of requested aliases and aliasees. Return any unrequested
 535   // aliases back to the JITDylib so as to not prematurely materialize any
 536   // aliasees.
 537   auto RequestedSymbols = R.getRequestedSymbols();
 538   SymbolAliasMap RequestedAliases;
 539
 540   for (auto &Name : RequestedSymbols) {
 541     auto I = Aliases.find(Name);
 542     assert(I != Aliases.end() && "Symbol not found in aliases map?");
 543     RequestedAliases[Name] = std::move(I->second);
 544     Aliases.erase(I);
 545   }
 546
 547   LLVM_DEBUG({
 548     ES.runSessionLocked([&]() {
 549       dbgs() << "materializing reexports: target = " << TgtJD.getName()
 550              << ", source = " << SrcJD.getName() << " " << RequestedAliases
 551              << "\n";
 552     });
 553   });
 554
 555   if (!Aliases.empty()) {
 556     if (SourceJD)
 557       R.replace(reexports(*SourceJD, std::move(Aliases), MatchNonExported));
 558     else
 559       R.replace(symbolAliases(std::move(Aliases)));
 560   }
 561
 562   // The OnResolveInfo struct will hold the aliases and responsibilty for each
 563   // query in the list.
 564   struct OnResolveInfo {
 565     OnResolveInfo(MaterializationResponsibility R, SymbolAliasMap Aliases)
 566         : R(std::move(R)), Aliases(std::move(Aliases)) {}
 567
 568     MaterializationResponsibility R;
 569     SymbolAliasMap Aliases;
 570   };
 571
 572   // Build a list of queries to issue. In each round we build the largest set of
 573   // aliases that we can resolve without encountering a chain definition of the
 574   // form Foo -> Bar, Bar -> Baz. Such a form would deadlock as the query would
 575   // be waitin on a symbol that it itself had to resolve. Usually this will just
 576   // involve one round and a single query.
 577
 578   std::vector<std::pair<SymbolNameSet, std::shared_ptr<OnResolveInfo>>>
 579       QueryInfos;
 580   while (!RequestedAliases.empty()) {
 581     SymbolNameSet ResponsibilitySymbols;
 582     SymbolNameSet QuerySymbols;
 583     SymbolAliasMap QueryAliases;
 584
 585     // Collect as many aliases as we can without including a chain.
 586     for (auto &KV : RequestedAliases) {
 587       // Chain detected. Skip this symbol for this round.
 588       if (&SrcJD == &TgtJD && (QueryAliases.count(KV.second.Aliasee) ||
 589                                RequestedAliases.count(KV.second.Aliasee)))
 590         continue;
 591
 592       ResponsibilitySymbols.insert(KV.first);
 593       QuerySymbols.insert(KV.second.Aliasee);
 594       QueryAliases[KV.first] = std::move(KV.second);
 595     }
 596
 597     // Remove the aliases collected this round from the RequestedAliases map.
 598     for (auto &KV : QueryAliases)
 599       RequestedAliases.erase(KV.first);
 600
 601     assert(!QuerySymbols.empty() && "Alias cycle detected!");
 602
 603     auto QueryInfo = std::make_shared<OnResolveInfo>(
 604         R.delegate(ResponsibilitySymbols), std::move(QueryAliases));
 605     QueryInfos.push_back(
 606         make_pair(std::move(QuerySymbols), std::move(QueryInfo)));
 607   }
 608
 609   // Issue the queries.
 610   while (!QueryInfos.empty()) {
 611     auto QuerySymbols = std::move(QueryInfos.back().first);
 612     auto QueryInfo = std::move(QueryInfos.back().second);
 613
 614     QueryInfos.pop_back();
 615
 616     auto RegisterDependencies = [QueryInfo,
 617                                  &SrcJD](const SymbolDependenceMap &Deps) {
 618       // If there were no materializing symbols, just bail out.
 619       if (Deps.empty())
 620         return;
 621
 622       // Otherwise the only deps should be on SrcJD.
 623       assert(Deps.size() == 1 && Deps.count(&SrcJD) &&
 624              "Unexpected dependencies for reexports");
 625
 626       auto &SrcJDDeps = Deps.find(&SrcJD)->second;
 627       SymbolDependenceMap PerAliasDepsMap;
 628       auto &PerAliasDeps = PerAliasDepsMap[&SrcJD];
 629
 630       for (auto &KV : QueryInfo->Aliases)
 631         if (SrcJDDeps.count(KV.second.Aliasee)) {
 632           PerAliasDeps = {KV.second.Aliasee};
 633           QueryInfo->R.addDependencies(KV.first, PerAliasDepsMap);
 634         }
 635     };
 636
 637     auto OnComplete = [QueryInfo](Expected<SymbolMap> Result) {
 638       auto &ES = QueryInfo->R.getTargetJITDylib().getExecutionSession();
 639       if (Result) {
 640         SymbolMap ResolutionMap;
 641         for (auto &KV : QueryInfo->Aliases) {
 642           assert(Result->count(KV.second.Aliasee) &&
 643                  "Result map missing entry?");
 644           ResolutionMap[KV.first] = JITEvaluatedSymbol(
 645               (*Result)[KV.second.Aliasee].getAddress(), KV.second.AliasFlags);
 646         }
 647         if (auto Err = QueryInfo->R.notifyResolved(ResolutionMap)) {
 648           ES.reportError(std::move(Err));
 649           QueryInfo->R.failMaterialization();
 650           return;
 651         }
 652         if (auto Err = QueryInfo->R.notifyEmitted()) {
 653           ES.reportError(std::move(Err));
 654           QueryInfo->R.failMaterialization();
 655           return;
 656         }
 657       } else {
 658         ES.reportError(Result.takeError());
 659         QueryInfo->R.failMaterialization();
 660       }
 661     };
 662
 663     ES.lookup(JITDylibSearchList({{&SrcJD, MatchNonExported}}), QuerySymbols,
 664               SymbolState::Resolved, std::move(OnComplete),
 665               std::move(RegisterDependencies));
 666   }
 667 }
 668
 669 void ReExportsMaterializationUnit::discard(const JITDylib &JD,
 670                                            const SymbolStringPtr &Name) {
 671   assert(Aliases.count(Name) &&
 672          "Symbol not covered by this MaterializationUnit");
 673   Aliases.erase(Name);
 674 }
 675
 676 SymbolFlagsMap
 677 ReExportsMaterializationUnit::extractFlags(const SymbolAliasMap &Aliases) {
 678   SymbolFlagsMap SymbolFlags;
 679   for (auto &KV : Aliases)
 680     SymbolFlags[KV.first] = KV.second.AliasFlags;
 681
 682   return SymbolFlags;
 683 }
 684
 685 Expected<SymbolAliasMap>
 686 buildSimpleReexportsAliasMap(JITDylib &SourceJD, const SymbolNameSet &Symbols) {
 687   auto Flags = SourceJD.lookupFlags(Symbols);
 688
 689   if (!Flags)
 690     return Flags.takeError();
 691
 692   if (Flags->size() != Symbols.size()) {
 693     SymbolNameSet Unresolved = Symbols;
 694     for (auto &KV : *Flags)
 695       Unresolved.erase(KV.first);
 696     return make_error<SymbolsNotFound>(std::move(Unresolved));
 697   }
 698
 699   SymbolAliasMap Result;
 700   for (auto &Name : Symbols) {
 701     assert(Flags->count(Name) && "Missing entry in flags map");
 702     Result[Name] = SymbolAliasMapEntry(Name, (*Flags)[Name]);
 703   }
 704
 705   return Result;
 706 }
 707
 708 ReexportsGenerator::ReexportsGenerator(JITDylib &SourceJD,
 709                                        bool MatchNonExported,
 710                                        SymbolPredicate Allow)
 711     : SourceJD(SourceJD), MatchNonExported(MatchNonExported),
 712       Allow(std::move(Allow)) {}
 713
 714 Expected<SymbolNameSet>
 715 ReexportsGenerator::tryToGenerate(JITDylib &JD, const SymbolNameSet &Names) {
 716   orc::SymbolNameSet Added;
 717   orc::SymbolAliasMap AliasMap;
 718
 719   auto Flags = SourceJD.lookupFlags(Names);
 720
 721   if (!Flags)
 722     return Flags.takeError();
 723
 724   for (auto &KV : *Flags) {
 725     if (Allow && !Allow(KV.first))
 726       continue;
 727     AliasMap[KV.first] = SymbolAliasMapEntry(KV.first, KV.second);
 728     Added.insert(KV.first);
 729   }
 730
 731   if (!Added.empty())
 732     cantFail(JD.define(reexports(SourceJD, AliasMap, MatchNonExported)));
 733
 734   return Added;
 735 }
 736
 737 JITDylib::DefinitionGenerator::~DefinitionGenerator() {}
 738
 739 void JITDylib::removeGenerator(DefinitionGenerator &G) {
 740   ES.runSessionLocked([&]() {
 741     auto I = std::find_if(DefGenerators.begin(), DefGenerators.end(),
 742                           [&](const std::unique_ptr<DefinitionGenerator> &H) {
 743                             return H.get() == &G;
 744                           });
 745     assert(I != DefGenerators.end() && "Generator not found");
 746     DefGenerators.erase(I);
 747   });
 748 }
 749
 750 Error JITDylib::defineMaterializing(const SymbolFlagsMap &SymbolFlags) {
 751   return ES.runSessionLocked([&]() -> Error {
 752     std::vector<SymbolTable::iterator> AddedSyms;
 753
 754     for (auto &KV : SymbolFlags) {
 755       SymbolTable::iterator EntryItr;
 756       bool Added;
 757
 758       std::tie(EntryItr, Added) =
 759           Symbols.insert(std::make_pair(KV.first, SymbolTableEntry(KV.second)));
 760
 761       if (Added) {
 762         AddedSyms.push_back(EntryItr);
 763         EntryItr->second.setState(SymbolState::Materializing);
 764       } else {
 765         // Remove any symbols already added.
 766         for (auto &SI : AddedSyms)
 767           Symbols.erase(SI);
 768
 769         // FIXME: Return all duplicates.
 770         return make_error<DuplicateDefinition>(*KV.first);
 771       }
 772     }
 773
 774     return Error::success();
 775   });
 776 }
 777
 778 void JITDylib::replace(std::unique_ptr<MaterializationUnit> MU) {
 779   assert(MU != nullptr && "Can not replace with a null MaterializationUnit");
 780
 781   auto MustRunMU =
 782       ES.runSessionLocked([&, this]() -> std::unique_ptr<MaterializationUnit> {
 783
 784 #ifndef NDEBUG
 785         for (auto &KV : MU->getSymbols()) {
 786           auto SymI = Symbols.find(KV.first);
 787           assert(SymI != Symbols.end() && "Replacing unknown symbol");
 788           assert(SymI->second.isInMaterializationPhase() &&
 789                  "Can not call replace on a symbol that is not materializing");
 790           assert(!SymI->second.hasMaterializerAttached() &&
 791                  "Symbol should not have materializer attached already");
 792           assert(UnmaterializedInfos.count(KV.first) == 0 &&
 793                  "Symbol being replaced should have no UnmaterializedInfo");
 794         }
 795 #endif // NDEBUG
 796
 797         // If any symbol has pending queries against it then we need to
 798         // materialize MU immediately.
 799         for (auto &KV : MU->getSymbols()) {
 800           auto MII = MaterializingInfos.find(KV.first);
 801           if (MII != MaterializingInfos.end()) {
 802             if (MII->second.hasQueriesPending())
 803               return std::move(MU);
 804           }
 805         }
 806
 807         // Otherwise, make MU responsible for all the symbols.
 808         auto UMI = std::make_shared<UnmaterializedInfo>(std::move(MU));
 809         for (auto &KV : UMI->MU->getSymbols()) {
 810           auto SymI = Symbols.find(KV.first);
 811           assert(SymI->second.getState() == SymbolState::Materializing &&
 812                  "Can not replace a symbol that is not materializing");
 813           assert(!SymI->second.hasMaterializerAttached() &&
 814                  "Can not replace a symbol that has a materializer attached");
 815           assert(UnmaterializedInfos.count(KV.first) == 0 &&
 816                  "Unexpected materializer entry in map");
 817           SymI->second.setAddress(SymI->second.getAddress());
 818           SymI->second.setMaterializerAttached(true);
 819           UnmaterializedInfos[KV.first] = UMI;
 820         }
 821
 822         return nullptr;
 823       });
 824
 825   if (MustRunMU)
 826     ES.dispatchMaterialization(*this, std::move(MustRunMU));
 827 }
 828
 829 SymbolNameSet
 830 JITDylib::getRequestedSymbols(const SymbolFlagsMap &SymbolFlags) const {
 831   return ES.runSessionLocked([&]() {
 832     SymbolNameSet RequestedSymbols;
 833
 834     for (auto &KV : SymbolFlags) {
 835       assert(Symbols.count(KV.first) && "JITDylib does not cover this symbol?");
 836       assert(Symbols.find(KV.first)->second.isInMaterializationPhase() &&
 837              "getRequestedSymbols can only be called for symbols that have "
 838              "started materializing");
 839       auto I = MaterializingInfos.find(KV.first);
 840       if (I == MaterializingInfos.end())
 841         continue;
 842
 843       if (I->second.hasQueriesPending())
 844         RequestedSymbols.insert(KV.first);
 845     }
 846
 847     return RequestedSymbols;
 848   });
 849 }
 850
 851 void JITDylib::addDependencies(const SymbolStringPtr &Name,
 852                                const SymbolDependenceMap &Dependencies) {
 853   assert(Symbols.count(Name) && "Name not in symbol table");
 854   assert(Symbols[Name].isInMaterializationPhase() &&
 855          "Can not add dependencies for a symbol that is not materializing");
 856
 857   // If Name is already in an error state then just bail out.
 858   if (Symbols[Name].getFlags().hasError())
 859     return;
 860
 861   auto &MI = MaterializingInfos[Name];
 862   assert(Symbols[Name].getState() != SymbolState::Emitted &&
 863          "Can not add dependencies to an emitted symbol");
 864
 865   bool DependsOnSymbolInErrorState = false;
 866
 867   // Register dependencies, record whether any depenendency is in the error
 868   // state.
 869   for (auto &KV : Dependencies) {
 870     assert(KV.first && "Null JITDylib in dependency?");
 871     auto &OtherJITDylib = *KV.first;
 872     auto &DepsOnOtherJITDylib = MI.UnemittedDependencies[&OtherJITDylib];
 873
 874     for (auto &OtherSymbol : KV.second) {
 875
 876       // Check the sym entry for the dependency.
 877       auto OtherSymI = OtherJITDylib.Symbols.find(OtherSymbol);
 878
 879 #ifndef NDEBUG
 880       // Assert that this symbol exists and has not reached the ready state
 881       // already.
 882       assert(OtherSymI != OtherJITDylib.Symbols.end() &&
 883              (OtherSymI->second.getState() != SymbolState::Ready &&
 884               "Dependency on emitted/ready symbol"));
 885 #endif
 886
 887       auto &OtherSymEntry = OtherSymI->second;
 888
 889       // If the dependency is in an error state then note this and continue,
 890       // we will move this symbol to the error state below.
 891       if (OtherSymEntry.getFlags().hasError()) {
 892         DependsOnSymbolInErrorState = true;
 893         continue;
 894       }
 895
 896       // If the dependency was not in the error state then add it to
 897       // our list of dependencies.
 898       assert(OtherJITDylib.MaterializingInfos.count(OtherSymbol) &&
 899              "No MaterializingInfo for dependency");
 900       auto &OtherMI = OtherJITDylib.MaterializingInfos[OtherSymbol];
 901
 902       if (OtherSymEntry.getState() == SymbolState::Emitted)
 903         transferEmittedNodeDependencies(MI, Name, OtherMI);
 904       else if (&OtherJITDylib != this || OtherSymbol != Name) {
 905         OtherMI.Dependants[this].insert(Name);
 906         DepsOnOtherJITDylib.insert(OtherSymbol);
 907       }
 908     }
 909
 910     if (DepsOnOtherJITDylib.empty())
 911       MI.UnemittedDependencies.erase(&OtherJITDylib);
 912   }
 913
 914   // If this symbol dependended on any symbols in the error state then move
 915   // this symbol to the error state too.
 916   if (DependsOnSymbolInErrorState)
 917     Symbols[Name].setFlags(Symbols[Name].getFlags() | JITSymbolFlags::HasError);
 918 }
 919
 920 Error JITDylib::resolve(const SymbolMap &Resolved) {
 921   SymbolNameSet SymbolsInErrorState;
 922   AsynchronousSymbolQuerySet CompletedQueries;
 923
 924   ES.runSessionLocked([&, this]() {
 925     struct WorklistEntry {
 926       SymbolTable::iterator SymI;
 927       JITEvaluatedSymbol ResolvedSym;
 928     };
 929
 930     std::vector<WorklistEntry> Worklist;
 931     Worklist.reserve(Resolved.size());
 932
 933     // Build worklist and check for any symbols in the error state.
 934     for (const auto &KV : Resolved) {
 935
 936       assert(!KV.second.getFlags().hasError() &&
 937              "Resolution result can not have error flag set");
 938
 939       auto SymI = Symbols.find(KV.first);
 940
 941       assert(SymI != Symbols.end() && "Symbol not found");
 942       assert(!SymI->second.hasMaterializerAttached() &&
 943              "Resolving symbol with materializer attached?");
 944       assert(SymI->second.getState() == SymbolState::Materializing &&
 945              "Symbol should be materializing");
 946       assert(SymI->second.getAddress() == 0 &&
 947              "Symbol has already been resolved");
 948
 949       if (SymI->second.getFlags().hasError())
 950         SymbolsInErrorState.insert(KV.first);
 951       else {
 952         assert((KV.second.getFlags() & ~JITSymbolFlags::Weak) ==
 953                    (SymI->second.getFlags() & ~JITSymbolFlags::Weak) &&
 954                "Resolved flags should match the declared flags");
 955
 956         Worklist.push_back({SymI, KV.second});
 957       }
 958     }
 959
 960     // If any symbols were in the error state then bail out.
 961     if (!SymbolsInErrorState.empty())
 962       return;
 963
 964     while (!Worklist.empty()) {
 965       auto SymI = Worklist.back().SymI;
 966       auto ResolvedSym = Worklist.back().ResolvedSym;
 967       Worklist.pop_back();
 968
 969       auto &Name = SymI->first;
 970
 971       // Resolved symbols can not be weak: discard the weak flag.
 972       JITSymbolFlags ResolvedFlags = ResolvedSym.getFlags();
 973       ResolvedFlags &= ~JITSymbolFlags::Weak;
 974       SymI->second.setAddress(ResolvedSym.getAddress());
 975       SymI->second.setFlags(ResolvedFlags);
 976       SymI->second.setState(SymbolState::Resolved);
 977
 978       auto &MI = MaterializingInfos[Name];
 979       for (auto &Q : MI.takeQueriesMeeting(SymbolState::Resolved)) {
 980         Q->notifySymbolMetRequiredState(Name, ResolvedSym);
 981         Q->removeQueryDependence(*this, Name);
 982         if (Q->isComplete())
 983           CompletedQueries.insert(std::move(Q));
 984       }
 985     }
 986   });
 987
 988   assert((SymbolsInErrorState.empty() || CompletedQueries.empty()) &&
 989          "Can't fail symbols and completed queries at the same time");
 990
 991   // If we failed any symbols then return an error.
 992   if (!SymbolsInErrorState.empty()) {
 993     auto FailedSymbolsDepMap = std::make_shared<SymbolDependenceMap>();
 994     (*FailedSymbolsDepMap)[this] = std::move(SymbolsInErrorState);
 995     return make_error<FailedToMaterialize>(std::move(FailedSymbolsDepMap));
 996   }
 997
 998   // Otherwise notify all the completed queries.
 999   for (auto &Q : CompletedQueries) {
1000     assert(Q->isComplete() && "Q not completed");
1001     Q->handleComplete();
1002   }
1003
1004   return Error::success();
1005 }
1006
1007 Error JITDylib::emit(const SymbolFlagsMap &Emitted) {
1008   AsynchronousSymbolQuerySet CompletedQueries;
1009   SymbolNameSet SymbolsInErrorState;
1010
1011   ES.runSessionLocked([&, this]() {
1012     std::vector<SymbolTable::iterator> Worklist;
1013
1014     // Scan to build worklist, record any symbols in the erorr state.
1015     for (const auto &KV : Emitted) {
1016       auto &Name = KV.first;
1017
1018       auto SymI = Symbols.find(Name);
1019       assert(SymI != Symbols.end() && "No symbol table entry for Name");
1020
1021       if (SymI->second.getFlags().hasError())
1022         SymbolsInErrorState.insert(Name);
1023       else
1024         Worklist.push_back(SymI);
1025     }
1026
1027     // If any symbols were in the error state then bail out.
1028     if (!SymbolsInErrorState.empty())
1029       return;
1030
1031     // Otherwise update dependencies and move to the emitted state.
1032     while (!Worklist.empty()) {
1033       auto SymI = Worklist.back();
1034       Worklist.pop_back();
1035
1036       auto &Name = SymI->first;
1037       auto &SymEntry = SymI->second;
1038
1039       // Move symbol to the emitted state.
1040       assert(SymEntry.getState() == SymbolState::Resolved &&
1041              "Emitting from state other than Resolved");
1042       SymEntry.setState(SymbolState::Emitted);
1043
1044       auto MII = MaterializingInfos.find(Name);
1045       assert(MII != MaterializingInfos.end() &&
1046              "Missing MaterializingInfo entry");
1047       auto &MI = MII->second;
1048
1049       // For each dependant, transfer this node's emitted dependencies to
1050       // it. If the dependant node is ready (i.e. has no unemitted
1051       // dependencies) then notify any pending queries.
1052       for (auto &KV : MI.Dependants) {
1053         auto &DependantJD = *KV.first;
1054         for (auto &DependantName : KV.second) {
1055           auto DependantMII =
1056               DependantJD.MaterializingInfos.find(DependantName);
1057           assert(DependantMII != DependantJD.MaterializingInfos.end() &&
1058                  "Dependant should have MaterializingInfo");
1059
1060           auto &DependantMI = DependantMII->second;
1061
1062           // Remove the dependant's dependency on this node.
1063           assert(DependantMI.UnemittedDependencies.count(this) &&
1064                  "Dependant does not have an unemitted dependencies record for "
1065                  "this JITDylib");
1066           assert(DependantMI.UnemittedDependencies[this].count(Name) &&
1067                  "Dependant does not count this symbol as a dependency?");
1068
1069           DependantMI.UnemittedDependencies[this].erase(Name);
1070           if (DependantMI.UnemittedDependencies[this].empty())
1071             DependantMI.UnemittedDependencies.erase(this);
1072
1073           // Transfer unemitted dependencies from this node to the dependant.
1074           DependantJD.transferEmittedNodeDependencies(DependantMI,
1075                                                       DependantName, MI);
1076
1077           auto DependantSymI = DependantJD.Symbols.find(DependantName);
1078           assert(DependantSymI != DependantJD.Symbols.end() &&
1079                  "Dependant has no entry in the Symbols table");
1080           auto &DependantSymEntry = DependantSymI->second;
1081
1082           // If the dependant is emitted and this node was the last of its
1083           // unemitted dependencies then the dependant node is now ready, so
1084           // notify any pending queries on the dependant node.
1085           if (DependantSymEntry.getState() == SymbolState::Emitted &&
1086               DependantMI.UnemittedDependencies.empty()) {
1087             assert(DependantMI.Dependants.empty() &&
1088                    "Dependants should be empty by now");
1089
1090             // Since this dependant is now ready, we erase its MaterializingInfo
1091             // and update its materializing state.
1092             DependantSymEntry.setState(SymbolState::Ready);
1093
1094             for (auto &Q : DependantMI.takeQueriesMeeting(SymbolState::Ready)) {
1095               Q->notifySymbolMetRequiredState(
1096                   DependantName, DependantSymI->second.getSymbol());
1097               if (Q->isComplete())
1098                 CompletedQueries.insert(Q);
1099               Q->removeQueryDependence(DependantJD, DependantName);
1100             }
1101
1102             DependantJD.MaterializingInfos.erase(DependantMII);
1103           }
1104         }
1105       }
1106
1107       MI.Dependants.clear();
1108       if (MI.UnemittedDependencies.empty()) {
1109         SymI->second.setState(SymbolState::Ready);
1110         for (auto &Q : MI.takeQueriesMeeting(SymbolState::Ready)) {
1111           Q->notifySymbolMetRequiredState(Name, SymI->second.getSymbol());
1112           if (Q->isComplete())
1113             CompletedQueries.insert(Q);
1114           Q->removeQueryDependence(*this, Name);
1115         }
1116         MaterializingInfos.erase(MII);
1117       }
1118     }
1119   });
1120
1121   assert((SymbolsInErrorState.empty() || CompletedQueries.empty()) &&
1122          "Can't fail symbols and completed queries at the same time");
1123
1124   // If we failed any symbols then return an error.
1125   if (!SymbolsInErrorState.empty()) {
1126     auto FailedSymbolsDepMap = std::make_shared<SymbolDependenceMap>();
1127     (*FailedSymbolsDepMap)[this] = std::move(SymbolsInErrorState);
1128     return make_error<FailedToMaterialize>(std::move(FailedSymbolsDepMap));
1129   }
1130
1131   // Otherwise notify all the completed queries.
1132   for (auto &Q : CompletedQueries) {
1133     assert(Q->isComplete() && "Q is not complete");
1134     Q->handleComplete();
1135   }
1136
1137   return Error::success();
1138 }
1139
1140 void JITDylib::notifyFailed(FailedSymbolsWorklist Worklist) {
1141   AsynchronousSymbolQuerySet FailedQueries;
1142   auto FailedSymbolsMap = std::make_shared<SymbolDependenceMap>();
1143
1144   // Failing no symbols is a no-op.
1145   if (Worklist.empty())
1146     return;
1147
1148   auto &ES = Worklist.front().first->getExecutionSession();
1149
1150   ES.runSessionLocked([&]() {
1151     while (!Worklist.empty()) {
1152       assert(Worklist.back().first && "Failed JITDylib can not be null");
1153       auto &JD = *Worklist.back().first;
1154       auto Name = std::move(Worklist.back().second);
1155       Worklist.pop_back();
1156
1157       (*FailedSymbolsMap)[&JD].insert(Name);
1158
1159       assert(JD.Symbols.count(Name) && "No symbol table entry for Name");
1160       auto &Sym = JD.Symbols[Name];
1161
1162       // Move the symbol into the error state.
1163       // Note that this may be redundant: The symbol might already have been
1164       // moved to this state in response to the failure of a dependence.
1165       Sym.setFlags(Sym.getFlags() | JITSymbolFlags::HasError);
1166
1167       // FIXME: Come up with a sane mapping of state to
1168       // presence-of-MaterializingInfo so that we can assert presence / absence
1169       // here, rather than testing it.
1170       auto MII = JD.MaterializingInfos.find(Name);
1171
1172       if (MII == JD.MaterializingInfos.end())
1173         continue;
1174
1175       auto &MI = MII->second;
1176
1177       // Move all dependants to the error state and disconnect from them.
1178       for (auto &KV : MI.Dependants) {
1179         auto &DependantJD = *KV.first;
1180         for (auto &DependantName : KV.second) {
1181           assert(DependantJD.Symbols.count(DependantName) &&
1182                  "No symbol table entry for DependantName");
1183           auto &DependantSym = DependantJD.Symbols[DependantName];
1184           DependantSym.setFlags(DependantSym.getFlags() |
1185                                 JITSymbolFlags::HasError);
1186
1187           assert(DependantJD.MaterializingInfos.count(DependantName) &&
1188                  "No MaterializingInfo for dependant");
1189           auto &DependantMI = DependantJD.MaterializingInfos[DependantName];
1190
1191           auto UnemittedDepI = DependantMI.UnemittedDependencies.find(&JD);
1192           assert(UnemittedDepI != DependantMI.UnemittedDependencies.end() &&
1193                  "No UnemittedDependencies entry for this JITDylib");
1194           assert(UnemittedDepI->second.count(Name) &&
1195                  "No UnemittedDependencies entry for this symbol");
1196           UnemittedDepI->second.erase(Name);
1197           if (UnemittedDepI->second.empty())
1198             DependantMI.UnemittedDependencies.erase(UnemittedDepI);
1199
1200           // If this symbol is already in the emitted state then we need to
1201           // take responsibility for failing its queries, so add it to the
1202           // worklist.
1203           if (DependantSym.getState() == SymbolState::Emitted) {
1204             assert(DependantMI.Dependants.empty() &&
1205                    "Emitted symbol should not have dependants");
1206             Worklist.push_back(std::make_pair(&DependantJD, DependantName));
1207           }
1208         }
1209       }
1210       MI.Dependants.clear();
1211
1212       // Disconnect from all unemitted depenencies.
1213       for (auto &KV : MI.UnemittedDependencies) {
1214         auto &UnemittedDepJD = *KV.first;
1215         for (auto &UnemittedDepName : KV.second) {
1216           auto UnemittedDepMII =
1217               UnemittedDepJD.MaterializingInfos.find(UnemittedDepName);
1218           assert(UnemittedDepMII != UnemittedDepJD.MaterializingInfos.end() &&
1219                  "Missing MII for unemitted dependency");
1220           assert(UnemittedDepMII->second.Dependants.count(&JD) &&
1221                  "JD not listed as a dependant of unemitted dependency");
1222           assert(UnemittedDepMII->second.Dependants[&JD].count(Name) &&
1223                  "Name is not listed as a dependant of unemitted dependency");
1224           UnemittedDepMII->second.Dependants[&JD].erase(Name);
1225           if (UnemittedDepMII->second.Dependants[&JD].empty())
1226             UnemittedDepMII->second.Dependants.erase(&JD);
1227         }
1228       }
1229       MI.UnemittedDependencies.clear();
1230
1231       // Collect queries to be failed for this MII.
1232       for (auto &Q : MII->second.pendingQueries()) {
1233         // Add the query to the list to be failed and detach it.
1234         FailedQueries.insert(Q);
1235         Q->detach();
1236       }
1237
1238       assert(MI.Dependants.empty() &&
1239              "Can not delete MaterializingInfo with dependants still attached");
1240       assert(MI.UnemittedDependencies.empty() &&
1241              "Can not delete MaterializingInfo with unemitted dependencies "
1242              "still attached");
1243       assert(!MI.hasQueriesPending() &&
1244              "Can not delete MaterializingInfo with queries pending");
1245       JD.MaterializingInfos.erase(MII);
1246     }
1247   });
1248
1249   for (auto &Q : FailedQueries)
1250     Q->handleFailed(make_error<FailedToMaterialize>(FailedSymbolsMap));
1251 }
1252
1253 void JITDylib::setSearchOrder(JITDylibSearchList NewSearchOrder,
1254                               bool SearchThisJITDylibFirst,
1255                               bool MatchNonExportedInThisDylib) {
1256   if (SearchThisJITDylibFirst) {
1257     if (NewSearchOrder.empty() || NewSearchOrder.front().first != this)
1258       NewSearchOrder.insert(NewSearchOrder.begin(),
1259                             {this, MatchNonExportedInThisDylib});
1260   }
1261
1262   ES.runSessionLocked([&]() { SearchOrder = std::move(NewSearchOrder); });
1263 }
1264
1265 void JITDylib::addToSearchOrder(JITDylib &JD, bool MatchNonExported) {
1266   ES.runSessionLocked([&]() {
1267     SearchOrder.push_back({&JD, MatchNonExported});
1268   });
1269 }
1270
1271 void JITDylib::replaceInSearchOrder(JITDylib &OldJD, JITDylib &NewJD,
1272                                     bool MatchNonExported) {
1273   ES.runSessionLocked([&]() {
1274     auto I = std::find_if(SearchOrder.begin(), SearchOrder.end(),
1275                           [&](const JITDylibSearchList::value_type &KV) {
1276                             return KV.first == &OldJD;
1277                           });
1278
1279     if (I != SearchOrder.end())
1280       *I = {&NewJD, MatchNonExported};
1281   });
1282 }
1283
1284 void JITDylib::removeFromSearchOrder(JITDylib &JD) {
1285   ES.runSessionLocked([&]() {
1286     auto I = std::find_if(SearchOrder.begin(), SearchOrder.end(),
1287                           [&](const JITDylibSearchList::value_type &KV) {
1288                             return KV.first == &JD;
1289                           });
1290     if (I != SearchOrder.end())
1291       SearchOrder.erase(I);
1292   });
1293 }
1294
1295 Error JITDylib::remove(const SymbolNameSet &Names) {
1296   return ES.runSessionLocked([&]() -> Error {
1297     using SymbolMaterializerItrPair =
1298         std::pair<SymbolTable::iterator, UnmaterializedInfosMap::iterator>;
1299     std::vector<SymbolMaterializerItrPair> SymbolsToRemove;
1300     SymbolNameSet Missing;
1301     SymbolNameSet Materializing;
1302
1303     for (auto &Name : Names) {
1304       auto I = Symbols.find(Name);
1305
1306       // Note symbol missing.
1307       if (I == Symbols.end()) {
1308         Missing.insert(Name);
1309         continue;
1310       }
1311
1312       // Note symbol materializing.
1313       if (I->second.isInMaterializationPhase()) {
1314         Materializing.insert(Name);
1315         continue;
1316       }
1317
1318       auto UMII = I->second.hasMaterializerAttached()
1319                       ? UnmaterializedInfos.find(Name)
1320                       : UnmaterializedInfos.end();
1321       SymbolsToRemove.push_back(std::make_pair(I, UMII));
1322     }
1323
1324     // If any of the symbols are not defined, return an error.
1325     if (!Missing.empty())
1326       return make_error<SymbolsNotFound>(std::move(Missing));
1327
1328     // If any of the symbols are currently materializing, return an error.
1329     if (!Materializing.empty())
1330       return make_error<SymbolsCouldNotBeRemoved>(std::move(Materializing));
1331
1332     // Remove the symbols.
1333     for (auto &SymbolMaterializerItrPair : SymbolsToRemove) {
1334       auto UMII = SymbolMaterializerItrPair.second;
1335
1336       // If there is a materializer attached, call discard.
1337       if (UMII != UnmaterializedInfos.end()) {
1338         UMII->second->MU->doDiscard(*this, UMII->first);
1339         UnmaterializedInfos.erase(UMII);
1340       }
1341
1342       auto SymI = SymbolMaterializerItrPair.first;
1343       Symbols.erase(SymI);
1344     }
1345
1346     return Error::success();
1347   });
1348 }
1349
1350 Expected<SymbolFlagsMap> JITDylib::lookupFlags(const SymbolNameSet &Names) {
1351   return ES.runSessionLocked([&, this]() -> Expected<SymbolFlagsMap> {
1352     SymbolFlagsMap Result;
1353     auto Unresolved = lookupFlagsImpl(Result, Names);
1354     if (!Unresolved)
1355       return Unresolved.takeError();
1356
1357     /// Run any definition generators.
1358     for (auto &DG : DefGenerators) {
1359
1360       // Bail out early if we've resolved everything.
1361       if (Unresolved->empty())
1362         break;
1363
1364       // Run this generator.
1365       auto NewDefs = DG->tryToGenerate(*this, *Unresolved);
1366       if (!NewDefs)
1367         return NewDefs.takeError();
1368
1369       if (!NewDefs->empty()) {
1370         auto Unresolved2 = lookupFlagsImpl(Result, *NewDefs);
1371         if (!Unresolved2)
1372           return Unresolved2.takeError();
1373         (void)Unresolved2;
1374         assert(Unresolved2->empty() &&
1375                "All fallback defs should have been found by lookupFlagsImpl");
1376       }
1377
1378       for (auto &Name : *NewDefs)
1379         Unresolved->erase(Name);
1380     }
1381     return Result;
1382   });
1383 }
1384
1385 Expected<SymbolNameSet> JITDylib::lookupFlagsImpl(SymbolFlagsMap &Flags,
1386                                                   const SymbolNameSet &Names) {
1387   SymbolNameSet Unresolved;
1388
1389   for (auto &Name : Names) {
1390     auto I = Symbols.find(Name);
1391     if (I != Symbols.end()) {
1392       assert(!Flags.count(Name) && "Symbol already present in Flags map");
1393       Flags[Name] = I->second.getFlags();
1394     } else
1395       Unresolved.insert(Name);
1396   }
1397
1398   return Unresolved;
1399 }
1400
1401 Error JITDylib::lodgeQuery(std::shared_ptr<AsynchronousSymbolQuery> &Q,
1402                            SymbolNameSet &Unresolved, bool MatchNonExported,
1403                            MaterializationUnitList &MUs) {
1404   assert(Q && "Query can not be null");
1405
1406   if (auto Err = lodgeQueryImpl(Q, Unresolved, MatchNonExported, MUs))
1407     return Err;
1408
1409   // Run any definition generators.
1410   for (auto &DG : DefGenerators) {
1411
1412     // Bail out early if we have resolved everything.
1413     if (Unresolved.empty())
1414       break;
1415
1416     // Run the generator.
1417     auto NewDefs = DG->tryToGenerate(*this, Unresolved);
1418
1419     // If the generator returns an error then bail out.
1420     if (!NewDefs)
1421       return NewDefs.takeError();
1422
1423     // If the generator was able to generate new definitions for any of the
1424     // unresolved symbols then lodge the query against them.
1425     if (!NewDefs->empty()) {
1426       for (auto &D : *NewDefs)
1427         Unresolved.erase(D);
1428
1429       // Lodge query. This can not fail as any new definitions were added
1430       // by the generator under the session locked. Since they can't have
1431       // started materializing yet the can not have failed.
1432       cantFail(lodgeQueryImpl(Q, *NewDefs, MatchNonExported, MUs));
1433
1434       assert(NewDefs->empty() &&
1435              "All fallback defs should have been found by lookupImpl");
1436     }
1437   }
1438
1439   return Error::success();
1440 }
1441
1442 Error JITDylib::lodgeQueryImpl(
1443     std::shared_ptr<AsynchronousSymbolQuery> &Q, SymbolNameSet &Unresolved,
1444     bool MatchNonExported,
1445     std::vector<std::unique_ptr<MaterializationUnit>> &MUs) {
1446
1447   std::vector<SymbolStringPtr> ToRemove;
1448   for (auto Name : Unresolved) {
1449
1450     // Search for the name in Symbols. Skip it if not found.
1451     auto SymI = Symbols.find(Name);
1452     if (SymI == Symbols.end())
1453       continue;
1454
1455     // If this is a non exported symbol and we're skipping those then skip it.
1456     if (!SymI->second.getFlags().isExported() && !MatchNonExported)
1457       continue;
1458
1459     // If we matched against Name in JD, mark it to be removed from the
1460     // Unresolved set.
1461     ToRemove.push_back(Name);
1462
1463     // If we matched against this symbol but it is in the error state then
1464     // bail out and treat it as a failure to materialize.
1465     if (SymI->second.getFlags().hasError()) {
1466       auto FailedSymbolsMap = std::make_shared<SymbolDependenceMap>();
1467       (*FailedSymbolsMap)[this] = {Name};
1468       return make_error<FailedToMaterialize>(std::move(FailedSymbolsMap));
1469     }
1470
1471     // If this symbol already meets the required state for then notify the
1472     // query and continue.
1473     if (SymI->second.getState() >= Q->getRequiredState()) {
1474       Q->notifySymbolMetRequiredState(Name, SymI->second.getSymbol());
1475       continue;
1476     }
1477
1478     // Otherwise this symbol does not yet meet the required state. Check whether
1479     // it has a materializer attached, and if so prepare to run it.
1480     if (SymI->second.hasMaterializerAttached()) {
1481       assert(SymI->second.getAddress() == 0 &&
1482              "Symbol not resolved but already has address?");
1483       auto UMII = UnmaterializedInfos.find(Name);
1484       assert(UMII != UnmaterializedInfos.end() &&
1485              "Lazy symbol should have UnmaterializedInfo");
1486       auto MU = std::move(UMII->second->MU);
1487       assert(MU != nullptr && "Materializer should not be null");
1488
1489       // Move all symbols associated with this MaterializationUnit into
1490       // materializing state.
1491       for (auto &KV : MU->getSymbols()) {
1492         auto SymK = Symbols.find(KV.first);
1493         SymK->second.setMaterializerAttached(false);
1494         SymK->second.setState(SymbolState::Materializing);
1495         UnmaterializedInfos.erase(KV.first);
1496       }
1497
1498       // Add MU to the list of MaterializationUnits to be materialized.
1499       MUs.push_back(std::move(MU));
1500     }
1501
1502     // Add the query to the PendingQueries list.
1503     assert(SymI->second.isInMaterializationPhase() &&
1504            "By this line the symbol should be materializing");
1505     auto &MI = MaterializingInfos[Name];
1506     MI.addQuery(Q);
1507     Q->addQueryDependence(*this, Name);
1508   }
1509
1510   // Remove any symbols that we found.
1511   for (auto &Name : ToRemove)
1512     Unresolved.erase(Name);
1513
1514   return Error::success();
1515 }
1516
1517 Expected<SymbolNameSet>
1518 JITDylib::legacyLookup(std::shared_ptr<AsynchronousSymbolQuery> Q,
1519                        SymbolNameSet Names) {
1520   assert(Q && "Query can not be null");
1521
1522   ES.runOutstandingMUs();
1523
1524   bool QueryComplete = false;
1525   std::vector<std::unique_ptr<MaterializationUnit>> MUs;
1526
1527   SymbolNameSet Unresolved = std::move(Names);
1528   auto Err = ES.runSessionLocked([&, this]() -> Error {
1529     QueryComplete = lookupImpl(Q, MUs, Unresolved);
1530
1531     // Run any definition generators.
1532     for (auto &DG : DefGenerators) {
1533
1534       // Bail out early if we have resolved everything.
1535       if (Unresolved.empty())
1536         break;
1537
1538       assert(!QueryComplete && "query complete but unresolved symbols remain?");
1539       auto NewDefs = DG->tryToGenerate(*this, Unresolved);
1540       if (!NewDefs)
1541         return NewDefs.takeError();
1542       if (!NewDefs->empty()) {
1543         for (auto &D : *NewDefs)
1544           Unresolved.erase(D);
1545         QueryComplete = lookupImpl(Q, MUs, *NewDefs);
1546         assert(NewDefs->empty() &&
1547                "All fallback defs should have been found by lookupImpl");
1548       }
1549     }
1550     return Error::success();
1551   });
1552
1553   if (Err)
1554     return std::move(Err);
1555
1556   assert((MUs.empty() || !QueryComplete) &&
1557          "If action flags are set, there should be no work to do (so no MUs)");
1558
1559   if (QueryComplete)
1560     Q->handleComplete();
1561
1562   // FIXME: Swap back to the old code below once RuntimeDyld works with
1563   //        callbacks from asynchronous queries.
1564   // Add MUs to the OutstandingMUs list.
1565   {
1566     std::lock_guard<std::recursive_mutex> Lock(ES.OutstandingMUsMutex);
1567     for (auto &MU : MUs)
1568       ES.OutstandingMUs.push_back(make_pair(this, std::move(MU)));
1569   }
1570   ES.runOutstandingMUs();
1571
1572   // Dispatch any required MaterializationUnits for materialization.
1573   // for (auto &MU : MUs)
1574   //  ES.dispatchMaterialization(*this, std::move(MU));
1575
1576   return Unresolved;
1577 }
1578
1579 bool JITDylib::lookupImpl(
1580     std::shared_ptr<AsynchronousSymbolQuery> &Q,
1581     std::vector<std::unique_ptr<MaterializationUnit>> &MUs,
1582     SymbolNameSet &Unresolved) {
1583   bool QueryComplete = false;
1584
1585   std::vector<SymbolStringPtr> ToRemove;
1586   for (auto Name : Unresolved) {
1587
1588     // Search for the name in Symbols. Skip it if not found.
1589     auto SymI = Symbols.find(Name);
1590     if (SymI == Symbols.end())
1591       continue;
1592
1593     // If we found Name, mark it to be removed from the Unresolved set.
1594     ToRemove.push_back(Name);
1595
1596     if (SymI->second.getState() >= Q->getRequiredState()) {
1597       Q->notifySymbolMetRequiredState(Name, SymI->second.getSymbol());
1598       if (Q->isComplete())
1599         QueryComplete = true;
1600       continue;
1601     }
1602
1603     // If the symbol is lazy, get the MaterialiaztionUnit for it.
1604     if (SymI->second.hasMaterializerAttached()) {
1605       assert(SymI->second.getAddress() == 0 &&
1606              "Lazy symbol should not have a resolved address");
1607       auto UMII = UnmaterializedInfos.find(Name);
1608       assert(UMII != UnmaterializedInfos.end() &&
1609              "Lazy symbol should have UnmaterializedInfo");
1610       auto MU = std::move(UMII->second->MU);
1611       assert(MU != nullptr && "Materializer should not be null");
1612
1613       // Kick all symbols associated with this MaterializationUnit into
1614       // materializing state.
1615       for (auto &KV : MU->getSymbols()) {
1616         auto SymK = Symbols.find(KV.first);
1617         assert(SymK != Symbols.end() && "Missing symbol table entry");
1618         SymK->second.setState(SymbolState::Materializing);
1619         SymK->second.setMaterializerAttached(false);
1620         UnmaterializedInfos.erase(KV.first);
1621       }
1622
1623       // Add MU to the list of MaterializationUnits to be materialized.
1624       MUs.push_back(std::move(MU));
1625     }
1626
1627     // Add the query to the PendingQueries list.
1628     assert(SymI->second.isInMaterializationPhase() &&
1629            "By this line the symbol should be materializing");
1630     auto &MI = MaterializingInfos[Name];
1631     MI.addQuery(Q);
1632     Q->addQueryDependence(*this, Name);
1633   }
1634
1635   // Remove any marked symbols from the Unresolved set.
1636   for (auto &Name : ToRemove)
1637     Unresolved.erase(Name);
1638
1639   return QueryComplete;
1640 }
1641
1642 void JITDylib::dump(raw_ostream &OS) {
1643   ES.runSessionLocked([&, this]() {
1644     OS << "JITDylib \"" << JITDylibName << "\" (ES: "
1645        << format("0x%016" PRIx64, reinterpret_cast<uintptr_t>(&ES)) << "):\n"
1646        << "Search order: [";
1647     for (auto &KV : SearchOrder)
1648       OS << " (\"" << KV.first->getName() << "\", "
1649          << (KV.second ? "all" : "exported only") << ")";
1650     OS << " ]\n"
1651        << "Symbol table:\n";
1652
1653     for (auto &KV : Symbols) {
1654       OS << "    \"" << *KV.first << "\": ";
1655       if (auto Addr = KV.second.getAddress())
1656         OS << format("0x%016" PRIx64, Addr) << ", " << KV.second.getFlags()
1657            << " ";
1658       else
1659         OS << "<not resolved> ";
1660
1661       OS << KV.second.getState();
1662
1663       if (KV.second.hasMaterializerAttached()) {
1664         OS << " (Materializer ";
1665         auto I = UnmaterializedInfos.find(KV.first);
1666         assert(I != UnmaterializedInfos.end() &&
1667                "Lazy symbol should have UnmaterializedInfo");
1668         OS << I->second->MU.get() << ")\n";
1669       } else
1670         OS << "\n";
1671     }
1672
1673     if (!MaterializingInfos.empty())
1674       OS << "  MaterializingInfos entries:\n";
1675     for (auto &KV : MaterializingInfos) {
1676       OS << "    \"" << *KV.first << "\":\n"
1677          << "      " << KV.second.pendingQueries().size()
1678          << " pending queries: { ";
1679       for (const auto &Q : KV.second.pendingQueries())
1680         OS << Q.get() << " (" << Q->getRequiredState() << ") ";
1681       OS << "}\n      Dependants:\n";
1682       for (auto &KV2 : KV.second.Dependants)
1683         OS << "        " << KV2.first->getName() << ": " << KV2.second << "\n";
1684       OS << "      Unemitted Dependencies:\n";
1685       for (auto &KV2 : KV.second.UnemittedDependencies)
1686         OS << "        " << KV2.first->getName() << ": " << KV2.second << "\n";
1687     }
1688   });
1689 }
1690
1691 void JITDylib::MaterializingInfo::addQuery(
1692     std::shared_ptr<AsynchronousSymbolQuery> Q) {
1693
1694   auto I = std::lower_bound(
1695       PendingQueries.rbegin(), PendingQueries.rend(), Q->getRequiredState(),
1696       [](const std::shared_ptr<AsynchronousSymbolQuery> &V, SymbolState S) {
1697         return V->getRequiredState() <= S;
1698       });
1699   PendingQueries.insert(I.base(), std::move(Q));
1700 }
1701
1702 void JITDylib::MaterializingInfo::removeQuery(
1703     const AsynchronousSymbolQuery &Q) {
1704   // FIXME: Implement 'find_as' for shared_ptr<T>/T*.
1705   auto I =
1706       std::find_if(PendingQueries.begin(), PendingQueries.end(),
1707                    [&Q](const std::shared_ptr<AsynchronousSymbolQuery> &V) {
1708                      return V.get() == &Q;
1709                    });
1710   assert(I != PendingQueries.end() &&
1711          "Query is not attached to this MaterializingInfo");
1712   PendingQueries.erase(I);
1713 }
1714
1715 JITDylib::AsynchronousSymbolQueryList
1716 JITDylib::MaterializingInfo::takeQueriesMeeting(SymbolState RequiredState) {
1717   AsynchronousSymbolQueryList Result;
1718   while (!PendingQueries.empty()) {
1719     if (PendingQueries.back()->getRequiredState() > RequiredState)
1720       break;
1721
1722     Result.push_back(std::move(PendingQueries.back()));
1723     PendingQueries.pop_back();
1724   }
1725
1726   return Result;
1727 }
1728
1729 JITDylib::JITDylib(ExecutionSession &ES, std::string Name)
1730     : ES(ES), JITDylibName(std::move(Name)) {
1731   SearchOrder.push_back({this, true});
1732 }
1733
1734 Error JITDylib::defineImpl(MaterializationUnit &MU) {
1735   SymbolNameSet Duplicates;
1736   std::vector<SymbolStringPtr> ExistingDefsOverridden;
1737   std::vector<SymbolStringPtr> MUDefsOverridden;
1738
1739   for (const auto &KV : MU.getSymbols()) {
1740     auto I = Symbols.find(KV.first);
1741
1742     if (I != Symbols.end()) {
1743       if (KV.second.isStrong()) {
1744         if (I->second.getFlags().isStrong() ||
1745             I->second.getState() > SymbolState::NeverSearched)
1746           Duplicates.insert(KV.first);
1747         else {
1748           assert(I->second.getState() == SymbolState::NeverSearched &&
1749                  "Overridden existing def should be in the never-searched "
1750                  "state");
1751           ExistingDefsOverridden.push_back(KV.first);
1752         }
1753       } else
1754         MUDefsOverridden.push_back(KV.first);
1755     }
1756   }
1757
1758   // If there were any duplicate definitions then bail out.
1759   if (!Duplicates.empty())
1760     return make_error<DuplicateDefinition>(**Duplicates.begin());
1761
1762   // Discard any overridden defs in this MU.
1763   for (auto &S : MUDefsOverridden)
1764     MU.doDiscard(*this, S);
1765
1766   // Discard existing overridden defs.
1767   for (auto &S : ExistingDefsOverridden) {
1768
1769     auto UMII = UnmaterializedInfos.find(S);
1770     assert(UMII != UnmaterializedInfos.end() &&
1771            "Overridden existing def should have an UnmaterializedInfo");
1772     UMII->second->MU->doDiscard(*this, S);
1773   }
1774
1775   // Finally, add the defs from this MU.
1776   for (auto &KV : MU.getSymbols()) {
1777     auto &SymEntry = Symbols[KV.first];
1778     SymEntry.setFlags(KV.second);
1779     SymEntry.setState(SymbolState::NeverSearched);
1780     SymEntry.setMaterializerAttached(true);
1781   }
1782
1783   return Error::success();
1784 }
1785
1786 void JITDylib::detachQueryHelper(AsynchronousSymbolQuery &Q,
1787                                  const SymbolNameSet &QuerySymbols) {
1788   for (auto &QuerySymbol : QuerySymbols) {
1789     assert(MaterializingInfos.count(QuerySymbol) &&
1790            "QuerySymbol does not have MaterializingInfo");
1791     auto &MI = MaterializingInfos[QuerySymbol];
1792     MI.removeQuery(Q);
1793   }
1794 }
1795
1796 void JITDylib::transferEmittedNodeDependencies(
1797     MaterializingInfo &DependantMI, const SymbolStringPtr &DependantName,
1798     MaterializingInfo &EmittedMI) {
1799   for (auto &KV : EmittedMI.UnemittedDependencies) {
1800     auto &DependencyJD = *KV.first;
1801     SymbolNameSet *UnemittedDependenciesOnDependencyJD = nullptr;
1802
1803     for (auto &DependencyName : KV.second) {
1804       auto &DependencyMI = DependencyJD.MaterializingInfos[DependencyName];
1805
1806       // Do not add self dependencies.
1807       if (&DependencyMI == &DependantMI)
1808         continue;
1809
1810       // If we haven't looked up the dependencies for DependencyJD yet, do it
1811       // now and cache the result.
1812       if (!UnemittedDependenciesOnDependencyJD)
1813         UnemittedDependenciesOnDependencyJD =
1814             &DependantMI.UnemittedDependencies[&DependencyJD];
1815
1816       DependencyMI.Dependants[this].insert(DependantName);
1817       UnemittedDependenciesOnDependencyJD->insert(DependencyName);
1818     }
1819   }
1820 }
1821
1822 ExecutionSession::ExecutionSession(std::shared_ptr<SymbolStringPool> SSP)
1823     : SSP(SSP ? std::move(SSP) : std::make_shared<SymbolStringPool>()) {
1824   // Construct the main dylib.
1825   JDs.push_back(std::unique_ptr<JITDylib>(new JITDylib(*this, "<main>")));
1826 }
1827
1828 JITDylib &ExecutionSession::getMainJITDylib() {
1829   return runSessionLocked([this]() -> JITDylib & { return *JDs.front(); });
1830 }
1831
1832 JITDylib *ExecutionSession::getJITDylibByName(StringRef Name) {
1833   return runSessionLocked([&, this]() -> JITDylib * {
1834     for (auto &JD : JDs)
1835       if (JD->getName() == Name)
1836         return JD.get();
1837     return nullptr;
1838   });
1839 }
1840
1841 JITDylib &ExecutionSession::createJITDylib(std::string Name,
1842                                            bool AddToMainDylibSearchOrder) {
1843   assert(!getJITDylibByName(Name) && "JITDylib with that name already exists");
1844   return runSessionLocked([&, this]() -> JITDylib & {
1845     JDs.push_back(
1846         std::unique_ptr<JITDylib>(new JITDylib(*this, std::move(Name))));
1847     if (AddToMainDylibSearchOrder)
1848       JDs.front()->addToSearchOrder(*JDs.back());
1849     return *JDs.back();
1850   });
1851 }
1852
1853 void ExecutionSession::legacyFailQuery(AsynchronousSymbolQuery &Q, Error Err) {
1854   assert(!!Err && "Error should be in failure state");
1855
1856   bool SendErrorToQuery;
1857   runSessionLocked([&]() {
1858     Q.detach();
1859     SendErrorToQuery = Q.canStillFail();
1860   });
1861
1862   if (SendErrorToQuery)
1863     Q.handleFailed(std::move(Err));
1864   else
1865     reportError(std::move(Err));
1866 }
1867
1868 Expected<SymbolMap> ExecutionSession::legacyLookup(
1869     LegacyAsyncLookupFunction AsyncLookup, SymbolNameSet Names,
1870     SymbolState RequiredState,
1871     RegisterDependenciesFunction RegisterDependencies) {
1872 #if LLVM_ENABLE_THREADS
1873   // In the threaded case we use promises to return the results.
1874   std::promise<SymbolMap> PromisedResult;
1875   Error ResolutionError = Error::success();
1876   auto NotifyComplete = [&](Expected<SymbolMap> R) {
1877     if (R)
1878       PromisedResult.set_value(std::move(*R));
1879     else {
1880       ErrorAsOutParameter _(&ResolutionError);
1881       ResolutionError = R.takeError();
1882       PromisedResult.set_value(SymbolMap());
1883     }
1884   };
1885 #else
1886   SymbolMap Result;
1887   Error ResolutionError = Error::success();
1888
1889   auto NotifyComplete = [&](Expected<SymbolMap> R) {
1890     ErrorAsOutParameter _(&ResolutionError);
1891     if (R)
1892       Result = std::move(*R);
1893     else
1894       ResolutionError = R.takeError();
1895   };
1896 #endif
1897
1898   auto Query = std::make_shared<AsynchronousSymbolQuery>(
1899       Names, RequiredState, std::move(NotifyComplete));
1900   // FIXME: This should be run session locked along with the registration code
1901   // and error reporting below.
1902   SymbolNameSet UnresolvedSymbols = AsyncLookup(Query, std::move(Names));
1903
1904   // If the query was lodged successfully then register the dependencies,
1905   // otherwise fail it with an error.
1906   if (UnresolvedSymbols.empty())
1907     RegisterDependencies(Query->QueryRegistrations);
1908   else {
1909     bool DeliverError = runSessionLocked([&]() {
1910       Query->detach();
1911       return Query->canStillFail();
1912     });
1913     auto Err = make_error<SymbolsNotFound>(std::move(UnresolvedSymbols));
1914     if (DeliverError)
1915       Query->handleFailed(std::move(Err));
1916     else
1917       reportError(std::move(Err));
1918   }
1919
1920 #if LLVM_ENABLE_THREADS
1921   auto ResultFuture = PromisedResult.get_future();
1922   auto Result = ResultFuture.get();
1923   if (ResolutionError)
1924     return std::move(ResolutionError);
1925   return std::move(Result);
1926
1927 #else
1928   if (ResolutionError)
1929     return std::move(ResolutionError);
1930
1931   return Result;
1932 #endif
1933 }
1934
1935 void ExecutionSession::lookup(
1936     const JITDylibSearchList &SearchOrder, SymbolNameSet Symbols,
1937     SymbolState RequiredState, SymbolsResolvedCallback NotifyComplete,
1938     RegisterDependenciesFunction RegisterDependencies) {
1939
1940   LLVM_DEBUG({
1941     runSessionLocked([&]() {
1942       dbgs() << "Looking up " << Symbols << " in " << SearchOrder
1943              << " (required state: " << RequiredState << ")\n";
1944     });
1945   });
1946
1947   // lookup can be re-entered recursively if running on a single thread. Run any
1948   // outstanding MUs in case this query depends on them, otherwise this lookup
1949   // will starve waiting for a result from an MU that is stuck in the queue.
1950   runOutstandingMUs();
1951
1952   auto Unresolved = std::move(Symbols);
1953   std::map<JITDylib *, MaterializationUnitList> CollectedMUsMap;
1954   auto Q = std::make_shared<AsynchronousSymbolQuery>(Unresolved, RequiredState,
1955                                                      std::move(NotifyComplete));
1956   bool QueryComplete = false;
1957
1958   auto LodgingErr = runSessionLocked([&]() -> Error {
1959     auto LodgeQuery = [&]() -> Error {
1960       for (auto &KV : SearchOrder) {
1961         assert(KV.first && "JITDylibList entries must not be null");
1962         assert(!CollectedMUsMap.count(KV.first) &&
1963                "JITDylibList should not contain duplicate entries");
1964
1965         auto &JD = *KV.first;
1966         auto MatchNonExported = KV.second;
1967         if (auto Err = JD.lodgeQuery(Q, Unresolved, MatchNonExported,
1968                                      CollectedMUsMap[&JD]))
1969           return Err;
1970       }
1971
1972       if (!Unresolved.empty())
1973         return make_error<SymbolsNotFound>(std::move(Unresolved));
1974
1975       return Error::success();
1976     };
1977
1978     if (auto Err = LodgeQuery()) {
1979       // Query failed.
1980
1981       // Disconnect the query from its dependencies.
1982       Q->detach();
1983
1984       // Replace the MUs.
1985       for (auto &KV : CollectedMUsMap)
1986         for (auto &MU : KV.second)
1987           KV.first->replace(std::move(MU));
1988
1989       return Err;
1990     }
1991
1992     // Query lodged successfully.
1993
1994     // Record whether this query is fully ready / resolved. We will use
1995     // this to call handleFullyResolved/handleFullyReady outside the session
1996     // lock.
1997     QueryComplete = Q->isComplete();
1998
1999     // Call the register dependencies function.
2000     if (RegisterDependencies && !Q->QueryRegistrations.empty())
2001       RegisterDependencies(Q->QueryRegistrations);
2002
2003     return Error::success();
2004   });
2005
2006   if (LodgingErr) {
2007     Q->handleFailed(std::move(LodgingErr));
2008     return;
2009   }
2010
2011   if (QueryComplete)
2012     Q->handleComplete();
2013
2014   // Move the MUs to the OutstandingMUs list, then materialize.
2015   {
2016     std::lock_guard<std::recursive_mutex> Lock(OutstandingMUsMutex);
2017
2018     for (auto &KV : CollectedMUsMap)
2019       for (auto &MU : KV.second)
2020         OutstandingMUs.push_back(std::make_pair(KV.first, std::move(MU)));
2021   }
2022
2023   runOutstandingMUs();
2024 }
2025
2026 Expected<SymbolMap>
2027 ExecutionSession::lookup(const JITDylibSearchList &SearchOrder,
2028                          const SymbolNameSet &Symbols,
2029                          SymbolState RequiredState,
2030                          RegisterDependenciesFunction RegisterDependencies) {
2031 #if LLVM_ENABLE_THREADS
2032   // In the threaded case we use promises to return the results.
2033   std::promise<SymbolMap> PromisedResult;
2034   Error ResolutionError = Error::success();
2035
2036   auto NotifyComplete = [&](Expected<SymbolMap> R) {
2037     if (R)
2038       PromisedResult.set_value(std::move(*R));
2039     else {
2040       ErrorAsOutParameter _(&ResolutionError);
2041       ResolutionError = R.takeError();
2042       PromisedResult.set_value(SymbolMap());
2043     }
2044   };
2045
2046 #else
2047   SymbolMap Result;
2048   Error ResolutionError = Error::success();
2049
2050   auto NotifyComplete = [&](Expected<SymbolMap> R) {
2051     ErrorAsOutParameter _(&ResolutionError);
2052     if (R)
2053       Result = std::move(*R);
2054     else
2055       ResolutionError = R.takeError();
2056   };
2057 #endif
2058
2059   // Perform the asynchronous lookup.
2060   lookup(SearchOrder, Symbols, RequiredState, NotifyComplete,
2061          RegisterDependencies);
2062
2063 #if LLVM_ENABLE_THREADS
2064   auto ResultFuture = PromisedResult.get_future();
2065   auto Result = ResultFuture.get();
2066
2067   if (ResolutionError)
2068     return std::move(ResolutionError);
2069
2070   return std::move(Result);
2071
2072 #else
2073   if (ResolutionError)
2074     return std::move(ResolutionError);
2075
2076   return Result;
2077 #endif
2078 }
2079
2080 Expected<JITEvaluatedSymbol>
2081 ExecutionSession::lookup(const JITDylibSearchList &SearchOrder,
2082                          SymbolStringPtr Name) {
2083   SymbolNameSet Names({Name});
2084
2085   if (auto ResultMap = lookup(SearchOrder, std::move(Names), SymbolState::Ready,
2086                               NoDependenciesToRegister)) {
2087     assert(ResultMap->size() == 1 && "Unexpected number of results");
2088     assert(ResultMap->count(Name) && "Missing result for symbol");
2089     return std::move(ResultMap->begin()->second);
2090   } else
2091     return ResultMap.takeError();
2092 }
2093
2094 Expected<JITEvaluatedSymbol>
2095 ExecutionSession::lookup(ArrayRef<JITDylib *> SearchOrder,
2096                          SymbolStringPtr Name) {
2097   SymbolNameSet Names({Name});
2098
2099   JITDylibSearchList FullSearchOrder;
2100   FullSearchOrder.reserve(SearchOrder.size());
2101   for (auto *JD : SearchOrder)
2102     FullSearchOrder.push_back({JD, false});
2103
2104   return lookup(FullSearchOrder, Name);
2105 }
2106
2107 Expected<JITEvaluatedSymbol>
2108 ExecutionSession::lookup(ArrayRef<JITDylib *> SearchOrder, StringRef Name) {
2109   return lookup(SearchOrder, intern(Name));
2110 }
2111
2112 void ExecutionSession::dump(raw_ostream &OS) {
2113   runSessionLocked([this, &OS]() {
2114     for (auto &JD : JDs)
2115       JD->dump(OS);
2116   });
2117 }
2118
2119 void ExecutionSession::runOutstandingMUs() {
2120   while (1) {
2121     std::pair<JITDylib *, std::unique_ptr<MaterializationUnit>> JITDylibAndMU;
2122
2123     {
2124       std::lock_guard<std::recursive_mutex> Lock(OutstandingMUsMutex);
2125       if (!OutstandingMUs.empty()) {
2126         JITDylibAndMU = std::move(OutstandingMUs.back());
2127         OutstandingMUs.pop_back();
2128       }
2129     }
2130
2131     if (JITDylibAndMU.first) {
2132       assert(JITDylibAndMU.second && "JITDylib, but no MU?");
2133       dispatchMaterialization(*JITDylibAndMU.first,
2134                               std::move(JITDylibAndMU.second));
2135     } else
2136       break;
2137   }
2138 }
2139
2140 MangleAndInterner::MangleAndInterner(ExecutionSession &ES, const DataLayout &DL)
2141     : ES(ES), DL(DL) {}
2142
2143 SymbolStringPtr MangleAndInterner::operator()(StringRef Name) {
2144   std::string MangledName;
2145   {
2146     raw_string_ostream MangledNameStream(MangledName);
2147     Mangler::getNameWithPrefix(MangledNameStream, Name, DL);
2148   }
2149   return ES.intern(MangledName);
2150 }
2151
2152 } // End namespace orc.
2153 } // End namespace llvm.