LLVM  12.0.0git
JITLinkGeneric.cpp
Go to the documentation of this file.
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 
17 
18 #define DEBUG_TYPE "jitlink"
19 
20 namespace llvm {
21 namespace jitlink {
22 
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),
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,
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: { ");
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
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
This class represents lattice values for constants.
Definition: AllocatorList.h:23
auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object< decltype(std::make_tuple(detail::build_format_adapter(std::forward< Ts >(Vals))...))>
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1491
Error takeError()
Take ownership of the stored error.
Definition: Error.h:557
Tagged union holding either a T or a Error.
Definition: APFloat.h:42
uint64_t JITTargetAddress
Represents an address in the target process&#39;s address space.
Definition: JITSymbol.h:42
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
#define P(N)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:193
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1433
static ErrorSuccess success()
Create a success value.
Definition: Error.h:332
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Error joinErrors(Error E1, Error E2)
Concatenate errors.
Definition: Error.h:429
iterator end()
Definition: DenseMap.h:83
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
#define LLVM_DEBUG(X)
Definition: Debug.h:122