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