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