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