1//===------ LinkGraphLinkingLayer.cpp - Link LinkGraphs with JITLink ------===//
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#include "llvm/ExecutionEngine/Orc/LinkGraphLinkingLayer.h"
10#include "llvm/ExecutionEngine/JITLink/EHFrameSupport.h"
11#include "llvm/ExecutionEngine/JITLink/aarch32.h"
12#include "llvm/ExecutionEngine/Orc/DebugUtils.h"
13#include "llvm/ExecutionEngine/Orc/Shared/ObjectFormats.h"
14#include "llvm/Support/MemoryBuffer.h"
15
16#define DEBUG_TYPE "orc"
17
18using namespace llvm;
19using namespace llvm::jitlink;
20using namespace llvm::orc;
21
22namespace {
23
24ExecutorAddr getJITSymbolPtrForSymbol(Symbol &Sym, const Triple &TT) {
25 switch (TT.getArch()) {
26 case Triple::arm:
27 case Triple::armeb:
28 case Triple::thumb:
29 case Triple::thumbeb:
30 if (hasTargetFlags(Sym, Flags: aarch32::ThumbSymbol)) {
31 // Set LSB to indicate thumb target
32 assert(Sym.isCallable() && "Only callable symbols can have thumb flag");
33 assert((Sym.getAddress().getValue() & 0x01) == 0 && "LSB is clear");
34 return Sym.getAddress() + 0x01;
35 }
36 return Sym.getAddress();
37 default:
38 return Sym.getAddress();
39 }
40}
41
42} // end anonymous namespace
43
44namespace llvm {
45namespace orc {
46
47class LinkGraphLinkingLayer::JITLinkCtx final : public JITLinkContext {
48public:
49 JITLinkCtx(LinkGraphLinkingLayer &Layer,
50 std::unique_ptr<MaterializationResponsibility> MR,
51 std::unique_ptr<MemoryBuffer> ObjBuffer)
52 : JITLinkContext(&MR->getTargetJITDylib()), Layer(Layer),
53 MR(std::move(MR)), ObjBuffer(std::move(ObjBuffer)) {
54 std::lock_guard<std::mutex> Lock(Layer.LayerMutex);
55 Plugins = Layer.Plugins;
56 }
57
58 ~JITLinkCtx() {
59 // If there is an object buffer return function then use it to
60 // return ownership of the buffer.
61 if (Layer.ReturnObjectBuffer && ObjBuffer)
62 Layer.ReturnObjectBuffer(std::move(ObjBuffer));
63 }
64
65 JITLinkMemoryManager &getMemoryManager() override { return Layer.MemMgr; }
66
67 void notifyMaterializing(LinkGraph &G) {
68 for (auto &P : Plugins)
69 P->notifyMaterializing(MR&: *MR, G, Ctx&: *this,
70 InputObject: ObjBuffer ? ObjBuffer->getMemBufferRef()
71 : MemoryBufferRef());
72 }
73
74 void notifyFailed(Error Err) override {
75 for (auto &P : Plugins)
76 Err = joinErrors(E1: std::move(Err), E2: P->notifyFailed(MR&: *MR));
77 Layer.getExecutionSession().reportError(Err: std::move(Err));
78 MR->failMaterialization();
79 }
80
81 void lookup(const LookupMap &Symbols,
82 std::unique_ptr<JITLinkAsyncLookupContinuation> LC) override {
83
84 JITDylibSearchOrder LinkOrder;
85 MR->getTargetJITDylib().withLinkOrderDo(
86 F: [&](const JITDylibSearchOrder &LO) { LinkOrder = LO; });
87
88 auto &ES = Layer.getExecutionSession();
89
90 SymbolLookupSet LookupSet;
91 for (auto &KV : Symbols) {
92 orc::SymbolLookupFlags LookupFlags;
93 switch (KV.second) {
94 case jitlink::SymbolLookupFlags::RequiredSymbol:
95 LookupFlags = orc::SymbolLookupFlags::RequiredSymbol;
96 break;
97 case jitlink::SymbolLookupFlags::WeaklyReferencedSymbol:
98 LookupFlags = orc::SymbolLookupFlags::WeaklyReferencedSymbol;
99 break;
100 }
101 LookupSet.add(Name: KV.first, Flags: LookupFlags);
102 }
103
104 // OnResolve -- De-intern the symbols and pass the result to the linker.
105 auto OnResolve = [LookupContinuation =
106 std::move(LC)](Expected<SymbolMap> Result) mutable {
107 if (!Result)
108 LookupContinuation->run(LR: Result.takeError());
109 else {
110 AsyncLookupResult LR;
111 LR.insert_range(R&: *Result);
112 LookupContinuation->run(LR: std::move(LR));
113 }
114 };
115
116 ES.lookup(K: LookupKind::Static, SearchOrder: LinkOrder, Symbols: std::move(LookupSet),
117 RequiredState: SymbolState::Resolved, NotifyComplete: std::move(OnResolve),
118 RegisterDependencies: [this](const SymbolDependenceMap &Deps) {
119 // Translate LookupDeps map to SymbolSourceJD.
120 for (auto &[DepJD, Deps] : Deps)
121 for (auto &DepSym : Deps)
122 SymbolSourceJDs[NonOwningSymbolStringPtr(DepSym)] = DepJD;
123 });
124 }
125
126 Error notifyResolved(LinkGraph &G) override {
127
128 SymbolFlagsMap ExtraSymbolsToClaim;
129 bool AutoClaim = Layer.AutoClaimObjectSymbols;
130
131 SymbolMap InternedResult;
132 for (auto *Sym : G.defined_symbols())
133 if (Sym->getScope() < Scope::SideEffectsOnly) {
134 auto Ptr = getJITSymbolPtrForSymbol(Sym&: *Sym, TT: G.getTargetTriple());
135 auto Flags = getJITSymbolFlagsForSymbol(Sym&: *Sym);
136 InternedResult[Sym->getName()] = {Ptr, Flags};
137 if (AutoClaim && !MR->getSymbols().count(Val: Sym->getName())) {
138 assert(!ExtraSymbolsToClaim.count(Sym->getName()) &&
139 "Duplicate symbol to claim?");
140 ExtraSymbolsToClaim[Sym->getName()] = Flags;
141 }
142 }
143
144 for (auto *Sym : G.absolute_symbols())
145 if (Sym->getScope() < Scope::SideEffectsOnly) {
146 auto Ptr = getJITSymbolPtrForSymbol(Sym&: *Sym, TT: G.getTargetTriple());
147 auto Flags = getJITSymbolFlagsForSymbol(Sym&: *Sym);
148 InternedResult[Sym->getName()] = {Ptr, Flags};
149 if (AutoClaim && !MR->getSymbols().count(Val: Sym->getName())) {
150 assert(!ExtraSymbolsToClaim.count(Sym->getName()) &&
151 "Duplicate symbol to claim?");
152 ExtraSymbolsToClaim[Sym->getName()] = Flags;
153 }
154 }
155
156 if (!ExtraSymbolsToClaim.empty())
157 if (auto Err = MR->defineMaterializing(SymbolFlags: ExtraSymbolsToClaim))
158 return Err;
159
160 {
161
162 // Check that InternedResult matches up with MR->getSymbols(), overriding
163 // flags if requested.
164 // This guards against faulty transformations / compilers / object caches.
165
166 // First check that there aren't any missing symbols.
167 size_t NumMaterializationSideEffectsOnlySymbols = 0;
168 SymbolNameVector MissingSymbols;
169 for (auto &[Sym, Flags] : MR->getSymbols()) {
170
171 auto I = InternedResult.find(Val: Sym);
172
173 // If this is a materialization-side-effects only symbol then bump
174 // the counter and remove in from the result, otherwise make sure that
175 // it's defined.
176 if (Flags.hasMaterializationSideEffectsOnly())
177 ++NumMaterializationSideEffectsOnlySymbols;
178 else if (I == InternedResult.end())
179 MissingSymbols.push_back(x: Sym);
180 else if (Layer.OverrideObjectFlags)
181 I->second.setFlags(Flags);
182 }
183
184 // If there were missing symbols then report the error.
185 if (!MissingSymbols.empty())
186 return make_error<MissingSymbolDefinitions>(
187 Args: Layer.getExecutionSession().getSymbolStringPool(), Args: G.getName(),
188 Args: std::move(MissingSymbols));
189
190 // If there are more definitions than expected, add them to the
191 // ExtraSymbols vector.
192 SymbolNameVector ExtraSymbols;
193 if (InternedResult.size() >
194 MR->getSymbols().size() - NumMaterializationSideEffectsOnlySymbols) {
195 for (auto &KV : InternedResult)
196 if (!MR->getSymbols().count(Val: KV.first))
197 ExtraSymbols.push_back(x: KV.first);
198 }
199
200 // If there were extra definitions then report the error.
201 if (!ExtraSymbols.empty())
202 return make_error<UnexpectedSymbolDefinitions>(
203 Args: Layer.getExecutionSession().getSymbolStringPool(), Args: G.getName(),
204 Args: std::move(ExtraSymbols));
205 }
206
207 if (auto Err = MR->notifyResolved(Symbols: InternedResult))
208 return Err;
209
210 return Error::success();
211 }
212
213 void notifyFinalized(JITLinkMemoryManager::FinalizedAlloc A) override {
214 if (auto Err = notifyEmitted(FA: std::move(A))) {
215 Layer.getExecutionSession().reportError(Err: std::move(Err));
216 MR->failMaterialization();
217 return;
218 }
219
220 if (auto Err = MR->notifyEmitted(EmittedDeps: SymbolDepGroups)) {
221 Layer.getExecutionSession().reportError(Err: std::move(Err));
222 MR->failMaterialization();
223 }
224 }
225
226 LinkGraphPassFunction getMarkLivePass(const Triple &TT) const override {
227 return [this](LinkGraph &G) { return markResponsibilitySymbolsLive(G); };
228 }
229
230 Error modifyPassConfig(LinkGraph &LG, PassConfiguration &Config) override {
231 // Add passes to mark duplicate defs as should-discard, and to walk the
232 // link graph to build the symbol dependence graph.
233 Config.PrePrunePasses.push_back(x: [this](LinkGraph &G) {
234 return claimOrExternalizeWeakAndCommonSymbols(G);
235 });
236
237 for (auto &P : Plugins)
238 P->modifyPassConfig(MR&: *MR, G&: LG, Config);
239
240 Config.PreFixupPasses.push_back(
241 x: [this](LinkGraph &G) { return registerDependencies(G); });
242
243 return Error::success();
244 }
245
246 Error notifyEmitted(jitlink::JITLinkMemoryManager::FinalizedAlloc FA) {
247 Error Err = Error::success();
248 for (auto &P : Plugins)
249 Err = joinErrors(E1: std::move(Err), E2: P->notifyEmitted(MR&: *MR));
250
251 if (Err) {
252 if (FA)
253 Err =
254 joinErrors(E1: std::move(Err), E2: Layer.MemMgr.deallocate(Alloc: std::move(FA)));
255 return Err;
256 }
257
258 if (FA)
259 return Layer.recordFinalizedAlloc(MR&: *MR, FA: std::move(FA));
260
261 return Error::success();
262 }
263
264private:
265 Error claimOrExternalizeWeakAndCommonSymbols(LinkGraph &G) {
266 SymbolFlagsMap NewSymbolsToClaim;
267 std::vector<std::pair<SymbolStringPtr, Symbol *>> NameToSym;
268
269 auto ProcessSymbol = [&](Symbol *Sym) {
270 if (Sym->hasName() && Sym->getLinkage() == Linkage::Weak &&
271 Sym->getScope() != Scope::Local) {
272 if (!MR->getSymbols().count(Val: Sym->getName())) {
273 NewSymbolsToClaim[Sym->getName()] =
274 getJITSymbolFlagsForSymbol(Sym&: *Sym) | JITSymbolFlags::Weak;
275 NameToSym.push_back(x: std::make_pair(x: Sym->getName(), y&: Sym));
276 }
277 }
278 };
279
280 for (auto *Sym : G.defined_symbols())
281 ProcessSymbol(Sym);
282 for (auto *Sym : G.absolute_symbols())
283 ProcessSymbol(Sym);
284
285 // Attempt to claim all weak defs that we're not already responsible for.
286 // This may fail if the resource tracker has become defunct, but should
287 // always succeed otherwise.
288 if (auto Err = MR->defineMaterializing(SymbolFlags: std::move(NewSymbolsToClaim)))
289 return Err;
290
291 // Walk the list of symbols that we just tried to claim. Symbols that we're
292 // responsible for are marked live. Symbols that we're not responsible for
293 // are turned into external references.
294 for (auto &KV : NameToSym) {
295 if (MR->getSymbols().count(Val: KV.first))
296 KV.second->setLive(true);
297 else
298 G.makeExternal(Sym&: *KV.second);
299 }
300
301 return Error::success();
302 }
303
304 Error markResponsibilitySymbolsLive(LinkGraph &G) const {
305 for (auto *Sym : G.defined_symbols())
306 if (Sym->hasName() && MR->getSymbols().count(Val: Sym->getName()))
307 Sym->setLive(true);
308 return Error::success();
309 }
310
311 Error registerDependencies(LinkGraph &G) {
312
313 struct BlockInfo {
314 bool InWorklist = false;
315 DenseSet<Symbol *> Defs;
316 DenseSet<Symbol *> SymbolDeps;
317 DenseSet<Block *> AnonEdges, AnonBackEdges;
318 };
319
320 DenseMap<Block *, BlockInfo> BlockInfos;
321
322 // Reserve space so that BlockInfos doesn't need to resize. This is
323 // essential to avoid invalidating pointers to entries below.
324 {
325 size_t NumBlocks = 0;
326 for (auto &Sec : G.sections())
327 NumBlocks += Sec.blocks_size();
328 BlockInfos.reserve(NumEntries: NumBlocks);
329 }
330
331 // Identify non-locally-scoped symbols defined by each block.
332 for (auto *Sym : G.defined_symbols()) {
333 if (Sym->getScope() != Scope::Local)
334 BlockInfos[&Sym->getBlock()].Defs.insert(V: Sym);
335 }
336
337 // Identify the symbolic and anonymous-block dependencies for each block.
338 for (auto *B : G.blocks()) {
339 auto &BI = BlockInfos[B];
340
341 for (auto &E : B->edges()) {
342
343 // External symbols are trivially depended on.
344 if (E.getTarget().isExternal()) {
345 BI.SymbolDeps.insert(V: &E.getTarget());
346 continue;
347 }
348
349 // Anonymous symbols aren't depended on at all (they're assumed to be
350 // already available).
351 if (E.getTarget().isAbsolute())
352 continue;
353
354 // If we get here then we depend on a symbol defined by some other
355 // block.
356 auto &TgtBI = BlockInfos[&E.getTarget().getBlock()];
357
358 // If that block has any definitions then use the first one as the
359 // "effective" dependence here (all symbols in TgtBI will become
360 // ready at the same time, and chosing a single symbol to represent
361 // the block keeps the SymbolDepGroup size small).
362 if (!TgtBI.Defs.empty()) {
363 BI.SymbolDeps.insert(V: *TgtBI.Defs.begin());
364 continue;
365 }
366
367 // Otherwise we've got a dependence on an anonymous block. Record it
368 // here for back-propagating symbol dependencies below.
369 BI.AnonEdges.insert(V: &E.getTarget().getBlock());
370 TgtBI.AnonBackEdges.insert(V: B);
371 }
372 }
373
374 // Prune anonymous blocks.
375 {
376 std::vector<Block *> BlocksToRemove;
377 for (auto &[B, BI] : BlockInfos) {
378 // Skip blocks with defs. We only care about anonyous blocks.
379 if (!BI.Defs.empty())
380 continue;
381
382 BlocksToRemove.push_back(x: B);
383
384 for (auto *FB : BI.AnonEdges)
385 BlockInfos[FB].AnonBackEdges.erase(V: B);
386
387 for (auto *BB : BI.AnonBackEdges)
388 BlockInfos[BB].AnonEdges.erase(V: B);
389
390 for (auto *FB : BI.AnonEdges) {
391 auto &FBI = BlockInfos[FB];
392 FBI.AnonBackEdges.insert_range(R&: BI.AnonBackEdges);
393 }
394
395 for (auto *BB : BI.AnonBackEdges) {
396 auto &BBI = BlockInfos[BB];
397 BBI.SymbolDeps.insert_range(R&: BI.SymbolDeps);
398 BBI.AnonEdges.insert_range(R&: BI.AnonEdges);
399 }
400 }
401
402 for (auto *B : BlocksToRemove)
403 BlockInfos.erase(Val: B);
404 }
405
406 // Build the initial dependence propagation worklist.
407 std::deque<Block *> Worklist;
408 for (auto &[B, BI] : BlockInfos) {
409 if (!BI.SymbolDeps.empty() && !BI.AnonBackEdges.empty()) {
410 Worklist.push_back(x: B);
411 BI.InWorklist = true;
412 }
413 }
414
415 // Propagate symbol deps through the graph.
416 while (!Worklist.empty()) {
417 auto *B = Worklist.front();
418 Worklist.pop_front();
419
420 auto &BI = BlockInfos[B];
421 BI.InWorklist = false;
422
423 for (auto *DB : BI.AnonBackEdges) {
424 auto &DBI = BlockInfos[DB];
425 for (auto *Sym : BI.SymbolDeps) {
426 if (DBI.SymbolDeps.insert(V: Sym).second && !DBI.InWorklist) {
427 Worklist.push_back(x: DB);
428 DBI.InWorklist = true;
429 }
430 }
431 }
432 }
433
434 // Transform our local dependence information into a list of
435 // SymbolDependenceGroups (in the SymbolDepGroups member), ready for use in
436 // the upcoming notifyFinalized call.
437 auto &TargetJD = MR->getTargetJITDylib();
438
439 for (auto &[B, BI] : BlockInfos) {
440 if (!BI.Defs.empty()) {
441 SymbolDepGroups.push_back(x: SymbolDependenceGroup());
442 auto &SDG = SymbolDepGroups.back();
443
444 for (auto *Def : BI.Defs)
445 SDG.Symbols.insert(V: Def->getName());
446
447 for (auto *Dep : BI.SymbolDeps) {
448 auto DepName = Dep->getName();
449 if (Dep->isDefined())
450 SDG.Dependencies[&TargetJD].insert(V: std::move(DepName));
451 else {
452 auto SourceJDItr =
453 SymbolSourceJDs.find(Val: NonOwningSymbolStringPtr(DepName));
454 if (SourceJDItr != SymbolSourceJDs.end())
455 SDG.Dependencies[SourceJDItr->second].insert(V: std::move(DepName));
456 }
457 }
458 }
459 }
460
461 return Error::success();
462 }
463
464 LinkGraphLinkingLayer &Layer;
465 std::vector<std::shared_ptr<LinkGraphLinkingLayer::Plugin>> Plugins;
466 std::unique_ptr<MaterializationResponsibility> MR;
467 std::unique_ptr<MemoryBuffer> ObjBuffer;
468 DenseMap<NonOwningSymbolStringPtr, JITDylib *> SymbolSourceJDs;
469 std::vector<SymbolDependenceGroup> SymbolDepGroups;
470};
471
472LinkGraphLinkingLayer::Plugin::~Plugin() = default;
473
474LinkGraphLinkingLayer::LinkGraphLinkingLayer(ExecutionSession &ES)
475 : LinkGraphLayer(ES), MemMgr(ES.getExecutorProcessControl().getMemMgr()) {
476 ES.registerResourceManager(RM&: *this);
477}
478
479LinkGraphLinkingLayer::LinkGraphLinkingLayer(ExecutionSession &ES,
480 JITLinkMemoryManager &MemMgr)
481 : LinkGraphLayer(ES), MemMgr(MemMgr) {
482 ES.registerResourceManager(RM&: *this);
483}
484
485LinkGraphLinkingLayer::LinkGraphLinkingLayer(
486 ExecutionSession &ES, std::unique_ptr<JITLinkMemoryManager> MemMgr)
487 : LinkGraphLayer(ES), MemMgr(*MemMgr), MemMgrOwnership(std::move(MemMgr)) {
488 ES.registerResourceManager(RM&: *this);
489}
490
491LinkGraphLinkingLayer::~LinkGraphLinkingLayer() {
492 assert(Allocs.empty() &&
493 "Layer destroyed with resources still attached "
494 "(ExecutionSession::endSession() must be called prior to "
495 "destruction)");
496 getExecutionSession().deregisterResourceManager(RM&: *this);
497}
498
499void LinkGraphLinkingLayer::emit(
500 std::unique_ptr<MaterializationResponsibility> R,
501 std::unique_ptr<LinkGraph> G) {
502 assert(R && "R must not be null");
503 assert(G && "G must not be null");
504 auto Ctx = std::make_unique<JITLinkCtx>(args&: *this, args: std::move(R), args: nullptr);
505 Ctx->notifyMaterializing(G&: *G);
506 link(G: std::move(G), Ctx: std::move(Ctx));
507}
508
509void LinkGraphLinkingLayer::emit(
510 std::unique_ptr<MaterializationResponsibility> R,
511 std::unique_ptr<LinkGraph> G, std::unique_ptr<MemoryBuffer> ObjBuf) {
512 assert(R && "R must not be null");
513 assert(G && "G must not be null");
514 assert(ObjBuf && "Object must not be null");
515 auto Ctx =
516 std::make_unique<JITLinkCtx>(args&: *this, args: std::move(R), args: std::move(ObjBuf));
517 Ctx->notifyMaterializing(G&: *G);
518 link(G: std::move(G), Ctx: std::move(Ctx));
519}
520
521Error LinkGraphLinkingLayer::recordFinalizedAlloc(
522 MaterializationResponsibility &MR, FinalizedAlloc FA) {
523 auto Err = MR.withResourceKeyDo(
524 F: [&](ResourceKey K) { Allocs[K].push_back(x: std::move(FA)); });
525
526 if (Err)
527 Err = joinErrors(E1: std::move(Err), E2: MemMgr.deallocate(Alloc: std::move(FA)));
528
529 return Err;
530}
531
532Error LinkGraphLinkingLayer::handleRemoveResources(JITDylib &JD,
533 ResourceKey K) {
534
535 {
536 Error Err = Error::success();
537 for (auto &P : Plugins)
538 Err = joinErrors(E1: std::move(Err), E2: P->notifyRemovingResources(JD, K));
539 if (Err)
540 return Err;
541 }
542
543 std::vector<FinalizedAlloc> AllocsToRemove;
544 getExecutionSession().runSessionLocked(F: [&] {
545 auto I = Allocs.find(Val: K);
546 if (I != Allocs.end()) {
547 std::swap(x&: AllocsToRemove, y&: I->second);
548 Allocs.erase(I);
549 }
550 });
551
552 if (AllocsToRemove.empty())
553 return Error::success();
554
555 return MemMgr.deallocate(Allocs: std::move(AllocsToRemove));
556}
557
558void LinkGraphLinkingLayer::handleTransferResources(JITDylib &JD,
559 ResourceKey DstKey,
560 ResourceKey SrcKey) {
561 if (Allocs.contains(Val: SrcKey)) {
562 // DstKey may not be in the DenseMap yet, so the following line may resize
563 // the container and invalidate iterators and value references.
564 auto &DstAllocs = Allocs[DstKey];
565 auto &SrcAllocs = Allocs[SrcKey];
566 DstAllocs.reserve(n: DstAllocs.size() + SrcAllocs.size());
567 for (auto &Alloc : SrcAllocs)
568 DstAllocs.push_back(x: std::move(Alloc));
569
570 Allocs.erase(Val: SrcKey);
571 }
572
573 for (auto &P : Plugins)
574 P->notifyTransferringResources(JD, DstKey, SrcKey);
575}
576
577} // End namespace orc.
578} // End namespace llvm.
579