Home | History | Annotate | Download | only in Orc 
      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.
   1691