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