LLVM  14.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({
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),
108  [S = std::move(Self), L = std::move(Layout)](
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,
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: { ");
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
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 
365  LLVM_DEBUG({
366  dbgs() << " Processing segment "
367  << static_cast<sys::Memory::ProtectionFlags>(Prot) << " [ "
368  << (const void *)SegMem.data() << " .. "
369  << (const void *)((char *)SegMem.data() + SegMem.size())
370  << " ]\n Processing content sections:\n";
371  });
372 
373  if (SegLayout.ContentBlocks.empty()) {
374  LLVM_DEBUG(dbgs() << " No content blocks.\n");
375  continue;
376  }
377 
378  size_t BlockOffset = 0;
379  size_t LastBlockEnd = 0;
380 
381  for (auto *B : SegLayout.ContentBlocks) {
382  LLVM_DEBUG(dbgs() << " " << *B << ":\n");
383 
384  // Pad to alignment/alignment-offset.
385  BlockOffset = alignToBlock(BlockOffset, *B);
386 
387  LLVM_DEBUG({
388  dbgs() << " Bumped block offset to "
389  << formatv("{0:x}", BlockOffset) << " to meet block alignment "
390  << B->getAlignment() << " and alignment offset "
391  << B->getAlignmentOffset() << "\n";
392  });
393 
394  // Zero pad up to alignment.
395  LLVM_DEBUG({
396  if (LastBlockEnd != BlockOffset)
397  dbgs() << " Zero padding from " << formatv("{0:x}", LastBlockEnd)
398  << " to " << formatv("{0:x}", BlockOffset) << "\n";
399  });
400 
401  for (; LastBlockEnd != BlockOffset; ++LastBlockEnd)
402  *(SegMem.data() + LastBlockEnd) = 0;
403 
404  // Copy initial block content.
405  LLVM_DEBUG({
406  dbgs() << " Copying block " << *B << " content, "
407  << B->getContent().size() << " bytes, from "
408  << (const void *)B->getContent().data() << " to offset "
409  << formatv("{0:x}", BlockOffset) << "\n";
410  });
411  memcpy(SegMem.data() + BlockOffset, B->getContent().data(),
412  B->getContent().size());
413 
414  // Point the block's content to the fixed up buffer.
415  B->setMutableContent(
416  {SegMem.data() + BlockOffset, B->getContent().size()});
417 
418  // Update block end pointer.
419  LastBlockEnd = BlockOffset + B->getContent().size();
420  BlockOffset = LastBlockEnd;
421  }
422 
423  // Zero pad the rest of the segment.
424  LLVM_DEBUG({
425  dbgs() << " Zero padding end of segment from offset "
426  << formatv("{0:x}", LastBlockEnd) << " to "
427  << formatv("{0:x}", SegMem.size()) << "\n";
428  });
429  for (; LastBlockEnd != SegMem.size(); ++LastBlockEnd)
430  *(SegMem.data() + LastBlockEnd) = 0;
431  }
432 }
433 
434 void JITLinkerBase::deallocateAndBailOut(Error Err) {
435  assert(Err && "Should not be bailing out on success value");
436  assert(Alloc && "can not call deallocateAndBailOut before allocation");
437  Ctx->notifyFailed(joinErrors(std::move(Err), Alloc->deallocate()));
438 }
439 
440 void prune(LinkGraph &G) {
441  std::vector<Symbol *> Worklist;
442  DenseSet<Block *> VisitedBlocks;
443 
444  // Build the initial worklist from all symbols initially live.
445  for (auto *Sym : G.defined_symbols())
446  if (Sym->isLive())
447  Worklist.push_back(Sym);
448 
449  // Propagate live flags to all symbols reachable from the initial live set.
450  while (!Worklist.empty()) {
451  auto *Sym = Worklist.back();
452  Worklist.pop_back();
453 
454  auto &B = Sym->getBlock();
455 
456  // Skip addressables that we've visited before.
457  if (VisitedBlocks.count(&B))
458  continue;
459 
460  VisitedBlocks.insert(&B);
461 
462  for (auto &E : Sym->getBlock().edges()) {
463  // If the edge target is a defined symbol that is being newly marked live
464  // then add it to the worklist.
465  if (E.getTarget().isDefined() && !E.getTarget().isLive())
466  Worklist.push_back(&E.getTarget());
467 
468  // Mark the target live.
469  E.getTarget().setLive(true);
470  }
471  }
472 
473  // Collect all defined symbols to remove, then remove them.
474  {
475  LLVM_DEBUG(dbgs() << "Dead-stripping defined symbols:\n");
476  std::vector<Symbol *> SymbolsToRemove;
477  for (auto *Sym : G.defined_symbols())
478  if (!Sym->isLive())
479  SymbolsToRemove.push_back(Sym);
480  for (auto *Sym : SymbolsToRemove) {
481  LLVM_DEBUG(dbgs() << " " << *Sym << "...\n");
482  G.removeDefinedSymbol(*Sym);
483  }
484  }
485 
486  // Delete any unused blocks.
487  {
488  LLVM_DEBUG(dbgs() << "Dead-stripping blocks:\n");
489  std::vector<Block *> BlocksToRemove;
490  for (auto *B : G.blocks())
491  if (!VisitedBlocks.count(B))
492  BlocksToRemove.push_back(B);
493  for (auto *B : BlocksToRemove) {
494  LLVM_DEBUG(dbgs() << " " << *B << "...\n");
495  G.removeBlock(*B);
496  }
497  }
498 
499  // Collect all external symbols to remove, then remove them.
500  {
501  LLVM_DEBUG(dbgs() << "Removing unused external symbols:\n");
502  std::vector<Symbol *> SymbolsToRemove;
503  for (auto *Sym : G.external_symbols())
504  if (!Sym->isLive())
505  SymbolsToRemove.push_back(Sym);
506  for (auto *Sym : SymbolsToRemove) {
507  LLVM_DEBUG(dbgs() << " " << *Sym << "...\n");
508  G.removeExternalSymbol(*Sym);
509  }
510  }
511 }
512 
513 } // end namespace jitlink
514 } // end namespace llvm
MemoryBuffer.h
BinaryStreamReader.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::lltok::Error
@ Error
Definition: LLToken.h:21
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::Error::success
static ErrorSuccess success()
Create a success value.
Definition: Error.h:331
Passes
const char * Passes
Definition: PassBuilderBindings.cpp:46
llvm::Expected
Tagged union holding either a T or a Error.
Definition: APFloat.h:42
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl::count
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
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::formatv
auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object< decltype(std::make_tuple(detail::build_format_adapter(std::forward< Ts >(Vals))...))>
Definition: FormatVariadic.h:250
llvm::orc::tpctypes::LookupResult
std::vector< JITTargetAddress > LookupResult
Definition: TargetProcessControlTypes.h:144
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::sys::Memory::ProtectionFlags
ProtectionFlags
Definition: Memory.h:54
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::DenseSet< Block * >
uint64_t
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DenseMap
Definition: DenseMap.h:714
llvm::joinErrors
Error joinErrors(Error E1, Error E2)
Concatenate errors.
Definition: Error.h:428
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
memcpy
<%struct.s * > cast struct s *S to sbyte *< sbyte * > sbyte uint cast struct s *agg result to sbyte *< sbyte * > sbyte uint cast struct s *memtmp to sbyte *< sbyte * > sbyte uint ret void llc ends up issuing two memcpy or custom lower memcpy(of small size) to be ldmia/stmia. I think option 2 is better but the current register allocator cannot allocate a chunk of registers at a time. A feasible temporary solution is to use specific physical registers at the lowering time for small(<
llvm::pdb::PDB_TableType::Segments
@ Segments
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::Error
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1492
llvm::JITTargetAddress
uint64_t JITTargetAddress
Represents an address in the target process's address space.
Definition: JITSymbol.h:42
llvm::Expected::takeError
Error takeError()
Take ownership of the stored error.
Definition: Error.h:589
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
JITLinkGeneric.h