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  uint32_t SegContentAlign = 1;
242  for (auto &SI : SegLayout.ContentSections) {
243  assert(!SI.S->atoms_empty() && "Sections in layout must not be empty");
244  assert(!SI.Atoms.empty() && "Section layouts must not be empty");
245 
246  // Bump to section alignment before processing atoms.
247  SegContentSize = alignTo(SegContentSize, SI.S->getAlignment());
248  SegContentAlign = std::max(SegContentAlign, SI.S->getAlignment());
249 
250  for (auto *DA : SI.Atoms) {
251  SegContentSize = alignTo(SegContentSize, DA->getAlignment());
252  SegContentSize += DA->getSize();
253  SegContentAlign = std::max(SegContentAlign, DA->getAlignment());
254  }
255  }
256 
257  // Calculate segment zero-fill size.
258  uint64_t SegZeroFillSize = 0;
259  uint32_t SegZeroFillAlign = 1;
260 
261  for (auto &SI : SegLayout.ZeroFillSections) {
262  assert(!SI.S->atoms_empty() && "Sections in layout must not be empty");
263  assert(!SI.Atoms.empty() && "Section layouts must not be empty");
264 
265  // Bump to section alignment before processing atoms.
266  SegZeroFillSize = alignTo(SegZeroFillSize, SI.S->getAlignment());
267  SegZeroFillAlign = std::max(SegZeroFillAlign, SI.S->getAlignment());
268 
269  for (auto *DA : SI.Atoms) {
270  SegZeroFillSize = alignTo(SegZeroFillSize, DA->getAlignment());
271  SegZeroFillSize += DA->getSize();
272  SegZeroFillAlign = std::max(SegZeroFillAlign, SI.S->getAlignment());
273  }
274  }
275 
276  assert(isPowerOf2_32(SegContentAlign) &&
277  "Expected content alignment to be power of 2");
278  assert(isPowerOf2_32(SegZeroFillAlign) &&
279  "Expected zero-fill alignment to be power of 2");
280  // Round content alignment up to segment alignment.
281  SegContentAlign = std::max(SegContentAlign, SegZeroFillAlign);
282 
283  Segments[Prot] = {SegContentSize, SegContentAlign, SegZeroFillSize,
284  SegZeroFillAlign};
285 
286  LLVM_DEBUG({
287  dbgs() << (&KV == &*Layout.begin() ? "" : "; ")
288  << static_cast<sys::Memory::ProtectionFlags>(Prot) << ": "
289  << SegContentSize << " content bytes (alignment "
290  << SegContentAlign << ") + " << SegZeroFillSize
291  << " zero-fill bytes (alignment " << SegZeroFillAlign << ")";
292  });
293  }
294  LLVM_DEBUG(dbgs() << " }\n");
295 
296  if (auto AllocOrErr = Ctx->getMemoryManager().allocate(Segments))
297  Alloc = std::move(*AllocOrErr);
298  else
299  return AllocOrErr.takeError();
300 
301  LLVM_DEBUG({
302  dbgs() << "JIT linker got working memory:\n";
303  for (auto &KV : Layout) {
304  auto Prot = static_cast<sys::Memory::ProtectionFlags>(KV.first);
305  dbgs() << " " << Prot << ": "
306  << (const void *)Alloc->getWorkingMemory(Prot).data() << "\n";
307  }
308  });
309 
310  // Update atom target addresses.
311  for (auto &KV : Layout) {
312  auto &Prot = KV.first;
313  auto &SL = KV.second;
314 
315  JITTargetAddress AtomTargetAddr =
316  Alloc->getTargetMemory(static_cast<sys::Memory::ProtectionFlags>(Prot));
317 
318  for (auto *SIList : {&SL.ContentSections, &SL.ZeroFillSections})
319  for (auto &SI : *SIList) {
320  AtomTargetAddr = alignTo(AtomTargetAddr, SI.S->getAlignment());
321  for (auto *DA : SI.Atoms) {
322  AtomTargetAddr = alignTo(AtomTargetAddr, DA->getAlignment());
323  DA->setAddress(AtomTargetAddr);
324  AtomTargetAddr += DA->getSize();
325  }
326  }
327  }
328 
329  return Error::success();
330 }
331 
332 DenseSet<StringRef> JITLinkerBase::getExternalSymbolNames() const {
333  // Identify unresolved external atoms.
334  DenseSet<StringRef> UnresolvedExternals;
335  for (auto *DA : G->external_atoms()) {
336  assert(DA->getAddress() == 0 &&
337  "External has already been assigned an address");
338  assert(DA->getName() != StringRef() && DA->getName() != "" &&
339  "Externals must be named");
340  UnresolvedExternals.insert(DA->getName());
341  }
342  return UnresolvedExternals;
343 }
344 
345 void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
346  for (auto &KV : Result) {
347  Atom &A = G->getAtomByName(KV.first);
348  assert(A.getAddress() == 0 && "Atom already resolved");
349  A.setAddress(KV.second.getAddress());
350  }
351 
352  LLVM_DEBUG({
353  dbgs() << "Externals after applying lookup result:\n";
354  for (auto *A : G->external_atoms())
355  dbgs() << " " << A->getName() << ": "
356  << formatv("{0:x16}", A->getAddress()) << "\n";
357  });
359  [](Atom *A) { return A->getAddress() != 0; }) &&
360  "All atoms should have been resolved by this point");
361 }
362 
363 void JITLinkerBase::deallocateAndBailOut(Error Err) {
364  assert(Err && "Should not be bailing out on success value");
365  assert(Alloc && "can not call deallocateAndBailOut before allocation");
366  Ctx->notifyFailed(joinErrors(std::move(Err), Alloc->deallocate()));
367 }
368 
369 void JITLinkerBase::dumpGraph(raw_ostream &OS) {
370  assert(G && "Graph is not set yet");
371  G->dump(dbgs(), [this](Edge::Kind K) { return getEdgeKindName(K); });
372 }
373 
374 void prune(AtomGraph &G) {
375  std::vector<DefinedAtom *> Worklist;
377 
378  // Build the initial worklist from all atoms initially live.
379  for (auto *DA : G.defined_atoms()) {
380  if (!DA->isLive() || DA->shouldDiscard())
381  continue;
382 
383  for (auto &E : DA->edges()) {
384  if (!E.getTarget().isDefined())
385  continue;
386 
387  auto &EDT = static_cast<DefinedAtom &>(E.getTarget());
388 
389  if (EDT.shouldDiscard())
390  EdgesToUpdate[&EDT].push_back(&E);
391  else if (E.isKeepAlive() && !EDT.isLive())
392  Worklist.push_back(&EDT);
393  }
394  }
395 
396  // Propagate live flags to all atoms reachable from the initial live set.
397  while (!Worklist.empty()) {
398  DefinedAtom &NextLive = *Worklist.back();
399  Worklist.pop_back();
400 
401  assert(!NextLive.shouldDiscard() &&
402  "should-discard nodes should never make it into the worklist");
403 
404  // If this atom has already been marked as live, or is marked to be
405  // discarded, then skip it.
406  if (NextLive.isLive())
407  continue;
408 
409  // Otherwise set it as live and add any non-live atoms that it points to
410  // to the worklist.
411  NextLive.setLive(true);
412 
413  for (auto &E : NextLive.edges()) {
414  if (!E.getTarget().isDefined())
415  continue;
416 
417  auto &EDT = static_cast<DefinedAtom &>(E.getTarget());
418 
419  if (EDT.shouldDiscard())
420  EdgesToUpdate[&EDT].push_back(&E);
421  else if (E.isKeepAlive() && !EDT.isLive())
422  Worklist.push_back(&EDT);
423  }
424  }
425 
426  // Collect atoms to remove, then remove them from the graph.
427  std::vector<DefinedAtom *> AtomsToRemove;
428  for (auto *DA : G.defined_atoms())
429  if (DA->shouldDiscard() || !DA->isLive())
430  AtomsToRemove.push_back(DA);
431 
432  LLVM_DEBUG(dbgs() << "Pruning atoms:\n");
433  for (auto *DA : AtomsToRemove) {
434  LLVM_DEBUG(dbgs() << " " << *DA << "... ");
435 
436  // Check whether we need to replace this atom with an external atom.
437  //
438  // We replace if all of the following hold:
439  // (1) The atom is marked should-discard,
440  // (2) it has live edges (i.e. edges from live atoms) pointing to it.
441  //
442  // Otherwise we simply delete the atom.
443 
444  G.removeDefinedAtom(*DA);
445 
446  auto EdgesToUpdateItr = EdgesToUpdate.find(DA);
447  if (EdgesToUpdateItr != EdgesToUpdate.end()) {
448  auto &ExternalReplacement = G.addExternalAtom(DA->getName());
449  for (auto *EdgeToUpdate : EdgesToUpdateItr->second)
450  EdgeToUpdate->setTarget(ExternalReplacement);
451  LLVM_DEBUG(dbgs() << "replaced with " << ExternalReplacement << "\n");
452  } else
453  LLVM_DEBUG(dbgs() << "deleted\n");
454  }
455 
456  // Finally, discard any absolute symbols that were marked should-discard.
457  {
458  std::vector<Atom *> AbsoluteAtomsToRemove;
459  for (auto *A : G.absolute_atoms())
460  if (A->shouldDiscard() || A->isLive())
461  AbsoluteAtomsToRemove.push_back(A);
462  for (auto *A : AbsoluteAtomsToRemove)
463  G.removeAbsoluteAtom(*A);
464  }
465 }
466 
467 } // end namespace jitlink
468 } // 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: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)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:428
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:1095
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
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:133
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