contrib/llvm/lib/ExecutionEngine/Orc/Core.cpp

   1 //===----- Core.cpp - Core ORC APIs (MaterializationUnit, VSO, etc.) ------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/ExecutionEngine/Orc/Core.h"
  11 #include "llvm/Config/llvm-config.h"
  12 #include "llvm/ExecutionEngine/Orc/OrcError.h"
  13 #include "llvm/IR/Mangler.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 namespace llvm {
  22 namespace orc {
  23
  24 char FailedToMaterialize::ID = 0;
  25 char SymbolsNotFound::ID = 0;
  26
  27 RegisterDependenciesFunction NoDependenciesToRegister =
  28     RegisterDependenciesFunction();
  29
  30 void MaterializationUnit::anchor() {}
  31
  32 raw_ostream &operator<<(raw_ostream &OS, const JITSymbolFlags &Flags) {
  33   if (Flags.isWeak())
  34     OS << 'W';
  35   else if (Flags.isCommon())
  36     OS << 'C';
  37   else
  38     OS << 'S';
  39
  40   if (Flags.isExported())
  41     OS << 'E';
  42   else
  43     OS << 'H';
  44
  45   return OS;
  46 }
  47
  48 raw_ostream &operator<<(raw_ostream &OS, const JITEvaluatedSymbol &Sym) {
  49   OS << format("0x%016x", Sym.getAddress()) << " " << Sym.getFlags();
  50   return OS;
  51 }
  52
  53 raw_ostream &operator<<(raw_ostream &OS, const SymbolMap::value_type &KV) {
  54   OS << "\"" << *KV.first << "\": " << KV.second;
  55   return OS;
  56 }
  57
  58 raw_ostream &operator<<(raw_ostream &OS, const SymbolNameSet &Symbols) {
  59   OS << "{";
  60   if (!Symbols.empty()) {
  61     OS << " \"" << **Symbols.begin() << "\"";
  62     for (auto &Sym : make_range(std::next(Symbols.begin()), Symbols.end()))
  63       OS << ", \"" << *Sym << "\"";
  64   }
  65   OS << " }";
  66   return OS;
  67 }
  68
  69 raw_ostream &operator<<(raw_ostream &OS, const SymbolMap &Symbols) {
  70   OS << "{";
  71   if (!Symbols.empty()) {
  72     OS << " {" << *Symbols.begin() << "}";
  73     for (auto &Sym : make_range(std::next(Symbols.begin()), Symbols.end()))
  74       OS << ", {" << Sym << "}";
  75   }
  76   OS << " }";
  77   return OS;
  78 }
  79
  80 raw_ostream &operator<<(raw_ostream &OS, const SymbolFlagsMap &SymbolFlags) {
  81   OS << "{";
  82   if (!SymbolFlags.empty()) {
  83     OS << " {\"" << *SymbolFlags.begin()->first
  84        << "\": " << SymbolFlags.begin()->second << "}";
  85     for (auto &KV :
  86          make_range(std::next(SymbolFlags.begin()), SymbolFlags.end()))
  87       OS << ", {\"" << *KV.first << "\": " << KV.second << "}";
  88   }
  89   OS << " }";
  90   return OS;
  91 }
  92
  93 raw_ostream &operator<<(raw_ostream &OS, const SymbolDependenceMap &Deps) {
  94   OS << "{";
  95   if (!Deps.empty()) {
  96     OS << " { " << Deps.begin()->first->getName() << ": "
  97        << Deps.begin()->second << " }";
  98     for (auto &KV : make_range(std::next(Deps.begin()), Deps.end()))
  99       OS << ", { " << KV.first->getName() << ": " << KV.second << " }";
 100   }
 101   OS << " }";
 102   return OS;
 103 }
 104
 105 raw_ostream &operator<<(raw_ostream &OS, const VSOList &VSOs) {
 106   OS << "[";
 107   if (!VSOs.empty()) {
 108     assert(VSOs.front() && "VSOList entries must not be null");
 109     OS << " " << VSOs.front()->getName();
 110     for (auto *V : make_range(std::next(VSOs.begin()), VSOs.end())) {
 111       assert(V && "VSOList entries must not be null");
 112       OS << ", " << V->getName();
 113     }
 114   }
 115   OS << " ]";
 116   return OS;
 117 }
 118
 119 FailedToMaterialize::FailedToMaterialize(SymbolNameSet Symbols)
 120     : Symbols(std::move(Symbols)) {
 121   assert(!this->Symbols.empty() && "Can not fail to resolve an empty set");
 122 }
 123
 124 std::error_code FailedToMaterialize::convertToErrorCode() const {
 125   return orcError(OrcErrorCode::UnknownORCError);
 126 }
 127
 128 void FailedToMaterialize::log(raw_ostream &OS) const {
 129   OS << "Failed to materialize symbols: " << Symbols;
 130 }
 131
 132 SymbolsNotFound::SymbolsNotFound(SymbolNameSet Symbols)
 133     : Symbols(std::move(Symbols)) {
 134   assert(!this->Symbols.empty() && "Can not fail to resolve an empty set");
 135 }
 136
 137 std::error_code SymbolsNotFound::convertToErrorCode() const {
 138   return orcError(OrcErrorCode::UnknownORCError);
 139 }
 140
 141 void SymbolsNotFound::log(raw_ostream &OS) const {
 142   OS << "Symbols not found: " << Symbols;
 143 }
 144
 145 void ExecutionSessionBase::legacyFailQuery(AsynchronousSymbolQuery &Q,
 146                                            Error Err) {
 147   assert(!!Err && "Error should be in failure state");
 148
 149   bool SendErrorToQuery;
 150   runSessionLocked([&]() {
 151     Q.detach();
 152     SendErrorToQuery = Q.canStillFail();
 153   });
 154
 155   if (SendErrorToQuery)
 156     Q.handleFailed(std::move(Err));
 157   else
 158     reportError(std::move(Err));
 159 }
 160
 161 Expected<SymbolMap> ExecutionSessionBase::legacyLookup(
 162     ExecutionSessionBase &ES, LegacyAsyncLookupFunction AsyncLookup,
 163     SymbolNameSet Names, bool WaitUntilReady,
 164     RegisterDependenciesFunction RegisterDependencies) {
 165 #if LLVM_ENABLE_THREADS
 166   // In the threaded case we use promises to return the results.
 167   std::promise<SymbolMap> PromisedResult;
 168   std::mutex ErrMutex;
 169   Error ResolutionError = Error::success();
 170   std::promise<void> PromisedReady;
 171   Error ReadyError = Error::success();
 172   auto OnResolve = [&](Expected<SymbolMap> R) {
 173     if (R)
 174       PromisedResult.set_value(std::move(*R));
 175     else {
 176       {
 177         ErrorAsOutParameter _(&ResolutionError);
 178         std::lock_guard<std::mutex> Lock(ErrMutex);
 179         ResolutionError = R.takeError();
 180       }
 181       PromisedResult.set_value(SymbolMap());
 182     }
 183   };
 184
 185   std::function<void(Error)> OnReady;
 186   if (WaitUntilReady) {
 187     OnReady = [&](Error Err) {
 188       if (Err) {
 189         ErrorAsOutParameter _(&ReadyError);
 190         std::lock_guard<std::mutex> Lock(ErrMutex);
 191         ReadyError = std::move(Err);
 192       }
 193       PromisedReady.set_value();
 194     };
 195   } else {
 196     OnReady = [&](Error Err) {
 197       if (Err)
 198         ES.reportError(std::move(Err));
 199     };
 200   }
 201
 202 #else
 203   SymbolMap Result;
 204   Error ResolutionError = Error::success();
 205   Error ReadyError = Error::success();
 206
 207   auto OnResolve = [&](Expected<SymbolMap> R) {
 208     ErrorAsOutParameter _(&ResolutionError);
 209     if (R)
 210       Result = std::move(*R);
 211     else
 212       ResolutionError = R.takeError();
 213   };
 214
 215   std::function<void(Error)> OnReady;
 216   if (WaitUntilReady) {
 217     OnReady = [&](Error Err) {
 218       ErrorAsOutParameter _(&ReadyError);
 219       if (Err)
 220         ReadyError = std::move(Err);
 221     };
 222   } else {
 223     OnReady = [&](Error Err) {
 224       if (Err)
 225         ES.reportError(std::move(Err));
 226     };
 227   }
 228 #endif
 229
 230   auto Query = std::make_shared<AsynchronousSymbolQuery>(
 231       Names, std::move(OnResolve), std::move(OnReady));
 232   // FIXME: This should be run session locked along with the registration code
 233   // and error reporting below.
 234   SymbolNameSet UnresolvedSymbols = AsyncLookup(Query, std::move(Names));
 235
 236   // If the query was lodged successfully then register the dependencies,
 237   // otherwise fail it with an error.
 238   if (UnresolvedSymbols.empty())
 239     RegisterDependencies(Query->QueryRegistrations);
 240   else {
 241     bool DeliverError = runSessionLocked([&]() {
 242       Query->detach();
 243       return Query->canStillFail();
 244     });
 245     auto Err = make_error<SymbolsNotFound>(std::move(UnresolvedSymbols));
 246     if (DeliverError)
 247       Query->handleFailed(std::move(Err));
 248     else
 249       ES.reportError(std::move(Err));
 250   }
 251
 252 #if LLVM_ENABLE_THREADS
 253   auto ResultFuture = PromisedResult.get_future();
 254   auto Result = ResultFuture.get();
 255
 256   {
 257     std::lock_guard<std::mutex> Lock(ErrMutex);
 258     if (ResolutionError) {
 259       // ReadyError will never be assigned. Consume the success value.
 260       cantFail(std::move(ReadyError));
 261       return std::move(ResolutionError);
 262     }
 263   }
 264
 265   if (WaitUntilReady) {
 266     auto ReadyFuture = PromisedReady.get_future();
 267     ReadyFuture.get();
 268
 269     {
 270       std::lock_guard<std::mutex> Lock(ErrMutex);
 271       if (ReadyError)
 272         return std::move(ReadyError);
 273     }
 274   } else
 275     cantFail(std::move(ReadyError));
 276
 277   return std::move(Result);
 278
 279 #else
 280   if (ResolutionError) {
 281     // ReadyError will never be assigned. Consume the success value.
 282     cantFail(std::move(ReadyError));
 283     return std::move(ResolutionError);
 284   }
 285
 286   if (ReadyError)
 287     return std::move(ReadyError);
 288
 289   return Result;
 290 #endif
 291 }
 292
 293 void ExecutionSessionBase::lookup(
 294     const VSOList &VSOs, const SymbolNameSet &Symbols,
 295     SymbolsResolvedCallback OnResolve, SymbolsReadyCallback OnReady,
 296     RegisterDependenciesFunction RegisterDependencies) {
 297
 298   // lookup can be re-entered recursively if running on a single thread. Run any
 299   // outstanding MUs in case this query depends on them, otherwise the main
 300   // thread will starve waiting for a result from an MU that it failed to run.
 301   runOutstandingMUs();
 302
 303   auto Unresolved = std::move(Symbols);
 304   std::map<VSO *, MaterializationUnitList> MUsMap;
 305   auto Q = std::make_shared<AsynchronousSymbolQuery>(
 306       Symbols, std::move(OnResolve), std::move(OnReady));
 307   bool QueryIsFullyResolved = false;
 308   bool QueryIsFullyReady = false;
 309   bool QueryFailed = false;
 310
 311   runSessionLocked([&]() {
 312     for (auto *V : VSOs) {
 313       assert(V && "VSOList entries must not be null");
 314       assert(!MUsMap.count(V) &&
 315              "VSOList should not contain duplicate entries");
 316       V->lodgeQuery(Q, Unresolved, MUsMap[V]);
 317     }
 318
 319     if (Unresolved.empty()) {
 320       // Query lodged successfully.
 321
 322       // Record whether this query is fully ready / resolved. We will use
 323       // this to call handleFullyResolved/handleFullyReady outside the session
 324       // lock.
 325       QueryIsFullyResolved = Q->isFullyResolved();
 326       QueryIsFullyReady = Q->isFullyReady();
 327
 328       // Call the register dependencies function.
 329       if (RegisterDependencies && !Q->QueryRegistrations.empty())
 330         RegisterDependencies(Q->QueryRegistrations);
 331     } else {
 332       // Query failed due to unresolved symbols.
 333       QueryFailed = true;
 334
 335       // Disconnect the query from its dependencies.
 336       Q->detach();
 337
 338       // Replace the MUs.
 339       for (auto &KV : MUsMap)
 340         for (auto &MU : KV.second)
 341           KV.first->replace(std::move(MU));
 342     }
 343   });
 344
 345   if (QueryFailed) {
 346     Q->handleFailed(make_error<SymbolsNotFound>(std::move(Unresolved)));
 347     return;
 348   } else {
 349     if (QueryIsFullyResolved)
 350       Q->handleFullyResolved();
 351     if (QueryIsFullyReady)
 352       Q->handleFullyReady();
 353   }
 354
 355   // Move the MUs to the OutstandingMUs list, then materialize.
 356   {
 357     std::lock_guard<std::recursive_mutex> Lock(OutstandingMUsMutex);
 358
 359     for (auto &KV : MUsMap)
 360       for (auto &MU : KV.second)
 361         OutstandingMUs.push_back(std::make_pair(KV.first, std::move(MU)));
 362   }
 363
 364   runOutstandingMUs();
 365 }
 366
 367 Expected<SymbolMap>
 368 ExecutionSessionBase::lookup(const VSOList &VSOs, const SymbolNameSet &Symbols,
 369                              RegisterDependenciesFunction RegisterDependencies,
 370                              bool WaitUntilReady) {
 371 #if LLVM_ENABLE_THREADS
 372   // In the threaded case we use promises to return the results.
 373   std::promise<SymbolMap> PromisedResult;
 374   std::mutex ErrMutex;
 375   Error ResolutionError = Error::success();
 376   std::promise<void> PromisedReady;
 377   Error ReadyError = Error::success();
 378   auto OnResolve = [&](Expected<SymbolMap> R) {
 379     if (R)
 380       PromisedResult.set_value(std::move(*R));
 381     else {
 382       {
 383         ErrorAsOutParameter _(&ResolutionError);
 384         std::lock_guard<std::mutex> Lock(ErrMutex);
 385         ResolutionError = R.takeError();
 386       }
 387       PromisedResult.set_value(SymbolMap());
 388     }
 389   };
 390
 391   std::function<void(Error)> OnReady;
 392   if (WaitUntilReady) {
 393     OnReady = [&](Error Err) {
 394       if (Err) {
 395         ErrorAsOutParameter _(&ReadyError);
 396         std::lock_guard<std::mutex> Lock(ErrMutex);
 397         ReadyError = std::move(Err);
 398       }
 399       PromisedReady.set_value();
 400     };
 401   } else {
 402     OnReady = [&](Error Err) {
 403       if (Err)
 404         reportError(std::move(Err));
 405     };
 406   }
 407
 408 #else
 409   SymbolMap Result;
 410   Error ResolutionError = Error::success();
 411   Error ReadyError = Error::success();
 412
 413   auto OnResolve = [&](Expected<SymbolMap> R) {
 414     ErrorAsOutParameter _(&ResolutionError);
 415     if (R)
 416       Result = std::move(*R);
 417     else
 418       ResolutionError = R.takeError();
 419   };
 420
 421   std::function<void(Error)> OnReady;
 422   if (WaitUntilReady) {
 423     OnReady = [&](Error Err) {
 424       ErrorAsOutParameter _(&ReadyError);
 425       if (Err)
 426         ReadyError = std::move(Err);
 427     };
 428   } else {
 429     OnReady = [&](Error Err) {
 430       if (Err)
 431         reportError(std::move(Err));
 432     };
 433   }
 434 #endif
 435
 436   // Perform the asynchronous lookup.
 437   lookup(VSOs, Symbols, OnResolve, OnReady, RegisterDependencies);
 438
 439 #if LLVM_ENABLE_THREADS
 440   auto ResultFuture = PromisedResult.get_future();
 441   auto Result = ResultFuture.get();
 442
 443   {
 444     std::lock_guard<std::mutex> Lock(ErrMutex);
 445     if (ResolutionError) {
 446       // ReadyError will never be assigned. Consume the success value.
 447       cantFail(std::move(ReadyError));
 448       return std::move(ResolutionError);
 449     }
 450   }
 451
 452   if (WaitUntilReady) {
 453     auto ReadyFuture = PromisedReady.get_future();
 454     ReadyFuture.get();
 455
 456     {
 457       std::lock_guard<std::mutex> Lock(ErrMutex);
 458       if (ReadyError)
 459         return std::move(ReadyError);
 460     }
 461   } else
 462     cantFail(std::move(ReadyError));
 463
 464   return std::move(Result);
 465
 466 #else
 467   if (ResolutionError) {
 468     // ReadyError will never be assigned. Consume the success value.
 469     cantFail(std::move(ReadyError));
 470     return std::move(ResolutionError);
 471   }
 472
 473   if (ReadyError)
 474     return std::move(ReadyError);
 475
 476   return Result;
 477 #endif
 478 }
 479
 480 void ExecutionSessionBase::runOutstandingMUs() {
 481   while (1) {
 482     std::pair<VSO *, std::unique_ptr<MaterializationUnit>> VSOAndMU;
 483
 484     {
 485       std::lock_guard<std::recursive_mutex> Lock(OutstandingMUsMutex);
 486       if (!OutstandingMUs.empty()) {
 487         VSOAndMU = std::move(OutstandingMUs.back());
 488         OutstandingMUs.pop_back();
 489       }
 490     }
 491
 492     if (VSOAndMU.first) {
 493       assert(VSOAndMU.second && "VSO, but no MU?");
 494       dispatchMaterialization(*VSOAndMU.first, std::move(VSOAndMU.second));
 495     } else
 496       break;
 497   }
 498 }
 499
 500 AsynchronousSymbolQuery::AsynchronousSymbolQuery(
 501     const SymbolNameSet &Symbols, SymbolsResolvedCallback NotifySymbolsResolved,
 502     SymbolsReadyCallback NotifySymbolsReady)
 503     : NotifySymbolsResolved(std::move(NotifySymbolsResolved)),
 504       NotifySymbolsReady(std::move(NotifySymbolsReady)) {
 505   NotYetResolvedCount = NotYetReadyCount = Symbols.size();
 506
 507   for (auto &S : Symbols)
 508     ResolvedSymbols[S] = nullptr;
 509 }
 510
 511 void AsynchronousSymbolQuery::resolve(const SymbolStringPtr &Name,
 512                                       JITEvaluatedSymbol Sym) {
 513   auto I = ResolvedSymbols.find(Name);
 514   assert(I != ResolvedSymbols.end() &&
 515          "Resolving symbol outside the requested set");
 516   assert(I->second.getAddress() == 0 && "Redundantly resolving symbol Name");
 517   I->second = std::move(Sym);
 518   --NotYetResolvedCount;
 519 }
 520
 521 void AsynchronousSymbolQuery::handleFullyResolved() {
 522   assert(NotYetResolvedCount == 0 && "Not fully resolved?");
 523   assert(NotifySymbolsResolved &&
 524          "NotifySymbolsResolved already called or error occurred");
 525   NotifySymbolsResolved(std::move(ResolvedSymbols));
 526   NotifySymbolsResolved = SymbolsResolvedCallback();
 527 }
 528
 529 void AsynchronousSymbolQuery::notifySymbolReady() {
 530   assert(NotYetReadyCount != 0 && "All symbols already finalized");
 531   --NotYetReadyCount;
 532 }
 533
 534 void AsynchronousSymbolQuery::handleFullyReady() {
 535   assert(QueryRegistrations.empty() &&
 536          "Query is still registered with some symbols");
 537   assert(!NotifySymbolsResolved && "Resolution not applied yet");
 538   NotifySymbolsReady(Error::success());
 539   NotifySymbolsReady = SymbolsReadyCallback();
 540 }
 541
 542 bool AsynchronousSymbolQuery::canStillFail() {
 543   return (NotifySymbolsResolved || NotifySymbolsReady);
 544 }
 545
 546 void AsynchronousSymbolQuery::handleFailed(Error Err) {
 547   assert(QueryRegistrations.empty() && ResolvedSymbols.empty() &&
 548          NotYetResolvedCount == 0 && NotYetReadyCount == 0 &&
 549          "Query should already have been abandoned");
 550   if (NotifySymbolsResolved) {
 551     NotifySymbolsResolved(std::move(Err));
 552     NotifySymbolsResolved = SymbolsResolvedCallback();
 553   } else {
 554     assert(NotifySymbolsReady && "Failed after both callbacks issued?");
 555     NotifySymbolsReady(std::move(Err));
 556   }
 557   NotifySymbolsReady = SymbolsReadyCallback();
 558 }
 559
 560 void AsynchronousSymbolQuery::addQueryDependence(VSO &V, SymbolStringPtr Name) {
 561   bool Added = QueryRegistrations[&V].insert(std::move(Name)).second;
 562   (void)Added;
 563   assert(Added && "Duplicate dependence notification?");
 564 }
 565
 566 void AsynchronousSymbolQuery::removeQueryDependence(
 567     VSO &V, const SymbolStringPtr &Name) {
 568   auto QRI = QueryRegistrations.find(&V);
 569   assert(QRI != QueryRegistrations.end() && "No dependencies registered for V");
 570   assert(QRI->second.count(Name) && "No dependency on Name in V");
 571   QRI->second.erase(Name);
 572   if (QRI->second.empty())
 573     QueryRegistrations.erase(QRI);
 574 }
 575
 576 void AsynchronousSymbolQuery::detach() {
 577   ResolvedSymbols.clear();
 578   NotYetResolvedCount = 0;
 579   NotYetReadyCount = 0;
 580   for (auto &KV : QueryRegistrations)
 581     KV.first->detachQueryHelper(*this, KV.second);
 582   QueryRegistrations.clear();
 583 }
 584
 585 MaterializationResponsibility::MaterializationResponsibility(
 586     VSO &V, SymbolFlagsMap SymbolFlags)
 587     : V(V), SymbolFlags(std::move(SymbolFlags)) {
 588   assert(!this->SymbolFlags.empty() && "Materializing nothing?");
 589
 590 #ifndef NDEBUG
 591   for (auto &KV : this->SymbolFlags)
 592     KV.second |= JITSymbolFlags::Materializing;
 593 #endif
 594 }
 595
 596 MaterializationResponsibility::~MaterializationResponsibility() {
 597   assert(SymbolFlags.empty() &&
 598          "All symbols should have been explicitly materialized or failed");
 599 }
 600
 601 SymbolNameSet MaterializationResponsibility::getRequestedSymbols() {
 602   return V.getRequestedSymbols(SymbolFlags);
 603 }
 604
 605 void MaterializationResponsibility::resolve(const SymbolMap &Symbols) {
 606 #ifndef NDEBUG
 607   for (auto &KV : Symbols) {
 608     auto I = SymbolFlags.find(KV.first);
 609     assert(I != SymbolFlags.end() &&
 610            "Resolving symbol outside this responsibility set");
 611     assert(I->second.isMaterializing() && "Duplicate resolution");
 612     I->second &= ~JITSymbolFlags::Materializing;
 613     if (I->second.isWeak())
 614       assert(I->second == (KV.second.getFlags() | JITSymbolFlags::Weak) &&
 615              "Resolving symbol with incorrect flags");
 616     else
 617       assert(I->second == KV.second.getFlags() &&
 618              "Resolving symbol with incorrect flags");
 619   }
 620 #endif
 621
 622   V.resolve(Symbols);
 623 }
 624
 625 void MaterializationResponsibility::finalize() {
 626 #ifndef NDEBUG
 627   for (auto &KV : SymbolFlags)
 628     assert(!KV.second.isMaterializing() &&
 629            "Failed to resolve symbol before finalization");
 630 #endif // NDEBUG
 631
 632   V.finalize(SymbolFlags);
 633   SymbolFlags.clear();
 634 }
 635
 636 Error MaterializationResponsibility::defineMaterializing(
 637     const SymbolFlagsMap &NewSymbolFlags) {
 638   // Add the given symbols to this responsibility object.
 639   // It's ok if we hit a duplicate here: In that case the new version will be
 640   // discarded, and the VSO::defineMaterializing method will return a duplicate
 641   // symbol error.
 642   for (auto &KV : NewSymbolFlags) {
 643     auto I = SymbolFlags.insert(KV).first;
 644     (void)I;
 645 #ifndef NDEBUG
 646     I->second |= JITSymbolFlags::Materializing;
 647 #endif
 648   }
 649
 650   return V.defineMaterializing(NewSymbolFlags);
 651 }
 652
 653 void MaterializationResponsibility::failMaterialization() {
 654
 655   SymbolNameSet FailedSymbols;
 656   for (auto &KV : SymbolFlags)
 657     FailedSymbols.insert(KV.first);
 658
 659   V.notifyFailed(FailedSymbols);
 660   SymbolFlags.clear();
 661 }
 662
 663 void MaterializationResponsibility::replace(
 664     std::unique_ptr<MaterializationUnit> MU) {
 665   for (auto &KV : MU->getSymbols())
 666     SymbolFlags.erase(KV.first);
 667
 668   V.replace(std::move(MU));
 669 }
 670
 671 MaterializationResponsibility
 672 MaterializationResponsibility::delegate(const SymbolNameSet &Symbols) {
 673   SymbolFlagsMap DelegatedFlags;
 674
 675   for (auto &Name : Symbols) {
 676     auto I = SymbolFlags.find(Name);
 677     assert(I != SymbolFlags.end() &&
 678            "Symbol is not tracked by this MaterializationResponsibility "
 679            "instance");
 680
 681     DelegatedFlags[Name] = std::move(I->second);
 682     SymbolFlags.erase(I);
 683   }
 684
 685   return MaterializationResponsibility(V, std::move(DelegatedFlags));
 686 }
 687
 688 void MaterializationResponsibility::addDependencies(
 689     const SymbolStringPtr &Name, const SymbolDependenceMap &Dependencies) {
 690   assert(SymbolFlags.count(Name) &&
 691          "Symbol not covered by this MaterializationResponsibility instance");
 692   V.addDependencies(Name, Dependencies);
 693 }
 694
 695 void MaterializationResponsibility::addDependenciesForAll(
 696     const SymbolDependenceMap &Dependencies) {
 697   for (auto &KV : SymbolFlags)
 698     V.addDependencies(KV.first, Dependencies);
 699 }
 700
 701 AbsoluteSymbolsMaterializationUnit::AbsoluteSymbolsMaterializationUnit(
 702     SymbolMap Symbols)
 703     : MaterializationUnit(extractFlags(Symbols)), Symbols(std::move(Symbols)) {}
 704
 705 void AbsoluteSymbolsMaterializationUnit::materialize(
 706     MaterializationResponsibility R) {
 707   R.resolve(Symbols);
 708   R.finalize();
 709 }
 710
 711 void AbsoluteSymbolsMaterializationUnit::discard(const VSO &V,
 712                                                  SymbolStringPtr Name) {
 713   assert(Symbols.count(Name) && "Symbol is not part of this MU");
 714   Symbols.erase(Name);
 715 }
 716
 717 SymbolFlagsMap
 718 AbsoluteSymbolsMaterializationUnit::extractFlags(const SymbolMap &Symbols) {
 719   SymbolFlagsMap Flags;
 720   for (const auto &KV : Symbols)
 721     Flags[KV.first] = KV.second.getFlags();
 722   return Flags;
 723 }
 724
 725 ReExportsMaterializationUnit::ReExportsMaterializationUnit(
 726     VSO *SourceVSO, SymbolAliasMap Aliases)
 727     : MaterializationUnit(extractFlags(Aliases)), SourceVSO(SourceVSO),
 728       Aliases(std::move(Aliases)) {}
 729
 730 void ReExportsMaterializationUnit::materialize(
 731     MaterializationResponsibility R) {
 732
 733   auto &ES = R.getTargetVSO().getExecutionSession();
 734   VSO &TgtV = R.getTargetVSO();
 735   VSO &SrcV = SourceVSO ? *SourceVSO : TgtV;
 736
 737   // Find the set of requested aliases and aliasees. Return any unrequested
 738   // aliases back to the VSO so as to not prematurely materialize any aliasees.
 739   auto RequestedSymbols = R.getRequestedSymbols();
 740   SymbolAliasMap RequestedAliases;
 741
 742   for (auto &Name : RequestedSymbols) {
 743     auto I = Aliases.find(Name);
 744     assert(I != Aliases.end() && "Symbol not found in aliases map?");
 745     RequestedAliases[Name] = std::move(I->second);
 746     Aliases.erase(I);
 747   }
 748
 749   if (!Aliases.empty()) {
 750     if (SourceVSO)
 751       R.replace(reexports(*SourceVSO, std::move(Aliases)));
 752     else
 753       R.replace(symbolAliases(std::move(Aliases)));
 754   }
 755
 756   // The OnResolveInfo struct will hold the aliases and responsibilty for each
 757   // query in the list.
 758   struct OnResolveInfo {
 759     OnResolveInfo(MaterializationResponsibility R, SymbolAliasMap Aliases)
 760         : R(std::move(R)), Aliases(std::move(Aliases)) {}
 761
 762     MaterializationResponsibility R;
 763     SymbolAliasMap Aliases;
 764   };
 765
 766   // Build a list of queries to issue. In each round we build the largest set of
 767   // aliases that we can resolve without encountering a chain definition of the
 768   // form Foo -> Bar, Bar -> Baz. Such a form would deadlock as the query would
 769   // be waitin on a symbol that it itself had to resolve. Usually this will just
 770   // involve one round and a single query.
 771
 772   std::vector<std::pair<SymbolNameSet, std::shared_ptr<OnResolveInfo>>>
 773       QueryInfos;
 774   while (!RequestedAliases.empty()) {
 775     SymbolNameSet ResponsibilitySymbols;
 776     SymbolNameSet QuerySymbols;
 777     SymbolAliasMap QueryAliases;
 778
 779     for (auto I = RequestedAliases.begin(), E = RequestedAliases.end();
 780          I != E;) {
 781       auto Tmp = I++;
 782
 783       // Chain detected. Skip this symbol for this round.
 784       if (&SrcV == &TgtV && (QueryAliases.count(Tmp->second.Aliasee) ||
 785                              RequestedAliases.count(Tmp->second.Aliasee)))
 786         continue;
 787
 788       ResponsibilitySymbols.insert(Tmp->first);
 789       QuerySymbols.insert(Tmp->second.Aliasee);
 790       QueryAliases[Tmp->first] = std::move(Tmp->second);
 791       RequestedAliases.erase(Tmp);
 792     }
 793     assert(!QuerySymbols.empty() && "Alias cycle detected!");
 794
 795     auto QueryInfo = std::make_shared<OnResolveInfo>(
 796         R.delegate(ResponsibilitySymbols), std::move(QueryAliases));
 797     QueryInfos.push_back(
 798         make_pair(std::move(QuerySymbols), std::move(QueryInfo)));
 799   }
 800
 801   // Issue the queries.
 802   while (!QueryInfos.empty()) {
 803     auto QuerySymbols = std::move(QueryInfos.back().first);
 804     auto QueryInfo = std::move(QueryInfos.back().second);
 805
 806     QueryInfos.pop_back();
 807
 808     auto RegisterDependencies = [QueryInfo,
 809                                  &SrcV](const SymbolDependenceMap &Deps) {
 810       // If there were no materializing symbols, just bail out.
 811       if (Deps.empty())
 812         return;
 813
 814       // Otherwise the only deps should be on SrcV.
 815       assert(Deps.size() == 1 && Deps.count(&SrcV) &&
 816              "Unexpected dependencies for reexports");
 817
 818       auto &SrcVDeps = Deps.find(&SrcV)->second;
 819       SymbolDependenceMap PerAliasDepsMap;
 820       auto &PerAliasDeps = PerAliasDepsMap[&SrcV];
 821
 822       for (auto &KV : QueryInfo->Aliases)
 823         if (SrcVDeps.count(KV.second.Aliasee)) {
 824           PerAliasDeps = {KV.second.Aliasee};
 825           QueryInfo->R.addDependencies(KV.first, PerAliasDepsMap);
 826         }
 827     };
 828
 829     auto OnResolve = [QueryInfo](Expected<SymbolMap> Result) {
 830       if (Result) {
 831         SymbolMap ResolutionMap;
 832         for (auto &KV : QueryInfo->Aliases) {
 833           assert(Result->count(KV.second.Aliasee) &&
 834                  "Result map missing entry?");
 835           ResolutionMap[KV.first] = JITEvaluatedSymbol(
 836               (*Result)[KV.second.Aliasee].getAddress(), KV.second.AliasFlags);
 837         }
 838         QueryInfo->R.resolve(ResolutionMap);
 839         QueryInfo->R.finalize();
 840       } else {
 841         auto &ES = QueryInfo->R.getTargetVSO().getExecutionSession();
 842         ES.reportError(Result.takeError());
 843         QueryInfo->R.failMaterialization();
 844       }
 845     };
 846
 847     auto OnReady = [&ES](Error Err) { ES.reportError(std::move(Err)); };
 848
 849     ES.lookup({&SrcV}, QuerySymbols, std::move(OnResolve), std::move(OnReady),
 850               std::move(RegisterDependencies));
 851   }
 852 }
 853
 854 void ReExportsMaterializationUnit::discard(const VSO &V, SymbolStringPtr Name) {
 855   assert(Aliases.count(Name) &&
 856          "Symbol not covered by this MaterializationUnit");
 857   Aliases.erase(Name);
 858 }
 859
 860 SymbolFlagsMap
 861 ReExportsMaterializationUnit::extractFlags(const SymbolAliasMap &Aliases) {
 862   SymbolFlagsMap SymbolFlags;
 863   for (auto &KV : Aliases)
 864     SymbolFlags[KV.first] = KV.second.AliasFlags;
 865
 866   return SymbolFlags;
 867 }
 868
 869 Expected<SymbolAliasMap>
 870 buildSimpleReexportsAliasMap(VSO &SourceV, const SymbolNameSet &Symbols) {
 871   auto Flags = SourceV.lookupFlags(Symbols);
 872
 873   if (Flags.size() != Symbols.size()) {
 874     SymbolNameSet Unresolved = Symbols;
 875     for (auto &KV : Flags)
 876       Unresolved.erase(KV.first);
 877     return make_error<SymbolsNotFound>(std::move(Unresolved));
 878   }
 879
 880   SymbolAliasMap Result;
 881   for (auto &Name : Symbols) {
 882     assert(Flags.count(Name) && "Missing entry in flags map");
 883     Result[Name] = SymbolAliasMapEntry(Name, Flags[Name]);
 884   }
 885
 886   return Result;
 887 }
 888
 889 Error VSO::defineMaterializing(const SymbolFlagsMap &SymbolFlags) {
 890   return ES.runSessionLocked([&]() -> Error {
 891     std::vector<SymbolMap::iterator> AddedSyms;
 892
 893     for (auto &KV : SymbolFlags) {
 894       SymbolMap::iterator EntryItr;
 895       bool Added;
 896
 897       auto NewFlags = KV.second;
 898       NewFlags |= JITSymbolFlags::Materializing;
 899
 900       std::tie(EntryItr, Added) = Symbols.insert(
 901           std::make_pair(KV.first, JITEvaluatedSymbol(0, NewFlags)));
 902
 903       if (Added)
 904         AddedSyms.push_back(EntryItr);
 905       else {
 906         // Remove any symbols already added.
 907         for (auto &SI : AddedSyms)
 908           Symbols.erase(SI);
 909
 910         // FIXME: Return all duplicates.
 911         return make_error<DuplicateDefinition>(*KV.first);
 912       }
 913     }
 914
 915     return Error::success();
 916   });
 917 }
 918
 919 void VSO::replace(std::unique_ptr<MaterializationUnit> MU) {
 920   assert(MU != nullptr && "Can not replace with a null MaterializationUnit");
 921
 922   auto MustRunMU =
 923       ES.runSessionLocked([&, this]() -> std::unique_ptr<MaterializationUnit> {
 924
 925 #ifndef NDEBUG
 926         for (auto &KV : MU->getSymbols()) {
 927           auto SymI = Symbols.find(KV.first);
 928           assert(SymI != Symbols.end() && "Replacing unknown symbol");
 929           assert(!SymI->second.getFlags().isLazy() &&
 930                  SymI->second.getFlags().isMaterializing() &&
 931                  "Can not replace symbol that is not materializing");
 932           assert(UnmaterializedInfos.count(KV.first) == 0 &&
 933                  "Symbol being replaced should have no UnmaterializedInfo");
 934         }
 935 #endif // NDEBUG
 936
 937         // If any symbol has pending queries against it then we need to
 938         // materialize MU immediately.
 939         for (auto &KV : MU->getSymbols()) {
 940           auto MII = MaterializingInfos.find(KV.first);
 941           if (MII != MaterializingInfos.end()) {
 942             if (!MII->second.PendingQueries.empty())
 943               return std::move(MU);
 944           }
 945         }
 946
 947         // Otherwise, make MU responsible for all the symbols.
 948         auto UMI = std::make_shared<UnmaterializedInfo>(std::move(MU));
 949         for (auto &KV : UMI->MU->getSymbols()) {
 950           assert(!KV.second.isLazy() &&
 951                  "Lazy flag should be managed internally.");
 952           assert(!KV.second.isMaterializing() &&
 953                  "Materializing flags should be managed internally.");
 954
 955           auto SymI = Symbols.find(KV.first);
 956           JITSymbolFlags ReplaceFlags = KV.second;
 957           ReplaceFlags |= JITSymbolFlags::Lazy;
 958           SymI->second = JITEvaluatedSymbol(SymI->second.getAddress(),
 959                                             std::move(ReplaceFlags));
 960           UnmaterializedInfos[KV.first] = UMI;
 961         }
 962
 963         return nullptr;
 964       });
 965
 966   if (MustRunMU)
 967     ES.dispatchMaterialization(*this, std::move(MustRunMU));
 968 }
 969
 970 SymbolNameSet VSO::getRequestedSymbols(const SymbolFlagsMap &SymbolFlags) {
 971   return ES.runSessionLocked([&]() {
 972     SymbolNameSet RequestedSymbols;
 973
 974     for (auto &KV : SymbolFlags) {
 975       assert(Symbols.count(KV.first) && "VSO does not cover this symbol?");
 976       assert(Symbols[KV.first].getFlags().isMaterializing() &&
 977              "getRequestedSymbols can only be called for materializing "
 978              "symbols");
 979       auto I = MaterializingInfos.find(KV.first);
 980       if (I == MaterializingInfos.end())
 981         continue;
 982
 983       if (!I->second.PendingQueries.empty())
 984         RequestedSymbols.insert(KV.first);
 985     }
 986
 987     return RequestedSymbols;
 988   });
 989 }
 990
 991 void VSO::addDependencies(const SymbolStringPtr &Name,
 992                           const SymbolDependenceMap &Dependencies) {
 993   assert(Symbols.count(Name) && "Name not in symbol table");
 994   assert((Symbols[Name].getFlags().isLazy() ||
 995           Symbols[Name].getFlags().isMaterializing()) &&
 996          "Symbol is not lazy or materializing");
 997
 998   auto &MI = MaterializingInfos[Name];
 999   assert(!MI.IsFinalized && "Can not add dependencies to finalized symbol");
1000
1001   for (auto &KV : Dependencies) {
1002     assert(KV.first && "Null VSO in dependency?");
1003     auto &OtherVSO = *KV.first;
1004     auto &DepsOnOtherVSO = MI.UnfinalizedDependencies[&OtherVSO];
1005
1006     for (auto &OtherSymbol : KV.second) {
1007 #ifndef NDEBUG
1008       // Assert that this symbol exists and has not been finalized already.
1009       auto SymI = OtherVSO.Symbols.find(OtherSymbol);
1010       assert(SymI != OtherVSO.Symbols.end() &&
1011              (SymI->second.getFlags().isLazy() ||
1012               SymI->second.getFlags().isMaterializing()) &&
1013              "Dependency on finalized symbol");
1014 #endif
1015
1016       auto &OtherMI = OtherVSO.MaterializingInfos[OtherSymbol];
1017
1018       if (OtherMI.IsFinalized)
1019         transferFinalizedNodeDependencies(MI, Name, OtherMI);
1020       else if (&OtherVSO != this || OtherSymbol != Name) {
1021         OtherMI.Dependants[this].insert(Name);
1022         DepsOnOtherVSO.insert(OtherSymbol);
1023       }
1024     }
1025
1026     if (DepsOnOtherVSO.empty())
1027       MI.UnfinalizedDependencies.erase(&OtherVSO);
1028   }
1029 }
1030
1031 void VSO::resolve(const SymbolMap &Resolved) {
1032   auto FullyResolvedQueries = ES.runSessionLocked([&, this]() {
1033     AsynchronousSymbolQuerySet FullyResolvedQueries;
1034     for (const auto &KV : Resolved) {
1035       auto &Name = KV.first;
1036       auto Sym = KV.second;
1037
1038       assert(!Sym.getFlags().isLazy() && !Sym.getFlags().isMaterializing() &&
1039              "Materializing flags should be managed internally");
1040
1041       auto I = Symbols.find(Name);
1042
1043       assert(I != Symbols.end() && "Symbol not found");
1044       assert(!I->second.getFlags().isLazy() &&
1045              I->second.getFlags().isMaterializing() &&
1046              "Symbol should be materializing");
1047       assert(I->second.getAddress() == 0 && "Symbol has already been resolved");
1048
1049       assert((Sym.getFlags() & ~JITSymbolFlags::Weak) ==
1050                  (JITSymbolFlags::stripTransientFlags(I->second.getFlags()) &
1051                   ~JITSymbolFlags::Weak) &&
1052              "Resolved flags should match the declared flags");
1053
1054       // Once resolved, symbols can never be weak.
1055       JITSymbolFlags ResolvedFlags = Sym.getFlags();
1056       ResolvedFlags &= ~JITSymbolFlags::Weak;
1057       ResolvedFlags |= JITSymbolFlags::Materializing;
1058       I->second = JITEvaluatedSymbol(Sym.getAddress(), ResolvedFlags);
1059
1060       auto &MI = MaterializingInfos[Name];
1061       for (auto &Q : MI.PendingQueries) {
1062         Q->resolve(Name, Sym);
1063         if (Q->isFullyResolved())
1064           FullyResolvedQueries.insert(Q);
1065       }
1066     }
1067
1068     return FullyResolvedQueries;
1069   });
1070
1071   for (auto &Q : FullyResolvedQueries) {
1072     assert(Q->isFullyResolved() && "Q not fully resolved");
1073     Q->handleFullyResolved();
1074   }
1075 }
1076
1077 void VSO::finalize(const SymbolFlagsMap &Finalized) {
1078   auto FullyReadyQueries = ES.runSessionLocked([&, this]() {
1079     AsynchronousSymbolQuerySet ReadyQueries;
1080
1081     for (const auto &KV : Finalized) {
1082       const auto &Name = KV.first;
1083
1084       auto MII = MaterializingInfos.find(Name);
1085       assert(MII != MaterializingInfos.end() &&
1086              "Missing MaterializingInfo entry");
1087
1088       auto &MI = MII->second;
1089
1090       // For each dependant, transfer this node's unfinalized dependencies to
1091       // it. If the dependant node is fully finalized then notify any pending
1092       // queries.
1093       for (auto &KV : MI.Dependants) {
1094         auto &DependantVSO = *KV.first;
1095         for (auto &DependantName : KV.second) {
1096           auto DependantMII =
1097               DependantVSO.MaterializingInfos.find(DependantName);
1098           assert(DependantMII != DependantVSO.MaterializingInfos.end() &&
1099                  "Dependant should have MaterializingInfo");
1100
1101           auto &DependantMI = DependantMII->second;
1102
1103           // Remove the dependant's dependency on this node.
1104           assert(DependantMI.UnfinalizedDependencies[this].count(Name) &&
1105                  "Dependant does not count this symbol as a dependency?");
1106           DependantMI.UnfinalizedDependencies[this].erase(Name);
1107           if (DependantMI.UnfinalizedDependencies[this].empty())
1108             DependantMI.UnfinalizedDependencies.erase(this);
1109
1110           // Transfer unfinalized dependencies from this node to the dependant.
1111           DependantVSO.transferFinalizedNodeDependencies(DependantMI,
1112                                                          DependantName, MI);
1113
1114           // If the dependant is finalized and this node was the last of its
1115           // unfinalized dependencies then notify any pending queries on the
1116           // dependant node.
1117           if (DependantMI.IsFinalized &&
1118               DependantMI.UnfinalizedDependencies.empty()) {
1119             assert(DependantMI.Dependants.empty() &&
1120                    "Dependants should be empty by now");
1121             for (auto &Q : DependantMI.PendingQueries) {
1122               Q->notifySymbolReady();
1123               if (Q->isFullyReady())
1124                 ReadyQueries.insert(Q);
1125               Q->removeQueryDependence(DependantVSO, DependantName);
1126             }
1127
1128             // If this dependant node was fully finalized we can erase its
1129             // MaterializingInfo and update its materializing state.
1130             assert(DependantVSO.Symbols.count(DependantName) &&
1131                    "Dependant has no entry in the Symbols table");
1132             auto &DependantSym = DependantVSO.Symbols[DependantName];
1133             DependantSym.setFlags(static_cast<JITSymbolFlags::FlagNames>(
1134                 DependantSym.getFlags() & ~JITSymbolFlags::Materializing));
1135             DependantVSO.MaterializingInfos.erase(DependantMII);
1136           }
1137         }
1138       }
1139       MI.Dependants.clear();
1140       MI.IsFinalized = true;
1141
1142       if (MI.UnfinalizedDependencies.empty()) {
1143         for (auto &Q : MI.PendingQueries) {
1144           Q->notifySymbolReady();
1145           if (Q->isFullyReady())
1146             ReadyQueries.insert(Q);
1147           Q->removeQueryDependence(*this, Name);
1148         }
1149         assert(Symbols.count(Name) &&
1150                "Symbol has no entry in the Symbols table");
1151         auto &Sym = Symbols[Name];
1152         Sym.setFlags(static_cast<JITSymbolFlags::FlagNames>(
1153             Sym.getFlags() & ~JITSymbolFlags::Materializing));
1154         MaterializingInfos.erase(MII);
1155       }
1156     }
1157
1158     return ReadyQueries;
1159   });
1160
1161   for (auto &Q : FullyReadyQueries) {
1162     assert(Q->isFullyReady() && "Q is not fully ready");
1163     Q->handleFullyReady();
1164   }
1165 }
1166
1167 void VSO::notifyFailed(const SymbolNameSet &FailedSymbols) {
1168
1169   // FIXME: This should fail any transitively dependant symbols too.
1170
1171   auto FailedQueriesToNotify = ES.runSessionLocked([&, this]() {
1172     AsynchronousSymbolQuerySet FailedQueries;
1173
1174     for (auto &Name : FailedSymbols) {
1175       auto I = Symbols.find(Name);
1176       assert(I != Symbols.end() && "Symbol not present in this VSO");
1177       Symbols.erase(I);
1178
1179       auto MII = MaterializingInfos.find(Name);
1180
1181       // If we have not created a MaterializingInfo for this symbol yet then
1182       // there is nobody to notify.
1183       if (MII == MaterializingInfos.end())
1184         continue;
1185
1186       // Copy all the queries to the FailedQueries list, then abandon them.
1187       // This has to be a copy, and the copy has to come before the abandon
1188       // operation: Each Q.detach() call will reach back into this
1189       // PendingQueries list to remove Q.
1190       for (auto &Q : MII->second.PendingQueries)
1191         FailedQueries.insert(Q);
1192
1193       for (auto &Q : FailedQueries)
1194         Q->detach();
1195
1196       assert(MII->second.PendingQueries.empty() &&
1197              "Queries remain after symbol was failed");
1198
1199       MaterializingInfos.erase(MII);
1200     }
1201
1202     return FailedQueries;
1203   });
1204
1205   for (auto &Q : FailedQueriesToNotify)
1206     Q->handleFailed(make_error<FailedToMaterialize>(FailedSymbols));
1207 }
1208
1209 void VSO::setSearchOrder(VSOList NewSearchOrder, bool SearchThisVSOFirst) {
1210   if (SearchThisVSOFirst && NewSearchOrder.front() != this)
1211     NewSearchOrder.insert(NewSearchOrder.begin(), this);
1212
1213   ES.runSessionLocked([&]() { SearchOrder = std::move(NewSearchOrder); });
1214 }
1215
1216 void VSO::addToSearchOrder(VSO &V) {
1217   ES.runSessionLocked([&]() { SearchOrder.push_back(&V); });
1218 }
1219
1220 void VSO::replaceInSearchOrder(VSO &OldV, VSO &NewV) {
1221   ES.runSessionLocked([&]() {
1222     auto I = std::find(SearchOrder.begin(), SearchOrder.end(), &OldV);
1223
1224     if (I != SearchOrder.end())
1225       *I = &NewV;
1226   });
1227 }
1228
1229 void VSO::removeFromSearchOrder(VSO &V) {
1230   ES.runSessionLocked([&]() {
1231     auto I = std::find(SearchOrder.begin(), SearchOrder.end(), &V);
1232     if (I != SearchOrder.end())
1233       SearchOrder.erase(I);
1234   });
1235 }
1236
1237 SymbolFlagsMap VSO::lookupFlags(const SymbolNameSet &Names) {
1238   return ES.runSessionLocked([&, this]() {
1239     SymbolFlagsMap Result;
1240     auto Unresolved = lookupFlagsImpl(Result, Names);
1241     if (FallbackDefinitionGenerator && !Unresolved.empty()) {
1242       auto FallbackDefs = FallbackDefinitionGenerator(*this, Unresolved);
1243       if (!FallbackDefs.empty()) {
1244         auto Unresolved2 = lookupFlagsImpl(Result, FallbackDefs);
1245         (void)Unresolved2;
1246         assert(Unresolved2.empty() &&
1247                "All fallback defs should have been found by lookupFlagsImpl");
1248       }
1249     };
1250     return Result;
1251   });
1252 }
1253
1254 SymbolNameSet VSO::lookupFlagsImpl(SymbolFlagsMap &Flags,
1255                                    const SymbolNameSet &Names) {
1256   SymbolNameSet Unresolved;
1257
1258   for (auto &Name : Names) {
1259     auto I = Symbols.find(Name);
1260
1261     if (I == Symbols.end()) {
1262       Unresolved.insert(Name);
1263       continue;
1264     }
1265
1266     assert(!Flags.count(Name) && "Symbol already present in Flags map");
1267     Flags[Name] = JITSymbolFlags::stripTransientFlags(I->second.getFlags());
1268   }
1269
1270   return Unresolved;
1271 }
1272
1273 void VSO::lodgeQuery(std::shared_ptr<AsynchronousSymbolQuery> &Q,
1274                      SymbolNameSet &Unresolved, MaterializationUnitList &MUs) {
1275   assert(Q && "Query can not be null");
1276
1277   lodgeQueryImpl(Q, Unresolved, MUs);
1278   if (FallbackDefinitionGenerator && !Unresolved.empty()) {
1279     auto FallbackDefs = FallbackDefinitionGenerator(*this, Unresolved);
1280     if (!FallbackDefs.empty()) {
1281       for (auto &D : FallbackDefs)
1282         Unresolved.erase(D);
1283       lodgeQueryImpl(Q, FallbackDefs, MUs);
1284       assert(FallbackDefs.empty() &&
1285              "All fallback defs should have been found by lookupImpl");
1286     }
1287   }
1288 }
1289
1290 void VSO::lodgeQueryImpl(
1291     std::shared_ptr<AsynchronousSymbolQuery> &Q, SymbolNameSet &Unresolved,
1292     std::vector<std::unique_ptr<MaterializationUnit>> &MUs) {
1293   for (auto I = Unresolved.begin(), E = Unresolved.end(); I != E;) {
1294     auto TmpI = I++;
1295     auto Name = *TmpI;
1296
1297     // Search for the name in Symbols. Skip it if not found.
1298     auto SymI = Symbols.find(Name);
1299     if (SymI == Symbols.end())
1300       continue;
1301
1302     // If we found Name in V, remove it frome the Unresolved set and add it
1303     // to the added set.
1304     Unresolved.erase(TmpI);
1305
1306     // If the symbol has an address then resolve it.
1307     if (SymI->second.getAddress() != 0)
1308       Q->resolve(Name, SymI->second);
1309
1310     // If the symbol is lazy, get the MaterialiaztionUnit for it.
1311     if (SymI->second.getFlags().isLazy()) {
1312       assert(SymI->second.getAddress() == 0 &&
1313              "Lazy symbol should not have a resolved address");
1314       assert(!SymI->second.getFlags().isMaterializing() &&
1315              "Materializing and lazy should not both be set");
1316       auto UMII = UnmaterializedInfos.find(Name);
1317       assert(UMII != UnmaterializedInfos.end() &&
1318              "Lazy symbol should have UnmaterializedInfo");
1319       auto MU = std::move(UMII->second->MU);
1320       assert(MU != nullptr && "Materializer should not be null");
1321
1322       // Move all symbols associated with this MaterializationUnit into
1323       // materializing state.
1324       for (auto &KV : MU->getSymbols()) {
1325         auto SymK = Symbols.find(KV.first);
1326         auto Flags = SymK->second.getFlags();
1327         Flags &= ~JITSymbolFlags::Lazy;
1328         Flags |= JITSymbolFlags::Materializing;
1329         SymK->second.setFlags(Flags);
1330         UnmaterializedInfos.erase(KV.first);
1331       }
1332
1333       // Add MU to the list of MaterializationUnits to be materialized.
1334       MUs.push_back(std::move(MU));
1335     } else if (!SymI->second.getFlags().isMaterializing()) {
1336       // The symbol is neither lazy nor materializing. Finalize it and
1337       // continue.
1338       Q->notifySymbolReady();
1339       continue;
1340     }
1341
1342     // Add the query to the PendingQueries list.
1343     assert(SymI->second.getFlags().isMaterializing() &&
1344            "By this line the symbol should be materializing");
1345     auto &MI = MaterializingInfos[Name];
1346     MI.PendingQueries.push_back(Q);
1347     Q->addQueryDependence(*this, Name);
1348   }
1349 }
1350
1351 SymbolNameSet VSO::legacyLookup(std::shared_ptr<AsynchronousSymbolQuery> Q,
1352                                 SymbolNameSet Names) {
1353   assert(Q && "Query can not be null");
1354
1355   ES.runOutstandingMUs();
1356
1357   LookupImplActionFlags ActionFlags = None;
1358   std::vector<std::unique_ptr<MaterializationUnit>> MUs;
1359
1360   SymbolNameSet Unresolved = std::move(Names);
1361   ES.runSessionLocked([&, this]() {
1362     ActionFlags = lookupImpl(Q, MUs, Unresolved);
1363     if (FallbackDefinitionGenerator && !Unresolved.empty()) {
1364       assert(ActionFlags == None &&
1365              "ActionFlags set but unresolved symbols remain?");
1366       auto FallbackDefs = FallbackDefinitionGenerator(*this, Unresolved);
1367       if (!FallbackDefs.empty()) {
1368         for (auto &D : FallbackDefs)
1369           Unresolved.erase(D);
1370         ActionFlags = lookupImpl(Q, MUs, FallbackDefs);
1371         assert(FallbackDefs.empty() &&
1372                "All fallback defs should have been found by lookupImpl");
1373       }
1374     }
1375   });
1376
1377   assert((MUs.empty() || ActionFlags == None) &&
1378          "If action flags are set, there should be no work to do (so no MUs)");
1379
1380   if (ActionFlags & NotifyFullyResolved)
1381     Q->handleFullyResolved();
1382
1383   if (ActionFlags & NotifyFullyReady)
1384     Q->handleFullyReady();
1385
1386   // FIXME: Swap back to the old code below once RuntimeDyld works with
1387   //        callbacks from asynchronous queries.
1388   // Add MUs to the OutstandingMUs list.
1389   {
1390     std::lock_guard<std::recursive_mutex> Lock(ES.OutstandingMUsMutex);
1391     for (auto &MU : MUs)
1392       ES.OutstandingMUs.push_back(make_pair(this, std::move(MU)));
1393   }
1394   ES.runOutstandingMUs();
1395
1396   // Dispatch any required MaterializationUnits for materialization.
1397   // for (auto &MU : MUs)
1398   //  ES.dispatchMaterialization(*this, std::move(MU));
1399
1400   return Unresolved;
1401 }
1402
1403 VSO::LookupImplActionFlags
1404 VSO::lookupImpl(std::shared_ptr<AsynchronousSymbolQuery> &Q,
1405                 std::vector<std::unique_ptr<MaterializationUnit>> &MUs,
1406                 SymbolNameSet &Unresolved) {
1407   LookupImplActionFlags ActionFlags = None;
1408
1409   for (auto I = Unresolved.begin(), E = Unresolved.end(); I != E;) {
1410     auto TmpI = I++;
1411     auto Name = *TmpI;
1412
1413     // Search for the name in Symbols. Skip it if not found.
1414     auto SymI = Symbols.find(Name);
1415     if (SymI == Symbols.end())
1416       continue;
1417
1418     // If we found Name in V, remove it frome the Unresolved set and add it
1419     // to the dependencies set.
1420     Unresolved.erase(TmpI);
1421
1422     // If the symbol has an address then resolve it.
1423     if (SymI->second.getAddress() != 0) {
1424       Q->resolve(Name, SymI->second);
1425       if (Q->isFullyResolved())
1426         ActionFlags |= NotifyFullyResolved;
1427     }
1428
1429     // If the symbol is lazy, get the MaterialiaztionUnit for it.
1430     if (SymI->second.getFlags().isLazy()) {
1431       assert(SymI->second.getAddress() == 0 &&
1432              "Lazy symbol should not have a resolved address");
1433       assert(!SymI->second.getFlags().isMaterializing() &&
1434              "Materializing and lazy should not both be set");
1435       auto UMII = UnmaterializedInfos.find(Name);
1436       assert(UMII != UnmaterializedInfos.end() &&
1437              "Lazy symbol should have UnmaterializedInfo");
1438       auto MU = std::move(UMII->second->MU);
1439       assert(MU != nullptr && "Materializer should not be null");
1440
1441       // Kick all symbols associated with this MaterializationUnit into
1442       // materializing state.
1443       for (auto &KV : MU->getSymbols()) {
1444         auto SymK = Symbols.find(KV.first);
1445         auto Flags = SymK->second.getFlags();
1446         Flags &= ~JITSymbolFlags::Lazy;
1447         Flags |= JITSymbolFlags::Materializing;
1448         SymK->second.setFlags(Flags);
1449         UnmaterializedInfos.erase(KV.first);
1450       }
1451
1452       // Add MU to the list of MaterializationUnits to be materialized.
1453       MUs.push_back(std::move(MU));
1454     } else if (!SymI->second.getFlags().isMaterializing()) {
1455       // The symbol is neither lazy nor materializing. Finalize it and
1456       // continue.
1457       Q->notifySymbolReady();
1458       if (Q->isFullyReady())
1459         ActionFlags |= NotifyFullyReady;
1460       continue;
1461     }
1462
1463     // Add the query to the PendingQueries list.
1464     assert(SymI->second.getFlags().isMaterializing() &&
1465            "By this line the symbol should be materializing");
1466     auto &MI = MaterializingInfos[Name];
1467     MI.PendingQueries.push_back(Q);
1468     Q->addQueryDependence(*this, Name);
1469   }
1470
1471   return ActionFlags;
1472 }
1473
1474 void VSO::dump(raw_ostream &OS) {
1475   ES.runSessionLocked([&, this]() {
1476     OS << "VSO \"" << VSOName
1477        << "\" (ES: " << format("0x%016x", reinterpret_cast<uintptr_t>(&ES))
1478        << "):\n"
1479        << "Symbol table:\n";
1480
1481     for (auto &KV : Symbols) {
1482       OS << "    \"" << *KV.first
1483          << "\": " << format("0x%016x", KV.second.getAddress());
1484       if (KV.second.getFlags().isLazy() ||
1485           KV.second.getFlags().isMaterializing()) {
1486         OS << " (";
1487         if (KV.second.getFlags().isLazy()) {
1488           auto I = UnmaterializedInfos.find(KV.first);
1489           assert(I != UnmaterializedInfos.end() &&
1490                  "Lazy symbol should have UnmaterializedInfo");
1491           OS << " Lazy (MU=" << I->second->MU.get() << ")";
1492         }
1493         if (KV.second.getFlags().isMaterializing())
1494           OS << " Materializing";
1495         OS << " )\n";
1496       } else
1497         OS << "\n";
1498     }
1499
1500     if (!MaterializingInfos.empty())
1501       OS << "  MaterializingInfos entries:\n";
1502     for (auto &KV : MaterializingInfos) {
1503       OS << "    \"" << *KV.first << "\":\n"
1504          << "      IsFinalized = " << (KV.second.IsFinalized ? "true" : "false")
1505          << "\n"
1506          << "      " << KV.second.PendingQueries.size()
1507          << " pending queries: { ";
1508       for (auto &Q : KV.second.PendingQueries)
1509         OS << Q.get() << " ";
1510       OS << "}\n      Dependants:\n";
1511       for (auto &KV2 : KV.second.Dependants)
1512         OS << "        " << KV2.first->getName() << ": " << KV2.second << "\n";
1513       OS << "      Unfinalized Dependencies:\n";
1514       for (auto &KV2 : KV.second.UnfinalizedDependencies)
1515         OS << "        " << KV2.first->getName() << ": " << KV2.second << "\n";
1516     }
1517   });
1518 }
1519
1520 VSO::VSO(ExecutionSessionBase &ES, std::string Name)
1521     : ES(ES), VSOName(std::move(Name)) {
1522   SearchOrder.push_back(this);
1523 }
1524
1525 Error VSO::defineImpl(MaterializationUnit &MU) {
1526   SymbolNameSet Duplicates;
1527   SymbolNameSet MUDefsOverridden;
1528
1529   struct ExistingDefOverriddenEntry {
1530     SymbolMap::iterator ExistingDefItr;
1531     JITSymbolFlags NewFlags;
1532   };
1533   std::vector<ExistingDefOverriddenEntry> ExistingDefsOverridden;
1534
1535   for (auto &KV : MU.getSymbols()) {
1536     assert(!KV.second.isLazy() && "Lazy flag should be managed internally.");
1537     assert(!KV.second.isMaterializing() &&
1538            "Materializing flags should be managed internally.");
1539
1540     SymbolMap::iterator EntryItr;
1541     bool Added;
1542
1543     auto NewFlags = KV.second;
1544     NewFlags |= JITSymbolFlags::Lazy;
1545
1546     std::tie(EntryItr, Added) = Symbols.insert(
1547         std::make_pair(KV.first, JITEvaluatedSymbol(0, NewFlags)));
1548
1549     if (!Added) {
1550       if (KV.second.isStrong()) {
1551         if (EntryItr->second.getFlags().isStrong() ||
1552             (EntryItr->second.getFlags() & JITSymbolFlags::Materializing))
1553           Duplicates.insert(KV.first);
1554         else
1555           ExistingDefsOverridden.push_back({EntryItr, NewFlags});
1556       } else
1557         MUDefsOverridden.insert(KV.first);
1558     }
1559   }
1560
1561   if (!Duplicates.empty()) {
1562     // We need to remove the symbols we added.
1563     for (auto &KV : MU.getSymbols()) {
1564       if (Duplicates.count(KV.first))
1565         continue;
1566
1567       bool Found = false;
1568       for (const auto &EDO : ExistingDefsOverridden)
1569         if (EDO.ExistingDefItr->first == KV.first)
1570           Found = true;
1571
1572       if (!Found)
1573         Symbols.erase(KV.first);
1574     }
1575
1576     // FIXME: Return all duplicates.
1577     return make_error<DuplicateDefinition>(**Duplicates.begin());
1578   }
1579
1580   // Update flags on existing defs and call discard on their materializers.
1581   for (auto &EDO : ExistingDefsOverridden) {
1582     assert(EDO.ExistingDefItr->second.getFlags().isLazy() &&
1583            !EDO.ExistingDefItr->second.getFlags().isMaterializing() &&
1584            "Overridden existing def should be in the Lazy state");
1585
1586     EDO.ExistingDefItr->second.setFlags(EDO.NewFlags);
1587
1588     auto UMII = UnmaterializedInfos.find(EDO.ExistingDefItr->first);
1589     assert(UMII != UnmaterializedInfos.end() &&
1590            "Overridden existing def should have an UnmaterializedInfo");
1591
1592     UMII->second->MU->doDiscard(*this, EDO.ExistingDefItr->first);
1593   }
1594
1595   // Discard overridden symbols povided by MU.
1596   for (auto &Sym : MUDefsOverridden)
1597     MU.doDiscard(*this, Sym);
1598
1599   return Error::success();
1600 }
1601
1602 void VSO::detachQueryHelper(AsynchronousSymbolQuery &Q,
1603                             const SymbolNameSet &QuerySymbols) {
1604   for (auto &QuerySymbol : QuerySymbols) {
1605     assert(MaterializingInfos.count(QuerySymbol) &&
1606            "QuerySymbol does not have MaterializingInfo");
1607     auto &MI = MaterializingInfos[QuerySymbol];
1608
1609     auto IdenticalQuery =
1610         [&](const std::shared_ptr<AsynchronousSymbolQuery> &R) {
1611           return R.get() == &Q;
1612         };
1613
1614     auto I = std::find_if(MI.PendingQueries.begin(), MI.PendingQueries.end(),
1615                           IdenticalQuery);
1616     assert(I != MI.PendingQueries.end() &&
1617            "Query Q should be in the PendingQueries list for QuerySymbol");
1618     MI.PendingQueries.erase(I);
1619   }
1620 }
1621
1622 void VSO::transferFinalizedNodeDependencies(
1623     MaterializingInfo &DependantMI, const SymbolStringPtr &DependantName,
1624     MaterializingInfo &FinalizedMI) {
1625   for (auto &KV : FinalizedMI.UnfinalizedDependencies) {
1626     auto &DependencyVSO = *KV.first;
1627     SymbolNameSet *UnfinalizedDependenciesOnDependencyVSO = nullptr;
1628
1629     for (auto &DependencyName : KV.second) {
1630       auto &DependencyMI = DependencyVSO.MaterializingInfos[DependencyName];
1631
1632       // Do not add self dependencies.
1633       if (&DependencyMI == &DependantMI)
1634         continue;
1635
1636       // If we haven't looked up the dependencies for DependencyVSO yet, do it
1637       // now and cache the result.
1638       if (!UnfinalizedDependenciesOnDependencyVSO)
1639         UnfinalizedDependenciesOnDependencyVSO =
1640             &DependantMI.UnfinalizedDependencies[&DependencyVSO];
1641
1642       DependencyMI.Dependants[this].insert(DependantName);
1643       UnfinalizedDependenciesOnDependencyVSO->insert(DependencyName);
1644     }
1645   }
1646 }
1647
1648 VSO &ExecutionSession::createVSO(std::string Name) {
1649   return runSessionLocked([&, this]() -> VSO & {
1650       VSOs.push_back(std::unique_ptr<VSO>(new VSO(*this, std::move(Name))));
1651     return *VSOs.back();
1652   });
1653 }
1654
1655 Expected<SymbolMap> lookup(const VSOList &VSOs, SymbolNameSet Names) {
1656
1657   if (VSOs.empty())
1658     return SymbolMap();
1659
1660   auto &ES = (*VSOs.begin())->getExecutionSession();
1661
1662   return ES.lookup(VSOs, Names, NoDependenciesToRegister, true);
1663 }
1664
1665 /// Look up a symbol by searching a list of VSOs.
1666 Expected<JITEvaluatedSymbol> lookup(const VSOList &VSOs, SymbolStringPtr Name) {
1667   SymbolNameSet Names({Name});
1668   if (auto ResultMap = lookup(VSOs, std::move(Names))) {
1669     assert(ResultMap->size() == 1 && "Unexpected number of results");
1670     assert(ResultMap->count(Name) && "Missing result for symbol");
1671     return std::move(ResultMap->begin()->second);
1672   } else
1673     return ResultMap.takeError();
1674 }
1675
1676 MangleAndInterner::MangleAndInterner(ExecutionSessionBase &ES,
1677                                      const DataLayout &DL)
1678     : ES(ES), DL(DL) {}
1679
1680 SymbolStringPtr MangleAndInterner::operator()(StringRef Name) {
1681   std::string MangledName;
1682   {
1683     raw_string_ostream MangledNameStream(MangledName);
1684     Mangler::getNameWithPrefix(MangledNameStream, Name, DL);
1685   }
1686   return ES.getSymbolStringPool().intern(MangledName);
1687 }
1688
1689 } // End namespace orc.
1690 } // End namespace llvm.