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