LLVM 17.0.0git
JITLink.h
Go to the documentation of this file.
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 "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/ADT/STLExtras.h"
25#include "llvm/Support/Endian.h"
26#include "llvm/Support/Error.h"
31#include <optional>
32
33#include <map>
34#include <string>
35#include <system_error>
36
37namespace llvm {
38namespace jitlink {
39
40class LinkGraph;
41class Symbol;
42class Section;
43
44/// Base class for errors originating in JIT linker, e.g. missing relocation
45/// support.
46class JITLinkError : public ErrorInfo<JITLinkError> {
47public:
48 static char ID;
49
50 JITLinkError(Twine ErrMsg) : ErrMsg(ErrMsg.str()) {}
51
52 void log(raw_ostream &OS) const override;
53 const std::string &getErrorMessage() const { return ErrMsg; }
54 std::error_code convertToErrorCode() const override;
55
56private:
57 std::string ErrMsg;
58};
59
60/// Represents fixups and constraints in the LinkGraph.
61class Edge {
62public:
63 using Kind = uint8_t;
64
66 Invalid, // Invalid edge value.
67 FirstKeepAlive, // Keeps target alive. Offset/addend zero.
68 KeepAlive = FirstKeepAlive, // Tag first edge kind that preserves liveness.
69 FirstRelocation // First architecture specific relocation.
70 };
71
73 using AddendT = int64_t;
74
75 Edge(Kind K, OffsetT Offset, Symbol &Target, AddendT Addend)
76 : Target(&Target), Offset(Offset), Addend(Addend), K(K) {}
77
78 OffsetT getOffset() const { return Offset; }
79 void setOffset(OffsetT Offset) { this->Offset = Offset; }
80 Kind getKind() const { return K; }
81 void setKind(Kind K) { this->K = K; }
82 bool isRelocation() const { return K >= FirstRelocation; }
84 assert(isRelocation() && "Not a relocation edge");
85 return K - FirstRelocation;
86 }
87 bool isKeepAlive() const { return K >= FirstKeepAlive; }
88 Symbol &getTarget() const { return *Target; }
89 void setTarget(Symbol &Target) { this->Target = &Target; }
90 AddendT getAddend() const { return Addend; }
91 void setAddend(AddendT Addend) { this->Addend = Addend; }
92
93private:
94 Symbol *Target = nullptr;
95 OffsetT Offset = 0;
96 AddendT Addend = 0;
97 Kind K = 0;
98};
99
100/// Returns the string name of the given generic edge kind, or "unknown"
101/// otherwise. Useful for debugging.
103
104/// Base class for Addressable entities (externals, absolutes, blocks).
106 friend class LinkGraph;
107
108protected:
109 Addressable(orc::ExecutorAddr Address, bool IsDefined)
110 : Address(Address), IsDefined(IsDefined), IsAbsolute(false) {}
111
113 : Address(Address), IsDefined(false), IsAbsolute(true) {
114 assert(!(IsDefined && IsAbsolute) &&
115 "Block cannot be both defined and absolute");
116 }
117
118public:
119 Addressable(const Addressable &) = delete;
120 Addressable &operator=(const Addressable &) = default;
123
124 orc::ExecutorAddr getAddress() const { return Address; }
125 void setAddress(orc::ExecutorAddr Address) { this->Address = Address; }
126
127 /// Returns true if this is a defined addressable, in which case you
128 /// can downcast this to a Block.
129 bool isDefined() const { return static_cast<bool>(IsDefined); }
130 bool isAbsolute() const { return static_cast<bool>(IsAbsolute); }
131
132private:
133 void setAbsolute(bool IsAbsolute) {
134 assert(!IsDefined && "Cannot change the Absolute flag on a defined block");
135 this->IsAbsolute = IsAbsolute;
136 }
137
138 orc::ExecutorAddr Address;
139 uint64_t IsDefined : 1;
140 uint64_t IsAbsolute : 1;
141
142protected:
143 // bitfields for Block, allocated here to improve packing.
147};
148
150
151/// An Addressable with content and edges.
152class Block : public Addressable {
153 friend class LinkGraph;
154
155private:
156 /// Create a zero-fill defined addressable.
159 : Addressable(Address, true), Parent(&Parent), Size(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 ContentMutable = false;
166 P2Align = Alignment ? llvm::countr_zero(Alignment) : 0;
167 this->AlignmentOffset = AlignmentOffset;
168 }
169
170 /// Create a defined addressable for the given content.
171 /// The Content is assumed to be non-writable, and will be copied when
172 /// mutations are required.
175 : Addressable(Address, true), Parent(&Parent), Data(Content.data()),
176 Size(Content.size()) {
177 assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2");
178 assert(AlignmentOffset < Alignment &&
179 "Alignment offset cannot exceed alignment");
180 assert(AlignmentOffset <= MaxAlignmentOffset &&
181 "Alignment offset exceeds maximum");
182 ContentMutable = false;
183 P2Align = Alignment ? llvm::countr_zero(Alignment) : 0;
184 this->AlignmentOffset = AlignmentOffset;
185 }
186
187 /// Create a defined addressable for the given content.
188 /// The content is assumed to be writable, and the caller is responsible
189 /// for ensuring that it lives for the duration of the Block's lifetime.
190 /// The standard way to achieve this is to allocate it on the Graph's
191 /// allocator.
192 Block(Section &Parent, MutableArrayRef<char> Content,
194 : Addressable(Address, true), Parent(&Parent), Data(Content.data()),
195 Size(Content.size()) {
196 assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2");
197 assert(AlignmentOffset < Alignment &&
198 "Alignment offset cannot exceed alignment");
199 assert(AlignmentOffset <= MaxAlignmentOffset &&
200 "Alignment offset exceeds maximum");
201 ContentMutable = true;
202 P2Align = Alignment ? llvm::countr_zero(Alignment) : 0;
203 this->AlignmentOffset = AlignmentOffset;
204 }
205
206public:
207 using EdgeVector = std::vector<Edge>;
208 using edge_iterator = EdgeVector::iterator;
209 using const_edge_iterator = EdgeVector::const_iterator;
210
211 Block(const Block &) = delete;
212 Block &operator=(const Block &) = delete;
213 Block(Block &&) = delete;
214 Block &operator=(Block &&) = delete;
215
216 /// Return the parent section for this block.
217 Section &getSection() const { return *Parent; }
218
219 /// Returns true if this is a zero-fill block.
220 ///
221 /// If true, getSize is callable but getContent is not (the content is
222 /// defined to be a sequence of zero bytes of length Size).
223 bool isZeroFill() const { return !Data; }
224
225 /// Returns the size of this defined addressable.
226 size_t getSize() const { return Size; }
227
228 /// Returns the address range of this defined addressable.
231 }
232
233 /// Get the content for this block. Block must not be a zero-fill block.
235 assert(Data && "Block does not contain content");
236 return ArrayRef<char>(Data, Size);
237 }
238
239 /// Set the content for this block.
240 /// Caller is responsible for ensuring the underlying bytes are not
241 /// deallocated while pointed to by this block.
243 assert(Content.data() && "Setting null content");
244 Data = Content.data();
245 Size = Content.size();
246 ContentMutable = false;
247 }
248
249 /// Get mutable content for this block.
250 ///
251 /// If this Block's content is not already mutable this will trigger a copy
252 /// of the existing immutable content to a new, mutable buffer allocated using
253 /// LinkGraph::allocateContent.
255
256 /// Get mutable content for this block.
257 ///
258 /// This block's content must already be mutable. It is a programmatic error
259 /// to call this on a block with immutable content -- consider using
260 /// getMutableContent instead.
262 assert(Data && "Block does not contain content");
263 assert(ContentMutable && "Content is not mutable");
264 return MutableArrayRef<char>(const_cast<char *>(Data), Size);
265 }
266
267 /// Set mutable content for this block.
268 ///
269 /// The caller is responsible for ensuring that the memory pointed to by
270 /// MutableContent is not deallocated while pointed to by this block.
272 assert(MutableContent.data() && "Setting null content");
273 Data = MutableContent.data();
274 Size = MutableContent.size();
275 ContentMutable = true;
276 }
277
278 /// Returns true if this block's content is mutable.
279 ///
280 /// This is primarily useful for asserting that a block is already in a
281 /// mutable state prior to modifying the content. E.g. when applying
282 /// fixups we expect the block to already be mutable as it should have been
283 /// copied to working memory.
284 bool isContentMutable() const { return ContentMutable; }
285
286 /// Get the alignment for this content.
287 uint64_t getAlignment() const { return 1ull << P2Align; }
288
289 /// Set the alignment for this content.
290 void setAlignment(uint64_t Alignment) {
291 assert(isPowerOf2_64(Alignment) && "Alignment must be a power of two");
292 P2Align = Alignment ? llvm::countr_zero(Alignment) : 0;
293 }
294
295 /// Get the alignment offset for this content.
297
298 /// Set the alignment offset for this content.
300 assert(AlignmentOffset < (1ull << P2Align) &&
301 "Alignment offset can't exceed alignment");
302 this->AlignmentOffset = AlignmentOffset;
303 }
304
305 /// Add an edge to this block.
307 Edge::AddendT Addend) {
308 assert((K == Edge::KeepAlive || !isZeroFill()) &&
309 "Adding edge to zero-fill block?");
310 Edges.push_back(Edge(K, Offset, Target, Addend));
311 }
312
313 /// Add an edge by copying an existing one. This is typically used when
314 /// moving edges between blocks.
315 void addEdge(const Edge &E) { Edges.push_back(E); }
316
317 /// Return the list of edges attached to this content.
319 return make_range(Edges.begin(), Edges.end());
320 }
321
322 /// Returns the list of edges attached to this content.
324 return make_range(Edges.begin(), Edges.end());
325 }
326
327 /// Return the size of the edges list.
328 size_t edges_size() const { return Edges.size(); }
329
330 /// Returns true if the list of edges is empty.
331 bool edges_empty() const { return Edges.empty(); }
332
333 /// Remove the edge pointed to by the given iterator.
334 /// Returns an iterator to the new next element.
335 edge_iterator removeEdge(edge_iterator I) { return Edges.erase(I); }
336
337 /// Returns the address of the fixup for the given edge, which is equal to
338 /// this block's address plus the edge's offset.
340 return getAddress() + E.getOffset();
341 }
342
343private:
344 static constexpr uint64_t MaxAlignmentOffset = (1ULL << 56) - 1;
345
346 void setSection(Section &Parent) { this->Parent = &Parent; }
347
348 Section *Parent;
349 const char *Data = nullptr;
350 size_t Size = 0;
351 std::vector<Edge> Edges;
352};
353
354// Align an address to conform with block alignment requirements.
356 uint64_t Delta = (B.getAlignmentOffset() - Addr) % B.getAlignment();
357 return Addr + Delta;
358}
359
360// Align a orc::ExecutorAddr to conform with block alignment requirements.
362 return orc::ExecutorAddr(alignToBlock(Addr.getValue(), B));
363}
364
365// Returns true if the given blocks contains exactly one valid c-string.
366// Zero-fill blocks of size 1 count as valid empty strings. Content blocks
367// must end with a zero, and contain no zeros before the end.
368bool isCStringBlock(Block &B);
369
370/// Describes symbol linkage. This can be used to resolve definition clashes.
371enum class Linkage : uint8_t {
372 Strong,
373 Weak,
374};
375
376/// Holds target-specific properties for a symbol.
377using TargetFlagsType = uint8_t;
378
379/// For errors and debugging output.
380const char *getLinkageName(Linkage L);
381
382/// Defines the scope in which this symbol should be visible:
383/// Default -- Visible in the public interface of the linkage unit.
384/// Hidden -- Visible within the linkage unit, but not exported from it.
385/// Local -- Visible only within the LinkGraph.
386enum class Scope : uint8_t {
387 Default,
388 Hidden,
389 Local
390};
391
392/// For debugging output.
393const char *getScopeName(Scope S);
394
395raw_ostream &operator<<(raw_ostream &OS, const Block &B);
396
397/// Symbol representation.
398///
399/// Symbols represent locations within Addressable objects.
400/// They can be either Named or Anonymous.
401/// Anonymous symbols have neither linkage nor visibility, and must point at
402/// ContentBlocks.
403/// Named symbols may be in one of four states:
404/// - Null: Default initialized. Assignable, but otherwise unusable.
405/// - Defined: Has both linkage and visibility and points to a ContentBlock
406/// - Common: Has both linkage and visibility, points to a null Addressable.
407/// - External: Has neither linkage nor visibility, points to an external
408/// Addressable.
409///
410class Symbol {
411 friend class LinkGraph;
412
413private:
415 orc::ExecutorAddrDiff Size, Linkage L, Scope S, bool IsLive,
416 bool IsCallable)
417 : Name(Name), Base(&Base), Offset(Offset), WeakRef(0), Size(Size) {
418 assert(Offset <= MaxOffset && "Offset out of range");
419 setLinkage(L);
420 setScope(S);
421 setLive(IsLive);
422 setCallable(IsCallable);
424 }
425
426 static Symbol &constructExternal(BumpPtrAllocator &Allocator,
427 Addressable &Base, StringRef Name,
429 bool WeaklyReferenced) {
430 assert(!Base.isDefined() &&
431 "Cannot create external symbol from defined block");
432 assert(!Name.empty() && "External symbol name cannot be empty");
433 auto *Sym = Allocator.Allocate<Symbol>();
434 new (Sym) Symbol(Base, 0, Name, Size, L, Scope::Default, false, false);
435 Sym->setWeaklyReferenced(WeaklyReferenced);
436 return *Sym;
437 }
438
439 static Symbol &constructAbsolute(BumpPtrAllocator &Allocator,
440 Addressable &Base, StringRef Name,
442 Scope S, bool IsLive) {
443 assert(!Base.isDefined() &&
444 "Cannot create absolute symbol from a defined block");
445 auto *Sym = Allocator.Allocate<Symbol>();
446 new (Sym) Symbol(Base, 0, Name, Size, L, S, IsLive, false);
447 return *Sym;
448 }
449
450 static Symbol &constructAnonDef(BumpPtrAllocator &Allocator, Block &Base,
452 orc::ExecutorAddrDiff Size, bool IsCallable,
453 bool IsLive) {
454 assert((Offset + Size) <= Base.getSize() &&
455 "Symbol extends past end of block");
456 auto *Sym = Allocator.Allocate<Symbol>();
457 new (Sym) Symbol(Base, Offset, StringRef(), Size, Linkage::Strong,
458 Scope::Local, IsLive, IsCallable);
459 return *Sym;
460 }
461
462 static Symbol &constructNamedDef(BumpPtrAllocator &Allocator, Block &Base,
465 Scope S, bool IsLive, bool IsCallable) {
466 assert((Offset + Size) <= Base.getSize() &&
467 "Symbol extends past end of block");
468 assert(!Name.empty() && "Name cannot be empty");
469 auto *Sym = Allocator.Allocate<Symbol>();
470 new (Sym) Symbol(Base, Offset, Name, Size, L, S, IsLive, IsCallable);
471 return *Sym;
472 }
473
474public:
475 /// Create a null Symbol. This allows Symbols to be default initialized for
476 /// use in containers (e.g. as map values). Null symbols are only useful for
477 /// assigning to.
478 Symbol() = default;
479
480 // Symbols are not movable or copyable.
481 Symbol(const Symbol &) = delete;
482 Symbol &operator=(const Symbol &) = delete;
483 Symbol(Symbol &&) = delete;
484 Symbol &operator=(Symbol &&) = delete;
485
486 /// Returns true if this symbol has a name.
487 bool hasName() const { return !Name.empty(); }
488
489 /// Returns the name of this symbol (empty if the symbol is anonymous).
491 assert((!Name.empty() || getScope() == Scope::Local) &&
492 "Anonymous symbol has non-local scope");
493 return Name;
494 }
495
496 /// Rename this symbol. The client is responsible for updating scope and
497 /// linkage if this name-change requires it.
498 void setName(StringRef Name) { this->Name = Name; }
499
500 /// Returns true if this Symbol has content (potentially) defined within this
501 /// object file (i.e. is anything but an external or absolute symbol).
502 bool isDefined() const {
503 assert(Base && "Attempt to access null symbol");
504 return Base->isDefined();
505 }
506
507 /// Returns true if this symbol is live (i.e. should be treated as a root for
508 /// dead stripping).
509 bool isLive() const {
510 assert(Base && "Attempting to access null symbol");
511 return IsLive;
512 }
513
514 /// Set this symbol's live bit.
515 void setLive(bool IsLive) { this->IsLive = IsLive; }
516
517 /// Returns true is this symbol is callable.
518 bool isCallable() const { return IsCallable; }
519
520 /// Set this symbol's callable bit.
521 void setCallable(bool IsCallable) { this->IsCallable = IsCallable; }
522
523 /// Returns true if the underlying addressable is an unresolved external.
524 bool isExternal() const {
525 assert(Base && "Attempt to access null symbol");
526 return !Base->isDefined() && !Base->isAbsolute();
527 }
528
529 /// Returns true if the underlying addressable is an absolute symbol.
530 bool isAbsolute() const {
531 assert(Base && "Attempt to access null symbol");
532 return Base->isAbsolute();
533 }
534
535 /// Return the addressable that this symbol points to.
537 assert(Base && "Cannot get underlying addressable for null symbol");
538 return *Base;
539 }
540
541 /// Return the addressable that this symbol points to.
543 assert(Base && "Cannot get underlying addressable for null symbol");
544 return *Base;
545 }
546
547 /// Return the Block for this Symbol (Symbol must be defined).
549 assert(Base && "Cannot get block for null symbol");
550 assert(Base->isDefined() && "Not a defined symbol");
551 return static_cast<Block &>(*Base);
552 }
553
554 /// Return the Block for this Symbol (Symbol must be defined).
555 const Block &getBlock() const {
556 assert(Base && "Cannot get block for null symbol");
557 assert(Base->isDefined() && "Not a defined symbol");
558 return static_cast<const Block &>(*Base);
559 }
560
561 /// Returns the offset for this symbol within the underlying addressable.
563
564 /// Returns the address of this symbol.
565 orc::ExecutorAddr getAddress() const { return Base->getAddress() + Offset; }
566
567 /// Returns the size of this symbol.
569
570 /// Set the size of this symbol.
572 assert(Base && "Cannot set size for null Symbol");
573 assert((Size == 0 || Base->isDefined()) &&
574 "Non-zero size can only be set for defined symbols");
575 assert((Offset + Size <= static_cast<const Block &>(*Base).getSize()) &&
576 "Symbol size cannot extend past the end of its containing block");
577 this->Size = Size;
578 }
579
580 /// Returns the address range of this symbol.
583 }
584
585 /// Returns true if this symbol is backed by a zero-fill block.
586 /// This method may only be called on defined symbols.
587 bool isSymbolZeroFill() const { return getBlock().isZeroFill(); }
588
589 /// Returns the content in the underlying block covered by this symbol.
590 /// This method may only be called on defined non-zero-fill symbols.
592 return getBlock().getContent().slice(Offset, Size);
593 }
594
595 /// Get the linkage for this Symbol.
596 Linkage getLinkage() const { return static_cast<Linkage>(L); }
597
598 /// Set the linkage for this Symbol.
600 assert((L == Linkage::Strong || (!Base->isAbsolute() && !Name.empty())) &&
601 "Linkage can only be applied to defined named symbols");
602 this->L = static_cast<uint8_t>(L);
603 }
604
605 /// Get the visibility for this Symbol.
606 Scope getScope() const { return static_cast<Scope>(S); }
607
608 /// Set the visibility for this Symbol.
609 void setScope(Scope S) {
610 assert((!Name.empty() || S == Scope::Local) &&
611 "Can not set anonymous symbol to non-local scope");
612 assert((S != Scope::Local || Base->isDefined() || Base->isAbsolute()) &&
613 "Invalid visibility for symbol type");
614 this->S = static_cast<uint8_t>(S);
615 }
616
617 /// Check wehther the given target flags are set for this Symbol.
619 return static_cast<TargetFlagsType>(TargetFlags) & Flags;
620 }
621
622 /// Set the target flags for this Symbol.
624 assert(Flags <= 1 && "Add more bits to store more than single flag");
625 TargetFlags = Flags;
626 }
627
628 /// Returns true if this is a weakly referenced external symbol.
629 /// This method may only be called on external symbols.
630 bool isWeaklyReferenced() const {
631 assert(isExternal() && "isWeaklyReferenced called on non-external");
632 return WeakRef;
633 }
634
635 /// Set the WeaklyReferenced value for this symbol.
636 /// This method may only be called on external symbols.
637 void setWeaklyReferenced(bool WeakRef) {
638 assert(isExternal() && "setWeaklyReferenced called on non-external");
639 this->WeakRef = WeakRef;
640 }
641
642private:
643 void makeExternal(Addressable &A) {
644 assert(!A.isDefined() && !A.isAbsolute() &&
645 "Attempting to make external with defined or absolute block");
646 Base = &A;
647 Offset = 0;
649 IsLive = 0;
650 // note: Size, Linkage and IsCallable fields left unchanged.
651 }
652
653 void makeAbsolute(Addressable &A) {
654 assert(!A.isDefined() && A.isAbsolute() &&
655 "Attempting to make absolute with defined or external block");
656 Base = &A;
657 Offset = 0;
658 }
659
660 void setBlock(Block &B) { Base = &B; }
661
662 void setOffset(orc::ExecutorAddrDiff NewOffset) {
663 assert(NewOffset <= MaxOffset && "Offset out of range");
664 Offset = NewOffset;
665 }
666
667 static constexpr uint64_t MaxOffset = (1ULL << 59) - 1;
668
669 // FIXME: A char* or SymbolStringPtr may pack better.
670 StringRef Name;
671 Addressable *Base = nullptr;
672 uint64_t Offset : 57;
673 uint64_t L : 1;
674 uint64_t S : 2;
675 uint64_t IsLive : 1;
676 uint64_t IsCallable : 1;
677 uint64_t WeakRef : 1;
678 uint64_t TargetFlags : 1;
679 size_t Size = 0;
680};
681
682raw_ostream &operator<<(raw_ostream &OS, const Symbol &A);
683
684void printEdge(raw_ostream &OS, const Block &B, const Edge &E,
685 StringRef EdgeKindName);
686
687/// Represents an object file section.
688class Section {
689 friend class LinkGraph;
690
691private:
693 : Name(Name), Prot(Prot), SecOrdinal(SecOrdinal) {}
694
695 using SymbolSet = DenseSet<Symbol *>;
696 using BlockSet = DenseSet<Block *>;
697
698public:
701
704
705 ~Section();
706
707 // Sections are not movable or copyable.
708 Section(const Section &) = delete;
709 Section &operator=(const Section &) = delete;
710 Section(Section &&) = delete;
711 Section &operator=(Section &&) = delete;
712
713 /// Returns the name of this section.
714 StringRef getName() const { return Name; }
715
716 /// Returns the protection flags for this section.
717 orc::MemProt getMemProt() const { return Prot; }
718
719 /// Set the protection flags for this section.
720 void setMemProt(orc::MemProt Prot) { this->Prot = Prot; }
721
722 /// Get the memory lifetime policy for this section.
724
725 /// Set the memory lifetime policy for this section.
726 void setMemLifetimePolicy(orc::MemLifetimePolicy MLP) { this->MLP = MLP; }
727
728 /// Returns the ordinal for this section.
729 SectionOrdinal getOrdinal() const { return SecOrdinal; }
730
731 /// Returns true if this section is empty (contains no blocks or symbols).
732 bool empty() const { return Blocks.empty(); }
733
734 /// Returns an iterator over the blocks defined in this section.
736 return make_range(Blocks.begin(), Blocks.end());
737 }
738
739 /// Returns an iterator over the blocks defined in this section.
741 return make_range(Blocks.begin(), Blocks.end());
742 }
743
744 /// Returns the number of blocks in this section.
745 BlockSet::size_type blocks_size() const { return Blocks.size(); }
746
747 /// Returns an iterator over the symbols defined in this section.
749 return make_range(Symbols.begin(), Symbols.end());
750 }
751
752 /// Returns an iterator over the symbols defined in this section.
754 return make_range(Symbols.begin(), Symbols.end());
755 }
756
757 /// Return the number of symbols in this section.
758 SymbolSet::size_type symbols_size() const { return Symbols.size(); }
759
760private:
761 void addSymbol(Symbol &Sym) {
762 assert(!Symbols.count(&Sym) && "Symbol is already in this section");
763 Symbols.insert(&Sym);
764 }
765
766 void removeSymbol(Symbol &Sym) {
767 assert(Symbols.count(&Sym) && "symbol is not in this section");
768 Symbols.erase(&Sym);
769 }
770
771 void addBlock(Block &B) {
772 assert(!Blocks.count(&B) && "Block is already in this section");
773 Blocks.insert(&B);
774 }
775
776 void removeBlock(Block &B) {
777 assert(Blocks.count(&B) && "Block is not in this section");
778 Blocks.erase(&B);
779 }
780
781 void transferContentTo(Section &DstSection) {
782 if (&DstSection == this)
783 return;
784 for (auto *S : Symbols)
785 DstSection.addSymbol(*S);
786 for (auto *B : Blocks)
787 DstSection.addBlock(*B);
788 Symbols.clear();
789 Blocks.clear();
790 }
791
792 StringRef Name;
793 orc::MemProt Prot;
795 SectionOrdinal SecOrdinal = 0;
796 BlockSet Blocks;
797 SymbolSet Symbols;
798};
799
800/// Represents a section address range via a pair of Block pointers
801/// to the first and last Blocks in the section.
803public:
804 SectionRange() = default;
805 SectionRange(const Section &Sec) {
806 if (Sec.blocks().empty())
807 return;
808 First = Last = *Sec.blocks().begin();
809 for (auto *B : Sec.blocks()) {
810 if (B->getAddress() < First->getAddress())
811 First = B;
812 if (B->getAddress() > Last->getAddress())
813 Last = B;
814 }
815 }
817 assert((!Last || First) && "First can not be null if end is non-null");
818 return First;
819 }
821 assert((First || !Last) && "Last can not be null if start is non-null");
822 return Last;
823 }
824 bool empty() const {
825 assert((First || !Last) && "Last can not be null if start is non-null");
826 return !First;
827 }
829 return First ? First->getAddress() : orc::ExecutorAddr();
830 }
832 return Last ? Last->getAddress() + Last->getSize() : orc::ExecutorAddr();
833 }
835
838 }
839
840private:
841 Block *First = nullptr;
842 Block *Last = nullptr;
843};
844
846private:
850
851 template <typename... ArgTs>
852 Addressable &createAddressable(ArgTs &&... Args) {
853 Addressable *A =
854 reinterpret_cast<Addressable *>(Allocator.Allocate<Addressable>());
855 new (A) Addressable(std::forward<ArgTs>(Args)...);
856 return *A;
857 }
858
859 void destroyAddressable(Addressable &A) {
860 A.~Addressable();
861 Allocator.Deallocate(&A);
862 }
863
864 template <typename... ArgTs> Block &createBlock(ArgTs &&... Args) {
865 Block *B = reinterpret_cast<Block *>(Allocator.Allocate<Block>());
866 new (B) Block(std::forward<ArgTs>(Args)...);
867 B->getSection().addBlock(*B);
868 return *B;
869 }
870
871 void destroyBlock(Block &B) {
872 B.~Block();
873 Allocator.Deallocate(&B);
874 }
875
876 void destroySymbol(Symbol &S) {
877 S.~Symbol();
878 Allocator.Deallocate(&S);
879 }
880
881 static iterator_range<Section::block_iterator> getSectionBlocks(Section &S) {
882 return S.blocks();
883 }
884
886 getSectionConstBlocks(const Section &S) {
887 return S.blocks();
888 }
889
891 getSectionSymbols(Section &S) {
892 return S.symbols();
893 }
894
896 getSectionConstSymbols(const Section &S) {
897 return S.symbols();
898 }
899
900 struct GetSectionMapEntryValue {
901 Section &operator()(SectionMap::value_type &KV) const { return *KV.second; }
902 };
903
904 struct GetSectionMapEntryConstValue {
905 const Section &operator()(const SectionMap::value_type &KV) const {
906 return *KV.second;
907 }
908 };
909
910public:
912
917
918 template <typename OuterItrT, typename InnerItrT, typename T,
919 iterator_range<InnerItrT> getInnerRange(
920 typename OuterItrT::reference)>
922 : public iterator_facade_base<
923 nested_collection_iterator<OuterItrT, InnerItrT, T, getInnerRange>,
924 std::forward_iterator_tag, T> {
925 public:
927
928 nested_collection_iterator(OuterItrT OuterI, OuterItrT OuterE)
929 : OuterI(OuterI), OuterE(OuterE),
930 InnerI(getInnerBegin(OuterI, OuterE)) {
931 moveToNonEmptyInnerOrEnd();
932 }
933
935 return (OuterI == RHS.OuterI) && (InnerI == RHS.InnerI);
936 }
937
938 T operator*() const {
939 assert(InnerI != getInnerRange(*OuterI).end() && "Dereferencing end?");
940 return *InnerI;
941 }
942
944 ++InnerI;
945 moveToNonEmptyInnerOrEnd();
946 return *this;
947 }
948
949 private:
950 static InnerItrT getInnerBegin(OuterItrT OuterI, OuterItrT OuterE) {
951 return OuterI != OuterE ? getInnerRange(*OuterI).begin() : InnerItrT();
952 }
953
954 void moveToNonEmptyInnerOrEnd() {
955 while (OuterI != OuterE && InnerI == getInnerRange(*OuterI).end()) {
956 ++OuterI;
957 InnerI = getInnerBegin(OuterI, OuterE);
958 }
959 }
960
961 OuterItrT OuterI, OuterE;
962 InnerItrT InnerI;
963 };
964
967 Symbol *, getSectionSymbols>;
968
972 getSectionConstSymbols>;
973
976 Block *, getSectionBlocks>;
977
981 getSectionConstBlocks>;
982
983 using GetEdgeKindNameFunction = const char *(*)(Edge::Kind);
984
985 LinkGraph(std::string Name, const Triple &TT, unsigned PointerSize,
986 support::endianness Endianness,
987 GetEdgeKindNameFunction GetEdgeKindName)
988 : Name(std::move(Name)), TT(TT), PointerSize(PointerSize),
989 Endianness(Endianness), GetEdgeKindName(std::move(GetEdgeKindName)) {}
990
991 LinkGraph(const LinkGraph &) = delete;
992 LinkGraph &operator=(const LinkGraph &) = delete;
993 LinkGraph(LinkGraph &&) = delete;
995
996 /// Returns the name of this graph (usually the name of the original
997 /// underlying MemoryBuffer).
998 const std::string &getName() const { return Name; }
999
1000 /// Returns the target triple for this Graph.
1001 const Triple &getTargetTriple() const { return TT; }
1002
1003 /// Returns the pointer size for use in this graph.
1004 unsigned getPointerSize() const { return PointerSize; }
1005
1006 /// Returns the endianness of content in this graph.
1007 support::endianness getEndianness() const { return Endianness; }
1008
1009 const char *getEdgeKindName(Edge::Kind K) const { return GetEdgeKindName(K); }
1010
1011 /// Allocate a mutable buffer of the given size using the LinkGraph's
1012 /// allocator.
1014 return {Allocator.Allocate<char>(Size), Size};
1015 }
1016
1017 /// Allocate a copy of the given string using the LinkGraph's allocator.
1018 /// This can be useful when renaming symbols or adding new content to the
1019 /// graph.
1021 auto *AllocatedBuffer = Allocator.Allocate<char>(Source.size());
1022 llvm::copy(Source, AllocatedBuffer);
1023 return MutableArrayRef<char>(AllocatedBuffer, Source.size());
1024 }
1025
1026 /// Allocate a copy of the given string using the LinkGraph's allocator.
1027 /// This can be useful when renaming symbols or adding new content to the
1028 /// graph.
1029 ///
1030 /// Note: This Twine-based overload requires an extra string copy and an
1031 /// extra heap allocation for large strings. The ArrayRef<char> overload
1032 /// should be preferred where possible.
1034 SmallString<256> TmpBuffer;
1035 auto SourceStr = Source.toStringRef(TmpBuffer);
1036 auto *AllocatedBuffer = Allocator.Allocate<char>(SourceStr.size());
1037 llvm::copy(SourceStr, AllocatedBuffer);
1038 return MutableArrayRef<char>(AllocatedBuffer, SourceStr.size());
1039 }
1040
1041 /// Allocate a copy of the given string using the LinkGraph's allocator.
1042 ///
1043 /// The allocated string will be terminated with a null character, and the
1044 /// returned MutableArrayRef will include this null character in the last
1045 /// position.
1047 char *AllocatedBuffer = Allocator.Allocate<char>(Source.size() + 1);
1048 llvm::copy(Source, AllocatedBuffer);
1049 AllocatedBuffer[Source.size()] = '\0';
1050 return MutableArrayRef<char>(AllocatedBuffer, Source.size() + 1);
1051 }
1052
1053 /// Allocate a copy of the given string using the LinkGraph's allocator.
1054 ///
1055 /// The allocated string will be terminated with a null character, and the
1056 /// returned MutableArrayRef will include this null character in the last
1057 /// position.
1058 ///
1059 /// Note: This Twine-based overload requires an extra string copy and an
1060 /// extra heap allocation for large strings. The ArrayRef<char> overload
1061 /// should be preferred where possible.
1063 SmallString<256> TmpBuffer;
1064 auto SourceStr = Source.toStringRef(TmpBuffer);
1065 auto *AllocatedBuffer = Allocator.Allocate<char>(SourceStr.size() + 1);
1066 llvm::copy(SourceStr, AllocatedBuffer);
1067 AllocatedBuffer[SourceStr.size()] = '\0';
1068 return MutableArrayRef<char>(AllocatedBuffer, SourceStr.size() + 1);
1069 }
1070
1071 /// Create a section with the given name, protection flags, and alignment.
1073 assert(!Sections.count(Name) && "Duplicate section name");
1074 std::unique_ptr<Section> Sec(new Section(Name, Prot, Sections.size()));
1075 return *Sections.insert(std::make_pair(Name, std::move(Sec))).first->second;
1076 }
1077
1078 /// Create a content block.
1081 uint64_t AlignmentOffset) {
1082 return createBlock(Parent, Content, Address, Alignment, AlignmentOffset);
1083 }
1084
1085 /// Create a content block with initially mutable data.
1087 MutableArrayRef<char> MutableContent,
1089 uint64_t Alignment,
1090 uint64_t AlignmentOffset) {
1091 return createBlock(Parent, MutableContent, Address, Alignment,
1092 AlignmentOffset);
1093 }
1094
1095 /// Create a content block with initially mutable data of the given size.
1096 /// Content will be allocated via the LinkGraph's allocateBuffer method.
1097 /// By default the memory will be zero-initialized. Passing false for
1098 /// ZeroInitialize will prevent this.
1099 Block &createMutableContentBlock(Section &Parent, size_t ContentSize,
1101 uint64_t Alignment, uint64_t AlignmentOffset,
1102 bool ZeroInitialize = true) {
1103 auto Content = allocateContent(ContentSize);
1104 if (ZeroInitialize)
1105 memset(Content.data(), 0, Content.size());
1106 return createBlock(Parent, Content, Address, Alignment, AlignmentOffset);
1107 }
1108
1109 /// Create a zero-fill block.
1112 uint64_t AlignmentOffset) {
1113 return createBlock(Parent, Size, Address, Alignment, AlignmentOffset);
1114 }
1115
1116 /// Returns a BinaryStreamReader for the given block.
1119 reinterpret_cast<const uint8_t *>(B.getContent().data()), B.getSize());
1121 }
1122
1123 /// Returns a BinaryStreamWriter for the given block.
1124 /// This will call getMutableContent to obtain mutable content for the block.
1127 reinterpret_cast<uint8_t *>(B.getMutableContent(*this).data()),
1128 B.getSize());
1130 }
1131
1132 /// Cache type for the splitBlock function.
1133 using SplitBlockCache = std::optional<SmallVector<Symbol *, 8>>;
1134
1135 /// Splits block B at the given index which must be greater than zero.
1136 /// If SplitIndex == B.getSize() then this function is a no-op and returns B.
1137 /// If SplitIndex < B.getSize() then this function returns a new block
1138 /// covering the range [ 0, SplitIndex ), and B is modified to cover the range
1139 /// [ SplitIndex, B.size() ).
1140 ///
1141 /// The optional Cache parameter can be used to speed up repeated calls to
1142 /// splitBlock for a single block. If the value is None the cache will be
1143 /// treated as uninitialized and splitBlock will populate it. Otherwise it
1144 /// is assumed to contain the list of Symbols pointing at B, sorted in
1145 /// descending order of offset.
1146 ///
1147 /// Notes:
1148 ///
1149 /// 1. splitBlock must be used with care. Splitting a block may cause
1150 /// incoming edges to become invalid if the edge target subexpression
1151 /// points outside the bounds of the newly split target block (E.g. an
1152 /// edge 'S + 10 : Pointer64' where S points to a newly split block
1153 /// whose size is less than 10). No attempt is made to detect invalidation
1154 /// of incoming edges, as in general this requires context that the
1155 /// LinkGraph does not have. Clients are responsible for ensuring that
1156 /// splitBlock is not used in a way that invalidates edges.
1157 ///
1158 /// 2. The newly introduced block will have a new ordinal which will be
1159 /// higher than any other ordinals in the section. Clients are responsible
1160 /// for re-assigning block ordinals to restore a compatible order if
1161 /// needed.
1162 ///
1163 /// 3. The cache is not automatically updated if new symbols are introduced
1164 /// between calls to splitBlock. Any newly introduced symbols may be
1165 /// added to the cache manually (descending offset order must be
1166 /// preserved), or the cache can be set to None and rebuilt by
1167 /// splitBlock on the next call.
1168 Block &splitBlock(Block &B, size_t SplitIndex,
1169 SplitBlockCache *Cache = nullptr);
1170
1171 /// Add an external symbol.
1172 /// Some formats (e.g. ELF) allow Symbols to have sizes. For Symbols whose
1173 /// size is not known, you should substitute '0'.
1174 /// The IsWeaklyReferenced argument determines whether the symbol must be
1175 /// present during lookup: Externals that are strongly referenced must be
1176 /// found or an error will be emitted. Externals that are weakly referenced
1177 /// are permitted to be undefined, in which case they are assigned an address
1178 /// of 0.
1180 bool IsWeaklyReferenced) {
1181 assert(llvm::count_if(ExternalSymbols,
1182 [&](const Symbol *Sym) {
1183 return Sym->getName() == Name;
1184 }) == 0 &&
1185 "Duplicate external symbol");
1186 auto &Sym = Symbol::constructExternal(
1187 Allocator, createAddressable(orc::ExecutorAddr(), false), Name, Size,
1188 Linkage::Strong, IsWeaklyReferenced);
1189 ExternalSymbols.insert(&Sym);
1190 return Sym;
1191 }
1192
1193 /// Add an absolute symbol.
1196 bool IsLive) {
1197 assert((S == Scope::Local || llvm::count_if(AbsoluteSymbols,
1198 [&](const Symbol *Sym) {
1199 return Sym->getName() == Name;
1200 }) == 0) &&
1201 "Duplicate absolute symbol");
1202 auto &Sym = Symbol::constructAbsolute(Allocator, createAddressable(Address),
1203 Name, Size, L, S, IsLive);
1204 AbsoluteSymbols.insert(&Sym);
1205 return Sym;
1206 }
1207
1208 /// Add an anonymous symbol.
1210 orc::ExecutorAddrDiff Size, bool IsCallable,
1211 bool IsLive) {
1212 auto &Sym = Symbol::constructAnonDef(Allocator, Content, Offset, Size,
1213 IsCallable, IsLive);
1214 Content.getSection().addSymbol(Sym);
1215 return Sym;
1216 }
1217
1218 /// Add a named symbol.
1221 Linkage L, Scope S, bool IsCallable, bool IsLive) {
1223 [&](const Symbol *Sym) {
1224 return Sym->getName() == Name;
1225 }) == 0) &&
1226 "Duplicate defined symbol");
1227 auto &Sym = Symbol::constructNamedDef(Allocator, Content, Offset, Name,
1228 Size, L, S, IsLive, IsCallable);
1229 Content.getSection().addSymbol(Sym);
1230 return Sym;
1231 }
1232
1234 return make_range(
1235 section_iterator(Sections.begin(), GetSectionMapEntryValue()),
1236 section_iterator(Sections.end(), GetSectionMapEntryValue()));
1237 }
1238
1240 return make_range(
1241 const_section_iterator(Sections.begin(),
1242 GetSectionMapEntryConstValue()),
1243 const_section_iterator(Sections.end(), GetSectionMapEntryConstValue()));
1244 }
1245
1246 size_t sections_size() const { return Sections.size(); }
1247
1248 /// Returns the section with the given name if it exists, otherwise returns
1249 /// null.
1251 auto I = Sections.find(Name);
1252 if (I == Sections.end())
1253 return nullptr;
1254 return I->second.get();
1255 }
1256
1258 auto Secs = sections();
1259 return make_range(block_iterator(Secs.begin(), Secs.end()),
1260 block_iterator(Secs.end(), Secs.end()));
1261 }
1262
1264 auto Secs = sections();
1265 return make_range(const_block_iterator(Secs.begin(), Secs.end()),
1266 const_block_iterator(Secs.end(), Secs.end()));
1267 }
1268
1270 return make_range(ExternalSymbols.begin(), ExternalSymbols.end());
1271 }
1272
1274 return make_range(AbsoluteSymbols.begin(), AbsoluteSymbols.end());
1275 }
1276
1278 auto Secs = sections();
1279 return make_range(defined_symbol_iterator(Secs.begin(), Secs.end()),
1280 defined_symbol_iterator(Secs.end(), Secs.end()));
1281 }
1282
1284 auto Secs = sections();
1285 return make_range(const_defined_symbol_iterator(Secs.begin(), Secs.end()),
1286 const_defined_symbol_iterator(Secs.end(), Secs.end()));
1287 }
1288
1289 /// Make the given symbol external (must not already be external).
1290 ///
1291 /// Symbol size, linkage and callability will be left unchanged. Symbol scope
1292 /// will be set to Default, and offset will be reset to 0.
1294 assert(!Sym.isExternal() && "Symbol is already external");
1295 if (Sym.isAbsolute()) {
1296 assert(AbsoluteSymbols.count(&Sym) &&
1297 "Sym is not in the absolute symbols set");
1298 assert(Sym.getOffset() == 0 && "Absolute not at offset 0");
1299 AbsoluteSymbols.erase(&Sym);
1300 auto &A = Sym.getAddressable();
1301 A.setAbsolute(false);
1302 A.setAddress(orc::ExecutorAddr());
1303 } else {
1304 assert(Sym.isDefined() && "Sym is not a defined symbol");
1305 Section &Sec = Sym.getBlock().getSection();
1306 Sec.removeSymbol(Sym);
1307 Sym.makeExternal(createAddressable(orc::ExecutorAddr(), false));
1308 }
1309 ExternalSymbols.insert(&Sym);
1310 }
1311
1312 /// Make the given symbol an absolute with the given address (must not already
1313 /// be absolute).
1314 ///
1315 /// The symbol's size, linkage, and callability, and liveness will be left
1316 /// unchanged, and its offset will be reset to 0.
1317 ///
1318 /// If the symbol was external then its scope will be set to local, otherwise
1319 /// it will be left unchanged.
1321 assert(!Sym.isAbsolute() && "Symbol is already absolute");
1322 if (Sym.isExternal()) {
1323 assert(ExternalSymbols.count(&Sym) &&
1324 "Sym is not in the absolute symbols set");
1325 assert(Sym.getOffset() == 0 && "External is not at offset 0");
1326 ExternalSymbols.erase(&Sym);
1327 auto &A = Sym.getAddressable();
1328 A.setAbsolute(true);
1329 A.setAddress(Address);
1331 } else {
1332 assert(Sym.isDefined() && "Sym is not a defined symbol");
1333 Section &Sec = Sym.getBlock().getSection();
1334 Sec.removeSymbol(Sym);
1335 Sym.makeAbsolute(createAddressable(Address));
1336 }
1337 AbsoluteSymbols.insert(&Sym);
1338 }
1339
1340 /// Turn an absolute or external symbol into a defined one by attaching it to
1341 /// a block. Symbol must not already be defined.
1344 bool IsLive) {
1345 assert(!Sym.isDefined() && "Sym is already a defined symbol");
1346 if (Sym.isAbsolute()) {
1347 assert(AbsoluteSymbols.count(&Sym) &&
1348 "Symbol is not in the absolutes set");
1349 AbsoluteSymbols.erase(&Sym);
1350 } else {
1351 assert(ExternalSymbols.count(&Sym) &&
1352 "Symbol is not in the externals set");
1353 ExternalSymbols.erase(&Sym);
1354 }
1355 Addressable &OldBase = *Sym.Base;
1356 Sym.setBlock(Content);
1357 Sym.setOffset(Offset);
1358 Sym.setSize(Size);
1359 Sym.setLinkage(L);
1360 Sym.setScope(S);
1361 Sym.setLive(IsLive);
1362 Content.getSection().addSymbol(Sym);
1363 destroyAddressable(OldBase);
1364 }
1365
1366 /// Transfer a defined symbol from one block to another.
1367 ///
1368 /// The symbol's offset within DestBlock is set to NewOffset.
1369 ///
1370 /// If ExplicitNewSize is given as None then the size of the symbol will be
1371 /// checked and auto-truncated to at most the size of the remainder (from the
1372 /// given offset) of the size of the new block.
1373 ///
1374 /// All other symbol attributes are unchanged.
1375 void
1377 orc::ExecutorAddrDiff NewOffset,
1378 std::optional<orc::ExecutorAddrDiff> ExplicitNewSize) {
1379 auto &OldSection = Sym.getBlock().getSection();
1380 Sym.setBlock(DestBlock);
1381 Sym.setOffset(NewOffset);
1382 if (ExplicitNewSize)
1383 Sym.setSize(*ExplicitNewSize);
1384 else {
1385 auto RemainingBlockSize = DestBlock.getSize() - NewOffset;
1386 if (Sym.getSize() > RemainingBlockSize)
1387 Sym.setSize(RemainingBlockSize);
1388 }
1389 if (&DestBlock.getSection() != &OldSection) {
1390 OldSection.removeSymbol(Sym);
1391 DestBlock.getSection().addSymbol(Sym);
1392 }
1393 }
1394
1395 /// Transfers the given Block and all Symbols pointing to it to the given
1396 /// Section.
1397 ///
1398 /// No attempt is made to check compatibility of the source and destination
1399 /// sections. Blocks may be moved between sections with incompatible
1400 /// permissions (e.g. from data to text). The client is responsible for
1401 /// ensuring that this is safe.
1402 void transferBlock(Block &B, Section &NewSection) {
1403 auto &OldSection = B.getSection();
1404 if (&OldSection == &NewSection)
1405 return;
1406 SmallVector<Symbol *> AttachedSymbols;
1407 for (auto *S : OldSection.symbols())
1408 if (&S->getBlock() == &B)
1409 AttachedSymbols.push_back(S);
1410 for (auto *S : AttachedSymbols) {
1411 OldSection.removeSymbol(*S);
1412 NewSection.addSymbol(*S);
1413 }
1414 OldSection.removeBlock(B);
1415 NewSection.addBlock(B);
1416 }
1417
1418 /// Move all blocks and symbols from the source section to the destination
1419 /// section.
1420 ///
1421 /// If PreserveSrcSection is true (or SrcSection and DstSection are the same)
1422 /// then SrcSection is preserved, otherwise it is removed (the default).
1423 void mergeSections(Section &DstSection, Section &SrcSection,
1424 bool PreserveSrcSection = false) {
1425 if (&DstSection == &SrcSection)
1426 return;
1427 for (auto *B : SrcSection.blocks())
1428 B->setSection(DstSection);
1429 SrcSection.transferContentTo(DstSection);
1430 if (!PreserveSrcSection)
1431 removeSection(SrcSection);
1432 }
1433
1434 /// Removes an external symbol. Also removes the underlying Addressable.
1436 assert(!Sym.isDefined() && !Sym.isAbsolute() &&
1437 "Sym is not an external symbol");
1438 assert(ExternalSymbols.count(&Sym) && "Symbol is not in the externals set");
1439 ExternalSymbols.erase(&Sym);
1440 Addressable &Base = *Sym.Base;
1441 assert(llvm::none_of(ExternalSymbols,
1442 [&](Symbol *AS) { return AS->Base == &Base; }) &&
1443 "Base addressable still in use");
1444 destroySymbol(Sym);
1445 destroyAddressable(Base);
1446 }
1447
1448 /// Remove an absolute symbol. Also removes the underlying Addressable.
1450 assert(!Sym.isDefined() && Sym.isAbsolute() &&
1451 "Sym is not an absolute symbol");
1452 assert(AbsoluteSymbols.count(&Sym) &&
1453 "Symbol is not in the absolute symbols set");
1454 AbsoluteSymbols.erase(&Sym);
1455 Addressable &Base = *Sym.Base;
1456 assert(llvm::none_of(ExternalSymbols,
1457 [&](Symbol *AS) { return AS->Base == &Base; }) &&
1458 "Base addressable still in use");
1459 destroySymbol(Sym);
1460 destroyAddressable(Base);
1461 }
1462
1463 /// Removes defined symbols. Does not remove the underlying block.
1465 assert(Sym.isDefined() && "Sym is not a defined symbol");
1466 Sym.getBlock().getSection().removeSymbol(Sym);
1467 destroySymbol(Sym);
1468 }
1469
1470 /// Remove a block. The block reference is defunct after calling this
1471 /// function and should no longer be used.
1473 assert(llvm::none_of(B.getSection().symbols(),
1474 [&](const Symbol *Sym) {
1475 return &Sym->getBlock() == &B;
1476 }) &&
1477 "Block still has symbols attached");
1478 B.getSection().removeBlock(B);
1479 destroyBlock(B);
1480 }
1481
1482 /// Remove a section. The section reference is defunct after calling this
1483 /// function and should no longer be used.
1485 assert(Sections.count(Sec.getName()) && "Section not found");
1486 assert(Sections.find(Sec.getName())->second.get() == &Sec &&
1487 "Section map entry invalid");
1488 Sections.erase(Sec.getName());
1489 }
1490
1491 /// Accessor for the AllocActions object for this graph. This can be used to
1492 /// register allocation action calls prior to finalization.
1493 ///
1494 /// Accessing this object after finalization will result in undefined
1495 /// behavior.
1497
1498 /// Dump the graph.
1499 void dump(raw_ostream &OS);
1500
1501private:
1502 // Put the BumpPtrAllocator first so that we don't free any of the underlying
1503 // memory until the Symbol/Addressable destructors have been run.
1505
1506 std::string Name;
1507 Triple TT;
1508 unsigned PointerSize;
1509 support::endianness Endianness;
1510 GetEdgeKindNameFunction GetEdgeKindName = nullptr;
1512 ExternalSymbolSet ExternalSymbols;
1513 ExternalSymbolSet AbsoluteSymbols;
1515};
1516
1518 if (!ContentMutable)
1519 setMutableContent(G.allocateContent({Data, Size}));
1520 return MutableArrayRef<char>(const_cast<char *>(Data), Size);
1521}
1522
1523/// Enables easy lookup of blocks by addresses.
1525public:
1526 using AddrToBlockMap = std::map<orc::ExecutorAddr, Block *>;
1527 using const_iterator = AddrToBlockMap::const_iterator;
1528
1529 /// A block predicate that always adds all blocks.
1530 static bool includeAllBlocks(const Block &B) { return true; }
1531
1532 /// A block predicate that always includes blocks with non-null addresses.
1533 static bool includeNonNull(const Block &B) { return !!B.getAddress(); }
1534
1535 BlockAddressMap() = default;
1536
1537 /// Add a block to the map. Returns an error if the block overlaps with any
1538 /// existing block.
1539 template <typename PredFn = decltype(includeAllBlocks)>
1541 if (!Pred(B))
1542 return Error::success();
1543
1544 auto I = AddrToBlock.upper_bound(B.getAddress());
1545
1546 // If we're not at the end of the map, check for overlap with the next
1547 // element.
1548 if (I != AddrToBlock.end()) {
1549 if (B.getAddress() + B.getSize() > I->second->getAddress())
1550 return overlapError(B, *I->second);
1551 }
1552
1553 // If we're not at the start of the map, check for overlap with the previous
1554 // element.
1555 if (I != AddrToBlock.begin()) {
1556 auto &PrevBlock = *std::prev(I)->second;
1557 if (PrevBlock.getAddress() + PrevBlock.getSize() > B.getAddress())
1558 return overlapError(B, PrevBlock);
1559 }
1560
1561 AddrToBlock.insert(I, std::make_pair(B.getAddress(), &B));
1562 return Error::success();
1563 }
1564
1565 /// Add a block to the map without checking for overlap with existing blocks.
1566 /// The client is responsible for ensuring that the block added does not
1567 /// overlap with any existing block.
1568 void addBlockWithoutChecking(Block &B) { AddrToBlock[B.getAddress()] = &B; }
1569
1570 /// Add a range of blocks to the map. Returns an error if any block in the
1571 /// range overlaps with any other block in the range, or with any existing
1572 /// block in the map.
1573 template <typename BlockPtrRange,
1574 typename PredFn = decltype(includeAllBlocks)>
1575 Error addBlocks(BlockPtrRange &&Blocks, PredFn Pred = includeAllBlocks) {
1576 for (auto *B : Blocks)
1577 if (auto Err = addBlock(*B, Pred))
1578 return Err;
1579 return Error::success();
1580 }
1581
1582 /// Add a range of blocks to the map without checking for overlap with
1583 /// existing blocks. The client is responsible for ensuring that the block
1584 /// added does not overlap with any existing block.
1585 template <typename BlockPtrRange>
1586 void addBlocksWithoutChecking(BlockPtrRange &&Blocks) {
1587 for (auto *B : Blocks)
1589 }
1590
1591 /// Iterates over (Address, Block*) pairs in ascending order of address.
1592 const_iterator begin() const { return AddrToBlock.begin(); }
1593 const_iterator end() const { return AddrToBlock.end(); }
1594
1595 /// Returns the block starting at the given address, or nullptr if no such
1596 /// block exists.
1598 auto I = AddrToBlock.find(Addr);
1599 if (I == AddrToBlock.end())
1600 return nullptr;
1601 return I->second;
1602 }
1603
1604 /// Returns the block covering the given address, or nullptr if no such block
1605 /// exists.
1607 auto I = AddrToBlock.upper_bound(Addr);
1608 if (I == AddrToBlock.begin())
1609 return nullptr;
1610 auto *B = std::prev(I)->second;
1611 if (Addr < B->getAddress() + B->getSize())
1612 return B;
1613 return nullptr;
1614 }
1615
1616private:
1617 Error overlapError(Block &NewBlock, Block &ExistingBlock) {
1618 auto NewBlockEnd = NewBlock.getAddress() + NewBlock.getSize();
1619 auto ExistingBlockEnd =
1620 ExistingBlock.getAddress() + ExistingBlock.getSize();
1621 return make_error<JITLinkError>(
1622 "Block at " +
1623 formatv("{0:x16} -- {1:x16}", NewBlock.getAddress().getValue(),
1624 NewBlockEnd.getValue()) +
1625 " overlaps " +
1626 formatv("{0:x16} -- {1:x16}", ExistingBlock.getAddress().getValue(),
1627 ExistingBlockEnd.getValue()));
1628 }
1629
1630 AddrToBlockMap AddrToBlock;
1631};
1632
1633/// A map of addresses to Symbols.
1635public:
1637
1638 /// Add a symbol to the SymbolAddressMap.
1639 void addSymbol(Symbol &Sym) {
1640 AddrToSymbols[Sym.getAddress()].push_back(&Sym);
1641 }
1642
1643 /// Add all symbols in a given range to the SymbolAddressMap.
1644 template <typename SymbolPtrCollection>
1645 void addSymbols(SymbolPtrCollection &&Symbols) {
1646 for (auto *Sym : Symbols)
1647 addSymbol(*Sym);
1648 }
1649
1650 /// Returns the list of symbols that start at the given address, or nullptr if
1651 /// no such symbols exist.
1653 auto I = AddrToSymbols.find(Addr);
1654 if (I == AddrToSymbols.end())
1655 return nullptr;
1656 return &I->second;
1657 }
1658
1659private:
1660 std::map<orc::ExecutorAddr, SymbolVector> AddrToSymbols;
1661};
1662
1663/// A function for mutating LinkGraphs.
1665
1666/// A list of LinkGraph passes.
1667using LinkGraphPassList = std::vector<LinkGraphPassFunction>;
1668
1669/// An LinkGraph pass configuration, consisting of a list of pre-prune,
1670/// post-prune, and post-fixup passes.
1672
1673 /// Pre-prune passes.
1674 ///
1675 /// These passes are called on the graph after it is built, and before any
1676 /// symbols have been pruned. Graph nodes still have their original vmaddrs.
1677 ///
1678 /// Notable use cases: Marking symbols live or should-discard.
1680
1681 /// Post-prune passes.
1682 ///
1683 /// These passes are called on the graph after dead stripping, but before
1684 /// memory is allocated or nodes assigned their final addresses.
1685 ///
1686 /// Notable use cases: Building GOT, stub, and TLV symbols.
1688
1689 /// Post-allocation passes.
1690 ///
1691 /// These passes are called on the graph after memory has been allocated and
1692 /// defined nodes have been assigned their final addresses, but before the
1693 /// context has been notified of these addresses. At this point externals
1694 /// have not been resolved, and symbol content has not yet been copied into
1695 /// working memory.
1696 ///
1697 /// Notable use cases: Setting up data structures associated with addresses
1698 /// of defined symbols (e.g. a mapping of __dso_handle to JITDylib* for the
1699 /// JIT runtime) -- using a PostAllocationPass for this ensures that the
1700 /// data structures are in-place before any query for resolved symbols
1701 /// can complete.
1703
1704 /// Pre-fixup passes.
1705 ///
1706 /// These passes are called on the graph after memory has been allocated,
1707 /// content copied into working memory, and all nodes (including externals)
1708 /// have been assigned their final addresses, but before any fixups have been
1709 /// applied.
1710 ///
1711 /// Notable use cases: Late link-time optimizations like GOT and stub
1712 /// elimination.
1714
1715 /// Post-fixup passes.
1716 ///
1717 /// These passes are called on the graph after block contents has been copied
1718 /// to working memory, and fixups applied. Blocks have been updated to point
1719 /// to their fixed up content.
1720 ///
1721 /// Notable use cases: Testing and validation.
1723};
1724
1725/// Flags for symbol lookup.
1726///
1727/// FIXME: These basically duplicate orc::SymbolLookupFlags -- We should merge
1728/// the two types once we have an OrcSupport library.
1730
1732
1733/// A map of symbol names to resolved addresses.
1735
1736/// A function object to call with a resolved symbol map (See AsyncLookupResult)
1737/// or an error if resolution failed.
1739public:
1741 virtual void run(Expected<AsyncLookupResult> LR) = 0;
1742
1743private:
1744 virtual void anchor();
1745};
1746
1747/// Create a lookup continuation from a function object.
1748template <typename Continuation>
1749std::unique_ptr<JITLinkAsyncLookupContinuation>
1750createLookupContinuation(Continuation Cont) {
1751
1752 class Impl final : public JITLinkAsyncLookupContinuation {
1753 public:
1754 Impl(Continuation C) : C(std::move(C)) {}
1755 void run(Expected<AsyncLookupResult> LR) override { C(std::move(LR)); }
1756
1757 private:
1758 Continuation C;
1759 };
1760
1761 return std::make_unique<Impl>(std::move(Cont));
1762}
1763
1764/// Holds context for a single jitLink invocation.
1766public:
1768
1769 /// Create a JITLinkContext.
1770 JITLinkContext(const JITLinkDylib *JD) : JD(JD) {}
1771
1772 /// Destroy a JITLinkContext.
1774
1775 /// Return the JITLinkDylib that this link is targeting, if any.
1776 const JITLinkDylib *getJITLinkDylib() const { return JD; }
1777
1778 /// Return the MemoryManager to be used for this link.
1780
1781 /// Notify this context that linking failed.
1782 /// Called by JITLink if linking cannot be completed.
1783 virtual void notifyFailed(Error Err) = 0;
1784
1785 /// Called by JITLink to resolve external symbols. This method is passed a
1786 /// lookup continutation which it must call with a result to continue the
1787 /// linking process.
1788 virtual void lookup(const LookupMap &Symbols,
1789 std::unique_ptr<JITLinkAsyncLookupContinuation> LC) = 0;
1790
1791 /// Called by JITLink once all defined symbols in the graph have been assigned
1792 /// their final memory locations in the target process. At this point the
1793 /// LinkGraph can be inspected to build a symbol table, however the block
1794 /// content will not generally have been copied to the target location yet.
1795 ///
1796 /// If the client detects an error in the LinkGraph state (e.g. unexpected or
1797 /// missing symbols) they may return an error here. The error will be
1798 /// propagated to notifyFailed and the linker will bail out.
1800
1801 /// Called by JITLink to notify the context that the object has been
1802 /// finalized (i.e. emitted to memory and memory permissions set). If all of
1803 /// this objects dependencies have also been finalized then the code is ready
1804 /// to run.
1806
1807 /// Called by JITLink prior to linking to determine whether default passes for
1808 /// the target should be added. The default implementation returns true.
1809 /// If subclasses override this method to return false for any target then
1810 /// they are required to fully configure the pass pipeline for that target.
1811 virtual bool shouldAddDefaultTargetPasses(const Triple &TT) const;
1812
1813 /// Returns the mark-live pass to be used for this link. If no pass is
1814 /// returned (the default) then the target-specific linker implementation will
1815 /// choose a conservative default (usually marking all symbols live).
1816 /// This function is only called if shouldAddDefaultTargetPasses returns true,
1817 /// otherwise the JITContext is responsible for adding a mark-live pass in
1818 /// modifyPassConfig.
1819 virtual LinkGraphPassFunction getMarkLivePass(const Triple &TT) const;
1820
1821 /// Called by JITLink to modify the pass pipeline prior to linking.
1822 /// The default version performs no modification.
1824
1825private:
1826 const JITLinkDylib *JD = nullptr;
1827};
1828
1829/// Marks all symbols in a graph live. This can be used as a default,
1830/// conservative mark-live implementation.
1832
1833/// Create an out of range error for the given edge in the given block.
1835 const Edge &E);
1836
1838 const Edge &E);
1839
1840/// Base case for edge-visitors where the visitor-list is empty.
1841inline void visitEdge(LinkGraph &G, Block *B, Edge &E) {}
1842
1843/// Applies the first visitor in the list to the given edge. If the visitor's
1844/// visitEdge method returns true then we return immediately, otherwise we
1845/// apply the next visitor.
1846template <typename VisitorT, typename... VisitorTs>
1847void visitEdge(LinkGraph &G, Block *B, Edge &E, VisitorT &&V,
1848 VisitorTs &&...Vs) {
1849 if (!V.visitEdge(G, B, E))
1850 visitEdge(G, B, E, std::forward<VisitorTs>(Vs)...);
1851}
1852
1853/// For each edge in the given graph, apply a list of visitors to the edge,
1854/// stopping when the first visitor's visitEdge method returns true.
1855///
1856/// Only visits edges that were in the graph at call time: if any visitor
1857/// adds new edges those will not be visited. Visitors are not allowed to
1858/// remove edges (though they can change their kind, target, and addend).
1859template <typename... VisitorTs>
1860void visitExistingEdges(LinkGraph &G, VisitorTs &&...Vs) {
1861 // We may add new blocks during this process, but we don't want to iterate
1862 // over them, so build a worklist.
1863 std::vector<Block *> Worklist(G.blocks().begin(), G.blocks().end());
1864
1865 for (auto *B : Worklist)
1866 for (auto &E : B->edges())
1867 visitEdge(G, B, E, std::forward<VisitorTs>(Vs)...);
1868}
1869
1870/// Create a LinkGraph from the given object buffer.
1871///
1872/// Note: The graph does not take ownership of the underlying buffer, nor copy
1873/// its contents. The caller is responsible for ensuring that the object buffer
1874/// outlives the graph.
1877
1878/// Link the given graph.
1879void link(std::unique_ptr<LinkGraph> G, std::unique_ptr<JITLinkContext> Ctx);
1880
1881} // end namespace jitlink
1882} // end namespace llvm
1883
1884#endif // LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H
This file defines the BumpPtrAllocator interface.
basic Basic Alias true
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
uint64_t Offset
T Content
uint64_t Addr
std::string Name
uint64_t Size
static void addSymbol(Object &Obj, const NewSymbolInfo &SymInfo, uint8_t DefaultVisibility)
Definition: ELFObjcopy.cpp:530
static void makeAbsolute(SmallVectorImpl< char > &Path)
Make Path absolute.
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
#define T
Basic Register Allocator
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
@ Flags
Definition: TextStubV5.cpp:93
@ Data
Definition: TextStubV5.cpp:111
Value * RHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array.
Definition: ArrayRef.h:193
Provides read only access to a subclass of BinaryStream.
Provides write only access to a subclass of WritableBinaryStream.
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
BucketT value_type
Definition: DenseMap.h:69
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Base class for user error types.
Definition: Error.h:348
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
static ErrorSuccess success()
Create a success value.
Definition: Error.h:330
Tagged union holding either a T or a Error.
Definition: Error.h:470
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:305
T * data() const
Definition: ArrayRef.h:352
SmallString - A SmallString is just a SmallVector with methods and accessors that make it work better...
Definition: SmallString.h:26
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Target - Wrapper for Target specific information.
Triple - Helper class for working with autoconf configuration names.
Definition: Triple.h:44
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
LLVM Value Representation.
Definition: Value.h:74
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
ConstIterator const_iterator
Definition: DenseSet.h:171
size_type size() const
Definition: DenseSet.h:81
bool erase(const ValueT &V)
Definition: DenseSet.h:101
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
A range adaptor for a pair of iterators.
Represents an address in the executor process.
uint64_t getValue() const
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
unique_function is a type-erasing functor similar to std::function.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
std::vector< AllocActionCallPair > AllocActions
A vector of allocation actions to be run for this allocation.
MemProt
Describes Read/Write/Exec permissions for memory.
Definition: MemoryFlags.h:27
uint64_t ExecutorAddrDiff
MemLifetimePolicy
Describes a memory lifetime policy for memory to be allocated by a JITLinkMemoryManager.
Definition: MemoryFlags.h:75
@ Standard
Standard memory should be allocated by the allocator and then deallocated when the deallocate method ...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:406
auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object< decltype(std::make_tuple(detail::build_format_adapter(std::forward< Ts >(Vals))...))>
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1777
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:297
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Definition: bit.h:179
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1833
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:375
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1921
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1946
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:2018
Definition: BitVector.h:858
#define N
Represents an address range in the exceutor process.