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 #include "EHFrameSupportImpl.h"
15 
18 
19 #define DEBUG_TYPE "jitlink"
20 
21 namespace llvm {
22 namespace jitlink {
23 
25 
26 void JITLinkerBase::linkPhase1(std::unique_ptr<JITLinkerBase> Self) {
27 
28  // Build the atom graph.
29  if (auto GraphOrErr = buildGraph(Ctx->getObjectBuffer()))
30  G = std::move(*GraphOrErr);
31  else
32  return Ctx->notifyFailed(GraphOrErr.takeError());
33  assert(G && "Graph should have been created by buildGraph above");
34 
35  // Prune and optimize the graph.
36  if (auto Err = runPasses(Passes.PrePrunePasses, *G))
37  return Ctx->notifyFailed(std::move(Err));
38 
39  LLVM_DEBUG({
40  dbgs() << "Atom graph \"" << G->getName() << "\" pre-pruning:\n";
41  dumpGraph(dbgs());
42  });
43 
44  prune(*G);
45 
46  LLVM_DEBUG({
47  dbgs() << "Atom graph \"" << G->getName() << "\" post-pruning:\n";
48  dumpGraph(dbgs());
49  });
50 
51  // Run post-pruning passes.
52  if (auto Err = runPasses(Passes.PostPrunePasses, *G))
53  return Ctx->notifyFailed(std::move(Err));
54 
55  // Sort atoms into segments.
56  layOutAtoms();
57 
58  // Allocate memory for segments.
59  if (auto Err = allocateSegments(Layout))
60  return Ctx->notifyFailed(std::move(Err));
61 
62  // Notify client that the defined atoms have been assigned addresses.
63  Ctx->notifyResolved(*G);
64 
65  auto ExternalSymbols = getExternalSymbolNames();
66 
67  // We're about to hand off ownership of ourself to the continuation. Grab a
68  // pointer to the context so that we can call it to initiate the lookup.
69  //
70  // FIXME: Once callee expressions are defined to be sequenced before argument
71  // expressions (c++17) we can simplify all this to:
72  //
73  // Ctx->lookup(std::move(UnresolvedExternals),
74  // [Self=std::move(Self)](Expected<AsyncLookupResult> Result) {
75  // Self->linkPhase2(std::move(Self), std::move(Result));
76  // });
77  //
78  // FIXME: Use move capture once we have c++14.
79  auto *TmpCtx = Ctx.get();
80  auto *UnownedSelf = Self.release();
81  auto Phase2Continuation =
82  [UnownedSelf](Expected<AsyncLookupResult> LookupResult) {
83  std::unique_ptr<JITLinkerBase> Self(UnownedSelf);
84  UnownedSelf->linkPhase2(std::move(Self), std::move(LookupResult));
85  };
86  TmpCtx->lookup(std::move(ExternalSymbols), std::move(Phase2Continuation));
87 }
88 
89 void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self,
91  // If the lookup failed, bail out.
92  if (!LR)
93  return deallocateAndBailOut(LR.takeError());
94 
95  // Assign addresses to external atoms.
96  applyLookupResult(*LR);
97 
98  LLVM_DEBUG({
99  dbgs() << "Atom graph \"" << G->getName() << "\" before copy-and-fixup:\n";
100  dumpGraph(dbgs());
101  });
102 
103  // Copy atom content to working memory and fix up.
104  if (auto Err = copyAndFixUpAllAtoms(Layout, *Alloc))
105  return deallocateAndBailOut(std::move(Err));
106 
107  LLVM_DEBUG({
108  dbgs() << "Atom graph \"" << G->getName() << "\" after copy-and-fixup:\n";
109  dumpGraph(dbgs());
110  });
111 
112  if (auto Err = runPasses(Passes.PostFixupPasses, *G))
113  return deallocateAndBailOut(std::move(Err));
114 
115  // FIXME: Use move capture once we have c++14.
116  auto *UnownedSelf = Self.release();
117  auto Phase3Continuation = [UnownedSelf](Error Err) {
118  std::unique_ptr<JITLinkerBase> Self(UnownedSelf);
119  UnownedSelf->linkPhase3(std::move(Self), std::move(Err));
120  };
121 
122  Alloc->finalizeAsync(std::move(Phase3Continuation));
123 }
124 
125 void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self, Error Err) {
126  if (Err)
127  return deallocateAndBailOut(std::move(Err));
128  Ctx->notifyFinalized(std::move(Alloc));
129 }
130 
131 Error JITLinkerBase::runPasses(AtomGraphPassList &Passes, AtomGraph &G) {
132  for (auto &P : Passes)
133  if (auto Err = P(G))
134  return Err;
135  return Error::success();
136 }
137 
138 void JITLinkerBase::layOutAtoms() {
139  // Group sections by protections, and whether or not they're zero-fill.
140  for (auto &S : G->sections()) {
141 
142  // Skip empty sections.
143  if (S.atoms_empty())
144  continue;
145 
146  auto &SL = Layout[S.getProtectionFlags()];
147  if (S.isZeroFill())
148  SL.ZeroFillSections.push_back(SegmentLayout::SectionLayout(S));
149  else
150  SL.ContentSections.push_back(SegmentLayout::SectionLayout(S));
151  }
152 
153  // Sort sections within the layout by ordinal.
154  {
155  auto CompareByOrdinal = [](const SegmentLayout::SectionLayout &LHS,
156  const SegmentLayout::SectionLayout &RHS) {
157  return LHS.S->getSectionOrdinal() < RHS.S->getSectionOrdinal();
158  };
159  for (auto &KV : Layout) {
160  auto &SL = KV.second;
161  std::sort(SL.ContentSections.begin(), SL.ContentSections.end(),
162  CompareByOrdinal);
163  std::sort(SL.ZeroFillSections.begin(), SL.ZeroFillSections.end(),
164  CompareByOrdinal);
165  }
166  }
167 
168  // Add atoms to the sections.
169  for (auto &KV : Layout) {
170  auto &SL = KV.second;
171  for (auto *SIList : {&SL.ContentSections, &SL.ZeroFillSections}) {
172  for (auto &SI : *SIList) {
173  // First build the set of layout-heads (i.e. "heads" of layout-next
174  // chains) by copying the section atoms, then eliminating any that
175  // appear as layout-next targets.
176  DenseSet<DefinedAtom *> LayoutHeads;
177  for (auto *DA : SI.S->atoms())
178  LayoutHeads.insert(DA);
179 
180  for (auto *DA : SI.S->atoms())
181  if (DA->hasLayoutNext())
182  LayoutHeads.erase(&DA->getLayoutNext());
183 
184  // Next, sort the layout heads by address order.
185  std::vector<DefinedAtom *> OrderedLayoutHeads;
186  OrderedLayoutHeads.reserve(LayoutHeads.size());
187  for (auto *DA : LayoutHeads)
188  OrderedLayoutHeads.push_back(DA);
189 
190  // Now sort the list of layout heads by address.
191  std::sort(OrderedLayoutHeads.begin(), OrderedLayoutHeads.end(),
192  [](const DefinedAtom *LHS, const DefinedAtom *RHS) {
193  return LHS->getAddress() < RHS->getAddress();
194  });
195 
196  // Now populate the SI.Atoms field by appending each of the chains.
197  for (auto *DA : OrderedLayoutHeads) {
198  SI.Atoms.push_back(DA);
199  while (DA->hasLayoutNext()) {
200  auto &Next = DA->getLayoutNext();
201  SI.Atoms.push_back(&Next);
202  DA = &Next;
203  }
204  }
205  }
206  }
207  }
208 
209  LLVM_DEBUG({
210  dbgs() << "Segment ordering:\n";
211  for (auto &KV : Layout) {
212  dbgs() << " Segment "
213  << static_cast<sys::Memory::ProtectionFlags>(KV.first) << ":\n";
214  auto &SL = KV.second;
215  for (auto &SIEntry :
216  {std::make_pair(&SL.ContentSections, "content sections"),
217  std::make_pair(&SL.ZeroFillSections, "zero-fill sections")}) {
218  auto &SIList = *SIEntry.first;
219  dbgs() << " " << SIEntry.second << ":\n";
220  for (auto &SI : SIList) {
221  dbgs() << " " << SI.S->getName() << ":\n";
222  for (auto *DA : SI.Atoms)
223  dbgs() << " " << *DA << "\n";
224  }
225  }
226  }
227  });
228 }
229 
230 Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) {
231 
232  // Compute segment sizes and allocate memory.
233  LLVM_DEBUG(dbgs() << "JIT linker requesting: { ");
235  for (auto &KV : Layout) {
236  auto &Prot = KV.first;
237  auto &SegLayout = KV.second;
238 
239  // Calculate segment content size.
240  size_t SegContentSize = 0;
241  for (auto &SI : SegLayout.ContentSections) {
242  assert(!SI.S->atoms_empty() && "Sections in layout must not be empty");
243  assert(!SI.Atoms.empty() && "Section layouts must not be empty");
244 
245  // Bump to section alignment before processing atoms.
246  SegContentSize = alignTo(SegContentSize, SI.S->getAlignment());
247 
248  for (auto *DA : SI.Atoms) {
249  SegContentSize = alignTo(SegContentSize, DA->getAlignment());
250  SegContentSize += DA->getSize();
251  }
252  }
253 
254  // Get segment content alignment.
255  unsigned SegContentAlign = 1;
256  if (!SegLayout.ContentSections.empty()) {
257  auto &FirstContentSection = SegLayout.ContentSections.front();
258  SegContentAlign =
259  std::max(FirstContentSection.S->getAlignment(),
260  FirstContentSection.Atoms.front()->getAlignment());
261  }
262 
263  // Calculate segment zero-fill size.
264  uint64_t SegZeroFillSize = 0;
265  for (auto &SI : SegLayout.ZeroFillSections) {
266  assert(!SI.S->atoms_empty() && "Sections in layout must not be empty");
267  assert(!SI.Atoms.empty() && "Section layouts must not be empty");
268 
269  // Bump to section alignment before processing atoms.
270  SegZeroFillSize = alignTo(SegZeroFillSize, SI.S->getAlignment());
271 
272  for (auto *DA : SI.Atoms) {
273  SegZeroFillSize = alignTo(SegZeroFillSize, DA->getAlignment());
274  SegZeroFillSize += DA->getSize();
275  }
276  }
277 
278  // Calculate segment zero-fill alignment.
279  uint32_t SegZeroFillAlign = 1;
280 
281  if (!SegLayout.ZeroFillSections.empty()) {
282  auto &FirstZeroFillSection = SegLayout.ZeroFillSections.front();
283  SegZeroFillAlign =
284  std::max(FirstZeroFillSection.S->getAlignment(),
285  FirstZeroFillSection.Atoms.front()->getAlignment());
286  }
287 
288  if (SegContentSize == 0)
289  SegContentAlign = SegZeroFillAlign;
290 
291  if (SegContentAlign % SegZeroFillAlign != 0)
292  return make_error<JITLinkError>("First content atom alignment does not "
293  "accommodate first zero-fill atom "
294  "alignment");
295 
296  Segments[Prot] = {SegContentSize, SegContentAlign, SegZeroFillSize,
297  SegZeroFillAlign};
298 
299  LLVM_DEBUG({
300  dbgs() << (&KV == &*Layout.begin() ? "" : "; ")
301  << static_cast<sys::Memory::ProtectionFlags>(Prot) << ": "
302  << SegContentSize << " content bytes (alignment "
303  << SegContentAlign << ") + " << SegZeroFillSize
304  << " zero-fill bytes (alignment " << SegZeroFillAlign << ")";
305  });
306  }
307  LLVM_DEBUG(dbgs() << " }\n");
308 
309  if (auto AllocOrErr = Ctx->getMemoryManager().allocate(Segments))
310  Alloc = std::move(*AllocOrErr);
311  else
312  return AllocOrErr.takeError();
313 
314  LLVM_DEBUG({
315  dbgs() << "JIT linker got working memory:\n";
316  for (auto &KV : Layout) {
317  auto Prot = static_cast<sys::Memory::ProtectionFlags>(KV.first);
318  dbgs() << " " << Prot << ": "
319  << (const void *)Alloc->getWorkingMemory(Prot).data() << "\n";
320  }
321  });
322 
323  // Update atom target addresses.
324  for (auto &KV : Layout) {
325  auto &Prot = KV.first;
326  auto &SL = KV.second;
327 
328  JITTargetAddress AtomTargetAddr =
329  Alloc->getTargetMemory(static_cast<sys::Memory::ProtectionFlags>(Prot));
330 
331  for (auto *SIList : {&SL.ContentSections, &SL.ZeroFillSections})
332  for (auto &SI : *SIList) {
333  AtomTargetAddr = alignTo(AtomTargetAddr, SI.S->getAlignment());
334  for (auto *DA : SI.Atoms) {
335  AtomTargetAddr = alignTo(AtomTargetAddr, DA->getAlignment());
336  DA->setAddress(AtomTargetAddr);
337  AtomTargetAddr += DA->getSize();
338  }
339  }
340  }
341 
342  return Error::success();
343 }
344 
345 DenseSet<StringRef> JITLinkerBase::getExternalSymbolNames() const {
346  // Identify unresolved external atoms.
347  DenseSet<StringRef> UnresolvedExternals;
348  for (auto *DA : G->external_atoms()) {
349  assert(DA->getAddress() == 0 &&
350  "External has already been assigned an address");
351  assert(DA->getName() != StringRef() && DA->getName() != "" &&
352  "Externals must be named");
353  UnresolvedExternals.insert(DA->getName());
354  }
355  return UnresolvedExternals;
356 }
357 
358 void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
359  for (auto &KV : Result) {
360  Atom &A = G->getAtomByName(KV.first);
361  assert(A.getAddress() == 0 && "Atom already resolved");
362  A.setAddress(KV.second.getAddress());
363  }
364 
365  LLVM_DEBUG({
366  dbgs() << "Externals after applying lookup result:\n";
367  for (auto *A : G->external_atoms())
368  dbgs() << " " << A->getName() << ": "
369  << formatv("{0:x16}", A->getAddress()) << "\n";
370  });
372  [](Atom *A) { return A->getAddress() != 0; }) &&
373  "All atoms should have been resolved by this point");
374 }
375 
376 void JITLinkerBase::deallocateAndBailOut(Error Err) {
377  assert(Err && "Should not be bailing out on success value");
378  assert(Alloc && "can not call deallocateAndBailOut before allocation");
379  Ctx->notifyFailed(joinErrors(std::move(Err), Alloc->deallocate()));
380 }
381 
382 void JITLinkerBase::dumpGraph(raw_ostream &OS) {
383  assert(G && "Graph is not set yet");
384  G->dump(dbgs(), [this](Edge::Kind K) { return getEdgeKindName(K); });
385 }
386 
387 void prune(AtomGraph &G) {
388  std::vector<DefinedAtom *> Worklist;
390 
391  // Build the initial worklist from all atoms initially live.
392  for (auto *DA : G.defined_atoms()) {
393  if (!DA->isLive() || DA->shouldDiscard())
394  continue;
395 
396  for (auto &E : DA->edges()) {
397  if (!E.getTarget().isDefined())
398  continue;
399 
400  auto &EDT = static_cast<DefinedAtom &>(E.getTarget());
401 
402  if (EDT.shouldDiscard())
403  EdgesToUpdate[&EDT].push_back(&E);
404  else if (E.isKeepAlive() && !EDT.isLive())
405  Worklist.push_back(&EDT);
406  }
407  }
408 
409  // Propagate live flags to all atoms reachable from the initial live set.
410  while (!Worklist.empty()) {
411  DefinedAtom &NextLive = *Worklist.back();
412  Worklist.pop_back();
413 
414  assert(!NextLive.shouldDiscard() &&
415  "should-discard nodes should never make it into the worklist");
416 
417  // If this atom has already been marked as live, or is marked to be
418  // discarded, then skip it.
419  if (NextLive.isLive())
420  continue;
421 
422  // Otherwise set it as live and add any non-live atoms that it points to
423  // to the worklist.
424  NextLive.setLive(true);
425 
426  for (auto &E : NextLive.edges()) {
427  if (!E.getTarget().isDefined())
428  continue;
429 
430  auto &EDT = static_cast<DefinedAtom &>(E.getTarget());
431 
432  if (EDT.shouldDiscard())
433  EdgesToUpdate[&EDT].push_back(&E);
434  else if (E.isKeepAlive() && !EDT.isLive())
435  Worklist.push_back(&EDT);
436  }
437  }
438 
439  // Collect atoms to remove, then remove them from the graph.
440  std::vector<DefinedAtom *> AtomsToRemove;
441  for (auto *DA : G.defined_atoms())
442  if (DA->shouldDiscard() || !DA->isLive())
443  AtomsToRemove.push_back(DA);
444 
445  LLVM_DEBUG(dbgs() << "Pruning atoms:\n");
446  for (auto *DA : AtomsToRemove) {
447  LLVM_DEBUG(dbgs() << " " << *DA << "... ");
448 
449  // Check whether we need to replace this atom with an external atom.
450  //
451  // We replace if all of the following hold:
452  // (1) The atom is marked should-discard,
453  // (2) it has live edges (i.e. edges from live atoms) pointing to it.
454  //
455  // Otherwise we simply delete the atom.
456 
457  G.removeDefinedAtom(*DA);
458 
459  auto EdgesToUpdateItr = EdgesToUpdate.find(DA);
460  if (EdgesToUpdateItr != EdgesToUpdate.end()) {
461  auto &ExternalReplacement = G.addExternalAtom(DA->getName());
462  for (auto *EdgeToUpdate : EdgesToUpdateItr->second)
463  EdgeToUpdate->setTarget(ExternalReplacement);
464  LLVM_DEBUG(dbgs() << "replaced with " << ExternalReplacement << "\n");
465  } else
466  LLVM_DEBUG(dbgs() << "deleted\n");
467  }
468 
469  // Finally, discard any absolute symbols that were marked should-discard.
470  {
471  std::vector<Atom *> AbsoluteAtomsToRemove;
472  for (auto *A : G.absolute_atoms())
473  if (A->shouldDiscard() || A->isLive())
474  AbsoluteAtomsToRemove.push_back(A);
475  for (auto *A : AbsoluteAtomsToRemove)
476  G.removeAbsoluteAtom(*A);
477  }
478 }
479 
480 } // end namespace jitlink
481 } // end namespace llvm
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool erase(const ValueT &V)
Definition: DenseSet.h:95
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:1192
uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the next integer (mod 2**64) that is greater than or equal to Value and is a multiple of Alig...
Definition: MathExtras.h:689
Error takeError()
Take ownership of the stored error.
Definition: Error.h:552
Tagged union holding either a T or a Error.
Definition: CachePruning.h:22
uint64_t JITTargetAddress
Represents an address in the target process&#39;s address space.
Definition: JITSymbol.h:40
#define P(N)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:187
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1122
static ErrorSuccess success()
Create a success value.
Definition: Error.h:326
size_type size() const
Definition: DenseSet.h:75
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
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