LLVM  10.0.0svn
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  // 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),
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,
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: { ");
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
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
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:1165
Error takeError()
Take ownership of the stored error.
Definition: Error.h:552
Tagged union holding either a T or a Error.
Definition: yaml2obj.h:21
uint64_t JITTargetAddress
Represents an address in the target process&#39;s address space.
Definition: JITSymbol.h:41
#define P(N)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1095
static ErrorSuccess success()
Create a success value.
Definition: Error.h:326
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:336
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:423
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:91
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
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:45
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
#define LLVM_DEBUG(X)
Definition: Debug.h:122