xref: /llvm-project/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp (revision 68774edcd65a310aadbaaffa7a63a416eef7cede)
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 
16 #include "llvm/Support/BinaryStreamReader.h"
17 #include "llvm/Support/MemoryBuffer.h"
18 
19 #define DEBUG_TYPE "jitlink"
20 
21 namespace llvm {
22 namespace jitlink {
23 
24 JITLinkerBase::~JITLinkerBase() {}
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,
90                                Expected<AsyncLookupResult> LR) {
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       llvm::sort(SL.ContentSections, CompareByOrdinal);
162       llvm::sort(SL.ZeroFillSections, CompareByOrdinal);
163     }
164   }
165 
166   // Add atoms to the sections.
167   for (auto &KV : Layout) {
168     auto &SL = KV.second;
169     for (auto *SIList : {&SL.ContentSections, &SL.ZeroFillSections}) {
170       for (auto &SI : *SIList) {
171         // First build the set of layout-heads (i.e. "heads" of layout-next
172         // chains) by copying the section atoms, then eliminating any that
173         // appear as layout-next targets.
174         DenseSet<DefinedAtom *> LayoutHeads;
175         for (auto *DA : SI.S->atoms())
176           LayoutHeads.insert(DA);
177 
178         for (auto *DA : SI.S->atoms())
179           if (DA->hasLayoutNext())
180             LayoutHeads.erase(&DA->getLayoutNext());
181 
182         // Next, sort the layout heads by address order.
183         std::vector<DefinedAtom *> OrderedLayoutHeads;
184         OrderedLayoutHeads.reserve(LayoutHeads.size());
185         for (auto *DA : LayoutHeads)
186           OrderedLayoutHeads.push_back(DA);
187 
188         // Now sort the list of layout heads by address.
189         llvm::sort(OrderedLayoutHeads,
190                    [](const DefinedAtom *LHS, const DefinedAtom *RHS) {
191                      return LHS->getAddress() < RHS->getAddress();
192                    });
193 
194         // Now populate the SI.Atoms field by appending each of the chains.
195         for (auto *DA : OrderedLayoutHeads) {
196           SI.Atoms.push_back(DA);
197           while (DA->hasLayoutNext()) {
198             auto &Next = DA->getLayoutNext();
199             SI.Atoms.push_back(&Next);
200             DA = &Next;
201           }
202         }
203       }
204     }
205   }
206 
207   LLVM_DEBUG({
208     dbgs() << "Segment ordering:\n";
209     for (auto &KV : Layout) {
210       dbgs() << "  Segment "
211              << static_cast<sys::Memory::ProtectionFlags>(KV.first) << ":\n";
212       auto &SL = KV.second;
213       for (auto &SIEntry :
214            {std::make_pair(&SL.ContentSections, "content sections"),
215             std::make_pair(&SL.ZeroFillSections, "zero-fill sections")}) {
216         auto &SIList = *SIEntry.first;
217         dbgs() << "    " << SIEntry.second << ":\n";
218         for (auto &SI : SIList) {
219           dbgs() << "      " << SI.S->getName() << ":\n";
220           for (auto *DA : SI.Atoms)
221             dbgs() << "        " << *DA << "\n";
222         }
223       }
224     }
225   });
226 }
227 
228 Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) {
229 
230   // Compute segment sizes and allocate memory.
231   LLVM_DEBUG(dbgs() << "JIT linker requesting: { ");
232   JITLinkMemoryManager::SegmentsRequestMap Segments;
233   for (auto &KV : Layout) {
234     auto &Prot = KV.first;
235     auto &SegLayout = KV.second;
236 
237     // Calculate segment content size.
238     size_t SegContentSize = 0;
239     for (auto &SI : SegLayout.ContentSections) {
240       assert(!SI.S->atoms_empty() && "Sections in layout must not be empty");
241       assert(!SI.Atoms.empty() && "Section layouts must not be empty");
242 
243       // Bump to section alignment before processing atoms.
244       SegContentSize = alignTo(SegContentSize, SI.S->getAlignment());
245 
246       for (auto *DA : SI.Atoms) {
247         SegContentSize = alignTo(SegContentSize, DA->getAlignment());
248         SegContentSize += DA->getSize();
249       }
250     }
251 
252     // Get segment content alignment.
253     unsigned SegContentAlign = 1;
254     if (!SegLayout.ContentSections.empty()) {
255       auto &FirstContentSection = SegLayout.ContentSections.front();
256       SegContentAlign =
257           std::max(FirstContentSection.S->getAlignment(),
258                    FirstContentSection.Atoms.front()->getAlignment());
259     }
260 
261     // Calculate segment zero-fill size.
262     uint64_t SegZeroFillSize = 0;
263     for (auto &SI : SegLayout.ZeroFillSections) {
264       assert(!SI.S->atoms_empty() && "Sections in layout must not be empty");
265       assert(!SI.Atoms.empty() && "Section layouts must not be empty");
266 
267       // Bump to section alignment before processing atoms.
268       SegZeroFillSize = alignTo(SegZeroFillSize, SI.S->getAlignment());
269 
270       for (auto *DA : SI.Atoms) {
271         SegZeroFillSize = alignTo(SegZeroFillSize, DA->getAlignment());
272         SegZeroFillSize += DA->getSize();
273       }
274     }
275 
276     // Calculate segment zero-fill alignment.
277     uint32_t SegZeroFillAlign = 1;
278 
279     if (!SegLayout.ZeroFillSections.empty()) {
280       auto &FirstZeroFillSection = SegLayout.ZeroFillSections.front();
281       SegZeroFillAlign =
282           std::max(FirstZeroFillSection.S->getAlignment(),
283                    FirstZeroFillSection.Atoms.front()->getAlignment());
284     }
285 
286     if (SegContentSize == 0)
287       SegContentAlign = SegZeroFillAlign;
288 
289     if (SegContentAlign % SegZeroFillAlign != 0)
290       return make_error<JITLinkError>("First content atom alignment does not "
291                                       "accommodate first zero-fill atom "
292                                       "alignment");
293 
294     Segments[Prot] = {SegContentSize, SegContentAlign, SegZeroFillSize,
295                       SegZeroFillAlign};
296 
297     LLVM_DEBUG({
298       dbgs() << (&KV == &*Layout.begin() ? "" : "; ")
299              << static_cast<sys::Memory::ProtectionFlags>(Prot) << ": "
300              << SegContentSize << " content bytes (alignment "
301              << SegContentAlign << ") + " << SegZeroFillSize
302              << " zero-fill bytes (alignment " << SegZeroFillAlign << ")";
303     });
304   }
305   LLVM_DEBUG(dbgs() << " }\n");
306 
307   if (auto AllocOrErr = Ctx->getMemoryManager().allocate(Segments))
308     Alloc = std::move(*AllocOrErr);
309   else
310     return AllocOrErr.takeError();
311 
312   LLVM_DEBUG({
313     dbgs() << "JIT linker got working memory:\n";
314     for (auto &KV : Layout) {
315       auto Prot = static_cast<sys::Memory::ProtectionFlags>(KV.first);
316       dbgs() << "  " << Prot << ": "
317              << (const void *)Alloc->getWorkingMemory(Prot).data() << "\n";
318     }
319   });
320 
321   // Update atom target addresses.
322   for (auto &KV : Layout) {
323     auto &Prot = KV.first;
324     auto &SL = KV.second;
325 
326     JITTargetAddress AtomTargetAddr =
327         Alloc->getTargetMemory(static_cast<sys::Memory::ProtectionFlags>(Prot));
328 
329     for (auto *SIList : {&SL.ContentSections, &SL.ZeroFillSections})
330       for (auto &SI : *SIList) {
331         AtomTargetAddr = alignTo(AtomTargetAddr, SI.S->getAlignment());
332         for (auto *DA : SI.Atoms) {
333           AtomTargetAddr = alignTo(AtomTargetAddr, DA->getAlignment());
334           DA->setAddress(AtomTargetAddr);
335           AtomTargetAddr += DA->getSize();
336         }
337       }
338   }
339 
340   return Error::success();
341 }
342 
343 DenseSet<StringRef> JITLinkerBase::getExternalSymbolNames() const {
344   // Identify unresolved external atoms.
345   DenseSet<StringRef> UnresolvedExternals;
346   for (auto *DA : G->external_atoms()) {
347     assert(DA->getAddress() == 0 &&
348            "External has already been assigned an address");
349     assert(DA->getName() != StringRef() && DA->getName() != "" &&
350            "Externals must be named");
351     UnresolvedExternals.insert(DA->getName());
352   }
353   return UnresolvedExternals;
354 }
355 
356 void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
357   for (auto &KV : Result) {
358     Atom &A = G->getAtomByName(KV.first);
359     assert(A.getAddress() == 0 && "Atom already resolved");
360     A.setAddress(KV.second.getAddress());
361   }
362 
363   LLVM_DEBUG({
364     dbgs() << "Externals after applying lookup result:\n";
365     for (auto *A : G->external_atoms())
366       dbgs() << "  " << A->getName() << ": "
367              << formatv("{0:x16}", A->getAddress()) << "\n";
368   });
369   assert(llvm::all_of(G->external_atoms(),
370                       [](Atom *A) { return A->getAddress() != 0; }) &&
371          "All atoms should have been resolved by this point");
372 }
373 
374 void JITLinkerBase::deallocateAndBailOut(Error Err) {
375   assert(Err && "Should not be bailing out on success value");
376   assert(Alloc && "can not call deallocateAndBailOut before allocation");
377   Ctx->notifyFailed(joinErrors(std::move(Err), Alloc->deallocate()));
378 }
379 
380 void JITLinkerBase::dumpGraph(raw_ostream &OS) {
381   assert(G && "Graph is not set yet");
382   G->dump(dbgs(), [this](Edge::Kind K) { return getEdgeKindName(K); });
383 }
384 
385 void prune(AtomGraph &G) {
386   std::vector<DefinedAtom *> Worklist;
387   DenseMap<DefinedAtom *, std::vector<Edge *>> EdgesToUpdate;
388 
389   // Build the initial worklist from all atoms initially live.
390   for (auto *DA : G.defined_atoms()) {
391     if (!DA->isLive() || DA->shouldDiscard())
392       continue;
393 
394     for (auto &E : DA->edges()) {
395       if (!E.getTarget().isDefined())
396         continue;
397 
398       auto &EDT = static_cast<DefinedAtom &>(E.getTarget());
399 
400       if (EDT.shouldDiscard())
401         EdgesToUpdate[&EDT].push_back(&E);
402       else if (E.isKeepAlive() && !EDT.isLive())
403         Worklist.push_back(&EDT);
404     }
405   }
406 
407   // Propagate live flags to all atoms reachable from the initial live set.
408   while (!Worklist.empty()) {
409     DefinedAtom &NextLive = *Worklist.back();
410     Worklist.pop_back();
411 
412     assert(!NextLive.shouldDiscard() &&
413            "should-discard nodes should never make it into the worklist");
414 
415     // If this atom has already been marked as live, or is marked to be
416     // discarded, then skip it.
417     if (NextLive.isLive())
418       continue;
419 
420     // Otherwise set it as live and add any non-live atoms that it points to
421     // to the worklist.
422     NextLive.setLive(true);
423 
424     for (auto &E : NextLive.edges()) {
425       if (!E.getTarget().isDefined())
426         continue;
427 
428       auto &EDT = static_cast<DefinedAtom &>(E.getTarget());
429 
430       if (EDT.shouldDiscard())
431         EdgesToUpdate[&EDT].push_back(&E);
432       else if (E.isKeepAlive() && !EDT.isLive())
433         Worklist.push_back(&EDT);
434     }
435   }
436 
437   // Collect atoms to remove, then remove them from the graph.
438   std::vector<DefinedAtom *> AtomsToRemove;
439   for (auto *DA : G.defined_atoms())
440     if (DA->shouldDiscard() || !DA->isLive())
441       AtomsToRemove.push_back(DA);
442 
443   LLVM_DEBUG(dbgs() << "Pruning atoms:\n");
444   for (auto *DA : AtomsToRemove) {
445     LLVM_DEBUG(dbgs() << "  " << *DA << "... ");
446 
447     // Check whether we need to replace this atom with an external atom.
448     //
449     // We replace if all of the following hold:
450     //   (1) The atom is marked should-discard,
451     //   (2) it has live edges (i.e. edges from live atoms) pointing to it.
452     //
453     // Otherwise we simply delete the atom.
454 
455     G.removeDefinedAtom(*DA);
456 
457     auto EdgesToUpdateItr = EdgesToUpdate.find(DA);
458     if (EdgesToUpdateItr != EdgesToUpdate.end()) {
459       auto &ExternalReplacement = G.addExternalAtom(DA->getName());
460       for (auto *EdgeToUpdate : EdgesToUpdateItr->second)
461         EdgeToUpdate->setTarget(ExternalReplacement);
462       LLVM_DEBUG(dbgs() << "replaced with " << ExternalReplacement << "\n");
463     } else
464       LLVM_DEBUG(dbgs() << "deleted\n");
465   }
466 
467   // Finally, discard any absolute symbols that were marked should-discard.
468   {
469     std::vector<Atom *> AbsoluteAtomsToRemove;
470     for (auto *A : G.absolute_atoms())
471       if (A->shouldDiscard() || A->isLive())
472         AbsoluteAtomsToRemove.push_back(A);
473     for (auto *A : AbsoluteAtomsToRemove)
474       G.removeAbsoluteAtom(*A);
475   }
476 }
477 
478 } // end namespace jitlink
479 } // end namespace llvm
480