llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp

   1 //===--------- JITLinkGeneric.cpp - Generic JIT linker utilities ----------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Generic JITLinker utility class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "JITLinkGeneric.h"
  14
  15 #include "llvm/Support/BinaryStreamReader.h"
  16 #include "llvm/Support/MemoryBuffer.h"
  17
  18 #define DEBUG_TYPE "jitlink"
  19
  20 namespace llvm {
  21 namespace jitlink {
  22
  23 JITLinkerBase::~JITLinkerBase() = default;
  24
  25 void JITLinkerBase::linkPhase1(std::unique_ptr<JITLinkerBase> Self) {
  26
  27   LLVM_DEBUG({
  28     dbgs() << "Starting link phase 1 for graph " << G->getName() << "\n";
  29   });
  30
  31   // Prune and optimize the graph.
  32   if (auto Err = runPasses(Passes.PrePrunePasses))
  33     return Ctx->notifyFailed(std::move(Err));
  34
  35   LLVM_DEBUG({
  36     dbgs() << "Link graph \"" << G->getName() << "\" pre-pruning:\n";
  37     G->dump(dbgs());
  38   });
  39
  40   prune(*G);
  41
  42   LLVM_DEBUG({
  43     dbgs() << "Link graph \"" << G->getName() << "\" post-pruning:\n";
  44     G->dump(dbgs());
  45   });
  46
  47   // Run post-pruning passes.
  48   if (auto Err = runPasses(Passes.PostPrunePasses))
  49     return Ctx->notifyFailed(std::move(Err));
  50
  51   // Skip straight to phase 2 if the graph is empty with no associated actions.
  52   if (G->allocActions().empty() && llvm::all_of(G->sections(), [](Section &S) {
  53         return S.getMemLifetime() == orc::MemLifetime::NoAlloc;
  54       })) {
  55     linkPhase2(std::move(Self), nullptr);
  56     return;
  57   }
  58
  59   Ctx->getMemoryManager().allocate(
  60       Ctx->getJITLinkDylib(), *G,
  61       [S = std::move(Self)](AllocResult AR) mutable {
  62         // FIXME: Once MSVC implements c++17 order of evaluation rules for calls
  63         // this can be simplified to
  64         //          S->linkPhase2(std::move(S), std::move(AR));
  65         auto *TmpSelf = S.get();
  66         TmpSelf->linkPhase2(std::move(S), std::move(AR));
  67       });
  68 }
  69
  70 void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self,
  71                                AllocResult AR) {
  72
  73   if (AR)
  74     Alloc = std::move(*AR);
  75   else
  76     return Ctx->notifyFailed(AR.takeError());
  77
  78   LLVM_DEBUG({
  79     dbgs() << "Link graph \"" << G->getName()
  80            << "\" before post-allocation passes:\n";
  81     G->dump(dbgs());
  82   });
  83
  84   // Run post-allocation passes.
  85   if (auto Err = runPasses(Passes.PostAllocationPasses))
  86     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
  87
  88   // Notify client that the defined symbols have been assigned addresses.
  89   LLVM_DEBUG(dbgs() << "Resolving symbols defined in " << G->getName() << "\n");
  90
  91   if (auto Err = Ctx->notifyResolved(*G))
  92     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
  93
  94   auto ExternalSymbols = getExternalSymbolNames();
  95
  96   // If there are no external symbols then proceed immediately with phase 3.
  97   if (ExternalSymbols.empty()) {
  98     LLVM_DEBUG({
  99       dbgs() << "No external symbols for " << G->getName()
 100              << ". Proceeding immediately with link phase 3.\n";
 101     });
 102     // FIXME: Once MSVC implements c++17 order of evaluation rules for calls
 103     // this can be simplified. See below.
 104     auto &TmpSelf = *Self;
 105     TmpSelf.linkPhase3(std::move(Self), AsyncLookupResult());
 106     return;
 107   }
 108
 109   // Otherwise look up the externals.
 110   LLVM_DEBUG({
 111     dbgs() << "Issuing lookup for external symbols for " << G->getName()
 112            << " (may trigger materialization/linking of other graphs)...\n";
 113   });
 114
 115   // We're about to hand off ownership of ourself to the continuation. Grab a
 116   // pointer to the context so that we can call it to initiate the lookup.
 117   //
 118   // FIXME: Once MSVC implements c++17 order of evaluation rules for calls this
 119   // can be simplified to:
 120   //
 121   // Ctx->lookup(std::move(UnresolvedExternals),
 122   //             [Self=std::move(Self)](Expected<AsyncLookupResult> Result) {
 123   //               Self->linkPhase3(std::move(Self), std::move(Result));
 124   //             });
 125   Ctx->lookup(std::move(ExternalSymbols),
 126               createLookupContinuation(
 127                   [S = std::move(Self)](
 128                       Expected<AsyncLookupResult> LookupResult) mutable {
 129                     auto &TmpSelf = *S;
 130                     TmpSelf.linkPhase3(std::move(S), std::move(LookupResult));
 131                   }));
 132 }
 133
 134 void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self,
 135                                Expected<AsyncLookupResult> LR) {
 136
 137   LLVM_DEBUG({
 138     dbgs() << "Starting link phase 3 for graph " << G->getName() << "\n";
 139   });
 140
 141   // If the lookup failed, bail out.
 142   if (!LR)
 143     return abandonAllocAndBailOut(std::move(Self), LR.takeError());
 144
 145   // Assign addresses to external addressables.
 146   applyLookupResult(*LR);
 147
 148   LLVM_DEBUG({
 149     dbgs() << "Link graph \"" << G->getName()
 150            << "\" before pre-fixup passes:\n";
 151     G->dump(dbgs());
 152   });
 153
 154   if (auto Err = runPasses(Passes.PreFixupPasses))
 155     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
 156
 157   LLVM_DEBUG({
 158     dbgs() << "Link graph \"" << G->getName() << "\" before copy-and-fixup:\n";
 159     G->dump(dbgs());
 160   });
 161
 162   // Fix up block content.
 163   if (auto Err = fixUpBlocks(*G))
 164     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
 165
 166   LLVM_DEBUG({
 167     dbgs() << "Link graph \"" << G->getName() << "\" after copy-and-fixup:\n";
 168     G->dump(dbgs());
 169   });
 170
 171   if (auto Err = runPasses(Passes.PostFixupPasses))
 172     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
 173
 174   // Skip straight to phase 4 if the graph has no allocation.
 175   if (!Alloc) {
 176     linkPhase4(std::move(Self), JITLinkMemoryManager::FinalizedAlloc{});
 177     return;
 178   }
 179
 180   Alloc->finalize([S = std::move(Self)](FinalizeResult FR) mutable {
 181     // FIXME: Once MSVC implements c++17 order of evaluation rules for calls
 182     // this can be simplified to
 183     //          S->linkPhase2(std::move(S), std::move(AR));
 184     auto *TmpSelf = S.get();
 185     TmpSelf->linkPhase4(std::move(S), std::move(FR));
 186   });
 187 }
 188
 189 void JITLinkerBase::linkPhase4(std::unique_ptr<JITLinkerBase> Self,
 190                                FinalizeResult FR) {
 191
 192   LLVM_DEBUG({
 193     dbgs() << "Starting link phase 4 for graph " << G->getName() << "\n";
 194   });
 195
 196   if (!FR)
 197     return Ctx->notifyFailed(FR.takeError());
 198
 199   Ctx->notifyFinalized(std::move(*FR));
 200
 201   LLVM_DEBUG({ dbgs() << "Link of graph " << G->getName() << " complete\n"; });
 202 }
 203
 204 Error JITLinkerBase::runPasses(LinkGraphPassList &Passes) {
 205   for (auto &P : Passes)
 206     if (auto Err = P(*G))
 207       return Err;
 208   return Error::success();
 209 }
 210
 211 JITLinkContext::LookupMap JITLinkerBase::getExternalSymbolNames() const {
 212   // Identify unresolved external symbols.
 213   JITLinkContext::LookupMap UnresolvedExternals;
 214   for (auto *Sym : G->external_symbols()) {
 215     assert(!Sym->getAddress() &&
 216            "External has already been assigned an address");
 217     assert(Sym->getName() != StringRef() && Sym->getName() != "" &&
 218            "Externals must be named");
 219     SymbolLookupFlags LookupFlags =
 220         Sym->isWeaklyReferenced() ? SymbolLookupFlags::WeaklyReferencedSymbol
 221                                   : SymbolLookupFlags::RequiredSymbol;
 222     UnresolvedExternals[Sym->getName()] = LookupFlags;
 223   }
 224   return UnresolvedExternals;
 225 }
 226
 227 void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
 228   for (auto *Sym : G->external_symbols()) {
 229     assert(Sym->getOffset() == 0 &&
 230            "External symbol is not at the start of its addressable block");
 231     assert(!Sym->getAddress() && "Symbol already resolved");
 232     assert(!Sym->isDefined() && "Symbol being resolved is already defined");
 233     auto ResultI = Result.find(Sym->getName());
 234     if (ResultI != Result.end()) {
 235       Sym->getAddressable().setAddress(ResultI->second.getAddress());
 236       Sym->setLinkage(ResultI->second.getFlags().isWeak() ? Linkage::Weak
 237                                                           : Linkage::Strong);
 238       Sym->setScope(ResultI->second.getFlags().isExported() ? Scope::Default
 239                                                             : Scope::Hidden);
 240     } else
 241       assert(Sym->isWeaklyReferenced() &&
 242              "Failed to resolve non-weak reference");
 243   }
 244
 245   LLVM_DEBUG({
 246     dbgs() << "Externals after applying lookup result:\n";
 247     for (auto *Sym : G->external_symbols()) {
 248       dbgs() << "  " << Sym->getName() << ": "
 249              << formatv("{0:x16}", Sym->getAddress().getValue());
 250       switch (Sym->getLinkage()) {
 251       case Linkage::Strong:
 252         break;
 253       case Linkage::Weak:
 254         dbgs() << " (weak)";
 255         break;
 256       }
 257       switch (Sym->getScope()) {
 258       case Scope::Local:
 259         llvm_unreachable("External symbol should not have local linkage");
 260       case Scope::Hidden:
 261         break;
 262       case Scope::Default:
 263         dbgs() << " (exported)";
 264         break;
 265       }
 266       dbgs() << "\n";
 267     }
 268   });
 269 }
 270
 271 void JITLinkerBase::abandonAllocAndBailOut(std::unique_ptr<JITLinkerBase> Self,
 272                                            Error Err) {
 273   assert(Err && "Should not be bailing out on success value");
 274   assert(Alloc && "can not call abandonAllocAndBailOut before allocation");
 275   Alloc->abandon([S = std::move(Self), E1 = std::move(Err)](Error E2) mutable {
 276     S->Ctx->notifyFailed(joinErrors(std::move(E1), std::move(E2)));
 277   });
 278 }
 279
 280 void prune(LinkGraph &G) {
 281   std::vector<Symbol *> Worklist;
 282   DenseSet<Block *> VisitedBlocks;
 283
 284   // Build the initial worklist from all symbols initially live.
 285   for (auto *Sym : G.defined_symbols())
 286     if (Sym->isLive())
 287       Worklist.push_back(Sym);
 288
 289   // Propagate live flags to all symbols reachable from the initial live set.
 290   while (!Worklist.empty()) {
 291     auto *Sym = Worklist.back();
 292     Worklist.pop_back();
 293
 294     auto &B = Sym->getBlock();
 295
 296     // Skip addressables that we've visited before.
 297     if (VisitedBlocks.count(&B))
 298       continue;
 299
 300     VisitedBlocks.insert(&B);
 301
 302     for (auto &E : Sym->getBlock().edges()) {
 303       // If the edge target is a defined symbol that is being newly marked live
 304       // then add it to the worklist.
 305       if (E.getTarget().isDefined() && !E.getTarget().isLive())
 306         Worklist.push_back(&E.getTarget());
 307
 308       // Mark the target live.
 309       E.getTarget().setLive(true);
 310     }
 311   }
 312
 313   // Collect all defined symbols to remove, then remove them.
 314   {
 315     LLVM_DEBUG(dbgs() << "Dead-stripping defined symbols:\n");
 316     std::vector<Symbol *> SymbolsToRemove;
 317     for (auto *Sym : G.defined_symbols())
 318       if (!Sym->isLive())
 319         SymbolsToRemove.push_back(Sym);
 320     for (auto *Sym : SymbolsToRemove) {
 321       LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
 322       G.removeDefinedSymbol(*Sym);
 323     }
 324   }
 325
 326   // Delete any unused blocks.
 327   {
 328     LLVM_DEBUG(dbgs() << "Dead-stripping blocks:\n");
 329     std::vector<Block *> BlocksToRemove;
 330     for (auto *B : G.blocks())
 331       if (!VisitedBlocks.count(B))
 332         BlocksToRemove.push_back(B);
 333     for (auto *B : BlocksToRemove) {
 334       LLVM_DEBUG(dbgs() << "  " << *B << "...\n");
 335       G.removeBlock(*B);
 336     }
 337   }
 338
 339   // Collect all external symbols to remove, then remove them.
 340   {
 341     LLVM_DEBUG(dbgs() << "Removing unused external symbols:\n");
 342     std::vector<Symbol *> SymbolsToRemove;
 343     for (auto *Sym : G.external_symbols())
 344       if (!Sym->isLive())
 345         SymbolsToRemove.push_back(Sym);
 346     for (auto *Sym : SymbolsToRemove) {
 347       LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
 348       G.removeExternalSymbol(*Sym);
 349     }
 350   }
 351 }
 352
 353 } // end namespace jitlink
 354 } // end namespace llvm