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() {}
  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   Ctx->getMemoryManager().allocate(
  52       Ctx->getJITLinkDylib(), *G,
  53       [S = std::move(Self)](AllocResult AR) mutable {
  54         auto *TmpSelf = S.get();
  55         TmpSelf->linkPhase2(std::move(S), std::move(AR));
  56       });
  57 }
  58
  59 void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self,
  60                                AllocResult AR) {
  61
  62   if (AR)
  63     Alloc = std::move(*AR);
  64   else
  65     return Ctx->notifyFailed(AR.takeError());
  66
  67   LLVM_DEBUG({
  68     dbgs() << "Link graph \"" << G->getName()
  69            << "\" before post-allocation passes:\n";
  70     G->dump(dbgs());
  71   });
  72
  73   // Run post-allocation passes.
  74   if (auto Err = runPasses(Passes.PostAllocationPasses))
  75     return Ctx->notifyFailed(std::move(Err));
  76
  77   // Notify client that the defined symbols have been assigned addresses.
  78   LLVM_DEBUG(dbgs() << "Resolving symbols defined in " << G->getName() << "\n");
  79
  80   if (auto Err = Ctx->notifyResolved(*G))
  81     return Ctx->notifyFailed(std::move(Err));
  82
  83   auto ExternalSymbols = getExternalSymbolNames();
  84
  85   // If there are no external symbols then proceed immediately with phase 3.
  86   if (ExternalSymbols.empty()) {
  87     LLVM_DEBUG({
  88       dbgs() << "No external symbols for " << G->getName()
  89              << ". Proceeding immediately with link phase 3.\n";
  90     });
  91     // FIXME: Once callee expressions are defined to be sequenced before
  92     //        argument expressions (c++17) we can simplify this. See below.
  93     auto &TmpSelf = *Self;
  94     TmpSelf.linkPhase3(std::move(Self), AsyncLookupResult());
  95     return;
  96   }
  97
  98   // Otherwise look up the externals.
  99   LLVM_DEBUG({
 100     dbgs() << "Issuing lookup for external symbols for " << G->getName()
 101            << " (may trigger materialization/linking of other graphs)...\n";
 102   });
 103
 104   // We're about to hand off ownership of ourself to the continuation. Grab a
 105   // pointer to the context so that we can call it to initiate the lookup.
 106   //
 107   // FIXME: Once callee expressions are defined to be sequenced before argument
 108   // expressions (c++17) we can simplify all this to:
 109   //
 110   // Ctx->lookup(std::move(UnresolvedExternals),
 111   //             [Self=std::move(Self)](Expected<AsyncLookupResult> Result) {
 112   //               Self->linkPhase3(std::move(Self), std::move(Result));
 113   //             });
 114   Ctx->lookup(std::move(ExternalSymbols),
 115               createLookupContinuation(
 116                   [S = std::move(Self)](
 117                       Expected<AsyncLookupResult> LookupResult) mutable {
 118                     auto &TmpSelf = *S;
 119                     TmpSelf.linkPhase3(std::move(S), std::move(LookupResult));
 120                   }));
 121 }
 122
 123 void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self,
 124                                Expected<AsyncLookupResult> LR) {
 125
 126   LLVM_DEBUG({
 127     dbgs() << "Starting link phase 3 for graph " << G->getName() << "\n";
 128   });
 129
 130   // If the lookup failed, bail out.
 131   if (!LR)
 132     return abandonAllocAndBailOut(std::move(Self), LR.takeError());
 133
 134   // Assign addresses to external addressables.
 135   applyLookupResult(*LR);
 136
 137   LLVM_DEBUG({
 138     dbgs() << "Link graph \"" << G->getName()
 139            << "\" before pre-fixup passes:\n";
 140     G->dump(dbgs());
 141   });
 142
 143   if (auto Err = runPasses(Passes.PreFixupPasses))
 144     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
 145
 146   LLVM_DEBUG({
 147     dbgs() << "Link graph \"" << G->getName() << "\" before copy-and-fixup:\n";
 148     G->dump(dbgs());
 149   });
 150
 151   // Fix up block content.
 152   if (auto Err = fixUpBlocks(*G))
 153     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
 154
 155   LLVM_DEBUG({
 156     dbgs() << "Link graph \"" << G->getName() << "\" after copy-and-fixup:\n";
 157     G->dump(dbgs());
 158   });
 159
 160   if (auto Err = runPasses(Passes.PostFixupPasses))
 161     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
 162
 163   Alloc->finalize([S = std::move(Self)](FinalizeResult FR) mutable {
 164     auto *TmpSelf = S.get();
 165     TmpSelf->linkPhase4(std::move(S), std::move(FR));
 166   });
 167 }
 168
 169 void JITLinkerBase::linkPhase4(std::unique_ptr<JITLinkerBase> Self,
 170                                FinalizeResult FR) {
 171
 172   LLVM_DEBUG({
 173     dbgs() << "Starting link phase 4 for graph " << G->getName() << "\n";
 174   });
 175
 176   if (!FR)
 177     return Ctx->notifyFailed(FR.takeError());
 178
 179   Ctx->notifyFinalized(std::move(*FR));
 180
 181   LLVM_DEBUG({ dbgs() << "Link of graph " << G->getName() << " complete\n"; });
 182 }
 183
 184 Error JITLinkerBase::runPasses(LinkGraphPassList &Passes) {
 185   for (auto &P : Passes)
 186     if (auto Err = P(*G))
 187       return Err;
 188   return Error::success();
 189 }
 190
 191 JITLinkContext::LookupMap JITLinkerBase::getExternalSymbolNames() const {
 192   // Identify unresolved external symbols.
 193   JITLinkContext::LookupMap UnresolvedExternals;
 194   for (auto *Sym : G->external_symbols()) {
 195     assert(!Sym->getAddress() &&
 196            "External has already been assigned an address");
 197     assert(Sym->getName() != StringRef() && Sym->getName() != "" &&
 198            "Externals must be named");
 199     SymbolLookupFlags LookupFlags =
 200         Sym->getLinkage() == Linkage::Weak
 201             ? SymbolLookupFlags::WeaklyReferencedSymbol
 202             : SymbolLookupFlags::RequiredSymbol;
 203     UnresolvedExternals[Sym->getName()] = LookupFlags;
 204   }
 205   return UnresolvedExternals;
 206 }
 207
 208 void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
 209   for (auto *Sym : G->external_symbols()) {
 210     assert(Sym->getOffset() == 0 &&
 211            "External symbol is not at the start of its addressable block");
 212     assert(!Sym->getAddress() && "Symbol already resolved");
 213     assert(!Sym->isDefined() && "Symbol being resolved is already defined");
 214     auto ResultI = Result.find(Sym->getName());
 215     if (ResultI != Result.end())
 216       Sym->getAddressable().setAddress(
 217           orc::ExecutorAddr(ResultI->second.getAddress()));
 218     else
 219       assert(Sym->getLinkage() == Linkage::Weak &&
 220              "Failed to resolve non-weak reference");
 221   }
 222
 223   LLVM_DEBUG({
 224     dbgs() << "Externals after applying lookup result:\n";
 225     for (auto *Sym : G->external_symbols())
 226       dbgs() << "  " << Sym->getName() << ": "
 227              << formatv("{0:x16}", Sym->getAddress().getValue()) << "\n";
 228   });
 229 }
 230
 231 void JITLinkerBase::abandonAllocAndBailOut(std::unique_ptr<JITLinkerBase> Self,
 232                                            Error Err) {
 233   assert(Err && "Should not be bailing out on success value");
 234   assert(Alloc && "can not call abandonAllocAndBailOut before allocation");
 235   Alloc->abandon([S = std::move(Self), E1 = std::move(Err)](Error E2) mutable {
 236     S->Ctx->notifyFailed(joinErrors(std::move(E1), std::move(E2)));
 237   });
 238 }
 239
 240 void prune(LinkGraph &G) {
 241   std::vector<Symbol *> Worklist;
 242   DenseSet<Block *> VisitedBlocks;
 243
 244   // Build the initial worklist from all symbols initially live.
 245   for (auto *Sym : G.defined_symbols())
 246     if (Sym->isLive())
 247       Worklist.push_back(Sym);
 248
 249   // Propagate live flags to all symbols reachable from the initial live set.
 250   while (!Worklist.empty()) {
 251     auto *Sym = Worklist.back();
 252     Worklist.pop_back();
 253
 254     auto &B = Sym->getBlock();
 255
 256     // Skip addressables that we've visited before.
 257     if (VisitedBlocks.count(&B))
 258       continue;
 259
 260     VisitedBlocks.insert(&B);
 261
 262     for (auto &E : Sym->getBlock().edges()) {
 263       // If the edge target is a defined symbol that is being newly marked live
 264       // then add it to the worklist.
 265       if (E.getTarget().isDefined() && !E.getTarget().isLive())
 266         Worklist.push_back(&E.getTarget());
 267
 268       // Mark the target live.
 269       E.getTarget().setLive(true);
 270     }
 271   }
 272
 273   // Collect all defined symbols to remove, then remove them.
 274   {
 275     LLVM_DEBUG(dbgs() << "Dead-stripping defined symbols:\n");
 276     std::vector<Symbol *> SymbolsToRemove;
 277     for (auto *Sym : G.defined_symbols())
 278       if (!Sym->isLive())
 279         SymbolsToRemove.push_back(Sym);
 280     for (auto *Sym : SymbolsToRemove) {
 281       LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
 282       G.removeDefinedSymbol(*Sym);
 283     }
 284   }
 285
 286   // Delete any unused blocks.
 287   {
 288     LLVM_DEBUG(dbgs() << "Dead-stripping blocks:\n");
 289     std::vector<Block *> BlocksToRemove;
 290     for (auto *B : G.blocks())
 291       if (!VisitedBlocks.count(B))
 292         BlocksToRemove.push_back(B);
 293     for (auto *B : BlocksToRemove) {
 294       LLVM_DEBUG(dbgs() << "  " << *B << "...\n");
 295       G.removeBlock(*B);
 296     }
 297   }
 298
 299   // Collect all external symbols to remove, then remove them.
 300   {
 301     LLVM_DEBUG(dbgs() << "Removing unused external symbols:\n");
 302     std::vector<Symbol *> SymbolsToRemove;
 303     for (auto *Sym : G.external_symbols())
 304       if (!Sym->isLive())
 305         SymbolsToRemove.push_back(Sym);
 306     for (auto *Sym : SymbolsToRemove) {
 307       LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
 308       G.removeExternalSymbol(*Sym);
 309     }
 310   }
 311 }
 312
 313 } // end namespace jitlink
 314 } // end namespace llvm