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   // Build the link graph.
  28   if (auto GraphOrErr = buildGraph(Ctx->getObjectBuffer()))
  29     G = std::move(*GraphOrErr);
  30   else
  31     return Ctx->notifyFailed(GraphOrErr.takeError());
  32   assert(G && "Graph should have been created by buildGraph above");
  33
  34   // Prune and optimize the graph.
  35   if (auto Err = runPasses(Passes.PrePrunePasses))
  36     return Ctx->notifyFailed(std::move(Err));
  37
  38   LLVM_DEBUG({
  39     dbgs() << "Link graph \"" << G->getName() << "\" pre-pruning:\n";
  40     dumpGraph(dbgs());
  41   });
  42
  43   prune(*G);
  44
  45   LLVM_DEBUG({
  46     dbgs() << "Link graph \"" << G->getName() << "\" post-pruning:\n";
  47     dumpGraph(dbgs());
  48   });
  49
  50   // Run post-pruning passes.
  51   if (auto Err = runPasses(Passes.PostPrunePasses))
  52     return Ctx->notifyFailed(std::move(Err));
  53
  54   // Sort blocks into segments.
  55   auto Layout = layOutBlocks();
  56
  57   // Allocate memory for segments.
  58   if (auto Err = allocateSegments(Layout))
  59     return Ctx->notifyFailed(std::move(Err));
  60
  61   // Notify client that the defined symbols have been assigned addresses.
  62   Ctx->notifyResolved(*G);
  63
  64   auto ExternalSymbols = getExternalSymbolNames();
  65
  66   // We're about to hand off ownership of ourself to the continuation. Grab a
  67   // pointer to the context so that we can call it to initiate the lookup.
  68   //
  69   // FIXME: Once callee expressions are defined to be sequenced before argument
  70   // expressions (c++17) we can simplify all this to:
  71   //
  72   // Ctx->lookup(std::move(UnresolvedExternals),
  73   //             [Self=std::move(Self)](Expected<AsyncLookupResult> Result) {
  74   //               Self->linkPhase2(std::move(Self), std::move(Result));
  75   //             });
  76   auto *TmpCtx = Ctx.get();
  77   TmpCtx->lookup(std::move(ExternalSymbols),
  78                  createLookupContinuation(
  79                      [S = std::move(Self), L = std::move(Layout)](
  80                          Expected<AsyncLookupResult> LookupResult) mutable {
  81                        auto &TmpSelf = *S;
  82                        TmpSelf.linkPhase2(std::move(S), std::move(LookupResult),
  83                                           std::move(L));
  84                      }));
  85 }
  86
  87 void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self,
  88                                Expected<AsyncLookupResult> LR,
  89                                SegmentLayoutMap Layout) {
  90   // If the lookup failed, bail out.
  91   if (!LR)
  92     return deallocateAndBailOut(LR.takeError());
  93
  94   // Assign addresses to external addressables.
  95   applyLookupResult(*LR);
  96
  97   LLVM_DEBUG({
  98     dbgs() << "Link graph \"" << G->getName() << "\" before copy-and-fixup:\n";
  99     dumpGraph(dbgs());
 100   });
 101
 102   // Copy block content to working memory and fix up.
 103   if (auto Err = copyAndFixUpBlocks(Layout, *Alloc))
 104     return deallocateAndBailOut(std::move(Err));
 105
 106   LLVM_DEBUG({
 107     dbgs() << "Link graph \"" << G->getName() << "\" after copy-and-fixup:\n";
 108     dumpGraph(dbgs());
 109   });
 110
 111   if (auto Err = runPasses(Passes.PostFixupPasses))
 112     return deallocateAndBailOut(std::move(Err));
 113
 114   // FIXME: Use move capture once we have c++14.
 115   auto *UnownedSelf = Self.release();
 116   auto Phase3Continuation = [UnownedSelf](Error Err) {
 117     std::unique_ptr<JITLinkerBase> Self(UnownedSelf);
 118     UnownedSelf->linkPhase3(std::move(Self), std::move(Err));
 119   };
 120
 121   Alloc->finalizeAsync(std::move(Phase3Continuation));
 122 }
 123
 124 void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self, Error Err) {
 125   if (Err)
 126     return deallocateAndBailOut(std::move(Err));
 127   Ctx->notifyFinalized(std::move(Alloc));
 128 }
 129
 130 Error JITLinkerBase::runPasses(LinkGraphPassList &Passes) {
 131   for (auto &P : Passes)
 132     if (auto Err = P(*G))
 133       return Err;
 134   return Error::success();
 135 }
 136
 137 JITLinkerBase::SegmentLayoutMap JITLinkerBase::layOutBlocks() {
 138
 139   SegmentLayoutMap Layout;
 140
 141   /// Partition blocks based on permissions and content vs. zero-fill.
 142   for (auto *B : G->blocks()) {
 143     auto &SegLists = Layout[B->getSection().getProtectionFlags()];
 144     if (!B->isZeroFill())
 145       SegLists.ContentBlocks.push_back(B);
 146     else
 147       SegLists.ZeroFillBlocks.push_back(B);
 148   }
 149
 150   /// Sort blocks within each list.
 151   for (auto &KV : Layout) {
 152
 153     auto CompareBlocks = [](const Block *LHS, const Block *RHS) {
 154       if (LHS->getSection().getOrdinal() != RHS->getSection().getOrdinal())
 155         return LHS->getSection().getOrdinal() < RHS->getSection().getOrdinal();
 156       return LHS->getOrdinal() < RHS->getOrdinal();
 157     };
 158
 159     auto &SegLists = KV.second;
 160     llvm::sort(SegLists.ContentBlocks, CompareBlocks);
 161     llvm::sort(SegLists.ZeroFillBlocks, CompareBlocks);
 162   }
 163
 164   LLVM_DEBUG({
 165     dbgs() << "Segment ordering:\n";
 166     for (auto &KV : Layout) {
 167       dbgs() << "  Segment "
 168              << static_cast<sys::Memory::ProtectionFlags>(KV.first) << ":\n";
 169       auto &SL = KV.second;
 170       for (auto &SIEntry :
 171            {std::make_pair(&SL.ContentBlocks, "content block"),
 172             std::make_pair(&SL.ZeroFillBlocks, "zero-fill block")}) {
 173         dbgs() << "    " << SIEntry.second << ":\n";
 174         for (auto *B : *SIEntry.first)
 175           dbgs() << "      " << *B << "\n";
 176       }
 177     }
 178   });
 179
 180   return Layout;
 181 }
 182
 183 Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) {
 184
 185   // Compute segment sizes and allocate memory.
 186   LLVM_DEBUG(dbgs() << "JIT linker requesting: { ");
 187   JITLinkMemoryManager::SegmentsRequestMap Segments;
 188   for (auto &KV : Layout) {
 189     auto &Prot = KV.first;
 190     auto &SegLists = KV.second;
 191
 192     uint64_t SegAlign = 1;
 193
 194     // Calculate segment content size.
 195     size_t SegContentSize = 0;
 196     for (auto *B : SegLists.ContentBlocks) {
 197       SegAlign = std::max(SegAlign, B->getAlignment());
 198       SegContentSize = alignToBlock(SegContentSize, *B);
 199       SegContentSize += B->getSize();
 200     }
 201
 202     uint64_t SegZeroFillStart = SegContentSize;
 203     uint64_t SegZeroFillEnd = SegZeroFillStart;
 204
 205     for (auto *B : SegLists.ZeroFillBlocks) {
 206       SegAlign = std::max(SegAlign, B->getAlignment());
 207       SegZeroFillEnd = alignToBlock(SegZeroFillEnd, *B);
 208       SegZeroFillEnd += B->getSize();
 209     }
 210
 211     Segments[Prot] = {SegAlign, SegContentSize,
 212                       SegZeroFillEnd - SegZeroFillStart};
 213
 214     LLVM_DEBUG({
 215       dbgs() << (&KV == &*Layout.begin() ? "" : "; ")
 216              << static_cast<sys::Memory::ProtectionFlags>(Prot)
 217              << ": alignment = " << SegAlign
 218              << ", content size = " << SegContentSize
 219              << ", zero-fill size = " << (SegZeroFillEnd - SegZeroFillStart);
 220     });
 221   }
 222   LLVM_DEBUG(dbgs() << " }\n");
 223
 224   if (auto AllocOrErr = Ctx->getMemoryManager().allocate(Segments))
 225     Alloc = std::move(*AllocOrErr);
 226   else
 227     return AllocOrErr.takeError();
 228
 229   LLVM_DEBUG({
 230     dbgs() << "JIT linker got working memory:\n";
 231     for (auto &KV : Layout) {
 232       auto Prot = static_cast<sys::Memory::ProtectionFlags>(KV.first);
 233       dbgs() << "  " << Prot << ": "
 234              << (const void *)Alloc->getWorkingMemory(Prot).data() << "\n";
 235     }
 236   });
 237
 238   // Update block target addresses.
 239   for (auto &KV : Layout) {
 240     auto &Prot = KV.first;
 241     auto &SL = KV.second;
 242
 243     JITTargetAddress NextBlockAddr =
 244         Alloc->getTargetMemory(static_cast<sys::Memory::ProtectionFlags>(Prot));
 245
 246     for (auto *SIList : {&SL.ContentBlocks, &SL.ZeroFillBlocks})
 247       for (auto *B : *SIList) {
 248         NextBlockAddr = alignToBlock(NextBlockAddr, *B);
 249         B->setAddress(NextBlockAddr);
 250         NextBlockAddr += B->getSize();
 251       }
 252   }
 253
 254   return Error::success();
 255 }
 256
 257 DenseSet<StringRef> JITLinkerBase::getExternalSymbolNames() const {
 258   // Identify unresolved external symbols.
 259   DenseSet<StringRef> UnresolvedExternals;
 260   for (auto *Sym : G->external_symbols()) {
 261     assert(Sym->getAddress() == 0 &&
 262            "External has already been assigned an address");
 263     assert(Sym->getName() != StringRef() && Sym->getName() != "" &&
 264            "Externals must be named");
 265     UnresolvedExternals.insert(Sym->getName());
 266   }
 267   return UnresolvedExternals;
 268 }
 269
 270 void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
 271   for (auto *Sym : G->external_symbols()) {
 272     assert(Sym->getAddress() == 0 && "Symbol already resolved");
 273     assert(!Sym->isDefined() && "Symbol being resolved is already defined");
 274     assert(Result.count(Sym->getName()) && "Missing resolution for symbol");
 275     Sym->getAddressable().setAddress(Result[Sym->getName()].getAddress());
 276   }
 277
 278   LLVM_DEBUG({
 279     dbgs() << "Externals after applying lookup result:\n";
 280     for (auto *Sym : G->external_symbols())
 281       dbgs() << "  " << Sym->getName() << ": "
 282              << formatv("{0:x16}", Sym->getAddress()) << "\n";
 283   });
 284   assert(llvm::all_of(G->external_symbols(),
 285                       [](Symbol *Sym) { return Sym->getAddress() != 0; }) &&
 286          "All symbols should have been resolved by this point");
 287 }
 288
 289 void JITLinkerBase::deallocateAndBailOut(Error Err) {
 290   assert(Err && "Should not be bailing out on success value");
 291   assert(Alloc && "can not call deallocateAndBailOut before allocation");
 292   Ctx->notifyFailed(joinErrors(std::move(Err), Alloc->deallocate()));
 293 }
 294
 295 void JITLinkerBase::dumpGraph(raw_ostream &OS) {
 296   assert(G && "Graph is not set yet");
 297   G->dump(dbgs(), [this](Edge::Kind K) { return getEdgeKindName(K); });
 298 }
 299
 300 void prune(LinkGraph &G) {
 301   std::vector<Symbol *> Worklist;
 302   DenseSet<Block *> VisitedBlocks;
 303
 304   // Build the initial worklist from all symbols initially live.
 305   for (auto *Sym : G.defined_symbols())
 306     if (Sym->isLive())
 307       Worklist.push_back(Sym);
 308
 309   // Propagate live flags to all symbols reachable from the initial live set.
 310   while (!Worklist.empty()) {
 311     auto *Sym = Worklist.back();
 312     Worklist.pop_back();
 313
 314     auto &B = Sym->getBlock();
 315
 316     // Skip addressables that we've visited before.
 317     if (VisitedBlocks.count(&B))
 318       continue;
 319
 320     VisitedBlocks.insert(&B);
 321
 322     for (auto &E : Sym->getBlock().edges()) {
 323       if (E.getTarget().isDefined() && !E.getTarget().isLive()) {
 324         E.getTarget().setLive(true);
 325         Worklist.push_back(&E.getTarget());
 326       }
 327     }
 328   }
 329
 330   // Collect all the symbols to remove, then remove them.
 331   {
 332     LLVM_DEBUG(dbgs() << "Dead-stripping symbols:\n");
 333     std::vector<Symbol *> SymbolsToRemove;
 334     for (auto *Sym : G.defined_symbols())
 335       if (!Sym->isLive())
 336         SymbolsToRemove.push_back(Sym);
 337     for (auto *Sym : SymbolsToRemove) {
 338       LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
 339       G.removeDefinedSymbol(*Sym);
 340     }
 341   }
 342
 343   // Delete any unused blocks.
 344   {
 345     LLVM_DEBUG(dbgs() << "Dead-stripping blocks:\n");
 346     std::vector<Block *> BlocksToRemove;
 347     for (auto *B : G.blocks())
 348       if (!VisitedBlocks.count(B))
 349         BlocksToRemove.push_back(B);
 350     for (auto *B : BlocksToRemove) {
 351       LLVM_DEBUG(dbgs() << "  " << *B << "...\n");
 352       G.removeBlock(*B);
 353     }
 354   }
 355 }
 356
 357 } // end namespace jitlink
 358 } // end namespace llvm