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