1 //===------------ JITLink.h - JIT linker functionality ----------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // Contains generic JIT-linker types.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H
14 #define LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H
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"
33 #include <system_error>
41 /// Base class for errors originating in JIT linker, e.g. missing relocation
43 class JITLinkError : public ErrorInfo<JITLinkError> {
47 JITLinkError(Twine ErrMsg) : ErrMsg(ErrMsg.str()) {}
49 void log(raw_ostream &OS) const override;
50 const std::string &getErrorMessage() const { return ErrMsg; }
51 std::error_code convertToErrorCode() const override;
57 /// Represents fixups and constraints in the LinkGraph.
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.
69 using OffsetT = uint32_t;
70 using AddendT = int64_t;
72 Edge(Kind K, OffsetT Offset, Symbol &Target, AddendT Addend)
73 : Target(&Target), Offset(Offset), Addend(Addend), K(K) {}
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;
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; }
91 Symbol *Target = nullptr;
97 /// Returns the string name of the given generic edge kind, or "unknown"
98 /// otherwise. Useful for debugging.
99 const char *getGenericEdgeKindName(Edge::Kind K);
101 /// Base class for Addressable entities (externals, absolutes, blocks).
103 friend class LinkGraph;
106 Addressable(JITTargetAddress Address, bool IsDefined)
107 : Address(Address), IsDefined(IsDefined), IsAbsolute(false) {}
109 Addressable(JITTargetAddress Address)
110 : Address(Address), IsDefined(false), IsAbsolute(true) {
111 assert(!(IsDefined && IsAbsolute) &&
112 "Block cannot be both defined and absolute");
116 Addressable(const Addressable &) = delete;
117 Addressable &operator=(const Addressable &) = default;
118 Addressable(Addressable &&) = delete;
119 Addressable &operator=(Addressable &&) = default;
121 JITTargetAddress getAddress() const { return Address; }
122 void setAddress(JITTargetAddress Address) { this->Address = Address; }
124 /// Returns true if this is a defined addressable, in which case you
125 /// can downcast this to a .
126 bool isDefined() const { return static_cast<bool>(IsDefined); }
127 bool isAbsolute() const { return static_cast<bool>(IsAbsolute); }
130 JITTargetAddress Address = 0;
131 uint64_t IsDefined : 1;
132 uint64_t IsAbsolute : 1;
135 using SectionOrdinal = unsigned;
137 /// An Addressable with content and edges.
138 class Block : public Addressable {
139 friend class LinkGraph;
142 /// Create a zero-fill defined addressable.
143 Block(Section &Parent, JITTargetAddress Size, JITTargetAddress Address,
144 uint64_t Alignment, uint64_t AlignmentOffset)
145 : Addressable(Address, true), Parent(Parent), Size(Size) {
146 assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2");
147 assert(AlignmentOffset < Alignment &&
148 "Alignment offset cannot exceed alignment");
149 assert(AlignmentOffset <= MaxAlignmentOffset &&
150 "Alignment offset exceeds maximum");
151 P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
152 this->AlignmentOffset = AlignmentOffset;
155 /// Create a defined addressable for the given content.
156 Block(Section &Parent, StringRef Content, JITTargetAddress Address,
157 uint64_t Alignment, uint64_t AlignmentOffset)
158 : Addressable(Address, true), Parent(Parent), Data(Content.data()),
159 Size(Content.size()) {
160 assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2");
161 assert(AlignmentOffset < Alignment &&
162 "Alignment offset cannot exceed alignment");
163 assert(AlignmentOffset <= MaxAlignmentOffset &&
164 "Alignment offset exceeds maximum");
165 P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
166 this->AlignmentOffset = AlignmentOffset;
170 using EdgeVector = std::vector<Edge>;
171 using edge_iterator = EdgeVector::iterator;
172 using const_edge_iterator = EdgeVector::const_iterator;
174 Block(const Block &) = delete;
175 Block &operator=(const Block &) = delete;
176 Block(Block &&) = delete;
177 Block &operator=(Block &&) = delete;
179 /// Return the parent section for this block.
180 Section &getSection() const { return Parent; }
182 /// Returns true if this is a zero-fill block.
184 /// If true, getSize is callable but getContent is not (the content is
185 /// defined to be a sequence of zero bytes of length Size).
186 bool isZeroFill() const { return !Data; }
188 /// Returns the size of this defined addressable.
189 size_t getSize() const { return Size; }
191 /// Get the content for this block. Block must not be a zero-fill block.
192 StringRef getContent() const {
193 assert(Data && "Section does not contain content");
194 return StringRef(Data, Size);
197 /// Set the content for this block.
198 /// Caller is responsible for ensuring the underlying bytes are not
199 /// deallocated while pointed to by this block.
200 void setContent(StringRef Content) {
201 Data = Content.data();
202 Size = Content.size();
205 /// Get the alignment for this content.
206 uint64_t getAlignment() const { return 1ull << P2Align; }
208 /// Set the alignment for this content.
209 void setAlignment(uint64_t Alignment) {
210 assert(isPowerOf2_64(Alignment) && "Alignment must be a power of two");
211 P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
214 /// Get the alignment offset for this content.
215 uint64_t getAlignmentOffset() const { return AlignmentOffset; }
217 /// Set the alignment offset for this content.
218 void setAlignmentOffset(uint64_t AlignmentOffset) {
219 assert(AlignmentOffset < (1ull << P2Align) &&
220 "Alignment offset can't exceed alignment");
221 this->AlignmentOffset = AlignmentOffset;
224 /// Add an edge to this block.
225 void addEdge(Edge::Kind K, Edge::OffsetT Offset, Symbol &Target,
226 Edge::AddendT Addend) {
227 Edges.push_back(Edge(K, Offset, Target, Addend));
230 /// Add an edge by copying an existing one. This is typically used when
231 /// moving edges between blocks.
232 void addEdge(const Edge &E) { Edges.push_back(E); }
234 /// Return the list of edges attached to this content.
235 iterator_range<edge_iterator> edges() {
236 return make_range(Edges.begin(), Edges.end());
239 /// Returns the list of edges attached to this content.
240 iterator_range<const_edge_iterator> edges() const {
241 return make_range(Edges.begin(), Edges.end());
244 /// Return the size of the edges list.
245 size_t edges_size() const { return Edges.size(); }
247 /// Returns true if the list of edges is empty.
248 bool edges_empty() const { return Edges.empty(); }
250 /// Remove the edge pointed to by the given iterator.
251 /// Returns an iterator to the new next element.
252 edge_iterator removeEdge(edge_iterator I) { return Edges.erase(I); }
255 static constexpr uint64_t MaxAlignmentOffset = (1ULL << 57) - 1;
257 uint64_t P2Align : 5;
258 uint64_t AlignmentOffset : 57;
260 const char *Data = nullptr;
262 std::vector<Edge> Edges;
265 /// Describes symbol linkage. This can be used to make resolve definition
267 enum class Linkage : uint8_t {
272 /// For errors and debugging output.
273 const char *getLinkageName(Linkage L);
275 /// Defines the scope in which this symbol should be visible:
276 /// Default -- Visible in the public interface of the linkage unit.
277 /// Hidden -- Visible within the linkage unit, but not exported from it.
278 /// Local -- Visible only within the LinkGraph.
279 enum class Scope : uint8_t { Default, Hidden, Local };
281 /// For debugging output.
282 const char *getScopeName(Scope S);
284 raw_ostream &operator<<(raw_ostream &OS, const Block &B);
286 /// Symbol representation.
288 /// Symbols represent locations within Addressable objects.
289 /// They can be either Named or Anonymous.
290 /// Anonymous symbols have neither linkage nor visibility, and must point at
292 /// Named symbols may be in one of four states:
293 /// - Null: Default initialized. Assignable, but otherwise unusable.
294 /// - Defined: Has both linkage and visibility and points to a ContentBlock
295 /// - Common: Has both linkage and visibility, points to a null Addressable.
296 /// - External: Has neither linkage nor visibility, points to an external
300 friend class LinkGraph;
303 Symbol(Addressable &Base, JITTargetAddress Offset, StringRef Name,
304 JITTargetAddress Size, Linkage L, Scope S, bool IsLive,
306 : Name(Name), Base(&Base), Offset(Offset), Size(Size) {
307 assert(Offset <= MaxOffset && "Offset out of range");
311 setCallable(IsCallable);
314 static Symbol &constructCommon(void *SymStorage, Block &Base, StringRef Name,
315 JITTargetAddress Size, Scope S, bool IsLive) {
316 assert(SymStorage && "Storage cannot be null");
317 assert(!Name.empty() && "Common symbol name cannot be empty");
318 assert(Base.isDefined() &&
319 "Cannot create common symbol from undefined block");
320 assert(static_cast<Block &>(Base).getSize() == Size &&
321 "Common symbol size should match underlying block size");
322 auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
323 new (Sym) Symbol(Base, 0, Name, Size, Linkage::Weak, S, IsLive, false);
327 static Symbol &constructExternal(void *SymStorage, Addressable &Base,
328 StringRef Name, JITTargetAddress Size,
330 assert(SymStorage && "Storage cannot be null");
331 assert(!Base.isDefined() &&
332 "Cannot create external symbol from defined block");
333 assert(!Name.empty() && "External symbol name cannot be empty");
334 auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
335 new (Sym) Symbol(Base, 0, Name, Size, L, Scope::Default, false, false);
339 static Symbol &constructAbsolute(void *SymStorage, Addressable &Base,
340 StringRef Name, JITTargetAddress Size,
341 Linkage L, Scope S, bool IsLive) {
342 assert(SymStorage && "Storage cannot be null");
343 assert(!Base.isDefined() &&
344 "Cannot create absolute symbol from a defined block");
345 auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
346 new (Sym) Symbol(Base, 0, Name, Size, L, S, IsLive, false);
350 static Symbol &constructAnonDef(void *SymStorage, Block &Base,
351 JITTargetAddress Offset,
352 JITTargetAddress Size, bool IsCallable,
354 assert(SymStorage && "Storage cannot be null");
355 assert((Offset + Size) <= Base.getSize() &&
356 "Symbol extends past end of block");
357 auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
358 new (Sym) Symbol(Base, Offset, StringRef(), Size, Linkage::Strong,
359 Scope::Local, IsLive, IsCallable);
363 static Symbol &constructNamedDef(void *SymStorage, Block &Base,
364 JITTargetAddress Offset, StringRef Name,
365 JITTargetAddress Size, Linkage L, Scope S,
366 bool IsLive, bool IsCallable) {
367 assert(SymStorage && "Storage cannot be null");
368 assert((Offset + Size) <= Base.getSize() &&
369 "Symbol extends past end of block");
370 assert(!Name.empty() && "Name cannot be empty");
371 auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
372 new (Sym) Symbol(Base, Offset, Name, Size, L, S, IsLive, IsCallable);
377 /// Create a null Symbol. This allows Symbols to be default initialized for
378 /// use in containers (e.g. as map values). Null symbols are only useful for
382 // Symbols are not movable or copyable.
383 Symbol(const Symbol &) = delete;
384 Symbol &operator=(const Symbol &) = delete;
385 Symbol(Symbol &&) = delete;
386 Symbol &operator=(Symbol &&) = delete;
388 /// Returns true if this symbol has a name.
389 bool hasName() const { return !Name.empty(); }
391 /// Returns the name of this symbol (empty if the symbol is anonymous).
392 StringRef getName() const {
393 assert((!Name.empty() || getScope() == Scope::Local) &&
394 "Anonymous symbol has non-local scope");
398 /// Returns true if this Symbol has content (potentially) defined within this
399 /// object file (i.e. is anything but an external or absolute symbol).
400 bool isDefined() const {
401 assert(Base && "Attempt to access null symbol");
402 return Base->isDefined();
405 /// Returns true if this symbol is live (i.e. should be treated as a root for
407 bool isLive() const {
408 assert(Base && "Attempting to access null symbol");
412 /// Set this symbol's live bit.
413 void setLive(bool IsLive) { this->IsLive = IsLive; }
415 /// Returns true is this symbol is callable.
416 bool isCallable() const { return IsCallable; }
418 /// Set this symbol's callable bit.
419 void setCallable(bool IsCallable) { this->IsCallable = IsCallable; }
421 /// Returns true if the underlying addressable is an unresolved external.
422 bool isExternal() const {
423 assert(Base && "Attempt to access null symbol");
424 return !Base->isDefined() && !Base->isAbsolute();
427 /// Returns true if the underlying addressable is an absolute symbol.
428 bool isAbsolute() const {
429 assert(Base && "Attempt to access null symbol");
430 return !Base->isDefined() && Base->isAbsolute();
433 /// Return the addressable that this symbol points to.
434 Addressable &getAddressable() {
435 assert(Base && "Cannot get underlying addressable for null symbol");
439 /// Return the addressable that thsi symbol points to.
440 const Addressable &getAddressable() const {
441 assert(Base && "Cannot get underlying addressable for null symbol");
445 /// Return the Block for this Symbol (Symbol must be defined).
447 assert(Base && "Cannot get block for null symbol");
448 assert(Base->isDefined() && "Not a defined symbol");
449 return static_cast<Block &>(*Base);
452 /// Return the Block for this Symbol (Symbol must be defined).
453 const Block &getBlock() const {
454 assert(Base && "Cannot get block for null symbol");
455 assert(Base->isDefined() && "Not a defined symbol");
456 return static_cast<const Block &>(*Base);
459 /// Returns the offset for this symbol within the underlying addressable.
460 JITTargetAddress getOffset() const { return Offset; }
462 /// Returns the address of this symbol.
463 JITTargetAddress getAddress() const { return Base->getAddress() + Offset; }
465 /// Returns the size of this symbol.
466 JITTargetAddress getSize() const { return Size; }
468 /// Returns true if this symbol is backed by a zero-fill block.
469 /// This method may only be called on defined symbols.
470 bool isSymbolZeroFill() const { return getBlock().isZeroFill(); }
472 /// Returns the content in the underlying block covered by this symbol.
473 /// This method may only be called on defined non-zero-fill symbols.
474 StringRef getSymbolContent() const {
475 return getBlock().getContent().substr(Offset, Size);
478 /// Get the linkage for this Symbol.
479 Linkage getLinkage() const { return static_cast<Linkage>(L); }
481 /// Set the linkage for this Symbol.
482 void setLinkage(Linkage L) {
483 assert((L == Linkage::Strong || (!Base->isAbsolute() && !Name.empty())) &&
484 "Linkage can only be applied to defined named symbols");
485 this->L = static_cast<uint8_t>(L);
488 /// Get the visibility for this Symbol.
489 Scope getScope() const { return static_cast<Scope>(S); }
491 /// Set the visibility for this Symbol.
492 void setScope(Scope S) {
493 assert((!Name.empty() || S == Scope::Local) &&
494 "Can not set anonymous symbol to non-local scope");
495 assert((S == Scope::Default || Base->isDefined() || Base->isAbsolute()) &&
496 "Invalid visibility for symbol type");
497 this->S = static_cast<uint8_t>(S);
501 void makeExternal(Addressable &A) {
502 assert(!A.isDefined() && "Attempting to make external with defined block");
505 setLinkage(Linkage::Strong);
506 setScope(Scope::Default);
508 // note: Size and IsCallable fields left unchanged.
511 void setBlock(Block &B) { Base = &B; }
513 void setOffset(uint64_t NewOffset) {
514 assert(NewOffset <= MaxOffset && "Offset out of range");
518 static constexpr uint64_t MaxOffset = (1ULL << 59) - 1;
520 // FIXME: A char* or SymbolStringPtr may pack better.
522 Addressable *Base = nullptr;
523 uint64_t Offset : 59;
527 uint64_t IsCallable : 1;
528 JITTargetAddress Size = 0;
531 raw_ostream &operator<<(raw_ostream &OS, const Symbol &A);
533 void printEdge(raw_ostream &OS, const Block &B, const Edge &E,
534 StringRef EdgeKindName);
536 /// Represents an object file section.
538 friend class LinkGraph;
541 Section(StringRef Name, sys::Memory::ProtectionFlags Prot,
542 SectionOrdinal SecOrdinal)
543 : Name(Name), Prot(Prot), SecOrdinal(SecOrdinal) {}
545 using SymbolSet = DenseSet<Symbol *>;
546 using BlockSet = DenseSet<Block *>;
549 using symbol_iterator = SymbolSet::iterator;
550 using const_symbol_iterator = SymbolSet::const_iterator;
552 using block_iterator = BlockSet::iterator;
553 using const_block_iterator = BlockSet::const_iterator;
557 /// Returns the name of this section.
558 StringRef getName() const { return Name; }
560 /// Returns the protection flags for this section.
561 sys::Memory::ProtectionFlags getProtectionFlags() const { return Prot; }
563 /// Returns the ordinal for this section.
564 SectionOrdinal getOrdinal() const { return SecOrdinal; }
566 /// Returns an iterator over the blocks defined in this section.
567 iterator_range<block_iterator> blocks() {
568 return make_range(Blocks.begin(), Blocks.end());
571 /// Returns an iterator over the blocks defined in this section.
572 iterator_range<const_block_iterator> blocks() const {
573 return make_range(Blocks.begin(), Blocks.end());
576 /// Returns an iterator over the symbols defined in this section.
577 iterator_range<symbol_iterator> symbols() {
578 return make_range(Symbols.begin(), Symbols.end());
581 /// Returns an iterator over the symbols defined in this section.
582 iterator_range<const_symbol_iterator> symbols() const {
583 return make_range(Symbols.begin(), Symbols.end());
586 /// Return the number of symbols in this section.
587 SymbolSet::size_type symbols_size() { return Symbols.size(); }
590 void addSymbol(Symbol &Sym) {
591 assert(!Symbols.count(&Sym) && "Symbol is already in this section");
592 Symbols.insert(&Sym);
595 void removeSymbol(Symbol &Sym) {
596 assert(Symbols.count(&Sym) && "symbol is not in this section");
600 void addBlock(Block &B) {
601 assert(!Blocks.count(&B) && "Block is already in this section");
605 void removeBlock(Block &B) {
606 assert(Blocks.count(&B) && "Block is not in this section");
611 sys::Memory::ProtectionFlags Prot;
612 SectionOrdinal SecOrdinal = 0;
617 /// Represents a section address range via a pair of Block pointers
618 /// to the first and last Blocks in the section.
621 SectionRange() = default;
622 SectionRange(const Section &Sec) {
623 if (llvm::empty(Sec.blocks()))
625 First = Last = *Sec.blocks().begin();
626 for (auto *B : Sec.blocks()) {
627 if (B->getAddress() < First->getAddress())
629 if (B->getAddress() > Last->getAddress())
633 Block *getFirstBlock() const {
634 assert((!Last || First) && "First can not be null if end is non-null");
637 Block *getLastBlock() const {
638 assert((First || !Last) && "Last can not be null if start is non-null");
641 bool isEmpty() const {
642 assert((First || !Last) && "Last can not be null if start is non-null");
645 JITTargetAddress getStart() const {
646 return First ? First->getAddress() : 0;
648 JITTargetAddress getEnd() const {
649 return Last ? Last->getAddress() + Last->getSize() : 0;
651 uint64_t getSize() const { return getEnd() - getStart(); }
654 Block *First = nullptr;
655 Block *Last = nullptr;
660 using SectionList = std::vector<std::unique_ptr<Section>>;
661 using ExternalSymbolSet = DenseSet<Symbol *>;
662 using BlockSet = DenseSet<Block *>;
664 template <typename... ArgTs>
665 Addressable &createAddressable(ArgTs &&... Args) {
667 reinterpret_cast<Addressable *>(Allocator.Allocate<Addressable>());
668 new (A) Addressable(std::forward<ArgTs>(Args)...);
672 void destroyAddressable(Addressable &A) {
674 Allocator.Deallocate(&A);
677 template <typename... ArgTs> Block &createBlock(ArgTs &&... Args) {
678 Block *B = reinterpret_cast<Block *>(Allocator.Allocate<Block>());
679 new (B) Block(std::forward<ArgTs>(Args)...);
680 B->getSection().addBlock(*B);
684 void destroyBlock(Block &B) {
686 Allocator.Deallocate(&B);
689 void destroySymbol(Symbol &S) {
691 Allocator.Deallocate(&S);
694 static iterator_range<Section::block_iterator> getSectionBlocks(Section &S) {
698 static iterator_range<Section::const_block_iterator>
699 getSectionConstBlocks(Section &S) {
703 static iterator_range<Section::symbol_iterator>
704 getSectionSymbols(Section &S) {
708 static iterator_range<Section::const_symbol_iterator>
709 getSectionConstSymbols(Section &S) {
714 using external_symbol_iterator = ExternalSymbolSet::iterator;
716 using section_iterator = pointee_iterator<SectionList::iterator>;
717 using const_section_iterator = pointee_iterator<SectionList::const_iterator>;
719 template <typename OuterItrT, typename InnerItrT, typename T,
720 iterator_range<InnerItrT> getInnerRange(
721 typename OuterItrT::reference)>
722 class nested_collection_iterator
723 : public iterator_facade_base<
724 nested_collection_iterator<OuterItrT, InnerItrT, T, getInnerRange>,
725 std::forward_iterator_tag, T> {
727 nested_collection_iterator() = default;
729 nested_collection_iterator(OuterItrT OuterI, OuterItrT OuterE)
730 : OuterI(OuterI), OuterE(OuterE),
731 InnerI(getInnerBegin(OuterI, OuterE)) {
732 moveToNonEmptyInnerOrEnd();
735 bool operator==(const nested_collection_iterator &RHS) const {
736 return (OuterI == RHS.OuterI) && (InnerI == RHS.InnerI);
739 T operator*() const {
740 assert(InnerI != getInnerRange(*OuterI).end() && "Dereferencing end?");
744 nested_collection_iterator operator++() {
746 moveToNonEmptyInnerOrEnd();
751 static InnerItrT getInnerBegin(OuterItrT OuterI, OuterItrT OuterE) {
752 return OuterI != OuterE ? getInnerRange(*OuterI).begin() : InnerItrT();
755 void moveToNonEmptyInnerOrEnd() {
756 while (OuterI != OuterE && InnerI == getInnerRange(*OuterI).end()) {
758 InnerI = getInnerBegin(OuterI, OuterE);
762 OuterItrT OuterI, OuterE;
766 using defined_symbol_iterator =
767 nested_collection_iterator<const_section_iterator,
768 Section::symbol_iterator, Symbol *,
771 using const_defined_symbol_iterator =
772 nested_collection_iterator<const_section_iterator,
773 Section::const_symbol_iterator, const Symbol *,
774 getSectionConstSymbols>;
776 using block_iterator = nested_collection_iterator<const_section_iterator,
777 Section::block_iterator,
778 Block *, getSectionBlocks>;
780 using const_block_iterator =
781 nested_collection_iterator<const_section_iterator,
782 Section::const_block_iterator, const Block *,
783 getSectionConstBlocks>;
785 LinkGraph(std::string Name, unsigned PointerSize,
786 support::endianness Endianness)
787 : Name(std::move(Name)), PointerSize(PointerSize),
788 Endianness(Endianness) {}
790 /// Returns the name of this graph (usually the name of the original
791 /// underlying MemoryBuffer).
792 const std::string &getName() { return Name; }
794 /// Returns the pointer size for use in this graph.
795 unsigned getPointerSize() const { return PointerSize; }
797 /// Returns the endianness of content in this graph.
798 support::endianness getEndianness() const { return Endianness; }
800 /// Create a section with the given name, protection flags, and alignment.
801 Section &createSection(StringRef Name, sys::Memory::ProtectionFlags Prot) {
802 std::unique_ptr<Section> Sec(new Section(Name, Prot, Sections.size()));
803 Sections.push_back(std::move(Sec));
804 return *Sections.back();
807 /// Create a content block.
808 Block &createContentBlock(Section &Parent, StringRef Content,
809 uint64_t Address, uint64_t Alignment,
810 uint64_t AlignmentOffset) {
811 return createBlock(Parent, Content, Address, Alignment, AlignmentOffset);
814 /// Create a zero-fill block.
815 Block &createZeroFillBlock(Section &Parent, uint64_t Size, uint64_t Address,
816 uint64_t Alignment, uint64_t AlignmentOffset) {
817 return createBlock(Parent, Size, Address, Alignment, AlignmentOffset);
820 /// Cache type for the splitBlock function.
821 using SplitBlockCache = Optional<SmallVector<Symbol *, 8>>;
823 /// Splits block B at the given index which must be greater than zero.
824 /// If SplitIndex == B.getSize() then this function is a no-op and returns B.
825 /// If SplitIndex < B.getSize() then this function returns a new block
826 /// covering the range [ 0, SplitIndex ), and B is modified to cover the range
827 /// [ SplitIndex, B.size() ).
829 /// The optional Cache parameter can be used to speed up repeated calls to
830 /// splitBlock for a single block. If the value is None the cache will be
831 /// treated as uninitialized and splitBlock will populate it. Otherwise it
832 /// is assumed to contain the list of Symbols pointing at B, sorted in
833 /// descending order of offset.
837 /// 1. The newly introduced block will have a new ordinal which will be
838 /// higher than any other ordinals in the section. Clients are responsible
839 /// for re-assigning block ordinals to restore a compatible order if
842 /// 2. The cache is not automatically updated if new symbols are introduced
843 /// between calls to splitBlock. Any newly introduced symbols may be
844 /// added to the cache manually (descending offset order must be
845 /// preserved), or the cache can be set to None and rebuilt by
846 /// splitBlock on the next call.
847 Block &splitBlock(Block &B, size_t SplitIndex,
848 SplitBlockCache *Cache = nullptr);
850 /// Add an external symbol.
851 /// Some formats (e.g. ELF) allow Symbols to have sizes. For Symbols whose
852 /// size is not known, you should substitute '0'.
853 /// For external symbols Linkage determines whether the symbol must be
854 /// present during lookup: Externals with strong linkage must be found or
855 /// an error will be emitted. Externals with weak linkage are permitted to
856 /// be undefined, in which case they are assigned a value of 0.
857 Symbol &addExternalSymbol(StringRef Name, uint64_t Size, Linkage L) {
859 Symbol::constructExternal(Allocator.Allocate<Symbol>(),
860 createAddressable(0, false), Name, Size, L);
861 ExternalSymbols.insert(&Sym);
865 /// Add an absolute symbol.
866 Symbol &addAbsoluteSymbol(StringRef Name, JITTargetAddress Address,
867 uint64_t Size, Linkage L, Scope S, bool IsLive) {
868 auto &Sym = Symbol::constructAbsolute(Allocator.Allocate<Symbol>(),
869 createAddressable(Address), Name,
871 AbsoluteSymbols.insert(&Sym);
875 /// Convenience method for adding a weak zero-fill symbol.
876 Symbol &addCommonSymbol(StringRef Name, Scope S, Section &Section,
877 JITTargetAddress Address, uint64_t Size,
878 uint64_t Alignment, bool IsLive) {
879 auto &Sym = Symbol::constructCommon(
880 Allocator.Allocate<Symbol>(),
881 createBlock(Section, Size, Address, Alignment, 0), Name, Size, S,
883 Section.addSymbol(Sym);
887 /// Add an anonymous symbol.
888 Symbol &addAnonymousSymbol(Block &Content, JITTargetAddress Offset,
889 JITTargetAddress Size, bool IsCallable,
891 auto &Sym = Symbol::constructAnonDef(Allocator.Allocate<Symbol>(), Content,
892 Offset, Size, IsCallable, IsLive);
893 Content.getSection().addSymbol(Sym);
897 /// Add a named symbol.
898 Symbol &addDefinedSymbol(Block &Content, JITTargetAddress Offset,
899 StringRef Name, JITTargetAddress Size, Linkage L,
900 Scope S, bool IsCallable, bool IsLive) {
902 Symbol::constructNamedDef(Allocator.Allocate<Symbol>(), Content, Offset,
903 Name, Size, L, S, IsLive, IsCallable);
904 Content.getSection().addSymbol(Sym);
908 iterator_range<section_iterator> sections() {
909 return make_range(section_iterator(Sections.begin()),
910 section_iterator(Sections.end()));
913 /// Returns the section with the given name if it exists, otherwise returns
915 Section *findSectionByName(StringRef Name) {
916 for (auto &S : sections())
917 if (S.getName() == Name)
922 iterator_range<block_iterator> blocks() {
923 return make_range(block_iterator(Sections.begin(), Sections.end()),
924 block_iterator(Sections.end(), Sections.end()));
927 iterator_range<const_block_iterator> blocks() const {
928 return make_range(const_block_iterator(Sections.begin(), Sections.end()),
929 const_block_iterator(Sections.end(), Sections.end()));
932 iterator_range<external_symbol_iterator> external_symbols() {
933 return make_range(ExternalSymbols.begin(), ExternalSymbols.end());
936 iterator_range<external_symbol_iterator> absolute_symbols() {
937 return make_range(AbsoluteSymbols.begin(), AbsoluteSymbols.end());
940 iterator_range<defined_symbol_iterator> defined_symbols() {
941 return make_range(defined_symbol_iterator(Sections.begin(), Sections.end()),
942 defined_symbol_iterator(Sections.end(), Sections.end()));
945 iterator_range<const_defined_symbol_iterator> defined_symbols() const {
947 const_defined_symbol_iterator(Sections.begin(), Sections.end()),
948 const_defined_symbol_iterator(Sections.end(), Sections.end()));
951 /// Turn a defined symbol into an external one.
952 void makeExternal(Symbol &Sym) {
953 if (Sym.getAddressable().isAbsolute()) {
954 assert(AbsoluteSymbols.count(&Sym) &&
955 "Sym is not in the absolute symbols set");
956 AbsoluteSymbols.erase(&Sym);
958 assert(Sym.isDefined() && "Sym is not a defined symbol");
959 Section &Sec = Sym.getBlock().getSection();
960 Sec.removeSymbol(Sym);
962 Sym.makeExternal(createAddressable(false));
963 ExternalSymbols.insert(&Sym);
966 /// Removes an external symbol. Also removes the underlying Addressable.
967 void removeExternalSymbol(Symbol &Sym) {
968 assert(!Sym.isDefined() && !Sym.isAbsolute() &&
969 "Sym is not an external symbol");
970 assert(ExternalSymbols.count(&Sym) && "Symbol is not in the externals set");
971 ExternalSymbols.erase(&Sym);
972 Addressable &Base = *Sym.Base;
974 destroyAddressable(Base);
977 /// Remove an absolute symbol. Also removes the underlying Addressable.
978 void removeAbsoluteSymbol(Symbol &Sym) {
979 assert(!Sym.isDefined() && Sym.isAbsolute() &&
980 "Sym is not an absolute symbol");
981 assert(AbsoluteSymbols.count(&Sym) &&
982 "Symbol is not in the absolute symbols set");
983 AbsoluteSymbols.erase(&Sym);
984 Addressable &Base = *Sym.Base;
986 destroyAddressable(Base);
989 /// Removes defined symbols. Does not remove the underlying block.
990 void removeDefinedSymbol(Symbol &Sym) {
991 assert(Sym.isDefined() && "Sym is not a defined symbol");
992 Sym.getBlock().getSection().removeSymbol(Sym);
997 void removeBlock(Block &B) {
998 assert(llvm::none_of(B.getSection().symbols(),
999 [&](const Symbol *Sym) {
1000 return &Sym->getBlock() == &B;
1002 "Block still has symbols attached");
1003 B.getSection().removeBlock(B);
1009 /// If supplied, the EdgeKindToName function will be used to name edge
1010 /// kinds in the debug output. Otherwise raw edge kind numbers will be
1012 void dump(raw_ostream &OS,
1013 std::function<StringRef(Edge::Kind)> EdegKindToName =
1014 std::function<StringRef(Edge::Kind)>());
1017 // Put the BumpPtrAllocator first so that we don't free any of the underlying
1018 // memory until the Symbol/Addressable destructors have been run.
1019 BumpPtrAllocator Allocator;
1022 unsigned PointerSize;
1023 support::endianness Endianness;
1024 SectionList Sections;
1025 ExternalSymbolSet ExternalSymbols;
1026 ExternalSymbolSet AbsoluteSymbols;
1029 /// Enables easy lookup of blocks by addresses.
1030 class BlockAddressMap {
1032 using AddrToBlockMap = std::map<JITTargetAddress, Block *>;
1033 using const_iterator = AddrToBlockMap::const_iterator;
1035 /// A block predicate that always adds all blocks.
1036 static bool includeAllBlocks(const Block &B) { return true; }
1038 /// A block predicate that always includes blocks with non-null addresses.
1039 static bool includeNonNull(const Block &B) { return B.getAddress(); }
1041 BlockAddressMap() = default;
1043 /// Add a block to the map. Returns an error if the block overlaps with any
1045 template <typename PredFn = decltype(includeAllBlocks)>
1046 Error addBlock(Block &B, PredFn Pred = includeAllBlocks) {
1048 return Error::success();
1050 auto I = AddrToBlock.upper_bound(B.getAddress());
1052 // If we're not at the end of the map, check for overlap with the next
1054 if (I != AddrToBlock.end()) {
1055 if (B.getAddress() + B.getSize() > I->second->getAddress())
1056 return overlapError(B, *I->second);
1059 // If we're not at the start of the map, check for overlap with the previous
1061 if (I != AddrToBlock.begin()) {
1062 auto &PrevBlock = *std::prev(I)->second;
1063 if (PrevBlock.getAddress() + PrevBlock.getSize() > B.getAddress())
1064 return overlapError(B, PrevBlock);
1067 AddrToBlock.insert(I, std::make_pair(B.getAddress(), &B));
1068 return Error::success();
1071 /// Add a block to the map without checking for overlap with existing blocks.
1072 /// The client is responsible for ensuring that the block added does not
1073 /// overlap with any existing block.
1074 void addBlockWithoutChecking(Block &B) { AddrToBlock[B.getAddress()] = &B; }
1076 /// Add a range of blocks to the map. Returns an error if any block in the
1077 /// range overlaps with any other block in the range, or with any existing
1078 /// block in the map.
1079 template <typename BlockPtrRange,
1080 typename PredFn = decltype(includeAllBlocks)>
1081 Error addBlocks(BlockPtrRange &&Blocks, PredFn Pred = includeAllBlocks) {
1082 for (auto *B : Blocks)
1083 if (auto Err = addBlock(*B, Pred))
1085 return Error::success();
1088 /// Add a range of blocks to the map without checking for overlap with
1089 /// existing blocks. The client is responsible for ensuring that the block
1090 /// added does not overlap with any existing block.
1091 template <typename BlockPtrRange>
1092 void addBlocksWithoutChecking(BlockPtrRange &&Blocks) {
1093 for (auto *B : Blocks)
1094 addBlockWithoutChecking(*B);
1097 /// Iterates over (Address, Block*) pairs in ascending order of address.
1098 const_iterator begin() const { return AddrToBlock.begin(); }
1099 const_iterator end() const { return AddrToBlock.end(); }
1101 /// Returns the block starting at the given address, or nullptr if no such
1103 Block *getBlockAt(JITTargetAddress Addr) const {
1104 auto I = AddrToBlock.find(Addr);
1105 if (I == AddrToBlock.end())
1110 /// Returns the block covering the given address, or nullptr if no such block
1112 Block *getBlockCovering(JITTargetAddress Addr) const {
1113 auto I = AddrToBlock.upper_bound(Addr);
1114 if (I == AddrToBlock.begin())
1116 auto *B = std::prev(I)->second;
1117 if (Addr < B->getAddress() + B->getSize())
1123 Error overlapError(Block &NewBlock, Block &ExistingBlock) {
1124 auto NewBlockEnd = NewBlock.getAddress() + NewBlock.getSize();
1125 auto ExistingBlockEnd =
1126 ExistingBlock.getAddress() + ExistingBlock.getSize();
1127 return make_error<JITLinkError>(
1129 formatv("{0:x16} -- {1:x16}", NewBlock.getAddress(), NewBlockEnd) +
1131 formatv("{0:x16} -- {1:x16}", ExistingBlock.getAddress(),
1135 AddrToBlockMap AddrToBlock;
1138 /// A map of addresses to Symbols.
1139 class SymbolAddressMap {
1141 using SymbolVector = SmallVector<Symbol *, 1>;
1143 /// Add a symbol to the SymbolAddressMap.
1144 void addSymbol(Symbol &Sym) {
1145 AddrToSymbols[Sym.getAddress()].push_back(&Sym);
1148 /// Add all symbols in a given range to the SymbolAddressMap.
1149 template <typename SymbolPtrCollection>
1150 void addSymbols(SymbolPtrCollection &&Symbols) {
1151 for (auto *Sym : Symbols)
1155 /// Returns the list of symbols that start at the given address, or nullptr if
1156 /// no such symbols exist.
1157 const SymbolVector *getSymbolsAt(JITTargetAddress Addr) const {
1158 auto I = AddrToSymbols.find(Addr);
1159 if (I == AddrToSymbols.end())
1165 std::map<JITTargetAddress, SymbolVector> AddrToSymbols;
1168 /// A function for mutating LinkGraphs.
1169 using LinkGraphPassFunction = std::function<Error(LinkGraph &)>;
1171 /// A list of LinkGraph passes.
1172 using LinkGraphPassList = std::vector<LinkGraphPassFunction>;
1174 /// An LinkGraph pass configuration, consisting of a list of pre-prune,
1175 /// post-prune, and post-fixup passes.
1176 struct PassConfiguration {
1178 /// Pre-prune passes.
1180 /// These passes are called on the graph after it is built, and before any
1181 /// symbols have been pruned. Graph nodes still have their original vmaddrs.
1183 /// Notable use cases: Marking symbols live or should-discard.
1184 LinkGraphPassList PrePrunePasses;
1186 /// Post-prune passes.
1188 /// These passes are called on the graph after dead stripping, but before
1189 /// memory is allocated or nodes assigned their final addresses.
1191 /// Notable use cases: Building GOT, stub, and TLV symbols.
1192 LinkGraphPassList PostPrunePasses;
1194 /// Pre-fixup passes.
1196 /// These passes are called on the graph after memory has been allocated,
1197 /// content copied into working memory, and nodes have been assigned their
1198 /// final addresses.
1200 /// Notable use cases: Late link-time optimizations like GOT and stub
1202 LinkGraphPassList PostAllocationPasses;
1204 /// Post-fixup passes.
1206 /// These passes are called on the graph after block contents has been copied
1207 /// to working memory, and fixups applied. Graph nodes have been updated to
1208 /// their final target vmaddrs.
1210 /// Notable use cases: Testing and validation.
1211 LinkGraphPassList PostFixupPasses;
1214 /// Flags for symbol lookup.
1216 /// FIXME: These basically duplicate orc::SymbolLookupFlags -- We should merge
1217 /// the two types once we have an OrcSupport library.
1218 enum class SymbolLookupFlags { RequiredSymbol, WeaklyReferencedSymbol };
1220 raw_ostream &operator<<(raw_ostream &OS, const SymbolLookupFlags &LF);
1222 /// A map of symbol names to resolved addresses.
1223 using AsyncLookupResult = DenseMap<StringRef, JITEvaluatedSymbol>;
1225 /// A function object to call with a resolved symbol map (See AsyncLookupResult)
1226 /// or an error if resolution failed.
1227 class JITLinkAsyncLookupContinuation {
1229 virtual ~JITLinkAsyncLookupContinuation() {}
1230 virtual void run(Expected<AsyncLookupResult> LR) = 0;
1233 virtual void anchor();
1236 /// Create a lookup continuation from a function object.
1237 template <typename Continuation>
1238 std::unique_ptr<JITLinkAsyncLookupContinuation>
1239 createLookupContinuation(Continuation Cont) {
1241 class Impl final : public JITLinkAsyncLookupContinuation {
1243 Impl(Continuation C) : C(std::move(C)) {}
1244 void run(Expected<AsyncLookupResult> LR) override { C(std::move(LR)); }
1250 return std::make_unique<Impl>(std::move(Cont));
1253 /// Holds context for a single jitLink invocation.
1254 class JITLinkContext {
1256 using LookupMap = DenseMap<StringRef, SymbolLookupFlags>;
1258 /// Destroy a JITLinkContext.
1259 virtual ~JITLinkContext();
1261 /// Return the MemoryManager to be used for this link.
1262 virtual JITLinkMemoryManager &getMemoryManager() = 0;
1264 /// Returns a StringRef for the object buffer.
1265 /// This method can not be called once takeObjectBuffer has been called.
1266 virtual MemoryBufferRef getObjectBuffer() const = 0;
1268 /// Notify this context that linking failed.
1269 /// Called by JITLink if linking cannot be completed.
1270 virtual void notifyFailed(Error Err) = 0;
1272 /// Called by JITLink to resolve external symbols. This method is passed a
1273 /// lookup continutation which it must call with a result to continue the
1274 /// linking process.
1275 virtual void lookup(const LookupMap &Symbols,
1276 std::unique_ptr<JITLinkAsyncLookupContinuation> LC) = 0;
1278 /// Called by JITLink once all defined symbols in the graph have been assigned
1279 /// their final memory locations in the target process. At this point the
1280 /// LinkGraph can be inspected to build a symbol table, however the block
1281 /// content will not generally have been copied to the target location yet.
1282 virtual void notifyResolved(LinkGraph &G) = 0;
1284 /// Called by JITLink to notify the context that the object has been
1285 /// finalized (i.e. emitted to memory and memory permissions set). If all of
1286 /// this objects dependencies have also been finalized then the code is ready
1289 notifyFinalized(std::unique_ptr<JITLinkMemoryManager::Allocation> A) = 0;
1291 /// Called by JITLink prior to linking to determine whether default passes for
1292 /// the target should be added. The default implementation returns true.
1293 /// If subclasses override this method to return false for any target then
1294 /// they are required to fully configure the pass pipeline for that target.
1295 virtual bool shouldAddDefaultTargetPasses(const Triple &TT) const;
1297 /// Returns the mark-live pass to be used for this link. If no pass is
1298 /// returned (the default) then the target-specific linker implementation will
1299 /// choose a conservative default (usually marking all symbols live).
1300 /// This function is only called if shouldAddDefaultTargetPasses returns true,
1301 /// otherwise the JITContext is responsible for adding a mark-live pass in
1302 /// modifyPassConfig.
1303 virtual LinkGraphPassFunction getMarkLivePass(const Triple &TT) const;
1305 /// Called by JITLink to modify the pass pipeline prior to linking.
1306 /// The default version performs no modification.
1307 virtual Error modifyPassConfig(const Triple &TT, PassConfiguration &Config);
1310 /// Marks all symbols in a graph live. This can be used as a default,
1311 /// conservative mark-live implementation.
1312 Error markAllSymbolsLive(LinkGraph &G);
1314 /// Basic JITLink implementation.
1316 /// This function will use sensible defaults for GOT and Stub handling.
1317 void jitLink(std::unique_ptr<JITLinkContext> Ctx);
1319 } // end namespace jitlink
1320 } // end namespace llvm
1322 #endif // LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H