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
linkPhase1(std::unique_ptr<JITLinkerBase> Self)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
linkPhase2(std::unique_ptr<JITLinkerBase> Self,AllocResult AR)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 Ctx->notifyFailed(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 Ctx->notifyFailed(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 Ctx->notifyFailed(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
linkPhase3(std::unique_ptr<JITLinkerBase> Self,Expected<AsyncLookupResult> LR)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
linkPhase4(std::unique_ptr<JITLinkerBase> Self,FinalizeResult FR)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
runPasses(LinkGraphPassList & Passes)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
getExternalSymbolNames() const197 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
applyLookupResult(AsyncLookupResult Result)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(
222 orc::ExecutorAddr(ResultI->second.getAddress()));
223 Sym->setLinkage(ResultI->second.getFlags().isWeak() ? Linkage::Weak
224 : Linkage::Strong);
225 Sym->setScope(ResultI->second.getFlags().isExported() ? Scope::Default
226 : Scope::Hidden);
227 } else
228 assert(Sym->isWeaklyReferenced() &&
229 "Failed to resolve non-weak reference");
230 }
231
232 LLVM_DEBUG({
233 dbgs() << "Externals after applying lookup result:\n";
234 for (auto *Sym : G->external_symbols()) {
235 dbgs() << " " << Sym->getName() << ": "
236 << formatv("{0:x16}", Sym->getAddress().getValue());
237 switch (Sym->getLinkage()) {
238 case Linkage::Strong:
239 break;
240 case Linkage::Weak:
241 dbgs() << " (weak)";
242 break;
243 }
244 switch (Sym->getScope()) {
245 case Scope::Local:
246 llvm_unreachable("External symbol should not have local linkage");
247 case Scope::Hidden:
248 break;
249 case Scope::Default:
250 dbgs() << " (exported)";
251 break;
252 }
253 dbgs() << "\n";
254 }
255 });
256 }
257
abandonAllocAndBailOut(std::unique_ptr<JITLinkerBase> Self,Error Err)258 void JITLinkerBase::abandonAllocAndBailOut(std::unique_ptr<JITLinkerBase> Self,
259 Error Err) {
260 assert(Err && "Should not be bailing out on success value");
261 assert(Alloc && "can not call abandonAllocAndBailOut before allocation");
262 Alloc->abandon([S = std::move(Self), E1 = std::move(Err)](Error E2) mutable {
263 S->Ctx->notifyFailed(joinErrors(std::move(E1), std::move(E2)));
264 });
265 }
266
prune(LinkGraph & G)267 void prune(LinkGraph &G) {
268 std::vector<Symbol *> Worklist;
269 DenseSet<Block *> VisitedBlocks;
270
271 // Build the initial worklist from all symbols initially live.
272 for (auto *Sym : G.defined_symbols())
273 if (Sym->isLive())
274 Worklist.push_back(Sym);
275
276 // Propagate live flags to all symbols reachable from the initial live set.
277 while (!Worklist.empty()) {
278 auto *Sym = Worklist.back();
279 Worklist.pop_back();
280
281 auto &B = Sym->getBlock();
282
283 // Skip addressables that we've visited before.
284 if (VisitedBlocks.count(&B))
285 continue;
286
287 VisitedBlocks.insert(&B);
288
289 for (auto &E : Sym->getBlock().edges()) {
290 // If the edge target is a defined symbol that is being newly marked live
291 // then add it to the worklist.
292 if (E.getTarget().isDefined() && !E.getTarget().isLive())
293 Worklist.push_back(&E.getTarget());
294
295 // Mark the target live.
296 E.getTarget().setLive(true);
297 }
298 }
299
300 // Collect all defined symbols to remove, then remove them.
301 {
302 LLVM_DEBUG(dbgs() << "Dead-stripping defined symbols:\n");
303 std::vector<Symbol *> SymbolsToRemove;
304 for (auto *Sym : G.defined_symbols())
305 if (!Sym->isLive())
306 SymbolsToRemove.push_back(Sym);
307 for (auto *Sym : SymbolsToRemove) {
308 LLVM_DEBUG(dbgs() << " " << *Sym << "...\n");
309 G.removeDefinedSymbol(*Sym);
310 }
311 }
312
313 // Delete any unused blocks.
314 {
315 LLVM_DEBUG(dbgs() << "Dead-stripping blocks:\n");
316 std::vector<Block *> BlocksToRemove;
317 for (auto *B : G.blocks())
318 if (!VisitedBlocks.count(B))
319 BlocksToRemove.push_back(B);
320 for (auto *B : BlocksToRemove) {
321 LLVM_DEBUG(dbgs() << " " << *B << "...\n");
322 G.removeBlock(*B);
323 }
324 }
325
326 // Collect all external symbols to remove, then remove them.
327 {
328 LLVM_DEBUG(dbgs() << "Removing unused external symbols:\n");
329 std::vector<Symbol *> SymbolsToRemove;
330 for (auto *Sym : G.external_symbols())
331 if (!Sym->isLive())
332 SymbolsToRemove.push_back(Sym);
333 for (auto *Sym : SymbolsToRemove) {
334 LLVM_DEBUG(dbgs() << " " << *Sym << "...\n");
335 G.removeExternalSymbol(*Sym);
336 }
337 }
338 }
339
340 } // end namespace jitlink
341 } // end namespace llvm
342