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 
15 #include "llvm/Support/BinaryStreamReader.h"
16 #include "llvm/Support/MemoryBuffer.h"
17 
18 #define DEBUG_TYPE "jitlink"
19 
20 namespace llvm {
21 namespace jitlink {
22 
23 JITLinkerBase::~JITLinkerBase() = default;
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   Ctx->getMemoryManager().allocate(
52       Ctx->getJITLinkDylib(), *G,
53       [S = std::move(Self)](AllocResult AR) mutable {
54         // FIXME: Once MSVC implements c++17 order of evaluation rules for calls
55         // this can be simplified to
56         //          S->linkPhase2(std::move(S), std::move(AR));
57         auto *TmpSelf = S.get();
58         TmpSelf->linkPhase2(std::move(S), std::move(AR));
59       });
60 }
61 
62 void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self,
63                                AllocResult AR) {
64 
65   if (AR)
66     Alloc = std::move(*AR);
67   else
68     return abandonAllocAndBailOut(std::move(Self), AR.takeError());
69 
70   LLVM_DEBUG({
71     dbgs() << "Link graph \"" << G->getName()
72            << "\" before post-allocation passes:\n";
73     G->dump(dbgs());
74   });
75 
76   // Run post-allocation passes.
77   if (auto Err = runPasses(Passes.PostAllocationPasses))
78     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
79 
80   // Notify client that the defined symbols have been assigned addresses.
81   LLVM_DEBUG(dbgs() << "Resolving symbols defined in " << G->getName() << "\n");
82 
83   if (auto Err = Ctx->notifyResolved(*G))
84     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
85 
86   auto ExternalSymbols = getExternalSymbolNames();
87 
88   // If there are no external symbols then proceed immediately with phase 3.
89   if (ExternalSymbols.empty()) {
90     LLVM_DEBUG({
91       dbgs() << "No external symbols for " << G->getName()
92              << ". Proceeding immediately with link phase 3.\n";
93     });
94     // FIXME: Once MSVC implements c++17 order of evaluation rules for calls
95     // this can be simplified. See below.
96     auto &TmpSelf = *Self;
97     TmpSelf.linkPhase3(std::move(Self), AsyncLookupResult());
98     return;
99   }
100 
101   // Otherwise look up the externals.
102   LLVM_DEBUG({
103     dbgs() << "Issuing lookup for external symbols for " << G->getName()
104            << " (may trigger materialization/linking of other graphs)...\n";
105   });
106 
107   // We're about to hand off ownership of ourself to the continuation. Grab a
108   // pointer to the context so that we can call it to initiate the lookup.
109   //
110   // FIXME: Once MSVC implements c++17 order of evaluation rules for calls this
111   // can be simplified to:
112   //
113   // Ctx->lookup(std::move(UnresolvedExternals),
114   //             [Self=std::move(Self)](Expected<AsyncLookupResult> Result) {
115   //               Self->linkPhase3(std::move(Self), std::move(Result));
116   //             });
117   Ctx->lookup(std::move(ExternalSymbols),
118               createLookupContinuation(
119                   [S = std::move(Self)](
120                       Expected<AsyncLookupResult> LookupResult) mutable {
121                     auto &TmpSelf = *S;
122                     TmpSelf.linkPhase3(std::move(S), std::move(LookupResult));
123                   }));
124 }
125 
126 void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self,
127                                Expected<AsyncLookupResult> LR) {
128 
129   LLVM_DEBUG({
130     dbgs() << "Starting link phase 3 for graph " << G->getName() << "\n";
131   });
132 
133   // If the lookup failed, bail out.
134   if (!LR)
135     return abandonAllocAndBailOut(std::move(Self), LR.takeError());
136 
137   // Assign addresses to external addressables.
138   applyLookupResult(*LR);
139 
140   LLVM_DEBUG({
141     dbgs() << "Link graph \"" << G->getName()
142            << "\" before pre-fixup passes:\n";
143     G->dump(dbgs());
144   });
145 
146   if (auto Err = runPasses(Passes.PreFixupPasses))
147     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
148 
149   LLVM_DEBUG({
150     dbgs() << "Link graph \"" << G->getName() << "\" before copy-and-fixup:\n";
151     G->dump(dbgs());
152   });
153 
154   // Fix up block content.
155   if (auto Err = fixUpBlocks(*G))
156     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
157 
158   LLVM_DEBUG({
159     dbgs() << "Link graph \"" << G->getName() << "\" after copy-and-fixup:\n";
160     G->dump(dbgs());
161   });
162 
163   if (auto Err = runPasses(Passes.PostFixupPasses))
164     return abandonAllocAndBailOut(std::move(Self), std::move(Err));
165 
166   Alloc->finalize([S = std::move(Self)](FinalizeResult FR) mutable {
167     // FIXME: Once MSVC implements c++17 order of evaluation rules for calls
168     // this can be simplified to
169     //          S->linkPhase2(std::move(S), std::move(AR));
170     auto *TmpSelf = S.get();
171     TmpSelf->linkPhase4(std::move(S), std::move(FR));
172   });
173 }
174 
175 void JITLinkerBase::linkPhase4(std::unique_ptr<JITLinkerBase> Self,
176                                FinalizeResult FR) {
177 
178   LLVM_DEBUG({
179     dbgs() << "Starting link phase 4 for graph " << G->getName() << "\n";
180   });
181 
182   if (!FR)
183     return Ctx->notifyFailed(FR.takeError());
184 
185   Ctx->notifyFinalized(std::move(*FR));
186 
187   LLVM_DEBUG({ dbgs() << "Link of graph " << G->getName() << " complete\n"; });
188 }
189 
190 Error JITLinkerBase::runPasses(LinkGraphPassList &Passes) {
191   for (auto &P : Passes)
192     if (auto Err = P(*G))
193       return Err;
194   return Error::success();
195 }
196 
197 JITLinkContext::LookupMap JITLinkerBase::getExternalSymbolNames() const {
198   // Identify unresolved external symbols.
199   JITLinkContext::LookupMap UnresolvedExternals;
200   for (auto *Sym : G->external_symbols()) {
201     assert(!Sym->getAddress() &&
202            "External has already been assigned an address");
203     assert(Sym->getName() != StringRef() && Sym->getName() != "" &&
204            "Externals must be named");
205     SymbolLookupFlags LookupFlags =
206         Sym->isWeaklyReferenced() ? SymbolLookupFlags::WeaklyReferencedSymbol
207                                   : SymbolLookupFlags::RequiredSymbol;
208     UnresolvedExternals[Sym->getName()] = LookupFlags;
209   }
210   return UnresolvedExternals;
211 }
212 
213 void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
214   for (auto *Sym : G->external_symbols()) {
215     assert(Sym->getOffset() == 0 &&
216            "External symbol is not at the start of its addressable block");
217     assert(!Sym->getAddress() && "Symbol already resolved");
218     assert(!Sym->isDefined() && "Symbol being resolved is already defined");
219     auto ResultI = Result.find(Sym->getName());
220     if (ResultI != Result.end()) {
221       Sym->getAddressable().setAddress(ResultI->second.getAddress());
222       Sym->setLinkage(ResultI->second.getFlags().isWeak() ? Linkage::Weak
223                                                           : Linkage::Strong);
224       Sym->setScope(ResultI->second.getFlags().isExported() ? Scope::Default
225                                                             : Scope::Hidden);
226     } else
227       assert(Sym->isWeaklyReferenced() &&
228              "Failed to resolve non-weak reference");
229   }
230 
231   LLVM_DEBUG({
232     dbgs() << "Externals after applying lookup result:\n";
233     for (auto *Sym : G->external_symbols()) {
234       dbgs() << "  " << Sym->getName() << ": "
235              << formatv("{0:x16}", Sym->getAddress().getValue());
236       switch (Sym->getLinkage()) {
237       case Linkage::Strong:
238         break;
239       case Linkage::Weak:
240         dbgs() << " (weak)";
241         break;
242       }
243       switch (Sym->getScope()) {
244       case Scope::Local:
245         llvm_unreachable("External symbol should not have local linkage");
246       case Scope::Hidden:
247         break;
248       case Scope::Default:
249         dbgs() << " (exported)";
250         break;
251       }
252       dbgs() << "\n";
253     }
254   });
255 }
256 
257 void JITLinkerBase::abandonAllocAndBailOut(std::unique_ptr<JITLinkerBase> Self,
258                                            Error Err) {
259   assert(Err && "Should not be bailing out on success value");
260   assert(Alloc && "can not call abandonAllocAndBailOut before allocation");
261   Alloc->abandon([S = std::move(Self), E1 = std::move(Err)](Error E2) mutable {
262     S->Ctx->notifyFailed(joinErrors(std::move(E1), std::move(E2)));
263   });
264 }
265 
266 void prune(LinkGraph &G) {
267   std::vector<Symbol *> Worklist;
268   DenseSet<Block *> VisitedBlocks;
269 
270   // Build the initial worklist from all symbols initially live.
271   for (auto *Sym : G.defined_symbols())
272     if (Sym->isLive())
273       Worklist.push_back(Sym);
274 
275   // Propagate live flags to all symbols reachable from the initial live set.
276   while (!Worklist.empty()) {
277     auto *Sym = Worklist.back();
278     Worklist.pop_back();
279 
280     auto &B = Sym->getBlock();
281 
282     // Skip addressables that we've visited before.
283     if (VisitedBlocks.count(&B))
284       continue;
285 
286     VisitedBlocks.insert(&B);
287 
288     for (auto &E : Sym->getBlock().edges()) {
289       // If the edge target is a defined symbol that is being newly marked live
290       // then add it to the worklist.
291       if (E.getTarget().isDefined() && !E.getTarget().isLive())
292         Worklist.push_back(&E.getTarget());
293 
294       // Mark the target live.
295       E.getTarget().setLive(true);
296     }
297   }
298 
299   // Collect all defined symbols to remove, then remove them.
300   {
301     LLVM_DEBUG(dbgs() << "Dead-stripping defined symbols:\n");
302     std::vector<Symbol *> SymbolsToRemove;
303     for (auto *Sym : G.defined_symbols())
304       if (!Sym->isLive())
305         SymbolsToRemove.push_back(Sym);
306     for (auto *Sym : SymbolsToRemove) {
307       LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
308       G.removeDefinedSymbol(*Sym);
309     }
310   }
311 
312   // Delete any unused blocks.
313   {
314     LLVM_DEBUG(dbgs() << "Dead-stripping blocks:\n");
315     std::vector<Block *> BlocksToRemove;
316     for (auto *B : G.blocks())
317       if (!VisitedBlocks.count(B))
318         BlocksToRemove.push_back(B);
319     for (auto *B : BlocksToRemove) {
320       LLVM_DEBUG(dbgs() << "  " << *B << "...\n");
321       G.removeBlock(*B);
322     }
323   }
324 
325   // Collect all external symbols to remove, then remove them.
326   {
327     LLVM_DEBUG(dbgs() << "Removing unused external symbols:\n");
328     std::vector<Symbol *> SymbolsToRemove;
329     for (auto *Sym : G.external_symbols())
330       if (!Sym->isLive())
331         SymbolsToRemove.push_back(Sym);
332     for (auto *Sym : SymbolsToRemove) {
333       LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
334       G.removeExternalSymbol(*Sym);
335     }
336   }
337 }
338 
339 } // end namespace jitlink
340 } // end namespace llvm
341