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