contrib/llvm-project/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({ dbgs() << "Building jitlink graph for new input...\n"; });
  28
  29   // Build the link graph.
  30   if (auto GraphOrErr = buildGraph(Ctx->getObjectBuffer()))
  31     G = std::move(*GraphOrErr);
  32   else
  33     return Ctx->notifyFailed(GraphOrErr.takeError());
  34   assert(G && "Graph should have been created by buildGraph above");
  35
  36   LLVM_DEBUG({
  37     dbgs() << "Starting link phase 1 for graph " << G->getName() << "\n";
  38   });
  39
  40   // Prune and optimize the graph.
  41   if (auto Err = runPasses(Passes.PrePrunePasses))
  42     return Ctx->notifyFailed(std::move(Err));
  43
  44   LLVM_DEBUG({
  45     dbgs() << "Link graph \"" << G->getName() << "\" pre-pruning:\n";
  46     dumpGraph(dbgs());
  47   });
  48
  49   prune(*G);
  50
  51   LLVM_DEBUG({
  52     dbgs() << "Link graph \"" << G->getName() << "\" post-pruning:\n";
  53     dumpGraph(dbgs());
  54   });
  55
  56   // Run post-pruning passes.
  57   if (auto Err = runPasses(Passes.PostPrunePasses))
  58     return Ctx->notifyFailed(std::move(Err));
  59
  60   // Sort blocks into segments.
  61   auto Layout = layOutBlocks();
  62
  63   // Allocate memory for segments.
  64   if (auto Err = allocateSegments(Layout))
  65     return Ctx->notifyFailed(std::move(Err));
  66
  67   // Notify client that the defined symbols have been assigned addresses.
  68   LLVM_DEBUG(
  69       { dbgs() << "Resolving symbols defined in " << G->getName() << "\n"; });
  70   Ctx->notifyResolved(*G);
  71
  72   auto ExternalSymbols = getExternalSymbolNames();
  73
  74   LLVM_DEBUG({
  75     dbgs() << "Issuing lookup for external symbols for " << G->getName()
  76            << " (may trigger materialization/linking of other graphs)...\n";
  77   });
  78
  79   // We're about to hand off ownership of ourself to the continuation. Grab a
  80   // pointer to the context so that we can call it to initiate the lookup.
  81   //
  82   // FIXME: Once callee expressions are defined to be sequenced before argument
  83   // expressions (c++17) we can simplify all this to:
  84   //
  85   // Ctx->lookup(std::move(UnresolvedExternals),
  86   //             [Self=std::move(Self)](Expected<AsyncLookupResult> Result) {
  87   //               Self->linkPhase2(std::move(Self), std::move(Result));
  88   //             });
  89   auto *TmpCtx = Ctx.get();
  90   TmpCtx->lookup(std::move(ExternalSymbols),
  91                  createLookupContinuation(
  92                      [S = std::move(Self), L = std::move(Layout)](
  93                          Expected<AsyncLookupResult> LookupResult) mutable {
  94                        auto &TmpSelf = *S;
  95                        TmpSelf.linkPhase2(std::move(S), std::move(LookupResult),
  96                                           std::move(L));
  97                      }));
  98 }
  99
 100 void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self,
 101                                Expected<AsyncLookupResult> LR,
 102                                SegmentLayoutMap Layout) {
 103
 104   LLVM_DEBUG({
 105     dbgs() << "Starting link phase 2 for graph " << G->getName() << "\n";
 106   });
 107
 108   // If the lookup failed, bail out.
 109   if (!LR)
 110     return deallocateAndBailOut(LR.takeError());
 111
 112   // Assign addresses to external addressables.
 113   applyLookupResult(*LR);
 114
 115   // Copy block content to working memory.
 116   copyBlockContentToWorkingMemory(Layout, *Alloc);
 117
 118   LLVM_DEBUG({
 119     dbgs() << "Link graph \"" << G->getName()
 120            << "\" before post-allocation passes:\n";
 121     dumpGraph(dbgs());
 122   });
 123
 124   if (auto Err = runPasses(Passes.PostAllocationPasses))
 125     return deallocateAndBailOut(std::move(Err));
 126
 127   LLVM_DEBUG({
 128     dbgs() << "Link graph \"" << G->getName() << "\" before copy-and-fixup:\n";
 129     dumpGraph(dbgs());
 130   });
 131
 132   // Fix up block content.
 133   if (auto Err = fixUpBlocks(*G))
 134     return deallocateAndBailOut(std::move(Err));
 135
 136   LLVM_DEBUG({
 137     dbgs() << "Link graph \"" << G->getName() << "\" after copy-and-fixup:\n";
 138     dumpGraph(dbgs());
 139   });
 140
 141   if (auto Err = runPasses(Passes.PostFixupPasses))
 142     return deallocateAndBailOut(std::move(Err));
 143
 144   // FIXME: Use move capture once we have c++14.
 145   auto *UnownedSelf = Self.release();
 146   auto Phase3Continuation = [UnownedSelf](Error Err) {
 147     std::unique_ptr<JITLinkerBase> Self(UnownedSelf);
 148     UnownedSelf->linkPhase3(std::move(Self), std::move(Err));
 149   };
 150
 151   Alloc->finalizeAsync(std::move(Phase3Continuation));
 152 }
 153
 154 void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self, Error Err) {
 155
 156   LLVM_DEBUG({
 157     dbgs() << "Starting link phase 3 for graph " << G->getName() << "\n";
 158   });
 159
 160   if (Err)
 161     return deallocateAndBailOut(std::move(Err));
 162   Ctx->notifyFinalized(std::move(Alloc));
 163
 164   LLVM_DEBUG({ dbgs() << "Link of graph " << G->getName() << " complete\n"; });
 165 }
 166
 167 Error JITLinkerBase::runPasses(LinkGraphPassList &Passes) {
 168   for (auto &P : Passes)
 169     if (auto Err = P(*G))
 170       return Err;
 171   return Error::success();
 172 }
 173
 174 JITLinkerBase::SegmentLayoutMap JITLinkerBase::layOutBlocks() {
 175
 176   SegmentLayoutMap Layout;
 177
 178   /// Partition blocks based on permissions and content vs. zero-fill.
 179   for (auto *B : G->blocks()) {
 180     auto &SegLists = Layout[B->getSection().getProtectionFlags()];
 181     if (!B->isZeroFill())
 182       SegLists.ContentBlocks.push_back(B);
 183     else
 184       SegLists.ZeroFillBlocks.push_back(B);
 185   }
 186
 187   /// Sort blocks within each list.
 188   for (auto &KV : Layout) {
 189
 190     auto CompareBlocks = [](const Block *LHS, const Block *RHS) {
 191       // Sort by section, address and size
 192       if (LHS->getSection().getOrdinal() != RHS->getSection().getOrdinal())
 193         return LHS->getSection().getOrdinal() < RHS->getSection().getOrdinal();
 194       if (LHS->getAddress() != RHS->getAddress())
 195         return LHS->getAddress() < RHS->getAddress();
 196       return LHS->getSize() < RHS->getSize();
 197     };
 198
 199     auto &SegLists = KV.second;
 200     llvm::sort(SegLists.ContentBlocks, CompareBlocks);
 201     llvm::sort(SegLists.ZeroFillBlocks, CompareBlocks);
 202   }
 203
 204   LLVM_DEBUG({
 205     dbgs() << "Computed segment ordering:\n";
 206     for (auto &KV : Layout) {
 207       dbgs() << "  Segment "
 208              << static_cast<sys::Memory::ProtectionFlags>(KV.first) << ":\n";
 209       auto &SL = KV.second;
 210       for (auto &SIEntry :
 211            {std::make_pair(&SL.ContentBlocks, "content block"),
 212             std::make_pair(&SL.ZeroFillBlocks, "zero-fill block")}) {
 213         dbgs() << "    " << SIEntry.second << ":\n";
 214         for (auto *B : *SIEntry.first)
 215           dbgs() << "      " << *B << "\n";
 216       }
 217     }
 218   });
 219
 220   return Layout;
 221 }
 222
 223 Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) {
 224
 225   // Compute segment sizes and allocate memory.
 226   LLVM_DEBUG(dbgs() << "JIT linker requesting: { ");
 227   JITLinkMemoryManager::SegmentsRequestMap Segments;
 228   for (auto &KV : Layout) {
 229     auto &Prot = KV.first;
 230     auto &SegLists = KV.second;
 231
 232     uint64_t SegAlign = 1;
 233
 234     // Calculate segment content size.
 235     size_t SegContentSize = 0;
 236     for (auto *B : SegLists.ContentBlocks) {
 237       SegAlign = std::max(SegAlign, B->getAlignment());
 238       SegContentSize = alignToBlock(SegContentSize, *B);
 239       SegContentSize += B->getSize();
 240     }
 241
 242     uint64_t SegZeroFillStart = SegContentSize;
 243     uint64_t SegZeroFillEnd = SegZeroFillStart;
 244
 245     for (auto *B : SegLists.ZeroFillBlocks) {
 246       SegAlign = std::max(SegAlign, B->getAlignment());
 247       SegZeroFillEnd = alignToBlock(SegZeroFillEnd, *B);
 248       SegZeroFillEnd += B->getSize();
 249     }
 250
 251     Segments[Prot] = {SegAlign, SegContentSize,
 252                       SegZeroFillEnd - SegZeroFillStart};
 253
 254     LLVM_DEBUG({
 255       dbgs() << (&KV == &*Layout.begin() ? "" : "; ")
 256              << static_cast<sys::Memory::ProtectionFlags>(Prot)
 257              << ": alignment = " << SegAlign
 258              << ", content size = " << SegContentSize
 259              << ", zero-fill size = " << (SegZeroFillEnd - SegZeroFillStart);
 260     });
 261   }
 262   LLVM_DEBUG(dbgs() << " }\n");
 263
 264   if (auto AllocOrErr = Ctx->getMemoryManager().allocate(Segments))
 265     Alloc = std::move(*AllocOrErr);
 266   else
 267     return AllocOrErr.takeError();
 268
 269   LLVM_DEBUG({
 270     dbgs() << "JIT linker got memory (working -> target):\n";
 271     for (auto &KV : Layout) {
 272       auto Prot = static_cast<sys::Memory::ProtectionFlags>(KV.first);
 273       dbgs() << "  " << Prot << ": "
 274              << (const void *)Alloc->getWorkingMemory(Prot).data() << " -> "
 275              << formatv("{0:x16}", Alloc->getTargetMemory(Prot)) << "\n";
 276     }
 277   });
 278
 279   // Update block target addresses.
 280   for (auto &KV : Layout) {
 281     auto &Prot = KV.first;
 282     auto &SL = KV.second;
 283
 284     JITTargetAddress NextBlockAddr =
 285         Alloc->getTargetMemory(static_cast<sys::Memory::ProtectionFlags>(Prot));
 286
 287     for (auto *SIList : {&SL.ContentBlocks, &SL.ZeroFillBlocks})
 288       for (auto *B : *SIList) {
 289         NextBlockAddr = alignToBlock(NextBlockAddr, *B);
 290         B->setAddress(NextBlockAddr);
 291         NextBlockAddr += B->getSize();
 292       }
 293   }
 294
 295   return Error::success();
 296 }
 297
 298 JITLinkContext::LookupMap JITLinkerBase::getExternalSymbolNames() const {
 299   // Identify unresolved external symbols.
 300   JITLinkContext::LookupMap UnresolvedExternals;
 301   for (auto *Sym : G->external_symbols()) {
 302     assert(Sym->getAddress() == 0 &&
 303            "External has already been assigned an address");
 304     assert(Sym->getName() != StringRef() && Sym->getName() != "" &&
 305            "Externals must be named");
 306     SymbolLookupFlags LookupFlags =
 307         Sym->getLinkage() == Linkage::Weak
 308             ? SymbolLookupFlags::WeaklyReferencedSymbol
 309             : SymbolLookupFlags::RequiredSymbol;
 310     UnresolvedExternals[Sym->getName()] = LookupFlags;
 311   }
 312   return UnresolvedExternals;
 313 }
 314
 315 void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
 316   for (auto *Sym : G->external_symbols()) {
 317     assert(Sym->getOffset() == 0 &&
 318            "External symbol is not at the start of its addressable block");
 319     assert(Sym->getAddress() == 0 && "Symbol already resolved");
 320     assert(!Sym->isDefined() && "Symbol being resolved is already defined");
 321     auto ResultI = Result.find(Sym->getName());
 322     if (ResultI != Result.end())
 323       Sym->getAddressable().setAddress(ResultI->second.getAddress());
 324     else
 325       assert(Sym->getLinkage() == Linkage::Weak &&
 326              "Failed to resolve non-weak reference");
 327   }
 328
 329   LLVM_DEBUG({
 330     dbgs() << "Externals after applying lookup result:\n";
 331     for (auto *Sym : G->external_symbols())
 332       dbgs() << "  " << Sym->getName() << ": "
 333              << formatv("{0:x16}", Sym->getAddress()) << "\n";
 334   });
 335   assert(llvm::all_of(G->external_symbols(),
 336                       [](Symbol *Sym) {
 337                         return Sym->getAddress() != 0 ||
 338                                Sym->getLinkage() == Linkage::Weak;
 339                       }) &&
 340          "All strong external symbols should have been resolved by now");
 341 }
 342
 343 void JITLinkerBase::copyBlockContentToWorkingMemory(
 344     const SegmentLayoutMap &Layout, JITLinkMemoryManager::Allocation &Alloc) {
 345
 346   LLVM_DEBUG(dbgs() << "Copying block content:\n");
 347   for (auto &KV : Layout) {
 348     auto &Prot = KV.first;
 349     auto &SegLayout = KV.second;
 350
 351     auto SegMem =
 352         Alloc.getWorkingMemory(static_cast<sys::Memory::ProtectionFlags>(Prot));
 353     char *LastBlockEnd = SegMem.data();
 354     char *BlockDataPtr = LastBlockEnd;
 355
 356     LLVM_DEBUG({
 357       dbgs() << "  Processing segment "
 358              << static_cast<sys::Memory::ProtectionFlags>(Prot) << " [ "
 359              << (const void *)SegMem.data() << " .. "
 360              << (const void *)((char *)SegMem.data() + SegMem.size())
 361              << " ]\n    Processing content sections:\n";
 362     });
 363
 364     for (auto *B : SegLayout.ContentBlocks) {
 365       LLVM_DEBUG(dbgs() << "    " << *B << ":\n");
 366
 367       // Pad to alignment/alignment-offset.
 368       BlockDataPtr = alignToBlock(BlockDataPtr, *B);
 369
 370       LLVM_DEBUG({
 371         dbgs() << "      Bumped block pointer to " << (const void *)BlockDataPtr
 372                << " to meet block alignment " << B->getAlignment()
 373                << " and alignment offset " << B->getAlignmentOffset() << "\n";
 374       });
 375
 376       // Zero pad up to alignment.
 377       LLVM_DEBUG({
 378         if (LastBlockEnd != BlockDataPtr)
 379           dbgs() << "      Zero padding from " << (const void *)LastBlockEnd
 380                  << " to " << (const void *)BlockDataPtr << "\n";
 381       });
 382
 383       while (LastBlockEnd != BlockDataPtr)
 384         *LastBlockEnd++ = 0;
 385
 386       // Copy initial block content.
 387       LLVM_DEBUG({
 388         dbgs() << "      Copying block " << *B << " content, "
 389                << B->getContent().size() << " bytes, from "
 390                << (const void *)B->getContent().data() << " to "
 391                << (const void *)BlockDataPtr << "\n";
 392       });
 393       memcpy(BlockDataPtr, B->getContent().data(), B->getContent().size());
 394
 395       // Point the block's content to the fixed up buffer.
 396       B->setContent(StringRef(BlockDataPtr, B->getContent().size()));
 397
 398       // Update block end pointer.
 399       LastBlockEnd = BlockDataPtr + B->getContent().size();
 400       BlockDataPtr = LastBlockEnd;
 401     }
 402
 403     // Zero pad the rest of the segment.
 404     LLVM_DEBUG({
 405       dbgs() << "    Zero padding end of segment from "
 406              << (const void *)LastBlockEnd << " to "
 407              << (const void *)((char *)SegMem.data() + SegMem.size()) << "\n";
 408     });
 409     while (LastBlockEnd != SegMem.data() + SegMem.size())
 410       *LastBlockEnd++ = 0;
 411   }
 412 }
 413
 414 void JITLinkerBase::deallocateAndBailOut(Error Err) {
 415   assert(Err && "Should not be bailing out on success value");
 416   assert(Alloc && "can not call deallocateAndBailOut before allocation");
 417   Ctx->notifyFailed(joinErrors(std::move(Err), Alloc->deallocate()));
 418 }
 419
 420 void JITLinkerBase::dumpGraph(raw_ostream &OS) {
 421   assert(G && "Graph is not set yet");
 422   G->dump(dbgs(), [this](Edge::Kind K) { return getEdgeKindName(K); });
 423 }
 424
 425 void prune(LinkGraph &G) {
 426   std::vector<Symbol *> Worklist;
 427   DenseSet<Block *> VisitedBlocks;
 428
 429   // Build the initial worklist from all symbols initially live.
 430   for (auto *Sym : G.defined_symbols())
 431     if (Sym->isLive())
 432       Worklist.push_back(Sym);
 433
 434   // Propagate live flags to all symbols reachable from the initial live set.
 435   while (!Worklist.empty()) {
 436     auto *Sym = Worklist.back();
 437     Worklist.pop_back();
 438
 439     auto &B = Sym->getBlock();
 440
 441     // Skip addressables that we've visited before.
 442     if (VisitedBlocks.count(&B))
 443       continue;
 444
 445     VisitedBlocks.insert(&B);
 446
 447     for (auto &E : Sym->getBlock().edges()) {
 448       if (E.getTarget().isDefined() && !E.getTarget().isLive()) {
 449         E.getTarget().setLive(true);
 450         Worklist.push_back(&E.getTarget());
 451       }
 452     }
 453   }
 454
 455   // Collect all the symbols to remove, then remove them.
 456   {
 457     LLVM_DEBUG(dbgs() << "Dead-stripping symbols:\n");
 458     std::vector<Symbol *> SymbolsToRemove;
 459     for (auto *Sym : G.defined_symbols())
 460       if (!Sym->isLive())
 461         SymbolsToRemove.push_back(Sym);
 462     for (auto *Sym : SymbolsToRemove) {
 463       LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
 464       G.removeDefinedSymbol(*Sym);
 465     }
 466   }
 467
 468   // Delete any unused blocks.
 469   {
 470     LLVM_DEBUG(dbgs() << "Dead-stripping blocks:\n");
 471     std::vector<Block *> BlocksToRemove;
 472     for (auto *B : G.blocks())
 473       if (!VisitedBlocks.count(B))
 474         BlocksToRemove.push_back(B);
 475     for (auto *B : BlocksToRemove) {
 476       LLVM_DEBUG(dbgs() << "  " << *B << "...\n");
 477       G.removeBlock(*B);
 478     }
 479   }
 480 }
 481
 482 } // end namespace jitlink
 483 } // end namespace llvm