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