1//===------------ JITLink.h - JIT linker functionality ----------*- C++ -*-===//
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// Contains generic JIT-linker types.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H
14#define LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H
15
16#include "JITLinkMemoryManager.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/DenseSet.h"
19#include "llvm/ADT/Optional.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/Triple.h"
22#include "llvm/ExecutionEngine/JITSymbol.h"
23#include "llvm/Support/Allocator.h"
24#include "llvm/Support/Endian.h"
25#include "llvm/Support/Error.h"
26#include "llvm/Support/FormatVariadic.h"
27#include "llvm/Support/MathExtras.h"
28#include "llvm/Support/Memory.h"
29#include "llvm/Support/MemoryBuffer.h"
30
31#include <map>
32#include <string>
33#include <system_error>
34
35namespace llvm {
36namespace jitlink {
37
38class Symbol;
39class Section;
40
41/// Base class for errors originating in JIT linker, e.g. missing relocation
42/// support.
43class JITLinkError : public ErrorInfo<JITLinkError> {
44public:
45 static char ID;
46
47 JITLinkError(Twine ErrMsg) : ErrMsg(ErrMsg.str()) {}
48
49 void log(raw_ostream &OS) const override;
50 const std::string &getErrorMessage() const { return ErrMsg; }
51 std::error_code convertToErrorCode() const override;
52
53private:
54 std::string ErrMsg;
55};
56
57/// Represents fixups and constraints in the LinkGraph.
58class Edge {
59public:
60 using Kind = uint8_t;
61
62 enum GenericEdgeKind : Kind {
63 Invalid, // Invalid edge value.
64 FirstKeepAlive, // Keeps target alive. Offset/addend zero.
65 KeepAlive = FirstKeepAlive, // Tag first edge kind that preserves liveness.
66 FirstRelocation // First architecture specific relocation.
67 };
68
69 using OffsetT = uint32_t;
70 using AddendT = int64_t;
71
72 Edge(Kind K, OffsetT Offset, Symbol &Target, AddendT Addend)
73 : Target(&Target), Offset(Offset), Addend(Addend), K(K) {}
74
75 OffsetT getOffset() const { return Offset; }
76 void setOffset(OffsetT Offset) { this->Offset = Offset; }
77 Kind getKind() const { return K; }
78 void setKind(Kind K) { this->K = K; }
79 bool isRelocation() const { return K >= FirstRelocation; }
80 Kind getRelocation() const {
81 assert(isRelocation() && "Not a relocation edge");
82 return K - FirstRelocation;
83 }
84 bool isKeepAlive() const { return K >= FirstKeepAlive; }
85 Symbol &getTarget() const { return *Target; }
86 void setTarget(Symbol &Target) { this->Target = &Target; }
87 AddendT getAddend() const { return Addend; }
88 void setAddend(AddendT Addend) { this->Addend = Addend; }
89
90private:
91 Symbol *Target = nullptr;
92 OffsetT Offset = 0;
93 AddendT Addend = 0;
94 Kind K = 0;
95};
96
97/// Returns the string name of the given generic edge kind, or "unknown"
98/// otherwise. Useful for debugging.
99const char *getGenericEdgeKindName(Edge::Kind K);
100
101/// Base class for Addressable entities (externals, absolutes, blocks).
102class Addressable {
103 friend class LinkGraph;
104
105protected:
106 Addressable(JITTargetAddress Address, bool IsDefined)
107 : Address(Address), IsDefined(IsDefined), IsAbsolute(false) {}
108
109 Addressable(JITTargetAddress Address)
110 : Address(Address), IsDefined(false), IsAbsolute(true) {
111 assert(!(IsDefined && IsAbsolute) &&
112 "Block cannot be both defined and absolute");
113 }
114
115public:
116 Addressable(const Addressable &) = delete;
117 Addressable &operator=(const Addressable &) = default;
118 Addressable(Addressable &&) = delete;
119 Addressable &operator=(Addressable &&) = default;
120
121 JITTargetAddress getAddress() const { return Address; }
122 void setAddress(JITTargetAddress Address) { this->Address = Address; }
123
124 /// Returns true if this is a defined addressable, in which case you
125 /// can downcast this to a Block.
126 bool isDefined() const { return static_cast<bool>(IsDefined); }
127 bool isAbsolute() const { return static_cast<bool>(IsAbsolute); }
128
129private:
130 void setAbsolute(bool IsAbsolute) {
131 assert(!IsDefined && "Cannot change the Absolute flag on a defined block");
132 this->IsAbsolute = IsAbsolute;
133 }
134
135 JITTargetAddress Address = 0;
136 uint64_t IsDefined : 1;
137 uint64_t IsAbsolute : 1;
138};
139
140using SectionOrdinal = unsigned;
141
142/// An Addressable with content and edges.
143class Block : public Addressable {
144 friend class LinkGraph;
145
146private:
147 /// Create a zero-fill defined addressable.
148 Block(Section &Parent, JITTargetAddress Size, JITTargetAddress Address,
149 uint64_t Alignment, uint64_t AlignmentOffset)
150 : Addressable(Address, true), Parent(Parent), Size(Size) {
151 assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2");
152 assert(AlignmentOffset < Alignment &&
153 "Alignment offset cannot exceed alignment");
154 assert(AlignmentOffset <= MaxAlignmentOffset &&
155 "Alignment offset exceeds maximum");
156 P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
157 this->AlignmentOffset = AlignmentOffset;
158 }
159
160 /// Create a defined addressable for the given content.
161 Block(Section &Parent, ArrayRef<char> Content, JITTargetAddress Address,
162 uint64_t Alignment, uint64_t AlignmentOffset)
163 : Addressable(Address, true), Parent(Parent), Data(Content.data()),
164 Size(Content.size()) {
165 assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2");
166 assert(AlignmentOffset < Alignment &&
167 "Alignment offset cannot exceed alignment");
168 assert(AlignmentOffset <= MaxAlignmentOffset &&
169 "Alignment offset exceeds maximum");
170 P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
171 this->AlignmentOffset = AlignmentOffset;
172 }
173
174public:
175 using EdgeVector = std::vector<Edge>;
176 using edge_iterator = EdgeVector::iterator;
177 using const_edge_iterator = EdgeVector::const_iterator;
178
179 Block(const Block &) = delete;
180 Block &operator=(const Block &) = delete;
181 Block(Block &&) = delete;
182 Block &operator=(Block &&) = delete;
183
184 /// Return the parent section for this block.
185 Section &getSection() const { return Parent; }
186
187 /// Returns true if this is a zero-fill block.
188 ///
189 /// If true, getSize is callable but getContent is not (the content is
190 /// defined to be a sequence of zero bytes of length Size).
191 bool isZeroFill() const { return !Data; }
192
193 /// Returns the size of this defined addressable.
194 size_t getSize() const { return Size; }
195
196 /// Get the content for this block. Block must not be a zero-fill block.
197 ArrayRef<char> getContent() const {
198 assert(Data && "Section does not contain content");
199 return ArrayRef<char>(Data, Size);
200 }
201
202 /// Set the content for this block.
203 /// Caller is responsible for ensuring the underlying bytes are not
204 /// deallocated while pointed to by this block.
205 void setContent(ArrayRef<char> Content) {
206 Data = Content.data();
207 Size = Content.size();
208 }
209
210 /// Get the alignment for this content.
211 uint64_t getAlignment() const { return 1ull << P2Align; }
212
213 /// Set the alignment for this content.
214 void setAlignment(uint64_t Alignment) {
215 assert(isPowerOf2_64(Alignment) && "Alignment must be a power of two");
216 P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
217 }
218
219 /// Get the alignment offset for this content.
220 uint64_t getAlignmentOffset() const { return AlignmentOffset; }
221
222 /// Set the alignment offset for this content.
223 void setAlignmentOffset(uint64_t AlignmentOffset) {
224 assert(AlignmentOffset < (1ull << P2Align) &&
225 "Alignment offset can't exceed alignment");
226 this->AlignmentOffset = AlignmentOffset;
227 }
228
229 /// Add an edge to this block.
230 void addEdge(Edge::Kind K, Edge::OffsetT Offset, Symbol &Target,
231 Edge::AddendT Addend) {
232 Edges.push_back(Edge(K, Offset, Target, Addend));
233 }
234
235 /// Add an edge by copying an existing one. This is typically used when
236 /// moving edges between blocks.
237 void addEdge(const Edge &E) { Edges.push_back(E); }
238
239 /// Return the list of edges attached to this content.
240 iterator_range<edge_iterator> edges() {
241 return make_range(Edges.begin(), Edges.end());
242 }
243
244 /// Returns the list of edges attached to this content.
245 iterator_range<const_edge_iterator> edges() const {
246 return make_range(Edges.begin(), Edges.end());
247 }
248
249 /// Return the size of the edges list.
250 size_t edges_size() const { return Edges.size(); }
251
252 /// Returns true if the list of edges is empty.
253 bool edges_empty() const { return Edges.empty(); }
254
255 /// Remove the edge pointed to by the given iterator.
256 /// Returns an iterator to the new next element.
257 edge_iterator removeEdge(edge_iterator I) { return Edges.erase(I); }
258
259 /// Returns the address of the fixup for the given edge, which is equal to
260 /// this block's address plus the edge's offset.
261 JITTargetAddress getFixupAddress(const Edge &E) const {
262 return getAddress() + E.getOffset();
263 }
264
265private:
266 static constexpr uint64_t MaxAlignmentOffset = (1ULL << 57) - 1;
267
268 uint64_t P2Align : 5;
269 uint64_t AlignmentOffset : 57;
270 Section &Parent;
271 const char *Data = nullptr;
272 size_t Size = 0;
273 std::vector<Edge> Edges;
274};
275
276/// Describes symbol linkage. This can be used to make resolve definition
277/// clashes.
278enum class Linkage : uint8_t {
279 Strong,
280 Weak,
281};
282
283/// For errors and debugging output.
284const char *getLinkageName(Linkage L);
285
286/// Defines the scope in which this symbol should be visible:
287/// Default -- Visible in the public interface of the linkage unit.
288/// Hidden -- Visible within the linkage unit, but not exported from it.
289/// Local -- Visible only within the LinkGraph.
290enum class Scope : uint8_t {
291 Default,
292 Hidden,
293 Local
294};
295
296/// For debugging output.
297const char *getScopeName(Scope S);
298
299raw_ostream &operator<<(raw_ostream &OS, const Block &B);
300
301/// Symbol representation.
302///
303/// Symbols represent locations within Addressable objects.
304/// They can be either Named or Anonymous.
305/// Anonymous symbols have neither linkage nor visibility, and must point at
306/// ContentBlocks.
307/// Named symbols may be in one of four states:
308/// - Null: Default initialized. Assignable, but otherwise unusable.
309/// - Defined: Has both linkage and visibility and points to a ContentBlock
310/// - Common: Has both linkage and visibility, points to a null Addressable.
311/// - External: Has neither linkage nor visibility, points to an external
312/// Addressable.
313///
314class Symbol {
315 friend class LinkGraph;
316
317private:
318 Symbol(Addressable &Base, JITTargetAddress Offset, StringRef Name,
319 JITTargetAddress Size, Linkage L, Scope S, bool IsLive,
320 bool IsCallable)
321 : Name(Name), Base(&Base), Offset(Offset), Size(Size) {
322 assert(Offset <= MaxOffset && "Offset out of range");
323 setLinkage(L);
324 setScope(S);
325 setLive(IsLive);
326 setCallable(IsCallable);
327 }
328
329 static Symbol &constructCommon(void *SymStorage, Block &Base, StringRef Name,
330 JITTargetAddress Size, Scope S, bool IsLive) {
331 assert(SymStorage && "Storage cannot be null");
332 assert(!Name.empty() && "Common symbol name cannot be empty");
333 assert(Base.isDefined() &&
334 "Cannot create common symbol from undefined block");
335 assert(static_cast<Block &>(Base).getSize() == Size &&
336 "Common symbol size should match underlying block size");
337 auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
338 new (Sym) Symbol(Base, 0, Name, Size, Linkage::Weak, S, IsLive, false);
339 return *Sym;
340 }
341
342 static Symbol &constructExternal(void *SymStorage, Addressable &Base,
343 StringRef Name, JITTargetAddress Size,
344 Linkage L) {
345 assert(SymStorage && "Storage cannot be null");
346 assert(!Base.isDefined() &&
347 "Cannot create external symbol from defined block");
348 assert(!Name.empty() && "External symbol name cannot be empty");
349 auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
350 new (Sym) Symbol(Base, 0, Name, Size, L, Scope::Default, false, false);
351 return *Sym;
352 }
353
354 static Symbol &constructAbsolute(void *SymStorage, Addressable &Base,
355 StringRef Name, JITTargetAddress Size,
356 Linkage L, Scope S, bool IsLive) {
357 assert(SymStorage && "Storage cannot be null");
358 assert(!Base.isDefined() &&
359 "Cannot create absolute symbol from a defined block");
360 auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
361 new (Sym) Symbol(Base, 0, Name, Size, L, S, IsLive, false);
362 return *Sym;
363 }
364
365 static Symbol &constructAnonDef(void *SymStorage, Block &Base,
366 JITTargetAddress Offset,
367 JITTargetAddress Size, bool IsCallable,
368 bool IsLive) {
369 assert(SymStorage && "Storage cannot be null");
370 assert((Offset + Size) <= Base.getSize() &&
371 "Symbol extends past end of block");
372 auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
373 new (Sym) Symbol(Base, Offset, StringRef(), Size, Linkage::Strong,
374 Scope::Local, IsLive, IsCallable);
375 return *Sym;
376 }
377
378 static Symbol &constructNamedDef(void *SymStorage, Block &Base,
379 JITTargetAddress Offset, StringRef Name,
380 JITTargetAddress Size, Linkage L, Scope S,
381 bool IsLive, bool IsCallable) {
382 assert(SymStorage && "Storage cannot be null");
383 assert((Offset + Size) <= Base.getSize() &&
384 "Symbol extends past end of block");
385 assert(!Name.empty() && "Name cannot be empty");
386 auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
387 new (Sym) Symbol(Base, Offset, Name, Size, L, S, IsLive, IsCallable);
388 return *Sym;
389 }
390
391public:
392 /// Create a null Symbol. This allows Symbols to be default initialized for
393 /// use in containers (e.g. as map values). Null symbols are only useful for
394 /// assigning to.
395 Symbol() = default;
396
397 // Symbols are not movable or copyable.
398 Symbol(const Symbol &) = delete;
399 Symbol &operator=(const Symbol &) = delete;
400 Symbol(Symbol &&) = delete;
401 Symbol &operator=(Symbol &&) = delete;
402
403 /// Returns true if this symbol has a name.
404 bool hasName() const { return !Name.empty(); }
405
406 /// Returns the name of this symbol (empty if the symbol is anonymous).
407 StringRef getName() const {
408 assert((!Name.empty() || getScope() == Scope::Local) &&
409 "Anonymous symbol has non-local scope");
410 return Name;
411 }
412
413 /// Rename this symbol. The client is responsible for updating scope and
414 /// linkage if this name-change requires it.
415 void setName(StringRef Name) { this->Name = Name; }
416
417 /// Returns true if this Symbol has content (potentially) defined within this
418 /// object file (i.e. is anything but an external or absolute symbol).
419 bool isDefined() const {
420 assert(Base && "Attempt to access null symbol");
421 return Base->isDefined();
422 }
423
424 /// Returns true if this symbol is live (i.e. should be treated as a root for
425 /// dead stripping).
426 bool isLive() const {
427 assert(Base && "Attempting to access null symbol");
428 return IsLive;
429 }
430
431 /// Set this symbol's live bit.
432 void setLive(bool IsLive) { this->IsLive = IsLive; }
433
434 /// Returns true is this symbol is callable.
435 bool isCallable() const { return IsCallable; }
436
437 /// Set this symbol's callable bit.
438 void setCallable(bool IsCallable) { this->IsCallable = IsCallable; }
439
440 /// Returns true if the underlying addressable is an unresolved external.
441 bool isExternal() const {
442 assert(Base && "Attempt to access null symbol");
443 return !Base->isDefined() && !Base->isAbsolute();
444 }
445
446 /// Returns true if the underlying addressable is an absolute symbol.
447 bool isAbsolute() const {
448 assert(Base && "Attempt to access null symbol");
449 return Base->isAbsolute();
450 }
451
452 /// Return the addressable that this symbol points to.
453 Addressable &getAddressable() {
454 assert(Base && "Cannot get underlying addressable for null symbol");
455 return *Base;
456 }
457
458 /// Return the addressable that thsi symbol points to.
459 const Addressable &getAddressable() const {
460 assert(Base && "Cannot get underlying addressable for null symbol");
461 return *Base;
462 }
463
464 /// Return the Block for this Symbol (Symbol must be defined).
465 Block &getBlock() {
466 assert(Base && "Cannot get block for null symbol");
467 assert(Base->isDefined() && "Not a defined symbol");
468 return static_cast<Block &>(*Base);
469 }
470
471 /// Return the Block for this Symbol (Symbol must be defined).
472 const Block &getBlock() const {
473 assert(Base && "Cannot get block for null symbol");
474 assert(Base->isDefined() && "Not a defined symbol");
475 return static_cast<const Block &>(*Base);
476 }
477
478 /// Returns the offset for this symbol within the underlying addressable.
479 JITTargetAddress getOffset() const { return Offset; }
480
481 /// Returns the address of this symbol.
482 JITTargetAddress getAddress() const { return Base->getAddress() + Offset; }
483
484 /// Returns the size of this symbol.
485 JITTargetAddress getSize() const { return Size; }
486
487 /// Set the size of this symbol.
488 void setSize(JITTargetAddress Size) {
489 assert(Base && "Cannot set size for null Symbol");
490 assert((Size == 0 || Base->isDefined()) &&
491 "Non-zero size can only be set for defined symbols");
492 assert((Offset + Size <= static_cast<const Block &>(*Base).getSize()) &&
493 "Symbol size cannot extend past the end of its containing block");
494 this->Size = Size;
495 }
496
497 /// Returns true if this symbol is backed by a zero-fill block.
498 /// This method may only be called on defined symbols.
499 bool isSymbolZeroFill() const { return getBlock().isZeroFill(); }
500
501 /// Returns the content in the underlying block covered by this symbol.
502 /// This method may only be called on defined non-zero-fill symbols.
503 ArrayRef<char> getSymbolContent() const {
504 return getBlock().getContent().slice(Offset, Size);
505 }
506
507 /// Get the linkage for this Symbol.
508 Linkage getLinkage() const { return static_cast<Linkage>(L); }
509
510 /// Set the linkage for this Symbol.
511 void setLinkage(Linkage L) {
512 assert((L == Linkage::Strong || (!Base->isAbsolute() && !Name.empty())) &&
513 "Linkage can only be applied to defined named symbols");
514 this->L = static_cast<uint8_t>(L);
515 }
516
517 /// Get the visibility for this Symbol.
518 Scope getScope() const { return static_cast<Scope>(S); }
519
520 /// Set the visibility for this Symbol.
521 void setScope(Scope S) {
522 assert((!Name.empty() || S == Scope::Local) &&
523 "Can not set anonymous symbol to non-local scope");
524 assert((S == Scope::Default || Base->isDefined() || Base->isAbsolute()) &&
525 "Invalid visibility for symbol type");
526 this->S = static_cast<uint8_t>(S);
527 }
528
529private:
530 void makeExternal(Addressable &A) {
531 assert(!A.isDefined() && !A.isAbsolute() &&
532 "Attempting to make external with defined or absolute block");
533 Base = &A;
534 Offset = 0;
535 setScope(Scope::Default);
536 IsLive = 0;
537 // note: Size, Linkage and IsCallable fields left unchanged.
538 }
539
540 void makeAbsolute(Addressable &A) {
541 assert(!A.isDefined() && A.isAbsolute() &&
542 "Attempting to make absolute with defined or external block");
543 Base = &A;
544 Offset = 0;
545 }
546
547 void setBlock(Block &B) { Base = &B; }
548
549 void setOffset(uint64_t NewOffset) {
550 assert(NewOffset <= MaxOffset && "Offset out of range");
551 Offset = NewOffset;
552 }
553
554 static constexpr uint64_t MaxOffset = (1ULL << 59) - 1;
555
556 // FIXME: A char* or SymbolStringPtr may pack better.
557 StringRef Name;
558 Addressable *Base = nullptr;
559 uint64_t Offset : 59;
560 uint64_t L : 1;
561 uint64_t S : 2;
562 uint64_t IsLive : 1;
563 uint64_t IsCallable : 1;
564 JITTargetAddress Size = 0;
565};
566
567raw_ostream &operator<<(raw_ostream &OS, const Symbol &A);
568
569void printEdge(raw_ostream &OS, const Block &B, const Edge &E,
570 StringRef EdgeKindName);
571
572/// Represents an object file section.
573class Section {
574 friend class LinkGraph;
575
576private:
577 Section(StringRef Name, sys::Memory::ProtectionFlags Prot,
578 SectionOrdinal SecOrdinal)
579 : Name(Name), Prot(Prot), SecOrdinal(SecOrdinal) {}
580
581 using SymbolSet = DenseSet<Symbol *>;
582 using BlockSet = DenseSet<Block *>;
583
584public:
585 using symbol_iterator = SymbolSet::iterator;
586 using const_symbol_iterator = SymbolSet::const_iterator;
587
588 using block_iterator = BlockSet::iterator;
589 using const_block_iterator = BlockSet::const_iterator;
590
591 ~Section();
592
593 // Sections are not movable or copyable.
594 Section(const Section &) = delete;
595 Section &operator=(const Section &) = delete;
596 Section(Section &&) = delete;
597 Section &operator=(Section &&) = delete;
598
599 /// Returns the name of this section.
600 StringRef getName() const { return Name; }
601
602 /// Returns the protection flags for this section.
603 sys::Memory::ProtectionFlags getProtectionFlags() const { return Prot; }
604
605 /// Set the protection flags for this section.
606 void setProtectionFlags(sys::Memory::ProtectionFlags Prot) {
607 this->Prot = Prot;
608 }
609
610 /// Returns the ordinal for this section.
611 SectionOrdinal getOrdinal() const { return SecOrdinal; }
612
613 /// Returns an iterator over the blocks defined in this section.
614 iterator_range<block_iterator> blocks() {
615 return make_range(Blocks.begin(), Blocks.end());
616 }
617
618 /// Returns an iterator over the blocks defined in this section.
619 iterator_range<const_block_iterator> blocks() const {
620 return make_range(Blocks.begin(), Blocks.end());
621 }
622
623 /// Returns an iterator over the symbols defined in this section.
624 iterator_range<symbol_iterator> symbols() {
625 return make_range(Symbols.begin(), Symbols.end());
626 }
627
628 /// Returns an iterator over the symbols defined in this section.
629 iterator_range<const_symbol_iterator> symbols() const {
630 return make_range(Symbols.begin(), Symbols.end());
631 }
632
633 /// Return the number of symbols in this section.
634 SymbolSet::size_type symbols_size() { return Symbols.size(); }
635
636private:
637 void addSymbol(Symbol &Sym) {
638 assert(!Symbols.count(&Sym) && "Symbol is already in this section");
639 Symbols.insert(&Sym);
640 }
641
642 void removeSymbol(Symbol &Sym) {
643 assert(Symbols.count(&Sym) && "symbol is not in this section");
644 Symbols.erase(&Sym);
645 }
646
647 void addBlock(Block &B) {
648 assert(!Blocks.count(&B) && "Block is already in this section");
649 Blocks.insert(&B);
650 }
651
652 void removeBlock(Block &B) {
653 assert(Blocks.count(&B) && "Block is not in this section");
654 Blocks.erase(&B);
655 }
656
657 StringRef Name;
658 sys::Memory::ProtectionFlags Prot;
659 SectionOrdinal SecOrdinal = 0;
660 BlockSet Blocks;
661 SymbolSet Symbols;
662};
663
664/// Represents a section address range via a pair of Block pointers
665/// to the first and last Blocks in the section.
666class SectionRange {
667public:
668 SectionRange() = default;
669 SectionRange(const Section &Sec) {
670 if (llvm::empty(Sec.blocks()))
671 return;
672 First = Last = *Sec.blocks().begin();
673 for (auto *B : Sec.blocks()) {
674 if (B->getAddress() < First->getAddress())
675 First = B;
676 if (B->getAddress() > Last->getAddress())
677 Last = B;
678 }
679 }
680 Block *getFirstBlock() const {
681 assert((!Last || First) && "First can not be null if end is non-null");
682 return First;
683 }
684 Block *getLastBlock() const {
685 assert((First || !Last) && "Last can not be null if start is non-null");
686 return Last;
687 }
688 bool empty() const {
689 assert((First || !Last) && "Last can not be null if start is non-null");
690 return !First;
691 }
692 JITTargetAddress getStart() const {
693 return First ? First->getAddress() : 0;
694 }
695 JITTargetAddress getEnd() const {
696 return Last ? Last->getAddress() + Last->getSize() : 0;
697 }
698 uint64_t getSize() const { return getEnd() - getStart(); }
699
700private:
701 Block *First = nullptr;
702 Block *Last = nullptr;
703};
704
705class LinkGraph {
706private:
707 using SectionList = std::vector<std::unique_ptr<Section>>;
708 using ExternalSymbolSet = DenseSet<Symbol *>;
709 using BlockSet = DenseSet<Block *>;
710
711 template <typename... ArgTs>
712 Addressable &createAddressable(ArgTs &&... Args) {
713 Addressable *A =
714 reinterpret_cast<Addressable *>(Allocator.Allocate<Addressable>());
715 new (A) Addressable(std::forward<ArgTs>(Args)...);
716 return *A;
717 }
718
719 void destroyAddressable(Addressable &A) {
720 A.~Addressable();
721 Allocator.Deallocate(&A);
722 }
723
724 template <typename... ArgTs> Block &createBlock(ArgTs &&... Args) {
725 Block *B = reinterpret_cast<Block *>(Allocator.Allocate<Block>());
726 new (B) Block(std::forward<ArgTs>(Args)...);
727 B->getSection().addBlock(*B);
728 return *B;
729 }
730
731 void destroyBlock(Block &B) {
732 B.~Block();
733 Allocator.Deallocate(&B);
734 }
735
736 void destroySymbol(Symbol &S) {
737 S.~Symbol();
738 Allocator.Deallocate(&S);
739 }
740
741 static iterator_range<Section::block_iterator> getSectionBlocks(Section &S) {
742 return S.blocks();
743 }
744
745 static iterator_range<Section::const_block_iterator>
746 getSectionConstBlocks(Section &S) {
747 return S.blocks();
748 }
749
750 static iterator_range<Section::symbol_iterator>
751 getSectionSymbols(Section &S) {
752 return S.symbols();
753 }
754
755 static iterator_range<Section::const_symbol_iterator>
756 getSectionConstSymbols(Section &S) {
757 return S.symbols();
758 }
759
760public:
761 using external_symbol_iterator = ExternalSymbolSet::iterator;
762
763 using section_iterator = pointee_iterator<SectionList::iterator>;
764 using const_section_iterator = pointee_iterator<SectionList::const_iterator>;
765
766 template <typename OuterItrT, typename InnerItrT, typename T,
767 iterator_range<InnerItrT> getInnerRange(
768 typename OuterItrT::reference)>
769 class nested_collection_iterator
770 : public iterator_facade_base<
771 nested_collection_iterator<OuterItrT, InnerItrT, T, getInnerRange>,
772 std::forward_iterator_tag, T> {
773 public:
774 nested_collection_iterator() = default;
775
776 nested_collection_iterator(OuterItrT OuterI, OuterItrT OuterE)
777 : OuterI(OuterI), OuterE(OuterE),
778 InnerI(getInnerBegin(OuterI, OuterE)) {
779 moveToNonEmptyInnerOrEnd();
780 }
781
782 bool operator==(const nested_collection_iterator &RHS) const {
783 return (OuterI == RHS.OuterI) && (InnerI == RHS.InnerI);
784 }
785
786 T operator*() const {
787 assert(InnerI != getInnerRange(*OuterI).end() && "Dereferencing end?");
788 return *InnerI;
789 }
790
791 nested_collection_iterator operator++() {
792 ++InnerI;
793 moveToNonEmptyInnerOrEnd();
794 return *this;
795 }
796
797 private:
798 static InnerItrT getInnerBegin(OuterItrT OuterI, OuterItrT OuterE) {
799 return OuterI != OuterE ? getInnerRange(*OuterI).begin() : InnerItrT();
800 }
801
802 void moveToNonEmptyInnerOrEnd() {
803 while (OuterI != OuterE && InnerI == getInnerRange(*OuterI).end()) {
804 ++OuterI;
805 InnerI = getInnerBegin(OuterI, OuterE);
806 }
807 }
808
809 OuterItrT OuterI, OuterE;
810 InnerItrT InnerI;
811 };
812
813 using defined_symbol_iterator =
814 nested_collection_iterator<const_section_iterator,
815 Section::symbol_iterator, Symbol *,
816 getSectionSymbols>;
817
818 using const_defined_symbol_iterator =
819 nested_collection_iterator<const_section_iterator,
820 Section::const_symbol_iterator, const Symbol *,
821 getSectionConstSymbols>;
822
823 using block_iterator = nested_collection_iterator<const_section_iterator,
824 Section::block_iterator,
825 Block *, getSectionBlocks>;
826
827 using const_block_iterator =
828 nested_collection_iterator<const_section_iterator,
829 Section::const_block_iterator, const Block *,
830 getSectionConstBlocks>;
831
832 using GetEdgeKindNameFunction = const char *(*)(Edge::Kind);
833
834 LinkGraph(std::string Name, const Triple &TT, unsigned PointerSize,
835 support::endianness Endianness,
836 GetEdgeKindNameFunction GetEdgeKindName)
837 : Name(std::move(Name)), TT(TT), PointerSize(PointerSize),
838 Endianness(Endianness), GetEdgeKindName(std::move(GetEdgeKindName)) {}
839
840 /// Returns the name of this graph (usually the name of the original
841 /// underlying MemoryBuffer).
842 const std::string &getName() const { return Name; }
843
844 /// Returns the target triple for this Graph.
845 const Triple &getTargetTriple() const { return TT; }
846
847 /// Returns the pointer size for use in this graph.
848 unsigned getPointerSize() const { return PointerSize; }
849
850 /// Returns the endianness of content in this graph.
851 support::endianness getEndianness() const { return Endianness; }
852
853 const char *getEdgeKindName(Edge::Kind K) const { return GetEdgeKindName(K); }
854
855 /// Allocate a copy of the given string using the LinkGraph's allocator.
856 /// This can be useful when renaming symbols or adding new content to the
857 /// graph.
858 ArrayRef<char> allocateString(ArrayRef<char> Source) {
859 auto *AllocatedBuffer = Allocator.Allocate<char>(Source.size());
860 llvm::copy(Source, AllocatedBuffer);
861 return ArrayRef<char>(AllocatedBuffer, Source.size());
862 }
863
864 /// Allocate a copy of the given string using the LinkGraph's allocator.
865 /// This can be useful when renaming symbols or adding new content to the
866 /// graph.
867 ///
868 /// Note: This Twine-based overload requires an extra string copy and an
869 /// extra heap allocation for large strings. The ArrayRef<char> overload
870 /// should be preferred where possible.
871 ArrayRef<char> allocateString(Twine Source) {
872 SmallString<256> TmpBuffer;
873 auto SourceStr = Source.toStringRef(TmpBuffer);
874 auto *AllocatedBuffer = Allocator.Allocate<char>(SourceStr.size());
875 llvm::copy(SourceStr, AllocatedBuffer);
876 return ArrayRef<char>(AllocatedBuffer, SourceStr.size());
877 }
878
879 /// Create a section with the given name, protection flags, and alignment.
880 Section &createSection(StringRef Name, sys::Memory::ProtectionFlags Prot) {
881 assert(llvm::find_if(Sections,
882 [&](std::unique_ptr<Section> &Sec) {
883 return Sec->getName() == Name;
884 }) == Sections.end() &&
885 "Duplicate section name");
886 std::unique_ptr<Section> Sec(new Section(Name, Prot, Sections.size()));
887 Sections.push_back(std::move(Sec));
888 return *Sections.back();
889 }
890
891 /// Create a content block.
892 Block &createContentBlock(Section &Parent, ArrayRef<char> Content,
893 uint64_t Address, uint64_t Alignment,
894 uint64_t AlignmentOffset) {
895 return createBlock(Parent, Content, Address, Alignment, AlignmentOffset);
896 }
897
898 /// Create a zero-fill block.
899 Block &createZeroFillBlock(Section &Parent, uint64_t Size, uint64_t Address,
900 uint64_t Alignment, uint64_t AlignmentOffset) {
901 return createBlock(Parent, Size, Address, Alignment, AlignmentOffset);
902 }
903
904 /// Cache type for the splitBlock function.
905 using SplitBlockCache = Optional<SmallVector<Symbol *, 8>>;
906
907 /// Splits block B at the given index which must be greater than zero.
908 /// If SplitIndex == B.getSize() then this function is a no-op and returns B.
909 /// If SplitIndex < B.getSize() then this function returns a new block
910 /// covering the range [ 0, SplitIndex ), and B is modified to cover the range
911 /// [ SplitIndex, B.size() ).
912 ///
913 /// The optional Cache parameter can be used to speed up repeated calls to
914 /// splitBlock for a single block. If the value is None the cache will be
915 /// treated as uninitialized and splitBlock will populate it. Otherwise it
916 /// is assumed to contain the list of Symbols pointing at B, sorted in
917 /// descending order of offset.
918 ///
919 /// Notes:
920 ///
921 /// 1. The newly introduced block will have a new ordinal which will be
922 /// higher than any other ordinals in the section. Clients are responsible
923 /// for re-assigning block ordinals to restore a compatible order if
924 /// needed.
925 ///
926 /// 2. The cache is not automatically updated if new symbols are introduced
927 /// between calls to splitBlock. Any newly introduced symbols may be
928 /// added to the cache manually (descending offset order must be
929 /// preserved), or the cache can be set to None and rebuilt by
930 /// splitBlock on the next call.
931 Block &splitBlock(Block &B, size_t SplitIndex,
932 SplitBlockCache *Cache = nullptr);
933
934 /// Add an external symbol.
935 /// Some formats (e.g. ELF) allow Symbols to have sizes. For Symbols whose
936 /// size is not known, you should substitute '0'.
937 /// For external symbols Linkage determines whether the symbol must be
938 /// present during lookup: Externals with strong linkage must be found or
939 /// an error will be emitted. Externals with weak linkage are permitted to
940 /// be undefined, in which case they are assigned a value of 0.
941 Symbol &addExternalSymbol(StringRef Name, uint64_t Size, Linkage L) {
942 assert(llvm::count_if(ExternalSymbols,
943 [&](const Symbol *Sym) {
944 return Sym->getName() == Name;
945 }) == 0 &&
946 "Duplicate external symbol");
947 auto &Sym =
948 Symbol::constructExternal(Allocator.Allocate<Symbol>(),
949 createAddressable(0, false), Name, Size, L);
950 ExternalSymbols.insert(&Sym);
951 return Sym;
952 }
953
954 /// Add an absolute symbol.
955 Symbol &addAbsoluteSymbol(StringRef Name, JITTargetAddress Address,
956 uint64_t Size, Linkage L, Scope S, bool IsLive) {
957 assert(llvm::count_if(AbsoluteSymbols,
958 [&](const Symbol *Sym) {
959 return Sym->getName() == Name;
960 }) == 0 &&
961 "Duplicate absolute symbol");
962 auto &Sym = Symbol::constructAbsolute(Allocator.Allocate<Symbol>(),
963 createAddressable(Address), Name,
964 Size, L, S, IsLive);
965 AbsoluteSymbols.insert(&Sym);
966 return Sym;
967 }
968
969 /// Convenience method for adding a weak zero-fill symbol.
970 Symbol &addCommonSymbol(StringRef Name, Scope S, Section &Section,
971 JITTargetAddress Address, uint64_t Size,
972 uint64_t Alignment, bool IsLive) {
973 assert(llvm::count_if(defined_symbols(),
974 [&](const Symbol *Sym) {
975 return Sym->getName() == Name;
976 }) == 0 &&
977 "Duplicate defined symbol");
978 auto &Sym = Symbol::constructCommon(
979 Allocator.Allocate<Symbol>(),
980 createBlock(Section, Size, Address, Alignment, 0), Name, Size, S,
981 IsLive);
982 Section.addSymbol(Sym);
983 return Sym;
984 }
985
986 /// Add an anonymous symbol.
987 Symbol &addAnonymousSymbol(Block &Content, JITTargetAddress Offset,
988 JITTargetAddress Size, bool IsCallable,
989 bool IsLive) {
990 auto &Sym = Symbol::constructAnonDef(Allocator.Allocate<Symbol>(), Content,
991 Offset, Size, IsCallable, IsLive);
992 Content.getSection().addSymbol(Sym);
993 return Sym;
994 }
995
996 /// Add a named symbol.
997 Symbol &addDefinedSymbol(Block &Content, JITTargetAddress Offset,
998 StringRef Name, JITTargetAddress Size, Linkage L,
999 Scope S, bool IsCallable, bool IsLive) {
1000 assert(llvm::count_if(defined_symbols(),
1001 [&](const Symbol *Sym) {
1002 return Sym->getName() == Name;
1003 }) == 0 &&
1004 "Duplicate defined symbol");
1005 auto &Sym =
1006 Symbol::constructNamedDef(Allocator.Allocate<Symbol>(), Content, Offset,
1007 Name, Size, L, S, IsLive, IsCallable);
1008 Content.getSection().addSymbol(Sym);
1009 return Sym;
1010 }
1011
1012 iterator_range<section_iterator> sections() {
1013 return make_range(section_iterator(Sections.begin()),
1014 section_iterator(Sections.end()));
1015 }
1016
1017 /// Returns the section with the given name if it exists, otherwise returns
1018 /// null.
1019 Section *findSectionByName(StringRef Name) {
1020 for (auto &S : sections())
1021 if (S.getName() == Name)
1022 return &S;
1023 return nullptr;
1024 }
1025
1026 iterator_range<block_iterator> blocks() {
1027 return make_range(block_iterator(Sections.begin(), Sections.end()),
1028 block_iterator(Sections.end(), Sections.end()));
1029 }
1030
1031 iterator_range<const_block_iterator> blocks() const {
1032 return make_range(const_block_iterator(Sections.begin(), Sections.end()),
1033 const_block_iterator(Sections.end(), Sections.end()));
1034 }
1035
1036 iterator_range<external_symbol_iterator> external_symbols() {
1037 return make_range(ExternalSymbols.begin(), ExternalSymbols.end());
1038 }
1039
1040 iterator_range<external_symbol_iterator> absolute_symbols() {
1041 return make_range(AbsoluteSymbols.begin(), AbsoluteSymbols.end());
1042 }
1043
1044 iterator_range<defined_symbol_iterator> defined_symbols() {
1045 return make_range(defined_symbol_iterator(Sections.begin(), Sections.end()),
1046 defined_symbol_iterator(Sections.end(), Sections.end()));
1047 }
1048
1049 iterator_range<const_defined_symbol_iterator> defined_symbols() const {
1050 return make_range(
1051 const_defined_symbol_iterator(Sections.begin(), Sections.end()),
1052 const_defined_symbol_iterator(Sections.end(), Sections.end()));
1053 }
1054
1055 /// Make the given symbol external (must not already be external).
1056 ///
1057 /// Symbol size, linkage and callability will be left unchanged. Symbol scope
1058 /// will be set to Default, and offset will be reset to 0.
1059 void makeExternal(Symbol &Sym) {
1060 assert(!Sym.isExternal() && "Symbol is already external");
1061 if (Sym.isAbsolute()) {
1062 assert(AbsoluteSymbols.count(&Sym) &&
1063 "Sym is not in the absolute symbols set");
1064 assert(Sym.getOffset() == 0 && "Absolute not at offset 0");
1065 AbsoluteSymbols.erase(&Sym);
1066 Sym.getAddressable().setAbsolute(false);
1067 } else {
1068 assert(Sym.isDefined() && "Sym is not a defined symbol");
1069 Section &Sec = Sym.getBlock().getSection();
1070 Sec.removeSymbol(Sym);
1071 Sym.makeExternal(createAddressable(0, false));
1072 }
1073 ExternalSymbols.insert(&Sym);
1074 }
1075
1076 /// Make the given symbol an absolute with the given address (must not already
1077 /// be absolute).
1078 ///
1079 /// Symbol size, linkage, scope, and callability, and liveness will be left
1080 /// unchanged. Symbol offset will be reset to 0.
1081 void makeAbsolute(Symbol &Sym, JITTargetAddress Address) {
1082 assert(!Sym.isAbsolute() && "Symbol is already absolute");
1083 if (Sym.isExternal()) {
1084 assert(ExternalSymbols.count(&Sym) &&
1085 "Sym is not in the absolute symbols set");
1086 assert(Sym.getOffset() == 0 && "External is not at offset 0");
1087 ExternalSymbols.erase(&Sym);
1088 Sym.getAddressable().setAbsolute(true);
1089 } else {
1090 assert(Sym.isDefined() && "Sym is not a defined symbol");
1091 Section &Sec = Sym.getBlock().getSection();
1092 Sec.removeSymbol(Sym);
1093 Sym.makeAbsolute(createAddressable(Address));
1094 }
1095 AbsoluteSymbols.insert(&Sym);
1096 }
1097
1098 /// Turn an absolute or external symbol into a defined one by attaching it to
1099 /// a block. Symbol must not already be defined.
1100 void makeDefined(Symbol &Sym, Block &Content, JITTargetAddress Offset,
1101 JITTargetAddress Size, Linkage L, Scope S, bool IsLive) {
1102 assert(!Sym.isDefined() && "Sym is already a defined symbol");
1103 if (Sym.isAbsolute()) {
1104 assert(AbsoluteSymbols.count(&Sym) &&
1105 "Symbol is not in the absolutes set");
1106 AbsoluteSymbols.erase(&Sym);
1107 } else {
1108 assert(ExternalSymbols.count(&Sym) &&
1109 "Symbol is not in the externals set");
1110 ExternalSymbols.erase(&Sym);
1111 }
1112 Addressable &OldBase = *Sym.Base;
1113 Sym.setBlock(Content);
1114 Sym.setOffset(Offset);
1115 Sym.setSize(Size);
1116 Sym.setLinkage(L);
1117 Sym.setScope(S);
1118 Sym.setLive(IsLive);
1119 Content.getSection().addSymbol(Sym);
1120 destroyAddressable(OldBase);
1121 }
1122
1123 /// Removes an external symbol. Also removes the underlying Addressable.
1124 void removeExternalSymbol(Symbol &Sym) {
1125 assert(!Sym.isDefined() && !Sym.isAbsolute() &&
1126 "Sym is not an external symbol");
1127 assert(ExternalSymbols.count(&Sym) && "Symbol is not in the externals set");
1128 ExternalSymbols.erase(&Sym);
1129 Addressable &Base = *Sym.Base;
1130 assert(llvm::find_if(ExternalSymbols,
1131 [&](Symbol *AS) { return AS->Base == &Base; }) ==
1132 ExternalSymbols.end() &&
1133 "Base addressable still in use");
1134 destroySymbol(Sym);
1135 destroyAddressable(Base);
1136 }
1137
1138 /// Remove an absolute symbol. Also removes the underlying Addressable.
1139 void removeAbsoluteSymbol(Symbol &Sym) {
1140 assert(!Sym.isDefined() && Sym.isAbsolute() &&
1141 "Sym is not an absolute symbol");
1142 assert(AbsoluteSymbols.count(&Sym) &&
1143 "Symbol is not in the absolute symbols set");
1144 AbsoluteSymbols.erase(&Sym);
1145 Addressable &Base = *Sym.Base;
1146 assert(llvm::find_if(ExternalSymbols,
1147 [&](Symbol *AS) { return AS->Base == &Base; }) ==
1148 ExternalSymbols.end() &&
1149 "Base addressable still in use");
1150 destroySymbol(Sym);
1151 destroyAddressable(Base);
1152 }
1153
1154 /// Removes defined symbols. Does not remove the underlying block.
1155 void removeDefinedSymbol(Symbol &Sym) {
1156 assert(Sym.isDefined() && "Sym is not a defined symbol");
1157 Sym.getBlock().getSection().removeSymbol(Sym);
1158 destroySymbol(Sym);
1159 }
1160
1161 /// Remove a block.
1162 void removeBlock(Block &B) {
1163 assert(llvm::none_of(B.getSection().symbols(),
1164 [&](const Symbol *Sym) {
1165 return &Sym->getBlock() == &B;
1166 }) &&
1167 "Block still has symbols attached");
1168 B.getSection().removeBlock(B);
1169 destroyBlock(B);
1170 }
1171
1172 /// Dump the graph.
1173 void dump(raw_ostream &OS);
1174
1175private:
1176 // Put the BumpPtrAllocator first so that we don't free any of the underlying
1177 // memory until the Symbol/Addressable destructors have been run.
1178 BumpPtrAllocator Allocator;
1179
1180 std::string Name;
1181 Triple TT;
1182 unsigned PointerSize;
1183 support::endianness Endianness;
1184 GetEdgeKindNameFunction GetEdgeKindName = nullptr;
1185 SectionList Sections;
1186 ExternalSymbolSet ExternalSymbols;
1187 ExternalSymbolSet AbsoluteSymbols;
1188};
1189
1190/// Enables easy lookup of blocks by addresses.
1191class BlockAddressMap {
1192public:
1193 using AddrToBlockMap = std::map<JITTargetAddress, Block *>;
1194 using const_iterator = AddrToBlockMap::const_iterator;
1195
1196 /// A block predicate that always adds all blocks.
1197 static bool includeAllBlocks(const Block &B) { return true; }
1198
1199 /// A block predicate that always includes blocks with non-null addresses.
1200 static bool includeNonNull(const Block &B) { return B.getAddress(); }
1201
1202 BlockAddressMap() = default;
1203
1204 /// Add a block to the map. Returns an error if the block overlaps with any
1205 /// existing block.
1206 template <typename PredFn = decltype(includeAllBlocks)>
1207 Error addBlock(Block &B, PredFn Pred = includeAllBlocks) {
1208 if (!Pred(B))
1209 return Error::success();
1210
1211 auto I = AddrToBlock.upper_bound(B.getAddress());
1212
1213 // If we're not at the end of the map, check for overlap with the next
1214 // element.
1215 if (I != AddrToBlock.end()) {
1216 if (B.getAddress() + B.getSize() > I->second->getAddress())
1217 return overlapError(B, *I->second);
1218 }
1219
1220 // If we're not at the start of the map, check for overlap with the previous
1221 // element.
1222 if (I != AddrToBlock.begin()) {
1223 auto &PrevBlock = *std::prev(I)->second;
1224 if (PrevBlock.getAddress() + PrevBlock.getSize() > B.getAddress())
1225 return overlapError(B, PrevBlock);
1226 }
1227
1228 AddrToBlock.insert(I, std::make_pair(B.getAddress(), &B));
1229 return Error::success();
1230 }
1231
1232 /// Add a block to the map without checking for overlap with existing blocks.
1233 /// The client is responsible for ensuring that the block added does not
1234 /// overlap with any existing block.
1235 void addBlockWithoutChecking(Block &B) { AddrToBlock[B.getAddress()] = &B; }
1236
1237 /// Add a range of blocks to the map. Returns an error if any block in the
1238 /// range overlaps with any other block in the range, or with any existing
1239 /// block in the map.
1240 template <typename BlockPtrRange,
1241 typename PredFn = decltype(includeAllBlocks)>
1242 Error addBlocks(BlockPtrRange &&Blocks, PredFn Pred = includeAllBlocks) {
1243 for (auto *B : Blocks)
1244 if (auto Err = addBlock(*B, Pred))
1245 return Err;
1246 return Error::success();
1247 }
1248
1249 /// Add a range of blocks to the map without checking for overlap with
1250 /// existing blocks. The client is responsible for ensuring that the block
1251 /// added does not overlap with any existing block.
1252 template <typename BlockPtrRange>
1253 void addBlocksWithoutChecking(BlockPtrRange &&Blocks) {
1254 for (auto *B : Blocks)
1255 addBlockWithoutChecking(*B);
1256 }
1257
1258 /// Iterates over (Address, Block*) pairs in ascending order of address.
1259 const_iterator begin() const { return AddrToBlock.begin(); }
1260 const_iterator end() const { return AddrToBlock.end(); }
1261
1262 /// Returns the block starting at the given address, or nullptr if no such
1263 /// block exists.
1264 Block *getBlockAt(JITTargetAddress Addr) const {
1265 auto I = AddrToBlock.find(Addr);
1266 if (I == AddrToBlock.end())
1267 return nullptr;
1268 return I->second;
1269 }
1270
1271 /// Returns the block covering the given address, or nullptr if no such block
1272 /// exists.
1273 Block *getBlockCovering(JITTargetAddress Addr) const {
1274 auto I = AddrToBlock.upper_bound(Addr);
1275 if (I == AddrToBlock.begin())
1276 return nullptr;
1277 auto *B = std::prev(I)->second;
1278 if (Addr < B->getAddress() + B->getSize())
1279 return B;
1280 return nullptr;
1281 }
1282
1283private:
1284 Error overlapError(Block &NewBlock, Block &ExistingBlock) {
1285 auto NewBlockEnd = NewBlock.getAddress() + NewBlock.getSize();
1286 auto ExistingBlockEnd =
1287 ExistingBlock.getAddress() + ExistingBlock.getSize();
1288 return make_error<JITLinkError>(
1289 "Block at " +
1290 formatv("{0:x16} -- {1:x16}", NewBlock.getAddress(), NewBlockEnd) +
1291 " overlaps " +
1292 formatv("{0:x16} -- {1:x16}", ExistingBlock.getAddress(),
1293 ExistingBlockEnd));
1294 }
1295
1296 AddrToBlockMap AddrToBlock;
1297};
1298
1299/// A map of addresses to Symbols.
1300class SymbolAddressMap {
1301public:
1302 using SymbolVector = SmallVector<Symbol *, 1>;
1303
1304 /// Add a symbol to the SymbolAddressMap.
1305 void addSymbol(Symbol &Sym) {
1306 AddrToSymbols[Sym.getAddress()].push_back(&Sym);
1307 }
1308
1309 /// Add all symbols in a given range to the SymbolAddressMap.
1310 template <typename SymbolPtrCollection>
1311 void addSymbols(SymbolPtrCollection &&Symbols) {
1312 for (auto *Sym : Symbols)
1313 addSymbol(*Sym);
1314 }
1315
1316 /// Returns the list of symbols that start at the given address, or nullptr if
1317 /// no such symbols exist.
1318 const SymbolVector *getSymbolsAt(JITTargetAddress Addr) const {
1319 auto I = AddrToSymbols.find(Addr);
1320 if (I == AddrToSymbols.end())
1321 return nullptr;
1322 return &I->second;
1323 }
1324
1325private:
1326 std::map<JITTargetAddress, SymbolVector> AddrToSymbols;
1327};
1328
1329/// A function for mutating LinkGraphs.
1330using LinkGraphPassFunction = std::function<Error(LinkGraph &)>;
1331
1332/// A list of LinkGraph passes.
1333using LinkGraphPassList = std::vector<LinkGraphPassFunction>;
1334
1335/// An LinkGraph pass configuration, consisting of a list of pre-prune,
1336/// post-prune, and post-fixup passes.
1337struct PassConfiguration {
1338
1339 /// Pre-prune passes.
1340 ///
1341 /// These passes are called on the graph after it is built, and before any
1342 /// symbols have been pruned. Graph nodes still have their original vmaddrs.
1343 ///
1344 /// Notable use cases: Marking symbols live or should-discard.
1345 LinkGraphPassList PrePrunePasses;
1346
1347 /// Post-prune passes.
1348 ///
1349 /// These passes are called on the graph after dead stripping, but before
1350 /// memory is allocated or nodes assigned their final addresses.
1351 ///
1352 /// Notable use cases: Building GOT, stub, and TLV symbols.
1353 LinkGraphPassList PostPrunePasses;
1354
1355 /// Post-allocation passes.
1356 ///
1357 /// These passes are called on the graph after memory has been allocated and
1358 /// defined nodes have been assigned their final addresses, but before the
1359 /// context has been notified of these addresses. At this point externals
1360 /// have not been resolved, and symbol content has not yet been copied into
1361 /// working memory.
1362 ///
1363 /// Notable use cases: Setting up data structures associated with addresses
1364 /// of defined symbols (e.g. a mapping of __dso_handle to JITDylib* for the
1365 /// JIT runtime) -- using a PostAllocationPass for this ensures that the
1366 /// data structures are in-place before any query for resolved symbols
1367 /// can complete.
1368 LinkGraphPassList PostAllocationPasses;
1369
1370 /// Pre-fixup passes.
1371 ///
1372 /// These passes are called on the graph after memory has been allocated,
1373 /// content copied into working memory, and all nodes (including externals)
1374 /// have been assigned their final addresses, but before any fixups have been
1375 /// applied.
1376 ///
1377 /// Notable use cases: Late link-time optimizations like GOT and stub
1378 /// elimination.
1379 LinkGraphPassList PreFixupPasses;
1380
1381 /// Post-fixup passes.
1382 ///
1383 /// These passes are called on the graph after block contents has been copied
1384 /// to working memory, and fixups applied. Blocks have been updated to point
1385 /// to their fixed up content.
1386 ///
1387 /// Notable use cases: Testing and validation.
1388 LinkGraphPassList PostFixupPasses;
1389};
1390
1391/// Flags for symbol lookup.
1392///
1393/// FIXME: These basically duplicate orc::SymbolLookupFlags -- We should merge
1394/// the two types once we have an OrcSupport library.
1395enum class SymbolLookupFlags { RequiredSymbol, WeaklyReferencedSymbol };
1396
1397raw_ostream &operator<<(raw_ostream &OS, const SymbolLookupFlags &LF);
1398
1399/// A map of symbol names to resolved addresses.
1400using AsyncLookupResult = DenseMap<StringRef, JITEvaluatedSymbol>;
1401
1402/// A function object to call with a resolved symbol map (See AsyncLookupResult)
1403/// or an error if resolution failed.
1404class JITLinkAsyncLookupContinuation {
1405public:
1406 virtual ~JITLinkAsyncLookupContinuation() {}
1407 virtual void run(Expected<AsyncLookupResult> LR) = 0;
1408
1409private:
1410 virtual void anchor();
1411};
1412
1413/// Create a lookup continuation from a function object.
1414template <typename Continuation>
1415std::unique_ptr<JITLinkAsyncLookupContinuation>
1416createLookupContinuation(Continuation Cont) {
1417
1418 class Impl final : public JITLinkAsyncLookupContinuation {
1419 public:
1420 Impl(Continuation C) : C(std::move(C)) {}
1421 void run(Expected<AsyncLookupResult> LR) override { C(std::move(LR)); }
1422
1423 private:
1424 Continuation C;
1425 };
1426
1427 return std::make_unique<Impl>(std::move(Cont));
1428}
1429
1430/// Holds context for a single jitLink invocation.
1431class JITLinkContext {
1432public:
1433 using LookupMap = DenseMap<StringRef, SymbolLookupFlags>;
1434
1435 /// Create a JITLinkContext.
1436 JITLinkContext(const JITLinkDylib *JD) : JD(JD) {}
1437
1438 /// Destroy a JITLinkContext.
1439 virtual ~JITLinkContext();
1440
1441 /// Return the JITLinkDylib that this link is targeting, if any.
1442 const JITLinkDylib *getJITLinkDylib() const { return JD; }
1443
1444 /// Return the MemoryManager to be used for this link.
1445 virtual JITLinkMemoryManager &getMemoryManager() = 0;
1446
1447 /// Notify this context that linking failed.
1448 /// Called by JITLink if linking cannot be completed.
1449 virtual void notifyFailed(Error Err) = 0;
1450
1451 /// Called by JITLink to resolve external symbols. This method is passed a
1452 /// lookup continutation which it must call with a result to continue the
1453 /// linking process.
1454 virtual void lookup(const LookupMap &Symbols,
1455 std::unique_ptr<JITLinkAsyncLookupContinuation> LC) = 0;
1456
1457 /// Called by JITLink once all defined symbols in the graph have been assigned
1458 /// their final memory locations in the target process. At this point the
1459 /// LinkGraph can be inspected to build a symbol table, however the block
1460 /// content will not generally have been copied to the target location yet.
1461 ///
1462 /// If the client detects an error in the LinkGraph state (e.g. unexpected or
1463 /// missing symbols) they may return an error here. The error will be
1464 /// propagated to notifyFailed and the linker will bail out.
1465 virtual Error notifyResolved(LinkGraph &G) = 0;
1466
1467 /// Called by JITLink to notify the context that the object has been
1468 /// finalized (i.e. emitted to memory and memory permissions set). If all of
1469 /// this objects dependencies have also been finalized then the code is ready
1470 /// to run.
1471 virtual void
1472 notifyFinalized(std::unique_ptr<JITLinkMemoryManager::Allocation> A) = 0;
1473
1474 /// Called by JITLink prior to linking to determine whether default passes for
1475 /// the target should be added. The default implementation returns true.
1476 /// If subclasses override this method to return false for any target then
1477 /// they are required to fully configure the pass pipeline for that target.
1478 virtual bool shouldAddDefaultTargetPasses(const Triple &TT) const;
1479
1480 /// Returns the mark-live pass to be used for this link. If no pass is
1481 /// returned (the default) then the target-specific linker implementation will
1482 /// choose a conservative default (usually marking all symbols live).
1483 /// This function is only called if shouldAddDefaultTargetPasses returns true,
1484 /// otherwise the JITContext is responsible for adding a mark-live pass in
1485 /// modifyPassConfig.
1486 virtual LinkGraphPassFunction getMarkLivePass(const Triple &TT) const;
1487
1488 /// Called by JITLink to modify the pass pipeline prior to linking.
1489 /// The default version performs no modification.
1490 virtual Error modifyPassConfig(LinkGraph &G, PassConfiguration &Config);
1491
1492private:
1493 const JITLinkDylib *JD = nullptr;
1494};
1495
1496/// Marks all symbols in a graph live. This can be used as a default,
1497/// conservative mark-live implementation.
1498Error markAllSymbolsLive(LinkGraph &G);
1499
1500/// Create an out of range error for the given edge in the given block.
1501Error makeTargetOutOfRangeError(const LinkGraph &G, const Block &B,
1502 const Edge &E);
1503
1504/// Create a LinkGraph from the given object buffer.
1505///
1506/// Note: The graph does not take ownership of the underlying buffer, nor copy
1507/// its contents. The caller is responsible for ensuring that the object buffer
1508/// outlives the graph.
1509Expected<std::unique_ptr<LinkGraph>>
1510createLinkGraphFromObject(MemoryBufferRef ObjectBuffer);
1511
1512/// Link the given graph.
1513void link(std::unique_ptr<LinkGraph> G, std::unique_ptr<JITLinkContext> Ctx);
1514
1515} // end namespace jitlink
1516} // end namespace llvm
1517
1518#endif // LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H
1519