1 //===--------- JITLinkGeneric.cpp - Generic JIT linker utilities ----------===//
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
7 //===----------------------------------------------------------------------===//
9 // Generic JITLinker utility class.
11 //===----------------------------------------------------------------------===//
13 #include "JITLinkGeneric.h"
15 #include "llvm/Support/BinaryStreamReader.h"
16 #include "llvm/Support/MemoryBuffer.h"
18 #define DEBUG_TYPE "jitlink"
23 JITLinkerBase::~JITLinkerBase() {}
25 void JITLinkerBase::linkPhase1(std::unique_ptr<JITLinkerBase> Self) {
27 LLVM_DEBUG({ dbgs() << "Building jitlink graph for new input...\n"; });
29 // Build the link graph.
30 if (auto GraphOrErr = buildGraph(Ctx->getObjectBuffer()))
31 G = std::move(*GraphOrErr);
33 return Ctx->notifyFailed(GraphOrErr.takeError());
34 assert(G && "Graph should have been created by buildGraph above");
37 dbgs() << "Starting link phase 1 for graph " << G->getName() << "\n";
40 // Prune and optimize the graph.
41 if (auto Err = runPasses(Passes.PrePrunePasses))
42 return Ctx->notifyFailed(std::move(Err));
45 dbgs() << "Link graph \"" << G->getName() << "\" pre-pruning:\n";
52 dbgs() << "Link graph \"" << G->getName() << "\" post-pruning:\n";
56 // Run post-pruning passes.
57 if (auto Err = runPasses(Passes.PostPrunePasses))
58 return Ctx->notifyFailed(std::move(Err));
60 // Sort blocks into segments.
61 auto Layout = layOutBlocks();
63 // Allocate memory for segments.
64 if (auto Err = allocateSegments(Layout))
65 return Ctx->notifyFailed(std::move(Err));
67 // Notify client that the defined symbols have been assigned addresses.
69 { dbgs() << "Resolving symbols defined in " << G->getName() << "\n"; });
70 Ctx->notifyResolved(*G);
72 auto ExternalSymbols = getExternalSymbolNames();
75 dbgs() << "Issuing lookup for external symbols for " << G->getName()
76 << " (may trigger materialization/linking of other graphs)...\n";
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.
82 // FIXME: Once callee expressions are defined to be sequenced before argument
83 // expressions (c++17) we can simplify all this to:
85 // Ctx->lookup(std::move(UnresolvedExternals),
86 // [Self=std::move(Self)](Expected<AsyncLookupResult> Result) {
87 // Self->linkPhase2(std::move(Self), std::move(Result));
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 {
95 TmpSelf.linkPhase2(std::move(S), std::move(LookupResult),
100 void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self,
101 Expected<AsyncLookupResult> LR,
102 SegmentLayoutMap Layout) {
105 dbgs() << "Starting link phase 2 for graph " << G->getName() << "\n";
108 // If the lookup failed, bail out.
110 return deallocateAndBailOut(LR.takeError());
112 // Assign addresses to external addressables.
113 applyLookupResult(*LR);
115 // Copy block content to working memory.
116 copyBlockContentToWorkingMemory(Layout, *Alloc);
119 dbgs() << "Link graph \"" << G->getName()
120 << "\" before post-allocation passes:\n";
124 if (auto Err = runPasses(Passes.PostAllocationPasses))
125 return deallocateAndBailOut(std::move(Err));
128 dbgs() << "Link graph \"" << G->getName() << "\" before copy-and-fixup:\n";
132 // Fix up block content.
133 if (auto Err = fixUpBlocks(*G))
134 return deallocateAndBailOut(std::move(Err));
137 dbgs() << "Link graph \"" << G->getName() << "\" after copy-and-fixup:\n";
141 if (auto Err = runPasses(Passes.PostFixupPasses))
142 return deallocateAndBailOut(std::move(Err));
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));
151 Alloc->finalizeAsync(std::move(Phase3Continuation));
154 void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self, Error Err) {
157 dbgs() << "Starting link phase 3 for graph " << G->getName() << "\n";
161 return deallocateAndBailOut(std::move(Err));
162 Ctx->notifyFinalized(std::move(Alloc));
164 LLVM_DEBUG({ dbgs() << "Link of graph " << G->getName() << " complete\n"; });
167 Error JITLinkerBase::runPasses(LinkGraphPassList &Passes) {
168 for (auto &P : Passes)
169 if (auto Err = P(*G))
171 return Error::success();
174 JITLinkerBase::SegmentLayoutMap JITLinkerBase::layOutBlocks() {
176 SegmentLayoutMap Layout;
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);
184 SegLists.ZeroFillBlocks.push_back(B);
187 /// Sort blocks within each list.
188 for (auto &KV : Layout) {
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();
199 auto &SegLists = KV.second;
200 llvm::sort(SegLists.ContentBlocks, CompareBlocks);
201 llvm::sort(SegLists.ZeroFillBlocks, CompareBlocks);
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;
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";
223 Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) {
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;
232 uint64_t SegAlign = 1;
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();
242 uint64_t SegZeroFillStart = SegContentSize;
243 uint64_t SegZeroFillEnd = SegZeroFillStart;
245 for (auto *B : SegLists.ZeroFillBlocks) {
246 SegAlign = std::max(SegAlign, B->getAlignment());
247 SegZeroFillEnd = alignToBlock(SegZeroFillEnd, *B);
248 SegZeroFillEnd += B->getSize();
251 Segments[Prot] = {SegAlign, SegContentSize,
252 SegZeroFillEnd - SegZeroFillStart};
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);
262 LLVM_DEBUG(dbgs() << " }\n");
264 if (auto AllocOrErr = Ctx->getMemoryManager().allocate(Segments))
265 Alloc = std::move(*AllocOrErr);
267 return AllocOrErr.takeError();
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";
279 // Update block target addresses.
280 for (auto &KV : Layout) {
281 auto &Prot = KV.first;
282 auto &SL = KV.second;
284 JITTargetAddress NextBlockAddr =
285 Alloc->getTargetMemory(static_cast<sys::Memory::ProtectionFlags>(Prot));
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();
295 return Error::success();
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;
312 return UnresolvedExternals;
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());
325 assert(Sym->getLinkage() == Linkage::Weak &&
326 "Failed to resolve non-weak reference");
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";
335 assert(llvm::all_of(G->external_symbols(),
337 return Sym->getAddress() != 0 ||
338 Sym->getLinkage() == Linkage::Weak;
340 "All strong external symbols should have been resolved by now");
343 void JITLinkerBase::copyBlockContentToWorkingMemory(
344 const SegmentLayoutMap &Layout, JITLinkMemoryManager::Allocation &Alloc) {
346 LLVM_DEBUG(dbgs() << "Copying block content:\n");
347 for (auto &KV : Layout) {
348 auto &Prot = KV.first;
349 auto &SegLayout = KV.second;
352 Alloc.getWorkingMemory(static_cast<sys::Memory::ProtectionFlags>(Prot));
353 char *LastBlockEnd = SegMem.data();
354 char *BlockDataPtr = LastBlockEnd;
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";
364 for (auto *B : SegLayout.ContentBlocks) {
365 LLVM_DEBUG(dbgs() << " " << *B << ":\n");
367 // Pad to alignment/alignment-offset.
368 BlockDataPtr = alignToBlock(BlockDataPtr, *B);
371 dbgs() << " Bumped block pointer to " << (const void *)BlockDataPtr
372 << " to meet block alignment " << B->getAlignment()
373 << " and alignment offset " << B->getAlignmentOffset() << "\n";
376 // Zero pad up to alignment.
378 if (LastBlockEnd != BlockDataPtr)
379 dbgs() << " Zero padding from " << (const void *)LastBlockEnd
380 << " to " << (const void *)BlockDataPtr << "\n";
383 while (LastBlockEnd != BlockDataPtr)
386 // Copy initial block content.
388 dbgs() << " Copying block " << *B << " content, "
389 << B->getContent().size() << " bytes, from "
390 << (const void *)B->getContent().data() << " to "
391 << (const void *)BlockDataPtr << "\n";
393 memcpy(BlockDataPtr, B->getContent().data(), B->getContent().size());
395 // Point the block's content to the fixed up buffer.
396 B->setContent(StringRef(BlockDataPtr, B->getContent().size()));
398 // Update block end pointer.
399 LastBlockEnd = BlockDataPtr + B->getContent().size();
400 BlockDataPtr = LastBlockEnd;
403 // Zero pad the rest of the segment.
405 dbgs() << " Zero padding end of segment from "
406 << (const void *)LastBlockEnd << " to "
407 << (const void *)((char *)SegMem.data() + SegMem.size()) << "\n";
409 while (LastBlockEnd != SegMem.data() + SegMem.size())
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()));
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); });
425 void prune(LinkGraph &G) {
426 std::vector<Symbol *> Worklist;
427 DenseSet<Block *> VisitedBlocks;
429 // Build the initial worklist from all symbols initially live.
430 for (auto *Sym : G.defined_symbols())
432 Worklist.push_back(Sym);
434 // Propagate live flags to all symbols reachable from the initial live set.
435 while (!Worklist.empty()) {
436 auto *Sym = Worklist.back();
439 auto &B = Sym->getBlock();
441 // Skip addressables that we've visited before.
442 if (VisitedBlocks.count(&B))
445 VisitedBlocks.insert(&B);
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());
455 // Collect all the symbols to remove, then remove them.
457 LLVM_DEBUG(dbgs() << "Dead-stripping symbols:\n");
458 std::vector<Symbol *> SymbolsToRemove;
459 for (auto *Sym : G.defined_symbols())
461 SymbolsToRemove.push_back(Sym);
462 for (auto *Sym : SymbolsToRemove) {
463 LLVM_DEBUG(dbgs() << " " << *Sym << "...\n");
464 G.removeDefinedSymbol(*Sym);
468 // Delete any unused blocks.
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");
482 } // end namespace jitlink
483 } // end namespace llvm