llvm/lib/ExecutionEngine/Orc/Core.cpp

   1 //===--- Core.cpp - Core ORC APIs (MaterializationUnit, JITDylib, etc.) ---===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ExecutionEngine/Orc/Core.h"
  10
  11 #include "llvm/ADT/STLExtras.h"
  12 #include "llvm/Config/llvm-config.h"
  13 #include "llvm/ExecutionEngine/Orc/DebugUtils.h"
  14 #include "llvm/ExecutionEngine/Orc/Shared/OrcError.h"
  15 #include "llvm/Support/FormatVariadic.h"
  16 #include "llvm/Support/MSVCErrorWorkarounds.h"
  17
  18 #include <condition_variable>
  19 #include <future>
  20 #include <optional>
  21
  22 #define DEBUG_TYPE "orc"
  23
  24 namespace llvm {
  25 namespace orc {
  26
  27 char ResourceTrackerDefunct::ID = 0;
  28 char FailedToMaterialize::ID = 0;
  29 char SymbolsNotFound::ID = 0;
  30 char SymbolsCouldNotBeRemoved::ID = 0;
  31 char MissingSymbolDefinitions::ID = 0;
  32 char UnexpectedSymbolDefinitions::ID = 0;
  33 char MaterializationTask::ID = 0;
  34 char LookupTask::ID = 0;
  35
  36 RegisterDependenciesFunction NoDependenciesToRegister =
  37     RegisterDependenciesFunction();
  38
  39 void MaterializationUnit::anchor() {}
  40
  41 ResourceTracker::ResourceTracker(JITDylibSP JD) {
  42   assert((reinterpret_cast<uintptr_t>(JD.get()) & 0x1) == 0 &&
  43          "JITDylib must be two byte aligned");
  44   JD->Retain();
  45   JDAndFlag.store(reinterpret_cast<uintptr_t>(JD.get()));
  46 }
  47
  48 ResourceTracker::~ResourceTracker() {
  49   getJITDylib().getExecutionSession().destroyResourceTracker(*this);
  50   getJITDylib().Release();
  51 }
  52
  53 Error ResourceTracker::remove() {
  54   return getJITDylib().getExecutionSession().removeResourceTracker(*this);
  55 }
  56
  57 void ResourceTracker::transferTo(ResourceTracker &DstRT) {
  58   getJITDylib().getExecutionSession().transferResourceTracker(DstRT, *this);
  59 }
  60
  61 void ResourceTracker::makeDefunct() {
  62   uintptr_t Val = JDAndFlag.load();
  63   Val |= 0x1U;
  64   JDAndFlag.store(Val);
  65 }
  66
  67 ResourceManager::~ResourceManager() = default;
  68
  69 ResourceTrackerDefunct::ResourceTrackerDefunct(ResourceTrackerSP RT)
  70     : RT(std::move(RT)) {}
  71
  72 std::error_code ResourceTrackerDefunct::convertToErrorCode() const {
  73   return orcError(OrcErrorCode::UnknownORCError);
  74 }
  75
  76 void ResourceTrackerDefunct::log(raw_ostream &OS) const {
  77   OS << "Resource tracker " << (void *)RT.get() << " became defunct";
  78 }
  79
  80 FailedToMaterialize::FailedToMaterialize(
  81     std::shared_ptr<SymbolStringPool> SSP,
  82     std::shared_ptr<SymbolDependenceMap> Symbols)
  83     : SSP(std::move(SSP)), Symbols(std::move(Symbols)) {
  84   assert(this->SSP && "String pool cannot be null");
  85   assert(!this->Symbols->empty() && "Can not fail to resolve an empty set");
  86
  87   // FIXME: Use a new dep-map type for FailedToMaterialize errors so that we
  88   // don't have to manually retain/release.
  89   for (auto &KV : *this->Symbols)
  90     KV.first->Retain();
  91 }
  92
  93 FailedToMaterialize::~FailedToMaterialize() {
  94   for (auto &KV : *Symbols)
  95     KV.first->Release();
  96 }
  97
  98 std::error_code FailedToMaterialize::convertToErrorCode() const {
  99   return orcError(OrcErrorCode::UnknownORCError);
 100 }
 101
 102 void FailedToMaterialize::log(raw_ostream &OS) const {
 103   OS << "Failed to materialize symbols: " << *Symbols;
 104 }
 105
 106 SymbolsNotFound::SymbolsNotFound(std::shared_ptr<SymbolStringPool> SSP,
 107                                  SymbolNameSet Symbols)
 108     : SSP(std::move(SSP)) {
 109   for (auto &Sym : Symbols)
 110     this->Symbols.push_back(Sym);
 111   assert(!this->Symbols.empty() && "Can not fail to resolve an empty set");
 112 }
 113
 114 SymbolsNotFound::SymbolsNotFound(std::shared_ptr<SymbolStringPool> SSP,
 115                                  SymbolNameVector Symbols)
 116     : SSP(std::move(SSP)), Symbols(std::move(Symbols)) {
 117   assert(!this->Symbols.empty() && "Can not fail to resolve an empty set");
 118 }
 119
 120 std::error_code SymbolsNotFound::convertToErrorCode() const {
 121   return orcError(OrcErrorCode::UnknownORCError);
 122 }
 123
 124 void SymbolsNotFound::log(raw_ostream &OS) const {
 125   OS << "Symbols not found: " << Symbols;
 126 }
 127
 128 SymbolsCouldNotBeRemoved::SymbolsCouldNotBeRemoved(
 129     std::shared_ptr<SymbolStringPool> SSP, SymbolNameSet Symbols)
 130     : SSP(std::move(SSP)), Symbols(std::move(Symbols)) {
 131   assert(!this->Symbols.empty() && "Can not fail to resolve an empty set");
 132 }
 133
 134 std::error_code SymbolsCouldNotBeRemoved::convertToErrorCode() const {
 135   return orcError(OrcErrorCode::UnknownORCError);
 136 }
 137
 138 void SymbolsCouldNotBeRemoved::log(raw_ostream &OS) const {
 139   OS << "Symbols could not be removed: " << Symbols;
 140 }
 141
 142 std::error_code MissingSymbolDefinitions::convertToErrorCode() const {
 143   return orcError(OrcErrorCode::MissingSymbolDefinitions);
 144 }
 145
 146 void MissingSymbolDefinitions::log(raw_ostream &OS) const {
 147   OS << "Missing definitions in module " << ModuleName
 148      << ": " << Symbols;
 149 }
 150
 151 std::error_code UnexpectedSymbolDefinitions::convertToErrorCode() const {
 152   return orcError(OrcErrorCode::UnexpectedSymbolDefinitions);
 153 }
 154
 155 void UnexpectedSymbolDefinitions::log(raw_ostream &OS) const {
 156   OS << "Unexpected definitions in module " << ModuleName
 157      << ": " << Symbols;
 158 }
 159
 160 AsynchronousSymbolQuery::AsynchronousSymbolQuery(
 161     const SymbolLookupSet &Symbols, SymbolState RequiredState,
 162     SymbolsResolvedCallback NotifyComplete)
 163     : NotifyComplete(std::move(NotifyComplete)), RequiredState(RequiredState) {
 164   assert(RequiredState >= SymbolState::Resolved &&
 165          "Cannot query for a symbols that have not reached the resolve state "
 166          "yet");
 167
 168   OutstandingSymbolsCount = Symbols.size();
 169
 170   for (auto &KV : Symbols)
 171     ResolvedSymbols[KV.first] = ExecutorSymbolDef();
 172 }
 173
 174 void AsynchronousSymbolQuery::notifySymbolMetRequiredState(
 175     const SymbolStringPtr &Name, ExecutorSymbolDef Sym) {
 176   auto I = ResolvedSymbols.find(Name);
 177   assert(I != ResolvedSymbols.end() &&
 178          "Resolving symbol outside the requested set");
 179   assert(I->second == ExecutorSymbolDef() &&
 180          "Redundantly resolving symbol Name");
 181
 182   // If this is a materialization-side-effects-only symbol then drop it,
 183   // otherwise update its map entry with its resolved address.
 184   if (Sym.getFlags().hasMaterializationSideEffectsOnly())
 185     ResolvedSymbols.erase(I);
 186   else
 187     I->second = std::move(Sym);
 188   --OutstandingSymbolsCount;
 189 }
 190
 191 void AsynchronousSymbolQuery::handleComplete(ExecutionSession &ES) {
 192   assert(OutstandingSymbolsCount == 0 &&
 193          "Symbols remain, handleComplete called prematurely");
 194
 195   class RunQueryCompleteTask : public Task {
 196   public:
 197     RunQueryCompleteTask(SymbolMap ResolvedSymbols,
 198                          SymbolsResolvedCallback NotifyComplete)
 199         : ResolvedSymbols(std::move(ResolvedSymbols)),
 200           NotifyComplete(std::move(NotifyComplete)) {}
 201     void printDescription(raw_ostream &OS) override {
 202       OS << "Execute query complete callback for " << ResolvedSymbols;
 203     }
 204     void run() override { NotifyComplete(std::move(ResolvedSymbols)); }
 205
 206   private:
 207     SymbolMap ResolvedSymbols;
 208     SymbolsResolvedCallback NotifyComplete;
 209   };
 210
 211   auto T = std::make_unique<RunQueryCompleteTask>(std::move(ResolvedSymbols),
 212                                                   std::move(NotifyComplete));
 213   NotifyComplete = SymbolsResolvedCallback();
 214   ES.dispatchTask(std::move(T));
 215 }
 216
 217 void AsynchronousSymbolQuery::handleFailed(Error Err) {
 218   assert(QueryRegistrations.empty() && ResolvedSymbols.empty() &&
 219          OutstandingSymbolsCount == 0 &&
 220          "Query should already have been abandoned");
 221   NotifyComplete(std::move(Err));
 222   NotifyComplete = SymbolsResolvedCallback();
 223 }
 224
 225 void AsynchronousSymbolQuery::addQueryDependence(JITDylib &JD,
 226                                                  SymbolStringPtr Name) {
 227   bool Added = QueryRegistrations[&JD].insert(std::move(Name)).second;
 228   (void)Added;
 229   assert(Added && "Duplicate dependence notification?");
 230 }
 231
 232 void AsynchronousSymbolQuery::removeQueryDependence(
 233     JITDylib &JD, const SymbolStringPtr &Name) {
 234   auto QRI = QueryRegistrations.find(&JD);
 235   assert(QRI != QueryRegistrations.end() &&
 236          "No dependencies registered for JD");
 237   assert(QRI->second.count(Name) && "No dependency on Name in JD");
 238   QRI->second.erase(Name);
 239   if (QRI->second.empty())
 240     QueryRegistrations.erase(QRI);
 241 }
 242
 243 void AsynchronousSymbolQuery::dropSymbol(const SymbolStringPtr &Name) {
 244   auto I = ResolvedSymbols.find(Name);
 245   assert(I != ResolvedSymbols.end() &&
 246          "Redundant removal of weakly-referenced symbol");
 247   ResolvedSymbols.erase(I);
 248   --OutstandingSymbolsCount;
 249 }
 250
 251 void AsynchronousSymbolQuery::detach() {
 252   ResolvedSymbols.clear();
 253   OutstandingSymbolsCount = 0;
 254   for (auto &KV : QueryRegistrations)
 255     KV.first->detachQueryHelper(*this, KV.second);
 256   QueryRegistrations.clear();
 257 }
 258
 259 AbsoluteSymbolsMaterializationUnit::AbsoluteSymbolsMaterializationUnit(
 260     SymbolMap Symbols)
 261     : MaterializationUnit(extractFlags(Symbols)), Symbols(std::move(Symbols)) {}
 262
 263 StringRef AbsoluteSymbolsMaterializationUnit::getName() const {
 264   return "<Absolute Symbols>";
 265 }
 266
 267 void AbsoluteSymbolsMaterializationUnit::materialize(
 268     std::unique_ptr<MaterializationResponsibility> R) {
 269   // Even though these are just absolute symbols we need to check for failure
 270   // to resolve/emit: the tracker for these symbols may have been removed while
 271   // the materialization was in flight (e.g. due to a failure in some action
 272   // triggered by the queries attached to the resolution/emission of these
 273   // symbols).
 274   if (auto Err = R->notifyResolved(Symbols)) {
 275     R->getExecutionSession().reportError(std::move(Err));
 276     R->failMaterialization();
 277     return;
 278   }
 279   if (auto Err = R->notifyEmitted()) {
 280     R->getExecutionSession().reportError(std::move(Err));
 281     R->failMaterialization();
 282     return;
 283   }
 284 }
 285
 286 void AbsoluteSymbolsMaterializationUnit::discard(const JITDylib &JD,
 287                                                  const SymbolStringPtr &Name) {
 288   assert(Symbols.count(Name) && "Symbol is not part of this MU");
 289   Symbols.erase(Name);
 290 }
 291
 292 MaterializationUnit::Interface
 293 AbsoluteSymbolsMaterializationUnit::extractFlags(const SymbolMap &Symbols) {
 294   SymbolFlagsMap Flags;
 295   for (const auto &KV : Symbols)
 296     Flags[KV.first] = KV.second.getFlags();
 297   return MaterializationUnit::Interface(std::move(Flags), nullptr);
 298 }
 299
 300 ReExportsMaterializationUnit::ReExportsMaterializationUnit(
 301     JITDylib *SourceJD, JITDylibLookupFlags SourceJDLookupFlags,
 302     SymbolAliasMap Aliases)
 303     : MaterializationUnit(extractFlags(Aliases)), SourceJD(SourceJD),
 304       SourceJDLookupFlags(SourceJDLookupFlags), Aliases(std::move(Aliases)) {}
 305
 306 StringRef ReExportsMaterializationUnit::getName() const {
 307   return "<Reexports>";
 308 }
 309
 310 void ReExportsMaterializationUnit::materialize(
 311     std::unique_ptr<MaterializationResponsibility> R) {
 312
 313   auto &ES = R->getTargetJITDylib().getExecutionSession();
 314   JITDylib &TgtJD = R->getTargetJITDylib();
 315   JITDylib &SrcJD = SourceJD ? *SourceJD : TgtJD;
 316
 317   // Find the set of requested aliases and aliasees. Return any unrequested
 318   // aliases back to the JITDylib so as to not prematurely materialize any
 319   // aliasees.
 320   auto RequestedSymbols = R->getRequestedSymbols();
 321   SymbolAliasMap RequestedAliases;
 322
 323   for (auto &Name : RequestedSymbols) {
 324     auto I = Aliases.find(Name);
 325     assert(I != Aliases.end() && "Symbol not found in aliases map?");
 326     RequestedAliases[Name] = std::move(I->second);
 327     Aliases.erase(I);
 328   }
 329
 330   LLVM_DEBUG({
 331     ES.runSessionLocked([&]() {
 332       dbgs() << "materializing reexports: target = " << TgtJD.getName()
 333              << ", source = " << SrcJD.getName() << " " << RequestedAliases
 334              << "\n";
 335     });
 336   });
 337
 338   if (!Aliases.empty()) {
 339     auto Err = SourceJD ? R->replace(reexports(*SourceJD, std::move(Aliases),
 340                                                SourceJDLookupFlags))
 341                         : R->replace(symbolAliases(std::move(Aliases)));
 342
 343     if (Err) {
 344       // FIXME: Should this be reported / treated as failure to materialize?
 345       // Or should this be treated as a sanctioned bailing-out?
 346       ES.reportError(std::move(Err));
 347       R->failMaterialization();
 348       return;
 349     }
 350   }
 351
 352   // The OnResolveInfo struct will hold the aliases and responsibility for each
 353   // query in the list.
 354   struct OnResolveInfo {
 355     OnResolveInfo(std::unique_ptr<MaterializationResponsibility> R,
 356                   SymbolAliasMap Aliases)
 357         : R(std::move(R)), Aliases(std::move(Aliases)) {}
 358
 359     std::unique_ptr<MaterializationResponsibility> R;
 360     SymbolAliasMap Aliases;
 361   };
 362
 363   // Build a list of queries to issue. In each round we build a query for the
 364   // largest set of aliases that we can resolve without encountering a chain of
 365   // aliases (e.g. Foo -> Bar, Bar -> Baz). Such a chain would deadlock as the
 366   // query would be waiting on a symbol that it itself had to resolve. Creating
 367   // a new query for each link in such a chain eliminates the possibility of
 368   // deadlock. In practice chains are likely to be rare, and this algorithm will
 369   // usually result in a single query to issue.
 370
 371   std::vector<std::pair<SymbolLookupSet, std::shared_ptr<OnResolveInfo>>>
 372       QueryInfos;
 373   while (!RequestedAliases.empty()) {
 374     SymbolNameSet ResponsibilitySymbols;
 375     SymbolLookupSet QuerySymbols;
 376     SymbolAliasMap QueryAliases;
 377
 378     // Collect as many aliases as we can without including a chain.
 379     for (auto &KV : RequestedAliases) {
 380       // Chain detected. Skip this symbol for this round.
 381       if (&SrcJD == &TgtJD && (QueryAliases.count(KV.second.Aliasee) ||
 382                                RequestedAliases.count(KV.second.Aliasee)))
 383         continue;
 384
 385       ResponsibilitySymbols.insert(KV.first);
 386       QuerySymbols.add(KV.second.Aliasee,
 387                        KV.second.AliasFlags.hasMaterializationSideEffectsOnly()
 388                            ? SymbolLookupFlags::WeaklyReferencedSymbol
 389                            : SymbolLookupFlags::RequiredSymbol);
 390       QueryAliases[KV.first] = std::move(KV.second);
 391     }
 392
 393     // Remove the aliases collected this round from the RequestedAliases map.
 394     for (auto &KV : QueryAliases)
 395       RequestedAliases.erase(KV.first);
 396
 397     assert(!QuerySymbols.empty() && "Alias cycle detected!");
 398
 399     auto NewR = R->delegate(ResponsibilitySymbols);
 400     if (!NewR) {
 401       ES.reportError(NewR.takeError());
 402       R->failMaterialization();
 403       return;
 404     }
 405
 406     auto QueryInfo = std::make_shared<OnResolveInfo>(std::move(*NewR),
 407                                                      std::move(QueryAliases));
 408     QueryInfos.push_back(
 409         make_pair(std::move(QuerySymbols), std::move(QueryInfo)));
 410   }
 411
 412   // Issue the queries.
 413   while (!QueryInfos.empty()) {
 414     auto QuerySymbols = std::move(QueryInfos.back().first);
 415     auto QueryInfo = std::move(QueryInfos.back().second);
 416
 417     QueryInfos.pop_back();
 418
 419     auto RegisterDependencies = [QueryInfo,
 420                                  &SrcJD](const SymbolDependenceMap &Deps) {
 421       // If there were no materializing symbols, just bail out.
 422       if (Deps.empty())
 423         return;
 424
 425       // Otherwise the only deps should be on SrcJD.
 426       assert(Deps.size() == 1 && Deps.count(&SrcJD) &&
 427              "Unexpected dependencies for reexports");
 428
 429       auto &SrcJDDeps = Deps.find(&SrcJD)->second;
 430       SymbolDependenceMap PerAliasDepsMap;
 431       auto &PerAliasDeps = PerAliasDepsMap[&SrcJD];
 432
 433       for (auto &KV : QueryInfo->Aliases)
 434         if (SrcJDDeps.count(KV.second.Aliasee)) {
 435           PerAliasDeps = {KV.second.Aliasee};
 436           QueryInfo->R->addDependencies(KV.first, PerAliasDepsMap);
 437         }
 438     };
 439
 440     auto OnComplete = [QueryInfo](Expected<SymbolMap> Result) {
 441       auto &ES = QueryInfo->R->getTargetJITDylib().getExecutionSession();
 442       if (Result) {
 443         SymbolMap ResolutionMap;
 444         for (auto &KV : QueryInfo->Aliases) {
 445           assert((KV.second.AliasFlags.hasMaterializationSideEffectsOnly() ||
 446                   Result->count(KV.second.Aliasee)) &&
 447                  "Result map missing entry?");
 448           // Don't try to resolve materialization-side-effects-only symbols.
 449           if (KV.second.AliasFlags.hasMaterializationSideEffectsOnly())
 450             continue;
 451
 452           ResolutionMap[KV.first] = {(*Result)[KV.second.Aliasee].getAddress(),
 453                                      KV.second.AliasFlags};
 454         }
 455         if (auto Err = QueryInfo->R->notifyResolved(ResolutionMap)) {
 456           ES.reportError(std::move(Err));
 457           QueryInfo->R->failMaterialization();
 458           return;
 459         }
 460         if (auto Err = QueryInfo->R->notifyEmitted()) {
 461           ES.reportError(std::move(Err));
 462           QueryInfo->R->failMaterialization();
 463           return;
 464         }
 465       } else {
 466         ES.reportError(Result.takeError());
 467         QueryInfo->R->failMaterialization();
 468       }
 469     };
 470
 471     ES.lookup(LookupKind::Static,
 472               JITDylibSearchOrder({{&SrcJD, SourceJDLookupFlags}}),
 473               QuerySymbols, SymbolState::Resolved, std::move(OnComplete),
 474               std::move(RegisterDependencies));
 475   }
 476 }
 477
 478 void ReExportsMaterializationUnit::discard(const JITDylib &JD,
 479                                            const SymbolStringPtr &Name) {
 480   assert(Aliases.count(Name) &&
 481          "Symbol not covered by this MaterializationUnit");
 482   Aliases.erase(Name);
 483 }
 484
 485 MaterializationUnit::Interface
 486 ReExportsMaterializationUnit::extractFlags(const SymbolAliasMap &Aliases) {
 487   SymbolFlagsMap SymbolFlags;
 488   for (auto &KV : Aliases)
 489     SymbolFlags[KV.first] = KV.second.AliasFlags;
 490
 491   return MaterializationUnit::Interface(std::move(SymbolFlags), nullptr);
 492 }
 493
 494 Expected<SymbolAliasMap> buildSimpleReexportsAliasMap(JITDylib &SourceJD,
 495                                                       SymbolNameSet Symbols) {
 496   SymbolLookupSet LookupSet(Symbols);
 497   auto Flags = SourceJD.getExecutionSession().lookupFlags(
 498       LookupKind::Static, {{&SourceJD, JITDylibLookupFlags::MatchAllSymbols}},
 499       SymbolLookupSet(std::move(Symbols)));
 500
 501   if (!Flags)
 502     return Flags.takeError();
 503
 504   SymbolAliasMap Result;
 505   for (auto &Name : Symbols) {
 506     assert(Flags->count(Name) && "Missing entry in flags map");
 507     Result[Name] = SymbolAliasMapEntry(Name, (*Flags)[Name]);
 508   }
 509
 510   return Result;
 511 }
 512
 513 class InProgressLookupState {
 514 public:
 515   // FIXME: Reduce the number of SymbolStringPtrs here. See
 516   //        https://github.com/llvm/llvm-project/issues/55576.
 517
 518   InProgressLookupState(LookupKind K, JITDylibSearchOrder SearchOrder,
 519                         SymbolLookupSet LookupSet, SymbolState RequiredState)
 520       : K(K), SearchOrder(std::move(SearchOrder)),
 521         LookupSet(std::move(LookupSet)), RequiredState(RequiredState) {
 522     DefGeneratorCandidates = this->LookupSet;
 523   }
 524   virtual ~InProgressLookupState() = default;
 525   virtual void complete(std::unique_ptr<InProgressLookupState> IPLS) = 0;
 526   virtual void fail(Error Err) = 0;
 527
 528   LookupKind K;
 529   JITDylibSearchOrder SearchOrder;
 530   SymbolLookupSet LookupSet;
 531   SymbolState RequiredState;
 532
 533   size_t CurSearchOrderIndex = 0;
 534   bool NewJITDylib = true;
 535   SymbolLookupSet DefGeneratorCandidates;
 536   SymbolLookupSet DefGeneratorNonCandidates;
 537
 538   enum {
 539     NotInGenerator,      // Not currently using a generator.
 540     ResumedForGenerator, // Resumed after being auto-suspended before generator.
 541     InGenerator          // Currently using generator.
 542   } GenState = NotInGenerator;
 543   std::vector<std::weak_ptr<DefinitionGenerator>> CurDefGeneratorStack;
 544 };
 545
 546 class InProgressLookupFlagsState : public InProgressLookupState {
 547 public:
 548   InProgressLookupFlagsState(
 549       LookupKind K, JITDylibSearchOrder SearchOrder, SymbolLookupSet LookupSet,
 550       unique_function<void(Expected<SymbolFlagsMap>)> OnComplete)
 551       : InProgressLookupState(K, std::move(SearchOrder), std::move(LookupSet),
 552                               SymbolState::NeverSearched),
 553         OnComplete(std::move(OnComplete)) {}
 554
 555   void complete(std::unique_ptr<InProgressLookupState> IPLS) override {
 556     auto &ES = SearchOrder.front().first->getExecutionSession();
 557     ES.OL_completeLookupFlags(std::move(IPLS), std::move(OnComplete));
 558   }
 559
 560   void fail(Error Err) override { OnComplete(std::move(Err)); }
 561
 562 private:
 563   unique_function<void(Expected<SymbolFlagsMap>)> OnComplete;
 564 };
 565
 566 class InProgressFullLookupState : public InProgressLookupState {
 567 public:
 568   InProgressFullLookupState(LookupKind K, JITDylibSearchOrder SearchOrder,
 569                             SymbolLookupSet LookupSet,
 570                             SymbolState RequiredState,
 571                             std::shared_ptr<AsynchronousSymbolQuery> Q,
 572                             RegisterDependenciesFunction RegisterDependencies)
 573       : InProgressLookupState(K, std::move(SearchOrder), std::move(LookupSet),
 574                               RequiredState),
 575         Q(std::move(Q)), RegisterDependencies(std::move(RegisterDependencies)) {
 576   }
 577
 578   void complete(std::unique_ptr<InProgressLookupState> IPLS) override {
 579     auto &ES = SearchOrder.front().first->getExecutionSession();
 580     ES.OL_completeLookup(std::move(IPLS), std::move(Q),
 581                          std::move(RegisterDependencies));
 582   }
 583
 584   void fail(Error Err) override {
 585     Q->detach();
 586     Q->handleFailed(std::move(Err));
 587   }
 588
 589 private:
 590   std::shared_ptr<AsynchronousSymbolQuery> Q;
 591   RegisterDependenciesFunction RegisterDependencies;
 592 };
 593
 594 ReexportsGenerator::ReexportsGenerator(JITDylib &SourceJD,
 595                                        JITDylibLookupFlags SourceJDLookupFlags,
 596                                        SymbolPredicate Allow)
 597     : SourceJD(SourceJD), SourceJDLookupFlags(SourceJDLookupFlags),
 598       Allow(std::move(Allow)) {}
 599
 600 Error ReexportsGenerator::tryToGenerate(LookupState &LS, LookupKind K,
 601                                         JITDylib &JD,
 602                                         JITDylibLookupFlags JDLookupFlags,
 603                                         const SymbolLookupSet &LookupSet) {
 604   assert(&JD != &SourceJD && "Cannot re-export from the same dylib");
 605
 606   // Use lookupFlags to find the subset of symbols that match our lookup.
 607   auto Flags = JD.getExecutionSession().lookupFlags(
 608       K, {{&SourceJD, JDLookupFlags}}, LookupSet);
 609   if (!Flags)
 610     return Flags.takeError();
 611
 612   // Create an alias map.
 613   orc::SymbolAliasMap AliasMap;
 614   for (auto &KV : *Flags)
 615     if (!Allow || Allow(KV.first))
 616       AliasMap[KV.first] = SymbolAliasMapEntry(KV.first, KV.second);
 617
 618   if (AliasMap.empty())
 619     return Error::success();
 620
 621   // Define the re-exports.
 622   return JD.define(reexports(SourceJD, AliasMap, SourceJDLookupFlags));
 623 }
 624
 625 LookupState::LookupState(std::unique_ptr<InProgressLookupState> IPLS)
 626     : IPLS(std::move(IPLS)) {}
 627
 628 void LookupState::reset(InProgressLookupState *IPLS) { this->IPLS.reset(IPLS); }
 629
 630 LookupState::LookupState() = default;
 631 LookupState::LookupState(LookupState &&) = default;
 632 LookupState &LookupState::operator=(LookupState &&) = default;
 633 LookupState::~LookupState() = default;
 634
 635 void LookupState::continueLookup(Error Err) {
 636   assert(IPLS && "Cannot call continueLookup on empty LookupState");
 637   auto &ES = IPLS->SearchOrder.begin()->first->getExecutionSession();
 638   ES.OL_applyQueryPhase1(std::move(IPLS), std::move(Err));
 639 }
 640
 641 DefinitionGenerator::~DefinitionGenerator() {
 642   std::deque<LookupState> LookupsToFail;
 643   {
 644     std::lock_guard<std::mutex> Lock(M);
 645     std::swap(PendingLookups, LookupsToFail);
 646     InUse = false;
 647   }
 648
 649   for (auto &LS : LookupsToFail)
 650     LS.continueLookup(make_error<StringError>(
 651         "Query waiting on DefinitionGenerator that was destroyed",
 652         inconvertibleErrorCode()));
 653 }
 654
 655 JITDylib::~JITDylib() {
 656   LLVM_DEBUG(dbgs() << "Destroying JITDylib " << getName() << "\n");
 657 }
 658
 659 Error JITDylib::clear() {
 660   std::vector<ResourceTrackerSP> TrackersToRemove;
 661   ES.runSessionLocked([&]() {
 662     assert(State != Closed && "JD is defunct");
 663     for (auto &KV : TrackerSymbols)
 664       TrackersToRemove.push_back(KV.first);
 665     TrackersToRemove.push_back(getDefaultResourceTracker());
 666   });
 667
 668   Error Err = Error::success();
 669   for (auto &RT : TrackersToRemove)
 670     Err = joinErrors(std::move(Err), RT->remove());
 671   return Err;
 672 }
 673
 674 ResourceTrackerSP JITDylib::getDefaultResourceTracker() {
 675   return ES.runSessionLocked([this] {
 676     assert(State != Closed && "JD is defunct");
 677     if (!DefaultTracker)
 678       DefaultTracker = new ResourceTracker(this);
 679     return DefaultTracker;
 680   });
 681 }
 682
 683 ResourceTrackerSP JITDylib::createResourceTracker() {
 684   return ES.runSessionLocked([this] {
 685     assert(State == Open && "JD is defunct");
 686     ResourceTrackerSP RT = new ResourceTracker(this);
 687     return RT;
 688   });
 689 }
 690
 691 void JITDylib::removeGenerator(DefinitionGenerator &G) {
 692   // DefGenerator moved into TmpDG to ensure that it's destroyed outside the
 693   // session lock (since it may have to send errors to pending queries).
 694   std::shared_ptr<DefinitionGenerator> TmpDG;
 695
 696   ES.runSessionLocked([&] {
 697     assert(State == Open && "JD is defunct");
 698     auto I = llvm::find_if(DefGenerators,
 699                            [&](const std::shared_ptr<DefinitionGenerator> &H) {
 700                              return H.get() == &G;
 701                            });
 702     assert(I != DefGenerators.end() && "Generator not found");
 703     TmpDG = std::move(*I);
 704     DefGenerators.erase(I);
 705   });
 706 }
 707
 708 Expected<SymbolFlagsMap>
 709 JITDylib::defineMaterializing(MaterializationResponsibility &FromMR,
 710                               SymbolFlagsMap SymbolFlags) {
 711
 712   return ES.runSessionLocked([&]() -> Expected<SymbolFlagsMap> {
 713     if (FromMR.RT->isDefunct())
 714       return make_error<ResourceTrackerDefunct>(FromMR.RT);
 715
 716     std::vector<NonOwningSymbolStringPtr> AddedSyms;
 717     std::vector<NonOwningSymbolStringPtr> RejectedWeakDefs;
 718
 719     for (auto SFItr = SymbolFlags.begin(), SFEnd = SymbolFlags.end();
 720          SFItr != SFEnd; ++SFItr) {
 721
 722       auto &Name = SFItr->first;
 723       auto &Flags = SFItr->second;
 724
 725       auto EntryItr = Symbols.find(Name);
 726
 727       // If the entry already exists...
 728       if (EntryItr != Symbols.end()) {
 729
 730         // If this is a strong definition then error out.
 731         if (!Flags.isWeak()) {
 732           // Remove any symbols already added.
 733           for (auto &S : AddedSyms)
 734             Symbols.erase(Symbols.find_as(S));
 735
 736           // FIXME: Return all duplicates.
 737           return make_error<DuplicateDefinition>(std::string(*Name));
 738         }
 739
 740         // Otherwise just make a note to discard this symbol after the loop.
 741         RejectedWeakDefs.push_back(NonOwningSymbolStringPtr(Name));
 742         continue;
 743       } else
 744         EntryItr =
 745           Symbols.insert(std::make_pair(Name, SymbolTableEntry(Flags))).first;
 746
 747       AddedSyms.push_back(NonOwningSymbolStringPtr(Name));
 748       EntryItr->second.setState(SymbolState::Materializing);
 749     }
 750
 751     // Remove any rejected weak definitions from the SymbolFlags map.
 752     while (!RejectedWeakDefs.empty()) {
 753       SymbolFlags.erase(SymbolFlags.find_as(RejectedWeakDefs.back()));
 754       RejectedWeakDefs.pop_back();
 755     }
 756
 757     return SymbolFlags;
 758   });
 759 }
 760
 761 Error JITDylib::replace(MaterializationResponsibility &FromMR,
 762                         std::unique_ptr<MaterializationUnit> MU) {
 763   assert(MU != nullptr && "Can not replace with a null MaterializationUnit");
 764   std::unique_ptr<MaterializationUnit> MustRunMU;
 765   std::unique_ptr<MaterializationResponsibility> MustRunMR;
 766
 767   auto Err =
 768       ES.runSessionLocked([&, this]() -> Error {
 769         if (FromMR.RT->isDefunct())
 770           return make_error<ResourceTrackerDefunct>(std::move(FromMR.RT));
 771
 772 #ifndef NDEBUG
 773         for (auto &KV : MU->getSymbols()) {
 774           auto SymI = Symbols.find(KV.first);
 775           assert(SymI != Symbols.end() && "Replacing unknown symbol");
 776           assert(SymI->second.getState() == SymbolState::Materializing &&
 777                  "Can not replace a symbol that ha is not materializing");
 778           assert(!SymI->second.hasMaterializerAttached() &&
 779                  "Symbol should not have materializer attached already");
 780           assert(UnmaterializedInfos.count(KV.first) == 0 &&
 781                  "Symbol being replaced should have no UnmaterializedInfo");
 782         }
 783 #endif // NDEBUG
 784
 785         // If the tracker is defunct we need to bail out immediately.
 786
 787         // If any symbol has pending queries against it then we need to
 788         // materialize MU immediately.
 789         for (auto &KV : MU->getSymbols()) {
 790           auto MII = MaterializingInfos.find(KV.first);
 791           if (MII != MaterializingInfos.end()) {
 792             if (MII->second.hasQueriesPending()) {
 793               MustRunMR = ES.createMaterializationResponsibility(
 794                   *FromMR.RT, std::move(MU->SymbolFlags),
 795                   std::move(MU->InitSymbol));
 796               MustRunMU = std::move(MU);
 797               return Error::success();
 798             }
 799           }
 800         }
 801
 802         // Otherwise, make MU responsible for all the symbols.
 803         auto UMI = std::make_shared<UnmaterializedInfo>(std::move(MU),
 804                                                         FromMR.RT.get());
 805         for (auto &KV : UMI->MU->getSymbols()) {
 806           auto SymI = Symbols.find(KV.first);
 807           assert(SymI->second.getState() == SymbolState::Materializing &&
 808                  "Can not replace a symbol that is not materializing");
 809           assert(!SymI->second.hasMaterializerAttached() &&
 810                  "Can not replace a symbol that has a materializer attached");
 811           assert(UnmaterializedInfos.count(KV.first) == 0 &&
 812                  "Unexpected materializer entry in map");
 813           SymI->second.setAddress(SymI->second.getAddress());
 814           SymI->second.setMaterializerAttached(true);
 815
 816           auto &UMIEntry = UnmaterializedInfos[KV.first];
 817           assert((!UMIEntry || !UMIEntry->MU) &&
 818                  "Replacing symbol with materializer still attached");
 819           UMIEntry = UMI;
 820         }
 821
 822         return Error::success();
 823       });
 824
 825   if (Err)
 826     return Err;
 827
 828   if (MustRunMU) {
 829     assert(MustRunMR && "MustRunMU set implies MustRunMR set");
 830     ES.dispatchTask(std::make_unique<MaterializationTask>(
 831         std::move(MustRunMU), std::move(MustRunMR)));
 832   } else {
 833     assert(!MustRunMR && "MustRunMU unset implies MustRunMR unset");
 834   }
 835
 836   return Error::success();
 837 }
 838
 839 Expected<std::unique_ptr<MaterializationResponsibility>>
 840 JITDylib::delegate(MaterializationResponsibility &FromMR,
 841                    SymbolFlagsMap SymbolFlags, SymbolStringPtr InitSymbol) {
 842
 843   return ES.runSessionLocked(
 844       [&]() -> Expected<std::unique_ptr<MaterializationResponsibility>> {
 845         if (FromMR.RT->isDefunct())
 846           return make_error<ResourceTrackerDefunct>(std::move(FromMR.RT));
 847
 848         return ES.createMaterializationResponsibility(
 849             *FromMR.RT, std::move(SymbolFlags), std::move(InitSymbol));
 850       });
 851 }
 852
 853 SymbolNameSet
 854 JITDylib::getRequestedSymbols(const SymbolFlagsMap &SymbolFlags) const {
 855   return ES.runSessionLocked([&]() {
 856     SymbolNameSet RequestedSymbols;
 857
 858     for (auto &KV : SymbolFlags) {
 859       assert(Symbols.count(KV.first) && "JITDylib does not cover this symbol?");
 860       assert(Symbols.find(KV.first)->second.getState() !=
 861                  SymbolState::NeverSearched &&
 862              Symbols.find(KV.first)->second.getState() != SymbolState::Ready &&
 863              "getRequestedSymbols can only be called for symbols that have "
 864              "started materializing");
 865       auto I = MaterializingInfos.find(KV.first);
 866       if (I == MaterializingInfos.end())
 867         continue;
 868
 869       if (I->second.hasQueriesPending())
 870         RequestedSymbols.insert(KV.first);
 871     }
 872
 873     return RequestedSymbols;
 874   });
 875 }
 876
 877 void JITDylib::addDependencies(const SymbolStringPtr &Name,
 878                                const SymbolDependenceMap &Dependencies) {
 879   ES.runSessionLocked([&]() {
 880     assert(Symbols.count(Name) && "Name not in symbol table");
 881     assert(Symbols[Name].getState() < SymbolState::Emitted &&
 882            "Can not add dependencies for a symbol that is not materializing");
 883
 884     LLVM_DEBUG({
 885       dbgs() << "In " << getName() << " adding dependencies for " << *Name
 886              << ": " << Dependencies << "\n";
 887     });
 888
 889     // If Name is already in an error state then just bail out.
 890     if (Symbols[Name].getFlags().hasError())
 891       return;
 892
 893     auto &MI = MaterializingInfos[Name];
 894     assert(Symbols[Name].getState() != SymbolState::Emitted &&
 895            "Can not add dependencies to an emitted symbol");
 896
 897     bool DependsOnSymbolInErrorState = false;
 898
 899     // Register dependencies, record whether any depenendency is in the error
 900     // state.
 901     for (auto &KV : Dependencies) {
 902       assert(KV.first && "Null JITDylib in dependency?");
 903       auto &OtherJITDylib = *KV.first;
 904       auto &DepsOnOtherJITDylib = MI.UnemittedDependencies[&OtherJITDylib];
 905
 906       for (auto &OtherSymbol : KV.second) {
 907
 908         // Check the sym entry for the dependency.
 909         auto OtherSymI = OtherJITDylib.Symbols.find(OtherSymbol);
 910
 911         // Assert that this symbol exists and has not reached the ready state
 912         // already.
 913         assert(OtherSymI != OtherJITDylib.Symbols.end() &&
 914                "Dependency on unknown symbol");
 915
 916         auto &OtherSymEntry = OtherSymI->second;
 917
 918         // If the other symbol is already in the Ready state then there's no
 919         // dependency to add.
 920         if (OtherSymEntry.getState() == SymbolState::Ready)
 921           continue;
 922
 923         // If the dependency is in an error state then note this and continue,
 924         // we will move this symbol to the error state below.
 925         if (OtherSymEntry.getFlags().hasError()) {
 926           DependsOnSymbolInErrorState = true;
 927           continue;
 928         }
 929
 930         // If the dependency was not in the error state then add it to
 931         // our list of dependencies.
 932         auto &OtherMI = OtherJITDylib.MaterializingInfos[OtherSymbol];
 933
 934         if (OtherSymEntry.getState() == SymbolState::Emitted)
 935           transferEmittedNodeDependencies(MI, Name, OtherMI);
 936         else if (&OtherJITDylib != this || OtherSymbol != Name) {
 937           OtherMI.Dependants[this].insert(Name);
 938           DepsOnOtherJITDylib.insert(OtherSymbol);
 939         }
 940       }
 941
 942       if (DepsOnOtherJITDylib.empty())
 943         MI.UnemittedDependencies.erase(&OtherJITDylib);
 944     }
 945
 946     // If this symbol dependended on any symbols in the error state then move
 947     // this symbol to the error state too.
 948     if (DependsOnSymbolInErrorState)
 949       Symbols[Name].setFlags(Symbols[Name].getFlags() |
 950                              JITSymbolFlags::HasError);
 951   });
 952 }
 953
 954 Error JITDylib::resolve(MaterializationResponsibility &MR,
 955                         const SymbolMap &Resolved) {
 956   AsynchronousSymbolQuerySet CompletedQueries;
 957
 958   if (auto Err = ES.runSessionLocked([&, this]() -> Error {
 959         if (MR.RT->isDefunct())
 960           return make_error<ResourceTrackerDefunct>(MR.RT);
 961
 962         if (State != Open)
 963           return make_error<StringError>("JITDylib " + getName() +
 964                                              " is defunct",
 965                                          inconvertibleErrorCode());
 966
 967         struct WorklistEntry {
 968           SymbolTable::iterator SymI;
 969           ExecutorSymbolDef ResolvedSym;
 970         };
 971
 972         SymbolNameSet SymbolsInErrorState;
 973         std::vector<WorklistEntry> Worklist;
 974         Worklist.reserve(Resolved.size());
 975
 976         // Build worklist and check for any symbols in the error state.
 977         for (const auto &KV : Resolved) {
 978
 979           assert(!KV.second.getFlags().hasError() &&
 980                  "Resolution result can not have error flag set");
 981
 982           auto SymI = Symbols.find(KV.first);
 983
 984           assert(SymI != Symbols.end() && "Symbol not found");
 985           assert(!SymI->second.hasMaterializerAttached() &&
 986                  "Resolving symbol with materializer attached?");
 987           assert(SymI->second.getState() == SymbolState::Materializing &&
 988                  "Symbol should be materializing");
 989           assert(SymI->second.getAddress() == ExecutorAddr() &&
 990                  "Symbol has already been resolved");
 991
 992           if (SymI->second.getFlags().hasError())
 993             SymbolsInErrorState.insert(KV.first);
 994           else {
 995             auto Flags = KV.second.getFlags();
 996             Flags &= ~JITSymbolFlags::Common;
 997             assert(Flags ==
 998                        (SymI->second.getFlags() & ~JITSymbolFlags::Common) &&
 999                    "Resolved flags should match the declared flags");
1000
1001             Worklist.push_back({SymI, {KV.second.getAddress(), Flags}});
1002           }
1003         }
1004
1005         // If any symbols were in the error state then bail out.
1006         if (!SymbolsInErrorState.empty()) {
1007           auto FailedSymbolsDepMap = std::make_shared<SymbolDependenceMap>();
1008           (*FailedSymbolsDepMap)[this] = std::move(SymbolsInErrorState);
1009           return make_error<FailedToMaterialize>(
1010               getExecutionSession().getSymbolStringPool(),
1011               std::move(FailedSymbolsDepMap));
1012         }
1013
1014         while (!Worklist.empty()) {
1015           auto SymI = Worklist.back().SymI;
1016           auto ResolvedSym = Worklist.back().ResolvedSym;
1017           Worklist.pop_back();
1018
1019           auto &Name = SymI->first;
1020
1021           // Resolved symbols can not be weak: discard the weak flag.
1022           JITSymbolFlags ResolvedFlags = ResolvedSym.getFlags();
1023           SymI->second.setAddress(ResolvedSym.getAddress());
1024           SymI->second.setFlags(ResolvedFlags);
1025           SymI->second.setState(SymbolState::Resolved);
1026
1027           auto MII = MaterializingInfos.find(Name);
1028           if (MII == MaterializingInfos.end())
1029             continue;
1030
1031           auto &MI = MII->second;
1032           for (auto &Q : MI.takeQueriesMeeting(SymbolState::Resolved)) {
1033             Q->notifySymbolMetRequiredState(Name, ResolvedSym);
1034             Q->removeQueryDependence(*this, Name);
1035             if (Q->isComplete())
1036               CompletedQueries.insert(std::move(Q));
1037           }
1038         }
1039
1040         return Error::success();
1041       }))
1042     return Err;
1043
1044   // Otherwise notify all the completed queries.
1045   for (auto &Q : CompletedQueries) {
1046     assert(Q->isComplete() && "Q not completed");
1047     Q->handleComplete(ES);
1048   }
1049
1050   return Error::success();
1051 }
1052
1053 Error JITDylib::emit(MaterializationResponsibility &MR,
1054                      const SymbolFlagsMap &Emitted) {
1055   AsynchronousSymbolQuerySet CompletedQueries;
1056   DenseMap<JITDylib *, SymbolNameVector> ReadySymbols;
1057
1058   if (auto Err = ES.runSessionLocked([&, this]() -> Error {
1059         if (MR.RT->isDefunct())
1060           return make_error<ResourceTrackerDefunct>(MR.RT);
1061
1062         if (State != Open)
1063           return make_error<StringError>("JITDylib " + getName() +
1064                                              " is defunct",
1065                                          inconvertibleErrorCode());
1066
1067         SymbolNameSet SymbolsInErrorState;
1068         std::vector<SymbolTable::iterator> Worklist;
1069
1070         // Scan to build worklist, record any symbols in the erorr state.
1071         for (const auto &KV : Emitted) {
1072           auto &Name = KV.first;
1073
1074           auto SymI = Symbols.find(Name);
1075           assert(SymI != Symbols.end() && "No symbol table entry for Name");
1076
1077           if (SymI->second.getFlags().hasError())
1078             SymbolsInErrorState.insert(Name);
1079           else
1080             Worklist.push_back(SymI);
1081         }
1082
1083         // If any symbols were in the error state then bail out.
1084         if (!SymbolsInErrorState.empty()) {
1085           auto FailedSymbolsDepMap = std::make_shared<SymbolDependenceMap>();
1086           (*FailedSymbolsDepMap)[this] = std::move(SymbolsInErrorState);
1087           return make_error<FailedToMaterialize>(
1088               getExecutionSession().getSymbolStringPool(),
1089               std::move(FailedSymbolsDepMap));
1090         }
1091
1092         // Otherwise update dependencies and move to the emitted state.
1093         while (!Worklist.empty()) {
1094           auto SymI = Worklist.back();
1095           Worklist.pop_back();
1096
1097           auto &Name = SymI->first;
1098           auto &SymEntry = SymI->second;
1099
1100           // Move symbol to the emitted state.
1101           assert(((SymEntry.getFlags().hasMaterializationSideEffectsOnly() &&
1102                    SymEntry.getState() == SymbolState::Materializing) ||
1103                   SymEntry.getState() == SymbolState::Resolved) &&
1104                  "Emitting from state other than Resolved");
1105           SymEntry.setState(SymbolState::Emitted);
1106
1107           auto MII = MaterializingInfos.find(Name);
1108
1109           // If this symbol has no MaterializingInfo then it's trivially ready.
1110           // Update its state and continue.
1111           if (MII == MaterializingInfos.end()) {
1112             SymEntry.setState(SymbolState::Ready);
1113             continue;
1114           }
1115
1116           auto &MI = MII->second;
1117
1118           // For each dependant, transfer this node's emitted dependencies to
1119           // it. If the dependant node is ready (i.e. has no unemitted
1120           // dependencies) then notify any pending queries.
1121           for (auto &KV : MI.Dependants) {
1122             auto &DependantJD = *KV.first;
1123             auto &DependantJDReadySymbols = ReadySymbols[&DependantJD];
1124             for (auto &DependantName : KV.second) {
1125               auto DependantMII =
1126                   DependantJD.MaterializingInfos.find(DependantName);
1127               assert(DependantMII != DependantJD.MaterializingInfos.end() &&
1128                      "Dependant should have MaterializingInfo");
1129
1130               auto &DependantMI = DependantMII->second;
1131
1132               // Remove the dependant's dependency on this node.
1133               assert(DependantMI.UnemittedDependencies.count(this) &&
1134                      "Dependant does not have an unemitted dependencies record "
1135                      "for "
1136                      "this JITDylib");
1137               assert(DependantMI.UnemittedDependencies[this].count(Name) &&
1138                      "Dependant does not count this symbol as a dependency?");
1139
1140               DependantMI.UnemittedDependencies[this].erase(Name);
1141               if (DependantMI.UnemittedDependencies[this].empty())
1142                 DependantMI.UnemittedDependencies.erase(this);
1143
1144               // Transfer unemitted dependencies from this node to the
1145               // dependant.
1146               DependantJD.transferEmittedNodeDependencies(DependantMI,
1147                                                           DependantName, MI);
1148
1149               auto DependantSymI = DependantJD.Symbols.find(DependantName);
1150               assert(DependantSymI != DependantJD.Symbols.end() &&
1151                      "Dependant has no entry in the Symbols table");
1152               auto &DependantSymEntry = DependantSymI->second;
1153
1154               // If the dependant is emitted and this node was the last of its
1155               // unemitted dependencies then the dependant node is now ready, so
1156               // notify any pending queries on the dependant node.
1157               if (DependantSymEntry.getState() == SymbolState::Emitted &&
1158                   DependantMI.UnemittedDependencies.empty()) {
1159                 assert(DependantMI.Dependants.empty() &&
1160                        "Dependants should be empty by now");
1161
1162                 // Since this dependant is now ready, we erase its
1163                 // MaterializingInfo and update its materializing state.
1164                 DependantSymEntry.setState(SymbolState::Ready);
1165                 DependantJDReadySymbols.push_back(DependantName);
1166
1167                 for (auto &Q :
1168                      DependantMI.takeQueriesMeeting(SymbolState::Ready)) {
1169                   Q->notifySymbolMetRequiredState(
1170                       DependantName, DependantSymI->second.getSymbol());
1171                   if (Q->isComplete())
1172                     CompletedQueries.insert(Q);
1173                   Q->removeQueryDependence(DependantJD, DependantName);
1174                 }
1175                 DependantJD.MaterializingInfos.erase(DependantMII);
1176               }
1177             }
1178           }
1179
1180           auto &ThisJDReadySymbols = ReadySymbols[this];
1181           MI.Dependants.clear();
1182           if (MI.UnemittedDependencies.empty()) {
1183             SymI->second.setState(SymbolState::Ready);
1184             ThisJDReadySymbols.push_back(Name);
1185             for (auto &Q : MI.takeQueriesMeeting(SymbolState::Ready)) {
1186               Q->notifySymbolMetRequiredState(Name, SymI->second.getSymbol());
1187               if (Q->isComplete())
1188                 CompletedQueries.insert(Q);
1189               Q->removeQueryDependence(*this, Name);
1190             }
1191             MaterializingInfos.erase(MII);
1192           }
1193         }
1194
1195         return Error::success();
1196       }))
1197     return Err;
1198
1199   // Otherwise notify all the completed queries.
1200   for (auto &Q : CompletedQueries) {
1201     assert(Q->isComplete() && "Q is not complete");
1202     Q->handleComplete(ES);
1203   }
1204
1205   return Error::success();
1206 }
1207
1208 void JITDylib::unlinkMaterializationResponsibility(
1209     MaterializationResponsibility &MR) {
1210   ES.runSessionLocked([&]() {
1211     auto I = TrackerMRs.find(MR.RT.get());
1212     assert(I != TrackerMRs.end() && "No MRs in TrackerMRs list for RT");
1213     assert(I->second.count(&MR) && "MR not in TrackerMRs list for RT");
1214     I->second.erase(&MR);
1215     if (I->second.empty())
1216       TrackerMRs.erase(MR.RT.get());
1217   });
1218 }
1219
1220 std::pair<JITDylib::AsynchronousSymbolQuerySet,
1221           std::shared_ptr<SymbolDependenceMap>>
1222 JITDylib::failSymbols(FailedSymbolsWorklist Worklist) {
1223   AsynchronousSymbolQuerySet FailedQueries;
1224   auto FailedSymbolsMap = std::make_shared<SymbolDependenceMap>();
1225
1226   while (!Worklist.empty()) {
1227     assert(Worklist.back().first && "Failed JITDylib can not be null");
1228     auto &JD = *Worklist.back().first;
1229     auto Name = std::move(Worklist.back().second);
1230     Worklist.pop_back();
1231
1232     (*FailedSymbolsMap)[&JD].insert(Name);
1233
1234     // Look up the symbol to fail.
1235     auto SymI = JD.Symbols.find(Name);
1236
1237     // It's possible that this symbol has already been removed, e.g. if a
1238     // materialization failure happens concurrently with a ResourceTracker or
1239     // JITDylib removal. In that case we can safely skip this symbol and
1240     // continue.
1241     if (SymI == JD.Symbols.end())
1242       continue;
1243     auto &Sym = SymI->second;
1244
1245     // Move the symbol into the error state.
1246     // Note that this may be redundant: The symbol might already have been
1247     // moved to this state in response to the failure of a dependence.
1248     Sym.setFlags(Sym.getFlags() | JITSymbolFlags::HasError);
1249
1250     // FIXME: Come up with a sane mapping of state to
1251     // presence-of-MaterializingInfo so that we can assert presence / absence
1252     // here, rather than testing it.
1253     auto MII = JD.MaterializingInfos.find(Name);
1254
1255     if (MII == JD.MaterializingInfos.end())
1256       continue;
1257
1258     auto &MI = MII->second;
1259
1260     // Move all dependants to the error state and disconnect from them.
1261     for (auto &KV : MI.Dependants) {
1262       auto &DependantJD = *KV.first;
1263       for (auto &DependantName : KV.second) {
1264         assert(DependantJD.Symbols.count(DependantName) &&
1265                "No symbol table entry for DependantName");
1266         auto &DependantSym = DependantJD.Symbols[DependantName];
1267         DependantSym.setFlags(DependantSym.getFlags() |
1268                               JITSymbolFlags::HasError);
1269
1270         assert(DependantJD.MaterializingInfos.count(DependantName) &&
1271                "No MaterializingInfo for dependant");
1272         auto &DependantMI = DependantJD.MaterializingInfos[DependantName];
1273
1274         auto UnemittedDepI = DependantMI.UnemittedDependencies.find(&JD);
1275         assert(UnemittedDepI != DependantMI.UnemittedDependencies.end() &&
1276                "No UnemittedDependencies entry for this JITDylib");
1277         assert(UnemittedDepI->second.count(Name) &&
1278                "No UnemittedDependencies entry for this symbol");
1279         UnemittedDepI->second.erase(Name);
1280         if (UnemittedDepI->second.empty())
1281           DependantMI.UnemittedDependencies.erase(UnemittedDepI);
1282
1283         // If this symbol is already in the emitted state then we need to
1284         // take responsibility for failing its queries, so add it to the
1285         // worklist.
1286         if (DependantSym.getState() == SymbolState::Emitted) {
1287           assert(DependantMI.Dependants.empty() &&
1288                  "Emitted symbol should not have dependants");
1289           Worklist.push_back(std::make_pair(&DependantJD, DependantName));
1290         }
1291       }
1292     }
1293     MI.Dependants.clear();
1294
1295     // Disconnect from all unemitted depenencies.
1296     for (auto &KV : MI.UnemittedDependencies) {
1297       auto &UnemittedDepJD = *KV.first;
1298       for (auto &UnemittedDepName : KV.second) {
1299         auto UnemittedDepMII =
1300             UnemittedDepJD.MaterializingInfos.find(UnemittedDepName);
1301         assert(UnemittedDepMII != UnemittedDepJD.MaterializingInfos.end() &&
1302                "Missing MII for unemitted dependency");
1303         assert(UnemittedDepMII->second.Dependants.count(&JD) &&
1304                "JD not listed as a dependant of unemitted dependency");
1305         assert(UnemittedDepMII->second.Dependants[&JD].count(Name) &&
1306                "Name is not listed as a dependant of unemitted dependency");
1307         UnemittedDepMII->second.Dependants[&JD].erase(Name);
1308         if (UnemittedDepMII->second.Dependants[&JD].empty())
1309           UnemittedDepMII->second.Dependants.erase(&JD);
1310       }
1311     }
1312     MI.UnemittedDependencies.clear();
1313
1314     // Collect queries to be failed for this MII.
1315     AsynchronousSymbolQueryList ToDetach;
1316     for (auto &Q : MII->second.pendingQueries()) {
1317       // Add the query to the list to be failed and detach it.
1318       FailedQueries.insert(Q);
1319       ToDetach.push_back(Q);
1320     }
1321     for (auto &Q : ToDetach)
1322       Q->detach();
1323
1324     assert(MI.Dependants.empty() &&
1325            "Can not delete MaterializingInfo with dependants still attached");
1326     assert(MI.UnemittedDependencies.empty() &&
1327            "Can not delete MaterializingInfo with unemitted dependencies "
1328            "still attached");
1329     assert(!MI.hasQueriesPending() &&
1330            "Can not delete MaterializingInfo with queries pending");
1331     JD.MaterializingInfos.erase(MII);
1332   }
1333
1334   return std::make_pair(std::move(FailedQueries), std::move(FailedSymbolsMap));
1335 }
1336
1337 void JITDylib::setLinkOrder(JITDylibSearchOrder NewLinkOrder,
1338                             bool LinkAgainstThisJITDylibFirst) {
1339   ES.runSessionLocked([&]() {
1340     assert(State == Open && "JD is defunct");
1341     if (LinkAgainstThisJITDylibFirst) {
1342       LinkOrder.clear();
1343       if (NewLinkOrder.empty() || NewLinkOrder.front().first != this)
1344         LinkOrder.push_back(
1345             std::make_pair(this, JITDylibLookupFlags::MatchAllSymbols));
1346       llvm::append_range(LinkOrder, NewLinkOrder);
1347     } else
1348       LinkOrder = std::move(NewLinkOrder);
1349   });
1350 }
1351
1352 void JITDylib::addToLinkOrder(const JITDylibSearchOrder &NewLinks) {
1353   ES.runSessionLocked([&]() {
1354     for (auto &KV : NewLinks) {
1355       // Skip elements of NewLinks that are already in the link order.
1356       if (llvm::is_contained(LinkOrder, KV))
1357         continue;
1358
1359       LinkOrder.push_back(std::move(KV));
1360     }
1361   });
1362 }
1363
1364 void JITDylib::addToLinkOrder(JITDylib &JD, JITDylibLookupFlags JDLookupFlags) {
1365   ES.runSessionLocked([&]() { LinkOrder.push_back({&JD, JDLookupFlags}); });
1366 }
1367
1368 void JITDylib::replaceInLinkOrder(JITDylib &OldJD, JITDylib &NewJD,
1369                                   JITDylibLookupFlags JDLookupFlags) {
1370   ES.runSessionLocked([&]() {
1371     assert(State == Open && "JD is defunct");
1372     for (auto &KV : LinkOrder)
1373       if (KV.first == &OldJD) {
1374         KV = {&NewJD, JDLookupFlags};
1375         break;
1376       }
1377   });
1378 }
1379
1380 void JITDylib::removeFromLinkOrder(JITDylib &JD) {
1381   ES.runSessionLocked([&]() {
1382     assert(State == Open && "JD is defunct");
1383     auto I = llvm::find_if(LinkOrder,
1384                            [&](const JITDylibSearchOrder::value_type &KV) {
1385                              return KV.first == &JD;
1386                            });
1387     if (I != LinkOrder.end())
1388       LinkOrder.erase(I);
1389   });
1390 }
1391
1392 Error JITDylib::remove(const SymbolNameSet &Names) {
1393   return ES.runSessionLocked([&]() -> Error {
1394     assert(State == Open && "JD is defunct");
1395     using SymbolMaterializerItrPair =
1396         std::pair<SymbolTable::iterator, UnmaterializedInfosMap::iterator>;
1397     std::vector<SymbolMaterializerItrPair> SymbolsToRemove;
1398     SymbolNameSet Missing;
1399     SymbolNameSet Materializing;
1400
1401     for (auto &Name : Names) {
1402       auto I = Symbols.find(Name);
1403
1404       // Note symbol missing.
1405       if (I == Symbols.end()) {
1406         Missing.insert(Name);
1407         continue;
1408       }
1409
1410       // Note symbol materializing.
1411       if (I->second.getState() != SymbolState::NeverSearched &&
1412           I->second.getState() != SymbolState::Ready) {
1413         Materializing.insert(Name);
1414         continue;
1415       }
1416
1417       auto UMII = I->second.hasMaterializerAttached()
1418                       ? UnmaterializedInfos.find(Name)
1419                       : UnmaterializedInfos.end();
1420       SymbolsToRemove.push_back(std::make_pair(I, UMII));
1421     }
1422
1423     // If any of the symbols are not defined, return an error.
1424     if (!Missing.empty())
1425       return make_error<SymbolsNotFound>(ES.getSymbolStringPool(),
1426                                          std::move(Missing));
1427
1428     // If any of the symbols are currently materializing, return an error.
1429     if (!Materializing.empty())
1430       return make_error<SymbolsCouldNotBeRemoved>(ES.getSymbolStringPool(),
1431                                                   std::move(Materializing));
1432
1433     // Remove the symbols.
1434     for (auto &SymbolMaterializerItrPair : SymbolsToRemove) {
1435       auto UMII = SymbolMaterializerItrPair.second;
1436
1437       // If there is a materializer attached, call discard.
1438       if (UMII != UnmaterializedInfos.end()) {
1439         UMII->second->MU->doDiscard(*this, UMII->first);
1440         UnmaterializedInfos.erase(UMII);
1441       }
1442
1443       auto SymI = SymbolMaterializerItrPair.first;
1444       Symbols.erase(SymI);
1445     }
1446
1447     return Error::success();
1448   });
1449 }
1450
1451 void JITDylib::dump(raw_ostream &OS) {
1452   ES.runSessionLocked([&, this]() {
1453     OS << "JITDylib \"" << getName() << "\" (ES: "
1454        << format("0x%016" PRIx64, reinterpret_cast<uintptr_t>(&ES))
1455        << ", State = ";
1456     switch (State) {
1457     case Open:
1458       OS << "Open";
1459       break;
1460     case Closing:
1461       OS << "Closing";
1462       break;
1463     case Closed:
1464       OS << "Closed";
1465       break;
1466     }
1467     OS << ")\n";
1468     if (State == Closed)
1469       return;
1470     OS << "Link order: " << LinkOrder << "\n"
1471        << "Symbol table:\n";
1472
1473     // Sort symbols so we get a deterministic order and can check them in tests.
1474     std::vector<std::pair<SymbolStringPtr, SymbolTableEntry *>> SymbolsSorted;
1475     for (auto &KV : Symbols)
1476       SymbolsSorted.emplace_back(KV.first, &KV.second);
1477     std::sort(SymbolsSorted.begin(), SymbolsSorted.end(),
1478               [](const auto &L, const auto &R) { return *L.first < *R.first; });
1479
1480     for (auto &KV : SymbolsSorted) {
1481       OS << "    \"" << *KV.first << "\": ";
1482       if (auto Addr = KV.second->getAddress())
1483         OS << Addr;
1484       else
1485         OS << "<not resolved> ";
1486
1487       OS << " " << KV.second->getFlags() << " " << KV.second->getState();
1488
1489       if (KV.second->hasMaterializerAttached()) {
1490         OS << " (Materializer ";
1491         auto I = UnmaterializedInfos.find(KV.first);
1492         assert(I != UnmaterializedInfos.end() &&
1493                "Lazy symbol should have UnmaterializedInfo");
1494         OS << I->second->MU.get() << ", " << I->second->MU->getName() << ")\n";
1495       } else
1496         OS << "\n";
1497     }
1498
1499     if (!MaterializingInfos.empty())
1500       OS << "  MaterializingInfos entries:\n";
1501     for (auto &KV : MaterializingInfos) {
1502       OS << "    \"" << *KV.first << "\":\n"
1503          << "      " << KV.second.pendingQueries().size()
1504          << " pending queries: { ";
1505       for (const auto &Q : KV.second.pendingQueries())
1506         OS << Q.get() << " (" << Q->getRequiredState() << ") ";
1507       OS << "}\n      Dependants:\n";
1508       for (auto &KV2 : KV.second.Dependants)
1509         OS << "        " << KV2.first->getName() << ": " << KV2.second << "\n";
1510       OS << "      Unemitted Dependencies:\n";
1511       for (auto &KV2 : KV.second.UnemittedDependencies)
1512         OS << "        " << KV2.first->getName() << ": " << KV2.second << "\n";
1513       assert((Symbols[KV.first].getState() != SymbolState::Ready ||
1514               !KV.second.pendingQueries().empty() ||
1515               !KV.second.Dependants.empty() ||
1516               !KV.second.UnemittedDependencies.empty()) &&
1517              "Stale materializing info entry");
1518     }
1519   });
1520 }
1521
1522 void JITDylib::MaterializingInfo::addQuery(
1523     std::shared_ptr<AsynchronousSymbolQuery> Q) {
1524
1525   auto I = llvm::lower_bound(
1526       llvm::reverse(PendingQueries), Q->getRequiredState(),
1527       [](const std::shared_ptr<AsynchronousSymbolQuery> &V, SymbolState S) {
1528         return V->getRequiredState() <= S;
1529       });
1530   PendingQueries.insert(I.base(), std::move(Q));
1531 }
1532
1533 void JITDylib::MaterializingInfo::removeQuery(
1534     const AsynchronousSymbolQuery &Q) {
1535   // FIXME: Implement 'find_as' for shared_ptr<T>/T*.
1536   auto I = llvm::find_if(
1537       PendingQueries, [&Q](const std::shared_ptr<AsynchronousSymbolQuery> &V) {
1538         return V.get() == &Q;
1539       });
1540   assert(I != PendingQueries.end() &&
1541          "Query is not attached to this MaterializingInfo");
1542   PendingQueries.erase(I);
1543 }
1544
1545 JITDylib::AsynchronousSymbolQueryList
1546 JITDylib::MaterializingInfo::takeQueriesMeeting(SymbolState RequiredState) {
1547   AsynchronousSymbolQueryList Result;
1548   while (!PendingQueries.empty()) {
1549     if (PendingQueries.back()->getRequiredState() > RequiredState)
1550       break;
1551
1552     Result.push_back(std::move(PendingQueries.back()));
1553     PendingQueries.pop_back();
1554   }
1555
1556   return Result;
1557 }
1558
1559 JITDylib::JITDylib(ExecutionSession &ES, std::string Name)
1560     : JITLinkDylib(std::move(Name)), ES(ES) {
1561   LinkOrder.push_back({this, JITDylibLookupFlags::MatchAllSymbols});
1562 }
1563
1564 std::pair<JITDylib::AsynchronousSymbolQuerySet,
1565           std::shared_ptr<SymbolDependenceMap>>
1566 JITDylib::removeTracker(ResourceTracker &RT) {
1567   // Note: Should be called under the session lock.
1568   assert(State != Closed && "JD is defunct");
1569
1570   SymbolNameVector SymbolsToRemove;
1571   std::vector<std::pair<JITDylib *, SymbolStringPtr>> SymbolsToFail;
1572
1573   if (&RT == DefaultTracker.get()) {
1574     SymbolNameSet TrackedSymbols;
1575     for (auto &KV : TrackerSymbols)
1576       for (auto &Sym : KV.second)
1577         TrackedSymbols.insert(Sym);
1578
1579     for (auto &KV : Symbols) {
1580       auto &Sym = KV.first;
1581       if (!TrackedSymbols.count(Sym))
1582         SymbolsToRemove.push_back(Sym);
1583     }
1584
1585     DefaultTracker.reset();
1586   } else {
1587     /// Check for a non-default tracker.
1588     auto I = TrackerSymbols.find(&RT);
1589     if (I != TrackerSymbols.end()) {
1590       SymbolsToRemove = std::move(I->second);
1591       TrackerSymbols.erase(I);
1592     }
1593     // ... if not found this tracker was already defunct. Nothing to do.
1594   }
1595
1596   for (auto &Sym : SymbolsToRemove) {
1597     assert(Symbols.count(Sym) && "Symbol not in symbol table");
1598
1599     // If there is a MaterializingInfo then collect any queries to fail.
1600     auto MII = MaterializingInfos.find(Sym);
1601     if (MII != MaterializingInfos.end())
1602       SymbolsToFail.push_back({this, Sym});
1603   }
1604
1605   AsynchronousSymbolQuerySet QueriesToFail;
1606   auto Result = failSymbols(std::move(SymbolsToFail));
1607
1608   // Removed symbols should be taken out of the table altogether.
1609   for (auto &Sym : SymbolsToRemove) {
1610     auto I = Symbols.find(Sym);
1611     assert(I != Symbols.end() && "Symbol not present in table");
1612
1613     // Remove Materializer if present.
1614     if (I->second.hasMaterializerAttached()) {
1615       // FIXME: Should this discard the symbols?
1616       UnmaterializedInfos.erase(Sym);
1617     } else {
1618       assert(!UnmaterializedInfos.count(Sym) &&
1619              "Symbol has materializer attached");
1620     }
1621
1622     Symbols.erase(I);
1623   }
1624
1625   return Result;
1626 }
1627
1628 void JITDylib::transferTracker(ResourceTracker &DstRT, ResourceTracker &SrcRT) {
1629   assert(State != Closed && "JD is defunct");
1630   assert(&DstRT != &SrcRT && "No-op transfers shouldn't call transferTracker");
1631   assert(&DstRT.getJITDylib() == this && "DstRT is not for this JITDylib");
1632   assert(&SrcRT.getJITDylib() == this && "SrcRT is not for this JITDylib");
1633
1634   // Update trackers for any not-yet materialized units.
1635   for (auto &KV : UnmaterializedInfos) {
1636     if (KV.second->RT == &SrcRT)
1637       KV.second->RT = &DstRT;
1638   }
1639
1640   // Update trackers for any active materialization responsibilities.
1641   {
1642     auto I = TrackerMRs.find(&SrcRT);
1643     if (I != TrackerMRs.end()) {
1644       auto &SrcMRs = I->second;
1645       auto &DstMRs = TrackerMRs[&DstRT];
1646       for (auto *MR : SrcMRs)
1647         MR->RT = &DstRT;
1648       if (DstMRs.empty())
1649         DstMRs = std::move(SrcMRs);
1650       else
1651         for (auto *MR : SrcMRs)
1652           DstMRs.insert(MR);
1653       // Erase SrcRT entry in TrackerMRs. Use &SrcRT key rather than iterator I
1654       // for this, since I may have been invalidated by 'TrackerMRs[&DstRT]'.
1655       TrackerMRs.erase(&SrcRT);
1656     }
1657   }
1658
1659   // If we're transfering to the default tracker we just need to delete the
1660   // tracked symbols for the source tracker.
1661   if (&DstRT == DefaultTracker.get()) {
1662     TrackerSymbols.erase(&SrcRT);
1663     return;
1664   }
1665
1666   // If we're transferring from the default tracker we need to find all
1667   // currently untracked symbols.
1668   if (&SrcRT == DefaultTracker.get()) {
1669     assert(!TrackerSymbols.count(&SrcRT) &&
1670            "Default tracker should not appear in TrackerSymbols");
1671
1672     SymbolNameVector SymbolsToTrack;
1673
1674     SymbolNameSet CurrentlyTrackedSymbols;
1675     for (auto &KV : TrackerSymbols)
1676       for (auto &Sym : KV.second)
1677         CurrentlyTrackedSymbols.insert(Sym);
1678
1679     for (auto &KV : Symbols) {
1680       auto &Sym = KV.first;
1681       if (!CurrentlyTrackedSymbols.count(Sym))
1682         SymbolsToTrack.push_back(Sym);
1683     }
1684
1685     TrackerSymbols[&DstRT] = std::move(SymbolsToTrack);
1686     return;
1687   }
1688
1689   auto &DstTrackedSymbols = TrackerSymbols[&DstRT];
1690
1691   // Finally if neither SrtRT or DstRT are the default tracker then
1692   // just append DstRT's tracked symbols to SrtRT's.
1693   auto SI = TrackerSymbols.find(&SrcRT);
1694   if (SI == TrackerSymbols.end())
1695     return;
1696
1697   DstTrackedSymbols.reserve(DstTrackedSymbols.size() + SI->second.size());
1698   for (auto &Sym : SI->second)
1699     DstTrackedSymbols.push_back(std::move(Sym));
1700   TrackerSymbols.erase(SI);
1701 }
1702
1703 Error JITDylib::defineImpl(MaterializationUnit &MU) {
1704
1705   LLVM_DEBUG({ dbgs() << "  " << MU.getSymbols() << "\n"; });
1706
1707   SymbolNameSet Duplicates;
1708   std::vector<SymbolStringPtr> ExistingDefsOverridden;
1709   std::vector<SymbolStringPtr> MUDefsOverridden;
1710
1711   for (const auto &KV : MU.getSymbols()) {
1712     auto I = Symbols.find(KV.first);
1713
1714     if (I != Symbols.end()) {
1715       if (KV.second.isStrong()) {
1716         if (I->second.getFlags().isStrong() ||
1717             I->second.getState() > SymbolState::NeverSearched)
1718           Duplicates.insert(KV.first);
1719         else {
1720           assert(I->second.getState() == SymbolState::NeverSearched &&
1721                  "Overridden existing def should be in the never-searched "
1722                  "state");
1723           ExistingDefsOverridden.push_back(KV.first);
1724         }
1725       } else
1726         MUDefsOverridden.push_back(KV.first);
1727     }
1728   }
1729
1730   // If there were any duplicate definitions then bail out.
1731   if (!Duplicates.empty()) {
1732     LLVM_DEBUG(
1733         { dbgs() << "  Error: Duplicate symbols " << Duplicates << "\n"; });
1734     return make_error<DuplicateDefinition>(std::string(**Duplicates.begin()));
1735   }
1736
1737   // Discard any overridden defs in this MU.
1738   LLVM_DEBUG({
1739     if (!MUDefsOverridden.empty())
1740       dbgs() << "  Defs in this MU overridden: " << MUDefsOverridden << "\n";
1741   });
1742   for (auto &S : MUDefsOverridden)
1743     MU.doDiscard(*this, S);
1744
1745   // Discard existing overridden defs.
1746   LLVM_DEBUG({
1747     if (!ExistingDefsOverridden.empty())
1748       dbgs() << "  Existing defs overridden by this MU: " << MUDefsOverridden
1749              << "\n";
1750   });
1751   for (auto &S : ExistingDefsOverridden) {
1752
1753     auto UMII = UnmaterializedInfos.find(S);
1754     assert(UMII != UnmaterializedInfos.end() &&
1755            "Overridden existing def should have an UnmaterializedInfo");
1756     UMII->second->MU->doDiscard(*this, S);
1757   }
1758
1759   // Finally, add the defs from this MU.
1760   for (auto &KV : MU.getSymbols()) {
1761     auto &SymEntry = Symbols[KV.first];
1762     SymEntry.setFlags(KV.second);
1763     SymEntry.setState(SymbolState::NeverSearched);
1764     SymEntry.setMaterializerAttached(true);
1765   }
1766
1767   return Error::success();
1768 }
1769
1770 void JITDylib::installMaterializationUnit(
1771     std::unique_ptr<MaterializationUnit> MU, ResourceTracker &RT) {
1772
1773   /// defineImpl succeeded.
1774   if (&RT != DefaultTracker.get()) {
1775     auto &TS = TrackerSymbols[&RT];
1776     TS.reserve(TS.size() + MU->getSymbols().size());
1777     for (auto &KV : MU->getSymbols())
1778       TS.push_back(KV.first);
1779   }
1780
1781   auto UMI = std::make_shared<UnmaterializedInfo>(std::move(MU), &RT);
1782   for (auto &KV : UMI->MU->getSymbols())
1783     UnmaterializedInfos[KV.first] = UMI;
1784 }
1785
1786 void JITDylib::detachQueryHelper(AsynchronousSymbolQuery &Q,
1787                                  const SymbolNameSet &QuerySymbols) {
1788   for (auto &QuerySymbol : QuerySymbols) {
1789     assert(MaterializingInfos.count(QuerySymbol) &&
1790            "QuerySymbol does not have MaterializingInfo");
1791     auto &MI = MaterializingInfos[QuerySymbol];
1792     MI.removeQuery(Q);
1793   }
1794 }
1795
1796 void JITDylib::transferEmittedNodeDependencies(
1797     MaterializingInfo &DependantMI, const SymbolStringPtr &DependantName,
1798     MaterializingInfo &EmittedMI) {
1799   for (auto &KV : EmittedMI.UnemittedDependencies) {
1800     auto &DependencyJD = *KV.first;
1801     SymbolNameSet *UnemittedDependenciesOnDependencyJD = nullptr;
1802
1803     for (auto &DependencyName : KV.second) {
1804       auto &DependencyMI = DependencyJD.MaterializingInfos[DependencyName];
1805
1806       // Do not add self dependencies.
1807       if (&DependencyMI == &DependantMI)
1808         continue;
1809
1810       // If we haven't looked up the dependencies for DependencyJD yet, do it
1811       // now and cache the result.
1812       if (!UnemittedDependenciesOnDependencyJD)
1813         UnemittedDependenciesOnDependencyJD =
1814             &DependantMI.UnemittedDependencies[&DependencyJD];
1815
1816       DependencyMI.Dependants[this].insert(DependantName);
1817       UnemittedDependenciesOnDependencyJD->insert(DependencyName);
1818     }
1819   }
1820 }
1821
1822 Platform::~Platform() = default;
1823
1824 Expected<DenseMap<JITDylib *, SymbolMap>> Platform::lookupInitSymbols(
1825     ExecutionSession &ES,
1826     const DenseMap<JITDylib *, SymbolLookupSet> &InitSyms) {
1827
1828   DenseMap<JITDylib *, SymbolMap> CompoundResult;
1829   Error CompoundErr = Error::success();
1830   std::mutex LookupMutex;
1831   std::condition_variable CV;
1832   uint64_t Count = InitSyms.size();
1833
1834   LLVM_DEBUG({
1835     dbgs() << "Issuing init-symbol lookup:\n";
1836     for (auto &KV : InitSyms)
1837       dbgs() << "  " << KV.first->getName() << ": " << KV.second << "\n";
1838   });
1839
1840   for (auto &KV : InitSyms) {
1841     auto *JD = KV.first;
1842     auto Names = std::move(KV.second);
1843     ES.lookup(
1844         LookupKind::Static,
1845         JITDylibSearchOrder({{JD, JITDylibLookupFlags::MatchAllSymbols}}),
1846         std::move(Names), SymbolState::Ready,
1847         [&, JD](Expected<SymbolMap> Result) {
1848           {
1849             std::lock_guard<std::mutex> Lock(LookupMutex);
1850             --Count;
1851             if (Result) {
1852               assert(!CompoundResult.count(JD) &&
1853                      "Duplicate JITDylib in lookup?");
1854               CompoundResult[JD] = std::move(*Result);
1855             } else
1856               CompoundErr =
1857                   joinErrors(std::move(CompoundErr), Result.takeError());
1858           }
1859           CV.notify_one();
1860         },
1861         NoDependenciesToRegister);
1862   }
1863
1864   std::unique_lock<std::mutex> Lock(LookupMutex);
1865   CV.wait(Lock, [&] { return Count == 0 || CompoundErr; });
1866
1867   if (CompoundErr)
1868     return std::move(CompoundErr);
1869
1870   return std::move(CompoundResult);
1871 }
1872
1873 void Platform::lookupInitSymbolsAsync(
1874     unique_function<void(Error)> OnComplete, ExecutionSession &ES,
1875     const DenseMap<JITDylib *, SymbolLookupSet> &InitSyms) {
1876
1877   class TriggerOnComplete {
1878   public:
1879     using OnCompleteFn = unique_function<void(Error)>;
1880     TriggerOnComplete(OnCompleteFn OnComplete)
1881         : OnComplete(std::move(OnComplete)) {}
1882     ~TriggerOnComplete() { OnComplete(std::move(LookupResult)); }
1883     void reportResult(Error Err) {
1884       std::lock_guard<std::mutex> Lock(ResultMutex);
1885       LookupResult = joinErrors(std::move(LookupResult), std::move(Err));
1886     }
1887
1888   private:
1889     std::mutex ResultMutex;
1890     Error LookupResult{Error::success()};
1891     OnCompleteFn OnComplete;
1892   };
1893
1894   LLVM_DEBUG({
1895     dbgs() << "Issuing init-symbol lookup:\n";
1896     for (auto &KV : InitSyms)
1897       dbgs() << "  " << KV.first->getName() << ": " << KV.second << "\n";
1898   });
1899
1900   auto TOC = std::make_shared<TriggerOnComplete>(std::move(OnComplete));
1901
1902   for (auto &KV : InitSyms) {
1903     auto *JD = KV.first;
1904     auto Names = std::move(KV.second);
1905     ES.lookup(
1906         LookupKind::Static,
1907         JITDylibSearchOrder({{JD, JITDylibLookupFlags::MatchAllSymbols}}),
1908         std::move(Names), SymbolState::Ready,
1909         [TOC](Expected<SymbolMap> Result) {
1910           TOC->reportResult(Result.takeError());
1911         },
1912         NoDependenciesToRegister);
1913   }
1914 }
1915
1916 void MaterializationTask::printDescription(raw_ostream &OS) {
1917   OS << "Materialization task: " << MU->getName() << " in "
1918      << MR->getTargetJITDylib().getName();
1919 }
1920
1921 void MaterializationTask::run() { MU->materialize(std::move(MR)); }
1922
1923 void LookupTask::printDescription(raw_ostream &OS) { OS << "Lookup task"; }
1924
1925 void LookupTask::run() { LS.continueLookup(Error::success()); }
1926
1927 ExecutionSession::ExecutionSession(std::unique_ptr<ExecutorProcessControl> EPC)
1928     : EPC(std::move(EPC)) {
1929   // Associated EPC and this.
1930   this->EPC->ES = this;
1931 }
1932
1933 ExecutionSession::~ExecutionSession() {
1934   // You must call endSession prior to destroying the session.
1935   assert(!SessionOpen &&
1936          "Session still open. Did you forget to call endSession?");
1937 }
1938
1939 Error ExecutionSession::endSession() {
1940   LLVM_DEBUG(dbgs() << "Ending ExecutionSession " << this << "\n");
1941
1942   auto JDsToRemove = runSessionLocked([&] {
1943     SessionOpen = false;
1944     return JDs;
1945   });
1946
1947   std::reverse(JDsToRemove.begin(), JDsToRemove.end());
1948
1949   auto Err = removeJITDylibs(std::move(JDsToRemove));
1950
1951   Err = joinErrors(std::move(Err), EPC->disconnect());
1952
1953   return Err;
1954 }
1955
1956 void ExecutionSession::registerResourceManager(ResourceManager &RM) {
1957   runSessionLocked([&] { ResourceManagers.push_back(&RM); });
1958 }
1959
1960 void ExecutionSession::deregisterResourceManager(ResourceManager &RM) {
1961   runSessionLocked([&] {
1962     assert(!ResourceManagers.empty() && "No managers registered");
1963     if (ResourceManagers.back() == &RM)
1964       ResourceManagers.pop_back();
1965     else {
1966       auto I = llvm::find(ResourceManagers, &RM);
1967       assert(I != ResourceManagers.end() && "RM not registered");
1968       ResourceManagers.erase(I);
1969     }
1970   });
1971 }
1972
1973 JITDylib *ExecutionSession::getJITDylibByName(StringRef Name) {
1974   return runSessionLocked([&, this]() -> JITDylib * {
1975     for (auto &JD : JDs)
1976       if (JD->getName() == Name)
1977         return JD.get();
1978     return nullptr;
1979   });
1980 }
1981
1982 JITDylib &ExecutionSession::createBareJITDylib(std::string Name) {
1983   assert(!getJITDylibByName(Name) && "JITDylib with that name already exists");
1984   return runSessionLocked([&, this]() -> JITDylib & {
1985     assert(SessionOpen && "Cannot create JITDylib after session is closed");
1986     JDs.push_back(new JITDylib(*this, std::move(Name)));
1987     return *JDs.back();
1988   });
1989 }
1990
1991 Expected<JITDylib &> ExecutionSession::createJITDylib(std::string Name) {
1992   auto &JD = createBareJITDylib(Name);
1993   if (P)
1994     if (auto Err = P->setupJITDylib(JD))
1995       return std::move(Err);
1996   return JD;
1997 }
1998
1999 Error ExecutionSession::removeJITDylibs(std::vector<JITDylibSP> JDsToRemove) {
2000
2001   // Set JD to 'Closing' state and remove JD from the ExecutionSession.
2002   runSessionLocked([&] {
2003     for (auto &JD : JDsToRemove) {
2004       assert(JD->State == JITDylib::Open && "JD already closed");
2005       JD->State = JITDylib::Closing;
2006       auto I = llvm::find(JDs, JD);
2007       assert(I != JDs.end() && "JD does not appear in session JDs");
2008       JDs.erase(I);
2009     }
2010   });
2011
2012   // Clear JITDylibs and notify the platform.
2013   Error Err = Error::success();
2014   for (auto JD : JDsToRemove) {
2015     Err = joinErrors(std::move(Err), JD->clear());
2016     if (P)
2017       Err = joinErrors(std::move(Err), P->teardownJITDylib(*JD));
2018   }
2019
2020   // Set JD to closed state. Clear remaining data structures.
2021   runSessionLocked([&] {
2022     for (auto &JD : JDsToRemove) {
2023       assert(JD->State == JITDylib::Closing && "JD should be closing");
2024       JD->State = JITDylib::Closed;
2025       assert(JD->Symbols.empty() && "JD.Symbols is not empty after clear");
2026       assert(JD->UnmaterializedInfos.empty() &&
2027              "JD.UnmaterializedInfos is not empty after clear");
2028       assert(JD->MaterializingInfos.empty() &&
2029              "JD.MaterializingInfos is not empty after clear");
2030       assert(JD->TrackerSymbols.empty() &&
2031              "TrackerSymbols is not empty after clear");
2032       JD->DefGenerators.clear();
2033       JD->LinkOrder.clear();
2034     }
2035   });
2036
2037   return Err;
2038 }
2039
2040 Expected<std::vector<JITDylibSP>>
2041 JITDylib::getDFSLinkOrder(ArrayRef<JITDylibSP> JDs) {
2042   if (JDs.empty())
2043     return std::vector<JITDylibSP>();
2044
2045   auto &ES = JDs.front()->getExecutionSession();
2046   return ES.runSessionLocked([&]() -> Expected<std::vector<JITDylibSP>> {
2047     DenseSet<JITDylib *> Visited;
2048     std::vector<JITDylibSP> Result;
2049
2050     for (auto &JD : JDs) {
2051
2052       if (JD->State != Open)
2053         return make_error<StringError>(
2054             "Error building link order: " + JD->getName() + " is defunct",
2055             inconvertibleErrorCode());
2056       if (Visited.count(JD.get()))
2057         continue;
2058
2059       SmallVector<JITDylibSP, 64> WorkStack;
2060       WorkStack.push_back(JD);
2061       Visited.insert(JD.get());
2062
2063       while (!WorkStack.empty()) {
2064         Result.push_back(std::move(WorkStack.back()));
2065         WorkStack.pop_back();
2066
2067         for (auto &KV : llvm::reverse(Result.back()->LinkOrder)) {
2068           auto &JD = *KV.first;
2069           if (!Visited.insert(&JD).second)
2070             continue;
2071           WorkStack.push_back(&JD);
2072         }
2073       }
2074     }
2075     return Result;
2076   });
2077 }
2078
2079 Expected<std::vector<JITDylibSP>>
2080 JITDylib::getReverseDFSLinkOrder(ArrayRef<JITDylibSP> JDs) {
2081   auto Result = getDFSLinkOrder(JDs);
2082   if (Result)
2083     std::reverse(Result->begin(), Result->end());
2084   return Result;
2085 }
2086
2087 Expected<std::vector<JITDylibSP>> JITDylib::getDFSLinkOrder() {
2088   return getDFSLinkOrder({this});
2089 }
2090
2091 Expected<std::vector<JITDylibSP>> JITDylib::getReverseDFSLinkOrder() {
2092   return getReverseDFSLinkOrder({this});
2093 }
2094
2095 void ExecutionSession::lookupFlags(
2096     LookupKind K, JITDylibSearchOrder SearchOrder, SymbolLookupSet LookupSet,
2097     unique_function<void(Expected<SymbolFlagsMap>)> OnComplete) {
2098
2099   OL_applyQueryPhase1(std::make_unique<InProgressLookupFlagsState>(
2100                           K, std::move(SearchOrder), std::move(LookupSet),
2101                           std::move(OnComplete)),
2102                       Error::success());
2103 }
2104
2105 Expected<SymbolFlagsMap>
2106 ExecutionSession::lookupFlags(LookupKind K, JITDylibSearchOrder SearchOrder,
2107                               SymbolLookupSet LookupSet) {
2108
2109   std::promise<MSVCPExpected<SymbolFlagsMap>> ResultP;
2110   OL_applyQueryPhase1(std::make_unique<InProgressLookupFlagsState>(
2111                           K, std::move(SearchOrder), std::move(LookupSet),
2112                           [&ResultP](Expected<SymbolFlagsMap> Result) {
2113                             ResultP.set_value(std::move(Result));
2114                           }),
2115                       Error::success());
2116
2117   auto ResultF = ResultP.get_future();
2118   return ResultF.get();
2119 }
2120
2121 void ExecutionSession::lookup(
2122     LookupKind K, const JITDylibSearchOrder &SearchOrder,
2123     SymbolLookupSet Symbols, SymbolState RequiredState,
2124     SymbolsResolvedCallback NotifyComplete,
2125     RegisterDependenciesFunction RegisterDependencies) {
2126
2127   LLVM_DEBUG({
2128     runSessionLocked([&]() {
2129       dbgs() << "Looking up " << Symbols << " in " << SearchOrder
2130              << " (required state: " << RequiredState << ")\n";
2131     });
2132   });
2133
2134   // lookup can be re-entered recursively if running on a single thread. Run any
2135   // outstanding MUs in case this query depends on them, otherwise this lookup
2136   // will starve waiting for a result from an MU that is stuck in the queue.
2137   dispatchOutstandingMUs();
2138
2139   auto Unresolved = std::move(Symbols);
2140   auto Q = std::make_shared<AsynchronousSymbolQuery>(Unresolved, RequiredState,
2141                                                      std::move(NotifyComplete));
2142
2143   auto IPLS = std::make_unique<InProgressFullLookupState>(
2144       K, SearchOrder, std::move(Unresolved), RequiredState, std::move(Q),
2145       std::move(RegisterDependencies));
2146
2147   OL_applyQueryPhase1(std::move(IPLS), Error::success());
2148 }
2149
2150 Expected<SymbolMap>
2151 ExecutionSession::lookup(const JITDylibSearchOrder &SearchOrder,
2152                          SymbolLookupSet Symbols, LookupKind K,
2153                          SymbolState RequiredState,
2154                          RegisterDependenciesFunction RegisterDependencies) {
2155 #if LLVM_ENABLE_THREADS
2156   // In the threaded case we use promises to return the results.
2157   std::promise<SymbolMap> PromisedResult;
2158   Error ResolutionError = Error::success();
2159
2160   auto NotifyComplete = [&](Expected<SymbolMap> R) {
2161     if (R)
2162       PromisedResult.set_value(std::move(*R));
2163     else {
2164       ErrorAsOutParameter _(&ResolutionError);
2165       ResolutionError = R.takeError();
2166       PromisedResult.set_value(SymbolMap());
2167     }
2168   };
2169
2170 #else
2171   SymbolMap Result;
2172   Error ResolutionError = Error::success();
2173
2174   auto NotifyComplete = [&](Expected<SymbolMap> R) {
2175     ErrorAsOutParameter _(&ResolutionError);
2176     if (R)
2177       Result = std::move(*R);
2178     else
2179       ResolutionError = R.takeError();
2180   };
2181 #endif
2182
2183   // Perform the asynchronous lookup.
2184   lookup(K, SearchOrder, std::move(Symbols), RequiredState, NotifyComplete,
2185          RegisterDependencies);
2186
2187 #if LLVM_ENABLE_THREADS
2188   auto ResultFuture = PromisedResult.get_future();
2189   auto Result = ResultFuture.get();
2190
2191   if (ResolutionError)
2192     return std::move(ResolutionError);
2193
2194   return std::move(Result);
2195
2196 #else
2197   if (ResolutionError)
2198     return std::move(ResolutionError);
2199
2200   return Result;
2201 #endif
2202 }
2203
2204 Expected<ExecutorSymbolDef>
2205 ExecutionSession::lookup(const JITDylibSearchOrder &SearchOrder,
2206                          SymbolStringPtr Name, SymbolState RequiredState) {
2207   SymbolLookupSet Names({Name});
2208
2209   if (auto ResultMap = lookup(SearchOrder, std::move(Names), LookupKind::Static,
2210                               RequiredState, NoDependenciesToRegister)) {
2211     assert(ResultMap->size() == 1 && "Unexpected number of results");
2212     assert(ResultMap->count(Name) && "Missing result for symbol");
2213     return std::move(ResultMap->begin()->second);
2214   } else
2215     return ResultMap.takeError();
2216 }
2217
2218 Expected<ExecutorSymbolDef>
2219 ExecutionSession::lookup(ArrayRef<JITDylib *> SearchOrder, SymbolStringPtr Name,
2220                          SymbolState RequiredState) {
2221   return lookup(makeJITDylibSearchOrder(SearchOrder), Name, RequiredState);
2222 }
2223
2224 Expected<ExecutorSymbolDef>
2225 ExecutionSession::lookup(ArrayRef<JITDylib *> SearchOrder, StringRef Name,
2226                          SymbolState RequiredState) {
2227   return lookup(SearchOrder, intern(Name), RequiredState);
2228 }
2229
2230 Error ExecutionSession::registerJITDispatchHandlers(
2231     JITDylib &JD, JITDispatchHandlerAssociationMap WFs) {
2232
2233   auto TagAddrs = lookup({{&JD, JITDylibLookupFlags::MatchAllSymbols}},
2234                          SymbolLookupSet::fromMapKeys(
2235                              WFs, SymbolLookupFlags::WeaklyReferencedSymbol));
2236   if (!TagAddrs)
2237     return TagAddrs.takeError();
2238
2239   // Associate tag addresses with implementations.
2240   std::lock_guard<std::mutex> Lock(JITDispatchHandlersMutex);
2241   for (auto &KV : *TagAddrs) {
2242     auto TagAddr = KV.second.getAddress();
2243     if (JITDispatchHandlers.count(TagAddr))
2244       return make_error<StringError>("Tag " + formatv("{0:x16}", TagAddr) +
2245                                          " (for " + *KV.first +
2246                                          ") already registered",
2247                                      inconvertibleErrorCode());
2248     auto I = WFs.find(KV.first);
2249     assert(I != WFs.end() && I->second &&
2250            "JITDispatchHandler implementation missing");
2251     JITDispatchHandlers[KV.second.getAddress()] =
2252         std::make_shared<JITDispatchHandlerFunction>(std::move(I->second));
2253     LLVM_DEBUG({
2254       dbgs() << "Associated function tag \"" << *KV.first << "\" ("
2255              << formatv("{0:x}", KV.second.getAddress()) << ") with handler\n";
2256     });
2257   }
2258   return Error::success();
2259 }
2260
2261 void ExecutionSession::runJITDispatchHandler(SendResultFunction SendResult,
2262                                              ExecutorAddr HandlerFnTagAddr,
2263                                              ArrayRef<char> ArgBuffer) {
2264
2265   std::shared_ptr<JITDispatchHandlerFunction> F;
2266   {
2267     std::lock_guard<std::mutex> Lock(JITDispatchHandlersMutex);
2268     auto I = JITDispatchHandlers.find(HandlerFnTagAddr);
2269     if (I != JITDispatchHandlers.end())
2270       F = I->second;
2271   }
2272
2273   if (F)
2274     (*F)(std::move(SendResult), ArgBuffer.data(), ArgBuffer.size());
2275   else
2276     SendResult(shared::WrapperFunctionResult::createOutOfBandError(
2277         ("No function registered for tag " +
2278          formatv("{0:x16}", HandlerFnTagAddr))
2279             .str()));
2280 }
2281
2282 void ExecutionSession::dump(raw_ostream &OS) {
2283   runSessionLocked([this, &OS]() {
2284     for (auto &JD : JDs)
2285       JD->dump(OS);
2286   });
2287 }
2288
2289 void ExecutionSession::dispatchOutstandingMUs() {
2290   LLVM_DEBUG(dbgs() << "Dispatching MaterializationUnits...\n");
2291   while (true) {
2292     std::optional<std::pair<std::unique_ptr<MaterializationUnit>,
2293                             std::unique_ptr<MaterializationResponsibility>>>
2294         JMU;
2295
2296     {
2297       std::lock_guard<std::recursive_mutex> Lock(OutstandingMUsMutex);
2298       if (!OutstandingMUs.empty()) {
2299         JMU.emplace(std::move(OutstandingMUs.back()));
2300         OutstandingMUs.pop_back();
2301       }
2302     }
2303
2304     if (!JMU)
2305       break;
2306
2307     assert(JMU->first && "No MU?");
2308     LLVM_DEBUG(dbgs() << "  Dispatching \"" << JMU->first->getName() << "\"\n");
2309     dispatchTask(std::make_unique<MaterializationTask>(std::move(JMU->first),
2310                                                        std::move(JMU->second)));
2311   }
2312   LLVM_DEBUG(dbgs() << "Done dispatching MaterializationUnits.\n");
2313 }
2314
2315 Error ExecutionSession::removeResourceTracker(ResourceTracker &RT) {
2316   LLVM_DEBUG({
2317     dbgs() << "In " << RT.getJITDylib().getName() << " removing tracker "
2318            << formatv("{0:x}", RT.getKeyUnsafe()) << "\n";
2319   });
2320   std::vector<ResourceManager *> CurrentResourceManagers;
2321
2322   JITDylib::AsynchronousSymbolQuerySet QueriesToFail;
2323   std::shared_ptr<SymbolDependenceMap> FailedSymbols;
2324
2325   runSessionLocked([&] {
2326     CurrentResourceManagers = ResourceManagers;
2327     RT.makeDefunct();
2328     std::tie(QueriesToFail, FailedSymbols) = RT.getJITDylib().removeTracker(RT);
2329   });
2330
2331   Error Err = Error::success();
2332
2333   auto &JD = RT.getJITDylib();
2334   for (auto *L : reverse(CurrentResourceManagers))
2335     Err = joinErrors(std::move(Err),
2336                      L->handleRemoveResources(JD, RT.getKeyUnsafe()));
2337
2338   for (auto &Q : QueriesToFail)
2339     Q->handleFailed(
2340         make_error<FailedToMaterialize>(getSymbolStringPool(), FailedSymbols));
2341
2342   return Err;
2343 }
2344
2345 void ExecutionSession::transferResourceTracker(ResourceTracker &DstRT,
2346                                                ResourceTracker &SrcRT) {
2347   LLVM_DEBUG({
2348     dbgs() << "In " << SrcRT.getJITDylib().getName()
2349            << " transfering resources from tracker "
2350            << formatv("{0:x}", SrcRT.getKeyUnsafe()) << " to tracker "
2351            << formatv("{0:x}", DstRT.getKeyUnsafe()) << "\n";
2352   });
2353
2354   // No-op transfers are allowed and do not invalidate the source.
2355   if (&DstRT == &SrcRT)
2356     return;
2357
2358   assert(&DstRT.getJITDylib() == &SrcRT.getJITDylib() &&
2359          "Can't transfer resources between JITDylibs");
2360   runSessionLocked([&]() {
2361     SrcRT.makeDefunct();
2362     auto &JD = DstRT.getJITDylib();
2363     JD.transferTracker(DstRT, SrcRT);
2364     for (auto *L : reverse(ResourceManagers))
2365       L->handleTransferResources(JD, DstRT.getKeyUnsafe(),
2366                                  SrcRT.getKeyUnsafe());
2367   });
2368 }
2369
2370 void ExecutionSession::destroyResourceTracker(ResourceTracker &RT) {
2371   runSessionLocked([&]() {
2372     LLVM_DEBUG({
2373       dbgs() << "In " << RT.getJITDylib().getName() << " destroying tracker "
2374              << formatv("{0:x}", RT.getKeyUnsafe()) << "\n";
2375     });
2376     if (!RT.isDefunct())
2377       transferResourceTracker(*RT.getJITDylib().getDefaultResourceTracker(),
2378                               RT);
2379   });
2380 }
2381
2382 Error ExecutionSession::IL_updateCandidatesFor(
2383     JITDylib &JD, JITDylibLookupFlags JDLookupFlags,
2384     SymbolLookupSet &Candidates, SymbolLookupSet *NonCandidates) {
2385   return Candidates.forEachWithRemoval(
2386       [&](const SymbolStringPtr &Name,
2387           SymbolLookupFlags SymLookupFlags) -> Expected<bool> {
2388         /// Search for the symbol. If not found then continue without
2389         /// removal.
2390         auto SymI = JD.Symbols.find(Name);
2391         if (SymI == JD.Symbols.end())
2392           return false;
2393
2394         // If this is a non-exported symbol and we're matching exported
2395         // symbols only then remove this symbol from the candidates list.
2396         //
2397         // If we're tracking non-candidates then add this to the non-candidate
2398         // list.
2399         if (!SymI->second.getFlags().isExported() &&
2400             JDLookupFlags == JITDylibLookupFlags::MatchExportedSymbolsOnly) {
2401           if (NonCandidates)
2402             NonCandidates->add(Name, SymLookupFlags);
2403           return true;
2404         }
2405
2406         // If we match against a materialization-side-effects only symbol
2407         // then make sure it is weakly-referenced. Otherwise bail out with
2408         // an error.
2409         // FIXME: Use a "materialization-side-effects-only symbols must be
2410         // weakly referenced" specific error here to reduce confusion.
2411         if (SymI->second.getFlags().hasMaterializationSideEffectsOnly() &&
2412             SymLookupFlags != SymbolLookupFlags::WeaklyReferencedSymbol)
2413           return make_error<SymbolsNotFound>(getSymbolStringPool(),
2414                                              SymbolNameVector({Name}));
2415
2416         // If we matched against this symbol but it is in the error state
2417         // then bail out and treat it as a failure to materialize.
2418         if (SymI->second.getFlags().hasError()) {
2419           auto FailedSymbolsMap = std::make_shared<SymbolDependenceMap>();
2420           (*FailedSymbolsMap)[&JD] = {Name};
2421           return make_error<FailedToMaterialize>(getSymbolStringPool(),
2422                                                  std::move(FailedSymbolsMap));
2423         }
2424
2425         // Otherwise this is a match. Remove it from the candidate set.
2426         return true;
2427       });
2428 }
2429
2430 void ExecutionSession::OL_resumeLookupAfterGeneration(
2431     InProgressLookupState &IPLS) {
2432
2433   assert(IPLS.GenState != InProgressLookupState::NotInGenerator &&
2434          "Should not be called for not-in-generator lookups");
2435   IPLS.GenState = InProgressLookupState::NotInGenerator;
2436
2437   LookupState LS;
2438
2439   if (auto DG = IPLS.CurDefGeneratorStack.back().lock()) {
2440     IPLS.CurDefGeneratorStack.pop_back();
2441     std::lock_guard<std::mutex> Lock(DG->M);
2442
2443     // If there are no pending lookups then mark the generator as free and
2444     // return.
2445     if (DG->PendingLookups.empty()) {
2446       DG->InUse = false;
2447       return;
2448     }
2449
2450     // Otherwise resume the next lookup.
2451     LS = std::move(DG->PendingLookups.front());
2452     DG->PendingLookups.pop_front();
2453   }
2454
2455   if (LS.IPLS) {
2456     LS.IPLS->GenState = InProgressLookupState::ResumedForGenerator;
2457     dispatchTask(std::make_unique<LookupTask>(std::move(LS)));
2458   }
2459 }
2460
2461 void ExecutionSession::OL_applyQueryPhase1(
2462     std::unique_ptr<InProgressLookupState> IPLS, Error Err) {
2463
2464   LLVM_DEBUG({
2465     dbgs() << "Entering OL_applyQueryPhase1:\n"
2466            << "  Lookup kind: " << IPLS->K << "\n"
2467            << "  Search order: " << IPLS->SearchOrder
2468            << ", Current index = " << IPLS->CurSearchOrderIndex
2469            << (IPLS->NewJITDylib ? " (entering new JITDylib)" : "") << "\n"
2470            << "  Lookup set: " << IPLS->LookupSet << "\n"
2471            << "  Definition generator candidates: "
2472            << IPLS->DefGeneratorCandidates << "\n"
2473            << "  Definition generator non-candidates: "
2474            << IPLS->DefGeneratorNonCandidates << "\n";
2475   });
2476
2477   if (IPLS->GenState == InProgressLookupState::InGenerator)
2478     OL_resumeLookupAfterGeneration(*IPLS);
2479
2480   assert(IPLS->GenState != InProgressLookupState::InGenerator &&
2481          "Lookup should not be in InGenerator state here");
2482
2483   // FIXME: We should attach the query as we go: This provides a result in a
2484   // single pass in the common case where all symbols have already reached the
2485   // required state. The query could be detached again in the 'fail' method on
2486   // IPLS. Phase 2 would be reduced to collecting and dispatching the MUs.
2487
2488   while (IPLS->CurSearchOrderIndex != IPLS->SearchOrder.size()) {
2489
2490     // If we've been handed an error or received one back from a generator then
2491     // fail the query. We don't need to unlink: At this stage the query hasn't
2492     // actually been lodged.
2493     if (Err)
2494       return IPLS->fail(std::move(Err));
2495
2496     // Get the next JITDylib and lookup flags.
2497     auto &KV = IPLS->SearchOrder[IPLS->CurSearchOrderIndex];
2498     auto &JD = *KV.first;
2499     auto JDLookupFlags = KV.second;
2500
2501     LLVM_DEBUG({
2502       dbgs() << "Visiting \"" << JD.getName() << "\" (" << JDLookupFlags
2503              << ") with lookup set " << IPLS->LookupSet << ":\n";
2504     });
2505
2506     // If we've just reached a new JITDylib then perform some setup.
2507     if (IPLS->NewJITDylib) {
2508       // Add any non-candidates from the last JITDylib (if any) back on to the
2509       // list of definition candidates for this JITDylib, reset definition
2510       // non-candidates to the empty set.
2511       SymbolLookupSet Tmp;
2512       std::swap(IPLS->DefGeneratorNonCandidates, Tmp);
2513       IPLS->DefGeneratorCandidates.append(std::move(Tmp));
2514
2515       LLVM_DEBUG({
2516         dbgs() << "  First time visiting " << JD.getName()
2517                << ", resetting candidate sets and building generator stack\n";
2518       });
2519
2520       // Build the definition generator stack for this JITDylib.
2521       runSessionLocked([&] {
2522         IPLS->CurDefGeneratorStack.reserve(JD.DefGenerators.size());
2523         for (auto &DG : reverse(JD.DefGenerators))
2524           IPLS->CurDefGeneratorStack.push_back(DG);
2525       });
2526
2527       // Flag that we've done our initialization.
2528       IPLS->NewJITDylib = false;
2529     }
2530
2531     // Remove any generation candidates that are already defined (and match) in
2532     // this JITDylib.
2533     runSessionLocked([&] {
2534       // Update the list of candidates (and non-candidates) for definition
2535       // generation.
2536       LLVM_DEBUG(dbgs() << "  Updating candidate set...\n");
2537       Err = IL_updateCandidatesFor(
2538           JD, JDLookupFlags, IPLS->DefGeneratorCandidates,
2539           JD.DefGenerators.empty() ? nullptr
2540                                    : &IPLS->DefGeneratorNonCandidates);
2541       LLVM_DEBUG({
2542         dbgs() << "    Remaining candidates = " << IPLS->DefGeneratorCandidates
2543                << "\n";
2544       });
2545
2546       // If this lookup was resumed after auto-suspension but all candidates
2547       // have already been generated (by some previous call to the generator)
2548       // treat the lookup as if it had completed generation.
2549       if (IPLS->GenState == InProgressLookupState::ResumedForGenerator &&
2550           IPLS->DefGeneratorCandidates.empty())
2551         OL_resumeLookupAfterGeneration(*IPLS);
2552     });
2553
2554     // If we encountered an error while filtering generation candidates then
2555     // bail out.
2556     if (Err)
2557       return IPLS->fail(std::move(Err));
2558
2559     /// Apply any definition generators on the stack.
2560     LLVM_DEBUG({
2561       if (IPLS->CurDefGeneratorStack.empty())
2562         LLVM_DEBUG(dbgs() << "  No generators to run for this JITDylib.\n");
2563       else if (IPLS->DefGeneratorCandidates.empty())
2564         LLVM_DEBUG(dbgs() << "  No candidates to generate.\n");
2565       else
2566         dbgs() << "  Running " << IPLS->CurDefGeneratorStack.size()
2567                << " remaining generators for "
2568                << IPLS->DefGeneratorCandidates.size() << " candidates\n";
2569     });
2570     while (!IPLS->CurDefGeneratorStack.empty() &&
2571            !IPLS->DefGeneratorCandidates.empty()) {
2572       auto DG = IPLS->CurDefGeneratorStack.back().lock();
2573
2574       if (!DG)
2575         return IPLS->fail(make_error<StringError>(
2576             "DefinitionGenerator removed while lookup in progress",
2577             inconvertibleErrorCode()));
2578
2579       // At this point the lookup is in either the NotInGenerator state, or in
2580       // the ResumedForGenerator state.
2581       // If this lookup is in the NotInGenerator state then check whether the
2582       // generator is in use. If the generator is not in use then move the
2583       // lookup to the InGenerator state and continue. If the generator is
2584       // already in use then just add this lookup to the pending lookups list
2585       // and bail out.
2586       // If this lookup is in the ResumedForGenerator state then just move it
2587       // to InGenerator and continue.
2588       if (IPLS->GenState == InProgressLookupState::NotInGenerator) {
2589         std::lock_guard<std::mutex> Lock(DG->M);
2590         if (DG->InUse) {
2591           DG->PendingLookups.push_back(std::move(IPLS));
2592           return;
2593         }
2594         DG->InUse = true;
2595       }
2596
2597       IPLS->GenState = InProgressLookupState::InGenerator;
2598
2599       auto K = IPLS->K;
2600       auto &LookupSet = IPLS->DefGeneratorCandidates;
2601
2602       // Run the generator. If the generator takes ownership of QA then this
2603       // will break the loop.
2604       {
2605         LLVM_DEBUG(dbgs() << "  Attempting to generate " << LookupSet << "\n");
2606         LookupState LS(std::move(IPLS));
2607         Err = DG->tryToGenerate(LS, K, JD, JDLookupFlags, LookupSet);
2608         IPLS = std::move(LS.IPLS);
2609       }
2610
2611       // If the lookup returned then pop the generator stack and unblock the
2612       // next lookup on this generator (if any).
2613       if (IPLS)
2614         OL_resumeLookupAfterGeneration(*IPLS);
2615
2616       // If there was an error then fail the query.
2617       if (Err) {
2618         LLVM_DEBUG({
2619           dbgs() << "  Error attempting to generate " << LookupSet << "\n";
2620         });
2621         assert(IPLS && "LS cannot be retained if error is returned");
2622         return IPLS->fail(std::move(Err));
2623       }
2624
2625       // Otherwise if QA was captured then break the loop.
2626       if (!IPLS) {
2627         LLVM_DEBUG(
2628             { dbgs() << "  LookupState captured. Exiting phase1 for now.\n"; });
2629         return;
2630       }
2631
2632       // Otherwise if we're continuing around the loop then update candidates
2633       // for the next round.
2634       runSessionLocked([&] {
2635         LLVM_DEBUG(dbgs() << "  Updating candidate set post-generation\n");
2636         Err = IL_updateCandidatesFor(
2637             JD, JDLookupFlags, IPLS->DefGeneratorCandidates,
2638             JD.DefGenerators.empty() ? nullptr
2639                                      : &IPLS->DefGeneratorNonCandidates);
2640       });
2641
2642       // If updating candidates failed then fail the query.
2643       if (Err) {
2644         LLVM_DEBUG(dbgs() << "  Error encountered while updating candidates\n");
2645         return IPLS->fail(std::move(Err));
2646       }
2647     }
2648
2649     if (IPLS->DefGeneratorCandidates.empty() &&
2650         IPLS->DefGeneratorNonCandidates.empty()) {
2651       // Early out if there are no remaining symbols.
2652       LLVM_DEBUG(dbgs() << "All symbols matched.\n");
2653       IPLS->CurSearchOrderIndex = IPLS->SearchOrder.size();
2654       break;
2655     } else {
2656       // If we get here then we've moved on to the next JITDylib with candidates
2657       // remaining.
2658       LLVM_DEBUG(dbgs() << "Phase 1 moving to next JITDylib.\n");
2659       ++IPLS->CurSearchOrderIndex;
2660       IPLS->NewJITDylib = true;
2661     }
2662   }
2663
2664   // Remove any weakly referenced candidates that could not be found/generated.
2665   IPLS->DefGeneratorCandidates.remove_if(
2666       [](const SymbolStringPtr &Name, SymbolLookupFlags SymLookupFlags) {
2667         return SymLookupFlags == SymbolLookupFlags::WeaklyReferencedSymbol;
2668       });
2669
2670   // If we get here then we've finished searching all JITDylibs.
2671   // If we matched all symbols then move to phase 2, otherwise fail the query
2672   // with a SymbolsNotFound error.
2673   if (IPLS->DefGeneratorCandidates.empty()) {
2674     LLVM_DEBUG(dbgs() << "Phase 1 succeeded.\n");
2675     IPLS->complete(std::move(IPLS));
2676   } else {
2677     LLVM_DEBUG(dbgs() << "Phase 1 failed with unresolved symbols.\n");
2678     IPLS->fail(make_error<SymbolsNotFound>(
2679         getSymbolStringPool(), IPLS->DefGeneratorCandidates.getSymbolNames()));
2680   }
2681 }
2682
2683 void ExecutionSession::OL_completeLookup(
2684     std::unique_ptr<InProgressLookupState> IPLS,
2685     std::shared_ptr<AsynchronousSymbolQuery> Q,
2686     RegisterDependenciesFunction RegisterDependencies) {
2687
2688   LLVM_DEBUG({
2689     dbgs() << "Entering OL_completeLookup:\n"
2690            << "  Lookup kind: " << IPLS->K << "\n"
2691            << "  Search order: " << IPLS->SearchOrder
2692            << ", Current index = " << IPLS->CurSearchOrderIndex
2693            << (IPLS->NewJITDylib ? " (entering new JITDylib)" : "") << "\n"
2694            << "  Lookup set: " << IPLS->LookupSet << "\n"
2695            << "  Definition generator candidates: "
2696            << IPLS->DefGeneratorCandidates << "\n"
2697            << "  Definition generator non-candidates: "
2698            << IPLS->DefGeneratorNonCandidates << "\n";
2699   });
2700
2701   bool QueryComplete = false;
2702   DenseMap<JITDylib *, JITDylib::UnmaterializedInfosList> CollectedUMIs;
2703
2704   auto LodgingErr = runSessionLocked([&]() -> Error {
2705     for (auto &KV : IPLS->SearchOrder) {
2706       auto &JD = *KV.first;
2707       auto JDLookupFlags = KV.second;
2708       LLVM_DEBUG({
2709         dbgs() << "Visiting \"" << JD.getName() << "\" (" << JDLookupFlags
2710                << ") with lookup set " << IPLS->LookupSet << ":\n";
2711       });
2712
2713       auto Err = IPLS->LookupSet.forEachWithRemoval(
2714           [&](const SymbolStringPtr &Name,
2715               SymbolLookupFlags SymLookupFlags) -> Expected<bool> {
2716             LLVM_DEBUG({
2717               dbgs() << "  Attempting to match \"" << Name << "\" ("
2718                      << SymLookupFlags << ")... ";
2719             });
2720
2721             /// Search for the symbol. If not found then continue without
2722             /// removal.
2723             auto SymI = JD.Symbols.find(Name);
2724             if (SymI == JD.Symbols.end()) {
2725               LLVM_DEBUG(dbgs() << "skipping: not present\n");
2726               return false;
2727             }
2728
2729             // If this is a non-exported symbol and we're matching exported
2730             // symbols only then skip this symbol without removal.
2731             if (!SymI->second.getFlags().isExported() &&
2732                 JDLookupFlags ==
2733                     JITDylibLookupFlags::MatchExportedSymbolsOnly) {
2734               LLVM_DEBUG(dbgs() << "skipping: not exported\n");
2735               return false;
2736             }
2737
2738             // If we match against a materialization-side-effects only symbol
2739             // then make sure it is weakly-referenced. Otherwise bail out with
2740             // an error.
2741             // FIXME: Use a "materialization-side-effects-only symbols must be
2742             // weakly referenced" specific error here to reduce confusion.
2743             if (SymI->second.getFlags().hasMaterializationSideEffectsOnly() &&
2744                 SymLookupFlags != SymbolLookupFlags::WeaklyReferencedSymbol) {
2745               LLVM_DEBUG({
2746                 dbgs() << "error: "
2747                           "required, but symbol is has-side-effects-only\n";
2748               });
2749               return make_error<SymbolsNotFound>(getSymbolStringPool(),
2750                                                  SymbolNameVector({Name}));
2751             }
2752
2753             // If we matched against this symbol but it is in the error state
2754             // then bail out and treat it as a failure to materialize.
2755             if (SymI->second.getFlags().hasError()) {
2756               LLVM_DEBUG(dbgs() << "error: symbol is in error state\n");
2757               auto FailedSymbolsMap = std::make_shared<SymbolDependenceMap>();
2758               (*FailedSymbolsMap)[&JD] = {Name};
2759               return make_error<FailedToMaterialize>(
2760                   getSymbolStringPool(), std::move(FailedSymbolsMap));
2761             }
2762
2763             // Otherwise this is a match.
2764
2765             // If this symbol is already in the required state then notify the
2766             // query, remove the symbol and continue.
2767             if (SymI->second.getState() >= Q->getRequiredState()) {
2768               LLVM_DEBUG(dbgs()
2769                          << "matched, symbol already in required state\n");
2770               Q->notifySymbolMetRequiredState(Name, SymI->second.getSymbol());
2771               return true;
2772             }
2773
2774             // Otherwise this symbol does not yet meet the required state. Check
2775             // whether it has a materializer attached, and if so prepare to run
2776             // it.
2777             if (SymI->second.hasMaterializerAttached()) {
2778               assert(SymI->second.getAddress() == ExecutorAddr() &&
2779                      "Symbol not resolved but already has address?");
2780               auto UMII = JD.UnmaterializedInfos.find(Name);
2781               assert(UMII != JD.UnmaterializedInfos.end() &&
2782                      "Lazy symbol should have UnmaterializedInfo");
2783
2784               auto UMI = UMII->second;
2785               assert(UMI->MU && "Materializer should not be null");
2786               assert(UMI->RT && "Tracker should not be null");
2787               LLVM_DEBUG({
2788                 dbgs() << "matched, preparing to dispatch MU@" << UMI->MU.get()
2789                        << " (" << UMI->MU->getName() << ")\n";
2790               });
2791
2792               // Move all symbols associated with this MaterializationUnit into
2793               // materializing state.
2794               for (auto &KV : UMI->MU->getSymbols()) {
2795                 auto SymK = JD.Symbols.find(KV.first);
2796                 assert(SymK != JD.Symbols.end() &&
2797                        "No entry for symbol covered by MaterializationUnit");
2798                 SymK->second.setMaterializerAttached(false);
2799                 SymK->second.setState(SymbolState::Materializing);
2800                 JD.UnmaterializedInfos.erase(KV.first);
2801               }
2802
2803               // Add MU to the list of MaterializationUnits to be materialized.
2804               CollectedUMIs[&JD].push_back(std::move(UMI));
2805             } else
2806               LLVM_DEBUG(dbgs() << "matched, registering query");
2807
2808             // Add the query to the PendingQueries list and continue, deleting
2809             // the element from the lookup set.
2810             assert(SymI->second.getState() != SymbolState::NeverSearched &&
2811                    SymI->second.getState() != SymbolState::Ready &&
2812                    "By this line the symbol should be materializing");
2813             auto &MI = JD.MaterializingInfos[Name];
2814             MI.addQuery(Q);
2815             Q->addQueryDependence(JD, Name);
2816
2817             return true;
2818           });
2819
2820       // Handle failure.
2821       if (Err) {
2822
2823         LLVM_DEBUG({
2824           dbgs() << "Lookup failed. Detaching query and replacing MUs.\n";
2825         });
2826
2827         // Detach the query.
2828         Q->detach();
2829
2830         // Replace the MUs.
2831         for (auto &KV : CollectedUMIs) {
2832           auto &JD = *KV.first;
2833           for (auto &UMI : KV.second)
2834             for (auto &KV2 : UMI->MU->getSymbols()) {
2835               assert(!JD.UnmaterializedInfos.count(KV2.first) &&
2836                      "Unexpected materializer in map");
2837               auto SymI = JD.Symbols.find(KV2.first);
2838               assert(SymI != JD.Symbols.end() && "Missing symbol entry");
2839               assert(SymI->second.getState() == SymbolState::Materializing &&
2840                      "Can not replace symbol that is not materializing");
2841               assert(!SymI->second.hasMaterializerAttached() &&
2842                      "MaterializerAttached flag should not be set");
2843               SymI->second.setMaterializerAttached(true);
2844               JD.UnmaterializedInfos[KV2.first] = UMI;
2845             }
2846         }
2847
2848         return Err;
2849       }
2850     }
2851
2852     LLVM_DEBUG(dbgs() << "Stripping unmatched weakly-referenced symbols\n");
2853     IPLS->LookupSet.forEachWithRemoval(
2854         [&](const SymbolStringPtr &Name, SymbolLookupFlags SymLookupFlags) {
2855           if (SymLookupFlags == SymbolLookupFlags::WeaklyReferencedSymbol) {
2856             Q->dropSymbol(Name);
2857             return true;
2858           } else
2859             return false;
2860         });
2861
2862     if (!IPLS->LookupSet.empty()) {
2863       LLVM_DEBUG(dbgs() << "Failing due to unresolved symbols\n");
2864       return make_error<SymbolsNotFound>(getSymbolStringPool(),
2865                                          IPLS->LookupSet.getSymbolNames());
2866     }
2867
2868     // Record whether the query completed.
2869     QueryComplete = Q->isComplete();
2870
2871     LLVM_DEBUG({
2872       dbgs() << "Query successfully "
2873              << (QueryComplete ? "completed" : "lodged") << "\n";
2874     });
2875
2876     // Move the collected MUs to the OutstandingMUs list.
2877     if (!CollectedUMIs.empty()) {
2878       std::lock_guard<std::recursive_mutex> Lock(OutstandingMUsMutex);
2879
2880       LLVM_DEBUG(dbgs() << "Adding MUs to dispatch:\n");
2881       for (auto &KV : CollectedUMIs) {
2882         LLVM_DEBUG({
2883           auto &JD = *KV.first;
2884           dbgs() << "  For " << JD.getName() << ": Adding " << KV.second.size()
2885                  << " MUs.\n";
2886         });
2887         for (auto &UMI : KV.second) {
2888           auto MR = createMaterializationResponsibility(
2889               *UMI->RT, std::move(UMI->MU->SymbolFlags),
2890               std::move(UMI->MU->InitSymbol));
2891           OutstandingMUs.push_back(
2892               std::make_pair(std::move(UMI->MU), std::move(MR)));
2893         }
2894       }
2895     } else
2896       LLVM_DEBUG(dbgs() << "No MUs to dispatch.\n");
2897
2898     if (RegisterDependencies && !Q->QueryRegistrations.empty()) {
2899       LLVM_DEBUG(dbgs() << "Registering dependencies\n");
2900       RegisterDependencies(Q->QueryRegistrations);
2901     } else
2902       LLVM_DEBUG(dbgs() << "No dependencies to register\n");
2903
2904     return Error::success();
2905   });
2906
2907   if (LodgingErr) {
2908     LLVM_DEBUG(dbgs() << "Failing query\n");
2909     Q->detach();
2910     Q->handleFailed(std::move(LodgingErr));
2911     return;
2912   }
2913
2914   if (QueryComplete) {
2915     LLVM_DEBUG(dbgs() << "Completing query\n");
2916     Q->handleComplete(*this);
2917   }
2918
2919   dispatchOutstandingMUs();
2920 }
2921
2922 void ExecutionSession::OL_completeLookupFlags(
2923     std::unique_ptr<InProgressLookupState> IPLS,
2924     unique_function<void(Expected<SymbolFlagsMap>)> OnComplete) {
2925
2926   auto Result = runSessionLocked([&]() -> Expected<SymbolFlagsMap> {
2927     LLVM_DEBUG({
2928       dbgs() << "Entering OL_completeLookupFlags:\n"
2929              << "  Lookup kind: " << IPLS->K << "\n"
2930              << "  Search order: " << IPLS->SearchOrder
2931              << ", Current index = " << IPLS->CurSearchOrderIndex
2932              << (IPLS->NewJITDylib ? " (entering new JITDylib)" : "") << "\n"
2933              << "  Lookup set: " << IPLS->LookupSet << "\n"
2934              << "  Definition generator candidates: "
2935              << IPLS->DefGeneratorCandidates << "\n"
2936              << "  Definition generator non-candidates: "
2937              << IPLS->DefGeneratorNonCandidates << "\n";
2938     });
2939
2940     SymbolFlagsMap Result;
2941
2942     // Attempt to find flags for each symbol.
2943     for (auto &KV : IPLS->SearchOrder) {
2944       auto &JD = *KV.first;
2945       auto JDLookupFlags = KV.second;
2946       LLVM_DEBUG({
2947         dbgs() << "Visiting \"" << JD.getName() << "\" (" << JDLookupFlags
2948                << ") with lookup set " << IPLS->LookupSet << ":\n";
2949       });
2950
2951       IPLS->LookupSet.forEachWithRemoval([&](const SymbolStringPtr &Name,
2952                                              SymbolLookupFlags SymLookupFlags) {
2953         LLVM_DEBUG({
2954           dbgs() << "  Attempting to match \"" << Name << "\" ("
2955                  << SymLookupFlags << ")... ";
2956         });
2957
2958         // Search for the symbol. If not found then continue without removing
2959         // from the lookup set.
2960         auto SymI = JD.Symbols.find(Name);
2961         if (SymI == JD.Symbols.end()) {
2962           LLVM_DEBUG(dbgs() << "skipping: not present\n");
2963           return false;
2964         }
2965
2966         // If this is a non-exported symbol then it doesn't match. Skip it.
2967         if (!SymI->second.getFlags().isExported() &&
2968             JDLookupFlags == JITDylibLookupFlags::MatchExportedSymbolsOnly) {
2969           LLVM_DEBUG(dbgs() << "skipping: not exported\n");
2970           return false;
2971         }
2972
2973         LLVM_DEBUG({
2974           dbgs() << "matched, \"" << Name << "\" -> " << SymI->second.getFlags()
2975                  << "\n";
2976         });
2977         Result[Name] = SymI->second.getFlags();
2978         return true;
2979       });
2980     }
2981
2982     // Remove any weakly referenced symbols that haven't been resolved.
2983     IPLS->LookupSet.remove_if(
2984         [](const SymbolStringPtr &Name, SymbolLookupFlags SymLookupFlags) {
2985           return SymLookupFlags == SymbolLookupFlags::WeaklyReferencedSymbol;
2986         });
2987
2988     if (!IPLS->LookupSet.empty()) {
2989       LLVM_DEBUG(dbgs() << "Failing due to unresolved symbols\n");
2990       return make_error<SymbolsNotFound>(getSymbolStringPool(),
2991                                          IPLS->LookupSet.getSymbolNames());
2992     }
2993
2994     LLVM_DEBUG(dbgs() << "Succeded, result = " << Result << "\n");
2995     return Result;
2996   });
2997
2998   // Run the callback on the result.
2999   LLVM_DEBUG(dbgs() << "Sending result to handler.\n");
3000   OnComplete(std::move(Result));
3001 }
3002
3003 void ExecutionSession::OL_destroyMaterializationResponsibility(
3004     MaterializationResponsibility &MR) {
3005
3006   assert(MR.SymbolFlags.empty() &&
3007          "All symbols should have been explicitly materialized or failed");
3008   MR.JD.unlinkMaterializationResponsibility(MR);
3009 }
3010
3011 SymbolNameSet ExecutionSession::OL_getRequestedSymbols(
3012     const MaterializationResponsibility &MR) {
3013   return MR.JD.getRequestedSymbols(MR.SymbolFlags);
3014 }
3015
3016 Error ExecutionSession::OL_notifyResolved(MaterializationResponsibility &MR,
3017                                           const SymbolMap &Symbols) {
3018   LLVM_DEBUG({
3019     dbgs() << "In " << MR.JD.getName() << " resolving " << Symbols << "\n";
3020   });
3021 #ifndef NDEBUG
3022   for (auto &KV : Symbols) {
3023     auto I = MR.SymbolFlags.find(KV.first);
3024     assert(I != MR.SymbolFlags.end() &&
3025            "Resolving symbol outside this responsibility set");
3026     assert(!I->second.hasMaterializationSideEffectsOnly() &&
3027            "Can't resolve materialization-side-effects-only symbol");
3028     assert((KV.second.getFlags() & ~JITSymbolFlags::Common) ==
3029                (I->second & ~JITSymbolFlags::Common) &&
3030            "Resolving symbol with incorrect flags");
3031   }
3032 #endif
3033
3034   return MR.JD.resolve(MR, Symbols);
3035 }
3036
3037 Error ExecutionSession::OL_notifyEmitted(MaterializationResponsibility &MR) {
3038   LLVM_DEBUG({
3039     dbgs() << "In " << MR.JD.getName() << " emitting " << MR.SymbolFlags
3040            << "\n";
3041   });
3042
3043   if (auto Err = MR.JD.emit(MR, MR.SymbolFlags))
3044     return Err;
3045
3046   MR.SymbolFlags.clear();
3047   return Error::success();
3048 }
3049
3050 Error ExecutionSession::OL_defineMaterializing(
3051     MaterializationResponsibility &MR, SymbolFlagsMap NewSymbolFlags) {
3052
3053   LLVM_DEBUG({
3054     dbgs() << "In " << MR.JD.getName() << " defining materializing symbols "
3055            << NewSymbolFlags << "\n";
3056   });
3057   if (auto AcceptedDefs =
3058           MR.JD.defineMaterializing(MR, std::move(NewSymbolFlags))) {
3059     // Add all newly accepted symbols to this responsibility object.
3060     for (auto &KV : *AcceptedDefs)
3061       MR.SymbolFlags.insert(KV);
3062     return Error::success();
3063   } else
3064     return AcceptedDefs.takeError();
3065 }
3066
3067 void ExecutionSession::OL_notifyFailed(MaterializationResponsibility &MR) {
3068
3069   LLVM_DEBUG({
3070     dbgs() << "In " << MR.JD.getName() << " failing materialization for "
3071            << MR.SymbolFlags << "\n";
3072   });
3073
3074   JITDylib::FailedSymbolsWorklist Worklist;
3075
3076   for (auto &KV : MR.SymbolFlags)
3077     Worklist.push_back(std::make_pair(&MR.JD, KV.first));
3078   MR.SymbolFlags.clear();
3079
3080   if (Worklist.empty())
3081     return;
3082
3083   JITDylib::AsynchronousSymbolQuerySet FailedQueries;
3084   std::shared_ptr<SymbolDependenceMap> FailedSymbols;
3085
3086   runSessionLocked([&]() {
3087     // If the tracker is defunct then there's nothing to do here.
3088     if (MR.RT->isDefunct())
3089       return;
3090
3091     std::tie(FailedQueries, FailedSymbols) =
3092         JITDylib::failSymbols(std::move(Worklist));
3093   });
3094
3095   for (auto &Q : FailedQueries)
3096     Q->handleFailed(
3097         make_error<FailedToMaterialize>(getSymbolStringPool(), FailedSymbols));
3098 }
3099
3100 Error ExecutionSession::OL_replace(MaterializationResponsibility &MR,
3101                                    std::unique_ptr<MaterializationUnit> MU) {
3102   for (auto &KV : MU->getSymbols()) {
3103     assert(MR.SymbolFlags.count(KV.first) &&
3104            "Replacing definition outside this responsibility set");
3105     MR.SymbolFlags.erase(KV.first);
3106   }
3107
3108   if (MU->getInitializerSymbol() == MR.InitSymbol)
3109     MR.InitSymbol = nullptr;
3110
3111   LLVM_DEBUG(MR.JD.getExecutionSession().runSessionLocked([&]() {
3112     dbgs() << "In " << MR.JD.getName() << " replacing symbols with " << *MU
3113            << "\n";
3114   }););
3115
3116   return MR.JD.replace(MR, std::move(MU));
3117 }
3118
3119 Expected<std::unique_ptr<MaterializationResponsibility>>
3120 ExecutionSession::OL_delegate(MaterializationResponsibility &MR,
3121                               const SymbolNameSet &Symbols) {
3122
3123   SymbolStringPtr DelegatedInitSymbol;
3124   SymbolFlagsMap DelegatedFlags;
3125
3126   for (auto &Name : Symbols) {
3127     auto I = MR.SymbolFlags.find(Name);
3128     assert(I != MR.SymbolFlags.end() &&
3129            "Symbol is not tracked by this MaterializationResponsibility "
3130            "instance");
3131
3132     DelegatedFlags[Name] = std::move(I->second);
3133     if (Name == MR.InitSymbol)
3134       std::swap(MR.InitSymbol, DelegatedInitSymbol);
3135
3136     MR.SymbolFlags.erase(I);
3137   }
3138
3139   return MR.JD.delegate(MR, std::move(DelegatedFlags),
3140                         std::move(DelegatedInitSymbol));
3141 }
3142
3143 void ExecutionSession::OL_addDependencies(
3144     MaterializationResponsibility &MR, const SymbolStringPtr &Name,
3145     const SymbolDependenceMap &Dependencies) {
3146   LLVM_DEBUG({
3147     dbgs() << "Adding dependencies for " << Name << ": " << Dependencies
3148            << "\n";
3149   });
3150   assert(MR.SymbolFlags.count(Name) &&
3151          "Symbol not covered by this MaterializationResponsibility instance");
3152   MR.JD.addDependencies(Name, Dependencies);
3153 }
3154
3155 void ExecutionSession::OL_addDependenciesForAll(
3156     MaterializationResponsibility &MR,
3157     const SymbolDependenceMap &Dependencies) {
3158   LLVM_DEBUG({
3159     dbgs() << "Adding dependencies for all symbols in " << MR.SymbolFlags << ": "
3160            << Dependencies << "\n";
3161   });
3162   for (auto &KV : MR.SymbolFlags)
3163     MR.JD.addDependencies(KV.first, Dependencies);
3164 }
3165
3166 #ifndef NDEBUG
3167 void ExecutionSession::dumpDispatchInfo(Task &T) {
3168   runSessionLocked([&]() {
3169     dbgs() << "Dispatching: ";
3170     T.printDescription(dbgs());
3171     dbgs() << "\n";
3172   });
3173 }
3174 #endif // NDEBUG
3175
3176 } // End namespace orc.
3177 } // End namespace llvm.